Lost in iteration: values lost when iterating ref head rules mixing static and dynamic paths

[anderseknert]

I encountered this issue when working on Regal (see issue for more details) earlier this summer, but since I was never able to reproduce it in OPA I figured it must be some special circumstance related to that project. Having now spent more time than I'd like to admit trying to narrow it down, I've finally been able to isolate the issue and reproduce it on OPA.

A nonsensical example, but it demonstrates the bug in the most compact form I could come up with. When mixing static and dynamic paths in a ref head rule, one type of iteration over the values can cause further iteration to not see all values.

package p

import rego.v1

obj.sub[x][x] contains x if some x in ["one", "two"]

obj[x][x] contains x if x := "whatever"

main contains x if {
    #[1 | obj.sub[_].one[_]]
    x := obj.sub[_][_][_]
}

At this point, evaluating main produces the expected result:

opa eval -f pretty -d policy.rego data.p.main
[
  "one",
  "two"
]

Uncommenting the first line in the main rule (iteration wrapped in a comprehension which shouldn't matter) however changes the result of evaluation:

opa eval -f pretty -d policy.rego data.p.main
[
  "one"
]

It seems that just the fact that we did obj.sub[_].one[_] once got the evaluator into a state where traversing the full object no longer returns all values.

[johanfylling]

After a bit of investigating, I can confirm this is a virtual-cache issue. There are certain scenarios where the ref of a rule node is unified before the associated rules are evaluated, causing ref variables to be pre-defined, but the result is stored in the virtual cache under a key that ends "left" of all relevant ref components.
E.g. the ref to p.obj.sub[_].one[_] has the 2nd ref var unified to "one", which scopes eval of the rule(s); but the result is stored under the key p.obj.sub.

[anderseknert]

Great work on this @johanfylling! 👏