rustc_middle/ty/inhabitedness/
inhabited_predicate.rs

Help
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/// Represents whether some type is inhabited in a given context.
9/// Examples of uninhabited types are `!`, `enum Void {}`, or a struct
10/// containing either of those types.
11/// A type's inhabitedness may depend on the `ParamEnv` as well as what types
12/// are visible in the current module.
13#[derive(Clone, Copy, Debug, PartialEq, HashStable)]
14pub enum InhabitedPredicate<'tcx> {
15    /// Inhabited
16    True,
17    /// Uninhabited
18    False,
19    /// Uninhabited when a const value is non-zero. This occurs when there is an
20    /// array of uninhabited items, but the array is inhabited if it is empty.
21    ConstIsZero(ty::Const<'tcx>),
22    /// Uninhabited if within a certain module. This occurs when an uninhabited
23    /// type has restricted visibility.
24    NotInModule(DefId),
25    /// Inhabited if some generic type is inhabited.
26    /// These are replaced by calling [`Self::instantiate`].
27    GenericType(Ty<'tcx>),
28    /// Inhabited if either we don't know the hidden type or we know it and it is inhabited.
29    OpaqueType(OpaqueTypeKey<'tcx>),
30    /// A AND B
31    And(&'tcx [InhabitedPredicate<'tcx>; 2]),
32    /// A OR B
33    Or(&'tcx [InhabitedPredicate<'tcx>; 2]),
34}
35
36impl<'tcx> InhabitedPredicate<'tcx> {
37    /// Returns true if the corresponding type is inhabited in the given `ParamEnv` and module.
38    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    /// Returns true if the corresponding type is inhabited in the given `ParamEnv` and module,
48    /// revealing opaques when possible.
49    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    /// Same as `apply`, but returns `None` if self contains a module predicate
67    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    /// Same as `apply`, but `NotInModule(_)` predicates yield `false`. That is,
72    /// privately uninhabited types are considered always uninhabited.
73    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]>, // for cycle detection
87        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            // `t` may be a projection, for which `inhabited_predicate` returns a `GenericType`. As
99            // we have a param_env available, we can do better.
100            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                    // We don't have more information than we started with, so consider inhabited.
106                    Self::GenericType(_) => Ok(true),
107                    pred => {
108                        // A type which is cyclic when monomorphized can happen here since the
109                        // layout error would only trigger later. See e.g. `tests/ui/sized/recursive-type-2.rs`.
110                        if eval_stack.contains(&t) {
111                            return Ok(true); // Recover; this will error later.
112                        }
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                // Unknown opaque is assumed inhabited.
123                None => Ok(true),
124                // Known opaque type is inspected recursively.
125                Some(t) => {
126                    // A cyclic opaque type can happen in corner cases that would only error later.
127                    // See e.g. `tests/ui/type-alias-impl-trait/recursive-tait-conflicting-defn.rs`.
128                    if eval_stack.contains(&t) {
129                        return Ok(true); // Recover; this will error later.
130                    }
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    /// Replaces generic types with its corresponding predicate
235    pub fn instantiate(self, tcx: TyCtxt<'tcx>, args: ty::GenericArgsRef<'tcx>) -> Self {
236        self.instantiate_opt(tcx, args).unwrap_or(self)
237    }
238
239    /// Same as [`Self::instantiate`], but if there is no generics to
240    /// instantiate, returns `None`. This is useful because it lets us avoid
241    /// allocating a recursive copy of everything when the result is unchanged.
242    ///
243    /// Only used to implement `instantiate` itself.
244    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
276// this is basically like `f(a)? && f(b)?` but different in the case of
277// `Ok(false) && Err(_) -> Ok(false)`
278fn 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}
rustc_middle/ty/inhabitedness/inhabited_predicate.rs

rustc_middle/ty/inhabitedness/
inhabited_predicate.rs
