Support template instantiation in the expression evaluator

[jarin]

Summary

WORK IN PROGRESS

This change is mostly for discussion, it is messy and likely wrong as I am new to the lldb codebase.

The goal of this exercise is to support expressions containing template instantiations, e.g. foo<int>::x.

The idea here is to collect all template types in the dwarf index. Later, when asked to find a name X, we import all the instantiations of X and pass the template declaration with the instantiations to Clang. In addition to my poor abstraction skills, the major problem with this is that we need to import all the instantiations even when only one is used. I tried to only import forward declarations, but if the instantiations were already previously completed, the AST importer still imports everything. This leads to massive evaluation times (tens of seconds) on templates with many instantiations (std::vector and the likes).

I am planning to pursue a different avenue, where I would introduce another hook into clang (perhaps in Sema::CheckTemplateIdType), but I am not sure how viable that path is.

[teemperor]

Will properly review this later, but this seems like a patch that might be related to the performance issue here: https://reviews.llvm.org/D41416

[jarin]

This update introduces a callback from clang for template specialization. The callback allows lldb to construct instantiations on demand, rather than having to create the instantiation eagerly.

Perhaps it would still beneficial to prune the instantiations (we only need one "sample" instantiation per template) when querying the generic type from the symbol file so that we do not have to parse all the instantiations eagerly.

[friss]

Sorry that I haven't reviewed the patch, but there's something I'd like to point out before anyone invests a lot of time into plugin holes in our current template support code.

It would be great to fix the way templates are represented, because currently the debug info doesn't allow us to answer Clang's requests correctly. There is the beginning of a discussion here: http://lists.llvm.org/pipermail/lldb-commits/Week-of-Mon-20180507/040689.html

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

[jarin]

In D69309#1752738, @friss wrote:

Sorry that I haven't reviewed the patch, but there's something I'd like to point out before anyone invests a lot of time into plugin holes in our current template support code.

It would be great to fix the way templates are represented, because currently the debug info doesn't allow us to answer Clang's requests correctly. There is the beginning of a discussion here: http://lists.llvm.org/pipermail/lldb-commits/Week-of-Mon-20180507/040689.html

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Having an entity for the template itself would be great. However, that would require compiler changes, so only the code compiled with new compilers would benefit, no? I am afraid we need a story for older toolchains, too.

In this patch, I do it in a really hacky way that does not work with accelerator tables, it only works with ManualDWARFIndex by extracting template names from instantiated templates.

[teemperor]

I think this approach looks already much more feasible than the last iteration.

+Richard because he knows better how FindClassTemplateSpecialization should look like to fit into the other lookup mechanisms we have in the ExternalASTSource (and I guess there is some more work needed to not violate some AST invariants and do this lookup in the right places). And +Vassil because he is probably also interested in having something like this for Modules at some point.

[labath]

In D69309#1754593, @jarin wrote:

In D69309#1752738, @friss wrote:

Sorry that I haven't reviewed the patch, but there's something I'd like to point out before anyone invests a lot of time into plugin holes in our current template support code.

It would be great to fix the way templates are represented, because currently the debug info doesn't allow us to answer Clang's requests correctly. There is the beginning of a discussion here: http://lists.llvm.org/pipermail/lldb-commits/Week-of-Mon-20180507/040689.html

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Having an entity for the template itself would be great. However, that would require compiler changes, so only the code compiled with new compilers would benefit, no? I am afraid we need a story for older toolchains, too.

Well, I think that's a question of tradeoffs -- i.e., how many hoops you would need to jump through to support the old compiler. Since the "manual" index needs to scan the debug info anyway, I think that the cost of supporting this flow (both in terms of runtime and code complexity) would be sufficiently low to enable that. However, for the apple/dwarf5 indexes the cost (both kinds) might be prohibitively high...

I don't think that supporting this only in the "manual" case would be that bad, but would still probably want to consider the problem as a whole, and come up with an accelerator story too, so that they can eventually catch up in terms of functionality...

[friss]

In D69309#1754659, @labath wrote:

In D69309#1754593, @jarin wrote:

In D69309#1752738, @friss wrote:

Sorry that I haven't reviewed the patch, but there's something I'd like to point out before anyone invests a lot of time into plugin holes in our current template support code.

It would be great to fix the way templates are represented, because currently the debug info doesn't allow us to answer Clang's requests correctly. There is the beginning of a discussion here: http://lists.llvm.org/pipermail/lldb-commits/Week-of-Mon-20180507/040689.html

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Having an entity for the template itself would be great. However, that would require compiler changes, so only the code compiled with new compilers would benefit, no? I am afraid we need a story for older toolchains, too.

Finding a way to handle older toolchains would be great, but not essential IMO. I would hope that when most people upgrade their LLDB, they also get a Clang update. We need to be careful not to break what is already working with older compilers though.

[clayborg]

I wanted to make sure that people understand about how templates are done in DWARF and the implications, just for completeness:

1. DWARF represents only specializations of templates (foo<int>) and not the generic template definition in terms of type T (foo<T>)
2. DWARF only creates the methods that are used in each compile unit. So we might only have std::vector<int>::erase() and std::vector<int>::back() in one compile unit and std::vector<int>::operator[](size_t) in another
3. The template type definitions we create in the clang AST context therefore have no generic template methods. The definition for foo<T> has no methods. All methods for the specialized type (foo<int>) are treated as specializations specific to the <int> type. We have to do this since we item #2 above might only have a fraction of the real template definition's methods.
4. #3 means that we must iterate over all instances of foo<int> to find as many methods as possible when creating the type since each one might only have a fraction of all methods from the original foo<T> definition in the code.

Any fixes we check in should:

• make sure that all tests that were previously passing continue to pass if we do any modifications.
• work for all cases (manual indexing, accelerator tables from apple and DWARF)

[v.g.vassilev]

https://reviews.llvm.org/D41416 could be relevant. I am not an expert but I think when reading the DWARF you could only register 'lazy' specializations which will be imported only when really required.

[jarin]

In D69309#1763454, @v.g.vassilev wrote:

https://reviews.llvm.org/D41416 could be relevant. I am not an expert but I think when reading the DWARF you could only register 'lazy' specializations which will be imported only when really required.

https://reviews.llvm.org/D41416 is indeed relevant, but it has not been landed. I suffer from the same problem you do - lldb needs all the specializations, but providing those takes too much time. Are you still planning to land your granular lazy specialization change?

[jarin]

In D69309#1752738, @friss wrote:

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Frederic, you say that "doing this in the compiler causes test failures in LLDB", which implies you have tried adding the template in the compiler. Do you have that compiler patch lying around so that we could have a look at what can be done on the lldb side?

I agree that a good long term fix is to have "Foo" as an entity in DWARF, although for backwards compatibility it might be better if the "Foo" template just contained references to the instantiations rather than having them as children.

[labath]

In D69309#1787297, @jarin wrote:

In D69309#1752738, @friss wrote:

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Frederic, you say that "doing this in the compiler causes test failures in LLDB", which implies you have tried adding the template in the compiler. Do you have that compiler patch lying around so that we could have a look at what can be done on the lldb side?

I agree that a good long term fix is to have "Foo" as an entity in DWARF, although for backwards compatibility it might be better if the "Foo" template just contained references to the instantiations rather than having them as children.

I am afraid you're overestimating the scope of that idea. I *think* that Fred was referring to simply changing the string that gets put into the DW_AT_name field of the /instantation/ (and, by extension, the accelerator table). The debug info would still describe instantiations only.

I don't believe anyone here was proposing to have DWARF actually describe templates themselves -- that might be possible, but you'd have to get pretty creative with dwarf attributes (and convince a bunch of people that this is actually a good idea).

[jarin]

In D69309#1787409, @labath wrote:

In D69309#1787297, @jarin wrote:

In D69309#1752738, @friss wrote:

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Frederic, you say that "doing this in the compiler causes test failures in LLDB", which implies you have tried adding the template in the compiler. Do you have that compiler patch lying around so that we could have a look at what can be done on the lldb side?

I agree that a good long term fix is to have "Foo" as an entity in DWARF, although for backwards compatibility it might be better if the "Foo" template just contained references to the instantiations rather than having them as children.

I am afraid you're overestimating the scope of that idea. I *think* that Fred was referring to simply changing the string that gets put into the DW_AT_name field of the /instantation/ (and, by extension, the accelerator table). The debug info would still describe instantiations only.

I don't believe anyone here was proposing to have DWARF actually describe templates themselves -- that might be possible, but you'd have to get pretty creative with dwarf attributes (and convince a bunch of people that this is actually a good idea).

You are right, I was indeed imagining something else. What Fred proposes makes a lot of sense to me, although the lookup of instantiations might be slow because there would be no accelerator for that (but we could build one).

[labath]

In D69309#1787468, @jarin wrote:

What Fred proposes makes a lot of sense to me, although the lookup of instantiations might be slow because there would be no accelerator for that (but we could build one).

Do we ever lookup instantiations through this API? Seems pretty fragile, due to all the template brackets and all kinds of whitespace one could insert between them...

[jarin]

In D69309#1787481, @labath wrote:

In D69309#1787468, @jarin wrote:

What Fred proposes makes a lot of sense to me, although the lookup of instantiations might be slow because there would be no accelerator for that (but we could build one).

Do we ever lookup instantiations through this API? Seems pretty fragile, due to all the template brackets and all kinds of whitespace one could insert between them...

I did it in this patch and it worked, but I agree it is brittle. Other than that, I think it is not used.

[friss]

In D69309#1787409, @labath wrote:

In D69309#1787297, @jarin wrote:

In D69309#1752738, @friss wrote:

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Frederic, you say that "doing this in the compiler causes test failures in LLDB", which implies you have tried adding the template in the compiler. Do you have that compiler patch lying around so that we could have a look at what can be done on the lldb side?

I agree that a good long term fix is to have "Foo" as an entity in DWARF, although for backwards compatibility it might be better if the "Foo" template just contained references to the instantiations rather than having them as children.

I am afraid you're overestimating the scope of that idea. I *think* that Fred was referring to simply changing the string that gets put into the DW_AT_name field of the /instantation/ (and, by extension, the accelerator table). The debug info would still describe instantiations only.

Just confirming that this is indeed what I meant. I don't have the patch handy anymore (it was extremely small, about 5 lines IIRC).

[probinson]

In D69309#1787994, @friss wrote:

In D69309#1787409, @labath wrote:

In D69309#1787297, @jarin wrote:

In D69309#1752738, @friss wrote:

Basically, today the debug info will describe an entity named "Foo<int>". The accelerator tables all reference this name. So when Clang asks us if we know "Foo" (which is what happens when instantiating), we fail to find the right instantiations. The consensus of the above discussion was that we should change the debug info to have "Foo" as the name of any instantiation, with a child DIE describing the template arguments. Just doing this in the compiler causes test failures in LLDB, so there's some work to do in LLDB to support this.

Frederic, you say that "doing this in the compiler causes test failures in LLDB", which implies you have tried adding the template in the compiler. Do you have that compiler patch lying around so that we could have a look at what can be done on the lldb side?

I agree that a good long term fix is to have "Foo" as an entity in DWARF, although for backwards compatibility it might be better if the "Foo" template just contained references to the instantiations rather than having them as children.

I am afraid you're overestimating the scope of that idea. I *think* that Fred was referring to simply changing the string that gets put into the DW_AT_name field of the /instantation/ (and, by extension, the accelerator table). The debug info would still describe instantiations only.

Just confirming that this is indeed what I meant. I don't have the patch handy anymore (it was extremely small, about 5 lines IIRC).

FWIW, the Sony debugger throws away the <type> part of the DW_AT_name and reconstructs it from the template_parameter children. The presence of typedefs and/or enums can make the <type> text inconsistent, especially across enums. Our debugger reconstructs the type-parameters because it's more consistent that way.

[jarin]

FWIW, the Sony debugger throws away the <type> part of the DW_AT_name and reconstructs it from the template_parameter children. The presence of typedefs and/or enums can make the <type> text inconsistent, especially across enums. Our debugger reconstructs the type-parameters because it's more consistent that way.

We have not seen any problems yet, but it does make sense to protect ourselves against different compilers. (I am not quite sure when I'll get back to this patch again as the current version has been good enough for our branch so far.)

clang/include/clang/AST/ExternalASTSource.h

 #include <iterator>
 #include <string>
 #include <utility>
 
 namespace clang {
 
 class ASTConsumer;
 class ASTContext;
+class ClassTemplateDecl;
 class CXXBaseSpecifier;
 class CXXCtorInitializer;
 class CXXRecordDecl;
 class DeclarationName;
 class FieldDecl;
 class IdentifierInfo;
 class NamedDecl;
 class ObjCInterfaceDecl;
public:
   /// Gives the external AST source an opportunity to complete an
   /// incomplete Objective-C class.
   ///
   /// This routine will only be invoked if the "externally completed" bit is
   /// set on the ObjCInterfaceDecl via the function
   /// \c ObjCInterfaceDecl::setExternallyCompleted().
   virtual void CompleteType(ObjCInterfaceDecl *Class);
 
+  /// Gives the external AST source an opportunity to insert class
+  /// template instantiations.
+  virtual bool FindClassTemplateSpecialization(ClassTemplateDecl *ClassTemplate,
+                                               ArrayRef<TemplateArgument> Args);
+
   /// Loads comment ranges.
   virtual void ReadComments();
 
   /// Notify ExternalASTSource that we started deserialization of
   /// a decl or type so until FinishedDeserializing is called there may be
   /// decls that are initializing. Must be paired with FinishedDeserializing.
   ///
   /// The default implementation of this method is a no-op.

clang/lib/AST/ExternalASTSource.cpp

 //===- ExternalASTSource.cpp - Abstract External AST Interface ------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file provides the default implementation of the ExternalASTSource
 //  interface, which enables construction of AST nodes from some external
 //  source.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ExternalASTSource.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/DeclTemplate.h"
 #include "clang/AST/DeclarationName.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/Module.h"
 #include "llvm/ADT/None.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cstdint>
 
void ExternalASTSource::FindFileRegionDecls(FileID File, unsigned Offset,
                                             SmallVectorImpl<Decl *> &Decls) {}
 
 void ExternalASTSource::CompleteRedeclChain(const Decl *D) {}
 
 void ExternalASTSource::CompleteType(TagDecl *Tag) {}
 
 void ExternalASTSource::CompleteType(ObjCInterfaceDecl *Class) {}
 
+bool ExternalASTSource::FindClassTemplateSpecialization(
+    ClassTemplateDecl *ClassTemplate, ArrayRef<TemplateArgument> Args) {
+  return false;
+}
+
 void ExternalASTSource::ReadComments() {}
 
 void ExternalASTSource::StartedDeserializing() {}
 
 void ExternalASTSource::FinishedDeserializing() {}
 
 void ExternalASTSource::StartTranslationUnit(ASTConsumer *Consumer) {}
 

clang/lib/Sema/SemaTemplate.cpp

QualType Sema::CheckTemplateIdType(TemplateName Name,
   } else if (ClassTemplateDecl *ClassTemplate
                = dyn_cast<ClassTemplateDecl>(Template)) {
     // Find the class template specialization declaration that
     // corresponds to these arguments.
     void *InsertPos = nullptr;
     ClassTemplateSpecializationDecl *Decl
       = ClassTemplate->findSpecialization(Converted, InsertPos);
     if (!Decl) {
+      // If we have external source, try to find the specialization
+      // in the external source.
+      if (auto *Source = Context.getExternalSource()) {
+        if (Source->FindClassTemplateSpecialization(ClassTemplate, Converted))
+          Decl = ClassTemplate->findSpecialization(Converted, InsertPos);
+      }
+    }
+    if (!Decl) {
       // This is the first time we have referenced this class template
       // specialization. Create the canonical declaration and add it to
       // the set of specializations.
       Decl = ClassTemplateSpecializationDecl::Create(
           Context, ClassTemplate->getTemplatedDecl()->getTagKind(),
           ClassTemplate->getDeclContext(),
           ClassTemplate->getTemplatedDecl()->getBeginLoc(),
           ClassTemplate->getLocation(), ClassTemplate, Converted, nullptr);

lldb/packages/Python/lldbsuite/test/lang/cpp/class-template-instantiation/Makefile

+CXX_SOURCES := main.cpp
+
+include Makefile.rules

lldb/packages/Python/lldbsuite/test/lang/cpp/class-template-instantiation/TestClassTemplateInstantiation.py

+"""
+Test that the expression evaluator can instantiate templates. We should be able
+to instantiate at least those templates that are instantiated in the symbol
+file.
+"""
+
+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+
+class TestClassTemplateInstantiation(TestBase):
+    mydir = TestBase.compute_mydir(__file__)
+
+    @skipIf(debug_info=no_match(["dwarf"]),oslist=no_match(["macosx"]))
+    def test_instantiate_template_from_function(self):
+        self.main_source_file = lldb.SBFileSpec("main.cpp")
+        self.build()
+        (_, _, thread, _) = lldbutil.run_to_source_breakpoint(self, "// break main", self.main_source_file)
+        frame = thread.GetSelectedFrame()
+
+        expr_result = frame.EvaluateExpression("foo<char>::x")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "43")
+
+        expr_result = frame.EvaluateExpression("foo<int>::x")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "46")
+
+        expr_result = frame.EvaluateExpression("sizeof(A::bar<short>)")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "2")
+
+        expr_result = frame.EvaluateExpression("sizeof(A::bar<int>)")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "4")
+
+    @skipIf(debug_info=no_match(["dwarf"]),oslist=no_match(["macosx"]))
+    def test_instantiate_template_from_method(self):
+        self.main_source_file = lldb.SBFileSpec("main.cpp")
+        self.build()
+        (_, _, thread, _) = lldbutil.run_to_source_breakpoint(self, "// break method", self.main_source_file)
+        frame = thread.GetSelectedFrame()
+
+        expr_result = frame.EvaluateExpression("sizeof(bar<short>)")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "2")
+
+        expr_result = frame.EvaluateExpression("sizeof(bar<int>)")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "4")
+
+        expr_result = frame.EvaluateExpression("::foo<char>::x")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "43")
+
+        expr_result = frame.EvaluateExpression("foo<int>::x")
+        self.assertTrue(expr_result.IsValid())
+        self.assertEqual(expr_result.GetValue(), "46")

lldb/packages/Python/lldbsuite/test/lang/cpp/class-template-instantiation/main.cpp

+template <typename T>
+struct foo {
+  static int x;
+};
+
+template <typename T>
+int foo<T>::x = 42 + sizeof(T);
+
+struct A {
+  template <typename T>
+  struct bar {
+    T f;
+  };
+
+  bar<int> bi;
+  bar<short> bs;
+
+  int size() {
+    return sizeof(bar<int>) + sizeof(bar<short>); // break method
+  }
+};
+
+int main() {
+  A a;
+  a.size();
+  return foo<char>::x + foo<int>::x;  // break main
+}

lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.h

public:
   void CompleteType(clang::TagDecl *Tag) override;
 
   /// Complete an ObjCInterfaceDecl.
   ///
   /// \param[in] Class
   ///     The Decl to be completed in place.
   void CompleteType(clang::ObjCInterfaceDecl *Class) override;
 
+  /// Find class template specialization for a class template.
+  ///
+  /// \param[in] ClassTemplate
+  ///     The class template to specialize.
+  /// \param[in] Args
+  //      Specialization arguments.
+  //  \return
+  //      True iff a specialization is found.
+  bool FindClassTemplateSpecialization(
+      clang::ClassTemplateDecl *ClassTemplate,
+      llvm::ArrayRef<clang::TemplateArgument> Args) override;
+
   /// Called on entering a translation unit.  Tells Clang by calling
   /// setHasExternalVisibleStorage() and setHasExternalLexicalStorage() that
   /// this object has something to say about undefined names.
   ///
   /// \param[in] Consumer
   ///     Unused.
   void StartTranslationUnit(clang::ASTConsumer *Consumer) override;
 
public:
     void CompleteType(clang::TagDecl *Tag) override {
       return m_original.CompleteType(Tag);
     }
 
     void CompleteType(clang::ObjCInterfaceDecl *Class) override {
       return m_original.CompleteType(Class);
     }
 
+    bool FindClassTemplateSpecialization(
+        clang::ClassTemplateDecl *ClassTemplate,
+        llvm::ArrayRef<clang::TemplateArgument> Args) override {
+      return m_original.FindClassTemplateSpecialization(ClassTemplate, Args);
+    }
+
     bool layoutRecordType(
         const clang::RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
         llvm::DenseMap<const clang::FieldDecl *, uint64_t> &FieldOffsets,
         llvm::DenseMap<const clang::CXXRecordDecl *, clang::CharUnits>
             &BaseOffsets,
         llvm::DenseMap<const clang::CXXRecordDecl *, clang::CharUnits>
             &VirtualBaseOffsets) override {
       return m_original.layoutRecordType(Record, Size, Alignment, FieldOffsets,

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

clang::ObjCInterfaceDecl *ClangASTSource::GetCompleteObjCInterface(
   if (!complete_interface_type)
     return nullptr;
 
   ObjCInterfaceDecl *complete_iface_decl(complete_interface_type->getDecl());
 
   return complete_iface_decl;
 }
 
+namespace {
+
+std::string
+GetNameForClassTemplateSpecialization(ClassTemplateDecl *class_template,
+                                      ArrayRef<TemplateArgument> args) {
+  clang::LangOptions lang_options;
+  lang_options.CPlusPlus = true;
+  lang_options.Bool = true;
+  PrintingPolicy policy(lang_options);
+
+  std::string name;
+  llvm::raw_string_ostream os(name);
+  class_template->printQualifiedName(os, policy);
+  os << "<";
+  bool is_first = true;
+  for (auto arg : args) {
+    if (is_first)
+      is_first = false;
+    else
+      os << ", ";
+    arg.print(policy, os);
+  }
+  os << ">";
+  return os.str();
+}
+
+} // namespace
+
+bool ClangASTSource::FindClassTemplateSpecialization(
+    ClassTemplateDecl *class_template, ArrayRef<TemplateArgument> args) {
+  Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS));
+  static unsigned int invocation_id = 0;
+  unsigned int current_id = invocation_id++;
+
+  const ConstString name(
+      GetNameForClassTemplateSpecialization(class_template, args));
+
+  if (log) {
+    LLDB_LOGF(
+        log,
+        "    FindClassTemplateSpecialization[%u] on (ASTContext*)%p Completing "
+        "(ClassTemplateDecl*)%p, searching for %s",
+        current_id, static_cast<void *>(m_ast_context),
+        static_cast<void *>(class_template), name.GetCString());
+
+    LLDB_LOGF(log, "      FCTS[%u] Before:", current_id);
+    ASTDumper dumper((Decl *)class_template);
+    dumper.ToLog(log, "      [FCTS] ");
+  }
+
+  TypeList types;
+  llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
+  m_target->GetImages().FindTypes(nullptr, name, true, 1, searched_symbol_files,
+                                  types);
+
+  size_t num_types = types.GetSize();
+  for (size_t ti = 0; ti < num_types; ++ti) {
+    lldb::TypeSP type_sp = types.GetTypeAtIndex(ti);
+    CompilerType full_type = type_sp->GetFullCompilerType();
+    if (GuardedCopyType(full_type)) {
+      LLDB_LOGF(log, "      FCTS[%u] Specialization inserted.", current_id);
+      return true;
+    }
+  }
+  LLDB_LOGF(log, "      FCTS[%u] Specialization not found.", current_id);
+  return false;
+}
+
 void ClangASTSource::FindExternalLexicalDecls(
     const DeclContext *decl_context,
     llvm::function_ref<bool(Decl::Kind)> predicate,
     llvm::SmallVectorImpl<Decl *> &decls) {
 
   if (HasMerger()) {
     if (auto *interface_decl = dyn_cast<ObjCInterfaceDecl>(decl_context)) {
       ObjCInterfaceDecl *complete_iface_decl =

lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.h

public:
   void GetGlobalVariables(const RegularExpression &regex,
                           DIEArray &offsets) override;
   void GetGlobalVariables(const DWARFUnit &cu, DIEArray &offsets) override;
   void GetObjCMethods(ConstString class_name, DIEArray &offsets) override;
   void GetCompleteObjCClass(ConstString class_name, bool must_be_implementation,
                             DIEArray &offsets) override;
   void GetTypes(ConstString name, DIEArray &offsets) override;
   void GetTypes(const DWARFDeclContext &context, DIEArray &offsets) override;
+  void GetGenericTypes(ConstString name, DIEArray &offsets) override;
+  void GetGenericTypes(const DWARFDeclContext &context,
+                       DIEArray &offsets) override;
   void GetNamespaces(ConstString name, DIEArray &offsets) override;
   void GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                     const CompilerDeclContext &parent_decl_ctx,
                     uint32_t name_type_mask,
                     std::vector<DWARFDIE> &dies) override;
   void GetFunctions(const RegularExpression &regex, DIEArray &offsets) override;
 
   void ReportInvalidDIERef(const DIERef &ref, llvm::StringRef name) override;

lldb/source/Plugins/SymbolFile/DWARF/AppleDWARFIndex.cpp

if (log)
       m_module.LogMessage(log, "FindByNameAndTag()");
     m_apple_types_up->FindByNameAndTag(type_name.GetStringRef(), tag, offsets);
     return;
   }
 
   m_apple_types_up->FindByName(type_name.GetStringRef(), offsets);
 }
 
+void AppleDWARFIndex::GetGenericTypes(ConstString name, DIEArray &offsets) {
+  return;
+}
+
+void AppleDWARFIndex::GetGenericTypes(const DWARFDeclContext &context,
+                                      DIEArray &offsets) {
+  return;
+}
+
 void AppleDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
   if (m_apple_namespaces_up)
     m_apple_namespaces_up->FindByName(name.GetStringRef(), offsets);
 }
 
 void AppleDWARFIndex::GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                                    const CompilerDeclContext &parent_decl_ctx,
                                    uint32_t name_type_mask,

lldb/source/Plugins/SymbolFile/DWARF/DWARFIndex.h

virtual void GetGlobalVariables(const RegularExpression &regex,
                                   DIEArray &offsets) = 0;
   virtual void GetGlobalVariables(const DWARFUnit &cu, DIEArray &offsets) = 0;
   virtual void GetObjCMethods(ConstString class_name, DIEArray &offsets) = 0;
   virtual void GetCompleteObjCClass(ConstString class_name,
                                     bool must_be_implementation,
                                     DIEArray &offsets) = 0;
   virtual void GetTypes(ConstString name, DIEArray &offsets) = 0;
   virtual void GetTypes(const DWARFDeclContext &context, DIEArray &offsets) = 0;
+  virtual void GetGenericTypes(ConstString name, DIEArray &offsets) = 0;
+  virtual void GetGenericTypes(const DWARFDeclContext &context,
+                               DIEArray &offsets) = 0;
   virtual void GetNamespaces(ConstString name, DIEArray &offsets) = 0;
   virtual void GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                             const CompilerDeclContext &parent_decl_ctx,
                             uint32_t name_type_mask,
                             std::vector<DWARFDIE> &dies) = 0;
   virtual void GetFunctions(const RegularExpression &regex,
                             DIEArray &offsets) = 0;
 

lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h

public:
   void GetGlobalVariables(const RegularExpression &regex,
                           DIEArray &offsets) override;
   void GetGlobalVariables(const DWARFUnit &cu, DIEArray &offsets) override;
   void GetObjCMethods(ConstString class_name, DIEArray &offsets) override {}
   void GetCompleteObjCClass(ConstString class_name, bool must_be_implementation,
                             DIEArray &offsets) override;
   void GetTypes(ConstString name, DIEArray &offsets) override;
   void GetTypes(const DWARFDeclContext &context, DIEArray &offsets) override;
+  void GetGenericTypes(ConstString name, DIEArray &offsets) override;
+  void GetGenericTypes(const DWARFDeclContext &context,
+                       DIEArray &offsets) override;
   void GetNamespaces(ConstString name, DIEArray &offsets) override;
   void GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                     const CompilerDeclContext &parent_decl_ctx,
                     uint32_t name_type_mask,
                     std::vector<DWARFDIE> &dies) override;
   void GetFunctions(const RegularExpression &regex,
                     DIEArray &offsets) override;
 

lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp

void DebugNamesDWARFIndex::GetTypes(const DWARFDeclContext &context,
 
   for (const DebugNames::Entry &entry :
        m_debug_names_up->equal_range(context[0].name)) {
     if (entry.tag() == context[0].tag)
       Append(entry, offsets);
   }
 }
 
+void DebugNamesDWARFIndex::GetGenericTypes(ConstString name,
+                                           DIEArray &offsets) {
+  m_fallback.GetGenericTypes(name, offsets);
+}
+
+void DebugNamesDWARFIndex::GetGenericTypes(const DWARFDeclContext &context,
+                                           DIEArray &offsets) {
+  m_fallback.GetGenericTypes(context, offsets);
+}
+
 void DebugNamesDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
   m_fallback.GetNamespaces(name, offsets);
 
   for (const DebugNames::Entry &entry :
        m_debug_names_up->equal_range(name.GetStringRef())) {
     if (entry.tag() == DW_TAG_namespace)
       Append(entry, offsets);
   }

lldb/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.h

public:
   void GetGlobalVariables(const RegularExpression &regex,
                           DIEArray &offsets) override;
   void GetGlobalVariables(const DWARFUnit &unit, DIEArray &offsets) override;
   void GetObjCMethods(ConstString class_name, DIEArray &offsets) override;
   void GetCompleteObjCClass(ConstString class_name, bool must_be_implementation,
                             DIEArray &offsets) override;
   void GetTypes(ConstString name, DIEArray &offsets) override;
   void GetTypes(const DWARFDeclContext &context, DIEArray &offsets) override;
+  void GetGenericTypes(ConstString name, DIEArray &offsets) override;
+  void GetGenericTypes(const DWARFDeclContext &context,
+                       DIEArray &offsets) override;
   void GetNamespaces(ConstString name, DIEArray &offsets) override;
   void GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                     const CompilerDeclContext &parent_decl_ctx,
                     uint32_t name_type_mask,
                     std::vector<DWARFDIE> &dies) override;
   void GetFunctions(const RegularExpression &regex, DIEArray &offsets) override;
 
   void ReportInvalidDIERef(const DIERef &ref, llvm::StringRef name) override {}
   void Dump(Stream &s) override;
 
 private:
   struct IndexSet {
     NameToDIE function_basenames;
     NameToDIE function_fullnames;
     NameToDIE function_methods;
     NameToDIE function_selectors;
     NameToDIE objc_class_selectors;
     NameToDIE globals;
     NameToDIE types;
+    NameToDIE generic_types;
     NameToDIE namespaces;
   };
   void Index();
   void IndexUnit(DWARFUnit &unit, IndexSet &set);
 
   static void IndexUnitImpl(DWARFUnit &unit,
                             const lldb::LanguageType cu_language,
                             IndexSet &set);

lldb/source/Plugins/SymbolFile/DWARF/ManualDWARFIndex.cpp

void ManualDWARFIndex::Index() {
 
   TaskPool::RunTasks([&]() { finalize_fn(&IndexSet::function_basenames); },
                      [&]() { finalize_fn(&IndexSet::function_fullnames); },
                      [&]() { finalize_fn(&IndexSet::function_methods); },
                      [&]() { finalize_fn(&IndexSet::function_selectors); },
                      [&]() { finalize_fn(&IndexSet::objc_class_selectors); },
                      [&]() { finalize_fn(&IndexSet::globals); },
                      [&]() { finalize_fn(&IndexSet::types); },
+                     [&]() { finalize_fn(&IndexSet::generic_types); },
                      [&]() { finalize_fn(&IndexSet::namespaces); });
 }
 
 void ManualDWARFIndex::IndexUnit(DWARFUnit &unit, IndexSet &set) {
   assert(
       !unit.GetSymbolFileDWARF().GetBaseCompileUnit() &&
       "DWARFUnit associated with .dwo or .dwp should not be indexed directly");
 
for (const DWARFDebugInfoEntry &die : unit.dies()) {
     case DW_TAG_constant:
     case DW_TAG_enumeration_type:
     case DW_TAG_string_type:
     case DW_TAG_structure_type:
     case DW_TAG_subroutine_type:
     case DW_TAG_typedef:
     case DW_TAG_union_type:
     case DW_TAG_unspecified_type:
-      if (name && !is_declaration)
-        set.types.Insert(ConstString(name), ref);
-      if (mangled_cstr && !is_declaration)
+      if (name && !is_declaration) {
+        ConstString name_cs(name);
+        set.types.Insert(name_cs, ref);
+        if (Language::LanguageIsCPlusPlus(cu_language) && !name_cs.IsEmpty() &&
+            name[name_cs.GetLength() - 1] == '>') {
+          const char *angle_bracket_pos = strchr(name, '<');
+          assert(angle_bracket_pos && "missing matching angle bracket");
+          size_t generic_length = angle_bracket_pos - name;
+          set.generic_types.Insert(ConstString(name, generic_length), ref);
+        }
+      }
+      if (mangled_cstr && !is_declaration) {
         set.types.Insert(ConstString(mangled_cstr), ref);
+      }
       break;
 
     case DW_TAG_namespace:
       if (name)
         set.namespaces.Insert(ConstString(name), ref);
       break;
 
     case DW_TAG_variable:

 }
 
 void ManualDWARFIndex::GetTypes(const DWARFDeclContext &context,
                                 DIEArray &offsets) {
   Index();
   m_set.types.Find(ConstString(context[0].name), offsets);
 }
 
+void ManualDWARFIndex::GetGenericTypes(ConstString name, DIEArray &offsets) {
+  Index();
+  m_set.generic_types.Find(name, offsets);
+}
+
+void ManualDWARFIndex::GetGenericTypes(const DWARFDeclContext &context,
+                                       DIEArray &offsets) {
+  Index();
+  m_set.generic_types.Find(ConstString(context[0].name), offsets);
+}
+
 void ManualDWARFIndex::GetNamespaces(ConstString name, DIEArray &offsets) {
   Index();
   m_set.namespaces.Find(name, offsets);
 }
 
 void ManualDWARFIndex::GetFunctions(ConstString name, SymbolFileDWARF &dwarf,
                                     const CompilerDeclContext &parent_decl_ctx,
                                     uint32_t name_type_mask,

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

if (die) {
         if (types.GetSize() >= max_matches)
           break;
       }
     } else {
       m_index->ReportInvalidDIERef(die_ref, name.GetStringRef());
     }
   }
 
+  die_offsets.clear();
+  m_index->GetGenericTypes(name, die_offsets);
+  for (size_t i = 0; i < die_offsets.size(); ++i) {
+    const DIERef &die_ref = die_offsets[i];
+    DWARFDIE die = GetDIE(die_ref);
+    if (die) {
+      if (!DIEInDeclContext(parent_decl_ctx, die))
+        continue; // The containing decl contexts don't match
+      if (Type *matching_type = ResolveType(die, true, true)) {
+        types.InsertUnique(matching_type->shared_from_this());
+        if (types.GetSize() >= max_matches)
+          break;
+      }
+    } else {
+      m_index->ReportInvalidDIERef(die_ref, name.GetStringRef());
+    }
+  }
+
   // Next search through the reachable Clang modules. This only applies for
   // DWARF objects compiled with -gmodules that haven't been processed by
   // dsymutil.
   if (num_die_matches < max_matches) {
     UpdateExternalModuleListIfNeeded();
 
     for (const auto &pair : m_external_type_modules)
       if (ModuleSP external_module_sp = pair.second) 

lldb/source/Symbol/TypeMap.cpp

if (!Type::GetTypeScopeAndBasename(qualified_typename, type_scope,
                                      type_basename, type_class)) {
     type_basename = qualified_typename;
     type_scope = "";
   }
   return RemoveMismatchedTypes(type_scope, type_basename, type_class,
                                exact_match);
 }
 
+namespace {
+
+bool TypeBasenamesMatch(const std::string &type_basename,
+                        llvm::StringRef match_type_basename,
+                        bool is_instantiation) {
+  if (match_type_basename == type_basename)
+    return true;
+  // If the basenames do not match, let us see if {match_type_basename} could
+  // be an instantiation of {type_basename}.
+  if (is_instantiation)
+    return false;
+  size_t basename_size = type_basename.size();
+  if (match_type_basename.size() <= basename_size)
+    return false;
+  if (match_type_basename[basename_size] != '<')
+    return false;
+  return match_type_basename.take_front(basename_size) == type_basename;
+}
+
+} // namespace
+
 void TypeMap::RemoveMismatchedTypes(const std::string &type_scope,
                                     const std::string &type_basename,
                                     TypeClass type_class, bool exact_match) {
   // Our "collection" type currently is a std::map which doesn't have any good
   // way to iterate and remove items from the map so we currently just make a
   // new list and add all of the matching types to it, and then swap it into
   // m_types at the end
   collection matching_types;
 
   iterator pos, end = m_types.end();
 
+  bool is_instantiation = type_basename.find('<') != std::string::npos;
+
   for (pos = m_types.begin(); pos != end; ++pos) {
     Type *the_type = pos->second.get();
     bool keep_match = false;
     TypeClass match_type_class = eTypeClassAny;
 
     if (type_class != eTypeClassAny) {
       match_type_class = the_type->GetForwardCompilerType().GetTypeClass();
       if ((match_type_class & type_class) == 0)
         continue;
     }
 
     ConstString match_type_name_const_str(the_type->GetQualifiedName());
     if (match_type_name_const_str) {
       const char *match_type_name = match_type_name_const_str.GetCString();
       llvm::StringRef match_type_scope;
       llvm::StringRef match_type_basename;
       if (Type::GetTypeScopeAndBasename(match_type_name, match_type_scope,
                                         match_type_basename,
                                         match_type_class)) {
-        if (match_type_basename == type_basename) {
+        if (TypeBasenamesMatch(type_basename, match_type_basename,
+                               is_instantiation)) {
           const size_t type_scope_size = type_scope.size();
           const size_t match_type_scope_size = match_type_scope.size();
           if (exact_match || (type_scope_size == match_type_scope_size)) {
             keep_match = match_type_scope == type_scope;
           } else {
             if (match_type_scope_size > type_scope_size) {
               const size_t type_scope_pos = match_type_scope.rfind(type_scope);
               if (type_scope_pos == match_type_scope_size - type_scope_size) {
if (match_type_name_const_str) {
                 }
               }
             }
           }
         }
       } else {
         // The type we are currently looking at doesn't exists in a namespace
         // or class, so it only matches if there is no type scope...
-        keep_match = type_scope.empty() && type_basename == match_type_name;
+        keep_match = type_scope.empty() &&
+                     TypeBasenamesMatch(type_basename, match_type_name,
+                                        is_instantiation);
       }
     }
 
     if (keep_match) {
       matching_types.insert(*pos);
     }
   }
   m_types.swap(matching_types);