src/librustc_traits/lowering/environment.rs

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