mauke

In Glob Matching Can Be Simple And Fast Too Russ Cox benchmarked several glob implementations by matching the string a¹⁰⁰ against the pattern (a*)ⁿb. (Here exponentiation refers to string repetition, as in 'a' x 100 matched against ('a*' x $n) . 'b' in Perl syntax.) What he found was that some implementations returned results instantly whereas others got extremely slow as soon as n grew past 5, taking seconds, minutes and even hours to finish.

This problem is caused by excessive backtracking. It's possible to implement globbing without nested backtracking (and the linked article explains a simple algorithm to do so), but a naive recursive implementation will suffer from this issue. It affects some shells, FTP servers, and programming languages, including Perl: File::Glob uses code from BSD libc (which is affected, unlike glibc). A patch was written and the next File::Glob release will include a fixed algorithm.

But what really caught my eye was the way Python implements glob matching: It translates each glob pattern to a regex, then simply invokes the regex engine. This approach also suffers from exponential backtracking because Python's regex engine uses an exponential-time algorithm. As it turns out I do something very similar in some of my JavaScript code to support user-specified wildcards.

The question is: Does converting the pattern to a regex suffer from the same problem in JavaScript and Perl, and can we avoid excessive backtracking somehow?

At first blush it seems like Perl is not affected:

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}b\z/s'

returns instantly. But this is because a specific regex optimization kicks in: Perl first checks whether the fixed substring 'b' appears in the target string, and because it doesn't, the match fails immediately. We can defeat this optimization by switching to:

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}[bc]\z/s'

or

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}b.*?a\z/s'

(Warning: This takes 1½ minutes to finish on my system; increasing the 6 to 7 or 8 is not recommended.)

So this approach seems vulnerable:

#!/usr/bin/env perl
use strict;
use warnings;

sub glob2re {
    my ($pat) = @_;
    $pat =~ s{(\W)}{
        $1 eq '?' ? '.' :
        $1 eq '*' ? '.*?' :
        '\\' . $1
    }eg;
    return qr/\A$pat\z/s;
}

('a' x 100) =~ glob2re(('a*' x 7) . 'b*a');

The above code indeed takes a long time to finish.

What about JavaScript? Here's the equivalent code:

function glob2re(pat) {
    pat = pat.replace(/\W/g, function (m0) {
        return (
            m0 === '?' ? '[\\s\\S]' :
            m0 === '*' ? '[\\s\\S]*?' :
            '\\' + m0
        );
    });
    return new RegExp('^' + pat + '$');
}

glob2re('a*'.repeat(7) + 'b').test('a'.repeat(100));

(Note the extra suckiness: JavaScript has no /s flag so you need something like [\s\S] to match any character.)

I've only tried this in Firefox but it also takes a long time to finish.

Clearly the naive approach does not work well. Can we fix it?

The algorithm presented by Russ Cox works by limiting the stack of saved backtracking states to at most 1 entry (yeah, that's not much of a "stack" anymore). As soon as a new instance of * starts being processed, all previous backtracking information is forgotten.

In Perl we can get the same effect by using the (*PRUNE) control verb:

#!/usr/bin/env perl
use strict;
use warnings;

sub glob2re {
    my ($pat) = @_;
    $pat =~ s{(\W)}{
        $1 eq '?' ? '.' :
        $1 eq '*' ? '(*PRUNE).*?' :
        '\\' . $1
    }eg;
    return qr/\A$pat\z/s;
}

('a' x 100) =~ glob2re(('a*' x 70) . 'b*a');

With this tiny change (adding (*PRUNE) to the generated regex), even 70 wildcards in a single pattern pose no problem: The program finishes instantly.

Again, what about JavaScript? Here the situation is a bit more complicated because JavaScript doesn't support control verbs. Normally this wouldn't be much of a problem because we could just turn foo*bar*baz into /foo(?>.*?bar)(?>.*?baz)/ instead, using (?>...) (an independent subexpression) to limit backtracking. Unfortunately JavaScript doesn't support (?>...) either. But wait! We can combine capturing groups, positive look-ahead, and backreferences to simulate (?>foo): Just use (?=(foo))\1 instead. Well, what we really want is a backreference to the last thing we captured. Perl again makes this easy with a relative backreference (\g{-1}) but in JavaScript we're forced to use absolute numbering instead. We can still do it because we control the whole regex, we just have to do a bit more manual work:

function glob2re(pat) {
    function tr(pat) {
        return pat.replace(/\W/g, function (m0) {
            return (
                m0 === '?' ? '[\\s\\S]' :
                '\\' + m0
            );
        });
    }

    var n = 1;
    pat = pat.replace(/\W[^*]*/g, function (m0, mp, ms) {
        if (m0.charAt(0) !== '*') {
            return tr(m0);
        }
        var eos = mp + m0.length === ms.length ? '$' : '';
        return '(?=([\\s\\S]*?' + tr(m0.substr(1)) + eos + '))\\' + n++;
    });
    return new RegExp('^' + pat + '$');
}

glob2re('a*'.repeat(70) + 'b').test('a'.repeat(100));

The code is starting to look a bit crazy and the regexes it generates are even worse, but it does work: Even 70 wildcards finish instantly.

Conclusion: Yes, converting glob patterns to efficient regexes is possible. It's even trivial in Perl. In JavaScript we have to jump through some annoying hoops but in the end we still get a regex that does what we want.