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