快速准确的C/C++语法搜索

传统在源代码中搜索模式的方法通常使用正则表达式，或者使用自定义解析器解析代码，但这两种方法都存在局限性。在实习期间，我开发了一个名为Syntex的内部工具原型，该工具通过搜索Clang AST来避免这些限制。本文将讨论Syntex在语法模式匹配方面的独特方法。

带上下文的搜索

Syntex解决了传统模式搜索工具的两个主要问题。

首先，现有工具容易产生假阴性结果。这些工具通常包含自己的解析器，根据搜索的代码库语言使用不同的解析器。对于C和C++代码库，这些工具通常在未进行宏扩展的情况下解析源代码，搜索的是未经宏扩展的代码，而不是像Clang这样的真实编译器产生的宏扩展后代码。这意味着这些工具无法确保结果的准确性。

其次，这些工具的内部解析器不使用与真实编译器相同的代码表示方式，也不理解源代码的语义。也就是说，这些工具产生纯文本输出突出显示结果，因此无法提供关于结果出现位置的代码语义信息。

Syntex通过操作实际的Clang AST解决了这两个问题。因为Syntex使用与编译器相同的AST，它消除了典型模式搜索工具的不准确性，并为进一步分析提供了语义信息。

解析C和C++代码是一项 notoriously困难的任务，需要实现无限制的前瞻和执行图灵完备的模板才能获得解析树。Syntex通过依赖Clang解决了解析源代码的问题，但它如何解析Syntex查询本身呢？

除了包含以$为前缀的元变量的查询外，Syntex查询在语法上是有效的C和C++代码。Syntex不直接解决C和C++语法的边缘情况，而是在解析查询时考虑所有可能的模糊解释。

在代码构建和索引时，Syntex通过递归遍历Clang AST并记录AST节点之间的关系来创建上下文无关文法。具有子节点的节点对应非终结符；每个这样的节点出现都会添加一个形式为parent -> child_0 … child_n的产生式规则。

在概念上，解析查询的第一步是执行词法分析。Syntex使用手写状态机进行词法分析。Syntex的词法分析器与典型编译器使用的词法分析器的一个不同之处在于，它返回输入字符的所有可能解释，而不仅仅是最贪婪的解释。

Syntex使用记忆化图表解析器根据合成模式语法解析查询。记忆化防止解析过程导致（可能）指数级的时间复杂度，结果记忆表作为查询解析森林的内存表示。

在查询解析表填充完毕后，Syntex需要在索引的源代码中定位查询所有解释的出现位置。这个过程从表中索引0处开始，其下一个索引是输入长度的条目；这些条目对应于覆盖整个输入字符串的解析。

Syntex的匹配算法操作专有的Clang AST序列化格式。序列化的AST被反序列化为内存中的树。反序列化过程构建了树节点类型（对应文法符号）到反序列化节点的索引，这使得Syntex能够快速发现可能与查询的根文法符号匹配的候选者。

Syntex的一个重要特性是支持查询中的"元变量"。例如，当指定"++i"这样的查询时，匹配器只会找到名为i的变量的递增表达式。但是，如果我们指定"++$“作为查询，Syntex将找到递增任何内容的表达式。

另一个重要特性是通配符操作符”$…"。它允许用户指定诸如"printf($…)“之类的查询。当想要匹配未知数量的节点时，通配符操作符非常有用。

Syntex的方法在传统语法模式搜索工具中是独特的：搜索引擎包含很少的语言特定代码，并且很容易推广到其他编程语言。使用Syntex的唯一要求是它需要能够访问产生每个AST节点的标记。

Syntex已经超越了开源和/或公开可用替代品（如Semgrep和weggli）的能力。Syntex的下一步发展是使其能够搜索不完全存在的源代码文本。C++语言最强大的功能之一是其模板：它们允许程序员描述通用数据结构的形状以及涉及它们的计算。