ref_cache: remove support for storing peeled values
[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 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 memmove(&dir->entries[entry_index],
242 &dir->entries[entry_index + 1],
243 (dir->nr - entry_index - 1) * sizeof(*dir->entries)
244 );
245 dir->nr--;
246 if (dir->sorted > entry_index)
247 dir->sorted--;
248 free_ref_entry(entry);
249 return dir->nr;
250 }
251
252 int add_ref_entry(struct ref_dir *dir, struct ref_entry *ref)
253 {
254 dir = find_containing_dir(dir, ref->name, 1);
255 if (!dir)
256 return -1;
257 add_entry_to_dir(dir, ref);
258 return 0;
259 }
260
261 /*
262 * Emit a warning and return true iff ref1 and ref2 have the same name
263 * and the same sha1. Die if they have the same name but different
264 * sha1s.
265 */
266 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
267 {
268 if (strcmp(ref1->name, ref2->name))
269 return 0;
270
271 /* Duplicate name; make sure that they don't conflict: */
272
273 if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
274 /* This is impossible by construction */
275 die("Reference directory conflict: %s", ref1->name);
276
277 if (oidcmp(&ref1->u.value.oid, &ref2->u.value.oid))
278 die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
279
280 warning("Duplicated ref: %s", ref1->name);
281 return 1;
282 }
283
284 /*
285 * Sort the entries in dir non-recursively (if they are not already
286 * sorted) and remove any duplicate entries.
287 */
288 static void sort_ref_dir(struct ref_dir *dir)
289 {
290 int i, j;
291 struct ref_entry *last = NULL;
292
293 /*
294 * This check also prevents passing a zero-length array to qsort(),
295 * which is a problem on some platforms.
296 */
297 if (dir->sorted == dir->nr)
298 return;
299
300 QSORT(dir->entries, dir->nr, ref_entry_cmp);
301
302 /* Remove any duplicates: */
303 for (i = 0, j = 0; j < dir->nr; j++) {
304 struct ref_entry *entry = dir->entries[j];
305 if (last && is_dup_ref(last, entry))
306 free_ref_entry(entry);
307 else
308 last = dir->entries[i++] = entry;
309 }
310 dir->sorted = dir->nr = i;
311 }
312
313 enum prefix_state {
314 /* All refs within the directory would match prefix: */
315 PREFIX_CONTAINS_DIR,
316
317 /* Some, but not all, refs within the directory might match prefix: */
318 PREFIX_WITHIN_DIR,
319
320 /* No refs within the directory could possibly match prefix: */
321 PREFIX_EXCLUDES_DIR
322 };
323
324 /*
325 * Return a `prefix_state` constant describing the relationship
326 * between the directory with the specified `dirname` and `prefix`.
327 */
328 static enum prefix_state overlaps_prefix(const char *dirname,
329 const char *prefix)
330 {
331 while (*prefix && *dirname == *prefix) {
332 dirname++;
333 prefix++;
334 }
335 if (!*prefix)
336 return PREFIX_CONTAINS_DIR;
337 else if (!*dirname)
338 return PREFIX_WITHIN_DIR;
339 else
340 return PREFIX_EXCLUDES_DIR;
341 }
342
343 /*
344 * Load all of the refs from `dir` (recursively) that could possibly
345 * contain references matching `prefix` into our in-memory cache. If
346 * `prefix` is NULL, prime unconditionally.
347 */
348 static void prime_ref_dir(struct ref_dir *dir, const char *prefix)
349 {
350 /*
351 * The hard work of loading loose refs is done by get_ref_dir(), so we
352 * just need to recurse through all of the sub-directories. We do not
353 * even need to care about sorting, as traversal order does not matter
354 * to us.
355 */
356 int i;
357 for (i = 0; i < dir->nr; i++) {
358 struct ref_entry *entry = dir->entries[i];
359 if (!(entry->flag & REF_DIR)) {
360 /* Not a directory; no need to recurse. */
361 } else if (!prefix) {
362 /* Recurse in any case: */
363 prime_ref_dir(get_ref_dir(entry), NULL);
364 } else {
365 switch (overlaps_prefix(entry->name, prefix)) {
366 case PREFIX_CONTAINS_DIR:
367 /*
368 * Recurse, and from here down we
369 * don't have to check the prefix
370 * anymore:
371 */
372 prime_ref_dir(get_ref_dir(entry), NULL);
373 break;
374 case PREFIX_WITHIN_DIR:
375 prime_ref_dir(get_ref_dir(entry), prefix);
376 break;
377 case PREFIX_EXCLUDES_DIR:
378 /* No need to prime this directory. */
379 break;
380 }
381 }
382 }
383 }
384
385 /*
386 * A level in the reference hierarchy that is currently being iterated
387 * through.
388 */
389 struct cache_ref_iterator_level {
390 /*
391 * The ref_dir being iterated over at this level. The ref_dir
392 * is sorted before being stored here.
393 */
394 struct ref_dir *dir;
395
396 enum prefix_state prefix_state;
397
398 /*
399 * The index of the current entry within dir (which might
400 * itself be a directory). If index == -1, then the iteration
401 * hasn't yet begun. If index == dir->nr, then the iteration
402 * through this level is over.
403 */
404 int index;
405 };
406
407 /*
408 * Represent an iteration through a ref_dir in the memory cache. The
409 * iteration recurses through subdirectories.
410 */
411 struct cache_ref_iterator {
412 struct ref_iterator base;
413
414 /*
415 * The number of levels currently on the stack. This is always
416 * at least 1, because when it becomes zero the iteration is
417 * ended and this struct is freed.
418 */
419 size_t levels_nr;
420
421 /* The number of levels that have been allocated on the stack */
422 size_t levels_alloc;
423
424 /*
425 * Only include references with this prefix in the iteration.
426 * The prefix is matched textually, without regard for path
427 * component boundaries.
428 */
429 const char *prefix;
430
431 /*
432 * A stack of levels. levels[0] is the uppermost level that is
433 * being iterated over in this iteration. (This is not
434 * necessary the top level in the references hierarchy. If we
435 * are iterating through a subtree, then levels[0] will hold
436 * the ref_dir for that subtree, and subsequent levels will go
437 * on from there.)
438 */
439 struct cache_ref_iterator_level *levels;
440 };
441
442 static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
443 {
444 struct cache_ref_iterator *iter =
445 (struct cache_ref_iterator *)ref_iterator;
446
447 while (1) {
448 struct cache_ref_iterator_level *level =
449 &iter->levels[iter->levels_nr - 1];
450 struct ref_dir *dir = level->dir;
451 struct ref_entry *entry;
452 enum prefix_state entry_prefix_state;
453
454 if (level->index == -1)
455 sort_ref_dir(dir);
456
457 if (++level->index == level->dir->nr) {
458 /* This level is exhausted; pop up a level */
459 if (--iter->levels_nr == 0)
460 return ref_iterator_abort(ref_iterator);
461
462 continue;
463 }
464
465 entry = dir->entries[level->index];
466
467 if (level->prefix_state == PREFIX_WITHIN_DIR) {
468 entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);
469 if (entry_prefix_state == PREFIX_EXCLUDES_DIR)
470 continue;
471 } else {
472 entry_prefix_state = level->prefix_state;
473 }
474
475 if (entry->flag & REF_DIR) {
476 /* push down a level */
477 ALLOC_GROW(iter->levels, iter->levels_nr + 1,
478 iter->levels_alloc);
479
480 level = &iter->levels[iter->levels_nr++];
481 level->dir = get_ref_dir(entry);
482 level->prefix_state = entry_prefix_state;
483 level->index = -1;
484 } else {
485 iter->base.refname = entry->name;
486 iter->base.oid = &entry->u.value.oid;
487 iter->base.flags = entry->flag;
488 return ITER_OK;
489 }
490 }
491 }
492
493 static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator,
494 struct object_id *peeled)
495 {
496 return peel_object(ref_iterator->oid->hash, peeled->hash);
497 }
498
499 static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator)
500 {
501 struct cache_ref_iterator *iter =
502 (struct cache_ref_iterator *)ref_iterator;
503
504 free((char *)iter->prefix);
505 free(iter->levels);
506 base_ref_iterator_free(ref_iterator);
507 return ITER_DONE;
508 }
509
510 static struct ref_iterator_vtable cache_ref_iterator_vtable = {
511 cache_ref_iterator_advance,
512 cache_ref_iterator_peel,
513 cache_ref_iterator_abort
514 };
515
516 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
517 const char *prefix,
518 int prime_dir)
519 {
520 struct ref_dir *dir;
521 struct cache_ref_iterator *iter;
522 struct ref_iterator *ref_iterator;
523 struct cache_ref_iterator_level *level;
524
525 dir = get_ref_dir(cache->root);
526 if (prefix && *prefix)
527 dir = find_containing_dir(dir, prefix, 0);
528 if (!dir)
529 /* There's nothing to iterate over. */
530 return empty_ref_iterator_begin();
531
532 if (prime_dir)
533 prime_ref_dir(dir, prefix);
534
535 iter = xcalloc(1, sizeof(*iter));
536 ref_iterator = &iter->base;
537 base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable, 1);
538 ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
539
540 iter->levels_nr = 1;
541 level = &iter->levels[0];
542 level->index = -1;
543 level->dir = dir;
544
545 if (prefix && *prefix) {
546 iter->prefix = xstrdup(prefix);
547 level->prefix_state = PREFIX_WITHIN_DIR;
548 } else {
549 level->prefix_state = PREFIX_CONTAINS_DIR;
550 }
551
552 return ref_iterator;
553 }