diff --git a/.github/workflows/coverage-gates.yml b/.github/workflows/coverage-gates.yml new file mode 100644 index 0000000000..4a4dc81f0d --- /dev/null +++ b/.github/workflows/coverage-gates.yml @@ -0,0 +1,57 @@ +name: Coverage Gates + +on: + push: + branches: ["main"] + pull_request: + branches: ["main"] + +permissions: + contents: read + +jobs: + coverage-gates: + name: Per-module coverage gates + runs-on: ubuntu-latest + + steps: + - uses: actions/checkout@v4 + + - name: Install Rust stable + uses: dtolnay/rust-toolchain@stable + with: + components: llvm-tools-preview + + - name: Install cargo-llvm-cov + uses: taiki-e/install-action@cargo-llvm-cov + + - name: Generate coverage (text) + run: cargo llvm-cov --text 2>&1 > cov_text.txt || true + + - name: Check per-module thresholds + run: | + FAIL=0 + check_module() { + local file=$1 threshold=$2 + local pct + pct=$(grep "$file" cov_text.txt | grep -oP '\d+\.\d+(?=%)' | tail -1) + if [ -z "$pct" ]; then + echo "WARNING: $file not found in coverage report" + return 0 + fi + if python3 -c "import sys; sys.exit(0 if float('$pct') >= $threshold else 1)"; then + echo "OK: $file: ${pct}% >= ${threshold}%" + else + echo "FAIL: $file: ${pct}% < ${threshold}%" + return 1 + fi + } + # Thresholds from coverage-thresholds.toml + check_module "wal.rs" 75 || FAIL=1 + check_module "db.rs" 70 || FAIL=1 + check_module "persistent_facts" 70 || FAIL=1 + check_module "btree_v6" 65 || FAIL=1 + check_module "executor.rs" 75 || FAIL=1 + check_module "evaluator.rs" 75 || FAIL=1 + check_module "stratification" 75 || FAIL=1 + exit $FAIL diff --git a/.github/workflows/fuzz.yml b/.github/workflows/fuzz.yml new file mode 100644 index 0000000000..ee4a737d49 --- /dev/null +++ b/.github/workflows/fuzz.yml @@ -0,0 +1,48 @@ +name: Fuzz (nightly) + +on: + schedule: + - cron: "0 4 * * *" + workflow_dispatch: + +permissions: + contents: read + +jobs: + fuzz: + name: Fuzz targets + runs-on: ubuntu-latest + timeout-minutes: 30 + + steps: + - uses: actions/checkout@v4 + + - name: Install Rust nightly + uses: dtolnay/rust-toolchain@nightly + + - name: Install cargo-fuzz + run: cargo install cargo-fuzz + + - name: Fuzz wal_entry (60s) + run: cargo fuzz run wal_entry -- -max_total_time=60 + continue-on-error: false + + - name: Fuzz file_header (60s) + run: cargo fuzz run file_header -- -max_total_time=60 + continue-on-error: false + + - name: Fuzz fact_page (60s) + run: cargo fuzz run fact_page -- -max_total_time=60 + continue-on-error: false + + - name: Fuzz btree_page (60s) + run: cargo fuzz run btree_page -- -max_total_time=60 + continue-on-error: false + + - name: Fuzz datalog_parser (60s) + run: cargo fuzz run datalog_parser -- -max_total_time=60 + continue-on-error: false + + - name: Fuzz datalog_eval (60s) + run: cargo fuzz run datalog_eval -- -max_total_time=60 + continue-on-error: false diff --git a/Cargo.toml b/Cargo.toml index 3675bbe7ca..f5a1e1e602 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -75,6 +75,7 @@ tempfile = "3" criterion = { version = "0.8", features = ["html_reports"] } wide = "0.7" proptest = "1" +uuid = { version = "1.0", features = ["v4", "v5"] } [target.'cfg(all(target_arch = "wasm32", not(target_os = "wasi")))'.dev-dependencies] wasm-bindgen-test = "0.3" diff --git a/coverage-thresholds.toml b/coverage-thresholds.toml new file mode 100644 index 0000000000..257aac5e01 --- /dev/null +++ b/coverage-thresholds.toml @@ -0,0 +1,12 @@ +# Coverage thresholds for critical reliability modules. +# Set at Wave 3 completion — ratchet upward in future waves. +# Update by running: cargo llvm-cov --text 2>&1 | grep + +[modules] +"src/wal.rs" = 75 +"src/db.rs" = 70 +"src/storage/persistent_facts.rs" = 70 +"src/storage/btree_v6.rs" = 65 +"src/query/datalog/executor.rs" = 75 +"src/query/datalog/evaluator.rs" = 75 +"src/query/datalog/stratification.rs" = 75 diff --git a/fuzz/corpus/datalog_eval/seed_basic.txt b/fuzz/corpus/datalog_eval/seed_basic.txt new file mode 100644 index 0000000000..297359df20 --- /dev/null +++ b/fuzz/corpus/datalog_eval/seed_basic.txt @@ -0,0 +1 @@ +(query [:find ?n :where [?e :name ?n]]) diff --git a/fuzz/corpus/datalog_eval/seed_not_join.txt b/fuzz/corpus/datalog_eval/seed_not_join.txt new file mode 100644 index 0000000000..659fa44830 --- /dev/null +++ b/fuzz/corpus/datalog_eval/seed_not_join.txt @@ -0,0 +1 @@ +(query [:find ?e :where [?e :color ?c] (not-join [?e] [?e :active true])]) diff --git a/fuzz/corpus/datalog_eval/seed_predicate.txt b/fuzz/corpus/datalog_eval/seed_predicate.txt new file mode 100644 index 0000000000..c1d130fa10 --- /dev/null +++ b/fuzz/corpus/datalog_eval/seed_predicate.txt @@ -0,0 +1 @@ +(query [:find ?n :where [?e :name ?n] [(= ?n "Alice")]]) diff --git a/fuzz/corpus/datalog_eval/seed_temporal.txt b/fuzz/corpus/datalog_eval/seed_temporal.txt new file mode 100644 index 0000000000..6295b0aa15 --- /dev/null +++ b/fuzz/corpus/datalog_eval/seed_temporal.txt @@ -0,0 +1 @@ +(query [:find ?n :where [?e :name ?n]] :as-of 1) diff --git a/fuzz/corpus/datalog_parser/seed_agg.txt b/fuzz/corpus/datalog_parser/seed_agg.txt new file mode 100644 index 0000000000..2bb50ed9c0 --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_agg.txt @@ -0,0 +1 @@ +(query [:find (count ?e) :where [?e :name ?n]]) diff --git a/fuzz/corpus/datalog_parser/seed_empty.txt b/fuzz/corpus/datalog_parser/seed_empty.txt new file mode 100644 index 0000000000..8b13789179 --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_empty.txt @@ -0,0 +1 @@ + diff --git a/fuzz/corpus/datalog_parser/seed_not.txt b/fuzz/corpus/datalog_parser/seed_not.txt new file mode 100644 index 0000000000..9ecbf126bd --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_not.txt @@ -0,0 +1 @@ +(query [:find ?e :where [?e :name ?n] (not [?e :banned true])]) diff --git a/fuzz/corpus/datalog_parser/seed_query.txt b/fuzz/corpus/datalog_parser/seed_query.txt new file mode 100644 index 0000000000..8aa1b226be --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_query.txt @@ -0,0 +1 @@ +(query [:find ?e :where [?e :name ?n]]) diff --git a/fuzz/corpus/datalog_parser/seed_retract.txt b/fuzz/corpus/datalog_parser/seed_retract.txt new file mode 100644 index 0000000000..7cad0c39ef --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_retract.txt @@ -0,0 +1 @@ +(retract [[:alice :name "Alice"]]) diff --git a/fuzz/corpus/datalog_parser/seed_rule.txt b/fuzz/corpus/datalog_parser/seed_rule.txt new file mode 100644 index 0000000000..3701ed964a --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_rule.txt @@ -0,0 +1 @@ +(rule [(parent ?x ?y) [?x :parent ?y]]) diff --git a/fuzz/corpus/datalog_parser/seed_transact.txt b/fuzz/corpus/datalog_parser/seed_transact.txt new file mode 100644 index 0000000000..5e4992f845 --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_transact.txt @@ -0,0 +1 @@ +(transact [[:e1 :name "Alice"]]) diff --git a/fuzz/corpus/datalog_parser/seed_truncated.txt b/fuzz/corpus/datalog_parser/seed_truncated.txt new file mode 100644 index 0000000000..465aefc19f --- /dev/null +++ b/fuzz/corpus/datalog_parser/seed_truncated.txt @@ -0,0 +1 @@ +(query [:find ?e \ No newline at end of file diff --git a/fuzz/fuzz_targets/datalog_eval.rs b/fuzz/fuzz_targets/datalog_eval.rs index af778b99a4..54c0a94099 100644 --- a/fuzz/fuzz_targets/datalog_eval.rs +++ b/fuzz/fuzz_targets/datalog_eval.rs @@ -1,6 +1,14 @@ #![no_main] use libfuzzer_sys::fuzz_target; -fuzz_target!(|_data: &[u8]| { - // Stub — implemented in Wave 3 PR 2 +fuzz_target!(|data: &[u8]| { + if let Ok(s) = std::str::from_utf8(data) { + let db = match minigraf::db::Minigraf::in_memory() { + Ok(db) => db, + Err(_) => return, + }; + let _ = db + .execute(r#"(transact [[:alice :name "Alice"] [:bob :name "Bob"] [:alice :age 30]])"#); + let _ = db.execute(s); + } }); diff --git a/fuzz/fuzz_targets/datalog_parser.rs b/fuzz/fuzz_targets/datalog_parser.rs index af778b99a4..da97622a0f 100644 --- a/fuzz/fuzz_targets/datalog_parser.rs +++ b/fuzz/fuzz_targets/datalog_parser.rs @@ -1,6 +1,12 @@ #![no_main] use libfuzzer_sys::fuzz_target; -fuzz_target!(|_data: &[u8]| { - // Stub — implemented in Wave 3 PR 2 +fuzz_target!(|data: &[u8]| { + if let Ok(s) = std::str::from_utf8(data) { + let db = match minigraf::db::Minigraf::in_memory() { + Ok(db) => db, + Err(_) => return, + }; + let _ = db.execute(s); + } }); diff --git a/tests/property_test.proptest-regressions b/tests/property_test.proptest-regressions new file mode 100644 index 0000000000..8217048bf5 --- /dev/null +++ b/tests/property_test.proptest-regressions @@ -0,0 +1,8 @@ +# Seeds for failure cases proptest has generated in the past. It is +# automatically read and these particular cases re-run before any +# novel cases are generated. +# +# It is recommended to check this file in to source control so that +# everyone who runs the test benefits from these saved cases. +cc 06842cd54e6438a54a2509966aa47b3763aa08b4daccf7953647c16767de6703 # shrinks to facts = [TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }] +cc 0cb2c60faac9ad670ed1b43ec1d56273127b4c442301d0425c859ef704510102 # shrinks to facts = [TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }, TestFact { entity: 0, attribute: ":color", value: Str("red") }] diff --git a/tests/property_test.rs b/tests/property_test.rs new file mode 100644 index 0000000000..96bbc48de3 --- /dev/null +++ b/tests/property_test.rs @@ -0,0 +1,218 @@ +//! Cross-feature property tests (#221). +//! +//! Compares Minigraf query results against a deliberately simple reference +//! evaluator for randomly-generated small graphs. +//! +//! Run: cargo test --test property_test +//! More cases: PROPTEST_CASES=500 cargo test --test property_test +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::QueryResult; +use minigraf::db::Minigraf; +use proptest::prelude::*; +use uuid::Uuid; + +#[derive(Debug, Clone)] +struct TestFact { + entity: usize, + attribute: String, + value: TestValue, +} + +#[derive(Debug, Clone, PartialEq)] +enum TestValue { + Str(String), + Int(i64), + Bool(bool), +} + +impl TestValue { + fn to_edn(&self) -> String { + match self { + TestValue::Str(s) => format!(r#""{s}""#), + TestValue::Int(n) => n.to_string(), + TestValue::Bool(b) => b.to_string(), + } + } +} + +#[derive(Debug, Clone)] +struct TestQuery { + attribute: String, + value_filter: Option, + negation_attr: Option, +} + +/// Compute the deterministic UUID for a keyword entity (mirrors `edn_to_entity_id`). +fn entity_uuid(idx: usize) -> Uuid { + let kw = format!(":e{idx}"); + Uuid::new_v5(&Uuid::NAMESPACE_OID, kw.as_bytes()) +} + +// ── Reference evaluator (naive, independent of production code) ─────────────── + +fn ref_eval(facts: &[TestFact], query: &TestQuery) -> Vec { + let mut matched: Vec = facts + .iter() + .filter(|f| { + f.attribute == query.attribute + && match &query.value_filter { + None => true, + Some(v) => &f.value == v, + } + }) + .map(|f| f.entity) + .collect(); + + if let Some(neg_attr) = &query.negation_attr { + let neg_entities: std::collections::HashSet = facts + .iter() + .filter(|f| &f.attribute == neg_attr) + .map(|f| f.entity) + .collect(); + matched.retain(|e| !neg_entities.contains(e)); + } + + matched.sort(); + matched.dedup(); + matched +} + +// ── Minigraf evaluator ──────────────────────────────────────────────────────── + +fn minigraf_eval(facts: &[TestFact], query: &TestQuery, max_entity: usize) -> Vec { + // Pre-compute UUID → index mapping for all possible entity indices. + let uuid_to_idx: std::collections::HashMap = + (0..max_entity).map(|i| (entity_uuid(i), i)).collect(); + + let db = Minigraf::in_memory().unwrap(); + + for fact in facts { + let entity_kw = format!(":e{}", fact.entity); + let val_edn = fact.value.to_edn(); + let attr = &fact.attribute; + let edn = format!(r#"(transact [[{entity_kw} {attr} {val_edn}]])"#); + let _ = db.execute(&edn); + } + + let val_clause = match &query.value_filter { + Some(v) => format!(" [(= ?v {})]", v.to_edn()), + None => String::new(), + }; + + let neg_clause = match &query.negation_attr { + Some(neg) => format!(" (not [?e {} _])", neg), + None => String::new(), + }; + + let attr = &query.attribute; + let datalog = format!("(query [:find ?e :where [?e {attr} ?v]{val_clause}{neg_clause}])"); + + let result = db.execute(&datalog); + // Skip test cases where the generated query fails to parse/evaluate. + if result.is_err() { + return vec![]; + } + match result.unwrap() { + QueryResult::QueryResults { results, .. } => { + let mut entities: Vec = results + .into_iter() + .flat_map(|r| r.into_iter()) + .filter_map(|v| match v { + minigraf::Value::Ref(uuid) => uuid_to_idx.get(&uuid).copied(), + _ => None, + }) + .collect(); + entities.sort(); + entities.dedup(); + entities + } + _ => vec![], + } +} + +// ── proptest generators ─────────────────────────────────────────────────────── + +fn arb_attribute() -> impl Strategy { + prop_oneof![ + Just(":color".to_string()), + Just(":size".to_string()), + Just(":active".to_string()), + Just(":tag".to_string()), + Just(":score".to_string()), + ] +} + +fn arb_value() -> impl Strategy { + prop_oneof![ + Just(TestValue::Str("red".to_string())), + Just(TestValue::Str("blue".to_string())), + Just(TestValue::Int(1)), + Just(TestValue::Int(2)), + Just(TestValue::Bool(true)), + ] +} + +fn arb_fact(max_entity: usize) -> impl Strategy { + (0..max_entity, arb_attribute(), arb_value()).prop_map(|(entity, attribute, value)| TestFact { + entity, + attribute, + value, + }) +} + +proptest! { + /// Minigraf results must match the reference evaluator for basic queries. + #[test] + fn basic_query_matches_reference(facts in prop::collection::vec(arb_fact(8), 3..20)) { + let query = TestQuery { + attribute: ":color".to_string(), + value_filter: None, + negation_attr: None, + }; + let ref_result = ref_eval(&facts, &query); + let mg_result = minigraf_eval(&facts, &query, 8); + prop_assert_eq!(ref_result, mg_result); + } + + /// Negation: entities with negation_attr must not appear in results. + #[test] + fn negation_excludes_correct_entities(facts in prop::collection::vec(arb_fact(8), 3..20)) { + let query = TestQuery { + attribute: ":color".to_string(), + value_filter: None, + negation_attr: Some(":active".to_string()), + }; + let ref_result = ref_eval(&facts, &query); + let mg_result = minigraf_eval(&facts, &query, 8); + + let neg_entities: std::collections::HashSet = facts + .iter() + .filter(|f| f.attribute == ":active") + .map(|f| f.entity) + .collect(); + + for &e in &mg_result { + prop_assert!( + !neg_entities.contains(&e), + "entity {} has negated attribute but appears in result", + e + ); + } + prop_assert_eq!(ref_result, mg_result); + } + + /// Impossible paths return empty results. + #[test] + fn impossible_path_returns_empty(facts in prop::collection::vec(arb_fact(8), 3..20)) { + let query = TestQuery { + attribute: ":__nonexistent__".to_string(), + value_filter: None, + negation_attr: None, + }; + let ref_result = ref_eval(&facts, &query); + let mg_result = minigraf_eval(&facts, &query, 8); + prop_assert!(ref_result.is_empty(), "reference: impossible path must be empty"); + prop_assert!(mg_result.is_empty(), "minigraf: impossible path must be empty"); + } +}