libgit2/libgit2 — pull request #1377 by phkelley (2013-03-01 14:07:33+00:00)
Title: Rewrite the tree iterator for fuller ignorecase support

This is the first draft of the work I've been doing to improve the ignorecase support of the tree iterator.

When we originally added ignorecase support to libgit2, the tree iterator didn't support ignorecase natively and so any time its results were merge joined with the results from another iterator that did support ignorecase (index, workdir), we had to spool-and-sort the results from the tree iterator before starting the merge join.

At some point in the last few months @arrbee added ignorecase support to the tree iterator to prevent this spool-and-sort. Rather than spool-and-sorting the entire result of the enumeration, we switched to icase-sorting each tree's entries as they were loaded. This is much faster, and mostly works.

The simplest failure case is when you have a root tree with two subtrees in it called "A" and "a". In "A" you have the blobs file1.txt and file3.txt. In "a" you have the blobs file2.txt and file4.txt. The old spool-and-sort would yield the following correct order:

A\file1.txt, a\file2.txt, A\file3.txt, a\file4.txt

But the more efficient approach of icase-sorting each tree's entries gives an incorrect order:

A\file1.txt, A\file3.txt, a\file2.txt, a\file4.txt

This can manifest itself as bad results from `git_status_foreach`, because the workdir and/or index iterators being joined against by the diff logic will enumerate items in the correct order. We also have seen users of our client tools corrupt their Git repositories by creating tree objects with duplicate entries in them. (This corruption has not yet been definitively linked back to this ignorecase issue, and I will be submitting a separate patch to check at runtime in the treebuilder that we are never writing out duplicate entries in a tree.)

This new implementation of the tree iterator keeps the faster approach of icase-sorting each tree's entries when possible (which is 99% of the time). Enumerations of items are deferred in the main loop (in `__advance`) so that they can be `strcasecmp`ed against the previous item. If there is an icase-collision, then a batch of colliding items is built. If the first item in the batch is not a tree, then it is enumerated and the remaining items in the batch are discarded. If the first item in the batch is a tree, then a multisubtree iterator is created to enumerate each item in the batch which is a tree. The multisubtree iterator has spoolandsort applied on top of it to sort these results. The tree iterator then enters a mode where it drains results from this spoolandsort-multisubtree iterator and delivers them to the caller. When the spoolandsort-multisubtree iterator is empty, the iterator returns to normal mode and picks up right after the point where the batch of items which icase-collided ended.

There are some other notable improvements to the iterator.
1. When doing an initial seek within a frame to arrive at a start position, we always know the folder/file state of what we are seeking for within the tree. As a result we can seek in the tree's vector of entries directly using `git_path_cmp`. This avoids the 'homing search' logic in tree.c.
2. When possible, we now do end-range seeks. This is possible whenever the current path part of the 'end' pathspec ends with a path separator, indicating that it is a folder.
3. Our binary search comparers for seeks never return 0, to allow us to slide to the beginning or end of a range without having to have a linear "back up" step after a successful bsearch to find the start of a range.

I am in the process of adding test cases this morning that exercise the functionality described above involving the multisubtree iterator. Right now the test suite has no coverage on it at all.