Как определить, какой из двух шаблонов глобусов более общий

Question

Допустим, у нас есть два шаблона глобуса, например app/src/**/* и app/src/some-dir/**/*.

Оба шаблона соответствуют некоторому пути, например app/src/some-dir/some-other-dir/my-file.txt.

Я должен сказать, какой из этих двух (или более) шаблонов больше общий . Другими словами, какой из шаблонов является подмножеством другого шаблона. В приведенном выше примере более общим шаблоном является app/src/**/*, потому что он соответствует всему в app/src, а второй шаблон соответствует всему в подкаталоге app/src.

Первая мысль - указать, какой префикс пути длиннее (часть шаблона перед любыми специальными символами, такими как *), но я считаю, что это не решение проблемы, поскольку шаблон может быть более сложным и может включать специальные символы в разных местах, например app/*/some-dir/some-other-dir.

Есть ли какое-нибудь надежное решение этой проблемы, которое не требует фактического подстановки и подсчета совпадающих файлов (поскольку это может быть медленной операцией)?

Answer 1

Учебный метод для этого состоит в том, чтобы преобразовать каждый глобус в детерминированный c конечный автомат, затем построить продукт автоматов (здесь неявно) и найти состояние, которое принимается в одном, но не в другом. В зависимости от того, сколько подмножеств проверок вы планируете выполнить и насколько велики конечные автоматы, возможно, стоит добавить этап минимизации DFA (также описанный в вашем любимом учебнике теории автоматов).

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()