[lldb] Make the ClassTemplateDecl merging logic in TypeSystemClang respect template parameters

[teemperor]

Summary

DWARF doesn't describe templates itself but only actual template instantiations.
Because of that LLDB has to infer the parameters of the class template declarations
from the actual instantiations when creating the internal Clang AST from debug info

Because there is no dedicated DIE for the class template, LLDB also creates the ClassTemplateDecl
implicitly when parsing a template instantiation. To avoid creating one ClassTemplateDecls for every
instantiation, TypeSystemClang::CreateClassTemplateDecl will check if there is already a
ClassTemplateDecl in the requested DeclContext and will reuse a found fitting declaration.

The logic that checks if a found class template fits to an instantiation is currently just comparing
the name of the template. So right now we map template<typename T> struct S; to
an instantiation with the values S<1, 2, 3> even though they clearly don't belong together.

This causes crashes later on when for example the Itanium mangler's
TemplateArgManglingInfo::needExactType method tries to find fitting the class template parameter
that fits to an instantiation value. In the example above it will try to find the parameter for
the value 2 but will just trigger a boundary check when retrieving the parameter with index 1
from the class template.

There are two ways we can end up with an instantiation that doesn't fit to a class template with
the same name:

1. We have two TUs with two templates that have the same name and internal linkage.
2. A forward declared template instantiation is emitted by GCC and Clang without an empty list of parameter values.

This patch makes the check for whether a class template declaration can be reused more sophisticated by
also comparing whether the parameter values can fit to the found class template. If we can't find a fitting
class template we justcreate a second class template with the fitting parameters.

Fixes rdar://76592821

[teemperor]

• Make a variable name more expressive.

[JDevlieghere]

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

1360–1364

Is "iff" a typo or intentional (if and only if)?

1494

Would there be value in making this an lldb_assert? I.e. is this something we expect to happen?

[teemperor]

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

1360–1364

It's the "if and only if` meaning. I guess the confusion comes from not using iff in the function below. WDYT, "if" here or "iff" below?

1494

I think the decision here is the same as in my comment below. It can't happen in the current LLDB from what I can see. But if someone adds LLDB support for other template parameter types and doesn't update this code, then this will crash on the user side (but not otherwise mess with their debug session). If we keep it as an assert then we will just crash for people that have asserts enabled.

1499

I think we could argue that this should be llvm_unreachable, but we have to backport this patch to fix some test failures on the last stable branch, so I want to backport this with an assert(...); return false (mostly because I'm not sure if we don't run into some weird edge case in the Swift->Clang interop code).

I'm open llvm_unreachable or the current version on llvm.org (or maybe landing this with an assert and making it unreachable as a follow-up). @JDevlieghere thoughts?

[JDevlieghere]

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

1360–1364

Yep, that was exactly it. I'm fine with iff iff it's consistent.

1494

Then we probably want an lldb assert, so we find out when that happens even if we don't hit it in the tests (which realistically is the only place we have asserts enabled).

1499

Sounds fair. I agree that we'd want an assert on the release branch.

[teemperor]

Ping, I would like to get the bots green :)

[teemperor]

• assert -> lldbassert

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.h

bool IsValid() const {
       // Having a pack name but no packed args doesn't make sense, so mark
       // these template parameters as invalid.
       if (pack_name && !packed_args)
         return false;
       return args.size() == names.size() &&
         (!packed_args || !packed_args->packed_args);
     }
 
+    bool hasParameterPack() const { return static_cast<bool>(packed_args); }
+
     llvm::SmallVector<const char *, 2> names;
     llvm::SmallVector<clang::TemplateArgument, 2> args;
     
     const char * pack_name = nullptr;
     std::unique_ptr<TemplateParameterInfos> packed_args;
   };
 
   clang::FunctionTemplateDecl *CreateFunctionTemplateDecl(

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

if (decl_ctx)
       decl_ctx->addDecl(decl);
 
     return GetType(ast.getTagDeclType(decl));
   }
   return CompilerType();
 }
 
 namespace {
-  bool IsValueParam(const clang::TemplateArgument &argument) {
-    return argument.getKind() == TemplateArgument::Integral;
-  }
+/// Returns true iff the given TemplateArgument should be represented as an
+/// NonTypeTemplateParmDecl in the AST.
 }
 
 static TemplateParameterList *CreateTemplateParameterList(
     ASTContext &ast,
     const TypeSystemClang::TemplateParameterInfos &template_param_infos,
     llvm::SmallVector<NamedDecl *, 8> &template_param_decls) {
   const bool parameter_pack = false;
   const bool is_typename = false;
void TypeSystemClang::CreateFunctionTemplateSpecializationInfo(
     const TemplateParameterInfos &infos) {
   TemplateArgumentList *template_args_ptr =
       TemplateArgumentList::CreateCopy(func_decl->getASTContext(), infos.args);
 
   func_decl->setFunctionTemplateSpecialization(func_tmpl_decl,
                                                template_args_ptr, nullptr);
 }
 
+/// Returns true if the given template parameter can represent the given value.
+/// For example, `typename T` can represent `int` but not integral values such
+/// as `int I = 3`.
+static bool TemplateParameterAllowsValue(NamedDecl *param,
+                                         const TemplateArgument &value) {
+  if (auto *type_param = llvm::dyn_cast<TemplateTypeParmDecl>(param)) {
+    // Compare the argument kind, i.e. ensure that <typename> != <int>.
+    if (value.getKind() != TemplateArgument::Type)
+      return false;
+  } else if (auto *type_param =
+                 llvm::dyn_cast<NonTypeTemplateParmDecl>(param)) {
+    // Compare the argument kind, i.e. ensure that <typename> != <int>.
+    if (!IsValueParam(value))
+      return false;
+    // Compare the integral type, i.e. ensure that <int> != <char>.
+    if (type_param->getType() != value.getIntegralType())
+      return false;
+  } else {
+    // There is no way to create other parameter decls at the moment, so we
+    // can't reach this case during normal LLDB usage. Log that this happened
+    // and assert.
+    Log *log = lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS);
+    LLDB_LOG(log,
+             "Don't know how to compare template parameter to passed"
+             " value. Decl kind of parameter is: {0}",
+             param->getDeclKindName());
+    lldbassert(false && "Can't compare this TemplateParmDecl subclass");
+    // In release builds just fall back to marking the parameter as not
+    // accepting the value so that we don't try to fit an instantiation to a
+    // template that doesn't fit. E.g., avoid that `S<1>` is being connected to
+    // `template<typename T> struct S;`.
+    return false;
+  }
+  return true;
+}
+
+/// Returns true if the given class template declaration could produce an
+/// instantiation with the specified values.
+/// For example, `<typename T>` allows the arguments `float`, but not for
+/// example `bool, float` or `3` (as an integer parameter value).
+static bool ClassTemplateAllowsToInstantiationArgs(
+    ClassTemplateDecl *class_template_decl,
+    const TypeSystemClang::TemplateParameterInfos &instantiation_values) {
+
+  TemplateParameterList &params = *class_template_decl->getTemplateParameters();
+
+  // Save some work by iterating only once over the found parameters and
+  // calculate the information related to parameter packs.
+
+  // Contains the first pack parameter (or non if there are none).
+  llvm::Optional<NamedDecl *> pack_parameter;
+  // Contains the number of non-pack parameters.
+  size_t non_pack_params = params.size();
+  for (size_t i = 0; i < params.size(); ++i) {
+    NamedDecl *param = params.getParam(i);
+    if (param->isParameterPack()) {
+      pack_parameter = param;
+      non_pack_params = i;
+      break;
+    }
+  }
+
+  // The found template needs to have compatible non-pack template arguments.
+  // E.g., ensure that <typename, typename> != <typename>.
+  // The pack parameters are compared later.
+  if (non_pack_params != instantiation_values.args.size())
+    return false;
+
+  // Ensure that <typename...> != <typename>.
+  if (pack_parameter.hasValue() != instantiation_values.hasParameterPack())
+    return false;
+
+  // Compare the first pack parameter that was found with the first pack
+  // parameter value. The special case of having an empty parameter pack value
+  // always fits to a pack parameter.
+  // E.g., ensure that <int...> != <typename...>.
+  if (pack_parameter && !instantiation_values.packed_args->args.empty() &&
+      !TemplateParameterAllowsValue(
+          *pack_parameter, instantiation_values.packed_args->args.front()))
+    return false;
+
+  // Compare all the non-pack parameters now.
+  // E.g., ensure that <int> != <long>.
+  for (const auto pair : llvm::zip_first(instantiation_values.args, params)) {
+    const TemplateArgument &passed_arg = std::get<0>(pair);
+    NamedDecl *found_param = std::get<1>(pair);
+    if (!TemplateParameterAllowsValue(found_param, passed_arg))
+      return false;
+  }
+
+  return class_template_decl;
+}
+
 ClassTemplateDecl *TypeSystemClang::CreateClassTemplateDecl(
     DeclContext *decl_ctx, OptionalClangModuleID owning_module,
     lldb::AccessType access_type, const char *class_name, int kind,
     const TemplateParameterInfos &template_param_infos) {
   ASTContext &ast = getASTContext();
 
   ClassTemplateDecl *class_template_decl = nullptr;
   if (decl_ctx == nullptr)
     decl_ctx = ast.getTranslationUnitDecl();
 
   IdentifierInfo &identifier_info = ast.Idents.get(class_name);
   DeclarationName decl_name(&identifier_info);
 
+  // Search the AST for an existing ClassTemplateDecl that could be reused.
   clang::DeclContext::lookup_result result = decl_ctx->lookup(decl_name);
-
   for (NamedDecl *decl : result) {
     class_template_decl = dyn_cast<clang::ClassTemplateDecl>(decl);
-    if (class_template_decl)
-      return class_template_decl;
+    if (!class_template_decl)
+      continue;
+    // The class template has to be able to represents the instantiation
+    // values we received. Without this we might end up putting an instantiation
+    // with arguments such as <int, int> to a template such as:
+    //     template<typename T> struct S;
+    // Connecting the instantiation to an incompatible template could cause
+    // problems later on.
+    if (!ClassTemplateAllowsToInstantiationArgs(class_template_decl,
+                                                template_param_infos))
+      continue;
   }
 
   llvm::SmallVector<NamedDecl *, 8> template_param_decls;
 
   TemplateParameterList *template_param_list = CreateTemplateParameterList(
       ast, template_param_infos, template_param_decls);
 
   CXXRecordDecl *template_cxx_decl = CXXRecordDecl::CreateDeserialized(ast, 0);

lldb/test/API/lang/cpp/forward-declared-template-specialization/Makefile

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

lldb/test/API/lang/cpp/forward-declared-template-specialization/TestCppForwardDeclaredTemplateSpecialization.py

+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+class TestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def test(self):
+        """
+        Tests a forward declared template and a normal template in the same
+        executable. GCC/Clang emit very limited debug information for forward
+        declared templates that might trip up LLDB.
+        """
+        self.build()
+        lldbutil.run_to_source_breakpoint(self, "// break here", lldb.SBFileSpec("main.cpp"))
+
+        self.expect_expr("a; b", result_type="Temp<float>")

lldb/test/API/lang/cpp/forward-declared-template-specialization/main.cpp

+// Forward declare a template and a specialization;
+template <typename T> class Temp;
+template <> class Temp<int>;
+
+// Force that debug informatin for the specialization is emitted.
+// Clang and GCC will create debug information that lacks any description
+// of the template argument 'int'.
+Temp<int> *a;
+
+// Define the template and create an implicit instantiation.
+template <typename T> class Temp { int f; };
+Temp<float> b;
+
+int main() {
+  return 0; // break here
+}

lldb/test/API/lang/cpp/incompatible-class-templates/Makefile

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

lldb/test/API/lang/cpp/incompatible-class-templates/TestCppIncompatibleClassTemplates.py

+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+class TestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def test(self):
+        """
+        Test debugging a binary that has two templates with the same name
+        but different template parameters.
+        """
+        self.build()
+        lldbutil.run_to_source_breakpoint(self, "// break here", lldb.SBFileSpec("main.cpp"))
+
+        # Try using both templates in the same expression. This shouldn't crash.
+        self.expect_expr("Template1.x + Template2.x", result_type="int")

lldb/test/API/lang/cpp/incompatible-class-templates/main.cpp

+int other();
+
+namespace {
+template <typename T1> struct Temp { int x; };
+// This emits the 'Temp' template in this TU.
+Temp<float> Template1;
+} // namespace
+
+int main() {
+  return Template1.x + other(); // break here
+}

lldb/test/API/lang/cpp/incompatible-class-templates/other.cpp

+namespace {
+template <typename T1, typename T2> struct Temp { int x; };
+// This emits the 'Temp' template from this TU.
+Temp<int, float> Template2;
+} // namespace
+
+int other() { return Template2.x; }

lldb/unittests/Symbol/TestTypeSystemClang.cpp

EXPECT_EQ(m_ast->GetTypeTemplateArgument(t.GetOpaqueQualType(), 1),
               CompilerType());
     auto result = m_ast->GetIntegralTemplateArgument(t.GetOpaqueQualType(), 1);
     ASSERT_NE(llvm::None, result);
     EXPECT_EQ(arg, result->value);
     EXPECT_EQ(int_type, result->type);
   }
 }
 
+class TestCreateClassTemplateDecl : public TestTypeSystemClang {
+protected:
+  /// The class templates created so far by the Expect* functions below.
+  llvm::DenseSet<ClassTemplateDecl *> m_created_templates;
+
+  /// Utility function for creating a class template.
+  ClassTemplateDecl *
+  CreateClassTemplate(const TypeSystemClang::TemplateParameterInfos &infos) {
+    ClassTemplateDecl *decl = m_ast->CreateClassTemplateDecl(
+        m_ast->GetTranslationUnitDecl(), OptionalClangModuleID(), eAccessPublic,
+        "foo", TTK_Struct, infos);
+    return decl;
+  }
+
+  /// Creates a new class template with the given template parameters.
+  /// Asserts that a new ClassTemplateDecl is created.
+  /// \param description The gtest scope string that should describe the input.
+  /// \param infos The template parameters that the class template should have.
+  /// \returns The created ClassTemplateDecl.
+  ClassTemplateDecl *
+  ExpectNewTemplate(std::string description,
+                    const TypeSystemClang::TemplateParameterInfos &infos) {
+    SCOPED_TRACE(description);
+    ClassTemplateDecl *first_template = CreateClassTemplate(infos);
+    // A new template should have been created.
+    EXPECT_FALSE(m_created_templates.contains(first_template))
+        << "Didn't create new class template but reused this existing decl:\n"
+        << ClangUtil::DumpDecl(first_template);
+    m_created_templates.insert(first_template);
+
+    // Creating a new template with the same arguments should always return
+    // the template created above.
+    ClassTemplateDecl *second_template = CreateClassTemplate(infos);
+    EXPECT_EQ(first_template, second_template)
+        << "Second attempt to create class template didn't reuse first decl:\n"
+        << ClangUtil::DumpDecl(first_template) << "\nInstead created/reused:\n"
+        << ClangUtil::DumpDecl(second_template);
+    return first_template;
+  }
+
+  /// Tries to create a new class template but asserts that an existing class
+  /// template in the current AST is reused (in contract so a new class
+  /// template being created).
+  /// \param description The gtest scope string that should describe the input.
+  /// \param infos The template parameters that the class template should have.
+  void
+  ExpectReusedTemplate(std::string description,
+                       const TypeSystemClang::TemplateParameterInfos &infos,
+                       ClassTemplateDecl *expected) {
+    SCOPED_TRACE(description);
+    ClassTemplateDecl *td = CreateClassTemplate(infos);
+    EXPECT_EQ(td, expected)
+        << "Created/reused class template is:\n"
+        << ClangUtil::DumpDecl(td) << "\nExpected to reuse:\n"
+        << ClangUtil::DumpDecl(expected);
+  }
+};
+
+TEST_F(TestCreateClassTemplateDecl, FindExistingTemplates) {
+  // This tests the logic in TypeSystemClang::CreateClassTemplateDecl that
+  // decides whether an existing ClassTemplateDecl in the AST can be reused.
+  // The behaviour should follow the C++ rules for redeclaring templates
+  // (e.g., parameter names can be changed/omitted.)
+
+  // This describes a class template *instantiation* from which we will infer
+  // the structure of the class template.
+  TypeSystemClang::TemplateParameterInfos infos;
+
+  // Test an empty template parameter list: <>
+  ExpectNewTemplate("<>", infos);
+
+  // Test that <typename T> with T = int creates a new template.
+  infos.names = {"T"};
+  infos.args = {TemplateArgument(m_ast->getASTContext().IntTy)};
+  ClassTemplateDecl *single_type_arg = ExpectNewTemplate("<typename T>", infos);
+
+  // Test that changing the parameter name doesn't create a new class template.
+  infos.names = {"A"};
+  ExpectReusedTemplate("<typename A> (A = int)", infos, single_type_arg);
+
+  // Test that changing the used type doesn't create a new class template.
+  infos.args = {TemplateArgument(m_ast->getASTContext().FloatTy)};
+  ExpectReusedTemplate("<typename A> (A = float)", infos, single_type_arg);
+
+  // Test that <typename A, signed char I> creates a new template with A = int
+  // and I = 47;
+  infos.names.push_back("I");
+  infos.args.push_back(TemplateArgument(m_ast->getASTContext(),
+                                        llvm::APSInt(llvm::APInt(8, 47)),
+                                        m_ast->getASTContext().SignedCharTy));
+  ClassTemplateDecl *type_and_char_value =
+      ExpectNewTemplate("<typename A, signed char I> (I = 47)", infos);
+
+  // Change the value of the I parameter to 123. The previously created
+  // class template should still be reused.
+  infos.args.pop_back();
+  infos.args.push_back(TemplateArgument(m_ast->getASTContext(),
+                                        llvm::APSInt(llvm::APInt(8, 123)),
+                                        m_ast->getASTContext().SignedCharTy));
+  ExpectReusedTemplate("<typename A, signed char I> (I = 123)", infos,
+                       type_and_char_value);
+
+  // Change the type of the I parameter to int so we have <typename A, int I>.
+  // The class template from above can't be reused.
+  infos.args.pop_back();
+  infos.args.push_back(TemplateArgument(m_ast->getASTContext(),
+                                        llvm::APSInt(llvm::APInt(32, 47)),
+                                        m_ast->getASTContext().IntTy));
+  ExpectNewTemplate("<typename A, int I> (I = 123)", infos);
+
+  // Test a second type parameter will also cause a new template to be created.
+  // We now have <typename A, int I, typename B>.
+  infos.names.push_back("B");
+  infos.args.push_back(TemplateArgument(m_ast->getASTContext().IntTy));
+  ClassTemplateDecl *type_and_char_value_and_type =
+      ExpectNewTemplate("<typename A, int I, typename B>", infos);
+
+  // Remove all the names from the parameters which shouldn't influence the
+  // way the templates get merged.
+  infos.names = {"", "", ""};
+  ExpectReusedTemplate("<typename, int, typename>", infos,
+                       type_and_char_value_and_type);
+}
+
+TEST_F(TestCreateClassTemplateDecl, FindExistingTemplatesWithParameterPack) {
+  // The same as FindExistingTemplates but for templates with parameter packs.
+
+  TypeSystemClang::TemplateParameterInfos infos;
+  infos.packed_args =
+      std::make_unique<TypeSystemClang::TemplateParameterInfos>();
+  infos.packed_args->names = {"", ""};
+  infos.packed_args->args = {TemplateArgument(m_ast->getASTContext().IntTy),
+                             TemplateArgument(m_ast->getASTContext().IntTy)};
+  ClassTemplateDecl *type_pack =
+      ExpectNewTemplate("<typename ...> (int, int)", infos);
+
+  // Special case: An instantiation for a parameter pack with no values fits
+  // to whatever class template we find. There isn't enough information to
+  // do an actual comparison here.
+  infos.packed_args =
+      std::make_unique<TypeSystemClang::TemplateParameterInfos>();
+  ExpectReusedTemplate("<...> (no values in pack)", infos, type_pack);
+
+  // Change the type content of pack type values.
+  infos.packed_args->names = {"", ""};
+  infos.packed_args->args = {TemplateArgument(m_ast->getASTContext().IntTy),
+                             TemplateArgument(m_ast->getASTContext().LongTy)};
+  ExpectReusedTemplate("<typename ...> (int, long)", infos, type_pack);
+
+  // Change the number of pack values.
+  infos.packed_args->args = {TemplateArgument(m_ast->getASTContext().IntTy)};
+  ExpectReusedTemplate("<typename ...> (int)", infos, type_pack);
+
+  // The names of the pack values shouldn't matter.
+  infos.packed_args->names = {"A", "B"};
+  ExpectReusedTemplate("<typename ...> (int)", infos, type_pack);
+
+  // Changing the kind of template argument will create a new template.
+  infos.packed_args->args = {TemplateArgument(m_ast->getASTContext(),
+                                              llvm::APSInt(llvm::APInt(32, 1)),
+                                              m_ast->getASTContext().IntTy)};
+  ClassTemplateDecl *int_pack = ExpectNewTemplate("<int ...> (int = 1)", infos);
+
+  // Changing the value of integral parameters will not create a new template.
+  infos.packed_args->args = {TemplateArgument(
+      m_ast->getASTContext(), llvm::APSInt(llvm::APInt(32, 123)),
+      m_ast->getASTContext().IntTy)};
+  ExpectReusedTemplate("<int ...> (int = 123)", infos, int_pack);
+
+  // Changing the integral type will create a new template.
+  infos.packed_args->args = {TemplateArgument(m_ast->getASTContext(),
+                                              llvm::APSInt(llvm::APInt(64, 1)),
+                                              m_ast->getASTContext().LongTy)};
+  ExpectNewTemplate("<long ...> (long = 1)", infos);
+
+  // Prependinding a non-pack parameter will create a new template.
+  infos.names = {"T"};
+  infos.args = {TemplateArgument(m_ast->getASTContext().IntTy)};
+  ExpectNewTemplate("<typename T, long...> (T = int, long = 1)", infos);
+}
+
 TEST_F(TestTypeSystemClang, OnlyPackName) {
   TypeSystemClang::TemplateParameterInfos infos;
   infos.pack_name = "A";
   EXPECT_FALSE(infos.IsValid());
 }
 
 static QualType makeConstInt(clang::ASTContext &ctxt) {
   QualType result(ctxt.IntTy);