1 Set-StrictMode -Version "4.0"
2
3 class MatrixConfig {
4 [PSCustomObject]$displayNames
5 [Hashtable]$displayNamesLookup
6 [PSCustomObject]$matrix
7 [MatrixParameter[]]$matrixParameters
8 [Array]$include
9 [Array]$exclude
10 }
11
12 class MatrixParameter {
13 MatrixParameter([String]$name, [System.Object]$value) {
14 $this.Value = $value
15 $this.Name = $name
16 }
17
18 [System.Object]$Value
19 [System.Object]$Name
20
21 Set($value, [String]$keyRegex = '')
22 {
23 if ($this.Value -is [PSCustomObject]) {
24 $set = $false
25 foreach ($prop in $this.Value.PSObject.Properties) {
26 if ($prop.Name -match $keyRegex) {
27 $prop.Value = $value
28 $set = $true
29 break
30 }
31 }
32 if (!$set) {
33 throw "Property `"$keyRegex`" does not exist for MatrixParameter."
34 }
35 } else {
36 $this.Value = $value
37 }
38 }
39
40 [System.Object]Flatten()
41 {
42 if ($this.Value -is [PSCustomObject]) {
43 return $this.Value.PSObject.Properties | ForEach-Object {
44 [MatrixParameter]::new($_.Name, $_.Value)
45 }
46 } elseif ($this.Value -is [Array]) {
47 return $this.Value | ForEach-Object {
48 [MatrixParameter]::new($this.Name, $_)
49 }
50 } else {
51 return $this
52 }
53 }
54
55 [Int]Length()
56 {
57 if ($this.Value -is [PSCustomObject]) {
58 return ($this.Value.PSObject.Properties | Measure-Object).Count
59 } elseif ($this.Value -is [Array]) {
60 return $this.Value.Length
61 } else {
62 return 1
63 }
64 }
65
66 [String]CreateDisplayName([Hashtable]$displayNamesLookup)
67 {
68 $displayName = $this.Value.ToString()
69 if ($this.Value -is [PSCustomObject]) {
70 $displayName = $this.Name
71 }
72
73 if ($displayNamesLookup.ContainsKey($displayName)) {
74 $displayName = $displayNamesLookup[$displayName]
75 }
76
77 # Matrix naming restrictions:
78 # https://docs.microsoft.com/en-us/azure/devops/pipelines/process/phases?view=azure-devops&tabs=yaml#multi-job-configuration
79 $displayName = $displayName -replace "[^A-Za-z0-9_]", ""
80 return $displayName
81 }
82 }
83
84 $IMPORT_KEYWORD = '$IMPORT'
85
GenerateMatrix([MatrixConfig] $config, [String] $selectFromMatrixType, [String] $displayNameFilter = '...', [Array] $filters = (), [Array] $replace = (), [Array] $nonSparseParameters = ())86 function GenerateMatrix(
87 [MatrixConfig]$config,
88 [String]$selectFromMatrixType,
89 [String]$displayNameFilter = ".*",
90 [Array]$filters = @(),
91 [Array]$replace = @(),
92 [Array]$nonSparseParameters = @()
93 ) {
94 $matrixParameters, $importedMatrix, $combinedDisplayNameLookup = ProcessImport $config.matrixParameters $selectFromMatrixType $config.displayNamesLookup
95 if ($selectFromMatrixType -eq "sparse") {
96 $matrix = GenerateSparseMatrix $matrixParameters $config.displayNamesLookup $nonSparseParameters
97 } elseif ($selectFromMatrixType -eq "all") {
98 $matrix = GenerateFullMatrix $matrixParameters $config.displayNamesLookup
99 } else {
100 throw "Matrix generator not implemented for selectFromMatrixType: $($platform.selectFromMatrixType)"
101 }
102
103 # Combine with imported after matrix generation, since a sparse selection should result in a full combination of the
104 # top level and imported sparse matrices (as opposed to a sparse selection of both matrices).
105 if ($importedMatrix) {
106 $matrix = CombineMatrices $matrix $importedMatrix $combinedDisplayNameLookup
107 }
108 if ($config.exclude) {
109 $matrix = ProcessExcludes $matrix $config.exclude
110 }
111 if ($config.include) {
112 $matrix = ProcessIncludes $config $matrix $selectFromMatrixType
113 }
114
115 $matrix = FilterMatrix $matrix $filters
116 $matrix = ProcessReplace $matrix $replace $config.displayNamesLookup
117 $matrix = FilterMatrixDisplayName $matrix $displayNameFilter
118 return $matrix
119 }
120
ProcessNonSparseParameters([MatrixParameter[]] $parameters, [Array] $nonSparseParameters)121 function ProcessNonSparseParameters(
122 [MatrixParameter[]]$parameters,
123 [Array]$nonSparseParameters
124 ) {
125 if (!$nonSparseParameters) {
126 return $parameters, $null
127 }
128
129 $sparse = [MatrixParameter[]]@()
130 $nonSparse = [MatrixParameter[]]@()
131
132 foreach ($param in $parameters) {
133 if ($param.Name -in $nonSparseParameters) {
134 $nonSparse += $param
135 } else {
136 $sparse += $param
137 }
138 }
139
140 return $sparse, $nonSparse
141 }
142
FilterMatrixDisplayName([array] $matrix, [string] $filter)143 function FilterMatrixDisplayName([array]$matrix, [string]$filter) {
144 return $matrix | Where-Object { $_ } | ForEach-Object {
145 if ($_.Name -match $filter) {
146 return $_
147 }
148 }
149 }
150
151 # Filters take the format of key=valueregex,key2=valueregex2
FilterMatrix([array] $matrix, [array] $filters)152 function FilterMatrix([array]$matrix, [array]$filters) {
153 $matrix = $matrix | ForEach-Object {
154 if (MatchesFilters $_ $filters) {
155 return $_
156 }
157 }
158 return $matrix
159 }
160
MatchesFilters([hashtable] $entry, [array] $filters)161 function MatchesFilters([hashtable]$entry, [array]$filters) {
162 foreach ($filter in $filters) {
163 $key, $regex = ParseFilter $filter
164 # Default all regex checks to go against empty string when keys are missing.
165 # This simplifies the filter syntax/interface to be regex only.
166 $value = ""
167 if ($null -ne $entry -and $entry.parameters.Contains($key)) {
168 $value = $entry.parameters[$key]
169 }
170 if ($value -notmatch $regex) {
171 return $false
172 }
173 }
174
175 return $true
176 }
177
ParseFilter([string]$filter)178 function ParseFilter([string]$filter) {
179 # Lazy match key in case value contains '='
180 if ($filter -match "(.+?)=(.+)") {
181 $key = $matches[1]
182 $regex = $matches[2]
183 return $key, $regex
184 } else {
185 throw "Invalid filter: `"${filter}`", expected <key>=<regex> format"
186 }
187 }
188
189 # Importing the JSON as PSCustomObject preserves key ordering,
190 # whereas ConvertFrom-Json -AsHashtable does not
GetMatrixConfigFromJson([String]$jsonConfig)191 function GetMatrixConfigFromJson([String]$jsonConfig)
192 {
193 [MatrixConfig]$config = $jsonConfig | ConvertFrom-Json
194 $config.matrixParameters = @()
195 $config.displayNamesLookup = @{}
196 $include = [MatrixParameter[]]@()
197 $exclude = [MatrixParameter[]]@()
198
199 if ($null -ne $config.displayNames) {
200 $config.displayNames.PSObject.Properties | ForEach-Object {
201 $config.displayNamesLookup.Add($_.Name, $_.Value)
202 }
203 }
204 if ($null -ne $config.matrix) {
205 $config.matrixParameters = PsObjectToMatrixParameterArray $config.matrix
206 }
207 foreach ($includeMatrix in $config.include) {
208 $include += ,@(PsObjectToMatrixParameterArray $includeMatrix)
209 }
210 foreach ($excludeMatrix in $config.exclude) {
211 $exclude += ,@(PsObjectToMatrixParameterArray $excludeMatrix)
212 }
213
214 $config.include = $include
215 $config.exclude = $exclude
216
217 return $config
218 }
219
PsObjectToMatrixParameterArray([PSCustomObject]$obj)220 function PsObjectToMatrixParameterArray([PSCustomObject]$obj)
221 {
222 if ($obj -eq $null) {
223 return $null
224 }
225 return $obj.PSObject.Properties | ForEach-Object {
226 [MatrixParameter]::new($_.Name, $_.Value)
227 }
228 }
229
ProcessExcludes([Array]$matrix, [Array]$excludes)230 function ProcessExcludes([Array]$matrix, [Array]$excludes)
231 {
232 $deleteKey = "%DELETE%"
233 $exclusionMatrix = @()
234
235 foreach ($exclusion in $excludes) {
236 $full = GenerateFullMatrix $exclusion
237 $exclusionMatrix += $full
238 }
239
240 foreach ($element in $matrix) {
241 foreach ($exclusion in $exclusionMatrix) {
242 $match = MatrixElementMatch $element.parameters $exclusion.parameters
243 if ($match) {
244 $element.parameters[$deleteKey] = $true
245 }
246 }
247 }
248
249 return $matrix | Where-Object { !$_.parameters.Contains($deleteKey) }
250 }
251
ProcessIncludes([MatrixConfig] $config, [Array] $matrix)252 function ProcessIncludes([MatrixConfig]$config, [Array]$matrix)
253 {
254 $inclusionMatrix = @()
255 foreach ($inclusion in $config.include) {
256 $full = GenerateFullMatrix $inclusion $config.displayNamesLookup
257 $inclusionMatrix += $full
258 }
259
260 return $matrix + $inclusionMatrix
261 }
262
ParseReplacement([String] $replacement)263 function ParseReplacement([String]$replacement) {
264 $parsed = '', '', ''
265 $idx = 0
266 $escaped = $false
267 $operators = '=', '/'
268 $err = "Invalid replacement syntax, expecting <key>=<value>/<replace>"
269
270 foreach ($c in $replacement -split '') {
271 if ($idx -ge $parsed.Length) {
272 throw $err
273 }
274 if (!$escaped -and $c -in $operators) {
275 $idx++
276 } else {
277 $parsed[$idx] += $c
278 }
279 $escaped = $c -eq '\'
280 }
281
282 if ($idx -lt $parsed.Length - 1) {
283 throw $err
284 }
285
286 $replace = $parsed[2] -replace "\\([$($operators -join '')])", '$1'
287
288 return @{
289 "key" = '^' + $parsed[0] + '$'
290 # Force full matches only.
291 "value" = '^' + $parsed[1] + '$'
292 "replace" = $replace
293 }
294 }
295
ProcessReplace()296 function ProcessReplace
297 {
298 param(
299 [Array]$matrix,
300 [Array]$replacements,
301 [Hashtable]$displayNamesLookup
302 )
303
304 if (!$replacements) {
305 return $matrix
306 }
307
308 $replaceMatrix = @()
309
310 foreach ($element in $matrix) {
311 $replacement = [MatrixParameter[]]@()
312
313 foreach ($perm in $element._permutation) {
314 $replace = $perm
315
316 # Iterate nested permutations or run once for singular values (int, string, bool)
317 foreach ($flattened in $perm.Flatten()) {
318 foreach ($query in $replacements) {
319 $parsed = ParseReplacement $query
320 if ($flattened.Name -match $parsed.key -and $flattened.Value -match $parsed.value) {
321 # In most cases, this will just swap one value for another, however -replace
322 # is used here in order to support replace values which may use regex capture groups
323 # e.g. 'foo-1' -replace '(foo)-1', '$1-replaced'
324 $replaceValue = $flattened.Value -replace $parsed.value, $parsed.replace
325 $perm.Set($replaceValue, $parsed.key)
326 break
327 }
328 }
329 }
330
331 $replacement += $perm
332 }
333
334 $replaceMatrix += CreateMatrixCombinationScalar $replacement $displayNamesLookup
335 }
336
337 return $replaceMatrix
338 }
339
ProcessImport([MatrixParameter[]]$matrix, [String]$selection, [Hashtable]$displayNamesLookup)340 function ProcessImport([MatrixParameter[]]$matrix, [String]$selection, [Hashtable]$displayNamesLookup)
341 {
342 $importPath = ""
343 $matrix = $matrix | ForEach-Object {
344 if ($_.Name -ne $IMPORT_KEYWORD) {
345 return $_
346 } else {
347 $importPath = $_.Value
348 }
349 }
350 if (!$matrix -or !$importPath) {
351 return $matrix, @()
352 }
353
354 $importedMatrixConfig = GetMatrixConfigFromJson (Get-Content $importPath)
355 $importedMatrix = GenerateMatrix $importedMatrixConfig $selection
356
357 $combinedDisplayNameLookup = $importedMatrixConfig.displayNamesLookup
358 foreach ($lookup in $displayNamesLookup.GetEnumerator()) {
359 $combinedDisplayNameLookup[$lookup.Name] = $lookup.Value
360 }
361
362 return $matrix, $importedMatrix, $importedMatrixConfig.displayNamesLookup
363 }
364
CombineMatrices([Array]$matrix1, [Array]$matrix2, [Hashtable]$displayNamesLookup = @{})365 function CombineMatrices([Array]$matrix1, [Array]$matrix2, [Hashtable]$displayNamesLookup = @{})
366 {
367 $combined = @()
368 if (!$matrix1) {
369 return $matrix2
370 }
371 if (!$matrix2) {
372 return $matrix1
373 }
374
375 foreach ($entry1 in $matrix1) {
376 foreach ($entry2 in $matrix2) {
377 $combined += CreateMatrixCombinationScalar ($entry1._permutation + $entry2._permutation) $displayNamesLookup
378 }
379 }
380
381 return $combined
382 }
383
MatrixElementMatch([System.Collections.Specialized.OrderedDictionary]$source, [System.Collections.Specialized.OrderedDictionary]$target)384 function MatrixElementMatch([System.Collections.Specialized.OrderedDictionary]$source, [System.Collections.Specialized.OrderedDictionary]$target)
385 {
386 if ($target.Count -eq 0) {
387 return $false
388 }
389
390 foreach ($key in $target.Keys) {
391 if (!$source.Contains($key) -or $source[$key] -ne $target[$key]) {
392 return $false
393 }
394 }
395
396 return $true
397 }
398
CloneOrderedDictionary([System.Collections.Specialized.OrderedDictionary]$dictionary)399 function CloneOrderedDictionary([System.Collections.Specialized.OrderedDictionary]$dictionary) {
400 $newDictionary = [Ordered]@{}
401 foreach ($element in $dictionary.GetEnumerator()) {
402 $newDictionary[$element.Name] = $element.Value
403 }
404 return $newDictionary
405 }
406
SerializePipelineMatrix([Array]$matrix)407 function SerializePipelineMatrix([Array]$matrix)
408 {
409 $pipelineMatrix = [Ordered]@{}
410 foreach ($entry in $matrix) {
411 if ($pipelineMatrix.Contains($entry.Name)) {
412 Write-Warning "Found duplicate configurations for job `"$($entry.name)`". Multiple values may have been replaced with the same value."
413 continue
414 }
415 $pipelineMatrix.Add($entry.name, [Ordered]@{})
416 foreach ($key in $entry.parameters.Keys) {
417 $pipelineMatrix[$entry.name].Add($key, $entry.parameters[$key])
418 }
419 }
420
421 return @{
422 compressed = $pipelineMatrix | ConvertTo-Json -Compress ;
423 pretty = $pipelineMatrix | ConvertTo-Json;
424 }
425 }
426
GenerateSparseMatrix()427 function GenerateSparseMatrix(
428 [MatrixParameter[]]$parameters,
429 [Hashtable]$displayNamesLookup,
430 [Array]$nonSparseParameters = @()
431 ) {
432 $parameters, $nonSparse = ProcessNonSparseParameters $parameters $nonSparseParameters
433 $dimensions = GetMatrixDimensions $parameters
434 $matrix = GenerateFullMatrix $parameters $displayNamesLookup
435
436 $sparseMatrix = @()
437 $indexes = GetSparseMatrixIndexes $dimensions
438 foreach ($idx in $indexes) {
439 $sparseMatrix += GetNdMatrixElement $idx $matrix $dimensions
440 }
441
442 if ($nonSparse) {
443 $allOfMatrix = GenerateFullMatrix $nonSparse $displayNamesLookup
444 return CombineMatrices $allOfMatrix $sparseMatrix $displayNamesLookup
445 }
446
447 return $sparseMatrix
448 }
449
GetSparseMatrixIndexes([Array]$dimensions)450 function GetSparseMatrixIndexes([Array]$dimensions)
451 {
452 $size = ($dimensions | Measure-Object -Maximum).Maximum
453 $indexes = @()
454
455 # With full matrix, retrieve items by doing diagonal lookups across the matrix N times.
456 # For example, given a matrix with dimensions 3, 2, 2:
457 # 0, 0, 0
458 # 1, 1, 1
459 # 2, 2, 2
460 # 3, 0, 0 <- 3, 3, 3 wraps to 3, 0, 0 given the dimensions
461 for ($i = 0; $i -lt $size; $i++) {
462 $idx = @()
463 for ($j = 0; $j -lt $dimensions.Length; $j++) {
464 $idx += $i % $dimensions[$j]
465 }
466 $indexes += ,$idx
467 }
468
469 return $indexes
470 }
471
GenerateFullMatrix()472 function GenerateFullMatrix(
473 [MatrixParameter[]] $parameters,
474 [Hashtable]$displayNamesLookup = @{}
475 ) {
476 # Handle when the config does not have a matrix specified (e.g. only the include field is specified)
477 if ($parameters.Count -eq 0) {
478 return @()
479 }
480
481 $matrix = [System.Collections.ArrayList]::new()
482 InitializeMatrix $parameters $displayNamesLookup $matrix
483
484 return $matrix
485 }
486
CreateMatrixCombinationScalar([MatrixParameter[]]$permutation, [Hashtable]$displayNamesLookup = @{})487 function CreateMatrixCombinationScalar([MatrixParameter[]]$permutation, [Hashtable]$displayNamesLookup = @{})
488 {
489 $names = @()
490 $flattenedParameters = [Ordered]@{}
491
492 foreach ($entry in $permutation) {
493 $nameSegment = ""
494
495 # Unwind nested permutations or run once for singular values (int, string, bool)
496 foreach ($param in $entry.Flatten()) {
497 if ($flattenedParameters.Contains($param.Name)) {
498 throw "Found duplicate parameter `"$($param.Name)`" when creating matrix combination."
499 }
500 $flattenedParameters.Add($param.Name, $param.Value)
501 }
502
503 $nameSegment = $entry.CreateDisplayName($displayNamesLookup)
504 if ($nameSegment) {
505 $names += $nameSegment
506 }
507 }
508
509 # The maximum allowed matrix name length is 100 characters
510 $name = $names -join "_"
511 if ($name.Length -gt 100) {
512 $name = $name[0..99] -join ""
513 }
514 $stripped = $name -replace "^[^A-Za-z]*", "" # strip leading digits
515 if ($stripped -eq "") {
516 $name = "job_" + $name # Handle names that consist entirely of numbers
517 } else {
518 $name = $stripped
519 }
520
521 return @{
522 name = $name
523 parameters = $flattenedParameters
524 # Keep the original permutation around in case we need to re-process this entry when transforming the matrix
525 _permutation = $permutation
526 }
527 }
528
InitializeMatrix()529 function InitializeMatrix
530 {
531 param(
532 [MatrixParameter[]]$parameters,
533 [Hashtable]$displayNamesLookup,
534 [System.Collections.ArrayList]$permutations,
535 $permutation = [MatrixParameter[]]@()
536 )
537 $head, $tail = $parameters
538
539 if (!$head) {
540 $entry = CreateMatrixCombinationScalar $permutation $displayNamesLookup
541 $permutations.Add($entry) | Out-Null
542 return
543 }
544
545 # This behavior implicitly treats non-array values as single elements
546 foreach ($param in $head.Flatten()) {
547 $newPermutation = $permutation + $param
548 InitializeMatrix $tail $displayNamesLookup $permutations $newPermutation
549 }
550 }
551
GetMatrixDimensions([MatrixParameter[]]$parameters)552 function GetMatrixDimensions([MatrixParameter[]]$parameters)
553 {
554 $dimensions = @()
555 foreach ($param in $parameters) {
556 $dimensions += $param.Length()
557 }
558
559 return $dimensions
560 }
561
SetNdMatrixElement()562 function SetNdMatrixElement
563 {
564 param(
565 $element,
566 [ValidateNotNullOrEmpty()]
567 [Array]$idx,
568 [ValidateNotNullOrEmpty()]
569 [Array]$matrix,
570 [ValidateNotNullOrEmpty()]
571 [Array]$dimensions
572 )
573
574 if ($idx.Length -ne $dimensions.Length) {
575 throw "Matrix index query $($idx.Length) must be the same length as its dimensions $($dimensions.Length)"
576 }
577
578 $arrayIndex = GetNdMatrixArrayIndex $idx $dimensions
579 $matrix[$arrayIndex] = $element
580 }
581
GetNdMatrixArrayIndex()582 function GetNdMatrixArrayIndex
583 {
584 param(
585 [ValidateNotNullOrEmpty()]
586 [Array]$idx,
587 [ValidateNotNullOrEmpty()]
588 [Array]$dimensions
589 )
590
591 if ($idx.Length -ne $dimensions.Length) {
592 throw "Matrix index query length ($($idx.Length)) must be the same as dimension length ($($dimensions.Length))"
593 }
594
595 $stride = 1
596 # Commented out does lookup with wrap handling
597 # $index = $idx[$idx.Length-1] % $dimensions[$idx.Length-1]
598 $index = $idx[$idx.Length-1]
599
600 for ($i = $dimensions.Length-1; $i -ge 1; $i--) {
601 $stride *= $dimensions[$i]
602 # Commented out does lookup with wrap handling
603 # $index += ($idx[$i-1] % $dimensions[$i-1]) * $stride
604 $index += $idx[$i-1] * $stride
605 }
606
607 return $index
608 }
609
GetNdMatrixElement()610 function GetNdMatrixElement
611 {
612 param(
613 [ValidateNotNullOrEmpty()]
614 [Array]$idx,
615 [ValidateNotNullOrEmpty()]
616 [Array]$matrix,
617 [ValidateNotNullOrEmpty()]
618 [Array]$dimensions
619 )
620
621 $arrayIndex = GetNdMatrixArrayIndex $idx $dimensions
622 return $matrix[$arrayIndex]
623 }
624
GetNdMatrixIndex()625 function GetNdMatrixIndex
626 {
627 param(
628 [int]$index,
629 [ValidateNotNullOrEmpty()]
630 [Array]$dimensions
631 )
632
633 $matrixIndex = @()
634 $stride = 1
635
636 for ($i = $dimensions.Length-1; $i -ge 1; $i--) {
637 $stride *= $dimensions[$i]
638 $page = [math]::floor($index / $stride) % $dimensions[$i-1]
639 $matrixIndex = ,$page + $matrixIndex
640 }
641 $col = $index % $dimensions[$dimensions.Length-1]
642 $matrixIndex += $col
643
644 return $matrixIndex
645 }
646
647 # # # # # # # # # # # # # # # # # # # # # # # # # # # #
648 # The below functions are non-dynamic examples that #
649 # help explain the above N-dimensional algorithm #
650 # # # # # # # # # # # # # # # # # # # # # # # # # # # #
Get4dMatrixElement([Array]$idx, [Array]$matrix, [Array]$dimensions)651 function Get4dMatrixElement([Array]$idx, [Array]$matrix, [Array]$dimensions)
652 {
653 $stride1 = $idx[0] * $dimensions[1] * $dimensions[2] * $dimensions[3]
654 $stride2 = $idx[1] * $dimensions[2] * $dimensions[3]
655 $stride3 = $idx[2] * $dimensions[3]
656 $stride4 = $idx[3]
657
658 return $matrix[$stride1 + $stride2 + $stride3 + $stride4]
659 }
660
Get4dMatrixIndex([int]$index, [Array]$dimensions)661 function Get4dMatrixIndex([int]$index, [Array]$dimensions)
662 {
663 $stride1 = $dimensions[3]
664 $stride2 = $dimensions[2]
665 $stride3 = $dimensions[1]
666 $page1 = [math]::floor($index / $stride1) % $dimensions[2]
667 $page2 = [math]::floor($index / ($stride1 * $stride2)) % $dimensions[1]
668 $page3 = [math]::floor($index / ($stride1 * $stride2 * $stride3)) % $dimensions[0]
669 $remainder = $index % $dimensions[3]
670
671 return @($page3, $page2, $page1, $remainder)
672 }
673
674