7

I've been experimenting with impl Trait and I came across this error when building a recursive function:

error[E0308]: if and else have incompatible types
  --> src/main.rs:16:5
   |
16 | /     if logic {
17 | |         one(false)
18 | |     } else {
19 | |         two()
20 | |     }
   | |_____^ expected opaque type, found a different opaque type
   |
   = note: expected type `impl Meow` (opaque type)
              found type `impl Meow` (opaque type)

Here's the code to reproduce (Rust playground link):

trait Meow {
    fn meow();
}

struct Cat(u64);

impl Meow for Cat {
    fn meow() {}
}

fn one(gate: bool) -> impl Meow {
    if gate {
        one(false)
    } else {
        two()
    }
}

fn two() -> impl Meow {
    Cat(42)
}

fn main() {
    let _ = one(true);
}

I haven't been able to find documentation about this particular issue and I find it odd that the compiler returns an error that roughly says "these two identical things are different".

Is there a way I can support the impl Trait syntax whilst doing this kind of recusion, please?

Improve this question
7
  • This is a slightly different question. Here the compiler could ideally deduce that the impl Meow returned by one must be the same as the impl Meow returned by two, whatever it is, in which case the two if branches would unify. It just doesn’t, today. Commented Jan 4, 2019 at 5:50
  • @AndersKaseorg while the question might be different, the answer is still the same as in the duplicate Commented Jan 4, 2019 at 8:51
  • @hellow I disagree. I thought so too at first, but then I looked more carefully at this question and came up with my answer, which is specific to this recursion pattern and does not require a trait object. Commented Jan 4, 2019 at 10:07
  • 1
    I agree with @AndersKaseorg, while the workaround in the linked answer also solves this issue, the reason why this fail is somewhat different: in the linked answer there are two different types that both implement the trait; in this question however there is only one type that implements the trait, and a smarter compiler could just accept it. Commented Jan 4, 2019 at 11:58
  • 1
    @MatthieuM.: Hmmm, yes, that's true if the caller and the callee are different functions. But what about a recursive function, can it use its own implementation when checking the recursive call? Maybe there are theoretical reasons not to do that, but I don't see any practical drawback. Commented Jan 4, 2019 at 13:43

2 Answers 2

Reset to default
7

Disclaimer: this answer assumes that the reader understands that -> impl Trait requires a single type to be returned; see this question for returning different types.

Opacity

One of the core principles of Rust is that type-checking is entirely driven by the interface of functions, types, etc... and the implementation is ignored.

With regard to -> impl Trait functionality, this manifests by the language treating each -> impl Trait as an opaque type, solely identified by the function it comes from.

As a result, you can call the same function twice:

use std::fmt::Debug;

fn cat(name: &str) -> impl Debug { format!("Meow {}", name) }

fn meow(g: bool) -> impl Debug {
    if g {
        cat("Mario")
    } else {
        cat("Luigi")
    }
}

fn main() {
    println!("{:?}", meow(true));
}

But you cannot call different functions, even when they return the same type, if at least one is hidden behind -> impl Trait:

use std::fmt::Debug;

fn mario() -> impl Debug { "Meow Mario" }

fn luigi() -> &'static str { "Meow Luigi" }

fn meow(g: bool) -> impl Debug {
    if g {
        mario()
    } else {
        luigi()
    }
}

fn main() {
    println!("{:?}", meow(true));
}

Yields:

error[E0308]: if and else have incompatible types
  --> src/main.rs:8:9
   |
8  | /         if g {
9  | |             mario()
10 | |         } else {
11 | |             luigi()
12 | |         }
   | |_________^ expected opaque type, found &str
   |
   = note: expected type `impl std::fmt::Debug`
              found type `&str`

And with two hidden behind -> impl Trait:

use std::fmt::Debug;

fn mario() -> impl Debug { "Meow Mario" }

fn luigi() -> impl Debug { "Meow Luigi" }

fn meow(g: bool) -> impl Debug {
    if g {
        mario()
    } else {
        luigi()
    }
}

fn main() {
    println!("{:?}", meow(true));
}

Yields the same error message than you got:

error[E0308]: if and else have incompatible types
  --> src/main.rs:8:5
   |
8  | /     if g {
9  | |         mario()
10 | |     } else {
11 | |         luigi()
12 | |     }
   | |_____^ expected opaque type, found a different opaque type
   |
   = note: expected type `impl std::fmt::Debug` (opaque type)
              found type `impl std::fmt::Debug` (opaque type)

Interaction with Recursion

None.

The language does not special-case recursion here, and therefore does not realize that, in the case presented in the question, there is only ever one type involved. Instead, it notices fn one(...) -> impl Meow and fn two(...) -> impl Meow and concludes that those are different opaque types and therefore compile-time unification is impossible.

It may be reasonable to submit a RFC to tweak this aspect, either by arguing on the point of view of recursion, or by arguing on the point of view of module-level visibility; this is beyond the scope of this answer.

Work around

The only possibility is to ensure that the type is unique, and this requires naming it. Once you have captured the type in a name, you can consistently apply it everywhere it needs to match.

I'll refer you to @Anders' answer for his clever work-around.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

5

I think an ideal compiler would accept your code, but the current language doesn’t allow for the recursive reasoning that would be needed to figure out that the types are actually the same in this case. You can work around this missing feature by abstracting over the impl Meow type with a type variable:

fn one_template<T: Meow>(gate: bool, two: impl FnOnce() -> T) -> T {
    if gate {
        one_template(false, two)
    } else {
        two()
    }
}

fn one(gate: bool) -> impl Meow {
    one_template(gate, two)
}

Rust playground link

Improve this answer

4 Comments

@MatthieuM. Your comment is not relevant to my answer. There is no dyn Trait involved here at all. This is entirely about working around a type unification problem between types that really are the same. (This is not like the other question where the types appear to be the same but aren’t!) If the compiler performed the unification correctly, it would still be zero-overhead. Did you read this carefully before marking it as a duplicate?
I agree with @Matthieu; the opacity of the type is the whole point. There are infinitely many things that a sufficiently smart compiler could do for you, but de-opacifying an opaque type is something it's not meant to do (along the same lines as full program type inference).
@trentcl Can we just get a few things out of the way: I fully understand that impl Trait is opaque, and that dyn Trait has run-time overhead (even though dyn Trait has nothing to do with this question). I am not proposing that the compiler should de-opacify impl Meow everywhere. That would be a total catastrophe for the abstraction barrier that impl Meow is meanat to enforce. Okay? We agree on all of that. But here, because we’re dealing with recursion, we’re supposed to be inside that abstraction barrier. We ought to be able to unify our own return type with our own return type!
Now you can agree or disagree that the language should be extended in that way. Fine. But can we at least acknowledge that this is a different question than the generic questions about impl Trait opacity and impl Trait being different from dyn Trait?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.