src/librustc_traits/lowering/environment.rs

   1 use rustc::traits::{
   2     Clause, Clauses, DomainGoal, Environment, FromEnv, ProgramClause, ProgramClauseCategory,
   3 };
   4 use rustc::ty::{self, Ty, TyCtxt};
   5 use rustc_data_structures::fx::FxHashSet;
   6 use rustc_hir::def_id::DefId;
   7
   8 struct ClauseVisitor<'a, 'tcx> {
   9     tcx: TyCtxt<'tcx>,
  10     round: &'a mut FxHashSet<Clause<'tcx>>,
  11 }
  12
  13 impl ClauseVisitor<'a, 'tcx> {
  14     fn new(tcx: TyCtxt<'tcx>, round: &'a mut FxHashSet<Clause<'tcx>>) -> Self {
  15         ClauseVisitor { tcx, round }
  16     }
  17
  18     fn visit_ty(&mut self, ty: Ty<'tcx>) {
  19         match ty.kind {
  20             ty::Projection(data) => {
  21                 self.round.extend(
  22                     self.tcx
  23                         .program_clauses_for(data.item_def_id)
  24                         .iter()
  25                         .filter(|c| c.category() == ProgramClauseCategory::ImpliedBound)
  26                         .cloned(),
  27                 );
  28             }
  29
  30             ty::Dynamic(..) => {
  31                 // FIXME: trait object rules are not yet implemented
  32             }
  33
  34             ty::Adt(def, ..) => {
  35                 self.round.extend(
  36                     self.tcx
  37                         .program_clauses_for(def.did)
  38                         .iter()
  39                         .filter(|c| c.category() == ProgramClauseCategory::ImpliedBound)
  40                         .cloned(),
  41                 );
  42             }
  43
  44             ty::Foreign(def_id)
  45             | ty::FnDef(def_id, ..)
  46             | ty::Closure(def_id, ..)
  47             | ty::Generator(def_id, ..)
  48             | ty::Opaque(def_id, ..) => {
  49                 self.round.extend(
  50                     self.tcx
  51                         .program_clauses_for(def_id)
  52                         .iter()
  53                         .filter(|c| c.category() == ProgramClauseCategory::ImpliedBound)
  54                         .cloned(),
  55                 );
  56             }
  57
  58             ty::Bool
  59             | ty::Char
  60             | ty::Int(..)
  61             | ty::Uint(..)
  62             | ty::Float(..)
  63             | ty::Str
  64             | ty::Array(..)
  65             | ty::Slice(..)
  66             | ty::RawPtr(..)
  67             | ty::FnPtr(..)
  68             | ty::Tuple(..)
  69             | ty::Ref(..)
  70             | ty::Never
  71             | ty::Infer(..)
  72             | ty::Placeholder(..)
  73             | ty::Param(..)
  74             | ty::Bound(..) => (),
  75
  76             ty::GeneratorWitness(..) | ty::UnnormalizedProjection(..) | ty::Error => {
  77                 bug!("unexpected type {:?}", ty);
  78             }
  79         }
  80     }
  81
  82     fn visit_from_env(&mut self, from_env: FromEnv<'tcx>) {
  83         match from_env {
  84             FromEnv::Trait(predicate) => {
  85                 self.round.extend(
  86                     self.tcx
  87                         .program_clauses_for(predicate.def_id())
  88                         .iter()
  89                         .filter(|c| c.category() == ProgramClauseCategory::ImpliedBound)
  90                         .cloned(),
  91                 );
  92             }
  93
  94             FromEnv::Ty(ty) => self.visit_ty(ty),
  95         }
  96     }
  97
  98     fn visit_domain_goal(&mut self, domain_goal: DomainGoal<'tcx>) {
  99         // The only domain goals we can find in an environment are:
 100         // * `DomainGoal::Holds(..)`
 101         // * `DomainGoal::FromEnv(..)`
 102         // The former do not lead to any implied bounds. So we only need
 103         // to visit the latter.
 104         if let DomainGoal::FromEnv(from_env) = domain_goal {
 105             self.visit_from_env(from_env);
 106         }
 107     }
 108
 109     fn visit_program_clause(&mut self, clause: ProgramClause<'tcx>) {
 110         self.visit_domain_goal(clause.goal);
 111         // No need to visit `clause.hypotheses`: they are always of the form
 112         // `FromEnv(...)` and were visited at a previous round.
 113     }
 114
 115     fn visit_clause(&mut self, clause: Clause<'tcx>) {
 116         match clause {
 117             Clause::Implies(clause) => self.visit_program_clause(clause),
 118             Clause::ForAll(clause) => self.visit_program_clause(*clause.skip_binder()),
 119         }
 120     }
 121 }
 122
 123 crate fn program_clauses_for_env<'tcx>(
 124     tcx: TyCtxt<'tcx>,
 125     environment: Environment<'tcx>,
 126 ) -> Clauses<'tcx> {
 127     debug!("program_clauses_for_env(environment={:?})", environment);
 128
 129     let mut last_round = FxHashSet::default();
 130     {
 131         let mut visitor = ClauseVisitor::new(tcx, &mut last_round);
 132         for &clause in environment.clauses {
 133             visitor.visit_clause(clause);
 134         }
 135     }
 136
 137     let mut closure = last_round.clone();
 138     let mut next_round = FxHashSet::default();
 139     while !last_round.is_empty() {
 140         let mut visitor = ClauseVisitor::new(tcx, &mut next_round);
 141         for clause in last_round.drain() {
 142             visitor.visit_clause(clause);
 143         }
 144         last_round.extend(next_round.drain().filter(|&clause| closure.insert(clause)));
 145     }
 146
 147     debug!("program_clauses_for_env: closure = {:#?}", closure);
 148
 149     return tcx.mk_clauses(closure.into_iter());
 150 }
 151
 152 crate fn environment(tcx: TyCtxt<'_>, def_id: DefId) -> Environment<'_> {
 153     use super::{IntoFromEnvGoal, Lower};
 154     use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
 155
 156     debug!("environment(def_id = {:?})", def_id);
 157
 158     // The environment of an impl Trait type is its defining function's environment.
 159     if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
 160         return environment(tcx, parent);
 161     }
 162
 163     // Compute the bounds on `Self` and the type parameters.
 164     let ty::InstantiatedPredicates { predicates, .. } =
 165         tcx.predicates_of(def_id).instantiate_identity(tcx);
 166
 167     let clauses = predicates
 168         .into_iter()
 169         .map(|predicate| predicate.lower())
 170         .map(|domain_goal| domain_goal.map_bound(|bound| bound.into_from_env_goal()))
 171         .map(|domain_goal| domain_goal.map_bound(|bound| bound.into_program_clause()))
 172         // `ForAll` because each `domain_goal` is a `PolyDomainGoal` and
 173         // could bound lifetimes.
 174         .map(Clause::ForAll);
 175
 176     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
 177     let node = tcx.hir().get(hir_id);
 178
 179     enum NodeKind {
 180         TraitImpl,
 181         InherentImpl,
 182         Fn,
 183         Other,
 184     };
 185
 186     let node_kind = match node {
 187         Node::TraitItem(item) => match item.kind {
 188             TraitItemKind::Fn(..) => NodeKind::Fn,
 189             _ => NodeKind::Other,
 190         },
 191
 192         Node::ImplItem(item) => match item.kind {
 193             ImplItemKind::Fn(..) => NodeKind::Fn,
 194             _ => NodeKind::Other,
 195         },
 196
 197         Node::Item(item) => match item.kind {
 198             ItemKind::Impl { of_trait: Some(_), .. } => NodeKind::TraitImpl,
 199             ItemKind::Impl { of_trait: None, .. } => NodeKind::InherentImpl,
 200             ItemKind::Fn(..) => NodeKind::Fn,
 201             _ => NodeKind::Other,
 202         },
 203
 204         Node::ForeignItem(item) => match item.kind {
 205             ForeignItemKind::Fn(..) => NodeKind::Fn,
 206             _ => NodeKind::Other,
 207         },
 208
 209         // FIXME: closures?
 210         _ => NodeKind::Other,
 211     };
 212
 213     let mut input_tys = FxHashSet::default();
 214
 215     match node_kind {
 216         // In a trait impl, we assume that the header trait ref and all its
 217         // constituents are well-formed.
 218         NodeKind::TraitImpl => {
 219             let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
 220
 221             input_tys.extend(trait_ref.input_types().flat_map(|ty| ty.walk()));
 222         }
 223
 224         // In an inherent impl, we assume that the receiver type and all its
 225         // constituents are well-formed.
 226         NodeKind::InherentImpl => {
 227             let self_ty = tcx.type_of(def_id);
 228             input_tys.extend(self_ty.walk());
 229         }
 230
 231         // In an fn, we assume that the arguments and all their constituents are
 232         // well-formed.
 233         NodeKind::Fn => {
 234             let fn_sig = tcx.fn_sig(def_id);
 235             let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig);
 236
 237             input_tys.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
 238         }
 239
 240         NodeKind::Other => (),
 241     }
 242
 243     let clauses = clauses.chain(
 244         input_tys
 245             .into_iter()
 246             .map(|ty| DomainGoal::FromEnv(FromEnv::Ty(ty)))
 247             .map(|domain_goal| domain_goal.into_program_clause())
 248             .map(Clause::Implies),
 249     );
 250
 251     debug!("environment: clauses = {:?}", clauses);
 252
 253     Environment { clauses: tcx.mk_clauses(clauses) }
 254 }