refs/ref-cache.c

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