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.

diff --git a/loopy.c b/loopy.c
index 652b9ecc091d7bc26f8a9dddcf7a53a18e43ca3d..7d3436aacbc5862ab2d657f93c4b0c828143e4f6 100644 (file)
--- 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:;
         }
     }