[thirdparty/git.git] / range-diff.c

#include "cache.h"
#include "range-diff.h"
#include "string-list.h"
#include "run-command.h"
#include "argv-array.h"
#include "hashmap.h"
#include "xdiff-interface.h"
#include "linear-assignment.h"
#include "diffcore.h"

struct patch_util {
	/* For the search for an exact match */
	struct hashmap_entry e;
	const char *diff, *patch;

	int i, shown;
	int diffsize;
	size_t diff_offset;
	/* the index of the matching item in the other branch, or -1 */
	int matching;
	struct object_id oid;
};

/*
 * Reads the patches into a string list, with the `util` field being populated
 * as struct object_id (will need to be free()d).
 */
static int read_patches(const char *range, struct string_list *list)
{
	struct child_process cp = CHILD_PROCESS_INIT;
	FILE *in;
	struct strbuf buf = STRBUF_INIT, line = STRBUF_INIT;
	struct patch_util *util = NULL;
	int in_header = 1;

	argv_array_pushl(&cp.args, "log", "--no-color", "-p", "--no-merges",
			"--reverse", "--date-order", "--decorate=no",
			"--no-abbrev-commit", range,
			NULL);
	cp.out = -1;
	cp.no_stdin = 1;
	cp.git_cmd = 1;

	if (start_command(&cp))
		return error_errno(_("could not start `log`"));
	in = fdopen(cp.out, "r");
	if (!in) {
		error_errno(_("could not read `log` output"));
		finish_command(&cp);
		return -1;
	}

	while (strbuf_getline(&line, in) != EOF) {
		const char *p;

		if (skip_prefix(line.buf, "commit ", &p)) {
			if (util) {
				string_list_append(list, buf.buf)->util = util;
				strbuf_reset(&buf);
			}
			util = xcalloc(sizeof(*util), 1);
			if (get_oid(p, &util->oid)) {
				error(_("could not parse commit '%s'"), p);
				free(util);
				string_list_clear(list, 1);
				strbuf_release(&buf);
				strbuf_release(&line);
				fclose(in);
				finish_command(&cp);
				return -1;
			}
			util->matching = -1;
			in_header = 1;
			continue;
		}

		if (starts_with(line.buf, "diff --git")) {
			in_header = 0;
			strbuf_addch(&buf, '\n');
			if (!util->diff_offset)
				util->diff_offset = buf.len;
			strbuf_addbuf(&buf, &line);
		} else if (in_header) {
			if (starts_with(line.buf, "Author: ")) {
				strbuf_addbuf(&buf, &line);
				strbuf_addstr(&buf, "\n\n");
			} else if (starts_with(line.buf, "    ")) {
				strbuf_rtrim(&line);
				strbuf_addbuf(&buf, &line);
				strbuf_addch(&buf, '\n');
			}
			continue;
		} else if (starts_with(line.buf, "@@ "))
			strbuf_addstr(&buf, "@@");
		else if (!line.buf[0] || starts_with(line.buf, "index "))
			/*
			 * A completely blank (not ' \n', which is context)
			 * line is not valid in a diff.  We skip it
			 * silently, because this neatly handles the blank
			 * separator line between commits in git-log
			 * output.
			 *
			 * We also want to ignore the diff's `index` lines
			 * because they contain exact blob hashes in which
			 * we are not interested.
			 */
			continue;
		else
			strbuf_addbuf(&buf, &line);

		strbuf_addch(&buf, '\n');
		util->diffsize++;
	}
	fclose(in);
	strbuf_release(&line);

	if (util)
		string_list_append(list, buf.buf)->util = util;
	strbuf_release(&buf);

	if (finish_command(&cp))
		return -1;

	return 0;
}

static int patch_util_cmp(const void *dummy, const struct patch_util *a,
		     const struct patch_util *b, const char *keydata)
{
	return strcmp(a->diff, keydata ? keydata : b->diff);
}

static void find_exact_matches(struct string_list *a, struct string_list *b)
{
	struct hashmap map;
	int i;

	hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0);

	/* First, add the patches of a to a hash map */
	for (i = 0; i < a->nr; i++) {
		struct patch_util *util = a->items[i].util;

		util->i = i;
		util->patch = a->items[i].string;
		util->diff = util->patch + util->diff_offset;
		hashmap_entry_init(util, strhash(util->diff));
		hashmap_add(&map, util);
	}

	/* Now try to find exact matches in b */
	for (i = 0; i < b->nr; i++) {
		struct patch_util *util = b->items[i].util, *other;

		util->i = i;
		util->patch = b->items[i].string;
		util->diff = util->patch + util->diff_offset;
		hashmap_entry_init(util, strhash(util->diff));
		other = hashmap_remove(&map, util, NULL);
		if (other) {
			if (other->matching >= 0)
				BUG("already assigned!");

			other->matching = i;
			util->matching = other->i;
		}
	}

	hashmap_free(&map, 0);
}

static void diffsize_consume(void *data, char *line, unsigned long len)
{
	(*(int *)data)++;
}

static int diffsize(const char *a, const char *b)
{
	xpparam_t pp = { 0 };
	xdemitconf_t cfg = { 0 };
	mmfile_t mf1, mf2;
	int count = 0;

	mf1.ptr = (char *)a;
	mf1.size = strlen(a);
	mf2.ptr = (char *)b;
	mf2.size = strlen(b);

	cfg.ctxlen = 3;
	if (!xdi_diff_outf(&mf1, &mf2, diffsize_consume, &count, &pp, &cfg))
		return count;

	error(_("failed to generate diff"));
	return COST_MAX;
}

static void get_correspondences(struct string_list *a, struct string_list *b,
				int creation_factor)
{
	int n = a->nr + b->nr;
	int *cost, c, *a2b, *b2a;
	int i, j;

	ALLOC_ARRAY(cost, st_mult(n, n));
	ALLOC_ARRAY(a2b, n);
	ALLOC_ARRAY(b2a, n);

	for (i = 0; i < a->nr; i++) {
		struct patch_util *a_util = a->items[i].util;

		for (j = 0; j < b->nr; j++) {
			struct patch_util *b_util = b->items[j].util;

			if (a_util->matching == j)
				c = 0;
			else if (a_util->matching < 0 && b_util->matching < 0)
				c = diffsize(a_util->diff, b_util->diff);
			else
				c = COST_MAX;
			cost[i + n * j] = c;
		}

		c = a_util->matching < 0 ?
			a_util->diffsize * creation_factor / 100 : COST_MAX;
		for (j = b->nr; j < n; j++)
			cost[i + n * j] = c;
	}

	for (j = 0; j < b->nr; j++) {
		struct patch_util *util = b->items[j].util;

		c = util->matching < 0 ?
			util->diffsize * creation_factor / 100 : COST_MAX;
		for (i = a->nr; i < n; i++)
			cost[i + n * j] = c;
	}

	for (i = a->nr; i < n; i++)
		for (j = b->nr; j < n; j++)
			cost[i + n * j] = 0;

	compute_assignment(n, n, cost, a2b, b2a);

	for (i = 0; i < a->nr; i++)
		if (a2b[i] >= 0 && a2b[i] < b->nr) {
			struct patch_util *a_util = a->items[i].util;
			struct patch_util *b_util = b->items[a2b[i]].util;

			a_util->matching = a2b[i];
			b_util->matching = i;
		}

	free(cost);
	free(a2b);
	free(b2a);
}

static const char *short_oid(struct patch_util *util)
{
	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
}

static struct diff_filespec *get_filespec(const char *name, const char *p)
{
	struct diff_filespec *spec = alloc_filespec(name);

	fill_filespec(spec, &null_oid, 0, 0644);
	spec->data = (char *)p;
	spec->size = strlen(p);
	spec->should_munmap = 0;
	spec->is_stdin = 1;

	return spec;
}

static void patch_diff(const char *a, const char *b,
			      struct diff_options *diffopt)
{
	diff_queue(&diff_queued_diff,
		   get_filespec("a", a), get_filespec("b", b));

	diffcore_std(diffopt);
	diff_flush(diffopt);
}

static void output(struct string_list *a, struct string_list *b,
		   struct diff_options *diffopt)
{
	int i = 0, j = 0;

	/*
	 * We assume the user is really more interested in the second argument
	 * ("newer" version). To that end, we print the output in the order of
	 * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
	 * commits that are no longer in the RHS into a good place, we place
	 * them once we have shown all of their predecessors in the LHS.
	 */

	while (i < a->nr || j < b->nr) {
		struct patch_util *a_util, *b_util;
		a_util = i < a->nr ? a->items[i].util : NULL;
		b_util = j < b->nr ? b->items[j].util : NULL;

		/* Skip all the already-shown commits from the LHS. */
		while (i < a->nr && a_util->shown)
			a_util = ++i < a->nr ? a->items[i].util : NULL;

		/* Show unmatched LHS commit whose predecessors were shown. */
		if (i < a->nr && a_util->matching < 0) {
			printf("%d: %s < -: --------\n",
			       i + 1, short_oid(a_util));
			i++;
			continue;
		}

		/* Show unmatched RHS commits. */
		while (j < b->nr && b_util->matching < 0) {
			printf("-: -------- > %d: %s\n",
			       j + 1, short_oid(b_util));
			b_util = ++j < b->nr ? b->items[j].util : NULL;
		}

		/* Show matching LHS/RHS pair. */
		if (j < b->nr) {
			a_util = a->items[b_util->matching].util;
			printf("%d: %s ! %d: %s\n",
			       b_util->matching + 1, short_oid(a_util),
			       j + 1, short_oid(b_util));
			if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
				patch_diff(a->items[b_util->matching].string,
					   b->items[j].string, diffopt);
			a_util->shown = 1;
			j++;
		}
	}
}

int show_range_diff(const char *range1, const char *range2,
		    int creation_factor, struct diff_options *diffopt)
{
	int res = 0;

	struct string_list branch1 = STRING_LIST_INIT_DUP;
	struct string_list branch2 = STRING_LIST_INIT_DUP;

	if (read_patches(range1, &branch1))
		res = error(_("could not parse log for '%s'"), range1);
	if (!res && read_patches(range2, &branch2))
		res = error(_("could not parse log for '%s'"), range2);

	if (!res) {
		find_exact_matches(&branch1, &branch2);
		get_correspondences(&branch1, &branch2, creation_factor);
		output(&branch1, &branch2, diffopt);
	}

	string_list_clear(&branch1, 1);
	string_list_clear(&branch2, 1);

	return res;
}
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"
d9c66f0b JS	10
	11	struct patch_util {
	12	/* For the search for an exact match */
	13	struct hashmap_entry e;
	14	const char diff, patch;
	15
9dc46e02	16	int i, shown;
d9c66f0b JS	17	int diffsize;
	18	size_t diff_offset;
	19	/* the index of the matching item in the other branch, or -1 */
	20	int matching;
	21	struct object_id oid;
	22	};
	23
	24	/*
	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).
	27	*/
	28	static int read_patches(const char range, struct string_list list)
	29	{
	30	struct child_process cp = CHILD_PROCESS_INIT;
	31	FILE *in;
	32	struct strbuf buf = STRBUF_INIT, line = STRBUF_INIT;
	33	struct patch_util *util = NULL;
	34	int in_header = 1;
	35
	36	argv_array_pushl(&cp.args, "log", "--no-color", "-p", "--no-merges",
	37	"--reverse", "--date-order", "--decorate=no",
	38	"--no-abbrev-commit", range,
	39	NULL);
	40	cp.out = -1;
	41	cp.no_stdin = 1;
	42	cp.git_cmd = 1;
	43
	44	if (start_command(&cp))
	45	return error_errno(_("could not start `log`"));
	46	in = fdopen(cp.out, "r");
	47	if (!in) {
	48	error_errno(_("could not read `log` output"));
	49	finish_command(&cp);
	50	return -1;
	51	}
	52
	53	while (strbuf_getline(&line, in) != EOF) {
	54	const char *p;
	55
	56	if (skip_prefix(line.buf, "commit ", &p)) {
	57	if (util) {
	58	string_list_append(list, buf.buf)->util = util;
	59	strbuf_reset(&buf);
	60	}
	61	util = xcalloc(sizeof(*util), 1);
	62	if (get_oid(p, &util->oid)) {
	63	error(_("could not parse commit '%s'"), p);
	64	free(util);
	65	string_list_clear(list, 1);
	66	strbuf_release(&buf);
	67	strbuf_release(&line);
	68	fclose(in);
	69	finish_command(&cp);
	70	return -1;
	71	}
	72	util->matching = -1;
	73	in_header = 1;
	74	continue;
	75	}
	76
	77	if (starts_with(line.buf, "diff --git")) {
	78	in_header = 0;
	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, " ")) {
a142f978	88	strbuf_rtrim(&line);
d9c66f0b JS	89	strbuf_addbuf(&buf, &line);
	90	strbuf_addch(&buf, '\n');
	91	}
	92	continue;
	93	} else if (starts_with(line.buf, "@@ "))
	94	strbuf_addstr(&buf, "@@");
	95	else if (!line.buf[0] \|\| starts_with(line.buf, "index "))
	96	/*
	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
	101	* output.
	102	*
	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.
	106	*/
	107	continue;
	108	else
	109	strbuf_addbuf(&buf, &line);
	110
	111	strbuf_addch(&buf, '\n');
	112	util->diffsize++;
	113	}
	114	fclose(in);
	115	strbuf_release(&line);
	116
	117	if (util)
	118	string_list_append(list, buf.buf)->util = util;
	119	strbuf_release(&buf);
	120
	121	if (finish_command(&cp))
	122	return -1;
	123
	124	return 0;
	125	}
	126
	127	static int patch_util_cmp(const void dummy, const struct patch_util a,
	128	const struct patch_util b, const char keydata)
	129	{
	130	return strcmp(a->diff, keydata ? keydata : b->diff);
	131	}
	132
	133	static void find_exact_matches(struct string_list a, struct string_list b)
	134	{
	135	struct hashmap map;
	136	int i;
	137
	138	hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0);
	139
	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;
	143
	144	util->i = i;
	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);
	149	}
	150
	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;
154
155	util->i = i;
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);
160	if (other) {
161	if (other->matching >= 0)
162	BUG("already assigned!");
163
164	other->matching = i;
165	util->matching = other->i;
166	}
167	}
168
169	hashmap_free(&map, 0);
170	}
171
172	static void diffsize_consume(void data, char line, unsigned long len)
173	{
174	((int )data)++;
175	}
176
177	static int diffsize(const char a, const char b)
178	{
179	xpparam_t pp = { 0 };
180	xdemitconf_t cfg = { 0 };
181	mmfile_t mf1, mf2;
182	int count = 0;
183
184	mf1.ptr = (char *)a;
185	mf1.size = strlen(a);
186	mf2.ptr = (char *)b;
187	mf2.size = strlen(b);
188
189	cfg.ctxlen = 3;
190	if (!xdi_diff_outf(&mf1, &mf2, diffsize_consume, &count, &pp, &cfg))
191	return count;
192
193	error(_("failed to generate diff"));
194	return COST_MAX;
195	}
196
197	static void get_correspondences(struct string_list a, struct string_list b,
198	int creation_factor)
199	{
200	int n = a->nr + b->nr;
201	int cost, c, a2b, *b2a;
202	int i, j;
203
204	ALLOC_ARRAY(cost, st_mult(n, n));
205	ALLOC_ARRAY(a2b, n);
206	ALLOC_ARRAY(b2a, n);
207
208	for (i = 0; i < a->nr; i++) {
209	struct patch_util *a_util = a->items[i].util;
210
211	for (j = 0; j < b->nr; j++) {
212	struct patch_util *b_util = b->items[j].util;
213
214	if (a_util->matching == j)
215	c = 0;
216	else if (a_util->matching < 0 && b_util->matching < 0)
217	c = diffsize(a_util->diff, b_util->diff);
218	else
219	c = COST_MAX;
220	cost[i + n * j] = c;
221	}
222
223	c = a_util->matching < 0 ?
224	a_util->diffsize * creation_factor / 100 : COST_MAX;
225	for (j = b->nr; j < n; j++)
226	cost[i + n * j] = c;
227	}
228
229	for (j = 0; j < b->nr; j++) {
230	struct patch_util *util = b->items[j].util;
231
232	c = util->matching < 0 ?
233	util->diffsize * creation_factor / 100 : COST_MAX;
234	for (i = a->nr; i < n; i++)
235	cost[i + n * j] = c;
236	}
237
238	for (i = a->nr; i < n; i++)
239	for (j = b->nr; j < n; j++)
240	cost[i + n * j] = 0;
241
242	compute_assignment(n, n, cost, a2b, b2a);
243
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;
248
249	a_util->matching = a2b[i];
250	b_util->matching = i;
251	}
252
253	free(cost);
254	free(a2b);
255	free(b2a);
256	}
257
258	static const char short_oid(struct patch_util util)
259	{
260	return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
261	}
262
c8c5e43a JS	263	static struct diff_filespec get_filespec(const char name, const char *p)
	264	{
	265	struct diff_filespec *spec = alloc_filespec(name);
	266
	267	fill_filespec(spec, &null_oid, 0, 0644);
	268	spec->data = (char *)p;
	269	spec->size = strlen(p);
	270	spec->should_munmap = 0;
	271	spec->is_stdin = 1;
	272
	273	return spec;
	274	}
	275
	276	static void patch_diff(const char a, const char b,
	277	struct diff_options *diffopt)
	278	{
	279	diff_queue(&diff_queued_diff,
	280	get_filespec("a", a), get_filespec("b", b));
	281
	282	diffcore_std(diffopt);
	283	diff_flush(diffopt);
	284	}
	285
	286	static void output(struct string_list a, struct string_list b,
	287	struct diff_options *diffopt)
d9c66f0b	288	{
9dc46e02 JS	289	int i = 0, j = 0;
	290
	291	/*
	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.
	297	*/
	298
	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;
	303
	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;
	307
	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));
	312	i++;
	313	continue;
	314	}
d9c66f0b	315
9dc46e02 JS	316	/* Show unmatched RHS commits. */
9dc46e02 JS	317	while (j < b->nr && b_util->matching < 0) {
d9c66f0b	318	printf("-: -------- > %d: %s\n",
9dc46e02 JS	319	j + 1, short_oid(b_util));
9dc46e02 JS	320	b_util = ++j < b->nr ? b->items[j].util : NULL;
d9c66f0b	321	}
d9c66f0b	322
9dc46e02 JS	323	/* Show matching LHS/RHS pair. */
	324	if (j < b->nr) {
	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));
c8c5e43a JS	329	if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
	330	patch_diff(a->items[b_util->matching].string,
	331	b->items[j].string, diffopt);
9dc46e02 JS	332	a_util->shown = 1;
	333	j++;
	334	}
d9c66f0b JS	335	}
	336	}
	337
	338	int show_range_diff(const char range1, const char range2,
c8c5e43a	339	int creation_factor, struct diff_options *diffopt)
d9c66f0b JS	340	{
	341	int res = 0;
	342
	343	struct string_list branch1 = STRING_LIST_INIT_DUP;
	344	struct string_list branch2 = STRING_LIST_INIT_DUP;
	345
	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);
	350
	351	if (!res) {
	352	find_exact_matches(&branch1, &branch2);
	353	get_correspondences(&branch1, &branch2, creation_factor);
c8c5e43a	354	output(&branch1, &branch2, diffopt);
d9c66f0b JS	355	}
	356
	357	string_list_clear(&branch1, 1);
	358	string_list_clear(&branch2, 1);
	359
	360	return res;
	361	}