[PATCH 1/8] fixup! combine_diff: simplify intersect_paths() further

From: Kirill Smelkov <kirr@mns.spb.ru>
Date: Feb 3, 2014, 12:47 UTC
Message-ID: <60ec61bdd2ef3cba7537e29c42f9c8a810da245d.1391430523.git.kirr@mns.spb.ru>
In-Reply-To: <cover.1391430523.git.kirr@mns.spb.ru>

That cleanup patch is good, but I've found a bug in it. In the item removal code

Show 7 quoted lines

> +                      /* p->path not in q->queue[]; drop it */
> +                      struct combine_diff_path *next = p->next;
> +
> +                      if ((*tail = next) != NULL)
> +                              tail = &next->next;
> +                      free(p);
>                        continue;

        *tail = next

is right, but

        tail = &next->next

is wrong, because it will lead to skipping the element after removed one. Proof:

    tail        p
      |         |
      |         |
      v         v
     +-+       +------+-+       +------+-+       +------+-+
     | |       |      | |       |      | |       |      | |
     |o------->|      |o------->|      |o------->|      |o------->
     |0|       |     1| |       |     2| |       |     3| |
     +-+       +------+-+       +------+-+       +------+-+

suppose, we are removing element 1. p->next points to 2, after

    *tail = next

0 points to 2, which != NULL. After

    tail = &next->next

tail points to &2->next.

On the next cycle iteration, after

    p = *tail

we'll have

    p = *2->next = 3

so 2 was skipped, oops.

I've actually hit the bug - when generating combine-diff, for merges with should-be empty `log -c` output, every second path was present in the diff. That, by the way, means we need to extend combine-diff tests somewhat.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 combine-diff.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/combine-diff.c b/combine-diff.c
index 0809e79..a03147c 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -58,8 +58,7 @@ static struct combine_diff_path *intersect_paths(struct combine_diff_path *curr,
 			/* p->path not in q->queue[]; drop it */
 			struct combine_diff_path *next = p->next;
 
-			if ((*tail = next) != NULL)
-				tail = &next->next;
+			*tail = next;
 			free(p);
 			continue;
 		}

-- 
1.9.rc1.181.g641f458