1 use rustc_data_structures
::fx
::FxHashSet
;
2 use rustc_middle
::ty
::fold
::{TypeFoldable, TypeVisitor}
;
3 use rustc_middle
::ty
::{self, Ty, TyCtxt}
;
4 use rustc_span
::source_map
::Span
;
6 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
7 pub struct Parameter(pub u32);
9 impl From
<ty
::ParamTy
> for Parameter
{
10 fn from(param
: ty
::ParamTy
) -> Self {
11 Parameter(param
.index
)
15 impl From
<ty
::EarlyBoundRegion
> for Parameter
{
16 fn from(param
: ty
::EarlyBoundRegion
) -> Self {
17 Parameter(param
.index
)
21 impl From
<ty
::ParamConst
> for Parameter
{
22 fn from(param
: ty
::ParamConst
) -> Self {
23 Parameter(param
.index
)
27 /// Returns the set of parameters constrained by the impl header.
28 pub fn parameters_for_impl
<'tcx
>(
29 impl_self_ty
: Ty
<'tcx
>,
30 impl_trait_ref
: Option
<ty
::TraitRef
<'tcx
>>,
31 ) -> FxHashSet
<Parameter
> {
32 let vec
= match impl_trait_ref
{
33 Some(tr
) => parameters_for(&tr
, false),
34 None
=> parameters_for(&impl_self_ty
, false),
36 vec
.into_iter().collect()
39 /// If `include_nonconstraining` is false, returns the list of parameters that are
40 /// constrained by `t` - i.e., the value of each parameter in the list is
41 /// uniquely determined by `t` (see RFC 447). If it is true, return the list
42 /// of parameters whose values are needed in order to constrain `ty` - these
43 /// differ, with the latter being a superset, in the presence of projections.
44 pub fn parameters_for
<'tcx
>(
45 t
: &impl TypeFoldable
<'tcx
>,
46 include_nonconstraining
: bool
,
48 let mut collector
= ParameterCollector { parameters: vec![], include_nonconstraining }
;
49 t
.visit_with(&mut collector
);
53 struct ParameterCollector
{
54 parameters
: Vec
<Parameter
>,
55 include_nonconstraining
: bool
,
58 impl<'tcx
> TypeVisitor
<'tcx
> for ParameterCollector
{
59 fn visit_ty(&mut self, t
: Ty
<'tcx
>) -> bool
{
61 ty
::Projection(..) | ty
::Opaque(..) if !self.include_nonconstraining
=> {
62 // projections are not injective
66 self.parameters
.push(Parameter
::from(data
));
71 t
.super_visit_with(self)
74 fn visit_region(&mut self, r
: ty
::Region
<'tcx
>) -> bool
{
75 if let ty
::ReEarlyBound(data
) = *r
{
76 self.parameters
.push(Parameter
::from(data
));
81 fn visit_const(&mut self, c
: &'tcx ty
::Const
<'tcx
>) -> bool
{
83 ty
::ConstKind
::Unevaluated(..) if !self.include_nonconstraining
=> {
84 // Constant expressions are not injective
85 return c
.ty
.visit_with(self);
87 ty
::ConstKind
::Param(data
) => {
88 self.parameters
.push(Parameter
::from(data
));
93 c
.super_visit_with(self)
97 pub fn identify_constrained_generic_params
<'tcx
>(
99 predicates
: ty
::GenericPredicates
<'tcx
>,
100 impl_trait_ref
: Option
<ty
::TraitRef
<'tcx
>>,
101 input_parameters
: &mut FxHashSet
<Parameter
>,
103 let mut predicates
= predicates
.predicates
.to_vec();
104 setup_constraining_predicates(tcx
, &mut predicates
, impl_trait_ref
, input_parameters
);
107 /// Order the predicates in `predicates` such that each parameter is
108 /// constrained before it is used, if that is possible, and add the
109 /// parameters so constrained to `input_parameters`. For example,
110 /// imagine the following impl:
112 /// impl<T: Debug, U: Iterator<Item = T>> Trait for U
114 /// The impl's predicates are collected from left to right. Ignoring
115 /// the implicit `Sized` bounds, these are
118 /// * <U as Iterator>::Item = T -- a desugared ProjectionPredicate
120 /// When we, for example, try to go over the trait-reference
121 /// `IntoIter<u32> as Trait`, we substitute the impl parameters with fresh
122 /// variables and match them with the impl trait-ref, so we know that
123 /// `$U = IntoIter<u32>`.
125 /// However, in order to process the `$T: Debug` predicate, we must first
126 /// know the value of `$T` - which is only given by processing the
127 /// projection. As we occasionally want to process predicates in a single
128 /// pass, we want the projection to come first. In fact, as projections
129 /// can (acyclically) depend on one another - see RFC447 for details - we
130 /// need to topologically sort them.
132 /// We *do* have to be somewhat careful when projection targets contain
133 /// projections themselves, for example in
134 /// impl<S,U,V,W> Trait for U where
135 /// /* 0 */ S: Iterator<Item = U>,
136 /// /* - */ U: Iterator,
137 /// /* 1 */ <U as Iterator>::Item: ToOwned<Owned=(W,<V as Iterator>::Item)>
138 /// /* 2 */ W: Iterator<Item = V>
140 /// we have to evaluate the projections in the order I wrote them:
141 /// `V: Debug` requires `V` to be evaluated. The only projection that
142 /// *determines* `V` is 2 (1 contains it, but *does not determine it*,
143 /// as it is only contained within a projection), but that requires `W`
144 /// which is determined by 1, which requires `U`, that is determined
145 /// by 0. I should probably pick a less tangled example, but I can't
147 pub fn setup_constraining_predicates
<'tcx
>(
149 predicates
: &mut [(ty
::Predicate
<'tcx
>, Span
)],
150 impl_trait_ref
: Option
<ty
::TraitRef
<'tcx
>>,
151 input_parameters
: &mut FxHashSet
<Parameter
>,
153 // The canonical way of doing the needed topological sort
154 // would be a DFS, but getting the graph and its ownership
155 // right is annoying, so I am using an in-place fixed-point iteration,
156 // which is `O(nt)` where `t` is the depth of type-parameter constraints,
157 // remembering that `t` should be less than 7 in practice.
159 // Basically, I iterate over all projections and swap every
160 // "ready" projection to the start of the list, such that
161 // all of the projections before `i` are topologically sorted
162 // and constrain all the parameters in `input_parameters`.
164 // In the example, `input_parameters` starts by containing `U` - which
165 // is constrained by the trait-ref - and so on the first pass we
166 // observe that `<U as Iterator>::Item = T` is a "ready" projection that
167 // constrains `T` and swap it to front. As it is the sole projection,
168 // no more swaps can take place afterwards, with the result being
169 // * <U as Iterator>::Item = T
173 "setup_constraining_predicates: predicates={:?} \
174 impl_trait_ref={:?} input_parameters={:?}",
175 predicates
, impl_trait_ref
, input_parameters
178 let mut changed
= true;
182 for j
in i
..predicates
.len() {
183 if let ty
::Predicate
::Projection(ref poly_projection
) = predicates
[j
].0 {
184 // Note that we can skip binder here because the impl
185 // trait ref never contains any late-bound regions.
186 let projection
= poly_projection
.skip_binder();
188 // Special case: watch out for some kind of sneaky attempt
189 // to project out an associated type defined by this very
191 let unbound_trait_ref
= projection
.projection_ty
.trait_ref(tcx
);
192 if Some(unbound_trait_ref
) == impl_trait_ref
{
196 // A projection depends on its input types and determines its output
197 // type. For example, if we have
198 // `<<T as Bar>::Baz as Iterator>::Output = <U as Iterator>::Output`
199 // Then the projection only applies if `T` is known, but it still
200 // does not determine `U`.
201 let inputs
= parameters_for(&projection
.projection_ty
.trait_ref(tcx
), true);
202 let relies_only_on_inputs
= inputs
.iter().all(|p
| input_parameters
.contains(&p
));
203 if !relies_only_on_inputs
{
206 input_parameters
.extend(parameters_for(&projection
.ty
, false));
210 // fancy control flow to bypass borrow checker
211 predicates
.swap(i
, j
);
216 "setup_constraining_predicates: predicates={:?} \
217 i={} impl_trait_ref={:?} input_parameters={:?}",
218 predicates
, i
, impl_trait_ref
, input_parameters