[swift-evolution] ValueEnumerable protocol with derived implementation for enums

[Brent Royal-Gordon]

>     • The "allValues" behavior should be provided by conformance to some protocol, named ValueEnumerable or ValuesEnumerable or similar.
>     • The compiler should derive an allValues implementation for "simple" enums (those without associated values).

Agreed on my part.

(I favor "Values" because "Value" in the singular implies to me that you can take a single value and enumerate it somehow, which is not what I have in mind.)

> If allValues were exposed as part of the protocol, then the generic constraint <T: ValueEnumerable> could be used meaningfully, i.e. you could write/use "T.allValues".
> 
> On the other hand, the limitations of the current generics system don't allow "associatedtype ValueCollection: Collection where ValueCollection.Iterator.Element == Self". Doug's Completing Generics manifesto included "Arbitrary requirements in protocols", under the category of "Minor extensions", which would remove this limitation. If this gets implemented, I think it makes a lot of sense to use it here.

Yes. I see some metaprogramming potential in being able to pass just a type and enumerate its values. For instance, you could say how far "through" a type that particular value lies, using nothing but an instance of it.

> Until then, though, we'd have to pick a concrete type for the collection. Brent proposed that it be an Array, "static var allValues: [Self]".
> 
> The biggest reason I didn't expose allValues on the protocol was that I figured we'd want to allow for efficient implementations which wouldn't require allocating storage for *all* the values (just the endpoints, for instance), but could still count and iterate over them.

If the Array limitation is truly going to be temporary, I don't think the need for storage is a serious long-term problem. Especially before we start getting fancy and supporting `ValueEnumerable` associated values, each `allValues` array is going to be small.

(However, see below for another path forward which would allow a much smaller instance.)

> Another question on the subject of exposing the property as a protocol requirement: What should the diagnostics look like if it's missing? Maybe something like this:
> 
>     struct MyType: ValueEnumerable { }
>     // error: type 'MyType' does not conform to protocol 'ValueEnumerable'
>     // note: protocol requires property 'allValues' with type '[MyType]'
>     // note: implementation of allValues cannot be automatically derived for a non-enum type

If Swift cannot automatically derive an implementation for a particular type, I think having a diagnostic stating that, and preferably saying why, would be a great idea.

> ### Should allValues implementations be derived for Comparable enums? What if the sorted order does/doesn't match the source order?
> 
> Brent has suggested the semantics of allValues should be such that for Comparable types, allValues is guaranteed to be ordered. If that were the case, we might not want to require the compiler to derive a ValueEnumerable implementation, since the source order may not match the Comparable-sorted order, and verifying this could overly complicate things. (I think I'm in agreement here: having the values be ordered is a good implementation of the principle of least surprise.)

With the impending introduction of a `Comparable` requirement on collection indices, we now have a second good reason for this: the values themselves are good candidates to index into the `allValues` collection, and they will need to be `Comparable`.

Incidentally, one open question is whether enums with raw values should be compared in source order or in raw value order. In other words, in:

	enum Foo: ValuesEnumerable {
		case bar = 2
		case baz = 1
	}

Is `Foo.allValues` equivalent to `[bar, baz]` or `[baz, bar]`? I'm not certain we can always reliably sort raw values at compile time; `String` is particularly worrisome because sort order tends to depend on tables built into the OS, but even integer literals are suspect when you consider that this feature can be used to initialize *any* `IntegerLiteralConvertible` type (or `StringLiteralConvertible`, or I believe `FloatLiteralConvertible` as well). Analyzing a raw value's sort order eventually becomes equivalent to analyzing a custom Comparable implementation.

* * *

However, the new Collection proposal (SE-0065, https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md) has actually given me an interesting idea about how to build this feature out of smaller pieces.

Suppose we introduce a `ValuesCountable` (or maybe just `Countable`) protocol like this:

	protocol ValuesCountable: Strideable /* implies Comparable and Equatable */ {
		associatedtype Stride: SignedInteger
		static var allValues: CountableClosedRange<Self> { get }
	}

Swift already synthesizes Equatable. We could additionally have it synthesize:

	• A `<` which compares the bit pattern (or perhaps the raw values?) to determine ordering.
	• A `distance(to:)` and `advanced(by:)` which operate with knowledge of the known-good values.
	• An `allValues` which basically amounts to just `return <first case>...<last case>`.

Small-scale reasons to like this approach:

	• It builds up the feature from individually tractable pieces.
	• `allValues` is only the size of the two endpoint elements, which strikes me as close to optimal. For small enums, that might only be a couple bytes.
	• `allValues` uses an already-written part of the standard library, so we don't have to write (or worse, synthesize) an entire collection implementation to get an efficient representation.

Implementation reasons to like this approach:

	• Derived `Comparable` is a highly desired feature in its own right. Derived `Strideable` is not as highly desired, but seems like it could be useful in some cases. Even if we don't finish `ValuesCountable` before Swift 3, those will still be on that WWDC slide with the Swift logo and forty little feature names.
	• We can start with really simple, really awful implementations of these derivations (for instance, `Comparable` and `Strideable` which are backed by a linearly-searched array) and improve them over time. Because they are hidden behind an API, we can continue to refine them even after Swift 3 is released.

Language design reasons to like it:

	• There is very little to this feature; it is mostly built out of other features with other uses.
	• It lends itself to being split up into several separate proposals, which is usually a favored approach.
	• `ValuesCountable` may be a good protocol for representing the bounds of other `SignedInteger`-`Strideable` types, like `Integer`. That would mean that *every* part of this (well, except the `allValues` synthesis) would have another purpose in Swift.

Future expansion reasons to like it:

	• Associated value support is *relatively* straightforward to implement; you just need more complicated `distance(to:)` and `advanced(by:)` implementations.
	• If we eventually gain `where` clauses on associated values, we can then choose to give `ValuesCountable` a `ValuesEnumerable` super-protocol with a broader type, like `Collection where Iterator.Element == Self`. This would allow us to represent, for instance, non-`Comparable` types without imposing an order on them (or at least, one that's only visible on an opaque index type).
	• If `ValuesCountable` becomes the way `Integer` expresses the range of its type, we could add a `ValuesBounded` super-protocol with a plain old `ClosedRange` for continuous types like `FloatingPoint`. (And `FloatingPoint`'s `ValuesBounded` can be `-Inf...Inf`, since `nan`s never compare equal to anything anyway.)

To be evenhanded, here are some reasons to dislike it:

	• It is pretty complex, arguably even overengineered. Some people may not like the design because of this.
	• It lends itself to being split up into several separate proposals, which is more complex to manage; it is also possible that some proposals will pass but not others.
	• `ValuesCountable` is probably not the API you would design for `Integer` if you had a completely free hand. (That would probably be something simpler, like `min` and `max` static members.)
	• It requires you to make your type `Comparable` and `Strideable`, even if these behaviors don't make much sense for your type other than for `allValues`. That limitation will stay until associated types become more expressive.
	• Since `CountableClosedRange` cannot represent an empty range, you would not be able to conform a caseless enum to `ValuesCountable`, even with a custom implementation. (Caseless enums do have a couple of bizarre uses.)
	• We might have to bikeshed everything again.

(And here's one esoteric alternative which is maddeningly out of reach:

	• If `Foo.Type` could be conformed to `CountableClosedRangeProtocol` (or at least to a subprotocol of `Collection` which filled in the necessary implementation), you could give it `lowerBound` and `upperBound` members and then do all this without an actual `allValues` property. Instead, the type *itself* would fill the role of the range; you would say (for instance) `for value in MyEnum { ... }` and it would loop through the values of `MyEnum`.

However, that would require conforming the metatype to a protocol, which is not something Swift lets you do; it's such an odd feature that I don't think I've even seen it *suggested* before. It would also populate the static namespace with all sorts of oddities from `Collection` and `Sequence`. Some (like `count`) might actually be useful in and of themselves; others (like `map`) are a little odd, but on balance sensible; a few (like `contains(_:)`, which would always be `true`) are kind of useless; and some (like the `subscript`s) are currently not allowed as static members in Swift. Not to mention the weirdness of having associated types on the metatype, and the "turtles all the way down" nature of the whole thing…)

-- 
Brent Royal-Gordon
Architechies