This is an archive of the discontinued LLVM Phabricator instance.

[AST] Allow limiting the scope of common AST traversals (getParents, RAV).
ClosedPublic

Authored by sammccall on Nov 9 2018, 6:45 AM.

Details

Summary

The goal is to allow analyses such as clang-tidy checks to run on a
subset of the AST, e.g. "only on main-file decls" for interactive tools.

Today, these become "problematically global" by running RecursiveASTVisitors
rooted at the TUDecl, or by navigating up via ASTContext::getParent().

The scope is restricted using a set of top-level-decls that RecursiveASTVisitors
should be rooted at. This also applies to the visitor that populates the
parent map, and so the top-level-decls are considered to have no parents.

This patch makes the traversal scope a mutable property of ASTContext.
The more obvious way to do this is to pass the top-level decls to
relevant functions directly, but this has some problems:

  • it's error-prone: accidentally mixing restricted and unrestricted scopes is a performance trap. Interleaving multiple analyses is common (many clang-tidy checks run matchers or RAVs from matcher callbacks)
  • it doesn't map well to the actual use cases, where we really do want *all* traversals to be restricted.
  • it involves a lot of plumbing in parts of the code that don't care about traversals.

This approach was tried out in D54259 and D54261, I wanted to like it
but it feels pretty awful in practice.

Caveats: to get scope-limiting behavior of RecursiveASTVisitors, callers
have to call the new TraverseAST(Ctx) function instead of TraverseDecl(TU).
I think this is an improvement to the API regardless.

Diff Detail

Repository
rC Clang

Event Timeline

sammccall created this revision.Nov 9 2018, 6:45 AM
MTC added a subscriber: MTC.Nov 11 2018, 6:12 PM
ioeric added a subscriber: thakis.Nov 12 2018, 8:47 AM

The new API and the refactoring look good to me. Just a nit and a question.

lib/AST/ASTContext.cpp
10291–10292

is this comment outdated?

lib/ASTMatchers/ASTMatchFinder.cpp
676

A quick search for "Found node that is not in the parent map." in my fav. search engine found a few prior discussions about this. E.g. @klimek seemed to want to remove the assertion (http://clang-developers.42468.n3.nabble.com/Question-about-failed-assertion-ASTMatchFinder-cc-quot-Found-node-that-is-not-in-the-parent-map-quot-td4038612.html), while @thakis seemed to favor keeping the assertion (https://bugs.chromium.org/p/chromium/issues/detail?id=580749).

Maybe we could still assertion if the scope if TU?

sammccall updated this revision to Diff 174000.Nov 14 2018, 1:44 AM
sammccall marked 2 inline comments as done.

Address review comments.
Remove special case for TUDecl since no-parents is now handled.

ioeric accepted this revision.Nov 14 2018, 1:52 AM

lgtm

lib/ASTMatchers/ASTMatchFinder.cpp
674

nit: a,b,c

680

none_of?

This revision is now accepted and ready to land.Nov 14 2018, 1:52 AM
This revision was automatically updated to reflect the committed changes.
sammccall marked 2 inline comments as done.

Hi Sam,

this patch "broke" ExprMutAnalyzer, at least it creates an assertion failure that seems harmless. Your thought on it would be great!

The assertion in: ASTMatchFinder.cpp +680 is triggered in the Analysis to figure out if something is mutated, because Parents is empty and the traversal scope is the TU itself, but the node is a CXXConstructoDecl. This does not happen for alle cases though, please take a look at this reproducer: https://godbolt.org/z/0yOq2I

Only for the Lambda-Case problems occur. If I #if 0 the assertion out the issue goes away, and the real world code that triggered this behaviour is not bothered, too.

I am really puzzled why this issue occurs, but as you implemented the restrictions it would like to hear your opinion on the issue. If you want to reproduce yourself I am of course happy to help, but
https://github.com/JonasToth/clang/blob/fix_crash/unittests/Analysis/ExprMutationAnalyzerTest.cpp#L1134 is probably the easiest way to do so (just add this to trunk and run check-clang-unit).

Thank you for the time!

See PR39949 as well, as it seems to trigger the same or a similar problem.
@ioeric and @klimek maybe could give an opinion, too?

See PR39949 as well, as it seems to trigger the same or a similar problem.
@ioeric and @klimek maybe could give an opinion, too?

Sounds like we might not correctly set the parent map for CXXConstructorDecl then?

Sounds like we might not correctly set the parent map for CXXConstructorDecl then?

I unfortunatly don't know where to start to look for. Could you give me a hint what to inspect to figure that out?

new years ping on the crash-issue.

this patch "broke" ExprMutAnalyzer, at least it creates an assertion failure that seems harmless. Your thought on it would be great!

As mentioned on the bug, this assertion already existed and this patch tries to preserve it in as many cases as possible.
You may be uncovering some unrelated bug (the kind the assertion was meant to catch). Does the assertion go away by reverting this patch (and keeping the old version of the assert)?

I've tried to check myself, but I can't use either of your reproducers. I'll try the one from the bug next (https://bugs.llvm.org/show_bug.cgi?id=39949)

The assertion in: ASTMatchFinder.cpp +680 is triggered in the Analysis to figure out if something is mutated, because Parents is empty and the traversal scope is the TU itself, but the node is a CXXConstructoDecl. This does not happen for alle cases though, please take a look at this reproducer: https://godbolt.org/z/0yOq2I

Only for the Lambda-Case problems occur. If I #if 0 the assertion out the issue goes away, and the real world code that triggered this behaviour is not bothered, too.

Oops, took me a while to realize this is a test for a check that hasn't landed :-)
The fact that this only triggers for a lambda case does suggest to me it's unrelated to this patch - those are exactly the sort of cases where apparently AST traversal has been incomplete in the past, yielding a partial parent map. My understanding is this tends to be harmless where it actually fires, but points to an AST inconsistency that is likely to cause problems in other cases. Thus there's pushback against removing the assertion (which I initially attempted to do).

I am really puzzled why this issue occurs, but as you implemented the restrictions it would like to hear your opinion on the issue. If you want to reproduce yourself I am of course happy to help, but
https://github.com/JonasToth/clang/blob/fix_crash/unittests/Analysis/ExprMutationAnalyzerTest.cpp#L1134 is probably the easiest way to do so (just add this to trunk and run check-clang-unit).

Is this still current? The code fails to parse (on 1137 a&& should be T&&). When I fix that the Results11 = match(withEnclosingCompound(...)) yields an empty vector. (The test does subsequently crash, but not in an interesting way).

@JonasToth As noted on https://bugs.llvm.org/show_bug.cgi?id=39949, this assertion is a pre-existing problem with the parent map + lambdas, unrelated to this patch.

I've analyzed where it comes from (details in the bug) but don't know what the right fix should be. @klimek, can you take a look at the bug?

@sammccall Thank you for analyzing and investigation! Keeping the assertion is of course good and I am not sure on how to proceed.

Given the close branch for 8.0 we might opt for an hotfix that resolves the issue for now.
I think the bug-report is the better place to continue working on it.