[cfe-dev] Caching a unified ParentMap in the ASTContext?

[Manuel Klimek]

On Tue, Dec 11, 2012 at 3:09 PM, Vane, Edwin <edwin.vane at intel.com> wrote:

>  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
>

For example Stmt nodes can have parents that are generated during template
specializations...


> 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?
>

Yep, we want to avoid it if possible...

Cheers,
/Manuel


> ****
>
> ** **
>
> *From:* cfe-dev-bounces at cs.uiuc.edu [mailto:cfe-dev-bounces at cs.uiuc.edu] *On
> Behalf Of *Manuel Klimek
> *Sent:* Tuesday, December 11, 2012 7:29 AM
> *To:* clang-dev Developers; Richard Smith
> *Subject:* [cfe-dev] Caching a unified ParentMap in the ASTContext?****
>
> ** **
>
> Hi,****
>
> ** **
>
> after some initial probing on IRC it seems like we might want a unified
> parent map (lazily) cached in the ASTContext.****
>
> ** **
>
> ** Context ******
>
> ** **
>
> 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].****
>
> ** **
>
> 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.****
>
> ** **
>
> 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.****
>
> ** **
>
> 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.****
>
> ** **
>
> 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.****
>
> ** **
>
> ** Proposal ******
>
> ** **
>
> The proposal would be to add methods to the ASTContext that allow querying
> the parents of a node.****
>
> ** **
>
> Knowing that this might not at all be what we want, I'm proposing a
> straw-man:****
>
> ** **
>
> /// \brief Returns an iterator to the parents of the given node.****
>
> ///****
>
> /// Note that this will lazily compute the parents of all nodes****
>
> /// and store them for later retrieval. Thus, the first call is O(n)****
>
> /// in the number of AST nodes.****
>
> ///****
>
> /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc, ****
>
> /// NestedNameSpecifier or NestedNameSpecifierLoc.****
>
> template <typename NodeT>****
>
> ParentIterator ASTContext::parents_begin(const NodeT &Node);****
>
> template <typename NodeT>****
>
> ParentIterator ASTContext::parents_end(const NodeT &Node);****
>
> ** **
>
> 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.****
>
> ** **
>
> 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...****
>
> ** **
>
> Thoughts?****
>
> /Manuel****
>
> ** **
>
> [1]
> http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/ASTMatchers/ASTMatchFinder.cpp?view=markup
> ****
>
> [2]
> http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/AST/ParentMap.h?view=markup
> ****
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20121211/b6e616d7/attachment.html>