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