View Javadoc
1   /*
2    * Copyright (C) 2019, Google LLC. and others
3    *
4    * This program and the accompanying materials are made available under the
5    * terms of the Eclipse Distribution License v. 1.0 which is available at
6    * https://www.eclipse.org/org/documents/edl-v10.php.
7    *
8    * SPDX-License-Identifier: BSD-3-Clause
9    */
10  
11  package org.eclipse.jgit.revwalk;
12  
13  import static org.junit.Assert.assertEquals;
14  import static org.junit.Assert.assertNull;
15  
16  import org.eclipse.jgit.lib.ObjectId;
17  import org.eclipse.jgit.revwalk.filter.MessageRevFilter;
18  import org.eclipse.jgit.revwalk.filter.RevFilter;
19  import org.eclipse.jgit.treewalk.filter.PathFilterGroup;
20  import org.junit.Test;
21  
22  public class FirstParentRevWalkTest extends RevWalkTestCase {
23  	@Test
24  	public void testStringOfPearls() throws Exception {
25  		RevCommit a = commit();
26  		RevCommit b = commit(a);
27  		RevCommit c = commit(b);
28  
29  		rw.reset();
30  		rw.setFirstParent(true);
31  		markStart(c);
32  		assertCommit(c, rw.next());
33  		assertCommit(b, rw.next());
34  		assertCommit(a, rw.next());
35  		assertNull(rw.next());
36  	}
37  
38  	@Test
39  	public void testSideBranch() throws Exception {
40  		RevCommit a = commit();
41  		RevCommit b1 = commit(a);
42  		RevCommit b2 = commit(a);
43  		RevCommit c1 = commit(b1);
44  		RevCommit c2 = commit(b2);
45  		RevCommit d = commit(c1, c2);
46  
47  		rw.reset();
48  		rw.setFirstParent(true);
49  		markStart(d);
50  		assertCommit(d, rw.next());
51  		assertCommit(c1, rw.next());
52  		assertCommit(b1, rw.next());
53  		assertCommit(a, rw.next());
54  		assertNull(rw.next());
55  	}
56  
57  	@Test
58  	public void testSecondParentAncestorOfFirstParent() throws Exception {
59  		RevCommit a = commit();
60  		RevCommit b = commit(a);
61  		RevCommit c = commit(b, a);
62  
63  		rw.reset();
64  		rw.setFirstParent(true);
65  		markStart(c);
66  		assertCommit(c, rw.next());
67  		assertCommit(b, rw.next());
68  		assertCommit(a, rw.next());
69  		assertNull(rw.next());
70  	}
71  
72  	@Test
73  	public void testFirstParentMultipleOccurrences() throws Exception {
74  		RevCommit a = commit();
75  		RevCommit b = commit(a);
76  		RevCommit c = commit(b);
77  		RevCommit d = commit(b);
78  
79  		rw.reset();
80  		rw.setFirstParent(true);
81  		markStart(c);
82  		markStart(d);
83  		assertCommit(d, rw.next());
84  		assertCommit(c, rw.next());
85  		assertCommit(b, rw.next());
86  		assertCommit(a, rw.next());
87  		assertNull(rw.next());
88  	}
89  
90  	@Test
91  	public void testReachableAlongFirstAndLaterParents() throws Exception {
92  		RevCommit a = commit();
93  		RevCommit b1 = commit(a);
94  		RevCommit b2 = commit(a);
95  		RevCommit b3 = commit(a);
96  		RevCommit c = commit(b1, b2);
97  		RevCommit d = commit(b2, b3);
98  
99  		rw.reset();
100 		rw.setFirstParent(true);
101 		markStart(c);
102 		markStart(d);
103 		assertCommit(d, rw.next());
104 		assertCommit(c, rw.next());
105 		// b3 is only reachable from c's second parent.
106 		// b2 is reachable from c's second parent but d's first parent.
107 		assertCommit(b2, rw.next());
108 		assertCommit(b1, rw.next());
109 		assertCommit(a, rw.next());
110 		assertNull(rw.next());
111 	}
112 
113 	@Test
114 	public void testStartCommitReachableOnlyFromLaterParents()
115 			throws Exception {
116 		RevCommit a = commit();
117 		RevCommit b1 = commit(a);
118 		RevCommit b2 = commit(a);
119 		RevCommit c = commit(b1, b2);
120 
121 		rw.reset();
122 		rw.setFirstParent(true);
123 		markStart(c);
124 		markStart(b2);
125 		assertCommit(c, rw.next());
126 		// b2 is only reachable from second parent, but is itself a start
127 		// commit.
128 		assertCommit(b2, rw.next());
129 		assertCommit(b1, rw.next());
130 		assertCommit(a, rw.next());
131 		assertNull(rw.next());
132 	}
133 
134 	@Test
135 	public void testRevFilter() throws Exception {
136 		RevCommit a = commit();
137 		RevCommit b1 = commitBuilder().parent(a).message("commit b1").create();
138 		RevCommit b2 = commitBuilder().parent(a).message("commit b2").create();
139 		RevCommit c = commit(b1, b2);
140 
141 		rw.reset();
142 		rw.setFirstParent(true);
143 		rw.setRevFilter(MessageRevFilter.create("commit b"));
144 		rw.markStart(c);
145 		assertCommit(b1, rw.next());
146 		assertNull(rw.next());
147 	}
148 
149 	@Test
150 	public void testTopoSort() throws Exception {
151 		RevCommit a = commit();
152 		RevCommit b1 = commit(a);
153 		RevCommit b2 = commit(a);
154 		RevCommit c = commit(b1, b2);
155 
156 		rw.reset();
157 		rw.sort(RevSort.TOPO);
158 		rw.setFirstParent(true);
159 		markStart(c);
160 		assertCommit(c, rw.next());
161 		assertCommit(b1, rw.next());
162 		assertCommit(a, rw.next());
163 		assertNull(rw.next());
164 	}
165 
166 	@Test
167 	public void testTopoNonIntermixSort() throws Exception {
168 		RevCommit a = commit();
169 		RevCommit b1 = commit(a);
170 		RevCommit b2 = commit(a);
171 		RevCommit c = commit(b1, b2);
172 
173 		rw.reset();
174 		rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
175 		rw.setFirstParent(true);
176 		markStart(c);
177 		assertCommit(c, rw.next());
178 		assertCommit(b1, rw.next());
179 		assertCommit(a, rw.next());
180 		assertNull(rw.next());
181 	}
182 
183 	@Test
184 	public void testCommitTimeSort() throws Exception {
185 		RevCommit a = commit();
186 		RevCommit b1 = commit(a);
187 		RevCommit b2 = commit(a);
188 		RevCommit c = commit(b1, b2);
189 
190 		rw.reset();
191 		rw.sort(RevSort.COMMIT_TIME_DESC);
192 		rw.setFirstParent(true);
193 		markStart(c);
194 		assertCommit(c, rw.next());
195 		assertCommit(b1, rw.next());
196 		assertCommit(a, rw.next());
197 		assertNull(rw.next());
198 	}
199 
200 	@Test
201 	public void testReverseSort() throws Exception {
202 		RevCommit a = commit();
203 		RevCommit b1 = commit(a);
204 		RevCommit b2 = commit(a);
205 		RevCommit c = commit(b1, b2);
206 
207 		rw.reset();
208 		rw.sort(RevSort.REVERSE);
209 		rw.setFirstParent(true);
210 		markStart(c);
211 		assertCommit(a, rw.next());
212 		assertCommit(b1, rw.next());
213 		assertCommit(c, rw.next());
214 		assertNull(rw.next());
215 	}
216 
217 	@Test
218 	public void testBoundarySort() throws Exception {
219 		RevCommit a = commit();
220 		RevCommit b = commit(a);
221 		RevCommit c1 = commit(b);
222 		RevCommit c2 = commit(b);
223 		RevCommit d = commit(c1, c2);
224 
225 		rw.reset();
226 		rw.sort(RevSort.BOUNDARY);
227 		rw.setFirstParent(true);
228 		markStart(d);
229 		markUninteresting(a);
230 		assertCommit(d, rw.next());
231 		assertCommit(c1, rw.next());
232 		assertCommit(b, rw.next());
233 		assertCommit(a, rw.next());
234 		assertNull(rw.next());
235 	}
236 
237 	@Test
238 	public void testFirstParentOfFirstParentMarkedUninteresting()
239 			throws Exception {
240 		RevCommit a = commit();
241 		RevCommit b1 = commit(a);
242 		RevCommit b2 = commit(a);
243 		RevCommit c1 = commit(b1);
244 		RevCommit c2 = commit(b2);
245 		RevCommit d = commit(c1, c2);
246 
247 		rw.reset();
248 		rw.setFirstParent(true);
249 		markStart(d);
250 		markUninteresting(b1);
251 		assertCommit(d, rw.next());
252 		assertCommit(c1, rw.next());
253 		assertNull(rw.next());
254 	}
255 
256 	@Test
257 	public void testUnparsedFirstParentOfFirstParentMarkedUninteresting()
258 			throws Exception {
259 		ObjectId a = unparsedCommit();
260 		ObjectId b1 = unparsedCommit(a);
261 		ObjectId b2 = unparsedCommit(a);
262 		ObjectId c1 = unparsedCommit(b1);
263 		ObjectId c2 = unparsedCommit(b2);
264 		ObjectId d = unparsedCommit(c1, c2);
265 
266 		rw.reset();
267 		rw.setFirstParent(true);
268 		RevCommit parsedD = rw.parseCommit(d);
269 		markStart(parsedD);
270 		markUninteresting(rw.parseCommit(b1));
271 		assertCommit(parsedD, rw.next());
272 		assertCommit(rw.parseCommit(c1), rw.next());
273 		assertNull(rw.next());
274 	}
275 
276 	@Test
277 	public void testFirstParentMarkedUninteresting() throws Exception {
278 		RevCommit a = commit();
279 		RevCommit b1 = commit(a);
280 		RevCommit b2 = commit(a);
281 		RevCommit c = commit(b1, b2);
282 
283 		rw.reset();
284 		rw.setFirstParent(true);
285 		markStart(c);
286 		markUninteresting(b1);
287 		assertCommit(c, rw.next());
288 		assertNull(rw.next());
289 	}
290 
291 	@Test
292 	public void testUnparsedFirstParentMarkedUninteresting() throws Exception {
293 		ObjectId a = unparsedCommit();
294 		ObjectId b1 = unparsedCommit(a);
295 		ObjectId b2 = unparsedCommit(a);
296 		ObjectId c = unparsedCommit(b1, b2);
297 
298 		rw.reset();
299 		rw.setFirstParent(true);
300 		RevCommit parsedC = rw.parseCommit(c);
301 		markStart(parsedC);
302 		markUninteresting(rw.parseCommit(b1));
303 		assertCommit(parsedC, rw.next());
304 		assertNull(rw.next());
305 	}
306 
307 	@Test
308 	public void testUninterestingCommitWithTwoParents() throws Exception {
309 		RevCommit a = commit();
310 		RevCommit b = commit(a);
311 		RevCommit c1 = commit(b);
312 		RevCommit c2 = commit(b);
313 		RevCommit d = commit(c1);
314 		RevCommit e = commit(c1, c2);
315 
316 		RevCommit uA = commit(a, b);
317 		RevCommit uB1 = commit(uA, c2);
318 		RevCommit uB2 = commit(uA, d);
319 		RevCommit uninteresting = commit(uB1, uB2);
320 
321 		rw.reset();
322 		rw.setFirstParent(true);
323 		markStart(e);
324 		markUninteresting(uninteresting);
325 
326 		assertCommit(e, rw.next());
327 		assertNull(rw.next());
328 	}
329 
330 	/**
331 	 * This fails if we try to propagate flags before parsing commits.
332 	 *
333 	 * @throws Exception
334 	 */
335 	@Test
336 	public void testUnparsedUninterestingCommitWithTwoParents()
337 			throws Exception {
338 		ObjectId a = unparsedCommit();
339 		ObjectId b = unparsedCommit(a);
340 		ObjectId c1 = unparsedCommit(b);
341 		ObjectId c2 = unparsedCommit(b);
342 		ObjectId d = unparsedCommit(c1);
343 		ObjectId e = unparsedCommit(c1, c2);
344 
345 		ObjectId uA = unparsedCommit(a, b);
346 		ObjectId uB1 = unparsedCommit(uA, c2);
347 		ObjectId uB2 = unparsedCommit(uA, d);
348 		ObjectId uninteresting = unparsedCommit(uB1, uB2);
349 
350 		rw.reset();
351 		rw.setFirstParent(true);
352 		RevCommit parsedE = rw.parseCommit(e);
353 		markStart(parsedE);
354 		markUninteresting(rw.parseCommit(uninteresting));
355 
356 		assertCommit(parsedE, rw.next());
357 		assertNull(rw.next());
358 	}
359 
360 	@Test
361 	public void testDepthWalk() throws Exception {
362 		RevCommit a = commit();
363 		RevCommit b1 = commit(a);
364 		RevCommit b2 = commit(a);
365 		RevCommit c = commit(b1, b2);
366 
367 		try (DepthWalk.RevWalk dw = new DepthWalk.RevWalk(db, 1)) {
368 			dw.setFirstParent(true);
369 			dw.markRoot(dw.parseCommit(c));
370 			dw.markStart(dw.parseCommit(c));
371 			assertEquals(c, dw.next());
372 			assertEquals(b1, dw.next());
373 			assertNull(dw.next());
374 		}
375 	}
376 
377 	@Test
378 	public void testDoNotRewriteParents() throws Exception {
379 		RevCommit a = commit();
380 		RevCommit b1 = commit(a);
381 		RevCommit b2 = commit(a);
382 		RevCommit c = commit(b1, b2);
383 
384 		rw.reset();
385 		rw.setFirstParent(true);
386 		rw.setRewriteParents(false);
387 		markStart(c);
388 		assertCommit(c, rw.next());
389 		assertCommit(b1, rw.next());
390 		assertCommit(a, rw.next());
391 		assertNull(rw.next());
392 	}
393 
394 	@Test(expected = IllegalStateException.class)
395 	public void testMarkStartBeforeSetFirstParent() throws Exception {
396 		RevCommit a = commit();
397 
398 		rw.reset();
399 		markStart(a);
400 		rw.setFirstParent(true);
401 	}
402 
403 	@Test(expected = IllegalStateException.class)
404 	public void testMergeBaseWithFirstParentNotAllowed() throws Exception {
405 		RevCommit a = commit();
406 
407 		rw.reset();
408 		rw.setFirstParent(true);
409 		rw.setRevFilter(RevFilter.MERGE_BASE);
410 		markStart(a);
411 		assertNull(rw.next());
412 	}
413 
414 	@Test
415 	public void testWithTopoSortAndTreeFilter() throws Exception {
416 		RevCommit a = commit();
417 		RevCommit b = commit(tree(file("0", blob("b"))), a);
418 		RevCommit c = commit(tree(file("0", blob("c"))), b, a);
419 		RevCommit d = commit(tree(file("0", blob("d"))), c);
420 
421 		rw.reset();
422 		rw.setFirstParent(true);
423 		rw.sort(RevSort.TOPO, true);
424 		rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
425 		markStart(d);
426 		assertCommit(d, rw.next());
427 		assertCommit(c, rw.next());
428 		assertCommit(b, rw.next());
429 		assertNull(rw.next());
430 	}
431 
432 	@Test
433 	public void testWithTopoSortAndTreeFilter2() throws Exception {
434 		RevCommit a = commit();
435 		RevCommit b = commit(tree(file("0", blob("b"))), a);
436 		RevCommit c = commit(tree(file("0", blob("c"))), a, b);
437 		RevCommit d = commit(tree(file("0", blob("d"))), c);
438 
439 		rw.reset();
440 		rw.setFirstParent(true);
441 		rw.sort(RevSort.TOPO, true);
442 		rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
443 		markStart(d);
444 		assertCommit(d, rw.next());
445 		assertCommit(c, rw.next());
446 		assertNull(rw.next());
447 	}
448 
449 	@Test
450 	public void testWithTopoNonIntermixSortAndTreeFilter() throws Exception {
451 		RevCommit a = commit();
452 		RevCommit b = commit(tree(file("0", blob("b"))), a);
453 		RevCommit c = commit(tree(file("0", blob("c"))), b, a);
454 		RevCommit d = commit(tree(file("0", blob("d"))), c);
455 
456 		rw.reset();
457 		rw.setFirstParent(true);
458 		rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER, true);
459 		rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
460 		markStart(d);
461 		assertCommit(d, rw.next());
462 		assertCommit(c, rw.next());
463 		assertCommit(b, rw.next());
464 		assertNull(rw.next());
465 	}
466 
467 	@Test
468 	public void testWithTopoNonIntermixSortAndTreeFilter2() throws Exception {
469 		RevCommit a = commit();
470 		RevCommit b = commit(tree(file("0", blob("b"))), a);
471 		RevCommit c = commit(tree(file("0", blob("c"))), a, b);
472 		RevCommit d = commit(tree(file("0", blob("d"))), c);
473 
474 		rw.reset();
475 		rw.setFirstParent(true);
476 		rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER, true);
477 		rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
478 		markStart(d);
479 		assertCommit(d, rw.next());
480 		assertCommit(c, rw.next());
481 		assertNull(rw.next());
482 	}
483 }