Syntactic Code Search with Sequence-to-Tree Matching: Supporting Syntactic Search with Incomplete Code Fragments

• Published in: Proceedings of ACM on programming languages 2024-06, Vol.8 (PLDI), p.2051-2072, Article 230
• Main Authors: Matute, Gabriel, Ni, Wode, Barik, Titus, Cheung, Alvin, Chasins, Sarah E.
• Format: Article
• Language: English
• Subjects: Formal language definitions; Information systems; Query representation; Software and its engineering; Software maintenance tools; Theory of computation; Tree languages
• ISSN: 2475-1421; 2475-1421
• DOI: 10.1145/3656460

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 stsearch 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.