1use std::collections::BTreeMap;
11
12use serde::{Deserialize, Serialize};
13
14use super::facts::outcome_of;
15use super::log::title;
16use super::{JobState, JobSummary, JobTitle, Outcome, job_title};
17
18pub const TIMELINE_DEFAULT: u64 = 24 * 3600;
20
21pub const TIMELINE_WINDOW_MAX: u64 = 7 * 24 * 3600;
23
24pub const TIMELINE_BARS_MAX: usize = 2000;
27
28#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
30pub struct TimelineQuery {
31 pub since: Option<u64>,
33 pub until: Option<u64>,
35}
36
37impl TimelineQuery {
38 pub fn window(&self, now: u64) -> Result<Span, String> {
41 let to = self.until.unwrap_or(now).min(now);
42 let from = self
43 .since
44 .unwrap_or_else(|| to.saturating_sub(TIMELINE_DEFAULT));
45 if from >= to {
46 return Err("a timeline's since is before its until".to_owned());
47 }
48 if to - from > TIMELINE_WINDOW_MAX {
49 return Err(format!(
50 "a timeline shows {} at most",
51 crate::api::duration(TIMELINE_WINDOW_MAX)
52 ));
53 }
54 Ok(Span { from, to })
55 }
56}
57
58#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
60pub struct Span {
61 pub from: u64,
63 pub to: u64,
65}
66
67#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
69#[serde(rename_all = "kebab-case", tag = "kind")]
70pub enum BarEnd {
71 At {
73 at: u64,
75 },
76 Open,
78 Unknown,
80 #[serde(other)]
82 Other,
83}
84
85impl BarEnd {
86 pub fn of_job(finished_at: Option<u64>, cleaned_at: Option<u64>, open: bool) -> BarEnd {
90 match (finished_at, open) {
91 (Some(at), _) => BarEnd::At {
92 at: cleaned_at.map_or(at, |cleaned| cleaned.min(at)),
93 },
94 (None, true) => BarEnd::Open,
95 (None, false) => BarEnd::Unknown,
96 }
97 }
98
99 pub fn at(self) -> Option<u64> {
101 match self {
102 BarEnd::At { at } => Some(at),
103 BarEnd::Open | BarEnd::Unknown | BarEnd::Other => None,
104 }
105 }
106}
107
108#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
110pub struct TimelineBar {
111 pub job: u64,
113 pub repository: String,
115 pub workflow: Option<String>,
117 pub name: String,
119 pub state: JobState,
121 pub conclusion: Option<String>,
123 pub runner_fault: bool,
125 pub queued_at: u64,
127 pub started_at: Option<u64>,
129 pub end: BarEnd,
131 pub runner: Option<String>,
133}
134
135impl TimelineBar {
136 pub fn of(job: &JobSummary) -> TimelineBar {
138 let end = BarEnd::of_job(
139 job.timeline.finished_at,
140 job.timeline.cleaned_at,
141 !job.state.is_final(),
142 );
143 TimelineBar {
144 job: job.id,
145 repository: job.repository.clone(),
146 workflow: job.workflow.clone(),
147 name: job.name.clone(),
148 state: job.state,
149 conclusion: job.conclusion.clone(),
150 runner_fault: job.runner_fault,
151 queued_at: job.timeline.queued_at,
152 started_at: job.timeline.started_at,
153 end,
154 runner: job.runner.as_ref().map(|runner| runner.name.clone()),
155 }
156 }
157
158 pub fn outcome(&self) -> Outcome {
160 outcome_of(
161 self.state,
162 self.conclusion.as_deref(),
163 self.started_at.is_some(),
164 self.runner_fault,
165 )
166 }
167
168 pub fn title(&self) -> JobTitle<'_> {
170 job_title(self.workflow.as_deref(), &self.name, Some(self.job))
171 }
172
173 pub fn end_words(&self) -> Option<&'static str> {
176 match (self.end, self.started_at) {
177 (BarEnd::At { .. }, _) => None,
178 (BarEnd::Open, Some(_)) => Some("running"),
179 (BarEnd::Open, None) => Some("waiting"),
180 (BarEnd::Unknown | BarEnd::Other, _) => Some("end unknown"),
181 }
182 }
183
184 fn begins(&self) -> u64 {
186 self.started_at.unwrap_or(self.queued_at)
187 }
188
189 pub fn overlaps(&self, window: Span, runner: Option<BarEnd>) -> bool {
194 self.queued_at < window.to
195 && match (self.end, runner) {
196 (BarEnd::At { at }, _) => at > window.from,
197 (BarEnd::Open, _) => true,
198 (BarEnd::Unknown | BarEnd::Other, Some(runner)) => {
199 runner.at().is_none_or(|at| at > window.from)
200 }
201 (BarEnd::Unknown | BarEnd::Other, None) => self.begins() >= window.from,
202 }
203 }
204}
205
206#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
209pub struct RunnerSpan {
210 pub name: String,
212 pub started_at: u64,
214 pub end: BarEnd,
216}
217
218#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
220pub struct Lane {
221 pub profile: String,
223 pub slot: usize,
225 pub bars: Vec<TimelineBar>,
227 pub runners: Vec<RunnerSpan>,
229}
230
231#[derive(Debug, Clone, Copy, PartialEq, Eq)]
233pub enum GapKind {
234 NoJob,
236 Unknown,
239}
240
241impl GapKind {
242 pub fn words(self) -> &'static str {
244 match self {
245 GapKind::NoJob => "no job",
246 GapKind::Unknown => "unknown",
247 }
248 }
249}
250
251#[derive(Debug, Clone, Copy, PartialEq, Eq)]
253pub struct Gap {
254 pub span: Span,
256 pub kind: GapKind,
258}
259
260#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
262pub struct SlotTimeline {
263 pub since: u64,
265 pub until: u64,
267 pub lanes: Vec<Lane>,
269 pub unassigned: Vec<TimelineBar>,
272 pub observed: Vec<Span>,
274 pub history_from: u64,
276 #[serde(default, skip_serializing_if = "Option::is_none")]
279 pub cut_before: Option<u64>,
280}
281
282#[derive(Debug, Clone, Default, PartialEq, Eq)]
284pub struct TimelineRows {
285 pub window: Option<Span>,
287 pub jobs: Vec<SlottedBar>,
289 pub runners: Vec<SlottedRunner>,
291 pub observed: Vec<Span>,
293 pub history_from: u64,
295}
296
297#[derive(Debug, Clone, PartialEq, Eq)]
299pub struct SlottedBar {
300 pub bar: TimelineBar,
302 pub slot: Option<SlotKey>,
304}
305
306#[derive(Debug, Clone, PartialEq, Eq)]
308pub struct SlottedRunner {
309 pub span: RunnerSpan,
311 pub slot: SlotKey,
313}
314
315#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
317pub struct SlotKey {
318 pub profile: String,
320 pub slot: usize,
322}
323
324impl SlotTimeline {
325 pub const UNASSIGNED: &'static str = "no runner here";
327
328 pub const NONE: &'static str = "no job ran or waited in this window";
330
331 pub fn cut_line(&self, now: u64) -> Option<String> {
334 let cut = self.cut_before?;
335 Some(format!(
336 "more than {TIMELINE_BARS_MAX} jobs and runners in this window: jobs that began before {} are left out",
337 crate::api::ago(cut, now)
338 ))
339 }
340
341 pub fn assemble(rows: TimelineRows) -> SlotTimeline {
344 let window = rows.window.unwrap_or(Span { from: 0, to: 0 });
345 let mut jobs = rows.jobs;
346 jobs.sort_by_key(|job| std::cmp::Reverse((job.bar.queued_at, job.bar.job)));
347 let mut runners = rows.runners;
348 runners.sort_by(|a, b| {
349 (b.span.started_at, &b.span.name).cmp(&(a.span.started_at, &a.span.name))
350 });
351 let mut cut_before = None;
352 if jobs.len() > TIMELINE_BARS_MAX {
353 jobs.truncate(TIMELINE_BARS_MAX);
354 cut_before = jobs.last().map(|job| job.bar.queued_at);
355 }
356 if runners.len() > TIMELINE_BARS_MAX {
357 runners.truncate(TIMELINE_BARS_MAX);
358 let cut = runners.last().map(|runner| runner.span.started_at);
359 cut_before = cut_before.max(cut);
360 }
361 let mut lanes: BTreeMap<SlotKey, Lane> = BTreeMap::new();
362 let mut unassigned = Vec::new();
363 for job in jobs.into_iter().rev() {
364 let mut bar = job.bar;
365 bar.name = title(&bar.name);
366 bar.workflow = bar.workflow.as_deref().map(title);
367 match job.slot {
368 Some(key) => lane(&mut lanes, key).bars.push(bar),
369 None => unassigned.push(bar),
370 }
371 }
372 for runner in runners.into_iter().rev() {
373 lane(&mut lanes, runner.slot).runners.push(runner.span);
374 }
375 for lane in lanes.values_mut() {
376 lane.bars
377 .sort_by_key(|bar| (bar.begins(), bar.queued_at, bar.job));
378 }
379 SlotTimeline {
380 since: window.from,
381 until: window.to,
382 lanes: lanes.into_values().collect(),
383 unassigned,
384 observed: rows.observed,
385 history_from: rows.history_from,
386 cut_before,
387 }
388 }
389
390 pub fn of(
393 jobs: &[JobSummary],
394 window: Span,
395 observed: Vec<Span>,
396 history_from: u64,
397 ) -> SlotTimeline {
398 let mut rows = TimelineRows {
399 window: Some(window),
400 observed,
401 history_from,
402 ..TimelineRows::default()
403 };
404 for job in jobs {
405 let bar = TimelineBar::of(job);
406 let runner_end = job.runner.as_ref().map(|_| {
408 match (job.timeline.cleaned_at, job.state.is_final()) {
409 (Some(at), _) => BarEnd::At { at },
410 (None, false) => BarEnd::Open,
411 (None, true) => BarEnd::Unknown,
412 }
413 });
414 if !bar.overlaps(window, runner_end) {
415 continue;
416 }
417 let slot = job.runner.as_ref().map(|runner| SlotKey {
418 profile: runner.profile.clone(),
419 slot: runner.slot,
420 });
421 if let (Some(runner), Some(slot), Some(end)) = (&job.runner, &slot, runner_end) {
422 let started_at = job.timeline.container_started_at.unwrap_or(bar.queued_at);
423 let up = started_at < window.to && end.at().is_none_or(|at| at > window.from);
424 if up {
425 rows.runners.push(SlottedRunner {
426 span: RunnerSpan {
427 name: runner.name.clone(),
428 started_at,
429 end,
430 },
431 slot: slot.clone(),
432 });
433 }
434 }
435 rows.jobs.push(SlottedBar { bar, slot });
436 }
437 SlotTimeline::assemble(rows)
438 }
439}
440
441impl Lane {
442 pub fn gaps(&self, timeline: &SlotTimeline) -> Vec<Gap> {
447 let window = Span {
448 from: timeline.since,
449 to: timeline.until,
450 };
451 if timeline.cut_before.is_some() {
452 return subtract(window, &self.busy(window))
453 .into_iter()
454 .map(|span| Gap {
455 span,
456 kind: GapKind::Unknown,
457 })
458 .collect();
459 }
460 let removed = |bar: &TimelineBar| {
463 self.runners
464 .iter()
465 .find(|runner| Some(&runner.name) == bar.runner.as_ref())
466 .and_then(|runner| runner.end.at())
467 };
468 let mut unsure = Vec::new();
469 for bar in &self.bars {
470 match (bar.started_at, bar.end) {
471 (Some(_), BarEnd::At { .. } | BarEnd::Open) => {}
472 (Some(from), BarEnd::Unknown | BarEnd::Other) => unsure.push(Span {
473 from,
474 to: removed(bar).unwrap_or(window.to),
475 }),
476 (None, end) => unsure.push(Span {
477 from: bar.queued_at,
478 to: end.at().unwrap_or(window.to),
479 }),
480 }
481 }
482 let mut gaps = Vec::new();
483 for free in subtract(window, &self.busy(window)) {
484 let mut known = Vec::new();
485 let watched = timeline
486 .observed
487 .iter()
488 .filter_map(|seen| clip(*seen, free));
489 for seen in watched {
490 known.extend(subtract(seen, &unsure));
491 }
492 for span in subtract(free, &known) {
493 gaps.push(Gap {
494 span,
495 kind: GapKind::Unknown,
496 });
497 }
498 gaps.extend(known.into_iter().map(|span| Gap {
499 span,
500 kind: GapKind::NoJob,
501 }));
502 }
503 gaps.sort_by_key(|gap| gap.span.from);
504 gaps
505 }
506
507 fn busy(&self, window: Span) -> Vec<Span> {
509 self.bars
510 .iter()
511 .filter_map(|bar| match (bar.started_at, bar.end) {
512 (Some(from), BarEnd::At { at }) => Some(Span { from, to: at }),
513 (Some(from), BarEnd::Open) => Some(Span {
514 from,
515 to: window.to,
516 }),
517 _ => None,
518 })
519 .collect()
520 }
521}
522
523fn clip(span: Span, within: Span) -> Option<Span> {
525 let from = span.from.max(within.from);
526 let to = span.to.min(within.to);
527 (from < to).then_some(Span { from, to })
528}
529
530fn subtract(span: Span, taken: &[Span]) -> Vec<Span> {
532 let mut taken: Vec<Span> = taken.iter().filter_map(|part| clip(*part, span)).collect();
533 taken.sort_by_key(|part| part.from);
534 let mut left = Vec::new();
535 let mut from = span.from;
536 for part in taken {
537 if part.from > from {
538 left.push(Span {
539 from,
540 to: part.from,
541 });
542 }
543 from = from.max(part.to);
544 }
545 if from < span.to {
546 left.push(Span { from, to: span.to });
547 }
548 left
549}
550
551fn lane(lanes: &mut BTreeMap<SlotKey, Lane>, key: SlotKey) -> &mut Lane {
553 lanes.entry(key).or_insert_with_key(|key| Lane {
554 profile: key.profile.clone(),
555 slot: key.slot,
556 bars: Vec::new(),
557 runners: Vec::new(),
558 })
559}
560
561#[cfg(test)]
563#[cfg(any(feature = "host", feature = "client"))]
564mod tests;