How to create a refactor tool?

user_257530 0
Viewed 89

I want to learn how to create refactor tools.

As an example: I want to create migration scripts
for when some library removes deprecated function
and we want to transform code to use the newer adequate functionality.

My idea was to use ANTLR to parse the code into AST,
use some pattern matching on this tree to modify contents,
and output the modified contents.

However, from what I read ANTLR isn't preserving formatting in AST tree,
therefore it would be hard to get unbroken content back.

Do you have a solution that would comply with:

  • allows me to modify code with preserving formatting
  • (optionally) allows me to use AST transformations for code transformation
  • (optionally) can transform variety languages like ANTLR

Question is not limited to one particular language,
I'd be happy to heard solutions created for different languages.

abstract-syntax-tree antlr refactoring automation
2 Answers

If you want a

  • general purpose tool to parse source code from arbitrary languages producing ASTs
  • apply procedural or preferably source-to-source pattern-directed rewrite rules to manipulate the ASTs
  • regenerate valid source code retaining formatting and comments

I know of only two systems at present that can do this robustly.

You probably don't want to try building frameworks like this yourself; these tools both have decades of PhD level investment to make them practical.

One issue that occurs repeatedly is the mistake of thinking that having a parser (e.g., ANTLR) solves most of the problem. See my essay on Life After Parsing. A key insight is that you can't transform "just the syntax (ASTs)" without context; you have to take in account the language semantics and whatever framework you choose to use had better help you do semantic analysis to support the rewrite rules.

There are other (general purpose) program transformation systems out there. Many are research. Few have been used to do serious software reengineering in practice. RASCAL has been applied to some quite interesting tasks but not in any commercial context that I know. DMS has been used in production for over 20 years to carry out massive code base changes including refactoring, API revision, and fully automated language migrations.

user_1201630

ANTLR has a TokenStreamRewriterTokenStreamRewriter class that is very good at preserving your source input.

It has very robust capabilities. It allow you to delete, insert or replace text in the input stream. IT actually stores up a series of pending changes, and then applies them when you ask for the modified input stream (even allows for rolling back changes, as well as multiple sets of changes).

A couple of examples from a recent presentation I did that touched on the Rewriter:

   private void plus0(RefactorUtilContext ctx, String pName) {
        for (var match : plus0PatternA.findAll(ctx, ANY_EXPR_XPATH)) {
            var matchCtx = (AddSubExprContext) (match.getTree());
            rewriter.delete(pName, matchCtx.op, matchCtx.rhs.getStop());
        }
        for (var match : plus0PatternB.findAll(ctx, ANY_EXPR_XPATH)) {
            var matchCtx = (AddSubExprContext) (match.getTree());
            rewriter.delete(pName, matchCtx.lhs.getStart(), matchCtx.op);
        }
    }

    private void times1(RefactorUtilContext ctx, String pName) {
        for (var match : times1PatternA.findAll(ctx, ANY_EXPR_XPATH)) {
            var matchCtx = (MulDivExprContext) (match.getTree());
            // rewriter.delete(pName, matchCtx.op, matchCtx.rhs.getStop());
            rewriter.insertBefore(pName, matchCtx.op, "/* ");
            rewriter.insertAfter(pName, matchCtx.rhs.getStart(), " */");
        }
        for (var match : times1PatternB.findAll(ctx, ANY_EXPR_XPATH)) {
            var matchCtx = (MulDivExprContext) (match.getTree());
            // rewriter.delete(pName, matchCtx.lhs.getStart(), matchCtx.op);
            rewriter.insertBefore(pName, matchCtx.lhs.getStart(), "/* ");
            rewriter.insertAfter(pName, matchCtx.op, " */");
        }
    }

TokenStreamRewriter, basically, just stores a set of instruction about how to modify you input stream, so everything about you input stream that you don't modify is, ummmm, unmodified :).

You may also wish to look into the XPath capabilities that ANTLR has. These allow you to find very specific patterns in the parse tree to locate the portions you would like to refactor. As the name suggests, the syntax is very similar to XPath for XML documents, but works on the parse tree instead of an XML DOM.

Note: all of these operate on the parse tree, not an AST (which would necessarily be of your own design, so ANTLR wouldn't know of it's structure. Also, it's in the nature of ASTs to drop irrelevant information (like comments, whitespace, etc.) so they're just not a good starting point for anything where you want to preserve formatting.)

I put together a quite small project for this presentation and it's on GitHub at LittleCalc. The most relevant file is LittleCalcExecutionVisitor.

You can start a REPL and test things out by running LittleCalcRepl.java

user_737640
Related