It's definitely a challenging feature! That said, there are numerous incremental steps along the way, and they should build on each other without requiring too many big leaps.
I agree with @Joe_Groff's point about having a design mapped out in advance, to some extent: the generics manifesto's description of variadic generics is fairly terse, and is in many ways a direct port of C++ variadic templates into Swift. Abstractly, the key ideas there are probably right: having the notion of "parameter packs" (for generic parameters, function parameters) that capture zero or more parameters with roughly the same shape and having "pack expansions" that replicate a particular pattern (whether it's a type, expression, or similar) for each element in the parameter pack. Syntax can be discussed at length and various features are up for debate (e.g., what to do about multiple parameter packs in a pack expansion, how inference works with parameter packs, etc.), but likely won't have a large effect on the initial stages of implementation.
Here's how I'd start on an implementation.
First, prepare the frontend: there are many places in the frontend where we assume that the only kind of generic parameter is a type parameter. With variadic templates, there will be a new kind of generic parameter: a parameter pack. For example, a GenericParamList contains a sequence of GenericTypeParamDecl * nodes. You'll want to abstract that that GenericParamList contains (e.g.) a GenericParamDecl node that effectively wraps up the GenericParamDecl * and can be extended later with a new case for parameter packs. It's easier to describe what I means in terms of Swift, which can model data structures so much better. It's like going from a GenericParamList containing an Array<GenericTypeParamDecl> to containing an Array<GenericParamDecl>, defined like this:
enum GenericParamDecl {
case typeParameter(GenericTypeParamDecl)
}
C++ enums aren't very expressive, but you can write a C++ class that wraps an enum and handles the data storage. Now, when you do this, you'll have to do some fairly-mechanical updates to a bunch of places in the frontend to make them switch over the different kinds of generic parameters. If we could write Swift, that would mean things like this:
switch genericParam {
case .typeParameter(let typeParam):
// existing code that works on typeParam
}
Of course it'll be uglier because it's C++, but the idea is the same: by doing this everywhere, we set ourselves up for an easier time when we add a new case into GenericParamDecl. When you're doing this, you'll likely want to factor more functionality into the new GenericParamDecl type, so it has an API that should work for different kinds of generic parameters that come along (packs, for variadic templates, but maybe even value parameters in the future).
You'll likely find other places in the AST that need similar treatment, e.g., SubstitutionMap and BoundGenericType will need some way to describe a generic argument (e.g., a GenericArgument that contains just a Type today, but will eventually contain a list of GenericArguments, a pack expansion, etc.). Pick off just one part of the AST at a time, and we can get PRs reviewed and merged---this is infrastructure work that's general goodness and doesn't need to wait for a proposal.
Once the frontend is prepared, it's time to start working on the representation of variadic generics: add the new case for a parameter pack to GenericParamDecl:
case typeParameterPack(GenericTypeParamDecl)
And add an isParameterPack bit and ellipsis location to GenericTypeParamDecl. The parser can set up this state, but the most significant amount of work here will be in updating all of those switch statements. It's okay to stub out ones that can't meaningfully be implemented now with llvm_unreachable("unimplemented variadic generics"), so you'll get a nice compiler crash and can find all of the places later that need updating.
At this point you can write something like:
struct Tuple<Types...> { }
but not do anything with it. Then work on something like:
Tuple<Int, String, Double>
Here, you'll want to extend your GenericArgument to include the array of generic arguments ( Int, String, Double) that are bound to the generic parameter pack Types.
This would be a good point to "lock down" any incorrect uses of parameter packs. For example, if inside the body of Tuple I were to write:
var foo: Types
I should probably get an error that says "parameter pack Types has not been expanded; did you mean to expand it with ...?". You can do that with an AST walk that verifies that every use of a parameter pack is covered by an expansion, and will save you a lot of grief when users (or your tests) try to use a parameter pack in a place that you don't yet support.
Other features will follow: pack expansions in generic argument lists, in where clauses, etc. Each time you'll extend some structure with new cases and deal with those throughout the frontend. We'd want to scope out more of the design along the way, so we know (for example) every place in the language where we will be able to introduce a parameter pack (generic param lists, function/subscript param lists) and write a pack expansion (function calls, subscript argument lists, tuples, etc.), as well as getting a sense of any "add on" features we might want.
There is also some very interesting work on mapping this down to LLVM IR and designing the runtime metadata to support this feature, but I think it's good to tackle that further down the road.
Doug
