use std::collections::HashMap;
use serde::Serialize;
use crate::analysis::FindingKind;
pub const MAX_GAP: usize = 2;
pub const MAX_GONE_GAP: usize = 16;
pub const MIN_GONE_DENSITY: u64 = 3;
pub const MIN_BLOCK_TEMPLATES: usize = 2;
#[derive(Debug, Clone, Serialize)]
pub struct Block {
pub kind: FindingKind,
pub first_line_no: usize,
pub last_line_no: usize,
pub line_count: u64,
pub lines_elsewhere: u64,
pub score: f64,
pub findings: Vec<usize>,
}
#[derive(Debug, PartialEq)]
pub(crate) struct ProtoBlock {
pub first: usize,
pub last: usize,
pub members: Vec<usize>,
pub lines_elsewhere: u64,
}
struct Candidate {
first: usize,
last: usize,
introduced: Vec<(usize, u64)>,
}
#[derive(Default)]
pub(crate) struct NewRuns {
open: bool,
first: usize,
last: usize,
gap: usize,
counts: HashMap<usize, u64>,
introduced: Vec<usize>,
grouped: HashMap<usize, u64>,
candidates: Vec<Candidate>,
}
impl NewRuns {
pub fn line(&mut self, line_no: usize, cid: usize, is_new: bool, first_of_cluster: bool) {
if !is_new {
if self.open {
self.gap += 1;
if self.gap > MAX_GAP {
self.close();
}
}
return;
}
if !self.open {
self.open = true;
self.first = line_no;
}
self.gap = 0;
self.last = line_no;
*self.counts.entry(cid).or_insert(0) += 1;
if first_of_cluster {
self.introduced.push(cid);
}
}
fn close(&mut self) {
if self.counts.len() >= MIN_BLOCK_TEMPLATES {
for (&cid, &lines) in &self.counts {
*self.grouped.entry(cid).or_insert(0) += lines;
}
if self.introduced.len() >= MIN_BLOCK_TEMPLATES {
self.candidates.push(Candidate {
first: self.first,
last: self.last,
introduced: self
.introduced
.iter()
.map(|cid| (*cid, self.counts[cid]))
.collect(),
});
}
}
self.counts.clear();
self.introduced.clear();
self.open = false;
self.gap = 0;
}
pub fn finish(mut self, target_counts: &HashMap<usize, u64>) -> Vec<ProtoBlock> {
if self.open {
self.close();
}
let grouped = &self.grouped;
let total = |cid: &usize| target_counts.get(cid).copied().unwrap_or(0);
self.candidates
.iter()
.filter_map(|run| {
let folded: Vec<&(usize, u64)> = run
.introduced
.iter()
.filter(|(cid, _)| grouped.get(cid).copied().unwrap_or(0) == total(cid))
.collect();
(folded.len() >= MIN_BLOCK_TEMPLATES).then(|| ProtoBlock {
first: run.first,
last: run.last,
members: folded.iter().map(|(cid, _)| *cid).collect(),
lines_elsewhere: folded.iter().map(|(cid, here)| total(cid) - here).sum(),
})
})
.collect()
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Extent {
pub cid: usize,
pub first: usize,
pub last: usize,
pub count: u64,
}
impl Extent {
fn packed(&self) -> bool {
let span = (self.last - self.first + 1) as u64;
self.count.saturating_mul(2) >= span
}
fn covered_to(&self) -> usize {
if self.packed() {
self.last
} else {
self.first
}
}
fn placed_lines(&self) -> u64 {
if self.packed() {
self.count
} else {
1
}
}
}
struct Chain {
from: usize,
to: usize,
first: usize,
covered: usize,
placed: u64,
}
pub(crate) fn gone_blocks(mut extents: Vec<Extent>) -> Vec<ProtoBlock> {
extents.sort_by_key(|e| (e.first, e.cid));
let mut chains: Vec<Chain> = Vec::new();
let mut start = 0;
while start < extents.len() {
let mut chain = Chain {
from: start,
to: start + 1,
first: extents[start].first,
covered: extents[start].covered_to(),
placed: extents[start].placed_lines(),
};
while chain.to < extents.len() && extents[chain.to].first <= chain.covered + MAX_GAP + 1 {
chain.covered = chain.covered.max(extents[chain.to].covered_to());
chain.placed += extents[chain.to].placed_lines();
chain.to += 1;
}
start = chain.to;
chains.push(chain);
while chains.len() >= 2 {
let (a, b) = (&chains[chains.len() - 2], &chains[chains.len() - 1]);
let gap = b.first.saturating_sub(a.covered + 1);
let span = (a.covered.max(b.covered) - a.first + 1) as u64;
if gap > MAX_GONE_GAP || (a.placed + b.placed) * MIN_GONE_DENSITY < span {
break;
}
let b = chains.pop().expect("two chains");
let a = chains.last_mut().expect("two chains");
a.to = b.to;
a.covered = a.covered.max(b.covered);
a.placed += b.placed;
}
}
chains
.iter()
.filter_map(|chain| {
let members: Vec<usize> = extents[chain.from..chain.to]
.iter()
.filter(|e| e.last <= chain.covered)
.map(|e| e.cid)
.collect();
(members.len() >= MIN_BLOCK_TEMPLATES).then_some(ProtoBlock {
first: chain.first,
last: chain.covered,
members,
lines_elsewhere: 0,
})
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
fn blocks_of(lines: &[Option<usize>]) -> Vec<ProtoBlock> {
let mut runs = NewRuns::default();
let mut counts: HashMap<usize, u64> = HashMap::new();
for (i, line) in lines.iter().enumerate() {
match line {
Some(cid) => {
let first = !counts.contains_key(cid);
*counts.entry(*cid).or_insert(0) += 1;
runs.line(i + 1, *cid, true, first);
}
None => runs.line(i + 1, usize::MAX, false, false),
}
}
runs.finish(&counts)
}
fn block(first: usize, last: usize, members: &[usize], lines_elsewhere: u64) -> ProtoBlock {
ProtoBlock {
first,
last,
members: members.to_vec(),
lines_elsewhere,
}
}
#[test]
fn consecutive_new_lines_are_one_block() {
let lines = [None, Some(1), Some(2), Some(3), None, None, None, None];
assert_eq!(blocks_of(&lines), vec![block(2, 4, &[1, 2, 3], 0)]);
}
#[test]
fn a_run_reaches_across_a_couple_of_known_lines_and_no_further() {
let bridged = [Some(1), None, None, Some(2)];
assert_eq!(blocks_of(&bridged), vec![block(1, 4, &[1, 2], 0)]);
let apart = [Some(1), None, None, None, Some(2)];
assert_eq!(blocks_of(&apart), vec![]);
}
#[test]
fn one_new_line_is_not_a_block_however_often_it_repeats() {
assert_eq!(blocks_of(&[Some(1), Some(1), Some(1), Some(1)]), vec![]);
}
#[test]
fn a_repeated_template_inside_a_block_is_counted_once() {
let lines = [Some(1), Some(2), Some(2), Some(2), Some(3)];
assert_eq!(blocks_of(&lines), vec![block(1, 5, &[1, 2, 3], 0)]);
}
#[test]
fn the_same_stack_trace_logged_again_is_still_one_block() {
let mut lines = vec![Some(1), Some(2), Some(3)];
for _ in 0..4 {
lines.extend([None, None, None, None, Some(1), Some(2), Some(3)]);
}
assert_eq!(blocks_of(&lines), vec![block(1, 3, &[1, 2, 3], 12)]);
}
#[test]
fn a_template_that_also_occurs_on_its_own_keeps_its_own_finding() {
let mut lines = vec![Some(1), Some(2), Some(9)];
for _ in 0..5 {
lines.extend([None, None, None, None, Some(9)]);
}
assert_eq!(blocks_of(&lines), vec![block(1, 3, &[1, 2], 0)]);
}
#[test]
fn a_block_needs_two_templates_that_fold() {
let lines = [
Some(1),
Some(2),
None,
None,
None,
Some(1),
None,
None,
None,
Some(2),
];
assert_eq!(blocks_of(&lines), vec![]);
}
#[test]
fn a_second_failure_is_a_second_block_and_shares_the_furniture() {
let lines = [
Some(1),
Some(3),
Some(2),
Some(4),
None,
None,
None,
Some(1),
Some(5),
Some(2),
Some(6),
];
assert_eq!(
blocks_of(&lines),
vec![block(1, 4, &[1, 3, 2, 4], 2), block(8, 11, &[5, 6], 0)]
);
}
#[test]
fn every_template_is_in_at_most_one_block() {
let mut state = 0x2545_f491_4f6c_dd1du64;
for _ in 0..500 {
let mut lines = Vec::new();
for _ in 0..60 {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
lines.push(match state % 9 {
cid @ 0..=5 => Some(cid as usize),
_ => None,
});
}
let blocks = blocks_of(&lines);
let mut seen = std::collections::HashSet::new();
for b in &blocks {
assert!(b.members.len() >= MIN_BLOCK_TEMPLATES);
assert!(b.first < b.last);
for cid in &b.members {
assert!(seen.insert(*cid), "template {cid} is in two blocks");
}
}
}
}
fn extent(cid: usize, first: usize, last: usize, count: u64) -> Extent {
Extent {
cid,
first,
last,
count,
}
}
#[test]
fn gone_templates_that_start_next_to_each_other_are_one_block() {
let extents = vec![
extent(4, 103, 103, 1),
extent(2, 101, 101, 1),
extent(3, 102, 102, 1),
extent(9, 400, 400, 1),
];
assert_eq!(gone_blocks(extents), vec![block(101, 103, &[2, 3, 4], 0)]);
}
#[test]
fn a_packed_template_carries_the_block_to_its_last_line() {
let extents = vec![
extent(1, 10, 10, 1),
extent(2, 11, 2010, 2000),
extent(3, 2011, 2011, 1),
];
assert_eq!(gone_blocks(extents), vec![block(10, 2011, &[1, 2, 3], 0)]);
}
#[test]
fn a_scattered_template_neither_extends_a_block_nor_folds_into_one() {
let extents = vec![
extent(1, 10, 10, 1),
extent(7, 11, 90_000, 450),
extent(2, 12, 12, 1),
extent(3, 5000, 5000, 1),
];
assert_eq!(gone_blocks(extents), vec![block(10, 12, &[1, 2], 0)]);
}
#[test]
fn skipped_steps_with_shared_lines_between_them_are_one_block() {
let mut extents = Vec::new();
for (step, start) in [100, 117, 134].into_iter().enumerate() {
for line in 0..6 {
extents.push(extent(step * 10 + line, start + line, start + line, 1));
}
}
let blocks = gone_blocks(extents);
assert_eq!(blocks.len(), 1);
assert_eq!((blocks[0].first, blocks[0].last), (100, 139));
assert_eq!(blocks[0].members.len(), 18);
}
#[test]
fn chains_join_only_while_a_third_of_the_stretch_is_gone() {
let extents = vec![
extent(1, 10, 10, 1),
extent(2, 11, 11, 1),
extent(3, 24, 24, 1),
extent(4, 25, 25, 1),
];
assert_eq!(
gone_blocks(extents),
vec![block(10, 11, &[1, 2], 0), block(24, 25, &[3, 4], 0)]
);
}
#[test]
fn chains_further_apart_than_the_gap_stay_apart_however_dense() {
let extents = vec![
extent(1, 1, 50, 50),
extent(2, 51, 100, 50),
extent(3, 121, 170, 50),
extent(4, 171, 220, 50),
];
assert_eq!(
gone_blocks(extents),
vec![block(1, 100, &[1, 2], 0), block(121, 220, &[3, 4], 0)]
);
}
#[test]
fn gone_lines_scattered_through_a_run_do_not_become_one_block() {
let extents: Vec<Extent> = (0..100)
.map(|i| extent(i, 5 + i * 10, 5 + i * 10, 1))
.collect();
assert_eq!(gone_blocks(extents), vec![]);
}
#[test]
fn two_gone_templates_far_apart_are_two_findings() {
let extents = vec![extent(1, 10, 10, 1), extent(2, 500, 500, 1)];
assert_eq!(gone_blocks(extents), vec![]);
}
}