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