Merge branch 'zh/read-cache-copy-name-entry-fix'
[alt-git.git] / range-diff.c
blobf63b3ffc200a8b71df3d7287322321ac70be2595
1 #include "cache.h"
2 #include "range-diff.h"
3 #include "string-list.h"
4 #include "run-command.h"
5 #include "strvec.h"
6 #include "hashmap.h"
7 #include "xdiff-interface.h"
8 #include "linear-assignment.h"
9 #include "diffcore.h"
10 #include "commit.h"
11 #include "pretty.h"
12 #include "userdiff.h"
13 #include "apply.h"
14 #include "revision.h"
16 struct patch_util {
17 /* For the search for an exact match */
18 struct hashmap_entry e;
19 const char *diff, *patch;
21 int i, shown;
22 int diffsize;
23 size_t diff_offset;
24 /* the index of the matching item in the other branch, or -1 */
25 int matching;
26 struct object_id oid;
30 * Reads the patches into a string list, with the `util` field being populated
31 * as struct object_id (will need to be free()d).
33 static int read_patches(const char *range, struct string_list *list,
34 const struct strvec *other_arg)
36 struct child_process cp = CHILD_PROCESS_INIT;
37 struct strbuf buf = STRBUF_INIT, contents = STRBUF_INIT;
38 struct patch_util *util = NULL;
39 int in_header = 1;
40 char *line, *current_filename = NULL;
41 ssize_t len;
42 size_t size;
43 int ret = -1;
45 strvec_pushl(&cp.args, "log", "--no-color", "-p", "--no-merges",
46 "--reverse", "--date-order", "--decorate=no",
47 "--no-prefix", "--submodule=short",
49 * Choose indicators that are not used anywhere
50 * else in diffs, but still look reasonable
51 * (e.g. will not be confusing when debugging)
53 "--output-indicator-new=>",
54 "--output-indicator-old=<",
55 "--output-indicator-context=#",
56 "--no-abbrev-commit",
57 "--pretty=medium",
58 "--notes",
59 NULL);
60 if (other_arg)
61 strvec_pushv(&cp.args, other_arg->v);
62 strvec_push(&cp.args, range);
63 cp.out = -1;
64 cp.no_stdin = 1;
65 cp.git_cmd = 1;
67 if (start_command(&cp))
68 return error_errno(_("could not start `log`"));
69 if (strbuf_read(&contents, cp.out, 0) < 0) {
70 error_errno(_("could not read `log` output"));
71 finish_command(&cp);
72 goto cleanup;
74 if (finish_command(&cp))
75 goto cleanup;
77 line = contents.buf;
78 size = contents.len;
79 for (; size > 0; size -= len, line += len) {
80 const char *p;
81 char *eol;
83 eol = memchr(line, '\n', size);
84 if (eol) {
85 *eol = '\0';
86 len = eol + 1 - line;
87 } else {
88 len = size;
91 if (skip_prefix(line, "commit ", &p)) {
92 if (util) {
93 string_list_append(list, buf.buf)->util = util;
94 strbuf_reset(&buf);
96 CALLOC_ARRAY(util, 1);
97 if (get_oid(p, &util->oid)) {
98 error(_("could not parse commit '%s'"), p);
99 FREE_AND_NULL(util);
100 string_list_clear(list, 1);
101 goto cleanup;
103 util->matching = -1;
104 in_header = 1;
105 continue;
108 if (!util) {
109 error(_("could not parse first line of `log` output: "
110 "did not start with 'commit ': '%s'"),
111 line);
112 string_list_clear(list, 1);
113 goto cleanup;
116 if (starts_with(line, "diff --git")) {
117 struct patch patch = { 0 };
118 struct strbuf root = STRBUF_INIT;
119 int linenr = 0;
120 int orig_len;
122 in_header = 0;
123 strbuf_addch(&buf, '\n');
124 if (!util->diff_offset)
125 util->diff_offset = buf.len;
126 if (eol)
127 *eol = '\n';
128 orig_len = len;
129 len = parse_git_diff_header(&root, &linenr, 0, line,
130 len, size, &patch);
131 if (len < 0) {
132 error(_("could not parse git header '%.*s'"),
133 orig_len, line);
134 FREE_AND_NULL(util);
135 string_list_clear(list, 1);
136 goto cleanup;
138 strbuf_addstr(&buf, " ## ");
139 if (patch.is_new > 0)
140 strbuf_addf(&buf, "%s (new)", patch.new_name);
141 else if (patch.is_delete > 0)
142 strbuf_addf(&buf, "%s (deleted)", patch.old_name);
143 else if (patch.is_rename)
144 strbuf_addf(&buf, "%s => %s", patch.old_name, patch.new_name);
145 else
146 strbuf_addstr(&buf, patch.new_name);
148 free(current_filename);
149 if (patch.is_delete > 0)
150 current_filename = xstrdup(patch.old_name);
151 else
152 current_filename = xstrdup(patch.new_name);
154 if (patch.new_mode && patch.old_mode &&
155 patch.old_mode != patch.new_mode)
156 strbuf_addf(&buf, " (mode change %06o => %06o)",
157 patch.old_mode, patch.new_mode);
159 strbuf_addstr(&buf, " ##");
160 release_patch(&patch);
161 } else if (in_header) {
162 if (starts_with(line, "Author: ")) {
163 strbuf_addstr(&buf, " ## Metadata ##\n");
164 strbuf_addstr(&buf, line);
165 strbuf_addstr(&buf, "\n\n");
166 strbuf_addstr(&buf, " ## Commit message ##\n");
167 } else if (starts_with(line, "Notes") &&
168 line[strlen(line) - 1] == ':') {
169 strbuf_addstr(&buf, "\n\n");
170 /* strip the trailing colon */
171 strbuf_addf(&buf, " ## %.*s ##\n",
172 (int)(strlen(line) - 1), line);
173 } else if (starts_with(line, " ")) {
174 p = line + len - 2;
175 while (isspace(*p) && p >= line)
176 p--;
177 strbuf_add(&buf, line, p - line + 1);
178 strbuf_addch(&buf, '\n');
180 continue;
181 } else if (skip_prefix(line, "@@ ", &p)) {
182 p = strstr(p, "@@");
183 strbuf_addstr(&buf, "@@");
184 if (current_filename && p[2])
185 strbuf_addf(&buf, " %s:", current_filename);
186 if (p)
187 strbuf_addstr(&buf, p + 2);
188 } else if (!line[0])
190 * A completely blank (not ' \n', which is context)
191 * line is not valid in a diff. We skip it
192 * silently, because this neatly handles the blank
193 * separator line between commits in git-log
194 * output.
196 continue;
197 else if (line[0] == '>') {
198 strbuf_addch(&buf, '+');
199 strbuf_addstr(&buf, line + 1);
200 } else if (line[0] == '<') {
201 strbuf_addch(&buf, '-');
202 strbuf_addstr(&buf, line + 1);
203 } else if (line[0] == '#') {
204 strbuf_addch(&buf, ' ');
205 strbuf_addstr(&buf, line + 1);
206 } else {
207 strbuf_addch(&buf, ' ');
208 strbuf_addstr(&buf, line);
211 strbuf_addch(&buf, '\n');
212 util->diffsize++;
215 ret = 0;
216 cleanup:
217 strbuf_release(&contents);
219 if (util)
220 string_list_append(list, buf.buf)->util = util;
221 strbuf_release(&buf);
222 free(current_filename);
224 return ret;
227 static int patch_util_cmp(const void *dummy, const struct patch_util *a,
228 const struct patch_util *b, const char *keydata)
230 return strcmp(a->diff, keydata ? keydata : b->diff);
233 static void find_exact_matches(struct string_list *a, struct string_list *b)
235 struct hashmap map = HASHMAP_INIT((hashmap_cmp_fn)patch_util_cmp, NULL);
236 int i;
238 /* First, add the patches of a to a hash map */
239 for (i = 0; i < a->nr; i++) {
240 struct patch_util *util = a->items[i].util;
242 util->i = i;
243 util->patch = a->items[i].string;
244 util->diff = util->patch + util->diff_offset;
245 hashmap_entry_init(&util->e, strhash(util->diff));
246 hashmap_add(&map, &util->e);
249 /* Now try to find exact matches in b */
250 for (i = 0; i < b->nr; i++) {
251 struct patch_util *util = b->items[i].util, *other;
253 util->i = i;
254 util->patch = b->items[i].string;
255 util->diff = util->patch + util->diff_offset;
256 hashmap_entry_init(&util->e, strhash(util->diff));
257 other = hashmap_remove_entry(&map, util, e, NULL);
258 if (other) {
259 if (other->matching >= 0)
260 BUG("already assigned!");
262 other->matching = i;
263 util->matching = other->i;
267 hashmap_clear(&map);
270 static int diffsize_consume(void *data, char *line, unsigned long len)
272 (*(int *)data)++;
273 return 0;
276 static void diffsize_hunk(void *data, long ob, long on, long nb, long nn,
277 const char *funcline, long funclen)
279 diffsize_consume(data, NULL, 0);
282 static int diffsize(const char *a, const char *b)
284 xpparam_t pp = { 0 };
285 xdemitconf_t cfg = { 0 };
286 mmfile_t mf1, mf2;
287 int count = 0;
289 mf1.ptr = (char *)a;
290 mf1.size = strlen(a);
291 mf2.ptr = (char *)b;
292 mf2.size = strlen(b);
294 cfg.ctxlen = 3;
295 if (!xdi_diff_outf(&mf1, &mf2,
296 diffsize_hunk, diffsize_consume, &count,
297 &pp, &cfg))
298 return count;
300 error(_("failed to generate diff"));
301 return COST_MAX;
304 static void get_correspondences(struct string_list *a, struct string_list *b,
305 int creation_factor)
307 int n = a->nr + b->nr;
308 int *cost, c, *a2b, *b2a;
309 int i, j;
311 ALLOC_ARRAY(cost, st_mult(n, n));
312 ALLOC_ARRAY(a2b, n);
313 ALLOC_ARRAY(b2a, n);
315 for (i = 0; i < a->nr; i++) {
316 struct patch_util *a_util = a->items[i].util;
318 for (j = 0; j < b->nr; j++) {
319 struct patch_util *b_util = b->items[j].util;
321 if (a_util->matching == j)
322 c = 0;
323 else if (a_util->matching < 0 && b_util->matching < 0)
324 c = diffsize(a_util->diff, b_util->diff);
325 else
326 c = COST_MAX;
327 cost[i + n * j] = c;
330 c = a_util->matching < 0 ?
331 a_util->diffsize * creation_factor / 100 : COST_MAX;
332 for (j = b->nr; j < n; j++)
333 cost[i + n * j] = c;
336 for (j = 0; j < b->nr; j++) {
337 struct patch_util *util = b->items[j].util;
339 c = util->matching < 0 ?
340 util->diffsize * creation_factor / 100 : COST_MAX;
341 for (i = a->nr; i < n; i++)
342 cost[i + n * j] = c;
345 for (i = a->nr; i < n; i++)
346 for (j = b->nr; j < n; j++)
347 cost[i + n * j] = 0;
349 compute_assignment(n, n, cost, a2b, b2a);
351 for (i = 0; i < a->nr; i++)
352 if (a2b[i] >= 0 && a2b[i] < b->nr) {
353 struct patch_util *a_util = a->items[i].util;
354 struct patch_util *b_util = b->items[a2b[i]].util;
356 a_util->matching = a2b[i];
357 b_util->matching = i;
360 free(cost);
361 free(a2b);
362 free(b2a);
365 static void output_pair_header(struct diff_options *diffopt,
366 int patch_no_width,
367 struct strbuf *buf,
368 struct strbuf *dashes,
369 struct patch_util *a_util,
370 struct patch_util *b_util)
372 struct object_id *oid = a_util ? &a_util->oid : &b_util->oid;
373 struct commit *commit;
374 char status;
375 const char *color_reset = diff_get_color_opt(diffopt, DIFF_RESET);
376 const char *color_old = diff_get_color_opt(diffopt, DIFF_FILE_OLD);
377 const char *color_new = diff_get_color_opt(diffopt, DIFF_FILE_NEW);
378 const char *color_commit = diff_get_color_opt(diffopt, DIFF_COMMIT);
379 const char *color;
381 if (!dashes->len)
382 strbuf_addchars(dashes, '-',
383 strlen(find_unique_abbrev(oid,
384 DEFAULT_ABBREV)));
386 if (!b_util) {
387 color = color_old;
388 status = '<';
389 } else if (!a_util) {
390 color = color_new;
391 status = '>';
392 } else if (strcmp(a_util->patch, b_util->patch)) {
393 color = color_commit;
394 status = '!';
395 } else {
396 color = color_commit;
397 status = '=';
400 strbuf_reset(buf);
401 strbuf_addstr(buf, status == '!' ? color_old : color);
402 if (!a_util)
403 strbuf_addf(buf, "%*s: %s ", patch_no_width, "-", dashes->buf);
404 else
405 strbuf_addf(buf, "%*d: %s ", patch_no_width, a_util->i + 1,
406 find_unique_abbrev(&a_util->oid, DEFAULT_ABBREV));
408 if (status == '!')
409 strbuf_addf(buf, "%s%s", color_reset, color);
410 strbuf_addch(buf, status);
411 if (status == '!')
412 strbuf_addf(buf, "%s%s", color_reset, color_new);
414 if (!b_util)
415 strbuf_addf(buf, " %*s: %s", patch_no_width, "-", dashes->buf);
416 else
417 strbuf_addf(buf, " %*d: %s", patch_no_width, b_util->i + 1,
418 find_unique_abbrev(&b_util->oid, DEFAULT_ABBREV));
420 commit = lookup_commit_reference(the_repository, oid);
421 if (commit) {
422 if (status == '!')
423 strbuf_addf(buf, "%s%s", color_reset, color);
425 strbuf_addch(buf, ' ');
426 pp_commit_easy(CMIT_FMT_ONELINE, commit, buf);
428 strbuf_addf(buf, "%s\n", color_reset);
430 fwrite(buf->buf, buf->len, 1, diffopt->file);
433 static struct userdiff_driver section_headers = {
434 .funcname = { "^ ## (.*) ##$\n"
435 "^.?@@ (.*)$", REG_EXTENDED }
438 static struct diff_filespec *get_filespec(const char *name, const char *p)
440 struct diff_filespec *spec = alloc_filespec(name);
442 fill_filespec(spec, null_oid(), 0, 0100644);
443 spec->data = (char *)p;
444 spec->size = strlen(p);
445 spec->should_munmap = 0;
446 spec->is_stdin = 1;
447 spec->driver = &section_headers;
449 return spec;
452 static void patch_diff(const char *a, const char *b,
453 struct diff_options *diffopt)
455 diff_queue(&diff_queued_diff,
456 get_filespec("a", a), get_filespec("b", b));
458 diffcore_std(diffopt);
459 diff_flush(diffopt);
462 static struct strbuf *output_prefix_cb(struct diff_options *opt, void *data)
464 return data;
467 static void output(struct string_list *a, struct string_list *b,
468 struct range_diff_options *range_diff_opts)
470 struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;
471 int patch_no_width = decimal_width(1 + (a->nr > b->nr ? a->nr : b->nr));
472 int i = 0, j = 0;
473 struct diff_options opts;
474 struct strbuf indent = STRBUF_INIT;
476 if (range_diff_opts->diffopt)
477 memcpy(&opts, range_diff_opts->diffopt, sizeof(opts));
478 else
479 diff_setup(&opts);
481 opts.no_free = 1;
482 if (!opts.output_format)
483 opts.output_format = DIFF_FORMAT_PATCH;
484 opts.flags.suppress_diff_headers = 1;
485 opts.flags.dual_color_diffed_diffs =
486 range_diff_opts->dual_color;
487 opts.flags.suppress_hunk_header_line_count = 1;
488 opts.output_prefix = output_prefix_cb;
489 strbuf_addstr(&indent, " ");
490 opts.output_prefix_data = &indent;
491 diff_setup_done(&opts);
494 * We assume the user is really more interested in the second argument
495 * ("newer" version). To that end, we print the output in the order of
496 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
497 * commits that are no longer in the RHS into a good place, we place
498 * them once we have shown all of their predecessors in the LHS.
501 while (i < a->nr || j < b->nr) {
502 struct patch_util *a_util, *b_util;
503 a_util = i < a->nr ? a->items[i].util : NULL;
504 b_util = j < b->nr ? b->items[j].util : NULL;
506 /* Skip all the already-shown commits from the LHS. */
507 while (i < a->nr && a_util->shown)
508 a_util = ++i < a->nr ? a->items[i].util : NULL;
510 /* Show unmatched LHS commit whose predecessors were shown. */
511 if (i < a->nr && a_util->matching < 0) {
512 if (!range_diff_opts->right_only)
513 output_pair_header(&opts, patch_no_width,
514 &buf, &dashes, a_util, NULL);
515 i++;
516 continue;
519 /* Show unmatched RHS commits. */
520 while (j < b->nr && b_util->matching < 0) {
521 if (!range_diff_opts->left_only)
522 output_pair_header(&opts, patch_no_width,
523 &buf, &dashes, NULL, b_util);
524 b_util = ++j < b->nr ? b->items[j].util : NULL;
527 /* Show matching LHS/RHS pair. */
528 if (j < b->nr) {
529 a_util = a->items[b_util->matching].util;
530 output_pair_header(&opts, patch_no_width,
531 &buf, &dashes, a_util, b_util);
532 if (!(opts.output_format & DIFF_FORMAT_NO_OUTPUT))
533 patch_diff(a->items[b_util->matching].string,
534 b->items[j].string, &opts);
535 a_util->shown = 1;
536 j++;
539 strbuf_release(&buf);
540 strbuf_release(&dashes);
541 strbuf_release(&indent);
542 opts.no_free = 0;
543 diff_free(&opts);
546 int show_range_diff(const char *range1, const char *range2,
547 struct range_diff_options *range_diff_opts)
549 int res = 0;
551 struct string_list branch1 = STRING_LIST_INIT_DUP;
552 struct string_list branch2 = STRING_LIST_INIT_DUP;
554 if (range_diff_opts->left_only && range_diff_opts->right_only)
555 res = error(_("options '%s' and '%s' cannot be used together"), "--left-only", "--right-only");
557 if (!res && read_patches(range1, &branch1, range_diff_opts->other_arg))
558 res = error(_("could not parse log for '%s'"), range1);
559 if (!res && read_patches(range2, &branch2, range_diff_opts->other_arg))
560 res = error(_("could not parse log for '%s'"), range2);
562 if (!res) {
563 find_exact_matches(&branch1, &branch2);
564 get_correspondences(&branch1, &branch2,
565 range_diff_opts->creation_factor);
566 output(&branch1, &branch2, range_diff_opts);
569 string_list_clear(&branch1, 1);
570 string_list_clear(&branch2, 1);
572 return res;
575 int is_range_diff_range(const char *arg)
577 char *copy = xstrdup(arg); /* setup_revisions() modifies it */
578 const char *argv[] = { "", copy, "--", NULL };
579 int i, positive = 0, negative = 0;
580 struct rev_info revs;
582 init_revisions(&revs, NULL);
583 if (setup_revisions(3, argv, &revs, NULL) == 1) {
584 for (i = 0; i < revs.pending.nr; i++)
585 if (revs.pending.objects[i].item->flags & UNINTERESTING)
586 negative++;
587 else
588 positive++;
589 for (i = 0; i < revs.pending.nr; i++) {
590 struct object *obj = revs.pending.objects[i].item;
592 if (obj->type == OBJ_COMMIT)
593 clear_commit_marks((struct commit *)obj,
594 ALL_REV_FLAGS);
598 free(copy);
599 release_revisions(&revs);
600 return negative > 0 && positive > 0;