blame: Compute the origin of lines in a result file

BlameGenerator digs through history and discovers the origin of each
line of some result file.  BlameResult consumes the stream of regions
created by the generator and lays them out in a table for applications
to display alongside of source lines.

Applications may optionally push in the working tree copy of a file
using the push(String, byte[]) method, allowing the application to
receive accurate line annotations for the working tree version.  Lines
that are uncommitted (difference between HEAD and working tree) will
show up with the description given by the application as the author,
or "Not Committed Yet" as a default string.

Applications may also run the BlameGenerator in reverse mode using the
reverse(AnyObjectId, AnyObjectId) method instead of push().  When
running in the reverse mode the generator annotates lines by the
commit they are removed in, rather than the commit they were added in.
This allows a user to discover where a line disappeared from when they
are looking at an older revision in the repository.  For example:

  blame --reverse 16e810b2..master -L 1080, org.eclipse.jgit.test/tst/org/eclipse/jgit/storage/file/RefDirectoryTest.java
           (                                              1080)   }
  2302a6d3 (Christian Halstrick 2011-05-20 11:18:20 +0200 1081)
  2302a6d3 (Christian Halstrick 2011-05-20 11:18:20 +0200 1082)   /**
  2302a6d3 (Christian Halstrick 2011-05-20 11:18:20 +0200 1083)    * Kick the timestamp of a local file.

Above we learn that line 1080 (a closing curly brace of the prior
method) still exists in branch master, but the Javadoc comment below
it has been removed by Christian Halstrick on May 20th as part of
commit 2302a6d3.  This result differs considerably from that of C
Git's blame --reverse feature.  JGit tells the reader which commit
performed the delete, while C Git tells the reader the last commit
that still contained the line, leaving it an exercise to the reader
to discover the descendant that performed the removal.

This is still only a basic implementation.  Quite notably it is
missing support for the smart block copy/move detection that the C
implementation of `git blame` is well known for.  Despite being
incremental, the BlameGenerator can only be run once.  After the
generator runs it cannot be reused.  A better implementation would
support applications browsing through history efficiently.

In regards to CQ 5110, only a little of the original code survives.

CQ: 5110
Bug: 306161
Change-Id: I84b8ea4838bb7d25f4fcdd540547884704661b8f
Signed-off-by: Kevin Sawicki <kevin@github.com>
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
Signed-off-by: Chris Aniszczyk <caniszczyk@gmail.com>

3 files changed, 415 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
index 8ec0b6582f..b1736472ee 100644
--- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
@@ -11,6 +11,7 @@ Import-Package: org.eclipse.jgit;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.api;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.api.errors;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.awtui;version="[1.0.0,1.1.0)",
+ org.eclipse.jgit.blame;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.console;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.diff;version="[1.0.0,1.1.0)",
  org.eclipse.jgit.dircache;version="[1.0.0,1.1.0)",
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/BlameCommandTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/BlameCommandTest.java
new file mode 100644
index 0000000000..1f67807e46
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/BlameCommandTest.java
@@ -0,0 +1,271 @@
+/*
+ * Copyright (C) 2011, GitHub Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.api;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+
+import org.eclipse.jgit.blame.BlameResult;
+import org.eclipse.jgit.lib.RepositoryTestCase;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.junit.Test;
+
+/**
+ * Unit tests of {@link BlameCommand}
+ */
+public class BlameCommandTest extends RepositoryTestCase {
+
+	private String join(String... lines) {
+		StringBuilder joined = new StringBuilder();
+		for (String line : lines)
+			joined.append(line).append('\n');
+		return joined.toString();
+	}
+
+	@Test
+	public void testSingleRevision() throws Exception {
+		Git git = new Git(db);
+
+		String[] content = new String[] { "first", "second", "third" };
+
+		writeTrashFile("file.txt", join(content));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit = git.commit().setMessage("create file").call();
+
+		BlameCommand command = new BlameCommand(db);
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertNotNull(lines);
+		assertEquals(3, lines.getResultContents().size());
+
+		for (int i = 0; i < 3; i++) {
+			assertEquals(commit, lines.getSourceCommit(i));
+			assertEquals(i, lines.getSourceLine(i));
+		}
+	}
+
+	@Test
+	public void testTwoRevisions() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "first", "second" };
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit1 = git.commit().setMessage("create file").call();
+
+		String[] content2 = new String[] { "first", "second", "third" };
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit2 = git.commit().setMessage("create file").call();
+
+		BlameCommand command = new BlameCommand(db);
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertEquals(3, lines.getResultContents().size());
+
+		assertEquals(commit1, lines.getSourceCommit(0));
+		assertEquals(0, lines.getSourceLine(0));
+
+		assertEquals(commit1, lines.getSourceCommit(1));
+		assertEquals(1, lines.getSourceLine(1));
+
+		assertEquals(commit2, lines.getSourceCommit(2));
+		assertEquals(2, lines.getSourceLine(2));
+	}
+
+	@Test
+	public void testRename() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "a", "b", "c" };
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit1 = git.commit().setMessage("create file").call();
+
+		writeTrashFile("file1.txt", join(content1));
+		git.add().addFilepattern("file1.txt").call();
+		git.rm().addFilepattern("file.txt").call();
+		git.commit().setMessage("moving file").call();
+
+		String[] content2 = new String[] { "a", "b", "c2" };
+		writeTrashFile("file1.txt", join(content2));
+		git.add().addFilepattern("file1.txt").call();
+		RevCommit commit3 = git.commit().setMessage("editing file").call();
+
+		BlameCommand command = new BlameCommand(db);
+		command.setFollowFileRenames(true);
+		command.setFilePath("file1.txt");
+		BlameResult lines = command.call();
+
+		assertEquals(commit1, lines.getSourceCommit(0));
+		assertEquals(0, lines.getSourceLine(0));
+		assertEquals("file.txt", lines.getSourcePath(0));
+
+		assertEquals(commit1, lines.getSourceCommit(1));
+		assertEquals(1, lines.getSourceLine(1));
+		assertEquals("file.txt", lines.getSourcePath(1));
+
+		assertEquals(commit3, lines.getSourceCommit(2));
+		assertEquals(2, lines.getSourceLine(2));
+		assertEquals("file1.txt", lines.getSourcePath(2));
+	}
+
+	@Test
+	public void testDeleteTrailingLines() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "a", "b", "c", "d" };
+		String[] content2 = new String[] { "a", "b" };
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit1 = git.commit().setMessage("create file").call();
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		BlameCommand command = new BlameCommand(db);
+
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertEquals(content2.length, lines.getResultContents().size());
+
+		assertEquals(commit1, lines.getSourceCommit(0));
+		assertEquals(commit1, lines.getSourceCommit(1));
+
+		assertEquals(0, lines.getSourceLine(0));
+		assertEquals(1, lines.getSourceLine(1));
+	}
+
+	@Test
+	public void testDeleteMiddleLines() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "a", "b", "c", "d", "e" };
+		String[] content2 = new String[] { "a", "c", "e" };
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit1 = git.commit().setMessage("edit file").call();
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		BlameCommand command = new BlameCommand(db);
+
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertEquals(content2.length, lines.getResultContents().size());
+
+		assertEquals(commit1, lines.getSourceCommit(0));
+		assertEquals(0, lines.getSourceLine(0));
+
+		assertEquals(commit1, lines.getSourceCommit(1));
+		assertEquals(1, lines.getSourceLine(1));
+
+		assertEquals(commit1, lines.getSourceCommit(2));
+		assertEquals(2, lines.getSourceLine(2));
+	}
+
+	@Test
+	public void testEditAllLines() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "a", "1" };
+		String[] content2 = new String[] { "b", "2" };
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit2 = git.commit().setMessage("create file").call();
+
+		BlameCommand command = new BlameCommand(db);
+
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertEquals(content2.length, lines.getResultContents().size());
+		assertEquals(commit2, lines.getSourceCommit(0));
+		assertEquals(commit2, lines.getSourceCommit(1));
+	}
+
+	@Test
+	public void testMiddleClearAllLines() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "a", "b", "c" };
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("edit file").call();
+
+		writeTrashFile("file.txt", "");
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("create file").call();
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit commit3 = git.commit().setMessage("edit file").call();
+
+		BlameCommand command = new BlameCommand(db);
+
+		command.setFilePath("file.txt");
+		BlameResult lines = command.call();
+		assertEquals(content1.length, lines.getResultContents().size());
+		assertEquals(commit3, lines.getSourceCommit(0));
+		assertEquals(commit3, lines.getSourceCommit(1));
+		assertEquals(commit3, lines.getSourceCommit(2));
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java
new file mode 100644
index 0000000000..657cf38708
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java
@@ -0,0 +1,143 @@
+/*
+ * Copyright (C) 2011, GitHub Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.api.blame;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import org.eclipse.jgit.api.Git;
+import org.eclipse.jgit.blame.BlameGenerator;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.RepositoryTestCase;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.junit.Test;
+
+/** Unit tests of {@link BlameGenerator}. */
+public class BlameGeneratorTest extends RepositoryTestCase {
+	@Test
+	public void testBoundLineDelete() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "first", "second" };
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit c1 = git.commit().setMessage("create file").call();
+
+		String[] content2 = new String[] { "third", "first", "second" };
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit c2 = git.commit().setMessage("create file").call();
+
+		BlameGenerator generator = new BlameGenerator(db, "file.txt");
+		try {
+			generator.push(null, db.resolve(Constants.HEAD));
+			assertEquals(3, generator.getResultContents().size());
+
+			assertTrue(generator.next());
+			assertEquals(c2, generator.getSourceCommit());
+			assertEquals(1, generator.getRegionLength());
+			assertEquals(0, generator.getResultStart());
+			assertEquals(1, generator.getResultEnd());
+			assertEquals(0, generator.getSourceStart());
+			assertEquals(1, generator.getSourceEnd());
+			assertEquals("file.txt", generator.getSourcePath());
+
+			assertTrue(generator.next());
+			assertEquals(c1, generator.getSourceCommit());
+			assertEquals(2, generator.getRegionLength());
+			assertEquals(1, generator.getResultStart());
+			assertEquals(3, generator.getResultEnd());
+			assertEquals(0, generator.getSourceStart());
+			assertEquals(2, generator.getSourceEnd());
+			assertEquals("file.txt", generator.getSourcePath());
+
+			assertFalse(generator.next());
+		} finally {
+			generator.release();
+		}
+	}
+
+	@Test
+	public void testLinesAllDeletedShortenedWalk() throws Exception {
+		Git git = new Git(db);
+
+		String[] content1 = new String[] { "first", "second", "third" };
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("create file").call();
+
+		String[] content2 = new String[] { "" };
+
+		writeTrashFile("file.txt", join(content2));
+		git.add().addFilepattern("file.txt").call();
+		git.commit().setMessage("create file").call();
+
+		writeTrashFile("file.txt", join(content1));
+		git.add().addFilepattern("file.txt").call();
+		RevCommit c3 = git.commit().setMessage("create file").call();
+
+		BlameGenerator generator = new BlameGenerator(db, "file.txt");
+		try {
+			generator.push(null, db.resolve(Constants.HEAD));
+			assertEquals(3, generator.getResultContents().size());
+
+			assertTrue(generator.next());
+			assertEquals(c3, generator.getSourceCommit());
+			assertEquals(0, generator.getResultStart());
+			assertEquals(3, generator.getResultEnd());
+
+			assertFalse(generator.next());
+		} finally {
+			generator.release();
+		}
+	}
+
+	private static String join(String... lines) {
+		StringBuilder joined = new StringBuilder();
+		for (String line : lines)
+			joined.append(line).append('\n');
+		return joined.toString();
+	}
+}