Children() rebuilds and sorts a slice from the children map on every
call; Depth() was calling it twice (once for the length check, once
for the cap hint) for no benefit since only the count is used.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This commit fixes an issue where `plan` and `wasm` bundle build
targets could produce different output bytes across separate
invocations of `opa build` for the same inputs.
There were two underlying causes, both from Golang random map
iteration order leaking through to the order-sensitive planner.
Causes:
- `compilePlan` (`v1/compile`) and `planQuery` (`v1/rego`) iterated over the
compiler's module map without sorting keys first. This caused the
planner to have iteration-dependent variations in output. This was
fixed by sorting the module names before use.
- `planRules` (`internal/planner`) sorted rules by length of the rule
name ref, which is not a unique value. Because the sorting of the
rules was using an unstable sorting algorithm, and the rule names
were coming from iterating over a `map` type in the rule trie, this
had edge cases where non-deterministic output ordering could creep
in. This was fixed by adding a ref `Compare` call as a tie-breaker
to get a stable sorting order, regardless of iteration order in the
rule trie.
This commit also adds regression tests that assert plan output is
independent of module and rule ordering. The two fixes are needed
together because both sets of issues hit the planner from different
angles, and are mostly independent of each other.
Signed-off-by: Philip Conrad <philip_conrad@apple.com>
Expanding the Rego syntax to support not-bodies (not blocks?): `not {...}`
For a not block to successfully evaluate, its body must not successfully evaluate. If evaluation causes iteration, all evaluation paths must fail.
Fixes: #8402
Signed-off-by: Johan Fylling <johan.dev@fylling.se>
Also:
- Add `(*TemplateString).Equal()` because why not.
- Update `x.Compare(y) == 0` to instead use `x.Equal(y)` where possible
Fixes#8158
Signed-off-by: Anders Eknert <anders.eknert@apple.com>
This change still follows the approach thought up in #6996, but now does
it more consistently: the extra args accumulated through (multiple)
with-replacements using variables are now put into the funcstackj, and
consistently affect the planning of functions in "higher" gens.
Fixes#5311.
Signed-off-by: Stephan Renatus <stephan@styra.com>
When planning rules like these:
```
package authz
p.allow[action][resource] if { action := "list"; resource := "fruit" }
p.unrelated.eat.veggies if true
resp := p[input.rule][input.action][input.resource]
```
we ended up with a broken CallDynamic statement. Since the first ref
rule is planned as `g0.data.authz.p.allow` and builds an object return
value, and the second rule is planned as
`g0.data.authz.p.unrelated.eat.veggies` with a boolean return value, we cannot
dynamically dispatch their calls.
With this change, the previously existing "unbalanced ruletrie" check now
also hits before reaching the end of the ref. It'll catch this situation
and avoid optimizing the dispatch. We'll end up with a longer, less
efficient, but correct plan.
Signed-off-by: Stephan Renatus <stephan@styra.com>
The previous check there was running into false positives, as the added
test case showed. We should only count relevant ruletrie child nodes.
Signed-off-by: Stephan Renatus <stephan@styra.com>
Brace yourselves! For there are many touched files here. No changes
in semantics however.
Spent a long time trying out the various optional rules gocritic
provides, and settled for a few of them. There are more I really
like, but that would take many hours to address across the codebase.
Perhaps others find gocritic too pedantic? If so, we can merge the
fixes without enabling the rule.
Signed-off-by: Anders Eknert <anders@styra.com>
And update code to conform to the rule.
- Replace unnecessary fmt.Sprintf with string concatenation
- Replace fmt.Sprint with more efficient strconv.Itoa
- Replace static fmt.Errorf calls with more efficient errors.New
Thanks @srenatus for pushing me down this rabbit hole!
Signed-off-by: Anders Eknert <anders@styra.com>
And a few other small fixes in tests. This i not so much
about performance but about choosing the best tool for a
given task :) But that the alternatives are also faster
doesn't hurt either.
Signed-off-by: Anders Eknert <anders@styra.com>
Having worked on performance improvements in OPA on the side for almost
a month now, there's a lot of code piling up 😅 So much that a single PR
would be way too much to review. Instead, I'm splitting the work into
chunks, and will submit the next PR as soon as this one is merged. Using
the same benchmark as before — Regal linting itself, these new changes
in total reduce the number of allocations by ~13 million, and quite a
substantial amount of evaluation time saved as well.
This first PR is isolated to improvements to terms, values and
built-ins, and saves ~3M allocations. The details can be found below for
each change, and of course in the code :)
**BenchmarkRegalLintingItself-10 Before**
```
1885978209 ns/op 3497157312 B/op 69064779 allocs/op
```
**BenchmarkRegalLintingItself-10 After**
```
1796255084 ns/op 3452379408 B/op 66126623 allocs/op
```
**Terms**
- Use pointer receivers consistently for object and set types. This allows
changing the sortGuard once lock from a pointer to a non-pointer type, which
is really the biggest win performance-wise in this PR.
- Comparisons happen all the time, so make sure these take the shortest path
possible whenever, possible, such as when one type is compared to another
value of the same type.
Built-in functions:
**Arrays**
- Both `array.concat` and `array.slice` will now return the operand on operations
where the result isn't different from the input operand (like when concatenating
an empty array) instead of allocating a new term/value.
**Strings**
- Return operand on unchanged result rather than allocating new term/value.
- Where applicable, have functions take a cheaper path when string is ASCII
and we can avoid the cost of rune conversion.
**Crypto**
- Hashing functions now optimized, spending less than half the time compared to
previously.
**Objects**
- Avoid heap allocating result boolean escaping its scope, and instead use the
return value of the `Until` function.
**HTTP**
- Use interned terms for keys in configuration object, avoding allocating these
each time `http.send` is invoked.
**Globs**
- Use read/write lock to avoid contention. Use package level vars for "constant"
values, avoiding them to escape to the heap each invocation.
**Not directly/only related to built-in functions**
- Add `ValueName` function replacing the previous `TypeName` functions for
getting the name of Value's without paying for `any` interface allocations.
- Add a few more interned terms.
Signed-off-by: Anders Eknert <anders@styra.com>
**main**
```
BenchmarkLintAllEnabled-10 1 2640715625 ns/op 6385110200 B/op 116296633 allocs/op
```
**pr**
```
BenchmarkLintAllEnabled-10 1 2597179708 ns/op 6183614112 B/op 108421141 allocs/op
```
(I renamed the benchmark, but this is the same as "regal linting itself"
used in the past)
Another 8 million allocations cut off from `regal lint bundle`,
and a whopping 10% improvements to wall clock time!
The most significant improvement is the Equal implementation for
refs, since that is called all over the place. But there are many
other fixes here, and they all contribute something substantial
(and fixes that only have had marginal impact have been left out).
Signed-off-by: Anders Eknert <anders@styra.com>
Fixing an issue where a non-collection `every`-domain didn’t fail evaluation.
Removing a possible attack surface, where an attacker with the ability to craft portions of the input document could replace a value with an expected collection type, that is known to be processed by an `every`-statement, with a non-collection value and thereby would cause the policy to accept a query that should otherwise be rejected.
Fixes: #6762
Signed-off-by: Johan Fylling <johan.dev@fylling.se>
This way the object insert operations can return a new object instance.
Before, the object construction for a rule like
p[a][b] := ...
would look like this:
*ir.BlockStmt BlockStmt (1 blocks)
*ir.Block Block (3 statements)
*ir.BlockStmt BlockStmt (1 blocks)
*ir.Block Block (2 statements)
*ir.DotStmt &{Source:{Value:Local<2>} Key:{Value:Local<10>} Target:Local<14>}
*ir.BreakStmt &{Index:1}
*ir.MakeObjectStmt &{Target:Local<14>}
*ir.ObjectInsertOnceStmt &{Key:{Value:Local<10>} Value:{Value:Local<14>} Object:Local<2>}
*ir.ObjectInsertOnceStmt &{Key:{Value:Local<11>} Value:{Value:Local<13>} Object:Local<14>}
Now, it'll look like
*ir.BlockStmt BlockStmt (1 blocks)
*ir.Block Block (2 statements)
*ir.BlockStmt BlockStmt (1 blocks)
*ir.Block Block (2 statements)
*ir.DotStmt &{Source:{Value:Local<2>} Key:{Value:Local<10>} Target:Local<14>}
*ir.BreakStmt &{Index:1}
*ir.MakeObjectStmt &{Target:Local<14>}
*ir.ObjectInsertOnceStmt &{Key:{Value:Local<11>} Value:{Value:Local<13>} Object:Local<14>}
*ir.ObjectInsertStmt &{Key:{Value:Local<10>} Value:{Value:Local<14>} Object:Local<2>}
so the object in Local<14> is built first, and the added to object Local<2>.
Signed-off-by: Stephan Renatus <stephan@styra.com>
Co-authored-by: Teemu Koponen <koponen@styra.com>
Basically lifting this compiler optiimization for the Wasm compiler into the planning stage: If we already know at plan time that a certain (in)equality check fails/succeeds, we don't need to do it. The less work, the better.
* planner: don't emit `NotEqualStmt{A: ..., B: false}` where superfluous
* planner: don't emit `EqualStmt{A: x, B: x}`
for string and bool constants
* compiler/wasm: remove optimizations
Signed-off-by: Stephan Renatus <stephan@styra.com>
So the check introduced before was too broad: it aborted optimizations
at the wrong spot -- the resulting plan didn't add up: path lengths used
in CallDynamicStmt didn't match path lengths that the planned funcs
had.
So, while this change looks like over-fitting (also to me), we're really
trying to make test previous fix more specific.
Generally looking at that section of the planner, it feels like the intro
of general refs would be a good moment to nuke and start over: the way
that refs-with-vars are put into the ruletrie seems like the root cause of
our trouble here.
Fixes#5964.
Signed-off-by: Stephan Renatus <stephan@styra.com>
With the introduction of ref heads in #4660, the planned IR
still mostly worked, but it was bypassing the CallDynamic
optimization when it shouldn't have.
This commit re-works some of the rule planning to more robustly
handle ref heads.
Also adds a few test cases to get a grip on what should and
should not happen.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Before, this was OK:
test_a {
. mock_f := true
allow with f as mock_f
}
but this had panicked:
mock_f := true
test_a {
allow with f as mock_f
}
Which, from a user perspective, is quite incomprehensible. Technically,
the first snippet was a (supported) replacement-by-value, and the second
was an unsupported replacement by a rule that was not a function.
Furthermore, the second case wasn't properly caught in the 'with' validations.
Now, we'll capture the situation, and start supporting it. Both snippets will
now work the same, as one would expect from the language surface.
Fixes#5299.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Previously, the planner didn't account for the variable to become known in the
process of planning term b.
In the case here, foo became known when planning the ref `input.foos[foo]`, the
rhs of the `foo = input.foos[foo]` unification.
Fixes#5271.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
The compiler ensures that all the keys we see there are scalars. For strings,
nothing changes -- they're handled just like before -- but this now also allows
numbers and booleans.
An example policy that exploded with a panic before is
package p
a[0] = true
when querying the full extent of `data.p` or `data.p.a`.
Fixes#5252.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This change allows rules to have string prefixes in their heads -- we've
come to call them "ref heads".
String prefixes means that where before, you had
package a.b.c
allow = true
you can now have
package a
b.c.allow = true
This allows for more concise policies, and different ways to structure
larger rule corpuses.
Backwards-compatibility:
- There are code paths that accept ast.Module structs that don't necessarily
come from the parser -- so we're backfilling the rule's Head.Reference
field from the Name when it's not present.
This is exposed through (Head).Ref() which always returns a Ref.
This also affects the `opa parse` "pretty" output:
With x.rego as
package x
import future.keywords
a.b.c.d if true
e[x] if true
we get
$ opa parse x rego
module
package
ref
data
"x"
import
ref
future
"keywords"
rule
head
ref
a
"b"
"c"
"d"
true
body
expr index=0
true
rule
head
ref
e
x
true
body
expr index=0
true
Note that
Name: e
Key: x
becomes
Reference: e[x]
in the output above (since that's how we're parsing it, back-compat edge cases aside)
- One special case for backcompat is `p[x] { ... }`:
rule | ref | key | value | name
------------------------+-------+-----+-------+-----
p[x] { ... } | p | x | nil | "p"
p contains x if { ... } | p | x | nil | "p"
p[x] if { ... } | p[x] | nil | true | ""
For interpreting a rule, we now have the following procedure:
1. if it has a Key, it's a multi-value rule; and its Ref defines the set:
Head{Key: x, Ref: p} ~> p is a set
^-- we'd get this from `p contains x if true`
or `p[x] { true }` (back compat)
2. if it has a Value, it's a single-value rule; its Ref may contain vars:
Head{Ref: p.q.r[s], Value: 12} ~> body determines s, `p.q.r.[s]` is 12
^-- we'd get this from `p.q.r[s] = 12 { s := "whatever" }`
Head{Key: x, Ref: p[x], Value: 3} ~> `p[x]` has value 3, `x` is determined
by the rule body
^-- we'd get this from `p[x] = 3 if x := 2`
or `p[x] = 3 { x := 2 }` (back compat)
Here, the Key isn't used, it's present for backwards compatibility: for ref-
less rule heads, `p[x] = 3` used to be a partial object: key x, value 3,
name "p"
- The destinction between complete rules and partial object rules disappears.
They're both single-value rules now.
- We're now outputting the refs of the rules completely in error messages, as
it's hard to make sense of "rule r" when there's rule r in package a.b.c and
rule b.c.r in package a.
Restrictions/next steps:
- Support for ref head rules in the REPL is pretty poor so far. Anything that
works does so rather accidentally. You should be able to work with policies
that contain ref heads, but you cannot interactively define them.
This is because before, we'd looked at REPL input like
p.foo.bar = true
and noticed that it cannot be a rule, so it's got to be a query. This is no
longer the case with ref heads.
- Currently vars in Refs are only allowed in the last position. This is expected
to change in the future.
- Also, for multi-value rules, we can not have a var at all -- so the following
isn't supported yet:
p.q.r[s] contains t if { ... }
-----
Most of the work happens when the RuleTree is derived from the ModuleTree -- in
the RuleTree, it doesn't matter if a rule was `p` in `package a.b.c` or `b.c.p`
in `package a`.
As such, the planner and wasm compiler hasn't seen that many adaptations:
- We're putting rules into the ruletree _including_ the var parts, so
p.q.a = 1
p.q.[x] = 2 { x := "b" }
end up in two different leaves:
p
`-> q
`-> a = 1
`-> [x] = 2`
- When planing a ref, we're checking if a rule tree node's children have
var keys, and plan "one level higher" accordingly:
Both sets of rules, p.q.a and p.q[x] will be planned into one function
(same as before); and accordingly return an object {"a": 1, "b": 2}
- When we don't have vars in the last ref part, we'll end up planning
the rules separately. This will have an effect on the IR.
p.q = 1
p.r = 2
Before, these would have been one function; now, it's two. As a result,
in Wasm, some "object insertion" conflicts can become "var assignment
conflicts", but that's in line with the now-new view of "multi-value"
and "single-value" rules, not partial {set/obj} vs complete.
* planner: only check ref.GroundPrefix() for optimizations
In a previous commit, we've only mapped
p.q.r[7]
as p.q.r; and as such, also need to lookup the ref
p.q.r[__local0__]
via p.q.r
(I think. Full disclosure: there might be edge cases here that are unaccounted
for, but right now, I'm aiming for making the existing tests green...)
New compiler stage:
In the compiler, we're having a new early rewriting step to ensure that the
RuleTree's keys are comparible. They're ast.Value, but some of them cause us
grief:
- ast.Object cannot be compared structurally; so
_, ok := map[ast.Value]bool{ast.NewObject([2]*ast.Term{ast.StringTerm("foo"), ast.StringTerm("bar")}): true}[ast.NewObject([2]*ast.Term{ast.StringTerm("foo"), ast.StringTerm("bar")})]
`ok` will never be true here.
- ast.Ref is a slice type, not hashable, so adding that to the RuleTree would
cause a runtime panic:
p[y.z] { y := input }
is now rewritten to
p[__local0__] { y := input; __local0__ := y.z }
This required moving the InitLocalVarGen stage up the chain, but as it's still
below ResolveRefs, we should be OK.
As a consequence, we've had to adapt `oracle` to cope with that rewriting:
1. The compiler rewrites rule head refs early because the rule tree expects
only simple vars, no refs, in rule head refs. So `p[x.y]` becomes
`p[local] { local = x.y }`
2. The oracle circles in on the node it's finding the definition for based
on source location, and the logic for doing that depends on unaltered
modules.
So here, (2.) is relaxed: the logic for building the lookup node stack can
now cope with generated statements that have been appended to the rule bodies.
There is a peculiarity about ref rules and extents:
See the added tests: having a ref rule implies that we get an empty object
in the full extent:
package p
foo.bar if false
makes the extent of data.p: {"foo": {}}
This is somewhat odd, but also follows from the behaviour we have right now
with empty modules:
package p.foo
bar if false
this also gives data.p the extent {"foo": {}}.
This could be worked around by recording, in the rule tree, when a node was
added because it's an intermediary with no values, but only children.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This has been semi-public anyways: people depend on the JSON structure to be
kept as-is.
So we might as well make the structs public, and make working with this easier
from golang. No need to copy the struct definitions manually.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Before, we'd only plan a single rule functions when a function used
in that rule's body was mocked, instead of planning one rule function
for the mocked, and one for the un-mocked function.
This only affects uses where both the mocked and the un-mocked version
of the rule are queried, like
p {
q with time.now_ns as 1 # (1)
not q # (2)
}
Now, we plan g1.data.pkg.q for (1), and g0.data.pkg.q for (2), where
g1's plan uses the mocked function result, and g0's plan uses the
builtin.
Fixes#4746.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.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>
Before, we had been planing `every x in xs { BODY }` as, roughly,
NOT
SCAN xs
NOT
BODY
This poses a problem: scans never fail -- they iterate _their_
bodies, and break out of their block when they are done iterating.
As far as the NOT is concerned, it always looks like the SCAN was
successful.
We had worked around that for the "outer" SCAN by breaking out of
the NOT's block at the end. However, the same trick can't be used
when BODY contains another SCAN, since we can't tell beforehand how
deeply we're nested, and doesn't know how far to break out again.
So in this commit, we replace the NOTs by some custom "condition
var" construct that works similar to how NOT gets compiled, but
sets the "inner" condition variable when the BODY's plan succeeds.
Likewise, the "outer" condition variable is tied to that result.
We're practically using the condition variables to encode
every x, y in xs { p(x,y) }
~> p(x1, y1) AND p(x2, y2) AND ... AND p(xn, yn)
~> NOT (NOT p(x1, y1) OR NOT p(x2, y2) OR ... OR NOT p(xn, yn))
The conditon variables are now implemented in the IR. (When using
ir.NotStmt, they are an artifact of compiling the IR to wasm.) This
is achieved by resetting a new local, and assigning it a dummy value
(true) to signal the condition was met.
----
This path was taken because I could not come up with a way to deal
with the "inner SCAN" situation just by using NOT blocks. The "outer"
NOT/SCAN could perhaps be salvaged, but I found it easier to reason
about one mechanism applied twice than to mix and match.
Another abandoned path was using ir.ReturnLocalStmt in the query's
plan iterator: while it worked well for simple cases, the problems
considered were that we might do the wrong thing in nested sitations,
like comprehensions. Also, it's not something we'd done in any other
place.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Due to excessive nesting of blocks, the break statement wasn't breaking
out of enough of them: this would this add an element to the result set
when it should have turned into undefined.
This was the case in two conditions:
a. the dynamic lookup not finding a data function to call, and the resulting
static data lookup failing to resolve the ref; or
b. the dynamically called function returns undefined
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This commit adds support for serializing/deserializing plans into/from
JSON. This allows us to compile policies out into JSON so that they
can be transpiled or interpreted in other environments.
To support these changes we have implemented custom marshaling on the
Block type and Operand (previously called LocalOrConst) type.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
All data refs, and all dots after input, are covered, but naked input
refs could go unnoticed: their undefined state, undetected, would have
funny consequences in other places.
Fixes#3891.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
This commit plumbs the print hook through to the wasm runtime so that
print calls are enabled when the wasm target is on. This commit also
updates the planner and compiler to support calls to void
functions--previously, the planner and wasm backend assumed that
functions returned values so they would perform checks for defined
values, however, with void functions, those checks must be suppressed.
Signed-off-by: Torin Sandall <torinsandall@gmail.com>
golint is deprecated. The author of the code no longer supports the
codebase. golangci-lint is faster than golint, and is in use by other
opa repositories (e.g. Gatekeeper).
This commit changes tools.go to reference golangci (so it ends up in
vendor) and modifies check-lint to use golangci instead.
Breaking API Changes:
- plugins/rest/rest.go: Fix typo "AllowInsureTLS" -> "AllowInsecureTLS"
- storage/errors.go: Removed unused IndexingNotSupportedErr
Signed-off-by: Will Beason <willbeason@google.com>
* wasm-e2e: fix test runner, adapt and include jsonpatch tests
The `sort_bindings` key now is interpreted a little differently now: it's
no longer sorting and comparing, but building two sets and compares them.
From the test author's perspective, nothing has changed, except that it
now actually compares them.
Fixes#2949.
* exported tests: don't sort test expectations
This leads to very weird situations, and seems to only be a convenience
for the test authors. So, instead, we'll have the test authors pin down
whatever the sorted bindings are, and assert that the sorted bindings of
the returned result set match.
* wasm: fix regex.find_all_string_submatch_n with n != -1
Fixes#3352.
* wasm: unify objects that contain vars
Unification only happens by the reused existing code path, but we still
have to assert equality of the rest.
Fixes#3351.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
If there is no data function for the vars (known at runtime), we'll have
to consult `data`. Before, this was ignored.
Fixes#3305.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
Stephan Renatus