如何区分两个glob模式中的哪一个更为普遍

Question

假设我们有两个glob模式，例如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。

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

Answer 1

这方面的教科书方法是将每个glob转换为确定性有限自动机，然后构造自动机的乘积(此处隐含(，并搜索一个在其中接受但在另一个中不接受的状态。根据您计划进行的子集检查数量和状态机的大小，可能值得添加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()