[PATCH v3] 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.

Previously, we would update `next` and `tail` under our assumption that every `fixup!` commit would find the start of the `fixup!`/`squash!` chain. This would lead to a segmentation fault because we would actually end up with a `next[i]` pointing to a `fixup!` but the corresponding `tail[i]` pointing nowhere, which would the lead to a segmentation fault.

Let's fix this by _inserting_, rather than _appending_, the item. In other words, if we make a given line successor of another line, we do not simply forget any previously set successor of the latter, but make it a successor of the former.

In the above example, at the point when we insert 04ecb just after 02f12, 03763 would already be recorded as a successor of 04ecb, and we now "squeeze in" 04ecb.

To complete the idea, we now no longer assume that `next[i]` pointing to a line means that `last[i]` points to a line, too. Instead, we extend the concept of `last` to cover also partial `fixup!`/`squash!` chains, i.e. chains starting in the middle of a larger such chain.

In the above example, after processing all lines, `last[0]` (corresponding to 0192a) would point to 03763, which indeed is the end of the overall `fixup!` chain, and `last[1]` (corresponding to 02f12) would point to 04ecb (which is the last `fixup!` targeting 02f12, but it has 03763 as successor, i.e. it is not the end of overall `fixup!` chain).

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 v2:
    
     * Explained the fix more verbosely in the commit message.
    
    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-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-625/dscho/autosquash-segfault-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/625

Range-diff vs v2:

 1:  de029422324 ! 1:  c1c4607da0e rebase --autosquash: fix a potential segfault
     @@ 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 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).
     +    Previously, we would update `next` and `tail` under our assumption that
     +    every `fixup!` commit would find the start of the `fixup!`/`squash!`
     +    chain. This would lead to a segmentation fault because we would actually
     +    end up with a `next[i]` pointing to a `fixup!` but the corresponding
     +    `tail[i]` pointing nowhere, which would the lead to a segmentation
     +    fault.
     +
     +    Let's fix this by _inserting_, rather than _appending_, the item. In
     +    other words, if we make a given line successor of another line, we do
     +    not simply forget any previously set successor of the latter, but make
     +    it a successor of the former.
     +
     +    In the above example, at the point when we insert 04ecb just after
     +    02f12, 03763 would already be recorded as a successor of 04ecb, and we
     +    now "squeeze in" 04ecb.
     +
     +    To complete the idea, we now no longer assume that `next[i]` pointing to
     +    a line means that `last[i]` points to a line, too. Instead, we extend
     +    the concept of `last` to cover also partial `fixup!`/`squash!` chains,
     +    i.e. chains starting in the middle of a larger such chain.
     +
     +    In the above example, after processing all lines, `last[0]`
     +    (corresponding to 0192a) would point to 03763, which indeed is the end
     +    of the overall `fixup!` chain, and `last[1]` (corresponding to 02f12)
     +    would point to 04ecb (which is the last `fixup!` targeting 02f12, but it
     +    has 03763 as successor, i.e. it is not the end of overall `fixup!`
     +    chain).
      
          Reported-by: Paul Ganssle <paul@ganssle.io>
          Helped-by: Jeff King <peff@peff.net>

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