Add directory rename detection to git

This series is a reboot of the directory rename detection series that was merged to master and then reverted due to the final patch having a buggy can-skip-update check, as noted at
https://public-inbox.org/git/[email protected]/
This series based on top of master.

This updated series fixes the problem found with the previous series, and also fixes Linus' issue with unnecessary rebuilds noted at
https://public-inbox.org/git/CA+55aFzLZ3UkG5svqZwSnhNk75=fXJRkvU1m_RHBG54NOoaZPA@mail.gmail.com/

For the original details about design considerations surrounding directory rename detection, see
https://public-inbox.org/git/[email protected]/

Patches 1--28 are identical to what was previously merged to master, modulo trivial compilation fixes due to the fact that I've rebased on master which now includes commit 916bc35b29af ("tree-walk: convert tree entry functions to object_id", 2018-03-12). As such, I've retained the Reviewed-by and Signed-off-by tags for these first 28 patches. (The final patch of the original series, patch 29, has been rewritten and replaced in this series.)

The remaining eight patches are new; a brief summary:

merge-recursive: improve add_cacheinfo error handling
merge-recursive: move more is_dirty handling to merge_content
merge-recursive: avoid triggering add_cacheinfo error with dirty mod

When Junio was bit by the previous series, the code reached a detected error state that should not ever be hit in production. That was bad enough, but the problem compounded because the code simply printed a vague not-very-scary-sounding error, and returned an error code that the caller ignored (which not only proceeded to then handle other paths which might print messages causing the error to scroll off the screen, but could result in a "clean" merge). Fix issues with the error handling...and then deal with the breakage of one particular test that was triggering this codepath.

t6046: testcases checking whether updates can be skipped in a merge

Add a fairly comprehensive set of tests for the skipability of working tree updates.

merge-recursive: fix was_tracked() to quit lying with some renamed
paths
merge-recursive: fix remainder of was_dirty() to use original index

Instead of using the current index as a (rather imperfect) proxy for the state of the index just before the merge, keep a copy of the original index around so we can get correct answers to whether certain paths were tracked or dirty before the merge.

merge-recursive: make "Auto-merging" comment show for other merges
merge-recursive: fix check for skipability of working tree updates

Fix and simplify the skipability check. Due to some tests being picky about output, the first of these two patches exists to avoid triggering the "Auto-merging $FILE" message too often with the simplified logic; in the process, it fixes a pair of existing issues with when those messages are shown, making it more accurate in general.

Additional testing:

* I've re-merged all ~13k merge commits in git.git with both git-2.17.0 and this version of git, comparing the results to each other in detail. (Including stdout & stderr, as well as the output of subsequent commands like git status, git ls-files -s, git diff -M, git diff -M --staged). The only differences were in 23 merges of either git-gui or gitk which involved directory renames (e.g. git-2.17.0's merge would result in files like 'lib/tools.tcl' or 'po/ru.po' instead of the expected 'git-gui/lib/tools.tcl' or 'gitk-git/po/ru.po')

* I'm trying to do the same with linux.git, but it looks like that will take nearly a week to complete...

My biggest question:

* Is there any other testing others would like to see, in order to avoid a repeat of the pain from my previous series and allow us to safely merge this newer one?

Elijah Newren (36):
directory rename detection: basic testcases
directory rename detection: directory splitting testcases directory rename detection: testcases to avoid taking detection too
far
directory rename detection: partially renamed directory
testcase/discussion
directory rename detection: files/directories in the way of some
renames
directory rename detection: testcases checking which side did the
rename
directory rename detection: more involved edge/corner testcases directory rename detection: testcases exploring possibly suboptimal
merges
directory rename detection: miscellaneous testcases to complete
coverage
directory rename detection: tests for handling overwriting untracked
files
directory rename detection: tests for handling overwriting dirty files
merge-recursive: move the get_renames() function
merge-recursive: introduce new functions to handle rename logic
merge-recursive: fix leaks of allocated renames and diff_filepairs
merge-recursive: make !o->detect_rename codepath more obvious
merge-recursive: split out code for determining diff_filepairs
merge-recursive: make a helper function for cleanup for handle_renames
merge-recursive: add get_directory_renames()
merge-recursive: check for directory level conflicts
merge-recursive: add computation of collisions due to dir rename &
merging
merge-recursive: check for file level conflicts then get new name
merge-recursive: when comparing files, don't include trees
merge-recursive: apply necessary modifications for directory renames
merge-recursive: avoid clobbering untracked files with directory
renames
merge-recursive: fix overwriting dirty files involved in renames
merge-recursive: fix remaining directory rename + dirty overwrite
cases
directory rename detection: new testcases showcasing a pair of bugs
merge-recursive: avoid spurious rename/rename conflict from dir
renames
merge-recursive: improve add_cacheinfo error handling
merge-recursive: move more is_dirty handling to merge_content
merge-recursive: avoid triggering add_cacheinfo error with dirty mod
t6046: testcases checking whether updates can be skipped in a merge
merge-recursive: fix was_tracked() to quit lying with some renamed
paths
merge-recursive: fix remainder of was_dirty() to use original index
merge-recursive: make "Auto-merging" comment show for other merges
merge-recursive: fix check for skipability of working tree updates

 merge-recursive.c                      | 1432 ++++++++-
 merge-recursive.h                      |   28 +
 strbuf.c                               |   16 +
 strbuf.h                               |   16 +
 t/t3501-revert-cherry-pick.sh          |    7 +-
 t/t6022-merge-rename.sh                |    2 +-
 t/t6043-merge-rename-directories.sh    | 3998 ++++++++++++++++++++++++
 t/t6046-merge-skip-unneeded-updates.sh |  761 +++++
 t/t7607-merge-overwrite.sh             |    2 +-
 unpack-trees.c                         |    4 +-
 unpack-trees.h                         |    4 +
 11 files changed, 6092 insertions(+), 178 deletions(-)
 create mode 100755 t/t6043-merge-rename-directories.sh
 create mode 100755 t/t6046-merge-skip-unneeded-updates.sh

2.17.0.290.ge988e9ce2a