#include "diffcore.h"
#include "tree.h"
-static void show_entry(struct diff_options *opt, const char *prefix,
- struct tree_desc *desc, struct strbuf *base);
-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
- struct strbuf *base, struct diff_options *opt)
-{
- unsigned mode1, mode2;
- const char *path1, *path2;
- const unsigned char *sha1, *sha2;
- int cmp, pathlen1, pathlen2;
- int old_baselen = base->len;
+static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
+ const char *base_str, struct diff_options *opt);
- sha1 = tree_entry_extract(t1, &path1, &mode1);
- sha2 = tree_entry_extract(t2, &path2, &mode2);
+/*
+ * Compare two tree entries, taking into account only path/S_ISDIR(mode),
+ * but not their sha1's.
+ *
+ * NOTE files and directories *always* compare differently, even when having
+ * the same name - thanks to base_name_compare().
+ *
+ * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
+ * so that they sort *after* valid tree entries.
+ *
+ * Due to this convention, if trees are scanned in sorted order, all
+ * non-empty descriptors will be processed first.
+ */
+static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
+{
+ struct name_entry *e1, *e2;
+ int cmp;
- pathlen1 = tree_entry_len(&t1->entry);
- pathlen2 = tree_entry_len(&t2->entry);
- cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
- if (cmp < 0) {
- show_entry(opt, "-", t1, base);
+ /* empty descriptors sort after valid tree entries */
+ if (!t1->size)
+ return t2->size ? 1 : 0;
+ else if (!t2->size)
return -1;
- }
- if (cmp > 0) {
- show_entry(opt, "+", t2, base);
- return 1;
- }
- if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
- return 0;
- /*
- * If the filemode has changed to/from a directory from/to a regular
- * file, we need to consider it a remove and an add.
- */
- if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
- show_entry(opt, "-", t1, base);
- show_entry(opt, "+", t2, base);
- return 0;
- }
-
- strbuf_add(base, path1, pathlen1);
- if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
- if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
- opt->change(opt, mode1, mode2,
- sha1, sha2, 1, 1, base->buf, 0, 0);
- }
- strbuf_addch(base, '/');
- diff_tree_sha1(sha1, sha2, base->buf, opt);
- } else {
- opt->change(opt, mode1, mode2, sha1, sha2, 1, 1, base->buf, 0, 0);
- }
- strbuf_setlen(base, old_baselen);
- return 0;
+ e1 = &t1->entry;
+ e2 = &t2->entry;
+ cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
+ e2->path, tree_entry_len(e2), e2->mode);
+ return cmp;
}
-/* A whole sub-tree went away or appeared */
-static void show_tree(struct diff_options *opt, const char *prefix,
- struct tree_desc *desc, struct strbuf *base)
+
+/* convert path, t1/t2 -> opt->diff_*() callbacks */
+static void emit_diff(struct diff_options *opt, struct strbuf *path,
+ struct tree_desc *t1, struct tree_desc *t2)
{
- enum interesting match = entry_not_interesting;
- for (; desc->size; update_tree_entry(desc)) {
- if (match != all_entries_interesting) {
- match = tree_entry_interesting(&desc->entry, base, 0,
- &opt->pathspec);
- if (match == all_entries_not_interesting)
- break;
- if (match == entry_not_interesting)
- continue;
+ unsigned int mode1 = t1 ? t1->entry.mode : 0;
+ unsigned int mode2 = t2 ? t2->entry.mode : 0;
+
+ if (mode1 && mode2) {
+ opt->change(opt, mode1, mode2, t1->entry.sha1, t2->entry.sha1,
+ 1, 1, path->buf, 0, 0);
+ }
+ else {
+ const unsigned char *sha1;
+ unsigned int mode;
+ int addremove;
+
+ if (mode2) {
+ addremove = '+';
+ sha1 = t2->entry.sha1;
+ mode = mode2;
+ } else {
+ addremove = '-';
+ sha1 = t1->entry.sha1;
+ mode = mode1;
}
- show_entry(opt, prefix, desc, base);
+
+ opt->add_remove(opt, addremove, mode, sha1, 1, path->buf, 0);
}
}
-/* A file entry went away or appeared */
-static void show_entry(struct diff_options *opt, const char *prefix,
- struct tree_desc *desc, struct strbuf *base)
+
+/* new path should be added to diff
+ *
+ * 3 cases on how/when it should be called and behaves:
+ *
+ * !t1, t2 -> path added, parent lacks it
+ * t1, !t2 -> path removed from parent
+ * t1, t2 -> path modified
+ */
+static void show_path(struct strbuf *base, struct diff_options *opt,
+ struct tree_desc *t1, struct tree_desc *t2)
{
unsigned mode;
const char *path;
- const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
- int pathlen = tree_entry_len(&desc->entry);
+ int pathlen;
int old_baselen = base->len;
+ int isdir, recurse = 0, emitthis = 1;
- strbuf_add(base, path, pathlen);
- if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
- enum object_type type;
- struct tree_desc inner;
- void *tree;
- unsigned long size;
+ /* at least something has to be valid */
+ assert(t1 || t2);
+
+ if (t2) {
+ /* path present in resulting tree */
+ tree_entry_extract(t2, &path, &mode);
+ pathlen = tree_entry_len(&t2->entry);
+ isdir = S_ISDIR(mode);
+ } else {
+ /*
+ * a path was removed - take path from parent. Also take
+ * mode from parent, to decide on recursion.
+ */
+ tree_entry_extract(t1, &path, &mode);
+ pathlen = tree_entry_len(&t1->entry);
- tree = read_sha1_file(sha1, &type, &size);
- if (!tree || type != OBJ_TREE)
- die("corrupt tree sha %s", sha1_to_hex(sha1));
+ isdir = S_ISDIR(mode);
+ mode = 0;
+ }
- if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
- opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
+ if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
+ recurse = 1;
+ emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
+ }
- strbuf_addch(base, '/');
+ strbuf_add(base, path, pathlen);
- init_tree_desc(&inner, tree, size);
- show_tree(opt, prefix, &inner, base);
- free(tree);
- } else
- opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
+ if (emitthis)
+ emit_diff(opt, base, t1, t2);
+
+ if (recurse) {
+ strbuf_addch(base, '/');
+ ll_diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
+ t2 ? t2->entry.sha1 : NULL, base->buf, opt);
+ }
strbuf_setlen(base, old_baselen);
}
static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
- struct diff_options *opt,
- enum interesting *match)
+ struct diff_options *opt)
{
+ enum interesting match;
+
while (t->size) {
- *match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
- if (*match) {
- if (*match == all_entries_not_interesting)
+ match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
+ if (match) {
+ if (match == all_entries_not_interesting)
t->size = 0;
break;
}
}
}
-int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
- const char *base_str, struct diff_options *opt)
+static int ll_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
+ const char *base_str, struct diff_options *opt)
{
+ struct tree_desc t1, t2;
+ void *t1tree, *t2tree;
struct strbuf base;
int baselen = strlen(base_str);
- enum interesting t1_match = entry_not_interesting;
- enum interesting t2_match = entry_not_interesting;
+
+ t1tree = fill_tree_descriptor(&t1, old);
+ t2tree = fill_tree_descriptor(&t2, new);
/* Enable recursion indefinitely */
opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
strbuf_add(&base, base_str, baselen);
for (;;) {
+ int cmp;
+
if (diff_can_quit_early(opt))
break;
if (opt->pathspec.nr) {
- skip_uninteresting(t1, &base, opt, &t1_match);
- skip_uninteresting(t2, &base, opt, &t2_match);
+ skip_uninteresting(&t1, &base, opt);
+ skip_uninteresting(&t2, &base, opt);
}
- if (!t1->size) {
- if (!t2->size)
- break;
- show_entry(opt, "+", t2, &base);
- update_tree_entry(t2);
- continue;
+ if (!t1.size && !t2.size)
+ break;
+
+ cmp = tree_entry_pathcmp(&t1, &t2);
+
+ /* t1 = t2 */
+ if (cmp == 0) {
+ if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
+ hashcmp(t1.entry.sha1, t2.entry.sha1) ||
+ (t1.entry.mode != t2.entry.mode))
+ show_path(&base, opt, &t1, &t2);
+
+ update_tree_entry(&t1);
+ update_tree_entry(&t2);
}
- if (!t2->size) {
- show_entry(opt, "-", t1, &base);
- update_tree_entry(t1);
- continue;
+
+ /* t1 < t2 */
+ else if (cmp < 0) {
+ show_path(&base, opt, &t1, /*t2=*/NULL);
+ update_tree_entry(&t1);
}
- switch (compare_tree_entry(t1, t2, &base, opt)) {
- case -1:
- update_tree_entry(t1);
- continue;
- case 0:
- update_tree_entry(t1);
- /* Fallthrough */
- case 1:
- update_tree_entry(t2);
- continue;
+
+ /* t1 > t2 */
+ else {
+ show_path(&base, opt, /*t1=*/NULL, &t2);
+ update_tree_entry(&t2);
}
- die("git diff-tree: internal error");
}
strbuf_release(&base);
+ free(t2tree);
+ free(t1tree);
return 0;
}
!DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
}
-static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
+static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
{
struct diff_options diff_opts;
struct diff_queue_struct *q = &diff_queued_diff;
diff_opts.break_opt = opt->break_opt;
diff_opts.rename_score = opt->rename_score;
diff_setup_done(&diff_opts);
- diff_tree(t1, t2, base, &diff_opts);
+ ll_diff_tree_sha1(old, new, base, &diff_opts);
diffcore_std(&diff_opts);
free_pathspec(&diff_opts.pathspec);
int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
{
- void *tree1, *tree2;
- struct tree_desc t1, t2;
- unsigned long size1, size2;
int retval;
- tree1 = read_object_with_reference(old, tree_type, &size1, NULL);
- if (!tree1)
- die("unable to read source tree (%s)", sha1_to_hex(old));
- tree2 = read_object_with_reference(new, tree_type, &size2, NULL);
- if (!tree2)
- die("unable to read destination tree (%s)", sha1_to_hex(new));
- init_tree_desc(&t1, tree1, size1);
- init_tree_desc(&t2, tree2, size2);
- retval = diff_tree(&t1, &t2, base, opt);
- if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
- init_tree_desc(&t1, tree1, size1);
- init_tree_desc(&t2, tree2, size2);
- try_to_follow_renames(&t1, &t2, base, opt);
- }
- free(tree1);
- free(tree2);
+ retval = ll_diff_tree_sha1(old, new, base, opt);
+ if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
+ try_to_follow_renames(old, new, base, opt);
+
return retval;
}
int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
{
- int retval;
- void *tree;
- unsigned long size;
- struct tree_desc empty, real;
-
- tree = read_object_with_reference(new, tree_type, &size, NULL);
- if (!tree)
- die("unable to read root tree (%s)", sha1_to_hex(new));
- init_tree_desc(&real, tree, size);
-
- init_tree_desc(&empty, "", 0);
- retval = diff_tree(&empty, &real, base, opt);
- free(tree);
- return retval;
+ return diff_tree_sha1(NULL, new, base, opt);
}