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

[Manuel Klimek]

On Wed, Dec 12, 2012 at 11:25 AM, Manuel Klimek <klimek at google.com> wrote:

> On Wed, Dec 12, 2012 at 2:19 AM, Jordan Rose <jordan_rose at apple.com>wrote:
>
>> (+Olaf Krzikalla, a known external user of the classic ParentMap)
>>
>> 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 *update* parents, which Olaf
>> uses, and (b) the careful handling of PseudoObjectExprs and
>> OpaqueValueExprs used for proper source locations in the analyzer.
>>
>> I also don't like the idea that building a ParentMap traverses the *
>> entire* 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 *everything* as easily. And if you allow both per-function and
>> global parent maps, you're doing redundant work.
>>
>> 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.
>>
>
> 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.
>
> 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.
>

Ping :) Or should I just come up with a patch so we have something concrete
to look at?

Cheers,
/Manuel


>
> Thanks!
> /Manuel
>
>
>>
>> Jordan
>>
>>
>> On Dec 11, 2012, at 4:29 , Manuel Klimek <klimek at google.com> wrote:
>>
>> 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
>>  _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130102/11568480/attachment.html>