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
 434 static int reftable_ref_record_equal_void(const void *a,
 435                                           const void *b, int hash_size)
 436 {
 437         struct reftable_ref_record *ra = (struct reftable_ref_record *) a;
 438         struct reftable_ref_record *rb = (struct reftable_ref_record *) b;
 439         return reftable_ref_record_equal(ra, rb, hash_size);
 440 }
 441
 442 static struct reftable_record_vtable reftable_ref_record_vtable = {
 443         .key = &reftable_ref_record_key,
 444         .type = BLOCK_TYPE_REF,
 445         .copy_from = &reftable_ref_record_copy_from,
 446         .val_type = &reftable_ref_record_val_type,
 447         .encode = &reftable_ref_record_encode,
 448         .decode = &reftable_ref_record_decode,
 449         .release = &reftable_ref_record_release_void,
 450         .is_deletion = &reftable_ref_record_is_deletion_void,
 451         .equal = &reftable_ref_record_equal_void,
 452 };
 453
 454 static void reftable_obj_record_key(const void *r, struct strbuf *dest)
 455 {
 456         const struct reftable_obj_record *rec =
 457                 (const struct reftable_obj_record *)r;
 458         strbuf_reset(dest);
 459         strbuf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
 460 }
 461
 462 static void reftable_obj_record_release(void *rec)
 463 {
 464         struct reftable_obj_record *obj = rec;
 465         FREE_AND_NULL(obj->hash_prefix);
 466         FREE_AND_NULL(obj->offsets);
 467         memset(obj, 0, sizeof(struct reftable_obj_record));
 468 }
 469
 470 static void reftable_obj_record_copy_from(void *rec, const void *src_rec,
 471                                           int hash_size)
 472 {
 473         struct reftable_obj_record *obj = rec;
 474         const struct reftable_obj_record *src =
 475                 (const struct reftable_obj_record *)src_rec;
 476
 477         reftable_obj_record_release(obj);
 478         *obj = *src;
 479         obj->hash_prefix = reftable_malloc(obj->hash_prefix_len);
 480         memcpy(obj->hash_prefix, src->hash_prefix, obj->hash_prefix_len);
 481
 482         obj->offsets = reftable_malloc(obj->offset_len * sizeof(uint64_t));
 483         COPY_ARRAY(obj->offsets, src->offsets, obj->offset_len);
 484 }
 485
 486 static uint8_t reftable_obj_record_val_type(const void *rec)
 487 {
 488         const struct reftable_obj_record *r = rec;
 489         if (r->offset_len > 0 && r->offset_len < 8)
 490                 return r->offset_len;
 491         return 0;
 492 }
 493
 494 static int reftable_obj_record_encode(const void *rec, struct string_view s,
 495                                       int hash_size)
 496 {
 497         const struct reftable_obj_record *r = rec;
 498         struct string_view start = s;
 499         int i = 0;
 500         int n = 0;
 501         uint64_t last = 0;
 502         if (r->offset_len == 0 || r->offset_len >= 8) {
 503                 n = put_var_int(&s, r->offset_len);
 504                 if (n < 0) {
 505                         return -1;
 506                 }
 507                 string_view_consume(&s, n);
 508         }
 509         if (r->offset_len == 0)
 510                 return start.len - s.len;
 511         n = put_var_int(&s, r->offsets[0]);
 512         if (n < 0)
 513                 return -1;
 514         string_view_consume(&s, n);
 515
 516         last = r->offsets[0];
 517         for (i = 1; i < r->offset_len; i++) {
 518                 int n = put_var_int(&s, r->offsets[i] - last);
 519                 if (n < 0) {
 520                         return -1;
 521                 }
 522                 string_view_consume(&s, n);
 523                 last = r->offsets[i];
 524         }
 525         return start.len - s.len;
 526 }
 527
 528 static int reftable_obj_record_decode(void *rec, struct strbuf key,
 529                                       uint8_t val_type, struct string_view in,
 530                                       int hash_size)
 531 {
 532         struct string_view start = in;
 533         struct reftable_obj_record *r = rec;
 534         uint64_t count = val_type;
 535         int n = 0;
 536         uint64_t last;
 537         int j;
 538         r->hash_prefix = reftable_malloc(key.len);
 539         memcpy(r->hash_prefix, key.buf, key.len);
 540         r->hash_prefix_len = key.len;
 541
 542         if (val_type == 0) {
 543                 n = get_var_int(&count, &in);
 544                 if (n < 0) {
 545                         return n;
 546                 }
 547
 548                 string_view_consume(&in, n);
 549         }
 550
 551         r->offsets = NULL;
 552         r->offset_len = 0;
 553         if (count == 0)
 554                 return start.len - in.len;
 555
 556         r->offsets = reftable_malloc(count * sizeof(uint64_t));
 557         r->offset_len = count;
 558
 559         n = get_var_int(&r->offsets[0], &in);
 560         if (n < 0)
 561                 return n;
 562         string_view_consume(&in, n);
 563
 564         last = r->offsets[0];
 565         j = 1;
 566         while (j < count) {
 567                 uint64_t delta = 0;
 568                 int n = get_var_int(&delta, &in);
 569                 if (n < 0) {
 570                         return n;
 571                 }
 572                 string_view_consume(&in, n);
 573
 574                 last = r->offsets[j] = (delta + last);
 575                 j++;
 576         }
 577         return start.len - in.len;
 578 }
 579
 580 static int not_a_deletion(const void *p)
 581 {
 582         return 0;
 583 }
 584
 585 static int reftable_obj_record_equal_void(const void *a, const void *b, int hash_size)
 586 {
 587         struct reftable_obj_record *ra = (struct reftable_obj_record *) a;
 588         struct reftable_obj_record *rb = (struct reftable_obj_record *) b;
 589
 590         if (ra->hash_prefix_len != rb->hash_prefix_len
 591             || ra->offset_len != rb->offset_len)
 592                 return 0;
 593
 594         if (ra->hash_prefix_len &&
 595             memcmp(ra->hash_prefix, rb->hash_prefix, ra->hash_prefix_len))
 596                 return 0;
 597         if (ra->offset_len &&
 598             memcmp(ra->offsets, rb->offsets, ra->offset_len * sizeof(uint64_t)))
 599                 return 0;
 600
 601         return 1;
 602 }
 603
 604 static struct reftable_record_vtable reftable_obj_record_vtable = {
 605         .key = &reftable_obj_record_key,
 606         .type = BLOCK_TYPE_OBJ,
 607         .copy_from = &reftable_obj_record_copy_from,
 608         .val_type = &reftable_obj_record_val_type,
 609         .encode = &reftable_obj_record_encode,
 610         .decode = &reftable_obj_record_decode,
 611         .release = &reftable_obj_record_release,
 612         .is_deletion = &not_a_deletion,
 613         .equal = &reftable_obj_record_equal_void,
 614 };
 615
 616 void reftable_log_record_print(struct reftable_log_record *log,
 617                                uint32_t hash_id)
 618 {
 619         char hex[GIT_MAX_HEXSZ + 1] = { 0 };
 620
 621         switch (log->value_type) {
 622         case REFTABLE_LOG_DELETION:
 623                 printf("log{%s(%" PRIu64 ") delete", log->refname,
 624                        log->update_index);
 625                 break;
 626         case REFTABLE_LOG_UPDATE:
 627                 printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n",
 628                        log->refname, log->update_index, log->value.update.name,
 629                        log->value.update.email, log->value.update.time,
 630                        log->value.update.tz_offset);
 631                 hex_format(hex, log->value.update.old_hash, hash_size(hash_id));
 632                 printf("%s => ", hex);
 633                 hex_format(hex, log->value.update.new_hash, hash_size(hash_id));
 634                 printf("%s\n\n%s\n}\n", hex, log->value.update.message);
 635                 break;
 636         }
 637 }
 638
 639 static void reftable_log_record_key(const void *r, struct strbuf *dest)
 640 {
 641         const struct reftable_log_record *rec =
 642                 (const struct reftable_log_record *)r;
 643         int len = strlen(rec->refname);
 644         uint8_t i64[8];
 645         uint64_t ts = 0;
 646         strbuf_reset(dest);
 647         strbuf_add(dest, (uint8_t *)rec->refname, len + 1);
 648
 649         ts = (~ts) - rec->update_index;
 650         put_be64(&i64[0], ts);
 651         strbuf_add(dest, i64, sizeof(i64));
 652 }
 653
 654 static void reftable_log_record_copy_from(void *rec, const void *src_rec,
 655                                           int hash_size)
 656 {
 657         struct reftable_log_record *dst = rec;
 658         const struct reftable_log_record *src =
 659                 (const struct reftable_log_record *)src_rec;
 660
 661         reftable_log_record_release(dst);
 662         *dst = *src;
 663         if (dst->refname) {
 664                 dst->refname = xstrdup(dst->refname);
 665         }
 666         switch (dst->value_type) {
 667         case REFTABLE_LOG_DELETION:
 668                 break;
 669         case REFTABLE_LOG_UPDATE:
 670                 if (dst->value.update.email) {
 671                         dst->value.update.email =
 672                                 xstrdup(dst->value.update.email);
 673                 }
 674                 if (dst->value.update.name) {
 675                         dst->value.update.name =
 676                                 xstrdup(dst->value.update.name);
 677                 }
 678                 if (dst->value.update.message) {
 679                         dst->value.update.message =
 680                                 xstrdup(dst->value.update.message);
 681                 }
 682
 683                 if (dst->value.update.new_hash) {
 684                         dst->value.update.new_hash = reftable_malloc(hash_size);
 685                         memcpy(dst->value.update.new_hash,
 686                                src->value.update.new_hash, hash_size);
 687                 }
 688                 if (dst->value.update.old_hash) {
 689                         dst->value.update.old_hash = reftable_malloc(hash_size);
 690                         memcpy(dst->value.update.old_hash,
 691                                src->value.update.old_hash, hash_size);
 692                 }
 693                 break;
 694         }
 695 }
 696
 697 static void reftable_log_record_release_void(void *rec)
 698 {
 699         struct reftable_log_record *r = rec;
 700         reftable_log_record_release(r);
 701 }
 702
 703 void reftable_log_record_release(struct reftable_log_record *r)
 704 {
 705         reftable_free(r->refname);
 706         switch (r->value_type) {
 707         case REFTABLE_LOG_DELETION:
 708                 break;
 709         case REFTABLE_LOG_UPDATE:
 710                 reftable_free(r->value.update.new_hash);
 711                 reftable_free(r->value.update.old_hash);
 712                 reftable_free(r->value.update.name);
 713                 reftable_free(r->value.update.email);
 714                 reftable_free(r->value.update.message);
 715                 break;
 716         }
 717         memset(r, 0, sizeof(struct reftable_log_record));
 718 }
 719
 720 static uint8_t reftable_log_record_val_type(const void *rec)
 721 {
 722         const struct reftable_log_record *log =
 723                 (const struct reftable_log_record *)rec;
 724
 725         return reftable_log_record_is_deletion(log) ? 0 : 1;
 726 }
 727
 728 static uint8_t zero[GIT_SHA256_RAWSZ] = { 0 };
 729
 730 static int reftable_log_record_encode(const void *rec, struct string_view s,
 731                                       int hash_size)
 732 {
 733         const struct reftable_log_record *r = rec;
 734         struct string_view start = s;
 735         int n = 0;
 736         uint8_t *oldh = NULL;
 737         uint8_t *newh = NULL;
 738         if (reftable_log_record_is_deletion(r))
 739                 return 0;
 740
 741         oldh = r->value.update.old_hash;
 742         newh = r->value.update.new_hash;
 743         if (!oldh) {
 744                 oldh = zero;
 745         }
 746         if (!newh) {
 747                 newh = zero;
 748         }
 749
 750         if (s.len < 2 * hash_size)
 751                 return -1;
 752
 753         memcpy(s.buf, oldh, hash_size);
 754         memcpy(s.buf + hash_size, newh, hash_size);
 755         string_view_consume(&s, 2 * hash_size);
 756
 757         n = encode_string(r->value.update.name ? r->value.update.name : "", s);
 758         if (n < 0)
 759                 return -1;
 760         string_view_consume(&s, n);
 761
 762         n = encode_string(r->value.update.email ? r->value.update.email : "",
 763                           s);
 764         if (n < 0)
 765                 return -1;
 766         string_view_consume(&s, n);
 767
 768         n = put_var_int(&s, r->value.update.time);
 769         if (n < 0)
 770                 return -1;
 771         string_view_consume(&s, n);
 772
 773         if (s.len < 2)
 774                 return -1;
 775
 776         put_be16(s.buf, r->value.update.tz_offset);
 777         string_view_consume(&s, 2);
 778
 779         n = encode_string(
 780                 r->value.update.message ? r->value.update.message : "", s);
 781         if (n < 0)
 782                 return -1;
 783         string_view_consume(&s, n);
 784
 785         return start.len - s.len;
 786 }
 787
 788 static int reftable_log_record_decode(void *rec, struct strbuf key,
 789                                       uint8_t val_type, struct string_view in,
 790                                       int hash_size)
 791 {
 792         struct string_view start = in;
 793         struct reftable_log_record *r = rec;
 794         uint64_t max = 0;
 795         uint64_t ts = 0;
 796         struct strbuf dest = STRBUF_INIT;
 797         int n;
 798
 799         if (key.len <= 9 || key.buf[key.len - 9] != 0)
 800                 return REFTABLE_FORMAT_ERROR;
 801
 802         r->refname = reftable_realloc(r->refname, key.len - 8);
 803         memcpy(r->refname, key.buf, key.len - 8);
 804         ts = get_be64(key.buf + key.len - 8);
 805
 806         r->update_index = (~max) - ts;
 807
 808         if (val_type != r->value_type) {
 809                 switch (r->value_type) {
 810                 case REFTABLE_LOG_UPDATE:
 811                         FREE_AND_NULL(r->value.update.old_hash);
 812                         FREE_AND_NULL(r->value.update.new_hash);
 813                         FREE_AND_NULL(r->value.update.message);
 814                         FREE_AND_NULL(r->value.update.email);
 815                         FREE_AND_NULL(r->value.update.name);
 816                         break;
 817                 case REFTABLE_LOG_DELETION:
 818                         break;
 819                 }
 820         }
 821
 822         r->value_type = val_type;
 823         if (val_type == REFTABLE_LOG_DELETION)
 824                 return 0;
 825
 826         if (in.len < 2 * hash_size)
 827                 return REFTABLE_FORMAT_ERROR;
 828
 829         r->value.update.old_hash =
 830                 reftable_realloc(r->value.update.old_hash, hash_size);
 831         r->value.update.new_hash =
 832                 reftable_realloc(r->value.update.new_hash, hash_size);
 833
 834         memcpy(r->value.update.old_hash, in.buf, hash_size);
 835         memcpy(r->value.update.new_hash, in.buf + hash_size, hash_size);
 836
 837         string_view_consume(&in, 2 * hash_size);
 838
 839         n = decode_string(&dest, in);
 840         if (n < 0)
 841                 goto done;
 842         string_view_consume(&in, n);
 843
 844         r->value.update.name =
 845                 reftable_realloc(r->value.update.name, dest.len + 1);
 846         memcpy(r->value.update.name, dest.buf, dest.len);
 847         r->value.update.name[dest.len] = 0;
 848
 849         strbuf_reset(&dest);
 850         n = decode_string(&dest, in);
 851         if (n < 0)
 852                 goto done;
 853         string_view_consume(&in, n);
 854
 855         r->value.update.email =
 856                 reftable_realloc(r->value.update.email, dest.len + 1);
 857         memcpy(r->value.update.email, dest.buf, dest.len);
 858         r->value.update.email[dest.len] = 0;
 859
 860         ts = 0;
 861         n = get_var_int(&ts, &in);
 862         if (n < 0)
 863                 goto done;
 864         string_view_consume(&in, n);
 865         r->value.update.time = ts;
 866         if (in.len < 2)
 867                 goto done;
 868
 869         r->value.update.tz_offset = get_be16(in.buf);
 870         string_view_consume(&in, 2);
 871
 872         strbuf_reset(&dest);
 873         n = decode_string(&dest, in);
 874         if (n < 0)
 875                 goto done;
 876         string_view_consume(&in, n);
 877
 878         r->value.update.message =
 879                 reftable_realloc(r->value.update.message, dest.len + 1);
 880         memcpy(r->value.update.message, dest.buf, dest.len);
 881         r->value.update.message[dest.len] = 0;
 882
 883         strbuf_release(&dest);
 884         return start.len - in.len;
 885
 886 done:
 887         strbuf_release(&dest);
 888         return REFTABLE_FORMAT_ERROR;
 889 }
 890
 891 static int null_streq(char *a, char *b)
 892 {
 893         char *empty = "";
 894         if (!a)
 895                 a = empty;
 896
 897         if (!b)
 898                 b = empty;
 899
 900         return 0 == strcmp(a, b);
 901 }
 902
 903 static int zero_hash_eq(uint8_t *a, uint8_t *b, int sz)
 904 {
 905         if (!a)
 906                 a = zero;
 907
 908         if (!b)
 909                 b = zero;
 910
 911         return !memcmp(a, b, sz);
 912 }
 913
 914 static int reftable_log_record_equal_void(const void *a,
 915                                           const void *b, int hash_size)
 916 {
 917         return reftable_log_record_equal((struct reftable_log_record *) a,
 918                                          (struct reftable_log_record *) b,
 919                                          hash_size);
 920 }
 921
 922 int reftable_log_record_equal(const struct reftable_log_record *a,
 923                               const struct reftable_log_record *b, int hash_size)
 924 {
 925         if (!(null_streq(a->refname, b->refname) &&
 926               a->update_index == b->update_index &&
 927               a->value_type == b->value_type))
 928                 return 0;
 929
 930         switch (a->value_type) {
 931         case REFTABLE_LOG_DELETION:
 932                 return 1;
 933         case REFTABLE_LOG_UPDATE:
 934                 return null_streq(a->value.update.name, b->value.update.name) &&
 935                        a->value.update.time == b->value.update.time &&
 936                        a->value.update.tz_offset == b->value.update.tz_offset &&
 937                        null_streq(a->value.update.email,
 938                                   b->value.update.email) &&
 939                        null_streq(a->value.update.message,
 940                                   b->value.update.message) &&
 941                        zero_hash_eq(a->value.update.old_hash,
 942                                     b->value.update.old_hash, hash_size) &&
 943                        zero_hash_eq(a->value.update.new_hash,
 944                                     b->value.update.new_hash, hash_size);
 945         }
 946
 947         abort();
 948 }
 949
 950 static int reftable_log_record_is_deletion_void(const void *p)
 951 {
 952         return reftable_log_record_is_deletion(
 953                 (const struct reftable_log_record *)p);
 954 }
 955
 956 static struct reftable_record_vtable reftable_log_record_vtable = {
 957         .key = &reftable_log_record_key,
 958         .type = BLOCK_TYPE_LOG,
 959         .copy_from = &reftable_log_record_copy_from,
 960         .val_type = &reftable_log_record_val_type,
 961         .encode = &reftable_log_record_encode,
 962         .decode = &reftable_log_record_decode,
 963         .release = &reftable_log_record_release_void,
 964         .is_deletion = &reftable_log_record_is_deletion_void,
 965         .equal = &reftable_log_record_equal_void
 966 };
 967
 968 struct reftable_record reftable_new_record(uint8_t typ)
 969 {
 970         struct reftable_record rec = { NULL };
 971         switch (typ) {
 972         case BLOCK_TYPE_REF: {
 973                 struct reftable_ref_record *r =
 974                         reftable_calloc(sizeof(struct reftable_ref_record));
 975                 reftable_record_from_ref(&rec, r);
 976                 return rec;
 977         }
 978
 979         case BLOCK_TYPE_OBJ: {
 980                 struct reftable_obj_record *r =
 981                         reftable_calloc(sizeof(struct reftable_obj_record));
 982                 reftable_record_from_obj(&rec, r);
 983                 return rec;
 984         }
 985         case BLOCK_TYPE_LOG: {
 986                 struct reftable_log_record *r =
 987                         reftable_calloc(sizeof(struct reftable_log_record));
 988                 reftable_record_from_log(&rec, r);
 989                 return rec;
 990         }
 991         case BLOCK_TYPE_INDEX: {
 992                 struct reftable_index_record empty = { .last_key =
 993                                                                STRBUF_INIT };
 994                 struct reftable_index_record *r =
 995                         reftable_calloc(sizeof(struct reftable_index_record));
 996                 *r = empty;
 997                 reftable_record_from_index(&rec, r);
 998                 return rec;
 999         }
1000         }
1001         abort();
1002         return rec;
1003 }
1004
1005 /* clear out the record, yielding the reftable_record data that was
1006  * encapsulated. */
1007 static void *reftable_record_yield(struct reftable_record *rec)
1008 {
1009         void *p = rec->data;
1010         rec->data = NULL;
1011         return p;
1012 }
1013
1014 void reftable_record_destroy(struct reftable_record *rec)
1015 {
1016         reftable_record_release(rec);
1017         reftable_free(reftable_record_yield(rec));
1018 }
1019
1020 static void reftable_index_record_key(const void *r, struct strbuf *dest)
1021 {
1022         const struct reftable_index_record *rec = r;
1023         strbuf_reset(dest);
1024         strbuf_addbuf(dest, &rec->last_key);
1025 }
1026
1027 static void reftable_index_record_copy_from(void *rec, const void *src_rec,
1028                                             int hash_size)
1029 {
1030         struct reftable_index_record *dst = rec;
1031         const struct reftable_index_record *src = src_rec;
1032
1033         strbuf_reset(&dst->last_key);
1034         strbuf_addbuf(&dst->last_key, &src->last_key);
1035         dst->offset = src->offset;
1036 }
1037
1038 static void reftable_index_record_release(void *rec)
1039 {
1040         struct reftable_index_record *idx = rec;
1041         strbuf_release(&idx->last_key);
1042 }
1043
1044 static uint8_t reftable_index_record_val_type(const void *rec)
1045 {
1046         return 0;
1047 }
1048
1049 static int reftable_index_record_encode(const void *rec, struct string_view out,
1050                                         int hash_size)
1051 {
1052         const struct reftable_index_record *r =
1053                 (const struct reftable_index_record *)rec;
1054         struct string_view start = out;
1055
1056         int n = put_var_int(&out, r->offset);
1057         if (n < 0)
1058                 return n;
1059
1060         string_view_consume(&out, n);
1061
1062         return start.len - out.len;
1063 }
1064
1065 static int reftable_index_record_decode(void *rec, struct strbuf key,
1066                                         uint8_t val_type, struct string_view in,
1067                                         int hash_size)
1068 {
1069         struct string_view start = in;
1070         struct reftable_index_record *r = rec;
1071         int n = 0;
1072
1073         strbuf_reset(&r->last_key);
1074         strbuf_addbuf(&r->last_key, &key);
1075
1076         n = get_var_int(&r->offset, &in);
1077         if (n < 0)
1078                 return n;
1079
1080         string_view_consume(&in, n);
1081         return start.len - in.len;
1082 }
1083
1084 static int reftable_index_record_equal(const void *a, const void *b, int hash_size)
1085 {
1086         struct reftable_index_record *ia = (struct reftable_index_record *) a;
1087         struct reftable_index_record *ib = (struct reftable_index_record *) b;
1088
1089         return ia->offset == ib->offset && !strbuf_cmp(&ia->last_key, &ib->last_key);
1090 }
1091
1092 static struct reftable_record_vtable reftable_index_record_vtable = {
1093         .key = &reftable_index_record_key,
1094         .type = BLOCK_TYPE_INDEX,
1095         .copy_from = &reftable_index_record_copy_from,
1096         .val_type = &reftable_index_record_val_type,
1097         .encode = &reftable_index_record_encode,
1098         .decode = &reftable_index_record_decode,
1099         .release = &reftable_index_record_release,
1100         .is_deletion = &not_a_deletion,
1101         .equal = &reftable_index_record_equal,
1102 };
1103
1104 void reftable_record_key(struct reftable_record *rec, struct strbuf *dest)
1105 {
1106         rec->ops->key(rec->data, dest);
1107 }
1108
1109 uint8_t reftable_record_type(struct reftable_record *rec)
1110 {
1111         return rec->ops->type;
1112 }
1113
1114 int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
1115                            int hash_size)
1116 {
1117         return rec->ops->encode(rec->data, dest, hash_size);
1118 }
1119
1120 void reftable_record_copy_from(struct reftable_record *rec,
1121                                struct reftable_record *src, int hash_size)
1122 {
1123         assert(src->ops->type == rec->ops->type);
1124
1125         rec->ops->copy_from(rec->data, src->data, hash_size);
1126 }
1127
1128 uint8_t reftable_record_val_type(struct reftable_record *rec)
1129 {
1130         return rec->ops->val_type(rec->data);
1131 }
1132
1133 int reftable_record_decode(struct reftable_record *rec, struct strbuf key,
1134                            uint8_t extra, struct string_view src, int hash_size)
1135 {
1136         return rec->ops->decode(rec->data, key, extra, src, hash_size);
1137 }
1138
1139 void reftable_record_release(struct reftable_record *rec)
1140 {
1141         rec->ops->release(rec->data);
1142 }
1143
1144 int reftable_record_is_deletion(struct reftable_record *rec)
1145 {
1146         return rec->ops->is_deletion(rec->data);
1147 }
1148
1149 int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size)
1150 {
1151         if (a->ops != b->ops)
1152                 return 0;
1153         return a->ops->equal(a->data, b->data, hash_size);
1154 }
1155
1156 void reftable_record_from_ref(struct reftable_record *rec,
1157                               struct reftable_ref_record *ref_rec)
1158 {
1159         assert(!rec->ops);
1160         rec->data = ref_rec;
1161         rec->ops = &reftable_ref_record_vtable;
1162 }
1163
1164 void reftable_record_from_obj(struct reftable_record *rec,
1165                               struct reftable_obj_record *obj_rec)
1166 {
1167         assert(!rec->ops);
1168         rec->data = obj_rec;
1169         rec->ops = &reftable_obj_record_vtable;
1170 }
1171
1172 void reftable_record_from_index(struct reftable_record *rec,
1173                                 struct reftable_index_record *index_rec)
1174 {
1175         assert(!rec->ops);
1176         rec->data = index_rec;
1177         rec->ops = &reftable_index_record_vtable;
1178 }
1179
1180 void reftable_record_from_log(struct reftable_record *rec,
1181                               struct reftable_log_record *log_rec)
1182 {
1183         assert(!rec->ops);
1184         rec->data = log_rec;
1185         rec->ops = &reftable_log_record_vtable;
1186 }
1187
1188 struct reftable_ref_record *reftable_record_as_ref(struct reftable_record *rec)
1189 {
1190         assert(reftable_record_type(rec) == BLOCK_TYPE_REF);
1191         return rec->data;
1192 }
1193
1194 struct reftable_log_record *reftable_record_as_log(struct reftable_record *rec)
1195 {
1196         assert(reftable_record_type(rec) == BLOCK_TYPE_LOG);
1197         return rec->data;
1198 }
1199
1200 static int hash_equal(uint8_t *a, uint8_t *b, int hash_size)
1201 {
1202         if (a && b)
1203                 return !memcmp(a, b, hash_size);
1204
1205         return a == b;
1206 }
1207
1208 int reftable_ref_record_equal(const struct reftable_ref_record *a,
1209                               const struct reftable_ref_record *b, int hash_size)
1210 {
1211         assert(hash_size > 0);
1212         if (!null_streq(a->refname, b->refname))
1213                 return 0;
1214
1215         if (a->update_index != b->update_index ||
1216             a->value_type != b->value_type)
1217                 return 0;
1218
1219         switch (a->value_type) {
1220         case REFTABLE_REF_SYMREF:
1221                 return !strcmp(a->value.symref, b->value.symref);
1222         case REFTABLE_REF_VAL2:
1223                 return hash_equal(a->value.val2.value, b->value.val2.value,
1224                                   hash_size) &&
1225                        hash_equal(a->value.val2.target_value,
1226                                   b->value.val2.target_value, hash_size);
1227         case REFTABLE_REF_VAL1:
1228                 return hash_equal(a->value.val1, b->value.val1, hash_size);
1229         case REFTABLE_REF_DELETION:
1230                 return 1;
1231         default:
1232                 abort();
1233         }
1234 }
1235
1236 int reftable_ref_record_compare_name(const void *a, const void *b)
1237 {
1238         return strcmp(((struct reftable_ref_record *)a)->refname,
1239                       ((struct reftable_ref_record *)b)->refname);
1240 }
1241
1242 int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref)
1243 {
1244         return ref->value_type == REFTABLE_REF_DELETION;
1245 }
1246
1247 int reftable_log_record_compare_key(const void *a, const void *b)
1248 {
1249         const struct reftable_log_record *la = a;
1250         const struct reftable_log_record *lb = b;
1251
1252         int cmp = strcmp(la->refname, lb->refname);
1253         if (cmp)
1254                 return cmp;
1255         if (la->update_index > lb->update_index)
1256                 return -1;
1257         return (la->update_index < lb->update_index) ? 1 : 0;
1258 }
1259
1260 int reftable_log_record_is_deletion(const struct reftable_log_record *log)
1261 {
1262         return (log->value_type == REFTABLE_LOG_DELETION);
1263 }
1264
1265 void string_view_consume(struct string_view *s, int n)
1266 {
1267         s->buf += n;
1268         s->len -= n;
1269 }