git.ozlabs.org Git - ccan/blob - 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 }