Analysis and transformation with the nuthatch tree-walking library

Abstract

Nuthatch is a system for traversing, collecting information from, and rewriting trees, based on the idea of tree walking. The main application is software analysis and transformation. Nuthatch traversals are non-recursive by default and independent of the concrete tree representation. We provide an extensible library, Nuthatch/J, for doing tree walking in Java, with adapters for interfacing with popular software transformation tools like Stratego/XT and Rascal. Transformations are described as walks that proceed in programmer-defined steps. Each step can perform actions based on observed properties of current node and walk, and affect state associated with the walk and also rewrite the walked tree. A step ends by walking to a different node in the tree, following the tree branches, and the walk ends by returning to the top.