Repository navigation
fix(stratify): report negative cycles with a stable predicate pair (#410) - #419
Merged
Merged
Conversation
) stratify() walked the rule dependency graph in HashMap order and returned the first (head, dep) pair whose stratum reached n, so the INT-054 message for the same rules named the predicates in either order between runs. Store the edges in a BTreeMap so heads are walked in sorted order. The message now matches the wiki example every time; acceptance is unchanged. Adds a unit test that builds the same two-rule cycle 64 times and checks the exact message. Other error paths in the evaluator, optimizer and magic-sets use fixed text or iterate Vecs, so they were not affected. Closes #410 Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy
Codecov Report✅ All modified and coverable lines are covered by tests. 📢 Thoughts on this report? Let us know! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Closes #410.
stratify()walked the rule dependency graph inHashMaporder and reported the first(head, dep)pair whose stratum reachedn. So the INT-054 message for the same rules named the two predicates in either order, depending on the run. The edges are now stored in aBTreeMap, so heads are walked in sorted order and the same rules always give the same message. Which rules are accepted or rejected is unchanged.For the example in the issue, the message is now always:
This matches the Stratification section of the wiki Datalog Reference, so the wiki needs no change.
Other error paths
As the issue asked, I checked the
err_coded!sites inevaluator.rs,optimizer.rs,magic_sets.rsandrules.rs. They use fixed text or iterateVecs, so none has the same problem.Tests
test_negative_cycle_error_message_is_deterministic: it builds the two-rule cycle 64 times, each with a freshRandomState, and checks the exact message. Before the fix it failed with the reversed pair.cargo fmt --check,cargo clippy -- -D warnings, andcargo test: 1203 passed, 0 failed, 8 ignored.Docs: CHANGELOG entry and test counts updated (CLAUDE.md, README.md, docs/TEST_COVERAGE.md).
🤖 Generated with Claude Code
https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy