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.ObjectId;
65 import org.eclipse.jgit.lib.PersonIdent;
66 import org.eclipse.jgit.lib.Repository;
67 import org.eclipse.jgit.revwalk.RevCommit;
68 import org.eclipse.jgit.revwalk.filter.RevFilter;
69 import org.eclipse.jgit.treewalk.AbstractTreeIterator;
70 import org.eclipse.jgit.treewalk.EmptyTreeIterator;
71 import org.eclipse.jgit.treewalk.WorkingTreeIterator;
72
73 /**
74 * A three-way merger performing a content-merge if necessary across multiple
75 * bases using recursion
76 *
77 * This merger extends the resolve merger and does several things differently:
78 *
79 * - allow more than one merge base, up to a maximum
80 *
81 * - uses "Lists" instead of Arrays for chained types
82 *
83 * - recursively merges the merge bases together to compute a usable base
84 * @since 3.0
85 */
86 public class RecursiveMerger extends ResolveMerger {
87 /**
88 * The maximum number of merge bases. This merge will stop when the number
89 * of merge bases exceeds this value
90 */
91 public final int MAX_BASES = 200;
92
93 /**
94 * Normal recursive merge when you want a choice of DirCache placement
95 * inCore
96 *
97 * @param local
98 * @param inCore
99 */
100 protected RecursiveMerger(Repository local, boolean inCore) {
101 super(local, inCore);
102 }
103
104 /**
105 * Normal recursive merge, implies not inCore
106 *
107 * @param local
108 */
109 protected RecursiveMerger(Repository local) {
110 this(local, false);
111 }
112
113 /**
114 * Get a single base commit for two given commits. If the two source commits
115 * have more than one base commit recursively merge the base commits
116 * together until you end up with a single base commit.
117 *
118 * @throws IOException
119 * @throws IncorrectObjectTypeException
120 */
121 @Override
122 protected RevCommit getBaseCommit(RevCommit a, RevCommit b)
123 throws IncorrectObjectTypeException, IOException {
124 return getBaseCommit(a, b, 0);
125 }
126
127 /**
128 * Get a single base commit for two given commits. If the two source commits
129 * have more than one base commit recursively merge the base commits
130 * together until a virtual common base commit has been found.
131 *
132 * @param a
133 * the first commit to be merged
134 * @param b
135 * the second commit to be merged
136 * @param callDepth
137 * the callDepth when this method is called recursively
138 * @return the merge base of two commits. If a criss-cross merge required a
139 * synthetic merge base this commit is visible only the merger's
140 * RevWalk and will not be in the repository.
141 * @throws IOException
142 * @throws IncorrectObjectTypeException
143 * one of the input objects is not a commit.
144 * @throws NoMergeBaseException
145 * too many merge bases are found or the computation of a common
146 * merge base failed (e.g. because of a conflict).
147 */
148 protected RevCommit getBaseCommit(RevCommit a, RevCommit b, int callDepth)
149 throws IOException {
150 ArrayList<RevCommit> baseCommits = new ArrayList<RevCommit>();
151 walk.reset();
152 walk.setRevFilter(RevFilter.MERGE_BASE);
153 walk.markStart(a);
154 walk.markStart(b);
155 RevCommit c;
156 while ((c = walk.next()) != null)
157 baseCommits.add(c);
158
159 if (baseCommits.isEmpty())
160 return null;
161 if (baseCommits.size() == 1)
162 return baseCommits.get(0);
163 if (baseCommits.size() >= MAX_BASES)
164 throw new NoMergeBaseException(NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES, MessageFormat.format(
165 JGitText.get().mergeRecursiveTooManyMergeBasesFor,
166 Integer.valueOf(MAX_BASES), a.name(), b.name(),
167 Integer.valueOf(baseCommits.size())));
168
169 // We know we have more than one base commit. We have to do merges now
170 // to determine a single base commit. We don't want to spoil the current
171 // dircache and working tree with the results of this intermediate
172 // merges. Therefore set the dircache to a new in-memory dircache and
173 // disable that we update the working-tree. We set this back to the
174 // original values once a single base commit is created.
175 RevCommit currentBase = baseCommits.get(0);
176 DirCache oldDircache = dircache;
177 boolean oldIncore = inCore;
178 WorkingTreeIterator oldWTreeIt = workingTreeIterator;
179 workingTreeIterator = null;
180 try {
181 dircache = DirCache.read(reader, currentBase.getTree());
182 inCore = true;
183
184 List<RevCommit> parents = new ArrayList<RevCommit>();
185 parents.add(currentBase);
186 for (int commitIdx = 1; commitIdx < baseCommits.size(); commitIdx++) {
187 RevCommit nextBase = baseCommits.get(commitIdx);
188 if (commitIdx >= MAX_BASES)
189 throw new NoMergeBaseException(
190 NoMergeBaseException.MergeBaseFailureReason.TOO_MANY_MERGE_BASES,
191 MessageFormat.format(
192 JGitText.get().mergeRecursiveTooManyMergeBasesFor,
193 Integer.valueOf(MAX_BASES), a.name(), b.name(),
194 Integer.valueOf(baseCommits.size())));
195 parents.add(nextBase);
196 RevCommit bc = getBaseCommit(currentBase, nextBase,
197 callDepth + 1);
198 AbstractTreeIterator bcTree = (bc == null) ? new EmptyTreeIterator()
199 : openTree(bc.getTree());
200 if (mergeTrees(bcTree, currentBase.getTree(),
201 nextBase.getTree(), true))
202 currentBase = createCommitForTree(resultTree, parents);
203 else
204 throw new NoMergeBaseException(
205 NoMergeBaseException.MergeBaseFailureReason.CONFLICTS_DURING_MERGE_BASE_CALCULATION,
206 MessageFormat.format(
207 JGitText.get().mergeRecursiveConflictsWhenMergingCommonAncestors,
208 currentBase.getName(), nextBase.getName()));
209 }
210 } finally {
211 inCore = oldIncore;
212 dircache = oldDircache;
213 workingTreeIterator = oldWTreeIt;
214 toBeCheckedOut.clear();
215 toBeDeleted.clear();
216 modifiedFiles.clear();
217 unmergedPaths.clear();
218 mergeResults.clear();
219 failingPaths.clear();
220 }
221 return currentBase;
222 }
223
224 /**
225 * Create a new commit by explicitly specifying the content tree and the
226 * parents. The commit message is not set and author/committer are set to
227 * the current user.
228 *
229 * @param tree
230 * the tree this commit should capture
231 * @param parents
232 * the list of parent commits
233 * @return a new commit visible only within this merger's RevWalk.
234 * @throws IOException
235 */
236 private RevCommit createCommitForTree(ObjectId tree, List<RevCommit> parents)
237 throws IOException {
238 CommitBuilder c = new CommitBuilder();
239 c.setTreeId(tree);
240 c.setParentIds(parents);
241 c.setAuthor(mockAuthor(parents));
242 c.setCommitter(c.getAuthor());
243 return RevCommit.parse(walk, c.build());
244 }
245
246 private static PersonIdent mockAuthor(List<RevCommit> parents) {
247 String name = RecursiveMerger.class.getSimpleName();
248 int time = 0;
249 for (RevCommit p : parents)
250 time = Math.max(time, p.getCommitTime());
251 return new PersonIdent(
252 name, name + "@JGit", //$NON-NLS-1$
253 new Date((time + 1) * 1000L),
254 TimeZone.getTimeZone("GMT+0000")); //$NON-NLS-1$
255 }
256 }