blob: ba01563a0241041cb401cfb03495e6067847248e [file] [log] [blame]
Linus Torvaldsac1b3d12005-10-20 21:05:05 -07001/*
2 * Helper functions for tree diff generation
3 */
4#include "cache.h"
5#include "diff.h"
Linus Torvalds750f7b62007-06-19 14:22:46 -07006#include "diffcore.h"
Peter Eriksen8e440252006-04-02 14:44:09 +02007#include "tree.h"
Linus Torvaldsac1b3d12005-10-20 21:05:05 -07008
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +07009static void show_entry(struct diff_options *opt, const char *prefix,
10 struct tree_desc *desc, struct strbuf *base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070011
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070012static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
13 struct strbuf *base, struct diff_options *opt)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070014{
15 unsigned mode1, mode2;
16 const char *path1, *path2;
17 const unsigned char *sha1, *sha2;
18 int cmp, pathlen1, pathlen2;
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070019 int old_baselen = base->len;
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070020
Linus Torvalds50f9a852006-01-31 14:10:56 -080021 sha1 = tree_entry_extract(t1, &path1, &mode1);
22 sha2 = tree_entry_extract(t2, &path2, &mode2);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070023
Nguyễn Thái Ngọc Duy0de16332011-10-24 17:36:09 +110024 pathlen1 = tree_entry_len(&t1->entry);
25 pathlen2 = tree_entry_len(&t2->entry);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070026 cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
27 if (cmp < 0) {
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070028 show_entry(opt, "-", t1, base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070029 return -1;
30 }
31 if (cmp > 0) {
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070032 show_entry(opt, "+", t2, base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070033 return 1;
34 }
Pierre Habouzit8f67f8a2007-11-10 20:05:14 +010035 if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070036 return 0;
37
38 /*
39 * If the filemode has changed to/from a directory from/to a regular
40 * file, we need to consider it a remove and an add.
41 */
42 if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070043 show_entry(opt, "-", t1, base);
44 show_entry(opt, "+", t2, base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070045 return 0;
46 }
47
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070048 strbuf_add(base, path1, pathlen1);
Pierre Habouzit8f67f8a2007-11-10 20:05:14 +010049 if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
Dmitry Potapovfd55a192008-07-16 18:54:02 +040050 if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070051 opt->change(opt, mode1, mode2,
Jeff Kinge5450102012-07-28 11:03:01 -040052 sha1, sha2, 1, 1, base->buf, 0, 0);
Dmitry Potapovfd55a192008-07-16 18:54:02 +040053 }
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070054 strbuf_addch(base, '/');
Johannes Schindelinc0aa3352011-03-22 13:50:08 +010055 diff_tree_sha1(sha1, sha2, base->buf, opt);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070056 } else {
Jeff Kinge5450102012-07-28 11:03:01 -040057 opt->change(opt, mode1, mode2, sha1, sha2, 1, 1, base->buf, 0, 0);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070058 }
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070059 strbuf_setlen(base, old_baselen);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070060 return 0;
61}
62
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070063/* A whole sub-tree went away or appeared */
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070064static void show_tree(struct diff_options *opt, const char *prefix,
65 struct tree_desc *desc, struct strbuf *base)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070066{
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +110067 enum interesting match = entry_not_interesting;
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +070068 for (; desc->size; update_tree_entry(desc)) {
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +110069 if (match != all_entries_interesting) {
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +070070 match = tree_entry_interesting(&desc->entry, base, 0,
71 &opt->pathspec);
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +110072 if (match == all_entries_not_interesting)
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +070073 break;
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +110074 if (match == entry_not_interesting)
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +070075 continue;
Junio C Hamano1d848f62007-03-21 17:00:27 -070076 }
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +070077 show_entry(opt, prefix, desc, base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070078 }
79}
80
81/* A file entry went away or appeared */
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070082static void show_entry(struct diff_options *opt, const char *prefix,
83 struct tree_desc *desc, struct strbuf *base)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070084{
85 unsigned mode;
86 const char *path;
Linus Torvalds50f9a852006-01-31 14:10:56 -080087 const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
Nguyễn Thái Ngọc Duy0de16332011-10-24 17:36:09 +110088 int pathlen = tree_entry_len(&desc->entry);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070089 int old_baselen = base->len;
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070090
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +070091 strbuf_add(base, path, pathlen);
Pierre Habouzit8f67f8a2007-11-10 20:05:14 +010092 if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
Nicolas Pitre21666f12007-02-26 14:55:59 -050093 enum object_type type;
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070094 struct tree_desc inner;
95 void *tree;
Linus Torvalds6fda5e52007-03-21 10:08:25 -070096 unsigned long size;
Linus Torvaldsac1b3d12005-10-20 21:05:05 -070097
Linus Torvalds6fda5e52007-03-21 10:08:25 -070098 tree = read_sha1_file(sha1, &type, &size);
Nicolas Pitre21666f12007-02-26 14:55:59 -050099 if (!tree || type != OBJ_TREE)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700100 die("corrupt tree sha %s", sha1_to_hex(sha1));
101
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700102 if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
Jeff Kinge5450102012-07-28 11:03:01 -0400103 opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700104
105 strbuf_addch(base, '/');
Nick Edelendf533f32009-06-13 17:06:09 -0700106
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700107 init_tree_desc(&inner, tree, size);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700108 show_tree(opt, prefix, &inner, base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700109 free(tree);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700110 } else
Jeff Kinge5450102012-07-28 11:03:01 -0400111 opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700112
113 strbuf_setlen(base, old_baselen);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700114}
115
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700116static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +1100117 struct diff_options *opt,
118 enum interesting *match)
Linus Torvalds5d865012007-03-18 15:18:30 -0700119{
120 while (t->size) {
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +0700121 *match = tree_entry_interesting(&t->entry, base, 0, &opt->pathspec);
122 if (*match) {
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +1100123 if (*match == all_entries_not_interesting)
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +0700124 t->size = 0;
125 break;
Linus Torvalds5d865012007-03-18 15:18:30 -0700126 }
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +0700127 update_tree_entry(t);
Linus Torvalds5d865012007-03-18 15:18:30 -0700128 }
129}
130
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700131int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
132 const char *base_str, struct diff_options *opt)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700133{
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700134 struct strbuf base;
135 int baselen = strlen(base_str);
Nguyễn Thái Ngọc Duyd688cf02011-10-24 17:36:10 +1100136 enum interesting t1_match = entry_not_interesting;
137 enum interesting t2_match = entry_not_interesting;
Linus Torvalds304de2d2007-03-17 20:06:24 -0700138
Nguyễn Thái Ngọc Duybc96cc82010-12-15 22:02:44 +0700139 /* Enable recursion indefinitely */
140 opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
141 opt->pathspec.max_depth = -1;
142
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700143 strbuf_init(&base, PATH_MAX);
144 strbuf_add(&base, base_str, baselen);
145
Linus Torvalds5d865012007-03-18 15:18:30 -0700146 for (;;) {
Junio C Hamano28b92642011-05-31 09:14:17 -0700147 if (diff_can_quit_early(opt))
Junio C Hamano822cac02007-03-14 11:12:51 -0700148 break;
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700149 if (opt->pathspec.nr) {
Nguyễn Thái Ngọc Duy97d0b742011-03-25 16:34:20 +0700150 skip_uninteresting(t1, &base, opt, &t1_match);
151 skip_uninteresting(t2, &base, opt, &t2_match);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700152 }
153 if (!t1->size) {
Linus Torvalds5d865012007-03-18 15:18:30 -0700154 if (!t2->size)
155 break;
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700156 show_entry(opt, "+", t2, &base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700157 update_tree_entry(t2);
158 continue;
159 }
160 if (!t2->size) {
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700161 show_entry(opt, "-", t1, &base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700162 update_tree_entry(t1);
163 continue;
164 }
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700165 switch (compare_tree_entry(t1, t2, &base, opt)) {
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700166 case -1:
167 update_tree_entry(t1);
168 continue;
169 case 0:
170 update_tree_entry(t1);
171 /* Fallthrough */
172 case 1:
173 update_tree_entry(t2);
174 continue;
175 }
Junio C Hamano7e44c932008-08-31 09:39:19 -0700176 die("git diff-tree: internal error");
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700177 }
Nguyễn Thái Ngọc Duy48932672010-12-15 22:02:42 +0700178
179 strbuf_release(&base);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700180 return 0;
181}
182
Linus Torvalds750f7b62007-06-19 14:22:46 -0700183/*
184 * Does it look like the resulting diff might be due to a rename?
185 * - single entry
186 * - not a valid previous file
187 */
188static inline int diff_might_be_rename(void)
189{
190 return diff_queued_diff.nr == 1 &&
191 !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
192}
193
194static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
195{
196 struct diff_options diff_opts;
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700197 struct diff_queue_struct *q = &diff_queued_diff;
198 struct diff_filepair *choice;
199 const char *paths[1];
Linus Torvalds750f7b62007-06-19 14:22:46 -0700200 int i;
201
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700202 /* Remove the file creation entry from the diff queue, and remember it */
203 choice = q->queue[0];
204 q->nr = 0;
205
Linus Torvalds750f7b62007-06-19 14:22:46 -0700206 diff_setup(&diff_opts);
Pierre Habouzit8f67f8a2007-11-10 20:05:14 +0100207 DIFF_OPT_SET(&diff_opts, RECURSIVE);
Bo Yang0cdca132010-05-06 21:52:29 -0700208 DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
Linus Torvalds750f7b62007-06-19 14:22:46 -0700209 diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700210 diff_opts.single_follow = opt->pathspec.raw[0];
Linus Torvalds6dd4b662007-10-20 12:31:31 -0700211 diff_opts.break_opt = opt->break_opt;
Jeff Kingdd98d882011-12-16 06:27:50 -0500212 diff_opts.rename_score = opt->rename_score;
Linus Torvalds750f7b62007-06-19 14:22:46 -0700213 paths[0] = NULL;
214 diff_tree_setup_paths(paths, &diff_opts);
Thomas Rast28452652012-08-03 14:16:24 +0200215 diff_setup_done(&diff_opts);
Linus Torvalds750f7b62007-06-19 14:22:46 -0700216 diff_tree(t1, t2, base, &diff_opts);
217 diffcore_std(&diff_opts);
Mike Hommey03b69c72007-12-11 22:59:55 +0100218 diff_tree_release_paths(&diff_opts);
Linus Torvalds750f7b62007-06-19 14:22:46 -0700219
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700220 /* Go through the new set of filepairing, and see if we find a more interesting one */
Junio C Hamano44c48a92010-08-13 12:17:45 -0700221 opt->found_follow = 0;
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700222 for (i = 0; i < q->nr; i++) {
223 struct diff_filepair *p = q->queue[i];
Linus Torvalds750f7b62007-06-19 14:22:46 -0700224
225 /*
226 * Found a source? Not only do we use that for the new
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700227 * diff_queued_diff, we will also use that as the path in
Linus Torvalds750f7b62007-06-19 14:22:46 -0700228 * the future!
229 */
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700230 if ((p->status == 'R' || p->status == 'C') &&
231 !strcmp(p->two->path, opt->pathspec.raw[0])) {
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700232 /* Switch the file-pairs around */
233 q->queue[i] = choice;
234 choice = p;
235
236 /* Update the path we use from now on.. */
Mike Hommey03b69c72007-12-11 22:59:55 +0100237 diff_tree_release_paths(opt);
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700238 opt->pathspec.raw[0] = xstrdup(p->one->path);
239 diff_tree_setup_paths(opt->pathspec.raw, opt);
Junio C Hamano44c48a92010-08-13 12:17:45 -0700240
241 /*
242 * The caller expects us to return a set of vanilla
243 * filepairs to let a later call to diffcore_std()
244 * it makes to sort the renames out (among other
245 * things), but we already have found renames
246 * ourselves; signal diffcore_std() not to muck with
247 * rename information.
248 */
249 opt->found_follow = 1;
Linus Torvalds750f7b62007-06-19 14:22:46 -0700250 break;
251 }
252 }
253
254 /*
Mike Ralphson3ea3c212009-04-17 19:13:30 +0100255 * Then, discard all the non-relevant file pairs...
Linus Torvalds750f7b62007-06-19 14:22:46 -0700256 */
Linus Torvalds9f38e1e2007-06-21 10:22:59 -0700257 for (i = 0; i < q->nr; i++) {
258 struct diff_filepair *p = q->queue[i];
259 diff_free_filepair(p);
260 }
261
262 /*
263 * .. and re-instate the one we want (which might be either the
264 * original one, or the rename/copy we found)
265 */
266 q->queue[0] = choice;
267 q->nr = 1;
Linus Torvalds750f7b62007-06-19 14:22:46 -0700268}
269
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700270int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
271{
272 void *tree1, *tree2;
273 struct tree_desc t1, t2;
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700274 unsigned long size1, size2;
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700275 int retval;
276
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700277 tree1 = read_object_with_reference(old, tree_type, &size1, NULL);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700278 if (!tree1)
279 die("unable to read source tree (%s)", sha1_to_hex(old));
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700280 tree2 = read_object_with_reference(new, tree_type, &size2, NULL);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700281 if (!tree2)
282 die("unable to read destination tree (%s)", sha1_to_hex(new));
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700283 init_tree_desc(&t1, tree1, size1);
284 init_tree_desc(&t2, tree2, size2);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700285 retval = diff_tree(&t1, &t2, base, opt);
Junio C Hamano39f75d22010-08-13 10:36:01 -0700286 if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
Linus Torvalds750f7b62007-06-19 14:22:46 -0700287 init_tree_desc(&t1, tree1, size1);
288 init_tree_desc(&t2, tree2, size2);
289 try_to_follow_renames(&t1, &t2, base, opt);
290 }
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700291 free(tree1);
292 free(tree2);
293 return retval;
294}
295
Rene Scharfe2b603562006-10-26 18:52:39 +0200296int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
297{
298 int retval;
299 void *tree;
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700300 unsigned long size;
Rene Scharfe2b603562006-10-26 18:52:39 +0200301 struct tree_desc empty, real;
302
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700303 tree = read_object_with_reference(new, tree_type, &size, NULL);
Rene Scharfe2b603562006-10-26 18:52:39 +0200304 if (!tree)
305 die("unable to read root tree (%s)", sha1_to_hex(new));
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700306 init_tree_desc(&real, tree, size);
Rene Scharfe2b603562006-10-26 18:52:39 +0200307
Linus Torvalds6fda5e52007-03-21 10:08:25 -0700308 init_tree_desc(&empty, "", 0);
Rene Scharfe2b603562006-10-26 18:52:39 +0200309 retval = diff_tree(&empty, &real, base, opt);
310 free(tree);
311 return retval;
312}
313
Junio C Hamanoa8baa7b2006-04-10 16:39:11 -0700314void diff_tree_release_paths(struct diff_options *opt)
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700315{
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700316 free_pathspec(&opt->pathspec);
Junio C Hamanoa8baa7b2006-04-10 16:39:11 -0700317}
318
319void diff_tree_setup_paths(const char **p, struct diff_options *opt)
320{
Nguyễn Thái Ngọc Duy66f13622010-12-15 22:02:38 +0700321 init_pathspec(&opt->pathspec, p);
Linus Torvaldsac1b3d12005-10-20 21:05:05 -0700322}