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