fix: Binding wrong associated type when lowering bounds like `T: Trait<Assoc = U>` #19182

ShoyuVanilla · 2025-02-19T16:19:02Z

Fixes #19177

The panic happens while borrow checking the following function in the mentioned crate
https://github.com/PingPongun/egui_struct/blob/b9549e51491e02a6c471e1cf7a6bd4b77bd87203/src/lib.rs#L774-L779

fn show_combobox<'a, T: Clone + ToString + PartialEq>(
    sel: &mut T,
    ui: &mut Ui,
    config: Option<&'a mut dyn Iterator<Item = T>>,
    id: impl Hash + Clone,
) -> Response {

When lowering trait object dyn Iterator<Item = T> on the following lines

rust-analyzer/crates/hir-ty/src/lower.rs

Lines 693 to 704 in 9691da7

    
           fn lower_dyn_trait(&mut self, bounds: &[TypeBound]) -> Ty { 
        
               let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner); 
        
               // INVARIANT: The principal trait bound, if present, must come first. Others may be in any 
        
               // order but should be in the same order for the same set but possibly different order of 
        
               // bounds in the input. 
        
               // INVARIANT: If this function returns `DynTy`, there should be at least one trait bound. 
        
               // These invariants are utilized by `TyExt::dyn_trait()` and chalk. 
        
               let mut lifetime = None; 
        
               let bounds = self.with_shifted_in(DebruijnIndex::ONE, |ctx| { 
        
                   let mut lowered_bounds = Vec::new(); 
        
                   for b in bounds { 
        
                       ctx.lower_type_bound(b, self_ty.clone(), false).for_each(|b| {

on L704, the bound TraitObject: Iterator<Item = T> passed to the following lines

rust-analyzer/crates/hir-ty/src/lower.rs

Lines 647 to 663 in 9691da7

    
           pub(crate) fn lower_type_bound<'b>( 
        
               &'b mut self, 
        
               bound: &'b TypeBound, 
        
               self_ty: Ty, 
        
               ignore_bindings: bool, 
        
           ) -> impl Iterator<Item = QuantifiedWhereClause> + use<'b, 'a> { 
        
               let mut assoc_bounds = None; 
        
               let mut clause = None; 
        
               match bound { 
        
                   &TypeBound::Path(path, TraitBoundModifier::None) | &TypeBound::ForLifetime(_, path) => { 
        
                       // FIXME Don't silently drop the hrtb lifetimes here 
        
                       if let Some((trait_ref, ctx)) = self.lower_trait_ref_from_path(path, self_ty) { 
        
                           if !ignore_bindings { 
        
                               assoc_bounds = 
        
                                   ctx.assoc_type_bindings_from_type_bound(bound, trait_ref.clone()); 
        
                           } 
        
                           clause = Some(crate::wrap_empty_binders(WhereClause::Implemented(trait_ref)));

and then passed to the following function through L661.

rust-analyzer/crates/hir-ty/src/lower/path.rs

Lines 787 to 791 in 9691da7

    
           pub(super) fn assoc_type_bindings_from_type_bound<'c>( 
        
               mut self, 
        
               bound: &'c TypeBound, 
        
               trait_ref: TraitRef, 
        
           ) -> Option<impl Iterator<Item = QuantifiedWhereClause> + use<'a, 'b, 'c>> {

But in that function, while trying to find target_param_idx in the following lines,
(note that the problematic behaviour happens only when target is WherePredicateTypeTarget::TypeOrConstParam in L844, which means we have desugared impl Trait generic type as a function's parameter type)

rust-analyzer/crates/hir-ty/src/lower/path.rs

Lines 840 to 846 in 9691da7

    
           let target_param_idx = 
        
               self.ctx.resolver.where_predicates_in_scope().find_map(|(p, _)| { 
        
                   match p { 
        
                       WherePredicate::TypeBound { 
        
                           target: WherePredicateTypeTarget::TypeOrConstParam(idx), 
        
                           bound: b, 
        
                       } if b == bound => Some(idx),

we check whether the two type bounds are equal(b == bound) with <TypeBound as PartialEq>::Eq

However, the TypeBounds is somewhat like a local pointer bound to the TypesMap that contains the actual TypeRef it is pointing out(the PathId is actually Idx<TypeRef>

rust-analyzer/crates/hir-def/src/hir/type_ref.rs

Lines 253 to 260 in 9691da7

    
           #[derive(Clone, PartialEq, Eq, Hash, Debug)] 
        
           pub enum TypeBound { 
        
               Path(PathId, TraitBoundModifier), 
        
               ForLifetime(Box<[Name]>, PathId), 
        
               Lifetime(LifetimeRef), 
        
               Use(Box<[UseArgRef]>), 
        
               Error, 
        
           }

and if bound and b are from two different TypesMap but have the same Idx, our associated type in trait ref bound is bound to a wrong parameter, and this caused panic inside chalk.

Adding equality check for two TypeBounds' provenance TypesMap fixes this issue, but I'm so scared because similar "Local Idx comparison between different Arenas" might be happening somewhere in our codebase 😨

ShoyuVanilla · 2025-02-19T16:22:12Z

crates/hir-ty/src/mir/eval/tests.rs

+) {
+}
+"#,
+        |e| matches!(e, MirEvalError::MirLowerError(_, MirLowerError::GenericArgNotProvided(..))),


Since the mir evaluation does mir lowering and then mir monomorphizing, this makes panics without the fix in this PR, in the process of solving "x is Copy?" goals while borrowck

ChayimFriedman2 · 2025-02-19T20:12:24Z

crates/hir-ty/src/lower/path.rs

+                                    WherePredicate::TypeBound {
+                                        target: WherePredicateTypeTarget::TypeOrConstParam(idx),
+                                        bound: b,
+                                    } if b == bound && self.ctx.types_map == types_map => Some(idx),


This seems like it would do a deep comparison of the type map, which is expensive. Is it possible to make a pointer comparison?

ChayimFriedman2

I also fear there are other instances of this pattern, but I can't think of an idea to solve it generally, nor can I think how to solve this more elegantly (comparing the types map is a bit weird).

ShoyuVanilla · 2025-02-22T21:44:13Z

I agree with you that comparing the type maps feels weird. I considered comparing the actual TyRefs inside the map instead, but that also seems problematic, as non-lowered TyRefs can semantically refer to different things. That said, I doubt this issue arises in the code I modified in this PR 😅.
Anyway, I chose to compare the maps to enforce a stricter "same origin" policy.

fix: Binding wrong assoc ty when lowering trait ref bound

9d459e8

rustbot added the S-waiting-on-review Status: Awaiting review from the assignee but also interested parties. label Feb 19, 2025

ShoyuVanilla commented Feb 19, 2025

View reviewed changes

ShoyuVanilla mentioned this pull request Feb 19, 2025

Usage of Idx without its containing Arena context might be a footgun #19183

Open

ChayimFriedman2 reviewed Feb 19, 2025

View reviewed changes

Explicitly compare TypesMap as ptrs

a82773a

ChayimFriedman2 approved these changes Feb 22, 2025

View reviewed changes

ChayimFriedman2 added this pull request to the merge queue Feb 22, 2025

Merged via the queue into rust-lang:master with commit 9df88ff Feb 22, 2025
9 checks passed

ShoyuVanilla deleted the issue-19177 branch February 22, 2025 22:21

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix: Binding wrong associated type when lowering bounds like `T: Trait<Assoc = U>` #19182

fix: Binding wrong associated type when lowering bounds like `T: Trait<Assoc = U>` #19182

ShoyuVanilla commented Feb 19, 2025

ShoyuVanilla Feb 19, 2025

ChayimFriedman2 Feb 19, 2025 •

edited

Loading

ChayimFriedman2 left a comment

ShoyuVanilla commented Feb 22, 2025

	fn lower_dyn_trait(&mut self, bounds: &[TypeBound]) -> Ty {
	let self_ty = TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(Interner);
	// INVARIANT: The principal trait bound, if present, must come first. Others may be in any
	// order but should be in the same order for the same set but possibly different order of
	// bounds in the input.
	// INVARIANT: If this function returns `DynTy`, there should be at least one trait bound.
	// These invariants are utilized by `TyExt::dyn_trait()` and chalk.
	let mut lifetime = None;
	let bounds = self.with_shifted_in(DebruijnIndex::ONE, \|ctx\| {
	let mut lowered_bounds = Vec::new();
	for b in bounds {
	ctx.lower_type_bound(b, self_ty.clone(), false).for_each(\|b\| {

	pub(crate) fn lower_type_bound<'b>(
	&'b mut self,
	bound: &'b TypeBound,
	self_ty: Ty,
	ignore_bindings: bool,
	) -> impl Iterator<Item = QuantifiedWhereClause> + use<'b, 'a> {
	let mut assoc_bounds = None;
	let mut clause = None;
	match bound {
	&TypeBound::Path(path, TraitBoundModifier::None) \| &TypeBound::ForLifetime(_, path) => {
	// FIXME Don't silently drop the hrtb lifetimes here
	if let Some((trait_ref, ctx)) = self.lower_trait_ref_from_path(path, self_ty) {
	if !ignore_bindings {
	assoc_bounds =
	ctx.assoc_type_bindings_from_type_bound(bound, trait_ref.clone());
	}
	clause = Some(crate::wrap_empty_binders(WhereClause::Implemented(trait_ref)));

	pub(super) fn assoc_type_bindings_from_type_bound<'c>(
	mut self,
	bound: &'c TypeBound,
	trait_ref: TraitRef,
	) -> Option<impl Iterator<Item = QuantifiedWhereClause> + use<'a, 'b, 'c>> {

	let target_param_idx =
	self.ctx.resolver.where_predicates_in_scope().find_map(\|(p, _)\| {
	match p {
	WherePredicate::TypeBound {
	target: WherePredicateTypeTarget::TypeOrConstParam(idx),
	bound: b,
	} if b == bound => Some(idx),

	#[derive(Clone, PartialEq, Eq, Hash, Debug)]
	pub enum TypeBound {
	Path(PathId, TraitBoundModifier),
	ForLifetime(Box<[Name]>, PathId),
	Lifetime(LifetimeRef),
	Use(Box<[UseArgRef]>),
	Error,
	}

fix: Binding wrong associated type when lowering bounds like T: Trait<Assoc = U> #19182

fix: Binding wrong associated type when lowering bounds like T: Trait<Assoc = U> #19182

Conversation

ShoyuVanilla commented Feb 19, 2025

ShoyuVanilla Feb 19, 2025

Choose a reason for hiding this comment

ChayimFriedman2 Feb 19, 2025 • edited Loading

Choose a reason for hiding this comment

ChayimFriedman2 left a comment

Choose a reason for hiding this comment

ShoyuVanilla commented Feb 22, 2025

fix: Binding wrong associated type when lowering bounds like `T: Trait<Assoc = U>` #19182

fix: Binding wrong associated type when lowering bounds like `T: Trait<Assoc = U>` #19182

ChayimFriedman2 Feb 19, 2025 •

edited

Loading