src/test/test_consdiff.c

   1 /* Copyright (c) 2014, Daniel Martí
   2  * Copyright (c) 2014-2019, The Tor Project, Inc. */
   3 /* See LICENSE for licensing information */
   4
   5 #define CONSDIFF_PRIVATE
   6
   7 #include "core/or/or.h"
   8 #include "test/test.h"
   9
  10 #include "feature/dircommon/consdiff.h"
  11 #include "lib/memarea/memarea.h"
  12 #include "test/log_test_helpers.h"
  13
  14 #define tt_str_eq_line(a,b) \
  15   tt_assert(line_str_eq((b),(a)))
  16
  17 static int
  18 consensus_split_lines_(smartlist_t *out, const char *s, memarea_t *area)
  19 {
  20   size_t len = strlen(s);
  21   return consensus_split_lines(out, s, len, area);
  22 }
  23
  24 static int
  25 consensus_compute_digest_(const char *cons,
  26                           consensus_digest_t *digest_out)
  27 {
  28   size_t len = strlen(cons);
  29   char *tmp = tor_memdup(cons, len);
  30   // We use memdup here to ensure that the input is NOT nul-terminated.
  31   // This makes it likelier for us to spot bugs.
  32   int r = consensus_compute_digest(tmp, len, digest_out);
  33   tor_free(tmp);
  34   return r;
  35 }
  36
  37 static int
  38 consensus_compute_digest_as_signed_(const char *cons,
  39                                     consensus_digest_t *digest_out)
  40 {
  41   size_t len = strlen(cons);
  42   char *tmp = tor_memdup(cons, len);
  43   // We use memdup here to ensure that the input is NOT nul-terminated.
  44   // This makes it likelier for us to spot bugs.
  45   int r = consensus_compute_digest_as_signed(tmp, len, digest_out);
  46   tor_free(tmp);
  47   return r;
  48 }
  49
  50 static void
  51 test_consdiff_smartlist_slice(void *arg)
  52 {
  53   smartlist_t *sl = smartlist_new();
  54   smartlist_slice_t *sls;
  55   int items[6] = {0,0,0,0,0,0};
  56
  57   /* Create a regular smartlist. */
  58   (void)arg;
  59   smartlist_add(sl, &items[1]);
  60   smartlist_add(sl, &items[2]);
  61   smartlist_add(sl, &items[3]);
  62   smartlist_add(sl, &items[4]);
  63   smartlist_add(sl, &items[5]);
  64
  65   /* See if the slice was done correctly. */
  66   sls = smartlist_slice(sl, 2, 5);
  67   tt_ptr_op(sl, OP_EQ, sls->list);
  68   tt_ptr_op(&items[3], OP_EQ, smartlist_get(sls->list, sls->offset));
  69   tt_ptr_op(&items[5], OP_EQ,
  70       smartlist_get(sls->list, sls->offset + (sls->len-1)));
  71   tor_free(sls);
  72
  73   /* See that using -1 as the end does get to the last element. */
  74   sls = smartlist_slice(sl, 2, -1);
  75   tt_ptr_op(sl, OP_EQ, sls->list);
  76   tt_ptr_op(&items[3], OP_EQ, smartlist_get(sls->list, sls->offset));
  77   tt_ptr_op(&items[5], OP_EQ,
  78       smartlist_get(sls->list, sls->offset + (sls->len-1)));
  79
  80  done:
  81   tor_free(sls);
  82   smartlist_free(sl);
  83 }
  84
  85 static void
  86 test_consdiff_smartlist_slice_string_pos(void *arg)
  87 {
  88   smartlist_t *sl = smartlist_new();
  89   smartlist_slice_t *sls;
  90   memarea_t *area = memarea_new();
  91
  92   /* Create a regular smartlist. */
  93   (void)arg;
  94   consensus_split_lines_(sl, "a\nd\nc\na\nb\n", area);
  95
  96   /* See that smartlist_slice_string_pos respects the bounds of the slice. */
  97   sls = smartlist_slice(sl, 2, 5);
  98   cdline_t a_line = { "a", 1 };
  99   tt_int_op(3, OP_EQ, smartlist_slice_string_pos(sls, &a_line));
 100   cdline_t d_line = { "d", 1 };
 101   tt_int_op(-1, OP_EQ, smartlist_slice_string_pos(sls, &d_line));
 102
 103  done:
 104   tor_free(sls);
 105   smartlist_free(sl);
 106   memarea_drop_all(area);
 107 }
 108
 109 static void
 110 test_consdiff_lcs_lengths(void *arg)
 111 {
 112   smartlist_t *sl1 = smartlist_new();
 113   smartlist_t *sl2 = smartlist_new();
 114   smartlist_slice_t *sls1, *sls2;
 115   int *lengths1, *lengths2;
 116   memarea_t *area = memarea_new();
 117
 118   /* Expected lcs lengths in regular and reverse order. */
 119   int e_lengths1[] = { 0, 1, 2, 3, 3, 4 };
 120   int e_lengths2[] = { 0, 1, 1, 2, 3, 4 };
 121
 122   (void)arg;
 123   consensus_split_lines_(sl1, "a\nb\nc\nd\ne\n", area);
 124   consensus_split_lines_(sl2, "a\nc\nd\ni\ne\n", area);
 125
 126   sls1 = smartlist_slice(sl1, 0, -1);
 127   sls2 = smartlist_slice(sl2, 0, -1);
 128
 129   lengths1 = lcs_lengths(sls1, sls2, 1);
 130   lengths2 = lcs_lengths(sls1, sls2, -1);
 131   tt_mem_op(e_lengths1, OP_EQ, lengths1, sizeof(int) * 6);
 132   tt_mem_op(e_lengths2, OP_EQ, lengths2, sizeof(int) * 6);
 133
 134  done:
 135   tor_free(lengths1);
 136   tor_free(lengths2);
 137   tor_free(sls1);
 138   tor_free(sls2);
 139   smartlist_free(sl1);
 140   smartlist_free(sl2);
 141   memarea_drop_all(area);
 142 }
 143
 144 static void
 145 test_consdiff_trim_slices(void *arg)
 146 {
 147   smartlist_t *sl1 = smartlist_new();
 148   smartlist_t *sl2 = smartlist_new();
 149   smartlist_t *sl3 = smartlist_new();
 150   smartlist_t *sl4 = smartlist_new();
 151   smartlist_slice_t *sls1, *sls2, *sls3, *sls4;
 152   memarea_t *area = memarea_new();
 153
 154   (void)arg;
 155   consensus_split_lines_(sl1, "a\nb\nb\nb\nd\n", area);
 156   consensus_split_lines_(sl2, "a\nc\nc\nc\nd\n", area);
 157   consensus_split_lines_(sl3, "a\nb\nb\nb\na\n", area);
 158   consensus_split_lines_(sl4, "c\nb\nb\nb\nc\n", area);
 159   sls1 = smartlist_slice(sl1, 0, -1);
 160   sls2 = smartlist_slice(sl2, 0, -1);
 161   sls3 = smartlist_slice(sl3, 0, -1);
 162   sls4 = smartlist_slice(sl4, 0, -1);
 163
 164   /* They should be trimmed by one line at each end. */
 165   tt_int_op(5, OP_EQ, sls1->len);
 166   tt_int_op(5, OP_EQ, sls2->len);
 167   trim_slices(sls1, sls2);
 168   tt_int_op(3, OP_EQ, sls1->len);
 169   tt_int_op(3, OP_EQ, sls2->len);
 170
 171   /* They should not be trimmed at all. */
 172   tt_int_op(5, OP_EQ, sls3->len);
 173   tt_int_op(5, OP_EQ, sls4->len);
 174   trim_slices(sls3, sls4);
 175   tt_int_op(5, OP_EQ, sls3->len);
 176   tt_int_op(5, OP_EQ, sls4->len);
 177
 178  done:
 179   tor_free(sls1);
 180   tor_free(sls2);
 181   tor_free(sls3);
 182   tor_free(sls4);
 183   smartlist_free(sl1);
 184   smartlist_free(sl2);
 185   smartlist_free(sl3);
 186   smartlist_free(sl4);
 187   memarea_drop_all(area);
 188 }
 189
 190 static void
 191 test_consdiff_set_changed(void *arg)
 192 {
 193   smartlist_t *sl1 = smartlist_new();
 194   smartlist_t *sl2 = smartlist_new();
 195   bitarray_t *changed1 = bitarray_init_zero(4);
 196   bitarray_t *changed2 = bitarray_init_zero(4);
 197   smartlist_slice_t *sls1, *sls2;
 198   memarea_t *area = memarea_new();
 199
 200   (void)arg;
 201   consensus_split_lines_(sl1, "a\nb\na\na\n", area);
 202   consensus_split_lines_(sl2, "a\na\na\na\n", area);
 203
 204   /* Length of sls1 is 0. */
 205   sls1 = smartlist_slice(sl1, 0, 0);
 206   sls2 = smartlist_slice(sl2, 1, 3);
 207   set_changed(changed1, changed2, sls1, sls2);
 208
 209   /* The former is not changed, the latter changes all of its elements. */
 210   tt_assert(!bitarray_is_set(changed1, 0));
 211   tt_assert(!bitarray_is_set(changed1, 1));
 212   tt_assert(!bitarray_is_set(changed1, 2));
 213   tt_assert(!bitarray_is_set(changed1, 3));
 214
 215   tt_assert(!bitarray_is_set(changed2, 0));
 216   tt_assert(bitarray_is_set(changed2, 1));
 217   tt_assert(bitarray_is_set(changed2, 2));
 218   tt_assert(!bitarray_is_set(changed2, 3));
 219   bitarray_clear(changed2, 1);
 220   bitarray_clear(changed2, 2);
 221
 222   /* Length of sls1 is 1 and its element is in sls2. */
 223   tor_free(sls1);
 224   sls1 = smartlist_slice(sl1, 0, 1);
 225   set_changed(changed1, changed2, sls1, sls2);
 226
 227   /* The latter changes all elements but the (first) common one. */
 228   tt_assert(!bitarray_is_set(changed1, 0));
 229   tt_assert(!bitarray_is_set(changed1, 1));
 230   tt_assert(!bitarray_is_set(changed1, 2));
 231   tt_assert(!bitarray_is_set(changed1, 3));
 232
 233   tt_assert(!bitarray_is_set(changed2, 0));
 234   tt_assert(!bitarray_is_set(changed2, 1));
 235   tt_assert(bitarray_is_set(changed2, 2));
 236   tt_assert(!bitarray_is_set(changed2, 3));
 237   bitarray_clear(changed2, 2);
 238
 239   /* Length of sls1 is 1 and its element is not in sls2. */
 240   tor_free(sls1);
 241   sls1 = smartlist_slice(sl1, 1, 2);
 242   set_changed(changed1, changed2, sls1, sls2);
 243
 244   /* The former changes its element, the latter changes all elements. */
 245   tt_assert(!bitarray_is_set(changed1, 0));
 246   tt_assert(bitarray_is_set(changed1, 1));
 247   tt_assert(!bitarray_is_set(changed1, 2));
 248   tt_assert(!bitarray_is_set(changed1, 3));
 249
 250   tt_assert(!bitarray_is_set(changed2, 0));
 251   tt_assert(bitarray_is_set(changed2, 1));
 252   tt_assert(bitarray_is_set(changed2, 2));
 253   tt_assert(!bitarray_is_set(changed2, 3));
 254
 255  done:
 256   bitarray_free(changed1);
 257   bitarray_free(changed2);
 258   smartlist_free(sl1);
 259   smartlist_free(sl2);
 260   tor_free(sls1);
 261   tor_free(sls2);
 262   memarea_drop_all(area);
 263 }
 264
 265 static void
 266 test_consdiff_calc_changes(void *arg)
 267 {
 268   smartlist_t *sl1 = smartlist_new();
 269   smartlist_t *sl2 = smartlist_new();
 270   smartlist_slice_t *sls1, *sls2;
 271   bitarray_t *changed1 = bitarray_init_zero(4);
 272   bitarray_t *changed2 = bitarray_init_zero(4);
 273   memarea_t *area = memarea_new();
 274
 275   (void)arg;
 276   consensus_split_lines_(sl1, "a\na\na\na\n", area);
 277   consensus_split_lines_(sl2, "a\na\na\na\n", area);
 278
 279   sls1 = smartlist_slice(sl1, 0, -1);
 280   sls2 = smartlist_slice(sl2, 0, -1);
 281   calc_changes(sls1, sls2, changed1, changed2);
 282
 283   /* Nothing should be set to changed. */
 284   tt_assert(!bitarray_is_set(changed1, 0));
 285   tt_assert(!bitarray_is_set(changed1, 1));
 286   tt_assert(!bitarray_is_set(changed1, 2));
 287   tt_assert(!bitarray_is_set(changed1, 3));
 288
 289   tt_assert(!bitarray_is_set(changed2, 0));
 290   tt_assert(!bitarray_is_set(changed2, 1));
 291   tt_assert(!bitarray_is_set(changed2, 2));
 292   tt_assert(!bitarray_is_set(changed2, 3));
 293
 294   smartlist_clear(sl2);
 295   consensus_split_lines_(sl2, "a\nb\na\nb\n", area);
 296   tor_free(sls1);
 297   tor_free(sls2);
 298   sls1 = smartlist_slice(sl1, 0, -1);
 299   sls2 = smartlist_slice(sl2, 0, -1);
 300   calc_changes(sls1, sls2, changed1, changed2);
 301
 302   /* Two elements are changed. */
 303   tt_assert(!bitarray_is_set(changed1, 0));
 304   tt_assert(bitarray_is_set(changed1, 1));
 305   tt_assert(bitarray_is_set(changed1, 2));
 306   tt_assert(!bitarray_is_set(changed1, 3));
 307   bitarray_clear(changed1, 1);
 308   bitarray_clear(changed1, 2);
 309
 310   tt_assert(!bitarray_is_set(changed2, 0));
 311   tt_assert(bitarray_is_set(changed2, 1));
 312   tt_assert(!bitarray_is_set(changed2, 2));
 313   tt_assert(bitarray_is_set(changed2, 3));
 314   bitarray_clear(changed1, 1);
 315   bitarray_clear(changed1, 3);
 316
 317   smartlist_clear(sl2);
 318   consensus_split_lines_(sl2, "b\nb\nb\nb\n", area);
 319   tor_free(sls1);
 320   tor_free(sls2);
 321   sls1 = smartlist_slice(sl1, 0, -1);
 322   sls2 = smartlist_slice(sl2, 0, -1);
 323   calc_changes(sls1, sls2, changed1, changed2);
 324
 325   /* All elements are changed. */
 326   tt_assert(bitarray_is_set(changed1, 0));
 327   tt_assert(bitarray_is_set(changed1, 1));
 328   tt_assert(bitarray_is_set(changed1, 2));
 329   tt_assert(bitarray_is_set(changed1, 3));
 330
 331   tt_assert(bitarray_is_set(changed2, 0));
 332   tt_assert(bitarray_is_set(changed2, 1));
 333   tt_assert(bitarray_is_set(changed2, 2));
 334   tt_assert(bitarray_is_set(changed2, 3));
 335
 336  done:
 337   bitarray_free(changed1);
 338   bitarray_free(changed2);
 339   smartlist_free(sl1);
 340   smartlist_free(sl2);
 341   tor_free(sls1);
 342   tor_free(sls2);
 343   memarea_drop_all(area);
 344 }
 345
 346 static void
 347 test_consdiff_get_id_hash(void *arg)
 348 {
 349   (void)arg;
 350
 351   cdline_t line1 = { "r name", 6 };
 352   cdline_t line2 = { "r name _hash_isnt_base64 etc", 28 };
 353   cdline_t line3 = { "r name hash+valid+base64 etc", 28 };
 354   cdline_t tmp;
 355
 356   /* No hash. */
 357   tt_int_op(-1, OP_EQ, get_id_hash(&line1, &tmp));
 358   /* The hash contains characters that are not base64. */
 359   tt_int_op(-1, OP_EQ, get_id_hash(&line2, &tmp));
 360
 361   /* valid hash. */
 362   tt_int_op(0, OP_EQ, get_id_hash(&line3, &tmp));
 363   tt_ptr_op(tmp.s, OP_EQ, line3.s + 7);
 364   tt_uint_op(tmp.len, OP_EQ, line3.len - 11);
 365
 366  done:
 367   ;
 368 }
 369
 370 static void
 371 test_consdiff_is_valid_router_entry(void *arg)
 372 {
 373   /* Doesn't start with "r ". */
 374   (void)arg;
 375   cdline_t line0 = { "foo", 3 };
 376   tt_int_op(0, OP_EQ, is_valid_router_entry(&line0));
 377
 378   /* These are already tested with get_id_hash, but make sure it's run
 379    * properly. */
 380
 381   cdline_t line1 = { "r name", 6 };
 382   cdline_t line2 = { "r name _hash_isnt_base64 etc", 28 };
 383   cdline_t line3 = { "r name hash+valid+base64 etc", 28 };
 384   tt_int_op(0, OP_EQ, is_valid_router_entry(&line1));
 385   tt_int_op(0, OP_EQ, is_valid_router_entry(&line2));
 386   tt_int_op(1, OP_EQ, is_valid_router_entry(&line3));
 387
 388  done:
 389   ;
 390 }
 391
 392 static void
 393 test_consdiff_next_router(void *arg)
 394 {
 395   smartlist_t *sl = smartlist_new();
 396   memarea_t *area = memarea_new();
 397   (void)arg;
 398   smartlist_add_linecpy(sl, area, "foo");
 399   smartlist_add_linecpy(sl, area,
 400       "r name hash+longer+than+27+chars+and+valid+base64 etc");
 401   smartlist_add_linecpy(sl, area, "foo");
 402   smartlist_add_linecpy(sl, area, "foo");
 403   smartlist_add_linecpy(sl, area,
 404       "r name hash+longer+than+27+chars+and+valid+base64 etc");
 405   smartlist_add_linecpy(sl, area, "foo");
 406
 407   /* Not currently on a router entry line, finding the next one. */
 408   tt_int_op(1, OP_EQ, next_router(sl, 0));
 409   tt_int_op(4, OP_EQ, next_router(sl, 2));
 410
 411   /* Already at the beginning of a router entry line, ignore it. */
 412   tt_int_op(4, OP_EQ, next_router(sl, 1));
 413
 414   /* There are no more router entries, so return the line after the last. */
 415   tt_int_op(6, OP_EQ, next_router(sl, 4));
 416   tt_int_op(6, OP_EQ, next_router(sl, 5));
 417
 418  done:
 419   smartlist_free(sl);
 420   memarea_drop_all(area);
 421 }
 422
 423 static int
 424 base64cmp_wrapper(const char *a, const char *b)
 425 {
 426   cdline_t aa = { a, a ? (uint32_t) strlen(a) : 0 };
 427   cdline_t bb = { b, b ? (uint32_t) strlen(b) : 0 };
 428   return base64cmp(&aa, &bb);
 429 }
 430
 431 static void
 432 test_consdiff_base64cmp(void *arg)
 433 {
 434   /* NULL arguments. */
 435   (void)arg;
 436   tt_int_op(0, OP_EQ, base64cmp_wrapper(NULL, NULL));
 437   tt_int_op(-1, OP_EQ, base64cmp_wrapper(NULL, "foo"));
 438   tt_int_op(1, OP_EQ, base64cmp_wrapper("bar", NULL));
 439
 440   /* Nil base64 values. */
 441   tt_int_op(0, OP_EQ, base64cmp_wrapper("", ""));
 442   tt_int_op(0, OP_EQ, base64cmp_wrapper("_", "&"));
 443
 444   /* Exact same valid strings. */
 445   tt_int_op(0, OP_EQ, base64cmp_wrapper("abcABC/+", "abcABC/+"));
 446   /* Both end with an invalid base64 char other than '\0'. */
 447   tt_int_op(0, OP_EQ, base64cmp_wrapper("abcABC/+ ", "abcABC/+ "));
 448   /* Only one ends with an invalid base64 char other than '\0'. */
 449   tt_int_op(-1, OP_EQ, base64cmp_wrapper("abcABC/+ ", "abcABC/+a"));
 450
 451   /* Comparisons that would return differently with strcmp(). */
 452   tt_int_op(strcmp("/foo", "Afoo"), OP_LT, 0);
 453   tt_int_op(base64cmp_wrapper("/foo", "Afoo"), OP_GT, 0);
 454   tt_int_op(strcmp("Afoo", "0foo"), OP_GT, 0);
 455   tt_int_op(base64cmp_wrapper("Afoo", "0foo"), OP_LT, 0);
 456
 457   /* Comparisons that would return the same as with strcmp(). */
 458   tt_int_op(strcmp("afoo", "Afoo"), OP_GT, 0);
 459   tt_int_op(base64cmp_wrapper("afoo", "Afoo"), OP_GT, 0);
 460
 461   /* Different lengths */
 462   tt_int_op(base64cmp_wrapper("afoo", "afooo"), OP_LT, 0);
 463   tt_int_op(base64cmp_wrapper("afooo", "afoo"), OP_GT, 0);
 464
 465  done:
 466   ;
 467 }
 468
 469 static void
 470 test_consdiff_gen_ed_diff(void *arg)
 471 {
 472   smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL;
 473   int i;
 474   memarea_t *area = memarea_new();
 475   setup_capture_of_logs(LOG_WARN);
 476
 477   (void)arg;
 478   cons1 = smartlist_new();
 479   cons2 = smartlist_new();
 480
 481   /* Identity hashes are not sorted properly, return NULL. */
 482   smartlist_add_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc");
 483   smartlist_add_linecpy(cons1, area, "foo");
 484   smartlist_add_linecpy(cons1, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc");
 485   smartlist_add_linecpy(cons1, area, "bar");
 486
 487   smartlist_add_linecpy(cons2, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc");
 488   smartlist_add_linecpy(cons2, area, "foo");
 489   smartlist_add_linecpy(cons2, area, "r name ccccccccccccccccccccccccccc etc");
 490   smartlist_add_linecpy(cons2, area, "bar");
 491
 492   diff = gen_ed_diff(cons1, cons2, area);
 493   tt_ptr_op(NULL, OP_EQ, diff);
 494   expect_single_log_msg_containing("Refusing to generate consensus diff "
 495          "because the base consensus doesn't have its router entries sorted "
 496          "properly.");
 497
 498   /* Same, but now with the second consensus. */
 499   mock_clean_saved_logs();
 500   diff = gen_ed_diff(cons2, cons1, area);
 501   tt_ptr_op(NULL, OP_EQ, diff);
 502   expect_single_log_msg_containing("Refusing to generate consensus diff "
 503          "because the target consensus doesn't have its router entries sorted "
 504          "properly.");
 505
 506   /* Same as the two above, but with the reversed thing immediately after a
 507      match. (The code handles this differently) */
 508   smartlist_del(cons1, 0);
 509   smartlist_add_linecpy(cons1, area, "r name aaaaaaaaaaaaaaaaaaaaaaaaaaa etc");
 510
 511   mock_clean_saved_logs();
 512   diff = gen_ed_diff(cons1, cons2, area);
 513   tt_ptr_op(NULL, OP_EQ, diff);
 514   expect_single_log_msg_containing("Refusing to generate consensus diff "
 515          "because the base consensus doesn't have its router entries sorted "
 516          "properly.");
 517
 518   mock_clean_saved_logs();
 519   diff = gen_ed_diff(cons2, cons1, area);
 520   tt_ptr_op(NULL, OP_EQ, diff);
 521   expect_single_log_msg_containing("Refusing to generate consensus diff "
 522          "because the target consensus doesn't have its router entries sorted "
 523          "properly.");
 524
 525   /* Identity hashes are repeated, return NULL. */
 526   smartlist_clear(cons1);
 527
 528   smartlist_add_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc");
 529   smartlist_add_linecpy(cons1, area, "foo");
 530   smartlist_add_linecpy(cons1, area, "r name bbbbbbbbbbbbbbbbbbbbbbbbbbb etc");
 531   smartlist_add_linecpy(cons1, area, "bar");
 532
 533   mock_clean_saved_logs();
 534   diff = gen_ed_diff(cons1, cons2, area);
 535   tt_ptr_op(NULL, OP_EQ, diff);
 536   expect_single_log_msg_containing("Refusing to generate consensus diff "
 537          "because the base consensus doesn't have its router entries sorted "
 538          "properly.");
 539
 540   /* We have to add a line that is just a dot, return NULL. */
 541   smartlist_clear(cons1);
 542   smartlist_clear(cons2);
 543
 544   smartlist_add_linecpy(cons1, area, "foo1");
 545   smartlist_add_linecpy(cons1, area, "foo2");
 546
 547   smartlist_add_linecpy(cons2, area, "foo1");
 548   smartlist_add_linecpy(cons2, area, ".");
 549   smartlist_add_linecpy(cons2, area, "foo2");
 550
 551   mock_clean_saved_logs();
 552   diff = gen_ed_diff(cons1, cons2, area);
 553   tt_ptr_op(NULL, OP_EQ, diff);
 554   expect_single_log_msg_containing("Cannot generate consensus diff "
 555          "because one of the lines to be added is \".\".");
 556
 557 #define MAX_LINE_COUNT (10000)
 558   /* Too many lines to be fed to the quadratic-time function. */
 559   smartlist_clear(cons1);
 560   smartlist_clear(cons2);
 561
 562   for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add_linecpy(cons1, area, "a");
 563   for (i=0; i < MAX_LINE_COUNT; ++i) smartlist_add_linecpy(cons1, area, "b");
 564
 565   mock_clean_saved_logs();
 566   diff = gen_ed_diff(cons1, cons2, area);
 567
 568   tt_ptr_op(NULL, OP_EQ, diff);
 569   expect_single_log_msg_containing("Refusing to generate consensus diff "
 570          "because we found too few common router ids.");
 571
 572   /* We have dot lines, but they don't interfere with the script format. */
 573   smartlist_clear(cons1);
 574   smartlist_clear(cons2);
 575
 576   smartlist_add_linecpy(cons1, area, "foo1");
 577   smartlist_add_linecpy(cons1, area, ".");
 578   smartlist_add_linecpy(cons1, area, ".");
 579   smartlist_add_linecpy(cons1, area, "foo2");
 580
 581   smartlist_add_linecpy(cons2, area, "foo1");
 582   smartlist_add_linecpy(cons2, area, ".");
 583   smartlist_add_linecpy(cons2, area, "foo2");
 584
 585   diff = gen_ed_diff(cons1, cons2, area);
 586   tt_ptr_op(NULL, OP_NE, diff);
 587   smartlist_free(diff);
 588
 589   /* Empty diff tests. */
 590   smartlist_clear(cons1);
 591   smartlist_clear(cons2);
 592
 593   diff = gen_ed_diff(cons1, cons2, area);
 594   tt_ptr_op(NULL, OP_NE, diff);
 595   tt_int_op(0, OP_EQ, smartlist_len(diff));
 596   smartlist_free(diff);
 597
 598   smartlist_add_linecpy(cons1, area, "foo");
 599   smartlist_add_linecpy(cons1, area, "bar");
 600
 601   smartlist_add_linecpy(cons2, area, "foo");
 602   smartlist_add_linecpy(cons2, area, "bar");
 603
 604   diff = gen_ed_diff(cons1, cons2, area);
 605   tt_ptr_op(NULL, OP_NE, diff);
 606   tt_int_op(0, OP_EQ, smartlist_len(diff));
 607   smartlist_free(diff);
 608
 609   /* Everything is deleted. */
 610   smartlist_clear(cons2);
 611
 612   diff = gen_ed_diff(cons1, cons2, area);
 613   tt_ptr_op(NULL, OP_NE, diff);
 614   tt_int_op(1, OP_EQ, smartlist_len(diff));
 615   tt_str_eq_line("1,2d", smartlist_get(diff, 0));
 616
 617   smartlist_free(diff);
 618
 619   /* Everything is added. */
 620   diff = gen_ed_diff(cons2, cons1, area);
 621   tt_ptr_op(NULL, OP_NE, diff);
 622   tt_int_op(4, OP_EQ, smartlist_len(diff));
 623   tt_str_eq_line("0a", smartlist_get(diff, 0));
 624   tt_str_eq_line("foo", smartlist_get(diff, 1));
 625   tt_str_eq_line("bar", smartlist_get(diff, 2));
 626   tt_str_eq_line(".", smartlist_get(diff, 3));
 627
 628   smartlist_free(diff);
 629
 630   /* Everything is changed. */
 631   smartlist_add_linecpy(cons2, area, "foo2");
 632   smartlist_add_linecpy(cons2, area, "bar2");
 633   diff = gen_ed_diff(cons1, cons2, area);
 634   tt_ptr_op(NULL, OP_NE, diff);
 635   tt_int_op(4, OP_EQ, smartlist_len(diff));
 636   tt_str_eq_line("1,2c", smartlist_get(diff, 0));
 637   tt_str_eq_line("foo2", smartlist_get(diff, 1));
 638   tt_str_eq_line("bar2", smartlist_get(diff, 2));
 639   tt_str_eq_line(".", smartlist_get(diff, 3));
 640
 641   smartlist_free(diff);
 642
 643   /* Test 'a', 'c' and 'd' together. See that it is done in reverse order. */
 644   smartlist_clear(cons1);
 645   smartlist_clear(cons2);
 646   consensus_split_lines_(cons1, "A\nB\nC\nD\nE\n", area);
 647   consensus_split_lines_(cons2, "A\nC\nO\nE\nU\n", area);
 648   diff = gen_ed_diff(cons1, cons2, area);
 649   tt_ptr_op(NULL, OP_NE, diff);
 650   tt_int_op(7, OP_EQ, smartlist_len(diff));
 651   tt_str_eq_line("5a", smartlist_get(diff, 0));
 652   tt_str_eq_line("U", smartlist_get(diff, 1));
 653   tt_str_eq_line(".", smartlist_get(diff, 2));
 654   tt_str_eq_line("4c", smartlist_get(diff, 3));
 655   tt_str_eq_line("O", smartlist_get(diff, 4));
 656   tt_str_eq_line(".", smartlist_get(diff, 5));
 657   tt_str_eq_line("2d", smartlist_get(diff, 6));
 658
 659   smartlist_free(diff);
 660
 661   smartlist_clear(cons1);
 662   smartlist_clear(cons2);
 663   consensus_split_lines_(cons1, "B\n", area);
 664   consensus_split_lines_(cons2, "A\nB\n", area);
 665   diff = gen_ed_diff(cons1, cons2, area);
 666   tt_ptr_op(NULL, OP_NE, diff);
 667   tt_int_op(3, OP_EQ, smartlist_len(diff));
 668   tt_str_eq_line("0a", smartlist_get(diff, 0));
 669   tt_str_eq_line("A", smartlist_get(diff, 1));
 670   tt_str_eq_line(".", smartlist_get(diff, 2));
 671
 672   /* TODO: small real use-cases, i.e. consensuses. */
 673
 674  done:
 675   teardown_capture_of_logs();
 676   smartlist_free(cons1);
 677   smartlist_free(cons2);
 678   smartlist_free(diff);
 679   memarea_drop_all(area);
 680 }
 681
 682 static void
 683 test_consdiff_apply_ed_diff(void *arg)
 684 {
 685   smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL;
 686   memarea_t *area = memarea_new();
 687   (void)arg;
 688   cons1 = smartlist_new();
 689   diff = smartlist_new();
 690   setup_capture_of_logs(LOG_WARN);
 691
 692   consensus_split_lines_(cons1, "A\nB\nC\nD\nE\n", area);
 693
 694   /* Command without range. */
 695   smartlist_add_linecpy(diff, area, "a");
 696   cons2 = apply_ed_diff(cons1, diff, 0);
 697   tt_ptr_op(NULL, OP_EQ, cons2);
 698   smartlist_clear(diff);
 699   expect_single_log_msg_containing("an ed command was missing a line number");
 700
 701   /* Range without command. */
 702   smartlist_add_linecpy(diff, area, "1");
 703   mock_clean_saved_logs();
 704   cons2 = apply_ed_diff(cons1, diff, 0);
 705   tt_ptr_op(NULL, OP_EQ, cons2);
 706   expect_single_log_msg_containing("a line with no ed command was found");
 707
 708   smartlist_clear(diff);
 709
 710   /* Range without end. */
 711   smartlist_add_linecpy(diff, area, "1,");
 712   mock_clean_saved_logs();
 713   cons2 = apply_ed_diff(cons1, diff, 0);
 714   tt_ptr_op(NULL, OP_EQ, cons2);
 715   expect_single_log_msg_containing("an ed command was missing a range "
 716                                    "end line number.");
 717
 718   smartlist_clear(diff);
 719
 720   /* Incoherent ranges. */
 721   smartlist_add_linecpy(diff, area, "1,1");
 722   mock_clean_saved_logs();
 723   cons2 = apply_ed_diff(cons1, diff, 0);
 724   tt_ptr_op(NULL, OP_EQ, cons2);
 725   expect_single_log_msg_containing("an invalid range was found");
 726
 727   smartlist_clear(diff);
 728
 729   smartlist_add_linecpy(diff, area, "3,2");
 730   mock_clean_saved_logs();
 731   cons2 = apply_ed_diff(cons1, diff, 0);
 732   tt_ptr_op(NULL, OP_EQ, cons2);
 733   expect_single_log_msg_containing("an invalid range was found");
 734
 735   smartlist_clear(diff);
 736
 737   /* Unexpected range for add command. */
 738   smartlist_add_linecpy(diff, area, "1,2a");
 739   mock_clean_saved_logs();
 740   cons2 = apply_ed_diff(cons1, diff, 0);
 741   tt_ptr_op(NULL, OP_EQ, cons2);
 742   expect_single_log_msg_containing("add lines after a range");
 743
 744   smartlist_clear(diff);
 745
 746   /* $ for a non-delete command. */
 747   smartlist_add_linecpy(diff, area, "1,$c");
 748   mock_clean_saved_logs();
 749   cons2 = apply_ed_diff(cons1, diff, 0);
 750   tt_ptr_op(NULL, OP_EQ, cons2);
 751   expect_single_log_msg_containing("it wanted to use $ with a command "
 752                                    "other than delete");
 753
 754   smartlist_clear(diff);
 755
 756   /* Script is not in reverse order. */
 757   smartlist_add_linecpy(diff, area, "1d");
 758   smartlist_add_linecpy(diff, area, "3d");
 759   mock_clean_saved_logs();
 760   cons2 = apply_ed_diff(cons1, diff, 0);
 761   tt_ptr_op(NULL, OP_EQ, cons2);
 762   expect_single_log_msg_containing("its commands are not properly sorted");
 763
 764   smartlist_clear(diff);
 765
 766   /* Script contains unrecognised commands longer than one char. */
 767   smartlist_add_linecpy(diff, area, "1foo");
 768   mock_clean_saved_logs();
 769   cons2 = apply_ed_diff(cons1, diff, 0);
 770   tt_ptr_op(NULL, OP_EQ, cons2);
 771   expect_single_log_msg_containing("an ed command longer than one char was "
 772                                    "found");
 773
 774   smartlist_clear(diff);
 775
 776   /* Script contains unrecognised commands. */
 777   smartlist_add_linecpy(diff, area, "1e");
 778   mock_clean_saved_logs();
 779   cons2 = apply_ed_diff(cons1, diff, 0);
 780   tt_ptr_op(NULL, OP_EQ, cons2);
 781   expect_single_log_msg_containing("an unrecognised ed command was found");
 782
 783   smartlist_clear(diff);
 784
 785   /* Command that should be followed by at least one line and a ".", but
 786    * isn't. */
 787   smartlist_add_linecpy(diff, area, "0a");
 788   mock_clean_saved_logs();
 789   cons2 = apply_ed_diff(cons1, diff, 0);
 790   tt_ptr_op(NULL, OP_EQ, cons2);
 791   expect_single_log_msg_containing("it has an ed command that tries to "
 792                                    "insert zero lines.");
 793
 794   /* Now it is followed by a ".", but it inserts zero lines. */
 795   smartlist_add_linecpy(diff, area, ".");
 796   mock_clean_saved_logs();
 797   cons2 = apply_ed_diff(cons1, diff, 0);
 798   tt_ptr_op(NULL, OP_EQ, cons2);
 799   expect_single_log_msg_containing("it has an ed command that tries to "
 800                                    "insert zero lines.");
 801
 802   smartlist_clear(diff);
 803
 804   /* Now it it inserts something, but has no terminator. */
 805   smartlist_add_linecpy(diff, area, "0a");
 806   smartlist_add_linecpy(diff, area, "hello");
 807   mock_clean_saved_logs();
 808   cons2 = apply_ed_diff(cons1, diff, 0);
 809   tt_ptr_op(NULL, OP_EQ, cons2);
 810   expect_single_log_msg_containing("lines to be inserted that don't end with "
 811                                    "a \".\".");
 812
 813   smartlist_clear(diff);
 814
 815   /* Ranges must be numeric only and cannot contain spaces. */
 816   smartlist_add_linecpy(diff, area, "0, 4d");
 817   mock_clean_saved_logs();
 818   cons2 = apply_ed_diff(cons1, diff, 0);
 819   tt_ptr_op(NULL, OP_EQ, cons2);
 820   expect_single_log_msg_containing("an ed command was missing a range "
 821                                    "end line number.");
 822
 823   smartlist_clear(diff);
 824
 825   /* '+' is not a number. */
 826   smartlist_add_linecpy(diff, area, "+0,4d");
 827   mock_clean_saved_logs();
 828   cons2 = apply_ed_diff(cons1, diff, 0);
 829   tt_ptr_op(NULL, OP_EQ, cons2);
 830   expect_single_log_msg_containing("an ed command was missing a line number");
 831
 832   smartlist_clear(diff);
 833
 834   /* range duplication */
 835   smartlist_add_linecpy(diff, area, "0,4d,5d");
 836   mock_clean_saved_logs();
 837   cons2 = apply_ed_diff(cons1, diff, 0);
 838   tt_ptr_op(NULL, OP_EQ, cons2);
 839   expect_single_log_msg_containing("an ed command longer than one char was "
 840                                    "found");
 841
 842   smartlist_clear(diff);
 843
 844   /* space before command */
 845   smartlist_add_linecpy(diff, area, "0,4 d");
 846   mock_clean_saved_logs();
 847   cons2 = apply_ed_diff(cons1, diff, 0);
 848   tt_ptr_op(NULL, OP_EQ, cons2);
 849   expect_single_log_msg_containing("an ed command longer than one char was "
 850                                    "found");
 851
 852   smartlist_clear(diff);
 853
 854   /* space inside number */
 855   smartlist_add_linecpy(diff, area, "0,4 5d");
 856   mock_clean_saved_logs();
 857   cons2 = apply_ed_diff(cons1, diff, 0);
 858   tt_ptr_op(NULL, OP_EQ, cons2);
 859   expect_single_log_msg_containing("an ed command longer than one char was "
 860                                    "found");
 861
 862   smartlist_clear(diff);
 863
 864   /* Test appending text, 'a'. */
 865   consensus_split_lines_(diff, "3a\nU\nO\n.\n0a\nV\n.\n", area);
 866   cons2 = apply_ed_diff(cons1, diff, 0);
 867   tt_ptr_op(NULL, OP_NE, cons2);
 868   tt_int_op(8, OP_EQ, smartlist_len(cons2));
 869   tt_str_eq_line("V", smartlist_get(cons2, 0));
 870   tt_str_eq_line("A", smartlist_get(cons2, 1));
 871   tt_str_eq_line("B", smartlist_get(cons2, 2));
 872   tt_str_eq_line("C", smartlist_get(cons2, 3));
 873   tt_str_eq_line("U", smartlist_get(cons2, 4));
 874   tt_str_eq_line("O", smartlist_get(cons2, 5));
 875   tt_str_eq_line("D", smartlist_get(cons2, 6));
 876   tt_str_eq_line("E", smartlist_get(cons2, 7));
 877
 878   smartlist_clear(diff);
 879   smartlist_free(cons2);
 880
 881   /* Test deleting text, 'd'. */
 882   consensus_split_lines_(diff, "4d\n1,2d\n", area);
 883   cons2 = apply_ed_diff(cons1, diff, 0);
 884   tt_ptr_op(NULL, OP_NE, cons2);
 885   tt_int_op(2, OP_EQ, smartlist_len(cons2));
 886   tt_str_eq_line("C", smartlist_get(cons2, 0));
 887   tt_str_eq_line("E", smartlist_get(cons2, 1));
 888
 889   smartlist_clear(diff);
 890   smartlist_free(cons2);
 891
 892   /* Test changing text, 'c'. */
 893   consensus_split_lines_(diff, "4c\nT\nX\n.\n1,2c\nM\n.\n", area);
 894   cons2 = apply_ed_diff(cons1, diff, 0);
 895   tt_ptr_op(NULL, OP_NE, cons2);
 896   tt_int_op(5, OP_EQ, smartlist_len(cons2));
 897   tt_str_eq_line("M", smartlist_get(cons2, 0));
 898   tt_str_eq_line("C", smartlist_get(cons2, 1));
 899   tt_str_eq_line("T", smartlist_get(cons2, 2));
 900   tt_str_eq_line("X", smartlist_get(cons2, 3));
 901   tt_str_eq_line("E", smartlist_get(cons2, 4));
 902
 903   smartlist_clear(diff);
 904   smartlist_free(cons2);
 905
 906   /* Test 'a', 'd' and 'c' together. */
 907   consensus_split_lines_(diff, "4c\nT\nX\n.\n2d\n0a\nM\n.\n", area);
 908   cons2 = apply_ed_diff(cons1, diff, 0);
 909   tt_ptr_op(NULL, OP_NE, cons2);
 910   tt_int_op(6, OP_EQ, smartlist_len(cons2));
 911   tt_str_eq_line("M", smartlist_get(cons2, 0));
 912   tt_str_eq_line("A", smartlist_get(cons2, 1));
 913   tt_str_eq_line("C", smartlist_get(cons2, 2));
 914   tt_str_eq_line("T", smartlist_get(cons2, 3));
 915   tt_str_eq_line("X", smartlist_get(cons2, 4));
 916   tt_str_eq_line("E", smartlist_get(cons2, 5));
 917
 918  done:
 919   teardown_capture_of_logs();
 920   smartlist_free(cons1);
 921   smartlist_free(cons2);
 922   smartlist_free(diff);
 923   memarea_drop_all(area);
 924 }
 925
 926 static void
 927 test_consdiff_gen_diff(void *arg)
 928 {
 929   char *cons1_str=NULL, *cons2_str=NULL;
 930   smartlist_t *cons1=NULL, *cons2=NULL, *diff=NULL;
 931   consensus_digest_t digests1, digests2;
 932   memarea_t *area = memarea_new();
 933   (void)arg;
 934   cons1 = smartlist_new();
 935   cons2 = smartlist_new();
 936
 937   /* Identity hashes are not sorted properly, return NULL.
 938    * Already tested in gen_ed_diff, but see that a NULL ed diff also makes
 939    * gen_diff return NULL. */
 940   cons1_str = tor_strdup(
 941       "network-status-version foo\n"
 942       "r name bbbbbbbbbbbbbbbbb etc\nfoo\n"
 943       "r name aaaaaaaaaaaaaaaaa etc\nbar\n"
 944       "directory-signature foo bar\nbar\n"
 945       );
 946   cons2_str = tor_strdup(
 947       "network-status-version foo\n"
 948       "r name aaaaaaaaaaaaaaaaa etc\nfoo\n"
 949       "r name ccccccccccccccccc etc\nbar\n"
 950       "directory-signature foo bar\nbar\n"
 951       );
 952
 953   tt_int_op(0, OP_EQ,
 954       consensus_compute_digest_as_signed_(cons1_str, &digests1));
 955   tt_int_op(0, OP_EQ,
 956       consensus_compute_digest_(cons2_str, &digests2));
 957
 958   consensus_split_lines_(cons1, cons1_str, area);
 959   consensus_split_lines_(cons2, cons2_str, area);
 960
 961   diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2, area);
 962   tt_ptr_op(NULL, OP_EQ, diff);
 963
 964   /* Check that the headers are done properly. */
 965   tor_free(cons1_str);
 966   cons1_str = tor_strdup(
 967       "network-status-version foo\n"
 968       "r name ccccccccccccccccc etc\nfoo\n"
 969       "r name eeeeeeeeeeeeeeeee etc\nbar\n"
 970       "directory-signature foo bar\nbar\n"
 971       );
 972   tt_int_op(0, OP_EQ,
 973       consensus_compute_digest_as_signed_(cons1_str, &digests1));
 974   smartlist_clear(cons1);
 975   consensus_split_lines_(cons1, cons1_str, area);
 976   diff = consdiff_gen_diff(cons1, cons2, &digests1, &digests2, area);
 977   tt_ptr_op(NULL, OP_NE, diff);
 978   tt_int_op(11, OP_EQ, smartlist_len(diff));
 979   tt_assert(line_str_eq(smartlist_get(diff, 0),
 980                         "network-status-diff-version 1"));
 981   tt_assert(line_str_eq(smartlist_get(diff, 1), "hash "
 982       "95D70F5A3CC65F920AA8B44C4563D7781A082674329661884E19E94B79D539C2 "
 983       "7AFECEFA4599BA33D603653E3D2368F648DF4AC4723929B0F7CF39281596B0C1"));
 984   tt_assert(line_str_eq(smartlist_get(diff, 2), "6,$d"));
 985   tt_assert(line_str_eq(smartlist_get(diff, 3), "3,4c"));
 986   tt_assert(line_str_eq(smartlist_get(diff, 4), "bar"));
 987   tt_assert(line_str_eq(smartlist_get(diff, 5),
 988                         "directory-signature foo bar"));
 989   tt_assert(line_str_eq(smartlist_get(diff, 6),
 990                         "."));
 991   tt_assert(line_str_eq(smartlist_get(diff, 7), "1a"));
 992   tt_assert(line_str_eq(smartlist_get(diff, 8),
 993                         "r name aaaaaaaaaaaaaaaaa etc"));
 994   tt_assert(line_str_eq(smartlist_get(diff, 9), "foo"));
 995   tt_assert(line_str_eq(smartlist_get(diff, 10), "."));
 996
 997   /* TODO: small real use-cases, i.e. consensuses. */
 998
 999  done:
1000   tor_free(cons1_str);
1001   tor_free(cons2_str);
1002   smartlist_free(cons1);
1003   smartlist_free(cons2);
1004   smartlist_free(diff);
1005   memarea_drop_all(area);
1006 }
1007
1008 static void
1009 test_consdiff_apply_diff(void *arg)
1010 {
1011   smartlist_t *cons1=NULL, *diff=NULL;
1012   char *cons1_str=NULL, *cons2 = NULL;
1013   consensus_digest_t digests1;
1014   (void)arg;
1015   memarea_t *area = memarea_new();
1016   cons1 = smartlist_new();
1017   diff = smartlist_new();
1018   setup_capture_of_logs(LOG_INFO);
1019
1020   cons1_str = tor_strdup(
1021       "network-status-version foo\n"
1022       "r name ccccccccccccccccc etc\nfoo\n"
1023       "r name eeeeeeeeeeeeeeeee etc\nbar\n"
1024       "directory-signature foo bar\nbar\n"
1025       );
1026   tt_int_op(0, OP_EQ,
1027       consensus_compute_digest_(cons1_str, &digests1));
1028   consensus_split_lines_(cons1, cons1_str, area);
1029
1030   /* diff doesn't have enough lines. */
1031   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1032   tt_ptr_op(NULL, OP_EQ, cons2);
1033   expect_single_log_msg_containing("too short")
1034
1035   /* first line doesn't match format-version string. */
1036   smartlist_add_linecpy(diff, area, "foo-bar");
1037   smartlist_add_linecpy(diff, area, "header-line");
1038   mock_clean_saved_logs();
1039   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1040   tt_ptr_op(NULL, OP_EQ, cons2);
1041   expect_single_log_msg_containing("format is not known")
1042
1043   /* The first word of the second header line is not "hash". */
1044   smartlist_clear(diff);
1045   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1046   smartlist_add_linecpy(diff, area, "word a b");
1047   smartlist_add_linecpy(diff, area, "x");
1048   mock_clean_saved_logs();
1049   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1050   tt_ptr_op(NULL, OP_EQ, cons2);
1051   expect_single_log_msg_containing("does not include the necessary digests")
1052
1053   /* Wrong number of words after "hash". */
1054   smartlist_clear(diff);
1055   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1056   smartlist_add_linecpy(diff, area, "hash a b c");
1057   mock_clean_saved_logs();
1058   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1059   tt_ptr_op(NULL, OP_EQ, cons2);
1060   expect_single_log_msg_containing("does not include the necessary digests")
1061
1062   /* base16 digests do not have the expected length. */
1063   smartlist_clear(diff);
1064   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1065   smartlist_add_linecpy(diff, area, "hash aaa bbb");
1066   mock_clean_saved_logs();
1067   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1068   tt_ptr_op(NULL, OP_EQ, cons2);
1069   expect_single_log_msg_containing("includes base16-encoded digests of "
1070                                    "incorrect size")
1071
1072   /* base16 digests contain non-base16 characters. */
1073   smartlist_clear(diff);
1074   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1075   smartlist_add_linecpy(diff, area, "hash"
1076       " ????????????????????????????????????????????????????????????????"
1077       " ----------------------------------------------------------------");
1078   mock_clean_saved_logs();
1079   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1080   tt_ptr_op(NULL, OP_EQ, cons2);
1081   expect_single_log_msg_containing("includes malformed digests")
1082
1083   /* Invalid ed diff.
1084    * As tested in apply_ed_diff, but check that apply_diff does return NULL if
1085    * the ed diff can't be applied. */
1086   smartlist_clear(diff);
1087   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1088   smartlist_add_linecpy(diff, area, "hash"
1089       /* sha3 of cons1. */
1090       " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4"
1091       /* sha256 of cons2. */
1092       " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA");
1093   smartlist_add_linecpy(diff, area, "foobar");
1094   mock_clean_saved_logs();
1095   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1096   tt_ptr_op(NULL, OP_EQ, cons2);
1097   expect_single_log_msg_containing("because an ed command was missing a line "
1098                                    "number")
1099
1100   /* Base consensus doesn't match its digest as found in the diff. */
1101   smartlist_clear(diff);
1102   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1103   smartlist_add_linecpy(diff, area, "hash"
1104       /* bogus sha256. */
1105       " 3333333333333333333333333333333333333333333333333333333333333333"
1106       /* sha256 of cons2. */
1107       " 635D34593020C08E5ECD865F9986E29D50028EFA62843766A8197AD228A7F6AA");
1108   mock_clean_saved_logs();
1109   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1110   tt_ptr_op(NULL, OP_EQ, cons2);
1111   expect_log_msg_containing("base consensus doesn't match the digest "
1112                             "as found");
1113
1114   /* Resulting consensus doesn't match its digest as found in the diff. */
1115   smartlist_clear(diff);
1116   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1117   smartlist_add_linecpy(diff, area, "hash"
1118       /* sha3 of cons1. */
1119       " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4"
1120       /* bogus sha3. */
1121       " 3333333333333333333333333333333333333333333333333333333333333333");
1122   mock_clean_saved_logs();
1123   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1124   tt_ptr_op(NULL, OP_EQ, cons2);
1125   expect_log_msg_containing("resulting consensus doesn't match the "
1126                             "digest as found");
1127
1128 #if 0
1129   /* XXXX No longer possible, since we aren't using the other algorithm. */
1130   /* Resulting consensus digest cannot be computed */
1131   smartlist_clear(diff);
1132   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1133   smartlist_add_linecpy(diff, area, "hash"
1134       /* sha3 of cons1. */
1135       " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4"
1136       /* bogus sha3. */
1137       " 3333333333333333333333333333333333333333333333333333333333333333");
1138   smartlist_add_linecpy(diff, area, "1,2d"); // remove starting line
1139   mock_clean_saved_logs();
1140   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1141   tt_ptr_op(NULL, OP_EQ, cons2);
1142   expect_log_msg_containing("Could not compute digests of the consensus "
1143                             "resulting from applying a consensus diff.");
1144 #endif /* 0 */
1145
1146   /* Very simple test, only to see that nothing errors. */
1147   smartlist_clear(diff);
1148   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1149   smartlist_add_linecpy(diff, area, "hash"
1150       /* sha3 of cons1. */
1151       " 06646D6CF563A41869D3B02E73254372AE3140046C5E7D83C9F71E54976AF9B4"
1152       /* sha3 of cons2. */
1153       " 90A418881B2FCAB3D9E60EE02E4D666D56CFA38F8A3B7AA3E0ADBA530DDA9353");
1154   smartlist_add_linecpy(diff, area, "3c");
1155   smartlist_add_linecpy(diff, area, "sample");
1156   smartlist_add_linecpy(diff, area, ".");
1157   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1158   tt_ptr_op(NULL, OP_NE, cons2);
1159   tt_str_op(
1160       "network-status-version foo\n"
1161       "r name ccccccccccccccccc etc\nsample\n"
1162       "r name eeeeeeeeeeeeeeeee etc\nbar\n"
1163       "directory-signature foo bar\nbar\n", OP_EQ,
1164       cons2);
1165   tor_free(cons2);
1166
1167   /* Check that lowercase letters in base16-encoded digests work too. */
1168   smartlist_clear(diff);
1169   smartlist_add_linecpy(diff, area, "network-status-diff-version 1");
1170   smartlist_add_linecpy(diff, area, "hash"
1171       /* sha3 of cons1. */
1172       " 06646d6cf563a41869d3b02e73254372ae3140046c5e7d83c9f71e54976af9b4"
1173       /* sha3 of cons2. */
1174       " 90a418881b2fcab3d9e60ee02e4d666d56cfa38f8a3b7aa3e0adba530dda9353");
1175   smartlist_add_linecpy(diff, area, "3c");
1176   smartlist_add_linecpy(diff, area, "sample");
1177   smartlist_add_linecpy(diff, area, ".");
1178   cons2 = consdiff_apply_diff(cons1, diff, &digests1);
1179   tt_ptr_op(NULL, OP_NE, cons2);
1180   tt_str_op(
1181       "network-status-version foo\n"
1182       "r name ccccccccccccccccc etc\nsample\n"
1183       "r name eeeeeeeeeeeeeeeee etc\nbar\n"
1184       "directory-signature foo bar\nbar\n", OP_EQ,
1185       cons2);
1186   tor_free(cons2);
1187
1188   smartlist_clear(diff);
1189
1190  done:
1191   teardown_capture_of_logs();
1192   tor_free(cons1_str);
1193   smartlist_free(cons1);
1194   smartlist_free(diff);
1195   memarea_drop_all(area);
1196 }
1197
1198 #define CONSDIFF_LEGACY(name)                                          \
1199   { #name, test_consdiff_ ## name , 0, NULL, NULL }
1200
1201 struct testcase_t consdiff_tests[] = {
1202   CONSDIFF_LEGACY(smartlist_slice),
1203   CONSDIFF_LEGACY(smartlist_slice_string_pos),
1204   CONSDIFF_LEGACY(lcs_lengths),
1205   CONSDIFF_LEGACY(trim_slices),
1206   CONSDIFF_LEGACY(set_changed),
1207   CONSDIFF_LEGACY(calc_changes),
1208   CONSDIFF_LEGACY(get_id_hash),
1209   CONSDIFF_LEGACY(is_valid_router_entry),
1210   CONSDIFF_LEGACY(next_router),
1211   CONSDIFF_LEGACY(base64cmp),
1212   CONSDIFF_LEGACY(gen_ed_diff),
1213   CONSDIFF_LEGACY(apply_ed_diff),
1214   CONSDIFF_LEGACY(gen_diff),
1215   CONSDIFF_LEGACY(apply_diff),
1216   END_OF_TESTCASES
1217 };