From 23a537243b935207ac8a418b9980bacb4e8e6d59 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Fri, 5 May 2017 07:09:22 +0100 Subject: [PATCH] Fix infinite-loop bug in Loopy's autofollow feature. Thanks to Glen Sawyer for reporting it. This is surely a consequence of separating interpret_move from execute_move - if I'd done things in the more obvious way, then this bug would never have happened, because once the autofollow code had gone once round the loop it would find that the starting edge was no longer in the same state it was looking for. But since we don't start changing the states of edges until execute_move(), it's possible for interpret_move() to go round and round a cycle for ever. Fortunately, it can _only_ happen if the edge you clicked on was part of a loop which is the whole of its connected component - i.e. every vertex in the cycle has degree 2 - and therefore we don't need O(N) space to detect it (e.g. by recording whether each edge has been visited already), but instead we can simply check if we've come back to the starting edge. --- loopy.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/loopy.c b/loopy.c index 652b9ec..7d3436a 100644 --- a/loopy.c +++ b/loopy.c @@ -3054,6 +3054,24 @@ static char *interpret_move(const game_state *state, game_ui *ui, state->lines[e_next - g->edges] != state->lines[i]) break; + if (e_next == e) { + /* + * Special case: we might have come all the + * way round a loop and found our way back to + * the same edge we started from. In that + * situation, we must terminate not only this + * while loop, but the 'for' outside it that + * was tracing in both directions from the + * starting edge, because if we let it trace + * in the second direction then we'll only + * find ourself traversing the same loop in + * the other order and generate an encoded + * move string that mentions the same set of + * edges twice. + */ + goto autofollow_done; + } + dot = (e_next->dot1 != dot ? e_next->dot1 : e_next->dot2); if (movelen > movesize - 40) { movesize = movesize * 5 / 4 + 128; @@ -3064,6 +3082,7 @@ static char *interpret_move(const game_state *state, game_ui *ui, (int)(e_this - g->edges), button_char); } } + autofollow_done:; } } -- 2.30.2