Dependent types representation in the NestedNameSpecifier

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Dependent types representation in the NestedNameSpecifier

Keane, Erich via cfe-dev
template <class T>
void f() {
  // Case 1:
  typename T::template U<int>::type x;
  // 'T::template U<int>' in the NNS is a DependentTemplateSpecializationType.

  // Case 2:
  typename T::U::type y;
  // 'T::U' in the NNS is an Identifier. Why not a DependentNameType?
}



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dependent types representation in the NestedNameSpecifier

Keane, Erich via cfe-dev
Good point.  At best implementing the second NNS as a dependent prefix + Identifier is redundant, since DependentNameType could already store this info, but you’re right that it would be more consistent with the first NNS you cite (the DependentTemplateSpecializationType) to implement the second NNS as a DependentNameType.

It seems like the Prefix field of NestedNameSpecifier is the root cause of this redundancy, and perhaps more general confusion.  I don’t think it is needed.  Perhaps an NNS should only store a simple PointerUnion of the various name kinds.  If we really want to keep the getPrefix() method we can define it as accessing the the properly cast pointer’s getQualifier() method.

DependentNameTypes/DependentTemplateSpecializationTypes each store their prefix on their own, so do ElaboratedTypes, so written prefixes for types would be covered, if I’m not mistaken.

The only non-trivial change I think needed would be for handling namespaces, for which we need to pair a written prefix with the NamespaceDecl or NamespaceAliasDecl.  In those cases, I think, we just define a "NamespaceName" class to handle the pairing of the decl and written qualifier, then allocate the NamespaceName as a trailing object of its NestedNameSpecifier in the applicable Create functions.

By getting rid of the Prefix field in this way we would be forced to define the second example you cite via a DependentNameType, making it more consistent with other the first example you cite, and would also save a little space in most cases.

I am probably missing something though.  In any case you raise a good point,

- Dave

On Jul 20, 2020, at 5:21 AM, Eduardo Caldas via cfe-dev <[hidden email]> wrote:

template <class T>
void f() {
  // Case 1:
  typename T::template U<int>::type x;
  // 'T::template U<int>' in the NNS is a DependentTemplateSpecializationType.

  // Case 2:
  typename T::U::type y;
  // 'T::U' in the NNS is an Identifier. Why not a DependentNameType?
}


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dependent types representation in the NestedNameSpecifier

Keane, Erich via cfe-dev
On Mon, 20 Jul 2020 at 12:11, David Rector via cfe-dev <[hidden email]> wrote:
Good point.  At best implementing the second NNS as a dependent prefix + Identifier is redundant, since DependentNameType could already store this info, but you’re right that it would be more consistent with the first NNS you cite (the DependentTemplateSpecializationType) to implement the second NNS as a DependentNameType.

It seems like the Prefix field of NestedNameSpecifier is the root cause of this redundancy, and perhaps more general confusion.  I don’t think it is needed.  Perhaps an NNS should only store a simple PointerUnion of the various name kinds.  If we really want to keep the getPrefix() method we can define it as accessing the the properly cast pointer’s getQualifier() method.

I think this is backwards from the intent of the design: the intent is that a NestedNameSpecifier is a singly-linked list of prefixes, each of which adds a single (unqualified) component. Following that design intent, using DependentTemplateSpecializationType here is strange, since it stores redundant qualifier information; all we really want to store for a dependent simple-template-id in a nested-name-specifier is an identifier plus a set of template arguments (and a flag to indicate if 'template' was specified), not even a type. In fact, the use of a type here causes minor problems (and slightly breaks the model) as described in this comment: https://github.com/llvm/llvm-project/blob/master/clang/lib/AST/NestedNameSpecifier.cpp#L306

However, perhaps the current design intent is not the best approach; it might improve the design if we stored the prefix as part of the representation whenever possible, instead of excluding it from the representation whenever possible. That would mean (as you note below) that the representation of namespaces would be different from that of any other NestedNameSpecifier. We would also need to consider how such a change would interact with the NestedNameSpecifierLoc representation -- presumably we'd end up with nested-name-specifier location data embedded in type location data embedded in nested-name-specifier location data recursively. That might be OK; I suspect that means we'd end up coupling NestedNameSpecifierLocBuilder and TypeLocBuilder, which is a little awkward because they're currently entirely independent and even live in different clang libraries right now (but there doesn't seem to be any good reason why TypeLocBuilder is in Sema rather than in AST). Another problem with the alternative design is that it would need a representation for dependent member accesses (eg, `x.A::b` where x is type-dependent): it's not meaningful (outside of nested-name-specifiers) to have a DependentNameType with no qualifier, but that's exactly what we'd need here. Note that we do permit a DependentTemplateSpecializationType to have no qualifier in order to handle the analogous case of `x.template A<T>::b`, and that special case has caused crashes in recent memory because people wrote code making the (reasonable) assumption that a DependentTemplateSpecializationType must always have a qualifier. Relatedly, the Dependent* types in NestedNameSpecifiers would violate uniformity because substitution into them would not proceed in the same way as regular substitution into a type, in part because of the different behavior of qualifiers in class member access (and also because there are different lookup rules for a name on the left-hand side of a ::).

I think either approach is workable. The current design intent has the advantage that it more directly follows the standard and its grammar rules, and so is better prepared for the possibility that nested-name-specifiers might one day diverge from the syntax of type-specifiers, and it uses a different representation for cases with different behaviors. The alternative design has the advantage that the type representation of a type nested-name-specifier models how that type would be written in the same context (including its qualifier).

On balance, if we fix the non-uniformity here, I'd suggest that we stop using DependentTemplateSpecializationType as a possible type representation for a NestedNameSpecifier and instead store only a "template" keyword flag, an identifier, and a list of template arguments.

DependentNameTypes/DependentTemplateSpecializationTypes each store their prefix on their own, so do ElaboratedTypes, so written prefixes for types would be covered, if I’m not mistaken.

The only non-trivial change I think needed would be for handling namespaces, for which we need to pair a written prefix with the NamespaceDecl or NamespaceAliasDecl.  In those cases, I think, we just define a "NamespaceName" class to handle the pairing of the decl and written qualifier, then allocate the NamespaceName as a trailing object of its NestedNameSpecifier in the applicable Create functions.

By getting rid of the Prefix field in this way we would be forced to define the second example you cite via a DependentNameType, making it more consistent with other the first example you cite, and would also save a little space in most cases.

I am probably missing something though.  In any case you raise a good point,

- Dave

On Jul 20, 2020, at 5:21 AM, Eduardo Caldas via cfe-dev <[hidden email]> wrote:

template <class T>
void f() {
  // Case 1:
  typename T::template U<int>::type x;
  // 'T::template U<int>' in the NNS is a DependentTemplateSpecializationType.

  // Case 2:
  typename T::U::type y;
  // 'T::U' in the NNS is an Identifier. Why not a DependentNameType?
}


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dependent types representation in the NestedNameSpecifier

Keane, Erich via cfe-dev
If we just want to align NestedNameSpecifier to its original intent, here’s another solution to consider; still a hassle, but maybe less of one in the long run:
  1. Only allow ElaboratedTypes to have qualifiers.  So, any other types with a getQualifier() method need to instead store that in an ElaboratedType atop them.  (Maybe even separate out a sugared QualifiedType whose only role is to guarantee a non-null qualifier.)
  2. Then, DependentTemplateSpecializationType and DependentNameType can work as a Specifier in an NNS, since they don't contain qualifier info (which would violate the intent of representing each chunk as an unqualified entity).
  3. Icing on the cake: change NNS::getAsType() to NNS::getAsType(bool MaybeQualified = false).  When you pass MaybeQualified=true and the NNS is a type and has a non null prefix, the result returned is an ElaboratedType (or QualifiedType) which is a perfect conversion of the NNS to its Type representation.
If on the other hand we wanted to lose the NNS::Prefix field and define NNS as simply a wrapper over a PointerUnion of possible kinds, we could still handle any special cases (e.g. x.A::B, qualified namespace names etc.) in designated classes (e.g. DependentMemberAccessName, NamespaceName) included in the PointerUnion.

All reasonable solutions.  I don’t know how NNSLoc and NNSLocBuilder would be affected though; those are probably the more important considerations.  

Dave

On Jul 20, 2020, at 3:51 PM, Richard Smith <[hidden email]> wrote:

On Mon, 20 Jul 2020 at 12:11, David Rector via cfe-dev <[hidden email]> wrote:
Good point.  At best implementing the second NNS as a dependent prefix + Identifier is redundant, since DependentNameType could already store this info, but you’re right that it would be more consistent with the first NNS you cite (the DependentTemplateSpecializationType) to implement the second NNS as a DependentNameType.

It seems like the Prefix field of NestedNameSpecifier is the root cause of this redundancy, and perhaps more general confusion.  I don’t think it is needed.  Perhaps an NNS should only store a simple PointerUnion of the various name kinds.  If we really want to keep the getPrefix() method we can define it as accessing the the properly cast pointer’s getQualifier() method.

I think this is backwards from the intent of the design: the intent is that a NestedNameSpecifier is a singly-linked list of prefixes, each of which adds a single (unqualified) component. Following that design intent, using DependentTemplateSpecializationType here is strange, since it stores redundant qualifier information; all we really want to store for a dependent simple-template-id in a nested-name-specifier is an identifier plus a set of template arguments (and a flag to indicate if 'template' was specified), not even a type. In fact, the use of a type here causes minor problems (and slightly breaks the model) as described in this comment: https://github.com/llvm/llvm-project/blob/master/clang/lib/AST/NestedNameSpecifier.cpp#L306

However, perhaps the current design intent is not the best approach; it might improve the design if we stored the prefix as part of the representation whenever possible, instead of excluding it from the representation whenever possible. That would mean (as you note below) that the representation of namespaces would be different from that of any other NestedNameSpecifier. We would also need to consider how such a change would interact with the NestedNameSpecifierLoc representation -- presumably we'd end up with nested-name-specifier location data embedded in type location data embedded in nested-name-specifier location data recursively. That might be OK; I suspect that means we'd end up coupling NestedNameSpecifierLocBuilder and TypeLocBuilder, which is a little awkward because they're currently entirely independent and even live in different clang libraries right now (but there doesn't seem to be any good reason why TypeLocBuilder is in Sema rather than in AST). Another problem with the alternative design is that it would need a representation for dependent member accesses (eg, `x.A::b` where x is type-dependent): it's not meaningful (outside of nested-name-specifiers) to have a DependentNameType with no qualifier, but that's exactly what we'd need here. Note that we do permit a DependentTemplateSpecializationType to have no qualifier in order to handle the analogous case of `x.template A<T>::b`, and that special case has caused crashes in recent memory because people wrote code making the (reasonable) assumption that a DependentTemplateSpecializationType must always have a qualifier. Relatedly, the Dependent* types in NestedNameSpecifiers would violate uniformity because substitution into them would not proceed in the same way as regular substitution into a type, in part because of the different behavior of qualifiers in class member access (and also because there are different lookup rules for a name on the left-hand side of a ::).

I think either approach is workable. The current design intent has the advantage that it more directly follows the standard and its grammar rules, and so is better prepared for the possibility that nested-name-specifiers might one day diverge from the syntax of type-specifiers, and it uses a different representation for cases with different behaviors. The alternative design has the advantage that the type representation of a type nested-name-specifier models how that type would be written in the same context (including its qualifier).

On balance, if we fix the non-uniformity here, I'd suggest that we stop using DependentTemplateSpecializationType as a possible type representation for a NestedNameSpecifier and instead store only a "template" keyword flag, an identifier, and a list of template arguments.

DependentNameTypes/DependentTemplateSpecializationTypes each store their prefix on their own, so do ElaboratedTypes, so written prefixes for types would be covered, if I’m not mistaken.

The only non-trivial change I think needed would be for handling namespaces, for which we need to pair a written prefix with the NamespaceDecl or NamespaceAliasDecl.  In those cases, I think, we just define a "NamespaceName" class to handle the pairing of the decl and written qualifier, then allocate the NamespaceName as a trailing object of its NestedNameSpecifier in the applicable Create functions.

By getting rid of the Prefix field in this way we would be forced to define the second example you cite via a DependentNameType, making it more consistent with other the first example you cite, and would also save a little space in most cases.

I am probably missing something though.  In any case you raise a good point,

- Dave

On Jul 20, 2020, at 5:21 AM, Eduardo Caldas via cfe-dev <[hidden email]> wrote:

template <class T>
void f() {
  // Case 1:
  typename T::template U<int>::type x;
  // 'T::template U<int>' in the NNS is a DependentTemplateSpecializationType.

  // Case 2:
  typename T::U::type y;
  // 'T::U' in the NNS is an Identifier. Why not a DependentNameType?
}


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: Dependent types representation in the NestedNameSpecifier

Keane, Erich via cfe-dev
In reply to this post by Keane, Erich via cfe-dev

Thanks a lot for the answers, they clarified many things :)


In fact, the use of a type here causes minor problems (and slightly breaks the model) as described in this comment: https://github.com/llvm/llvm-project/blob/master/clang/lib/AST/NestedNameSpecifier.cpp#L306

I think I might have another minor problem to add ^^. `getLocalSourceRange` gave an unexpected result for case 2. Applying it iteratively to the `NestedNameSpecifierLoc` “T::template U<int>::”, by means of:

```

for (auto it = NNSLoc; it; it = it.getPrefix()) 

it.getLocalSourceRange();

```

Gives results:

```

T::template U<int>

T

```

Whereas we would expect:

```

template U<int>

T

```

I think this is another example where the “use of a type causes minor problems” and gives unexpected results.



On balance, if we fix the non-uniformity here, I'd suggest that we stop using DependentTemplateSpecializationType as a possible type representation for a NestedNameSpecifier and instead store only a "template" keyword flag, an identifier, and a list of template arguments.

I completely agree with the suggestion.


Indeed, storing a “template” keyword flag, an identifier and a list of template arguments, models exactly what is described in the standard.


nested-name-specifier:

::

type-name ::

namespace-name ::

decltype-specifier ::

nested-name-specifier identifier ::

nested-name-specifier template_opt simple-template-id ::


simple-template-id:

template-name < template-argument-list_opt >


template-name:

identifier



One might argue though that the grammar rule for nested-name-specifiers is written in a somewhat convoluted manner, that mixes syntax and semantics.



On Mon, 20 Jul 2020 at 21:51, Richard Smith <[hidden email]> wrote:
On Mon, 20 Jul 2020 at 12:11, David Rector via cfe-dev <[hidden email]> wrote:
Good point.  At best implementing the second NNS as a dependent prefix + Identifier is redundant, since DependentNameType could already store this info, but you’re right that it would be more consistent with the first NNS you cite (the DependentTemplateSpecializationType) to implement the second NNS as a DependentNameType.

It seems like the Prefix field of NestedNameSpecifier is the root cause of this redundancy, and perhaps more general confusion.  I don’t think it is needed.  Perhaps an NNS should only store a simple PointerUnion of the various name kinds.  If we really want to keep the getPrefix() method we can define it as accessing the the properly cast pointer’s getQualifier() method.

I think this is backwards from the intent of the design: the intent is that a NestedNameSpecifier is a singly-linked list of prefixes, each of which adds a single (unqualified) component. Following that design intent, using DependentTemplateSpecializationType here is strange, since it stores redundant qualifier information; all we really want to store for a dependent simple-template-id in a nested-name-specifier is an identifier plus a set of template arguments (and a flag to indicate if 'template' was specified), not even a type. In fact, the use of a type here causes minor problems (and slightly breaks the model) as described in this comment: https://github.com/llvm/llvm-project/blob/master/clang/lib/AST/NestedNameSpecifier.cpp#L306

However, perhaps the current design intent is not the best approach; it might improve the design if we stored the prefix as part of the representation whenever possible, instead of excluding it from the representation whenever possible. That would mean (as you note below) that the representation of namespaces would be different from that of any other NestedNameSpecifier. We would also need to consider how such a change would interact with the NestedNameSpecifierLoc representation -- presumably we'd end up with nested-name-specifier location data embedded in type location data embedded in nested-name-specifier location data recursively. That might be OK; I suspect that means we'd end up coupling NestedNameSpecifierLocBuilder and TypeLocBuilder, which is a little awkward because they're currently entirely independent and even live in different clang libraries right now (but there doesn't seem to be any good reason why TypeLocBuilder is in Sema rather than in AST). Another problem with the alternative design is that it would need a representation for dependent member accesses (eg, `x.A::b` where x is type-dependent): it's not meaningful (outside of nested-name-specifiers) to have a DependentNameType with no qualifier, but that's exactly what we'd need here. Note that we do permit a DependentTemplateSpecializationType to have no qualifier in order to handle the analogous case of `x.template A<T>::b`, and that special case has caused crashes in recent memory because people wrote code making the (reasonable) assumption that a DependentTemplateSpecializationType must always have a qualifier. Relatedly, the Dependent* types in NestedNameSpecifiers would violate uniformity because substitution into them would not proceed in the same way as regular substitution into a type, in part because of the different behavior of qualifiers in class member access (and also because there are different lookup rules for a name on the left-hand side of a ::).

I think either approach is workable. The current design intent has the advantage that it more directly follows the standard and its grammar rules, and so is better prepared for the possibility that nested-name-specifiers might one day diverge from the syntax of type-specifiers, and it uses a different representation for cases with different behaviors. The alternative design has the advantage that the type representation of a type nested-name-specifier models how that type would be written in the same context (including its qualifier).

On balance, if we fix the non-uniformity here, I'd suggest that we stop using DependentTemplateSpecializationType as a possible type representation for a NestedNameSpecifier and instead store only a "template" keyword flag, an identifier, and a list of template arguments.

DependentNameTypes/DependentTemplateSpecializationTypes each store their prefix on their own, so do ElaboratedTypes, so written prefixes for types would be covered, if I’m not mistaken.

The only non-trivial change I think needed would be for handling namespaces, for which we need to pair a written prefix with the NamespaceDecl or NamespaceAliasDecl.  In those cases, I think, we just define a "NamespaceName" class to handle the pairing of the decl and written qualifier, then allocate the NamespaceName as a trailing object of its NestedNameSpecifier in the applicable Create functions.

By getting rid of the Prefix field in this way we would be forced to define the second example you cite via a DependentNameType, making it more consistent with other the first example you cite, and would also save a little space in most cases.

I am probably missing something though.  In any case you raise a good point,

- Dave

On Jul 20, 2020, at 5:21 AM, Eduardo Caldas via cfe-dev <[hidden email]> wrote:

template <class T>
void f() {
  // Case 1:
  typename T::template U<int>::type x;
  // 'T::template U<int>' in the NNS is a DependentTemplateSpecializationType.

  // Case 2:
  typename T::U::type y;
  // 'T::U' in the NNS is an Identifier. Why not a DependentNameType?
}


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev