<div style="font-family: arial, helvetica, sans-serif; font-size: 10pt"><div dir="ltr">On Tue, Dec 11, 2012 at 3:09 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">I’m still pretty new to this and haven’t plumbed the depths of the matcher internals yet but how can an AST node have multiple parents? Also, when matching
 is </span></p></div></div></blockquote><div><br></div><div style>For example Stmt nodes can have parents that are generated during template specializations...</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">underway and the AST is being recursively visited couldn’t we piggy-back this process to get the parent map for free or is storage of such a map something we want to avoid if possible?</span></p>
</div></div></blockquote><div><br></div><div style>Yep, we want to avoid it if possible...</div><div style><br></div><div style>Cheers,</div><div style>/Manuel</div><div style> </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""> <a href="mailto:cfe-dev-bounces@cs.uiuc.edu" target="_blank">cfe-dev-bounces@cs.uiuc.edu</a> [mailto:<a href="mailto:cfe-dev-bounces@cs.uiuc.edu" target="_blank">cfe-dev-bounces@cs.uiuc.edu</a>]
<b>On Behalf Of </b>Manuel Klimek<br>
<b>Sent:</b> Tuesday, December 11, 2012 7:29 AM<br>
<b>To:</b> clang-dev Developers; Richard Smith<br>
<b>Subject:</b> [cfe-dev] Caching a unified ParentMap in the ASTContext?<u></u><u></u></span></p><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">Hi,<u></u><u></u></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">after some initial probing on IRC it seems like we might want a unified parent map (lazily) cached in the ASTContext.<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">** Context **<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">For the ASTMatchers we have come up with a 2nd implementation of a ParentMap in clang [1], which has slightly different requirements from the first one [2].<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">The lifetime of the ASTMatcher's map is currently bound to the lifetime of the MatchFinder - the map is lazily created, if we have any matchers that need it, and re-used for
 all subsequent matches.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">Recently we added support to match on arbitrary nodes, which has led to a pattern where one uses the ASTMatchers to find nodes to refactor, and then uses the match-on-node
 functionality to figure out what's going on around that node.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">The problem is that currently we don't have a way to re-use the ParentMap that was already built between those calls, leading to an N^2 algorithm in the number of AST nodes.<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">When thinking about where this information would fit best, we thought it's strongly coupled to the ASTContext, so before running off and creating an ASTMatchContext that contains
 an ASTContext and a ParentMap, I thought I'd through out the idea of using a unified ParentMap in the ASTContext.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">** Proposal **<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">The proposal would be to add methods to the ASTContext that allow querying the parents of a node.<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">Knowing that this might not at all be what we want, I'm proposing a straw-man:<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// \brief Returns an iterator to the parents of the given node.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">///<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// Note that this will lazily compute the parents of all nodes<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// and store them for later retrieval. Thus, the first call is O(n)<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// in the number of AST nodes.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">///<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, <u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/// NestedNameSpecifier or NestedNameSpecifierLoc.<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">template <typename NodeT><u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">ParentIterator ASTContext::parents_begin(const NodeT &Node);<u></u><u></u></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">template <typename NodeT><u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">ParentIterator ASTContext::parents_end(const NodeT &Node);<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">An alternative would be to use DynTypedNode in the interface instead of templating the method and hiding it, but I'm not sure how much exposure to that we want in general.<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">I'm also fine with putting up a solution just for the matchers, but wanted to make sure to pursue a more generally useful solution if there's interest...<u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">Thoughts?<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">/Manuel<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif""><u></u> <u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">[1] <a href="http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp?view=markup" target="_blank">http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp?view=markup</a><u></u><u></u></span></p>

</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif"">[2] <a href="http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ParentMap.h?view=markup" target="_blank">http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ParentMap.h?view=markup</a><u></u><u></u></span></p>

</div>
</div>
</div>
</div></div></div>
</div>

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