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

[Jordan Rose]

On Jan 4, 2013, at 2:04 , Manuel Klimek <klimek at google.com> wrote:

> On Thu, Jan 3, 2013 at 6:06 PM, Ted Kremenek <kremenek at apple.com> wrote:
> On Jan 3, 2013, at 7:37 AM, Manuel Klimek <klimek at google.com> wrote:
> 
>> On Wed, Jan 2, 2013 at 8:08 PM, Ted Kremenek <kremenek at apple.com> wrote:
>> On Jan 2, 2013, at 9:58 AM, Jordan Rose <jordan_rose at apple.com> wrote:
>> 
>>> I'm not so worried about the cost of building the map; the analyzer run tends to dwarf any linear-time operations anyway. I just don't want to build it for the entire translation unit, since we won't use most of it and we're already caching the per-function ones. I don't think that's a design issue, though.
>>> 
>> 
>> 
>> Agreed.  It would be great if a "generic" parent map would just build the parts of the map on demand as necessary.  Then all clients could benefit from the optimization of only paying for what you use.
>> 
>> The basic problem I see here is a trade-off in "saved time" when only a subset is needed vs. how often we need to run over the whole AST:
>> - as far as I can tell, we need to run over *all* of the AST at least once at the moment at which we need the first parent (or am I missing something?) - we can most certainly only *store* parts of it, but we at least need to iterate over everything
>> - every time we run into an access that needs parent information we did not store, we'll need to re-run over everything (right?)
>> 
>> One way I see to mitigate the problem would be the following: have getParent() on the ASTContext take a node and a "AncestorHint" node, which basically tells getParent(), that AncestorHint *should usually* be enough to figure out the request - in the context of the static analyzer that might be the current FunctionDecl (we could also use that to speed up lots of our refactoring cases actually).
>> 
>> If the parent cannot be found within the AncestorHint, the whole AST would be visited (or we assert unless the AncestorHint is NULL or something similar).
>> 
>> Thoughts?
>> /Manuel
>>  
> 
> Hi Manuel,
> 
> The AncestorHint approach sounds reasonable to me.  It would capture the workflow of currently clients of ParentMap like the static analyzer fairly well.  Usually we know what function or method we are looking at, and that can bound the scope of the AST walk.
> 
> Hi Ted,
> 
> one more thing, I'm curious what the exact requirements for the static analyzer are here:
> A node can have multiple parents - for example, if I have a template function and an instantiation of that template function, some of the statements in the function will be reachable both via the template declaration and the instantiation - both are important contexts of the statement. Does this matter for the static analyzer? Or is the static analyzer only interested in the non-instantiation parts of the AST?
> 
> One problem I currently have is that I don't know enough about which nodes get reused during template instantiation, so I'm not sure yet in whether there might be simple solutions to figure out how to resolve those issues...

Interesting. The analyzer core uses the parent of an expression to tell if/how the value of the expression is going to be used; for that I suppose we'd actually want the instantiation. The diagnostics use the parents to determine where to attach notes (and arrows for Xcode); in that case we're mostly interested in the source locations, which should be the same for both.

I would guess we don't handle recursive templates very well if any of the leaf nodes are reused; the behavior of ParentMap in that case is always to prefer the last visit!

But we're not doing anything special to deal with instantiations vs. non-instantiations, so I doubt we'd regress much here whatever you end up doing.

Jordan

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20130104/bf192e06/attachment.html>