From d029a2adef974d18d16db2d41c0603d67d41fd9c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 10 Oct 2026 15:16:30 +0530 Subject: [PATCH 1/2] test: drive faults through the whole save/WAL/recovery path; never retry a failed checkpoint (#390) A test-only, thread-local fault plan (src/storage/fault.rs) is asked before every write and sync of FileBackend, the WAL (header, entries, torn-tail cut, removal) and sync_parent_dir. It fails the k-th write or sync with EIO, a short or torn write, a full disk that keeps failing later writes, a failed fsync, or a failed fsync that also loses the writes since the last good one (FileBackend keeps pre-images while a plan is armed; the WAL is cut back to its last synced length). src/fault_matrix.rs runs each fault at every call index of a transact, a WAL-creating transact, an automatic checkpoint, checkpoint(), the close-time checkpoint and rebuild_indexes(), then kills the handle and reopens: the facts are exactly the handle's, plus the failed transaction whole or not at all; verify is clean; a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint, and retry a checkpoint whose meta fsync failed, crashing at each write. Decision (written down in ERROR_REFERENCE and Minigraf::checkpoint): a checkpoint that failed after it may have written is never retried on the same handle. PersistentFactStorage sets `failed` before its first write and clears it on success; while set, save and rebuild_indexes return the new STG-046, writes are refused before they take a tx_count, and the close-time save is skipped. Without this, the retry test reopens to STG-029: the retried checkpoint overwrote pages the on-disk meta of the "failed" one referenced. A rebuild refused with STG-041 writes nothing and does not set it. The #513 test hook (tear_next_append) is replaced by the fault plan. Refs #390 Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- CHANGELOG.md | 1 + CLAUDE.md | 3 +- README.md | 2 +- docs/ERROR_REFERENCE.md | 17 ++ docs/TEST_COVERAGE.md | 4 +- src/db.rs | 45 +++- src/error.rs | 9 + src/fault_matrix.rs | 410 ++++++++++++++++++++++++++++++++ src/lib.rs | 2 + src/storage/backend/file.rs | 84 +++++++ src/storage/dir_sync.rs | 6 + src/storage/fault.rs | 205 ++++++++++++++++ src/storage/mod.rs | 2 + src/storage/persistent_facts.rs | 48 +++- src/wal.rs | 95 +++++--- 15 files changed, 897 insertions(+), 36 deletions(-) create mode 100644 src/fault_matrix.rs create mode 100644 src/storage/fault.rs diff --git a/CHANGELOG.md b/CHANGELOG.md index 958b54159..10b4955c1 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -40,6 +40,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Queries no longer lose or duplicate facts when more than 65,535 facts are waiting for a checkpoint (#445; also fixed in v2.0.3). - **A file shorter than its meta page count is refused at open with `STG-044`** (#497). Open never compared the meta page's `page_count` with the file's length. A truncated file (an interrupted copy, a partial download) opened, and its queries and checkpoints then failed with `INT-049` after the WAL had accepted writes. A meta with a `page_count` far past the end opened too: its next checkpoint wrote at that page id, leaving a sparse file of up to 4 EiB, and `verify()` scanned to that count and never finished. Open now refuses both, read-write and read-only, without modifying the file. It does not fall back to the other meta page, because a valid newer meta means that checkpoint happened. A checkpoint now fails with `INT-049` instead of writing a meta that counts pages the backend does not hold, and `verify()` reports a `page_count` past the end as `STG-044` and stops its page scan at the end of the file. `BrowserDb` is not checked: it keeps only live pages (#440), so its store has no length to compare. New code `STG-044`. - **A file shorter than one page is refused at open with `STG-045` unless it is a torn first write** (#506). Open treated any file under 4 KiB as a new database, because it holds no whole page, and a read-write open wrote a new empty database over it. A database cut below one page by an interrupted copy, or an unrelated file at the path, was silently replaced. Now such a file opens as a new database only when its bytes are zeros or a prefix of the first meta page a new database writes (what a crash during creation can leave, the rule a torn full page 0 already followed); anything else is `STG-045`, read-write and read-only, and the file is not modified. A zero-length file is still a new database. New code `STG-045`. +- **A failed checkpoint is never retried on the same handle** (#390). A checkpoint that failed after it may have written (a failed write, a full disk, a failed `fsync`) could be retried by the next checkpoint. After a failed `fsync` the operating system may have dropped the written pages, and the checkpoint's meta page may have reached the disk although the call failed; a retry could then overwrite pages that meta references, and a crash during the retry left a file that failed to read with `STG-029`. Now every later write, checkpoint and index rebuild through that handle fails with the new `STG-046`, queries keep working, and the close-time checkpoint is skipped. Reopening the database recovers everything committed: it is all in the WAL. A `rebuild_indexes()` refused with `STG-041` writes nothing and does not count as failed. A fault-injection matrix now covers EIO, torn and short writes, a full disk and failed fsyncs at every write and sync of transacts, checkpoints, the close-time checkpoint and index rebuilds. - **A commit made after a torn WAL entry is no longer lost on recovery** (#513). Recovery replays the WAL up to its first partial or damaged entry, but the writer appended after the end of the file. After a crash during an append, the next session's commits went in after the partial entry, so a second crash before any checkpoint lost them, although each had been fsynced and reported as committed. A failed append (short write, full disk, I/O error) did the same to the next commit through that handle. Opening a database for writing now cuts the WAL back to the end of its last valid entry, and syncs it, before anything is appended. After a failed append, every later write through that handle fails with the new `WAL-007` until the database is reopened or a `checkpoint()` succeeds. The transaction whose append failed is not applied; after a reopen it is either there in full (its entry reached the disk) or not at all. Affected every release since v0.5.0. - **A v7 fact page with a damaged type byte fails the upgrade with `STG-014`** (#496). Opening a v7 file skipped, without an error, any page in its fact-page range whose type byte was not the fact-page type. The read-write open then upgraded the file to v8 and freed the old v7 pages, so that page's facts were lost for good; the read-only open returned the same answer with them missing. A v2.x writer fills that range with fact pages only, so any other type there is damage: open now fails with `STG-014`, read-write and read-only, and leaves the v7 file as it was. v7 fact pages have no checksum of their own, so damage elsewhere in a page can still decode to wrong facts or fail with another code; keep a copy of a v7 file until it has opened under v3.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). diff --git a/CLAUDE.md b/CLAUDE.md index 7a58e8368..49d1a9736 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -108,6 +108,7 @@ cargo run < demos/demo_negation.txt - `backend/file.rs`: Single `.graph` file backend (4KB pages, cross-platform) - `backend/memory.rs`: In-memory backend for testing - `backend/fault_inject.rs`: `FaultInjectingBackend` — injects I/O errors for durability tests (test builds only) + - `fault.rs`: thread-local fault plan (test builds only, #390) — EIO, torn/short writes, sticky ENOSPC, failed fsync with or without lost writes, at the k-th write or sync of `FileBackend`, the WAL and `sync_parent_dir`; driven by `src/fault_matrix.rs` - `index.rs`: pending (uncheckpointed) EAVT/AEVT keys over UUIDs and strings, `encode_value` - `keys.rs`: byte-comparable v8 keys (FDB integers, value tags, `tx↓`, FOREVER), DICT keys, `MAX_VALUE_BYTES`, `MAX_IDENT_BYTES` - `node.rs`: prefix-compressed leaf and shortest-separator internal node codecs @@ -197,7 +198,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1393 tests** (1384 passing, 9 ignored; unit + integration + doc). +**1406 tests** (1397 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. diff --git a/README.md b/README.md index 879da8352..17828bf13 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1393 tests +cargo test # run 1406 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index 720f03886..aef1ff413 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -157,6 +157,7 @@ with no `CodedError` anywhere in its chain. | STG-043 | Log writer target already exists | Storage | | STG-044 | File shorter than its meta page count | Storage | | STG-045 | File shorter than one page and not a new database | Storage | +| STG-046 | Earlier checkpoint failed on this handle | Storage | | WAL-001 | Invalid WAL magic number | WAL | | WAL-002 | Unsupported WAL version | WAL | | WAL-003 | Value size exceeds maximum | WAL | @@ -2307,6 +2308,22 @@ let mut out = LogWriter::create("memory.v2.graph", OpenOptions::new())?; --- +### STG-046 Earlier checkpoint failed on this handle + +**Error text**: `an earlier checkpoint failed on this handle and is not retried; reopen the database` + +**Cause**: A checkpoint (automatic, `checkpoint()`, `rebuild_indexes()`, or the one on close) failed with an I/O error after it may have written pages: a failed write, a full disk, or a failed `fsync`. After a failed `fsync` the operating system may have dropped the written pages while marking them clean, so a second `fsync` can report success for data that never reached the disk (the PostgreSQL "fsyncgate" problem). The checkpoint's meta page may also have reached the disk although the call failed; a retry would then overwrite pages that page references. So the handle never retries: every later write, checkpoint and index rebuild through it fails with STG-046. + +Nothing committed is lost. Every committed transaction is still in the WAL, and the `.graph` file holds either the previous checkpoint or the failed one complete. Queries through the handle keep working. The close-time checkpoint is skipped. + +**Resolution**: +- Fix the cause (free disk space, check the device and the kernel log), then drop every clone of the handle and open the database again. Opening picks the newest complete checkpoint and replays the WAL. +- Do not copy the `.graph` file without its `.wal` while the handle is in this state. + +**Scenario**: The disk fills during an automatic checkpoint, so the `transact` that triggered it fails with the I/O error (its transaction is already in the WAL and applied). The next `transact` fails with STG-046 until the database is reopened. + +--- + ## WAL — Write-Ahead Log Errors WAL errors relate to the sidecar `.wal` file written alongside the `.graph` file. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index fb9b7b97f..8df032a06 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,9 +4,9 @@ **Verified**: 2026-10-10 with `cargo test --quiet` -**Result**: 1,384 passing tests and 9 ignored tests (1,393 total) +**Result**: 1,397 passing tests and 9 ignored tests (1,406 total) -This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, 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 writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, 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 writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 935 passing; nine that spawn threads or a child process are ignored on WASI. These are not counted above. ### Covered Areas diff --git a/src/db.rs b/src/db.rs index ded7be338..d447e4c92 100644 --- a/src/db.rs +++ b/src/db.rs @@ -371,6 +371,24 @@ impl Drop for Inner { } } +/// Refuse a write, before it takes a `tx_count`, on a handle where an earlier +/// write failed: a checkpoint (STG-046) or a WAL append (WAL-007). See #390 +/// and #513. +fn refuse_if_failed(ctx: &WriteContext) -> Result<()> { + #[cfg(not(target_arch = "wasm32"))] + if let WriteContext::File { pfs, wal, .. } = ctx { + if pfs.failed() { + bail_coded!(ErrorCode::Stg046); + } + if wal.as_ref().is_some_and(WalWriter::failed) { + bail_coded!(ErrorCode::Wal007); + } + } + #[cfg(target_arch = "wasm32")] + let _ = ctx; + Ok(()) +} + // ─── Fact size validation (moved to WAL serialization) ──────────────────────── // ─── Minigraf ───────────────────────────────────────────────────────────────── @@ -696,6 +714,7 @@ impl Minigraf { let tx_id = crate::graph::types::tx_id_now(); crate::graph::storage::check_valid_windows(&stamped, tx_id)?; crate::graph::storage::check_one_window_per_triple(&stamped)?; + refuse_if_failed(&ctx)?; let tx_count = self.inner.fact_storage.allocate_tx_count(); let stamped: Vec = stamped @@ -891,6 +910,16 @@ impl Minigraf { /// # Errors /// /// Returns an error if the write lock is poisoned or the checkpoint I/O fails. + /// + /// A failed checkpoint is never retried on the same handle: after a failed + /// `fsync` the operating system may have dropped the written pages, and a + /// retry could report success over them. Every later write, checkpoint + /// and index rebuild through the handle fails with STG-046; queries keep + /// working. Reopen the database: every committed transaction is still in + /// the WAL, and the file holds the previous checkpoint or the failed one + /// complete. The same applies to an automatic checkpoint, which fails the + /// `transact` or `commit` that triggered it after that transaction is + /// already durable in the WAL. pub fn checkpoint(&self) -> Result<(), MinigrafError> { self.checkpoint_inner().map_err(MinigrafError::from) } @@ -1012,6 +1041,18 @@ impl Minigraf { self.inner.fact_storage.current_tx_count() } + /// End the handle as a killed process would: no close-time checkpoint and + /// no save on drop. Whatever reached the file stays; the lock is released. + #[cfg(all(test, not(target_arch = "wasm32")))] + pub(crate) fn kill(self) { + let mut ctx = self.inner.write_lock.lock().unwrap(); + if let WriteContext::File { mut pfs, .. } = + std::mem::replace(&mut *ctx, WriteContext::Memory) + { + pfs.discard(); + } + } + /// Internal checkpoint logic (operates on an already-held write-lock guard). fn do_checkpoint(_fact_storage: &FactStorage, ctx: &mut WriteContext) -> Result<()> { match ctx { @@ -1500,6 +1541,7 @@ impl<'a> WriteTransaction<'a> { // are checked again here (#436). let tx_id = crate::graph::types::tx_id_now(); crate::graph::storage::check_valid_windows(&facts_to_commit, tx_id)?; + refuse_if_failed(&self.guard)?; let tx_count = self.inner.fact_storage.allocate_tx_count(); // Stamp facts with tx_id and tx_count @@ -2425,9 +2467,10 @@ mod tests { let db = Minigraf::open(&db_path).unwrap(); db.execute("(transact [[:a :name \"A\"]])").unwrap(); - crate::wal::tear_next_append(9); + crate::storage::fault::arm(crate::storage::fault::Fault::Torn(9), 0); db.execute("(transact [[:b :name \"B\"]])") .expect_err("the torn append fails"); + crate::storage::fault::disarm(); assert_eq!(names(&db), 1, "the failed transaction is not applied"); let err = db diff --git a/src/error.rs b/src/error.rs index 7a83276dd..964bbacb2 100644 --- a/src/error.rs +++ b/src/error.rs @@ -189,6 +189,7 @@ pub(crate) enum ErrorCode { Stg043, Stg044, Stg045, + Stg046, Wal001, Wal002, Wal003, @@ -1101,6 +1102,12 @@ pub(crate) const REGISTRY: &[(ErrorCode, &str, &str, ErrorCategory)] = &[ "File is {} bytes, shorter than one page, and is not a new Minigraf database", ErrorCategory::Storage, ), + ( + ErrorCode::Stg046, + "STG-046", + "an earlier checkpoint failed on this handle and is not retried; reopen the database", + ErrorCategory::Storage, + ), ( ErrorCode::Wal001, "WAL-001", @@ -2022,6 +2029,7 @@ mod tests { | ErrorCode::Stg043 | ErrorCode::Stg044 | ErrorCode::Stg045 + | ErrorCode::Stg046 | ErrorCode::Wal001 | ErrorCode::Wal002 | ErrorCode::Wal003 @@ -2246,6 +2254,7 @@ mod tests { ErrorCode::Stg043, ErrorCode::Stg044, ErrorCode::Stg045, + ErrorCode::Stg046, ErrorCode::Wal001, ErrorCode::Wal002, ErrorCode::Wal003, diff --git a/src/fault_matrix.rs b/src/fault_matrix.rs new file mode 100644 index 000000000..d87d077c7 --- /dev/null +++ b/src/fault_matrix.rs @@ -0,0 +1,410 @@ +//! Fault-injection matrix through the whole `Minigraf` write path (#390). +//! +//! Each case builds a file database (checkpointed facts, multi-valued and +//! retracted facts, long values, entries pending in the WAL), arms one fault +//! at the `k`-th write or sync of one operation, runs the operation, and +//! then: +//! +//! - checks that a later write either succeeds or is refused with WAL-007 or +//! STG-046, and that after a failed checkpoint another one is STG-046 +//! (never retried); +//! - kills the handle (no close-time checkpoint) and reopens with working +//! I/O: the facts are exactly what the handle held, plus, only when the +//! transaction's own write failed, that whole transaction or none of it. +//! `verify` finds nothing; +//! - commits once more, kills, reopens, and finds that commit too. +//! +//! `k` runs from 0 until the operation finishes without reaching the fault. + +use crate::db::{Minigraf, OpenOptions}; +use crate::fact_log::FactFilter; +use crate::storage::fault::{self, Fault, Site}; +use std::path::Path; + +/// One fact version, comparable across handles. +type Rec = (String, String, String, u64, u64, i64, i64, bool); + +fn snapshot(db: &Minigraf) -> Vec { + let mut v: Vec = db + .fact_log(&FactFilter::new()) + .unwrap() + .map(|r| { + let r = r.unwrap(); + ( + r.entity.to_string(), + r.attribute, + format!("{:?}", r.value), + r.tx_count, + r.tx_id, + r.valid_from, + r.valid_to, + r.asserted, + ) + }) + .collect(); + v.sort(); + v +} + +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +enum Op { + /// A transact appended to an existing WAL. + Transact, + /// A transact that creates the WAL (header, directory sync). + TransactNewWal, + /// A transact whose WAL entry reaches the checkpoint threshold. + AutoCheckpoint, + /// `checkpoint()` with entries pending. + Checkpoint, + /// Dropping the handle: the close-time checkpoint. + Close, + /// `rebuild_indexes()` with entries pending. + Rebuild, +} + +impl Op { + /// Whether the operation writes its own transaction (`X`). + fn writes_x(self) -> bool { + matches!(self, Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint) + } +} + +const X: &str = r#"(transact [[:x1 :p/x 1] [:x1 :p/x 2] [:x2 :p/xlong "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"]])"#; +const X_FACTS: usize = 3; + +fn open(path: &Path, op: Op) -> Minigraf { + let threshold = if op == Op::AutoCheckpoint { 3 } else { 1000 }; + OpenOptions::new() + .wal_checkpoint_threshold(threshold) + .path(path) + .open() + .expect("open") +} + +/// `n` facts on entities `0..n`, some with long values. +fn bulk(prefix: &str, n: usize) -> String { + let mut s = String::from("(transact ["); + for i in 0..n { + s.push_str(&format!( + "[:{prefix}{i} :p/n {i}] [:{prefix}{i} :p/name \"name {prefix} {i}\"]" + )); + if i % 25 == 0 { + s.push_str(&format!( + "[:{prefix}{i} :p/long \"{}\"]", + "l".repeat(80 + i % 7) + )); + } + } + s.push_str("])"); + s +} + +/// A database committed over two checkpoints (multi-level trees, a free +/// list, multi-valued and retracted facts, long values) and, except for +/// `TransactNewWal`, two entries pending in the WAL. +fn build(path: &Path, op: Op) -> Minigraf { + let db = open(path, op); + db.execute(&bulk("a", 150)).unwrap(); + db.execute(r#"(transact [[:e1 :p/tag "a"] [:e1 :p/tag "b"] [:e2 :p/n 1]])"#) + .unwrap(); + db.checkpoint().unwrap(); + db.execute(&bulk("b", 150)).unwrap(); + db.execute(r#"(retract [[:e1 :p/tag "a"] [:a7 :p/n 7]])"#) + .unwrap(); + db.checkpoint().unwrap(); + if op != Op::TransactNewWal { + db.execute(&bulk("c", 20)).unwrap(); + db.execute(r#"(transact [[:e1 :p/tag "c"] [:e3 :p/ref :e1]])"#) + .unwrap(); + } + db +} + +/// The records `after` has beyond `before`, if `before` is all in `after`. +fn extra(before: &[Rec], after: &[Rec]) -> Option> { + let mut rest = after.to_vec(); + for r in before { + let i = rest.iter().position(|x| x == r)?; + rest.remove(i); + } + Some(rest) +} + +/// Whether `recs` is exactly one whole `X` transaction. +fn is_whole_x(recs: &[Rec]) -> bool { + recs.len() == X_FACTS + && recs.iter().all(|r| r.1.starts_with(":p/x") && r.7) + && recs.iter().all(|r| r.3 == recs[0].3) +} + +fn code(e: crate::MinigrafError) -> &'static str { + e.code() +} + +fn reopen_and_check(path: &Path, op: Op, live: &[Rec], x_failed: bool) { + let db = open(path, op); + let reopened = snapshot(&db); + let more = extra(live, &reopened).expect("a fact the handle held was lost"); + assert!( + more.is_empty() || (x_failed && is_whole_x(&more)), + "reopened file holds facts the handle never committed, or part of one" + ); + let report = db.verify().unwrap(); + assert!(report.problems.is_empty(), "verify after reopen"); + + // One more commit after recovery must survive a kill. + db.execute(r#"(transact [[:z :p/z "after"]])"#).unwrap(); + let with_z = snapshot(&db); + db.kill(); + let db = open(path, op); + assert!(snapshot(&db) == with_z, "a commit after recovery was lost"); + assert!(db.verify().unwrap().problems.is_empty(), "verify after Z"); + db.kill(); +} + +/// Run `op` with `fault` at every call index. Returns how many indexes hit. +fn run(op: Op, f: Fault) -> u64 { + let mut hits = 0; + for k in 0u64.. { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("f.graph"); + let db = build(&path, op); + let before = snapshot(&db); + + fault::arm(f, k); + let (result, db) = match op { + Op::Transact | Op::TransactNewWal | Op::AutoCheckpoint => { + (db.execute(X).map(|_| ()), Some(db)) + } + Op::Checkpoint => (db.checkpoint(), Some(db)), + Op::Rebuild => (db.rebuild_indexes(), Some(db)), + Op::Close => { + drop(db); + (Ok(()), None) + } + }; + let tripped = fault::disarm(); + + let live = match db { + Some(db) => { + let live = snapshot(&db); + let applied = extra(&before, &live).expect("the handle lost a fact"); + if op.writes_x() { + assert!( + applied.is_empty() || is_whole_x(&applied), + "the handle applied part of a transaction" + ); + if result.is_ok() { + assert!(is_whole_x(&applied), "a committed transaction is missing"); + } + } else { + assert!(applied.is_empty(), "a checkpoint changed the facts"); + } + + let checkpoint_failed = + result.is_err() && matches!(tripped, Some(Site::PageWrite | Site::PageSync)); + if checkpoint_failed { + let err = db.checkpoint().expect_err("a failed checkpoint is retried"); + assert_eq!(code(err), "STG-046"); + } + + // A later write succeeds, or is refused as failed. + let live = match db.execute(r#"(transact [[:y :p/y "later"]])"#) { + Ok(_) => snapshot(&db), + Err(e) => { + let c = code(e); + assert!(c == "WAL-007" || c == "STG-046", "later write: {c}"); + assert!(result.is_err(), "a write refused after a success"); + + live + } + }; + db.kill(); + live + } + // The close-time checkpoint's errors are not reported. + None => before, + }; + + let x_failed = op.writes_x() && result.is_err(); + reopen_and_check(&path, op, &live, x_failed); + + if tripped.is_none() { + assert!(result.is_ok(), "failed without a fault"); + break; + } + hits += 1; + } + hits +} + +const FAULTS: [Fault; 7] = [ + Fault::Eio, + Fault::Torn(1), + Fault::Torn(40), + Fault::Torn(4095), + Fault::Enospc, + Fault::SyncEio, + Fault::SyncLost, +]; + +fn run_all(op: Op) { + for f in FAULTS { + let hits = run(op, f); + assert!(hits > 0, "the fault never fired"); + } +} + +#[test] +fn faults_during_transact() { + run_all(Op::Transact); +} + +#[test] +fn faults_during_transact_that_creates_the_wal() { + run_all(Op::TransactNewWal); +} + +#[test] +fn faults_during_auto_checkpoint() { + run_all(Op::AutoCheckpoint); +} + +#[test] +fn faults_during_checkpoint() { + run_all(Op::Checkpoint); +} + +#[test] +fn faults_during_close() { + run_all(Op::Close); +} + +#[test] +fn faults_during_rebuild_indexes() { + run_all(Op::Rebuild); +} + +/// The disk fills part-way through a checkpoint: every write from then on +/// fails. The checkpoint fails, the handle refuses writes with STG-046, and +/// after space is freed a reopen holds every committed fact. +#[test] +fn disk_full_halfway_through_a_checkpoint() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("f.graph"); + let db = build(&path, Op::Checkpoint); + for i in 0..200 { + db.execute(&format!("(transact [[:bulk{i} :p/n {i}]])")) + .unwrap(); + } + let live = snapshot(&db); + + // Count the checkpoint's page writes on a copy, then fill the disk at + // half of them. + let writes = { + let copy_dir = tempfile::tempdir().unwrap(); + let copy = copy_dir.path().join("f.graph"); + std::fs::copy(&path, ©).unwrap(); + let mut wal = copy.as_os_str().to_owned(); + wal.push(".wal"); + let mut src_wal = path.as_os_str().to_owned(); + src_wal.push(".wal"); + std::fs::copy(&src_wal, &wal).unwrap(); + let db2 = open(©, Op::Checkpoint); + fault::arm(Fault::Eio, u64::MAX); + db2.checkpoint().unwrap(); + let n = fault::count(); + fault::disarm(); + db2.kill(); + n + }; + assert!(writes > 4, "the checkpoint writes several pages"); + + fault::arm(Fault::Enospc, writes / 2); + let err = db.checkpoint().expect_err("the disk is full"); + assert_eq!(fault::disarm(), Some(Site::PageWrite)); + let c = code(err); + assert!(c.starts_with("INT") || c.starts_with("STG"), "{c}"); + let err = db + .execute("(transact [[:late :p/n 1]])") + .expect_err("writes are refused"); + assert_eq!(code(err), "STG-046"); + assert!(snapshot(&db) == live, "reads still see every fact"); + db.kill(); + + reopen_and_check(&path, Op::Checkpoint, &live, false); +} + +/// How many calls `fault` targets during a clean checkpoint of a copy of +/// the database at `path`. +fn checkpoint_calls(path: &Path, f: Fault) -> u64 { + let copy_dir = tempfile::tempdir().unwrap(); + let copy = copy_dir.path().join("f.graph"); + std::fs::copy(path, ©).unwrap(); + let mut wal = copy.as_os_str().to_owned(); + wal.push(".wal"); + let mut src_wal = path.as_os_str().to_owned(); + src_wal.push(".wal"); + if Path::new(&src_wal).exists() { + std::fs::copy(&src_wal, &wal).unwrap(); + } + let db = open(©, Op::Checkpoint); + fault::arm(f, u64::MAX); + db.checkpoint().unwrap(); + let n = fault::count(); + fault::disarm(); + db.kill(); + n +} + +/// The fsyncgate case: the checkpoint's last fsync (after its meta page +/// write) fails, but the meta page reached the file. The handle must not +/// commit again: a retry would write the same generation into pages that +/// meta references, and a crash during it would leave the file pointing +/// at them. Here a later write and a retried checkpoint (crashing at each +/// of its writes) are both refused, and every reopen is intact. +#[test] +fn no_commit_after_a_failed_meta_fsync() { + let dir = tempfile::tempdir().unwrap(); + let base = dir.path().join("base.graph"); + build(&base, Op::Checkpoint).kill(); + let syncs = checkpoint_calls(&base, Fault::SyncEio); + let writes = checkpoint_calls(&base, Fault::Eio); + let mut base_wal = base.as_os_str().to_owned(); + base_wal.push(".wal"); + + for j in 0..writes { + let case = tempfile::tempdir().unwrap(); + let path = case.path().join("f.graph"); + std::fs::copy(&base, &path).unwrap(); + let mut wal = path.as_os_str().to_owned(); + wal.push(".wal"); + std::fs::copy(&base_wal, &wal).unwrap(); + + let db = open(&path, Op::Checkpoint); + let live = snapshot(&db); + // The last two syncs are the meta page's and the directory's, + // after the WAL is removed. + fault::arm(Fault::SyncEio, syncs - 2); + db.checkpoint().expect_err("the last fsync fails"); + assert_eq!(fault::disarm(), Some(Site::PageSync)); + + let live = match db.execute(r#"(transact [[:y :p/y "later"] [:a3 :p/n 33]])"#) { + Ok(_) => snapshot(&db), + Err(e) => { + assert_eq!(code(e), "STG-046"); + live + } + }; + fault::arm(Fault::Torn(2048), j); + if let Err(e) = db.checkpoint() { + if fault::disarm().is_none() { + assert_eq!(code(e), "STG-046"); + } + } else { + fault::disarm(); + } + db.kill(); + reopen_and_check(&path, Op::Checkpoint, &live, false); + } +} diff --git a/src/lib.rs b/src/lib.rs index 3b65b1fa1..2075af39e 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -80,6 +80,8 @@ pub mod db; pub mod error; /// Every fact version, streamed: [`FactLog`], [`FactFilter`], [`FactRecord`]. pub mod fact_log; +#[cfg(all(test, not(target_arch = "wasm32")))] +mod fault_matrix; pub(crate) mod graph; /// Build a new database from explicit fact records: [`LogWriter`]. #[cfg(not(target_arch = "wasm32"))] diff --git a/src/storage/backend/file.rs b/src/storage/backend/file.rs index 487090ace..75dd14076 100644 --- a/src/storage/backend/file.rs +++ b/src/storage/backend/file.rs @@ -209,6 +209,19 @@ pub struct FileBackend { page_count: u64, /// Opened with `LockMode::Shared`: `write_page` and `sync` refuse. read_only: bool, + /// Test-only: what the writes since the last sync replaced, so a fault + /// can lose them (`fault::Fault::SyncLost`). + #[cfg(test)] + unsynced: Unsynced, +} + +/// Pages written since the last sync, with their earlier contents (`None` +/// past the old end), and the file length at that sync. +#[cfg(test)] +#[derive(Default)] +struct Unsynced { + pages: std::collections::BTreeMap>>, + synced_len: Option, } impl FileBackend { @@ -352,6 +365,8 @@ impl FileBackend { page_count, read_only, _path_guard: path_guard, + #[cfg(test)] + unsynced: Unsynced::default(), }) } @@ -361,6 +376,43 @@ impl FileBackend { &self.path } + /// Keep page `page_id`'s contents before its first write since the last + /// sync, and the file length at that sync. + #[cfg(test)] + fn remember_unsynced(&mut self, page_id: u64) -> Result<()> { + if self.unsynced.synced_len.is_none() { + self.unsynced.synced_len = Some(self.file.metadata()?.len()); + } + if !self.unsynced.pages.contains_key(&page_id) { + let old = if page_id < self.page_count { + Some(self.read_page(page_id)?) + } else { + None + }; + self.unsynced.pages.insert(page_id, old); + } + Ok(()) + } + + /// Undo every write since the last sync, as a kernel that dropped the + /// dirty pages of a failed fsync would. + #[cfg(test)] + fn lose_unsynced(&mut self) -> Result<()> { + let unsynced = std::mem::take(&mut self.unsynced); + for (page_id, old) in unsynced.pages { + if let Some(old) = old { + self.file + .seek(SeekFrom::Start(page_id.saturating_mul(PAGE_SIZE as u64)))?; + self.file.write_all(&old)?; + } + } + if let Some(len) = unsynced.synced_len { + self.file.set_len(len)?; + self.page_count = len / PAGE_SIZE as u64; + } + Ok(()) + } + /// Cut the file to zero pages and sync, keeping the lock. Used to reuse /// a log writer's `.partial` file left by an earlier build (#431). pub(crate) fn truncate(&mut self) -> Result<()> { @@ -389,6 +441,22 @@ impl StorageBackend for FileBackend { format!("page offset overflow for page_id {page_id}") ) })?; + #[cfg(test)] + { + use crate::storage::fault::{self, Action, Site}; + if fault::armed() { + self.remember_unsynced(page_id)?; + } + match fault::on(Site::PageWrite) { + Action::Fail(e) => return Err(e.into()), + Action::Tear(n) => { + self.file.seek(SeekFrom::Start(offset))?; + self.file.write_all(&data[..n.min(data.len())])?; + return Err(fault::eio().into()); + } + Action::Proceed | Action::Lose => {} + } + } self.file.seek(SeekFrom::Start(offset))?; self.file.write_all(data)?; @@ -434,7 +502,23 @@ impl StorageBackend for FileBackend { if self.read_only { bail_coded!(ErrorCode::Int056, "sync"); } + #[cfg(test)] + { + use crate::storage::fault::{self, Action, Site}; + match fault::on(Site::PageSync) { + Action::Fail(e) => return Err(e.into()), + Action::Lose => { + self.lose_unsynced()?; + return Err(fault::eio().into()); + } + Action::Proceed | Action::Tear(_) => {} + } + } self.file.sync_all()?; + #[cfg(test)] + { + self.unsynced = Unsynced::default(); + } Ok(()) } diff --git a/src/storage/dir_sync.rs b/src/storage/dir_sync.rs index 65edc6fae..9f772d1de 100644 --- a/src/storage/dir_sync.rs +++ b/src/storage/dir_sync.rs @@ -33,6 +33,12 @@ pub(crate) fn sync_parent_dir(child: &Path) -> io::Result<()> { #[cfg(test)] record(dir, child); + #[cfg(test)] + match crate::storage::fault::on(crate::storage::fault::Site::DirSync) { + crate::storage::fault::Action::Fail(e) => return Err(e), + crate::storage::fault::Action::Lose => return Err(crate::storage::fault::eio()), + _ => {} + } #[cfg(unix)] std::fs::File::open(dir)?.sync_all()?; diff --git a/src/storage/fault.rs b/src/storage/fault.rs new file mode 100644 index 000000000..0fbd1fec6 --- /dev/null +++ b/src/storage/fault.rs @@ -0,0 +1,205 @@ +//! Test-only fault plan for the file and WAL I/O paths (#390). +//! +//! Every write and sync that reaches the disk through `FileBackend`, the WAL +//! writer and `sync_parent_dir` asks [`on`] first. With a plan armed on the +//! calling thread, the `at`-th call of the plan's kind (writes or syncs, +//! counted from 0) fails the way [`Fault`] says. A [`Fault::Enospc`] plan +//! keeps failing every later write too, like a full disk. With no plan +//! armed, [`on`] returns [`Action::Proceed`] and the call runs as usual. +//! +//! The plan is thread-local, so tests running in parallel do not see each +//! other's faults; a `Minigraf` call runs its I/O on the calling thread. + +use std::cell::RefCell; +use std::io; + +/// Where an I/O call happens. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub(crate) enum Site { + /// `FileBackend::write_page`. + PageWrite, + /// `FileBackend::sync`. + PageSync, + /// A write to the WAL: its header or an entry. + WalWrite, + /// Cutting a torn tail off the WAL (`set_len`). + WalTruncate, + /// An fsync of the WAL. + WalSync, + /// Removing the WAL after a checkpoint. + WalRemove, + /// `sync_parent_dir`. + DirSync, +} + +impl Site { + fn is_write(self) -> bool { + matches!( + self, + Site::PageWrite | Site::WalWrite | Site::WalTruncate | Site::WalRemove + ) + } +} + +/// How the chosen call fails. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +pub(crate) enum Fault { + /// The write fails with EIO and writes nothing. + Eio, + /// The write stores its first `n` bytes, then fails with EIO: a short + /// write, or a torn page. + Torn(usize), + /// The write fails with ENOSPC and writes nothing, and so does every + /// later write (removing a file still works). + Enospc, + /// The sync fails with EIO; what was written stays in the file. + SyncEio, + /// The sync fails with EIO and the writes since that file's last good + /// sync are lost, as when the kernel drops dirty pages after a failed + /// fsync (PostgreSQL's "fsyncgate"). + SyncLost, +} + +impl Fault { + fn targets(self, site: Site) -> bool { + match self { + Fault::Eio | Fault::Torn(_) => site.is_write(), + Fault::Enospc => site.is_write() && site != Site::WalRemove, + Fault::SyncEio | Fault::SyncLost => !site.is_write(), + } + } +} + +/// What the call site must do. +#[derive(Debug)] +pub(crate) enum Action { + /// Run the call as usual. + Proceed, + /// Fail with this error, writing nothing. + Fail(io::Error), + /// Write the first `n` bytes, then fail with EIO. + Tear(usize), + /// Throw away the writes since the last good sync, then fail with EIO. + Lose, +} + +struct Plan { + fault: Fault, + at: u64, + seen: u64, + tripped: Option, +} + +thread_local! { + static PLAN: RefCell> = const { RefCell::new(None) }; +} + +/// Arm `fault` at the `at`-th call it targets on this thread. +pub(crate) fn arm(fault: Fault, at: u64) { + PLAN.with(|p| { + *p.borrow_mut() = Some(Plan { + fault, + at, + seen: 0, + tripped: None, + }) + }); +} + +/// Remove the plan. Returns the site where it fired, if it did. +pub(crate) fn disarm() -> Option { + PLAN.with(|p| p.borrow_mut().take().and_then(|plan| plan.tripped)) +} + +/// Whether a plan is armed on this thread. Call sites keep what they need +/// to undo unsynced writes ([`Fault::SyncLost`]) only then. +pub(crate) fn armed() -> bool { + PLAN.with(|p| p.borrow().is_some()) +} + +/// How many calls the armed plan has targeted so far. +pub(crate) fn count() -> u64 { + PLAN.with(|p| p.borrow().as_ref().map_or(0, |plan| plan.seen)) +} + +/// An EIO for a failed call. +pub(crate) fn eio() -> io::Error { + io::Error::other("fault injection: EIO") +} + +/// Ask the plan what the call at `site` must do. +pub(crate) fn on(site: Site) -> Action { + PLAN.with(|p| { + let mut p = p.borrow_mut(); + let Some(plan) = p.as_mut() else { + return Action::Proceed; + }; + if !plan.fault.targets(site) { + return Action::Proceed; + } + if plan.fault == Fault::Enospc && plan.tripped.is_some() { + return Action::Fail(io::Error::from(io::ErrorKind::StorageFull)); + } + let n = plan.seen; + plan.seen = n.saturating_add(1); + if n != plan.at { + return Action::Proceed; + } + plan.tripped = Some(site); + match plan.fault { + Fault::Eio | Fault::SyncEio => Action::Fail(eio()), + Fault::Torn(bytes) => Action::Tear(bytes), + Fault::Enospc => Action::Fail(io::Error::from(io::ErrorKind::StorageFull)), + Fault::SyncLost => Action::Lose, + } + }) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn no_plan_proceeds() { + disarm(); + assert!(matches!(on(Site::PageWrite), Action::Proceed)); + assert!(!armed()); + } + + #[test] + fn write_fault_counts_writes_only() { + arm(Fault::Eio, 1); + assert!(matches!(on(Site::PageWrite), Action::Proceed)); + assert!(matches!(on(Site::PageSync), Action::Proceed)); + assert!(matches!(on(Site::WalWrite), Action::Fail(_))); + assert!(matches!(on(Site::WalWrite), Action::Proceed)); + assert_eq!(disarm(), Some(Site::WalWrite)); + } + + #[test] + fn sync_fault_counts_syncs_only() { + arm(Fault::SyncLost, 1); + assert!(matches!(on(Site::DirSync), Action::Proceed)); + assert!(matches!(on(Site::PageWrite), Action::Proceed)); + assert!(matches!(on(Site::PageSync), Action::Lose)); + assert_eq!(disarm(), Some(Site::PageSync)); + } + + #[test] + fn enospc_keeps_failing_writes_but_not_removes() { + arm(Fault::Enospc, 0); + assert!(matches!(on(Site::WalRemove), Action::Proceed)); + assert!(matches!(on(Site::PageWrite), Action::Fail(_))); + assert!(matches!(on(Site::WalWrite), Action::Fail(_))); + assert!(matches!(on(Site::PageSync), Action::Proceed)); + assert!(matches!(on(Site::WalRemove), Action::Proceed)); + assert_eq!(disarm(), Some(Site::PageWrite)); + } + + #[test] + fn plan_that_never_fires_reports_none() { + arm(Fault::Torn(10), 5); + assert!(matches!(on(Site::PageWrite), Action::Proceed)); + assert_eq!(disarm(), None); + } +} diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 760861d93..cc3149a15 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -11,6 +11,8 @@ pub mod cache; pub(crate) mod dict; #[cfg(not(target_arch = "wasm32"))] pub(crate) mod dir_sync; +#[cfg(all(test, not(target_arch = "wasm32")))] +pub(crate) mod fault; pub(crate) mod freelist; pub mod index; pub(crate) mod keys; diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 53a4b23e1..b36c42247 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -38,6 +38,12 @@ pub struct PersistentFactStorage { page_cache: Arc, storage: FactStorage, dirty: bool, + /// A commit (`save` or `rebuild_indexes`) failed after it may have + /// written. Every later commit is refused with STG-046 (#390): after a + /// failed fsync the kernel may have dropped the written pages, and a + /// retry could report success over them, or overwrite pages of a meta + /// that did reach the disk. Reopening reads the file afresh. + failed: bool, /// The active (last committed) meta page. meta: MetaPage, /// Ids the last `save()` put on the free list, for the browser layer to @@ -130,6 +136,7 @@ impl PersistentFactStorage { page_cache: Arc::new(PageCache::new(page_cache_capacity)), storage: FactStorage::new(), dirty: false, + failed: false, meta: MetaPage::empty(1), #[cfg(all(target_arch = "wasm32", feature = "browser"))] released: Vec::new(), @@ -389,7 +396,11 @@ impl PersistentFactStorage { /// a sync, the new meta goes to the other slot and is synced: the only commit /// point. A failure at any step leaves the active meta and all it references /// untouched. The pages written depend on the change, not on the graph size. + /// + /// After a failure that may have written (anything past the checks + /// below), this and every later commit fail with STG-046. pub fn save(&mut self) -> Result<()> { + self.refuse_if_failed()?; if !self.dirty { return Ok(()); } @@ -397,6 +408,8 @@ impl PersistentFactStorage { let pending_facts = self.storage.get_pending_facts(); let m = self.meta; let next_gen = m.next_generation()?; + // Cleared only when the commit completes. + self.failed = true; let mut backend = self.lock()?; let mut alloc = @@ -455,6 +468,7 @@ impl PersistentFactStorage { drop(backend); self.dirty = false; + self.failed = false; self.activate(new_meta); #[cfg(all(target_arch = "wasm32", feature = "browser"))] { @@ -493,12 +507,18 @@ impl PersistentFactStorage { use crate::storage::keys::{Index, KeyFact}; use std::collections::BTreeSet; + self.refuse_if_failed()?; self.refuse_while_logs_open()?; let m = self.meta; let next_gen = m.next_generation()?; let pending_facts = self.storage.get_pending_facts(); - let mut backend = self.lock()?; + // Locked through a clone of the handle, so `self.failed` can be set + // while the guard is held. + let backend_handle = Arc::clone(&self.backend); + let mut backend = backend_handle + .lock() + .map_err(|_| err_coded!(ErrorCode::Stg016))?; let cache = PageCache::new(VERIFY_CACHE_PAGES); cache.set_generation_bound(m.generation); @@ -532,6 +552,9 @@ impl PersistentFactStorage { (source, pool) }; + // Nothing is written before this point (STG-041 leaves the file and + // this handle as they were). Cleared only when the commit completes. + self.failed = true; let mut alloc = PageAllocator::new(pool.into_iter().collect(), m.page_count, next_gen); let encoded = encode( &pending_facts, @@ -645,6 +668,7 @@ impl PersistentFactStorage { drop(backend); self.dirty = false; + self.failed = false; self.activate(new_meta); self.storage.post_checkpoint_clear(); Ok(()) @@ -652,6 +676,19 @@ impl PersistentFactStorage { /// API-013 while a fact log is open: it reads pages of the active /// generation, and a commit frees pages that the next one reuses (#430). + fn refuse_if_failed(&self) -> Result<()> { + if self.failed { + bail_coded!(ErrorCode::Stg046); + } + Ok(()) + } + + /// Whether a commit failed after it may have written (STG-046). + #[cfg(not(target_arch = "wasm32"))] + pub(crate) fn failed(&self) -> bool { + self.failed + } + fn refuse_while_logs_open(&self) -> Result<()> { match self.storage.log_pins() { 0 => Ok(()), @@ -716,8 +753,9 @@ impl PersistentFactStorage { impl Drop for PersistentFactStorage { fn drop(&mut self) { - // Auto-save on drop - if self.dirty { + // Auto-save on drop, unless an earlier commit failed: the WAL still + // holds everything, and the next open replays it. + if self.dirty && !self.failed { let _ = self.save(); } } @@ -2866,6 +2904,10 @@ mod tests { let before = snapshot(&damaged); let mut pfs = open_mem(&damaged, None).unwrap(); assert_eq!(code(pfs.rebuild_indexes().unwrap_err()), "STG-041"); + assert!( + !pfs.failed(), + "a refusal before any write keeps the handle usable" + ); drop(pfs); assert!( snapshot(&damaged) == before, diff --git a/src/wal.rs b/src/wal.rs index 15d6324e5..eab0df8da 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -29,6 +29,8 @@ use crate::db::SyncMode; use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::types::{Fact, Value}; use crate::storage::dir_sync::sync_parent_dir; +#[cfg(test)] +use crate::storage::fault::{self, Action, Site}; use crate::storage::keys::{MAX_IDENT_BYTES, MAX_VALUE_BYTES}; use anyhow::Result; use std::fs::{File, OpenOptions}; @@ -50,11 +52,46 @@ fn write_wal_header(file: &mut File, base_generation: u64) -> Result<()> { buf[8..16].copy_from_slice(&base_generation.to_le_bytes()); // bytes 16..32 are reserved zeros file.seek(SeekFrom::Start(0))?; - file.write_all(&buf)?; - file.sync_all()?; + wal_write(file, &buf)?; + wal_sync(file, true, 0)?; Ok(()) } +/// Write `bytes` at the file's position. Every WAL byte goes through here. +fn wal_write(file: &mut File, bytes: &[u8]) -> io::Result<()> { + #[cfg(test)] + match fault::on(Site::WalWrite) { + Action::Fail(e) => return Err(e), + Action::Tear(n) => { + file.write_all(&bytes[..n.min(bytes.len())])?; + return Err(fault::eio()); + } + Action::Proceed | Action::Lose => {} + } + file.write_all(bytes) +} + +/// Sync the WAL (`sync_all` when `all`, else `sync_data`). `synced_len` is +/// its length at the last good sync: a test fault that loses unsynced +/// writes cuts the file back to it. +#[cfg_attr(not(test), allow(unused_variables))] +fn wal_sync(file: &mut File, all: bool, synced_len: u64) -> io::Result<()> { + #[cfg(test)] + match fault::on(Site::WalSync) { + Action::Fail(e) => return Err(e), + Action::Lose => { + file.set_len(synced_len)?; + return Err(fault::eio()); + } + Action::Proceed | Action::Tear(_) => {} + } + if all { + file.sync_all() + } else { + file.sync_data() + } +} + /// Check magic and version and return the header's base generation. fn validate_wal_header(file: &mut File) -> Result { let mut buf = [0u8; WAL_HEADER_SIZE]; @@ -166,6 +203,8 @@ pub struct WalWriter { /// An append failed, so the file may end in a partial entry. Later /// appends would land after it, where replay never reaches (#513). failed: bool, + /// The file's length after the last successful append. + end: u64, } impl WalWriter { @@ -197,11 +236,12 @@ impl WalWriter { // The header is durable; make the WAL's directory entry // durable too, or a power loss can lose the whole file (#389). sync_parent_dir(path)?; - file.seek(SeekFrom::End(0))?; + let end = file.seek(SeekFrom::End(0))?; return Ok(WalWriter { file, sync_mode, failed: false, + end, }); } Err(e) if e.kind() == std::io::ErrorKind::AlreadyExists => {} @@ -218,8 +258,14 @@ impl WalWriter { // would be lost: cut it off before appending (#513). let (_, valid_end) = scan_entries(&mut file)?; if file.metadata()?.len() > valid_end { + #[cfg(test)] + if let Action::Fail(e) = fault::on(Site::WalTruncate) { + return Err(e.into()); + } file.set_len(valid_end)?; - file.sync_all()?; + // A lost sync here would bring the cut bytes back, + // which the test fault cannot model: it fails instead. + wal_sync(&mut file, true, valid_end)?; } } // A previous crash landed between this file's creation and its @@ -232,11 +278,12 @@ impl WalWriter { sync_parent_dir(path)?; } } - file.seek(SeekFrom::End(0))?; + let end = file.seek(SeekFrom::End(0))?; Ok(WalWriter { file, sync_mode, failed: false, + end, }) } @@ -271,20 +318,20 @@ impl WalWriter { } fn write_entry(&mut self, entry_bytes: &[u8]) -> Result<()> { - #[cfg(test)] - if let Some(n) = TEAR_NEXT_APPEND.take() { - self.file - .write_all(&entry_bytes[..n.min(entry_bytes.len())])?; - return Err(io::Error::other("test: torn WAL append").into()); - } - self.file.write_all(entry_bytes)?; + wal_write(&mut self.file, entry_bytes)?; match self.sync_mode { - SyncMode::Full => self.file.sync_data()?, + SyncMode::Full => wal_sync(&mut self.file, false, self.end)?, SyncMode::Normal => {} } + self.end = self.end.saturating_add(entry_bytes.len() as u64); Ok(()) } + /// Whether an append failed, so every later one is refused (WAL-007). + pub(crate) fn failed(&self) -> bool { + self.failed + } + /// Delete the WAL file at `path`. Called after a successful checkpoint. /// /// Fsyncs the parent directory after the remove, so a power loss cannot @@ -297,6 +344,11 @@ impl WalWriter { let retries: u32 = if cfg!(windows) { 10 } else { 1 }; let mut last_err = None; for i in 0..retries { + #[cfg(test)] + if let Action::Fail(e) = fault::on(Site::WalRemove) { + last_err = Some(e); + break; + } match std::fs::remove_file(path) { Ok(()) => { sync_parent_dir(path)?; @@ -320,20 +372,6 @@ impl WalWriter { } } -// Test-only: the next append on this thread writes only the first `n` bytes -// of its entry, then fails, as a short write or a full disk would. -#[cfg(test)] -thread_local! { - static TEAR_NEXT_APPEND: std::cell::Cell> = - const { std::cell::Cell::new(None) }; -} - -/// Make the next WAL append on this thread write `n` bytes and fail. -#[cfg(test)] -pub(crate) fn tear_next_append(n: usize) { - TEAR_NEXT_APPEND.set(Some(n)); -} - // ─── WalReader ────────────────────────────────────────────────────────────── /// Reads and validates WAL entries for crash recovery. @@ -824,10 +862,11 @@ mod tests { let fact = |tx: u64| make_fact(Uuid::new_v4(), ":name", Value::Integer(1), tx); writer.append_entry(1, &[fact(1)]).unwrap(); - tear_next_append(10); + fault::arm(fault::Fault::Torn(10), 0); writer .append_entry(2, &[fact(2)]) .expect_err("the torn append fails"); + assert_eq!(fault::disarm(), Some(Site::WalWrite)); let err: crate::error::MinigrafError = writer .append_entry(3, &[fact(3)]) .expect_err("later appends are refused") From d70182161a6ea76a94555bbfeb4f98295864f41a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 10 Oct 2026 15:24:30 +0530 Subject: [PATCH 2/2] test: count checkpoint writes on a closed copy; Windows cannot copy an open file (#390) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_012wXxZguv7PgKQjMMH4yJ5h --- src/fault_matrix.rs | 25 +++++-------------------- 1 file changed, 5 insertions(+), 20 deletions(-) diff --git a/src/fault_matrix.rs b/src/fault_matrix.rs index d87d077c7..222fac618 100644 --- a/src/fault_matrix.rs +++ b/src/fault_matrix.rs @@ -297,27 +297,12 @@ fn disk_full_halfway_through_a_checkpoint() { db.execute(&format!("(transact [[:bulk{i} :p/n {i}]])")) .unwrap(); } + db.kill(); + // Count the checkpoint's writes on a copy (Windows cannot copy a file + // that is open), then fill the disk at half of them. + let writes = checkpoint_calls(&path, Fault::Eio); + let db = open(&path, Op::Checkpoint); let live = snapshot(&db); - - // Count the checkpoint's page writes on a copy, then fill the disk at - // half of them. - let writes = { - let copy_dir = tempfile::tempdir().unwrap(); - let copy = copy_dir.path().join("f.graph"); - std::fs::copy(&path, ©).unwrap(); - let mut wal = copy.as_os_str().to_owned(); - wal.push(".wal"); - let mut src_wal = path.as_os_str().to_owned(); - src_wal.push(".wal"); - std::fs::copy(&src_wal, &wal).unwrap(); - let db2 = open(©, Op::Checkpoint); - fault::arm(Fault::Eio, u64::MAX); - db2.checkpoint().unwrap(); - let n = fault::count(); - fault::disarm(); - db2.kill(); - n - }; assert!(writes > 4, "the checkpoint writes several pages"); fault::arm(Fault::Enospc, writes / 2);