Allowing extensions of bound generic types


(Jacob Bandes-Storch) #1

I'm looking into allowing extensions like "extension Array where Element ==
Int" — relaxing the restriction that prevents generic function/type
definitions from having concrete types specified. (Slava mentioned that
this is a favorable language change without need for the evolution process:
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151207/000865.html
)

I'd like to run my thoughts by some people who know what they're talking
about, before diving in too far :slight_smile:

The diagnostic in question is
    diag::requires_generic_param_made_equal_to_concrete
    "same-type requirement makes generic parameter %0 non-generic"
which is emitted from ArchetypeBuilder::addSameTypeRequirementToConcrete().

Multiple code paths reach checkGenericParamList() which adds the
requirements:

    - DeclChecker::visitClassDecl
       -> TC::validateDecl case for struct/class/enum
       -> TC::validateGenericTypeSignature
       -> TC::validateGenericSignature
       -> TC::checkGenericParamList

    - DeclChecker::visitFuncDecl
       -> TC::validateGenericFuncSignature
       -> TC::checkGenericFuncSignature
       -> TC::checkGenericParamList

    - DeclChecker::visitExtensionDecl
       -> TC::validateExtension
       -> TC::checkExtensionGenericParams
       -> TC::validateGenericSignature
       -> TC::checkGenericParamList
(Mildly confusing to have both "validate" and "check" variants, but only in
some of the cases...?)

It's only in the 3rd case (extensions) that we want to allow the
requirements to make the types fully bound/concrete. So here's what I
propose doing:

  1. The ArchetypeBuilder needs to know whether this is allowed. So add a
boolean field, called e.g. AllowConcreteRequirements.

  2a. Pass false to the ArchetypeBuilder created in
validateGenericFuncSignature.
  2b. Pass the boolean through as a param to validateGenericSignature,
where the ArchetypeBuilder is created. (validateGenericSignature is used in
both class & extension cases). In particular, pass true from
checkExtensionGenericParams and false from validateGenericTypeSignature.

  3. Skip the error if AllowConcreteRequirements was true. Instead allow
the requirement to be added (and fix any fallout issues from this change,
add tests, yadda yadda).

How does that sound?

Also, is there any desire to remove this restriction?
    diag::extension_specialization
    "constrained extension must be declared on the unspecialized generic
type %0 with constraints specified by a 'where' clause"
It seems natural to want to allow "extension Array<Int>", but I'm afraid it
may complicate things significantly, especially if we only wanted to allow
this syntax in the case of .

Jacob Bandes-Storch


(Jacob Bandes-Storch) #2

Email is hard...last sentence should say "in the case of extensions".
Jacob


(Douglas Gregor) #3

Hi Jacob

Apologies for the delay in answering…

I'm looking into allowing extensions like "extension Array where Element == Int" — relaxing the restriction that prevents generic function/type definitions from having concrete types specified. (Slava mentioned that this is a favorable language change without need for the evolution process: https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151207/000865.html)

I'd like to run my thoughts by some people who know what they're talking about, before diving in too far :slight_smile:

The diagnostic in question is
    diag::requires_generic_param_made_equal_to_concrete
    "same-type requirement makes generic parameter %0 non-generic"
which is emitted from ArchetypeBuilder::addSameTypeRequirementToConcrete().

Multiple code paths reach checkGenericParamList() which adds the requirements:

    - DeclChecker::visitClassDecl
       -> TC::validateDecl case for struct/class/enum
       -> TC::validateGenericTypeSignature
       -> TC::validateGenericSignature
       -> TC::checkGenericParamList

    - DeclChecker::visitFuncDecl
       -> TC::validateGenericFuncSignature
       -> TC::checkGenericFuncSignature
       -> TC::checkGenericParamList

    - DeclChecker::visitExtensionDecl
       -> TC::validateExtension
       -> TC::checkExtensionGenericParams
       -> TC::validateGenericSignature
       -> TC::checkGenericParamList

There’s a path through TypeChecker::handleSILGenericParams() that you need to consider, which is triggered when parsing SIL. It’s an odd case because you get all of the generic parameter lists up front. I suspect you would just always allow type parameters to be equated with concrete types from here.

(Mildly confusing to have both "validate" and "check" variants, but only in some of the cases…?)

Having the “check” in the middle/bottom is the exceptional part here. The rough intent at one point was that “validate” was basic validation of a declaration so that it could be useful from elsewhere, while “check” checks all of the semantic constraints to see if the declaration was well-formed. But, it wasn’t followed that carefully, and this turns out to be a not-terribly-useful distinction. Rather, we should be handling more fine-grained type checking requests iteratively, per

  https://github.com/apple/swift/blob/master/docs/proposals/DeclarationTypeChecker.rst

But that’s off on the horizon. Back to your actual question…

It's only in the 3rd case (extensions) that we want to allow the requirements to make the types fully bound/concrete.

Okay, so this means that your example would be accepted, but something like:

  class X<T where T == Int> {
  }

would remain ill-formed, as would

  class X<T> {
    func f<U where T == Int>() { … }
  }

So here's what I propose doing:

  1. The ArchetypeBuilder needs to know whether this is allowed. So add a boolean field, called e.g. AllowConcreteRequirements.

  2a. Pass false to the ArchetypeBuilder created in validateGenericFuncSignature.
  2b. Pass the boolean through as a param to validateGenericSignature, where the ArchetypeBuilder is created. (validateGenericSignature is used in both class & extension cases). In particular, pass true from checkExtensionGenericParams and false from validateGenericTypeSignature.

  3. Skip the error if AllowConcreteRequirements was true. Instead allow the requirement to be added (and fix any fallout issues from this change, add tests, yadda yadda).

How does that sound?

You may need to make the AllowConcreteRequirements flag indicate the depth at which generic parameters are allowed to be made equivalent to concrete types. Consider, for example:

  class X<T> { }

  extension X<T> {
    func f<U where T == Int>() { }
  }

Presumably that should be ill-formed still, and that one would properly have to write

  extension X where T == Int {
    func f() { }
  }

(which is much clearer anyway, of course!).

And although it’s broken today for other reasons, the depth of the generic parameters that are allowed to be made equivalent to concrete types could be > 0 if you had a generic type nested within a generic type, e.g.,

  class X<T> {
    class Y<U> {
    }
  }

  extension X.Y where T == Int, U == String { … } // okay; both depths 0 and 1 are okay to bind to concrete types

Also, is there any desire to remove this restriction?
    diag::extension_specialization
    "constrained extension must be declared on the unspecialized generic type %0 with constraints specified by a 'where' clause"
It seems natural to want to allow "extension Array<Int>", but I'm afraid it may complicate things significantly, especially if we only wanted to allow this syntax in the case of .

I’d want this bit of syntax to go through swift-evolution, even though I suspect it would be very well-received. There’s a syntactic symmetry question it invokes, because

  struct X<T> { … }

introduces T as a type parameter while

  extension X<T> { … }

looks up T in the enclosing scope. That potentially becomes somewhat ambiguous if we want to be able to introduce new type parameters in a specific extension, which comes up if we implement something akin to C++’s partial specialization. For example, extending an array of optional values:

  extension X<T?> { } // no, looks up T in the enclosing scope

There are syntactic ways around this. For example, putting the type parameters after “extension”:

  extension<T> Array<T?> { }

or even spell it with the syntactic sugar:

  extension<T> [T?] {
    func nonnilValues() -> [T] {
    }
  }

to open the flood gates yet further.

I don’t see any rush to push the syntax through swift-evolution: you can work on the implementation using the “Element == Int” syntax (which should work regardless of whether there’s a more concise way to spell the same intent) and discuss/add the syntactic sugar later.

  - Doug

···

On Dec 9, 2015, at 2:00 AM, Jacob Bandes-Storch via swift-dev <swift-dev@swift.org> wrote:


(Jacob Bandes-Storch) #4

Hi Doug, thanks for the response!

There’s a path through TypeChecker::handleSILGenericParams() that you need

to consider, which is triggered when parsing SIL. It’s an odd case because
you get all of the generic parameter lists up front. I suspect you would
just always allow type parameters to be equated with concrete types from
here.

Yeah, sounds reasonable.

You may need to make the AllowConcreteRequirements flag indicate the depth

at which generic parameters are allowed to be made equivalent to concrete
types.

I guess that makes sense to me, although I'm not convinced it's actually
going to be necessary. I'm going to try to get an initial version working
first, then consider using depth instead of just a bool.

The problem I'm running into now is that the PotentialArchetype's
getType(ArchetypeBuilder&) is returning the concrete type it was
constrained to, so castToArchetype fails (inside getAllArchetypes, during
finalizeGenericParamList). I tried simply skipping these archetypes, but a
lot of stuff downstream seems to depend on the number of archetypes
matching the number of generic params (such as
ConsraintSystem::openGeneric, BoundGenericType, etc.). Do you think I
should be modifying ArchetypeBuilder::PotentialArchetype::getType() to
return a valid archetype in this case, and just let the constraint solver
deal with the same-type requirement later on?

Thanks,
Jacob