All notable changes to libdictenstein are recorded here.
Date format is ISO-8601 (YYYY-MM-DD).
Binding contract gate. bindings/api.json is the machine-readable model of the
41-function ldict_* C ABI (status/kind/capability/unit-domain pins, registry coordinates
for all 14 governed facades, sibling pins), and scripts/check-bindings.py (stdlib-only,
--json capable) enforces it: model ↔ src/ffi.rs ↔ include/libdictenstein.h symbol and
constant parity, per-facade referenced-symbol validity, coordinate/version coherence, the
publishable-file identity guard, exact npm pins, and byte-equality of
include/vinary_tree_interop.h against the canonical sibling header
(LDICT_INTEROP_HEADER_CANONICAL overrides; skip-with-warning when the sibling checkout is
absent). Wired into CI as the binding-contract job. Binding-scrutiny findings now live in
docs/bindings/FINDINGS_LEDGER.md (seeded with LDICT-B1…B3).
Tier-1 single-owner file lock (multi-process safety). Opening a persistent ARTrie (byte,
char, or vocab; mmap or io_uring backend) now takes an advisory flock(LOCK_EX | LOCK_NB) on
a "<path>.wlock" sidecar at the six DiskManager open chokepoints. A second OS process — or a
second concurrent handle to the same path — is rejected with the new
PersistentARTrieError::FileLocked instead of silently corrupting the file, closing the
previously unguarded open-vs-open cross-process footgun. Same-process reopen (e.g. crash-recovery
tests that mem::forget a handle) is preserved via a process-global refcounted lock registry, and
the lock-free read/write hot paths are untouched (the lock is taken once per open, never per
operation). Uses the safe rustix::fs::flock (no new unsafe). First cross-process test:
tests/persistent_multiprocess_lock.rs. Documented in docs/design/os-level-locking.md.
Tier-2 SWMR (single-writer / multi-reader-process) design. A complete, red-teamed design for
read-only reader processes that serve lock-free snapshots of the last durable checkpoint
(atomic-rename publication + background ArcSwap refresh), preserving the single-process
lock-free invariant. Design-only — docs/design/swmr-multiprocess.md.
Many-thread vocab soak (tests/vocab_shared_lockfree_soak.rs) — writers/readers/checkpoint/
eviction/snapshot+fork churners on one Arc<PersistentVocabARTrie> with a no-lost-write oracle
audited in-memory and after reopen; plus reverse-map + reopen assertions added to
tests/vocab_shared_lockfree_concurrency.rs.
PersistentVocabARTrie
checkpoints silently corrupted and lost ALL data on reopen once the serialized image
spanned more than a few arenas (~a few thousand terms). Root cause: the generic
MmapDiskManager/IoUringDiskManager::allocate_block reads the free-list head from the
standard FileHeader at block-0 bytes 32..40 — which exactly aliases the vocab VOCB
header's checkpoint_lsn field. After the first checkpoint wrote a non-zero
checkpoint_lsn, allocate_block misread it as a free-list head and returned a bogus
block_id (checkpoint_lsn >> 40, i.e. 0), overwriting the header block. Fixed by gating
the free-list on the FileHeader magic in both backends' allocate_block/free_block
(custom-header files, which never free blocks, correctly skip the free-list). Regression
test: tests/vocab_scale_checkpoint_repro.rs (base checkpoint + fork_to at 12k terms);
also exercised under load by tests/vocab_shared_lockfree_soak.rs.SharedVocabARTrie is now lock-free (Arc<PersistentVocabARTrie>). The F4
lock-collapse (already shipped for byte/char) now covers vocab: the alias dropped
its outer parking_lot::RwLock, so concurrent readers and writers on a shared
vocabulary handle no longer serialize against each other — the inner trie was
already &self + lock-free (overlay CAS, DashMap forward/reverse caches, atomic
counters, epoch-pinned reads). Backward-compatible .read()/.write() are
preserved by the no-lock SharedTrieAccess shim. eviction_coordinator moved to a
std::sync::Mutex and durability_policy to an AtomicEnumCell (both now mutated
through the bare Arc handle), and a new checkpoint_lock serializes concurrent
checkpoint() calls (loom- and TLA+-verified deadlock-freedom).PersistentVocabARTrie::clone is now a lossless in-memory snapshot. It
previously produced a hollow shell (reported len() == N yet every lookup returned
None). It now Arc-shares the immutable overlay's frozen root (O(1), point-in-time)
and materializes the forward/reverse caches by walking that root, so the snapshot is
internally consistent even under concurrent mutation of the source. The snapshot is
detached from storage (read-only and Drop-safe).PersistentVocabARTrie::fork_to(path) — create a fully independent, writable,
on-disk copy (its own file + WAL) by replaying every (term, id) pair
id-preservingly. Preserves the exact id frontier (including burned-id gaps), start
index, and durability policy; refuses to clobber an existing path; and removes
partial files on error. Works on any backend, including a storage-less snapshot.PersistentVocabARTrie::snapshot() — a named alias for the lossless snapshot
clone, for call-site intent.memmap2 0.9.10 → 0.9.11 — RUSTSEC-2026-0186, unchecked pointer offset. This is
the mmap backend under the entire persistent ARTrie, so the exposure sat on every
disk-backed read path. The declared floor is now 0.9.11, not 0.9.crossbeam-epoch 0.9.18 → 0.9.20 — RUSTSEC-2026-0204, invalid pointer dereference
in the fmt::Pointer impl for Atomic/Shared. Reached via rayon's
work-stealing deque; pinned by raising the rayon floor to 1.12.anyhow 1.0.102 → 1.0.104 — RUSTSEC-2026-0190, unsoundness in
Error::downcast_mut(). Transitive via prost-derive.paste → pastey 0.2 — RUSTSEC-2024-0436, unmaintained and archived with no
fixed version. Declared as a package rename so the paste::paste! call sites are
unchanged. Dev-dependency only.bincode remains on 2.0 (RUSTSEC-2025-0141, unmaintained, no fixed version).
It is now pinned >=2.0, <3: bincode 3.0.0 is a tombstone release shipping only
a README and a lib.rs containing a compiler error, so upgrading to it breaks the
build by design. Migration to the maintained bincode-next fork is tracked
separately and gated behind a byte-level regression net.pathmap 0.2.2 required 1.88, bincode 2.0.1 and lru 0.18
required 1.85, and even default-feature log/thiserror required 1.71. Clippy had
been reporting the discrepancy directly (an existing div_ceil call in
overlay/codec.rs was flagged as "stable since 1.73" against the declared 1.70).
The msrv CI job moves to a matching 1.95 toolchain; cargo +1.95.0 build --all-features is verified to succeed.rustc-hash 1.1 → 2.1,
sysinfo 0.37 → 0.39.6, prost/prost-build 0.13 → 0.14.4, and the
dev-dependencies criterion 0.5 → 0.8 and rand 0.8 → 0.9.BloomFilter serialized under rustc-hash 1.x is not readable under 2.x.
rustc-hash 2.0 replaced the fxhash algorithm, and BloomFilter persists its raw bit
vector rather than its keys, so bits set by the old hash and queried by the new one
yield false negatives. Nothing inside this crate is affected — DawgCore's
bloom_filter and suffix_cache are both serde(skip), and the on-disk ARTrie
format uses xxh3 — but a downstream crate that serialized a BloomFilter standalone
must rebuild it from its source terms rather than migrating the bits. Documented on
the type.rand's value stream differs across major versions,
so although every generator here is a fixed-seed StdRng and runs stay deterministic
within a version, the generated term corpora after this change are not the same
inputs behind the figures recorded in docs/benchmarks/ and docs/experiments/.
Treat those as a separate experimental condition rather than a regression.rand, rand_core, rand_chacha and ppv-lite86 collapsed to one
copy each (choosing rand 0.9 over 0.10 specifically because proptest already
pulls 0.9), getrandom went from three copies to two, and the stale itertools 0.10
pulled by criterion 0.5 is gone.PersistentVocabARTrie mapped mutation traits now perform real
index-aware writes. MutableMappedDictionary::insert_with_value and
update_or_insert on both PersistentVocabARTrie and SharedVocabARTrie
now treat the supplied u64 value as an explicit requested vocabulary index
for new terms, while preserving immutable indices for existing terms.
union_with inserts missing terms with their source indices and calls the
merge callback only for conflicts, warning if a merge result would require
remapping an existing index. Focused trait-honesty tests now pin requested
index insertion, index-conflict rejection, union index preservation, and
existing-index immutability.PersistentVocabARTrie::sync_to_disk_async now advances synced_lsn.
The completed-handle sync path now records the LSN returned by the WAL sync,
matching sync() / rotate_wal() durability accounting. Vocab sync tests
assert that repeated syncs advance the public synced frontier after later WAL
writes.DynamicDawgU64 compaction/minimization now publish real rebuilt graphs.
The u64 DAWG no longer clears the compaction flag as a no-op: compact() and
minimize() snapshot visible final sequences, rebuild a compact graph,
intern equivalent non-final valueless suffix subgraphs, and atomically publish
the rebuilt root edge list. Reads remain wait-free; compaction briefly gates
writers during publication to avoid losing concurrent writes. Regression
tests cover dead-branch removal, value preservation, empty-sequence values,
and concurrent writer/compactor interleavings.PersistentSuffixAutomaton{,Char},
PersistentSuffixTree{,Char}, and PersistentScdawg{,Char} now append a
prepared native WAL operation, publish rebuilt immutable graph snapshots with
pointer-identity CAS, and append a commit marker before acknowledging
retryable writes (insert, insert_with_value, remove, clear,
compact). Checkpoints retain active WAL records and record a native
operation watermark so recovery skips checkpoint-folded operations and ignores
uncommitted CAS-loser prepares. Under continuous writer churn, checkpoint may
skip image publication rather than blocking writers; retained WAL replay
remains authoritative. The mapped update contract now uses a retry-safe
Fn(&mut V) updater so update_or_insert can join the same CAS publication
path without a writer lock.PersistentARTrieU64Compact durability aligned with the byte/char
Order-A overlay path. Native u64 now uses the shared WAL overlay regime,
appends CommitRank after the winning CAS publication, seeds and advances
CommittedWatermark, records checkpoint checkpoint_lsn, and retains WAL
tail records for recovery. The implementation keeps the native
OverlayNode<U64Key<4>, V> architecture and u64 CX checkpoint image; the old
native bincode snapshot/WAL path remains available only from git history.
Recovery tests now cover checkpoint-tail replay and CommitRank generation
ordering. Fixed-sample benchmarks added the encoded parallel reader/writer
control; pgmcp experiments 53-55 accepted native prefix-4 lookup,
parallel read/write latency, and prefix-4 checkpoint-density hypotheses.
Raw samples are in
docs/experiments/persistent-u64-watermark-commitrank-2026-06-13.md;
pgmcp artifact 132 stores the full benchmark output.TrieRef (lock-free, $O(1)$-from-focus).
PathMapNode / PathMapNodeChar are now type aliases of the new
TrieRefNode / TrieRefNodeChar (pathmap::core) over a sealed TrieRefLike
handle. PathMapDictionary{,Char}::root() takes an $O(1)$ copy-on-write
snapshot and queries run lock-free over it (snapshot isolation), replacing
the former lock-per-operation, root-replay node ($O(n^2)$ byte-steps + n lock
round-trips to walk a term of length n). PathMapZipper is likewise reworked
onto TrieRefZipper. Fields were private, so there is no downstream breakage.pathmap, dynamic_dawg, double_array_trie, suffix_automaton, scdawg,
and persistent_artrie (with char/, core/, vocab/) — each as
family/{mod,ascii,char,…}.rs, with mod.rs re-exporting the family's public
types. The crate-root re-exports and prelude are preserved; no
compatibility shims remain for the old flat module paths.56-61 for native parallel read/write latency;
all 36 raw metric x arm sample vectors are stored in pgmcp data table
libdictenstein.persistent_suffix_native_benchmark_sample_sets, and the
result summary is recorded in
docs/experiments/persistent-suffix-native-2026-06-13.md.persistent-artrie implementation set:
PersistentARTrie{,Char}, PersistentARTrieU64Compact,
PersistentARTrieU64Prefix3Compat, PersistentVocabARTrie, and native
persistent suffix automaton/tree/SCDAWG variants. The docs distinguish ARTrie
overlay publication from suffix graph prepared/commit CAS publication and
summarize the appended u64 benchmark artifacts (111, 112) without
replacing historical ledger data.pathmap::snapshot):
PathMapSnapshot / PathMapRef (and …Char variants) wrap a borrowed or
$O(1)$-snapshotted PathMap so a caller that already holds one (e.g. MORK's
Space.btm) can fuzzy-query it with no copy and no lock. Constructors:
from_map, from_map_ref, from_trie_ref, from_read_zipper. Plus
PathMapDictionary{,Char}::snapshot() and a borrowed PathMapZipperRef<'a>.pathmap requirement widened to >=0.2.2, <0.4 (publishable — resolves to
0.2.2 on crates.io; accepts a local 0.3 via [patch.crates-io]). Verified to
compile against PathMap 0.3.0 (0 API errors).MmapDiskManager keeps mmap as the production fast path, but under
cfg(miri) it opens the same file format with positional file I/O because
Miri does not support file-backed mappings. This lets
RUN_MIRI=1 FORMAL_MIRI_TOOLCHAIN=nightly run the documented vocab
persistence, swizzled-pointer, and buffer-manager checks instead of failing
during sysroot/cache or mmap setup. build.rs declares cfg(miri) for
unexpected_cfgs hygiene..cargo/config.toml: scoped target-cpu=native down to
target-feature=+aes,+sse2 (the minimum gxhash requires). Native
builds remain available via RUSTFLAGS="-C target-cpu=native". The
previous unconditional setting silently produced binaries that emitted
illegal-instruction signals on slightly older x86_64 hardware..github/workflows/ci.yml replaces coverage.yml with a
full-coverage CI matrix:
-D warnings.RUSTDOCFLAGS=-D warnings (broken intra-doc links fail CI).--check.rust-version in Cargo.toml).make in formal-verification/rocq/).cargo fmt applied across the workspace; ~200 files normalized.
CI now enforces drift via cargo fmt --check.0.12 → 0.18. API unchanged at our call site
(LruCache::new(NonZeroUsize)); 7 reverse_cache tests still pass.src/serialization/serde_helpers.rs: extracted shared
serialize_arc_vec / deserialize_arc_vec / serialize_arc_vec_vec /
deserialize_arc_vec_vec (previously byte-for-byte duplicated across
double_array_trie.rs and double_array_trie_char.rs). Both DAT files
now use them.src/sync_compat.rs: std-fallback RwLock wrapper now has
try_read / try_write matching parking_lot's Option<Guard> shape.
Single canonical type per build; the audit's "two RwLock types" issue
resolved.src/union_zipper/: 1632-LOC union_zipper.rs split into 4 modules
(merge_strategies.rs, lattice.rs, semiring_lattice.rs, plus
mod.rs for the zipper + iterator + extension traits + tests). All
external use libdictenstein::union_zipper::{FirstWins, LatticeJoin, …} call-sites continue to work via pub use re-exports.DictionaryFactory expanded from 4 backends → 11
(DoubleArrayTrie{,Char}, DynamicDawg{,Char,U64},
SuffixAutomaton{,Char}, Scdawg{,Char},
PathMapDictionary{,Char}). Persistent-ARTrie family excluded
(needs file paths). +1 test added for Unicode backends.*_with_values_char) for char-Unit
backends. Combined with the byte path (added in A3), bincode/json/
plaintext now round-trip (String, V) pairs for both Unit = u8 and
Unit = char backends. u64 (DynamicDawgU64) still has no
*_with_values path because u64 doesn't trivially round-trip through
String; needs format design.Scdawg<V>::get_value + MappedDictionary impls added for parity
with ScdawgChar. Both Scdawg variants now usable with the
value-preserving serializers and MappedDictionary callers.docs/dynamic_dawg/suffix_cache_bug.md documents why the
find_or_create_suffix cache in dynamic_dawg{,_char}.rs is
#[allow(dead_code)] (the dynamic-insertion path violates the cache's
endpoint-uniqueness invariant). Includes design candidates for
re-enabling.DoubleArrayTrie{,Char}::free_list and rebuild_threshold fields
documented as RESERVED-FOR-FUTURE; kept in the on-disk format for
back-compat.MutableDictionary docstring rewritten to call out the
complementarity with MutableMappedDictionary (set-like vs value-
aware; both needed; neither subsumes the other).ARTrieAtomicOps trait body commented out per CLAUDE.md (no impl
sites; signatures conflicted with ARTrie's own methods). Empty
#[deprecated] compatibility shim kept for back-compat.EvictableARTrie::{enable,disable,force}_eviction changed from
&mut self to &self (3 impl sites updated). The &mut self bound
was performative — impls already mutate through interior write guards.ARTrie::durability_policy return type points at
crate::persistent_artrie::core::durability::DurabilityPolicy
(canonical home); the byte-side pub use re-export is retained.ARTrie::iter_prefix_units sibling method added that preserves
Self::Unit typing (the old iter_prefix returns String, lossy for
non-byte impls). Default fallback round-trips through iter_prefix.BijectiveDictionary::get_term now returns Option<Cow<'_, str>>
(was Option<&str>). Drops the unsafe pointer dereference in
BijectiveMap. PersistentVocabARTrie / SharedVocabARTrie impls now
return reconstructed terms instead of unconditional None (which
silently violated the documented bijection invariant). New
tests/bijective_trait_invariant.rs covers all 3 impls.MappedDictionary::get_value broken default removed — was let _ = self.contains(term); None. Now required; all 15 in-tree impls already
provided one.MappedDictionary impls:
DictionaryFromTermsWithValues trait + extract_terms_with_values
helper + serialize_with_values / deserialize_with_values methods on
bincode/json/plaintext. The legacy serialize/deserialize path
silently dropped values (shipped Vec<String> over the wire). New
tests/serialization_value_roundtrip.rs covers DynamicDawg/DAT byte
variants, char variants, and a regression-guard for the legacy
drop-values behavior.SharedVocabARTrie warning-only methods were made visible as a
historical hardening step. At this point in the history, unsupported
methods emitted log::warn! instead of silently discarding non-default
arguments. This was later superseded by the Unreleased persistent-vocab change above:
insert_with_value, update_or_insert, and union_with now perform real
index-aware writes and are pinned by tests/vocab_trait_honesty.rs.FilterableValue::Atom associated type added; Vec<T> / HashSet<T>
/ SmallVec<A> get per-element semantics
(self.iter().any(predicate) / self.iter().all(predicate)) instead
of the previous "test the whole collection" behavior that made
matches_any and matches_all indistinguishable.extract_terms iterative rewrite prevents stack overflow on long
single-child chains. Bug found during implementation: the depth field
in the new explicit-stack frame must be captured BEFORE pushing the
descent byte (using AFTER caused the post-backtrack current_term to
retain the wrong prefix). New 50k-deep DynamicDawg test in
serialization/mod.rs..unwrap() → .expect("invariant: …") in production code
(suffix_automaton{,_char}.rs, dynamic_dawg_char.rs) with forensic
messages tied to the actual invariant.transducer doc-rot fixed: 6 rust,ignore doc-tests in
suffix_automaton{,_char}.rs rewritten to use the real API +
libdictenstein::prelude::*, with a pointer to where the transducer
actually lives (downstream in liblevenshtein). All 6 now run./// ```` doc fence atprefetch_api.rs:14fixed (brokecargo test --doc` whenever the file was visited).formal-verification/VERIFICATION_RESULTS.md and README.md
refreshed to reflect 15 .v files / 232 propositions / 0 Admitted /
0 Axiom across the Rocq tree (commits b7630ad + efe1943).simd, scdawg-bloom, scdawg-simd
(all had zero #[cfg(feature = …)] references in code).group-commit feature relabeled EXPERIMENTAL with cross-reference
to docs/persistence/group-commit.md. Behavior unchanged.docs/sanitizers/
with date-stamped filenames + scripts/run-sanitizers.sh regen script.build.rs emits cargo:rerun-if-changed=proto/libdictenstein.proto
(under #[cfg(feature = "protobuf")])..gitignore for the formal-verification/rocq/**/.*.aux files.src/lib.rs backend table refreshed: 11 in-memory + 3 disk-backed
backends, all linked.DictionaryFactory.docs/persistence/mmap-architecture.md refreshed to reference the
post-Phase-6 file layout (persistent_artrie/core/{disk_manager, buffer_manager, swizzled_ptr, block_storage, io_uring_disk_manager, wal, durability}.rs).docs/algorithms/implementations/scdawg.md and
docs/algorithms/implementations/bijective.md.rust,ignore doc-tests promoted to compile-checked
rust,no_run (the conversion script wraps ?-using bodies in a
hidden fn main() -> Result<…>; the remaining 123 use API patterns
that need context-specific per-block rewrites and stay as
rust,ignore).Pre-plan: 2006 passing. Post-plan: 2288 passing (+282).
simd, scdawg-bloom, scdawg-simd). No-op for any
downstream consumer that wasn't getting any SIMD/bloom-filter behavior from
them anyway.group-commit: relabeled from "REJECTED: causes regression
on NVMe" to "EXPERIMENTAL" with explicit benchmark cross-reference. The
feature itself is unchanged; the description is now honest about its status.
See docs/persistence/group-commit.md.README.md Features section: now lists all 11 real features
(was: 6, with 3 referring to dropped flags).build.rs: emits cargo:rerun-if-changed=proto/libdictenstein.proto
under #[cfg(feature = "protobuf")], so cargo correctly rebuilds the
generated protobuf code when the schema changes.formal-verification/VERIFICATION_RESULTS.md and
formal-verification/README.md: refreshed to reflect the current state —
15 .v files, 232 propositions, 0 Admitted / 0 Axiom / 0 Parameter.
The "Admitted Theorems", "Proven Theorems" and "Future Work" sections now
match the actual proof tree (commits b7630ad and efe1943).docs/sanitizers/,
with date-stamped filenames and a scripts/run-sanitizers.sh regen script..gitignore: added formal-verification/rocq/**/.*.aux to silence the
cosmetic dot-prefix .aux files that Rocq leaves behind.group-commit regresses on NVMe and where it's still
expected to help./home/dylon/.claude/plans/rust-backtrace-1-rust-log-debug-cargo-n-purrfect-lemon.md
(7 phases: Hygiene → Tier A correctness → Tier B API parity → Tier C
architecture/dedup → CI/build infra → Documentation → Verification).Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |