| 1 | import type { Conclusion, Job } from "@g1t/contracts"; |
| 2 | |
| 3 | /** |
| 4 | * A run's jobs as a graph: grouped (a matrix's jobs into one node, a called |
| 5 | * workflow's jobs into a box under the job that calls it), placed in |
| 6 | * columns by how deep their `needs` go, ordered within a column so fewer |
| 7 | * connectors cross, and joined by connectors. Pure, so the run page draws |
| 8 | * it again from each refresh of its data. |
| 9 | */ |
| 10 | |
| 11 | /** What the graph reads of a job. */ |
| 12 | export type GraphJob = Pick<Job, "id" | "key" | "name" | "needs" | "status" | "conclusion" | "startedAt" | "finishedAt"> & |
| 13 | Partial<Pick<Job, "environment" | "environmentUrl" | "uses">>; |
| 14 | |
| 15 | /** Where a node or a group stands, as the status icon shows it. */ |
| 16 | export type Standing = { status: Job["status"]; conclusion: Conclusion | null }; |
| 17 | |
| 18 | /** One job; a matrix's jobs (one key, several jobs); or a job calling a workflow, with that workflow's jobs. */ |
| 19 | export type Unit = |
| 20 | | { kind: "job"; key: string; label: string; needs: string[]; job: GraphJob } |
| 21 | | { kind: "matrix"; key: string; label: string; needs: string[]; jobs: GraphJob[] } |
| 22 | | { kind: "call"; key: string; label: string; needs: string[]; uses: string | null; callers: GraphJob[]; units: Unit[] }; |
| 23 | |
| 24 | /** Sizes, in pixels. */ |
| 25 | export const GRAPH = { |
| 26 | nodeWidth: 220, |
| 27 | nodeHeight: 44, |
| 28 | /** The line a deployment's address takes. */ |
| 29 | urlHeight: 18, |
| 30 | /** A matrix's job, listed in its expanded node. */ |
| 31 | rowHeight: 32, |
| 32 | columnGap: 48, |
| 33 | rowGap: 16, |
| 34 | groupPad: 12, |
| 35 | groupHead: 32, |
| 36 | margin: 16, |
| 37 | } as const; |
| 38 | |
| 39 | /** `test` from `test (ubuntu-latest, 20)`. */ |
| 40 | export function baseName(name: string): string { |
| 41 | return name.replace(/\s*\([^()]*\)$/, "") || name; |
| 42 | } |
| 43 | |
| 44 | /** A called workflow's job by its own name: `test`, not `build / test`. */ |
| 45 | function within(name: string, parent: string | null): string { |
| 46 | return parent && name.startsWith(`${parent} / `) ? name.slice(parent.length + 3) : name; |
| 47 | } |
| 48 | |
| 49 | function unique(values: string[]): string[] { |
| 50 | return [...new Set(values)]; |
| 51 | } |
| 52 | |
| 53 | /** |
| 54 | * The run's jobs as units, in the order they were listed. A called |
| 55 | * workflow's jobs have keys under their caller's (`build/test`), and a |
| 56 | * matrix's jobs share their key. |
| 57 | */ |
| 58 | export function groupJobs(jobs: GraphJob[], prefix = "", parent: string | null = null): Unit[] { |
| 59 | const order: string[] = []; |
| 60 | const direct = new Map<string, GraphJob[]>(); |
| 61 | const nested = new Map<string, GraphJob[]>(); |
| 62 | for (const job of jobs) { |
| 63 | if (!job.key.startsWith(prefix)) continue; |
| 64 | const rest = job.key.slice(prefix.length); |
| 65 | if (!rest) continue; |
| 66 | const segment = rest.split("/")[0]!; |
| 67 | const key = prefix + segment; |
| 68 | if (!direct.has(key)) { |
| 69 | order.push(key); |
| 70 | direct.set(key, []); |
| 71 | nested.set(key, []); |
| 72 | } |
| 73 | (rest === segment ? direct : nested).get(key)!.push(job); |
| 74 | } |
| 75 | return order.map((key): Unit => { |
| 76 | const own = direct.get(key)!; |
| 77 | const inner = nested.get(key)!; |
| 78 | const needs = unique(own.flatMap((job) => job.needs)); |
| 79 | const label = own.length > 0 ? within(own.length > 1 ? baseName(own[0]!.name) : own[0]!.name, parent) : key.slice(prefix.length); |
| 80 | if (inner.length > 0 || own.some((job) => job.uses)) { |
| 81 | const callerName = own.length > 0 ? (own.length > 1 ? baseName(own[0]!.name) : own[0]!.name) : label; |
| 82 | return { |
| 83 | kind: "call", |
| 84 | key, |
| 85 | label, |
| 86 | needs, |
| 87 | uses: own.find((job) => job.uses)?.uses ?? null, |
| 88 | callers: own, |
| 89 | units: groupJobs(inner, `${key}/`, callerName), |
| 90 | }; |
| 91 | } |
| 92 | if (own.length > 1) return { kind: "matrix", key, label, needs, jobs: own }; |
| 93 | return { kind: "job", key, label, needs, job: own[0]! }; |
| 94 | }); |
| 95 | } |
| 96 | |
| 97 | /** Every job of a unit, its called workflow's included. */ |
| 98 | export function jobsOf(unit: Unit): GraphJob[] { |
| 99 | if (unit.kind === "job") return [unit.job]; |
| 100 | if (unit.kind === "matrix") return unit.jobs; |
| 101 | return [...unit.callers, ...unit.units.flatMap(jobsOf)]; |
| 102 | } |
| 103 | |
| 104 | /** Where several jobs stand together: running while any runs, else the worst way any ended. */ |
| 105 | export function standingOf(jobs: GraphJob[]): Standing { |
| 106 | if (jobs.length === 0) return { status: "waiting", conclusion: null }; |
| 107 | if (jobs.every((job) => job.status === "completed")) { |
| 108 | const ended = jobs.map((job) => job.conclusion); |
| 109 | const conclusion: Conclusion = ended.includes("failure") |
| 110 | ? "failure" |
| 111 | : ended.includes("cancelled") |
| 112 | ? "cancelled" |
| 113 | : ended.includes("success") |
| 114 | ? "success" |
| 115 | : "skipped"; |
| 116 | return { status: "completed", conclusion }; |
| 117 | } |
| 118 | const has = (status: Job["status"]) => jobs.some((job) => job.status === status); |
| 119 | if (has("in_progress") || has("calling")) return { status: "in_progress", conclusion: null }; |
| 120 | if (has("pending")) return { status: "pending", conclusion: null }; |
| 121 | if (has("queued")) return { status: "queued", conclusion: null }; |
| 122 | return { status: "waiting", conclusion: null }; |
| 123 | } |
| 124 | |
| 125 | /** A unit's standing; a called workflow's is its caller's while it has one. */ |
| 126 | export function unitStanding(unit: Unit): Standing { |
| 127 | if (unit.kind === "call" && unit.callers.length > 0) return standingOf(unit.callers); |
| 128 | return standingOf(jobsOf(unit)); |
| 129 | } |
| 130 | |
| 131 | /** |
| 132 | * Each unit's column: the longest path of `needs` from a unit needing |
| 133 | * nothing. Needs of keys not among `units` are left out, and so is a need |
| 134 | * that would close a cycle (a workflow cannot have one, but the graph does |
| 135 | * not trust that). |
| 136 | */ |
| 137 | export function columns(units: Unit[]): Map<string, number> { |
| 138 | const byKey = new Map(units.map((unit) => [unit.key, unit])); |
| 139 | const depth = new Map<string, number>(); |
| 140 | const visiting = new Set<string>(); |
| 141 | const visit = (key: string): number => { |
| 142 | const known = depth.get(key); |
| 143 | if (known !== undefined) return known; |
| 144 | if (visiting.has(key)) return -1; |
| 145 | visiting.add(key); |
| 146 | let column = 0; |
| 147 | for (const need of byKey.get(key)!.needs) { |
| 148 | if (need === key || !byKey.has(need)) continue; |
| 149 | const before = visit(need); |
| 150 | if (before >= 0) column = Math.max(column, before + 1); |
| 151 | } |
| 152 | visiting.delete(key); |
| 153 | depth.set(key, column); |
| 154 | return column; |
| 155 | }; |
| 156 | for (const unit of units) visit(unit.key); |
| 157 | return depth; |
| 158 | } |
| 159 | |
| 160 | /** The connectors of one level: from a need to what needs it, never backwards. */ |
| 161 | function links(units: Unit[], column: Map<string, number>): [string, string][] { |
| 162 | const out: [string, string][] = []; |
| 163 | for (const unit of units) |
| 164 | for (const need of unique(unit.needs)) |
| 165 | if (need !== unit.key && column.has(need) && column.get(need)! < column.get(unit.key)!) out.push([need, unit.key]); |
| 166 | return out; |
| 167 | } |
| 168 | |
| 169 | /** |
| 170 | * How many pairs of connectors cross, counting pairs that run between the |
| 171 | * same two columns. |
| 172 | */ |
| 173 | export function crossings(order: string[][], edges: [string, string][]): number { |
| 174 | const at = new Map<string, [number, number]>(); |
| 175 | order.forEach((keys, column) => keys.forEach((key, row) => at.set(key, [column, row]))); |
| 176 | let count = 0; |
| 177 | for (let i = 0; i < edges.length; i++) |
| 178 | for (let j = i + 1; j < edges.length; j++) { |
| 179 | const [a, b] = edges[i]!.map((key) => at.get(key)!); |
| 180 | const [c, d] = edges[j]!.map((key) => at.get(key)!); |
| 181 | if (a![0] !== c![0] || b![0] !== d![0]) continue; |
| 182 | if ((a![1] - c![1]) * (b![1] - d![1]) < 0) count++; |
| 183 | } |
| 184 | return count; |
| 185 | } |
| 186 | |
| 187 | /** |
| 188 | * Units per column, top to bottom: first as listed, then sorted by the |
| 189 | * mean row of what they need (sweeping right) and of what needs them |
| 190 | * (sweeping left), a few times, keeping the order with the fewest |
| 191 | * crossings. |
| 192 | */ |
| 193 | export function orderColumns(units: Unit[], column: Map<string, number>, sweeps = 4): string[][] { |
| 194 | const count = units.length === 0 ? 0 : Math.max(...column.values()) + 1; |
| 195 | let order: string[][] = Array.from({ length: count }, () => []); |
| 196 | for (const unit of units) order[column.get(unit.key)!]!.push(unit.key); |
| 197 | const edges = links(units, column); |
| 198 | const needsOf = new Map<string, string[]>(); |
| 199 | const neededBy = new Map<string, string[]>(); |
| 200 | for (const [from, to] of edges) { |
| 201 | needsOf.set(to, [...(needsOf.get(to) ?? []), from]); |
| 202 | neededBy.set(from, [...(neededBy.get(from) ?? []), to]); |
| 203 | } |
| 204 | let best = order.map((keys) => [...keys]); |
| 205 | let fewest = crossings(best, edges); |
| 206 | const rowOf = () => { |
| 207 | const rows = new Map<string, number>(); |
| 208 | order.forEach((keys) => keys.forEach((key, row) => rows.set(key, row))); |
| 209 | return rows; |
| 210 | }; |
| 211 | const sortBy = (keys: string[], others: Map<string, string[]>, rows: Map<string, number>) => { |
| 212 | const centre = (key: string, index: number) => { |
| 213 | const near = others.get(key) ?? []; |
| 214 | return near.length === 0 ? index : near.reduce((sum, other) => sum + rows.get(other)!, 0) / near.length; |
| 215 | }; |
| 216 | return keys |
| 217 | .map((key, index) => ({ key, index, at: centre(key, index) })) |
| 218 | .sort((x, y) => x.at - y.at || x.index - y.index) |
| 219 | .map(({ key }) => key); |
| 220 | }; |
| 221 | for (let sweep = 0; sweep < sweeps && fewest > 0; sweep++) { |
| 222 | const right = sweep % 2 === 0; |
| 223 | const range = right ? [...order.keys()].slice(1) : [...order.keys()].reverse().slice(1); |
| 224 | for (const index of range) order[index] = sortBy(order[index]!, right ? needsOf : neededBy, rowOf()); |
| 225 | const now = crossings(order, edges); |
| 226 | if (now < fewest) { |
| 227 | fewest = now; |
| 228 | best = order.map((keys) => [...keys]); |
| 229 | } |
| 230 | } |
| 231 | return best; |
| 232 | } |
| 233 | |
| 234 | /** A placed node: a job, or a matrix's jobs. */ |
| 235 | export type PlacedNode = { |
| 236 | unit: Extract<Unit, { kind: "job" | "matrix" }>; |
| 237 | x: number; |
| 238 | y: number; |
| 239 | w: number; |
| 240 | h: number; |
| 241 | expanded: boolean; |
| 242 | }; |
| 243 | |
| 244 | /** A placed box: a job calling a workflow, its jobs inside. */ |
| 245 | export type PlacedGroup = { unit: Extract<Unit, { kind: "call" }>; x: number; y: number; w: number; h: number }; |
| 246 | |
| 247 | /** |
| 248 | * `failed`: from a unit that failed. `active`: to a unit running now. |
| 249 | * `idle`: the rest. |
| 250 | */ |
| 251 | export type EdgeState = "idle" | "active" | "failed"; |
| 252 | export type PlacedEdge = { from: string; to: string; path: string; state: EdgeState }; |
| 253 | |
| 254 | export type GraphLayout = { width: number; height: number; nodes: PlacedNode[]; groups: PlacedGroup[]; edges: PlacedEdge[] }; |
| 255 | |
| 256 | type Level = { width: number; height: number; nodes: PlacedNode[]; groups: PlacedGroup[]; edges: PlacedEdge[] }; |
| 257 | |
| 258 | /** A job node's height: taller with a deployment's address. */ |
| 259 | function jobHeight(job: GraphJob): number { |
| 260 | return GRAPH.nodeHeight + (job.environmentUrl ? GRAPH.urlHeight : 0); |
| 261 | } |
| 262 | |
| 263 | /** The address a matrix's jobs all deploy to, when they share one. */ |
| 264 | export function sharedUrl(jobs: GraphJob[]): string | null { |
| 265 | const url = jobs[0]?.environmentUrl ?? null; |
| 266 | return url && jobs.every((job) => job.environmentUrl === url) ? url : null; |
| 267 | } |
| 268 | |
| 269 | /** A rounded right-angled connector from a node's right edge to another's left. */ |
| 270 | export function connector(x1: number, y1: number, x2: number, y2: number): string { |
| 271 | if (Math.abs(y1 - y2) < 0.5) return `M${x1} ${y1}H${x2}`; |
| 272 | // Turn in the gap before the target, so the connector leaves at its source's row. |
| 273 | const mx = Math.max(x1 + 8, x2 - GRAPH.columnGap / 2); |
| 274 | const r = Math.min(8, Math.abs(y2 - y1) / 2, mx - x1, x2 - mx); |
| 275 | const down = y2 > y1 ? 1 : -1; |
| 276 | return [ |
| 277 | `M${x1} ${y1}`, |
| 278 | `H${mx - r}`, |
| 279 | `Q${mx} ${y1} ${mx} ${y1 + down * r}`, |
| 280 | `V${y2 - down * r}`, |
| 281 | `Q${mx} ${y2} ${mx + r} ${y2}`, |
| 282 | `H${x2}`, |
| 283 | ].join(""); |
| 284 | } |
| 285 | |
| 286 | function edgeState(from: Unit, to: Unit): EdgeState { |
| 287 | const source = unitStanding(from); |
| 288 | if (source.status === "completed" && source.conclusion === "failure") return "failed"; |
| 289 | const target = unitStanding(to); |
| 290 | if (source.status === "completed" && target.status === "in_progress") return "active"; |
| 291 | return "idle"; |
| 292 | } |
| 293 | |
| 294 | function place(units: Unit[], expanded: ReadonlySet<string>, ox: number, oy: number): Level { |
| 295 | const column = columns(units); |
| 296 | const order = orderColumns(units, column); |
| 297 | const byKey = new Map(units.map((unit) => [unit.key, unit])); |
| 298 | const level: Level = { width: 0, height: 0, nodes: [], groups: [], edges: [] }; |
| 299 | // Each unit's size; a called workflow's box holds its own level. |
| 300 | const size = (unit: Unit): [number, number] => { |
| 301 | if (unit.kind === "job") return [GRAPH.nodeWidth, jobHeight(unit.job)]; |
| 302 | if (unit.kind === "matrix") |
| 303 | return [ |
| 304 | GRAPH.nodeWidth, |
| 305 | GRAPH.nodeHeight + (sharedUrl(unit.jobs) ? GRAPH.urlHeight : 0) + (expanded.has(unit.key) ? unit.jobs.length * GRAPH.rowHeight + 6 : 0), |
| 306 | ]; |
| 307 | const content = place(unit.units, expanded, 0, 0); |
| 308 | return [Math.max(GRAPH.nodeWidth, content.width) + GRAPH.groupPad * 2, GRAPH.groupHead + content.height + GRAPH.groupPad]; |
| 309 | }; |
| 310 | const sizes = new Map(units.map((unit) => [unit.key, size(unit)])); |
| 311 | const box = new Map<string, { x: number; y: number; w: number; h: number }>(); |
| 312 | let x = ox; |
| 313 | for (const keys of order) { |
| 314 | let y = oy; |
| 315 | let widest = 0; |
| 316 | for (const key of keys) { |
| 317 | const [w, h] = sizes.get(key)!; |
| 318 | box.set(key, { x, y, w, h }); |
| 319 | y += h + GRAPH.rowGap; |
| 320 | widest = Math.max(widest, w); |
| 321 | } |
| 322 | level.height = Math.max(level.height, y - GRAPH.rowGap - oy); |
| 323 | x += widest + GRAPH.columnGap; |
| 324 | } |
| 325 | level.width = Math.max(0, x - GRAPH.columnGap - ox); |
| 326 | for (const unit of units) { |
| 327 | const at = box.get(unit.key)!; |
| 328 | if (unit.kind === "call") { |
| 329 | level.groups.push({ unit, ...at }); |
| 330 | // Its jobs, moved into its box. |
| 331 | const content = place(unit.units, expanded, at.x + GRAPH.groupPad, at.y + GRAPH.groupHead); |
| 332 | level.nodes.push(...content.nodes); |
| 333 | level.groups.push(...content.groups); |
| 334 | level.edges.push(...content.edges); |
| 335 | } else { |
| 336 | level.nodes.push({ unit, ...at, expanded: unit.kind === "matrix" && expanded.has(unit.key) }); |
| 337 | } |
| 338 | } |
| 339 | for (const [from, to] of links(units, column)) { |
| 340 | const a = box.get(from)!; |
| 341 | const b = box.get(to)!; |
| 342 | // Connectors meet a node at the middle of its first line. |
| 343 | const anchor = GRAPH.nodeHeight / 2; |
| 344 | level.edges.push({ from, to, path: connector(a.x + a.w, a.y + anchor, b.x, b.y + anchor), state: edgeState(byKey.get(from)!, byKey.get(to)!) }); |
| 345 | } |
| 346 | return level; |
| 347 | } |
| 348 | |
| 349 | /** The whole graph, placed: `expanded` names the matrices shown open. */ |
| 350 | export function layoutRun(jobs: GraphJob[], expanded: ReadonlySet<string> = new Set()): GraphLayout { |
| 351 | const level = place(groupJobs(jobs), expanded, GRAPH.margin, GRAPH.margin); |
| 352 | return { |
| 353 | width: level.width + GRAPH.margin * 2, |
| 354 | height: level.height + GRAPH.margin * 2, |
| 355 | nodes: level.nodes, |
| 356 | groups: level.groups, |
| 357 | edges: level.edges, |
| 358 | }; |
| 359 | } |