Using impl Trait in a recursive function

Question

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?

Answer 1

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.

Answer 2

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