All packages, except for `cmd` and `internal`, have been moved into a new `v1` root package.
Old packages are kept for backwards-compatibility reasons. All contained code is replaced with simple type aliases and proxy functions to `v1` implementations.
Old packages default to the Rego v0 syntax, new `v1` packages default to the Rego v1 syntax.
Signed-off-by: Johan Fylling <johan.dev@fylling.se>
With this change, `undefined` outcomes of complete rule evaluations
are now also cached. Previously, only defined results had been cached,
and empty partial sets/objects.
In the case of partial rules with string keys, the introduction of ref heads
changed how they had been evaluated: Before, they had been evaluated
as partial sets, and thus got cached when empty. After, they had been
evaluated as complete rules (with ref heads), and if they were undefined,
they had _not_ been cached. This caused a performance regression.
Fixes#593.
Signed-off-by: Edward Paget <edward.paget@chime.com>
Follow-up to #4540
We can now mock functions that are user-defined:
package test
f(_) = 1 {
input.x = "x"
}
p = y {
y := f(1) with f as 2
}
...following the same scoping rules as laid out for built-in mocks.
The replacement can be a value (replacing all calls), or a built-in,
or another non-built-in function.
Also addresses bugs in the previous slice:
* topdown/evalCall: account for empty rules result from indexer
* topdown/eval: capture value replacement in PE could panic
Note: in PE, we now drop 'with' for function mocks of any kind:
These are always fully replaced in the saved support modules, so
this should be OK.
When keeping them, we'd also have to either copy the existing definitions
into the support module; or create a function stub in it.
Fixes#4449.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
With this change, we can replace calls to built-in functions via `with`. The replacement
can either be a value -- which will be used as the return value for every call to the
mocked built-in -- or a reference to a non-built-in function -- when the results need
to depend on the call's arguments.
Compiler, topdown, and planner have been adapted in this change. The included
docs changes describe the replacement options further.
Fixes first part of #4449. (Missing are non-built-in functions as mock targets.)
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This commit adds a new kind of indexing to the compiler and topdown to
help avoid recomputing comprehensions. This helps with queries that
perform "group by" operations.
This optimization allows policies to perform group-by/aggregation in
O(n) instead of O(n^2). The optimization works by computing a set of
index keys for the comprehension at compile-time and then computing
the collection once at evaluation-time and indexing the result based
on the keys.
The index keys are variables in the outer query that limit the values
produced by the comprehension. In the simple group-by case these are
the object values themselves. During evaluation, topdown checks if
indexing is possible and builds the index by computing the
comprehension without creating a closure over the outer query. This
computes ALL values in the collection defined by the
comprehension. The results are keyed by the assignments to the
variables indicated in the comprehension index. This way the
comprehension does not have to be recomputed for each set of
assignments in the outer query.
The index is exposed on both the compiler and the query compiler so
that ad-hoc queries can benefit from the indexing as well. This is
important for things like the playground where users may select a rule
body and run it. If that exhibited n^2 behaviour it would be quite
confusing.
In order to be indexed, the comprehension must meet a few
conditions. Importantly, the indexing should not worsen overall
performance. To ensure this, comprehensions containing refs or walk()
calls that include output vars that close over the outer query are not
indexed. This means that if the caller were pushing down assignments
to those vars, OPA will not compute the entire collection.
In the future we can improve the index to cover more kinds of
comprehensions. One improvement that would be particularly nice would
be to allow the comprehension index to close over specific local
variables in the parent scope. This would let us build the index in
more cases--however, the analysis would need to be careful to take
into account the count of closure variables. Variables with multiple
assignments would be poor candidates.
Benchmark results (before, O(n^2) runtime):
BenchmarkComprehensionIndexing/10-16 13831 85821 ns/op
BenchmarkComprehensionIndexing/100-16 208 5662625 ns/op
BenchmarkComprehensionIndexing/1000-16 2 549295038 ns/op
Benchmark results (after, O(n) runtime):
BenchmarkComprehensionIndexing/10-16 35809 33369 ns/op
BenchmarkComprehensionIndexing/100-16 3756 274546 ns/op
BenchmarkComprehensionIndexing/1000-16 438 2725152 ns/op
Fixes#2276
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Previously the virtual cache was implemented using a
map[ast.Value]... which works for scalar key terms but not composites
(because they're not comparable.) This change updates the virtual
cache to use a util.HashMap that supports all term kinds. This
prevents the virtual cache lookup/insert from panicing when a key like
data.x.y[[1]] is received.
In addition to fixing the virtual cache, this change updates the
Term.Equal() function to include an early-exit for types that do not
allocate in their Equal() functions.
The early-exit was added because swapping out the map[ast.Value]...
for util.HashMap introduced allocations into the virtual cache
lookup/insert operations which doubled the benchmark latency. See
below for benchmark results before/after this commit.
```
BEFORE
======
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8 5000000 284 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/open-policy-agent/opa/topdown 1.731s
Success: Benchmarks passed.
AFTER
=====
goos: linux
goarch: amd64
pkg: github.com/open-policy-agent/opa/topdown
BenchmarkVirtualCache-8 5000000 322 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/open-policy-agent/opa/topdown 1.969s
Success: Benchmarks passed.
```
This change will also let us memoize virtual sets using the same cache
(see #822).
Fixes#1197
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Now that the base cache is not used for the with keyword
implementation, the code we added specifically for that can be
removed.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
This is a follow-on to the previous commit. Note, with this change,
input and data replacement are handled using the same code (whereas
before the data replacement used the baseCache which could lead to
slightly different behaviour). The only difference is that the data
replacement has to keep track of prefixes so that base/virtual
documents can be shadowed.
Also, rename helper that merges with values into term to indicate purpose.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
These changes make it possible to replace the data document.
Both base and virtual documents can be replaced. These changes support
replacing rules without arguments. They do not support replacing
rules/functions with arguments. To support that, we would need to take into
account the scenarios that would arise as a result of replacing the arguments
to the rule/function and the return value of the rule/function itself.
Fixes#517
Signed-off-by: Ashutosh Narkar <anarkar4387@gmail.com>
The virtual document cache was not being invalidated. As a result, if
the same rule was evaluated twice where the first expression included a
with modifier, the result on the second evaluation may be incorrect.
Fixes#736
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
AST conversion can be expensive for large JSON values. This change adds
a cache for storage reads so that the conversion only occurs once for a
particular leaf in the data document. For example, given the following
reads:
data.foo # cache miss, storage read, cache insert
data.foo.bar # cache hit
data.baz.qux # cache miss, storage read, cache insert
data.baz # cache miss, storage read, cache remove+insert
data.baz.qux # cache hit
In the 4th case, the cache element for data.baz.qux is removed as it can
be served by the cache element for data.baz.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
These changes modify topdown evaluation to use a binding list that
namespaces variables. This allows topdown to propagate partially ground
ref operands into child query evaluation.
These changes also prepare topdown evaluation to support a partial
evaluation mode.
With these changes, evaluation is no longer performed in two steps
(i.e., first pass of evaluating individual terms, second pass of
evaluating built-in expressions.) Instead, evaluation assumes queries
have been rewritten to eagerly evaluate refs and comprehension. This
way, ref and comprehension bindings do not have to be maintained
separately: they are handled by the normal variable binding list.
This commit contains some breaking changes to the topdown APIs,
namely...
1. Truth explanation has been removed. This feature was not used and the
tracing changes broke it. We can revisit in future if necessary.
2. Data indexing has been removed. Data indexing can be re-added in
future if necessary however it should be handled outside of topdown to
avoid potential memory leaks.
3. Built-in functions produce at-most-one output now. Functions that
used to produce multiple outputs (e.g., io.jwt.decode) can produce a
composite value if they need to.
Fixes#131
Johan Fylling