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
|
// Copyright 2016 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.query2;
import static com.google.common.collect.ImmutableSet.toImmutableSet;
import static com.google.devtools.build.lib.query2.SkyQueryEnvironment.IS_TTV;
import static com.google.devtools.build.lib.query2.SkyQueryEnvironment.SKYKEY_TO_LABEL;
import com.google.common.base.Predicates;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.common.collect.Multimap;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.packages.Target;
import com.google.devtools.build.lib.query2.engine.Callback;
import com.google.devtools.build.lib.query2.engine.QueryException;
import com.google.devtools.build.lib.query2.engine.QueryExpressionContext;
import com.google.devtools.build.lib.query2.engine.Uniquifier;
import com.google.devtools.build.skyframe.SkyKey;
import java.util.Map;
import java.util.Set;
/**
* A helper class that computes unbounded 'deps(<expr>)' via BFS. Re-use logic from {@link
* AbstractEdgeVisitor} to grab relevant semaphore locks when processing nodes as well as batching
* visits by packages.
*/
class DepsUnboundedVisitor extends AbstractEdgeVisitor<SkyKey> {
/**
* A {@link Uniquifier} for valid deps. Only used prior to visiting the deps. Deps filtering is
* done in the {@link DepsUnboundedVisitor#getVisitResult} stage.
*/
private final Uniquifier<SkyKey> validDepUniquifier;
private final boolean depsNeedFiltering;
private final QueryExpressionContext<Target> context;
DepsUnboundedVisitor(
SkyQueryEnvironment env,
Uniquifier<SkyKey> validDepUniquifier,
Callback<Target> callback,
MultisetSemaphore<PackageIdentifier> packageSemaphore,
boolean depsNeedFiltering,
QueryExpressionContext<Target> context) {
super(env, callback, packageSemaphore);
this.validDepUniquifier = validDepUniquifier;
this.depsNeedFiltering = depsNeedFiltering;
this.context = context;
}
/**
* A {@link Factory} for {@link DepsUnboundedVisitor} instances, each of which will be used to
* perform visitation of the DTC of the {@link SkyKey}s passed in a single {@link
* Callback#process} call. Note that all the created instances share the same {@link Uniquifier}
* so that we don't visit the same Skyframe node more than once.
*/
static class Factory implements ParallelVisitor.Factory {
private final SkyQueryEnvironment env;
private final Uniquifier<SkyKey> validDepUniquifier;
private final Callback<Target> callback;
private final MultisetSemaphore<PackageIdentifier> packageSemaphore;
private final boolean depsNeedFiltering;
private final QueryExpressionContext<Target> context;
Factory(
SkyQueryEnvironment env,
Callback<Target> callback,
MultisetSemaphore<PackageIdentifier> packageSemaphore,
boolean depsNeedFiltering,
QueryExpressionContext<Target> context) {
this.env = env;
this.validDepUniquifier = env.createSkyKeyUniquifier();
this.callback = callback;
this.packageSemaphore = packageSemaphore;
this.depsNeedFiltering = depsNeedFiltering;
this.context = context;
}
@Override
public ParallelVisitor<SkyKey, Target> create() {
return new DepsUnboundedVisitor(
env,
validDepUniquifier,
callback,
packageSemaphore,
depsNeedFiltering,
context);
}
}
@Override
protected Visit getVisitResult(Iterable<SkyKey> keys) throws InterruptedException {
if (depsNeedFiltering) {
// We have to targetify the keys here in order to determine the allowed dependencies.
Multimap<SkyKey, SkyKey> packageKeyToTargetKeyMap = env.makePackageKeyToTargetKeyMap(keys);
Set<PackageIdentifier> pkgIdsNeededForTargetification =
packageKeyToTargetKeyMap
.keySet()
.stream()
.map(SkyQueryEnvironment.PACKAGE_SKYKEY_TO_PACKAGE_IDENTIFIER)
.collect(toImmutableSet());
packageSemaphore.acquireAll(pkgIdsNeededForTargetification);
Iterable<Target> deps;
try {
deps = env.getFwdDeps(env.makeTargetsFromSkyKeys(keys).values(), context);
} finally {
packageSemaphore.releaseAll(pkgIdsNeededForTargetification);
}
return new Visit(
/*keysToUseForResult=*/ keys,
/*keysToVisit=*/ Iterables.transform(deps, Target::getLabel));
}
// We need to explicitly check that all requested TTVs are actually in the graph.
Map<SkyKey, Iterable<SkyKey>> depMap = env.graph.getDirectDeps(keys);
checkIfMissingTargets(keys, depMap);
Iterable<SkyKey> deps = Iterables.filter(Iterables.concat(depMap.values()), IS_TTV);
return new Visit(keys, deps);
}
private void checkIfMissingTargets(Iterable<SkyKey> keys, Map<SkyKey, Iterable<SkyKey>> depMap) {
if (depMap.size() != Iterables.size(keys)) {
Iterable<Label> missingTargets =
Iterables.transform(
Iterables.filter(keys, Predicates.not(Predicates.in(depMap.keySet()))),
SKYKEY_TO_LABEL);
env.getEventHandler()
.handle(Event.warn("Targets were missing from graph: " + missingTargets));
}
}
@Override
protected Iterable<SkyKey> preprocessInitialVisit(Iterable<SkyKey> keys) {
return keys;
}
@Override
protected SkyKey getNewNodeFromEdge(SkyKey visit) {
return visit;
}
@Override
protected ImmutableList<SkyKey> getUniqueValues(Iterable<SkyKey> keysToVisit)
throws QueryException {
// Legit deps are already filtered using env.getFwdDeps().
return validDepUniquifier.unique(keysToVisit);
}
}
|
