use xsnprintf for generating git object headers
[git] / shallow.c
1 #include "cache.h"
2 #include "tempfile.h"
3 #include "lockfile.h"
4 #include "commit.h"
5 #include "tag.h"
6 #include "pkt-line.h"
7 #include "remote.h"
8 #include "refs.h"
9 #include "sha1-array.h"
10 #include "diff.h"
11 #include "revision.h"
12 #include "commit-slab.h"
13 #include "sigchain.h"
14
15 static int is_shallow = -1;
16 static struct stat_validity shallow_stat;
17 static char *alternate_shallow_file;
18
19 void set_alternate_shallow_file(const char *path, int override)
20 {
21         if (is_shallow != -1)
22                 die("BUG: is_repository_shallow must not be called before set_alternate_shallow_file");
23         if (alternate_shallow_file && !override)
24                 return;
25         free(alternate_shallow_file);
26         alternate_shallow_file = xstrdup_or_null(path);
27 }
28
29 int register_shallow(const unsigned char *sha1)
30 {
31         struct commit_graft *graft =
32                 xmalloc(sizeof(struct commit_graft));
33         struct commit *commit = lookup_commit(sha1);
34
35         hashcpy(graft->oid.hash, sha1);
36         graft->nr_parent = -1;
37         if (commit && commit->object.parsed)
38                 commit->parents = NULL;
39         return register_commit_graft(graft, 0);
40 }
41
42 int is_repository_shallow(void)
43 {
44         FILE *fp;
45         char buf[1024];
46         const char *path = alternate_shallow_file;
47
48         if (is_shallow >= 0)
49                 return is_shallow;
50
51         if (!path)
52                 path = git_path_shallow();
53         /*
54          * fetch-pack sets '--shallow-file ""' as an indicator that no
55          * shallow file should be used. We could just open it and it
56          * will likely fail. But let's do an explicit check instead.
57          */
58         if (!*path || (fp = fopen(path, "r")) == NULL) {
59                 stat_validity_clear(&shallow_stat);
60                 is_shallow = 0;
61                 return is_shallow;
62         }
63         stat_validity_update(&shallow_stat, fileno(fp));
64         is_shallow = 1;
65
66         while (fgets(buf, sizeof(buf), fp)) {
67                 unsigned char sha1[20];
68                 if (get_sha1_hex(buf, sha1))
69                         die("bad shallow line: %s", buf);
70                 register_shallow(sha1);
71         }
72         fclose(fp);
73         return is_shallow;
74 }
75
76 struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
77                 int shallow_flag, int not_shallow_flag)
78 {
79         int i = 0, cur_depth = 0;
80         struct commit_list *result = NULL;
81         struct object_array stack = OBJECT_ARRAY_INIT;
82         struct commit *commit = NULL;
83         struct commit_graft *graft;
84
85         while (commit || i < heads->nr || stack.nr) {
86                 struct commit_list *p;
87                 if (!commit) {
88                         if (i < heads->nr) {
89                                 commit = (struct commit *)
90                                         deref_tag(heads->objects[i++].item, NULL, 0);
91                                 if (!commit || commit->object.type != OBJ_COMMIT) {
92                                         commit = NULL;
93                                         continue;
94                                 }
95                                 if (!commit->util)
96                                         commit->util = xmalloc(sizeof(int));
97                                 *(int *)commit->util = 0;
98                                 cur_depth = 0;
99                         } else {
100                                 commit = (struct commit *)
101                                         stack.objects[--stack.nr].item;
102                                 cur_depth = *(int *)commit->util;
103                         }
104                 }
105                 parse_commit_or_die(commit);
106                 cur_depth++;
107                 if ((depth != INFINITE_DEPTH && cur_depth >= depth) ||
108                     (is_repository_shallow() && !commit->parents &&
109                      (graft = lookup_commit_graft(commit->object.sha1)) != NULL &&
110                      graft->nr_parent < 0)) {
111                         commit_list_insert(commit, &result);
112                         commit->object.flags |= shallow_flag;
113                         commit = NULL;
114                         continue;
115                 }
116                 commit->object.flags |= not_shallow_flag;
117                 for (p = commit->parents, commit = NULL; p; p = p->next) {
118                         if (!p->item->util) {
119                                 int *pointer = xmalloc(sizeof(int));
120                                 p->item->util = pointer;
121                                 *pointer =  cur_depth;
122                         } else {
123                                 int *pointer = p->item->util;
124                                 if (cur_depth >= *pointer)
125                                         continue;
126                                 *pointer = cur_depth;
127                         }
128                         if (p->next)
129                                 add_object_array(&p->item->object,
130                                                 NULL, &stack);
131                         else {
132                                 commit = p->item;
133                                 cur_depth = *(int *)commit->util;
134                         }
135                 }
136         }
137
138         return result;
139 }
140
141 static void check_shallow_file_for_update(void)
142 {
143         if (is_shallow == -1)
144                 die("BUG: shallow must be initialized by now");
145
146         if (!stat_validity_check(&shallow_stat, git_path_shallow()))
147                 die("shallow file has changed since we read it");
148 }
149
150 #define SEEN_ONLY 1
151 #define VERBOSE   2
152
153 struct write_shallow_data {
154         struct strbuf *out;
155         int use_pack_protocol;
156         int count;
157         unsigned flags;
158 };
159
160 static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
161 {
162         struct write_shallow_data *data = cb_data;
163         const char *hex = oid_to_hex(&graft->oid);
164         if (graft->nr_parent != -1)
165                 return 0;
166         if (data->flags & SEEN_ONLY) {
167                 struct commit *c = lookup_commit(graft->oid.hash);
168                 if (!c || !(c->object.flags & SEEN)) {
169                         if (data->flags & VERBOSE)
170                                 printf("Removing %s from .git/shallow\n",
171                                        sha1_to_hex(c->object.sha1));
172                         return 0;
173                 }
174         }
175         data->count++;
176         if (data->use_pack_protocol)
177                 packet_buf_write(data->out, "shallow %s", hex);
178         else {
179                 strbuf_addstr(data->out, hex);
180                 strbuf_addch(data->out, '\n');
181         }
182         return 0;
183 }
184
185 static int write_shallow_commits_1(struct strbuf *out, int use_pack_protocol,
186                                    const struct sha1_array *extra,
187                                    unsigned flags)
188 {
189         struct write_shallow_data data;
190         int i;
191         data.out = out;
192         data.use_pack_protocol = use_pack_protocol;
193         data.count = 0;
194         data.flags = flags;
195         for_each_commit_graft(write_one_shallow, &data);
196         if (!extra)
197                 return data.count;
198         for (i = 0; i < extra->nr; i++) {
199                 strbuf_addstr(out, sha1_to_hex(extra->sha1[i]));
200                 strbuf_addch(out, '\n');
201                 data.count++;
202         }
203         return data.count;
204 }
205
206 int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
207                           const struct sha1_array *extra)
208 {
209         return write_shallow_commits_1(out, use_pack_protocol, extra, 0);
210 }
211
212 static struct tempfile temporary_shallow;
213
214 const char *setup_temporary_shallow(const struct sha1_array *extra)
215 {
216         struct strbuf sb = STRBUF_INIT;
217         int fd;
218
219         if (write_shallow_commits(&sb, 0, extra)) {
220                 fd = xmks_tempfile(&temporary_shallow, git_path("shallow_XXXXXX"));
221
222                 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
223                         die_errno("failed to write to %s",
224                                   get_tempfile_path(&temporary_shallow));
225                 close_tempfile(&temporary_shallow);
226                 strbuf_release(&sb);
227                 return get_tempfile_path(&temporary_shallow);
228         }
229         /*
230          * is_repository_shallow() sees empty string as "no shallow
231          * file".
232          */
233         return get_tempfile_path(&temporary_shallow);
234 }
235
236 void setup_alternate_shallow(struct lock_file *shallow_lock,
237                              const char **alternate_shallow_file,
238                              const struct sha1_array *extra)
239 {
240         struct strbuf sb = STRBUF_INIT;
241         int fd;
242
243         fd = hold_lock_file_for_update(shallow_lock, git_path_shallow(),
244                                        LOCK_DIE_ON_ERROR);
245         check_shallow_file_for_update();
246         if (write_shallow_commits(&sb, 0, extra)) {
247                 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
248                         die_errno("failed to write to %s",
249                                   get_lock_file_path(shallow_lock));
250                 *alternate_shallow_file = get_lock_file_path(shallow_lock);
251         } else
252                 /*
253                  * is_repository_shallow() sees empty string as "no
254                  * shallow file".
255                  */
256                 *alternate_shallow_file = "";
257         strbuf_release(&sb);
258 }
259
260 static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
261 {
262         int fd = *(int *)cb;
263         if (graft->nr_parent == -1)
264                 packet_write(fd, "shallow %s\n", oid_to_hex(&graft->oid));
265         return 0;
266 }
267
268 void advertise_shallow_grafts(int fd)
269 {
270         if (!is_repository_shallow())
271                 return;
272         for_each_commit_graft(advertise_shallow_grafts_cb, &fd);
273 }
274
275 /*
276  * mark_reachable_objects() should have been run prior to this and all
277  * reachable commits marked as "SEEN".
278  */
279 void prune_shallow(int show_only)
280 {
281         static struct lock_file shallow_lock;
282         struct strbuf sb = STRBUF_INIT;
283         int fd;
284
285         if (show_only) {
286                 write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY | VERBOSE);
287                 strbuf_release(&sb);
288                 return;
289         }
290         fd = hold_lock_file_for_update(&shallow_lock, git_path_shallow(),
291                                        LOCK_DIE_ON_ERROR);
292         check_shallow_file_for_update();
293         if (write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY)) {
294                 if (write_in_full(fd, sb.buf, sb.len) != sb.len)
295                         die_errno("failed to write to %s",
296                                   get_lock_file_path(&shallow_lock));
297                 commit_lock_file(&shallow_lock);
298         } else {
299                 unlink(git_path_shallow());
300                 rollback_lock_file(&shallow_lock);
301         }
302         strbuf_release(&sb);
303 }
304
305 struct trace_key trace_shallow = TRACE_KEY_INIT(SHALLOW);
306
307 /*
308  * Step 1, split sender shallow commits into "ours" and "theirs"
309  * Step 2, clean "ours" based on .git/shallow
310  */
311 void prepare_shallow_info(struct shallow_info *info, struct sha1_array *sa)
312 {
313         int i;
314         trace_printf_key(&trace_shallow, "shallow: prepare_shallow_info\n");
315         memset(info, 0, sizeof(*info));
316         info->shallow = sa;
317         if (!sa)
318                 return;
319         info->ours = xmalloc(sizeof(*info->ours) * sa->nr);
320         info->theirs = xmalloc(sizeof(*info->theirs) * sa->nr);
321         for (i = 0; i < sa->nr; i++) {
322                 if (has_sha1_file(sa->sha1[i])) {
323                         struct commit_graft *graft;
324                         graft = lookup_commit_graft(sa->sha1[i]);
325                         if (graft && graft->nr_parent < 0)
326                                 continue;
327                         info->ours[info->nr_ours++] = i;
328                 } else
329                         info->theirs[info->nr_theirs++] = i;
330         }
331 }
332
333 void clear_shallow_info(struct shallow_info *info)
334 {
335         free(info->ours);
336         free(info->theirs);
337 }
338
339 /* Step 4, remove non-existent ones in "theirs" after getting the pack */
340
341 void remove_nonexistent_theirs_shallow(struct shallow_info *info)
342 {
343         unsigned char (*sha1)[20] = info->shallow->sha1;
344         int i, dst;
345         trace_printf_key(&trace_shallow, "shallow: remove_nonexistent_theirs_shallow\n");
346         for (i = dst = 0; i < info->nr_theirs; i++) {
347                 if (i != dst)
348                         info->theirs[dst] = info->theirs[i];
349                 if (has_sha1_file(sha1[info->theirs[i]]))
350                         dst++;
351         }
352         info->nr_theirs = dst;
353 }
354
355 define_commit_slab(ref_bitmap, uint32_t *);
356
357 struct paint_info {
358         struct ref_bitmap ref_bitmap;
359         unsigned nr_bits;
360         char **slab;
361         char *free, *end;
362         unsigned slab_count;
363 };
364
365 static uint32_t *paint_alloc(struct paint_info *info)
366 {
367         unsigned nr = (info->nr_bits + 31) / 32;
368         unsigned size = nr * sizeof(uint32_t);
369         void *p;
370         if (!info->slab_count || info->free + size > info->end) {
371                 info->slab_count++;
372                 REALLOC_ARRAY(info->slab, info->slab_count);
373                 info->free = xmalloc(COMMIT_SLAB_SIZE);
374                 info->slab[info->slab_count - 1] = info->free;
375                 info->end = info->free + COMMIT_SLAB_SIZE;
376         }
377         p = info->free;
378         info->free += size;
379         return p;
380 }
381
382 /*
383  * Given a commit SHA-1, walk down to parents until either SEEN,
384  * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
385  * all walked commits.
386  */
387 static void paint_down(struct paint_info *info, const unsigned char *sha1,
388                        int id)
389 {
390         unsigned int i, nr;
391         struct commit_list *head = NULL;
392         int bitmap_nr = (info->nr_bits + 31) / 32;
393         int bitmap_size = bitmap_nr * sizeof(uint32_t);
394         uint32_t *tmp = xmalloc(bitmap_size); /* to be freed before return */
395         uint32_t *bitmap = paint_alloc(info);
396         struct commit *c = lookup_commit_reference_gently(sha1, 1);
397         if (!c)
398                 return;
399         memset(bitmap, 0, bitmap_size);
400         bitmap[id / 32] |= (1 << (id % 32));
401         commit_list_insert(c, &head);
402         while (head) {
403                 struct commit_list *p;
404                 struct commit *c = head->item;
405                 uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
406
407                 p = head;
408                 head = head->next;
409                 free(p);
410
411                 /* XXX check "UNINTERESTING" from pack bitmaps if available */
412                 if (c->object.flags & (SEEN | UNINTERESTING))
413                         continue;
414                 else
415                         c->object.flags |= SEEN;
416
417                 if (*refs == NULL)
418                         *refs = bitmap;
419                 else {
420                         memcpy(tmp, *refs, bitmap_size);
421                         for (i = 0; i < bitmap_nr; i++)
422                                 tmp[i] |= bitmap[i];
423                         if (memcmp(tmp, *refs, bitmap_size)) {
424                                 *refs = paint_alloc(info);
425                                 memcpy(*refs, tmp, bitmap_size);
426                         }
427                 }
428
429                 if (c->object.flags & BOTTOM)
430                         continue;
431
432                 if (parse_commit(c))
433                         die("unable to parse commit %s",
434                             sha1_to_hex(c->object.sha1));
435
436                 for (p = c->parents; p; p = p->next) {
437                         uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,
438                                                           p->item);
439                         if (p->item->object.flags & SEEN)
440                                 continue;
441                         if (*p_refs == NULL || *p_refs == *refs)
442                                 *p_refs = *refs;
443                         commit_list_insert(p->item, &head);
444                 }
445         }
446
447         nr = get_max_object_index();
448         for (i = 0; i < nr; i++) {
449                 struct object *o = get_indexed_object(i);
450                 if (o && o->type == OBJ_COMMIT)
451                         o->flags &= ~SEEN;
452         }
453
454         free(tmp);
455 }
456
457 static int mark_uninteresting(const char *refname, const struct object_id *oid,
458                               int flags, void *cb_data)
459 {
460         struct commit *commit = lookup_commit_reference_gently(oid->hash, 1);
461         if (!commit)
462                 return 0;
463         commit->object.flags |= UNINTERESTING;
464         mark_parents_uninteresting(commit);
465         return 0;
466 }
467
468 static void post_assign_shallow(struct shallow_info *info,
469                                 struct ref_bitmap *ref_bitmap,
470                                 int *ref_status);
471 /*
472  * Step 6(+7), associate shallow commits with new refs
473  *
474  * info->ref must be initialized before calling this function.
475  *
476  * If used is not NULL, it's an array of info->shallow->nr
477  * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
478  * m-th shallow commit from info->shallow.
479  *
480  * If used is NULL, "ours" and "theirs" are updated. And if ref_status
481  * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
482  * the ref needs some shallow commits from either info->ours or
483  * info->theirs.
484  */
485 void assign_shallow_commits_to_refs(struct shallow_info *info,
486                                     uint32_t **used, int *ref_status)
487 {
488         unsigned char (*sha1)[20] = info->shallow->sha1;
489         struct sha1_array *ref = info->ref;
490         unsigned int i, nr;
491         int *shallow, nr_shallow = 0;
492         struct paint_info pi;
493
494         trace_printf_key(&trace_shallow, "shallow: assign_shallow_commits_to_refs\n");
495         shallow = xmalloc(sizeof(*shallow) * (info->nr_ours + info->nr_theirs));
496         for (i = 0; i < info->nr_ours; i++)
497                 shallow[nr_shallow++] = info->ours[i];
498         for (i = 0; i < info->nr_theirs; i++)
499                 shallow[nr_shallow++] = info->theirs[i];
500
501         /*
502          * Prepare the commit graph to track what refs can reach what
503          * (new) shallow commits.
504          */
505         nr = get_max_object_index();
506         for (i = 0; i < nr; i++) {
507                 struct object *o = get_indexed_object(i);
508                 if (!o || o->type != OBJ_COMMIT)
509                         continue;
510
511                 o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
512         }
513
514         memset(&pi, 0, sizeof(pi));
515         init_ref_bitmap(&pi.ref_bitmap);
516         pi.nr_bits = ref->nr;
517
518         /*
519          * "--not --all" to cut short the traversal if new refs
520          * connect to old refs. If not (e.g. force ref updates) it'll
521          * have to go down to the current shallow commits.
522          */
523         head_ref(mark_uninteresting, NULL);
524         for_each_ref(mark_uninteresting, NULL);
525
526         /* Mark potential bottoms so we won't go out of bound */
527         for (i = 0; i < nr_shallow; i++) {
528                 struct commit *c = lookup_commit(sha1[shallow[i]]);
529                 c->object.flags |= BOTTOM;
530         }
531
532         for (i = 0; i < ref->nr; i++)
533                 paint_down(&pi, ref->sha1[i], i);
534
535         if (used) {
536                 int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
537                 memset(used, 0, sizeof(*used) * info->shallow->nr);
538                 for (i = 0; i < nr_shallow; i++) {
539                         const struct commit *c = lookup_commit(sha1[shallow[i]]);
540                         uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
541                         if (*map)
542                                 used[shallow[i]] = xmemdupz(*map, bitmap_size);
543                 }
544                 /*
545                  * unreachable shallow commits are not removed from
546                  * "ours" and "theirs". The user is supposed to run
547                  * step 7 on every ref separately and not trust "ours"
548                  * and "theirs" any more.
549                  */
550         } else
551                 post_assign_shallow(info, &pi.ref_bitmap, ref_status);
552
553         clear_ref_bitmap(&pi.ref_bitmap);
554         for (i = 0; i < pi.slab_count; i++)
555                 free(pi.slab[i]);
556         free(pi.slab);
557         free(shallow);
558 }
559
560 struct commit_array {
561         struct commit **commits;
562         int nr, alloc;
563 };
564
565 static int add_ref(const char *refname, const struct object_id *oid,
566                    int flags, void *cb_data)
567 {
568         struct commit_array *ca = cb_data;
569         ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
570         ca->commits[ca->nr] = lookup_commit_reference_gently(oid->hash, 1);
571         if (ca->commits[ca->nr])
572                 ca->nr++;
573         return 0;
574 }
575
576 static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
577 {
578         int i;
579         if (!ref_status)
580                 return;
581         for (i = 0; i < nr; i++)
582                 if (bitmap[i / 32] & (1 << (i % 32)))
583                         ref_status[i]++;
584 }
585
586 /*
587  * Step 7, reachability test on "ours" at commit level
588  */
589 static void post_assign_shallow(struct shallow_info *info,
590                                 struct ref_bitmap *ref_bitmap,
591                                 int *ref_status)
592 {
593         unsigned char (*sha1)[20] = info->shallow->sha1;
594         struct commit *c;
595         uint32_t **bitmap;
596         int dst, i, j;
597         int bitmap_nr = (info->ref->nr + 31) / 32;
598         struct commit_array ca;
599
600         trace_printf_key(&trace_shallow, "shallow: post_assign_shallow\n");
601         if (ref_status)
602                 memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
603
604         /* Remove unreachable shallow commits from "theirs" */
605         for (i = dst = 0; i < info->nr_theirs; i++) {
606                 if (i != dst)
607                         info->theirs[dst] = info->theirs[i];
608                 c = lookup_commit(sha1[info->theirs[i]]);
609                 bitmap = ref_bitmap_at(ref_bitmap, c);
610                 if (!*bitmap)
611                         continue;
612                 for (j = 0; j < bitmap_nr; j++)
613                         if (bitmap[0][j]) {
614                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
615                                 dst++;
616                                 break;
617                         }
618         }
619         info->nr_theirs = dst;
620
621         memset(&ca, 0, sizeof(ca));
622         head_ref(add_ref, &ca);
623         for_each_ref(add_ref, &ca);
624
625         /* Remove unreachable shallow commits from "ours" */
626         for (i = dst = 0; i < info->nr_ours; i++) {
627                 if (i != dst)
628                         info->ours[dst] = info->ours[i];
629                 c = lookup_commit(sha1[info->ours[i]]);
630                 bitmap = ref_bitmap_at(ref_bitmap, c);
631                 if (!*bitmap)
632                         continue;
633                 for (j = 0; j < bitmap_nr; j++)
634                         if (bitmap[0][j] &&
635                             /* Step 7, reachability test at commit level */
636                             !in_merge_bases_many(c, ca.nr, ca.commits)) {
637                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
638                                 dst++;
639                                 break;
640                         }
641         }
642         info->nr_ours = dst;
643
644         free(ca.commits);
645 }
646
647 /* (Delayed) step 7, reachability test at commit level */
648 int delayed_reachability_test(struct shallow_info *si, int c)
649 {
650         if (si->need_reachability_test[c]) {
651                 struct commit *commit = lookup_commit(si->shallow->sha1[c]);
652
653                 if (!si->commits) {
654                         struct commit_array ca;
655
656                         memset(&ca, 0, sizeof(ca));
657                         head_ref(add_ref, &ca);
658                         for_each_ref(add_ref, &ca);
659                         si->commits = ca.commits;
660                         si->nr_commits = ca.nr;
661                 }
662
663                 si->reachable[c] = in_merge_bases_many(commit,
664                                                        si->nr_commits,
665                                                        si->commits);
666                 si->need_reachability_test[c] = 0;
667         }
668         return si->reachable[c];
669 }