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

[Ted Kremenek]

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.

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