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<'set, 'a, 'tcx: 'a + 'set> {
  15     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  16     round: &'set mut FxHashSet<Clause<'tcx>>,
  17 }
  18
  19 impl ClauseVisitor<'set, 'a, 'tcx> {
  20     fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, round: &'set 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.sty {
  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<'a, 'tcx>(
 131     tcx: TyCtxt<'a, 'tcx, '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<'a, 'tcx>(
 164     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 165     def_id: DefId
 166 ) -> Environment<'tcx> {
 167     use super::{Lower, IntoFromEnvGoal};
 168     use rustc::hir::{Node, TraitItemKind, ImplItemKind, ItemKind, ForeignItemKind};
 169
 170     debug!("environment(def_id = {:?})", def_id);
 171
 172     // The environment of an impl Trait type is its defining function's environment.
 173     if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
 174         return environment(tcx, parent);
 175     }
 176
 177     // Compute the bounds on `Self` and the type parameters.
 178     let ty::InstantiatedPredicates { predicates } = tcx.predicates_of(def_id)
 179         .instantiate_identity(tcx);
 180
 181     let clauses = predicates.into_iter()
 182         .map(|predicate| predicate.lower())
 183         .map(|domain_goal| domain_goal.map_bound(|bound| bound.into_from_env_goal()))
 184         .map(|domain_goal| domain_goal.map_bound(|bound| bound.into_program_clause()))
 185
 186         // `ForAll` because each `domain_goal` is a `PolyDomainGoal` and
 187         // could bound lifetimes.
 188         .map(Clause::ForAll);
 189
 190     let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
 191     let node = tcx.hir().get_by_hir_id(hir_id);
 192
 193     enum NodeKind {
 194         TraitImpl,
 195         InherentImpl,
 196         Fn,
 197         Other,
 198     };
 199
 200     let node_kind = match node {
 201         Node::TraitItem(item) => match item.node {
 202             TraitItemKind::Method(..) => NodeKind::Fn,
 203             _ => NodeKind::Other,
 204         }
 205
 206         Node::ImplItem(item) => match item.node {
 207             ImplItemKind::Method(..) => NodeKind::Fn,
 208             _ => NodeKind::Other,
 209         }
 210
 211         Node::Item(item) => match item.node {
 212             ItemKind::Impl(.., Some(..), _, _) => NodeKind::TraitImpl,
 213             ItemKind::Impl(.., None, _, _) => NodeKind::InherentImpl,
 214             ItemKind::Fn(..) => NodeKind::Fn,
 215             _ => NodeKind::Other,
 216         }
 217
 218         Node::ForeignItem(item) => match item.node {
 219             ForeignItemKind::Fn(..) => NodeKind::Fn,
 220             _ => NodeKind::Other,
 221         }
 222
 223         // FIXME: closures?
 224         _ => NodeKind::Other,
 225     };
 226
 227     let mut input_tys = FxHashSet::default();
 228
 229     match node_kind {
 230         // In a trait impl, we assume that the header trait ref and all its
 231         // constituents are well-formed.
 232         NodeKind::TraitImpl => {
 233             let trait_ref = tcx.impl_trait_ref(def_id)
 234                 .expect("not an impl");
 235
 236             input_tys.extend(
 237                 trait_ref.input_types().flat_map(|ty| ty.walk())
 238             );
 239         }
 240
 241         // In an inherent impl, we assume that the receiver type and all its
 242         // constituents are well-formed.
 243         NodeKind::InherentImpl => {
 244             let self_ty = tcx.type_of(def_id);
 245             input_tys.extend(self_ty.walk());
 246         }
 247
 248         // In an fn, we assume that the arguments and all their constituents are
 249         // well-formed.
 250         NodeKind::Fn => {
 251             let fn_sig = tcx.fn_sig(def_id);
 252             let fn_sig = tcx.liberate_late_bound_regions(def_id, &fn_sig);
 253
 254             input_tys.extend(
 255                 fn_sig.inputs().iter().flat_map(|ty| ty.walk())
 256             );
 257         }
 258
 259         NodeKind::Other => (),
 260     }
 261
 262     let clauses = clauses.chain(
 263         input_tys.into_iter()
 264             .map(|ty| DomainGoal::FromEnv(FromEnv::Ty(ty)))
 265             .map(|domain_goal| domain_goal.into_program_clause())
 266             .map(Clause::Implies)
 267     );
 268
 269     debug!("environment: clauses = {:?}", clauses);
 270
 271     Environment {
 272         clauses: tcx.mk_clauses(clauses),
 273     }
 274 }