You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
What is the underlying problem you're trying to solve?
Hey!
At Spacelift we integrate with OPA extensively. One of the use cases is reacting to Push events and deciding whether it's interesting for the current Stack or not.
A pattern we've been seeing our users writing very commonly, is the following:
which, if both affected_files and interesting_paths are dynamic arrays, ends up being O(n^3), and is a bottleneck for many policies.
Describe the ideal solution
Add a function any_prefix_matches_any_string (name TBD) which accepts two arguments which are both arrays of strings. Then checks if any of the strings in the second argument is a prefix of any of the strings in the first argument, but does it fast.
Similarly, a any_suffix_matches_any_string (name TBD) function for suffixes.
For a test case of ours which with the naive approach takes 60ms, a draft implementation based on Patricia trees takes 0.5-1ms.
Additional Context
Very happy to contribute this.
The text was updated successfully, but these errors were encountered:
What is the underlying problem you're trying to solve?
Hey!
At Spacelift we integrate with OPA extensively. One of the use cases is reacting to Push events and deciding whether it's interesting for the current Stack or not.
A pattern we've been seeing our users writing very commonly, is the following:
which, if both
affected_files
andinteresting_paths
are dynamic arrays, ends up being O(n^3), and is a bottleneck for many policies.Describe the ideal solution
Add a function
any_prefix_matches_any_string
(name TBD) which accepts two arguments which are both arrays of strings. Then checks if any of the strings in the second argument is a prefix of any of the strings in the first argument, but does it fast.Similarly, a
any_suffix_matches_any_string
(name TBD) function for suffixes.For a test case of ours which with the naive approach takes 60ms, a draft implementation based on Patricia trees takes 0.5-1ms.
Additional Context
Very happy to contribute this.
The text was updated successfully, but these errors were encountered: