2 * GIT - The information manager from hell
4 * Copyright (C) Linus Torvalds, 2005
12 #include "cache-tree.h"
17 static int update
= 0;
18 static int index_only
= 0;
19 static int nontrivial_merge
= 0;
20 static int trivial_merges_only
= 0;
21 static int aggressive
= 0;
22 static int verbose_update
= 0;
23 static volatile int progress_update
= 0;
25 static int head_idx
= -1;
26 static int merge_size
= 0;
28 static struct object_list
*trees
= NULL
;
30 static struct cache_entry df_conflict_entry
= {
33 static struct tree_entry_list df_conflict_list
= {
35 .next
= &df_conflict_list
38 typedef int (*merge_fn_t
)(struct cache_entry
**src
);
40 static int entcmp(char *name1
, int dir1
, char *name2
, int dir2
)
42 int len1
= strlen(name1
);
43 int len2
= strlen(name2
);
44 int len
= len1
< len2
? len1
: len2
;
45 int ret
= memcmp(name1
, name2
, len
);
55 ret
= (c1
< c2
) ? -1 : (c1
> c2
) ? 1 : 0;
61 static int unpack_trees_rec(struct tree_entry_list
**posns
, int len
,
62 const char *base
, merge_fn_t fn
, int *indpos
)
64 int baselen
= strlen(base
);
65 int src_size
= len
+ 1;
72 struct tree_entry_list
**subposns
;
73 struct cache_entry
**src
;
79 /* Find the first name in the input. */
85 if (merge
&& *indpos
< active_nr
) {
86 /* This is a bit tricky: */
87 /* If the index has a subdirectory (with
88 * contents) as the first name, it'll get a
89 * filename like "foo/bar". But that's after
90 * "foo", so the entry in trees will get
91 * handled first, at which point we'll go into
92 * "foo", and deal with "bar" from the index,
93 * because the base will be "foo/". The only
94 * way we can actually have "foo/bar" first of
95 * all the things is if the trees don't
96 * contain "foo" at all, in which case we'll
97 * handle "foo/bar" without going into the
98 * directory, but that's fine (and will return
99 * an error anyway, with the added unknown
103 cache_name
= active_cache
[*indpos
]->name
;
104 if (strlen(cache_name
) > baselen
&&
105 !memcmp(cache_name
, base
, baselen
)) {
106 cache_name
+= baselen
;
115 printf("index %s\n", first
);
117 for (i
= 0; i
< len
; i
++) {
118 if (!posns
[i
] || posns
[i
] == &df_conflict_list
)
121 printf("%d %s\n", i
+ 1, posns
[i
]->name
);
123 if (!first
|| entcmp(first
, firstdir
,
125 posns
[i
]->directory
) > 0) {
126 first
= posns
[i
]->name
;
127 firstdir
= posns
[i
]->directory
;
130 /* No name means we're done */
134 pathlen
= strlen(first
);
135 ce_size
= cache_entry_size(baselen
+ pathlen
);
137 src
= xcalloc(src_size
, sizeof(struct cache_entry
*));
139 subposns
= xcalloc(len
, sizeof(struct tree_list_entry
*));
141 if (cache_name
&& !strcmp(cache_name
, first
)) {
143 src
[0] = active_cache
[*indpos
];
144 remove_cache_entry_at(*indpos
);
147 for (i
= 0; i
< len
; i
++) {
148 struct cache_entry
*ce
;
151 (posns
[i
] != &df_conflict_list
&&
152 strcmp(first
, posns
[i
]->name
))) {
156 if (posns
[i
] == &df_conflict_list
) {
157 src
[i
+ merge
] = &df_conflict_entry
;
161 if (posns
[i
]->directory
) {
163 parse_tree(posns
[i
]->item
.tree
);
164 subposns
[i
] = posns
[i
]->item
.tree
->entries
;
165 posns
[i
] = posns
[i
]->next
;
166 src
[i
+ merge
] = &df_conflict_entry
;
172 else if (i
+ 1 < head_idx
)
174 else if (i
+ 1 > head_idx
)
179 ce
= xcalloc(1, ce_size
);
180 ce
->ce_mode
= create_ce_mode(posns
[i
]->mode
);
181 ce
->ce_flags
= create_ce_flags(baselen
+ pathlen
,
183 memcpy(ce
->name
, base
, baselen
);
184 memcpy(ce
->name
+ baselen
, first
, pathlen
+ 1);
188 memcpy(ce
->sha1
, posns
[i
]->item
.any
->sha1
, 20);
190 subposns
[i
] = &df_conflict_list
;
191 posns
[i
] = posns
[i
]->next
;
198 printf("%s:\n", first
);
199 for (i
= 0; i
< src_size
; i
++) {
202 printf("%s\n", sha1_to_hex(src
[i
]->sha1
));
210 printf("Added %d entries\n", ret
);
214 for (i
= 0; i
< src_size
; i
++) {
216 add_cache_entry(src
[i
], ADD_CACHE_OK_TO_ADD
|ADD_CACHE_SKIP_DFCHECK
);
222 char *newbase
= xmalloc(baselen
+ 2 + pathlen
);
223 memcpy(newbase
, base
, baselen
);
224 memcpy(newbase
+ baselen
, first
, pathlen
);
225 newbase
[baselen
+ pathlen
] = '/';
226 newbase
[baselen
+ pathlen
+ 1] = '\0';
227 if (unpack_trees_rec(subposns
, len
, newbase
, fn
,
237 static void reject_merge(struct cache_entry
*ce
)
239 die("Entry '%s' would be overwritten by merge. Cannot merge.",
243 /* Unlink the last component and attempt to remove leading
244 * directories, in case this unlink is the removal of the
245 * last entry in the directory -- empty directories are removed.
247 static void unlink_entry(char *name
)
256 cp
= strrchr(name
, '/');
263 status
= rmdir(name
);
272 static void progress_interval(int signum
)
277 static void setup_progress_signal(void)
282 memset(&sa
, 0, sizeof(sa
));
283 sa
.sa_handler
= progress_interval
;
284 sigemptyset(&sa
.sa_mask
);
285 sa
.sa_flags
= SA_RESTART
;
286 sigaction(SIGALRM
, &sa
, NULL
);
288 v
.it_interval
.tv_sec
= 1;
289 v
.it_interval
.tv_usec
= 0;
290 v
.it_value
= v
.it_interval
;
291 setitimer(ITIMER_REAL
, &v
, NULL
);
294 static void check_updates(struct cache_entry
**src
, int nr
)
296 static struct checkout state
= {
302 unsigned short mask
= htons(CE_UPDATE
);
303 unsigned last_percent
= 200, cnt
= 0, total
= 0;
305 if (update
&& verbose_update
) {
306 for (total
= cnt
= 0; cnt
< nr
; cnt
++) {
307 struct cache_entry
*ce
= src
[cnt
];
308 if (!ce
->ce_mode
|| ce
->ce_flags
& mask
)
312 /* Don't bother doing this for very small updates */
317 fprintf(stderr
, "Checking files out...\n");
318 setup_progress_signal();
325 struct cache_entry
*ce
= *src
++;
328 if (!ce
->ce_mode
|| ce
->ce_flags
& mask
) {
331 percent
= (cnt
* 100) / total
;
332 if (percent
!= last_percent
||
334 fprintf(stderr
, "%4u%% (%u/%u) done\r",
335 percent
, cnt
, total
);
336 last_percent
= percent
;
342 unlink_entry(ce
->name
);
345 if (ce
->ce_flags
& mask
) {
346 ce
->ce_flags
&= ~mask
;
348 checkout_entry(ce
, &state
, NULL
);
352 signal(SIGALRM
, SIG_IGN
);
357 static int unpack_trees(merge_fn_t fn
)
360 unsigned len
= object_list_length(trees
);
361 struct tree_entry_list
**posns
;
363 struct object_list
*posn
= trees
;
367 posns
= xmalloc(len
* sizeof(struct tree_entry_list
*));
368 for (i
= 0; i
< len
; i
++) {
369 posns
[i
] = ((struct tree
*) posn
->item
)->entries
;
372 if (unpack_trees_rec(posns
, len
, "", fn
, &indpos
))
376 if (trivial_merges_only
&& nontrivial_merge
)
377 die("Merge requires file-level merging");
379 check_updates(active_cache
, active_nr
);
383 static int list_tree(unsigned char *sha1
)
385 struct tree
*tree
= parse_tree_indirect(sha1
);
388 object_list_append(&tree
->object
, &trees
);
392 static int same(struct cache_entry
*a
, struct cache_entry
*b
)
398 return a
->ce_mode
== b
->ce_mode
&&
399 !memcmp(a
->sha1
, b
->sha1
, 20);
404 * When a CE gets turned into an unmerged entry, we
405 * want it to be up-to-date
407 static void verify_uptodate(struct cache_entry
*ce
)
414 if (!lstat(ce
->name
, &st
)) {
415 unsigned changed
= ce_match_stat(ce
, &st
, 1);
422 die("Entry '%s' not uptodate. Cannot merge.", ce
->name
);
425 static void invalidate_ce_path(struct cache_entry
*ce
)
428 cache_tree_invalidate_path(active_cache_tree
, ce
->name
);
431 static int merged_entry(struct cache_entry
*merge
, struct cache_entry
*old
)
433 merge
->ce_flags
|= htons(CE_UPDATE
);
436 * See if we can re-use the old CE directly?
437 * That way we get the uptodate stat info.
439 * This also removes the UPDATE flag on
442 if (same(old
, merge
)) {
445 verify_uptodate(old
);
446 invalidate_ce_path(old
);
449 merge
->ce_flags
&= ~htons(CE_STAGEMASK
);
450 add_cache_entry(merge
, ADD_CACHE_OK_TO_ADD
);
454 static int deleted_entry(struct cache_entry
*ce
, struct cache_entry
*old
)
457 verify_uptodate(old
);
459 add_cache_entry(ce
, ADD_CACHE_OK_TO_ADD
);
460 invalidate_ce_path(ce
);
464 static int keep_entry(struct cache_entry
*ce
)
466 add_cache_entry(ce
, ADD_CACHE_OK_TO_ADD
);
471 static void show_stage_entry(FILE *o
,
472 const char *label
, const struct cache_entry
*ce
)
475 fprintf(o
, "%s (missing)\n", label
);
477 fprintf(o
, "%s%06o %s %d\t%s\n",
480 sha1_to_hex(ce
->sha1
),
486 static int threeway_merge(struct cache_entry
**stages
)
488 struct cache_entry
*index
;
489 struct cache_entry
*head
;
490 struct cache_entry
*remote
= stages
[head_idx
+ 1];
493 int remote_match
= 0;
495 int df_conflict_head
= 0;
496 int df_conflict_remote
= 0;
498 int any_anc_missing
= 0;
499 int no_anc_exists
= 1;
502 for (i
= 1; i
< head_idx
; i
++) {
510 head
= stages
[head_idx
];
512 if (head
== &df_conflict_entry
) {
513 df_conflict_head
= 1;
517 if (remote
== &df_conflict_entry
) {
518 df_conflict_remote
= 1;
522 /* First, if there's a #16 situation, note that to prevent #13
525 if (!same(remote
, head
)) {
526 for (i
= 1; i
< head_idx
; i
++) {
527 if (same(stages
[i
], head
)) {
530 if (same(stages
[i
], remote
)) {
536 /* We start with cases where the index is allowed to match
537 * something other than the head: #14(ALT) and #2ALT, where it
538 * is permitted to match the result instead.
540 /* #14, #14ALT, #2ALT */
541 if (remote
&& !df_conflict_head
&& head_match
&& !remote_match
) {
542 if (index
&& !same(index
, remote
) && !same(index
, head
))
544 return merged_entry(remote
, index
);
547 * If we have an entry in the index cache, then we want to
548 * make sure that it matches head.
550 if (index
&& !same(index
, head
)) {
556 if (same(head
, remote
))
557 return merged_entry(head
, index
);
559 if (!df_conflict_remote
&& remote_match
&& !head_match
)
560 return merged_entry(head
, index
);
564 if (!head
&& !remote
&& any_anc_missing
)
567 /* Under the new "aggressive" rule, we resolve mostly trivial
568 * cases that we historically had git-merge-one-file resolve.
571 int head_deleted
= !head
&& !df_conflict_head
;
572 int remote_deleted
= !remote
&& !df_conflict_remote
;
575 * Deleted in one and unchanged in the other.
577 if ((head_deleted
&& remote_deleted
) ||
578 (head_deleted
&& remote
&& remote_match
) ||
579 (remote_deleted
&& head
&& head_match
)) {
581 return deleted_entry(index
, index
);
585 * Added in both, identically.
587 if (no_anc_exists
&& head
&& remote
&& same(head
, remote
))
588 return merged_entry(head
, index
);
592 /* Below are "no merge" cases, which require that the index be
593 * up-to-date to avoid the files getting overwritten with
594 * conflict resolution files.
597 verify_uptodate(index
);
600 nontrivial_merge
= 1;
602 /* #2, #3, #4, #6, #7, #9, #11. */
604 if (!head_match
|| !remote_match
) {
605 for (i
= 1; i
< head_idx
; i
++) {
607 keep_entry(stages
[i
]);
615 fprintf(stderr
, "read-tree: warning #16 detected\n");
616 show_stage_entry(stderr
, "head ", stages
[head_match
]);
617 show_stage_entry(stderr
, "remote ", stages
[remote_match
]);
620 if (head
) { count
+= keep_entry(head
); }
621 if (remote
) { count
+= keep_entry(remote
); }
628 * The rule is to "carry forward" what is in the index without losing
629 * information across a "fast forward", favoring a successful merge
630 * over a merge failure when it makes sense. For details of the
631 * "carry forward" rule, please see <Documentation/git-read-tree.txt>.
634 static int twoway_merge(struct cache_entry
**src
)
636 struct cache_entry
*current
= src
[0];
637 struct cache_entry
*oldtree
= src
[1], *newtree
= src
[2];
640 return error("Cannot do a twoway merge of %d trees",
644 if ((!oldtree
&& !newtree
) || /* 4 and 5 */
645 (!oldtree
&& newtree
&&
646 same(current
, newtree
)) || /* 6 and 7 */
647 (oldtree
&& newtree
&&
648 same(oldtree
, newtree
)) || /* 14 and 15 */
649 (oldtree
&& newtree
&&
650 !same(oldtree
, newtree
) && /* 18 and 19*/
651 same(current
, newtree
))) {
652 return keep_entry(current
);
654 else if (oldtree
&& !newtree
&& same(current
, oldtree
)) {
656 return deleted_entry(oldtree
, current
);
658 else if (oldtree
&& newtree
&&
659 same(current
, oldtree
) && !same(current
, newtree
)) {
661 return merged_entry(newtree
, current
);
664 /* all other failures */
666 reject_merge(oldtree
);
668 reject_merge(current
);
670 reject_merge(newtree
);
675 return merged_entry(newtree
, current
);
677 return deleted_entry(oldtree
, current
);
684 * - take the stat information from stage0, take the data from stage1
686 static int oneway_merge(struct cache_entry
**src
)
688 struct cache_entry
*old
= src
[0];
689 struct cache_entry
*a
= src
[1];
692 return error("Cannot do a oneway merge of %d trees",
696 invalidate_ce_path(old
);
699 if (old
&& same(old
, a
)) {
700 return keep_entry(old
);
702 return merged_entry(a
, NULL
);
705 static int read_cache_unmerged(void)
708 struct cache_entry
**dst
;
713 for (i
= 0; i
< active_nr
; i
++) {
714 struct cache_entry
*ce
= active_cache
[i
];
717 invalidate_ce_path(ce
);
724 active_nr
-= deleted
;
728 static const char read_tree_usage
[] = "git-read-tree (<sha> | -m [--aggressive] [-u | -i] <sha1> [<sha2> [<sha3>]])";
730 static struct cache_file cache_file
;
732 int main(int argc
, char **argv
)
734 int i
, newfd
, reset
, stage
= 0;
735 unsigned char sha1
[20];
736 merge_fn_t fn
= NULL
;
738 setup_git_directory();
739 git_config(git_default_config
);
741 newfd
= hold_index_file_for_update(&cache_file
, get_index_file());
743 die("unable to create new cachefile");
745 git_config(git_default_config
);
749 for (i
= 1; i
< argc
; i
++) {
750 const char *arg
= argv
[i
];
752 /* "-u" means "update", meaning that a merge will update
755 if (!strcmp(arg
, "-u")) {
760 if (!strcmp(arg
, "-v")) {
765 /* "-i" means "index only", meaning that a merge will
766 * not even look at the working tree.
768 if (!strcmp(arg
, "-i")) {
773 /* This differs from "-m" in that we'll silently ignore unmerged entries */
774 if (!strcmp(arg
, "--reset")) {
776 usage(read_tree_usage
);
780 read_cache_unmerged();
784 if (!strcmp(arg
, "--trivial")) {
785 trivial_merges_only
= 1;
789 if (!strcmp(arg
, "--aggressive")) {
794 /* "-m" stands for "merge", meaning we start in stage 1 */
795 if (!strcmp(arg
, "-m")) {
797 usage(read_tree_usage
);
798 if (read_cache_unmerged())
799 die("you need to resolve your current index first");
805 /* using -u and -i at the same time makes no sense */
806 if (1 < index_only
+ update
)
807 usage(read_tree_usage
);
809 if (get_sha1(arg
, sha1
) < 0)
810 usage(read_tree_usage
);
811 if (list_tree(sha1
) < 0)
812 die("failed to unpack tree object %s", arg
);
815 if ((update
||index_only
) && !merge
)
816 usage(read_tree_usage
);
820 die("just how do you expect me to merge %d trees?", stage
-1);
831 cache_tree_free(&active_cache_tree
);
836 head_idx
= stage
- 2;
842 if (write_cache(newfd
, active_cache
, active_nr
) ||
843 commit_index_file(&cache_file
))
844 die("unable to write new index file");