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::{self, TyCtxt};
  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: 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: 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_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                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().copy_trait() {
 100                     assemble_builtin_copy_clone_impls(
 101                         self.infcx.tcx,
 102                         trait_predicate.def_id(),
 103                         trait_predicate.self_ty(),
 104                         &mut clauses
 105                     );
 106                 }
 107
 108                 if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().clone_trait() {
 109                     // For all builtin impls, the conditions for `Copy` and
 110                     // `Clone` are the same.
 111                     assemble_builtin_copy_clone_impls(
 112                         self.infcx.tcx,
 113                         trait_predicate.def_id(),
 114                         trait_predicate.self_ty(),
 115                         &mut clauses
 116                     );
 117                 }
 118
 119                 // FIXME: we need to add special rules for other builtin impls:
 120                 // * `Generator`
 121                 // * `FnOnce` / `FnMut` / `Fn`
 122                 // * trait objects
 123                 // * auto traits
 124
 125                 // Rule `Implemented-From-Env` will be computed from the environment.
 126                 clauses
 127             }
 128
 129             DomainGoal::Holds(ProjectionEq(projection_predicate)) => {
 130                 // These come from:
 131                 // * the assoc type definition (rule `ProjectionEq-Placeholder`)
 132                 // * normalization of the assoc ty values (rule `ProjectionEq-Normalize`)
 133                 // * implied bounds from trait definitions (rule `Implied-Bound-From-Trait`)
 134                 // * implied bounds from type definitions (rule `Implied-Bound-From-Type`)
 135
 136                 let clauses = self.infcx.tcx.program_clauses_for(
 137                     projection_predicate.projection_ty.item_def_id
 138                 ).into_iter()
 139
 140                     // only select `ProjectionEq-Placeholder` and `ProjectionEq-Normalize`
 141                     .filter(|clause| clause.category() == ProgramClauseCategory::Other)
 142
 143                     .cloned()
 144                     .collect::<Vec<_>>();
 145
 146                 // Rules `Implied-Bound-From-Trait` and `Implied-Bound-From-Type` will be computed
 147                 // from the environment.
 148                 clauses
 149             }
 150
 151             // For outlive requirements, just assume they hold. `ResolventOps::resolvent_clause`
 152             // will register them as actual region constraints later.
 153             DomainGoal::Holds(RegionOutlives(..)) | DomainGoal::Holds(TypeOutlives(..)) => {
 154                 vec![Clause::Implies(ProgramClause {
 155                     goal,
 156                     hypotheses: ty::List::empty(),
 157                     category: ProgramClauseCategory::Other,
 158                 })]
 159             }
 160
 161             DomainGoal::WellFormed(WellFormed::Trait(trait_predicate)) => {
 162                 // These come from -- the trait decl (rule `WellFormed-TraitRef`).
 163                 self.infcx.tcx.program_clauses_for(trait_predicate.def_id())
 164                     .into_iter()
 165
 166                     // only select `WellFormed-TraitRef`
 167                     .filter(|clause| clause.category() == ProgramClauseCategory::WellFormed)
 168
 169                     .cloned()
 170                     .collect()
 171             }
 172
 173             DomainGoal::WellFormed(WellFormed::Ty(ty)) => {
 174                 // These come from:
 175                 // * the associated type definition if `ty` refers to an unnormalized
 176                 //   associated type (rule `WellFormed-AssocTy`)
 177                 // * custom rules for built-in types
 178                 // * the type definition otherwise (rule `WellFormed-Type`)
 179                 let clauses = match ty.sty {
 180                     ty::Projection(data) => {
 181                         self.infcx.tcx.program_clauses_for(data.item_def_id)
 182                     }
 183
 184                     // These types are always WF.
 185                     ty::Bool |
 186                     ty::Char |
 187                     ty::Int(..) |
 188                     ty::Uint(..) |
 189                     ty::Float(..) |
 190                     ty::Str |
 191                     ty::Param(..) |
 192                     ty::Placeholder(..) |
 193                     ty::Error |
 194                     ty::Never => {
 195                         let wf_clause = ProgramClause {
 196                             goal,
 197                             hypotheses: ty::List::empty(),
 198                             category: ProgramClauseCategory::WellFormed,
 199                         };
 200                         let wf_clause = Clause::Implies(wf_clause);
 201
 202                         self.infcx.tcx.mk_clauses(iter::once(wf_clause))
 203                     }
 204
 205                     // Always WF (recall that we do not check for parameters to be WF).
 206                     ty::RawPtr(ptr) => wf_clause_for_raw_ptr(self.infcx.tcx, ptr.mutbl),
 207
 208                     // Always WF (recall that we do not check for parameters to be WF).
 209                     ty::FnPtr(fn_ptr) => {
 210                         let fn_ptr = fn_ptr.skip_binder();
 211                         wf_clause_for_fn_ptr(
 212                             self.infcx.tcx,
 213                             fn_ptr.inputs_and_output.len(),
 214                             fn_ptr.c_variadic,
 215                             fn_ptr.unsafety,
 216                             fn_ptr.abi
 217                         )
 218                     }
 219
 220                     // WF if inner type is `Sized`.
 221                     ty::Slice(..) => wf_clause_for_slice(self.infcx.tcx),
 222
 223                     // WF if inner type is `Sized`.
 224                     ty::Array(_, length) => wf_clause_for_array(self.infcx.tcx, length),
 225
 226                     // WF if all types but the last one are `Sized`.
 227                     ty::Tuple(types) => wf_clause_for_tuple(
 228                         self.infcx.tcx,
 229                         types.len()
 230                     ),
 231
 232                     // WF if `sub_ty` outlives `region`.
 233                     ty::Ref(_, _, mutbl) => wf_clause_for_ref(self.infcx.tcx, mutbl),
 234
 235                     ty::FnDef(def_id, ..) => wf_clause_for_fn_def(self.infcx.tcx, def_id),
 236
 237                     ty::Dynamic(..) => {
 238                         // FIXME: no rules yet for trait objects
 239                         ty::List::empty()
 240                     }
 241
 242                     ty::Adt(def, ..) => {
 243                         self.infcx.tcx.program_clauses_for(def.did)
 244                     }
 245
 246                     // FIXME: these are probably wrong
 247                     ty::Foreign(def_id) |
 248                     ty::Closure(def_id, ..) |
 249                     ty::Generator(def_id, ..) |
 250                     ty::Opaque(def_id, ..) => {
 251                         self.infcx.tcx.program_clauses_for(def_id)
 252                     }
 253
 254                     // Artificially trigger an ambiguity.
 255                     ty::Infer(..) => {
 256                         let tcx = self.infcx.tcx;
 257                         let types = [tcx.types.i32, tcx.types.u32, tcx.types.f32, tcx.types.f64];
 258                         let clauses = types.iter()
 259                             .cloned()
 260                             .map(|ty| ProgramClause {
 261                                 goal: DomainGoal::WellFormed(WellFormed::Ty(ty)),
 262                                 hypotheses: ty::List::empty(),
 263                                 category: ProgramClauseCategory::WellFormed,
 264                             })
 265                             .map(|clause| Clause::Implies(clause));
 266                         tcx.mk_clauses(clauses)
 267                     }
 268
 269                     ty::GeneratorWitness(..) |
 270                     ty::UnnormalizedProjection(..) |
 271                     ty::Bound(..) => {
 272                         bug!("unexpected type {:?}", ty)
 273                     }
 274                 };
 275
 276                 clauses.into_iter()
 277                     .filter(|clause| clause.category() == ProgramClauseCategory::WellFormed)
 278                     .cloned()
 279                     .collect()
 280             }
 281
 282             DomainGoal::FromEnv(FromEnv::Trait(..)) => {
 283                 // These come from:
 284                 // * implied bounds from trait definitions (rule `Implied-Bound-From-Trait`)
 285                 // * implied bounds from type definitions (rule `Implied-Bound-From-Type`)
 286                 // * implied bounds from assoc type defs (rules `Implied-Trait-From-AssocTy`,
 287                 //   `Implied-Bound-From-AssocTy` and `Implied-WC-From-AssocTy`)
 288
 289                 // All of these rules are computed in the environment.
 290                 vec![]
 291             }
 292
 293             DomainGoal::FromEnv(FromEnv::Ty(..)) => {
 294                 // There are no `FromEnv::Ty(..) :- ...` rules (this predicate only
 295                 // comes from the environment).
 296                 vec![]
 297             }
 298
 299             DomainGoal::Normalize(projection_predicate) => {
 300                 // These come from -- assoc ty values (rule `Normalize-From-Impl`).
 301                 let mut clauses = vec![];
 302
 303                 assemble_clauses_from_assoc_ty_values(
 304                     self.infcx.tcx,
 305                     projection_predicate.projection_ty.trait_ref(self.infcx.tcx).def_id,
 306                     &mut clauses
 307                 );
 308
 309                 clauses
 310             }
 311         };
 312
 313         debug!("program_clauses: clauses = {:?}", clauses);
 314         debug!("program_clauses: adding clauses from environment = {:?}", environment);
 315
 316         let mut _orig_query_values = OriginalQueryValues::default();
 317         let canonical_environment = self.infcx.canonicalize_query(
 318             environment,
 319             &mut _orig_query_values
 320         ).value;
 321         let env_clauses = self.infcx.tcx.program_clauses_for_env(canonical_environment);
 322
 323         debug!("program_clauses: env_clauses = {:?}", env_clauses);
 324
 325         clauses.extend(env_clauses.into_iter().cloned());
 326         clauses.extend(environment.clauses.iter().cloned());
 327         clauses
 328     }
 329 }