From: Jonathan Nieder <jrnieder@gmail.com>
To: Ramkumar Ramachandra <artagnon@gmail.com>
Cc: Git Mailing List <git@vger.kernel.org>,
David Michael Barr <david.barr@cordelta.com>,
Sverre Rabbelier <srabbelier@gmail.com>
Subject: [PATCH 02/11] vcs-svn: Skeleton of an svn delta parser
Date: Wed, 13 Oct 2010 04:21:43 -0500 [thread overview]
Message-ID: <20101013092143.GC32608@burratino> (raw)
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
next prev parent reply other threads:[~2010-10-13 9:25 UTC|newest]
Thread overview: 79+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-07-15 16:22 [PATCH 0/8] Resurrect rr/svn-export Ramkumar Ramachandra
2010-07-15 16:22 ` [PATCH 1/8] Export parse_date_basic() to convert a date string to timestamp Ramkumar Ramachandra
2010-07-15 17:25 ` Jonathan Nieder
2010-07-15 22:54 ` Junio C Hamano
2010-07-15 16:22 ` [PATCH 2/8] Introduce vcs-svn lib Ramkumar Ramachandra
2010-07-15 17:46 ` Jonathan Nieder
2010-07-15 19:15 ` Ramkumar Ramachandra
2010-07-15 16:22 ` [PATCH 3/8] Add memory pool library Ramkumar Ramachandra
2010-07-15 18:57 ` Jonathan Nieder
2010-07-15 19:12 ` Ramkumar Ramachandra
2010-07-15 16:23 ` [PATCH 4/8] Add treap implementation Ramkumar Ramachandra
2010-07-15 19:09 ` Jonathan Nieder
2010-07-15 19:18 ` Ramkumar Ramachandra
2010-07-15 16:23 ` [PATCH 5/8] Add string-specific memory pool Ramkumar Ramachandra
2010-07-15 16:23 ` [PATCH 6/8] Add stream helper library Ramkumar Ramachandra
2010-07-15 19:19 ` Jonathan Nieder
2010-07-15 16:23 ` [PATCH 7/8] Add infrastructure to write revisions in fast-export format Ramkumar Ramachandra
2010-07-15 19:28 ` Jonathan Nieder
2010-07-15 16:23 ` [PATCH 8/8] Add SVN dump parser Ramkumar Ramachandra
2010-07-15 19:52 ` Jonathan Nieder
2010-07-15 20:04 ` Jonathan Nieder
2010-07-16 10:13 ` [PATCH 0/8] Resurrect rr/svn-export Jonathan Nieder
2010-07-16 10:16 ` [PATCH 3/9] Add memory pool library Jonathan Nieder
2010-07-16 10:23 ` [PATCH 4/9] Add treap implementation Jonathan Nieder
2010-07-16 18:26 ` Jonathan Nieder
2010-08-09 21:57 ` [PATCH 0/10] rr/svn-export reroll Jonathan Nieder
2010-08-09 22:01 ` [PATCH 01/10] Export parse_date_basic() to convert a date string to timestamp Jonathan Nieder
2010-08-09 22:04 ` [PATCH 02/10] Introduce vcs-svn lib Jonathan Nieder
2010-08-09 22:11 ` [PATCH 03/10] Add memory pool library Jonathan Nieder
2010-08-09 22:17 ` [PATCH 04/10] Add treap implementation Jonathan Nieder
2010-08-12 17:22 ` Junio C Hamano
2010-08-12 22:02 ` Jonathan Nieder
2010-08-12 22:11 ` Jonathan Nieder
2010-08-12 22:44 ` Junio C Hamano
2010-08-09 22:34 ` [PATCH 05/10] Add string-specific memory pool Jonathan Nieder
2010-08-12 17:22 ` Junio C Hamano
2010-08-12 21:30 ` Jonathan Nieder
2010-08-09 22:39 ` [PATCH 06/10] Add stream helper library Jonathan Nieder
2010-08-09 22:48 ` [PATCH 07/10] Infrastructure to write revisions in fast-export format Jonathan Nieder
2010-08-09 22:55 ` [PATCH 08/10] SVN dump parser Jonathan Nieder
2010-08-12 17:22 ` Junio C Hamano
2010-08-09 22:55 ` PATCH 09/10] Update svn-fe manual Jonathan Nieder
2010-08-09 22:58 ` [PATCH 10/10] svn-fe manual: Clarify warning about deltas in dump files Jonathan Nieder
2010-08-10 12:53 ` [PATCH 0/10] rr/svn-export reroll Ramkumar Ramachandra
2010-08-11 1:53 ` Jonathan Nieder
2010-10-11 2:34 ` [PATCH/WIP 00/16] svn delta applier Jonathan Nieder
2010-10-11 2:37 ` [PATCH 01/16] vcs-svn: Eliminate global byte_buffer[] array Jonathan Nieder
2010-10-11 2:39 ` [PATCH 03/16] vcs-svn: Collect line_buffer data in a struct Jonathan Nieder
2010-10-11 2:41 ` [PATCH 04/16] vcs-svn: Teach line_buffer to handle multiple input files Jonathan Nieder
2010-10-11 2:44 ` [PATCH 05/16] vcs-svn: Make buffer_skip_bytes() report partial reads Jonathan Nieder
2010-10-11 2:46 ` [PATCH 06/16] vcs-svn: Improve support for reading large files Jonathan Nieder
2010-10-11 2:47 ` [PATCH 07/16] vcs-svn: Add binary-safe read() function Jonathan Nieder
2010-10-11 2:47 ` [PATCH 08/16] vcs-svn: Let callers peek ahead to find stream end Jonathan Nieder
2010-10-11 2:51 ` [PATCH 09/16] vcs-svn: Allow input errors to be detected early Jonathan Nieder
2010-10-11 2:52 ` [PATCH 10/16] vcs-svn: Allow character-oriented input Jonathan Nieder
2010-10-11 2:53 ` [PATCH 11/16] vcs-svn: Add code to maintain a sliding view of a file Jonathan Nieder
2010-10-11 2:55 ` [PATCH 12/16] vcs-svn: Learn to parse variable-length integers Jonathan Nieder
2010-10-11 2:58 ` [PATCH 13/16] vcs-svn: Learn to check for SVN\0 magic Jonathan Nieder
2010-10-11 2:59 ` [PATCH 14/16] compat: helper for detecting unsigned overflow Jonathan Nieder
2010-10-11 3:00 ` [PATCH 15/16] t9010 (svn-fe): Eliminate dependency on svn perl bindings Jonathan Nieder
2010-10-11 3:11 ` [PATCH 02/16] vcs-svn: Replace buffer_read_string() memory pool with a strbuf Jonathan Nieder
2010-10-11 4:01 ` [PATCH/RFC 16'/16] vcs-svn: Add svn delta parser Jonathan Nieder
2010-10-13 9:17 ` [PATCH/RFC 0/11] Building up the " Jonathan Nieder
2010-10-13 9:19 ` [PATCH 01/11] fixup! vcs-svn: Learn to parse variable-length integers Jonathan Nieder
2010-10-13 9:21 ` Jonathan Nieder [this message]
2010-10-13 9:30 ` [PATCH 03/11] vcs-svn: Read the preimage while applying deltas Jonathan Nieder
2010-10-14 21:45 ` Sam Vilain
2010-10-14 23:40 ` Jonathan Nieder
2010-10-13 9:35 ` [PATCH 04/11] vcs-svn: Read inline data from deltas Jonathan Nieder
2010-10-13 9:38 ` [PATCH 05/11] vcs-svn: Read instructions " Jonathan Nieder
2010-10-13 9:39 ` [PATCH 06/11] vcs-svn: Implement copyfrom_data delta instruction Jonathan Nieder
2010-10-13 9:41 ` [PATCH 07/11] vcs-svn: Check declared number of output bytes Jonathan Nieder
2010-10-13 9:48 ` [PATCH 08/11] vcs-svn: Reject deltas that do not consume all inline data Jonathan Nieder
2010-10-13 9:50 ` [PATCH 09/11] vcs-svn: Let deltas use data from postimage Jonathan Nieder
2010-10-13 9:53 ` [PATCH 10/11] vcs-svn: Reject deltas that read past end of preimage Jonathan Nieder
2010-10-13 9:58 ` [PATCH 11/11] vcs-svn: Allow deltas to copy from preimage Jonathan Nieder
2010-10-13 10:00 ` Jonathan Nieder
2010-10-18 17:00 ` [PATCH/RFC 0/11] Building up the delta parser Ramkumar Ramachandra
2010-10-18 17:03 ` Jonathan Nieder
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20101013092143.GC32608@burratino \
--to=jrnieder@gmail.com \
--cc=artagnon@gmail.com \
--cc=david.barr@cordelta.com \
--cc=git@vger.kernel.org \
--cc=srabbelier@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).