clang: fix early substitution of alias templates

[mizvekov]

Summary

When substituting alias templates, we stop bumping up template
parameters below current substitution level.

Fixes PR55886.

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

[mizvekov]

.

[mizvekov]

.

[mizvekov]

.

[mizvekov]

.

[mizvekov]

@rsmith , I have marked the few spots where the change is meaningful.

clang/include/clang/Sema/Template.h

515–524

mark

652–671

mark

clang/lib/Sema/SemaTemplateInstantiate.cpp

931–941

mark

1195–1210

mark

1864

mark

clang/lib/Sema/SemaTemplateInstantiateDecl.cpp

2763

mark

2917–2922

mark

3055–3061

mark

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

124

mark

[mizvekov]

clang/lib/Sema/SemaTemplateInstantiateDecl.cpp

1031

mark

[mizvekov]

.

[rsmith]

clang/lib/Sema/SemaTemplateInstantiate.cpp

1864

Instead of adding the new EarlySubstitution flag and wiring it through everywhere, can you use the existing MultiLevelTemplateArgumentList::getNewDepth function? That already handles the case of a depth that's within the number of retained outer levels. We might need to set the number of retained outer levels properly when doing alias template substitution; I'm not sure if we do so currently and I suspect we don't.

[mizvekov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

1864

I think we do set the number of outer levels correctly when substituting within the type of alias templates, circa SemaTemplate.cpp:3718:

// Only substitute for the innermost template argument list.
MultiLevelTemplateArgumentList TemplateArgLists;
TemplateArgLists.addOuterTemplateArguments(&StackTemplateArgs);
TemplateArgLists.addOuterRetainedLevels(
    AliasTemplate->getTemplateParameters()->getDepth());

What the flag was done to deal with is what happens in TemplateDeclInstantiator::VisitTypeAliasTemplateDecl, when replacing just the inner level. We need to substitute there without changing any depths, including the template parameters of the alias itself, and I could not find a way to do that without extending it with the new flag.

Anyway, I will think about this again.
I ended up finding another test case which this patch only partially helps, so I have been back investigating this problem again: https://godbolt.org/z/9fGb1KKvq

template <typename... As> struct Y;
template <typename ...Bs> using Z = Y<Bs...>;
template <typename ...Cs> struct foo {
  template <typename ...Ds> using bind = Z<Ds..., Cs...>;
};
using U = foo<int>::bind<char>;

[mizvekov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

1864

Though that last test case seems actually to be a wrong index problem, not wrong depth.

[mizvekov]

• much smaller patch, puts the new flag as a mutable member of MultiLevelTemplateArgumentList

[mizvekov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

1864

That last new test case hits an unrelated problem besides this one, so I will deal with it in a separate patch.

[mizvekov]

rebase

[mizvekov]

rebase

clang/include/clang/Sema/Template.h

class MultiLevelTemplateArgumentList {
     SmallVector<ArgList, 4> TemplateArgumentLists;
 
     /// The number of outer levels of template arguments that are not
     /// being substituted.
     unsigned NumRetainedOuterLevels = 0;
 
     /// The kind of substitution described by this argument list.
     TemplateSubstitutionKind Kind = TemplateSubstitutionKind::Specialization;
+    mutable bool EarlySubstitution = false;
+
+    class SubstitutionRAII {
+      bool *EarlySubstitution, OldEarlySubstitution;
+      friend class MultiLevelTemplateArgumentList;
+
+      SubstitutionRAII(bool &EarlySubstitution, bool NewEarlySubstitution)
+          : EarlySubstitution(&EarlySubstitution),
+            OldEarlySubstitution(
+                std::exchange(EarlySubstitution, NewEarlySubstitution)) {}
+
+    public:
+      SubstitutionRAII(SubstitutionRAII &&other)
+          : EarlySubstitution(std::exchange(other.EarlySubstitution,
+                                            &other.OldEarlySubstitution)),
+            OldEarlySubstitution(other.OldEarlySubstitution) {}
+      SubstitutionRAII(const SubstitutionRAII &) = delete;
+      SubstitutionRAII &operator=(const SubstitutionRAII &) = delete;
+      ~SubstitutionRAII() { *EarlySubstitution = OldEarlySubstitution; }
+    };
 
   public:
     /// Construct an empty set of template argument lists.
     MultiLevelTemplateArgumentList() = default;
 
     /// Construct a single-level template argument list.
     explicit
     MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
public:
 
     unsigned getNumRetainedOuterLevels() const {
       return NumRetainedOuterLevels;
     }
 
     /// Determine how many of the \p OldDepth outermost template parameter
     /// lists would be removed by substituting these arguments.
     unsigned getNewDepth(unsigned OldDepth) const {
-      if (OldDepth < NumRetainedOuterLevels)
-        return OldDepth;
-      if (OldDepth < getNumLevels())
-        return NumRetainedOuterLevels;
-      return OldDepth - TemplateArgumentLists.size();
+      return EarlySubstitution ? OldDepth
+                               : OldDepth - getNumSubstitutedLevels();
     }
 
     /// Retrieve the template argument at a given depth and index.
     const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
       assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
       assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
       return TemplateArgumentLists[getNumLevels() - Depth - 1][Index];
     }
public:
     void addOuterRetainedLevels(unsigned Num) {
       NumRetainedOuterLevels += Num;
     }
 
     /// Retrieve the innermost template argument list.
     const ArgList &getInnermost() const {
       return TemplateArgumentLists.front();
     }
+
+    /// Get a scope object to perform early substitution.
+    SubstitutionRAII getEarlySubstitutionRAII() const {
+      return SubstitutionRAII(EarlySubstitution, true);
+    }
+
+    /// Get a scope object to perform late substitution.
+    SubstitutionRAII getLateSubstitutionRAII() const {
+      return SubstitutionRAII(EarlySubstitution, false);
+    }
   };
 
   /// The context in which partial ordering of function templates occurs.
   enum TPOC {
     /// Partial ordering of function templates for a function call.
     TPOC_Call,
 
     /// Partial ordering of function templates for a call to a
class TemplateDeclInstantiator
     /// A list of out-of-line variable template partial
     /// specializations that will need to be instantiated after the
     /// enclosing variable's instantiation is complete.
     /// FIXME: Verify that this is needed.
     SmallVector<
         std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
     OutOfLineVarPartialSpecs;
 
   public:
     TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
                              const MultiLevelTemplateArgumentList &TemplateArgs)
         : SemaRef(SemaRef),
           SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
           Owner(Owner), TemplateArgs(TemplateArgs) {}
 
 // Define all the decl visitors using DeclNodes.inc
 #define DECL(DERIVED, BASE) \
     Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D);
 #define ABSTRACT_DECL(DECL)
 
 // Decls which never appear inside a class or function.
 #define OBJCCONTAINER(DERIVED, BASE)
 #define FILESCOPEASM(DERIVED, BASE)
 #define IMPORT(DERIVED, BASE)
 #define EXPORT(DERIVED, BASE)
 #define LINKAGESPEC(DERIVED, BASE)
InstantiateVarTemplatePartialSpecialization(
         VarTemplateDecl *VarTemplate,
         VarTemplatePartialSpecializationDecl *PartialSpec);
     void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
 
   private:
     template<typename T>
     Decl *instantiateUnresolvedUsingDecl(T *D,
                                          bool InstantiatingPackElement = false);
   };
 
 } // namespace clang
 
 #endif // LLVM_CLANG_SEMA_TEMPLATE_H

clang/lib/Sema/SemaTemplateInstantiate.cpp

 //===----------------------------------------------------------------------===/
 // Template Instantiation for Types
 //===----------------------------------------------------------------------===/
 namespace {
   class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
     const MultiLevelTemplateArgumentList &TemplateArgs;
     SourceLocation Loc;
     DeclarationName Entity;
 
   public:
     typedef TreeTransform<TemplateInstantiator> inherited;
 
     TemplateInstantiator(Sema &SemaRef,
                          const MultiLevelTemplateArgumentList &TemplateArgs,
                          SourceLocation Loc,
                          DeclarationName Entity)
       : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
         Entity(Entity) { }
 
     /// Determine whether the given type \p T has already been
     /// transformed.
     ///
     /// For the purposes of template instantiation, a type has already been
     /// transformed if it is NULL or if it is not dependent.
     bool AlreadyTransformed(QualType T);
 
     /// Returns the location of the entity being instantiated, if known.
     SourceLocation getBaseLocation() { return Loc; }
 
     /// Returns the name of the entity being instantiated, if any.
     DeclarationName getBaseEntity() { return Entity; }
 
     /// Sets the "base" location and entity when that
     /// information is known based on another transformation.
     void setBase(SourceLocation Loc, DeclarationName Entity) {
       this->Loc = Loc;
       this->Entity = Entity;
     }
 
-    unsigned TransformTemplateDepth(unsigned Depth) {
-      return TemplateArgs.getNewDepth(Depth);
+    unsigned TransformTemplateDepth(unsigned OldDepth) {
+      if (OldDepth < TemplateArgs.getNumRetainedOuterLevels())
+        return OldDepth;
+      if (OldDepth < TemplateArgs.getNumLevels())
+        return TemplateArgs.getNumRetainedOuterLevels();
+      return OldDepth - TemplateArgs.getNumSubstitutedLevels();
     }
 
     bool TryExpandParameterPacks(SourceLocation EllipsisLoc,
                                  SourceRange PatternRange,
                                  ArrayRef<UnexpandedParameterPack> Unexpanded,
                                  bool &ShouldExpand, bool &RetainExpansion,
                                  Optional<unsigned> &NumExpansions) {
       return getSema().CheckParameterPacksForExpansion(EllipsisLoc,
public:
     }
 
     TemplateParameterList *TransformTemplateParameterList(
                               TemplateParameterList *OrigTPL)  {
       if (!OrigTPL || !OrigTPL->size()) return OrigTPL;
 
       DeclContext *Owner = OrigTPL->getParam(0)->getDeclContext();
       TemplateDeclInstantiator  DeclInstantiator(getSema(),
                         /* DeclContext *Owner */ Owner, TemplateArgs);
       return DeclInstantiator.SubstTemplateParams(OrigTPL);
     }
 
     concepts::TypeRequirement *
     TransformTypeRequirement(concepts::TypeRequirement *Req);
     concepts::ExprRequirement *
     TransformExprRequirement(concepts::ExprRequirement *Req);
     concepts::NestedRequirement *
     TransformNestedRequirement(concepts::NestedRequirement *Req);
 
   private:
     ExprResult transformNonTypeTemplateParmRef(NonTypeTemplateParmDecl *parm,
                                                SourceLocation loc,
                                                TemplateArgument arg);
   };
 }
 
 bool TemplateInstantiator::AlreadyTransformed(QualType T) {
   if (T.isNull())
     return true;
 
   if (T->isInstantiationDependentType() || T->isVariablyModifiedType())
     return false;
TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
   // template we are instantiating). Create a new template type
   // parameter with the template "level" reduced by one.
   TemplateTypeParmDecl *NewTTPDecl = nullptr;
   if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
     NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
                                   TransformDecl(TL.getNameLoc(), OldTTPDecl));
 
   QualType Result = getSema().Context.getTemplateTypeParmType(
-      T->getDepth() - TemplateArgs.getNumSubstitutedLevels(), T->getIndex(),
+      TemplateArgs.getNewDepth(T->getDepth()), T->getIndex(),
       T->isParameterPack(), NewTTPDecl);
   TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
   NewTL.setNameLoc(TL.getNameLoc());
   return Result;
 }
 
 QualType
 TemplateInstantiator::TransformSubstTemplateTypeParmPackType(
                                                             TypeLocBuilder &TLB,

clang/lib/Sema/SemaTemplateInstantiateDecl.cpp

Decl *TemplateDeclInstantiator::VisitTypeAliasDecl(TypeAliasDecl *D) {
   return Typedef;
 }
 
 Decl *
 TemplateDeclInstantiator::VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D) {
   // Create a local instantiation scope for this type alias template, which
   // will contain the instantiations of the template parameters.
   LocalInstantiationScope Scope(SemaRef);
 
-  TemplateParameterList *TempParams = D->getTemplateParameters();
-  TemplateParameterList *InstParams = SubstTemplateParams(TempParams);
+  auto EarlySubstitutionScope = TemplateArgs.getEarlySubstitutionRAII();
+  TemplateParameterList *InstParams =
+      SubstTemplateParams(D->getTemplateParameters());
   if (!InstParams)
     return nullptr;
 
   TypeAliasDecl *Pattern = D->getTemplatedDecl();
 
   TypeAliasTemplateDecl *PrevAliasTemplate = nullptr;
   if (getPreviousDeclForInstantiation<TypedefNameDecl>(Pattern)) {
     DeclContext::lookup_result Found = Owner->lookup(Pattern->getDeclName());
if (D->isPackExpansion() && !D->isExpandedParameterPack()) {
                           TC->getConceptNameInfo().getEndLoc()),
               Unexpanded, TemplateArgs, Expand, RetainExpansion, NumExpanded))
         return nullptr;
     }
   }
 
   TemplateTypeParmDecl *Inst = TemplateTypeParmDecl::Create(
       SemaRef.Context, Owner, D->getBeginLoc(), D->getLocation(),
-      D->getDepth() - TemplateArgs.getNumSubstitutedLevels(), D->getIndex(),
+      TemplateArgs.getNewDepth(D->getDepth()), D->getIndex(),
       D->getIdentifier(), D->wasDeclaredWithTypename(), D->isParameterPack(),
       D->hasTypeConstraint(), NumExpanded);
 
   Inst->setAccess(AS_public);
   Inst->setImplicit(D->isImplicit());
   if (auto *TC = D->getTypeConstraint()) {
     if (!D->isImplicit()) {
       // Invented template parameter type constraints will be instantiated with
       // the corresponding auto-typed parameter as it might reference other
if (T.isNull()) {
       Invalid = true;
     }
   }
 
   NonTypeTemplateParmDecl *Param;
   if (IsExpandedParameterPack)
     Param = NonTypeTemplateParmDecl::Create(
         SemaRef.Context, Owner, D->getInnerLocStart(), D->getLocation(),
-        D->getDepth() - TemplateArgs.getNumSubstitutedLevels(),
-        D->getPosition(), D->getIdentifier(), T, DI, ExpandedParameterPackTypes,
+        TemplateArgs.getNewDepth(D->getDepth()), D->getPosition(),
+        D->getIdentifier(), T, DI, ExpandedParameterPackTypes,
         ExpandedParameterPackTypesAsWritten);
   else
     Param = NonTypeTemplateParmDecl::Create(
         SemaRef.Context, Owner, D->getInnerLocStart(), D->getLocation(),
-        D->getDepth() - TemplateArgs.getNumSubstitutedLevels(),
-        D->getPosition(), D->getIdentifier(), T, D->isParameterPack(), DI);
+        TemplateArgs.getNewDepth(D->getDepth()), D->getPosition(),
+        D->getIdentifier(), T, D->isParameterPack(), DI);
 
   if (AutoTypeLoc AutoLoc = DI->getTypeLoc().getContainedAutoTypeLoc())
     if (AutoLoc.isConstrained())
       if (SemaRef.AttachTypeConstraint(
               AutoLoc, Param,
               IsExpandedParameterPack
                 ? DI->getTypeLoc().getAs<PackExpansionTypeLoc>()
                     .getEllipsisLoc()
if (D->isExpandedParameterPack()) {
     if (!InstParams)
       return nullptr;
   }
 
   // Build the template template parameter.
   TemplateTemplateParmDecl *Param;
   if (IsExpandedParameterPack)
     Param = TemplateTemplateParmDecl::Create(
         SemaRef.Context, Owner, D->getLocation(),
-        D->getDepth() - TemplateArgs.getNumSubstitutedLevels(),
-        D->getPosition(), D->getIdentifier(), InstParams, ExpandedParams);
+        TemplateArgs.getNewDepth(D->getDepth()), D->getPosition(),
+        D->getIdentifier(), InstParams, ExpandedParams);
   else
     Param = TemplateTemplateParmDecl::Create(
         SemaRef.Context, Owner, D->getLocation(),
-        D->getDepth() - TemplateArgs.getNumSubstitutedLevels(),
-        D->getPosition(), D->isParameterPack(), D->getIdentifier(), InstParams);
+        TemplateArgs.getNewDepth(D->getDepth()), D->getPosition(),
+        D->isParameterPack(), D->getIdentifier(), InstParams);
   if (D->hasDefaultArgument() && !D->defaultArgumentWasInherited()) {
     NestedNameSpecifierLoc QualifierLoc =
         D->getDefaultArgument().getTemplateQualifierLoc();
     QualifierLoc =
         SemaRef.SubstNestedNameSpecifierLoc(QualifierLoc, TemplateArgs);
     TemplateName TName = SemaRef.SubstTemplateName(
         QualifierLoc, D->getDefaultArgument().getArgument().getAsTemplate(),
         D->getDefaultArgument().getTemplateNameLoc(), TemplateArgs);
if (Invalid)
     return nullptr;
 
   // FIXME: Concepts: Substitution into requires clause should only happen when
   // checking satisfaction.
   Expr *InstRequiresClause = nullptr;
   if (Expr *E = L->getRequiresClause()) {
     EnterExpressionEvaluationContext ConstantEvaluated(
         SemaRef, Sema::ExpressionEvaluationContext::Unevaluated);
+    auto LateSubstitutionScope = TemplateArgs.getLateSubstitutionRAII();
     ExprResult Res = SemaRef.SubstExpr(E, TemplateArgs);
     if (Res.isInvalid() || !Res.isUsable()) {
       return nullptr;
     }
     InstRequiresClause = Res.get();
   }
 
   TemplateParameterList *InstL

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

 using type2 = typename C<int>::type1<void>;
 // CHECK:      TypeAliasDecl 0x{{[^ ]*}} <line:[[@LINE-1]]:1, col:42> col:7 type2 'typename C<int>::type1<void>':'void (int)'
 // CHECK-NEXT: ElaboratedType 0x{{[^ ]*}} 'typename C<int>::type1<void>' sugar
 // CHECK-NEXT: TemplateSpecializationType 0x{{[^ ]*}} 'type1<void>' sugar alias type1
 // CHECK-NEXT: TemplateArgument type 'void'
 // CHECK-NEXT: BuiltinType 0x{{[^ ]*}} 'void'
 // CHECK-NEXT: FunctionProtoType 0x{{[^ ]*}} 'void (int)' cdecl
 // CHECK-NEXT: SubstTemplateTypeParmType 0x{{[^ ]*}} 'void' sugar
-// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent depth 0 index 0
+// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent depth 1 index 0
 // CHECK-NEXT: TemplateTypeParm 0x{{[^ ]*}} 'U'
 // CHECK-NEXT: BuiltinType 0x{{[^ ]*}} 'void'
 // CHECK-NEXT: SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent depth 0 index 0
 } // namespace PR55886
 
 namespace PR56099 {
 template <typename... As> struct Y;

 };
 using t2 = D<float, char>::B<int, short>;
 // CHECK:      TemplateSpecializationType 0x{{[^ ]*}} 'B<int, short>' sugar alias B
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (int (*)(float, int), int (*)(char, short))' cdecl
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (float, int)' cdecl
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'float' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent contains_unexpanded_pack depth 0 index 0 pack
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar pack_index 0
-// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
+// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 1 index 0 pack
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (char, short)' cdecl
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar pack_index 1
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent contains_unexpanded_pack depth 0 index 0 pack
 // CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar pack_index 1
-// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
+// CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 1 index 0 pack
 } // namespace PR56099