[clang] extend getCommonSugaredType to merge sugar nodes

[mizvekov]

Summary

This continues D111283 by extending the getCommonSugaredType
implementation to also merge non-canonical type nodes.

We merge these nodes by going up starting from the canonical
node, calculating their merged properties on the way.

If we reach a pair that is too different, or which we could not
otherwise unify, we bail out and don't try to keep going on to
the next pair, in effect striping out all the remaining top-level
sugar nodes. This avoids mismatching 'companion' nodes, such as
ElaboratedType, so that they don't end up elaborating some other
unrelated thing.

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

[rsmith]

clang/lib/AST/ASTContext.cpp

12733

Typo "inefficient" (multiple instances)

12749

Should we bail out if this happens, as we do in the other cases above?

12774–12775

These template arguments might in general be unrelated. Is that a problem here? Eg:

template<typename T, template<typename> typename Predicate> concept satisfies = Predicate<T>::value;
auto f(bool c) {
  satisfies<std::is_trivially_copyable> auto x = 0;
  satisfies<std::is_integral> auto y = 0;
  // Common sugar here should presumably be "unconstrained auto deduced as `int`".
  return c ? x : y;
}

12777–12778

Instantiation-dependence and "contains unexpanded parameter pack" can depend on which sugar we choose to preserve. I think you strictly-speaking would need to recompute these based on the sugar we end up with rather than inheriting them from AX.

12846–12848

Can avoid a repeated check here.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12749

I think this means what we are trying to merge is unrelated, so yes. I just didn't come up with a test case yet :)

12774–12775

Right, yes, we should bail out in that case as well I think.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12749

I added the handling for those being different here, but I don't think it matters for any existing type attribute that I could find.

12777–12778

I think in this case, a dependent Auto will never be sugar, and a non-dependent auto can't have a pack either, so we can just pass in false for both.

[davrec]

clang/lib/AST/ASTContext.cpp

12245

I'm not clear on how NExpX could not equal NExpY - could you add a test which demonstrates this case?

12836

Nit: "As" -> "Args", since that's common elsewhere

12900

It would be very helpful to incorporate your description and the description from D111283 as comments in this function. E.g. something like the following ...

12902–12921

// Desugar SX and SY, setting the sugar and qualifiers aside into Xs and Ys/QX and QY, 
// until we reach their underlying "canonical nodes".  (Note these are not necessarily 
// canonical types, as their child types may still be sugared.)

12904

// The canonical nodes differ. Build a common canonical node out of the two, 
// including any sugar shared by their child types.

12906

// The canonical nodes were identical: we may have desugared too much.
// Add any common sugar back in.

12926

// Even though the remaining sugar nodes in Xs and Ys differ, some may be of the same
// type class and have common sugar in their child types.  Walk up these nodes, 
// adding in any such sugar.

[davrec]

clang/lib/AST/ASTContext.cpp

12799

This last argument should probably be omitted/nullptr passed, since

1. We probably won't encounter any owned tag decls in the types passed to this function;
2. Even if we did, it would not necessarily be true that they both have non-null owned tag decls, and I don't see any nullptr checks in getCommonDecl; and
3. Even if we checked for nullptr there, and say passed the same argument to X and Y so EX==EY, and that had an owned tag decl, it is not clear to me it would be appropriate to construct a new type with the same owned tag decl as another type.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12799

1. We can see, a one liner like this will do: int e = true ? (struct S*)0 : (struct S*)0;

Though normally in an example like the above, you would only see the owned decl on X, because when we get to Y the name has already been introduced into the scope.

I have an idea for a test case, but it's a bit convoluted:

This also introduces an OwnedTagDecl: (struct S<T>*)0.

So with resugaring, if we resugar T, it might be possible to construct this situatiation. Given if it's appropriate to keep the OwnedTagDecl when resugaring, of course, which goes to 3)

2. This is handled by declaresSameEntity, if either or both decls are null, we say they are not the same decl.

3. That I am not sure. I see that this OwnedTagDecl is only used by the type printer, and it replaces printing the rest of the type by printing the OwnedDecl instead. So why do you think it would not be appropriate that the rebuilt type keeps this?

[davrec]

clang/lib/AST/ASTContext.cpp

12799

(Re #3) Because I think the sense ownership is respected in how ownedTagDecls are presently handled: at most one ElaboratedType owns a particular TagDecl, *and* that type does not seem to be reused elsewhere in the AST. (This is relied on in https://reviews.llvm.org/D131685, which was on my mind when I looked at this.)

E.g. consider this expansion of your example:

auto e = true ? (struct S*)0 : (true ? (struct S*)0 : (struct S*)0);

The first ElaboratedType has an ownedTagDecl; the second is a distinct ElaboratedType without an ownedTagDecl, and the third equals the second.

Now in practice what this means is that getCommonDecl when used on binary expressions of this sort will always be nullptr, so no harm done. But suppose it is called with X=Y=some ET with an ownedTagDecl (which is the only time I believe we could see a non null getCommonDecl result here). Should the type that is returned have that same owned tag decl? I think that would violate the sense of the original type "owning" that decl that seems to be respected elsewhere in the AST.

Re type printing, I believe that ownedTagDecls only affects printing of defined TagDecls like struct S { int i; } x; (which is what I was mostly thinking re ownedTagDecls - I don't think we will see those here); for undefined ones like struct S x;, printing should be unaffected whether there is an ownedTagDecl or not.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12799

With type deduction this can happen:

auto x = (struct S*)0; // it will also appear in the type of x
using t = decltype(x); // and now also in t

With your second example, it can also happen:

struct S { int i; } x;
int e = true ? &x : (struct S*)0;

In those cases, the type node that owns the decl will be the same object, but that is only because of uniquing.

It may be possible that two different objects end up in this situation, if for example they come from different modules that got merged.

[davrec]

clang/lib/AST/ASTContext.cpp

12799

With type deduction this can happen:

auto x = (struct S*)0; // it will also appear in the type of x
using t = decltype(x); // and now also in t

My local clang is out of date - the type of x for me is just an AutoType wrapping a PointerType to a RecordType. In light of the addition of the ElaboratedType there, it seems fine to be consistent here with however that case handles ownedTagDecls, but FWIW I do not think that deduced ElaboratedType should have an ownedTagDecl either. Only the original type should be the owner - not any type deduced from it.

This is a minor issue with few if any observable effects for now, but should be kept in mind if issues arise later: the fact the ownership of ownedTagDecls is respected was the only factor that made https://discourse.llvm.org/t/ast-parent-of-class-in-a-friend-declaration/64275 easily solvable.

With your second example, it can also happen:

struct S { int i; } x;
int e = true ? &x : (struct S*)0;

The DeclRefExpr x indeed reuses the ElaboratedType used in the VarDecl x, with its ownedTagDecl and all. That seems fair, a special case. For all other type deductions I would mildly object to including an ownedTagDecl.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12245

It may not be needed in this patch, and it might in fact be related to a bug which I already solved in the main resugaring patch. I will double check later.

12799

I think that assumption might work on ElaboratedTypeLocs instead. I think only one per TU should appear in the AST.
Resugaring might make us rebuild such TypeLocs, but the non-resugared one should be unreachable from the AST.

12900

Thanks! I also added some extras in there.

[ChuanqiXu]

clang/include/clang/AST/ASTContext.h

1369

Maybe we need a comment for this. The signature looks not straight forward and I can't relate this to the above comment.

[mizvekov]

clang/include/clang/AST/ASTContext.h

1369

I think I wanted to make this an internal variant, since we will probably never need this outside of ASTContext anyway, but there is the friendship situation between Type and ASTContext. Maybe making this private would be for the best.

[ChuanqiXu]

clang/include/clang/AST/ASTContext.h

1369

Yeah, the signature confused me as well... as long as the second parameter is Decayed already, why we need to get the decayed type again? I guess Underlying may be a better name.

[mizvekov]

clang/include/clang/AST/ASTContext.h

1369

Ah I see, but this confusion already existed. See the definition of DecayedType in Type.h, where you have the QualType getDecayedType() member. This is what this Decayed parameter represents, what we will put in there to be returned by that method.

For DecayedType / AdjustedType / AttributedType there exists this confusion where they have two child nodes, which arbitrarily picking one of them to be called the UnderlyingType could be controversial. You could make the case that it should be the same one we use for implementing desugar, but there are arguments there for the other case.

[ChuanqiXu]

clang/include/clang/AST/ASTContext.h

1369

I see. I got your point. Thanks.

[davrec]

LGTM

[erichkeane]

I've got concerns about the interface not being clear on null-ability, and THIS patch seems to move us toward nulls being disallowed, so I'd like that formalized when possible (either via asserts or, better, by switching to references when possible). Otherwise, LG.

clang/lib/AST/ASTContext.cpp

12141–12142

same concerns about null here. I find myself wondering if this 'getCommonX' should take/return references when possible.

[mizvekov]

clang/lib/AST/ASTContext.cpp

12141–12142

Null is a valid input on this one. We change this function to now accept unrelated decls, and return null in that case as well.

[tra]

It looks like some of these changes are causing compiler to crash in clang::ASTContext::getFloatTypeSemantics during CUDA compilation:
https://lab.llvm.org/buildbot/#/builders/55/builds/35047

I'm currently working on narrowing down which commit is the culprit. Here's a snippet of the stack trace:

 #8 0x0000000008fda385 clang::ASTContext::getFloatTypeSemantics(clang::QualType) const (/buildbot/cuda-p4-0/work/clang-cuda-p4/clang/bin/clang-16+0x8fda385)
 #9 0x0000000008927cb5 unsupportedTypeConversion(clang::Sema const&, clang::QualType, clang::QualType) SemaExpr.cpp:0:0
#10 0x000000000894925a clang::Sema::CheckAssignmentConstraints(clang::QualType, clang::ActionResult<clang::Expr*, true>&, clang::CastKind&, bool) (/buildbot/cuda-p4-0/work/clang-cuda-p4/clang/bin/clang-16+0x894925a)
#11 0x0000000008948e26 clang::Sema::CheckAssignmentConstraints(clang::SourceLocation, clang::QualType, clang::QualType) (/buildbot/cuda-p4-0/work/clang-cuda-p4/clang/bin/clang-16+0x8948e26)
#12 0x00000000089570a7 clang::Sema::CheckAssignmentOperands(clang::Expr*, clang::ActionResult<clang::Expr*, true>&, clang::SourceLocation, clang::QualType, clang::BinaryOperatorKind) (/buildbot/cuda-p4-0/work/clang-cuda-p4/clang/bin/clang-16+0x89570a7)
#13 0x000000000893af00 clang::Sema::CreateBuiltinBinOp(clang::SourceLocation, clang::BinaryOperatorKind, clang::Expr*, clang::Expr*) (/buildbot/cuda-p4-0/work/clang-cuda-p4/clang/bin/clang-16+0x893af00)

[tra]

The culprit appears to be D111509.

clang/include/clang/AST/ASTContext.h

public:
 
   /// Return the uniqued reference to the decayed version of the given
   /// type.  Can only be called on array and function types which decay to
   /// pointer types.
   QualType getDecayedType(QualType T) const;
   CanQualType getDecayedType(CanQualType T) const {
     return CanQualType::CreateUnsafe(getDecayedType((QualType) T));
   }
+  QualType getDecayedType(QualType T, QualType Decayed) const;
 
   /// Return the uniqued reference to the atomic type for the specified
   /// type.
   QualType getAtomicType(QualType T) const;
 
   /// Return the uniqued reference to the type for a block of the
   /// specified type.
   QualType getBlockPointerType(QualType T) const;

clang/lib/AST/ASTContext.cpp

QualType ASTContext::getAdjustedType(QualType Orig, QualType New) const {
 
   AT = new (*this, TypeAlignment)
       AdjustedType(Type::Adjusted, Orig, New, Canonical);
   Types.push_back(AT);
   AdjustedTypes.InsertNode(AT, InsertPos);
   return QualType(AT, 0);
 }
 
+QualType ASTContext::getDecayedType(QualType T, QualType Decayed) const {
+  llvm::FoldingSetNodeID ID;
+  AdjustedType::Profile(ID, T, Decayed);
+  void *InsertPos = nullptr;
+  AdjustedType *AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
+  if (AT)
+    return QualType(AT, 0);
+
+  QualType Canonical = getCanonicalType(Decayed);
+
+  // Get the new insert position for the node we care about.
+  AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
+  assert(!AT && "Shouldn't be in the map!");
+
+  AT = new (*this, TypeAlignment) DecayedType(T, Decayed, Canonical);
+  Types.push_back(AT);
+  AdjustedTypes.InsertNode(AT, InsertPos);
+  return QualType(AT, 0);
+}
+
 QualType ASTContext::getDecayedType(QualType T) const {
   assert((T->isArrayType() || T->isFunctionType()) && "T does not decay");
 
   QualType Decayed;
 
   // C99 6.7.5.3p7:
   //   A declaration of a parameter as "array of type" shall be
   //   adjusted to "qualified pointer to type", where the type
   //   qualifiers (if any) are those specified within the [ and ] of
   //   the array type derivation.
   if (T->isArrayType())
     Decayed = getArrayDecayedType(T);
 
   // C99 6.7.5.3p8:
   //   A declaration of a parameter as "function returning type"
   //   shall be adjusted to "pointer to function returning type", as
   //   in 6.3.2.1.
   if (T->isFunctionType())
     Decayed = getPointerType(T);
 
-  llvm::FoldingSetNodeID ID;
-  AdjustedType::Profile(ID, T, Decayed);
-  void *InsertPos = nullptr;
-  AdjustedType *AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
-  if (AT)
-    return QualType(AT, 0);
-
-  QualType Canonical = getCanonicalType(Decayed);
-
-  // Get the new insert position for the node we care about.
-  AT = AdjustedTypes.FindNodeOrInsertPos(ID, InsertPos);
-  assert(!AT && "Shouldn't be in the map!");
-
-  AT = new (*this, TypeAlignment) DecayedType(T, Decayed, Canonical);
-  Types.push_back(AT);
-  AdjustedTypes.InsertNode(AT, InsertPos);
-  return QualType(AT, 0);
+  return getDecayedType(T, Decayed);
 }
 
 /// getBlockPointerType - Return the uniqued reference to the type for
 /// a pointer to the specified block.
 QualType ASTContext::getBlockPointerType(QualType T) const {
   assert(T->isFunctionType() && "block of function types only");
   // Unique pointers, to guarantee there is only one block of a particular
   // structure.

 unsigned ASTContext::getTargetAddressSpace(LangAS AS) const {
   if (isTargetAddressSpace(AS))
     return toTargetAddressSpace(AS);
   else
     return (*AddrSpaceMap)[(unsigned)AS];
 }
 
 static Decl *getCommonDecl(Decl *X, Decl *Y) {
-  if (X == Y)
-    return X;
-  assert(declaresSameEntity(X, Y));
+  if (!declaresSameEntity(X, Y))
+    return nullptr;
   for (const Decl *DX : X->redecls()) {
     // If we reach Y before reaching the first decl, that means X is older.
     if (DX == Y)
       return X;
     // If we reach the first decl, then Y is older.
     if (DX->isFirstDecl())
       return Y;
   }
   llvm_unreachable("Corrupt redecls chain");
 }
 
 template <class T,
           std::enable_if_t<std::is_base_of<Decl, T>::value, bool> = true>
 T *getCommonDecl(T *X, T *Y) {
   return cast_or_null<T>(
       getCommonDecl(const_cast<Decl *>(cast_or_null<Decl>(X)),
                     const_cast<Decl *>(cast_or_null<Decl>(Y))));
 }
 
+template <class T,
+          std::enable_if_t<std::is_base_of<Decl, T>::value, bool> = true>
+T *getCommonDeclChecked(T *X, T *Y) {
+  return cast<T>(getCommonDecl(const_cast<Decl *>(cast<Decl>(X)),
+                               const_cast<Decl *>(cast<Decl>(Y))));
+}
+
 static TemplateName getCommonTemplateName(ASTContext &Ctx, TemplateName X,
                                           TemplateName Y) {
   if (X.getAsVoidPointer() == Y.getAsVoidPointer())
     return X;
   // FIXME: There are cases here where we could find a common template name
   //        with more sugar. For example one could be a SubstTemplateTemplate*
   //        replacing the other.
   TemplateName CX = Ctx.getCanonicalTemplateName(X);
-  assert(CX.getAsVoidPointer() ==
-         Ctx.getCanonicalTemplateName(Y).getAsVoidPointer());
+  if (CX.getAsVoidPointer() !=
+      Ctx.getCanonicalTemplateName(Y).getAsVoidPointer())
+    return TemplateName();
   return CX;
 }
 
+static TemplateName
+getCommonTemplateNameChecked(ASTContext &Ctx, TemplateName X, TemplateName Y) {
+  TemplateName R = getCommonTemplateName(Ctx, X, Y);
+  assert(R.getAsVoidPointer() != nullptr);
+  return R;
+}
+
 static auto getCommonTypeArray(ASTContext &Ctx, ArrayRef<QualType> Xs,
                                ArrayRef<QualType> Ys,
                                bool Unqualified = false) {
   assert(Xs.size() == Ys.size());
   SmallVector<QualType, 8> Rs(Xs.size());
   for (size_t I = 0; I < Rs.size(); ++I)
     Rs[I] = Ctx.getCommonSugaredType(Xs[I], Ys[I], Unqualified);
   return Rs;
 }
 
 template <class T>
 static SourceLocation getCommonAttrLoc(const T *X, const T *Y) {
   return X->getAttributeLoc() == Y->getAttributeLoc() ? X->getAttributeLoc()
                                                       : SourceLocation();
 }
 
 static TemplateArgument getCommonTemplateArgument(ASTContext &Ctx,
                                                   const TemplateArgument &X,
                                                   const TemplateArgument &Y) {
-  assert(X.getKind() == Y.getKind());
+  if (X.getKind() != Y.getKind())
+    return TemplateArgument();
+
   switch (X.getKind()) {
   case TemplateArgument::ArgKind::Type:
+    if (!Ctx.hasSameType(X.getAsType(), Y.getAsType()))
+      return TemplateArgument();
     return TemplateArgument(
         Ctx.getCommonSugaredType(X.getAsType(), Y.getAsType()));
   case TemplateArgument::ArgKind::NullPtr:
+    if (!Ctx.hasSameType(X.getNullPtrType(), Y.getNullPtrType()))
+      return TemplateArgument();
     return TemplateArgument(
         Ctx.getCommonSugaredType(X.getNullPtrType(), Y.getNullPtrType()),
         /*Unqualified=*/true);
+  case TemplateArgument::ArgKind::Expression:
+    if (!Ctx.hasSameType(X.getAsExpr()->getType(), Y.getAsExpr()->getType()))
+      return TemplateArgument();
+    // FIXME: Try to keep the common sugar.
+    return X;
+  case TemplateArgument::ArgKind::Template: {
+    TemplateName TX = X.getAsTemplate(), TY = Y.getAsTemplate();
+    TemplateName CTN = ::getCommonTemplateName(Ctx, TX, TY);
+    if (!CTN.getAsVoidPointer())
+      return TemplateArgument();
+    return TemplateArgument(CTN);
+  }
+  case TemplateArgument::ArgKind::TemplateExpansion: {
+    TemplateName TX = X.getAsTemplateOrTemplatePattern(),
+                 TY = Y.getAsTemplateOrTemplatePattern();
+    TemplateName CTN = ::getCommonTemplateName(Ctx, TX, TY);
+    if (!CTN.getAsVoidPointer())
+      return TemplateName();
+    auto NExpX = X.getNumTemplateExpansions();
+    assert(NExpX == Y.getNumTemplateExpansions());
+    return TemplateArgument(CTN, NExpX);
+  }
   default:
     // FIXME: Handle the other argument kinds.
     return X;
   }
   llvm_unreachable("");
 }
 
+static bool getCommonTemplateArguments(ASTContext &Ctx,
+                                       SmallVectorImpl<TemplateArgument> &R,
+                                       ArrayRef<TemplateArgument> Xs,
+                                       ArrayRef<TemplateArgument> Ys) {
+  if (Xs.size() != Ys.size())
+    return true;
+  R.resize(Xs.size());
+  for (size_t I = 0; I < R.size(); ++I) {
+    R[I] = getCommonTemplateArgument(Ctx, Xs[I], Ys[I]);
+    if (R[I].isNull())
+      return true;
+  }
+  return false;
+}
+
 static auto getCommonTemplateArguments(ASTContext &Ctx,
-                                       ArrayRef<TemplateArgument> X,
-                                       ArrayRef<TemplateArgument> Y) {
-  SmallVector<TemplateArgument, 8> R(X.size());
-  for (size_t I = 0; I < R.size(); ++I)
-    R[I] = getCommonTemplateArgument(Ctx, X[I], Y[I]);
+                                       ArrayRef<TemplateArgument> Xs,
+                                       ArrayRef<TemplateArgument> Ys) {
+  SmallVector<TemplateArgument, 8> R;
+  bool Different = getCommonTemplateArguments(Ctx, R, Xs, Ys);
+  assert(!Different);
+  (void)Different;
   return R;
 }
 
 template <class T>
 static ElaboratedTypeKeyword getCommonTypeKeyword(const T *X, const T *Y) {
   return X->getKeyword() == Y->getKeyword() ? X->getKeyword()
                                             : ElaboratedTypeKeyword::ETK_None;
 }
ASTContext::mergeExceptionSpecs(FunctionProtoType::ExceptionSpecInfo ESI1,
   case EST_Uninstantiated:
   case EST_Unparsed:
     llvm_unreachable("shouldn't see unresolved exception specifications here");
   }
 
   llvm_unreachable("invalid ExceptionSpecificationType");
 }
 
-static QualType getCommonType(ASTContext &Ctx, const Type *X, const Type *Y) {
+static QualType getCommonNonSugarTypeNode(ASTContext &Ctx, const Type *X,
+                                          const Type *Y) {
   Type::TypeClass TC = X->getTypeClass();
   assert(TC == Y->getTypeClass());
   switch (TC) {
 #define UNEXPECTED_TYPE(Class, Kind)                                           \
   case Type::Class:                                                            \
     llvm_unreachable("Unexpected " Kind ": " #Class);
 
 #define NON_CANONICAL_TYPE(Class, Base) UNEXPECTED_TYPE(Class, "non-canonical")
case Type::Auto: {
     assert(AX->getKeyword() == AY->getKeyword());
     assert(AX->isInstantiationDependentType() ==
            AY->isInstantiationDependentType());
     auto As = getCommonTemplateArguments(Ctx, AX->getTypeConstraintArguments(),
                                          AY->getTypeConstraintArguments());
     return Ctx.getAutoType(QualType(), AX->getKeyword(),
                            AX->isInstantiationDependentType(),
                            AX->containsUnexpandedParameterPack(),
-                           getCommonDecl(AX->getTypeConstraintConcept(),
+                           getCommonDeclChecked(AX->getTypeConstraintConcept(),
                                                 AY->getTypeConstraintConcept()),
                            As);
   }
   case Type::IncompleteArray: {
     const auto *AX = cast<IncompleteArrayType>(X),
                *AY = cast<IncompleteArrayType>(Y);
     return Ctx.getIncompleteArrayType(getCommonElementType(Ctx, AX, AY),
                                       getCommonSizeModifier(AX, AY),
                                       getCommonIndexTypeCVRQualifiers(AX, AY));
case Type::DependentVector: {
     return Ctx.getDependentVectorType(
         getCommonElementType(Ctx, VX, VY), getCommonSizeExpr(VX, VY),
         getCommonAttrLoc(VX, VY), VX->getVectorKind());
   }
   case Type::InjectedClassName: {
     const auto *IX = cast<InjectedClassNameType>(X),
                *IY = cast<InjectedClassNameType>(Y);
     return Ctx.getInjectedClassNameType(
-        getCommonDecl(IX->getDecl(), IY->getDecl()),
+        getCommonDeclChecked(IX->getDecl(), IY->getDecl()),
         Ctx.getCommonSugaredType(IX->getInjectedSpecializationType(),
                                  IY->getInjectedSpecializationType()));
   }
   case Type::TemplateSpecialization: {
     const auto *TX = cast<TemplateSpecializationType>(X),
                *TY = cast<TemplateSpecializationType>(Y);
     auto As = getCommonTemplateArguments(Ctx, TX->template_arguments(),
                                          TY->template_arguments());
     return Ctx.getTemplateSpecializationType(
-        ::getCommonTemplateName(Ctx, TX->getTemplateName(),
+        ::getCommonTemplateNameChecked(Ctx, TX->getTemplateName(),
                                        TY->getTemplateName()),
-        As, TX->getCanonicalTypeInternal());
+        As, X->getCanonicalTypeInternal());
   }
   case Type::DependentName: {
     const auto *NX = cast<DependentNameType>(X),
                *NY = cast<DependentNameType>(Y);
     assert(NX->getIdentifier() == NY->getIdentifier());
     return Ctx.getDependentNameType(
         getCommonTypeKeyword(NX, NY), getCommonNNS(Ctx, NX, NY),
         NX->getIdentifier(), NX->getCanonicalTypeInternal());
case Type::Pipe: {
     auto MP = PX->isReadOnly() ? &ASTContext::getReadPipeType
                                : &ASTContext::getWritePipeType;
     return (Ctx.*MP)(getCommonElementType(Ctx, PX, PY));
   }
   }
   llvm_unreachable("Unknown Type Class");
 }
 
-static auto unwrapSugar(SplitQualType &T) {
+static QualType getCommonSugarTypeNode(ASTContext &Ctx, const Type *X,
+                                       const Type *Y,
+                                       SplitQualType Underlying) {
+  Type::TypeClass TC = X->getTypeClass();
+  if (TC != Y->getTypeClass())
+    return QualType();
+  switch (TC) {
+#define UNEXPECTED_TYPE(Class, Kind)                                           \
+  case Type::Class:                                                            \
+    llvm_unreachable("Unexpected " Kind ": " #Class);
+#define TYPE(Class, Base)
+#define DEPENDENT_TYPE(Class, Base) UNEXPECTED_TYPE(Class, "dependent")
+#include "clang/AST/TypeNodes.inc"
+
+#define CANONICAL_TYPE(Class) UNEXPECTED_TYPE(Class, "canonical")
+    CANONICAL_TYPE(Atomic)
+    CANONICAL_TYPE(BitInt)
+    CANONICAL_TYPE(BlockPointer)
+    CANONICAL_TYPE(Builtin)
+    CANONICAL_TYPE(Complex)
+    CANONICAL_TYPE(ConstantArray)
+    CANONICAL_TYPE(ConstantMatrix)
+    CANONICAL_TYPE(Enum)
+    CANONICAL_TYPE(ExtVector)
+    CANONICAL_TYPE(FunctionNoProto)
+    CANONICAL_TYPE(FunctionProto)
+    CANONICAL_TYPE(IncompleteArray)
+    CANONICAL_TYPE(LValueReference)
+    CANONICAL_TYPE(MemberPointer)
+    CANONICAL_TYPE(ObjCInterface)
+    CANONICAL_TYPE(ObjCObject)
+    CANONICAL_TYPE(ObjCObjectPointer)
+    CANONICAL_TYPE(Pipe)
+    CANONICAL_TYPE(Pointer)
+    CANONICAL_TYPE(Record)
+    CANONICAL_TYPE(RValueReference)
+    CANONICAL_TYPE(VariableArray)
+    CANONICAL_TYPE(Vector)
+#undef CANONICAL_TYPE
+
+#undef UNEXPECTED_TYPE
+
+  case Type::Adjusted: {
+    const auto *AX = cast<AdjustedType>(X), *AY = cast<AdjustedType>(Y);
+    QualType OX = AX->getOriginalType(), OY = AY->getOriginalType();
+    if (!Ctx.hasSameType(OX, OY))
+      return QualType();
+    // FIXME: It's inefficient to have to unify the original types.
+    return Ctx.getAdjustedType(Ctx.getCommonSugaredType(OX, OY),
+                               Ctx.getQualifiedType(Underlying));
+  }
+  case Type::Decayed: {
+    const auto *DX = cast<DecayedType>(X), *DY = cast<DecayedType>(Y);
+    QualType OX = DX->getOriginalType(), OY = DY->getOriginalType();
+    if (!Ctx.hasSameType(OX, OY))
+      return QualType();
+    // FIXME: It's inefficient to have to unify the original types.
+    return Ctx.getDecayedType(Ctx.getCommonSugaredType(OX, OY),
+                              Ctx.getQualifiedType(Underlying));
+  }
+  case Type::Attributed: {
+    const auto *AX = cast<AttributedType>(X), *AY = cast<AttributedType>(Y);
+    AttributedType::Kind Kind = AX->getAttrKind();
+    if (Kind != AY->getAttrKind())
+      return QualType();
+    QualType MX = AX->getModifiedType(), MY = AY->getModifiedType();
+    if (!Ctx.hasSameType(MX, MY))
+      return QualType();
+    // FIXME: It's inefficient to have to unify the modified types.
+    return Ctx.getAttributedType(Kind, Ctx.getCommonSugaredType(MX, MY),
+                                 Ctx.getQualifiedType(Underlying));
+  }
+  case Type::BTFTagAttributed: {
+    const auto *BX = cast<BTFTagAttributedType>(X);
+    const BTFTypeTagAttr *AX = BX->getAttr();
+    // The attribute is not uniqued, so just compare the tag.
+    if (AX->getBTFTypeTag() !=
+        cast<BTFTagAttributedType>(Y)->getAttr()->getBTFTypeTag())
+      return QualType();
+    return Ctx.getBTFTagAttributedType(AX, Ctx.getQualifiedType(Underlying));
+  }
+  case Type::Auto: {
+    const auto *AX = cast<AutoType>(X), *AY = cast<AutoType>(Y);
+
+    AutoTypeKeyword KW = AX->getKeyword();
+    if (KW != AY->getKeyword())
+      return QualType();
+
+    ConceptDecl *CD = ::getCommonDecl(AX->getTypeConstraintConcept(),
+                                      AY->getTypeConstraintConcept());
+    SmallVector<TemplateArgument, 8> As;
+    if (CD &&
+        getCommonTemplateArguments(Ctx, As, AX->getTypeConstraintArguments(),
+                                   AY->getTypeConstraintArguments()))
+      CD = nullptr; // The arguments differ, so make it unconstrained.
+
+    // Both auto types can't be dependent, otherwise they wouldn't have been
+    // sugar. This implies they can't contain unexpanded packs either.
+    return Ctx.getAutoType(Ctx.getQualifiedType(Underlying), AX->getKeyword(),
+                           /*IsDependent=*/false, /*IsPack=*/false, CD, As);
+  }
+  case Type::Decltype:
+    return QualType();
+  case Type::DeducedTemplateSpecialization:
+    // FIXME: Try to merge these.
+    return QualType();
+
+  case Type::Elaborated: {
+    const auto *EX = cast<ElaboratedType>(X), *EY = cast<ElaboratedType>(Y);
+    return Ctx.getElaboratedType(
+        ::getCommonTypeKeyword(EX, EY), ::getCommonNNS(Ctx, EX, EY),
+        Ctx.getQualifiedType(Underlying),
+        ::getCommonDecl(EX->getOwnedTagDecl(), EY->getOwnedTagDecl()));
+  }
+  case Type::MacroQualified: {
+    const auto *MX = cast<MacroQualifiedType>(X),
+               *MY = cast<MacroQualifiedType>(Y);
+    const IdentifierInfo *IX = MX->getMacroIdentifier();
+    if (IX != MY->getMacroIdentifier())
+      return QualType();
+    return Ctx.getMacroQualifiedType(Ctx.getQualifiedType(Underlying), IX);
+  }
+  case Type::SubstTemplateTypeParm: {
+    const auto *SX = cast<SubstTemplateTypeParmType>(X),
+               *SY = cast<SubstTemplateTypeParmType>(Y);
+    const TemplateTypeParmType *PX = SX->getReplacedParameter();
+    if (PX != SY->getReplacedParameter())
+      return QualType();
+
+    return Ctx.getSubstTemplateTypeParmType(PX,
+                                            Ctx.getQualifiedType(Underlying));
+  }
+  case Type::ObjCTypeParam:
+    // FIXME: Try to merge these.
+    return QualType();
+  case Type::Paren:
+    return Ctx.getParenType(Ctx.getQualifiedType(Underlying));
+
+  case Type::TemplateSpecialization: {
+    const auto *TX = cast<TemplateSpecializationType>(X),
+               *TY = cast<TemplateSpecializationType>(Y);
+    TemplateName CTN = ::getCommonTemplateName(Ctx, TX->getTemplateName(),
+                                               TY->getTemplateName());
+    if (!CTN.getAsVoidPointer())
+      return QualType();
+    SmallVector<TemplateArgument, 8> Args;
+    if (getCommonTemplateArguments(Ctx, Args, TX->template_arguments(),
+                                   TY->template_arguments()))
+      return QualType();
+    return Ctx.getTemplateSpecializationType(CTN, Args,
+                                             Ctx.getQualifiedType(Underlying));
+  }
+  case Type::Typedef: {
+    const auto *TX = cast<TypedefType>(X), *TY = cast<TypedefType>(Y);
+    const TypedefNameDecl *CD = ::getCommonDecl(TX->getDecl(), TY->getDecl());
+    if (!CD)
+      return QualType();
+    return Ctx.getTypedefType(CD, Ctx.getQualifiedType(Underlying));
+  }
+  case Type::TypeOf:
+    return Ctx.getTypeOfType(Ctx.getQualifiedType(Underlying));
+  case Type::TypeOfExpr:
+    return QualType();
+
+  case Type::UnaryTransform: {
+    const auto *UX = cast<UnaryTransformType>(X),
+               *UY = cast<UnaryTransformType>(Y);
+    UnaryTransformType::UTTKind KX = UX->getUTTKind();
+    if (KX != UY->getUTTKind())
+      return QualType();
+    QualType BX = UX->getBaseType(), BY = UY->getBaseType();
+    if (!Ctx.hasSameType(BX, BY))
+      return QualType();
+    // FIXME: It's inefficient to have to unify the base types.
+    return Ctx.getUnaryTransformType(Ctx.getCommonSugaredType(BX, BY),
+                                     Ctx.getQualifiedType(Underlying), KX);
+  }
+  case Type::Using: {
+    const auto *UX = cast<UsingType>(X), *UY = cast<UsingType>(Y);
+    const UsingShadowDecl *CD =
+        ::getCommonDecl(UX->getFoundDecl(), UY->getFoundDecl());
+    if (!CD)
+      return QualType();
+    return Ctx.getUsingType(CD, Ctx.getQualifiedType(Underlying));
+  }
+  }
+  llvm_unreachable("Unhandled Type Class");
+}
+
+static auto unwrapSugar(SplitQualType &T, Qualifiers &QTotal) {
   SmallVector<SplitQualType, 8> R;
   while (true) {
+    QTotal += T.Quals;
     QualType NT = T.Ty->getLocallyUnqualifiedSingleStepDesugaredType();
     if (NT == QualType(T.Ty, 0))
       break;
-    SplitQualType SplitNT = NT.split();
-    SplitNT.Quals += T.Quals;
     R.push_back(T);
-    T = SplitNT;
+    T = NT.split();
   }
   return R;
 }
 
-static bool removeDifferentTopLevelSugar(SplitQualType &SX, SplitQualType &SY) {
-  auto Xs = ::unwrapSugar(SX), Ys = ::unwrapSugar(SY);
-  if (SX.Ty != SY.Ty)
-    return true;
-  while (!Xs.empty() && !Ys.empty() && Xs.back().Ty == Ys.back().Ty) {
-    SX = Xs.pop_back_val();
-    SY = Ys.pop_back_val();
-  }
-  return false;
-}
-
 QualType ASTContext::getCommonSugaredType(QualType X, QualType Y,
                                           bool Unqualified) {
   assert(Unqualified ? hasSameUnqualifiedType(X, Y) : hasSameType(X, Y));
   if (X == Y)
     return X;
   if (!Unqualified) {
     if (X.isCanonical())
       return X;
     if (Y.isCanonical())
       return Y;
   }
 
   SplitQualType SX = X.split(), SY = Y.split();
-  if (::removeDifferentTopLevelSugar(SX, SY))
-    SX.Ty = ::getCommonType(*this, SX.Ty, SY.Ty).getTypePtr();
-
+  Qualifiers QX, QY;
+  // Desugar SX and SY, setting the sugar and qualifiers aside into Xs and Ys,
+  // until we reach their underlying "canonical nodes". Note these are not
+  // necessarily canonical types, as they may still have sugared properties.
+  // QX and QY will store the sum of all qualifiers in Xs and Ys respectively.
+  auto Xs = ::unwrapSugar(SX, QX), Ys = ::unwrapSugar(SY, QY);
+  if (SX.Ty != SY.Ty) {
+    // The canonical nodes differ. Build a common canonical node out of the two,
+    // unifying their sugar. This may recurse back here.
+    SX.Ty = ::getCommonNonSugarTypeNode(*this, SX.Ty, SY.Ty).getTypePtr();
+  } else {
+    // The canonical nodes were identical: We may have desugared too much.
+    // Add any common sugar back in.
+    while (!Xs.empty() && !Ys.empty() && Xs.back().Ty == Ys.back().Ty) {
+      QX -= SX.Quals;
+      QY -= SY.Quals;
+      SX = Xs.pop_back_val();
+      SY = Ys.pop_back_val();
+    }
+  }
   if (Unqualified)
-    SX.Quals = Qualifiers::removeCommonQualifiers(SX.Quals, SY.Quals);
+    QX = Qualifiers::removeCommonQualifiers(QX, QY);
   else
-    assert(SX.Quals == SY.Quals);
+    assert(QX == QY);
+
+  // Even though the remaining sugar nodes in Xs and Ys differ, some may be
+  // related. Walk up these nodes, unifying them and adding the result.
+  while (!Xs.empty() && !Ys.empty()) {
+    auto Underlying = SplitQualType(
+        SX.Ty, Qualifiers::removeCommonQualifiers(SX.Quals, SY.Quals));
+    SX = Xs.pop_back_val();
+    SY = Ys.pop_back_val();
+    SX.Ty = ::getCommonSugarTypeNode(*this, SX.Ty, SY.Ty, Underlying)
+                .getTypePtrOrNull();
+    // Stop at the first pair which is unrelated.
+    if (!SX.Ty) {
+      SX.Ty = Underlying.Ty;
+      break;
+    }
+    QX -= Underlying.Quals;
+  };
 
-  QualType R = getQualifiedType(SX);
+  // Add back the missing accumulated qualifiers, which were stripped off
+  // with the sugar nodes we could not unify.
+  QualType R = getQualifiedType(SX.Ty, QX);
   assert(Unqualified ? hasSameUnqualifiedType(R, X) : hasSameType(R, X));
   return R;
 }
 
 QualType ASTContext::getCorrespondingSaturatedType(QualType Ty) const {
   assert(Ty->isFixedPointType());
 
   if (Ty->isSaturatedFixedPointType()) return Ty;

clang/lib/Sema/SemaTemplateDeduction.cpp

if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
       ArgType = S.Context.getLValueReferenceType(ArgType);
     }
   } else {
     // C++ [temp.deduct.call]p2:
     //   If P is not a reference type:
     //   - If A is an array type, the pointer type produced by the
     //     array-to-pointer standard conversion (4.2) is used in place of
     //     A for type deduction; otherwise,
-    if (ArgType->isArrayType())
-      ArgType = S.Context.getArrayDecayedType(ArgType);
     //   - If A is a function type, the pointer type produced by the
     //     function-to-pointer standard conversion (4.3) is used in place
     //     of A for type deduction; otherwise,
-    else if (ArgType->isFunctionType())
-      ArgType = S.Context.getPointerType(ArgType);
+    if (ArgType->canDecayToPointerType())
+      ArgType = S.Context.getDecayedType(ArgType);
     else {
       // - If A is a cv-qualified type, the top level cv-qualifiers of A's
       //   type are ignored for type deduction.
       ArgType = ArgType.getUnqualifiedType();
     }
   }
 
   // C++0x [temp.deduct.call]p4:

clang/test/SemaCXX/sugar-common-types.cpp

-// RUN: %clang_cc1 -fsyntax-only -verify %s -std=c++20 -fenable-matrix
+// RUN: %clang_cc1 -fsyntax-only -verify %s -std=c++20 -fenable-matrix -triple i686-pc-win32
 
 enum class N {};
 
 using B1 = int;
 using X1 = B1;
 using Y1 = B1;
 
 using B2 = void;

 N t4 = X3() + Y3();   // expected-error {{rvalue of type 'B3'}}
 
 N t5 = A3() ? X3() : Y3(); // expected-error {{rvalue of type 'B3'}}
 N t6 = A3() ? X1() : Y1(); // expected-error {{vector condition type 'A3' (vector of 4 'char' values) and result type '__attribute__((__vector_size__(4 * sizeof(B1)))) B1' (vector of 4 'B1' values) do not have elements of the same size}}
 
 N t7 = X4() + Y4(); // expected-error {{rvalue of type 'B4'}}
 N t8 = X4() * Y4(); // expected-error {{rvalue of type 'B4'}}
 N t9 = X5() * Y5(); // expected-error {{rvalue of type 'A4 __attribute__((matrix_type(3, 3)))'}}
+
+template <class T> struct S1 {
+  template <class U> struct S2 {};
+};
+
+N t10 = 0 ? S1<X1>() : S1<Y1>(); // expected-error {{from 'S1<B1>' (aka 'S1<int>')}}
+N t11 = 0 ? S1<X1>::S2<X2>() : S1<Y1>::S2<Y2>(); // expected-error {{from 'S1<int>::S2<B2>' (aka 'S2<void>')}}
+
+template <class T> using Al = S1<T>;
+
+N t12 = 0 ? Al<X1>() : Al<Y1>(); // expected-error {{from 'Al<B1>' (aka 'S1<int>')}}
+
+#define AS1 __attribute__((address_space(1)))
+#define AS2 __attribute__((address_space(1)))
+using AS1X1 = AS1 B1;
+using AS1Y1 = AS1 B1;
+using AS2Y1 = AS2 B1;
+N t13 = 0 ? (AS1X1){} : (AS1Y1){}; // expected-error {{rvalue of type 'AS1 B1' (aka '__attribute__((address_space(1))) int')}}
+N t14 = 0 ? (AS1X1){} : (AS2Y1){}; // expected-error {{rvalue of type '__attribute__((address_space(1))) B1' (aka '__attribute__((address_space(1))) int')}}
+
+using FX1 = X1 ();
+using FY1 = Y1 ();
+N t15 = 0 ? (FX1*){} : (FY1*){}; // expected-error {{rvalue of type 'B1 (*)()' (aka 'int (*)()')}}
+
+struct SS1 {};
+using SB1 = SS1;
+using SX1 = SB1;
+using SY1 = SB1;
+
+using MFX1 = X1 SX1::*();
+using MFY1 = Y1 SY1::*();
+
+N t16 = 0 ? (MFX1*){} : (MFY1*){}; // expected-error {{rvalue of type 'B1 SB1::*(*)()'}}
+
+N t17 = 0 ? (FX1 SX1::*){} : (FY1 SY1::*){}; // expected-error {{rvalue of type 'B1 (SB1::*)() __attribute__((thiscall))'}}
+
+N t18 = 0 ? (__typeof(X1*)){} : (__typeof(Y1*)){}; // expected-error {{rvalue of type 'typeof(B1 *)' (aka 'int *')}}
+
+struct Enums {
+  enum X : B1;
+  enum Y : ::B1;
+};
+using EnumsB = Enums;
+using EnumsX = EnumsB;
+using EnumsY = EnumsB;
+
+N t19 = 0 ? (__underlying_type(EnumsX::X)){} : (__underlying_type(EnumsY::Y)){};
+// expected-error@-1 {{rvalue of type 'B1' (aka 'int')}}
+
+N t20 = 0 ? (__underlying_type(EnumsX::X)){} : (__underlying_type(EnumsY::X)){};
+// expected-error@-1 {{rvalue of type '__underlying_type(Enums::X)' (aka 'int')}}
+
+using SBTF1 = SS1 [[clang::btf_type_tag("1")]];
+using SBTF2 = ::SS1 [[clang::btf_type_tag("1")]];
+using SBTF3 = ::SS1 [[clang::btf_type_tag("2")]];
+
+N t21 = 0 ? (SBTF1){} : (SBTF3){}; // expected-error {{from 'SS1'}}
+N t22 = 0 ? (SBTF1){} : (SBTF2){}; // expected-error {{from 'SS1 btf_type_tag(1)' (aka 'SS1')}}
+
+using QX = const SB1 *;
+using QY = const ::SB1 *;
+N t23 = 0 ? (QX){} : (QY){}; // expected-error {{rvalue of type 'const SB1 *' (aka 'const SS1 *')}}
+
+template <class T> using Alias = short;
+N t24 = 0 ? (Alias<X1>){} : (Alias<Y1>){}; // expected-error {{rvalue of type 'Alias<B1>' (aka 'short')}}
+N t25 = 0 ? (Alias<X1>){} : (Alias<X2>){}; // expected-error {{rvalue of type 'short'}}
+
+template <class T, class U> concept C1 = true;
+template <class T, class U> concept C2 = true;
+C1<X1> auto t26_1 = (SB1){};
+C1<X2> auto t26_2 = (::SB1){};
+C2<X2> auto t26_3 = (::SB1){};
+N t26 = 0 ? t26_1 : t26_2; // expected-error {{from 'SB1' (aka 'SS1')}}
+N t27 = 0 ? t26_1 : t26_3; // expected-error {{from 'SB1' (aka 'SS1')}}

libcxx/DELETE.ME

 D111283
 D111509
+D130308