partial eval: Improve support for cases where default values are not required

[tsandall]

Currently, OPA generates support rules for all rule sets that include a default rule, regardless of whether:

1. the default value is required in the partial evaluation output
2. the rule set depends on unknown values

This issue focuses on the first problem.

For example:

Query (unknowns=[input]):

data.example.allow = true

Policy:

package example

default allow = false

allow {
  input.x = 1
}

allow {
  input.y = 2
}

In this case, the result of partial evaluation is:

Queries (1 total):

data.partial.example.allow = true

Support modules (1 total):

package partial.example

allow = true { input.x = 1 }
default allow = false

In this case, the default value is not actually required in the partial evaluation output (since true != false). OPA should avoid generating support rules in cases like this which will be common for Compile API integrations.

Related Issues: #812

[srenatus]

Where would this go? I'd be happy to give this a try, but I'm a bit lost as to where to start

[tsandall]

hey @srenatus, I've updated this issue to scope it better. I've created another issue (#823) to capture the other improvement we could make. The other issue will require a bit more groundwork.

For this issue, the observation is that the default value is not required in the partial evaluation output, i.e., the query above will be undefined when all of the non-default rules are undefined, similarly, the query will be defined if any of the non-default rules are defined.

The evaluator currently has a special case for partial evaluation of rules with a default value: https://github.com/open-policy-agent/opa/blob/master/topdown/eval.go#L1445. When the evaluator checks if the rule set has a default value, it can determine if the default value is required. In these cases, the default value is NOT required if the other term in the expression (<ref> = <term>) does not equal the default value. The other term in the expression is part of the evalVirtualComplete struct state (it's the rterm field.)

I think what needs to happen is the evaluator should plug rterm and compare the result to the default value. Something like this:

if e.ir.Default != nil {
  plugged := e.rbindings.Plug(e.rterm)
  if !ast.IsConstant(plugged) || plugged.Equal(e.ir.Default.Value) {
     return // generate support rule like we do today
  }
}

return // partially evaluate rule normally

Plugging substitues variable bindings. E.g., given the query query x=1; x=y; y=z; z>0, plugging x and y in the last expression would result in 1>0.