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