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 struct object_id *oid, int flag)
  38 {
  39         struct ref_entry *ref;
  40
  41         FLEX_ALLOC_STR(ref, name, refname);
  42         oidcpy(&ref->u.value.oid, oid);
  43         ref->flag = flag;
  44         return ref;
  45 }
  46
  47 struct ref_cache *create_ref_cache(struct ref_store *refs,
  48                                    fill_ref_dir_fn *fill_ref_dir)
  49 {
  50         struct ref_cache *ret = xcalloc(1, sizeof(*ret));
  51
  52         ret->ref_store = refs;
  53         ret->fill_ref_dir = fill_ref_dir;
  54         ret->root = create_dir_entry(ret, "", 0);
  55         return ret;
  56 }
  57
  58 static void clear_ref_dir(struct ref_dir *dir);
  59
  60 static void free_ref_entry(struct ref_entry *entry)
  61 {
  62         if (entry->flag & REF_DIR) {
  63                 /*
  64                  * Do not use get_ref_dir() here, as that might
  65                  * trigger the reading of loose refs.
  66                  */
  67                 clear_ref_dir(&entry->u.subdir);
  68         }
  69         free(entry);
  70 }
  71
  72 void free_ref_cache(struct ref_cache *cache)
  73 {
  74         free_ref_entry(cache->root);
  75         free(cache);
  76 }
  77
  78 /*
  79  * Clear and free all entries in dir, recursively.
  80  */
  81 static void clear_ref_dir(struct ref_dir *dir)
  82 {
  83         int i;
  84         for (i = 0; i < dir->nr; i++)
  85                 free_ref_entry(dir->entries[i]);
  86         FREE_AND_NULL(dir->entries);
  87         dir->sorted = dir->nr = dir->alloc = 0;
  88 }
  89
  90 struct ref_entry *create_dir_entry(struct ref_cache *cache,
  91                                    const char *dirname, size_t len)
  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 | REF_INCOMPLETE;
  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)
 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 '/'). Returns 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 {
 154         int entry_index = search_ref_dir(dir, subdirname, len);
 155         struct ref_entry *entry;
 156
 157         if (entry_index == -1)
 158                 return NULL;
 159
 160         entry = dir->entries[entry_index];
 161         return get_ref_dir(entry);
 162 }
 163
 164 /*
 165  * If refname is a reference name, find the ref_dir within the dir
 166  * tree that should hold refname. If refname is a directory name
 167  * (i.e., it ends in '/'), then return that ref_dir itself. dir must
 168  * represent the top-level directory and must already be complete.
 169  * Sort ref_dirs and recurse into subdirectories as necessary. Will
 170  * return NULL if the desired directory cannot be found.
 171  */
 172 static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 173                                            const char *refname)
 174 {
 175         const char *slash;
 176         for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
 177                 size_t dirnamelen = slash - refname + 1;
 178                 struct ref_dir *subdir;
 179                 subdir = search_for_subdir(dir, refname, dirnamelen);
 180                 if (!subdir) {
 181                         dir = NULL;
 182                         break;
 183                 }
 184                 dir = subdir;
 185         }
 186
 187         return dir;
 188 }
 189
 190 struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname)
 191 {
 192         int entry_index;
 193         struct ref_entry *entry;
 194         dir = find_containing_dir(dir, refname);
 195         if (!dir)
 196                 return NULL;
 197         entry_index = search_ref_dir(dir, refname, strlen(refname));
 198         if (entry_index == -1)
 199                 return NULL;
 200         entry = dir->entries[entry_index];
 201         return (entry->flag & REF_DIR) ? NULL : entry;
 202 }
 203
 204 /*
 205  * Emit a warning and return true iff ref1 and ref2 have the same name
 206  * and the same oid. Die if they have the same name but different
 207  * oids.
 208  */
 209 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
 210 {
 211         if (strcmp(ref1->name, ref2->name))
 212                 return 0;
 213
 214         /* Duplicate name; make sure that they don't conflict: */
 215
 216         if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
 217                 /* This is impossible by construction */
 218                 die("Reference directory conflict: %s", ref1->name);
 219
 220         if (!oideq(&ref1->u.value.oid, &ref2->u.value.oid))
 221                 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
 222
 223         warning("Duplicated ref: %s", ref1->name);
 224         return 1;
 225 }
 226
 227 /*
 228  * Sort the entries in dir non-recursively (if they are not already
 229  * sorted) and remove any duplicate entries.
 230  */
 231 static void sort_ref_dir(struct ref_dir *dir)
 232 {
 233         int i, j;
 234         struct ref_entry *last = NULL;
 235
 236         /*
 237          * This check also prevents passing a zero-length array to qsort(),
 238          * which is a problem on some platforms.
 239          */
 240         if (dir->sorted == dir->nr)
 241                 return;
 242
 243         QSORT(dir->entries, dir->nr, ref_entry_cmp);
 244
 245         /* Remove any duplicates: */
 246         for (i = 0, j = 0; j < dir->nr; j++) {
 247                 struct ref_entry *entry = dir->entries[j];
 248                 if (last && is_dup_ref(last, entry))
 249                         free_ref_entry(entry);
 250                 else
 251                         last = dir->entries[i++] = entry;
 252         }
 253         dir->sorted = dir->nr = i;
 254 }
 255
 256 enum prefix_state {
 257         /* All refs within the directory would match prefix: */
 258         PREFIX_CONTAINS_DIR,
 259
 260         /* Some, but not all, refs within the directory might match prefix: */
 261         PREFIX_WITHIN_DIR,
 262
 263         /* No refs within the directory could possibly match prefix: */
 264         PREFIX_EXCLUDES_DIR
 265 };
 266
 267 /*
 268  * Return a `prefix_state` constant describing the relationship
 269  * between the directory with the specified `dirname` and `prefix`.
 270  */
 271 static enum prefix_state overlaps_prefix(const char *dirname,
 272                                          const char *prefix)
 273 {
 274         while (*prefix && *dirname == *prefix) {
 275                 dirname++;
 276                 prefix++;
 277         }
 278         if (!*prefix)
 279                 return PREFIX_CONTAINS_DIR;
 280         else if (!*dirname)
 281                 return PREFIX_WITHIN_DIR;
 282         else
 283                 return PREFIX_EXCLUDES_DIR;
 284 }
 285
 286 /*
 287  * Load all of the refs from `dir` (recursively) that could possibly
 288  * contain references matching `prefix` into our in-memory cache. If
 289  * `prefix` is NULL, prime unconditionally.
 290  */
 291 static void prime_ref_dir(struct ref_dir *dir, const char *prefix)
 292 {
 293         /*
 294          * The hard work of loading loose refs is done by get_ref_dir(), so we
 295          * just need to recurse through all of the sub-directories. We do not
 296          * even need to care about sorting, as traversal order does not matter
 297          * to us.
 298          */
 299         int i;
 300         for (i = 0; i < dir->nr; i++) {
 301                 struct ref_entry *entry = dir->entries[i];
 302                 if (!(entry->flag & REF_DIR)) {
 303                         /* Not a directory; no need to recurse. */
 304                 } else if (!prefix) {
 305                         /* Recurse in any case: */
 306                         prime_ref_dir(get_ref_dir(entry), NULL);
 307                 } else {
 308                         switch (overlaps_prefix(entry->name, prefix)) {
 309                         case PREFIX_CONTAINS_DIR:
 310                                 /*
 311                                  * Recurse, and from here down we
 312                                  * don't have to check the prefix
 313                                  * anymore:
 314                                  */
 315                                 prime_ref_dir(get_ref_dir(entry), NULL);
 316                                 break;
 317                         case PREFIX_WITHIN_DIR:
 318                                 prime_ref_dir(get_ref_dir(entry), prefix);
 319                                 break;
 320                         case PREFIX_EXCLUDES_DIR:
 321                                 /* No need to prime this directory. */
 322                                 break;
 323                         }
 324                 }
 325         }
 326 }
 327
 328 /*
 329  * A level in the reference hierarchy that is currently being iterated
 330  * through.
 331  */
 332 struct cache_ref_iterator_level {
 333         /*
 334          * The ref_dir being iterated over at this level. The ref_dir
 335          * is sorted before being stored here.
 336          */
 337         struct ref_dir *dir;
 338
 339         enum prefix_state prefix_state;
 340
 341         /*
 342          * The index of the current entry within dir (which might
 343          * itself be a directory). If index == -1, then the iteration
 344          * hasn't yet begun. If index == dir->nr, then the iteration
 345          * through this level is over.
 346          */
 347         int index;
 348 };
 349
 350 /*
 351  * Represent an iteration through a ref_dir in the memory cache. The
 352  * iteration recurses through subdirectories.
 353  */
 354 struct cache_ref_iterator {
 355         struct ref_iterator base;
 356
 357         /*
 358          * The number of levels currently on the stack. This is always
 359          * at least 1, because when it becomes zero the iteration is
 360          * ended and this struct is freed.
 361          */
 362         size_t levels_nr;
 363
 364         /* The number of levels that have been allocated on the stack */
 365         size_t levels_alloc;
 366
 367         /*
 368          * Only include references with this prefix in the iteration.
 369          * The prefix is matched textually, without regard for path
 370          * component boundaries.
 371          */
 372         const char *prefix;
 373
 374         /*
 375          * A stack of levels. levels[0] is the uppermost level that is
 376          * being iterated over in this iteration. (This is not
 377          * necessary the top level in the references hierarchy. If we
 378          * are iterating through a subtree, then levels[0] will hold
 379          * the ref_dir for that subtree, and subsequent levels will go
 380          * on from there.)
 381          */
 382         struct cache_ref_iterator_level *levels;
 383
 384         struct repository *repo;
 385 };
 386
 387 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
 388 {
 389         struct cache_ref_iterator *iter =
 390                 (struct cache_ref_iterator *)ref_iterator;
 391
 392         while (1) {
 393                 struct cache_ref_iterator_level *level =
 394                         &iter->levels[iter->levels_nr - 1];
 395                 struct ref_dir *dir = level->dir;
 396                 struct ref_entry *entry;
 397                 enum prefix_state entry_prefix_state;
 398
 399                 if (level->index == -1)
 400                         sort_ref_dir(dir);
 401
 402                 if (++level->index == level->dir->nr) {
 403                         /* This level is exhausted; pop up a level */
 404                         if (--iter->levels_nr == 0)
 405                                 return ref_iterator_abort(ref_iterator);
 406
 407                         continue;
 408                 }
 409
 410                 entry = dir->entries[level->index];
 411
 412                 if (level->prefix_state == PREFIX_WITHIN_DIR) {
 413                         entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);
 414                         if (entry_prefix_state == PREFIX_EXCLUDES_DIR ||
 415                             (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_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 }