Struct Interner 

pub struct Interner { /* private fields */ }

A single-threaded string interner.

Interner maps each distinct string to a small Symbol, stores the bytes exactly once in a contiguous buffer, and hands back integer handles. Interning a string it has already seen is a hash lookup with no allocation and no copy; resolving a symbol borrows the original bytes straight out of the buffer.

Design

Bytes live once, appended end to end in a single String. A symbol is an index into a side table of (start, len) spans into that buffer, so a symbol is four bytes regardless of how long its string is. Deduplication runs through an open-addressing hash index that stores symbol ids, not strings, so it adds no second copy of the bytes. The buffer only ever appends and the span table only ever grows, so a symbol issued early keeps resolving to the same string for the interner’s whole lifetime, including after either structure reallocates — resolve recomputes the slice from the current buffer on each call rather than holding a borrowed pointer, so growth can never dangle a previously issued symbol.

Capacity

Symbol ids span 1..=u32::MAX, so an interner holds up to u32::MAX distinct strings. Reaching that bound requires interning over four billion distinct strings, which exhausts memory long before the id space — the span table alone would need tens of gigabytes. A defined, non-panicking exhaustion result is scheduled for a later release; until then the boundary is unreachable for any input that fits in memory.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();

let print = interner.intern("print");
let again = interner.intern("print");
let read = interner.intern("read");

// Deduplication: the same string always yields the same symbol.
assert_eq!(print, again);
assert_ne!(print, read);

// Resolution borrows the stored bytes back out.
assert_eq!(interner.resolve(print), Some("print"));
assert_eq!(interner.len(), 2);

Implementations

impl Interner

pub fn new() -> Self

Creates an empty interner.

No allocation happens until the first string is interned, so an interner that is created but never used costs nothing.

Examples

use intern_lang::Interner;

let interner = Interner::new();
assert!(interner.is_empty());

pub fn with_capacity(capacity: usize) -> Self

Creates an empty interner sized to hold about capacity distinct strings before the dedup index has to grow.

This pre-allocates the span table and the hash index. The backing byte buffer is left to grow on demand, since the total byte length cannot be predicted from a string count. Use this when the rough number of distinct identifiers is known ahead of time — for example, sizing from a previous compilation — to avoid a series of reallocations during warm-up.

Examples

use intern_lang::Interner;

let mut interner = Interner::with_capacity(1_024);
let sym = interner.intern("identifier");
assert_eq!(interner.resolve(sym), Some("identifier"));

pub fn intern(&mut self, s: &str) -> Symbol

Interns s, returning its Symbol.

If s has been interned before, the existing symbol is returned and nothing is allocated or copied. Otherwise the bytes are appended to the backing store, a fresh symbol is assigned, and that symbol is returned. Either way the result round-trips: interner.resolve(interner.intern(s)) is always Some(s).

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
let a = interner.intern("while");
let b = interner.intern("while");
let c = interner.intern("until");

assert_eq!(a, b);            // deduplicated
assert_ne!(a, c);            // distinct strings, distinct symbols
assert_eq!(interner.resolve(a), Some("while"));

Symbol-space bound

An interner issues at most u32::MAX distinct symbols. intern is the infallible path for the overwhelming common case where that bound is never approached; at the bound it saturates — returning the highest symbol without adding the string — rather than panicking. Use try_intern when you need the exhaustion reported as a Result instead.

pub fn try_intern(&mut self, s: &str) -> Result<Symbol, InternError>

Interns s, returning its Symbol, or an error if the symbol space is exhausted.

This is the fallible counterpart to intern. It behaves identically — deduplicating, allocation-free on a repeat hit — except that interning a new string when the symbol space is full returns InternError::SymbolSpaceExhausted instead of saturating. Interning a string that already exists never fails, even at the bound.

Errors

Returns InternError::SymbolSpaceExhausted when s is new and the interner has already issued all of its symbols. This is unreachable for any input that fits in memory; the method exists so a caller that must account for the boundary can do so explicitly.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
let sym = interner.try_intern("identifier").expect("space available");
assert_eq!(interner.resolve(sym), Some("identifier"));

// Re-interning the same string yields the same symbol and never errors.
assert_eq!(interner.try_intern("identifier"), Ok(sym));

pub fn get(&self, s: &str) -> Option<Symbol>

Looks up s without interning it, returning its Symbol if it is already present.

Unlike intern, this never mutates the interner: a miss returns None rather than allocating a new symbol. Use it to ask “has this name been seen?” without growing the symbol space.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
let sym = interner.intern("declared");

assert_eq!(interner.get("declared"), Some(sym));
assert_eq!(interner.get("undeclared"), None);

pub fn resolve(&self, symbol: Symbol) -> Option<&str>

Resolves symbol back to the string it names, borrowing the bytes from the backing store.

Returns Some(&str) for any symbol this interner issued, and None for a symbol whose id is out of range — most often one issued by a different interner. A symbol from another interner whose id happens to fall in range resolves to this interner’s string at that id; symbols are only meaningful with the interner that produced them.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
let sym = interner.intern("resolved");
assert_eq!(interner.resolve(sym), Some("resolved"));

// A symbol from an interner that issued more symbols is out of range here.
let mut other = Interner::new();
let _ = other.intern("a");
let high = other.intern("b");
assert_eq!(interner.resolve(high), None);

pub fn resolve_with<R, F>(&self, symbol: Symbol, f: F) -> Option<R>

where F: FnOnce(&str) -> R,

Runs f against the string symbol names, returning its result, or None if symbol is out of range.

This is the Lookup trait’s resolution form. For the single-threaded interner it is a thin wrapper over resolve — prefer resolve here, which hands back the borrowed slice directly. The closure form exists so the same generic code works against the ConcurrentInterner, where the borrow cannot outlive the read lock.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
let sym = interner.intern("identifier");
assert_eq!(interner.resolve_with(sym, str::len), Some(10));

pub fn len(&self) -> usize

Returns the number of distinct strings interned so far.

This is also the id that the next newly interned string will receive.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
assert_eq!(interner.len(), 0);
let _ = interner.intern("x");
let _ = interner.intern("x"); // duplicate, not counted again
let _ = interner.intern("y");
assert_eq!(interner.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if no strings have been interned.

Examples

use intern_lang::Interner;

let mut interner = Interner::new();
assert!(interner.is_empty());
let _ = interner.intern("x");
assert!(!interner.is_empty());

Trait Implementations

impl Debug for Interner

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Interner

fn default() -> Self

Returns the “default value” for a type.

impl Lookup for Interner

fn get(&self, s: &str) -> Option<Symbol>

Returns the symbol for s if it has already been interned, without interning it.

fn resolve_with<R, F>(&self, symbol: Symbol, f: F) -> Option<R>

where F: FnOnce(&str) -> R,

Runs f against the string symbol names, returning its result, or None if symbol is out of range for this interner.

fn len(&self) -> usize

Returns the number of distinct strings interned so far.

fn is_empty(&self) -> bool

Returns true if no strings have been interned.