intern-lang 1.0.0

Fast string and symbol interning - identifier comparisons become integer comparisons.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

# intern-lang v0.3.0 — Concurrent interner

**Interning goes parallel.** v0.3.0 adds `ConcurrentInterner`, a thread-safe
interner many threads can intern into at once while sharing one symbol space, and
the `Lookup` trait that both interners implement. It is additive — the storage,
the deduplication, and the symbol stability guarantees are exactly those of the
single-threaded `Interner`, whose hot path is untouched. No breaking changes.

## What is intern-lang?

A string interner. It maps each distinct string to a small, copyable `Symbol`,
stores the bytes once in a contiguous backing store, and hands back integer
handles so that comparing two names is an integer comparison rather than a byte
walk. It is the deduplication layer beneath the lexer and the symbol table.

## What's new in 0.3.0

### `ConcurrentInterner` — one symbol space, many threads

`ConcurrentInterner` wraps `Interner` in an `RwLock` and exposes the same
operations through `&self`, so a pool of lexer or parser threads can share one
symbol space behind an `Arc`.

```rust
use std::sync::Arc;
use std::thread;

use intern_lang::ConcurrentInterner;

let interner = Arc::new(ConcurrentInterner::new());

let handles: Vec<_> = (0..8)
    .map(|_| {
        let interner = Arc::clone(&interner);
        thread::spawn(move || interner.intern("shared"))
    })
    .collect();

let symbols: Vec<_> = handles.into_iter().map(|h| h.join().unwrap()).collect();

// All eight threads agree on one symbol; "shared" was interned exactly once.
assert!(symbols.iter().all(|&s| s == symbols[0]));
assert_eq!(interner.len(), 1);
```

It requires the `std` feature (on by default); the crate stays `no_std` for the
single-threaded `Interner` when `std` is off. The surface mirrors `Interner`:
`new`, `with_capacity`, `intern`, `get`, `resolve_with` (zero-copy, runs a closure
under the read lock), `resolve` (owned `String`), `len`, `is_empty`. It is
`Send + Sync`.

### Correctness under contention, proven not assumed

Interning takes a two-step path. A string already present is found under a
**shared read lock**, so the common warm-cache case runs concurrently across
threads with no exclusive access. Only a genuinely new string escalates to the
**exclusive write lock**, and the insert re-checks for the string while holding
it — so two threads racing to intern the same new string still resolve to one
symbol: the writer that loses the race finds the winner's entry instead of minting
a duplicate. The `RwLock`'s exclusivity is what makes "no duplicate symbols for
the same string" hold, with no custom lock-free protocol to get wrong.

This is covered by contention tests in `tests/concurrent.rs`: sixteen threads
intern a heavily overlapping set of five hundred strings (two thousand interns per
thread), then every thread's symbol map is checked to agree string-for-string,
and the interner's final size is asserted to be exactly the distinct count — one
symbol per string, no duplicates. A second test interns disjoint per-thread
namespaces across eight threads and round-trips every symbol through `resolve`. A
poison-recovery test confirms a panic elsewhere does not wedge the interner.

### `Lookup` — the shared read seam

Both interners implement `Lookup`, the read-side contract, so generic code can
accept either:

```rust
use intern_lang::{ConcurrentInterner, Interner, Lookup};

fn name_len<L: Lookup>(interner: &L, s: &str) -> Option<usize> {
    let sym = interner.get(s)?;
    interner.resolve_with(sym, str::len)
}

let mut single = Interner::new();
let _ = single.intern("alpha");
assert_eq!(name_len(&single, "alpha"), Some(5));

let shared = ConcurrentInterner::new();
let _ = shared.intern("beta");
assert_eq!(name_len(&shared, "beta"), Some(4));
```

Interning is deliberately *not* on the trait: the two interners disagree on how it
is called (`&mut self` versus `&self`), and forcing a common signature would tax
the single-threaded hot path with synchronisation it does not need. Resolution is
expressed as `resolve_with` — a closure run against the borrowed string — because
a concurrent interner can only expose the bytes while it holds its read lock.

### The single-threaded hot path is untouched

The concurrent backend is a separate type wrapping `Interner`; the single-threaded
`intern`/`resolve` path gained no synchronisation, no branches, and no fields. The
only addition to `Interner` is `resolve_with`, a thin wrapper over `resolve` for
the trait. Both exit criteria for this milestone — correct under contention, and
no tax on the single-threaded path — are met.

### Benchmarks — contention measured

`benches/bench.rs` adds a `concurrent_intern_existing` group that measures
warm-path throughput at 1, 4, and 8 threads. On the development machine
(Windows x86_64, Rust stable), eight threads sustain roughly **4× the
single-thread intern throughput**, since hits are served under a shared read lock;
the gap from a perfect 8× is read-lock bookkeeping and per-iteration thread setup,
not write serialisation. If a write-heavy workload ever shows write contention,
the storage can be sharded behind the same surface without an API change.

## Breaking changes

**None.** `ConcurrentInterner` and `Lookup` are additive, and
`Interner::resolve_with` is a new method.

## Verification

Run on Windows x86_64, Rust stable 1.95.x and MSRV 1.85; the same commands run on
Linux (WSL2 Ubuntu) and across the CI matrix (Linux / macOS / Windows × stable /
1.85):

```bash
cargo fmt --all -- --check
cargo clippy --all-targets -- -D warnings
cargo clippy --all-targets --all-features -- -D warnings
cargo test
cargo test --all-features
cargo build --no-default-features
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo +1.85 test --all-features
cargo audit
cargo deny check
```

All green. Counts at this tag:

- Default features: 24 unit + (9 + 5 + 3) integration/property + 22 doctests.
- `--no-default-features`: the single-threaded interner builds clean as `no_std`;
  `ConcurrentInterner` is correctly absent.

## What's next

- **0.4.0 — serde, exhaustion contract, feature freeze.** Optional `serde` for
  `Symbol`, a defined non-panicking symbol-space-exhaustion result property-tested
  at the boundary, and a declared frozen public surface in `docs/API.md`.

## Installation

```toml
[dependencies]
intern-lang = "0.3"
```

MSRV: Rust 1.85.

## Documentation

- [README](https://github.com/jamesgober/intern-lang/blob/main/README.md)
- [API Reference](https://github.com/jamesgober/intern-lang/blob/main/docs/API.md)
- [CHANGELOG](https://github.com/jamesgober/intern-lang/blob/main/CHANGELOG.md)

---

**Full diff:** [`v0.2.0...v0.3.0`](https://github.com/jamesgober/intern-lang/compare/v0.2.0...v0.3.0).
**Changelog:** [`CHANGELOG.md`](https://github.com/jamesgober/intern-lang/blob/main/CHANGELOG.md#030---2026-06-20).