<div dir="ltr">On Thu, Apr 18, 2013 at 3:32 PM, Vane, Edwin <span dir="ltr"><<a href="mailto:edwin.vane@intel.com" target="_blank">edwin.vane@intel.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Do you already have a place to insert this sameAs() matcher then? Any changes I make would probably only affect sub-ex ref matchers.</span></p>
</div></div></blockquote><div><br></div><div style>I'm not sure I understand what you mean. (apart from: insert next to equalsNode in ASTMatchers.h :P)</div><div style><br></div><div style>Regarding the name: we can either name overload equalsNode with a string, or call it equalsBoundNode.</div>
<div>†</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Why are declarations more expensive?</span></p></div></blockquote><div><br></div><div style>They just are generally hard to parse in C++ (so much can go wrong), and most of the transitive closure of TUs are declarations...</div>
<div style><br></div><div style>Cheers,</div><div style>/Manuel</div><div>†</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple">
<div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u>†<u></u></span></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Manuel Klimek [mailto:<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>]
<br>
<b>Sent:</b> Thursday, April 18, 2013 9:12 AM</span></p><div><div class="h5"><br>
<b>To:</b> Vane, Edwin<br>
<b>Cc:</b> Daniel Jasper; Alexander Kornienko; Clang Dev List (<a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a>)<br>
<b>Subject:</b> Re: RFC: AST Matcher Sub-expression references implementation straw man<u></u><u></u></div></div><p></p><div><div class="h5">
<p class="MsoNormal"><u></u>†<u></u></p>
<div>
<p class="MsoNormal">On Thu, Apr 18, 2013 at 3:00 PM, Vane, Edwin <<a href="mailto:edwin.vane@intel.com" target="_blank">edwin.vane@intel.com</a>> wrote:<u></u><u></u></p>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">If we donít have to worry about unresolved sub-expression references then the implementation of a
 sub-ex ref matcher is pretty straight-forward. However, the Ďlook up node in the BoundNodesTreeí statement is where all the trickiness is. Using existing machinery to do this could be computationally expensive. Iím going to do a bit of profiling to check this
 out. Iíve seen some mention of profiling stubs in the code already. Are there any tips or best known methods I should be aware of?</span><u></u><u></u></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><u></u>†<u></u></p>
</div>
<div>
<p class="MsoNormal">Not really - once you have something, I'll patch it in and test it over our 100MLOC code base and see how bad it is ;)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Apart from that, just use a sufficiently large TU that takes multiple seconds to parse and run over that... Declarations are where most of the parsing time goes anyway :P...<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">†</span><u></u><u></u></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Manuel Klimek [mailto:<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>]
<br>
<b>Sent:</b> Wednesday, April 17, 2013 3:43 PM<br>
<b>To:</b> Vane, Edwin<br>
<b>Cc:</b> Daniel Jasper; Alexander Kornienko; Clang Dev List (<a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a>)</span><u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><br>
<b>Subject:</b> Re: RFC: AST Matcher Sub-expression references implementation straw man<u></u><u></u></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
<div>
<p class="MsoNormal">On Wed, Apr 17, 2013 at 7:47 PM, Vane, Edwin <<a href="mailto:edwin.vane@intel.com" target="_blank">edwin.vane@intel.com</a>> wrote:<u></u><u></u></p>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">†</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">†</span><u></u><u></u></p>
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Manuel Klimek [mailto:<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>]
<br>
<b>Sent:</b> Wednesday, April 17, 2013 3:45 AM<br>
<b>To:</b> Vane, Edwin; Daniel Jasper; Alexander Kornienko<br>
<b>Cc:</b> Clang Dev List (<a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a>)<br>
<b>Subject:</b> Re: RFC: AST Matcher Sub-expression references implementation straw man</span><u></u><u></u></p>
<p class="MsoNormal">†<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Tue, Apr 16, 2013 at 8:47 PM, Manuel Klimek <<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>> wrote:<u></u><u></u></p>
</div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">+djasper, alexfh<u></u><u></u></p>
<div>
<div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<div>
<p class="MsoNormal">On Tue, Apr 16, 2013 at 7:15 PM, Vane, Edwin <<a href="mailto:edwin.vane@intel.com" target="_blank">edwin.vane@intel.com</a>> wrote:<u></u><u></u></p>
<p class="MsoNormal">Hi all,<br>
<br>
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.<br>
<br>
======<br>
Quick motivation first:<br>
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):<br>
<br>
varDecl(hasType(qualType(...).bind("declType")),<br>
† † † † † † † †hasInitializer(hasType(sameAs("declType")))<u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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 :)<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="color:#1f497d">†</span><u></u><u></u></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">[Edwin]
</span></i></b><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I had thought the type could be inferred from which matcher the sub-ex ref is passed to ŗ la PolymorphicMatchWithParam*. Ambiguities would be solved the same way
 we currently have to resolve ambiguities in the polymorphic matchers; by explicitly inserting a dyncast matcher:</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">hasType(qualType(sameAs(ďblahĒ)))</span><u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">You're right... †<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I have no attachments to the name. Iím open to suggestions.</span><u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Daniel usually has good naming ideas :)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">†</span><u></u><u></u></p>
</div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<p class="MsoNormal">)<br>
<br>
There's potential for other sub-expression reference matchers beyond the "sameAs()" matcher proposed by this example. Name comparisons for example.<br>
======<br>
<br>
Proposed changes to implement sub-expression references:<br>
- In a sub-ex matcher, look-up in the provided BoundNodesTreeBuilder for the given id.<br>
† - If the id exists perform matcher logic, return truth value.<br>
† - If an id doesn't exist, record an unresolved sub-expression reference in the Builder and return true.<br>
† † - 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.<br>
- 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.<u></u><u></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I'm currently opposed to unresolved subexpression matcher handling (but happy to be convinced otherwise).<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Currently, we have:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">a) a defined order of execution<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">b) a well-defined cut-off for logical expressions<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">And on a more principled note:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">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 match?<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal">†<u></u><u></u></p>
<p class="MsoNormal"><b><i><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">[Edwin] The unresolved sub-ex refs were meant to handle what I thought was an un-defined order
 of execution actually. But now that I think about it, the un-defined part is just the order of *creation* of matchers, not the calling of their match() functions. I think youíre right that we could just re-arrange a matcher so the tagging happens before the
 ref. Given that, I donít think unresolved sub-ex refs are necessary. I donít think itís that big of onus on users of AST Matchers to organize their matchers this way.</span></i></b><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">†</span><u></u><u></u></p>
</div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<p class="MsoNormal">Outstanding questions:<br>
- 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.<br>
<br>
--<br>
Edwin Vane<br>
† Software Developer<br>
† Intel of Canada, Inc.<u></u><u></u></p>
</blockquote>
</div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal">†<u></u><u></u></p>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><u></u>†<u></u></p>
</div>
</div>
</div></div></div>
</div>

</blockquote></div><br></div></div>