2 * GIT - The information manager from hell
4 * Copyright (C) Linus Torvalds, 2005
12 #include "tree-walk.h"
13 #include "cache-tree.h"
20 static int update
= 0;
21 static int index_only
= 0;
22 static int nontrivial_merge
= 0;
23 static int trivial_merges_only
= 0;
24 static int aggressive
= 0;
25 static int verbose_update
= 0;
26 static volatile int progress_update
= 0;
28 static int head_idx
= -1;
29 static int merge_size
= 0;
31 static struct object_list
*trees
= NULL
;
33 static struct cache_entry df_conflict_entry
= {
36 struct tree_entry_list
{
37 struct tree_entry_list
*next
;
38 unsigned directory
: 1;
39 unsigned executable
: 1;
43 const unsigned char *sha1
;
46 static struct tree_entry_list df_conflict_list
= {
48 .next
= &df_conflict_list
51 typedef int (*merge_fn_t
)(struct cache_entry
**src
);
53 static struct tree_entry_list
*create_tree_entry_list(struct tree
*tree
)
55 struct tree_desc desc
;
56 struct tree_entry_list
*ret
= NULL
;
57 struct tree_entry_list
**list_p
= &ret
;
59 desc
.buf
= tree
->buffer
;
60 desc
.size
= tree
->size
;
65 const unsigned char *sha1
;
66 struct tree_entry_list
*entry
;
68 sha1
= tree_entry_extract(&desc
, &path
, &mode
);
69 update_tree_entry(&desc
);
71 entry
= xmalloc(sizeof(struct tree_entry_list
));
75 entry
->directory
= S_ISDIR(mode
) != 0;
76 entry
->executable
= (mode
& S_IXUSR
) != 0;
77 entry
->symlink
= S_ISLNK(mode
) != 0;
81 list_p
= &entry
->next
;
86 static int entcmp(const char *name1
, int dir1
, const char *name2
, int dir2
)
88 int len1
= strlen(name1
);
89 int len2
= strlen(name2
);
90 int len
= len1
< len2
? len1
: len2
;
91 int ret
= memcmp(name1
, name2
, len
);
101 ret
= (c1
< c2
) ? -1 : (c1
> c2
) ? 1 : 0;
102 if (c1
&& c2
&& !ret
)
107 static int unpack_trees_rec(struct tree_entry_list
**posns
, int len
,
108 const char *base
, merge_fn_t fn
, int *indpos
)
110 int baselen
= strlen(base
);
111 int src_size
= len
+ 1;
118 struct tree_entry_list
**subposns
;
119 struct cache_entry
**src
;
125 /* Find the first name in the input. */
130 /* Check the cache */
131 if (merge
&& *indpos
< active_nr
) {
132 /* This is a bit tricky: */
133 /* If the index has a subdirectory (with
134 * contents) as the first name, it'll get a
135 * filename like "foo/bar". But that's after
136 * "foo", so the entry in trees will get
137 * handled first, at which point we'll go into
138 * "foo", and deal with "bar" from the index,
139 * because the base will be "foo/". The only
140 * way we can actually have "foo/bar" first of
141 * all the things is if the trees don't
142 * contain "foo" at all, in which case we'll
143 * handle "foo/bar" without going into the
144 * directory, but that's fine (and will return
145 * an error anyway, with the added unknown
149 cache_name
= active_cache
[*indpos
]->name
;
150 if (strlen(cache_name
) > baselen
&&
151 !memcmp(cache_name
, base
, baselen
)) {
152 cache_name
+= baselen
;
161 printf("index %s\n", first
);
163 for (i
= 0; i
< len
; i
++) {
164 if (!posns
[i
] || posns
[i
] == &df_conflict_list
)
167 printf("%d %s\n", i
+ 1, posns
[i
]->name
);
169 if (!first
|| entcmp(first
, firstdir
,
171 posns
[i
]->directory
) > 0) {
172 first
= posns
[i
]->name
;
173 firstdir
= posns
[i
]->directory
;
176 /* No name means we're done */
180 pathlen
= strlen(first
);
181 ce_size
= cache_entry_size(baselen
+ pathlen
);
183 src
= xcalloc(src_size
, sizeof(struct cache_entry
*));
185 subposns
= xcalloc(len
, sizeof(struct tree_list_entry
*));
187 if (cache_name
&& !strcmp(cache_name
, first
)) {
189 src
[0] = active_cache
[*indpos
];
190 remove_cache_entry_at(*indpos
);
193 for (i
= 0; i
< len
; i
++) {
194 struct cache_entry
*ce
;
197 (posns
[i
] != &df_conflict_list
&&
198 strcmp(first
, posns
[i
]->name
))) {
202 if (posns
[i
] == &df_conflict_list
) {
203 src
[i
+ merge
] = &df_conflict_entry
;
207 if (posns
[i
]->directory
) {
208 struct tree
*tree
= lookup_tree(posns
[i
]->sha1
);
211 subposns
[i
] = create_tree_entry_list(tree
);
212 posns
[i
] = posns
[i
]->next
;
213 src
[i
+ merge
] = &df_conflict_entry
;
219 else if (i
+ 1 < head_idx
)
221 else if (i
+ 1 > head_idx
)
226 ce
= xcalloc(1, ce_size
);
227 ce
->ce_mode
= create_ce_mode(posns
[i
]->mode
);
228 ce
->ce_flags
= create_ce_flags(baselen
+ pathlen
,
230 memcpy(ce
->name
, base
, baselen
);
231 memcpy(ce
->name
+ baselen
, first
, pathlen
+ 1);
235 memcpy(ce
->sha1
, posns
[i
]->sha1
, 20);
237 subposns
[i
] = &df_conflict_list
;
238 posns
[i
] = posns
[i
]->next
;
245 printf("%s:\n", first
);
246 for (i
= 0; i
< src_size
; i
++) {
249 printf("%s\n", sha1_to_hex(src
[i
]->sha1
));
257 printf("Added %d entries\n", ret
);
261 for (i
= 0; i
< src_size
; i
++) {
263 add_cache_entry(src
[i
], ADD_CACHE_OK_TO_ADD
|ADD_CACHE_SKIP_DFCHECK
);
269 char *newbase
= xmalloc(baselen
+ 2 + pathlen
);
270 memcpy(newbase
, base
, baselen
);
271 memcpy(newbase
+ baselen
, first
, pathlen
);
272 newbase
[baselen
+ pathlen
] = '/';
273 newbase
[baselen
+ pathlen
+ 1] = '\0';
274 if (unpack_trees_rec(subposns
, len
, newbase
, fn
,
284 static void reject_merge(struct cache_entry
*ce
)
286 die("Entry '%s' would be overwritten by merge. Cannot merge.",
290 /* Unlink the last component and attempt to remove leading
291 * directories, in case this unlink is the removal of the
292 * last entry in the directory -- empty directories are removed.
294 static void unlink_entry(char *name
)
303 cp
= strrchr(name
, '/');
310 status
= rmdir(name
);
319 static void progress_interval(int signum
)
324 static void setup_progress_signal(void)
329 memset(&sa
, 0, sizeof(sa
));
330 sa
.sa_handler
= progress_interval
;
331 sigemptyset(&sa
.sa_mask
);
332 sa
.sa_flags
= SA_RESTART
;
333 sigaction(SIGALRM
, &sa
, NULL
);
335 v
.it_interval
.tv_sec
= 1;
336 v
.it_interval
.tv_usec
= 0;
337 v
.it_value
= v
.it_interval
;
338 setitimer(ITIMER_REAL
, &v
, NULL
);
341 static void check_updates(struct cache_entry
**src
, int nr
)
343 static struct checkout state
= {
349 unsigned short mask
= htons(CE_UPDATE
);
350 unsigned last_percent
= 200, cnt
= 0, total
= 0;
352 if (update
&& verbose_update
) {
353 for (total
= cnt
= 0; cnt
< nr
; cnt
++) {
354 struct cache_entry
*ce
= src
[cnt
];
355 if (!ce
->ce_mode
|| ce
->ce_flags
& mask
)
359 /* Don't bother doing this for very small updates */
364 fprintf(stderr
, "Checking files out...\n");
365 setup_progress_signal();
372 struct cache_entry
*ce
= *src
++;
375 if (!ce
->ce_mode
|| ce
->ce_flags
& mask
) {
378 percent
= (cnt
* 100) / total
;
379 if (percent
!= last_percent
||
381 fprintf(stderr
, "%4u%% (%u/%u) done\r",
382 percent
, cnt
, total
);
383 last_percent
= percent
;
389 unlink_entry(ce
->name
);
392 if (ce
->ce_flags
& mask
) {
393 ce
->ce_flags
&= ~mask
;
395 checkout_entry(ce
, &state
, NULL
);
399 signal(SIGALRM
, SIG_IGN
);
404 static int unpack_trees(merge_fn_t fn
)
407 unsigned len
= object_list_length(trees
);
408 struct tree_entry_list
**posns
;
410 struct object_list
*posn
= trees
;
414 posns
= xmalloc(len
* sizeof(struct tree_entry_list
*));
415 for (i
= 0; i
< len
; i
++) {
416 posns
[i
] = create_tree_entry_list((struct tree
*) posn
->item
);
419 if (unpack_trees_rec(posns
, len
, "", fn
, &indpos
))
423 if (trivial_merges_only
&& nontrivial_merge
)
424 die("Merge requires file-level merging");
426 check_updates(active_cache
, active_nr
);
430 static int list_tree(unsigned char *sha1
)
432 struct tree
*tree
= parse_tree_indirect(sha1
);
435 object_list_append(&tree
->object
, &trees
);
439 static int same(struct cache_entry
*a
, struct cache_entry
*b
)
445 return a
->ce_mode
== b
->ce_mode
&&
446 !memcmp(a
->sha1
, b
->sha1
, 20);
451 * When a CE gets turned into an unmerged entry, we
452 * want it to be up-to-date
454 static void verify_uptodate(struct cache_entry
*ce
)
458 if (index_only
|| reset
)
461 if (!lstat(ce
->name
, &st
)) {
462 unsigned changed
= ce_match_stat(ce
, &st
, 1);
468 ce
->ce_flags
|= htons(CE_UPDATE
);
473 die("Entry '%s' not uptodate. Cannot merge.", ce
->name
);
476 static void invalidate_ce_path(struct cache_entry
*ce
)
479 cache_tree_invalidate_path(active_cache_tree
, ce
->name
);
483 * We do not want to remove or overwrite a working tree file that
486 static void verify_absent(const char *path
, const char *action
)
490 if (index_only
|| reset
|| !update
)
492 if (!lstat(path
, &st
))
493 die("Untracked working tree file '%s' "
494 "would be %s by merge.", path
, action
);
497 static int merged_entry(struct cache_entry
*merge
, struct cache_entry
*old
)
499 merge
->ce_flags
|= htons(CE_UPDATE
);
502 * See if we can re-use the old CE directly?
503 * That way we get the uptodate stat info.
505 * This also removes the UPDATE flag on
508 if (same(old
, merge
)) {
511 verify_uptodate(old
);
512 invalidate_ce_path(old
);
516 verify_absent(merge
->name
, "overwritten");
517 invalidate_ce_path(merge
);
520 merge
->ce_flags
&= ~htons(CE_STAGEMASK
);
521 add_cache_entry(merge
, ADD_CACHE_OK_TO_ADD
);
525 static int deleted_entry(struct cache_entry
*ce
, struct cache_entry
*old
)
528 verify_uptodate(old
);
530 verify_absent(ce
->name
, "removed");
532 add_cache_entry(ce
, ADD_CACHE_OK_TO_ADD
);
533 invalidate_ce_path(ce
);
537 static int keep_entry(struct cache_entry
*ce
)
539 add_cache_entry(ce
, ADD_CACHE_OK_TO_ADD
);
544 static void show_stage_entry(FILE *o
,
545 const char *label
, const struct cache_entry
*ce
)
548 fprintf(o
, "%s (missing)\n", label
);
550 fprintf(o
, "%s%06o %s %d\t%s\n",
553 sha1_to_hex(ce
->sha1
),
559 static int threeway_merge(struct cache_entry
**stages
)
561 struct cache_entry
*index
;
562 struct cache_entry
*head
;
563 struct cache_entry
*remote
= stages
[head_idx
+ 1];
566 int remote_match
= 0;
567 const char *path
= NULL
;
569 int df_conflict_head
= 0;
570 int df_conflict_remote
= 0;
572 int any_anc_missing
= 0;
573 int no_anc_exists
= 1;
576 for (i
= 1; i
< head_idx
; i
++) {
581 path
= stages
[i
]->name
;
587 head
= stages
[head_idx
];
589 if (head
== &df_conflict_entry
) {
590 df_conflict_head
= 1;
594 if (remote
== &df_conflict_entry
) {
595 df_conflict_remote
= 1;
606 /* First, if there's a #16 situation, note that to prevent #13
609 if (!same(remote
, head
)) {
610 for (i
= 1; i
< head_idx
; i
++) {
611 if (same(stages
[i
], head
)) {
614 if (same(stages
[i
], remote
)) {
620 /* We start with cases where the index is allowed to match
621 * something other than the head: #14(ALT) and #2ALT, where it
622 * is permitted to match the result instead.
624 /* #14, #14ALT, #2ALT */
625 if (remote
&& !df_conflict_head
&& head_match
&& !remote_match
) {
626 if (index
&& !same(index
, remote
) && !same(index
, head
))
628 return merged_entry(remote
, index
);
631 * If we have an entry in the index cache, then we want to
632 * make sure that it matches head.
634 if (index
&& !same(index
, head
)) {
640 if (same(head
, remote
))
641 return merged_entry(head
, index
);
643 if (!df_conflict_remote
&& remote_match
&& !head_match
)
644 return merged_entry(head
, index
);
648 if (!head
&& !remote
&& any_anc_missing
)
651 /* Under the new "aggressive" rule, we resolve mostly trivial
652 * cases that we historically had git-merge-one-file resolve.
655 int head_deleted
= !head
&& !df_conflict_head
;
656 int remote_deleted
= !remote
&& !df_conflict_remote
;
659 * Deleted in one and unchanged in the other.
661 if ((head_deleted
&& remote_deleted
) ||
662 (head_deleted
&& remote
&& remote_match
) ||
663 (remote_deleted
&& head
&& head_match
)) {
665 return deleted_entry(index
, index
);
667 verify_absent(path
, "removed");
671 * Added in both, identically.
673 if (no_anc_exists
&& head
&& remote
&& same(head
, remote
))
674 return merged_entry(head
, index
);
678 /* Below are "no merge" cases, which require that the index be
679 * up-to-date to avoid the files getting overwritten with
680 * conflict resolution files.
683 verify_uptodate(index
);
686 verify_absent(path
, "overwritten");
688 nontrivial_merge
= 1;
690 /* #2, #3, #4, #6, #7, #9, #11. */
692 if (!head_match
|| !remote_match
) {
693 for (i
= 1; i
< head_idx
; i
++) {
695 keep_entry(stages
[i
]);
703 fprintf(stderr
, "read-tree: warning #16 detected\n");
704 show_stage_entry(stderr
, "head ", stages
[head_match
]);
705 show_stage_entry(stderr
, "remote ", stages
[remote_match
]);
708 if (head
) { count
+= keep_entry(head
); }
709 if (remote
) { count
+= keep_entry(remote
); }
716 * The rule is to "carry forward" what is in the index without losing
717 * information across a "fast forward", favoring a successful merge
718 * over a merge failure when it makes sense. For details of the
719 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
722 static int twoway_merge(struct cache_entry
**src
)
724 struct cache_entry
*current
= src
[0];
725 struct cache_entry
*oldtree
= src
[1], *newtree
= src
[2];
728 return error("Cannot do a twoway merge of %d trees",
732 if ((!oldtree
&& !newtree
) || /* 4 and 5 */
733 (!oldtree
&& newtree
&&
734 same(current
, newtree
)) || /* 6 and 7 */
735 (oldtree
&& newtree
&&
736 same(oldtree
, newtree
)) || /* 14 and 15 */
737 (oldtree
&& newtree
&&
738 !same(oldtree
, newtree
) && /* 18 and 19*/
739 same(current
, newtree
))) {
740 return keep_entry(current
);
742 else if (oldtree
&& !newtree
&& same(current
, oldtree
)) {
744 return deleted_entry(oldtree
, current
);
746 else if (oldtree
&& newtree
&&
747 same(current
, oldtree
) && !same(current
, newtree
)) {
749 return merged_entry(newtree
, current
);
752 /* all other failures */
754 reject_merge(oldtree
);
756 reject_merge(current
);
758 reject_merge(newtree
);
763 return merged_entry(newtree
, current
);
765 return deleted_entry(oldtree
, current
);
772 * - take the stat information from stage0, take the data from stage1
774 static int oneway_merge(struct cache_entry
**src
)
776 struct cache_entry
*old
= src
[0];
777 struct cache_entry
*a
= src
[1];
780 return error("Cannot do a oneway merge of %d trees",
784 return deleted_entry(old
, old
);
785 if (old
&& same(old
, a
)) {
788 if (lstat(old
->name
, &st
) ||
789 ce_match_stat(old
, &st
, 1))
790 old
->ce_flags
|= htons(CE_UPDATE
);
792 return keep_entry(old
);
794 return merged_entry(a
, old
);
797 static int read_cache_unmerged(void)
800 struct cache_entry
**dst
;
805 for (i
= 0; i
< active_nr
; i
++) {
806 struct cache_entry
*ce
= active_cache
[i
];
809 invalidate_ce_path(ce
);
816 active_nr
-= deleted
;
820 static void prime_cache_tree_rec(struct cache_tree
*it
, struct tree
*tree
)
822 struct tree_desc desc
;
825 memcpy(it
->sha1
, tree
->object
.sha1
, 20);
826 desc
.buf
= tree
->buffer
;
827 desc
.size
= tree
->size
;
832 const unsigned char *sha1
;
834 sha1
= tree_entry_extract(&desc
, &name
, &mode
);
835 update_tree_entry(&desc
);
839 struct cache_tree_sub
*sub
;
840 struct tree
*subtree
= lookup_tree(sha1
);
841 if (!subtree
->object
.parsed
)
843 sub
= cache_tree_sub(it
, name
);
844 sub
->cache_tree
= cache_tree();
845 prime_cache_tree_rec(sub
->cache_tree
, subtree
);
846 cnt
+= sub
->cache_tree
->entry_count
;
849 it
->entry_count
= cnt
;
852 static void prime_cache_tree(void)
854 struct tree
*tree
= (struct tree
*)trees
->item
;
857 active_cache_tree
= cache_tree();
858 prime_cache_tree_rec(active_cache_tree
, tree
);
862 static const char read_tree_usage
[] = "git-read-tree (<sha> | -m [--aggressive] [-u | -i] <sha1> [<sha2> [<sha3>]])";
864 static struct cache_file cache_file
;
866 int cmd_read_tree(int argc
, const char **argv
, char **envp
)
868 int i
, newfd
, stage
= 0;
869 unsigned char sha1
[20];
870 merge_fn_t fn
= NULL
;
872 setup_git_directory();
873 git_config(git_default_config
);
875 newfd
= hold_index_file_for_update(&cache_file
, get_index_file());
877 die("unable to create new cachefile");
879 git_config(git_default_config
);
883 for (i
= 1; i
< argc
; i
++) {
884 const char *arg
= argv
[i
];
886 /* "-u" means "update", meaning that a merge will update
889 if (!strcmp(arg
, "-u")) {
894 if (!strcmp(arg
, "-v")) {
899 /* "-i" means "index only", meaning that a merge will
900 * not even look at the working tree.
902 if (!strcmp(arg
, "-i")) {
907 /* This differs from "-m" in that we'll silently ignore unmerged entries */
908 if (!strcmp(arg
, "--reset")) {
910 usage(read_tree_usage
);
914 read_cache_unmerged();
918 if (!strcmp(arg
, "--trivial")) {
919 trivial_merges_only
= 1;
923 if (!strcmp(arg
, "--aggressive")) {
928 /* "-m" stands for "merge", meaning we start in stage 1 */
929 if (!strcmp(arg
, "-m")) {
931 usage(read_tree_usage
);
932 if (read_cache_unmerged())
933 die("you need to resolve your current index first");
939 /* using -u and -i at the same time makes no sense */
940 if (1 < index_only
+ update
)
941 usage(read_tree_usage
);
943 if (get_sha1(arg
, sha1
))
944 die("Not a valid object name %s", arg
);
945 if (list_tree(sha1
) < 0)
946 die("failed to unpack tree object %s", arg
);
949 if ((update
||index_only
) && !merge
)
950 usage(read_tree_usage
);
954 die("just how do you expect me to merge %d trees?", stage
-1);
965 cache_tree_free(&active_cache_tree
);
970 head_idx
= stage
- 2;
978 * When reading only one tree (either the most basic form,
979 * "-m ent" or "--reset ent" form), we can obtain a fully
980 * valid cache-tree because the index must match exactly
981 * what came from the tree.
983 if (trees
&& trees
->item
&& (!merge
|| (stage
== 2))) {
984 cache_tree_free(&active_cache_tree
);
988 if (write_cache(newfd
, active_cache
, active_nr
) ||
989 commit_index_file(&cache_file
))
990 die("unable to write new index file");