Why does OPA reject a Rego helper that calls itself to walk a base-image chain?

## Why the compiler says no Rego deliberately is not Turing-complete for policy evaluation. The compiler builds a graph of which rules and functions depend on which, and rejects the policy if that graph has a cycle — a rule that references itself, a function that calls itself, or two that reference each other. The error names the rule and says it is recursive, and it happens at load time, so the policy never reaches a decision point in that state. That restriction is a feature: a policy engine sitting in an admission path or a pipeline gate must answer in bounded time, and forbidding recursion removes the whole class of policies that might not answer at all. ### The shape that triggers it You want to know whether an image's *ancestry* terminates in a blessed base — not just its immediate parent, but the parent's parent, and so on: ``` # rejected: is_derived_from calls itself is_derived_from(img, base) if { parent := parent_of(img) is_derived_from(parent, base) } ``` This is the natural recursive formulation from any other language, and it is precisely what Rego will not compile. ### Option 1: a transitive closure built-in If you can express the ancestry as a graph — an object mapping each node to the set of nodes it points at — `graph.reachable(graph, initial)` returns the set of nodes reachable from the starting nodes, doing the walk for you without recursion in your policy: ``` ancestors := graph.reachable(input.parent_edges, {input.image.id}) deny contains msg if { count(ancestors & approved_base_ids) == 0 msg := "image ancestry does not reach an approved base" } ``` The cost is that you must supply the edge set, which brings you to the second option anyway. ### Option 2: flatten the chain before evaluation The most robust answer in an interview is usually that the walk should not happen inside the policy at all. The build system already knows what each image was built from; the image's own config carries its layer history and any inherited base-image annotations. Resolving an ancestry means following references between *different* objects, and a decision point typically hands the policy one object — so the walk belongs upstream, and the policy should receive an already-flattened list: ``` deny contains msg if { count({a | some a in input.image.ancestry} & approved_bases) == 0 msg := "image ancestry does not reach an approved base" } ``` This keeps the rule readable, keeps evaluation fast and deterministic, and moves a data-gathering problem to where the data lives. ### Option 3: unroll a bounded depth If your chain is genuinely at most two or three deep by convention — application image, team base, organisation base — you can write the two or three levels out explicitly. It is honest and it compiles. Say out loud that it is a bound you chose, and what happens at level four, because an interviewer will ask. ### The case that decides whether you thought about it What if the ancestry data is missing for an image? Then the reachable set is empty, the intersection is empty, and the rule denies — which is the fail-closed direction, and here that is the right one. But make the message distinguish "ancestry does not reach an approved base" from "no ancestry recorded", because the two need different fixes from different people: one is a base-image change, the other is a build-pipeline change. A blocked developer who cannot tell which one they hit will escalate, and rightly. ### Related shapes that also trip the check - **Mutual recursion.** `a` calls `b`, `b` calls `a`. Same cycle, same rejection. - **Recursion through the data document.** A rule whose body references its own package output — including via a `data.` path constructed to look indirect — still forms a cycle in the graph. - **A helper that references the very set it contributes to.** Referring to `deny` from inside a `deny` definition is a cycle, even though the intent is only to count the existing violations. The fix in every case is the same move: turn the iterative walk into either a built-in that does it, or data that is already flat by the time the policy sees it.