rebase --autosquash: fix a potential segfault

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>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/sequencer.c b/sequencer.c
index 7798f93b23f2250e61564951b6a467ae19746b36..32266c94e55e2a877ee07b229aa28ada50484972 100644 (file)
--- a/sequencer.c
+++ b/sequencer.c
@@ -5034,10 +5034,13 @@ static 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 (tail[i2] < 0) {
+                               next[i] = next[i2];
                                next[i2] = i;
-                       else
+                       } else {
+                               next[i] = next[tail[i2]];
                                next[tail[i2]] = i;
+                       }
                        tail[i2] = i;
                } else if (!hashmap_get_from_hash(&subject2item,
                                                strhash(subject), subject)) {

diff --git a/t/t3415-rebase-autosquash.sh b/t/t3415-rebase-autosquash.sh
index 13f5688135d853106702b7679eb302f6ae3d1450..03983b3489369afa52d38d0e51dee8eaa4ad84da 100755 (executable)
--- a/t/t3415-rebase-autosquash.sh
+++ b/t/t3415-rebase-autosquash.sh
@@ -349,4 +349,20 @@ test_expect_success 'abort last squash' '
        ! grep first actual
 '
 
+test_expect_success 'fixup a fixup' '
+       echo 0to-fixup >file0 &&
+       test_tick &&
+       git commit -m "to-fixup" file0 &&
+       test_tick &&
+       git commit --squash HEAD -m X --allow-empty &&
+       test_tick &&
+       git commit --squash HEAD^ -m Y --allow-empty &&
+       test_tick &&
+       git commit -m "squash! $(git rev-parse HEAD^)" -m Z --allow-empty &&
+       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