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 private static final int IN_PENDING = RevWalk.SEEN;
73 private static final int POPPED = RevWalk.TEMP_MARK;
74 private static final int MERGE_BASE = RevWalk.REWRITE;
75
76 private final RevWalk walker;
77 private final DateRevQueue pending;
78
79 private int branchMask;
80 private int recarryTest;
81 private int recarryMask;
82 private int mergeBaseAncestor = -1;
83 private LinkedList<RevCommit> ret = new LinkedList<>();
84
85 private CarryStack stack;
86
87 MergeBaseGenerator(RevWalk w) {
88 walker = w;
89 pending = new DateRevQueue();
90 }
91
92 void init(AbstractRevQueue p) throws IOException {
93 try {
94 for (;;) {
95 final RevCommit c = p.next();
96 if (c == null)
97 break;
98 add(c);
99 }
100 // Setup the condition used by carryOntoOne to detect a late
101 // merge base and produce it on the next round.
102 //
103 recarryTest = branchMask | POPPED;
104 recarryMask = branchMask | POPPED | MERGE_BASE;
105 mergeBaseAncestor = walker.allocFlag();
106
107 for (;;) {
108 RevCommit c = _next();
109 if (c == null) {
110 break;
111 }
112 ret.add(c);
113 }
114 } finally {
115 // Always free the flags immediately. This ensures the flags
116 // will be available for reuse when the walk resets.
117 //
118 walker.freeFlag(branchMask | mergeBaseAncestor);
119 }
120 }
121
122 private void add(RevCommit c) {
123 final int flag = walker.allocFlag();
124 branchMask |= flag;
125 if ((c.flags & branchMask) != 0) {
126 // This should never happen. RevWalk ensures we get a
127 // commit admitted to the initial queue only once. If
128 // we see this marks aren't correctly erased.
129 //
130 throw new IllegalStateException(MessageFormat.format(JGitText.get().staleRevFlagsOn, c.name()));
131 }
132 c.flags |= flag;
133 pending.add(c);
134 }
135
136 @Override
137 int outputType() {
138 return 0;
139 }
140
141 private RevCommit _next() throws MissingObjectException,
142 IncorrectObjectTypeException, IOException {
143 for (;;) {
144 final RevCommit c = pending.next();
145 if (c == null) {
146 return null;
147 }
148
149 for (RevCommit p : c.parents) {
150 if ((p.flags & IN_PENDING) != 0)
151 continue;
152 if ((p.flags & PARSED) == 0)
153 p.parseHeaders(walker);
154 p.flags |= IN_PENDING;
155 pending.add(p);
156 }
157
158 int carry = c.flags & branchMask;
159 boolean mb = carry == branchMask;
160 if (mb) {
161 // If we are a merge base make sure our ancestors are
162 // also flagged as being popped, so that they do not
163 // generate to the caller.
164 //
165 carry |= MERGE_BASE | mergeBaseAncestor;
166 }
167 carryOntoHistory(c, carry);
168
169 if ((c.flags & MERGE_BASE) != 0) {
170 // This commit is an ancestor of a merge base we already
171 // popped back to the caller. If everyone in pending is
172 // that way we are done traversing; if not we just need
173 // to move to the next available commit and try again.
174 //
175 if (pending.everbodyHasFlag(MERGE_BASE))
176 return null;
177 continue;
178 }
179 c.flags |= POPPED;
180
181 if (mb) {
182 c.flags |= MERGE_BASE;
183 return c;
184 }
185 }
186 }
187
188 @Override
189 RevCommit next() throws MissingObjectException,
190 IncorrectObjectTypeException, IOException {
191 while (!ret.isEmpty()) {
192 RevCommit commit = ret.remove();
193 if ((commit.flags & mergeBaseAncestor) == 0) {
194 return commit;
195 }
196 }
197 return null;
198 }
199
200 private void carryOntoHistory(RevCommit c, int carry) {
201 stack = null;
202 for (;;) {
203 carryOntoHistoryInnerLoop(c, carry);
204 if (stack == null) {
205 break;
206 }
207 c = stack.c;
208 carry = stack.carry;
209 stack = stack.prev;
210 }
211 }
212
213 private void carryOntoHistoryInnerLoop(RevCommit c, int carry) {
214 for (;;) {
215 RevCommit[] parents = c.parents;
216 if (parents == null || parents.length == 0) {
217 break;
218 }
219
220 int e = parents.length - 1;
221 for (int i = 0; i < e; i++) {
222 RevCommit p = parents[i];
223 if (carryOntoOne(p, carry) == CONTINUE) {
224 // Walking p will be required, buffer p on stack.
225 stack = new CarryStack(stack, p, carry);
226 }
227 // For other results from carryOntoOne:
228 // HAVE_ALL: p has all bits, do nothing to skip that path.
229 // CONTINUE_ON_STACK: callee pushed StackElement for p.
230 }
231
232 c = parents[e];
233 if (carryOntoOne(c, carry) != CONTINUE) {
234 break;
235 }
236 }
237 }
238
239 private static final int CONTINUE = 0;
240 private static final int HAVE_ALL = 1;
241 private static final int CONTINUE_ON_STACK = 2;
242
243 private int carryOntoOne(RevCommit p, int carry) {
244 // If we already had all carried flags, our parents do too.
245 // Return HAVE_ALL to stop caller from running down this leg
246 // of the revision graph any further.
247 //
248 // Otherwise return CONTINUE to ask the caller to walk history.
249 int rc = (p.flags & carry) == carry ? HAVE_ALL : CONTINUE;
250 p.flags |= carry;
251
252 if ((p.flags & recarryMask) == recarryTest) {
253 // We were popped without being a merge base, but we just got
254 // voted to be one. Inject ourselves back at the front of the
255 // pending queue and tell all of our ancestors they are within
256 // the merge base now.
257 p.flags &= ~POPPED;
258 pending.add(p);
259 stack = new CarryStack(stack, p, branchMask | MERGE_BASE);
260 return CONTINUE_ON_STACK;
261 }
262 return rc;
263 }
264
265 private static class CarryStack {
266 final CarryStack prev;
267 final RevCommit c;
268 final int carry;
269
270 CarryStack(CarryStack prev, RevCommit c, int carry) {
271 this.prev = prev;
272 this.c = c;
273 this.carry = carry;
274 }
275 }
276 }