4 ms·

Just a heads up that this implementation has exponential time complexity on pathological patterns. Demo: https://tio.run/##tVddc6IwFH3nV0Q7WyXFIlrdUWr7uC/9B213

• ball_of_lint 4y ago
  That might help, but I think it goes in the wrong direction - The proper way to implement a regex matcher if you are worried about performance against arbitrary patterns is to build a Finite State Machine. It's not as simple of code and involves knowing some computer science theory, but results in a matcher with better time complexity guarantees.
  • ridiculous_fish 4y ago
    Finite state machines also have their cliffs, in particular bounded repetition. Rust's FA-based regex will explode with /.{12345}/, while v8's backtracking engine handles it no problem.
    • burntsushi 4y ago
      Yes, but please be careful here. The cliffs are categorically different. The cliffs of a finite state machine are still bounded to O(m * n), where m ~ len(regex) and n ~ len(haystack). The cliffs of a backtracker are exponential and difficult to predict. The repetition operator provokes the cliff because it represents short-hand syntax for easily increasing `m` to very large sizes. Indeed, by default, '.{12345}' will fail to compile because it blows the default limit. That only works because, as I said, the cliffs for finite automata based regex engines are far more predictable.
  • hddqsb 4y ago
    [Note: This comment tree is about the Redis code, which uses glob-style patterns rather than regex. So in this comment and in my grandparent comment, "*" means "any string" rather than "zero or more of the previous pattern".] An NFA / DFA would be a perfectly valid way to implement an efficient matcher, but it's not the only way. For example, memoization (https://news.ycombinator.com/item?id=32434412#32436442 https://news.ycombinator.com/item?id=32434412#32436442) can be easily shown to have time complexity O(P * T) where P = len(pattern) and T = len(text), which is the same as a basic NFA implementation. In the case of the Redis code, my proposed fix requires much less code and memory than memoization or an NFA, and has time complexity O(P * T). It's slightly harder to prove this bound; here is a sketch of the proof: Matching against a pattern fragment that does not contain "*" takes O(len(pattern_fragment)). When a call to stringmatchlen() encounters a wildcard, it may recurse O(T) times (and then it returns). Each recursive call can be classified either "leaf" (if there is a match failure before the next wildcard) or "full" (if the match reaches the next wildcard). The insight I described leads to at most one "full" call at each level of the recursion (i.e. for each wildcard in the pattern). So for a particular pattern fragment, the number of "leaf" calls that process it is O(T). Hence the overall time complexity is O(P * T).