Skip to content

bug: INT-054 negative-cycle error names the two predicates in a random order #410

Closed

Description

@adityamukho

Summary

The stratification error for a negative cycle does not give the same message for the same input. Running this 10 times in the REPL on main:

(rule [(p ?x) (not (q ?x))])
(rule [(q ?x) (not (p ?x))])

gave:

7× Error: [INT-054] unstratifiable: predicate 'q' is involved in a negative cycle through 'p'
3× Error: [INT-054] unstratifiable: predicate 'p' is involved in a negative cycle through 'q'

Cause

stratify() in src/query/datalog/stratification.rs (around lines 85–98) walks the dependency graph through a HashMap, and it reports the first (head, dep) pair whose stratum reaches n. Because HashMap iteration order is randomized per process, the pair it reports first changes between runs.

Why it matters

  • Users, docs and bug reports can't quote a stable message. The wiki Datalog Reference (Stratification) quotes one order, so it is wrong about 30% of the time.
  • A test that asserts on the full message text would fail at random.

Suggested fix

Iterate in a sorted order: sort the rule heads and their dependencies, or use a BTreeMap/BTreeSet for the graph walked here. Then the same input always names the same pair. Add a test that runs the same registration many times, for example in a loop, and asserts that the exact message never changes. Check the other error paths that iterate over HashMaps in the evaluator and optimizer for the same problem.

This changes only the error text, not the behavior, so it fits v2.0.2.

Found while verifying the wiki; see #383.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions