git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 02/11] vcs-svn: Skeleton of an svn delta parser

From
Jonathan Nieder <jrnieder@gmail.com>
Date
Oct 13, 2010, 09:21 UTC
Message-ID
<20101013092143.GC32608@burratino>
In-Reply-To
<20101013091714.GA32608@burratino>

A delta in the subversion delta (svndiff0) format consists of the magic bytes SVN\0 followed by a sequence of windows, each beginning with a window header consisting of five integers (with variable-length representation):

	source view offset
	source view length
	output length
	instructions length
	auxiliary data length

Add an svndiff0_apply() function and test-svn-fe -d commandline tool to parse such a delta in the special case of not including any instructions or auxiliary data.

Later patches will add features to turn this into a fully functional delta applier, for use by svn-fe in parsing the streams produced by "svnrdump dump" and "svnadmin dump --deltas".

Helped-by: Ramkumar Ramachandra <artagnon@gmail.com>
Helped-by: David Barr <david.barr@cordelta.com>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
---
 Makefile          |    4 +-
 t/t9011-svn-da.sh |   82 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 test-svn-fe.c     |   39 ++++++++++++++++++++----
 vcs-svn/svndiff.c |   64 +++++++++++++++++++++++++++++++++++++++++
 vcs-svn/svndiff.h |    9 ++++++
 5 files changed, 189 insertions(+), 9 deletions(-)
 create mode 100755 t/t9011-svn-da.sh
 create mode 100644 vcs-svn/svndiff.h
diff --git a/Makefile b/Makefile
index d99da33..966f5c7 100644
--- a/Makefile
+++ b/Makefile
@@ -1766,7 +1766,7 @@ XDIFF_OBJS = xdiff/xdiffi.o xdiff/xprepare.o xdiff/xutils.o xdiff/xemit.o \
 	xdiff/xmerge.o xdiff/xpatience.o
 VCSSVN_OBJS = vcs-svn/string_pool.o vcs-svn/line_buffer.o \
 	vcs-svn/repo_tree.o vcs-svn/fast_export.o vcs-svn/svndump.o \
-	vcs-svn/sliding_window.o
+	vcs-svn/sliding_window.o vcs-svn/svndiff.o
 OBJECTS := $(GIT_OBJS) $(XDIFF_OBJS) $(VCSSVN_OBJS)
 
 dep_files := $(foreach f,$(OBJECTS),$(dir $f).depend/$(notdir $f).d)
@@ -1893,7 +1893,7 @@ xdiff-interface.o $(XDIFF_OBJS): \
 $(VCSSVN_OBJS): \
 	vcs-svn/obj_pool.h vcs-svn/trp.h vcs-svn/string_pool.h \
 	vcs-svn/line_buffer.h vcs-svn/repo_tree.h vcs-svn/fast_export.h \
-	vcs-svn/svndump.h vcs-svn/sliding_window.h
+	vcs-svn/sliding_window.h vcs-svn/svndump.h vcs-svn/svndiff.h
 endif
 
 exec_cmd.s exec_cmd.o: EXTRA_CPPFLAGS = \
diff --git a/t/t9011-svn-da.sh b/t/t9011-svn-da.sh
new file mode 100755
index 0000000..8dccd16
--- /dev/null
+++ b/t/t9011-svn-da.sh
@@ -0,0 +1,82 @@
+#!/bin/sh
+
+test_description='test handling of deltas by dumpfile importer'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	>empty &&
+	printf foo >preimage
+'
+
+test_expect_success 'reject empty delta' '
+	test_must_fail test-svn-fe -d preimage empty 0
+'
+
+test_expect_success 'delta can empty file' '
+	printf "SVNQ" | q_to_nul >clear.delta &&
+	test-svn-fe -d preimage clear.delta 4 >actual &&
+	test_cmp empty actual
+'
+
+test_expect_success 'one-window empty delta' '
+	printf "SVNQ%s" "QQQQQ" | q_to_nul >clear.onewindow &&
+	test-svn-fe -d preimage clear.onewindow 9 >actual &&
+	test_cmp empty actual
+'
+
+test_expect_success 'incomplete window header' '
+	printf "SVNQ%s" "QQQQQ" | q_to_nul >clear.onewindow &&
+	printf "SVNQ%s" "QQ" | q_to_nul >clear.partialwindow &&
+	test_must_fail test-svn-fe -d preimage clear.onewindow 6 &&
+	test_must_fail test-svn-fe -d preimage clear.partialwindow 6
+'
+
+test_expect_success 'declared delta longer than actual delta' '
+	printf "SVNQ%s" "QQQQQ" | q_to_nul >clear.onewindow &&
+	printf "SVNQ%s" "QQ" | q_to_nul >clear.partialwindow &&
+	test_must_fail test-svn-fe -d preimage clear.onewindow 14 &&
+	test_must_fail test-svn-fe -d preimage clear.partialwindow 9
+'
+
+test_expect_success 'two-window empty delta' '
+	printf "SVNQ%s%s" "QQQQQ" "QQQQQ" | q_to_nul >clear.twowindow &&
+	test-svn-fe -d preimage clear.twowindow 14 >actual &&
+	test_must_fail test-svn-fe -d preimage clear.twowindow 13 &&
+	test_cmp empty actual
+'
+
+test_expect_success 'noisy zeroes' '
+	printf "SVNQ%s" \
+		"RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRQQQQQ" |
+		tr R "\200" |
+		q_to_nul >clear.noisy &&
+	len=$(wc -c <clear.noisy) &&
+	test-svn-fe -d preimage clear.noisy $len &&
+	test_cmp empty actual
+'
+
+test_expect_success 'reject variable-length int in magic' '
+	printf "SVNRQ" | tr R "\200" | q_to_nul >clear.badmagic &&
+	test_must_fail test-svn-fe -d preimage clear.badmagic 5
+'
+
+test_expect_success 'truncated integer' '
+	printf "SVNQ%s%s" "QQQQQ" "QQQQRRQ" |
+		tr R "\200" |
+		q_to_nul >clear.fullint &&
+	printf "SVNQ%s%s" "QQQQQ" "QQQQRR" |
+		tr RT "\201" |
+		q_to_nul >clear.partialint &&
+	test_must_fail test-svn-fe -d preimage clear.fullint 15 &&
+	test-svn-fe -d preimage clear.fullint 16 &&
+	test_must_fail test-svn-fe -d preimage clear.partialint 15
+'
+
+test_expect_success 'nonempty (but unused) preimage view' '
+	printf "SVNQ%b" "Q\003QQQ" | q_to_nul >clear.readpreimage &&
+	test-svn-fe -d preimage clear.readpreimage 9 >actual &&
+	test_cmp empty actual
+'
+
+test_done
diff --git a/test-svn-fe.c b/test-svn-fe.c
index 77cf78a..197a2c3 100644
--- a/test-svn-fe.c
+++ b/test-svn-fe.c
@@ -4,14 +4,39 @@
 
 #include "git-compat-util.h"
 #include "vcs-svn/svndump.h"
+#include "vcs-svn/svndiff.h"
+#include "vcs-svn/line_buffer.h"
 
 int main(int argc, char *argv[])
 {
-	if (argc != 2)
-		usage("test-svn-fe <file>");
-	svndump_init(argv[1]);
-	svndump_read(NULL);
-	svndump_deinit();
-	svndump_reset();
-	return 0;
+	static const char test_svnfe_usage[] =
+		"test-svn-fe (<dumpfile> | [-d] <preimage> <delta> <len>)";
+	if (argc < 2)
+		usage(test_svnfe_usage);
+	if (argc == 2) {
+		svndump_init(argv[1]);
+		svndump_read(NULL);
+		svndump_deinit();
+		svndump_reset();
+		return 0;
+	}
+	if (argc == 5 && !strcmp(argv[1], "-d")) {
+		struct line_buffer preimage = LINE_BUFFER_INIT;
+		struct line_buffer delta = LINE_BUFFER_INIT;
+		if (buffer_init(&preimage, argv[2]))
+			die_errno("cannot open preimage");
+		if (buffer_init(&delta, argv[3]))
+			die_errno("cannot open delta");
+		if (svndiff0_apply(&delta, (off_t) strtoull(argv[4], NULL, 0),
+				   &preimage, stdout))
+			return 1;
+		if (buffer_deinit(&preimage))
+			die_errno("cannot close preimage");
+		if (buffer_deinit(&delta))
+			die_errno("cannot close delta");
+		buffer_reset(&preimage);
+		buffer_reset(&delta);
+		return 0;
+	}
+	usage(test_svnfe_usage);
 }
diff --git a/vcs-svn/svndiff.c b/vcs-svn/svndiff.c
index 36d2b30..e572a93 100644
--- a/vcs-svn/svndiff.c
+++ b/vcs-svn/svndiff.c
@@ -12,6 +12,7 @@
  * See http://svn.apache.org/repos/asf/subversion/trunk/notes/svndiff.
  *
  * svndiff0 ::= 'SVN\0' window window*;
+ * window ::= int int int int int instructions inline_data;
  * int ::= highdigit* lowdigit;
  * highdigit ::= # binary 1000 0000 OR-ed with 7 bit value;
  * lowdigit ::= # 7 bit value;
@@ -76,3 +77,66 @@ static int parse_int(const char **buf, size_t *result, const char *end)
 	return error("Invalid instruction: incomplete integer %"PRIu64,
 		     (uint64_t) rv);
 }
+
+static int read_offset(struct line_buffer *in, off_t *result, off_t *len)
+{
+	uintmax_t val;
+	if (read_int(in, &val, len))
+		return -1;
+	if (val > maximum_signed_value_of_type(off_t))
+		return error("Unrepresentable offset: %"PRIuMAX, val);
+	*result = val;
+	return 0;
+}
+
+static int read_length(struct line_buffer *in, size_t *result, off_t *len)
+{
+	uintmax_t val;
+	if (read_int(in, &val, len))
+		return -1;
+	if (val > SIZE_MAX)
+		return error("Unrepresentable length: %"PRIuMAX, val);
+	*result = val;
+	return 0;
+}
+
+static int apply_one_window(struct line_buffer *delta, off_t *delta_len)
+{
+	size_t out_len;
+	size_t instructions_len;
+	size_t data_len;
+	assert(delta_len);
+
+	/* "source view" offset and length already handled; */
+	if (read_length(delta, &out_len, delta_len) ||
+	    read_length(delta, &instructions_len, delta_len) ||
+	    read_length(delta, &data_len, delta_len))
+		return -1;
+	if (instructions_len > 0)
+		return error("What do you think I am?  A delta applier?");
+	if (data_len > 0)
+		return error("No support for inline data yet");
+	return 0;
+}
+
+int svndiff0_apply(struct line_buffer *delta, off_t delta_len,
+		   struct line_buffer *preimage, FILE *postimage)
+{
+	assert(delta && preimage && postimage);
+
+	if (read_magic(delta, &delta_len))
+		return -1;
+	while (delta_len > 0) {	/* For each window: */
+		off_t pre_off;
+		size_t pre_len;
+		if (read_offset(delta, &pre_off, &delta_len) ||
+		    read_length(delta, &pre_len, &delta_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);
+	}
+	return 0;
+}
diff --git a/vcs-svn/svndiff.h b/vcs-svn/svndiff.h
new file mode 100644
index 0000000..a986099
--- /dev/null
+++ b/vcs-svn/svndiff.h
@@ -0,0 +1,9 @@
+#ifndef SVNDIFF_H_
+#define SVNDIFF_H_
+
+#include "line_buffer.h"
+
+extern int svndiff0_apply(struct line_buffer *delta, off_t delta_len,
+			  struct line_buffer *preimage, FILE *postimage);
+
+#endif

-- 
1.7.2.3
Previous: Jonathan NiederNext: Jonathan Nieder
Message 65 of 79 in “Resurrect rr/svn-export”
  1. 0/8 Resurrect rr/svn-exportRamkumar Ramachandra, Jul 15, 2010
  2. 1/8 Export parse_date_basic() to convert a date string to timestampRamkumar Ramachandra, Jul 15, 2010
  3. Jonathan NiederJul 15, 2010
  4. Junio C HamanoJul 15, 2010
  5. 2/8 Introduce vcs-svn libRamkumar Ramachandra, Jul 15, 2010
  6. Jonathan NiederJul 15, 2010
  7. Ramkumar RamachandraJul 15, 2010
  8. 3/8 Add memory pool libraryRamkumar Ramachandra, Jul 15, 2010
  9. Jonathan NiederJul 15, 2010
  10. Ramkumar RamachandraJul 15, 2010
  11. 4/8 Add treap implementationRamkumar Ramachandra, Jul 15, 2010
  12. Jonathan NiederJul 15, 2010
  13. Ramkumar RamachandraJul 15, 2010
  14. 5/8 Add string-specific memory poolRamkumar Ramachandra, Jul 15, 2010
  15. 6/8 Add stream helper libraryRamkumar Ramachandra, Jul 15, 2010
  16. Jonathan NiederJul 15, 2010
  17. 7/8 Add infrastructure to write revisions in fast-export formatRamkumar Ramachandra, Jul 15, 2010
  18. Jonathan NiederJul 15, 2010
  19. 8/8 Add SVN dump parserRamkumar Ramachandra, Jul 15, 2010
  20. Jonathan NiederJul 15, 2010
  21. Jonathan NiederJul 15, 2010
  22. Jonathan NiederJul 16, 2010
  23. 3/9 Add memory pool libraryJonathan Nieder, Jul 16, 2010
  24. 4/9 Add treap implementationJonathan Nieder, Jul 16, 2010
  25. Jonathan NiederJul 16, 2010
  26. 0/10 rr/svn-export rerollJonathan Nieder, Aug 9, 2010
  27. 01/10 Export parse_date_basic() to convert a date string to timestampJonathan Nieder, Aug 9, 2010
  28. 02/10 Introduce vcs-svn libJonathan Nieder, Aug 9, 2010
  29. 03/10 Add memory pool libraryJonathan Nieder, Aug 9, 2010
  30. 04/10 Add treap implementationJonathan Nieder, Aug 9, 2010
  31. Junio C HamanoAug 12, 2010
  32. Jonathan NiederAug 12, 2010
  33. Jonathan NiederAug 12, 2010
  34. Junio C HamanoAug 12, 2010
  35. 05/10 Add string-specific memory poolJonathan Nieder, Aug 9, 2010
  36. Junio C HamanoAug 12, 2010
  37. Jonathan NiederAug 12, 2010
  38. 06/10 Add stream helper libraryJonathan Nieder, Aug 9, 2010
  39. 07/10 Infrastructure to write revisions in fast-export formatJonathan Nieder, Aug 9, 2010
  40. 08/10 SVN dump parserJonathan Nieder, Aug 9, 2010
  41. Junio C HamanoAug 12, 2010
  42. PATCH 09/10] Update svn-fe manualJonathan Nieder, Aug 9, 2010
  43. 10/10 svn-fe manual: Clarify warning about deltas in dump filesJonathan Nieder, Aug 9, 2010
  44. Ramkumar RamachandraAug 10, 2010
  45. Jonathan NiederAug 11, 2010
  46. 00/16 svn delta applierJonathan Nieder, Oct 11, 2010
  47. 01/16 vcs-svn: Eliminate global byte_buffer[] arrayJonathan Nieder, Oct 11, 2010
  48. 03/16 vcs-svn: Collect line_buffer data in a structJonathan Nieder, Oct 11, 2010
  49. 04/16 vcs-svn: Teach line_buffer to handle multiple input filesJonathan Nieder, Oct 11, 2010
  50. 05/16 vcs-svn: Make buffer_skip_bytes() report partial readsJonathan Nieder, Oct 11, 2010
  51. 06/16 vcs-svn: Improve support for reading large filesJonathan Nieder, Oct 11, 2010
  52. 07/16 vcs-svn: Add binary-safe read() functionJonathan Nieder, Oct 11, 2010
  53. 08/16 vcs-svn: Let callers peek ahead to find stream endJonathan Nieder, Oct 11, 2010
  54. 09/16 vcs-svn: Allow input errors to be detected earlyJonathan Nieder, Oct 11, 2010
  55. 10/16 vcs-svn: Allow character-oriented inputJonathan Nieder, Oct 11, 2010
  56. 11/16 vcs-svn: Add code to maintain a sliding view of a fileJonathan Nieder, Oct 11, 2010
  57. 12/16 vcs-svn: Learn to parse variable-length integersJonathan Nieder, Oct 11, 2010
  58. 13/16 vcs-svn: Learn to check for SVN\0 magicJonathan Nieder, Oct 11, 2010
  59. 14/16 compat: helper for detecting unsigned overflowJonathan Nieder, Oct 11, 2010
  60. 15/16 t9010 (svn-fe): Eliminate dependency on svn perl bindingsJonathan Nieder, Oct 11, 2010
  61. 02/16 vcs-svn: Replace buffer_read_string() memory pool with a strbufJonathan Nieder, Oct 11, 2010
  62. vcs-svn: Add svn delta parserJonathan Nieder, Oct 11, 2010
  63. 0/11 Building up the delta parserJonathan Nieder, Oct 13, 2010
  64. 01/11 fixup! vcs-svn: Learn to parse variable-length integersJonathan Nieder, Oct 13, 2010
  65. 02/11 vcs-svn: Skeleton of an svn delta parserJonathan Nieder, Oct 13, 2010
  66. 03/11 vcs-svn: Read the preimage while applying deltasJonathan Nieder, Oct 13, 2010
  67. Sam VilainOct 14, 2010
  68. Jonathan NiederOct 14, 2010
  69. 04/11 vcs-svn: Read inline data from deltasJonathan Nieder, Oct 13, 2010
  70. 05/11 vcs-svn: Read instructions from deltasJonathan Nieder, Oct 13, 2010
  71. 06/11 vcs-svn: Implement copyfrom_data delta instructionJonathan Nieder, Oct 13, 2010
  72. 07/11 vcs-svn: Check declared number of output bytesJonathan Nieder, Oct 13, 2010
  73. 08/11 vcs-svn: Reject deltas that do not consume all inline dataJonathan Nieder, Oct 13, 2010
  74. 09/11 vcs-svn: Let deltas use data from postimageJonathan Nieder, Oct 13, 2010
  75. 10/11 vcs-svn: Reject deltas that read past end of preimageJonathan Nieder, Oct 13, 2010
  76. 11/11 vcs-svn: Allow deltas to copy from preimageJonathan Nieder, Oct 13, 2010
  77. 11/11 vcs-svn: Allow deltas to copy from preimageJonathan Nieder, Oct 13, 2010
  78. Ramkumar RamachandraOct 18, 2010
  79. Jonathan NiederOct 18, 2010

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.