bdelta: new module for binary diff/patch
[ccan] / ccan / bdelta / test / run-myers.c
1 #include "common.h"
2
3 #define is_digit(c) ((c) >= '0' && (c) <= '9')
4
5 static uint32_t parse_int(const char **sp)
6 {
7         const char *s = *sp;
8         uint32_t n = 0;
9         
10         while (is_digit(*s)) {
11                 n *= 10;
12                 n += *s++ - '0';
13         }
14         
15         *sp = s;
16         return n;
17 }
18
19 static const char *op_name(int op)
20 {
21         switch (op) {
22                 case OP_COPY:
23                         return "copy";
24                 case OP_SKIP:
25                         return "skip";
26                 case OP_INSERT:
27                         return "insert";
28                 
29                 default:
30                         return "<invalid opcode>";
31         }
32 }
33
34 static const char *verify_csi32(
35         const unsigned char *patch_start, const unsigned char *patch_end,
36         const char *expected)
37 {
38         const unsigned char *p = patch_start;
39         
40         if (p >= patch_end)
41                 return "Patch type byte missing";
42         if (*p++ != PT_CSI32)
43                 return "Patch type byte is not PT_CSI32";
44         
45         for (;;) {
46                 int patch_op;
47                 uint32_t patch_size;
48                 int expected_op;
49                 uint32_t expected_size;
50                 
51                 while (*expected == ' ')
52                         expected++;
53                 if (*expected == '\0')
54                         break;
55                 
56                 if (!csi32_parse_op(&p, patch_end, &patch_op, &patch_size)) {
57                         if (p == patch_end)
58                                 return "Patch shorter than expected.";
59                         else
60                                 return "Patch contains invalid CSI-32";
61                 }
62                 
63                 switch (*expected) {
64                         case 'c':
65                                 expected_op = OP_COPY;
66                                 break;
67                         case 's':
68                                 expected_op = OP_SKIP;
69                                 break;
70                         case 'i':
71                                 expected_op = OP_INSERT;
72                                 break;
73                         
74                         default:
75                                 diag("verify_csi32: Unexpected character %c", *expected);
76                                 return "Syntax error in expected difference";
77                 }
78                 expected++;
79                 
80                 while (*expected == ' ')
81                         expected++;
82                 
83                 if (patch_op != expected_op) {
84                         diag("verify_csi32: Expected %s, but next op is %s %lu",
85                              op_name(expected_op), op_name(patch_op), (unsigned long)patch_size);
86                         return "Operation mismatch";
87                 }
88                 
89                 if (expected_op == OP_COPY || expected_op == OP_SKIP) {
90                         if (!is_digit(*expected)) {
91                                 diag("verify_csi32: Expected size after %s instruction",
92                                      op_name(expected_op));
93                                 return "Syntax error in expected difference";
94                         }
95                         expected_size = parse_int(&expected);
96                         
97                         if (patch_size != expected_size) {
98                                 diag("verify_csi32: Expected %s %lu, but patch says %s %lu",
99                                      op_name(expected_op), (unsigned long)expected_size,
100                                      op_name(expected_op), (unsigned long)patch_size);
101                                 return "Operation size mismatch";
102                         }
103                 } else {
104                         if (*expected++ != '\'') {
105                                 diag("verify_csi32: Expected single-quoted string after insert instruction");
106                                 return "Syntax error in expected difference";
107                         }
108                         
109                         for (expected_size = 0; ; expected_size++) {
110                                 unsigned char c;
111                                 
112                                 if (*expected == '\'' && *(expected + 1) == '\'') {
113                                         c = '\'';
114                                         expected += 2;
115                                 } else if (*expected == '\'') {
116                                         expected++;
117                                         break;
118                                 } else if (*expected == '\0') {
119                                         diag("verify_csi32: Missing end quote");
120                                         return "Syntax error in expected difference";
121                                 } else {
122                                         c = *expected++;
123                                 }
124                                 
125                                 if (!(p < patch_end && *p++ == c))
126                                         return "Insertion string mismatch";
127                         }
128                         
129                         if (patch_size != expected_size)
130                                 return "Insertion string mismatch";
131                 }
132         }
133         
134         if (p != patch_end)
135                 return "Patch longer than expected.";
136         
137         return NULL;
138 }
139
140 static void test_myers(const char *old, const char *new_, const char *expected_difference)
141 {
142         SB patch;
143         BDELTAcode rc;
144         const char *verify_msg;
145         
146         if (sb_init(&patch) != 0) {
147                 fail("Out of memory");
148                 return;
149         }
150         
151         rc = diff_myers(old, strlen(old), new_, strlen(new_), &patch);
152         if (rc != BDELTA_OK) {
153                 fail("test_myers(%s, %s, %s): diff_myers failed: %s", old, new_, expected_difference, bdelta_strerror(rc));
154                 sb_discard(&patch, NULL, NULL);
155                 return;
156         }
157         
158         verify_msg = verify_csi32(patch.start, patch.cur, expected_difference);
159         sb_discard(&patch, NULL, NULL);
160         
161         if (verify_msg != NULL) {
162                 fail("test_myers(%s, %s, %s): %s", old, new_, expected_difference, verify_msg);
163                 return;
164         }
165         
166         pass("test_myers(%s, %s, %s)", old, new_, expected_difference);
167 }
168
169 int main(void)
170 {
171         (void) random_string_pair;
172         
173         plan_tests(17);
174         
175         test_myers("abcabba", "cbabac",   "s2 c1 i'b' c2 s1 c1 i'c'");
176         test_myers("abcdefg", "abcdefg",  "c7");
177         test_myers("abcdefg", "abcde",    "c5");
178         test_myers("abcdefg", "abcdefga", "c7 i'a'");
179         test_myers("abbbbbb", "bbbbbb",   "s1 c6");
180         test_myers("abbbbbb", "bbbbbbb",  "s1 c6 i'b'");
181         test_myers("bbbbbb",  "abbbbbb",  "i'a' c6");
182         test_myers("bbbbbbb", "abbbbbb",  "i'a' c6");
183         test_myers("bbbbbb",  "abbbbbbb", "i'a' c6 i'b'");
184         
185         test_myers("ac",   "ba",   "i'b' c1");
186         test_myers("ac",   "bc",   "s1 i'b' c1");
187         test_myers("abcd", "cabd", "i'c' c2 s1 c1");
188         test_myers("",     "abc",  "i'abc'");
189         test_myers("abc",  "",     "");
190         test_myers("abcd", "d",    "s3 c1");
191         test_myers("", "", "");
192         
193         /*
194          * In the event the strings have no characters in common, diff_myers will
195          * emit a skip of all the characters in the old string.  Although it is
196          * unnecessary, it is tricky to get rid of.  bdelta_diff will discard the
197          * patch anyway, because it's bigger than a literal.
198          */
199         test_myers("aaaaaaa", "bbbbbbb",  "s7 i'bbbbbbb'");
200         
201         return exit_status();
202 }