Skip to main content

am_wordlist/
lib.rs

1#![no_std]
2#![forbid(unsafe_code)]
3//! A fast, embedded word list you can index, with zero runtime init and zero
4//! allocation.
5//!
6//! The whole list is baked into the binary at compile time, with each word's
7//! start offset computed ahead of time in `build.rs`, so indexed lookup is a
8//! plain slice. The list is sorted and duplicate-free, so [`position`],
9//! [`contains`] and [`starting_with`] are binary searches over it.
10
11use core::ops::{Bound, RangeBounds};
12
13mod data {
14    // Generated by build.rs
15    include!(concat!(env!("OUT_DIR"), "/worddata.rs"));
16}
17
18/// How many words there are.
19pub const LEN: usize = data::WORD_COUNT;
20
21/// Resolve a word index into the slice of the blob it borrows.
22///
23/// `STARTS` holds one offset per word plus a sentinel, and `build.rs` writes
24/// exactly one separator byte after every word, so a word ends one byte before
25/// the next one starts. Storing starts alone halves the index.
26#[inline]
27fn word(index: usize) -> &'static str {
28    let start = data::STARTS[index] as usize;
29    let end = data::STARTS[index + 1] as usize - 1;
30    &data::BLOB[start..end]
31}
32
33/// Index of the first word in `lo..hi` where `pred` turns false. `pred` must
34/// hold for a (possibly empty) prefix of the range and fail for the rest.
35#[inline]
36fn partition_point(lo: usize, hi: usize, pred: impl Fn(usize) -> bool) -> usize {
37    let (mut lo, mut hi) = (lo, hi);
38    while lo < hi {
39        let mid = lo + (hi - lo) / 2;
40        if pred(mid) {
41            lo = mid + 1;
42        } else {
43            hi = mid;
44        }
45    }
46    lo
47}
48
49#[inline]
50pub fn len() -> usize {
51    LEN
52}
53
54#[inline]
55pub fn is_empty() -> bool {
56    LEN == 0
57}
58
59/// Look up a single word by index. O(1), no allocation. Out of range is `None`.
60#[inline]
61pub fn get(index: usize) -> Option<&'static str> {
62    if index < LEN { Some(word(index)) } else { None }
63}
64
65/// Look up a contiguous range of words as an allocation-free iterator.
66///
67/// Accepts any range (`a..b`, `a..=b`, `a..`, `..b`, `..`). Returns `None` if
68/// the range is out of bounds or its start is past its end — matching [`get`].
69///
70/// ```
71/// let mut it = am_wordlist::get_range(0..3).unwrap();
72/// assert_eq!(it.clone().count(), 3);
73/// assert_eq!(it.next(), am_wordlist::get(0));
74/// assert!(am_wordlist::get_range(0..=am_wordlist::LEN).is_none());
75/// ```
76#[inline]
77pub fn get_range<R: RangeBounds<usize>>(
78    range: R,
79) -> Option<impl Iterator<Item = &'static str> + Clone> {
80    let start = match range.start_bound() {
81        Bound::Included(&n) => n,
82        Bound::Excluded(&n) => n.checked_add(1)?,
83        Bound::Unbounded => 0,
84    };
85    let end = match range.end_bound() {
86        Bound::Included(&n) => n.checked_add(1)?,
87        Bound::Excluded(&n) => n,
88        Bound::Unbounded => LEN,
89    };
90    if start > end || end > LEN {
91        return None;
92    }
93    Some((start..end).map(word as fn(usize) -> &'static str))
94}
95
96/// Iterate over every word in order. O(1) to set up, no allocation.
97#[inline]
98pub fn iter() -> impl Iterator<Item = &'static str> + Clone {
99    (0..LEN).map(word as fn(usize) -> &'static str)
100}
101
102/// Find a word's index. O(log n), no allocation. Not found is `None`.
103///
104/// The embedded list is sorted by byte order and duplicate-free, so this is a
105/// binary search. Matching is exact and case-sensitive; every embedded word is
106/// lowercase ASCII, so anything else is always `None`.
107///
108/// ```
109/// let w = am_wordlist::get(100).unwrap();
110/// assert_eq!(am_wordlist::position(w), Some(100));
111/// assert_eq!(am_wordlist::position("Not A Word"), None);
112/// ```
113#[inline]
114pub fn position(word: &str) -> Option<usize> {
115    let i = partition_point(0, LEN, |i| self::word(i) < word);
116    (i < LEN && self::word(i) == word).then_some(i)
117}
118
119/// Whether the list contains a word. O(log n), no allocation.
120///
121/// ```
122/// assert!(am_wordlist::contains(am_wordlist::get(0).unwrap()));
123/// assert!(!am_wordlist::contains("zzzzzzzz"));
124/// ```
125#[inline]
126pub fn contains(word: &str) -> bool {
127    position(word).is_some()
128}
129
130/// Iterate over every word starting with `prefix`, in order. O(log n) to set
131/// up, no allocation.
132///
133/// An empty prefix yields the whole list; a prefix no word starts with yields
134/// nothing.
135///
136/// ```
137/// let mut it = am_wordlist::starting_with("aba");
138/// assert!(it.all(|w| w.starts_with("aba")));
139/// assert_eq!(am_wordlist::starting_with("zzzzzzzz").count(), 0);
140/// ```
141#[inline]
142pub fn starting_with(prefix: &str) -> impl Iterator<Item = &'static str> + Clone {
143    // Words sharing a prefix are contiguous in a sorted list: skip everything
144    // ordered before the prefix, then take while the prefix still matches.
145    let start = partition_point(0, LEN, |i| word(i) < prefix);
146    let end = partition_point(start, LEN, |i| word(i).starts_with(prefix));
147    (start..end).map(word as fn(usize) -> &'static str)
148}
149
150#[cfg(test)]
151mod tests {
152
153    /// Pins the byte-level shape of every word. An off-by-one in the span
154    /// index would leak a separator byte into a word, or truncate one.
155    #[test]
156    fn every_word_is_clean_lowercase_ascii() {
157        for (i, w) in super::iter().enumerate() {
158            assert!(!w.is_empty(), "empty word at {i}");
159            assert!(
160                w.bytes().all(|b| b.is_ascii_lowercase()),
161                "word {i} is not pure lowercase ascii: {w:?}"
162            );
163        }
164    }
165
166    #[test]
167    fn position_round_trips_with_get() {
168        // Sample across the list rather than walking all of it.
169        for i in (0..super::len()).step_by(97) {
170            let w = super::get(i).unwrap();
171            assert_eq!(super::position(w), Some(i), "round trip failed for {w:?}");
172        }
173    }
174
175    #[test]
176    fn contains_agrees_with_linear_scan() {
177        for probe in ["a", "zebra", "apple", "cackle", "abandon"] {
178            let expected = super::iter().any(|w| w == probe);
179            assert_eq!(
180                super::contains(probe),
181                expected,
182                "disagreement on {probe:?}"
183            );
184        }
185    }
186
187    #[test]
188    fn contains_rejects_non_words() {
189        // Empty, uppercase and punctuated inputs can never be in the list.
190        for probe in ["", "Apple", "not-a-word", "zzzzzzzz", "apple pie"] {
191            assert!(!super::contains(probe), "should not contain {probe:?}");
192            assert_eq!(super::position(probe), None);
193        }
194    }
195
196    #[test]
197    fn starting_with_matches_linear_filter() {
198        for prefix in ["ab", "zy", "q", "cackl"] {
199            let expected: usize = super::iter().filter(|w| w.starts_with(prefix)).count();
200            let got = super::starting_with(prefix).count();
201            assert_eq!(got, expected, "wrong count for prefix {prefix:?}");
202            assert!(super::starting_with(prefix).all(|w| w.starts_with(prefix)));
203        }
204    }
205
206    #[test]
207    fn starting_with_edge_cases() {
208        // Empty prefix matches everything; an impossible prefix matches nothing.
209        assert_eq!(super::starting_with("").count(), super::len());
210        assert_eq!(super::starting_with("zzzzzzzz").count(), 0);
211        // A prefix that is itself a word includes that word.
212        let w = super::get(0).unwrap();
213        assert!(super::starting_with(w).any(|x| x == w));
214    }
215
216    #[test]
217    fn sorted_and_unique() {
218        let mut prev: Option<&str> = None;
219        for (i, w) in super::iter().enumerate() {
220            if let Some(p) = prev {
221                assert!(p < w, "not sorted/unique at {i}: {p:?} then {w:?}");
222            }
223            prev = Some(w);
224        }
225    }
226    #[test]
227    fn non_empty() {
228        assert!(super::len() > 0);
229        assert_eq!(super::len(), super::LEN);
230        assert!(!super::is_empty());
231    }
232
233    #[test]
234    fn bounds() {
235        assert!(super::get(0).is_some());
236        assert!(super::get(super::len() - 1).is_some());
237        assert!(super::get(super::len()).is_none());
238        assert!(super::get(usize::MAX).is_none());
239    }
240
241    #[test]
242    fn iter_matches_get() {
243        assert_eq!(super::iter().count(), super::len());
244        for (i, w) in super::iter().enumerate() {
245            assert_eq!(super::get(i), Some(w));
246        }
247    }
248
249    #[test]
250    fn get_range_matches_get() {
251        let mut range = super::get_range(2..5).unwrap();
252        assert_eq!(range.clone().count(), 3);
253        assert_eq!(range.next(), super::get(2));
254        assert_eq!(range.next(), super::get(3));
255        assert_eq!(range.next(), super::get(4));
256        assert_eq!(range.next(), None);
257    }
258
259    #[test]
260    fn get_range_bounds_variants() {
261        let full = super::len();
262        assert_eq!(super::get_range(..).unwrap().count(), full);
263        assert_eq!(super::get_range(..3).unwrap().count(), 3);
264        assert_eq!(super::get_range(0..=2).unwrap().count(), 3);
265        assert_eq!(super::get_range(full - 1..).unwrap().count(), 1);
266        // Empty ranges are valid and yield nothing.
267        assert_eq!(super::get_range(2..2).unwrap().count(), 0);
268    }
269
270    #[test]
271    fn get_range_out_of_bounds() {
272        let full = super::len();
273        assert!(super::get_range(0..=full).is_none());
274        assert!(super::get_range(full + 1..full + 2).is_none());
275        // start past end is rejected, not clamped.
276        let (a, b) = (5usize, 2usize);
277        assert!(super::get_range(a..b).is_none());
278        assert!(super::get_range(..=usize::MAX).is_none());
279    }
280}