[clang] AST: SubstTemplateTypeParmType support for non-canonical underlying type

[mizvekov]

Summary

This change allows us to represent in the AST some specific
circumstances where we substitute a template parameter type
which is part of the underlying type of a previous substitution.

This presently happens in some circumstances dealing with
substitution of defaulted parameters of template template
parameters, and in some other cases during concepts substitution.

The main motivation for this change is for the future use in the
implementation of template specialization resugaring, as this will
allow us to represent a substitution with sugared types.

Signed-off-by: Matheus Izvekov <[e-mail]>

[erichkeane]

Patch generally seems OK to me. I would vastly prefer a better commit message explaining the intent here. Also, not quite sure I see the need for the extra bit?

[mizvekov]

In D132816#3799484, @erichkeane wrote:

Patch generally seems OK to me. I would vastly prefer a better commit message explaining the intent here. Also, not quite sure I see the need for the extra bit?

Well mechanically the low level intent is explained in the commit summary, and it does give some benefits without any further patches as now we can represent better in the AST some substitutions related to default arguments in template template parameters, and some other substitutions performed in concepts checking.

But the important reason is that with resugaring, this will allow us to produce a resugared type which still contains SubstNodes marking the original substitutions, otherwise we would have to wipe that out and we wouldn't be able to resugar these types again if needed.

The extra bit is for saving storage when the underlying type is already canonical, so that this patch has minimal memory usage impact.

[erichkeane]

In D132816#3799535, @mizvekov wrote:

In D132816#3799484, @erichkeane wrote:

Patch generally seems OK to me. I would vastly prefer a better commit message explaining the intent here. Also, not quite sure I see the need for the extra bit?

Well mechanically the low level intent is explained in the commit summary, and it does give some benefits without any further patches as now we can represent better in the AST some substitutions related to default arguments in template template parameters, and some other substitutions performed in concepts checking.

But the important reason is that with resugaring, this will allow us to produce a resugared type which still contains SubstNodes marking the original substitutions, otherwise we would have to wipe that out and we wouldn't be able to resugar these types again if needed.

The extra bit is for saving storage when the underlying type is already canonical, so that this patch has minimal memory usage impact.

Woops, sorry about the 'extra bit' part, that was because of a comment I had and deleted, I was suggesting at one point that the bit should be a property of the 'underlying type' (that is, determine it based on the canonicalness of the underlying type), but I think I figured out why it wouldn't be necessary.

As far as the "commit summary", the patch summary at least is empty...

[mizvekov]

In D132816#3799543, @erichkeane wrote:

As far as the "commit summary", the patch summary at least is empty...

Yeah I meant the one line title of the commit, but I will update it to include a summary with further elaboration in a bit.

[davrec]

Agree this needs a brief commit message, just explaining that previously the underlying type had to be canonical, but now it can be sugared, allowing a better/more informative representation.

clang/include/clang/AST/TypeProperties.td

741–742

^ Delete this comment

clang/include/clang/AST/Type.h

class AutoTypeBitfields {
     unsigned NumArgs;
   };
 
   class SubstTemplateTypeParmTypeBitfields {
     friend class SubstTemplateTypeParmType;
 
     unsigned : NumTypeBits;
 
+    unsigned HasNonCanonicalUnderlyingType : 1;
+
     /// Represents the index within a pack if this represents a substitution
     /// from a pack expansion. This index starts at the end of the pack and
     /// increments towards the beginning.
     /// Positive non-zero number represents the index + 1.
     /// Zero means this is not substituted from an expansion.
     unsigned PackIndex : 16;
   };
 

 
 /// Represents the result of substituting a type for a template
 /// type parameter.
 ///
 /// Within an instantiated template, all template type parameters have
 /// been replaced with these.  They are used solely to record that a
 /// type was originally written as a template type parameter;
 /// therefore they are never canonical.
-class SubstTemplateTypeParmType : public Type, public llvm::FoldingSetNode {
+class SubstTemplateTypeParmType final
+    : public Type,
+      public llvm::FoldingSetNode,
+      private llvm::TrailingObjects<SubstTemplateTypeParmType, QualType> {
   friend class ASTContext;
+  friend class llvm::TrailingObjects<SubstTemplateTypeParmType, QualType>;
 
   // The original type parameter.
   const TemplateTypeParmType *Replaced;
 
   SubstTemplateTypeParmType(const TemplateTypeParmType *Param, QualType Canon,
                             Optional<unsigned> PackIndex);
 
 public:
   /// Gets the template parameter that was substituted for.
   const TemplateTypeParmType *getReplacedParameter() const {
     return Replaced;
   }
 
   /// Gets the type that was substituted for the template
   /// parameter.
   QualType getReplacementType() const {
-    return getCanonicalTypeInternal();
+    return SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType
+               ? *getTrailingObjects<QualType>()
+               : getCanonicalTypeInternal();
   }
 
   Optional<unsigned> getPackIndex() const {
     if (SubstTemplateTypeParmTypeBits.PackIndex == 0)
       return None;
     return SubstTemplateTypeParmTypeBits.PackIndex - 1;
   }
 
   bool isSugared() const { return true; }
   QualType desugar() const { return getReplacementType(); }
 
   void Profile(llvm::FoldingSetNodeID &ID) {
     Profile(ID, getReplacedParameter(), getReplacementType(), getPackIndex());
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID,
                       const TemplateTypeParmType *Replaced,
                       QualType Replacement, Optional<unsigned> PackIndex) {
     ID.AddPointer(Replaced);
-    ID.AddPointer(Replacement.getAsOpaquePtr());
+    Replacement.Profile(ID);
     ID.AddInteger(PackIndex ? *PackIndex - 1 : 0);
   }
 
   static bool classof(const Type *T) {
     return T->getTypeClass() == SubstTemplateTypeParm;
   }
 };
 

clang/include/clang/AST/TypeProperties.td

let Class = SubstTemplateTypeParmType in {
   }
   def : Property<"replacementType", QualType> {
     let Read = [{ node->getReplacementType() }];
   }
   def : Property<"PackIndex", Optional<UInt32>> {
     let Read = [{ node->getPackIndex() }];
   }
 
   def : Creator<[{
-    // The call to getCanonicalType here existed in ASTReader.cpp, too.
     return ctx.getSubstTemplateTypeParmType(
         cast<TemplateTypeParmType>(replacedParameter),
-        ctx.getCanonicalType(replacementType), PackIndex);
+        replacementType, PackIndex);
   }]>;
 }
 
 let Class = PackExpansionType in {
   def : Property<"pattern", QualType> {
     let Read = [{ node->getPattern() }];
   }
   def : Property<"numExpansions", Optional<UInt32>> {

clang/lib/AST/ASTContext.cpp

QualType ASTContext::getBTFTagAttributedType(const BTFTypeTagAttr *BTFAttr,
   return QualType(Ty, 0);
 }
 
 /// Retrieve a substitution-result type.
 QualType
 ASTContext::getSubstTemplateTypeParmType(const TemplateTypeParmType *Parm,
                                          QualType Replacement,
                                          Optional<unsigned> PackIndex) const {
-  assert(Replacement.isCanonical()
-         && "replacement types must always be canonical");
-
   llvm::FoldingSetNodeID ID;
   SubstTemplateTypeParmType::Profile(ID, Parm, Replacement, PackIndex);
   void *InsertPos = nullptr;
   SubstTemplateTypeParmType *SubstParm
     = SubstTemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
 
   if (!SubstParm) {
-    SubstParm = new (*this, TypeAlignment)
-        SubstTemplateTypeParmType(Parm, Replacement, PackIndex);
+    void *Mem = Allocate(SubstTemplateTypeParmType::totalSizeToAlloc<QualType>(
+                             !Replacement.isCanonical()),
+                         TypeAlignment);
+    SubstParm =
+        new (Mem) SubstTemplateTypeParmType(Parm, Replacement, PackIndex);
     Types.push_back(SubstParm);
     SubstTemplateTypeParmTypes.InsertNode(SubstParm, InsertPos);
   }
 
   return QualType(SubstParm, 0);
 }
 
 /// Retrieve a

clang/lib/AST/ASTImporter.cpp

ExpectedType ASTNodeImporter::VisitSubstTemplateTypeParmType(
   if (!ReplacedOrErr)
     return ReplacedOrErr.takeError();
 
   ExpectedType ToReplacementTypeOrErr = import(T->getReplacementType());
   if (!ToReplacementTypeOrErr)
     return ToReplacementTypeOrErr.takeError();
 
   return Importer.getToContext().getSubstTemplateTypeParmType(
-      *ReplacedOrErr, ToReplacementTypeOrErr->getCanonicalType(),
-      T->getPackIndex());
+      *ReplacedOrErr, *ToReplacementTypeOrErr, T->getPackIndex());
 }
 
 ExpectedType ASTNodeImporter::VisitSubstTemplateTypeParmPackType(
     const SubstTemplateTypeParmPackType *T) {
   Expected<const TemplateTypeParmType *> ReplacedOrErr =
       import(T->getReplacedParameter());
   if (!ReplacedOrErr)
     return ReplacedOrErr.takeError();

clang/lib/AST/Type.cpp

CXXRecordDecl *InjectedClassNameType::getDecl() const {
   return cast<CXXRecordDecl>(getInterestingTagDecl(Decl));
 }
 
 IdentifierInfo *TemplateTypeParmType::getIdentifier() const {
   return isCanonicalUnqualified() ? nullptr : getDecl()->getIdentifier();
 }
 
 SubstTemplateTypeParmType::SubstTemplateTypeParmType(
-    const TemplateTypeParmType *Param, QualType Canon,
+    const TemplateTypeParmType *Param, QualType Replacement,
     Optional<unsigned> PackIndex)
-    : Type(SubstTemplateTypeParm, Canon, Canon->getDependence()),
+    : Type(SubstTemplateTypeParm, Replacement.getCanonicalType(),
+           Replacement->getDependence()),
       Replaced(Param) {
+  SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType =
+      Replacement != getCanonicalTypeInternal();
+  if (SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType)
+    *getTrailingObjects<QualType>() = Replacement;
+
   SubstTemplateTypeParmTypeBits.PackIndex = PackIndex ? *PackIndex + 1 : 0;
 }
 
 SubstTemplateTypeParmPackType::SubstTemplateTypeParmPackType(
     const TemplateTypeParmType *Param, QualType Canon,
     const TemplateArgument &ArgPack)
     : Type(SubstTemplateTypeParmPack, Canon,
            TypeDependence::DependentInstantiation |

clang/lib/Sema/SemaTemplate.cpp

checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD,
 
   // Wrap the type in substitution sugar.
   auto getSubstType = [&](QualType Replacement, unsigned IndexReplaced,
                           Optional<unsigned> PackIndexReplaced) {
     QualType TTP = SemaRef.Context.getTemplateTypeParmType(
         0, IndexReplaced, false,
         cast<TemplateTypeParmDecl>(TPL->getParam(IndexReplaced)));
     return SemaRef.Context.getSubstTemplateTypeParmType(
-        cast<TemplateTypeParmType>(TTP), Replacement.getCanonicalType(),
-        PackIndexReplaced);
+        cast<TemplateTypeParmType>(TTP), Replacement, PackIndexReplaced);
   };
 
   switch (BTD->getBuiltinTemplateKind()) {
   case BTK__make_integer_seq: {
     // Specializations of __make_integer_seq<S, T, N> are treated like
     // S<T, 0, ..., N-1>.
 
     QualType OrigType = Converted[1].getAsType();

clang/lib/Sema/TreeTransform.h

QualType TreeTransform<Derived>::TransformSubstTemplateTypeParmType(
   // Substitute into the replacement type, which itself might involve something
   // that needs to be transformed. This only tends to occur with default
   // template arguments of template template parameters.
   TemporaryBase Rebase(*this, TL.getNameLoc(), DeclarationName());
   QualType Replacement = getDerived().TransformType(T->getReplacementType());
   if (Replacement.isNull())
     return QualType();
 
-  // Always canonicalize the replacement type.
-  Replacement = SemaRef.Context.getCanonicalType(Replacement);
   QualType Result = SemaRef.Context.getSubstTemplateTypeParmType(
       T->getReplacedParameter(), Replacement, T->getPackIndex());
 
   // Propagate type-source information.
   SubstTemplateTypeParmTypeLoc NewTL
     = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
   NewTL.setNameLoc(TL.getNameLoc());
   return Result;

clang/test/AST/ast-dump-template-decls.cpp

 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar pack_index 1
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (char, short)' cdecl
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent contains_unexpanded_pack depth 0 index 0 pack
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
 } // namespace PR56099
+
+namespace subst_default_argument {
+template<class A1> class A {};
+template<template<class C1, class C2 = A<C1>> class D1, class D2> using D = D1<D2>;
+
+template<class E1, class E2> class E {};
+using test1 = D<E, int>;
+// CHECK:      TypeAliasDecl 0x{{[^ ]*}} <line:{{[1-9]+}}:1, col:23> col:7 test1 'D<subst_default_argument::E, int>':'subst_default_argument::E<int, subst_default_argument::A<int>>'
+// CHECK:      TemplateSpecializationType 0x{{[^ ]*}} 'A<int>' sugar A
+// CHECK-NEXT: |-TemplateArgument type 'int':'int'
+// CHECK-NEXT: | `-SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar
+// CHECK-NEXT: |   |-TemplateTypeParmType 0x{{[^ ]*}} 'C1' dependent depth 1 index 0
+// CHECK-NEXT: |   | `-TemplateTypeParm 0x{{[^ ]*}} 'C1'
+// CHECK-NEXT: |   `-SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar
+// CHECK-NEXT: |     |-TemplateTypeParmType 0x{{[^ ]*}} 'type-parameter-0-1' dependent depth 0 index 1
+// CHECK-NEXT: |     `-BuiltinType 0x{{[^ ]*}} 'int'
+// CHECK-NEXT: `-RecordType 0x{{[^ ]*}} 'subst_default_argument::A<int>'
+// CHECK-NEXT:   `-ClassTemplateSpecialization 0x{{[^ ]*}} 'A'
+} // namespace subst_default_argument