[thirdparty/git.git] / commit-reach.c

#include "cache.h"
#include "commit.h"
#include "decorate.h"
#include "prio-queue.h"
#include "tree.h"
#include "revision.h"
#include "tag.h"
#include "commit-reach.h"

/* Remember to update object flag allocation in object.h */
#define PARENT1		(1u<<16)
#define PARENT2		(1u<<17)
#define STALE		(1u<<18)
#define RESULT		(1u<<19)

static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);

static int queue_has_nonstale(struct prio_queue *queue)
{
	int i;
	for (i = 0; i < queue->nr; i++) {
		struct commit *commit = queue->array[i].data;
		if (!(commit->object.flags & STALE))
			return 1;
	}
	return 0;
}

/* all input commits in one and twos[] must have been parsed! */
static struct commit_list *paint_down_to_common(struct commit *one, int n,
						struct commit **twos,
						int min_generation)
{
	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
	struct commit_list *result = NULL;
	int i;
	uint32_t last_gen = GENERATION_NUMBER_INFINITY;

	one->object.flags |= PARENT1;
	if (!n) {
		commit_list_append(one, &result);
		return result;
	}
	prio_queue_put(&queue, one);

	for (i = 0; i < n; i++) {
		twos[i]->object.flags |= PARENT2;
		prio_queue_put(&queue, twos[i]);
	}

	while (queue_has_nonstale(&queue)) {
		struct commit *commit = prio_queue_get(&queue);
		struct commit_list *parents;
		int flags;

		if (commit->generation > last_gen)
			BUG("bad generation skip %8x > %8x at %s",
			    commit->generation, last_gen,
			    oid_to_hex(&commit->object.oid));
		last_gen = commit->generation;

		if (commit->generation < min_generation)
			break;

		flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
		if (flags == (PARENT1 | PARENT2)) {
			if (!(commit->object.flags & RESULT)) {
				commit->object.flags |= RESULT;
				commit_list_insert_by_date(commit, &result);
			}
			/* Mark parents of a found merge stale */
			flags |= STALE;
		}
		parents = commit->parents;
		while (parents) {
			struct commit *p = parents->item;
			parents = parents->next;
			if ((p->object.flags & flags) == flags)
				continue;
			if (parse_commit(p))
				return NULL;
			p->object.flags |= flags;
			prio_queue_put(&queue, p);
		}
	}

	clear_prio_queue(&queue);
	return result;
}

static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
{
	struct commit_list *list = NULL;
	struct commit_list *result = NULL;
	int i;

	for (i = 0; i < n; i++) {
		if (one == twos[i])
			/*
			 * We do not mark this even with RESULT so we do not
			 * have to clean it up.
			 */
			return commit_list_insert(one, &result);
	}

	if (parse_commit(one))
		return NULL;
	for (i = 0; i < n; i++) {
		if (parse_commit(twos[i]))
			return NULL;
	}

	list = paint_down_to_common(one, n, twos, 0);

	while (list) {
		struct commit *commit = pop_commit(&list);
		if (!(commit->object.flags & STALE))
			commit_list_insert_by_date(commit, &result);
	}
	return result;
}

struct commit_list *get_octopus_merge_bases(struct commit_list *in)
{
	struct commit_list *i, *j, *k, *ret = NULL;

	if (!in)
		return ret;

	commit_list_insert(in->item, &ret);

	for (i = in->next; i; i = i->next) {
		struct commit_list *new_commits = NULL, *end = NULL;

		for (j = ret; j; j = j->next) {
			struct commit_list *bases;
			bases = get_merge_bases(i->item, j->item);
			if (!new_commits)
				new_commits = bases;
			else
				end->next = bases;
			for (k = bases; k; k = k->next)
				end = k;
		}
		ret = new_commits;
	}
	return ret;
}

static int remove_redundant(struct commit **array, int cnt)
{
	/*
	 * Some commit in the array may be an ancestor of
	 * another commit.  Move such commit to the end of
	 * the array, and return the number of commits that
	 * are independent from each other.
	 */
	struct commit **work;
	unsigned char *redundant;
	int *filled_index;
	int i, j, filled;

	work = xcalloc(cnt, sizeof(*work));
	redundant = xcalloc(cnt, 1);
	ALLOC_ARRAY(filled_index, cnt - 1);

	for (i = 0; i < cnt; i++)
		parse_commit(array[i]);
	for (i = 0; i < cnt; i++) {
		struct commit_list *common;
		uint32_t min_generation = array[i]->generation;

		if (redundant[i])
			continue;
		for (j = filled = 0; j < cnt; j++) {
			if (i == j || redundant[j])
				continue;
			filled_index[filled] = j;
			work[filled++] = array[j];

			if (array[j]->generation < min_generation)
				min_generation = array[j]->generation;
		}
		common = paint_down_to_common(array[i], filled, work,
					      min_generation);
		if (array[i]->object.flags & PARENT2)
			redundant[i] = 1;
		for (j = 0; j < filled; j++)
			if (work[j]->object.flags & PARENT1)
				redundant[filled_index[j]] = 1;
		clear_commit_marks(array[i], all_flags);
		clear_commit_marks_many(filled, work, all_flags);
		free_commit_list(common);
	}

	/* Now collect the result */
	COPY_ARRAY(work, array, cnt);
	for (i = filled = 0; i < cnt; i++)
		if (!redundant[i])
			array[filled++] = work[i];
	for (j = filled, i = 0; i < cnt; i++)
		if (redundant[i])
			array[j++] = work[i];
	free(work);
	free(redundant);
	free(filled_index);
	return filled;
}

static struct commit_list *get_merge_bases_many_0(struct commit *one,
						  int n,
						  struct commit **twos,
						  int cleanup)
{
	struct commit_list *list;
	struct commit **rslt;
	struct commit_list *result;
	int cnt, i;

	result = merge_bases_many(one, n, twos);
	for (i = 0; i < n; i++) {
		if (one == twos[i])
			return result;
	}
	if (!result || !result->next) {
		if (cleanup) {
			clear_commit_marks(one, all_flags);
			clear_commit_marks_many(n, twos, all_flags);
		}
		return result;
	}

	/* There are more than one */
	cnt = commit_list_count(result);
	rslt = xcalloc(cnt, sizeof(*rslt));
	for (list = result, i = 0; list; list = list->next)
		rslt[i++] = list->item;
	free_commit_list(result);

	clear_commit_marks(one, all_flags);
	clear_commit_marks_many(n, twos, all_flags);

	cnt = remove_redundant(rslt, cnt);
	result = NULL;
	for (i = 0; i < cnt; i++)
		commit_list_insert_by_date(rslt[i], &result);
	free(rslt);
	return result;
}

struct commit_list *get_merge_bases_many(struct commit *one,
					 int n,
					 struct commit **twos)
{
	return get_merge_bases_many_0(one, n, twos, 1);
}

struct commit_list *get_merge_bases_many_dirty(struct commit *one,
					       int n,
					       struct commit **twos)
{
	return get_merge_bases_many_0(one, n, twos, 0);
}

struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
{
	return get_merge_bases_many_0(one, 1, &two, 1);
}

/*
 * Is "commit" a descendant of one of the elements on the "with_commit" list?
 */
int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
{
	if (!with_commit)
		return 1;
	while (with_commit) {
		struct commit *other;

		other = with_commit->item;
		with_commit = with_commit->next;
		if (in_merge_bases(other, commit))
			return 1;
	}
	return 0;
}

/*
 * Is "commit" an ancestor of one of the "references"?
 */
int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
{
	struct commit_list *bases;
	int ret = 0, i;
	uint32_t min_generation = GENERATION_NUMBER_INFINITY;

	if (parse_commit(commit))
		return ret;
	for (i = 0; i < nr_reference; i++) {
		if (parse_commit(reference[i]))
			return ret;
		if (reference[i]->generation < min_generation)
			min_generation = reference[i]->generation;
	}

	if (commit->generation > min_generation)
		return ret;

	bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
	if (commit->object.flags & PARENT2)
		ret = 1;
	clear_commit_marks(commit, all_flags);
	clear_commit_marks_many(nr_reference, reference, all_flags);
	free_commit_list(bases);
	return ret;
}

/*
 * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
 */
int in_merge_bases(struct commit *commit, struct commit *reference)
{
	return in_merge_bases_many(commit, 1, &reference);
}

struct commit_list *reduce_heads(struct commit_list *heads)
{
	struct commit_list *p;
	struct commit_list *result = NULL, **tail = &result;
	struct commit **array;
	int num_head, i;

	if (!heads)
		return NULL;

	/* Uniquify */
	for (p = heads; p; p = p->next)
		p->item->object.flags &= ~STALE;
	for (p = heads, num_head = 0; p; p = p->next) {
		if (p->item->object.flags & STALE)
			continue;
		p->item->object.flags |= STALE;
		num_head++;
	}
	array = xcalloc(num_head, sizeof(*array));
	for (p = heads, i = 0; p; p = p->next) {
		if (p->item->object.flags & STALE) {
			array[i++] = p->item;
			p->item->object.flags &= ~STALE;
		}
	}
	num_head = remove_redundant(array, num_head);
	for (i = 0; i < num_head; i++)
		tail = &commit_list_insert(array[i], tail)->next;
	free(array);
	return result;
}

void reduce_heads_replace(struct commit_list **heads)
{
	struct commit_list *result = reduce_heads(*heads);
	free_commit_list(*heads);
	*heads = result;
}

static void unmark_and_free(struct commit_list *list, unsigned int mark)
{
	while (list) {
		struct commit *commit = pop_commit(&list);
		commit->object.flags &= ~mark;
	}
}

int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
{
	struct object *o;
	struct commit *old_commit, *new_commit;
	struct commit_list *list, *used;
	int found = 0;

	/*
	 * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
	 * old_commit.  Otherwise we require --force.
	 */
	o = deref_tag(the_repository, parse_object(the_repository, old_oid),
		      NULL, 0);
	if (!o || o->type != OBJ_COMMIT)
		return 0;
	old_commit = (struct commit *) o;

	o = deref_tag(the_repository, parse_object(the_repository, new_oid),
		      NULL, 0);
	if (!o || o->type != OBJ_COMMIT)
		return 0;
	new_commit = (struct commit *) o;

	if (parse_commit(new_commit) < 0)
		return 0;

	used = list = NULL;
	commit_list_insert(new_commit, &list);
	while (list) {
		new_commit = pop_most_recent_commit(&list, TMP_MARK);
		commit_list_insert(new_commit, &used);
		if (new_commit == old_commit) {
			found = 1;
			break;
		}
	}
	unmark_and_free(list, TMP_MARK);
	unmark_and_free(used, TMP_MARK);
	return found;
}
Commit	Line	Data
5227c385	1	#include "cache.h"
5227c385	2	#include "commit.h"
1d614d41 DS	3	#include "decorate.h"
	4	#include "prio-queue.h"
	5	#include "tree.h"
	6	#include "revision.h"
	7	#include "tag.h"
5227c385 DS	8	#include "commit-reach.h"
	9
	10	/* Remember to update object flag allocation in object.h */
	11	#define PARENT1 (1u<<16)
	12	#define PARENT2 (1u<<17)
	13	#define STALE (1u<<18)
	14	#define RESULT (1u<<19)
	15
	16	static const unsigned all_flags = (PARENT1 \| PARENT2 \| STALE \| RESULT);
	17
	18	static int queue_has_nonstale(struct prio_queue *queue)
	19	{
	20	int i;
	21	for (i = 0; i < queue->nr; i++) {
	22	struct commit *commit = queue->array[i].data;
	23	if (!(commit->object.flags & STALE))
	24	return 1;
	25	}
	26	return 0;
	27	}
	28
	29	/* all input commits in one and twos[] must have been parsed! */
	30	static struct commit_list paint_down_to_common(struct commit one, int n,
	31	struct commit **twos,
	32	int min_generation)
	33	{
	34	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
	35	struct commit_list *result = NULL;
	36	int i;
	37	uint32_t last_gen = GENERATION_NUMBER_INFINITY;
	38
	39	one->object.flags \|= PARENT1;
	40	if (!n) {
	41	commit_list_append(one, &result);
	42	return result;
	43	}
	44	prio_queue_put(&queue, one);
	45
	46	for (i = 0; i < n; i++) {
	47	twos[i]->object.flags \|= PARENT2;
	48	prio_queue_put(&queue, twos[i]);
	49	}
	50
	51	while (queue_has_nonstale(&queue)) {
	52	struct commit *commit = prio_queue_get(&queue);
	53	struct commit_list *parents;
	54	int flags;
	55
	56	if (commit->generation > last_gen)
	57	BUG("bad generation skip %8x > %8x at %s",
	58	commit->generation, last_gen,
	59	oid_to_hex(&commit->object.oid));
	60	last_gen = commit->generation;
	61
	62	if (commit->generation < min_generation)
	63	break;
	64
	65	flags = commit->object.flags & (PARENT1 \| PARENT2 \| STALE);
	66	if (flags == (PARENT1 \| PARENT2)) {
	67	if (!(commit->object.flags & RESULT)) {
	68	commit->object.flags \|= RESULT;
	69	commit_list_insert_by_date(commit, &result);
	70	}
	71	/* Mark parents of a found merge stale */
72	flags \|= STALE;
73	}
74	parents = commit->parents;
75	while (parents) {
76	struct commit *p = parents->item;
77	parents = parents->next;
78	if ((p->object.flags & flags) == flags)
79	continue;
80	if (parse_commit(p))
81	return NULL;
82	p->object.flags \|= flags;
83	prio_queue_put(&queue, p);
84	}
85	}
86
87	clear_prio_queue(&queue);
88	return result;
89	}
90
91	static struct commit_list merge_bases_many(struct commit one, int n, struct commit **twos)
92	{
93	struct commit_list *list = NULL;
94	struct commit_list *result = NULL;
95	int i;
96
97	for (i = 0; i < n; i++) {
98	if (one == twos[i])
99	/*
100	* We do not mark this even with RESULT so we do not
101	* have to clean it up.
102	*/
103	return commit_list_insert(one, &result);
104	}
105
106	if (parse_commit(one))
107	return NULL;
108	for (i = 0; i < n; i++) {
109	if (parse_commit(twos[i]))
110	return NULL;
111	}
112
113	list = paint_down_to_common(one, n, twos, 0);
114
115	while (list) {
116	struct commit *commit = pop_commit(&list);
117	if (!(commit->object.flags & STALE))
118	commit_list_insert_by_date(commit, &result);
119	}
120	return result;
121	}
122
123	struct commit_list get_octopus_merge_bases(struct commit_list in)
124	{
125	struct commit_list i, j, k, ret = NULL;
126
127	if (!in)
128	return ret;
129
130	commit_list_insert(in->item, &ret);
131
132	for (i = in->next; i; i = i->next) {
133	struct commit_list new_commits = NULL, end = NULL;
134
135	for (j = ret; j; j = j->next) {
136	struct commit_list *bases;
137	bases = get_merge_bases(i->item, j->item);
138	if (!new_commits)
139	new_commits = bases;
140	else
141	end->next = bases;
142	for (k = bases; k; k = k->next)
143	end = k;
144	}
145	ret = new_commits;
146	}
147	return ret;
148	}
149
150	static int remove_redundant(struct commit **array, int cnt)
151	{
152	/*
153	* Some commit in the array may be an ancestor of
154	* another commit. Move such commit to the end of
155	* the array, and return the number of commits that
156	* are independent from each other.
157	*/
158	struct commit **work;
159	unsigned char *redundant;
160	int *filled_index;
161	int i, j, filled;
162
163	work = xcalloc(cnt, sizeof(*work));
164	redundant = xcalloc(cnt, 1);
165	ALLOC_ARRAY(filled_index, cnt - 1);
166
167	for (i = 0; i < cnt; i++)
168	parse_commit(array[i]);
169	for (i = 0; i < cnt; i++) {
170	struct commit_list *common;
171	uint32_t min_generation = array[i]->generation;
172
173	if (redundant[i])
174	continue;
175	for (j = filled = 0; j < cnt; j++) {
176	if (i == j \|\| redundant[j])
177	continue;
178	filled_index[filled] = j;
179	work[filled++] = array[j];
180
181	if (array[j]->generation < min_generation)
182	min_generation = array[j]->generation;
183	}
184	common = paint_down_to_common(array[i], filled, work,
185	min_generation);
186	if (array[i]->object.flags & PARENT2)
187	redundant[i] = 1;
188	for (j = 0; j < filled; j++)
189	if (work[j]->object.flags & PARENT1)
190	redundant[filled_index[j]] = 1;
191	clear_commit_marks(array[i], all_flags);
192	clear_commit_marks_many(filled, work, all_flags);
193	free_commit_list(common);
194	}
195
196	/* Now collect the result */
197	COPY_ARRAY(work, array, cnt);
198	for (i = filled = 0; i < cnt; i++)
199	if (!redundant[i])
200	array[filled++] = work[i];
201	for (j = filled, i = 0; i < cnt; i++)
202	if (redundant[i])
203	array[j++] = work[i];
204	free(work);
205	free(redundant);
206	free(filled_index);
207	return filled;
208	}
209
210	static struct commit_list get_merge_bases_many_0(struct commit one,
211	int n,
212	struct commit **twos,
213	int cleanup)
214	{
215	struct commit_list *list;
216	struct commit **rslt;
217	struct commit_list *result;
218	int cnt, i;
219
220	result = merge_bases_many(one, n, twos);
221	for (i = 0; i < n; i++) {
222	if (one == twos[i])
223	return result;
224	}
225	if (!result \|\| !result->next) {
226	if (cleanup) {
227	clear_commit_marks(one, all_flags);
228	clear_commit_marks_many(n, twos, all_flags);
229	}
230	return result;
231	}
232
233	/* There are more than one */
234	cnt = commit_list_count(result);
235	rslt = xcalloc(cnt, sizeof(*rslt));
236	for (list = result, i = 0; list; list = list->next)
237	rslt[i++] = list->item;
238	free_commit_list(result);
239
240	clear_commit_marks(one, all_flags);
241	clear_commit_marks_many(n, twos, all_flags);
242
243	cnt = remove_redundant(rslt, cnt);
244	result = NULL;
245	for (i = 0; i < cnt; i++)
246	commit_list_insert_by_date(rslt[i], &result);
247	free(rslt);
248	return result;
249	}
250
251	struct commit_list get_merge_bases_many(struct commit one,
252	int n,
253	struct commit **twos)
254	{
255	return get_merge_bases_many_0(one, n, twos, 1);
256	}
257
258	struct commit_list get_merge_bases_many_dirty(struct commit one,
259	int n,
260	struct commit **twos)
261	{
262	return get_merge_bases_many_0(one, n, twos, 0);
263	}
264
265	struct commit_list get_merge_bases(struct commit one, struct commit *two)
266	{
267	return get_merge_bases_many_0(one, 1, &two, 1);
268	}
269
270	/*
271	* Is "commit" a descendant of one of the elements on the "with_commit" list?
272	*/
273	int is_descendant_of(struct commit commit, struct commit_list with_commit)
274	{
275	if (!with_commit)
276	return 1;
277	while (with_commit) {
278	struct commit *other;
279
280	other = with_commit->item;
281	with_commit = with_commit->next;
282	if (in_merge_bases(other, commit))
283	return 1;
284	}
285	return 0;
286	}
287
288	/*
289	* Is "commit" an ancestor of one of the "references"?
290	*/
291	int in_merge_bases_many(struct commit commit, int nr_reference, struct commit *reference)
292	{
293	struct commit_list *bases;
294	int ret = 0, i;
295	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
296
297	if (parse_commit(commit))
298	return ret;
299	for (i = 0; i < nr_reference; i++) {
300	if (parse_commit(reference[i]))
301	return ret;
302	if (reference[i]->generation < min_generation)
303	min_generation = reference[i]->generation;
304	}
305
306	if (commit->generation > min_generation)
307	return ret;
308
309	bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
310	if (commit->object.flags & PARENT2)
311	ret = 1;
312	clear_commit_marks(commit, all_flags);
313	clear_commit_marks_many(nr_reference, reference, all_flags);
314	free_commit_list(bases);
315	return ret;
316	}
317
318	/*
319	* Is "commit" an ancestor of (i.e. reachable from) the "reference"?
320	*/
321	int in_merge_bases(struct commit commit, struct commit reference)
322	{
323	return in_merge_bases_many(commit, 1, &reference);
324	}
325
326	struct commit_list reduce_heads(struct commit_list heads)
327	{
328	struct commit_list *p;
329	struct commit_list result = NULL, *tail = &result;
330	struct commit **array;
331	int num_head, i;
332
333	if (!heads)
334	return NULL;
335
336	/* Uniquify */
337	for (p = heads; p; p = p->next)
338	p->item->object.flags &= ~STALE;
339	for (p = heads, num_head = 0; p; p = p->next) {
340	if (p->item->object.flags & STALE)
341	continue;
342	p->item->object.flags \|= STALE;
343	num_head++;
344	}
345	array = xcalloc(num_head, sizeof(*array));
346	for (p = heads, i = 0; p; p = p->next) {
347	if (p->item->object.flags & STALE) {
348	array[i++] = p->item;
349	p->item->object.flags &= ~STALE;
350	}
351	}
352	num_head = remove_redundant(array, num_head);
353	for (i = 0; i < num_head; i++)
354	tail = &commit_list_insert(array[i], tail)->next;
355	free(array);
356	return result;
357	}
358
359	void reduce_heads_replace(struct commit_list **heads)
360	{
361	struct commit_list result = reduce_heads(heads);
362	free_commit_list(*heads);
363	*heads = result;
364	}
1d614d41 DS	365
	366	static void unmark_and_free(struct commit_list *list, unsigned int mark)
	367	{
	368	while (list) {
	369	struct commit *commit = pop_commit(&list);
	370	commit->object.flags &= ~mark;
	371	}
	372	}
	373
	374	int ref_newer(const struct object_id new_oid, const struct object_id old_oid)
	375	{
	376	struct object *o;
	377	struct commit old_commit, new_commit;
	378	struct commit_list list, used;
	379	int found = 0;
	380
	381	/*
	382	* Both new_commit and old_commit must be commit-ish and new_commit is descendant of
	383	* old_commit. Otherwise we require --force.
	384	*/
	385	o = deref_tag(the_repository, parse_object(the_repository, old_oid),
	386	NULL, 0);
	387	if (!o \|\| o->type != OBJ_COMMIT)
	388	return 0;
	389	old_commit = (struct commit *) o;
	390
	391	o = deref_tag(the_repository, parse_object(the_repository, new_oid),
	392	NULL, 0);
	393	if (!o \|\| o->type != OBJ_COMMIT)
	394	return 0;
	395	new_commit = (struct commit *) o;
	396
	397	if (parse_commit(new_commit) < 0)
	398	return 0;
	399
	400	used = list = NULL;
	401	commit_list_insert(new_commit, &list);
	402	while (list) {
	403	new_commit = pop_most_recent_commit(&list, TMP_MARK);
	404	commit_list_insert(new_commit, &used);
	405	if (new_commit == old_commit) {
	406	found = 1;
	407	break;
	408	}
	409	}
	410	unmark_and_free(list, TMP_MARK);
	411	unmark_and_free(used, TMP_MARK);
	412	return found;
	413	}