blob: 7684a5980c8c6c976cda1f53e86b411a29979ceb [file] [log] [blame]
Damien Martin-Guillerezf88f4d82015-09-25 13:56:55 +00001// Copyright 2014 The Bazel Authors. All rights reserved.
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +01002//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14package com.google.devtools.build.lib.skyframe;
15
16import com.google.common.base.Function;
17import com.google.common.base.Preconditions;
18import com.google.common.base.Verify;
19import com.google.common.collect.Collections2;
20import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
21import com.google.devtools.build.lib.events.Event;
22import com.google.devtools.build.lib.events.EventKind;
23import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.ResolvedFile;
24import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.TraversalRequest;
25import com.google.devtools.build.lib.vfs.Dirent;
26import com.google.devtools.build.lib.vfs.Path;
27import com.google.devtools.build.lib.vfs.PathFragment;
28import com.google.devtools.build.lib.vfs.RootedPath;
29import com.google.devtools.build.skyframe.SkyFunction;
30import com.google.devtools.build.skyframe.SkyFunctionException;
31import com.google.devtools.build.skyframe.SkyKey;
32import com.google.devtools.build.skyframe.SkyValue;
33
34import java.util.ArrayList;
35import java.util.Collection;
36import java.util.List;
37import java.util.Map;
38
39import javax.annotation.Nullable;
40
41/** A {@link SkyFunction} to build {@link RecursiveFilesystemTraversalValue}s. */
42public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
43
44 private static final class MissingDepException extends Exception {}
45
46 /** Base class for exceptions that {@link RecursiveFilesystemTraversalFunctionException} wraps. */
47 public abstract static class RecursiveFilesystemTraversalException extends Exception {
48 protected RecursiveFilesystemTraversalException(String message) {
49 super(message);
50 }
51 }
52
53 /** Thrown when a generated directory's root-relative path conflicts with a package's path. */
54 public static final class GeneratedPathConflictException extends
55 RecursiveFilesystemTraversalException {
56 GeneratedPathConflictException(TraversalRequest traversal) {
57 super(String.format(
58 "Generated directory %s conflicts with package under the same path. Additional info: %s",
59 traversal.path.getRelativePath().getPathString(),
60 traversal.errorInfo != null ? traversal.errorInfo : traversal.toString()));
61 }
62 }
63
64 /**
65 * Thrown when the traversal encounters a subdirectory with a BUILD file but is not allowed to
Laszlo Csomorf04efcc2015-02-12 17:08:06 +000066 * recurse into it. See {@code PackageBoundaryMode#REPORT_ERROR}.
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010067 */
68 public static final class CannotCrossPackageBoundaryException extends
69 RecursiveFilesystemTraversalException {
70 CannotCrossPackageBoundaryException(String message) {
71 super(message);
72 }
73 }
74
75 /**
76 * Thrown when a dangling symlink is attempted to be dereferenced.
77 *
78 * <p>Note: this class is not identical to the one in com.google.devtools.build.lib.view.fileset
79 * and it's not easy to merge the two because of the dependency structure. The other one will
80 * probably be removed along with the rest of the legacy Fileset code.
81 */
82 public static final class DanglingSymlinkException extends RecursiveFilesystemTraversalException {
83 public final String path;
84 public final String unresolvedLink;
85
86 public DanglingSymlinkException(String path, String unresolvedLink) {
Laszlo Csomor0ad729f2015-12-02 15:20:35 +000087 super(
88 String.format(
89 "Found dangling symlink: %s, unresolved path: \"%s\"", path, unresolvedLink));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010090 Preconditions.checkArgument(path != null && !path.isEmpty());
91 Preconditions.checkArgument(unresolvedLink != null && !unresolvedLink.isEmpty());
92 this.path = path;
93 this.unresolvedLink = unresolvedLink;
94 }
95
96 public String getPath() {
97 return path;
98 }
99 }
100
101 /** Exception type thrown by {@link RecursiveFilesystemTraversalFunction#compute}. */
102 private static final class RecursiveFilesystemTraversalFunctionException extends
103 SkyFunctionException {
104 RecursiveFilesystemTraversalFunctionException(RecursiveFilesystemTraversalException e) {
105 super(e, Transience.PERSISTENT);
106 }
107 }
108
109 @Override
110 public SkyValue compute(SkyKey skyKey, Environment env)
111 throws RecursiveFilesystemTraversalFunctionException {
112 TraversalRequest traversal = (TraversalRequest) skyKey.argument();
113 try {
114 // Stat the traversal root.
115 FileInfo rootInfo = lookUpFileInfo(env, traversal);
116
117 if (!rootInfo.type.exists()) {
118 // May be a dangling symlink or a non-existent file. Handle gracefully.
119 if (rootInfo.type.isSymlink()) {
120 return resultForDanglingSymlink(traversal.path, rootInfo);
121 } else {
122 return RecursiveFilesystemTraversalValue.EMPTY;
123 }
124 }
125
126 if (rootInfo.type.isFile()) {
Janak Ramakrishnan26cb4652015-04-21 01:29:54 +0000127 if (traversal.pattern == null
128 || traversal.pattern.matcher(
129 rootInfo.realPath.getRelativePath().getPathString()).matches()) {
130 // The root is a file or a symlink to one.
131 return resultForFileRoot(traversal.path, rootInfo);
132 } else {
133 return RecursiveFilesystemTraversalValue.EMPTY;
134 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100135 }
136
137 // Otherwise the root is a directory or a symlink to one.
138 PkgLookupResult pkgLookupResult = checkIfPackage(env, traversal, rootInfo);
139 traversal = pkgLookupResult.traversal;
140
141 if (pkgLookupResult.isConflicting()) {
142 // The traversal was requested for an output directory whose root-relative path conflicts
143 // with a source package. We can't handle that, bail out.
144 throw new RecursiveFilesystemTraversalFunctionException(
145 new GeneratedPathConflictException(traversal));
146 } else if (pkgLookupResult.isPackage() && !traversal.skipTestingForSubpackage) {
147 // The traversal was requested for a directory that defines a package.
Laszlo Csomorf04efcc2015-02-12 17:08:06 +0000148 String msg = traversal.errorInfo + " crosses package boundary into package rooted at "
149 + traversal.path.getRelativePath().getPathString();
150 switch (traversal.crossPkgBoundaries) {
151 case CROSS:
152 // We are free to traverse the subpackage but we need to display a warning.
153 env.getListener().handle(new Event(EventKind.WARNING, null, msg));
154 break;
155 case DONT_CROSS:
156 // We cannot traverse the subpackage and should skip it silently. Return empty results.
157 return RecursiveFilesystemTraversalValue.EMPTY;
158 case REPORT_ERROR:
159 // We cannot traverse the subpackage and should complain loudly (display an error).
160 throw new RecursiveFilesystemTraversalFunctionException(
161 new CannotCrossPackageBoundaryException(msg));
162 default:
163 throw new IllegalStateException(traversal.toString());
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100164 }
165 }
166
167 // We are free to traverse this directory.
168 Collection<SkyKey> dependentKeys = createRecursiveTraversalKeys(env, traversal);
169 return resultForDirectory(traversal, rootInfo, traverseChildren(env, dependentKeys));
170 } catch (MissingDepException e) {
171 return null;
172 }
173 }
174
175 @Override
176 public String extractTag(SkyKey skyKey) {
177 return null;
178 }
179
180 private static final class FileInfo {
181 final FileType type;
182 final FileStateValue metadata;
183 @Nullable final RootedPath realPath;
184 @Nullable final PathFragment unresolvedSymlinkTarget;
185
186 FileInfo(FileType type, FileStateValue metadata, @Nullable RootedPath realPath,
187 @Nullable PathFragment unresolvedSymlinkTarget) {
188 this.type = Preconditions.checkNotNull(type);
189 this.metadata = Preconditions.checkNotNull(metadata);
190 this.realPath = realPath;
191 this.unresolvedSymlinkTarget = unresolvedSymlinkTarget;
192 }
193
194 @Override
195 public String toString() {
196 if (type.isSymlink()) {
197 return String.format("(%s: link_value=%s, real_path=%s)", type,
198 unresolvedSymlinkTarget.getPathString(), realPath);
199 } else {
200 return String.format("(%s: real_path=%s)", type, realPath);
201 }
202 }
203 }
204
205 private static FileInfo lookUpFileInfo(Environment env, TraversalRequest traversal)
206 throws MissingDepException {
207 // Stat the file.
208 FileValue fileValue = (FileValue) getDependentSkyValue(env, FileValue.key(traversal.path));
209 if (fileValue.exists()) {
210 // If it exists, it may either be a symlink or a file/directory.
211 PathFragment unresolvedLinkTarget = null;
212 FileType type = null;
213 if (fileValue.isSymlink()) {
214 unresolvedLinkTarget = fileValue.getUnresolvedLinkTarget();
215 type = fileValue.isDirectory() ? FileType.SYMLINK_TO_DIRECTORY : FileType.SYMLINK_TO_FILE;
216 } else {
217 type = fileValue.isDirectory() ? FileType.DIRECTORY : FileType.FILE;
218 }
219 return new FileInfo(type, fileValue.realFileStateValue(),
220 fileValue.realRootedPath(), unresolvedLinkTarget);
221 } else {
222 // If it doesn't exist, or it's a dangling symlink, we still want to handle that gracefully.
223 return new FileInfo(
224 fileValue.isSymlink() ? FileType.DANGLING_SYMLINK : FileType.NONEXISTENT,
225 fileValue.realFileStateValue(), null,
226 fileValue.isSymlink() ? fileValue.getUnresolvedLinkTarget() : null);
227 }
228 }
229
230 private static final class PkgLookupResult {
231 private enum Type {
232 CONFLICT, DIRECTORY, PKG
233 }
234
235 private final Type type;
236 final TraversalRequest traversal;
237 final FileInfo rootInfo;
238
239 /** Result for a generated directory that conflicts with a source package. */
240 static PkgLookupResult conflict(TraversalRequest traversal, FileInfo rootInfo) {
241 return new PkgLookupResult(Type.CONFLICT, traversal, rootInfo);
242 }
243
244 /** Result for a source or generated directory (not a package). */
245 static PkgLookupResult directory(TraversalRequest traversal, FileInfo rootInfo) {
246 return new PkgLookupResult(Type.DIRECTORY, traversal, rootInfo);
247 }
248
249 /** Result for a package, i.e. a directory with a BUILD file. */
250 static PkgLookupResult pkg(TraversalRequest traversal, FileInfo rootInfo) {
251 return new PkgLookupResult(Type.PKG, traversal, rootInfo);
252 }
253
254 private PkgLookupResult(Type type, TraversalRequest traversal, FileInfo rootInfo) {
255 this.type = Preconditions.checkNotNull(type);
256 this.traversal = Preconditions.checkNotNull(traversal);
257 this.rootInfo = Preconditions.checkNotNull(rootInfo);
258 }
259
260 boolean isPackage() {
261 return type == Type.PKG;
262 }
263
264 boolean isConflicting() {
265 return type == Type.CONFLICT;
266 }
267
268 @Override
269 public String toString() {
270 return String.format("(%s: info=%s, traversal=%s)", type, rootInfo, traversal);
271 }
272 }
273
274 /**
275 * Checks whether the {@code traversal}'s path refers to a package directory.
276 *
277 * @return the result of the lookup; it contains potentially new {@link TraversalRequest} and
278 * {@link FileInfo} so the caller should use these instead of the old ones (this happens when
279 * a package is found, but under a different root than expected)
280 */
281 private static PkgLookupResult checkIfPackage(Environment env, TraversalRequest traversal,
282 FileInfo rootInfo) throws MissingDepException {
283 Preconditions.checkArgument(rootInfo.type.exists() && !rootInfo.type.isFile(),
284 "{%s} {%s}", traversal, rootInfo);
285 PackageLookupValue pkgLookup = (PackageLookupValue) getDependentSkyValue(env,
286 PackageLookupValue.key(traversal.path.getRelativePath()));
287
288 if (pkgLookup.packageExists()) {
289 if (traversal.isGenerated) {
290 // The traversal's root was a generated directory, but its root-relative path conflicts with
291 // an existing package.
292 return PkgLookupResult.conflict(traversal, rootInfo);
293 } else {
294 // The traversal's root was a source directory and it defines a package.
295 Path pkgRoot = pkgLookup.getRoot();
296 if (!pkgRoot.equals(traversal.path.getRoot())) {
297 // However the root of this package is different from what we expected. stat() the real
298 // BUILD file of that package.
299 traversal = traversal.forChangedRootPath(pkgRoot);
300 rootInfo = lookUpFileInfo(env, traversal);
301 Verify.verify(rootInfo.type.exists(), "{%s} {%s}", traversal, rootInfo);
302 }
303 return PkgLookupResult.pkg(traversal, rootInfo);
304 }
305 } else {
306 // The traversal's root was a directory (source or generated one), no package exists under the
307 // same root-relative path.
308 return PkgLookupResult.directory(traversal, rootInfo);
309 }
310 }
311
312 /**
313 * List the directory and create {@code SkyKey}s to request contents of its children recursively.
314 *
315 * <p>The returned keys are of type {@link SkyFunctions#RECURSIVE_FILESYSTEM_TRAVERSAL}.
316 */
317 private static Collection<SkyKey> createRecursiveTraversalKeys(Environment env,
318 TraversalRequest traversal) throws MissingDepException {
319 // Use the traversal's path, even if it's a symlink. The contents of the directory, as listed
320 // in the result, must be relative to it.
321 DirectoryListingValue dirListing = (DirectoryListingValue) getDependentSkyValue(env,
322 DirectoryListingValue.key(traversal.path));
323
324 List<SkyKey> result = new ArrayList<>();
325 for (Dirent dirent : dirListing.getDirents()) {
326 RootedPath childPath = RootedPath.toRootedPath(traversal.path.getRoot(),
327 traversal.path.getRelativePath().getRelative(dirent.getName()));
328 TraversalRequest childTraversal = traversal.forChildEntry(childPath);
329 result.add(RecursiveFilesystemTraversalValue.key(childTraversal));
330 }
331 return result;
332 }
333
334 /**
335 * Creates result for a dangling symlink.
336 *
337 * @param linkName path to the symbolic link
338 * @param info the {@link FileInfo} associated with the link file
339 */
340 private static RecursiveFilesystemTraversalValue resultForDanglingSymlink(RootedPath linkName,
341 FileInfo info) {
342 Preconditions.checkState(info.type.isSymlink() && !info.type.exists(), "{%s} {%s}", linkName,
343 info.type);
344 return RecursiveFilesystemTraversalValue.of(
345 ResolvedFile.danglingSymlink(linkName, info.unresolvedSymlinkTarget, info.metadata));
346 }
347
348 /**
349 * Creates results for a file or for a symlink that points to one.
350 *
351 * <p>A symlink may be direct (points to a file) or transitive (points at a direct or transitive
352 * symlink).
353 */
354 private static RecursiveFilesystemTraversalValue resultForFileRoot(RootedPath path,
355 FileInfo info) {
356 Preconditions.checkState(info.type.isFile() && info.type.exists(), "{%s} {%s}", path,
357 info.type);
358 if (info.type.isSymlink()) {
359 return RecursiveFilesystemTraversalValue.of(ResolvedFile.symlinkToFile(info.realPath, path,
360 info.unresolvedSymlinkTarget, info.metadata));
361 } else {
362 return RecursiveFilesystemTraversalValue.of(ResolvedFile.regularFile(path, info.metadata));
363 }
364 }
365
366 private static RecursiveFilesystemTraversalValue resultForDirectory(TraversalRequest traversal,
367 FileInfo rootInfo, Collection<RecursiveFilesystemTraversalValue> subdirTraversals) {
368 // Collect transitive closure of files in subdirectories.
369 NestedSetBuilder<ResolvedFile> paths = NestedSetBuilder.stableOrder();
370 for (RecursiveFilesystemTraversalValue child : subdirTraversals) {
371 paths.addTransitive(child.getTransitiveFiles());
372 }
373 ResolvedFile root;
374 if (rootInfo.type.isSymlink()) {
375 root = ResolvedFile.symlinkToDirectory(rootInfo.realPath, traversal.path,
376 rootInfo.unresolvedSymlinkTarget, rootInfo.metadata);
377 paths.add(root);
378 } else {
379 root = ResolvedFile.directory(rootInfo.realPath);
380 }
381 return RecursiveFilesystemTraversalValue.of(root, paths.build());
382 }
383
384 private static SkyValue getDependentSkyValue(Environment env, SkyKey key)
385 throws MissingDepException {
386 SkyValue value = env.getValue(key);
387 if (env.valuesMissing()) {
388 throw new MissingDepException();
389 }
390 return value;
391 }
392
393 /**
394 * Requests Skyframe to compute the dependent values and returns them.
395 *
396 * <p>The keys must all be {@link SkyFunctions#RECURSIVE_FILESYSTEM_TRAVERSAL} keys.
397 */
398 private static Collection<RecursiveFilesystemTraversalValue> traverseChildren(
399 Environment env, Iterable<SkyKey> keys)
400 throws MissingDepException {
401 Map<SkyKey, SkyValue> values = env.getValues(keys);
402 if (env.valuesMissing()) {
403 throw new MissingDepException();
404 }
405 return Collections2.transform(values.values(),
406 new Function<SkyValue, RecursiveFilesystemTraversalValue>() {
407 @Override
408 public RecursiveFilesystemTraversalValue apply(SkyValue input) {
409 return (RecursiveFilesystemTraversalValue) input;
410 }
411 });
412 }
413
414 /** Type information about the filesystem entry residing at a path. */
415 enum FileType {
416 /** A regular file. */
417 FILE {
418 @Override boolean isFile() { return true; }
419 @Override boolean exists() { return true; }
420 @Override public String toString() { return "<f>"; }
421 },
422 /**
423 * A symlink to a regular file.
424 *
425 * <p>The symlink may be direct (points to a non-symlink (here a file)) or it may be transitive
426 * (points to a direct or transitive symlink).
427 */
428 SYMLINK_TO_FILE {
429 @Override boolean isFile() { return true; }
430 @Override boolean isSymlink() { return true; }
431 @Override boolean exists() { return true; }
432 @Override public String toString() { return "<lf>"; }
433 },
434 /** A directory. */
435 DIRECTORY {
436 @Override boolean isDirectory() { return true; }
437 @Override boolean exists() { return true; }
438 @Override public String toString() { return "<d>"; }
439 },
440 /**
441 * A symlink to a directory.
442 *
443 * <p>The symlink may be direct (points to a non-symlink (here a directory)) or it may be
444 * transitive (points to a direct or transitive symlink).
445 */
446 SYMLINK_TO_DIRECTORY {
447 @Override boolean isDirectory() { return true; }
448 @Override boolean isSymlink() { return true; }
449 @Override boolean exists() { return true; }
450 @Override public String toString() { return "<ld>"; }
451 },
452 /** A dangling symlink, i.e. one whose target is known not to exist. */
453 DANGLING_SYMLINK {
454 @Override boolean isFile() { throw new UnsupportedOperationException(); }
455 @Override boolean isDirectory() { throw new UnsupportedOperationException(); }
456 @Override boolean isSymlink() { return true; }
457 @Override public String toString() { return "<l?>"; }
458 },
459 /** A path that does not exist or should be ignored. */
460 NONEXISTENT {
461 @Override public String toString() { return "<?>"; }
462 };
463
464 boolean isFile() { return false; }
465 boolean isDirectory() { return false; }
466 boolean isSymlink() { return false; }
467 boolean exists() { return false; }
468 @Override public abstract String toString();
469 }
470}