compile: recursion check fails on non-recursive ref

[anderseknert]

This compiles:

package p

rule if {
    some root in ["foo", "bar"]
    data[root].sub
}

Whereas this doesn't:

package p

rule if {
    some root in ["foo", "bar"]
    data[root].rule
}

->

rego_recursion_error: rule data.p.rule is recursive: data.p.rule -> data.p.rule

Which we know is wrong since none of the values root resolves will produce the recursive data.p.rule ref that the error message claims. Without having looked at the code, I assume that root is considered dynamic, even though all possible values are known and could be checked at compile time. I don't think this check would need to cover all possible cases, but it should be able to identify at least simple cases like this where the variable part of a ref is just an enumeration of values known at compile time, and even local in scope. The use case is if course (not so dynamic) policy composition, where we want to run an input across a number of roots we know exist.

[srenatus]

Without having looked at the code, I assume that root is considered dynamic, even though all possible values are known and could be checked at compile time.

Yup this would be trivial in the evaluator, but the compiler doesn't know any of the potential values. It only looks at the expression

data[__local1__].rule

and doesn't know if it's preceded by your example or something like

__local1__ = input.oracle
data[__local1__].rule

I don't think this is a bug. It's behaving as expected, overly cautious 😅

It's really hard to strike a good balance here, static analysis vs dynamic analysis. Your example seems obvious but wouldn't someone then also expect this to pass?

p if {
  every x in {"foo", "bar"} { func(x, "api") }
}

func(x, y) if {
  data[x][y].allow
  not data[x][y].deny
}

This only affects the first part, right? If we do the standard potential recursion break-up twist of introducing a prefix, we'd be good?

[anderseknert]

the compiler doesn't know any of the potential values

Add a static prefix and it suddenly knows exactly what kind of values you handed it. This is a recursion error:

rule if data[["foo", "bar"][_] + 1].rule

While this is a type checker error:

rule if data.prefix[["foo", "bar"][_] + 1].rule

The step from "the compiler knows this is a string" to "the compiler knows the value of the string" when possible (like when pointing to a local constant value) seems like a small one to a layman like myself :)

While I understand it's not that simple, it's quite hard to grasp why this is fine:

rule if {
	data["foo"].rule
}

While this isn't.

rule if {
	foo := "foo"
	data[foo].rule
}

That is likely not what most would expect, and hence why I think of this as a bug. I don't mind having this categorized as a feature request instead though.

The compiler could even rewrite the latter to the former if it was able to identify foo as replaceable by its value (i.e. a constant). Reminds me a little about what we talked about with regard to optimizing how template strings get rewritten, and making the compiler aware of cases where this isn't needed for safety.

[johanfylling]

This seems related, but there might be some added nuance with the rule head ref.

[anderseknert]

@johanfylling most likely yes! I'm fine with merging the issues. Although it'll be more satisfying for anyone working on this to close two issues in one PR :P