8000 fuzz(datalog_eval): skip inputs whose patterns join to a cross product (#575) by adityamukho · Pull Request #576 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]
Skip to content

fuzz(datalog_eval): skip inputs whose patterns join to a cross product (#575) #576

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 3 commits into from
Oct 13, 2026
Merged

fuzz(datalog_eval): skip inputs whose patterns join to a cross product (#575) #576

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
8d13b30
fuzz(datalog_eval): skip inputs whose patterns join to a cross produc…
adityamukho Oct 13, 2026
e0b3484
fuzz(datalog_eval): ignore brackets inside string literals in the guard
adityamukho Oct 13, 2026
81b89da
ci(codecov): ignore the fuzz harnesses
adityamukho Oct 13, 2026
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
5 changes: 5 additions & 0 deletions codecov.yml
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,11 @@
codecov:
require_ci_to_pass: false

# Fuzz harnesses run under cargo-fuzz, never under cargo test, so their lines
# can only show as uncovered.
ignore:
- "fuzz/**"

coverage:
status:
project:
Expand Down
1 change: 1 addition & 0 deletions fuzz/corpus/datalog_eval/8ee829c9ac5625e2f85feebc78b0ffbccafc23d7
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1 @@
(query [:find ?n:find ?nzYYYYY:find:where [?e ??amEnot-joinm ?Uor-join][?000000000000099e ??suddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddjoin ?n][?00000000dddd00000000000000000000500000000000000000000000000900000000000000000000000000000000000000000000000000000001895298942?e ??amEnot-join ?U][?00000000000000000000000000?OO000000000e ??amEnot-dddddddddddddddddddddddddddddddddddddddddddddddd?ddddddddddddddddd 8000 ddddddddddddjoin ?-][?00000000d?ddd000000000000000000d?ddd000000000000000000000000K00000000000000000v000009000000000000092233720368000000000000000000009000000000000092000000000000007000000000000000v00000900000000000009223372036800000000000000000000900000000000000000000000000000000?m9999e ??sudddddddddddddddjoin ?_][?00000000dddd00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000575408294?m9999e ??suddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddjoin ?n][?00000000dddd00000000000000000000000000000000000000000000000900000000000009223372036800000000000000000000900000000000009223372?e ??amEnot-join ?U][?080023372036854775807?m9999e ??sudddddddddddddddjoin ?_][?00000000dddd00000000000000000000K00000000000000000v009223372036800000000000000000000900000000000000000000000000000000?m9999e ??sudddddddddddddddjokn ?_][?00000000dddd000000000000000000000000000000000000000000000000000000000G00000000000000000000000000000000000000000000575408294?m9999e ??suddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddjoin ?n][?09551615dddd00000000000000000000000000000000000000000000000900000000000009223372036800000000000000000000900000000000009223372?e ??amEnot-join ?U][?023372036854775807?m9999e ??sudddddddddddddjddoin ?_][?000000dddddddddddddddddddddddddddddddddd?00000000d?ddd000000000000000000d?ddd000000000000000000000000K00000000000000000v000009000000000000092233720368000000000000000000009000000000000092000000000000007000000000000000v00000900000000000009223372036800000000000000000000900000000000000000000000000000000?m9999e ??sudddddddddddddddjoin ?_][?00000000dddd000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000999e ??sudddddddddddddddjoin ?_][?00000000dddd00000000000000000000000000000000000dddd0000000000000000000000000000000000000000000000000000000000000000000000000000000000000575408294?m9999e ??suddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddjoin ?n][?00000000dddd00000000000000000000000000000000000000000000000900000000000009223372036800000000000000000000900000000000009223372?e ??amEnot-join ?U][?023372036854775807?m9999e ??sudddddddddddddddjoin ?_][?00000000dddz000000000000000000000000000000000000000000000000000A0000000000000000000000000000000000000000000000000000000000000000000000000000K00000000000000000v009223372036800000000000000000000900000000000000000000000000000000?m9999e ??sudddddddddddddddjoin ?_][?00000000dddd0000000000000000000000000000000000000000000000000000000000000000000000000000000000000575408294?m9999e ??suddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddjoin ?n][?00000000dddd0072036800000000000000000000900000000000000000000000000000000?m9999e ??sudddddddddddddddjoin ?_][?00000000dddd00000000000000000000000000000000000dddd000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007073139687094747134?m9999e ??suame ?navgin]])
147 changes: 147 additions & 0 deletions fuzz/fuzz_targets/datalog_eval.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,8 +1,25 @@
#![no_main]
use libfuzzer_sys::fuzz_target;
use std::collections::HashMap;

/// The facts every input runs against, as the tokens a pattern would use.
const FACTS: [[&str; 3]; 3] = [
[":alice", ":name", "\"Alice\""],
[":bob", ":name", "\"Bob\""],
[":alice", ":age", "30"],
];

/// Inputs whose patterns could join to more rows 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).
if join_rows_bound(s) > MAX_JOIN_ROWS {
return;
}
let db = match minigraf::db::Minigraf::in_memory() {
Ok(db) => db,
Err(_) => return,
Expand All @@ -12,3 +29,133 @@ fuzz_target!(|data: &[u8]| {
let _ = db.execute(s);
}
});

/// An upper estimate of the rows a cross product of the input's patterns yields.
///
/// 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
/// nothing); each group's join is counted against `FACTS`, and the groups multiply.
/// A group with no matches counts as 1, so an empty pattern never hides a cross
/// product that the planner may build before reaching it.
fn join_rows_bound(s: &str) -> u64 {
let patterns = patterns(s);
let mut parent: Vec<usize> = (0..patterns.len()).collect();
let mut owner: HashMap<&str, usize> = HashMap::new();
for (i, p) in patterns.iter().enumerate() {
for &t in p.iter().filter(|t| is_var(t)) {
match owner.get(t) {
Some(&j) => {
let (a, b) = (find(&mut parent, i), find(&mut parent, j));
parent[a] = b;
}
None => {
owner.insert(t, i);
}
}
}
}
let mut groups: HashMap<usize, Vec<[&str; 3]>> = HashMap::new();
for (i, p) in patterns.iter().enumerate() {
let root = find(&mut parent, i);
groups.entry(root).or_default().push(*p);
}
let mut total: u64 = 1;
for group in groups.values() {
let mut rows = 0;
count_join(group, &mut Vec::new(), &mut rows);
total = total.saturating_mul(rows.max(1));
if total > MAX_JOIN_ROWS {
break;
}
}
total
}

/// The first three tokens of every innermost `[...]` holding at least three.
/// Brackets inside string literals are text, not vectors.
fn patterns(s: &str) -> Vec<[&str; 3]> {
let mut out = Vec::new();
let mut start = None;
let (mut in_string, mut escaped) = (false, false);
for (i, ch) in s.char_indices() {
if in_string {
match ch {
_ if escaped => escaped = false,
'\\' => escaped = true,
'"' => in_string = false,
_ => {}
}
continue;
}
match ch {
'"' => in_string = true,
'[' => start = Some(i + 1),
'(' | ')' => start = None,
']' => {
if let Some(from) = start.take() {
let mut tokens = s[from..i].split_whitespace();
if let (Some(e), Some(a), Some(v)) =
(tokens.next(), tokens.next(), tokens.next())
{
out.push([e, a, v]);
}
}
}
_ => {}
}
}
out
}

fn is_wildcard(t: &str) -> bool {
t == "_" || t.starts_with("?_")
}

fn is_var(t: &str) -> bool {
t.starts_with('?') && !is_wildcard(t)
}

fn find(parent: &mut [usize], mut i: usize) -> usize {
while parent[i] != i {
parent[i] = parent[parent[i]];
i = parent[i];
}
i
}

/// Counts the group's join over `FACTS` 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 {
if *rows > MAX_JOIN_ROWS {
return;
}
let mark = bound.len();
let matches = pattern.iter().zip(fact 6FE8 ).all(|(&t, &x)| {
if is_wildcard(t) {
true
} else if is_var(t) {
match bound.iter().find(|(v, _)| *v == t) {
Some(&(_, y)) => y == x,
None => {
bound.push((t, x));
true
}
}
} else {
t == x
}
});
if matches {
count_join(rest, bound, rows);
}
bound.truncate(mark);
}
}
Loading
0