1 /*
2 * Copyright (C) 2012, Research In Motion Limited
3 * Copyright (C) 2012, Christian Halstrick <christian.halstrick@sap.com>
4 * and other copyright owners as documented in the project's IP log.
5 *
6 * This program and the accompanying materials are made available
7 * under the terms of the Eclipse Distribution License v1.0 which
8 * accompanies this distribution, is reproduced below, and is
9 * available at http://www.eclipse.org/org/documents/edl-v10.php
10 *
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or
14 * without modification, are permitted provided that the following
15 * conditions are met:
16 *
17 * - Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials provided
23 * with the distribution.
24 *
25 * - Neither the name of the Eclipse Foundation, Inc. nor the
26 * names of its contributors may be used to endorse or promote
27 * products derived from this software without specific prior
28 * written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
31 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
32 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
35 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
36 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
37 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
38 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
39 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
42 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 */
44
45 /*
46 * Contributors:
47 * George Young - initial API and implementation
48 * Christian Halstrick - initial API and implementation
49 */
50 package org.eclipse.jgit.merge;
51
52 import java.io.IOException;
53 import java.text.MessageFormat;
54 import java.util.ArrayList;
55 import java.util.Date;
56 import java.util.List;
57 import java.util.TimeZone;
58
59 import org.eclipse.jgit.dircache.DirCache;
60 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
61 import org.eclipse.jgit.errors.NoMergeBaseException;
62 import org.eclipse.jgit.internal.JGitText;
63 import org.eclipse.jgit.lib.CommitBuilder;
64 import org.eclipse.jgit.lib.Config;
65 import org.eclipse.jgit.lib.ObjectId;
66 import org.eclipse.jgit.lib.ObjectInserter;
67 import org.eclipse.jgit.lib.PersonIdent;
68 import org.eclipse.jgit.lib.Repository;
69 import org.eclipse.jgit.revwalk.RevCommit;
70 import org.eclipse.jgit.revwalk.filter.RevFilter;
71 import org.eclipse.jgit.treewalk.AbstractTreeIterator;
72 import org.eclipse.jgit.treewalk.EmptyTreeIterator;
73 import org.eclipse.jgit.treewalk.WorkingTreeIterator;
74
75 /**
76 * A three-way merger performing a content-merge if necessary across multiple
77 * bases using recursion
78 *
79 * This merger extends the resolve merger and does several things differently:
80 *
81 * - allow more than one merge base, up to a maximum
82 *
83 * - uses "Lists" instead of Arrays for chained types
84 *
85 * - recursively merges the merge bases together to compute a usable base
86 *
87 * @since 3.0
88 */
89 public class RecursiveMerger extends ResolveMerger {
90 /**
91 * The maximum number of merge bases. This merge will stop when the number
92 * of merge bases exceeds this value
93 */
94 public final int MAX_BASES = 200;
95
96 /**
97 * Normal recursive merge when you want a choice of DirCache placement
98 * inCore
99 *
100 * @param local
101 * a {@link org.eclipse.jgit.lib.Repository} object.
102 * @param inCore
103 * a boolean.
104 */
105 protected RecursiveMerger(Repository local, boolean inCore) {
106 super(local, inCore);
107 }
108
109 /**
110 * Normal recursive merge, implies not inCore
111 *
112 * @param local a {@link org.eclipse.jgit.lib.Repository} object.
113 */
114 protected RecursiveMerger(Repository local) {
115 this(local, false);
116 }
117
118 /**
119 * Normal recursive merge, implies inCore.
120 *
121 * @param inserter
122 * an {@link org.eclipse.jgit.lib.ObjectInserter} object.
123 * @param config
124 * the repository configuration
125 * @since 4.8
126 */
127 protected RecursiveMerger(ObjectInserter inserter, Config config) {
128 super(inserter, config);
129 }
130
131 /**
132 * {@inheritDoc}
133 * <p>
134 * Get a single base commit for two given commits. If the two source commits
135 * have more than one base commit recursively merge the base commits
136 * together until you end up with a single base commit.
137 */
138 @Override
139 protected RevCommit getBaseCommit(RevCommit a, RevCommit b)
140 throws IncorrectObjectTypeException, IOException {
141 return getBaseCommit(a, b, 0);
142 }
143
144 /**
145 * Get a single base commit for two given commits. If the two source commits
146 * have more than one base commit recursively merge the base commits
147 * together until a virtual common base commit has been found.
148 *
149 * @param a
150 * the first commit to be merged
151 * @param b
152 * the second commit to be merged
153 * @param callDepth
154 * the callDepth when this method is called recursively
155 * @return the merge base of two commits. If a criss-cross merge required a
156 * synthetic merge base this commit is visible only the merger's
157 * RevWalk and will not be in the repository.
158 * @throws java.io.IOException
159 * @throws IncorrectObjectTypeException
160 * one of the input objects is not a commit.
161 * @throws NoMergeBaseException
162 * too many merge bases are found or the computation of a common
163 * merge base failed (e.g. because of a conflict).
164 */
165 protected RevCommit getBaseCommit(RevCommit a, RevCommit b, int callDepth)
166 throws IOException {
167 ArrayList<RevCommit> baseCommits = new ArrayList<>();
168 walk.reset();
169 walk.setRevFilter(RevFilter.MERGE_BASE);
170 walk.markStart(a);
171 walk.markStart(b);
172 RevCommit c;
173 while ((c = walk.next()) != null)
174 baseCommits.add(c);
175
176 if (baseCommits.isEmpty())
177 return null;
178 if (baseCommits.size() == 1)
179 return baseCommits.get(0);
180 if (baseCommits.size() >= MAX_BASES)
181 throw new NoMergeBaseException(NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES, MessageFormat.format(
182 JGitText.get().mergeRecursiveTooManyMergeBasesFor,
183 Integer.valueOf(MAX_BASES), a.name(), b.name(),
184 Integer.valueOf(baseCommits.size())));
185
186 // We know we have more than one base commit. We have to do merges now
187 // to determine a single base commit. We don't want to spoil the current
188 // dircache and working tree with the results of this intermediate
189 // merges. Therefore set the dircache to a new in-memory dircache and
190 // disable that we update the working-tree. We set this back to the
191 // original values once a single base commit is created.
192 RevCommit currentBase = baseCommits.get(0);
193 DirCache oldDircache = dircache;
194 boolean oldIncore = inCore;
195 WorkingTreeIterator oldWTreeIt = workingTreeIterator;
196 workingTreeIterator = null;
197 try {
198 dircache = DirCache.read(reader, currentBase.getTree());
199 inCore = true;
200
201 List<RevCommit> parents = new ArrayList<>();
202 parents.add(currentBase);
203 for (int commitIdx = 1; commitIdx < baseCommits.size(); commitIdx++) {
204 RevCommit nextBase = baseCommits.get(commitIdx);
205 if (commitIdx >= MAX_BASES)
206 throw new NoMergeBaseException(
207 NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES,
208 MessageFormat.format(
209 JGitText.get().mergeRecursiveTooManyMergeBasesFor,
210 Integer.valueOf(MAX_BASES), a.name(), b.name(),
211 Integer.valueOf(baseCommits.size())));
212 parents.add(nextBase);
213 RevCommit bc = getBaseCommit(currentBase, nextBase,
214 callDepth + 1);
215 AbstractTreeIterator bcTree = (bc == null) ? new EmptyTreeIterator()
216 : openTree(bc.getTree());
217 if (mergeTrees(bcTree, currentBase.getTree(),
218 nextBase.getTree(), true))
219 currentBase = createCommitForTree(resultTree, parents);
220 else
221 throw new NoMergeBaseException(
222 NoMergeBaseException.MergeBaseFailureReason.CONFLICTS_DURING_MERGE_BASE_CALCULATION,
223 MessageFormat.format(
224 JGitText.get().mergeRecursiveConflictsWhenMergingCommonAncestors,
225 currentBase.getName(), nextBase.getName()));
226 }
227 } finally {
228 inCore = oldIncore;
229 dircache = oldDircache;
230 workingTreeIterator = oldWTreeIt;
231 toBeCheckedOut.clear();
232 toBeDeleted.clear();
233 modifiedFiles.clear();
234 unmergedPaths.clear();
235 mergeResults.clear();
236 failingPaths.clear();
237 }
238 return currentBase;
239 }
240
241 /**
242 * Create a new commit by explicitly specifying the content tree and the
243 * parents. The commit message is not set and author/committer are set to
244 * the current user.
245 *
246 * @param tree
247 * the tree this commit should capture
248 * @param parents
249 * the list of parent commits
250 * @return a new commit visible only within this merger's RevWalk.
251 * @throws IOException
252 */
253 private RevCommit createCommitForTree(ObjectId tree, List<RevCommit> parents)
254 throws IOException {
255 CommitBuilder c = new CommitBuilder();
256 c.setTreeId(tree);
257 c.setParentIds(parents);
258 c.setAuthor(mockAuthor(parents));
259 c.setCommitter(c.getAuthor());
260 return RevCommit.parse(walk, c.build());
261 }
262
263 private static PersonIdent mockAuthor(List<RevCommit> parents) {
264 String name = RecursiveMerger.class.getSimpleName();
265 int time = 0;
266 for (RevCommit p : parents)
267 time = Math.max(time, p.getCommitTime());
268 return new PersonIdent(
269 name, name + "@JGit", //$NON-NLS-1$
270 new Date((time + 1) * 1000L),
271 TimeZone.getTimeZone("GMT+0000")); //$NON-NLS-1$
272 }
273 }