IceTea233 commented on issue #1616: URL: https://github.com/apache/casbin/issues/1616#issuecomment-5236338524
I have been thinking about precompiling the matcher into a state machine recently. After investigating in I found that the matcher is backed by another package [govaluate](https://github.com/apache/casbin-govaluate/blob/master/EvaluableExpression.go). It provides great functionality to resolve and evaluate C-like expressions, which I thought to be used as the syntax of the matchers. Internally, it loads the expression string to build it into a tree, then traversal over it on evaluating. My thought is to build the traversal process into a state machine. Suppose we have a match expression that match a request against a policy, and for generality, we assume that all the expression only contains the logical operators: "AND", "NOT", "OR", the pure value: "TRUE", "FALSE". Notice that in such generalized form of expression, if we construct it into a tree, and has `m` leaves (obviously all leaves should be pure value, or more general, a function that finally output a boolean value.), then we can construct a state machine with `m` states, since we always determine whether to early-stop or proceed to examine the next value on the leaves node. Each state `S_i` check whether the leaf is a match or not, with a function `F_i(R, P)`, which is a function that check "if the request matches the policy for the i_th condition." After got the value of the state, determine either moving to the next state or early stop with a specific value. I am not able to prove the correctness but i ntuitively think that the transition can be determined by traversal overt the tree for every expression, except those with recursion, though I'm not sure if current matcher support recursion yet. If this idea make sense, we can simplify each matching from traversal over a tree to scan over an array of state with checker functions `F_i(R,P)` and transition of the state `T_i(F_i)`, which looks simpler to handle and optimize. I might start to examine this idea with some simple implementation in recent couples of weeks. -- 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]
