Add a clang-transformer tutorial

[ymandel]

Summary

This patch adds a tutorial for the ClangTransformer library in libTooling (clang/Tooling/Transformer).

[ymandel]

tweaks

[ymandel]

removed stray internal reference.

[gribozavr2]

clang/docs/ClangTransformerTutorial.rst

53

Please use relative links:

:doc:`LibASTMatchers`

65

Does this link work? Or does it need to use the RST syntax?

70

"an api" -> "a style guide rule"?

95

"renaming a function"

321

Remove "and"?

356

"of a particular"

397

Please use relative links with :doc:.

[ymandel]

Responses to comments

[ymandel]

Thanks for the review!

clang/docs/ClangTransformerTutorial.rst

70

yes. this example came from an API with its own style guide. :)

clang/docs/ClangTransformerTutorial.rst

+==========================
+Clang Transformer Tutorial
+==========================
+
+A tutorial on how to write a source-to-source translation tool using Clang Transformer.
+
+.. contents::
+   :local:
+
+What is Clang Transformer?
+--------------------------
+
+Clang Transformer is a framework for writing C++ diagnostics and program
+transformations. It is built on the clang toolchain and the LibTooling library,
+but aims to hide much of the complexity of clang's native, low-level libraries.
+
+The core abstraction of Transformer is the *rewrite rule*, which specifies how
+to change a given program pattern into a new form. Here are some examples of
+tasks you can achieve with Transformer:
+
+*   warn against using the name ``MkX`` for a declared function,
+*   change ``MkX`` to ``MakeX``, where ``MkX`` is the name of a declared function,
+*   change ``s.size()`` to ``Size(s)``, where ``s`` is a ``string``,
+*   collapse ``e.child().m()`` to ``e.m()``, for any expression ``e`` and method named
+    ``m``.
+
+All of the examples have a common form: they identify a pattern that is the
+target of the transformation, they specify an *edit* to the code identified by
+the pattern, and their pattern and edit refer to common variables, like ``s``,
+``e``, and ``m``, that range over code fragments. Our first and second examples also
+specify constraints on the pattern that aren't apparent from the syntax alone,
+like "``s`` is a ``string``." Even the first example ("warn ...") shares this form,
+even though it doesn't change any of the code -- it's "edit" is simply a no-op.
+
+Transformer helps users succinctly specify rules of this sort and easily execute
+them locally over a collection of files, apply them to selected portions of
+a codebase, or even bundle them as a clang-tidy check for ongoing application.
+
+Who is Clang Transformer for?
+-----------------------------
+
+Clang Transformer is for developers who want to write clang-tidy checks or write
+tools to modify a large number of C++ files in (roughly) the same way. What
+qualifies as "large" really depends on the nature of the change and your
+patience for repetitive editing. In our experience, automated solutions become
+worthwhile somewhere between 100 and 500 files.
+
+Getting Started
+---------------
+
+Patterns in Transformer are expressed with :doc:`clang's AST matchers <LibASTMatchers>`. 
+Matchers are a language of combinators for describing portions of a clang
+Abstract Syntax Tree (AST). Since clang's AST includes complete type information
+(within the limits of single `Translation Unit (TU)`_,
+these patterns can even encode rich constraints on the type properties of AST
+nodes.
+
+.. _`Translation Unit (TU)`: https://en.wikipedia.org/wiki/Translation_unit_\(programming\)
+
+We assume a familiarity with the clang AST and the corresponding AST matchers
+for the purpose of this tutorial. Users who are unfamiliar with either are
+encouraged to start with the recommended references in `Related Reading`_.
+
+Example: style-checking names
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Assume you have a style-guide rule which forbids functions from being named
+"MkX" and you want to write a check that catches any violations of this rule. We
+can express this a Transformer rewrite rule:
+
+.. code-block:: c++
+    
+   makeRule(functionDecl(hasName("MkX").bind("fun"),
+      noopEdit(node("fun")),
+      cat("The name ``MkX`` is not allowed for functions; please rename"));
+
+``makeRule`` is our go-to function for generating rewrite rules. It takes three
+arguments: the pattern, the edit, and (optionally) an explanatory note. In our
+example, the pattern (``functionDecl(...)``) identifies the declaration of the
+function ``MkX``. Since we're just diagnosing the problem, but not suggesting a
+fix, our edit is an no-op. But, it contains an *anchor* for the diagnostic
+message: ``node("fun")`` says to associate the message with the source range of
+the AST node bound to "fun"; in this case, the ill-named function declaration.
+Finally, we use ``cat`` to build a message that explains the change. Regarding the
+name ``cat`` -- we'll discuss it in more detail below, but suffice it to say that
+it can also take multiple arguments and concatenate their results.
+
+Note that the result of ``makeRule`` is a value of type
+``clang::transformer::RewriteRule``, but most users don't need to care about the
+details of this type.
+
+Example: renaming a function
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Now, let's extend this example to a *transformation*; specifically, the second
+example above:
+
+.. code-block:: c++
+    
+   makeRule(declRefExpr(to(functionDecl(hasName("MkX")))),
+      changeTo(cat("MakeX")),
+      cat("MkX has been renamed MakeX"));
+
+In this example, the pattern (``declRefExpr(...)``) identifies any *reference* to
+the function ``MkX``, rather than the declaration itself, as in our previous
+example. Our edit (``changeTo(...)``) says to *change* the code matched by the
+pattern *to* the text "MakeX". Finally, we use ``cat`` again to build a message
+that explains the change.
+
+Here are some example changes that this rule would make:
+
++--------------------------+----------------------------+
+| Original                 | Result                     |
++==========================+============================+
+| ``X x = MkX(3);``        | ``X x = MakeX(3);``        |
++--------------------------+----------------------------+
+| ``CallFactory(MkX, 3);`` | ``CallFactory(MakeX, 3);`` |
++--------------------------+----------------------------+
+| ``auto f = MkX;``        | ``auto f = MakeX;``        |
++--------------------------+----------------------------+
+
+Example: method to function
+^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Next, let's write a rule to replace a method call with a (free) function call,
+applied to the original method call's target object. Specifically, "change
+``s.size()`` to ``Size(s)``, where ``s`` is a ``string``." We start with a simpler
+change that ignores the type of ``s``. That is, it will modify *any* method call
+where the method is named "size":
+
+.. code-block:: c++
+    
+   llvm::StringRef s = "str";
+   makeRule(
+     cxxMemberCallExpr(
+       on(expr().bind(s)),
+       callee(cxxMethodDecl(hasName("size")))),
+     changeTo(cat("Size(", node(s), ")")),
+     cat("Method ``size`` is deprecated in favor of free function ``Size``"));
+
+We express the pattern with the given AST matcher, which binds the method call's
+target to ``s`` [#f1]_. For the edit, we again use ``changeTo``, but this
+time we construct the term from multiple parts, which we compose with ``cat``. The
+second part of our term is ``node(s)``, which selects the source code
+corresponding to the AST node ``s`` that was bound when a match was found in the
+AST for our rule's pattern. ``node(s)`` constructs a ``RangeSelector``, which, when
+used in ``cat``, indicates that the selected source should be inserted in the
+output at that point.
+
+Now, we probably don't want to rewrite *all* invocations of "size" methods, just
+those on ``std::string``\ s. We can achieve this change simply by refining our
+matcher. The rest of the rule remains unchanged:
+
+.. code-block:: c++
+    
+   llvm::StringRef s = "str";
+   makeRule(
+     cxxMemberCallExpr(
+       on(expr(hasType(namedDecl(hasName("std::string"))))
+   .bind(s)),
+       callee(cxxMethodDecl(hasName("size")))),
+     changeTo(cat("Size(", node(s), ")")),
+     cat("Method ``size`` is deprecated in favor of free function ``Size``"));
+
+Example: rewriting method calls
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+In this example, we delete an "intermediary" method call in a string of
+invocations. This scenario can arise, for example, if you want to collapse a
+substructure into its parent.
+
+.. code-block:: c++
+    
+   llvm::StringRef e = "expr", m = "member";
+   auto child_call = cxxMemberCallExpr(on(expr().bind(e)),
+               callee(cxxMethodDecl(hasName("child"))));
+   makeRule(cxxMemberCallExpr(on(child_call), callee(memberExpr().bind(m)),
+      changeTo(cat(e, ".", member(m), "()"))),
+      cat("``child`` accessor is being removed; call ",
+    member(m), " directly on parent"));
+
+This rule isn't quite what we want: it will rewrite ``my_object.child().foo()`` to
+``my_object.foo()``, but it will also rewrite ``my_ptr->child().foo()`` to
+``my_ptr.foo()``, which is not what we intend. We could fix this by restricting
+the pattern with ``not(isArrow())`` in the definition of ``child_call``. Yet, we
+*want* to rewrite calls through pointers.
+
+To capture this idiom, we provide the ``access`` combinator to intelligently
+construct a field/method access. In our example, the member access is expressed
+as:
+
+.. code-block:: c++
+    
+   access(e, cat(member(m)))
+
+The first argument specifies the object being accessed and the second, a
+description of the field/method name. In this case, we specify that the method
+name should be copied from the source -- specifically, the source range of ``m``'s
+member. To construct the method call, we would use this expression in ``cat``:
+
+.. code-block:: c++
+    
+   cat(access(e, cat(member(m))), "()")
+
+Reference: ranges, stencils, edits, rules
+-----------------------------------------
+
+The above examples demonstrate just the basics of rewrite rules. Every element
+we touched on has more available constructors: range selectors, stencils, edits
+and rules. In this section, we'll briefly review each in turn, with references
+to the source headers for up-to-date information. First, though, we clarify what
+rewrite rules are actually rewriting.
+
+Rewriting ASTs to... Text?
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The astute reader may have noticed that we've been somewhat vague in our
+explanation of what the rewrite rules are actually rewriting. We've referred to
+"code", but code can be represented both as raw source text and as an abstract
+syntax tree. So, which one is it?
+
+Ideally, we'd be rewriting the input AST to a new AST, but clang's AST is not
+terribly amenable to this kind of transformation. So, we compromise: we express
+our patterns and the names that they bind in terms of the AST, but our changes
+in terms of source code text. We've designed Transformer's language to bridge
+the gap between the two representations, in an attempt to minimize the user's
+need to reason about source code locations and other, low-level syntactic
+details.
+
+Range Selectors
+^^^^^^^^^^^^^^^
+
+Transformer provides a small API for describing source ranges: the
+``RangeSelector`` combinators. These ranges are most commonly used to specify the
+source code affected by an edit and to extract source code in constructing new
+text.
+
+Roughly, there are two kinds of range combinators: ones that select a source
+range based on the AST, and others that combine existing ranges into new ranges.
+For example, ``node`` selects the range of source spanned by a particular AST
+node, as we've seen, while ``after`` selects the (empty) range located immediately
+after its argument range. So, ``after(node("id"))`` is the empty range immediately
+following the AST node bound to ``id``.
+
+For the full collection of ``RangeSelector``\ s, see the header,
+`clang/Tooling/Transformer/RangeSelector.h <https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Tooling/Transformer/RangeSelector.h>`_
+
+Stencils
+^^^^^^^^
+
+Transformer offers a large and growing collection of combinators for
+constructing output. Above, we demonstrated ``cat``, the core function for
+constructing stencils. It takes a series of arguments, of three possible kinds:
+
+#.  Raw text, to be copied directly to the output.
+#.  Selector: specified with a ``RangeSelector``, indicates a range of source text
+    to copy to the output.
+#.  Builder: an operation that constructs a code snippet from its arguments. For
+    example, the ``access`` function we saw above.
+
+Data of these different types are all represented (generically) by a ``Stencil``.
+``cat`` takes text and ``RangeSelector``\ s directly as arguments, rather than
+requiring that they be constructed with a builder; other builders are
+constructed explicitly.
+
+In general, ``Stencil``\ s produce text from a match result. So, they are not
+limited to generating source code, but can also be used to generate diagnostic
+messages that reference (named) elements of the matched code, like we saw in the
+example of rewriting method calls.
+
+Further details of the ``Stencil`` type are documented in the header file
+`clang/Tooling/Transformer/Stencil.h <https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Tooling/Transformer/Stencil.h>`_.
+
+Edits
+^^^^^
+
+Transformer supports additional forms of edits. First, in a ``changeTo``, we can
+specify the particular portion of code to be replaced, using the same
+``RangeSelector`` we saw earlier. For example, we could change the function name
+in a function declaration with:
+
+.. code-block:: c++
+    
+   makeRule(functionDecl(hasName("bad")).bind(f),
+      changeTo(name(f), cat("good")),
+      cat("bad is now good"));
+
+We also provide simpler editing primitives for insertion and deletion:
+``insertBefore``, ``insertAfter`` and ``remove``. These can all be found in the header
+file
+`clang/Tooling/Transformer/RewriteRule.h <https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Tooling/Transformer/RewriteRule.h>`_.
+
+We are not limited one edit per match found. Some situations require making
+multiple edits for each match. For example, suppose we wanted to swap two
+arguments of a function call.
+
+For this, we provide an overload of ``makeRule`` that takes a list of edits,
+rather than just a single one. Our example might look like:
+
+.. code-block:: c++
+    
+   makeRule(callExpr(...),
+     {changeTo(node(arg0), cat(node(arg2))),
+      changeTo(node(arg2), cat(node(arg0)))},
+     cat("swap the first and third arguments of the call"));
+
+``EditGenerator``\ s (Advanced)
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+The particular edits we've seen so far are all instances of the ``ASTEdit`` class,
+or a list of such. But, not all edits can be expressed as ``ASTEdit``\ s. So, we
+also support a very general signature for edit generators:
+
+.. code-block:: c++
+    
+   using EditGenerator = MatchConsumer<llvm::SmallVector<Edit, 1>>;
+
+That is, an ``EditGenerator`` is function that maps a ``MatchResult`` to a set
+of edits, or fails. This signature supports a very general form of computation
+over match results. Transformer provides a number of functions for working with
+``EditGenerator``\ s, most notably
+`flatten <https://github.com/llvm/llvm-project/blob/1fabe6e51917bcd7a1242294069c682fe6dffa45/clang/include/clang/Tooling/Transformer/RewriteRule.h#L165-L167>`_
+``EditGenerator``\ s, like list flattening. For the full list, see the header file
+`clang/Tooling/Transformer/RewriteRule.h <https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Tooling/Transformer/RewriteRule.h>`_.
+
+Rules
+^^^^^
+
+We can also compose multiple *rules*, rather than just edits within a rule,
+using ``applyFirst``: it composes a list of rules as an ordered choice, where
+Transformer applies the first rule whose pattern matches, ignoring others in the
+list that follow. If the matchers are independent then order doesn't matter. In
+that case, ``applyFirst`` is simply joining the set of rules into one.
+
+The benefit of ``applyFirst`` is that, for some problems, it allows the user to
+more concisely formulate later rules in the list, since their patterns need not
+explicitly exclude the earlier patterns of the list. For example, consider a set
+of rules that rewrite compound statements, where one rule handles the case of an
+empty compound statement and the other handles non-empty compound statements.
+With ``applyFirst``, these rules can be expressed compactly as:
+
+.. code-block:: c++
+    
+   applyFirst({
+     makeRule(compoundStmt(statementCountIs(0)).bind("empty"), ...),
+     makeRule(compoundStmt().bind("non-empty"),...)
+   })
+
+The second rule does not need to explicitly specify that the compound statement
+is non-empty -- it follows from the rules position in ``applyFirst``. For more
+complicated examples, this can lead to substantially more readable code.
+
+Sometimes, a modification to the code might require the inclusion of a
+particular header file. To this end, users can modify rules to specify include
+directives with ``addInclude``.
+
+For additional documentation on these functions, see the header file
+`clang/Tooling/Transformer/RewriteRule.h <https://github.com/llvm/llvm-project/blob/main/clang/include/clang/Tooling/Transformer/RewriteRule.h>`_.
+
+Using a RewriteRule as a clang-tidy check
+-----------------------------------------
+
+Transformer supports executing a rewrite rule as a
+`clang-tidy <https://clang.llvm.org/extra/clang-tidy/>`_ check, with the class
+``clang::tidy::utils::TransformerClangTidyCheck``. It is designed to require
+minimal code in the definition. For example, given a rule
+``MyCheckAsRewriteRule``, one can define a tidy check as follows:
+
+.. code-block:: c++
+
+   class MyCheck : public TransformerClangTidyCheck {
+    public:
+     MyCheck(StringRef Name, ClangTidyContext *Context)
+   : TransformerClangTidyCheck(MyCheckAsRewriteRule, Name, Context) {}
+   };
+
+``TransformerClangTidyCheck`` implements the virtual ``registerMatchers`` and
+``check`` methods based on your rule specification, so you don't need to implement
+them yourself. If the rule needs to be configured based on the language options
+and/or the clang-tidy configuration, it can be expressed as a function taking
+these as parameters and (optionally) returning a ``RewriteRule``. This would be
+useful, for example, for our method-renaming rule, which is parameterized by the
+original name and the target. For details, see
+`clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h <https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clang-tidy/utils/TransformerClangTidyCheck.h>`_
+
+Related Reading
+---------------
+
+A good place to start understanding the clang AST and its matchers is with the
+introductions on clang's site:
+
+*   :doc:`Introduction to the Clang AST <IntroductionToTheClangAST>`
+*   :doc:`Matching the Clang AST <LibASTMatchers>`
+*   `AST Matcher Reference <https://clang.llvm.org/docs/LibASTMatchersReference.html>`_
+
+.. rubric:: Footnotes
+
+.. [#f1] Technically, it binds it to the string "str", to which our
+    variable ``s`` is bound. But, the choice of that id string is
+    irrelevant, so elide the difference.

clang/docs/index.rst

.. toctree::
    ExternalClangExamples
    IntroductionToTheClangAST
    LibTooling
    LibFormat
    ClangPlugins
    RAVFrontendAction
    LibASTMatchersTutorial
    LibASTMatchers
+   ClangTransformerTutorial
    LibASTImporter
    HowToSetupToolingForLLVM
    JSONCompilationDatabase
    RefactoringEngine
 
 Using Clang Tools
 =================