2 #include "range-diff.h"
3 #include "string-list.h"
4 #include "run-command.h"
5 #include "argv-array.h"
7 #include "xdiff-interface.h"
8 #include "linear-assignment.h"
16 /* For the search for an exact match */
17 struct hashmap_entry e
;
18 const char *diff
, *patch
;
23 /* the index of the matching item in the other branch, or -1 */
28 static size_t find_end_of_line(char *buffer
, unsigned long size
)
30 char *eol
= memchr(buffer
, '\n', size
);
36 return eol
+ 1 - buffer
;
40 * Reads the patches into a string list, with the `util` field being populated
41 * as struct object_id (will need to be free()d).
43 static int read_patches(const char *range
, struct string_list
*list
)
45 struct child_process cp
= CHILD_PROCESS_INIT
;
46 struct strbuf buf
= STRBUF_INIT
, contents
= STRBUF_INIT
;
47 struct patch_util
*util
= NULL
;
49 char *line
, *current_filename
= NULL
;
53 argv_array_pushl(&cp
.args
, "log", "--no-color", "-p", "--no-merges",
54 "--reverse", "--date-order", "--decorate=no",
56 * Choose indicators that are not used anywhere
57 * else in diffs, but still look reasonable
58 * (e.g. will not be confusing when debugging)
60 "--output-indicator-new=>",
61 "--output-indicator-old=<",
62 "--output-indicator-context=#",
63 "--no-abbrev-commit", range
,
69 if (start_command(&cp
))
70 return error_errno(_("could not start `log`"));
71 if (strbuf_read(&contents
, cp
.out
, 0) < 0) {
72 error_errno(_("could not read `log` output"));
79 for (offset
= 0; size
> 0; offset
+= len
, size
-= len
, line
+= len
) {
82 len
= find_end_of_line(line
, size
);
84 if (skip_prefix(line
, "commit ", &p
)) {
86 string_list_append(list
, buf
.buf
)->util
= util
;
89 util
= xcalloc(sizeof(*util
), 1);
90 if (get_oid(p
, &util
->oid
)) {
91 error(_("could not parse commit '%s'"), p
);
93 string_list_clear(list
, 1);
95 strbuf_release(&contents
);
104 if (starts_with(line
, "diff --git")) {
105 struct patch patch
= { 0 };
106 struct strbuf root
= STRBUF_INIT
;
110 strbuf_addch(&buf
, '\n');
111 if (!util
->diff_offset
)
112 util
->diff_offset
= buf
.len
;
113 line
[len
- 1] = '\n';
114 len
= parse_git_diff_header(&root
, &linenr
, 1, line
,
117 die(_("could not parse git header '%.*s'"), (int)len
, line
);
118 strbuf_addstr(&buf
, " ## ");
119 if (patch
.is_new
> 0)
120 strbuf_addf(&buf
, "%s (new)", patch
.new_name
);
121 else if (patch
.is_delete
> 0)
122 strbuf_addf(&buf
, "%s (deleted)", patch
.old_name
);
123 else if (patch
.is_rename
)
124 strbuf_addf(&buf
, "%s => %s", patch
.old_name
, patch
.new_name
);
126 strbuf_addstr(&buf
, patch
.new_name
);
128 free(current_filename
);
129 if (patch
.is_delete
> 0)
130 current_filename
= xstrdup(patch
.old_name
);
132 current_filename
= xstrdup(patch
.new_name
);
134 if (patch
.new_mode
&& patch
.old_mode
&&
135 patch
.old_mode
!= patch
.new_mode
)
136 strbuf_addf(&buf
, " (mode change %06o => %06o)",
137 patch
.old_mode
, patch
.new_mode
);
139 strbuf_addstr(&buf
, " ##");
140 } else if (in_header
) {
141 if (starts_with(line
, "Author: ")) {
142 strbuf_addstr(&buf
, " ## Metadata ##\n");
143 strbuf_addstr(&buf
, line
);
144 strbuf_addstr(&buf
, "\n\n");
145 strbuf_addstr(&buf
, " ## Commit message ##\n");
146 } else if (starts_with(line
, " ")) {
148 while (isspace(*p
) && p
>= line
)
150 strbuf_add(&buf
, line
, p
- line
+ 1);
151 strbuf_addch(&buf
, '\n');
154 } else if (skip_prefix(line
, "@@ ", &p
)) {
156 strbuf_addstr(&buf
, "@@");
157 if (current_filename
&& p
[2])
158 strbuf_addf(&buf
, " %s:", current_filename
);
160 strbuf_addstr(&buf
, p
+ 2);
163 * A completely blank (not ' \n', which is context)
164 * line is not valid in a diff. We skip it
165 * silently, because this neatly handles the blank
166 * separator line between commits in git-log
170 else if (line
[0] == '>') {
171 strbuf_addch(&buf
, '+');
172 strbuf_addstr(&buf
, line
+ 1);
173 } else if (line
[0] == '<') {
174 strbuf_addch(&buf
, '-');
175 strbuf_addstr(&buf
, line
+ 1);
176 } else if (line
[0] == '#') {
177 strbuf_addch(&buf
, ' ');
178 strbuf_addstr(&buf
, line
+ 1);
180 strbuf_addch(&buf
, ' ');
181 strbuf_addstr(&buf
, line
);
184 strbuf_addch(&buf
, '\n');
187 strbuf_release(&contents
);
190 string_list_append(list
, buf
.buf
)->util
= util
;
191 strbuf_release(&buf
);
192 free(current_filename
);
194 if (finish_command(&cp
))
200 static int patch_util_cmp(const void *dummy
, const struct patch_util
*a
,
201 const struct patch_util
*b
, const char *keydata
)
203 return strcmp(a
->diff
, keydata
? keydata
: b
->diff
);
206 static void find_exact_matches(struct string_list
*a
, struct string_list
*b
)
211 hashmap_init(&map
, (hashmap_cmp_fn
)patch_util_cmp
, NULL
, 0);
213 /* First, add the patches of a to a hash map */
214 for (i
= 0; i
< a
->nr
; i
++) {
215 struct patch_util
*util
= a
->items
[i
].util
;
218 util
->patch
= a
->items
[i
].string
;
219 util
->diff
= util
->patch
+ util
->diff_offset
;
220 hashmap_entry_init(&util
->e
, strhash(util
->diff
));
221 hashmap_add(&map
, &util
->e
);
224 /* Now try to find exact matches in b */
225 for (i
= 0; i
< b
->nr
; i
++) {
226 struct patch_util
*util
= b
->items
[i
].util
, *other
;
229 util
->patch
= b
->items
[i
].string
;
230 util
->diff
= util
->patch
+ util
->diff_offset
;
231 hashmap_entry_init(&util
->e
, strhash(util
->diff
));
232 other
= hashmap_remove_entry(&map
, util
, NULL
,
234 e
/* member name */);
236 if (other
->matching
>= 0)
237 BUG("already assigned!");
240 util
->matching
= other
->i
;
247 static void diffsize_consume(void *data
, char *line
, unsigned long len
)
252 static void diffsize_hunk(void *data
, long ob
, long on
, long nb
, long nn
,
253 const char *funcline
, long funclen
)
255 diffsize_consume(data
, NULL
, 0);
258 static int diffsize(const char *a
, const char *b
)
260 xpparam_t pp
= { 0 };
261 xdemitconf_t cfg
= { 0 };
266 mf1
.size
= strlen(a
);
268 mf2
.size
= strlen(b
);
271 if (!xdi_diff_outf(&mf1
, &mf2
,
272 diffsize_hunk
, diffsize_consume
, &count
,
276 error(_("failed to generate diff"));
280 static void get_correspondences(struct string_list
*a
, struct string_list
*b
,
283 int n
= a
->nr
+ b
->nr
;
284 int *cost
, c
, *a2b
, *b2a
;
287 ALLOC_ARRAY(cost
, st_mult(n
, n
));
291 for (i
= 0; i
< a
->nr
; i
++) {
292 struct patch_util
*a_util
= a
->items
[i
].util
;
294 for (j
= 0; j
< b
->nr
; j
++) {
295 struct patch_util
*b_util
= b
->items
[j
].util
;
297 if (a_util
->matching
== j
)
299 else if (a_util
->matching
< 0 && b_util
->matching
< 0)
300 c
= diffsize(a_util
->diff
, b_util
->diff
);
306 c
= a_util
->matching
< 0 ?
307 a_util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
308 for (j
= b
->nr
; j
< n
; j
++)
312 for (j
= 0; j
< b
->nr
; j
++) {
313 struct patch_util
*util
= b
->items
[j
].util
;
315 c
= util
->matching
< 0 ?
316 util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
317 for (i
= a
->nr
; i
< n
; i
++)
321 for (i
= a
->nr
; i
< n
; i
++)
322 for (j
= b
->nr
; j
< n
; j
++)
325 compute_assignment(n
, n
, cost
, a2b
, b2a
);
327 for (i
= 0; i
< a
->nr
; i
++)
328 if (a2b
[i
] >= 0 && a2b
[i
] < b
->nr
) {
329 struct patch_util
*a_util
= a
->items
[i
].util
;
330 struct patch_util
*b_util
= b
->items
[a2b
[i
]].util
;
332 a_util
->matching
= a2b
[i
];
333 b_util
->matching
= i
;
341 static void output_pair_header(struct diff_options
*diffopt
,
344 struct strbuf
*dashes
,
345 struct patch_util
*a_util
,
346 struct patch_util
*b_util
)
348 struct object_id
*oid
= a_util
? &a_util
->oid
: &b_util
->oid
;
349 struct commit
*commit
;
351 const char *color_reset
= diff_get_color_opt(diffopt
, DIFF_RESET
);
352 const char *color_old
= diff_get_color_opt(diffopt
, DIFF_FILE_OLD
);
353 const char *color_new
= diff_get_color_opt(diffopt
, DIFF_FILE_NEW
);
354 const char *color_commit
= diff_get_color_opt(diffopt
, DIFF_COMMIT
);
358 strbuf_addchars(dashes
, '-',
359 strlen(find_unique_abbrev(oid
,
365 } else if (!a_util
) {
368 } else if (strcmp(a_util
->patch
, b_util
->patch
)) {
369 color
= color_commit
;
372 color
= color_commit
;
377 strbuf_addstr(buf
, status
== '!' ? color_old
: color
);
379 strbuf_addf(buf
, "%*s: %s ", patch_no_width
, "-", dashes
->buf
);
381 strbuf_addf(buf
, "%*d: %s ", patch_no_width
, a_util
->i
+ 1,
382 find_unique_abbrev(&a_util
->oid
, DEFAULT_ABBREV
));
385 strbuf_addf(buf
, "%s%s", color_reset
, color
);
386 strbuf_addch(buf
, status
);
388 strbuf_addf(buf
, "%s%s", color_reset
, color_new
);
391 strbuf_addf(buf
, " %*s: %s", patch_no_width
, "-", dashes
->buf
);
393 strbuf_addf(buf
, " %*d: %s", patch_no_width
, b_util
->i
+ 1,
394 find_unique_abbrev(&b_util
->oid
, DEFAULT_ABBREV
));
396 commit
= lookup_commit_reference(the_repository
, oid
);
399 strbuf_addf(buf
, "%s%s", color_reset
, color
);
401 strbuf_addch(buf
, ' ');
402 pp_commit_easy(CMIT_FMT_ONELINE
, commit
, buf
);
404 strbuf_addf(buf
, "%s\n", color_reset
);
406 fwrite(buf
->buf
, buf
->len
, 1, diffopt
->file
);
409 static struct userdiff_driver section_headers
= {
410 .funcname
= { "^ ## (.*) ##$\n"
411 "^.?@@ (.*)$", REG_EXTENDED
}
414 static struct diff_filespec
*get_filespec(const char *name
, const char *p
)
416 struct diff_filespec
*spec
= alloc_filespec(name
);
418 fill_filespec(spec
, &null_oid
, 0, 0100644);
419 spec
->data
= (char *)p
;
420 spec
->size
= strlen(p
);
421 spec
->should_munmap
= 0;
423 spec
->driver
= §ion_headers
;
428 static void patch_diff(const char *a
, const char *b
,
429 struct diff_options
*diffopt
)
431 diff_queue(&diff_queued_diff
,
432 get_filespec("a", a
), get_filespec("b", b
));
434 diffcore_std(diffopt
);
438 static void output(struct string_list
*a
, struct string_list
*b
,
439 struct diff_options
*diffopt
)
441 struct strbuf buf
= STRBUF_INIT
, dashes
= STRBUF_INIT
;
442 int patch_no_width
= decimal_width(1 + (a
->nr
> b
->nr
? a
->nr
: b
->nr
));
446 * We assume the user is really more interested in the second argument
447 * ("newer" version). To that end, we print the output in the order of
448 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
449 * commits that are no longer in the RHS into a good place, we place
450 * them once we have shown all of their predecessors in the LHS.
453 while (i
< a
->nr
|| j
< b
->nr
) {
454 struct patch_util
*a_util
, *b_util
;
455 a_util
= i
< a
->nr
? a
->items
[i
].util
: NULL
;
456 b_util
= j
< b
->nr
? b
->items
[j
].util
: NULL
;
458 /* Skip all the already-shown commits from the LHS. */
459 while (i
< a
->nr
&& a_util
->shown
)
460 a_util
= ++i
< a
->nr
? a
->items
[i
].util
: NULL
;
462 /* Show unmatched LHS commit whose predecessors were shown. */
463 if (i
< a
->nr
&& a_util
->matching
< 0) {
464 output_pair_header(diffopt
, patch_no_width
,
465 &buf
, &dashes
, a_util
, NULL
);
470 /* Show unmatched RHS commits. */
471 while (j
< b
->nr
&& b_util
->matching
< 0) {
472 output_pair_header(diffopt
, patch_no_width
,
473 &buf
, &dashes
, NULL
, b_util
);
474 b_util
= ++j
< b
->nr
? b
->items
[j
].util
: NULL
;
477 /* Show matching LHS/RHS pair. */
479 a_util
= a
->items
[b_util
->matching
].util
;
480 output_pair_header(diffopt
, patch_no_width
,
481 &buf
, &dashes
, a_util
, b_util
);
482 if (!(diffopt
->output_format
& DIFF_FORMAT_NO_OUTPUT
))
483 patch_diff(a
->items
[b_util
->matching
].string
,
484 b
->items
[j
].string
, diffopt
);
489 strbuf_release(&buf
);
490 strbuf_release(&dashes
);
493 static struct strbuf
*output_prefix_cb(struct diff_options
*opt
, void *data
)
498 int show_range_diff(const char *range1
, const char *range2
,
499 int creation_factor
, int dual_color
,
500 struct diff_options
*diffopt
)
504 struct string_list branch1
= STRING_LIST_INIT_DUP
;
505 struct string_list branch2
= STRING_LIST_INIT_DUP
;
507 if (read_patches(range1
, &branch1
))
508 res
= error(_("could not parse log for '%s'"), range1
);
509 if (!res
&& read_patches(range2
, &branch2
))
510 res
= error(_("could not parse log for '%s'"), range2
);
513 struct diff_options opts
;
514 struct strbuf indent
= STRBUF_INIT
;
517 memcpy(&opts
, diffopt
, sizeof(opts
));
521 if (!opts
.output_format
)
522 opts
.output_format
= DIFF_FORMAT_PATCH
;
523 opts
.flags
.suppress_diff_headers
= 1;
524 opts
.flags
.dual_color_diffed_diffs
= dual_color
;
525 opts
.flags
.suppress_hunk_header_line_count
= 1;
526 opts
.output_prefix
= output_prefix_cb
;
527 strbuf_addstr(&indent
, " ");
528 opts
.output_prefix_data
= &indent
;
529 diff_setup_done(&opts
);
531 find_exact_matches(&branch1
, &branch2
);
532 get_correspondences(&branch1
, &branch2
, creation_factor
);
533 output(&branch1
, &branch2
, &opts
);
535 strbuf_release(&indent
);
538 string_list_clear(&branch1
, 1);
539 string_list_clear(&branch2
, 1);