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