1 /*
2 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43
44 package org.eclipse.jgit.revwalk;
45
46 import java.io.IOException;
47 import java.text.MessageFormat;
48 import java.util.LinkedList;
49
50 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
51 import org.eclipse.jgit.errors.MissingObjectException;
52 import org.eclipse.jgit.internal.JGitText;
53
54 /**
55 * Computes the merge base(s) of the starting commits.
56 * <p>
57 * This generator is selected if the RevFilter is only
58 * {@link org.eclipse.jgit.revwalk.filter.RevFilter#MERGE_BASE}.
59 * <p>
60 * To compute the merge base we assign a temporary flag to each of the starting
61 * commits. The maximum number of starting commits is bounded by the number of
62 * free flags available in the RevWalk when the generator is initialized. These
63 * flags will be automatically released on the next reset of the RevWalk, but
64 * not until then, as they are assigned to commits throughout the history.
65 * <p>
66 * Several internal flags are reused here for a different purpose, but this
67 * should not have any impact as this generator should be run alone, and without
68 * any other generators wrapped around it.
69 */
70 class MergeBaseGenerator extends Generator {
71 private static final int PARSED = RevWalk.PARSED;
72
73 private static final int IN_PENDING = RevWalk.SEEN;
74
75 private static final int POPPED = RevWalk.TEMP_MARK;
76
77 private static final int MERGE_BASE = RevWalk.REWRITE;
78
79 private final RevWalk walker;
80
81 private final DateRevQueue pending;
82
83 private int branchMask;
84
85 private int recarryTest;
86
87 private int recarryMask;
88
89 private int mergeBaseAncestor = -1;
90 private LinkedList<RevCommit> ret = new LinkedList<RevCommit>();
91
92 MergeBaseGenerator(final RevWalk w) {
93 walker = w;
94 pending = new DateRevQueue();
95 }
96
97 void init(final AbstractRevQueue p) throws IOException {
98 try {
99 for (;;) {
100 final RevCommit c = p.next();
101 if (c == null)
102 break;
103 add(c);
104 }
105 // Setup the condition used by carryOntoOne to detect a late
106 // merge base and produce it on the next round.
107 //
108 recarryTest = branchMask | POPPED;
109 recarryMask = branchMask | POPPED | MERGE_BASE;
110 mergeBaseAncestor = walker.allocFlag();
111
112 for (;;) {
113 RevCommit c = _next();
114 if (c == null) {
115 break;
116 }
117 ret.add(c);
118 }
119 } finally {
120 // Always free the flags immediately. This ensures the flags
121 // will be available for reuse when the walk resets.
122 //
123 walker.freeFlag(branchMask | mergeBaseAncestor);
124 }
125 }
126
127 private void add(final RevCommit c) {
128 final int flag = walker.allocFlag();
129 branchMask |= flag;
130 if ((c.flags & branchMask) != 0) {
131 // This should never happen. RevWalk ensures we get a
132 // commit admitted to the initial queue only once. If
133 // we see this marks aren't correctly erased.
134 //
135 throw new IllegalStateException(MessageFormat.format(JGitText.get().staleRevFlagsOn, c.name()));
136 }
137 c.flags |= flag;
138 pending.add(c);
139 }
140
141 @Override
142 int outputType() {
143 return 0;
144 }
145
146 private RevCommit _next() throws MissingObjectException,
147 IncorrectObjectTypeException, IOException {
148 for (;;) {
149 final RevCommit c = pending.next();
150 if (c == null) {
151 return null;
152 }
153
154 for (final RevCommit p : c.parents) {
155 if ((p.flags & IN_PENDING) != 0)
156 continue;
157 if ((p.flags & PARSED) == 0)
158 p.parseHeaders(walker);
159 p.flags |= IN_PENDING;
160 pending.add(p);
161 }
162
163 int carry = c.flags & branchMask;
164 boolean mb = carry == branchMask;
165 if (mb) {
166 // If we are a merge base make sure our ancestors are
167 // also flagged as being popped, so that they do not
168 // generate to the caller.
169 //
170 carry |= MERGE_BASE | mergeBaseAncestor;
171 }
172 carryOntoHistory(c, carry);
173
174 if ((c.flags & MERGE_BASE) != 0) {
175 // This commit is an ancestor of a merge base we already
176 // popped back to the caller. If everyone in pending is
177 // that way we are done traversing; if not we just need
178 // to move to the next available commit and try again.
179 //
180 if (pending.everbodyHasFlag(MERGE_BASE))
181 return null;
182 continue;
183 }
184 c.flags |= POPPED;
185
186 if (mb) {
187 c.flags |= MERGE_BASE;
188 return c;
189 }
190 }
191 }
192
193 @Override
194 RevCommit next() throws MissingObjectException,
195 IncorrectObjectTypeException, IOException {
196 while (!ret.isEmpty()) {
197 RevCommit commit = ret.remove();
198 if ((commit.flags & mergeBaseAncestor) == 0) {
199 return commit;
200 }
201 }
202 return null;
203 }
204
205 private void carryOntoHistory(RevCommit c, final int carry) {
206 for (;;) {
207 final RevCommit[] pList = c.parents;
208 if (pList == null)
209 return;
210 final int n = pList.length;
211 if (n == 0)
212 return;
213
214 for (int i = 1; i < n; i++) {
215 final RevCommit p = pList[i];
216 if (!carryOntoOne(p, carry))
217 carryOntoHistory(p, carry);
218 }
219
220 c = pList[0];
221 if (carryOntoOne(c, carry))
222 break;
223 }
224 }
225
226 private boolean carryOntoOne(final RevCommit p, final int carry) {
227 final boolean haveAll = (p.flags & carry) == carry;
228 p.flags |= carry;
229
230 if ((p.flags & recarryMask) == recarryTest) {
231 // We were popped without being a merge base, but we just got
232 // voted to be one. Inject ourselves back at the front of the
233 // pending queue and tell all of our ancestors they are within
234 // the merge base now.
235 //
236 p.flags &= ~POPPED;
237 pending.add(p);
238 carryOntoHistory(p, branchMask | MERGE_BASE);
239 return true;
240 }
241
242 // If we already had all carried flags, our parents do too.
243 // Return true to stop the caller from running down this leg
244 // of the revision graph any further.
245 //
246 return haveAll;
247 }
248 }