How to tell which of two glob patterns is more general

user_1426705 0
Viewed 55

Let's say we have two glob patterns, for example app/src/**/* and app/src/some-dir/**/*.

Both patterns match some path, for example app/src/some-dir/some-other-dir/my-file.txt.

I need to tell, which of this two (or more) patterns is more general. In other words, which of patterns is a subset of another pattern. In example above more general pattern is app/src/**/*, because it matches everything in app/src, and second pattern matches everything in a subdirectory of app/src.

The first thought is to tell, which path prefix is longer (part of pattern before any special symbols like *), but I believe that's not a solution to a problem, since pattern can be more complicated and can include special characters in different places, something like app/*/some-dir/some-other-dir.

Is there any reliable solution for this problem, that does not require actual globbing and counting matched files (since it may be a slow operation) ?

glob path algorithm
1 Answers

The textbook method for this is to convert each glob to a deterministic finite automaton, then construct the product of the automata (implicitly here), and search for a state that is accepting in one but not the other. Depending on how many subset checks you're planning to do and how big the state machines get, it may be worth adding a DFA minimization stage (also covered in your favorite automata theory textbook).

Some rough Python 3:

import re


def glob_tokens_from_glob(g):
    return re.findall(r"\*\*?|[^*]", g)


def is_wild(token):
    return token.startswith("*") or token == "?"


def epsilon_successors(tokens, i):
    yield i
    while i < len(tokens) and tokens[i].startswith("*"):
        i += 1
        yield i


def successors(tokens, i, sym):
    if i >= len(tokens):
        pass
    elif tokens[i] == "**":
        yield i
    elif tokens[i] == "*":
        if sym != "/":
            yield i
    elif tokens[i] == "?":
        if sym != "/":
            yield i + 1
    elif tokens[i] == sym:
        yield i + 1


def successor_dict(tokens, q):
    symbols = {tokens[i] for i in q if i < len(tokens) if not is_wild(tokens[i])}
    symbols.update({"/", "[^/]"})
    return {
        sym: frozenset(
            k
            for i in q
            for j in successors(tokens, i, sym)
            for k in epsilon_successors(tokens, j)
        )
        for sym in symbols
    }


def dfa_from_glob_tokens(tokens):
    q0 = frozenset(epsilon_successors(tokens, 0))
    delta = {frozenset(): {"[^/]": frozenset()}}
    stack = [q0]
    while stack:
        q = stack.pop()
        if q in delta:
            continue
        d = successor_dict(tokens, q)
        stack.extend(d.values())
        delta[q] = d
    return (q0, delta, {q for q in delta.keys() if len(tokens) in q})


def dfa_from_glob(g):
    return dfa_from_glob_tokens(glob_tokens_from_glob(g))


def successor(d, sym):
    if sym in d:
        return d[sym]
    elif sym == "/":
        return frozenset()
    else:
        return d["[^/]"]


def dfa_matches_subset(dfa_a, dfa_b):
    q0_a, delta_a, f_a = dfa_a
    q0_b, delta_b, f_b = dfa_b
    stack = [(q0_a, q0_b)]
    visited = set()
    while stack:
        q = stack.pop()
        if q in visited:
            continue
        visited.add(q)
        q_a, q_b = q
        if q_a in f_a and q_b not in f_b:
            return False
        d_a = delta_a[q_a]
        d_b = delta_b[q_b]
        symbols = set(d_a.keys())
        symbols.update(d_b.keys())
        stack.extend((successor(d_a, sym), successor(d_b, sym)) for sym in symbols)
    return True


def test():
    dfa1 = dfa_from_glob("app/src/**/*")
    dfa2 = dfa_from_glob("app/src/some-dir/**/*")
    dfa3 = dfa_from_glob("app/src/some-dir/some-other-dir/my-file.txt")
    dfa4 = dfa_from_glob("app/*/some-dir/some-other-dir/*")
    dfa5 = dfa_from_glob("*")
    dfa6 = dfa_from_glob("/")
    dfa7 = dfa_from_glob("?")
    dfa8 = dfa_from_glob("b")
    dfa9 = dfa_from_glob("cc")
    dfas = [dfa1, dfa2, dfa3, dfa4, dfa5, dfa6, dfa7, dfa8, dfa9]
    for a in dfas:
        for b in dfas:
            print(int(dfa_matches_subset(a, b)), end=" ")
        print()


test()
user_21446690
Related