1// SPDX-License-Identifier: MIT
2
3package workflow
4
5import (
6 "context"
7 "errors"
8 "fmt"
9 "strings"
10
11 "bnema.dev/ermite-actions/expr"
12)
13
14// Limits of matrix expansion. GitHub only limits the number of jobs; the
15// other limits keep the work done for a hostile matrix bounded.
16const (
17 // MaxMatrixJobs is the number of jobs a matrix may produce.
18 MaxMatrixJobs = 256
19 // MaxMatrixProduct is the size of the cross product of the vectors, before
20 // exclusions, above which a matrix is refused.
21 MaxMatrixProduct = 1 << 16
22 // MaxMatrixEntries is the number of entries of include and, separately,
23 // of exclude.
24 MaxMatrixEntries = 256
25)
26
27// checkEvery is the number of combinations between two checks of the context.
28const checkEvery = 1024
29
30// MatrixCombo is one job of a matrix.
31type MatrixCombo struct {
32 // Values is the "matrix" context of the job: the vector values in the
33 // order of the keys, then the keys added by include entries in the order
34 // they were first added.
35 Values *expr.Dictionary
36 // Segments are the scalar values of Values, in order, shown in the name
37 // of the job: "build (ubuntu-latest, 14)". Null and the empty string are
38 // left out, as recorded (matrix-edge-values); arrays and mappings are
39 // left out too, which is assumed.
40 Segments []string
41}
42
43// DisplayName returns the name of the job: base alone when there are no
44// segments, else base followed by the segments in parentheses.
45func (c MatrixCombo) DisplayName(base string) string {
46 if len(c.Segments) == 0 {
47 return base
48 }
49 return base + " (" + strings.Join(c.Segments, ", ") + ")"
50}
51
52// ExpandMatrix expands the matrix of an evaluated strategy (a dictionary with
53// the optional keys "matrix", "fail-fast" and "max-parallel", or null) into
54// the job combinations, like GitHub:
55//
56// - the combinations are the cross product of the vectors, the first key
57// varying slowest;
58// - exclude removes every combination that contains all the key-value
59// pairs of one of its entries; every key of an entry must be a vector of
60// the matrix, or the matrix is an error that matches
61// [ErrExcludeUnknownKey];
62// - then each include entry is added to every remaining combination whose
63// values for the vector keys it mentions are equal (an entry that
64// mentions no vector key matches all), without overwriting the original
65// values; an entry that matches no combination becomes a combination of
66// its own;
67// - more than 256 jobs is an error. A strategy without a matrix gives a
68// single combination.
69//
70// The work is bounded: the product of the vectors may not exceed
71// [MaxMatrixProduct], include and exclude may have [MaxMatrixEntries] entries
72// each, and ctx is checked every few thousand combinations.
73//
74// What github.com settled. Recorded (matrix-edge-values): null and the empty
75// string are left out of the default job name. For matrix-edge-values (exclude key not
76// in the matrix) and matrix-over-256 the recordings hold only a failed run
77// with no job: the wording of the two errors below, and the unknown exclude
78// key being reported once per offending entry, were observed on the github.com
79// run page, not in the recordings. Still assumed, from the documented
80// semantics of include and exclude: the order of the cross product (first key
81// slowest), the display name listing every scalar value including those
82// added by include (see [MatrixCombo.DisplayName]), the comparison of values
83// (same kind, strings compared exactly, mappings by containment), an include
84// key matching a vector key case-insensitively, the error when every
85// combination is excluded, the other limits above, and the wording of the
86// other errors.
87func ExpandMatrix(ctx context.Context, strategy expr.Value) ([]MatrixCombo, error) {
88 s, err := ParseStrategy(ctx, strategy)
89 if err != nil {
90 return nil, err
91 }
92 return s.Combos, nil
93}
94
95func buildMatrix(ctx context.Context, m expr.Value) ([]MatrixCombo, bool, error) {
96 switch m.(type) {
97 case nil, expr.Null:
98 return []MatrixCombo{{Values: expr.NewDictionary()}}, false, nil
99 }
100 md, ok := m.(*expr.Dictionary)
101 if !ok {
102 return nil, false, errors.New("the matrix must be a mapping")
103 }
104 if md == nil {
105 return []MatrixCombo{{Values: expr.NewDictionary()}}, false, nil
106 }
107 var vecs []vector
108 var includes, excludes []*expr.Dictionary
109 for _, p := range md.Pairs() {
110 switch p.Key {
111 case "include":
112 list, err := matrixEntries("include", p.Value)
113 if err != nil {
114 return nil, false, err
115 }
116 includes = list
117 case "exclude":
118 list, err := matrixEntries("exclude", p.Value)
119 if err != nil {
120 return nil, false, err
121 }
122 excludes = list
123 default:
124 arr, ok := p.Value.(*expr.Array)
125 if !ok || arr == nil || arr.Len() == 0 {
126 return nil, false, fmt.Errorf("matrix vector '%s' does not contain any values", p.Key)
127 }
128 if arr.Len() > MaxMatrixProduct {
129 return nil, false, errProductTooBig
130 }
131 vecs = append(vecs, vector{key: p.Key, items: arr.Items()})
132 }
133 }
134 return expand(ctx, vecs, includes, excludes)
135}
136
137func matrixEntries(name string, v expr.Value) ([]*expr.Dictionary, error) {
138 arr, ok := v.(*expr.Array)
139 if !ok || arr == nil {
140 return nil, fmt.Errorf("matrix %s must be a sequence of mappings", name)
141 }
142 if arr.Len() > MaxMatrixEntries {
143 return nil, fmt.Errorf("matrix %s has more than %d entries", name, MaxMatrixEntries)
144 }
145 var out []*expr.Dictionary
146 for _, it := range arr.Items() {
147 d, ok := it.(*expr.Dictionary)
148 if !ok || d == nil {
149 return nil, fmt.Errorf("matrix %s must be a sequence of mappings", name)
150 }
151 out = append(out, d)
152 }
153 return out, nil
154}
155
156// ErrExcludeUnknownKey is matched, with [errors.Is], by the error that
157// [ExpandMatrix], [ParseStrategy] and [Job.EvaluateStrategy] return when an
158// entry of "exclude" names a key that is not a vector of the matrix (keys
159// that only "include" adds do not count). GitHub refuses such a workflow as
160// invalid, before any job exists, and names the run after the file path
161// rather than after the "name:" key (recorded: matrix-edge-values,
162// a-exclude-unknown-key.yml). The error carries one line per offending
163// entry; when several entries offend, errors.Is still holds.
164var ErrExcludeUnknownKey = errors.New("matrix exclude key does not match any key within the matrix")
165
166// excludeKeyError is the error for one exclude entry with an unknown key.
167type excludeKeyError struct {
168 // Key is the first unknown key of the entry.
169 Key string
170}
171
172// Unwrap makes errors.Is(err, [ErrExcludeUnknownKey]) hold.
173func (e *excludeKeyError) Unwrap() error { return ErrExcludeUnknownKey }
174
175func (e *excludeKeyError) Error() string {
176 return fmt.Sprintf("Matrix exclude key '%s' does not match any key within the matrix", e.Key)
177}
178
179// errProductTooBig is returned when the cross product of the vectors is too
180// large to be enumerated. GitHub would count the configurations left after
181// the exclusions; this limit keeps the work bounded, see [MaxMatrixProduct].
182var errProductTooBig = fmt.Errorf("matrix too large: the cross product of the vectors exceeds %d combinations", MaxMatrixProduct)
183
184// ErrTooManyConfigurations is matched, with [errors.Is], by the error that
185// [ExpandMatrix], [ParseStrategy] and [Job.EvaluateStrategy] return when a
186// matrix produces more than [MaxMatrixJobs] configurations. The error itself
187// carries the job and the count in its text. It does not match the error for a
188// cross product over [MaxMatrixProduct], which is a work bound of this package
189// rather than a GitHub rule.
190var ErrTooManyConfigurations = errors.New("matrix produces too many configurations")
191
192// configurationLimitError is returned when a matrix produces more than
193// [MaxMatrixJobs] configurations. Its text is the one observed on the
194// github.com run page for matrix-over-256 (not in the recordings, which only
195// hold the failed run): "Strategy for job 'too-many' produced 272
196// configurations which exceeds the maximum of 256 configurations". Job is
197// empty when the matrix was expanded without a job, see
198// [Job.EvaluateStrategy].
199type configurationLimitError struct {
200 // Job is the id of the job.
201 Job string
202 // Count is the number of configurations the matrix produces.
203 Count int
204}
205
206// Unwrap makes errors.Is(err, [ErrTooManyConfigurations]) hold.
207func (e *configurationLimitError) Unwrap() error { return ErrTooManyConfigurations }
208
209func (e *configurationLimitError) Error() string {
210 subject := "Strategy"
211 if e.Job != "" {
212 subject = fmt.Sprintf("Strategy for job '%s'", e.Job)
213 }
214 return fmt.Sprintf("%s produced %d configurations which exceeds the maximum of %d configurations", subject, e.Count, MaxMatrixJobs)
215}
216
217type vector struct {
218 key string
219 items []expr.Value
220}
221
222// condition says which items of vector key may appear in a combination that
223// an exclude or include entry applies to.
224type condition struct {
225 vec int
226 ok []bool // by index of the item in the vector
227}
228
229type includeEntry struct {
230 conds []condition
231 extra []expr.Pair // pairs whose key is not a vector
232}
233
234func compileCondition(vecs []vector, vi int, want expr.Value) condition {
235 c := condition{vec: vi, ok: make([]bool, len(vecs[vi].items))}
236 for i, it := range vecs[vi].items {
237 c.ok[i] = valuesMatch(it, want)
238 }
239 return c
240}
241
242func expand(ctx context.Context, vecs []vector, includes, excludes []*expr.Dictionary) ([]MatrixCombo, bool, error) {
243 index := make(map[string]int, len(vecs))
244 for i, v := range vecs {
245 index[strings.ToLower(v.key)] = i
246 }
247 // Exclude entries become lists of conditions on item positions, so that
248 // testing a combination costs a few array reads.
249 var excl [][]condition
250 var bad []error
251 for _, ex := range excludes {
252 var conds []condition
253 unknown := false
254 for _, p := range ex.Pairs() {
255 vi, ok := index[strings.ToLower(p.Key)]
256 if !ok {
257 // One error per offending entry, for its first unknown key.
258 bad = append(bad, &excludeKeyError{Key: p.Key})
259 unknown = true
260 break
261 }
262 conds = append(conds, compileCondition(vecs, vi, p.Value))
263 }
264 if len(conds) > 0 && !unknown {
265 excl = append(excl, conds)
266 }
267 }
268 if len(bad) > 0 {
269 return nil, false, errors.Join(bad...)
270 }
271 incl := make([]includeEntry, len(includes))
272 for n, inc := range includes {
273 for _, p := range inc.Pairs() {
274 if vi, ok := index[strings.ToLower(p.Key)]; ok {
275 incl[n].conds = append(incl[n].conds, compileCondition(vecs, vi, p.Value))
276 } else {
277 incl[n].extra = append(incl[n].extra, p)
278 }
279 }
280 }
281
282 // total counts every configuration, so that the error of a matrix over the
283 // limit tells how many it produces; only the first MaxMatrixJobs are built.
284 var combos []MatrixCombo
285 total := 0
286 matched := make([]bool, len(includes))
287 if len(vecs) > 0 {
288 product := 1
289 for _, v := range vecs {
290 product *= len(v.items)
291 if product > MaxMatrixProduct {
292 return nil, false, errProductTooBig
293 }
294 }
295 tuple := make([]int, len(vecs))
296 next:
297 for i := 0; i < product; i++ {
298 if i%checkEvery == 0 {
299 if err := ctx.Err(); err != nil {
300 return nil, false, err
301 }
302 }
303 if i > 0 {
304 // Advance the last position first: the first key varies slowest.
305 for k := len(tuple) - 1; k >= 0; k-- {
306 tuple[k]++
307 if tuple[k] < len(vecs[k].items) {
308 break
309 }
310 tuple[k] = 0
311 }
312 }
313 for _, conds := range excl {
314 if allHold(conds, tuple) {
315 continue next
316 }
317 }
318 total++
319 build := total <= MaxMatrixJobs
320 var b *comboBuilder
321 if build {
322 b = &comboBuilder{vals: map[string]expr.Value{}}
323 for k, v := range vecs {
324 b.set(v.key, v.items[tuple[k]])
325 }
326 }
327 for n, inc := range incl {
328 if !allHold(inc.conds, tuple) {
329 continue
330 }
331 matched[n] = true
332 if build {
333 for _, p := range inc.extra {
334 b.set(p.Key, p.Value)
335 }
336 }
337 }
338 if build {
339 combos = append(combos, b.combo())
340 }
341 }
342 }
343 for n, inc := range includes {
344 if matched[n] {
345 continue
346 }
347 total++
348 if total > MaxMatrixJobs {
349 continue
350 }
351 b := &comboBuilder{vals: map[string]expr.Value{}}
352 for _, p := range inc.Pairs() {
353 b.set(p.Key, p.Value)
354 }
355 combos = append(combos, b.combo())
356 }
357 if total > MaxMatrixJobs {
358 return nil, false, &configurationLimitError{Count: total}
359 }
360 if len(combos) == 0 {
361 if len(vecs) == 0 && len(includes) == 0 && len(excludes) == 0 {
362 // An empty matrix runs the job once.
363 return []MatrixCombo{{Values: expr.NewDictionary()}}, true, nil
364 }
365 // TODO(verify with recording): GitHub's behaviour when every
366 // combination is excluded.
367 return nil, false, errors.New("the matrix has no combinations: all of them are excluded")
368 }
369 return combos, true, nil
370}
371
372func allHold(conds []condition, tuple []int) bool {
373 for _, c := range conds {
374 if !c.ok[tuple[c.vec]] {
375 return false
376 }
377 }
378 return true
379}
380
381// comboBuilder holds the values of one combination while includes are
382// applied; added values may be overwritten by later includes, original ones
383// never are (an include's vector keys are conditions, not assignments).
384type comboBuilder struct {
385 keys []string
386 vals map[string]expr.Value // by lower-cased key
387}
388
389func (b *comboBuilder) set(key string, v expr.Value) {
390 lk := strings.ToLower(key)
391 if _, ok := b.vals[lk]; !ok {
392 b.keys = append(b.keys, key)
393 }
394 b.vals[lk] = v
395}
396
397func (b *comboBuilder) combo() MatrixCombo {
398 d := expr.NewDictionary()
399 var segs []string
400 for _, k := range b.keys {
401 v := b.vals[strings.ToLower(k)]
402 d.Add(k, v)
403 if s, ok := segment(v); ok {
404 segs = append(segs, s)
405 }
406 }
407 return MatrixCombo{Values: d, Segments: segs}
408}
409
410// valuesMatch compares a matrix value with the value in an include or
411// exclude entry: scalars of the same kind and value are equal, arrays must be
412// equal element by element, and a mapping in the entry must be contained in
413// the matrix value.
414func valuesMatch(have, want expr.Value) bool {
415 if kindName(have) != kindName(want) {
416 return false
417 }
418 switch w := want.(type) {
419 case expr.Null:
420 return true
421 case expr.Boolean:
422 return have.(expr.Boolean) == w
423 case expr.Number:
424 return have.(expr.Number) == w
425 case expr.String:
426 return have.(expr.String) == w
427 case *expr.Array:
428 h := have.(*expr.Array)
429 if h.Len() != w.Len() {
430 return false
431 }
432 for i := 0; i < w.Len(); i++ {
433 if !valuesMatch(h.At(i), w.At(i)) {
434 return false
435 }
436 }
437 return true
438 case *expr.Dictionary:
439 h := have.(*expr.Dictionary)
440 for _, p := range w.Pairs() {
441 hv, ok := h.Get(p.Key)
442 if !ok || !valuesMatch(hv, p.Value) {
443 return false
444 }
445 }
446 return true
447 }
448 return false
449}
450
451// segment is the text a matrix value adds to the name of a job. Null and the
452// empty string add nothing, numbers and booleans are shown as in an
453// expression ("1.5", "true"); all recorded (matrix-edge-values:
454// "default-name", "two-axes (x)"). Arrays and mappings add nothing: assumed,
455// not recorded.
456func segment(v expr.Value) (string, bool) {
457 switch v.(type) {
458 case nil, expr.Null, *expr.Array, *expr.Dictionary:
459 return "", false
460 }
461 s := expr.CoerceString(v)
462 return s, s != ""
463}