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