Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

partial eval: panic in copy propagation when ref head refers to call output transitively #912

Closed
tsandall opened this issue Aug 29, 2018 · 0 comments
Labels

Comments

@tsandall
Copy link
Member

tsandall commented Aug 29, 2018

If a ref head transitively refers to the output of a call expression and the ref head is NOT the root in the union-find structure, the copy propagator will incorrectly try to substitute the call output with the call.

The problem is that the copy propagation implementation assumes that calls cannot be used as ref heads because it's illegal to dereference calls, e.g., f(x)[0] is not syntactically valid today. If the copy propagator encounters a ref head that can be substituted, it assumes the substituted value is a ref (in which case the ref to be substituted just extends the binding value.)

When we compute the set of ref heads in a query, we must take the union-find into account. I.e., the copy propagator should replace the ref head with the union-find root before adding it to the head var set.

For example:

p {
  split(input, ":", x)
  y = x
  y[0]
}  

In this query, the union-find structure would be {x: x, y: x} and the headvar set would be {y,}. When the split expression is processed, it would be killed and x would be bound to split(input, ":"). When the last expression is processed, the implementation will first replace y with x and then try to replace x with split(input, ":") before panicing.

Note, if the second expression is reversed to x = y the panic is avoided (because y becomes the union-find root) and the result is split(input, ":", y); y[0].

@tsandall tsandall added the bug label Aug 29, 2018
tsandall added a commit to tsandall/opa that referenced this issue Aug 29, 2018
The copy propagator was not taking the union-find subsitutions into
account when building the headvar set. As a result, bindings were being
added for call expressions when the var would later be substituted for a
ref head (which ultimately would cause a panic when the ref head was
substituted for the call).

These changes update the copy propagator to add the union-find root to
the headvar set instead of the headvar. This way the headvar
construction is consistent with the binding plug and update below.

Fixes open-policy-agent#912

Signed-off-by: Torin Sandall <torinsandall@gmail.com>
tsandall added a commit that referenced this issue Aug 29, 2018
The copy propagator was not taking the union-find subsitutions into
account when building the headvar set. As a result, bindings were being
added for call expressions when the var would later be substituted for a
ref head (which ultimately would cause a panic when the ref head was
substituted for the call).

These changes update the copy propagator to add the union-find root to
the headvar set instead of the headvar. This way the headvar
construction is consistent with the binding plug and update below.

Fixes #912

Signed-off-by: Torin Sandall <torinsandall@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant