Automated [] rollback of [] + merge with []

*** Reason for rollback ***

Original CL uncovered a depot issue which was fixed in []. I verified it was the only such issue (see []).

*** Original change description ***

Rollback of commit f87a414a6bf50613a2c419e53a96f76154f44ae3.

*** Reason for rollback ***

Rolling back until [] is submitted and we have verified that there are no other breakages

*** Original change description ***

Handle the case of infinite symlink expansion where a path in a symlink chain is a symlink to an ancestor of a path in the chain.

--
MOS_MIGRATED_REVID=105251788

1 files changed, 56 insertions, 38 deletions

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 8a7c84d5e6..0e8f46a67b 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
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
@@ -208,50 +209,67 @@ public class FileFunction implements SkyFunction {
       symlinkTargetRootedPath = RootedPath.toRootedPathMaybeUnderRoot(symlinkTargetPath,
           pkgLocator.get().getPathEntries());
     }
-    Path symlinkTargetPath = symlinkTargetRootedPath.asPath();
-    Path existingFloorPath = orderedSeenPaths.floor(symlinkTargetPath);
-    // Here is a brief argument that the following logic is correct.
+    // Suppose we have a symlink chain p -> p1 -> p2 -> ... pK. We want to determine the fully
+    // resolved path, if any, of p. This entails following the chain and noticing if there's a
+    // symlink issue. There three sorts of issues:
+    // (i) Symlink cycle:
+    //   p -> p1 -> p2 -> p1
+    // (ii) Unbounded expansion caused by a symlink to a descendant of a member of the chain:
+    //   p -> a/b -> c/d -> a/b/e
+    // (iii) Unbounded expansion caused by a symlink to an ancestor of a member of the chain:
+    //   p -> a/b -> c/d -> a
     //
-    // 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 =
-            CycleUtils.splitIntoPathAndChain(
-                isPathPredicate(symlinkTargetRootedPath.asPath()), symlinkChain);
-        FileSymlinkCycleException fsce =
-            new FileSymlinkCycleException(pathAndChain.getFirst(), pathAndChain.getSecond());
-        uniquenessKey = FileSymlinkCycleUniquenessFunction.key(fsce.getCycle());
-        fse = fsce;
-      } else {
-        Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
-            CycleUtils.splitIntoPathAndChain(
-                isPathPredicate(existingFloorPath),
-                ImmutableList.copyOf(
-                    Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
-        uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
-        fse = new FileSymlinkInfiniteExpansionException(
-            pathAndChain.getFirst(), pathAndChain.getSecond());
-      }
+    // We can detect all three of these symlink issues by following the chain and deciding if each
+    // new element is problematic. Here is our incremental algorithm:
+    //
+    // Suppose we encounter the symlink target p and we have already encountered all the paths in P:
+    //   If p is in P then we have a found a cycle (i).
+    //   If p is a descendant of any path p' in P then we have unbounded expansion (ii).
+    //   If p is an ancestor of any path p' in P then we have unbounded expansion (iii).
+    // We can check for these cases efficiently (read: sublinear time) by finding the extremal
+    // candidate p' for (ii) and (iii).
+    Path symlinkTargetPath = symlinkTargetRootedPath.asPath();
+    SkyKey uniquenessKey = null;
+    FileSymlinkException fse = null;
+    Path seenFloorPath = orderedSeenPaths.floor(symlinkTargetPath);
+    Path seenCeilingPath = orderedSeenPaths.ceiling(symlinkTargetPath);
+    if (orderedSeenPaths.contains(symlinkTargetPath)) {
+      // 'rootedPath' is a symlink to a previous element in the symlink chain (i).
+      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
+          CycleUtils.splitIntoPathAndChain(
+              isPathPredicate(symlinkTargetRootedPath.asPath()), symlinkChain);
+      FileSymlinkCycleException fsce =
+          new FileSymlinkCycleException(pathAndChain.getFirst(), pathAndChain.getSecond());
+      uniquenessKey = FileSymlinkCycleUniquenessFunction.key(fsce.getCycle());
+      fse = fsce;
+    } else if (seenFloorPath != null && symlinkTargetPath.startsWith(seenFloorPath)) {
+      // 'rootedPath' is a symlink to a descendant of a previous element in the symlink chain (ii).
+      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
+          CycleUtils.splitIntoPathAndChain(
+              isPathPredicate(seenFloorPath),
+              ImmutableList.copyOf(
+                  Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
+      uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
+      fse = new FileSymlinkInfiniteExpansionException(
+          pathAndChain.getFirst(), pathAndChain.getSecond());
+    } else if (seenCeilingPath != null && seenCeilingPath.startsWith(symlinkTargetPath)) {
+      // 'rootedPath' is a symlink to an ancestor of a previous element in the symlink chain (iii).
+      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
+          CycleUtils.splitIntoPathAndChain(
+              isPathPredicate(seenCeilingPath),
+              ImmutableList.copyOf(
+                  Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
+      uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
+      fse = new FileSymlinkInfiniteExpansionException(
+          pathAndChain.getFirst(), pathAndChain.getSecond());
+    }
+    if (uniquenessKey != null) {
       if (env.getValue(uniquenessKey) == null) {
         // Note that this dependency is merely to ensure that each unique symlink error gets
         // reported exactly once.
         return null;
       }
-      throw new FileFunctionException(fse);
+      throw new FileFunctionException(Preconditions.checkNotNull(fse, rootedPath));
     }
     return resolveFromAncestors(symlinkTargetRootedPath, env);
   }