reftable/record.c

   1 /*
   2 Copyright 2020 Google LLC
   3
   4 Use of this source code is governed by a BSD-style
   5 license that can be found in the LICENSE file or at
   6 https://developers.google.com/open-source/licenses/bsd
   7 */
   8
   9 /* record.c - methods for different types of records. */
  10
  11 #include "record.h"
  12
  13 #include "system.h"
  14 #include "constants.h"
  15 #include "reftable-error.h"
  16 #include "basics.h"
  17
  18 static struct reftable_record_vtable *
  19 reftable_record_vtable(struct reftable_record *rec);
  20 static void *reftable_record_data(struct reftable_record *rec);
  21
  22 int get_var_int(uint64_t *dest, struct string_view *in)
  23 {
  24         int ptr = 0;
  25         uint64_t val;
  26
  27         if (in->len == 0)
  28                 return -1;
  29         val = in->buf[ptr] & 0x7f;
  30
  31         while (in->buf[ptr] & 0x80) {
  32                 ptr++;
  33                 if (ptr > in->len) {
  34                         return -1;
  35                 }
  36                 val = (val + 1) << 7 | (uint64_t)(in->buf[ptr] & 0x7f);
  37         }
  38
  39         *dest = val;
  40         return ptr + 1;
  41 }
  42
  43 int put_var_int(struct string_view *dest, uint64_t val)
  44 {
  45         uint8_t buf[10] = { 0 };
  46         int i = 9;
  47         int n = 0;
  48         buf[i] = (uint8_t)(val & 0x7f);
  49         i--;
  50         while (1) {
  51                 val >>= 7;
  52                 if (!val) {
  53                         break;
  54                 }
  55                 val--;
  56                 buf[i] = 0x80 | (uint8_t)(val & 0x7f);
  57                 i--;
  58         }
  59
  60         n = sizeof(buf) - i - 1;
  61         if (dest->len < n)
  62                 return -1;
  63         memcpy(dest->buf, &buf[i + 1], n);
  64         return n;
  65 }
  66
  67 int reftable_is_block_type(uint8_t typ)
  68 {
  69         switch (typ) {
  70         case BLOCK_TYPE_REF:
  71         case BLOCK_TYPE_LOG:
  72         case BLOCK_TYPE_OBJ:
  73         case BLOCK_TYPE_INDEX:
  74                 return 1;
  75         }
  76         return 0;
  77 }
  78
  79 const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec)
  80 {
  81         switch (rec->value_type) {
  82         case REFTABLE_REF_VAL1:
  83                 return rec->value.val1;
  84         case REFTABLE_REF_VAL2:
  85                 return rec->value.val2.value;
  86         default:
  87                 return NULL;
  88         }
  89 }
  90
  91 const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec)
  92 {
  93         switch (rec->value_type) {
  94         case REFTABLE_REF_VAL2:
  95                 return rec->value.val2.target_value;
  96         default:
  97                 return NULL;
  98         }
  99 }
 100
 101 static int decode_string(struct strbuf *dest, struct string_view in)
 102 {
 103         int start_len = in.len;
 104         uint64_t tsize = 0;
 105         int n = get_var_int(&tsize, &in);
 106         if (n <= 0)
 107                 return -1;
 108         string_view_consume(&in, n);
 109         if (in.len < tsize)
 110                 return -1;
 111
 112         strbuf_reset(dest);
 113         strbuf_add(dest, in.buf, tsize);
 114         string_view_consume(&in, tsize);
 115
 116         return start_len - in.len;
 117 }
 118
 119 static int encode_string(char *str, struct string_view s)
 120 {
 121         struct string_view start = s;
 122         int l = strlen(str);
 123         int n = put_var_int(&s, l);
 124         if (n < 0)
 125                 return -1;
 126         string_view_consume(&s, n);
 127         if (s.len < l)
 128                 return -1;
 129         memcpy(s.buf, str, l);
 130         string_view_consume(&s, l);
 131
 132         return start.len - s.len;
 133 }
 134
 135 int reftable_encode_key(int *restart, struct string_view dest,
 136                         struct strbuf prev_key, struct strbuf key,
 137                         uint8_t extra)
 138 {
 139         struct string_view start = dest;
 140         int prefix_len = common_prefix_size(&prev_key, &key);
 141         uint64_t suffix_len = key.len - prefix_len;
 142         int n = put_var_int(&dest, (uint64_t)prefix_len);
 143         if (n < 0)
 144                 return -1;
 145         string_view_consume(&dest, n);
 146
 147         *restart = (prefix_len == 0);
 148
 149         n = put_var_int(&dest, suffix_len << 3 | (uint64_t)extra);
 150         if (n < 0)
 151                 return -1;
 152         string_view_consume(&dest, n);
 153
 154         if (dest.len < suffix_len)
 155                 return -1;
 156         memcpy(dest.buf, key.buf + prefix_len, suffix_len);
 157         string_view_consume(&dest, suffix_len);
 158
 159         return start.len - dest.len;
 160 }
 161
 162 int reftable_decode_keylen(struct string_view in,
 163                            uint64_t *prefix_len,
 164                            uint64_t *suffix_len,
 165                            uint8_t *extra)
 166 {
 167         size_t start_len = in.len;
 168         int n;
 169
 170         n = get_var_int(prefix_len, &in);
 171         if (n < 0)
 172                 return -1;
 173         string_view_consume(&in, n);
 174
 175         n = get_var_int(suffix_len, &in);
 176         if (n <= 0)
 177                 return -1;
 178         string_view_consume(&in, n);
 179
 180         *extra = (uint8_t)(*suffix_len & 0x7);
 181         *suffix_len >>= 3;
 182
 183         return start_len - in.len;
 184 }
 185
 186 int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,
 187                         struct string_view in)
 188 {
 189         int start_len = in.len;
 190         uint64_t prefix_len = 0;
 191         uint64_t suffix_len = 0;
 192         int n;
 193
 194         n = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);
 195         if (n < 0)
 196                 return -1;
 197         string_view_consume(&in, n);
 198
 199         if (in.len < suffix_len ||
 200             prefix_len > last_key->len)
 201                 return -1;
 202
 203         strbuf_setlen(last_key, prefix_len);
 204         strbuf_add(last_key, in.buf, suffix_len);
 205         string_view_consume(&in, suffix_len);
 206
 207         return start_len - in.len;
 208 }
 209
 210 static void reftable_ref_record_key(const void *r, struct strbuf *dest)
 211 {
 212         const struct reftable_ref_record *rec =
 213                 (const struct reftable_ref_record *)r;
 214         strbuf_reset(dest);
 215         strbuf_addstr(dest, rec->refname);
 216 }
 217
 218 static void reftable_ref_record_copy_from(void *rec, const void *src_rec,
 219                                           int hash_size)
 220 {
 221         struct reftable_ref_record *ref = rec;
 222         const struct reftable_ref_record *src = src_rec;
 223         char *refname = NULL;
 224         size_t refname_cap = 0;
 225
 226         assert(hash_size > 0);
 227
 228         SWAP(refname, ref->refname);
 229         SWAP(refname_cap, ref->refname_cap);
 230         reftable_ref_record_release(ref);
 231         SWAP(ref->refname, refname);
 232         SWAP(ref->refname_cap, refname_cap);
 233
 234         if (src->refname) {
 235                 size_t refname_len = strlen(src->refname);
 236
 237                 REFTABLE_ALLOC_GROW(ref->refname, refname_len + 1,
 238                                     ref->refname_cap);
 239                 memcpy(ref->refname, src->refname, refname_len);
 240                 ref->refname[refname_len] = 0;
 241         }
 242
 243         ref->update_index = src->update_index;
 244         ref->value_type = src->value_type;
 245         switch (src->value_type) {
 246         case REFTABLE_REF_DELETION:
 247                 break;
 248         case REFTABLE_REF_VAL1:
 249                 memcpy(ref->value.val1, src->value.val1, hash_size);
 250                 break;
 251         case REFTABLE_REF_VAL2:
 252                 memcpy(ref->value.val2.value, src->value.val2.value, hash_size);
 253                 memcpy(ref->value.val2.target_value,
 254                        src->value.val2.target_value, hash_size);
 255                 break;
 256         case REFTABLE_REF_SYMREF:
 257                 ref->value.symref = xstrdup(src->value.symref);
 258                 break;
 259         }
 260 }
 261
 262 static char hexdigit(int c)
 263 {
 264         if (c <= 9)
 265                 return '0' + c;
 266         return 'a' + (c - 10);
 267 }
 268
 269 static void hex_format(char *dest, const unsigned char *src, int hash_size)
 270 {
 271         assert(hash_size > 0);
 272         if (src) {
 273                 int i = 0;
 274                 for (i = 0; i < hash_size; i++) {
 275                         dest[2 * i] = hexdigit(src[i] >> 4);
 276                         dest[2 * i + 1] = hexdigit(src[i] & 0xf);
 277                 }
 278                 dest[2 * hash_size] = 0;
 279         }
 280 }
 281
 282 static void reftable_ref_record_print_sz(const struct reftable_ref_record *ref,
 283                                          int hash_size)
 284 {
 285         char hex[GIT_MAX_HEXSZ + 1] = { 0 }; /* BUG */
 286         printf("ref{%s(%" PRIu64 ") ", ref->refname, ref->update_index);
 287         switch (ref->value_type) {
 288         case REFTABLE_REF_SYMREF:
 289                 printf("=> %s", ref->value.symref);
 290                 break;
 291         case REFTABLE_REF_VAL2:
 292                 hex_format(hex, ref->value.val2.value, hash_size);
 293                 printf("val 2 %s", hex);
 294                 hex_format(hex, ref->value.val2.target_value,
 295                            hash_size);
 296                 printf("(T %s)", hex);
 297                 break;
 298         case REFTABLE_REF_VAL1:
 299                 hex_format(hex, ref->value.val1, hash_size);
 300                 printf("val 1 %s", hex);
 301                 break;
 302         case REFTABLE_REF_DELETION:
 303                 printf("delete");
 304                 break;
 305         }
 306         printf("}\n");
 307 }
 308
 309 void reftable_ref_record_print(const struct reftable_ref_record *ref,
 310                                uint32_t hash_id) {
 311         reftable_ref_record_print_sz(ref, hash_size(hash_id));
 312 }
 313
 314 static void reftable_ref_record_release_void(void *rec)
 315 {
 316         reftable_ref_record_release(rec);
 317 }
 318
 319 void reftable_ref_record_release(struct reftable_ref_record *ref)
 320 {
 321         switch (ref->value_type) {
 322         case REFTABLE_REF_SYMREF:
 323                 reftable_free(ref->value.symref);
 324                 break;
 325         case REFTABLE_REF_VAL2:
 326                 break;
 327         case REFTABLE_REF_VAL1:
 328                 break;
 329         case REFTABLE_REF_DELETION:
 330                 break;
 331         default:
 332                 abort();
 333         }
 334
 335         reftable_free(ref->refname);
 336         memset(ref, 0, sizeof(struct reftable_ref_record));
 337 }
 338
 339 static uint8_t reftable_ref_record_val_type(const void *rec)
 340 {
 341         const struct reftable_ref_record *r =
 342                 (const struct reftable_ref_record *)rec;
 343         return r->value_type;
 344 }
 345
 346 static int reftable_ref_record_encode(const void *rec, struct string_view s,
 347                                       int hash_size)
 348 {
 349         const struct reftable_ref_record *r =
 350                 (const struct reftable_ref_record *)rec;
 351         struct string_view start = s;
 352         int n = put_var_int(&s, r->update_index);
 353         assert(hash_size > 0);
 354         if (n < 0)
 355                 return -1;
 356         string_view_consume(&s, n);
 357
 358         switch (r->value_type) {
 359         case REFTABLE_REF_SYMREF:
 360                 n = encode_string(r->value.symref, s);
 361                 if (n < 0) {
 362                         return -1;
 363                 }
 364                 string_view_consume(&s, n);
 365                 break;
 366         case REFTABLE_REF_VAL2:
 367                 if (s.len < 2 * hash_size) {
 368                         return -1;
 369                 }
 370                 memcpy(s.buf, r->value.val2.value, hash_size);
 371                 string_view_consume(&s, hash_size);
 372                 memcpy(s.buf, r->value.val2.target_value, hash_size);
 373                 string_view_consume(&s, hash_size);
 374                 break;
 375         case REFTABLE_REF_VAL1:
 376                 if (s.len < hash_size) {
 377                         return -1;
 378                 }
 379                 memcpy(s.buf, r->value.val1, hash_size);
 380                 string_view_consume(&s, hash_size);
 381                 break;
 382         case REFTABLE_REF_DELETION:
 383                 break;
 384         default:
 385                 abort();
 386         }
 387
 388         return start.len - s.len;
 389 }
 390
 391 static int reftable_ref_record_decode(void *rec, struct strbuf key,
 392                                       uint8_t val_type, struct string_view in,
 393                                       int hash_size, struct strbuf *scratch)
 394 {
 395         struct reftable_ref_record *r = rec;
 396         struct string_view start = in;
 397         uint64_t update_index = 0;
 398         const char *refname = NULL;
 399         size_t refname_cap = 0;
 400         int n;
 401
 402         assert(hash_size > 0);
 403
 404         n = get_var_int(&update_index, &in);
 405         if (n < 0)
 406                 return n;
 407         string_view_consume(&in, n);
 408
 409         SWAP(refname, r->refname);
 410         SWAP(refname_cap, r->refname_cap);
 411         reftable_ref_record_release(r);
 412         SWAP(r->refname, refname);
 413         SWAP(r->refname_cap, refname_cap);
 414
 415         REFTABLE_ALLOC_GROW(r->refname, key.len + 1, r->refname_cap);
 416         memcpy(r->refname, key.buf, key.len);
 417         r->refname[key.len] = 0;
 418
 419         r->update_index = update_index;
 420         r->value_type = val_type;
 421         switch (val_type) {
 422         case REFTABLE_REF_VAL1:
 423                 if (in.len < hash_size) {
 424                         return -1;
 425                 }
 426
 427                 memcpy(r->value.val1, in.buf, hash_size);
 428                 string_view_consume(&in, hash_size);
 429                 break;
 430
 431         case REFTABLE_REF_VAL2:
 432                 if (in.len < 2 * hash_size) {
 433                         return -1;
 434                 }
 435
 436                 memcpy(r->value.val2.value, in.buf, hash_size);
 437                 string_view_consume(&in, hash_size);
 438
 439                 memcpy(r->value.val2.target_value, in.buf, hash_size);
 440                 string_view_consume(&in, hash_size);
 441                 break;
 442
 443         case REFTABLE_REF_SYMREF: {
 444                 int n = decode_string(scratch, in);
 445                 if (n < 0) {
 446                         return -1;
 447                 }
 448                 string_view_consume(&in, n);
 449                 r->value.symref = strbuf_detach(scratch, NULL);
 450         } break;
 451
 452         case REFTABLE_REF_DELETION:
 453                 break;
 454         default:
 455                 abort();
 456                 break;
 457         }
 458
 459         return start.len - in.len;
 460 }
 461
 462 static int reftable_ref_record_is_deletion_void(const void *p)
 463 {
 464         return reftable_ref_record_is_deletion(
 465                 (const struct reftable_ref_record *)p);
 466 }
 467
 468 static int reftable_ref_record_equal_void(const void *a,
 469                                           const void *b, int hash_size)
 470 {
 471         struct reftable_ref_record *ra = (struct reftable_ref_record *) a;
 472         struct reftable_ref_record *rb = (struct reftable_ref_record *) b;
 473         return reftable_ref_record_equal(ra, rb, hash_size);
 474 }
 475
 476 static int reftable_ref_record_cmp_void(const void *_a, const void *_b)
 477 {
 478         const struct reftable_ref_record *a = _a;
 479         const struct reftable_ref_record *b = _b;
 480         return strcmp(a->refname, b->refname);
 481 }
 482
 483 static void reftable_ref_record_print_void(const void *rec,
 484                                            int hash_size)
 485 {
 486         reftable_ref_record_print_sz((struct reftable_ref_record *) rec, hash_size);
 487 }
 488
 489 static struct reftable_record_vtable reftable_ref_record_vtable = {
 490         .key = &reftable_ref_record_key,
 491         .type = BLOCK_TYPE_REF,
 492         .copy_from = &reftable_ref_record_copy_from,
 493         .val_type = &reftable_ref_record_val_type,
 494         .encode = &reftable_ref_record_encode,
 495         .decode = &reftable_ref_record_decode,
 496         .release = &reftable_ref_record_release_void,
 497         .is_deletion = &reftable_ref_record_is_deletion_void,
 498         .equal = &reftable_ref_record_equal_void,
 499         .cmp = &reftable_ref_record_cmp_void,
 500         .print = &reftable_ref_record_print_void,
 501 };
 502
 503 static void reftable_obj_record_key(const void *r, struct strbuf *dest)
 504 {
 505         const struct reftable_obj_record *rec =
 506                 (const struct reftable_obj_record *)r;
 507         strbuf_reset(dest);
 508         strbuf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
 509 }
 510
 511 static void reftable_obj_record_release(void *rec)
 512 {
 513         struct reftable_obj_record *obj = rec;
 514         FREE_AND_NULL(obj->hash_prefix);
 515         FREE_AND_NULL(obj->offsets);
 516         memset(obj, 0, sizeof(struct reftable_obj_record));
 517 }
 518
 519 static void reftable_obj_record_print(const void *rec, int hash_size)
 520 {
 521         const struct reftable_obj_record *obj = rec;
 522         char hex[GIT_MAX_HEXSZ + 1] = { 0 };
 523         struct strbuf offset_str = STRBUF_INIT;
 524         int i;
 525
 526         for (i = 0; i < obj->offset_len; i++)
 527                 strbuf_addf(&offset_str, "%" PRIu64 " ", obj->offsets[i]);
 528         hex_format(hex, obj->hash_prefix, obj->hash_prefix_len);
 529         printf("prefix %s (len %d), offsets [%s]\n",
 530                hex, obj->hash_prefix_len, offset_str.buf);
 531         strbuf_release(&offset_str);
 532 }
 533
 534 static void reftable_obj_record_copy_from(void *rec, const void *src_rec,
 535                                           int hash_size)
 536 {
 537         struct reftable_obj_record *obj = rec;
 538         const struct reftable_obj_record *src =
 539                 (const struct reftable_obj_record *)src_rec;
 540
 541         reftable_obj_record_release(obj);
 542
 543         REFTABLE_ALLOC_ARRAY(obj->hash_prefix, src->hash_prefix_len);
 544         obj->hash_prefix_len = src->hash_prefix_len;
 545         if (src->hash_prefix_len)
 546                 memcpy(obj->hash_prefix, src->hash_prefix, obj->hash_prefix_len);
 547
 548         REFTABLE_ALLOC_ARRAY(obj->offsets, src->offset_len);
 549         obj->offset_len = src->offset_len;
 550         COPY_ARRAY(obj->offsets, src->offsets, src->offset_len);
 551 }
 552
 553 static uint8_t reftable_obj_record_val_type(const void *rec)
 554 {
 555         const struct reftable_obj_record *r = rec;
 556         if (r->offset_len > 0 && r->offset_len < 8)
 557                 return r->offset_len;
 558         return 0;
 559 }
 560
 561 static int reftable_obj_record_encode(const void *rec, struct string_view s,
 562                                       int hash_size)
 563 {
 564         const struct reftable_obj_record *r = rec;
 565         struct string_view start = s;
 566         int i = 0;
 567         int n = 0;
 568         uint64_t last = 0;
 569         if (r->offset_len == 0 || r->offset_len >= 8) {
 570                 n = put_var_int(&s, r->offset_len);
 571                 if (n < 0) {
 572                         return -1;
 573                 }
 574                 string_view_consume(&s, n);
 575         }
 576         if (r->offset_len == 0)
 577                 return start.len - s.len;
 578         n = put_var_int(&s, r->offsets[0]);
 579         if (n < 0)
 580                 return -1;
 581         string_view_consume(&s, n);
 582
 583         last = r->offsets[0];
 584         for (i = 1; i < r->offset_len; i++) {
 585                 int n = put_var_int(&s, r->offsets[i] - last);
 586                 if (n < 0) {
 587                         return -1;
 588                 }
 589                 string_view_consume(&s, n);
 590                 last = r->offsets[i];
 591         }
 592         return start.len - s.len;
 593 }
 594
 595 static int reftable_obj_record_decode(void *rec, struct strbuf key,
 596                                       uint8_t val_type, struct string_view in,
 597                                       int hash_size, struct strbuf *scratch UNUSED)
 598 {
 599         struct string_view start = in;
 600         struct reftable_obj_record *r = rec;
 601         uint64_t count = val_type;
 602         int n = 0;
 603         uint64_t last;
 604         int j;
 605
 606         reftable_obj_record_release(r);
 607
 608         REFTABLE_ALLOC_ARRAY(r->hash_prefix, key.len);
 609         memcpy(r->hash_prefix, key.buf, key.len);
 610         r->hash_prefix_len = key.len;
 611
 612         if (val_type == 0) {
 613                 n = get_var_int(&count, &in);
 614                 if (n < 0) {
 615                         return n;
 616                 }
 617
 618                 string_view_consume(&in, n);
 619         }
 620
 621         r->offsets = NULL;
 622         r->offset_len = 0;
 623         if (count == 0)
 624                 return start.len - in.len;
 625
 626         REFTABLE_ALLOC_ARRAY(r->offsets, count);
 627         r->offset_len = count;
 628
 629         n = get_var_int(&r->offsets[0], &in);
 630         if (n < 0)
 631                 return n;
 632         string_view_consume(&in, n);
 633
 634         last = r->offsets[0];
 635         j = 1;
 636         while (j < count) {
 637                 uint64_t delta = 0;
 638                 int n = get_var_int(&delta, &in);
 639                 if (n < 0) {
 640                         return n;
 641                 }
 642                 string_view_consume(&in, n);
 643
 644                 last = r->offsets[j] = (delta + last);
 645                 j++;
 646         }
 647         return start.len - in.len;
 648 }
 649
 650 static int not_a_deletion(const void *p)
 651 {
 652         return 0;
 653 }
 654
 655 static int reftable_obj_record_equal_void(const void *a, const void *b, int hash_size)
 656 {
 657         struct reftable_obj_record *ra = (struct reftable_obj_record *) a;
 658         struct reftable_obj_record *rb = (struct reftable_obj_record *) b;
 659
 660         if (ra->hash_prefix_len != rb->hash_prefix_len
 661             || ra->offset_len != rb->offset_len)
 662                 return 0;
 663
 664         if (ra->hash_prefix_len &&
 665             memcmp(ra->hash_prefix, rb->hash_prefix, ra->hash_prefix_len))
 666                 return 0;
 667         if (ra->offset_len &&
 668             memcmp(ra->offsets, rb->offsets, ra->offset_len * sizeof(uint64_t)))
 669                 return 0;
 670
 671         return 1;
 672 }
 673
 674 static int reftable_obj_record_cmp_void(const void *_a, const void *_b)
 675 {
 676         const struct reftable_obj_record *a = _a;
 677         const struct reftable_obj_record *b = _b;
 678         int cmp;
 679
 680         cmp = memcmp(a->hash_prefix, b->hash_prefix,
 681                      a->hash_prefix_len > b->hash_prefix_len ?
 682                      a->hash_prefix_len : b->hash_prefix_len);
 683         if (cmp)
 684                 return cmp;
 685
 686         /*
 687          * When the prefix is the same then the object record that is longer is
 688          * considered to be bigger.
 689          */
 690         return a->hash_prefix_len - b->hash_prefix_len;
 691 }
 692
 693 static struct reftable_record_vtable reftable_obj_record_vtable = {
 694         .key = &reftable_obj_record_key,
 695         .type = BLOCK_TYPE_OBJ,
 696         .copy_from = &reftable_obj_record_copy_from,
 697         .val_type = &reftable_obj_record_val_type,
 698         .encode = &reftable_obj_record_encode,
 699         .decode = &reftable_obj_record_decode,
 700         .release = &reftable_obj_record_release,
 701         .is_deletion = &not_a_deletion,
 702         .equal = &reftable_obj_record_equal_void,
 703         .cmp = &reftable_obj_record_cmp_void,
 704         .print = &reftable_obj_record_print,
 705 };
 706
 707 static void reftable_log_record_print_sz(struct reftable_log_record *log,
 708                                          int hash_size)
 709 {
 710         char hex[GIT_MAX_HEXSZ + 1] = { 0 };
 711
 712         switch (log->value_type) {
 713         case REFTABLE_LOG_DELETION:
 714                 printf("log{%s(%" PRIu64 ") delete\n", log->refname,
 715                        log->update_index);
 716                 break;
 717         case REFTABLE_LOG_UPDATE:
 718                 printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n",
 719                        log->refname, log->update_index,
 720                        log->value.update.name ? log->value.update.name : "",
 721                        log->value.update.email ? log->value.update.email : "",
 722                        log->value.update.time,
 723                        log->value.update.tz_offset);
 724                 hex_format(hex, log->value.update.old_hash, hash_size);
 725                 printf("%s => ", hex);
 726                 hex_format(hex, log->value.update.new_hash, hash_size);
 727                 printf("%s\n\n%s\n}\n", hex,
 728                        log->value.update.message ? log->value.update.message : "");
 729                 break;
 730         }
 731 }
 732
 733 void reftable_log_record_print(struct reftable_log_record *log,
 734                                       uint32_t hash_id)
 735 {
 736         reftable_log_record_print_sz(log, hash_size(hash_id));
 737 }
 738
 739 static void reftable_log_record_key(const void *r, struct strbuf *dest)
 740 {
 741         const struct reftable_log_record *rec =
 742                 (const struct reftable_log_record *)r;
 743         int len = strlen(rec->refname);
 744         uint8_t i64[8];
 745         uint64_t ts = 0;
 746         strbuf_reset(dest);
 747         strbuf_add(dest, (uint8_t *)rec->refname, len + 1);
 748
 749         ts = (~ts) - rec->update_index;
 750         put_be64(&i64[0], ts);
 751         strbuf_add(dest, i64, sizeof(i64));
 752 }
 753
 754 static void reftable_log_record_copy_from(void *rec, const void *src_rec,
 755                                           int hash_size)
 756 {
 757         struct reftable_log_record *dst = rec;
 758         const struct reftable_log_record *src =
 759                 (const struct reftable_log_record *)src_rec;
 760
 761         reftable_log_record_release(dst);
 762         *dst = *src;
 763         if (dst->refname) {
 764                 dst->refname = xstrdup(dst->refname);
 765         }
 766         switch (dst->value_type) {
 767         case REFTABLE_LOG_DELETION:
 768                 break;
 769         case REFTABLE_LOG_UPDATE:
 770                 if (dst->value.update.email) {
 771                         dst->value.update.email =
 772                                 xstrdup(dst->value.update.email);
 773                 }
 774                 if (dst->value.update.name) {
 775                         dst->value.update.name =
 776                                 xstrdup(dst->value.update.name);
 777                 }
 778                 if (dst->value.update.message) {
 779                         dst->value.update.message =
 780                                 xstrdup(dst->value.update.message);
 781                 }
 782
 783                 memcpy(dst->value.update.new_hash,
 784                        src->value.update.new_hash, hash_size);
 785                 memcpy(dst->value.update.old_hash,
 786                        src->value.update.old_hash, hash_size);
 787                 break;
 788         }
 789 }
 790
 791 static void reftable_log_record_release_void(void *rec)
 792 {
 793         struct reftable_log_record *r = rec;
 794         reftable_log_record_release(r);
 795 }
 796
 797 void reftable_log_record_release(struct reftable_log_record *r)
 798 {
 799         reftable_free(r->refname);
 800         switch (r->value_type) {
 801         case REFTABLE_LOG_DELETION:
 802                 break;
 803         case REFTABLE_LOG_UPDATE:
 804                 reftable_free(r->value.update.name);
 805                 reftable_free(r->value.update.email);
 806                 reftable_free(r->value.update.message);
 807                 break;
 808         }
 809         memset(r, 0, sizeof(struct reftable_log_record));
 810 }
 811
 812 static uint8_t reftable_log_record_val_type(const void *rec)
 813 {
 814         const struct reftable_log_record *log =
 815                 (const struct reftable_log_record *)rec;
 816
 817         return reftable_log_record_is_deletion(log) ? 0 : 1;
 818 }
 819
 820 static int reftable_log_record_encode(const void *rec, struct string_view s,
 821                                       int hash_size)
 822 {
 823         const struct reftable_log_record *r = rec;
 824         struct string_view start = s;
 825         int n = 0;
 826         if (reftable_log_record_is_deletion(r))
 827                 return 0;
 828
 829         if (s.len < 2 * hash_size)
 830                 return -1;
 831
 832         memcpy(s.buf, r->value.update.old_hash, hash_size);
 833         memcpy(s.buf + hash_size, r->value.update.new_hash, hash_size);
 834         string_view_consume(&s, 2 * hash_size);
 835
 836         n = encode_string(r->value.update.name ? r->value.update.name : "", s);
 837         if (n < 0)
 838                 return -1;
 839         string_view_consume(&s, n);
 840
 841         n = encode_string(r->value.update.email ? r->value.update.email : "",
 842                           s);
 843         if (n < 0)
 844                 return -1;
 845         string_view_consume(&s, n);
 846
 847         n = put_var_int(&s, r->value.update.time);
 848         if (n < 0)
 849                 return -1;
 850         string_view_consume(&s, n);
 851
 852         if (s.len < 2)
 853                 return -1;
 854
 855         put_be16(s.buf, r->value.update.tz_offset);
 856         string_view_consume(&s, 2);
 857
 858         n = encode_string(
 859                 r->value.update.message ? r->value.update.message : "", s);
 860         if (n < 0)
 861                 return -1;
 862         string_view_consume(&s, n);
 863
 864         return start.len - s.len;
 865 }
 866
 867 static int reftable_log_record_decode(void *rec, struct strbuf key,
 868                                       uint8_t val_type, struct string_view in,
 869                                       int hash_size, struct strbuf *scratch)
 870 {
 871         struct string_view start = in;
 872         struct reftable_log_record *r = rec;
 873         uint64_t max = 0;
 874         uint64_t ts = 0;
 875         int n;
 876
 877         if (key.len <= 9 || key.buf[key.len - 9] != 0)
 878                 return REFTABLE_FORMAT_ERROR;
 879
 880         REFTABLE_ALLOC_GROW(r->refname, key.len - 8, r->refname_cap);
 881         memcpy(r->refname, key.buf, key.len - 8);
 882         ts = get_be64(key.buf + key.len - 8);
 883
 884         r->update_index = (~max) - ts;
 885
 886         if (val_type != r->value_type) {
 887                 switch (r->value_type) {
 888                 case REFTABLE_LOG_UPDATE:
 889                         FREE_AND_NULL(r->value.update.message);
 890                         r->value.update.message_cap = 0;
 891                         FREE_AND_NULL(r->value.update.email);
 892                         FREE_AND_NULL(r->value.update.name);
 893                         break;
 894                 case REFTABLE_LOG_DELETION:
 895                         break;
 896                 }
 897         }
 898
 899         r->value_type = val_type;
 900         if (val_type == REFTABLE_LOG_DELETION)
 901                 return 0;
 902
 903         if (in.len < 2 * hash_size)
 904                 return REFTABLE_FORMAT_ERROR;
 905
 906         memcpy(r->value.update.old_hash, in.buf, hash_size);
 907         memcpy(r->value.update.new_hash, in.buf + hash_size, hash_size);
 908
 909         string_view_consume(&in, 2 * hash_size);
 910
 911         n = decode_string(scratch, in);
 912         if (n < 0)
 913                 goto done;
 914         string_view_consume(&in, n);
 915
 916         /*
 917          * In almost all cases we can expect the reflog name to not change for
 918          * reflog entries as they are tied to the local identity, not to the
 919          * target commits. As an optimization for this common case we can thus
 920          * skip copying over the name in case it's accurate already.
 921          */
 922         if (!r->value.update.name ||
 923             strcmp(r->value.update.name, scratch->buf)) {
 924                 r->value.update.name =
 925                         reftable_realloc(r->value.update.name, scratch->len + 1);
 926                 memcpy(r->value.update.name, scratch->buf, scratch->len);
 927                 r->value.update.name[scratch->len] = 0;
 928         }
 929
 930         n = decode_string(scratch, in);
 931         if (n < 0)
 932                 goto done;
 933         string_view_consume(&in, n);
 934
 935         /* Same as above, but for the reflog email. */
 936         if (!r->value.update.email ||
 937             strcmp(r->value.update.email, scratch->buf)) {
 938                 r->value.update.email =
 939                         reftable_realloc(r->value.update.email, scratch->len + 1);
 940                 memcpy(r->value.update.email, scratch->buf, scratch->len);
 941                 r->value.update.email[scratch->len] = 0;
 942         }
 943
 944         ts = 0;
 945         n = get_var_int(&ts, &in);
 946         if (n < 0)
 947                 goto done;
 948         string_view_consume(&in, n);
 949         r->value.update.time = ts;
 950         if (in.len < 2)
 951                 goto done;
 952
 953         r->value.update.tz_offset = get_be16(in.buf);
 954         string_view_consume(&in, 2);
 955
 956         n = decode_string(scratch, in);
 957         if (n < 0)
 958                 goto done;
 959         string_view_consume(&in, n);
 960
 961         REFTABLE_ALLOC_GROW(r->value.update.message, scratch->len + 1,
 962                             r->value.update.message_cap);
 963         memcpy(r->value.update.message, scratch->buf, scratch->len);
 964         r->value.update.message[scratch->len] = 0;
 965
 966         return start.len - in.len;
 967
 968 done:
 969         return REFTABLE_FORMAT_ERROR;
 970 }
 971
 972 static int null_streq(char *a, char *b)
 973 {
 974         char *empty = "";
 975         if (!a)
 976                 a = empty;
 977
 978         if (!b)
 979                 b = empty;
 980
 981         return 0 == strcmp(a, b);
 982 }
 983
 984 static int reftable_log_record_equal_void(const void *a,
 985                                           const void *b, int hash_size)
 986 {
 987         return reftable_log_record_equal((struct reftable_log_record *) a,
 988                                          (struct reftable_log_record *) b,
 989                                          hash_size);
 990 }
 991
 992 static int reftable_log_record_cmp_void(const void *_a, const void *_b)
 993 {
 994         const struct reftable_log_record *a = _a;
 995         const struct reftable_log_record *b = _b;
 996         int cmp = strcmp(a->refname, b->refname);
 997         if (cmp)
 998                 return cmp;
 999
1000         /*
1001          * Note that the comparison here is reversed. This is because the
1002          * update index is reversed when comparing keys. For reference, see how
1003          * we handle this in reftable_log_record_key()`.
1004          */
1005         return b->update_index - a->update_index;
1006 }
1007
1008 int reftable_log_record_equal(const struct reftable_log_record *a,
1009                               const struct reftable_log_record *b, int hash_size)
1010 {
1011         if (!(null_streq(a->refname, b->refname) &&
1012               a->update_index == b->update_index &&
1013               a->value_type == b->value_type))
1014                 return 0;
1015
1016         switch (a->value_type) {
1017         case REFTABLE_LOG_DELETION:
1018                 return 1;
1019         case REFTABLE_LOG_UPDATE:
1020                 return null_streq(a->value.update.name, b->value.update.name) &&
1021                        a->value.update.time == b->value.update.time &&
1022                        a->value.update.tz_offset == b->value.update.tz_offset &&
1023                        null_streq(a->value.update.email,
1024                                   b->value.update.email) &&
1025                        null_streq(a->value.update.message,
1026                                   b->value.update.message) &&
1027                        !memcmp(a->value.update.old_hash,
1028                                b->value.update.old_hash, hash_size) &&
1029                        !memcmp(a->value.update.new_hash,
1030                                b->value.update.new_hash, hash_size);
1031         }
1032
1033         abort();
1034 }
1035
1036 static int reftable_log_record_is_deletion_void(const void *p)
1037 {
1038         return reftable_log_record_is_deletion(
1039                 (const struct reftable_log_record *)p);
1040 }
1041
1042 static void reftable_log_record_print_void(const void *rec, int hash_size)
1043 {
1044         reftable_log_record_print_sz((struct reftable_log_record*)rec, hash_size);
1045 }
1046
1047 static struct reftable_record_vtable reftable_log_record_vtable = {
1048         .key = &reftable_log_record_key,
1049         .type = BLOCK_TYPE_LOG,
1050         .copy_from = &reftable_log_record_copy_from,
1051         .val_type = &reftable_log_record_val_type,
1052         .encode = &reftable_log_record_encode,
1053         .decode = &reftable_log_record_decode,
1054         .release = &reftable_log_record_release_void,
1055         .is_deletion = &reftable_log_record_is_deletion_void,
1056         .equal = &reftable_log_record_equal_void,
1057         .cmp = &reftable_log_record_cmp_void,
1058         .print = &reftable_log_record_print_void,
1059 };
1060
1061 static void reftable_index_record_key(const void *r, struct strbuf *dest)
1062 {
1063         const struct reftable_index_record *rec = r;
1064         strbuf_reset(dest);
1065         strbuf_addbuf(dest, &rec->last_key);
1066 }
1067
1068 static void reftable_index_record_copy_from(void *rec, const void *src_rec,
1069                                             int hash_size)
1070 {
1071         struct reftable_index_record *dst = rec;
1072         const struct reftable_index_record *src = src_rec;
1073
1074         strbuf_reset(&dst->last_key);
1075         strbuf_addbuf(&dst->last_key, &src->last_key);
1076         dst->offset = src->offset;
1077 }
1078
1079 static void reftable_index_record_release(void *rec)
1080 {
1081         struct reftable_index_record *idx = rec;
1082         strbuf_release(&idx->last_key);
1083 }
1084
1085 static uint8_t reftable_index_record_val_type(const void *rec)
1086 {
1087         return 0;
1088 }
1089
1090 static int reftable_index_record_encode(const void *rec, struct string_view out,
1091                                         int hash_size)
1092 {
1093         const struct reftable_index_record *r =
1094                 (const struct reftable_index_record *)rec;
1095         struct string_view start = out;
1096
1097         int n = put_var_int(&out, r->offset);
1098         if (n < 0)
1099                 return n;
1100
1101         string_view_consume(&out, n);
1102
1103         return start.len - out.len;
1104 }
1105
1106 static int reftable_index_record_decode(void *rec, struct strbuf key,
1107                                         uint8_t val_type, struct string_view in,
1108                                         int hash_size, struct strbuf *scratch UNUSED)
1109 {
1110         struct string_view start = in;
1111         struct reftable_index_record *r = rec;
1112         int n = 0;
1113
1114         strbuf_reset(&r->last_key);
1115         strbuf_addbuf(&r->last_key, &key);
1116
1117         n = get_var_int(&r->offset, &in);
1118         if (n < 0)
1119                 return n;
1120
1121         string_view_consume(&in, n);
1122         return start.len - in.len;
1123 }
1124
1125 static int reftable_index_record_equal(const void *a, const void *b, int hash_size)
1126 {
1127         struct reftable_index_record *ia = (struct reftable_index_record *) a;
1128         struct reftable_index_record *ib = (struct reftable_index_record *) b;
1129
1130         return ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);
1131 }
1132
1133 static int reftable_index_record_cmp(const void *_a, const void *_b)
1134 {
1135         const struct reftable_index_record *a = _a;
1136         const struct reftable_index_record *b = _b;
1137         return strbuf_cmp(&a->last_key, &b->last_key);
1138 }
1139
1140 static void reftable_index_record_print(const void *rec, int hash_size)
1141 {
1142         const struct reftable_index_record *idx = rec;
1143         /* TODO: escape null chars? */
1144         printf("\"%s\" %" PRIu64 "\n", idx->last_key.buf, idx->offset);
1145 }
1146
1147 static struct reftable_record_vtable reftable_index_record_vtable = {
1148         .key = &reftable_index_record_key,
1149         .type = BLOCK_TYPE_INDEX,
1150         .copy_from = &reftable_index_record_copy_from,
1151         .val_type = &reftable_index_record_val_type,
1152         .encode = &reftable_index_record_encode,
1153         .decode = &reftable_index_record_decode,
1154         .release = &reftable_index_record_release,
1155         .is_deletion = &not_a_deletion,
1156         .equal = &reftable_index_record_equal,
1157         .cmp = &reftable_index_record_cmp,
1158         .print = &reftable_index_record_print,
1159 };
1160
1161 void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)
1162 {
1163         reftable_record_vtable(rec)->key(reftable_record_data(rec), dest);
1164 }
1165
1166 int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
1167                            int hash_size)
1168 {
1169         return reftable_record_vtable(rec)->encode(reftable_record_data(rec),
1170                                                    dest, hash_size);
1171 }
1172
1173 void reftable_record_copy_from(struct reftable_record *rec,
1174                                struct reftable_record *src, int hash_size)
1175 {
1176         assert(src->type == rec->type);
1177
1178         reftable_record_vtable(rec)->copy_from(reftable_record_data(rec),
1179                                                reftable_record_data(src),
1180                                                hash_size);
1181 }
1182
1183 uint8_t reftable_record_val_type(struct reftable_record *rec)
1184 {
1185         return reftable_record_vtable(rec)->val_type(reftable_record_data(rec));
1186 }
1187
1188 int reftable_record_decode(struct reftable_record *rec, struct strbuf key,
1189                            uint8_t extra, struct string_view src, int hash_size,
1190                            struct strbuf *scratch)
1191 {
1192         return reftable_record_vtable(rec)->decode(reftable_record_data(rec),
1193                                                    key, extra, src, hash_size,
1194                                                    scratch);
1195 }
1196
1197 void reftable_record_release(struct reftable_record *rec)
1198 {
1199         reftable_record_vtable(rec)->release(reftable_record_data(rec));
1200 }
1201
1202 int reftable_record_is_deletion(struct reftable_record *rec)
1203 {
1204         return reftable_record_vtable(rec)->is_deletion(
1205                 reftable_record_data(rec));
1206 }
1207
1208 int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b)
1209 {
1210         if (a->type != b->type)
1211                 BUG("cannot compare reftable records of different type");
1212         return reftable_record_vtable(a)->cmp(
1213                 reftable_record_data(a), reftable_record_data(b));
1214 }
1215
1216 int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)
1217 {
1218         if (a->type != b->type)
1219                 return 0;
1220         return reftable_record_vtable(a)->equal(
1221                 reftable_record_data(a), reftable_record_data(b), hash_size);
1222 }
1223
1224 static int hash_equal(const unsigned char *a, const unsigned char *b, int hash_size)
1225 {
1226         if (a && b)
1227                 return !memcmp(a, b, hash_size);
1228
1229         return a == b;
1230 }
1231
1232 int reftable_ref_record_equal(const struct reftable_ref_record *a,
1233                               const struct reftable_ref_record *b, int hash_size)
1234 {
1235         assert(hash_size > 0);
1236         if (!null_streq(a->refname, b->refname))
1237                 return 0;
1238
1239         if (a->update_index != b->update_index ||
1240             a->value_type != b->value_type)
1241                 return 0;
1242
1243         switch (a->value_type) {
1244         case REFTABLE_REF_SYMREF:
1245                 return !strcmp(a->value.symref, b->value.symref);
1246         case REFTABLE_REF_VAL2:
1247                 return hash_equal(a->value.val2.value, b->value.val2.value,
1248                                   hash_size) &&
1249                        hash_equal(a->value.val2.target_value,
1250                                   b->value.val2.target_value, hash_size);
1251         case REFTABLE_REF_VAL1:
1252                 return hash_equal(a->value.val1, b->value.val1, hash_size);
1253         case REFTABLE_REF_DELETION:
1254                 return 1;
1255         default:
1256                 abort();
1257         }
1258 }
1259
1260 int reftable_ref_record_compare_name(const void *a, const void *b)
1261 {
1262         return strcmp(((struct reftable_ref_record *)a)->refname,
1263                       ((struct reftable_ref_record *)b)->refname);
1264 }
1265
1266 int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref)
1267 {
1268         return ref->value_type == REFTABLE_REF_DELETION;
1269 }
1270
1271 int reftable_log_record_compare_key(const void *a, const void *b)
1272 {
1273         const struct reftable_log_record *la = a;
1274         const struct reftable_log_record *lb = b;
1275
1276         int cmp = strcmp(la->refname, lb->refname);
1277         if (cmp)
1278                 return cmp;
1279         if (la->update_index > lb->update_index)
1280                 return -1;
1281         return (la->update_index < lb->update_index) ? 1 : 0;
1282 }
1283
1284 int reftable_log_record_is_deletion(const struct reftable_log_record *log)
1285 {
1286         return (log->value_type == REFTABLE_LOG_DELETION);
1287 }
1288
1289 static void *reftable_record_data(struct reftable_record *rec)
1290 {
1291         switch (rec->type) {
1292         case BLOCK_TYPE_REF:
1293                 return &rec->u.ref;
1294         case BLOCK_TYPE_LOG:
1295                 return &rec->u.log;
1296         case BLOCK_TYPE_INDEX:
1297                 return &rec->u.idx;
1298         case BLOCK_TYPE_OBJ:
1299                 return &rec->u.obj;
1300         }
1301         abort();
1302 }
1303
1304 static struct reftable_record_vtable *
1305 reftable_record_vtable(struct reftable_record *rec)
1306 {
1307         switch (rec->type) {
1308         case BLOCK_TYPE_REF:
1309                 return &reftable_ref_record_vtable;
1310         case BLOCK_TYPE_LOG:
1311                 return &reftable_log_record_vtable;
1312         case BLOCK_TYPE_INDEX:
1313                 return &reftable_index_record_vtable;
1314         case BLOCK_TYPE_OBJ:
1315                 return &reftable_obj_record_vtable;
1316         }
1317         abort();
1318 }
1319
1320 void reftable_record_init(struct reftable_record *rec, uint8_t typ)
1321 {
1322         memset(rec, 0, sizeof(*rec));
1323         rec->type = typ;
1324
1325         switch (typ) {
1326         case BLOCK_TYPE_REF:
1327         case BLOCK_TYPE_LOG:
1328         case BLOCK_TYPE_OBJ:
1329                 return;
1330         case BLOCK_TYPE_INDEX:
1331                 strbuf_init(&rec->u.idx.last_key, 0);
1332                 return;
1333         default:
1334                 BUG("unhandled record type");
1335         }
1336 }
1337
1338 void reftable_record_print(struct reftable_record *rec, int hash_size)
1339 {
1340         printf("'%c': ", rec->type);
1341         reftable_record_vtable(rec)->print(reftable_record_data(rec), hash_size);
1342 }