src/librustc/traits/query.rs

   1 //! Experimental types for the trait query interface. The methods
   2 //! defined in this module are all based on **canonicalization**,
   3 //! which makes a canonical query by replacing unbound inference
   4 //! variables and regions, so that results can be reused more broadly.
   5 //! The providers for the queries defined here can be found in
   6 //! `librustc_traits`.
   7
   8 use crate::ich::StableHashingContext;
   9 use crate::infer::canonical::{Canonical, QueryResponse};
  10 use crate::ty::error::TypeError;
  11 use crate::ty::subst::GenericArg;
  12 use crate::ty::{self, Ty, TyCtxt};
  13
  14 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
  15 use rustc_data_structures::sync::Lrc;
  16 use rustc_errors::struct_span_err;
  17 use rustc_span::source_map::Span;
  18 use std::iter::FromIterator;
  19 use std::mem;
  20
  21 pub mod type_op {
  22     use crate::ty::fold::TypeFoldable;
  23     use crate::ty::subst::UserSubsts;
  24     use crate::ty::{Predicate, Ty};
  25     use rustc_hir::def_id::DefId;
  26     use std::fmt;
  27
  28     #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, Lift)]
  29     pub struct AscribeUserType<'tcx> {
  30         pub mir_ty: Ty<'tcx>,
  31         pub def_id: DefId,
  32         pub user_substs: UserSubsts<'tcx>,
  33     }
  34
  35     impl<'tcx> AscribeUserType<'tcx> {
  36         pub fn new(mir_ty: Ty<'tcx>, def_id: DefId, user_substs: UserSubsts<'tcx>) -> Self {
  37             Self { mir_ty, def_id, user_substs }
  38         }
  39     }
  40
  41     #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, Lift)]
  42     pub struct Eq<'tcx> {
  43         pub a: Ty<'tcx>,
  44         pub b: Ty<'tcx>,
  45     }
  46
  47     impl<'tcx> Eq<'tcx> {
  48         pub fn new(a: Ty<'tcx>, b: Ty<'tcx>) -> Self {
  49             Self { a, b }
  50         }
  51     }
  52
  53     #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, Lift)]
  54     pub struct Subtype<'tcx> {
  55         pub sub: Ty<'tcx>,
  56         pub sup: Ty<'tcx>,
  57     }
  58
  59     impl<'tcx> Subtype<'tcx> {
  60         pub fn new(sub: Ty<'tcx>, sup: Ty<'tcx>) -> Self {
  61             Self { sub, sup }
  62         }
  63     }
  64
  65     #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, Lift)]
  66     pub struct ProvePredicate<'tcx> {
  67         pub predicate: Predicate<'tcx>,
  68     }
  69
  70     impl<'tcx> ProvePredicate<'tcx> {
  71         pub fn new(predicate: Predicate<'tcx>) -> Self {
  72             ProvePredicate { predicate }
  73         }
  74     }
  75
  76     #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, Lift)]
  77     pub struct Normalize<T> {
  78         pub value: T,
  79     }
  80
  81     impl<'tcx, T> Normalize<T>
  82     where
  83         T: fmt::Debug + TypeFoldable<'tcx>,
  84     {
  85         pub fn new(value: T) -> Self {
  86             Self { value }
  87         }
  88     }
  89 }
  90
  91 pub type CanonicalProjectionGoal<'tcx> =
  92     Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>>>;
  93
  94 pub type CanonicalTyGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Ty<'tcx>>>;
  95
  96 pub type CanonicalPredicateGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>>;
  97
  98 pub type CanonicalTypeOpAscribeUserTypeGoal<'tcx> =
  99     Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::AscribeUserType<'tcx>>>;
 100
 101 pub type CanonicalTypeOpEqGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Eq<'tcx>>>;
 102
 103 pub type CanonicalTypeOpSubtypeGoal<'tcx> =
 104     Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Subtype<'tcx>>>;
 105
 106 pub type CanonicalTypeOpProvePredicateGoal<'tcx> =
 107     Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::ProvePredicate<'tcx>>>;
 108
 109 pub type CanonicalTypeOpNormalizeGoal<'tcx, T> =
 110     Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Normalize<T>>>;
 111
 112 #[derive(Clone, Debug, HashStable)]
 113 pub struct NoSolution;
 114
 115 pub type Fallible<T> = Result<T, NoSolution>;
 116
 117 impl<'tcx> From<TypeError<'tcx>> for NoSolution {
 118     fn from(_: TypeError<'tcx>) -> NoSolution {
 119         NoSolution
 120     }
 121 }
 122
 123 #[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
 124 pub struct DropckOutlivesResult<'tcx> {
 125     pub kinds: Vec<GenericArg<'tcx>>,
 126     pub overflows: Vec<Ty<'tcx>>,
 127 }
 128
 129 impl<'tcx> DropckOutlivesResult<'tcx> {
 130     pub fn report_overflows(&self, tcx: TyCtxt<'tcx>, span: Span, ty: Ty<'tcx>) {
 131         if let Some(overflow_ty) = self.overflows.iter().next() {
 132             let mut err = struct_span_err!(
 133                 tcx.sess,
 134                 span,
 135                 E0320,
 136                 "overflow while adding drop-check rules for {}",
 137                 ty,
 138             );
 139             err.note(&format!("overflowed on {}", overflow_ty));
 140             err.emit();
 141         }
 142     }
 143
 144     pub fn into_kinds_reporting_overflows(
 145         self,
 146         tcx: TyCtxt<'tcx>,
 147         span: Span,
 148         ty: Ty<'tcx>,
 149     ) -> Vec<GenericArg<'tcx>> {
 150         self.report_overflows(tcx, span, ty);
 151         let DropckOutlivesResult { kinds, overflows: _ } = self;
 152         kinds
 153     }
 154 }
 155
 156 /// A set of constraints that need to be satisfied in order for
 157 /// a type to be valid for destruction.
 158 #[derive(Clone, Debug, HashStable)]
 159 pub struct DtorckConstraint<'tcx> {
 160     /// Types that are required to be alive in order for this
 161     /// type to be valid for destruction.
 162     pub outlives: Vec<ty::subst::GenericArg<'tcx>>,
 163
 164     /// Types that could not be resolved: projections and params.
 165     pub dtorck_types: Vec<Ty<'tcx>>,
 166
 167     /// If, during the computation of the dtorck constraint, we
 168     /// overflow, that gets recorded here. The caller is expected to
 169     /// report an error.
 170     pub overflows: Vec<Ty<'tcx>>,
 171 }
 172
 173 impl<'tcx> DtorckConstraint<'tcx> {
 174     pub fn empty() -> DtorckConstraint<'tcx> {
 175         DtorckConstraint { outlives: vec![], dtorck_types: vec![], overflows: vec![] }
 176     }
 177 }
 178
 179 impl<'tcx> FromIterator<DtorckConstraint<'tcx>> for DtorckConstraint<'tcx> {
 180     fn from_iter<I: IntoIterator<Item = DtorckConstraint<'tcx>>>(iter: I) -> Self {
 181         let mut result = Self::empty();
 182
 183         for DtorckConstraint { outlives, dtorck_types, overflows } in iter {
 184             result.outlives.extend(outlives);
 185             result.dtorck_types.extend(dtorck_types);
 186             result.overflows.extend(overflows);
 187         }
 188
 189         result
 190     }
 191 }
 192
 193 /// This returns true if the type `ty` is "trivial" for
 194 /// dropck-outlives -- that is, if it doesn't require any types to
 195 /// outlive. This is similar but not *quite* the same as the
 196 /// `needs_drop` test in the compiler already -- that is, for every
 197 /// type T for which this function return true, needs-drop would
 198 /// return `false`. But the reverse does not hold: in particular,
 199 /// `needs_drop` returns false for `PhantomData`, but it is not
 200 /// trivial for dropck-outlives.
 201 ///
 202 /// Note also that `needs_drop` requires a "global" type (i.e., one
 203 /// with erased regions), but this function does not.
 204 pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool {
 205     match ty.kind {
 206         // None of these types have a destructor and hence they do not
 207         // require anything in particular to outlive the dtor's
 208         // execution.
 209         ty::Infer(ty::FreshIntTy(_))
 210         | ty::Infer(ty::FreshFloatTy(_))
 211         | ty::Bool
 212         | ty::Int(_)
 213         | ty::Uint(_)
 214         | ty::Float(_)
 215         | ty::Never
 216         | ty::FnDef(..)
 217         | ty::FnPtr(_)
 218         | ty::Char
 219         | ty::GeneratorWitness(..)
 220         | ty::RawPtr(_)
 221         | ty::Ref(..)
 222         | ty::Str
 223         | ty::Foreign(..)
 224         | ty::Error => true,
 225
 226         // [T; N] and [T] have same properties as T.
 227         ty::Array(ty, _) | ty::Slice(ty) => trivial_dropck_outlives(tcx, ty),
 228
 229         // (T1..Tn) and closures have same properties as T1..Tn --
 230         // check if *any* of those are trivial.
 231         ty::Tuple(ref tys) => tys.iter().all(|t| trivial_dropck_outlives(tcx, t.expect_ty())),
 232         ty::Closure(def_id, ref substs) => {
 233             substs.as_closure().upvar_tys(def_id, tcx).all(|t| trivial_dropck_outlives(tcx, t))
 234         }
 235
 236         ty::Adt(def, _) => {
 237             if Some(def.did) == tcx.lang_items().manually_drop() {
 238                 // `ManuallyDrop` never has a dtor.
 239                 true
 240             } else {
 241                 // Other types might. Moreover, PhantomData doesn't
 242                 // have a dtor, but it is considered to own its
 243                 // content, so it is non-trivial. Unions can have `impl Drop`,
 244                 // and hence are non-trivial as well.
 245                 false
 246             }
 247         }
 248
 249         // The following *might* require a destructor: needs deeper inspection.
 250         ty::Dynamic(..)
 251         | ty::Projection(..)
 252         | ty::Param(_)
 253         | ty::Opaque(..)
 254         | ty::Placeholder(..)
 255         | ty::Infer(_)
 256         | ty::Bound(..)
 257         | ty::Generator(..) => false,
 258
 259         ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
 260     }
 261 }
 262
 263 #[derive(Debug, HashStable)]
 264 pub struct CandidateStep<'tcx> {
 265     pub self_ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>,
 266     pub autoderefs: usize,
 267     /// `true` if the type results from a dereference of a raw pointer.
 268     /// when assembling candidates, we include these steps, but not when
 269     /// picking methods. This so that if we have `foo: *const Foo` and `Foo` has methods
 270     /// `fn by_raw_ptr(self: *const Self)` and `fn by_ref(&self)`, then
 271     /// `foo.by_raw_ptr()` will work and `foo.by_ref()` won't.
 272     pub from_unsafe_deref: bool,
 273     pub unsize: bool,
 274 }
 275
 276 #[derive(Clone, Debug, HashStable)]
 277 pub struct MethodAutoderefStepsResult<'tcx> {
 278     /// The valid autoderef steps that could be find.
 279     pub steps: Lrc<Vec<CandidateStep<'tcx>>>,
 280     /// If Some(T), a type autoderef reported an error on.
 281     pub opt_bad_ty: Option<Lrc<MethodAutoderefBadTy<'tcx>>>,
 282     /// If `true`, `steps` has been truncated due to reaching the
 283     /// recursion limit.
 284     pub reached_recursion_limit: bool,
 285 }
 286
 287 #[derive(Debug, HashStable)]
 288 pub struct MethodAutoderefBadTy<'tcx> {
 289     pub reached_raw_pointer: bool,
 290     pub ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>,
 291 }
 292
 293 /// Result from the `normalize_projection_ty` query.
 294 #[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
 295 pub struct NormalizationResult<'tcx> {
 296     /// Result of normalization.
 297     pub normalized_ty: Ty<'tcx>,
 298 }
 299
 300 /// Outlives bounds are relationships between generic parameters,
 301 /// whether they both be regions (`'a: 'b`) or whether types are
 302 /// involved (`T: 'a`). These relationships can be extracted from the
 303 /// full set of predicates we understand or also from types (in which
 304 /// case they are called implied bounds). They are fed to the
 305 /// `OutlivesEnv` which in turn is supplied to the region checker and
 306 /// other parts of the inference system.
 307 #[derive(Clone, Debug, TypeFoldable, Lift)]
 308 pub enum OutlivesBound<'tcx> {
 309     RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
 310     RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
 311     RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
 312 }
 313
 314 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for OutlivesBound<'tcx> {
 315     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 316         mem::discriminant(self).hash_stable(hcx, hasher);
 317         match *self {
 318             OutlivesBound::RegionSubRegion(ref a, ref b) => {
 319                 a.hash_stable(hcx, hasher);
 320                 b.hash_stable(hcx, hasher);
 321             }
 322             OutlivesBound::RegionSubParam(ref a, ref b) => {
 323                 a.hash_stable(hcx, hasher);
 324                 b.hash_stable(hcx, hasher);
 325             }
 326             OutlivesBound::RegionSubProjection(ref a, ref b) => {
 327                 a.hash_stable(hcx, hasher);
 328                 b.hash_stable(hcx, hasher);
 329             }
 330         }
 331     }
 332 }