Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve rule index to support glob.match built-in #1496

Closed
tsandall opened this issue Jun 14, 2019 · 0 comments
Closed

Improve rule index to support glob.match built-in #1496

tsandall opened this issue Jun 14, 2019 · 0 comments
Assignees

Comments

@tsandall
Copy link
Member

As mentioned in #1443 it's possible to implement an IAM-like policy and use partial evaluation to get good performance as long as subject/action/resource matching is limited to equality matching. However, currently, if matching is based on glob.match or regex the performance is poor because the rule indexer is ineffective.

We can extend the rule index to support the glob.match built-in function by generalizing the trie build step in the rule index.

For example:

# equality expression understood by indexer
input.resource = ["foo", _, "bar"]

# operator: =
# operand: input.resource
# operand: ["foo", _, "bar"]
glob.match("foo:*:bar", [":"], input.resource)

# operator: glob.match [":"]
# operand: input.resource
# operand: "foo:*:bar"

The rule indexer can be extended to add edges in the trie for the pattern operand by representing the pattern string as an array (e.g., "foo:*:bar" becomes ["foo", _, "bar"])

In the initial implementation we can leave super globs out.

@tsandall tsandall self-assigned this Jun 14, 2019
tsandall added a commit to tsandall/opa that referenced this issue Jun 23, 2019
These changes update the rule index to support glob.match calls. The
changes update the build step to transform glob.match(pattern,
delimiter, match) calls into ref/value pairs like equality
expressions. In addition, the build step creates a mapper function
that transforms resolved values into lookup values during traversal.

As part of these changes, the build operation has been refactored so
that most of the process is encapsulated by a new refindices struct
that's separate from the actual rule index/trie. Hopefully this makes
the code easier to follow.

The index build step for glob.match only recognizes statements where
the match operand was given as a reference (and then was rewritten by
the earlier step in the compiler.) If this is too brittle we could
revisit the build step and close over all intermediate assignments.

Fixes open-policy-agent#1496

Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Archived in project
Development

No branches or pull requests

1 participant