vendor/chalk-solve-0.25.0/src/split.rs

   1 use crate::rust_ir::*;
   2 use crate::RustIrDatabase;
   3 use chalk_ir::interner::Interner;
   4 use chalk_ir::*;
   5 use std::sync::Arc;
   6 use tracing::{debug, instrument};
   7
   8 /// Methods for splitting up the projections for associated types from
   9 /// the surrounding context.
  10 pub trait Split<I: Interner>: RustIrDatabase<I> {
  11     /// Given a projection of an associated type, split the type
  12     /// parameters into those that come from the *trait* and those
  13     /// that come from the *associated type itself*. So e.g. if you
  14     /// have `(Iterator::Item)<F>`, this would return `([F], [])`,
  15     /// since `Iterator::Item` is not generic and hence doesn't have
  16     /// any type parameters itself.
  17     fn split_projection<'p>(
  18         &self,
  19         projection: &'p ProjectionTy<I>,
  20     ) -> (
  21         Arc<AssociatedTyDatum<I>>,
  22         &'p [GenericArg<I>],
  23         &'p [GenericArg<I>],
  24     ) {
  25         let interner = self.interner();
  26         let ProjectionTy {
  27             associated_ty_id,
  28             ref substitution,
  29         } = *projection;
  30         let parameters = substitution.as_slice(interner);
  31         let associated_ty_data = &self.associated_ty_data(associated_ty_id);
  32         let (trait_params, other_params) =
  33             self.split_associated_ty_parameters(parameters, &**associated_ty_data);
  34         (associated_ty_data.clone(), trait_params, other_params)
  35     }
  36
  37     /// Given a projection `<P0 as Trait<P1..Pn>>::Item<Pn..Pm>`,
  38     /// returns the trait parameters `[P0..Pn]` (see
  39     /// `split_projection`).
  40     fn trait_parameters_from_projection<'p>(
  41         &self,
  42         projection: &'p ProjectionTy<I>,
  43     ) -> &'p [GenericArg<I>] {
  44         let (_, trait_params, _) = self.split_projection(projection);
  45         trait_params
  46     }
  47
  48     /// Given a projection `<P0 as Trait<P1..Pn>>::Item<Pn..Pm>`,
  49     /// returns the trait parameters `[P0..Pn]` (see
  50     /// `split_projection`).
  51     fn trait_ref_from_projection<'p>(&self, projection: &'p ProjectionTy<I>) -> TraitRef<I> {
  52         let interner = self.interner();
  53         let (associated_ty_data, trait_params, _) = self.split_projection(&projection);
  54         TraitRef {
  55             trait_id: associated_ty_data.trait_id,
  56             substitution: Substitution::from_iter(interner, trait_params),
  57         }
  58     }
  59
  60     /// Given the full set of parameters (or binders) for an
  61     /// associated type *value* (which appears in an impl), splits
  62     /// them into the substitutions for the *impl* and those for the
  63     /// *associated type*.
  64     ///
  65     /// # Example
  66     ///
  67     /// ```ignore (example)
  68     /// impl<T> Iterable for Vec<T> {
  69     ///     type Iter<'a>;
  70     /// }
  71     /// ```
  72     ///
  73     /// in this example, the full set of parameters would be `['x,
  74     /// Y]`, where `'x` is the value for `'a` and `Y` is the value for
  75     /// `T`.
  76     ///
  77     /// # Returns
  78     ///
  79     /// Returns the pair of:
  80     ///
  81     /// * the parameters for the impl (`[Y]`, in our example)
  82     /// * the parameters for the associated type value (`['a]`, in our example)
  83     fn split_associated_ty_value_parameters<'p, P>(
  84         &self,
  85         parameters: &'p [P],
  86         associated_ty_value: &AssociatedTyValue<I>,
  87     ) -> (&'p [P], &'p [P]) {
  88         let interner = self.interner();
  89         let impl_datum = self.impl_datum(associated_ty_value.impl_id);
  90         let impl_params_len = impl_datum.binders.len(interner);
  91         assert!(parameters.len() >= impl_params_len);
  92
  93         // the impl parameters are a suffix
  94         //
  95         // [ P0..Pn, Pn...Pm ]
  96         //           ^^^^^^^ impl parameters
  97         let split_point = parameters.len() - impl_params_len;
  98         let (other_params, impl_params) = parameters.split_at(split_point);
  99         (impl_params, other_params)
 100     }
 101
 102     /// Given the full set of parameters for an associated type *value*
 103     /// (which appears in an impl), returns the trait reference
 104     /// and projection that are being satisfied by that value.
 105     ///
 106     /// # Example
 107     ///
 108     /// ```ignore (example)
 109     /// impl<T> Iterable for Vec<T> {
 110     ///     type Iter<'a>;
 111     /// }
 112     /// ```
 113     ///
 114     /// Here we expect the full set of parameters for `Iter`, which
 115     /// would be `['x, Y]`, where `'x` is the value for `'a` and `Y`
 116     /// is the value for `T`.
 117     ///
 118     /// Returns the pair of:
 119     ///
 120     /// * the parameters that apply to the impl (`Y`, in our example)
 121     /// * the projection `<Vec<Y> as Iterable>::Iter<'x>`
 122     #[instrument(level = "debug", skip(self, associated_ty_value))]
 123     fn impl_parameters_and_projection_from_associated_ty_value<'p>(
 124         &self,
 125         parameters: &'p [GenericArg<I>],
 126         associated_ty_value: &AssociatedTyValue<I>,
 127     ) -> (&'p [GenericArg<I>], ProjectionTy<I>) {
 128         let interner = self.interner();
 129
 130         let impl_datum = self.impl_datum(associated_ty_value.impl_id);
 131
 132         // Get the trait ref from the impl -- so in our example above
 133         // this would be `Box<!T>: Foo`.
 134         let (impl_parameters, atv_parameters) =
 135             self.split_associated_ty_value_parameters(&parameters, associated_ty_value);
 136         let trait_ref = {
 137             let opaque_ty_ref = impl_datum.binders.map_ref(|b| &b.trait_ref);
 138             debug!(?opaque_ty_ref);
 139             opaque_ty_ref.substitute(interner, impl_parameters)
 140         };
 141
 142         // Create the parameters for the projection -- in our example
 143         // above, this would be `['!a, Box<!T>]`, corresponding to
 144         // `<Box<!T> as Foo>::Item<'!a>`
 145         let projection_substitution = Substitution::from_iter(
 146             interner,
 147             atv_parameters
 148                 .iter()
 149                 .chain(trait_ref.substitution.iter(interner))
 150                 .cloned(),
 151         );
 152
 153         let projection = ProjectionTy {
 154             associated_ty_id: associated_ty_value.associated_ty_id,
 155             substitution: projection_substitution,
 156         };
 157
 158         debug!(?impl_parameters, ?trait_ref, ?projection);
 159
 160         (impl_parameters, projection)
 161     }
 162
 163     /// Given the full set of parameters (or binders) for an
 164     /// associated type datum (the one appearing in a trait), splits
 165     /// them into the parameters for the *trait* and those for the
 166     /// *associated type*.
 167     ///
 168     /// # Example
 169     ///
 170     /// ```ignore (example)
 171     /// trait Foo<T> {
 172     ///     type Assoc<'a>;
 173     /// }
 174     /// ```
 175     ///
 176     /// in this example, the full set of parameters would be `['x,
 177     /// Y]`, where `'x` is the value for `'a` and `Y` is the value for
 178     /// `T`.
 179     ///
 180     /// # Returns
 181     ///
 182     /// Returns the tuple of:
 183     ///
 184     /// * the parameters for the impl (`[Y]`, in our example)
 185     /// * the parameters for the associated type value (`['a]`, in our example)
 186     fn split_associated_ty_parameters<'p, P>(
 187         &self,
 188         parameters: &'p [P],
 189         associated_ty_datum: &AssociatedTyDatum<I>,
 190     ) -> (&'p [P], &'p [P]) {
 191         let trait_datum = &self.trait_datum(associated_ty_datum.trait_id);
 192         let trait_num_params = trait_datum.binders.len(self.interner());
 193         let split_point = parameters.len() - trait_num_params;
 194         let (other_params, trait_params) = parameters.split_at(split_point);
 195         (trait_params, other_params)
 196     }
 197 }
 198
 199 impl<DB: RustIrDatabase<I> + ?Sized, I: Interner> Split<I> for DB {}