[PATCH 1/3] bisect: rework some rev related functions to make them more reusable

[PATCH 1/3] bisect: rework some rev related functions to make them more reusable

[Christian Couder]

This patches changes the "bisect_rev_setup" and "bisect_common"
functions to make it easier to reuse them in a later patch.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c |   25 ++++++++++++++-----------
 1 files changed, 14 insertions(+), 11 deletions(-)

diff --git a/bisect.c b/bisect.c
index f57b62c..dc4e1bb 100644
--- a/bisect.c
+++ b/bisect.c
@@ -553,7 +553,9 @@ struct commit_list *filter_skipped(struct commit_list *list,
 	return filtered;
 }
 
-static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
+static void bisect_rev_setup(struct rev_info *revs, const char *prefix,
+			     const char *bad_format, const char *good_format,
+			     int read_paths)
 {
 	struct argv_array rev_argv = { NULL, 0, 0 };
 	int i;
@@ -564,26 +566,24 @@ static void bisect_rev_setup(struct rev_info *revs, const char *prefix)
 
 	/* rev_argv.argv[0] will be ignored by setup_revisions */
 	argv_array_push(&rev_argv, xstrdup("bisect_rev_setup"));
-	argv_array_push_sha1(&rev_argv, current_bad_sha1, "%s");
+	argv_array_push_sha1(&rev_argv, current_bad_sha1, bad_format);
 	for (i = 0; i < good_revs.sha1_nr; i++)
-		argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "^%s");
+		argv_array_push_sha1(&rev_argv, good_revs.sha1[i],
+				     good_format);
 	argv_array_push(&rev_argv, xstrdup("--"));
-	read_bisect_paths(&rev_argv);
+	if (read_paths)
+		read_bisect_paths(&rev_argv);
 	argv_array_push(&rev_argv, NULL);
 
 	setup_revisions(rev_argv.argv_nr, rev_argv.argv, revs, NULL);
-	revs->limited = 1;
 }
 
-static void bisect_common(struct rev_info *revs, int *reaches, int *all)
+static void bisect_common(struct rev_info *revs)
 {
 	if (prepare_revision_walk(revs))
 		die("revision walk setup failed");
 	if (revs->tree_objects)
 		mark_edges_uninteresting(revs->commits, revs, NULL);
-
-	revs->commits = find_bisection(revs->commits, reaches, all,
-				       !!skipped_revs.sha1_nr);
 }
 
 static void exit_if_skipped_commits(struct commit_list *tried,
@@ -843,10 +843,13 @@ int bisect_next_all(const char *prefix)
 
 	check_good_are_ancestors_of_bad(prefix);
 
-	bisect_rev_setup(&revs, prefix);
+	bisect_rev_setup(&revs, prefix, "%s", "^%s", 1);
+	revs.limited = 1;
 
-	bisect_common(&revs, &reaches, &all);
+	bisect_common(&revs);
 
+	revs.commits = find_bisection(revs.commits, &reaches, &all,
+				       !!skipped_revs.sha1_nr);
 	revs.commits = filter_skipped(revs.commits, &tried, 0);
 
 	if (!revs.commits) {
-- 
1.6.3.rc1.112.g17e25

[PATCH 2/3] commit: add function to unparse a commit and its parents

[Christian Couder]

This patch adds the "unparse_commit" function that returns a commit
into an unparsed state by freeing its data and resetting its fields
to 0.

Its parents are recursively unparsed too, because they might have
been changed. But its tree is not unparsed as it should not have
been modifed.

Note that as the "flags" and "used" fields may be used even if the
object is not parsed, we have to reset them anyway.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 commit.c |   20 ++++++++++++++++++++
 commit.h |    2 ++
 2 files changed, 22 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index cf72143..1d4db4d 100644
--- a/commit.c
+++ b/commit.c
@@ -317,6 +317,26 @@ int parse_commit(struct commit *item)
 	return ret;
 }
 
+static void unparse_commit_list(struct commit_list *list)
+{
+	for (; list; list = list->next)
+		unparse_commit(list->item);
+}
+
+void unparse_commit(struct commit *item)
+{
+	item->object.flags = 0;
+	item->object.used = 0;
+	if (item->object.parsed) {
+		item->object.parsed = 0;
+		if (item->parents) {
+			unparse_commit_list(item->parents);
+			free_commit_list(item->parents);
+			item->parents = NULL;
+		}
+	}
+}
+
 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 {
 	struct commit_list *new_list = xmalloc(sizeof(struct commit_list));
diff --git a/commit.h b/commit.h
index 8bfdf0e..a8bdd09 100644
--- a/commit.h
+++ b/commit.h
@@ -40,6 +40,8 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size);
 
 int parse_commit(struct commit *item);
 
+void unparse_commit(struct commit *item);
+
 struct commit_list * commit_list_insert(struct commit *item, struct commit_list **list_p);
 unsigned commit_list_count(const struct commit_list *l);
 struct commit_list * insert_by_date(struct commit *item, struct commit_list **list);
-- 
1.6.3.rc1.112.g17e25

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> Its parents are recursively unparsed too, because they might have
> been changed. But its tree is not unparsed as it should not have
> been modifed.

It is a bug in any codepath if it used commit->tree without first checking
if commit->parsed is true to begin with, so you could NULLify commit->tree
but that shouldn't make any difference.  I agree leaving the tree object
as-is would make sense.

I am not convinced that unparsing all the _remaining_ parents recursively
like your patch does is enough.  Isn't there a codepath that

 - parses a commit A to find list of true parents X, Y, Z;

 - iterates over that list and descend into one of these parents X, doing
   nasty things such as pruning its parents list after parsing it; and

 - decides to prune that parent X from the parent list, making the parent
   list of A into Y and Z?

After such a sequence, calling your unparse_commit(A) will unparse A and
remaining parents of Y and Z, but will still leave X in the dirty state.

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Christian Couder]

Le lundi 18 mai 2009, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > Its parents are recursively unparsed too, because they might have
> > been changed. But its tree is not unparsed as it should not have
> > been modifed.
>
> It is a bug in any codepath if it used commit->tree without first
> checking if commit->parsed is true to begin with, so you could NULLify
> commit->tree but that shouldn't make any difference.  I agree leaving the
> tree object as-is would make sense.
>
> I am not convinced that unparsing all the _remaining_ parents recursively
> like your patch does is enough.  Isn't there a codepath that 
>
>  - parses a commit A to find list of true parents X, Y, Z;
>
>  - iterates over that list and descend into one of these parents X, doing
>    nasty things such as pruning its parents list after parsing it; and
>
>  - decides to prune that parent X from the parent list, making the parent
>    list of A into Y and Z?
>
> After such a sequence, calling your unparse_commit(A) will unparse A and
> remaining parents of Y and Z, but will still leave X in the dirty state.

I agree that unparsing all the remaining parents recursively may not be 
enough in some cases, but I don't know much about these cases. Is it only 
when revs->prune is set?

I think it should be ok when checking that all good revs are ancestor of the 
bad rev, but I may be missing something. 

It should be ok too when using "git replace" and/or grafts as the parent 
list of a commit should be changed before its parents are changed.

I also found the clear_commit_marks function that could be used when 
checking ancestors so I will resend a patch series using it and without 
patch 2/3. But I can continue to work on unparsing commits to improve 
the "git replace" series. I need to find some test cases though, and I 
cannot think of any interesting one right now.

By the way, when you say that you suspect an attempt to replace an object 
that is directly listed on the command line would not work very well with 
the current replace series, is it related to the unparsing commit problem?

Thanks,
Christian.

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> By the way, when you say that you suspect an attempt to replace an object 
> that is directly listed on the command line would not work very well with 
> the current replace series, is it related to the unparsing commit problem?

What I fear is something like this.

	git push $there 04a8c^2:master

It would need to parse 04a8c to find its second parent and then start
discussing what object to send with the other end.  "04a8c^2" is a direct
user input and should mean the same commit as git show "04a8c^2" would
give the user, so it obviously needs to obey the replace rules (making
04a8c parsed), but the object transfer should not look at replace at all
(that's the whole point of not using the "graft hack" that cannot be
sanely transferred to the other end).

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Jakub Narebski]

Junio C Hamano <gitster@pobox.com> writes:
> Christian Couder <chriscool@tuxfamily.org> writes:
> 
> > By the way, when you say that you suspect an attempt to replace an object 
> > that is directly listed on the command line would not work very well with 
> > the current replace series, is it related to the unparsing commit problem?
> 
> What I fear is something like this.
> 
> 	git push $there 04a8c^2:master
> 
> It would need to parse 04a8c to find its second parent and then start
> discussing what object to send with the other end.  "04a8c^2" is a direct
> user input and should mean the same commit as git show "04a8c^2" would
> give the user, so it obviously needs to obey the replace rules (making
> 04a8c parsed), but the object transfer should not look at replace at all
> (that's the whole point of not using the "graft hack" that cannot be
> sanely transferred to the other end).

First, I have always thought that you cannot push arbitrary SHA-1
(arbitrary commits) in git; you can only push via refs. Isn't it true?

Second, the "refs/replace" mechanism has the advantage over grafts
that it is sanely transferrable. Whether "04a8c^2"^{replaced} exists
on remote side depends on if other side has the same replacement, or
if you push replacements in the same push.

Solution here could be to bail out and ask user to confirm whether
other side has the same replacements... or something like that.
-- 
Jakub Narebski
Poland
ShadeHawk on #git

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Miles Bader]

Jakub Narebski <jnareb@gmail.com> writes:
>> 	git push $there 04a8c^2:master
>
> First, I have always thought that you cannot push arbitrary SHA-1
> (arbitrary commits) in git; you can only push via refs. Isn't it true?

Hmm, you could try it...

[Pushing random commits has always worked for me though.]

-miles

-- 
The secret to creativity is knowing how to hide your sources.
  --Albert Einstein

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Junio C Hamano]

Jakub Narebski <jnareb@gmail.com> writes:

> First, I have always thought that you cannot push arbitrary SHA-1
> (arbitrary commits) in git; you can only push via refs. Isn't it true?

No.

> Second, the "refs/replace" mechanism has the advantage over grafts
> that it is sanely transferrable. Whether "04a8c^2"^{replaced} exists
> on remote side depends on if other side has the same replacement, or
> if you push replacements in the same push.

The reason why replace mechanism could be cleaner than grafts is because
reachability traversal and transfer do not obey replacements, and local
ancestry traversal will if there are refs/replace entries.

So "git log" and friends will obey refs/replace/*, but between
a repository that replaces a commit and another that doesn't, they will
transfer history without replace entries getting in the way.  Whatever
04a8c^2 resolves to with replacements, the _real_ history between that
commit and whatever the tips of refs on the other side has is
transferred, and that commit will update the 'master' branch on the other
side.

If the other side sees it as the second parent of 04a8c is a different
matter.  If refs/replace hierarchy is shared between the repositories, it
will; otherwise it won't.  And the beauty of the replace mechanism is,
unlike grafts, because object transfer will always be done using _real_
history, you can sanely sync refs/replace hierarchy between the
repositories via push or fetch.  During the push of the 04a8c^2 object,
the other side does not have to worry about the presense/absense of
replace that changes the interpretation of that notation on either end.
The exact same underlying history is transferred with or without the
replacement objects.

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Jakub Narebski]

On Tue, 19 May 2009, Junio C Hamano wrote:
> Jakub Narebski <jnareb@gmail.com> writes:
> 
> > First, I have always thought that you cannot push arbitrary SHA-1
> > (arbitrary commits) in git; you can only push via refs. Isn't it true?
> 
> No.

Oh. I must have mistaken it with the protection in the opposite side:
git-fetch doesn't allow fetching arbitrary SHA-1 (arbitrary commits),
isn't it?

Side note: I wonder if any other DVCS has such shotgun of^W^W a feature ;-)

> > Second, the "refs/replace" mechanism has the advantage over grafts
> > that it is sanely transferrable. Whether "04a8c^2"^{replaced} exists
> > on remote side depends on if other side has the same replacement, or
> > if you push replacements in the same push.
> 
> The reason why replace mechanism could be cleaner than grafts is because
> reachability traversal and transfer do not obey replacements, and local
> ancestry traversal will if there are refs/replace entries.
[cut]

Thanks for an explanation. So "refs/replace" is sanely transferrable
because it can be transferred using local reachability only (without
replacements turned on), isn't it?

As I understand the problem with replacement rules is that it cannot be
treated simply as 'extended SHA1' syntax; the replacements must be done
only for local operations, which probably means opt-in, and pushing it
down to the commands itself... well, that or marking commands as local
or remote...

-- 
Jakub Narebski
Poland

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Johannes Sixt]

Christian Couder schrieb:
> +static void unparse_commit_list(struct commit_list *list)
> +{
> +	for (; list; list = list->next)
> +		unparse_commit(list->item);
> +}
> +
> +void unparse_commit(struct commit *item)
> +{
> +	item->object.flags = 0;
> +	item->object.used = 0;
> +	if (item->object.parsed) {
> +		item->object.parsed = 0;
> +		if (item->parents) {
> +			unparse_commit_list(item->parents);
> +			free_commit_list(item->parents);
> +			item->parents = NULL;
> +		}
> +	}
> +}

I see a recursion here. Could this not overflow the stack if there is a
long ancestry chain?

-- Hannes

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Johannes Schindelin]

Hi,

On Mon, 25 May 2009, Johannes Sixt wrote:

> Christian Couder schrieb:
> > +static void unparse_commit_list(struct commit_list *list)
> > +{
> > +	for (; list; list = list->next)
> > +		unparse_commit(list->item);
> > +}
> > +
> > +void unparse_commit(struct commit *item)
> > +{
> > +	item->object.flags = 0;
> > +	item->object.used = 0;
> > +	if (item->object.parsed) {
> > +		item->object.parsed = 0;
> > +		if (item->parents) {
> > +			unparse_commit_list(item->parents);
> > +			free_commit_list(item->parents);
> > +			item->parents = NULL;
> > +		}
> > +	}
> > +}
> 
> I see a recursion here. Could this not overflow the stack if there is a
> long ancestry chain?

You mean tail recursion, i.e. something like

void unparse_commit(struct commit *item)
{
	item->object.flags = 0;
	item->object.used = 0;
	while (item->object.parsed) {
		struct commit *first;

		item->object.parsed = 0;
		if (!item->parents)
			break;
		if (item->parents->next)
			unparse_commit_list(item->parents->next);
		first = item->parents->item;
		free_commit_list(item->parents);
		item->parents = NULL;
		item = first;
	}
}

However, I am a bit concerned that this function is dangerous, as it just 
assumes that there is no reference to the commits left, which assumption 
is _very_ easy to break by mistake.

Ciao,
Dscho

Re: [PATCH 2/3] commit: add function to unparse a commit and its parents

[Christian Couder]

Hi,

Le Monday 25 May 2009, Johannes Schindelin a écrit :
> Hi,
>
> On Mon, 25 May 2009, Johannes Sixt wrote:
> > Christian Couder schrieb:
> > > +static void unparse_commit_list(struct commit_list *list)
> > > +{
> > > +	for (; list; list = list->next)
> > > +		unparse_commit(list->item);
> > > +}
> > > +
> > > +void unparse_commit(struct commit *item)
> > > +{
> > > +	item->object.flags = 0;
> > > +	item->object.used = 0;
> > > +	if (item->object.parsed) {
> > > +		item->object.parsed = 0;
> > > +		if (item->parents) {
> > > +			unparse_commit_list(item->parents);
> > > +			free_commit_list(item->parents);
> > > +			item->parents = NULL;
> > > +		}
> > > +	}
> > > +}
> >
> > I see a recursion here. Could this not overflow the stack if there is a
> > long ancestry chain?
>
> You mean tail recursion, i.e. something like
>
> void unparse_commit(struct commit *item)
> {
> 	item->object.flags = 0;
> 	item->object.used = 0;
> 	while (item->object.parsed) {
> 		struct commit *first;
>
> 		item->object.parsed = 0;
> 		if (!item->parents)
> 			break;
> 		if (item->parents->next)
> 			unparse_commit_list(item->parents->next);
> 		first = item->parents->item;
> 		free_commit_list(item->parents);
> 		item->parents = NULL;
> 		item = first;
> 	}
> }

Yes, it is better like this. Thanks and sorry about responding late.

> However, I am a bit concerned that this function is dangerous, as it just
> assumes that there is no reference to the commits left, which assumption
> is _very_ easy to break by mistake.

Anyway I will send a 2 patch series that will use clear_commit_marks instead 
of this function.

Thanks,
Christian.

[PATCH 3/3] bisect: check ancestors without forking a "git rev-list" process

[Christian Couder]

We must save the pending commits that will be used during revision
walking and unparse them after, because we want to leave a clean
state for the next revision walking that will try to find the best
bisection point.

As we don't fork a process anymore to call "git rev-list", we need
to remove the use of GIT_TRACE to check how "git rev-list" is
called from the t6030 test that uses it.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c                    |   54 +++++++++++++++++-------------------------
 t/t6030-bisect-porcelain.sh |   13 +---------
 2 files changed, 23 insertions(+), 44 deletions(-)

diff --git a/bisect.c b/bisect.c
index dc4e1bb..c43c120 100644
--- a/bisect.c
+++ b/bisect.c
@@ -750,42 +750,31 @@ static void check_merge_bases(void)
 	free_commit_list(result);
 }
 
-/*
- * This function runs the command "git rev-list $_good ^$_bad"
- * and returns 1 if it produces some output, 0 otherwise.
- */
-static int check_ancestors(void)
+static int check_ancestors(const char *prefix)
 {
-	struct argv_array rev_argv = { NULL, 0, 0 };
-	struct strbuf str = STRBUF_INIT;
-	int i, result = 0;
-	struct child_process rls;
-	FILE *rls_fout;
+	struct rev_info revs;
+	struct object_array pending_copy;
+	int i, res;
 
-	argv_array_push(&rev_argv, xstrdup("rev-list"));
-	argv_array_push_sha1(&rev_argv, current_bad_sha1, "^%s");
-	for (i = 0; i < good_revs.sha1_nr; i++)
-		argv_array_push_sha1(&rev_argv, good_revs.sha1[i], "%s");
-	argv_array_push(&rev_argv, NULL);
+	bisect_rev_setup(&revs, prefix, "^%s", "%s", 0);
 
-	memset(&rls, 0, sizeof(rls));
-	rls.argv = rev_argv.argv;
-	rls.out = -1;
-	rls.git_cmd = 1;
-	if (start_command(&rls))
-		die("Could not launch 'git rev-list' command.");
-	rls_fout = fdopen(rls.out, "r");
-	while (strbuf_getline(&str, rls_fout, '\n') != EOF) {
-		strbuf_trim(&str);
-		if (*str.buf) {
-			result = 1;
-			break;
-		}
+	/* Save pending objects, so they can be cleaned up later. */
+	memset(&pending_copy, 0, sizeof(pending_copy));
+	for (i = 0; i < revs.pending.nr; i++)
+		add_object_array(revs.pending.objects[i].item,
+				 revs.pending.objects[i].name,
+				 &pending_copy);
+
+	bisect_common(&revs);
+	res = (revs.commits != NULL);
+
+	/* Clean up objects used, as they will be reused. */
+	for (i = 0; i < pending_copy.nr; i++) {
+		struct object *o = pending_copy.objects[i].item;
+		unparse_commit((struct commit *)o);
 	}
-	fclose(rls_fout);
-	finish_command(&rls);
 
-	return result;
+	return res;
 }
 
 /*
@@ -813,7 +802,8 @@ static void check_good_are_ancestors_of_bad(const char *prefix)
 	if (good_revs.sha1_nr == 0)
 		return;
 
-	if (check_ancestors())
+	/* Check if all good revs are ancestor of the bad rev. */
+	if (check_ancestors(prefix))
 		check_merge_bases();
 
 	/* Create file BISECT_ANCESTORS_OK. */
diff --git a/t/t6030-bisect-porcelain.sh b/t/t6030-bisect-porcelain.sh
index 54b7ea6..5254b23 100755
--- a/t/t6030-bisect-porcelain.sh
+++ b/t/t6030-bisect-porcelain.sh
@@ -482,28 +482,17 @@ test_expect_success 'good merge bases when good and bad are siblings' '
 	git bisect reset
 '
 
-check_trace() {
-	grep "$1" "$GIT_TRACE" | grep "\^$2" | grep "$3" >/dev/null
-}
-
 test_expect_success 'optimized merge base checks' '
-	GIT_TRACE="$(pwd)/trace.log" &&
-	export GIT_TRACE &&
 	git bisect start "$HASH7" "$SIDE_HASH7" > my_bisect_log.txt &&
 	grep "merge base must be tested" my_bisect_log.txt &&
 	grep "$HASH4" my_bisect_log.txt &&
-	check_trace "rev-list" "$HASH7" "$SIDE_HASH7" &&
 	git bisect good > my_bisect_log2.txt &&
 	test -f ".git/BISECT_ANCESTORS_OK" &&
 	test "$HASH6" = $(git rev-parse --verify HEAD) &&
-	: > "$GIT_TRACE" &&
 	git bisect bad > my_bisect_log3.txt &&
-	test_must_fail check_trace "rev-list" "$HASH6" "$SIDE_HASH7" &&
 	git bisect good "$A_HASH" > my_bisect_log4.txt &&
 	grep "merge base must be tested" my_bisect_log4.txt &&
-	test_must_fail test -f ".git/BISECT_ANCESTORS_OK" &&
-	check_trace "rev-list" "$HASH6" "$A_HASH" &&
-	unset GIT_TRACE
+	test_must_fail test -f ".git/BISECT_ANCESTORS_OK"
 '
 
 # This creates another side branch called "parallel" with some files
-- 
1.6.3.rc1.112.g17e25