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.
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.
12 use middle::ty::{self, Ty};
14 use std::collections::HashSet;
16 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
19 Region(ty::EarlyBoundRegion),
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![];
28 if let ty::TyProjection(..) = t.sty {
29 false // projections are not injective.
31 result.append(&mut parameters_for_type_shallow(t));
32 // non-projection type constructors are injective.
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);
44 trait_ref.substs.types.iter()
45 .flat_map(|ty| parameters_for_type(ty));
47 region_parameters.extend(type_parameters);
52 fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
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),
68 fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
71 .filter_map(|r| parameters_for_region(r))
75 fn parameters_for_region(region: &ty::Region) -> Option<Parameter> {
77 ty::ReEarlyBound(data) => Some(Parameter::Region(data)),
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>)
88 let num_inputs = input_parameters.len();
90 let poly_projection_predicates = // : iterator over PolyProjectionPredicate
92 .filter_map(|predicate| {
94 ty::Predicate::Projection(ref data) => Some(data.clone()),
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();
104 // Special case: watch out for some kind of sneaky attempt
105 // to project out an associated type defined by this very
107 let unbound_trait_ref = &projection.projection_ty.trait_ref;
108 if Some(unbound_trait_ref.clone()) == impl_trait_ref {
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));
119 if input_parameters.len() == num_inputs {