Canonicalize some TransitiveTraversalValue objects -- those corresponding to error-free built-in rules, and to non-rules. This should save memory, as well as CPU for built-in rules, since we don't have to make sets out of their providers more than once.

Also fix a bug in the equality check where we weren't comparing the canHaveAnyProvider field properly.

--
MOS_MIGRATED_REVID=126121351

2 files changed, 136 insertions, 31 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/InternerWithPresenceCheck.java b/src/main/java/com/google/devtools/build/lib/skyframe/InternerWithPresenceCheck.java
new file mode 100644
index 0000000000..d80b3b5416
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/InternerWithPresenceCheck.java
@@ -0,0 +1,47 @@
+// Copyright 2016 The Bazel Authors. 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 static com.google.common.base.Preconditions.checkNotNull;
+
+import com.google.common.collect.Interner;
+import com.google.common.collect.MapMaker;
+
+import java.util.concurrent.ConcurrentMap;
+
+import javax.annotation.Nullable;
+
+/**
+ * Strong {@link Interner} that also exposes whether there is a canonical representative for the
+ * given sample object via {@link #getCanonical}.
+ */
+public class InternerWithPresenceCheck<T> implements Interner<T> {
+  private final ConcurrentMap<T, T> map = new MapMaker().makeMap();
+
+  @Override
+  public T intern(T sample) {
+    T canonical = map.putIfAbsent(checkNotNull(sample), sample);
+    return (canonical == null) ? sample : canonical;
+  }
+
+  /**
+   * Returns the canonical representative for {@code sample} if it is present. Unlike {@link
+   * #intern}, does not store {@code sample}. In other words, this method does not mutate the
+   * interner.
+   */
+  @Nullable
+  T getCanonical(T sample) {
+    return map.get(sample);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
index 9389c79a81..24ed4bb6c7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TransitiveTraversalValue.java
@@ -19,57 +19,115 @@ import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.RuleClass;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.List;
 import java.util.Objects;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
 
 import javax.annotation.Nullable;
 
 /**
  * A <i>transitive</i> target reference that, when built in skyframe, loads the entire transitive
- * closure of a target. Retains the first error message found during the transitive traversal,
- * and a set of names of providers if the target is a {@link Rule}.
+ * closure of a target. Retains the first error message found during the transitive traversal, and a
+ * set of names of providers if the target is a {@link Rule}.
+ *
+ * <p>Interns values for error-free traversal nodes that correspond to built-in rules.
  */
 @Immutable
 @ThreadSafe
 public class TransitiveTraversalValue implements SkyValue {
+  private static final TransitiveTraversalValue EMPTY_VALUE =
+      new TransitiveTraversalValue(false, ImmutableSet.<String>of(), null);
+  // A quick-lookup cache that allows us to get the value for a given RuleClass, assuming no error
+  // messages for the target. Only stores built-in RuleClass objects to avoid memory bloat.
+  private static final ConcurrentMap<RuleClass, TransitiveTraversalValue> VALUES_BY_RULE_CLASS =
+      new ConcurrentHashMap<>();
+  /**
+   * A strong interner of TransitiveTargetValue objects. Because we only wish to intern values for
+   * built-in rules, we need an interner with an additional method to return the canonical
+   * representative if it is present without interning our sample. This is only mutated in {@link
+   * #forTarget}, and read in {@link #forTarget} and {@link #create}.
+   */
+  private static final InternerWithPresenceCheck<TransitiveTraversalValue> VALUE_INTERNER =
+      new InternerWithPresenceCheck<>();
+
+  static {
+    VALUE_INTERNER.intern(EMPTY_VALUE);
+  }
+
   private final boolean canHaveAnyProvider;
-  @Nullable private final ImmutableSet<String> providers;
+  private final ImmutableSet<String> providers;
   @Nullable private final String firstErrorMessage;
 
-  public TransitiveTraversalValue(boolean canHaveAnyProvider,
-      @Nullable Iterable<String> providers, @Nullable String firstErrorMessage) {
+  private TransitiveTraversalValue(
+      boolean canHaveAnyProvider,
+      ImmutableSet<String> providers,
+      @Nullable String firstErrorMessage) {
     this.canHaveAnyProvider = canHaveAnyProvider;
-    this.providers = (providers == null) ? null : canonicalSet(providers);
+    this.providers = Preconditions.checkNotNull(providers);
     this.firstErrorMessage =
         (firstErrorMessage == null) ? null : StringCanonicalizer.intern(firstErrorMessage);
   }
 
-  public static TransitiveTraversalValue unsuccessfulTransitiveTraversal(String firstErrorMessage) {
-    return new TransitiveTraversalValue(false, null, Preconditions.checkNotNull(firstErrorMessage));
+  static TransitiveTraversalValue unsuccessfulTransitiveTraversal(String firstErrorMessage) {
+    return new TransitiveTraversalValue(
+        false, ImmutableSet.<String>of(), Preconditions.checkNotNull(firstErrorMessage));
   }
 
-  public static TransitiveTraversalValue forTarget(
-      Target target, @Nullable String firstErrorMessage) {
+  static TransitiveTraversalValue forTarget(Target target, @Nullable String firstErrorMessage) {
     if (target instanceof Rule) {
       Rule rule = (Rule) target;
-      return new TransitiveTraversalValue(
-          rule.getRuleClassObject().canHaveAnyProvider(),
-          toStringSet(rule.getRuleClassObject().getAdvertisedProviders()),
-          firstErrorMessage);
+      RuleClass ruleClass = rule.getRuleClassObject();
+      if (firstErrorMessage == null && !ruleClass.isSkylark()) {
+        TransitiveTraversalValue value = VALUES_BY_RULE_CLASS.get(ruleClass);
+        if (value != null) {
+          return value;
+        }
+        ImmutableSet<String> providers = canonicalSet(toList(ruleClass.getAdvertisedProviders()));
+        value = new TransitiveTraversalValue(ruleClass.canHaveAnyProvider(), providers, null);
+        // May already be there from another RuleClass or a concurrent put.
+        value = VALUE_INTERNER.intern(value);
+        // May already be there from a concurrent put.
+        VALUES_BY_RULE_CLASS.putIfAbsent(ruleClass, value);
+        return value;
+      } else {
+        // If this is a Skylark rule, we may still get a cache hit from another RuleClass with the
+        // same providers.
+        return TransitiveTraversalValue.create(
+            ruleClass.canHaveAnyProvider(),
+            toList(rule.getRuleClassObject().getAdvertisedProviders()),
+            firstErrorMessage);
+      }
+    }
+    if (firstErrorMessage == null) {
+      return EMPTY_VALUE;
+    } else {
+      return new TransitiveTraversalValue(false, ImmutableSet.<String>of(), firstErrorMessage);
     }
-  return new TransitiveTraversalValue(false, ImmutableList.<String>of(), firstErrorMessage);
   }
 
-  public static TransitiveTraversalValue withProviders(
-      Collection<String> providers, @Nullable String firstErrorMessage) {
-    return new TransitiveTraversalValue(false, ImmutableSet.copyOf(providers), firstErrorMessage);
+  public static TransitiveTraversalValue create(
+      boolean canHaveAnyProvider,
+      Collection<String> providers,
+      @Nullable String firstErrorMessage) {
+    TransitiveTraversalValue value =
+        new TransitiveTraversalValue(
+            canHaveAnyProvider, canonicalSet(providers), firstErrorMessage);
+    if (firstErrorMessage == null) {
+      TransitiveTraversalValue oldValue = VALUE_INTERNER.getCanonical(value);
+      return oldValue == null ? value : oldValue;
+    }
+    return value;
   }
 
   private static ImmutableSet<String> canonicalSet(Iterable<String> strIterable) {
@@ -80,14 +138,15 @@ public class TransitiveTraversalValue implements SkyValue {
     return builder.build();
   }
 
-  private static ImmutableSet<String> toStringSet(Iterable<Class<?>> providers) {
-    ImmutableSet.Builder<String> pBuilder = new ImmutableSet.Builder<>();
-    if (providers != null) {
-      for (Class<?> clazz : providers) {
-        pBuilder.add(StringCanonicalizer.intern(clazz.getName()));
-      }
+  private static List<String> toList(Collection<Class<?>> providers) {
+    if (providers == null) {
+      return ImmutableList.of();
     }
-    return pBuilder.build();
+    List<String> strings = new ArrayList<>(providers.size());
+    for (Class<?> clazz : providers) {
+      strings.add(clazz.getName());
+    }
+    return strings;
   }
 
   /**
@@ -98,10 +157,9 @@ public class TransitiveTraversalValue implements SkyValue {
   }
 
   /**
-   * Returns the set of provider names from the target, if the target is a {@link Rule}. If there
-   * were errors loading the target, returns {@code null}.
+   * Returns the set of provider names from the target, if the target is a {@link Rule}. Otherwise
+   * returns the empty set.
    */
-  @Nullable
   public Set<String> getProviders() {
     return providers;
   }
@@ -124,9 +182,9 @@ public class TransitiveTraversalValue implements SkyValue {
       return false;
     }
     TransitiveTraversalValue that = (TransitiveTraversalValue) o;
-    return Objects.equals(this.firstErrorMessage, that.firstErrorMessage)
-        && Objects.equals(this.providers, that.providers)
-        && Objects.equals(this.canHaveAnyProvider, canHaveAnyProvider);
+    return this.canHaveAnyProvider == that.canHaveAnyProvider
+        && Objects.equals(this.firstErrorMessage, that.firstErrorMessage)
+        && this.providers.equals(that.providers);
   }
 
   @Override