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