src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java

// Copyright 2017 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.collect.nestedset;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;
import com.google.devtools.build.lib.actions.CommandLineItem;
import com.google.devtools.build.lib.actions.CommandLineItem.MapFn;
import com.google.devtools.build.lib.util.Fingerprint;
import com.google.devtools.build.lib.vfs.DigestHashFunction;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

/** Computes fingerprints for nested sets, reusing sub-computations from children. */
public class NestedSetFingerprintCache {
  private static final int EMPTY_SET_DIGEST = 104_395_303;

  /** Memoize the subresults. We have to have one cache per type of command item map function. */
  private Map<CommandLineItem.MapFn<?>, DigestMap> mapFnToDigestMap = createMap();

  private final Set<Class<?>> seenMapFns = new HashSet<>();
  private final Multiset<Class<?>> seenParametrizedMapFns = HashMultiset.create();

  public <T> void addNestedSetToFingerprint(Fingerprint fingerprint, NestedSet<T> nestedSet) {
    addNestedSetToFingerprint(CommandLineItem.MapFn.DEFAULT, fingerprint, nestedSet);
  }

  public <T> void addNestedSetToFingerprint(
      CommandLineItem.MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet) {
    if (mapFn instanceof CommandLineItem.CapturingMapFn) {
      addNestedSetToFingerprintSlow(mapFn, fingerprint, nestedSet);
      return;
    }
    // Only top-level nested sets can be empty, so we can bail here
    if (nestedSet.isEmpty()) {
      fingerprint.addInt(EMPTY_SET_DIGEST);
      return;
    }
    DigestMap digestMap = mapFnToDigestMap.computeIfAbsent(mapFn, this::newDigestMap);
    fingerprint.addInt(nestedSet.getOrder().ordinal());
    Object children = nestedSet.getChildren();
    addToFingerprint(mapFn, fingerprint, digestMap, children);
  }

  private <T> void addNestedSetToFingerprintSlow(
      MapFn<? super T> mapFn, Fingerprint fingerprint, NestedSet<T> nestedSet) {
    for (T object : nestedSet.toList()) {
      addToFingerprint(mapFn, fingerprint, object);
    }
  }

  public void clear() {
    mapFnToDigestMap = createMap();
    seenMapFns.clear();
    seenParametrizedMapFns.clear();
  }

  @SuppressWarnings("unchecked")
  private <T> void addToFingerprint(
      CommandLineItem.MapFn<? super T> mapFn,
      Fingerprint fingerprint,
      DigestMap digestMap,
      Object children) {
    if (children instanceof Object[]) {
      if (!digestMap.readDigest(children, fingerprint)) {
        Fingerprint childrenFingerprint = new Fingerprint();
        for (Object child : (Object[]) children) {
          addToFingerprint(mapFn, childrenFingerprint, digestMap, child);
        }
        digestMap.insertAndReadDigest(children, childrenFingerprint, fingerprint);
      }
    } else {
      addToFingerprint(mapFn, fingerprint, (T) children);
    }
  }

  @VisibleForTesting
  <T> void addToFingerprint(
      CommandLineItem.MapFn<? super T> mapFn, Fingerprint fingerprint, T object) {
    mapFn.expandToCommandLine(object, fingerprint::addString);
  }

  private static Map<CommandLineItem.MapFn<?>, DigestMap> createMap() {
    return new ConcurrentHashMap<>();
  }

  private DigestMap newDigestMap(CommandLineItem.MapFn<?> mapFn) {
    Class<?> mapFnClass = mapFn.getClass();
    if (mapFn instanceof CommandLineItem.ParametrizedMapFn) {
      int occurrences = seenParametrizedMapFns.add(mapFnClass, 1) + 1;
      if (occurrences > ((CommandLineItem.ParametrizedMapFn) mapFn).maxInstancesAllowed()) {
        throw new IllegalArgumentException(
            String.format(
                "Too many instances of CommandLineItem.ParametrizedMapFn '%s' detected. "
                    + "Please construct fewer instances or use CommandLineItem.CapturingMapFn.",
                mapFnClass.getName()));
      }
    } else {
      if (!seenMapFns.add(mapFnClass)) {
        throw new IllegalArgumentException(
            String.format(
                "Illegal mapFn implementation: '%s'. "
                    + "CommandLineItem.MapFn instances must be singletons. "
                    + "Please see CommandLineItem.ParametrizedMapFn or "
                    + "CommandLineItem.CapturingMapFn for alternatives.",
                mapFnClass.getName()));
      }
    }
    // TODO(b/112460990): Use the value from DigestHashFunction.getDefault(), but check for
    // contention.
    return new DigestMap(DigestHashFunction.SHA256, 1024);
  }
}