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:

doctest/src/Runner/Example.hs

Lines 51 to 55 in 24bb7f5

	chunksMatch zs@(WildCardChunk : xs) (_:ys) =
	let resWithoutWC = xs `chunksMatch` ys in
	let resWithWC = zs `chunksMatch` ys in
	let res = longerMatch resWithoutWC resWithWC in
	prependWildcard res

and

doctest/src/Runner/Example.hs

Lines 69 to 72 in 24bb7f5

	matches zs@(WildCardLine : xs) us@(_ : ys) =
	let matchWithoutWC = xs `matches` us in
	let matchWithWC = zs `matches` ys in
	matchWithoutWC `matchMax` (incLineNo matchWithWC)

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.