From 33eba4049d13ca614a41dfcdcfdb577f16521918 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 15 Oct 2026 08:45:27 +0530 Subject: [PATCH] fuzz(datalog_eval): count partial bindings in the join guard (#597) The guard skipped inputs whose patterns join to more than 50,000 rows but counted only the rows after the last pattern. A not-join body still runs on the executor pattern by pattern in text order, so the nightly's 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and timed out after 60 s. That is the known #575 limit (streaming engine, #546 for negation), not a new bug. The guard now counts the bindings after every pattern. On the v3 corpus (4,783 inputs) coverage drops from 9,719 to 9,712 edges. The input is added as a seed. Refs #597 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP --- .../datalog_eval/seed_long_not_join_body_597.txt | 1 + fuzz/fuzz_targets/datalog_eval.rs | 16 +++++++++++----- 2 files changed, 12 insertions(+), 5 deletions(-) create mode 100644 fuzz/corpus/datalog_eval/seed_long_not_join_body_597.txt diff --git a/fuzz/corpus/datalog_eval/seed_long_not_join_body_597.txt b/fuzz/corpus/datalog_eval/seed_long_not_join_body_597.txt new file mode 100644 index 0000000000..e38d5d0e14 --- /dev/null +++ b/fuzz/corpus/datalog_eval/seed_long_not_join_body_597.txt @@ -0,0 +1 @@ +(query [: :where [?e ?FFFFFFF ?c] (not-join [?e ?_ct?6EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lEEneFFFunqnjFmaxqfn ?c] [?e ?lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEqfn ?c] [?e ?lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?s] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lyznufn6666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnlnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEq ?c000000001002302725] [?e ?lunufn ?c] [?e ?lynnueFFnnue166633333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue166666666nufn ?c] [?e ?lynnueFFnnue6666666?66666666662666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-Eqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnueFFnnueFEEEEEEEWEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lyznufn ?c000000002004605448] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEEEEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnjnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?E ?lynnufn ?c] [?e ?lynnueVFn2nyneFFFfq ?kfn] [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEeEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEyznufn ?c000000001002302724] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666666666666666666666666666666666EEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lu?lynnueFFnnueFEECEEEEEEEEqfn ?c] [?_?e ?lysnufn ?c] [?e ?lunufn ?c] [?e ?lynnueFFnnue333333333nufn ?c] [?e ?lynnueFFnnue6666666?66666666666666666666666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??ylnEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-Eqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueVFnnyneFFFFqfn ?k] [?e ?lynEEEEEEEEEEEEEqfn ?a] [?e ?ynsufun ??nc] [?e ?lunufn ?a] [?e ?lynnue666666666666666FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnntnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEEEEEdEEqfn ?g] [?e ?lynnufn ?c] [?e ?lynnueFF-nnyneFFFFqfn ?k] [?e ?lynEEEEdEEqfn ?g] [?E ?lynnufn ?c] [?e ?lynnueVFn2nyneFFFfqfn ?k] [?e ?lynEEEE6666?66666600000000011406509395579415211FEEEEEEEEEEEqfn ?nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnc] [?_?e ?lEEneFFFunqnjFqfn ?c] [?e ??lynEEEEEEdEEqfn ?g] [?E ?lfalseynnufn ?c] [?e :__magic_qunqnjoqqqq??lynnueVFnnyneFFFfqfn ?ke])]) diff --git a/fuzz/fuzz_targets/datalog_eval.rs b/fuzz/fuzz_targets/datalog_eval.rs index 55d3a27634..32c4e9655b 100644 --- a/fuzz/fuzz_targets/datalog_eval.rs +++ b/fuzz/fuzz_targets/datalog_eval.rs @@ -9,14 +9,17 @@ const FACTS: [[&str; 3]; 3] = [ [":alice", ":age", "30"], ]; -/// Inputs whose patterns could join to more rows than this are skipped. +/// Inputs whose patterns could build more bindings than this are skipped. const MAX_JOIN_ROWS: u64 = 50_000; fuzz_target!(|data: &[u8]| { if let Ok(s) = std::str::from_utf8(data) { // The executor holds every intermediate binding, so patterns that share no // variables build their whole cross product: 3^k rows over these 3 facts. - // That is a known limit, not a new bug (#575, fixed by #473/#549). + // Negation bodies still run there, pattern by pattern in text order, so a + // long body builds every partial binding even when its last pattern + // matches nothing (#597). That is a known limit, not a new bug (#575, + // fixed by #473/#549, and #546 for negation). if join_rows_bound(s) > MAX_JOIN_ROWS { return; } @@ -30,7 +33,8 @@ fuzz_target!(|data: &[u8]| { } }); -/// An upper estimate of the rows a cross product of the input's patterns yields. +/// An upper estimate of the bindings the input's patterns build, partial ones +/// included. /// /// Every innermost vector of three or more tokens counts as a pattern. Patterns are /// grouped by the variables they share (`_` and `?_…` are wildcards and share @@ -123,14 +127,15 @@ fn find(parent: &mut [usize], mut i: usize) -> usize { i } -/// Counts the group's join over `FACTS` depth first, stopping past `MAX_JOIN_ROWS`. +/// Counts the bindings the group's join over `FACTS` builds in text order, after +/// each pattern and not only after the last one, depth first, stopping past +/// `MAX_JOIN_ROWS`. fn count_join<'a>( group: &[[&'a str; 3]], bound: &mut Vec<(&'a str, &'static str)>, rows: &mut u64, ) { let Some((pattern, rest)) = group.split_first() else { - *rows += 1; return; }; for fact in &FACTS { @@ -154,6 +159,7 @@ fn count_join<'a>( } }); if matches { + *rows += 1; count_join(rest, bound, rows); } bound.truncate(mark);