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
3 changes: 2 additions & 1 deletion CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -49,6 +49,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
- Reopening next to a WAL whose entries were all already checkpointed no longer rewinds the transaction counter, so later transactions no longer reuse `tx_count` values and `:as-of` history stays correct (#447; also fixed in v2.0.3).
- `checkpoint()` removes a WAL whose entries are all already in the file (#457). When it had no facts to flush, it returned early and left the WAL until a later write was checkpointed. That WAL is left by a crash between a checkpoint's commit and its WAL delete, or by a failed delete (`WAL-006`). Its contents were always skipped on replay, so no data was affected; the sidecar file just stayed. Also fixed on the v2.x line (`main`, #540), not yet released.
- Closing a handle opened with `wal_checkpoint_threshold(usize::MAX)` no longer writes its pending facts to the `.graph` file (#476). The sentinel was documented to suppress the close-time checkpoint, and `Minigraf`'s close did skip it, but the storage layer still saved on drop, leaving a WAL whose entries were all checkpointed. The file now stays as the last explicit `checkpoint()` left it, and the WAL keeps every pending fact for the next open to replay, so bulk loaders and benchmarks see the pending WAL they ask for. No data is lost either way. Also fixed on the v2.x line (`main`, #540), not yet released.
- **A query on another thread sees each transaction whole** (#554). A commit wrote its WAL entry, then added the transaction's facts to the in-memory store one fact at a time, each under its own lock, so a query running on another thread could return part of the transaction. `execute("(transact ...)")`, `execute("(retract ...)")` and `WriteTransaction::commit` all did this. They now add the whole transaction under one lock, as does WAL replay. Stored data was never affected. Affected `WriteTransaction` since v0.5.0 and `execute` since v0.6.0.

### Internal

Expand All @@ -72,7 +73,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0

### Known issues

- Same-transaction multi-valued facts can read back as one value (#371, #287), a fact retracted and re-asserted in one `WriteTransaction` is lost at commit (#477), a later assertion does not replace an earlier valid-time window (#435), and `save()` is not crash-atomic (#374); all are fixed in v3.0.0. All v2.x known issues, with affected versions and workarounds, are listed in the pinned issue #421.
- Same-transaction multi-valued facts can read back as one value (#371, #287), a fact retracted and re-asserted in one `WriteTransaction` is lost at commit (#477), a later assertion does not replace an earlier valid-time window (#435), and `save()` is not crash-atomic (#374); all are fixed in v3.0.0. The patterns of one query can read different database states while another thread commits (#555); not yet fixed. All v2.x known issues, with affected versions and workarounds, are listed in the pinned issue #421.

## v2.0.4 — 2026-10-08

Expand Down
2 changes: 1 addition & 1 deletion CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -201,7 +201,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are

## Test Coverage

**1432 tests** (1422 passing, 10 ignored; unit + integration + doc).
**1440 tests** (1427 passing, 13 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
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1432 tests
cargo test # run 1440 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
7 changes: 4 additions & 3 deletions docs/TEST_COVERAGE.md

Large diffs are not rendered by default.

11 changes: 5 additions & 6 deletions src/browser/mod.rs
Original file line number Diff line number Diff line change
Expand Up @@ -343,12 +343,11 @@ impl BrowserDb {
})
.collect();

for fact in &stamped {
inner
.fact_storage
.load_fact(fact.clone())
.map_err(|e| JsValue::from_str(&e.to_string()))?;
}
// One batch, so no query sees part of the transaction (#554).
inner
.fact_storage
.load_facts(stamped)
.map_err(|e| JsValue::from_str(&e.to_string()))?;

inner.pfs.mark_dirty();
inner
Expand Down
18 changes: 7 additions & 11 deletions src/db.rs
Original file line number Diff line number Diff line change
Expand Up @@ -630,9 +630,7 @@ impl Minigraf {
// Already present in the main file; skip.
continue;
}
for fact in &entry.facts {
let _ = fact_storage.load_fact(fact.clone())?;
}
let _ = fact_storage.load_facts(entry.facts.iter().cloned())?;
#[allow(clippy::arithmetic_side_effects)]
{
replayed += 1;
Expand Down Expand Up @@ -756,10 +754,9 @@ impl Minigraf {
&stamped,
)?;

// WAL succeeded — now apply facts to shared FactStorage.
for fact in &stamped {
let _ = self.inner.fact_storage.load_fact(fact.clone())?;
}
// WAL succeeded — now apply facts to shared FactStorage, in one
// batch so no query sees part of the transaction (#554).
let _ = self.inner.fact_storage.load_facts(stamped)?;

// Trigger auto-checkpoint AFTER facts are in FactStorage so the
// checkpoint captures the newly written facts. An open fact log
Expand Down Expand Up @@ -1591,10 +1588,9 @@ impl<'a> WriteTransaction<'a> {
&stamped,
)?;

// WAL succeeded — now apply facts to shared FactStorage.
for fact in stamped {
let _ = self.inner.fact_storage.load_fact(fact)?;
}
// WAL succeeded — now apply facts to shared FactStorage, in one
// batch so no query sees part of the transaction (#554).
let _ = self.inner.fact_storage.load_facts(stamped)?;

// Trigger auto-checkpoint AFTER facts are in FactStorage so the
// checkpoint captures the newly written facts. An open fact log
Expand Down
49 changes: 49 additions & 0 deletions src/graph/storage.rs
Original file line number Diff line number Diff line change
Expand Up @@ -309,6 +309,29 @@ impl FactStorage {
Ok(true)
}

/// Insert facts with their tx_id and tx_count preserved, all under one
/// write lock, so a query sees either none of them or all of them (#554).
///
/// Commits and WAL replay use this for a whole transaction. Duplicates are
/// skipped as in [`Self::load_fact`]. Returns how many facts were loaded.
pub(crate) fn load_facts(&self, facts: impl IntoIterator<Item = Fact>) -> Result<usize> {
let mut d = self
.data
.write()
.map_err(|_| err_coded!(ErrorCode::Int050, "data"))?;
let mut loaded = 0usize;
for fact in facts {
if !d.pending_keys.insert(pending_key(&fact)) {
continue;
}
let pos = d.facts.len();
d.pending_indexes.insert(&fact, pos);
d.facts.push(fact);
loaded = loaded.saturating_add(1);
}
Ok(loaded)
}

/// Raise tx_counter to max(tx_count) across all loaded facts.
///
/// Must be called after all `load_fact()` calls complete so that the next
Expand Down Expand Up @@ -1641,6 +1664,32 @@ mod tests {
assert_eq!(storage.fact_count(), 2);
}

#[test]
fn load_facts_appends_a_batch_and_skips_duplicates() {
let storage = FactStorage::new();
let a = Fact::new(
uuid::Uuid::new_v4(),
":t/a".to_string(),
Value::Integer(1),
1,
);
let b = Fact::new(
uuid::Uuid::new_v4(),
":t/a".to_string(),
Value::Integer(2),
1,
);
assert_eq!(
storage
.load_facts(vec![a.clone(), b.clone(), a.clone()])
.unwrap(),
2
);
assert_eq!(storage.fact_count(), 2);
assert_eq!(storage.load_facts(vec![b]).unwrap(), 0);
assert_eq!(storage.fact_count(), 2);
}

#[test]
fn test_load_fact_duplicate_detection_includes_asserted() {
let storage = FactStorage::new();
Expand Down
4 changes: 1 addition & 3 deletions src/storage/persistent_facts.rs
Original file line number Diff line number Diff line change
Expand Up @@ -163,9 +163,7 @@ impl<B: StorageBackend + 'static> PersistentFactStorage<B> {
let max_tx = max_fact_tx.max(header.last_checkpointed_tx_count);
// Pending facts are kept in tx order (the fact log relies on it).
facts.sort_by_key(|f| f.tx_count);
for fact in facts {
let _ = self.storage.load_fact(fact)?;
}
let _ = self.storage.load_facts(facts)?;
Ok(MetaPage {
last_checkpointed_tx_count: max_tx,
..MetaPage::empty(1)
Expand Down
199 changes: 199 additions & 0 deletions tests/snapshot_atomicity_test.rs
Original file line number Diff line number Diff line change
@@ -0,0 +1,199 @@
//! Reproducers: a query must see each transaction whole, and each fact once,
//! while other threads commit and checkpoint (#473 spec §2 and §4.1).
//!
//! Each test runs a writer thread against a reader thread for a fixed time and
//! fails on the first answer that breaks the invariant.
#![cfg(not(target_arch = "wasm32"))]

use minigraf::{Minigraf, OpenOptions, QueryResult};
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;
use std::time::{Duration, Instant};

const RUN_FOR: Duration = Duration::from_secs(3);

fn rows(db: &Minigraf, query: &str) -> Vec<Vec<String>> {
match db.execute(query).unwrap() {
QueryResult::QueryResults { results, .. } => results
.iter()
.map(|r| {
r.iter()
.map(|v| match v {
minigraf::Value::Integer(n) => n.to_string(),
minigraf::Value::Keyword(k) => k.clone(),
minigraf::Value::String(s) => s.clone(),
_ => "other".to_string(),
})
.collect()
})
.collect(),
_ => panic!("expected query results"),
}
}

/// Runs `write` in a loop on one thread and `check` in a loop on this one
/// until `RUN_FOR` passes. `check` returns an error message on a violation.
fn race(
db: Arc<Minigraf>,
mut write: impl FnMut(&Minigraf, u64) + Send + 'static,
mut check: impl FnMut(&Minigraf) -> Option<String>,
) -> Option<String> {
let stop = Arc::new(AtomicBool::new(false));
let writer = {
let (db, stop) = (Arc::clone(&db), Arc::clone(&stop));
thread::spawn(move || {
let mut i = 0;
while !stop.load(Ordering::Relaxed) {
write(&db, i);
i += 1;
}
})
};
let start = Instant::now();
let mut found = None;
while start.elapsed() < RUN_FOR {
if let Some(msg) = check(&db) {
found = Some(msg);
break;
}
}
stop.store(true, Ordering::Relaxed);
writer.join().unwrap();
found
}

const N: u64 = 500;

fn batch(i: u64) -> String {
let facts: String = (0..N)
.map(|j| format!("[:b{i}x{j} :batch/id {i}]"))
.collect();
format!("(transact [{facts}])")
}

/// Every write commits `N` facts in one transaction; a query must never see
/// a count that is not a multiple of `N` (#554).
fn commit_is_seen_whole(db: Minigraf, write: impl FnMut(&Minigraf, u64) + Send + 'static) {
let found = race(Arc::new(db), write, |db| {
let n = rows(db, "(query [:find ?e :where [?e :batch/id ?b]])").len() as u64;
(n % N != 0).then(|| format!("saw {n} facts, not a multiple of {N}"))
});
if let Some(msg) = found {
panic!("partial transaction visible: {msg}");
}
}

fn write_transaction(db: &Minigraf, i: u64) {
let mut tx = db.begin_write().unwrap();
tx.execute(&batch(i)).unwrap();
tx.commit().unwrap();
}

fn execute_transact(db: &Minigraf, i: u64) {
db.execute(&batch(i)).unwrap();
}

fn file_db(dir: &tempfile::TempDir) -> Minigraf {
let opts = OpenOptions::default().wal_checkpoint_threshold(usize::MAX);
Minigraf::open_with_options(dir.path().join("w.graph"), opts).unwrap()
}

#[test]
fn write_transaction_commit_is_seen_whole_in_memory() {
commit_is_seen_whole(Minigraf::in_memory().unwrap(), write_transaction);
}

#[test]
fn write_transaction_commit_is_seen_whole_on_file() {
let dir = tempfile::tempdir().unwrap();
commit_is_seen_whole(file_db(&dir), write_transaction);
}

#[test]
fn execute_transact_is_seen_whole_in_memory() {
commit_is_seen_whole(Minigraf::in_memory().unwrap(), execute_transact);
}

#[test]
fn execute_transact_is_seen_whole_on_file() {
let dir = tempfile::tempdir().unwrap();
commit_is_seen_whole(file_db(&dir), execute_transact);
}

/// A checkpoint sets the new committed reader and clears the pending store
/// under two separate locks, so a query in between can read the checkpointed
/// facts twice. Every fact here has its own entity, so a repeated row is a
/// fact read twice.
#[test]
#[ignore = "reproducer: fails on v3 today; fixed by #473 sub-issue #543"]
fn checkpoint_never_shows_a_fact_twice() {
let dir = tempfile::tempdir().unwrap();
let opts = OpenOptions::default().wal_checkpoint_threshold(usize::MAX);
let db = Minigraf::open_with_options(dir.path().join("c.graph"), opts).unwrap();
let found = race(
Arc::new(db),
|db, i| {
db.execute(&format!("(transact [[:c{i} :ck/n {i}]])"))
.unwrap();
db.checkpoint().unwrap();
},
|db| {
for q in [
"(query [:find ?e ?n :where [?e :ck/n ?n]])",
"(query [:find ?e ?n :valid-at :any-valid-time :where [?e :ck/n ?n]])",
] {
let mut r = rows(db, q);
let n = r.len();
r.sort();
r.dedup();
if r.len() != n {
return Some(format!("{n} rows, {} distinct: {q}", r.len()));
}
}
None
},
);
if let Some(msg) = found {
panic!("fact seen twice during a checkpoint: {msg}");
}
}

/// A query fetches each attribute with its own `get_live_facts` call, each
/// under its own read lock, so a transaction that commits between the two
/// calls is seen by one pattern and not the other. Every transaction writes
/// `:pair/x` and `:pair/y` for one entity together.
fn patterns_see_one_state(db: Minigraf) {
let found = race(
Arc::new(db),
|db, i| {
db.execute(&format!(
"(transact [[:p{i} :pair/x {i}] [:p{i} :pair/y {i}]])"
))
.unwrap();
},
|db| {
let r = rows(
db,
"(query [:find ?e :where [?e :pair/x ?x] (not [?e :pair/y ?x])])",
);
(!r.is_empty()).then(|| format!("{} entities with x but no y", r.len()))
},
);
if let Some(msg) = found {
panic!("one query saw two database states: {msg}");
}
}

#[test]
#[ignore = "reproducer for #555: fails on v3 today"]
fn patterns_of_one_query_see_one_state_in_memory() {
patterns_see_one_state(Minigraf::in_memory().unwrap());
}

#[test]
#[ignore = "reproducer for #555: fails on v3 today"]
fn patterns_of_one_query_see_one_state_on_file() {
let dir = tempfile::tempdir().unwrap();
patterns_see_one_state(Minigraf::open(dir.path().join("p.graph")).unwrap());
}
Loading