Imported Upstream version 2.6.5
[platform/upstream/git.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 = pop_commit(&head);
405                 uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
406
407                 /* XXX check "UNINTERESTING" from pack bitmaps if available */
408                 if (c->object.flags & (SEEN | UNINTERESTING))
409                         continue;
410                 else
411                         c->object.flags |= SEEN;
412
413                 if (*refs == NULL)
414                         *refs = bitmap;
415                 else {
416                         memcpy(tmp, *refs, bitmap_size);
417                         for (i = 0; i < bitmap_nr; i++)
418                                 tmp[i] |= bitmap[i];
419                         if (memcmp(tmp, *refs, bitmap_size)) {
420                                 *refs = paint_alloc(info);
421                                 memcpy(*refs, tmp, bitmap_size);
422                         }
423                 }
424
425                 if (c->object.flags & BOTTOM)
426                         continue;
427
428                 if (parse_commit(c))
429                         die("unable to parse commit %s",
430                             sha1_to_hex(c->object.sha1));
431
432                 for (p = c->parents; p; p = p->next) {
433                         uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,
434                                                           p->item);
435                         if (p->item->object.flags & SEEN)
436                                 continue;
437                         if (*p_refs == NULL || *p_refs == *refs)
438                                 *p_refs = *refs;
439                         commit_list_insert(p->item, &head);
440                 }
441         }
442
443         nr = get_max_object_index();
444         for (i = 0; i < nr; i++) {
445                 struct object *o = get_indexed_object(i);
446                 if (o && o->type == OBJ_COMMIT)
447                         o->flags &= ~SEEN;
448         }
449
450         free(tmp);
451 }
452
453 static int mark_uninteresting(const char *refname, const struct object_id *oid,
454                               int flags, void *cb_data)
455 {
456         struct commit *commit = lookup_commit_reference_gently(oid->hash, 1);
457         if (!commit)
458                 return 0;
459         commit->object.flags |= UNINTERESTING;
460         mark_parents_uninteresting(commit);
461         return 0;
462 }
463
464 static void post_assign_shallow(struct shallow_info *info,
465                                 struct ref_bitmap *ref_bitmap,
466                                 int *ref_status);
467 /*
468  * Step 6(+7), associate shallow commits with new refs
469  *
470  * info->ref must be initialized before calling this function.
471  *
472  * If used is not NULL, it's an array of info->shallow->nr
473  * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
474  * m-th shallow commit from info->shallow.
475  *
476  * If used is NULL, "ours" and "theirs" are updated. And if ref_status
477  * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
478  * the ref needs some shallow commits from either info->ours or
479  * info->theirs.
480  */
481 void assign_shallow_commits_to_refs(struct shallow_info *info,
482                                     uint32_t **used, int *ref_status)
483 {
484         unsigned char (*sha1)[20] = info->shallow->sha1;
485         struct sha1_array *ref = info->ref;
486         unsigned int i, nr;
487         int *shallow, nr_shallow = 0;
488         struct paint_info pi;
489
490         trace_printf_key(&trace_shallow, "shallow: assign_shallow_commits_to_refs\n");
491         shallow = xmalloc(sizeof(*shallow) * (info->nr_ours + info->nr_theirs));
492         for (i = 0; i < info->nr_ours; i++)
493                 shallow[nr_shallow++] = info->ours[i];
494         for (i = 0; i < info->nr_theirs; i++)
495                 shallow[nr_shallow++] = info->theirs[i];
496
497         /*
498          * Prepare the commit graph to track what refs can reach what
499          * (new) shallow commits.
500          */
501         nr = get_max_object_index();
502         for (i = 0; i < nr; i++) {
503                 struct object *o = get_indexed_object(i);
504                 if (!o || o->type != OBJ_COMMIT)
505                         continue;
506
507                 o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
508         }
509
510         memset(&pi, 0, sizeof(pi));
511         init_ref_bitmap(&pi.ref_bitmap);
512         pi.nr_bits = ref->nr;
513
514         /*
515          * "--not --all" to cut short the traversal if new refs
516          * connect to old refs. If not (e.g. force ref updates) it'll
517          * have to go down to the current shallow commits.
518          */
519         head_ref(mark_uninteresting, NULL);
520         for_each_ref(mark_uninteresting, NULL);
521
522         /* Mark potential bottoms so we won't go out of bound */
523         for (i = 0; i < nr_shallow; i++) {
524                 struct commit *c = lookup_commit(sha1[shallow[i]]);
525                 c->object.flags |= BOTTOM;
526         }
527
528         for (i = 0; i < ref->nr; i++)
529                 paint_down(&pi, ref->sha1[i], i);
530
531         if (used) {
532                 int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
533                 memset(used, 0, sizeof(*used) * info->shallow->nr);
534                 for (i = 0; i < nr_shallow; i++) {
535                         const struct commit *c = lookup_commit(sha1[shallow[i]]);
536                         uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
537                         if (*map)
538                                 used[shallow[i]] = xmemdupz(*map, bitmap_size);
539                 }
540                 /*
541                  * unreachable shallow commits are not removed from
542                  * "ours" and "theirs". The user is supposed to run
543                  * step 7 on every ref separately and not trust "ours"
544                  * and "theirs" any more.
545                  */
546         } else
547                 post_assign_shallow(info, &pi.ref_bitmap, ref_status);
548
549         clear_ref_bitmap(&pi.ref_bitmap);
550         for (i = 0; i < pi.slab_count; i++)
551                 free(pi.slab[i]);
552         free(pi.slab);
553         free(shallow);
554 }
555
556 struct commit_array {
557         struct commit **commits;
558         int nr, alloc;
559 };
560
561 static int add_ref(const char *refname, const struct object_id *oid,
562                    int flags, void *cb_data)
563 {
564         struct commit_array *ca = cb_data;
565         ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
566         ca->commits[ca->nr] = lookup_commit_reference_gently(oid->hash, 1);
567         if (ca->commits[ca->nr])
568                 ca->nr++;
569         return 0;
570 }
571
572 static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
573 {
574         int i;
575         if (!ref_status)
576                 return;
577         for (i = 0; i < nr; i++)
578                 if (bitmap[i / 32] & (1 << (i % 32)))
579                         ref_status[i]++;
580 }
581
582 /*
583  * Step 7, reachability test on "ours" at commit level
584  */
585 static void post_assign_shallow(struct shallow_info *info,
586                                 struct ref_bitmap *ref_bitmap,
587                                 int *ref_status)
588 {
589         unsigned char (*sha1)[20] = info->shallow->sha1;
590         struct commit *c;
591         uint32_t **bitmap;
592         int dst, i, j;
593         int bitmap_nr = (info->ref->nr + 31) / 32;
594         struct commit_array ca;
595
596         trace_printf_key(&trace_shallow, "shallow: post_assign_shallow\n");
597         if (ref_status)
598                 memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
599
600         /* Remove unreachable shallow commits from "theirs" */
601         for (i = dst = 0; i < info->nr_theirs; i++) {
602                 if (i != dst)
603                         info->theirs[dst] = info->theirs[i];
604                 c = lookup_commit(sha1[info->theirs[i]]);
605                 bitmap = ref_bitmap_at(ref_bitmap, c);
606                 if (!*bitmap)
607                         continue;
608                 for (j = 0; j < bitmap_nr; j++)
609                         if (bitmap[0][j]) {
610                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
611                                 dst++;
612                                 break;
613                         }
614         }
615         info->nr_theirs = dst;
616
617         memset(&ca, 0, sizeof(ca));
618         head_ref(add_ref, &ca);
619         for_each_ref(add_ref, &ca);
620
621         /* Remove unreachable shallow commits from "ours" */
622         for (i = dst = 0; i < info->nr_ours; i++) {
623                 if (i != dst)
624                         info->ours[dst] = info->ours[i];
625                 c = lookup_commit(sha1[info->ours[i]]);
626                 bitmap = ref_bitmap_at(ref_bitmap, c);
627                 if (!*bitmap)
628                         continue;
629                 for (j = 0; j < bitmap_nr; j++)
630                         if (bitmap[0][j] &&
631                             /* Step 7, reachability test at commit level */
632                             !in_merge_bases_many(c, ca.nr, ca.commits)) {
633                                 update_refstatus(ref_status, info->ref->nr, *bitmap);
634                                 dst++;
635                                 break;
636                         }
637         }
638         info->nr_ours = dst;
639
640         free(ca.commits);
641 }
642
643 /* (Delayed) step 7, reachability test at commit level */
644 int delayed_reachability_test(struct shallow_info *si, int c)
645 {
646         if (si->need_reachability_test[c]) {
647                 struct commit *commit = lookup_commit(si->shallow->sha1[c]);
648
649                 if (!si->commits) {
650                         struct commit_array ca;
651
652                         memset(&ca, 0, sizeof(ca));
653                         head_ref(add_ref, &ca);
654                         for_each_ref(add_ref, &ca);
655                         si->commits = ca.commits;
656                         si->nr_commits = ca.nr;
657                 }
658
659                 si->reachable[c] = in_merge_bases_many(commit,
660                                                        si->nr_commits,
661                                                        si->commits);
662                 si->need_reachability_test[c] = 0;
663         }
664         return si->reachable[c];
665 }