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"
12 /* For the search for an exact match */
13 struct hashmap_entry e
;
14 const char *diff
, *patch
;
19 /* the index of the matching item in the other branch, or -1 */
25 * Reads the patches into a string list, with the `util` field being populated
26 * as struct object_id (will need to be free()d).
28 static int read_patches(const char *range
, struct string_list
*list
)
30 struct child_process cp
= CHILD_PROCESS_INIT
;
32 struct strbuf buf
= STRBUF_INIT
, line
= STRBUF_INIT
;
33 struct patch_util
*util
= NULL
;
36 argv_array_pushl(&cp
.args
, "log", "--no-color", "-p", "--no-merges",
37 "--reverse", "--date-order", "--decorate=no",
38 "--no-abbrev-commit", range
,
44 if (start_command(&cp
))
45 return error_errno(_("could not start `log`"));
46 in
= fdopen(cp
.out
, "r");
48 error_errno(_("could not read `log` output"));
53 while (strbuf_getline(&line
, in
) != EOF
) {
56 if (skip_prefix(line
.buf
, "commit ", &p
)) {
58 string_list_append(list
, buf
.buf
)->util
= util
;
61 util
= xcalloc(sizeof(*util
), 1);
62 if (get_oid(p
, &util
->oid
)) {
63 error(_("could not parse commit '%s'"), p
);
65 string_list_clear(list
, 1);
67 strbuf_release(&line
);
77 if (starts_with(line
.buf
, "diff --git")) {
79 strbuf_addch(&buf
, '\n');
80 if (!util
->diff_offset
)
81 util
->diff_offset
= buf
.len
;
82 strbuf_addbuf(&buf
, &line
);
83 } else if (in_header
) {
84 if (starts_with(line
.buf
, "Author: ")) {
85 strbuf_addbuf(&buf
, &line
);
86 strbuf_addstr(&buf
, "\n\n");
87 } else if (starts_with(line
.buf
, " ")) {
89 strbuf_addbuf(&buf
, &line
);
90 strbuf_addch(&buf
, '\n');
93 } else if (starts_with(line
.buf
, "@@ "))
94 strbuf_addstr(&buf
, "@@");
95 else if (!line
.buf
[0] || starts_with(line
.buf
, "index "))
97 * A completely blank (not ' \n', which is context)
98 * line is not valid in a diff. We skip it
99 * silently, because this neatly handles the blank
100 * separator line between commits in git-log
103 * We also want to ignore the diff's `index` lines
104 * because they contain exact blob hashes in which
105 * we are not interested.
109 strbuf_addbuf(&buf
, &line
);
111 strbuf_addch(&buf
, '\n');
115 strbuf_release(&line
);
118 string_list_append(list
, buf
.buf
)->util
= util
;
119 strbuf_release(&buf
);
121 if (finish_command(&cp
))
127 static int patch_util_cmp(const void *dummy
, const struct patch_util
*a
,
128 const struct patch_util
*b
, const char *keydata
)
130 return strcmp(a
->diff
, keydata
? keydata
: b
->diff
);
133 static void find_exact_matches(struct string_list
*a
, struct string_list
*b
)
138 hashmap_init(&map
, (hashmap_cmp_fn
)patch_util_cmp
, NULL
, 0);
140 /* First, add the patches of a to a hash map */
141 for (i
= 0; i
< a
->nr
; i
++) {
142 struct patch_util
*util
= a
->items
[i
].util
;
145 util
->patch
= a
->items
[i
].string
;
146 util
->diff
= util
->patch
+ util
->diff_offset
;
147 hashmap_entry_init(util
, strhash(util
->diff
));
148 hashmap_add(&map
, util
);
151 /* Now try to find exact matches in b */
152 for (i
= 0; i
< b
->nr
; i
++) {
153 struct patch_util
*util
= b
->items
[i
].util
, *other
;
156 util
->patch
= b
->items
[i
].string
;
157 util
->diff
= util
->patch
+ util
->diff_offset
;
158 hashmap_entry_init(util
, strhash(util
->diff
));
159 other
= hashmap_remove(&map
, util
, NULL
);
161 if (other
->matching
>= 0)
162 BUG("already assigned!");
165 util
->matching
= other
->i
;
169 hashmap_free(&map
, 0);
172 static void diffsize_consume(void *data
, char *line
, unsigned long len
)
177 static int diffsize(const char *a
, const char *b
)
179 xpparam_t pp
= { 0 };
180 xdemitconf_t cfg
= { 0 };
185 mf1
.size
= strlen(a
);
187 mf2
.size
= strlen(b
);
190 if (!xdi_diff_outf(&mf1
, &mf2
, diffsize_consume
, &count
, &pp
, &cfg
))
193 error(_("failed to generate diff"));
197 static void get_correspondences(struct string_list
*a
, struct string_list
*b
,
200 int n
= a
->nr
+ b
->nr
;
201 int *cost
, c
, *a2b
, *b2a
;
204 ALLOC_ARRAY(cost
, st_mult(n
, n
));
208 for (i
= 0; i
< a
->nr
; i
++) {
209 struct patch_util
*a_util
= a
->items
[i
].util
;
211 for (j
= 0; j
< b
->nr
; j
++) {
212 struct patch_util
*b_util
= b
->items
[j
].util
;
214 if (a_util
->matching
== j
)
216 else if (a_util
->matching
< 0 && b_util
->matching
< 0)
217 c
= diffsize(a_util
->diff
, b_util
->diff
);
223 c
= a_util
->matching
< 0 ?
224 a_util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
225 for (j
= b
->nr
; j
< n
; j
++)
229 for (j
= 0; j
< b
->nr
; j
++) {
230 struct patch_util
*util
= b
->items
[j
].util
;
232 c
= util
->matching
< 0 ?
233 util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
234 for (i
= a
->nr
; i
< n
; i
++)
238 for (i
= a
->nr
; i
< n
; i
++)
239 for (j
= b
->nr
; j
< n
; j
++)
242 compute_assignment(n
, n
, cost
, a2b
, b2a
);
244 for (i
= 0; i
< a
->nr
; i
++)
245 if (a2b
[i
] >= 0 && a2b
[i
] < b
->nr
) {
246 struct patch_util
*a_util
= a
->items
[i
].util
;
247 struct patch_util
*b_util
= b
->items
[a2b
[i
]].util
;
249 a_util
->matching
= a2b
[i
];
250 b_util
->matching
= i
;
258 static const char *short_oid(struct patch_util
*util
)
260 return find_unique_abbrev(&util
->oid
, DEFAULT_ABBREV
);
263 static struct diff_filespec
*get_filespec(const char *name
, const char *p
)
265 struct diff_filespec
*spec
= alloc_filespec(name
);
267 fill_filespec(spec
, &null_oid
, 0, 0644);
268 spec
->data
= (char *)p
;
269 spec
->size
= strlen(p
);
270 spec
->should_munmap
= 0;
276 static void patch_diff(const char *a
, const char *b
,
277 struct diff_options
*diffopt
)
279 diff_queue(&diff_queued_diff
,
280 get_filespec("a", a
), get_filespec("b", b
));
282 diffcore_std(diffopt
);
286 static void output(struct string_list
*a
, struct string_list
*b
,
287 struct diff_options
*diffopt
)
292 * We assume the user is really more interested in the second argument
293 * ("newer" version). To that end, we print the output in the order of
294 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
295 * commits that are no longer in the RHS into a good place, we place
296 * them once we have shown all of their predecessors in the LHS.
299 while (i
< a
->nr
|| j
< b
->nr
) {
300 struct patch_util
*a_util
, *b_util
;
301 a_util
= i
< a
->nr
? a
->items
[i
].util
: NULL
;
302 b_util
= j
< b
->nr
? b
->items
[j
].util
: NULL
;
304 /* Skip all the already-shown commits from the LHS. */
305 while (i
< a
->nr
&& a_util
->shown
)
306 a_util
= ++i
< a
->nr
? a
->items
[i
].util
: NULL
;
308 /* Show unmatched LHS commit whose predecessors were shown. */
309 if (i
< a
->nr
&& a_util
->matching
< 0) {
310 printf("%d: %s < -: --------\n",
311 i
+ 1, short_oid(a_util
));
316 /* Show unmatched RHS commits. */
317 while (j
< b
->nr
&& b_util
->matching
< 0) {
318 printf("-: -------- > %d: %s\n",
319 j
+ 1, short_oid(b_util
));
320 b_util
= ++j
< b
->nr
? b
->items
[j
].util
: NULL
;
323 /* Show matching LHS/RHS pair. */
325 a_util
= a
->items
[b_util
->matching
].util
;
326 printf("%d: %s ! %d: %s\n",
327 b_util
->matching
+ 1, short_oid(a_util
),
328 j
+ 1, short_oid(b_util
));
329 if (!(diffopt
->output_format
& DIFF_FORMAT_NO_OUTPUT
))
330 patch_diff(a
->items
[b_util
->matching
].string
,
331 b
->items
[j
].string
, diffopt
);
338 int show_range_diff(const char *range1
, const char *range2
,
339 int creation_factor
, struct diff_options
*diffopt
)
343 struct string_list branch1
= STRING_LIST_INIT_DUP
;
344 struct string_list branch2
= STRING_LIST_INIT_DUP
;
346 if (read_patches(range1
, &branch1
))
347 res
= error(_("could not parse log for '%s'"), range1
);
348 if (!res
&& read_patches(range2
, &branch2
))
349 res
= error(_("could not parse log for '%s'"), range2
);
352 find_exact_matches(&branch1
, &branch2
);
353 get_correspondences(&branch1
, &branch2
, creation_factor
);
354 output(&branch1
, &branch2
, diffopt
);
357 string_list_clear(&branch1
, 1);
358 string_list_clear(&branch2
, 1);