hashrope
A BB[2/7] weight-balanced binary tree augmented with polynomial hash metadata at every node.
Zero dependencies by default. no_std + alloc compatible. Rust 2021 edition.
The optional bigint feature adds Python-compatible arbitrary-precision hashes
and compressed rope lengths in Rust 0.3.2. The compatible 0.3 release line
retains existing consumers' dependency requirements. See
PARITY.md for the Python API matrix, exact fixture provenance,
downstream compatibility checks, and remaining adoption limitations.
What it does
hashrope is a rope data structure where every node carries a polynomial hash over a Mersenne prime field. This enables:
- O(log w) concat and split with strict BB[2/7] weight-balance via recursive join
- O(log q) repetition encoding via
RepeatNode— represents^qwithout materializing - O(log w) substring hashing without allocating new nodes
- O(1) whole-sequence hash at any node
- Sliding windows with eviction and opt-in arena reclamation
The default u64 API uses Mersenne modular reduction by bit folding. The optional bigint API uses BigUint modular arithmetic. Nodes live in contiguous arenas without reference counting or atomic operations.
Install
[]
= "0.3.2"
Quick start
use Arena;
let mut a = new;
// Build ropes from byte slices
let hello = a.from_bytes;
let world = a.from_bytes;
// Concat: O(log w)
let hw = a.concat;
assert_eq!;
assert_eq!;
// Split at any byte position: O(log w)
let = a.split;
assert_eq!;
assert_eq!;
// Rejoin preserves hash
let rejoined = a.concat;
assert_eq!;
// Repeat: O(log q) — no materialization
let pattern = a.from_bytes;
let repeated = a.repeat; // "ab" × 10⁶
assert_eq!;
// Substring hash without allocation: O(log w)
let h = a.substr_hash; // hash of "hello"
assert_eq!;
// Validate BB[2/7] invariants (for debugging)
a.validate;
Node types
| Type | Description | Weight |
|---|---|---|
Leaf(data) |
Raw byte slice | 1 |
Internal(left, right) |
Binary node with BB[2/7] balance | w(left) + w(right) |
Repeat(child, q) |
Virtual repetition, q ≥ 2 | w(child) × q |
Arena allocation
All nodes live in a single Arena. Node references are u32 indices. The arena is dropped as a unit — no per-node deallocation. This gives cache-friendly traversal and zero-cost structural sharing.
let mut a = new;
let node = a.from_bytes;
println!;
Sliding window
For streaming applications, SlidingWindow maintains a bounded-size logical
window. The existing constructors preserve arena handles and retain evicted
allocations. The new new_bounded constructor also reclaims arena storage:
use ;
let mut sw = new_bounded;
sw.append_bytes;
// Oldest bytes are evicted when the window exceeds d_max + m_max
Reclamation copies the retained graph after eviction, preserving shared nodes
and compressed repeats. Its cost depends on the retained graph and leaf data;
it does not expand repeated bytes. Node IDs observed through arena() may
change on append in this opt-in mode. Calling arena_mut() permanently disables
reclamation so handles allocated by the caller remain valid. Keep the existing
constructors when stable arena handles are required.
Arbitrary precision
Enable bigint on the dependency:
[]
= { = "0.3.2", = ["bigint"] }
#
bigint::PolynomialHash, bigint::Arena, its rope wrappers, and
bigint::SlidingWindow use BigUint for hashes, moduli, lengths, positions,
and repetition counts. They support the 127-bit Python profile and wider
Mersenne moduli. This feature uses num-bigint and num-traits without their
std features. The original u64 types, enum layouts, and default profile
remain unchanged. BigUint values can be displayed as decimal strings without
precision loss; applications own any external serialization format.
Byte and compatibility contracts
All inputs and offsets are bytes. Text callers explicitly choose an encoding
(for example UTF-8 with str::as_bytes()); Hashrope does not normalize Unicode.
Splitting inside a UTF-8 code point preserves exact bytes, although either half
may not decode as text. Substring queries take start and length, not end.
Supply a valid in-bounds range. The new bigint API rejects malformed ranges;
the existing API retains its established range behavior.
Both APIs default to p = 2^61 - 1, base 131, with the byte + 1 polynomial
convention. The u64 API checks representational limits before storing node
metadata and panics on overflow. Materializing a compressed rope requires
addressable memory. Hashes are probabilistic fingerprints, not cryptographic
digests or collision-free equality proofs.
Rust lazy arenas remain available. Arena::hash and rope_hash return
LAZY_SENTINEL until materialization; call ensure_hash(root_id) or query the
full range with substr_hash first. The new bigint API computes hashes eagerly.
Polynomial hash properties
The hash function is a polynomial rolling hash over GF(2⁶¹ − 1):
- Homomorphic under concatenation:
H(A‖B) = H(A)·x^|B| + H(B) - Homomorphic under repetition:
H(s^q) = H(s)·Φ(q, x^|s|)where Φ is computed in O(log q) - Collision behavior: fixed-base polynomial fingerprints can collide; equal hashes do not prove byte equality.
Benchmarks
Uses Criterion.rs with HTML reports.
Changelog
See CHANGELOG.md.
License
MIT