Auto-generated sum types

[Ekleog]

First, the idea was lain down by @glaebhoerl here.

The idea is basically to have a way to tell the compiler “please auto-generate me a sum trait for my -> impl Trait” function, that would automatically derive Trait based on the implementations of the individual members.

There would, I think, be a need for a syntax specially dedicated to this, so that people are not auto-generating these without being aware of it. Currently, the two syntaxes I can think of are either |value| (without a following {}), running on the idea of “this is auto-generated, just like closures” (I don't like it much, but it could make sense), and the other idea is to make it use a keyword. I'd have gone with auto, but it appears to not be reserved, and become or enum would likely be the best choices.

(Edit: @Pauan pointed out that the |…| syntax would be ambiguous in certain cases, so please disregard it)

So the syntax would, I think, look like this:

fn foo(x: bool) -> impl Iterator<Item = u8> {
    if x { return become b"foo".iter().cloned() }
    become b"hello".iter().map(|c| c + 1)
}
// Or:
fn foo(x: bool) -> impl Iterator<Item = u8> {
    if x { return enum b"foo".iter().cloned() }
    enum b"hello".iter().map(|c| c + 1)
}
// Or:
fn foo(x: bool) -> impl Iterator<Item = u8> {
    if x { return |b"foo".iter().cloned()| }
    |b"hello".iter().map(|c| c + 1)|
}

The major advantage of the || syntax is that it doesn't raise the issue of parenthesizing, as it's already made of parenthesis.

What do you think about this idea, especially now that impl Trait is landing and the need is getting stronger?

[alexreg]

Thanks for creating a separate issue for this.

To be honest, I'm not sure we need explicit syntax for this. It's more of an (important) implementation detail than a user-facing feature, no? But if one does want to make the syntax explicit, then I suggest putting something like impl enum Trait in the function signature.

[Nemo157]

To be honest, I'm not sure we need explicit syntax for this. It's more of an (important) implementation detail than a user-facing feature, no? But if one does want to make the syntax explicit, then I suggest putting something like impl enum Trait in the function signature.

@alexreg one reason to make it explicit is it does have performance implications, each time you call a method there will have to be a branch to call into the current type (hmm, unless these were implemented as some form of stack-box with a vtable instead, either way that still changes the performance). My first thought was also to make it a modifier on the impl Trait syntax to avoid having to repeat it on each return (impl sum Trait for the insiders pun of the some Trait proposed keyword instead of impl). But, as you mention this is an implementation detail, so that should not be exposed in the signature (could just have rustdoc hide it I suppose).

[Pauan]

I might be wrong, but wouldn't the |...| cause parsing ambiguities, since it's already used for closures?

[Ekleog]

@Pauan Oh indeed, I was thinking EXPR { } was not valid syntax, but that's not the case in eg. if. Then, in if the |...| syntax should not be allowed anyway in if conditions, but that'd complicate for no reason the parser.

@Nemo157, @alexreg The issue with putting this as a modifier in the type signature is the fact it wouldn't work well inside a function:

fn bar() -> Option<LinkedList<char>> { /* ... */ }
// This is allowed
fn foo() -> impl enum Iterator<Item = char> {
    match bar() {
        Some(x) => x.iter(),
        None => "".iter(),
    }
}
// Either this is not allowed, or the loss in performance is not explicit
fn foo() -> impl enum Iterator<Item = char> {
    let mut tmp = match bar() {
        Some(x) => x.iter(),
        None => "".iter(),
    };
    let n = tmp.next();
    match n {
        Some(_) => tmp,
        None => "foo bar".iter(),
    }
}

[est31]

Haven't you just invented dynamic dispatch??

[alexreg]

Yeah, fair point about the performance hit. It’s a small one, but it wouldn’t be in the spirit of Rust to hide it from the user syntactically.

[Nemo157]

@Ekleog you can use the exact same syntax for inside a function, somewhere you need to mention the trait that you're generating a sum type for anyway:

fn foo() -> impl enum Iterator<Item = char> {
    let mut tmp: impl enum Iterator<Item = char> = match bar() {
        Some(x) => x.iter(),
        None => "".iter(),
    };
    let n = tmp.next();
    match n {
        Some(_) => tmp,
        None => "foo bar".iter(),
    }
}

@est31 a constrained form of dynamic dispatch that could potentially get statically optimized if the compiler can prove only one or the other case is hit. Or, as I briefly mentioned above it could be possible for this to be done via a union for storage + a vtable for implementation, giving the benefits of dynamic dispatch without having to use the heap. (Although, if you have wildly different sizes for the different variants then you pay the cost in always using the size of the largest.)

One thing that I think might be important is to benchmark this versus just boxing and potentially have a lint recommending switching to a box if you have a large number of variants (I'm almost certain that a 200 variant switch would be a lot slower than dynamically dispatching to one of 200 implementors of a trait, but I couldn't begin to guess at what point the two crossover in call overhead, and there's the overhead of allocating the box in the first place).

[Ekleog]

@Nemo157 Thanks for explaining things better than I could!

I'd just have a small remark about your statement: I don't think a 200-variant switch would be a lot slower than dynamic dispatch: the switch should be codegen'd as a jump table, which would give something like (last time I wrote assembler is getting a bit long ago so I'm not sure about the exact syntax) mov rax, 0xBASE_JUMP_TABLE(ENUM_DISCRIMINANT,3); jmp rax, while the dynamic dispatch would look like mov rax, METHOD_INDEX(VTABLE); jmp rax. As BASE_JUMP_TABLE and METHOD_INDEX are constants, they're hardcoded in the assembly, and so both cases end up being 1/ a memory load (either in JUMP_TABLE or VTABLE, so there could be cache impact here depending on whether you always call different methods on the same object or whether you always call the same method on different objects), and 2/ a jump (with a dependency between these instructions).

So the mere number of implementors shouldn't matter much in evaluating the performance of this dispatch vs. a box. The way of using them does have an impact, but this will likely be hard to evaluate from the compiler's perspective.

However, what may raise an issue about performance is nesting of such sum types: if you have a sum type of a sum type of etc., then you're going to lose quite a bit of time going through all these jump tables. But the compiler may detect that one member of the sum type is another sum type and just flatten the result, so I guess that's more a matter of implementation than specifiction? :)

[est31]

a constrained form of dynamic dispatch that could potentially get statically optimized if the compiler can prove only one or the other case is hit.

LLVM is capable of doing devirtualisation.

as I briefly mentioned above it could be possible for this to be done via a union for storage + a vtable for implementation, giving the benefits of dynamic dispatch without having to use the heap

That's a point admittedly. Dynamically sized stack objects are a possibility but they have certain performance disadvantages.

[burdges]

Is there anything wrong with the bike shed color -> enum Trait? There are still folk who want impl Trait to be replaced by some Trait and any Trait so maybe just enum Trait catches the "make this for me" better.

I think procedural macros could generate this right now. If coersions develop further then maybe doing so would becomes quite simple even. Right now, there are Either types that do this for specific types like Iterator and Future. I'm unsure why they do not even implement From.

[Ekleog]

So if we are going to start painting the bike shed (there seems to be little opposition right now, even though it has only been like a day since initial posting), I think there is a first question to answer:

Should the indication of the fact the return is an anonymous sum type lie in the return type or at the return sites?

i.e.

fn foo(x: T) -> MARKER Trait {
    match x {
        Bar => bar(),
        Baz => baz(),
        Quux => quux(),
    }
}
// vs.
fn foo(x: T) -> impl Trait {
    match x {
        Bar => MARKER bar(),
        Baz => MARKER baz(),
        Quux => MARKER quux(),
    }
}

Once this question will have been answered, we'll be able to think about the specifics of what MARKER should be.

[Ekleog]

So, now, my opinion: I think the fact the return is an anonymous sum type should lie at the return site, for two reasons:

• mostly because the caller has no need of knowing that the return type is an anonymous sum type, only that it's some type that implements Trait
• but also because it will have a nicer syntax when used inside a function with something that is not actually a return, but eg. let x = match or similar (depending on how effective type inference of the result will be, I think taking the intersection of the traits matched by all the return branches should do it, but…)

On the other hand, the only argument I could think of in favor of putting the marker in the return type is that it makes for less boilerplate, but I'm not really convinced, so I'm maybe not pushing forward the best arguments.

[alexreg]

@Ekleog Yeah, I'm with you on return site actually, even though I proposed the return type syntax above. As you say, it reflects the fact that it's more of an implementation detail that consumers of the function don't need to (shouldn't) care about. Also, I think the analogy to box syntax is a good one, and it would be used in a similar way superficially.

[Nemo157]

I think procedural macros could generate this right now.

For a closed set of traits, sure, but to allow this to be used for any trait requires compiler support for getting the methods of the traits. Delegation plus some of its extensions might enable this to be fully implemented as a procedural macro.

I'm tempted to try and write a library or procedural macro version of this, I am currently manually doing this for io::{Read, Write} so even if it only supports those traits it would be useful for me. If it works that could be a good way to get some experience with using it in real code to inform the RFC.

[Ixrec]

Various forms of enum impl Trait sugar for autogenerated anonymous enums have been discussed a few times in the past. For some reason I can't find a centralized discussion of them now, but I think the points that came up before but haven't been fully raised yet are:

• The original motivation in past discussions was to make it possible to introduce a new error type to a function without it "virally infecting"/requiring code changes up the entire call stack. I still believe that's a far more compelling benefit than anything to do with performance (after all, this is just sugar over defining your own enum).
• It's probably better to put the marker for this feature on the signature, i.e. fn foo(x: T) -> MARKER Trait
  • As far as I know, the only options here are one marker in the signature, and one marker at every return point. A marker for every return point is just too noisy (especially when the return point is just a ?), and seems to go against the motivation of making it trivial to introduce a new error type.
  • The main argument against having it in the signature is that it shouldn't and doesn't affect the function's API/contract, so it's not something clients should know about. While a good rule of thumb, it's been pointed out in the past that this is already not an ironclad rule (I believe mut on arguments was the counterexample that's stable today), so rustdoc having to hide the marker isn't a new layer of complexity.
• The syntax probably should include impl Trait because "returning an impl Trait" is the function's API/contract as far as clients are concerned. Hence, I slightly prefer enum impl Trait over enum Trait or impl enum Trait.

I believe the main thing preventing these discussions from going anywhere is that making it even easier to use impl Trait further accentuates the only serious problem with impl Trait: that it encourages making types unnameable. But now that the abstract type proposal exists, I don't personally think that's a big concern anymore.

---

@Nemo157 Hmm, what delegation extensions do you think we'd need? The "desugaring" I've always imagined is just a delegate *, so we'd need enum delegation (technically an extension iirc), and then whatever it takes for a delegate * to "just work" on most traits, which might mean delegation of associated types/constants, and I think that's it.

Though I think we should probably not block this on delegation, since it could just be compiler magic.

[Nemo157]

From the current delegation RFC the extensions required are "delegating for an enum where every variant's data type implements the same trait" (or "Getter Methods" + "Delegate block") and "Delegating 'multiple Self arguments' for traits like PartialOrd" (although, this could be implemented without it and this feature would be in the same state as normal delegation until it's supported).

One thing I just realised is that delegation won't help with unbound associated types, required to support use cases like:

#[enumified]
fn foo() -> impl IntoIterator<Item = u32> {
    if true {
        vec![1, 2]
    } else {
        static values: &[u32] = &[3, 4];
        values.iter().cloned()
    }
}

would need to generate something like

enum Enumified_foo_IntoIterator {
    A(Vec<u32>),
    B(iter::Cloned<slice::Iter<'static>>),
}

enum Enumified_foo_IntoIterator_IntoIter_Iterator {
    A(vec::Iter<u32>),
    B(iter::Cloned<slice::Iter<'static>>),
}

impl IntoIterator for Enumified_foo {
    type Item = u32;
    type IntoIter = Enumified_foo_IntoIterator_IntoIter_Iterator;

    fn into_iter(self) -> self::IntoIter {
        match self {
            Enumified_foo_IntoIterator::A(a)
                => Enumified_foo_IntoIterator_IntoIter_Iterator::A(a.into_iter()),
            Enumified_foo_IntoIterator::B(b)
                => Enumified_foo_IntoIterator_IntoIter_Iterator::B(b.into_iter()),
        }
    }
}

impl Iterator for Enumified_foo_IntoIterator_IntoIter_Iterator {
    ...
}

[Ekleog]

@Ixrec Oh indeed, I didn't think of the Result<Foo, impl ErrorTrait> use case (my use case being really futures and wanting not to allocate all the time), that would make a syntax with the marker at return site much less convenient, with ?.

However, this could be “fixed” by piping ?'s definition through sed 's/return/return MARKER/'.

This wouldn't change the behaviour for existing code (as adding MARKER when there is a single variant would be a no-op). However, an argument could be raised that it does the reducing of performance without explicit marker, but for ? the boat has sailed and it's already using From magically.

So I still think that the ease of using MARKER through type-inferred branches (like let x = match { ... }), and not only at typed boundaries (like function-level return or let x: MARKER Trait = match { ... }), is a net enough win in favor of MARKER at the return site, with an implicit MARKER for ?.

However, as a downside of MARKER at return site, I must add that having it at return site will likely make implementation harder: what is the type of { MARKER x }? I'd say it could be handled by having a “TypeInProgress” type that would slowly be intersected with all the other types, and MARKER basically lifts Type to TypeInProgress(Type), and then typing rules follow, eg.

fn bar() -> bool {…}
struct Baz {} fn baz() -> Baz {…}
struct Quux {} fn quux() -> Quux {…}
struct More {} fn more() -> More {…}

trait Trait1 {} impl Trait1 for Baz {} impl Trait1 for Quux {} impl Trait1 for More
trait Trait2 {} impl Trait2 for Baz {} impl Trait2 for Quux {}

fn foo() -> impl Trait1 {
    let x = match bar() {
        true => MARKER baz(), //: TypeInProgress(Baz)
        false => MARKER quux(), //: TypeInProgress(Quux)
    }; //: TypeInProgress(Baz, Baz) & TypeInProgress(Quux, Quux)
    // = TypeInProgress(Trait1 + Trait2, enum { Baz, Quux })
    // (all the traits implemented by both)
    if bar() {
        MARKER x //: TypeInProgress(Trait1 + Trait2, enum { Baz, Quux })
    } else {
        MARKER more() //: TypeInProgress(More, More)
    } // TypeInProgress(Trait1 + Trait2, enum { Baz, Quux }) & TypeInProgress(More, More)
    // = TypeInProgress(Trait1, enum { Baz, Quux, More })
    // (all the types implemented by both)
}

And, once this forward-running phase has been performed, the actual type can be observed (ie. here enum { Baz, Quux, More }), generated, and backwards-filled into all the TypeInProgress placeholders. Obviously, this requires that at the time of MARKER, the type is already known.

On the other hand, for a return-site-level MARKER setup, the scheme I can think of is the following:

// (skipping the same boilerplate)

fn foo() -> MARKER Trait1 {
    let x: MARKER Trait1 = match bar() {
        true => baz(),
        false => quux(),
    }; // Here we need to infer MARKER Trait1.
    // Observing all the values that come in, we see it must be enum { Baz, Quux }
    if bar() {
        x
    } else {
        more()
    } // Here we need to infer MARKER Trait1.
    // Observing all the values that come in, it must be enum { enum { Baz, Quux }, More }
}

I personally find the syntax of the second example less convenient (it forces writing down exactly which trait(s) we want to have, not letting type inference do its job) and the end-result less clean (two nested enums will be harder to optimize). It also will likely not detect common subtrees, eg. if the more() of the else branch was replaced by if bar() { more() } else { baz() }, the first type inference algorithm would infer enum { Baz, Quux, More }, because TypeInProgress(Trait1, enum { Baz, Quux, More }) is the intersection of TypeInProgress(Trait1 + Trait2, enum { Baz, Quux }) and TypeInProgress(Trait1, enum { More, Baz }) ; while the second type inference algorithm would be forced to complete the typing at the let x: MARKER Trait1, and would thus have to infer enum { enum { Baz, Quux }, enum { More, Baz } } (or maybe enum { enum { Baz, Quux }, More, Baz }, and in either case hitting exactly the performance issue of nesting sum types discussed before).

What do you think about the idea of having ? return MARKER x.unwrap_err()? (I agree with you that without it it's most likely best to have MARKER at the return type)

[Ixrec]

I personally find the syntax of the second example less convenient (it forces writing down exactly which trait(s) we want to have, not letting type inference do its job)

For me, the primary use case is returning an enum impl Trait from a function, in which case you already need to write down the traits you want in the signature. So I never saw this as a disadvantage. In fact, it didn't even occur to me to apply enum impl Trait on a regular let binding until today.

I'm not sure I understand the sentiment behind "not letting type inference do its job". Both variations of this idea involve us writing an explicit MARKER to say we want an autogenerated anonymous enum type. In both cases, type inference is only gathering up all the variants for us, and never inferring the need for an anon enum type in the first place. In both cases, the variable x needs to have a type of some kind, at least for type-checking purposes, and in both cases that type may very well disappear during compilation/optimization. So, what's the job that type inference doesn't do in the MARKER-on-signature case?

and the end-result less clean (two nested enums will be harder to optimize). It also will likely not detect common subtrees

I'm not sure I buy either of these claims. To the extent that "detecting common subtrees" is important, I would expect the existing enum layout optimizations to effectively take care of that for free. We probably need an actual compiler dev to comment here, but my expectation would be that the actual optimization-inhibiting difficulties would come from having "all traits" implemented by the anon enums, instead of just the traits you need.

And to me, the autogenerated anonymous enum type implementing more traits than I need/want it to is "less clean". I guess that's one of those loaded terms that's not super helpful.

I'm not seeing the significance of the TypeInProgress stuff; that seems like machinery you could use in implementing either variation of the syntax, and I don't see what it buys you other than perhaps guaranteeing the type of x goes away. This is probably another thing we need compiler people to comment on, but trying to make some variables not have a type sounds to me like it would be a non-starter, its motivation better addressed my optimizations after type-checking, and entirely orthogonal to the question of what the surface syntax should be anyway.

What do you think about the idea of having ? return MARKER x.unwrap_err()? (I agree with you that without it it's most likely best to have MARKER at the return type)

I think "the idea of having ? return MARKER x.unwrap_err()" is also strictly an implementation detail that's not really relevant to the surface syntax debate, especially since ? is already more than just sugar over a macro.

---

To clarify, I believe the real, interesting issue here is whether we want these anonymous enum types to implement only the traits we explicitly ask for, or all the traits they possibly could implement. Now that this question has been raised, I believe it's the only outstanding issue that really needs to get debated to make a decision on whether MARKER goes at every return site or only once in the signature/binding.

My preference is of course for the traits to be listed explicitly, since I believe the primary use case to be function signatures where you have to list them explicitly anyway, and I also suspect that auto-implementing every possible trait could lead to unexpected type inference nuisances, or runtime behavior, though I haven't thought about that much.

Let's make the type inference nuisance thing concrete. Say Trait1 and Trait2 both have a foo method, and types A and B both implement both traits. Then you want to write a function that, as in your last two examples, returns enum impl Trait1 and has a let binding on a match with two branches. If we go with your variation, the let binding infers the equivalent of enum impl Trait1+Trait2 and a foo() call later in the function becomes ambiguous, while in my variation you have to explicitly write enum impl Trait1 so a call to foo() just works. That's a real disadvantage of auto-implementing all possible traits, right?

[Ekleog]

I think "the idea of having ? return MARKER x.unwrap_err()" is also strictly an implementation detail that's not really relevant to the surface syntax debate, especially since ? is already more than just sugar over a macro.

Well, I added it to answer your concern that it would be painful to have to add MARKER at return sites like ? :)

Let's make the type inference nuisance thing concrete. Say Trait1 and Trait2 both have a foo method, and types A and B both implement both traits. Then you want to write a function that, as in your last two examples, returns enum impl Trait1 and has a let binding on a match with two branches. If we go with your variation, the let binding infers the equivalent of enum impl Trait1+Trait2 and a foo() call later in the function becomes ambiguous, while in my variation you have to explicitly write enum impl Trait1 so a call to foo() just works. That's a real disadvantage of auto-implementing all possible traits, right?

That's true. However, the same could be said with regular types: if I return a single value (so no MARKER anywhere), that implements Trait1 + Trait2 and put it in an un-typed variable, then calls to foo() later will be ambiguous. So that's consistent with what we currently have, and I don't think that's a real disadvantage: it's still possible to explicitly type with return-site marker, if you want to implement only a single trait and/or type inference fails: let x: impl Trait1 = if foo() { MARKER bar() } else { MARKER baz() } (the marking of a specific type would “close” the TypeInProgress type and realize it)

I'm not seeing the significance of the TypeInProgress stuff; that seems like machinery you could use in implementing either variation of the syntax, and I don't see what it buys you other than perhaps guaranteeing the type of x goes away.

Well, apart from the end-result being cleaner (and I don't think enum layout optimizations could optimize enum { enum { Foo, Bar }, Bar, Quux } into enum { Foo, Bar, Quux }, at least with named enums, as the tag could have significance), I don't know about rustc specifically, but typing is usually done on the AST. And on an AST, I think it'd be easier to go forward and slowly complete the type of a variable, than to try to go backwards from the return point to the return sites, and from there check all the possible types that could be returned .

Actually, I'd guess that's how rustc currently does type inference:

fn foo() -> Vec<u8> {
    let res = Vec::new; //: TypeInProgress(Vec<_>)
    bar();
    res // Here we know it must be Vec<u8>, so the _ from above is turned into u8
}

This is probably another thing we need compiler people to comment on, […]

Completely agree with you on this point :)

[nielsle]

Would it be practical to use a procedural macro to derive a specialized iterator for each word? (It seems possible, but a little verbose)

#[derive(IntoLetterIter)]
#[IntoLetterIterString="foo"]
struct Foo;

#[derive(IntoLetterIter)]
#[IntoLetterIterString="hello"]
struct Hello;

fn foo(x: bool) -> impl IntoIterator<Item = u8> {
    if x {  
        Foo 
    } else {
        Hello
    }
}

[joshtriplett]

I'm concerned with the degree to which this seems to combine the implementation details of this specific optimization with the code wanting to use that optimization. It seems like, despite impl Trait itself being a relatively new feature, we're talking about extending it to include a form of reified vtables as an optimization, and exposing that particular choice of optimization with new syntax. And we're doing that without any performance numbers to evaluate that optimization.

I also wonder to what degree we could detect the cases where this makes sense (e.g. cases where we can know statically which impl gets returned) and handle those without needing the hint. If the compiler is already considering inlining a function, and it can see that the call to the function will always result in the same type implementing the Trait, then what prevents it from devirtualizing already?

I'd suggest, if we want to go this route, that we need 1) an implementation of this that doesn't require compiler changes, such as via a macro, 2) benchmarks, and 3) some clear indication that we can't already do this with automatic optimization. And even if we do end up deciding to do this, I'd expect it to look less like a marker on the return type or on the return expressions, and more like an #[optimization_hint] of some kind, similar to #[inline]

[maplant]

Just to add my thoughts to this without clutter, here is my version of the optimization: https://internals.rust-lang.org/t/allowing-multiple-disparate-return-types-in-impl-trait-using-unions/7439 Automatically generating an enum is one way to devirtualize, but without inlining a lot of redundant match statements would be generated. I'm interested in seeing what performance gains can be gleaned from this, if any.

I think that automatic sum type generation should be left to procedural macros

[Nemo157]

@joshtriplett I don’t believe the only reason to want this is as an optimisation. One of the major reasons I want this is to support returning different implementations of an interface based on runtime decisions without requiring heap allocation, for use on embedded devices. I have been able to avoid needing this by sticking to compile time decisions (via generics) and having a few manually implemented delegating enums, but if this were supported via the language/a macro somehow that would really expand the possible design space.

I do agree that experimenting with a macro (limited to a supported set of traits, since it’s impossible for the macro to get the trait method list) would be the way to start. I’ve been meaning to try and throw something together myself, but haven’t found the time yet.

[maplant]

@joshtriplett to address part of your comment, i.e. benchmarks, I created a repository that uses my method and benchmarks it against Box. Although I only have one test case and it is somewhat naive, it seems that my method is about twice as fast as Box. Repo here: https://github.com/DataAnalysisCosby/impl-trait-opt

[joshtriplett]

@Nemo157 I don't think you need heap allocation to use -> impl Trait, with or without this optimization.

But in any case, I would hope that if it's available as an optimization hint, it would have an always version just like inline does.

[Ekleog]

@joshtriplett Let's look at this example (here showing what we want to do):

trait Trait {}
struct Foo {} impl Trait for Foo {}
struct Bar {} impl Trait for Bar {}

fn foo(x: bool) -> impl Trait {
    if x {
        Foo {}
    } else {
        Bar {}
    }
}

(playground)

This doesn't build. In order to make it build, I have a choice: either make it a heap-allocated object:

fn foo(x: bool) -> Box<Trait> {
    if x {
        Box::new(Foo {})
    } else {
        Box::new(Bar {})
    }
}

(playground)

Or I do it with an enum:

enum FooBar { F(Foo), B(Bar) }
impl Trait for FooBar {}
fn foo(x: bool) -> impl Trait {
    if x {
        FooBar::F(Foo {})
    } else {
        FooBar::B(Bar {})
    }
}

(playground)

The aim of this idea is to make the enum solution actually usable without a lot of boilerplate.

Is there another way to do this without heap allocation that I'd have missed?

As for the idea of making it an optimization, do you mean “just return a Box and have the compiler optimize-box-away(always)”? If so, how would it handle no_std systems, that don't (IIRC, my last use of such a system was ~a year ago) actually have Box::new?

[joshtriplett]

@Ekleog Ah, thank you for the clarification; I see what you're getting at now.

[nielsle]

Regarding the third playground example, you can use derive_more to derive Foo.into(), or alternatively you can use derive-new to derive a constructor for FooBar.These libraries do not solve the complete problem in the RFC, but they may help a little.

AFAICS a procedural macro on the following form could potentially solve the complete problem

#[derive(IntoLetterIter)]
enum FooBar {
    #[format="foo"]
    Foo,
    #[format="hello"]
    Hello,
}

[MajorBreakfast]

Quick question: How does this proposal look like on the calling site?

fn foo(x: bool) -> impl Iterator<Item = u8> { ... } // Uses what is proposed here

fn main() {
    foo().next(); // Usage like this?
}

And an idea. What about:

fn foo(x: bool) -> Box<dyn Trait>; // Rust 2018 version of `Box<Trait>`
fn foo(x: bool) -> dyn Trait; // Possible syntax for this proposal
fn foo(x: bool) -> dyn impl Trait; // Both keywords.
                                   // impl suggests that the actual type is unnamed
                                   // dyn suggests that there is dynamic dispatch

dyn would make sense to me because there is dynamic dispatch involved unless the compiler can infer that it is not required in a particular scenario. (Maybe this is nonsense. I'm just suggesting it in case it's not 😄)

[Pauan]

@MajorBreakfast The caller doesn't know (or care) whether the function is using auto-generated enums or not: everything works normally. So your example will work.

As for the syntax, my understanding is that dyn Trait is already used for trait objects, e.g. impl dyn Trait { ... }

And the performance characteristics (and behavior) of auto-generated enums is different from trait objects, so I'm not sure if it's a good idea to try and associate them together.

[MajorBreakfast]

As for the syntax, my understanding is that dyn Trait is already used for trait objects, e.g. impl dyn Trait { ... }

Isn't this effectively a trait object on the stack instead of the heap? If not, where is the difference?

Edit: The difference is the size of course, duh o_O Wasn't thinking right when I wrote this. The question is: Is it close enough to call it dyn?

[MajorBreakfast]

• I agree with @Ixrec that the marker should be on the signature for convenience, but dropped in rustdoc because it's irrelevant for API compat (comment by @Ixrec)
• I don't quite like enum as additional keyword
  • It's only half the story (data layout). The other half is dynamic dispatch.
  • The value does not behave like an enum. It's all hidden

[Pauan]

@MajorBreakfast Aside from the performance, there's also the fact that trait objects have type erasure: a Box<dyn Trait> can be anything that implements that trait. Whereas an auto-generated enum has a very specific and known set of types.

As for the syntax, my point is that the dyn Trait syntax is already being used, so it might not be feasible or desirable to use it for auto-generated enums.

It's only half the story (data layout). The other half is dynamic dispatch.

The "dynamic dispatch" is simply a match, which is the normal way of using enum. There's nothing special about it.

The value does not behave like an enum. It's all hidden

But it does behave exactly like an enum. The fact that it is an unnameable type (just like closures) doesn't change its behavior or how the programmer thinks about it.

Just like how programmers can reason about closures, even though their exact layout is unspecified (and they are unnameable), the same is true with auto-generated enums.

[MajorBreakfast]

Aside from the performance, there's also the fact that trait objects have type erasure: a Box can be anything that implements that trait. Whereas an auto-generated enum has a very specific and known set of types.

From the user's perspective this is also type erasure. The types are only known to the compiler.

The "dynamic dispatch" is simply a match, which is the normal way of using enum.

The match that @Nemo157 mentions here only exists in generated code. I think the example he gives is more for illustration and it actually simulates how a trait object would redirect the call to the correct implementation.

But it does behave exactly like an enum.

No, you can't match on it.

[Pauan]

From the user's perspective this is also type erasure. The types are only known to the compiler.

Sure, it is a form of type erasure, but it still feels qualitatively different from Box<dyn Trait>. I can't quite articulate why it feels different for me.

The match that @Nemo157 mentions here only exists in generated code. [...] No, you can't match on it.

Of course that's a natural consequence of it being unnameable, but the performance and behavior should still be the same as an enum.

[MajorBreakfast]

@Pauan

but it still feels qualitatively different from Box. I can't quite articulate why it feels different for me.

Differences:

• As you said, dyn Trait can be a lot of types. This one can only be one of a few types mentioned inside the function.
• A dyn Trait is unsized. At runtime it has a size and it's as big as it needs to be. This one is an enum, so it's size is known at compile time and it's as big as the largest of its variants.

Although I think the two are quite similar, I also think you're right for not wanting to call it a dyn.

but the performance and behavior should still be the same as an enum.

Performance, yes. But, all enum-ish behaviour isn't visible to the user. That's why I suggest not calling it an enum. If we can come up with something better that is ^^' (Making sum a keyword is a bad idea, because it'll break a lot of code for certain)

---

BTW the Unsized Rvalue RFC introduces unsized types on the stack. It doesn't allow functions to return an unsized value, but this might one day be possible in Rust. Consequently a solution other than an enum might be possible in the future. I still like the solution proposed here, because AFAIK async functions won't be able to support unsized types on the stack because they compile to a state machine.

[alexreg]

Yes, it does indeed feel very different from Box, because at the end of the day the type is statically known. This should be reason enough.

[Nemo157]

I took the evening to throw together an experimental proc-macro based implementation: https://github.com/Nemo157/impl_sum

There's some big limitations documented in the readme, with probably other stuff I forgot/didn't notice, but if anyone else wants to experiment with this there's something to work with there now. (If you have any implementation comments/issues feel free to open issues on that repo to avoid cluttering this issue).

[Diggsey]

Re: syntax, what about an attribute in the type signature (not actually sure if attributes are allowed here but w/e)

fn do_something() -> Vec<#[auto_enum] impl Trait> {
    ...
}

Attributes are not typically considered part of the type signature anyway, so there's no problem with it being in the return type position.

[alexreg]

An attribute in the type sig? That’s some super-ugly syntax. Plus there’s no precedent for it. The enum keyword makes more sense to me.

[mitsuhiko]

Out of all the proposals here something like #[marker] on the function itself makes most sense to me. In particular there are too many macros that just return so that a marker on the return position makes no sense.

[alexreg]

@mitsuhiko The thing is, this functionality can't be properly replicated by a (procedural) macro. So making it look like it is a macro is just deceptive at best.

[Nemo157]

@mitsuhiko what macros are you thinking of? The only only I can think of is try!/? but wanting the error type to be an auto-generated sum type seems unlikely to me.

One extra difficulty might be supporting closure transforms, would it be possible to support a function like this where the sum type for impl Display happens inside an inner closure:

fn load(input: Option<&str>, number: bool) -> Option<impl Display> {
    input.map(|v| {
        if number {
            v.parse::<i32>().unwrap()
        } else {
            v.into_owned()
        }
    })
}

This example could also be extended to have 2 of the branches inside the closure, and an additional branch or 2 outside it.

[mitsuhiko]

@Nemo157 I can't judge how likely it is that errors might not be sum types here as we cannot predict what will happen in the future. I also think that modifiers on return are significantly harder to understand for users (and make the language more complex) than an attribute. Let alone that there are implied returns.

About which macros it affects: a lot of Rust projects have their own try macros. Almost all of mine have some custom try!/unwrap! type macros. The failure crate has custom "error throwing" macros etc.

@alexreg why can a procedural macro not replicate it? But regardless there are lots of compiler internals that are implemented as special macros or attributes so this would not be completely new to the language.

[Ekleog]

@mitsuhiko With a proposal like #[marker] on the function itself (as opposed to return type), how would you type things like this? (here using marker on return type for clarity)

let foo: impl Display = if bar { "foo".to_owned() } else { 5 };
println!("{}", foo);

I can understand the idea of having a marker on return type (and then the #[marker] syntax looks ugly to me, having -> Option<#[marker] impl Display> for @Nemo157's example, and I think another syntax would be better), but I don't really get the idea of having a marker on the function itself.

In my mind this is more a debate of how we want to say to Rust “Please wrap this value in an anonymous enum for me” and/or “Please make an anonymous enum out of these values”.

I prefer the first option (in part because I don't see a clear way for the user to understand from which values exactly the compiler will infer the type) And so I think the most intuitive is marker-on-return-site, but marker-on-return-type might make sense to.

Actually, to understand my reason given in parenthesis above, here is an example of why I feel uneasy about the return-type marker option:

fn foo() -> marker impl Trait {
    let bar = if test() { something() } else { somethingelse() };
    if othertest() { bar } else { stillotherstuff() }
}

Assuming something, somethingelse and stillotherstuff all return different types implementing Trait, not knowing how the compiler is implemented I can't really guess whether this will build or not. Is the type forced at the let bar boundary? Is it left “in progress”?

The advantage of the return-site marker option is that it makes things “explicitly implicit”: when encountering the marker, the value is wrapped in an anonymous enum ready to be extended, and when the being-built anonymous enum hits a type, it is realized. While with the return-type marker, the question is “which are the paths considered by the compiler as leading to the return-type marker?”, which I think can't be answered without a clear understanding of the internals.

About the issue of macros that return, they could just add the marker on each return site: if a single type is ever encountered by an anonymous enum, it will be an anonymous enum with a single member, which could (should?) actually be returned as the said member -- thus being a noop when there is no need for anonymous enums, and automatically adding anonymous enum capability when asked for.

[mitsuhiko]

@Ekleog

@mitsuhiko With a proposal like #[marker] on the function itself (as opposed to return type), how would you type things like this? (here using marker on return type for clarity)

let foo: impl Display = #[marker] {
    if bar { "foo".to_owned() } else { 5 }
};
println!("{}", foo);

Also I do wonder if the marker could not just go entirely. If the impact of that generated type is not too big then it might just be that this could be an acceptable solution to begin with. Hard to tell though.

[Ekleog]

@mitsuhiko So between

fn foo() -> marker impl Trait {
    let foo: marker impl Trait = if bar() { baz() } else { quux() };
    if x() { foo } else { y() }
}

and

#[marker]
fn foo() -> impl Trait {
    let foo: impl Trait = #[marker] {
        if bar() { baz() } else { quux() }
    };
    if x() { foo } else { y() }
}

you'd rather have the second one? (comparing to return-site as that's the closest to your proposal, with the smallest non-trivial example I could manage)

If so I think we can only agree to disagree :)

[mitsuhiko]

I just don't see a reason why this should become syntax in the first place. If it's such a great feature and the performance impact is a massive deal then it can still migrate from an attribute to real syntax later.

[MajorBreakfast]

@mitsuhiko

Also I do wonder if the marker could not just go entirely.

I think there should be a marker:

• Rust likes to make things explicit. If you've got two types with different sizes they get combined into an enum with the size of the bigger type plus discriminant. Should this really be hidden?
• An enum is not the only way to solve this. Currently Rust does not support dynamically sized rvalues. It is however likely that this is going to change in the future.

[mitsuhiko]

Also to further add to my stance on attributes: even async/await started out with not introducing new syntax. This is a fringe feature in comparison.