forked from operator-framework/operator-registry
-
Notifications
You must be signed in to change notification settings - Fork 0
/
diff_include.go
288 lines (258 loc) · 9.95 KB
/
diff_include.go
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
package declcfg
import (
"fmt"
"strings"
"github.com/blang/semver/v4"
"github.com/sirupsen/logrus"
utilerrors "k8s.io/apimachinery/pkg/util/errors"
"github.com/operator-framework/operator-registry/alpha/model"
)
// DiffIncluder knows how to add packages, channels, and bundles
// from a source to a destination model.Model.
type DiffIncluder struct {
// Packages to add.
Packages []DiffIncludePackage
Logger *logrus.Entry
}
// DiffIncludePackage specifies a package, and optionally channels
// or a set of bundles from all channels (wrapped by a DiffIncludeChannel),
// to include.
type DiffIncludePackage struct {
// Name of package.
Name string
// Channels in package.
Channels []DiffIncludeChannel
// AllChannels contains bundle versions in package.
// Upgrade graphs from all channels in the named package containing a version
// from this field are included.
AllChannels DiffIncludeChannel
}
// DiffIncludeChannel specifies a channel, and optionally bundles and bundle versions to include.
type DiffIncludeChannel struct {
// Name of channel.
Name string
// Versions of bundles.
Versions []semver.Version
// Bundles are bundle names to include.
// Set this field only if the named bundle has no semantic version metadata.
Bundles []string
}
// Run adds all packages and channels in DiffIncluder with matching names
// directly, and all versions plus their upgrade graphs to channel heads,
// from newModel to outputModel.
func (i DiffIncluder) Run(newModel, outputModel model.Model) error {
var includeErrs []error
for _, ipkg := range i.Packages {
pkgLog := i.Logger.WithField("package", ipkg.Name)
includeErrs = append(includeErrs, ipkg.includeNewInOutputModel(newModel, outputModel, pkgLog)...)
}
if len(includeErrs) != 0 {
return fmt.Errorf("error including items:\n%v", utilerrors.NewAggregate(includeErrs))
}
return nil
}
// includeNewInOutputModel adds all packages, channels, and versions (bundles)
// specified by ipkg that exist in newModel to outputModel. Any package, channel,
// or version in ipkg not satisfied by newModel is an error.
func (ipkg DiffIncludePackage) includeNewInOutputModel(newModel, outputModel model.Model, logger *logrus.Entry) (ierrs []error) {
newPkg, newHasPkg := newModel[ipkg.Name]
if !newHasPkg {
ierrs = append(ierrs, fmt.Errorf("[package=%q] package does not exist in new model", ipkg.Name))
return ierrs
}
pkgLog := logger.WithField("package", newPkg.Name)
// No channels or versions were specified, meaning "include the full package".
if len(ipkg.Channels) == 0 && len(ipkg.AllChannels.Versions) == 0 && len(ipkg.AllChannels.Bundles) == 0 {
outputModel[ipkg.Name] = newPkg
return nil
}
outputPkg := copyPackageNoChannels(newPkg)
outputModel[outputPkg.Name] = outputPkg
// Add all channels to ipkg.Channels if bundles or versions were specified to include across all channels.
// skipMissingBundleForChannels's value for a channel will be true IFF at least one version is specified,
// since some other channel may contain that version.
skipMissingBundleForChannels := map[string]bool{}
if len(ipkg.AllChannels.Versions) != 0 || len(ipkg.AllChannels.Bundles) != 0 {
for newChName := range newPkg.Channels {
ipkg.Channels = append(ipkg.Channels, DiffIncludeChannel{
Name: newChName,
Versions: ipkg.AllChannels.Versions,
Bundles: ipkg.AllChannels.Bundles,
})
skipMissingBundleForChannels[newChName] = true
}
}
for _, ich := range ipkg.Channels {
newCh, pkgHasCh := newPkg.Channels[ich.Name]
if !pkgHasCh {
ierrs = append(ierrs, fmt.Errorf("[package=%q channel=%q] channel does not exist in new model", newPkg.Name, ich.Name))
continue
}
chLog := pkgLog.WithField("channel", newCh.Name)
bundles, err := getBundlesForVersions(newCh, ich.Versions, ich.Bundles, chLog, skipMissingBundleForChannels[newCh.Name])
if err != nil {
ierrs = append(ierrs, fmt.Errorf("[package=%q channel=%q] %v", newPkg.Name, newCh.Name, err))
continue
}
outputCh := copyChannelNoBundles(newCh, outputPkg)
outputPkg.Channels[outputCh.Name] = outputCh
for _, b := range bundles {
tb := copyBundle(b, outputCh, outputPkg)
outputCh.Bundles[tb.Name] = tb
}
}
return ierrs
}
// getBundlesForVersions returns all bundles matching a version in vers
// and their upgrade graph(s) to ch.Head().
// If skipMissingBundles is true, bundle names and versions not satisfied by bundles in ch
// will not result in errors.
func getBundlesForVersions(ch *model.Channel, vers []semver.Version, names []string, logger *logrus.Entry, skipMissingBundles bool) (bundles []*model.Bundle, err error) {
// Short circuit when no versions were specified, meaning "include the whole channel".
if len(vers) == 0 {
for _, b := range ch.Bundles {
bundles = append(bundles, b)
}
return bundles, nil
}
// Add every bundle with a specified bundle name or directly satisfying a bundle version to bundles.
versionsToInclude := make(map[string]struct{}, len(vers))
for _, ver := range vers {
versionsToInclude[ver.String()] = struct{}{}
}
namesToInclude := make(map[string]struct{}, len(vers))
for _, name := range names {
namesToInclude[name] = struct{}{}
}
for _, b := range ch.Bundles {
_, includeVersionedBundle := versionsToInclude[b.Version.String()]
_, includeNamedBundle := namesToInclude[b.Name]
if includeVersionedBundle || includeNamedBundle {
bundles = append(bundles, b)
}
}
// Some version was not satisfied by this channel.
if len(bundles) != len(versionsToInclude)+len(namesToInclude) && !skipMissingBundles {
for _, b := range bundles {
delete(versionsToInclude, b.Version.String())
delete(namesToInclude, b.Name)
}
var verStrs, nameStrs []string
for verStr := range versionsToInclude {
verStrs = append(verStrs, verStr)
}
for nameStr := range namesToInclude {
nameStrs = append(nameStrs, nameStr)
}
sb := strings.Builder{}
if len(verStrs) != 0 {
sb.WriteString(fmt.Sprintf("versions=%+q ", verStrs))
}
if len(nameStrs) != 0 {
sb.WriteString(fmt.Sprintf("names=%+q", nameStrs))
}
return nil, fmt.Errorf("bundles do not exist in channel: %s", strings.TrimSpace(sb.String()))
}
// Fill in the upgrade graph between each bundle and head.
// Regardless of semver order, this step needs to be performed
// for each included bundle because there might be leaf nodes
// in the upgrade graph for a particular version not captured
// by any other fill due to skips not being honored here.
head, err := ch.Head()
if err != nil {
return nil, err
}
graph := makeUpgradeGraph(ch)
bundleSet := map[string]*model.Bundle{}
for _, ib := range bundles {
if _, addedBundle := bundleSet[ib.Name]; addedBundle {
// A prior graph traverse already included this bundle.
continue
}
intersectingBundles, intersectionFound := findIntersectingBundles(ch, ib, head, graph)
if !intersectionFound {
logger.Debugf("channel head %q not reachable from bundle %q, adding without upgrade graph", head.Name, ib.Name)
bundleSet[ib.Name] = ib
}
for _, rb := range intersectingBundles {
bundleSet[rb.Name] = rb
}
}
for _, b := range bundleSet {
bundles = append(bundles, b)
}
return bundles, nil
}
// makeUpgradeGraph creates a DAG of bundles with map key Bundle.Replaces.
func makeUpgradeGraph(ch *model.Channel) map[string][]*model.Bundle {
graph := map[string][]*model.Bundle{}
for _, b := range ch.Bundles {
if b.Replaces != "" {
graph[b.Replaces] = append(graph[b.Replaces], b)
}
}
return graph
}
// findIntersectingBundles finds the intersecting bundle of start and end in the
// replaces upgrade graph graph by traversing down to the lowest graph node,
// then returns every bundle higher than the intersection. It is possible
// to find no intersection; this should only happen when start and end
// are not part of the same upgrade graph.
// Output bundle order is not guaranteed.
// Precondition: start must be a bundle in ch.
// Precondition: end must be ch's head.
func findIntersectingBundles(ch *model.Channel, start, end *model.Bundle, graph map[string][]*model.Bundle) ([]*model.Bundle, bool) {
// The intersecting set is equal to end if start is end.
if start.Name == end.Name {
return []*model.Bundle{end}, true
}
// Construct start's replaces chain for comparison against end's.
startChain := map[string]*model.Bundle{start.Name: nil}
for curr := start; curr != nil && curr.Replaces != ""; curr = ch.Bundles[curr.Replaces] {
startChain[curr.Replaces] = curr
}
// Trace end's replaces chain until it intersects with start's, or the root is reached.
var intersection string
if _, inChain := startChain[end.Name]; inChain {
intersection = end.Name
} else {
for curr := end; curr != nil && curr.Replaces != ""; curr = ch.Bundles[curr.Replaces] {
if _, inChain := startChain[curr.Replaces]; inChain {
intersection = curr.Replaces
break
}
}
}
// No intersection is found, delegate behavior to caller.
if intersection == "" {
return nil, false
}
// Find all bundles that replace the intersection via BFS,
// i.e. the set of bundles that fill the update graph between start and end.
replacesIntersection := graph[intersection]
replacesSet := map[string]*model.Bundle{}
for _, b := range replacesIntersection {
currName := ""
for next := []*model.Bundle{b}; len(next) > 0; next = next[1:] {
currName = next[0].Name
if _, hasReplaces := replacesSet[currName]; !hasReplaces {
replacers := graph[currName]
next = append(next, replacers...)
replacesSet[currName] = ch.Bundles[currName]
}
}
}
// Remove every bundle between start and intersection exclusively,
// since these bundles must already exist in the destination channel.
for rep := start; rep != nil && rep.Name != intersection; rep = ch.Bundles[rep.Replaces] {
delete(replacesSet, rep.Name)
}
// Ensure both start and end are added to the output.
replacesSet[start.Name] = start
replacesSet[end.Name] = end
var intersectingBundles []*model.Bundle
for _, b := range replacesSet {
intersectingBundles = append(intersectingBundles, b)
}
return intersectingBundles, true
}