Large character classes combined with {m,n} is very slow and memory-hungry

[jaspervdj]

module Main where
import qualified Text.Regex.TDFA as Tdfa

main :: IO ()
main = do
    let pattern = "^[\x0020-\xD7FF]{1,255}$"
        input   = take 100 $ cycle "abcd"

        regex :: Tdfa.Regex
        regex = Tdfa.makeRegexOpts Tdfa.defaultCompOpt Tdfa.defaultExecOpt pattern

        matches :: [Tdfa.MatchArray]
        matches = Tdfa.match regex input

    print matches

This takes over 6 seconds on my machine and claims around 3GB(!) in memory. Removing the {m,n} part and using "^[\x0020-\xD7FF]+$" combined with an explicit length check (in Haskell) is a workaround.

[neongreen]

😔

I don't have time for maintaining this library, but patches are welcome.

[ChrisKuklewicz]

The version of regex-tdfa in haskell is quite naive about X{n,m} and expands this to fill m copies of X in the desugared AST and in the finite-automata-thing. There is an almost finished OCaml variant that I have where it does NOT duplicate the X in the AST and does not build a finite-automata-thing. If I were time rich then I could finish this in OCaml and port it to a better regex-tdfa. Alas, I do not think I have that much time,

…

On Sat, Mar 10, 2018 at 2:15 PM, Artyom Kazak ***@***.***> wrote: 😔 I don't have time for maintaining this library, but patches are welcome. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#14 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABXVB_Stsg2PiG01PAvODiNQ7J2iIe9dks5tc9__gaJpZM4QnPL_> .

[neongreen]

Moving over to haskell-hvr/regex-tdfa#3.