[PATCH v2] rebase --autosquash: fix a potential segfault

From: Johannes Schindelin <johannes.schindelin@gmx.de>

When rearranging the todo list so that the fixups/squashes are reordered just after the commits they intend to fix up, we use two arrays to maintain that list: `next` and `tail`.

The idea is that `next[i]`, if set to a non-negative value, contains the index of the item that should be rearranged just after the `i`th item.

To avoid having to walk the entire `next` chain when appending another fixup/squash, we also store the end of the `next` chain in `tail[i]`.

The logic we currently use to update these array items is based on the assumption that given a fixup/squash item at index `i`, we just found the index `i2` indicating the first item in that fixup chain.

However, as reported by Paul Ganssle, that need not be true: the special form `fixup! <commit-hash>` is allowed to point to _another_ fixup commit in the middle of the fixup chain.

Example:

	* 0192a To fixup
	* 02f12 fixup! To fixup
	* 03763 fixup! To fixup
	* 04ecb fixup! 02f12

Note how the fourth commit targets the second commit, which is already a fixup that targets the first commit.

The good news is that it is easy to fix this: we use the correct condition (we now possibly set `tail[i2]` even for fixups in the middle) and we _also_ have to ensure that we _insert_ the item rather than _append_ it, i.e. we need to set `next[i2]` accordingly (it might still be set to `-1` if it was actually appended).

Reported-by: Paul Ganssle <paul@ganssle.io>
Helped-by: Jeff King <peff@peff.net>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
    rebase --autosquash: fix a potential segfault
    
    This patch is in response to 
    https://lore.kernel.org/git/017dbc40-8d21-00fb-7b0e-6708d2dcb366@ganssle.io/
    .
    
    Changes since v1:
    
     * Fixed the order of two or more fixups-of-fixups (oddly enough, this
       simplified the patch...)
     * Extended the test to have two fixups-of-fixups, ensuring their order
       is preserved.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-625%2Fdscho%2Fautosquash-segfault-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-625/dscho/autosquash-segfault-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/625

Range-diff vs v1:

 1:  bb820acc342 ! 1:  de029422324 rebase --autosquash: fix a potential segfault
     @@ Commit message
          index of the item that should be rearranged just after the `i`th item.
      
          To avoid having to walk the entire `next` chain when appending another
     -    fixup/squash, we also store the end of the `next` chain in `last[i]`.
     +    fixup/squash, we also store the end of the `next` chain in `tail[i]`.
      
          The logic we currently use to update these array items is based on the
          assumption that given a fixup/squash item at index `i`, we just found
     @@ Commit message
          Note how the fourth commit targets the second commit, which is already a
          fixup that targets the first commit.
      
     -    The good news is that it is easy to fix this: we can detect the
     -    situation by looking at `last[i2]` (which will be `-1` if `i2` is
     -    actually in the middle of a fixup chain), and in that case we simply
     -    need to squeeze the current item into the middle of the `next` chain,
     -    without touching `last` (i.e. leaving the end index of the fixup chain
     -    alone).
     +    The good news is that it is easy to fix this: we use the correct
     +    condition (we now possibly set `tail[i2]` even for fixups in the middle)
     +    and we _also_ have to ensure that we _insert_ the item rather than
     +    _append_ it, i.e. we need to set `next[i2]` accordingly (it might still
     +    be set to `-1` if it was actually appended).
      
          Reported-by: Paul Ganssle <paul@ganssle.io>
          Helped-by: Jeff King <peff@peff.net>
     @@ Commit message
      
       ## sequencer.c ##
      @@ sequencer.c: int todo_list_rearrange_squash(struct todo_list *todo_list)
     + 			todo_list->items[i].command =
     + 				starts_with(subject, "fixup!") ?
       				TODO_FIXUP : TODO_SQUASH;
     - 			if (next[i2] < 0)
     +-			if (next[i2] < 0)
     ++			if (tail[i2] < 0) {
     ++				next[i] = next[i2];
       				next[i2] = i;
      -			else
     -+			else if (tail[i2] >= 0)
     ++			} else {
     ++				next[i] = next[tail[i2]];
       				next[tail[i2]] = i;
     -+			else {
     -+				/*
     -+				 * i2 refers to a fixup commit in the middle of
     -+				 * a fixup chain
     -+				 */
     -+				next[i] = next[i2];
     -+				next[i2] = i;
     -+				continue;
      +			}
       			tail[i2] = i;
       		} else if (!hashmap_get_from_hash(&subject2item,
     @@ t/t3415-rebase-autosquash.sh: test_expect_success 'abort last squash' '
      +	git commit --squash HEAD^ -m Y --allow-empty &&
      +	test_tick &&
      +	git commit -m "squash! $(git rev-parse HEAD^)" -m Z --allow-empty &&
     -+	git rebase -ki --autosquash HEAD~4 &&
     -+	test XZY = $(git show | tr -cd X-Z)
     ++	test_tick &&
     ++	git commit -m "squash! $(git rev-parse HEAD^^)" -m W --allow-empty &&
     ++	git rebase -ki --autosquash HEAD~5 &&
     ++	test XZWY = $(git show | tr -cd W-Z)
      +'
      +
       test_done

 sequencer.c                  |  7 +++++--
 t/t3415-rebase-autosquash.sh | 16 ++++++++++++++++
 2 files changed, 21 insertions(+), 2 deletions(-)