Bigcurve trait regression

[TomAFrench]

trait BigNumTrait {}

pub struct MyBigNum;

impl crate::BigNumTrait for MyBigNum {}

trait CurveParamsTrait<BigNum>
where
    BigNum: BigNumTrait,
{
    fn one();
}

pub struct BN254Params;
impl CurveParamsTrait<MyBigNum> for BN254Params {

    fn one() {}
}

trait BigCurveTrait {
    fn one();
}

pub struct BigCurve<BigNum, CurveParams> {}

type BN254 = BigCurve<MyBigNum, BN254Params>;

impl<BigNum, CurveParams> BigCurveTrait for BigCurve<BigNum, CurveParams>
where
    CurveParams: CurveParamsTrait<BigNum>,
    BigNum: BigNumTrait,
{
    fn one() {
        let _ = CurveParams::one();
    }
}

fn main() {
    let P = BN254::one();
}

This is a minimised (maybe not minimal) reproduction of the issue currently affecting https://github.com/noir-lang/noir_bigcurve as reported by @kashbrti.

fyi @asterite as you've been working on the trait system recently.

[TomAFrench]

My guess is that we're not properly applying the trait constraints on BigNum onto CurveParams properly here:

impl<BigNum, CurveParams> BigCurveTrait for BigCurve<BigNum, CurveParams>
where
    CurveParams: CurveParamsTrait<BigNum>,
    BigNum: BigNumTrait,

[asterite]

Apparently this PR broke this: #6645

That is, once we started type-checking trait default methods. Now I'll try to understand why, because there are no default methods in the snippet above 🤔

[asterite]

I found that if the where clause is moved from the trait to the function:

trait BigNumTrait {}

pub struct MyBigNum;

impl crate::BigNumTrait for MyBigNum {}

trait CurveParamsTrait<BigNum>
{
    fn one() where BigNum: BigNumTrait;
}

pub struct BN254Params;
impl CurveParamsTrait<MyBigNum> for BN254Params {

    fn one() {}
}

trait BigCurveTrait {
    fn two();
}

pub struct BigCurve<BigNum, CurveParams> {}

type BN254 = BigCurve<MyBigNum, BN254Params>;

impl<BigNum, CurveParams> BigCurveTrait for BigCurve<BigNum, CurveParams>
where
    BigNum: BigNumTrait,
    CurveParams: CurveParamsTrait<BigNum>,
{
    fn two() {
        let _ = CurveParams::one();
    }
}

fn main() {
    let _ = BN254::two();
}

then we get the same error, but we also get the same error before #6645 was merged, so that PR just exposed the bug in more cases.

I'm still not sure how to fix it or why it happens. I have a code change that apparently makes it work, I have an intuition about how it works but I'm not sure. I'll push it anyway to check external repos in the meantime.

[asterite]

Trying to reduce the code a bit I found this code crashes (and it crashes in commit 6515e4e which is before all the trait type-checking work started):

trait BigNumTrait {}

trait CurveParamsTrait<BigNum> {
    fn one()
    where
        BigNum: BigNumTrait;
}

pub struct MyBigNum;

impl BigNumTrait for MyBigNum {}

pub struct Params;
impl CurveParamsTrait<MyBigNum> for Params {

    fn one() {}
}

fn foo<C>()
where
    C: CurveParamsTrait<MyBigNum>,
{
    let _ = C::one();
}

fn main() {
    foo::<Params>();
}

This crashes with this:

The application panicked (crashed).
Message:  index out of bounds: the len is 0 but the index is 0
Location: compiler/noirc_frontend/src/monomorphization/mod.rs:2138

It seems there's something wrong with how trait methods are solved.

[asterite]

So what I'm seeing is happening in the code above is that for this call:

    let _ = C::one();

1. we push a trait constraint for ExprId related to C::one that will check where BigNum: BigNumTrait, checking that MyBigNum implements BigNumTrait. That comes from the function's where clauses.
2. because C::one is a trait method call, we say for now that the selected trait impl for that call (for the same ExprId as above (!)) is an assumed call on CurveTraitParams

When popping the function context we check any trait constraints we pushed. One was pushed in point 1 so we check it. We find that impl BigNumTrait for MyBigNum {} is the BigNumTrait implementation for MyBigNum, and we select that trait implementation for that ExprId. This overwrites the previous trait implementation selection for that expression. And in fact it's wrong because the trait impl selection for C::one should be about CurveParamsTrait... or maybe the issue is that there are two trait impl selections to choose, but only one ExprId to use as the anchor? Or maybe verifying trait constraints doesn't always imply having to select a trait impl. Not sure!