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
49 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
50 import org.eclipse.jgit.errors.MissingObjectException;
51 import org.eclipse.jgit.internal.JGitText;
52
53 /**
54 * Computes the merge base(s) of the starting commits.
55 * <p>
56 * This generator is selected if the RevFilter is only
57 * {@link org.eclipse.jgit.revwalk.filter.RevFilter#MERGE_BASE}.
58 * <p>
59 * To compute the merge base we assign a temporary flag to each of the starting
60 * commits. The maximum number of starting commits is bounded by the number of
61 * free flags available in the RevWalk when the generator is initialized. These
62 * flags will be automatically released on the next reset of the RevWalk, but
63 * not until then, as they are assigned to commits throughout the history.
64 * <p>
65 * Several internal flags are reused here for a different purpose, but this
66 * should not have any impact as this generator should be run alone, and without
67 * any other generators wrapped around it.
68 */
69 class MergeBaseGenerator extends Generator {
70 private static final int PARSED = RevWalk.PARSED;
71
72 private static final int IN_PENDING = RevWalk.SEEN;
73
74 private static final int POPPED = RevWalk.TEMP_MARK;
75
76 private static final int MERGE_BASE = RevWalk.REWRITE;
77
78 private final RevWalk walker;
79
80 private final DateRevQueue pending;
81
82 private int branchMask;
83
84 private int recarryTest;
85
86 private int recarryMask;
87
88 MergeBaseGenerator(final RevWalk w) {
89 walker = w;
90 pending = new DateRevQueue();
91 }
92
93 void init(final AbstractRevQueue p) {
94 try {
95 for (;;) {
96 final RevCommit c = p.next();
97 if (c == null)
98 break;
99 add(c);
100 }
101 } finally {
102 // Always free the flags immediately. This ensures the flags
103 // will be available for reuse when the walk resets.
104 //
105 walker.freeFlag(branchMask);
106
107 // Setup the condition used by carryOntoOne to detect a late
108 // merge base and produce it on the next round.
109 //
110 recarryTest = branchMask | POPPED;
111 recarryMask = branchMask | POPPED | MERGE_BASE;
112 }
113 }
114
115 private void add(final RevCommit c) {
116 final int flag = walker.allocFlag();
117 branchMask |= flag;
118 if ((c.flags & branchMask) != 0) {
119 // This should never happen. RevWalk ensures we get a
120 // commit admitted to the initial queue only once. If
121 // we see this marks aren't correctly erased.
122 //
123 throw new IllegalStateException(MessageFormat.format(JGitText.get().staleRevFlagsOn, c.name()));
124 }
125 c.flags |= flag;
126 pending.add(c);
127 }
128
129 @Override
130 int outputType() {
131 return 0;
132 }
133
134 @Override
135 RevCommit next() throws MissingObjectException,
136 IncorrectObjectTypeException, IOException {
137 for (;;) {
138 final RevCommit c = pending.next();
139 if (c == null) {
140 return null;
141 }
142
143 for (final RevCommit p : c.parents) {
144 if ((p.flags & IN_PENDING) != 0)
145 continue;
146 if ((p.flags & PARSED) == 0)
147 p.parseHeaders(walker);
148 p.flags |= IN_PENDING;
149 pending.add(p);
150 }
151
152 int carry = c.flags & branchMask;
153 boolean mb = carry == branchMask;
154 if (mb) {
155 // If we are a merge base make sure our ancestors are
156 // also flagged as being popped, so that they do not
157 // generate to the caller.
158 //
159 carry |= MERGE_BASE;
160 }
161 carryOntoHistory(c, carry);
162
163 if ((c.flags & MERGE_BASE) != 0) {
164 // This commit is an ancestor of a merge base we already
165 // popped back to the caller. If everyone in pending is
166 // that way we are done traversing; if not we just need
167 // to move to the next available commit and try again.
168 //
169 if (pending.everbodyHasFlag(MERGE_BASE))
170 return null;
171 continue;
172 }
173 c.flags |= POPPED;
174
175 if (mb) {
176 c.flags |= MERGE_BASE;
177 return c;
178 }
179 }
180 }
181
182 private void carryOntoHistory(RevCommit c, final int carry) {
183 for (;;) {
184 final RevCommit[] pList = c.parents;
185 if (pList == null)
186 return;
187 final int n = pList.length;
188 if (n == 0)
189 return;
190
191 for (int i = 1; i < n; i++) {
192 final RevCommit p = pList[i];
193 if (!carryOntoOne(p, carry))
194 carryOntoHistory(p, carry);
195 }
196
197 c = pList[0];
198 if (carryOntoOne(c, carry))
199 break;
200 }
201 }
202
203 private boolean carryOntoOne(final RevCommit p, final int carry) {
204 final boolean haveAll = (p.flags & carry) == carry;
205 p.flags |= carry;
206
207 if ((p.flags & recarryMask) == recarryTest) {
208 // We were popped without being a merge base, but we just got
209 // voted to be one. Inject ourselves back at the front of the
210 // pending queue and tell all of our ancestors they are within
211 // the merge base now.
212 //
213 p.flags &= ~POPPED;
214 pending.add(p);
215 carryOntoHistory(p, branchMask | MERGE_BASE);
216 return true;
217 }
218
219 // If we already had all carried flags, our parents do too.
220 // Return true to stop the caller from running down this leg
221 // of the revision graph any further.
222 //
223 return haveAll;
224 }
225 }