fix(provenance): prove bound recursive queries from Magic Sets' evaluated tuples by jsam · Pull Request #354 · inputlayer/inputlayer

jsam · 2026-10-05T13:18:11Z

Intent

I want you to really hyper focus on making the symbolic engine, you know, crisp and really truly production ready. (Context: the first engine baseline on the dedicated benchmark host, main 25058f1, perf-gate/baselines/engine-baseline-2026-10-04.md on branch fm/bench-machine, shows .why ?reach(1, Y) (a recursive rule, 4 result rows, 200 nodes / 300 edges) takes 1.67 s p50, while .why on a non-recursive rule takes 3.4 ms. Proofs are the core of 'decisions your agents can prove'.)

What Changed

After a Magic Sets rewrite, the engine now lists the adorned relations it created (e.g. reach_bf → reach, via the new MagicSetRewriter::adorned_relations). When execution finishes, it copies each adorned relation's tuples into the derived results under the original relation's name, so proof search can look them up. If a relation has more than one adornment, its tuples are merged without duplicates. If the program also evaluated the relation unrestricted, that full result is left as is.
Proof search no longer re-derives a subgoal from the rules when the evaluation already computed every tuple of that derived relation (ProofContext::is_complete). If such a subgoal has no matching tuple, it fails right away. Before, .why on a left-recursive closure (e.g. .why ?reach(1, Y)) kept re-deriving the closure around every cycle in the graph.
Added tests:
- engine tests for exposing and merging adorned relations;
- a prove_body test showing a computed relation isn't re-derived;
- handler tests checking that .why / .why full on left- and right-recursive paths over a cyclic graph return the expected rows, with proofs that go all the way down to edge facts.
Also added a why_recursive_cyclic criterion benchmark: the 200-node / 300-edge random graph and a 30-node ring.

Risk Assessment

✅ Low: The change is well-bounded. Adorned Magic Sets tuples are exposed under the original name only when the program did not also evaluate that relation unrestricted. Because adornments bind only positions that stay invariant across recursion, the demanded subset covers every subgoal proof search reaches. Truncation by the result cap only hits the query head, and the .why path turns off constant specialization, so is_complete holds for every derived relation the proof context sees. The prior round's removal of materialized is fully applied.

Testing

I followed the operator's budget limits: the targeted provenance, Magic Sets and proof lib tests (all 138 passed) and the why_recursive_cyclic benchmark. I did not build the base commit and did not run the whole workspace. I then built the release server and client at HEAD and ran them against a throwaway data directory, sending live queries over the WebSocket API. On the perf-gate graph, .why ?reach(1, Y) returned the same 4 rows as the plain query in 2.1–2.3 ms per call, against the 1.67 s baseline, and every proof was complete down to edge facts. On the 6-edge cycle, the bound recursive .why variants each returned in about 2 ms, fully grounded. A query for a row that does not exist returned an empty result quickly. .why_not still names the correct blocker for each rule. In the benchmark, random_200_300 took about 0.91 ms and ring_30 (a 30-node ring where every node reaches every other) about 22.6 ms. I removed the transient binaries and a stale server and temp directory left over from the previous run.

Live validation: ✅ go - 5 of 6 scenarios driven live against the product

Scenario	Result	Live	Evidence
User runs `.why ?reach(1, Y)` on the perf-gate 200-node/300-edge recursive graph and gets proofs in milliseconds instead of 1.67 s	✅ pass	live	head-0253839e-live-transcript.txt: 5 calls at 2.1–2.3 ms each, 4 rows, the same rows as `?reach(1, Y)`
Every proof returned for the bound recursive query is complete and reaches input edge facts, with no truncated or untraced derived leaves	✅ pass	live	head-0253839e-live-transcript.txt: every root is 'grounded in input facts' for reach, path, full path, path(2,2) and rpath
Adversarial: bound left-recursive `.why ?path(1, Y)` and `.why ?path(2, 2)` around a 3-cycle (previously 27 s and 12 s) return quickly and correctly	✅ pass	live	head-0253839e-live-transcript.txt: .why ?path(1,Y) 2.3 ms with 5 rows, .why full 2.4 ms, .why ?path(2,2) 1.9 ms; regression test recursive_proof_tests passes
Adversarial: `.why` for a recursive tuple that does not exist (path(4,1)) returns no rows and no false proof	✅ pass	live	head-0253839e-live-transcript.txt: `.why ?path(4, 1)` returned 0 rows in 1.4 ms
`.why_not` on recursive relations still names the true blocker for each rule after the proof-context change	✅ pass	live	head-0253839e-why-not-transcript.txt: `.why_not path(4, 1)` blames cyc(4,1) and cyc(5,1); `.why_not reach(1, 2)` blames edge(1,2) and edge(137,2)
The why_recursive_cyclic benchmark guards proof speed on cyclic closures	⏸️ untested	no	The prior payload recorded this as a Criterion benchmark of the handler (random_200_300 ≈ 0.91 ms, ring_30 ≈ 22.6 ms), not as a run against the live server, so it did not establish a live result. The…

Evidence: Live .why transcript at HEAD (200/300 reach + cyclic path/rpath)

=== seed (head) ===
Rule 'path' registered.
> +rpath(X, Y) <- cyc(X, Y)
Rule 'rpath' registered.
> +rpath(X, Z) <- cyc(X, Y), rpath(Y, Z)
Rule 'rpath' registered.

=== [head] ?reach(1, Y)  (2.3 ms, result, 362 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: none

=== [head] .why ?reach(1, Y)  (2.3 ms, result, 4448 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: 4
  root reach[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root reach[1,82] nodes={"rule":2,"fact":2} grounded in input facts
  root reach[1,137] nodes={"rule":1,"fact":1} grounded in input facts
  root reach[1,139] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?reach(1, Y)  (2.1 ms, result, 4448 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: 4
  root reach[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root reach[1,82] nodes={"rule":2,"fact":2} grounded in input facts
  root reach[1,137] nodes={"rule":1,"fact":1} grounded in input facts
  root reach[1,139] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?reach(1, Y)  (2.3 ms, result, 4448 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: 4
  root reach[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root reach[1,82] nodes={"rule":2,"fact":2} grounded in input facts
  root reach[1,137] nodes={"rule":1,"fact":1} grounded in input facts
  root reach[1,139] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?reach(1, Y)  (2.2 ms, result, 4448 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: 4
  root reach[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root reach[1,82] nodes={"rule":2,"fact":2} grounded in input facts
  root reach[1,137] nodes={"rule":1,"fact":1} grounded in input facts
  root reach[1,139] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?reach(1, Y)  (2.2 ms, result, 4449 bytes) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
proof_trees: 4
  root reach[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root reach[1,82] nodes={"rule":2,"fact":2} grounded in input facts
  root reach[1,137] nodes={"rule":1,"fact":1} grounded in input facts
  root reach[1,139] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?path(1, Y)  (2.3 ms, result, 7392 bytes) ===
rows (5): [1,1] [1,2] [1,3] [1,4] [1,5]
proof_trees: 5
  root path[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root path[1,2] nodes={"rule":1,"fact":1} grounded in input facts
  root path[1,3] nodes={"rule":2,"fact":2} grounded in input facts
  root path[1,4] nodes={"rule":3,"fact":3} grounded in input facts
  root path[1,5] nodes={"rule":2,"fact":2} grounded in input facts

=== [head] .why full ?path(1, Y)  (2.4 ms, result, 7392 bytes) ===
rows (5): [1,1] [1,2] [1,3] [1,4] [1,5]
proof_trees: 5
  root path[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root path[1,2] nodes={"rule":1,"fact":1} grounded in input facts
  root path[1,3] nodes={"rule":2,"fact":2} grounded in input facts
  root path[1,4] nodes={"rule":3,"fact":3} grounded in input facts
  root path[1,5] nodes={"rule":2,"fact":2} grounded in input facts

=== [head] .why ?path(2, 2)  (1.9 ms, result, 2040 bytes) ===
rows (1): [2,2]
proof_trees: 1
  root path[2,2] nodes={"rule":3,"fact":3} grounded in input facts

=== [head] .why ?rpath(1, Y)  (2.0 ms, result, 6075 bytes) ===
rows (5): [1,1] [1,2] [1,3] [1,4] [1,5]
proof_trees: 5
  root rpath[1,1] nodes={"rule":3,"fact":3} grounded in input facts
  root rpath[1,2] nodes={"rule":1,"fact":1} grounded in input facts
  root rpath[1,3] nodes={"rule":2,"fact":2} grounded in input facts
  root rpath[1,4] nodes={"rule":3,"fact":3} grounded in input facts
  root rpath[1,5] nodes={"rule":2,"fact":2} grounded in input facts

=== [head] .why ?path(4, 1)  (1.4 ms, result, 132 bytes) ===
rows (0): 
proof_trees: none

=== [head] .why_not ?path(4, 1)  (0.5 ms, result, 1109 bytes) ===
rows (2): ["?path(4, 1) was NOT derived:"] ["  No rules produce this relation."]
proof_trees: 1
  root ?path[4,1] nodes={"why_not":2} PROBLEMS: why_not node ?path[4,1] {"blocker":{"reason":"?path(4, 1) was NOT derived","type":"head_unification_failed"},"clause_index":0,"clause_text":"","rule_name":"?path"}; why_not node ?path[4,1] {"blocker":{"reason":"No rules produce this relation","type":"head_unification_failed"},"clause_index":0,"clause_text":"","rule_name":"?path"}

Evidence: Live .why_not transcript at HEAD

=== seed (head) ===
Rule 'path' registered.
> +rpath(X, Y) <- cyc(X, Y)
Rule 'rpath' registered.
> +rpath(X, Z) <- cyc(X, Y), rpath(Y, Z)
Rule 'rpath' registered.

=== [head] .why_not path(4, 1)  (2.1 ms, result, 2146 bytes) ===
rows (9): ["path(4, 1) was NOT derived:"] [""] ["  Rule: path (clause 0)"] ["    path(X, Y) <- cyc(X, Y)"] ["    Blocker: Body predicate 0 (cyc(4, 1)) failed: No matching tuples in cyc"] [""] ["  Rule: path (clause 1)"] ["    path(X, Z) <- path(X, Y), cyc(Y, Z)"] ["    Blocker: Body predicate 1 (cyc(5, 1)) failed: No matching tuples in cyc"]
proof_trees: 1
  root path[4,1] nodes={"why_not":5,"fact":1} PROBLEMS: why_not node path[4,1] {"blocker":{"reason":"path(4, 1) was NOT derived","type":"head_unification_failed"},"clause_index":0,"clause_text":"","rule_name":"path"}; why_not node path[4,1] {"bindings":{"X":4,"Y":5,"Z":1},"children":["n2","n3"],"conclusion":{"args":[4,1],"pred":"path"},"kind":"why_not","rule_id":"path(X, Z) <- path(X, Y), cyc(Y, Z)"}; why_not node cyc[5,1] {"blocker":{"predicate_index":1,"predicate_text":"cyc(5, 1)","reason":"No matching tuples in cyc","type":"body_atom_failed"},"clause_index":1,"clause_text":"cyc(5, 1)","rule_name":"cyc"}; untraced derived leaf path[4,5]; why_not node path[4,1] {"bindings":{"X":4,"Y":1},"children":["n0"],"conclusion":{"args":[4,1],"pred":"path"},"kind":"why_not","rule_id":"path(X, Y) <- cyc(X, Y)"}; why_not node cyc[4,1] {"blocker":{"predicate_index":0,"predicate_text":"cyc(4, 1)","reason":"No matching tuples in cyc","type":"body_atom_failed"},"clause_index":0,"clause_text":"cyc(4, 1)","rule_name":"cyc"}

=== [head] .why_not reach(1, 2)  (64.0 ms, result, 2196 bytes) ===
rows (9): ["reach(1, 2) was NOT derived:"] [""] ["  Rule: reach (clause 0)"] ["    reach(X, Y) <- edge(X, Y)"] ["    Blocker: Body predicate 0 (edge(1, 2)) failed: No matching tuples in edge"] [""] ["  Rule: reach (clause 1)"] ["    reach(X, Z) <- reach(X, Y), edge(Y, Z)"] ["    Blocker: Body predicate 1 (edge(137, 2)) failed: No matching tuples in edge"]
proof_trees: 1
  root reach[1,2] nodes={"why_not":5,"fact":1} PROBLEMS: why_not node reach[1,2] {"blocker":{"reason":"reach(1, 2) was NOT derived","type":"head_unification_failed"},"clause_index":0,"clause_text":"","rule_name":"reach"}; why_not node reach[1,2] {"bindings":{"X":1,"Y":137,"Z":2},"children":["n2","n3"],"conclusion":{"args":[1,2],"pred":"reach"},"kind":"why_not","rule_id":"reach(X, Z) <- reach(X, Y), edge(Y, Z)"}; why_not node edge[137,2] {"blocker":{"predicate_index":1,"predicate_text":"edge(137, 2)","reason":"No matching tuples in edge","type":"body_atom_failed"},"clause_index":1,"clause_text":"edge(137, 2)","rule_name":"edge"}; untraced derived leaf reach[1,137]; why_not node reach[1,2] {"bindings":{"X":1,"Y":2},"children":["n0"],"conclusion":{"args":[1,2],"pred":"reach"},"kind":"why_not","rule_id":"reach(X, Y) <- edge(X, Y)"}; why_not node edge[1,2] {"blocker":{"predicate_index":0,"predicate_text":"edge(1, 2)","reason":"No matching tuples in edge","type":"body_atom_failed"},"clause_index":0,"clause_text":"edge(1, 2)","rule_name":"edge"}

Evidence: Targeted release lib tests log

   Compiling serde v1.0.229
   Compiling fastrand v2.5.0
   Compiling figment v0.10.19
   Compiling ciborium-io v0.2.2
   Compiling plotters-backend v0.3.7
   Compiling itertools v0.10.5
   Compiling wait-timeout v0.2.1
   Compiling bit-vec v0.8.0
   Compiling cast v0.3.0
   Compiling quick-error v1.2.3
   Compiling rand_xorshift v0.4.0
   Compiling is-terminal v0.4.17
   Compiling anes v0.1.6
   Compiling oorandom v11.1.5
   Compiling unarray v0.1.4
   Compiling ciborium-ll v0.2.2
   Compiling tempfile v3.27.0
   Compiling plotters-svg v0.3.7
   Compiling bit-set v0.8.0
   Compiling plotters v0.3.7
   Compiling rusty-fork v0.3.1
   Compiling proptest v1.11.0
   Compiling smallvec v1.16.2
   Compiling chrono v0.4.39
   Compiling toml_datetime v0.6.11
   Compiling serde_spanned v0.6.9
   Compiling bincode v1.3.3
   Compiling serde_urlencoded v0.7.1
   Compiling tracing-serde v0.2.0
   Compiling inputlayer-ws-protocol v0.1.0 (~/.no-mistakes/worktrees/9eea230c3aae/01M462DB7ZG5ZHMXCCNVBTHPCY/ws-protocol)
   Compiling tinytemplate v1.2.1
   Compiling ciborium v0.2.2
   Compiling parking_lot_core v0.9.12
   Compiling icu_normalizer v2.3.0
   Compiling columnar v0.11.1
   Compiling nibble_vec v0.1.0
   Compiling columnation v0.1.2
   Compiling tracing-subscriber v0.3.23
   Compiling toml_edit v0.22.27
   Compiling radix_trie v0.2.1
   Compiling parking_lot v0.12.5
   Compiling dashmap v5.5.3
   Compiling rustyline v14.0.0
   Compiling criterion-plot v0.5.0
   Compiling tokio v1.53.2
   Compiling hnsw_rs v0.3.4
   Compiling idna_adapter v1.2.2
   Compiling idna v1.1.0
   Compiling criterion v0.5.1
   Compiling url v2.5.8
   Compiling arrow-array v53.4.1
   Compiling timely_communication v0.27.0
   Compiling tracing-appender v0.2.5
   Compiling toml v0.8.23
   Compiling timely v0.27.0
   Compiling arrow-select v53.4.1
   Compiling arrow-arith v53.4.1
   Compiling arrow-row v53.4.1
   Compiling arrow-cast v53.4.1
   Compiling arrow-ord v53.4.1
   Compiling arrow-string v53.4.1
   Compiling tokio-util v0.7.19
   Compiling tower v0.5.3
   Compiling tokio-tungstenite v0.24.0
   Compiling tokio-native-tls v0.3.1
   Compiling inputlayer-testkit v0.1.0 (~/.no-mistakes/worktrees/9eea230c3aae/01M462DB7ZG5ZHMXCCNVBTHPCY/testkit)
   Compiling tower-http v0.6.11
   Compiling h2 v0.4.19
   Compiling tower-http v0.5.2
   Compiling differential-dataflow v0.20.0
   Compiling arrow-ipc v53.4.1
   Compiling arrow-csv v53.4.1
   Compiling arrow-json v53.4.1
   Compiling parquet v53.4.1
   Compiling arrow v53.4.1
   Compiling hyper v1.11.1
   Compiling hyper-util v0.1.21
   Compiling hyper-tls v0.6.0
   Compiling axum v0.7.9
   Compiling reqwest v0.12.28
   Compiling inputlayer-ontology-client v0.1.0 (~/.no-mistakes/worktrees/9eea230c3aae/01M462DB7ZG5ZHMXCCNVBTHPCY/ontology-client)
   Compiling inputlayer v0.1.0 (~/.no-mistakes/worktrees/9eea230c3aae/01M462DB7ZG5ZHMXCCNVBTHPCY)
    Finished `release` profile [optimized] target(s) in 4m 04s
     Running unittests src/lib.rs (target/release/deps/inputlayer-9371120605bad74d)

running 138 tests
test magic_sets::specialize::tests::test_specialize_bound_non_recursive_relation ... ok
test magic_sets::tests::test_magic_seed_string_constant ... ok
test magic_sets::tests::test_magic_seed_facts ... ok
test magic_sets::tests::test_adornment_detection_all_bound_tc ... ok
test magic_sets::tests::test_no_magic_propagation_same_bound_var ... ok
test magic_sets::tests::test_no_magic_for_non_invariant_bound ... ok
test magic_sets::tests::test_adornment_suffix ... ok
test magic_sets::tests::test_adornment_detection_basic ... ok
test incremental::tests::test_derived_relations_accessor ... ok
test magic_sets::tests::test_no_rewrite_when_non_recursive ... ok
test magic_sets::tests::test_all_bound_query_tc ... ok
test magic_sets::tests::test_rewrite_transitive_closure ... ok
test magic_sets::specialize::tests::test_specialize_flows_through_rule_chains ... ok
test magic_sets::tests::test_adornment_detection_string_constant ... ok
test magic_sets::tests::test_all_bound_query_non_tc ... ok
test magic_sets::specialize::tests::test_specialize_skips_recursive_unbound_and_unconstrainable ... ok
test magic_sets::tests::test_adornment_detection_no_bindings ... ok
test magic_sets::tests::test_mutual_recursion_not_adorned ... ok
test magic_sets::tests::test_rewrite_preserves_non_recursive ... ok
test magic_sets::tests::test_two_constants_seed_one_adornment ... ok
test magic_sets::tests::test_query_rewritten_to_adorned ... ok
test incremental::tests::test_derived_stats ... ok
test magic_sets::tests::test_unbound_use_keeps_original_rules ... ok
test protocol::rest::handlers::ws::execute::tests::test_result_frame_carries_id_rows_and_provenance ... ok
test protocol::wire::tests::test_wire_tuple_provenance_variants ... ok
test provenance::backward_chaining::tests::test_aggregation_count ... ok
test provenance::backward_chaining::tests::test_aggregation_export_mode ... ok
test provenance::backward_chaining::tests::test_aggregation_gui_mode_trims ... ok
test provenance::backward_chaining::tests::test_comparison_rule ... ok
test provenance::backward_chaining::tests::test_join_rule ... ok
test provenance::backward_chaining::tests::test_base_fact_missing ... ok
test provenance::backward_chaining::tests::test_depth_limit ... ok
test provenance::backward_chaining::tests::test_negation ... ok
test provenance::backward_chaining::tests::test_multi_level_rules ... ok
test protocol::wire::tests::test_wire_tuple_with_provenance ... ok
test provenance::backward_chaining::tests::test_recursive_cycle_detection ... ok
test provenance::proof_relations::tests::indexed_candidates_are_the_matching_tuples_in_insertion_order ... ok
test provenance::proof_relations::tests::a_pattern_is_scanned_until_it_repeats_then_indexed_once ... ok
test provenance::proof_relations::tests::integers_of_either_width_and_signed_zeros_share_a_key ... ok
test provenance::proof_relations::tests::unbound_lookups_and_missing_relations_scan ... ok
test provenance::backward_chaining::tests::test_json_export_shape ... ok
test provenance::proof_tree::tests::test_aggregate_node ... ok
test protocol::wire::tests::test_wire_tuple_without_provenance ... ok
test provenance::proof_tree::tests::test_diamond_deduplication ... ok
test provenance::backward_chaining::tests::test_single_rule ... ok
test provenance::proof_relations::tests::contains_uses_exact_tuple_equality_with_or_without_an_index ... ok
test provenance::backward_chaining::tests::test_with_derived_data ... ok
test provenance::backward_chaining::tests::test_aggregation_never_truncated ... ok
test provenance::proof_tree::tests::test_fact_deduplication ... ok
test provenance::proof_tree::tests::test_format_tree_output ... ok
test provenance::proof_tree::tests::test_json_roundtrip ... ok
test provenance::proof_tree::tests::test_empty_graph ... ok
test provenance::indexed_proof_tests::indexed_why_not_equals_scanned_why_not ... ok
test provenance::backward_chaining::tests::test_recursive_transitive_closure ... ok
test provenance::proof_relations::tests::tuples_lacking_a_bound_column_stay_candidates_in_order ... ok
test provenance::backward_chaining::tests::test_base_fact ... ok
test provenance::proof_tree::tests::test_json_shape_matches_spec ... ok
test provenance::proof_tree::tests::test_rule_with_children ... ok
test provenance::prove_body::tests::test_computed_relation_is_not_re_derived ... ok
test provenance::prove_body::tests::test_evaluation_order_waits_for_bindings ... ok
test provenance::prove_body::tests::test_comparison_passes ... ok
test provenance::proof_tree::tests::test_single_fact_node ... ok
test provenance::prove_body::tests::test_empty_states_error ... ok
test provenance::proof_tree::tests::test_truncated_node ... ok
test provenance::prove_body::tests::test_comparison_before_its_atom_proves_in_source_order ... ok
test provenance::proof_tree::tests::test_why_not_node ... ok
test provenance::prove_body::tests::test_comparison_fails_filters ... ok
test provenance::prove_body::tests::test_multi_body_join ... ok
test provenance::prove_body::tests::test_negation_fails ... ok
test provenance::tests::test_blocker_display ... ok
test provenance::unification::tests::test_evaluate_comparison_neq ... ok
test provenance::prove_body::tests::test_positive_base_match ... ok
test provenance::prove_body::tests::test_negation_reads_derived_relations ... ok
test provenance::prove_body::tests::test_candidate_cap ... ok
test provenance::tests::test_why_not_format ... ok
test provenance::unification::tests::test_find_matching_all_unbound ... ok
test provenance::tests::test_proof_config_default ... ok
test provenance::unification::tests::test_evaluate_comparison_strings_and_mixed_types ... ok
test provenance::unification::tests::test_evaluate_comparison_eq ... ok
test provenance::unification::tests::test_evaluate_comparison_lt_gt ... ok
test provenance::unification::tests::test_find_matching_fully_bound ... ok
test provenance::tests::test_why_not_no_rules ... ok
test provenance::prove_body::tests::test_negation_succeeds ... ok
test provenance::prove_body::tests::test_positive_derived_fallback ... ok
test provenance::unification::tests::test_format_bound_terms ... ok
test provenance::unification::tests::test_substitute_atom_fully_bound ... ok
test provenance::unification::tests::test_substitute_atom_partial ... ok
test provenance::unification::tests::test_unify_all_variables ... ok
test provenance::unification::tests::test_unify_repeated_variable_conflict ... ok
test provenance::unification::tests::test_unify_with_string_constant ... ok
test provenance::why_not::tests::test_why_not_body_atom_fails ... ok
test provenance::unification::tests::test_unify_constant_mismatch ... ok
test provenance::why_not::tests::test_why_not_comparison_fails ... ok
test provenance::unification::tests::test_unify_with_placeholder ... ok
test provenance::why_not::tests::test_why_not_graph_json_export ... ok
test provenance::why_not::tests::test_why_not_nonexistent_relation ... ok
test provenance::why_not::tests::test_why_not_wrong_arity ... ok
test provenance::why_not::tests::test_why_not_negation_blocks ... ok
test provenance::unification::tests::test_find_matching_empty_relation ... ok
test session::tests::test_provenance_deserialization ... ok
test provenance::unification::tests::test_unify_arity_mismatch ... ok
test provenance::unification::tests::test_cross_type_numeric_equality ... ok
test storage_engine::snapshot::plan_cache_tests::magic_sets_seeds_are_restored_for_every_execution ... ok
test provenance::unification::tests::test_evaluate_comparison_unbound_error ... ok
test provenance::why_not::tests::test_why_not_join_shows_progress ... ok
test provenance::unification::tests::test_find_matching_partially_bound ... ok
test tests::test_expose_adorned_relations_merges_adornments ... ok
test provenance::why_not::tests::test_why_not_multiple_rules_all_fail ... ok
test provenance::unification::tests::test_unify_repeated_variable ... ok
test tests::test_magic_sets_string_constants ... ok
test provenance::why_not::tests::test_why_not_base_fact_missing ... ok
test provenance::unification::tests::test_unify_with_constants ... ok
test tests::test_magic_sets_disabled ... ok
test tests::test_magic_sets_both_bound ... ok
test session::tests::test_provenance_serialization ... ok
test tests::test_derived_exposes_adorned_relation_under_original_name ... ok
test tests::test_magic_sets_unbound_unchanged ... ok
test tests::test_magic_sets_tc_chain ... ok
test tests::test_derived_keeps_unrestricted_evaluation ... ok
test tests::test_magic_sets_with_sip ... ok
test tests::test_magic_sets_tc_matches_unbound ... ok
test protocol::handler::pinned_proof_tests::a_proof_that_does_not_end_the_program_rejects_it ... ok
test protocol::handler::pinned_proof_tests::a_failed_program_returns_no_proof ... ok
test protocol::handler::tests::test_derived_relation_uses_query_variable_names ... ok
test protocol::handler::pinned_proof_tests::writes_after_the_commit_do_not_change_the_proof ... ok
test protocol::handler::tests::test_provenance_tags_persistent_vs_ephemeral ... ok
test protocol::handler::pinned_proof_tests::the_reply_names_the_revision_the_writes_committed_at ... ok
test protocol::handler::pinned_proof_tests::the_proof_revision_is_the_snapshot_before_the_program_changes ... ok
test protocol::handler::pinned_proof_tests::the_documented_example_runs ... ok
test protocol::handler::pinned_proof_tests::the_proof_follows_the_guard_through_a_restage ... ok
test protocol::handler::pinned_proof_tests::why_full_and_why_not_can_end_a_program_that_writes ... ok
test protocol::handler::pinned_proof_tests::a_failed_proof_fails_its_statement_and_keeps_the_writes ... ok
test protocol::handler::pinned_proof_tests::a_won_claim_returns_the_proof_of_the_state_its_guard_passed_on ... ok
test protocol::handler::pinned_proof_tests::a_refused_claim_returns_an_empty_proof ... ok
test protocol::handler::recursive_proof_tests::why_proves_bound_recursive_queries_around_a_cycle ... ok
test protocol::handler::proof_snapshot_tests::why_not_explains_the_captured_snapshot_despite_concurrent_writes ... ok
test protocol::handler::proof_snapshot_tests::why_explains_the_captured_snapshot_despite_concurrent_writes ... ok
test provenance::indexed_proof_tests::indexed_proofs_equal_scanned_proofs ... ok

test result: ok. 138 passed; 0 failed; 0 ignored; 0 measured; 3031 filtered out; finished in 1.33s

EXIT 0

Evidence: Criterion why_recursive_cyclic results

Source: Criterion why_recursive_cyclic results (local file: ~/.no-mistakes/evidence/01M462DB7ZG5ZHMXCCNVBTHPCY/bench-why_recursive_cyclic.log)

why_recursive_cyclic/random_200_300 time: [892.52 µs 910.50 µs 938.54 µs]
why_recursive_cyclic/ring_30 time: [22.427 ms 22.628 ms 22.822 ms]

Evidence: Live .why ?reach(1, Y) excerpt

=== [head] .why ?reach(1, Y) (2.2 ms, result) ===
rows (4): [1,1] [1,82] [1,137] [1,139]
root reach[1,1] nodes={rule:3,fact:3} grounded in input facts
root reach[1,82] nodes={rule:2,fact:2} grounded in input facts
root reach[1,137] nodes={rule:1,fact:1} grounded in input facts
root reach[1,139] nodes={rule:3,fact:3} grounded in input facts

- Outcome: 🔧 1 issue found → no changes applied ✅ across 3 runs (57m8s)

Pipeline

Updates from git push no-mistakes

✅ **intent** - passed

✅ No issues found.

✅ **Rebase** - passed

✅ No issues found.

⚠️ **Review** - 0 issues

✅ No issues found.

⚠️ src/protocol/handler.rs:808 - This is a component the intent doesn't need. Besides the derived-data completeness check, the change adds a second completeness source: ProofContext::materialized, with_materialized (src/provenance/backward_chaining.rs:46, :84) and the materialized.contains branch of is_complete (backward_chaining.rs:109), wired up from snapshot.materialized_relations here. In production that set is always empty. Materializations come only from enable_incremental/set_auto_materialize/materialize_derived_relation, and nothing outside tests calls any of them. The slow .why ?reach(1, Y) case is fixed entirely by expose_adorned_relations plus the derived-data half of is_complete. The new branch only runs in tests (the third case of prove_body.rs test_computed_relation_is_not_re_derived). The .why_not context at handler.rs:919-924 never sets it, so the two proof paths treat materialized relations differently. Suggested fix: remove the materialized field, with_materialized, its call here and that test case, and keep is_complete based on derived data only. If you want this for future materialization support, keep it, but then also wire it into .why_not.

🔧 Fix applied.
✅ Re-checked - no issues remain.

🔧 **Test** - 1 issue found → no changes applied ✅

ℹ️ src/provenance/backward_chaining.rs:338 - Not a regression, but it bears on the 'production-ready proofs' goal: on cyclic data, backward chaining still sometimes ends a proof in a source: derived fact leaf instead of tracing that tuple back to edge facts. Examples: .why ?path(X, Y) row path(3,5) goes through an untraced path(3,3); on the 15-node graph, reach(1,8) and reach(1,13) are untraced. The base build gives the same leaves for unbound queries, and this change makes bound queries match those unbound proofs exactly. The likely cause is the visited-set fallback in src/provenance/backward_chaining.rs (~line 338), which falls back to a Derived leaf once ancestors block every rule derivation. Fixing it would be a follow-up, outside this change.
Live validation: ✅ go - 7 of 7 scenarios driven live against the product

Scenario	Result	Live	Evidence
`.why ?reach(1, Y)` on the perf-gate engine graph (200 nodes/300 edges) returns 4 grounded proofs in milliseconds instead of ~1.7 s	✅ pass	live	summary.txt; new-g200.jsonl (p50 1.4 ms over 21 runs) vs base-g200.jsonl (p50 1732.8 ms); 4 rows and 4 trees; every leaf an EDB edge; root proofs identical to base
Bound recursive `.why` around a cycle (left- and right-linear, `full`, fully bound) gives correct rows and proofs grounded in edge facts	✅ pass	live	cyc.jsonl / base-cyc.jsonl: `.why ?path(1, Y)` 26.8 s -> 2 ms, `.why ?path(2, 2)` 12 s -> 1.3 ms; rows and root proofs identical; all grounded
Adversarial: a graph where the old proof search never finished (15 nodes/30 edges) now answers	✅ pass	live	base-g15.jsonl: deadline_exceeded after 30 s; new-g15.jsonl: 14 rows in 7.4 ms; proofs identical to the base build's unbound proofs of the same tuples
Adversarial: a bound query with no answers (`.why ?path(4, 1)`, `?reach(5, Y)`) returns no rows quickly rather than re-deriving the closure	✅ pass	live	cyc.jsonl / new-mixed.jsonl: 0 rows in about 1 ms
Mutual recursion, non-linear recursion, negation over recursion and conjunctive bound queries keep the same proofs	✅ pass	live	new-mixed.jsonl vs base-mixed.jsonl: rows and root proofs identical for reach/even/odd/unreached
After retracting edge(3,4), `.why ?path(1, Y)` drops node 4 and no proof uses the retracted edge	✅ pass	live	new-retract.jsonl: rows [1,1],[1,2],[1,3],[1,5]; all proofs grounded in the reduced EDB
Unbound `.why ?path(X, Y)` / `?reach(X, Y)` (no Magic Sets) gives the same proofs as before	✅ pass	live	base-g15-unbound.jsonl vs new-g15-unbound.jsonl and base-cyc-unbound.jsonl vs cyc.jsonl: identical rows and root proofs

cargo build --release --bin inputlayer-server --bin inputlayer-client at be793058, plus a base ddcd1584 build from git archive, each server running on its own port, temp data dir and HOME
Loaded fixtures with inputlayer-client --script: a 6-edge cycle with left- and right-linear rules, the perf-gate graph Graph::random(200,300,42) regenerated with the same SplitMix64, a 15-node/30-edge random graph, and a mixed KG (non-linear reach, mutually recursive even/odd, negation over recursion)
WebSocket client (Node 22) sending .why programs and capturing raw proof_trees and wall-clock timings; a checker that requires one tree per row, each root equal to its row, and every leaf a real EDB edge fact
.why ?reach(1, Y) x21 on the new build vs x5 on the base, plus .why ?two_hop(1, Z) and plain ?reach(1, Y) for reference
.why ?path(1, Y), .why full ?path(1, Y), .why ?path(2, 2), .why ?rpath(1, Y), .why ?rpath(X, 5), .why ?path(X, Y) and the no-proof .why ?path(4, 1) on both builds
Compared rows and canonical root proof trees between base and new builds
Retracted edge(3,4) live, then ran .why ?path(1, Y), ?path(1,4) and ?path(3,Y) and checked the proofs against the reduced EDB
cargo test --release --lib -- recursive_proof_tests test_derived_exposes test_derived_keeps test_expose_adorned test_computed_relation_is_not_re_derived
⚠️ The Test agent did not finish within its invocation budget. Reported: agent run tests timed out after 30m0s: agent last produced output 578ms ago (96 observed); agent reported: claude parse events: context deadline exceeded. This is a budget or provider-slowness cut, not a code failure. Re-running the same request costs another full budget, so no further attempt is made automatically. If this repository's targeted tests or evidence gathering routinely approach the default 30m0s, raise test_agent_timeout in global config. Respond with fix to spend another budget: a repair turn runs only for selected findings other than this budget cut, then validation re-runs. Or abort and retry after raising the budget.

🔧 No changes applied.
✅ Re-checked - no issues remain.

Live validation: ✅ go - 5 of 6 scenarios driven live against the product

Scenario	Result	Live	Evidence
User runs `.why ?reach(1, Y)` on the perf-gate 200-node/300-edge recursive graph and gets proofs in milliseconds instead of 1.67 s	✅ pass	live	head-0253839e-live-transcript.txt: 5 calls at 2.1–2.3 ms each, 4 rows, the same rows as `?reach(1, Y)`
Every proof returned for the bound recursive query is complete and reaches input edge facts, with no truncated or untraced derived leaves	✅ pass	live	head-0253839e-live-transcript.txt: every root is 'grounded in input facts' for reach, path, full path, path(2,2) and rpath
Adversarial: bound left-recursive `.why ?path(1, Y)` and `.why ?path(2, 2)` around a 3-cycle (previously 27 s and 12 s) return quickly and correctly	✅ pass	live	head-0253839e-live-transcript.txt: .why ?path(1,Y) 2.3 ms with 5 rows, .why full 2.4 ms, .why ?path(2,2) 1.9 ms; regression test recursive_proof_tests passes
Adversarial: `.why` for a recursive tuple that does not exist (path(4,1)) returns no rows and no false proof	✅ pass	live	head-0253839e-live-transcript.txt: `.why ?path(4, 1)` returned 0 rows in 1.4 ms
`.why_not` on recursive relations still names the true blocker for each rule after the proof-context change	✅ pass	live	head-0253839e-why-not-transcript.txt: `.why_not path(4, 1)` blames cyc(4,1) and cyc(5,1); `.why_not reach(1, 2)` blames edge(1,2) and edge(137,2)
The why_recursive_cyclic benchmark guards proof speed on cyclic closures	⏸️ untested	no	The prior payload recorded this as a Criterion benchmark of the handler (random_200_300 ≈ 0.91 ms, ring_30 ≈ 22.6 ms), not as a run against the live server, so it did not establish a live result. The…

cargo test --release --lib -- provenance magic_sets recursive_proof proof_snapshot pinned_proof test_derived test_expose (138 passed, includes recursive_proof_tests::why_proves_bound_recursive_queries_around_a_cycle)
cargo build --release --bin inputlayer-server --bin inputlayer-client at HEAD 0253839e, then drive.sh: real inputlayer-server on 127.0.0.1:18391 with a temp data dir and bootstrap API key, seeded via inputlayer-client --script, queried over the WebSocket API
Live: ?reach(1, Y) plus 5× .why ?reach(1, Y) on the 200-node/300-edge seed-42 graph
Live: .why ?path(1, Y), .why full ?path(1, Y), .why ?path(2, 2), .why ?rpath(1, Y), .why ?path(4, 1) on the 6-edge cyclic graph
Live: .why_not path(4, 1) and .why_not reach(1, 2) (port 18392)
cargo bench --bench proof_benchmarks -- why_recursive_cyclic

✅ **Document** - passed

✅ No issues found.

✅ **Lint** - passed

✅ No issues found.

✅ **Push** - passed

✅ No issues found.

…ated tuples A bound recursive `.why` (`.why ?reach(1, Y)`) was evaluated by Magic Sets under the adorned relation `reach_bf`, so proof search found no `reach` tuples in the derived data. Every subgoal on the recursive relation then fell through to forward enumeration from the rules, which re-derives the closure with no memoization and explores every path around a cycle down to the depth limit: 1.7 s for the perf-gate engine graph (200 nodes, 300 edges, 4 rows), 32 s for a six-edge graph with one cycle, and no answer after 10 minutes on 15 nodes and 30 edges. - The engine's derived relations now also name each adorned relation's tuples by the relation it restricts, unless the program evaluated that relation unrestricted too. One adornment shares its tuples; several are merged without duplicates. - Proof search no longer re-derives a derived relation the evaluation computed, or one that is materialized: an empty lookup there means the subgoal has no derivation. Proof rows and root proof DAGs are unchanged on a corpus of cyclic, left-, right- and non-linear recursive, same-generation, mutually recursive, negation-over-recursion and random-graph queries. The perf-gate case drops from 1.74 s to 1.2 ms (the query alone takes 1.0 ms). Adds a handler test proving bound recursive queries around a cycle down to `edge` facts, engine tests for the exposed adorned relations, a proof search test for computed relations, and a `why_recursive_cyclic` benchmark group.

…rom proof context

jsam added 2 commits October 5, 2026 13:18

no-mistakes(review): Remove unused materialized completeness source f…

0253839

…rom proof context

jsam force-pushed the fm/fix-why-recursive branch from be79305 to 0253839 Compare October 5, 2026 14:18

jsam changed the title ~~fix(provenance): stop re-deriving recursive closures when proving bound recursive queries~~ fix(provenance): prove bound recursive queries from Magic Sets' evaluated tuples Oct 5, 2026

jsam merged commit 1addf8d into main Oct 5, 2026
21 checks passed

jsam deleted the fm/fix-why-recursive branch October 5, 2026 14:28

jsam mentioned this pull request Oct 5, 2026

Engine release tracker: checkpoints 1-2 live status #199

Closed

Navigation Menu

Repository navigation

fix(provenance): prove bound recursive queries from Magic Sets' evaluated tuples - #354

fix(provenance): prove bound recursive queries from Magic Sets' evaluated tuples#354
jsam merged 2 commits into
mainfrom
fm/fix-why-recursive

jsam commented Oct 5, 2026 •

edited

Loading

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Conversation

jsam commented Oct 5, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Intent

What Changed

Risk Assessment

Testing

Pipeline

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

jsam commented Oct 5, 2026 •

edited

Loading