1 use crate::ty
::context
::TyCtxt
;
2 use crate::ty
::{self, DefId, DefIdTree, ParamEnv, Ty}
;
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
> {
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.
21 /// Inhabited if some generic type is inhabited.
22 /// These are replaced by calling [`Self::subst`].
23 GenericType(Ty
<'tcx
>),
25 And(&'tcx
[InhabitedPredicate
<'tcx
>; 2]),
27 Or(&'tcx
[InhabitedPredicate
<'tcx
>; 2]),
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
{
35 .apply_inner
::<!>(tcx
, param_env
, &|id
| Ok(tcx
.is_descendant_of(module_def_id
, id
)));
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()
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));
54 param_env
: ParamEnv
<'tcx
>,
55 in_module
: &impl Fn(DefId
) -> Result
<bool
, E
>,
56 ) -> Result
<bool
, E
> {
58 Self::False
=> Ok(false),
59 Self::True
=> Ok(true),
60 Self::ConstIsZero(const_
) => match const_
.try_eval_usize(tcx
, param_env
) {
61 None
| Some(0) => Ok(true),
62 Some(1..) => Ok(false),
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
)),
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
])))
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
])))
79 pub fn all(tcx
: TyCtxt
<'tcx
>, iter
: impl IntoIterator
<Item
= Self>) -> Self {
80 let mut result
= Self::True
;
82 if matches
!(pred
, Self::False
) {
85 result
= result
.and(tcx
, pred
);
90 pub fn any(tcx
: TyCtxt
<'tcx
>, iter
: impl IntoIterator
<Item
= Self>) -> Self {
91 let mut result
= Self::False
;
93 if matches
!(pred
, Self::True
) {
96 result
= result
.or(tcx
, pred
);
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
))
110 (Self::NotInModule(a
), Self::NotInModule(b
)) if tcx
.is_descendant_of(b
, a
) => {
111 Some(Self::NotInModule(a
))
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
) {
117 } else if let Some(bc
) = b
.reduce_and(tcx
, c
) {
118 Some(Self::And(tcx
.arena
.alloc([a
, bc
])))
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
))
136 (Self::NotInModule(a
), Self::NotInModule(b
)) if tcx
.is_descendant_of(b
, a
) => {
137 Some(Self::NotInModule(b
))
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
) {
143 } else if let Some(bc
) = b
.reduce_or(tcx
, c
) {
144 Some(Self::Or(tcx
.arena
.alloc([a
, bc
])))
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)
158 fn subst_opt(self, tcx
: TyCtxt
<'tcx
>, substs
: ty
::SubstsRef
<'tcx
>) -> Option
<Self> {
160 Self::ConstIsZero(c
) => {
161 let c
= ty
::EarlyBinder(c
).subst(tcx
, substs
);
162 let pred
= match c
.kind().try_to_machine_usize(tcx
) {
163 Some(0) => Self::True
,
164 Some(1..) => Self::False
,
165 None
=> Self::ConstIsZero(c
),
169 Self::GenericType(t
) => {
170 Some(ty
::EarlyBinder(t
).subst(tcx
, substs
).inhabited_predicate(tcx
))
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
))),
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
))),
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
> {
191 if matches
!(a
, Ok(false)) {
195 (_
, Ok(false)) | (Ok(false), _
) => Ok(false),
196 (Ok(true), Ok(true)) => Ok(true),
197 (Err(e
), _
) | (_
, Err(e
)) => Err(e
),
201 fn try_or
<T
, E
>(a
: T
, b
: T
, f
: impl Fn(T
) -> Result
<bool
, E
>) -> Result
<bool
, E
> {
203 if matches
!(a
, Ok(true)) {
207 (_
, Ok(true)) | (Ok(true), _
) => Ok(true),
208 (Ok(false), Ok(false)) => Ok(false),
209 (Err(e
), _
) | (_
, Err(e
)) => Err(e
),