logdelta 0.2.2

Diff logs by meaning, not by bytes. See what's new in the failing run.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
//! High-level operations built on top of [`crate::mask`], [`crate::drain`] and
//! [`crate::scoring`]: mining a single run's templates, and diffing one or more baseline
//! runs against a target run.

use std::collections::HashMap;
use std::io;

use serde::Serialize;

use crate::context::ContextWindow;
use crate::drain::{Cluster, Drain, DEFAULT_SIMILARITY_THRESHOLD};
use crate::io::read_lines;
use crate::mask::{tokenize_line, CustomMask};
use crate::scoring::{score_template, DEFAULT_SIGNIFICANCE};
use crate::values::ValueTracker;

/// The result of mining a single log source.
#[derive(Serialize)]
pub struct RunSummary {
    pub total_lines: u64,
    pub clusters: Vec<Cluster>,
}

/// Masks and mines every line of `path` on its own, independent [`Drain`] instance. Used by
/// `logdelta templates`.
pub fn mine_run(path: &str, custom: &[CustomMask], threshold: f64) -> io::Result<RunSummary> {
    mine_lines(read_lines(path)?, custom, threshold)
}

/// [`mine_run`] over any source of lines (a file, stdin, or text already in memory).
pub fn mine_lines<I>(lines: I, custom: &[CustomMask], threshold: f64) -> io::Result<RunSummary>
where
    I: Iterator<Item = io::Result<String>>,
{
    let mut drain = Drain::new(threshold);
    let mut total = 0u64;
    for line in lines {
        let line = line?;
        total += 1;
        let tokens = tokenize_line(&line, custom);
        drain.add_tokens(tokens, total as usize, &line);
    }
    Ok(RunSummary {
        total_lines: total,
        clusters: drain.into_clusters(),
    })
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum FindingKind {
    New,
    Gone,
    Changed,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
#[serde(rename_all = "lowercase")]
pub enum Direction {
    Up,
    Down,
    Flat,
}

#[derive(Serialize)]
pub struct Finding {
    pub kind: FindingKind,
    pub direction: Direction,
    pub template: String,
    pub score: f64,
    pub baseline_counts: Vec<u64>,
    pub target_count: u64,
    /// 1-based line number of the first line in the target that matched this template.
    pub first_target_line_no: Option<usize>,
    pub first_target_raw: Option<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub context: Option<ContextWindow>,
}

/// A wildcard position within an otherwise-stable template whose target-run value never
/// appeared in any baseline — the "content flip" case frequency-based scoring alone can't
/// see (see [`crate::values`]). Example: a pytest line's status word going from `PASSED` in
/// every baseline to `FAILED` in the target, with the line's frequency and position
/// otherwise unchanged.
#[derive(Serialize)]
pub struct ValueFinding {
    pub template: String,
    /// Index into `template`'s whitespace-separated tokens of the flipped position.
    pub position: usize,
    pub new_value: String,
    /// Distinct values seen across all baselines at this position, sorted.
    pub baseline_values: Vec<String>,
    pub first_target_line_no: usize,
    pub first_target_raw: String,
    /// `baseline occurrences / distinct baseline values` at this position — how established
    /// the baseline side is. Findings are sorted by this, most established first, so the
    /// most-confident content flips (a status seen hundreds of times, now different) lead.
    pub established: f64,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub context: Option<ContextWindow>,
}

#[derive(Serialize)]
pub struct DiffResult {
    pub baseline_totals: Vec<u64>,
    pub target_total: u64,
    /// Total distinct templates found across baselines and target combined (not just the
    /// ones with a finding) — the "412 templates" in a summary like "3,012 → 3,104 lines ·
    /// 412 templates · 4 findings".
    pub total_templates: usize,
    pub findings: Vec<Finding>,
    pub value_findings: Vec<ValueFinding>,
}

impl DiffResult {
    /// Attaches `-C` context windows (keyed by first-target-line-number) to each finding.
    pub fn attach_context(&mut self, ctx: &HashMap<usize, ContextWindow>) {
        for f in &mut self.findings {
            if let Some(no) = f.first_target_line_no {
                f.context = ctx.get(&no).cloned();
            }
        }
        for v in &mut self.value_findings {
            v.context = ctx.get(&v.first_target_line_no).cloned();
        }
    }

    /// Every first-target-line-number across all findings, for a single context-collection
    /// pass.
    pub fn wanted_line_numbers(&self) -> std::collections::BTreeSet<usize> {
        self.findings
            .iter()
            .filter_map(|f| f.first_target_line_no)
            .chain(self.value_findings.iter().map(|v| v.first_target_line_no))
            .collect()
    }
}

pub struct DiffOptions {
    pub threshold: f64,
    pub significance: f64,
}

impl Default for DiffOptions {
    fn default() -> Self {
        DiffOptions {
            threshold: DEFAULT_SIMILARITY_THRESHOLD,
            significance: DEFAULT_SIGNIFICANCE,
        }
    }
}

/// Mines `baselines` and `target` into one shared [`Drain`] instance (baselines first, in
/// order, then the target) so that cluster ids and templates are directly comparable across
/// runs, then scores every template's frequency shift.
pub fn diff_runs(
    baselines: &[&str],
    target: &str,
    custom: &[CustomMask],
    opts: &DiffOptions,
) -> io::Result<DiffResult> {
    let baseline_lines = baselines
        .iter()
        .map(|path| read_lines(path))
        .collect::<io::Result<Vec<_>>>()?;
    diff_lines(baseline_lines, read_lines(target)?, custom, opts)
}

/// [`diff_runs`] over any sources of lines: files, stdin, or text already in memory (the
/// browser build diffs pasted logs this way).
pub fn diff_lines<B, T>(
    baselines: Vec<B>,
    target: T,
    custom: &[CustomMask],
    opts: &DiffOptions,
) -> io::Result<DiffResult>
where
    B: Iterator<Item = io::Result<String>>,
    T: Iterator<Item = io::Result<String>>,
{
    let n_baselines = baselines.len();
    let mut drain = Drain::new(opts.threshold);
    let mut tracker = ValueTracker::with_baselines(n_baselines);

    let mut baseline_counts: Vec<HashMap<usize, u64>> = Vec::with_capacity(n_baselines);
    let mut baseline_totals: Vec<u64> = Vec::with_capacity(n_baselines);
    for (baseline_idx, lines) in baselines.into_iter().enumerate() {
        let mut counts: HashMap<usize, u64> = HashMap::new();
        let mut total = 0u64;
        for line in lines {
            let line = line?;
            total += 1;
            let tokens = tokenize_line(&line, custom);
            let cid = drain.add_tokens(tokens.clone(), total as usize, &line);
            tracker.record_baseline(baseline_idx, cid, total as usize, &line, &tokens);
            *counts.entry(cid).or_insert(0) += 1;
        }
        baseline_counts.push(counts);
        baseline_totals.push(total);
    }

    let mut target_counts: HashMap<usize, u64> = HashMap::new();
    let mut target_first: HashMap<usize, (usize, String)> = HashMap::new();
    let mut target_total = 0u64;
    for line in target {
        let line = line?;
        target_total += 1;
        let tokens = tokenize_line(&line, custom);
        let cid = drain.add_tokens(tokens.clone(), target_total as usize, &line);
        tracker.record_target(cid, target_total as usize, &line, &tokens);
        *target_counts.entry(cid).or_insert(0) += 1;
        target_first
            .entry(cid)
            .or_insert((target_total as usize, line.clone()));
    }

    let total_templates = drain.clusters().len();
    let mut findings = Vec::new();
    let mut value_findings = Vec::new();
    for cluster in drain.clusters() {
        let id = cluster.id;
        let bc: Vec<u64> = baseline_counts
            .iter()
            .map(|m| *m.get(&id).unwrap_or(&0))
            .collect();
        let tc = *target_counts.get(&id).unwrap_or(&0);
        let baseline_sum: u64 = bc.iter().sum();
        let present_in_every_baseline = n_baselines > 0 && bc.iter().all(|&c| c > 0);
        // Computed unconditionally (even for NEW/GONE, which don't need it to be
        // classified) because it's cheap and every finding reports its score either way;
        // simpler than threading an `Option` through and computing it twice.
        let score = score_template(&bc, &baseline_totals, tc, target_total);

        let kind = if tc > 0 && baseline_sum == 0 && n_baselines > 0 {
            Some(FindingKind::New)
        } else if tc == 0 && present_in_every_baseline {
            Some(FindingKind::Gone)
        } else if n_baselines > 0 {
            if score >= opts.significance {
                Some(FindingKind::Changed)
            } else {
                None
            }
        } else {
            // No baseline given at all: everything is trivially "new" to the report.
            Some(FindingKind::New)
        };

        let Some(kind) = kind else { continue };

        let baseline_rate = if baseline_totals.iter().sum::<u64>() > 0 {
            baseline_sum as f64 / baseline_totals.iter().sum::<u64>() as f64
        } else {
            0.0
        };
        let target_rate = if target_total > 0 {
            tc as f64 / target_total as f64
        } else {
            0.0
        };
        let direction = match kind {
            FindingKind::New => Direction::Up,
            FindingKind::Gone => Direction::Down,
            FindingKind::Changed => {
                if target_rate > baseline_rate {
                    Direction::Up
                } else if target_rate < baseline_rate {
                    Direction::Down
                } else {
                    Direction::Flat
                }
            }
        };

        let (line_no, raw) = target_first
            .get(&id)
            .map(|(n, r)| (Some(*n), Some(r.clone())))
            .unwrap_or((None, None));

        findings.push(Finding {
            kind,
            direction,
            template: cluster.template(),
            score,
            baseline_counts: bc,
            target_count: tc,
            first_target_line_no: line_no,
            first_target_raw: raw,
            context: None,
        });
    }

    // NEW VALUE: a wildcard position in a template that's otherwise present in both baseline
    // and target (so NEW/GONE, which are about the *template's* presence, already explain
    // those cases) whose target-run value never appeared in any baseline. Independent of the
    // frequency-based findings above: the whole point is to catch a content flip that a
    // count-based test can't see because the count didn't change.
    if n_baselines > 0 {
        for cluster in drain.clusters() {
            let id = cluster.id;
            let baseline_present = baseline_counts
                .iter()
                .any(|m| m.get(&id).copied().unwrap_or(0) > 0);
            let target_present = target_counts.get(&id).copied().unwrap_or(0) > 0;
            if !baseline_present || !target_present {
                continue;
            }
            for (pos, tok) in cluster.tokens.iter().enumerate() {
                if tok != "<*>" {
                    continue;
                }
                if let Some(found) = tracker.new_value_at(id, pos) {
                    value_findings.push(ValueFinding {
                        template: cluster.template(),
                        position: pos,
                        new_value: found.value,
                        baseline_values: found.baseline_values,
                        first_target_line_no: found.first_target_line_no,
                        first_target_raw: found.first_target_raw,
                        established: found.established,
                        context: None,
                    });
                }
            }
        }
    }

    findings.sort_by(|a, b| {
        kind_rank(a.kind).cmp(&kind_rank(b.kind)).then(
            b.score
                .partial_cmp(&a.score)
                .unwrap_or(std::cmp::Ordering::Equal),
        )
    });
    // Most-established baseline value first: a status seen hundreds of times that just
    // changed is a stronger signal than one that barely cleared the repetition bar.
    value_findings.sort_by(|a, b| {
        b.established
            .partial_cmp(&a.established)
            .unwrap_or(std::cmp::Ordering::Equal)
            .then(a.template.cmp(&b.template))
            .then(a.position.cmp(&b.position))
    });

    Ok(DiffResult {
        baseline_totals,
        target_total,
        total_templates,
        findings,
        value_findings,
    })
}

fn kind_rank(k: FindingKind) -> u8 {
    match k {
        FindingKind::New => 0,
        FindingKind::Gone => 1,
        FindingKind::Changed => 2,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::io::Write;

    fn write_tmp(lines: &[&str]) -> tempfile::NamedTempFile {
        let mut f = tempfile::NamedTempFile::new().unwrap();
        for l in lines {
            writeln!(f, "{l}").unwrap();
        }
        f.flush().unwrap();
        f
    }

    #[test]
    fn diffing_text_in_memory_matches_diffing_the_same_files() {
        const GOOD: [&str; 3] = [
            "2024-01-01T00:00:00Z start",
            "2024-01-01T00:00:01Z ok 12ms",
            "2024-01-01T00:00:02Z ok 7ms",
        ];
        const BAD: [&str; 3] = [
            "2024-01-01T00:00:00Z start",
            "2024-01-01T00:00:01Z ok 9ms",
            "2024-01-01T00:00:02Z FATAL: out of memory",
        ];
        let (good, bad) = (&GOOD, &BAD);
        let (gf, bf) = (write_tmp(good), write_tmp(bad));
        let opts = DiffOptions::default();
        let from_files = diff_runs(
            &[gf.path().to_str().unwrap()],
            bf.path().to_str().unwrap(),
            &[],
            &opts,
        )
        .unwrap();
        let lines = |ls: &'static [&'static str]| ls.iter().map(|l| Ok(l.to_string()));
        let in_memory = diff_lines(vec![lines(good)], lines(bad), &[], &opts).unwrap();
        assert_eq!(
            serde_json::to_value(&from_files).unwrap(),
            serde_json::to_value(&in_memory).unwrap()
        );
        assert_eq!(in_memory.findings.len(), from_files.findings.len());
    }

    #[test]
    fn detects_new_template() {
        let good = write_tmp(&["2024-01-01T00:00:00Z start", "2024-01-01T00:00:01Z ok"]);
        let bad = write_tmp(&[
            "2024-01-01T00:00:00Z start",
            "2024-01-01T00:00:01Z ok",
            "2024-01-01T00:00:02Z FATAL: out of memory",
        ]);
        let result = diff_runs(
            &[good.path().to_str().unwrap()],
            bad.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        assert!(result
            .findings
            .iter()
            .any(|f| f.kind == FindingKind::New && f.template.contains("FATAL")));
    }

    #[test]
    fn detects_gone_template() {
        let good = write_tmp(&["<TS> start", "<TS> shutdown clean"]);
        let bad = write_tmp(&["<TS> start"]);
        let result = diff_runs(
            &[good.path().to_str().unwrap()],
            bad.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        assert!(result
            .findings
            .iter()
            .any(|f| f.kind == FindingKind::Gone && f.template.contains("shutdown")));
    }

    #[test]
    fn multiple_baselines_suppress_flaky_template() {
        // "retrying" happens in some passing baselines already, at a noisy rate; the same
        // rate in target should NOT be flagged once multiple baselines establish it's normal.
        let b1 = write_tmp(&["a", "a", "a", "retry attempt"]);
        let b2 = write_tmp(&["a", "a", "a", "a"]);
        let b3 = write_tmp(&["a", "a", "retry attempt", "retry attempt"]);
        let target = write_tmp(&["a", "a", "a", "retry attempt"]);
        let result = diff_runs(
            &[
                b1.path().to_str().unwrap(),
                b2.path().to_str().unwrap(),
                b3.path().to_str().unwrap(),
            ],
            target.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        assert!(!result.findings.iter().any(|f| f.template.contains("retry")));
    }

    #[test]
    fn detects_a_content_flip_frequency_scoring_alone_would_miss() {
        // Same line, same position - only the value at that position changes. A count-based
        // test alone can't see this; it's what ValueFinding (backed by `crate::values`)
        // exists for. The baseline repeats PASSED enough times to clear
        // `values::MIN_AVG_REPETITION`, the way a real test suite run would.
        let good = write_tmp(&["tests/test_math.py::test_divide PASSED [ 57%]"; 6]);
        let bad = write_tmp(&["tests/test_math.py::test_divide FAILED [ 57%]"]);
        let result = diff_runs(
            &[good.path().to_str().unwrap()],
            bad.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        assert!(
            result.value_findings.iter().any(|v| v.new_value == "FAILED"
                && v.baseline_values == vec!["PASSED".to_string()]
                && v.template.contains("test_divide")),
            "expected a NEW VALUE finding for the PASSED->FAILED flip, got: {:?}",
            result
                .value_findings
                .iter()
                .map(|v| (&v.template, &v.new_value))
                .collect::<Vec<_>>()
        );
    }

    #[test]
    fn no_value_findings_without_a_baseline() {
        let target = write_tmp(&["status PASSED"]);
        let result = diff_runs(
            &[],
            target.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        assert!(result.value_findings.is_empty());
    }

    #[test]
    fn first_target_line_is_recorded() {
        let good = write_tmp(&["ok"]);
        let bad = write_tmp(&["ok", "ok", "boom now"]);
        let result = diff_runs(
            &[good.path().to_str().unwrap()],
            bad.path().to_str().unwrap(),
            &[],
            &DiffOptions::default(),
        )
        .unwrap();
        let f = result
            .findings
            .iter()
            .find(|f| f.template.contains("boom"))
            .unwrap();
        assert_eq!(f.first_target_line_no, Some(3));
        assert_eq!(f.first_target_raw.as_deref(), Some("boom now"));
    }

    #[test]
    fn mine_run_counts_templates() {
        let f = write_tmp(&["user alice in", "user bob in", "user carol in", "bye"]);
        let summary = mine_run(
            f.path().to_str().unwrap(),
            &[],
            DEFAULT_SIMILARITY_THRESHOLD,
        )
        .unwrap();
        assert_eq!(summary.total_lines, 4);
        let top = summary.clusters.iter().max_by_key(|c| c.count).unwrap();
        assert_eq!(top.count, 3);
        assert_eq!(top.template(), "user <*> in");
    }
}