refs/ref-cache.c

   1 #include "../cache.h"
   2 #include "../refs.h"
   3 #include "refs-internal.h"
   4 #include "ref-cache.h"
   5 #include "../iterator.h"
   6
   7 void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
   8 {
   9         ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
  10         dir->entries[dir->nr++] = entry;
  11         /* optimize for the case that entries are added in order */
  12         if (dir->nr == 1 ||
  13             (dir->nr == dir->sorted + 1 &&
  14              strcmp(dir->entries[dir->nr - 2]->name,
  15                     dir->entries[dir->nr - 1]->name) < 0))
  16                 dir->sorted = dir->nr;
  17 }
  18
  19 struct ref_dir *get_ref_dir(struct ref_entry *entry)
  20 {
  21         struct ref_dir *dir;
  22         assert(entry->flag & REF_DIR);
  23         dir = &entry->u.subdir;
  24         if (entry->flag & REF_INCOMPLETE) {
  25                 if (!dir->cache->fill_ref_dir)
  26                         die("BUG: incomplete ref_store without fill_ref_dir function");
  27
  28                 dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);
  29                 entry->flag &= ~REF_INCOMPLETE;
  30         }
  31         return dir;
  32 }
  33
  34 struct ref_entry *create_ref_entry(const char *refname,
  35                                    const struct object_id *oid, int flag)
  36 {
  37         struct ref_entry *ref;
  38
  39         FLEX_ALLOC_STR(ref, name, refname);
  40         oidcpy(&ref->u.value.oid, oid);
  41         oidclr(&ref->u.value.peeled);
  42         ref->flag = flag;
  43         return ref;
  44 }
  45
  46 struct ref_cache *create_ref_cache(struct ref_store *refs,
  47                                    fill_ref_dir_fn *fill_ref_dir)
  48 {
  49         struct ref_cache *ret = xcalloc(1, sizeof(*ret));
  50
  51         ret->ref_store = refs;
  52         ret->fill_ref_dir = fill_ref_dir;
  53         ret->root = create_dir_entry(ret, "", 0, 1);
  54         return ret;
  55 }
  56
  57 static void clear_ref_dir(struct ref_dir *dir);
  58
  59 static void free_ref_entry(struct ref_entry *entry)
  60 {
  61         if (entry->flag & REF_DIR) {
  62                 /*
  63                  * Do not use get_ref_dir() here, as that might
  64                  * trigger the reading of loose refs.
  65                  */
  66                 clear_ref_dir(&entry->u.subdir);
  67         }
  68         free(entry);
  69 }
  70
  71 void free_ref_cache(struct ref_cache *cache)
  72 {
  73         free_ref_entry(cache->root);
  74         free(cache);
  75 }
  76
  77 /*
  78  * Clear and free all entries in dir, recursively.
  79  */
  80 static void clear_ref_dir(struct ref_dir *dir)
  81 {
  82         int i;
  83         for (i = 0; i < dir->nr; i++)
  84                 free_ref_entry(dir->entries[i]);
  85         FREE_AND_NULL(dir->entries);
  86         dir->sorted = dir->nr = dir->alloc = 0;
  87 }
  88
  89 struct ref_entry *create_dir_entry(struct ref_cache *cache,
  90                                    const char *dirname, size_t len,
  91                                    int incomplete)
  92 {
  93         struct ref_entry *direntry;
  94
  95         FLEX_ALLOC_MEM(direntry, name, dirname, len);
  96         direntry->u.subdir.cache = cache;
  97         direntry->flag = REF_DIR | (incomplete ? REF_INCOMPLETE : 0);
  98         return direntry;
  99 }
 100
 101 static int ref_entry_cmp(const void *a, const void *b)
 102 {
 103         struct ref_entry *one = *(struct ref_entry **)a;
 104         struct ref_entry *two = *(struct ref_entry **)b;
 105         return strcmp(one->name, two->name);
 106 }
 107
 108 static void sort_ref_dir(struct ref_dir *dir);
 109
 110 struct string_slice {
 111         size_t len;
 112         const char *str;
 113 };
 114
 115 static int ref_entry_cmp_sslice(const void *key_, const void *ent_)
 116 {
 117         const struct string_slice *key = key_;
 118         const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;
 119         int cmp = strncmp(key->str, ent->name, key->len);
 120         if (cmp)
 121                 return cmp;
 122         return '\0' - (unsigned char)ent->name[key->len];
 123 }
 124
 125 int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)
 126 {
 127         struct ref_entry **r;
 128         struct string_slice key;
 129
 130         if (refname == NULL || !dir->nr)
 131                 return -1;
 132
 133         sort_ref_dir(dir);
 134         key.len = len;
 135         key.str = refname;
 136         r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),
 137                     ref_entry_cmp_sslice);
 138
 139         if (r == NULL)
 140                 return -1;
 141
 142         return r - dir->entries;
 143 }
 144
 145 /*
 146  * Search for a directory entry directly within dir (without
 147  * recursing).  Sort dir if necessary.  subdirname must be a directory
 148  * name (i.e., end in '/').  If mkdir is set, then create the
 149  * directory if it is missing; otherwise, return NULL if the desired
 150  * directory cannot be found.  dir must already be complete.
 151  */
 152 static struct ref_dir *search_for_subdir(struct ref_dir *dir,
 153                                          const char *subdirname, size_t len,
 154                                          int mkdir)
 155 {
 156         int entry_index = search_ref_dir(dir, subdirname, len);
 157         struct ref_entry *entry;
 158         if (entry_index == -1) {
 159                 if (!mkdir)
 160                         return NULL;
 161                 /*
 162                  * Since dir is complete, the absence of a subdir
 163                  * means that the subdir really doesn't exist;
 164                  * therefore, create an empty record for it but mark
 165                  * the record complete.
 166                  */
 167                 entry = create_dir_entry(dir->cache, subdirname, len, 0);
 168                 add_entry_to_dir(dir, entry);
 169         } else {
 170                 entry = dir->entries[entry_index];
 171         }
 172         return get_ref_dir(entry);
 173 }
 174
 175 /*
 176  * If refname is a reference name, find the ref_dir within the dir
 177  * tree that should hold refname. If refname is a directory name
 178  * (i.e., it ends in '/'), then return that ref_dir itself. dir must
 179  * represent the top-level directory and must already be complete.
 180  * Sort ref_dirs and recurse into subdirectories as necessary. If
 181  * mkdir is set, then create any missing directories; otherwise,
 182  * return NULL if the desired directory cannot be found.
 183  */
 184 static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 185                                            const char *refname, int mkdir)
 186 {
 187         const char *slash;
 188         for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
 189                 size_t dirnamelen = slash - refname + 1;
 190                 struct ref_dir *subdir;
 191                 subdir = search_for_subdir(dir, refname, dirnamelen, mkdir);
 192                 if (!subdir) {
 193                         dir = NULL;
 194                         break;
 195                 }
 196                 dir = subdir;
 197         }
 198
 199         return dir;
 200 }
 201
 202 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
 203 {
 204         int entry_index;
 205         struct ref_entry *entry;
 206         dir = find_containing_dir(dir, refname, 0);
 207         if (!dir)
 208                 return NULL;
 209         entry_index = search_ref_dir(dir, refname, strlen(refname));
 210         if (entry_index == -1)
 211                 return NULL;
 212         entry = dir->entries[entry_index];
 213         return (entry->flag & REF_DIR) ? NULL : entry;
 214 }
 215
 216 int remove_entry_from_dir(struct ref_dir *dir, const char *refname)
 217 {
 218         int refname_len = strlen(refname);
 219         int entry_index;
 220         struct ref_entry *entry;
 221         int is_dir = refname[refname_len - 1] == '/';
 222         if (is_dir) {
 223                 /*
 224                  * refname represents a reference directory.  Remove
 225                  * the trailing slash; otherwise we will get the
 226                  * directory *representing* refname rather than the
 227                  * one *containing* it.
 228                  */
 229                 char *dirname = xmemdupz(refname, refname_len - 1);
 230                 dir = find_containing_dir(dir, dirname, 0);
 231                 free(dirname);
 232         } else {
 233                 dir = find_containing_dir(dir, refname, 0);
 234         }
 235         if (!dir)
 236                 return -1;
 237         entry_index = search_ref_dir(dir, refname, refname_len);
 238         if (entry_index == -1)
 239                 return -1;
 240         entry = dir->entries[entry_index];
 241
 242         memmove(&dir->entries[entry_index],
 243                 &dir->entries[entry_index + 1],
 244                 (dir->nr - entry_index - 1) * sizeof(*dir->entries)
 245                 );
 246         dir->nr--;
 247         if (dir->sorted > entry_index)
 248                 dir->sorted--;
 249         free_ref_entry(entry);
 250         return dir->nr;
 251 }
 252
 253 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
 254 {
 255         dir = find_containing_dir(dir, ref->name, 1);
 256         if (!dir)
 257                 return -1;
 258         add_entry_to_dir(dir, ref);
 259         return 0;
 260 }
 261
 262 /*
 263  * Emit a warning and return true iff ref1 and ref2 have the same name
 264  * and the same sha1.  Die if they have the same name but different
 265  * sha1s.
 266  */
 267 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
 268 {
 269         if (strcmp(ref1->name, ref2->name))
 270                 return 0;
 271
 272         /* Duplicate name; make sure that they don't conflict: */
 273
 274         if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
 275                 /* This is impossible by construction */
 276                 die("Reference directory conflict: %s", ref1->name);
 277
 278         if (oidcmp(&ref1->u.value.oid, &ref2->u.value.oid))
 279                 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
 280
 281         warning("Duplicated ref: %s", ref1->name);
 282         return 1;
 283 }
 284
 285 /*
 286  * Sort the entries in dir non-recursively (if they are not already
 287  * sorted) and remove any duplicate entries.
 288  */
 289 static void sort_ref_dir(struct ref_dir *dir)
 290 {
 291         int i, j;
 292         struct ref_entry *last = NULL;
 293
 294         /*
 295          * This check also prevents passing a zero-length array to qsort(),
 296          * which is a problem on some platforms.
 297          */
 298         if (dir->sorted == dir->nr)
 299                 return;
 300
 301         QSORT(dir->entries, dir->nr, ref_entry_cmp);
 302
 303         /* Remove any duplicates: */
 304         for (i = 0, j = 0; j < dir->nr; j++) {
 305                 struct ref_entry *entry = dir->entries[j];
 306                 if (last && is_dup_ref(last, entry))
 307                         free_ref_entry(entry);
 308                 else
 309                         last = dir->entries[i++] = entry;
 310         }
 311         dir->sorted = dir->nr = i;
 312 }
 313
 314 enum prefix_state {
 315         /* All refs within the directory would match prefix: */
 316         PREFIX_CONTAINS_DIR,
 317
 318         /* Some, but not all, refs within the directory might match prefix: */
 319         PREFIX_WITHIN_DIR,
 320
 321         /* No refs within the directory could possibly match prefix: */
 322         PREFIX_EXCLUDES_DIR
 323 };
 324
 325 /*
 326  * Return a `prefix_state` constant describing the relationship
 327  * between the directory with the specified `dirname` and `prefix`.
 328  */
 329 static enum prefix_state overlaps_prefix(const char *dirname,
 330                                          const char *prefix)
 331 {
 332         while (*prefix && *dirname == *prefix) {
 333                 dirname++;
 334                 prefix++;
 335         }
 336         if (!*prefix)
 337                 return PREFIX_CONTAINS_DIR;
 338         else if (!*dirname)
 339                 return PREFIX_WITHIN_DIR;
 340         else
 341                 return PREFIX_EXCLUDES_DIR;
 342 }
 343
 344 /*
 345  * Load all of the refs from `dir` (recursively) that could possibly
 346  * contain references matching `prefix` into our in-memory cache. If
 347  * `prefix` is NULL, prime unconditionally.
 348  */
 349 static void prime_ref_dir(struct ref_dir *dir, const char *prefix)
 350 {
 351         /*
 352          * The hard work of loading loose refs is done by get_ref_dir(), so we
 353          * just need to recurse through all of the sub-directories. We do not
 354          * even need to care about sorting, as traversal order does not matter
 355          * to us.
 356          */
 357         int i;
 358         for (i = 0; i < dir->nr; i++) {
 359                 struct ref_entry *entry = dir->entries[i];
 360                 if (!(entry->flag & REF_DIR)) {
 361                         /* Not a directory; no need to recurse. */
 362                 } else if (!prefix) {
 363                         /* Recurse in any case: */
 364                         prime_ref_dir(get_ref_dir(entry), NULL);
 365                 } else {
 366                         switch (overlaps_prefix(entry->name, prefix)) {
 367                         case PREFIX_CONTAINS_DIR:
 368                                 /*
 369                                  * Recurse, and from here down we
 370                                  * don't have to check the prefix
 371                                  * anymore:
 372                                  */
 373                                 prime_ref_dir(get_ref_dir(entry), NULL);
 374                                 break;
 375                         case PREFIX_WITHIN_DIR:
 376                                 prime_ref_dir(get_ref_dir(entry), prefix);
 377                                 break;
 378                         case PREFIX_EXCLUDES_DIR:
 379                                 /* No need to prime this directory. */
 380                                 break;
 381                         }
 382                 }
 383         }
 384 }
 385
 386 /*
 387  * A level in the reference hierarchy that is currently being iterated
 388  * through.
 389  */
 390 struct cache_ref_iterator_level {
 391         /*
 392          * The ref_dir being iterated over at this level. The ref_dir
 393          * is sorted before being stored here.
 394          */
 395         struct ref_dir *dir;
 396
 397         enum prefix_state prefix_state;
 398
 399         /*
 400          * The index of the current entry within dir (which might
 401          * itself be a directory). If index == -1, then the iteration
 402          * hasn't yet begun. If index == dir->nr, then the iteration
 403          * through this level is over.
 404          */
 405         int index;
 406 };
 407
 408 /*
 409  * Represent an iteration through a ref_dir in the memory cache. The
 410  * iteration recurses through subdirectories.
 411  */
 412 struct cache_ref_iterator {
 413         struct ref_iterator base;
 414
 415         /*
 416          * The number of levels currently on the stack. This is always
 417          * at least 1, because when it becomes zero the iteration is
 418          * ended and this struct is freed.
 419          */
 420         size_t levels_nr;
 421
 422         /* The number of levels that have been allocated on the stack */
 423         size_t levels_alloc;
 424
 425         /*
 426          * Only include references with this prefix in the iteration.
 427          * The prefix is matched textually, without regard for path
 428          * component boundaries.
 429          */
 430         const char *prefix;
 431
 432         /*
 433          * A stack of levels. levels[0] is the uppermost level that is
 434          * being iterated over in this iteration. (This is not
 435          * necessary the top level in the references hierarchy. If we
 436          * are iterating through a subtree, then levels[0] will hold
 437          * the ref_dir for that subtree, and subsequent levels will go
 438          * on from there.)
 439          */
 440         struct cache_ref_iterator_level *levels;
 441 };
 442
 443 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
 444 {
 445         struct cache_ref_iterator *iter =
 446                 (struct cache_ref_iterator *)ref_iterator;
 447
 448         while (1) {
 449                 struct cache_ref_iterator_level *level =
 450                         &iter->levels[iter->levels_nr - 1];
 451                 struct ref_dir *dir = level->dir;
 452                 struct ref_entry *entry;
 453                 enum prefix_state entry_prefix_state;
 454
 455                 if (level->index == -1)
 456                         sort_ref_dir(dir);
 457
 458                 if (++level->index == level->dir->nr) {
 459                         /* This level is exhausted; pop up a level */
 460                         if (--iter->levels_nr == 0)
 461                                 return ref_iterator_abort(ref_iterator);
 462
 463                         continue;
 464                 }
 465
 466                 entry = dir->entries[level->index];
 467
 468                 if (level->prefix_state == PREFIX_WITHIN_DIR) {
 469                         entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);
 470                         if (entry_prefix_state == PREFIX_EXCLUDES_DIR)
 471                                 continue;
 472                 } else {
 473                         entry_prefix_state = level->prefix_state;
 474                 }
 475
 476                 if (entry->flag & REF_DIR) {
 477                         /* push down a level */
 478                         ALLOC_GROW(iter->levels, iter->levels_nr + 1,
 479                                    iter->levels_alloc);
 480
 481                         level = &iter->levels[iter->levels_nr++];
 482                         level->dir = get_ref_dir(entry);
 483                         level->prefix_state = entry_prefix_state;
 484                         level->index = -1;
 485                 } else {
 486                         iter->base.refname = entry->name;
 487                         iter->base.oid = &entry->u.value.oid;
 488                         iter->base.flags = entry->flag;
 489                         return ITER_OK;
 490                 }
 491         }
 492 }
 493
 494 enum peel_status peel_entry(struct ref_entry *entry, int repeel)
 495 {
 496         enum peel_status status;
 497
 498         if (entry->flag & REF_KNOWS_PEELED) {
 499                 if (repeel) {
 500                         entry->flag &= ~REF_KNOWS_PEELED;
 501                         oidclr(&entry->u.value.peeled);
 502                 } else {
 503                         return is_null_oid(&entry->u.value.peeled) ?
 504                                 PEEL_NON_TAG : PEEL_PEELED;
 505                 }
 506         }
 507         if (entry->flag & REF_ISBROKEN)
 508                 return PEEL_BROKEN;
 509         if (entry->flag & REF_ISSYMREF)
 510                 return PEEL_IS_SYMREF;
 511
 512         status = peel_object(entry->u.value.oid.hash, entry->u.value.peeled.hash);
 513         if (status == PEEL_PEELED || status == PEEL_NON_TAG)
 514                 entry->flag |= REF_KNOWS_PEELED;
 515         return status;
 516 }
 517
 518 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
 519                                    struct object_id *peeled)
 520 {
 521         struct cache_ref_iterator *iter =
 522                 (struct cache_ref_iterator *)ref_iterator;
 523         struct cache_ref_iterator_level *level;
 524         struct ref_entry *entry;
 525
 526         level = &iter->levels[iter->levels_nr - 1];
 527
 528         if (level->index == -1)
 529                 die("BUG: peel called before advance for cache iterator");
 530
 531         entry = level->dir->entries[level->index];
 532
 533         if (peel_entry(entry, 0))
 534                 return -1;
 535         oidcpy(peeled, &entry->u.value.peeled);
 536         return 0;
 537 }
 538
 539 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
 540 {
 541         struct cache_ref_iterator *iter =
 542                 (struct cache_ref_iterator *)ref_iterator;
 543
 544         free((char *)iter->prefix);
 545         free(iter->levels);
 546         base_ref_iterator_free(ref_iterator);
 547         return ITER_DONE;
 548 }
 549
 550 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
 551         cache_ref_iterator_advance,
 552         cache_ref_iterator_peel,
 553         cache_ref_iterator_abort
 554 };
 555
 556 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
 557                                               const char *prefix,
 558                                               int prime_dir)
 559 {
 560         struct ref_dir *dir;
 561         struct cache_ref_iterator *iter;
 562         struct ref_iterator *ref_iterator;
 563         struct cache_ref_iterator_level *level;
 564
 565         dir = get_ref_dir(cache->root);
 566         if (prefix && *prefix)
 567                 dir = find_containing_dir(dir, prefix, 0);
 568         if (!dir)
 569                 /* There's nothing to iterate over. */
 570                 return empty_ref_iterator_begin();
 571
 572         if (prime_dir)
 573                 prime_ref_dir(dir, prefix);
 574
 575         iter = xcalloc(1, sizeof(*iter));
 576         ref_iterator = &iter->base;
 577         base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
 578         ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
 579
 580         iter->levels_nr = 1;
 581         level = &iter->levels[0];
 582         level->index = -1;
 583         level->dir = dir;
 584
 585         if (prefix && *prefix) {
 586                 iter->prefix = xstrdup(prefix);
 587                 level->prefix_state = PREFIX_WITHIN_DIR;
 588         } else {
 589                 level->prefix_state = PREFIX_CONTAINS_DIR;
 590         }
 591
 592         return ref_iterator;
 593 }