一句话：提出仅需词法分析、基于树自动机的序列到树匹配架构，使语法代码搜索可接受尚不可解析的不完整查询。
Semgrep、Comby 等轻量语法分析工具利用代码的树结构，比字符串与正则搜索更具表达力，其查询语言接近源语言本身。但现有匹配技术要求查询必须是完整且可解析的代码片段，导致正在编写中的查询无法使用。本文提出一种新的搜索架构：查询只需经过词法分析（tokenize）而无需解析。在此架构上，作者基于树自动机构造了新的查询语言与匹配算法，以支持树感知的通配符。作者实现了工具 stsearch，并进行了实证评估：stsearch 能支持所有可被词法化的查询，对已有完整查询的结果质量与 Semgrep 相当。该工作表明轻量语法代码搜索可以接受进行中的规格说明，从而有望更好地支持交互式使用场景。
Lightweight syntactic analysis tools like Semgrep and Comby leverage the tree structure of code, making them more expressive than string and regex search. Unlike traditional language frameworks (e.g., ESLint) that analyze codebases via explicit syntax tree manipulations, these tools use query languages that closely resemble the source language. However, state-of-the-art matching techniques for these tools require queries to be complete and parsable snippets, which makes in-progress query specifications useless. We propose a new search architecture that relies only on tokenizing (not parsing) a query. We introduce a novel language and matching algorithm to support tree-aware wildcards on this architecture by building on tree automata. We also present stsearch , a syntactic search tool leveraging our approach. In contrast to past work, our approach supports syntactic search even for previously unparsable queries. We show empirically that stsea rch can support all tokenizable queries, while still providing results comparable to Semgrep for existing queries. Our work offers evidence that lightweight syntactic code search can accept in-progress specifications, potentially improving support for interactive settings. CCS Concepts: • Software and its engineering → Formal language definitions ; Software maintenance tools; • Information systems → Query representation; • Theory of computation → Tree languages.
@article{MatuteNBCC24,
title = {Syntactic Code Search with Sequence-to-Tree Matching: Supporting Syntactic Search with Incomplete Code Fragments},
author = {Gabriel Matute and Wode Ni and Titus Barik and Alvin Cheung and Sarah E. Chasins},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656460}
}