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

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

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


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

@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?


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall added a comment.

In D54309#1320628 , @JonasToth wrote:

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


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

new years ping on the crash-issue.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

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


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Manuel Klimek via Phabricator via cfe-commits]

klimek added a comment.

In D54309#1326852 , @JonasToth wrote:

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


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

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


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

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!


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D54309/new/

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
sammccall marked 2 inline comments as done.
Closed by commit rC346847: [AST] Allow limiting the scope of common AST 
traversals (getParents, RAV). (authored by sammccall, committed by ).

Changed prior to commit:
  https://reviews.llvm.org/D54309?vs=174000=174004#toc

Repository:
  rC Clang

https://reviews.llvm.org/D54309

Files:
  include/clang/AST/ASTContext.h
  include/clang/AST/RecursiveASTVisitor.h
  lib/AST/ASTContext.cpp
  lib/ASTMatchers/ASTMatchFinder.cpp
  unittests/AST/ASTContextParentMapTest.cpp
  unittests/Tooling/CMakeLists.txt
  unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp

Index: lib/ASTMatchers/ASTMatchFinder.cpp
===
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -635,10 +635,6 @@
   bool memoizedMatchesAncestorOfRecursively(
   const ast_type_traits::DynTypedNode , const DynTypedMatcher ,
   BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
-if (Node.get() ==
-ActiveASTContext->getTranslationUnitDecl())
-  return false;
-
 // For AST-nodes that don't have an identity, we can't memoize.
 if (!Builder->isComparable())
   return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
@@ -673,7 +669,22 @@
 BoundNodesTreeBuilder *Builder,
 AncestorMatchMode MatchMode) {
 const auto  = ActiveASTContext->getParents(Node);
-assert(!Parents.empty() && "Found node that is not in the parent map.");
+if (Parents.empty()) {
+  // Nodes may have no parents if:
+  //  a) the node is the TranslationUnitDecl
+  //  b) we have a limited traversal scope that excludes the parent edges
+  //  c) there is a bug in the AST, and the node is not reachable
+  // Usually the traversal scope is the whole AST, which precludes b.
+  // Bugs are common enough that it's worthwhile asserting when we can.
+  assert(Node.get() ||
+ /* Traversal scope is limited if none of the bounds are the TU */
+ llvm::none_of(ActiveASTContext->getTraversalScope(),
+   [](Decl *D) {
+ return D->getKind() == Decl::TranslationUnit;
+   }) &&
+ "Found node that is not in the complete parent map!");
+  return false;
+}
 if (Parents.size() == 1) {
   // Only one parent - do recursive memoization.
   const ast_type_traits::DynTypedNode Parent = Parents[0];
@@ -1019,7 +1030,7 @@
   internal::MatchASTVisitor Visitor(, Options);
   Visitor.set_active_ast_context();
   Visitor.onStartOfTranslationUnit();
-  Visitor.TraverseDecl(Context.getTranslationUnitDecl());
+  Visitor.TraverseAST(Context);
   Visitor.onEndOfTranslationUnit();
 }
 
Index: lib/AST/ASTContext.cpp
===
--- lib/AST/ASTContext.cpp
+++ lib/AST/ASTContext.cpp
@@ -796,11 +796,10 @@
   CommentCommandTraits(BumpAlloc, LOpts.CommentOpts),
   CompCategories(this_()), LastSDM(nullptr, 0) {
   TUDecl = TranslationUnitDecl::Create(*this);
+  TraversalScope = {TUDecl};
 }
 
 ASTContext::~ASTContext() {
-  ReleaseParentMapEntries();
-
   // Release the DenseMaps associated with DeclContext objects.
   // FIXME: Is this the ideal solution?
   ReleaseDeclContextMaps();
@@ -838,22 +837,80 @@
 Value.second->~PerModuleInitializers();
 }
 
-void ASTContext::ReleaseParentMapEntries() {
-  if (!PointerParents) return;
-  for (const auto  : *PointerParents) {
-if (Entry.second.is()) {
-  delete Entry.second.get();
-} else if (Entry.second.is()) {
-  delete Entry.second.get();
-}
-  }
-  for (const auto  : *OtherParents) {
-if (Entry.second.is()) {
-  delete Entry.second.get();
-} else if (Entry.second.is()) {
-  delete Entry.second.get();
-}
+class ASTContext::ParentMap {
+  /// Contains parents of a node.
+  using ParentVector = llvm::SmallVector;
+
+  /// Maps from a node to its parents. This is used for nodes that have
+  /// pointer identity only, which are more common and we can save space by
+  /// only storing a unique pointer to them.
+  using ParentMapPointers = llvm::DenseMap<
+  const void *,
+  llvm::PointerUnion4>;
+
+  /// Parent map for nodes without pointer identity. We store a full
+  /// DynTypedNode for all keys.
+  using ParentMapOtherNodes = llvm::DenseMap<
+  ast_type_traits::DynTypedNode,
+  llvm::PointerUnion4>;
+
+  ParentMapPointers PointerParents;
+  ParentMapOtherNodes OtherParents;
+  class ASTVisitor;
+
+  static ast_type_traits::DynTypedNode
+  getSingleDynTypedNodeFromParentMap(ParentMapPointers::mapped_type U) {
+if (const auto *D = U.dyn_cast())
+  return ast_type_traits::DynTypedNode::create(*D);
+if (const auto *S = U.dyn_cast())
+  

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

[Eric Liu via Phabricator via cfe-commits]

ioeric accepted this revision.
ioeric added a comment.
This revision is now accepted and ready to land.

lgtm




Comment at: lib/ASTMatchers/ASTMatchFinder.cpp:674
+  // Nodes may have no parents if:
+  //  a) the node is the TranslationUnitDecl
+  //  a) there is a bug in the AST, and the node is not reachable

nit: a,b,c



Comment at: lib/ASTMatchers/ASTMatchFinder.cpp:680
+  assert(Node.get() ||
+ !llvm::any_of(ActiveASTContext->getTraversalScope(),
+   [](Decl *D) {

`none_of`?


Repository:
  rC Clang

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall updated this revision to Diff 174000.
sammccall marked 2 inline comments as done.
sammccall added a comment.

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


Repository:
  rC Clang

https://reviews.llvm.org/D54309

Files:
  include/clang/AST/ASTContext.h
  include/clang/AST/RecursiveASTVisitor.h
  lib/AST/ASTContext.cpp
  lib/ASTMatchers/ASTMatchFinder.cpp
  unittests/AST/ASTContextParentMapTest.cpp
  unittests/Tooling/CMakeLists.txt
  unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp

Index: unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp
===
--- /dev/null
+++ unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp
@@ -0,0 +1,51 @@
+//===- unittest/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp ---===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "TestVisitor.h"
+
+using namespace clang;
+
+namespace {
+
+class Visitor : public ExpectedLocationVisitor {
+public:
+  Visitor(ASTContext *Context) { this->Context = Context; }
+
+  bool VisitNamedDecl(NamedDecl *D) {
+if (!D->isImplicit())
+  Match(D->getName(), D->getLocation());
+return true;
+  }
+};
+
+TEST(RecursiveASTVisitor, RespectsTraversalScope) {
+  auto AST = tooling::buildASTFromCode(
+  R"cpp(
+struct foo {
+  struct bar {
+struct baz {};
+  };
+};
+  )cpp",
+  "foo.cpp", std::make_shared());
+  auto  = AST->getASTContext();
+  auto  = *Ctx.getTranslationUnitDecl();
+  auto  = *TU.lookup(("foo")).front();
+  auto  = *cast(Foo).lookup(("bar")).front();
+
+  Ctx.setTraversalScope({});
+
+  Visitor V();
+  V.DisallowMatch("foo", 2, 8);
+  V.ExpectMatch("bar", 3, 10);
+  V.ExpectMatch("baz", 4, 12);
+  V.TraverseAST(Ctx);
+}
+
+} // end anonymous namespace
Index: unittests/Tooling/CMakeLists.txt
===
--- unittests/Tooling/CMakeLists.txt
+++ unittests/Tooling/CMakeLists.txt
@@ -40,6 +40,7 @@
   RecursiveASTVisitorTests/NestedNameSpecifiers.cpp
   RecursiveASTVisitorTests/ParenExpr.cpp
   RecursiveASTVisitorTests/TemplateArgumentLocTraverser.cpp
+  RecursiveASTVisitorTests/TraversalScope.cpp
   RecursiveASTVisitorTestDeclVisitor.cpp
   RecursiveASTVisitorTestPostOrderVisitor.cpp
   RecursiveASTVisitorTestTypeLocVisitor.cpp
Index: unittests/AST/ASTContextParentMapTest.cpp
===
--- unittests/AST/ASTContextParentMapTest.cpp
+++ unittests/AST/ASTContextParentMapTest.cpp
@@ -17,6 +17,9 @@
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include "gmock/gmock.h"
+
+using testing::ElementsAre;
 
 namespace clang {
 namespace ast_matchers {
@@ -78,5 +81,30 @@
   hasAncestor(cxxRecordDecl(unless(isTemplateInstantiation(;
 }
 
+TEST(GetParents, RespectsTraversalScope) {
+  auto AST =
+  tooling::buildASTFromCode("struct foo { int bar; };", "foo.cpp",
+std::make_shared());
+  auto  = AST->getASTContext();
+  auto  = *Ctx.getTranslationUnitDecl();
+  auto  = *TU.lookup(("foo")).front();
+  auto  = *cast(Foo).lookup(("bar")).front();
+
+  using ast_type_traits::DynTypedNode;
+  // Initially, scope is the whole TU.
+  EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo)));
+  EXPECT_THAT(Ctx.getParents(Foo), ElementsAre(DynTypedNode::create(TU)));
+
+  // Restrict the scope, now some parents are gone.
+  Ctx.setTraversalScope({});
+  EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo)));
+  EXPECT_THAT(Ctx.getParents(Foo), ElementsAre());
+
+  // Reset the scope, we get back the original results.
+  Ctx.setTraversalScope({});
+  EXPECT_THAT(Ctx.getParents(Bar), ElementsAre(DynTypedNode::create(Foo)));
+  EXPECT_THAT(Ctx.getParents(Foo), ElementsAre(DynTypedNode::create(TU)));
+}
+
 } // end namespace ast_matchers
 } // end namespace clang
Index: lib/ASTMatchers/ASTMatchFinder.cpp
===
--- lib/ASTMatchers/ASTMatchFinder.cpp
+++ lib/ASTMatchers/ASTMatchFinder.cpp
@@ -635,10 +635,6 @@
   bool memoizedMatchesAncestorOfRecursively(
   const ast_type_traits::DynTypedNode , const DynTypedMatcher ,
   BoundNodesTreeBuilder *Builder, AncestorMatchMode MatchMode) {
-if (Node.get() ==
-ActiveASTContext->getTranslationUnitDecl())
-  return false;
-
 // For AST-nodes that don't have an identity, we can't memoize.
 if (!Builder->isComparable())
   return matchesAncestorOfRecursively(Node, Matcher, Builder, MatchMode);
@@ -673,7 +669,21 @@
 BoundNodesTreeBuilder 

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

[Eric Liu via Phabricator via cfe-commits]

ioeric added a subscriber: thakis.
ioeric added a comment.

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




Comment at: lib/AST/ASTContext.cpp:10292
+  if (!Parents)
 // We always need to run over the whole translation unit, as
 // hasAncestor can escape any subtree.

is this comment outdated?



Comment at: lib/ASTMatchers/ASTMatchFinder.cpp:676
 const auto  = ActiveASTContext->getParents(Node);
-assert(!Parents.empty() && "Found node that is not in the parent map.");
 if (Parents.size() == 1) {

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?


Repository:
  rC Clang

https://reviews.llvm.org/D54309



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Sam McCall via Phabricator via cfe-commits]

sammccall created this revision.
sammccall added reviewers: klimek, ioeric.
Herald added subscribers: cfe-commits, mgorny.

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 https://reviews.llvm.org/D54259 and 
https://reviews.llvm.org/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.


Repository:
  rC Clang

https://reviews.llvm.org/D54309

Files:
  include/clang/AST/ASTContext.h
  include/clang/AST/RecursiveASTVisitor.h
  lib/AST/ASTContext.cpp
  lib/ASTMatchers/ASTMatchFinder.cpp
  unittests/AST/ASTContextParentMapTest.cpp
  unittests/Tooling/CMakeLists.txt
  unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp

Index: unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp
===
--- /dev/null
+++ unittests/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp
@@ -0,0 +1,51 @@
+//===- unittest/Tooling/RecursiveASTVisitorTests/TraversalScope.cpp ---===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "TestVisitor.h"
+
+using namespace clang;
+
+namespace {
+
+class Visitor : public ExpectedLocationVisitor {
+public:
+  Visitor(ASTContext *Context) { this->Context = Context; }
+
+  bool VisitNamedDecl(NamedDecl *D) {
+if (!D->isImplicit())
+  Match(D->getName(), D->getLocation());
+return true;
+  }
+};
+
+TEST(RecursiveASTVisitor, RespectsTraversalScope) {
+  auto AST = tooling::buildASTFromCode(
+  R"cpp(
+struct foo {
+  struct bar {
+struct baz {};
+  };
+};
+  )cpp",
+  "foo.cpp", std::make_shared());
+  auto  = AST->getASTContext();
+  auto  = *Ctx.getTranslationUnitDecl();
+  auto  = *TU.lookup(("foo")).front();
+  auto  = *cast(Foo).lookup(("bar")).front();
+
+  Ctx.setTraversalScope({});
+
+  Visitor V();
+  V.DisallowMatch("foo", 2, 8);
+  V.ExpectMatch("bar", 3, 10);
+  V.ExpectMatch("baz", 4, 12);
+  V.TraverseAST(Ctx);
+}
+
+} // end anonymous namespace
Index: unittests/Tooling/CMakeLists.txt
===
--- unittests/Tooling/CMakeLists.txt
+++ unittests/Tooling/CMakeLists.txt
@@ -40,6 +40,7 @@
   RecursiveASTVisitorTests/NestedNameSpecifiers.cpp
   RecursiveASTVisitorTests/ParenExpr.cpp
   RecursiveASTVisitorTests/TemplateArgumentLocTraverser.cpp
+  RecursiveASTVisitorTests/TraversalScope.cpp
   RecursiveASTVisitorTestDeclVisitor.cpp
   RecursiveASTVisitorTestPostOrderVisitor.cpp
   RecursiveASTVisitorTestTypeLocVisitor.cpp
Index: unittests/AST/ASTContextParentMapTest.cpp
===
--- unittests/AST/ASTContextParentMapTest.cpp
+++ unittests/AST/ASTContextParentMapTest.cpp
@@ -17,6 +17,9 @@
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Tooling/Tooling.h"
 #include "gtest/gtest.h"
+#include "gmock/gmock.h"
+
+using testing::ElementsAre;
 
 namespace clang {
 namespace ast_matchers {
@@ -78,5 +81,30 @@
   hasAncestor(cxxRecordDecl(unless(isTemplateInstantiation(;
 }
 
+TEST(GetParents, RespectsTraversalScope) {
+  auto AST =
+  tooling::buildASTFromCode("struct foo { int bar; };", "foo.cpp",
+std::make_shared());
+  auto  = AST->getASTContext();
+  auto  = *Ctx.getTranslationUnitDecl();
+  auto  = *TU.lookup(("foo")).front();
+  auto  = *cast(Foo).lookup(("bar")).front();
+
+  using ast_type_traits::DynTypedNode;
+  // Initially, scope is the whole TU.
+