Something went wrong. Try again.
GET /xrpc/tech.waow.typeahead.searchActors typeahead.waow.tech
Something went wrong. Try again.
Zig
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858//! Prefix key derivation. Given a normalized handle and display name,//! emit the lookup keys that map an actor into the prefix index.//!//! Four namespaces://! `h:<prefix>` — every prefix of the normalized handle, length 1..PREFIX_MAX//! `n:<prefix>` — every prefix of every display-name token, length 1..PREFIX_MAX//! `e:<handle>` — the exact normalized handle (one key per actor)//! `d:<prefix>` — every prefix of every dot-boundary suffix of the handle,//! so `foo.germ.network` is findable by `germ.network`,//! `germ`, `network` (atproto handles are domain-structured;//! `h:` only matches start-anchored, never mid-handle).//!//! Builder calls `deriveAll` for each actor and emits (key, did, score)//! tuples. Serving calls `queryKeys` on the user's normalized query.//! The two paths must agree on what a "key" looks like for any input —//! both go through this file. See normalize.zig for upstream constraints.
const std = @import("std");const Allocator = std.mem.Allocator;const normalize = @import("normalize.zig");
/// Maximum prefix length emitted by the builder. Caps the long tail of/// 13+-char prefixes that almost nobody types. Bumping this multiplies/// index size linearly with handle/token length.pub const PREFIX_MAX: usize = 16;
/// Cap on the number of display-name tokens we index per actor. Defense/// against pathological display names (someone setting it to a 200-word/// essay would otherwise emit thousands of keys for one actor).pub const MAX_DISPLAY_TOKENS: usize = 8;
/// Single key namespace tag. Encoded as a 2-byte ASCII prefix in the/// stored key (`h:`, `n:`, `e:`) for human-readable debugging and a/// trivial `WHERE key IN (...)` lookup that covers all three.pub const Namespace = enum(u8) { handle_prefix = 'h', display_token = 'n', exact_handle = 'e', domain_suffix = 'd',};
/// Render a namespace + text into a freshly-allocated key string/// "<ns>:<text>". Caller owns the result (arena-typical).pub fn formatKey(arena: Allocator, ns: Namespace, text: []const u8) ![]const u8 { return std.fmt.allocPrint(arena, "{c}:{s}", .{ @backingInt(ns), text });}
/// Derive every `h:` prefix key for a normalized handle. Returns a slice/// of allocated keys; lengths from 1 up to min(len, PREFIX_MAX).pub fn handlePrefixKeys(arena: Allocator, normalized_handle: []const u8) ![][]const u8 { const max = @min(normalized_handle.len, PREFIX_MAX); if (max == 0) return &.{};
var keys = try arena.alloc([]const u8, max); var i: usize = 0; while (i < max) : (i += 1) { keys[i] = try formatKey(arena, .handle_prefix, normalized_handle[0 .. i + 1]); } return keys;}
/// Tokens from a normalized display name. Splits on the single ASCII/// space character `' '` (normalize collapses all separators to one space)./// Empty strings between leading/trailing separators have already been/// stripped by normalize, so consecutive spaces don't happen.////// Returns up to MAX_DISPLAY_TOKENS slices into the input (NOT copies)./// Caller must hold the input alive while using the result.pub fn displayTokens(arena: Allocator, normalized_display: []const u8) ![][]const u8 { if (normalized_display.len == 0) return &.{};
var tokens: std.ArrayListUnmanaged([]const u8) = .empty; var it = std.mem.splitScalar(u8, normalized_display, ' '); while (it.next()) |tok| { if (tok.len == 0) continue; try tokens.append(arena, tok); if (tokens.items.len >= MAX_DISPLAY_TOKENS) break; } return tokens.toOwnedSlice(arena);}
/// Max codepoints bigrammed from a single CJK run (defense against a/// pathological all-CJK display name). Phase 0 avg is ~4 codepoints.pub const CJK_RUN_MAX: usize = 24;
/// CJK codepoints we index: Han, Hiragana (katakana is folded to Hiragana/// upstream in normalize.zig), and half-width katakana. Must agree with the/// set normalize.zig preserves — anything preserved-and-non-ASCII is CJK.fn isCjkCodepoint(cp: u21) bool { return (cp >= 0x3040 and cp <= 0x30FF) // hiragana + (folded-away) katakana + ー or (cp >= 0x3400 and cp <= 0x4DBF) // CJK Ext A or (cp >= 0x4E00 and cp <= 0x9FFF) // CJK Unified Ideographs or (cp >= 0xF900 and cp <= 0xFAFF) // CJK Compatibility Ideographs or (cp >= 0xFF66 and cp <= 0xFF9D); // half-width katakana}
/// Emit `n:` keys for one contiguous CJK run (codepoint-safe — all slices/// land on UTF-8 boundaries). Adjacent-codepoint BIGRAMS (`n:日本`, `n:本太`)/// approximate word boundaries for a script with no spaces; the query side/// intersects them (the existing multi-token `n:` AND). Plus the LEADING/// UNIGRAM (`n:日`) so a 1-char in-progress query matches./// for_query=false (builder): bigrams + leading unigram./// for_query=true (query): bigrams; or the single unigram when the run/// is one codepoint (no every-char unigram).fn appendCjkKeys( arena: Allocator, keys: *std.ArrayListUnmanaged([]const u8), run: []const u8, for_query: bool,) !void { // Byte offsets of each codepoint boundary, capped at CJK_RUN_MAX cps. var bound: [CJK_RUN_MAX + 1]usize = undefined; var n: usize = 0; bound[0] = 0; const view = std.unicode.Utf8View.init(run) catch return; var it = view.iterator(); while (it.nextCodepointSlice()) |cps| { if (n >= CJK_RUN_MAX) break; bound[n + 1] = bound[n] + cps.len; n += 1; } if (n == 0) return; if (n == 1) { try keys.append(arena, try formatKey(arena, .display_token, run[0..bound[1]])); return; } var i: usize = 0; while (i + 1 < n) : (i += 1) { try keys.append(arena, try formatKey(arena, .display_token, run[bound[i]..bound[i + 2]])); } if (!for_query) { try keys.append(arena, try formatKey(arena, .display_token, run[0..bound[1]])); // leading unigram }}
/// Emit `n:` keys for one Latin (ASCII, post-normalize) run./// for_query=false (builder): every prefix, length 1..PREFIX_MAX./// for_query=true (query): the full run as a single key.fn appendLatinKeys( arena: Allocator, keys: *std.ArrayListUnmanaged([]const u8), run: []const u8, for_query: bool,) !void { if (run.len == 0) return; if (for_query) { try keys.append(arena, try formatKey(arena, .display_token, prefixCut(run))); return; } const max = @min(run.len, PREFIX_MAX); // Latin run is ASCII → byte == codepoint var i: usize = 0; while (i < max) : (i += 1) { try keys.append(arena, try formatKey(arena, .display_token, run[0 .. i + 1])); }}
/// The shared, script-aware `n:`-key tokenizer. Segments one whitespace-token/// into contiguous Latin vs CJK runs (codepoint-safe) and emits keys per run./// BOTH the builder (`displayPrefixKeys`, for_query=false) and the serving/// path (`queryKeys`, for_query=true) go through here — one code path, so the/// index and the query can never disagree on what a CJK key looks like.fn emitTokenKeys( arena: Allocator, keys: *std.ArrayListUnmanaged([]const u8), token: []const u8, for_query: bool,) !void { const view = std.unicode.Utf8View.init(token) catch { try appendLatinKeys(arena, keys, token, for_query); // invalid utf8: treat as ascii return; }; var it = view.iterator(); var run_start: usize = 0; var pos: usize = 0; var cur_cjk: ?bool = null; while (it.nextCodepointSlice()) |cps| { const cp = std.unicode.utf8Decode(cps) catch { pos += cps.len; continue; }; const this_cjk = isCjkCodepoint(cp); if (cur_cjk) |ck| { if (ck != this_cjk) { try emitRun(arena, keys, token[run_start..pos], ck, for_query); run_start = pos; } } cur_cjk = this_cjk; pos += cps.len; } if (cur_cjk) |ck| try emitRun(arena, keys, token[run_start..pos], ck, for_query);}
fn emitRun( arena: Allocator, keys: *std.ArrayListUnmanaged([]const u8), run: []const u8, is_cjk: bool, for_query: bool,) !void { if (is_cjk) try appendCjkKeys(arena, keys, run, for_query) else try appendLatinKeys(arena, keys, run, for_query);}
/// Derive every `n:` key for a normalized display name. Latin runs emit/// prefixes; CJK runs emit bigrams + a leading unigram (see emitTokenKeys)./// Duplicate keys across tokens are NOT deduplicated here — the builder's/// group-by pass naturally dedupes.pub fn displayPrefixKeys(arena: Allocator, normalized_display: []const u8) ![][]const u8 { const tokens = try displayTokens(arena, normalized_display); if (tokens.len == 0) return &.{};
var keys: std.ArrayListUnmanaged([]const u8) = .empty; for (tokens) |tok| try emitTokenKeys(arena, &keys, tok, false); return keys.toOwnedSlice(arena);}
/// Derive the single `e:` exact-handle key. Returns null if the handle/// is empty (don't emit empty-string keys — they collide trivially).pub fn exactHandleKey(arena: Allocator, normalized_handle: []const u8) !?[]const u8 { if (normalized_handle.len == 0) return null; return try formatKey(arena, .exact_handle, normalized_handle);}
/// Derive every `d:` key: prefixes of each dot-boundary suffix of the handle./// For `foo.germ.network` the suffixes are `germ.network` and `network` (the/// full handle is excluded — `h:` already covers start-anchored matches), and/// each emits prefixes up to PREFIX_MAX. Lets a domain search like/// `germ.network` (or just `germ`/`network`) surface every account under it.pub fn domainSuffixKeys(arena: Allocator, normalized_handle: []const u8) ![][]const u8 { var keys: std.ArrayListUnmanaged([]const u8) = .empty; var i: usize = 0; while (i < normalized_handle.len) : (i += 1) { if (normalized_handle[i] != '.') continue; const suffix = normalized_handle[i + 1 ..]; const max = @min(suffix.len, PREFIX_MAX); var j: usize = 0; while (j < max) : (j += 1) { try keys.append(arena, try formatKey(arena, .domain_suffix, suffix[0 .. j + 1])); } } return keys.toOwnedSlice(arena);}
/// Derive every key for an actor (h: prefixes, n: token prefixes, e: exact)./// Called per-actor by the builder. Order doesn't matter — the builder/// groups by key later. Output may contain DUPLICATES (e.g. display name/// "fig fig" produces two `n:fig` keys). Builders dedupe via GROUP BY at/// sort time, so duplicates are correct for that path.////// IMPORTANT: callers MUST pass values already normalized through the/// right entry point — `normalize.handle()` for the handle, and/// `normalize.display()` for the display name. The split exists so the/// underscore policy and other handle-specific rules are applied/// upstream of prefix derivation. Mixing the two normalize fns leaks/// invalid characters into `h:`/`e:` keys.pub fn deriveAll( arena: Allocator, normalized_handle: []const u8, normalized_display: []const u8,) ![][]const u8 { var all: std.ArrayListUnmanaged([]const u8) = .empty;
if (try exactHandleKey(arena, normalized_handle)) |k| { try all.append(arena, k); } for (try handlePrefixKeys(arena, normalized_handle)) |k| { try all.append(arena, k); } for (try displayPrefixKeys(arena, normalized_display)) |k| { try all.append(arena, k); } for (try domainSuffixKeys(arena, normalized_handle)) |k| { try all.append(arena, k); }
return all.toOwnedSlice(arena);}
/// Same as `deriveAll` but returns a deduplicated, lexicographically/// sorted slice. Use this from the OVERLAY UPDATER, where emitting/// duplicate prefix_overlay rows would be wasted work AND would break/// diff-against-old-prefixes set arithmetic (`added = new - old`).////// The dedupe step uses a StringHashMap keyed by the full namespaced/// key text. Cost is O(N) on the emission count, which is bounded by/// PREFIX_MAX * (1 + MAX_DISPLAY_TOKENS) per actor — well under 200/// entries even in the worst case.pub fn deriveAllUnique( arena: Allocator, normalized_handle: []const u8, normalized_display: []const u8,) ![][]const u8 { const all = try deriveAll(arena, normalized_handle, normalized_display);
var seen: std.StringHashMap(void) = .init(arena); try seen.ensureTotalCapacity(@intCast(all.len)); for (all) |k| _ = try seen.getOrPut(k);
var unique = try arena.alloc([]const u8, seen.count()); var i: usize = 0; var it = seen.keyIterator(); while (it.next()) |k| : (i += 1) unique[i] = k.*;
std.mem.sort([]const u8, unique, {}, lexLessThan); return unique;}
fn lexLessThan(_: void, a: []const u8, b: []const u8) bool { return std.mem.order(u8, a, b) == .lt;}
/// Build the set of lookup keys for an incoming search query. Single/// query produces ≤ MAX_DISPLAY_TOKENS+2 keys (handle prefix + exact +/// up to MAX_DISPLAY_TOKENS display-token prefixes).////// Strategy for a query like "fig aka":/// - h:fig%20aka (handle prefix with the literal normalized query)/// - e:fig%20aka (exact handle match)/// - n:fig, n:aka (token-prefix keys, one per query token)////// Note: `h:` here uses the FULL query string including internal spaces./// That intentionally won't match any handle (handles don't have spaces),/// but matters for compositional clarity — the serving layer can choose/// to skip h:/e: keys when the query has whitespace.pub fn queryKeys(arena: Allocator, normalized_query: []const u8) ![][]const u8 { if (normalized_query.len == 0) return &.{};
var keys: std.ArrayListUnmanaged([]const u8) = .empty;
// Single-token queries: h: and e: are real lookups. Multi-token: // they typically miss but we emit them anyway for compositional // simplicity — empty lookups cost ~nothing. // // The builder never emits a prefix key longer than PREFIX_MAX, so the // h:/d: lookups use the query's PREFIX_MAX-cut; `e:` stays whole. A query // longer than the cut needs `matchesFullQuery` on the hydrated rows. const has_space = std.mem.indexOfScalar(u8, normalized_query, ' ') != null; if (!has_space) { const cut = prefixCut(normalized_query); try keys.append(arena, try formatKey(arena, .handle_prefix, cut)); try keys.append(arena, try formatKey(arena, .exact_handle, normalized_query)); // domain-suffix lookup: matches accounts under a domain the query names // (e.g. `germ.network` → `*.germ.network`, or `germ` → that label). try keys.append(arena, try formatKey(arena, .domain_suffix, cut)); }
// CJK-aware: a CJK query token yields its bigram set (intersected by the // serving layer); a Latin token yields its single full-run key. Same // tokenizer the builder uses, so index + query agree. const tokens = try displayTokens(arena, normalized_query); for (tokens) |tok| try emitTokenKeys(arena, &keys, tok, true);
return keys.toOwnedSlice(arena);}
/// The longest prefix of `text` that the builder could have emitted as a key:/// at most PREFIX_MAX bytes, never split inside a UTF-8 sequence.pub fn prefixCut(text: []const u8) []const u8 { if (text.len <= PREFIX_MAX) return text; var end: usize = PREFIX_MAX; while (end > 0 and (text[end] & 0xC0) == 0x80) end -= 1; return text[0..end];}
/// True when some lookup key for this query was cut to PREFIX_MAX, so the/// candidates a key returns are a superset of the real matches.////// Only ASCII runs count: handles are ASCII, so a cut `h:`/`d:` key with/// non-Latin bytes could never have matched, and CJK `n:` keys are bigrams/// with no length cap.pub fn queryExceedsPrefixMax(normalized_query: []const u8) bool { var it = std.mem.splitScalar(u8, normalized_query, ' '); while (it.next()) |tok| { if (longestLatinRun(tok) > PREFIX_MAX) return true; } return false;}
fn longestLatinRun(token: []const u8) usize { var best: usize = 0; var cur: usize = 0; for (token) |b| { if (b < 0x80) { cur += 1; if (cur > best) best = cur; } else cur = 0; } return best;}
/// The serving-side complement of the PREFIX_MAX cut. Decides whether an/// actor (already normalized with `normalize.handle` / `normalize.display`)/// matches the whole query under the same rules the keys encode:/// single token → h: (handle starts with it), e: (equal), d: (a dot-boundary/// suffix starts with it), or n: (a display run starts with it)/// multi token → every token must start some display run (intersect_all)/// Only tokens that were actually cut are checked; the rest already matched/// exactly via their keys.pub fn matchesFullQuery(normalized_query: []const u8, normalized_handle: []const u8, normalized_display: []const u8) bool { const has_space = std.mem.indexOfScalar(u8, normalized_query, ' ') != null; if (!has_space) { if (std.mem.startsWith(u8, normalized_handle, normalized_query)) return true; if (startsDotSuffix(normalized_handle, normalized_query)) return true; return tokenMatchesDisplay(normalized_query, normalized_display); } var it = std.mem.splitScalar(u8, normalized_query, ' '); while (it.next()) |tok| { if (tok.len == 0) continue; if (longestLatinRun(tok) <= PREFIX_MAX) continue; if (!tokenMatchesDisplay(tok, normalized_display)) return false; } return true;}
fn startsDotSuffix(handle: []const u8, needle: []const u8) bool { var i: usize = 0; while (i < handle.len) : (i += 1) { if (handle[i] != '.') continue; if (std.mem.startsWith(u8, handle[i + 1 ..], needle)) return true; } return false;}
/// Every Latin run of `token` longer than PREFIX_MAX must begin some Latin/// run of the display name. Runs shorter than that matched their key whole.fn tokenMatchesDisplay(token: []const u8, display: []const u8) bool { var start: usize = 0; var i: usize = 0; while (i <= token.len) : (i += 1) { const boundary = i == token.len or token[i] >= 0x80; if (!boundary) continue; const run = token[start..i]; if (run.len > PREFIX_MAX and !runStartsDisplayRun(run, display)) return false; start = i + 1; } return true;}
fn runStartsDisplayRun(run: []const u8, display: []const u8) bool { var pos: usize = 0; while (std.mem.indexOfPos(u8, display, pos, run)) |at| : (pos = at + 1) { if (at == 0 or display[at - 1] == ' ' or display[at - 1] >= 0x80) return true; } return false;}
// ─── tests ───────────────────────────────────────────────────────────────
const testing = std.testing;
test "formatKey shape" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); try testing.expectEqualStrings("h:nate", try formatKey(arena.allocator(), .handle_prefix, "nate")); try testing.expectEqualStrings("n:fig", try formatKey(arena.allocator(), .display_token, "fig")); try testing.expectEqualStrings("e:nate.fm", try formatKey(arena.allocator(), .exact_handle, "nate.fm"));}
test "handlePrefixKeys generates every prefix" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try handlePrefixKeys(arena.allocator(), "nate"); try testing.expectEqual(@as(usize, 4), keys.len); try testing.expectEqualStrings("h:n", keys[0]); try testing.expectEqualStrings("h:na", keys[1]); try testing.expectEqualStrings("h:nat", keys[2]); try testing.expectEqualStrings("h:nate", keys[3]);}
test "handlePrefixKeys respects PREFIX_MAX" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); var long_handle: [40]u8 = undefined; @memset(&long_handle, 'a'); const keys = try handlePrefixKeys(arena.allocator(), &long_handle); try testing.expectEqual(PREFIX_MAX, keys.len); try testing.expectEqual(@as(usize, 2 + PREFIX_MAX), keys[PREFIX_MAX - 1].len); // "h:" + PREFIX_MAX chars}
test "handlePrefixKeys on empty handle returns empty" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try handlePrefixKeys(arena.allocator(), ""); try testing.expectEqual(@as(usize, 0), keys.len);}
test "displayTokens splits on single space" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const tokens = try displayTokens(arena.allocator(), "fig aka phil"); try testing.expectEqual(@as(usize, 3), tokens.len); try testing.expectEqualStrings("fig", tokens[0]); try testing.expectEqualStrings("aka", tokens[1]); try testing.expectEqualStrings("phil", tokens[2]);}
test "displayTokens caps at MAX_DISPLAY_TOKENS" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const tokens = try displayTokens(arena.allocator(), "a b c d e f g h i j k l"); try testing.expectEqual(MAX_DISPLAY_TOKENS, tokens.len); try testing.expectEqualStrings("a", tokens[0]); try testing.expectEqualStrings("h", tokens[MAX_DISPLAY_TOKENS - 1]);}
test "displayPrefixKeys covers every token's prefixes" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try displayPrefixKeys(arena.allocator(), "fig aka"); // "fig" → 3, "aka" → 3 try testing.expectEqual(@as(usize, 6), keys.len); try testing.expectEqualStrings("n:f", keys[0]); try testing.expectEqualStrings("n:fi", keys[1]); try testing.expectEqualStrings("n:fig", keys[2]); try testing.expectEqualStrings("n:a", keys[3]); try testing.expectEqualStrings("n:ak", keys[4]); try testing.expectEqualStrings("n:aka", keys[5]);}
test "deriveAll combines h/n/e for a typical actor" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAll(arena.allocator(), "nate", "Nate Smith"); // After normalize: handle="nate", display="nate smith" // But this fn assumes inputs ARE normalized — the builder calls // normalize first. For this test, we give normalized values directly. const keys2 = try deriveAll(arena.allocator(), "nate", "nate smith"); try testing.expectEqual(@as(usize, 1 + 4 + 4 + 5), keys2.len); // e:nate + 4 h: + 4 n:nate-prefixes + 5 n:smith-prefixes _ = keys;
// Spot check var found_exact = false; var found_h_nate = false; var found_n_smith = false; for (keys2) |k| { if (std.mem.eql(u8, k, "e:nate")) found_exact = true; if (std.mem.eql(u8, k, "h:nate")) found_h_nate = true; if (std.mem.eql(u8, k, "n:smith")) found_n_smith = true; } try testing.expect(found_exact); try testing.expect(found_h_nate); try testing.expect(found_n_smith);}
test "deriveAll handles empty display name" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAll(arena.allocator(), "nate", ""); // 1 exact + 4 handle prefixes; no display tokens. try testing.expectEqual(@as(usize, 5), keys.len);}
test "deriveAll handles empty handle" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAll(arena.allocator(), "", "John Doe"); // No e:, no h:; display tokens only ("john"=4, "doe"=3) // But wait — "John Doe" isn't normalized; we'd need lowercase. // Caller is responsible for normalizing before calling deriveAll. // Treating literal as normalized for this test: _ = keys; const keys2 = try deriveAll(arena.allocator(), "", "john doe"); try testing.expectEqual(@as(usize, 4 + 3), keys2.len);}
test "queryKeys: single token" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try queryKeys(arena.allocator(), "nate"); try testing.expectEqual(@as(usize, 4), keys.len); // h:, e:, d:, n: try testing.expectEqualStrings("h:nate", keys[0]); try testing.expectEqualStrings("e:nate", keys[1]); try testing.expectEqualStrings("d:nate", keys[2]); try testing.expectEqualStrings("n:nate", keys[3]);}
test "domainSuffixKeys: prefixes of each dot-boundary suffix" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try domainSuffixKeys(arena.allocator(), "foo.germ.network"); // suffixes: "germ.network" (12 prefixes) + "network" (7 prefixes) = 19 try testing.expectEqual(@as(usize, 19), keys.len); var has_germ = false; var has_germ_network = false; var has_network = false; var has_full = false; for (keys) |k| { if (std.mem.eql(u8, k, "d:germ")) has_germ = true; if (std.mem.eql(u8, k, "d:germ.network")) has_germ_network = true; if (std.mem.eql(u8, k, "d:network")) has_network = true; if (std.mem.eql(u8, k, "d:foo.germ.network")) has_full = true; } try testing.expect(has_germ); // searchable by domain label prefix try testing.expect(has_germ_network); // searchable by full domain suffix try testing.expect(has_network); // searchable by TLD-ish label try testing.expect(!has_full); // full handle excluded (h:/e: cover it)}
test "domainSuffixKeys: no dots → no keys" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try domainSuffixKeys(arena.allocator(), "nodots"); try testing.expectEqual(@as(usize, 0), keys.len);}
test "deriveAll for a domain handle is findable by its domain suffix" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAll(arena.allocator(), "foo.germ.network", ""); var has_d_germ_network = false; for (keys) |k| if (std.mem.eql(u8, k, "d:germ.network")) { has_d_germ_network = true; }; try testing.expect(has_d_germ_network);}
test "queryKeys: multi-token query skips h:/e: (would never match)" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try queryKeys(arena.allocator(), "fig aka"); // Only n: keys for each token, no h:/e: since query has whitespace. try testing.expectEqual(@as(usize, 2), keys.len); try testing.expectEqualStrings("n:fig", keys[0]); try testing.expectEqualStrings("n:aka", keys[1]);}
test "queryKeys: empty query returns empty" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try queryKeys(arena.allocator(), ""); try testing.expectEqual(@as(usize, 0), keys.len);}
test "deriveAll output is sane for unicode-normalized input" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit();
// simulate the indexer flow: caller normalizes via the per-field // entry point, then derives. const handle = try normalize.handle(arena.allocator(), "Éric.fm"); const display = try normalize.display(arena.allocator(), "Éric Müller");
try testing.expectEqualStrings("eric.fm", handle); try testing.expectEqualStrings("eric muller", display);
const keys = try deriveAll(arena.allocator(), handle, display);
var has_h_eric = false; var has_n_muller = false; for (keys) |k| { if (std.mem.eql(u8, k, "h:eric")) has_h_eric = true; if (std.mem.eql(u8, k, "n:muller")) has_n_muller = true; } try testing.expect(has_h_eric); try testing.expect(has_n_muller);}
test "deriveAll on display 'fig fig' emits duplicate n:fig keys (by design)" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAll(arena.allocator(), "", "fig fig"); // "fig" tokenized twice → 3 prefixes × 2 = 6 n: keys try testing.expectEqual(@as(usize, 6), keys.len);
var n_fig_count: usize = 0; for (keys) |k| if (std.mem.eql(u8, k, "n:fig")) { n_fig_count += 1; }; try testing.expectEqual(@as(usize, 2), n_fig_count);}
test "deriveAllUnique returns sorted deduped slice" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try deriveAllUnique(arena.allocator(), "alice", "alice the great"); // duplicates (e.g. n:a appears from "alice", "the", and any other a-word) collapse.
// Verify no duplicates for (keys, 0..) |k, i| { for (keys[i + 1 ..]) |other| { try testing.expect(!std.mem.eql(u8, k, other)); } }
// Verify sorted var prev: []const u8 = ""; for (keys) |k| { try testing.expect(std.mem.order(u8, prev, k) == .lt); prev = k; }
// Sanity: expected keys are present var has_e_alice = false; var has_h_a = false; var has_n_great = false; for (keys) |k| { if (std.mem.eql(u8, k, "e:alice")) has_e_alice = true; if (std.mem.eql(u8, k, "h:a")) has_h_a = true; if (std.mem.eql(u8, k, "n:great")) has_n_great = true; } try testing.expect(has_e_alice); try testing.expect(has_h_a); try testing.expect(has_n_great);}
test "deriveAllUnique enables clean set-diff for overlay rename" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit();
// Actor renamed from "alice.fm" → "bob.fm". Overlay needs to suppress // every "h:alic*" / "e:alice.fm" key the actor used to occupy. const old_keys = try deriveAllUnique(arena.allocator(), "alice.fm", ""); const new_keys = try deriveAllUnique(arena.allocator(), "bob.fm", "");
// Build "removed" = old - new via simple intersection scan (both sorted). var removed: std.ArrayListUnmanaged([]const u8) = .empty; var oi: usize = 0; var ni: usize = 0; while (oi < old_keys.len) { if (ni == new_keys.len) { try removed.append(arena.allocator(), old_keys[oi]); oi += 1; continue; } const cmp = std.mem.order(u8, old_keys[oi], new_keys[ni]); switch (cmp) { .lt => { try removed.append(arena.allocator(), old_keys[oi]); oi += 1; }, .eq => { oi += 1; ni += 1; }, .gt => ni += 1, } }
// Removed should include all h:alic* prefixes and e:alice.fm. var has_h_alice = false; var has_e_alicefm = false; for (removed.items) |k| { if (std.mem.eql(u8, k, "h:alice")) has_h_alice = true; if (std.mem.eql(u8, k, "e:alice.fm")) has_e_alicefm = true; } try testing.expect(has_h_alice); try testing.expect(has_e_alicefm);}
// ─── v2: CJK / Japanese ────────────────────────────────────────────────────
fn keySet(arena: Allocator, keys: [][]const u8) !std.StringHashMap(void) { var s = std.StringHashMap(void).init(arena); for (keys) |k| try s.put(k, {}); return s;}
test "v2: displayPrefixKeys bigrams a CJK run + leading unigram" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try displayPrefixKeys(arena.allocator(), "日本太郎"); // bigrams 日本, 本太, 太郎 + leading unigram 日 → 4 keys try testing.expectEqual(@as(usize, 4), keys.len); var s = try keySet(arena.allocator(), keys); try testing.expect(s.contains("n:日本")); try testing.expect(s.contains("n:本太")); try testing.expect(s.contains("n:太郎")); try testing.expect(s.contains("n:日"));}
test "v2: queryKeys bigrams a CJK query" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); var s = try keySet(arena.allocator(), try queryKeys(arena.allocator(), "佐藤太郎")); try testing.expect(s.contains("n:佐藤")); try testing.expect(s.contains("n:藤太")); try testing.expect(s.contains("n:太郎"));}
test "v2: single CJK char query → leading unigram only" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); var s = try keySet(arena.allocator(), try queryKeys(arena.allocator(), "日")); try testing.expect(s.contains("n:日"));}
test "v2: mixed latin+cjk token segments into runs" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); var s = try keySet(arena.allocator(), try displayPrefixKeys(arena.allocator(), "tokyo東京")); try testing.expect(s.contains("n:t")); // latin prefix try testing.expect(s.contains("n:tokyo")); // latin full try testing.expect(s.contains("n:東京")); // cjk bigram try testing.expect(s.contains("n:東")); // cjk leading unigram}
test "v2: query bigrams are a subset of indexed keys (builder/query agree)" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); var idx = try keySet(arena.allocator(), try displayPrefixKeys(arena.allocator(), "佐藤太郎")); // a partial query "佐藤太" must produce only n: keys present in the index const q = try queryKeys(arena.allocator(), "佐藤太"); for (q) |k| { if (std.mem.startsWith(u8, k, "n:")) try testing.expect(idx.contains(k)); }}
test "queryKeys: keys longer than PREFIX_MAX are cut; e: stays whole" { var arena = std.heap.ArenaAllocator.init(testing.allocator); defer arena.deinit(); const keys = try queryKeys(arena.allocator(), "hq.definitelyarealcompany"); try testing.expectEqual(@as(usize, 4), keys.len); try testing.expectEqualStrings("h:hq.definitelyare", keys[0]); try testing.expectEqualStrings("e:hq.definitelyarealcompany", keys[1]); try testing.expectEqualStrings("d:hq.definitelyare", keys[2]); try testing.expectEqualStrings("n:hq.definitelyare", keys[3]); // the cut keys are exactly what the builder emits for a matching actor const emitted = try deriveAllUnique(arena.allocator(), "alice.hq.definitelyarealcompany.com", "hq.definitelyarealcompany"); var seen_h = false; var seen_d = false; var seen_n = false; for (emitted) |k| { if (std.mem.eql(u8, k, "h:alice.hq.definit")) seen_h = true; if (std.mem.eql(u8, k, keys[2])) seen_d = true; if (std.mem.eql(u8, k, keys[3])) seen_n = true; } try testing.expect(seen_h and seen_d and seen_n);}
test "prefixCut never splits a UTF-8 sequence" { try testing.expectEqualStrings("abc", prefixCut("abc")); try testing.expectEqual(@as(usize, PREFIX_MAX), prefixCut("abcdefghijklmnopqrstuvwxyz").len); const cut = prefixCut("abcdefghijklmno日本語"); try testing.expectEqualStrings("abcdefghijklmno", cut);}
test "queryExceedsPrefixMax" { try testing.expect(!queryExceedsPrefixMax("")); try testing.expect(!queryExceedsPrefixMax("abcdefghijklmnop")); try testing.expect(queryExceedsPrefixMax("abcdefghijklmnopq")); try testing.expect(!queryExceedsPrefixMax("nate nowack")); try testing.expect(queryExceedsPrefixMax("nate definitelyarealcompany")); try testing.expect(!queryExceedsPrefixMax("日本語日本語日本語日本語日本語日本語"));}
test "matchesFullQuery: handle prefix, exact, dot suffix, display run" { const q = "hq.definitelyarealcomp"; try testing.expect(matchesFullQuery(q, "alice.hq.definitelyarealcompany.com", "")); try testing.expect(!matchesFullQuery(q, "alice.hq.definitelyarealcorp.com", "")); try testing.expect(matchesFullQuery(q, "hq.definitelyarealcompany.com", "")); try testing.expect(matchesFullQuery(q, "x.y", "alice hq.definitelyarealcompany")); try testing.expect(!matchesFullQuery(q, "x.y", "alicehq.definitelyarealcompany")); try testing.expect(matchesFullQuery("definitelyarealcompany", "x.y", "日本definitelyarealcompany")); // multi-token: only the long token is checked; the short one matched its key try testing.expect(matchesFullQuery("nate definitelyarealcompany", "x.y", "n definitelyarealcompanyx")); try testing.expect(!matchesFullQuery("nate definitelyarealcompany", "x.y", "nate definitelyarealcorp"));}