]>
git.ipfire.org Git - thirdparty/git.git/blob - range-diff.c
2d94200d3034b1914aac1507c86be16f3298cf4b
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"
11 /* For the search for an exact match */
12 struct hashmap_entry e
;
13 const char *diff
, *patch
;
18 /* the index of the matching item in the other branch, or -1 */
24 * Reads the patches into a string list, with the `util` field being populated
25 * as struct object_id (will need to be free()d).
27 static int read_patches(const char *range
, struct string_list
*list
)
29 struct child_process cp
= CHILD_PROCESS_INIT
;
31 struct strbuf buf
= STRBUF_INIT
, line
= STRBUF_INIT
;
32 struct patch_util
*util
= NULL
;
35 argv_array_pushl(&cp
.args
, "log", "--no-color", "-p", "--no-merges",
36 "--reverse", "--date-order", "--decorate=no",
37 "--no-abbrev-commit", range
,
43 if (start_command(&cp
))
44 return error_errno(_("could not start `log`"));
45 in
= fdopen(cp
.out
, "r");
47 error_errno(_("could not read `log` output"));
52 while (strbuf_getline(&line
, in
) != EOF
) {
55 if (skip_prefix(line
.buf
, "commit ", &p
)) {
57 string_list_append(list
, buf
.buf
)->util
= util
;
60 util
= xcalloc(sizeof(*util
), 1);
61 if (get_oid(p
, &util
->oid
)) {
62 error(_("could not parse commit '%s'"), p
);
64 string_list_clear(list
, 1);
66 strbuf_release(&line
);
76 if (starts_with(line
.buf
, "diff --git")) {
78 strbuf_addch(&buf
, '\n');
79 if (!util
->diff_offset
)
80 util
->diff_offset
= buf
.len
;
81 strbuf_addbuf(&buf
, &line
);
82 } else if (in_header
) {
83 if (starts_with(line
.buf
, "Author: ")) {
84 strbuf_addbuf(&buf
, &line
);
85 strbuf_addstr(&buf
, "\n\n");
86 } else if (starts_with(line
.buf
, " ")) {
87 strbuf_addbuf(&buf
, &line
);
88 strbuf_addch(&buf
, '\n');
91 } else if (starts_with(line
.buf
, "@@ "))
92 strbuf_addstr(&buf
, "@@");
93 else if (!line
.buf
[0] || starts_with(line
.buf
, "index "))
95 * A completely blank (not ' \n', which is context)
96 * line is not valid in a diff. We skip it
97 * silently, because this neatly handles the blank
98 * separator line between commits in git-log
101 * We also want to ignore the diff's `index` lines
102 * because they contain exact blob hashes in which
103 * we are not interested.
107 strbuf_addbuf(&buf
, &line
);
109 strbuf_addch(&buf
, '\n');
113 strbuf_release(&line
);
116 string_list_append(list
, buf
.buf
)->util
= util
;
117 strbuf_release(&buf
);
119 if (finish_command(&cp
))
125 static int patch_util_cmp(const void *dummy
, const struct patch_util
*a
,
126 const struct patch_util
*b
, const char *keydata
)
128 return strcmp(a
->diff
, keydata
? keydata
: b
->diff
);
131 static void find_exact_matches(struct string_list
*a
, struct string_list
*b
)
136 hashmap_init(&map
, (hashmap_cmp_fn
)patch_util_cmp
, NULL
, 0);
138 /* First, add the patches of a to a hash map */
139 for (i
= 0; i
< a
->nr
; i
++) {
140 struct patch_util
*util
= a
->items
[i
].util
;
143 util
->patch
= a
->items
[i
].string
;
144 util
->diff
= util
->patch
+ util
->diff_offset
;
145 hashmap_entry_init(util
, strhash(util
->diff
));
146 hashmap_add(&map
, util
);
149 /* Now try to find exact matches in b */
150 for (i
= 0; i
< b
->nr
; i
++) {
151 struct patch_util
*util
= b
->items
[i
].util
, *other
;
154 util
->patch
= b
->items
[i
].string
;
155 util
->diff
= util
->patch
+ util
->diff_offset
;
156 hashmap_entry_init(util
, strhash(util
->diff
));
157 other
= hashmap_remove(&map
, util
, NULL
);
159 if (other
->matching
>= 0)
160 BUG("already assigned!");
163 util
->matching
= other
->i
;
167 hashmap_free(&map
, 0);
170 static void diffsize_consume(void *data
, char *line
, unsigned long len
)
175 static int diffsize(const char *a
, const char *b
)
177 xpparam_t pp
= { 0 };
178 xdemitconf_t cfg
= { 0 };
183 mf1
.size
= strlen(a
);
185 mf2
.size
= strlen(b
);
188 if (!xdi_diff_outf(&mf1
, &mf2
, diffsize_consume
, &count
, &pp
, &cfg
))
191 error(_("failed to generate diff"));
195 static void get_correspondences(struct string_list
*a
, struct string_list
*b
,
198 int n
= a
->nr
+ b
->nr
;
199 int *cost
, c
, *a2b
, *b2a
;
202 ALLOC_ARRAY(cost
, st_mult(n
, n
));
206 for (i
= 0; i
< a
->nr
; i
++) {
207 struct patch_util
*a_util
= a
->items
[i
].util
;
209 for (j
= 0; j
< b
->nr
; j
++) {
210 struct patch_util
*b_util
= b
->items
[j
].util
;
212 if (a_util
->matching
== j
)
214 else if (a_util
->matching
< 0 && b_util
->matching
< 0)
215 c
= diffsize(a_util
->diff
, b_util
->diff
);
221 c
= a_util
->matching
< 0 ?
222 a_util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
223 for (j
= b
->nr
; j
< n
; j
++)
227 for (j
= 0; j
< b
->nr
; j
++) {
228 struct patch_util
*util
= b
->items
[j
].util
;
230 c
= util
->matching
< 0 ?
231 util
->diffsize
* creation_factor
/ 100 : COST_MAX
;
232 for (i
= a
->nr
; i
< n
; i
++)
236 for (i
= a
->nr
; i
< n
; i
++)
237 for (j
= b
->nr
; j
< n
; j
++)
240 compute_assignment(n
, n
, cost
, a2b
, b2a
);
242 for (i
= 0; i
< a
->nr
; i
++)
243 if (a2b
[i
] >= 0 && a2b
[i
] < b
->nr
) {
244 struct patch_util
*a_util
= a
->items
[i
].util
;
245 struct patch_util
*b_util
= b
->items
[a2b
[i
]].util
;
247 a_util
->matching
= a2b
[i
];
248 b_util
->matching
= i
;
256 static const char *short_oid(struct patch_util
*util
)
258 return find_unique_abbrev(&util
->oid
, DEFAULT_ABBREV
);
261 static void output(struct string_list
*a
, struct string_list
*b
)
266 * We assume the user is really more interested in the second argument
267 * ("newer" version). To that end, we print the output in the order of
268 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
269 * commits that are no longer in the RHS into a good place, we place
270 * them once we have shown all of their predecessors in the LHS.
273 while (i
< a
->nr
|| j
< b
->nr
) {
274 struct patch_util
*a_util
, *b_util
;
275 a_util
= i
< a
->nr
? a
->items
[i
].util
: NULL
;
276 b_util
= j
< b
->nr
? b
->items
[j
].util
: NULL
;
278 /* Skip all the already-shown commits from the LHS. */
279 while (i
< a
->nr
&& a_util
->shown
)
280 a_util
= ++i
< a
->nr
? a
->items
[i
].util
: NULL
;
282 /* Show unmatched LHS commit whose predecessors were shown. */
283 if (i
< a
->nr
&& a_util
->matching
< 0) {
284 printf("%d: %s < -: --------\n",
285 i
+ 1, short_oid(a_util
));
290 /* Show unmatched RHS commits. */
291 while (j
< b
->nr
&& b_util
->matching
< 0) {
292 printf("-: -------- > %d: %s\n",
293 j
+ 1, short_oid(b_util
));
294 b_util
= ++j
< b
->nr
? b
->items
[j
].util
: NULL
;
297 /* Show matching LHS/RHS pair. */
299 a_util
= a
->items
[b_util
->matching
].util
;
300 printf("%d: %s ! %d: %s\n",
301 b_util
->matching
+ 1, short_oid(a_util
),
302 j
+ 1, short_oid(b_util
));
309 int show_range_diff(const char *range1
, const char *range2
,
314 struct string_list branch1
= STRING_LIST_INIT_DUP
;
315 struct string_list branch2
= STRING_LIST_INIT_DUP
;
317 if (read_patches(range1
, &branch1
))
318 res
= error(_("could not parse log for '%s'"), range1
);
319 if (!res
&& read_patches(range2
, &branch2
))
320 res
= error(_("could not parse log for '%s'"), range2
);
323 find_exact_matches(&branch1
, &branch2
);
324 get_correspondences(&branch1
, &branch2
, creation_factor
);
325 output(&branch1
, &branch2
);
328 string_list_clear(&branch1
, 1);
329 string_list_clear(&branch2
, 1);