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