Elegantly handle unbounded file symlink resolutions, e.g. 'a' -> 'b' -> 'a/nope'.

--
MOS_MIGRATED_REVID=99337668

17 files changed, 387 insertions, 116 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
index 72e3afc541..fbf3870f09 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ASTFileLookupFunction.java
@@ -140,8 +140,8 @@ public class ASTFileLookupFunction implements SkyFunction {
       FileValue fileValue = null;
       try {
         fileValue = (FileValue) env.getValueOrThrow(fileSkyKey, IOException.class,
-            FileSymlinkCycleException.class, InconsistentFilesystemException.class);
-      } catch (IOException | FileSymlinkCycleException e) {
+            FileSymlinkException.class, InconsistentFilesystemException.class);
+      } catch (IOException | FileSymlinkException e) {
         throw new ASTLookupFunctionException(new ErrorReadingSkylarkExtensionException(
             e.getMessage()), Transience.PERSISTENT);
       } catch (InconsistentFilesystemException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessFunction.java
new file mode 100644
index 0000000000..5cd698c7ae
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessFunction.java
@@ -0,0 +1,51 @@
+// Copyright 2014 Google Inc. 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.skyframe;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+abstract class AbstractFileSymlinkExceptionUniquenessFunction implements SkyFunction {
+  protected abstract String getConciseDescription();
+  protected abstract String getHeaderMessage();
+  protected abstract String getFooterMessage();
+  protected abstract SkyValue getDummyValue();
+
+  @Override
+  public SkyValue compute(SkyKey skyKey, Environment env) {
+    StringBuilder errorMessage = new StringBuilder();
+    errorMessage.append(getConciseDescription() + " detected\n");
+    errorMessage.append(getHeaderMessage() + "\n");
+    @SuppressWarnings("unchecked")
+    ImmutableList<RootedPath> chain = (ImmutableList<RootedPath>) skyKey.argument();
+    for (RootedPath rootedPath : chain) {
+      errorMessage.append(rootedPath.asPath() + "\n");
+    }
+    errorMessage.append(getFooterMessage() + "\n");
+    // The purpose of this SkyFunction is the side effect of emitting an error message exactly
+    // once per build per unique symlink error.
+    env.getListener().handle(Event.error(errorMessage.toString()));
+    return getDummyValue();
+  }
+
+  @Override
+  public String extractTag(SkyKey skyKey) {
+    return null;
+  }
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessValue.java
new file mode 100644
index 0000000000..39c20cc534
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AbstractFileSymlinkExceptionUniquenessValue.java
@@ -0,0 +1,52 @@
+// Copyright 2014 Google Inc. 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.skyframe;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/**
+ * A value for ensuring that a file symlink error is reported exactly once. This is achieved by
+ * forcing the same value key for two logically equivalent errors and letting Skyframe do its
+ * magic.
+ */
+class AbstractFileSymlinkExceptionUniquenessValue implements SkyValue {
+  protected static SkyKey key(SkyFunctionName functionName, ImmutableList<RootedPath> chain) {
+    Preconditions.checkState(!chain.isEmpty());
+    return new SkyKey(functionName, canonicalize(chain));
+  }
+
+  private static ImmutableList<RootedPath> canonicalize(ImmutableList<RootedPath> cycle) {
+    int minPos = 0;
+    String minString = cycle.get(0).toString();
+    for (int i = 1; i < cycle.size(); i++) {
+      String candidateString = cycle.get(i).toString();
+      if (candidateString.compareTo(minString) < 0) {
+        minPos = i;
+        minString = candidateString;
+      }
+    }
+    ImmutableList.Builder<RootedPath> builder = ImmutableList.builder();
+    for (int i = 0; i < cycle.size(); i++) {
+      int pos = (minPos + i) % cycle.size();
+      builder.add(cycle.get(pos));
+    }
+    return builder.build();
+  }
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
index e277476bd6..be4a010063 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactFunction.java
@@ -98,8 +98,8 @@ class ArtifactFunction implements SkyFunction {
     FileValue fileValue;
     try {
       fileValue = (FileValue) env.getValueOrThrow(fileSkyKey, IOException.class,
-          InconsistentFilesystemException.class, FileSymlinkCycleException.class);
-    } catch (IOException | InconsistentFilesystemException | FileSymlinkCycleException e) {
+          InconsistentFilesystemException.class, FileSymlinkException.class);
+    } catch (IOException | InconsistentFilesystemException | FileSymlinkException e) {
       throw makeMissingInputFileExn(artifact, mandatory, e, env.getListener());
     }
     if (fileValue == null) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
index 1ca8588fab..ecccc075d1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.util.Pair;
@@ -28,7 +29,8 @@ import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
 import java.io.IOException;
-import java.util.LinkedHashSet;
+import java.util.ArrayList;
+import java.util.TreeSet;
 import java.util.concurrent.atomic.AtomicReference;
 
 import javax.annotation.Nullable;
@@ -41,7 +43,6 @@ import javax.annotation.Nullable;
  * if the destination of the symlink is invalidated. Directory symlinks are also covered.
  */
 public class FileFunction implements SkyFunction {
-
   private final AtomicReference<PathPackageLocator> pkgLocator;
   private final TimestampGranularityMonitor tsgm;
   private final ExternalFilesHelper externalFilesHelper;
@@ -84,19 +85,11 @@ public class FileFunction implements SkyFunction {
       realFileStateValue = fileStateValue;
     }
 
-    LinkedHashSet<RootedPath> seenPaths = Sets.newLinkedHashSet();
+    ArrayList<RootedPath> symlinkChain = new ArrayList<>();
+    TreeSet<Path> orderedSeenPaths = Sets.newTreeSet();
     while (realFileStateValue.getType().equals(FileStateValue.Type.SYMLINK)) {
-      if (!seenPaths.add(realRootedPath)) {
-        FileSymlinkCycleException fileSymlinkCycleException =
-            makeFileSymlinkCycleException(realRootedPath, seenPaths);
-        if (env.getValue(FileSymlinkCycleUniquenessValue.key(fileSymlinkCycleException.getCycle()))
-            == null) {
-          // Note that this dependency is merely to ensure that each unique cycle gets reported
-          // exactly once.
-          return null;
-        }
-        throw new FileFunctionException(fileSymlinkCycleException);
-      }
+      symlinkChain.add(realRootedPath);
+      orderedSeenPaths.add(realRootedPath.asPath());
       if (externalFilesHelper.shouldAssumeImmutable(realRootedPath)) {
         // If the file is assumed to be immutable, we want to resolve the symlink chain without
         // adding dependencies since we don't care about incremental correctness.
@@ -112,7 +105,7 @@ public class FileFunction implements SkyFunction {
         }
       } else {
         Pair<RootedPath, FileStateValue> resolvedState = getSymlinkTargetRootedPath(realRootedPath,
-            realFileStateValue.getSymlinkTarget(), env);
+            realFileStateValue.getSymlinkTarget(), orderedSeenPaths, symlinkChain, env);
         if (resolvedState == null) {
           return null;
         }
@@ -171,48 +164,94 @@ public class FileFunction implements SkyFunction {
    */
   @Nullable
   private Pair<RootedPath, FileStateValue> getSymlinkTargetRootedPath(RootedPath rootedPath,
-      PathFragment symlinkTarget, Environment env) throws FileFunctionException {
+      PathFragment symlinkTarget, TreeSet<Path> orderedSeenPaths,
+      Iterable<RootedPath> symlinkChain, Environment env) throws FileFunctionException {
+    RootedPath symlinkTargetRootedPath;
     if (symlinkTarget.isAbsolute()) {
       Path path = rootedPath.asPath().getFileSystem().getRootDirectory().getRelative(
           symlinkTarget);
-      return resolveFromAncestors(
-          RootedPath.toRootedPathMaybeUnderRoot(path, pkgLocator.get().getPathEntries()), env);
+      symlinkTargetRootedPath =
+          RootedPath.toRootedPathMaybeUnderRoot(path, pkgLocator.get().getPathEntries());
+    } else {
+      Path path = rootedPath.asPath();
+      Path symlinkTargetPath;
+      if (path.getParentDirectory() != null) {
+        RootedPath parentRootedPath = RootedPath.toRootedPathMaybeUnderRoot(
+            path.getParentDirectory(), pkgLocator.get().getPathEntries());
+        FileValue parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
+        if (parentFileValue == null) {
+          return null;
+        }
+        symlinkTargetPath = parentFileValue.realRootedPath().asPath().getRelative(symlinkTarget);
+      } else {
+        // This means '/' is a symlink to 'symlinkTarget'.
+        symlinkTargetPath = path.getRelative(symlinkTarget);
+      }
+      symlinkTargetRootedPath = RootedPath.toRootedPathMaybeUnderRoot(symlinkTargetPath,
+          pkgLocator.get().getPathEntries());
     }
-    Path path = rootedPath.asPath();
-    Path symlinkTargetPath;
-    if (path.getParentDirectory() != null) {
-      RootedPath parentRootedPath = RootedPath.toRootedPathMaybeUnderRoot(
-          path.getParentDirectory(), pkgLocator.get().getPathEntries());
-      FileValue parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
-      if (parentFileValue == null) {
+    Path symlinkTargetPath = symlinkTargetRootedPath.asPath();
+    Path existingFloorPath = orderedSeenPaths.floor(symlinkTargetPath);
+    // Here is a brief argument that the following logic is correct.
+    //
+    // Any path 'p' in the symlink chain that is no larger than 'symlinkTargetPath' is one of:
+    //   (i)   'symlinkTargetPath'
+    //   (ii)   a smaller sibling 's' of 'symlinkTargetPath' or a sibling of an ancestor of
+    //         'symlinkTargetPath'
+    //   (iii)  an ancestor 'a' of 'symlinkTargetPath'
+    //   (iv) something else (e.g. a smaller sibling of an ancestor of 'symlinkTargetPath')
+    // If the largest 'p' is 'symlinkTarget' itself then 'existingFloorPath' will be that and we
+    // have found cycle. Otherwise, if there is such a 's' then 'existingFloorPath' will be the
+    // largest one. But the presence of any such 's' in the symlink chain implies an infinite
+    // expansion, which we would have already noticed. On the other hand, if there is such an 'a'
+    // then 'existingFloorPath' will be the largest one that and we definitely have found an
+    // infinite symlink expansion. Otherwise, if there is no such 'a', then the presence of
+    // 'symlinkTargetPath' doesn't create an infinite symlink expansion.
+    if (existingFloorPath != null && symlinkTargetPath.startsWith(existingFloorPath)) {
+      SkyKey uniquenessKey;
+      FileSymlinkException fse;
+      if (symlinkTargetPath.equals(existingFloorPath)) {
+        Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
+            splitIntoPathAndChain(symlinkTargetRootedPath.asPath(), symlinkChain);
+        FileSymlinkCycleException fsce =
+            new FileSymlinkCycleException(pathAndChain.getFirst(), pathAndChain.getSecond());
+        uniquenessKey = FileSymlinkCycleUniquenessValue.key(fsce.getCycle());
+        fse = fsce;
+      } else {
+        Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
+            splitIntoPathAndChain(existingFloorPath,
+                ImmutableList.copyOf(Iterables.concat(symlinkChain,
+                    ImmutableList.of(symlinkTargetRootedPath))));
+        uniquenessKey = FileSymlinkInfiniteExpansionUniquenessValue.key(pathAndChain.getSecond());
+        fse = new FileSymlinkInfiniteExpansionException(
+            pathAndChain.getFirst(), pathAndChain.getSecond());
+      }
+      if (env.getValue(uniquenessKey) == null) {
+        // Note that this dependency is merely to ensure that each unique symlink error gets
+        // reported exactly once.
         return null;
       }
-      symlinkTargetPath = parentFileValue.realRootedPath().asPath().getRelative(symlinkTarget);
-    } else {
-      // This means '/' is a symlink to 'symlinkTarget'.
-      symlinkTargetPath = path.getRelative(symlinkTarget);
+      throw new FileFunctionException(fse);
     }
-    RootedPath symlinkTargetRootedPath = RootedPath.toRootedPathMaybeUnderRoot(symlinkTargetPath,
-        pkgLocator.get().getPathEntries());
     return resolveFromAncestors(symlinkTargetRootedPath, env);
   }
 
-  private FileSymlinkCycleException makeFileSymlinkCycleException(RootedPath startOfCycle,
-      Iterable<RootedPath> symlinkPaths) {
+  private Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> splitIntoPathAndChain(
+      Path startOfCycle, Iterable<RootedPath> symlinkRootedPaths) {
     boolean inPathToCycle = true;
     ImmutableList.Builder<RootedPath> pathToCycleBuilder = ImmutableList.builder();
     ImmutableList.Builder<RootedPath> cycleBuilder = ImmutableList.builder();
-    for (RootedPath path : symlinkPaths) {
-      if (path.equals(startOfCycle)) {
+    for (RootedPath rootedPath : symlinkRootedPaths) {
+      if (rootedPath.asPath().equals(startOfCycle)) {
         inPathToCycle = false;
       }
       if (inPathToCycle) {
-        pathToCycleBuilder.add(path);
+        pathToCycleBuilder.add(rootedPath);
       } else {
-        cycleBuilder.add(path);
+        cycleBuilder.add(rootedPath);
       }
     }
-    return new FileSymlinkCycleException(pathToCycleBuilder.build(), cycleBuilder.build());
+    return Pair.of(pathToCycleBuilder.build(), cycleBuilder.build());
   }
 
   @Nullable
@@ -231,7 +270,7 @@ public class FileFunction implements SkyFunction {
       super(e, transience);
     }
 
-    public FileFunctionException(FileSymlinkCycleException e) {
+    public FileFunctionException(FileSymlinkException e) {
       super(e, Transience.PERSISTENT);
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleException.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleException.java
index d57fc42cfc..f5592988fe 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleException.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleException.java
@@ -17,8 +17,7 @@ import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.vfs.RootedPath;
 
 /** Exception indicating that a cycle was found in the filesystem. */
-public class FileSymlinkCycleException extends Exception {
-
+class FileSymlinkCycleException extends FileSymlinkException {
   private final ImmutableList<RootedPath> pathToCycle;
   private final ImmutableList<RootedPath> cycle;
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
index a0604b5b42..3ce5532b17 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessFunction.java
@@ -13,33 +13,29 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.events.Event;
-import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyFunction;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
-/** A value builder that has the side effect of reporting a file symlink cycle. */
-public class FileSymlinkCycleUniquenessFunction implements SkyFunction {
-
-  @SuppressWarnings("unchecked")  // Cast from Object to ImmutableList<RootedPath>.
+/** A {@link SkyFunction} that has the side effect of reporting a file symlink cycle. */
+public class FileSymlinkCycleUniquenessFunction
+    extends AbstractFileSymlinkExceptionUniquenessFunction {
   @Override
-  public SkyValue compute(SkyKey skyKey, Environment env) {
-    StringBuilder cycleMessage = new StringBuilder("circular symlinks detected\n");
-    cycleMessage.append("[start of symlink cycle]\n");
-    for (RootedPath rootedPath : (ImmutableList<RootedPath>) skyKey.argument()) {
-      cycleMessage.append(rootedPath.asPath() + "\n");
-    }
-    cycleMessage.append("[end of symlink cycle]");
-    // The purpose of this value builder is the side effect of emitting an error message exactly
-    // once per build per unique cycle.
-    env.getListener().handle(Event.error(cycleMessage.toString()));
+  protected SkyValue getDummyValue() {
     return FileSymlinkCycleUniquenessValue.INSTANCE;
   }
 
   @Override
-  public String extractTag(SkyKey skyKey) {
-    return null;
+  protected String getConciseDescription() {
+    return "circular symlinks";
+  }
+
+  @Override
+  protected String getHeaderMessage() {
+    return "[start of symlink cycle]";
+  }
+
+  @Override
+  protected String getFooterMessage() {
+    return "[end of symlink cycle]";
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessValue.java
index 627276d357..e8e9f28352 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkCycleUniquenessValue.java
@@ -13,45 +13,23 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
-import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.vfs.RootedPath;
 import com.google.devtools.build.skyframe.SkyKey;
-import com.google.devtools.build.skyframe.SkyValue;
 
 /**
  * A value for ensuring that a file symlink cycle is reported exactly once. This is achieved by
  * forcing the same value key for two logically equivalent cycles (e.g. ['a' -> 'b' -> 'c' -> 'a']
- * and ['b' -> 'c' -> 'a' -> 'b'], and letting Skyframe do its magic. 
+ * and ['b' -> 'c' -> 'a' -> 'b']), and letting Skyframe do its magic. 
  */
-class FileSymlinkCycleUniquenessValue implements SkyValue {
-
-  public static final FileSymlinkCycleUniquenessValue INSTANCE =
-      new FileSymlinkCycleUniquenessValue();
+class FileSymlinkCycleUniquenessValue extends AbstractFileSymlinkExceptionUniquenessValue {
+  static final FileSymlinkCycleUniquenessValue INSTANCE = new FileSymlinkCycleUniquenessValue();
 
   private FileSymlinkCycleUniquenessValue() {
   }
 
   static SkyKey key(ImmutableList<RootedPath> cycle) {
-    Preconditions.checkState(!cycle.isEmpty()); 
-    return new SkyKey(SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, canonicalize(cycle));
-  }
-
-  private static ImmutableList<RootedPath> canonicalize(ImmutableList<RootedPath> cycle) {
-    int minPos = 0;
-    String minString = cycle.get(0).toString();
-    for (int i = 1; i < cycle.size(); i++) {
-      String candidateString = cycle.get(i).toString();
-      if (candidateString.compareTo(minString) < 0) {
-        minPos = i;
-        minString = candidateString;
-      }
-    }
-    ImmutableList.Builder<RootedPath> builder = ImmutableList.builder();
-    for (int i = 0; i < cycle.size(); i++) {
-      int pos = (minPos + i) % cycle.size();
-      builder.add(cycle.get(pos));
-    }
-    return builder.build();
+    return AbstractFileSymlinkExceptionUniquenessValue.key(
+        SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS, cycle);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkException.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkException.java
new file mode 100644
index 0000000000..5da3083275
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkException.java
@@ -0,0 +1,21 @@
+// Copyright 2015 Google Inc. 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.skyframe;
+
+/** Exception indicating a problem with symlinks. */
+public abstract class FileSymlinkException extends Exception {
+  protected FileSymlinkException(String message) {
+    super(message);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionException.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionException.java
new file mode 100644
index 0000000000..a223c8bf7f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionException.java
@@ -0,0 +1,50 @@
+// Copyright 2015 Google Inc. 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.skyframe;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.vfs.RootedPath;
+
+/** Exception indicating that a symlink has an unbounded expansion on resolution. */
+public class FileSymlinkInfiniteExpansionException extends FileSymlinkException {
+  private final ImmutableList<RootedPath> pathToChain;
+  private final ImmutableList<RootedPath> chain;
+
+  FileSymlinkInfiniteExpansionException(ImmutableList<RootedPath> pathToChain,
+      ImmutableList<RootedPath> chain) {
+    // The infinite expansion has already been reported by
+    // FileSymlinkInfiniteExpansionUniquenessValue, but we still want to have a readable
+    // #getMessage.
+    super("Infinite symlink expansion");
+    this.pathToChain = pathToChain;
+    this.chain = chain;
+  }
+
+  /**
+   * The symlink path to the symlink that is the root cause of the infinite expansion. For example,
+   * suppose 'a' -> 'b' -> 'c' -> 'd' -> 'c/nope'. The path to the chain is 'a', 'b'.
+   */
+  ImmutableList<RootedPath> getPathToChain() {
+    return pathToChain;
+  }
+
+  /**
+   * The symlink chain that is the root cause of the infinite expansion. For example, suppose
+   * 'a' -> 'b' -> 'c' -> 'd' -> 'c/nope'. The chain is 'c', 'd', 'c/nope'.
+   */
+  ImmutableList<RootedPath> getChain() {
+    return chain;
+  }
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java
new file mode 100644
index 0000000000..06a94619a0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessFunction.java
@@ -0,0 +1,42 @@
+// Copyright 2015 Google Inc. 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.skyframe;
+
+import com.google.devtools.build.skyframe.SkyFunction;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/** A {@link SkyFunction} that has the side effect of reporting a file symlink expansion error. */
+public class FileSymlinkInfiniteExpansionUniquenessFunction
+    extends AbstractFileSymlinkExceptionUniquenessFunction {
+  @Override
+  protected SkyValue getDummyValue() {
+    return FileSymlinkInfiniteExpansionUniquenessValue.INSTANCE;
+  }
+
+  @Override
+  protected String getConciseDescription() {
+    return "infinite symlink expansion";
+  }
+
+  @Override
+  protected String getHeaderMessage() {
+    return "[start of symlink chain]";
+  }
+
+  @Override
+  protected String getFooterMessage() {
+    return "[end of symlink chain]";
+  }
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessValue.java
new file mode 100644
index 0000000000..e866b51572
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileSymlinkInfiniteExpansionUniquenessValue.java
@@ -0,0 +1,39 @@
+// Copyright 2015 Google Inc. 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.skyframe;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.vfs.RootedPath;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.SkyValue;
+
+/**
+ * A value for ensuring that a file symlink expansion error is reported exactly once. This is
+ * achieved by forcing the same value key for two logically equivalent expansion errors (e.g.
+ * ['a' -> 'b' -> 'c' -> 'a/nope'] and ['b' -> 'c' -> 'a' -> 'a/nope']), and letting Skyframe do
+ * its magic.
+ */
+class FileSymlinkInfiniteExpansionUniquenessValue implements SkyValue {
+  static final FileSymlinkInfiniteExpansionUniquenessValue INSTANCE =
+      new FileSymlinkInfiniteExpansionUniquenessValue();
+
+  private FileSymlinkInfiniteExpansionUniquenessValue() {
+  }
+
+  static SkyKey key(ImmutableList<RootedPath> cycle) {
+    return AbstractFileSymlinkExceptionUniquenessValue.key(
+        SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS, cycle);
+  }
+}
+
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 56fa8df043..6514ff73db 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -139,10 +139,10 @@ public class PackageFunction implements SkyFunction {
     boolean packageShouldBeInError = packageWasInError;
     ImmutableMap.Builder<PathFragment, PackageLookupValue> builder = ImmutableMap.builder();
     for (Map.Entry<SkyKey, ValueOrException3<BuildFileNotFoundException,
-        InconsistentFilesystemException, FileSymlinkCycleException>> entry :
+        InconsistentFilesystemException, FileSymlinkException>> entry :
             env.getValuesOrThrow(depKeys, BuildFileNotFoundException.class,
                 InconsistentFilesystemException.class,
-                FileSymlinkCycleException.class).entrySet()) {
+                FileSymlinkException.class).entrySet()) {
       PathFragment pkgName = ((PackageIdentifier) entry.getKey().argument()).getPackageFragment();
       try {
         PackageLookupValue value = (PackageLookupValue) entry.getValue().get();
@@ -153,7 +153,7 @@ public class PackageFunction implements SkyFunction {
         maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
       } catch (InconsistentFilesystemException e) {
         throw new InternalInconsistentFilesystemException(packageIdentifier, e);
-      } catch (FileSymlinkCycleException e) {
+      } catch (FileSymlinkException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
       }
@@ -167,14 +167,14 @@ public class PackageFunction implements SkyFunction {
     Preconditions.checkState(
         Iterables.all(depKeys, SkyFunctions.isSkyFunction(SkyFunctions.FILE)), depKeys);
     boolean packageShouldBeInError = packageWasInError;
-    for (Map.Entry<SkyKey, ValueOrException3<IOException, FileSymlinkCycleException,
+    for (Map.Entry<SkyKey, ValueOrException3<IOException, FileSymlinkException,
         InconsistentFilesystemException>> entry : env.getValuesOrThrow(depKeys, IOException.class,
-            FileSymlinkCycleException.class, InconsistentFilesystemException.class).entrySet()) {
+            FileSymlinkException.class, InconsistentFilesystemException.class).entrySet()) {
       try {
         entry.getValue().get();
       } catch (IOException e) {
         maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
-      } catch (FileSymlinkCycleException e) {
+      } catch (FileSymlinkException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
       } catch (InconsistentFilesystemException e) {
@@ -191,14 +191,14 @@ public class PackageFunction implements SkyFunction {
         Iterables.all(depKeys, SkyFunctions.isSkyFunction(SkyFunctions.GLOB)), depKeys);
     boolean packageShouldBeInError = packageWasInError;
     for (Map.Entry<SkyKey, ValueOrException4<IOException, BuildFileNotFoundException,
-        FileSymlinkCycleException, InconsistentFilesystemException>> entry :
+        FileSymlinkException, InconsistentFilesystemException>> entry :
         env.getValuesOrThrow(depKeys, IOException.class, BuildFileNotFoundException.class,
-            FileSymlinkCycleException.class, InconsistentFilesystemException.class).entrySet()) {
+            FileSymlinkException.class, InconsistentFilesystemException.class).entrySet()) {
       try {
         entry.getValue().get();
       } catch (IOException | BuildFileNotFoundException e) {
         maybeThrowFilesystemInconsistency(packageIdentifier, e, packageWasInError);
-      } catch (FileSymlinkCycleException e) {
+      } catch (FileSymlinkException e) {
         // Legacy doesn't detect symlink cycles.
         packageShouldBeInError = true;
       } catch (InconsistentFilesystemException e) {
@@ -315,9 +315,9 @@ public class PackageFunction implements SkyFunction {
     PackageValue workspace = null;
     try {
       workspace = (PackageValue) env.getValueOrThrow(workspaceKey, IOException.class,
-          FileSymlinkCycleException.class, InconsistentFilesystemException.class,
+          FileSymlinkException.class, InconsistentFilesystemException.class,
           EvalException.class);
-    } catch (IOException | FileSymlinkCycleException | InconsistentFilesystemException
+    } catch (IOException | FileSymlinkException | InconsistentFilesystemException
         | EvalException e) {
       throw new PackageFunctionException(new BadWorkspaceFileException(e.getMessage()),
           Transience.PERSISTENT);
@@ -393,9 +393,9 @@ public class PackageFunction implements SkyFunction {
     FileValue buildFileValue;
     try {
       buildFileValue = (FileValue) env.getValueOrThrow(FileValue.key(buildFileRootedPath),
-          IOException.class, FileSymlinkCycleException.class,
+          IOException.class, FileSymlinkException.class,
           InconsistentFilesystemException.class);
-    } catch (IOException | FileSymlinkCycleException | InconsistentFilesystemException e) {
+    } catch (IOException | FileSymlinkException | InconsistentFilesystemException e) {
       throw new IllegalStateException("Package lookup succeeded but encountered error when "
           + "getting FileValue for BUILD file directly.", e);
     }
@@ -633,9 +633,9 @@ public class PackageFunction implements SkyFunction {
       containingPkgLookupKeys.add(ContainingPackageLookupValue.key(dirId));
     }
     Map<SkyKey, ValueOrException3<BuildFileNotFoundException, InconsistentFilesystemException,
-        FileSymlinkCycleException>> containingPkgLookupValues = env.getValuesOrThrow(
+        FileSymlinkException>> containingPkgLookupValues = env.getValuesOrThrow(
             containingPkgLookupKeys, BuildFileNotFoundException.class,
-            InconsistentFilesystemException.class, FileSymlinkCycleException.class);
+            InconsistentFilesystemException.class, FileSymlinkException.class);
     if (env.valuesMissing()) {
       return;
     }
@@ -673,11 +673,11 @@ public class PackageFunction implements SkyFunction {
   getContainingPkgLookupValueAndPropagateInconsistentFilesystemExceptions(
       PackageIdentifier packageIdentifier,
       ValueOrException3<BuildFileNotFoundException, InconsistentFilesystemException,
-      FileSymlinkCycleException> containingPkgLookupValueOrException, Environment env)
+      FileSymlinkException> containingPkgLookupValueOrException, Environment env)
           throws InternalInconsistentFilesystemException {
     try {
       return (ContainingPackageLookupValue) containingPkgLookupValueOrException.get();
-    } catch (BuildFileNotFoundException | FileSymlinkCycleException e) {
+    } catch (BuildFileNotFoundException | FileSymlinkException e) {
       env.getListener().handle(Event.error(null, e.getMessage()));
       return null;
     } catch (InconsistentFilesystemException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
index 40bbdb6c7d..5657bccb68 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
@@ -96,7 +96,7 @@ public class PackageLookupFunction implements SkyFunction {
     FileValue fileValue = null;
     try {
       fileValue = (FileValue) env.getValueOrThrow(fileSkyKey, IOException.class,
-          FileSymlinkCycleException.class, InconsistentFilesystemException.class);
+          FileSymlinkException.class, InconsistentFilesystemException.class);
     } catch (IOException e) {
       // TODO(bazel-team): throw an IOException here and let PackageFunction wrap that into a
       // BuildFileNotFoundException.
@@ -104,7 +104,7 @@ public class PackageLookupFunction implements SkyFunction {
           "IO errors while looking for " + basename + " file reading "
               + buildFileRootedPath.asPath() + ": " + e.getMessage(), e),
           Transience.PERSISTENT);
-    } catch (FileSymlinkCycleException e) {
+    } catch (FileSymlinkException e) {
       throw new PackageLookupFunctionException(new BuildFileNotFoundException(packageIdentifier,
           "Symlink cycle detected while trying to find " + basename + " file "
               + buildFileRootedPath.asPath()),
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
index edb14c61d8..63d56c547a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursiveDirectoryTraversalFunction.java
@@ -116,8 +116,8 @@ abstract class RecursiveDirectoryTraversalFunction
     FileValue fileValue;
     try {
       fileValue = (FileValue) env.getValueOrThrow(fileKey, InconsistentFilesystemException.class,
-          FileSymlinkCycleException.class, IOException.class);
-    } catch (InconsistentFilesystemException | FileSymlinkCycleException | IOException e) {
+          FileSymlinkException.class, IOException.class);
+    } catch (InconsistentFilesystemException | FileSymlinkException | IOException e) {
       return reportErrorAndReturn("Failed to get information about path", e, rootRelativePath,
           env.getListener());
     }
@@ -196,11 +196,11 @@ abstract class RecursiveDirectoryTraversalFunction
     try {
       dirValue = (DirectoryListingValue) env.getValueOrThrow(DirectoryListingValue.key(rootedPath),
           InconsistentFilesystemException.class, IOException.class,
-          FileSymlinkCycleException.class);
+          FileSymlinkException.class);
     } catch (InconsistentFilesystemException | IOException e) {
       return reportErrorAndReturn("Failed to list directory contents", e, rootRelativePath,
           env.getListener());
-    } catch (FileSymlinkCycleException e) {
+    } catch (FileSymlinkException e) {
       // DirectoryListingFunction only throws FileSymlinkCycleException when FileFunction throws it,
       // but FileFunction was evaluated for rootedPath above, and didn't throw there. It shouldn't
       // be able to avoid throwing there but throw here.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
index b6944c5140..f8d8febf55 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyFunctions.java
@@ -26,7 +26,9 @@ public final class SkyFunctions {
   public static final SkyFunctionName DIRECTORY_LISTING_STATE =
       SkyFunctionName.create("DIRECTORY_LISTING_STATE");
   public static final SkyFunctionName FILE_SYMLINK_CYCLE_UNIQUENESS =
-      SkyFunctionName.create("FILE_SYMLINK_CYCLE_UNIQUENESS_NODE");
+      SkyFunctionName.create("FILE_SYMLINK_CYCLE_UNIQUENESS");
+  public static final SkyFunctionName FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS =
+      SkyFunctionName.create("FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS");
   public static final SkyFunctionName FILE = SkyFunctionName.create("FILE");
   public static final SkyFunctionName DIRECTORY_LISTING =
       SkyFunctionName.create("DIRECTORY_LISTING");
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 45a3849496..a06a9dacde 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -295,6 +295,8 @@ public abstract class SkyframeExecutor implements WalkableGraphFactory {
         new DirectoryListingStateFunction(externalFilesHelper));
     map.put(SkyFunctions.FILE_SYMLINK_CYCLE_UNIQUENESS,
         new FileSymlinkCycleUniquenessFunction());
+    map.put(SkyFunctions.FILE_SYMLINK_INFINITE_EXPANSION_UNIQUENESS,
+        new FileSymlinkInfiniteExpansionUniquenessFunction());
     map.put(SkyFunctions.FILE, new FileFunction(pkgLocator, tsgm, externalFilesHelper));
     map.put(SkyFunctions.DIRECTORY_LISTING, new DirectoryListingFunction());
     map.put(SkyFunctions.PACKAGE_LOOKUP, new PackageLookupFunction(deletedPackages));