Extending `impl Trait` to allow multiple return types

[ExpHP]

@rkruppe’s backcompat hazard only scrapes the surface:

// This compiles today; as I certainly hope it would!

fn foo(n: u32) -> impl Debug { ... }

fn main() {
    let xs = (0..5).map(foo).collect::<Vec<_>>();
    println!("{:?}", xs);
}

so to me, the simple answer to

[should it] be the default behavior of impl Trait ?

is that making this the default is indefensible. (unless, well… I guess it could be an edition-related change)

[Soni]

can you desugar into a closure with TCO?

[DDOtten]

If we compile an impl Trait function that returns multiple types that implement Trait to a function that returns an enum that implements Trait by delegating the implementation to the enum variants it would be backwards compatible. The function still returns a value that implements Trait. However we could run into some problems for some traits when delegating.

[DDOtten]

Say we have a trait Trait that looks as follows:

trait Trait {
    type Type;

    fn foo(self) -> Self::Type;
    
    fn bar();
}

and a function

fn func(x: bool) -> impl Trait<Type = i32> {
    if x {
        TypeA::new()
    } else {
        TypeB::new()
    }
}

then we compile it to

fn func(x: bool) -> Hidden {
    if x {
        Hidden::HiddenTypeA(TypeA::new())
    } else {
        Hidden::HiddenTypeB(TypeB::new())
    }
}

enum Hidden {
    HiddenTypeA(TypeA),
    HiddenTypeB(TypeB),
}

impl Trait for Hidden {
    type Type = i32;

    fn foo(self) -> Self::Type {
        match self {
            Hidden::HiddenTypeA(a) => a.foo(),
            Hidden::HiddenTypeB(b) => b.foo(),
        }
    }

    fn bar() {
        match &self {
            &Hidden::HiddenTypeA(_) => TypeA::bar(),
            &Hidden::HiddenTypeB(_) => TypeB::bar(),
        }
    }
}

I don’t know if this would be possible for every trait. The only case I see a problem with is traits with a const value. That is a niche case and I think it would be alright to disallow impl Trait with multiple types when Trait contains a value. All cases with impl Trait would still work because we still allow all functions that return a single type and functions that return multiple types really only return one. For that reason I personally we don’t need the enum impl Trait because it does not matter for people that call your function.

[Nemo157]

There’s a lot of prior discussion of the autogenerated sum type idea here: https://github.com/rust-lang/rfcs/issues/2414 (along with a bit of prior discussion across other earlier RFCs).

There’s many things that will cause issues with generating the delegation e.g. fn foo(self, other: Self), but hopefully that can all be handled by a generalized delegation framework that an autogenerated sum type could just reuse.

For that reason I personally we don’t need the enum impl Trait because it does not matter for people that call your function.

It doesn’t matter for people calling your function, but it does matter for writing the function itself, there are different tradeoffs between an auto-generated sum type and a dynamically dispatched type that you should be aware of.

[kennytm]

I would have 'ed the -> enum impl Trait syntax if there was no APIT, but given APIT it feels asymmetric if this isn’t allowed:

fn output() -> enum impl Trait { ... }

fn inpit(a: enum impl Trait) { ... }

Perhaps it should just be a function attribute (since the CPS transform is applied to the whole function)

#[allow(multiple_return_types)]
fn output() -> impl Trait { ... }

fn input(a: impl Trait) { ... }

[drXor]

I dropped by the paint store:

• enum impl Trait APIT is reserved as sugar for the Any mechanism (gross, but the only use of APIT enum impl I can think of).
• An attribute, as you suggest. I like #[polymorphic_return], even though it’s a heinous lie because no monomorphizaton happens. See also #[virtual_return].
• On that note, virtual is reserved. fn foo() -> virtual Trait?
• Drop impl altogether and say enum Trait. This is probably confusing with how items are declared though, especially since this type syntax (from C) suggests that Trait is an enum.
• Move enum to the start of the function: enum fn foo() -> impl Trait. Is there something interesting we can do with a return type that isn’t an impl Trait?
• Since we’re using continuations, -> become Trait? Kinda silly, and maybe we want become T in type position for something else.
• Accept that we can’t have symmetry because covariant (return) position is special.

Relatedly; how many of the problems you’d want to solve with enum impl Trait can be solved by having anonymous coproduct types? We have anonymous product types (tuples) so I hallucinate something like

fn foo(x: (i32 + &'static str)) {
    match x {
        0(i) => println!("int: {}", i),
        1(s) => println!("str: {}", s),
    }
}
// desugar
enum __magic {
    v0(i32), v1(&'static str),
}
fn foo(x: __magic) {
    match x {
        v0(i) => println!("int: {}", i),
        v1(s) => println!("str: {}", s),
    }
}

(Yes, I’m aware that enum impl Trait is not returning an anonymous enum but doing fancy become continuation.)

[scalexm]

Without considering enum impl which is totally fine (the function still returns one specific type), how would you typecheck this with your « multiple return types » setting:

fn bar<T>(x: T, y: T) { }

fn main() {
    bar(g(false), g(true));
}

From a typeck point of view, would the return type of the g function still considered as an enum?

Edit: I see that @rkruppe actually raised a very similar concern

[drXor]

I assume T will tyck as g::return (whatever that is) which is known to be an enum impl Trait. The monomorphization of bar for that value of T will include the necessary become glue, with main simply passing bar::GVtable to g.

[scottmcm]

while an extra keyword like enum makes it clear in the return signature where this happens

While I overall agree with your post, I don’t think this part is necessary.

If I have a method that returns impl Iterator<Item=u8> today, I can totally return an Either<Iter1, Iter2> from inside it without needing to put an enum keyword in the signature. So I don’t see why it ought to be explicit in the signature.

One could have the marker inside the body instead, like

enum if b { it.step_by(2) } else { it.rev() }

[phaylon]

If I have a method that returns impl Iterator<Item=u8> today, I can totally return an Either<Iter1, Iter2> from inside it without needing to put an enum keyword in the signature. So I don’t see why it ought to be explicit in the signature .

Sure, it can also go in the function body somwhere. That keeps the information local as well. Even more local and it documents the intended “merge point”, so I’m all for that alternative.

[kornel]

The original CPS idea is very cool, but I’d be afraid to use it in practice — that’s just asking for exponential growth of code when multiple such calls are combined.

And the lesser variant based around a regular enum, but automagically inserted in all places, doesn’t add any functionality that isn’t available already (without the syntax sugar), so it isn’t as compelling.

[rpjohnst]

First, the questions around backwards compatibility, which I believe is still preserved:

I don’t think we can backwards-compatibly change existing impl Trait return types to this meaning ¹

¹ Consider for example let mut x = returns_impl_trait(1); x = returns_impl_trait(2);

This is not actually an issue for this proposal. impl Trait is, itself, something like ∃ T. T: Trait => T. So at the type-checking level, the types of returns_impl_trait(1) and returns_impl_trait(2) unify.

Each time returns_impl_trait returns, you have the potential to enter a differently-monomorphized piece of the caller, which knows the new concrete type. (And the stack frame can stay the same because x already has to reserve enough space for any of returns_impl_trait's concrete return types.)

@ExpHP’s example is harder, but not impossible either. The idea of forbidding it in the 2018 epoch is appealing in some ways, as Vec<impl Debug> is not a type we support today. But the full interpretation can be made to work, of impl Trait as a full existential type with its witness “folded into the instruction pointer.”

The key is that, while Vec inherently and intentionally “strips away” the control flow around the values it contains, we can instead convert the existential’s witness from its encoding as the instruction pointer to a value that goes in the Vec.

Then, as part of println!, std::slice::Iter<impl Debug>'s Iterator::next method can use the same mechanism as any other function that returns impl Trait- the caller (in this case <[impl Debug] as Debug>::fmt, or rather its indirect callees in the display plumbing) monomorphizes its continuation for each of the concrete types that the original foo call returns, and the callee returns to the appropriate one based on the value stored in the Vec.

And finally, @scalexm’s example—this is also doable, though it’s a more interesting question of whether it should be allowed. At one level, this interpretation means one impl Debug is the same type as any other impl Debug, satisfying the constraint that x and y have the same type.

Without any further constraints on T, it doesn’t actually matter- we could monomorphize bar to give x and y the same size regardless of what g returns. And if you add T: Display or whatever trait g returns, bar could be monomorphized as if it were bar<T, U>(x: T, y: U) while again giving x and y the same size. But at another, is that actually what bar meant? Does it break anything important?

---

And the questions about functionality and syntax:

It’s fascinating to me that we could do this. However, I very much don’t want us to do this, precisely because impl Trait is currently guaranteed to represent a specific concrete type. I look forward to being able to use that unspecified concrete type in other places, such as structs, and this would prevent doing so.

From what I understand, there aren’t any plans to allow putting impl Trait in structs anyway. That’s to be provided by abstract type instead, which also provides a name. What this does disallow is things like this, which try to retroactively name an existing impl Trait type:

abstract type T: Trait;

fn f() -> T { g() }

fn g() -> impl Trait { .. }

a code size explosion that’s roughly exponential in the number of eliminated branches.

This is exactly the same scale as normal generic functions- “roughly exponential” in the number of type parameters, i.e. the number of eliminated dyn Traits. And as @earthengine points out, combinator-based futures code would run different logic in each monomorphized continuation, leading to approximately the same number of “states” as an equivalent async fn.

It’s certainly worth considering, but without benchmarking things I don’t believe we can really say that the outcome is any worse than pervasive use of type parameters. We still need good tools like cargo bloat regardless.

I feel that this is conflating two different questions:

1. Design: Assuming we want an enum impl Trait feature someday, should it require some kind of explicit opt-in / visible piece of syntax, or be the default behavior of impl Trait ?

2. Implementation: Should enum impl Trait be implemented literally as an enum or as this fancy CPS magic?

These are intertwined—the answer to the first depends on (among other things) the answer to the second. One of the issues with enum impl Trait, which makes people want yet-another-syntax for it instead of just reusing impl Trait, is that it’s basically a new dynamic dispatch mechanism. A major draw of this proposal, on the other hand, is that it works the same as argument-position impl Trait, without a new dynamic dispatch mechanism.

So while as it stands I believe this is backwards compatible, we can’t really separate those two questions without at least committing to forward compatibility with it until (1) is decided. And as a general response to the enum impl Trait bikeshedding going on here, I would say any new syntax in the type essentially defeats the proposal’s purpose (of making APIT and RPIT equivalent).

I do think a marker in the callee function body, like @scottmcm suggests, might make sense. It would be a helpful call-out that the following code is using “static existentials,” and isn’t just a type error.

[kornel]

This would work, except overhead of heap allocation:

fn foo() -> dyn Trait {
   Box::new(if random {
       TraitOne()
   } else {
       TraitTwo()
   })
}

So how about adding an alternative to Box that does the magical enum wrapping?

fn foo() -> MagicEnumWrapper<dyn Trait> {
   MagicEnumWrapper::new(if random {
       TraitOne()
   } else {
       TraitTwo()
   })
}

With compiler’s help the MagicEnumWrapper<T> would make new enums for its T as necessary, and the newtype would remain stack-allocated.

[rpjohnst]

MagicEnumWrapper is essentially “unsized rvalues”- which use a vptr instead of an enum, and allows different sizes so it can support things like slices.

[varkor]

For this proposal to be viable, we would definitely want to consider requiring annotations to be present where monomorphisation can occur. For polymorphic functions, we effectively have this in terms of type parameters (here including argument-position impl Trait) — assuming users understand what monomorphisation is.

However, if we blindly allow inference of variables with type impl Trait, which is happening implicitly in the examples here, then we’re effectively inferring a polymorphic type, with no indication this is happening. As such, without looking at function signatures, we might have no idea monomorphisation is occurring.

fn g(b: bool) -> impl Display {
    if b { 42 } else { "hello" }
}

// This version of `f`...
fn f() {
    println!("{}", g(true));
}

// Is equivalent to this version:
fn f() {
    // We're inferring a generic type!
    let x<T: Display>: T = g(true); // Alternatively `let x: impl Display = g(true);`.
    println!("{}", x);
}

If we require type annotations for generic types, then this proposal seems more plausible from a “no hidden costs” point of view. (This also achieves the “callee body marker” functionality @scottmcm suggested.)

With this alteration, not specifying a generic type would force return-position impl Trait to be monomorphic (or otherwise cause an error), as it currently is today, so it entirely preserves the expected behaviour.

[scalexm]

And finally, @scalexm’s example—this is also doable, though it’s a more interesting question of whether it should be allowed. At one level, this interpretation means one impl Debug is the same type as any other impl Debug , satisfying the constraint that x and y have the same type.

I’m not sure I understand what you mean by “whether it should be allowed”. It already compiles, so if you meant “whether it should compile”, then yes it should in order to preserve backward compatibility.

essentially defeats the proposal’s purpose (of making APIT and RPIT equivalent).

I read the posts you linked, there are some points but the mathematical facts are not presented in a very rigorous way and eventually I don’t buy the “APIT and RPIT should be equivalent” thing. For example,

fn foo(x: impl Debug)

may always be considered as a type constructor while

fn bar() -> impl Debug

will never be. At best, we may know that the return type of bar takes values from a specific finite set which highly depends on bar, whereas the input type of foo may take values from an infinite set. Anyway I guess that’s not the interesting point of this topic.

[rpjohnst]

I’m not sure I understand what you mean by “whether it should be allowed”.

Certainly, if we decided to make it stop working it would have to be in the new edition. I was speaking more in terms of whether it makes sense from the perspective of this proposal—that is, the perspective of impl Trait being equivalent to ∃ T. T: Trait => T regardless of its position.

fn foo(x: impl Debug) treats it this way, giving foo the type fn(∃ T. T: Debug => T) -> (), which can only be considered a type constructor because it’s isomorphic to the type ∀ T. T: Debug => fn(T) -> ().

fn bar() -> impl Debug does not treat it this way. The problem is not that there’s no isomorphism to a universal quantifier, but that the type of bar is something other than fn() -> (∃ T. T: Debug => T). It is instead ∃ T. T: Debug => fn() -> T.

Why is the quantifier in a different location? Under the existential types interpretation, there’s no good answer other than “because we implemented something else, for other reasons.” I’m not sure how much more rigorous we can make this—our options are a) keep things as they are, with an inconsistent meaning for impl Trait, b) change the interpretation of impl Trait but not the functionality (this is the inference interpretation), or c) extend the functionality of impl Trait but not the interpretation (this is this proposal).

[varkor]

At the risk of derailing the conversation, I’d like to comment on this:

I read the posts you linked, there are some points but the mathematical facts are not presented in a very rigorous way

If, by “very rigorous way”, you mean formalised, then no, they’re not (the posts were supposed to be reasonably precise, but primarily accessible). I do think they’re more explicit than any other explanation of the existential semantics of impl Trait, and if you’ve spotted a flaw in the reasoning, I’d definitely want to address it.

For example,

fn foo(x: impl Debug)

may always be considered as a type constructor while

fn bar() -> impl Debug

will never be.

A type constructor is a function from a type to a type. fn foo(impl Debug) is a function from value to values. So I don’t understand your point here.

At best, we may know that the return type of bar takes values from a specific finite set which highly depends on bar , whereas the input type of foo may take values from an infinite set.

The return type of bar is a single type (impl Debug). The return type of the function never changes — under the existential interpretation, it’s always an existential type (it doesn’t “take on” the type it’s quantifying). The type over which the return type is quantified, though, could be any type in the universe though (assuming it meets the trait condition). The same goes for the input type.

The difference between argument-position and return-position impl Trait, as discussed in the post, is the quantifier position, which entirely describes the difference in functionality.

[scalexm]

A type constructor is a function from a type to a type. fn foo(impl Debug) is a function from value to values. So I don’t understand your point here.

As you wrote somewhere, fn foo(x: impl Debug) is isomorphic to fn foo<T: Debug>(x: T). When you declare such a function, you are indeed declaring a type constructor T -> fn(T). The fact that you cannot name this constructor in actual Rust is something else. Anyway, my point is that impl Debug in arg position does not depend foo, while impl Debug in return position does depend on bar.

Edit: this is indeed what I was meaning by « not very rigorous », sorry I should have been more clear. Also I’m not a type theorist, but the point that is very unclear to me is when you somehow « map » a logical implication to a function. Apart from sharing the -> symbol, I don’t see how this is done, and I think that could have been explained better.