+#include "object.h"
+#include "tree.h"
+
+static int merge = 0;
+static int update = 0;
+static int index_only = 0;
+
+static int head_idx = -1;
+static int merge_size = 0;
+
+static struct object_list *trees = NULL;
+
+static struct cache_entry df_conflict_entry = {
+};
+
+static struct tree_entry_list df_conflict_list = {
+ .name = NULL,
+ .next = &df_conflict_list
+};
+
+typedef int (*merge_fn_t)(struct cache_entry **src);
+
+static int entcmp(char *name1, int dir1, 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 int unpack_trees_rec(struct tree_entry_list **posns, int len,
+ const char *base, merge_fn_t fn, int *indpos)
+{
+ int baselen = strlen(base);
+ int src_size = len + 1;
+ do {
+ int i;
+ 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 (merge && *indpos < 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[*indpos]->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,
+ posns[i]->directory) > 0) {
+ first = posns[i]->name;
+ firstdir = posns[i]->directory;
+ }
+ }
+ /* No name means we're done */
+ if (!first)
+ return 0;
+
+ pathlen = strlen(first);
+ ce_size = cache_entry_size(baselen + pathlen);
+
+ src = xmalloc(sizeof(struct cache_entry *) * src_size);
+ memset(src, 0, sizeof(struct cache_entry *) * src_size);
+
+ subposns = xmalloc(sizeof(struct tree_list_entry *) * len);
+ memset(subposns, 0, sizeof(struct tree_list_entry *) * len);
+
+ if (cache_name && !strcmp(cache_name, first)) {
+ any_files = 1;
+ src[0] = active_cache[*indpos];
+ remove_cache_entry_at(*indpos);
+ }
+
+ 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 + merge] = &df_conflict_entry;
+ continue;
+ }
+
+ if (posns[i]->directory) {
+ any_dirs = 1;
+ parse_tree(posns[i]->item.tree);
+ subposns[i] = posns[i]->item.tree->entries;
+ posns[i] = posns[i]->next;
+ src[i + merge] = &df_conflict_entry;
+ continue;
+ }
+
+ if (!merge)
+ ce_stage = 0;
+ else if (i + 1 < head_idx)
+ ce_stage = 1;
+ else if (i + 1 > head_idx)
+ ce_stage = 3;
+ else
+ ce_stage = 2;
+
+ ce = xmalloc(ce_size);
+ memset(ce, 0, 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;
+
+ memcpy(ce->sha1, posns[i]->item.any->sha1, 20);
+ src[i + merge] = ce;
+ subposns[i] = &df_conflict_list;
+ posns[i] = posns[i]->next;
+ }
+ if (any_files) {
+ if (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 = fn(src);
+
+#if DBRT_DEBUG > 1
+ printf("Added %d entries\n", ret);
+#endif
+ *indpos += ret;
+ } else {
+ 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, fn,
+ indpos))
+ return -1;
+ free(newbase);
+ }
+ free(subposns);
+ free(src);
+ } while (1);
+}
+
+static void reject_merge(struct cache_entry *ce)
+{
+ die("Entry '%s' would be overwritten by merge. Cannot merge.",
+ ce->name);
+}
+
+static void check_updates(struct cache_entry **src, int nr)
+{
+ static struct checkout state = {
+ .base_dir = "",
+ .force = 1,
+ .quiet = 1,
+ .refresh_cache = 1,
+ };
+ unsigned short mask = htons(CE_UPDATE);
+ while (nr--) {
+ struct cache_entry *ce = *src++;
+ if (!ce->ce_mode) {
+ if (update)
+ unlink(ce->name);
+ continue;
+ }
+ if (ce->ce_flags & mask) {
+ ce->ce_flags &= ~mask;
+ if (update)
+ checkout_entry(ce, &state);
+ }
+ }
+}
+
+static int unpack_trees(merge_fn_t fn)
+{
+ int indpos = 0;
+ unsigned len = object_list_length(trees);
+ struct tree_entry_list **posns =
+ xmalloc(len * sizeof(struct tree_entry_list *));
+ int i;
+ struct object_list *posn = trees;
+ merge_size = len;
+ for (i = 0; i < len; i++) {
+ posns[i] = ((struct tree *) posn->item)->entries;
+ posn = posn->next;
+ }
+ if (unpack_trees_rec(posns, len, "", fn, &indpos))
+ return -1;
+
+ check_updates(active_cache, active_nr);
+ return 0;
+}
+
+static int list_tree(unsigned char *sha1)
+{
+ struct tree *tree = parse_tree_indirect(sha1);
+ if (!tree)
+ return -1;
+ object_list_append(&tree->object, &trees);
+ return 0;
+}
+
+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 &&
+ !memcmp(a->sha1, b->sha1, 20);
+}
+
+
+/*
+ * 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)