use std::collections::HashMap;
use std::io;
use serde::Serialize;
use crate::blocks::{gone_blocks, Block, Extent, NewRuns, ProtoBlock};
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::{count_g_test, score_template, DEFAULT_SIGNIFICANCE};
use crate::values::ValueTracker;
#[derive(Serialize)]
pub struct RunSummary {
pub total_lines: u64,
pub clusters: Vec<Cluster>,
}
pub fn mine_run(path: &str, custom: &[CustomMask], threshold: f64) -> io::Result<RunSummary> {
mine_lines(read_lines(path)?, custom, threshold)
}
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,
pub first_target_line_no: Option<usize>,
pub first_target_raw: Option<String>,
#[serde(skip_serializing_if = "Option::is_none")]
pub first_baseline_line_no: Option<usize>,
#[serde(skip_serializing_if = "Option::is_none")]
pub first_baseline_raw: Option<String>,
#[serde(skip_serializing_if = "Option::is_none")]
pub block: Option<usize>,
#[serde(skip_serializing_if = "Option::is_none")]
pub context: Option<ContextWindow>,
}
#[derive(Serialize)]
pub struct ValueFinding {
pub template: String,
pub position: usize,
pub new_value: String,
pub baseline_values: Vec<String>,
pub first_target_line_no: usize,
pub first_target_raw: String,
pub established: f64,
#[serde(skip_serializing_if = "Option::is_none")]
pub block: Option<usize>,
#[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,
pub total_templates: usize,
pub findings: Vec<Finding>,
pub blocks: Vec<Block>,
pub value_findings: Vec<ValueFinding>,
}
impl DiffResult {
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();
}
}
pub fn wanted_line_numbers(&self) -> std::collections::BTreeSet<usize> {
self.findings
.iter()
.filter(|f| f.block.is_none())
.filter_map(|f| f.first_target_line_no)
.chain(self.ungrouped_values().map(|v| v.first_target_line_no))
.collect()
}
pub fn ungrouped_findings(&self) -> impl Iterator<Item = &Finding> {
self.findings.iter().filter(|f| f.block.is_none())
}
pub fn ungrouped_values(&self) -> impl Iterator<Item = &ValueFinding> {
self.value_findings.iter().filter(|v| v.block.is_none())
}
pub fn report_count(&self) -> usize {
self.blocks.len() + self.ungrouped_findings().count() + self.ungrouped_values().count()
}
pub fn finding_count(&self) -> usize {
self.findings.len() + self.value_findings.len()
}
}
pub struct DiffOptions {
pub threshold: f64,
pub significance: f64,
pub group: bool,
}
impl Default for DiffOptions {
fn default() -> Self {
DiffOptions {
threshold: DEFAULT_SIMILARITY_THRESHOLD,
significance: DEFAULT_SIGNIFICANCE,
group: true,
}
}
}
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)
}
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 group = opts.group && n_baselines > 0;
let mut baseline_counts: Vec<HashMap<usize, u64>> = Vec::with_capacity(n_baselines);
let mut baseline_totals: Vec<u64> = Vec::with_capacity(n_baselines);
let mut first_baseline_last: HashMap<usize, usize> = HashMap::new();
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_token_slice(&tokens, total as usize, &line);
tracker.record_baseline(baseline_idx, cid, total as usize, &line, &tokens);
*counts.entry(cid).or_insert(0) += 1;
if group && baseline_idx == 0 {
first_baseline_last.insert(cid, total as usize);
}
}
baseline_counts.push(counts);
baseline_totals.push(total);
}
let baseline_clusters = drain.clusters().len();
let mut new_runs = NewRuns::default();
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_token_slice(&tokens, target_total as usize, &line);
tracker.record_target(cid, target_total as usize, &line, &tokens);
*target_counts.entry(cid).or_insert(0) += 1;
let first_of_cluster = !target_first.contains_key(&cid);
if first_of_cluster {
target_first.insert(cid, (target_total as usize, line.clone()));
}
if group {
let is_new = cid >= baseline_clusters;
new_runs.line(target_total as usize, cid, is_new, first_of_cluster);
}
}
let total_templates = drain.clusters().len();
let mut findings: Vec<(usize, Finding)> = 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);
let score = score_template(&bc, &baseline_totals, tc, target_total);
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 share_direction = if target_rate > baseline_rate {
Direction::Up
} else if target_rate < baseline_rate {
Direction::Down
} else {
Direction::Flat
};
let count_direction = match (tc * n_baselines as u64).cmp(&baseline_sum) {
std::cmp::Ordering::Greater => Direction::Up,
std::cmp::Ordering::Less => Direction::Down,
std::cmp::Ordering::Equal => Direction::Flat,
};
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
&& count_g_test(&bc, tc) >= opts.significance
&& share_direction == count_direction
{
Some(FindingKind::Changed)
} else {
None
}
} else {
Some(FindingKind::New)
};
let Some(kind) = kind else { continue };
let direction = match kind {
FindingKind::New => Direction::Up,
FindingKind::Gone => Direction::Down,
FindingKind::Changed => share_direction,
};
let (line_no, raw) = target_first
.get(&id)
.map(|(n, r)| (Some(*n), Some(r.clone())))
.unwrap_or((None, None));
let (baseline_line_no, baseline_raw) = if kind == FindingKind::Gone {
(
Some(cluster.first_line_no),
Some(cluster.first_line_raw.clone()),
)
} else {
(None, None)
};
findings.push((
id,
Finding {
kind,
direction,
template: cluster.template(),
score,
baseline_counts: bc,
target_count: tc,
first_target_line_no: line_no,
first_target_raw: raw,
first_baseline_line_no: baseline_line_no,
first_baseline_raw: baseline_raw,
block: None,
context: None,
},
));
}
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,
block: None,
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),
)
});
let (cluster_ids, mut findings): (Vec<usize>, Vec<Finding>) = findings.into_iter().unzip();
let mut blocks = Vec::new();
if group {
let index_of: HashMap<usize, usize> = cluster_ids
.iter()
.enumerate()
.map(|(index, cid)| (*cid, index))
.collect();
let gone = findings
.iter()
.zip(&cluster_ids)
.filter(|(f, _)| f.kind == FindingKind::Gone)
.filter_map(|(f, cid)| {
Some(Extent {
cid: *cid,
first: f.first_baseline_line_no?,
last: *first_baseline_last.get(cid)?,
count: f.baseline_counts.first().copied()?,
})
})
.collect();
let found = [
(FindingKind::New, new_runs.finish(&target_counts)),
(FindingKind::Gone, gone_blocks(gone)),
];
for (kind, protos) in found {
for proto in protos {
if let Some(block) = build_block(kind, &proto, &index_of, &findings) {
blocks.push(block);
}
}
}
blocks.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),
)
.then(a.first_line_no.cmp(&b.first_line_no))
});
for (index, block) in blocks.iter().enumerate() {
for &member in &block.findings {
findings[member].block = Some(index);
}
}
}
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))
});
for v in &mut value_findings {
v.block = blocks.iter().position(|b| {
b.kind == FindingKind::New
&& (b.first_line_no..=b.last_line_no).contains(&v.first_target_line_no)
});
}
Ok(DiffResult {
baseline_totals,
target_total,
total_templates,
findings,
blocks,
value_findings,
})
}
fn build_block(
kind: FindingKind,
proto: &ProtoBlock,
index_of: &HashMap<usize, usize>,
findings: &[Finding],
) -> Option<Block> {
let line_no = |f: &Finding| match kind {
FindingKind::Gone => f.first_baseline_line_no,
_ => f.first_target_line_no,
};
let mut members: Vec<usize> = proto
.members
.iter()
.filter_map(|cid| index_of.get(cid).copied())
.filter(|&index| findings[index].kind == kind)
.collect();
if members.len() < crate::blocks::MIN_BLOCK_TEMPLATES {
return None;
}
members.sort_by_key(|&index| line_no(&findings[index]));
let lines = |f: &Finding| match kind {
FindingKind::Gone => f.baseline_counts.first().copied().unwrap_or(0),
_ => f.target_count,
};
Some(Block {
kind,
first_line_no: proto.first,
last_line_no: proto.last,
line_count: members.iter().map(|&index| lines(&findings[index])).sum(),
lines_elsewhere: proto.lines_elsewhere,
score: members.iter().map(|&index| findings[index].score).sum(),
findings: members,
})
}
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() {
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")));
}
fn lines_of(parts: &[(&str, usize)]) -> Vec<String> {
parts
.iter()
.flat_map(|(line, times)| std::iter::repeat_n(line.to_string(), *times))
.collect()
}
fn changed(baselines: &[Vec<String>], target: &[String]) -> Vec<String> {
let sources: Vec<_> = baselines
.iter()
.map(|b| b.iter().cloned().map(Ok))
.collect();
let result = diff_lines(
sources,
target.iter().cloned().map(Ok),
&[],
&DiffOptions::default(),
)
.unwrap();
result
.findings
.iter()
.filter(|f| f.kind == FindingKind::Changed)
.map(|f| f.template.clone())
.collect()
}
#[test]
fn a_run_that_stops_early_does_not_change_the_lines_it_did_print() {
let good = lines_of(&[("fetched branch ok", 250), ("step finished fine", 1000)]);
let bad = lines_of(&[("fetched branch ok", 250), ("step finished fine", 100)]);
let found = changed(&[good.clone(), good.clone(), good], &bad);
assert_eq!(found, vec!["step finished fine".to_string()]);
}
#[test]
fn a_bigger_run_with_the_same_mix_changes_nothing() {
let good = lines_of(&[("request served", 300), ("cache hit", 100), ("retry", 20)]);
let bad = lines_of(&[("request served", 900), ("cache hit", 300), ("retry", 60)]);
assert_eq!(changed(&[good.clone(), good], &bad), Vec::<String>::new());
}
#[test]
fn a_line_printed_far_more_often_in_a_run_of_the_same_size_is_changed() {
let good = lines_of(&[("request served", 400), ("retry", 3)]);
let bad = lines_of(&[("request served", 363), ("retry", 40)]);
assert_eq!(
changed(&[good.clone(), good.clone(), good], &bad),
vec!["retry".to_string()]
);
}
#[test]
fn detects_a_content_flip_frequency_scoring_alone_would_miss() {
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");
}
}