1use rustc_macros::HashStable;
2use smallvec::SmallVec;
3use tracing::instrument;
4
5use crate::ty::context::TyCtxt;
6use crate::ty::{self, DefId, OpaqueTypeKey, Ty, TypingEnv};
7
8#[derive(Clone, Copy, Debug, PartialEq, HashStable)]
14pub enum InhabitedPredicate<'tcx> {
15 True,
17 False,
19 ConstIsZero(ty::Const<'tcx>),
22 NotInModule(DefId),
25 GenericType(Ty<'tcx>),
28 OpaqueType(OpaqueTypeKey<'tcx>),
30 And(&'tcx [InhabitedPredicate<'tcx>; 2]),
32 Or(&'tcx [InhabitedPredicate<'tcx>; 2]),
34}
35
36impl<'tcx> InhabitedPredicate<'tcx> {
37 pub fn apply(
39 self,
40 tcx: TyCtxt<'tcx>,
41 typing_env: TypingEnv<'tcx>,
42 module_def_id: DefId,
43 ) -> bool {
44 self.apply_revealing_opaque(tcx, typing_env, module_def_id, &|_| None)
45 }
46
47 pub fn apply_revealing_opaque(
50 self,
51 tcx: TyCtxt<'tcx>,
52 typing_env: TypingEnv<'tcx>,
53 module_def_id: DefId,
54 reveal_opaque: &impl Fn(OpaqueTypeKey<'tcx>) -> Option<Ty<'tcx>>,
55 ) -> bool {
56 let Ok(result) = self.apply_inner::<!>(
57 tcx,
58 typing_env,
59 &mut Default::default(),
60 &|id| Ok(tcx.is_descendant_of(module_def_id, id)),
61 reveal_opaque,
62 );
63 result
64 }
65
66 pub fn apply_any_module(self, tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>) -> Option<bool> {
68 self.apply_inner(tcx, typing_env, &mut Default::default(), &|_| Err(()), &|_| None).ok()
69 }
70
71 pub fn apply_ignore_module(self, tcx: TyCtxt<'tcx>, typing_env: TypingEnv<'tcx>) -> bool {
74 let Ok(result) =
75 self.apply_inner::<!>(tcx, typing_env, &mut Default::default(), &|_| Ok(true), &|_| {
76 None
77 });
78 result
79 }
80
81 #[instrument(level = "debug", skip(tcx, typing_env, in_module, reveal_opaque), ret)]
82 fn apply_inner<E: std::fmt::Debug>(
83 self,
84 tcx: TyCtxt<'tcx>,
85 typing_env: TypingEnv<'tcx>,
86 eval_stack: &mut SmallVec<[Ty<'tcx>; 1]>, in_module: &impl Fn(DefId) -> Result<bool, E>,
88 reveal_opaque: &impl Fn(OpaqueTypeKey<'tcx>) -> Option<Ty<'tcx>>,
89 ) -> Result<bool, E> {
90 match self {
91 Self::False => Ok(false),
92 Self::True => Ok(true),
93 Self::ConstIsZero(const_) => match const_.try_to_target_usize(tcx) {
94 None | Some(0) => Ok(true),
95 Some(1..) => Ok(false),
96 },
97 Self::NotInModule(id) => in_module(id).map(|in_mod| !in_mod),
98 Self::GenericType(t) => {
101 let normalized_pred = tcx
102 .try_normalize_erasing_regions(typing_env, t)
103 .map_or(self, |t| t.inhabited_predicate(tcx));
104 match normalized_pred {
105 Self::GenericType(_) => Ok(true),
107 pred => {
108 if eval_stack.contains(&t) {
111 return Ok(true); }
113 eval_stack.push(t);
114 let ret =
115 pred.apply_inner(tcx, typing_env, eval_stack, in_module, reveal_opaque);
116 eval_stack.pop();
117 ret
118 }
119 }
120 }
121 Self::OpaqueType(key) => match reveal_opaque(key) {
122 None => Ok(true),
124 Some(t) => {
126 if eval_stack.contains(&t) {
129 return Ok(true); }
131 eval_stack.push(t);
132 let ret = t.inhabited_predicate(tcx).apply_inner(
133 tcx,
134 typing_env,
135 eval_stack,
136 in_module,
137 reveal_opaque,
138 );
139 eval_stack.pop();
140 ret
141 }
142 },
143 Self::And([a, b]) => try_and(a, b, |x| {
144 x.apply_inner(tcx, typing_env, eval_stack, in_module, reveal_opaque)
145 }),
146 Self::Or([a, b]) => try_or(a, b, |x| {
147 x.apply_inner(tcx, typing_env, eval_stack, in_module, reveal_opaque)
148 }),
149 }
150 }
151
152 pub fn and(self, tcx: TyCtxt<'tcx>, other: Self) -> Self {
153 self.reduce_and(tcx, other).unwrap_or_else(|| Self::And(tcx.arena.alloc([self, other])))
154 }
155
156 pub fn or(self, tcx: TyCtxt<'tcx>, other: Self) -> Self {
157 self.reduce_or(tcx, other).unwrap_or_else(|| Self::Or(tcx.arena.alloc([self, other])))
158 }
159
160 pub fn all(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self {
161 let mut result = Self::True;
162 for pred in iter {
163 if matches!(pred, Self::False) {
164 return Self::False;
165 }
166 result = result.and(tcx, pred);
167 }
168 result
169 }
170
171 pub fn any(tcx: TyCtxt<'tcx>, iter: impl IntoIterator<Item = Self>) -> Self {
172 let mut result = Self::False;
173 for pred in iter {
174 if matches!(pred, Self::True) {
175 return Self::True;
176 }
177 result = result.or(tcx, pred);
178 }
179 result
180 }
181
182 fn reduce_and(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> {
183 match (self, other) {
184 (Self::True, a) | (a, Self::True) => Some(a),
185 (Self::False, _) | (_, Self::False) => Some(Self::False),
186 (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)),
187 (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)),
188 (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => {
189 Some(Self::NotInModule(b))
190 }
191 (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => {
192 Some(Self::NotInModule(a))
193 }
194 (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)),
195 (Self::And(&[a, b]), c) | (c, Self::And(&[a, b])) => {
196 if let Some(ac) = a.reduce_and(tcx, c) {
197 Some(ac.and(tcx, b))
198 } else if let Some(bc) = b.reduce_and(tcx, c) {
199 Some(Self::And(tcx.arena.alloc([a, bc])))
200 } else {
201 None
202 }
203 }
204 _ => None,
205 }
206 }
207
208 fn reduce_or(self, tcx: TyCtxt<'tcx>, other: Self) -> Option<Self> {
209 match (self, other) {
210 (Self::True, _) | (_, Self::True) => Some(Self::True),
211 (Self::False, a) | (a, Self::False) => Some(a),
212 (Self::ConstIsZero(a), Self::ConstIsZero(b)) if a == b => Some(Self::ConstIsZero(a)),
213 (Self::NotInModule(a), Self::NotInModule(b)) if a == b => Some(Self::NotInModule(a)),
214 (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(a, b) => {
215 Some(Self::NotInModule(a))
216 }
217 (Self::NotInModule(a), Self::NotInModule(b)) if tcx.is_descendant_of(b, a) => {
218 Some(Self::NotInModule(b))
219 }
220 (Self::GenericType(a), Self::GenericType(b)) if a == b => Some(Self::GenericType(a)),
221 (Self::Or(&[a, b]), c) | (c, Self::Or(&[a, b])) => {
222 if let Some(ac) = a.reduce_or(tcx, c) {
223 Some(ac.or(tcx, b))
224 } else if let Some(bc) = b.reduce_or(tcx, c) {
225 Some(Self::Or(tcx.arena.alloc([a, bc])))
226 } else {
227 None
228 }
229 }
230 _ => None,
231 }
232 }
233
234 pub fn instantiate(self, tcx: TyCtxt<'tcx>, args: ty::GenericArgsRef<'tcx>) -> Self {
236 self.instantiate_opt(tcx, args).unwrap_or(self)
237 }
238
239 fn instantiate_opt(self, tcx: TyCtxt<'tcx>, args: ty::GenericArgsRef<'tcx>) -> Option<Self> {
245 match self {
246 Self::ConstIsZero(c) => {
247 let c = ty::EarlyBinder::bind(c).instantiate(tcx, args);
248 let pred = match c.try_to_target_usize(tcx) {
249 Some(0) => Self::True,
250 Some(1..) => Self::False,
251 None => Self::ConstIsZero(c),
252 };
253 Some(pred)
254 }
255 Self::GenericType(t) => {
256 Some(ty::EarlyBinder::bind(t).instantiate(tcx, args).inhabited_predicate(tcx))
257 }
258 Self::And(&[a, b]) => match a.instantiate_opt(tcx, args) {
259 None => b.instantiate_opt(tcx, args).map(|b| a.and(tcx, b)),
260 Some(InhabitedPredicate::False) => Some(InhabitedPredicate::False),
261 Some(a) => Some(a.and(tcx, b.instantiate_opt(tcx, args).unwrap_or(b))),
262 },
263 Self::Or(&[a, b]) => match a.instantiate_opt(tcx, args) {
264 None => b.instantiate_opt(tcx, args).map(|b| a.or(tcx, b)),
265 Some(InhabitedPredicate::True) => Some(InhabitedPredicate::True),
266 Some(a) => Some(a.or(tcx, b.instantiate_opt(tcx, args).unwrap_or(b))),
267 },
268 Self::True | Self::False | Self::NotInModule(_) => None,
269 Self::OpaqueType(_) => {
270 bug!("unexpected OpaqueType in InhabitedPredicate");
271 }
272 }
273 }
274}
275
276fn try_and<T, E>(a: T, b: T, mut f: impl FnMut(T) -> Result<bool, E>) -> Result<bool, E> {
279 let a = f(a);
280 if matches!(a, Ok(false)) {
281 return Ok(false);
282 }
283 match (a, f(b)) {
284 (_, Ok(false)) | (Ok(false), _) => Ok(false),
285 (Ok(true), Ok(true)) => Ok(true),
286 (Err(e), _) | (_, Err(e)) => Err(e),
287 }
288}
289
290fn try_or<T, E>(a: T, b: T, mut f: impl FnMut(T) -> Result<bool, E>) -> Result<bool, E> {
291 let a = f(a);
292 if matches!(a, Ok(true)) {
293 return Ok(true);
294 }
295 match (a, f(b)) {
296 (_, Ok(true)) | (Ok(true), _) => Ok(true),
297 (Ok(false), Ok(false)) => Ok(false),
298 (Err(e), _) | (_, Err(e)) => Err(e),
299 }
300}