diff options
Diffstat (limited to 'unpack-trees.c')
| -rw-r--r-- | unpack-trees.c | 928 |
1 files changed, 928 insertions, 0 deletions
diff --git a/unpack-trees.c b/unpack-trees.c new file mode 100644 index 0000000000..aa2513ed79 --- /dev/null +++ b/unpack-trees.c @@ -0,0 +1,928 @@ +#include "cache.h" +#include "dir.h" +#include "tree.h" +#include "tree-walk.h" +#include "cache-tree.h" +#include "unpack-trees.h" +#include "progress.h" +#include "refs.h" + +#define DBRT_DEBUG 1 + +struct tree_entry_list { + struct tree_entry_list *next; + unsigned int mode; + const char *name; + const unsigned char *sha1; +}; + +static struct tree_entry_list *create_tree_entry_list(struct tree_desc *desc) +{ + struct name_entry one; + struct tree_entry_list *ret = NULL; + struct tree_entry_list **list_p = &ret; + + while (tree_entry(desc, &one)) { + struct tree_entry_list *entry; + + entry = xmalloc(sizeof(struct tree_entry_list)); + entry->name = one.path; + entry->sha1 = one.sha1; + entry->mode = one.mode; + entry->next = NULL; + + *list_p = entry; + list_p = &entry->next; + } + return ret; +} + +static int entcmp(const char *name1, int dir1, const char *name2, int dir2) +{ + int len1 = strlen(name1); + int len2 = strlen(name2); + int len = len1 < len2 ? len1 : len2; + int ret = memcmp(name1, name2, len); + unsigned char c1, c2; + if (ret) + return ret; + c1 = name1[len]; + c2 = name2[len]; + if (!c1 && dir1) + c1 = '/'; + if (!c2 && dir2) + c2 = '/'; + ret = (c1 < c2) ? -1 : (c1 > c2) ? 1 : 0; + if (c1 && c2 && !ret) + ret = len1 - len2; + return ret; +} + +static inline void remove_entry(int remove) +{ + if (remove >= 0) + remove_cache_entry_at(remove); +} + +static int unpack_trees_rec(struct tree_entry_list **posns, int len, + const char *base, struct unpack_trees_options *o, + struct tree_entry_list *df_conflict_list) +{ + int remove; + int baselen = strlen(base); + int src_size = len + 1; + int retval = 0; + + do { + int i; + const char *first; + int firstdir = 0; + int pathlen; + unsigned ce_size; + struct tree_entry_list **subposns; + struct cache_entry **src; + int any_files = 0; + int any_dirs = 0; + char *cache_name; + int ce_stage; + + /* Find the first name in the input. */ + + first = NULL; + cache_name = NULL; + + /* Check the cache */ + if (o->merge && o->pos < active_nr) { + /* This is a bit tricky: */ + /* If the index has a subdirectory (with + * contents) as the first name, it'll get a + * filename like "foo/bar". But that's after + * "foo", so the entry in trees will get + * handled first, at which point we'll go into + * "foo", and deal with "bar" from the index, + * because the base will be "foo/". The only + * way we can actually have "foo/bar" first of + * all the things is if the trees don't + * contain "foo" at all, in which case we'll + * handle "foo/bar" without going into the + * directory, but that's fine (and will return + * an error anyway, with the added unknown + * file case. + */ + + cache_name = active_cache[o->pos]->name; + if (strlen(cache_name) > baselen && + !memcmp(cache_name, base, baselen)) { + cache_name += baselen; + first = cache_name; + } else { + cache_name = NULL; + } + } + +#if DBRT_DEBUG > 1 + if (first) + printf("index %s\n", first); +#endif + for (i = 0; i < len; i++) { + if (!posns[i] || posns[i] == df_conflict_list) + continue; +#if DBRT_DEBUG > 1 + printf("%d %s\n", i + 1, posns[i]->name); +#endif + if (!first || entcmp(first, firstdir, + posns[i]->name, + S_ISDIR(posns[i]->mode)) > 0) { + first = posns[i]->name; + firstdir = S_ISDIR(posns[i]->mode); + } + } + /* No name means we're done */ + if (!first) + goto leave_directory; + + pathlen = strlen(first); + ce_size = cache_entry_size(baselen + pathlen); + + src = xcalloc(src_size, sizeof(struct cache_entry *)); + + subposns = xcalloc(len, sizeof(struct tree_list_entry *)); + + remove = -1; + if (cache_name && !strcmp(cache_name, first)) { + any_files = 1; + src[0] = active_cache[o->pos]; + remove = o->pos; + } + + for (i = 0; i < len; i++) { + struct cache_entry *ce; + + if (!posns[i] || + (posns[i] != df_conflict_list && + strcmp(first, posns[i]->name))) { + continue; + } + + if (posns[i] == df_conflict_list) { + src[i + o->merge] = o->df_conflict_entry; + continue; + } + + if (S_ISDIR(posns[i]->mode)) { + struct tree *tree = lookup_tree(posns[i]->sha1); + struct tree_desc t; + any_dirs = 1; + parse_tree(tree); + init_tree_desc(&t, tree->buffer, tree->size); + subposns[i] = create_tree_entry_list(&t); + posns[i] = posns[i]->next; + src[i + o->merge] = o->df_conflict_entry; + continue; + } + + if (!o->merge) + ce_stage = 0; + else if (i + 1 < o->head_idx) + ce_stage = 1; + else if (i + 1 > o->head_idx) + ce_stage = 3; + else + ce_stage = 2; + + ce = xcalloc(1, ce_size); + ce->ce_mode = create_ce_mode(posns[i]->mode); + ce->ce_flags = create_ce_flags(baselen + pathlen, + ce_stage); + memcpy(ce->name, base, baselen); + memcpy(ce->name + baselen, first, pathlen + 1); + + any_files = 1; + + hashcpy(ce->sha1, posns[i]->sha1); + src[i + o->merge] = ce; + subposns[i] = df_conflict_list; + posns[i] = posns[i]->next; + } + if (any_files) { + if (o->merge) { + int ret; + +#if DBRT_DEBUG > 1 + printf("%s:\n", first); + for (i = 0; i < src_size; i++) { + printf(" %d ", i); + if (src[i]) + printf("%s\n", sha1_to_hex(src[i]->sha1)); + else + printf("\n"); + } +#endif + ret = o->fn(src, o, remove); + +#if DBRT_DEBUG > 1 + printf("Added %d entries\n", ret); +#endif + o->pos += ret; + } else { + remove_entry(remove); + for (i = 0; i < src_size; i++) { + if (src[i]) { + add_cache_entry(src[i], ADD_CACHE_OK_TO_ADD|ADD_CACHE_SKIP_DFCHECK); + } + } + } + } + if (any_dirs) { + char *newbase = xmalloc(baselen + 2 + pathlen); + memcpy(newbase, base, baselen); + memcpy(newbase + baselen, first, pathlen); + newbase[baselen + pathlen] = '/'; + newbase[baselen + pathlen + 1] = '\0'; + if (unpack_trees_rec(subposns, len, newbase, o, + df_conflict_list)) { + retval = -1; + goto leave_directory; + } + free(newbase); + } + free(subposns); + free(src); + } while (1); + + leave_directory: + return retval; +} + +/* Unlink the last component and attempt to remove leading + * directories, in case this unlink is the removal of the + * last entry in the directory -- empty directories are removed. + */ +static void unlink_entry(char *name, char *last_symlink) +{ + char *cp, *prev; + + if (has_symlink_leading_path(name, last_symlink)) + return; + if (unlink(name)) + return; + prev = NULL; + while (1) { + int status; + cp = strrchr(name, '/'); + if (prev) + *prev = '/'; + if (!cp) + break; + + *cp = 0; + status = rmdir(name); + if (status) { + *cp = '/'; + break; + } + prev = cp; + } +} + +static struct checkout state; +static void check_updates(struct cache_entry **src, int nr, + struct unpack_trees_options *o) +{ + unsigned short mask = htons(CE_UPDATE); + unsigned cnt = 0, total = 0; + struct progress *progress = NULL; + char last_symlink[PATH_MAX]; + + if (o->update && o->verbose_update) { + for (total = cnt = 0; cnt < nr; cnt++) { + struct cache_entry *ce = src[cnt]; + if (!ce->ce_mode || ce->ce_flags & mask) + total++; + } + + progress = start_progress_delay("Checking out files", + total, 50, 2); + cnt = 0; + } + + *last_symlink = '\0'; + while (nr--) { + struct cache_entry *ce = *src++; + + if (!ce->ce_mode || ce->ce_flags & mask) + display_progress(progress, ++cnt); + if (!ce->ce_mode) { + if (o->update) + unlink_entry(ce->name, last_symlink); + continue; + } + if (ce->ce_flags & mask) { + ce->ce_flags &= ~mask; + if (o->update) { + checkout_entry(ce, &state, NULL); + *last_symlink = '\0'; + } + } + } + stop_progress(&progress); +} + +int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o) +{ + struct tree_entry_list **posns; + int i; + struct tree_entry_list df_conflict_list; + static struct cache_entry *dfc; + + memset(&df_conflict_list, 0, sizeof(df_conflict_list)); + df_conflict_list.next = &df_conflict_list; + memset(&state, 0, sizeof(state)); + state.base_dir = ""; + state.force = 1; + state.quiet = 1; + state.refresh_cache = 1; + + o->merge_size = len; + + if (!dfc) + dfc = xcalloc(1, sizeof(struct cache_entry) + 1); + o->df_conflict_entry = dfc; + + if (len) { + posns = xmalloc(len * sizeof(struct tree_entry_list *)); + for (i = 0; i < len; i++) + posns[i] = create_tree_entry_list(t+i); + + if (unpack_trees_rec(posns, len, o->prefix ? o->prefix : "", + o, &df_conflict_list)) + return -1; + } + + if (o->trivial_merges_only && o->nontrivial_merge) + die("Merge requires file-level merging"); + + check_updates(active_cache, active_nr, o); + return 0; +} + +/* Here come the merge functions */ + +static void reject_merge(struct cache_entry *ce) +{ + die("Entry '%s' would be overwritten by merge. Cannot merge.", + ce->name); +} + +static int same(struct cache_entry *a, struct cache_entry *b) +{ + if (!!a != !!b) + return 0; + if (!a && !b) + return 1; + return a->ce_mode == b->ce_mode && + !hashcmp(a->sha1, b->sha1); +} + + +/* + * When a CE gets turned into an unmerged entry, we + * want it to be up-to-date + */ +static void verify_uptodate(struct cache_entry *ce, + struct unpack_trees_options *o) +{ + struct stat st; + + if (o->index_only || o->reset) + return; + + if (!lstat(ce->name, &st)) { + unsigned changed = ce_match_stat(ce, &st, CE_MATCH_IGNORE_VALID); + if (!changed) + return; + /* + * NEEDSWORK: the current default policy is to allow + * submodule to be out of sync wrt the supermodule + * index. This needs to be tightened later for + * submodules that are marked to be automatically + * checked out. + */ + if (S_ISGITLINK(ntohl(ce->ce_mode))) + return; + errno = 0; + } + if (errno == ENOENT) + return; + die("Entry '%s' not uptodate. Cannot merge.", ce->name); +} + +static void invalidate_ce_path(struct cache_entry *ce) +{ + if (ce) + cache_tree_invalidate_path(active_cache_tree, ce->name); +} + +/* + * Check that checking out ce->sha1 in subdir ce->name is not + * going to overwrite any working files. + * + * Currently, git does not checkout subprojects during a superproject + * checkout, so it is not going to overwrite anything. + */ +static int verify_clean_submodule(struct cache_entry *ce, const char *action, + struct unpack_trees_options *o) +{ + return 0; +} + +static int verify_clean_subdirectory(struct cache_entry *ce, const char *action, + struct unpack_trees_options *o) +{ + /* + * we are about to extract "ce->name"; we would not want to lose + * anything in the existing directory there. + */ + int namelen; + int pos, i; + struct dir_struct d; + char *pathbuf; + int cnt = 0; + unsigned char sha1[20]; + + if (S_ISGITLINK(ntohl(ce->ce_mode)) && + resolve_gitlink_ref(ce->name, "HEAD", sha1) == 0) { + /* If we are not going to update the submodule, then + * we don't care. + */ + if (!hashcmp(sha1, ce->sha1)) + return 0; + return verify_clean_submodule(ce, action, o); + } + + /* + * First let's make sure we do not have a local modification + * in that directory. + */ + namelen = strlen(ce->name); + pos = cache_name_pos(ce->name, namelen); + if (0 <= pos) + return cnt; /* we have it as nondirectory */ + pos = -pos - 1; + for (i = pos; i < active_nr; i++) { + struct cache_entry *ce = active_cache[i]; + int len = ce_namelen(ce); + if (len < namelen || + strncmp(ce->name, ce->name, namelen) || + ce->name[namelen] != '/') + break; + /* + * ce->name is an entry in the subdirectory. + */ + if (!ce_stage(ce)) { + verify_uptodate(ce, o); + ce->ce_mode = 0; + } + cnt++; + } + + /* + * Then we need to make sure that we do not lose a locally + * present file that is not ignored. + */ + pathbuf = xmalloc(namelen + 2); + memcpy(pathbuf, ce->name, namelen); + strcpy(pathbuf+namelen, "/"); + + memset(&d, 0, sizeof(d)); + if (o->dir) + d.exclude_per_dir = o->dir->exclude_per_dir; + i = read_directory(&d, ce->name, pathbuf, namelen+1, NULL); + if (i) + die("Updating '%s' would lose untracked files in it", + ce->name); + free(pathbuf); + return cnt; +} + +/* + * We do not want to remove or overwrite a working tree file that + * is not tracked, unless it is ignored. + */ +static void verify_absent(struct cache_entry *ce, const char *action, + struct unpack_trees_options *o) +{ + struct stat st; + + if (o->index_only || o->reset || !o->update) + return; + + if (has_symlink_leading_path(ce->name, NULL)) + return; + + if (!lstat(ce->name, &st)) { + int cnt; + + if (o->dir && excluded(o->dir, ce->name)) + /* + * ce->name is explicitly excluded, so it is Ok to + * overwrite it. + */ + return; + if (S_ISDIR(st.st_mode)) { + /* + * We are checking out path "foo" and + * found "foo/." in the working tree. + * This is tricky -- if we have modified + * files that are in "foo/" we would lose + * it. + */ + cnt = verify_clean_subdirectory(ce, action, o); + + /* + * If this removed entries from the index, + * what that means is: + * + * (1) the caller unpack_trees_rec() saw path/foo + * in the index, and it has not removed it because + * it thinks it is handling 'path' as blob with + * D/F conflict; + * (2) we will return "ok, we placed a merged entry + * in the index" which would cause o->pos to be + * incremented by one; + * (3) however, original o->pos now has 'path/foo' + * marked with "to be removed". + * + * We need to increment it by the number of + * deleted entries here. + */ + o->pos += cnt; + return; + } + + /* + * The previous round may already have decided to + * delete this path, which is in a subdirectory that + * is being replaced with a blob. + */ + cnt = cache_name_pos(ce->name, strlen(ce->name)); + if (0 <= cnt) { + struct cache_entry *ce = active_cache[cnt]; + if (!ce_stage(ce) && !ce->ce_mode) + return; + } + + die("Untracked working tree file '%s' " + "would be %s by merge.", ce->name, action); + } +} + +static int merged_entry(struct cache_entry *merge, struct cache_entry *old, + struct unpack_trees_options *o) +{ + merge->ce_flags |= htons(CE_UPDATE); + if (old) { + /* + * See if we can re-use the old CE directly? + * That way we get the uptodate stat info. + * + * This also removes the UPDATE flag on + * a match. + */ + if (same(old, merge)) { + memcpy(merge, old, offsetof(struct cache_entry, name)); + } else { + verify_uptodate(old, o); + invalidate_ce_path(old); + } + } + else { + verify_absent(merge, "overwritten", o); + invalidate_ce_path(merge); + } + + merge->ce_flags &= ~htons(CE_STAGEMASK); + add_cache_entry(merge, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE); + return 1; +} + +static int deleted_entry(struct cache_entry *ce, struct cache_entry *old, + struct unpack_trees_options *o) +{ + if (old) + verify_uptodate(old, o); + else + verify_absent(ce, "removed", o); + ce->ce_mode = 0; + add_cache_entry(ce, ADD_CACHE_OK_TO_ADD|ADD_CACHE_OK_TO_REPLACE); + invalidate_ce_path(ce); + return 1; +} + +static int keep_entry(struct cache_entry *ce, struct unpack_trees_options *o) +{ + add_cache_entry(ce, ADD_CACHE_OK_TO_ADD); + return 1; +} + +#if DBRT_DEBUG +static void show_stage_entry(FILE *o, + const char *label, const struct cache_entry *ce) +{ + if (!ce) + fprintf(o, "%s (missing)\n", label); + else + fprintf(o, "%s%06o %s %d\t%s\n", + label, + ntohl(ce->ce_mode), + sha1_to_hex(ce->sha1), + ce_stage(ce), + ce->name); +} +#endif + +int threeway_merge(struct cache_entry **stages, + struct unpack_trees_options *o, + int remove) +{ + struct cache_entry *index; + struct cache_entry *head; + struct cache_entry *remote = stages[o->head_idx + 1]; + int count; + int head_match = 0; + int remote_match = 0; + + int df_conflict_head = 0; + int df_conflict_remote = 0; + + int any_anc_missing = 0; + int no_anc_exists = 1; + int i; + + for (i = 1; i < o->head_idx; i++) { + if (!stages[i] || stages[i] == o->df_conflict_entry) + any_anc_missing = 1; + else + no_anc_exists = 0; + } + + index = stages[0]; + head = stages[o->head_idx]; + + if (head == o->df_conflict_entry) { + df_conflict_head = 1; + head = NULL; + } + + if (remote == o->df_conflict_entry) { + df_conflict_remote = 1; + remote = NULL; + } + + /* First, if there's a #16 situation, note that to prevent #13 + * and #14. + */ + if (!same(remote, head)) { + for (i = 1; i < o->head_idx; i++) { + if (same(stages[i], head)) { + head_match = i; + } + if (same(stages[i], remote)) { + remote_match = i; + } + } + } + + /* We start with cases where the index is allowed to match + * something other than the head: #14(ALT) and #2ALT, where it + * is permitted to match the result instead. + */ + /* #14, #14ALT, #2ALT */ + if (remote && !df_conflict_head && head_match && !remote_match) { + if (index && !same(index, remote) && !same(index, head)) + reject_merge(index); + return merged_entry(remote, index, o); + } + /* + * If we have an entry in the index cache, then we want to + * make sure that it matches head. + */ + if (index && !same(index, head)) { + reject_merge(index); + } + + if (head) { + /* #5ALT, #15 */ + if (same(head, remote)) + return merged_entry(head, index, o); + /* #13, #3ALT */ + if (!df_conflict_remote && remote_match && !head_match) + return merged_entry(head, index, o); + } + + /* #1 */ + if (!head && !remote && any_anc_missing) { + remove_entry(remove); + return 0; + } + + /* Under the new "aggressive" rule, we resolve mostly trivial + * cases that we historically had git-merge-one-file resolve. + */ + if (o->aggressive) { + int head_deleted = !head && !df_conflict_head; + int remote_deleted = !remote && !df_conflict_remote; + struct cache_entry *ce = NULL; + + if (index) + ce = index; + else if (head) + ce = head; + else if (remote) + ce = remote; + else { + for (i = 1; i < o->head_idx; i++) { + if (stages[i] && stages[i] != o->df_conflict_entry) { + ce = stages[i]; + break; + } + } + } + + /* + * Deleted in both. + * Deleted in one and unchanged in the other. + */ + if ((head_deleted && remote_deleted) || + (head_deleted && remote && remote_match) || + (remote_deleted && head && head_match)) { + remove_entry(remove); + if (index) + return deleted_entry(index, index, o); + else if (ce && !head_deleted) + verify_absent(ce, "removed", o); + return 0; + } + /* + * Added in both, identically. + */ + if (no_anc_exists && head && remote && same(head, remote)) + return merged_entry(head, index, o); + + } + + /* Below are "no merge" cases, which require that the index be + * up-to-date to avoid the files getting overwritten with + * conflict resolution files. + */ + if (index) { + verify_uptodate(index, o); + } + + remove_entry(remove); + o->nontrivial_merge = 1; + + /* #2, #3, #4, #6, #7, #9, #10, #11. */ + count = 0; + if (!head_match || !remote_match) { + for (i = 1; i < o->head_idx; i++) { + if (stages[i] && stages[i] != o->df_conflict_entry) { + keep_entry(stages[i], o); + count++; + break; + } + } + } +#if DBRT_DEBUG + else { + fprintf(stderr, "read-tree: warning #16 detected\n"); + show_stage_entry(stderr, "head ", stages[head_match]); + show_stage_entry(stderr, "remote ", stages[remote_match]); + } +#endif + if (head) { count += keep_entry(head, o); } + if (remote) { count += keep_entry(remote, o); } + return count; +} + +/* + * Two-way merge. + * + * The rule is to "carry forward" what is in the index without losing + * information across a "fast forward", favoring a successful merge + * over a merge failure when it makes sense. For details of the + * "carry forward" rule, please see <Documentation/git-read-tree.txt>. + * + */ +int twoway_merge(struct cache_entry **src, + struct unpack_trees_options *o, + int remove) +{ + struct cache_entry *current = src[0]; + struct cache_entry *oldtree = src[1]; + struct cache_entry *newtree = src[2]; + + if (o->merge_size != 2) + return error("Cannot do a twoway merge of %d trees", + o->merge_size); + + if (oldtree == o->df_conflict_entry) + oldtree = NULL; + if (newtree == o->df_conflict_entry) + newtree = NULL; + + if (current) { + if ((!oldtree && !newtree) || /* 4 and 5 */ + (!oldtree && newtree && + same(current, newtree)) || /* 6 and 7 */ + (oldtree && newtree && + same(oldtree, newtree)) || /* 14 and 15 */ + (oldtree && newtree && + !same(oldtree, newtree) && /* 18 and 19 */ + same(current, newtree))) { + return keep_entry(current, o); + } + else if (oldtree && !newtree && same(current, oldtree)) { + /* 10 or 11 */ + remove_entry(remove); + return deleted_entry(oldtree, current, o); + } + else if (oldtree && newtree && + same(current, oldtree) && !same(current, newtree)) { + /* 20 or 21 */ + return merged_entry(newtree, current, o); + } + else { + /* all other failures */ + remove_entry(remove); + if (oldtree) + reject_merge(oldtree); + if (current) + reject_merge(current); + if (newtree) + reject_merge(newtree); + return -1; + } + } + else if (newtree) + return merged_entry(newtree, current, o); + remove_entry(remove); + return deleted_entry(oldtree, current, o); +} + +/* + * Bind merge. + * + * Keep the index entries at stage0, collapse stage1 but make sure + * stage0 does not have anything there. + */ +int bind_merge(struct cache_entry **src, + struct unpack_trees_options *o, + int remove) +{ + struct cache_entry *old = src[0]; + struct cache_entry *a = src[1]; + + if (o->merge_size != 1) + return error("Cannot do a bind merge of %d trees\n", + o->merge_size); + if (a && old) + die("Entry '%s' overlaps. Cannot bind.", a->name); + if (!a) + return keep_entry(old, o); + else + return merged_entry(a, NULL, o); +} + +/* + * One-way merge. + * + * The rule is: + * - take the stat information from stage0, take the data from stage1 + */ +int oneway_merge(struct cache_entry **src, + struct unpack_trees_options *o, + int remove) +{ + struct cache_entry *old = src[0]; + struct cache_entry *a = src[1]; + + if (o->merge_size != 1) + return error("Cannot do a oneway merge of %d trees", + o->merge_size); + + if (!a) { + remove_entry(remove); + return deleted_entry(old, old, o); + } + if (old && same(old, a)) { + if (o->reset) { + struct stat st; + if (lstat(old->name, &st) || + ce_match_stat(old, &st, CE_MATCH_IGNORE_VALID)) + old->ce_flags |= htons(CE_UPDATE); + } + return keep_entry(old, o); + } + return merged_entry(a, old, o); +} |