Typenum ambiguity

[compiler-errors]

fn main() {
    let _: <typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0> as typenum::Pow<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0>, typenum::B1>>>::Output;
}

The type above, which should be equivalent to U32 (since it's 0b10^0b101 = 2^5 = 32), but results in ambiguity (or overflow? can't tell):

error[E0282]: type annotations needed
 --> src/main.rs:2:12
  |
2 | ..._: <typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0> as typenum::Pow<typenum::UInt<typenum::UInt<typenum::UInt<typenum::UTerm, typenum::B1>, typenum::B0>, typenum::B1>>>::Outp...
  |       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot infer type for associated type `<UInt<UInt<UTerm, B1>, B0> as Pow<UInt<UInt<UInt<UTerm, B1>, B0>, B1>>>::Output`

[compiler-errors]

Keeping me from being able to test rust-lang/rust#112365.

[lcnr]

minimized

#![recursion_limit = "512"]


fn main() {
    let _: <typenum::consts::U1 as typenum::Pow<typenum::consts::U4>>::Output;
}

1^4 also fails, X^3 works

[lcnr]

fn bound<T, U: ?Sized>()
where
    T: std::ops::Mul<Output = U>,
{
}

fn main() {
    bound::<<typenum::UInt<typenum::UTerm, typenum::B1> as std::ops::Mul>::Output, _>()
}

(1*1)*(1*1) xd

[lcnr]

fn bound<T, U, V: ?Sized>()
where
    T: std::ops::Add<U, Output = V>,
{
}

fn main() {
    bound::<
        <typenum::U1 as std::ops::Add<typenum::U0>>::Output,
        <typenum::U1 as std::ops::Add<typenum::U0>>::Output,
        _,
    >()
}

(1 + 0) + (1 + 0)

need a Projection goal

[lcnr]

further minimized, feels like a generalizer shortcoming

trait Id {
    type Assoc: ?Sized;
}
impl<T: ?Sized> Id for T {
    type Assoc = T;
} 

fn bound<T, U, V: ?Sized>()
where
    T: std::ops::Add<U, Output = V>,
{
}

fn main() {
    bound::<
        <typenum::U1 as Id>::Assoc,
        <typenum::U1 as Id>::Assoc,
        _,
    >()
}

[compiler-errors]

Minimized away the dependency:

use std::ops::Add;

trait Id {
    type Assoc: ?Sized;
}
impl<T: ?Sized> Id for T {
    type Assoc = T;
}

fn bound<T, V: ?Sized>()
where
    T: Add<T, Output = V>,
{
}

fn main() {
    bound::<<U1 as Id>::Assoc, _>()
}

// Inlined deps from typenum

struct UTerm;

struct UInt<U, B> {
    _msb: U,
    _lsb: B,
}

struct B0;
struct B1;

trait Bit {}

type U1 = UInt<UTerm, B1>;

trait Unsigned {}

impl Unsigned for UTerm {}

impl<U: Unsigned, B: Bit> Unsigned for UInt<U, B> {}

impl Add<B1> for UTerm {
    type Output = UInt<UTerm, B1>;

    fn add(self, _: B1) -> Self::Output {
        todo!()
    }
}

impl<U: Unsigned> Add<U> for UTerm {
    type Output = U;

    fn add(self, _: U) -> Self::Output {
        todo!()
    }
}

impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B1>> for UInt<Ul, B1>
where
    Ul: Add<Ur>,
    <Ul as Add<Ur>>::Output: Add<B1>,
{
    type Output = UInt<<<Ul as Add<Ur>>::Output as Add<B1>>::Output, B0>;

    fn add(self, _: UInt<Ur, B1>) -> Self::Output {
        todo!()
    }
}

[compiler-errors]

Yup, this is due to a generalizer shortcoming afaict. We end up generalizing UInt<<<UTerm as Add<?1t>>::Output as Add<B1>>::Output, B0> into UInt<<<UTerm as Add<?2t>>::Output as Add<B1>>::Output, B0>, emitting an alias-eq goal in the process. This ends up stalling out in ambiguity.

[compiler-errors]

Solution to this would be:

1. Re-apply the subst-relate incompleteness, or
2. Fix generalizing projections.

[lcnr]

further minimized

trait Id {
    type Assoc: ?Sized;
}
impl<T: ?Sized> Id for T {
    type Assoc = T;
}

trait WithAssoc<T: ?Sized> {
    type Assoc: ?Sized;
}


struct Leaf;
struct Wrapper<U: ?Sized>(U);

impl<U: ?Sized> WithAssoc<U> for Leaf {
    type Assoc = U;
}

impl<Ul: ?Sized, Ur: ?Sized> WithAssoc<Wrapper<Ur>> for Wrapper<Ul>
where
    Ul: WithAssoc<Ur>,
{
    type Assoc = <<Ul as WithAssoc<Ur>>::Assoc as Id>::Assoc;
}

fn bound<T: ?Sized, U: ?Sized, V: ?Sized>()
where
    T: WithAssoc<U, Assoc = V>,
{
}

fn main() {
    bound::<<Wrapper<Leaf> as Id>::Assoc, <Wrapper<Leaf> as Id>::Assoc, _>()
}