Papers › AST Indexing: A Near-Constant Time Solution to the Get-Descendants-by-Type Problem
AST Indexing: A Near-Constant Time Solution to the Get-Descendants-by-Type Problem
Sam Kelly
In this paper we present two novel abstract syntax tree (AST) indexing algorithms that solve the get-descendants-by-type problem in near constant time. This work has been implemented in the U.S. Department of Energy's ROSE compiler framework with plans to be officially integrated as an optimization library called "NodeFinder". ROSE is an open source software analysis platform and source-to-source compiler suited for large-scale C/C++, UPC, Java, Python, Fortran, OpenCL, CUDA, and OpenMP applications that has been actively developed at Lawrence Livermore National Laboratory for the last sixteen years. The get-descendants-by-type problem is the problem of efficiently answering queries of the form “given an arbitrary AST node 𝐴 and an arbitrary node type 𝑇, return all descendants of 𝐴 that are of type 𝑇". Our algorithms are generic in that they can also be applied to any tree that has a meaningful notion of node "type", so we also explore some potential applications in the fields of file systems and databases.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections