glob: foo??bar*.gif

Russ Cox, “Glob Matching Can Be Simple And Fast Too” (2017-04-24)
https://research.swtch.com/glob
benchmarks several globbing implementations (shells, FTP servers, programming languages / libraries)
file name: aaaaaa....aaaa (100 × "a")
patterns: b / a*b / a*a*b / … a*a*a*…a*b (N × "a*", "b")
some implementations: runtime grows linearly with number of *s
other implementations: exponential (7 minutes for 8 asterisks)

who's affected?

BSD libc
bash, zsh, tcsh, dash (csh just calls glob() from libc)
Java, Perl, Python, Tcl (PHP just calls glob() from libc)
tnftpd, Pure-FTPd
Not affected: glibc, Rust, Go, Ruby

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length && pat[p] == str[s]) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    return matches_at(str, 0, pat, 0);
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    return matches_at(str, 0, pat, 0);
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    return matches_at(str, 0, pat, 0);
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s <= str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    return matches_at(str, 0, pat, 0);
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s <= str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    return matches_at(str, 0, pat, 0);
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s <= str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

what happen

    for (; s <= str.length; s++) {
        if (matches_at(str, s, pat, p+1)) {
            return true;
        }
    }

matches("aaaaaaaaaa", "a*a*a*a*b")

a*   # loop: s .. str.length / 1 .. 10
  a*   # loop: s .. str.length / 2 .. 10
    a*   # loop: s .. str.length / 3 .. 10
      a*   # loop: s .. str.length / 4 .. 10
        b    # fail: backtrack

backtracking

when faced with a decision, just choose the first alternative
remember the other alternative (push it on a stack)
if your choice leads to a solution, great (throw away the stack)
if not (and the stack is not empty): pop the last entry and use that (revise your last decision and go the other way)

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s <= str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }


            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s <= str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }


            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s < str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
                return matches_at(str, s, pat, p+1);

            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s < str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
                p++;
                next;
            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s < str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
                p++;
                next;
            } else if (s < str.length &&
                       (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s < str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                for (; s < str.length; s++) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                while (s < str.length) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                    s++;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                    s++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                    s++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                    s++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    if (matches_at(str, s, pat, p+1)) {
                        return true;
                    }
                    s++;
                    cont.push([s+1, p]);
                    p++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                    p++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                    p++;
                    next;
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

bool matches_at(string str, int s, string pat, int p) {
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

redundant retries

every * tries to match shorter strings first
when we reach the end of …*…*…* for the first time, all preceding * have consumed as little of the string as possible
after exhausting all possibilities for the last *, there's no point in having the preceding stars try to match more
that just limits our options further (and we've already tried all of them)
💡 solution: throw away all saved continuations when reaching a new *

bool matches(string str, string pat) {
    int s = 0, p = 0;
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                cont.clear();
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    stack cont;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                cont.clear();
                if (s < str.length) {
                    cont.push([s+1, p]);
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (!cont.empty()) {
            [s, p] = cont.pop();
            next;
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    int cont_s = -1, cont_p;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                cont_s = -1;
                if (s < str.length) {
                    [cont_s, cont_p] = [s+1, p];
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (cont_s != -1) {
            [s, p] = [cont_s, cont_p];
            next;
        }
        return false;
    }
    return true;
}

bool matches(string str, string pat) {
    int s = 0, p = 0;
    int cont_s = -1, cont_p;
    while (s < str.length || p < pat.length) {
        if (p < pat.length) {
            if (pat[p] == '*') {
                cont_s = -1;
                if (s < str.length) {
                    [cont_s, cont_p] = [s+1, p];
                }
                p++;
                next;
            }
            if (s < str.length && (pat[p] == '?' || pat[p] == str[s])) {
                s++; p++;
                next;
            }
        }
        if (cont_s != -1) {
            [s, p] = [cont_s, cont_p];
            next;
        }
        return false;
    }
    return true;
}

Python

exponential run time
… but does not use a recursive glob() algorithm
translates glob pattern to regex, then uses normal regex engine
… which does full backtracking, so it's exponential anyway

sub glob2re {
    my ($pat) = @_;

    return qr/\A\Q$pat\E\z/;
}

"aaaaaaaaaa" =~ glob2re("a*a*a*b*");

# same exponential backtracking problems

sub glob2re {
    my ($pat) = @_;
    $pat = quotemeta $pat;
    return qr/\A$pat\z/;
}

"aaaaaaaaaa" =~ glob2re("a*a*a*b*");

# same exponential backtracking problems

sub glob2re {
    my ($pat) = @_;
    $pat =~ s/(\W)/\\$1/g;
    return qr/\A$pat\z/;
}

"aaaaaaaaaa" =~ glob2re("a*a*a*b*");

# same exponential backtracking problems

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

"aaaaaaaaaa" =~ glob2re("a*a*a*b*");

# same exponential backtracking problems

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

"aaaaaaaaaa" =~ glob2re("a*a*a*b*");
# fixed!
# same exponential backtracking problems

Conclusions

Perl and Python both use backtracking in their regex engines
… causing the same performance problem
easy fix in Perl
throw away backtracking stack before entering *
… just like our hand-written version
fix can be emulated on other, less capable regex engines (e.g. JavaScript), but the resulting regexes are horrible: http://blogs.perl.org/users/mauke/2017/05/converting-glob-patterns-to-efficient-regexes-in-perl-and-javascript.html

{END,FIN}{E,} (END|FIN)E?

glob() and exponential backtracking

Lukas Mai

2017-06-27

glob: foo??bar*.gif

who's affected?

why does this happen?

we're done … ?

what happen

backtracking

redundant retries

Thank you!

Python

Conclusions