src/main/java/com/google/devtools/build/lib/skyframe/rewinding/RewindableGraphInconsistencyReceiver.java

// Copyright 2022 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.rewinding;

import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.ImmutableList.toImmutableList;

import com.google.common.collect.ConcurrentHashMultiset;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multiset;
import com.google.common.flogger.GoogleLogger;
import com.google.devtools.build.lib.skyframe.NodeDroppingInconsistencyReceiver;
import com.google.devtools.build.lib.util.StringUtil;
import com.google.devtools.build.skyframe.GraphInconsistencyReceiver;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.proto.GraphInconsistency.Inconsistency;
import com.google.devtools.build.skyframe.proto.GraphInconsistency.InconsistencyStats;
import com.google.devtools.build.skyframe.proto.GraphInconsistency.InconsistencyStats.InconsistencyStat;
import java.util.Collection;
import java.util.function.Predicate;
import java.util.function.Supplier;
import javax.annotation.Nullable;

/**
 * {@link GraphInconsistencyReceiver} for evaluations operating on graphs that support rewinding (no
 * reverse dependencies, no action cache).
 *
 * <p>Action rewinding results in various kinds of inconsistencies which this receiver tolerates.
 * The first occurrence of each type of tolerated inconsistency is logged. Stats are collected and
 * available through {@link #getInconsistencyStats}.
 *
 * <p>{@link #reset} should be called between commands to clear stats and reset the {@link
 * #rewindingInitiated} state used for consistency checks.
 */
public final class RewindableGraphInconsistencyReceiver implements GraphInconsistencyReceiver {

  private static final GoogleLogger logger = GoogleLogger.forEnclosingClass();

  private static final int LOGGED_CHILDREN_LIMIT = 50;

  private final Multiset<Inconsistency> selfCounts = ConcurrentHashMultiset.create();
  private final Multiset<Inconsistency> childCounts = ConcurrentHashMultiset.create();
  private boolean rewindingInitiated = false;
  private boolean heuristicallyDropNodes = false;

  public void setHeuristicallyDropNodes(boolean heuristicallyDropNodes) {
    this.heuristicallyDropNodes = heuristicallyDropNodes;
  }

  @Override
  public void noteInconsistencyAndMaybeThrow(
      SkyKey key, @Nullable Collection<SkyKey> otherKeys, Inconsistency inconsistency) {
    if (heuristicallyDropNodes
        && NodeDroppingInconsistencyReceiver.isExpectedInconsistency(
            key, otherKeys, inconsistency)) {
      // If `--heuristically_drop_nodes` is enabled, check whether the inconsistency is caused by
      // dropped state node. If so, tolerate the inconsistency and return.
      return;
    }

    // RESET_REQUESTED and PARENT_FORCE_REBUILD_OF_CHILD may be the first inconsistencies seen with
    // rewinding. BUILDING_PARENT_FOUND_UNDONE_CHILD may also be seen, but it will not be the first.
    switch (inconsistency) {
      case RESET_REQUESTED:
        checkState(
            RewindingInconsistencyUtils.isTypeThatDependsOnRewindableNodes(key),
            "Unexpected reset requested for: %s",
            key);
        boolean isFirst = noteSelfInconsistency(inconsistency);
        if (isFirst) {
          logger.atInfo().log("Reset requested for: %s", key);
        }
        rewindingInitiated = true;
        return;

      case PARENT_FORCE_REBUILD_OF_CHILD:
        boolean parentMayForceRebuildChildren =
            RewindingInconsistencyUtils.mayForceRebuildChildren(key);
        ImmutableList<SkyKey> unrewindableRebuildChildren =
            otherKeys.stream()
                .filter(Predicate.not(RewindingInconsistencyUtils::isRewindable))
                .collect(toImmutableList());
        checkState(
            parentMayForceRebuildChildren && unrewindableRebuildChildren.isEmpty(),
            "Unexpected force rebuild, parent = %s, children = %s",
            key,
            listChildren(parentMayForceRebuildChildren ? unrewindableRebuildChildren : otherKeys));
        isFirst = noteSelfInconsistency(inconsistency);
        childCounts.add(inconsistency, otherKeys.size());
        if (isFirst) {
          logger.atInfo().log(
              "Parent force rebuild of children: parent = %s, children = %s",
              key, listChildren(otherKeys));
        }
        rewindingInitiated = true;
        return;

      case BUILDING_PARENT_FOUND_UNDONE_CHILD:
        boolean parentDependsOnRewindableNodes =
            RewindingInconsistencyUtils.isTypeThatDependsOnRewindableNodes(key);
        ImmutableList<SkyKey> unrewindableUndoneChildren =
            otherKeys.stream()
                .filter(Predicate.not(RewindingInconsistencyUtils::isRewindable))
                .collect(toImmutableList());
        checkState(
            rewindingInitiated
                && parentDependsOnRewindableNodes
                && unrewindableUndoneChildren.isEmpty(),
            "Unexpected undone children: parent = %s, children = %s",
            key,
            listChildren(
                rewindingInitiated && parentDependsOnRewindableNodes
                    ? unrewindableUndoneChildren
                    : otherKeys));
        isFirst = noteSelfInconsistency(inconsistency);
        childCounts.add(inconsistency, otherKeys.size());
        if (isFirst) {
          logger.atInfo().log(
              "Building parent found undone children: parent = %s, children = %s",
              key, listChildren(otherKeys));
        }
        return;

      default:
        throw new IllegalStateException(
            String.format(
                "Unexpected inconsistency %s, key = %s, otherKeys = %s",
                inconsistency, key, listChildren(otherKeys)));
    }
  }

  /**
   * Returns an object suitable for use as a string format arg in precondition checks or logger
   * statements.
   */
  private static Object listChildren(@Nullable Collection<SkyKey> children) {
    if (children == null) {
      return "null";
    }
    if (children.size() <= LOGGED_CHILDREN_LIMIT) {
      return children;
    }
    return new Object() {
      @Override
      public String toString() {
        return StringUtil.listItemsWithLimit(new StringBuilder(), LOGGED_CHILDREN_LIMIT, children)
            .toString();
      }
    };
  }

  /**
   * Notes in {@link #selfCounts} that an inconsistency occurred and returns true if it was the
   * first one detected.
   */
  private boolean noteSelfInconsistency(Inconsistency inconsistency) {
    return selfCounts.add(inconsistency, 1) == 0;
  }

  @Override
  public boolean restartPermitted() {
    return true;
  }

  @Override
  public InconsistencyStats getInconsistencyStats() {
    InconsistencyStats.Builder builder = InconsistencyStats.newBuilder();
    addInconsistencyStats(selfCounts, builder::addSelfStatsBuilder);
    addInconsistencyStats(childCounts, builder::addChildStatsBuilder);
    return builder.build();
  }

  private static void addInconsistencyStats(
      Multiset<Inconsistency> inconsistencies,
      Supplier<InconsistencyStat.Builder> builderSupplier) {
    inconsistencies.forEachEntry(
        (inconsistency, count) ->
            builderSupplier.get().setInconsistency(inconsistency).setCount(count));
  }

  @Override
  public void reset() {
    selfCounts.clear();
    childCounts.clear();
    rewindingInitiated = false;
  }
}