[ASTImporter] Support CXXDeductionGuideDecl with local typedef

[martong]

Summary

CXXDeductionGuideDecl with a local typedef has its own copy of the
TypedefDecl with the CXXDeductionGuideDecl as the DeclContext of that
TypedefDecl.

template <typename T> struct A {
  typedef T U;
  A(U, T);
};
A a{(int)0, (int)0};

Related discussion on cfe-dev:
http://lists.llvm.org/pipermail/cfe-dev/2020-November/067252.html

Without this fix, when we import the CXXDeductionGuideDecl (via
VisitFunctionDecl) then before creating the Decl we must import the
FunctionType. However, the first parameter's type is the afore mentioned
local typedef. So, we then start importing the TypedefDecl whose
DeclContext is the CXXDeductionGuideDecl itself. The infinite loop is
formed.

#0 clang::ASTNodeImporter::VisitCXXDeductionGuideDecl(clang::CXXDeductionGuideDecl*) clang/lib/AST/ASTImporter.cpp:3543:0
#1 clang::declvisitor::Base<std::add_pointer, clang::ASTNodeImporter, llvm::Expected<clang::Decl*> >::Visit(clang::Decl*) /home/egbomrt/WORK/llvm5/build/debug/tools/clang/include/clang/AST/DeclNodes.inc:405:0
#2 clang::ASTImporter::ImportImpl(clang::Decl*) clang/lib/AST/ASTImporter.cpp:8038:0
#3 clang::ASTImporter::Import(clang::Decl*) clang/lib/AST/ASTImporter.cpp:8200:0
#4 clang::ASTImporter::ImportContext(clang::DeclContext*) clang/lib/AST/ASTImporter.cpp:8297:0
#5 clang::ASTNodeImporter::ImportDeclContext(clang::Decl*, clang::DeclContext*&, clang::DeclContext*&) clang/lib/AST/ASTImporter.cpp:1852:0
#6 clang::ASTNodeImporter::ImportDeclParts(clang::NamedDecl*, clang::DeclContext*&, clang::DeclContext*&, clang::DeclarationName&, clang::NamedDecl*&, clang::SourceLocation&) clang/lib/AST/ASTImporter.cpp:1628:0
#7 clang::ASTNodeImporter::VisitTypedefNameDecl(clang::TypedefNameDecl*, bool) clang/lib/AST/ASTImporter.cpp:2419:0
#8 clang::ASTNodeImporter::VisitTypedefDecl(clang::TypedefDecl*) clang/lib/AST/ASTImporter.cpp:2500:0
#9 clang::declvisitor::Base<std::add_pointer, clang::ASTNodeImporter, llvm::Expected<clang::Decl*> >::Visit(clang::Decl*) /home/egbomrt/WORK/llvm5/build/debug/tools/clang/include/clang/AST/DeclNodes.inc:315:0
#10 clang::ASTImporter::ImportImpl(clang::Decl*) clang/lib/AST/ASTImporter.cpp:8038:0
#11 clang::ASTImporter::Import(clang::Decl*) clang/lib/AST/ASTImporter.cpp:8200:0
#12 llvm::Expected<clang::TypedefNameDecl*> clang::ASTNodeImporter::import<clang::TypedefNameDecl>(clang::TypedefNameDecl*) clang/lib/AST/ASTImporter.cpp:165:0
#13 clang::ASTNodeImporter::VisitTypedefType(clang::TypedefType const*) clang/lib/AST/ASTImporter.cpp:1304:0
#14 clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType> >::Visit(clang::Type const*) /home/egbomrt/WORK/llvm5/build/debug/tools/clang/include/clang/AST/TypeNodes.inc:74:0
#15 clang::ASTImporter::Import(clang::QualType) clang/lib/AST/ASTImporter.cpp:8071:0
#16 llvm::Expected<clang::QualType> clang::ASTNodeImporter::import<clang::QualType>(clang::QualType const&) clang/lib/AST/ASTImporter.cpp:179:0
#17 clang::ASTNodeImporter::VisitFunctionProtoType(clang::FunctionProtoType const*) clang/lib/AST/ASTImporter.cpp:1244:0
#18 clang::TypeVisitor<clang::ASTNodeImporter, llvm::Expected<clang::QualType> >::Visit(clang::Type const*) /home/egbomrt/WORK/llvm5/build/debug/tools/clang/include/clang/AST/TypeNodes.inc:47:0
#19 clang::ASTImporter::Import(clang::QualType) clang/lib/AST/ASTImporter.cpp:8071:0
#20 llvm::Expected<clang::QualType> clang::ASTNodeImporter::import<clang::QualType>(clang::QualType const&) clang/lib/AST/ASTImporter.cpp:179:0
#21 clang::QualType clang::ASTNodeImporter::importChecked<clang::QualType>(llvm::Error&, clang::QualType const&) clang/lib/AST/ASTImporter.cpp:198:0
#22 clang::ASTNodeImporter::VisitFunctionDecl(clang::FunctionDecl*) clang/lib/AST/ASTImporter.cpp:3313:0
#23 clang::ASTNodeImporter::VisitCXXDeductionGuideDecl(clang::CXXDeductionGuideDecl*) clang/lib/AST/ASTImporter.cpp:3543:0

The fix is to first create the TypedefDecl and only then start to import
the DeclContext.
Basically, we could do this during the import of all other Decls (not
just for typedefs). But it seems, there is only one another AST
construct that has a similar cycle: a struct defined as a function
parameter:

int struct_in_proto(struct data_t{int a;int b;} *d);

In that case, however, we had decided to return simply with an error
back then because that seemed to be a very rare construct.

[shafik]

clang/lib/AST/ASTImporter.cpp

2522

I am not super excited about this solution, I feel like several bugs we have had can be attributed to these exception control flow cases that we have in the ASTImporter. I don't have any immediate better solution.

[martong]

clang/lib/AST/ASTImporter.cpp

2522

Before uploading this patch I had been thinking about several other solutions
but all of them had some problems:

Detect the loop in the AST and return with UnsupportedConstruct. We could do
the detection with the help of ImportPath. However, I realized this approach is
way too defensive and removes the support for an important AST node which is
against our goals.

Try to eliminate the looping contruct from the AST. I could do that for some
cases (D92101) but there are still cases when the Sema must create such a loop
deliberately (the test case in this patch shows that).

It is essential to add a newly created Decl to the lookupTable ASAP because it
makes it possible for subsequent imports to find the existing Decl and this way
avoiding the creation of duplicated Decls. This is why AddToLookupTable is
called in MapImported. But the lookuptable operates on the DeclContext of the
Decl, and in this patch we must not import the DeclContext before.
Consequently, we have to add to the loopkuptable once the DeclContext is
imported. Perhaps, we could provide an optional lambda function to
GetImportedOrCreateDecl which would be called before MapImported (and that
lambda would do the DC import), but this seems even more clumsy.

BTW, the lookuptable is not used in LLDB, there you use the traditional lookup
implemented in DeclContext (addDeclInternal and noload_lookup). One problem
with noload_lookup is that it does not find some Decls because it obeys to C++
visibility rules, thus new duplicated Decls are created. The ASTImporter must
be able to lookup e.g. template specialization Decls too, in order to avoid
creating a redundant duplicated clone and this is the task of the lookupTable.
I hope one day LLDB would be able to switch to ASTImporterLookupTable from
noload_lookup. The other problem is with addDeclInternal: we call this later,
not in MapImported. The only responsibility attached to the use of addDeclInternal
should be to clone the visibility as it is in the source context (and not managing
the do-not-create-duplicate-decls issue).

So yes, there are many exceptional control flow cases, but most of them stems
from the complexity of trying to support two different needs: noload_lookup and
minimal import are needed exceptionally for LLDB. I was thinking about to
create a separate ASTImporter implementation specifically for CTU and LLDB
could have it's own implementation. For that we just need to create an
interface class with virtual functions. Having two different implementations
could save us from braking each others tests and this could be a big gain, WDYT?
(On the other hand, we'd loose updates and fixes from the other team.)

[martong]

I was thinking about to create a separate ASTImporter implementation specifically for CTU and LLDB could have it's own implementation. For that we just need to create an interface class with virtual functions.

One implementation could reside in libCrossTU and the other in LLDB. At least, that's what I thought. Unfortunately there is an obstacle which renders this whole idea practically unfeasible: Currently ASTImporter and ASTNodeImporter are friends of almost all AST classes.

[martong]

Ping.
@teemperor please take a look if you have some time. This is a really important patch which may influence some future directions regarding the ASTImporter.

[teemperor]

In D92209#2437416, @martong wrote:

Ping.
@teemperor please take a look if you have some time. This is a really important patch which may influence some future directions regarding the ASTImporter.

Apologies, last week was very busy here. I'll review this tomorrow morning.

[teemperor]

There are several LLDB tests failing with this change. The TestImportBaseClassWhenClassHasDerivedMember.py is probably the only relevant one. The others are probably failing for the same reason but with a more convoluted setup. I looked into the failure and it seems this patch is now skipping the workaround in ImportContext that was introduced in D78000 (as the Importer.GetAlreadyImportedOrNull will give us a DeclContext and then we just use that as-is). If you remove the if (!DC || !LexicalDC) before the if ((Err = ImportDeclContext(D, DC, LexicalDC))) this should keep the old behaviour.

Beside that issue this LGTM. Removing the 'if' seems straightforward, so I'll accept this. Thanks!

clang/lib/AST/ASTImporter.cpp

2522

I hope one day LLDB would be able to switch to ASTImporterLookupTable from noload_lookup.

Done here: https://reviews.llvm.org/D92848

clang/unittests/AST/ASTImporterTest.cpp

5932

Second parameter seems not relevant for the test?

[martong]

• Remove if (!DC || !LexicalDC)

[martong]

Thanks for the review guys!

clang/lib/AST/ASTImporter.cpp

2522

Thanks, this could enable some simplifications in the ASTImporter then.

[martong]

• Remove not relevant param from test

clang/lib/AST/ASTImporter.cpp

public:
     ExpectedType VisitPackExpansionType(const PackExpansionType *T);
     ExpectedType VisitDependentTemplateSpecializationType(
         const DependentTemplateSpecializationType *T);
     ExpectedType VisitObjCInterfaceType(const ObjCInterfaceType *T);
     ExpectedType VisitObjCObjectType(const ObjCObjectType *T);
     ExpectedType VisitObjCObjectPointerType(const ObjCObjectPointerType *T);
 
     // Importing declarations
+    Error ImportDeclParts(NamedDecl *D, DeclarationName &Name, NamedDecl *&ToD,
+                          SourceLocation &Loc);
     Error ImportDeclParts(
         NamedDecl *D, DeclContext *&DC, DeclContext *&LexicalDC,
         DeclarationName &Name, NamedDecl *&ToD, SourceLocation &Loc);
     Error ImportDefinitionIfNeeded(Decl *FromD, Decl *ToD = nullptr);
     Error ImportDeclarationNameLoc(
         const DeclarationNameInfo &From, DeclarationNameInfo &To);
     Error ImportDeclContext(DeclContext *FromDC, bool ForceImport = false);
     Error ImportDeclContext(
Error ASTNodeImporter::ImportDeclParts(
   ToD = cast_or_null<NamedDecl>(Importer.GetAlreadyImportedOrNull(D));
   if (ToD)
     if (Error Err = ASTNodeImporter(*this).ImportDefinitionIfNeeded(D, ToD))
       return Err;
 
   return Error::success();
 }
 
+Error ASTNodeImporter::ImportDeclParts(NamedDecl *D, DeclarationName &Name,
+                                       NamedDecl *&ToD, SourceLocation &Loc) {
+
+  // Import the name of this declaration.
+  if (Error Err = importInto(Name, D->getDeclName()))
+    return Err;
+
+  // Import the location of this declaration.
+  if (Error Err = importInto(Loc, D->getLocation()))
+    return Err;
+
+  ToD = cast_or_null<NamedDecl>(Importer.GetAlreadyImportedOrNull(D));
+  if (ToD)
+    if (Error Err = ASTNodeImporter(*this).ImportDefinitionIfNeeded(D, ToD))
+      return Err;
+
+  return Error::success();
+}
+
 Error ASTNodeImporter::ImportDefinitionIfNeeded(Decl *FromD, Decl *ToD) {
   if (!FromD)
     return Error::success();
 
   if (!ToD)
     if (Error Err = importInto(ToD, FromD))
       return Err;
 
ExpectedDecl ASTNodeImporter::VisitNamespaceAliasDecl(NamespaceAliasDecl *D) {
   LexicalDC->addDeclInternal(ToD);
 
   return ToD;
 }
 
 ExpectedDecl
 ASTNodeImporter::VisitTypedefNameDecl(TypedefNameDecl *D, bool IsAlias) {
   // Import the major distinguishing characteristics of this typedef.
-  DeclContext *DC, *LexicalDC;
   DeclarationName Name;
   SourceLocation Loc;
   NamedDecl *ToD;
-  if (Error Err = ImportDeclParts(D, DC, LexicalDC, Name, ToD, Loc))
+  // Do not import the DeclContext, we will import it once the TypedefNameDecl
+  // is created.
+  if (Error Err = ImportDeclParts(D, Name, ToD, Loc))
     return std::move(Err);
   if (ToD)
     return ToD;
 
+  DeclContext *DC = cast_or_null<DeclContext>(
+      Importer.GetAlreadyImportedOrNull(cast<Decl>(D->getDeclContext())));
+  DeclContext *LexicalDC =
+      cast_or_null<DeclContext>(Importer.GetAlreadyImportedOrNull(
+          cast<Decl>(D->getLexicalDeclContext())));
+
   // If this typedef is not in block scope, determine whether we've
   // seen a typedef with the same name (that we can merge with) or any
   // other entity by that name (which name lookup could conflict with).
   // Note: Repeated typedefs are not valid in C99:
   // 'typedef int T; typedef int T;' is invalid
   // We do not care about this now.
-  if (!DC->isFunctionOrMethod()) {
+  if (DC && !DC->isFunctionOrMethod()) {
     SmallVector<NamedDecl *, 4> ConflictingDecls;
     unsigned IDNS = Decl::IDNS_Ordinary;
     auto FoundDecls = Importer.findDeclsInToCtx(DC, Name);
     for (auto *FoundDecl : FoundDecls) {
       if (!FoundDecl->isInIdentifierNamespace(IDNS))
         continue;
       if (auto *FoundTypedef = dyn_cast<TypedefNameDecl>(FoundDecl)) {
         if (!hasSameVisibilityContextAndLinkage(FoundTypedef, D))
if (GetImportedOrCreateDecl<TypeAliasDecl>(
         ToTypedef, D, Importer.getToContext(), DC, ToBeginLoc, Loc,
         Name.getAsIdentifierInfo(), ToTypeSourceInfo))
       return ToTypedef;
   } else if (GetImportedOrCreateDecl<TypedefDecl>(
       ToTypedef, D, Importer.getToContext(), DC, ToBeginLoc, Loc,
       Name.getAsIdentifierInfo(), ToTypeSourceInfo))
     return ToTypedef;
 
-  ToTypedef->setAccess(D->getAccess());
+  // Import the DeclContext and set it to the Typedef.
+  if (!DC || !LexicalDC)
+    if ((Err = ImportDeclContext(D, DC, LexicalDC)))
+      return std::move(Err);
+  ToTypedef->setDeclContext(DC);
   ToTypedef->setLexicalDeclContext(LexicalDC);
+  // Add to the lookupTable because we could not do that in MapImported.
+  Importer.AddToLookupTable(ToTypedef);
+
+  ToTypedef->setAccess(D->getAccess());
 
   // Templated declarations should not appear in DeclContext.
   TypeAliasDecl *FromAlias = IsAlias ? cast<TypeAliasDecl>(D) : nullptr;
   if (!FromAlias || !FromAlias->getDescribedAliasTemplate())
     LexicalDC->addDeclInternal(ToTypedef);
 
   return ToTypedef;
 }
Decl *ASTImporter::MapImported(Decl *From, Decl *To) {
   assert((Pos == ImportedDecls.end() || Pos->second == To) &&
       "Try to import an already imported Decl");
   if (Pos != ImportedDecls.end())
     return Pos->second;
   ImportedDecls[From] = To;
   // This mapping should be maintained only in this function. Therefore do not
   // check for additional consistency.
   ImportedFromDecls[To] = From;
+  // In the case of TypedefNameDecl we create the Decl first and only then we
+  // import and set its DeclContext. So, the DC is still not set when we reach
+  // here from GetImportedOrCreateDecl.
+  if (To->getDeclContext())
     AddToLookupTable(To);
   return To;
 }
 
 llvm::Optional<ImportError>
 ASTImporter::getImportDeclErrorIfAny(Decl *FromD) const {
   auto Pos = ImportDeclErrors.find(FromD);
   if (Pos != ImportDeclErrors.end())
     return Pos->second;

clang/unittests/AST/ASTImporterTest.cpp

TEST_P(ImportFunctions, CTADUserDefinedExplicit) {
   ASSERT_FALSE(FromD->isImplicit());
   ASSERT_TRUE(FromD->isExplicit()); // Has the explicit keyword.
   auto *ToD = Import(FromD, Lang_CXX17);
   ASSERT_TRUE(ToD);
   EXPECT_FALSE(FromD->isImplicit());
   EXPECT_TRUE(ToD->isExplicit());
 }
 
+TEST_P(ImportFunctions, CTADWithLocalTypedef) {
+  Decl *TU = getTuDecl(
+      R"(
+      template <typename T> struct A {
+        typedef T U;
+        A(U, T);
+      };
+      A a{(int)0, (int)0};
+      )",
+      Lang_CXX17, "input.cc");
+  auto *FromD = FirstDeclMatcher<CXXDeductionGuideDecl>().match(
+      TU, cxxDeductionGuideDecl());
+  auto *ToD = Import(FromD, Lang_CXX17);
+  ASSERT_TRUE(ToD);
+}
+
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ASTImporterLookupTableTest,
                         DefaultTestValuesForRunOptions, );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportPath,
                         ::testing::Values(std::vector<std::string>()), );
 
 INSTANTIATE_TEST_CASE_P(ParameterizedTests, ImportExpr,
                         DefaultTestValuesForRunOptions, );