Merge branch 'ab/ref-filter-no-contains' into maint
[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 }