[clang] template / auto deduction deduces common sugar

[mizvekov]

Summary

After upgrading the type deduction machinery to retain type sugar in
D110216, we were left with a situation where there is no general
well behaved mechanism in Clang to unify the type sugar of multiple
deductions of the same type parameter.

So we ended up making an arbitrary choice: keep the sugar of the first
deduction, ignore subsequent ones.

In general, we already had this problem, but in a smaller scale.
The result of the conditional operator and many other binary ops
could benefit from such a mechanism.

This patch implements such a type sugar unification mechanism.

The basics:

This patch introduces a getCommonSugaredType(QualType X, QualType Y)
method to ASTContext which implements this functionality, and uses it
for unifying the results of type deduction and return type deduction.
This will return the most derived type sugar which occurs in both X and
Y.

Example:

Suppose we have these types:

using Animal = int;
using Cat = Animal;
using Dog = Animal;

using Tom = Cat;
using Spike = Dog;
using Tyke = Dog;

For X = Tom, Y = Spike, this will result in Animal.
For X = Spike, Y = Tyke, this will result in Dog.

How it works:

We take two types, X and Y, which we wish to unify as input.
These types must have the same (qualified or unqualified) canonical
type.

We dive down fast through top-level type sugar nodes, to the
underlying canonical node. If these canonical nodes differ, we
build a common one out of the two, unifying any sugar they had.
Note that this might involve a recursive call to unify any children
of those. We then return that canonical node, handling any qualifiers.

If they don't differ, we walk up the list of sugar type nodes we dived
through, finding the last identical pair, and returning that as the
result, again handling qualifiers.

Note that this patch will not unify sugar nodes if they are not
identical already. We will simply strip off top-level sugar nodes that
differ between X and Y. This sugar node unification will instead be
implemented in a subsequent patch.

This patch also implements a few users of this mechanism:

• Template argument deduction.
• Auto deduction, for functions returning auto / decltype(auto), with special handling for initializer_list as well.

Further users will be implemented in a subsequent patch.

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

[rsmith]

clang/lib/AST/ASTContext.cpp

11782–11793

This seems a bit suspicious: getCommonTypeArray assumes the two arrays contain the same types in the same order, but if the arrays can be different sizes, is it really correct to assume that they contain the same types if they're the same size?

Can we make this work the same way that the conditional expression handling deals with differing lists of exception types?

11853

I think this should probably be a declaresSameEntity check: we might be comparing injected class names from two different merged modules with two different declarations for the same class definition. The right declaration to use is the one that is chosen to be "the" definition.

[mizvekov]

• Just rebase, no review comments addressed yet.
• One small churn in test/SemaCXX/deduced-return-void.cpp, which is new since last rebase. As this patch uses the template deduction machinery to also handle the mutiple return statements, we detect the inconsistent deduction before substitution, so we don't error out trying to form the reference to void.

[mizvekov]

clang/lib/AST/ASTContext.cpp

11543–11544

I have updated the ASContext::getCommonSugaredType to accept an Unqualified parameter to handle this case.
We will strip qualifiers from each other until the types are the same.

11570

Yeah, but this has been dead code since we went back to canonical template parameter / arguments.
I have removed it and put some unreachables in place.
We will circle back around to add it with this suggestion later.

11782–11793

Handled this with a new ASTContext::mergeTypeLists that does what the conditional expression handling did, while getting the common sugar of types when they occur in both lists.

11853

Implemented this with a new getCommonDecl function, which for now will just fall back to the canonical decl if they differ.

Wonder if there is a cheap way to determine which of the two decls was declared earlier. Have to look this up, but would a simple pointer comparison be guaranteed to work? Eg would the earliest declaration, since being created earlier and allocated earlier, be guaranteed by design to have a lower (or greater) pointer value?

[Mordante]

The libc++ build failures are due a broken libc++ HEAD. The current HEAD should work again.

[rsmith]

clang/lib/AST/ASTContext.cpp

11570

This will need to deal with all the cases that can arrive here. If it sees resolved template arguments, then this includes Type, Declaration, NullPtr, Integral, Template, TemplateExpansion, and Pack. If it sees unresolved template arguments, then this includes at least Type, Expression, Template, and TemplateExpansion. This function currently doesn't cover either set, so I strongly suspect that this llvm_unreachable is actually reachable.

Can we just return X; on all the cases we don't currently handle?

11627

11655

Please add braces to this outer for.

11675–11677

What guarantees that we won't see never-canonical types here?

I understand why we won't see sugar-free types (we can't have two Type*s that are different but represent the same type if they're sugar-free), and why we won't see non-unique types here (we can't have two Type*s that are different but represent the same type if they're not uniqued). But why can't we find, say, two different TypedefTypes here that desugar to the same type?

11703–11704

I don't understand why the deduced type must be null here. I think it usually will be, because if the deduced type were non-null, it would have to be identical (because we know desugaring one more level results in identical types), and in that case we'd typically have produced the same AutoType. But it seems like we could have two constrained AutoTypes here that desugar to the same type but differ in the spelling of their constraints, in which case the common type should presumably have a deduced type. I wonder if we should just be checking AX->getDeducedType() == AY->getDeducedType() here and passing in AX->getDeducedType() as the deduced type below?

11777–11778

If either of them was spelled as an lvalue then the pointee type was spelled as either an lvalue reference or a non-reference for that input type, and we'll strip off the spelling-as-rvalue-reference part of the other type when finding the common type. The only case in which I think it makes sense to retain the "spelled as rvalue" flag would be if *both* sides were lvalue references spelled as rvalue references.

11828–11829

Can we cope with a variadic function with no ellipsis location? I'd expect that to confuse some parts of Clang. Picking one of the two arbitrarily isn't great but may be the best we can do.

11853

No, there's no guarantee on pointer ordering. While we do use slab allocation, we allocate multiple slabs and there's no ordering between slabs. (Also declarations can be read from an AST file in any order.) There's no good way to find which of two declarations was declared first without a linear scan; see NamedDecl::declarationReplaces for existing code doing that scan. It might be that we need the scan rarely enough that we can afford to do it.

11914

No-op change, but this would make it a bit more obvious to a reader why it's OK to pass in TX here.

clang/lib/Sema/SemaExprCXX.cpp

1476–1477

It'd be nice to add an assert(Result == TDK_AlreadyDiagnosed); here now that we can do so.

2013

Likewise it'd be nice to add an assert(Result == TDK_AlreadyDiagnosed); here.

clang/lib/Sema/SemaTemplateDeduction.cpp

4577–4580

This comment is out of date.

4709–4710

I do like this approach to repeated deduction, but I'm not sure that it actually works. For example:

void f();
void g();
void g(int);
auto h(bool b) {
  if (b) return f;
  return g;
}

I think this is required to fail to compile, because we can't deduce the return type from the returned expression g. But I think what will happen here is that we'll say that g is a non-deduced context and then succeed because we pre-populated the deduced type from the void(*)() from f.

Instead, how about not pre-populating Deduced[0], and instead "deducing" the template parameter from Result after we check for the TDK_Incomplete case below? That should still let us reuse the logic for merging deductions.

4726

Can we use checkDeducedTemplateArguments here to unify the type sugar?

[mizvekov]

In D111283#3646066, @Mordante wrote:

The libc++ build failures are due a broken libc++ HEAD. The current HEAD should work again.

Thanks for letting me know! Pushed my patches again just to have a look at the result, haven't made any changes yet.

And Richard, tons of thanks again for the review!

[mizvekov]

clang/lib/AST/ASTContext.cpp

11675–11677

The idea is that this function is only called from a context where removeDifferentTopLevelSugar / unwrapSugar will have removed all top-level nodes which are sugar. So in particular, we will never see here any type nodes which have an implementation for is isSugared which always returns true, such as the TypedefType case.

So this is peculiar to this initial implementation, which never tries to "merge" sugar nodes.
There is value in trying to merge those, but you can imagine that the implementation for that is much more complicated and needs more thinking to get right and efficient.

For example for the TypedefType case right now:

If we had two different typedefs with the same underlying type, then there seems to be no sensible choice here except stripping off the typedef, I mean what Decl would we put on the TypedefType? Right now nullptr would not work since we always take the underlying type from the Decl, but even if it did, the value of having a nullptr decl seems questionable given the amount of trouble this could cause in other code.

If the TypedefTypes pointed to the same TypedefDecl, then it would make sense to create a new one with the "common" Decl between them, such as the earliest declaration or the canonical one, but might not be worth the extra complexity in the overall logic just for this effect.

Note that on my D127695, I implemented resugared TypedefTypes, which can have a different (but canonically the same) underlying type. With that, we would have more to do here and I think then it would be worth improving this further.

Otherwise, there is other interesting sugar we could try merging in the future as well, such as ElaboratedType and alias TemplateSpecializationTypes.

11703–11704

Well if they desugared to anything, then they would never show up in this function, they would have been stripped off by unwrapSugar as I explained in the previous comment.

[mizvekov]

clang/lib/AST/ASTContext.cpp

11570

Yeah I will just return X for the peace of mind for now, but I think what is happening here is that we only see unresolved template arguments, so we would theoretically be missing the handling of Template and TemplateExpansion cases.

The problem is, I think we are not actually preserving type sugar of those two cases, because of a profiling bug.
I pointed this problem out recently in this revision: https://reviews.llvm.org/D126172

So this is probably pretty hard to test right now, and we would not even get any results from handling it, so I will
leave a FIXME instead.

11828–11829

Can we cope with a variadic function with no ellipsis location? I'd expect that to confuse some parts of Clang. Picking one of the two arbitrarily isn't great but may be the best we can do.

Will leave that out for now with a FIXME.

clang/lib/Sema/SemaTemplateDeduction.cpp

4709–4710

Nice find. We don't actually need to repeat the deduction. We only need to return Inconsistent deduction if Result and Deduced[0] are different, and get the common sugar otherwise.

We already had to do so for the decltype(auto) case, and we could have totally resugared the initializer lists but forgot as you pointed out, and we had to make this same check for that case anyway.

So I combined all these cases, further simplifying things, and added the new test case for initializer_list.

[erichkeane]

This is a sizable patch, and it isn't really clear from context what I'm looking at. Can you please improve the description/commit message to better clarify what you are trying to do, what you did, and how you are trying to accomplish it?

[mizvekov]

In D111283#3712348, @erichkeane wrote:

This is a sizable patch, and it isn't really clear from context what I'm looking at. Can you please improve the description/commit message to better clarify what you are trying to do, what you did, and how you are trying to accomplish it?

Updated description, also, for reference, the other patches that continue this work are D111509 and D130308.

Thanks for taking a look!

[davrec]

This part of the description is confusing:

We take two types, X and Y, which we wish to unify as input.
These types must have the same (qualified or unqualified) canonical
type.

We dive down fast through top-level type sugar nodes, to the
underlying canonical node. If these canonical nodes differ, we
build a common one out of the two, unifying any sugar they had.
Note that this might involve a recursive call to unify any children
of those. We then return that canonical node, handling any qualifiers.

If they don't differ, we walk up the list of sugar type nodes we dived
through, finding the last identical pair, and returning that as the
result, again handling qualifiers.

The first paragraph says X and Y must have the same canonical type, the second suggests they need not. In all the test cases, they have the same canonical type.

IIUC the second paragraph only applies to the stuff done in D130308; is that correct?

If so, the description should clearly state this patch only handles the case when the canonical types of X and Y are identical, and note that if the canonical types of X and Y differ, this patch does nothing, but D130308 adds some additional logic to search for common sugar in child type nodes of X and Y to use in the merged type.

And of course please add a full description to D130308 as well when you have a chance.

[mizvekov]

In D111283#3716104, @davrec wrote:

The first paragraph says X and Y must have the same canonical type, the second suggests they need not.

The first paragraph is talking about canonical equality, or if you take it that types 'refer' to their canonical types, referential equality.
Ie 'X.getCanonicalType() == Y.getCanonicalType()'

For short, when there is referential equality, I will say that the types are 'the same'. This matches terminology in Clang, for example see the helper ASTContext::hasSameType.

When there is structural equality, ie 'X == Y', I will say for short the types are 'identical'.

The second paragraph is talking about 'Canonical nodes', not 'Canonical types'.

A canonical node is a type node for which 'isSugared' method returns false.
This is not the same thing as saying that a Canonical node is a canonical type.

For example, 'PointerType' nodes are always canonical nodes, because it has an 'isSugared' implementation which always returns false:

bool isSugared() const { return false; }

But pointer types can be non-canonical, in particular when the PointeeType is not a canonical type.

In D111283#3716104, @davrec wrote:

In all the test cases, they have the same canonical type.

Well not exactly, we also handle and test the case they are also the same when 'unqualified'.

The case here is function types that differ only in top-level qualifiers of parameters, so this is used only when we are recursing down a FunctionType.

Those FunctionTypes should be treated as the same, ie you can't overload based on differences in top-level qualifiers of function parameters.
But this should not be treated as a semantic adjustment, like we do for decays, eg in array parameters, because we still need to consider those qualifiers on the parameter itself within the function definition, unlike what happens with decays (where we basically just rewrite the type of the parameter).

See the t8 and t11 test cases in clang/test/SemaCXX/sugared-auto.cpp, which test top-level differences in const and ObjectiveC lifetime qualifiers respectively.

IIUC the second paragraph only applies to the stuff done in D130308; is that correct?

No, it's talking about the stuff in this patch.

In this patch, we unify Canonical nodes that differ, but don't unify different non-canonical nodes (ie those which 'isSugared()' returns true), that last part is done in D130308.

If so, the description should clearly state this patch only handles the case when the canonical types of X and Y are identical, and note that if the canonical types of X and Y differ, this patch does nothing, but D130308 adds some additional logic to search for common sugar in child type nodes of X and Y to use in the merged type.

Well it's not that we do nothing if the types are not the same!
That the inputs should be the same (but not necessaritly identical) is an invariant, ie a contract to use this function.
In a debug build, we will check that this invariant is respected, asserting otherwise.

And of course please add a full description to D130308 as well when you have a chance.

Sure.

[davrec]

The second paragraph is talking about 'Canonical nodes', not 'Canonical types'.

A canonical node is a type node for which 'isSugared' method returns false.

Thanks for the clarification, but note that that term is not in general use so far as I'm aware. But instead of defining it and getting into details it might be clearer, and certainly would have saved me the most time, for the description to simply note that this patch introduces ASTContext::getCommonSugaredType(QualType X, QualType Y, bool Unqualified = false), and puts it to use in type deduction for binary expressions etc., and give an example or two to demonstrate. (More generally on a large patch I prefer a description to give me a few starting points, the primary changes which necessitate all the others.)

Re the patch itself: it looks good to me other than a few nits, but this has such a broad and deep span (intricate details of the AST + intricate details of Sema) it is difficult to give it a final thumbs up - really hoping @rsmith might take a final look. But if time runs out it is definitely worth accepting as is and seeing how it goes; the benefits exceed the risks. I will try to take a close look at the other patches on your stack, but the same probably applies. You've done a tremendous amount of work here, very impressive.

clang/include/clang/AST/ASTContext.h

2738

A clearer name might be combineExceptionSpecs, or the original mergeExceptionSpecs, since this is getting the union of their sets of exception specs, whereas getCommon* suggests getting the intersection, e.g. getCommonSugaredType is getting the intersection of two "sets" of type sugar in a sense.

Also, please add some brief documentation to the function.

2756

Any reason this is public? Or in the header at all? Seems like it could be a static function in the cpp.

clang/lib/AST/ASTContext.cpp

11544

I think "canonical" should be replaced with "first" here and isCanonicalDecl() with isFirstDecl(). So far as I can tell getCanonicalDecl() returns getFirstDecl() everywhere for now, but that could conceivably change, and in any case the goal of this code is to find which is older, so "first" would be clearer as well.

[mizvekov]

In D111283#3721905, @davrec wrote:

But instead of defining it and getting into details it might be clearer, and certainly would have saved me the most time, for the description to simply note that this patch introduces ASTContext::getCommonSugaredType(QualType X, QualType Y, bool Unqualified = false), and puts it to use in type deduction for binary expressions etc., and give an example or two to demonstrate. (More generally on a large patch I prefer a description to give me a few starting points, the primary changes which necessitate all the others.)

Done, thanks for the feedback!

Re the patch itself: it looks good to me other than a few nits, but this has such a broad and deep span (intricate details of the AST + intricate details of Sema) it is difficult to give it a final thumbs up - really hoping @rsmith might take a final look. But if time runs out it is definitely worth accepting as is and seeing how it goes; the benefits exceed the risks. I will try to take a close look at the other patches on your stack, but the same probably applies. You've done a tremendous amount of work here, very impressive.

Yeah, but we made good progress here, thanks again!

[v.g.vassilev]

Thanks for working on this! I left some comments. I did not look very deep in the patch but it seems quite consistent to the rest of the code in Sema.

Can you provide some performance numbers for this patch. I believe that the less confident reviewers will be more comfortable letting that patch in. I think this work is important and should be merged before GSoC ends. It will allow clang to diagnose better errors in template instantiations even for cases such as llvm.org/PR12853

clang/lib/AST/ASTContext.cpp

11554

Maybe getCommonDecl should take const Decl* instead of const_cast-ing here.

11597

11833

Defining decl groups does not seem common in the llvm/clang codebase. I don't think we have a specific rule discouraging that. However, I think stepping through with a debugger will be harder. Maybe make this and other occurrences more consistent to the rest of the codebase?

[mizvekov]

In D111283#3733415, @v.g.vassilev wrote:

Thanks for working on this! I left some comments. I did not look very deep in the patch but it seems quite consistent to the rest of the code in Sema.

Thanks!

Can you provide some performance numbers for this patch. I believe that the less confident reviewers will be more comfortable letting that patch in.

Yeah, sounds good.

clang/lib/AST/ASTContext.cpp

11554

If getCommonDecl took const Decl, I believe I would still need to const_cast to const Decl * anyway, because otherwise we would end up in infinite recursion into this function template.

And I would then in addition need to const_cast in the return value, which would make the whole thing more complicated.

11833

Though in these cases the expression is just a cast, you would so rarely need to step into them as there is very little interesting going on in there.

[mizvekov]

llvm-compile-time-tracker stats for this patch: http://llvm-compile-time-tracker.com/compare.php?from=f7a33090a91015836497c75f173775392ab0304d&to=771076b836b331f50f8a852fba1353aa60865e30&stat=instructions

For the next one on the stack, which hooks the new mechanism here to more places: http://llvm-compile-time-tracker.com/compare.php?from=771076b836b331f50f8a852fba1353aa60865e30&to=56a1894e70ff387d0b7791564a12a5879655c86f&stat=instructions

For the one after that, which extends this mechanism to cover sugar nodes: http://llvm-compile-time-tracker.com/compare.php?from=56a1894e70ff387d0b7791564a12a5879655c86f&to=96a13ce3e1776de824585182603f01258332d2c8&stat=instructions

They all look to be within what you would expect from noise alone.

[ChuanqiXu]

clang/include/clang/AST/ASTContext.h

2747–2751

For this comment, I want to know what if Xand Y is not equal. Is there an assertion failure or special type returned?

[mizvekov]

clang/include/clang/AST/ASTContext.h

2747–2751

Assertion failure, the function is supposed to handle only the case where hasSame[Unqualified]Type(X, Y) == true.

It will always return a type R for which hasSame[Unqualified]Type(R, Y) == true also holds, so there are no special return values.

[davrec]

I hope I'm not stepping on any toes given the recent changes in code ownership, but I'm accepting this and D130308 because

1. They are a nice improvement to the AST that naturally follows from the earlier work adding sugar to type deductions,
2. I have given it a fairly close look and it LGTM,
3. @rsmith has taken a step back and so may not be available to give it a final look,
4. @mizvekov has verified that the performance impact is negligible, and
5. Other reviewers seem to have at least given it a once over and have not identified major issues.

Anyone object/need more time to review?

[erichkeane]

Thanks for your patience, this was a sizable review that it took a while to be able to make time for. A handful of non-functional reviews, but the functionality looks fine.

clang/lib/AST/ASTContext.cpp

11538

As a nit, I'd prefer this assert above the 'if' above, that way it catches Nulls in that case. It seems that the 'contract' for this function is no null values, so we want to catch this ASAP.

11544

For class types, canonical decl is usually the definition if one exists. So I assume we do mean 'first' here.

11553

Do we REALLY need to tolerate 'null' here as well? It seems we should do a normal cast and have the cast assert.

11571

Please comment these functions, it isn't clear on read through what you mean by 'Array' here. You probably mean for this to be something like getCommonTypes.

11603

Please give me a message here, just anything reasonably descriptive so that when it shows up I have something to grep.

11640

I guess I don't see the po int of the next 3 functions? There is no sugaring or anything, AND they already assume they are the same expression/element/etc?

11722

something a little more unique in this (and others!) would be appreciated.

[mizvekov]

clang/lib/AST/ASTContext.cpp

11538

Actually we want to handle the case they are both null, in which case we return null as well.
This case would trip the assert below, as declaresSameEntity considers that not the same entity.

For example, unconstrained AutoType will have null ConceptDecl.

In the D130308 patch, we add another variant, `getCommonDeclChecked, which requires non-null inputs, which can be used in places where non-null is required.

I went ahead and moved the introduction of getCommonDeclChecked to this patch, even though there is only one use of it.

11553

Yes, as above.

11571

Yeah that name works as well.

11640

Well the point is to not repeat the assert in all use sites.

[mizvekov]

In D111283#3771900, @erichkeane wrote:

Thanks for your patience, this was a sizable review that it took a while to be able to make time for. A handful of non-functional reviews, but the functionality looks fine.

Thanks, I appreciate the effort!

[ychen]

Hi @mizvekov , I noticed that deduction for partial ordering also inherits this new behavior. Do you think partial ordering could opt out of this, or is it better for partial ordering to deal with the new sugared types?

[mizvekov]

In D111283#3783250, @ychen wrote:

Hi @mizvekov , I noticed that deduction for partial ordering also inherits this new behavior. Do you think partial ordering could opt out of this, or is it better for partial ordering to deal with the new sugared types?

I would expect partial ordering to be performed only using canonical types, that type sugar should make no difference there.

Note that previous to this patch, we would already produce sugar on deduction, but the behavior with regards to deducing the same template parameter from multiple places was pretty badly behaved: We would just keep the sugar from the first deduction, and ignore any subsequent ones. That meant that the deduction order had an effect on the result. With this patch, deduction becomes order agnostic.

What kind of difference are you seeing?

[alexfh]

Hi Matheus, an early heads up: this commit is causing clang crashes on some of our code. I'll post more details a bit later.

[ychen]

In D111283#3783338, @mizvekov wrote:

In D111283#3783250, @ychen wrote:

Hi @mizvekov , I noticed that deduction for partial ordering also inherits this new behavior. Do you think partial ordering could opt out of this, or is it better for partial ordering to deal with the new sugared types?

I would expect partial ordering to be performed only using canonical types, that type sugar should make no difference there.

Note that previous to this patch, we would already produce sugar on deduction, but the behavior with regards to deducing the same template parameter from multiple places was pretty badly behaved: We would just keep the sugar from the first deduction, and ignore any subsequent ones. That meant that the deduction order had an effect on the result. With this patch, deduction becomes order agnostic.

I see. I think it is definitely a good thing. I'm still learning what the expected AST should look like during the partial ordering.

What kind of difference are you seeing?

For

template <typename...> struct A {};

template <class T>
bool foo(A<T>);

template <class T, class... Args>
bool foo(A<T, Args...>);

template <class Tuple> bool bar()
{
    return foo(Tuple{});
}

A<T> is currently modeled as ElaboratedType. It was TemplateSpecializationType before. Reading comments for ElaboratedType, it looks like sugar type might not be needed here?

ElaboratedType 0xd79c8f0 'A<T>' sugar dependent
`-TemplateSpecializationType 0xd79c8b0 'A<T>' dependent A
  `-TemplateArgument type 'T'
    `-TemplateTypeParmType 0xd79c7f0 'T' dependent depth 0 index 0
      `-TemplateTypeParm 0xd79c768 'T'

[mizvekov]

In D111283#3784615, @ychen wrote:

A<T> is currently modeled as ElaboratedType. It was TemplateSpecializationType before. Reading comments for ElaboratedType, it looks like sugar type might not be needed here?

Ah you might be seeing an ElaboratedTYpe here, where there was none before, perhaps because of https://reviews.llvm.org/D112374, and not because of this patch.

Yeah ElaboratedType is just sugar that should have no effect on partial ordering. But then I think no sugar should have effect on partial ordering. What is stopping you from just looking at the canonical type instead? On a canonical type, you would never see an ElaboratedType node, or a TemplateSpecializationType which is not dependent.

Is this related to the AutoType canonicalization issues we were discussing in the other patch of yours?

[ychen]

In D111283#3784648, @mizvekov wrote:

In D111283#3784615, @ychen wrote:

A<T> is currently modeled as ElaboratedType. It was TemplateSpecializationType before. Reading comments for ElaboratedType, it looks like sugar type might not be needed here?

Ah you might be seeing an ElaboratedTYpe here, where there was none before, perhaps because of https://reviews.llvm.org/D112374, and not because of this patch.

Yeah ElaboratedType is just sugar that should have no effect on partial ordering. But then I think no sugar should have effect on partial ordering. What is stopping you from just looking at the canonical type instead? On a canonical type, you would never see an ElaboratedType node, or a TemplateSpecializationType which is not dependent.

Thanks for the link. I'm not blocked by any of these patches, instead just trying to have a mental model of when to expect the sugared type :-). For partial ordering, the TemplateSpecializationType could be dependent, since the injected template arguments are dependent, I guess that's the reason there is the ElaboratedType?

Is this related to the AutoType canonicalization issues we were discussing in the other patch of yours?

Nope. I found this AST difference while investigating D133683.

[mizvekov]

In D111283#3784663, @ychen wrote:

Thanks for the link. I'm not blocked by any of these patches, instead just trying to have a mental model of when to expect the sugared type :-). For partial ordering, the TemplateSpecializationType could be dependent, since the injected template arguments are dependent, I guess that's the reason there is the ElaboratedType?

The ElaboratedType is a sort of a companion node to other nodes that represent things in the language which can have (non-dependent) nested name qualifiers (a NNS for short) and / or an elaborated type specifier (such as the struct in struct A).

It's only purpose is to carry that extra bit of data, like some external storage really, and it shouldn't affect the semantics of the program once the source code is parsed into an AST.

Here, in your example, the ElaboratedType is there, as a companion to that TemplateSpecializationType, just to say that this template specialization was written without any name qualifiers nor elaboration.

[ychen]

In D111283#3784702, @mizvekov wrote:

In D111283#3784663, @ychen wrote:

Thanks for the link. I'm not blocked by any of these patches, instead just trying to have a mental model of when to expect the sugared type :-). For partial ordering, the TemplateSpecializationType could be dependent, since the injected template arguments are dependent, I guess that's the reason there is the ElaboratedType?

The ElaboratedType is a sort of a companion node to other nodes that represent things in the language which can have (non-dependent) nested name qualifiers (a NNS for short) and / or an elaborated type specifier (such as the struct in struct A).

It's only purpose is to carry that extra bit of data, like some external storage really, and it shouldn't affect the semantics of the program once the source code is parsed into an AST.

Here, in your example, the ElaboratedType is there, as a companion to that TemplateSpecializationType, just to say that this template specialization was written without any name qualifiers nor elaboration.

Very helpful explanation :-).

[alexfh]

In D111283#3783627, @alexfh wrote:

Hi Matheus, an early heads up: this commit is causing clang crashes on some of our code. I'll post more details a bit later.

The stack trace of the failure looks like this:

 #0 0x0000564e08f78aca llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (./clang-after+0x7778aca)
 #1 0x0000564e08f76b78 llvm::sys::RunSignalHandlers() (./clang-after+0x7776b78)                                                                                                                                                                       
 #2 0x0000564e08f10027 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) (./clang-after+0x7710027)
 #3 0x0000564e08f102bd CrashRecoverySignalHandler(int) (./clang-after+0x77102bd)
 #4 0x00007f4773e731c0 __restore_rt
 #5 0x0000564e06591b6b (./clang-after+0x4d91b6b)
 #6 0x0000564e06374ef8 checkDeducedTemplateArguments(clang::ASTContext&, clang::DeducedTemplateArgument const&, clang::DeducedTemplateArgument const&) (./clang-after+0x4b74ef8)
 #7 0x0000564e0636b7b1 DeduceTemplateArgumentsByTypeMatch(clang::Sema&, clang::TemplateParameterList*, clang::QualType, clang::QualType, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, unsigned int, bool, bool) (./clang-after+0x4b6b7b1)
 #8 0x0000564e0636c896 DeduceTemplateArgumentsByTypeMatch(clang::Sema&, clang::TemplateParameterList*, clang::QualType, clang::QualType, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, unsigned int, bool, bool) (./clang-after+0x4b6c896)
 #9 0x0000564e06376430 DeduceTemplateArguments(clang::Sema&, clang::TemplateParameterList*, clang::QualType const*, unsigned int, clang::QualType const*, unsigned int, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, unsigned int, bool) (./clang-after+0x4b76430)
#10 0x0000564e06370895 isAtLeastAsSpecializedAs(clang::Sema&, clang::SourceLocation, clang::FunctionTemplateDecl*, clang::FunctionTemplateDecl*, clang::TemplatePartialOrderingContext, unsigned int, bool) (./clang-after+0x4b70895)
#11 0x0000564e063702c1 clang::Sema::getMoreSpecializedTemplate(clang::FunctionTemplateDecl*, clang::FunctionTemplateDecl*, clang::SourceLocation, clang::TemplatePartialOrderingContext, unsigned int, unsigned int, bool, bool) (./clang-after+0x4b702c1)
#12 0x0000564e0626a07c clang::isBetterOverloadCandidate(clang::Sema&, clang::OverloadCandidate const&, clang::OverloadCandidate const&, clang::SourceLocation, clang::OverloadCandidateSet::CandidateSetKind) (./clang-after+0x4a6a07c)
#13 0x0000564e0625e199 clang::OverloadCandidateSet::BestViableFunction(clang::Sema&, clang::SourceLocation, clang::OverloadCandidate*&) (./clang-after+0x4a5e199)
#14 0x0000564e06272aec clang::Sema::BuildOverloadedCallExpr(clang::Scope*, clang::Expr*, clang::UnresolvedLookupExpr*, clang::SourceLocation, llvm::MutableArrayRef<clang::Expr*>, clang::SourceLocation, clang::Expr*, bool, bool) (./clang-after+0x4a72aec)
#15 0x0000564e05fd3157 clang::Sema::BuildCallExpr(clang::Scope*, clang::Expr*, clang::SourceLocation, llvm::MutableArrayRef<clang::Expr*>, clang::SourceLocation, clang::Expr*, bool, bool) (./clang-after+0x47d3157)
#16 0x0000564e05feb5b6 clang::Sema::ActOnCallExpr(clang::Scope*, clang::Expr*, clang::SourceLocation, llvm::MutableArrayRef<clang::Expr*>, clang::SourceLocation, clang::Expr*) (./clang-after+0x47eb5b6)
#17 0x0000564e063d0bc6 clang::TreeTransform<(anonymous namespace)::TemplateInstantiator>::TransformCallExpr(clang::CallExpr*) (./clang-after+0x4bd0bc6)
#18 0x0000564e063c80f9 clang::Sema::SubstInitializer(clang::Expr*, clang::MultiLevelTemplateArgumentList const&, bool) (./clang-after+0x4bc80f9)
#19 0x0000564e064057c8 clang::Sema::InstantiateVariableInitializer(clang::VarDecl*, clang::VarDecl*, clang::MultiLevelTemplateArgumentList const&) (./clang-after+0x4c057c8)
#20 0x0000564e063fa1be clang::Sema::BuildVariableInstantiation(clang::VarDecl*, clang::VarDecl*, clang::MultiLevelTemplateArgumentList const&, llvm::SmallVector<clang::Sema::LateInstantiatedAttribute, 16u>*, clang::DeclContext*, clang::LocalInstantiationScope*, bool, clang::VarTemplateSpecializationDecl*) (./clang-after+0x4bfa1be)
#21 0x0000564e063f99db clang::TemplateDeclInstantiator::VisitVarDecl(clang::VarDecl*, bool, llvm::ArrayRef<clang::BindingDecl*>*) (./clang-after+0x4bf99db)
#22 0x0000564e0642f599 void llvm::function_ref<void ()>::callback_fn<clang::Sema::SubstDecl(clang::Decl*, clang::DeclContext*, clang::MultiLevelTemplateArgumentList const&)::$_0>(long) (./clang-after+0x4c2f599)
#23 0x0000564e05cc55ee clang::Sema::runWithSufficientStackSpace(clang::SourceLocation, llvm::function_ref<void ()>) (./clang-after+0x44c55ee)
#24 0x0000564e06406ceb clang::Sema::SubstDecl(clang::Decl*, clang::DeclContext*, clang::MultiLevelTemplateArgumentList const&) (./clang-after+0x4c06ceb)
#25 0x0000564e063e91ac clang::TreeTransform<(anonymous namespace)::TemplateInstantiator>::TransformDeclStmt(clang::DeclStmt*) (./clang-after+0x4be91ac)
#26 0x0000564e063e08c7 clang::TreeTransform<(anonymous namespace)::TemplateInstantiator>::TransformCompoundStmt(clang::CompoundStmt*, bool) (./clang-after+0x4be08c7)
#27 0x0000564e063c96be clang::Sema::SubstStmt(clang::Stmt*, clang::MultiLevelTemplateArgumentList const&) (./clang-after+0x4bc96be)
#28 0x0000564e06408b57 clang::Sema::InstantiateFunctionDefinition(clang::SourceLocation, clang::FunctionDecl*, bool, bool, bool) (./clang-after+0x4c08b57)
#29 0x0000564e0640ad95 clang::Sema::PerformPendingInstantiations(bool) (./clang-after+0x4c0ad95)
#30 0x0000564e06408c54 clang::Sema::InstantiateFunctionDefinition(clang::SourceLocation, clang::FunctionDecl*, bool, bool, bool) (./clang-after+0x4c08c54)
#31 0x0000564e0640ad95 clang::Sema::PerformPendingInstantiations(bool) (./clang-after+0x4c0ad95)
#32 0x0000564e05cc7b40 clang::Sema::ActOnEndOfTranslationUnitFragment(clang::Sema::TUFragmentKind) (./clang-after+0x44c7b40)
#33 0x0000564e05cc8877 clang::Sema::ActOnEndOfTranslationUnit() (./clang-after+0x44c8877)
#34 0x0000564e05a344ec clang::Parser::ParseTopLevelDecl(clang::OpaquePtr<clang::DeclGroupRef>&, clang::Sema::ModuleImportState&) (./clang-after+0x42344ec)
#35 0x0000564e05a2effe clang::ParseAST(clang::Sema&, bool, bool) (./clang-after+0x422effe)
#36 0x0000564e057af31a clang::FrontendAction::Execute() (./clang-after+0x3faf31a)
#37 0x0000564e057224e6 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (./clang-after+0x3f224e6)
#38 0x0000564e049d9446 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (./clang-after+0x31d9446)
#39 0x0000564e049cdb40 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (./clang-after+0x31cdb40)
#40 0x0000564e049cbda4 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (./clang-after+0x31cbda4)
#41 0x0000564e058afcf7 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>>, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>>*, bool*) const::$_1>(long) (./clang-after+0x40afcf7)
#42 0x0000564e08f0fef1 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (./clang-after+0x770fef1)
#43 0x0000564e058af64c clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef>>, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>>*, bool*) const (./clang-after+0x40af64c)
#44 0x0000564e05874f77 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (./clang-after+0x4074f77)
#45 0x0000564e05875230 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::__u::pair<int, clang::driver::Command const*>>&, bool) const (./clang-after+0x4075230)
#46 0x0000564e058911af clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::__u::pair<int, clang::driver::Command const*>>&) (./clang-after+0x40911af)
#47 0x0000564e049cb50b clang_main(int, char**) (./clang-after+0x31cb50b)
#48 0x00007f4773d04633 __libc_start_main
#49 0x0000564e049c846a _start (./clang-after+0x31c846a)
clang-after: error: clang frontend command failed with exit code 133 (use -v to see invocation)
clang version google3-trunk (1819d5999c7091781a6441dad4bcede9c554ca90)
Target: x86_64-unknown-linux-gnu

I'm reducing the test case.

[alexfh]

In D111283#3785240, @alexfh wrote:

In D111283#3783627, @alexfh wrote:

Hi Matheus, an early heads up: this commit is causing clang crashes on some of our code. I'll post more details a bit later.

The stack trace of the failure looks like this:

And the assertions-enabled build of clang prints this:

Unexpected sugar-free: TemplateTypeParm
UNREACHABLE executed at llvm-project/clang/lib/AST/ASTContext.cpp:12383!

[alexfh]

In D111283#3785259, @alexfh wrote:

In D111283#3785240, @alexfh wrote:

In D111283#3783627, @alexfh wrote:

Hi Matheus, an early heads up: this commit is causing clang crashes on some of our code. I'll post more details a bit later.

The stack trace of the failure looks like this:

And the assertions-enabled build of clang prints this:

Unexpected sugar-free: TemplateTypeParm
UNREACHABLE executed at llvm-project/clang/lib/AST/ASTContext.cpp:12383!

Reduced test case:

$ cat q.cc
struct a {
  int b;
};
template <typename c, typename d> using e = c d::*;
struct f {
  long b() const;
  template <typename c> c g(e<c, a>) const;
  a h;
};
template <typename c, typename d, typename... i>
void j(e<c, d>, const d *, i...);
template <typename c, typename d> c j(e<c, d>, const d *);
template <typename c> c f::g(e<c, a> k) const { return j(k, &h); }
long f::b() const { return g(&a::b); }

$ ./clang-after q.cc
...
1.      <eof> parser at end of file
2.      q.cc:13:28: instantiating function definition 'f::g<int>'
...
clang-after: error: unable to execute command: Trace/breakpoint trap
clang-after: error: clang frontend command failed due to signal (use -v to see invocation)

Please fix or revert soon.

Thanks!

[alexfh]

I've reverted d200db38637884fd0b421802c6094b2a03ceb29e in 637da9de4c6619c0e179c2c2f0dbfebd08ac2a0f.

And a bit more compact test case:

template <typename T>
using P = int T::*;

template <typename T, typename... A>
void j(P<T>, T, A...);

template <typename T>
void j(P<T>, T);

struct S {
  int b;
};
void g(P<S> k, S s) { j(k, s); }

[mizvekov]

Even simpler:

template <class T> using P = T;

template <class T, class... A> void j(P<T>, T, A...);
template <class T> void j(P<T>, T);

void g() { j(P<int>{}, int{}); }

[davrec]

clang/lib/AST/ASTContext.cpp

11762

Could we just return X here? Would that just default to the old behavior instead of crashing whenever unforeseen cases arise?

[mizvekov]

clang/lib/AST/ASTContext.cpp

11762

No, I think we should enforce the invariants and make sure we are handling everything that can be handled.

Classing TemplateTypeParm as sugar-free was what was wrong and we missed this on the review.

[davrec]

clang/lib/AST/ASTContext.cpp

11762

There might always going to be a few rare corner cases vulnerable to this though, particularly as more types are added and the people adding them don't pay strict attention to how to incorporate them here, and don't write the requisite tests (which seem very difficult to foresee and produce). When those cases arise we will be crashing even though we could produce a perfectly good program with the intended semantics; the only thing that would suffer for most users is slightly less clear diagnostic messages for those rare cases. I think it would be better to let those cases gradually percolate to our attention via bug reports concerning those diagnostics, rather than inconveniencing the user and demanding immediate attention via crashes. Or am I missing something?

[mizvekov]

clang/lib/AST/ASTContext.cpp

11762

I could on the same argument remove all asserts here and just let the program not crash on unforeseen circumstances.

On the other hand, having these asserts here helps us catch bugs not only here, but in other parts of the code. For example uniquing / canonicalization bugs.

If someone changes the properties of a type so that the assumptions here are not valid anymore, it's helpful to have that pointed out soon.

Going for as an example this specific bug, if there werent those asserts / unreachables in place and we had weakened the validation here, it would take a very long time for us to figure out we were making the wrong assumption with regards to TemplateTypeParmType.

I'd rather figure that out sooner on CI / internal testing rather than have a bug created by a user two years from now.

[davrec]

clang/lib/AST/ASTContext.cpp

11762

Yes its nicer to developers to get stack traces and reproductions whenever something goes wrong, and crashing is a good way to get those, but users probably won't be so thrilled about it. Especially given that the main selling point of this patch is that it makes diagnostics nicer for users: isn't it a bit absurd to crash whenever we can't guarantee our diagnostics will be perfect?

And again the real problem is future types not being properly incorporated here and properly tested: i.e. the worry is that this will be a continuing source of crashes, even if we handle all the present types properly.

How about we leave it as an unreachable for now, to help ensure all the present types are handled, but if months or years from now there continue to be crashes due to this, then just return X (while maybe write something to llvm::errs() to encourage users to report it), so we don't make the perfect the enemy of the good.

[vhscampos]

For reference, another small reproducer of the crash, but with a different stack trace than the first example posted here:

// Must compile with -std=c++03 to crash
#include <algorithm>

int main(int, char**)
{
  int i[3] = {1, 2, 3};
  int j[3] = {4, 5, 6};
  std::swap(i, j);

  return 0;
}

Compile with -std=c++03 to reproduce the assertion failure.
We found it by running the libcxx tests.

[mizvekov]

clang/lib/AST/ASTContext.cpp

11762

It's not about crashing when it won't be perfect. We already do these kinds of things, see the FIXMEs around the TemplateArgument and NestedNameSpecifier, where we just return something worse than we wish to, just because we don't have time to implement it now.

These unreachables and asserts here are about testing / documenting our knowledge of the system and making it easier to find problems. These should be impossible to happen in correct code, and if they do happen because of mistakes, fixing them sooner is just going to save us resources.

llvm::errs suggestion I perceive as out of line with current practice in LLVM, we don't and have a system for producing diagnostics for results possibly affected by FIXME and TODO situations and the like, as far as I know, and I am not aware of any discussions in that direction. I expect a lot of complexity and noise if we went this way.
And I think this would have even less chance of working out if we started to incorporate the reporting of violation of invariants into that.

I think even just using raw llvm::errs on clang would be incorrect per design, and could likely break users that parse our output.

I think if months and years from now, if someone stumbled upon an assert firing here and, instead of understanding what is happening and then fixing the code, just removed / weakened the assert, that would simply not be good and I hope a reviewer would stop that from happening :)

[mizvekov]

@alexfh This new revision that I just pushed should be good.

Do you want to give it a look / test, or should we go ahead and merge it?

[mizvekov]

In D111283#3786610, @vhscampos wrote:

For reference, another small reproducer of the crash, but with a different stack trace than the first example posted here:

// Must compile with -std=c++03 to crash
#include <algorithm>

int main(int, char**)
{
  int i[3] = {1, 2, 3};
  int j[3] = {4, 5, 6};
  std::swap(i, j);

  return 0;
}

Compile with -std=c++03 to reproduce the assertion failure.
We found it by running the libcxx tests.

Thanks. Is this a different crash, or is It the same unreachable firing as the one @alexfh reported?

EDIT: NVM, I see it's a different problem, thanks for reporting.

[aaronpuchert]

clang/lib/AST/ASTContext.cpp

11762

I tend to agree that an assertion is appropriate for this. But you could turn this into

assert(false && "...");
return X;

which would still assert, but fall back to something "reasonable" in builds without assertions. The issue with llvm_unreachable is that it translates to __builtin_unreachable() in builds without assertions, and the optimizer takes advantage of that quite heavily. That's why llvm_unreachable is better left to places where we're pretty sure they're unreachable unless something went horribly wrong, such as after switches that handle all enumeration values.

[mizvekov]

clang/lib/AST/ASTContext.cpp

11762

I see, that is reasonable.

But grepping for assert(false in the code base, I see that they are pretty rare, accounting for a bit less than 0.5% in clang/ and 0.3% in llvm/, compared to the total number of asserts. They occur fifty times less than plain llvm_unreachables. I don't remember ever seeing them in practice, so I was not aware this was something we would do.

I feel like in these cases where we are using llvm_unreachable in this patch, I am 100% sure they are really unreachable, unless something went horribly wrong. But I mean I could be completely wrong as well, I must admit, so maybe in those cases that is what went horribly wrong? (Me being wrong I mean)

[mizvekov]

@vhscampos that issue should be fixed now as well, thanks for the report!

[aaronpuchert]

clang/lib/AST/ASTContext.cpp

11762

It depends on how likely you think it is that someone inadvertently violates the invariant without noticing (even after running the tests). For internal invariants or things unlikely to miss in a test, llvm_unreachable should be fine. The less certain you are that mistakes would be hard to make or easy to find, the more preferable would be a fallback. If you think this was a one-off blunder and is unlikely to reoccur, you can also stick to llvm_unreachable. So this was just a suggestion, and since I merely skimmed over the code I'm not the best to judge.

[davrec]

clang/lib/AST/ASTContext.cpp

11762

The assert(false) was a great suggestion. I see the argument for unreachable too.

It seems there are two ways to proceed: unreachable for now, but downgrade to assert(false) if the issue re-arises, or assert(false) for now, upgraded to unreachable later if we find that assert is never tripped.

I'm inclined to prefer the latter, assert(false) for now, assuming there is not a noticeable performance impact on optimized builds with no assertions.

Reason: IIUC, it is not just a) new types, but also b) changes to Sema to support new features that do not construct type sugar properly but are not caught during review, could introduce bugs here that are not detected until a corner case (involving combining instances of such types) is discovered much later. While these bugs do need to be caught and fixed, it would be nice if builds without assertions could continue to work while they were.

But either course is reasonable and @mizekov has the best understanding of how likely such bugs are to find their way in.

[alexfh]

In D111283#3786678, @mizvekov wrote:

@alexfh This new revision that I just pushed should be good.

Do you want to give it a look / test, or should we go ahead and merge it?

Thanks for the fix! If it fixes the test case I provided, that should be enough for now. If it breaks anything else, we'll find this out in a few days after you land the patch.

clang/include/clang/AST/ASTContext.h

public:
   /// Get target-dependent integer value for null pointer which is used for
   /// constant folding.
   uint64_t getTargetNullPointerValue(QualType QT) const;
 
   bool addressSpaceMapManglingFor(LangAS AS) const {
     return AddrSpaceMapMangling || isTargetAddressSpace(AS);
   }
 
+  // For two canonically equal types, return a type which has
+  // the common sugar between them.
+  QualType getCommonSugar(QualType X, QualType Y);
+
 private:
   // Helper for integer ordering
   unsigned getIntegerRank(const Type *T) const;
 
 public:
   //===--------------------------------------------------------------------===//
   //                    Type Compatibility Predicates
   //===--------------------------------------------------------------------===//
 
   /// Compatibility predicates used to check assignment expressions.
   bool typesAreCompatible(QualType T1, QualType T2,
                           bool CompareUnqualified = false); // C99 6.2.7p1
 
   bool propertyTypesAreCompatible(QualType, QualType);
   bool typesAreBlockPointerCompatible(QualType, QualType);
 
   bool isObjCIdType(QualType T) const {
     return T == getObjCIdType();
   }
 
   bool isObjCClassType(QualType T) const {
     return T == getObjCClassType();
   }

clang/include/clang/AST/Type.h

public:
   }
 
   /// Retrieve the ref-qualifier associated with this function type.
   RefQualifierKind getRefQualifier() const {
     return static_cast<RefQualifierKind>(FunctionTypeBits.RefQualifier);
   }
 
   using param_type_iterator = const QualType *;
-  using param_type_range = llvm::iterator_range<param_type_iterator>;
 
-  param_type_range param_types() const {
-    return param_type_range(param_type_begin(), param_type_end());
+  ArrayRef<QualType> param_types() const {
+    return llvm::makeArrayRef(param_type_begin(), param_type_end());
   }
 
   param_type_iterator param_type_begin() const {
     return getTrailingObjects<QualType>();
   }
 
   param_type_iterator param_type_end() const {
     return param_type_begin() + getNumParams();

clang/include/clang/Sema/Sema.h

   SubstAutoTypeSourceInfoDependent(TypeSourceInfo *TypeWithAuto);
 
   /// Completely replace the \c auto in \p TypeWithAuto by
   /// \p Replacement. This does not retain any \c auto type sugar.
   QualType ReplaceAutoType(QualType TypeWithAuto, QualType Replacement);
   TypeSourceInfo *ReplaceAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
                                             QualType Replacement);
 
-  /// Result type of DeduceAutoType.
-  enum DeduceAutoResult {
-    DAR_Succeeded,
-    DAR_Failed,
-    DAR_FailedAlreadyDiagnosed
-  };
-
-  DeduceAutoResult
-  DeduceAutoType(TypeSourceInfo *AutoType, Expr *&Initializer, QualType &Result,
-                 Optional<unsigned> DependentDeductionDepth = None,
-                 bool IgnoreConstraints = false);
-  DeduceAutoResult
-  DeduceAutoType(TypeLoc AutoTypeLoc, Expr *&Initializer, QualType &Result,
-                 Optional<unsigned> DependentDeductionDepth = None,
+  TemplateDeductionResult DeduceAutoType(TypeLoc AutoTypeLoc, Expr *Initializer,
+                                         QualType &Result,
+                                         sema::TemplateDeductionInfo &Info,
+                                         bool DependentDeduction = false,
                                          bool IgnoreConstraints = false);
   void DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init);
   bool DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
                         bool Diagnose = true);
 
   /// Declare implicit deduction guides for a class template if we've
   /// not already done so.
   void DeclareImplicitDeductionGuides(TemplateDecl *Template,
                                       SourceLocation Loc);
 
   QualType DeduceTemplateSpecializationFromInitializer(
       TypeSourceInfo *TInfo, const InitializedEntity &Entity,
       const InitializationKind &Kind, MultiExprArg Init);
 
   QualType deduceVarTypeFromInitializer(VarDecl *VDecl, DeclarationName Name,
                                         QualType Type, TypeSourceInfo *TSI,
                                         SourceRange Range, bool DirectInit,
                                         Expr *Init);
 
   TypeLoc getReturnTypeLoc(FunctionDecl *FD) const;
 
   bool DeduceFunctionTypeFromReturnExpr(FunctionDecl *FD,
-                                        SourceLocation ReturnLoc,
-                                        Expr *&RetExpr, AutoType *AT);
+                                        SourceLocation ReturnLoc, Expr *RetExpr,
+                                        AutoType *AT);
 
   FunctionTemplateDecl *getMoreSpecializedTemplate(
       FunctionTemplateDecl *FT1, FunctionTemplateDecl *FT2, SourceLocation Loc,
       TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1,
       unsigned NumCallArguments2, bool Reversed = false);
   UnresolvedSetIterator
   getMostSpecialized(UnresolvedSetIterator SBegin, UnresolvedSetIterator SEnd,
                      TemplateSpecCandidateSet &FailedCandidates,

clang/lib/AST/ASTContext.cpp

return hasSameType(T, U) ||
          (getLangOpts().CPlusPlus17 &&
           hasSameType(getFunctionTypeWithExceptionSpec(T, EST_None),
                       getFunctionTypeWithExceptionSpec(U, EST_None)));
 }
 
 QualType ASTContext::getFunctionTypeWithoutPtrSizes(QualType T) {
   if (const auto *Proto = T->getAs<FunctionProtoType>()) {
     QualType RetTy = removePtrSizeAddrSpace(Proto->getReturnType());
-    SmallVector<QualType, 16> Args(Proto->param_types());
+    SmallVector<QualType, 16> Args(Proto->param_types().size());
     for (unsigned i = 0, n = Args.size(); i != n; ++i)
-      Args[i] = removePtrSizeAddrSpace(Args[i]);
+      Args[i] = removePtrSizeAddrSpace(Proto->param_types()[i]);
     return getFunctionType(RetTy, Args, Proto->getExtProtoInfo());
   }
 
   if (const FunctionNoProtoType *Proto = T->getAs<FunctionNoProtoType>()) {
     QualType RetTy = removePtrSizeAddrSpace(Proto->getReturnType());
     return getFunctionNoProtoType(RetTy, Proto->getExtInfo());
   }
 

 
 unsigned ASTContext::getTargetAddressSpace(LangAS AS) const {
   if (isTargetAddressSpace(AS))
     return toTargetAddressSpace(AS);
   else
     return (*AddrSpaceMap)[(unsigned)AS];
 }
 
+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) {
+    QualType X = Xs[I], Y = Ys[I];
+    if (!Ctx.hasSameType(X, Y)) {
+      assert(Ctx.hasSameUnqualifiedType(X, Y));
+      auto XQuals = X.getCVRQualifiers(), YQuals = Y.getCVRQualifiers();
+      X.addFastQualifiers(YQuals & ~XQuals);
+      Y.addFastQualifiers(XQuals & ~YQuals);
+    }
+    Rs[I] = Ctx.getCommonSugar(X, Y);
+  }
+  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());
+  switch (X.getKind()) {
+  case TemplateArgument::ArgKind::Type:
+    return TemplateArgument(Ctx.getCommonSugar(X.getAsType(), Y.getAsType()));
+  case TemplateArgument::ArgKind::NullPtr:
+    return TemplateArgument(
+        Ctx.getCommonSugar(X.getNullPtrType(), Y.getNullPtrType()), true);
+  default:
+    return X;
+  }
+  llvm_unreachable("");
+}
+
+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]);
+  return R;
+}
+
+template <class T>
+static ElaboratedTypeKeyword getCommonTypeKeyword(const T *X, const T *Y) {
+  return X->getKeyword() == Y->getKeyword() ? X->getKeyword()
+                                            : ElaboratedTypeKeyword::ETK_None;
+}
+
+template <class T>
+static NestedNameSpecifier *getCommonNNS(ASTContext &Ctx, const T *X,
+                                         const T *Y) {
+  return X->getQualifier() == Y->getQualifier()
+             ? X->getQualifier()
+             : Ctx.getCanonicalNestedNameSpecifier(X->getQualifier());
+}
+
+template <class T>
+static QualType getCommonElementType(ASTContext &Ctx, const T *X, const T *Y) {
+  return Ctx.getCommonSugar(X->getElementType(), Y->getElementType());
+}
+
+template <class T>
+static QualType getCommonPointeeType(ASTContext &Ctx, const T *X, const T *Y) {
+  return Ctx.getCommonSugar(X->getPointeeType(), Y->getPointeeType());
+}
+
+template <class T> static auto *getCommonSizeExpr(T *X, T *Y) {
+  assert(X->getSizeExpr() == Y->getSizeExpr());
+  return X->getSizeExpr();
+}
+
+static auto getCommonSizeModifier(const ArrayType *X, const ArrayType *Y) {
+  assert(X->getSizeModifier() == Y->getSizeModifier());
+  return X->getSizeModifier();
+}
+
+static auto getCommonIndexTypeCVRQualifiers(const ArrayType *X,
+                                            const ArrayType *Y) {
+  assert(X->getIndexTypeCVRQualifiers() == Y->getIndexTypeCVRQualifiers());
+  return X->getIndexTypeCVRQualifiers();
+}
+
+static QualType getCommonCanonicalType(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")
+#define TYPE(Class, Base)
+#include "clang/AST/TypeNodes.inc"
+
+#define SUGAR_FREE_TYPE(Class) UNEXPECTED_TYPE(Class, "sugar-free")
+    SUGAR_FREE_TYPE(Builtin)
+    SUGAR_FREE_TYPE(Decltype)
+    SUGAR_FREE_TYPE(DeducedTemplateSpecialization)
+    SUGAR_FREE_TYPE(DependentExtInt)
+    SUGAR_FREE_TYPE(Enum)
+    SUGAR_FREE_TYPE(ExtInt)
+    SUGAR_FREE_TYPE(ObjCInterface)
+    SUGAR_FREE_TYPE(Record)
+    SUGAR_FREE_TYPE(SubstTemplateTypeParmPack)
+    SUGAR_FREE_TYPE(TemplateTypeParm)
+    SUGAR_FREE_TYPE(UnresolvedUsing)
+#undef SUGAR_FREE_TYPE
+#define NON_UNIQUE_TYPE(Class) UNEXPECTED_TYPE(Class, "non-unique")
+    NON_UNIQUE_TYPE(TypeOfExpr)
+    NON_UNIQUE_TYPE(VariableArray)
+#undef NON_UNIQUE_TYPE
+
+    UNEXPECTED_TYPE(TypeOf, "sugar")
+
+#undef UNEXPECTED_TYPE
+
+  case Type::Auto: {
+    const auto *AX = cast<AutoType>(X), *AY = cast<AutoType>(Y);
+    assert(AX->getDeducedType().isNull());
+    assert(AY->getDeducedType().isNull());
+    assert(AX->getKeyword() == AY->getKeyword());
+    assert(AX->isInstantiationDependentType() ==
+           AY->isInstantiationDependentType());
+    assert(AX->getTypeConstraintConcept() == AY->getTypeConstraintConcept());
+    auto As = getCommonTemplateArguments(Ctx, AX->getTypeConstraintArguments(),
+                                         AY->getTypeConstraintArguments());
+    return Ctx.getAutoType(QualType(), AX->getKeyword(),
+                           AX->isInstantiationDependentType(),
+                           AX->containsUnexpandedParameterPack(),
+                           AX->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::DependentSizedArray: {
+    const auto *AX = cast<DependentSizedArrayType>(X),
+               *AY = cast<DependentSizedArrayType>(Y);
+    return Ctx.getDependentSizedArrayType(
+        getCommonElementType(Ctx, AX, AY), getCommonSizeExpr(AX, AY),
+        getCommonSizeModifier(AX, AY), getCommonIndexTypeCVRQualifiers(AX, AY),
+        AX->getBracketsRange() == AY->getBracketsRange()
+            ? AX->getBracketsRange()
+            : SourceRange());
+  }
+  case Type::ConstantArray: {
+    const auto *AX = cast<ConstantArrayType>(X),
+               *AY = cast<ConstantArrayType>(Y);
+    assert(AX->getSize() == AY->getSize());
+    return Ctx.getConstantArrayType(getCommonElementType(Ctx, AX, AY),
+                                    AX->getSize(), getCommonSizeExpr(AX, AY),
+                                    getCommonSizeModifier(AX, AY),
+                                    getCommonIndexTypeCVRQualifiers(AX, AY));
+  }
+  case Type::Atomic: {
+    const auto *AX = cast<AtomicType>(X), *AY = cast<AtomicType>(Y);
+    return Ctx.getAtomicType(
+        Ctx.getCommonSugar(AX->getValueType(), AY->getValueType()));
+  }
+  case Type::Complex: {
+    const auto *CX = cast<ComplexType>(X), *CY = cast<ComplexType>(Y);
+    return Ctx.getComplexType(getCommonElementType(Ctx, CX, CY));
+  }
+  case Type::Pointer: {
+    const auto *PX = cast<PointerType>(X), *PY = cast<PointerType>(Y);
+    return Ctx.getPointerType(getCommonPointeeType(Ctx, PX, PY));
+  }
+  case Type::BlockPointer: {
+    const auto *PX = cast<BlockPointerType>(X), *PY = cast<BlockPointerType>(Y);
+    return Ctx.getBlockPointerType(getCommonPointeeType(Ctx, PX, PY));
+  }
+  case Type::ObjCObjectPointer: {
+    const auto *PX = cast<ObjCObjectPointerType>(X),
+               *PY = cast<ObjCObjectPointerType>(Y);
+    return Ctx.getObjCObjectPointerType(getCommonPointeeType(Ctx, PX, PY));
+  }
+  case Type::MemberPointer: {
+    const auto *PX = cast<MemberPointerType>(X),
+               *PY = cast<MemberPointerType>(Y);
+    return Ctx.getMemberPointerType(
+        getCommonPointeeType(Ctx, PX, PY),
+        Ctx.getCommonSugar(QualType(PX->getClass(), 0),
+                           QualType(PY->getClass(), 0))
+            .getTypePtr());
+  }
+  case Type::LValueReference: {
+    const auto *PX = cast<LValueReferenceType>(X),
+               *PY = cast<LValueReferenceType>(Y);
+    return Ctx.getLValueReferenceType(getCommonPointeeType(Ctx, PX, PY),
+                                      PX->isSpelledAsLValue() &&
+                                          PY->isSpelledAsLValue());
+  }
+  case Type::RValueReference: {
+    const auto *PX = cast<RValueReferenceType>(X),
+               *PY = cast<RValueReferenceType>(Y);
+    return Ctx.getRValueReferenceType(getCommonPointeeType(Ctx, PX, PY));
+  }
+  case Type::DependentAddressSpace: {
+    const auto *PX = cast<DependentAddressSpaceType>(X),
+               *PY = cast<DependentAddressSpaceType>(Y);
+    return Ctx.getDependentAddressSpaceType(getCommonPointeeType(Ctx, PX, PY),
+                                            PX->getAddrSpaceExpr(),
+                                            getCommonAttrLoc(PX, PY));
+  }
+  case Type::FunctionNoProto: {
+    const auto *FX = cast<FunctionNoProtoType>(X),
+               *FY = cast<FunctionNoProtoType>(Y);
+    assert(FX->getExtInfo() == FY->getExtInfo());
+    return Ctx.getFunctionNoProtoType(
+        Ctx.getCommonSugar(FX->getReturnType(), FY->getReturnType()),
+        FX->getExtInfo());
+  }
+  case Type::FunctionProto: {
+    const auto *FX = cast<FunctionProtoType>(X),
+               *FY = cast<FunctionProtoType>(Y);
+    FunctionProtoType::ExtProtoInfo EPIX = FX->getExtProtoInfo(),
+                                    EPIY = FY->getExtProtoInfo();
+    assert(EPIX.ExceptionSpec.Type == EPIY.ExceptionSpec.Type);
+    assert(EPIX.ExceptionSpec.NoexceptExpr == EPIY.ExceptionSpec.NoexceptExpr);
+    assert(EPIX.ExceptionSpec.SourceDecl == EPIY.ExceptionSpec.SourceDecl);
+    assert(EPIX.ExceptionSpec.SourceTemplate ==
+           EPIY.ExceptionSpec.SourceTemplate);
+    assert(EPIX.ExtInfo == EPIY.ExtInfo);
+    assert(EPIX.ExtParameterInfos == EPIY.ExtParameterInfos);
+    assert(EPIX.RefQualifier == EPIY.RefQualifier);
+    assert(EPIX.TypeQuals == EPIY.TypeQuals);
+    assert(EPIX.Variadic == EPIY.Variadic);
+
+    if (EPIX.EllipsisLoc != EPIY.EllipsisLoc)
+      EPIX.EllipsisLoc = SourceLocation();
+    EPIX.HasTrailingReturn = EPIX.HasTrailingReturn && EPIY.HasTrailingReturn;
+
+    QualType R = Ctx.getCommonSugar(FX->getReturnType(), FY->getReturnType());
+    auto P = getCommonTypeArray(Ctx, FX->param_types(), FY->param_types(),
+                                /*Unqualified=*/true);
+
+    if (EPIX.ExceptionSpec.Exceptions.size() ==
+        EPIY.ExceptionSpec.Exceptions.size()) {
+      auto E = getCommonTypeArray(Ctx, EPIX.ExceptionSpec.Exceptions,
+                                  EPIY.ExceptionSpec.Exceptions);
+      EPIX.ExceptionSpec.Exceptions = E;
+      return Ctx.getFunctionType(R, P, EPIX);
+    } else {
+      if (EPIY.ExceptionSpec.Exceptions.size() >
+          EPIX.ExceptionSpec.Exceptions.size())
+        EPIX.ExceptionSpec.Exceptions = EPIY.ExceptionSpec.Exceptions;
+      return Ctx.getFunctionType(R, P, EPIX);
+    }
+  }
+  case Type::ObjCObject: {
+    const auto *OX = cast<ObjCObjectType>(X), *OY = cast<ObjCObjectType>(Y);
+    assert(llvm::equal(OX->getProtocols(), OY->getProtocols()));
+    auto TAs = getCommonTypeArray(Ctx, OX->getTypeArgsAsWritten(),
+                                  OY->getTypeArgsAsWritten());
+    return Ctx.getObjCObjectType(
+        Ctx.getCommonSugar(OX->getBaseType(), OY->getBaseType()), TAs,
+        OX->getProtocols(),
+        OX->isKindOfTypeAsWritten() && OY->isKindOfTypeAsWritten());
+  }
+  case Type::ConstantMatrix: {
+    const auto *MX = cast<ConstantMatrixType>(X),
+               *MY = cast<ConstantMatrixType>(Y);
+    assert(MX->getNumRows() == MY->getNumRows());
+    assert(MX->getNumColumns() == MY->getNumColumns());
+    return Ctx.getConstantMatrixType(getCommonElementType(Ctx, MX, MY),
+                                     MX->getNumRows(), MX->getNumColumns());
+  }
+  case Type::DependentSizedMatrix: {
+    const auto *MX = cast<DependentSizedMatrixType>(X),
+               *MY = cast<DependentSizedMatrixType>(Y);
+    assert(MX->getRowExpr() == MY->getRowExpr());
+    assert(MX->getColumnExpr() == MY->getColumnExpr());
+    return Ctx.getDependentSizedMatrixType(
+        getCommonElementType(Ctx, MX, MY), MX->getRowExpr(),
+        MX->getColumnExpr(), getCommonAttrLoc(MX, MY));
+  }
+  case Type::Vector: {
+    const auto *VX = cast<VectorType>(X), *VY = cast<VectorType>(Y);
+    assert(VX->getNumElements() == VY->getNumElements());
+    assert(VX->getVectorKind() == VY->getVectorKind());
+    return Ctx.getVectorType(getCommonElementType(Ctx, VX, VY),
+                             VX->getNumElements(), VX->getVectorKind());
+  }
+  case Type::ExtVector: {
+    const auto *VX = cast<ExtVectorType>(X), *VY = cast<ExtVectorType>(Y);
+    assert(VX->getNumElements() == VY->getNumElements());
+    return Ctx.getExtVectorType(getCommonElementType(Ctx, VX, VY),
+                                VX->getNumElements());
+  }
+  case Type::DependentSizedExtVector: {
+    const auto *VX = cast<DependentSizedExtVectorType>(X),
+               *VY = cast<DependentSizedExtVectorType>(Y);
+    return Ctx.getDependentSizedExtVectorType(getCommonElementType(Ctx, VX, VY),
+                                              getCommonSizeExpr(VX, VY),
+                                              getCommonAttrLoc(VX, VY));
+  }
+  case Type::DependentVector: {
+    const auto *VX = cast<DependentVectorType>(X),
+               *VY = cast<DependentVectorType>(Y);
+    assert(VX->getVectorKind() == VY->getVectorKind());
+    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);
+    assert(IX->getDecl() == IY->getDecl());
+    return Ctx.getInjectedClassNameType(
+        IX->getDecl(), Ctx.getCommonSugar(IX->getInjectedSpecializationType(),
+                                          IY->getInjectedSpecializationType()));
+  }
+  case Type::TemplateSpecialization: {
+    const auto *TX = cast<TemplateSpecializationType>(X),
+               *TY = cast<TemplateSpecializationType>(Y);
+    assert(TX->getTemplateName().getAsVoidPointer() ==
+           TY->getTemplateName().getAsVoidPointer());
+    auto As = getCommonTemplateArguments(Ctx, TX->template_arguments(),
+                                         TY->template_arguments());
+    return Ctx.getTemplateSpecializationType(TX->getTemplateName(), As);
+  }
+  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());
+  }
+  case Type::DependentTemplateSpecialization: {
+    const auto *TX = cast<DependentTemplateSpecializationType>(X),
+               *TY = cast<DependentTemplateSpecializationType>(Y);
+    assert(TX->getIdentifier() == TY->getIdentifier());
+    auto As = getCommonTemplateArguments(Ctx, TX->template_arguments(),
+                                         TY->template_arguments());
+    return Ctx.getDependentTemplateSpecializationType(
+        getCommonTypeKeyword(TX, TY), getCommonNNS(Ctx, TX, TY),
+        TX->getIdentifier(), As);
+  }
+  case Type::UnaryTransform: {
+    const auto *TX = cast<UnaryTransformType>(X),
+               *TY = cast<UnaryTransformType>(Y);
+    assert(TX->getUTTKind() == TY->getUTTKind());
+    return Ctx.getUnaryTransformType(
+        Ctx.getCommonSugar(TX->getBaseType(), TY->getBaseType()),
+        Ctx.getCommonSugar(TX->getUnderlyingType(), TY->getUnderlyingType()),
+        TX->getUTTKind());
+  }
+  case Type::PackExpansion: {
+    const auto *PX = cast<PackExpansionType>(X),
+               *PY = cast<PackExpansionType>(Y);
+    return Ctx.getPackExpansionType(
+        Ctx.getCommonSugar(PX->getPattern(), PY->getPattern()),
+        PX->getNumExpansions(), false);
+  }
+  case Type::Pipe: {
+    const auto *PX = cast<PipeType>(X), *PY = cast<PipeType>(Y);
+    assert(PX->isReadOnly() == PY->isReadOnly());
+    auto MP = PX->isReadOnly() ? &ASTContext::getReadPipeType
+                               : &ASTContext::getWritePipeType;
+    return (Ctx.*MP)(getCommonElementType(Ctx, PX, PY));
+  }
+  }
+  llvm_unreachable("Unknown Type Class");
+}
+
+static auto unwrapSugar(QualType &T) {
+  SmallVector<QualType, 8> R;
+  while (true) {
+    QualType NT = T->getLocallyUnqualifiedSingleStepDesugaredType();
+    NT.addFastQualifiers(T.getLocalFastQualifiers());
+    if (T == NT)
+      break;
+    R.push_back(T);
+    T = NT;
+  }
+  return R;
+}
+
+QualType ASTContext::getCommonSugar(QualType X, QualType Y) {
+  assert(hasSameType(X, Y));
+  if (X == Y || X.isCanonical())
+    return X;
+  if (Y.isCanonical())
+    return Y;
+
+  QualType Orig = X;
+  (void)Orig;
+  {
+    auto Xs = ::unwrapSugar(X), Ys = ::unwrapSugar(Y);
+    if (X == Y) {
+      while (!Xs.empty() && !Ys.empty() && Xs.back() == Ys.back()) {
+        X = Xs.pop_back_val();
+        Y = Ys.pop_back_val();
+      }
+      assert(hasSameType(X, Orig));
+      return X;
+    }
+  }
+
+  auto Quals = X.getLocalFastQualifiers();
+  assert(Quals == Y.getLocalFastQualifiers());
+
+  X = ::getCommonCanonicalType(*this, X.getTypePtr(), Y.getTypePtr());
+  X.addFastQualifiers(Quals);
+  assert(hasSameType(X, Orig));
+  return X;
+}
+
 QualType ASTContext::getCorrespondingSaturatedType(QualType Ty) const {
   assert(Ty->isFixedPointType());
 
   if (Ty->isSaturatedFixedPointType()) return Ty;
 
   switch (Ty->castAs<BuiltinType>()->getKind()) {
     default:
       llvm_unreachable("Not a fixed point type!");

clang/lib/Sema/SemaDecl.cpp

if (!getLangOpts().CPlusPlus &&
     const FunctionType *OldFuncType = OldQType->getAs<FunctionType>();
     const FunctionType *NewFuncType = NewQType->getAs<FunctionType>();
     const FunctionProtoType *OldProto = nullptr;
     if (MergeTypeWithOld && isa<FunctionNoProtoType>(NewFuncType) &&
         (OldProto = dyn_cast<FunctionProtoType>(OldFuncType))) {
       // The old declaration provided a function prototype, but the
       // new declaration does not. Merge in the prototype.
       assert(!OldProto->hasExceptionSpec() && "Exception spec in C");
-      SmallVector<QualType, 16> ParamTypes(OldProto->param_types());
-      NewQType =
-          Context.getFunctionType(NewFuncType->getReturnType(), ParamTypes,
+      NewQType = Context.getFunctionType(NewFuncType->getReturnType(),
+                                         OldProto->param_types(),
                                          OldProto->getExtProtoInfo());
       New->setType(NewQType);
       New->setHasInheritedPrototype();
 
       // Synthesize parameters with the same types.
       SmallVector<ParmVarDecl*, 16> Params;
       for (const auto &ParamType : OldProto->param_types()) {
         ParmVarDecl *Param = ParmVarDecl::Create(Context, New, SourceLocation(),
                                                  SourceLocation(), nullptr,
QualType Sema::deduceVarTypeFromInitializer(VarDecl *VDecl,
   //   is present, e has type cv A
   if (VDecl && isa<DecompositionDecl>(VDecl) &&
       Context.hasSameUnqualifiedType(Type, Context.getAutoDeductType()) &&
       DeduceInit->getType()->isConstantArrayType())
     return Context.getQualifiedType(DeduceInit->getType(),
                                     Type.getQualifiers());
 
   QualType DeducedType;
-  if (DeduceAutoType(TSI, DeduceInit, DeducedType) == DAR_Failed) {
+  TemplateDeductionInfo Info(DeduceInit->getExprLoc());
+  TemplateDeductionResult Result =
+      DeduceAutoType(TSI->getTypeLoc(), DeduceInit, DeducedType, Info);
+  if (Result != TDK_Success && Result != TDK_MiscellaneousDeductionFailure) {
     if (!IsInitCapture)
       DiagnoseAutoDeductionFailure(VDecl, DeduceInit);
     else if (isa<InitListExpr>(Init))
       Diag(Range.getBegin(),
            diag::err_init_capture_deduction_failure_from_init_list)
           << VN
           << (DeduceInit->getType().isNull() ? TSI->getType()
                                              : DeduceInit->getType())

clang/lib/Sema/SemaExprCXX.cpp

Sema::BuildCXXTypeConstructExpr(TypeSourceInfo *TInfo,
   //   If the type is a placeholder for a deduced class type, [...perform class
   //   template argument deduction...]
   DeducedType *Deduced = Ty->getContainedDeducedType();
   if (Deduced && isa<DeducedTemplateSpecializationType>(Deduced)) {
     Ty = DeduceTemplateSpecializationFromInitializer(TInfo, Entity,
                                                      Kind, Exprs);
     if (Ty.isNull())
       return ExprError();
     Entity = InitializedEntity::InitializeTemporary(TInfo, Ty);
   }
 
   if (Ty->isDependentType() || CallExpr::hasAnyTypeDependentArguments(Exprs)) {
     // FIXME: CXXUnresolvedConstructExpr does not model list-initialization
     // directly. We work around this by dropping the locations of the braces.
     SourceRange Locs = ListInitialization
                            ? SourceRange()
                            : SourceRange(LParenOrBraceLoc, RParenOrBraceLoc);
     return CXXUnresolvedConstructExpr::Create(Context, Ty.getNonReferenceType(),
if (NumInits > 1) {
                             diag::err_auto_new_ctor_multiple_expressions)
                        << AllocType << TypeRange);
     }
     if (Braced && !getLangOpts().CPlusPlus17)
       Diag(Initializer->getBeginLoc(), diag::ext_auto_new_list_init)
           << AllocType << TypeRange;
     Expr *Deduce = Inits[0];
     QualType DeducedType;
-    if (DeduceAutoType(AllocTypeInfo, Deduce, DeducedType) == DAR_Failed)
+    TemplateDeductionInfo Info(Deduce->getExprLoc());
+    TemplateDeductionResult Result =
+        DeduceAutoType(AllocTypeInfo->getTypeLoc(), Deduce, DeducedType, Info);
+    if (Result != TDK_Success && Result != TDK_MiscellaneousDeductionFailure)
       return ExprError(Diag(StartLoc, diag::err_auto_new_deduction_failure)
-                       << AllocType << Deduce->getType()
-                       << TypeRange << Deduce->getSourceRange());
+                       << AllocType << Deduce->getType() << TypeRange
+                       << Deduce->getSourceRange());
     if (DeducedType.isNull())
       return ExprError();
     AllocType = DeducedType;
   }
 
   // Per C++0x [expr.new]p5, the type being constructed may be a
   // typedef of an array type.
   if (!ArraySize) {
     if (const ConstantArrayType *Array
                               = Context.getAsConstantArrayType(AllocType)) {

clang/lib/Sema/SemaStmt.cpp

if (DeclStmt *DS = dyn_cast<DeclStmt>(First)) {
       // declare identifiers for objects having storage class 'auto' or
       // 'register'.
       if (!D->hasLocalStorage())
         return StmtError(Diag(D->getLocation(),
                               diag::err_non_local_variable_decl_in_for));
 
       // If the type contained 'auto', deduce the 'auto' to 'id'.
       if (FirstType->getContainedAutoType()) {
-        OpaqueValueExpr OpaqueId(D->getLocation(), Context.getObjCIdType(),
-                                 VK_PRValue);
+        SourceLocation Loc = D->getLocation();
+        OpaqueValueExpr OpaqueId(Loc, Context.getObjCIdType(), VK_PRValue);
         Expr *DeducedInit = &OpaqueId;
-        if (DeduceAutoType(D->getTypeSourceInfo(), DeducedInit, FirstType) ==
-                DAR_Failed)
+        TemplateDeductionInfo Info(Loc);
+        FirstType = QualType();
+        TemplateDeductionResult Result = DeduceAutoType(
+            D->getTypeSourceInfo()->getTypeLoc(), DeducedInit, FirstType, Info);
+        if (Result != TDK_Success &&
+            Result != TDK_MiscellaneousDeductionFailure)
           DiagnoseAutoDeductionFailure(D, DeducedInit);
         if (FirstType.isNull()) {
           D->setInvalidDecl();
           return StmtError();
         }
 
         D->setType(FirstType);
 
if (!Res.isUsable()) {
       return true;
     }
     Init = Res.get();
   }
 
   // Deduce the type for the iterator variable now rather than leaving it to
   // AddInitializerToDecl, so we can produce a more suitable diagnostic.
   QualType InitType;
-  if ((!isa<InitListExpr>(Init) && Init->getType()->isVoidType()) ||
-      SemaRef.DeduceAutoType(Decl->getTypeSourceInfo(), Init, InitType) ==
-          Sema::DAR_Failed)
+  if (!isa<InitListExpr>(Init) && Init->getType()->isVoidType()) {
+    SemaRef.Diag(Loc, DiagID) << Init->getType();
+  } else {
+    TemplateDeductionInfo Info(Init->getExprLoc());
+    Sema::TemplateDeductionResult Result = SemaRef.DeduceAutoType(
+        Decl->getTypeSourceInfo()->getTypeLoc(), Init, InitType, Info);
+    if (Result != Sema::TDK_Success &&
+        Result != Sema::TDK_MiscellaneousDeductionFailure)
       SemaRef.Diag(Loc, DiagID) << Init->getType();
+  }
+
   if (InitType.isNull()) {
     Decl->setInvalidDecl();
     return true;
   }
   Decl->setType(InitType);
 
   // In ARC, infer lifetime.
   // FIXME: ARC may want to turn this into 'const __unsafe_unretained' if
return FD->getTypeSourceInfo()
       .getAsAdjusted<FunctionProtoTypeLoc>()
       .getReturnLoc();
 }
 
 /// Deduce the return type for a function from a returned expression, per
 /// C++1y [dcl.spec.auto]p6.
 bool Sema::DeduceFunctionTypeFromReturnExpr(FunctionDecl *FD,
                                             SourceLocation ReturnLoc,
-                                            Expr *&RetExpr,
-                                            AutoType *AT) {
+                                            Expr *RetExpr, AutoType *AT) {
   // If this is the conversion function for a lambda, we choose to deduce it
   // type from the corresponding call operator, not from the synthesized return
   // statement within it. See Sema::DeduceReturnType.
   if (isLambdaConversionOperator(FD))
     return false;
 
-  TypeLoc OrigResultType = getReturnTypeLoc(FD);
-  QualType Deduced;
-
   if (RetExpr && isa<InitListExpr>(RetExpr)) {
     //  If the deduction is for a return statement and the initializer is
     //  a braced-init-list, the program is ill-formed.
     Diag(RetExpr->getExprLoc(),
          getCurLambda() ? diag::err_lambda_return_init_list
                         : diag::err_auto_fn_return_init_list)
         << RetExpr->getSourceRange();
     return true;
   }
 
   if (FD->isDependentContext()) {
     // C++1y [dcl.spec.auto]p12:
     //   Return type deduction [...] occurs when the definition is
     //   instantiated even if the function body contains a return
     //   statement with a non-type-dependent operand.
     assert(AT->isDeduced() && "should have deduced to dependent type");
     return false;
   }
 
-  if (RetExpr) {
+  //  In the case of a return with no operand, the initializer is considered
+  //  to be void().
+  CXXScalarValueInitExpr VoidVal(Context.VoidTy, nullptr, SourceLocation());
+  if (!RetExpr)
+    RetExpr = &VoidVal;
+
+  QualType Deduced = AT->getDeducedType();
+  {
+    TypeLoc OrigResultType = getReturnTypeLoc(FD);
     //  Otherwise, [...] deduce a value for U using the rules of template
     //  argument deduction.
-    DeduceAutoResult DAR = DeduceAutoType(OrigResultType, RetExpr, Deduced);
-
-    if (DAR == DAR_Failed && !FD->isInvalidDecl())
-      Diag(RetExpr->getExprLoc(), diag::err_auto_fn_deduction_failure)
-        << OrigResultType.getType() << RetExpr->getType();
-
-    if (DAR != DAR_Succeeded)
+    TemplateDeductionInfo Info(RetExpr->getExprLoc());
+    TemplateDeductionResult Res =
+        DeduceAutoType(OrigResultType, RetExpr, Deduced, Info);
+    if (Res != TDK_Success && FD->isInvalidDecl())
       return true;
-
-    // If a local type is part of the returned type, mark its fields as
-    // referenced.
-    LocalTypedefNameReferencer Referencer(*this);
-    Referencer.TraverseType(RetExpr->getType());
-  } else {
-    //  In the case of a return with no operand, the initializer is considered
-    //  to be void().
-    //
-    // Deduction here can only succeed if the return type is exactly 'cv auto'
-    // or 'decltype(auto)', so just check for that case directly.
-    if (!OrigResultType.getType()->getAs<AutoType>()) {
+    switch (Res) {
+    case TDK_Success:
+      break;
+    case TDK_MiscellaneousDeductionFailure:
+      return true;
+    case TDK_Inconsistent: {
+      //  If a function with a declared return type that contains a placeholder
+      //  type
+      //  has multiple return statements, the return type is deduced for each
+      //  return statement. [...] if the type deduced is not the same in each
+      //  deduction, the program is ill-formed.
+      const LambdaScopeInfo *LambdaSI = getCurLambda();
+      if (LambdaSI && LambdaSI->HasImplicitReturnType)
+        Diag(ReturnLoc, diag::err_typecheck_missing_return_type_incompatible)
+            << Info.SecondArg << Info.FirstArg << true /*IsLambda*/;
+      else
+        Diag(ReturnLoc, diag::err_auto_fn_different_deductions)
+            << (AT->isDecltypeAuto() ? 1 : 0) << Info.SecondArg
+            << Info.FirstArg;
+      return true;
+    }
+    default:
+      if (!Info.SecondArg.isNull() && Info.SecondArg.getAsType()->isVoidType())
         Diag(ReturnLoc, diag::err_auto_fn_return_void_but_not_auto)
             << OrigResultType.getType();
+      else
+        Diag(RetExpr->getExprLoc(), diag::err_auto_fn_deduction_failure)
+            << OrigResultType.getType() << Info.SecondArg;
       return true;
     }
-    // We always deduce U = void in this case.
-    Deduced = SubstAutoType(OrigResultType.getType(), Context.VoidTy);
-    if (Deduced.isNull())
-      return true;
   }
 
+  // If a local type is part of the returned type, mark its fields as
+  // referenced.
+  LocalTypedefNameReferencer(*this).TraverseType(RetExpr->getType());
+
   // CUDA: Kernel function must have 'void' return type.
-  if (getLangOpts().CUDA)
-    if (FD->hasAttr<CUDAGlobalAttr>() && !Deduced->isVoidType()) {
-      Diag(FD->getLocation(), diag::err_kern_type_not_void_return)
-          << FD->getType() << FD->getSourceRange();
-      return true;
-    }
+  if (getLangOpts().CUDA && FD->hasAttr<CUDAGlobalAttr>() &&
+      !Deduced->isVoidType()) {
 
-  //  If a function with a declared return type that contains a placeholder type
-  //  has multiple return statements, the return type is deduced for each return
-  //  statement. [...] if the type deduced is not the same in each deduction,
-  //  the program is ill-formed.
-  QualType DeducedT = AT->getDeducedType();
-  if (!DeducedT.isNull() && !FD->isInvalidDecl()) {
-    AutoType *NewAT = Deduced->getContainedAutoType();
-    // It is possible that NewAT->getDeducedType() is null. When that happens,
-    // we should not crash, instead we ignore this deduction.
-    if (NewAT->getDeducedType().isNull())
-      return false;
-
-    CanQualType OldDeducedType = Context.getCanonicalFunctionResultType(
-                                   DeducedT);
-    CanQualType NewDeducedType = Context.getCanonicalFunctionResultType(
-                                   NewAT->getDeducedType());
-    if (!FD->isDependentContext() && OldDeducedType != NewDeducedType) {
-      const LambdaScopeInfo *LambdaSI = getCurLambda();
-      if (LambdaSI && LambdaSI->HasImplicitReturnType) {
-        Diag(ReturnLoc, diag::err_typecheck_missing_return_type_incompatible)
-          << NewAT->getDeducedType() << DeducedT
-          << true /*IsLambda*/;
-      } else {
-        Diag(ReturnLoc, diag::err_auto_fn_different_deductions)
-          << (AT->isDecltypeAuto() ? 1 : 0)
-          << NewAT->getDeducedType() << DeducedT;
-      }
-      return true;
-    }
-  } else if (!FD->isInvalidDecl()) {
+  if (!FD->isInvalidDecl() && AT->getDeducedType() != Deduced)
     // Update all declarations of the function to have the deduced return type.
     Context.adjustDeducedFunctionResultType(FD, Deduced);
-  }
 
   return false;
 }
 
 StmtResult
 Sema::ActOnReturnStmt(SourceLocation ReturnLoc, Expr *RetValExp,
                       Scope *CurScope) {
   // Correct typos, in case the containing function returns 'auto' and

clang/lib/Sema/SemaTemplate.cpp

if (CTAK == CTAK_Deduced && Arg->isTypeDependent()) {
         Converted = TemplateArgument(Arg);
         return Arg;
       }
     }
 
     // When checking a deduced template argument, deduce from its type even if
     // the type is dependent, in order to check the types of non-type template
     // arguments line up properly in partial ordering.
-    Optional<unsigned> Depth = Param->getDepth() + 1;
     Expr *DeductionArg = Arg;
     if (auto *PE = dyn_cast<PackExpansionExpr>(DeductionArg))
       DeductionArg = PE->getPattern();
     TypeSourceInfo *TSI =
         Context.getTrivialTypeSourceInfo(ParamType, Param->getLocation());
     if (isa<DeducedTemplateSpecializationType>(DeducedT)) {
       InitializedEntity Entity =
           InitializedEntity::InitializeTemplateParameter(ParamType, Param);
       InitializationKind Kind = InitializationKind::CreateForInit(
           DeductionArg->getBeginLoc(), /*DirectInit*/false, DeductionArg);
       Expr *Inits[1] = {DeductionArg};
       ParamType =
           DeduceTemplateSpecializationFromInitializer(TSI, Entity, Kind, Inits);
       if (ParamType.isNull())
         return ExprError();
-    } else if (DeduceAutoType(
-                   TSI, DeductionArg, ParamType, Depth,
+    } else {
+      TemplateDeductionInfo Info(DeductionArg->getExprLoc(),
+                                 Param->getDepth() + 1);
+      ParamType = QualType();
+      TemplateDeductionResult Result =
+          DeduceAutoType(TSI->getTypeLoc(), DeductionArg, ParamType, Info,
+                         /*DependentDeduction=*/true,
                          // We do not check constraints right now because the
-                   // immediately-declared constraint of the auto type is also
-                   // an associated constraint, and will be checked along with
-                   // the other associated constraints after checking the
-                   // template argument list.
-                   /*IgnoreConstraints=*/true) == DAR_Failed) {
+                         // immediately-declared constraint of the auto type is
+                         // also an associated constraint, and will be checked
+                         // along with the other associated constraints after
+                         // checking the template argument list.
+                         /*IgnoreConstraints=*/true);
+      if (Result != TDK_Success &&
+          Result != TDK_MiscellaneousDeductionFailure) {
         Diag(Arg->getExprLoc(),
              diag::err_non_type_template_parm_type_deduction_failure)
             << Param->getDeclName() << Param->getType() << Arg->getType()
             << Arg->getSourceRange();
         Diag(Param->getLocation(), diag::note_template_param_here);
         return ExprError();
       }
+    }
     // CheckNonTypeTemplateParameterType will produce a diagnostic if there's
     // an error. The error message normally references the parameter
     // declaration, but here we'll pass the argument location because that's
     // where the parameter type is deduced.
     ParamType = CheckNonTypeTemplateParameterType(ParamType, Arg->getExprLoc());
     if (ParamType.isNull()) {
       Diag(Param->getLocation(), diag::note_template_param_here);
       return ExprError();

clang/lib/Sema/SemaTemplateDeduction.cpp

if (!XType.isNull()) {
         return DeducedTemplateArgument();
     }
   }
 
   switch (X.getKind()) {
   case TemplateArgument::Null:
     llvm_unreachable("Non-deduced template arguments handled above");
 
-  case TemplateArgument::Type:
+  case TemplateArgument::Type: {
     // If two template type arguments have the same type, they're compatible.
-    if (Y.getKind() == TemplateArgument::Type &&
-        Context.hasSameType(X.getAsType(), Y.getAsType()))
-      return X;
+    QualType TX = X.getAsType(), TY = Y.getAsType();
+    if (Y.getKind() == TemplateArgument::Type && Context.hasSameType(TX, TY))
+      return DeducedTemplateArgument(Context.getCommonSugar(TX, TY),
+                                     X.wasDeducedFromArrayBound() ||
+                                         Y.wasDeducedFromArrayBound());
 
     // If one of the two arguments was deduced from an array bound, the other
     // supersedes it.
     if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
       return X.wasDeducedFromArrayBound() ? Y : X;
 
     // The arguments are not compatible.
     return DeducedTemplateArgument();
+  }
 
   case TemplateArgument::Integral:
     // If we deduced a constant in one case and either a dependent expression or
     // declaration in another case, keep the integral constant.
     // If both are integral constants with the same value, keep that value.
     if (Y.getKind() == TemplateArgument::Expression ||
         Y.getKind() == TemplateArgument::Declaration ||
         (Y.getKind() == TemplateArgument::Integral &&
case TemplateArgument::Declaration:
 
     // All other combinations are incompatible.
     return DeducedTemplateArgument();
 
   case TemplateArgument::NullPtr:
     // If we deduced a null pointer and a dependent expression, keep the
     // null pointer.
     if (Y.getKind() == TemplateArgument::Expression)
-      return X;
+      return TemplateArgument(
+          Context.getCommonSugar(X.getNullPtrType(), Y.getAsExpr()->getType()),
+          true);
 
     // If we deduced a null pointer and an integral constant, keep the
     // integral constant.
     if (Y.getKind() == TemplateArgument::Integral)
       return Y;
 
     // If we deduced two null pointers, they are the same.
     if (Y.getKind() == TemplateArgument::NullPtr)
-      return X;
+      return TemplateArgument(
+          Context.getCommonSugar(X.getNullPtrType(), Y.getNullPtrType()), true);
 
     // All other combinations are incompatible.
     return DeducedTemplateArgument();
 
   case TemplateArgument::Pack: {
     if (Y.getKind() != TemplateArgument::Pack ||
         X.pack_size() != Y.pack_size())
       return DeducedTemplateArgument();
QualType Apply(TypeLoc TL) {
       TypeLocBuilder TLB;
       TLB.reserve(TL.getFullDataSize());
       return TransformType(TLB, TL);
     }
   };
 
 } // namespace
 
-Sema::DeduceAutoResult
-Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result,
-                     Optional<unsigned> DependentDeductionDepth,
-                     bool IgnoreConstraints) {
-  return DeduceAutoType(Type->getTypeLoc(), Init, Result,
-                        DependentDeductionDepth, IgnoreConstraints);
-}
-
-/// Attempt to produce an informative diagostic explaining why auto deduction
-/// failed.
-/// \return \c true if diagnosed, \c false if not.
-static bool diagnoseAutoDeductionFailure(Sema &S,
-                                         Sema::TemplateDeductionResult TDK,
-                                         TemplateDeductionInfo &Info,
-                                         ArrayRef<SourceRange> Ranges) {
-  switch (TDK) {
-  case Sema::TDK_Inconsistent: {
-    // Inconsistent deduction means we were deducing from an initializer list.
-    auto D = S.Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction);
-    D << Info.FirstArg << Info.SecondArg;
-    for (auto R : Ranges)
-      D << R;
-    return true;
-  }
-
-  // FIXME: Are there other cases for which a custom diagnostic is more useful
-  // than the basic "types don't match" diagnostic?
-
-  default:
-    return false;
-  }
-}
-
-static Sema::DeduceAutoResult
-CheckDeducedPlaceholderConstraints(Sema &S, const AutoType &Type,
-                                   AutoTypeLoc TypeLoc, QualType Deduced) {
+static bool CheckDeducedPlaceholderConstraints(Sema &S, const AutoType &Type,
+                                               AutoTypeLoc TypeLoc,
+                                               QualType Deduced) {
   ConstraintSatisfaction Satisfaction;
   ConceptDecl *Concept = Type.getTypeConstraintConcept();
   TemplateArgumentListInfo TemplateArgs(TypeLoc.getLAngleLoc(),
                                         TypeLoc.getRAngleLoc());
   TemplateArgs.addArgument(
       TemplateArgumentLoc(TemplateArgument(Deduced),
                           S.Context.getTrivialTypeSourceInfo(
                               Deduced, TypeLoc.getNameLoc())));
   for (unsigned I = 0, C = TypeLoc.getNumArgs(); I != C; ++I)
     TemplateArgs.addArgument(TypeLoc.getArgLoc(I));
 
   llvm::SmallVector<TemplateArgument, 4> Converted;
   if (S.CheckTemplateArgumentList(Concept, SourceLocation(), TemplateArgs,
                                   /*PartialTemplateArgs=*/false, Converted))
-    return Sema::DAR_FailedAlreadyDiagnosed;
+    return true;
   if (S.CheckConstraintSatisfaction(Concept, {Concept->getConstraintExpr()},
                                     Converted, TypeLoc.getLocalSourceRange(),
                                     Satisfaction))
-    return Sema::DAR_FailedAlreadyDiagnosed;
+    return true;
   if (!Satisfaction.IsSatisfied) {
     std::string Buf;
     llvm::raw_string_ostream OS(Buf);
     OS << "'" << Concept->getName();
     if (TypeLoc.hasExplicitTemplateArgs()) {
       printTemplateArgumentList(
           OS, Type.getTypeConstraintArguments(), S.getPrintingPolicy(),
           Type.getTypeConstraintConcept()->getTemplateParameters());
     }
     OS << "'";
     OS.flush();
     S.Diag(TypeLoc.getConceptNameLoc(),
            diag::err_placeholder_constraints_not_satisfied)
-         << Deduced << Buf << TypeLoc.getLocalSourceRange();
     S.DiagnoseUnsatisfiedConstraint(Satisfaction);
-    return Sema::DAR_FailedAlreadyDiagnosed;
+    return true;
   }
-  return Sema::DAR_Succeeded;
+  return false;
 }
 
 /// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
 ///
 /// Note that this is done even if the initializer is dependent. (This is
 /// necessary to support partial ordering of templates using 'auto'.)
 /// A dependent type will be produced when deducing from a dependent type.
 ///
 /// \param Type the type pattern using the auto type-specifier.
 /// \param Init the initializer for the variable whose type is to be deduced.
 /// \param Result if type deduction was successful, this will be set to the
 ///        deduced type.
 /// \param DependentDeductionDepth Set if we should permit deduction in
 ///        dependent cases. This is necessary for template partial ordering with
 ///        'auto' template parameters. The value specified is the template
 ///        parameter depth at which we should perform 'auto' deduction.
 /// \param IgnoreConstraints Set if we should not fail if the deduced type does
 ///                          not satisfy the type-constraint in the auto type.
-Sema::DeduceAutoResult
-Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
-                     Optional<unsigned> DependentDeductionDepth,
+Sema::TemplateDeductionResult Sema::DeduceAutoType(TypeLoc Type, Expr *Init,
+                                                   QualType &Result,
+                                                   TemplateDeductionInfo &Info,
+                                                   bool DependentDeduction,
                                                    bool IgnoreConstraints) {
+  assert(DependentDeduction || Info.getDeducedDepth() == 0);
   if (Init->containsErrors())
-    return DAR_FailedAlreadyDiagnosed;
-  if (Init->getType()->isNonOverloadPlaceholderType()) {
+    return TDK_MiscellaneousDeductionFailure;
+
+  const AutoType *AT = Type.getType()->getContainedAutoType();
+  assert(AT);
+
+  if (Init->getType()->isNonOverloadPlaceholderType() || AT->isDecltypeAuto()) {
     ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
     if (NonPlaceholder.isInvalid())
-      return DAR_FailedAlreadyDiagnosed;
+      return TDK_MiscellaneousDeductionFailure;
     Init = NonPlaceholder.get();
   }
 
   DependentAuto DependentResult = {
       /*.IsPack = */ (bool)Type.getAs<PackExpansionTypeLoc>()};
 
-  if (!DependentDeductionDepth &&
+  if (!DependentDeduction &&
       (Type.getType()->isDependentType() || Init->isTypeDependent() ||
        Init->containsUnexpandedParameterPack())) {
     Result = SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
     assert(!Result.isNull() && "substituting DependentTy can't fail");
-    return DAR_Succeeded;
-  }
-
-  // Find the depth of template parameter to synthesize.
-  unsigned Depth = DependentDeductionDepth.getValueOr(0);
-
-  // If this is a 'decltype(auto)' specifier, do the decltype dance.
-  // Since 'decltype(auto)' can only occur at the top of the type, we
-  // don't need to go digging for it.
-  if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
-    if (AT->isDecltypeAuto()) {
-      if (isa<InitListExpr>(Init)) {
-        Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
-        return DAR_FailedAlreadyDiagnosed;
-      }
+    return TDK_Success;
 
-      ExprResult ER = CheckPlaceholderExpr(Init);
-      if (ER.isInvalid())
-        return DAR_FailedAlreadyDiagnosed;
-      QualType Deduced = getDecltypeForExpr(ER.get());
-      assert(!Deduced.isNull());
-      if (AT->isConstrained() && !IgnoreConstraints) {
-        auto ConstraintsResult =
-            CheckDeducedPlaceholderConstraints(*this, *AT,
-                                               Type.getContainedAutoTypeLoc(),
-                                               Deduced);
-        if (ConstraintsResult != DAR_Succeeded)
-          return ConstraintsResult;
-      }
-      Result = SubstituteDeducedTypeTransform(*this, Deduced).Apply(Type);
-      if (Result.isNull())
-        return DAR_FailedAlreadyDiagnosed;
-      return DAR_Succeeded;
-    } else if (!getLangOpts().CPlusPlus) {
-      if (isa<InitListExpr>(Init)) {
-        Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c);
-        return DAR_FailedAlreadyDiagnosed;
-      }
-    }
+  auto *InitList = dyn_cast<InitListExpr>(Init);
+  if (!getLangOpts().CPlusPlus && InitList) {
+    return TDK_MiscellaneousDeductionFailure;
   }
 
-  SourceLocation Loc = Init->getExprLoc();
-
-  LocalInstantiationScope InstScope(*this);
-
-  // Build template<class TemplParam> void Func(FuncParam);
-  TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create(
-      Context, nullptr, SourceLocation(), Loc, Depth, 0, nullptr, false, false,
-      false);
-  QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
-  NamedDecl *TemplParamPtr = TemplParam;
-  FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt(
-      Context, Loc, Loc, TemplParamPtr, Loc, nullptr);
-
-  QualType FuncParam =
-      SubstituteDeducedTypeTransform(*this, TemplArg, /*UseTypeSugar*/ true)
-          .Apply(Type);
-  assert(!FuncParam.isNull() &&
-         "substituting template parameter for 'auto' failed");
-
   // Deduce type of TemplParam in Func(Init)
   SmallVector<DeducedTemplateArgument, 1> Deduced;
   Deduced.resize(1);
 
-  TemplateDeductionInfo Info(Loc, Depth);
-
   // If deduction failed, don't diagnose if the initializer is dependent; it
   // might acquire a matching type in the instantiation.
-  auto DeductionFailed = [&](TemplateDeductionResult TDK,
-                             ArrayRef<SourceRange> Ranges) -> DeduceAutoResult {
+  auto DeductionFailed = [&](TemplateDeductionResult TDK) {
     if (Init->isTypeDependent()) {
       Result =
           SubstituteDeducedTypeTransform(*this, DependentResult).Apply(Type);
       assert(!Result.isNull() && "substituting DependentTy can't fail");
-      return DAR_Succeeded;
+      return TDK_Success;
     }
-    if (diagnoseAutoDeductionFailure(*this, TDK, Info, Ranges))
-      return DAR_FailedAlreadyDiagnosed;
-    return DAR_Failed;
+    return TDK;
   };
 
   SmallVector<OriginalCallArg, 4> OriginalCallArgs;
 
-  InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
+  QualType DeducedType;
+  // If this is a 'decltype(auto)' specifier, do the decltype dance.
+  if (AT->isDecltypeAuto()) {
     if (InitList) {
-    // Notionally, we substitute std::initializer_list<T> for 'auto' and deduce
-    // against that. Such deduction only succeeds if removing cv-qualifiers and
-    // references results in std::initializer_list<T>.
-    if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
-      return DAR_Failed;
+      Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
+      return TDK_MiscellaneousDeductionFailure;
+    }
 
-    // Resolving a core issue: a braced-init-list containing any designators is
-    // a non-deduced context.
-    for (Expr *E : InitList->inits())
-      if (isa<DesignatedInitExpr>(E))
-        return DAR_Failed;
+    DeducedType = getDecltypeForExpr(Init);
+    assert(!DeducedType.isNull());
 
-    SourceRange DeducedFromInitRange;
-    for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
-      Expr *Init = InitList->getInit(i);
+    if (!Result.isNull()) {
+      if (!Context.hasSameType(DeducedType, Result)) {
+        Info.FirstArg = Result;
+        Info.SecondArg = DeducedType;
+        return DeductionFailed(TDK_Inconsistent);
+      }
+      DeducedType = Context.getCommonSugar(Result, DeducedType);
+    }
+  } else {
+    LocalInstantiationScope InstScope(*this);
 
+    // Build template<class TemplParam> void Func(FuncParam);
+    SourceLocation Loc = Init->getExprLoc();
+    TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create(
+        Context, nullptr, SourceLocation(), Loc, Info.getDeducedDepth(), 0,
+        nullptr, false, false, false);
+    QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
+    NamedDecl *TemplParamPtr = TemplParam;
+    FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt(
+        Context, Loc, Loc, TemplParamPtr, Loc, nullptr);
+
+    if (InitList) {
+      // Notionally, we substitute std::initializer_list<T> for 'auto' and
+      // deduce against that. Such deduction only succeeds if removing
+      // cv-qualifiers and references results in std::initializer_list<T>.
+      if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
+        return TDK_Invalid;
+
+      SourceRange DeducedFromInitRange;
+      for (Expr *Init : InitList->inits()) {
+        // Resolving a core issue: a braced-init-list containing any designators
+        // is a non-deduced context.
+        if (isa<DesignatedInitExpr>(Init))
+          return TDK_Invalid;
         if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
-              *this, TemplateParamsSt.get(), 0, TemplArg, Init,
-              Info, Deduced, OriginalCallArgs, /*Decomposed*/ true,
-              /*ArgIdx*/ 0, /*TDF*/ 0))
-        return DeductionFailed(TDK, {DeducedFromInitRange,
-                                     Init->getSourceRange()});
+                *this, TemplateParamsSt.get(), 0, TemplArg, Init, Info, Deduced,
+                OriginalCallArgs, /*Decomposed=*/true,
+                /*ArgIdx=*/0, /*TDF=*/0)) {
+          if (TDK == TDK_Inconsistent) {
+            Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction)
+                << Info.FirstArg << Info.SecondArg << DeducedFromInitRange
+                << Init->getSourceRange();
+            return DeductionFailed(TDK_MiscellaneousDeductionFailure);
+          }
+          return DeductionFailed(TDK);
+        }
 
         if (DeducedFromInitRange.isInvalid() &&
             Deduced[0].getKind() != TemplateArgument::Null)
           DeducedFromInitRange = Init->getSourceRange();
       }
     } else {
       if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
         Diag(Loc, diag::err_auto_bitfield);
-      return DAR_FailedAlreadyDiagnosed;
+        return TDK_MiscellaneousDeductionFailure;
       }
-
+      QualType FuncParam =
+          SubstituteDeducedTypeTransform(*this, TemplArg, /*UseTypeSugar=*/true)
+              .Apply(Type);
+      assert(!FuncParam.isNull() &&
+             "substituting template parameter for 'auto' failed");
+      if (!Result.isNull())
+        Deduced[0] = DeducedTemplateArgument(Result);
       if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
               *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
-            OriginalCallArgs, /*Decomposed*/ false, /*ArgIdx*/ 0, /*TDF*/ 0))
-      return DeductionFailed(TDK, {});
+              OriginalCallArgs, /*Decomposed=*/false, /*ArgIdx=*/0, /*TDF=*/0))
+        return DeductionFailed(TDK);
     }
 
     // Could be null if somehow 'auto' appears in a non-deduced context.
     if (Deduced[0].getKind() != TemplateArgument::Type)
-    return DeductionFailed(TDK_Incomplete, {});
-
-  QualType DeducedType = Deduced[0].getAsType();
+      return DeductionFailed(TDK_Incomplete);
+    DeducedType = Deduced[0].getAsType();
 
     if (InitList) {
       DeducedType = BuildStdInitializerList(DeducedType, Loc);
       if (DeducedType.isNull())
-      return DAR_FailedAlreadyDiagnosed;
+        return TDK_MiscellaneousDeductionFailure;
+      if (!Result.isNull() && !Context.hasSameType(Result, DeducedType)) {
+        Info.FirstArg = Result;
+        Info.SecondArg = DeducedType;
+        return DeductionFailed(TDK_Inconsistent);
       }
-
-  if (const auto *AT = Type.getType()->getAs<AutoType>()) {
-    if (AT->isConstrained() && !IgnoreConstraints) {
-      auto ConstraintsResult =
-          CheckDeducedPlaceholderConstraints(*this, *AT,
-                                             Type.getContainedAutoTypeLoc(),
-                                             DeducedType);
-      if (ConstraintsResult != DAR_Succeeded)
-        return ConstraintsResult;
     }
   }
 
+  if (AT->isConstrained() && !IgnoreConstraints &&
+      CheckDeducedPlaceholderConstraints(
+          *this, *AT, Type.getContainedAutoTypeLoc(), DeducedType))
+    return TDK_MiscellaneousDeductionFailure;
+
   Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type);
   if (Result.isNull())
-    return DAR_FailedAlreadyDiagnosed;
+    return TDK_MiscellaneousDeductionFailure;
 
   // Check that the deduced argument type is compatible with the original
   // argument type per C++ [temp.deduct.call]p4.
   QualType DeducedA = InitList ? Deduced[0].getAsType() : Result;
   for (const OriginalCallArg &OriginalArg : OriginalCallArgs) {
     assert((bool)InitList == OriginalArg.DecomposedParam &&
            "decomposed non-init-list in auto deduction?");
     if (auto TDK =
             CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) {
       Result = QualType();
-      return DeductionFailed(TDK, {});
+      return DeductionFailed(TDK);
     }
   }
 
-  return DAR_Succeeded;
+  return TDK_Success;
 }
 
 QualType Sema::SubstAutoType(QualType TypeWithAuto,
                              QualType TypeToReplaceAuto) {
   assert(TypeToReplaceAuto != Context.DependentTy);
   return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
       .TransformType(TypeWithAuto);
 }

clang/test/SemaCXX/sugared-auto.cpp

-// RUN: %clang_cc1 -fsyntax-only -verify %s -std=c++14
+// RUN: %clang_cc1 -fsyntax-only -verify %s -std=c++20 -fblocks -fenable-matrix -Wno-dynamic-exception-spec
 
 enum class N {};
 
-using T1 = int;
-auto x1 = T1();
-N t1 = x1;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T1' (aka 'int')}}
-
-using T2 = T1 *;
-auto x2 = T2();
-N t2 = x2;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T2' (aka 'int *')}}
-
-auto *x3 = T2();
-N t3 = x3;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T1 *' (aka 'int *')}}
-
-auto f1() { return T1(); }
-auto x4 = f1();
-N t4 = x4;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T1' (aka 'int')}}
-
-decltype(auto) f2() { return T1(); }
-auto x5 = f2();
-N t5 = x5;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T1' (aka 'int')}}
-
-auto x6 = [a = T1()] { return a; }();
-N t6 = x6;
-// expected-error@-1 {{cannot initialize a variable of type 'N' with an lvalue of type 'T1' (aka 'int')}}
+using Animal = int;
+
+using AnimalPtr = Animal *;
+
+using Man = Animal;
+using Dog = Animal;
+
+using ManPtr = Man *;
+using DogPtr = Dog *;
+
+using SocratesPtr = ManPtr;
+
+using ConstMan = const Man;
+using ConstDog = const Dog;
+
+using Virus = void;
+using SARS = Virus;
+using Ebola = Virus;
+
+using Bacteria = float;
+using Bacilli = Bacteria;
+using Vibrio = Bacteria;
+
+struct Plant;
+using Gymnosperm = Plant;
+using Angiosperm = Plant;
+
+namespace variable {
+
+auto x1 = Animal();
+N t1 = x1; // expected-error {{lvalue of type 'Animal' (aka 'int')}}
+
+auto x2 = AnimalPtr();
+N t2 = x2; // expected-error {{lvalue of type 'AnimalPtr' (aka 'int *')}}
+
+auto *x3 = AnimalPtr();
+N t3 = x3; // expected-error {{lvalue of type 'Animal *' (aka 'int *')}}
+
+// Each variable deduces separately.
+auto x4 = Man(), x5 = Dog();
+N t4 = x4; // expected-error {{lvalue of type 'Man' (aka 'int')}}
+N t5 = x5; // expected-error {{lvalue of type 'Dog' (aka 'int')}}
+
+} // namespace variable
+
+namespace function_basic {
+
+auto f1() { return Animal(); }
+auto x1 = f1();
+N t1 = x1; // expected-error {{lvalue of type 'Animal' (aka 'int')}}
+
+decltype(auto) f2() { return Animal(); }
+auto x2 = f2();
+N t2 = x2; // expected-error {{lvalue of type 'Animal' (aka 'int')}}
+
+auto x3 = [a = Animal()] { return a; }();
+N t3 = x3; // expected-error {{lvalue of type 'Animal' (aka 'int')}}
+
+} // namespace function_basic
+
+namespace function_multiple_basic {
+
+N t1 = [] { // expected-error {{rvalue of type 'Animal' (aka 'int')}}
+  if (true)
+    return Man();
+  return Dog();
+}();
+
+N t2 = []() -> decltype(auto) { // expected-error {{rvalue of type 'Animal' (aka 'int')}}
+  if (true)
+    return Man();
+  return Dog();
+}();
+
+N t3 = [] { // expected-error {{rvalue of type 'Animal' (aka 'int')}}
+  if (true)
+    return Dog();
+  auto x = Man();
+  return x;
+}();
+
+N t4 = [] { // expected-error {{rvalue of type 'int'}}
+  if (true)
+    return Dog();
+  return 1;
+}();
+
+N t5 = [] { // expected-error {{rvalue of type 'Virus' (aka 'void')}}
+  if (true)
+    return Ebola();
+  return SARS();
+}();
+
+N t6 = [] { // expected-error {{rvalue of type 'void'}}
+  if (true)
+    return SARS();
+  return;
+}();
+
+} // namespace function_multiple_basic
+
+#define TEST_AUTO(X, A, B) \
+  auto X(A a, B b) {       \
+    if (0)                 \
+      return a;            \
+    if (0)                 \
+      return b;            \
+    return N();            \
+  }
+#define TEST_DAUTO(X, A, B)     \
+  decltype(auto) X(A a, B b) {  \
+    if (0)                      \
+      return static_cast<A>(a); \
+    if (0)                      \
+      return static_cast<B>(b); \
+    return N();                 \
+  }
+
+namespace misc {
+
+TEST_AUTO(t1, ManPtr, DogPtr)      // expected-error {{but deduced as 'Animal *' (aka 'int *')}}
+TEST_AUTO(t2, ManPtr, int *)       // expected-error {{but deduced as 'int *'}}
+TEST_AUTO(t3, SocratesPtr, ManPtr) // expected-error {{but deduced as 'ManPtr' (aka 'int *')}}
+
+TEST_AUTO(t4, _Atomic(Man), _Atomic(Dog)) // expected-error {{but deduced as '_Atomic(Animal)'}}
+
+using block_man = void (^)(Man);
+using block_dog = void (^)(Dog);
+TEST_AUTO(t5, block_man, block_dog) // expected-error {{but deduced as 'void (^)(Animal)'}}
+
+using fp1 = SARS (*)(Man, DogPtr) throw(Vibrio);
+using fp2 = Ebola (*)(Dog, ManPtr) throw(Bacilli);
+TEST_AUTO(t6, fp1, fp2); // expected-error {{but deduced as 'Virus (*)(Animal, Animal *) throw(Bacteria)' (aka 'void (*)(int, int *) throw(Bacteria)')}}
+
+using fp3 = SARS (*)() throw(Man);
+using fp4 = Ebola (*)() throw(Vibrio);
+auto t7(fp3 a, fp4 b) {
+  if (false)
+    return true ? a : b;
+  if (false)
+    return a;
+  return N(); // expected-error {{but deduced as 'SARS (*)() throw(Man, Vibrio)' (aka 'void (*)() throw(Man, Vibrio)')}}
+}
+
+using fp5 = void (*)(const Man);
+using fp6 = void (*)(Dog);
+TEST_AUTO(t8, fp5, fp6); // expected-error {{but deduced as 'void (*)(const Animal)' (aka 'void (*)(const int)')}}
+
+using fp6 = void (*)(ConstMan);
+using fp7 = void (*)(ConstDog);
+TEST_AUTO(t10, fp6, fp7); // expected-error {{but deduced as 'void (*)(const Animal)' (aka 'void (*)(const int)')}}
+
+TEST_AUTO(t11, Man Angiosperm::*, Dog Gymnosperm::*) // expected-error {{but deduced as 'Animal Plant::*'}}
+
+TEST_DAUTO(t12, const Man &, const Dog &) // expected-error {{but deduced as 'const Animal &' (aka 'const int &')}}
+
+TEST_DAUTO(t13, Man &&, Dog &&) // expected-error {{but deduced as 'Animal &&' (aka 'int &&')}}
+
+using matrix_man = Man __attribute__((matrix_type(4, 4)));
+using matrix_dog = Dog __attribute__((matrix_type(4, 4)));
+TEST_AUTO(t14, matrix_man, matrix_dog) // expected-error {{but deduced as 'Animal __attribute__((matrix_type(4, 4)))'}}
+
+using vector_man = Man __attribute__((vector_size(4)));
+using vector_dog = Dog __attribute__((vector_size(4)));
+TEST_AUTO(t15, vector_man, vector_dog) // expected-error {{but deduced as '__attribute__((__vector_size__(1 * sizeof(Animal)))) Animal' (vector of 1 'Animal' value)}}
+
+using ext_vector_man = Man __attribute__((ext_vector_type(4)));
+using ext_vector_dog = Dog __attribute__((ext_vector_type(4)));
+TEST_AUTO(t16, ext_vector_man, ext_vector_dog) // expected-error {{but deduced as 'Animal __attribute__((ext_vector_type(4)))' (vector of 4 'Animal' values)}}
+
+} // namespace misc