]>
Commit | Line | Data |
---|---|---|
2b03887a | 1 | use crate::ty::context::TyCtxt; |
353b0b11 | 2 | use crate::ty::{self, DefId, ParamEnv, Ty}; |
2b03887a FG |
3 | |
4 | /// Represents whether some type is inhabited in a given context. | |
5 | /// Examples of uninhabited types are `!`, `enum Void {}`, or a struct | |
6 | /// containing either of those types. | |
7 | /// A type's inhabitedness may depend on the `ParamEnv` as well as what types | |
8 | /// are visible in the current module. | |
9 | #[derive(Clone, Copy, Debug, PartialEq, HashStable)] | |
10 | pub enum InhabitedPredicate<'tcx> { | |
11 | /// Inhabited | |
12 | True, | |
13 | /// Uninhabited | |
14 | False, | |
15 | /// Uninhabited when a const value is non-zero. This occurs when there is an | |
16 | /// array of uninhabited items, but the array is inhabited if it is empty. | |
17 | ConstIsZero(ty::Const<'tcx>), | |
18 | /// Uninhabited if within a certain module. This occurs when an uninhabited | |
19 | /// type has restricted visibility. | |
20 | NotInModule(DefId), | |
21 | /// Inhabited if some generic type is inhabited. | |
22 | /// These are replaced by calling [`Self::subst`]. | |
23 | GenericType(Ty<'tcx>), | |
24 | /// A AND B | |
25 | And(&'tcx [InhabitedPredicate<'tcx>; 2]), | |
26 | /// A OR B | |
27 | Or(&'tcx [InhabitedPredicate<'tcx>; 2]), | |
28 | } | |
29 | ||
30 | impl<'tcx> InhabitedPredicate<'tcx> { | |
31 | /// Returns true if the corresponding type is inhabited in the given | |
32 | /// `ParamEnv` and module | |
33 | pub fn apply(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>, module_def_id: DefId) -> bool { | |
34 | let Ok(result) = self | |
35 | .apply_inner::<!>(tcx, param_env, &|id| Ok(tcx.is_descendant_of(module_def_id, id))); | |
36 | result | |
37 | } | |
38 | ||
39 | /// Same as `apply`, but returns `None` if self contains a module predicate | |
40 | pub fn apply_any_module(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>) -> Option<bool> { | |
41 | self.apply_inner(tcx, param_env, &|_| Err(())).ok() | |
42 | } | |
43 | ||
487cf647 FG |
44 | /// Same as `apply`, but `NotInModule(_)` predicates yield `false`. That is, |
45 | /// privately uninhabited types are considered always uninhabited. | |
46 | pub fn apply_ignore_module(self, tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>) -> bool { | |
47 | let Ok(result) = self.apply_inner::<!>(tcx, param_env, &|_| Ok(true)); | |
48 | result | |
49 | } | |
50 | ||
2b03887a FG |
51 | fn apply_inner<E>( |
52 | self, | |
53 | tcx: TyCtxt<'tcx>, | |
54 | param_env: ParamEnv<'tcx>, | |
55 | in_module: &impl Fn(DefId) -> Result<bool, E>, | |
56 | ) -> Result<bool, E> { | |
57 | match self { | |
58 | Self::False => Ok(false), | |
59 | Self::True => Ok(true), | |
9ffffee4 | 60 | Self::ConstIsZero(const_) => match const_.try_eval_target_usize(tcx, param_env) { |
2b03887a FG |
61 | None | Some(0) => Ok(true), |
62 | Some(1..) => Ok(false), | |
63 | }, | |
64 | Self::NotInModule(id) => in_module(id).map(|in_mod| !in_mod), | |
65 | Self::GenericType(_) => Ok(true), | |
66 | Self::And([a, b]) => try_and(a, b, |x| x.apply_inner(tcx, param_env, in_module)), | |
67 | Self::Or([a, b]) => try_or(a, b, |x| x.apply_inner(tcx, param_env, in_module)), | |
68 | } | |
69 | } | |
70 | ||
71 | pub fn and(self, tcx: TyCtxt<'tcx>, other: Self) -> Self { | |
72 | self.reduce_and(tcx, other).unwrap_or_else(|| Self::And(tcx.arena.alloc([self, other]))) | |
73 | } | |
74 | ||
75 | pub fn or(self, tcx: TyCtxt<'tcx>, other: Self) -> Self { | |
76 | self.reduce_or(tcx, other).unwrap_or_else(|| Self::Or(tcx.arena.alloc([self, other]))) | |
77 | } | |
78 | ||
79 | pub fn all(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self { | |
80 | let mut result = Self::True; | |
81 | for pred in iter { | |
82 | if matches!(pred, Self::False) { | |
83 | return Self::False; | |
84 | } | |
85 | result = result.and(tcx, pred); | |
86 | } | |
87 | result | |
88 | } | |
89 | ||
90 | pub fn any(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self { | |
91 | let mut result = Self::False; | |
92 | for pred in iter { | |
93 | if matches!(pred, Self::True) { | |
94 | return Self::True; | |
95 | } | |
96 | result = result.or(tcx, pred); | |
97 | } | |
98 | result | |
99 | } | |
100 | ||
101 | fn reduce_and(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> { | |
102 | match (self, other) { | |
103 | (Self::True, a) | (a, Self::True) => Some(a), | |
104 | (Self::False, _) | (_, Self::False) => Some(Self::False), | |
105 | (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)), | |
106 | (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)), | |
107 | (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => { | |
108 | Some(Self::NotInModule(b)) | |
109 | } | |
110 | (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => { | |
111 | Some(Self::NotInModule(a)) | |
112 | } | |
113 | (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)), | |
114 | (Self::And(&[a, b]), c) | (c, Self::And(&[a, b])) => { | |
115 | if let Some(ac) = a.reduce_and(tcx, c) { | |
116 | Some(ac.and(tcx, b)) | |
117 | } else if let Some(bc) = b.reduce_and(tcx, c) { | |
118 | Some(Self::And(tcx.arena.alloc([a, bc]))) | |
119 | } else { | |
120 | None | |
121 | } | |
122 | } | |
123 | _ => None, | |
124 | } | |
125 | } | |
126 | ||
127 | fn reduce_or(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> { | |
128 | match (self, other) { | |
129 | (Self::True, _) | (_, Self::True) => Some(Self::True), | |
130 | (Self::False, a) | (a, Self::False) => Some(a), | |
131 | (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)), | |
132 | (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)), | |
133 | (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => { | |
134 | Some(Self::NotInModule(a)) | |
135 | } | |
136 | (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => { | |
137 | Some(Self::NotInModule(b)) | |
138 | } | |
139 | (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)), | |
140 | (Self::Or(&[a, b]), c) | (c, Self::Or(&[a, b])) => { | |
141 | if let Some(ac) = a.reduce_or(tcx, c) { | |
142 | Some(ac.or(tcx, b)) | |
143 | } else if let Some(bc) = b.reduce_or(tcx, c) { | |
144 | Some(Self::Or(tcx.arena.alloc([a, bc]))) | |
145 | } else { | |
146 | None | |
147 | } | |
148 | } | |
149 | _ => None, | |
150 | } | |
151 | } | |
152 | ||
153 | /// Replaces generic types with its corresponding predicate | |
154 | pub fn subst(self, tcx: TyCtxt<'tcx>, substs: ty::SubstsRef<'tcx>) -> Self { | |
155 | self.subst_opt(tcx, substs).unwrap_or(self) | |
156 | } | |
157 | ||
158 | fn subst_opt(self, tcx: TyCtxt<'tcx>, substs: ty::SubstsRef<'tcx>) -> Option<Self> { | |
159 | match self { | |
160 | Self::ConstIsZero(c) => { | |
161 | let c = ty::EarlyBinder(c).subst(tcx, substs); | |
9ffffee4 | 162 | let pred = match c.kind().try_to_target_usize(tcx) { |
2b03887a FG |
163 | Some(0) => Self::True, |
164 | Some(1..) => Self::False, | |
165 | None => Self::ConstIsZero(c), | |
166 | }; | |
167 | Some(pred) | |
168 | } | |
169 | Self::GenericType(t) => { | |
170 | Some(ty::EarlyBinder(t).subst(tcx, substs).inhabited_predicate(tcx)) | |
171 | } | |
172 | Self::And(&[a, b]) => match a.subst_opt(tcx, substs) { | |
173 | None => b.subst_opt(tcx, substs).map(|b| a.and(tcx, b)), | |
174 | Some(InhabitedPredicate::False) => Some(InhabitedPredicate::False), | |
175 | Some(a) => Some(a.and(tcx, b.subst_opt(tcx, substs).unwrap_or(b))), | |
176 | }, | |
177 | Self::Or(&[a, b]) => match a.subst_opt(tcx, substs) { | |
178 | None => b.subst_opt(tcx, substs).map(|b| a.or(tcx, b)), | |
179 | Some(InhabitedPredicate::True) => Some(InhabitedPredicate::True), | |
180 | Some(a) => Some(a.or(tcx, b.subst_opt(tcx, substs).unwrap_or(b))), | |
181 | }, | |
182 | _ => None, | |
183 | } | |
184 | } | |
185 | } | |
186 | ||
187 | // this is basically like `f(a)? && f(b)?` but different in the case of | |
188 | // `Ok(false) && Err(_) -> Ok(false)` | |
189 | fn try_and<T, E>(a: T, b: T, f: impl Fn(T) -> Result<bool, E>) -> Result<bool, E> { | |
190 | let a = f(a); | |
191 | if matches!(a, Ok(false)) { | |
192 | return Ok(false); | |
193 | } | |
194 | match (a, f(b)) { | |
195 | (_, Ok(false)) | (Ok(false), _) => Ok(false), | |
196 | (Ok(true), Ok(true)) => Ok(true), | |
197 | (Err(e), _) | (_, Err(e)) => Err(e), | |
198 | } | |
199 | } | |
200 | ||
201 | fn try_or<T, E>(a: T, b: T, f: impl Fn(T) -> Result<bool, E>) -> Result<bool, E> { | |
202 | let a = f(a); | |
203 | if matches!(a, Ok(true)) { | |
204 | return Ok(true); | |
205 | } | |
206 | match (a, f(b)) { | |
207 | (_, Ok(true)) | (Ok(true), _) => Ok(true), | |
208 | (Ok(false), Ok(false)) => Ok(false), | |
209 | (Err(e), _) | (_, Err(e)) => Err(e), | |
210 | } | |
211 | } |