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