Replace xmalloc+memset(0) with xcalloc.
[git] / read-tree.c
1 /*
2  * GIT - The information manager from hell
3  *
4  * Copyright (C) Linus Torvalds, 2005
5  */
6 #define DBRT_DEBUG 1
7
8 #include "cache.h"
9
10 #include "object.h"
11 #include "tree.h"
12 #include <sys/time.h>
13 #include <signal.h>
14
15 static int merge = 0;
16 static int update = 0;
17 static int index_only = 0;
18 static int nontrivial_merge = 0;
19 static int trivial_merges_only = 0;
20 static int aggressive = 0;
21 static int verbose_update = 0;
22 static volatile int progress_update = 0;
23
24 static int head_idx = -1;
25 static int merge_size = 0;
26
27 static struct object_list *trees = NULL;
28
29 static struct cache_entry df_conflict_entry = { 
30 };
31
32 static struct tree_entry_list df_conflict_list = {
33         .name = NULL,
34         .next = &df_conflict_list
35 };
36
37 typedef int (*merge_fn_t)(struct cache_entry **src);
38
39 static int entcmp(char *name1, int dir1, char *name2, int dir2)
40 {
41         int len1 = strlen(name1);
42         int len2 = strlen(name2);
43         int len = len1 < len2 ? len1 : len2;
44         int ret = memcmp(name1, name2, len);
45         unsigned char c1, c2;
46         if (ret)
47                 return ret;
48         c1 = name1[len];
49         c2 = name2[len];
50         if (!c1 && dir1)
51                 c1 = '/';
52         if (!c2 && dir2)
53                 c2 = '/';
54         ret = (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0;
55         if (c1 && c2 && !ret)
56                 ret = len1 - len2;
57         return ret;
58 }
59
60 static int unpack_trees_rec(struct tree_entry_list **posns, int len,
61                             const char *base, merge_fn_t fn, int *indpos)
62 {
63         int baselen = strlen(base);
64         int src_size = len + 1;
65         do {
66                 int i;
67                 char *first;
68                 int firstdir = 0;
69                 int pathlen;
70                 unsigned ce_size;
71                 struct tree_entry_list **subposns;
72                 struct cache_entry **src;
73                 int any_files = 0;
74                 int any_dirs = 0;
75                 char *cache_name;
76                 int ce_stage;
77
78                 /* Find the first name in the input. */
79
80                 first = NULL;
81                 cache_name = NULL;
82
83                 /* Check the cache */
84                 if (merge && *indpos < active_nr) {
85                         /* This is a bit tricky: */
86                         /* If the index has a subdirectory (with
87                          * contents) as the first name, it'll get a
88                          * filename like "foo/bar". But that's after
89                          * "foo", so the entry in trees will get
90                          * handled first, at which point we'll go into
91                          * "foo", and deal with "bar" from the index,
92                          * because the base will be "foo/". The only
93                          * way we can actually have "foo/bar" first of
94                          * all the things is if the trees don't
95                          * contain "foo" at all, in which case we'll
96                          * handle "foo/bar" without going into the
97                          * directory, but that's fine (and will return
98                          * an error anyway, with the added unknown
99                          * file case.
100                          */
101
102                         cache_name = active_cache[*indpos]->name;
103                         if (strlen(cache_name) > baselen &&
104                             !memcmp(cache_name, base, baselen)) {
105                                 cache_name += baselen;
106                                 first = cache_name;
107                         } else {
108                                 cache_name = NULL;
109                         }
110                 }
111
112 #if DBRT_DEBUG > 1
113                 if (first)
114                         printf("index %s\n", first);
115 #endif
116                 for (i = 0; i < len; i++) {
117                         if (!posns[i] || posns[i] == &df_conflict_list)
118                                 continue;
119 #if DBRT_DEBUG > 1
120                         printf("%d %s\n", i + 1, posns[i]->name);
121 #endif
122                         if (!first || entcmp(first, firstdir,
123                                              posns[i]->name, 
124                                              posns[i]->directory) > 0) {
125                                 first = posns[i]->name;
126                                 firstdir = posns[i]->directory;
127                         }
128                 }
129                 /* No name means we're done */
130                 if (!first)
131                         return 0;
132
133                 pathlen = strlen(first);
134                 ce_size = cache_entry_size(baselen + pathlen);
135
136                 src = xcalloc(src_size, sizeof(struct cache_entry *));
137
138                 subposns = xcalloc(len, sizeof(struct tree_list_entry *));
139
140                 if (cache_name && !strcmp(cache_name, first)) {
141                         any_files = 1;
142                         src[0] = active_cache[*indpos];
143                         remove_cache_entry_at(*indpos);
144                 }
145
146                 for (i = 0; i < len; i++) {
147                         struct cache_entry *ce;
148
149                         if (!posns[i] ||
150                             (posns[i] != &df_conflict_list &&
151                              strcmp(first, posns[i]->name))) {
152                                 continue;
153                         }
154
155                         if (posns[i] == &df_conflict_list) {
156                                 src[i + merge] = &df_conflict_entry;
157                                 continue;
158                         }
159
160                         if (posns[i]->directory) {
161                                 any_dirs = 1;
162                                 parse_tree(posns[i]->item.tree);
163                                 subposns[i] = posns[i]->item.tree->entries;
164                                 posns[i] = posns[i]->next;
165                                 src[i + merge] = &df_conflict_entry;
166                                 continue;
167                         }
168
169                         if (!merge)
170                                 ce_stage = 0;
171                         else if (i + 1 < head_idx)
172                                 ce_stage = 1;
173                         else if (i + 1 > head_idx)
174                                 ce_stage = 3;
175                         else
176                                 ce_stage = 2;
177
178                         ce = xcalloc(1, ce_size);
179                         ce->ce_mode = create_ce_mode(posns[i]->mode);
180                         ce->ce_flags = create_ce_flags(baselen + pathlen,
181                                                        ce_stage);
182                         memcpy(ce->name, base, baselen);
183                         memcpy(ce->name + baselen, first, pathlen + 1);
184
185                         any_files = 1;
186
187                         memcpy(ce->sha1, posns[i]->item.any->sha1, 20);
188                         src[i + merge] = ce;
189                         subposns[i] = &df_conflict_list;
190                         posns[i] = posns[i]->next;
191                 }
192                 if (any_files) {
193                         if (merge) {
194                                 int ret;
195
196 #if DBRT_DEBUG > 1
197                                 printf("%s:\n", first);
198                                 for (i = 0; i < src_size; i++) {
199                                         printf(" %d ", i);
200                                         if (src[i])
201                                                 printf("%s\n", sha1_to_hex(src[i]->sha1));
202                                         else
203                                                 printf("\n");
204                                 }
205 #endif
206                                 ret = fn(src);
207                                 
208 #if DBRT_DEBUG > 1
209                                 printf("Added %d entries\n", ret);
210 #endif
211                                 *indpos += ret;
212                         } else {
213                                 for (i = 0; i < src_size; i++) {
214                                         if (src[i]) {
215                                                 add_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK);
216                                         }
217                                 }
218                         }
219                 }
220                 if (any_dirs) {
221                         char *newbase = xmalloc(baselen + 2 + pathlen);
222                         memcpy(newbase, base, baselen);
223                         memcpy(newbase + baselen, first, pathlen);
224                         newbase[baselen + pathlen] = '/';
225                         newbase[baselen + pathlen + 1] = '\0';
226                         if (unpack_trees_rec(subposns, len, newbase, fn,
227                                              indpos))
228                                 return -1;
229                         free(newbase);
230                 }
231                 free(subposns);
232                 free(src);
233         } while (1);
234 }
235
236 static void reject_merge(struct cache_entry *ce)
237 {
238         die("Entry '%s' would be overwritten by merge. Cannot merge.", 
239             ce->name);
240 }
241
242 /* Unlink the last component and attempt to remove leading
243  * directories, in case this unlink is the removal of the
244  * last entry in the directory -- empty directories are removed.
245  */
246 static void unlink_entry(char *name)
247 {
248         char *cp, *prev;
249
250         if (unlink(name))
251                 return;
252         prev = NULL;
253         while (1) {
254                 int status;
255                 cp = strrchr(name, '/');
256                 if (prev)
257                         *prev = '/';
258                 if (!cp)
259                         break;
260
261                 *cp = 0;
262                 status = rmdir(name);
263                 if (status) {
264                         *cp = '/';
265                         break;
266                 }
267                 prev = cp;
268         }
269 }
270
271 static void progress_interval(int signum)
272 {
273         signal(SIGALRM, progress_interval);
274         progress_update = 1;
275 }
276
277 static void check_updates(struct cache_entry **src, int nr)
278 {
279         static struct checkout state = {
280                 .base_dir = "",
281                 .force = 1,
282                 .quiet = 1,
283                 .refresh_cache = 1,
284         };
285         unsigned short mask = htons(CE_UPDATE);
286         unsigned last_percent = 200, cnt = 0, total = 0;
287
288         if (update && verbose_update) {
289                 struct itimerval v;
290
291                 for (total = cnt = 0; cnt < nr; cnt++) {
292                         struct cache_entry *ce = src[cnt];
293                         if (!ce->ce_mode || ce->ce_flags & mask)
294                                 total++;
295                 }
296
297                 /* Don't bother doing this for very small updates */
298                 if (total < 250)
299                         total = 0;
300
301                 if (total) {
302                         v.it_interval.tv_sec = 1;
303                         v.it_interval.tv_usec = 0;
304                         v.it_value = v.it_interval;
305                         signal(SIGALRM, progress_interval);
306                         setitimer(ITIMER_REAL, &v, NULL);
307                         fprintf(stderr, "Checking files out...\n");
308                         progress_update = 1;
309                 }
310                 cnt = 0;
311         }
312
313         while (nr--) {
314                 struct cache_entry *ce = *src++;
315
316                 if (total) {
317                         if (!ce->ce_mode || ce->ce_flags & mask) {
318                                 unsigned percent;
319                                 cnt++;
320                                 percent = (cnt * 100) / total;
321                                 if (percent != last_percent ||
322                                     progress_update) {
323                                         fprintf(stderr, "%4u%% (%u/%u) done\r",
324                                                 percent, cnt, total);
325                                         last_percent = percent;
326                                 }
327                         }
328                 }
329                 if (!ce->ce_mode) {
330                         if (update)
331                                 unlink_entry(ce->name);
332                         continue;
333                 }
334                 if (ce->ce_flags & mask) {
335                         ce->ce_flags &= ~mask;
336                         if (update)
337                                 checkout_entry(ce, &state, NULL);
338                 }
339         }
340         if (total) {
341                 fputc('\n', stderr);
342                 signal(SIGALRM, SIG_IGN);
343         }
344 }
345
346 static int unpack_trees(merge_fn_t fn)
347 {
348         int indpos = 0;
349         unsigned len = object_list_length(trees);
350         struct tree_entry_list **posns;
351         int i;
352         struct object_list *posn = trees;
353         merge_size = len;
354
355         if (len) {
356                 posns = xmalloc(len * sizeof(struct tree_entry_list *));
357                 for (i = 0; i < len; i++) {
358                         posns[i] = ((struct tree *) posn->item)->entries;
359                         posn = posn->next;
360                 }
361                 if (unpack_trees_rec(posns, len, "", fn, &indpos))
362                         return -1;
363         }
364
365         if (trivial_merges_only && nontrivial_merge)
366                 die("Merge requires file-level merging");
367
368         check_updates(active_cache, active_nr);
369         return 0;
370 }
371
372 static int list_tree(unsigned char *sha1)
373 {
374         struct tree *tree = parse_tree_indirect(sha1);
375         if (!tree)
376                 return -1;
377         object_list_append(&tree->object, &trees);
378         return 0;
379 }
380
381 static int same(struct cache_entry *a, struct cache_entry *b)
382 {
383         if (!!a != !!b)
384                 return 0;
385         if (!a && !b)
386                 return 1;
387         return a->ce_mode == b->ce_mode && 
388                 !memcmp(a->sha1, b->sha1, 20);
389 }
390
391
392 /*
393  * When a CE gets turned into an unmerged entry, we
394  * want it to be up-to-date
395  */
396 static void verify_uptodate(struct cache_entry *ce)
397 {
398         struct stat st;
399
400         if (index_only)
401                 return;
402
403         if (!lstat(ce->name, &st)) {
404                 unsigned changed = ce_match_stat(ce, &st, 1);
405                 if (!changed)
406                         return;
407                 errno = 0;
408         }
409         if (errno == ENOENT)
410                 return;
411         die("Entry '%s' not uptodate. Cannot merge.", ce->name);
412 }
413
414 static int merged_entry(struct cache_entry *merge, struct cache_entry *old)
415 {
416         merge->ce_flags |= htons(CE_UPDATE);
417         if (old) {
418                 /*
419                  * See if we can re-use the old CE directly?
420                  * That way we get the uptodate stat info.
421                  *
422                  * This also removes the UPDATE flag on
423                  * a match.
424                  */
425                 if (same(old, merge)) {
426                         *merge = *old;
427                 } else {
428                         verify_uptodate(old);
429                 }
430         }
431         merge->ce_flags &= ~htons(CE_STAGEMASK);
432         add_cache_entry(merge, ADD_CACHE_OK_TO_ADD);
433         return 1;
434 }
435
436 static int deleted_entry(struct cache_entry *ce, struct cache_entry *old)
437 {
438         if (old)
439                 verify_uptodate(old);
440         ce->ce_mode = 0;
441         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
442         return 1;
443 }
444
445 static int keep_entry(struct cache_entry *ce)
446 {
447         add_cache_entry(ce, ADD_CACHE_OK_TO_ADD);
448         return 1;
449 }
450
451 #if DBRT_DEBUG
452 static void show_stage_entry(FILE *o,
453                              const char *label, const struct cache_entry *ce)
454 {
455         if (!ce)
456                 fprintf(o, "%s (missing)\n", label);
457         else
458                 fprintf(o, "%s%06o %s %d\t%s\n",
459                         label,
460                         ntohl(ce->ce_mode),
461                         sha1_to_hex(ce->sha1),
462                         ce_stage(ce),
463                         ce->name);
464 }
465 #endif
466
467 static int threeway_merge(struct cache_entry **stages)
468 {
469         struct cache_entry *index;
470         struct cache_entry *head; 
471         struct cache_entry *remote = stages[head_idx + 1];
472         int count;
473         int head_match = 0;
474         int remote_match = 0;
475
476         int df_conflict_head = 0;
477         int df_conflict_remote = 0;
478
479         int any_anc_missing = 0;
480         int no_anc_exists = 1;
481         int i;
482
483         for (i = 1; i < head_idx; i++) {
484                 if (!stages[i])
485                         any_anc_missing = 1;
486                 else
487                         no_anc_exists = 0;
488         }
489
490         index = stages[0];
491         head = stages[head_idx];
492
493         if (head == &df_conflict_entry) {
494                 df_conflict_head = 1;
495                 head = NULL;
496         }
497
498         if (remote == &df_conflict_entry) {
499                 df_conflict_remote = 1;
500                 remote = NULL;
501         }
502
503         /* First, if there's a #16 situation, note that to prevent #13
504          * and #14. 
505          */
506         if (!same(remote, head)) {
507                 for (i = 1; i < head_idx; i++) {
508                         if (same(stages[i], head)) {
509                                 head_match = i;
510                         }
511                         if (same(stages[i], remote)) {
512                                 remote_match = i;
513                         }
514                 }
515         }
516
517         /* We start with cases where the index is allowed to match
518          * something other than the head: #14(ALT) and #2ALT, where it
519          * is permitted to match the result instead.
520          */
521         /* #14, #14ALT, #2ALT */
522         if (remote && !df_conflict_head && head_match && !remote_match) {
523                 if (index && !same(index, remote) && !same(index, head))
524                         reject_merge(index);
525                 return merged_entry(remote, index);
526         }
527         /*
528          * If we have an entry in the index cache, then we want to
529          * make sure that it matches head.
530          */
531         if (index && !same(index, head)) {
532                 reject_merge(index);
533         }
534
535         if (head) {
536                 /* #5ALT, #15 */
537                 if (same(head, remote))
538                         return merged_entry(head, index);
539                 /* #13, #3ALT */
540                 if (!df_conflict_remote && remote_match && !head_match)
541                         return merged_entry(head, index);
542         }
543
544         /* #1 */
545         if (!head && !remote && any_anc_missing)
546                 return 0;
547
548         /* Under the new "aggressive" rule, we resolve mostly trivial
549          * cases that we historically had git-merge-one-file resolve.
550          */
551         if (aggressive) {
552                 int head_deleted = !head && !df_conflict_head;
553                 int remote_deleted = !remote && !df_conflict_remote;
554                 /*
555                  * Deleted in both.
556                  * Deleted in one and unchanged in the other.
557                  */
558                 if ((head_deleted && remote_deleted) ||
559                     (head_deleted && remote && remote_match) ||
560                     (remote_deleted && head && head_match)) {
561                         if (index)
562                                 return deleted_entry(index, index);
563                         return 0;
564                 }
565                 /*
566                  * Added in both, identically.
567                  */
568                 if (no_anc_exists && head && remote && same(head, remote))
569                         return merged_entry(head, index);
570
571         }
572
573         /* Below are "no merge" cases, which require that the index be
574          * up-to-date to avoid the files getting overwritten with
575          * conflict resolution files. 
576          */
577         if (index) {
578                 verify_uptodate(index);
579         }
580
581         nontrivial_merge = 1;
582
583         /* #2, #3, #4, #6, #7, #9, #11. */
584         count = 0;
585         if (!head_match || !remote_match) {
586                 for (i = 1; i < head_idx; i++) {
587                         if (stages[i]) {
588                                 keep_entry(stages[i]);
589                                 count++;
590                                 break;
591                         }
592                 }
593         }
594 #if DBRT_DEBUG
595         else {
596                 fprintf(stderr, "read-tree: warning #16 detected\n");
597                 show_stage_entry(stderr, "head   ", stages[head_match]);
598                 show_stage_entry(stderr, "remote ", stages[remote_match]);
599         }
600 #endif
601         if (head) { count += keep_entry(head); }
602         if (remote) { count += keep_entry(remote); }
603         return count;
604 }
605
606 /*
607  * Two-way merge.
608  *
609  * The rule is to "carry forward" what is in the index without losing
610  * information across a "fast forward", favoring a successful merge
611  * over a merge failure when it makes sense.  For details of the
612  * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
613  *
614  */
615 static int twoway_merge(struct cache_entry **src)
616 {
617         struct cache_entry *current = src[0];
618         struct cache_entry *oldtree = src[1], *newtree = src[2];
619
620         if (merge_size != 2)
621                 return error("Cannot do a twoway merge of %d trees",
622                              merge_size);
623
624         if (current) {
625                 if ((!oldtree && !newtree) || /* 4 and 5 */
626                     (!oldtree && newtree &&
627                      same(current, newtree)) || /* 6 and 7 */
628                     (oldtree && newtree &&
629                      same(oldtree, newtree)) || /* 14 and 15 */
630                     (oldtree && newtree &&
631                      !same(oldtree, newtree) && /* 18 and 19*/
632                      same(current, newtree))) {
633                         return keep_entry(current);
634                 }
635                 else if (oldtree && !newtree && same(current, oldtree)) {
636                         /* 10 or 11 */
637                         return deleted_entry(oldtree, current);
638                 }
639                 else if (oldtree && newtree &&
640                          same(current, oldtree) && !same(current, newtree)) {
641                         /* 20 or 21 */
642                         return merged_entry(newtree, current);
643                 }
644                 else {
645                         /* all other failures */
646                         if (oldtree)
647                                 reject_merge(oldtree);
648                         if (current)
649                                 reject_merge(current);
650                         if (newtree)
651                                 reject_merge(newtree);
652                         return -1;
653                 }
654         }
655         else if (newtree)
656                 return merged_entry(newtree, current);
657         else
658                 return deleted_entry(oldtree, current);
659 }
660
661 /*
662  * One-way merge.
663  *
664  * The rule is:
665  * - take the stat information from stage0, take the data from stage1
666  */
667 static int oneway_merge(struct cache_entry **src)
668 {
669         struct cache_entry *old = src[0];
670         struct cache_entry *a = src[1];
671
672         if (merge_size != 1)
673                 return error("Cannot do a oneway merge of %d trees",
674                              merge_size);
675
676         if (!a)
677                 return 0;
678         if (old && same(old, a)) {
679                 return keep_entry(old);
680         }
681         return merged_entry(a, NULL);
682 }
683
684 static int read_cache_unmerged(void)
685 {
686         int i, deleted;
687         struct cache_entry **dst;
688
689         read_cache();
690         dst = active_cache;
691         deleted = 0;
692         for (i = 0; i < active_nr; i++) {
693                 struct cache_entry *ce = active_cache[i];
694                 if (ce_stage(ce)) {
695                         deleted++;
696                         continue;
697                 }
698                 if (deleted)
699                         *dst = ce;
700                 dst++;
701         }
702         active_nr -= deleted;
703         return deleted;
704 }
705
706 static const char read_tree_usage[] = "git-read-tree (<sha> | -m [--aggressive] [-u | -i] <sha1> [<sha2> [<sha3>]])";
707
708 static struct cache_file cache_file;
709
710 int main(int argc, char **argv)
711 {
712         int i, newfd, reset, stage = 0;
713         unsigned char sha1[20];
714         merge_fn_t fn = NULL;
715
716         setup_git_directory();
717         git_config(git_default_config);
718
719         newfd = hold_index_file_for_update(&cache_file, get_index_file());
720         if (newfd < 0)
721                 die("unable to create new cachefile");
722
723         git_config(git_default_config);
724
725         merge = 0;
726         reset = 0;
727         for (i = 1; i < argc; i++) {
728                 const char *arg = argv[i];
729
730                 /* "-u" means "update", meaning that a merge will update
731                  * the working tree.
732                  */
733                 if (!strcmp(arg, "-u")) {
734                         update = 1;
735                         continue;
736                 }
737
738                 if (!strcmp(arg, "-v")) {
739                         verbose_update = 1;
740                         continue;
741                 }
742
743                 /* "-i" means "index only", meaning that a merge will
744                  * not even look at the working tree.
745                  */
746                 if (!strcmp(arg, "-i")) {
747                         index_only = 1;
748                         continue;
749                 }
750
751                 /* This differs from "-m" in that we'll silently ignore unmerged entries */
752                 if (!strcmp(arg, "--reset")) {
753                         if (stage || merge)
754                                 usage(read_tree_usage);
755                         reset = 1;
756                         merge = 1;
757                         stage = 1;
758                         read_cache_unmerged();
759                         continue;
760                 }
761
762                 if (!strcmp(arg, "--trivial")) {
763                         trivial_merges_only = 1;
764                         continue;
765                 }
766
767                 if (!strcmp(arg, "--aggressive")) {
768                         aggressive = 1;
769                         continue;
770                 }
771
772                 /* "-m" stands for "merge", meaning we start in stage 1 */
773                 if (!strcmp(arg, "-m")) {
774                         if (stage || merge)
775                                 usage(read_tree_usage);
776                         if (read_cache_unmerged())
777                                 die("you need to resolve your current index first");
778                         stage = 1;
779                         merge = 1;
780                         continue;
781                 }
782
783                 /* using -u and -i at the same time makes no sense */
784                 if (1 < index_only + update)
785                         usage(read_tree_usage);
786
787                 if (get_sha1(arg, sha1) < 0)
788                         usage(read_tree_usage);
789                 if (list_tree(sha1) < 0)
790                         die("failed to unpack tree object %s", arg);
791                 stage++;
792         }
793         if ((update||index_only) && !merge)
794                 usage(read_tree_usage);
795
796         if (merge) {
797                 if (stage < 2)
798                         die("just how do you expect me to merge %d trees?", stage-1);
799                 switch (stage - 1) {
800                 case 1:
801                         fn = oneway_merge;
802                         break;
803                 case 2:
804                         fn = twoway_merge;
805                         break;
806                 case 3:
807                         fn = threeway_merge;
808                         break;
809                 default:
810                         fn = threeway_merge;
811                         break;
812                 }
813
814                 if (stage - 1 >= 3)
815                         head_idx = stage - 2;
816                 else
817                         head_idx = 1;
818         }
819
820         unpack_trees(fn);
821         if (write_cache(newfd, active_cache, active_nr) ||
822             commit_index_file(&cache_file))
823                 die("unable to write new index file");
824         return 0;
825 }