[lldb][modern-type-lookup] No longer import temporary declarations into the persistent AST

[teemperor]

Summary

As we figured out in D67803, importing declarations from a temporary ASTContext that were originally from a persistent ASTContext
causes a bunch of duplicated declarations where we end up having declarations in the target AST that have no associated ASTImporter that
can complete them.

I haven't figured out how/if we can solve this in the current way we do things in LLDB, but in the modern-type-lookup this is solvable
as we have a saner architecture with the ExternalASTMerger. As we can (hopefully) make modern-type-lookup the default mode in the future,
I would say we try fixing this issue here. As we don't use the hack that was reinstated in D67803 during modern-type-lookup, the test case for this
is essentially just printing any kind of container in std:: as we would otherwise run into the issue that required a hack like D67803.

What this patch is doing in essence is that instead of importing a declaration from a temporary ASTContext, we instead check if the
declaration originally came from a persistent ASTContext (e.g. the debug information) and we directly import from there. The ExternalASTMerger
is already connected with ASTImporters to these different sources, so this patch is essentially just two parts:

1. Mark our temporary ASTContext/ImporterSource as temporary when we import from the expression AST.
2. If the ExternalASTMerger sees we import from the expression AST, instead of trying to import these temporary declarations, check if we

can instead import from the persistent ASTContext that is already connected. This ensures that all records from the persistent source actually
come from the persistent source and are minimally imported in a way that allows them to be completed later on in the target AST.

The next step is to run the ASTImporter for these temporary expressions with the MinimalImport mode disabled, but that's a follow up patch.

This patch fixes most test failures with modern-type-lookup enabled by default (down to 73 failing tests, which includes the 22 import-std-module tests
which need special treatment).

[martong]

With [modern-type-lookup], we completely evade the use of ASTImporterDelegate? That would be a wonderful thing to use only the the ExternalASTMerger on a long term...

... a bunch of duplicated declarations

This popped a few thoughts into my head:
One way to discover duplicated declarations is to set the ODRViolation handling strategy to "conservative" in clang::ASTImporter. However, minimal imported decls will be structurally non-equivalent with those which are imported in normal mode. Thus, it may make sense only if the normal import mode is used exclusively.

The next step is to run the ASTImporter for these temporary expressions with the MinimalImport mode disabled, but that's a follow up patch.

👍 I think this is a very good direction.

clang/include/clang/AST/ExternalASTMerger.h

120

typo: functions -> function
FromD -> D ?

clang/lib/AST/DeclBase.cpp

95

Left over debug printout?

clang/lib/AST/ExternalASTMerger.cpp

108

I was thinking about that ToOrigin could be in the SharedState, but then I realized it is better to have it here, because the merger is the one which encapsulates the handling of several importers.

141

This line/sentence is hard to parse for me.
I get this part:

This way the ExternalASTMerger can safely do a minimal import that doesn't cause having minimally imported declarations in the target ASTContext.

But this I don't:

that no connected ASTImporter has imported.

149

👍
I like this approach.

[aprantl]

clang/include/clang/AST/ExternalASTMerger.h

87

super-nit: there's supposed to be a comma before and after "i.e." and "e.g." :-)

clang/lib/AST/ExternalASTMerger.cpp

171

&& "error message" ... this will help with debugging in a couple of months!

[shafik]

clang/include/clang/AST/ExternalASTMerger.h

95

Identifiers the begin with an underscore and followed by a capital letter are reserved see lex.name/p3.1:

Each identifier that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.

clang/lib/AST/ExternalASTMerger.cpp

141

I agree this is hard to parse, although I am happy that you are explaining the rationale.

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp

183

So we are removing this b/c we are now doing a minimal import from the temporary source and then in the next patch you will change that?

[teemperor]

clang/lib/AST/DeclBase.cpp

95

Whoops, thanks.

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp

183

We always did a minimal import here and the completer just tried to turn this a non-minimal import by iterating over the AST and then copying a bunch of declarations over. It currently only seems to cause errors in the existing tests. Also, we anyway don't test the feature it's actually supposed to implement anywhere in LLLDB as this is a bug in the original LLDB. So this just removes this code until we can properly implement and test it (which will hopefully just be turning off the MinimalImport when importing from temporary sources).

[teemperor]

• Addressed feedback (Thanks Gabor, Adrian & Shafik!)

[martong]

LGTM!

clang/include/clang/AST/ExternalASTMerger.h

public:
   /// ASTImporters require both ASTContext and FileManager to be able to
   /// import SourceLocations properly.  Additionally, when import occurs for
   /// a DeclContext whose origin has been overridden, then this
   /// ExternalASTMerger must be able to determine that.
   class ImporterSource {
     ASTContext *
     FileManager &FM;
     const OriginMap &OM;
+    /// True iff the source only exists temporary, i.e. it will be removed from
+    /// the ExternalASTMerger during the life time of the ExternalASTMerger.
+    bool Temporary;
+    /// If the ASTContext of this source has an ExternalASTMerger that imports
+    /// into this source, then this will point to that other ExternalASTMerger.
+    ExternalASTMerger *Merger;
 
   public:
-    ImporterSource(ASTContext &_AST, FileManager &_FM, const OriginMap &_OM)
-        : AST(_AST), FM(_FM), OM(_OM) {}
+    ImporterSource(ASTContext &_AST, FileManager &_FM, const OriginMap &_OM,
+                   bool _Temporary = false, ExternalASTMerger *Merger = nullptr)
+        : AST(_AST), FM(_FM), OM(_OM), Temporary(_Temporary), Merger(Merger) {}
     ASTContext &getASTContext() const { return AST; }
     FileManager &getFileManager() const { return FM; }
     const OriginMap &getOriginMap() const { return OM; }
+    bool isTemporary() const { return Temporary; }
+    ExternalASTMerger *getMerger() const { return Merger; }
   };
 
 private:
   /// The target for this ExtenralASTMerger.
   ImporterTarget Target;
   /// ExternalASTMerger has multiple ASTImporters that import into the same
   /// TU. This is the shared state for all ASTImporters of this
   /// ExternalASTMerger.
   /// See also the CrossTranslationUnitContext that has a similar setup.
   std::shared_ptr<ASTImporterSharedState> SharedState;
 
 public:
   ExternalASTMerger(const ImporterTarget &Target,
                     llvm::ArrayRef<ImporterSource> Sources);
 
+  /// Asks all connected ASTImporters if any of them imported the given
+  /// declaration. If any ASTImporter did import the given declaration,
+  /// then this functions returns the declaration that FromD was imported from.
+  /// Returns nullptr if no ASTImporter did import import FromD.
+  Decl *FindOriginalDecl(Decl *D);
+
   /// Add a set of ASTContexts as possible origins.
   ///
   /// Usually the set will be initialized in the constructor, but long-lived
   /// ExternalASTMergers may need to import from new sources (for example,
   /// newly-parsed source files).
   ///
   /// Ensures that Importers does not gain duplicate entries as a result.
   void AddSources(llvm::ArrayRef<ImporterSource> Sources);

clang/lib/AST/DeclBase.cpp

void *Decl::operator new(std::size_t Size, const ASTContext &Context,
   // Store the global declaration ID in the second 4 bytes.
   PrefixPtr[1] = ID;
 
   return Result;
 }
 
 void *Decl::operator new(std::size_t Size, const ASTContext &Ctx,
                          DeclContext *Parent, std::size_t Extra) {
+  if (!(!Parent || &Parent->getParentASTContext() == &Ctx)) {
+    llvm::errs() << Parent << " | " << &Parent->getParentASTContext()
+                 << "==" << &Ctx << "\n";
+  }
   assert(!Parent || &Parent->getParentASTContext() == &Ctx);
   // With local visibility enabled, we track the owning module even for local
   // declarations. We create the TU decl early and may not yet know what the
   // LangOpts are, so conservatively allocate the storage.
   if (Ctx.getLangOpts().trackLocalOwningModule() || !Parent) {
     // Ensure required alignment of the resulting object by adding extra
     // padding at the start if required.
     size_t ExtraAlign =

clang/lib/AST/ExternalASTMerger.cpp

 ///   arbitrary names in the source context.
 /// - It updates the ExternalASTMerger's origin map as needed whenever a
 ///   it sees a DeclContext.
 class LazyASTImporter : public ASTImporter {
 private:
   ExternalASTMerger &Parent;
   ASTImporter Reverse;
   const ExternalASTMerger::OriginMap &FromOrigins;
-
+  /// @see ExternalASTMerger::ImporterSource::Temporary
+  bool TemporarySource;
+  /// Map of imported declarations back to the declarations they originated
+  /// from.
+  llvm::DenseMap<Decl *, Decl *> ToOrigin;
+  /// @see ExternalASTMerger::ImporterSource::Merger
+  ExternalASTMerger *SourceMerger;
   llvm::raw_ostream &logs() { return Parent.logs(); }
 public:
   LazyASTImporter(ExternalASTMerger &_Parent, ASTContext &ToContext,
                   FileManager &ToFileManager,
                   const ExternalASTMerger::ImporterSource &_Source,
                   std::shared_ptr<ASTImporterSharedState> SharedState)
       : ASTImporter(ToContext, ToFileManager, _Source.getASTContext(),
                     _Source.getFileManager(),
                     /*MinimalImport=*/true, SharedState),
         Parent(_Parent),
         Reverse(_Source.getASTContext(), _Source.getFileManager(), ToContext,
                 ToFileManager, /*MinimalImport=*/true),
-        FromOrigins(_Source.getOriginMap()) {}
+        FromOrigins(_Source.getOriginMap()),
+        TemporarySource(_Source.isTemporary()),
+        SourceMerger(_Source.getMerger()) {}
+
+  llvm::Expected<Decl *> ImportImpl(Decl *FromD) override {
+    if (!TemporarySource || !SourceMerger)
+      return ASTImporter::ImportImpl(FromD);
+
+    // If we get here, then this source is importing from a temporary ASTContext
+    // that also has another ExternalASTMerger attached. It could be
+    // possible that the current ExternalASTMerger and the temporary ASTContext
+    // share a common ImporterSource, which means that the temporary
+    // AST could contain declarations that were imported from a source
+    // that this ExternalASTMerger can access directly. Instead of importing
+    // such declarations from the temporary ASTContext, they should instead
+    // be directly imported by this ExternalASTMerger from the original
+    // source. This way the ExternalASTMerger can safely do a minimal import
+    // that doesn't cause having minimally imported declarations in the target
+    // ASTContext that no connected ASTImporter has imported (and can complete).
+    //
+    // The following code tracks back any declaration that needs to be
+    // imported from the temporary ASTContext to a persistent ASTContext.
+    // Then the ExternalASTMerger tries to import from the persistent
+    // ASTContext directly by using the associated ASTImporter. If that
+    // succeeds, this ASTImporter just maps the declarations imported by
+    // the other (persistent) ASTImporter to this (temporary) ASTImporter.
+    // The steps can be visualized like this:
+    //
+    //  Target AST <--- 3. Indirect import --- Persistent AST
+    //       ^            of persistent decl        ^
+    //       |                                      |
+    // 1. Current import           2. Tracking back to persistent decl
+    // 4. Map persistent decl                       |
+    //  & pretend we imported.                      |
+    //       |                                      |
+    // Temporary AST -------------------------------'
+
+    // First, ask the ExternalASTMerger of the source where the temporary
+    // declaration originated from.
+    Decl *Persistent = SourceMerger->FindOriginalDecl(FromD);
+    // FromD isn't from a persistent AST, so just do a normal import.
+    if (!Persistent)
+      return ASTImporter::ImportImpl(FromD);
+    // Now ask the current ExternalASTMerger to try import the persistent
+    // declaration into the target.
+    ASTContext &PersistentCtx = Persistent->getASTContext();
+    ASTImporter &OtherImporter = Parent.ImporterForOrigin(PersistentCtx);
+    // Check that we never end up in the current Importer again.
+    assert(&PersistentCtx != &getFromContext());
+    assert(&OtherImporter != this);
+    auto DeclOrErr = OtherImporter.Import(Persistent);
+    // Errors when importing the persistent decl are treated as if we
+    // had errors with importing the temporary decl.
+    if (!DeclOrErr)
+      return DeclOrErr.takeError();
+    Decl *D = *DeclOrErr;
+    // Tell the current ASTImporter that this has already been imported
+    // to prevent any further queries for the temporary decl.
+    MapImported(FromD, D);
+    return D;
+  }
+
+  /// Implements the ASTImporter interface for tracking back a declaration
+  /// to its original declaration it came from.
+  Decl *GetOriginalDecl(Decl *To) override {
+    auto It = ToOrigin.find(To);
+    if (It != ToOrigin.end())
+      return It->second;
+    return nullptr;
+  }
 
   /// Whenever a DeclContext is imported, ensure that ExternalASTSource's origin
   /// map is kept up to date.  Also set the appropriate flags.
   void Imported(Decl *From, Decl *To) override {
+    ToOrigin[To] = From;
+
     if (auto *ToDC = dyn_cast<DeclContext>(To)) {
       const bool LoggingEnabled = Parent.LoggingEnabled();
       if (LoggingEnabled)
         logs() << "(ExternalASTMerger*)" << (void*)&Parent
                << " imported (DeclContext*)" << (void*)ToDC
                << ", (ASTContext*)" << (void*)&getToContext()
                << " from (DeclContext*)" << (void*)llvm::cast<DeclContext>(From)
                << ", (ASTContext*)" << (void*)&getFromContext()

 
 ExternalASTMerger::ExternalASTMerger(const ImporterTarget &Target,
                                      llvm::ArrayRef<ImporterSource> Sources) : LogStream(&llvm::nulls()), Target(Target) {
   SharedState = std::make_shared<ASTImporterSharedState>(
       *Target.AST.getTranslationUnitDecl());
   AddSources(Sources);
 }
 
+Decl *ExternalASTMerger::FindOriginalDecl(Decl *D) {
+  assert(&D->getASTContext() == &Target.AST);
+  for (const auto &I : Importers)
+    if (auto Result = I->GetOriginalDecl(D))
+      return Result;
+  return nullptr;
+}
+
 void ExternalASTMerger::AddSources(llvm::ArrayRef<ImporterSource> Sources) {
   for (const ImporterSource &S : Sources) {
     assert(&S.getASTContext() != &Target.AST);
+    // Check that the associated merger actually imports into the source AST.
+    assert(!S.getMerger() || &S.getMerger()->Target.AST == &S.getASTContext());
     Importers.push_back(std::make_unique<LazyASTImporter>(
         *this, Target.AST, Target.FM, S, SharedState));
   }
 }
 
 void ExternalASTMerger::RemoveSources(llvm::ArrayRef<ImporterSource> Sources) {
   if (LoggingEnabled())
     for (const ImporterSource &S : Sources)

lldb/packages/Python/lldbsuite/test/functionalities/modern-type-lookup/libcxx/TestLibCxxModernTypeLookup.py

def test(self):
         # Activate modern-type-lookup.
         self.runCmd("settings set target.experimental.use-modern-type-lookup true")
 
         lldbutil.run_to_source_breakpoint(self,
             "// Set break point at this line.", lldb.SBFileSpec("main.cpp"))
 
         # Test a few simple expressions that should still work with modern-type-lookup.
         self.expect("expr pair", substrs=["(std::", "pair<int, long", "= (first = 1, second = 2)"])
+        self.expect("expr foo", substrs=["(std::", "string", "\"bar\""])
+        self.expect("expr map", substrs=["(std::", "map", "first = 1, second = 2"])
+        self.expect("expr umap", substrs=["(std::", "unordered_map", "first = 1, second = 2"])

lldb/packages/Python/lldbsuite/test/functionalities/modern-type-lookup/libcxx/main.cpp

 #include <utility>
+#include <string>
+#include <map>
+#include <unordered_map>
 
 int main(int argc, char **argv) {
   std::pair<int, long> pair = std::make_pair<int, float>(1, 2L);
+  std::string foo = "bar";
+  std::map<int, int> map;
+  map[1] = 2;
+  std::unordered_map<int, int> umap;
+  umap[1] = 2;
   return pair.first; // Set break point at this line.
 }

lldb/source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp

if (target) {
       ret.byte_order = target->GetArchitecture().GetByteOrder();
       ret.address_byte_size = target->GetArchitecture().GetAddressByteSize();
     }
   }
 
   return ret;
 }
 
-namespace {
-/// This class walks an AST and ensures that all DeclContexts defined inside the
-/// current source file are properly complete.
-///
-/// This is used to ensure that persistent types defined in the current source
-/// file migrate completely to the persistent AST context before they are
-/// reused.  If that didn't happen, it would be impoossible to complete them
-/// because their origin would be gone.
-///
-/// The stragtegy used by this class is to check the SourceLocation (to be
-/// specific, the FileID) and see if it's the FileID for the current expression.
-/// Alternate strategies could include checking whether an ExternalASTMerger,
-/// set up to not have the current context as a source, can find an original for
-/// the type.
-class Completer : public clang::RecursiveASTVisitor<Completer> {
-private:
-  /// Used to import Decl contents
-  clang::ASTImporter &m_exporter;
-  /// The file that's going away
-  clang::FileID m_file;
-  /// Visited Decls, to avoid cycles
-  llvm::DenseSet<clang::Decl *> m_completed;
-
-  bool ImportAndCheckCompletable(clang::Decl *decl) {
-    llvm::Expected<clang::Decl *> imported_decl = m_exporter.Import(decl);
-    if (!imported_decl) {
-      llvm::consumeError(imported_decl.takeError());
-      return false;
-    }
-    if (m_completed.count(decl))
-      return false;
-    if (!llvm::isa<DeclContext>(decl))
-      return false;
-    const clang::SourceLocation loc = decl->getLocation();
-    if (!loc.isValid())
-      return false;
-    const clang::FileID file =
-        m_exporter.getFromContext().getSourceManager().getFileID(loc);
-    if (file != m_file)
-      return false;
-    // We are assuming the Decl was parsed in this very expression, so it
-    // should not have external storage.
-    lldbassert(!llvm::cast<DeclContext>(decl)->hasExternalLexicalStorage());
-    return true;
-  }
-
-  void Complete(clang::Decl *decl) {
-    m_completed.insert(decl);
-    auto *decl_context = llvm::cast<DeclContext>(decl);
-    llvm::Expected<clang::Decl *> imported_decl = m_exporter.Import(decl);
-    if (!imported_decl) {
-      llvm::consumeError(imported_decl.takeError());
-      return;
-    }
-    m_exporter.CompleteDecl(decl);
-    for (Decl *child : decl_context->decls())
-      if (ImportAndCheckCompletable(child))
-        Complete(child);
-  }
-
-  void MaybeComplete(clang::Decl *decl) {
-    if (ImportAndCheckCompletable(decl))
-      Complete(decl);
-  }
-
-public:
-  Completer(clang::ASTImporter &exporter, clang::FileID file)
-      : m_exporter(exporter), m_file(file) {}
-
-  // Implements the RecursiveASTVisitor's core API.  It is called on each Decl
-  // that the RecursiveASTVisitor encounters, and returns true if the traversal
-  // should continue.
-  bool VisitDecl(clang::Decl *decl) {
-    MaybeComplete(decl);
-    return true;
-  }
-};
-} // namespace
-
-static void CompleteAllDeclContexts(clang::ASTImporter &exporter,
-                                    clang::FileID file, clang::QualType root) {
-  clang::QualType canonical_type = root.getCanonicalType();
-  if (clang::TagDecl *tag_decl = canonical_type->getAsTagDecl()) {
-    Completer(exporter, file).TraverseDecl(tag_decl);
-  } else if (auto interface_type = llvm::dyn_cast<ObjCInterfaceType>(
-                 canonical_type.getTypePtr())) {
-    Completer(exporter, file).TraverseDecl(interface_type->getDecl());
-  } else {
-    Completer(exporter, file).TraverseType(canonical_type);
-  }
-}
-
 static clang::QualType ExportAllDeclaredTypes(
-    clang::ExternalASTMerger &merger, clang::ASTContext &source,
-    clang::FileManager &source_file_manager,
+    clang::ExternalASTMerger &parent_merger, clang::ExternalASTMerger &merger,
+    clang::ASTContext &source, clang::FileManager &source_file_manager,
     const clang::ExternalASTMerger::OriginMap &source_origin_map,
     clang::FileID file, clang::QualType root) {
+  // Mark the source as temporary to make sure all declarations from the
+  // AST are exported. Also add the parent_merger as the merger into the
+  // source AST so that the merger can track back any declarations from
+  // the persistent ASTs we used as sources.
   clang::ExternalASTMerger::ImporterSource importer_source(
-      source, source_file_manager, source_origin_map);
+      source, source_file_manager, source_origin_map, /*Temporary*/ true,
+      &parent_merger);
   merger.AddSources(importer_source);
   clang::ASTImporter &exporter = merger.ImporterForOrigin(source);
-  CompleteAllDeclContexts(exporter, file, root);
   llvm::Expected<clang::QualType> ret_or_error = exporter.Import(root);
   merger.RemoveSources(importer_source);
   if (ret_or_error) {
     return *ret_or_error;
   } else {
     Log *log = lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS);
     LLDB_LOG_ERROR(log, ret_or_error.takeError(), "Couldn't import type: {0}");
     return clang::QualType();
return TypeFromUser(m_ast_importer_sp->DeportType(
                         &target);
   } else if (m_merger_up) {
     clang::FileID source_file =
         source.getASTContext()->getSourceManager().getFileID(
             source.getASTContext()->getTranslationUnitDecl()->getLocation());
     auto scratch_ast_context = static_cast<ClangASTContextForExpressions *>(
         m_target->GetScratchClangASTContext());
     clang::QualType exported_type = ExportAllDeclaredTypes(
-        scratch_ast_context->GetMergerUnchecked(), *source.getASTContext(),
-        *source.getFileManager(), m_merger_up->GetOrigins(), source_file,
+        *m_merger_up.get(), scratch_ast_context->GetMergerUnchecked(),
+        *source.getASTContext(), *source.getFileManager(),
+        m_merger_up->GetOrigins(), source_file,
         clang::QualType::getFromOpaquePtr(parser_type.GetOpaqueQualType()));
     return TypeFromUser(exported_type.getAsOpaquePtr(), &target);
   } else {
     lldbassert(0 && "No mechanism for deporting a type!");
     return TypeFromUser();
   }
 }