1use 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;
24const 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;
39const MAX_NESTING: usize = 128;
42
43static 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#[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#[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
83fn 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
91pub 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 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
116pub 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
151fn 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
392fn 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
465fn 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
486fn 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
513fn 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
542fn 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
582fn 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
593fn 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 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
639fn 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
669fn 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#[derive(Debug, Clone, Default, PartialEq, Eq)]
687pub struct Prepared {
688 pub fingerprints: Vec<String>,
690 pub min_prefix: usize,
692 pub tails: Vec<String>,
694 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 pub fn usable(&self) -> bool {
715 !self.fingerprints.is_empty() && self.min_prefix > 0 && self.min_prefix <= self.fingerprints.len()
716 }
717}
718
719pub 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
734fn 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
751fn 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#[derive(Debug, Clone, PartialEq, Eq)]
786pub struct Request {
787 caller_scope: String,
788 prepared: Prepared,
789}
790
791impl Request {
792 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 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
820fn 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#[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 pub access: u64,
863}
864
865impl Match {
866 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#[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 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 groups: HashMap<String, u64>,
927 prefixes: HashMap<String, HashMap<String, u64>>,
929 tails: HashMap<String, BTreeSet<u64>>,
931}
932
933pub struct Matcher {
936 limits: Limits,
937 namespaces: HashMap<String, Namespace>,
938 groups: HashMap<u64, Group>,
939 lru: BTreeMap<u64, u64>,
941 next_group: u64,
942 next_lru: u64,
943 group_count: usize,
944 prefix_count: usize,
945 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 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 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 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 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 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 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 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 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 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 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 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 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 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 #[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 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 #[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 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 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 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 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 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 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 #[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 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 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 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
1680fn 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#[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 candidate_end - overlap + 1 > 0 || parent_start > 0
1740}
1741
1742#[cfg(test)]
1743#[path = "lcp_tests.rs"]
1744mod tests;