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