This is an automated email from the ASF dual-hosted git repository.
hsluoyz pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/casbin-pycasbin.git
The following commit(s) were added to refs/heads/master by this push:
new 598d64a fix: speed up key_match with multiple wildcards
598d64a is described below
commit 598d64abcd0b99cf1349ed287bf885a279d3792e
Author: Yang Luo <[email protected]>
AuthorDate: Sat Oct 10 01:55:30 2026 +0800
fix: speed up key_match with multiple wildcards
---
casbin/synced_enforcer.py | 4 +-
casbin/util/builtin_operators.py | 73 ++++++++++++++++++++++++++++++++++--
tests/util/test_builtin_operators.py | 9 +++++
3 files changed, 81 insertions(+), 5 deletions(-)
diff --git a/casbin/synced_enforcer.py b/casbin/synced_enforcer.py
index 8e5e028..bfd714a 100644
--- a/casbin/synced_enforcer.py
+++ b/casbin/synced_enforcer.py
@@ -215,7 +215,7 @@ class SyncedEnforcer:
def get_adapter(self):
"""gets the current adapter."""
with self._rl:
- self._e.get_adapter()
+ return self._e.get_adapter()
def set_adapter(self, adapter):
"""sets the current adapter."""
@@ -712,7 +712,7 @@ class SyncedEnforcer:
def is_filtered(self):
"""returns true if the loaded policy has been filtered."""
with self._rl:
- self._e.is_filtered()
+ return self._e.is_filtered()
def add_policies(self, rules):
"""adds authorization rules to the current policy.
diff --git a/casbin/util/builtin_operators.py b/casbin/util/builtin_operators.py
index 2aff2ad..99075a9 100644
--- a/casbin/util/builtin_operators.py
+++ b/casbin/util/builtin_operators.py
@@ -14,6 +14,7 @@
import ipaddress
import re
+from functools import lru_cache
from datetime import datetime
import wcmatch.glob as glob
@@ -23,6 +24,72 @@ KEY_MATCH4_PATTERN = re.compile(r"{([^/]+)}")
KEY_MATCH5_PATTERN = re.compile(r"{[^/]+}")
+WILDCARD_PATTERN = re.compile(r"\.\*|\[\^\\?/\]\+|\.|[^\\^$.|?*+()\[\]{}]")
+
+
+def _any_char(c):
+ return c != "\n"
+
+
+def _segment_char(c):
+ return c != "/"
+
+
+@lru_cache(maxsize=1024)
+def _parse_wildcards(pattern):
+ """splits a path pattern made of literals, ".", "[^/]+" and two or more
".*" into (char test, repeatable) steps,
+ returns None for any other pattern."""
+ if pattern.count(".*") < 2:
+ return None
+
+ steps = []
+ pos = 0
+ while pos < len(pattern):
+ m = WILDCARD_PATTERN.match(pattern, pos)
+ if not m:
+ return None
+ token = m.group()
+ if token == ".*":
+ steps.append((_any_char, True))
+ elif token == ".":
+ steps.append((_any_char, False))
+ elif len(token) > 1:
+ steps.append((_segment_char, False))
+ steps.append((_segment_char, True))
+ else:
+ steps.append((token.__eq__, False))
+ pos = m.end()
+ return tuple(steps)
+
+
+def _path_match(key1, pattern):
+ """determines whether the whole key1 matches the path pattern. A pattern
with several ".*" is matched in
+ O(len(key1) * len(pattern)), because re.match() backtracks polynomially on
it."""
+ steps = _parse_wildcards(pattern)
+ if steps is None:
+ return regex_match(key1, "^" + pattern + "$")
+
+ end = len(steps)
+
+ def add(states, i):
+ states.add(i)
+ while i < end and steps[i][1]:
+ i += 1
+ states.add(i)
+
+ states = set()
+ add(states, 0)
+ for c in key1:
+ next_states = set()
+ for i in states:
+ if i < end and steps[i][0](c):
+ add(next_states, i if steps[i][1] else i + 1)
+ if not next_states:
+ return False
+ states = next_states
+ return end in states
+
+
def key_match(key1, key2):
"""determines whether key1 matches the pattern of key2 (similar to RESTful
path), key2 can contain a *.
For example, "/foo/bar" matches "/foo/*"
@@ -72,7 +139,7 @@ def key_match2(key1, key2):
if key2 == "*":
key2 = "(.*)"
- return regex_match(key1, "^" + key2 + "$")
+ return _path_match(key1, key2)
def key_match2_func(*args):
@@ -114,7 +181,7 @@ def key_match3(key1, key2):
key2 = key2.replace("/*", "/.*")
key2 = KEY_MATCH3_PATTERN.sub(r"\g<1>[^\/]+\g<2>", key2, 0)
- return regex_match(key1, "^" + key2 + "$")
+ return _path_match(key1, key2)
def key_match3_func(*args):
@@ -213,7 +280,7 @@ def key_match5(key1: str, key2: str) -> bool:
key2 = KEY_MATCH5_PATTERN.sub(r"[^/]+", key2, 0)
- return regex_match(key1, "^" + key2 + "$")
+ return _path_match(key1, key2)
def key_match5_func(*args) -> bool:
diff --git a/tests/util/test_builtin_operators.py
b/tests/util/test_builtin_operators.py
index 984e0e4..ccdb7d5 100644
--- a/tests/util/test_builtin_operators.py
+++ b/tests/util/test_builtin_operators.py
@@ -74,6 +74,15 @@ class TestBuiltinOperators(TestCase):
self.assertFalse(util.key_match2_func("/alice/all", "/:/all"))
+ def test_key_match2_multiple_wildcards(self):
+ self.assertTrue(util.key_match2_func("/api/a/b/c/detail",
"/api/*/*/*/detail"))
+ self.assertTrue(util.key_match2_func("/api////detail",
"/api/*/*/*/detail"))
+ self.assertTrue(util.key_match2_func("/api/a/b/c/d/1/detail",
"/api/*/*/:id/detail"))
+ self.assertFalse(util.key_match2_func("/api/a/b/detail",
"/api/*/*/*/detail"))
+ self.assertFalse(util.key_match2_func("/api/a/b/c/detail/x",
"/api/*/*/*/detail"))
+ # used to take minutes because of regex backtracking
+ self.assertFalse(util.key_match2_func("/api/" + "/" * 5000,
"/api/*/*/*/detail"))
+
def test_key_get2(self):
self.assertEqual(util.key_get2("/foo", "/foo", "id"), "")
self.assertEqual(util.key_get2("/foo", "/foo*", "id"), "")
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
