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
48 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
49 import org.eclipse.jgit.errors.MissingObjectException;
50 import org.eclipse.jgit.revwalk.filter.RevFilter;
51
52 /**
53 * An ordered list of {@link org.eclipse.jgit.revwalk.RevCommit} subclasses.
54 *
55 * @param <E>
56 * type of subclass of RevCommit the list is storing.
57 */
58 public class RevCommitList<E extends RevCommit> extends RevObjectList<E> {
59 private RevWalk walker;
60
61 /** {@inheritDoc} */
62 @Override
63 public void clear() {
64 super.clear();
65 walker = null;
66 }
67
68 /**
69 * Apply a flag to all commits matching the specified filter.
70 * <p>
71 * Same as <code>applyFlag(matching, flag, 0, size())</code>, but without
72 * the incremental behavior.
73 *
74 * @param matching
75 * the filter to test commits with. If the filter includes a
76 * commit it will have the flag set; if the filter does not
77 * include the commit the flag will be unset.
78 * @param flag
79 * the flag to apply (or remove). Applications are responsible
80 * for allocating this flag from the source RevWalk.
81 * @throws java.io.IOException
82 * revision filter needed to read additional objects, but an
83 * error occurred while reading the pack files or loose objects
84 * of the repository.
85 * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
86 * revision filter needed to read additional objects, but an
87 * object was not of the correct type. Repository corruption may
88 * have occurred.
89 * @throws org.eclipse.jgit.errors.MissingObjectException
90 * revision filter needed to read additional objects, but an
91 * object that should be present was not found. Repository
92 * corruption may have occurred.
93 */
94 public void applyFlag(RevFilter matching, RevFlag flag)
95 throws MissingObjectException, IncorrectObjectTypeException,
96 IOException {
97 applyFlag(matching, flag, 0, size());
98 }
99
100 /**
101 * Apply a flag to all commits matching the specified filter.
102 * <p>
103 * This version allows incremental testing and application, such as from a
104 * background thread that needs to periodically halt processing and send
105 * updates to the UI.
106 *
107 * @param matching
108 * the filter to test commits with. If the filter includes a
109 * commit it will have the flag set; if the filter does not
110 * include the commit the flag will be unset.
111 * @param flag
112 * the flag to apply (or remove). Applications are responsible
113 * for allocating this flag from the source RevWalk.
114 * @param rangeBegin
115 * first commit within the list to begin testing at, inclusive.
116 * Must not be negative, but may be beyond the end of the list.
117 * @param rangeEnd
118 * last commit within the list to end testing at, exclusive. If
119 * smaller than or equal to <code>rangeBegin</code> then no
120 * commits will be tested.
121 * @throws java.io.IOException
122 * revision filter needed to read additional objects, but an
123 * error occurred while reading the pack files or loose objects
124 * of the repository.
125 * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
126 * revision filter needed to read additional objects, but an
127 * object was not of the correct type. Repository corruption may
128 * have occurred.
129 * @throws org.eclipse.jgit.errors.MissingObjectException
130 * revision filter needed to read additional objects, but an
131 * object that should be present was not found. Repository
132 * corruption may have occurred.
133 */
134 public void applyFlag(final RevFilter matching, final RevFlag flag,
135 int rangeBegin, int rangeEnd) throws MissingObjectException,
136 IncorrectObjectTypeException, IOException {
137 final RevWalk w = flag.getRevWalk();
138 rangeEnd = Math.min(rangeEnd, size());
139 while (rangeBegin < rangeEnd) {
140 int index = rangeBegin;
141 Block s = contents;
142 while (s.shift > 0) {
143 final int i = index >> s.shift;
144 index -= i << s.shift;
145 s = (Block) s.contents[i];
146 }
147
148 while (rangeBegin++ < rangeEnd && index < BLOCK_SIZE) {
149 final RevCommit="../../../../org/eclipse/jgit/revwalk/RevCommit.html#RevCommit">RevCommit c = (RevCommit) s.contents[index++];
150 if (matching.include(w, c))
151 c.add(flag);
152 else
153 c.remove(flag);
154 }
155 }
156 }
157
158 /**
159 * Remove the given flag from all commits.
160 * <p>
161 * Same as <code>clearFlag(flag, 0, size())</code>, but without the
162 * incremental behavior.
163 *
164 * @param flag
165 * the flag to remove. Applications are responsible for
166 * allocating this flag from the source RevWalk.
167 */
168 public void clearFlag(RevFlag flag) {
169 clearFlag(flag, 0, size());
170 }
171
172 /**
173 * Remove the given flag from all commits.
174 * <p>
175 * This method is actually implemented in terms of:
176 * <code>applyFlag(RevFilter.NONE, flag, rangeBegin, rangeEnd)</code>.
177 *
178 * @param flag
179 * the flag to remove. Applications are responsible for
180 * allocating this flag from the source RevWalk.
181 * @param rangeBegin
182 * first commit within the list to begin testing at, inclusive.
183 * Must not be negative, but may be beyond the end of the list.
184 * @param rangeEnd
185 * last commit within the list to end testing at, exclusive. If
186 * smaller than or equal to <code>rangeBegin</code> then no
187 * commits will be tested.
188 */
189 public void clearFlag(final RevFlag flag, final int rangeBegin,
190 final int rangeEnd) {
191 try {
192 applyFlag(RevFilter.NONE, flag, rangeBegin, rangeEnd);
193 } catch (IOException e) {
194 // Never happen. The filter we use does not throw any
195 // exceptions, for any reason.
196 }
197 }
198
199 /**
200 * Find the next commit that has the given flag set.
201 *
202 * @param flag
203 * the flag to test commits against.
204 * @param begin
205 * first commit index to test at. Applications may wish to begin
206 * at 0, to test the first commit in the list.
207 * @return index of the first commit at or after index <code>begin</code>
208 * that has the specified flag set on it; -1 if no match is found.
209 */
210 public int indexOf(RevFlag flag, int begin) {
211 while (begin < size()) {
212 int index = begin;
213 Block s = contents;
214 while (s.shift > 0) {
215 final int i = index >> s.shift;
216 index -= i << s.shift;
217 s = (Block) s.contents[i];
218 }
219
220 while (begin++ < size() && index < BLOCK_SIZE) {
221 final RevCommit="../../../../org/eclipse/jgit/revwalk/RevCommit.html#RevCommit">RevCommit c = (RevCommit) s.contents[index++];
222 if (c.has(flag))
223 return begin;
224 }
225 }
226 return -1;
227 }
228
229 /**
230 * Find the next commit that has the given flag set.
231 *
232 * @param flag
233 * the flag to test commits against.
234 * @param begin
235 * first commit index to test at. Applications may wish to begin
236 * at <code>size()-1</code>, to test the last commit in the
237 * list.
238 * @return index of the first commit at or before index <code>begin</code>
239 * that has the specified flag set on it; -1 if no match is found.
240 */
241 public int lastIndexOf(RevFlag flag, int begin) {
242 begin = Math.min(begin, size() - 1);
243 while (begin >= 0) {
244 int index = begin;
245 Block s = contents;
246 while (s.shift > 0) {
247 final int i = index >> s.shift;
248 index -= i << s.shift;
249 s = (Block) s.contents[i];
250 }
251
252 while (begin-- >= 0 && index >= 0) {
253 final RevCommit="../../../../org/eclipse/jgit/revwalk/RevCommit.html#RevCommit">RevCommit c = (RevCommit) s.contents[index--];
254 if (c.has(flag))
255 return begin;
256 }
257 }
258 return -1;
259 }
260
261 /**
262 * Set the revision walker this list populates itself from.
263 *
264 * @param w
265 * the walker to populate from.
266 * @see #fillTo(int)
267 */
268 public void source(RevWalk w) {
269 walker = w;
270 }
271
272 /**
273 * Is this list still pending more items?
274 *
275 * @return true if {@link #fillTo(int)} might be able to extend the list
276 * size when called.
277 */
278 public boolean isPending() {
279 return walker != null;
280 }
281
282 /**
283 * Ensure this list contains at least a specified number of commits.
284 * <p>
285 * The revision walker specified by {@link #source(RevWalk)} is pumped until
286 * the given number of commits are contained in this list. If there are
287 * fewer total commits available from the walk then the method will return
288 * early. Callers can test the final size of the list by {@link #size()} to
289 * determine if the high water mark specified was met.
290 *
291 * @param highMark
292 * number of commits the caller wants this list to contain when
293 * the fill operation is complete.
294 * @throws java.io.IOException
295 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
296 * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
297 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
298 * @throws org.eclipse.jgit.errors.MissingObjectException
299 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
300 */
301 @SuppressWarnings("unchecked")
302 public void fillTo(int highMark) throws MissingObjectException,
303 IncorrectObjectTypeException, IOException {
304 if (walker == null || size > highMark)
305 return;
306
307 RevCommit c = walker.next();
308 if (c == null) {
309 walker = null;
310 return;
311 }
312 enter(size, (E) c);
313 add((E) c);
314
315 while (size <= highMark) {
316 int index = size;
317 Block s = contents;
318 while (index >> s.shift >= BLOCK_SIZE) {
319 s = new Block(s.shift + BLOCK_SHIFT);
320 s.contents[0] = contents;
321 contents = s;
322 }
323 while (s.shift > 0) {
324 final int i = index >> s.shift;
325 index -= i << s.shift;
326 if (s.contents[i] == null)
327 s.contents[i] = new Block(s.shift - BLOCK_SHIFT);
328 s = (Block) s.contents[i];
329 }
330
331 final Object[] dst = s.contents;
332 while (size <= highMark && index < BLOCK_SIZE) {
333 c = walker.next();
334 if (c == null) {
335 walker = null;
336 return;
337 }
338 enter(size++, (E) c);
339 dst[index++] = c;
340 }
341 }
342 }
343
344 /**
345 * Ensures all commits until the given commit are loaded. The revision
346 * walker specified by {@link #source(RevWalk)} is pumped until the
347 * specified commit is loaded. Callers can test the final size of the list
348 * by {@link #size()} to determine if the high water mark specified was met.
349 * <p>
350 *
351 * @param commitToLoad
352 * commit the caller wants this list to contain when the fill
353 * operation is complete.
354 * @param highMark
355 * maximum number of commits the caller wants this list to
356 * contain when the fill operation is complete. If highMark is 0
357 * the walk is pumped until the specified commit or the end of
358 * the walk is reached.
359 * @throws java.io.IOException
360 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
361 * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
362 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
363 * @throws org.eclipse.jgit.errors.MissingObjectException
364 * see {@link org.eclipse.jgit.revwalk.RevWalk#next()}
365 */
366 @SuppressWarnings("unchecked")
367 public void fillTo(RevCommit commitToLoad, int highMark)
368 throws MissingObjectException, IncorrectObjectTypeException,
369 IOException {
370 if (walker == null || commitToLoad == null
371 || (highMark > 0 && size > highMark))
372 return;
373
374 RevCommit c = walker.next();
375 if (c == null) {
376 walker = null;
377 return;
378 }
379 enter(size, (E) c);
380 add((E) c);
381
382 while ((highMark == 0 || size <= highMark) && !c.equals(commitToLoad)) {
383 int index = size;
384 Block s = contents;
385 while (index >> s.shift >= BLOCK_SIZE) {
386 s = new Block(s.shift + BLOCK_SHIFT);
387 s.contents[0] = contents;
388 contents = s;
389 }
390 while (s.shift > 0) {
391 final int i = index >> s.shift;
392 index -= i << s.shift;
393 if (s.contents[i] == null)
394 s.contents[i] = new Block(s.shift - BLOCK_SHIFT);
395 s = (Block) s.contents[i];
396 }
397
398 final Object[] dst = s.contents;
399 while ((highMark == 0 || size <= highMark) && index < BLOCK_SIZE
400 && !c.equals(commitToLoad)) {
401 c = walker.next();
402 if (c == null) {
403 walker = null;
404 return;
405 }
406 enter(size++, (E) c);
407 dst[index++] = c;
408 }
409 }
410 }
411
412 /**
413 * Optional callback invoked when commits enter the list by fillTo.
414 * <p>
415 * This method is only called during {@link #fillTo(int)}.
416 *
417 * @param index
418 * the list position this object will appear at.
419 * @param e
420 * the object being added (or set) into the list.
421 */
422 protected void enter(int index, E e) {
423 // Do nothing by default.
424 }
425 }