chiark / gitweb /
Fix infinite-loop bug in Loopy's autofollow feature.
authorSimon Tatham <anakin@pobox.com>
Fri, 5 May 2017 06:09:22 +0000 (07:09 +0100)
committerSimon Tatham <anakin@pobox.com>
Fri, 5 May 2017 06:09:22 +0000 (07:09 +0100)
commit23a537243b935207ac8a418b9980bacb4e8e6d59
tree8fc242c4746067f1f474be96060e203042664f6d
parent9972f35b27cadd6a49f2ec57f2ec07e4fa373341
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