algorithm - 如何判断两个 glob 模式中哪一个更通用

Question

假设我们有两个 glob 模式，例如 app/src/**/* 和 app/src/some-dir/**/*。

两种模式都匹配某个路径，例如 app/src/some-dir/some-other-dir/my-file.txt。

我需要告诉大家，这两种(或更多)模式中哪一种更通用。换句话说，哪个模式是另一个模式的子集。在上面的示例中，更通用的模式是 app/src/**/*，因为它匹配 app/src 中的所有内容，第二个模式匹配 子目录中的所有内容>应用程序/src。

第一个想法是告诉哪个路径前缀更长(模式的一部分在任何特殊符号如 * 之前)，但我相信这不是问题的解决方案，因为模式可以更多复杂，并且可以在不同位置包含特殊字符，例如 app/*/some-dir/some-other-dir。

对于这个问题有没有可靠的解决方案，不需要实际的通配符和计数匹配的文件(因为它可能是一个缓慢的操作)？

Answer 1

教科书上的方法是将每个球体转换为确定性有限自动机，然后构造自动机的乘积(此处隐式)，并搜索在一个球体中接受但在另一个球体中不接受的状态。根据您计划执行的子集检查数量以及状态机的大小，可能值得添加 DFA 最小化阶段(您最喜欢的自动机理论教科书中也有介绍)。

一些粗略的 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()