Trait predicate evaluation cache incorrectly handles EvaluatedToOk

[Aaron1011]

Split out from the discussion in #80336. See #80336 (comment) for the original comments.

---

The issue is caused by the way that we handle regions in the evaluation cache. When we insert a result into the evaluation cache (either infcx.evaluation_cache or tcx.evaluation_cache, we use a 'freshened' version of the original TraitPredicate as the key. The 'freshened' TraitPredicate has all non-late-bound regions erased.

Unfortunately, this can lead to issues if we try to evaluate the following two predicates:

impl SomeTrait for SomeType<'static>

SomeType<'static> as SomeTrait
SomeType<'#_r> as SomeTrait

When we evaluate SomeType<'static> as SomeTrait, we'll get EvaluatedToOk, since the region parameter in our trait ref is known to match the impl. We will then cache the result as <SomeType<'erased> as SomeTrait> -> EvaluatedToOk.

If we later try to evaluate SomeType<'#_r> as SomeTrait, we will end up matching the evaluation cache entry, giving us a result of EvaluatedToOk. However, we should have gotten a result of EvaluatedToOkModuloRegions, since we don't know that '#_r == 'static holds.

This is really difficult to observe in practice, for a number of reasons:

• The relevant trait predicates need to get evaluated, not just registered in a FulfillmentContext.
• Trait evaluation usually goes through the evaluate_obligation query, which canonicalizes the regions in the input trait ref. To end up trying to evaluate SomeType<'static> as SomeTrait, we need to end up calling evaluate_predicate_recursively on it, with a different original trait ref used in the original query.
• Using EvaluatedToOkModuloRegions instead of EvaluatedToOk only seems to cause an error when it results in the incremental hash changing (I don't know if it's possible to weaponize this into extending a lifetime).

As a result, I haven't been able to minimize this.

[Aaron1011]

With #83007 landing, this is going to start causing ICEs (since the query result is actually changing across compilatioon sessions). I'm still not sure if this can actually cause unsoundness, but it should be fixed anyway, since it's a bug in a pretty subtle part of the trait system.

cc @eddyb @matthewjasper - I'm not familiar enough with the relevant code to be sure of how to fix this.

[Aaron1011]

This can be reproduced by following the instructions in #82920 after #83007 lands - it turns out that that reproducer also hits this issue. Unfortunately, that reproducer is quite large, and I'm not sure how to minimize it.

[eddyb]

I wouldn't know where to look (or rather, I only know the vague shape of all of this, but not enough details) and would defer to @nikomatsakis or @matthewjasper, myself.

The only thing I can think of is we should blanket use EvaluatedToOkModuloRegions any time freshening erased a lifetime.

[KalitaAlexey]

The same issue happens on https://github.com/substrate-developer-hub/substrate-node-template.

[Aaron1011]

@lqd managed to create a minimized reproducer in #83115 (comment):

pub trait Interner {
    type InternedVariableKinds;
}

trait RustIrDatabase<I: Interner> {
    fn associated_ty_data(&self) -> AssociatedTyDatum<I>;
    fn impl_datum(&self) -> ImplDatum<I>;
}

trait Fold<I: Interner> {
    type Result;
}
impl<T, I: Interner> Fold<I> for Binders<T>
where
    T: HasInterner<Interner = I> + Fold<I>,
    <T as Fold<I>>::Result: HasInterner<Interner = I>,
    I: Interner,
{
    type Result = Binders<T::Result>;
}
impl<I: Interner> Fold<I> for WhereClause<I> {
    type Result = Binders<WhereClause<I>>;
}

trait HasInterner {
    type Interner: Interner;
}
impl<T: HasInterner> HasInterner for Vec<T> {
    type Interner = T::Interner;
}
impl<T: HasInterner + ?Sized> HasInterner for &T {
    type Interner = T::Interner;
}

pub struct VariableKind<I: Interner> {
    _marker: std::marker::PhantomData<I>,
}

struct VariableKinds<I: Interner> {
    _interned: I::InternedVariableKinds,
}

struct WhereClause<I: Interner> {
    _marker: std::marker::PhantomData<I>,
}
impl<I: Interner> HasInterner for WhereClause<I> {
    type Interner = I;
}

struct Binders<T> {
    _marker: std::marker::PhantomData<T>,
}
impl<T: HasInterner> HasInterner for Binders<T> {
    type Interner = T::Interner;
}
impl<T> Binders<&T> {
    fn cloned(self) -> Binders<T> {
        unimplemented!()
    }
}
impl<T: HasInterner> Binders<T> {
    fn map_ref<'a, U, OP>(&'a self, _op: OP) -> Binders<U>
    where
        OP: FnOnce(&'a T) -> U,
        U: HasInterner<Interner = T::Interner>,
    {
        unimplemented!()
    }
}
impl<T, I: Interner> Binders<T>
where
    T: Fold<I> + HasInterner<Interner = I>,
    I: Interner,
{
    fn substitute(self) -> T::Result {
        unimplemented!()
    }
}
impl<V, U> IntoIterator for Binders<V>
where
    V: HasInterner + IntoIterator<Item = U>,
    U: HasInterner<Interner = V::Interner>,
{
    type Item = Binders<U>;
    type IntoIter = BindersIntoIterator<V>;
    fn into_iter(self) -> Self::IntoIter {
        unimplemented!()
    }
}
struct BindersIntoIterator<V: HasInterner> {
    _binders: VariableKinds<V::Interner>,
}
impl<V> Iterator for BindersIntoIterator<V>
where
    V: HasInterner + IntoIterator,
    <V as IntoIterator>::Item: HasInterner<Interner = V::Interner>,
{
    type Item = Binders<<V as IntoIterator>::Item>;
    fn next(&mut self) -> Option<Self::Item> {
        unimplemented!()
    }
}

struct ImplDatum<I: Interner> {
    binders: Binders<ImplDatumBound<I>>,
}
struct ImplDatumBound<I: Interner> {
    where_clauses: Vec<Binders<WhereClause<I>>>,
}
impl<I: Interner> HasInterner for ImplDatumBound<I> {
    type Interner = I;
}

struct AssociatedTyDatum<I: Interner> {
    binders: Binders<AssociatedTyDatumBound<I>>,
}

struct AssociatedTyDatumBound<I: Interner> {
    where_clauses: Vec<Binders<WhereClause<I>>>,
}
impl<I: Interner> HasInterner for AssociatedTyDatumBound<I> {
    type Interner = I;
}

struct ClauseBuilder<'me, I: Interner> {
    db: &'me dyn RustIrDatabase<I>,
}
impl<'me, I: Interner> ClauseBuilder<'me, I> {
    fn new() -> Self {
        unimplemented!()
    }
    fn push_clause(&mut self, _conditions: impl Iterator<Item = Binders<Binders<WhereClause<I>>>>) {
        unimplemented!()
    }
}

pub(crate) struct Forest<I: Interner> {
    _marker: std::marker::PhantomData<I>,
}

impl<I: Interner> Forest<I> {
    fn iter_answers<'f>(&'f self) {
        let builder = &mut ClauseBuilder::<I>::new();
        let impl_datum = builder.db.impl_datum();
        let impl_where_clauses = impl_datum
            .binders
            .map_ref(|b| &b.where_clauses)
            .into_iter()
            .map(|wc| wc.cloned().substitute());
        let associated_ty = builder.db.associated_ty_data();
        let assoc_ty_where_clauses = associated_ty
            .binders
            .map_ref(|b| &b.where_clauses)
            .into_iter()
            .map(|wc| wc.cloned().substitute());
        builder.push_clause(impl_where_clauses.chain(assoc_ty_where_clauses));
    }
}

pub struct SLGSolver {
    pub(crate) forest: Forest<ChalkIr>,
}
impl SLGSolver {
    fn new() -> Self {
        unimplemented!()
    }
    fn solve_multiple(&self) {
        let _answers = self.forest.iter_answers();
    }
}

pub struct ChalkIr;
impl Interner for ChalkIr {
    type InternedVariableKinds = Vec<VariableKind<ChalkIr>>;
}

fn main() {
    let solver = SLGSolver::new();
    solver.solve_multiple();
}