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