blob: 6adf32f03df5b93ecc32045ce3e88701a4a52d82 [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
Nathan Harmata808217c2015-10-12 22:07:19 +000016import com.google.common.base.Preconditions;
Janak Ramakrishnandf0531f2015-09-23 17:30:04 +000017import com.google.common.base.Predicate;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010018import com.google.common.collect.ImmutableList;
Nathan Harmataad810502015-07-29 01:33:49 +000019import com.google.common.collect.Iterables;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010020import com.google.common.collect.Sets;
21import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
22import com.google.devtools.build.lib.util.Pair;
Nathan Harmatada692512015-03-25 17:02:30 +000023import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010024import com.google.devtools.build.lib.vfs.Path;
25import com.google.devtools.build.lib.vfs.PathFragment;
26import com.google.devtools.build.lib.vfs.RootedPath;
27import com.google.devtools.build.skyframe.SkyFunction;
28import com.google.devtools.build.skyframe.SkyFunctionException;
29import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
30import com.google.devtools.build.skyframe.SkyKey;
31import com.google.devtools.build.skyframe.SkyValue;
32
Nathan Harmatada692512015-03-25 17:02:30 +000033import java.io.IOException;
Nathan Harmataad810502015-07-29 01:33:49 +000034import java.util.ArrayList;
35import java.util.TreeSet;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010036import java.util.concurrent.atomic.AtomicReference;
37
38import javax.annotation.Nullable;
39
40/**
41 * A {@link SkyFunction} for {@link FileValue}s.
42 *
43 * <p>Most of the complexity in the implementation is associated to handling symlinks. Namely,
44 * this class makes sure that {@code FileValue}s corresponding to symlinks are correctly invalidated
45 * if the destination of the symlink is invalidated. Directory symlinks are also covered.
46 */
47public class FileFunction implements SkyFunction {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010048 private final AtomicReference<PathPackageLocator> pkgLocator;
Nathan Harmatada692512015-03-25 17:02:30 +000049 private final TimestampGranularityMonitor tsgm;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010050 private final ExternalFilesHelper externalFilesHelper;
51
52 public FileFunction(AtomicReference<PathPackageLocator> pkgLocator,
Nathan Harmatada692512015-03-25 17:02:30 +000053 TimestampGranularityMonitor tsgm,
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010054 ExternalFilesHelper externalFilesHelper) {
55 this.pkgLocator = pkgLocator;
Nathan Harmatada692512015-03-25 17:02:30 +000056 this.tsgm = tsgm;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010057 this.externalFilesHelper = externalFilesHelper;
58 }
59
60 @Override
61 public SkyValue compute(SkyKey skyKey, Environment env) throws FileFunctionException {
62 RootedPath rootedPath = (RootedPath) skyKey.argument();
Nathan Harmata5fb10732015-09-29 22:59:02 +000063 RootedPath realRootedPath = null;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010064 FileStateValue realFileStateValue = null;
65 PathFragment relativePath = rootedPath.getRelativePath();
66
67 // Resolve ancestor symlinks, but only if the current file is not the filesystem root (has no
68 // parent) or a package path root (treated opaquely and handled by skyframe's DiffAwareness
Nathan Harmatada692512015-03-25 17:02:30 +000069 // interface). Note that this is the first thing we do - if an ancestor is part of a
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010070 // symlink cycle, we want to detect that quickly as it gives a more informative error message
71 // than we'd get doing bogus filesystem operations.
Nathan Harmatada692512015-03-25 17:02:30 +000072 if (!relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010073 Pair<RootedPath, FileStateValue> resolvedState =
74 resolveFromAncestors(rootedPath, env);
75 if (resolvedState == null) {
76 return null;
77 }
78 realRootedPath = resolvedState.getFirst();
79 realFileStateValue = resolvedState.getSecond();
80 }
81
82 FileStateValue fileStateValue = (FileStateValue) env.getValue(FileStateValue.key(rootedPath));
83 if (fileStateValue == null) {
84 return null;
85 }
86 if (realFileStateValue == null) {
Nathan Harmata5fb10732015-09-29 22:59:02 +000087 realRootedPath = rootedPath;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010088 realFileStateValue = fileStateValue;
Nathan Harmata5fb10732015-09-29 22:59:02 +000089 } else if (rootedPath.equals(realRootedPath) && !fileStateValue.equals(realFileStateValue)) {
90 String message = String.format(
91 "Some filesystem operations implied %s was a %s but others made us think it was a %s",
92 rootedPath.asPath().getPathString(),
93 fileStateValue.prettyPrint(),
94 realFileStateValue.prettyPrint());
95 throw new FileFunctionException(new InconsistentFilesystemException(message),
96 Transience.TRANSIENT);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +010097 }
98
Nathan Harmataad810502015-07-29 01:33:49 +000099 ArrayList<RootedPath> symlinkChain = new ArrayList<>();
100 TreeSet<Path> orderedSeenPaths = Sets.newTreeSet();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100101 while (realFileStateValue.getType().equals(FileStateValue.Type.SYMLINK)) {
Nathan Harmataad810502015-07-29 01:33:49 +0000102 symlinkChain.add(realRootedPath);
103 orderedSeenPaths.add(realRootedPath.asPath());
Nathan Harmatada692512015-03-25 17:02:30 +0000104 if (externalFilesHelper.shouldAssumeImmutable(realRootedPath)) {
105 // If the file is assumed to be immutable, we want to resolve the symlink chain without
106 // adding dependencies since we don't care about incremental correctness.
107 try {
108 Path realPath = rootedPath.asPath().resolveSymbolicLinks();
109 realRootedPath = RootedPath.toRootedPathMaybeUnderRoot(realPath,
110 pkgLocator.get().getPathEntries());
111 realFileStateValue = FileStateValue.create(realRootedPath, tsgm);
112 } catch (IOException e) {
Lukacs Berki05c5daa2015-08-28 07:40:04 +0000113 RootedPath root = RootedPath.toRootedPath(
114 rootedPath.asPath().getFileSystem().getRootDirectory(),
115 rootedPath.asPath().getFileSystem().getRootDirectory());
116 return FileValue.value(
117 rootedPath, fileStateValue,
118 root, FileStateValue.NONEXISTENT_FILE_STATE_NODE);
Nathan Harmatada692512015-03-25 17:02:30 +0000119 } catch (InconsistentFilesystemException e) {
120 throw new FileFunctionException(e, Transience.TRANSIENT);
121 }
122 } else {
123 Pair<RootedPath, FileStateValue> resolvedState = getSymlinkTargetRootedPath(realRootedPath,
Nathan Harmataad810502015-07-29 01:33:49 +0000124 realFileStateValue.getSymlinkTarget(), orderedSeenPaths, symlinkChain, env);
Nathan Harmatada692512015-03-25 17:02:30 +0000125 if (resolvedState == null) {
126 return null;
127 }
128 realRootedPath = resolvedState.getFirst();
129 realFileStateValue = resolvedState.getSecond();
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100130 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100131 }
132 return FileValue.value(rootedPath, fileStateValue, realRootedPath, realFileStateValue);
133 }
134
135 /**
136 * Returns the path and file state of {@code rootedPath}, accounting for ancestor symlinks, or
137 * {@code null} if there was a missing dep.
138 */
139 @Nullable
140 private Pair<RootedPath, FileStateValue> resolveFromAncestors(RootedPath rootedPath,
141 Environment env) throws FileFunctionException {
142 PathFragment relativePath = rootedPath.getRelativePath();
143 RootedPath realRootedPath = rootedPath;
144 FileValue parentFileValue = null;
Nathan Harmatada692512015-03-25 17:02:30 +0000145 // We only resolve ancestors if the file is not assumed to be immutable (handling ancestors
146 // would be too aggressive).
147 if (!externalFilesHelper.shouldAssumeImmutable(rootedPath)
148 && !relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100149 RootedPath parentRootedPath = RootedPath.toRootedPath(rootedPath.getRoot(),
150 relativePath.getParentDirectory());
151 parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
152 if (parentFileValue == null) {
153 return null;
154 }
155 PathFragment baseName = new PathFragment(relativePath.getBaseName());
156 RootedPath parentRealRootedPath = parentFileValue.realRootedPath();
157 realRootedPath = RootedPath.toRootedPath(parentRealRootedPath.getRoot(),
158 parentRealRootedPath.getRelativePath().getRelative(baseName));
Nathan Harmata96be0c12015-09-11 22:15:50 +0000159 if (!parentFileValue.exists()) {
Ulf Adams8cef2f92015-10-19 10:37:42 +0000160 return Pair.<RootedPath, FileStateValue>of(
161 realRootedPath, FileStateValue.NONEXISTENT_FILE_STATE_NODE);
Nathan Harmata96be0c12015-09-11 22:15:50 +0000162 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100163 }
164 FileStateValue realFileStateValue =
165 (FileStateValue) env.getValue(FileStateValue.key(realRootedPath));
166 if (realFileStateValue == null) {
167 return null;
168 }
169 if (realFileStateValue.getType() != FileStateValue.Type.NONEXISTENT
170 && parentFileValue != null && !parentFileValue.isDirectory()) {
171 String type = realFileStateValue.getType().toString().toLowerCase();
172 String message = type + " " + rootedPath.asPath() + " exists but its parent "
Nathan Harmata96be0c12015-09-11 22:15:50 +0000173 + "path " + parentFileValue.realRootedPath().asPath() + " isn't an existing directory.";
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100174 throw new FileFunctionException(new InconsistentFilesystemException(message),
175 Transience.TRANSIENT);
176 }
177 return Pair.of(realRootedPath, realFileStateValue);
178 }
179
180 /**
181 * Returns the symlink target and file state of {@code rootedPath}'s symlink to
182 * {@code symlinkTarget}, accounting for ancestor symlinks, or {@code null} if there was a
183 * missing dep.
184 */
185 @Nullable
186 private Pair<RootedPath, FileStateValue> getSymlinkTargetRootedPath(RootedPath rootedPath,
Nathan Harmataad810502015-07-29 01:33:49 +0000187 PathFragment symlinkTarget, TreeSet<Path> orderedSeenPaths,
188 Iterable<RootedPath> symlinkChain, Environment env) throws FileFunctionException {
189 RootedPath symlinkTargetRootedPath;
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100190 if (symlinkTarget.isAbsolute()) {
191 Path path = rootedPath.asPath().getFileSystem().getRootDirectory().getRelative(
192 symlinkTarget);
Nathan Harmataad810502015-07-29 01:33:49 +0000193 symlinkTargetRootedPath =
194 RootedPath.toRootedPathMaybeUnderRoot(path, pkgLocator.get().getPathEntries());
195 } else {
196 Path path = rootedPath.asPath();
197 Path symlinkTargetPath;
198 if (path.getParentDirectory() != null) {
199 RootedPath parentRootedPath = RootedPath.toRootedPathMaybeUnderRoot(
200 path.getParentDirectory(), pkgLocator.get().getPathEntries());
201 FileValue parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
202 if (parentFileValue == null) {
203 return null;
204 }
205 symlinkTargetPath = parentFileValue.realRootedPath().asPath().getRelative(symlinkTarget);
206 } else {
207 // This means '/' is a symlink to 'symlinkTarget'.
208 symlinkTargetPath = path.getRelative(symlinkTarget);
209 }
210 symlinkTargetRootedPath = RootedPath.toRootedPathMaybeUnderRoot(symlinkTargetPath,
211 pkgLocator.get().getPathEntries());
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100212 }
Nathan Harmata808217c2015-10-12 22:07:19 +0000213 // Suppose we have a symlink chain p -> p1 -> p2 -> ... pK. We want to determine the fully
214 // resolved path, if any, of p. This entails following the chain and noticing if there's a
215 // symlink issue. There three sorts of issues:
216 // (i) Symlink cycle:
217 // p -> p1 -> p2 -> p1
218 // (ii) Unbounded expansion caused by a symlink to a descendant of a member of the chain:
219 // p -> a/b -> c/d -> a/b/e
220 // (iii) Unbounded expansion caused by a symlink to an ancestor of a member of the chain:
221 // p -> a/b -> c/d -> a
Shreya Bhattaraif87a4142015-10-09 19:48:11 +0000222 //
Nathan Harmata808217c2015-10-12 22:07:19 +0000223 // We can detect all three of these symlink issues by following the chain and deciding if each
224 // new element is problematic. Here is our incremental algorithm:
225 //
226 // Suppose we encounter the symlink target p and we have already encountered all the paths in P:
227 // If p is in P then we have a found a cycle (i).
228 // If p is a descendant of any path p' in P then we have unbounded expansion (ii).
229 // If p is an ancestor of any path p' in P then we have unbounded expansion (iii).
230 // We can check for these cases efficiently (read: sublinear time) by finding the extremal
231 // candidate p' for (ii) and (iii).
232 Path symlinkTargetPath = symlinkTargetRootedPath.asPath();
233 SkyKey uniquenessKey = null;
234 FileSymlinkException fse = null;
235 Path seenFloorPath = orderedSeenPaths.floor(symlinkTargetPath);
236 Path seenCeilingPath = orderedSeenPaths.ceiling(symlinkTargetPath);
237 if (orderedSeenPaths.contains(symlinkTargetPath)) {
238 // 'rootedPath' is a symlink to a previous element in the symlink chain (i).
239 Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
240 CycleUtils.splitIntoPathAndChain(
241 isPathPredicate(symlinkTargetRootedPath.asPath()), symlinkChain);
242 FileSymlinkCycleException fsce =
243 new FileSymlinkCycleException(pathAndChain.getFirst(), pathAndChain.getSecond());
244 uniquenessKey = FileSymlinkCycleUniquenessFunction.key(fsce.getCycle());
245 fse = fsce;
246 } else if (seenFloorPath != null && symlinkTargetPath.startsWith(seenFloorPath)) {
247 // 'rootedPath' is a symlink to a descendant of a previous element in the symlink chain (ii).
248 Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
249 CycleUtils.splitIntoPathAndChain(
250 isPathPredicate(seenFloorPath),
251 ImmutableList.copyOf(
252 Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
253 uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
254 fse = new FileSymlinkInfiniteExpansionException(
255 pathAndChain.getFirst(), pathAndChain.getSecond());
256 } else if (seenCeilingPath != null && seenCeilingPath.startsWith(symlinkTargetPath)) {
257 // 'rootedPath' is a symlink to an ancestor of a previous element in the symlink chain (iii).
258 Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
259 CycleUtils.splitIntoPathAndChain(
260 isPathPredicate(seenCeilingPath),
261 ImmutableList.copyOf(
262 Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
263 uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
264 fse = new FileSymlinkInfiniteExpansionException(
265 pathAndChain.getFirst(), pathAndChain.getSecond());
266 }
267 if (uniquenessKey != null) {
Nathan Harmataad810502015-07-29 01:33:49 +0000268 if (env.getValue(uniquenessKey) == null) {
269 // Note that this dependency is merely to ensure that each unique symlink error gets
270 // reported exactly once.
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100271 return null;
272 }
Nathan Harmata808217c2015-10-12 22:07:19 +0000273 throw new FileFunctionException(Preconditions.checkNotNull(fse, rootedPath));
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100274 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100275 return resolveFromAncestors(symlinkTargetRootedPath, env);
276 }
277
Janak Ramakrishnandf0531f2015-09-23 17:30:04 +0000278 private static final Predicate<RootedPath> isPathPredicate(final Path path) {
279 return new Predicate<RootedPath>() {
280 @Override
281 public boolean apply(RootedPath rootedPath) {
282 return rootedPath.asPath().equals(path);
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100283 }
Janak Ramakrishnandf0531f2015-09-23 17:30:04 +0000284 };
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100285 }
286
287 @Nullable
288 @Override
289 public String extractTag(SkyKey skyKey) {
290 return null;
291 }
292
293 /**
294 * Used to declare all the exception types that can be wrapped in the exception thrown by
295 * {@link FileFunction#compute}.
296 */
297 private static final class FileFunctionException extends SkyFunctionException {
298
299 public FileFunctionException(InconsistentFilesystemException e, Transience transience) {
300 super(e, transience);
301 }
302
Nathan Harmataad810502015-07-29 01:33:49 +0000303 public FileFunctionException(FileSymlinkException e) {
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100304 super(e, Transience.PERSISTENT);
305 }
Han-Wen Nienhuysd08b27f2015-02-25 16:45:20 +0100306 }
307}