Speed up fingerprint and hashcode computation by:

1. Add a fingerprint of the FilesetTraversalParams rather than the transitive closure of its attributes, while adding the FilesetTraversalParams to a Fingerprint.
2. Memoize the above fingerprint computations as well as hashCode computations for FilesetTraversalparams.

Use AutoValue's @Memoize as well as equals and hashcode to simplify the code.

RELNOTES: None
PiperOrigin-RevId: 171191126

2 files changed, 122 insertions, 238 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
index 23ddd3f0f5..3a9e211860 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParams.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.actions;
 
+import com.google.auto.value.AutoValue;
+import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.base.Optional;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.Label;
@@ -32,7 +34,7 @@ import java.util.Set;
 public interface FilesetTraversalParams {
 
   /** Desired behavior if the traversal hits a directory with a BUILD file, i.e. a subpackage. */
-  public enum PackageBoundaryMode {
+  enum PackageBoundaryMode {
     /** The traversal should recurse into the directory, optionally reporting a warning. */
     CROSS,
 
@@ -55,7 +57,7 @@ public interface FilesetTraversalParams {
   }
 
   /**
-   * Abstraction of the root directory of a {@link DirectTraversal}.
+   * The root directory of a {@link DirectTraversal}.
    *
    * <ul>
    * <li>The root of package traversals is the package directory, i.e. the parent of the BUILD file.
@@ -65,14 +67,15 @@ public interface FilesetTraversalParams {
    *
    * <p>For the meaning of "recursive" and "file" traversals see {@link DirectTraversal}.
    */
-  interface DirectTraversalRoot {
+  @AutoValue
+  abstract class DirectTraversalRoot {
 
     /**
      * Returns the root part of the full path.
      *
      * <p>This is typically the workspace root or some output tree's root (e.g. genfiles, binfiles).
      */
-    Path getRootPart();
+    public abstract Path getRootPart();
 
     /**
      * Returns the {@link #getRootPart() root}-relative part of the path.
@@ -80,14 +83,30 @@ public interface FilesetTraversalParams {
      * <p>This is typically the source directory under the workspace or the output file under an
      * output directory.
      */
-    PathFragment getRelativePart();
+    public abstract PathFragment getRelativePart();
 
     /** Returns a {@link RootedPath} composed of the root and relative parts. */
-    RootedPath asRootedPath();
+    public RootedPath asRootedPath() {
+      return RootedPath.toRootedPath(getRootPart(), getRelativePart());
+    }
+
+    @Memoized
+    @Override
+    public abstract int hashCode();
+
+    static DirectTraversalRoot forPackage(Artifact buildFile) {
+      return new AutoValue_FilesetTraversalParams_DirectTraversalRoot(
+          buildFile.getRoot().getPath(), buildFile.getRootRelativePath().getParentDirectory());
+    }
+
+    static DirectTraversalRoot forFileOrDirectory(Artifact fileOrDirectory) {
+      return new AutoValue_FilesetTraversalParams_DirectTraversalRoot(
+          fileOrDirectory.getRoot().getPath(), fileOrDirectory.getRootRelativePath());
+    }
   }
 
   /**
-   * Describes a request for a direct filesystem traversal.
+   * A request for a direct filesystem traversal.
    *
    * <p>"Direct" means this corresponds to an actual filesystem traversal as opposed to traversing
    * another Fileset rule, which is called a "nested" traversal.
@@ -103,10 +122,11 @@ public interface FilesetTraversalParams {
    *
    * <p>See {@link DirectTraversal#getRoot()} for more details.
    */
-  interface DirectTraversal {
+  @AutoValue
+  abstract class DirectTraversal {
 
     /** Returns the root of the traversal; see {@link DirectTraversalRoot}. */
-    DirectTraversalRoot getRoot();
+    public abstract DirectTraversalRoot getRoot();
 
     /**
      * Returns true if this traversal refers to a whole package.
@@ -116,7 +136,7 @@ public interface FilesetTraversalParams {
      * <p>Package traversals are always recursive (see {@link #isRecursive()}) and are never
      * generated (see {@link #isGenerated()}).
      */
-    boolean isPackage();
+    public abstract boolean isPackage();
 
     /**
      * Returns true if this is a "recursive traversal", i.e. created from FilesetEntry.srcdir.
@@ -142,16 +162,48 @@ public interface FilesetTraversalParams {
      * expanded just like normal directories, subsequent directory symlinks under them are *not*
      * expanded though; they are not expanded at all in "file traversals").
      */
-    boolean isRecursive();
+    public abstract boolean isRecursive();
 
     /** Returns true if the root points to a generated file, symlink or directory. */
-    boolean isGenerated();
+    public abstract boolean isGenerated();
 
     /** Returns true if input symlinks should be dereferenced; false if copied. */
-    boolean isFollowingSymlinks();
+    public abstract boolean isFollowingSymlinks();
 
     /** Returns the desired behavior when the traversal hits a subpackage. */
-    PackageBoundaryMode getPackageBoundaryMode();
+    public abstract PackageBoundaryMode getPackageBoundaryMode();
+
+    @Memoized
+    @Override
+    public abstract int hashCode();
+
+    @Memoized
+    byte[] getFingerprint() {
+      Fingerprint fp = new Fingerprint();
+      fp.addPath(getRoot().asRootedPath().asPath());
+      fp.addBoolean(isPackage());
+      fp.addBoolean(isFollowingSymlinks());
+      fp.addBoolean(isRecursive());
+      fp.addBoolean(isGenerated());
+      getPackageBoundaryMode().fingerprint(fp);
+      return fp.digestAndReset();
+    }
+
+    static DirectTraversal getDirectTraversal(
+        DirectTraversalRoot root,
+        boolean isPackage,
+        boolean followSymlinks,
+        PackageBoundaryMode pkgBoundaryMode,
+        boolean isRecursive,
+        boolean isGenerated) {
+      return new AutoValue_FilesetTraversalParams_DirectTraversal(
+          root,
+          isPackage,
+          isRecursive,
+          isGenerated,
+          followSymlinks,
+          pkgBoundaryMode);
+    }
   }
 
   /** Label of the Fileset rule that owns this traversal. */
diff --git a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
index a894e0aa2a..5277badbce 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/FilesetTraversalParamsFactory.java
@@ -13,22 +13,20 @@
 // limitations under the License.
 package com.google.devtools.build.lib.actions;
 
+import com.google.auto.value.AutoValue;
+import com.google.auto.value.extension.memoized.Memoized;
 import com.google.common.base.Optional;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Ordering;
-import com.google.devtools.build.lib.actions.FilesetTraversalParams.DirectTraversal;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.DirectTraversalRoot;
 import com.google.devtools.build.lib.actions.FilesetTraversalParams.PackageBoundaryMode;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.FilesetEntry.SymlinkBehavior;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import com.google.devtools.build.lib.vfs.RootedPath;
-import java.util.Objects;
 import java.util.Set;
 import javax.annotation.Nullable;
 
@@ -55,8 +53,9 @@ public final class FilesetTraversalParamsFactory {
       Artifact buildFile, PathFragment destPath, @Nullable Set<String> excludes,
       SymlinkBehavior symlinkBehaviorMode, PackageBoundaryMode pkgBoundaryMode) {
     Preconditions.checkState(buildFile.isSourceArtifact(), "%s", buildFile);
-    return new DirectoryTraversalParams(ownerLabel, DirectTraversalRootImpl.forPackage(buildFile),
-        true, destPath, excludes, symlinkBehaviorMode, pkgBoundaryMode, true, false);
+    return DirectoryTraversalParams.getDirectoryTraversalParams(ownerLabel,
+        DirectTraversalRoot.forPackage(buildFile), true, destPath, excludes,
+        symlinkBehaviorMode, pkgBoundaryMode, true, false);
   }
 
   /**
@@ -78,8 +77,8 @@ public final class FilesetTraversalParamsFactory {
   public static FilesetTraversalParams recursiveTraversalOfDirectory(Label ownerLabel,
       Artifact directoryToTraverse, PathFragment destPath, @Nullable Set<String> excludes,
       SymlinkBehavior symlinkBehaviorMode, PackageBoundaryMode pkgBoundaryMode) {
-    return new DirectoryTraversalParams(ownerLabel,
-        DirectTraversalRootImpl.forFileOrDirectory(directoryToTraverse), false, destPath,
+    return DirectoryTraversalParams.getDirectoryTraversalParams(ownerLabel,
+        DirectTraversalRoot.forFileOrDirectory(directoryToTraverse), false, destPath,
         excludes, symlinkBehaviorMode, pkgBoundaryMode, true,
         !directoryToTraverse.isSourceArtifact());
   }
@@ -101,8 +100,8 @@ public final class FilesetTraversalParamsFactory {
   public static FilesetTraversalParams fileTraversal(Label ownerLabel, Artifact fileToTraverse,
       PathFragment destPath, SymlinkBehavior symlinkBehaviorMode,
       PackageBoundaryMode pkgBoundaryMode) {
-    return new DirectoryTraversalParams(ownerLabel,
-        DirectTraversalRootImpl.forFileOrDirectory(fileToTraverse), false, destPath, null,
+    return DirectoryTraversalParams.getDirectoryTraversalParams(ownerLabel,
+        DirectTraversalRoot.forFileOrDirectory(fileToTraverse), false, destPath, null,
         symlinkBehaviorMode, pkgBoundaryMode, false, !fileToTraverse.isSourceArtifact());
   }
 
@@ -132,133 +131,44 @@ public final class FilesetTraversalParamsFactory {
       return Iterables.getOnlyElement(nested);
     }
     // When srcdir is another Fileset, then files must be null so strip_prefix must also be null.
-    return new NestedTraversalParams(ownerLabel, nested, destDir, excludes);
+    return NestedTraversalParams.getNestedTraversal(ownerLabel, nested, destDir, excludes);
   }
 
-  private abstract static class ParamsCommon implements FilesetTraversalParams {
-    private final Label ownerLabelForErrorMessages;
-    private final PathFragment destDir;
-    private final ImmutableSet<String> excludes;
-
-    ParamsCommon(
-        Label ownerLabelForErrorMessages, PathFragment destDir, @Nullable Set<String> excludes) {
-      this.ownerLabelForErrorMessages = ownerLabelForErrorMessages;
-      this.destDir = destDir;
-      if (excludes == null) {
-        this.excludes = ImmutableSet.of();
-      } else {
-        // Order the set for the sake of deterministic fingerprinting.
-        this.excludes = ImmutableSet.copyOf(Ordering.natural().immutableSortedCopy(excludes));
-      }
-    }
-
-    @Override
-    public Label getOwnerLabelForErrorMessages() {
-      return ownerLabelForErrorMessages;
-    }
-
-    @Override
-    public Set<String> getExcludedFiles() {
-      return excludes;
-    }
-
-    @Override
-    public PathFragment getDestPath() {
-      return destDir;
-    }
-
-    protected final void commonFingerprint(Fingerprint fp) {
-      fp.addPath(destDir);
-      if (!excludes.isEmpty()) {
-        fp.addStrings(excludes);
-      }
-    }
-
-    @Override
-    public String toString() {
-      return super.toString()
-          + "["
-          + destDir
-          + ", "
-          + ownerLabelForErrorMessages
-          + ", "
-          + excludes
-          + "]";
-    }
-
-    protected boolean internalEquals(ParamsCommon that) {
-      return Objects.equals(this.ownerLabelForErrorMessages, that.ownerLabelForErrorMessages)
-          && Objects.equals(this.destDir, that.destDir)
-          && Objects.equals(this.excludes, that.excludes);
-    }
-
-    protected int internalHashCode() {
-      return Objects.hash(ownerLabelForErrorMessages, destDir, excludes);
-    }
+  private static Set<String> getOrderedExcludes(@Nullable Set<String> excludes) {
+    // Order the set for the sake of deterministic fingerprinting.
+    return excludes == null
+        ? ImmutableSet.of()
+        : ImmutableSet.copyOf(Ordering.natural().immutableSortedCopy(excludes));
   }
 
-  private static final class DirectTraversalImpl implements DirectTraversal {
-    private final DirectTraversalRoot root;
-    private final boolean isPackage;
-    private final boolean followSymlinks;
-    private final PackageBoundaryMode pkgBoundaryMode;
-    private final boolean isRecursive;
-    private final boolean isGenerated;
-
-    DirectTraversalImpl(DirectTraversalRoot root, boolean isPackage, boolean followSymlinks,
-        PackageBoundaryMode pkgBoundaryMode, boolean isRecursive, boolean isGenerated) {
-      this.root = root;
-      this.isPackage = isPackage;
-      this.followSymlinks = followSymlinks;
-      this.pkgBoundaryMode = pkgBoundaryMode;
-      this.isRecursive = isRecursive;
-      this.isGenerated = isGenerated;
-    }
-
-    @Override
-    public DirectTraversalRoot getRoot() {
-      return root;
-    }
-
-    @Override
-    public boolean isPackage() {
-      return isPackage;
-    }
-
+  @AutoValue
+  abstract static class DirectoryTraversalParams implements FilesetTraversalParams {
     @Override
-    public boolean isRecursive() {
-      return isRecursive;
+    public ImmutableList<FilesetTraversalParams> getNestedTraversal() {
+      return ImmutableList.of();
     }
 
+    @Memoized
     @Override
-    public boolean isGenerated() {
-      return isGenerated;
-    }
+    public abstract int hashCode();
 
-    @Override
-    public boolean isFollowingSymlinks() {
-      return followSymlinks;
+    @Memoized
+    byte[] getFingerprint() {
+      Fingerprint fp = new Fingerprint();
+      fp.addPath(getDestPath());
+      if (!getExcludedFiles().isEmpty()) {
+        fp.addStrings(getExcludedFiles());
+      }
+      fp.addBytes(getDirectTraversal().get().getFingerprint());
+      return fp.digestAndReset();
     }
 
     @Override
-    public PackageBoundaryMode getPackageBoundaryMode() {
-      return pkgBoundaryMode;
-    }
-
-    void fingerprint(Fingerprint fp) {
-      fp.addPath(root.asRootedPath().asPath());
-      fp.addBoolean(isPackage);
-      fp.addBoolean(followSymlinks);
-      fp.addBoolean(isRecursive);
-      fp.addBoolean(isGenerated);
-      pkgBoundaryMode.fingerprint(fp);
+    public void fingerprint(Fingerprint fp) {
+      fp.addBytes(getFingerprint());
     }
-  }
-
-  private static final class DirectoryTraversalParams extends ParamsCommon {
-    private final DirectTraversalImpl traversal;
 
-    DirectoryTraversalParams(Label ownerLabel,
+    static DirectoryTraversalParams getDirectoryTraversalParams(Label ownerLabel,
         DirectTraversalRoot root,
         boolean isPackage,
         PathFragment destPath,
@@ -267,126 +177,48 @@ public final class FilesetTraversalParamsFactory {
         PackageBoundaryMode pkgBoundaryMode,
         boolean isRecursive,
         boolean isGenerated) {
-      super(ownerLabel, destPath, excludes);
-      traversal = new DirectTraversalImpl(root, isPackage,
+      DirectTraversal traversal = DirectTraversal.getDirectTraversal(root, isPackage,
           symlinkBehaviorMode == SymlinkBehavior.DEREFERENCE, pkgBoundaryMode, isRecursive,
           isGenerated);
+      return new AutoValue_FilesetTraversalParamsFactory_DirectoryTraversalParams(
+          ownerLabel, destPath, getOrderedExcludes(excludes), Optional.of(traversal));
     }
+  }
 
+  @AutoValue
+  abstract static class NestedTraversalParams implements FilesetTraversalParams {
     @Override
     public Optional<DirectTraversal> getDirectTraversal() {
-      return Optional.<DirectTraversal>of(traversal);
-    }
-
-    @Override
-    public ImmutableList<FilesetTraversalParams> getNestedTraversal() {
-      return ImmutableList.of();
+      return Optional.absent();
     }
 
+    @Memoized
     @Override
-    public void fingerprint(Fingerprint fp) {
-      commonFingerprint(fp);
-      traversal.fingerprint(fp);
-    }
+    public abstract int hashCode();
 
-    @Override
-    public int hashCode() {
-      return 37 * super.internalHashCode() + Objects.hashCode(traversal);
+    @Memoized
+    protected byte[] getFingerprint() {
+      Fingerprint fp = new Fingerprint();
+      fp.addPath(getDestPath());
+      if (!getExcludedFiles().isEmpty()) {
+        fp.addStrings(getExcludedFiles());
+      }
+      getNestedTraversal().forEach(nestedTraversal -> nestedTraversal.fingerprint(fp));
+      return fp.digestAndReset();
     }
 
     @Override
-    public boolean equals(Object obj) {
-      if (this == obj) {
-        return true;
-      }
-      if (!(obj instanceof DirectoryTraversalParams)) {
-        return false;
-      }
-      DirectoryTraversalParams that = (DirectoryTraversalParams) obj;
-      return Objects.equals(this.traversal, that.traversal) && internalEquals(that);
+    public void fingerprint(Fingerprint fp) {
+      fp.addBytes(getFingerprint());
     }
-  }
-
-  private static final class NestedTraversalParams extends ParamsCommon {
-    private final ImmutableList<FilesetTraversalParams> nested;
 
-    NestedTraversalParams(
+    static NestedTraversalParams getNestedTraversal(
         Label ownerLabel,
         ImmutableList<FilesetTraversalParams> nested,
         PathFragment destDir,
         @Nullable Set<String> excludes) {
-      super(ownerLabel, destDir, excludes);
-      this.nested = nested;
-    }
-
-    @Override
-    public Optional<DirectTraversal> getDirectTraversal() {
-      return Optional.absent();
-    }
-
-    @Override
-    public ImmutableList<FilesetTraversalParams> getNestedTraversal() {
-      return nested;
-    }
-
-    @Override
-    public void fingerprint(Fingerprint fp) {
-      commonFingerprint(fp);
-      for (FilesetTraversalParams param : nested) {
-        param.fingerprint(fp);
-      }
-    }
-
-    @Override
-    public int hashCode() {
-      return 37 * super.internalHashCode() + Objects.hashCode(nested);
-    }
-
-    @Override
-    public boolean equals(Object obj) {
-      if (this == obj) {
-        return true;
-      }
-      if (!(obj instanceof NestedTraversalParams)) {
-        return false;
-      }
-      NestedTraversalParams that = (NestedTraversalParams) obj;
-      return Objects.equals(this.nested, that.nested) && internalEquals(that);
-    }
-  }
-
-  private static final class DirectTraversalRootImpl implements DirectTraversalRoot {
-    private final Path rootDir;
-    private final PathFragment relativeDir;
-
-    static DirectTraversalRoot forPackage(Artifact buildFile) {
-      return new DirectTraversalRootImpl(buildFile.getRoot().getPath(),
-          buildFile.getRootRelativePath().getParentDirectory());
-    }
-
-    static DirectTraversalRoot forFileOrDirectory(Artifact fileOrDirectory) {
-      return new DirectTraversalRootImpl(fileOrDirectory.getRoot().getPath(),
-          fileOrDirectory.getRootRelativePath());
-    }
-
-    private DirectTraversalRootImpl(Path rootDir, PathFragment relativeDir) {
-      this.rootDir = rootDir;
-      this.relativeDir = relativeDir;
-    }
-
-    @Override
-    public Path getRootPart() {
-      return rootDir;
-    }
-
-    @Override
-    public PathFragment getRelativePart() {
-      return relativeDir;
-    }
-
-    @Override
-    public RootedPath asRootedPath() {
-      return RootedPath.toRootedPath(rootDir, relativeDir);
+      return new AutoValue_FilesetTraversalParamsFactory_NestedTraversalParams(
+          ownerLabel, destDir, getOrderedExcludes(excludes), nested);
     }
   }
 }