Needlessly exponential pattern-matching

[quasicomputational]

mkResult in Runner.Example is the heart of doctest: it checks the actual output against the expected pattern, which can include wildcards both within a line and across lines.

Here's how wildcard matching is implemented currently:

https://github.com/sol/doctest/blob/24bb7f5fa48d90d73904e8c60f7fe7f5e9cc9cd6/src/Runner/Example.hs#L51-L55

and

https://github.com/sol/doctest/blob/24bb7f5fa48d90d73904e8c60f7fe7f5e9cc9cd6/src/Runner/Example.hs#L69-L72

Note that they'll try both branches in isolation, leading to an exponential running time on pathological input. This has been made slightly worse by #249 wanting to go down both branches to find the best place to show the difference, but it was there before.

In most cases this is pretty un-noticeable to users, who'll tend to use tame patterns, but it's currently biting me in running the test suite where QuickCheck generates some real monsters.

Since the patterns are a regular language, mkResult could be re-implemented to use finite automata instead, which should bring a significant speed-up on pathological input.

[amigalemming]

Can you recommend a Haskell-only regular-expression matching library? I think about implementing your suggestion in doctest-extract.