View Javadoc
1   /*
2    * Copyright (C) 2009, Google Inc.
3    * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> and others
4    *
5    * This program and the accompanying materials are made available under the
6    * terms of the Eclipse Distribution License v. 1.0 which is available at
7    * https://www.eclipse.org/org/documents/edl-v10.php.
8    *
9    * SPDX-License-Identifier: BSD-3-Clause
10   */
11  
12  package org.eclipse.jgit.revwalk;
13  
14  import java.io.IOException;
15  
16  import org.eclipse.jgit.errors.IncorrectObjectTypeException;
17  import org.eclipse.jgit.errors.MissingObjectException;
18  import org.eclipse.jgit.errors.StopWalkException;
19  import org.eclipse.jgit.lib.ObjectId;
20  import org.eclipse.jgit.revwalk.filter.RevFilter;
21  
22  /**
23   * Default (and first pass) RevCommit Generator implementation for RevWalk.
24   * <p>
25   * This generator starts from a set of one or more commits and process them in
26   * descending (newest to oldest) commit time order. Commits automatically cause
27   * their parents to be enqueued for further processing, allowing the entire
28   * commit graph to be walked. A {@link RevFilter} may be used to select a subset
29   * of the commits and return them to the caller.
30   */
31  class PendingGenerator extends Generator {
32  	private static final int PARSED = RevWalk.PARSED;
33  
34  	private static final int SEEN = RevWalk.SEEN;
35  
36  	private static final int UNINTERESTING = RevWalk.UNINTERESTING;
37  
38  	/**
39  	 * Number of additional commits to scan after we think we are done.
40  	 * <p>
41  	 * This small buffer of commits is scanned to ensure we didn't miss anything
42  	 * as a result of clock skew when the commits were made. We need to set our
43  	 * constant to 1 additional commit due to the use of a pre-increment
44  	 * operator when accessing the value.
45  	 */
46  	static final int OVER_SCAN = 5 + 1;
47  
48  	/** A commit near the end of time, to initialize {@link #last} with. */
49  	private static final RevCommit INIT_LAST;
50  
51  	static {
52  		INIT_LAST = new RevCommit(ObjectId.zeroId());
53  		INIT_LAST.commitTime = Integer.MAX_VALUE;
54  	}
55  
56  	private final RevWalk walker;
57  
58  	private final DateRevQueue pending;
59  
60  	private final RevFilter filter;
61  
62  	private final int output;
63  
64  	/** Last commit produced to the caller from {@link #next()}. */
65  	private RevCommit last = INIT_LAST;
66  
67  	/**
68  	 * Number of commits we have remaining in our over-scan allotment.
69  	 * <p>
70  	 * Only relevant if there are {@link #UNINTERESTING} commits in the
71  	 * {@link #pending} queue.
72  	 */
73  	private int overScan = OVER_SCAN;
74  
75  	boolean canDispose;
76  
77  	PendingGenerator(final RevWalk w, final DateRevQueue p,
78  			final RevFilter f, final int out) {
79  		super(w.isFirstParent());
80  		walker = w;
81  		pending = p;
82  		filter = f;
83  		output = out;
84  		canDispose = true;
85  	}
86  
87  	@Override
88  	int outputType() {
89  		return output | SORT_COMMIT_TIME_DESC;
90  	}
91  
92  	@Override
93  	RevCommit next() throws MissingObjectException,
94  			IncorrectObjectTypeException, IOException {
95  		try {
96  			for (;;) {
97  				final RevCommit c = pending.next();
98  				if (c == null) {
99  					return null;
100 				}
101 
102 				final boolean produce;
103 				if ((c.flags & UNINTERESTING) != 0)
104 					produce = false;
105 				else {
106 					if (filter.requiresCommitBody())
107 						c.parseBody(walker);
108 					produce = filter.include(walker, c);
109 				}
110 
111 				for (int i = 0; i < c.parents.length; i++) {
112 					RevCommit p = c.parents[i];
113 					// If the commit is uninteresting, don't try to prune
114 					// parents because we want the maximal uninteresting set.
115 					if (firstParent && i > 0 && (c.flags & UNINTERESTING) == 0) {
116 						continue;
117 					}
118 					if ((p.flags & SEEN) != 0)
119 						continue;
120 					if ((p.flags & PARSED) == 0)
121 						p.parseHeaders(walker);
122 					p.flags |= SEEN;
123 					pending.add(p);
124 				}
125 				walker.carryFlagsImpl(c);
126 
127 				if ((c.flags & UNINTERESTING) != 0) {
128 					if (pending.everbodyHasFlag(UNINTERESTING)) {
129 						final RevCommit n = pending.peek();
130 						if (n != null && n.commitTime >= last.commitTime) {
131 							// This is too close to call. The next commit we
132 							// would pop is dated after the last one produced.
133 							// We have to keep going to ensure that we carry
134 							// flags as much as necessary.
135 							//
136 							overScan = OVER_SCAN;
137 						} else if (--overScan == 0)
138 							throw StopWalkException.INSTANCE;
139 					} else {
140 						overScan = OVER_SCAN;
141 					}
142 					if (canDispose)
143 						c.disposeBody();
144 					continue;
145 				}
146 
147 				if (produce)
148 					return last = c;
149 				else if (canDispose)
150 					c.disposeBody();
151 			}
152 		} catch (StopWalkException swe) {
153 			pending.clear();
154 			return null;
155 		}
156 	}
157 }