<div style="font-family: arial, helvetica, sans-serif; font-size: 10pt"><div dir="ltr"><div class="gmail_default" style>On Wed, Jan 2, 2013 at 8:08 PM, Ted Kremenek <span dir="ltr"><<a href="mailto:kremenek@apple.com" target="_blank">kremenek@apple.com</a>></span> wrote:<br>
</div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div class="im"><div><div>On Jan 2, 2013, at 9:58 AM, Jordan Rose <<a href="mailto:jordan_rose@apple.com" target="_blank">jordan_rose@apple.com</a>> wrote:</div>
<br><blockquote type="cite"><div style="font-family:Helvetica;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
I'm not so worried about the cost of <i>building</i> 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.</div>
<br></blockquote></div><div><br></div></div><div>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.</div>
</div></blockquote><div><br></div><div style>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:</div><div style>- 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</div>
<div style>- every time we run into an access that needs parent information we did not store, we'll need to re-run over everything (right?)</div><div style><br></div><div style>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).</div>
<div style><br></div><div style>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).</div><div style><br></div><div style>
Thoughts?</div><div style>/Manuel</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div>A reasonable approach to stage things would be to first move the current ParentMap to libStaticAnalyzerCore, and have the analyzer use that.  Manuel can then feel free to design a more generic data structure, and we can then evaluate whether or not to switch the analyzer over to using that.</div>
</div></blockquote></div><br></div></div></div>