| 1 | /** |
| 2 | * `strategy.matrix` expansion with GitHub's include/exclude semantics |
| 3 | * (https://docs.github.com/en/actions/writing-workflows/choosing-what-your-workflow-does/running-variations-of-jobs-in-a-workflow). |
| 4 | */ |
| 5 | import { evaluateValue, type ExprContext } from "./expr/evaluate.js"; |
| 6 | |
| 7 | export type MatrixCombination = Record<string, unknown>; |
| 8 | |
| 9 | export class MatrixError extends Error { |
| 10 | constructor(message: string) { |
| 11 | super(message); |
| 12 | this.name = "MatrixError"; |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | const isPlainObject = (v: unknown): v is Record<string, unknown> => |
| 17 | typeof v === "object" && v !== null && !Array.isArray(v); |
| 18 | |
| 19 | function scalarEqual(a: unknown, b: unknown): boolean { |
| 20 | if (a === b) return true; |
| 21 | if (a === null || b === null || a === undefined || b === undefined) return false; |
| 22 | if (typeof a === "object" || typeof b === "object") return false; |
| 23 | return String(a) === String(b); |
| 24 | } |
| 25 | |
| 26 | /** Deep equality (scalars compared by string form so `18` equals `'18'`). */ |
| 27 | export function deepEqual(a: unknown, b: unknown): boolean { |
| 28 | if (Array.isArray(a) || Array.isArray(b)) { |
| 29 | if (!Array.isArray(a) || !Array.isArray(b) || a.length !== b.length) return false; |
| 30 | return a.every((v, i) => deepEqual(v, b[i])); |
| 31 | } |
| 32 | if (isPlainObject(a) || isPlainObject(b)) { |
| 33 | if (!isPlainObject(a) || !isPlainObject(b)) return false; |
| 34 | const ka = Object.keys(a); |
| 35 | if (ka.length !== Object.keys(b).length) return false; |
| 36 | return ka.every((k) => Object.prototype.hasOwnProperty.call(b, k) && deepEqual(a[k], b[k])); |
| 37 | } |
| 38 | return scalarEqual(a, b); |
| 39 | } |
| 40 | |
| 41 | /** `pattern` partially matches `value`: every key of a pattern object matches (recursively). */ |
| 42 | function partialMatch(pattern: unknown, value: unknown): boolean { |
| 43 | if (isPlainObject(pattern) && isPlainObject(value)) { |
| 44 | return Object.keys(pattern).every((k) => Object.prototype.hasOwnProperty.call(value, k) && partialMatch(pattern[k], value[k])); |
| 45 | } |
| 46 | return deepEqual(pattern, value); |
| 47 | } |
| 48 | |
| 49 | function resolve(value: unknown, ctx: ExprContext | undefined): unknown { |
| 50 | return typeof value === "string" && value.includes("${{") ? evaluateValue(value, ctx ?? {}) : value; |
| 51 | } |
| 52 | |
| 53 | function asObjectList(value: unknown, what: string): Array<Record<string, unknown>> { |
| 54 | if (value === undefined || value === null) return []; |
| 55 | if (isPlainObject(value)) return [value]; |
| 56 | if (!Array.isArray(value)) throw new MatrixError(`matrix.${what} must be a list of mappings`); |
| 57 | return value.map((entry, i) => { |
| 58 | if (!isPlainObject(entry)) throw new MatrixError(`matrix.${what}[${i}] must be a mapping`); |
| 59 | return entry; |
| 60 | }); |
| 61 | } |
| 62 | |
| 63 | /** |
| 64 | * Expands a matrix into its job combinations. |
| 65 | * |
| 66 | * - `undefined`/`null` (no matrix) yields a single empty combination `[{}]`. |
| 67 | * - The matrix (or any of its vectors, `include` or `exclude`) may be a |
| 68 | * `${{ }}` expression string, evaluated with `ctx` (e.g. `fromJSON(needs.x.outputs.m)`). |
| 69 | * - Exclusions are applied first (partial matches exclude). |
| 70 | * - Each `include` entry is merged into every original combination whose |
| 71 | * original matrix values it does not overwrite (values added by earlier |
| 72 | * includes may be overwritten); if it fits none, it becomes a new combination. |
| 73 | */ |
| 74 | /** Combinations before `exclude`, and entries in `include` or `exclude`: these bound the work of expanding a matrix. */ |
| 75 | export const MAX_MATRIX_COMBINATIONS = 4096; |
| 76 | export const MAX_MATRIX_ENTRIES = 256; |
| 77 | |
| 78 | export function expandMatrix(matrix: unknown, ctx?: ExprContext): MatrixCombination[] { |
| 79 | if (matrix === undefined || matrix === null) return [{}]; |
| 80 | const resolved = resolve(matrix, ctx); |
| 81 | if (resolved === undefined || resolved === null || resolved === "") return [{}]; |
| 82 | if (!isPlainObject(resolved)) throw new MatrixError("matrix must be a mapping"); |
| 83 | |
| 84 | const dims: Array<[string, unknown[]]> = []; |
| 85 | let include: Array<Record<string, unknown>> = []; |
| 86 | let exclude: Array<Record<string, unknown>> = []; |
| 87 | for (const [key, raw] of Object.entries(resolved)) { |
| 88 | const value = resolve(raw, ctx); |
| 89 | if (key === "include") include = asObjectList(value, "include"); |
| 90 | else if (key === "exclude") exclude = asObjectList(value, "exclude"); |
| 91 | else { |
| 92 | if (!Array.isArray(value)) throw new MatrixError(`matrix.${key} must be a list (got ${value === null ? "null" : typeof value})`); |
| 93 | dims.push([key, value]); |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | for (const [what, list] of [["include", include], ["exclude", exclude]] as const) { |
| 98 | if (list.length > MAX_MATRIX_ENTRIES) throw new MatrixError(`matrix.${what} has ${list.length} entries; at most ${MAX_MATRIX_ENTRIES} are allowed`); |
| 99 | } |
| 100 | // Count the combinations before building any, so a matrix like 20 values in each of 6 vectors |
| 101 | // (64 million) is refused at once instead of filling memory. |
| 102 | const product = dims.reduce((n, [, values]) => n * values.length, dims.length ? 1 : 0); |
| 103 | if (product > MAX_MATRIX_COMBINATIONS) throw new MatrixError(`the matrix has ${product} combinations before exclusions; at most ${MAX_MATRIX_COMBINATIONS} are allowed (and a matrix may produce at most 256 jobs)`); |
| 104 | |
| 105 | let combos: MatrixCombination[] = []; |
| 106 | if (dims.length > 0) { |
| 107 | combos = [{}]; |
| 108 | for (const [key, values] of dims) { |
| 109 | const next: MatrixCombination[] = []; |
| 110 | for (const combo of combos) for (const v of values) next.push({ ...combo, [key]: v }); |
| 111 | combos = next; |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | combos = combos.filter((combo) => !exclude.some((ex) => Object.keys(ex).every((k) => k in combo && partialMatch(ex[k], combo[k])))); |
| 116 | |
| 117 | const originalKeys = new Set(dims.map(([k]) => k)); |
| 118 | const extra: MatrixCombination[] = []; |
| 119 | for (const entry of include) { |
| 120 | let added = false; |
| 121 | for (const combo of combos) { |
| 122 | const fits = Object.keys(entry).every((k) => !originalKeys.has(k) || deepEqual(combo[k], entry[k])); |
| 123 | if (fits) { |
| 124 | // Original vector values are never overwritten; values added by earlier includes may be. |
| 125 | for (const [k, v] of Object.entries(entry)) if (!originalKeys.has(k)) combo[k] = v; |
| 126 | added = true; |
| 127 | } |
| 128 | } |
| 129 | if (!added) extra.push({ ...entry }); |
| 130 | } |
| 131 | return [...combos, ...extra]; |
| 132 | } |