// Copyright (C) 2012 The Android Open Source Project
//
// 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.gerrit.server.git;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.ImmutableSet.toImmutableSet;
import static com.google.common.collect.ImmutableSortedSet.toImmutableSortedSet;
import static com.google.gerrit.git.ObjectIds.abbreviateName;
import static java.nio.charset.StandardCharsets.UTF_8;
import static java.util.Comparator.naturalOrder;
import static java.util.stream.Collectors.joining;

import com.google.auto.factory.AutoFactory;
import com.google.auto.factory.Provided;
import com.google.common.base.Strings;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSortedSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import com.google.common.flogger.FluentLogger;
import com.google.gerrit.common.FooterConstants;
import com.google.gerrit.common.Nullable;
import com.google.gerrit.entities.Account;
import com.google.gerrit.entities.BooleanProjectConfig;
import com.google.gerrit.entities.BranchNameKey;
import com.google.gerrit.entities.Change;
import com.google.gerrit.entities.LabelId;
import com.google.gerrit.entities.LabelType;
import com.google.gerrit.entities.PatchSet;
import com.google.gerrit.entities.PatchSetApproval;
import com.google.gerrit.exceptions.InvalidMergeStrategyException;
import com.google.gerrit.exceptions.MergeWithConflictsNotSupportedException;
import com.google.gerrit.exceptions.StorageException;
import com.google.gerrit.extensions.registration.DynamicItem;
import com.google.gerrit.extensions.restapi.BadRequestException;
import com.google.gerrit.extensions.restapi.MergeConflictException;
import com.google.gerrit.extensions.restapi.MethodNotAllowedException;
import com.google.gerrit.extensions.restapi.ResourceNotFoundException;
import com.google.gerrit.server.ChangeUtil;
import com.google.gerrit.server.IdentifiedUser;
import com.google.gerrit.server.approval.ApprovalsUtil;
import com.google.gerrit.server.config.GerritServerConfig;
import com.google.gerrit.server.config.UrlFormatter;
import com.google.gerrit.server.git.CodeReviewCommit.CodeReviewRevWalk;
import com.google.gerrit.server.notedb.ChangeNotes;
import com.google.gerrit.server.project.ProjectState;
import com.google.gerrit.server.submit.ChangeAlreadyMergedException;
import com.google.gerrit.server.submit.CommitMergeStatus;
import com.google.gerrit.server.submit.MergeIdenticalTreeException;
import com.google.gerrit.server.submit.MergeSorter;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;
import org.eclipse.jgit.diff.Sequence;
import org.eclipse.jgit.dircache.DirCache;
import org.eclipse.jgit.dircache.DirCacheBuilder;
import org.eclipse.jgit.dircache.DirCacheEntry;
import org.eclipse.jgit.errors.AmbiguousObjectException;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.LargeObjectException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.NoMergeBaseException;
import org.eclipse.jgit.errors.NoMergeBaseException.MergeBaseFailureReason;
import org.eclipse.jgit.errors.RevisionSyntaxException;
import org.eclipse.jgit.lib.CommitBuilder;
import org.eclipse.jgit.lib.Config;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectInserter;
import org.eclipse.jgit.lib.PersonIdent;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.merge.MergeFormatter;
import org.eclipse.jgit.merge.MergeResult;
import org.eclipse.jgit.merge.MergeStrategy;
import org.eclipse.jgit.merge.Merger;
import org.eclipse.jgit.merge.ResolveMerger;
import org.eclipse.jgit.merge.ThreeWayMergeStrategy;
import org.eclipse.jgit.merge.ThreeWayMerger;
import org.eclipse.jgit.revwalk.FooterKey;
import org.eclipse.jgit.revwalk.FooterLine;
import org.eclipse.jgit.revwalk.RevCommit;
import org.eclipse.jgit.revwalk.RevFlag;
import org.eclipse.jgit.revwalk.RevSort;
import org.eclipse.jgit.revwalk.RevWalk;
import org.eclipse.jgit.util.TemporaryBuffer;

/**
 * Utility methods used during the merge process.
 *
 * <p><strong>Note:</strong> Unless otherwise specified, the methods in this class <strong>do
 * not</strong> flush {@link ObjectInserter}s. Callers that want to read back objects before
 * flushing should use {@link ObjectInserter#newReader()}. This is already the default behavior of
 * {@code BatchUpdate}.
 */
@AutoFactory
public class MergeUtil {
  private static final FluentLogger logger = FluentLogger.forEnclosingClass();

  /**
   * Length of abbreviated hex SHA-1s in merged filenames.
   *
   * <p>This is a constant so output is stable over time even if the SHA-1 prefix becomes ambiguous.
   */
  private static final int NAME_ABBREV_LEN = 6;

  private static final String R_HEADS_MASTER = Constants.R_HEADS + Constants.MASTER;

  public static boolean useRecursiveMerge(Config cfg) {
    return cfg.getBoolean("core", null, "useRecursiveMerge", true);
  }

  public static ThreeWayMergeStrategy getMergeStrategy(Config cfg) {
    return useRecursiveMerge(cfg) ? MergeStrategy.RECURSIVE : MergeStrategy.RESOLVE;
  }

  private final IdentifiedUser.GenericFactory identifiedUserFactory;
  private final DynamicItem<UrlFormatter> urlFormatter;
  private final ApprovalsUtil approvalsUtil;
  private final ProjectState project;
  private final boolean useContentMerge;
  private final boolean useRecursiveMerge;
  private final PluggableCommitMessageGenerator commitMessageGenerator;
  private final ChangeUtil changeUtil;

  MergeUtil(
      @Provided @GerritServerConfig Config serverConfig,
      @Provided IdentifiedUser.GenericFactory identifiedUserFactory,
      @Provided DynamicItem<UrlFormatter> urlFormatter,
      @Provided ApprovalsUtil approvalsUtil,
      @Provided PluggableCommitMessageGenerator commitMessageGenerator,
      @Provided ChangeUtil changeUtil,
      ProjectState project) {
    this(
        serverConfig,
        identifiedUserFactory,
        urlFormatter,
        approvalsUtil,
        commitMessageGenerator,
        changeUtil,
        project,
        project.is(BooleanProjectConfig.USE_CONTENT_MERGE));
  }

  MergeUtil(
      @Provided @GerritServerConfig Config serverConfig,
      @Provided IdentifiedUser.GenericFactory identifiedUserFactory,
      @Provided DynamicItem<UrlFormatter> urlFormatter,
      @Provided ApprovalsUtil approvalsUtil,
      @Provided PluggableCommitMessageGenerator commitMessageGenerator,
      @Provided ChangeUtil changeUtil,
      ProjectState project,
      boolean useContentMerge) {
    this.identifiedUserFactory = identifiedUserFactory;
    this.urlFormatter = urlFormatter;
    this.approvalsUtil = approvalsUtil;
    this.commitMessageGenerator = commitMessageGenerator;
    this.changeUtil = changeUtil;
    this.project = project;
    this.useContentMerge = useContentMerge;
    this.useRecursiveMerge = useRecursiveMerge(serverConfig);
  }

  public CodeReviewCommit getFirstFastForward(
      CodeReviewCommit mergeTip, RevWalk rw, List<CodeReviewCommit> toMerge) {
    for (Iterator<CodeReviewCommit> i = toMerge.iterator(); i.hasNext(); ) {
      try {
        final CodeReviewCommit n = i.next();
        if (mergeTip == null || rw.isMergedInto(mergeTip, n)) {
          i.remove();
          return n;
        }
      } catch (IOException e) {
        throw new StorageException("Cannot fast-forward test during merge", e);
      }
    }
    return mergeTip;
  }

  public List<CodeReviewCommit> reduceToMinimalMerge(
      MergeSorter mergeSorter, Collection<CodeReviewCommit> toSort) {
    List<CodeReviewCommit> result = new ArrayList<>();
    try {
      result.addAll(mergeSorter.sort(toSort));
    } catch (IOException | StorageException e) {
      throw new StorageException("Branch head sorting failed", e);
    }
    result.sort(CodeReviewCommit.ORDER);
    return result;
  }

  public CodeReviewCommit createCherryPickFromCommit(
      ObjectInserter inserter,
      Config repoConfig,
      RevCommit mergeTip,
      RevCommit originalCommit,
      PersonIdent cherryPickCommitterIdent,
      String commitMsg,
      CodeReviewRevWalk rw,
      int parentIndex,
      boolean ignoreIdenticalTree,
      boolean allowConflicts)
      throws IOException,
          MergeIdenticalTreeException,
          MergeConflictException,
          MethodNotAllowedException,
          InvalidMergeStrategyException {
    return createCherryPickFromCommit(
        inserter,
        repoConfig,
        mergeTip,
        originalCommit,
        cherryPickCommitterIdent,
        commitMsg,
        rw,
        parentIndex,
        ignoreIdenticalTree,
        allowConflicts,
        false);
  }

  public CodeReviewCommit createCherryPickFromCommit(
      ObjectInserter inserter,
      Config repoConfig,
      RevCommit mergeTip,
      RevCommit originalCommit,
      PersonIdent cherryPickCommitterIdent,
      String commitMsg,
      CodeReviewRevWalk rw,
      int parentIndex,
      boolean ignoreIdenticalTree,
      boolean allowConflicts,
      boolean diff3Format)
      throws IOException,
          MergeIdenticalTreeException,
          MergeConflictException,
          MethodNotAllowedException,
          InvalidMergeStrategyException {

    ThreeWayMerger m = newThreeWayMerger(inserter, repoConfig);
    m.setBase(originalCommit.getParent(parentIndex));

    DirCache dc = DirCache.newInCore();
    if (allowConflicts && m instanceof ResolveMerger) {
      // The DirCache must be set on ResolveMerger before calling
      // ResolveMerger#merge(AnyObjectId...) otherwise the entries in DirCache don't get populated.
      ((ResolveMerger) m).setDirCache(dc);
    }

    ObjectId tree;
    ImmutableSet<String> filesWithGitConflicts;
    if (m.merge(mergeTip, originalCommit)) {
      filesWithGitConflicts = null;
      tree = m.getResultTreeId();
      logger.atFine().log(
          "CherryPick treeId=%s (no conflicts, inserter: %s)", tree.name(), m.getObjectInserter());
      if (tree.equals(mergeTip.getTree()) && !ignoreIdenticalTree) {
        throw new MergeIdenticalTreeException("identical tree");
      }
    } else {
      if (!allowConflicts) {
        throw new MergeConflictException(
            String.format(
                "merge conflict while merging commits %s and %s",
                mergeTip.toObjectId(), originalCommit.toObjectId()));
      }

      if (!useContentMerge) {
        // If content merge is disabled we don't have a ResolveMerger and hence cannot merge with
        // conflict markers.
        throw new MethodNotAllowedException(
            "Cherry-pick with allow conflicts requires that content merge is enabled.");
      }

      // For merging with conflict markers we need a ResolveMerger, double-check that we have one.
      checkState(m instanceof ResolveMerger, "allow conflicts is not supported");

      if (m.getResultTreeId() != null) {
        // Merging with conflicts below uses the same DirCache instance that has been used by the
        // Merger to attempt the merge without conflicts.
        //
        // The Merger uses the DirCache to do the updates, and in particular to write the result
        // tree. DirCache caches a single DirCacheTree instance that is used to write the result
        // tree, but it writes the result tree only if there were no conflicts.
        //
        // Merging with conflicts uses the same DirCache instance to write the tree with conflicts
        // that has been used by the Merger. This means if the Merger unexpectedly wrote a result
        // tree although there had been conflicts, then merging with conflicts uses the same
        // DirCacheTree instance to write the tree with conflicts. However DirCacheTree#writeTree
        // writes a tree only once and then that tree is cached. Further invocations of
        // DirCacheTree#writeTree have no effect and return the previously created tree. This means
        // merging with conflicts can only successfully create the tree with conflicts if the Merger
        // didn't write a result tree yet. Hence this is checked here and we log a warning if the
        // result tree was already written.
        logger.atWarning().log(
            "result tree has already been written: %s (merge: %s, conflicts: %s, failed: %s)",
            m,
            m.getResultTreeId().name(),
            ((ResolveMerger) m).getUnmergedPaths(),
            ((ResolveMerger) m).getFailingPaths());
      }

      Map<String, MergeResult<? extends Sequence>> mergeResults =
          ((ResolveMerger) m).getMergeResults();

      filesWithGitConflicts =
          mergeResults.entrySet().stream()
              .filter(e -> e.getValue().containsConflicts())
              .map(Map.Entry::getKey)
              .collect(toImmutableSet());

      tree =
          mergeWithConflicts(
              rw,
              inserter,
              dc,
              "HEAD",
              mergeTip,
              "CHANGE",
              originalCommit,
              mergeResults,
              diff3Format);
      logger.atFine().log(
          "AutoMerge treeId=%s (with conflicts, inserter: %s)", tree.name(), inserter);
    }

    CommitBuilder cherryPickCommit = new CommitBuilder();
    cherryPickCommit.setTreeId(tree);
    cherryPickCommit.setParentId(mergeTip);
    cherryPickCommit.setAuthor(originalCommit.getAuthorIdent());
    cherryPickCommit.setCommitter(cherryPickCommitterIdent);
    cherryPickCommit.setMessage(commitMsg);
    matchAuthorToCommitterDate(project, cherryPickCommit);
    CodeReviewCommit commit = rw.parseCommit(inserter.insert(cherryPickCommit));
    commit.setFilesWithGitConflicts(filesWithGitConflicts);
    logger.atFine().log("CherryPick commitId=%s", commit.name());
    return commit;
  }

  public static ObjectId mergeWithConflicts(
      RevWalk rw,
      ObjectInserter ins,
      DirCache dc,
      String oursName,
      RevCommit ours,
      String theirsName,
      RevCommit theirs,
      Map<String, MergeResult<? extends Sequence>> mergeResults)
      throws IOException {
    return mergeWithConflicts(rw, ins, dc, oursName, ours, theirsName, theirs, mergeResults, false);
  }

  @SuppressWarnings("resource") // TemporaryBuffer requires calling close before reading.
  public static ObjectId mergeWithConflicts(
      RevWalk rw,
      ObjectInserter ins,
      DirCache dc,
      String oursName,
      RevCommit ours,
      String theirsName,
      RevCommit theirs,
      Map<String, MergeResult<? extends Sequence>> mergeResults,
      boolean diff3Format)
      throws IOException {
    rw.parseBody(ours);
    rw.parseBody(theirs);
    String oursMsg = ours.getShortMessage();
    String theirsMsg = theirs.getShortMessage();

    int nameLength = Math.max(oursName.length(), theirsName.length());
    String oursNameFormatted =
        String.format(
            "%-" + nameLength + "s (%s %s)",
            oursName,
            abbreviateName(ours, NAME_ABBREV_LEN),
            oursMsg.substring(0, Math.min(oursMsg.length(), 60)));
    String theirsNameFormatted =
        String.format(
            "%-" + nameLength + "s (%s %s)",
            theirsName,
            abbreviateName(theirs, NAME_ABBREV_LEN),
            theirsMsg.substring(0, Math.min(theirsMsg.length(), 60)));

    MergeFormatter fmt = new MergeFormatter();
    Map<String, ObjectId> resolved = new HashMap<>();
    for (Map.Entry<String, MergeResult<? extends Sequence>> entry : mergeResults.entrySet()) {
      MergeResult<? extends Sequence> p = entry.getValue();
      TemporaryBuffer buf = null;
      try {
        // TODO(dborowitz): Respect inCoreLimit here.
        buf = new TemporaryBuffer.LocalFile(null, 10 * 1024 * 1024);
        if (diff3Format) {
          fmt.formatMergeDiff3(buf, p, "BASE", oursNameFormatted, theirsNameFormatted, UTF_8);
        } else {
          fmt.formatMerge(buf, p, "BASE", oursNameFormatted, theirsNameFormatted, UTF_8);
        }
        buf.close(); // Flush file and close for writes, but leave available for reading.

        try (InputStream in = buf.openInputStream()) {
          resolved.put(entry.getKey(), ins.insert(Constants.OBJ_BLOB, buf.length(), in));
        }
      } finally {
        if (buf != null) {
          buf.destroy();
        }
      }
    }

    DirCacheBuilder builder = dc.builder();
    int cnt = dc.getEntryCount();
    for (int i = 0; i < cnt; ) {
      DirCacheEntry entry = dc.getEntry(i);
      if (entry.getStage() == 0) {
        builder.add(entry);
        i++;
        continue;
      }

      int next = dc.nextEntry(i);
      String path = entry.getPathString();
      DirCacheEntry res = new DirCacheEntry(path);
      if (resolved.containsKey(path)) {
        // For a file with content merge conflict that we produced a result
        // above on, collapse the file down to a single stage 0 with just
        // the blob content, and a randomly selected mode (the lowest stage,
        // which should be the merge base, or ours).
        res.setFileMode(entry.getFileMode());
        res.setObjectId(resolved.get(path));

      } else if (next == i + 1) {
        // If there is exactly one stage present, shouldn't be a conflict...
        res.setFileMode(entry.getFileMode());
        res.setObjectId(entry.getObjectId());

      } else if (next == i + 2) {
        // Two stages suggests a delete/modify conflict. Pick the higher
        // stage as the automatic result.
        entry = dc.getEntry(i + 1);
        res.setFileMode(entry.getFileMode());
        res.setObjectId(entry.getObjectId());

      } else {
        // 3 stage conflict, no resolve above
        // Punt on the 3-stage conflict and show the base, for now.
        res.setFileMode(entry.getFileMode());
        res.setObjectId(entry.getObjectId());
      }
      builder.add(res);
      i = next;
    }
    builder.finish();
    return dc.writeTree(ins);
  }

  public static CodeReviewCommit createMergeCommit(
      ObjectInserter inserter,
      Config repoConfig,
      RevCommit mergeTip,
      RevCommit originalCommit,
      String mergeStrategy,
      boolean allowConflicts,
      PersonIdent committerIdent,
      String commitMsg,
      CodeReviewRevWalk rw)
      throws IOException,
          MergeIdenticalTreeException,
          MergeConflictException,
          InvalidMergeStrategyException {
    return createMergeCommit(
        inserter,
        repoConfig,
        mergeTip,
        originalCommit,
        mergeStrategy,
        allowConflicts,
        committerIdent,
        committerIdent,
        commitMsg,
        rw);
  }

  public static CodeReviewCommit createMergeCommit(
      ObjectInserter inserter,
      Config repoConfig,
      RevCommit mergeTip,
      RevCommit originalCommit,
      String mergeStrategy,
      boolean allowConflicts,
      PersonIdent authorIdent,
      PersonIdent committerIdent,
      String commitMsg,
      CodeReviewRevWalk rw)
      throws IOException,
          MergeIdenticalTreeException,
          MergeConflictException,
          InvalidMergeStrategyException {

    if (!MergeStrategy.THEIRS.getName().equals(mergeStrategy)
        && rw.isMergedInto(originalCommit, mergeTip)) {
      throw new ChangeAlreadyMergedException(
          "'" + originalCommit.getName() + "' has already been merged");
    }

    Merger m = newMerger(inserter, repoConfig, mergeStrategy);

    DirCache dc = DirCache.newInCore();
    if (allowConflicts && m instanceof ResolveMerger) {
      // The DirCache must be set on ResolveMerger before calling
      // ResolveMerger#merge(AnyObjectId...) otherwise the entries in DirCache don't get populated.
      ((ResolveMerger) m).setDirCache(dc);
    }

    ObjectId tree;
    ImmutableSet<String> filesWithGitConflicts;
    if (m.merge(false, mergeTip, originalCommit)) {
      filesWithGitConflicts = null;
      tree = m.getResultTreeId();
    } else {
      List<String> conflicts = ImmutableList.of();
      Map<String, ResolveMerger.MergeFailureReason> failed = ImmutableMap.of();
      if (m instanceof ResolveMerger) {
        conflicts = ((ResolveMerger) m).getUnmergedPaths();
        failed = ((ResolveMerger) m).getFailingPaths();
      }

      if (m.getResultTreeId() != null) {
        // Merging with conflicts below uses the same DirCache instance that has been used by the
        // Merger to attempt the merge without conflicts.
        //
        // The Merger uses the DirCache to do the updates, and in particular to write the result
        // tree. DirCache caches a single DirCacheTree instance that is used to write the result
        // tree, but it writes the result tree only if there were no conflicts.
        //
        // Merging with conflicts uses the same DirCache instance to write the tree with conflicts
        // that has been used by the Merger. This means if the Merger unexpectedly wrote a result
        // tree although there had been conflicts, then merging with conflicts uses the same
        // DirCacheTree instance to write the tree with conflicts. However DirCacheTree#writeTree
        // writes a tree only once and then that tree is cached. Further invocations of
        // DirCacheTree#writeTree have no effect and return the previously created tree. This means
        // merging with conflicts can only successfully create the tree with conflicts if the Merger
        // didn't write a result tree yet. Hence this is checked here and we log a warning if the
        // result tree was already written.
        logger.atWarning().log(
            "result tree has already been written: %s (merge: %s, conflicts: %s, failed: %s)",
            m, m.getResultTreeId().name(), conflicts, failed);
      }

      if (!allowConflicts) {
        throw new MergeConflictException(createConflictMessage(conflicts));
      }

      // For merging with conflict markers we need a ResolveMerger, double-check that we have one.
      if (!(m instanceof ResolveMerger)) {
        throw new MergeWithConflictsNotSupportedException(MergeStrategy.get(mergeStrategy));
      }
      Map<String, MergeResult<? extends Sequence>> mergeResults =
          ((ResolveMerger) m).getMergeResults();

      filesWithGitConflicts =
          mergeResults.entrySet().stream()
              .filter(e -> e.getValue().containsConflicts())
              .map(Map.Entry::getKey)
              .collect(toImmutableSet());

      tree =
          mergeWithConflicts(
              rw,
              inserter,
              dc,
              "TARGET BRANCH",
              mergeTip,
              "SOURCE BRANCH",
              originalCommit,
              mergeResults);
    }

    CommitBuilder mergeCommit = new CommitBuilder();
    mergeCommit.setTreeId(tree);
    mergeCommit.setParentIds(mergeTip, originalCommit);
    mergeCommit.setAuthor(authorIdent);
    mergeCommit.setCommitter(committerIdent);
    mergeCommit.setMessage(commitMsg);
    CodeReviewCommit commit = rw.parseCommit(inserter.insert(mergeCommit));
    commit.setFilesWithGitConflicts(filesWithGitConflicts);
    return commit;
  }

  public static String createConflictMessage(List<String> conflicts) {
    if (conflicts.isEmpty()) {
      return "";
    }

    StringBuilder sb = new StringBuilder("merge conflict(s):");
    for (String c : conflicts) {
      sb.append('\n').append(c);
    }
    return sb.toString();
  }

  /**
   * Adds footers to existing commit message based on the state of the change.
   *
   * <p>This adds the following footers if they are missing:
   *
   * <ul>
   *   <li>Reviewed-on: <i>url</i>
   *   <li>Reviewed-by | Tested-by | <i>Other-Label-Name</i>: <i>reviewer</i>
   *   <li>Change-Id
   * </ul>
   *
   * @return new message
   */
  private String createDetailedCommitMessage(RevCommit n, ChangeNotes notes, PatchSet.Id psId) {
    Change c = notes.getChange();
    final List<FooterLine> footers = n.getFooterLines();
    final StringBuilder msgbuf = new StringBuilder();
    msgbuf.append(n.getFullMessage());

    if (msgbuf.length() == 0) {
      // WTF, an empty commit message?
      msgbuf.append("<no commit message provided>");
    }
    if (msgbuf.charAt(msgbuf.length() - 1) != '\n') {
      // Missing a trailing LF? Correct it (perhaps the editor was broken).
      msgbuf.append('\n');
    }
    if (footers.isEmpty()) {
      // Doesn't end in a "Signed-off-by: ..." style line? Add another line
      // break to start a new paragraph for the reviewed-by tag lines.
      //
      msgbuf.append('\n');
    }

    if (changeUtil.getChangeIdsFromFooter(n).isEmpty()) {
      msgbuf.append(FooterConstants.CHANGE_ID.getName());
      msgbuf.append(": ");
      msgbuf.append(c.getKey().get());
      msgbuf.append('\n');
    }

    Optional<String> url = urlFormatter.get().getChangeViewUrl(c.getProject(), c.getId());
    if (url.isPresent()) {
      if (!contains(footers, FooterConstants.REVIEWED_ON, url.get())) {
        msgbuf
            .append(FooterConstants.REVIEWED_ON.getName())
            .append(": ")
            .append(url.get())
            .append('\n');
      }
    }
    PatchSetApproval submitAudit = null;

    for (PatchSetApproval a : safeGetApprovals(notes, psId)) {
      if (a.value() <= 0) {
        // Negative votes aren't counted.
        continue;
      }

      if (a.isLegacySubmit()) {
        // Submit is treated specially, below (becomes committer)
        //
        if (submitAudit == null || a.granted().compareTo(submitAudit.granted()) > 0) {
          submitAudit = a;
        }
        continue;
      }

      final Account acc = identifiedUserFactory.create(a.accountId()).getAccount();
      final StringBuilder identbuf = new StringBuilder();
      if (acc.fullName() != null && acc.fullName().length() > 0) {
        if (identbuf.length() > 0) {
          identbuf.append(' ');
        }
        identbuf.append(acc.fullName());
      }
      if (acc.preferredEmail() != null && acc.preferredEmail().length() > 0) {
        if (isSignedOffBy(footers, acc.preferredEmail())) {
          continue;
        }
        if (identbuf.length() > 0) {
          identbuf.append(' ');
        }
        identbuf.append('<');
        identbuf.append(acc.preferredEmail());
        identbuf.append('>');
      }
      if (identbuf.length() == 0) {
        // Nothing reasonable to describe them by? Ignore them.
        continue;
      }

      final String tag;
      if (isCodeReview(a.labelId())) {
        tag = "Reviewed-by";
      } else if (isVerified(a.labelId())) {
        tag = "Tested-by";
      } else {
        final Optional<LabelType> lt = project.getLabelTypes().byLabel(a.labelId());
        if (!lt.isPresent()) {
          continue;
        }
        tag = lt.get().getName();
      }

      if (!contains(footers, new FooterKey(tag), identbuf.toString())) {
        msgbuf.append(tag);
        msgbuf.append(": ");
        msgbuf.append(identbuf);
        msgbuf.append('\n');
      }
    }
    return msgbuf.toString();
  }

  public String createCommitMessageOnSubmit(CodeReviewCommit n, RevCommit mergeTip) {
    return createCommitMessageOnSubmit(n, mergeTip, n.notes(), n.getPatchsetId());
  }

  /**
   * Creates a commit message for a change, which can be customized by plugins.
   *
   * <p>By default, adds footers to existing commit message based on the state of the change.
   * Plugins implementing {@link ChangeMessageModifier} can modify the resulting commit message
   * arbitrarily.
   *
   * @return new message
   */
  public String createCommitMessageOnSubmit(
      RevCommit n, @Nullable RevCommit mergeTip, ChangeNotes notes, PatchSet.Id id) {
    return commitMessageGenerator.generate(
        n, mergeTip, notes.getChange().getDest(), createDetailedCommitMessage(n, notes, id));
  }

  private static boolean isCodeReview(LabelId id) {
    return LabelId.CODE_REVIEW.equalsIgnoreCase(id.get());
  }

  private static boolean isVerified(LabelId id) {
    return LabelId.VERIFIED.equalsIgnoreCase(id.get());
  }

  private Iterable<PatchSetApproval> safeGetApprovals(ChangeNotes notes, PatchSet.Id psId) {
    try {
      return approvalsUtil.byPatchSet(notes, psId);
    } catch (StorageException e) {
      logger.atSevere().withCause(e).log("Can't read approval records for %s", psId);
      return Collections.emptyList();
    }
  }

  private static boolean contains(List<FooterLine> footers, FooterKey key, String val) {
    for (FooterLine line : footers) {
      if (line.matches(key) && val.equals(line.getValue())) {
        return true;
      }
    }
    return false;
  }

  private static boolean isSignedOffBy(List<FooterLine> footers, String email) {
    for (FooterLine line : footers) {
      if (line.matches(FooterKey.SIGNED_OFF_BY) && email.equals(line.getEmailAddress())) {
        return true;
      }
    }
    return false;
  }

  public boolean canMerge(
      MergeSorter mergeSorter,
      Repository repo,
      CodeReviewCommit mergeTip,
      CodeReviewCommit toMerge) {
    if (hasMissingDependencies(mergeSorter, toMerge)) {
      return false;
    }

    return canMerge(mergeTip, repo, toMerge);
  }

  private boolean canMerge(CodeReviewCommit mergeTip, Repository repo, CodeReviewCommit toMerge) {
    try (ObjectInserter ins = new InMemoryInserter(repo)) {
      return newThreeWayMerger(ins, repo.getConfig()).merge(mergeTip, toMerge);
    } catch (LargeObjectException e) {
      logger.atWarning().log("Cannot merge due to LargeObjectException: %s", toMerge.name());
      return false;
    } catch (NoMergeBaseException e) {
      return false;
    } catch (IOException e) {
      throw new StorageException("Cannot merge " + toMerge.name(), e);
    }
  }

  public boolean canFastForward(
      MergeSorter mergeSorter,
      CodeReviewCommit mergeTip,
      CodeReviewRevWalk rw,
      CodeReviewCommit toMerge) {
    if (hasMissingDependencies(mergeSorter, toMerge)) {
      return false;
    }

    return canFastForward(mergeTip, rw, toMerge);
  }

  private boolean canFastForward(
      CodeReviewCommit mergeTip, CodeReviewRevWalk rw, CodeReviewCommit toMerge) {
    try {
      return mergeTip == null
          || rw.isMergedInto(mergeTip, toMerge)
          || rw.isMergedInto(toMerge, mergeTip);
    } catch (IOException e) {
      throw new StorageException("Cannot fast-forward test during merge", e);
    }
  }

  public boolean canFastForwardOrMerge(
      MergeSorter mergeSorter,
      CodeReviewCommit mergeTip,
      CodeReviewRevWalk rw,
      Repository repo,
      CodeReviewCommit toMerge) {
    if (hasMissingDependencies(mergeSorter, toMerge)) {
      return false;
    }

    return canFastForward(mergeTip, rw, toMerge) || canMerge(mergeTip, repo, toMerge);
  }

  public boolean canCherryPick(
      MergeSorter mergeSorter,
      Repository repo,
      CodeReviewCommit mergeTip,
      CodeReviewRevWalk rw,
      CodeReviewCommit toMerge) {
    if (mergeTip == null) {
      // The branch is unborn. Fast-forward is possible.
      //
      return true;
    }

    if (toMerge.getParentCount() == 0) {
      // Refuse to merge a root commit into an existing branch,
      // we cannot obtain a delta for the cherry-pick to apply.
      //
      return false;
    }

    if (toMerge.getParentCount() == 1) {
      // If there is only one parent, a cherry-pick can be done by
      // taking the delta relative to that one parent and redoing
      // that on the current merge tip.
      //
      try (ObjectInserter ins = new InMemoryInserter(repo)) {
        ThreeWayMerger m = newThreeWayMerger(ins, repo.getConfig());
        m.setBase(toMerge.getParent(0));
        return m.merge(mergeTip, toMerge);
      } catch (IOException e) {
        throw new StorageException(
            String.format(
                "Cannot merge commit %s with mergetip %s", toMerge.name(), mergeTip.name()),
            e);
      }
    }

    // There are multiple parents, so this is a merge commit. We
    // don't want to cherry-pick the merge as clients can't easily
    // rebase their history with that merge present and replaced
    // by an equivalent merge with a different first parent. So
    // instead behave as though MERGE_IF_NECESSARY was configured.
    //
    return canFastForwardOrMerge(mergeSorter, mergeTip, rw, repo, toMerge);
  }

  public boolean hasMissingDependencies(MergeSorter mergeSorter, CodeReviewCommit toMerge) {
    try {
      return !mergeSorter.sort(Collections.singleton(toMerge)).contains(toMerge);
    } catch (IOException | StorageException e) {
      throw new StorageException("Branch head sorting failed", e);
    }
  }

  public CodeReviewCommit mergeOneCommit(
      PersonIdent author,
      PersonIdent committer,
      CodeReviewRevWalk rw,
      ObjectInserter inserter,
      Config repoConfig,
      BranchNameKey destBranch,
      CodeReviewCommit mergeTip,
      CodeReviewCommit n)
      throws InvalidMergeStrategyException {
    ThreeWayMerger m = newThreeWayMerger(inserter, repoConfig);
    try {
      if (m.merge(mergeTip, n)) {
        return writeMergeCommit(
            author, committer, rw, inserter, destBranch, mergeTip, m.getResultTreeId(), n);
      }
      failed(rw, mergeTip, n, CommitMergeStatus.PATH_CONFLICT);
    } catch (NoMergeBaseException e) {
      try {
        failed(rw, mergeTip, n, getCommitMergeStatus(e.getReason()));
      } catch (IOException e2) {
        throw new StorageException("Cannot merge " + n.name(), e2);
      }
    } catch (IOException e) {
      throw new StorageException("Cannot merge " + n.name(), e);
    }
    return mergeTip;
  }

  private static CommitMergeStatus getCommitMergeStatus(MergeBaseFailureReason reason) {
    switch (reason) {
      case MULTIPLE_MERGE_BASES_NOT_SUPPORTED:
      case TOO_MANY_MERGE_BASES:
      default:
        return CommitMergeStatus.MANUAL_RECURSIVE_MERGE;
      case CONFLICTS_DURING_MERGE_BASE_CALCULATION:
        return CommitMergeStatus.PATH_CONFLICT;
    }
  }

  /**
   * Marks all commits that are reachable from the given commit {@code n} as failed by setting the
   * provided {@code failure} status code on them.
   *
   * <p>If the same commits are retrieved from the same {@link CodeReviewRevWalk} instance later the
   * status code that we set here can be read there.
   */
  private static void failed(
      CodeReviewRevWalk rw,
      CodeReviewCommit mergeTip,
      CodeReviewCommit n,
      CommitMergeStatus failure)
      throws MissingObjectException, IncorrectObjectTypeException, IOException {
    rw.reset();
    rw.markStart(n);
    rw.markUninteresting(mergeTip);
    CodeReviewCommit failed;
    while ((failed = rw.next()) != null) {
      failed.setStatusCode(failure);
    }
  }

  public CodeReviewCommit writeMergeCommit(
      PersonIdent author,
      PersonIdent committer,
      CodeReviewRevWalk rw,
      ObjectInserter inserter,
      BranchNameKey destBranch,
      CodeReviewCommit mergeTip,
      ObjectId treeId,
      CodeReviewCommit n)
      throws IOException, MissingObjectException, IncorrectObjectTypeException {
    final List<CodeReviewCommit> merged = new ArrayList<>();
    rw.reset();
    rw.markStart(n);
    rw.markUninteresting(mergeTip);
    CodeReviewCommit crc;
    while ((crc = rw.next()) != null) {
      if (crc.getPatchsetId() != null) {
        merged.add(crc);
      }
    }

    StringBuilder msgbuf = new StringBuilder().append(summarize(rw, merged));
    if (!R_HEADS_MASTER.equals(destBranch.branch())) {
      msgbuf.append(" into ");
      msgbuf.append(destBranch.shortName());
    }

    if (merged.size() > 1) {
      msgbuf.append("\n\n* changes:\n");
      for (CodeReviewCommit c : merged) {
        rw.parseBody(c);
        msgbuf.append("  ");
        msgbuf.append(c.getShortMessage());
        msgbuf.append("\n");
      }
    }

    final CommitBuilder mergeCommit = new CommitBuilder();
    mergeCommit.setTreeId(treeId);
    mergeCommit.setParentIds(mergeTip, n);
    mergeCommit.setAuthor(author);
    mergeCommit.setCommitter(committer);
    mergeCommit.setMessage(msgbuf.toString());

    CodeReviewCommit mergeResult = rw.parseCommit(inserter.insert(mergeCommit));
    mergeResult.setNotes(n.getNotes());
    return mergeResult;
  }

  private String summarize(RevWalk rw, List<CodeReviewCommit> merged) throws IOException {
    if (merged.size() == 1) {
      CodeReviewCommit c = merged.get(0);
      rw.parseBody(c);
      return String.format("Merge \"%s\"", c.getShortMessage());
    }

    ImmutableSortedSet<String> topics =
        merged.stream()
            .map(c -> c.change().getTopic())
            .filter(t -> !Strings.isNullOrEmpty(t))
            .map(t -> "\"" + t + "\"")
            .collect(toImmutableSortedSet(naturalOrder()));

    if (!topics.isEmpty()) {
      return String.format(
          "Merge changes from topic%s %s",
          topics.size() > 1 ? "s" : "", topics.stream().collect(joining(", ")));
    }
    return merged.stream()
        .limit(5)
        .map(c -> c.change().getKey().abbreviate())
        .collect(joining(",", "Merge changes ", merged.size() > 5 ? ", ..." : ""));
  }

  public ThreeWayMerger newThreeWayMerger(ObjectInserter inserter, Config repoConfig)
      throws InvalidMergeStrategyException {
    return newThreeWayMerger(inserter, repoConfig, mergeStrategyName());
  }

  public String mergeStrategyName() {
    return mergeStrategyName(useContentMerge, useRecursiveMerge);
  }

  public static String mergeStrategyName(boolean useContentMerge, boolean useRecursiveMerge) {
    String mergeStrategy;

    if (useContentMerge) {
      // Settings for this project allow us to try and automatically resolve
      // conflicts within files if needed. Use either the old resolve merger or
      // new recursive merger, and instruct to operate in core.
      if (useRecursiveMerge) {
        mergeStrategy = MergeStrategy.RECURSIVE.getName();
      } else {
        mergeStrategy = MergeStrategy.RESOLVE.getName();
      }
    } else {
      // No auto conflict resolving allowed. If any of the
      // affected files was modified, merge will fail.
      mergeStrategy = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.getName();
    }

    logger.atFine().log(
        "mergeStrategy = %s (useContentMerge = %s, useRecursiveMerge = %s)",
        mergeStrategy, useContentMerge, useRecursiveMerge);
    return mergeStrategy;
  }

  public static ThreeWayMerger newThreeWayMerger(
      ObjectInserter inserter, Config repoConfig, String strategyName)
      throws InvalidMergeStrategyException {
    Merger m = newMerger(inserter, repoConfig, strategyName);
    checkArgument(
        m instanceof ThreeWayMerger,
        "merge strategy %s does not support three-way merging",
        strategyName);
    return (ThreeWayMerger) m;
  }

  public static Merger newMerger(ObjectInserter inserter, Config repoConfig, String strategyName)
      throws InvalidMergeStrategyException {
    MergeStrategy strategy = MergeStrategy.get(strategyName);
    if (strategy == null) {
      throw new InvalidMergeStrategyException(strategyName);
    }
    return strategy.newMerger(
        new ObjectInserter.Filter() {
          @Override
          protected ObjectInserter delegate() {
            return inserter;
          }

          @Override
          public void flush() {}

          @Override
          public void close() {}

          @Override
          public String toString() {
            return String.format(
                "%s (wrapped inserter: %s)", super.toString(), inserter.toString());
          }
        },
        repoConfig);
  }

  public void markCleanMerges(
      RevWalk rw, RevFlag canMergeFlag, CodeReviewCommit mergeTip, Set<RevCommit> alreadyAccepted) {
    if (mergeTip == null) {
      // If mergeTip is null here, branchTip was null, indicating a new branch
      // at the start of the merge process. We also elected to merge nothing,
      // probably due to missing dependencies. Nothing was cleanly merged.
      //
      return;
    }

    try {
      rw.resetRetain(canMergeFlag);
      rw.sort(RevSort.TOPO);
      rw.sort(RevSort.REVERSE, true);
      rw.markStart(mergeTip);
      for (RevCommit c : alreadyAccepted) {
        // If branch was not created by this submit.
        if (!Objects.equals(c, mergeTip)) {
          rw.markUninteresting(c);
        }
      }

      CodeReviewCommit c;
      while ((c = (CodeReviewCommit) rw.next()) != null) {
        if (c.getPatchsetId() != null && c.getStatusCode() == null) {
          c.setStatusCode(CommitMergeStatus.CLEAN_MERGE);
        }
      }
    } catch (IOException e) {
      throw new StorageException("Cannot mark clean merges", e);
    }
  }

  public Set<Change.Id> findUnmergedChanges(
      Set<Change.Id> expected,
      CodeReviewRevWalk rw,
      RevFlag canMergeFlag,
      CodeReviewCommit oldTip,
      CodeReviewCommit mergeTip,
      Iterable<Change.Id> alreadyMerged) {
    if (mergeTip == null) {
      return expected;
    }

    try {
      Set<Change.Id> found = Sets.newHashSetWithExpectedSize(expected.size());
      Iterables.addAll(found, alreadyMerged);
      rw.resetRetain(canMergeFlag);
      rw.sort(RevSort.TOPO);
      rw.markStart(mergeTip);
      if (oldTip != null) {
        rw.markUninteresting(oldTip);
      }

      CodeReviewCommit c;
      while ((c = rw.next()) != null) {
        if (c.getPatchsetId() == null) {
          continue;
        }
        Change.Id id = c.getPatchsetId().changeId();
        if (!expected.contains(id)) {
          continue;
        }
        found.add(id);
        if (found.size() == expected.size()) {
          return Collections.emptySet();
        }
      }
      return Sets.difference(expected, found);
    } catch (IOException e) {
      throw new StorageException("Cannot check if changes were merged", e);
    }
  }

  @Nullable
  public static CodeReviewCommit findAnyMergedInto(
      CodeReviewRevWalk rw, Iterable<CodeReviewCommit> commits, CodeReviewCommit tip)
      throws IOException {
    for (CodeReviewCommit c : commits) {
      // TODO(dborowitz): Seems like this could get expensive for many patch
      // sets. Is there a more efficient implementation?
      if (rw.isMergedInto(c, tip)) {
        return c;
      }
    }
    return null;
  }

  public static RevCommit resolveCommit(Repository repo, RevWalk rw, String str)
      throws BadRequestException, ResourceNotFoundException, IOException {
    try {
      ObjectId commitId = repo.resolve(str);
      if (commitId == null) {
        throw new BadRequestException("Cannot resolve '" + str + "' to a commit");
      }
      return rw.parseCommit(commitId);
    } catch (AmbiguousObjectException | IncorrectObjectTypeException | RevisionSyntaxException e) {
      throw new BadRequestException(e.getMessage());
    } catch (MissingObjectException e) {
      throw new ResourceNotFoundException(e.getMessage());
    }
  }

  private static void matchAuthorToCommitterDate(ProjectState project, CommitBuilder commit) {
    if (project.is(BooleanProjectConfig.MATCH_AUTHOR_TO_COMMITTER_DATE)) {
      commit.setAuthor(
          new PersonIdent(
              commit.getAuthor(),
              commit.getCommitter().getWhen(),
              commit.getCommitter().getTimeZone()));
    }
  }
}