2 * Helper functions for tree diff generation
9 static char *malloc_base(const char *base
, int baselen
, const char *path
, int pathlen
)
11 char *newbase
= xmalloc(baselen
+ pathlen
+ 2);
12 memcpy(newbase
, base
, baselen
);
13 memcpy(newbase
+ baselen
, path
, pathlen
);
14 memcpy(newbase
+ baselen
+ pathlen
, "/", 2);
18 static char *malloc_fullname(const char *base
, int baselen
, const char *path
, int pathlen
)
20 char *fullname
= xmalloc(baselen
+ pathlen
+ 1);
21 memcpy(fullname
, base
, baselen
);
22 memcpy(fullname
+ baselen
, path
, pathlen
);
23 fullname
[baselen
+ pathlen
] = 0;
27 static void show_entry(struct diff_options
*opt
, const char *prefix
, struct tree_desc
*desc
,
28 const char *base
, int baselen
);
30 static int compare_tree_entry(struct tree_desc
*t1
, struct tree_desc
*t2
, const char *base
, int baselen
, struct diff_options
*opt
)
32 unsigned mode1
, mode2
;
33 const char *path1
, *path2
;
34 const unsigned char *sha1
, *sha2
;
35 int cmp
, pathlen1
, pathlen2
;
38 sha1
= tree_entry_extract(t1
, &path1
, &mode1
);
39 sha2
= tree_entry_extract(t2
, &path2
, &mode2
);
41 pathlen1
= tree_entry_len(path1
, sha1
);
42 pathlen2
= tree_entry_len(path2
, sha2
);
43 cmp
= base_name_compare(path1
, pathlen1
, mode1
, path2
, pathlen2
, mode2
);
45 show_entry(opt
, "-", t1
, base
, baselen
);
49 show_entry(opt
, "+", t2
, base
, baselen
);
52 if (!DIFF_OPT_TST(opt
, FIND_COPIES_HARDER
) && !hashcmp(sha1
, sha2
) && mode1
== mode2
)
56 * If the filemode has changed to/from a directory from/to a regular
57 * file, we need to consider it a remove and an add.
59 if (S_ISDIR(mode1
) != S_ISDIR(mode2
)) {
60 show_entry(opt
, "-", t1
, base
, baselen
);
61 show_entry(opt
, "+", t2
, base
, baselen
);
65 if (DIFF_OPT_TST(opt
, RECURSIVE
) && S_ISDIR(mode1
)) {
67 char *newbase
= malloc_base(base
, baselen
, path1
, pathlen1
);
68 if (DIFF_OPT_TST(opt
, TREE_IN_RECURSIVE
)) {
69 newbase
[baselen
+ pathlen1
] = 0;
70 opt
->change(opt
, mode1
, mode2
,
71 sha1
, sha2
, newbase
, 0, 0);
72 newbase
[baselen
+ pathlen1
] = '/';
74 retval
= diff_tree_sha1(sha1
, sha2
, newbase
, opt
);
79 fullname
= malloc_fullname(base
, baselen
, path1
, pathlen1
);
80 opt
->change(opt
, mode1
, mode2
, sha1
, sha2
, fullname
, 0, 0);
86 * Is a tree entry interesting given the pathspec we have?
88 * Pre-condition: baselen == 0 || base[baselen-1] == '/'
91 * - 2 for "yes, and all subsequent entries will be"
94 * - negative for "no, and no subsequent entries will be either"
96 static int tree_entry_interesting(struct tree_desc
*desc
, const char *base
, int baselen
, struct diff_options
*opt
)
99 const unsigned char *sha1
;
103 int never_interesting
= -1;
105 if (!opt
->pathspec
.nr
)
108 sha1
= tree_entry_extract(desc
, &path
, &mode
);
110 pathlen
= tree_entry_len(path
, sha1
);
112 for (i
= 0; i
< opt
->pathspec
.nr
; i
++) {
113 const struct pathspec_item
*item
= opt
->pathspec
.items
+i
;
114 const char *match
= item
->match
;
115 int matchlen
= item
->len
;
116 int m
= -1; /* signals that we haven't called strncmp() */
118 if (baselen
>= matchlen
) {
119 /* If it doesn't match, move along... */
120 if (strncmp(base
, match
, matchlen
))
124 * If the base is a subdirectory of a path which
125 * was specified, all of them are interesting.
128 base
[matchlen
] == '/' ||
129 match
[matchlen
- 1] == '/')
132 /* Just a random prefix match */
136 /* Does the base match? */
137 if (strncmp(base
, match
, baselen
))
143 if (never_interesting
) {
145 * We have not seen any match that sorts later
146 * than the current path.
150 * Does match sort strictly earlier than path
151 * with their common parts?
153 m
= strncmp(match
, path
,
154 (matchlen
< pathlen
) ? matchlen
: pathlen
);
159 * If we come here even once, that means there is at
160 * least one pathspec that would sort equal to or
161 * later than the path we are currently looking at.
162 * In other words, if we have never reached this point
163 * after iterating all pathspecs, it means all
164 * pathspecs are either outside of base, or inside the
165 * base but sorts strictly earlier than the current
166 * one. In either case, they will never match the
167 * subsequent entries. In such a case, we initialized
168 * the variable to -1 and that is what will be
169 * returned, allowing the caller to terminate early.
171 never_interesting
= 0;
174 if (pathlen
> matchlen
)
177 if (matchlen
> pathlen
) {
178 if (match
[pathlen
] != '/')
186 * we cheated and did not do strncmp(), so we do
189 m
= strncmp(match
, path
, pathlen
);
192 * If common part matched earlier then it is a hit,
193 * because we rejected the case where path is not a
194 * leading directory and is shorter than match.
199 return never_interesting
; /* No matches */
202 /* A whole sub-tree went away or appeared */
203 static void show_tree(struct diff_options
*opt
, const char *prefix
, struct tree_desc
*desc
, const char *base
, int baselen
)
205 int all_interesting
= 0;
212 show
= tree_entry_interesting(desc
, base
, baselen
,
220 show_entry(opt
, prefix
, desc
, base
, baselen
);
221 update_tree_entry(desc
);
225 /* A file entry went away or appeared */
226 static void show_entry(struct diff_options
*opt
, const char *prefix
, struct tree_desc
*desc
,
227 const char *base
, int baselen
)
231 const unsigned char *sha1
= tree_entry_extract(desc
, &path
, &mode
);
232 int pathlen
= tree_entry_len(path
, sha1
);
234 if (DIFF_OPT_TST(opt
, RECURSIVE
) && S_ISDIR(mode
)) {
235 enum object_type type
;
236 char *newbase
= malloc_base(base
, baselen
, path
, pathlen
);
237 struct tree_desc inner
;
241 tree
= read_sha1_file(sha1
, &type
, &size
);
242 if (!tree
|| type
!= OBJ_TREE
)
243 die("corrupt tree sha %s", sha1_to_hex(sha1
));
245 if (DIFF_OPT_TST(opt
, TREE_IN_RECURSIVE
)) {
246 newbase
[baselen
+ pathlen
] = 0;
247 opt
->add_remove(opt
, *prefix
, mode
, sha1
, newbase
, 0);
248 newbase
[baselen
+ pathlen
] = '/';
251 init_tree_desc(&inner
, tree
, size
);
252 show_tree(opt
, prefix
, &inner
, newbase
, baselen
+ 1 + pathlen
);
257 char *fullname
= malloc_fullname(base
, baselen
, path
, pathlen
);
258 opt
->add_remove(opt
, prefix
[0], mode
, sha1
, fullname
, 0);
263 static void skip_uninteresting(struct tree_desc
*t
, const char *base
, int baselen
, struct diff_options
*opt
, int *all_interesting
)
266 int show
= tree_entry_interesting(t
, base
, baselen
, opt
);
268 *all_interesting
= 1;
270 update_tree_entry(t
);
280 int diff_tree(struct tree_desc
*t1
, struct tree_desc
*t2
, const char *base
, struct diff_options
*opt
)
282 int baselen
= strlen(base
);
283 int all_t1_interesting
= 0;
284 int all_t2_interesting
= 0;
287 if (DIFF_OPT_TST(opt
, QUICK
) &&
288 DIFF_OPT_TST(opt
, HAS_CHANGES
))
290 if (opt
->pathspec
.nr
) {
291 if (!all_t1_interesting
)
292 skip_uninteresting(t1
, base
, baselen
, opt
,
293 &all_t1_interesting
);
294 if (!all_t2_interesting
)
295 skip_uninteresting(t2
, base
, baselen
, opt
,
296 &all_t2_interesting
);
301 show_entry(opt
, "+", t2
, base
, baselen
);
302 update_tree_entry(t2
);
306 show_entry(opt
, "-", t1
, base
, baselen
);
307 update_tree_entry(t1
);
310 switch (compare_tree_entry(t1
, t2
, base
, baselen
, opt
)) {
312 update_tree_entry(t1
);
315 update_tree_entry(t1
);
318 update_tree_entry(t2
);
321 die("git diff-tree: internal error");
327 * Does it look like the resulting diff might be due to a rename?
329 * - not a valid previous file
331 static inline int diff_might_be_rename(void)
333 return diff_queued_diff
.nr
== 1 &&
334 !DIFF_FILE_VALID(diff_queued_diff
.queue
[0]->one
);
337 static void try_to_follow_renames(struct tree_desc
*t1
, struct tree_desc
*t2
, const char *base
, struct diff_options
*opt
)
339 struct diff_options diff_opts
;
340 struct diff_queue_struct
*q
= &diff_queued_diff
;
341 struct diff_filepair
*choice
;
342 const char *paths
[1];
345 /* Remove the file creation entry from the diff queue, and remember it */
346 choice
= q
->queue
[0];
349 diff_setup(&diff_opts
);
350 DIFF_OPT_SET(&diff_opts
, RECURSIVE
);
351 DIFF_OPT_SET(&diff_opts
, FIND_COPIES_HARDER
);
352 diff_opts
.output_format
= DIFF_FORMAT_NO_OUTPUT
;
353 diff_opts
.single_follow
= opt
->pathspec
.raw
[0];
354 diff_opts
.break_opt
= opt
->break_opt
;
356 diff_tree_setup_paths(paths
, &diff_opts
);
357 if (diff_setup_done(&diff_opts
) < 0)
358 die("unable to set up diff options to follow renames");
359 diff_tree(t1
, t2
, base
, &diff_opts
);
360 diffcore_std(&diff_opts
);
361 diff_tree_release_paths(&diff_opts
);
363 /* Go through the new set of filepairing, and see if we find a more interesting one */
364 opt
->found_follow
= 0;
365 for (i
= 0; i
< q
->nr
; i
++) {
366 struct diff_filepair
*p
= q
->queue
[i
];
369 * Found a source? Not only do we use that for the new
370 * diff_queued_diff, we will also use that as the path in
373 if ((p
->status
== 'R' || p
->status
== 'C') &&
374 !strcmp(p
->two
->path
, opt
->pathspec
.raw
[0])) {
375 /* Switch the file-pairs around */
376 q
->queue
[i
] = choice
;
379 /* Update the path we use from now on.. */
380 diff_tree_release_paths(opt
);
381 opt
->pathspec
.raw
[0] = xstrdup(p
->one
->path
);
382 diff_tree_setup_paths(opt
->pathspec
.raw
, opt
);
385 * The caller expects us to return a set of vanilla
386 * filepairs to let a later call to diffcore_std()
387 * it makes to sort the renames out (among other
388 * things), but we already have found renames
389 * ourselves; signal diffcore_std() not to muck with
390 * rename information.
392 opt
->found_follow
= 1;
398 * Then, discard all the non-relevant file pairs...
400 for (i
= 0; i
< q
->nr
; i
++) {
401 struct diff_filepair
*p
= q
->queue
[i
];
402 diff_free_filepair(p
);
406 * .. and re-instate the one we want (which might be either the
407 * original one, or the rename/copy we found)
409 q
->queue
[0] = choice
;
413 int diff_tree_sha1(const unsigned char *old
, const unsigned char *new, const char *base
, struct diff_options
*opt
)
416 struct tree_desc t1
, t2
;
417 unsigned long size1
, size2
;
420 tree1
= read_object_with_reference(old
, tree_type
, &size1
, NULL
);
422 die("unable to read source tree (%s)", sha1_to_hex(old
));
423 tree2
= read_object_with_reference(new, tree_type
, &size2
, NULL
);
425 die("unable to read destination tree (%s)", sha1_to_hex(new));
426 init_tree_desc(&t1
, tree1
, size1
);
427 init_tree_desc(&t2
, tree2
, size2
);
428 retval
= diff_tree(&t1
, &t2
, base
, opt
);
429 if (!*base
&& DIFF_OPT_TST(opt
, FOLLOW_RENAMES
) && diff_might_be_rename()) {
430 init_tree_desc(&t1
, tree1
, size1
);
431 init_tree_desc(&t2
, tree2
, size2
);
432 try_to_follow_renames(&t1
, &t2
, base
, opt
);
439 int diff_root_tree_sha1(const unsigned char *new, const char *base
, struct diff_options
*opt
)
444 struct tree_desc empty
, real
;
446 tree
= read_object_with_reference(new, tree_type
, &size
, NULL
);
448 die("unable to read root tree (%s)", sha1_to_hex(new));
449 init_tree_desc(&real
, tree
, size
);
451 init_tree_desc(&empty
, "", 0);
452 retval
= diff_tree(&empty
, &real
, base
, opt
);
457 void diff_tree_release_paths(struct diff_options
*opt
)
459 free_pathspec(&opt
->pathspec
);
462 void diff_tree_setup_paths(const char **p
, struct diff_options
*opt
)
464 init_pathspec(&opt
->pathspec
, p
);