fd0c2111c48dc13b9d0d713ec7aa4a181daedb6a
   1#include "cache.h"
   2#include "tree-walk.h"
   3#include "blob.h"
   4
   5static const char merge_tree_usage[] = "git-merge-tree <base-tree> <branch1> <branch2>";
   6static int resolve_directories = 1;
   7
   8struct merge_list {
   9        struct merge_list *next;
  10        struct merge_list *link;        /* other stages for this object */
  11
  12        unsigned int stage : 2,
  13                     flags : 30;
  14        unsigned int mode;
  15        const char *path;
  16        struct blob *blob;
  17};
  18
  19static struct merge_list *merge_result, **merge_result_end = &merge_result;
  20
  21static void add_merge_entry(struct merge_list *entry)
  22{
  23        *merge_result_end = entry;
  24        merge_result_end = &entry->next;
  25}
  26
  27static void merge_trees(struct tree_desc t[3], const char *base);
  28
  29static const char *explanation(struct merge_list *entry)
  30{
  31        switch (entry->stage) {
  32        case 0:
  33                return "merged";
  34        case 3:
  35                return "added in remote";
  36        case 2:
  37                if (entry->link)
  38                        return "added in both";
  39                return "added in local";
  40        }
  41
  42        /* Existed in base */
  43        entry = entry->link;
  44        if (!entry)
  45                return "removed in both";
  46
  47        if (entry->link)
  48                return "changed in both";
  49
  50        if (entry->stage == 3)
  51                return "removed in local";
  52        return "removed in remote";
  53}
  54
  55static void show_result_list(struct merge_list *entry)
  56{
  57        printf("%s\n", explanation(entry));
  58        do {
  59                struct merge_list *link = entry->link;
  60                static const char *desc[4] = { "result", "base", "our", "their" };
  61                printf("  %-6s %o %s %s\n", desc[entry->stage], entry->mode, sha1_to_hex(entry->blob->object.sha1), entry->path);
  62                entry = link;
  63        } while (entry);
  64}
  65
  66static void show_result(void)
  67{
  68        struct merge_list *walk;
  69
  70        walk = merge_result;
  71        while (walk) {
  72                show_result_list(walk);
  73                walk = walk->next;
  74        }
  75}
  76
  77/* An empty entry never compares same, not even to another empty entry */
  78static int same_entry(struct name_entry *a, struct name_entry *b)
  79{
  80        return  a->sha1 &&
  81                b->sha1 &&
  82                !memcmp(a->sha1, b->sha1, 20) &&
  83                a->mode == b->mode;
  84}
  85
  86static struct merge_list *create_entry(unsigned stage, unsigned mode, const unsigned char *sha1, const char *path)
  87{
  88        struct merge_list *res = xmalloc(sizeof(*res));
  89
  90        memset(res, 0, sizeof(*res));
  91        res->stage = stage;
  92        res->path = path;
  93        res->mode = mode;
  94        res->blob = lookup_blob(sha1);
  95        return res;
  96}
  97
  98static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result)
  99{
 100        struct merge_list *orig, *final;
 101        const char *path;
 102
 103        /* If it's already branch1, don't bother showing it */
 104        if (!branch1)
 105                return;
 106
 107        path = strdup(mkpath("%s%s", base, result->path));
 108        orig = create_entry(2, branch1->mode, branch1->sha1, path);
 109        final = create_entry(0, result->mode, result->sha1, path);
 110
 111        final->link = orig;
 112
 113        add_merge_entry(final);
 114}
 115
 116static int unresolved_directory(const char *base, struct name_entry n[3])
 117{
 118        int baselen;
 119        char *newbase;
 120        struct name_entry *p;
 121        struct tree_desc t[3];
 122        void *buf0, *buf1, *buf2;
 123
 124        if (!resolve_directories)
 125                return 0;
 126        p = n;
 127        if (!p->mode) {
 128                p++;
 129                if (!p->mode)
 130                        p++;
 131        }
 132        if (!S_ISDIR(p->mode))
 133                return 0;
 134        baselen = strlen(base);
 135        newbase = xmalloc(baselen + p->pathlen + 2);
 136        memcpy(newbase, base, baselen);
 137        memcpy(newbase + baselen, p->path, p->pathlen);
 138        memcpy(newbase + baselen + p->pathlen, "/", 2);
 139
 140        buf0 = fill_tree_descriptor(t+0, n[0].sha1);
 141        buf1 = fill_tree_descriptor(t+1, n[1].sha1);
 142        buf2 = fill_tree_descriptor(t+2, n[2].sha1);
 143        merge_trees(t, newbase);
 144
 145        free(buf0);
 146        free(buf1);
 147        free(buf2);
 148        free(newbase);
 149        return 1;
 150}
 151
 152
 153static struct merge_list *link_entry(unsigned stage, const char *base, struct name_entry *n, struct merge_list *entry)
 154{
 155        const char *path;
 156        struct merge_list *link;
 157
 158        if (!n->mode)
 159                return entry;
 160        if (entry)
 161                path = entry->path;
 162        else
 163                path = strdup(mkpath("%s%s", base, n->path));
 164        link = create_entry(stage, n->mode, n->sha1, path);
 165        link->link = entry;
 166        return link;
 167}
 168
 169static void unresolved(const char *base, struct name_entry n[3])
 170{
 171        struct merge_list *entry = NULL;
 172
 173        if (unresolved_directory(base, n))
 174                return;
 175
 176        /*
 177         * Do them in reverse order so that the resulting link
 178         * list has the stages in order - link_entry adds new
 179         * links at the front.
 180         */
 181        entry = link_entry(3, base, n + 2, entry);
 182        entry = link_entry(2, base, n + 1, entry);
 183        entry = link_entry(1, base, n + 0, entry);
 184
 185        add_merge_entry(entry);
 186}
 187
 188/*
 189 * Merge two trees together (t[1] and t[2]), using a common base (t[0])
 190 * as the origin.
 191 *
 192 * This walks the (sorted) trees in lock-step, checking every possible
 193 * name. Note that directories automatically sort differently from other
 194 * files (see "base_name_compare"), so you'll never see file/directory
 195 * conflicts, because they won't ever compare the same.
 196 *
 197 * IOW, if a directory changes to a filename, it will automatically be
 198 * seen as the directory going away, and the filename being created.
 199 *
 200 * Think of this as a three-way diff.
 201 *
 202 * The output will be either:
 203 *  - successful merge
 204 *       "0 mode sha1 filename"
 205 *    NOTE NOTE NOTE! FIXME! We really really need to walk the index
 206 *    in parallel with this too!
 207 *
 208 *  - conflict:
 209 *      "1 mode sha1 filename"
 210 *      "2 mode sha1 filename"
 211 *      "3 mode sha1 filename"
 212 *    where not all of the 1/2/3 lines may exist, of course.
 213 *
 214 * The successful merge rules are the same as for the three-way merge
 215 * in git-read-tree.
 216 */
 217static void threeway_callback(int n, unsigned long mask, struct name_entry *entry, const char *base)
 218{
 219        /* Same in both? */
 220        if (same_entry(entry+1, entry+2)) {
 221                if (entry[0].sha1) {
 222                        resolve(base, NULL, entry+1);
 223                        return;
 224                }
 225        }
 226
 227        if (same_entry(entry+0, entry+1)) {
 228                if (entry[2].sha1 && !S_ISDIR(entry[2].mode)) {
 229                        resolve(base, entry+1, entry+2);
 230                        return;
 231                }
 232        }
 233
 234        if (same_entry(entry+0, entry+2)) {
 235                if (entry[1].sha1 && !S_ISDIR(entry[1].mode)) {
 236                        resolve(base, NULL, entry+1);
 237                        return;
 238                }
 239        }
 240
 241        unresolved(base, entry);
 242}
 243
 244static void merge_trees(struct tree_desc t[3], const char *base)
 245{
 246        traverse_trees(3, t, base, threeway_callback);
 247}
 248
 249static void *get_tree_descriptor(struct tree_desc *desc, const char *rev)
 250{
 251        unsigned char sha1[20];
 252        void *buf;
 253
 254        if (get_sha1(rev, sha1))
 255                die("unknown rev %s", rev);
 256        buf = fill_tree_descriptor(desc, sha1);
 257        if (!buf)
 258                die("%s is not a tree", rev);
 259        return buf;
 260}
 261
 262int main(int argc, char **argv)
 263{
 264        struct tree_desc t[3];
 265        void *buf1, *buf2, *buf3;
 266
 267        if (argc < 4)
 268                usage(merge_tree_usage);
 269
 270        buf1 = get_tree_descriptor(t+0, argv[1]);
 271        buf2 = get_tree_descriptor(t+1, argv[2]);
 272        buf3 = get_tree_descriptor(t+2, argv[3]);
 273        merge_trees(t, "");
 274        free(buf1);
 275        free(buf2);
 276        free(buf3);
 277
 278        show_result();
 279        return 0;
 280}