1 /*
2 * Copyright (C) 2009, Google Inc.
3 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
4 * and other copyright owners as documented in the project's IP log.
5 *
6 * This program and the accompanying materials are made available
7 * under the terms of the Eclipse Distribution License v1.0 which
8 * accompanies this distribution, is reproduced below, and is
9 * available at http://www.eclipse.org/org/documents/edl-v10.php
10 *
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or
14 * without modification, are permitted provided that the following
15 * conditions are met:
16 *
17 * - Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials provided
23 * with the distribution.
24 *
25 * - Neither the name of the Eclipse Foundation, Inc. nor the
26 * names of its contributors may be used to endorse or promote
27 * products derived from this software without specific prior
28 * written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
31 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
32 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
35 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
36 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
37 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
38 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
39 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
42 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 */
44
45 package org.eclipse.jgit.revwalk;
46
47 import java.io.IOException;
48
49 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
50 import org.eclipse.jgit.errors.MissingObjectException;
51 import org.eclipse.jgit.errors.StopWalkException;
52 import org.eclipse.jgit.lib.ObjectId;
53 import org.eclipse.jgit.revwalk.filter.RevFilter;
54
55 /**
56 * Default (and first pass) RevCommit Generator implementation for RevWalk.
57 * <p>
58 * This generator starts from a set of one or more commits and process them in
59 * descending (newest to oldest) commit time order. Commits automatically cause
60 * their parents to be enqueued for further processing, allowing the entire
61 * commit graph to be walked. A {@link RevFilter} may be used to select a subset
62 * of the commits and return them to the caller.
63 */
64 class PendingGenerator extends Generator {
65 private static final int PARSED = RevWalk.PARSED;
66
67 private static final int SEEN = RevWalk.SEEN;
68
69 private static final int UNINTERESTING = RevWalk.UNINTERESTING;
70
71 /**
72 * Number of additional commits to scan after we think we are done.
73 * <p>
74 * This small buffer of commits is scanned to ensure we didn't miss anything
75 * as a result of clock skew when the commits were made. We need to set our
76 * constant to 1 additional commit due to the use of a pre-increment
77 * operator when accessing the value.
78 */
79 static final int OVER_SCAN = 5 + 1;
80
81 /** A commit near the end of time, to initialize {@link #last} with. */
82 private static final RevCommit INIT_LAST;
83
84 static {
85 INIT_LAST = new RevCommit(ObjectId.zeroId());
86 INIT_LAST.commitTime = Integer.MAX_VALUE;
87 }
88
89 private final RevWalk walker;
90
91 private final DateRevQueue pending;
92
93 private final RevFilter filter;
94
95 private final int output;
96
97 /** Last commit produced to the caller from {@link #next()}. */
98 private RevCommit last = INIT_LAST;
99
100 /**
101 * Number of commits we have remaining in our over-scan allotment.
102 * <p>
103 * Only relevant if there are {@link #UNINTERESTING} commits in the
104 * {@link #pending} queue.
105 */
106 private int overScan = OVER_SCAN;
107
108 boolean canDispose;
109
110 PendingGenerator(final RevWalk w, final DateRevQueue p,
111 final RevFilter f, final int out) {
112 walker = w;
113 pending = p;
114 filter = f;
115 output = out;
116 canDispose = true;
117 }
118
119 @Override
120 int outputType() {
121 return output | SORT_COMMIT_TIME_DESC;
122 }
123
124 @Override
125 RevCommit next() throws MissingObjectException,
126 IncorrectObjectTypeException, IOException {
127 try {
128 for (;;) {
129 final RevCommit c = pending.next();
130 if (c == null) {
131 return null;
132 }
133
134 final boolean produce;
135 if ((c.flags & UNINTERESTING) != 0)
136 produce = false;
137 else {
138 if (filter.requiresCommitBody())
139 c.parseBody(walker);
140 produce = filter.include(walker, c);
141 }
142
143 for (RevCommit p : c.parents) {
144 if ((p.flags & SEEN) != 0)
145 continue;
146 if ((p.flags & PARSED) == 0)
147 p.parseHeaders(walker);
148 p.flags |= SEEN;
149 pending.add(p);
150 }
151 walker.carryFlagsImpl(c);
152
153 if ((c.flags & UNINTERESTING) != 0) {
154 if (pending.everbodyHasFlag(UNINTERESTING)) {
155 final RevCommit n = pending.peek();
156 if (n != null && n.commitTime >= last.commitTime) {
157 // This is too close to call. The next commit we
158 // would pop is dated after the last one produced.
159 // We have to keep going to ensure that we carry
160 // flags as much as necessary.
161 //
162 overScan = OVER_SCAN;
163 } else if (--overScan == 0)
164 throw StopWalkException.INSTANCE;
165 } else {
166 overScan = OVER_SCAN;
167 }
168 if (canDispose)
169 c.disposeBody();
170 continue;
171 }
172
173 if (produce)
174 return last = c;
175 else if (canDispose)
176 c.disposeBody();
177 }
178 } catch (StopWalkException swe) {
179 pending.clear();
180 return null;
181 }
182 }
183 }