akmalsyrf opened a new pull request, #1740:
URL: https://github.com/apache/casbin/pull/1740
## Summary
Adds cheap fast paths to `KeyMatch2`, `KeyMatch3`, `KeyMatch4`, and
`KeyMatch5` so matching short-circuits before string transforms and
`RegexMatch` when:
1. `key1 == key2` → `true`
2. `key2 == "*"` → `true` (same as today's `RegexMatch` against `^*$`)
3. `key2` has no pattern metacharacters (`*`, `:`, or `{` depending on the
matcher) → `false` (equality already checked)
**Why:** With `AddNamedDomainMatchingFunc("g", ..., KeyMatch2)` (or
KeyMatch3/4/5), `DomainManager` evaluates the matcher O(N×D) times while
building role links. Many real deployments use mostly **concrete** domains
(`team/123`, `org/456`, …) plus a bare `"*"` admin/wildcard domain. After
#1721, `RegexMatch` no longer recompiles on every call, but literal≠literal
comparisons still pay for `strings.Replace`, pattern `ReplaceAllString`, map
lookup, and `MatchString`. That remains the dominant cost for large domain
graphs and shows up as Lambda / process cold-start time when policies are
loaded on boot.
This is **behaviour-preserving** for existing tests and for the cases above
(verified against current `KeyMatch2("team/1", "*") == true`, etc.).
Related:
- Fixes a major practical hotspot called out in #1004 (does **not** fully
solve #1004’s O(N²) role-manager architecture; that needs distinguishing
pattern vs plain domains)
- Complements #1721 (cached `RegexMatch`)
- Related in spirit to #1699 (fast path around unconditional
`strings.Replace`), but targets the higher-impact literal / `"*"` cases
## Motivation / production context
We hit multi-second Casbin cold starts once the `g` policy graph grew
(thousands of domain-scoped grouping rules + one `g, admin, *`). Profiling
pointed at domain matching during `BuildRoleLinks`. A thin equality/`*`
short-circuit recovered most of the cost; this PR lifts that optimization into
the shared matchers so all KeyMatch users benefit.
## Change details
| Matcher | Pattern chars checked | Notes |
|---------|----------------------|--------|
| `KeyMatch2` | `*`, `:` | RESTful `:param` + `*` |
| `KeyMatch3` | `*`, `{` | `{param}` style |
| `KeyMatch4` | `*`, `{` | same metacharacters; repeated-token logic
unchanged |
| `KeyMatch5` | `*`, `{` | query string stripped **before** fast paths
(preserves `/foo?x=1` vs `/foo`) |
REST / patterned inputs still take the existing transform + `RegexMatch`
path.
## Test plan
- [x] `go test ./util/` — existing KeyMatch suites + new cases for bare
`"*"`, unequal literals, equal literals
- [x] `go test ./...` — full suite green
- [x] New benchmarks:
- `BenchmarkKeyMatch2_LiteralDomains` — N=1200 concrete domains + `"*"`
(all-pairs)
- `BenchmarkKeyMatch2_RESTPatterns` — patterned paths still exercise regex
path
Local results (Linux amd64, `-benchtime=3x`):
```
BenchmarkKeyMatch2_LiteralDomains-14 3 33255274 ns/op 0 B/op
0 allocs/op
BenchmarkKeyMatch2_RESTPatterns-14 3 42056 ns/op 14026 B/op
23 allocs/op
```
Literal all-pairs is **0 allocs** after this change (previously every call
went through pattern rewrite + cached regexp match).
## Out of scope
- Redesigning `DomainManager` to index pattern vs plain domains (#1004 root
cause)
- Changing KeyMatch / GlobMatch APIs
- Adapter or enforcer API changes
Made with [Cursor](https://cursor.com)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
