Skip to main content

magi/
flake.rs

1//! Flaky verification: a `verify.e2e` failure that did not reproduce.
2//!
3//! `graph::run_e2e_with_retry` runs a failed e2e command once more on the same
4//! commit before anything is decided from it. When that second run passes, the
5//! first failure was not a verdict on the patch, and this module does the two
6//! things that follow:
7//!
8//! - identifies the failure ([`fingerprint`]) without knowing the test
9//!   framework, from the failure lines the saved output excerpt keeps;
10//! - files one queue task per distinct failure asking for the root cause
11//!   ([`record`]), so ten runs hitting the same flaky test leave one task.
12//!
13//! Best effort by construction, like `followup::after_merge`: a filing failure
14//! becomes a run event and never changes a verdict.
15
16use std::path::Path;
17
18use anyhow::{Result, bail};
19
20use crate::queue::{Queue, Source, Task, TaskStatus};
21use crate::run::{RunState, VerifyFlake};
22
23/// Node name carried by [`Source::Agent`] on a filed flake task.
24pub const NODE: &str = "flake";
25
26/// Lines of normalised failure text a fingerprint is made of, at most.
27const SIGNATURE_LINES: usize = 16;
28
29/// Characters of one normalised signature line that count.
30const LINE_CLIP: usize = 160;
31
32/// A task already finished for this failure does not cover a new occurrence
33/// (the fix did not hold, or something else broke it again); the next free
34/// generation is filed. This bounds the scan.
35const MAX_GENERATIONS: u32 = 16;
36
37/// A line mentioning one of these (lower-case match) belongs to the failure.
38/// Language- and framework-agnostic on purpose: `cargo test`, nextest, pytest,
39/// jest, go test and TAP all say at least one of these on a failing test.
40const FAILURE_WORDS: &[&str] = &[
41    "fail",
42    "panick",
43    "assert",
44    "error",
45    "not ok",
46    "timed out",
47    "timeout",
48    "exception",
49    "traceback",
50    "\u{2717}",
51    "\u{2718}",
52    "\u{d7}",
53];
54
55/// What identifies one failure: the normalised failure lines, sorted and
56/// distinct, plus a line to show a person.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct Signature {
59    /// Sorted, distinct, normalised lines (volatile numbers and ids removed).
60    pub lines: Vec<String>,
61    /// The first failure line as printed, for a title.
62    pub label: String,
63}
64
65fn strip_ansi(line: &str) -> String {
66    let mut out = String::with_capacity(line.len());
67    let mut chars = line.chars();
68    while let Some(c) = chars.next() {
69        if c == '\x1b' && chars.clone().next() == Some('[') {
70            chars.next();
71            for c in chars.by_ref() {
72                if ('@'..='~').contains(&c) {
73                    break;
74                }
75            }
76        } else {
77            out.push(c);
78        }
79    }
80    out
81}
82
83/// Replace what changes between two runs of the same failing test: numbers
84/// (durations, line numbers, thread ids, counts), long hex words (hashes) and
85/// random temporary directory names. Whitespace is collapsed.
86fn normalize(line: &str) -> String {
87    let mut out = String::with_capacity(line.len());
88    let mut token = String::new();
89    let flush = |token: &mut String, out: &mut String| {
90        if token.is_empty() {
91            return;
92        }
93        let hex = token.len() >= 8 && token.chars().all(|c| c.is_ascii_hexdigit());
94        if hex || (token.len() >= 7 && token.starts_with("tmp")) {
95            out.push('#');
96        } else {
97            let mut in_digits = false;
98            for c in token.chars() {
99                if c.is_ascii_digit() {
100                    if !in_digits {
101                        out.push('#');
102                    }
103                    in_digits = true;
104                } else {
105                    in_digits = false;
106                    out.push(c);
107                }
108            }
109        }
110        token.clear();
111    };
112    let mut space = false;
113    for c in line.trim().chars() {
114        if c.is_alphanumeric() || c == '_' {
115            if space {
116                out.push(' ');
117                space = false;
118            }
119            token.push(c);
120        } else if c.is_whitespace() {
121            flush(&mut token, &mut out);
122            space = true;
123        } else {
124            flush(&mut token, &mut out);
125            if space {
126                out.push(' ');
127                space = false;
128            }
129            out.push(c);
130        }
131    }
132    flush(&mut token, &mut out);
133    out.chars().take(LINE_CLIP).collect()
134}
135
136fn is_header(line: &str) -> bool {
137    let t = line.trim();
138    t.starts_with("[full output") || t.starts_with("[... output reduced") || t == "[...]"
139}
140
141fn is_failure_line(line: &str) -> bool {
142    let lower = line.trim().to_lowercase();
143    !lower.starts_with("test result: ok") && FAILURE_WORDS.iter().any(|word| lower.contains(word))
144}
145
146/// The [`Signature`] of a failing command's output (the excerpt magi kept) and
147/// exit code.
148///
149/// Failure lines (see [`FAILURE_WORDS`]) are normalised and sorted, so the
150/// order tests happen to fail in under parallel execution and the numbers a
151/// flaky assertion prints do not change the identity. Output with no failure
152/// line at all falls back to its last three lines, then to the exit code.
153pub fn signature(output: &str, code: Option<i32>) -> Signature {
154    let plain: Vec<String> = output
155        .lines()
156        .filter(|l| !is_header(l))
157        .map(strip_ansi)
158        .filter(|l| !l.trim().is_empty())
159        .collect();
160    let failing: Vec<&String> = plain.iter().filter(|l| is_failure_line(l)).collect();
161    let (picked, label): (Vec<&String>, String) = if failing.is_empty() {
162        let tail: Vec<&String> = plain.iter().rev().take(3).rev().collect();
163        let label = tail.first().map(|l| l.trim().to_owned());
164        (tail, label.unwrap_or_default())
165    } else {
166        (failing.clone(), failing[0].trim().to_owned())
167    };
168    let mut lines: Vec<String> = picked.iter().map(|l| normalize(l)).collect();
169    lines.sort();
170    lines.dedup();
171    lines.truncate(SIGNATURE_LINES);
172    if lines.is_empty() {
173        lines.push(format!(
174            "exit code {}",
175            code.map_or("none".into(), |c| c.to_string())
176        ));
177    }
178    let label = if label.is_empty() {
179        lines[0].clone()
180    } else {
181        label.chars().take(100).collect()
182    };
183    Signature { lines, label }
184}
185
186/// A stable identifier of the failure in `repo`: 40 bits of FNV-1a over the
187/// repository and the [`Signature`] lines, as ten hex digits. The command is
188/// deliberately not part of it: the same failing test reached through a
189/// different command line is the same defect.
190pub fn fingerprint(repo: &Path, signature: &Signature) -> String {
191    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
192    let mut feed = |bytes: &[u8]| {
193        for b in bytes {
194            h ^= u64::from(*b);
195            h = h.wrapping_mul(0x0100_0000_01b3);
196        }
197    };
198    feed(repo.to_string_lossy().as_bytes());
199    for line in &signature.lines {
200        feed(&[0]);
201        feed(line.as_bytes());
202    }
203    format!("{:010x}", h & 0xff_ffff_ffff)
204}
205
206/// The id of the generation-`n` task for failure `key`. Ends in the key, so
207/// `queue::short` names the failure whatever the generation.
208fn task_id(key: &str, generation: u32) -> String {
209    if generation <= 1 {
210        format!("flake-{key}")
211    } else {
212        format!("flake-r{generation}-{key}")
213    }
214}
215
216fn marker(key: &str) -> String {
217    format!("Failure fingerprint: {key}")
218}
219
220fn fenced(text: &str) -> String {
221    // A fence longer than any backtick run inside, so the excerpt cannot
222    // close it early.
223    let longest = text
224        .split(|c| c != '`')
225        .map(str::len)
226        .max()
227        .unwrap_or(0)
228        .max(2);
229    let fence = "`".repeat(longest + 1);
230    format!("{fence}\n{}\n{fence}", text.trim_end())
231}
232
233fn build_task(state: &RunState, flake: &VerifyFlake, label: &str, id: String) -> Task {
234    let excerpt = crate::scrub::scrub(&flake.first_failure, &crate::scrub::Identity::current());
235    let instruction = format!(
236        "A verification command failed once and then passed when it was run again on the \
237         same commit, so magi recorded the failure as a flake instead of charging it to the \
238         change that was being verified. Find the root cause of the intermittent failure and \
239         fix it.\n\n\
240         Fix the cause, not the symptom: do not loosen the assertion, add a retry, raise a \
241         timeout or skip the check to make it quieter. Typical causes are a race or an \
242         ordering assumption in the code or the test, shared state between tests (a fixed \
243         port, a shared directory, process-global state), a time-based wait that is too \
244         tight under load, and a layout or timing measurement taken before the page or \
245         process settled. To reproduce, run the check repeatedly and with several copies at \
246         once. If it no longer fails on current main after a serious attempt, say so and \
247         change nothing.\n\n\
248         {marker}\n\
249         Command: `{command}`\n\
250         Seen in run {run} ({context}) on commit {head}\n\n\
251         ## First failure (the rerun passed)\n\n{excerpt}\n",
252        marker = marker(&flake.fingerprint),
253        command = flake.command,
254        run = state.id,
255        context = flake.context,
256        head = flake.head,
257        excerpt = fenced(&excerpt),
258    );
259    let mut task = Task::new(
260        crate::queue::title_from(&format!("flaky verification: {label}"), 90),
261        instruction,
262        state.repo.clone(),
263        Source::Agent {
264            run: state.id.clone(),
265            node: NODE.to_owned(),
266        },
267    );
268    task.id = id;
269    task.solo = true;
270    task
271}
272
273/// File the task for `flake`, or find the unfinished one that already tracks
274/// the same failure. Returns the task id and whether this call created it.
275///
276/// Ids are derived from the failure, never from the run, and written with
277/// [`Queue::create_new`], so two runs hitting the same failure concurrently
278/// still leave one task. A finished (`Done`) task does not cover a recurrence:
279/// the next generation id is tried.
280pub fn file(
281    state: &RunState,
282    flake: &VerifyFlake,
283    label: &str,
284    queue: &Queue,
285) -> Result<(String, bool)> {
286    for generation in 1..=MAX_GENERATIONS {
287        let id = task_id(&flake.fingerprint, generation);
288        let mut task = build_task(state, flake, label, id.clone());
289        if queue.create_new(&mut task)? {
290            return Ok((id, true));
291        }
292        let existing = queue.get(&id)?;
293        if existing.status != TaskStatus::Done {
294            return Ok((id, false));
295        }
296    }
297    bail!("{MAX_GENERATIONS} earlier tasks for this failure are already done")
298}
299
300/// Record a flake in the run's ledger and file (or find) its task. Never
301/// fails: the outcome is part of the record and of a `verify` event.
302pub fn record(state: &mut RunState, mut flake: VerifyFlake, label: &str, queue: &Queue) {
303    match file(state, &flake, label, queue) {
304        Ok((id, created)) => {
305            state.event(
306                "verify",
307                format!(
308                    "{}: `{}` failed, then passed on the same commit {} - a flake, not a \
309                     verdict on the change; {} task {id} (failure {})",
310                    flake.context,
311                    flake.command,
312                    short(&flake.head),
313                    if created {
314                        "filed"
315                    } else {
316                        "already tracked by"
317                    },
318                    flake.fingerprint,
319                ),
320            );
321            flake.task = Some(id);
322            flake.filed = created;
323        }
324        Err(e) => {
325            state.event(
326                "verify",
327                format!(
328                    "{}: `{}` failed, then passed on the same commit {} - a flake, not a \
329                     verdict on the change; no task could be filed: {e:#}",
330                    flake.context,
331                    flake.command,
332                    short(&flake.head),
333                ),
334            );
335            flake.filing_error = Some(format!("{e:#}"));
336        }
337    }
338    state.verify_flakes.push(flake);
339}
340
341fn short(commit: &str) -> String {
342    commit.chars().take(7).collect()
343}
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348
349    fn sig(text: &str) -> Signature {
350        signature(text, Some(101))
351    }
352
353    #[test]
354    fn the_same_failure_has_one_signature_whatever_the_numbers_and_order() {
355        let a = "[full output: artifacts/e2e-1.out]\n\
356                 running 3 tests\n\
357                 test web::tests::layout ... FAILED\n\
358                 test talk::tests::turn ... FAILED\n\
359                 thread 'web::tests::layout' panicked at src/web.rs:101:9:\n\
360                 timed out after 5.31s waiting for 17 rows\n\
361                 test result: FAILED. 1 passed; 2 failed; 0 ignored; finished in 6.02s\n";
362        let b = "[full output: artifacts/e2e-4.out]\n\
363                 running 3 tests\n\
364                 test talk::tests::turn ... FAILED\n\
365                 thread 'web::tests::layout' panicked at src/web.rs:101:9:\n\
366                 timed out after 7.9s waiting for 4 rows\n\
367                 test web::tests::layout ... FAILED\n\
368                 test result: FAILED. 1 passed; 2 failed; 0 ignored; finished in 8.11s\n";
369        assert_eq!(sig(a).lines, sig(b).lines);
370        let repo = Path::new("/repo");
371        assert_eq!(fingerprint(repo, &sig(a)), fingerprint(repo, &sig(b)));
372    }
373
374    #[test]
375    fn a_different_failing_test_is_a_different_failure() {
376        let a = "test web::tests::layout ... FAILED\n";
377        let b = "test talk::tests::turn ... FAILED\n";
378        let repo = Path::new("/repo");
379        assert_ne!(fingerprint(repo, &sig(a)), fingerprint(repo, &sig(b)));
380        assert_ne!(
381            fingerprint(Path::new("/one"), &sig(a)),
382            fingerprint(Path::new("/two"), &sig(a)),
383            "the same text in another repository is another defect"
384        );
385    }
386
387    #[test]
388    fn passing_noise_does_not_enter_the_signature() {
389        let s = sig(
390            "test a ... ok\ntest result: ok. 12 passed; 0 failed; 0 ignored\n\
391             test b ... FAILED\n",
392        );
393        assert_eq!(s.lines, vec!["test b ... FAILED".to_owned()]);
394        assert_eq!(s.label, "test b ... FAILED");
395    }
396
397    #[test]
398    fn output_without_a_failure_word_falls_back_to_its_tail_then_the_exit_code() {
399        assert_eq!(
400            sig("one\ntwo\nthree\nfour\n").lines,
401            ["four", "three", "two"]
402        );
403        assert_eq!(sig("").lines, ["exit code 101"]);
404        assert_eq!(signature("", None).lines, ["exit code none"]);
405    }
406
407    #[test]
408    fn random_names_and_hashes_are_normalised_away() {
409        let a = normalize("error: C:\\Temp\\.tmpAbC123 at deadbeef01 in 12ms");
410        let b = normalize("error: C:\\Temp\\.tmpZzZ999 at 0123abcd99 in 7ms");
411        assert_eq!(a, b);
412    }
413
414    #[test]
415    fn a_task_per_failure_is_filed_once_and_a_finished_one_does_not_cover() {
416        let dir = tempfile::tempdir().unwrap();
417        let queue = Queue::at(dir.path().join("queue"));
418        let state = RunState::new(
419            Path::new("/repo").to_path_buf(),
420            "main".into(),
421            "abc1234".into(),
422            "make a note".into(),
423            crate::config::Config::default(),
424        );
425        let s = sig("test web::tests::layout ... FAILED\n");
426        let flake = VerifyFlake {
427            round: Some(1),
428            context: "round 1".into(),
429            head: "abcdef1234567890".into(),
430            command: "cargo test".into(),
431            first_failure: "test web::tests::layout ... FAILED".into(),
432            fingerprint: fingerprint(&state.repo, &s),
433            at: jiff::Timestamp::now(),
434            task: None,
435            filed: false,
436            filing_error: None,
437        };
438        let (first, created) = file(&state, &flake, &s.label, &queue).unwrap();
439        assert!(created);
440        let (again, created) = file(&state, &flake, &s.label, &queue).unwrap();
441        assert_eq!((again.as_str(), created), (first.as_str(), false));
442        assert_eq!(queue.list().len(), 1);
443        let task = queue.get(&first).unwrap();
444        assert!(task.instruction.contains(&marker(&flake.fingerprint)));
445        assert!(task.instruction.contains("not the symptom"));
446        assert!(matches!(&task.source, Source::Agent { node, .. } if node == NODE));
447
448        queue
449            .modify(&first, |t| {
450                t.status = TaskStatus::Done;
451                true
452            })
453            .unwrap();
454        let (next, created) = file(&state, &flake, &s.label, &queue).unwrap();
455        assert!(created, "a recurrence after the task was done is new work");
456        assert_ne!(next, first);
457        assert_eq!(crate::queue::short(&next), crate::queue::short(&first));
458    }
459}