org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCommitGraphTest.java

/*
 * Copyright (C) 2023, Tencent.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Distribution License v. 1.0 which is available at
 * https://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */

package org.eclipse.jgit.revwalk;

import static java.util.Arrays.asList;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import java.io.IOException;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.eclipse.jgit.diff.DiffConfig;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ConfigConstants;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.revwalk.filter.MessageRevFilter;
import org.eclipse.jgit.revwalk.filter.RevFilter;
import org.eclipse.jgit.treewalk.filter.AndTreeFilter;
import org.eclipse.jgit.treewalk.filter.ChangedPathTreeFilter;
import org.eclipse.jgit.treewalk.filter.OrTreeFilter;
import org.eclipse.jgit.treewalk.filter.PathFilter;
import org.eclipse.jgit.treewalk.filter.TreeFilter;
import org.junit.Test;

public class RevWalkCommitGraphTest extends AbstractRevWalkWithCommitGraphTest {

	@Test
	public void testParseHeaders() throws Exception {
		RevCommit c1 = commitFile("file1", "1", "master");

		RevCommit notParseInGraph = rw.lookupCommit(c1);
		rw.parseHeaders(notParseInGraph);
		assertNotNull(notParseInGraph.getRawBuffer());
		assertEquals(Constants.COMMIT_GENERATION_UNKNOWN,
				notParseInGraph.getGeneration());

		enableAndWriteCommitGraph();

		reinitializeRevWalk();
		RevCommit parseInGraph = rw.lookupCommit(c1);
		parseInGraph.parseHeaders(rw);

		assertNotNull(parseInGraph.getRawBuffer());
		assertEquals(1, parseInGraph.getGeneration());
		assertEquals(notParseInGraph.getId(), parseInGraph.getId());
		assertEquals(notParseInGraph.getTree(), parseInGraph.getTree());
		assertEquals(notParseInGraph.getCommitTime(), parseInGraph.getCommitTime());
		assertArrayEquals(notParseInGraph.getParents(), parseInGraph.getParents());

		reinitializeRevWalk();
		rw.setRetainBody(false);
		RevCommit noBody = rw.lookupCommit(c1);
		noBody.parseHeaders(rw);

		assertNull(noBody.getRawBuffer());
		assertEquals(1, noBody.getGeneration());
		assertEquals(notParseInGraph.getId(), noBody.getId());
		assertEquals(notParseInGraph.getTree(), noBody.getTree());
		assertEquals(notParseInGraph.getCommitTime(), noBody.getCommitTime());
		assertArrayEquals(notParseInGraph.getParents(), noBody.getParents());
	}

	@Test
	public void testParseCanonical() throws Exception {
		RevCommit c1 = commitFile("file1", "1", "master");
		enableAndWriteCommitGraph();

		RevCommit notParseInGraph = rw.lookupCommit(c1);
		rw.parseHeaders(notParseInGraph);

		reinitializeRevWalk();
		RevCommit parseInGraph = rw.lookupCommit(c1);
		parseInGraph.parseCanonical(rw, rw.getCachedBytes(c1));

		assertNotNull(parseInGraph.getRawBuffer());
		assertEquals(1, parseInGraph.getGeneration());
		assertEquals(notParseInGraph.getId(), parseInGraph.getId());
		assertEquals(notParseInGraph.getTree(), parseInGraph.getTree());
		assertEquals(notParseInGraph.getCommitTime(),
				parseInGraph.getCommitTime());
		assertArrayEquals(notParseInGraph.getParents(),
				parseInGraph.getParents());

		reinitializeRevWalk();
		rw.setRetainBody(false);
		RevCommit noBody = rw.lookupCommit(c1);
		noBody.parseCanonical(rw, rw.getCachedBytes(c1));

		assertNull(noBody.getRawBuffer());
		assertEquals(1, noBody.getGeneration());
		assertEquals(notParseInGraph.getId(), noBody.getId());
		assertEquals(notParseInGraph.getTree(), noBody.getTree());
		assertEquals(notParseInGraph.getCommitTime(), noBody.getCommitTime());
		assertArrayEquals(notParseInGraph.getParents(), noBody.getParents());
	}

	@Test
	public void testInitializeShallowCommits() throws Exception {
		RevCommit c1 = commit(commit());
		branch(c1, "master");
		enableAndWriteCommitGraph();
		assertCommitCntInGraph(2);

		db.getObjectDatabase().setShallowCommits(Collections.singleton(c1));
		RevCommit parseInGraph = rw.lookupCommit(c1);
		parseInGraph.parseHeaders(rw);

		assertNotNull(parseInGraph.getRawBuffer());
		assertEquals(2, parseInGraph.getGeneration());
		assertEquals(0, parseInGraph.getParentCount());
	}

	@Test
	public void testTreeFilter() throws Exception {
		RevCommit c1 = commitFile("file1", "1", "master");
		RevCommit c2 = commitFile("file2", "2", "master");
		RevCommit c3 = commitFile("file1", "3", "master");
		RevCommit c4 = commitFile("file2", "4", "master");

		enableAndWriteCommitGraph();
		assertCommitCntInGraph(4);

		rw.markStart(rw.lookupCommit(c4));
		rw.setTreeFilter(AndTreeFilter.create(PathFilter.create("file1"),
				TreeFilter.ANY_DIFF));
		assertEquals(c3, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		reinitializeRevWalk();
		rw.markStart(rw.lookupCommit(c4));
		rw.setTreeFilter(AndTreeFilter.create(PathFilter.create("file2"),
				TreeFilter.ANY_DIFF));
		assertEquals(c4, rw.next());
		assertEquals(c2, rw.next());
		assertNull(rw.next());
	}

	@Test
	public void testChangedPathFilterMergeCommit_followFilter()
			throws Exception {
		RevCommit root1 = commit(tree(file("file1", blob("1"))));
		RevCommit root2 = commit(tree(file("file1", blob("2"))));
		RevCommit root3 = commit(tree(file("file1", blob("3"))));
		RevCommit merge1 = commit(tree(file("file1", blob("1"))), root1, root2);
		RevCommit merge2 = commit(tree(file("file1", blob("1"))), merge1,
				root3);
		RevCommit tip2 = commit(tree(file("file1", blob("1"))), merge2);
		RevCommit tip = commit(tree(file("file2", blob("1"))), tip2);

		branch(tip, "master");

		enableAndWriteCommitGraph();

		FollowFilter followFilter = FollowFilter.create("file2",
				db.getConfig().get(DiffConfig.KEY));

		rw.setTreeFilter(followFilter);
		rw.setRevFilter(RevFilter.ALL);
		rw.sort(RevSort.NONE);
		rw.setRetainBody(false);
		rw.markStart(rw.lookupCommit(db.resolve("master")));

		assertCommits(
				// no CG nor BF
				travel(followFilter, RevFilter.ALL, RevSort.NONE, false,
						"master"),
				// with CG and BF
				travel(rw, true));

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();

		// tip did a rename but didn't change content
		assertEquals(1, rfs.getChangedPathFilterTruePositive());

		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// tip2, merge2, merge1 didn't change content relative to their base
		// parent
		assertEquals(3, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilterMergeCommit_usedBaseParentAsRewrite()
			throws Exception {
		RevCommit root1 = commit(tree(file("file1", blob("1"))));
		RevCommit root2 = commit(tree(file("file1", blob("2"))));
		RevCommit root3 = commit(tree(file("file1", blob("3"))));
		RevCommit merge1 = commit(tree(file("file1", blob("1"))), root1, root2);
		RevCommit merge2 = commit(tree(file("file1", blob("1"))), merge1,
				root3);

		branch(merge2, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter changedPathTreeFilter = ChangedPathTreeFilter.create("file1");

		rw.setTreeFilter(changedPathTreeFilter);
		rw.setRevFilter(RevFilter.ALL);
		rw.sort(RevSort.NONE);
		rw.setRetainBody(false);
		rw.markStart(rw.lookupCommit(db.resolve("master")));

		assertCommits(
				// no CG nor BF
				travel(changedPathTreeFilter, RevFilter.ALL, RevSort.NONE, false,
						"master"),
				// with CG and BF
				travel(rw, true));

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// both merge1 and merge2 used their base parent as redirect
		assertEquals(2, rfs.getNumMergeCommitsUsedBaseParentAsRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsUsedPullRequestParentAsRedirect());
		assertEquals(0, rfs.getNumMergeCommitsHadNoRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsHadNoDiffWithAnyInterestingParent());
	}

	@Test
	public void testChangedPathFilterMergeCommit_usedPullRequestParentAsRewrite()
			throws Exception {
		RevCommit root1 = commit(tree(file("file1", blob("1"))));
		RevCommit root2 = commit(tree(file("file1", blob("2"))));
		RevCommit root3 = commit(tree(file("file1", blob("3"))));
		RevCommit merge1 = commit(tree(file("file1", blob("2"))), root1, root2);
		RevCommit merge2 = commit(tree(file("file1", blob("2"))), root3,
				merge1);

		branch(merge2, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter changedPathTreeFilter = ChangedPathTreeFilter.create("file1");

		rw.setTreeFilter(changedPathTreeFilter);
		rw.setRevFilter(RevFilter.ALL);
		rw.sort(RevSort.NONE);
		rw.setRetainBody(false);
		rw.markStart(rw.lookupCommit(db.resolve("master")));

		assertCommits(
				// no CG nor BF
				travel(changedPathTreeFilter, RevFilter.ALL, RevSort.NONE, false,
						"master"),
				// with CG and BF
				travel(rw, true));

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// both merge1 and merge2 used their 2nd parent as redirect
		assertEquals(0, rfs.getNumMergeCommitsUsedBaseParentAsRedirect());
		assertEquals(2,
				rfs.getNumMergeCommitsUsedPullRequestParentAsRedirect());
		assertEquals(0, rfs.getNumMergeCommitsHadNoRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsHadNoDiffWithAnyInterestingParent());
	}

	@Test
	public void testChangedPathFilterMergeCommit_noParentRedirect()
			throws Exception {
		RevCommit root1 = commit(tree(file("file1", blob("1"))));
		RevCommit root2 = commit(tree(file("file1", blob("2"))));
		RevCommit root3 = commit(tree(file("file1", blob("3"))));
		RevCommit merge1 = commit(tree(file("file1", blob("4"))), root1, root2);
		RevCommit merge2 = commit(tree(file("file1", blob("5"))), root3,
				merge1);

		branch(merge2, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter changedPathTreeFilter = ChangedPathTreeFilter.create("file1");
		rw.setTreeFilter(changedPathTreeFilter);
		rw.setRevFilter(RevFilter.ALL);
		rw.sort(RevSort.NONE);
		rw.setRetainBody(false);
		rw.markStart(rw.lookupCommit(db.resolve("master")));

		assertCommits(
				// no CG nor BF
				travel(changedPathTreeFilter, RevFilter.ALL, RevSort.NONE, false,
						"master"),
				// with CG and BF
				travel(rw, true));

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// both merge1 and merge2 did not need redirect since they are different
		// from all of their parents
		assertEquals(0, rfs.getNumMergeCommitsUsedBaseParentAsRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsUsedPullRequestParentAsRedirect());
		assertEquals(2, rfs.getNumMergeCommitsHadNoRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsHadNoDiffWithAnyInterestingParent());
	}

	@Test
	public void testChangedPathFilterMergeCommit_noInterestingParentForRedirect()
			throws Exception {
		RevCommit root1 = commit(tree(file("file1", blob("1"))));
		RevCommit root2 = commit(tree(file("file1", blob("2"))));
		RevCommit root3 = commit(tree(file("file1", blob("2"))));
		RevCommit root4 = commit(tree(file("file1", blob("3"))));

		RevCommit merge1 = commit(tree(file("file1", blob("1"))), root1, root2);
		RevCommit merge2 = commit(tree(file("file1", blob("2"))), root3, root4);
		RevCommit merge3 = commit(tree(file("file1", blob("1"))), merge1,
				merge2);

		branch(merge3, "master");

		ChangedPathTreeFilter changedPathTreeFilter = ChangedPathTreeFilter.create("file1");

		RevWalk expectedRevWalk = new RevWalk(db);
		expectedRevWalk.setTreeFilter(changedPathTreeFilter);
		expectedRevWalk.setRevFilter(RevFilter.ALL);
		expectedRevWalk.sort(RevSort.NONE);
		expectedRevWalk.setRetainBody(false);
		expectedRevWalk
				.markStart(expectedRevWalk.lookupCommit(db.resolve("master")));
		expectedRevWalk.markUninteresting(expectedRevWalk.lookupCommit(merge1));
		expectedRevWalk.markUninteresting(expectedRevWalk.lookupCommit(root3));

		enableAndWriteCommitGraph();
		rw.setTreeFilter(changedPathTreeFilter);
		rw.setRevFilter(RevFilter.ALL);
		rw.sort(RevSort.NONE);
		rw.setRetainBody(false);
		rw.markStart(rw.lookupCommit(db.resolve("master")));
		rw.markUninteresting(rw.lookupCommit(merge1));
		rw.markUninteresting(rw.lookupCommit(root3));

		assertCommits(
				// no CG nor BF
				travel(expectedRevWalk, false),
				// with CG and BF
				travel(rw, true));

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// both merge3 and merge2 had same content base parent but they were
		// UNINTERESTING
		assertEquals(0, rfs.getNumMergeCommitsUsedBaseParentAsRedirect());
		assertEquals(0,
				rfs.getNumMergeCommitsUsedPullRequestParentAsRedirect());
		assertEquals(0, rfs.getNumMergeCommitsHadNoRedirect());
		assertEquals(2,
				rfs.getNumMergeCommitsHadNoDiffWithAnyInterestingParent());
	}

	@Test
	public void testChangedPathFilter_allModify() throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file2", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file1", blob("3"))), c2);
		RevCommit c4 = commit(tree(file("file2", blob("4"))), c3);

		branch(c4, "master");

		enableAndWriteCommitGraph();

		TreeRevFilter trf = new TreeRevFilter(rw,
				ChangedPathTreeFilter.create("file1"));
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// all commits modified file1 but c1 did not have a parent
		assertEquals(3, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// No negatives because all 4 commits had modified file1
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_someModify() throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file1", blob("1"))), c1);
		RevCommit c3 = commit(tree(file("file1", blob("2"))), c2);
		RevCommit c4 = commit(tree(file("file1", blob("1"))), c3);

		branch(c4, "master");

		enableAndWriteCommitGraph();

		TreeRevFilter trf = new TreeRevFilter(rw,
				ChangedPathTreeFilter.create("file1"));
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c4 and c3 modified file1. c1 did not have a parent
		assertEquals(2, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// c2 did not modify file1
		assertEquals(1, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilterWithMultiPaths() throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file1", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file2", blob("3"))), c2);
		RevCommit c4 = commit(tree(file("file3", blob("4"))), c3);

		branch(c4, "master");

		enableAndWriteCommitGraph();

		TreeRevFilter trf = new TreeRevFilter(rw,
				ChangedPathTreeFilter.create("file1", "file2"));
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// all commits have modified either file1 or file2, c1 did not have a
		// parent
		assertEquals(3, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// No negative
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilterWithFollowFilter() throws Exception {
		RevCommit c0 = commit(tree());
		RevCommit c1 = commit(tree(file("file", blob("contents"))), c0);
		RevCommit c2 = commit(tree(file("file", blob("contents")),
				file("unrelated", blob("unrelated change"))), c1);
		RevCommit c3 = commit(tree(file("renamed-file", blob("contents")),
				file("unrelated", blob("unrelated change"))), c2);
		RevCommit c4 = commit(
				tree(file("renamed-file", blob("contents")),
						file("unrelated", blob("another unrelated change"))),
				c3);
		branch(c4, "master");

		enableAndWriteCommitGraph();

		db.getConfig().setString(ConfigConstants.CONFIG_DIFF_SECTION, null,
				ConfigConstants.CONFIG_KEY_RENAMES, "true");

		TreeRevFilter trf = new TreeRevFilter(rw, FollowFilter
				.create("renamed-file", db.getConfig().get(DiffConfig.KEY)));
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c3, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// Path "renamed-file" is in c3's bloom filter, and another path "file"
		// is in c1's bloom filter (we know of "file" because the rev walk
		// detected that "renamed-file" is a renaming of "file")
		assertEquals(2, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// 2 commits that have exactly one parent and don't match path
		assertEquals(2, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_or_pathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(
				tree(file("file1", blob("1")), file("file2", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file2", blob("2"))), c2);
		RevCommit c4 = commit(
				tree(file("file2", blob("2")), file("file3", blob("3"))), c3);
		RevCommit c5 = commit(
				tree(file("file2", blob("2")), file("file3", blob("3"))), c4);

		branch(c5, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf1 = ChangedPathTreeFilter.create("file1");
		ChangedPathTreeFilter pf2 = ChangedPathTreeFilter.create("file2");

		TreeFilter tf = OrTreeFilter
				.create(new ChangedPathTreeFilter[] { pf1, pf2 });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c5));
		rw.setRevFilter(trf);
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c2 and c3 has either file1 or file2, c1 is not counted as
		// ChangedPathFilter only applies to commits with 1 parent
		assertEquals(2, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// c4 and c5 did not modify file1 or file2
		assertEquals(2, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_or_pathFilter_or_pathFilter_listOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(
				tree(file("file1", blob("1")), file("file2", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file2", blob("2"))), c2);
		RevCommit c4 = commit(tree(file("file3", blob("3"))), c3);
		RevCommit c5 = commit(tree(file("file3", blob("3"))), c4);

		branch(c5, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf1 = ChangedPathTreeFilter.create("file1");
		ChangedPathTreeFilter pf2 = ChangedPathTreeFilter.create("file2");
		ChangedPathTreeFilter pf3 = ChangedPathTreeFilter.create("file3");

		TreeFilter tf = OrTreeFilter
				.create(new ChangedPathTreeFilter[] { pf1, pf2, pf3 });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c5));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c2 and c3 has either modified file1 or file2 or file3, c1 is not
		// counted as ChangedPathFilter only applies to commits with 1 parent
		assertEquals(3, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// c5 does not modify either file1 or file2 or file3
		assertEquals(1, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_or_nonPathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file2", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file2", blob("3"))), c2);
		RevCommit c4 = commit(tree(file("file2", blob("3"))), c3);

		branch(c4, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf = ChangedPathTreeFilter.create("file1");
		TreeFilter npf = TreeFilter.ANY_DIFF;

		TreeFilter tf = OrTreeFilter.create(new TreeFilter[] { pf, npf });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c2 modified file1, c3 defaulted positive due to ANY_DIFF, c1 is not
		// counted as ChangedPathFilter only applies to commits with 1 parent
		assertEquals(2, rfs.getChangedPathFilterTruePositive());

		// c4 defaulted positive due to ANY_DIFF, but didn't no diff with its
		// parent c3
		assertEquals(1, rfs.getChangedPathFilterFalsePositive());

		// No negative due to the OrTreeFilter
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_nonPathFilter_or_nonPathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commitFile("file1", "1", "master");
		RevCommit c2 = commitFile("file2", "2", "master");
		RevCommit c3 = commitFile("file3", "3", "master");
		RevCommit c4 = commitFile("file4", "4", "master");

		enableAndWriteCommitGraph();

		TreeFilter npf1 = TreeFilter.ANY_DIFF;
		TreeFilter npf2 = TreeFilter.ANY_DIFF;

		TreeFilter tf = OrTreeFilter.create(new TreeFilter[] { npf1, npf2 });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// No true positives since there's no pathFilter
		assertEquals(0, rfs.getChangedPathFilterTruePositive());

		// No false positives since there's no pathFilter
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// No negative since there's no pathFilter
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_and_pathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file2", blob("2"))), c1);

		branch(c2, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf1 = ChangedPathTreeFilter.create("file1");
		ChangedPathTreeFilter pf2 = ChangedPathTreeFilter.create("file2");

		TreeFilter atf = AndTreeFilter
				.create(new ChangedPathTreeFilter[] { pf1, pf2 });
		TreeRevFilter trf = new TreeRevFilter(rw, atf);

		rw.markStart(rw.lookupCommit(c2));
		rw.setRevFilter(trf);

		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c1 is not counted as ChangedPathFilter only applies to commits with 1
		// parent
		assertEquals(0, rfs.getChangedPathFilterTruePositive());

		// c2 has modified both file 1 and file2,
		// however nothing is returned from TreeWalk since a TreeHead
		// cannot be two paths at once
		assertEquals(1, rfs.getChangedPathFilterFalsePositive());

		// No negatives
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_and_pathFilter_and_pathFilter_listOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file2", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file3", blob("3"))), c2);

		branch(c3, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf1 = ChangedPathTreeFilter.create("file1");
		ChangedPathTreeFilter pf2 = ChangedPathTreeFilter.create("file2");
		ChangedPathTreeFilter pf3 = ChangedPathTreeFilter.create("file3");

		TreeFilter tf = AndTreeFilter
				.create(new ChangedPathTreeFilter[] { pf1, pf2, pf3 });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c3));
		rw.setRevFilter(trf);
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c1 is not counted as ChangedPathFilter only applies to commits with 1
		// parent
		assertEquals(0, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// c2 and c3 can not possibly have both file1, file2, and file3 as
		// treeHead at once
		assertEquals(2, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_pathFilter_and_nonPathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commit(tree(file("file1", blob("1"))));
		RevCommit c2 = commit(tree(file("file1", blob("2"))), c1);
		RevCommit c3 = commit(tree(file("file1", blob("2"))), c2);

		branch(c3, "master");

		enableAndWriteCommitGraph();

		ChangedPathTreeFilter pf = ChangedPathTreeFilter.create("file1");
		TreeFilter npf = TreeFilter.ANY_DIFF;

		TreeFilter tf = AndTreeFilter.create(new TreeFilter[] { pf, npf });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c3));
		rw.setRevFilter(trf);
		assertEquals(c2, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// c2 modified file1 and c1 is not counted as ChangedPathFilter only
		// applies to commits with 1 parent
		assertEquals(1, rfs.getChangedPathFilterTruePositive());

		// No false positives
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// c3 did not modify file1
		assertEquals(1, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testChangedPathFilter_nonPathFilter_and_nonPathFilter_binaryOperation()
			throws Exception {
		RevCommit c1 = commitFile("file1", "1", "master");
		commitFile("file1", "1", "master");
		RevCommit c3 = commitFile("file3", "3", "master");
		RevCommit c4 = commitFile("file4", "4", "master");

		enableAndWriteCommitGraph();

		TreeFilter npf1 = TreeFilter.ANY_DIFF;
		TreeFilter npf2 = TreeFilter.ANY_DIFF;

		TreeFilter tf = AndTreeFilter.create(new TreeFilter[] { npf1, npf2 });

		TreeRevFilter trf = new TreeRevFilter(rw, tf);
		rw.markStart(rw.lookupCommit(c4));
		rw.setRevFilter(trf);
		assertEquals(c4, rw.next());
		assertEquals(c3, rw.next());
		assertEquals(c1, rw.next());
		assertNull(rw.next());

		RevWalk.RevFilterStats rfs = rw.getRevFilterStats();
		// No true positives since there's no path
		assertEquals(0, rfs.getChangedPathFilterTruePositive());

		// No false positives since there's no path
		assertEquals(0, rfs.getChangedPathFilterFalsePositive());

		// No negative since there's no path
		assertEquals(0, rfs.getChangedPathFilterNegative());
	}

	@Test
	public void testWalkWithCommitMessageFilter() throws Exception {
		RevCommit a = commit();
		RevCommit b = commitBuilder().parent(a)
				.message("The quick brown fox jumps over the lazy dog!")
				.create();
		RevCommit c = commitBuilder().parent(b).message("commit-c").create();
		branch(c, "master");

		enableAndWriteCommitGraph();
		assertCommitCntInGraph(3);

		rw.setRevFilter(MessageRevFilter.create("quick brown fox jumps"));
		rw.markStart(rw.lookupCommit(c));
		assertEquals(b, rw.next());
		assertNull(rw.next());
	}

	@Test
	public void testCommitsWalk() throws Exception {
		RevCommit c1 = commit();
		branch(c1, "commits/1");
		RevCommit c2 = commit(c1);
		branch(c2, "commits/2");
		RevCommit c3 = commit(c2);
		branch(c3, "commits/3");

		enableAndWriteCommitGraph();
		assertCommitCntInGraph(3);
		testRevWalkBehavior("commits/1", "commits/3");

		// add more commits
		RevCommit c4 = commit(c1);
		RevCommit c5 = commit(c4);
		RevCommit c6 = commit(c1);
		RevCommit c7 = commit(c6);

		RevCommit m1 = commit(c2, c4);
		branch(m1, "merge/1");
		RevCommit m2 = commit(c4, c6);
		branch(m2, "merge/2");
		RevCommit m3 = commit(c3, c5, c7);
		branch(m3, "merge/3");

		/*
		 * <pre>
		 * current graph structure:
		 *
		 *    __M3___
		 *   /   |   \
		 *  3 M1 5 M2 7
		 *  |/  \|/  \|
		 *  2    4    6
		 *  |___/____/
		 *  1
		 * </pre>
		 */
		enableAndWriteCommitGraph();
		reinitializeRevWalk();
		assertCommitCntInGraph(10);
		testRevWalkBehavior("merge/1", "merge/2");
		testRevWalkBehavior("merge/1", "merge/3");
		testRevWalkBehavior("merge/2", "merge/3");

		// add one more commit
		RevCommit c8 = commit(m3);
		branch(c8, "commits/8");

		/*
		 * <pre>
		 * current graph structure:
		 *       8
		 *       |
		 *    __M3___
		 *   /   |   \
		 *  3 M1 5 M2 7
		 *  |/  \|/  \|
		 *  2    4    6
		 *  |___/____/
		 *  1
		 * </pre>
		 */
		testRevWalkBehavior("commits/8", "merge/1");
		testRevWalkBehavior("commits/8", "merge/2");

		enableAndWriteCommitGraph();
		reinitializeRevWalk();
		assertCommitCntInGraph(11);
		testRevWalkBehavior("commits/8", "merge/1");
		testRevWalkBehavior("commits/8", "merge/2");
	}

	@Test
	public void testMergedInto() throws Exception {
		RevCommit c1 = commit();
		Ref branch1 = branch(c1, "commits/1");
		RevCommit c2 = commit(c1);
		Ref branch2 = branch(c2, "commits/2");
		RevCommit c3 = commit(c2);
		Ref branch3 = branch(c3, "commits/3");
		RevCommit c4 = commit(c1);
		Ref branch4 = branch(c4, "commits/4");
		RevCommit c5 = commit(c4);
		Ref branch5 = branch(c5, "commits/5");
		enableAndWriteCommitGraph();
		RevCommit c6 = commit(c1);
		Ref branch6 = branch(c6, "commits/6");
		RevCommit c7 = commit(c2, c4);
		Ref branch7 = branch(c7, "commits/7");
		RevCommit c8 = commit(c5);
		Ref branch8 = branch(c8, "commits/8");
		RevCommit c9 = commit(c4, c6);
		Ref branch9 = branch(c9, "commits/9");

		/*
		 * <pre>
		 * current graph structure:
		 *       8
		 *       |
		 *  3  7 5  9
		 *  |/  \|/  \
		 *  2    4    6
		 *  |___/____/
		 *  1
		 * </pre>
		 *
		 * [6, 7, 8, 9] are not in commit-graph.
		 */

		reinitializeRevWalk();
		assertFalse(isObjectIdInGraph(c9));
		assertRefsEquals(asList(branch9), allMergedInto(c9));

		assertFalse(isObjectIdInGraph(c8));
		assertRefsEquals(asList(branch8), allMergedInto(c8));

		assertFalse(isObjectIdInGraph(c7));
		assertRefsEquals(asList(branch7), allMergedInto(c7));

		assertFalse(isObjectIdInGraph(c6));
		assertRefsEquals(asList(branch6, branch9), allMergedInto(c6));

		assertTrue(isObjectIdInGraph(c5));
		assertRefsEquals(asList(branch5, branch8), allMergedInto(c5));

		assertTrue(isObjectIdInGraph(c4));
		assertRefsEquals(asList(branch4, branch5, branch7, branch8, branch9),
				allMergedInto(c4));

		assertTrue(isObjectIdInGraph(c3));
		assertRefsEquals(asList(branch3), allMergedInto(c3));

		assertTrue(isObjectIdInGraph(c2));
		assertRefsEquals(asList(branch2, branch3, branch7), allMergedInto(c2));

		assertTrue(isObjectIdInGraph(c1));
		assertRefsEquals(asList(branch1, branch2, branch3, branch4, branch5,
				branch6, branch7, branch8, branch9), allMergedInto(c1));
	}

	boolean isObjectIdInGraph(AnyObjectId id) {
		return rw.commitGraph().findGraphPosition(id) >= 0;
	}

	List<Ref> allMergedInto(RevCommit needle) throws IOException {
		List<Ref> refs = db.getRefDatabase().getRefs();
		return rw.getMergedInto(rw.lookupCommit(needle), refs);
	}

	void assertRefsEquals(List<Ref> expecteds, List<Ref> actuals) {
		assertEquals(expecteds.size(), actuals.size());
		Collections.sort(expecteds, Comparator.comparing(Ref::getName));
		Collections.sort(actuals, Comparator.comparing(Ref::getName));
		for (int i = 0; i < expecteds.size(); i++) {
			Ref expected = expecteds.get(i);
			Ref actual = actuals.get(i);
			assertEquals(expected.getName(), actual.getName());
			assertEquals(expected.getObjectId(), actual.getObjectId());
		}
	}

	void testRevWalkBehavior(String branch, String compare) throws Exception {
		assertCommits(
				travel(TreeFilter.ALL, RevFilter.MERGE_BASE, RevSort.NONE, true,
						branch, compare),
				travel(TreeFilter.ALL, RevFilter.MERGE_BASE, RevSort.NONE,
						false, branch, compare));

		assertCommits(
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.TOPO, true,
						branch),
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.TOPO, false,
						branch));

		assertCommits(
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.TOPO, true,
						compare),
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.TOPO, false,
						compare));

		assertCommits(
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.COMMIT_TIME_DESC,
						true, branch),
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.COMMIT_TIME_DESC,
						false, branch));

		assertCommits(
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.COMMIT_TIME_DESC,
						true, compare),
				travel(TreeFilter.ALL, RevFilter.ALL, RevSort.COMMIT_TIME_DESC,
						false, compare));
	}

}