use std::collections::HashMap;
use serde::Serialize;
use crate::mask::is_placeholder;
#[derive(Debug, Clone, Serialize)]
pub struct Cluster {
pub id: usize,
pub tokens: Vec<String>,
pub count: u64,
pub first_line_no: usize,
pub first_line_raw: String,
}
impl Cluster {
pub fn template(&self) -> String {
self.tokens.join(" ")
}
}
pub const DEFAULT_SIMILARITY_THRESHOLD: f64 = 0.5;
pub struct Drain {
threshold: f64,
index: HashMap<(usize, String), Vec<usize>>,
clusters: Vec<Cluster>,
}
impl Default for Drain {
fn default() -> Self {
Self::new(DEFAULT_SIMILARITY_THRESHOLD)
}
}
impl Drain {
pub fn new(threshold: f64) -> Self {
Drain {
threshold,
index: HashMap::new(),
clusters: Vec::new(),
}
}
pub fn clusters(&self) -> &[Cluster] {
&self.clusters
}
pub fn into_clusters(self) -> Vec<Cluster> {
self.clusters
}
pub fn add_line(&mut self, masked: &str, line_no: usize, raw: &str) -> usize {
let tokens: Vec<String> = masked.split_whitespace().map(str::to_owned).collect();
self.add_tokens(tokens, line_no, raw)
}
pub fn add_tokens(&mut self, tokens: Vec<String>, line_no: usize, raw: &str) -> usize {
if tokens.is_empty() {
return self.upsert_empty(line_no, raw);
}
let key = (tokens.len(), tokens[0].clone());
let candidates = self.index.entry(key.clone()).or_default();
let mut best: Option<(usize, f64)> = None;
for &cid in candidates.iter() {
let sim = similarity(&self.clusters[cid].tokens, &tokens);
if sim >= self.threshold && best.map(|(_, bs)| sim > bs).unwrap_or(true) {
best = Some((cid, sim));
}
}
if let Some((cid, _)) = best {
let cluster = &mut self.clusters[cid];
for (t, l) in cluster.tokens.iter_mut().zip(tokens.iter()) {
if t != l && t != "<*>" {
*t = "<*>".to_string();
}
}
cluster.count += 1;
cid
} else {
let cid = self.clusters.len();
self.clusters.push(Cluster {
id: cid,
tokens,
count: 1,
first_line_no: line_no,
first_line_raw: raw.to_string(),
});
self.index.entry(key).or_default().push(cid);
cid
}
}
pub fn contains_matching_template(&self, tokens: &[String]) -> bool {
if tokens.is_empty() {
return self.index.contains_key(&(0, String::new()));
}
let key = (tokens.len(), tokens[0].clone());
let Some(candidates) = self.index.get(&key) else {
return false;
};
candidates
.iter()
.any(|&cid| similarity(&self.clusters[cid].tokens, tokens) >= self.threshold)
}
fn upsert_empty(&mut self, line_no: usize, raw: &str) -> usize {
let key = (0usize, String::new());
if let Some(&cid) = self.index.get(&key).and_then(|v| v.first()) {
self.clusters[cid].count += 1;
return cid;
}
let cid = self.clusters.len();
self.clusters.push(Cluster {
id: cid,
tokens: Vec::new(),
count: 1,
first_line_no: line_no,
first_line_raw: raw.to_string(),
});
self.index.entry(key).or_default().push(cid);
cid
}
}
fn similarity(template: &[String], line: &[String]) -> f64 {
debug_assert_eq!(template.len(), line.len());
if template.is_empty() {
return 1.0;
}
let has_literal_content = template.iter().any(|t| t != "<*>" && !is_placeholder(t));
let matches = template
.iter()
.zip(line.iter())
.filter(|(t, l)| {
if *t == "<*>" {
return true;
}
if t != l {
return false;
}
!(has_literal_content && is_placeholder(t))
})
.count();
matches as f64 / template.len() as f64
}
#[cfg(test)]
mod tests {
use super::*;
fn ids(drain: &mut Drain, lines: &[&str]) -> Vec<usize> {
lines
.iter()
.enumerate()
.map(|(i, l)| drain.add_line(l, i + 1, l))
.collect()
}
#[test]
fn identical_lines_form_one_cluster() {
let mut d = Drain::default();
let got = ids(&mut d, &["a b c", "a b c", "a b c"]);
assert_eq!(got, vec![0, 0, 0]);
assert_eq!(d.clusters()[0].count, 3);
assert_eq!(d.clusters()[0].template(), "a b c");
}
#[test]
fn one_varying_token_becomes_wildcard() {
let mut d = Drain::default();
ids(&mut d, &["connected to <IP>", "connected to <IP>"]);
assert_eq!(d.clusters().len(), 1);
assert_eq!(d.clusters()[0].template(), "connected to <IP>");
let mut d2 = Drain::default();
ids(&mut d2, &["user alice logged in", "user bob logged in"]);
assert_eq!(d2.clusters().len(), 1);
assert_eq!(d2.clusters()[0].template(), "user <*> logged in");
assert_eq!(d2.clusters()[0].count, 2);
}
#[test]
fn different_token_counts_are_different_clusters() {
let mut d = Drain::default();
let got = ids(&mut d, &["a b c", "a b c d"]);
assert_ne!(got[0], got[1]);
assert_eq!(d.clusters().len(), 2);
}
#[test]
fn below_threshold_similarity_starts_new_cluster() {
let mut d = Drain::new(0.9);
let got = ids(&mut d, &["start job one", "abort task two"]);
assert_ne!(got[0], got[1]);
}
#[test]
fn deterministic_across_runs() {
let lines = [
"user alice logged in",
"user bob logged in",
"disk usage 92 percent",
"disk usage 10 percent",
"user carol logged in",
];
let mut d1 = Drain::default();
let ids1 = ids(&mut d1, &lines);
let mut d2 = Drain::default();
let ids2 = ids(&mut d2, &lines);
assert_eq!(ids1, ids2);
let templates1: Vec<_> = d1.clusters().iter().map(Cluster::template).collect();
let templates2: Vec<_> = d2.clusters().iter().map(Cluster::template).collect();
assert_eq!(templates1, templates2);
}
#[test]
fn records_first_occurrence() {
let mut d = Drain::default();
d.add_line("user alice logged in", 1, "raw: user alice logged in");
d.add_line("user bob logged in", 5, "raw: user bob logged in");
assert_eq!(d.clusters()[0].first_line_no, 1);
assert_eq!(d.clusters()[0].first_line_raw, "raw: user alice logged in");
}
#[test]
fn empty_lines_cluster_together() {
let mut d = Drain::default();
let got = ids(&mut d, &["", "", "a b"]);
assert_eq!(got[0], got[1]);
assert_ne!(got[0], got[2]);
}
#[test]
fn shared_placeholder_prefix_does_not_merge_unrelated_lines() {
let mut d = Drain::default();
let got = ids(
&mut d,
&[
"<TS> stderr F alpha=1 beta=2 gamma=3",
"<TS> stderr F goroutine 42 [running]:",
],
);
assert_ne!(
got[0], got[1],
"unrelated lines sharing only a <TS> + boilerplate prefix must not merge"
);
}
#[test]
fn fully_templated_short_lines_still_cluster_on_placeholder_sequence_alone() {
let mut d = Drain::default();
let got = ids(&mut d, &["<TS> <NUM>", "<TS> <NUM>"]);
assert_eq!(got[0], got[1]);
assert_eq!(d.clusters()[0].count, 2);
}
#[test]
fn literal_tokens_still_generalize_around_a_real_shared_prefix() {
let mut d = Drain::default();
let got = ids(
&mut d,
&["user alice logged in at <TS>", "user bob logged in at <TS>"],
);
assert_eq!(got[0], got[1]);
assert_eq!(d.clusters()[0].template(), "user <*> logged in at <TS>");
}
#[test]
fn add_tokens_matches_add_line_for_plain_whitespace_tokenizing() {
let mut d = Drain::default();
let id_a = d.add_line("user alice in", 1, "user alice in");
let mut d2 = Drain::default();
let id_b = d2.add_tokens(
vec!["user".into(), "alice".into(), "in".into()],
1,
"user alice in",
);
assert_eq!(id_a, id_b);
assert_eq!(d.clusters()[0].template(), d2.clusters()[0].template());
}
}