[ASTImporter] make sure that ACtx::getParents still works

[r.stahl]

Summary

If an AST node is imported after a call to getParents in the ToCtx, it was no longer possible to retrieve its parents since the old results were cached.

Valid types for getParents:

• Decl, Stmt, NestedNameSpecifier: handled explicitly
• Type: not supported by ast importer
• TypeLoc: not imported
• NestedNameSpecifierLoc: calls import for NNS

[a.sidorin]

Hello Rafael,

The patch is awesome. The only thing I'm uncomfortable with is that we call invalidation on every stmt import - not only during the top-level one. Fixing this requires separating entry point from internal imports and is out of scope of this patch, but adding some FIXMEs is very appreciated.

lib/AST/ASTImporter.cpp

6757

We already do the invalidation in Import(Stmt), so it looks redundant here.

[r.stahl]

lib/AST/ASTImporter.cpp

6757

Yes, sorry this should actually be in Import(Decl) as I wrote in the description!

[r.stahl]

addressed review comments

[martong]

lib/AST/ASTImporter.cpp

6776

Can an Expr has a parent too? If yes, why not invalidate the parents in Import(Expr*) ?
I am also a bit concerned to call the invalidation during the import of all Stmt (and possible during the import of Exprs too).
Isn't it enough to invalidate only during Import(Decl*)?

[r.stahl]

lib/AST/ASTImporter.cpp

6776

The Import(Expr) function just defers to Import(Stmt) so a call there would be redundant as Alexey commented.

I don't think it would be enough to invalidate in Import(Decl), because Import(Stmt) is part of the public API. I don't know if it makes sense to just import Stmts and if there is any user code doing that, but it is theoretically possible. In that case we should make Import(Stmt) and Import(Expr) private.

I wouldn't be too concerned about too many calls to invalidate, since the function doesn't do anything once the parent info has been released and it will only be rebuilt once someone calls ACtx::getParents - which is not the case while importing.

[martong]

Ok, thanks for the explanation. Now it looks good to me.

[a.sidorin]

LGTM. Aaron, could you please confirm that AST changes are fine?

include/clang/AST/ASTContext.h

638

I'd prefer to call reset(), but I won't insist on it.

[aaron.ballman]

Adding Richard as he has more background in this area. In general, I think it's okay - if we invalidate too often, we do lose some performance, but the correctness should still be there. I'll let Richard provide the final sign-off, however.

[r.stahl]

@rsmith do you have a chance to take a look or assign someone else?

[rsmith]

This is not specific to the ASTImporter; any change to the AST after a call to getParents could at least potentially have similar problems. Generally, responsibility for dealing with this must lie with the consumer of the parent map, not with the ASTContext, since the ASTContext generally doesn't even know when the AST gets mutated.

I think that the parent map should not be a member of the ASTContext at all. That'd make it much clearer that the responsibility for not reusing it across AST mutations lies with the consumer, not with the mutator of the AST. (Also, having it in ASTContext invites bugs; we do not want the parent map to ever be used by anything in Sema, for instance, largely due to the invalidation problems. In fact, I don't think the clang binary needs the parent map code at all; it really belongs in libTooling.)

[r.stahl]

@rsmith Yes, this should generally better be handled outside of the ASTContext. That would be out of scope of this patch. Is it fine to proceed with this one for now?

For my usage scenario it actually is convenient this way. In my checker I use getParents, but if I would replace this with some tooling functions I wouldn't know when the maps become invalid since the invalidation happens on a lower level within the analyzer. I'd have to search the parents on every callback invocation which would be a massive performance issue.

Once an external parent utility exists, we would still need some invalidation notification. If anyone uses the analyzer and parent maps he'd want to know when they become invalid for performance reasons. Ideally only when necessary like the invalidateParents calls in this patch.

[a_sidorin]

Hello Richard,

Thank you for clarification. However, I think that moving ParentMap into libTooling is out of scope for this patch. Are you OK if this change will be committed with adding a TODO or FIXME for this move?

[r.stahl]

ASTContext::getParents should not be used this way. This use-case is solved by function-scoped ParentMaps or AnalysisDeclContext::getParentMap. Discussion: http://lists.llvm.org/pipermail/cfe-dev/2019-April/061944.html

include/clang/AST/ASTContext.h

public:
   /// 'NodeT' can be one of Decl, Stmt, Type, TypeLoc,
   /// NestedNameSpecifier or NestedNameSpecifierLoc.
   template <typename NodeT> DynTypedNodeList getParents(const NodeT &Node) {
     return getParents(ast_type_traits::DynTypedNode::create(Node));
   }
 
   DynTypedNodeList getParents(const ast_type_traits::DynTypedNode &Node);
 
+  void invalidateParents() {
+    ReleaseParentMapEntries();
+    PointerParents = nullptr;
+  }
+
   const clang::PrintingPolicy &getPrintingPolicy() const {
     return PrintingPolicy;
   }
 
   void setPrintingPolicy(const clang::PrintingPolicy &Policy) {
     PrintingPolicy = Policy;
   }
 

lib/AST/ASTImporter.cpp

if (Pos != ImportedDecls.end()) {
     return ToD;
   }
   
   // Import the type
   Decl *ToD = Importer.Visit(FromD);
   if (!ToD)
     return nullptr;
 
+  ToContext.invalidateParents();
+
   // Record the imported declaration.
   ImportedDecls[FromD] = ToD;
   ToD->IdentifierNamespace = FromD->IdentifierNamespace;
   return ToD;
 }
 
 DeclContext *ASTImporter::ImportContext(DeclContext *FromDC) {
   if (!FromDC)
DeclContext *ASTImporter::ImportContext(DeclContext *FromDC) {
   return ToDC;
 }
 
 Expr *ASTImporter::Import(Expr *FromE) {
   if (!FromE)
     return nullptr;
 
   return cast_or_null<Expr>(Import(cast<Stmt>(FromE)));
 }
 
 Stmt *ASTImporter::Import(Stmt *FromS) {
   if (!FromS)
     return nullptr;
 
   // Check whether we've already imported this declaration.  
   llvm::DenseMap<Stmt *, Stmt *>::iterator Pos = ImportedStmts.find(FromS);
   if (Pos != ImportedStmts.end())
     return Pos->second;
-  
   // Import the type
   ASTNodeImporter Importer(*this);
   Stmt *ToS = Importer.Visit(FromS);
   if (!ToS)
     return nullptr;
 
+  // FIXME: We could add a separate function that assumes parents have already
+  // been invalidated to avoid repeatedly calling this.
+  ToContext.invalidateParents();
+
   // Record the imported declaration.
   ImportedStmts[FromS] = ToS;
   return ToS;
 }
 
 NestedNameSpecifier *ASTImporter::Import(NestedNameSpecifier *FromNNS) {
   if (!FromNNS)
     return nullptr;
 
   NestedNameSpecifier *prefix = Import(FromNNS->getPrefix());
+  NestedNameSpecifier *ToNNS = nullptr;
 
   switch (FromNNS->getKind()) {
   case NestedNameSpecifier::Identifier:
     if (IdentifierInfo *II = Import(FromNNS->getAsIdentifier())) {
-      return NestedNameSpecifier::Create(ToContext, prefix, II);
+      ToNNS = NestedNameSpecifier::Create(ToContext, prefix, II);
     }
-    return nullptr;
+    break;
 
   case NestedNameSpecifier::Namespace:
     if (auto *NS = 
             cast_or_null<NamespaceDecl>(Import(FromNNS->getAsNamespace()))) {
-      return NestedNameSpecifier::Create(ToContext, prefix, NS);
+      ToNNS = NestedNameSpecifier::Create(ToContext, prefix, NS);
     }
-    return nullptr;
+    break;
 
   case NestedNameSpecifier::NamespaceAlias:
     if (auto *NSAD = 
           cast_or_null<NamespaceAliasDecl>(Import(FromNNS->getAsNamespaceAlias()))) {
-      return NestedNameSpecifier::Create(ToContext, prefix, NSAD);
+      ToNNS = NestedNameSpecifier::Create(ToContext, prefix, NSAD);
     }
-    return nullptr;
+    break;
 
   case NestedNameSpecifier::Global:
-    return NestedNameSpecifier::GlobalSpecifier(ToContext);
+    ToNNS = NestedNameSpecifier::GlobalSpecifier(ToContext);
+    break;
 
   case NestedNameSpecifier::Super:
     if (auto *RD =
             cast_or_null<CXXRecordDecl>(Import(FromNNS->getAsRecordDecl()))) {
-      return NestedNameSpecifier::SuperSpecifier(ToContext, RD);
+      ToNNS = NestedNameSpecifier::SuperSpecifier(ToContext, RD);
     }
-    return nullptr;
+    break;
 
   case NestedNameSpecifier::TypeSpec:
   case NestedNameSpecifier::TypeSpecWithTemplate: {
       QualType T = Import(QualType(FromNNS->getAsType(), 0u));
       if (!T.isNull()) {
         bool bTemplate = FromNNS->getKind() == 
                          NestedNameSpecifier::TypeSpecWithTemplate;
-        return NestedNameSpecifier::Create(ToContext, prefix, 
+        ToNNS = NestedNameSpecifier::Create(ToContext, prefix, 
                                            bTemplate, T.getTypePtr());
       }
-    }
-      return nullptr;
+      break;
     }
 
+  default:
     llvm_unreachable("Invalid nested name specifier kind");
   }
 
+  if (ToNNS)
+    ToContext.invalidateParents();
+
+  return ToNNS;
+}
+
 NestedNameSpecifierLoc ASTImporter::Import(NestedNameSpecifierLoc FromNNS) {
   // Copied from NestedNameSpecifier mostly.
   SmallVector<NestedNameSpecifierLoc , 8> NestedNames;
   NestedNameSpecifierLoc NNS = FromNNS;
 
   // Push each of the nested-name-specifiers's onto a stack for
   // serialization in reverse order.
   while (NNS) {

unittests/AST/ASTImporterTest.cpp

auto Pattern = translationUnitDecl(has(classTemplateDecl(
       hasName("Base"),
       has(classTemplateSpecializationDecl(has(fieldDecl(hasName("a"))))))));
   ASSERT_TRUE(
       MatchVerifier<Decl>{}.match(From->getTranslationUnitDecl(), Pattern));
   EXPECT_TRUE(
       MatchVerifier<Decl>{}.match(To->getTranslationUnitDecl(), Pattern));
 }
 
+TEST_P(ASTImporterTestBase, ValidParents) {
+  // Create parent cache in To context.
+  Decl *PreTU = getTuDecl("struct S {};", Lang_CXX, "pre.cc");
+  RecordDecl *FromRD = FirstDeclMatcher<RecordDecl>().match(PreTU, recordDecl());
+  auto ToRD = cast<RecordDecl>(Import(FromRD, Lang_CXX));
+  auto &ToACtx = ToAST->getASTContext();
+  ToACtx.getParents(*ToRD);
+
+  Decl *FromTU = getTuDecl("void f() {}", Lang_CXX);
+  CompoundStmt *FromCS = FirstDeclMatcher<CompoundStmt>().match(FromTU,
+                                                                compoundStmt());
+  FunctionDecl *FromFD = FirstDeclMatcher<FunctionDecl>().match(FromTU,
+                                                                functionDecl());
+
+  auto FromPs = FromFD->getASTContext().getParents(*FromCS);
+  ASSERT_TRUE(!FromPs.empty());
+  auto FromP = FromPs[0].get<FunctionDecl>();
+  EXPECT_EQ(FromP, FromFD);
+
+  auto ToFD = cast<FunctionDecl>(Import(FromFD, Lang_CXX));
+
+  Decl *ToTU = ToACtx.getTranslationUnitDecl();
+  auto ToCS = FirstDeclMatcher<CompoundStmt>().match(ToTU, compoundStmt());
+
+  auto ToPs = ToACtx.getParents(*ToCS);
+  ASSERT_TRUE(!ToPs.empty());
+  auto ToP = ToPs[0].get<FunctionDecl>();
+  EXPECT_EQ(ToP, ToFD);
+}
+
 INSTANTIATE_TEST_CASE_P(
     ParameterizedTests, ASTImporterTestBase,
     ::testing::Values(ArgVector(), ArgVector{"-fdelayed-template-parsing"}),);
 
 struct ImportFunctions : ASTImporterTestBase {};
 
 TEST_P(ImportFunctions,
        PrototypeShouldBeImportedAsAPrototypeWhenThereIsNoDefinition) {