Merge branch 'js/remote-curl-i18n'
[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 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 }