[PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags()

[PATCH 0/1] Properly peel tags in can_all_from_reach_with_flags()

[Derrick Stolee via GitGitGadget]

As Peff reported [1], the refactored can_all_from_reach_with_flags() method
does not properly peel tags. Since the helper method can_all_from_reach()
and code in t/helper/test-reach.c all peel tags before getting to this
method, it is not super-simple to create a test that demonstrates this.

I modified t/helper/test-reach.c to allow calling
can_all_from_reach_with_flags() directly, and added a test in
t6600-test-reach.sh that demonstrates the segfault without the fix. The fix
in commit-reach.c is Peff's fix verbatim.

[1] 
https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u

Derrick Stolee (1):
  commit-reach: properly peel tags

 commit-reach.c        | 25 ++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 63 insertions(+), 14 deletions(-)


base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/39
-- 
gitgitgadget

[PATCH 1/1] commit-reach: properly peel tags

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
"commit-reach: make can_all_from_reach... linear" but incorrectly
assumed that all objects provided were commits. During a fetch
negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
to the 'from' array. The current code creates a segfault.

Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
and add a test in t6600-test-reach.sh that demonstrates this segfault.

Correct the issue by peeling tags when investigating the initial list
of objects in the 'from' array.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c        | 25 ++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 63 insertions(+), 14 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 86715c103c..6de72c6e03 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,
 {
 	struct commit **list = NULL;
 	int i;
+	int nr_commits;
 	int result = 1;
 
 	ALLOC_ARRAY(list, from->nr);
+	nr_commits = 0;
 	for (i = 0; i < from->nr; i++) {
-		list[i] = (struct commit *)from->objects[i].item;
+		struct object *from_one = from->objects[i].item;
 
-		if (parse_commit(list[i]) ||
-		    list[i]->generation < min_generation)
-			return 0;
+		from_one = deref_tag(the_repository, from_one,
+				     "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
+			from->objects[i].item->flags |= assign_flag;
+			continue;
+		}
+
+		list[nr_commits] = (struct commit *)from_one;
+		if (parse_commit(list[nr_commits]) ||
+		    list[nr_commits]->generation < min_generation)
+			return 0; /* is this a leak? */
+		nr_commits++;
 	}
 
-	QSORT(list, from->nr, compare_commits_by_gen);
+	QSORT(list, nr_commits, compare_commits_by_gen);
 
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */
 		struct commit_list *stack = NULL;
 
@@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		clear_commit_marks(list[i], RESULT);
 		clear_commit_marks(list[i], assign_flag);
 	}
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index eb21103998..08d2ea68e8 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
 	struct commit_list *X, *Y;
+	struct object_array X_obj = OBJECT_ARRAY_INIT;
 	struct commit **X_array;
 	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;
@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;
-		struct object *o;
+		struct object *orig;
+		struct object *peeled;
 		struct commit *c;
 		if (buf.len < 3)
 			continue;
@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)
 		if (get_oid_committish(buf.buf + 2, &oid))
 			die("failed to resolve %s", buf.buf + 2);
 
-		o = parse_object(r, &oid);
-		o = deref_tag_noverify(o);
+		orig = parse_object(r, &oid);
+		peeled = deref_tag_noverify(orig);
 
-		if (!o)
+		if (!peeled)
 			die("failed to load commit for input %s resulting in oid %s\n",
 			    buf.buf, oid_to_hex(&oid));
 
-		c = object_as_type(r, o, OBJ_COMMIT, 0);
+		c = object_as_type(r, peeled, OBJ_COMMIT, 0);
 
 		if (!c)
 			die("failed to load commit for input %s resulting in oid %s\n",
@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)
 				commit_list_insert(c, &X);
 				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
 				X_array[X_nr++] = c;
+				add_object_array(orig, NULL, &X_obj);
 				break;
 
 			case 'Y':
@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)
 		print_sorted_commit_ids(list);
 	} else if (!strcmp(av[1], "can_all_from_reach")) {
 		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
+	} else if (!strcmp(av[1], "can_all_from_reach_with_flag")) {
+		struct commit_list *iter = Y;
+
+		while (iter) {
+			iter->item->object.flags |= 2;
+			iter = iter->next;
+		}
+
+		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
 	} else if (!strcmp(av[1], "commit_contains")) {
 		struct ref_filter filter;
 		struct contains_cache cache;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index d139a00d1d..f7bf82290b 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -31,7 +31,8 @@ test_expect_success 'setup' '
 	for i in $(test_seq 1 10)
 	do
 		test_commit "1-$i" &&
-		git branch -f commit-1-$i
+		git branch -f commit-1-$i &&
+		git tag -a -m "1-$i" tag-1-$i commit-1-$i
 	done &&
 	for j in $(test_seq 1 9)
 	do
@@ -39,11 +40,13 @@ test_expect_success 'setup' '
 		x=$(($j + 1)) &&
 		test_commit "$x-1" &&
 		git branch -f commit-$x-1 &&
+		git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
 
 		for i in $(test_seq 2 10)
 		do
 			git merge commit-$j-$i -m "$x-$i" &&
-			git branch -f commit-$x-$i
+			git branch -f commit-$x-$i &&
+			git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i
 		done
 	done &&
 	git commit-graph write --reachable &&
@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '
 	test_three_modes can_all_from_reach
 '
 
+test_expect_success 'can_all_from_reach_with_flag: tags case' '
+	cat >input <<-\EOF &&
+	X:tag-2-10
+	X:tag-3-9
+	X:tag-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:tag-1-9
+	Y:tag-2-8
+	Y:tag-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-7-3
+	Y:commit-8-1
+	EOF
+	echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
+	test_three_modes can_all_from_reach_with_flag
+'
+	
 test_expect_success 'commit_contains:hit' '
 	cat >input <<-\EOF &&
 	A:commit-7-7
-- 
gitgitgadget

Re: [PATCH 1/1] commit-reach: properly peel tags

[Jeff King]

On Wed, Sep 12, 2018 at 07:22:56AM -0700, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
> "commit-reach: make can_all_from_reach... linear" but incorrectly
> assumed that all objects provided were commits. During a fetch
> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
> to the 'from' array. The current code creates a segfault.
> 
> Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
> and add a test in t6600-test-reach.sh that demonstrates this segfault.

Thanks, that makes a lot of sense for reproducing. I almost wonder if
the whole X_array of commits in test-reach could just go away, and we'd
feed whatever list of objects the caller happens to send. That may make
it simpler to include non-commit objects in a variety of tests.

That said, I didn't look closely at other fallout in the program from
that, so I'll defer to your judgement.

> Correct the issue by peeling tags when investigating the initial list
> of objects in the 'from' array.
> 
> Signed-off-by: Jeff King <peff@peff.net>

I'm not sure if this should just be Reported-by, since I don't know that
I actually contributed any code. ;) But for anything I might have
contributed, certainly you have my signoff.

>  	for (i = 0; i < from->nr; i++) {
> -		list[i] = (struct commit *)from->objects[i].item;
> +		struct object *from_one = from->objects[i].item;
>  
> -		if (parse_commit(list[i]) ||
> -		    list[i]->generation < min_generation)
> -			return 0;
> +		from_one = deref_tag(the_repository, from_one,
> +				     "a from object", 0);
> +		if (!from_one || from_one->type != OBJ_COMMIT) {
> +			from->objects[i].item->flags |= assign_flag;
> +			continue;
> +		}

I didn't resurrect the comment from this conditional that was in the
original code (mostly because I wasn't sure if the reasoning was still
entirely valid, or what setting the flag here actually means). But it's
probably worth saying something here to explain why it's OK to punt on
this case, and what it means to just set the flag.

> [...]

The rest of the patch looks sane to me. I didn't go through the trouble
to reproduce the segfault with the test, but it sounds like you did.

-Peff

Re: [PATCH 1/1] commit-reach: properly peel tags

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> diff --git a/commit-reach.c b/commit-reach.c
> index 86715c103c..6de72c6e03 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  {
>  	struct commit **list = NULL;
>  	int i;
> +	int nr_commits;
>  	int result = 1;
>  
>  	ALLOC_ARRAY(list, from->nr);
> +	nr_commits = 0;
>  	for (i = 0; i < from->nr; i++) {
> -		list[i] = (struct commit *)from->objects[i].item;
> +		struct object *from_one = from->objects[i].item;
>  
> -		if (parse_commit(list[i]) ||
> -		    list[i]->generation < min_generation)
> -			return 0;
> +		from_one = deref_tag(the_repository, from_one,
> +				     "a from object", 0);
> +		if (!from_one || from_one->type != OBJ_COMMIT) {
> +			from->objects[i].item->flags |= assign_flag;

I wondered why this is not futzing with "from_one->flags"; by going
back to the original from->objects[] array, the code is setting the
flags on the original tag object and not the non-commit object that
was pointed at by the tag.

> +			continue;
> +		}
> +
> +		list[nr_commits] = (struct commit *)from_one;
> +		if (parse_commit(list[nr_commits]) ||
> +		    list[nr_commits]->generation < min_generation)
> +			return 0; /* is this a leak? */
> +		nr_commits++;
>  	}

In the original code, the flags bits were left unchanged if the loop
terminated by hitting a commit whose generation is too young (or
parse_commit() returns non-zero).  With this updated code, flags bit
can be modified before the code notices the situation and leave the
function, bypassing the "cleanup" we see below that clears the
"assign_flag" bits.

Would it be a problem that we return early without cleaning up?

Even if we do not call this early return, the assign_flag bits added
to the original tag in from->objects[i].item won't be cleaned in
this new code, as "cleanup:" section now loops over the list[] that
omits the object whose flags was smudged above before the "continue".

Would it be a problem that we leave the assign_flags without
cleaning up?

> -	QSORT(list, from->nr, compare_commits_by_gen);
> +	QSORT(list, nr_commits, compare_commits_by_gen);
>  
> -	for (i = 0; i < from->nr; i++) {
> +	for (i = 0; i < nr_commits; i++) {
>  		/* DFS from list[i] */
>  		struct commit_list *stack = NULL;
>  
> @@ -600,7 +611,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  	}
>  
>  cleanup:
> -	for (i = 0; i < from->nr; i++) {
> +	for (i = 0; i < nr_commits; i++) {
>  		clear_commit_marks(list[i], RESULT);
>  		clear_commit_marks(list[i], assign_flag);
>  	}

Re: [PATCH 1/1] commit-reach: properly peel tags

[Jeff King]

On Wed, Sep 12, 2018 at 02:23:42PM -0700, Junio C Hamano wrote:

> > diff --git a/commit-reach.c b/commit-reach.c
> > index 86715c103c..6de72c6e03 100644
> > --- a/commit-reach.c
> > +++ b/commit-reach.c
> > @@ -544,20 +544,31 @@ int can_all_from_reach_with_flag(struct object_array *from,
> >  {
> >  	struct commit **list = NULL;
> >  	int i;
> > +	int nr_commits;
> >  	int result = 1;
> >  
> >  	ALLOC_ARRAY(list, from->nr);
> > +	nr_commits = 0;
> >  	for (i = 0; i < from->nr; i++) {
> > -		list[i] = (struct commit *)from->objects[i].item;
> > +		struct object *from_one = from->objects[i].item;
> >  
> > -		if (parse_commit(list[i]) ||
> > -		    list[i]->generation < min_generation)
> > -			return 0;
> > +		from_one = deref_tag(the_repository, from_one,
> > +				     "a from object", 0);
> > +		if (!from_one || from_one->type != OBJ_COMMIT) {
> > +			from->objects[i].item->flags |= assign_flag;
> 
> I wondered why this is not futzing with "from_one->flags"; by going
> back to the original from->objects[] array, the code is setting the
> flags on the original tag object and not the non-commit object that
> was pointed at by the tag.

Note that from_one may even be NULL.

> > +			continue;
> > +		}
> > +
> > +		list[nr_commits] = (struct commit *)from_one;
> > +		if (parse_commit(list[nr_commits]) ||
> > +		    list[nr_commits]->generation < min_generation)
> > +			return 0; /* is this a leak? */
> > +		nr_commits++;
> >  	}
> 
> In the original code, the flags bits were left unchanged if the loop
> terminated by hitting a commit whose generation is too young (or
> parse_commit() returns non-zero).  With this updated code, flags bit
> can be modified before the code notices the situation and leave the
> function, bypassing the "cleanup" we see below that clears the
> "assign_flag" bits.
> 
> Would it be a problem that we return early without cleaning up?
> 
> Even if we do not call this early return, the assign_flag bits added
> to the original tag in from->objects[i].item won't be cleaned in
> this new code, as "cleanup:" section now loops over the list[] that
> omits the object whose flags was smudged above before the "continue".
> 
> Would it be a problem that we leave the assign_flags without
> cleaning up?

Yeah, I hadn't thought about the bit cleanup when making my original
suggestion. In the original code (before 4fbcca4eff), I think we did set
flags as we iterated through the loop, and we could still do an early
return when we hit "!reachable(...)". But I don't see any cleanup of
assign_flag there at all.

So I guess I'm pretty confused about what the semantics are supposed to
be.

-Peff

[PATCH v2 0/1] Properly peel tags in can_all_from_reach_with_flags()

[Derrick Stolee via GitGitGadget]

As Peff reported [1], the refactored can_all_from_reach_with_flags() method
does not properly peel tags. Since the helper method can_all_from_reach()
and code in t/helper/test-reach.c all peel tags before getting to this
method, it is not super-simple to create a test that demonstrates this.

I modified t/helper/test-reach.c to allow calling
can_all_from_reach_with_flags() directly, and added a test in
t6600-test-reach.sh that demonstrates the segfault without the fix.

For V2, I compared the loop that inspects the 'from' commits in commit
ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version
here and got the following diff:

3c3
<                 if (from_one->flags & assign_flag)
---
>                 if (!from_one || from_one->flags & assign_flag)
5c5,7
<                 from_one = deref_tag(the_repository, from_one, "a from object", 0);
---
>
>                 from_one = deref_tag(the_repository, from_one,
>                                      "a from object", 0);
14a17,22
>
>                 list[nr_commits] = (struct commit *)from_one;
>                 if (parse_commit(list[nr_commits]) ||
>                     list[nr_commits]->generation < min_generation)
>                         return 0; /* is this a leak? */
>                 nr_commits++;

This diff includes the early termination we had before 'deref_tag' and the
comment for why we can ignore non-commit objects.

[1] 
https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u

Derrick Stolee (1):
  commit-reach: properly peel tags

 commit-reach.c        | 33 ++++++++++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 71 insertions(+), 14 deletions(-)


base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/39

Range-diff vs v1:

 1:  948e222228 ! 1:  4bf21204dd commit-reach: properly peel tags
     @@ -36,9 +36,17 @@
      -		if (parse_commit(list[i]) ||
      -		    list[i]->generation < min_generation)
      -			return 0;
     ++		if (!from_one || from_one->flags & assign_flag)
     ++			continue;
     ++
      +		from_one = deref_tag(the_repository, from_one,
      +				     "a from object", 0);
      +		if (!from_one || from_one->type != OBJ_COMMIT) {
     ++			/* no way to tell if this is reachable by
     ++			 * looking at the ancestry chain alone, so
     ++			 * leave a note to ourselves not to worry about
     ++			 * this object anymore.
     ++			 */
      +			from->objects[i].item->flags |= assign_flag;
      +			continue;
      +		}
     @@ -187,7 +195,7 @@
      +	echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
      +	test_three_modes can_all_from_reach_with_flag
      +'
     -+	
     ++
       test_expect_success 'commit_contains:hit' '
       	cat >input <<-\EOF &&
       	A:commit-7-7

-- 
gitgitgadget

[PATCH v2 1/1] commit-reach: properly peel tags

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
"commit-reach: make can_all_from_reach... linear" but incorrectly
assumed that all objects provided were commits. During a fetch
negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
to the 'from' array. The current code creates a segfault.

Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
and add a test in t6600-test-reach.sh that demonstrates this segfault.

Correct the issue by peeling tags when investigating the initial list
of objects in the 'from' array.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c        | 33 ++++++++++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 71 insertions(+), 14 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 86715c103c..4048a2132a 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from,
 {
 	struct commit **list = NULL;
 	int i;
+	int nr_commits;
 	int result = 1;
 
 	ALLOC_ARRAY(list, from->nr);
+	nr_commits = 0;
 	for (i = 0; i < from->nr; i++) {
-		list[i] = (struct commit *)from->objects[i].item;
+		struct object *from_one = from->objects[i].item;
 
-		if (parse_commit(list[i]) ||
-		    list[i]->generation < min_generation)
-			return 0;
+		if (!from_one || from_one->flags & assign_flag)
+			continue;
+
+		from_one = deref_tag(the_repository, from_one,
+				     "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
+			/* no way to tell if this is reachable by
+			 * looking at the ancestry chain alone, so
+			 * leave a note to ourselves not to worry about
+			 * this object anymore.
+			 */
+			from->objects[i].item->flags |= assign_flag;
+			continue;
+		}
+
+		list[nr_commits] = (struct commit *)from_one;
+		if (parse_commit(list[nr_commits]) ||
+		    list[nr_commits]->generation < min_generation)
+			return 0; /* is this a leak? */
+		nr_commits++;
 	}
 
-	QSORT(list, from->nr, compare_commits_by_gen);
+	QSORT(list, nr_commits, compare_commits_by_gen);
 
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */
 		struct commit_list *stack = NULL;
 
@@ -600,7 +619,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		clear_commit_marks(list[i], RESULT);
 		clear_commit_marks(list[i], assign_flag);
 	}
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index eb21103998..08d2ea68e8 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
 	struct commit_list *X, *Y;
+	struct object_array X_obj = OBJECT_ARRAY_INIT;
 	struct commit **X_array;
 	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;
@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;
-		struct object *o;
+		struct object *orig;
+		struct object *peeled;
 		struct commit *c;
 		if (buf.len < 3)
 			continue;
@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)
 		if (get_oid_committish(buf.buf + 2, &oid))
 			die("failed to resolve %s", buf.buf + 2);
 
-		o = parse_object(r, &oid);
-		o = deref_tag_noverify(o);
+		orig = parse_object(r, &oid);
+		peeled = deref_tag_noverify(orig);
 
-		if (!o)
+		if (!peeled)
 			die("failed to load commit for input %s resulting in oid %s\n",
 			    buf.buf, oid_to_hex(&oid));
 
-		c = object_as_type(r, o, OBJ_COMMIT, 0);
+		c = object_as_type(r, peeled, OBJ_COMMIT, 0);
 
 		if (!c)
 			die("failed to load commit for input %s resulting in oid %s\n",
@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)
 				commit_list_insert(c, &X);
 				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
 				X_array[X_nr++] = c;
+				add_object_array(orig, NULL, &X_obj);
 				break;
 
 			case 'Y':
@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)
 		print_sorted_commit_ids(list);
 	} else if (!strcmp(av[1], "can_all_from_reach")) {
 		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
+	} else if (!strcmp(av[1], "can_all_from_reach_with_flag")) {
+		struct commit_list *iter = Y;
+
+		while (iter) {
+			iter->item->object.flags |= 2;
+			iter = iter->next;
+		}
+
+		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
 	} else if (!strcmp(av[1], "commit_contains")) {
 		struct ref_filter filter;
 		struct contains_cache cache;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index d139a00d1d..ae94b27f70 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -31,7 +31,8 @@ test_expect_success 'setup' '
 	for i in $(test_seq 1 10)
 	do
 		test_commit "1-$i" &&
-		git branch -f commit-1-$i
+		git branch -f commit-1-$i &&
+		git tag -a -m "1-$i" tag-1-$i commit-1-$i
 	done &&
 	for j in $(test_seq 1 9)
 	do
@@ -39,11 +40,13 @@ test_expect_success 'setup' '
 		x=$(($j + 1)) &&
 		test_commit "$x-1" &&
 		git branch -f commit-$x-1 &&
+		git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
 
 		for i in $(test_seq 2 10)
 		do
 			git merge commit-$j-$i -m "$x-$i" &&
-			git branch -f commit-$x-$i
+			git branch -f commit-$x-$i &&
+			git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i
 		done
 	done &&
 	git commit-graph write --reachable &&
@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '
 	test_three_modes can_all_from_reach
 '
 
+test_expect_success 'can_all_from_reach_with_flag: tags case' '
+	cat >input <<-\EOF &&
+	X:tag-2-10
+	X:tag-3-9
+	X:tag-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:tag-1-9
+	Y:tag-2-8
+	Y:tag-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-7-3
+	Y:commit-8-1
+	EOF
+	echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
+	test_three_modes can_all_from_reach_with_flag
+'
+
 test_expect_success 'commit_contains:hit' '
 	cat >input <<-\EOF &&
 	A:commit-7-7
-- 
gitgitgadget

Re: [PATCH v2 1/1] commit-reach: properly peel tags

[Derrick Stolee]

On 9/13/2018 12:10 PM, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@microsoft.com>
>
> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
> "commit-reach: make can_all_from_reach... linear" but incorrectly
> assumed that all objects provided were commits. During a fetch
> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
> to the 'from' array. The current code creates a segfault.
>
> Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
> and add a test in t6600-test-reach.sh that demonstrates this segfault.
>
> Correct the issue by peeling tags when investigating the initial list
> of objects in the 'from' array.
>
> Signed-off-by: Jeff King <peff@peff.net>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>   commit-reach.c        | 33 ++++++++++++++++++++++++++-------
>   t/helper/test-reach.c | 22 +++++++++++++++++-----
>   t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
>   3 files changed, 71 insertions(+), 14 deletions(-)
>
> diff --git a/commit-reach.c b/commit-reach.c
> index 86715c103c..4048a2132a 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -544,20 +544,39 @@ int can_all_from_reach_with_flag(struct object_array *from,
>   {
>   	struct commit **list = NULL;
>   	int i;
> +	int nr_commits;
>   	int result = 1;
>   
>   	ALLOC_ARRAY(list, from->nr);
> +	nr_commits = 0;
>   	for (i = 0; i < from->nr; i++) {
> -		list[i] = (struct commit *)from->objects[i].item;
> +		struct object *from_one = from->objects[i].item;
>   
> -		if (parse_commit(list[i]) ||
> -		    list[i]->generation < min_generation)
> -			return 0;
> +		if (!from_one || from_one->flags & assign_flag)
> +			continue;
> +
> +		from_one = deref_tag(the_repository, from_one,
> +				     "a from object", 0);
> +		if (!from_one || from_one->type != OBJ_COMMIT) {
> +			/* no way to tell if this is reachable by
> +			 * looking at the ancestry chain alone, so
> +			 * leave a note to ourselves not to worry about
> +			 * this object anymore.
> +			 */
> +			from->objects[i].item->flags |= assign_flag;
> +			continue;
> +		}
> +
> +		list[nr_commits] = (struct commit *)from_one;
> +		if (parse_commit(list[nr_commits]) ||
> +		    list[nr_commits]->generation < min_generation)
> +			return 0; /* is this a leak? */

Of course, after sending v2, I see this comment. This is a leak of 
'list' and should be fixed.

Not only is it a leak here, it is also a leak in the 'cleanup' section. 
I'll squash the following into v3, but I'll let v2 simmer for review 
before rerolling.


diff --git a/commit-reach.c b/commit-reach.c
index 4048a2132a..c457d8d85f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct 
object_array *from,

                 list[nr_commits] = (struct commit *)from_one;
                 if (parse_commit(list[nr_commits]) ||
-                   list[nr_commits]->generation < min_generation)
-                       return 0; /* is this a leak? */
+                   list[nr_commits]->generation < min_generation) {
+                       result = 0;
+                       goto cleanup;
+               }
+
                 nr_commits++;
         }

@@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct object_array 
*from,
                 clear_commit_marks(list[i], RESULT);
                 clear_commit_marks(list[i], assign_flag);
         }
+       free(list);
         return result;
  }

Re: [PATCH v2 1/1] commit-reach: properly peel tags

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

>> +		if (!from_one || from_one->type != OBJ_COMMIT) {
>> +			/* no way to tell if this is reachable by
>> +			 * looking at the ancestry chain alone, so
>> +			 * leave a note to ourselves not to worry about
>> +			 * this object anymore.
>> +			 */
>> +			from->objects[i].item->flags |= assign_flag;
>> +			continue;
>> +		}
>> +
>> +		list[nr_commits] = (struct commit *)from_one;
>> +		if (parse_commit(list[nr_commits]) ||
>> +		    list[nr_commits]->generation < min_generation)
>> +			return 0; /* is this a leak? */
>
> Of course, after sending v2, I see this comment. This is a leak of
> 'list' and should be fixed.
>
> Not only is it a leak here, it is also a leak in the 'cleanup'
> section. I'll squash the following into v3, but I'll let v2 simmer for
> review before rerolling.
>
> diff --git a/commit-reach.c b/commit-reach.c
> index 4048a2132a..c457d8d85f 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -569,8 +569,11 @@ int can_all_from_reach_with_flag(struct
> object_array *from,
>
>                 list[nr_commits] = (struct commit *)from_one;
>                 if (parse_commit(list[nr_commits]) ||
> -                   list[nr_commits]->generation < min_generation)
> -                       return 0; /* is this a leak? */
> +                   list[nr_commits]->generation < min_generation) {
> +                       result = 0;
> +                       goto cleanup;
> +               }
> +
>                 nr_commits++;
>         }
>
> @@ -623,6 +626,7 @@ int can_all_from_reach_with_flag(struct
> object_array *from,
>                 clear_commit_marks(list[i], RESULT);
>                 clear_commit_marks(list[i], assign_flag);
>         }
> +       free(list);
>         return result;
>  }

With this, commit marks are cleared even when we do the "early
return", but only for the objects that appear in the resulting
list[].  Because the for() loop in the last hunk interates over
list[], those non-commit objects that are smudged with assign_flag
but never made to list[] will be left smudged when this function
returns (this is true when there is no early return).  

Is that intended?

[PATCH v3 0/2] Properly peel tags in can_all_from_reach_with_flags()

[Derrick Stolee via GitGitGadget]

As Peff reported [1], the refactored can_all_from_reach_with_flags() method
does not properly peel tags. Since the helper method can_all_from_reach()
and code in t/helper/test-reach.c all peel tags before getting to this
method, it is not super-simple to create a test that demonstrates this.

I modified t/helper/test-reach.c to allow calling
can_all_from_reach_with_flags() directly, and added a test in
t6600-test-reach.sh that demonstrates the segfault without the fix.

For V2, I compared the loop that inspects the 'from' commits in commit
ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version
here and got the following diff:

3c3
<                 if (from_one->flags & assign_flag)
---
>                 if (!from_one || from_one->flags & assign_flag)
5c5,7
<                 from_one = deref_tag(the_repository, from_one, "a from object", 0);
---
>
>                 from_one = deref_tag(the_repository, from_one,
>                                      "a from object", 0);
14a17,22
>
>                 list[nr_commits] = (struct commit *)from_one;
>                 if (parse_commit(list[nr_commits]) ||
>                     list[nr_commits]->generation < min_generation)
>                         return 0; /* is this a leak? */
>                 nr_commits++;

This diff includes the early termination we had before 'deref_tag' and the
comment for why we can ignore non-commit objects.

[1] 
https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u

Derrick Stolee (2):
  commit-reach: properly peel tags
  commit-reach: fix memory and flag leaks

 commit-reach.c        | 41 ++++++++++++++++++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 79 insertions(+), 14 deletions(-)


base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/39

Range-diff vs v2:

 1:  4bf21204dd ! 1:  0a1e661271 commit-reach: properly peel tags
     @@ -53,8 +53,11 @@
      +
      +		list[nr_commits] = (struct commit *)from_one;
      +		if (parse_commit(list[nr_commits]) ||
     -+		    list[nr_commits]->generation < min_generation)
     -+			return 0; /* is this a leak? */
     ++		    list[nr_commits]->generation < min_generation) {
     ++			result = 0;
     ++			goto cleanup;
     ++		}
     ++
      +		nr_commits++;
       	}
       
 -:  ---------- > 2:  b2e0ee4978 commit-reach: fix memory and flag leaks

-- 
gitgitgadget

[PATCH v3 1/2] commit-reach: properly peel tags

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
"commit-reach: make can_all_from_reach... linear" but incorrectly
assumed that all objects provided were commits. During a fetch
negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
to the 'from' array. The current code creates a segfault.

Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
and add a test in t6600-test-reach.sh that demonstrates this segfault.

Correct the issue by peeling tags when investigating the initial list
of objects in the 'from' array.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c        | 36 +++++++++++++++++++++++++++++-------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 ++++++++++++++++++++++++++++--
 3 files changed, 74 insertions(+), 14 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 86715c103c..e748414d04 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,
 {
 	struct commit **list = NULL;
 	int i;
+	int nr_commits;
 	int result = 1;
 
 	ALLOC_ARRAY(list, from->nr);
+	nr_commits = 0;
 	for (i = 0; i < from->nr; i++) {
-		list[i] = (struct commit *)from->objects[i].item;
+		struct object *from_one = from->objects[i].item;
 
-		if (parse_commit(list[i]) ||
-		    list[i]->generation < min_generation)
-			return 0;
+		if (!from_one || from_one->flags & assign_flag)
+			continue;
+
+		from_one = deref_tag(the_repository, from_one,
+				     "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
+			/* no way to tell if this is reachable by
+			 * looking at the ancestry chain alone, so
+			 * leave a note to ourselves not to worry about
+			 * this object anymore.
+			 */
+			from->objects[i].item->flags |= assign_flag;
+			continue;
+		}
+
+		list[nr_commits] = (struct commit *)from_one;
+		if (parse_commit(list[nr_commits]) ||
+		    list[nr_commits]->generation < min_generation) {
+			result = 0;
+			goto cleanup;
+		}
+
+		nr_commits++;
 	}
 
-	QSORT(list, from->nr, compare_commits_by_gen);
+	QSORT(list, nr_commits, compare_commits_by_gen);
 
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */
 		struct commit_list *stack = NULL;
 
@@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		clear_commit_marks(list[i], RESULT);
 		clear_commit_marks(list[i], assign_flag);
 	}
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index eb21103998..08d2ea68e8 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
 	struct commit_list *X, *Y;
+	struct object_array X_obj = OBJECT_ARRAY_INIT;
 	struct commit **X_array;
 	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;
@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;
-		struct object *o;
+		struct object *orig;
+		struct object *peeled;
 		struct commit *c;
 		if (buf.len < 3)
 			continue;
@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)
 		if (get_oid_committish(buf.buf + 2, &oid))
 			die("failed to resolve %s", buf.buf + 2);
 
-		o = parse_object(r, &oid);
-		o = deref_tag_noverify(o);
+		orig = parse_object(r, &oid);
+		peeled = deref_tag_noverify(orig);
 
-		if (!o)
+		if (!peeled)
 			die("failed to load commit for input %s resulting in oid %s\n",
 			    buf.buf, oid_to_hex(&oid));
 
-		c = object_as_type(r, o, OBJ_COMMIT, 0);
+		c = object_as_type(r, peeled, OBJ_COMMIT, 0);
 
 		if (!c)
 			die("failed to load commit for input %s resulting in oid %s\n",
@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)
 				commit_list_insert(c, &X);
 				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
 				X_array[X_nr++] = c;
+				add_object_array(orig, NULL, &X_obj);
 				break;
 
 			case 'Y':
@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)
 		print_sorted_commit_ids(list);
 	} else if (!strcmp(av[1], "can_all_from_reach")) {
 		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
+	} else if (!strcmp(av[1], "can_all_from_reach_with_flag")) {
+		struct commit_list *iter = Y;
+
+		while (iter) {
+			iter->item->object.flags |= 2;
+			iter = iter->next;
+		}
+
+		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
 	} else if (!strcmp(av[1], "commit_contains")) {
 		struct ref_filter filter;
 		struct contains_cache cache;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index d139a00d1d..ae94b27f70 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -31,7 +31,8 @@ test_expect_success 'setup' '
 	for i in $(test_seq 1 10)
 	do
 		test_commit "1-$i" &&
-		git branch -f commit-1-$i
+		git branch -f commit-1-$i &&
+		git tag -a -m "1-$i" tag-1-$i commit-1-$i
 	done &&
 	for j in $(test_seq 1 9)
 	do
@@ -39,11 +40,13 @@ test_expect_success 'setup' '
 		x=$(($j + 1)) &&
 		test_commit "$x-1" &&
 		git branch -f commit-$x-1 &&
+		git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
 
 		for i in $(test_seq 2 10)
 		do
 			git merge commit-$j-$i -m "$x-$i" &&
-			git branch -f commit-$x-$i
+			git branch -f commit-$x-$i &&
+			git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i
 		done
 	done &&
 	git commit-graph write --reachable &&
@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '
 	test_three_modes can_all_from_reach
 '
 
+test_expect_success 'can_all_from_reach_with_flag: tags case' '
+	cat >input <<-\EOF &&
+	X:tag-2-10
+	X:tag-3-9
+	X:tag-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:tag-1-9
+	Y:tag-2-8
+	Y:tag-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-7-3
+	Y:commit-8-1
+	EOF
+	echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
+	test_three_modes can_all_from_reach_with_flag
+'
+
 test_expect_success 'commit_contains:hit' '
 	cat >input <<-\EOF &&
 	A:commit-7-7
-- 
gitgitgadget

[PATCH v3 2/2] commit-reach: fix memory and flag leaks

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The can_all_from_reach_with_flag() method uses 'assign_flag' as a
value we can use to mark objects temporarily during our commit walk.
The intent is that these flags are removed from all objects before
returning. However, this is not the case.

The 'from' array could also contain objects that are not commits, and
we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
section that removes these markers.

Also, we forgot to free() the memory for 'list', so add that to the
'cleanup' section.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/commit-reach.c b/commit-reach.c
index e748414d04..5a845440a9 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -626,6 +626,11 @@ cleanup:
 		clear_commit_marks(list[i], RESULT);
 		clear_commit_marks(list[i], assign_flag);
 	}
+	free(list);
+
+	for (i = 0; i < from->nr; i++)
+		from->objects[i].item->flags &= ~assign_flag;
+
 	return result;
 }
 
-- 
gitgitgadget

Re: [PATCH v3 1/2] commit-reach: properly peel tags

[Jeff King]

On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote:

> diff --git a/commit-reach.c b/commit-reach.c
> index 86715c103c..e748414d04 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  {
>  	struct commit **list = NULL;
>  	int i;
> +	int nr_commits;
>  	int result = 1;
>  
>  	ALLOC_ARRAY(list, from->nr);
> +	nr_commits = 0;
>  	for (i = 0; i < from->nr; i++) {
> -		list[i] = (struct commit *)from->objects[i].item;
> +		struct object *from_one = from->objects[i].item;
>  
> -		if (parse_commit(list[i]) ||
> -		    list[i]->generation < min_generation)
> -			return 0;
> +		if (!from_one || from_one->flags & assign_flag)
> +			continue;
> +
> +		from_one = deref_tag(the_repository, from_one,
> +				     "a from object", 0);
> +		if (!from_one || from_one->type != OBJ_COMMIT) {
> +			/* no way to tell if this is reachable by
> +			 * looking at the ancestry chain alone, so
> +			 * leave a note to ourselves not to worry about
> +			 * this object anymore.
> +			 */

A minor nit, but the original comment you restored here has a style
violation. Might be worth fixing up (but certainly not worth a re-roll
on its own).

> +			from->objects[i].item->flags |= assign_flag;

OK, so here we mark the original tag with a flag...

> +
> +		list[nr_commits] = (struct commit *)from_one;
> +		if (parse_commit(list[nr_commits]) ||
> +		    list[nr_commits]->generation < min_generation) {
> +			result = 0;
> +			goto cleanup;
> +		}

And we jump to the cleanup here, but...

> @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  	}
>  
>  cleanup:
> -	for (i = 0; i < from->nr; i++) {
> +	for (i = 0; i < nr_commits; i++) {
>  		clear_commit_marks(list[i], RESULT);
>  		clear_commit_marks(list[i], assign_flag);

This walks over the items in the list array, which don't include the tag
we marked. Did we decide that's OK? I think it's actually how the
original code behaved, too, but it seems funny. At the least we might
want to call it out in the commit message.

Should we also be walking from->objects and clearing the flags from
there (maybe not RESULT, but assign_flag)? It's not clear to me if it's
unintentional for those to be marked after the function leaves or not.

Also, a minor aside, but I think it would be slightly more efficient for
those final two lines to do:

  clear_commit_marks(list[i], RESULT | assign_flag);

Of course, that's totally orthogonal to this patch, but it may make you
feel better to offset the other round of clearing I'm suggesting. ;)

> diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
> index eb21103998..08d2ea68e8 100644
> --- a/t/helper/test-reach.c
> +++ b/t/helper/test-reach.c

These bits all looked good to me.

-Peff

Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks

[Jeff King]

On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The can_all_from_reach_with_flag() method uses 'assign_flag' as a
> value we can use to mark objects temporarily during our commit walk.
> The intent is that these flags are removed from all objects before
> returning. However, this is not the case.
> 
> The 'from' array could also contain objects that are not commits, and
> we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
> section that removes these markers.
> 
> Also, we forgot to free() the memory for 'list', so add that to the
> 'cleanup' section.

Urgh, ignore most of my response to patch 1, then. I saw there was a
patch 2, but thought it was just handling the free().

The flag-clearing here makes perfect sense.

-Peff

Re: [PATCH v3 1/2] commit-reach: properly peel tags

[Derrick Stolee]

On 9/21/2018 7:56 PM, Jeff King wrote:
> On Fri, Sep 21, 2018 at 08:05:26AM -0700, Derrick Stolee via GitGitGadget wrote:
> +		if (!from_one || from_one->type != OBJ_COMMIT) {
> +			/* no way to tell if this is reachable by
> +			 * looking at the ancestry chain alone, so
> +			 * leave a note to ourselves not to worry about
> +			 * this object anymore.
> +			 */
> A minor nit, but the original comment you restored here has a style
> violation. Might be worth fixing up (but certainly not worth a re-roll
> on its own).
>
>> @@ -600,7 +622,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>>   	}
>>   
>>   cleanup:
>> -	for (i = 0; i < from->nr; i++) {
>> +	for (i = 0; i < nr_commits; i++) {
>>   		clear_commit_marks(list[i], RESULT);
>>   		clear_commit_marks(list[i], assign_flag);
> Also, a minor aside, but I think it would be slightly more efficient for
> those final two lines to do:
>
>    clear_commit_marks(list[i], RESULT | assign_flag);
>
> Of course, that's totally orthogonal to this patch, but it may make you
> feel better to offset the other round of clearing I'm suggesting. ;)

This is definitely a better thing to do, and I'll make the change in v4, 
along with the comment style cleanup above.

Thanks,

-Stolee

Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks

[Derrick Stolee]

On 9/21/2018 7:58 PM, Jeff King wrote:
> On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:
>
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> The can_all_from_reach_with_flag() method uses 'assign_flag' as a
>> value we can use to mark objects temporarily during our commit walk.
>> The intent is that these flags are removed from all objects before
>> returning. However, this is not the case.
>>
>> The 'from' array could also contain objects that are not commits, and
>> we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
>> section that removes these markers.
>>
>> Also, we forgot to free() the memory for 'list', so add that to the
>> 'cleanup' section.
> Urgh, ignore most of my response to patch 1, then. I saw there was a
> patch 2, but thought it was just handling the free().
>
> The flag-clearing here makes perfect sense.

In my local branch, I ended up squashing this commit into the previous, 
because I discovered clear_commit_marks_many() making the cleanup 
section have this diff:

@@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct 
object_array *from,
         }

  cleanup:
-       for (i = 0; i < from->nr; i++) {
-               clear_commit_marks(list[i], RESULT);
-               clear_commit_marks(list[i], assign_flag);
-       }
+       clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
+       free(list);
+
+       for (i = 0; i < from->nr; i++)
+               from->objects[i].item->flags &= ~assign_flag;
+
         return result;
  }

With the bigger change in the larger set, there is less reason to do 
separate commits. (Plus, it confused you during review.)

Thanks,

-Stolee

Re: [PATCH v3 2/2] commit-reach: fix memory and flag leaks

[Jeff King]

On Mon, Sep 24, 2018 at 01:25:12PM -0400, Derrick Stolee wrote:

> On 9/21/2018 7:58 PM, Jeff King wrote:
> > On Fri, Sep 21, 2018 at 08:05:27AM -0700, Derrick Stolee via GitGitGadget wrote:
> > 
> > > From: Derrick Stolee <dstolee@microsoft.com>
> > > 
> > > The can_all_from_reach_with_flag() method uses 'assign_flag' as a
> > > value we can use to mark objects temporarily during our commit walk.
> > > The intent is that these flags are removed from all objects before
> > > returning. However, this is not the case.
> > > 
> > > The 'from' array could also contain objects that are not commits, and
> > > we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
> > > section that removes these markers.
> > > 
> > > Also, we forgot to free() the memory for 'list', so add that to the
> > > 'cleanup' section.
> > Urgh, ignore most of my response to patch 1, then. I saw there was a
> > patch 2, but thought it was just handling the free().
> > 
> > The flag-clearing here makes perfect sense.
> 
> In my local branch, I ended up squashing this commit into the previous,
> because I discovered clear_commit_marks_many() making the cleanup section
> have this diff:
> 
> @@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array
> *from,
>         }
> 
>  cleanup:
> -       for (i = 0; i < from->nr; i++) {
> -               clear_commit_marks(list[i], RESULT);
> -               clear_commit_marks(list[i], assign_flag);
> -       }
> +       clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
> +       free(list);
> +
> +       for (i = 0; i < from->nr; i++)
> +               from->objects[i].item->flags &= ~assign_flag;
> +
>         return result;
>  }
> 
> With the bigger change in the larger set, there is less reason to do
> separate commits. (Plus, it confused you during review.)

Yeah, that looks better still. Thanks!

-Peff

[PATCH v4 0/1] Properly peel tags in can_all_from_reach_with_flags()

[Derrick Stolee via GitGitGadget]

As Peff reported [1], the refactored can_all_from_reach_with_flags() method
does not properly peel tags. Since the helper method can_all_from_reach()
and code in t/helper/test-reach.c all peel tags before getting to this
method, it is not super-simple to create a test that demonstrates this.

I modified t/helper/test-reach.c to allow calling
can_all_from_reach_with_flags() directly, and added a test in
t6600-test-reach.sh that demonstrates the segfault without the fix.

For V2, I compared the loop that inspects the 'from' commits in commit
ba3ca1edce "commit-reach: move can_all_from_reach_with_flags" to the version
here and got the following diff:

3c3
<                 if (from_one->flags & assign_flag)
---
>                 if (!from_one || from_one->flags & assign_flag)
5c5,7
<                 from_one = deref_tag(the_repository, from_one, "a from object", 0);
---
>
>                 from_one = deref_tag(the_repository, from_one,
>                                      "a from object", 0);
14a17,22
>
>                 list[nr_commits] = (struct commit *)from_one;
>                 if (parse_commit(list[nr_commits]) ||
>                     list[nr_commits]->generation < min_generation)
>                         return 0; /* is this a leak? */
>                 nr_commits++;

This diff includes the early termination we had before 'deref_tag' and the
comment for why we can ignore non-commit objects.

[1] 
https://public-inbox.org/git/0bf9103c-9377-506b-7ad7-e5273d8e94fc@gmail.com/T/#u

Derrick Stolee (1):
  commit-reach: properly peel tags and clear flags

 commit-reach.c        | 44 +++++++++++++++++++++++++++++++++----------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++--
 3 files changed, 79 insertions(+), 17 deletions(-)


base-commit: 6621c838743812aaba96e55cfec8524ea1144c2d
Published-As: https://github.com/gitgitgadget/git/releases/tags/pr-39%2Fderrickstolee%2Ftag-fix-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-39/derrickstolee/tag-fix-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/39

Range-diff vs v3:

 1:  0a1e661271 ! 1:  a0a3cf0134 commit-reach: properly peel tags
     @@ -1,6 +1,6 @@
      Author: Derrick Stolee <dstolee@microsoft.com>
      
     -    commit-reach: properly peel tags
     +    commit-reach: properly peel tags and clear flags
      
          The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
          "commit-reach: make can_all_from_reach... linear" but incorrectly
     @@ -14,6 +14,19 @@
          Correct the issue by peeling tags when investigating the initial list
          of objects in the 'from' array.
      
     +    The can_all_from_reach_with_flag() method uses 'assign_flag' as a
     +    value we can use to mark objects temporarily during our commit walk.
     +    The intent is that these flags are removed from all objects before
     +    returning. However, this is not the case.
     +
     +    The 'from' array could also contain objects that are not commits, and
     +    we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
     +    section that removes these markers.
     +
     +    Also, we forgot to free() the memory for 'list', so add that to the
     +    'cleanup' section. Also, use a cleaner mechanism for clearing those
     +    flags.
     +
          Signed-off-by: Jeff King <peff@peff.net>
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
     @@ -74,10 +87,18 @@
       
       cleanup:
      -	for (i = 0; i < from->nr; i++) {
     -+	for (i = 0; i < nr_commits; i++) {
     - 		clear_commit_marks(list[i], RESULT);
     - 		clear_commit_marks(list[i], assign_flag);
     - 	}
     +-		clear_commit_marks(list[i], RESULT);
     +-		clear_commit_marks(list[i], assign_flag);
     +-	}
     ++	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
     ++	free(list);
     ++
     ++	for (i = 0; i < from->nr; i++)
     ++		from->objects[i].item->flags &= ~assign_flag;
     ++
     + 	return result;
     + }
     + 
      
      diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
      --- a/t/helper/test-reach.c
 2:  b2e0ee4978 < -:  ---------- commit-reach: fix memory and flag leaks

-- 
gitgitgadget

[PATCH v4 1/1] commit-reach: properly peel tags and clear flags

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
"commit-reach: make can_all_from_reach... linear" but incorrectly
assumed that all objects provided were commits. During a fetch
negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
to the 'from' array. The current code creates a segfault.

Add a direct call to can_all_from_reach_with_flag() in 'test-tool reach'
and add a test in t6600-test-reach.sh that demonstrates this segfault.

Correct the issue by peeling tags when investigating the initial list
of objects in the 'from' array.

The can_all_from_reach_with_flag() method uses 'assign_flag' as a
value we can use to mark objects temporarily during our commit walk.
The intent is that these flags are removed from all objects before
returning. However, this is not the case.

The 'from' array could also contain objects that are not commits, and
we mark those objects with 'assign_flag'. Add a loop to the 'cleanup'
section that removes these markers.

Also, we forgot to free() the memory for 'list', so add that to the
'cleanup' section. Also, use a cleaner mechanism for clearing those
flags.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c        | 44 +++++++++++++++++++++++++++++++++----------
 t/helper/test-reach.c | 22 +++++++++++++++++-----
 t/t6600-test-reach.sh | 30 +++++++++++++++++++++++++++--
 3 files changed, 79 insertions(+), 17 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 86715c103c..db84f85986 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,
 {
 	struct commit **list = NULL;
 	int i;
+	int nr_commits;
 	int result = 1;
 
 	ALLOC_ARRAY(list, from->nr);
+	nr_commits = 0;
 	for (i = 0; i < from->nr; i++) {
-		list[i] = (struct commit *)from->objects[i].item;
+		struct object *from_one = from->objects[i].item;
 
-		if (parse_commit(list[i]) ||
-		    list[i]->generation < min_generation)
-			return 0;
+		if (!from_one || from_one->flags & assign_flag)
+			continue;
+
+		from_one = deref_tag(the_repository, from_one,
+				     "a from object", 0);
+		if (!from_one || from_one->type != OBJ_COMMIT) {
+			/* no way to tell if this is reachable by
+			 * looking at the ancestry chain alone, so
+			 * leave a note to ourselves not to worry about
+			 * this object anymore.
+			 */
+			from->objects[i].item->flags |= assign_flag;
+			continue;
+		}
+
+		list[nr_commits] = (struct commit *)from_one;
+		if (parse_commit(list[nr_commits]) ||
+		    list[nr_commits]->generation < min_generation) {
+			result = 0;
+			goto cleanup;
+		}
+
+		nr_commits++;
 	}
 
-	QSORT(list, from->nr, compare_commits_by_gen);
+	QSORT(list, nr_commits, compare_commits_by_gen);
 
-	for (i = 0; i < from->nr; i++) {
+	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */
 		struct commit_list *stack = NULL;
 
@@ -600,10 +622,12 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < from->nr; i++) {
-		clear_commit_marks(list[i], RESULT);
-		clear_commit_marks(list[i], assign_flag);
-	}
+	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
+	free(list);
+
+	for (i = 0; i < from->nr; i++)
+		from->objects[i].item->flags &= ~assign_flag;
+
 	return result;
 }
 
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index eb21103998..08d2ea68e8 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -31,6 +31,7 @@ int cmd__reach(int ac, const char **av)
 	struct object_id oid_A, oid_B;
 	struct commit *A, *B;
 	struct commit_list *X, *Y;
+	struct object_array X_obj = OBJECT_ARRAY_INIT;
 	struct commit **X_array;
 	int X_nr, X_alloc;
 	struct strbuf buf = STRBUF_INIT;
@@ -49,7 +50,8 @@ int cmd__reach(int ac, const char **av)
 
 	while (strbuf_getline(&buf, stdin) != EOF) {
 		struct object_id oid;
-		struct object *o;
+		struct object *orig;
+		struct object *peeled;
 		struct commit *c;
 		if (buf.len < 3)
 			continue;
@@ -57,14 +59,14 @@ int cmd__reach(int ac, const char **av)
 		if (get_oid_committish(buf.buf + 2, &oid))
 			die("failed to resolve %s", buf.buf + 2);
 
-		o = parse_object(r, &oid);
-		o = deref_tag_noverify(o);
+		orig = parse_object(r, &oid);
+		peeled = deref_tag_noverify(orig);
 
-		if (!o)
+		if (!peeled)
 			die("failed to load commit for input %s resulting in oid %s\n",
 			    buf.buf, oid_to_hex(&oid));
 
-		c = object_as_type(r, o, OBJ_COMMIT, 0);
+		c = object_as_type(r, peeled, OBJ_COMMIT, 0);
 
 		if (!c)
 			die("failed to load commit for input %s resulting in oid %s\n",
@@ -85,6 +87,7 @@ int cmd__reach(int ac, const char **av)
 				commit_list_insert(c, &X);
 				ALLOC_GROW(X_array, X_nr + 1, X_alloc);
 				X_array[X_nr++] = c;
+				add_object_array(orig, NULL, &X_obj);
 				break;
 
 			case 'Y':
@@ -113,6 +116,15 @@ int cmd__reach(int ac, const char **av)
 		print_sorted_commit_ids(list);
 	} else if (!strcmp(av[1], "can_all_from_reach")) {
 		printf("%s(X,Y):%d\n", av[1], can_all_from_reach(X, Y, 1));
+	} else if (!strcmp(av[1], "can_all_from_reach_with_flag")) {
+		struct commit_list *iter = Y;
+
+		while (iter) {
+			iter->item->object.flags |= 2;
+			iter = iter->next;
+		}
+
+		printf("%s(X,_,_,0,0):%d\n", av[1], can_all_from_reach_with_flag(&X_obj, 2, 4, 0, 0));
 	} else if (!strcmp(av[1], "commit_contains")) {
 		struct ref_filter filter;
 		struct contains_cache cache;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index d139a00d1d..ae94b27f70 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -31,7 +31,8 @@ test_expect_success 'setup' '
 	for i in $(test_seq 1 10)
 	do
 		test_commit "1-$i" &&
-		git branch -f commit-1-$i
+		git branch -f commit-1-$i &&
+		git tag -a -m "1-$i" tag-1-$i commit-1-$i
 	done &&
 	for j in $(test_seq 1 9)
 	do
@@ -39,11 +40,13 @@ test_expect_success 'setup' '
 		x=$(($j + 1)) &&
 		test_commit "$x-1" &&
 		git branch -f commit-$x-1 &&
+		git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
 
 		for i in $(test_seq 2 10)
 		do
 			git merge commit-$j-$i -m "$x-$i" &&
-			git branch -f commit-$x-$i
+			git branch -f commit-$x-$i &&
+			git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i
 		done
 	done &&
 	git commit-graph write --reachable &&
@@ -205,6 +208,29 @@ test_expect_success 'can_all_from_reach:miss' '
 	test_three_modes can_all_from_reach
 '
 
+test_expect_success 'can_all_from_reach_with_flag: tags case' '
+	cat >input <<-\EOF &&
+	X:tag-2-10
+	X:tag-3-9
+	X:tag-4-8
+	X:commit-5-7
+	X:commit-6-6
+	X:commit-7-5
+	X:commit-8-4
+	X:commit-9-3
+	Y:tag-1-9
+	Y:tag-2-8
+	Y:tag-3-7
+	Y:commit-4-6
+	Y:commit-5-5
+	Y:commit-6-4
+	Y:commit-7-3
+	Y:commit-8-1
+	EOF
+	echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
+	test_three_modes can_all_from_reach_with_flag
+'
+
 test_expect_success 'commit_contains:hit' '
 	cat >input <<-\EOF &&
 	A:commit-7-7
-- 
gitgitgadget

Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags

[Jeff King]

On Mon, Sep 24, 2018 at 01:57:52PM -0700, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <dstolee@microsoft.com>
> 
> The can_all_from_reach_with_flag() algorithm was refactored in 4fbcca4e
> "commit-reach: make can_all_from_reach... linear" but incorrectly
> assumed that all objects provided were commits. During a fetch
> negotiation, ok_to_give_up() in upload-pack.c may provide unpeeled tags
> to the 'from' array. The current code creates a segfault.
> [...]

Thanks, this version looks good to me.

-Peff

Re: [PATCH v4 1/1] commit-reach: properly peel tags and clear flags

[Eric Sunshine]

On Mon, Sep 24, 2018 at 4:58 PM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
> diff --git a/commit-reach.c b/commit-reach.c
> @@ -544,20 +544,42 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  {
> +               from_one = deref_tag(the_repository, from_one,
> +                                    "a from object", 0);
> +               if (!from_one || from_one->type != OBJ_COMMIT) {
> +                       /* no way to tell if this is reachable by
> +                        * looking at the ancestry chain alone, so
> +                        * leave a note to ourselves not to worry about
> +                        * this object anymore.
> +                        */

Style nit:

    /*
     * Multi-line comment
     * formatting.
     */

[PATCH] commit-reach: cleanups in can_all_from_reach...

[Derrick Stolee]

From: Derrick Stolee <dstolee@microsoft.com>

Due to a regression introduced by 4fbcca4e "commit-reach: make
can_all_from_reach... linear" the series including b67f6b26
"commit-reach: properly peel tags" was merged to master quickly.

There were a few more cleanups left to apply in the series, which
are included by this change:

1. Clean up a comment that is in the incorrect style.

2. Replace multiple calls to clear_commit_marks() with one call to
   clear_commit_marks_many().

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 5a845440a9..66aa41262c 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -558,7 +558,8 @@ int can_all_from_reach_with_flag(struct object_array *from,
 		from_one = deref_tag(the_repository, from_one,
 				     "a from object", 0);
 		if (!from_one || from_one->type != OBJ_COMMIT) {
-			/* no way to tell if this is reachable by
+			/*
+			 * no way to tell if this is reachable by
 			 * looking at the ancestry chain alone, so
 			 * leave a note to ourselves not to worry about
 			 * this object anymore.
@@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 	}
 
 cleanup:
-	for (i = 0; i < nr_commits; i++) {
-		clear_commit_marks(list[i], RESULT);
-		clear_commit_marks(list[i], assign_flag);
-	}
+	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
 	free(list);
 
 	for (i = 0; i < from->nr; i++)

base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b
-- 
2.19.0

Re: [PATCH] commit-reach: cleanups in can_all_from_reach...

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  	}
>  
>  cleanup:
> -	for (i = 0; i < nr_commits; i++) {
> -		clear_commit_marks(list[i], RESULT);
> -		clear_commit_marks(list[i], assign_flag);
> -	}
> +	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
>  	free(list);
>  
>  	for (i = 0; i < from->nr; i++)
>
> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b

This change looks good to me. 

This is a tangent, but while re-reading clear_commit_marks() and its
helpers to refresh my memory, I found that the bottom-most helper in
the callchain was written in a very confusing way, but it is not a
fault of this clean-up.  I however suspect that it would not help us
all that much to use clear_commit_marks_many() with its current
implementation.  It first clears all commits on the first-parent
chain from each list[] element, while accumulating the parent
commits that are yet to be processed in a commit_list in LIFO order,
and then consumes these accumulated side parents the same way.  We
probably would benefit by rewriting clear_commit_marks_many() to
traverse from all the tips given in list[] taking advantage of the
generation numbers, using a prio queue to manage the commits
yet-to-be-cleared, or something.

Re: [PATCH] commit-reach: cleanups in can_all_from_reach...

[Derrick Stolee]

On 9/25/2018 2:06 PM, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
>
>> @@ -622,10 +623,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
>>   	}
>>   
>>   cleanup:
>> -	for (i = 0; i < nr_commits; i++) {
>> -		clear_commit_marks(list[i], RESULT);
>> -		clear_commit_marks(list[i], assign_flag);
>> -	}
>> +	clear_commit_marks_many(nr_commits, list, RESULT | assign_flag);
>>   	free(list);
>>   
>>   	for (i = 0; i < from->nr; i++)
>>
>> base-commit: 4067a64672f9db8ca38d5a2682a7cdba7938c18b
> This change looks good to me.
>
> This is a tangent, but while re-reading clear_commit_marks() and its
> helpers to refresh my memory, I found that the bottom-most helper in
> the callchain was written in a very confusing way, but it is not a
> fault of this clean-up.  I however suspect that it would not help us
> all that much to use clear_commit_marks_many() with its current
> implementation.  It first clears all commits on the first-parent
> chain from each list[] element, while accumulating the parent
> commits that are yet to be processed in a commit_list in LIFO order,
> and then consumes these accumulated side parents the same way.  We
> probably would benefit by rewriting clear_commit_marks_many() to
> traverse from all the tips given in list[] taking advantage of the
> generation numbers, using a prio queue to manage the commits
> yet-to-be-cleared, or something.

Another commit walk that could be improved by generation numbers? It's 
like my bat-signal!

Thanks for pointing me in that direction. I'll take a look.

-Stolee

Re: [PATCH] commit-reach: cleanups in can_all_from_reach...

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> Another commit walk that could be improved by generation numbers? It's
> like my bat-signal!

Ah, nevermind.  The "traversal" done by these helper functions is
the most stupid kind (not the algorthim, but the need).  It's not
like there is an opportunity to optimize by not traversing the
remainder if we choose the order of traversal intelligently, so any
algorithm that does not visit the same node twice and does not do
the most naive recursion would work, and what we currently have
there is just fine.