topdown/copypropagation: keep refs into livevars #4936
Conversation
srenatus
force-pushed
the
sr/topdown/copyprop-with-tautologies
branch
4 times, most recently
from
2ce4f1d
to
cb8e7f3
Compare
| @@ -2147,9 +2147,10 @@ func (r *Rego) partial(ctx context.Context, ectx *EvalContext) (*PartialQueries, | |||
|
|
|||
| var unknowns []*ast.Term | |||
|
|
|||
| if ectx.parsedUnknowns != nil { | |||
| switch { | |||
There was a problem hiding this comment.
style preference: I like condition-less switch statements.
| @@ -282,12 +295,16 @@ func (t bindingPlugTransform) plugBindingsRef(pctx *plugContext, v ast.Ref) ast. | |||
| // updateBindings returns false if the expression can be killed. If the | |||
| // expression is killed, the binding list is updated to map a var to value. | |||
| func (p *CopyPropagator) updateBindings(pctx *plugContext, expr *ast.Expr) bool { | |||
| if pctx.negated || len(expr.With) > 0 { | |||
| switch { | |||
| a, b := expr.Operand(0), expr.Operand(1) | ||
| if a.Equal(b) { | ||
| if p.livevarRef(a) { |
There was a problem hiding this comment.
⚡ This is the new thing: they might be equal, but they can still be relevant!
| @@ -374,7 +406,7 @@ func sortbindings(bindings *ast.ValueMap) []*binding { | |||
| return false | |||
| }) | |||
| sort.Slice(sorted, func(i, j int) bool { | |||
| return sorted[i].k.Compare(sorted[j].k) < 0 | |||
| return sorted[i].k.Compare(sorted[j].k) > 0 | |||
There was a problem hiding this comment.
🔍 changing the ordering here let's us avoid adding __local0__ = input to the body when we already have __localcp0__ = input.a.
| @@ -397,17 +429,21 @@ func makeDisjointSets(livevars ast.VarSet, query ast.Body) (*unionFind, bool) { | |||
| a, b := expr.Operand(0), expr.Operand(1) | |||
| varA, ok1 := a.Value.(ast.Var) | |||
| varB, ok2 := b.Value.(ast.Var) | |||
| if ok1 && ok2 { | |||
|
|
|||
| switch { | |||
| case ast.Ref: | ||
| livevars.Add(v[0].Value.(ast.Var)) | ||
| } | ||
| } |
There was a problem hiding this comment.
Before, we hadn't added input or data if they're part of the unknowns to the livevars. This felt a bit odd to me -- what if input.foo is unknown, but input.bar == input.bar is in the query to-be-copy-propagated? Turns out that's not possible -- we're only running CP after a successful PE run, as a final step. So, if we've made it to CP, and there's a tautology to check (input.x == input.x), checking its first term is good enough.
| @@ -2985,7 +3079,12 @@ func TestTopDownPartialEval(t *testing.T) { | |||
| x = true | |||
| }`, | |||
| }, | |||
| wantQueries: []string{"a1 = input.foo1; b1 = input.foo2; c1 = input.foo3; d1 = input.foo4; e1 = input.foo5"}, | |||
| wantQueries: []string{` | |||
There was a problem hiding this comment.
That's the only impact of the ordering change in our test suite. 🙃
| @@ -3054,34 +3153,6 @@ func TestTopDownPartialEval(t *testing.T) { | |||
| shallow: true, | |||
| skipPartialNamespace: true, | |||
| }, | |||
| { | |||
There was a problem hiding this comment.
I've moved these to the other block of copy-prop related tests.
| wantSupport: []string{`package partial.test | ||
| p[__local1__1] { __local0__1 = {i1 | input[i1]}; neq(and(__local0__1, set()), __local0__1); sprintf("%v", [__local0__1], __local1__1) } | ||
| `}, | ||
| }, |
There was a problem hiding this comment.
☝️ these two are just moved to keep the CP-related tests together.
srenatus
force-pushed
the
sr/topdown/copyprop-with-tautologies
branch
from
cb8e7f3
to
e7ab277
Compare
Before, a query of
input.a == input.a
would not survive copypropagation.
With this change, it'll be recorded as removedEq, and subsequent processing
steps ensure that it's kept in the body.
Changing the sort order in sortBindings allows us to limit the unnecessary
variable bindings: with the previous ordering, we'd get
__local0__1 = input; __localcp0__ = input.a
for the query `x := input; input.a == input.a`. Sorting the other way, we'll
process `__localcp0__ = input.a` first, add it to the body, and when we check
`__local0__1 = input`, we find that `input` is already contained in the body,
and is thus not needed.
Fixes open-policy-agent#4848.
Signed-off-by: Stephan Renatus <stephan.renatus@gmail.com>
srenatus
force-pushed
the
sr/topdown/copyprop-with-tautologies
branch
from
e7ab277
to
2465f34
Compare
Before, a query of
would not survive copy-propagation.
With this change, it'll be recorded as removedEq, and subsequent processing
steps ensure that it's kept in the body.`
Fixes #4848.
TODO: