Re: [PATCH] fast-import: use binary search in tree_content_remove

[Jeff King <peff@peff.net>]

On Sat, Mar 10, 2007 at 10:38:33PM -0500, Shawn O. Pearce wrote:

> Well, its not necessary for you, as you aren't trying to remove
> something from your huge tree.  ;-)

Heh, I meant necessary as in "Oops, I probably just completely broke
fast-import". But I see I managed to do that anyway. :)

> Your patch is fine.  fast-import takes an "optimization" here and
> does not bother to actually delete entries from a tree until *after*

OK, that was my reading, as well; thanks for confirming.

> Jeff King's recent changes to sort trees by strictly name (and binary
> search to locate an entry) works OK up until we have to write a
> tree out that uses the funny name/mode sorting that native Git uses:

And here is a test that I believe triggers the problem (fails with my
patches, succeeds with your fix):

diff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh
index 2e1a09f..2ec68b0 100755
--- a/t/t9300-fast-import.sh
+++ b/t/t9300-fast-import.sh
@@ -501,4 +501,54 @@ test_expect_success \
     'test `git-rev-parse --verify branch^1` \
 		= `git-rev-parse --verify K^1`'
 
+###
+### series L
+###
+
+cat >input <<INPUT_END
+blob
+mark :1
+data <<EOF
+some data
+EOF
+
+blob
+mark :2
+data <<EOF
+other data
+EOF
+
+commit refs/heads/L
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+create L
+COMMIT
+
+M 644 :1 b.
+M 644 :1 b/other
+M 644 :1 ba
+
+commit refs/heads/L
+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE
+data <<COMMIT
+update L
+COMMIT
+
+M 644 :2 b.
+M 644 :2 b/other
+M 644 :2 ba
+INPUT_END
+
+cat >expect <<EXPECT_END
+:100644 100644 4268632... 55d3a52... M	b.
+:040000 040000 0ae5cac... 443c768... M	b
+:100644 100644 4268632... 55d3a52... M	ba
+EXPECT_END
+
+test_expect_success \
+    'L: verify internal tree sorting' \
+	'git-fast-import <input &&
+	 git-diff --raw L^ L >output &&
+	 diff -u expect output'
+
 test_done

> I'm plastering over the problem by resorting a tree strictly by
> name after it has been written out and the deleted entries have
> been filtered out.

I wonder if we could make this a bit cleaner by actually using the git
sort in the first place. I will take a look...

-Peff