blob: ed943ef8dd8ba66a918e2ba5505f158df797abfd [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
fellyf1e30f32019-07-09 12:26:10 -070016import static java.nio.charset.StandardCharsets.UTF_8;
17
Googler5284e6c2019-10-30 07:43:54 -070018import com.google.common.annotations.VisibleForTesting;
tomlua155b532017-11-08 20:12:47 +010019import com.google.common.base.Preconditions;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010020import com.google.common.base.Verify;
21import com.google.common.collect.Collections2;
Googlerc8acdbd2018-11-08 10:47:15 -080022import com.google.common.collect.ImmutableList;
felly5be4dd62018-02-05 11:11:53 -080023import com.google.devtools.build.lib.actions.Artifact;
Googlerc8acdbd2018-11-08 10:47:15 -080024import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
shahan602cc852018-06-06 20:09:57 -070025import com.google.devtools.build.lib.actions.FileArtifactValue;
fellyf1e30f32019-07-09 12:26:10 -070026import com.google.devtools.build.lib.actions.FileStateType;
27import com.google.devtools.build.lib.actions.FileStateValue;
Googler5284e6c2019-10-30 07:43:54 -070028import com.google.devtools.build.lib.actions.FileStateValue.RegularFileStateValue;
shahan602cc852018-06-06 20:09:57 -070029import com.google.devtools.build.lib.actions.FileValue;
fellyf1e30f32019-07-09 12:26:10 -070030import com.google.devtools.build.lib.actions.HasDigest;
Laszlo Csomor207140f2015-12-07 15:07:33 +000031import com.google.devtools.build.lib.collect.nestedset.NestedSet;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010032import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
33import com.google.devtools.build.lib.events.Event;
janakre2af68f2021-03-18 15:11:30 -070034import com.google.devtools.build.lib.io.FileSymlinkException;
35import com.google.devtools.build.lib.io.FileSymlinkInfiniteExpansionException;
36import com.google.devtools.build.lib.io.FileSymlinkInfiniteExpansionUniquenessFunction;
janakrb77246c2021-03-05 14:41:58 -080037import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
twerth45d82ca2021-02-24 02:28:54 -080038import com.google.devtools.build.lib.profiler.Profiler;
39import com.google.devtools.build.lib.profiler.ProfilerTask;
40import com.google.devtools.build.lib.profiler.SilentCloseable;
janakra4a564a2021-03-18 12:40:11 -070041import com.google.devtools.build.lib.server.FailureDetails;
jcaterb11c6e22020-04-03 11:40:16 -070042import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.FileType;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010043import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.ResolvedFile;
Laszlo Csomorb4d482b2015-12-04 13:23:54 +000044import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.ResolvedFileFactory;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010045import com.google.devtools.build.lib.skyframe.RecursiveFilesystemTraversalValue.TraversalRequest;
fellyf1e30f32019-07-09 12:26:10 -070046import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
Googler0129a242021-12-01 09:04:45 -080047import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
fellyf1e30f32019-07-09 12:26:10 -070048import com.google.devtools.build.lib.util.Fingerprint;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010049import com.google.devtools.build.lib.vfs.Dirent;
felly5be4dd62018-02-05 11:11:53 -080050import com.google.devtools.build.lib.vfs.FileStatus;
felly5be4dd62018-02-05 11:11:53 -080051import com.google.devtools.build.lib.vfs.Path;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010052import com.google.devtools.build.lib.vfs.PathFragment;
tomluee6a6862018-01-17 14:36:26 -080053import com.google.devtools.build.lib.vfs.Root;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010054import com.google.devtools.build.lib.vfs.RootedPath;
felly5be4dd62018-02-05 11:11:53 -080055import com.google.devtools.build.lib.vfs.Symlinks;
janakrfc1d79c2022-01-27 13:02:07 -080056import com.google.devtools.build.lib.vfs.SyscallCache;
janakre2853222022-03-08 10:52:18 -080057import com.google.devtools.build.lib.vfs.XattrProvider;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010058import com.google.devtools.build.skyframe.SkyFunction;
59import com.google.devtools.build.skyframe.SkyFunctionException;
60import com.google.devtools.build.skyframe.SkyKey;
61import com.google.devtools.build.skyframe.SkyValue;
kush95bf7c82017-08-30 00:27:35 +020062import java.io.IOException;
fellyf1e30f32019-07-09 12:26:10 -070063import java.math.BigInteger;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010064import java.util.ArrayList;
65import java.util.Collection;
felly5be4dd62018-02-05 11:11:53 -080066import java.util.Collections;
67import java.util.HashMap;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010068import java.util.List;
69import java.util.Map;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010070import javax.annotation.Nullable;
71
72/** A {@link SkyFunction} to build {@link RecursiveFilesystemTraversalValue}s. */
73public final class RecursiveFilesystemTraversalFunction implements SkyFunction {
fellyf1e30f32019-07-09 12:26:10 -070074 private static final byte[] MISSING_FINGERPRINT =
75 new BigInteger(1, "NonexistentFileStateValue".getBytes(UTF_8)).toByteArray();
76
Googler0129a242021-12-01 09:04:45 -080077 @SerializationConstant @AutoCodec.VisibleForSerialization
fellyf1e30f32019-07-09 12:26:10 -070078 static final HasDigest NON_EXISTENT_HAS_DIGEST = () -> MISSING_FINGERPRINT;
79
80 private static final FileInfo NON_EXISTENT_FILE_INFO =
81 new FileInfo(FileType.NONEXISTENT, NON_EXISTENT_HAS_DIGEST, null, null);
82
mschallerc12c0442020-06-08 12:06:35 -070083 /** The exception that {@link RecursiveFilesystemTraversalFunctionException} wraps. */
84 public static class RecursiveFilesystemTraversalException extends Exception {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010085
mschallerc12c0442020-06-08 12:06:35 -070086 /**
87 * Categories of errors that prevent normal {@link RecursiveFilesystemTraversalFunction}
88 * evaluation.
89 */
90 public enum Type {
91 /**
92 * The traversal encountered a subdirectory with a BUILD file but is not allowed to recurse
93 * into it. See {@code PackageBoundaryMode#REPORT_ERROR}.
94 */
95 CANNOT_CROSS_PACKAGE_BOUNDARY,
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010096
mschallerc12c0442020-06-08 12:06:35 -070097 /** A dangling symlink was dereferenced. */
98 DANGLING_SYMLINK,
99
100 /** A file operation failed. */
101 FILE_OPERATION_FAILURE,
102
103 /** A generated directory's root-relative path conflicts with a package's path. */
104 GENERATED_PATH_CONFLICT,
janakrb77246c2021-03-05 14:41:58 -0800105
106 /** A file/directory visited was part of a symlink cycle or infinite expansion. */
107 SYMLINK_CYCLE_OR_INFINITE_EXPANSION,
mschallerc12c0442020-06-08 12:06:35 -0700108 }
109
110 private final Type type;
111
112 RecursiveFilesystemTraversalException(String message, Type type) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100113 super(message);
mschallerc12c0442020-06-08 12:06:35 -0700114 this.type = type;
115 }
116
117 public Type getType() {
118 return type;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100119 }
120 }
121
122 /**
123 * Thrown when a dangling symlink is attempted to be dereferenced.
124 *
125 * <p>Note: this class is not identical to the one in com.google.devtools.build.lib.view.fileset
126 * and it's not easy to merge the two because of the dependency structure. The other one will
127 * probably be removed along with the rest of the legacy Fileset code.
128 */
mschallerc12c0442020-06-08 12:06:35 -0700129 static final class DanglingSymlinkException extends RecursiveFilesystemTraversalException {
130 DanglingSymlinkException(String path, String unresolvedLink) {
Laszlo Csomor0ad729f2015-12-02 15:20:35 +0000131 super(
132 String.format(
mschallerc12c0442020-06-08 12:06:35 -0700133 "Found dangling symlink: %s, unresolved path: \"%s\"", path, unresolvedLink),
134 Type.DANGLING_SYMLINK);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100135 Preconditions.checkArgument(path != null && !path.isEmpty());
136 Preconditions.checkArgument(unresolvedLink != null && !unresolvedLink.isEmpty());
kush95bf7c82017-08-30 00:27:35 +0200137 }
138 }
139
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100140 /** Exception type thrown by {@link RecursiveFilesystemTraversalFunction#compute}. */
141 private static final class RecursiveFilesystemTraversalFunctionException extends
142 SkyFunctionException {
143 RecursiveFilesystemTraversalFunctionException(RecursiveFilesystemTraversalException e) {
144 super(e, Transience.PERSISTENT);
145 }
146 }
147
janakrb2a94342022-02-05 22:02:14 -0800148 private final SyscallCache syscallCache;
janakr491e4412022-01-28 15:35:34 -0800149
janakrb2a94342022-02-05 22:02:14 -0800150 RecursiveFilesystemTraversalFunction(SyscallCache syscallCache) {
janakr491e4412022-01-28 15:35:34 -0800151 this.syscallCache = syscallCache;
152 }
153
janakrb77246c2021-03-05 14:41:58 -0800154 @Nullable
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100155 @Override
156 public SkyValue compute(SkyKey skyKey, Environment env)
Janak Ramakrishnan3c0adb22016-08-15 21:54:55 +0000157 throws RecursiveFilesystemTraversalFunctionException, InterruptedException {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100158 TraversalRequest traversal = (TraversalRequest) skyKey.argument();
twerth45d82ca2021-02-24 02:28:54 -0800159 try (SilentCloseable c =
160 Profiler.instance()
161 .profile(ProfilerTask.FILESYSTEM_TRAVERSAL, traversal.getRoot().toString())) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100162 // Stat the traversal root.
janakrb2a94342022-02-05 22:02:14 -0800163 FileInfo rootInfo = lookUpFileInfo(env, traversal, syscallCache);
janakrb77246c2021-03-05 14:41:58 -0800164 if (rootInfo == null) {
165 return null;
166 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100167
168 if (!rootInfo.type.exists()) {
169 // May be a dangling symlink or a non-existent file. Handle gracefully.
170 if (rootInfo.type.isSymlink()) {
felly5be4dd62018-02-05 11:11:53 -0800171 return resultForDanglingSymlink(traversal.root.asRootedPath(), rootInfo);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100172 } else {
173 return RecursiveFilesystemTraversalValue.EMPTY;
174 }
175 }
176
177 if (rootInfo.type.isFile()) {
felly5be4dd62018-02-05 11:11:53 -0800178 return resultForFileRoot(traversal.root.asRootedPath(), rootInfo);
Googlerc8acdbd2018-11-08 10:47:15 -0800179 } else if (rootInfo.type.isDirectory() && rootInfo.metadata instanceof TreeArtifactValue) {
180 final TreeArtifactValue value = (TreeArtifactValue) rootInfo.metadata;
181 ImmutableList.Builder<RecursiveFilesystemTraversalValue> list = ImmutableList.builder();
182 for (Map.Entry<TreeFileArtifact, FileArtifactValue> entry
183 : value.getChildValues().entrySet()) {
184 RootedPath path =
185 RootedPath.toRootedPath(
186 traversal.root.asRootedPath().getRoot(), entry.getKey().getPath());
jcaterb11c6e22020-04-03 11:40:16 -0700187 list.add(
188 resultForFileRoot(
189 path,
190 // TreeArtifact can't have symbolic inside. So the assumption for FileType.FILE
191 // is always true.
192 new FileInfo(FileType.FILE, entry.getValue(), path, null)));
Googlerc8acdbd2018-11-08 10:47:15 -0800193 }
194 return resultForDirectory(traversal, rootInfo, list.build());
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100195 }
196
197 // Otherwise the root is a directory or a symlink to one.
janakrb2a94342022-02-05 22:02:14 -0800198 PkgLookupResult pkgLookupResult = checkIfPackage(env, traversal, rootInfo, syscallCache);
janakrb77246c2021-03-05 14:41:58 -0800199 if (pkgLookupResult == null) {
200 return null;
201 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100202 traversal = pkgLookupResult.traversal;
203
204 if (pkgLookupResult.isConflicting()) {
205 // The traversal was requested for an output directory whose root-relative path conflicts
206 // with a source package. We can't handle that, bail out.
mschallerc12c0442020-06-08 12:06:35 -0700207 throw createGeneratedPathConflictException(traversal);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100208 } else if (pkgLookupResult.isPackage() && !traversal.skipTestingForSubpackage) {
209 // The traversal was requested for a directory that defines a package.
tomlu8cc5dcf2018-01-19 09:28:06 -0800210 String msg =
211 traversal.errorInfo
212 + " crosses package boundary into package rooted at "
felly5be4dd62018-02-05 11:11:53 -0800213 + traversal.root.asRootedPath().getRootRelativePath().getPathString();
Laszlo Csomorf04efcc2015-02-12 17:08:06 +0000214 switch (traversal.crossPkgBoundaries) {
215 case CROSS:
216 // We are free to traverse the subpackage but we need to display a warning.
Ulf Adams760e7092016-04-21 08:09:51 +0000217 env.getListener().handle(Event.warn(null, msg));
Laszlo Csomorf04efcc2015-02-12 17:08:06 +0000218 break;
219 case DONT_CROSS:
220 // We cannot traverse the subpackage and should skip it silently. Return empty results.
221 return RecursiveFilesystemTraversalValue.EMPTY;
222 case REPORT_ERROR:
223 // We cannot traverse the subpackage and should complain loudly (display an error).
224 throw new RecursiveFilesystemTraversalFunctionException(
mschallerc12c0442020-06-08 12:06:35 -0700225 new RecursiveFilesystemTraversalException(
226 msg, RecursiveFilesystemTraversalException.Type.CANNOT_CROSS_PACKAGE_BOUNDARY));
Laszlo Csomorf04efcc2015-02-12 17:08:06 +0000227 default:
228 throw new IllegalStateException(traversal.toString());
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100229 }
230 }
231
232 // We are free to traverse this directory.
233 Collection<SkyKey> dependentKeys = createRecursiveTraversalKeys(env, traversal);
janakrb77246c2021-03-05 14:41:58 -0800234 if (dependentKeys == null) {
235 return null;
236 }
237 Collection<RecursiveFilesystemTraversalValue> subdirTraversals =
238 traverseChildren(env, dependentKeys, /*inline=*/ traversal.isRootGenerated);
239 if (subdirTraversals == null) {
240 return null;
241 }
242 return resultForDirectory(traversal, rootInfo, subdirTraversals);
243 } catch (IOException | BuildFileNotFoundException e) {
244 String message =
245 String.format(
246 "Error while traversing directory %s: %s",
247 traversal.root.getRelativePart(), e.getMessage());
janakra4a564a2021-03-18 12:40:11 -0700248 // Trying to stat the starting point of this root may have failed with a symlink cycle or
249 // trying to get a package lookup value may have failed due to a symlink cycle.
250 RecursiveFilesystemTraversalException.Type exceptionType =
251 RecursiveFilesystemTraversalException.Type.FILE_OPERATION_FAILURE;
252 if (e instanceof FileSymlinkException) {
253 exceptionType =
254 RecursiveFilesystemTraversalException.Type.SYMLINK_CYCLE_OR_INFINITE_EXPANSION;
255 }
256 if (e instanceof DetailedException) {
257 FailureDetails.PackageLoading.Code code =
258 ((DetailedException) e)
259 .getDetailedExitCode()
260 .getFailureDetail()
261 .getPackageLoading()
262 .getCode();
263 if (code == FailureDetails.PackageLoading.Code.SYMLINK_CYCLE_OR_INFINITE_EXPANSION) {
264 exceptionType =
265 RecursiveFilesystemTraversalException.Type.SYMLINK_CYCLE_OR_INFINITE_EXPANSION;
266 }
267 }
kush95bf7c82017-08-30 00:27:35 +0200268 throw new RecursiveFilesystemTraversalFunctionException(
janakra4a564a2021-03-18 12:40:11 -0700269 new RecursiveFilesystemTraversalException(message, exceptionType));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100270 }
271 }
272
mschallerc12c0442020-06-08 12:06:35 -0700273 private static RecursiveFilesystemTraversalFunctionException createGeneratedPathConflictException(
274 TraversalRequest traversal) {
275 String message =
276 String.format(
277 "Generated directory %s conflicts with package under the same path. "
278 + "Additional info: %s",
279 traversal.root.asRootedPath().getRootRelativePath().getPathString(),
280 traversal.errorInfo != null ? traversal.errorInfo : traversal.toString());
281 return new RecursiveFilesystemTraversalFunctionException(
282 new RecursiveFilesystemTraversalException(
283 message, RecursiveFilesystemTraversalException.Type.GENERATED_PATH_CONFLICT));
284 }
285
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100286 private static final class FileInfo {
287 final FileType type;
fellyf1e30f32019-07-09 12:26:10 -0700288 final HasDigest metadata;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100289 @Nullable final RootedPath realPath;
290 @Nullable final PathFragment unresolvedSymlinkTarget;
291
kush4b120e72018-07-11 16:21:27 -0700292 FileInfo(
293 FileType type,
fellyf1e30f32019-07-09 12:26:10 -0700294 HasDigest metadata,
kush4b120e72018-07-11 16:21:27 -0700295 @Nullable RootedPath realPath,
kushb39c6932018-07-12 21:25:23 -0700296 @Nullable PathFragment unresolvedSymlinkTarget) {
fellyf1e30f32019-07-09 12:26:10 -0700297 Preconditions.checkNotNull(metadata.getDigest(), metadata);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100298 this.type = Preconditions.checkNotNull(type);
kushb39c6932018-07-12 21:25:23 -0700299 this.metadata = metadata;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100300 this.realPath = realPath;
301 this.unresolvedSymlinkTarget = unresolvedSymlinkTarget;
302 }
303
304 @Override
305 public String toString() {
306 if (type.isSymlink()) {
307 return String.format("(%s: link_value=%s, real_path=%s)", type,
308 unresolvedSymlinkTarget.getPathString(), realPath);
309 } else {
310 return String.format("(%s: real_path=%s)", type, realPath);
311 }
312 }
313 }
314
janakrb77246c2021-03-05 14:41:58 -0800315 @Nullable
janakr491e4412022-01-28 15:35:34 -0800316 private static FileInfo lookUpFileInfo(
317 Environment env, TraversalRequest traversal, SyscallCache syscallCache)
janakrb77246c2021-03-05 14:41:58 -0800318 throws IOException, InterruptedException {
janakr5fb2a482018-03-02 17:48:57 -0800319 if (traversal.isRootGenerated) {
fellyf1e30f32019-07-09 12:26:10 -0700320 HasDigest fsVal = null;
felly5be4dd62018-02-05 11:11:53 -0800321 if (traversal.root.getOutputArtifact() != null) {
322 Artifact artifact = traversal.root.getOutputArtifact();
lberki36df7ed2019-06-27 06:32:03 -0700323 SkyKey artifactKey = Artifact.key(artifact);
felly5be4dd62018-02-05 11:11:53 -0800324 SkyValue value = env.getValue(artifactKey);
325 if (env.valuesMissing()) {
janakrb77246c2021-03-05 14:41:58 -0800326 return null;
felly5be4dd62018-02-05 11:11:53 -0800327 }
kush95bf7c82017-08-30 00:27:35 +0200328
fellyf1e30f32019-07-09 12:26:10 -0700329 if (value instanceof FileArtifactValue || value instanceof TreeArtifactValue) {
330 fsVal = (HasDigest) value;
janakr8541f6d2019-06-11 14:40:21 -0700331 } else if (value instanceof ActionExecutionValue) {
Googleraed41602020-06-02 12:22:53 -0700332 fsVal = ((ActionExecutionValue) value).getExistingFileArtifactValue(artifact);
felly5be4dd62018-02-05 11:11:53 -0800333 } else {
kushb39c6932018-07-12 21:25:23 -0700334 return NON_EXISTENT_FILE_INFO;
felly5be4dd62018-02-05 11:11:53 -0800335 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100336 }
felly5be4dd62018-02-05 11:11:53 -0800337 RootedPath realPath = traversal.root.asRootedPath();
felly6c399d62018-07-18 15:55:59 -0700338 if (traversal.strictOutputFiles) {
339 Preconditions.checkNotNull(fsVal, "Strict Fileset output tree has null FileArtifactValue");
Googlerc8acdbd2018-11-08 10:47:15 -0800340 return new FileInfo(
341 (fsVal instanceof TreeArtifactValue ? FileType.DIRECTORY : FileType.FILE),
jcaterb11c6e22020-04-03 11:40:16 -0700342 fsVal,
343 realPath,
344 null);
felly5be4dd62018-02-05 11:11:53 -0800345 } else {
felly6c399d62018-07-18 15:55:59 -0700346 // FileArtifactValue does not currently track symlinks. If it did, we could potentially
347 // remove some of the filesystem operations we're doing here.
348 Path path = traversal.root.asRootedPath().asPath();
fellyf1e30f32019-07-09 12:26:10 -0700349 FileStateValue fileState =
janakr841c04a2022-02-22 14:36:37 -0800350 FileStateValue.create(traversal.root.asRootedPath(), syscallCache, null);
fellyf1e30f32019-07-09 12:26:10 -0700351 if (fileState.getType() == FileStateType.NONEXISTENT) {
352 throw new IOException("Missing file: " + path);
353 }
felly6c399d62018-07-18 15:55:59 -0700354 FileStatus followStat = path.statIfFound(Symlinks.FOLLOW);
355 FileType type;
356 PathFragment unresolvedLinkTarget = null;
357 if (followStat == null) {
358 type = FileType.DANGLING_SYMLINK;
fellyf1e30f32019-07-09 12:26:10 -0700359 if (fileState.getType() != FileStateType.SYMLINK) {
360 throw new IOException("Expected symlink for " + path + ", but got: " + fileState);
felly6c399d62018-07-18 15:55:59 -0700361 }
362 unresolvedLinkTarget = path.readSymbolicLink();
fellyf1e30f32019-07-09 12:26:10 -0700363 } else if (fileState.getType() == FileStateType.REGULAR_FILE) {
felly6c399d62018-07-18 15:55:59 -0700364 type = FileType.FILE;
fellyf1e30f32019-07-09 12:26:10 -0700365 } else if (fileState.getType() == FileStateType.DIRECTORY) {
felly6c399d62018-07-18 15:55:59 -0700366 type = FileType.DIRECTORY;
367 } else {
368 unresolvedLinkTarget = path.readSymbolicLink();
369 realPath =
370 RootedPath.toRootedPath(
371 Root.absoluteRoot(path.getFileSystem()), path.resolveSymbolicLinks());
372 type = followStat.isFile() ? FileType.SYMLINK_TO_FILE : FileType.SYMLINK_TO_DIRECTORY;
373 }
fellyf1e30f32019-07-09 12:26:10 -0700374 if (fsVal == null) {
375 fsVal = fileState;
376 }
janakr491e4412022-01-28 15:35:34 -0800377 return new FileInfo(
378 type, withDigest(fsVal, path, syscallCache), realPath, unresolvedLinkTarget);
felly5be4dd62018-02-05 11:11:53 -0800379 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100380 } else {
felly5be4dd62018-02-05 11:11:53 -0800381 // Stat the file.
382 FileValue fileValue =
383 (FileValue) env.getValueOrThrow(
384 FileValue.key(traversal.root.asRootedPath()), IOException.class);
385
386 if (env.valuesMissing()) {
janakrb77246c2021-03-05 14:41:58 -0800387 return null;
felly5be4dd62018-02-05 11:11:53 -0800388 }
lberki7598bc62020-10-02 01:33:14 -0700389 if (fileValue.unboundedAncestorSymlinkExpansionChain() != null) {
390 SkyKey uniquenessKey =
391 FileSymlinkInfiniteExpansionUniquenessFunction.key(
392 fileValue.unboundedAncestorSymlinkExpansionChain());
393 env.getValue(uniquenessKey);
394 if (env.valuesMissing()) {
janakrb77246c2021-03-05 14:41:58 -0800395 return null;
lberki7598bc62020-10-02 01:33:14 -0700396 }
397
398 throw new FileSymlinkInfiniteExpansionException(
399 fileValue.pathToUnboundedAncestorSymlinkExpansionChain(),
400 fileValue.unboundedAncestorSymlinkExpansionChain());
401 }
felly5be4dd62018-02-05 11:11:53 -0800402 if (fileValue.exists()) {
403 // If it exists, it may either be a symlink or a file/directory.
404 PathFragment unresolvedLinkTarget = null;
405 FileType type;
406 if (fileValue.isSymlink()) {
407 unresolvedLinkTarget = fileValue.getUnresolvedLinkTarget();
408 type = fileValue.isDirectory() ? FileType.SYMLINK_TO_DIRECTORY : FileType.SYMLINK_TO_FILE;
409 } else {
410 type = fileValue.isDirectory() ? FileType.DIRECTORY : FileType.FILE;
411 }
Googler5284e6c2019-10-30 07:43:54 -0700412 Path path = traversal.root.asRootedPath().asPath();
kush4b120e72018-07-11 16:21:27 -0700413 return new FileInfo(
fellyf1e30f32019-07-09 12:26:10 -0700414 type,
janakr491e4412022-01-28 15:35:34 -0800415 withDigest(fileValue.realFileStateValue(), path, syscallCache),
fellyf1e30f32019-07-09 12:26:10 -0700416 fileValue.realRootedPath(),
417 unresolvedLinkTarget);
felly5be4dd62018-02-05 11:11:53 -0800418 } else {
419 // If it doesn't exist, or it's a dangling symlink, we still want to handle that gracefully.
420 return new FileInfo(
421 fileValue.isSymlink() ? FileType.DANGLING_SYMLINK : FileType.NONEXISTENT,
janakr491e4412022-01-28 15:35:34 -0800422 withDigest(fileValue.realFileStateValue(), null, syscallCache),
kush4b120e72018-07-11 16:21:27 -0700423 null,
kushb39c6932018-07-12 21:25:23 -0700424 fileValue.isSymlink() ? fileValue.getUnresolvedLinkTarget() : null);
felly5be4dd62018-02-05 11:11:53 -0800425 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100426 }
427 }
428
Googler5284e6c2019-10-30 07:43:54 -0700429 /**
430 * Transform the HasDigest to the appropriate type based on the current state of the digest. If
431 * fsVal is type RegularFileStateValue or FileArtifactValue and has a valid digest value, then we
432 * want to convert it to a new FileArtifactValue type. Otherwise if they are of the two
433 * forementioned types but do not have a digest, then we will create a FileArtifactValue using its
434 * {@link Path}. Otherwise we will fingerprint the digest and return it as a new {@link
435 * HasDigest.ByteStringDigest} object.
436 *
437 * @param fsVal - the HasDigest value that was in the graph.
438 * @param path - the Path of the digest.
439 * @return transformed HasDigest value based on the digest field and object type.
440 */
441 @VisibleForTesting
janakre2853222022-03-08 10:52:18 -0800442 static HasDigest withDigest(HasDigest fsVal, Path path, XattrProvider syscallCache)
janakr491e4412022-01-28 15:35:34 -0800443 throws IOException {
fellyf1e30f32019-07-09 12:26:10 -0700444 if (fsVal instanceof FileStateValue) {
Googler5284e6c2019-10-30 07:43:54 -0700445 FileStateValue fsv = (FileStateValue) fsVal;
446 if (fsv instanceof RegularFileStateValue) {
447 RegularFileStateValue rfsv = (RegularFileStateValue) fsv;
448 return rfsv.getDigest() != null
449 // If we have the digest, then simply convert it with the digest value.
450 ? FileArtifactValue.createForVirtualActionInput(rfsv.getDigest(), rfsv.getSize())
451 // Otherwise, create a file FileArtifactValue (RegularFileArtifactValue) based on the
452 // path and size.
janakr491e4412022-01-28 15:35:34 -0800453 : FileArtifactValue.createForNormalFileUsingPath(path, rfsv.getSize(), syscallCache);
Googler5284e6c2019-10-30 07:43:54 -0700454 }
janakre430dc02021-04-28 12:28:57 -0700455 return new HasDigest.ByteStringDigest(fsv.getValueFingerprint());
fellyf1e30f32019-07-09 12:26:10 -0700456 } else if (fsVal instanceof FileArtifactValue) {
Googler5284e6c2019-10-30 07:43:54 -0700457 FileArtifactValue fav = ((FileArtifactValue) fsVal);
458 if (fav.getDigest() != null) {
459 return fav;
460 }
461
462 // In the case there is a directory, the HasDigest value should not be converted. Otherwise,
463 // if the HasDigest value is a file, convert it using the Path and size values.
464 return fav.getType().isFile()
janakr491e4412022-01-28 15:35:34 -0800465 ? FileArtifactValue.createForNormalFileUsingPath(path, fav.getSize(), syscallCache)
janakre430dc02021-04-28 12:28:57 -0700466 : new HasDigest.ByteStringDigest(fav.getValueFingerprint());
fellyf1e30f32019-07-09 12:26:10 -0700467 }
468 return fsVal;
469 }
470
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100471 private static final class PkgLookupResult {
472 private enum Type {
473 CONFLICT, DIRECTORY, PKG
474 }
475
476 private final Type type;
477 final TraversalRequest traversal;
478 final FileInfo rootInfo;
479
480 /** Result for a generated directory that conflicts with a source package. */
481 static PkgLookupResult conflict(TraversalRequest traversal, FileInfo rootInfo) {
482 return new PkgLookupResult(Type.CONFLICT, traversal, rootInfo);
483 }
484
485 /** Result for a source or generated directory (not a package). */
486 static PkgLookupResult directory(TraversalRequest traversal, FileInfo rootInfo) {
487 return new PkgLookupResult(Type.DIRECTORY, traversal, rootInfo);
488 }
489
490 /** Result for a package, i.e. a directory with a BUILD file. */
491 static PkgLookupResult pkg(TraversalRequest traversal, FileInfo rootInfo) {
492 return new PkgLookupResult(Type.PKG, traversal, rootInfo);
493 }
494
495 private PkgLookupResult(Type type, TraversalRequest traversal, FileInfo rootInfo) {
496 this.type = Preconditions.checkNotNull(type);
497 this.traversal = Preconditions.checkNotNull(traversal);
498 this.rootInfo = Preconditions.checkNotNull(rootInfo);
499 }
500
501 boolean isPackage() {
502 return type == Type.PKG;
503 }
504
505 boolean isConflicting() {
506 return type == Type.CONFLICT;
507 }
508
509 @Override
510 public String toString() {
511 return String.format("(%s: info=%s, traversal=%s)", type, rootInfo, traversal);
512 }
513 }
514
515 /**
516 * Checks whether the {@code traversal}'s path refers to a package directory.
517 *
518 * @return the result of the lookup; it contains potentially new {@link TraversalRequest} and
519 * {@link FileInfo} so the caller should use these instead of the old ones (this happens when
520 * a package is found, but under a different root than expected)
521 */
Janak Ramakrishnan3c0adb22016-08-15 21:54:55 +0000522 private static PkgLookupResult checkIfPackage(
janakr491e4412022-01-28 15:35:34 -0800523 Environment env, TraversalRequest traversal, FileInfo rootInfo, SyscallCache syscallCache)
janakrb77246c2021-03-05 14:41:58 -0800524 throws IOException, InterruptedException, BuildFileNotFoundException {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100525 Preconditions.checkArgument(rootInfo.type.exists() && !rootInfo.type.isFile(),
526 "{%s} {%s}", traversal, rootInfo);
janakrb77246c2021-03-05 14:41:58 -0800527 // PackageLookupFunction/dependencies can only throw IOException, BuildFileNotFoundException,
528 // and RepositoryFetchException, and RepositoryFetchException is not in play here. Note that
529 // run-of-the-mill circular symlinks will *not* throw here, and will trigger later errors during
530 // the recursive traversal.
tomlu8cc5dcf2018-01-19 09:28:06 -0800531 PackageLookupValue pkgLookup =
532 (PackageLookupValue)
janakrb77246c2021-03-05 14:41:58 -0800533 env.getValueOrThrow(
534 PackageLookupValue.key(traversal.root.asRootedPath().getRootRelativePath()),
535 BuildFileNotFoundException.class,
536 IOException.class);
537 if (env.valuesMissing()) {
538 return null;
539 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100540
541 if (pkgLookup.packageExists()) {
janakr5fb2a482018-03-02 17:48:57 -0800542 if (traversal.isRootGenerated) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100543 // The traversal's root was a generated directory, but its root-relative path conflicts with
544 // an existing package.
545 return PkgLookupResult.conflict(traversal, rootInfo);
546 } else {
547 // The traversal's root was a source directory and it defines a package.
tomluee6a6862018-01-17 14:36:26 -0800548 Root pkgRoot = pkgLookup.getRoot();
felly5be4dd62018-02-05 11:11:53 -0800549 if (!pkgRoot.equals(traversal.root.asRootedPath().getRoot())) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100550 // However the root of this package is different from what we expected. stat() the real
551 // BUILD file of that package.
552 traversal = traversal.forChangedRootPath(pkgRoot);
janakr491e4412022-01-28 15:35:34 -0800553 rootInfo = lookUpFileInfo(env, traversal, syscallCache);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100554 Verify.verify(rootInfo.type.exists(), "{%s} {%s}", traversal, rootInfo);
555 }
556 return PkgLookupResult.pkg(traversal, rootInfo);
557 }
558 } else {
559 // The traversal's root was a directory (source or generated one), no package exists under the
560 // same root-relative path.
561 return PkgLookupResult.directory(traversal, rootInfo);
562 }
563 }
564
565 /**
566 * List the directory and create {@code SkyKey}s to request contents of its children recursively.
567 *
568 * <p>The returned keys are of type {@link SkyFunctions#RECURSIVE_FILESYSTEM_TRAVERSAL}.
569 */
janakrb77246c2021-03-05 14:41:58 -0800570 @Nullable
Janak Ramakrishnan3c0adb22016-08-15 21:54:55 +0000571 private static Collection<SkyKey> createRecursiveTraversalKeys(
janakrb77246c2021-03-05 14:41:58 -0800572 Environment env, TraversalRequest traversal) throws InterruptedException, IOException {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100573 // Use the traversal's path, even if it's a symlink. The contents of the directory, as listed
574 // in the result, must be relative to it.
felly5be4dd62018-02-05 11:11:53 -0800575 Iterable<Dirent> dirents;
janakr5fb2a482018-03-02 17:48:57 -0800576 if (traversal.isRootGenerated) {
felly5be4dd62018-02-05 11:11:53 -0800577 // If we're dealing with an output file, read the directory directly instead of creating
578 // filesystem nodes under the output tree.
579 List<Dirent> direntsCollection =
580 new ArrayList<>(
581 traversal.root.asRootedPath().asPath().readdir(Symlinks.FOLLOW));
582 Collections.sort(direntsCollection);
583 dirents = direntsCollection;
584 } else {
janakrb77246c2021-03-05 14:41:58 -0800585 DirectoryListingValue dirListingValue =
586 (DirectoryListingValue)
587 env.getValueOrThrow(
588 DirectoryListingValue.key(traversal.root.asRootedPath()), IOException.class);
589 if (dirListingValue == null) {
590 return null;
591 }
592 dirents = dirListingValue.getDirents();
felly5be4dd62018-02-05 11:11:53 -0800593 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100594
595 List<SkyKey> result = new ArrayList<>();
felly5be4dd62018-02-05 11:11:53 -0800596 for (Dirent dirent : dirents) {
tomlu8cc5dcf2018-01-19 09:28:06 -0800597 RootedPath childPath =
598 RootedPath.toRootedPath(
felly5be4dd62018-02-05 11:11:53 -0800599 traversal.root.asRootedPath().getRoot(),
600 traversal.root.asRootedPath().getRootRelativePath().getRelative(dirent.getName()));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100601 TraversalRequest childTraversal = traversal.forChildEntry(childPath);
janakr5fb2a482018-03-02 17:48:57 -0800602 result.add(childTraversal);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100603 }
604 return result;
605 }
606
607 /**
608 * Creates result for a dangling symlink.
609 *
610 * @param linkName path to the symbolic link
611 * @param info the {@link FileInfo} associated with the link file
612 */
613 private static RecursiveFilesystemTraversalValue resultForDanglingSymlink(RootedPath linkName,
614 FileInfo info) {
615 Preconditions.checkState(info.type.isSymlink() && !info.type.exists(), "{%s} {%s}", linkName,
616 info.type);
617 return RecursiveFilesystemTraversalValue.of(
kushb39c6932018-07-12 21:25:23 -0700618 ResolvedFileFactory.danglingSymlink(linkName, info.unresolvedSymlinkTarget, info.metadata));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100619 }
620
621 /**
622 * Creates results for a file or for a symlink that points to one.
623 *
624 * <p>A symlink may be direct (points to a file) or transitive (points at a direct or transitive
625 * symlink).
626 */
627 private static RecursiveFilesystemTraversalValue resultForFileRoot(RootedPath path,
628 FileInfo info) {
629 Preconditions.checkState(info.type.isFile() && info.type.exists(), "{%s} {%s}", path,
630 info.type);
631 if (info.type.isSymlink()) {
Laszlo Csomorb4d482b2015-12-04 13:23:54 +0000632 return RecursiveFilesystemTraversalValue.of(
633 ResolvedFileFactory.symlinkToFile(
kushb39c6932018-07-12 21:25:23 -0700634 info.realPath, path, info.unresolvedSymlinkTarget, info.metadata));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100635 } else {
Laszlo Csomorb4d482b2015-12-04 13:23:54 +0000636 return RecursiveFilesystemTraversalValue.of(
kushb39c6932018-07-12 21:25:23 -0700637 ResolvedFileFactory.regularFile(path, info.metadata));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100638 }
639 }
640
641 private static RecursiveFilesystemTraversalValue resultForDirectory(TraversalRequest traversal,
642 FileInfo rootInfo, Collection<RecursiveFilesystemTraversalValue> subdirTraversals) {
643 // Collect transitive closure of files in subdirectories.
644 NestedSetBuilder<ResolvedFile> paths = NestedSetBuilder.stableOrder();
645 for (RecursiveFilesystemTraversalValue child : subdirTraversals) {
646 paths.addTransitive(child.getTransitiveFiles());
647 }
648 ResolvedFile root;
649 if (rootInfo.type.isSymlink()) {
Laszlo Csomor207140f2015-12-07 15:07:33 +0000650 NestedSet<ResolvedFile> children = paths.build();
Laszlo Csomorb4d482b2015-12-04 13:23:54 +0000651 root =
652 ResolvedFileFactory.symlinkToDirectory(
653 rootInfo.realPath,
felly5be4dd62018-02-05 11:11:53 -0800654 traversal.root.asRootedPath(),
Laszlo Csomorb4d482b2015-12-04 13:23:54 +0000655 rootInfo.unresolvedSymlinkTarget,
kushb39c6932018-07-12 21:25:23 -0700656 hashDirectorySymlink(children, rootInfo.metadata));
Laszlo Csomor207140f2015-12-07 15:07:33 +0000657 paths = NestedSetBuilder.<ResolvedFile>stableOrder().addTransitive(children).add(root);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100658 } else {
Laszlo Csomorb4d482b2015-12-04 13:23:54 +0000659 root = ResolvedFileFactory.directory(rootInfo.realPath);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100660 }
661 return RecursiveFilesystemTraversalValue.of(root, paths.build());
662 }
663
fellyf1e30f32019-07-09 12:26:10 -0700664 private static HasDigest hashDirectorySymlink(
ulfjack61216fd2019-12-18 12:31:03 -0800665 NestedSet<ResolvedFile> children, HasDigest metadata) {
Laszlo Csomor207140f2015-12-07 15:07:33 +0000666 // If the root is a directory symlink, the associated FileStateValue does not change when the
667 // linked directory's contents change, so we can't use the FileStateValue as metadata like we
668 // do with other ResolvedFile kinds. Instead we compute a metadata hash from the child
669 // elements and return that as the ResolvedFile's metadata hash.
fellyf1e30f32019-07-09 12:26:10 -0700670 Fingerprint fp = new Fingerprint();
671 fp.addBytes(metadata.getDigest());
ulfjack61216fd2019-12-18 12:31:03 -0800672 for (ResolvedFile file : children.toList()) {
fellyf1e30f32019-07-09 12:26:10 -0700673 fp.addPath(file.getNameInSymlinkTree());
674 fp.addBytes(file.getMetadata().getDigest());
Laszlo Csomor207140f2015-12-07 15:07:33 +0000675 }
fellyf1e30f32019-07-09 12:26:10 -0700676 byte[] result = fp.digestAndReset();
677 return new HasDigest.ByteStringDigest(result);
Laszlo Csomor207140f2015-12-07 15:07:33 +0000678 }
679
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100680 /**
681 * Requests Skyframe to compute the dependent values and returns them.
682 *
683 * <p>The keys must all be {@link SkyFunctions#RECURSIVE_FILESYSTEM_TRAVERSAL} keys.
684 */
janakrb77246c2021-03-05 14:41:58 -0800685 @Nullable
felly5be4dd62018-02-05 11:11:53 -0800686 private Collection<RecursiveFilesystemTraversalValue> traverseChildren(
687 Environment env, Iterable<SkyKey> keys, boolean inline)
janakrb77246c2021-03-05 14:41:58 -0800688 throws InterruptedException, RecursiveFilesystemTraversalFunctionException {
felly5be4dd62018-02-05 11:11:53 -0800689 Map<SkyKey, SkyValue> values;
690 if (inline) {
691 // Don't create Skyframe nodes for a recursive traversal over the output tree.
692 // Instead, inline the recursion in the top-level request.
693 values = new HashMap<>();
694 for (SkyKey depKey : keys) {
695 values.put(depKey, compute(depKey, env));
696 }
697 } else {
698 values = env.getValues(keys);
699 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100700 if (env.valuesMissing()) {
janakrb77246c2021-03-05 14:41:58 -0800701 return null;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100702 }
felly5be4dd62018-02-05 11:11:53 -0800703
kushb39c6932018-07-12 21:25:23 -0700704 return Collections2.transform(values.values(), RecursiveFilesystemTraversalValue.class::cast);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100705 }
706
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100707}