<div style="font-family: arial, helvetica, sans-serif; font-size: 10pt"><div dir="ltr"><div class="gmail_default" style>On Wed, Dec 12, 2012 at 11:25 AM, Manuel Klimek <span dir="ltr"><<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>></span> wrote:<br>
</div><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 style="font-family:arial,helvetica,sans-serif;font-size:10pt">
<div dir="ltr"><div class="im">On Wed, Dec 12, 2012 at 2:19 AM, Jordan Rose <span dir="ltr"><<a href="mailto:jordan_rose@apple.com" target="_blank">jordan_rose@apple.com</a>></span> wrote:<br>
</div><div class="gmail_extra"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div>(+Olaf Krzikalla, a known external user of the classic ParentMap)</div>
<div><br></div><div>The analyzer seems to be the primary user of the "classic" ParentMap; it's also scattered over the rewriters, but I'm not sure it's ever actually used there. All of the uses of our ParentMap seem like they could easily be implemented on top of ASTMatcher's DenseMap implementation, though I'm a little concerned about (a) the ability to <i>update</i> parents, which Olaf uses, and (b) the careful handling of PseudoObjectExprs and OpaqueValueExprs used for proper source locations in the analyzer.</div>
<div><br></div><div>I also don't like the idea that building a ParentMap traverses the <i>entire</i> AST. That includes everything pulled in in every header file, when usually the analyzer only needs to deal with a single function at a time. I'm not sure what to say about this, though; making ParentMaps specific to Decls seems problematic in a different way: you can't match across <i>everything</i> as easily. And if you allow both per-function and global parent maps, you're doing redundant work.</div>
<div><br></div><div>Hm. I'm not sure what I think yet, but I'm leaning towards using your lazily constructed global map on ASTContext and yet still keeping the per-function maps on AnalysisDeclContext. Unifying the two types is fine, though.</div>
</div></blockquote><div><br></div></div><div>One thing I'm concerned about is how performance critical the parent map for the analyzer is - we'll need to expand ours to work for at least all types of nodes that have pointer identity (including TypeLoc and NestedNameSpecifierLoc, as those are crucial for refactorings), while the analyzer (currently) seems to only need statements.</div>
<div><br></div><div>Before trying to come up with a patch I'd be interested whether you expect the analyzer to need parents for different node types anyway, and whether you think the additional performance hit of building a more generic parent map would be prohibitive.</div>
</div></div></div></div></blockquote><div><br></div><div style>Ping :) Or should I just come up with a patch so we have something concrete to look at?</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 style="font-family:arial,helvetica,sans-serif;font-size:10pt"><div dir="ltr"><div class="gmail_extra">
<div class="gmail_quote">
<div><br></div><div>Thanks!</div><span class="HOEnZb"><font color="#888888"><div>/Manuel</div></font></span><div><div class="h5"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">
<div><br></div><div>Jordan</div><div><br></div><div><br></div><div><div><div><div>On Dec 11, 2012, at 4:29 , Manuel Klimek <<a href="mailto:klimek@google.com" target="_blank">klimek@google.com</a>> wrote:</div>
<br></div></div><blockquote type="cite"><div><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt"><div dir="ltr">Hi,<div><br></div><div>after some initial probing on IRC it seems like we might want a unified parent map (lazily) cached in the ASTContext.</div>
<div><br></div><div>** Context **</div><div><br></div>
<div>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].</div><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div><div>
<br></div><div>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.</div>
<div><br></div><div>** Proposal **</div><div><br></div><div>The proposal would be to add methods to the ASTContext that allow querying the parents of a node.</div><div><br></div><div>Knowing that this might not at all be what we want, I'm proposing a straw-man:<br>
</div><div><br></div><div>/// \brief Returns an iterator to the parents of the given node.</div><div>///</div><div>/// Note that this will lazily compute the parents of all nodes</div><div>/// and store them for later retrieval. Thus, the first call is O(n)</div>
<div>/// in the number of AST nodes.</div><div>///</div><div>/// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, </div><div>/// NestedNameSpecifier or NestedNameSpecifierLoc.</div><div>
template <typename NodeT></div><div>ParentIterator ASTContext::parents_begin(const NodeT &Node);</div><div><div>template <typename NodeT></div><div>ParentIterator ASTContext::parents_end(const NodeT &Node);</div>
<div><br></div></div><div>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.</div><div>
<br></div><div>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...</div><div><br></div><div>Thoughts?</div>
<div>/Manuel</div><div><br></div><div>[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></div>
<div>[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></div>
</div></div></div></div>
_______________________________________________<br>cfe-dev mailing list<br><a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
</blockquote></div><br></div></blockquote></div></div></div><br></div></div></div>
</blockquote></div><br></div></div></div>