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

[Vane, Edwin]

Could we still piggy-back the matching process if we provided a flag to the constructor of MatchFinder? Then we'd incur storage only when we wanted and save that extra O(N) overhead.

From: Manuel Klimek [mailto:klimek at google.com]
Sent: Tuesday, December 11, 2012 9:17 AM
To: Vane, Edwin
Cc: clang-dev Developers
Subject: Re: [cfe-dev] Caching a unified ParentMap in the ASTContext?

On Tue, Dec 11, 2012 at 3:09 PM, Vane, Edwin <edwin.vane at intel.com<mailto: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> [mailto: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/9ab7e99d/attachment.html>