8000 fix(query): float constants match equal floats only (#706) — backport by adityamukho · Pull Request #711 · project-minigraf/minigraf · GitHub
[go: up one dir, main page]

Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
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 CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -9,6 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Fixed

- **A float constant in a pattern matches equal floats only** (#706), backported from v3.0.0. A float written in a pattern's value position, or bound to a `$slot` of a prepared query, matched every stored float within an absolute `f64::EPSILON` (about `2.2e-16`), so `[?e :m/x 0.0]` returned an entity whose `:m/x` is `1e-17`, while `[?e :m/x ?v] [(= ?v 0.0)]` did not. Above 1.0 the epsilon is smaller than the gap between adjacent floats, so only floats smaller than about `2.2e-16` in magnitude were affected: every one of them matched `0.0`, and `1e-20` matched `5e-20`. Float constants now compare by IEEE `==`, as joins, predicates and the indexes do: `0.0` matches `-0.0` and nothing else changes. The fix covers patterns in queries, rule bodies and `not` / `or` bodies. Nothing stored was wrong.
- **WAL entries of more than 1,000,000 facts replay** (#686), backported from v3.0.0. A `transact`, `retract` or `WriteTransaction` commit of more than 1,000,000 facts wrote a WAL entry that replay took as damage: replay stopped there, and the next open cut the WAL off at that entry, so after a crash, kill or close without a checkpoint that transaction and every later one in the WAL were lost, though each had reported success. Replay now takes an entry's fact count as damage only when the bytes after it cannot hold that many facts. A checkpoint before the crash kept the facts. Present since v0.5.0.
- **Prepared queries use the database's rule limits** (#679), backported from v3.0.0. `PreparedQuery::execute` ran a rule query with the default `max_derived_facts` and `max_results` of 1,000,000 whatever `OpenOptions` set, so a lower limit set to stop a runaway recursive rule did not apply to prepared queries, and a higher one set for a large derivation failed with `INT-020` where `execute` of the same query succeeded. It now uses the database's limits, as `execute` does. `:max-derived-facts` and `:max-results` written in the query text were always applied. Present since v0.19.0.

Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -179,7 +179,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint.

## Test Coverage

**1323 tests** (1314 passing, 9 ignored; unit + integration + doc).
**1325 tests** (1316 passing, 9 ignored; unit + integration + doc).
See `docs/TEST_COVERAGE.md` for the full per-file breakdown.

**Testing conventions** — see the Testing Conventions section below before writing any tests.
Expand Down
3 changes: 2 additions & 1 deletion docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@

**Verified**: 2026-10-23 with `cargo test`

**Result**: 1,314 passing tests and 9 ignored tests (1,323 total), including the golden-file corpus (#391)
**Result**: 1,316 passing tests and 9 ignored tests (1,325 total), including the golden-file corpus (#391)

For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617).

Expand Down Expand Up @@ -36,6 +36,7 @@ The v2.0.9 suite covers the public database API, the Datalog engine, storage and
- **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration, WAL replay, checksums, corruption handling, and fault injection.
- **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, also during a checkpoint (`tests/snapshot_atomicity_test.rs`, #554, #555, #558).
- **WAL entries of any size** (`src/wal.rs`, 3 tests, 1 replacing the 1,000,000-fact cap test; #686): an entry of 1,000,001 facts and the entries after it replay, and reopening the writer cuts none of them off; a fact count the bytes after it cannot hold (one more than a quarter of them, or `u64::MAX`) ends replay at that entry, and reopening the writer cuts the WAL off there. A count the bytes could hold whose facts are cut short, at a fact's length or inside its bytes, also ends replay there.
- **Float constants** (`tests/float_constant_test.rs`, 2 tests; #706): a float constant in a pattern, bound to a `$slot`, in a rule body, in a `not` body or in an `=` predicate matches equal floats only (`1e-17` does not match `0.0`, `0.0` matches `-0.0`), in memory, on file before and after a checkpoint and after reopen.
- **Kani proofs of the value encoding** (#627; not `#[test]`s, run by `cargo kani` and `.github/workflows/kani.yml`): 5 harnesses in `src/storage/index/verification.rs` prove, for every input, that `encode_value` (the `value_bytes` of the v7 indexes) writes `Null` as `[0x00]` and each of `Boolean`, `Integer`, `Float` and `Ref` with its own type byte and in its own order (non-NaN floats by IEEE total order, so `-0.0` before `0.0`), and every NaN to the same bytes. Each harness fails when its encoder is broken on purpose. Where NaN sorts is not asserted (#688). Strings, keywords, decoders, fact pages and the WAL are left out: the model checker does not finish on them, so the fuzz and property tests cover them. v3.0.0 adds proofs of its key encoders.
- **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md).
- **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples.
Expand Down
2 changes: 1 addition & 1 deletion src/query/datalog/matcher.rs
Original file line number Diff line number Diff line change
Expand Up @@ -214,7 +214,7 @@ impl PatternMatcher {

EdnValue::Float(f) => {
if let Value::Float(ff) = fact_value {
(f - ff).abs() < f64::EPSILON
f == ff
} else {
false
}
Expand Down
104 changes: 104 additions & 0 deletions tests/float_constant_test.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,104 @@
//! A float constant in a pattern matches equal floats only, by IEEE `==`,
//! as joins and predicates compare them (#706). Before, it matched every
//! float within `f64::EPSILON`, so `0.0` matched `1e-17`.

use minigraf::{BindValue, Minigraf, QueryResult, Value};

fn rows(r: QueryResult) -> Vec<Vec<Value>> {
match r {
QueryResult::QueryResults { results, .. } => results,
_ => panic!("expected QueryResults"),
}
}

fn query(db: &Minigraf, q: &str) -> Vec<Vec<Value>> {
rows(db.execute(&format!("(query {q})")).expect("query"))
}

/// The entity a keyword names, as `edn_to_entity_id` derives it.
fn named(k: &str) -> uuid::Uuid {
uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, k.as_bytes())
}

/// `1e-17`, `0.0` and `-0.0`: the first is within `f64::EPSILON` of the
/// others but equal to neither.
const SMALL_FLOATS: &str =
"(transact [[:tiny :m/x 0.00000000000000001] [:zero :m/x 0.0] [:neg :m/x -0.0]])";

/// The keywords naming the entities in `r`'s first column, sorted.
fn names_of(r: &[Vec<Value>]) -> Vec<&'static str> {
let mut n: Vec<&str> = r
.iter()
.map(|row| {
[":tiny", ":zero", ":neg"]
.into_iter()
.find(|k| matches!(&row[0], Value::Ref(u) if *u == named(k)))
.unwrap_or("?")
})
.collect();
n.sort();
n
}

/// A float constant written in a pattern, bound to a `$slot`, written in a
/// rule or `not` body, or compared by a predicate matches equal floats only.
fn assert_float_constants_exact(db: &Minigraf) {
db.execute("(rule [(zeroish ?e) [?e :m/x 0.0]])").unwrap();
db.execute("(rule [(xval ?e ?v) [?e :m/x ?v]])").unwrap();
for q in [
"[:find ?e :where [?e :m/x 0.0]]",
"[:find ?e :where [?e :m/x -0.0]]",
"[:find ?e :where [?e :m/x ?v] [(= ?v 0.0)]]",
"[:find ?e :where (zeroish ?e)]",
] {
assert_eq!(names_of(&query(db, q)), [":neg", ":zero"], "{q}");
}
// A rule call's literal joins by `Value`'s hash on v2.x, which tells
// `-0.0` from `0.0` (v3.0.0 pairs them, #545); only `1e-17` is checked.
let r = query(db, "[:find ?e :where (xval ?e 0.0)]");
assert_eq!(names_of(&r), [":zero"], "a rule call's float argument");
let r = query(db, "[:find ?e :where (xval ?e 0.00000000000000001)]");
assert_eq!(names_of(&r), [":tiny"], "a rule call's float argument");
for q in [
"[:find ?e :where [?e :m/x 0.00000000000000001]]",
"[:find ?e :where [?e :m/x _] (not [?e :m/x 0.0])]",
"[:find ?e :where [?e :m/x ?v] (not [?e :m/x 0.0] [(< ?v 1.0)])]",
] {
assert_eq!(names_of(&query(db, q)), [":tiny"], "{q}");
}
let r = query(db, "[:find ?e :where [?e :m/x 0.00000000000000002]]");
assert!(r.is_empty(), "2e-17 matches nothing");

let p = db
.prepare("(query [:find ?e :where [?e :m/x $v]])")
.unwrap();
for (v, want) in [(0.0, &[":neg", ":zero"][..]), (1e-17, &[":tiny"][..])] {
let r = rows(
p.execute(&[("v", BindValue::Val(Value::Float(v)))])
.unwrap(),
);
assert_eq!(names_of(&r), want, "bound {v}");
}
}

#[test]
fn float_constant_matches_equal_floats_only() {
let db = Minigraf::in_memory().unwrap();
db.execute(SMALL_FLOATS).unwrap();
assert_float_constants_exact(&db);
}

#[cfg(not(target_arch = "wasm32"))]
#[cfg(not(target_arch = "wasm32"))]
#[test]
fn float_constant_matches_equal_floats_only_after_checkpoint() {
let dir = tempfile::tempdir().unwrap();
let path = dir.path().join("floats.graph");
let db = Minigraf::open(&path).unwrap();
db.execute(SMALL_FLOATS).unwrap();
assert_float_constants_exact(&db);
db.checkpoint().unwrap();
assert_float_constants_exact(&db);
drop(db);
assert_float_constants_exact(&Minigraf::open(&path).unwrap());
}
Loading
0