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