Retrieve strings with a trie

A trie, or retrieval tree, shares common prefixes between keys. Each edge here represents one Unicode scalar. The path c → a → r represents "car"; a terminal marker distinguishes that stored key from a prefix that merely leads to "cart". The permanent root represents the empty string.

This example implements a set of strings directly in Plenty, including exact lookup, insertion, pruning deletion, prefix enumeration, and longest-prefix matching. It uses private node IDs rather than stored references. It is an educational implementation, not a new std API.

Run the example

From a repository checkout:

plenty book/src/design/examples/data-structures/trie/main.plenty
plenty book/src/design/examples/data-structures/trie/checks.plenty

Or save the implementation, demo, and test driver in the same directory, then run plenty main.plenty or plenty checks.plenty. These are the canonical source files compiled by the Rust regression tests. The demo below includes its source rather than maintaining another copy:

import trie

def main() -> Result[(), AllocError | IoError]:
    mut words = trie.create()?
    for key in ["", "car", "cart", "cat", "dog", "café", "cafe\u{301}", "猫", "猫咪"]?:
        drop(trie.insert(&mut words, key)?)
    print(trie.ordered(&words)?)?
    print(trie.has(&words, "car"), trie.has(&words, "ca"))?
    print(trie.has_prefix(&words, "ca"), trie.has_prefix(&words, "z"))?
    print(trie.with_prefix(&words, "car")?)?
    print(trie.with_prefix(&words, "猫")?)?
    print(trie.longest_prefix(&words, "cartwheel"))?
    print(trie.longest_prefix(&words, "unknown"))?
    print(trie.insert(&mut words, "car")?)?
    print(trie.remove(&mut words, "car"), trie.has(&words, "cart"))?
    print(trie.with_prefix(&words, "car")?)?
    print(trie.remove(&mut words, ""))?
    print(trie.longest_prefix(&words, "unknown"))?
    print(trie.valid(&words)?)?
    Ok(())

Expected output (the visually similar café spellings are distinct keys):

["", "café", "café", "car", "cart", "cat", "dog", "猫", "猫咪"]
True False
True False
["car", "cart"]
["猫", "猫咪"]
Option[str].Some("cart")
Option[str].Some("")
False
True True
["cart"]
True
Option[str].Nothing
True

Interface

All key, prefix, and text parameters borrow &str; the implementation keeps immutable string handles only when needed. Exact lookup, prefix existence, longest-prefix matching, and deletion allocate nothing. Insertion can allocate node storage; enumeration allocates its result list; validation allocates visitation marks and a worklist.

For an empty set, has_prefix(&tree, "") is False, enumeration returns an empty list, and longest_prefix returns Nothing. If "" is stored, longest-prefix matching returns at least Some(""), even when no nonempty key matches. Removing a key does not remove its longer descendants or shorter stored prefixes.

Unicode and ownership

Matching is exact and case-sensitive. There is no normalization, case folding, locale collation, or grapheme-cluster segmentation. "é" and "e\u{301}" follow different paths. A combining mark is its own edge; an emoji outside the basic multilingual plane is one scalar, not several byte edges. Embedded NUL and the maximum Unicode scalar are accepted like other valid string content.

Terminal nodes retain full keys as immutable str handles, so enumeration need not rebuild each string from its path. Returned strings remain valid after deletion, slot reuse, or dropping the trie. They share immutable storage rather than copying key bytes; an inserted heap-backed key can therefore keep that storage alive. See text storage and iteration.

Validation

The model driver compares the trie with a sorted-list set and independent prefix/longest-prefix scans. It checks 14,400 pairs of five-key insertion/deletion permutations, duplicates, missing removals, complete pruning and refill, plus 8,000 mixed operations over Unicode, case-sensitive, empty, NUL-containing, and prefix-related keys. A high-fanout case inserts 256 distinct scalar edges at both root and interior levels in reverse order, then alternates first/middle/last sibling deletion. A 10,000-scalar key checks returned strings after the original key, query, and trie owners are destroyed, with same-sized allocation pressure before comparison against independently rebuilt text.

The integration tests additionally sweep insertion and prefix-result allocation failures, retry failed insertion, disable allocation during lookup/pruning/reuse, and exercise a 100,000-scalar key under a 256 KiB native stack on Linux:

cargo test --locked --features runtime-checks --test integration test_data_structure_patterns::trie

Read trie storage, updates, and costs for the implementation and its limits. Compare the balanced search trees when ordering alone, rather than shared-prefix retrieval, is the main requirement.