// 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.actions;

import static com.google.common.collect.ImmutableListMultimap.toImmutableListMultimap;

import com.google.common.base.Functions;
import com.google.common.collect.ImmutableListMultimap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Streams;
import com.google.devtools.build.lib.cmdline.Label;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.EventHandler;
import com.google.devtools.build.lib.packages.AspectDescriptor;
import com.google.devtools.build.lib.server.FailureDetails.Analysis;
import com.google.devtools.build.lib.server.FailureDetails.Analysis.Code;
import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
import com.google.devtools.build.lib.skyframe.SaneAnalysisException;
import com.google.devtools.build.lib.util.DetailedExitCode;
import java.util.Set;
import java.util.stream.Collectors;
import javax.annotation.Nullable;

/** A mutable action graph. Implementations of this interface must be thread-safe. */
public interface MutableActionGraph extends ActionGraph {

  /**
   * Attempts to register the action. If any of the action's outputs already has a generating
   * action, and the two actions are not compatible, then an {@link ActionConflictException} is
   * thrown. The internal data structure may be partially modified when that happens; it is not
   * guaranteed that all potential conflicts are detected, but at least one of them is.
   *
   * <p>For example, take three actions A, B, and C, where A creates outputs a and b, B creates just
   * b, and C creates c and b. There are two potential conflicts in this case, between A and B, and
   * between B and C. Depending on the ordering of calls to this method and the ordering of outputs
   * in the action output lists, either one or two conflicts are detected: if B is registered first,
   * then both conflicts are detected; if either A or C is registered first, then only one conflict
   * is detected.
   */
  void registerAction(ActionAnalysisMetadata action)
      throws ActionConflictException, InterruptedException;

  /** Returns the size of the action graph. */
  int getSize();

  /**
   * This exception is thrown when a conflict between actions is detected. It contains information
   * about the artifact for which the conflict is found, and data about the two conflicting actions
   * and their owners.
   */
  final class ActionConflictException extends Exception implements SaneAnalysisException {

    private final Artifact artifact;

    private static final int MAX_DIFF_ARTIFACTS_TO_REPORT = 5;

    public static ActionConflictException create(
        ActionKeyContext actionKeyContext,
        Artifact artifact,
        ActionAnalysisMetadata previousAction,
        ActionAnalysisMetadata attemptedAction) {
      return new ActionConflictException(
          artifact,
          createDetailedMessage(artifact, actionKeyContext, attemptedAction, previousAction));
    }

    private ActionConflictException(Artifact artifact, String message) {
      super(message);
      this.artifact = artifact;
    }

    public Artifact getArtifact() {
      return artifact;
    }

    private static String createDetailedMessage(
        Artifact artifact,
        ActionKeyContext actionKeyContext,
        ActionAnalysisMetadata a,
        ActionAnalysisMetadata b) {
      return "file '"
          + artifact.prettyPrint()
          + "' is generated by these conflicting actions:\n"
          + debugSuffix(actionKeyContext, a, b);
    }

    public void reportTo(EventHandler eventListener) {
      eventListener.handle(Event.error(this.getMessage()));
    }

    @Override
    public DetailedExitCode getDetailedExitCode() {
      return DetailedExitCode.of(
          FailureDetail.newBuilder()
              .setMessage(getMessage())
              .setAnalysis(Analysis.newBuilder().setCode(Code.ACTION_CONFLICT))
              .build());
    }

    private static void addStringDetail(
        StringBuilder sb, String key, String valueA, String valueB) {
      valueA = valueA != null ? valueA : "(null)";
      valueB = valueB != null ? valueB : "(null)";

      sb.append(key).append(": ").append(valueA);
      if (!valueA.equals(valueB)) {
        sb.append(", ").append(valueB);
      }
      sb.append("\n");
    }

    private static void addListDetail(
        StringBuilder sb, String key, Iterable<Artifact> valueA, Iterable<Artifact> valueB) {
      Set<Artifact> diffA = differenceWithoutOwner(valueA, valueB);
      Set<Artifact> diffB = differenceWithoutOwner(valueB, valueA);

      sb.append(key).append(": ");
      if (diffA.isEmpty() && diffB.isEmpty()) {
        sb.append("are equal\n");
      } else {
        if (!diffA.isEmpty()) {
          sb.append(
              "Attempted action contains artifacts not in previous action (first "
                  + MAX_DIFF_ARTIFACTS_TO_REPORT
                  + "): \n");
          prettyPrintArtifactDiffs(sb, diffA);
        }

        if (!diffB.isEmpty()) {
          sb.append(
              "Previous action contains artifacts not in attempted action (first "
                  + MAX_DIFF_ARTIFACTS_TO_REPORT
                  + "): \n");
          prettyPrintArtifactDiffs(sb, diffB);
        }
      }
    }

    /** Returns items in {@code valueA} that are not in {@code valueB}, ignoring the owner. */
    private static Set<Artifact> differenceWithoutOwner(
        Iterable<Artifact> valueA, Iterable<Artifact> valueB) {
      ImmutableSet.Builder<Artifact> diff = new ImmutableSet.Builder<>();

      // Group valueB by exec path for easier checks.
      ImmutableListMultimap<String, Artifact> mapB =
          Streams.stream(valueB)
              .collect(toImmutableListMultimap(Artifact::getExecPathString, Functions.identity()));
      for (Artifact a : valueA) {
        boolean found = false;
        for (Artifact b : mapB.get(a.getExecPathString())) {
          if (a.equalsWithoutOwner(b)) {
            found = true;
            break;
          }
        }
        if (!found) {
          diff.add(a);
        }
      }

      return diff.build();
    }

    /** Pretty print action diffs (at most {@code MAX_DIFF_ARTIFACTS_TO_REPORT} lines). */
    private static void prettyPrintArtifactDiffs(StringBuilder sb, Set<Artifact> diff) {
      for (Artifact artifact : Iterables.limit(diff, MAX_DIFF_ARTIFACTS_TO_REPORT)) {
        sb.append('\t').append(artifact.prettyPrint()).append('\n');
      }
    }

    // See also Actions.canBeShared()
    private static String debugSuffix(
        ActionKeyContext actionKeyContext, ActionAnalysisMetadata a, ActionAnalysisMetadata b) {
      // Note: the error message reveals to users the names of intermediate files that are not
      // documented in the BUILD language.  This error-reporting logic is rather elaborate but it
      // does help to diagnose some tricky situations.
      StringBuilder sb = new StringBuilder();
      ActionOwner aOwner = a.getOwner();
      ActionOwner bOwner = b.getOwner();
      boolean aNull = aOwner == null;
      boolean bNull = bOwner == null;

      addStringDetail(
          sb,
          "Label",
          aNull ? null : Label.print(aOwner.getLabel()),
          bNull ? null : Label.print(bOwner.getLabel()));
      if ((!aNull && !aOwner.getAspectDescriptors().isEmpty())
          || (!bNull && !bOwner.getAspectDescriptors().isEmpty())) {
        addStringDetail(sb, "Aspects", aspectDescriptor(aOwner), aspectDescriptor(bOwner));
      }
      addStringDetail(
          sb,
          "RuleClass",
          aNull ? null : aOwner.getTargetKind(),
          bNull ? null : bOwner.getTargetKind());
      addStringDetail(
          sb,
          "JavaActionClass",
          aNull ? null : a.getClass().toString(),
          bNull ? null : b.getClass().toString());
      addStringDetail(
          sb,
          "Configuration",
          aNull ? null : aOwner.getConfigurationChecksum(),
          bNull ? null : bOwner.getConfigurationChecksum());
      addStringDetail(sb, "Mnemonic", a.getMnemonic(), b.getMnemonic());
      try {
        addStringDetail(
            sb,
            "Action key",
            a.getKey(actionKeyContext, /*artifactExpander=*/ null),
            b.getKey(actionKeyContext, /*artifactExpander=*/ null));
      } catch (InterruptedException e) {
        // Only for debugging - skip the key and carry on.
        addStringDetail(sb, "Action key", "<elided due to interrupt>", "<elided due to interrupt>");
        Thread.currentThread().interrupt();
      }

      if ((a instanceof ActionExecutionMetadata) && (b instanceof ActionExecutionMetadata)) {
        addStringDetail(
            sb,
            "Progress message",
            ((ActionExecutionMetadata) a).getProgressMessage(),
            ((ActionExecutionMetadata) b).getProgressMessage());
        addStringDetail(
            sb,
            "Action describeKey",
            ((ActionExecutionMetadata) a).describeKey(),
            ((ActionExecutionMetadata) b).describeKey());
      }

      Artifact aPrimaryInput = a.getPrimaryInput();
      Artifact bPrimaryInput = b.getPrimaryInput();
      addStringDetail(
          sb,
          "PrimaryInput",
          aPrimaryInput == null ? null : aPrimaryInput.toString(),
          bPrimaryInput == null ? null : bPrimaryInput.toString());
      addStringDetail(
          sb, "PrimaryOutput", a.getPrimaryOutput().toString(), b.getPrimaryOutput().toString());

      // Only add list details if the primary input of A matches the input of B. Otherwise
      // the above information is enough and list diff detail is not needed.
      if ((aPrimaryInput == null && bPrimaryInput == null)
          || (aPrimaryInput != null
              && bPrimaryInput != null
              && aPrimaryInput.toString().equals(bPrimaryInput.toString()))) {
        Artifact aPrimaryOutput = a.getPrimaryOutput();
        Artifact bPrimaryOutput = b.getPrimaryOutput();
        if (!aPrimaryOutput.equalsWithoutOwner(bPrimaryOutput)) {
          sb.append("Primary outputs are different: ")
              .append(System.identityHashCode(aPrimaryOutput))
              .append(", ")
              .append(System.identityHashCode(bPrimaryOutput))
              .append('\n');
        }
        ArtifactOwner aArtifactOwner = aPrimaryOutput.getArtifactOwner();
        ArtifactOwner bArtifactOwner = bPrimaryOutput.getArtifactOwner();
        addStringDetail(
            sb, "Owner information", aArtifactOwner.toString(), bArtifactOwner.toString());
        addListDetail(
            sb,
            "MandatoryInputs",
            a.getMandatoryInputs().toList(),
            b.getMandatoryInputs().toList());
        addListDetail(sb, "Outputs", a.getOutputs(), b.getOutputs());
      }

      return sb.toString();
    }

    @Nullable
    private static String aspectDescriptor(ActionOwner owner) {
      return owner == null
          ? null
          : owner.getAspectDescriptors().stream()
              .map(AspectDescriptor::getDescription)
              .collect(Collectors.joining(",", "[", "]"));
    }
  }
}