]>
Commit | Line | Data |
---|---|---|
d9c66f0b JS |
1 | #include "cache.h" |
2 | #include "range-diff.h" | |
3 | #include "string-list.h" | |
4 | #include "run-command.h" | |
5 | #include "argv-array.h" | |
6 | #include "hashmap.h" | |
7 | #include "xdiff-interface.h" | |
8 | #include "linear-assignment.h" | |
c8c5e43a | 9 | #include "diffcore.h" |
eb0be38c JS |
10 | #include "commit.h" |
11 | #include "pretty.h" | |
4eba1fe6 | 12 | #include "userdiff.h" |
d9c66f0b JS |
13 | |
14 | struct patch_util { | |
15 | /* For the search for an exact match */ | |
16 | struct hashmap_entry e; | |
17 | const char *diff, *patch; | |
18 | ||
9dc46e02 | 19 | int i, shown; |
d9c66f0b JS |
20 | int diffsize; |
21 | size_t diff_offset; | |
22 | /* the index of the matching item in the other branch, or -1 */ | |
23 | int matching; | |
24 | struct object_id oid; | |
25 | }; | |
26 | ||
27 | /* | |
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). | |
30 | */ | |
31 | static int read_patches(const char *range, struct string_list *list) | |
32 | { | |
33 | struct child_process cp = CHILD_PROCESS_INIT; | |
34 | FILE *in; | |
35 | struct strbuf buf = STRBUF_INIT, line = STRBUF_INIT; | |
36 | struct patch_util *util = NULL; | |
37 | int in_header = 1; | |
38 | ||
39 | argv_array_pushl(&cp.args, "log", "--no-color", "-p", "--no-merges", | |
40 | "--reverse", "--date-order", "--decorate=no", | |
8d5ccb59 SB |
41 | /* |
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) | |
45 | */ | |
46 | "--output-indicator-new=>", | |
47 | "--output-indicator-old=<", | |
48 | "--output-indicator-context=#", | |
d9c66f0b JS |
49 | "--no-abbrev-commit", range, |
50 | NULL); | |
51 | cp.out = -1; | |
52 | cp.no_stdin = 1; | |
53 | cp.git_cmd = 1; | |
54 | ||
55 | if (start_command(&cp)) | |
56 | return error_errno(_("could not start `log`")); | |
57 | in = fdopen(cp.out, "r"); | |
58 | if (!in) { | |
59 | error_errno(_("could not read `log` output")); | |
60 | finish_command(&cp); | |
61 | return -1; | |
62 | } | |
63 | ||
64 | while (strbuf_getline(&line, in) != EOF) { | |
65 | const char *p; | |
66 | ||
67 | if (skip_prefix(line.buf, "commit ", &p)) { | |
68 | if (util) { | |
69 | string_list_append(list, buf.buf)->util = util; | |
70 | strbuf_reset(&buf); | |
71 | } | |
72 | util = xcalloc(sizeof(*util), 1); | |
73 | if (get_oid(p, &util->oid)) { | |
74 | error(_("could not parse commit '%s'"), p); | |
75 | free(util); | |
76 | string_list_clear(list, 1); | |
77 | strbuf_release(&buf); | |
78 | strbuf_release(&line); | |
79 | fclose(in); | |
80 | finish_command(&cp); | |
81 | return -1; | |
82 | } | |
83 | util->matching = -1; | |
84 | in_header = 1; | |
85 | continue; | |
86 | } | |
87 | ||
88 | if (starts_with(line.buf, "diff --git")) { | |
89 | in_header = 0; | |
90 | strbuf_addch(&buf, '\n'); | |
91 | if (!util->diff_offset) | |
92 | util->diff_offset = buf.len; | |
2543a641 | 93 | strbuf_addch(&buf, ' '); |
d9c66f0b JS |
94 | strbuf_addbuf(&buf, &line); |
95 | } else if (in_header) { | |
96 | if (starts_with(line.buf, "Author: ")) { | |
97 | strbuf_addbuf(&buf, &line); | |
98 | strbuf_addstr(&buf, "\n\n"); | |
99 | } else if (starts_with(line.buf, " ")) { | |
a142f978 | 100 | strbuf_rtrim(&line); |
d9c66f0b JS |
101 | strbuf_addbuf(&buf, &line); |
102 | strbuf_addch(&buf, '\n'); | |
103 | } | |
104 | continue; | |
105 | } else if (starts_with(line.buf, "@@ ")) | |
106 | strbuf_addstr(&buf, "@@"); | |
107 | else if (!line.buf[0] || starts_with(line.buf, "index ")) | |
108 | /* | |
109 | * A completely blank (not ' \n', which is context) | |
110 | * line is not valid in a diff. We skip it | |
111 | * silently, because this neatly handles the blank | |
112 | * separator line between commits in git-log | |
113 | * output. | |
114 | * | |
115 | * We also want to ignore the diff's `index` lines | |
116 | * because they contain exact blob hashes in which | |
117 | * we are not interested. | |
118 | */ | |
119 | continue; | |
8d5ccb59 SB |
120 | else if (line.buf[0] == '>') { |
121 | strbuf_addch(&buf, '+'); | |
122 | strbuf_add(&buf, line.buf + 1, line.len - 1); | |
123 | } else if (line.buf[0] == '<') { | |
124 | strbuf_addch(&buf, '-'); | |
125 | strbuf_add(&buf, line.buf + 1, line.len - 1); | |
126 | } else if (line.buf[0] == '#') { | |
127 | strbuf_addch(&buf, ' '); | |
128 | strbuf_add(&buf, line.buf + 1, line.len - 1); | |
129 | } else { | |
2543a641 | 130 | strbuf_addch(&buf, ' '); |
d9c66f0b | 131 | strbuf_addbuf(&buf, &line); |
8d5ccb59 | 132 | } |
d9c66f0b JS |
133 | |
134 | strbuf_addch(&buf, '\n'); | |
135 | util->diffsize++; | |
136 | } | |
137 | fclose(in); | |
138 | strbuf_release(&line); | |
139 | ||
140 | if (util) | |
141 | string_list_append(list, buf.buf)->util = util; | |
142 | strbuf_release(&buf); | |
143 | ||
144 | if (finish_command(&cp)) | |
145 | return -1; | |
146 | ||
147 | return 0; | |
148 | } | |
149 | ||
150 | static int patch_util_cmp(const void *dummy, const struct patch_util *a, | |
151 | const struct patch_util *b, const char *keydata) | |
152 | { | |
153 | return strcmp(a->diff, keydata ? keydata : b->diff); | |
154 | } | |
155 | ||
156 | static void find_exact_matches(struct string_list *a, struct string_list *b) | |
157 | { | |
158 | struct hashmap map; | |
159 | int i; | |
160 | ||
161 | hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0); | |
162 | ||
163 | /* First, add the patches of a to a hash map */ | |
164 | for (i = 0; i < a->nr; i++) { | |
165 | struct patch_util *util = a->items[i].util; | |
166 | ||
167 | util->i = i; | |
168 | util->patch = a->items[i].string; | |
169 | util->diff = util->patch + util->diff_offset; | |
170 | hashmap_entry_init(util, strhash(util->diff)); | |
171 | hashmap_add(&map, util); | |
172 | } | |
173 | ||
174 | /* Now try to find exact matches in b */ | |
175 | for (i = 0; i < b->nr; i++) { | |
176 | struct patch_util *util = b->items[i].util, *other; | |
177 | ||
178 | util->i = i; | |
179 | util->patch = b->items[i].string; | |
180 | util->diff = util->patch + util->diff_offset; | |
181 | hashmap_entry_init(util, strhash(util->diff)); | |
182 | other = hashmap_remove(&map, util, NULL); | |
183 | if (other) { | |
184 | if (other->matching >= 0) | |
185 | BUG("already assigned!"); | |
186 | ||
187 | other->matching = i; | |
188 | util->matching = other->i; | |
189 | } | |
190 | } | |
191 | ||
192 | hashmap_free(&map, 0); | |
193 | } | |
194 | ||
195 | static void diffsize_consume(void *data, char *line, unsigned long len) | |
196 | { | |
197 | (*(int *)data)++; | |
198 | } | |
199 | ||
200 | static int diffsize(const char *a, const char *b) | |
201 | { | |
202 | xpparam_t pp = { 0 }; | |
203 | xdemitconf_t cfg = { 0 }; | |
204 | mmfile_t mf1, mf2; | |
205 | int count = 0; | |
206 | ||
207 | mf1.ptr = (char *)a; | |
208 | mf1.size = strlen(a); | |
209 | mf2.ptr = (char *)b; | |
210 | mf2.size = strlen(b); | |
211 | ||
212 | cfg.ctxlen = 3; | |
213 | if (!xdi_diff_outf(&mf1, &mf2, diffsize_consume, &count, &pp, &cfg)) | |
214 | return count; | |
215 | ||
216 | error(_("failed to generate diff")); | |
217 | return COST_MAX; | |
218 | } | |
219 | ||
220 | static void get_correspondences(struct string_list *a, struct string_list *b, | |
221 | int creation_factor) | |
222 | { | |
223 | int n = a->nr + b->nr; | |
224 | int *cost, c, *a2b, *b2a; | |
225 | int i, j; | |
226 | ||
227 | ALLOC_ARRAY(cost, st_mult(n, n)); | |
228 | ALLOC_ARRAY(a2b, n); | |
229 | ALLOC_ARRAY(b2a, n); | |
230 | ||
231 | for (i = 0; i < a->nr; i++) { | |
232 | struct patch_util *a_util = a->items[i].util; | |
233 | ||
234 | for (j = 0; j < b->nr; j++) { | |
235 | struct patch_util *b_util = b->items[j].util; | |
236 | ||
237 | if (a_util->matching == j) | |
238 | c = 0; | |
239 | else if (a_util->matching < 0 && b_util->matching < 0) | |
240 | c = diffsize(a_util->diff, b_util->diff); | |
241 | else | |
242 | c = COST_MAX; | |
243 | cost[i + n * j] = c; | |
244 | } | |
245 | ||
246 | c = a_util->matching < 0 ? | |
247 | a_util->diffsize * creation_factor / 100 : COST_MAX; | |
248 | for (j = b->nr; j < n; j++) | |
249 | cost[i + n * j] = c; | |
250 | } | |
251 | ||
252 | for (j = 0; j < b->nr; j++) { | |
253 | struct patch_util *util = b->items[j].util; | |
254 | ||
255 | c = util->matching < 0 ? | |
256 | util->diffsize * creation_factor / 100 : COST_MAX; | |
257 | for (i = a->nr; i < n; i++) | |
258 | cost[i + n * j] = c; | |
259 | } | |
260 | ||
261 | for (i = a->nr; i < n; i++) | |
262 | for (j = b->nr; j < n; j++) | |
263 | cost[i + n * j] = 0; | |
264 | ||
265 | compute_assignment(n, n, cost, a2b, b2a); | |
266 | ||
267 | for (i = 0; i < a->nr; i++) | |
268 | if (a2b[i] >= 0 && a2b[i] < b->nr) { | |
269 | struct patch_util *a_util = a->items[i].util; | |
270 | struct patch_util *b_util = b->items[a2b[i]].util; | |
271 | ||
272 | a_util->matching = a2b[i]; | |
273 | b_util->matching = i; | |
274 | } | |
275 | ||
276 | free(cost); | |
277 | free(a2b); | |
278 | free(b2a); | |
279 | } | |
280 | ||
faa1df86 | 281 | static void output_pair_header(struct diff_options *diffopt, |
d1f87a2d | 282 | int patch_no_width, |
faa1df86 | 283 | struct strbuf *buf, |
eb0be38c JS |
284 | struct strbuf *dashes, |
285 | struct patch_util *a_util, | |
286 | struct patch_util *b_util) | |
d9c66f0b | 287 | { |
eb0be38c JS |
288 | struct object_id *oid = a_util ? &a_util->oid : &b_util->oid; |
289 | struct commit *commit; | |
faa1df86 JS |
290 | char status; |
291 | const char *color_reset = diff_get_color_opt(diffopt, DIFF_RESET); | |
292 | const char *color_old = diff_get_color_opt(diffopt, DIFF_FILE_OLD); | |
293 | const char *color_new = diff_get_color_opt(diffopt, DIFF_FILE_NEW); | |
294 | const char *color_commit = diff_get_color_opt(diffopt, DIFF_COMMIT); | |
295 | const char *color; | |
eb0be38c JS |
296 | |
297 | if (!dashes->len) | |
298 | strbuf_addchars(dashes, '-', | |
299 | strlen(find_unique_abbrev(oid, | |
300 | DEFAULT_ABBREV))); | |
301 | ||
faa1df86 JS |
302 | if (!b_util) { |
303 | color = color_old; | |
304 | status = '<'; | |
305 | } else if (!a_util) { | |
306 | color = color_new; | |
307 | status = '>'; | |
308 | } else if (strcmp(a_util->patch, b_util->patch)) { | |
309 | color = color_commit; | |
310 | status = '!'; | |
311 | } else { | |
312 | color = color_commit; | |
313 | status = '='; | |
314 | } | |
315 | ||
eb0be38c | 316 | strbuf_reset(buf); |
faa1df86 | 317 | strbuf_addstr(buf, status == '!' ? color_old : color); |
eb0be38c | 318 | if (!a_util) |
d1f87a2d | 319 | strbuf_addf(buf, "%*s: %s ", patch_no_width, "-", dashes->buf); |
eb0be38c | 320 | else |
d1f87a2d | 321 | strbuf_addf(buf, "%*d: %s ", patch_no_width, a_util->i + 1, |
eb0be38c JS |
322 | find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV)); |
323 | ||
faa1df86 JS |
324 | if (status == '!') |
325 | strbuf_addf(buf, "%s%s", color_reset, color); | |
326 | strbuf_addch(buf, status); | |
327 | if (status == '!') | |
328 | strbuf_addf(buf, "%s%s", color_reset, color_new); | |
eb0be38c JS |
329 | |
330 | if (!b_util) | |
d1f87a2d | 331 | strbuf_addf(buf, " %*s: %s", patch_no_width, "-", dashes->buf); |
eb0be38c | 332 | else |
d1f87a2d | 333 | strbuf_addf(buf, " %*d: %s", patch_no_width, b_util->i + 1, |
eb0be38c JS |
334 | find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV)); |
335 | ||
336 | commit = lookup_commit_reference(the_repository, oid); | |
337 | if (commit) { | |
faa1df86 JS |
338 | if (status == '!') |
339 | strbuf_addf(buf, "%s%s", color_reset, color); | |
340 | ||
eb0be38c JS |
341 | strbuf_addch(buf, ' '); |
342 | pp_commit_easy(CMIT_FMT_ONELINE, commit, buf); | |
343 | } | |
faa1df86 | 344 | strbuf_addf(buf, "%s\n", color_reset); |
eb0be38c | 345 | |
87f1b2d4 | 346 | fwrite(buf->buf, buf->len, 1, diffopt->file); |
d9c66f0b JS |
347 | } |
348 | ||
4eba1fe6 JS |
349 | static struct userdiff_driver no_func_name = { |
350 | .funcname = { "$^", 0 } | |
351 | }; | |
352 | ||
c8c5e43a JS |
353 | static struct diff_filespec *get_filespec(const char *name, const char *p) |
354 | { | |
355 | struct diff_filespec *spec = alloc_filespec(name); | |
356 | ||
357 | fill_filespec(spec, &null_oid, 0, 0644); | |
358 | spec->data = (char *)p; | |
359 | spec->size = strlen(p); | |
360 | spec->should_munmap = 0; | |
361 | spec->is_stdin = 1; | |
4eba1fe6 | 362 | spec->driver = &no_func_name; |
c8c5e43a JS |
363 | |
364 | return spec; | |
365 | } | |
366 | ||
367 | static void patch_diff(const char *a, const char *b, | |
368 | struct diff_options *diffopt) | |
369 | { | |
370 | diff_queue(&diff_queued_diff, | |
371 | get_filespec("a", a), get_filespec("b", b)); | |
372 | ||
373 | diffcore_std(diffopt); | |
374 | diff_flush(diffopt); | |
375 | } | |
376 | ||
377 | static void output(struct string_list *a, struct string_list *b, | |
378 | struct diff_options *diffopt) | |
d9c66f0b | 379 | { |
eb0be38c | 380 | struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT; |
d1f87a2d | 381 | int patch_no_width = decimal_width(1 + (a->nr > b->nr ? a->nr : b->nr)); |
9dc46e02 JS |
382 | int i = 0, j = 0; |
383 | ||
384 | /* | |
385 | * We assume the user is really more interested in the second argument | |
386 | * ("newer" version). To that end, we print the output in the order of | |
387 | * the RHS (the `b` parameter). To put the LHS (the `a` parameter) | |
388 | * commits that are no longer in the RHS into a good place, we place | |
389 | * them once we have shown all of their predecessors in the LHS. | |
390 | */ | |
391 | ||
392 | while (i < a->nr || j < b->nr) { | |
393 | struct patch_util *a_util, *b_util; | |
394 | a_util = i < a->nr ? a->items[i].util : NULL; | |
395 | b_util = j < b->nr ? b->items[j].util : NULL; | |
396 | ||
397 | /* Skip all the already-shown commits from the LHS. */ | |
398 | while (i < a->nr && a_util->shown) | |
399 | a_util = ++i < a->nr ? a->items[i].util : NULL; | |
400 | ||
401 | /* Show unmatched LHS commit whose predecessors were shown. */ | |
402 | if (i < a->nr && a_util->matching < 0) { | |
d1f87a2d | 403 | output_pair_header(diffopt, patch_no_width, |
faa1df86 | 404 | &buf, &dashes, a_util, NULL); |
9dc46e02 JS |
405 | i++; |
406 | continue; | |
407 | } | |
d9c66f0b | 408 | |
9dc46e02 JS |
409 | /* Show unmatched RHS commits. */ |
410 | while (j < b->nr && b_util->matching < 0) { | |
d1f87a2d | 411 | output_pair_header(diffopt, patch_no_width, |
faa1df86 | 412 | &buf, &dashes, NULL, b_util); |
9dc46e02 | 413 | b_util = ++j < b->nr ? b->items[j].util : NULL; |
d9c66f0b | 414 | } |
d9c66f0b | 415 | |
9dc46e02 JS |
416 | /* Show matching LHS/RHS pair. */ |
417 | if (j < b->nr) { | |
418 | a_util = a->items[b_util->matching].util; | |
d1f87a2d | 419 | output_pair_header(diffopt, patch_no_width, |
faa1df86 | 420 | &buf, &dashes, a_util, b_util); |
c8c5e43a JS |
421 | if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT)) |
422 | patch_diff(a->items[b_util->matching].string, | |
423 | b->items[j].string, diffopt); | |
9dc46e02 JS |
424 | a_util->shown = 1; |
425 | j++; | |
426 | } | |
d9c66f0b | 427 | } |
eb0be38c JS |
428 | strbuf_release(&buf); |
429 | strbuf_release(&dashes); | |
d9c66f0b JS |
430 | } |
431 | ||
73a834e9 ES |
432 | static struct strbuf *output_prefix_cb(struct diff_options *opt, void *data) |
433 | { | |
434 | return data; | |
435 | } | |
436 | ||
d9c66f0b | 437 | int show_range_diff(const char *range1, const char *range2, |
73a834e9 ES |
438 | int creation_factor, int dual_color, |
439 | struct diff_options *diffopt) | |
d9c66f0b JS |
440 | { |
441 | int res = 0; | |
442 | ||
443 | struct string_list branch1 = STRING_LIST_INIT_DUP; | |
444 | struct string_list branch2 = STRING_LIST_INIT_DUP; | |
445 | ||
446 | if (read_patches(range1, &branch1)) | |
447 | res = error(_("could not parse log for '%s'"), range1); | |
448 | if (!res && read_patches(range2, &branch2)) | |
449 | res = error(_("could not parse log for '%s'"), range2); | |
450 | ||
451 | if (!res) { | |
73a834e9 ES |
452 | struct diff_options opts; |
453 | struct strbuf indent = STRBUF_INIT; | |
454 | ||
455 | memcpy(&opts, diffopt, sizeof(opts)); | |
456 | opts.output_format = DIFF_FORMAT_PATCH; | |
457 | opts.flags.suppress_diff_headers = 1; | |
458 | opts.flags.dual_color_diffed_diffs = dual_color; | |
459 | opts.output_prefix = output_prefix_cb; | |
460 | strbuf_addstr(&indent, " "); | |
461 | opts.output_prefix_data = &indent; | |
462 | diff_setup_done(&opts); | |
463 | ||
d9c66f0b JS |
464 | find_exact_matches(&branch1, &branch2); |
465 | get_correspondences(&branch1, &branch2, creation_factor); | |
73a834e9 ES |
466 | output(&branch1, &branch2, &opts); |
467 | ||
468 | strbuf_release(&indent); | |
d9c66f0b JS |
469 | } |
470 | ||
471 | string_list_clear(&branch1, 1); | |
472 | string_list_clear(&branch2, 1); | |
473 | ||
474 | return res; | |
475 | } |