src/librustc_traits/chalk_context/program_clauses/mod.rs

   1 mod builtin;
   2 mod primitive;
   3
   4 use super::ChalkInferenceContext;
   5 use rustc::traits::{
   6     Clause, DomainGoal, Environment, FromEnv, ProgramClause, ProgramClauseCategory, WellFormed,
   7 };
   8 use rustc::ty::{self, TyCtxt};
   9 use rustc_hir::def_id::DefId;
  10 use std::iter;
  11
  12 use self::builtin::*;
  13 use self::primitive::*;
  14
  15 fn assemble_clauses_from_impls<'tcx>(
  16     tcx: TyCtxt<'tcx>,
  17     trait_def_id: DefId,
  18     clauses: &mut Vec<Clause<'tcx>>,
  19 ) {
  20     tcx.for_each_impl(trait_def_id, |impl_def_id| {
  21         clauses.extend(tcx.program_clauses_for(impl_def_id).into_iter().cloned());
  22     });
  23 }
  24
  25 fn assemble_clauses_from_assoc_ty_values<'tcx>(
  26     tcx: TyCtxt<'tcx>,
  27     trait_def_id: DefId,
  28     clauses: &mut Vec<Clause<'tcx>>,
  29 ) {
  30     tcx.for_each_impl(trait_def_id, |impl_def_id| {
  31         for def_id in tcx.associated_item_def_ids(impl_def_id).iter() {
  32             clauses.extend(tcx.program_clauses_for(*def_id).into_iter().cloned());
  33         }
  34     });
  35 }
  36
  37 impl ChalkInferenceContext<'cx, 'tcx> {
  38     pub(super) fn program_clauses_impl(
  39         &self,
  40         environment: &Environment<'tcx>,
  41         goal: &DomainGoal<'tcx>,
  42     ) -> Vec<Clause<'tcx>> {
  43         use rustc::infer::canonical::OriginalQueryValues;
  44         use rustc::traits::WhereClause::*;
  45
  46         let goal = self.infcx.resolve_vars_if_possible(goal);
  47
  48         debug!("program_clauses(goal = {:?})", goal);
  49
  50         let mut clauses = match goal {
  51             DomainGoal::Holds(Implemented(trait_predicate)) => {
  52                 // These come from:
  53                 // * implementations of the trait itself (rule `Implemented-From-Impl`)
  54                 // * the trait decl (rule `Implemented-From-Env`)
  55
  56                 let mut clauses = vec![];
  57
  58                 assemble_clauses_from_impls(self.infcx.tcx, trait_predicate.def_id(), &mut clauses);
  59
  60                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().sized_trait() {
  61                     assemble_builtin_sized_impls(
  62                         self.infcx.tcx,
  63                         trait_predicate.def_id(),
  64                         trait_predicate.self_ty(),
  65                         &mut clauses,
  66                     );
  67                 }
  68
  69                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().unsize_trait() {
  70                     let source = trait_predicate.self_ty();
  71                     let target = trait_predicate.trait_ref.substs.type_at(1);
  72                     assemble_builtin_unsize_impls(
  73                         self.infcx.tcx,
  74                         trait_predicate.def_id(),
  75                         source,
  76                         target,
  77                         &mut clauses,
  78                     );
  79                 }
  80
  81                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().copy_trait() {
  82                     assemble_builtin_copy_clone_impls(
  83                         self.infcx.tcx,
  84                         trait_predicate.def_id(),
  85                         trait_predicate.self_ty(),
  86                         &mut clauses,
  87                     );
  88                 }
  89
  90                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().clone_trait() {
  91                     // For all builtin impls, the conditions for `Copy` and
  92                     // `Clone` are the same.
  93                     assemble_builtin_copy_clone_impls(
  94                         self.infcx.tcx,
  95                         trait_predicate.def_id(),
  96                         trait_predicate.self_ty(),
  97                         &mut clauses,
  98                     );
  99                 }
 100
 101                 // FIXME: we need to add special rules for other builtin impls:
 102                 // * `Generator`
 103                 // * `FnOnce` / `FnMut` / `Fn`
 104                 // * trait objects
 105                 // * auto traits
 106
 107                 // Rule `Implemented-From-Env` will be computed from the environment.
 108                 clauses
 109             }
 110
 111             DomainGoal::Holds(ProjectionEq(projection_predicate)) => {
 112                 // These come from:
 113                 // * the assoc type definition (rule `ProjectionEq-Placeholder`)
 114                 // * normalization of the assoc ty values (rule `ProjectionEq-Normalize`)
 115                 // * implied bounds from trait definitions (rule `Implied-Bound-From-Trait`)
 116                 // * implied bounds from type definitions (rule `Implied-Bound-From-Type`)
 117
 118                 let clauses = self
 119                     .infcx
 120                     .tcx
 121                     .program_clauses_for(projection_predicate.projection_ty.item_def_id)
 122                     .into_iter()
 123                     // only select `ProjectionEq-Placeholder` and `ProjectionEq-Normalize`
 124                     .filter(|clause| clause.category() == ProgramClauseCategory::Other)
 125                     .cloned()
 126                     .collect::<Vec<_>>();
 127
 128                 // Rules `Implied-Bound-From-Trait` and `Implied-Bound-From-Type` will be computed
 129                 // from the environment.
 130                 clauses
 131             }
 132
 133             // For outlive requirements, just assume they hold. `ResolventOps::resolvent_clause`
 134             // will register them as actual region constraints later.
 135             DomainGoal::Holds(RegionOutlives(..)) | DomainGoal::Holds(TypeOutlives(..)) => {
 136                 vec![Clause::Implies(ProgramClause {
 137                     goal,
 138                     hypotheses: ty::List::empty(),
 139                     category: ProgramClauseCategory::Other,
 140                 })]
 141             }
 142
 143             DomainGoal::WellFormed(WellFormed::Trait(trait_predicate)) => {
 144                 // These come from -- the trait decl (rule `WellFormed-TraitRef`).
 145                 self.infcx
 146                     .tcx
 147                     .program_clauses_for(trait_predicate.def_id())
 148                     .into_iter()
 149                     // only select `WellFormed-TraitRef`
 150                     .filter(|clause| clause.category() == ProgramClauseCategory::WellFormed)
 151                     .cloned()
 152                     .collect()
 153             }
 154
 155             DomainGoal::WellFormed(WellFormed::Ty(ty)) => {
 156                 // These come from:
 157                 // * the associated type definition if `ty` refers to an unnormalized
 158                 //   associated type (rule `WellFormed-AssocTy`)
 159                 // * custom rules for built-in types
 160                 // * the type definition otherwise (rule `WellFormed-Type`)
 161                 let clauses = match ty.kind {
 162                     ty::Projection(data) => self.infcx.tcx.program_clauses_for(data.item_def_id),
 163
 164                     // These types are always WF.
 165                     ty::Bool
 166                     | ty::Char
 167                     | ty::Int(..)
 168                     | ty::Uint(..)
 169                     | ty::Float(..)
 170                     | ty::Str
 171                     | ty::Param(..)
 172                     | ty::Placeholder(..)
 173                     | ty::Error
 174                     | ty::Never => {
 175                         let wf_clause = ProgramClause {
 176                             goal,
 177                             hypotheses: ty::List::empty(),
 178                             category: ProgramClauseCategory::WellFormed,
 179                         };
 180                         let wf_clause = Clause::Implies(wf_clause);
 181
 182                         self.infcx.tcx.mk_clauses(iter::once(wf_clause))
 183                     }
 184
 185                     // Always WF (recall that we do not check for parameters to be WF).
 186                     ty::RawPtr(ptr) => wf_clause_for_raw_ptr(self.infcx.tcx, ptr.mutbl),
 187
 188                     // Always WF (recall that we do not check for parameters to be WF).
 189                     ty::FnPtr(fn_ptr) => {
 190                         let fn_ptr = fn_ptr.skip_binder();
 191                         wf_clause_for_fn_ptr(
 192                             self.infcx.tcx,
 193                             fn_ptr.inputs_and_output.len(),
 194                             fn_ptr.c_variadic,
 195                             fn_ptr.unsafety,
 196                             fn_ptr.abi,
 197                         )
 198                     }
 199
 200                     // WF if inner type is `Sized`.
 201                     ty::Slice(..) => wf_clause_for_slice(self.infcx.tcx),
 202
 203                     // WF if inner type is `Sized`.
 204                     ty::Array(_, length) => wf_clause_for_array(self.infcx.tcx, length),
 205
 206                     // WF if all types but the last one are `Sized`.
 207                     ty::Tuple(types) => wf_clause_for_tuple(self.infcx.tcx, types.len()),
 208
 209                     // WF if `sub_ty` outlives `region`.
 210                     ty::Ref(_, _, mutbl) => wf_clause_for_ref(self.infcx.tcx, mutbl),
 211
 212                     ty::FnDef(def_id, ..) => wf_clause_for_fn_def(self.infcx.tcx, def_id),
 213
 214                     ty::Dynamic(..) => {
 215                         // FIXME: no rules yet for trait objects
 216                         ty::List::empty()
 217                     }
 218
 219                     ty::Adt(def, ..) => self.infcx.tcx.program_clauses_for(def.did),
 220
 221                     // FIXME: these are probably wrong
 222                     ty::Foreign(def_id)
 223                     | ty::Closure(def_id, ..)
 224                     | ty::Generator(def_id, ..)
 225                     | ty::Opaque(def_id, ..) => self.infcx.tcx.program_clauses_for(def_id),
 226
 227                     // Artificially trigger an ambiguity.
 228                     ty::Infer(..) => {
 229                         let tcx = self.infcx.tcx;
 230                         let types = [tcx.types.i32, tcx.types.u32, tcx.types.f32, tcx.types.f64];
 231                         let clauses = types
 232                             .iter()
 233                             .cloned()
 234                             .map(|ty| ProgramClause {
 235                                 goal: DomainGoal::WellFormed(WellFormed::Ty(ty)),
 236                                 hypotheses: ty::List::empty(),
 237                                 category: ProgramClauseCategory::WellFormed,
 238                             })
 239                             .map(|clause| Clause::Implies(clause));
 240                         tcx.mk_clauses(clauses)
 241                     }
 242
 243                     ty::GeneratorWitness(..) | ty::UnnormalizedProjection(..) | ty::Bound(..) => {
 244                         bug!("unexpected type {:?}", ty)
 245                     }
 246                 };
 247
 248                 clauses
 249                     .into_iter()
 250                     .filter(|clause| clause.category() == ProgramClauseCategory::WellFormed)
 251                     .cloned()
 252                     .collect()
 253             }
 254
 255             DomainGoal::FromEnv(FromEnv::Trait(..)) => {
 256                 // These come from:
 257                 // * implied bounds from trait definitions (rule `Implied-Bound-From-Trait`)
 258                 // * implied bounds from type definitions (rule `Implied-Bound-From-Type`)
 259                 // * implied bounds from assoc type defs (rules `Implied-Trait-From-AssocTy`,
 260                 //   `Implied-Bound-From-AssocTy` and `Implied-WC-From-AssocTy`)
 261
 262                 // All of these rules are computed in the environment.
 263                 vec![]
 264             }
 265
 266             DomainGoal::FromEnv(FromEnv::Ty(..)) => {
 267                 // There are no `FromEnv::Ty(..) :- ...` rules (this predicate only
 268                 // comes from the environment).
 269                 vec![]
 270             }
 271
 272             DomainGoal::Normalize(projection_predicate) => {
 273                 // These come from -- assoc ty values (rule `Normalize-From-Impl`).
 274                 let mut clauses = vec![];
 275
 276                 assemble_clauses_from_assoc_ty_values(
 277                     self.infcx.tcx,
 278                     projection_predicate.projection_ty.trait_ref(self.infcx.tcx).def_id,
 279                     &mut clauses,
 280                 );
 281
 282                 clauses
 283             }
 284         };
 285
 286         debug!("program_clauses: clauses = {:?}", clauses);
 287         debug!("program_clauses: adding clauses from environment = {:?}", environment);
 288
 289         let mut _orig_query_values = OriginalQueryValues::default();
 290         let canonical_environment =
 291             self.infcx.canonicalize_query(environment, &mut _orig_query_values).value;
 292         let env_clauses = self.infcx.tcx.program_clauses_for_env(canonical_environment);
 293
 294         debug!("program_clauses: env_clauses = {:?}", env_clauses);
 295
 296         clauses.extend(env_clauses.into_iter().cloned());
 297         clauses.extend(environment.clauses.iter().cloned());
 298         clauses
 299     }
 300 }