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