Bare '-' before a rule silently makes the data document depend on rule order

Reporter: Sophontic Labs (https://sophontic.ai) / @SophonticAI

Short description

OPA accepts a bare minus immediately before a rule as an elided-left-operand binary expression. In rule-head position, the resulting minus(0, ident) head consumes the following rule. Which rule is consumed depends on the order of the surrounding rules, so two legal orderings of the same rule set produce different data documents and different readouts. Both presentations parse, check, and evaluate with rc 0.

Reproduced today with the official current release:

• OPA 1.21.0
• build commit dc6269f2c648bbbece4b76fa1fc3dbb7b61cc7b6
• darwin/arm64, Rego v1

This contradicts the documented Rego property that “The order in which statements occur does not matter.”

Steps To Reproduce

Save these two exact files.

base.rego — 115 bytes, SHA-256 9d79c2853454b90388b9f7917ea31b110226c75c82e2bfe667a07f79c326e330:

package semverisvalid-

leadingV := semver.is_valid("v1.1.12-rc1+foo")

valid := semver.is_valid("1.1.12-rc1+foo")

reversed.rego — 113 bytes, SHA-256 8670234039b82ce436d13dcc96654e78b392bbe3e64f8ff1917236dc1f344cf9:

package semverisvalid-
valid := semver.is_valid("1.1.12-rc1+foo")
leadingV := semver.is_valid("v1.1.12-rc1+foo")

Run:

$ opa parse base.rego >/dev/null; echo $?
0
$ opa check base.rego >/dev/null; echo $?
0
$ opa eval -d base.rego -f raw data.semverisvalid
{"valid":true}

$ opa parse reversed.rego >/dev/null; echo $?
0
$ opa check reversed.rego >/dev/null; echo $?
0
$ opa eval -d reversed.rego -f raw data.semverisvalid
{"leadingV":true}

The only semantic change is rule order. A consumer reading data.semverisvalid.valid receives true in the first presentation and undefined in the second, with no error on either side.

The trigger is one byte relative to OPA's own semver.is_valid example: replacing the newline immediately after the package declaration with a minus. The parser reads the minus before the first rule as 0 - ident, turns that into a compound rule head, and swallows whichever rule is first.

Expected behavior

Rule reordering should not change the parsed document. In particular, a rule head formed from an elided left operand should be rejected. Unary minus before a ref should remain valid in expression position, but the minus(0, ref) transform should not be admitted as a rule head that consumes a neighboring rule.

A focused regression test can parse the same policy in two legal rule orders and require identical documents/readouts.

Additional context

Seven measured facets of the same parser defect

1. Dangling-fragment entry. An early-closed string leaving 2006- merges with the next line's identifier into a compound minus-expression rule head. On 1.21.0 the base presentation returns [] for data.time_format.xzz10561; the reversed presentation returns ["zffe42"]. Both evaluate rc 0.
2. Readout facet. In the swallowed presentation, xzz10561 is undefined even though its declared value expression, "zffe42", is still present in the accepted source. The parsed document no longer contains the rule the source appears to declare.
3. Import/delegation propagation. A main policy that imports data.delegate.xzz10561 reads undefined from one ordering of the delegate and zffe42 from the other. Reordering only the delegate changes every importer's answer.
4. One-byte loud entry. On a time_format policy, the same single minus byte yields an order-dependent compile result: one order exits 2 with “var ts is unsafe”; the other exits 0 with {"ts":"1985-10-27"}. This is the loud calibration of the same grammar path.
5. One-byte silent entry. The semver witness above is silent at distance one: both orders parse/check/evaluate rc 0, but the document flips between {"valid":true} and {"leadingV":true}.
6. Two-edit loud-to-silent transition. On the time_format seed, inserting the minus and applying one block copy gives a silent pair: {"rts":"1985-10-27"} versus {"ts":"1985-10-27"}, rc 0 on both sides.
7. Corpus blast radius. An insert-anchored two-edit sweep over the shipped-policy corpus produced 42,351 CLI-confirmed silent flips. They were shape-concentrated: p10 had 35,398 / 1,090,512 (about 1 in 31), p08 had 6,952 / 6,158,217, p11 had 1 / 905,463, and thirteen other measured shapes were clean.

Additional exact representatives:

Dangling-fragment pair (211 bytes each):

package time_format
xzz6026 := "zf3f24"
zzx19206 := "zf3316"
result := time.parse_ns("2006-01-02", ts)
ts := "1985-10-27"
xzz3835 := "zf533a"
xzz47605 := "zfdf88"
xzz1025 := "arse_ns("2006-
xzz10561 := "zffe42"

Reordered:

package time_format
xzz10561 := "zffe42"
xzz1025 := "arse_ns("2006-
xzz47605 := "zfdf88"
xzz3835 := "zf533a"
ts := "1985-10-27"
result := time.parse_ns("2006-01-02", ts)
zzx19206 := "zf3316"
xzz6026 := "zf3f24"

SHA-256: 3b4931aa2b7556f61484fd256f98f19186c8cd64913f480f15a66f6866917ed5 and efda47cc3ac9520d908e29056c23779e21e030d90621cb47b51e18eab1f553d0.

Two-edit silent pair:

package time_format-

ts := "1985-10-27"
rts := "1985-10-27"e_ns("2006-01-02", ts)

package time_format-
rts := "1985-10-27"e_ns("2006-01-02", ts)
ts := "1985-10-27"

These are 83 and 82 bytes, SHA-256 0f02ca682037d7e83108175cd592b436af1731d6c549172b45b1d376e814559c and b5b6e1a48161d37480fe79143f0032626581d5aca45e67c704c59d7e5716928d. On 1.21.0 they evaluate to {"rts":"1985-10-27"} and {"ts":"1985-10-27"}, respectively.

Regression window and prior art

A version ladder found that v0.38.1, v0.50.0, v0.70.0, v1.0.0, v1.4.2, v1.10.0, and v1.15.0 reject the elision entry with the same parse-error signature. v1.16.0 admits it, and the behavior persists through v1.17.0, v1.20.2, and the current v1.21.0.

That boundary aligns with #8551, which fixed #5014. The PR describes changing parseTerm so that unary minus before a ref is transformed into minus(0, ref). The behavior reported here is the rule-head side effect of that grammar path; #5014 did not report the elided rule-head admission or the presentation-order document flip.

Production relevance and scope

A unit test that asserts the final affected data path catches every witness above. The risk is where order invariance itself is not asserted: a cosmetic refactor, merge, formatter/code-generation pass, or bundle regeneration can reorder rules and silently change the parsed document. The import witness shows that the changed text can be in a delegate without touching the consuming policy. The version window also means policy text rejected on v1.15.0 is silently admitted with different semantics after an upgrade to v1.16.0 or later.

This is a correctness report. It does not claim exploitability beyond the measured document/readout channel; a composed allow-gate check in our test set was clean.

Suggested fix

Reject a rule head whose parse consumed an elided left operand, and reject the dangling-fragment merge that forms binary-expression rule heads. The pre-v1.16.0 parser already rejected this entry while the intended #5014/#8551 expression-position behavior can remain supported.