Skip to main content

cpa_server/
lcp.rs

1//! Go's Merkle longest-common-prefix session matcher (sdk/cliproxy/session/lcp.go).
2//!
3//! Requests without an explicit session are reduced to protocol-independent canonical
4//! turns, each turn to a bounded fingerprint, and the fingerprints to rolling Merkle
5//! prefix keys. The matcher remembers which credential served each sequence, so a
6//! conversation that grows, forks or is compacted keeps its credential and a stable
7//! `lcp:v1:` session identity.
8//!
9//! Values are Go byte strings (`Vec<u8>`): fingerprints hash bytes, and samples cut
10//! large values at byte offsets as Go does.
11
12use std::collections::{BTreeMap, BTreeSet, HashMap};
13use std::sync::LazyLock;
14use std::time::{Duration, Instant};
15
16use cpa_common::gostr::{GoStr, lower_bytes, trim_space};
17use cpa_common::json::{self, GoValue, Kind, Res};
18use sha2::{Digest, Sha256};
19
20const TURN_VERSION: &str = "cpa-session-turn-v1";
21const LARGE_PART: usize = 16 * 1024;
22const SPARSE_BYTES: usize = 12 * 1024;
23const DEFAULT_MAX_TURNS: usize = 1024;
24// ponytail: Go's caps, which bound entries, not bytes. With session affinity on and four
25// interleaved agent sessions sending no session ID (counting allocator, 2026-10-06, MB of
26// 1,024 kB), 150-turn conversations at one request every 3 s held 57.7 MB of heap after
27// an hour and then 60.7 to 67.0 MB (the 1 h TTL), and 300-turn conversations at one
28// request a second held 82.2 MB from 40 minutes on, under these caps. Each turn binds a
29// new group, so prefix entries grow with the square of a conversation's length, and every
30// fingerprint and prefix key is a 64-character hex string. Keeping 32-byte digests would
31// cut that without moving the caps; lower caps would be a difference from Go.
32const DEFAULT_MAX_GROUPS: usize = 4096;
33const DEFAULT_MAX_PREFIXES: usize = 262_144;
34const MAX_TURNS: usize = 4096;
35const MAX_PARTS: usize = 256;
36const MIN_COMPACTION_OVERLAP: usize = 2;
37const PROBE_WINDOW: usize = 32;
38const MAX_TAILS_PER_KEY: usize = 16;
39// ponytail: requests nested deeper than this skip the matcher (see `Request::new`); far
40// beyond any conversation. Iterative extraction would lift the ceiling.
41const MAX_NESTING: usize = 128;
42
43// Go RE2: `\d`, `\b` and `\s` are ASCII (`\s` is `[\t\n\f\r ]`, without `\v`); `(?i)`
44// folds Unicode (the `k` of `think` also matches U+212A); `.` with `s` matches any rune,
45// invalid bytes included.
46static ISO8601: LazyLock<regex::bytes::Regex> = LazyLock::new(|| {
47    regex::bytes::Regex::new(r"(?-u)\b\d{4}-\d{2}-\d{2}[T ]\d{2}:\d{2}:\d{2}(?:\.\d+)?(?:Z|[+-]\d{2}:?\d{2})?\b")
48        .unwrap()
49});
50static UUID: LazyLock<regex::bytes::Regex> = LazyLock::new(|| {
51    regex::bytes::Regex::new(
52        r"(?-u)\b[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[1-5][0-9a-fA-F]{3}-[89abAB][0-9a-fA-F]{3}-[0-9a-fA-F]{12}\b",
53    )
54    .unwrap()
55});
56static THINK: LazyLock<regex::bytes::Regex> = LazyLock::new(|| {
57    regex::bytes::Regex::new(r"(?i)[\t\n\x0C\r ]*<(?:think|thinking)>(?s-u:.)*?</(?:think|thinking)>[\t\n\x0C\r ]*")
58        .unwrap()
59});
60
61/// Go `CanonicalPart`.
62#[derive(Debug, Clone, Default, PartialEq, Eq)]
63pub struct Part {
64    pub kind: String,
65    pub mime: String,
66    pub value: Vec<u8>,
67    pub digest: String,
68    pub original_size: i64,
69    pub sampled: bool,
70}
71
72/// Go `CanonicalTurn`.
73#[derive(Debug, Clone, Default, PartialEq, Eq)]
74pub struct Turn {
75    pub role: String,
76    pub parts: Vec<Part>,
77}
78
79fn sha_hex(data: &[u8]) -> String {
80    format!("{:x}", Sha256::digest(data))
81}
82
83/// Go `writeFingerprintField`.
84fn field(hash: &mut Sha256, value: &[u8]) {
85    hash.update(value.len().to_string().as_bytes());
86    hash.update(b":");
87    hash.update(value);
88    hash.update(b"\0");
89}
90
91/// Go `FastTurnFingerprint`.
92pub fn fingerprint(turn: &Turn) -> String {
93    let turn = normalize_turn(turn);
94    let mut hash = Sha256::new();
95    field(&mut hash, TURN_VERSION.as_bytes());
96    field(&mut hash, turn.role.as_bytes());
97    for part in &turn.parts {
98        field(&mut hash, part.kind.as_bytes());
99        field(&mut hash, part.mime.as_bytes());
100        field(&mut hash, part.original_size.to_string().as_bytes());
101        // A sampled system part's digest covers unmasked timestamps; the masked sample
102        // stands in for it.
103        if turn.role != "system" || !part.sampled {
104            field(&mut hash, part.digest.as_bytes());
105        }
106        let large = part.original_size > LARGE_PART as i64 || part.value.len() > LARGE_PART;
107        if !part.sampled && large {
108            field(&mut hash, &sparse_sample(&part.value, SPARSE_BYTES));
109        } else {
110            field(&mut hash, &part.value);
111        }
112    }
113    format!("{:x}", hash.finalize())
114}
115
116/// Go `ExtractCanonicalTurns`: `format` is the Go translator format name; empty infers
117/// it from the payload.
118pub fn extract(format: &str, payload: &[u8]) -> Vec<Turn> {
119    if payload.is_empty() {
120        return Vec::new();
121    }
122    let root = json::parse(payload);
123    if !root.exists() {
124        return Vec::new();
125    }
126    let format = match format.trim() {
127        "" => infer_format(&root),
128        f => f,
129    };
130    let is = |name: &str| format.go_eq_fold(name);
131    let mut turns = Vec::new();
132    if is("claude") {
133        messages_turns(&mut turns, &root, true);
134    } else if is("gemini") || is("antigravity") {
135        gemini_turns(&mut turns, &root);
136    } else if is("interactions") {
137        interaction_turns(&mut turns, &root);
138    } else if is("openai-response") || is("codex") {
139        responses_turns(&mut turns, &root);
140    } else {
141        messages_turns(&mut turns, &root, false);
142    }
143    turns
144        .iter()
145        .map(normalize_turn)
146        .filter(|t| !t.role.is_empty() && !t.parts.is_empty())
147        .take(MAX_TURNS)
148        .collect()
149}
150
151/// gjson `Result.String()`, trimmed and lowercased as Go's `strings.ToLower(strings.TrimSpace(..))`.
152fn lower_trim(value: &Res<'_>) -> String {
153    lower_bytes(trim_space(&value.bytes()))
154}
155
156fn infer_format(root: &Res<'_>) -> &'static str {
157    let mut root = root.clone();
158    let request = root.get("request");
159    if request.exists() && !root.get("contents").exists() {
160        root = request;
161    }
162    if root.get("contents").is_array()
163        || root.get("systemInstruction").exists()
164        || root.get("system_instruction").exists()
165    {
166        return "gemini";
167    }
168    if root.get("instructions").exists() {
169        return "openai-response";
170    }
171    let input = root.get("input");
172    if input.exists() {
173        if input.kind == Kind::String {
174            return "interactions";
175        }
176        for item in input.array() {
177            let typ = lower_trim(&item.get("type"));
178            if typ.contains("user_input") || typ.contains("instruction") {
179                return "interactions";
180            }
181        }
182        return "openai-response";
183    }
184    if root.get("system").exists() {
185        return "claude";
186    }
187    "openai"
188}
189
190fn has_capacity(turns: &[Turn]) -> bool {
191    turns.len() < MAX_TURNS
192}
193
194fn append_turn(turns: &mut Vec<Turn>, role: &str, parts: Vec<Part>) {
195    if !has_capacity(turns) || parts.is_empty() {
196        return;
197    }
198    turns.push(Turn {
199        role: role.to_owned(),
200        parts: limit_parts(Vec::new(), parts),
201    });
202}
203
204fn messages_turns(turns: &mut Vec<Turn>, root: &Res<'_>, top_level_system: bool) {
205    if top_level_system {
206        let system = root.get("system");
207        if system.exists() {
208            append_turn(turns, "system", parts_from(&system));
209        }
210    }
211    root.get("messages").each(|_, message| {
212        if !has_capacity(turns) {
213            return false;
214        }
215        let mut role = canonical_role(&message.get("role").bytes());
216        if role.is_empty() {
217            role = "unknown".into();
218        }
219        let content = message.get("content");
220        let mut parts = parts_from(&content);
221        for key in ["tool_calls", "tool_call", "function_call", "tool_use"] {
222            let value = message.get(key);
223            if value.exists() {
224                parts.extend(parts_from(&value));
225            }
226        }
227        if parts.is_empty() && !content.exists() {
228            parts = parts_from(&message);
229        }
230        append_turn(turns, &role, parts);
231        true
232    });
233}
234
235fn responses_turns(turns: &mut Vec<Turn>, root: &Res<'_>) {
236    let instructions = root.get("instructions");
237    if instructions.exists() {
238        append_turn(turns, "system", parts_from(&instructions));
239    }
240    if !has_capacity(turns) {
241        return;
242    }
243    let input = root.get("input");
244    if !input.exists() {
245        return;
246    }
247    if input.kind == Kind::String {
248        append_turn(turns, "user", parts_from(&input));
249        return;
250    }
251    input.each(|_, item| {
252        if !has_capacity(turns) {
253            return false;
254        }
255        let typ = lower_trim(&item.get("type"));
256        if typ == "reasoning" || typ == "response.output_text" {
257            return true;
258        }
259        let mut role = canonical_role(&item.get("role").bytes());
260        if role.is_empty() {
261            role = if typ.contains("function_call_output") || typ.contains("tool_result") {
262                "tool"
263            } else if typ.contains("function_call") || typ.contains("tool_call") {
264                "assistant"
265            } else if typ.contains("compaction") {
266                "system"
267            } else {
268                "unknown"
269            }
270            .into();
271        }
272        let content = item.get("content");
273        let mut parts = parts_from(&content);
274        if parts.is_empty() && !content.exists() {
275            parts = parts_from(&item);
276        }
277        append_turn(turns, &role, parts);
278        true
279    });
280}
281
282fn gemini_turns(turns: &mut Vec<Turn>, root: &Res<'_>) {
283    let mut root = root.clone();
284    let request = root.get("request");
285    if request.exists() && !root.get("contents").exists() {
286        root = request;
287    }
288    let mut cached = root.get("cachedContent");
289    if !cached.exists() {
290        cached = root.get("cached_content");
291    }
292    if cached.exists() {
293        let mut part = text_part(&cached);
294        part.kind = "resource".into();
295        append_turn(turns, "system", vec![part]);
296    }
297    let system = root.get("systemInstruction");
298    if system.exists() {
299        append_turn(turns, "system", parts_from(&system));
300    } else {
301        let system = root.get("system_instruction");
302        if system.exists() {
303            append_turn(turns, "system", parts_from(&system));
304        }
305    }
306    root.get("contents").each(|_, content| {
307        if !has_capacity(turns) {
308            return false;
309        }
310        let mut role = canonical_role(&content.get("role").bytes());
311        if role.is_empty() {
312            role = "unknown".into();
313        }
314        let content_parts = content.get("parts");
315        let mut parts = parts_from(&content_parts);
316        if parts.is_empty() && !content_parts.exists() {
317            parts = parts_from(&content);
318        }
319        append_turn(turns, &role, parts);
320        true
321    });
322}
323
324fn interaction_turns(turns: &mut Vec<Turn>, root: &Res<'_>) {
325    let system = root.get("system_instruction");
326    if system.exists() {
327        append_turn(turns, "system", parts_from(&system));
328    } else {
329        let system = root.get("systemInstruction");
330        if system.exists() {
331            append_turn(turns, "system", parts_from(&system));
332        }
333    }
334    interaction_value(turns, &root.get("input"), "");
335}
336
337fn interaction_value(turns: &mut Vec<Turn>, value: &Res<'_>, inherited: &str) -> bool {
338    if !value.exists() {
339        return true;
340    }
341    if !has_capacity(turns) {
342        return false;
343    }
344    if value.is_array() {
345        value.each(|_, child| interaction_value(turns, &child, inherited));
346        return has_capacity(turns);
347    }
348    if value.kind != Kind::Json {
349        append_turn(turns, &default_interaction_role(inherited), parts_from(value));
350        return has_capacity(turns);
351    }
352    let steps = value.get("steps");
353    if steps.is_array() {
354        let mut role = canonical_role(&value.get("role").bytes());
355        if role.is_empty() {
356            role = inherited.to_owned();
357        }
358        steps.each(|_, child| interaction_value(turns, &child, &role));
359        return has_capacity(turns);
360    }
361    let typ = lower_trim(&value.get("type"));
362    let mut role = canonical_role(&value.get("role").bytes());
363    if role.is_empty() {
364        role = if typ.contains("system") || typ.contains("developer") {
365            "system".into()
366        } else if typ.contains("user") {
367            "user".into()
368        } else if typ.contains("model") || typ.contains("assistant") {
369            "assistant".into()
370        } else if typ.contains("tool") || typ.contains("function") {
371            "tool".into()
372        } else {
373            default_interaction_role(inherited)
374        };
375    }
376    let content = value.get("content");
377    let mut parts = parts_from(&content);
378    if parts.is_empty() && !content.exists() {
379        parts = parts_from(value);
380    }
381    append_turn(turns, &role, parts);
382    has_capacity(turns)
383}
384
385fn default_interaction_role(inherited: &str) -> String {
386    match canonical_role(inherited.as_bytes()) {
387        role if role.is_empty() => "user".into(),
388        role => role,
389    }
390}
391
392/// Go `canonicalPartsFromJSON`.
393fn parts_from(value: &Res<'_>) -> Vec<Part> {
394    if !value.exists() {
395        return Vec::new();
396    }
397    match value.kind {
398        Kind::String => vec![text_part(value)],
399        Kind::Number | Kind::True | Kind::False => vec![Part {
400            kind: "value".into(),
401            value: value.raw().to_vec(),
402            original_size: value.raw().len() as i64,
403            ..Part::default()
404        }],
405        Kind::Json => {
406            if is_reasoning(value) {
407                return Vec::new();
408            }
409            if value.is_array() {
410                let mut parts = Vec::new();
411                let mut dropped = 0;
412                value.each(|_, child| {
413                    if parts.len() >= MAX_PARTS {
414                        dropped += 1;
415                        return true;
416                    }
417                    let added = parts_from(&child);
418                    parts = limit_parts(std::mem::take(&mut parts), added);
419                    true
420                });
421                if dropped > 0 {
422                    parts = limit_count(parts, dropped);
423                }
424                return parts;
425            }
426            let text = value.get("text");
427            if text.kind == Kind::String {
428                return vec![text_part(&text)];
429            }
430            let content = value.get("content");
431            if content.exists() {
432                return parts_from(&content);
433            }
434            let parts = value.get("parts");
435            if parts.exists() {
436                return parts_from(&parts);
437            }
438            let typ = lower_trim(&value.get("type"));
439            if matches!(typ.as_str(), "input_text" | "output_text" | "text") && text.exists() {
440                return vec![text_part(&text)];
441            }
442            if typ.contains("tool") || typ.contains("function_call") || typ == "function" {
443                return vec![json_part(format!("tool:{typ}"), value)];
444            }
445            if let Some(kind) = gemini_tool_kind(value) {
446                return vec![json_part(kind.into(), value)];
447            }
448            let media = [
449                "image_url",
450                "inlineData",
451                "inline_data",
452                "fileData",
453                "file_data",
454                "source",
455            ];
456            if media.iter().any(|key| value.get(*key).exists()) {
457                return vec![json_part("media".into(), value)];
458            }
459            vec![json_part("json".into(), value)]
460        }
461        Kind::Null => vec![json_part("value".into(), value)],
462    }
463}
464
465/// Go `canonicalTextPart`.
466fn text_part(value: &Res<'_>) -> Part {
467    let text = normalize_text(&value.bytes(), false);
468    if text.len() > LARGE_PART {
469        return Part {
470            kind: "text".into(),
471            value: sparse_sample(&text, SPARSE_BYTES),
472            digest: sha_hex(&text),
473            original_size: text.len() as i64,
474            sampled: true,
475            ..Part::default()
476        };
477    }
478    Part {
479        kind: "text".into(),
480        original_size: text.len() as i64,
481        value: text,
482        ..Part::default()
483    }
484}
485
486/// Go `canonicalJSONPart`: small values as Go re-marshals them after decoding into `any`
487/// (sorted keys, float64 numbers, HTML-escaped); large ones sampled with a digest.
488fn json_part(kind: String, value: &Res<'_>) -> Part {
489    let raw = value.raw();
490    if raw.len() > LARGE_PART {
491        return Part {
492            kind,
493            value: sparse_sample(raw, SPARSE_BYTES),
494            digest: sha_hex(raw),
495            original_size: raw.len() as i64,
496            sampled: true,
497            ..Part::default()
498        };
499    }
500    let raw = GoValue::parse_f64(raw).map_or_else(|| raw.to_vec(), |v| v.marshal());
501    Part {
502        kind,
503        original_size: raw.len() as i64,
504        value: raw,
505        ..Part::default()
506    }
507}
508
509fn is_marker(part: &Part) -> bool {
510    part.kind == "value" && part.value.starts_with(b"<truncated:")
511}
512
513/// Go `limitCanonicalParts`: at most 256 parts, the rest folded into one marker that
514/// counts them.
515fn limit_parts(mut parts: Vec<Part>, mut added: Vec<Part>) -> Vec<Part> {
516    if added.is_empty() {
517        return parts;
518    }
519    let mut existing_dropped = 0;
520    let has_marker = added.last().is_some_and(is_marker);
521    if has_marker {
522        existing_dropped = added.pop().map_or(0, |m| m.original_size);
523    }
524    let space = MAX_PARTS as i64 - parts.len() as i64;
525    if space <= 0 {
526        return limit_count(parts, added.len() as i64 + existing_dropped);
527    }
528    let space = space as usize;
529    if added.len() > space {
530        let dropped = (added.len() - space) as i64 + existing_dropped;
531        added.truncate(space);
532        parts.extend(added);
533        return limit_count(parts, dropped);
534    }
535    parts.extend(added);
536    if has_marker || existing_dropped > 0 {
537        return limit_count(parts, existing_dropped);
538    }
539    parts
540}
541
542/// Go `limitCanonicalPartsCount`.
543fn limit_count(mut parts: Vec<Part>, dropped: i64) -> Vec<Part> {
544    if dropped <= 0 {
545        return parts;
546    }
547    if let Some(marker) = parts.last_mut().filter(|p| is_marker(p)) {
548        marker.original_size += dropped;
549        marker.value = format!("<truncated:{} parts>", marker.original_size).into_bytes();
550        return parts;
551    }
552    parts.push(Part {
553        kind: "value".into(),
554        value: format!("<truncated:{dropped} parts>").into_bytes(),
555        original_size: dropped,
556        ..Part::default()
557    });
558    parts
559}
560
561fn is_reasoning(value: &Res<'_>) -> bool {
562    if value.kind != Kind::Json || value.is_array() {
563        return false;
564    }
565    let typ = lower_trim(&value.get("type"));
566    if matches!(typ.as_str(), "thinking" | "reasoning" | "thought") || typ.contains("reasoning") {
567        return true;
568    }
569    value.get("thought").kind == Kind::True
570}
571
572fn gemini_tool_kind(value: &Res<'_>) -> Option<&'static str> {
573    if value.get("functionCall").exists() || value.get("function_call").exists() {
574        return Some("tool:function_call");
575    }
576    if value.get("functionResponse").exists() || value.get("function_response").exists() {
577        return Some("tool:function_response");
578    }
579    None
580}
581
582/// Go `canonicalRole`.
583fn canonical_role(role: &[u8]) -> String {
584    let role = lower_bytes(trim_space(role));
585    match role.as_str() {
586        "system" | "developer" => "system".into(),
587        "assistant" | "model" | "ai" => "assistant".into(),
588        "tool" | "function" => "tool".into(),
589        _ => role,
590    }
591}
592
593/// Go `normalizeCanonicalTurn`.
594fn normalize_turn(turn: &Turn) -> Turn {
595    let role = canonical_role(turn.role.as_bytes());
596    let mut parts = Vec::with_capacity(turn.parts.len());
597    for part in &turn.parts {
598        if part.value.is_empty() {
599            continue;
600        }
601        let mut part = part.clone();
602        part.kind = lower_bytes(trim_space(part.kind.as_bytes()));
603        part.mime = lower_bytes(trim_space(part.mime.as_bytes()));
604        if part.original_size <= 0 {
605            part.original_size = part.value.len() as i64;
606        }
607        if part.kind == "text" {
608            if role == "system" {
609                part.value = normalize_text(&part.value, true);
610            } else if !part.sampled {
611                part.value = normalize_text(&part.value, false);
612            }
613            if !part.sampled {
614                part.original_size = part.value.len() as i64;
615            }
616        }
617        if !part.value.is_empty() {
618            parts.push(part);
619        }
620    }
621    let mut parts = limit_parts(Vec::new(), parts);
622    // Parallel tool calls in any order fingerprint the same.
623    let tool_indexes: Vec<usize> = parts
624        .iter()
625        .enumerate()
626        .filter(|(_, p)| p.kind.starts_with("tool:") || p.kind.contains("function_call"))
627        .map(|(i, _)| i)
628        .collect();
629    if tool_indexes.len() > 1 {
630        let mut tools: Vec<Part> = tool_indexes.iter().map(|&i| parts[i].clone()).collect();
631        tools.sort_by(|a, b| a.value.cmp(&b.value).then_with(|| a.digest.cmp(&b.digest)));
632        for (i, tool) in tool_indexes.into_iter().zip(tools) {
633            parts[i] = tool;
634        }
635    }
636    Turn { role, parts }
637}
638
639/// Go `normalizeText`: newlines unified, think blocks dropped, system timestamps and
640/// UUIDs masked, then trimmed.
641fn normalize_text(value: &[u8], mask_system_dynamics: bool) -> Vec<u8> {
642    let mut value = value.to_vec();
643    if value.contains(&b'\r') {
644        let mut out = Vec::with_capacity(value.len());
645        let mut i = 0;
646        while i < value.len() {
647            if value[i] == b'\r' {
648                out.push(b'\n');
649                if value.get(i + 1) == Some(&b'\n') {
650                    i += 1;
651                }
652            } else {
653                out.push(value[i]);
654            }
655            i += 1;
656        }
657        value = out;
658    }
659    let value = THINK.replace_all(&value, regex::bytes::NoExpand(b" "));
660    let value = if mask_system_dynamics {
661        let value = ISO8601.replace_all(&value, regex::bytes::NoExpand(b"<timestamp>"));
662        UUID.replace_all(&value, regex::bytes::NoExpand(b"<uuid>")).into_owned()
663    } else {
664        value.into_owned()
665    };
666    trim_space(&value).to_vec()
667}
668
669/// Go `sparseSample`: head, middle and tail thirds of `limit` bytes.
670fn sparse_sample(value: &[u8], limit: usize) -> Vec<u8> {
671    if value.len() <= limit {
672        return value.to_vec();
673    }
674    let head = limit / 3;
675    let middle = limit / 3;
676    let tail = limit - head - middle;
677    let middle_start = (value.len() - middle) / 2;
678    let mut out = Vec::with_capacity(limit);
679    out.extend_from_slice(&value[..head]);
680    out.extend_from_slice(&value[middle_start..middle_start + middle]);
681    out.extend_from_slice(&value[value.len() - tail..]);
682    out
683}
684
685/// Go `PrepareExt`: what a request contributes to matching.
686#[derive(Debug, Clone, Default, PartialEq, Eq)]
687pub struct Prepared {
688    /// One per turn, at most 4096.
689    pub fingerprints: Vec<String>,
690    /// The first prefix that includes a non-system turn (0: none).
691    pub min_prefix: usize,
692    /// The fingerprints of the last 32 turns.
693    pub tails: Vec<String>,
694    /// Go `EnvironmentDigest` over the system turns.
695    pub environment: String,
696}
697
698impl Prepared {
699    pub fn new(turns: &[Turn]) -> Self {
700        let fingerprints: Vec<String> = turns.iter().take(MAX_TURNS).map(fingerprint).collect();
701        let start = turns.len().saturating_sub(PROBE_WINDOW);
702        Self {
703            fingerprints,
704            min_prefix: turns
705                .iter()
706                .position(|t| canonical_role(t.role.as_bytes()) != "system")
707                .map_or(0, |i| i + 1),
708            tails: turns[start..].iter().map(fingerprint).collect(),
709            environment: environment_digest(turns),
710        }
711    }
712
713    /// Go's guard before matching or binding.
714    pub fn usable(&self) -> bool {
715        !self.fingerprints.is_empty() && self.min_prefix > 0 && self.min_prefix <= self.fingerprints.len()
716    }
717}
718
719/// Go `EnvironmentDigest`: every system turn's fingerprint, empty without one.
720pub fn environment_digest(turns: &[Turn]) -> String {
721    let mut hash = Sha256::new();
722    let mut any = false;
723    for turn in turns.iter().filter(|t| canonical_role(t.role.as_bytes()) == "system") {
724        any = true;
725        field(&mut hash, fingerprint(turn).as_bytes());
726    }
727    if any {
728        format!("{:x}", hash.finalize())
729    } else {
730        String::new()
731    }
732}
733
734/// Go `fallbackEnvironmentDigest` and `environmentDigest`: the leading system-turn
735/// fingerprints.
736fn fallback_environment(fingerprints: &[String], min_prefix: usize) -> String {
737    if min_prefix <= 1 || fingerprints.is_empty() {
738        return String::new();
739    }
740    let mut hash = Sha256::new();
741    for fp in &fingerprints[..(min_prefix - 1).min(fingerprints.len())] {
742        field(&mut hash, fp.as_bytes());
743    }
744    format!("{:x}", hash.finalize())
745}
746
747fn last_window(fingerprints: &[String]) -> Vec<String> {
748    fingerprints[fingerprints.len().saturating_sub(PROBE_WINDOW)..].to_vec()
749}
750
751/// Go `rollingPrefixKeys`: `n:hex` where each hash chains the previous one.
752fn rolling_prefix_keys(fingerprints: &[String]) -> Vec<String> {
753    let mut previous = [0u8; 32];
754    fingerprints
755        .iter()
756        .enumerate()
757        .map(|(i, fp)| {
758            let mut hash = Sha256::new();
759            hash.update(previous);
760            hash.update(b"\0");
761            hash.update(fp.as_bytes());
762            previous = hash.finalize().into();
763            let hex: String = previous.iter().map(|b| format!("{b:02x}")).collect();
764            format!("{}:{hex}", i + 1)
765        })
766        .collect()
767}
768
769fn sequence_key(fingerprints: &[String]) -> String {
770    rolling_prefix_keys(fingerprints).pop().unwrap_or_default()
771}
772
773fn session_id(namespace: &str, first_prefix: &str) -> String {
774    let seed = format!("cli-proxy-api:lcp-session:v1\0{namespace}\0{first_prefix}");
775    format!("lcp:v1:{}", sha_hex(seed.as_bytes()))
776}
777
778fn compaction_session_id(namespace: &str, parent: &str, sequence: &str) -> String {
779    let seed = format!("cli-proxy-api:lcp-compaction-session:v1\0{namespace}\0{parent}\0{sequence}");
780    format!("lcp:v1:{}", sha_hex(seed.as_bytes()))
781}
782
783/// What a request without an explicit session brings to selection (Go `pickLCP`'s
784/// inputs): its caller scope and prepared turns.
785#[derive(Debug, Clone, PartialEq, Eq)]
786pub struct Request {
787    caller_scope: String,
788    prepared: Prepared,
789}
790
791impl Request {
792    /// `None` when Go skips the matcher: an anonymous caller (no caller scope) or no
793    /// usable turns (empty, or system turns only). Also `None` for a body nested deeper
794    /// than [`MAX_NESTING`], which Go walks on its growable stack: extraction recurses
795    /// once per level, and a native stack would overflow and abort the server.
796    pub fn new(format: &str, body: &[u8], caller: &str) -> Option<Self> {
797        let caller_scope = cpa_common::session::caller_scope(caller);
798        if caller_scope.is_empty() || nests_deeper(body, MAX_NESTING) {
799            return None;
800        }
801        let prepared = Prepared::new(&extract(format, body));
802        prepared.usable().then_some(Self { caller_scope, prepared })
803    }
804
805    /// Go `lcpAffinityNamespace`. With session affinity on, Go always selects through
806    /// the mixed-provider picker, so the provider is `mixed`.
807    pub fn namespace(&self, model: &str) -> String {
808        format!(
809            "lcp:v1::mixed::{}::{}",
810            crate::scheduler::canonical_model(model),
811            self.caller_scope
812        )
813    }
814
815    pub fn prepared(&self) -> &Prepared {
816        &self.prepared
817    }
818}
819
820/// Whether `body` has more than `limit` arrays and objects open at once (brackets
821/// inside strings do not count).
822fn nests_deeper(body: &[u8], limit: usize) -> bool {
823    let (mut depth, mut in_string, mut escaped) = (0usize, false, false);
824    for &c in body {
825        if in_string {
826            if escaped {
827                escaped = false;
828            } else if c == b'\\' {
829                escaped = true;
830            } else if c == b'"' {
831                in_string = false;
832            }
833            continue;
834        }
835        match c {
836            b'"' => in_string = true,
837            b'{' | b'[' => {
838                depth += 1;
839                if depth > limit {
840                    return true;
841                }
842            }
843            b'}' | b']' => depth = depth.saturating_sub(1),
844            _ => {}
845        }
846    }
847    false
848}
849
850/// Go `MerklePrefixMatch` (and `MerklePrefixBindResult`, which has no credential or
851/// prefix length).
852#[derive(Debug, Clone, Default, PartialEq, Eq)]
853pub struct Match {
854    pub auth: String,
855    pub session: String,
856    pub parent: String,
857    pub prefix_length: usize,
858    pub fork: bool,
859    pub compaction: bool,
860    pub node_kind: String,
861    /// The access generation that guards later removal.
862    pub access: u64,
863}
864
865impl Match {
866    /// The session hierarchy Go's selector writes into the request metadata after a
867    /// pick (`node_kind`, `is_fork`, `is_compaction`): a plain hit carries none.
868    pub fn node(&self) -> (&'static str, bool, bool) {
869        if self.fork {
870            ("fork", true, false)
871        } else if self.compaction {
872            ("compaction", false, true)
873        } else {
874            ("", false, false)
875        }
876    }
877}
878
879/// Go `MerklePrefixMatcherConfig`.
880#[derive(Debug, Clone, Copy, Default)]
881pub struct Limits {
882    pub ttl: Duration,
883    pub max_turns: usize,
884    pub max_groups: usize,
885    pub max_prefixes: usize,
886}
887
888struct Group {
889    key: String,
890    namespace: String,
891    auth: String,
892    session: String,
893    parent: String,
894    min_prefix: usize,
895    fork: bool,
896    compaction: bool,
897    node_kind: String,
898    environment: String,
899    fingerprints: Vec<String>,
900    tails: Vec<String>,
901    prefix_keys: Vec<String>,
902    expires: Instant,
903    last_access: u64,
904    lru: u64,
905}
906
907impl Group {
908    /// The tail window indexed for compaction (Go falls back to all fingerprints).
909    fn tail_window(&self) -> &[String] {
910        if self.tails.is_empty() {
911            &self.fingerprints
912        } else {
913            &self.tails
914        }
915    }
916}
917
918fn tail_key(tails: &[String]) -> Option<String> {
919    let n = tails.len();
920    (n >= MIN_COMPACTION_OVERLAP).then(|| format!("{}\0{}", tails[n - 2], tails[n - 1]))
921}
922
923#[derive(Default)]
924struct Namespace {
925    /// Sequence key to group.
926    groups: HashMap<String, u64>,
927    /// Prefix key to the groups (by sequence key) whose trajectory has that prefix.
928    prefixes: HashMap<String, HashMap<String, u64>>,
929    /// The last two tail fingerprints to the groups ending with them.
930    tails: HashMap<String, BTreeSet<u64>>,
931}
932
933/// Go `MerklePrefixMatcher`: bounded (by groups and prefix entries, least recently used
934/// first), expiring after the TTL, with no background task. Callers serialize access.
935pub struct Matcher {
936    limits: Limits,
937    namespaces: HashMap<String, Namespace>,
938    groups: HashMap<u64, Group>,
939    /// LRU order: sequence number to group.
940    lru: BTreeMap<u64, u64>,
941    next_group: u64,
942    next_lru: u64,
943    group_count: usize,
944    prefix_count: usize,
945    /// Monotonic across `clear`, so a pre-clear generation never evicts a newer binding.
946    access: u64,
947    operations: u64,
948}
949
950impl Default for Matcher {
951    fn default() -> Self {
952        Self::new(Limits::default())
953    }
954}
955
956impl Matcher {
957    /// Go `NewMerklePrefixMatcherWithConfig`, defaults included.
958    pub fn new(limits: Limits) -> Self {
959        let mut limits = limits;
960        if limits.ttl.is_zero() {
961            limits.ttl = Duration::from_secs(3600);
962        }
963        if limits.max_turns == 0 {
964            limits.max_turns = DEFAULT_MAX_TURNS;
965        }
966        if limits.max_groups == 0 {
967            limits.max_groups = DEFAULT_MAX_GROUPS;
968        }
969        if limits.max_prefixes == 0 {
970            limits.max_prefixes = DEFAULT_MAX_PREFIXES;
971        }
972        limits.max_prefixes = limits.max_prefixes.max(limits.max_turns);
973        Self {
974            limits,
975            namespaces: HashMap::new(),
976            groups: HashMap::new(),
977            lru: BTreeMap::new(),
978            next_group: 0,
979            next_lru: 0,
980            group_count: 0,
981            prefix_count: 0,
982            access: 0,
983            operations: 0,
984        }
985    }
986
987    /// A fresh matcher on `limits` that keeps counting access generations, so a lease
988    /// picked before the change never evicts a binding made after it.
989    pub fn reset(&mut self, limits: Limits) {
990        let access = self.access;
991        *self = Self::new(limits);
992        self.access = access;
993    }
994
995    pub fn limits(&self) -> Limits {
996        self.limits
997    }
998
999    /// Go's public-method defaults for missing tails and environment, then
1000    /// `sanitizeFingerprints` (at most `max_turns` fingerprints).
1001    fn context<'p>(&self, prepared: &'p Prepared) -> Option<(&'p [String], Vec<String>, String)> {
1002        let tails = if prepared.tails.is_empty() {
1003            last_window(&prepared.fingerprints)
1004        } else {
1005            prepared.tails.clone()
1006        };
1007        let environment = if prepared.environment.is_empty() {
1008            fallback_environment(&prepared.fingerprints, prepared.min_prefix)
1009        } else {
1010            prepared.environment.clone()
1011        };
1012        if !prepared.usable() {
1013            return None;
1014        }
1015        let fingerprints = &prepared.fingerprints[..prepared.fingerprints.len().min(self.limits.max_turns)];
1016        (prepared.min_prefix <= fingerprints.len()).then_some((fingerprints, tails, environment))
1017    }
1018
1019    /// Go `MatchFingerprintsWithContext`: the longest known prefix, a fork of it, or a
1020    /// compaction continuation.
1021    pub fn find(&mut self, namespace: &str, prepared: &Prepared, now: Instant) -> Option<Match> {
1022        if namespace.is_empty() {
1023            return None;
1024        }
1025        let (fingerprints, tails, environment) = self.context(prepared)?;
1026        self.tick(now);
1027        self.match_locked(namespace, fingerprints, &tails, &environment, prepared.min_prefix, now)
1028    }
1029
1030    /// Go `BindFingerprintsWithContext`: records the sequence for `auth`; the result
1031    /// carries its session identity. `None` when nothing could be bound.
1032    pub fn bind(&mut self, namespace: &str, prepared: &Prepared, auth: &str, now: Instant) -> Option<Match> {
1033        let auth = auth.trim();
1034        if namespace.trim().is_empty() || auth.is_empty() {
1035            return None;
1036        }
1037        let (fingerprints, tails, environment) = self.context(prepared)?;
1038        self.tick(now);
1039        let bound = self.bind_locked(
1040            namespace,
1041            fingerprints,
1042            tails,
1043            environment,
1044            prepared.min_prefix,
1045            auth,
1046            now,
1047        );
1048        (!bound.session.is_empty()).then_some(bound)
1049    }
1050
1051    /// Go `TouchFingerprintsWithContext`: refreshes the sequence if `auth` still owns it,
1052    /// or binds a new extension. False when another credential took it over.
1053    pub fn touch(&mut self, namespace: &str, prepared: &Prepared, auth: &str, now: Instant) -> bool {
1054        let auth = auth.trim();
1055        if namespace.trim().is_empty() || auth.is_empty() {
1056            return false;
1057        }
1058        let Some((fingerprints, tails, environment)) = self.context(prepared) else {
1059            return false;
1060        };
1061        self.tick(now);
1062        self.touch_locked(
1063            namespace,
1064            fingerprints,
1065            tails,
1066            environment,
1067            prepared.min_prefix,
1068            auth,
1069            now,
1070        )
1071    }
1072
1073    /// Go `RemoveFingerprintsBefore`: drops the exact sequence bound to `auth` unless it
1074    /// was refreshed after `generation` (0: unconditionally).
1075    pub fn remove(
1076        &mut self,
1077        namespace: &str,
1078        fingerprints: &[String],
1079        auth: &str,
1080        generation: u64,
1081        now: Instant,
1082    ) -> bool {
1083        if namespace.is_empty() || auth.is_empty() || fingerprints.is_empty() {
1084            return false;
1085        }
1086        let fingerprints = &fingerprints[..fingerprints.len().min(self.limits.max_turns)];
1087        self.tick(now);
1088        let Some(ns) = self.namespaces.get(namespace) else {
1089            return false;
1090        };
1091        let Some(&id) = ns.groups.get(&sequence_key(fingerprints)) else {
1092            return false;
1093        };
1094        let group = &self.groups[&id];
1095        if group.auth != auth || (generation > 0 && group.last_access > generation) {
1096            return false;
1097        }
1098        self.remove_group(id);
1099        true
1100    }
1101
1102    /// Go `InvalidateAuth`.
1103    pub fn invalidate(&mut self, auth: &str) {
1104        if auth.is_empty() {
1105            return;
1106        }
1107        let ids: Vec<u64> = self.ordered_ids(|g| g.auth == auth);
1108        ids.into_iter().for_each(|id| {
1109            self.remove_group(id);
1110        });
1111    }
1112
1113    /// Drops the bindings of credentials `keep` rejects (removed credentials).
1114    pub fn retain(&mut self, keep: impl Fn(&str) -> bool) {
1115        let ids = self.ordered_ids(|g| !keep(&g.auth));
1116        ids.into_iter().for_each(|id| {
1117            self.remove_group(id);
1118        });
1119    }
1120
1121    /// Go `Clear`; the access counter keeps counting.
1122    pub fn clear(&mut self) {
1123        self.namespaces.clear();
1124        self.groups.clear();
1125        self.lru.clear();
1126        self.group_count = 0;
1127        self.prefix_count = 0;
1128    }
1129
1130    /// Go `LookupSession`: the credentials bound to an LCP session (sorted) and its
1131    /// namespace, without refreshing anything; expired groups are dropped.
1132    pub fn lookup(&mut self, session: &str, now: Instant) -> Option<(Vec<String>, String)> {
1133        if session.is_empty() {
1134            return None;
1135        }
1136        let expired = self.ordered_ids(|g| g.session == session && now >= g.expires);
1137        expired.into_iter().for_each(|id| {
1138            self.remove_group(id);
1139        });
1140        let active = self.ordered_ids(|g| g.session == session);
1141        let namespace = self.groups.get(active.first()?)?.namespace.clone();
1142        let mut auths: Vec<String> = active
1143            .iter()
1144            .map(|id| self.groups[id].auth.clone())
1145            .filter(|a| !a.is_empty())
1146            .collect();
1147        auths.sort();
1148        auths.dedup();
1149        (!auths.is_empty()).then_some((auths, namespace))
1150    }
1151
1152    /// Group IDs (creation order) whose group satisfies `keep`.
1153    fn ordered_ids(&self, keep: impl Fn(&Group) -> bool) -> Vec<u64> {
1154        let mut ids: Vec<u64> = self.groups.iter().filter(|(_, g)| keep(g)).map(|(id, _)| *id).collect();
1155        ids.sort_unstable();
1156        ids
1157    }
1158
1159    /// Go `prepareLocked`: an expiry sweep every 128 operations.
1160    fn tick(&mut self, now: Instant) {
1161        self.operations += 1;
1162        if self.operations.is_multiple_of(128) {
1163            let expired = self.ordered_ids(|g| now >= g.expires);
1164            expired.into_iter().for_each(|id| {
1165                self.remove_group(id);
1166            });
1167        }
1168    }
1169
1170    fn next_access(&mut self) -> u64 {
1171        self.access += 1;
1172        self.access
1173    }
1174
1175    fn move_to_back(&mut self, id: u64) {
1176        let seq = self.next_lru;
1177        self.next_lru += 1;
1178        if let Some(group) = self.groups.get_mut(&id) {
1179            self.lru.remove(&group.lru);
1180            group.lru = seq;
1181            self.lru.insert(seq, id);
1182        }
1183    }
1184
1185    /// Go `touchLocked`.
1186    #[allow(clippy::too_many_arguments)]
1187    fn touch_locked(
1188        &mut self,
1189        namespace: &str,
1190        fingerprints: &[String],
1191        tails: Vec<String>,
1192        environment: String,
1193        min_prefix: usize,
1194        auth: &str,
1195        now: Instant,
1196    ) -> bool {
1197        let key = sequence_key(fingerprints);
1198        let existing = self
1199            .namespaces
1200            .entry(namespace.to_owned())
1201            .or_default()
1202            .groups
1203            .get(&key)
1204            .copied();
1205        let Some(id) = existing else {
1206            self.bind_locked(namespace, fingerprints, tails, environment, min_prefix, auth, now);
1207            return true;
1208        };
1209        if now >= self.groups[&id].expires {
1210            self.remove_group(id);
1211            self.bind_locked(namespace, fingerprints, tails, environment, min_prefix, auth, now);
1212            return true;
1213        }
1214        let group = self.groups.get_mut(&id).expect("indexed group");
1215        if group.auth != auth {
1216            if group.auth == "home-pending" || group.auth.is_empty() {
1217                group.auth = auth.to_owned();
1218            } else {
1219                // A delayed success never overwrites a failover's newer binding.
1220                return false;
1221            }
1222        }
1223        let access = self.next_access();
1224        let ttl = self.limits.ttl;
1225        let group = self.groups.get_mut(&id).expect("indexed group");
1226        group.expires = now + ttl;
1227        group.last_access = access;
1228        group.environment = environment;
1229        if !tails.is_empty() && group.tails != tails {
1230            let mut group = self.remove_group(id).expect("indexed group");
1231            group.tails = tails;
1232            self.add_group(id, group);
1233        }
1234        self.move_to_back(id);
1235        true
1236    }
1237
1238    /// Go `bindLocked`.
1239    #[allow(clippy::too_many_arguments)]
1240    fn bind_locked(
1241        &mut self,
1242        namespace: &str,
1243        fingerprints: &[String],
1244        mut tails: Vec<String>,
1245        mut environment: String,
1246        min_prefix: usize,
1247        auth: &str,
1248        now: Instant,
1249    ) -> Match {
1250        if tails.is_empty() {
1251            tails = last_window(fingerprints);
1252        }
1253        if environment.is_empty() {
1254            environment = fallback_environment(fingerprints, min_prefix);
1255        }
1256        let key = sequence_key(fingerprints);
1257        let existing = self
1258            .namespaces
1259            .entry(namespace.to_owned())
1260            .or_default()
1261            .groups
1262            .get(&key)
1263            .copied();
1264        if let Some(id) = existing {
1265            let live = now < self.groups[&id].expires;
1266            let old = self.remove_group(id).expect("indexed group");
1267            if live {
1268                // Rebinding keeps the sequence's identity and lineage.
1269                let access = self.next_access();
1270                let group = Group {
1271                    key,
1272                    namespace: namespace.to_owned(),
1273                    auth: auth.to_owned(),
1274                    session: old.session.clone(),
1275                    parent: old.parent.clone(),
1276                    min_prefix,
1277                    fork: old.fork,
1278                    compaction: old.compaction,
1279                    node_kind: old.node_kind.clone(),
1280                    environment,
1281                    fingerprints: fingerprints.to_vec(),
1282                    tails,
1283                    prefix_keys: old.prefix_keys,
1284                    expires: now + self.limits.ttl,
1285                    last_access: access,
1286                    lru: 0,
1287                };
1288                let id = self.new_id();
1289                let access = self.add_group(id, group);
1290                return Match {
1291                    session: old.session,
1292                    parent: old.parent,
1293                    fork: old.fork,
1294                    compaction: old.compaction,
1295                    node_kind: old.node_kind,
1296                    access,
1297                    ..Match::default()
1298                };
1299            }
1300        }
1301        let mut auth = auth.to_owned();
1302        let found = self.match_locked(namespace, fingerprints, &tails, &environment, min_prefix, now);
1303        let mut bound = Match::default();
1304        if let Some(found) = found {
1305            if found.compaction && !found.auth.is_empty() && auth.is_empty() {
1306                auth = found.auth.clone();
1307            }
1308            bound = Match {
1309                auth: String::new(),
1310                prefix_length: 0,
1311                ..found
1312            };
1313        }
1314        let prefix_keys = rolling_prefix_keys(fingerprints);
1315        if bound.session.is_empty() {
1316            let first = match prefix_keys.len() {
1317                0 => String::new(),
1318                n => prefix_keys[if min_prefix > 0 && min_prefix <= n {
1319                    min_prefix - 1
1320                } else {
1321                    0
1322                }]
1323                .clone(),
1324            };
1325            bound.session = session_id(namespace, &first);
1326        }
1327        let access = self.next_access();
1328        let group = Group {
1329            key,
1330            namespace: namespace.to_owned(),
1331            auth,
1332            session: bound.session.clone(),
1333            parent: bound.parent.clone(),
1334            min_prefix,
1335            fork: bound.fork,
1336            compaction: bound.compaction,
1337            node_kind: bound.node_kind.clone(),
1338            environment,
1339            fingerprints: fingerprints.to_vec(),
1340            tails,
1341            prefix_keys,
1342            expires: now + self.limits.ttl,
1343            last_access: access,
1344            lru: 0,
1345        };
1346        let id = self.new_id();
1347        bound.access = self.add_group(id, group);
1348        bound
1349    }
1350
1351    fn new_id(&mut self) -> u64 {
1352        self.next_group += 1;
1353        self.next_group
1354    }
1355
1356    /// Go `addGroupLocked`: indexes the group, then evicts least recently used groups
1357    /// past the bounds. Returns the group's access generation.
1358    fn add_group(&mut self, id: u64, mut group: Group) -> u64 {
1359        if group.prefix_keys.is_empty() {
1360            group.prefix_keys = rolling_prefix_keys(&group.fingerprints);
1361        }
1362        let ns = self.namespaces.entry(group.namespace.clone()).or_default();
1363        ns.groups.insert(group.key.clone(), id);
1364        for prefix in &group.prefix_keys {
1365            ns.prefixes
1366                .entry(prefix.clone())
1367                .or_default()
1368                .insert(group.key.clone(), id);
1369        }
1370        if let Some(tail) = tail_key(group.tail_window()) {
1371            ns.tails.entry(tail).or_default().insert(id);
1372        }
1373        group.last_access = self.next_access();
1374        group.lru = self.next_lru;
1375        self.lru.insert(self.next_lru, id);
1376        self.next_lru += 1;
1377        self.group_count += 1;
1378        self.prefix_count += group.prefix_keys.len();
1379        let access = group.last_access;
1380        self.groups.insert(id, group);
1381        while self.group_count > self.limits.max_groups || self.prefix_count > self.limits.max_prefixes {
1382            let Some((_, &oldest)) = self.lru.first_key_value() else {
1383                break;
1384            };
1385            self.remove_group(oldest);
1386        }
1387        access
1388    }
1389
1390    /// Go `removeGroupLocked`.
1391    fn remove_group(&mut self, id: u64) -> Option<Group> {
1392        let group = self.groups.remove(&id)?;
1393        if let Some(ns) = self.namespaces.get_mut(&group.namespace) {
1394            if ns.groups.get(&group.key) == Some(&id) {
1395                ns.groups.remove(&group.key);
1396            }
1397            for prefix in &group.prefix_keys {
1398                if let Some(bucket) = ns.prefixes.get_mut(prefix) {
1399                    bucket.remove(&group.key);
1400                    if bucket.is_empty() {
1401                        ns.prefixes.remove(prefix);
1402                    }
1403                }
1404            }
1405            if let Some(tail) = tail_key(group.tail_window())
1406                && let Some(bucket) = ns.tails.get_mut(&tail)
1407            {
1408                bucket.remove(&id);
1409                if bucket.is_empty() {
1410                    ns.tails.remove(&tail);
1411                }
1412            }
1413            if ns.groups.is_empty() {
1414                self.namespaces.remove(&group.namespace);
1415            }
1416        }
1417        self.lru.remove(&group.lru);
1418        self.group_count = self.group_count.saturating_sub(1);
1419        self.prefix_count = self.prefix_count.saturating_sub(group.prefix_keys.len());
1420        Some(group)
1421    }
1422
1423    /// Go `matchLocked`: binary search for the longest live prefix.
1424    fn match_locked(
1425        &mut self,
1426        namespace: &str,
1427        fingerprints: &[String],
1428        tails: &[String],
1429        environment: &str,
1430        min_prefix: usize,
1431        now: Instant,
1432    ) -> Option<Match> {
1433        if !self.namespaces.contains_key(namespace)
1434            || fingerprints.is_empty()
1435            || min_prefix == 0
1436            || min_prefix > fingerprints.len()
1437        {
1438            return None;
1439        }
1440        let prefix_keys = rolling_prefix_keys(fingerprints);
1441        let (mut low, mut high) = (min_prefix, fingerprints.len());
1442        let mut best = None;
1443        let mut best_len = 0;
1444        while low <= high {
1445            let middle = low + (high - low) / 2;
1446            match self.newest_matching(namespace, &prefix_keys[middle - 1], &fingerprints[..middle], now) {
1447                Some(id) => {
1448                    best = Some(id);
1449                    best_len = middle;
1450                    low = middle + 1;
1451                }
1452                None => high = middle - 1,
1453            }
1454        }
1455        let Some(id) = best else {
1456            return self.match_compaction(
1457                namespace,
1458                fingerprints,
1459                tails,
1460                environment,
1461                &prefix_keys,
1462                min_prefix,
1463                0,
1464                now,
1465            );
1466        };
1467        let access = self.next_access();
1468        let ttl = self.limits.ttl;
1469        let group = self.groups.get_mut(&id).expect("indexed group");
1470        group.expires = now + ttl;
1471        group.last_access = access;
1472        let (mut session, mut parent, mut node_kind) =
1473            (group.session.clone(), group.parent.clone(), group.node_kind.clone());
1474        let (auth, group_compaction, group_len) = (group.auth.clone(), group.compaction, group.fingerprints.len());
1475        self.move_to_back(id);
1476        let mut fork = false;
1477        // A request that leaves the known trajectory after the common prefix is a fork,
1478        // unless it keeps a trailing run of the parent (an in-place compaction).
1479        if best_len < group_len && fingerprints.len() > best_len {
1480            if let Some(found) = self.match_compaction(
1481                namespace,
1482                fingerprints,
1483                tails,
1484                environment,
1485                &prefix_keys,
1486                min_prefix,
1487                best_len,
1488                now,
1489            ) {
1490                return Some(found);
1491            }
1492            fork = true;
1493            node_kind = "fork".into();
1494            parent = session_id(namespace, &prefix_keys[best_len - 1]);
1495            session = session_id(namespace, &prefix_keys[best_len]);
1496        }
1497        Some(Match {
1498            auth,
1499            session,
1500            parent,
1501            prefix_length: best_len,
1502            fork,
1503            compaction: group_compaction && !fork,
1504            node_kind,
1505            access,
1506        })
1507    }
1508
1509    /// Go `newestMatchingGroup`: the longest live trajectory with this exact prefix,
1510    /// most recently accessed first.
1511    fn newest_matching(&self, namespace: &str, prefix: &str, fingerprints: &[String], now: Instant) -> Option<u64> {
1512        let bucket = self.namespaces.get(namespace)?.prefixes.get(prefix)?;
1513        let mut best: Option<&Group> = None;
1514        let mut best_id = None;
1515        for id in bucket.values() {
1516            let Some(group) = self.groups.get(id) else { continue };
1517            if now >= group.expires
1518                || group.min_prefix > fingerprints.len()
1519                || group.fingerprints.len() < fingerprints.len()
1520                || group.fingerprints[..fingerprints.len()] != *fingerprints
1521            {
1522                continue;
1523            }
1524            let better = match best {
1525                None => true,
1526                Some(b) => {
1527                    group.fingerprints.len() > b.fingerprints.len()
1528                        || (group.fingerprints.len() == b.fingerprints.len()
1529                            && (group.last_access > b.last_access
1530                                || (group.last_access == b.last_access && group.expires > b.expires)))
1531                }
1532            };
1533            if better {
1534                best = Some(group);
1535                best_id = Some(*id);
1536            }
1537        }
1538        best_id
1539    }
1540
1541    /// Go `matchCompactionLocked`: the one lineage leaf whose tail the request's tail
1542    /// continues after its history was summarized or truncated.
1543    #[allow(clippy::too_many_arguments)]
1544    fn match_compaction(
1545        &mut self,
1546        namespace: &str,
1547        fingerprints: &[String],
1548        tails: &[String],
1549        environment: &str,
1550        _prefix_keys: &[String],
1551        min_prefix: usize,
1552        best_len: usize,
1553        now: Instant,
1554    ) -> Option<Match> {
1555        let owned;
1556        let candidate_tail = if tails.is_empty() {
1557            owned = last_window(fingerprints);
1558            &owned[..]
1559        } else {
1560            tails
1561        };
1562        let n = candidate_tail.len();
1563        if n < MIN_COMPACTION_OVERLAP {
1564            return None;
1565        }
1566        let mut candidates: Vec<u64> = Vec::new();
1567        let mut best_overlap = 0;
1568        let mut overflow = false;
1569        for end in (MIN_COMPACTION_OVERLAP - 1..n).rev() {
1570            let key = format!("{}\0{}", candidate_tail[end - 1], candidate_tail[end]);
1571            let ns = self.namespaces.get_mut(namespace)?;
1572            let Some(bucket) = ns.tails.get_mut(&key) else { continue };
1573            // Lazily prune expired groups from the bucket.
1574            let groups = &self.groups;
1575            bucket.retain(|id| groups.get(id).is_some_and(|g| now < g.expires));
1576            if bucket.is_empty() {
1577                ns.tails.remove(&key);
1578                continue;
1579            }
1580            if bucket.len() > MAX_TAILS_PER_KEY {
1581                overflow = true;
1582                continue;
1583            }
1584            for id in bucket.iter() {
1585                let group = &groups[id];
1586                if group.environment != environment {
1587                    continue;
1588                }
1589                let parent_tail = group.tail_window();
1590                let t_len = parent_tail.len();
1591                if t_len < MIN_COMPACTION_OVERLAP {
1592                    continue;
1593                }
1594                let overlap = overlap(candidate_tail, parent_tail, end, t_len - 1);
1595                if overlap >= MIN_COMPACTION_OVERLAP
1596                    && is_compaction_overlap(
1597                        fingerprints.len(),
1598                        n,
1599                        end,
1600                        group.fingerprints.len(),
1601                        t_len,
1602                        t_len - 1,
1603                        overlap,
1604                        min_prefix,
1605                        best_len,
1606                    )
1607                {
1608                    if overlap > best_overlap {
1609                        best_overlap = overlap;
1610                        candidates = vec![*id];
1611                    } else if overlap == best_overlap && !candidates.iter().any(|c| groups[c].session == group.session)
1612                    {
1613                        candidates.push(*id);
1614                    }
1615                }
1616            }
1617        }
1618        if overflow || candidates.is_empty() {
1619            return None;
1620        }
1621        let leaves: Vec<u64> = candidates
1622            .iter()
1623            .copied()
1624            .filter(|c1| {
1625                let s1 = &self.groups[c1].session;
1626                !candidates.iter().any(|c2| {
1627                    let s2 = &self.groups[c2].session;
1628                    s1 != s2 && self.is_ancestor(namespace, s1, s2)
1629                })
1630            })
1631            .collect();
1632        // Several unrelated lineages with the same overlap are ambiguous.
1633        let [id] = leaves[..] else { return None };
1634        let access = self.next_access();
1635        let ttl = self.limits.ttl;
1636        let group = self.groups.get_mut(&id).expect("indexed group");
1637        group.expires = now + ttl;
1638        group.last_access = access;
1639        let (auth, parent) = (group.auth.clone(), group.session.clone());
1640        self.move_to_back(id);
1641        Some(Match {
1642            auth,
1643            session: compaction_session_id(namespace, &parent, &sequence_key(fingerprints)),
1644            parent,
1645            prefix_length: best_overlap,
1646            fork: false,
1647            compaction: true,
1648            node_kind: "compaction".into(),
1649            access,
1650        })
1651    }
1652
1653    /// Go `isAncestorSession`: walks parent links (at most 32) from `descendant`.
1654    fn is_ancestor(&self, namespace: &str, ancestor: &str, descendant: &str) -> bool {
1655        let Some(ns) = self.namespaces.get(namespace) else {
1656            return false;
1657        };
1658        if ancestor.is_empty() || descendant.is_empty() || ancestor == descendant {
1659            return false;
1660        }
1661        let mut ids: Vec<u64> = ns.groups.values().copied().collect();
1662        ids.sort_unstable();
1663        let mut current = descendant.to_owned();
1664        for _ in 0..32 {
1665            let parent = ids
1666                .iter()
1667                .filter_map(|id| self.groups.get(id))
1668                .find(|g| g.session == current && !g.parent.is_empty())
1669                .map(|g| g.parent.clone());
1670            let Some(parent) = parent else { return false };
1671            if parent == ancestor {
1672                return true;
1673            }
1674            current = parent;
1675        }
1676        false
1677    }
1678}
1679
1680/// Go `calculateOverlap`: the common run ending at both positions, at most 32.
1681fn overlap(candidate: &[String], parent: &[String], candidate_end: usize, parent_end: usize) -> usize {
1682    let mut overlap = 0;
1683    while overlap < PROBE_WINDOW
1684        && candidate_end >= overlap
1685        && parent_end >= overlap
1686        && candidate[candidate_end - overlap] == parent[parent_end - overlap]
1687    {
1688        overlap += 1;
1689    }
1690    overlap
1691}
1692
1693/// Go `isCompactionOverlap`, in Go's signed arithmetic.
1694#[allow(clippy::too_many_arguments)]
1695fn is_compaction_overlap(
1696    full_candidate: usize,
1697    candidate_tail: usize,
1698    candidate_end: usize,
1699    full_parent: usize,
1700    parent_tail: usize,
1701    parent_end: usize,
1702    overlap: usize,
1703    min_prefix: usize,
1704    best_len: usize,
1705) -> bool {
1706    let [
1707        full_candidate,
1708        candidate_tail,
1709        candidate_end,
1710        full_parent,
1711        parent_tail,
1712        parent_end,
1713        overlap,
1714        min_prefix,
1715        best_len,
1716    ] = [
1717        full_candidate,
1718        candidate_tail,
1719        candidate_end,
1720        full_parent,
1721        parent_tail,
1722        parent_end,
1723        overlap,
1724        min_prefix,
1725        best_len,
1726    ]
1727    .map(|v| v as i64);
1728    let candidate_start_in_tail = candidate_end - overlap + 1;
1729    let parent_start = full_parent - 1 - (parent_tail - 1 - parent_end) - overlap + 1;
1730    let allowed_start = min_prefix.max(best_len + 1);
1731    if candidate_start_in_tail > 0 {
1732        let candidate_start = full_candidate - 1 - (candidate_tail - 1 - candidate_end) - overlap + 1;
1733        if candidate_start > allowed_start {
1734            return false;
1735        }
1736    }
1737    // History was reduced: early candidate turns were summarized, or early parent turns
1738    // were truncated away.
1739    candidate_end - overlap + 1 > 0 || parent_start > 0
1740}
1741
1742#[cfg(test)]
1743#[path = "lcp_tests.rs"]
1744mod tests;