How to test that a function doesn't infinite loop

Learn
1

I have a bunch of functions designed for navigating a 2d grid: up, down, rowStart, columnEnd, etc. They all have the signature GridWalker a -> Maybe (GridWalker a). Some of the functions are fairly complex and could descend into an infinite loop if not implemented correctly. So I’d like to write a test that will fuzz both the grid and a list of walking functions to run in order. That way I can test lots of different steps in different orders on different pieces of data. If everything is working correctly every test will terminate. If there’s something wrong, the test will end up in an infinite loop. Here’s what I have so far:

         fuzz
            (Fuzz.map2 Tuple.pair fuzzWalker (Fuzz.list fuzzWalkFunc))
            "no sequence of walking functions produces an infinite loop"
            (\( walker, walkFuncs ) ->
                let
                    _ =
                        GridWalker.walk walkFuncs walker
                in
                Expect.true "Just need to run the function to ensure it doesn't infinite loop" True
            )

This appears to work. However:

  • Is there any guarantee the _ = assignment will actually run? Technically it could be just dropped by the compiler since the output isn’t actually used.
  • When I run elm-review NoUnused.Variables complains that I’m assigning to _ which has no effect.

Is there a better way to do this?

2

You could do this:

         fuzz
            (Fuzz.map2 Tuple.pair fuzzWalker (Fuzz.list fuzzWalkFunc))
            "no sequence of walking functions produces an infinite loop"
            (\( walker, walkFuncs ) ->
                GridWalker.walk walkFuncs walker
                    |> always Expect.pass
            )
1 Like
3

You’re question is actually touching on a very fundamental problem “halting problem”.
However in your case it is possible to help ensure the loop exits eventually. Things like timeouts, Max depth counters and checking for loops in the current planned path come to mind.
Another thing that comes to mind is to try and break down the complexity of the algorithm, so you can test smaller chunks of it ( possibly without the need of the loop/recursive behavior wrapping it)
Just some ideas.

2 Likes
4

thanks my issue has been fixed.

5

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.