rust-lang / rfcs

RFCs for changes to Rust
https://rust-lang.github.io/rfcs/
Apache License 2.0
5.95k stars 1.57k forks source link

Draft RFC: variadic generics #376

Open rust-highfive opened 10 years ago

rust-highfive commented 10 years ago

Issue by eddyb Monday Oct 28, 2013 at 17:39 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/10124

This issue was labelled with: B-RFC in the Rust repository


The Problem

C++11 sets a decent precedent, with its variadic templates, which can be used to define type-safe variadic functions, among other things. I propose a similar syntax, a trailing ..T in generic formal type parameters:

type Tuple<..T> = (..T); // the parens here are the same as the ones around a tuple.
// use => expansion
Tuple<> => ()
Tuple<int> => (int,)
Tuple<A, B, C> => (A, B, C)

The simple example above only uses ..T, but not T itself. The question which arises is this: what is T? C++11 has a special case for variadic parameter packs, but we can do better. We have tuples. We can use them to store the actual variadic generic type parameters:

// Completely equivalent definition:
type Tuple<..T> = T;
// Detailed expansion of (..T) from above:
Tuple<> => (..()) => ()
Tuple<int> => (..(int,)) => (int,)
Tuple<A, B, C> => (..(A, B, C)) => (A, B, C)

The Solution: Part Two

Now that we know the answer is "tuples", everything else is about extending them. The prefix .. operator would expand a tuple type:

// in another tuple type:
type AppendTuple<T, U> = (..T, U);
type PrependTuple<T, U> = (U, ..T);
AppendTuple<PrependTuple<Tuple<B>, A>, C> => (A, B, C)
// in a fn type's parameter list:
type VoidFn<..Args> = fn(..Args);
VoidFn<A, B, C> => fn(A, B, C);
// in a variadic generic parameter list:
Tuple<..(A, B, C), ..(D, E, F)> => (A, B, C, D, E, F)

Then we can do the same thing with values:

// in another tuple:
(..(true, false), ..(1, "foo"), "bar") => (true, false, 1, "foo", "bar")
// in a function call:
f(..(a, b), ..(c, d, e), f) => f(a, b, c, d, e, f)

There's only one piece missing: we're still not able to define a function which takes a variable number of arguments. For this, I propose ..x: T (where T is a tuple type) in a pattern, which can be used to "capture" multiple arguments when used in fn formal arguments:

// Destructure a tuple.
let (head, ..tail) = foo;
// This function has the type fn(int, A, B, C), and can be called as such:
fn bar(_: int, ..x: (A, B, C)) -> R {...}

A type bound for ..T (i.e. impl<..T: Trait>) could mean that the tuple T has to satisfy the bound (or each type in T, but that's generally less useful).

Examples:

// The highly anticipated Fn trait.
trait Fn<Ret, ..Args> {
    fn call(self, .._: Args) -> Ret;
}
impl Fn<Ret, ..Args> for fn(..Args) -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}
impl Fn<Ret, ..Args> for |..Args| -> Ret {
    fn call(self, ..args: Args) -> Ret {
        self(..args)
    }
}

// Cloning tuples (all cons-list-like algorithms can be implemented this way).
impl<Head, ..Tail: Clone> Clone for (Head, ..Tail) {
    fn clone(&self @ &(ref head, ..ref tail)) -> (Head, ..Tail) {
        (head.clone(), ..tail.clone())
    }
}
impl Clone for () {
    fn clone(&self) -> () {
        ()
    }
}

// Restricting all types in a variadic tuple to one type.
trait ArrayLikeTuple<T> {
    fn len() -> uint;
}
impl<T> ArrayLikeTuple<T> for () {
    fn len() -> uint {0}
}
impl<T, ..Tail: ArrayLikeTuple<T>> ArrayLikeTuple<T> for (T, ..Tail) {
    fn len() -> uint {
        1 + Tail::len()
    }
}

// And using that trait to write variadic container constructors.
impl<T> Vec<T> {
    fn new<..Args: ArrayLikeTuple<T>>(..args: Args) -> Vec<T> {
        let v: Vec<T> = Vec::with_capacity(Args::len());
        // Use an unsafe move_iter-like pattern to move all the args
        // directly into the newly allocated vector. 
        // Alternatively, implement &move [T] and move_iter on that.
    }
}

// Zipping tuples, using a `Tuple` kind and associated items.
trait TupleZip<Other>: Tuple {
    type Result: Tuple;
    fn zip(self, other: Other) -> Result;
}
impl TupleZip<()> for () {
    type Result = ();
    fn zip(self, _: ()) -> () {}
}
impl<A, ATail: TupleZip<BTail>, B, BTail: Tuple> TupleZip<(B, ..BTail)> for (A, ..ATail) {
    type Result = ((A, B), ..ATail::Result);
    fn zip(self @ (a, ..a_tail), (b, ..b_tail): (B, ..BTail)) -> Result {
        ((a, b), ..a_tail.zip(b_tail))
    }
}

Todo

qraynaud commented 6 years ago

I was planning to transcribe some C++ code I have in Rust. It is some playground project of mine that is somehow like yacc. It currently can generate correct parsing tables and parsers for any LALR(1) grammar for C++ and Javascript.

Somehow, I wanted to move the grammar analysis codebase to Rust and also the reference parser implementation. My concern is I'd like to be able to define my parsers like I did in C++ / JS: for each pattern in each rule in the grammar, you have to provide a method to construct the value it produces consuming the subrules / tokens values. I had an interface like this:

template </* … */>
class parser: base_parser</* … */> {
  void register_rules() {
    this->register_code("rule_name", 0, *this, /* pattern index in the rule */, &parser::rule_name_0);
  }

  float rule_name_0(int i, float f) {
    return i + f;
  }
}

The form with 4 args is providing a method, the 3rd being the object on which the method should be invoked on while with 3 args, you could pass on any function instead. What is important to me is that register_code is able to accept any function / method whatever the arguments if the arguments are all comprised in the types included in a variant type the parser is templated with and if they have less than 50 arguments (the limitation is caused by the fact that I used macros to implement this because when I wrote this code, c++11 was not really around). If you want to take a look at what I did, the code is here: https://bitbucket.org/qraynaud/jungle/src/default/src/libs/jungle/caller.hpp.

I have in the internal parser code a class that can invoke any of those methods using a provided array of values of the variant type I talked of before. Since everything relies on proper templating, the type checking is ensured at compilation for the most part. The variant still has to check it has the correct type value in it at execution time but it will fail properly if not.

I find this important because it makes the rules codebase easy to understand. You put an argument for every token / subrule your pattern contains (eg rule: expr "+" expr + "int" would result in a signature like (left: f64, plus: (), right: f64, i: u32)). I could give to the method the array of arguments directly (like an array of enums) but it feels wrong to me.

Since the basic parser code is not generated, I have the feeling that it is impossible to achieve anything even remotely like this in Rust as of today. It would be great if this spec could take into account those kind of usages to make them possible.

tinyplasticgreyknight commented 6 years ago

@qraynaud I'm not sure if I understand what you're looking for exactly, but would it be a useful workaround if your function always accepts only a single argument, which might be a tuple containing the "real" arguments?

Maybe I should read your original repository and get a feel for how this is all used :-)

qraynaud commented 6 years ago

@tinyplasticgreyknight : even so, every function would have a different tuple type and that would not work either for me right?

Each method for each parser rule's pattern has a different signature. I think that was not clear enough. What I implemented in C++ is similar to the apply method in JS (obj.method.apply(obj, [arg1, arg2, …])).

I don't really see how I can build the correct tuple, its signature being something like (..T) with each T being one type between a list of known types. With this idea I got my problem moved. Before it was calling a method using a vector of arguments, now it is constructing a tuple with a vector of arguments. Not knowing beforehand the types & the numbers of arguments…

takkuumi commented 6 years ago

Will it implement in 2018?

Centril commented 6 years ago

@NateLing up for writing a formal RFC proposal about it? ;)

takkuumi commented 5 years ago

@Centril yeap

Systemcluster commented 4 years ago

For reference, since this seems to be the most prominent issue when looking for "variadic generics":

Since there is no dedicated tag for it, is there any place where the general progress of this topic can be followed?

hirrolot commented 4 years ago

Why not just use induction on heterogeneous lists? See: https://docs.rs/frunk/0.3.1/frunk/hlist/index.html

ChayimFriedman2 commented 4 years ago

I just want to say here that now TypeScript 4.0 implemented the same thing in the same shape (more or less). See: https://www.typescriptlang.org/docs/handbook/release-notes/typescript-4-0.html#variadic-tuple-types

Kixiron commented 3 years ago

This is a draft RFC, so I can pretty confidently say no

burdges commented 3 years ago

If you want optional arguments soon then implement them on nightly using procmacros

fn foo(..mandatory_args..) -> Foo { Foo { ..mandatory_args.. } }
pub struct Foo { ..mandatory_args.. }
impl FnOnce<()> for Foo { .. }
impl FnOnce<OptArg1> for Foo { .. }
impl FnOnce<OptArg2> for Foo { .. }
impl FnOnce<OptArg3> for Foo { .. }
impl FnOnce<OptArg4> for Foo { .. }

and invoke like foo(mandatory_args)(optarg3)

It'd even support different return types for different optional argument types.

Randl commented 3 years ago

Is anyone working on turning it into full RFC? cc @eddyb @canndrew @Centril @NateLing

eddyb commented 3 years ago

There's been several attempts over the years and it doesn't seem like it's going to happen again any time soon, sorry.

I have a branch somewhere with some of the implementation details (that can be used internally by rustc even without a proper VG feature, in order to clean up the extern "rust-call" mess), but even that I don't know when I'll get back to.

86maid commented 9 months ago

Is there anyone else?

jasal82 commented 6 months ago

I don't think this will be implemented in 2018. It would still be pretty useful.

kirawi commented 2 months ago

Related: https://poignardazur.github.io/2024/05/25/report-on-rustnl-variadics/

burdges commented 2 months ago

I'd expect some builder patters plus https://github.com/rust-lang/rfcs/pull/3681 would be preferable for many if not most variadics use cases, ala MyFn { whatever args, .. }.go()

I suppose Iterator<Item = &dyn MyTrait> fits many of the remaining use cases, but if we'd some generic closure then maybe the compiler could derive a tuple trait from the base trait:

#[derive_tuple(MyTraitTuple)]
pub trait MyTrait { .. }

defines

trait MyTraitTuple {
    type Head: MyTrait;
    type Tail: MyTraitTuple;
    .. map fns using generic closures .. 
}