1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
// Copyright 2025 syzkaller project authors. All rights reserved.
// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
package main
import "sort"
// CoveringArray returns an array of representative parameter value combinations.
// The method considers parameters from the first to the last and first tries to
// generate all possible combinations of their values.
// If N != 0, the method eventually switches to ensuring that all value pairs
// are represented, once all pairs are covered - all triples (aka Covering Array).
func CoveringArray(params [][]string, n int) [][]string {
var ret [][]int
for paramID, param := range params {
if len(ret) == 0 {
ret = append(ret, []int{})
}
// If we can explore all combinations, do it.
if len(ret)*len(param) <= n || n == 0 {
var newRet [][]int
for value := range param {
for _, row := range ret {
newRet = append(newRet, extendRow(row, value))
}
}
ret = newRet
continue
}
cover := &pairCoverage{cover: map[pairCombo]struct{}{}}
// First, select a value for each row.
var newRet [][]int
for _, row := range ret {
bestValue, bestCount := 0, coverDelta{}
for valueID := range param {
newCount := cover.wouldCover(row, paramID, valueID)
if newCount.betterThan(bestCount) {
bestValue = valueID
bestCount = newCount
}
}
newRet = append(newRet, extendRow(row, bestValue))
cover.record(row, paramID, bestValue)
}
// Now that all previous combinations are preserved, we can (as long as
// we don't exceed N) duplicate some of the rows to cover more.
for len(newRet) < n {
var bestRow []int
bestValue, bestCount := 0, coverDelta{}
for _, row := range ret {
for valueID := range param {
newCount := cover.wouldCover(row, paramID, valueID)
if newCount.betterThan(bestCount) {
bestRow = row
bestValue = valueID
bestCount = newCount
}
}
}
if !bestCount.betterThan(coverDelta{}) {
break
}
newRet = append(newRet, extendRow(bestRow, bestValue))
cover.record(bestRow, paramID, bestValue)
}
ret = newRet
}
sort.Slice(ret, func(i, j int) bool {
rowA, rowB := ret[i], ret[j]
for k := 0; k < len(rowA); k++ {
if rowA[k] != rowB[k] {
return rowA[k] < rowB[k]
}
}
return false
})
var retStrings [][]string
for _, row := range ret {
var stringRow []string
for paramID, valueID := range row {
stringRow = append(stringRow, params[paramID][valueID])
}
retStrings = append(retStrings, stringRow)
}
return retStrings
}
type pairCoverage struct {
cover map[pairCombo]struct{}
}
type coverDelta struct {
pairs int
triples int
}
func (c coverDelta) betterThan(other coverDelta) bool {
if c.pairs != other.pairs {
return c.pairs > other.pairs
}
return c.triples > other.triples
}
// By how much the coverage would increase if we append newVal to the row.
// The first integer is the number of newly covered pairs of values,
// the second integer is the number of newly covered triples of values.
func (pc *pairCoverage) wouldCover(row []int, newID, newVal int) coverDelta {
var pairs, triples int
for _, item := range rowToPairCombos(row, false, newID, newVal) {
if _, ok := pc.cover[item]; !ok {
pairs++
}
}
for _, item := range rowToPairCombos(row, true, newID, newVal) {
if _, ok := pc.cover[item]; !ok {
triples++
}
}
return coverDelta{pairs, triples}
}
func (pc *pairCoverage) record(row []int, newID, newVal int) {
for _, item := range append(
rowToPairCombos(row, false, newID, newVal),
rowToPairCombos(row, true, newID, newVal)...) {
pc.cover[item] = struct{}{}
}
}
type pair struct {
pos int
value int
}
type pairCombo struct {
first pair
second pair
third pair
}
func rowToPairCombos(row []int, triples bool, newID, newVal int) []pairCombo {
var ret []pairCombo
// All things being equal, we want to also favor more different values.
ret = append(ret, pairCombo{third: pair{newID + 1, newVal}})
for i := 0; i+1 < len(row); i++ {
if !triples {
ret = append(ret, pairCombo{
first: pair{i + 1, row[i]},
third: pair{newID + 1, newVal},
})
continue
}
for j := i + 1; j < len(row); j++ {
ret = append(ret, pairCombo{
first: pair{i + 1, row[i]},
second: pair{j + 1, row[j]},
third: pair{newID + 1, newVal},
})
}
}
return ret
}
func extendRow(row []int, newVal int) []int {
return append(append([]int{}, row...), newVal)
}
|
