From 9b979c03a57a6400c7e2e46f0aaf117ea14e7060 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 3 Apr 2026 09:31:51 +0530 Subject: [PATCH] fix(types): replace pointer-address Ord with discriminant-based Ord for Value MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Value::Ord's cross-variant fallthrough compared stack-frame pointer addresses, which is non-deterministic across call contexts and violates Rust's Ord contract (BTreeMap/BTreeSet require a consistent total order). This caused incorrect aggregation grouping (PR #71) and wrong OR/OrJoin deduplication (PR #68). Fix: use a stable u8 discriminant per variant for cross-variant ordering. Also fix the O(n²) Vec::contains deduplication in count-distinct and sum-distinct (issue #50, which PR #66 claimed to fix but did not): replace with BTreeSet, which is now safe because Value::Ord is a correct total order. Adds two regression tests: - value_ord_cross_variant_is_antisymmetric: proves the old code violated antisymmetry (cmp(a,b) must equal reverse(cmp(b,a))) - value_ord_cross_variant_is_stable: cross-variant ordering must depend only on the variant type, not the inner value Co-Authored-By: Claude Sonnet 4.6 --- src/graph/types.rs | 74 +++++++++++++++++++++++++++++++--- src/query/datalog/functions.rs | 19 +++------ 2 files changed, 75 insertions(+), 18 deletions(-) diff --git a/src/graph/types.rs b/src/graph/types.rs index 10e182b895..ae8cd6d588 100644 --- a/src/graph/types.rs +++ b/src/graph/types.rs @@ -90,12 +90,23 @@ impl Ord for Value { (Value::Ref(a), Value::Ref(b)) => a.cmp(b), (Value::Keyword(a), Value::Keyword(b)) => a.cmp(b), (Value::Null, Value::Null) => std::cmp::Ordering::Equal, - // Different variants - order by discriminant + // Different variants — order by a stable integer discriminant so + // the total order is deterministic and does not depend on stack + // addresses (the previous implementation used pointer values here, + // which are non-deterministic and violate Ord's contract). _ => { - // Use pointers to get consistent ordering between variants - let self_ptr = self as *const Value as usize; - let other_ptr = other as *const Value as usize; - self_ptr.cmp(&other_ptr) + fn discriminant(v: &Value) -> u8 { + match v { + Value::String(_) => 0, + Value::Integer(_) => 1, + Value::Float(_) => 2, + Value::Boolean(_) => 3, + Value::Ref(_) => 4, + Value::Keyword(_) => 5, + Value::Null => 6, + } + } + discriminant(self).cmp(&discriminant(other)) } } } @@ -593,4 +604,57 @@ mod tests { assert!(opts.valid_from.is_none()); assert!(opts.valid_to.is_none()); } + + // Helper used by the cross-variant Ord tests: moves values into a fresh + // stack frame so the two parameters are always at distinct, consistent + // addresses independent of the call site. + fn cmp_values(a: Value, b: Value) -> std::cmp::Ordering { + a.cmp(&b) + } + + #[test] + fn value_ord_cross_variant_is_antisymmetric() { + // The pointer-address bug causes both cmp_values(A, B) and + // cmp_values(B, A) to return the same ordering (whichever parameter + // slot has the lower address "wins" in both calls), violating the + // antisymmetry requirement for Ord: cmp(a,b) must equal reverse(cmp(b,a)). + let pairs: &[(Value, Value)] = &[ + (Value::String("hello".into()), Value::Integer(42)), + (Value::Integer(1), Value::Float(1.0)), + (Value::Boolean(true), Value::Null), + (Value::Keyword(":k".into()), Value::String("x".into())), + ]; + for (a, b) in pairs { + let forward = cmp_values(a.clone(), b.clone()); + let backward = cmp_values(b.clone(), a.clone()); + assert_eq!( + forward, + backward.reverse(), + "Value::Ord cross-variant comparison must be antisymmetric" + ); + assert_ne!( + forward, + std::cmp::Ordering::Equal, + "Values of different types must not compare as Equal" + ); + } + } + + #[test] + fn value_ord_cross_variant_is_stable() { + // Ordering between two fixed variant types must be stable: it should + // not depend on what the inner value is, only on which variant it is. + // With the pointer-address bug every allocation is at a different + // address, so this constraint can be violated non-deterministically. + let string_lt_integer = cmp_values(Value::String("a".into()), Value::Integer(0)); + for s in ["", "z", "hello world"] { + for i in [i64::MIN, 0, i64::MAX] { + let result = cmp_values(Value::String(s.into()), Value::Integer(i)); + assert_eq!( + result, string_lt_integer, + "Cross-variant ordering must depend only on the variant, not the inner value" + ); + } + } + } } diff --git a/src/query/datalog/functions.rs b/src/query/datalog/functions.rs index 3567859213..b0c366ee3d 100644 --- a/src/query/datalog/functions.rs +++ b/src/query/datalog/functions.rs @@ -376,24 +376,17 @@ pub fn apply_builtin_aggregate(name: &str, values: &[&Value]) -> anyhow::Result< "count" => Ok(Value::Integer(values.len() as i64)), "count-distinct" => { - let mut seen: Vec<&Value> = Vec::new(); - for v in values { - if !seen.contains(v) { - seen.push(v); - } - } + // O(n log n) via BTreeSet — Value::Ord is a stable discriminant-based + // total order so BTreeSet membership is correct. + let seen: std::collections::BTreeSet<&Value> = values.iter().copied().collect(); Ok(Value::Integer(seen.len() as i64)) } "sum" | "sum-distinct" => { let deduped: Vec<&Value> = if name == "sum-distinct" { - let mut seen: Vec<&Value> = Vec::new(); - for v in values { - if !seen.contains(v) { - seen.push(v); - } - } - seen + // O(n log n) via BTreeSet (same rationale as count-distinct). + let seen: std::collections::BTreeSet<&Value> = values.iter().copied().collect(); + seen.into_iter().collect() } else { values.to_vec() };