src/librustc_typeck/constrained_type_params.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use middle::subst;
  12 use middle::ty::{self, Ty};
  13
  14 use std::collections::HashSet;
  15
  16 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
  17 pub enum Parameter {
  18     Type(ty::ParamTy),
  19     Region(ty::EarlyBoundRegion),
  20 }
  21
  22 /// Returns the list of parameters that are constrained by the type `ty`
  23 /// - i.e. the value of each parameter in the list is uniquely determined
  24 /// by `ty` (see RFC 447).
  25 pub fn parameters_for_type<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
  26     let mut result = vec![];
  27     ty.maybe_walk(|t| {
  28         if let ty::TyProjection(..) = t.sty {
  29             false // projections are not injective.
  30         } else {
  31             result.append(&mut parameters_for_type_shallow(t));
  32             // non-projection type constructors are injective.
  33             true
  34         }
  35     });
  36     result
  37 }
  38
  39 pub fn parameters_for_trait_ref<'tcx>(trait_ref: &ty::TraitRef<'tcx>) -> Vec<Parameter> {
  40     let mut region_parameters =
  41         parameters_for_regions_in_substs(&trait_ref.substs);
  42
  43     let type_parameters =
  44         trait_ref.substs.types.iter()
  45                               .flat_map(|ty| parameters_for_type(ty));
  46
  47     region_parameters.extend(type_parameters);
  48
  49     region_parameters
  50 }
  51
  52 fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
  53     match ty.sty {
  54         ty::TyParam(ref d) =>
  55             vec![Parameter::Type(d.clone())],
  56         ty::TyRef(region, _) =>
  57             parameters_for_region(region).into_iter().collect(),
  58         ty::TyStruct(_, substs) |
  59         ty::TyEnum(_, substs) =>
  60             parameters_for_regions_in_substs(substs),
  61         ty::TyTrait(ref data) =>
  62             parameters_for_regions_in_substs(&data.principal.skip_binder().substs),
  63         _ =>
  64             vec![],
  65     }
  66 }
  67
  68 fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
  69     substs.regions()
  70           .iter()
  71           .filter_map(|r| parameters_for_region(r))
  72           .collect()
  73 }
  74
  75 fn parameters_for_region(region: &ty::Region) -> Option<Parameter> {
  76     match *region {
  77         ty::ReEarlyBound(data) => Some(Parameter::Region(data)),
  78         _ => None,
  79     }
  80 }
  81
  82 pub fn identify_constrained_type_params<'tcx>(_tcx: &ty::ctxt<'tcx>,
  83                                               predicates: &[ty::Predicate<'tcx>],
  84                                               impl_trait_ref: Option<ty::TraitRef<'tcx>>,
  85                                               input_parameters: &mut HashSet<Parameter>)
  86 {
  87     loop {
  88         let num_inputs = input_parameters.len();
  89
  90         let poly_projection_predicates = // : iterator over PolyProjectionPredicate
  91             predicates.iter()
  92                       .filter_map(|predicate| {
  93                           match *predicate {
  94                               ty::Predicate::Projection(ref data) => Some(data.clone()),
  95                               _ => None,
  96                           }
  97                       });
  98
  99         for poly_projection in poly_projection_predicates {
 100             // Note that we can skip binder here because the impl
 101             // trait ref never contains any late-bound regions.
 102             let projection = poly_projection.skip_binder();
 103
 104             // Special case: watch out for some kind of sneaky attempt
 105             // to project out an associated type defined by this very
 106             // trait.
 107             let unbound_trait_ref = &projection.projection_ty.trait_ref;
 108             if Some(unbound_trait_ref.clone()) == impl_trait_ref {
 109                 continue;
 110             }
 111
 112             let inputs = parameters_for_trait_ref(&projection.projection_ty.trait_ref);
 113             let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p));
 114             if relies_only_on_inputs {
 115                 input_parameters.extend(parameters_for_type(projection.ty));
 116             }
 117         }
 118
 119         if input_parameters.len() == num_inputs {
 120             break;
 121         }
 122     }
 123 }