vendor/chalk-solve-0.80.0/src/clauses/builtin_traits/unsize.rs

   1 use std::collections::HashSet;
   2 use std::iter;
   3 use std::ops::ControlFlow;
   4
   5 use crate::clauses::ClauseBuilder;
   6 use crate::rust_ir::AdtKind;
   7 use crate::{Interner, RustIrDatabase, TraitRef, WellKnownTrait};
   8 use chalk_ir::{
   9     cast::Cast,
  10     interner::HasInterner,
  11     visit::{SuperVisit, Visit, Visitor},
  12     Binders, Const, ConstValue, DebruijnIndex, DomainGoal, DynTy, EqGoal, Goal, LifetimeOutlives,
  13     QuantifiedWhereClauses, Substitution, TraitId, Ty, TyKind, TypeOutlives, WhereClause,
  14 };
  15
  16 struct UnsizeParameterCollector<I: Interner> {
  17     interner: I,
  18     // FIXME should probably use a bitset instead
  19     parameters: HashSet<usize>,
  20 }
  21
  22 impl<I: Interner> Visitor<I> for UnsizeParameterCollector<I> {
  23     type BreakTy = ();
  24
  25     fn as_dyn(&mut self) -> &mut dyn Visitor<I, BreakTy = Self::BreakTy> {
  26         self
  27     }
  28
  29     fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
  30         let interner = self.interner;
  31
  32         match ty.kind(interner) {
  33             TyKind::BoundVar(bound_var) => {
  34                 // check if bound var refers to the outermost binder
  35                 if bound_var.debruijn.shifted_in() == outer_binder {
  36                     self.parameters.insert(bound_var.index);
  37                 }
  38                 ControlFlow::Continue(())
  39             }
  40             _ => ty.super_visit_with(self, outer_binder),
  41         }
  42     }
  43
  44     fn visit_const(&mut self, constant: &Const<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
  45         let interner = self.interner;
  46
  47         if let ConstValue::BoundVar(bound_var) = constant.data(interner).value {
  48             // check if bound var refers to the outermost binder
  49             if bound_var.debruijn.shifted_in() == outer_binder {
  50                 self.parameters.insert(bound_var.index);
  51             }
  52         }
  53         ControlFlow::Continue(())
  54     }
  55
  56     fn interner(&self) -> I {
  57         self.interner
  58     }
  59 }
  60
  61 fn outer_binder_parameters_used<I: Interner>(
  62     interner: I,
  63     v: &Binders<impl Visit<I> + HasInterner>,
  64 ) -> HashSet<usize> {
  65     let mut visitor = UnsizeParameterCollector {
  66         interner,
  67         parameters: HashSet::new(),
  68     };
  69     v.visit_with(&mut visitor, DebruijnIndex::INNERMOST);
  70     visitor.parameters
  71 }
  72
  73 // has nothing to do with occurs check
  74 struct ParameterOccurenceCheck<'p, I: Interner> {
  75     interner: I,
  76     parameters: &'p HashSet<usize>,
  77 }
  78
  79 impl<'p, I: Interner> Visitor<I> for ParameterOccurenceCheck<'p, I> {
  80     type BreakTy = ();
  81
  82     fn as_dyn(&mut self) -> &mut dyn Visitor<I, BreakTy = Self::BreakTy> {
  83         self
  84     }
  85
  86     fn visit_ty(&mut self, ty: &Ty<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
  87         let interner = self.interner;
  88
  89         match ty.kind(interner) {
  90             TyKind::BoundVar(bound_var) => {
  91                 if bound_var.debruijn.shifted_in() == outer_binder
  92                     && self.parameters.contains(&bound_var.index)
  93                 {
  94                     ControlFlow::Break(())
  95                 } else {
  96                     ControlFlow::Continue(())
  97                 }
  98             }
  99             _ => ty.super_visit_with(self, outer_binder),
 100         }
 101     }
 102
 103     fn visit_const(&mut self, constant: &Const<I>, outer_binder: DebruijnIndex) -> ControlFlow<()> {
 104         let interner = self.interner;
 105
 106         match constant.data(interner).value {
 107             ConstValue::BoundVar(bound_var) => {
 108                 if bound_var.debruijn.shifted_in() == outer_binder
 109                     && self.parameters.contains(&bound_var.index)
 110                 {
 111                     ControlFlow::Break(())
 112                 } else {
 113                     ControlFlow::Continue(())
 114                 }
 115             }
 116             _ => ControlFlow::Continue(()),
 117         }
 118     }
 119
 120     fn interner(&self) -> I {
 121         self.interner
 122     }
 123 }
 124
 125 fn uses_outer_binder_params<I: Interner>(
 126     interner: I,
 127     v: &Binders<impl Visit<I> + HasInterner>,
 128     parameters: &HashSet<usize>,
 129 ) -> bool {
 130     let mut visitor = ParameterOccurenceCheck {
 131         interner,
 132         parameters,
 133     };
 134
 135     let flow = v.visit_with(&mut visitor, DebruijnIndex::INNERMOST);
 136     matches!(flow, ControlFlow::Break(_))
 137 }
 138
 139 fn principal_id<I: Interner>(
 140     db: &dyn RustIrDatabase<I>,
 141     bounds: &Binders<QuantifiedWhereClauses<I>>,
 142 ) -> Option<TraitId<I>> {
 143     let interner = db.interner();
 144
 145     bounds
 146         .skip_binders()
 147         .iter(interner)
 148         .filter_map(|b| b.trait_id())
 149         .find(|&id| !db.trait_datum(id).is_auto_trait())
 150 }
 151
 152 fn auto_trait_ids<'a, I: Interner>(
 153     db: &'a dyn RustIrDatabase<I>,
 154     bounds: &'a Binders<QuantifiedWhereClauses<I>>,
 155 ) -> impl Iterator<Item = TraitId<I>> + 'a {
 156     let interner = db.interner();
 157
 158     bounds
 159         .skip_binders()
 160         .iter(interner)
 161         .filter_map(|clause| clause.trait_id())
 162         .filter(move |&id| db.trait_datum(id).is_auto_trait())
 163 }
 164
 165 pub fn add_unsize_program_clauses<I: Interner>(
 166     db: &dyn RustIrDatabase<I>,
 167     builder: &mut ClauseBuilder<'_, I>,
 168     trait_ref: TraitRef<I>,
 169     _ty: TyKind<I>,
 170 ) {
 171     let interner = db.interner();
 172
 173     let source_ty = trait_ref.self_type_parameter(interner);
 174     let target_ty = trait_ref
 175         .substitution
 176         .at(interner, 1)
 177         .assert_ty_ref(interner)
 178         .clone();
 179
 180     let unsize_trait_id = trait_ref.trait_id;
 181
 182     // N.B. here rustc asserts that `TraitRef` is not a higher-ranked bound
 183     // i.e. `for<'a> &'a T: Unsize<dyn Trait+'a>` is never provable.
 184     //
 185     // In chalk it would be awkward to implement and I am not sure
 186     // there is a need for it, the original comment states that this restriction
 187     // could be lifted.
 188     //
 189     // for more info visit `fn assemble_candidates_for_unsizing` and
 190     // `fn confirm_builtin_unisize_candidate` in rustc.
 191
 192     match (source_ty.kind(interner), target_ty.kind(interner)) {
 193         // dyn Trait + AutoX + 'a -> dyn Trait + AutoY + 'b
 194         (
 195             TyKind::Dyn(DynTy {
 196                 bounds: bounds_a,
 197                 lifetime: lifetime_a,
 198             }),
 199             TyKind::Dyn(DynTy {
 200                 bounds: bounds_b,
 201                 lifetime: lifetime_b,
 202             }),
 203         ) => {
 204             let principal_a = principal_id(db, bounds_a);
 205             let principal_b = principal_id(db, bounds_b);
 206
 207             let auto_trait_ids_a: Vec<_> = auto_trait_ids(db, bounds_a).collect();
 208             let auto_trait_ids_b: Vec<_> = auto_trait_ids(db, bounds_b).collect();
 209
 210             let may_apply = principal_a == principal_b
 211                 && auto_trait_ids_b
 212                     .iter()
 213                     .all(|id_b| auto_trait_ids_a.iter().any(|id_a| id_a == id_b));
 214
 215             if !may_apply {
 216                 return;
 217             }
 218
 219             // COMMENT FROM RUSTC:
 220             // ------------------
 221             // Require that the traits involved in this upcast are **equal**;
 222             // only the **lifetime bound** is changed.
 223             //
 224             // This condition is arguably too strong -- it would
 225             // suffice for the source trait to be a *subtype* of the target
 226             // trait. In particular, changing from something like
 227             // `for<'a, 'b> Foo<'a, 'b>` to `for<'a> Foo<'a, 'a>` should be
 228             // permitted.
 229             // <...>
 230             // I've modified this to `.eq` because I want to continue rejecting
 231             // that [`old-lub-glb-object.rs`] test (as we have
 232             // done for quite some time) before we are firmly comfortable
 233             // with what our behavior should be there. -nikomatsakis
 234             // ------------------
 235
 236             // Construct a new trait object type by taking the source ty,
 237             // filtering out auto traits of source that are not present in target
 238             // and changing source lifetime to target lifetime.
 239             //
 240             // In order for the coercion to be valid, this new type
 241             // should be equal to target type.
 242             let new_source_ty = TyKind::Dyn(DynTy {
 243                 bounds: bounds_a.map_ref(|bounds| {
 244                     QuantifiedWhereClauses::from_iter(
 245                         interner,
 246                         bounds.iter(interner).filter(|bound| {
 247                             let trait_id = match bound.trait_id() {
 248                                 Some(id) => id,
 249                                 None => return true,
 250                             };
 251
 252                             if auto_trait_ids_a.iter().all(|&id_a| id_a != trait_id) {
 253                                 return true;
 254                             }
 255                             auto_trait_ids_b.iter().any(|&id_b| id_b == trait_id)
 256                         }),
 257                     )
 258                 }),
 259                 lifetime: lifetime_b.clone(),
 260             })
 261             .intern(interner);
 262
 263             // Check that new source is equal to target
 264             let eq_goal = EqGoal {
 265                 a: new_source_ty.cast(interner),
 266                 b: target_ty.clone().cast(interner),
 267             }
 268             .cast(interner);
 269
 270             // Check that source lifetime outlives target lifetime
 271             let lifetime_outlives_goal: Goal<I> = WhereClause::LifetimeOutlives(LifetimeOutlives {
 272                 a: lifetime_a.clone(),
 273                 b: lifetime_b.clone(),
 274             })
 275             .cast(interner);
 276
 277             builder.push_clause(trait_ref, [eq_goal, lifetime_outlives_goal].iter());
 278         }
 279
 280         // T -> dyn Trait + 'a
 281         (_, TyKind::Dyn(DynTy { bounds, lifetime })) => {
 282             // Check if all traits in trait object are object safe
 283             let object_safe_goals = bounds
 284                 .skip_binders()
 285                 .iter(interner)
 286                 .filter_map(|bound| bound.trait_id())
 287                 .map(|id| DomainGoal::ObjectSafe(id).cast(interner));
 288
 289             // Check that T implements all traits of the trait object
 290             let source_ty_bounds = bounds
 291                 .clone()
 292                 .substitute(interner, &Substitution::from1(interner, source_ty.clone()));
 293
 294             // Check that T is sized because we can only make
 295             // a trait object from a sized type
 296             let self_sized_goal: WhereClause<_> = TraitRef {
 297                 trait_id: db
 298                     .well_known_trait_id(WellKnownTrait::Sized)
 299                     .expect("Expected Sized to be defined when proving Unsize"),
 300                 substitution: Substitution::from1(interner, source_ty.clone()),
 301             }
 302             .cast(interner);
 303
 304             // Check that `source_ty` outlives `'a`
 305             let source_ty_outlives: Goal<_> = WhereClause::TypeOutlives(TypeOutlives {
 306                 ty: source_ty,
 307                 lifetime: lifetime.clone(),
 308             })
 309             .cast(interner);
 310
 311             builder.push_clause(
 312                 trait_ref,
 313                 source_ty_bounds
 314                     .iter(interner)
 315                     .map(|bound| bound.clone().cast::<Goal<I>>(interner))
 316                     .chain(object_safe_goals)
 317                     .chain(iter::once(self_sized_goal.cast(interner)))
 318                     .chain(iter::once(source_ty_outlives)),
 319             );
 320         }
 321
 322         (TyKind::Array(array_ty, _array_const), TyKind::Slice(slice_ty)) => {
 323             let eq_goal = EqGoal {
 324                 a: array_ty.clone().cast(interner),
 325                 b: slice_ty.clone().cast(interner),
 326             };
 327
 328             builder.push_clause(trait_ref, iter::once(eq_goal));
 329         }
 330
 331         // Adt<T> -> Adt<U>
 332         (TyKind::Adt(adt_id_a, substitution_a), TyKind::Adt(adt_id_b, substitution_b)) => {
 333             if adt_id_a != adt_id_b {
 334                 return;
 335             }
 336
 337             let adt_id = *adt_id_a;
 338             let adt_datum = db.adt_datum(adt_id);
 339
 340             // Unsizing of enums is not allowed
 341             if adt_datum.kind == AdtKind::Enum {
 342                 return;
 343             }
 344
 345             // We have a `struct` so we're guaranteed a single variant
 346             let fields_len = adt_datum
 347                 .binders
 348                 .skip_binders()
 349                 .variants
 350                 .last()
 351                 .unwrap()
 352                 .fields
 353                 .len();
 354
 355             if fields_len == 0 {
 356                 return;
 357             }
 358
 359             let adt_tail_field = adt_datum
 360                 .binders
 361                 .map_ref(|bound| bound.variants.last().unwrap().fields.last().unwrap())
 362                 .cloned();
 363
 364             // Collect unsize parameters that last field contains and
 365             // ensure there at least one of them.
 366             let unsize_parameter_candidates =
 367                 outer_binder_parameters_used(interner, &adt_tail_field);
 368
 369             if unsize_parameter_candidates.is_empty() {
 370                 return;
 371             }
 372             // Ensure none of the other fields mention the parameters used
 373             // in unsizing.
 374             // We specifically want variables specified by the outermost binder
 375             // i.e. the struct generic arguments binder.
 376             if uses_outer_binder_params(
 377                 interner,
 378                 &adt_datum
 379                     .binders
 380                     .map_ref(|bound| &bound.variants.last().unwrap().fields[..fields_len - 1]),
 381                 &unsize_parameter_candidates,
 382             ) {
 383                 return;
 384             }
 385
 386             let parameters_a = substitution_a.as_slice(interner);
 387             let parameters_b = substitution_b.as_slice(interner);
 388             // Check that the source adt with the target's
 389             // unsizing parameters is equal to the target.
 390             // We construct a new substitution where if a parameter is used in the
 391             // coercion (i.e. it's a non-lifetime struct parameter used by it's last field),
 392             // then we take that parameter from target substitution, otherwise we take
 393             // it from the source substitution.
 394             //
 395             // In order for the coercion to be valid, target struct and
 396             // struct with this newly constructed substitution applied to it should be equal.
 397             let substitution = Substitution::from_iter(
 398                 interner,
 399                 parameters_a.iter().enumerate().map(|(i, p)| {
 400                     if unsize_parameter_candidates.contains(&i) {
 401                         &parameters_b[i]
 402                     } else {
 403                         p
 404                     }
 405                 }),
 406             );
 407
 408             let eq_goal = EqGoal {
 409                 a: TyKind::Adt(adt_id, substitution)
 410                     .intern(interner)
 411                     .cast(interner),
 412                 b: target_ty.clone().cast(interner),
 413             }
 414             .cast(interner);
 415
 416             // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`.
 417             let source_tail_field = adt_tail_field.clone().substitute(interner, substitution_a);
 418             let target_tail_field = adt_tail_field.substitute(interner, substitution_b);
 419
 420             // Check that `TailField<T>: Unsize<TailField<U>>`
 421             let last_field_unsizing_goal: Goal<I> = TraitRef {
 422                 trait_id: unsize_trait_id,
 423                 substitution: Substitution::from_iter(
 424                     interner,
 425                     [source_tail_field, target_tail_field].iter().cloned(),
 426                 ),
 427             }
 428             .cast(interner);
 429
 430             builder.push_clause(trait_ref, [eq_goal, last_field_unsizing_goal].iter());
 431         }
 432
 433         // (.., T) -> (.., U)
 434         (TyKind::Tuple(arity_a, substitution_a), TyKind::Tuple(arity_b, substitution_b)) => {
 435             if arity_a != arity_b || *arity_a == 0 {
 436                 return;
 437             }
 438             let arity = arity_a;
 439
 440             let tail_ty_a = substitution_a.iter(interner).last().unwrap();
 441             let tail_ty_b = substitution_b.iter(interner).last().unwrap();
 442
 443             // Check that the source tuple with the target's
 444             // last element is equal to the target.
 445             let new_tuple = TyKind::Tuple(
 446                 *arity,
 447                 Substitution::from_iter(
 448                     interner,
 449                     substitution_a
 450                         .iter(interner)
 451                         .take(arity - 1)
 452                         .chain(iter::once(tail_ty_b)),
 453                 ),
 454             )
 455             .cast(interner)
 456             .intern(interner);
 457
 458             let eq_goal: Goal<I> = EqGoal {
 459                 a: new_tuple.cast(interner),
 460                 b: target_ty.clone().cast(interner),
 461             }
 462             .cast(interner);
 463
 464             // Check that `T: Unsize<U>`
 465             let last_field_unsizing_goal: Goal<I> = TraitRef {
 466                 trait_id: unsize_trait_id,
 467                 substitution: Substitution::from_iter(
 468                     interner,
 469                     [tail_ty_a, tail_ty_b].iter().cloned(),
 470                 ),
 471             }
 472             .cast(interner);
 473
 474             builder.push_clause(trait_ref, [eq_goal, last_field_unsizing_goal].iter());
 475         }
 476
 477         _ => (),
 478     }
 479 }