refs/ref-cache.c

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