RecursiveMerger.java

  1. /*
  2.  * Copyright (C) 2012, Research In Motion Limited
  3.  * Copyright (C) 2012, Christian Halstrick <christian.halstrick@sap.com> and others
  4.  *
  5.  * This program and the accompanying materials are made available under the
  6.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  7.  * https://www.eclipse.org/org/documents/edl-v10.php.
  8.  *
  9.  * SPDX-License-Identifier: BSD-3-Clause
  10.  */

  12. /*
  13.  * Contributors:
  14.  *    George Young - initial API and implementation
  15.  *    Christian Halstrick - initial API and implementation
  16.  */
  17. package org.eclipse.jgit.merge;

  19. import java.io.IOException;
  20. import java.text.MessageFormat;
  21. import java.util.ArrayList;
  22. import java.util.Date;
  23. import java.util.List;
  24. import java.util.TimeZone;

  26. import org.eclipse.jgit.dircache.DirCache;
  27. import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  28. import org.eclipse.jgit.errors.NoMergeBaseException;
  29. import org.eclipse.jgit.internal.JGitText;
  30. import org.eclipse.jgit.lib.CommitBuilder;
  31. import org.eclipse.jgit.lib.Config;
  32. import org.eclipse.jgit.lib.ObjectId;
  33. import org.eclipse.jgit.lib.ObjectInserter;
  34. import org.eclipse.jgit.lib.PersonIdent;
  35. import org.eclipse.jgit.lib.Repository;
  36. import org.eclipse.jgit.revwalk.RevCommit;
  37. import org.eclipse.jgit.revwalk.filter.RevFilter;
  38. import org.eclipse.jgit.treewalk.AbstractTreeIterator;
  39. import org.eclipse.jgit.treewalk.EmptyTreeIterator;
  40. import org.eclipse.jgit.treewalk.WorkingTreeIterator;

  42. /**
  43.  * A three-way merger performing a content-merge if necessary across multiple
  44.  * bases using recursion
  45.  *
  46.  * This merger extends the resolve merger and does several things differently:
  47.  *
  48.  * - allow more than one merge base, up to a maximum
  49.  *
  50.  * - uses "Lists" instead of Arrays for chained types
  51.  *
  52.  * - recursively merges the merge bases together to compute a usable base
  53.  *
  54.  * @since 3.0
  55.  */
  56. public class RecursiveMerger extends ResolveMerger {
  57.     /**
  58.      * The maximum number of merge bases. This merge will stop when the number
  59.      * of merge bases exceeds this value
  60.      */
  61.     public final int MAX_BASES = 200;

  63.     /**
  64.      * Normal recursive merge when you want a choice of DirCache placement
  65.      * inCore
  66.      *
  67.      * @param local
  68.      *            a {@link org.eclipse.jgit.lib.Repository} object.
  69.      * @param inCore
  70.      *            a boolean.
  71.      */
  72.     protected RecursiveMerger(Repository local, boolean inCore) {
  73.         super(local, inCore);
  74.     }

  76.     /**
  77.      * Normal recursive merge, implies not inCore
  78.      *
  79.      * @param local a {@link org.eclipse.jgit.lib.Repository} object.
  80.      */
  81.     protected RecursiveMerger(Repository local) {
  82.         this(local, false);
  83.     }

  85.     /**
  86.      * Normal recursive merge, implies inCore.
  87.      *
  88.      * @param inserter
  89.      *            an {@link org.eclipse.jgit.lib.ObjectInserter} object.
  90.      * @param config
  91.      *            the repository configuration
  92.      * @since 4.8
  93.      */
  94.     protected RecursiveMerger(ObjectInserter inserter, Config config) {
  95.         super(inserter, config);
  96.     }

  98.     /**
  99.      * {@inheritDoc}
  100.      * <p>
  101.      * Get a single base commit for two given commits. If the two source commits
  102.      * have more than one base commit recursively merge the base commits
  103.      * together until you end up with a single base commit.
  104.      */
  105.     @Override
  106.     protected RevCommit getBaseCommit(RevCommit a, RevCommit b)
  107.             throws IncorrectObjectTypeException, IOException {
  108.         return getBaseCommit(a, b, 0);
  109.     }

  111.     /**
  112.      * Get a single base commit for two given commits. If the two source commits
  113.      * have more than one base commit recursively merge the base commits
  114.      * together until a virtual common base commit has been found.
  115.      *
  116.      * @param a
  117.      *            the first commit to be merged
  118.      * @param b
  119.      *            the second commit to be merged
  120.      * @param callDepth
  121.      *            the callDepth when this method is called recursively
  122.      * @return the merge base of two commits. If a criss-cross merge required a
  123.      *         synthetic merge base this commit is visible only the merger's
  124.      *         RevWalk and will not be in the repository.
  125.      * @throws java.io.IOException
  126.      * @throws IncorrectObjectTypeException
  127.      *             one of the input objects is not a commit.
  128.      * @throws NoMergeBaseException
  129.      *             too many merge bases are found or the computation of a common
  130.      *             merge base failed (e.g. because of a conflict).
  131.      */
  132.     protected RevCommit getBaseCommit(RevCommit a, RevCommit b, int callDepth)
  133.             throws IOException {
  134.         ArrayList<RevCommit> baseCommits = new ArrayList<>();
  135.         walk.reset();
  136.         walk.setRevFilter(RevFilter.MERGE_BASE);
  137.         walk.markStart(a);
  138.         walk.markStart(b);
  139.         RevCommit c;
  140.         while ((c = walk.next()) != null)
  141.             baseCommits.add(c);

  143.         if (baseCommits.isEmpty())
  144.             return null;
  145.         if (baseCommits.size() == 1)
  146.             return baseCommits.get(0);
  147.         if (baseCommits.size() >= MAX_BASES)
  148.             throw new NoMergeBaseException(NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES, MessageFormat.format(
  149.                     JGitText.get().mergeRecursiveTooManyMergeBasesFor,
  150.                     Integer.valueOf(MAX_BASES), a.name(), b.name(),
  151.                             Integer.valueOf(baseCommits.size())));

  153.         // We know we have more than one base commit. We have to do merges now
  154.         // to determine a single base commit. We don't want to spoil the current
  155.         // dircache and working tree with the results of this intermediate
  156.         // merges. Therefore set the dircache to a new in-memory dircache and
  157.         // disable that we update the working-tree. We set this back to the
  158.         // original values once a single base commit is created.
  159.         RevCommit currentBase = baseCommits.get(0);
  160.         DirCache oldDircache = dircache;
  161.         boolean oldIncore = inCore;
  162.         WorkingTreeIterator oldWTreeIt = workingTreeIterator;
  163.         workingTreeIterator = null;
  164.         try {
  165.             dircache = DirCache.read(reader, currentBase.getTree());
  166.             inCore = true;

  168.             List<RevCommit> parents = new ArrayList<>();
  169.             parents.add(currentBase);
  170.             for (int commitIdx = 1; commitIdx < baseCommits.size(); commitIdx++) {
  171.                 RevCommit nextBase = baseCommits.get(commitIdx);
  172.                 if (commitIdx >= MAX_BASES)
  173.                     throw new NoMergeBaseException(
  174.                             NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES,
  175.                             MessageFormat.format(
  176.                             JGitText.get().mergeRecursiveTooManyMergeBasesFor,
  177.                             Integer.valueOf(MAX_BASES), a.name(), b.name(),
  178.                                     Integer.valueOf(baseCommits.size())));
  179.                 parents.add(nextBase);
  180.                 RevCommit bc = getBaseCommit(currentBase, nextBase,
  181.                         callDepth + 1);
  182.                 AbstractTreeIterator bcTree = (bc == null) ? new EmptyTreeIterator()
  183.                         : openTree(bc.getTree());
  184.                 if (mergeTrees(bcTree, currentBase.getTree(),
  185.                         nextBase.getTree(), true))
  186.                     currentBase = createCommitForTree(resultTree, parents);
  187.                 else
  188.                     throw new NoMergeBaseException(
  189.                             NoMergeBaseException.MergeBaseFailureReason.CONFLICTS_DURING_MERGE_BASE_CALCULATION,
  190.                             MessageFormat.format(
  191.                                     JGitText.get().mergeRecursiveConflictsWhenMergingCommonAncestors,
  192.                                     currentBase.getName(), nextBase.getName()));
  193.             }
  194.         } finally {
  195.             inCore = oldIncore;
  196.             dircache = oldDircache;
  197.             workingTreeIterator = oldWTreeIt;
  198.             unmergedPaths.clear();
  199.             mergeResults.clear();
  200.             failingPaths.clear();
  201.         }
  202.         return currentBase;
  203.     }

  205.     /**
  206.      * Create a new commit by explicitly specifying the content tree and the
  207.      * parents. The commit message is not set and author/committer are set to
  208.      * the current user.
  209.      *
  210.      * @param tree
  211.      *            the tree this commit should capture
  212.      * @param parents
  213.      *            the list of parent commits
  214.      * @return a new commit visible only within this merger's RevWalk.
  215.      * @throws IOException
  216.      */
  217.     private RevCommit createCommitForTree(ObjectId tree, List<RevCommit> parents)
  218.             throws IOException {
  219.         CommitBuilder c = new CommitBuilder();
  220.         c.setTreeId(tree);
  221.         c.setParentIds(parents);
  222.         c.setAuthor(mockAuthor(parents));
  223.         c.setCommitter(c.getAuthor());
  224.         return RevCommit.parse(walk, c.build());
  225.     }

  227.     private static PersonIdent mockAuthor(List<RevCommit> parents) {
  228.         String name = RecursiveMerger.class.getSimpleName();
  229.         int time = 0;
  230.         for (RevCommit p : parents)
  231.             time = Math.max(time, p.getCommitTime());
  232.         return new PersonIdent(
  233.                 name, name + "@JGit", //$NON-NLS-1$
  234.                 new Date((time + 1) * 1000L),
  235.                 TimeZone.getTimeZone("GMT+0000")); //$NON-NLS-1$
  236.     }
  237. }
Created with JaCoCo 0.8.7.202105040129