Skip to main content

runnerd_core/api/jobs/log/
outline.rs

1//! A job's log outline: the groups and the error and warning marks [`Outliner`] finds as lines are stored, which
2//! lines each step printed as far as that can be told, how much of the log is there, and what a failed job's log
3//! says of its failure. The store keeps an [`Outliner`]'s state and changes beside the lines; [`LogOutline::assemble`]
4//! reads them back with the job's stored steps, which stay the authority on a step's times and outcome.
5//!
6//! Which lines a step printed is best effort: the log does not say. A segment starts at the first outlined line, at
7//! every group and at the lines the runner opens a step with but no group (`Post job cleanup.`, `Cleaning up orphan
8//! processes`, a job hook's). GitHub stores a step's times in whole seconds, so time alone cannot split the steps
9//! that share one, such as a quick failure and the skipped steps after it. The runner opens every step but `Set up
10//! job` and the few it adds without a header (`HEADERLESS`, `HEADERLESS_GROUPS`) with a top-level `Run …` group
11//! or one of those lines, so the log is cut there into blocks, and each step that ran printed one or more blocks, in
12//! order. A block goes to a step when every way of giving each block to a step in order, each step its times hold and
13//! each step that ran at least one block, gives it that step: a user group titled `Run …` adds a block no order
14//! settles, and it goes to no step. Where a headerless step ran, the outline was capped, or no such way exists, a
15//! segment goes to the one step, at or after the previous segment's, whose stored times hold the times of
16//! its first and its last line that has one. A block or segment no time places goes to no step, unless it lies
17//! between two of one step. Never by position, and never by a title alone: a step can print any title.
18
19use std::fmt::Write as _;
20
21use serde::{Deserialize, Serialize};
22
23use super::{LineKind, LineRead, StoredLine, StyledLine, classify, plain, prefix, time_of};
24use crate::api::{Job, RecordNote, RecordState, Step, Tone};
25
26/// Groups nested deeper than this are counted, not kept.
27pub(crate) const DEPTH_MAX: usize = 8;
28
29/// Groups a job's outline keeps; later ones are counted, not kept.
30pub(crate) const GROUP_MAX: u64 = 1000;
31
32/// Error and warning lines a job's outline marks; later ones are counted, not marked.
33pub(crate) const MARK_MAX: u64 = 1000;
34
35/// Lines that start a step without a group (`Post job cleanup.`) an outline keeps.
36const SECTION_MAX: u64 = 200;
37
38/// A group's title is cut to this many bytes.
39const TITLE_MAX: usize = 200;
40
41/// A group's title is read from at most this many bytes of its line.
42pub(crate) const TITLE_SOURCE_MAX: usize = 4 * TITLE_MAX;
43
44/// How much of a line is read for its time: the runner's timestamp and the space after it.
45const TIME_PREFIX: u64 = 64;
46
47/// How much of a failed step's line is read for its exit code: the runner's line is short.
48const EXIT_PREFIX: u64 = 256;
49
50/// How much of each line of a failure's excerpt is shown, in bytes; the rest is counted as omitted.
51const EXCERPT_LINE_BYTES: u64 = 4 << 10;
52
53/// How far back from a failed step's last line its exit code is looked for.
54const EXIT_SCAN: u64 = 200;
55
56/// The last lines of a failed step a failure summary shows.
57const EXCERPT: u64 = 10;
58
59/// Lines the runner prints when a step begins without a group: each post step, `Complete job`, and the steps of a
60/// self-hosted runner's job hooks, whose `Run …` group follows.
61const SECTIONS: [&str; 4] = [
62    "Post job cleanup.",
63    "Cleaning up orphan processes",
64    "A job started hook has been configured by the self-hosted runner administrator",
65    "A job completed hook has been configured by the self-hosted runner administrator",
66];
67
68/// How the runner titles the top-level group that opens a script or action step: `Run cargo test`.
69const HEADER: &str = "Run ";
70
71/// The steps the runner opens with no header: their lines join the block before them, or they print none, so a log
72/// with one is not cut into blocks.
73const HEADERLESS: [&str; 4] = [
74    "Initialize containers",
75    "Stop containers",
76    "Wait for all background steps",
77    "Create custom image",
78];
79
80/// How the runner titles the groups of the steps it adds for a Docker action, `Pull …` and `Build …`, which have no
81/// header: a log with one is not cut into blocks. Their step names are not matched, since a user's step can be named
82/// `Build the app`.
83const HEADERLESS_GROUPS: [&str; 2] = ["Pull down action image", "Build container for action use"];
84
85/// How the runner says a script step failed: `##[error]Process completed with exit code 101.`.
86const EXIT: &str = "Process completed with exit code ";
87
88/// What the store keeps of an outline between batches of lines: one row per job.
89#[derive(Debug, Clone, Default, PartialEq, Eq)]
90pub struct SavedOutline {
91    /// The first line outlined: 0, or the next line of a job whose log an older runnerd began.
92    pub from: u64,
93    /// Error lines seen.
94    pub errors: u64,
95    /// Warning lines seen.
96    pub warnings: u64,
97    /// Groups kept.
98    pub groups: u64,
99    /// Error and warning marks kept.
100    pub marks: u64,
101    /// Section lines kept.
102    pub sections: u64,
103    /// Groups not kept: nested past 8 deep or past 1000 a job.
104    pub dropped: u64,
105    /// Of those, the ones still open: an `##[endgroup]` closes one of them before a kept one.
106    pub hidden: u64,
107    /// The kept groups still open, outermost first, by the line they start at.
108    pub open: Vec<u64>,
109}
110
111/// What a line changes in the outline, for the store to keep.
112#[derive(Debug, Clone, PartialEq, Eq)]
113pub enum OutlineChange {
114    /// A group starts at `start`, inside `depth` open ones.
115    Opened {
116        /// Its `##[group]` line.
117        start: u64,
118        /// How many groups it is inside.
119        depth: u32,
120        /// Its title, plain and cut to 200 bytes.
121        title: String,
122    },
123    /// The group that started at `start` ends at `end`, its `##[endgroup]` line.
124    Closed {
125        /// Its `##[group]` line.
126        start: u64,
127        /// Its `##[endgroup]` line.
128        end: u64,
129    },
130    /// An error or warning line.
131    Marked(LogMark),
132    /// A line that starts a step without a group.
133    Section {
134        /// The line.
135        line: u64,
136    },
137}
138
139/// Builds a job's outline a line at a time. The store resumes one from its saved state for each batch of lines and
140/// saves it after, in the transaction that stores the lines.
141#[derive(Debug)]
142pub struct Outliner {
143    saved: SavedOutline,
144}
145
146impl Outliner {
147    /// An outline starting at line `from`.
148    pub fn new(from: u64) -> Outliner {
149        Outliner {
150            saved: SavedOutline {
151                from,
152                ..SavedOutline::default()
153            },
154        }
155    }
156
157    /// The outline the store saved.
158    pub fn resume(saved: SavedOutline) -> Outliner {
159        Outliner { saved }
160    }
161
162    /// What to save.
163    pub fn saved(&self) -> &SavedOutline {
164        &self.saved
165    }
166
167    /// Reads line `line`, with stored text `text`: what it changes, if anything.
168    pub fn line(&mut self, line: u64, text: &str) -> Option<OutlineChange> {
169        let saved = &mut self.saved;
170        let (kind, rest) = classify(text);
171        match kind {
172            LineKind::Group => {
173                if saved.hidden > 0 || saved.open.len() >= DEPTH_MAX || saved.groups >= GROUP_MAX {
174                    saved.hidden += 1;
175                    saved.dropped += 1;
176                    return None;
177                }
178                let depth = u32::try_from(saved.open.len()).unwrap_or(u32::MAX);
179                saved.open.push(line);
180                saved.groups += 1;
181                Some(OutlineChange::Opened {
182                    start: line,
183                    depth,
184                    title: title(rest),
185                })
186            }
187            LineKind::EndGroup => {
188                if saved.hidden > 0 {
189                    saved.hidden -= 1;
190                    return None;
191                }
192                // One with no open group is left alone.
193                let start = saved.open.pop()?;
194                Some(OutlineChange::Closed { start, end: line })
195            }
196            LineKind::Error | LineKind::Warning => {
197                let kind = if kind == LineKind::Error {
198                    saved.errors += 1;
199                    MarkKind::Error
200                } else {
201                    saved.warnings += 1;
202                    MarkKind::Warning
203                };
204                (saved.marks < MARK_MAX).then(|| {
205                    saved.marks += 1;
206                    OutlineChange::Marked(LogMark { line, kind })
207                })
208            }
209            LineKind::Output if SECTIONS.contains(&rest) && saved.sections < SECTION_MAX => {
210                saved.sections += 1;
211                Some(OutlineChange::Section { line })
212            }
213            _ => None,
214        }
215    }
216}
217
218/// A title, such as a group's or a step's name: plain, read from its first [`TITLE_SOURCE_MAX`] bytes and cut to
219/// [`TITLE_MAX`].
220pub(crate) fn title(text: &str) -> String {
221    let title = plain(prefix(text, TITLE_SOURCE_MAX));
222    prefix(&title, TITLE_MAX).to_owned()
223}
224
225/// Lines from `from` up to, not including, `to`.
226#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
227pub struct LineRange {
228    /// The first line.
229    pub from: u64,
230    /// The line after the last.
231    pub to: u64,
232}
233
234impl LineRange {
235    /// Whether it holds no line.
236    pub fn is_empty(&self) -> bool {
237        self.to <= self.from
238    }
239}
240
241/// A foldable group of lines, from its `##[group]` to its `##[endgroup]` line.
242#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
243pub struct LogGroup {
244    /// Its `##[group]` line.
245    pub start: u64,
246    /// Its `##[endgroup]` line; absent while it is open, or when the log never closed it.
247    #[serde(default, skip_serializing_if = "Option::is_none")]
248    pub end: Option<u64>,
249    /// How many groups it is inside.
250    pub depth: u32,
251    /// Its title.
252    pub title: String,
253}
254
255/// What a marked line says.
256#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
257#[serde(rename_all = "kebab-case")]
258pub enum MarkKind {
259    /// `##[error]`.
260    Error,
261    /// `##[warning]`.
262    Warning,
263    /// A kind a newer daemon names.
264    #[serde(other)]
265    Unknown,
266}
267
268/// An error or warning line.
269#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
270pub struct LogMark {
271    /// The line.
272    pub line: u64,
273    /// What it says.
274    pub kind: MarkKind,
275}
276
277/// Which lines a step printed, as far as the log tells.
278#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
279#[serde(tag = "kind", rename_all = "kebab-case")]
280pub enum StepLog {
281    /// These lines.
282    Lines(LineRange),
283    /// None: it was skipped or has not started.
284    Empty,
285    /// Its lines cannot be told from the others', or are not here: they may be among the unattributed ones.
286    Unattributed,
287    /// A reading a newer daemon gives; this client treats it as unattributed.
288    #[serde(other)]
289    Unknown,
290}
291
292/// A stored step and its lines.
293#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
294pub struct StepLines {
295    /// The step's number, as in `Job::steps`.
296    pub number: u32,
297    /// Its lines.
298    pub lines: StepLog,
299}
300
301/// How much of a job's log there is to read, in order of precedence.
302#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
303#[serde(rename_all = "kebab-case")]
304pub enum LogEvidence {
305    /// Every line the job printed, outlined.
306    Complete,
307    /// The job still runs: lines may come.
308    Running,
309    /// Outlined only from `LogOutline::from`: an older runnerd stored the lines before it.
310    Partial,
311    /// Cut at `history.log_max`: what the job printed after was not kept.
312    Truncated,
313    /// Deleted after `history.logs`, or being deleted.
314    Expired,
315    /// No log was captured.
316    Missing,
317    /// Stored by a runnerd that kept no outline: the lines read, without their structure.
318    NotOutlined,
319    /// A reading a newer daemon gives.
320    #[serde(other)]
321    Unknown,
322}
323
324impl LogEvidence {
325    /// What a reader needs told, if anything: `cut at history.log_max`.
326    pub fn words(self) -> Option<&'static str> {
327        match self {
328            LogEvidence::Complete => None,
329            LogEvidence::Running => Some("still running"),
330            LogEvidence::Partial => Some("outlined from a later line"),
331            LogEvidence::Truncated => Some("cut at history.log_max"),
332            LogEvidence::Expired => Some("deleted after history.logs"),
333            LogEvidence::Missing => Some("no log was captured"),
334            LogEvidence::NotOutlined => Some("kept without an outline"),
335            LogEvidence::Unknown => Some("read by a newer runnerd"),
336        }
337    }
338
339    /// What it means: a cut log is worth a look.
340    pub fn tone(self) -> Tone {
341        match self {
342            LogEvidence::Truncated => Tone::Warn,
343            LogEvidence::Complete => Tone::Neutral,
344            _ => Tone::Quiet,
345        }
346    }
347
348    /// Whether lines past what is stored may still come.
349    pub fn grows(self) -> bool {
350        self == LogEvidence::Running
351    }
352}
353
354/// What a failed job's log says of its failure. Each part is absent where the evidence is.
355#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
356pub struct FailureSummary {
357    /// The first step GitHub reports failed.
358    #[serde(default, skip_serializing_if = "Option::is_none")]
359    pub step: Option<u32>,
360    /// The exit code the runner printed in that step's lines.
361    #[serde(default, skip_serializing_if = "Option::is_none")]
362    pub exit_code: Option<i64>,
363    /// That step's last lines; absent when which lines are its is unknown.
364    #[serde(default, skip_serializing_if = "Option::is_none")]
365    pub excerpt: Option<Vec<StyledLine>>,
366    /// The command that opens a shell in the job's record, while it is kept: `runnerctl shell 42`.
367    #[serde(default, skip_serializing_if = "Option::is_none")]
368    pub shell: Option<String>,
369}
370
371impl FailureSummary {
372    /// Its first line, for `steps`, the job's: `Step 4, Unit tests, failed with exit code 101`.
373    pub fn headline(&self, steps: &[Step]) -> String {
374        let Some(number) = self.step else {
375            return "No step reports the failure".to_owned();
376        };
377        let mut text = match steps.iter().find(|step| step.number == number) {
378            Some(step) => format!("Step {number}, {}, failed", title(&step.name)),
379            None => format!("Step {number} failed"),
380        };
381        if let Some(code) = self.exit_code {
382            write!(text, " with exit code {code}").ok();
383        }
384        text
385    }
386}
387
388/// `GET /v1/jobs/{id}/log/outline`: a job's log as structure.
389#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
390pub struct LogOutline {
391    /// The job.
392    pub job: u64,
393    /// How much of the log there is.
394    pub evidence: LogEvidence,
395    /// Lines stored: they are numbered from 0 up to this, less any deleted.
396    pub lines: u64,
397    /// The first line outlined; `lines` when none is.
398    pub from: u64,
399    /// Its groups, by their first line.
400    pub groups: Vec<LogGroup>,
401    /// Each stored step and its lines, in the job's order.
402    pub steps: Vec<StepLines>,
403    /// The stored lines no step got.
404    pub unattributed: Vec<LineRange>,
405    /// Error lines seen.
406    pub errors: u64,
407    /// Warning lines seen.
408    pub warnings: u64,
409    /// The error and warning lines, up to 1000.
410    pub marks: Vec<LogMark>,
411    /// Some groups or marks were only counted: more than it keeps.
412    pub capped: bool,
413    /// On a failed job: what its log says of the failure.
414    #[serde(default, skip_serializing_if = "Option::is_none")]
415    pub failure: Option<FailureSummary>,
416}
417
418/// What the store has of a job's log besides its outline.
419#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
420pub struct StoredLog {
421    /// Lines stored, as `LogSummary::lines` counts them.
422    pub lines: u64,
423    /// Whether the log reached `history.log_max`.
424    pub truncated: bool,
425    /// Whether its first and its last line are still there: pruning deletes from the first.
426    pub kept: bool,
427}
428
429/// What the store keeps of a job's outline: its saved state, `None` for a log no outline was kept of, and its groups,
430/// marks and section lines, each by line.
431#[derive(Debug, Clone, Default, PartialEq, Eq)]
432pub struct OutlineParts {
433    /// Its state.
434    pub saved: Option<SavedOutline>,
435    /// Its groups.
436    pub groups: Vec<LogGroup>,
437    /// Its marks.
438    pub marks: Vec<LogMark>,
439    /// The lines that start a step without a group.
440    pub sections: Vec<u64>,
441}
442
443/// A segment of the log, from one possible step start to the next.
444#[derive(Debug)]
445struct Segment {
446    range: LineRange,
447    /// The times of its first and last lines, in seconds.
448    first: Option<u64>,
449    last: Option<u64>,
450}
451
452impl LogOutline {
453    /// How many lines a part of the log holds, as a fold says it: `1 line`, `5 lines`.
454    pub fn count_words(lines: usize) -> String {
455        if lines == 1 {
456            "1 line".to_owned()
457        } else {
458            format!("{lines} lines")
459        }
460    }
461
462    /// What a client says when it outlines only the log's last `shown` lines, `first` lines in: `The last 5000 lines;
463    /// the full log has the 1200 before them`. `None` when it shows them all.
464    pub fn tail_words(first: u64, shown: usize) -> Option<String> {
465        (first > 0)
466            .then(|| format!("the last {shown} lines; the full log has the {first} before them"))
467    }
468
469    /// Assembles a job's outline from what the store keeps, all read at one time. `read` returns the stored lines
470    /// a [`LineRead`] asks for: the start of the first and last line of each segment, and a failed step's last
471    /// lines, the most of them cut to a few hundred bytes.
472    pub fn assemble(
473        job: &Job,
474        stored: StoredLog,
475        parts: OutlineParts,
476        read: &mut dyn FnMut(LineRead) -> Vec<StoredLine>,
477    ) -> LogOutline {
478        let evidence = evidence(job, stored, parts.saved.as_ref());
479        let outlined = stored.kept && parts.saved.is_some();
480        let saved = parts.saved.unwrap_or_default();
481        let from = if outlined { saved.from } else { stored.lines };
482        let segments = if outlined {
483            segments(from, stored.lines, &parts.groups, &parts.sections, read)
484        } else {
485            Vec::new()
486        };
487        let ends = Ends {
488            leading: from > 0,
489            trailing: stored.truncated || !job.summary.state.is_final(),
490        };
491        let ranges = block_starts(from, stored.lines, &parts.groups, &parts.sections, &saved)
492            .and_then(|starts| by_blocks(&job.steps, &segments, &starts, ends))
493            .unwrap_or_else(|| attribute(&job.steps, &segments));
494        let steps: Vec<StepLines> = job
495            .steps
496            .iter()
497            .zip(&ranges)
498            .map(|(step, range)| StepLines {
499                number: step.number,
500                lines: match range {
501                    Some(range) => StepLog::Lines(*range),
502                    None if step.started_at.is_none()
503                        || step.conclusion.as_deref() == Some("skipped") =>
504                    {
505                        StepLog::Empty
506                    }
507                    None => StepLog::Unattributed,
508                },
509            })
510            .collect();
511        let readable = !matches!(evidence, LogEvidence::Expired | LogEvidence::Missing);
512        let unattributed = if readable {
513            gaps(stored.lines, ranges.iter().flatten())
514        } else {
515            Vec::new()
516        };
517        let failure = job.summary.is_failure().then(|| failure(job, &steps, read));
518        LogOutline {
519            job: job.summary.id,
520            evidence,
521            lines: stored.lines,
522            from,
523            capped: saved.dropped > 0 || saved.marks < saved.errors + saved.warnings,
524            errors: saved.errors,
525            warnings: saved.warnings,
526            groups: parts.groups,
527            marks: parts.marks,
528            steps,
529            unattributed,
530            failure,
531        }
532    }
533
534    /// The outline of a whole log held in memory, as the store would keep it: for fixtures and the demo.
535    pub fn of(job: &Job, lines: &[String]) -> LogOutline {
536        let mut outliner = Outliner::new(0);
537        let mut parts = OutlineParts::default();
538        for (number, text) in (0..).zip(lines) {
539            match outliner.line(number, text) {
540                Some(OutlineChange::Opened {
541                    start,
542                    depth,
543                    title,
544                }) => {
545                    parts.groups.push(LogGroup {
546                        start,
547                        end: None,
548                        depth,
549                        title,
550                    });
551                }
552                Some(OutlineChange::Closed { start, end }) => {
553                    if let Some(group) = parts.groups.iter_mut().find(|group| group.start == start)
554                    {
555                        group.end = Some(end);
556                    }
557                }
558                Some(OutlineChange::Marked(mark)) => parts.marks.push(mark),
559                Some(OutlineChange::Section { line }) => parts.sections.push(line),
560                None => {}
561            }
562        }
563        parts.saved = (!lines.is_empty()).then(|| outliner.saved().clone());
564        let stored = StoredLog {
565            lines: lines.len() as u64,
566            truncated: job.summary.log.truncated,
567            kept: true,
568        };
569        LogOutline::assemble(job, stored, parts, &mut |read| read.of(lines))
570    }
571
572    /// The lines of step `number`, when known.
573    pub fn step_lines(&self, number: u32) -> Option<LineRange> {
574        self.steps
575            .iter()
576            .find(|step| step.number == number)
577            .and_then(|step| match step.lines {
578                StepLog::Lines(range) => Some(range),
579                _ => None,
580            })
581    }
582}
583
584fn evidence(job: &Job, stored: StoredLog, saved: Option<&SavedOutline>) -> LogEvidence {
585    let fin = job.summary.state.is_final();
586    if stored.lines > 0 && !stored.kept {
587        return LogEvidence::Expired;
588    }
589    // A log can reach its cap before its first line is stored.
590    if stored.truncated {
591        return LogEvidence::Truncated;
592    }
593    if stored.lines == 0 {
594        return if fin {
595            LogEvidence::Missing
596        } else {
597            LogEvidence::Running
598        };
599    }
600    let Some(saved) = saved else {
601        return LogEvidence::NotOutlined;
602    };
603    if saved.from > 0 {
604        LogEvidence::Partial
605    } else if !fin {
606        LogEvidence::Running
607    } else {
608        LogEvidence::Complete
609    }
610}
611
612/// The stored lines in `range`, each cut to `prefix` bytes.
613fn read_range(
614    read: &mut dyn FnMut(LineRead) -> Vec<StoredLine>,
615    range: LineRange,
616    prefix: u64,
617) -> Vec<StoredLine> {
618    let mut lines = read(LineRead {
619        from: range.from,
620        limit: range.to.saturating_sub(range.from),
621        prefix,
622        bytes: u64::MAX,
623    });
624    lines.retain(|line| line.line < range.to);
625    lines
626}
627
628/// The log from `from` to `lines`, cut at every group and section line.
629fn segments(
630    from: u64,
631    lines: u64,
632    groups: &[LogGroup],
633    sections: &[u64],
634    read: &mut dyn FnMut(LineRead) -> Vec<StoredLine>,
635) -> Vec<Segment> {
636    let mut starts: Vec<u64> = std::iter::once(from)
637        .chain(groups.iter().map(|group| group.start))
638        .chain(sections.iter().copied())
639        .filter(|start| (from..lines).contains(start))
640        .collect();
641    starts.sort_unstable();
642    starts.dedup();
643    let mut time = |line: u64| {
644        read_range(
645            read,
646            LineRange {
647                from: line,
648                to: line + 1,
649            },
650            TIME_PREFIX,
651        )
652        .first()
653        .and_then(|line| time_of(&line.text))
654    };
655    starts
656        .iter()
657        .enumerate()
658        .map(|(index, &start)| {
659            let end = starts.get(index + 1).copied().unwrap_or(lines);
660            Segment {
661                range: LineRange {
662                    from: start,
663                    to: end,
664                },
665                first: time(start),
666                last: time(end - 1),
667            }
668        })
669        .collect()
670}
671
672/// Whether `step` ran over `at`, in seconds: its stored times are whole seconds, so its last one is held to its end.
673fn holds(step: &Step, at: u64) -> bool {
674    step.started_at
675        .is_some_and(|started| at >= started && step.completed_at.is_none_or(|end| at <= end))
676}
677
678/// Each step's lines, by index into `steps`: the segments it got, with any between them.
679fn attribute(steps: &[Step], segments: &[Segment]) -> Vec<Option<LineRange>> {
680    let mut ranges: Vec<Option<LineRange>> = vec![None; steps.len()];
681    let mut earliest = 0;
682    for segment in segments {
683        let times: Vec<u64> = [segment.first, segment.last]
684            .into_iter()
685            .flatten()
686            .collect();
687        if times.is_empty() {
688            continue;
689        }
690        let mut candidates = (earliest..steps.len())
691            .filter(|&index| times.iter().all(|&at| holds(&steps[index], at)));
692        let chosen = match (candidates.next(), candidates.next()) {
693            (Some(only), None) => Some(only),
694            _ => None,
695        };
696        if let Some(index) = chosen {
697            earliest = index;
698            let range = ranges[index].get_or_insert(segment.range);
699            range.to = segment.range.to;
700        }
701    }
702    ranges
703}
704
705/// Which ends of the log may hold no line of a step that ran: the start of a log outlined from a later line, and the
706/// end of one cut at its cap or still growing.
707#[derive(Debug, Clone, Copy)]
708struct Ends {
709    leading: bool,
710    trailing: bool,
711}
712
713/// Where the log's blocks start: the first outlined line, each line the runner opens a step with but no group, and
714/// each top-level `Run …` group but one that follows such a line. `None` when a step's start may be missing: the
715/// outline only counted some groups or section lines, or a Docker action's step printed no header.
716fn block_starts(
717    from: u64,
718    lines: u64,
719    groups: &[LogGroup],
720    sections: &[u64],
721    saved: &SavedOutline,
722) -> Option<Vec<u64>> {
723    let headerless = groups.iter().any(|group| {
724        group.depth == 0
725            && HEADERLESS_GROUPS
726                .iter()
727                .any(|title| group.title.starts_with(title))
728    });
729    if saved.dropped > 0 || saved.sections >= SECTION_MAX || headerless {
730        return None;
731    }
732    let headers = groups
733        .iter()
734        .filter(|group| group.depth == 0 && group.title.starts_with(HEADER))
735        .map(|group| group.start)
736        .filter(|&start| start == 0 || !sections.contains(&(start - 1)));
737    let mut starts: Vec<u64> = std::iter::once(from)
738        .chain(sections.iter().copied())
739        .chain(headers)
740        .filter(|start| (from..lines).contains(start))
741        .collect();
742    starts.sort_unstable();
743    starts.dedup();
744    Some(starts)
745}
746
747/// A block of the log: the segments from one block start to the next.
748#[derive(Debug)]
749struct Block {
750    /// Its first line, and the line after the last segment with a time: lines after that no time places.
751    range: LineRange,
752    /// The earliest and latest time of its lines, when any has one.
753    times: Option<(u64, u64)>,
754}
755
756/// Each step's lines, by index into `steps`, from the blocks only one order gives it; `None` when no order fits, or a
757/// step prints no header, and the segments are attributed by time alone.
758fn by_blocks(
759    steps: &[Step],
760    segments: &[Segment],
761    starts: &[u64],
762    ends: Ends,
763) -> Option<Vec<Option<LineRange>>> {
764    if steps
765        .iter()
766        .any(|step| HEADERLESS.contains(&step.name.as_str()))
767    {
768        return None;
769    }
770    let mut blocks: Vec<Block> = Vec::new();
771    for segment in segments {
772        let opens = starts.binary_search(&segment.range.from).is_ok();
773        if opens || blocks.is_empty() {
774            blocks.push(Block {
775                range: LineRange {
776                    from: segment.range.from,
777                    to: segment.range.from,
778                },
779                times: None,
780            });
781        }
782        let block = blocks.last_mut()?;
783        for at in [segment.first, segment.last].into_iter().flatten() {
784            let (low, high) = block.times.get_or_insert((at, at));
785            *low = (*low).min(at);
786            *high = (*high).max(at);
787            block.range.to = segment.range.to;
788        }
789    }
790    // The steps that printed lines, if they ran: a skipped step prints none.
791    let ran: Vec<usize> = (0..steps.len())
792        .filter(|&index| {
793            steps[index].started_at.is_some()
794                && steps[index].conclusion.as_deref() != Some("skipped")
795        })
796        .collect();
797    let owners = Orders::new(&blocks, steps, &ran, ends)?.owners();
798    let mut ranges: Vec<Option<LineRange>> = vec![None; steps.len()];
799    for (block, owner) in blocks.iter().zip(owners) {
800        if let (Some(index), Some(_), false) = (owner, block.times, block.range.is_empty()) {
801            let range = ranges[index].get_or_insert(block.range);
802            range.to = block.range.to;
803        }
804    }
805    Some(ranges)
806}
807
808/// The ways of giving each block to a step in order: block `i` and step `k` index `blocks` and `ran`. A step that
809/// ended in success or failure printed at least one block; any other, or one before the outlined lines or after the
810/// stored ones, may have printed none here.
811struct Orders<'log> {
812    blocks: &'log [Block],
813    steps: &'log [Step],
814    ran: &'log [usize],
815    ends: Ends,
816    /// Whether blocks `..i` can go to steps `..k`, step `k` given none of them yet, by `i * (ran + 1) + k`.
817    fresh: Vec<bool>,
818    /// The same, block `i - 1` given to step `k`.
819    open: Vec<bool>,
820}
821
822impl<'log> Orders<'log> {
823    /// The ways, or `None` when there are none.
824    fn new(
825        blocks: &'log [Block],
826        steps: &'log [Step],
827        ran: &'log [usize],
828        ends: Ends,
829    ) -> Option<Orders<'log>> {
830        let cells = (blocks.len() + 1) * (ran.len() + 1);
831        let mut orders = Orders {
832            blocks,
833            steps,
834            ran,
835            ends,
836            fresh: vec![false; cells],
837            open: vec![false; cells],
838        };
839        orders.fresh[0] = true;
840        for i in 0..=blocks.len() {
841            for k in 0..ran.len() {
842                let at = orders.cell(i, k);
843                if orders.fresh[at] && orders.may_skip(i, k) {
844                    let next = orders.cell(i, k + 1);
845                    orders.fresh[next] = true;
846                }
847                if orders.open[at] {
848                    let next = orders.cell(i, k + 1);
849                    orders.fresh[next] = true;
850                }
851                if i < blocks.len() && (orders.fresh[at] || orders.open[at]) && orders.fits(i, k) {
852                    let next = orders.cell(i + 1, k);
853                    orders.open[next] = true;
854                }
855            }
856        }
857        let done = orders.cell(blocks.len(), ran.len());
858        orders.fresh[done].then_some(orders)
859    }
860
861    fn cell(&self, i: usize, k: usize) -> usize {
862        i * (self.ran.len() + 1) + k
863    }
864
865    /// Whether step `k` may have printed no block, when blocks `..i` went to the steps before it.
866    fn may_skip(&self, i: usize, k: usize) -> bool {
867        let ended = matches!(
868            self.steps[self.ran[k]].conclusion.as_deref(),
869            Some("success" | "failure")
870        );
871        !ended || (i == 0 && self.ends.leading) || (i == self.blocks.len() && self.ends.trailing)
872    }
873
874    /// Whether step `k`'s stored times hold block `i`'s; a block with no time fits any step.
875    fn fits(&self, i: usize, k: usize) -> bool {
876        let step = &self.steps[self.ran[k]];
877        self.blocks[i]
878            .times
879            .is_none_or(|(low, high)| holds(step, low) && holds(step, high))
880    }
881
882    /// The step, by index into the job's steps, that every way gives each block, if one does.
883    fn owners(&self) -> Vec<Option<usize>> {
884        let (blocks, ran) = (self.blocks.len(), self.ran.len());
885        // Whether blocks `i..` can go to steps `k..` from each state, as `fresh` and `open` are read forward.
886        let mut fresh = vec![false; self.fresh.len()];
887        let mut open = vec![false; self.open.len()];
888        let done = self.cell(blocks, ran);
889        fresh[done] = true;
890        for i in (0..=blocks).rev() {
891            for k in (0..ran).rev() {
892                let at = self.cell(i, k);
893                let next_step = fresh[self.cell(i, k + 1)];
894                let takes = i < blocks && self.fits(i, k) && open[self.cell(i + 1, k)];
895                fresh[at] = (self.may_skip(i, k) && next_step) || takes;
896                open[at] = next_step || takes;
897            }
898        }
899        (0..blocks)
900            .map(|i| {
901                let mut owners = (0..ran).filter(|&k| {
902                    let at = self.cell(i, k);
903                    (self.fresh[at] || self.open[at])
904                        && self.fits(i, k)
905                        && open[self.cell(i + 1, k)]
906                });
907                match (owners.next(), owners.next()) {
908                    (Some(only), None) => Some(self.ran[only]),
909                    _ => None,
910                }
911            })
912            .collect()
913    }
914}
915
916/// The lines below `lines` that no range holds.
917fn gaps<'range>(lines: u64, ranges: impl Iterator<Item = &'range LineRange>) -> Vec<LineRange> {
918    let mut ranges: Vec<LineRange> = ranges.copied().collect();
919    ranges.sort_unstable_by_key(|range| range.from);
920    let mut gaps = Vec::new();
921    let mut at = 0;
922    for range in ranges {
923        if range.from > at {
924            gaps.push(LineRange {
925                from: at,
926                to: range.from,
927            });
928        }
929        at = at.max(range.to);
930    }
931    if at < lines {
932        gaps.push(LineRange {
933            from: at,
934            to: lines,
935        });
936    }
937    gaps
938}
939
940/// What a failed job's log says of its failure.
941fn failure(
942    job: &Job,
943    steps: &[StepLines],
944    read: &mut dyn FnMut(LineRead) -> Vec<StoredLine>,
945) -> FailureSummary {
946    let step = job
947        .steps
948        .iter()
949        .find(|step| step.conclusion.as_deref() == Some("failure"))
950        .map(|step| step.number);
951    let range = step.and_then(|number| {
952        steps
953            .iter()
954            .find(|step| step.number == number)
955            .and_then(|step| match step.lines {
956                StepLog::Lines(range) => Some(range),
957                _ => None,
958            })
959    });
960    let last = |count: u64, range: LineRange| LineRange {
961        from: range.to.saturating_sub(count).max(range.from),
962        to: range.to,
963    };
964    let exit_code = range.and_then(|range| {
965        read_range(read, last(EXIT_SCAN, range), EXIT_PREFIX)
966            .iter()
967            .rev()
968            .map(StoredLine::styled)
969            .find_map(|line| {
970                // A line read only in part is no exit message: what was cut off may make it something else.
971                (line.kind == LineKind::Error && line.omitted == 0)
972                    .then(|| line.text())
973                    .and_then(|text| {
974                        text.strip_prefix(EXIT)?
975                            .strip_suffix('.')?
976                            .parse::<i64>()
977                            .ok()
978                    })
979            })
980    });
981    let excerpt = range.map(|range| {
982        read_range(read, last(EXCERPT, range), EXCERPT_LINE_BYTES)
983            .iter()
984            .map(StoredLine::styled)
985            .collect()
986    });
987    let shell = job
988        .record
989        .as_ref()
990        .filter(|record| matches!(record.state(), RecordState::Kept { .. }))
991        .map(|_| RecordNote::shell_command(job.summary.id));
992    FailureSummary {
993        step,
994        exit_code,
995        excerpt,
996        shell,
997    }
998}