Bug in merge-ort (rename detection can have collisions?)

[Glen Choo <chooglen@google.com>]

(I'm not 100% what the bug _is_, only that there is one.)

= Report

At $DAYJOB, there was a report that "git merge" was failing on certain
branches. Fortunately, the repo is publicly accessible, so I can share
the full reproduction recipe:

  git clone https://android.googlesource.com/platform/external/tensorflow tensorflow &&
  cd tensorflow &&
  git merge origin/upstream-master # HEAD is at origin/master

This gives:

  Performing inexact rename detection: 100% (4371280/4371280), done.
  Performing inexact rename detection: 100% (12529218/12529218), done.
  Assertion failed: (ci->filemask == 2 || ci->filemask == 4), function apply_directory_rename_modifications, file merge-ort.c, line 2410. 

This bug seems specific to merge-ort; "git merge -s recursive
origin/upstream-master" seems to work as expected.

In case the branches have changed since then, here are the commit ids:

  $ git rev-parse origin/master
  68e55281824e8a79fa67e1a3061f39bd4c4b2e57
  $ git rev-parse origin/upstream-master
  0be5bb09aeeff3a6825842326fadc8159a5553ab
  $ git merge-base 68e55281824e8a79fa67e1a3061f39bd4c4b2e57 0be5bb09aeeff3a6825842326fadc8159a5553ab
  8e819019081f39d83df42baba4acfced3abf3f90

= Interesting info

I don't understand the merge-ort code enough to understand what's going
on, but I was able to find some (hopefully helpful) details. I added
this log line just above the offending assert() call:

	trace2_printf("0 %s, 1 %s, 2 %s, fm %d, dm %d", ci->pathnames[0],
    ci->pathnames[1], ci->pathnames[2], ci->filemask, ci->dirmask);

Here are the lines I thought were suspicious:

  0 <path1>, 1 <path1>, 2 <path1>, fm 2, dm 0
  [...]
  0 <path2>, 1 <path1>, 2 <path2>, fm 6, dm 0 # this is the last line

Notice that the last line detected a rename from <path2> to <path1>, but
we already saw <path1> earlier.

IIUC "(ci->filemask == 2 || ci->filemask == 4)" can be read as "the path
either exists on only the left side or only the right side of the
merge", so ci->filemask == 6 should mean "the path exists on both sides
of the merge"?

"-s recursive" seems to handle the rename just fine (it picks <path2>
IIRC).

I also dug into each commit to see which paths were present:

  head="origin/master"
  other="origin/upstream-master"
  merge_base="$(git merge-base origin/master origin/upstream-master)"
  path1="tensorflow/lite/g3doc/convert/metadata_writer_tutorial.ipynb"
  path2="tensorflow/lite/g3doc/models/convert/metadata_writer_tutorial.ipynb"

  git rev-parse "$head:$path1" # (exists)
  git rev-parse "$head:$path2" # (doesn't exist)

  git rev-parse "$other:$path1" # (doesn't exist)
  git rev-parse "$other:$path2" # (exists)

  git rev-parse "$merge_base:$path1" # (doesn't exist)
  git rev-parse "$merge_base:$path2" # (doesn't exist)

i.e. both files are new and are renames of each other. I haven't tried
using this property to create a minimally-reproducing recipe though.