Move rename detection, path following into DiffFormatter

Applications just want a quick way to configure our diff
implementation, and then just want to use it without a lot of fuss.

Move all of the rename detection logic and path following logic
out of our pgm package and into DiffFormatter itself, making it
much easier for a GUI to take advantage of the features without
duplicating a lot of code.

Change-Id: I4b54e987bb6dc804fb270cbc495fe4cae26c7b0e
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

3 files changed, 368 insertions, 36 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffConfig.java
index 91b7467aee..4b86f55fcd 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffConfig.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffConfig.java
@@ -55,12 +55,28 @@ public class DiffConfig {
 		}
 	};
 
+	private final boolean noPrefix;
+
+	private final boolean renames;
+
 	private final int renameLimit;
 
 	private DiffConfig(final Config rc) {
+		noPrefix = rc.getBoolean("diff", "noprefix", false);
+		renames = rc.getBoolean("diff", "renames", false);
 		renameLimit = rc.getInt("diff", "renamelimit", 200);
 	}
 
+	/** @return true if the prefix "a/" and "b/" should be suppressed. */
+	public boolean isNoPrefix() {
+		return noPrefix;
+	}
+
+	/** @return true if rename detection is enabled by default. */
+	public boolean isRenameDetectionEnabled() {
+		return renames;
+	}
+
 	/** @return limit on number of paths to perform inexact rename detection. */
 	public int getRenameLimit() {
 		return renameLimit;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
index cb145e4b5a..3590ef5b48 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffFormatter.java
@@ -45,6 +45,7 @@
 package org.eclipse.jgit.diff;
 
 import static org.eclipse.jgit.diff.DiffEntry.ChangeType.ADD;
+import static org.eclipse.jgit.diff.DiffEntry.ChangeType.COPY;
 import static org.eclipse.jgit.diff.DiffEntry.ChangeType.DELETE;
 import static org.eclipse.jgit.diff.DiffEntry.ChangeType.MODIFY;
 import static org.eclipse.jgit.diff.DiffEntry.ChangeType.RENAME;
@@ -56,6 +57,7 @@ import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.OutputStream;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.List;
 
 import org.eclipse.jgit.JGitText;
@@ -65,16 +67,26 @@ import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.errors.LargeObjectException;
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
+import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectLoader;
 import org.eclipse.jgit.lib.ObjectReader;
+import org.eclipse.jgit.lib.ProgressMonitor;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.patch.FileHeader;
 import org.eclipse.jgit.patch.HunkHeader;
 import org.eclipse.jgit.patch.FileHeader.PatchType;
+import org.eclipse.jgit.revwalk.FollowFilter;
+import org.eclipse.jgit.revwalk.RevTree;
+import org.eclipse.jgit.revwalk.RevWalk;
 import org.eclipse.jgit.storage.pack.PackConfig;
+import org.eclipse.jgit.treewalk.AbstractTreeIterator;
+import org.eclipse.jgit.treewalk.CanonicalTreeParser;
+import org.eclipse.jgit.treewalk.TreeWalk;
+import org.eclipse.jgit.treewalk.filter.AndTreeFilter;
+import org.eclipse.jgit.treewalk.filter.TreeFilter;
 import org.eclipse.jgit.util.QuotedString;
 import org.eclipse.jgit.util.io.DisabledOutputStream;
 
@@ -96,6 +108,8 @@ public class DiffFormatter {
 
 	private Repository db;
 
+	private ObjectReader reader;
+
 	private int context = 3;
 
 	private int abbreviationLength = 7;
@@ -108,6 +122,12 @@ public class DiffFormatter {
 
 	private String newPrefix = "b/";
 
+	private TreeFilter pathFilter = TreeFilter.ALL;
+
+	private RenameDetector renameDetector;
+
+	private ProgressMonitor progressMonitor;
+
 	/**
 	 * Create a new formatter with a default level of context.
 	 *
@@ -128,11 +148,25 @@ public class DiffFormatter {
 	/**
 	 * Set the repository the formatter can load object contents from.
 	 *
+	 * Once a repository has been set, the formatter must be released to ensure
+	 * the internal ObjectReader is able to release its resources.
+	 *
 	 * @param repository
 	 *            source repository holding referenced objects.
 	 */
 	public void setRepository(Repository repository) {
+		if (reader != null)
+			reader.release();
+
 		db = repository;
+		reader = db.newObjectReader();
+
+		DiffConfig dc = db.getConfig().get(DiffConfig.KEY);
+		if (dc.isNoPrefix()) {
+			setOldPrefix("");
+			setNewPrefix("");
+		}
+		setDetectRenames(dc.isRenameDetectionEnabled());
 	}
 
 	/**
@@ -220,6 +254,64 @@ public class DiffFormatter {
 		newPrefix = prefix;
 	}
 
+	/** @return true if rename detection is enabled. */
+	public boolean isDetectRenames() {
+		return renameDetector != null;
+	}
+
+	/**
+	 * Enable or disable rename detection.
+	 *
+	 * Before enabling rename detection the repository must be set with
+	 * {@link #setRepository(Repository)}. Once enabled the detector can be
+	 * configured away from its defaults by obtaining the instance directly from
+	 * {@link #getRenameDetector()} and invoking configuration.
+	 *
+	 * @param on
+	 *            if rename detection should be enabled.
+	 */
+	public void setDetectRenames(boolean on) {
+		if (on && renameDetector == null) {
+			assertHaveRepository();
+			renameDetector = new RenameDetector(db);
+		} else if (!on)
+			renameDetector = null;
+	}
+
+	/** @return the rename detector if rename detection is enabled. */
+	public RenameDetector getRenameDetector() {
+		return renameDetector;
+	}
+
+	/**
+	 * Set the progress monitor for long running rename detection.
+	 *
+	 * @param pm
+	 *            progress monitor to receive rename detection status through.
+	 */
+	public void setProgressMonitor(ProgressMonitor pm) {
+		progressMonitor = pm;
+	}
+
+	/**
+	 * Set the filter to produce only specific paths.
+	 *
+	 * If the filter is an instance of {@link FollowFilter}, the filter path
+	 * will be updated during successive scan or format invocations. The updated
+	 * path can be obtained from {@link #getPathFilter()}.
+	 *
+	 * @param filter
+	 *            the tree filter to apply.
+	 */
+	public void setPathFilter(TreeFilter filter) {
+		pathFilter = filter != null ? filter : TreeFilter.ALL;
+	}
+
+	/** @return the current path filter. */
+	public TreeFilter getPathFilter() {
+		return pathFilter;
+	}
+
 	/**
 	 * Flush the underlying output stream of this formatter.
 	 *
@@ -230,6 +322,208 @@ public class DiffFormatter {
 		out.flush();
 	}
 
+	/** Release the internal ObjectReader state. */
+	public void release() {
+		if (reader != null)
+			reader.release();
+	}
+
+	/**
+	 * Determine the differences between two trees.
+	 *
+	 * No output is created, instead only the file paths that are different are
+	 * returned. Callers may choose to format these paths themselves, or convert
+	 * them into {@link FileHeader} instances with a complete edit list by
+	 * calling {@link #toFileHeader(DiffEntry)}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @return the paths that are different.
+	 * @throws IOException
+	 *             trees cannot be read or file contents cannot be read.
+	 */
+	public List<DiffEntry> scan(AnyObjectId a, AnyObjectId b)
+			throws IOException {
+		assertHaveRepository();
+
+		RevWalk rw = new RevWalk(reader);
+		return scan(rw.parseTree(a), rw.parseTree(b));
+	}
+
+	/**
+	 * Determine the differences between two trees.
+	 *
+	 * No output is created, instead only the file paths that are different are
+	 * returned. Callers may choose to format these paths themselves, or convert
+	 * them into {@link FileHeader} instances with a complete edit list by
+	 * calling {@link #toFileHeader(DiffEntry)}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @return the paths that are different.
+	 * @throws IOException
+	 *             trees cannot be read or file contents cannot be read.
+	 */
+	public List<DiffEntry> scan(RevTree a, RevTree b) throws IOException {
+		assertHaveRepository();
+
+		CanonicalTreeParser aParser = new CanonicalTreeParser();
+		CanonicalTreeParser bParser = new CanonicalTreeParser();
+
+		aParser.reset(reader, a);
+		bParser.reset(reader, b);
+
+		return scan(aParser, bParser);
+	}
+
+	/**
+	 * Determine the differences between two trees.
+	 *
+	 * No output is created, instead only the file paths that are different are
+	 * returned. Callers may choose to format these paths themselves, or convert
+	 * them into {@link FileHeader} instances with a complete edit list by
+	 * calling {@link #toFileHeader(DiffEntry)}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @return the paths that are different.
+	 * @throws IOException
+	 *             trees cannot be read or file contents cannot be read.
+	 */
+	public List<DiffEntry> scan(AbstractTreeIterator a, AbstractTreeIterator b)
+			throws IOException {
+		assertHaveRepository();
+
+		TreeWalk walk = new TreeWalk(reader);
+		walk.reset();
+		walk.addTree(a);
+		walk.addTree(b);
+		walk.setRecursive(true);
+
+		if (pathFilter == TreeFilter.ALL) {
+			walk.setFilter(TreeFilter.ANY_DIFF);
+		} else if (pathFilter instanceof FollowFilter) {
+			walk.setFilter(pathFilter);
+		} else {
+			walk.setFilter(AndTreeFilter
+					.create(pathFilter, TreeFilter.ANY_DIFF));
+		}
+
+		List<DiffEntry> files = DiffEntry.scan(walk);
+		if (pathFilter instanceof FollowFilter && isAdd(files)) {
+			// The file we are following was added here, find where it
+			// came from so we can properly show the rename or copy,
+			// then continue digging backwards.
+			//
+			a.reset();
+			b.reset();
+			walk.reset();
+			walk.addTree(a);
+			walk.addTree(b);
+			walk.setFilter(TreeFilter.ANY_DIFF);
+
+			if (renameDetector == null)
+				setDetectRenames(true);
+			files = updateFollowFilter(detectRenames(DiffEntry.scan(walk)));
+
+		} else if (renameDetector != null)
+			files = detectRenames(files);
+
+		return files;
+	}
+
+	private List<DiffEntry> detectRenames(List<DiffEntry> files)
+			throws IOException {
+		renameDetector.reset();
+		renameDetector.addAll(files);
+		return renameDetector.compute(reader, progressMonitor);
+	}
+
+	private boolean isAdd(List<DiffEntry> files) {
+		String oldPath = ((FollowFilter) pathFilter).getPath();
+		for (DiffEntry ent : files) {
+			if (ent.getChangeType() == ADD && ent.getNewPath().equals(oldPath))
+				return true;
+		}
+		return false;
+	}
+
+	private List<DiffEntry> updateFollowFilter(List<DiffEntry> files) {
+		String oldPath = ((FollowFilter) pathFilter).getPath();
+		for (DiffEntry ent : files) {
+			if (isRename(ent) && ent.getNewPath().equals(oldPath)) {
+				pathFilter = FollowFilter.create(ent.getOldPath());
+				return Collections.singletonList(ent);
+			}
+		}
+		return Collections.emptyList();
+	}
+
+	private static boolean isRename(DiffEntry ent) {
+		return ent.getChangeType() == RENAME || ent.getChangeType() == COPY;
+	}
+
+	/**
+	 * Format the differences between two trees.
+	 *
+	 * The patch is expressed as instructions to modify {@code a} to make it
+	 * {@code b}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @throws IOException
+	 *             trees cannot be read, file contents cannot be read, or the
+	 *             patch cannot be output.
+	 */
+	public void format(AnyObjectId a, AnyObjectId b) throws IOException {
+		format(scan(a, b));
+	}
+
+	/**
+	 * Format the differences between two trees.
+	 *
+	 * The patch is expressed as instructions to modify {@code a} to make it
+	 * {@code b}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @throws IOException
+	 *             trees cannot be read, file contents cannot be read, or the
+	 *             patch cannot be output.
+	 */
+	public void format(RevTree a, RevTree b) throws IOException {
+		format(scan(a, b));
+	}
+
+	/**
+	 * Format the differences between two trees.
+	 *
+	 * The patch is expressed as instructions to modify {@code a} to make it
+	 * {@code b}.
+	 *
+	 * @param a
+	 *            the old (or previous) side.
+	 * @param b
+	 *            the new (or updated) side.
+	 * @throws IOException
+	 *             trees cannot be read, file contents cannot be read, or the
+	 *             patch cannot be output.
+	 */
+	public void format(AbstractTreeIterator a, AbstractTreeIterator b)
+			throws IOException {
+		format(scan(a, b));
+	}
+
 	/**
 	 * Format a patch script from a list of difference entries.
 	 *
@@ -272,13 +566,10 @@ public class DiffFormatter {
 
 	private String format(AbbreviatedObjectId id) {
 		if (id.isComplete() && db != null) {
-			ObjectReader reader = db.newObjectReader();
 			try {
 				id = reader.abbreviate(id.toObjectId(), abbreviationLength);
 			} catch (IOException cannotAbbreviate) {
 				// Ignore this. We'll report the full identity.
-			} finally {
-				reader.release();
 			}
 		}
 		return id.name();
@@ -319,22 +610,22 @@ public class DiffFormatter {
 			end = head.getHunks().get(0).getStartOffset();
 		out.write(head.getBuffer(), start, end - start);
 		if (head.getPatchType() == PatchType.UNIFIED)
-			formatEdits(a, b, head.toEditList());
+			format(head.toEditList(), a, b);
 	}
 
 	/**
 	 * Formats a list of edits in unified diff format
 	 *
+	 * @param edits
+	 *            some differences which have been calculated between A and B
 	 * @param a
 	 *            the text A which was compared
 	 * @param b
 	 *            the text B which was compared
-	 * @param edits
-	 *            some differences which have been calculated between A and B
 	 * @throws IOException
 	 */
-	public void formatEdits(final RawText a, final RawText b,
-			final EditList edits) throws IOException {
+	public void format(final EditList edits, final RawText a, final RawText b)
+			throws IOException {
 		for (int curIdx = 0; curIdx < edits.size();) {
 			Edit curEdit = edits.get(curIdx);
 			final int endIdx = findCombinedEnd(edits, curIdx);
@@ -513,7 +804,7 @@ public class DiffFormatter {
 	 * @throws MissingObjectException
 	 *             one of the blobs referenced by the DiffEntry is missing.
 	 */
-	public FileHeader createFileHeader(DiffEntry ent) throws IOException,
+	public FileHeader toFileHeader(DiffEntry ent) throws IOException,
 			CorruptObjectException, MissingObjectException {
 		return createFormatResult(ent).header;
 	}
@@ -542,24 +833,14 @@ public class DiffFormatter {
 			type = PatchType.UNIFIED;
 
 		} else {
-			if (db == null)
-				throw new IllegalStateException(
-						JGitText.get().repositoryIsRequired);
+			assertHaveRepository();
 
-			ObjectReader reader = db.newObjectReader();
-			byte[] aRaw, bRaw;
-			try {
-				aRaw = open(reader, //
-						ent.getOldPath(), //
-						ent.getOldMode(), //
-						ent.getOldId());
-				bRaw = open(reader, //
-						ent.getNewPath(), //
-						ent.getNewMode(), //
-						ent.getNewId());
-			} finally {
-				reader.release();
-			}
+			byte[] aRaw = open(ent.getOldPath(), //
+					ent.getOldMode(), //
+					ent.getOldId());
+			byte[] bRaw = open(ent.getNewPath(), //
+					ent.getNewMode(), //
+					ent.getNewId());
 
 			if (aRaw == BINARY || bRaw == BINARY //
 					|| RawText.isBinary(aRaw) || RawText.isBinary(bRaw)) {
@@ -592,8 +873,13 @@ public class DiffFormatter {
 		return res;
 	}
 
-	private byte[] open(ObjectReader reader, String path, FileMode mode,
-			AbbreviatedObjectId id) throws IOException {
+	private void assertHaveRepository() {
+		if (db == null)
+			throw new IllegalStateException(JGitText.get().repositoryIsRequired);
+	}
+
+	private byte[] open(String path, FileMode mode, AbbreviatedObjectId id)
+			throws IOException {
 		if (mode == FileMode.MISSING)
 			return EMPTY;
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
index 9c1310ab81..bd4a5e2381 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
@@ -100,11 +100,11 @@ public class RenameDetector {
 		}
 	};
 
-	private List<DiffEntry> entries = new ArrayList<DiffEntry>();
+	private List<DiffEntry> entries;
 
-	private List<DiffEntry> deleted = new ArrayList<DiffEntry>();
+	private List<DiffEntry> deleted;
 
-	private List<DiffEntry> added = new ArrayList<DiffEntry>();
+	private List<DiffEntry> added;
 
 	private boolean done;
 
@@ -137,6 +137,8 @@ public class RenameDetector {
 
 		DiffConfig cfg = repo.getConfig().get(DiffConfig.KEY);
 		renameLimit = cfg.getRenameLimit();
+
+		reset();
 	}
 
 	/**
@@ -305,19 +307,39 @@ public class RenameDetector {
 	 */
 	public List<DiffEntry> compute(ProgressMonitor pm) throws IOException {
 		if (!done) {
+			ObjectReader reader = repo.newObjectReader();
+			try {
+				return compute(reader, pm);
+			} finally {
+				reader.release();
+			}
+		}
+		return Collections.unmodifiableList(entries);
+	}
+
+	/**
+	 * Detect renames in the current file set.
+	 *
+	 * @param reader
+	 *            reader to obtain objects from the repository with.
+	 * @param pm
+	 *            report progress during the detection phases.
+	 * @return an unmodifiable list of {@link DiffEntry}s representing all files
+	 *         that have been changed.
+	 * @throws IOException
+	 *             file contents cannot be read from the repository.
+	 */
+	public List<DiffEntry> compute(ObjectReader reader, ProgressMonitor pm)
+			throws IOException {
+		if (!done) {
 			done = true;
 
 			if (pm == null)
 				pm = NullProgressMonitor.INSTANCE;
-			ObjectReader reader = repo.newObjectReader();
-			try {
 				breakModifies(reader, pm);
 				findExactRenames(pm);
 				findContentRenames(reader, pm);
 				rejoinModifies(pm);
-			} finally {
-				reader.release();
-			}
 
 			entries.addAll(added);
 			added = null;
@@ -330,6 +352,14 @@ public class RenameDetector {
 		return Collections.unmodifiableList(entries);
 	}
 
+	/** Reset this rename detector for another rename detection pass. */
+	public void reset() {
+		entries = new ArrayList<DiffEntry>();
+		deleted = new ArrayList<DiffEntry>();
+		added = new ArrayList<DiffEntry>();
+		done = false;
+	}
+
 	private void breakModifies(ObjectReader reader, ProgressMonitor pm)
 			throws IOException {
 		if (breakScore <= 0)