<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 style>Knowing that this might not at all be what we want, I'm proposing a straw-man:<br>
</div><div style><br></div><div style>/// \brief Returns an iterator to the parents of the given node.</div><div style>///</div><div style>/// Note that this will lazily compute the parents of all nodes</div><div style>/// and store them for later retrieval. Thus, the first call is O(n)</div>
<div style>/// in the number of AST nodes.</div><div style>///</div><div style>/// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, </div><div style>/// NestedNameSpecifier or NestedNameSpecifierLoc.</div><div style>
template <typename NodeT></div><div style>ParentIterator ASTContext::parents_begin(const NodeT &Node);</div><div style><div>template <typename NodeT></div><div>ParentIterator ASTContext::parents_end(const NodeT &Node);</div>
<div><br></div></div><div style>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 style>
<br></div><div style>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 style><br></div><div style>Thoughts?</div>
<div style>/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">http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ParentMap.h?view=markup</a></div></div></div>