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 pub fn parameters_for_type<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
  23     ty.walk()
  24       .flat_map(|ty| parameters_for_type_shallow(ty))
  25       .collect()
  26 }
  27
  28 pub fn parameters_for_trait_ref<'tcx>(trait_ref: &ty::TraitRef<'tcx>) -> Vec<Parameter> {
  29     let mut region_parameters =
  30         parameters_for_regions_in_substs(&trait_ref.substs);
  31
  32     let type_parameters =
  33         trait_ref.substs.types.iter()
  34                               .flat_map(|ty| parameters_for_type(ty));
  35
  36     region_parameters.extend(type_parameters);
  37
  38     region_parameters
  39 }
  40
  41 fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
  42     match ty.sty {
  43         ty::TyParam(ref d) =>
  44             vec![Parameter::Type(d.clone())],
  45         ty::TyRef(region, _) =>
  46             parameters_for_region(region).into_iter().collect(),
  47         ty::TyStruct(_, substs) |
  48         ty::TyEnum(_, substs) =>
  49             parameters_for_regions_in_substs(substs),
  50         ty::TyTrait(ref data) =>
  51             parameters_for_regions_in_substs(&data.principal.skip_binder().substs),
  52         _ =>
  53             vec![],
  54     }
  55 }
  56
  57 fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
  58     substs.regions()
  59           .iter()
  60           .filter_map(|r| parameters_for_region(r))
  61           .collect()
  62 }
  63
  64 fn parameters_for_region(region: &ty::Region) -> Option<Parameter> {
  65     match *region {
  66         ty::ReEarlyBound(data) => Some(Parameter::Region(data)),
  67         _ => None,
  68     }
  69 }
  70
  71 pub fn identify_constrained_type_params<'tcx>(_tcx: &ty::ctxt<'tcx>,
  72                                               predicates: &[ty::Predicate<'tcx>],
  73                                               impl_trait_ref: Option<ty::TraitRef<'tcx>>,
  74                                               input_parameters: &mut HashSet<Parameter>)
  75 {
  76     loop {
  77         let num_inputs = input_parameters.len();
  78
  79         let poly_projection_predicates = // : iterator over PolyProjectionPredicate
  80             predicates.iter()
  81                       .filter_map(|predicate| {
  82                           match *predicate {
  83                               ty::Predicate::Projection(ref data) => Some(data.clone()),
  84                               _ => None,
  85                           }
  86                       });
  87
  88         for poly_projection in poly_projection_predicates {
  89             // Note that we can skip binder here because the impl
  90             // trait ref never contains any late-bound regions.
  91             let projection = poly_projection.skip_binder();
  92
  93             // Special case: watch out for some kind of sneaky attempt
  94             // to project out an associated type defined by this very
  95             // trait.
  96             let unbound_trait_ref = &projection.projection_ty.trait_ref;
  97             if Some(unbound_trait_ref.clone()) == impl_trait_ref {
  98                 continue;
  99             }
 100
 101             let inputs = parameters_for_trait_ref(&projection.projection_ty.trait_ref);
 102             let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p));
 103             if relies_only_on_inputs {
 104                 input_parameters.extend(parameters_for_type(projection.ty));
 105             }
 106         }
 107
 108         if input_parameters.len() == num_inputs {
 109             break;
 110         }
 111     }
 112 }