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