lean_ctx_patterns/
template_collapse.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Template collapse for the governor's R4 rule.
4//!
5//! [`super::lossless_collapse`] only folds byte-identical lines, so real logs,
6//! lint output and exports, whose lines differ in a timestamp, a sequence
7//! number or an id, never shrink. Here every line is reduced to a *template*:
8//! its variable fields become a placeholder. Variable fields are maximal ASCII
9//! alphanumeric words that are
10//! - a number (`2026`, `750`, the `03` of `2026-03-14`), except a short
11//!   enumeration suffix of a name (`worker-2`, `shard_7`: at most
12//!   [`MAX_NAME_SUFFIX_DIGITS`] digits after `<letter>-`/`<letter>_`),
13//! - a number with a short unit or separator letter (`750ms`, `14T10`,
14//!   `411Z`, `0x1f`: starts with a digit, at most three letters),
15//! - a hex id of at least [`MIN_HEX_ID`] characters with a digit
16//!   (`fc56b260`), or a UUID.
17//!
18//! Decimals, IP addresses, durations and dates follow from these rules.
19//! Words such as lint codes (`W501`, `E201`), hosts, paths and messages are
20//! not variable, so two lines with different text never share a template.
21//!
22//! Lines sharing one template at least [`MIN_GROUP`] times are shown once,
23//! where the first one was, as `[N× like] <first line> … last: <changed part
24//! of the last line>`. Everything else stays verbatim and in order. This is
25//! lossy for the reader; the caller keeps the full output in the archive and
26//! names it. The result is a pure function of the input (#498): no clock, no
27//! hash-map order reaches the output.
28//!
29//! Safety classes:
30//! - Input with a diff hunk is refused whole: every diff line matters.
31//! - Protected lines are never grouped: test-runner lines, Python traceback
32//!   blocks (header, indented frames, exception line) and indented
33//!   continuation lines right after a severity line.
34//! - JSON records (lines opening with `{`, or a `[` line that parses as
35//!   JSON) are never grouped: in an export the numbers are the data.
36//! - Severity lines (error, warning, failure, panic, exception words) stay
37//!   verbatim while all of them together fit in [`SEVERITY_VERBATIM_BYTES`].
38//!   Past that, each distinct normalized message is kept once with its count,
39//!   grouped only with lines of the same severity template, never with plain
40//!   lines. A rare error therefore stays visible: its text differs from the
41//!   surrounding retries, so its template has fewer than [`MIN_GROUP`]
42//!   members and the line stays verbatim.
43
44use std::collections::HashMap;
45
46/// Fewest lines sharing a template that are collapsed. A group line costs
47/// about two lines (first line plus the changed tail of the last), so eight
48/// members save at least 75 % of them; smaller sets are usually distinct
49/// events the reader wants to see one by one.
50pub const MIN_GROUP: usize = 8;
51
52/// All severity lines stay verbatim while their total size stays below this
53/// (about 1,000 tokens); past it each distinct message is kept once.
54pub const SEVERITY_VERBATIM_BYTES: usize = 4096;
55
56/// Larger input is left alone (bounded runtime; the archive keeps 10 MB).
57pub const MAX_INPUT_BYTES: usize = 8 * 1024 * 1024;
58
59/// Longer lines are never grouped (bounded per-line work, rarely a log line).
60const MAX_TEMPLATE_LINE_BYTES: usize = 4096;
61
62/// At most this many indented lines after a severity line are protected.
63const MAX_CONTINUATION: usize = 64;
64
65/// Digits after `<letter>-` or `<letter>_` up to this length name a member
66/// of a small set (`worker-2`) and stay literal.
67pub const MAX_NAME_SUFFIX_DIGITS: usize = 2;
68
69/// Shortest hex word (with a digit) treated as an id.
70pub const MIN_HEX_ID: usize = 6;
71
72/// Placeholder byte for a variable field inside a template key.
73const HOLE: u8 = 0x01;
74
75/// The collapse result: the rendered body and its counts.
76#[derive(Debug, Clone, PartialEq, Eq)]
77pub struct TemplateCollapsed {
78    pub body: String,
79    pub lines_before: usize,
80    pub lines_after: usize,
81    /// Number of `[N× like]` group lines.
82    pub groups: usize,
83    /// Lines folded into a group line (its first line included).
84    pub grouped_lines: usize,
85}
86
87#[derive(Debug, Clone, Copy, PartialEq, Eq)]
88enum Class {
89    Plain,
90    Severity,
91    Protected,
92}
93
94fn severity_re() -> &'static regex::Regex {
95    static RE: std::sync::OnceLock<regex::Regex> = std::sync::OnceLock::new();
96    RE.get_or_init(|| {
97        regex::Regex::new(concat!(
98            r"(?i:\b(errors?|critical|fatal|panic(ked|king|s)?|exceptions?|fail(ed|ure|ures|ing|s)?",
99            r"|warn(ing|ings)?|traceback|segfault|abort(ed)?|denied|assert(ion|ions|ed)?)\b)",
100            r"|[a-z](Error|Exception)\b",
101        ))
102        .expect("BUG: invalid template_collapse severity regex")
103    })
104}
105
106fn test_runner_re() -> &'static regex::Regex {
107    static RE: std::sync::OnceLock<regex::Regex> = std::sync::OnceLock::new();
108    RE.get_or_init(|| {
109        regex::Regex::new(concat!(
110            r"(?i:\btest result:|\brunning \d+ tests?\b|\b\d+ (passed|skipped|tests?)\b)",
111            r"|^(PASS|FAIL|ok|not ok|OK|FAILED)\b",
112        ))
113        .expect("BUG: invalid template_collapse test-runner regex")
114    })
115}
116
117fn is_diff_line(line: &str) -> bool {
118    line.starts_with("diff --git ") || (line.starts_with("@@ -") && line[4..].contains(" @@"))
119}
120
121fn is_indented(line: &str) -> bool {
122    line.starts_with([' ', '\t']) && !line.trim().is_empty()
123}
124
125/// A JSON record (owner decision 2026-10-31): its numbers are data, so an
126/// export stays countable. Every line opening with `{` counts; one opening
127/// with `[` only when it parses as JSON, so bracketed log prefixes such as
128/// `[2026-03-14 10:00:00] INFO …` still group.
129fn is_data_record(line: &str) -> bool {
130    let t = line.trim();
131    t.starts_with('{')
132        || (t.starts_with('[')
133            && t.ends_with(']')
134            && serde_json::from_str::<serde::de::IgnoredAny>(t).is_ok())
135}
136
137/// Per-line class. Severity lines become protected when they all fit in the
138/// verbatim budget.
139fn classify(lines: &[&str]) -> Vec<Class> {
140    let mut class = vec![Class::Plain; lines.len()];
141    let mut i = 0;
142    while i < lines.len() {
143        let line = lines[i];
144        if line.contains("Traceback (most recent call last)") {
145            class[i] = Class::Protected;
146            let mut j = i + 1;
147            while j < lines.len() && (is_indented(lines[j]) || lines[j].trim().is_empty()) {
148                class[j] = Class::Protected;
149                j += 1;
150            }
151            if j < lines.len() {
152                // The exception line closing the block.
153                class[j] = Class::Protected;
154                j += 1;
155            }
156            i = j;
157            continue;
158        }
159        if test_runner_re().is_match(line) {
160            class[i] = Class::Protected;
161        } else if severity_re().is_match(line) {
162            class[i] = Class::Severity;
163            let mut j = i + 1;
164            while j < lines.len() && j - i <= MAX_CONTINUATION && is_indented(lines[j]) {
165                class[j] = Class::Protected;
166                j += 1;
167            }
168            i = j;
169            continue;
170        }
171        i += 1;
172    }
173    let severity_bytes: usize = lines
174        .iter()
175        .zip(&class)
176        .filter(|(_, c)| **c == Class::Severity)
177        .map(|(l, _)| l.len() + 1)
178        .sum();
179    if severity_bytes <= SEVERITY_VERBATIM_BYTES {
180        for c in &mut class {
181            if *c == Class::Severity {
182                *c = Class::Protected;
183            }
184        }
185    }
186    class
187}
188
189fn is_uuid_at(b: &[u8]) -> bool {
190    const SHAPE: [usize; 5] = [8, 4, 4, 4, 12];
191    let mut pos = 0;
192    for (k, len) in SHAPE.iter().enumerate() {
193        if k > 0 {
194            if b.get(pos) != Some(&b'-') {
195                return false;
196            }
197            pos += 1;
198        }
199        let Some(part) = b.get(pos..pos + len) else {
200            return false;
201        };
202        if !part.iter().all(u8::is_ascii_hexdigit) {
203            return false;
204        }
205        pos += len;
206    }
207    !b.get(pos).is_some_and(u8::is_ascii_alphanumeric)
208}
209
210/// Whether the alphanumeric `word`, starting at `start` of `line`, is a
211/// variable field (see the module docs).
212fn is_variable(line: &[u8], start: usize, word: &[u8]) -> bool {
213    let digits = word.iter().filter(|b| b.is_ascii_digit()).count();
214    if digits == 0 {
215        return false;
216    }
217    if digits == word.len() {
218        let name_suffix = start >= 2
219            && matches!(line[start - 1], b'-' | b'_')
220            && line[start - 2].is_ascii_alphabetic();
221        return !(name_suffix && word.len() <= MAX_NAME_SUFFIX_DIGITS);
222    }
223    if word[0].is_ascii_digit() && word.len() - digits <= 3 {
224        return true;
225    }
226    word.len() >= MIN_HEX_ID && word.iter().all(u8::is_ascii_hexdigit)
227}
228
229/// The template key of `line` and the byte spans of its variable fields.
230fn template(line: &str) -> (Vec<u8>, Vec<(usize, usize)>) {
231    let b = line.as_bytes();
232    let mut key = Vec::with_capacity(b.len());
233    let mut spans = Vec::new();
234    let mut i = 0;
235    while i < b.len() {
236        if !b[i].is_ascii_alphanumeric() {
237            key.push(b[i]);
238            i += 1;
239            continue;
240        }
241        let start = i;
242        let word_start_ok = start == 0 || !b[start - 1].is_ascii_alphanumeric();
243        if word_start_ok && is_uuid_at(&b[start..]) {
244            i = start + 36;
245            key.push(HOLE);
246            spans.push((start, i));
247            continue;
248        }
249        while i < b.len() && b[i].is_ascii_alphanumeric() {
250            i += 1;
251        }
252        if is_variable(b, start, &b[start..i]) {
253            key.push(HOLE);
254            spans.push((start, i));
255        } else {
256            key.extend_from_slice(&b[start..i]);
257        }
258    }
259    (key, spans)
260}
261
262struct Group {
263    first: usize,
264    last: usize,
265    count: usize,
266}
267
268/// Collapse lines that differ only in variable fields. `None` when nothing
269/// collapses, the input is too large, or it carries a diff.
270#[must_use]
271pub fn collapse(input: &str) -> Option<TemplateCollapsed> {
272    if input.len() > MAX_INPUT_BYTES {
273        return None;
274    }
275    let lines: Vec<&str> = input.split('\n').collect();
276    if lines.iter().any(|l| is_diff_line(l)) {
277        return None;
278    }
279    let class = classify(&lines);
280    let mut index: HashMap<(bool, Vec<u8>), usize> = HashMap::new();
281    let mut groups: Vec<Group> = Vec::new();
282    let mut spans: Vec<Vec<(usize, usize)>> = vec![Vec::new(); lines.len()];
283    let mut member: Vec<Option<usize>> = vec![None; lines.len()];
284    for (i, line) in lines.iter().enumerate() {
285        if class[i] == Class::Protected
286            || line.trim().is_empty()
287            || line.len() > MAX_TEMPLATE_LINE_BYTES
288            || is_data_record(line)
289        {
290            continue;
291        }
292        let (key, line_spans) = template(line);
293        if line_spans.is_empty() {
294            // Without a variable field only identical lines share the
295            // template: that is R2's job, and a text line stays verbatim.
296            continue;
297        }
298        spans[i] = line_spans;
299        let next = groups.len();
300        let g = *index
301            .entry((class[i] == Class::Severity, key))
302            .or_insert(next);
303        if g == next {
304            groups.push(Group {
305                first: i,
306                last: i,
307                count: 0,
308            });
309        }
310        groups[g].last = i;
311        groups[g].count += 1;
312        member[i] = Some(g);
313    }
314    let mut out: Vec<String> = Vec::with_capacity(lines.len());
315    let (mut group_lines, mut grouped) = (0usize, 0usize);
316    for (i, line) in lines.iter().enumerate() {
317        match member[i].map(|g| &groups[g]) {
318            Some(g) if g.count >= MIN_GROUP => {
319                if g.first == i {
320                    out.push(group_line(&lines, &spans, g));
321                    group_lines += 1;
322                    grouped += g.count;
323                }
324            }
325            _ => out.push((*line).to_string()),
326        }
327    }
328    if group_lines == 0 {
329        return None;
330    }
331    Some(TemplateCollapsed {
332        body: out.join("\n"),
333        lines_before: lines.len(),
334        lines_after: out.len(),
335        groups: group_lines,
336        grouped_lines: grouped,
337    })
338}
339
340/// `[N× like] <first> … last: <changed span of the last line>`.
341fn group_line(lines: &[&str], spans: &[Vec<(usize, usize)>], g: &Group) -> String {
342    fn field(line: &str, s: (usize, usize)) -> &str {
343        &line[s.0..s.1]
344    }
345    let (first, last) = (lines[g.first], lines[g.last]);
346    let (fs, ls) = (&spans[g.first], &spans[g.last]);
347    let changed: Vec<usize> = (0..fs.len().min(ls.len()))
348        .filter(|&k| field(first, fs[k]) != field(last, ls[k]))
349        .collect();
350    match (changed.first(), changed.last()) {
351        (Some(&a), Some(&z)) => format!(
352            "[{}× like] {first} … last: {}",
353            g.count,
354            &last[ls[a].0..ls[z].1]
355        ),
356        _ => format!("[{}× identical] {first}", g.count),
357    }
358}
359
360/// The text a reader gets: one header naming the archived original, then
361/// the body. `recovery` is the caller's pointer to the full output.
362#[must_use]
363pub fn render(c: &TemplateCollapsed, recovery: &str) -> String {
364    format!(
365        "[lean-ctx: {} lines shown as {}; {} lines that differ only in numbers, ids or timestamps \
366         are grouped as \"[N× like] first … last: …\"; every distinct error message is kept; {recovery}]\n{}",
367        c.lines_before, c.lines_after, c.grouped_lines, c.body
368    )
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374
375    fn heartbeat_log(n: usize) -> String {
376        (0..n).fold(String::new(), |mut s, i| {
377            let ms = i * 997;
378            s.push_str(&format!(
379                "2026-03-14T10:{:02}:{:02}.{:03}Z INFO heartbeat ok worker-2 seq={i}\n",
380                (ms / 60_000) % 60,
381                (ms / 1000) % 60,
382                ms % 1000
383            ));
384            s
385        })
386    }
387
388    #[test]
389    fn variable_field_table() {
390        // (line, template with HOLE shown as '#')
391        let cases = [
392            (
393                "2026-03-14T10:00:00.001Z INFO heartbeat ok worker-2 seq=0",
394                "#-#-#:#:#.# INFO heartbeat ok worker-2 seq=#",
395            ),
396            ("delivery dlv-fc56b260 took 750ms", "delivery dlv-# took #"),
397            (
398                "batch b-006992 delivered 487/500",
399                "batch b-# delivered #/#",
400            ),
401            ("from 10.0.12.7:8443", "from #.#.#.#:#"),
402            ("id 550e8400-e29b-41d4-a716-446655440000 ok", "id # ok"),
403            (
404                "relayd/schema.py:47:101: W501 line too long (128 > 100)",
405                "relayd/schema.py:#:#: W501 line too long (# > #)",
406            ),
407            ("shard_7 v2 E201 cafe", "shard_7 v2 E201 cafe"),
408        ];
409        for (line, want) in cases {
410            let (key, _) = template(line);
411            let shown: String = key
412                .iter()
413                .map(|&b| if b == HOLE { '#' } else { b as char })
414                .collect();
415            assert_eq!(shown, want, "{line}");
416        }
417    }
418
419    #[test]
420    fn heartbeat_log_collapses_by_at_least_eighty_percent() {
421        let log = heartbeat_log(1500);
422        let c = collapse(&log).expect("collapses");
423        assert!(
424            c.body.len() * 5 <= log.len(),
425            "{} vs {}",
426            c.body.len(),
427            log.len()
428        );
429        assert!(c.body.starts_with(
430            "[1500× like] 2026-03-14T10:00:00.000Z INFO heartbeat ok worker-2 seq=0 … last: "
431        ));
432        assert!(
433            c.body.contains("seq=1499"),
434            "last instance named: {}",
435            c.body
436        );
437        assert_eq!((c.groups, c.grouped_lines), (1, 1500));
438    }
439
440    #[test]
441    fn rare_error_among_thousands_of_retries_stays_verbatim() {
442        let mut log = String::new();
443        let rare = "2026-03-14T03:12:09.114Z ERROR worker-2 batch b-006992 stopped: ValueError: invalid duration '5x' in parse_duration";
444        for i in 0..3000 {
445            if i == 1777 {
446                log.push_str(rare);
447                log.push('\n');
448            }
449            log.push_str(&format!(
450                "2026-03-14T03:{:02}:{:02}.{:03}Z WARN worker-1 delivery dlv-{:08x} to https://a.example/x failed: 503 Service Unavailable (attempt {}/5, retrying in 500ms)\n",
451                (i / 60) % 60, i % 60, i % 1000, i * 7919 + 0x1000_0000, i % 5 + 1
452            ));
453        }
454        let c = collapse(&log).expect("collapses");
455        assert!(c.body.lines().any(|l| l == rare), "rare error verbatim");
456        assert!(c.body.len() * 10 < log.len());
457        // The retries are one severity message, kept once with its count.
458        assert!(c.body.contains("[3000× like] "));
459    }
460
461    #[test]
462    fn small_severity_sets_stay_verbatim_and_never_mix_with_plain_lines() {
463        let mut log = heartbeat_log(200);
464        for i in 0..20 {
465            log.push_str(&format!(
466                "2026-03-14T11:00:{i:02}.000Z ERROR worker-3 timeout after {i}s\n"
467            ));
468        }
469        let c = collapse(&log).unwrap();
470        for i in 0..20 {
471            let line = format!("2026-03-14T11:00:{i:02}.000Z ERROR worker-3 timeout after {i}s");
472            assert!(c.body.lines().any(|l| l == line), "{line}");
473        }
474    }
475
476    #[test]
477    fn tracebacks_test_output_and_diffs_stay_untouched() {
478        let mut log = heartbeat_log(100);
479        let tb = "Traceback (most recent call last):\n  File \"relayd/worker.py\", line 88, in run\n    d = parse_duration(v)\n  File \"relayd/config.py\", line 12, in parse_duration\n    raise ValueError(v)\nValueError: 5x";
480        let tb_lines: Vec<String> = tb.lines().map(str::to_owned).collect();
481        for _ in 0..10 {
482            log.push_str(tb);
483            log.push('\n');
484        }
485        for i in 0..12 {
486            log.push_str(&format!("ok {i} - case_{i}\n"));
487        }
488        log.push_str("Ran 12 tests in 0.004s\n");
489        let c = collapse(&log).unwrap();
490        for l in &tb_lines {
491            assert_eq!(c.body.lines().filter(|b| b == l).count(), 10, "{l}");
492        }
493        assert_eq!(c.body.lines().filter(|l| l.starts_with("ok ")).count(), 12);
494        assert!(c.body.contains("Ran 12 tests in 0.004s"));
495
496        let diff = format!(
497            "{}diff --git a/x b/x\n@@ -1,2 +1,2 @@\n",
498            heartbeat_log(100)
499        );
500        assert!(collapse(&diff).is_none(), "diffs are refused whole");
501    }
502
503    #[test]
504    fn output_is_deterministic_and_order_preserving() {
505        let mut log = String::from("start\n");
506        log.push_str(&heartbeat_log(40));
507        log.push_str("middle marker\n");
508        log.push_str(&heartbeat_log(40));
509        log.push_str("end\n");
510        let a = collapse(&log).unwrap();
511        assert_eq!(a, collapse(&log).unwrap());
512        let body: Vec<&str> = a.body.lines().collect();
513        assert_eq!(body[0], "start");
514        assert!(body[1].starts_with("[80× like] "));
515        assert_eq!(&body[2..], &["middle marker", "end"]);
516        assert_eq!(render(&a, "full: X"), render(&a, "full: X"));
517    }
518
519    #[test]
520    fn nothing_to_group_returns_none() {
521        assert!(collapse("a\nb\nc").is_none());
522        assert!(collapse(&heartbeat_log(MIN_GROUP - 1)).is_none());
523        assert!(
524            collapse(&"plain text line\n".repeat(50)).is_none(),
525            "identical text is R2's"
526        );
527        // JSON records are data: never grouped. A bracketed log prefix is not.
528        let records = |open: &str, close: &str| {
529            (0..50).fold(String::new(), |mut s, i| {
530                s.push_str(&format!(
531                    "{open}\"id\":{i},\"status\":{}{close}\n",
532                    200 + i % 3
533                ));
534                s
535            })
536        };
537        assert!(collapse(&records("{", "}")).is_none());
538        assert!(collapse(&records("[{", "}]")).is_none());
539        let bracketed = (0..50).fold(String::new(), |mut s, i| {
540            s.push_str(&format!(
541                "[2026-03-14 10:00:{:02}] INFO heartbeat seq={i}\n",
542                i % 60
543            ));
544            s
545        });
546        assert!(collapse(&bracketed).is_some());
547    }
548}
lean_ctx_patterns/template_collapse.rs

lean_ctx_patterns/
template_collapse.rs
