compiler/rustc_middle/src/ty/inhabitedness/inhabited_predicate.rs

   1 use crate::ty::context::TyCtxt;
   2 use crate::ty::{self, DefId, DefIdTree, ParamEnv, Ty};
   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
  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
  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),
  60             Self::ConstIsZero(const_) => match const_.try_eval_usize(tcx, param_env) {
  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);
 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),
 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 }