[GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

Instead of manually doing an in-place list reversal, use the helper
function reverse_commit_list(), hence improving code readability.

Signed-off-by: Kousik Sanagavarapu <five231003@gmail.com>
---

This patch addresses the issue #1156(Use reverse_commit_list() in more
places) on gitgitgadget. I also would like to submit this patch as the microproject for
GSoC 2023.

 builtin/merge.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 5900b81729..4503dbfeb3 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -736,7 +736,6 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 		struct commit *result;
 		struct commit_list *reversed = NULL;
 		struct merge_options o;
-		struct commit_list *j;
 
 		if (remoteheads->next) {
 			error(_("Not handling anything other than two heads merge."));
@@ -757,8 +756,7 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 		o.branch1 = head_arg;
 		o.branch2 = merge_remote_util(remoteheads->item)->name;
 
-		for (j = common; j; j = j->next)
-			commit_list_insert(j->item, &reversed);
+		reversed = reverse_commit_list(common);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
 		if (!strcmp(strategy, "ort"))
-- 
2.25.1

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Junio C Hamano]

Kousik Sanagavarapu <five231003@gmail.com> writes:

> Instead of manually doing an in-place list reversal, use the helper
> function reverse_commit_list(), hence improving code readability.

But isn't reverse_commit_list() destructive in that it reuses the
elements on the original list to create the reversed list?  The
original code creates a new and separate list, so even when
try_merge_strategy() is called many times, its "common" parameter
given by the caller stays the same.

What happens in the second and subsequent call to
try_merge_strategy() in your updated version?  The element pointed
at by the "common" variable, which is the first element of the list
in the first call, gets its .next member NULLed by calling
reverse_commit_list().  The rest of the try_merge_strategy()
function in its first call might work the same way as before (as
long as it does not use "common" and only uses "reversed"; I did not
check), but because the "common" the caller passed is now a single
element list that consists of itself, and all the other elements are
lost.  The caller uses that same "common" to call try_merge_strategy()
again, with a different strategy.  This second call is getting a common
ancestor list that was already broken by the first call, no?

> Signed-off-by: Kousik Sanagavarapu <five231003@gmail.com>
> ---
>
> This patch addresses the issue #1156(Use reverse_commit_list() in more
> places) on gitgitgadget. I also would like to submit this patch as the microproject for
> GSoC 2023.
>
>  builtin/merge.c | 4 +---
>  1 file changed, 1 insertion(+), 3 deletions(-)
>
> diff --git a/builtin/merge.c b/builtin/merge.c
> index 5900b81729..4503dbfeb3 100644
> --- a/builtin/merge.c
> +++ b/builtin/merge.c
> @@ -736,7 +736,6 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
>  		struct commit *result;
>  		struct commit_list *reversed = NULL;
>  		struct merge_options o;
> -		struct commit_list *j;
>  
>  		if (remoteheads->next) {
>  			error(_("Not handling anything other than two heads merge."));
> @@ -757,8 +756,7 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
>  		o.branch1 = head_arg;
>  		o.branch2 = merge_remote_util(remoteheads->item)->name;
>  
> -		for (j = common; j; j = j->next)
> -			commit_list_insert(j->item, &reversed);
> +		reversed = reverse_commit_list(common);
>  
>  		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
>  		if (!strcmp(strategy, "ort"))

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Elijah Newren]

On Thu, Feb 2, 2023 at 9:10 AM Kousik Sanagavarapu <five231003@gmail.com> wrote:
>
> Instead of manually doing an in-place list reversal, use the helper
> function reverse_commit_list(), hence improving code readability.
>
> Signed-off-by: Kousik Sanagavarapu <five231003@gmail.com>
> ---
>
> This patch addresses the issue #1156(Use reverse_commit_list() in more
> places) on gitgitgadget. I also would like to submit this patch as the microproject for
> GSoC 2023.

Looks like this was a suggestion from me, so I'm to blame.  But
looking at it again, I'm not sure builtin/merge.c is actually a good
candidate because...

>  builtin/merge.c | 4 +---
>  1 file changed, 1 insertion(+), 3 deletions(-)
>
> diff --git a/builtin/merge.c b/builtin/merge.c
> index 5900b81729..4503dbfeb3 100644
> --- a/builtin/merge.c
> +++ b/builtin/merge.c
> @@ -736,7 +736,6 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
>                 struct commit *result;
>                 struct commit_list *reversed = NULL;
>                 struct merge_options o;
> -               struct commit_list *j;
>
>                 if (remoteheads->next) {
>                         error(_("Not handling anything other than two heads merge."));
> @@ -757,8 +756,7 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
>                 o.branch1 = head_arg;
>                 o.branch2 = merge_remote_util(remoteheads->item)->name;
>
> -               for (j = common; j; j = j->next)
> -                       commit_list_insert(j->item, &reversed);

This is not an in-place list reversal; it's creating a new list that
is reversed.  "common" can continue to be used separately from
"reversed" after this point.  (And the new list, "reversed" is
consumed by merge_recursive()/merge_ort_recursive(), so there's
nothing to free.)

> +               reversed = reverse_commit_list(common);

This is an in-place list reversal.  If there's only one merge strategy
being attempted, this may work, since "common" probably won't be used
afterwards.

However, if we have multiple merge strategies that expect to be passed
the common commits -- a situation we probably don't have a testcase
for in the testsuite -- then I think this code change will result in a
use-after-free error.


>                 hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
>                 if (!strcmp(strategy, "ort"))
> --
> 2.25.1

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

When I submitted the patch, I didn't realize that reverse_commit_list() helper
function had such behavior. It was very different from what I had expected.
Maybe I should have been more careful and looked into the details before
submitting the patch.

Thanks for your explanation, it was valuable. Especially on the part where you
explained about the try_merge_strategy() function, it helped me gain more
insight on the whole situation. Sorry for this patch, I will be more careful next time.

P.S. Please ignore the empty email, it was me trying to figure out git-send-email
and how could to reply to specific lines of the email by referencing them. The
email got sent by accident.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

Now, I think I understand the mistake that I did. Even if it did work
for one merge strategy, the code would not be good as the helper function
is not doing what it is intended to do. In any case, I should have been
more careful submitting the patch.

On a side note, I think we can now close the issue #1156 on gitgitgadget? As
with builtin/merge.c out of the way, the only other case is in revision.c
and the use of the helper function there is inapproriate.

Thanks for the explanation.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Elijah Newren]

On Fri, Feb 3, 2023 at 9:49 AM Kousik Sanagavarapu <five231003@gmail.com> wrote:
>
> Now, I think I understand the mistake that I did. Even if it did work
> for one merge strategy, the code would not be good as the helper function
> is not doing what it is intended to do. In any case, I should have been
> more careful submitting the patch.
>
> On a side note, I think we can now close the issue #1156 on gitgitgadget? As
> with builtin/merge.c out of the way, the only other case is in revision.c
> and the use of the helper function there is inapproriate.
>
> Thanks for the explanation.

Yeah, it should have been closed back when
https://lore.kernel.org/git/CANsrJQd0v2V9H8HPkiH2179C1c-NOSTRRB8YXt8v6R0YAbFPDQ@mail.gmail.com/
was submitted.  But none of us caught it.

Also, gitgitgadget #1156 was opened because of my suggestion to do
this as a "leftoverbit", i.e. I was suggesting it as a micro-project
to new people.  I should have checked at the time that it was a valid
micro-project, but neglected to do so.  You merely came along and
started implementing what was suggested.

Anyway, the point of the GSoC microprojects are to make sure you are
familiar with how to format and submit patches to the mailing list and
respond; having the code you contribute in a microproject be accepted
is not required, just a bonus.  And you clearly managed to send the
patch to the list, had a correctly formatted commit message (short
summary with area and correct lack of capitalization, good
descriptions, signed-off-by), got the additional notes for reviewers
(very helpful!) in the correct spot, etc., so I still see this as a
successful microproject for you.  I apologize for not doing my due
diligence when I suggested it, and for us not catching that it should
have been closed when someone implemented the valid half of the
suggestion last year.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> Also, gitgitgadget #1156 was opened because of my suggestion to do
> this as a "leftoverbit", i.e. I was suggesting it as a micro-project
> to new people.  I should have checked at the time that it was a valid
> micro-project, but neglected to do so.  You merely came along and
> started implementing what was suggested.
>
> Anyway, the point of the GSoC microprojects are to make sure you are
> familiar with how to format and submit patches to the mailing list and
> respond; having the code you contribute in a microproject be accepted
> is not required, just a bonus.  And you clearly managed to send the
> patch to the list, had a correctly formatted commit message (short
> summary with area and correct lack of capitalization, good
> descriptions, signed-off-by), got the additional notes for reviewers
> (very helpful!) in the correct spot, etc., so I still see this as a
> successful microproject for you.  I apologize for not doing my due
> diligence when I suggested it, and for us not catching that it should
> have been closed when someone implemented the valid half of the
> suggestion last year.

One possible action item for us may be to rename or give comment to
highlight the in-place destructive nature of the function to make it
easier for developers to use (or avoid misusing) it.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

On Fri, 3 Feb 2023 at 23:32, Elijah Newren <newren@gmail.com> wrote:

> Anyway, the point of the GSoC microprojects are to make sure you are
> familiar with how to format and submit patches to the mailing list and
> respond; having the code you contribute in a microproject be accepted
> is not required, just a bonus.  And you clearly managed to send the
> patch to the list, had a correctly formatted commit message (short
> summary with area and correct lack of capitalization, good
> descriptions, signed-off-by), got the additional notes for reviewers
> (very helpful!) in the correct spot, etc., so I still see this as a
> successful microproject for you.

I still need to get used to the codebase a bit, but the process
itself is fun. I also realized how helpful these notes and discussions
are. Thanks.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

On Fri, 3 Feb 2023 at 23:32, Elijah Newren <newren@gmail.com> wrote:

> Anyway, the point of the GSoC microprojects are to make sure you are
> familiar with how to format and submit patches to the mailing list and
> respond; having the code you contribute in a microproject be accepted
> is not required, just a bonus.  And you clearly managed to send the
> patch to the list, had a correctly formatted commit message (short
> summary with area and correct lack of capitalization, good
> descriptions, signed-off-by), got the additional notes for reviewers
> (very helpful!) in the correct spot, etc., so I still see this as a
> successful microproject for you.

I still need to get used to the codebase a bit, but the process
itself is fun. I also realized how helpful these notes and discussions
are. Thanks.

Re: [GSoC][PATCH] merge: use reverse_commit_list() for list reversal

[Kousik Sanagavarapu]

On Sat, 4 Feb 2023 at 00:37, Junio C Hamano <gitster@pobox.com> wrote:

> One possible action item for us may be to rename or give comment to
> highlight the in-place destructive nature of the function to make it
> easier for developers to use (or avoid misusing) it.

There is a comment describing what the function does in commit.h but
it doesn't  _explicitly_ warn about this destructive behavior (although,
with a little thinking, developers can infer that the function can cause
this behavior after reading the comment). So, maybe we should go with the
comment being a bit more descriptive?

Thanks