Hands-On: Mini Symbol Table with Safe Interning (Advanced)

Context: what you are building
Implement a symbol table that maps identifiers to unique canonical strings for a small DSL or config parser. The table should intern only from a bounded vocabulary, avoid interning arbitrary unbounded inputs, and expose fast reference comparisons for tokens.

Public API (a signature sketch, not compilable code: the bodies are yours to write)

public sealed class SymbolTable
{
    public SymbolTable(IEnumerable<string> allowed); // seed with a bounded set
    public string Canonicalize(string text);         // returns the table's canonical instance if allowed; else returns original
    public bool AreSameSymbol(string a, string b);   // correct for ANY two inputs, fast when both are canonical
}

Hints - Mental model (who does what)

Maintain a HashSet of allowed tokens to bound the vocabulary. Intern each vocabulary entry once, in the constructor.
For allowed tokens, hand back the instance the set is already storing. HashSet<string>.TryGetValue(text, out var canonical) does exactly that, so a parser loop never touches the process-wide intern pool again.
For everything else, return the original text untouched to avoid growing the pool.
Because of that last rule, a reference compare alone is not a correct symbol test: two equal identifiers built at run time are different references and the same symbol. AreSameSymbol has to say so.

Hints - Steps with checkpoints

Step A: Construct with a normalized HashSet (e.g., StringComparer.Ordinal).

Step B: In Canonicalize, look the text up with TryGetValue and return the stored instance; return the input unchanged when it is not there.

Step C: AreSameSymbol canonicalizes both inputs, tries ReferenceEquals as the fast path, and falls back to string.Equals(ca, cb, StringComparison.Ordinal). The fallback is not belt and braces: without it, two identical out-of-vocabulary identifiers are reported as different symbols, which is the case a parser hits most often.Checkpoint: print four things and check all four. (1) ReferenceEquals(Canonicalize(new string("IF")), Canonicalize("IF")) is True: allowed tokens collapse to one reference. (2) AreSameSymbol("IF", "ELSE") is False. (3) string.IsInterned(Canonicalize("junk-" + Guid.NewGuid())) is null: disallowed tokens did not grow the pool. (4) with u1 and u2 two runtime-built copies of the same identifier that is not in the vocabulary, ReferenceEquals(u1, u2) is False while AreSameSymbol(u1, u2) is True. If (4) prints False, your AreSameSymbol is a reference compare and it is wrong.

Hints - Validation & errors

Guard allowed against null.
Choose StringComparer.Ordinal for stable, culture-agnostic symbol identity.

Hints - Pitfalls

Interning everything (memory leak risk).
Re-interning on every lookup. The constructor already did it; a per-token string.Intern call hits process-wide shared state with its own synchronization, inside your parser’s hot loop.
Using culture-sensitive comparisons for symbols.
Assuming ReferenceEquals implies equal content without prior canonicalization.
And the converse, which is the one that bites: assuming that after canonicalization, different references imply different content. They do not, for anything outside the vocabulary.

Hints - TODO Skeleton

using System;
using System.Collections.Generic;

public sealed class SymbolTable
{
    private readonly HashSet<string> _allowed;

    public SymbolTable(IEnumerable<string> allowed)
    {
        // HINT: validate; create HashSet with StringComparer.Ordinal; for each token -> string.Intern and add
        throw new NotImplementedException(); // TODO
    }

    public string Canonicalize(string text)
    {
        // HINT: _allowed.TryGetValue(text, out var canonical) ? canonical : text
        //       TryGetValue returns the STORED instance, so no per-call string.Intern.
        throw new NotImplementedException(); // TODO
    }

    public bool AreSameSymbol(string a, string b)
    {
        // HINT: canonicalize both, then ReferenceEquals as the fast path,
        //       falling back to string.Equals(..., StringComparison.Ordinal).
        //       The fallback is what makes this correct for identifiers, which are
        //       never in the keyword vocabulary.
        throw new NotImplementedException(); // TODO
    }
}

0% Complete