src/librustc_traits/chalk_context/program_clauses/mod.rs

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