[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

745–746

^ Delete this comment

clang/include/clang/AST/Type.h

class AutoTypeBitfields {
     unsigned NumArgs;
   };
 
   class SubstTemplateTypeParmTypeBitfields {
     friend class SubstTemplateTypeParmType;
 
     unsigned : NumTypeBits;
 
+    unsigned HasNonCanonicalUnderlyingType : 1;
+
     // The index of the template parameter this substitution represents.
-    unsigned Index : 16;
+    unsigned Index : 15;
 
     /// 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>;
 
   Decl *ReplacedDecl;
 
   SubstTemplateTypeParmType(QualType Replacement, Decl *ReplacedDecl,
                             unsigned Index, Optional<unsigned> PackIndex);
 
 public:
   /// Gets the type that was substituted for the template
   /// parameter.
-  QualType getReplacementType() const { return getCanonicalTypeInternal(); }
+  QualType getReplacementType() const {
+    return SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType
+               ? *getTrailingObjects<QualType>()
+               : getCanonicalTypeInternal();
+  }
 
   /// Gets the templated entity that was substituted.
   Decl *getReplacedDecl() const { return ReplacedDecl; }
 
   const TemplateTypeParmDecl *getReplacedParameter() const;
 
   unsigned getIndex() const { return SubstTemplateTypeParmTypeBits.Index; }
 
void Profile(llvm::FoldingSetNodeID &ID) {
     Profile(ID, getReplacementType(), getReplacedDecl(), getIndex(),
             getPackIndex());
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID, QualType Replacement,
                       const Decl *ReplacedDecl, unsigned Index,
                       Optional<unsigned> PackIndex) {
     ID.AddPointer(ReplacedDecl);
-    ID.AddPointer(Replacement.getAsOpaquePtr());
+    Replacement.Profile(ID);
     ID.AddInteger(Index);
     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<"Index", UInt32> {
     let Read = [{ node->getIndex() }];
   }
   def : Property<"PackIndex", Optional<UInt32>> {
     let Read = [{ node->getPackIndex() }];
   }
 
   // The call to getCanonicalType here existed in ASTReader.cpp, too.
   def : Creator<[{
     return ctx.getSubstTemplateTypeParmType(
-        ctx.getCanonicalType(replacementType), replacedDecl, Index, PackIndex);
+        replacementType, replacedDecl, Index, 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(QualType Replacement,
                                          Decl *ReplacedDecl, unsigned Index,
                                          Optional<unsigned> PackIndex) const {
-  assert(Replacement.isCanonical()
-         && "replacement types must always be canonical");
-
   llvm::FoldingSetNodeID ID;
   SubstTemplateTypeParmType::Profile(ID, Replacement, ReplacedDecl, Index,
                                      PackIndex);
   void *InsertPos = nullptr;
   SubstTemplateTypeParmType *SubstParm =
       SubstTemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
 
   if (!SubstParm) {
-    SubstParm = new (*this, TypeAlignment)
+    void *Mem = Allocate(SubstTemplateTypeParmType::totalSizeToAlloc<QualType>(
+                             !Replacement.isCanonical()),
+                         TypeAlignment);
+    SubstParm = new (Mem)
         SubstTemplateTypeParmType(Replacement, ReplacedDecl, Index, PackIndex);
     Types.push_back(SubstParm);
     SubstTemplateTypeParmTypes.InsertNode(SubstParm, InsertPos);
   }
 
   return QualType(SubstParm, 0);
 }
 

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(
-      ToReplacementTypeOrErr->getCanonicalType(), *ReplacedOrErr, T->getIndex(),
+      *ToReplacementTypeOrErr, *ReplacedOrErr, T->getIndex(),
       T->getPackIndex());
 }
 
 ExpectedType ASTNodeImporter::VisitSubstTemplateTypeParmPackType(
     const SubstTemplateTypeParmPackType *T) {
   Expected<Decl *> ReplacedOrErr = import(T->getReplacedDecl());
   if (!ReplacedOrErr)
     return ReplacedOrErr.takeError();

clang/lib/AST/Type.cpp

 }
 
 SubstTemplateTypeParmType::SubstTemplateTypeParmType(
     QualType Replacement, Decl *ReplacedDecl, unsigned Index,
     Optional<unsigned> PackIndex)
     : Type(SubstTemplateTypeParm, Replacement.getCanonicalType(),
            Replacement->getDependence()),
       ReplacedDecl(ReplacedDecl) {
+  SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType =
+      Replacement != getCanonicalTypeInternal();
+  if (SubstTemplateTypeParmTypeBits.HasNonCanonicalUnderlyingType)
+    *getTrailingObjects<QualType>() = Replacement;
+
   SubstTemplateTypeParmTypeBits.Index = Index;
   SubstTemplateTypeParmTypeBits.PackIndex = PackIndex ? *PackIndex + 1 : 0;
   assert(ReplacedDecl != nullptr);
   assert(getReplacedParameter() != nullptr);
 }
 
 const TemplateTypeParmDecl *
 SubstTemplateTypeParmType::getReplacedParameter() const {

clang/lib/Sema/SemaTemplate.cpp

checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD,
   ASTContext &Context = SemaRef.getASTContext();
 
   TemplateParameterList *TPL = BTD->getTemplateParameters();
 
   // Wrap the type in substitution sugar.
   auto getSubstType = [&](QualType Replacement, unsigned IndexReplaced,
                           Optional<unsigned> PackIndexReplaced) {
     return SemaRef.Context.getSubstTemplateTypeParmType(
-        Replacement.getCanonicalType(), BTD, IndexReplaced, PackIndexReplaced);
+        Replacement, BTD, IndexReplaced, 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();