-
Notifications
You must be signed in to change notification settings - Fork 124
/
dependency.go
295 lines (268 loc) · 11.7 KB
/
dependency.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
package model
import (
"github.com/mongodb/grip"
"github.com/pkg/errors"
)
type dependencyIncluder struct {
Project *Project
requester string
included map[TVPair]bool
deactivateGeneratedDeps map[TVPair]bool
}
// IncludeDependencies takes a project and a slice of variant/task pairs names
// and returns the expanded set of variant/task pairs to include all the dependencies/requirements
// for the given set of tasks.
// If any dependency is cross-variant, it will include the variant and task for that dependency.
// This function can return an error, but it should be treated as an informational warning.
func IncludeDependencies(project *Project, tvpairs []TVPair, requester string, activationInfo *specificActivationInfo) ([]TVPair, error) {
di := &dependencyIncluder{Project: project, requester: requester}
return di.include(tvpairs, activationInfo, nil)
}
// IncludeDependenciesWithGenerated performs the same function as IncludeDependencies for generated projects.
// activationInfo and generatedVariants are required in the case for generate tasks to detect if
// new generated dependency's task/variant pairs are depended on by inactive tasks. If so,
// we also set these new dependencies to inactive.
func IncludeDependenciesWithGenerated(project *Project, tvpairs []TVPair, requester string, activationInfo *specificActivationInfo, generatedVariants []parserBV) ([]TVPair, error) {
di := &dependencyIncluder{Project: project, requester: requester}
return di.include(tvpairs, activationInfo, generatedVariants)
}
// include crawls the tasks represented by the combination of variants and tasks and
// add or removes tasks based on the dependency graph. Dependent tasks
// are added; tasks that depend on unreachable tasks are pruned. New slices
// of variants and tasks are returned.
func (di *dependencyIncluder) include(initialDeps []TVPair, activationInfo *specificActivationInfo, generatedVariants []parserBV) ([]TVPair, error) {
di.included = map[TVPair]bool{}
di.deactivateGeneratedDeps = map[TVPair]bool{}
warnings := grip.NewBasicCatcher()
// handle each pairing, recursively adding and pruning based
// on the task's dependencies
for _, d := range initialDeps {
_, err := di.handle(d, activationInfo, generatedVariants, true)
warnings.Add(err)
}
outPairs := []TVPair{}
for pair, shouldInclude := range di.included {
if shouldInclude {
outPairs = append(outPairs, pair)
}
}
// We deactivate tasks that do not have specific activation set in the
// generated project but have been generated as dependencies of other
// explicitly inactive tasks
for pair, addToActivationInfo := range di.deactivateGeneratedDeps {
if addToActivationInfo {
activationInfo.activationTasks[pair.Variant] = append(activationInfo.activationTasks[pair.Variant], pair.TaskName)
}
}
return outPairs, warnings.Resolve()
}
// handle finds and includes all tasks that the given task/variant pair depends
// on. Returns true if the task and all of its dependent tasks can be scheduled
// for the requester. Returns false if it cannot be scheduled, with an error
// explaining why.
// isRoot denotes whether the function is at its recursive root, and if so we
// update the deactivateGeneratedDeps map.
func (di *dependencyIncluder) handle(pair TVPair, activationInfo *specificActivationInfo, generatedVariants []parserBV, isRoot bool) (bool, error) {
if included, ok := di.included[pair]; ok {
// we've been here before, so don't redo work
return included, nil
}
// For a task group, recurse on each task and add those tasks that should be
// included.
if tg := di.Project.FindTaskGroup(pair.TaskName); tg != nil {
catcher := grip.NewBasicCatcher()
for _, t := range tg.Tasks {
_, err := di.handle(TVPair{TaskName: t, Variant: pair.Variant}, activationInfo, generatedVariants, false)
catcher.Wrapf(err, "task group '%s' in variant '%s' contains unschedulable task '%s'", pair.TaskName, pair.Variant, t)
}
if catcher.HasErrors() {
return false, catcher.Resolve()
}
return true, nil
}
// we must load the BuildVariantTaskUnit for the task/variant pair,
// since it contains the full scope of dependency information
bvt := di.Project.FindTaskForVariant(pair.TaskName, pair.Variant)
if bvt == nil {
di.included[pair] = false
return false, errors.Errorf("task '%s' does not exist in project '%s' for variant '%s'", pair.TaskName,
di.Project.Identifier, pair.Variant)
}
if bvt.SkipOnRequester(di.requester) {
// TODO (DEVPROD-4776): it seems like this should not include the task,
// but should not error either. When checking dependencies, it simply
// skips tasks whose requester doesn't apply, so it should probably just
// return false and no error here.
di.included[pair] = false
return false, errors.Errorf("task '%s' in variant '%s' cannot be run for a '%s'", pair.TaskName, pair.Variant, di.requester)
}
if bvt.IsDisabled() {
di.included[pair] = false
return false, nil
}
di.included[pair] = true
// queue up all dependencies for recursive inclusion
deps := di.expandDependencies(pair, bvt.DependsOn)
// If this function is invoked from generate.tasks, calculate all variants
// that need to be included as dependencies, but are not in the generated project.
// If all the task / variant pairs that spawn these dependencies are inactive, we
// also mark this newly generated dependency as inactive.
pairSpecifiesActivation := activationInfo.taskOrVariantHasSpecificActivation(pair.Variant, pair.TaskName)
catcher := grip.NewBasicCatcher()
for _, dep := range deps {
// Since the only tasks that have activation info set are the initial unexpanded dependencies, we only need
// to propagate the deactivateGeneratedDeps for those tasks, which only exist at the root level of each recursion.
// Hence, if isRoot is true, we updateDeactivationMap for the full recursive set of dependencies of the task.
if isRoot {
di.updateDeactivationMap(dep, generatedVariants, pairSpecifiesActivation)
}
ok, err := di.handle(dep, activationInfo, generatedVariants, false)
if !ok {
di.included[pair] = false
catcher.Wrapf(err, "task '%s' in variant '%s' has an unschedulable dependency", pair.TaskName, pair.Variant)
}
}
if catcher.HasErrors() {
return false, catcher.Resolve()
}
// we've reached a point where we know it is safe to include the current task
return true, nil
}
func (di *dependencyIncluder) updateDeactivationMap(pair TVPair, generatedVariants []parserBV, pairSpecifiesActivation bool) {
if !variantExistsInGeneratedProject(generatedVariants, pair.Variant) {
// If the dependency has not yet been added to deactivateGeneratedDeps, or if the
// original pair needs to be active, we update deactivateGeneratedDeps.
// We ultimately will only deactivate new dependencies where deactivateGeneratedDeps[pair] = true.
// If deactivateGeneratedDeps[pair] = false it signifies that there was at least
// one pair that depends on this new dep being active - so we cannot deactivate it.
if _, foundPair := di.deactivateGeneratedDeps[pair]; !foundPair || !pairSpecifiesActivation {
di.deactivateGeneratedDeps[pair] = pairSpecifiesActivation
di.recursivelyUpdateDeactivationMap(pair, map[TVPair]bool{}, pairSpecifiesActivation)
}
}
}
// recursivelyUpdateDeactivationMap recurses through the full dependencies of a task and updates their value
// in the deactivateGeneratedDeps based on the pairSpecifiesActivation input.
func (di *dependencyIncluder) recursivelyUpdateDeactivationMap(pair TVPair, dependencyIncluded map[TVPair]bool, pairSpecifiesActivation bool) {
// If we've been here before, return early to avoid infinite recursion and extra work.
if dependencyIncluded[pair] {
return
}
dependencyIncluded[pair] = true
bvt := di.Project.FindTaskForVariant(pair.TaskName, pair.Variant)
if bvt != nil {
deps := di.expandDependencies(pair, bvt.DependsOn)
for _, dep := range deps {
// Values only get set to true if pairSpecifiesActivation is true, otherwise they are set to false,
// which signifies that we must activate the task.
if _, foundDep := di.deactivateGeneratedDeps[dep]; !foundDep || !pairSpecifiesActivation {
di.deactivateGeneratedDeps[dep] = pairSpecifiesActivation
}
di.recursivelyUpdateDeactivationMap(dep, dependencyIncluded, pairSpecifiesActivation)
}
}
}
// expandDependencies finds all tasks depended on by the current task/variant pair.
func (di *dependencyIncluder) expandDependencies(pair TVPair, depends []TaskUnitDependency) []TVPair {
deps := []TVPair{}
for _, d := range depends {
// don't automatically add dependencies if they are marked patch_optional
if d.PatchOptional {
continue
}
switch {
case d.Variant == AllVariants && d.Name == AllDependencies: // task = *, variant = *
// Here we get all variants and tasks (excluding the current task)
// and add them to the list of tasks and variants.
for _, v := range di.Project.BuildVariants {
for _, t := range v.Tasks {
if t.Name == pair.TaskName && v.Name == pair.Variant {
continue
}
projectTask := di.Project.FindTaskForVariant(t.Name, v.Name)
if projectTask != nil {
if projectTask.IsDisabled() || projectTask.SkipOnRequester(di.requester) {
continue
}
deps = append(deps, TVPair{TaskName: t.Name, Variant: v.Name})
}
}
}
case d.Variant == AllVariants: // specific task, variant = *
// In the case where we depend on a task on all variants, we fetch the task's
// dependencies, then add that task for all variants that have it.
for _, v := range di.Project.BuildVariants {
for _, t := range v.Tasks {
if t.Name == pair.TaskName && v.Name == pair.Variant {
continue
}
if t.IsGroup {
if !di.dependencyMatchesTaskGroupTask(pair, t, d) {
continue
}
} else if t.Name != d.Name {
continue
}
projectTask := di.Project.FindTaskForVariant(t.Name, v.Name)
if projectTask != nil {
if projectTask.IsDisabled() || projectTask.SkipOnRequester(di.requester) {
continue
}
deps = append(deps, TVPair{TaskName: t.Name, Variant: v.Name})
}
}
}
case d.Name == AllDependencies: // task = *, specific variant
// Here we add every task for a single variant. We add the dependent variant,
// then add all of that variant's task, as well as their dependencies.
v := d.Variant
if v == "" {
v = pair.Variant
}
variant := di.Project.FindBuildVariant(v)
if variant != nil {
for _, t := range variant.Tasks {
if t.Name == pair.TaskName && variant.Name == pair.Variant {
continue
}
projectTask := di.Project.FindTaskForVariant(t.Name, v)
if projectTask != nil {
if projectTask.IsDisabled() || projectTask.SkipOnRequester(di.requester) {
continue
}
deps = append(deps, TVPair{TaskName: t.Name, Variant: variant.Name})
}
}
}
default: // specific name, specific variant
// We simply add a single task/variant and its dependencies. This does not do
// the requester check above because we assume the user has configured this
// correctly
v := d.Variant
if v == "" {
v = pair.Variant
}
projectTask := di.Project.FindTaskForVariant(d.Name, v)
if projectTask != nil && !projectTask.IsDisabled() {
deps = append(deps, TVPair{TaskName: d.Name, Variant: v})
}
}
}
return deps
}
func (di *dependencyIncluder) dependencyMatchesTaskGroupTask(depSrc TVPair, bvt BuildVariantTaskUnit, dep TaskUnitDependency) bool {
tg := di.Project.FindTaskGroup(bvt.Name)
if tg == nil {
return false
}
for _, tgTaskName := range tg.Tasks {
if tgTaskName == depSrc.TaskName && bvt.Variant == depSrc.Variant {
// Exclude self.
continue
}
if tgTaskName == dep.Name {
return true
}
}
return false
}