Subject: [PATCH 03/11] vcs-svn: Read the preimage while applying deltas

From: Jonathan Nieder <[email-masked]>
Date: Wed, 13 Oct 2010 04:30:37 -0500

The source view offset heading each svndiff0 window represents a
number of bytes past the beginning of the preimage.  Together with the
source view length, it instructs the delta applier about what portion
of the preimage instructions will refer to.  Read in that data right
away using the sliding window code.

Maybe some day we will mmap() to prepare to read data more lazily.

For compatibility with Subversion's implementation, tolerate source
view offsets pointing past the end of the preimage file (a later
patch will remove this flexibility).  For simplicity, also permit
source views that start within the preimage and end outside of it,
even though Subversion does not.

This does not teach the delta applier to read instructions or copy
data from the source view yet.  Deltas that would produce nonempty
output are still rejected.

Helped-by: Ramkumar Ramachandra <[email-masked]>
Helped-by: David Barr <[email-masked]>
Signed-off-by: Jonathan Nieder <[email-masked]>
---
It occurs to me that Sam Vilain may well have something valuable to
say about this series, having implemented something similar[1].

Sam, this series adds an svndiff0 parser for git to use in parsing
v3 dumps (which are way easier to produce with remote access to an
svn repository than v2 dumps).  The beginning of the series is at [2],
though that cover letter is out of date: now, modulo any new bugs
I've introduced with this reroll, it is known to successfully apply
all the deltas involved in a complete dump of the ASF repo.

I am interested in improvements and complaints of all kinds.

[1] http://search.cpan.org/~samv/Parse-SVNDiff-0.03/lib/Parse/SVNDiff.pm
[2] http://thread.gmane.org/gmane.comp.version-control.git/151086/focus=158731

 t/t9011-svn-da.sh |   38 ++++++++++++++++++++++++++++++++++++++
 vcs-svn/svndiff.c |   22 +++++++++++++++-------
 2 files changed, 53 insertions(+), 7 deletions(-)

diff --git a/t/t9011-svn-da.sh b/t/t9011-svn-da.sh
index 8dccd16..b9aad70 100755
--- a/t/t9011-svn-da.sh
+++ b/t/t9011-svn-da.sh
@@ -79,4 +79,42 @@ test_expect_success 'nonempty (but unused) preimage view' '
 	test_cmp empty actual
 '
 
+test_expect_success 'preimage view: right endpoint cannot backtrack' '
+	printf "SVNQ%b%b" "Q\003QQQ" "Q\002QQQ" |
+		q_to_nul >clear.backtrack &&
+	test_must_fail test-svn-fe -d preimage clear.backtrack 14
+'
+
+test_expect_success 'preimage view: left endpoint can advance' '
+	printf "SVNQ%b%b" "Q\003QQQ" "\001\002QQQ" |
+		q_to_nul >clear.preshrink &&
+	printf "SVNQ%b%b" "Q\003QQQ" "\001\001QQQ" |
+		q_to_nul >clear.shrinkbacktrack &&
+	test-svn-fe -d preimage clear.preshrink 14 >actual &&
+	test_must_fail test-svn-fe -d preimage clear.shrinkbacktrack 14 &&
+	test_cmp empty actual
+'
+
+test_expect_success 'preimage view: offsets compared by value' '
+	printf "SVNQ%b%b" "\001\001QQQ" "\0200Q\003QQQ" |
+		q_to_nul >clear.noisybacktrack &&
+	printf "SVNQ%b%b" "\001\001QQQ" "\0200\001\002QQQ" |
+		q_to_nul >clear.noisyadvance &&
+	test_must_fail test-svn-fe -d preimage clear.noisybacktrack 15
+	test-svn-fe -d preimage clear.noisyadvance 15 &&
+	test_cmp empty actual
+'
+
+test_expect_success 'preimage view: accept truncated preimage' '
+	printf "SVNQ%b" "\010QQQQ" | q_to_nul >clear.lateemptyread &&
+	printf "SVNQ%b" "\010\001QQQ" | q_to_nul >clear.latenonemptyread &&
+	printf "SVNQ%b" "\001\010QQQ" | q_to_nul >clear.longread &&
+	test-svn-fe -d preimage clear.lateemptyread 9 >actual.emptyread &&
+	test-svn-fe -d preimage clear.latenonemptyread 9 >actual.nonemptyread &&
+	test-svn-fe -d preimage clear.longread 9 >actual.longread &&
+	test_cmp empty actual.emptyread &&
+	test_cmp empty actual.nonemptyread &&
+	test_cmp empty actual.longread
+'
+
 test_done
diff --git a/vcs-svn/svndiff.c b/vcs-svn/svndiff.c
index e572a93..f2876b3 100644
--- a/vcs-svn/svndiff.c
+++ b/vcs-svn/svndiff.c
@@ -4,6 +4,7 @@
  */
 
 #include "git-compat-util.h"
+#include "sliding_window.h"
 #include "line_buffer.h"
 
 /*
@@ -122,21 +123,28 @@ static int apply_one_window(struct line_buffer *delta, off_t *delta_len)
 int svndiff0_apply(struct line_buffer *delta, off_t delta_len,
 		   struct line_buffer *preimage, FILE *postimage)
 {
+	struct view preimage_view = {preimage, 0, STRBUF_INIT};
 	assert(delta && preimage && postimage);
 
 	if (read_magic(delta, &delta_len))
-		return -1;
+		goto fail;
 	while (delta_len > 0) {	/* For each window: */
-		off_t pre_off;
+		off_t pre_off = pre_off;
 		size_t pre_len;
 		if (read_offset(delta, &pre_off, &delta_len) ||
 		    read_length(delta, &pre_len, &delta_len) ||
+		    move_window(&preimage_view, pre_off, pre_len) ||
 		    apply_one_window(delta, &delta_len))
-			return -1;
-		if (delta_len && buffer_at_eof(delta))
-			return error("Delta ends early! "
-				     "(%"PRIu64" bytes remaining)",
-				     (uint64_t) delta_len);
+			goto fail;
+		if (delta_len && buffer_at_eof(delta)) {
+			error("Delta ends early! (%"PRIu64" bytes remaining)",
+			      (uint64_t) delta_len);
+			goto fail;
+		}
 	}
+	strbuf_release(&preimage_view.buf);
 	return 0;
+ fail:
+	strbuf_release(&preimage_view.buf);
+	return -1;
 }
-- 
1.7.2.3