[cfe-dev] RFC: AST Matcher Sub-expression references implementation straw man

Manuel Klimek klimek at google.com
Wed Apr 17 00:44:43 PDT 2013

On Tue, Apr 16, 2013 at 8:47 PM, Manuel Klimek <klimek at google.com> wrote:

> +djasper, alexfh
> On Tue, Apr 16, 2013 at 7:15 PM, Vane, Edwin <edwin.vane at intel.com> wrote:
>> Hi all,
>> I've been looking at implementing sub-expression references in AST
>> Matchers. I'd like to propose an implementation and get feedback,
>> especially if I've overlooked something.
>> ======
>> Quick motivation first:
>> The goal of sub-expression references is to write matchers that can refer
>> to nodes tagged by the matcher and use these nodes in more tests. Consider
>> the following simple example that wants to find variable declarations whose
>> type exactly matches the initializer type (for simplicity, lets ignore all
>> the implicit cast stuff that will exist around the initializer):
>> varDecl(hasType(qualType(...).bind("declType")),
>>                hasInitializer(hasType(sameAs("declType")))
Minor point: I'd guess we'll need to specify the type here explicitly, like
sameAs<QualType>("declType"). Also, I'm not very happy with the color of
the bike shed called "sameAs" yet :)

>> There's potential for other sub-expression reference matchers beyond the
>> "sameAs()" matcher proposed by this example. Name comparisons for example.
>> ======
>> Proposed changes to implement sub-expression references:
>> - In a sub-ex matcher, look-up in the provided BoundNodesTreeBuilder for
>> the given id.
>>   - If the id exists perform matcher logic, return truth value.
>>   - If an id doesn't exist, record an unresolved sub-expression reference
>> in the Builder and return true.
>>     - Info recorded: id we're looking for and some sort of matcher
>> "future": a callback or functor for executing matcher logic at a later time
>> along with all necessary data matcher needs.
>> - When control returns to the top level finder logic
>> (MatchASTVisitor::match()) we tend to unresolved sub-ex refs. For each
>> recorded unresolved sub-ex ref, do a search through the BoundNodesTree for
>> a matching id. If one is found, execute matcher future. If the future
>> returns false, the match fails and the Callback that would normally get
>> called will not be. If no id is found, match also fails. If the matcher
>> future returns true, proceed to calling Callback for the match. The
>> handling of unresolved sub-ex refs could be handled by modifying
>> MatchVisitor.
I'm currently opposed to unresolved subexpression matcher handling (but
happy to be convinced otherwise).
Currently, we have:
a) a defined order of execution
b) a well-defined cut-off for logical expressions

That is, if you say anyOf(a(), b()), b() will not be matched if a()
matches. Now a() could contain a sub-expression matcher referring to
something that might be bound in b(); how would you propose to solve this?

And on a more principled note:
Which things can we solve with unresolved subexpression matchers that
cannot also be solved by re-arranging the matcher so that the bind() to the
id must always happen before the sameAs match, otherwise sameAs will not

> Outstanding questions:
>> - Where should unresolved sub-ex refs be stored? Top-most level of the
>> BoundNodesTree or just in the level at which the ref happens. Does it
>> matter? Sub-ex refs should be able to refer to nodes anywhere else in the
>> matcher and not have specific scope. Even if refs are stored at the current
>> level, they should be collected and handled all at once when matching is
>> complete.
>> --
>> Edwin Vane
>>   Software Developer
>>   Intel of Canada, Inc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130417/ff73b5c6/attachment.html>

More information about the cfe-dev mailing list