8000 fuzz(datalog_eval): count partial bindings in the join guard (#597) by adityamukho · Pull Request #600 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

fuzz(datalog_eval): count partial bindings in the join guard (#597) #600

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
adityamukho merged 1 commit into from
Oct 15, 2026
Merged

fuzz(datalog_eval): count partial bindings in the join guard (#597) #600

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions fuzz/corpus/datalog_eval/seed_long_not_join_body_597.txt
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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])])
16 changes: 11 additions & 5 deletions fuzz/fuzz_targets/datalog_eval.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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;
}
Expand All @@ -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
Expand Down Expand Up @@ -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 {
Expand All @@ -154,6 +159,7 @@ fn count_join<'a>(
}
});
if matches {
*rows += 1;
count_join(rest, bound, rows);
}
bound.truncate(mark);
Expand Down
Loading
0