通过算法将一系列路径名 inclusion/exclusion 规则转换为查找命令？

Question

考虑使用以下元规则解释的任意路径名前缀序列 inclusion/exclusion 规则：

前提条件：与目录相关的规则将遵循与其祖先相关的任何规则
后面的规则覆盖前面的规则，.gitignore 风格

或伪代码：

for each pathname in `find .`

    pathname.excluded = true //or false - two variants of the problem

    for each rule in rules
        if pathname.starts_with(rule)
            pathname.excluded = rule.is_exclusion

    if !pathname.excluded
        output pathname

我正在寻找一种算法，可以将此类规范转换为 find 命令所需的格式，即交替 -prunes 和 -prints。

找到。 stuff -prune -o stuff -print -o ...

这样的查找命令的输出应该与上述伪代码算法的输出设置相同。

这里的困难在于，使用 find 命令一旦目录被修剪，就无法取消修剪，查找甚至不会递归到其中，因此后续 "inclusion rules" 与其后代相关的内容将无效.

Answer 1

创建一个 trie 树，其中每个节点都有一个布尔字段 excluded。对于每个规则，按如下方式将其插入到 trie 中。向下走到它在 trie 中的节点，根据需要创建 excluded 等于默认排除的新节点。在那个节点，删除它的子节点。

trie的意思是，判断一条路径是否被排除，尽可能的按照路径在trie中走，然后return最后一个节点的excluded值达到。

要将 trie 转换为 find 命令，请为其每个节点指定一个规则。外部节点产生前缀匹配。内部节点产生完全匹配。

通过算法将一系列路径名 inclusion/exclusion 规则转换为查找命令？

Algorithmically convert a sequence of pathname inclusion/exclusion rules to a find command?

algorithm

find