Clang: fix AST representation of expanded template arguments.

[mizvekov]

Summary

Extend clang's SubstTemplateTypeParm to represent the pack substitution index.

Fixes PR56099.

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

[mizvekov]

.

[mizvekov]

.

[mizvekov]

format

[mizvekov]

rebase

[shafik]

clang/lib/AST/ASTImporter.cpp

1534

I think we should have a test in ASTImporterTest.cpp to make sure we are importing the pack index correctly.

[mizvekov]

clang/lib/AST/ASTImporter.cpp

1534

Thanks for the suggestion, implemented.
It turns out we didn't even have any tests for importing SubsTemplateTypeParmType in the first place.

[davrec]

This corrects a genuine deficiency in the AST, and the patch LGTM. Can we knock this off Matheus' stack?

[mizvekov]

In D128113#3708204, @davrec wrote:

This corrects a genuine deficiency in the AST, and the patch LGTM. Can we knock this off Matheus' stack?

Thanks!!!! :-)

[shafik]

LGTM as well

[joanahalili]

We have a translation unit, on which we see an increase of compilation time and clang memory allocation from 11GB to 14GB. We are working on an isolated case.

[mizvekov]

In D128113#3733051, @joanahalili wrote:

We have a translation unit, on which we see an increase of compilation time and clang memory allocation from 11GB to 14GB. We are working on an isolated case.

Thanks for looking into this!

What I can imagine may be happening here is that if we instantiate a template with a very large argument pack consisting of mostly the same template arguments, we will create many more SubstTemplateTypeParmType nodes with this patch, as they won't unique so much anymore, because each will have a different pack index.

[davrec]

In D128113#3733764, @mizvekov wrote:

In D128113#3733051, @joanahalili wrote:

We have a translation unit, on which we see an increase of compilation time and clang memory allocation from 11GB to 14GB. We are working on an isolated case.

Thanks for looking into this!

What I can imagine may be happening here is that if we instantiate a template with a very large argument pack consisting of mostly the same template arguments, we will create many more SubstTemplateTypeParmType nodes with this patch, as they won't unique so much anymore, because each will have a different pack index.

If this is indeed a major problem, and/or if performance is an issue for other of the patches in the stack, maybe the solution is along the lines of what I raised in https://discourse.llvm.org/t/rfc-improving-diagnostics-with-template-specialization-resugaring/64294/5: introduce an option that determines how much sugar we construct in the AST, and modify ASTContext::get*Type(...) accordingly.

For now it could have two possible values, 'medium' and 'maximum', and getSubstTemplateTypeParmType(...) could be modified so it always uses PackIndex=0 whenever it is only set to 'medium'. And, for later patches, resugaring would only be enabled when it is set to 'maximum'. (And maybe later a 'minimum' option could be experimented with which disables all sugar except that needed to keep tests passing.)

[alexfh]

Adding to the comment @joanahalili posted: this particular translation unit happens to have a large number of reverse dependencies and Clang's memory allocation has pushed it over the limits, which makes this issue quite serious. So far I can't say how widespread are large increases in clang heap allocation, which don't lead to exceeding memory limits used in the build setup and thus are less noticeable. However, I suppose that this should affect various clang-based tools like ciderd. @sammccall @kadircet, fyi.

[joanahalili]

reproduction.cpp25 KBDownload

clang -fsyntax-only -std=c++17  -fproc-stat-report -Wno-deprecated-declarations  -fsized-deallocation -Werror -Wno-deprecated-declarations  -Wno-inconsistent-missing-override -Wno-null-conversion -Wno-ignored-attributes  -Wno-defaulted-function-deleted -xc++ reproduction.cpp

This is the reproducer we managed to create for the memory increase. As mentioned above we notice both a difference in memory and execution time.
Clang version before this patch

• Memory: 8Gb
• Time: 32507 ms

Clang version with this patch:

• Memory: 10.5 Gb (2.5Gb increase)
• Time 63812 (almost double the previous compilation time).

[mizvekov]

In D128113#3742779, @joanahalili wrote:

This is the reproducer we managed to create for the memory increase. As mentioned above we notice both a difference in memory and execution time.

Thanks.

I also added a print of the amount of SubstTemplateTypeParmType nodes that were uniqued:

Before:

SubstTemplateTypeParmType: 751088
clang.exe: output=a.exe, total=46687.500 ms, user=46031.250 ms, mem=7793868 Kb

After:

SubstTemplateTypeParmType: 41919586
clang.exe: output=a.exe, total=68828.125 ms, user=67968.750 ms, mem=10511992 Kb

This DR is so basic that I don't really see reasonable way to avoid this cost except by disabling it with a flag.

Though I wonder how useful a SubstTemplateTypeParmType is without the pack index. If that kind of heavy handed meta-programming is reasonable, a flag for disabling substitution sugar entirely does not seem unreasonable...

[alexfh]

In D128113#3743736, @mizvekov wrote:

In D128113#3742779, @joanahalili wrote:

This is the reproducer we managed to create for the memory increase. As mentioned above we notice both a difference in memory and execution time.

Thanks.

I also added a print of the amount of SubstTemplateTypeParmType nodes that were uniqued:

Before:

SubstTemplateTypeParmType: 751088
clang.exe: output=a.exe, total=46687.500 ms, user=46031.250 ms, mem=7793868 Kb

After:

SubstTemplateTypeParmType: 41919586
clang.exe: output=a.exe, total=68828.125 ms, user=67968.750 ms, mem=10511992 Kb

This DR is so basic that I don't really see reasonable way to avoid this cost except by disabling it with a flag.

Though I wonder how useful a SubstTemplateTypeParmType is without the pack index. If that kind of heavy handed meta-programming is reasonable, a flag for disabling substitution sugar entirely does not seem unreasonable...

I wonder what is the practical application of the substitution index in SubstTemplateTypeParmType? Diagnostics? Matching AST? Something else? What would be the cost of calculating the index when necessary?

[mizvekov]

In D128113#3743936, @alexfh wrote:

I wonder what is the practical application of the substitution index in SubstTemplateTypeParmType? Diagnostics? Matching AST? Something else? What would be the cost of calculating the index when necessary?

The pack index helps you figure out which argument within an argument pack was used in a substitution, much like the ReplacementType has an index which helps you figure out which argument was used.

Calculating it should be possible, if we have the whole type which contains the pattern from where the expansion came from.

The problem is that if we want to extract a sub-type from the whole, say the type of a certain function argument, then we would have to rebuild that type to include this pack index in any substitution sugar. And that sounds expensive as well.

[alexfh]

In D128113#3744128, @mizvekov wrote:

In D128113#3743936, @alexfh wrote:

I wonder what is the practical application of the substitution index in SubstTemplateTypeParmType? Diagnostics? Matching AST? Something else? What would be the cost of calculating the index when necessary?

The pack index helps you figure out which argument within an argument pack was used in a substitution, much like the ReplacementType has an index which helps you figure out which argument was used.

Calculating it should be possible, if we have the whole type which contains the pattern from where the expansion came from.

The problem is that if we want to extract a sub-type from the whole, say the type of a certain function argument, then we would have to rebuild that type to include this pack index in any substitution sugar. And that sounds expensive as well.

Do you have a practical example that would use the substitution index? I believe you had something in mind before you implemented this patch?

[mizvekov]

In D128113#3744290, @alexfh wrote:

Do you have a practical example that would use the substitution index? I believe you had something in mind before you implemented this patch?

Oh, yes, this is needed for / is going to culminate in the implementation of the project described in https://discourse.llvm.org/t/rfc-improving-diagnostics-with-template-specialization-resugaring/64294/11

[alexfh]

In D128113#3744296, @mizvekov wrote:

In D128113#3744290, @alexfh wrote:

Do you have a practical example that would use the substitution index? I believe you had something in mind before you implemented this patch?

Oh, yes, this is needed for / is going to culminate in the implementation of the project described in https://discourse.llvm.org/t/rfc-improving-diagnostics-with-template-specialization-resugaring/64294/11

The whole project seems like a great improvement in clang diagnostics, but I don't yet see how template parameter pack substitution indices fit into the whole picture. If different type parameters in a parameter pack differ only by some other type of suraring, would they be distinguishable in the current state? How do substitution indices affect this?

[mizvekov]

In D128113#3744315, @alexfh wrote:

The whole project seems like a great improvement in clang diagnostics, but I don't yet see how template parameter pack substitution indices fit into the whole picture. If different type parameters in a parameter pack differ only by some other type of suraring, would they be distinguishable in the current state? How do substitution indices affect this?

We need the pack index just as much as the index.

When we are resugaring some type and we find a SubstTemplateParmType, first we try to find a template specialization in the current naming context (ie a nested name specifier) which refers to the same template as the Subst node.

Then we have to rebuild that Subst node using, as the new underlying type, the template argument which appears in the template specialization we found. To find that argument, first we use the index, which already was available in the AST prior to this patch. But in case that index refers to an argument pack, then we need the pack index to be able to find the argument inside that.

[alexfh]

In D128113#3744353, @mizvekov wrote:

In D128113#3744315, @alexfh wrote:

The whole project seems like a great improvement in clang diagnostics, but I don't yet see how template parameter pack substitution indices fit into the whole picture. If different type parameters in a parameter pack differ only by some other type of suraring, would they be distinguishable in the current state? How do substitution indices affect this?

We need the pack index just as much as the index.

When we are resugaring some type and we find a SubstTemplateParmType, first we try to find a template specialization in the current naming context (ie a nested name specifier) which refers to the same template as the Subst node.

Then we have to rebuild that Subst node using, as the new underlying type, the template argument which appears in the template specialization we found. To find that argument, first we use the index, which already was available in the AST prior to this patch. But in case that index refers to an argument pack, then we need the pack index to be able to find the argument inside that.

I more or less understand the general direction, but it would be interesting to look at the specific code that uses this.

The main questions we need to answer here are:

1. is the cost of storing parameter pack substitution indices while building AST worth the benefits?
2. is there an alternative solution that would shift the cost to the moment when this information is about to be used (when formatting diagnostic, I suppose)?
3. is there a good way to make this cost optional (using a flag or somehow else)?

[mizvekov]

In D128113#3745888, @alexfh wrote:

The main questions we need to answer here are:

1. is the cost of storing parameter pack substitution indices while building AST worth the benefits?
2. is there an alternative solution that would shift the cost to the moment when this information is about to be used (when formatting diagnostic, I suppose)?
3. is there a good way to make this cost optional (using a flag or somehow else)?

1. For me yes, this was a fairly simple patch that got reviewed quickly and got the job done. But it seems it was not good for your use case :)
2. I think there is a chance the approach I mentioned earlier could work. It's hard for me to tell without spending some time trying. This could though end up being a much more complicated patch, which hits my projects bottleneck: it's pretty hard to find reviewers for this sort of stuff.
3. That has the advantage of change simplicity, but not user simplicity. It could provide a escape hatch in allowing us to have a simple solution now, but then iterate to something better later. But since this is an externally visible change to the AST, it does seem far from ideal to be changing this twice. It would be pretty unfortunate if someone else started using this feature and then we decided to take it away.

I would be fine though reverting this, and then doing some more investigation, and also perhaps waiting for a second opinion from @rsmith.

[alexfh]

In D128113#3746674, @mizvekov wrote:

In D128113#3745888, @alexfh wrote:

The main questions we need to answer here are:

1. is the cost of storing parameter pack substitution indices while building AST worth the benefits?
2. is there an alternative solution that would shift the cost to the moment when this information is about to be used (when formatting diagnostic, I suppose)?
3. is there a good way to make this cost optional (using a flag or somehow else)?

1. For me yes, this was a fairly simple patch that got reviewed quickly and got the job done. But it seems it was not good for your use case :)
2. I think there is a chance the approach I mentioned earlier could work. It's hard for me to tell without spending some time trying. This could though end up being a much more complicated patch, which hits my projects bottleneck: it's pretty hard to find reviewers for this sort of stuff.
3. That has the advantage of change simplicity, but not user simplicity. It could provide a escape hatch in allowing us to have a simple solution now, but then iterate to something better later. But since this is an externally visible change to the AST, it does seem far from ideal to be changing this twice. It would be pretty unfortunate if someone else started using this feature and then we decided to take it away.

I would be fine though reverting this, and then doing some more investigation, and also perhaps waiting for a second opinion from @rsmith.

For now we've added a workaround for the most problematic use case and got us unblocked. Thus there is no need now in introducing additional flags. However, I'm rather concerned about the cumulative additional overhead our build infrastructure gets as a result of this patch. Measuring this would unfortunately be a project of its own, which I'm not ready to commit to. If reverting this and discussing with Richard Smith is an option for you, I'd suggest doing this now and if you end up not finding a good alternative, we would probably need to find a way to estimate the impact of this patch. WDYT?

[mizvekov]

In D128113#3747946, @alexfh wrote:

For now we've added a workaround for the most problematic use case and got us unblocked. Thus there is no need now in introducing additional flags. However, I'm rather concerned about the cumulative additional overhead our build infrastructure gets as a result of this patch. Measuring this would unfortunately be a project of its own, which I'm not ready to commit to. If reverting this and discussing with Richard Smith is an option for you, I'd suggest doing this now and if you end up not finding a good alternative, we would probably need to find a way to estimate the impact of this patch. WDYT?

Thanks, and sorry for the long time to respond to this.

I have been thinking about this problem, and I have an idea for a solution which is better on the performance side, but more complex change.

We would need to implement some pattern matching during AST traversal, and keep track of the pack index there. When extracting a component of the larger type, such as when deducing non-pack arguments from a pack, we would wrap it over with a new sugar type node which encodes the current pack indexes.

I reflected a bit on this, and yeah I think we should try to design something which does not potentially hinder large packs so much.

I am not sure how this is going to play out in practice, and it's possible we may need to come back to this solution again, but I think it's prudent to revert it for now if we are not sure, as this is an API change, however obscure for most users.

As an aside, it would be really helpful if you could track how the compilation of your codebase performs as clang evolves, regardless if we keep this change or not :)
Maybe you can reuse something from http://llvm-compile-time-tracker.com/

[alexfh]

In D128113#3751477, @mizvekov wrote:

In D128113#3747946, @alexfh wrote:

For now we've added a workaround for the most problematic use case and got us unblocked. Thus there is no need now in introducing additional flags. However, I'm rather concerned about the cumulative additional overhead our build infrastructure gets as a result of this patch. Measuring this would unfortunately be a project of its own, which I'm not ready to commit to. If reverting this and discussing with Richard Smith is an option for you, I'd suggest doing this now and if you end up not finding a good alternative, we would probably need to find a way to estimate the impact of this patch. WDYT?

Thanks, and sorry for the long time to respond to this.

I have been thinking about this problem, and I have an idea for a solution which is better on the performance side, but more complex change.

We would need to implement some pattern matching during AST traversal, and keep track of the pack index there. When extracting a component of the larger type, such as when deducing non-pack arguments from a pack, we would wrap it over with a new sugar type node which encodes the current pack indexes.

I reflected a bit on this, and yeah I think we should try to design something which does not potentially hinder large packs so much.

I am not sure how this is going to play out in practice, and it's possible we may need to come back to this solution again, but I think it's prudent to revert it for now if we are not sure, as this is an API change, however obscure for most users.

I appreciate your effort on designing an alternative solution. Hopefully, it works out well.

As an aside, it would be really helpful if you could track how the compilation of your codebase performs as clang evolves, regardless if we keep this change or not :)
Maybe you can reuse something from http://llvm-compile-time-tracker.com/

Good point about tracking compile time. We do have compiler performance tests running in a controlled environment with a number of measures in place to reduce errors in results, but they are limited to a rather small sample of build targets. Tracking compiler performance (times, memory used) for all of our code and using this as a regression test for compiler performance is impractical due to the size of the code base, rate of changes, and the design of the build system (high level of parallelism, aggressive caching, shared build cluster consisting of machines with different performance characteristics).

[davrec]

Two last thoughts:
1: To reiterate it doesn't seem right to view this (or any patch adding not-semantically-relevant info to the AST) as a one-size-fits-all costs vs. benefits optimization. On the one hand, the additional AST info hurts compilation performance. On the other, the info might make debugging faster, or be useful to a tool. A flag governing how much non-semantically-necessary info to add to the AST really seems the better solution in general, and warrants more discussion in cases like this (e.g. Matheus's other resugaring patches, which may cause this debate to resurface regardless of the approach he takes here). The user could set the flag high when debugging, and decrease it when diagnostics/debug info are less expected/not needed. (In light of the performance tests done here, the performance benefit of allowing the user to omit *other* non-semantically-necessary nodes from the AST could be significant; such a flag could allow that.)

2: After thinking about it further I don't think the pack index provides sufficiently useful info in any case, since packs will always be expanded in full, in order: when you find the first SubstTemplateTypeParmType expanded from a pack, the rest are sure to be right behind. IIUC I see how including the pack index makes resugaring more straightforward: the substitution of the sugared info for the non-sugared info occurs via a TreeTransform (see clang/lib/Sema/SemaTemplate.cpp in https://reviews.llvm.org/D127695), and by storing the pack index Matheus can simply override TransformSubstTemplateTypeParmType to make use of the pack index to easily fetch the corresponding sugared info. But since the pack indices are predictable given a bird's eye view of the AST, maybe state info can be stored in the TreeTransform to allow the pack index to be inferred in each call to TransformSubstTemplateTypeParmType?

[mizvekov]

In D128113#3753565, @davrec wrote:

2: After thinking about it further I don't think the pack index provides sufficiently useful info in any case, since packs will always be expanded in full, in order: when you find the first SubstTemplateTypeParmType expanded from a pack, the rest are sure to be right behind. IIUC I see how including the pack index makes resugaring more straightforward: the substitution of the sugared info for the non-sugared info occurs via a TreeTransform (see clang/lib/Sema/SemaTemplate.cpp in https://reviews.llvm.org/D127695), and by storing the pack index Matheus can simply override TransformSubstTemplateTypeParmType to make use of the pack index to easily fetch the corresponding sugared info. But since the pack indices are predictable given a bird's eye view of the AST, maybe state info can be stored in the TreeTransform to allow the pack index to be inferred in each call to TransformSubstTemplateTypeParmType?

Packs are expanded from patterns, which is an arbitrary type that will reference one or more parameter pack anywhere within. So going back from an expanded pack back to a pattern + number of expansions will take more effort and we may need to add new markings to the AST to help with that.

Check this example out: https://godbolt.org/z/rsGsM6GrM

template <class ...Ts> struct A {
  template <class ...Us> struct B {
      using type1 = void ((void (*...fps)(Ts, Us)));
  };
};
using type2 = A<int, char>::B<short, bool>::type1;

TypeAliasDecl 0x55ffe8b45368 <line:8:1, col:45> col:7 type2 'A<int, char>::B<short, bool>::type1':'void ((void (*)(int, short), void (*)(char, bool)))'
  `-ElaboratedType 0x55ffe8b452f0 'A<int, char>::B<short, bool>::type1' sugar
    `-TypedefType 0x55ffe8b452d0 'A<int, char>::B<short, bool>::type1' sugar
      |-TypeAlias 0x55ffe8b45258 'type1'
      `-FunctionProtoType 0x55ffe8b451e0 'void ((void (*)(int, short), void (*)(char, bool)))' cdecl
        |-ParenType 0x55ffe8b12150 'void' sugar
        | `-BuiltinType 0x55ffe8ac6370 'void'
        |-PointerType 0x55ffe8b44550 'void (*)(int, short)'
        | `-ParenType 0x55ffe8b444f0 'void (int, short)' sugar
        |   `-FunctionProtoType 0x55ffe8b444b0 'void (int, short)' cdecl
        |     |-BuiltinType 0x55ffe8ac6370 'void'
        |     |-SubstTemplateTypeParmType 0x55ffe8b44310 'int' sugar
        |     | |-TemplateTypeParmType 0x55ffe8b11440 'Ts' dependent contains_unexpanded_pack depth 0 index 0 pack
        |     | | `-TemplateTypeParm 0x55ffe8b113c0 'Ts'
        |     | `-BuiltinType 0x55ffe8ac6410 'int'
        |     `-SubstTemplateTypeParmType 0x55ffe8b443c0 'short' sugar
        |       |-TemplateTypeParmType 0x55ffe8b11960 'Us' dependent contains_unexpanded_pack depth 1 index 0 pack
        |       | `-TemplateTypeParm 0x55ffe8b118d8 'Us'
        |       `-BuiltinType 0x55ffe8ac63f0 'short'
        `-PointerType 0x55ffe8b450c0 'void (*)(char, bool)'
          `-ParenType 0x55ffe8b45060 'void (char, bool)' sugar
            `-FunctionProtoType 0x55ffe8b447d0 'void (char, bool)' cdecl
              |-BuiltinType 0x55ffe8ac6370 'void'
              |-SubstTemplateTypeParmType 0x55ffe8b44630 'char' sugar
              | |-TemplateTypeParmType 0x55ffe8b11440 'Ts' dependent contains_unexpanded_pack depth 0 index 0 pack
              | | `-TemplateTypeParm 0x55ffe8b113c0 'Ts'
              | `-BuiltinType 0x55ffe8ac63b0 'char'
              `-SubstTemplateTypeParmType 0x55ffe8b446e0 'bool' sugar
                |-TemplateTypeParmType 0x55ffe8b11960 'Us' dependent contains_unexpanded_pack depth 1 index 0 pack
                | `-TemplateTypeParm 0x55ffe8b118d8 'Us'
                `-BuiltinType 0x55ffe8ac6390 'bool'

And in fact, a given parameter pack might be referenced more than one time in a given pack expansion pattern:

template <class ...Ts> struct A {
  template <class ...Us> struct B {
      using type1 = void ((void (*...fps)(Ts, Ts, Us)));
  };
};

Ie those two Ts are referencing the same argument within the pack, we can't confuse that with an expansion.

So think also about a case like the above, but where you are performing the expansion just one time. It doesn't look like to me you can figure that out from what Clang leaves behind in the AST at the moment.
We may need to create a new AST node, which is like a Subst variant of a PackExpansionType, at the expansion loci.

[davrec]

Great examples.

Check this example out: https://godbolt.org/z/rsGsM6GrM

template <class ...Ts> struct A {
  template <class ...Us> struct B {
      using type1 = void ((void (*...fps)(Ts, Us)));
  };
};
using type2 = A<int, char>::B<short, bool>::type1;

TypeAliasDecl 0x55ffe8b45368 <line:8:1, col:45> col:7 type2 'A<int, char>::B<short, bool>::type1':'void ((void (*)(int, short), void (*)(char, bool)))'
  `-ElaboratedType 0x55ffe8b452f0 'A<int, char>::B<short, bool>::type1' sugar
    `-TypedefType 0x55ffe8b452d0 'A<int, char>::B<short, bool>::type1' sugar
      |-TypeAlias 0x55ffe8b45258 'type1'
      `-FunctionProtoType 0x55ffe8b451e0 'void ((void (*)(int, short), void (*)(char, bool)))' cdecl
        |-ParenType 0x55ffe8b12150 'void' sugar
        | `-BuiltinType 0x55ffe8ac6370 'void'
        |-PointerType 0x55ffe8b44550 'void (*)(int, short)'
        | `-ParenType 0x55ffe8b444f0 'void (int, short)' sugar
        |   `-FunctionProtoType 0x55ffe8b444b0 'void (int, short)' cdecl
        |     |-BuiltinType 0x55ffe8ac6370 'void'
        |     |-SubstTemplateTypeParmType 0x55ffe8b44310 'int' sugar
        |     | |-TemplateTypeParmType 0x55ffe8b11440 'Ts' dependent contains_unexpanded_pack depth 0 index 0 pack
        |     | | `-TemplateTypeParm 0x55ffe8b113c0 'Ts'
        |     | `-BuiltinType 0x55ffe8ac6410 'int'
        |     `-SubstTemplateTypeParmType 0x55ffe8b443c0 'short' sugar
        |       |-TemplateTypeParmType 0x55ffe8b11960 'Us' dependent contains_unexpanded_pack depth 1 index 0 pack
        |       | `-TemplateTypeParm 0x55ffe8b118d8 'Us'
        |       `-BuiltinType 0x55ffe8ac63f0 'short'
        `-PointerType 0x55ffe8b450c0 'void (*)(char, bool)'
          `-ParenType 0x55ffe8b45060 'void (char, bool)' sugar
            `-FunctionProtoType 0x55ffe8b447d0 'void (char, bool)' cdecl
              |-BuiltinType 0x55ffe8ac6370 'void'
              |-SubstTemplateTypeParmType 0x55ffe8b44630 'char' sugar
              | |-TemplateTypeParmType 0x55ffe8b11440 'Ts' dependent contains_unexpanded_pack depth 0 index 0 pack
              | | `-TemplateTypeParm 0x55ffe8b113c0 'Ts'
              | `-BuiltinType 0x55ffe8ac63b0 'char'
              `-SubstTemplateTypeParmType 0x55ffe8b446e0 'bool' sugar
                |-TemplateTypeParmType 0x55ffe8b11960 'Us' dependent contains_unexpanded_pack depth 1 index 0 pack
                | `-TemplateTypeParm 0x55ffe8b118d8 'Us'
                `-BuiltinType 0x55ffe8ac6390 'bool'

If it were as simple as the above case the Resugarer TreeTransform could say keep a map of TemplateTypeParmTypes to current pack indices, and iterate those during each each TransformSubstTemplateTypeParmType call, but...

And in fact, a given parameter pack might be referenced more than one time in a given pack expansion pattern:

template <class ...Ts> struct A {
  template <class ...Us> struct B {
      using type1 = void ((void (*...fps)(Ts, Ts, Us)));
  };
};

Ie those two Ts are referencing the same argument within the pack, we can't confuse that with an expansion.

So think also about a case like the above, but where you are performing the expansion just one time. It doesn't look like to me you can figure that out from what Clang leaves behind in the AST at the moment.

...the different Ts are the same TemplateTypeParmType, so that wouldn't work. You're right, more info is needed.

We may need to create a new AST node, which is like a Subst variant of a PackExpansionType, at the expansion loci.

Or, maybe TemplateTypeParmType could store a number that would make it unique for each *instance* of it in a given expansion? Or just SubstTemplateTypeParmType could store this number in addition to its TemplateTypeParmType? (E.g. the first Ts in an expansion is 0, the second Ts in the same expansion is 1, etc. - but it resets for the next expansion.)

[mizvekov]

In D128113#3753624, @davrec wrote:

Or just SubstTemplateTypeParmType could store this number in addition to its TemplateTypeParmType? (E.g. the first Ts in an expansion is 0, the second Ts in the same expansion is 1, etc. - but it resets for the next expansion.)

Well that number is just the pack_index, as implemented in this current patch :)

I like the idea obviously, this patch is so simple, and simple solutions are the best when they are good enough.

I am not completely sold that this solution is not good enough, it's hard to make the case that the reproducer is a reasonable program, but at the same time it's obvious that packs where designed to deal very cheaply with very large number of arguments.

And this patch does not make the worst case worse: If all arguments are different types in all expansions, then a different pack_index will not cause an extra uniquing because the underlying types will be different as well anyway.

[davrec]

In D128113#3753640, @mizvekov wrote:

In D128113#3753624, @davrec wrote:

Or just SubstTemplateTypeParmType could store this number in addition to its TemplateTypeParmType? (E.g. the first Ts in an expansion is 0, the second Ts in the same expansion is 1, etc. - but it resets for the next expansion.)

Well that number is just the pack_index, as implemented in this current patch :)

I meant that, in an of expansion (Ts, Ts, Us), either the two Ts would be two unique TemplateTypeParmTypes by adding an instanceIndex or whatever to refer to the two different syntactic instances (this would of course naturally result in two unique STTPTs), or for a bit more savings the TTPTs for the two Ts could continue to be the same but their STTPTs would include the instanceIndex, so there is only one unique TTPT but two unique STTPTs referring to Ts.

I.e. if there are 100 types in in Ts there would still only be two unique SubstTemplateTypeParmTypes created, as opposed to only 1 as there currently is, or 100 as this patch creates.

Any way it is done, the goal would be to make the STTPTs just as unique as necessary so the Resugarer can keep map from the unique STTPTs to its current pack index, and iterate the relevant index with each call to TransformSubstTemplateTypeParmType.

If I'm missing something and it is substantially more complex than that, then you're right that storing the pack index might end up the best solution - we don't want to e.g. have to do considerable Sema logic in the Resugarer just to infer the pack index.

[davrec]

In D128113#3753656, @davrec wrote:

In D128113#3753640, @mizvekov wrote:

In D128113#3753624, @davrec wrote:

Or just SubstTemplateTypeParmType could store this number in addition to its TemplateTypeParmType? (E.g. the first Ts in an expansion is 0, the second Ts in the same expansion is 1, etc. - but it resets for the next expansion.)

Well that number is just the pack_index, as implemented in this current patch :)

Disregard my previous comment, you're right, that would be identical. I'm mixing up my STTPTs and TTPTs :). So the proposed solution would be to make the TTPTs unique, and map from the TTPTs to their current pack indices in the Resugarer. But, that is probably identical in terms of memory usage as your proposal to introduce a new sugar type representing unique expansion instances, and the latter is probably clearer/less disruptive.

Thanks for your work on this, and for explaining these complexities.

[mizvekov]

In D128113#3753656, @davrec wrote:

If I'm missing something and it is substantially more complex than that, then you're right that storing the pack index might end up the best solution - we don't want to e.g. have to do considerable Sema logic in the Resugarer just to infer the pack index.

Having a new Subst-like node that wraps the whole expanded pattern seems to simplify the case where we need to take the type apart, such as deductions, leaving you without the 'birds-eye' view. Otherwise we would need to dig into the type to figure out what pack indexes we need to preserve in the resulting type.

[mizvekov]

In D128113#3753662, @davrec wrote:

Thanks for your work on this, and for explaining these complexities.

TBH I still don't know what to do here from the project perspective. I have a new deadline now that runs until November.

It seems that sitting down, figuring out a solution and coming up with a review-ready patch would take a considerable portion of that time. And then the review could take a year.

Meanwhile there is still considerable work remaining on the resugarer, in terms of addressing performance and getting everything into a reviewable state.

So I might try leaving this problem aside and not handle packs, for now. This would make us not able to resugar tuples for example, which is very unfortunate.

But in the unlikely case there was someone else interested in solving this problem, this could be parallelized.

[mizvekov]

@davrec @alexfh

I finally managed to have a talk to @rsmith about this.

He thinks that, even if we can't come up with a better solution in time, the benefits of this patch justify the costs observed, as those substitution nodes are pretty useless without a way to index the pack, and having a rich AST is one of Clang's main goals.

But he also came up with this nifty idea that this high cost is perhaps coming because we are reindexing the whole pack every time that repro recurses on that disjunction and we consume the first element in the deduction.
And that a good solution for this might be to just index the pack backwards, so that 0 is the last element.

I will try that sometime soon. Even if I don't see an improvement, any further objections we just re-merge this?

PS: That does not disregard the other ideas to further improve this in the future. Another thing he noted that would be important is to also be able to represent in the resulting AST a pack that expanded 0 times.

[davrec]

In D128113#3777353, @mizvekov wrote:

@davrec @alexfh

I finally managed to have a talk to @rsmith about this.

He thinks that, even if we can't come up with a better solution in time, the benefits of this patch justify the costs observed, as those substitution nodes are pretty useless without a way to index the pack, and having a rich AST is one of Clang's main goals.

I support that - re-merge for now, and consider ways to reduce costs going forward.

I thought this through every which way and could not avoid @mizvekov's conclusion, that the only other way would be another Subst* type node, from which the pack indices could be inferred, but only via non-straightforward code requiring a bird's eye view of the AST.

Taking a step back and reconsidering, it's clear the original way - just storing the pack index - is very much preferable to all that complexity. The benefits justify the costs for most users, and for clang developers who would be burdened by the appearance of an obscure new type class. And as I said previously I think broad flags governing how much sugar/non-semantic info is added to the AST, i.e. letting users balance benefits vs. costs for themselves, is the better way to handle these concerns.

[mizvekov]

The reverse indexing worked great for that problem, the patch has no perf impact now on that reproduction.cpp.

That doesn't mean it doesn't have any impact in general, or that it can't be further improved, but other solutions will take more time to develop and we can revisit this later.

clang/docs/ReleaseNotes.rst

 - Clang configuration files are now read through the virtual file system
   rather than the physical one, if these are different.
 - Clang will now no longer treat a C 'overloadable' function without a prototype as
   a variadic function with the attribute.  This should make further diagnostics more
   clear.
 - Fixes to builtin template emulation of regular templates.
   `Issue 42102 <https://github.com/llvm/llvm-project/issues/42102>`_
   `Issue 51928 <https://github.com/llvm/llvm-project/issues/51928>`_
+- A SubstTemplateTypeParmType can now represent the pack index for a
+  substitution from an expanded pack.
+  `Issue 56099 <https://github.com/llvm/llvm-project/issues/56099>`_
 
 
 Improvements to Clang's diagnostics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 - Clang will now check compile-time determinable string literals as format strings.
   Fixes `Issue 55805: <https://github.com/llvm/llvm-project/issues/55805>`_.
 - ``-Wformat`` now recognizes ``%b`` for the ``printf``/``scanf`` family of
   functions and ``%B`` for the ``printf`` family of functions. Fixes

clang/include/clang/AST/ASTContext.h

public:
 
   QualType getAttributedType(attr::Kind attrKind, QualType modifiedType,
                              QualType equivalentType) const;
 
   QualType getBTFTagAttributedType(const BTFTypeTagAttr *BTFAttr,
                                    QualType Wrapped);
 
   QualType getSubstTemplateTypeParmType(const TemplateTypeParmType *Replaced,
-                                        QualType Replacement) const;
-  QualType getSubstTemplateTypeParmPackType(
-                                          const TemplateTypeParmType *Replaced,
-                                            const TemplateArgument &ArgPack);
+                                        QualType Replacement,
+                                        Optional<unsigned> PackIndex) const;
+  QualType
+  getSubstTemplateTypeParmPackType(const TemplateTypeParmType *Replaced,
 
   QualType
   getTemplateTypeParmType(unsigned Depth, unsigned Index,
                           bool ParameterPack,
                           TemplateTypeParmDecl *ParmDecl = nullptr) const;
 
   QualType getTemplateSpecializationType(TemplateName T,
                                          ArrayRef<TemplateArgument> Args,

clang/include/clang/AST/JSONNodeDumper.h

public:
   void VisitArrayType(const ArrayType *AT);
   void VisitConstantArrayType(const ConstantArrayType *CAT);
   void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *VT);
   void VisitVectorType(const VectorType *VT);
   void VisitUnresolvedUsingType(const UnresolvedUsingType *UUT);
   void VisitUnaryTransformType(const UnaryTransformType *UTT);
   void VisitTagType(const TagType *TT);
   void VisitTemplateTypeParmType(const TemplateTypeParmType *TTPT);
+  void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *STTPT);
   void VisitAutoType(const AutoType *AT);
   void VisitTemplateSpecializationType(const TemplateSpecializationType *TST);
   void VisitInjectedClassNameType(const InjectedClassNameType *ICNT);
   void VisitObjCInterfaceType(const ObjCInterfaceType *OIT);
   void VisitPackExpansionType(const PackExpansionType *PET);
   void VisitElaboratedType(const ElaboratedType *ET);
   void VisitMacroQualifiedType(const MacroQualifiedType *MQT);
   void VisitMemberPointerType(const MemberPointerType *MPT);

clang/include/clang/AST/TextNodeDumper.h

#include "clang/AST/AttrTextNodeDump.inc"
   void VisitFunctionType(const FunctionType *T);
   void VisitFunctionProtoType(const FunctionProtoType *T);
   void VisitUnresolvedUsingType(const UnresolvedUsingType *T);
   void VisitUsingType(const UsingType *T);
   void VisitTypedefType(const TypedefType *T);
   void VisitUnaryTransformType(const UnaryTransformType *T);
   void VisitTagType(const TagType *T);
   void VisitTemplateTypeParmType(const TemplateTypeParmType *T);
+  void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T);
   void VisitAutoType(const AutoType *T);
   void VisitDeducedTemplateSpecializationType(
       const DeducedTemplateSpecializationType *T);
   void VisitTemplateSpecializationType(const TemplateSpecializationType *T);
   void VisitInjectedClassNameType(const InjectedClassNameType *T);
   void VisitObjCInterfaceType(const ObjCInterfaceType *T);
   void VisitPackExpansionType(const PackExpansionType *T);
 

clang/include/clang/AST/Type.h

class AutoTypeBitfields {
     /// However as this limit is somewhat easy to hit with template
     /// metaprogramming we'd prefer to keep it as large as possible.
     /// At the moment it has been left as a non-bitfield since this type
     /// safely fits in 64 bits as an unsigned, so there is no reason to
     /// introduce the performance impact of a bitfield.
     unsigned NumArgs;
   };
 
+  class SubstTemplateTypeParmTypeBitfields {
+    friend class SubstTemplateTypeParmType;
+
+    unsigned : NumTypeBits;
+
+    /// Represents the index within a pack if this represents a substitution
+    /// from a pack expansion. This index starts at the end of the pack and
+    /// increments towards the beginning.
+    /// Positive non-zero number represents the index + 1.
+    /// Zero means this is not substituted from an expansion.
+    unsigned PackIndex : 16;
+  };
+
   class SubstTemplateTypeParmPackTypeBitfields {
     friend class SubstTemplateTypeParmPackType;
 
     unsigned : NumTypeBits;
 
     /// The number of template arguments in \c Arguments, which is
     /// expected to be able to hold at least 1024 according to [implimits].
     /// However as this limit is somewhat easy to hit with template
union {
     AutoTypeBitfields AutoTypeBits;
     BuiltinTypeBitfields BuiltinTypeBits;
     FunctionTypeBitfields FunctionTypeBits;
     ObjCObjectTypeBitfields ObjCObjectTypeBits;
     ReferenceTypeBitfields ReferenceTypeBits;
     TypeWithKeywordBitfields TypeWithKeywordBits;
     ElaboratedTypeBitfields ElaboratedTypeBits;
     VectorTypeBitfields VectorTypeBits;
+    SubstTemplateTypeParmTypeBitfields SubstTemplateTypeParmTypeBits;
     SubstTemplateTypeParmPackTypeBitfields SubstTemplateTypeParmPackTypeBits;
     TemplateSpecializationTypeBitfields TemplateSpecializationTypeBits;
     DependentTemplateSpecializationTypeBitfields
       DependentTemplateSpecializationTypeBits;
     PackExpansionTypeBitfields PackExpansionTypeBits;
   };
 
 private:

 /// type was originally written as a template type parameter;
 /// therefore they are never canonical.
 class SubstTemplateTypeParmType : public Type, public llvm::FoldingSetNode {
   friend class ASTContext;
 
   // The original type parameter.
   const TemplateTypeParmType *Replaced;
 
-  SubstTemplateTypeParmType(const TemplateTypeParmType *Param, QualType Canon)
-      : Type(SubstTemplateTypeParm, Canon, Canon->getDependence()),
-        Replaced(Param) {}
+  SubstTemplateTypeParmType(const TemplateTypeParmType *Param, QualType Canon,
+                            Optional<unsigned> PackIndex);
 
 public:
   /// Gets the template parameter that was substituted for.
   const TemplateTypeParmType *getReplacedParameter() const {
     return Replaced;
   }
 
   /// Gets the type that was substituted for the template
   /// parameter.
   QualType getReplacementType() const {
     return getCanonicalTypeInternal();
   }
 
+  Optional<unsigned> getPackIndex() const {
+    if (SubstTemplateTypeParmTypeBits.PackIndex == 0)
+      return None;
+    return SubstTemplateTypeParmTypeBits.PackIndex - 1;
+  }
+
   bool isSugared() const { return true; }
   QualType desugar() const { return getReplacementType(); }
 
   void Profile(llvm::FoldingSetNodeID &ID) {
-    Profile(ID, getReplacedParameter(), getReplacementType());
+    Profile(ID, getReplacedParameter(), getReplacementType(), getPackIndex());
   }
 
   static void Profile(llvm::FoldingSetNodeID &ID,
                       const TemplateTypeParmType *Replaced,
-                      QualType Replacement) {
+                      QualType Replacement, Optional<unsigned> PackIndex) {
     ID.AddPointer(Replaced);
     ID.AddPointer(Replacement.getAsOpaquePtr());
+    ID.AddInteger(PackIndex ? *PackIndex - 1 : 0);
   }
 
   static bool classof(const Type *T) {
     return T->getTypeClass() == SubstTemplateTypeParm;
   }
 };
 
 /// Represents the result of substituting a set of types for a template

clang/include/clang/AST/TypeProperties.td

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

clang/lib/AST/ASTContext.cpp

QualType ASTContext::getBTFTagAttributedType(const BTFTypeTagAttr *BTFAttr,
   BTFTagAttributedTypes.InsertNode(Ty, InsertPos);
 
   return QualType(Ty, 0);
 }
 
 /// Retrieve a substitution-result type.
 QualType
 ASTContext::getSubstTemplateTypeParmType(const TemplateTypeParmType *Parm,
-                                         QualType Replacement) const {
+                                         QualType Replacement,
+                                         Optional<unsigned> PackIndex) const {
   assert(Replacement.isCanonical()
          && "replacement types must always be canonical");
 
   llvm::FoldingSetNodeID ID;
-  SubstTemplateTypeParmType::Profile(ID, Parm, Replacement);
+  SubstTemplateTypeParmType::Profile(ID, Parm, Replacement, PackIndex);
   void *InsertPos = nullptr;
   SubstTemplateTypeParmType *SubstParm
     = SubstTemplateTypeParmTypes.FindNodeOrInsertPos(ID, InsertPos);
 
   if (!SubstParm) {
     SubstParm = new (*this, TypeAlignment)
-      SubstTemplateTypeParmType(Parm, Replacement);
+        SubstTemplateTypeParmType(Parm, Replacement, PackIndex);
     Types.push_back(SubstParm);
     SubstTemplateTypeParmTypes.InsertNode(SubstParm, InsertPos);
   }
 
   return QualType(SubstParm, 0);
 }
 
 /// Retrieve a
case Type::MacroQualified: {
     return Ctx.getMacroQualifiedType(Ctx.getQualifiedType(Underlying), IX);
   }
   case Type::SubstTemplateTypeParm: {
     const auto *SX = cast<SubstTemplateTypeParmType>(X),
                *SY = cast<SubstTemplateTypeParmType>(Y);
     const TemplateTypeParmType *PX = SX->getReplacedParameter();
     if (PX != SY->getReplacedParameter())
       return QualType();
-
-    return Ctx.getSubstTemplateTypeParmType(PX,
-                                            Ctx.getQualifiedType(Underlying));
+    auto PackIndex = SX->getPackIndex();
+    if (PackIndex != SY->getPackIndex())
+      return QualType();
+    return Ctx.getSubstTemplateTypeParmType(
+        PX, Ctx.getQualifiedType(Underlying), PackIndex);
   }
   case Type::ObjCTypeParam:
     // FIXME: Try to merge these.
     return QualType();
   case Type::Paren:
     return Ctx.getParenType(Ctx.getQualifiedType(Underlying));
 
   case Type::TemplateSpecialization: {

clang/lib/AST/ASTImporter.cpp

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

clang/lib/AST/ASTStructuralEquivalence.cpp

case Type::SubstTemplateTypeParm: {
     const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
     if (!IsStructurallyEquivalent(Context,
                                   QualType(Subst1->getReplacedParameter(), 0),
                                   QualType(Subst2->getReplacedParameter(), 0)))
       return false;
     if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
                                   Subst2->getReplacementType()))
       return false;
+    if (Subst1->getPackIndex() != Subst2->getPackIndex())
+      return false;
     break;
   }
 
   case Type::SubstTemplateTypeParmPack: {
     const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
     const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
     if (!IsStructurallyEquivalent(Context,
                                   QualType(Subst1->getReplacedParameter(), 0),

clang/lib/AST/JSONNodeDumper.cpp

 void JSONNodeDumper::VisitTemplateTypeParmType(
     const TemplateTypeParmType *TTPT) {
   JOS.attribute("depth", TTPT->getDepth());
   JOS.attribute("index", TTPT->getIndex());
   attributeOnlyIfTrue("isPack", TTPT->isParameterPack());
   JOS.attribute("decl", createBareDeclRef(TTPT->getDecl()));
 }
 
+void JSONNodeDumper::VisitSubstTemplateTypeParmType(
+    const SubstTemplateTypeParmType *STTPT) {
+  if (auto PackIndex = STTPT->getPackIndex())
+    JOS.attribute("pack_index", *PackIndex);
+}
+
 void JSONNodeDumper::VisitAutoType(const AutoType *AT) {
   JOS.attribute("undeduced", !AT->isDeduced());
   switch (AT->getKeyword()) {
   case AutoTypeKeyword::Auto:
     JOS.attribute("typeKeyword", "auto");
     break;
   case AutoTypeKeyword::DecltypeAuto:
     JOS.attribute("typeKeyword", "decltype(auto)");

clang/lib/AST/TextNodeDumper.cpp

 
 void TextNodeDumper::VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
   OS << " depth " << T->getDepth() << " index " << T->getIndex();
   if (T->isParameterPack())
     OS << " pack";
   dumpDeclRef(T->getDecl());
 }
 
+void TextNodeDumper::VisitSubstTemplateTypeParmType(
+    const SubstTemplateTypeParmType *T) {
+  if (auto PackIndex = T->getPackIndex())
+    OS << " pack_index " << *PackIndex;
+}
+
 void TextNodeDumper::VisitAutoType(const AutoType *T) {
   if (T->isDecltypeAuto())
     OS << " decltype(auto)";
   if (!T->isDeduced())
     OS << " undeduced";
   if (T->isConstrained()) {
     dumpDeclRef(T->getTypeConstraintConcept());
     for (const auto &Arg : T->getTypeConstraintArguments())

clang/lib/AST/Type.cpp

QualType VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
     if (replacementType.isNull())
       return {};
 
     if (replacementType.getAsOpaquePtr()
           == T->getReplacementType().getAsOpaquePtr())
       return QualType(T, 0);
 
     return Ctx.getSubstTemplateTypeParmType(T->getReplacedParameter(),
-                                            replacementType);
+                                            replacementType, T->getPackIndex());
   }
 
   // FIXME: Non-trivial to implement, but important for C++
   SUGARED_TYPE_CLASS(TemplateSpecialization)
 
   QualType VisitAutoType(const AutoType *T) {
     if (!T->isDeduced())
       return QualType(T, 0);

 CXXRecordDecl *InjectedClassNameType::getDecl() const {
   return cast<CXXRecordDecl>(getInterestingTagDecl(Decl));
 }
 
 IdentifierInfo *TemplateTypeParmType::getIdentifier() const {
   return isCanonicalUnqualified() ? nullptr : getDecl()->getIdentifier();
 }
 
+SubstTemplateTypeParmType::SubstTemplateTypeParmType(
+    const TemplateTypeParmType *Param, QualType Canon,
+    Optional<unsigned> PackIndex)
+    : Type(SubstTemplateTypeParm, Canon, Canon->getDependence()),
+      Replaced(Param) {
+  SubstTemplateTypeParmTypeBits.PackIndex = PackIndex ? *PackIndex + 1 : 0;
+}
+
 SubstTemplateTypeParmPackType::SubstTemplateTypeParmPackType(
     const TemplateTypeParmType *Param, QualType Canon,
     const TemplateArgument &ArgPack)
     : Type(SubstTemplateTypeParmPack, Canon,
            TypeDependence::DependentInstantiation |
                TypeDependence::UnexpandedPack),
       Replaced(Param), Arguments(ArgPack.pack_begin()) {
   SubstTemplateTypeParmPackTypeBits.NumArgs = ArgPack.pack_size();

clang/lib/Sema/SemaTemplate.cpp

checkBuiltinTemplateIdType(Sema &SemaRef, BuiltinTemplateDecl *BTD,
                            const SmallVectorImpl<TemplateArgument> &Converted,
                            SourceLocation TemplateLoc,
                            TemplateArgumentListInfo &TemplateArgs) {
   ASTContext &Context = SemaRef.getASTContext();
 
   TemplateParameterList *TPL = BTD->getTemplateParameters();
 
   // Wrap the type in substitution sugar.
-  auto getSubstType = [&](unsigned IndexReplaced, QualType Replacement) {
+  auto getSubstType = [&](QualType Replacement, unsigned IndexReplaced,
+                          Optional<unsigned> PackIndexReplaced) {
     QualType TTP = SemaRef.Context.getTemplateTypeParmType(
         0, IndexReplaced, false,
         cast<TemplateTypeParmDecl>(TPL->getParam(IndexReplaced)));
     return SemaRef.Context.getSubstTemplateTypeParmType(
-        cast<TemplateTypeParmType>(TTP), Replacement.getCanonicalType());
+        cast<TemplateTypeParmType>(TTP), Replacement.getCanonicalType(),
+        PackIndexReplaced);
   };
 
   switch (BTD->getBuiltinTemplateKind()) {
   case BTK__make_integer_seq: {
     // Specializations of __make_integer_seq<S, T, N> are treated like
     // S<T, 0, ..., N-1>.
 
     QualType OrigType = Converted[1].getAsType();
     // C++14 [inteseq.intseq]p1:
     //   T shall be an integer type.
     if (!OrigType->isDependentType() && !OrigType->isIntegralType(Context)) {
       SemaRef.Diag(TemplateArgs[1].getLocation(),
                    diag::err_integer_sequence_integral_element_type);
       return QualType();
     }
 
     TemplateArgument NumArgsArg = Converted[2];
     if (NumArgsArg.isDependent())
       return Context.getCanonicalTemplateSpecializationType(TemplateName(BTD),
                                                             Converted);
 
     TemplateArgumentListInfo SyntheticTemplateArgs;
     // The type argument, wrapped in substitution sugar, gets reused as the
     // first template argument in the synthetic template argument list.
-    QualType SyntheticType = getSubstType(1, OrigType);
+    QualType SyntheticType = getSubstType(OrigType, 1, None);
     SyntheticTemplateArgs.addArgument(
         TemplateArgumentLoc(TemplateArgument(SyntheticType),
                             SemaRef.Context.getTrivialTypeSourceInfo(
                                 SyntheticType, TemplateArgs[1].getLocation())));
 
     if (llvm::APSInt NumArgs = NumArgsArg.getAsIntegral(); NumArgs >= 0) {
       // Expand N into 0 ... N-1.
       for (llvm::APSInt I(NumArgs.getBitWidth(), NumArgs.isUnsigned());
case BTK__type_pack_element:
     // If the Index is out of bounds, the program is ill-formed.
     if (Index >= Ts.pack_size()) {
       SemaRef.Diag(TemplateArgs[0].getLocation(),
                    diag::err_type_pack_element_out_of_bounds);
       return QualType();
     }
 
     // We simply return the type at index `Index`.
-    auto Nth = std::next(Ts.pack_begin(), Index.getExtValue());
-    return getSubstType(1, Nth->getAsType());
+    int64_t N = Index.getExtValue();
+    return getSubstType(Ts.getPackAsArray()[N].getAsType(), 1,
+                        Ts.pack_size() - 1 - N);
   }
   llvm_unreachable("unexpected BuiltinTemplateDecl!");
 }
 
 /// Determine whether this alias template is "enable_if_t".
 /// libc++ >=14 uses "__enable_if_t" in C++11 mode.
 static bool isEnableIfAliasTemplate(TypeAliasTemplateDecl *AliasTemplate) {
   return AliasTemplate->getName().equals("enable_if_t") ||

clang/lib/Sema/SemaTemplateInstantiate.cpp

if (TemplateArgs.isRewrite()) {
       QualType NewT = Arg.getAsType();
       assert(isa<TemplateTypeParmType>(NewT) &&
              "type parm not rewritten to type parm");
       auto NewTL = TLB.push<TemplateTypeParmTypeLoc>(NewT);
       NewTL.setNameLoc(TL.getNameLoc());
       return NewT;
     }
 
+    Optional<unsigned> PackIndex;
     if (T->isParameterPack()) {
       assert(Arg.getKind() == TemplateArgument::Pack &&
              "Missing argument pack");
 
       if (getSema().ArgumentPackSubstitutionIndex == -1) {
         // We have the template argument pack, but we're not expanding the
         // enclosing pack expansion yet. Just save the template argument
         // pack for later substitution.
         QualType Result
           = getSema().Context.getSubstTemplateTypeParmPackType(T, Arg);
         SubstTemplateTypeParmPackTypeLoc NewTL
           = TLB.push<SubstTemplateTypeParmPackTypeLoc>(Result);
         NewTL.setNameLoc(TL.getNameLoc());
         return Result;
       }
 
+      // PackIndex starts from last element.
+      PackIndex = Arg.pack_size() - 1 - getSema().ArgumentPackSubstitutionIndex;
       Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
     }
 
     assert(Arg.getKind() == TemplateArgument::Type &&
            "Template argument kind mismatch");
 
     QualType Replacement = Arg.getAsType();
 
     // TODO: only do this uniquing once, at the start of instantiation.
-    QualType Result
-      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
+    QualType Result = getSema().Context.getSubstTemplateTypeParmType(
+        T, Replacement, PackIndex);
     SubstTemplateTypeParmTypeLoc NewTL
       = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
     NewTL.setNameLoc(TL.getNameLoc());
     return Result;
   }
 
   // The template type parameter comes from an inner template (e.g.,
   // the template parameter list of a member template inside the
TemplateInstantiator::TransformSubstTemplateTypeParmPackType(
   if (getSema().ArgumentPackSubstitutionIndex == -1) {
     // We aren't expanding the parameter pack, so just return ourselves.
     SubstTemplateTypeParmPackTypeLoc NewTL
       = TLB.push<SubstTemplateTypeParmPackTypeLoc>(TL.getType());
     NewTL.setNameLoc(TL.getNameLoc());
     return TL.getType();
   }
 
-  TemplateArgument Arg = TL.getTypePtr()->getArgumentPack();
-  Arg = getPackSubstitutedTemplateArgument(getSema(), Arg);
-  QualType Result = Arg.getAsType();
-
-  Result = getSema().Context.getSubstTemplateTypeParmType(
-                                      TL.getTypePtr()->getReplacedParameter(),
-                                                          Result);
+  const SubstTemplateTypeParmPackType *T = TL.getTypePtr();
+  TemplateArgument Pack = T->getArgumentPack();
+  TemplateArgument Arg = getPackSubstitutedTemplateArgument(getSema(), Pack);
+  // PackIndex starts from last element.
+  QualType Result = getSema().Context.getSubstTemplateTypeParmType(
+      T->getReplacedParameter(), Arg.getAsType(),
+      Pack.pack_size() - 1 - getSema().ArgumentPackSubstitutionIndex);
   SubstTemplateTypeParmTypeLoc NewTL
     = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
   NewTL.setNameLoc(TL.getNameLoc());
   return Result;
 }
 
 template<typename EntityPrinter>
 static concepts::Requirement::SubstitutionDiagnostic *

clang/lib/Sema/TreeTransform.h

else if (T.getObjCLifetime()) {
       if (const SubstTemplateTypeParmType *SubstTypeParam
                                 = dyn_cast<SubstTemplateTypeParmType>(T)) {
         QualType Replacement = SubstTypeParam->getReplacementType();
         Qualifiers Qs = Replacement.getQualifiers();
         Qs.removeObjCLifetime();
         Replacement = SemaRef.Context.getQualifiedType(
             Replacement.getUnqualifiedType(), Qs);
         T = SemaRef.Context.getSubstTemplateTypeParmType(
-            SubstTypeParam->getReplacedParameter(), Replacement);
+            SubstTypeParam->getReplacedParameter(), Replacement,
+            SubstTypeParam->getPackIndex());
       } else if ((AutoTy = dyn_cast<AutoType>(T)) && AutoTy->isDeduced()) {
         // 'auto' types behave the same way as template parameters.
         QualType Deduced = AutoTy->getDeducedType();
         Qualifiers Qs = Deduced.getQualifiers();
         Qs.removeObjCLifetime();
         Deduced =
             SemaRef.Context.getQualifiedType(Deduced.getUnqualifiedType(), Qs);
         T = SemaRef.Context.getAutoType(Deduced, AutoTy->getKeyword(),
QualType TreeTransform<Derived>::TransformSubstTemplateTypeParmType(
   // template arguments of template template parameters.
   TemporaryBase Rebase(*this, TL.getNameLoc(), DeclarationName());
   QualType Replacement = getDerived().TransformType(T->getReplacementType());
   if (Replacement.isNull())
     return QualType();
 
   // Always canonicalize the replacement type.
   Replacement = SemaRef.Context.getCanonicalType(Replacement);
-  QualType Result
-    = SemaRef.Context.getSubstTemplateTypeParmType(T->getReplacedParameter(),
-                                                   Replacement);
+  QualType Result = SemaRef.Context.getSubstTemplateTypeParmType(
+      T->getReplacedParameter(), Replacement, T->getPackIndex());
 
   // Propagate type-source information.
   SubstTemplateTypeParmTypeLoc NewTL
     = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
   NewTL.setNameLoc(TL.getNameLoc());
   return Result;
 
 }

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

 namespace PR56099 {
 template <typename... As> struct Y;
 template <typename... Bs> using Z = Y<Bs...>;
 template <typename... Cs> struct foo {
   template <typename... Ds> using bind = Z<Ds..., Cs...>;
 };
 using t1 = foo<int, short>::bind<char, float>;
 // CHECK:      TemplateSpecializationType 0x{{[^ ]*}} 'Y<char, float, int, short>' sugar Y
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar pack_index 3
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'Bs' dependent contains_unexpanded_pack depth 0 index 0 pack
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'float' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'float' sugar pack_index 2
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'Bs' dependent contains_unexpanded_pack depth 0 index 0 pack
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar pack_index 1
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'Bs' dependent contains_unexpanded_pack depth 0 index 0 pack
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'Bs' dependent contains_unexpanded_pack depth 0 index 0 pack
 
 template <typename... T> struct D {
   template <typename... U> using B = int(int (*...p)(T, U));
 };
 using t2 = D<float, char>::B<int, short>;
 // CHECK:      TemplateSpecializationType 0x{{[^ ]*}} 'B<int, short>' sugar alias B
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (int (*)(float, int), int (*)(char, short))' cdecl
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (float, int)' cdecl
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'float' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'float' sugar pack_index 1
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent contains_unexpanded_pack depth 0 index 0 pack
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'int' sugar pack_index 1
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
 // CHECK:      FunctionProtoType 0x{{[^ ]*}} 'int (char, short)' cdecl
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'char' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'T' dependent contains_unexpanded_pack depth 0 index 0 pack
-// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar
+// CHECK:      SubstTemplateTypeParmType 0x{{[^ ]*}} 'short' sugar pack_index 0
 // CHECK-NEXT: TemplateTypeParmType 0x{{[^ ]*}} 'U' dependent contains_unexpanded_pack depth 0 index 0 pack
 } // namespace PR56099

clang/test/SemaTemplate/type_pack_element.cpp

 // RUN: %clang_cc1 -std=c++2b -fsyntax-only -triple x86_64-linux-gnu -ast-dump -verify -xc++ < %s | FileCheck %s
 
 using test1 = __type_pack_element<0, int>;
 //      CHECK: |-TypeAliasDecl 0x{{[0-9A-Fa-f]+}} <<stdin>:3:1, col:41> col:7 test1 '__type_pack_element<0, int>':'int'
 // CHECK-NEXT:   `-ElaboratedType 0x{{[0-9A-Fa-f]+}} '__type_pack_element<0, int>' sugar
 // CHECK-NEXT:     `-TemplateSpecializationType 0x{{[0-9A-Fa-f]+}} '__type_pack_element<0, int>' sugar alias __type_pack_element
 // CHECK-NEXT:       |-TemplateArgument expr
 // CHECK-NEXT:       | `-ConstantExpr 0x{{[0-9A-Fa-f]+}} <col:35> 'unsigned long'
 // CHECK-NEXT:       |   |-value: Int 0
 // CHECK-NEXT:       |   `-ImplicitCastExpr 0x{{[0-9A-Fa-f]+}} <col:35> 'unsigned long' <IntegralCast>
 // CHECK-NEXT:       |     `-IntegerLiteral 0x{{[0-9A-Fa-f]+}} <col:35> 'int' 0
 // CHECK-NEXT:       |-TemplateArgument type 'int'
 // CHECK-NEXT:       | `-BuiltinType 0x{{[0-9A-Fa-f]+}} 'int'
-// CHECK-NEXT:       `-SubstTemplateTypeParmType 0x{{[0-9A-Fa-f]+}} 'int' sugar
+// CHECK-NEXT:       `-SubstTemplateTypeParmType 0x{{[0-9A-Fa-f]+}} 'int' sugar pack_index 0
 // CHECK-NEXT:         |-TemplateTypeParmType 0x{{[0-9A-Fa-f]+}} 'auto' dependent depth 0 index 1
 // CHECK-NEXT:         | `-TemplateTypeParm 0x{{[0-9A-Fa-f]+}} ''
 // CHECK-NEXT:         `-BuiltinType 0x{{[0-9A-Fa-f]+}} 'int'
 
 template<int N, class ...Ts> struct A {
   using test2 = __type_pack_element<N, Ts...>;
 //      CHECK: |-TypeAliasDecl 0x{{[0-9A-Fa-f]+}} <line:20:3, col:45> col:9 test2 '__type_pack_element<N, Ts...>':'__type_pack_element<N, type-parameter-0-1...>'
 // CHECK-NEXT:   `-ElaboratedType 0x{{[0-9A-Fa-f]+}} '__type_pack_element<N, Ts...>' sugar dependent

clang/unittests/AST/ASTImporterTest.cpp

TEST_P(ASTImporterOptionSpecificTestBase,
   EXPECT_TRUE(SharedStatePtr->getLookupTable()->contains(
       ToD1->getDeclContext(), ToD1->getTemplateParameters()->getParam(0)));
   EXPECT_EQ(ToD2->getTemplateParameters()->getParam(0)->getDeclContext(),
             ToD2->getDeclContext());
   EXPECT_TRUE(SharedStatePtr->getLookupTable()->contains(
       ToD2->getDeclContext(), ToD2->getTemplateParameters()->getParam(0)));
 }
 
+TEST_P(ASTImporterOptionSpecificTestBase, ImportSubstTemplateTypeParmType) {
+  constexpr auto Code = R"(
+    template <class A1, class... A2> struct A {
+      using B = A1(A2...);
+    };
+    template struct A<void, char, float, int, short>;
+    )";
+  Decl *FromTU = getTuDecl(Code, Lang_CXX11, "input.cpp");
+  auto *FromClass = FirstDeclMatcher<ClassTemplateSpecializationDecl>().match(
+      FromTU, classTemplateSpecializationDecl());
+
+  auto testType = [&](ASTContext &Ctx, const char *Name,
+                      llvm::Optional<unsigned> PackIndex) {
+    const auto *Subst = selectFirst<SubstTemplateTypeParmType>(
+        "sttp", match(substTemplateTypeParmType(
+                          hasReplacementType(hasCanonicalType(asString(Name))))
+                          .bind("sttp"),
+                      Ctx));
+    const char *ExpectedTemplateParamName = PackIndex ? "A2" : "A1";
+    ASSERT_TRUE(Subst);
+    ASSERT_EQ(Subst->getReplacedParameter()->getIdentifier()->getName(),
+              ExpectedTemplateParamName);
+    ASSERT_EQ(Subst->getPackIndex(), PackIndex);
+  };
+  auto tests = [&](ASTContext &Ctx) {
+    testType(Ctx, "void", None);
+    testType(Ctx, "char", 3);
+    testType(Ctx, "float", 2);
+    testType(Ctx, "int", 1);
+    testType(Ctx, "short", 0);
+  };
+
+  tests(FromTU->getASTContext());
+
+  ClassTemplateSpecializationDecl *ToClass = Import(FromClass, Lang_CXX11);
+  tests(ToClass->getASTContext());
+}
+
 const AstTypeMatcher<SubstTemplateTypeParmPackType>
     substTemplateTypeParmPackType;
 
 TEST_P(ASTImporterOptionSpecificTestBase, ImportSubstTemplateTypeParmPackType) {
   constexpr auto Code = R"(
     template<typename ...T> struct D {
       template<typename... U> using B = int(int (*...p)(T, U));
       template<typename U1, typename U2> D(B<U1, U2>*);