surround %s with quotes when failed to lookup commit
[git/debian.git] / delta-islands.c
blobc824a5f6a42e56c04a46c8189d4fc1675fd172ea
1 #include "git-compat-util.h"
2 #include "alloc.h"
3 #include "attr.h"
4 #include "object.h"
5 #include "blob.h"
6 #include "commit.h"
7 #include "gettext.h"
8 #include "hex.h"
9 #include "tag.h"
10 #include "tree.h"
11 #include "delta.h"
12 #include "pack.h"
13 #include "tree-walk.h"
14 #include "diff.h"
15 #include "revision.h"
16 #include "list-objects.h"
17 #include "progress.h"
18 #include "refs.h"
19 #include "khash.h"
20 #include "pack-bitmap.h"
21 #include "pack-objects.h"
22 #include "delta-islands.h"
23 #include "oid-array.h"
24 #include "config.h"
26 KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
28 static kh_oid_map_t *island_marks;
29 static unsigned island_counter;
30 static unsigned island_counter_core;
32 struct remote_island {
33 uint64_t hash;
34 struct oid_array oids;
37 struct island_bitmap {
38 uint32_t refcount;
39 uint32_t bits[FLEX_ARRAY];
42 static uint32_t island_bitmap_size;
45 * Allocate a new bitmap; if "old" is not NULL, the new bitmap will be a copy
46 * of "old". Otherwise, the new bitmap is empty.
48 static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)
50 size_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);
51 struct island_bitmap *b = xcalloc(1, size);
53 if (old)
54 memcpy(b, old, size);
56 b->refcount = 1;
57 return b;
60 static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)
62 uint32_t i;
64 for (i = 0; i < island_bitmap_size; ++i)
65 a->bits[i] |= b->bits[i];
68 static int island_bitmap_is_subset(struct island_bitmap *self,
69 struct island_bitmap *super)
71 uint32_t i;
73 if (self == super)
74 return 1;
76 for (i = 0; i < island_bitmap_size; ++i) {
77 if ((self->bits[i] & super->bits[i]) != self->bits[i])
78 return 0;
81 return 1;
84 #define ISLAND_BITMAP_BLOCK(x) (x / 32)
85 #define ISLAND_BITMAP_MASK(x) (1 << (x % 32))
87 static void island_bitmap_set(struct island_bitmap *self, uint32_t i)
89 self->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);
92 static int island_bitmap_get(struct island_bitmap *self, uint32_t i)
94 return (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;
97 int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)
99 khiter_t trg_pos, src_pos;
101 /* If we aren't using islands, assume everything goes together. */
102 if (!island_marks)
103 return 1;
106 * If we don't have a bitmap for the target, we can delta it
107 * against anything -- it's not an important object
109 trg_pos = kh_get_oid_map(island_marks, *trg_oid);
110 if (trg_pos >= kh_end(island_marks))
111 return 1;
114 * if the source (our delta base) doesn't have a bitmap,
115 * we don't want to base any deltas on it!
117 src_pos = kh_get_oid_map(island_marks, *src_oid);
118 if (src_pos >= kh_end(island_marks))
119 return 0;
121 return island_bitmap_is_subset(kh_value(island_marks, trg_pos),
122 kh_value(island_marks, src_pos));
125 int island_delta_cmp(const struct object_id *a, const struct object_id *b)
127 khiter_t a_pos, b_pos;
128 struct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;
130 if (!island_marks)
131 return 0;
133 a_pos = kh_get_oid_map(island_marks, *a);
134 if (a_pos < kh_end(island_marks))
135 a_bitmap = kh_value(island_marks, a_pos);
137 b_pos = kh_get_oid_map(island_marks, *b);
138 if (b_pos < kh_end(island_marks))
139 b_bitmap = kh_value(island_marks, b_pos);
141 if (a_bitmap) {
142 if (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))
143 return -1;
145 if (b_bitmap) {
146 if (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap))
147 return 1;
150 return 0;
153 static struct island_bitmap *create_or_get_island_marks(struct object *obj)
155 khiter_t pos;
156 int hash_ret;
158 pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
159 if (hash_ret)
160 kh_value(island_marks, pos) = island_bitmap_new(NULL);
162 return kh_value(island_marks, pos);
165 static void set_island_marks(struct object *obj, struct island_bitmap *marks)
167 struct island_bitmap *b;
168 khiter_t pos;
169 int hash_ret;
171 pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
172 if (hash_ret) {
174 * We don't have one yet; make a copy-on-write of the
175 * parent.
177 marks->refcount++;
178 kh_value(island_marks, pos) = marks;
179 return;
183 * We do have it. Make sure we split any copy-on-write before
184 * updating.
186 b = kh_value(island_marks, pos);
187 if (b->refcount > 1) {
188 b->refcount--;
189 b = kh_value(island_marks, pos) = island_bitmap_new(b);
191 island_bitmap_or(b, marks);
194 static void mark_remote_island_1(struct repository *r,
195 struct remote_island *rl,
196 int is_core_island)
198 uint32_t i;
200 for (i = 0; i < rl->oids.nr; ++i) {
201 struct island_bitmap *marks;
202 struct object *obj = parse_object(r, &rl->oids.oid[i]);
204 if (!obj)
205 continue;
207 marks = create_or_get_island_marks(obj);
208 island_bitmap_set(marks, island_counter);
210 if (is_core_island && obj->type == OBJ_COMMIT)
211 obj->flags |= NEEDS_BITMAP;
213 /* If it was a tag, also make sure we hit the underlying object. */
214 while (obj && obj->type == OBJ_TAG) {
215 obj = ((struct tag *)obj)->tagged;
216 if (obj) {
217 parse_object(r, &obj->oid);
218 marks = create_or_get_island_marks(obj);
219 island_bitmap_set(marks, island_counter);
224 if (is_core_island)
225 island_counter_core = island_counter;
227 island_counter++;
230 struct tree_islands_todo {
231 struct object_entry *entry;
232 unsigned int depth;
235 static int tree_depth_compare(const void *a, const void *b)
237 const struct tree_islands_todo *todo_a = a;
238 const struct tree_islands_todo *todo_b = b;
240 return todo_a->depth - todo_b->depth;
243 void resolve_tree_islands(struct repository *r,
244 int progress,
245 struct packing_data *to_pack)
247 struct progress *progress_state = NULL;
248 struct tree_islands_todo *todo;
249 int nr = 0;
250 int i;
252 if (!island_marks)
253 return;
256 * We process only trees, as commits and tags have already been handled
257 * (and passed their marks on to root trees, as well. We must make sure
258 * to process them in descending tree-depth order so that marks
259 * propagate down the tree properly, even if a sub-tree is found in
260 * multiple parent trees.
262 ALLOC_ARRAY(todo, to_pack->nr_objects);
263 for (i = 0; i < to_pack->nr_objects; i++) {
264 if (oe_type(&to_pack->objects[i]) == OBJ_TREE) {
265 todo[nr].entry = &to_pack->objects[i];
266 todo[nr].depth = oe_tree_depth(to_pack, &to_pack->objects[i]);
267 nr++;
270 QSORT(todo, nr, tree_depth_compare);
272 if (progress)
273 progress_state = start_progress(_("Propagating island marks"), nr);
275 for (i = 0; i < nr; i++) {
276 struct object_entry *ent = todo[i].entry;
277 struct island_bitmap *root_marks;
278 struct tree *tree;
279 struct tree_desc desc;
280 struct name_entry entry;
281 khiter_t pos;
283 pos = kh_get_oid_map(island_marks, ent->idx.oid);
284 if (pos >= kh_end(island_marks))
285 continue;
287 root_marks = kh_value(island_marks, pos);
289 tree = lookup_tree(r, &ent->idx.oid);
290 if (!tree || parse_tree(tree) < 0)
291 die(_("bad tree object %s"), oid_to_hex(&ent->idx.oid));
293 init_tree_desc(&desc, tree->buffer, tree->size);
294 while (tree_entry(&desc, &entry)) {
295 struct object *obj;
297 if (S_ISGITLINK(entry.mode))
298 continue;
300 obj = lookup_object(r, &entry.oid);
301 if (!obj)
302 continue;
304 set_island_marks(obj, root_marks);
307 free_tree_buffer(tree);
309 display_progress(progress_state, i+1);
312 stop_progress(&progress_state);
313 free(todo);
316 struct island_load_data {
317 kh_str_t *remote_islands;
318 regex_t *rx;
319 size_t nr;
320 size_t alloc;
322 static const char *core_island_name;
324 static void free_config_regexes(struct island_load_data *ild)
326 for (size_t i = 0; i < ild->nr; i++)
327 regfree(&ild->rx[i]);
328 free(ild->rx);
331 static void free_remote_islands(kh_str_t *remote_islands)
333 const char *island_name;
334 struct remote_island *rl;
336 kh_foreach(remote_islands, island_name, rl, {
337 free((void *)island_name);
338 oid_array_clear(&rl->oids);
339 free(rl);
341 kh_destroy_str(remote_islands);
344 static int island_config_callback(const char *k, const char *v, void *cb)
346 struct island_load_data *ild = cb;
348 if (!strcmp(k, "pack.island")) {
349 struct strbuf re = STRBUF_INIT;
351 if (!v)
352 return config_error_nonbool(k);
354 ALLOC_GROW(ild->rx, ild->nr + 1, ild->alloc);
356 if (*v != '^')
357 strbuf_addch(&re, '^');
358 strbuf_addstr(&re, v);
360 if (regcomp(&ild->rx[ild->nr], re.buf, REG_EXTENDED))
361 die(_("failed to load island regex for '%s': %s"), k, re.buf);
363 strbuf_release(&re);
364 ild->nr++;
365 return 0;
368 if (!strcmp(k, "pack.islandcore"))
369 return git_config_string(&core_island_name, k, v);
371 return 0;
374 static void add_ref_to_island(kh_str_t *remote_islands, const char *island_name,
375 const struct object_id *oid)
377 uint64_t sha_core;
378 struct remote_island *rl = NULL;
380 int hash_ret;
381 khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);
383 if (hash_ret) {
384 kh_key(remote_islands, pos) = xstrdup(island_name);
385 kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));
388 rl = kh_value(remote_islands, pos);
389 oid_array_append(&rl->oids, oid);
391 memcpy(&sha_core, oid->hash, sizeof(uint64_t));
392 rl->hash += sha_core;
395 static int find_island_for_ref(const char *refname, const struct object_id *oid,
396 int flags UNUSED, void *cb)
398 struct island_load_data *ild = cb;
401 * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,
402 * so we can diagnose below a config with more capture groups
403 * than we support.
405 regmatch_t matches[16];
406 int i, m;
407 struct strbuf island_name = STRBUF_INIT;
409 /* walk backwards to get last-one-wins ordering */
410 for (i = ild->nr - 1; i >= 0; i--) {
411 if (!regexec(&ild->rx[i], refname,
412 ARRAY_SIZE(matches), matches, 0))
413 break;
416 if (i < 0)
417 return 0;
419 if (matches[ARRAY_SIZE(matches) - 1].rm_so != -1)
420 warning(_("island regex from config has "
421 "too many capture groups (max=%d)"),
422 (int)ARRAY_SIZE(matches) - 2);
424 for (m = 1; m < ARRAY_SIZE(matches); m++) {
425 regmatch_t *match = &matches[m];
427 if (match->rm_so == -1)
428 continue;
430 if (island_name.len)
431 strbuf_addch(&island_name, '-');
433 strbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);
436 add_ref_to_island(ild->remote_islands, island_name.buf, oid);
437 strbuf_release(&island_name);
438 return 0;
441 static struct remote_island *get_core_island(kh_str_t *remote_islands)
443 if (core_island_name) {
444 khiter_t pos = kh_get_str(remote_islands, core_island_name);
445 if (pos < kh_end(remote_islands))
446 return kh_value(remote_islands, pos);
449 return NULL;
452 static void deduplicate_islands(kh_str_t *remote_islands, struct repository *r)
454 struct remote_island *island, *core = NULL, **list;
455 unsigned int island_count, dst, src, ref, i = 0;
457 island_count = kh_size(remote_islands);
458 ALLOC_ARRAY(list, island_count);
460 kh_foreach_value(remote_islands, island, {
461 list[i++] = island;
464 for (ref = 0; ref + 1 < island_count; ref++) {
465 for (src = ref + 1, dst = src; src < island_count; src++) {
466 if (list[ref]->hash == list[src]->hash)
467 continue;
469 if (src != dst)
470 list[dst] = list[src];
472 dst++;
474 island_count = dst;
477 island_bitmap_size = (island_count / 32) + 1;
478 core = get_core_island(remote_islands);
480 for (i = 0; i < island_count; ++i) {
481 mark_remote_island_1(r, list[i], core && list[i]->hash == core->hash);
484 free(list);
487 void load_delta_islands(struct repository *r, int progress)
489 struct island_load_data ild = { 0 };
491 island_marks = kh_init_oid_map();
493 git_config(island_config_callback, &ild);
494 ild.remote_islands = kh_init_str();
495 for_each_ref(find_island_for_ref, &ild);
496 free_config_regexes(&ild);
497 deduplicate_islands(ild.remote_islands, r);
498 free_remote_islands(ild.remote_islands);
500 if (progress)
501 fprintf(stderr, _("Marked %d islands, done.\n"), island_counter);
504 void propagate_island_marks(struct commit *commit)
506 khiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);
508 if (pos < kh_end(island_marks)) {
509 struct commit_list *p;
510 struct island_bitmap *root_marks = kh_value(island_marks, pos);
512 repo_parse_commit(the_repository, commit);
513 set_island_marks(&repo_get_commit_tree(the_repository, commit)->object,
514 root_marks);
515 for (p = commit->parents; p; p = p->next)
516 set_island_marks(&p->item->object, root_marks);
520 void free_island_marks(void)
522 struct island_bitmap *bitmap;
524 if (island_marks) {
525 kh_foreach_value(island_marks, bitmap, {
526 if (!--bitmap->refcount)
527 free(bitmap);
529 kh_destroy_oid_map(island_marks);
532 /* detect use-after-free with a an address which is never valid: */
533 island_marks = (void *)-1;
536 int compute_pack_layers(struct packing_data *to_pack)
538 uint32_t i;
540 if (!core_island_name || !island_marks)
541 return 1;
543 for (i = 0; i < to_pack->nr_objects; ++i) {
544 struct object_entry *entry = &to_pack->objects[i];
545 khiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);
547 oe_set_layer(to_pack, entry, 1);
549 if (pos < kh_end(island_marks)) {
550 struct island_bitmap *bitmap = kh_value(island_marks, pos);
552 if (island_bitmap_get(bitmap, island_counter_core))
553 oe_set_layer(to_pack, entry, 0);
557 return 2;