bug: adding shellstyle patterns can burn time and memory

[timbray]

If you add a sequence of random shellstyle patterns Quamina quickly starts generating huge automata and AddPattern starts slowing down dramatically to the point where it's basically unusable.

My test words that produced this effect: "aahed*", "aalii", "aargh", "aarti*", "abaca", "abaci", "aback", "abacs", "abaft", "abaka", "abamp", "aband", "abase", "abash", "abask", "abate", "abaya", "abbas", "abbed*", "ab*bes"

[embano1]

Sounds like a good candidate to add some Fuzz testing with timeout detection to Quamina at some point? https://go.dev/doc/fuzz/

[timbray]

Yes on fuzzing. Ouch, this one is really beating me up, we may end up running into a fundamental computer-science issue here and just say that combining a lot of wildcards makes AddPattern() expensive in both time and memory. But haven't given up yet.

[embano1]

Fair enough Tim, there‘s always a cost and at least if users are aware of penalties, IMHO that‘s fine for now.