forked from golang/dep
/
locksat.go
199 lines (166 loc) · 5.47 KB
/
locksat.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
// 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 (
radix "github.com/armon/go-radix"
"github.com/golang/dep/gps"
"github.com/golang/dep/gps/paths"
"github.com/golang/dep/gps/pkgtree"
)
// LockSatisfaction holds the compound result of LockSatisfiesInputs, allowing
// the caller to inspect each of several orthogonal possible types of failure.
//
// The zero value assumes that there was no input lock, which necessarily means
// the inputs were not satisfied. This zero value means we err on the side of
// failure.
type LockSatisfaction struct {
// If LockExisted is false, it indicates that a nil gps.Lock was passed to
// LockSatisfiesInputs().
LockExisted bool
// MissingImports is the set of import paths that were present in the
// inputs but missing in the Lock.
MissingImports []string
// ExcessImports is the set of import paths that were present in the Lock
// but absent from the inputs.
ExcessImports []string
// UnmatchedConstraints reports any normal, non-override constraint rules that
// were not satisfied by the corresponding LockedProject in the Lock.
UnmetConstraints map[gps.ProjectRoot]ConstraintMismatch
// UnmatchedOverrides reports any override rules that were not satisfied by the
// corresponding LockedProject in the Lock.
UnmetOverrides map[gps.ProjectRoot]ConstraintMismatch
}
// ConstraintMismatch is a two-tuple of a gps.Version, and a gps.Constraint that
// does not allow that version.
type ConstraintMismatch struct {
C gps.Constraint
V gps.Version
}
// LockSatisfiesInputs determines whether the provided Lock satisfies all the
// requirements indicated by the inputs (RootManifest and PackageTree).
//
// The second parameter is expected to be the list of imports that were used to
// generate the input Lock. Without this explicit list, it is not possible to
// compute package imports that may have been removed. Figuring out that
// negative space would require exploring the entire graph to ensure there are
// no in-edges for particular imports.
func LockSatisfiesInputs(l gps.Lock, m gps.RootManifest, ptree pkgtree.PackageTree) LockSatisfaction {
if l == nil {
return LockSatisfaction{}
}
lsat := LockSatisfaction{
LockExisted: true,
UnmetOverrides: make(map[gps.ProjectRoot]ConstraintMismatch),
UnmetConstraints: make(map[gps.ProjectRoot]ConstraintMismatch),
}
var ig *pkgtree.IgnoredRuleset
var req map[string]bool
if m != nil {
ig = m.IgnoredPackages()
req = m.RequiredPackages()
}
rm, _ := ptree.ToReachMap(true, true, false, ig)
reach := rm.FlattenFn(paths.IsStandardImportPath)
inlock := make(map[string]bool, len(l.InputImports()))
ininputs := make(map[string]bool, len(reach)+len(req))
type lockUnsatisfy uint8
const (
missingFromLock lockUnsatisfy = iota
inAdditionToLock
)
pkgDiff := make(map[string]lockUnsatisfy)
for _, imp := range reach {
ininputs[imp] = true
}
for imp := range req {
ininputs[imp] = true
}
for _, imp := range l.InputImports() {
inlock[imp] = true
}
for ip := range ininputs {
if !inlock[ip] {
pkgDiff[ip] = missingFromLock
} else {
// So we don't have to revisit it below
delete(inlock, ip)
}
}
// Something in the missing list might already be in the packages list,
// because another package in the depgraph imports it. We could make a
// special case for that, but it would break the simplicity of the model and
// complicate the notion of LockSatisfaction.Passed(), so let's see if we
// can get away without it.
for ip := range inlock {
if !ininputs[ip] {
pkgDiff[ip] = inAdditionToLock
}
}
for ip, typ := range pkgDiff {
if typ == missingFromLock {
lsat.MissingImports = append(lsat.MissingImports, ip)
} else {
lsat.ExcessImports = append(lsat.ExcessImports, ip)
}
}
eff := findEffectualConstraints(m, ininputs)
ovr, constraints := m.Overrides(), m.DependencyConstraints()
for _, lp := range l.Projects() {
pr := lp.Ident().ProjectRoot
if pp, has := ovr[pr]; has {
if !pp.Constraint.Matches(lp.Version()) {
lsat.UnmetOverrides[pr] = ConstraintMismatch{
C: pp.Constraint,
V: lp.Version(),
}
}
// The constraint isn't considered if we have an override,
// independent of whether the override is satisfied.
continue
}
if pp, has := constraints[pr]; has && eff[string(pr)] && !pp.Constraint.Matches(lp.Version()) {
lsat.UnmetConstraints[pr] = ConstraintMismatch{
C: pp.Constraint,
V: lp.Version(),
}
}
}
return lsat
}
// Satisfied is a shortcut method that indicates whether there were any ways in
// which the Lock did not satisfy the inputs. It will return true only if the
// Lock was satisfactory in all respects vis-a-vis the inputs.
func (ls LockSatisfaction) Satisfied() bool {
if !ls.LockExisted {
return false
}
if len(ls.MissingImports) > 0 {
return false
}
if len(ls.ExcessImports) > 0 {
return false
}
if len(ls.UnmetOverrides) > 0 {
return false
}
if len(ls.UnmetConstraints) > 0 {
return false
}
return true
}
func findEffectualConstraints(m gps.Manifest, imports map[string]bool) map[string]bool {
eff := make(map[string]bool)
xt := radix.New()
for pr := range m.DependencyConstraints() {
// FIXME(sdboyer) this has the trailing slash ambiguity problem; adapt
// code from the solver
xt.Insert(string(pr), nil)
}
for imp := range imports {
if root, _, has := xt.LongestPrefix(imp); has {
eff[root] = true
}
}
return eff
}