unpack-trees traversing with index quite broken...

Linus,

I found an issue I do not know how to resolve.

Suppose you try to merge these three trees:

 - Tree #1 (ancestor)
   t   tree, in which there is an entry f that is a blob
   t/f blob

 - Tree #2 (ours)
   t   blob
   t-f blob

 - Tree #3 (theirs)
   t-f blob

The index matches our tree.

The callchain that causes "read-tree -m -u #1 #2 #3" misbehave looks like this.

unpack_trees()
->traverse_trees()
  entry[0] = "t" (tree taken from Tree #1)
  entry[1] = "t" (blob taken from Tree #2)
  entry[2] = nothing
  ->unpack_callback()
    ce = "t" (blob taken from the index)
    ->unpack_nondirectories()
      src[0] = "t" (blob from the index)
      src[1] = conflict (tree taken from Tree #1)
      src[2] = "t" (blob taken from Tree #2)
      src[3] = NULL
    ->call_unpack_fn()
      This callback is perfectly fine.
    /* Now handle any directories.. unpack-trees.c, ll.336- */
    ->traverse_trees_recursive()
      Now we stepped into tree "t".
      ->traverse_trees()
        entry[0] = "f" (blob from "t/" tree in Tree #1)
        entry[1] = nothing (Tree #2 does not have "t/" subtree)
        entry[2] = nothing (Tree #3 does not have "t/" subtree)
        ->unpack_callback()
          ce = "t-f" (blob taken from the index)
          ->compare_entry(ce, entry[])
          <- "t-f" comes anything in "t/" directory, return negative

          Because we are processing "t/something" at this level, and
          "t-f" that should come earlier than any "t/something", we
          assume that there is no matching entries in the trees.
          ->unpack_index_entry(ce = "t-f")
            ->call_unpack_fn()
              This callback is utterly wrong.  "t-f" from the index
              has a matching entry in Tree #2 and Tree #3, but we
              haven't seen them yet!

At first, I thought that we could fudge this particular example by noticing that "t-f" is earlier only because "t-f" sorts before "t/", the path-prefix of the problematic level, and pretend the negative return from compare_entry() as if it was positive (i.e. deferring the processing of the index entry). While this approach lets the problematic level correctly feed only "t/f" to call_unpack_fn() and come back, and the rest may proceed cleanly for this particular case, I do not think it is the right solution.

If Tree #3 had another tree "t/" in it, the situation would look like this instead:

 - Tree #1 (ancestor)
   t   tree, in which there is an entry f that is a blob
   t/f blob

 - Tree #2 (ours, matches the index)
   t   blob
   t-f blob

 - Tree #3 (theirs)
   t-f blob
   t   tree, in which there is an entry f that is a blob    

Since traverse_trees() wants to walk the trees in parallel, never seeking back, I do not think it would feed t-f from Tree #2 and Tree #3 to the unpack_callback() sanely. Worse yet, the logic to walk the index in parallel while this is happening (i.e. "Are we supposed to look at the index too?" part) does not want to seek o->pos pointer back either, so I am stuck X-<...