<div style="font-family: arial, helvetica, sans-serif; font-size: 10pt"><div dir="ltr">Hello all,<div><br></div><div style>We have been working on a layer on top of the AST Matcher library to support creating arbitrary matchers at runtime.</div>
<div style>I have a proof of concept working on the tooling branch and wanted to send a proposal to make it a real thing.</div><div style>The proposal doc is on google docs at:</div><div style><a href="https://docs.google.com/a/google.com/document/d/1sUSlxwJsTdU39n1uapTGz7Xl3vejC1aZtri2IXHkNws/edit" class="cremed">https://docs.google.com/a/google.com/document/d/1sUSlxwJsTdU39n1uapTGz7Xl3vejC1aZtri2IXHkNws/edit</a><br>
</div><div style><br></div><div style>Inlined copy below for those that prefer it this way. Feel free to comment on either.</div><div style>_Sam</div><div style><b id="internal-source-marker_0.7362583263311535" style="color:rgb(0,0,0);font-family:'Times New Roman';font-size:medium;font-weight:normal"><h1 dir="ltr">
<span style="font-size:24px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Design: Dynamic AST Matchers</span></h1><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">This document contains a design proposal for a dynamic AST matcher layer that supports creating arbitrary matchers at runtime, which will allow for generic tools to be developed.</span><br>
<h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Context</span></h2><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">The existing AST matcher framework provides a very powerful and compact way to traverse the AST and find specific nodes by providing complex predicates.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">However, this framework requires that all predicates to be used at runtime are fully defined at compile time. The creation of these predicates can be a big challenge in some cases, and this limitation forces a ‘recompile’ step on this creative loop.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"></span><br><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Also, without being able to specify matchers at runtime we can’t support more generic search use cases. For example, an editor-based search tool that supports an AST matcher predicates.</span><br>
<h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Goals</span></h2><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline">
<span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Runtime parsing of matcher expressions, including literals and predicates. Feedback for syntax/semantic errors in the expressions</span></li>
</ul><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Create matchers at runtime by name, with dynamically created arguments if required by the matcher</span></li>
<li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline"><span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Query command line tool that runs the matcher on a specific compilation unit and reports all matches</span></li>
</ul><h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Non-goals</span></h2><ul style="margin-top:0pt;margin-bottom:0pt"><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline">
<span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Dynamic refactoring tools. They might be implemented using dynamic matchers, but it is out of the scope for this library</span></li><li dir="ltr" style="list-style-type:disc;font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline">
<span style="background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Full C++ expression support for predicates. Values are going to be limited to literals (eg. 1, “foo”). Expressions like 1+2 will not be parsed. Some useful constants (like INT_MAX) might be available</span></li>
</ul><h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Code location</span></h2><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">The main output of the project will be a library to be used by AST matcher related clang-tools, and should live close to the already existing AST matcher library, but as a separate library</span><br>
<h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Matcher implementation</span></h2><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">One aspect that simplifies the implementation of dynamic matchers is to have a uniform generic signature for creating them. Otherwise, whatever code that creates them will require explicit knowledge of each matcher, or at least of each signature.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">The generic signature is of the form </span><span style="font-size:12px;font-family:'Courier New';background-color:transparent;vertical-align:baseline;white-space:pre-wrap">VariantType (*)(const std::vector<VariantType>& args)</span><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">. A variant type instance can contain numbers, booleans, strings and Matchers, as well as error related information for return values.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Instead of reimplementing all matchers to have a generic signature, we implement marshaller functions that provide the generic signature on top of the regular static one. The marshallers verify that the argument count and types are correct and calls the underlying constructor function.</span><br>
<h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Registry</span></h2><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">At initialization of the framework, all known matchers are added into a registry. This registry provides a way to create matchers at runtime by name.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">This registry is the only component that would require maintenance when the ASTMatcher library is updated. Any new matcher, and new overloads for existing matchers, would have to be added to the registry. In most cases, a single line of code per matcher does the job.</span><br>
<h2 dir="ltr"><span style="font-size:19px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Matcher expression parsing</span></h2><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">A simple matcher expression parser, combined with the matcher registry, allows clients to go from a user provided string to a </span><span style="font-size:15px;font-family:'Courier New';background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Matcher<T></span><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">. The output of the parser is a variant type also, which allows it to return Matchers as well as syntax and semantic errors.</span><br>
<span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap">The parser interface provides a way for the client to inject and/or modify the matcher tree as it is being created. For example, a client could insert </span><span style="font-size:15px;font-family:'Courier New';background-color:transparent;vertical-align:baseline;white-space:pre-wrap">Id()</span><span style="font-size:15px;font-family:Arial;background-color:transparent;vertical-align:baseline;white-space:pre-wrap"> matcher around specific nodes without having to do it in the string form.</span></b><br>
</div></div></div>