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"
15 /* For the search for an exact match */
16 struct hashmap_entry e
;
17 const char *diff
, *patch
;
22 /* the index of the matching item in the other branch, or -1 */
28 * Reads the patches into a string list, with the `util` field being populated
29 * as struct object_id (will need to be free()d).
31 static int read_patches(const char *range
, struct string_list
*list
)
33 struct child_process cp
= CHILD_PROCESS_INIT
;
35 struct strbuf buf
= STRBUF_INIT
, line
= STRBUF_INIT
;
36 struct patch_util
*util
= NULL
;
39 argv_array_pushl(&cp
.args
, "log", "--no-color", "-p", "--no-merges",
40 "--reverse", "--date-order", "--decorate=no",
42 * Choose indicators that are not used anywhere
43 * else in diffs, but still look reasonable
44 * (e.g. will not be confusing when debugging)
46 "--output-indicator-new=>",
47 "--output-indicator-old=<",
48 "--output-indicator-context=#",
49 "--no-abbrev-commit", range
,
55 if (start_command(&cp
))
56 return error_errno(_("could not start `log`"));
57 in
= fdopen(cp
.out
, "r");
59 error_errno(_("could not read `log` output"));
64 while (strbuf_getline(&line
, in
) != EOF
) {
67 if (skip_prefix(line
.buf
, "commit ", &p
)) {
69 string_list_append(list
, buf
.buf
)->util
= util
;
72 util
= xcalloc(sizeof(*util
), 1);
73 if (get_oid(p
, &util
->oid
)) {
74 error(_("could not parse commit '%s'"), p
);
76 string_list_clear(list
, 1);
78 strbuf_release(&line
);
88 if (starts_with(line
.buf
, "diff --git")) {
90 strbuf_addch(&buf
, '\n');
91 if (!util
->diff_offset
)
92 util
->diff_offset
= buf
.len
;
93 strbuf_addbuf(&buf
, &line
);
94 } else if (in_header
) {
95 if (starts_with(line
.buf
, "Author: ")) {
96 strbuf_addbuf(&buf
, &line
);
97 strbuf_addstr(&buf
, "\n\n");
98 } else if (starts_with(line
.buf
, " ")) {
100 strbuf_addbuf(&buf
, &line
);
101 strbuf_addch(&buf
, '\n');
104 } else if (starts_with(line
.buf
, "@@ "))
105 strbuf_addstr(&buf
, "@@");
106 else if (!line
.buf
[0] || starts_with(line
.buf
, "index "))
108 * A completely blank (not ' \n', which is context)
109 * line is not valid in a diff. We skip it
110 * silently, because this neatly handles the blank
111 * separator line between commits in git-log
114 * We also want to ignore the diff's `index` lines
115 * because they contain exact blob hashes in which
116 * we are not interested.
119 else if (line
.buf
[0] == '>') {
120 strbuf_addch(&buf
, '+');
121 strbuf_add(&buf
, line
.buf
+ 1, line
.len
- 1);
122 } else if (line
.buf
[0] == '<') {
123 strbuf_addch(&buf
, '-');
124 strbuf_add(&buf
, line
.buf
+ 1, line
.len
- 1);
125 } else if (line
.buf
[0] == '#') {
126 strbuf_addch(&buf
, ' ');
127 strbuf_add(&buf
, line
.buf
+ 1, line
.len
- 1);
129 strbuf_addbuf(&buf
, &line
);
132 strbuf_addch(&buf
, '\n');
136 strbuf_release(&line
);
139 string_list_append(list
, buf
.buf
)->util
= util
;
140 strbuf_release(&buf
);
142 if (finish_command(&cp
))
148 static int patch_util_cmp(const void *dummy
, const struct patch_util
*a
,
149 const struct patch_util
*b
, const char *keydata
)
151 return strcmp(a
->diff
, keydata
? keydata
: b
->diff
);
154 static void find_exact_matches(struct string_list
*a
, struct string_list
*b
)
159 hashmap_init(&map
, (hashmap_cmp_fn
)patch_util_cmp
, NULL
, 0);
161 /* First, add the patches of a to a hash map */
162 for (i
= 0; i
< a
->nr
; i
++) {
163 struct patch_util
*util
= a
->items
[i
].util
;
166 util
->patch
= a
->items
[i
].string
;
167 util
->diff
= util
->patch
+ util
->diff_offset
;
168 hashmap_entry_init(util
, strhash(util
->diff
));
169 hashmap_add(&map
, util
);
172 /* Now try to find exact matches in b */
173 for (i
= 0; i
< b
->nr
; i
++) {
174 struct patch_util
*util
= b
->items
[i
].util
, *other
;
177 util
->patch
= b
->items
[i
].string
;
178 util
->diff
= util
->patch
+ util
->diff_offset
;
179 hashmap_entry_init(util
, strhash(util
->diff
));
180 other
= hashmap_remove(&map
, util
, NULL
);
182 if (other
->matching
>= 0)
183 BUG("already assigned!");
186 util
->matching
= other
->i
;
190 hashmap_free(&map
, 0);
193 static void diffsize_consume(void *data
, char *line
, unsigned long len
)
198 static int diffsize(const char *a
, const char *b
)
200 xpparam_t pp
= { 0 };
201 xdemitconf_t cfg
= { 0 };
206 mf1
.size
= strlen(a
);
208 mf2
.size
= strlen(b
);
211 if (!xdi_diff_outf(&mf1
, &mf2
, diffsize_consume
, &count
, &pp
, &cfg
))
214 error(_("failed to generate diff"));
218 static void get_correspondences(struct string_list
*a
, struct string_list
*b
,
221 int n
= a
->nr
+ b
->nr
;
222 int *cost
, c
, *a2b
, *b2a
;
225 ALLOC_ARRAY(cost
, st_mult(n
, n
));
229 for (i
= 0; i
< a
->nr
; i
++) {
230 struct patch_util
*a_util
= a
->items
[i
].util
;
232 for (j
= 0; j
< b
->nr
; j
++) {
233 struct patch_util
*b_util
= b
->items
[j
].util
;
235 if (a_util
->matching
== j
)
237 else if (a_util
->matching
< 0 && b_util
->matching
< 0)
238 c
= diffsize(a_util
->diff
, b_util
->diff
);
244 c
= a_util
->matching
< 0 ?
245 a_util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
246 for (j
= b
->nr
; j
< n
; j
++)
250 for (j
= 0; j
< b
->nr
; j
++) {
251 struct patch_util
*util
= b
->items
[j
].util
;
253 c
= util
->matching
< 0 ?
254 util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
255 for (i
= a
->nr
; i
< n
; i
++)
259 for (i
= a
->nr
; i
< n
; i
++)
260 for (j
= b
->nr
; j
< n
; j
++)
263 compute_assignment(n
, n
, cost
, a2b
, b2a
);
265 for (i
= 0; i
< a
->nr
; i
++)
266 if (a2b
[i
] >= 0 && a2b
[i
] < b
->nr
) {
267 struct patch_util
*a_util
= a
->items
[i
].util
;
268 struct patch_util
*b_util
= b
->items
[a2b
[i
]].util
;
270 a_util
->matching
= a2b
[i
];
271 b_util
->matching
= i
;
279 static void output_pair_header(struct diff_options
*diffopt
,
282 struct strbuf
*dashes
,
283 struct patch_util
*a_util
,
284 struct patch_util
*b_util
)
286 struct object_id
*oid
= a_util
? &a_util
->oid
: &b_util
->oid
;
287 struct commit
*commit
;
289 const char *color_reset
= diff_get_color_opt(diffopt
, DIFF_RESET
);
290 const char *color_old
= diff_get_color_opt(diffopt
, DIFF_FILE_OLD
);
291 const char *color_new
= diff_get_color_opt(diffopt
, DIFF_FILE_NEW
);
292 const char *color_commit
= diff_get_color_opt(diffopt
, DIFF_COMMIT
);
296 strbuf_addchars(dashes
, '-',
297 strlen(find_unique_abbrev(oid
,
303 } else if (!a_util
) {
306 } else if (strcmp(a_util
->patch
, b_util
->patch
)) {
307 color
= color_commit
;
310 color
= color_commit
;
315 strbuf_addstr(buf
, status
== '!' ? color_old
: color
);
317 strbuf_addf(buf
, "%*s: %s ", patch_no_width
, "-", dashes
->buf
);
319 strbuf_addf(buf
, "%*d: %s ", patch_no_width
, a_util
->i
+ 1,
320 find_unique_abbrev(&a_util
->oid
, DEFAULT_ABBREV
));
323 strbuf_addf(buf
, "%s%s", color_reset
, color
);
324 strbuf_addch(buf
, status
);
326 strbuf_addf(buf
, "%s%s", color_reset
, color_new
);
329 strbuf_addf(buf
, " %*s: %s", patch_no_width
, "-", dashes
->buf
);
331 strbuf_addf(buf
, " %*d: %s", patch_no_width
, b_util
->i
+ 1,
332 find_unique_abbrev(&b_util
->oid
, DEFAULT_ABBREV
));
334 commit
= lookup_commit_reference(the_repository
, oid
);
337 strbuf_addf(buf
, "%s%s", color_reset
, color
);
339 strbuf_addch(buf
, ' ');
340 pp_commit_easy(CMIT_FMT_ONELINE
, commit
, buf
);
342 strbuf_addf(buf
, "%s\n", color_reset
);
344 fwrite(buf
->buf
, buf
->len
, 1, stdout
);
347 static struct userdiff_driver no_func_name
= {
348 .funcname
= { "$^", 0 }
351 static struct diff_filespec
*get_filespec(const char *name
, const char *p
)
353 struct diff_filespec
*spec
= alloc_filespec(name
);
355 fill_filespec(spec
, &null_oid
, 0, 0644);
356 spec
->data
= (char *)p
;
357 spec
->size
= strlen(p
);
358 spec
->should_munmap
= 0;
360 spec
->driver
= &no_func_name
;
365 static void patch_diff(const char *a
, const char *b
,
366 struct diff_options
*diffopt
)
368 diff_queue(&diff_queued_diff
,
369 get_filespec("a", a
), get_filespec("b", b
));
371 diffcore_std(diffopt
);
375 static void output(struct string_list
*a
, struct string_list
*b
,
376 struct diff_options
*diffopt
)
378 struct strbuf buf
= STRBUF_INIT
, dashes
= STRBUF_INIT
;
379 int patch_no_width
= decimal_width(1 + (a
->nr
> b
->nr
? a
->nr
: b
->nr
));
383 * We assume the user is really more interested in the second argument
384 * ("newer" version). To that end, we print the output in the order of
385 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
386 * commits that are no longer in the RHS into a good place, we place
387 * them once we have shown all of their predecessors in the LHS.
390 while (i
< a
->nr
|| j
< b
->nr
) {
391 struct patch_util
*a_util
, *b_util
;
392 a_util
= i
< a
->nr
? a
->items
[i
].util
: NULL
;
393 b_util
= j
< b
->nr
? b
->items
[j
].util
: NULL
;
395 /* Skip all the already-shown commits from the LHS. */
396 while (i
< a
->nr
&& a_util
->shown
)
397 a_util
= ++i
< a
->nr
? a
->items
[i
].util
: NULL
;
399 /* Show unmatched LHS commit whose predecessors were shown. */
400 if (i
< a
->nr
&& a_util
->matching
< 0) {
401 output_pair_header(diffopt
, patch_no_width
,
402 &buf
, &dashes
, a_util
, NULL
);
407 /* Show unmatched RHS commits. */
408 while (j
< b
->nr
&& b_util
->matching
< 0) {
409 output_pair_header(diffopt
, patch_no_width
,
410 &buf
, &dashes
, NULL
, b_util
);
411 b_util
= ++j
< b
->nr
? b
->items
[j
].util
: NULL
;
414 /* Show matching LHS/RHS pair. */
416 a_util
= a
->items
[b_util
->matching
].util
;
417 output_pair_header(diffopt
, patch_no_width
,
418 &buf
, &dashes
, a_util
, b_util
);
419 if (!(diffopt
->output_format
& DIFF_FORMAT_NO_OUTPUT
))
420 patch_diff(a
->items
[b_util
->matching
].string
,
421 b
->items
[j
].string
, diffopt
);
426 strbuf_release(&buf
);
427 strbuf_release(&dashes
);
430 int show_range_diff(const char *range1
, const char *range2
,
431 int creation_factor
, struct diff_options
*diffopt
)
435 struct string_list branch1
= STRING_LIST_INIT_DUP
;
436 struct string_list branch2
= STRING_LIST_INIT_DUP
;
438 if (read_patches(range1
, &branch1
))
439 res
= error(_("could not parse log for '%s'"), range1
);
440 if (!res
&& read_patches(range2
, &branch2
))
441 res
= error(_("could not parse log for '%s'"), range2
);
444 find_exact_matches(&branch1
, &branch2
);
445 get_correspondences(&branch1
, &branch2
, creation_factor
);
446 output(&branch1
, &branch2
, diffopt
);
449 string_list_clear(&branch1
, 1);
450 string_list_clear(&branch2
, 1);