1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
use crate::mir::Mutability;
use crate::ty::{self, Ty, TyCtxt};
use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
use rustc_hir::def_id::DefId;
use rustc_query_system::ich::StableHashingContext;
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;
use self::SimplifiedTypeGen::*;
pub type SimplifiedType = SimplifiedTypeGen<DefId>;
/// See `simplify_type`
///
/// Note that we keep this type generic over the type of identifier it uses
/// because we sometimes need to use SimplifiedTypeGen values as stable sorting
/// keys (in which case we use a DefPathHash as id-type) but in the general case
/// the non-stable but fast to construct DefId-version is the better choice.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, TyEncodable, TyDecodable)]
pub enum SimplifiedTypeGen<D>
where
D: Copy + Debug + Eq,
{
BoolSimplifiedType,
CharSimplifiedType,
IntSimplifiedType(ty::IntTy),
UintSimplifiedType(ty::UintTy),
FloatSimplifiedType(ty::FloatTy),
AdtSimplifiedType(D),
ForeignSimplifiedType(D),
StrSimplifiedType,
ArraySimplifiedType,
SliceSimplifiedType,
RefSimplifiedType(Mutability),
PtrSimplifiedType(Mutability),
NeverSimplifiedType,
TupleSimplifiedType(usize),
/// A trait object, all of whose components are markers
/// (e.g., `dyn Send + Sync`).
MarkerTraitObjectSimplifiedType,
TraitSimplifiedType(D),
ClosureSimplifiedType(D),
GeneratorSimplifiedType(D),
GeneratorWitnessSimplifiedType(usize),
OpaqueSimplifiedType(D),
FunctionSimplifiedType(usize),
ParameterSimplifiedType,
}
#[derive(PartialEq, Eq, Debug, Clone, Copy)]
pub enum TreatParams {
/// Treat parameters as bound types in the given environment.
///
/// For this to be correct the input has to be fully normalized
/// in its param env as it may otherwise cause us to ignore
/// potentially applying impls.
AsBoundTypes,
AsPlaceholders,
}
/// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists.
///
/// The idea is to get something simple that we can use to quickly decide if two types could unify,
/// for example during method lookup.
///
/// A special case here are parameters and projections, which are only injective
/// if they are treated as bound types.
///
/// For example when storing impls based on their simplified self type, we treat
/// generic parameters as placeholders. We must not simplify them here,
/// as they can unify with any other type.
///
/// With projections we have to be even more careful, as even when treating them as bound types
/// this is still only correct if they are fully normalized.
///
/// ¹ meaning that if the outermost layers are different, then the whole types are also different.
pub fn simplify_type<'tcx>(
tcx: TyCtxt<'tcx>,
ty: Ty<'tcx>,
treat_params: TreatParams,
) -> Option<SimplifiedType> {
match *ty.kind() {
ty::Bool => Some(BoolSimplifiedType),
ty::Char => Some(CharSimplifiedType),
ty::Int(int_type) => Some(IntSimplifiedType(int_type)),
ty::Uint(uint_type) => Some(UintSimplifiedType(uint_type)),
ty::Float(float_type) => Some(FloatSimplifiedType(float_type)),
ty::Adt(def, _) => Some(AdtSimplifiedType(def.did())),
ty::Str => Some(StrSimplifiedType),
ty::Array(..) => Some(ArraySimplifiedType),
ty::Slice(..) => Some(SliceSimplifiedType),
ty::RawPtr(ptr) => Some(PtrSimplifiedType(ptr.mutbl)),
ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() {
Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => {
Some(TraitSimplifiedType(principal_def_id))
}
_ => Some(MarkerTraitObjectSimplifiedType),
},
ty::Ref(_, _, mutbl) => Some(RefSimplifiedType(mutbl)),
ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)),
ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)),
ty::GeneratorWitness(tys) => Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len())),
ty::Never => Some(NeverSimplifiedType),
ty::Tuple(tys) => Some(TupleSimplifiedType(tys.len())),
ty::FnPtr(f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())),
ty::Param(_) | ty::Projection(_) => match treat_params {
// When treated as bound types, projections don't unify with
// anything as long as they are fully normalized.
//
// We will have to be careful with lazy normalization here.
TreatParams::AsBoundTypes => {
debug!("treating `{}` as a bound type", ty);
Some(ParameterSimplifiedType)
}
TreatParams::AsPlaceholders => None,
},
ty::Opaque(def_id, _) => Some(OpaqueSimplifiedType(def_id)),
ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)),
ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None,
}
}
impl<D: Copy + Debug + Eq> SimplifiedTypeGen<D> {
pub fn def(self) -> Option<D> {
match self {
AdtSimplifiedType(d)
| ForeignSimplifiedType(d)
| TraitSimplifiedType(d)
| ClosureSimplifiedType(d)
| GeneratorSimplifiedType(d)
| OpaqueSimplifiedType(d) => Some(d),
_ => None,
}
}
pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U>
where
F: Fn(D) -> U,
U: Copy + Debug + Eq,
{
match self {
BoolSimplifiedType => BoolSimplifiedType,
CharSimplifiedType => CharSimplifiedType,
IntSimplifiedType(t) => IntSimplifiedType(t),
UintSimplifiedType(t) => UintSimplifiedType(t),
FloatSimplifiedType(t) => FloatSimplifiedType(t),
AdtSimplifiedType(d) => AdtSimplifiedType(map(d)),
ForeignSimplifiedType(d) => ForeignSimplifiedType(map(d)),
StrSimplifiedType => StrSimplifiedType,
ArraySimplifiedType => ArraySimplifiedType,
SliceSimplifiedType => SliceSimplifiedType,
RefSimplifiedType(m) => RefSimplifiedType(m),
PtrSimplifiedType(m) => PtrSimplifiedType(m),
NeverSimplifiedType => NeverSimplifiedType,
MarkerTraitObjectSimplifiedType => MarkerTraitObjectSimplifiedType,
TupleSimplifiedType(n) => TupleSimplifiedType(n),
TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
GeneratorWitnessSimplifiedType(n) => GeneratorWitnessSimplifiedType(n),
OpaqueSimplifiedType(d) => OpaqueSimplifiedType(map(d)),
FunctionSimplifiedType(n) => FunctionSimplifiedType(n),
ParameterSimplifiedType => ParameterSimplifiedType,
}
}
}
impl<'a, D> HashStable<StableHashingContext<'a>> for SimplifiedTypeGen<D>
where
D: Copy + Debug + Eq + HashStable<StableHashingContext<'a>>,
{
fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
mem::discriminant(self).hash_stable(hcx, hasher);
match *self {
BoolSimplifiedType
| CharSimplifiedType
| StrSimplifiedType
| ArraySimplifiedType
| SliceSimplifiedType
| NeverSimplifiedType
| ParameterSimplifiedType
| MarkerTraitObjectSimplifiedType => {
// nothing to do
}
RefSimplifiedType(m) | PtrSimplifiedType(m) => m.hash_stable(hcx, hasher),
IntSimplifiedType(t) => t.hash_stable(hcx, hasher),
UintSimplifiedType(t) => t.hash_stable(hcx, hasher),
FloatSimplifiedType(t) => t.hash_stable(hcx, hasher),
AdtSimplifiedType(d) => d.hash_stable(hcx, hasher),
TupleSimplifiedType(n) => n.hash_stable(hcx, hasher),
TraitSimplifiedType(d) => d.hash_stable(hcx, hasher),
ClosureSimplifiedType(d) => d.hash_stable(hcx, hasher),
GeneratorSimplifiedType(d) => d.hash_stable(hcx, hasher),
GeneratorWitnessSimplifiedType(n) => n.hash_stable(hcx, hasher),
OpaqueSimplifiedType(d) => d.hash_stable(hcx, hasher),
FunctionSimplifiedType(n) => n.hash_stable(hcx, hasher),
ForeignSimplifiedType(d) => d.hash_stable(hcx, hasher),
}
}
}
|
