src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java

// Copyright 2014 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.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.devtools.build.lib.skyframe.SkyValueRetrieverUtils.retrieveRemoteSkyValue;

import com.google.common.base.Joiner;
import com.google.common.base.MoreObjects;
import com.google.common.base.Predicates;
import com.google.common.base.Suppliers;
import com.google.common.base.Verify;
import com.google.common.collect.Collections2;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.MultimapBuilder;
import com.google.common.collect.SetMultimap;
import com.google.common.flogger.GoogleLogger;
import com.google.devtools.build.lib.actions.Action;
import com.google.devtools.build.lib.actions.ActionCacheChecker.Token;
import com.google.devtools.build.lib.actions.ActionCompletionEvent;
import com.google.devtools.build.lib.actions.ActionExecutedEvent.ErrorTiming;
import com.google.devtools.build.lib.actions.ActionExecutionException;
import com.google.devtools.build.lib.actions.ActionInputMap;
import com.google.devtools.build.lib.actions.ActionLookupData;
import com.google.devtools.build.lib.actions.ActionWithDiscoveredInputsState;
import com.google.devtools.build.lib.actions.Actions;
import com.google.devtools.build.lib.actions.AlreadyReportedActionExecutionException;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.ArtifactPathResolver;
import com.google.devtools.build.lib.actions.DelegatingPairInputMetadataProvider;
import com.google.devtools.build.lib.actions.DiscoveredInputsEvent;
import com.google.devtools.build.lib.actions.FileArtifactValue;
import com.google.devtools.build.lib.actions.InputMetadataProvider;
import com.google.devtools.build.lib.actions.LostInputsActionExecutionException;
import com.google.devtools.build.lib.actions.OutputMetadataStore;
import com.google.devtools.build.lib.actions.PackageRootResolver;
import com.google.devtools.build.lib.actions.RichArtifactData;
import com.google.devtools.build.lib.actions.RichDataProducingAction;
import com.google.devtools.build.lib.actions.SpawnMetrics;
import com.google.devtools.build.lib.analysis.BlazeDirectories;
import com.google.devtools.build.lib.bugreport.BugReport;
import com.google.devtools.build.lib.bugreport.BugReporter;
import com.google.devtools.build.lib.causes.Cause;
import com.google.devtools.build.lib.causes.LabelCause;
import com.google.devtools.build.lib.clock.BlazeClock;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
import com.google.devtools.build.lib.collect.nestedset.ArtifactNestedSetKey;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.collect.nestedset.Order;
import com.google.devtools.build.lib.io.InconsistentFilesystemException;
import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
import com.google.devtools.build.lib.profiler.Profiler;
import com.google.devtools.build.lib.profiler.ProfilerTask;
import com.google.devtools.build.lib.profiler.SilentCloseable;
import com.google.devtools.build.lib.server.FailureDetails.Execution;
import com.google.devtools.build.lib.server.FailureDetails.Execution.Code;
import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
import com.google.devtools.build.lib.skyframe.ArtifactFunction.MissingArtifactValue;
import com.google.devtools.build.lib.skyframe.ArtifactFunction.SourceArtifactException;
import com.google.devtools.build.lib.skyframe.ArtifactNestedSetFunction.ArtifactNestedSetEvalException;
import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ActionPostprocessing;
import com.google.devtools.build.lib.skyframe.rewinding.ActionRewindException;
import com.google.devtools.build.lib.skyframe.rewinding.ActionRewindStrategy;
import com.google.devtools.build.lib.skyframe.rewinding.ActionRewindStrategy.RewindPlanResult;
import com.google.devtools.build.lib.skyframe.serialization.SkyValueRetriever;
import com.google.devtools.build.lib.skyframe.serialization.SkyValueRetriever.RetrievalContext;
import com.google.devtools.build.lib.skyframe.serialization.SkyValueRetriever.SerializableSkyKeyComputeState;
import com.google.devtools.build.lib.skyframe.serialization.analysis.RemoteAnalysisCacheReaderDepsProvider;
import com.google.devtools.build.lib.util.DetailedExitCode;
import com.google.devtools.build.lib.util.DetailedExitCode.DetailedExitCodeComparator;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
import com.google.devtools.build.lib.vfs.BatchStat;
import com.google.devtools.build.lib.vfs.FileSystem;
import com.google.devtools.build.lib.vfs.OutputService;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.Root;
import com.google.devtools.build.skyframe.MemoizingEvaluator;
import com.google.devtools.build.skyframe.NodeEntry;
import com.google.devtools.build.skyframe.SkyFunction;
import com.google.devtools.build.skyframe.SkyFunctionException;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.SkyframeLookupResult;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.function.Predicate;
import java.util.function.Supplier;
import javax.annotation.Nullable;

/**
 * A {@link SkyFunction} that creates {@link ActionExecutionValue}s. There are four points where
 * this function can abort due to missing values in the graph:
 *
 * <ol>
 *   <li>For actions that discover inputs, if missing metadata needed to resolve an artifact from a
 *       string input in the action cache.
 *   <li>If missing metadata for artifacts in inputs (including the artifacts above).
 *   <li>For actions that discover inputs, if missing metadata for inputs discovered prior to
 *       execution.
 *   <li>For actions that discover inputs, but do so during execution, if missing metadata for
 *       inputs discovered during execution.
 * </ol>
 *
 * <p>If async action execution is enabled, or if a non-primary shared action coalesces with an
 * in-flight primary shared action's execution, this function can abort after declaring an external
 * dep on the execution's completion future.
 */
// Non-final for mocking.
public class ActionExecutionFunction implements SkyFunction {

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

  private final ActionRewindStrategy actionRewindStrategy;
  private final SkyframeActionExecutor skyframeActionExecutor;

  // Direct access to the MemoizingEvaluator should typically not be allowed in SkyFunctions. We
  // allow it here as an optimization for accessing inputs that are under an ArtifactNestedSet node
  // without adding a direct Skyframe edge on the input or its generating action.
  private final Supplier<MemoizingEvaluator> evaluator;

  private final BlazeDirectories directories;
  private final Supplier<TimestampGranularityMonitor> tsgm;
  private final BugReporter bugReporter;
  private final Supplier<ConsumedArtifactsTracker> consumedArtifactsTrackerSupplier;
  private final Supplier<RemoteAnalysisCacheReaderDepsProvider> cachingDependenciesSupplier;

  public ActionExecutionFunction(
      ActionRewindStrategy actionRewindStrategy,
      SkyframeActionExecutor skyframeActionExecutor,
      Supplier<MemoizingEvaluator> evaluator,
      BlazeDirectories directories,
      Supplier<TimestampGranularityMonitor> tsgm,
      BugReporter bugReporter,
      Supplier<RemoteAnalysisCacheReaderDepsProvider> cachingDependenciesSupplier,
      Supplier<ConsumedArtifactsTracker> consumedArtifactsTrackerSupplier) {
    this.actionRewindStrategy = checkNotNull(actionRewindStrategy);
    this.skyframeActionExecutor = checkNotNull(skyframeActionExecutor);
    this.evaluator = checkNotNull(evaluator);
    this.directories = checkNotNull(directories);
    this.tsgm = checkNotNull(tsgm);
    this.bugReporter = checkNotNull(bugReporter);
    this.cachingDependenciesSupplier = cachingDependenciesSupplier;
    this.consumedArtifactsTrackerSupplier = consumedArtifactsTrackerSupplier;
  }

  @Override
  @Nullable
  public SkyValue compute(SkyKey skyKey, Environment env)
      throws ActionExecutionFunctionException, InterruptedException {
    ActionLookupData actionLookupData = (ActionLookupData) skyKey.argument();
    RemoteAnalysisCacheReaderDepsProvider remoteCachingDependencies =
        cachingDependenciesSupplier.get();
    if (remoteCachingDependencies.mode().isRetrievalEnabled()
        && !remoteCachingDependencies.getSkycacheAnalysisOnly()
        && !skyframeActionExecutor.shouldSkipRetrieval(actionLookupData)) {
      switch (retrieveRemoteSkyValue(
          actionLookupData, env, remoteCachingDependencies, InputDiscoveryState::new)) {
        case SkyValueRetriever.Restart unused:
          return null;
        case SkyValueRetriever.RetrievedValue v:
          return v.value();
        case SkyValueRetriever.NoCachedData unused:
          break;
      }
    }
    Action action =
        ActionUtils.getActionForLookupData(
            env,
            actionLookupData,
            /* crashIfActionOwnerMissing= */ !remoteCachingDependencies
                .mode()
                .isRetrievalEnabled());
    if (action == null) {
      return null;
    }

    try {
      SkyValue result = computeInternal(actionLookupData, action, env);
      if (result != null) {
        SkyValueRetrieverUtils.tryUploadAsync(
            remoteCachingDependencies, actionLookupData, result, env);
      }
      return result;
    } catch (ActionExecutionFunctionException e) {
      skyframeActionExecutor.recordExecutionError();
      throw e;
    } catch (UndoneInputsException e) {
      return actionRewindStrategy.patchNestedSetGraphToPropagateError(
          actionLookupData, action, e.undoneInputs, e.inputDepKeys);
    }
  }

  @Nullable
  private SkyValue computeInternal(
      ActionLookupData actionLookupData, Action action, Environment env)
      throws ActionExecutionFunctionException, InterruptedException, UndoneInputsException {
    if (Actions.dependsOnBuildId(action)) {
      PrecomputedValue.BUILD_ID.get(env);
    }

    // Look up the parts of the environment that influence the action.
    Collection<String> clientEnvironmentVariables = action.getClientEnvironmentVariables();
    ImmutableMap<String, String> clientEnv;
    if (!clientEnvironmentVariables.isEmpty()) {
      ImmutableSet<String> clientEnvironmentVariablesSet =
          ImmutableSet.copyOf(clientEnvironmentVariables);
      Iterable<SkyKey> depKeys =
          Iterables.transform(clientEnvironmentVariablesSet, ClientEnvironmentFunction::key);
      SkyframeLookupResult clientEnvLookup = env.getValuesAndExceptions(depKeys);
      if (env.valuesMissing()) {
        return null;
      }
      ImmutableMap.Builder<String, String> builder =
          ImmutableMap.builderWithExpectedSize(clientEnvironmentVariablesSet.size());
      for (SkyKey depKey : depKeys) {
        EnvironmentVariableValue envValue = (EnvironmentVariableValue) clientEnvLookup.get(depKey);
        if (envValue.value() != null) {
          builder.put((String) depKey.argument(), envValue.value());
        }
      }
      clientEnv = builder.buildOrThrow();
    } else {
      clientEnv = ImmutableMap.of();
    }

    // If two actions are shared and the first one executes, when the second one goes to execute, we
    // should detect that and short-circuit.
    //
    // Additionally, if an action restarted (in the Skyframe sense) after it executed because it
    // discovered new inputs during execution, we should detect that and short-circuit.
    //
    // Separately, we use InputDiscoveryState to avoid redoing work on Skyframe restarts for actions
    // that discover inputs. This is not [currently] relevant here, because it is [currently] not
    // possible for an action to both be shared and also discover inputs; see b/72764586.
    ActionExecutionState previousExecution = skyframeActionExecutor.probeActionExecution(action);

    // If this action was previously completed this build, then this evaluation must be happening
    // because of rewinding. Prevent any progress events from being published a second time for this
    // action; downstream consumers of action events reasonably don't expect them.
    if (!skyframeActionExecutor.shouldEmitProgressEvents(action)) {
      env = new ProgressEventSuppressingEnvironment(env);
    }

    InputDiscoveryState state;
    if (action.discoversInputs()) {
      state = env.getState(InputDiscoveryState::new);
    } else {
      // Because this is a new state, all conditionals below about whether state has already done
      // something will return false, and so we will execute all necessary steps.
      state = new InputDiscoveryState();
    }
    if (!state.hasCollectedInputs()) {
      try {
        state.allInputs = collectInputs(action, env);
      } catch (AlreadyReportedActionExecutionException e) {
        throw new ActionExecutionFunctionException(e);
      }
      if (state.allInputs == null) {
        // Missing deps.
        return null;
      }
    }

    CheckInputResults checkedInputs = null;
    NestedSet<Artifact> allInputs = state.allInputs.getAllInputs();

    if (!state.actionInputCollectedEventSent) {
      env.getListener()
          .post(
              ActionInputCollectedEvent.create(
                  action, allInputs, skyframeActionExecutor.getActionContextRegistry()));
      state.actionInputCollectedEventSent = true;
    }

    if (!state.hasArtifactData()) {
      ImmutableSet<SkyKey> inputDepKeys =
          getInputDepKeys(
              consumedArtifactsTrackerSupplier.get(),
              allInputs,
              action.getSchedulingDependencies(),
              state);

      SkyframeLookupResult inputDepsResult = env.getValuesAndExceptions(inputDepKeys);
      if (previousExecution == null) {
        // Do we actually need to find our metadata?
        try {
          checkedInputs = checkInputs(env, action, inputDepsResult, allInputs, inputDepKeys);
        } catch (ActionExecutionException e) {
          throw new ActionExecutionFunctionException(e);
        }
      }
      if (env.valuesMissing()) {
        // There was missing artifact metadata in the graph. Wait for it to be present.
        // We must check this and return here before attempting to establish any Skyframe
        // dependencies of the action; see establishSkyframeDependencies why.
        return null;
      }
    }

    if (checkedInputs != null) {
      checkState(!state.hasArtifactData(), "%s %s", state, action);
      state.inputArtifactData = checkedInputs.actionInputMap;
      state.actionInputMetadataProvider = new ActionInputMetadataProvider(state.inputArtifactData);
      state.skyframeInputMetadataProvider =
          new SkyframeInputMetadataProvider(
              evaluator.get(),
              skyframeActionExecutor.getPerBuildFileCache(),
              directories.getRelativeOutputPath());
      state.compositeInputMetadataProvider =
          new DelegatingPairInputMetadataProvider(
              state.actionInputMetadataProvider, state.skyframeInputMetadataProvider);
      if (skyframeActionExecutor.actionFileSystemType().isEnabled()) {
        state.actionFileSystem =
            skyframeActionExecutor.createActionFileSystem(
                directories.getRelativeOutputPath(),
                state.compositeInputMetadataProvider,
                action.getOutputs());
      }
    }

    skyframeActionExecutor.acquireActionExecutionSemaphore();
    long actionStartTime = BlazeClock.nanoTime();
    ActionExecutionValue result;
    try {
      result =
          checkCacheAndExecuteIfNeeded(
              action,
              state,
              allInputs,
              env,
              clientEnv,
              actionLookupData,
              previousExecution,
              actionStartTime);
    } catch (LostInputsActionExecutionException e) {
      ImmutableSet<SkyKey> inputDepKeys =
          getInputDepKeys(
              /* consumedArtifactsTracker= */ null,
              allInputs,
              action.getSchedulingDependencies(),
              /* state= */ null);
      ActionInputMap inputArtifactData = state.inputArtifactData;
      if (inputArtifactData == null) {
        // Reconstitute inputArtifactData if it was not present in `state`.
        //
        // This can happen after Skyframe restarts inside `handleLostInputs`, when remote analysis
        // is enabled. This is primarily for non-input discovering actions, but could potentially
        // occur for input-discovering actions if SkyKeyComputeState is evicted.
        try {
          // Since `checkInputs` must have succeeded prior to `checkCacheAndExecuteIfNeeded`, it
          // should succeed here.
          inputArtifactData =
              checkInputs(
                      env,
                      action,
                      env.getValuesAndExceptions(inputDepKeys),
                      allInputs,
                      inputDepKeys)
                  .actionInputMap;
        } catch (ActionExecutionException e2) {
          // This should be impossible since metadata was already checked once, but we handle it
          // for completeness.
          throw new ActionExecutionFunctionException(e2);
        }
      }
      NestedSet<Artifact> discoveredInputs = null;
      if (action.discoversInputs()) {
        if (state.discoveredInputs != null) {
          discoveredInputs = state.discoveredInputs;
        } else if (action.inputsKnown()) {
          discoveredInputs = action.getInputs();
        }
      }

      return handleLostInputs(
          e,
          actionLookupData,
          action,
          actionStartTime,
          env,
          inputDepKeys,
          discoveredInputs,
          inputArtifactData);
    } catch (ActionExecutionException e) {
      // In this case we do not report the error to the action reporter because we have already
      // done it in SkyframeActionExecutor.reportErrorIfNotAbortingMode() method. That method
      // prints the error in the top-level reporter and also dumps the recorded StdErr for the
      // action. Label can be null in the case of, e.g., the SystemActionOwner (for build-info.txt).
      throw new ActionExecutionFunctionException(new AlreadyReportedActionExecutionException(e));
    } finally {
      skyframeActionExecutor.releaseActionExecutionSemaphore();
    }

    if (env.valuesMissing()) {
      // This usually happens only for input-discovering actions. Other actions may have
      // valuesMissing() here in rare circumstances related to Fileset inputs being unavailable.
      // See comments in ActionInputMapHelper#getFilesets().
      return null;
    }

    // We're done with the action. Clear the cached NestedSet list representations to save memory.
    action.getInputs().clearCachedListRepresentation();
    allInputs.clearCachedListRepresentation();

    // After the action execution is finalized, unregister the outputs from the consumed set to save
    // memory.
    if (consumedArtifactsTrackerSupplier.get() != null) {
      consumedArtifactsTrackerSupplier
          .get()
          .unregisterOutputsAfterExecutionDone(action.getOutputs());
    }

    return result;
  }

  private static ImmutableSet<SkyKey> getInputDepKeys(
      @Nullable ConsumedArtifactsTracker consumedArtifactsTracker,
      NestedSet<Artifact> allInputs,
      NestedSet<Artifact> schedulingDependencies,
      @Nullable // may be null if consumedArtifactsTracker is null
          InputDiscoveryState state) {
    ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();

    // Register the action's inputs and scheduling deps as "consumed" in the build.
    // As a general rule, we do it before requesting for the evaluation of these artifacts. This
    // would provide a good estimate of which outputs are consumed.
    boolean registerConsumed =
        consumedArtifactsTracker != null && !state.checkedForConsumedArtifactRegistration;
    if (registerConsumed) {
      state.checkedForConsumedArtifactRegistration = true;
    }

    // We "unwrap" the NestedSet and evaluate the first layer of direct Artifacts here in order to
    // save memory:
    // - This top layer costs 1 extra ArtifactNestedSetKey node.
    // - It's uncommon that 2 actions share the exact same set of inputs
    //   => the top layer offers little in terms of reusability.
    ArtifactNestedSetKey.visitDirectDeps(
        allInputs,
        leaf -> {
          if (registerConsumed) {
            consumedArtifactsTracker.registerConsumedArtifact(leaf);
          }
          result.add(Artifact.key(leaf));
        },
        result::add);

    if (schedulingDependencies.isSingleton()) {
      Artifact schedulingDep = schedulingDependencies.getSingleton();
      if (registerConsumed) {
        consumedArtifactsTracker.registerConsumedArtifact(schedulingDep);
      }
      result.add(Artifact.key(schedulingDep));
    } else if (!schedulingDependencies.isEmpty()) {
      result.add(ArtifactNestedSetKey.create(schedulingDependencies));
    }

    return result.build();
  }

  /**
   * Cleans up state associated with the current action execution attempt and returns a {@link
   * Reset} value which rewinds the actions that generate the lost inputs.
   */
  @Nullable // null if there were missing dependencies
  private Reset handleLostInputs(
      LostInputsActionExecutionException e,
      ActionLookupData actionLookupData,
      Action action,
      long actionStartTimeNanos,
      Environment env,
      ImmutableSet<SkyKey> inputDepKeys,
      @Nullable // non-null if the Action discovers inputs and input discovery succeeded
          NestedSet<Artifact> discoveredInputs,
      ActionInputMap inputArtifactData)
      throws InterruptedException, ActionExecutionFunctionException {
    checkState(
        e.isPrimaryAction(actionLookupData),
        "Non-primary action handling lost inputs exception: %s %s",
        actionLookupData,
        e);

    // inputDepKeys only contains keys in the initial, pre-input-discovery Skyframe request. If the
    // action discovers inputs, we must combine them with discovered input keys.
    ImmutableSet<SkyKey> failedActionDeps;
    if (e.isFromInputDiscovery()) {
      // The action failed during input discovery. We don't know the discovered inputs, so just add
      // keys of lost inputs in case any of them were discovered.
      failedActionDeps =
          ImmutableSet.<SkyKey>builder()
              .addAll(inputDepKeys)
              .addAll(
                  Collections2.transform(
                      e.getLostInputs().values(), input -> Artifact.key((Artifact) input)))
              .build();
    } else if (discoveredInputs != null) {
      failedActionDeps =
          ImmutableSet.<SkyKey>builder()
              .addAll(inputDepKeys)
              .addAll(Artifact.keys(discoveredInputs.toList()))
              .build();
    } else {
      failedActionDeps = inputDepKeys;
    }

    RewindPlanResult rewindPlanResult = null;
    try {
      rewindPlanResult =
          actionRewindStrategy.prepareRewindPlanForLostInputs(
              actionLookupData,
              action,
              failedActionDeps,
              e,
              inputArtifactData,
              env,
              actionStartTimeNanos);
    } catch (ActionRewindException rewindingFailedException) {
      throw new ActionExecutionFunctionException(
          new AlreadyReportedActionExecutionException(
              skyframeActionExecutor.processAndGetExceptionToThrow(
                  env.getListener(),
                  e.getPrimaryOutputPath(),
                  action,
                  new ActionExecutionException(
                      rewindingFailedException,
                      action,
                      /* catastrophe= */ false,
                      rewindingFailedException.getDetailedExitCode()),
                  e.getFileOutErr(),
                  ErrorTiming.AFTER_EXECUTION)));
    } finally {
      if (e.isActionStartedEventAlreadyEmitted() && rewindPlanResult == null) {
        // Rewinding was unsuccessful. SkyframeActionExecutor's ActionRunner didn't emit an
        // ActionCompletionEvent because it hoped rewinding would fix things. Because it won't, this
        // must emit one to compensate.
        ActionInputMetadataProvider inputMetadataProvider =
            new ActionInputMetadataProvider(inputArtifactData);
        env.getListener()
            .post(
                new ActionCompletionEvent(
                    actionStartTimeNanos,
                    BlazeClock.nanoTime(),
                    action,
                    inputMetadataProvider,
                    /* outputMetadataStore= */ null,
                    actionLookupData));
      }
    }
    return rewindPlanResult.toNullIfMissingDependenciesElseReset();
  }

  /**
   * An action's inputs needed for execution. May not just be the result of Action#getInputs(). If
   * the action cache's view of this action contains additional inputs, it will request metadata for
   * them, so we consider those inputs as dependencies of this action as well. Returns null if some
   * dependencies were missing and this ActionExecutionFunction needs to restart.
   */
  @Nullable
  private AllInputs collectInputs(Action action, Environment env)
      throws InterruptedException, AlreadyReportedActionExecutionException {
    if (action.inputsKnown()) {
      return new AllInputs(action.getInputs());
    }

    checkState(action.discoversInputs(), action);
    List<Artifact> actionCacheInputs =
        skyframeActionExecutor.getActionCachedInputs(
            action, new PackageRootResolverWithEnvironment(env));
    if (actionCacheInputs == null) {
      checkState(env.valuesMissing(), action);
      return null;
    }

    // Actions which pruned their inputs may be able to get an action cache hit without requesting
    // the full set of original inputs. We'll request them later on if there is no action cache hit.
    NestedSet<Artifact> allKnownInputs =
        action.prunedInputs() ? NestedSetBuilder.emptySet(Order.STABLE_ORDER) : action.getInputs();
    return new AllInputs(allKnownInputs, actionCacheInputs);
  }

  static class AllInputs {
    final NestedSet<Artifact> defaultInputs;
    @Nullable final List<Artifact> actionCacheInputs;

    AllInputs(NestedSet<Artifact> defaultInputs) {
      this.defaultInputs = checkNotNull(defaultInputs);
      this.actionCacheInputs = null;
    }

    AllInputs(NestedSet<Artifact> defaultInputs, List<Artifact> actionCacheInputs) {
      this.defaultInputs = checkNotNull(defaultInputs);
      this.actionCacheInputs = checkNotNull(actionCacheInputs);
    }

    /** Compute the inputs to request from Skyframe. */
    NestedSet<Artifact> getAllInputs() {
      if (actionCacheInputs == null || actionCacheInputs.isEmpty()) {
        return defaultInputs;
      }
      return NestedSetBuilder.<Artifact>newBuilder(Order.STABLE_ORDER)
          .addTransitive(defaultInputs)
          .addAll(actionCacheInputs)
          .build();
    }
  }

  /**
   * Skyframe implementation of {@link PackageRootResolver}. Should be used only from SkyFunctions,
   * because it uses SkyFunction.Environment for evaluation of ContainingPackageLookupValue.
   */
  private static class PackageRootResolverWithEnvironment implements PackageRootResolver {
    private final List<ContainingPackageLookupValue.Key> packageLookupsRequested =
        new ArrayList<>();
    private final Environment env;

    private PackageRootResolverWithEnvironment(Environment env) {
      this.env = env;
    }

    @Nullable
    @Override
    public Map<PathFragment, Root> findPackageRootsForFiles(Iterable<PathFragment> execPaths)
        throws PackageRootException, InterruptedException {
      checkState(
          packageLookupsRequested.isEmpty(),
          "resolver should only be called once: %s %s",
          packageLookupsRequested,
          execPaths);
      // Create SkyKeys list based on execPaths.
      Map<PathFragment, ContainingPackageLookupValue.Key> depKeys = new HashMap<>();
      for (PathFragment path : execPaths) {
        PathFragment parent =
            checkNotNull(path.getParentDirectory(), "Must pass in files, not root directory");
        checkArgument(!parent.isAbsolute(), path);
        Optional<PackageIdentifier> pkgId =
            PackageIdentifier.discoverFromExecPath(path, /* forFiles= */ true);
        if (pkgId.isPresent()) {
          ContainingPackageLookupValue.Key depKey = ContainingPackageLookupValue.key(pkgId.get());
          depKeys.put(path, depKey);
          packageLookupsRequested.add(depKey);
        }
      }

      SkyframeLookupResult values = env.getValuesAndExceptions(depKeys.values());
      Map<PathFragment, Root> result = new HashMap<>();
      for (PathFragment path : execPaths) {
        if (!depKeys.containsKey(path)) {
          continue;
        }
        ContainingPackageLookupValue value;
        try {
          value =
              (ContainingPackageLookupValue)
                  values.getOrThrow(
                      depKeys.get(path),
                      BuildFileNotFoundException.class,
                      InconsistentFilesystemException.class);
        } catch (BuildFileNotFoundException e) {
          throw PackageRootException.create(path, e);
        } catch (InconsistentFilesystemException e) {
          throw PackageRootException.create(path, e);
        }
        if (value != null && value.hasContainingPackage()) {
          // We have found corresponding root for current execPath.
          result.put(path, value.getContainingPackageRoot());
        } else {
          // We haven't found corresponding root for current execPath.
          result.put(path, null);
        }
      }
      return env.valuesMissing() ? null : result;
    }
  }

  @Nullable
  private ActionExecutionValue checkCacheAndExecuteIfNeeded(
      Action action,
      InputDiscoveryState state,
      NestedSet<Artifact> allInputs,
      Environment env,
      Map<String, String> clientEnv,
      ActionLookupData actionLookupData,
      @Nullable ActionExecutionState previousAction,
      long actionStartTime)
      throws ActionExecutionException, InterruptedException {
    if (previousAction != null) {
      // There are two cases where we can already have an ActionExecutionState for a specific
      // output:
      // 1. Another instance of a shared action won the race and got executed first.
      // 2. The action was already started earlier, and this SkyFunction got restarted since
      //    there's progress to be made.
      // In either case, we must use this ActionExecutionState to continue. Note that in the first
      // case, we don't have any input metadata available, so we couldn't re-execute the action even
      // if we wanted to.
      if (state.discoveredInputs != null
          && action instanceof ActionWithDiscoveredInputsState actionWithDiscoveredInputsState) {
        // Re-inject discovered inputs from the SkyKeyComputeState if missing
        // dependencies of this action were rewinded, causing this action's
        // restart. We want to avoid recomputing them. See b/505164988 for more
        // details.
        actionWithDiscoveredInputsState.setAdditionalInputs(state.discoveredInputs);
      }
      return previousAction.getResultOrDependOnFuture(
          env,
          actionLookupData,
          action,
          skyframeActionExecutor.getSharedActionCallback(
              env.getListener(), state.discoveredInputs != null, action, actionLookupData));
    }

    ActionExecutionValue previousOutputs = null;
    if (skyframeActionExecutor.checkRewoundActionOutputs()
        && evaluator.get().isRewinding(actionLookupData)) {
      // Rewinding retains the prior SkyValue even while its node is being rebuilt. Unlike the
      // executor's per-build action map, this also covers local/remote cache hits and actions that
      // completed in a previous invocation. This is best effort: if another shared owner wins
      // execution, the shared-result shortcut above can bypass the check. Only inspect this key's
      // retained value, without introducing a dependency on ourselves.
      NodeEntry entry =
          evaluator.get().getExistingEntryAtCurrentlyEvaluatingVersion(actionLookupData);
      if (entry.toValue() instanceof ActionExecutionValue value) {
        previousOutputs = value;
      }
    }

    ArtifactPathResolver pathResolver =
        ArtifactPathResolver.createPathResolver(
            state.actionFileSystem, skyframeActionExecutor.getExecRoot());

    BatchStat batchStatter = null;
    if (state.actionFileSystem == null) {
      OutputService outputService = skyframeActionExecutor.getOutputService();
      if (outputService != null) {
        batchStatter = outputService.getBatchStatter();
      }
    }

    ActionOutputMetadataStore outputMetadataStore =
        ActionOutputMetadataStore.create(
            skyframeActionExecutor.useArchivedTreeArtifacts(action),
            skyframeActionExecutor.getOutputPermissions(),
            ImmutableSet.copyOf(action.getOutputs()),
            skyframeActionExecutor.getXattrProvider(),
            batchStatter,
            tsgm.get(),
            pathResolver);

    // We only need to check the action cache if we haven't done it on a previous run.
    if (!state.hasCheckedActionCache()) {
      state.token =
          skyframeActionExecutor.checkActionCache(
              env.getListener(),
              action,
              state.actionInputMetadataProvider,
              outputMetadataStore,
              pathResolver,
              actionStartTime,
              state.allInputs.actionCacheInputs,
              clientEnv,
              previousOutputs);
    }

    if (state.token == null) {
      RichArtifactData reconstructedRichArtifactData =
          action instanceof RichDataProducingAction rdpa
              ? rdpa.reconstructRichDataOnActionCacheHit(state.actionInputMetadataProvider)
              : null;
      return ActionExecutionValue.create(
          outputMetadataStore, reconstructedRichArtifactData, action);
    }

    outputMetadataStore.prepareForActionExecution();

    if (action.discoversInputs()) {
      Duration discoveredInputsDuration = Duration.ZERO;
      if (state.discoveredInputs == null) {
        if (!state.preparedInputDiscovery) {
          action.prepareInputDiscovery();
          state.preparedInputDiscovery = true;
        }

        try (SilentCloseable c =
            Profiler.instance().profile(ProfilerTask.DISCOVER_INPUTS, "discoverInputs")) {
          try (var unused = state.skyframeInputMetadataProvider.withSkyframeAllowed(env)) {
            state.discoveredInputs =
                skyframeActionExecutor.discoverInputs(
                    action,
                    actionLookupData,
                    allInputs,
                    state.compositeInputMetadataProvider,
                    env,
                    state.actionFileSystem);
          }
        }

        discoveredInputsDuration = Duration.ofNanos(BlazeClock.nanoTime() - actionStartTime);
        if (env.valuesMissing()) {
          checkState(
              state.discoveredInputs == null,
              "Inputs were discovered but more deps were requested by %s",
              action);
          return null;
        }
        checkNotNull(
            state.discoveredInputs,
            "Input discovery returned null but no more deps were requested by %s",
            action);
      }

      addDiscoveredInputs(state, env, action, /* afterExecution= */ false);
      if (env.valuesMissing()) {
        return null;
      }

      // When discover inputs completes, post an event with the duration values.
      env.getListener()
          .post(
              new DiscoveredInputsEvent(
                  SpawnMetrics.Builder.forOtherExec()
                      .setParseTime(discoveredInputsDuration)
                      .setTotalTime(discoveredInputsDuration)
                      .build(),
                  action,
                  actionStartTime));
    }

    return skyframeActionExecutor.executeAction(
        env,
        action,
        state.compositeInputMetadataProvider,
        outputMetadataStore,
        actionStartTime,
        actionLookupData,
        state.actionFileSystem,
        new ActionPostprocessingImpl(state),
        state.discoveredInputs != null,
        previousOutputs);
  }

  /** Implementation of {@link ActionPostprocessing}. */
  private final class ActionPostprocessingImpl implements ActionPostprocessing {
    private final InputDiscoveryState state;

    ActionPostprocessingImpl(InputDiscoveryState state) {
      this.state = state;
    }

    @Override
    public void run(
        Environment env,
        Action action,
        InputMetadataProvider inputMetadataProvider,
        OutputMetadataStore outputMetadataStore,
        Map<String, String> clientEnv)
        throws InterruptedException, ActionExecutionException {
      if (action.discoversInputs()) {
        state.discoveredInputs = action.getInputs();
        addDiscoveredInputs(state, env, action, /* afterExecution= */ true);
        if (env.valuesMissing()) {
          return;
        }
      }
      checkState(!env.valuesMissing(), action);
      skyframeActionExecutor.updateActionCache(
          action,
          state.inputMetadataProviderIncludingLateDiscoveredInputs(inputMetadataProvider),
          outputMetadataStore,
          state.token,
          clientEnv);
    }
  }

  /**
   * Adds the metadata of {@link InputDiscoveryState#discoveredInputs} that isn't known yet to the
   * state.
   *
   * <p>Before the action is executed, the metadata is added to {@link
   * InputDiscoveryState#inputArtifactData} so that the action can access it. Afterwards, it is
   * added to {@link InputDiscoveryState#lateDiscoveredInputArtifactData} instead: the action file
   * system reads {@code inputArtifactData} and outlives the action itself, but {@link
   * ActionInputMap} is not thread-safe, so mutating it at that point would race with those reads.
   */
  private void addDiscoveredInputs(
      InputDiscoveryState state, Environment env, Action actionForError, boolean afterExecution)
      throws InterruptedException, ActionExecutionException {
    // TODO(janakr): This code's assumptions are wrong in the face of Starlark actions with unused
    //  inputs, since ActionExecutionExceptions can come through here and should be aggregated. Fix.

    // Filter down to unknown discovered inputs eagerly instead of using a lazy Iterables#filter to
    // reduce iteration cost.
    List<Artifact> unknownDiscoveredInputs = new ArrayList<>();
    for (Artifact input : state.discoveredInputs.toList()) {
      if (state.getKnownDiscoveredInputMetadata(input) == null) {
        unknownDiscoveredInputs.add(input);
      }
    }

    if (unknownDiscoveredInputs.isEmpty()) {
      return;
    }

    ActionInputMap inputData =
        afterExecution
            ? state.getOrCreateLateDiscoveredInputArtifactData(unknownDiscoveredInputs.size())
            : state.inputArtifactData;

    SkyframeLookupResult nonMandatoryDiscovered =
        env.getValuesAndExceptions(Artifact.keys(unknownDiscoveredInputs));
    for (Artifact input : unknownDiscoveredInputs) {
      SkyValue retrievedMetadata;
      try {
        retrievedMetadata =
            nonMandatoryDiscovered.getOrThrow(Artifact.key(input), SourceArtifactException.class);
      } catch (SourceArtifactException e) {
        if (!input.isSourceArtifact()) {
          throw new IllegalStateException(
              String.format(
                  "Non-source artifact had SourceArtifactException %s %s",
                  input.toDebugString(), actionForError.prettyPrint()),
              e);
        }

        skyframeActionExecutor.printError(e.getMessage(), actionForError);
        // We don't create a specific cause for the artifact as we do in #handleMissingFile because
        // it likely has no label, so we'd have to use the Action's label anyway. Just use the
        // default ActionFailed event constructed by ActionExecutionException.
        String message = "discovered input file does not exist";
        DetailedExitCode code = createDetailedExitCodeForMissingDiscoveredInput(message);
        throw new ActionExecutionException(message, actionForError, false, code);
      }
      if (retrievedMetadata == null) {
        checkState(
            env.valuesMissing(),
            "%s had no metadata but all values were present for %s",
            input,
            actionForError);
        continue;
      }
      if (retrievedMetadata instanceof MissingArtifactValue) {
        retrievedMetadata = FileArtifactValue.MISSING_FILE_MARKER;
      }
      ActionInputMapHelper.addToMap(
          inputData, input, retrievedMetadata, MetadataConsumerForMetrics.NO_OP);
    }
  }

  private static class CheckInputResults {
    /** Metadata about Artifacts consumed by this Action. */
    private final ActionInputMap actionInputMap;

    CheckInputResults(ActionInputMap actionInputMap) {
      this.actionInputMap = actionInputMap;
    }
  }

  private static Predicate<Artifact> makeMandatoryInputPredicate(Action action) {
    if (!action.discoversInputs()) {
      return Predicates.alwaysTrue();
    }

    return new Predicate<>() {
      // Lazily flatten the NestedSet in case the predicate is never needed. It's only used in the
      // exceptional case of a missing artifact.
      private ImmutableSet<Artifact> mandatoryInputs = null;
      private ImmutableSet<Artifact> schedulingDependencies = null;

      @Override
      public boolean test(Artifact input) {
        if (!input.isSourceArtifact()) {
          return true;
        }
        if (mandatoryInputs == null) {
          mandatoryInputs = action.getMandatoryInputs().toSet();
        }

        if (mandatoryInputs.contains(input)) {
          return true;
        }

        if (schedulingDependencies == null) {
          schedulingDependencies = action.getSchedulingDependencies().toSet();
        }

        if (schedulingDependencies.contains(input)) {
          return true;
        }

        return false;
      }
    };
  }

  /**
   * Declares a dependency on all known inputs of the action. Throws an exception if any are known
   * to be missing.
   *
   * <p>Returns {@code null} if {@link Environment#valuesMissing} is true and no inputs result in
   * {@link ActionExecutionException}s.
   */
  @Nullable
  private CheckInputResults checkInputs(
      Environment env,
      Action action,
      SkyframeLookupResult inputDepsResult,
      NestedSet<Artifact> allInputs,
      ImmutableSet<SkyKey> inputDepKeys)
      throws ActionExecutionException, InterruptedException, UndoneInputsException {
    Predicate<Artifact> isMandatoryInput = makeMandatoryInputPredicate(action);

    ActionExecutionFunctionExceptionHandler actionExecutionFunctionExceptionHandler =
        new ActionExecutionFunctionExceptionHandler(
            Suppliers.memoize(
                () -> {
                  ImmutableSet<Artifact> allInputsSet =
                      ImmutableSet.<Artifact>builder()
                          .addAll(allInputs.toList())
                          .addAll(action.getSchedulingDependencies().toList())
                          .build();
                  SetMultimap<SkyKey, Artifact> skyKeyToArtifactSet =
                      MultimapBuilder.hashKeys().hashSetValues().build();
                  allInputsSet.forEach(
                      input -> {
                        SkyKey key = Artifact.key(input);
                        if (key != input) {
                          skyKeyToArtifactSet.put(key, input);
                        }
                      });
                  return skyKeyToArtifactSet;
                }),
            inputDepsResult,
            action,
            isMandatoryInput,
            inputDepKeys);
    boolean hasMissingInputs =
        actionExecutionFunctionExceptionHandler.accumulateAndMaybeThrowExceptions();

    if (env.valuesMissing()) {
      return null;
    }

    ImmutableList<Artifact> allInputsList = allInputs.toList();

    // When there are no missing values or there was an error, we can start checking individual
    // files. We don't bother to optimize the error-ful case since it's rare.
    ActionInputMap inputArtifactData = new ActionInputMap(allInputsList.size());
    List<Artifact> undoneInputs = new ArrayList<>(0);

    for (Artifact input : allInputsList) {
      SkyValue value =
          getAndCheckInputSkyValue(
              env,
              action,
              input,
              inputDepKeys,
              isMandatoryInput,
              actionExecutionFunctionExceptionHandler);

      if (value != null) {
        ActionInputMapHelper.addToMap(
            inputArtifactData, input, value, MetadataConsumerForMetrics.NO_OP);
      } else if (!hasMissingInputs && input.hasKnownGeneratingAction()) {
        // Derived inputs are mandatory, but we did not detect any missing inputs. This is only
        // possible for indirect inputs (beneath an ArtifactNestedSetKey) when, between the time the
        // associated direct dependency ArtifactNestedSetKey completes successfully and the call to
        // lookupInput, the input's key was rewound and completed with an error.
        undoneInputs.add(input);
      }
    }

    if (!undoneInputs.isEmpty()) {
      throw new UndoneInputsException(ImmutableSet.copyOf(undoneInputs), inputDepKeys);
    }

    // If there were no errors, we don't go through the scheduling dependencies because the only
    // reason to do so is to find and report missing input source files.
    if (hasMissingInputs) {
      // We unwrap the nested set like in getInputDepKeys(); apparently, if we don't do this, it's
      // a significant memory use hit due to the memoized graph traversal in NestedSet. This only
      // matters when a build encounters a missing source file which then gets resolved in a
      // subsequent build without re-analysis (and thus the memo fields in NestedSet survive)
      CompactHashSet<Artifact> seen = CompactHashSet.create();
      for (Artifact input : action.getSchedulingDependencies().getLeaves()) {
        Verify.verify(seen.add(input));
        getAndCheckInputSkyValue(
            env,
            action,
            input,
            inputDepKeys,
            isMandatoryInput,
            actionExecutionFunctionExceptionHandler);
      }

      for (NestedSet<Artifact> nonLeaf : action.getSchedulingDependencies().getNonLeaves()) {
        for (Artifact input : nonLeaf.toList()) {
          if (seen.add(input)) {
            getAndCheckInputSkyValue(
                env,
                action,
                input,
                inputDepKeys,
                isMandatoryInput,
                actionExecutionFunctionExceptionHandler);
          }
        }
      }
    }

    // After accumulating the inputs, we might find some mandatory artifact with
    // SourceFileInErrorArtifactValue.
    actionExecutionFunctionExceptionHandler.maybeThrowException();

    return new CheckInputResults(inputArtifactData);
  }

  @CanIgnoreReturnValue
  @Nullable
  private SkyValue getAndCheckInputSkyValue(
      Environment env,
      Action action,
      Artifact input,
      ImmutableSet<SkyKey> inputDepKeys,
      Predicate<Artifact> isMandatoryInput,
      @Nullable ActionExecutionFunctionExceptionHandler actionExecutionFunctionExceptionHandler)
      throws InterruptedException, ActionExecutionException {
    SkyValue value = lookupInput(input, inputDepKeys, env);
    switch (value) {
      case ActionExecutionValue actionExecutionValue -> {
        if (input.isChildOfDeclaredDirectory()) {
          TreeArtifactValue tree = actionExecutionValue.getTreeArtifactValue(input.getParent());
          if (tree != null && !tree.getChildValues().containsKey(input)) {
            String errorMessage =
                String.format(
                    "Nondeterministic output tree artifact detected: a previous execution produced"
                        + " child %s in tree %s (generated by %s), but a subsequent execution did"
                        + " not",
                    input.getParentRelativePath(),
                    input.getParent().getExecPathString(),
                    input.getParent().getArtifactOwner().getLabel());
            DetailedExitCode detailedExitCode =
                DetailedExitCode.of(
                    FailureDetail.newBuilder()
                        .setMessage(errorMessage)
                        .setExecution(
                            Execution.newBuilder().setCode(Code.NONDETERMINISTIC_TREE_ARTIFACT))
                        .build());
            throw new ActionExecutionException(
                errorMessage, action, /* catastrophe= */ false, detailedExitCode);
          }
        }
      }
      case MissingArtifactValue missingArtifactValue -> {
        if (!isMandatoryInput.test(input)) {
          return FileArtifactValue.MISSING_FILE_MARKER;
        }
        checkNotNull(
                actionExecutionFunctionExceptionHandler,
                "Missing artifact should have been caught already %s %s %s",
                input,
                value,
                action)
            .accumulateMissingFileArtifactValue(input, missingArtifactValue);
        return null;
      }
      case null -> {
        checkState(
            !isMandatoryInput.test(input)
                || (input.hasKnownGeneratingAction() && skyframeActionExecutor.rewindingEnabled()),
            "Unexpected undone mandatory input: %s",
            input);
        return null;
      }
      default -> {}
    }
    return value;
  }

  /**
   * Looks up the value for an input without adding additional Skyframe dependencies.
   *
   * <p>If the input's {@link Artifact#key} is already a direct dependency, looks up its value in
   * the {@link Environment}. Otherwise, the input is assumed to be beneath an already-requested
   * {@link ArtifactNestedSetKey}, and {@link
   * MemoizingEvaluator#getExistingEntryAtCurrentlyEvaluatingVersion} is used.
   */
  @Nullable
  private SkyValue lookupInput(Artifact input, ImmutableSet<SkyKey> inputDepKeys, Environment env)
      throws InterruptedException {
    SkyKey key = Artifact.key(input);
    if (inputDepKeys.contains(key)) {
      return env.getLookupHandleForPreviouslyRequestedDeps().get(key);
    }
    NodeEntry entry = evaluator.get().getExistingEntryAtCurrentlyEvaluatingVersion(key);
    if (entry == null) {
      return null;
    }
    // Use toValue() so that in case the input's generating action was rewound, we still get some
    // value. It might end up being a lost input when we execute the consuming action, but it may be
    // available if its generating action was rewound due to losing a different output. In the rare
    // case that rewinding completed with an error, this will return null.
    return entry.toValue();
  }

  static LabelCause createLabelCause(
      Artifact input,
      DetailedExitCode detailedExitCode,
      Label labelInCaseOfBug,
      BugReporter bugReporter) {
    if (input.getOwner() == null && !input.isSourceArtifact()) {
      bugReporter.sendBugReport(
          new IllegalStateException(
              String.format(
                  "Mandatory artifact %s with exit code %s should have owner (%s)",
                  input, detailedExitCode, labelInCaseOfBug)));
    }
    return createLabelCauseNullOwnerOk(input, detailedExitCode, labelInCaseOfBug, bugReporter);
  }

  private static LabelCause createLabelCauseNullOwnerOk(
      Artifact input,
      DetailedExitCode detailedExitCode,
      Label actionLabel,
      BugReporter bugReporter) {
    if (!input.isSourceArtifact()) {
      bugReporter.logUnexpected(
          "Unexpected exit code %s for generated artifact %s (%s)",
          detailedExitCode, input, actionLabel);
    }
    return new LabelCause(
        MoreObjects.firstNonNull(input.getOwner(), actionLabel), detailedExitCode);
  }

  /**
   * State to save work across restarts of ActionExecutionFunction due to missing values in the
   * graph for actions that discover inputs. There are three places where we save work, all for
   * actions that discover inputs:
   *
   * <ol>
   *   <li>If not all known input metadata (coming from Action#getInputs) is available yet, then the
   *       calculated set of inputs (including the inputs resolved from the action cache) is saved.
   *   <li>If not all discovered inputs' metadata is available yet, then the known input metadata
   *       together with the set of discovered inputs is saved, as well as the Token used to
   *       identify this action to the action cache.
   *   <li>If, after execution, new inputs are discovered whose metadata is not yet available, then
   *       the same data as in the previous case is saved, along with the actual result of
   *       execution.
   * </ol>
   */
  static class InputDiscoveryState implements SerializableSkyKeyComputeState {
    AllInputs allInputs;

    /** Mutable map containing metadata for known artifacts. */
    ActionInputMap inputArtifactData = null;

    /** A thin wrapper around ActionInputMap for Fileset-related caching. */
    ActionInputMetadataProvider actionInputMetadataProvider = null;

    /** An input metadata provider that does Skyframe lookups. */
    SkyframeInputMetadataProvider skyframeInputMetadataProvider = null;

    /**
     * The input metadata provider that knows everything required to look up action inputs. It
     * consists of these parts:
     *
     * <ul>
     *   <li>The set of direct action inputs ({@link #inputArtifactData})
     *   <li>Skyframe lookups for generated artifacts that are not direct inputs
     *   <li>File system lookups for source artifacts that are not direct inputs
     * </ul>
     *
     * The latter two exist to support input discovery, when an action may well read files that are
     * not direct inputs. The metadata is actually in Skyframe so we could conceivably create the
     * equivalent of an {@link ActionInputMap} with scheduling dependencies and then these two would
     * not be needed. However, it would incur a huge performance hit because the most significant
     * use of input discovery is C++ include scanning, where the vast majority of scheduling
     * dependencies are not actually accessed.
     */
    DelegatingPairInputMetadataProvider compositeInputMetadataProvider = null;

    /**
     * Metadata for inputs that were only discovered after the action was executed.
     *
     * <p>Deliberately not part of {@link #inputArtifactData}: that map is read by the action file
     * system, which outlives the action itself and is read asynchronously. {@link ActionInputMap}
     * is not thread-safe, so mutating it concurrently corrupts it for the reader.
     */
    @Nullable private ActionInputMap lateDiscoveredInputArtifactData = null;

    @Nullable private InputMetadataProvider lateDiscoveredInputMetadataProvider = null;

    Token token = null;
    NestedSet<Artifact> discoveredInputs = null;
    FileSystem actionFileSystem = null;
    boolean preparedInputDiscovery = false;
    boolean actionInputCollectedEventSent = false;

    boolean checkedForConsumedArtifactRegistration = false;

    @Nullable // Initialized lazily
    private RetrievalContext retrievalContext = null;

    boolean hasCollectedInputs() {
      return allInputs != null;
    }

    boolean hasArtifactData() {
      return inputArtifactData != null;
    }

    /**
     * Returns the metadata already known for a discovered input, or null if it hasn't been looked
     * up yet.
     */
    @Nullable
    FileArtifactValue getKnownDiscoveredInputMetadata(Artifact input) {
      FileArtifactValue metadata = inputArtifactData.getInputMetadata(input);
      if (metadata != null || lateDiscoveredInputArtifactData == null) {
        return metadata;
      }
      return lateDiscoveredInputArtifactData.getInputMetadata(input);
    }

    ActionInputMap getOrCreateLateDiscoveredInputArtifactData(int sizeHint) {
      if (lateDiscoveredInputArtifactData == null) {
        lateDiscoveredInputArtifactData = new ActionInputMap(sizeHint);
        lateDiscoveredInputMetadataProvider =
            new ActionInputMetadataProvider(lateDiscoveredInputArtifactData);
      }
      return lateDiscoveredInputArtifactData;
    }

    /**
     * Returns a provider that also covers inputs discovered after the action was executed, which
     * are kept out of {@link #inputArtifactData}.
     */
    InputMetadataProvider inputMetadataProviderIncludingLateDiscoveredInputs(
        InputMetadataProvider inputMetadataProvider) {
      return lateDiscoveredInputMetadataProvider == null
          ? inputMetadataProvider
          : new DelegatingPairInputMetadataProvider(
              lateDiscoveredInputMetadataProvider, inputMetadataProvider);
    }

    boolean hasCheckedActionCache() {
      // If token is null because there was an action cache hit, this method is never called again
      // because we return immediately.
      return token != null;
    }

    @Override
    public RetrievalContext getRetrievalContext() {
      if (retrievalContext == null) {
        retrievalContext = new RetrievalContext();
      }

      return retrievalContext;
    }

    @Override
    public String toString() {
      return MoreObjects.toStringHelper(this)
          .add("token", token)
          .add("allInputs", allInputs)
          .add("inputArtifactData", inputArtifactData)
          .add("discoveredInputs", discoveredInputs)
          .toString();
    }
  }

  /**
   * Used to declare all the exception types that can be wrapped in the exception thrown by {@link
   * ActionExecutionFunction#compute}.
   */
  static final class ActionExecutionFunctionException extends SkyFunctionException {

    private final ActionExecutionException actionException;

    ActionExecutionFunctionException(ActionExecutionException e) {
      // We conservatively assume that the error is transient. We don't have enough information to
      // distinguish non-transient errors (e.g. compilation error from a deterministic compiler)
      // from transient ones (e.g. IO error).
      // TODO(bazel-team): Have ActionExecutionExceptions declare their transience.
      super(e, Transience.TRANSIENT);
      this.actionException = e;
    }

    @Override
    public boolean isCatastrophic() {
      return actionException.isCatastrophe();
    }
  }

  /**
   * Thrown when all direct dependencies are available but {@link #lookupInput} returns {@code null}
   * for one or more generated inputs.
   *
   * <p>This is only possible for indirect inputs (beneath an {@link ArtifactNestedSetKey}) when,
   * between the time the associated direct dependency {@link ArtifactNestedSetKey} is observed to
   * be done and the call to {@link #lookupInput}, the input's {@link Artifact#key} was rewound and
   * completed with an error.
   */
  private static final class UndoneInputsException extends Exception {
    private final ImmutableSet<Artifact> undoneInputs;
    private final ImmutableSet<SkyKey> inputDepKeys;

    UndoneInputsException(ImmutableSet<Artifact> undoneInputs, ImmutableSet<SkyKey> inputDepKeys) {
      this.undoneInputs = undoneInputs;
      this.inputDepKeys = inputDepKeys;
    }
  }

  /** Helper subclass for the error-handling logic for {@link #checkInputs}. */
  private final class ActionExecutionFunctionExceptionHandler {
    private final Supplier<SetMultimap<SkyKey, Artifact>> skyKeyToDerivedArtifactSetForExceptions;
    private final SkyframeLookupResult inputDepsResult;
    private final Action action;
    private final Predicate<Artifact> isMandatoryInput;
    private final ImmutableSet<SkyKey> inputDepKeys;
    private final List<LabelCause> missingArtifactCauses = Lists.newArrayListWithCapacity(0);
    private final List<NestedSet<Cause>> transitiveCauses = Lists.newArrayListWithCapacity(0);
    private ActionExecutionException worstActionExecutionException;

    ActionExecutionFunctionExceptionHandler(
        Supplier<SetMultimap<SkyKey, Artifact>> skyKeyToDerivedArtifactSetForExceptions,
        SkyframeLookupResult inputDepsResult,
        Action action,
        Predicate<Artifact> isMandatoryInput,
        ImmutableSet<SkyKey> inputDepKeys) {
      this.skyKeyToDerivedArtifactSetForExceptions = skyKeyToDerivedArtifactSetForExceptions;
      this.inputDepsResult = inputDepsResult;
      this.action = action;
      this.isMandatoryInput = isMandatoryInput;
      this.inputDepKeys = inputDepKeys;
    }

    /**
     * Goes through the list of evaluated SkyKeys and handles any exception that arises, taking into
     * account whether the corresponding artifact(s) is a mandatory input.
     *
     * <p>Also updates ArtifactNestedSetFunction#skyKeyToSkyValue if an Artifact's value is
     * non-null.
     *
     * @throws ActionExecutionException if the eval of any mandatory artifact threw an exception
     * @return true if there is at least one input artifact that is missing
     */
    boolean accumulateAndMaybeThrowExceptions() throws ActionExecutionException {
      boolean someInputsMissing = false;
      for (SkyKey key : inputDepKeys) {
        try {
          SkyValue value =
              inputDepsResult.getOrThrow(
                  key,
                  SourceArtifactException.class,
                  ActionExecutionException.class,
                  ArtifactNestedSetEvalException.class);
          if (value == null) {
            continue;
          }
          if (key instanceof ArtifactNestedSetKey) {
            if (value == ArtifactNestedSetValue.SOME_MISSING) {
              someInputsMissing = true;
            }
            continue;
          }

          if (value instanceof MissingArtifactValue) {
            someInputsMissing = true;
          }
        } catch (SourceArtifactException e) {
          handleSourceArtifactExceptionFromSkykey(key, e);
        } catch (ActionExecutionException e) {
          handleActionExecutionExceptionFromSkykey(key, e);
        } catch (ArtifactNestedSetEvalException e) {
          for (Pair<SkyKey, Exception> skyKeyAndException : e.getNestedExceptions().toList()) {
            SkyKey skyKey = skyKeyAndException.getFirst();
            Exception inputException = skyKeyAndException.getSecond();
            checkState(
                inputException instanceof SourceArtifactException
                    || inputException instanceof ActionExecutionException,
                "Unexpected exception type: %s, key: %s",
                inputException,
                skyKey);
            if (inputException instanceof SourceArtifactException) {
              handleSourceArtifactExceptionFromSkykey(
                  skyKey, (SourceArtifactException) inputException);
              continue;
            }
            handleActionExecutionExceptionFromSkykey(
                skyKey, (ActionExecutionException) inputException);
          }
        }
      }
      maybeThrowException();
      return someInputsMissing;
    }

    private void handleActionExecutionExceptionFromSkykey(SkyKey key, ActionExecutionException e) {
      if (key instanceof Artifact artifact) {
        handleActionExecutionExceptionPerArtifact(artifact, e);
        return;
      }
      Set<Artifact> associatedInputs = skyKeyToDerivedArtifactSetForExceptions.get().get(key);
      if (associatedInputs.isEmpty()) {
        // This can happen if an action prunes its inputs, e.g. the way StarlarkAction implements
        // unused_inputs_list. An input may no longer be present in getInputs(), but its generating
        // action could still be a Skyframe dependency because Skyframe eagerly adds a dep group to
        // a dirty node if all prior dep groups are clean. If the pruned input is in error, it
        // propagates during error bubbling, and we reach this point.
        // TODO(lberki): Can inputs be immutable instead?
        logger.atWarning().log(
            "While handling errors for %s, encountered error from %s which is not associated with"
                + " any inputs",
            action.prettyPrint(), key);
        if (worstActionExecutionException == null) {
          worstActionExecutionException = e;
          transitiveCauses.add(e.getRootCauses());
        }
      } else {
        for (Artifact input : associatedInputs) {
          handleActionExecutionExceptionPerArtifact(input, e);
        }
      }
    }

    private void handleSourceArtifactExceptionFromSkykey(SkyKey key, SourceArtifactException e) {
      if (!(key instanceof Artifact) || !((Artifact) key).isSourceArtifact()) {
        bugReporter.logUnexpected(
            e, "Unexpected SourceArtifactException for key: %s, %s", key, action.prettyPrint());
        missingArtifactCauses.add(
            new LabelCause(action.getOwner().getLabel(), e.getDetailedExitCode()));
        return;
      }

      if (isMandatoryInput.test((Artifact) key)) {
        missingArtifactCauses.add(
            createLabelCauseNullOwnerOk(
                (Artifact) key,
                e.getDetailedExitCode(),
                action.getOwner().getLabel(),
                bugReporter));
      }
    }

    void accumulateMissingFileArtifactValue(Artifact input, MissingArtifactValue value) {
      missingArtifactCauses.add(
          createLabelCause(
              input, value.getDetailedExitCode(), action.getOwner().getLabel(), bugReporter));
    }

    /**
     * @throws ActionExecutionException if there is any accumulated exception from the inputs.
     */
    void maybeThrowException() throws ActionExecutionException {
      for (LabelCause missingInput : missingArtifactCauses) {
        skyframeActionExecutor.printError(missingInput.getMessage(), action);
      }
      // We need to rethrow the worst exception because it can contain a useful error message.
      if (worstActionExecutionException != null) {
        if (missingArtifactCauses.isEmpty()
            && (checkNotNull(transitiveCauses, action).size() == 1)) {
          // In the case a single action failed, just propagate the exception upward. This avoids
          // having to copy the root causes to the upwards transitive closure.
          throw worstActionExecutionException;
        }
        NestedSetBuilder<Cause> allCauses =
            NestedSetBuilder.<Cause>stableOrder().addAll(missingArtifactCauses);
        transitiveCauses.forEach(allCauses::addTransitive);
        throw new ActionExecutionException(
            worstActionExecutionException.getMessage(),
            worstActionExecutionException.getCause(),
            action,
            allCauses.build(),
            worstActionExecutionException.isCatastrophe(),
            worstActionExecutionException.getDetailedExitCode());
      }

      if (!missingArtifactCauses.isEmpty()) {
        throw throwSourceErrorException(action, missingArtifactCauses);
      }
    }

    private void handleActionExecutionExceptionPerArtifact(
        Artifact input, ActionExecutionException e) {
      if (isMandatoryInput.test(input)) {
        // Prefer a catastrophic exception as the one we propagate.
        if (worstActionExecutionException == null) {
          worstActionExecutionException = e;
        } else {
          worstActionExecutionException =
              ActionExecutionException.SEVERITY_ORDERING.max(worstActionExecutionException, e);
        }
        transitiveCauses.add(e.getRootCauses());
      }
    }
  }

  /**
   * Called when there are no action execution errors (whose reporting hides missing sources), but
   * there was at least one missing/io exception-triggering source artifact. Returns a {@link
   * DetailedExitCode} constructed from {@code sourceArtifactErrorCauses} specific to a single such
   * artifact and an error message suitable as the message to a thrown exception that summarizes the
   * findings.
   */
  static Pair<DetailedExitCode, String> createSourceErrorCodeAndMessage(
      List<? extends Cause> sourceArtifactErrorCauses, Object debugInfo) {
    AtomicBoolean sawSourceArtifactException = new AtomicBoolean();
    AtomicBoolean sawMissingFile = new AtomicBoolean();
    DetailedExitCode prioritizedDetailedExitCode =
        sourceArtifactErrorCauses.stream()
            .map(Cause::getDetailedExitCode)
            .peek(
                code -> {
                  if (code.getFailureDetail() == null) {
                    BugReport.sendBugReport(
                        new NullPointerException(
                            "Code " + code + " had no failure detail for " + debugInfo));
                    return;
                  }
                  if (code.getFailureDetail().hasFilesystem()) {
                    sawSourceArtifactException.set(true);
                    return;
                  }
                  switch (code.getFailureDetail().getExecution().getCode()) {
                    case SOURCE_INPUT_IO_EXCEPTION -> sawSourceArtifactException.set(true);
                    case SOURCE_INPUT_MISSING -> sawMissingFile.set(true);
                    default ->
                        BugReport.sendNonFatalBugReport(
                            new IllegalStateException(
                                "Unexpected error code in " + code + " for " + debugInfo));
                  }
                })
            .max(DetailedExitCodeComparator.INSTANCE)
            .get();
    String errorMessage =
        sourceArtifactErrorCauses.size()
            + " input file(s) "
            + Joiner.on(" or ")
                .skipNulls()
                .join(
                    sawSourceArtifactException.get() ? "are in error" : null,
                    sawMissingFile.get() ? "do not exist" : null);
    return Pair.of(prioritizedDetailedExitCode, errorMessage);
  }

  private ActionExecutionException throwSourceErrorException(
      Action action, List<? extends Cause> sourceArtifactErrorCauses)
      throws ActionExecutionException {
    Pair<DetailedExitCode, String> codeAndMessage =
        createSourceErrorCodeAndMessage(sourceArtifactErrorCauses, action);
    ActionExecutionException ex =
        new ActionExecutionException(
            codeAndMessage.getSecond(),
            action,
            NestedSetBuilder.wrap(Order.STABLE_ORDER, sourceArtifactErrorCauses),
            /* catastrophe= */ false,
            codeAndMessage.getFirst());
    skyframeActionExecutor.printError(ex.getMessage(), action);
    // Don't actually return: throw exception directly so caller can't get it wrong.
    throw ex;
  }

  private static DetailedExitCode createDetailedExitCodeForMissingDiscoveredInput(String message) {
    return DetailedExitCode.of(
        FailureDetail.newBuilder()
            .setMessage(message)
            .setExecution(Execution.newBuilder().setCode(Code.DISCOVERED_INPUT_DOES_NOT_EXIST))
            .build());
  }
}