This repository has been archived by the owner on Sep 9, 2020. It is now read-only.
/
lockdiff.go
439 lines (377 loc) · 12.8 KB
/
lockdiff.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
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package verify
import (
"bytes"
"sort"
"strings"
"github.com/golang/dep/gps"
)
// DeltaDimension defines a bitset enumerating all of the different dimensions
// along which a Lock, and its constitutent components, can change.
type DeltaDimension uint32
// Each flag represents an ortohgonal dimension along which Locks can vary with
// respect to each other.
const (
InputImportsChanged DeltaDimension = 1 << iota
ProjectAdded
ProjectRemoved
SourceChanged
VersionChanged
RevisionChanged
PackagesChanged
PruneOptsChanged
HashVersionChanged
HashChanged
AnyChanged = (1 << iota) - 1
)
// LockDelta represents all possible differences between two Locks.
type LockDelta struct {
AddedImportInputs []string
RemovedImportInputs []string
ProjectDeltas map[gps.ProjectRoot]LockedProjectDelta
}
// LockedProjectDelta represents all possible state changes of a LockedProject
// within a Lock. It encapsulates the property-level differences represented by
// a LockedProjectPropertiesDelta, but can also represent existence deltas - a
// given name came to exist, or cease to exist, across two Locks.
type LockedProjectDelta struct {
Name gps.ProjectRoot
ProjectRemoved, ProjectAdded bool
LockedProjectPropertiesDelta
}
// LockedProjectPropertiesDelta represents all possible differences between the
// properties of two LockedProjects. It can represent deltas for
// VerifiableProject properties, as well.
type LockedProjectPropertiesDelta struct {
PackagesAdded, PackagesRemoved []string
VersionBefore, VersionAfter gps.UnpairedVersion
RevisionBefore, RevisionAfter gps.Revision
SourceBefore, SourceAfter string
PruneOptsBefore, PruneOptsAfter gps.PruneOptions
HashVersionBefore, HashVersionAfter int
HashChanged bool
}
// DiffLocks compares two locks and computes a semantically rich delta between
// them.
func DiffLocks(l1, l2 gps.Lock) LockDelta {
// Default nil locks to empty locks, so that we can still generate a diff.
if l1 == nil {
if l2 == nil {
// But both locks being nil results in an empty delta.
return LockDelta{}
}
l1 = gps.SimpleLock{}
}
if l2 == nil {
l2 = gps.SimpleLock{}
}
p1, p2 := l1.Projects(), l2.Projects()
p1 = sortLockedProjects(p1)
p2 = sortLockedProjects(p2)
diff := LockDelta{
ProjectDeltas: make(map[gps.ProjectRoot]LockedProjectDelta),
}
var i2next int
for i1 := 0; i1 < len(p1); i1++ {
lp1 := p1[i1]
pr1 := lp1.Ident().ProjectRoot
lpd := LockedProjectDelta{
Name: pr1,
// Default to assuming a project was removed, as it will handle both
// the obvious removal case (where there's a visible hole in p2),
// and the non-obvious case, where p2 is shorter than p1.
ProjectRemoved: true,
}
for i2 := i2next; i2 < len(p2); i2++ {
lp2 := p2[i2]
pr2 := lp2.Ident().ProjectRoot
switch strings.Compare(string(pr1), string(pr2)) {
case 0: // Found a matching project
lpd = LockedProjectDelta{
Name: pr1,
LockedProjectPropertiesDelta: DiffLockedProjectProperties(lp1, lp2),
}
i2next = i2 + 1 // Don't visit this project again
case +1: // Found a new project
diff.ProjectDeltas[pr2] = LockedProjectDelta{
Name: pr2,
ProjectAdded: true,
}
i2next = i2 + 1 // Don't visit this project again
continue // Keep looking for a matching project
}
break // Done evaluating this project, move onto the next
}
diff.ProjectDeltas[pr1] = lpd
}
// Anything that still hasn't been evaluated are adds
for i2 := i2next; i2 < len(p2); i2++ {
lp2 := p2[i2]
pr2 := lp2.Ident().ProjectRoot
diff.ProjectDeltas[pr2] = LockedProjectDelta{
Name: pr2,
ProjectAdded: true,
}
}
diff.AddedImportInputs, diff.RemovedImportInputs = findAddedAndRemoved(l1.InputImports(), l2.InputImports())
return diff
}
func findAddedAndRemoved(l1, l2 []string) (add, remove []string) {
// Computing package add/removes might be optimizable to O(n) (?), but it's
// not critical path for any known case, so not worth the effort right now.
p1, p2 := make(map[string]bool, len(l1)), make(map[string]bool, len(l2))
for _, pkg := range l1 {
p1[pkg] = true
}
for _, pkg := range l2 {
p2[pkg] = true
}
for pkg := range p1 {
if !p2[pkg] {
remove = append(remove, pkg)
}
}
for pkg := range p2 {
if !p1[pkg] {
add = append(add, pkg)
}
}
return add, remove
}
// DiffLockedProjectProperties takes two gps.LockedProject and computes a delta
// for each of their component properties.
//
// This function is focused exclusively on the properties of a LockedProject. As
// such, it does not compare the ProjectRoot part of the LockedProject's
// ProjectIdentifier, as those are names, and the concern here is a difference
// in properties, not intrinsic identity.
func DiffLockedProjectProperties(lp1, lp2 gps.LockedProject) LockedProjectPropertiesDelta {
ld := LockedProjectPropertiesDelta{
SourceBefore: lp1.Ident().Source,
SourceAfter: lp2.Ident().Source,
}
ld.PackagesAdded, ld.PackagesRemoved = findAddedAndRemoved(lp1.Packages(), lp2.Packages())
switch v := lp1.Version().(type) {
case gps.PairedVersion:
ld.VersionBefore, ld.RevisionBefore = v.Unpair(), v.Revision()
case gps.Revision:
ld.RevisionBefore = v
case gps.UnpairedVersion:
// This should ideally never happen
ld.VersionBefore = v
}
switch v := lp2.Version().(type) {
case gps.PairedVersion:
ld.VersionAfter, ld.RevisionAfter = v.Unpair(), v.Revision()
case gps.Revision:
ld.RevisionAfter = v
case gps.UnpairedVersion:
// This should ideally never happen
ld.VersionAfter = v
}
vp1, ok1 := lp1.(VerifiableProject)
vp2, ok2 := lp2.(VerifiableProject)
if ok1 && ok2 {
ld.PruneOptsBefore, ld.PruneOptsAfter = vp1.PruneOpts, vp2.PruneOpts
ld.HashVersionBefore, ld.HashVersionAfter = vp1.Digest.HashVersion, vp2.Digest.HashVersion
if !bytes.Equal(vp1.Digest.Digest, vp2.Digest.Digest) {
ld.HashChanged = true
}
} else if ok1 {
ld.PruneOptsBefore = vp1.PruneOpts
ld.HashVersionBefore = vp1.Digest.HashVersion
ld.HashChanged = true
} else if ok2 {
ld.PruneOptsAfter = vp2.PruneOpts
ld.HashVersionAfter = vp2.Digest.HashVersion
ld.HashChanged = true
}
return ld
}
// Changed indicates whether the delta contains a change along the dimensions
// with their corresponding bits set.
//
// This implementation checks the topmost-level Lock properties
func (ld LockDelta) Changed(dims DeltaDimension) bool {
if dims&InputImportsChanged != 0 && (len(ld.AddedImportInputs) > 0 || len(ld.RemovedImportInputs) > 0) {
return true
}
for _, ld := range ld.ProjectDeltas {
if ld.Changed(dims & ^InputImportsChanged) {
return true
}
}
return false
}
// Changes returns a bitset indicating the dimensions along which deltas exist across
// all contents of the LockDelta.
//
// This recurses down into the individual LockedProjectDeltas contained within
// the LockDelta. A single delta along a particular dimension from a single
// project is sufficient to flip the bit on for that dimension.
func (ld LockDelta) Changes() DeltaDimension {
var dd DeltaDimension
if len(ld.AddedImportInputs) > 0 || len(ld.RemovedImportInputs) > 0 {
dd |= InputImportsChanged
}
for _, ld := range ld.ProjectDeltas {
dd |= ld.Changes()
}
return dd
}
// Changed indicates whether the delta contains a change along the dimensions
// with their corresponding bits set.
//
// For example, if only the Revision changed, and this method is called with
// SourceChanged | VersionChanged, it will return false; if it is called with
// VersionChanged | RevisionChanged, it will return true.
func (ld LockedProjectDelta) Changed(dims DeltaDimension) bool {
if dims&ProjectAdded != 0 && ld.WasAdded() {
return true
}
if dims&ProjectRemoved != 0 && ld.WasRemoved() {
return true
}
return ld.LockedProjectPropertiesDelta.Changed(dims & ^ProjectAdded & ^ProjectRemoved)
}
// Changes returns a bitset indicating the dimensions along which there were
// changes between the compared LockedProjects. This includes both
// existence-level deltas (add/remove) and property-level deltas.
func (ld LockedProjectDelta) Changes() DeltaDimension {
var dd DeltaDimension
if ld.WasAdded() {
dd |= ProjectAdded
}
if ld.WasRemoved() {
dd |= ProjectRemoved
}
return dd | ld.LockedProjectPropertiesDelta.Changes()
}
// WasRemoved returns true if the named project existed in the first lock, but
// did not exist in the second lock.
func (ld LockedProjectDelta) WasRemoved() bool {
return ld.ProjectRemoved
}
// WasAdded returns true if the named project did not exist in the first lock,
// but did exist in the second lock.
func (ld LockedProjectDelta) WasAdded() bool {
return ld.ProjectAdded
}
// Changed indicates whether the delta contains a change along the dimensions
// with their corresponding bits set.
//
// For example, if only the Revision changed, and this method is called with
// SourceChanged | VersionChanged, it will return false; if it is called with
// VersionChanged | RevisionChanged, it will return true.
func (ld LockedProjectPropertiesDelta) Changed(dims DeltaDimension) bool {
if dims&SourceChanged != 0 && ld.SourceChanged() {
return true
}
if dims&RevisionChanged != 0 && ld.RevisionChanged() {
return true
}
if dims&PruneOptsChanged != 0 && ld.PruneOptsChanged() {
return true
}
if dims&HashChanged != 0 && ld.HashChanged {
return true
}
if dims&HashVersionChanged != 0 && ld.HashVersionChanged() {
return true
}
if dims&VersionChanged != 0 && ld.VersionChanged() {
return true
}
if dims&PackagesChanged != 0 && ld.PackagesChanged() {
return true
}
return false
}
// Changes returns a bitset indicating the dimensions along which there were
// changes between the compared LockedProjects.
func (ld LockedProjectPropertiesDelta) Changes() DeltaDimension {
var dd DeltaDimension
if ld.SourceChanged() {
dd |= SourceChanged
}
if ld.RevisionChanged() {
dd |= RevisionChanged
}
if ld.PruneOptsChanged() {
dd |= PruneOptsChanged
}
if ld.HashChanged {
dd |= HashChanged
}
if ld.HashVersionChanged() {
dd |= HashVersionChanged
}
if ld.VersionChanged() {
dd |= VersionChanged
}
if ld.PackagesChanged() {
dd |= PackagesChanged
}
return dd
}
// SourceChanged returns true if the source field differed between the first and
// second locks.
func (ld LockedProjectPropertiesDelta) SourceChanged() bool {
return ld.SourceBefore != ld.SourceAfter
}
// VersionChanged returns true if the version property differed between the
// first and second locks. In addition to simple changes (e.g. 1.0.1 -> 1.0.2),
// this also includes all possible version type changes either going from a
// paired version to a plain revision, or the reverse direction, or the type of
// unpaired version changing (e.g. branch -> semver).
func (ld LockedProjectPropertiesDelta) VersionChanged() bool {
if ld.VersionBefore == nil && ld.VersionAfter == nil {
return false
} else if (ld.VersionBefore == nil || ld.VersionAfter == nil) || (ld.VersionBefore.Type() != ld.VersionAfter.Type()) {
return true
} else if !ld.VersionBefore.Matches(ld.VersionAfter) {
return true
}
return false
}
// RevisionChanged returns true if the revision property differed between the
// first and second locks.
func (ld LockedProjectPropertiesDelta) RevisionChanged() bool {
return ld.RevisionBefore != ld.RevisionAfter
}
// PackagesChanged returns true if the package set gained or lost members (or
// both) between the first and second locks.
func (ld LockedProjectPropertiesDelta) PackagesChanged() bool {
return len(ld.PackagesAdded) > 0 || len(ld.PackagesRemoved) > 0
}
// PruneOptsChanged returns true if the pruning flags for the project changed
// between the first and second locks.
func (ld LockedProjectPropertiesDelta) PruneOptsChanged() bool {
return ld.PruneOptsBefore != ld.PruneOptsAfter
}
// HashVersionChanged returns true if the version of the hashing algorithm
// changed between the first and second locks.
func (ld LockedProjectPropertiesDelta) HashVersionChanged() bool {
return ld.HashVersionBefore != ld.HashVersionAfter
}
// HashVersionWasZero returns true if the first lock had a zero hash version,
// which can only mean it was uninitialized.
func (ld LockedProjectPropertiesDelta) HashVersionWasZero() bool {
return ld.HashVersionBefore == 0
}
// sortLockedProjects returns a sorted copy of lps, or itself if already sorted.
func sortLockedProjects(lps []gps.LockedProject) []gps.LockedProject {
if len(lps) <= 1 || sort.SliceIsSorted(lps, func(i, j int) bool {
return lps[i].Ident().Less(lps[j].Ident())
}) {
return lps
}
cp := make([]gps.LockedProject, len(lps))
copy(cp, lps)
sort.Slice(cp, func(i, j int) bool {
return cp[i].Ident().Less(cp[j].Ident())
})
return cp
}