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

[Manuel Klimek]

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

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