src/tools/rust-analyzer/crates/hir-ty/src/inhabitedness.rs

   1 //! Type inhabitedness logic.
   2 use std::ops::ControlFlow::{self, Break, Continue};
   3
   4 use chalk_ir::{
   5     visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
   6     DebruijnIndex,
   7 };
   8 use hir_def::{
   9     adt::VariantData, attr::Attrs, type_ref::ConstScalar, visibility::Visibility, AdtId,
  10     EnumVariantId, HasModule, Lookup, ModuleId, VariantId,
  11 };
  12
  13 use crate::{
  14     db::HirDatabase, Binders, ConcreteConst, Const, ConstValue, Interner, Substitution, Ty, TyKind,
  15 };
  16
  17 /// Checks whether a type is visibly uninhabited from a particular module.
  18 pub(crate) fn is_ty_uninhabited_from(ty: &Ty, target_mod: ModuleId, db: &dyn HirDatabase) -> bool {
  19     let mut uninhabited_from = UninhabitedFrom { target_mod, db };
  20     let inhabitedness = ty.visit_with(&mut uninhabited_from, DebruijnIndex::INNERMOST);
  21     inhabitedness == BREAK_VISIBLY_UNINHABITED
  22 }
  23
  24 /// Checks whether a variant is visibly uninhabited from a particular module.
  25 pub(crate) fn is_enum_variant_uninhabited_from(
  26     variant: EnumVariantId,
  27     subst: &Substitution,
  28     target_mod: ModuleId,
  29     db: &dyn HirDatabase,
  30 ) -> bool {
  31     let enum_data = db.enum_data(variant.parent);
  32     let vars_attrs = db.variants_attrs(variant.parent);
  33     let is_local = variant.parent.lookup(db.upcast()).container.krate() == target_mod.krate();
  34
  35     let mut uninhabited_from = UninhabitedFrom { target_mod, db };
  36     let inhabitedness = uninhabited_from.visit_variant(
  37         variant.into(),
  38         &enum_data.variants[variant.local_id].variant_data,
  39         subst,
  40         &vars_attrs[variant.local_id],
  41         is_local,
  42     );
  43     inhabitedness == BREAK_VISIBLY_UNINHABITED
  44 }
  45
  46 struct UninhabitedFrom<'a> {
  47     target_mod: ModuleId,
  48     db: &'a dyn HirDatabase,
  49 }
  50
  51 const CONTINUE_OPAQUELY_INHABITED: ControlFlow<VisiblyUninhabited> = Continue(());
  52 const BREAK_VISIBLY_UNINHABITED: ControlFlow<VisiblyUninhabited> = Break(VisiblyUninhabited);
  53 #[derive(PartialEq, Eq)]
  54 struct VisiblyUninhabited;
  55
  56 impl TypeVisitor<Interner> for UninhabitedFrom<'_> {
  57     type BreakTy = VisiblyUninhabited;
  58
  59     fn as_dyn(&mut self) -> &mut dyn TypeVisitor<Interner, BreakTy = VisiblyUninhabited> {
  60         self
  61     }
  62
  63     fn visit_ty(
  64         &mut self,
  65         ty: &Ty,
  66         outer_binder: DebruijnIndex,
  67     ) -> ControlFlow<VisiblyUninhabited> {
  68         match ty.kind(Interner) {
  69             TyKind::Adt(adt, subst) => self.visit_adt(adt.0, subst),
  70             TyKind::Never => BREAK_VISIBLY_UNINHABITED,
  71             TyKind::Tuple(..) => ty.super_visit_with(self, outer_binder),
  72             TyKind::Array(item_ty, len) => match try_usize_const(len) {
  73                 Some(0) | None => CONTINUE_OPAQUELY_INHABITED,
  74                 Some(1..) => item_ty.super_visit_with(self, outer_binder),
  75             },
  76
  77             TyKind::Ref(..) | _ => CONTINUE_OPAQUELY_INHABITED,
  78         }
  79     }
  80
  81     fn interner(&self) -> Interner {
  82         Interner
  83     }
  84 }
  85
  86 impl UninhabitedFrom<'_> {
  87     fn visit_adt(&mut self, adt: AdtId, subst: &Substitution) -> ControlFlow<VisiblyUninhabited> {
  88         let attrs = self.db.attrs(adt.into());
  89         let adt_non_exhaustive = attrs.by_key("non_exhaustive").exists();
  90         let is_local = adt.module(self.db.upcast()).krate() == self.target_mod.krate();
  91         if adt_non_exhaustive && !is_local {
  92             return CONTINUE_OPAQUELY_INHABITED;
  93         }
  94
  95         // An ADT is uninhabited iff all its variants uninhabited.
  96         match adt {
  97             // rustc: For now, `union`s are never considered uninhabited.
  98             AdtId::UnionId(_) => CONTINUE_OPAQUELY_INHABITED,
  99             AdtId::StructId(s) => {
 100                 let struct_data = self.db.struct_data(s);
 101                 self.visit_variant(s.into(), &struct_data.variant_data, subst, &attrs, is_local)
 102             }
 103             AdtId::EnumId(e) => {
 104                 let vars_attrs = self.db.variants_attrs(e);
 105                 let enum_data = self.db.enum_data(e);
 106
 107                 for (local_id, enum_var) in enum_data.variants.iter() {
 108                     let variant_inhabitedness = self.visit_variant(
 109                         EnumVariantId { parent: e, local_id }.into(),
 110                         &enum_var.variant_data,
 111                         subst,
 112                         &vars_attrs[local_id],
 113                         is_local,
 114                     );
 115                     match variant_inhabitedness {
 116                         Break(VisiblyUninhabited) => continue,
 117                         Continue(()) => return CONTINUE_OPAQUELY_INHABITED,
 118                     }
 119                 }
 120                 BREAK_VISIBLY_UNINHABITED
 121             }
 122         }
 123     }
 124
 125     fn visit_variant(
 126         &mut self,
 127         variant: VariantId,
 128         variant_data: &VariantData,
 129         subst: &Substitution,
 130         attrs: &Attrs,
 131         is_local: bool,
 132     ) -> ControlFlow<VisiblyUninhabited> {
 133         let non_exhaustive_field_list = attrs.by_key("non_exhaustive").exists();
 134         if non_exhaustive_field_list && !is_local {
 135             return CONTINUE_OPAQUELY_INHABITED;
 136         }
 137
 138         let is_enum = matches!(variant, VariantId::EnumVariantId(..));
 139         let field_tys = self.db.field_types(variant);
 140         let field_vis = self.db.field_visibilities(variant);
 141
 142         for (fid, _) in variant_data.fields().iter() {
 143             self.visit_field(field_vis[fid], &field_tys[fid], subst, is_enum)?;
 144         }
 145         CONTINUE_OPAQUELY_INHABITED
 146     }
 147
 148     fn visit_field(
 149         &mut self,
 150         vis: Visibility,
 151         ty: &Binders<Ty>,
 152         subst: &Substitution,
 153         is_enum: bool,
 154     ) -> ControlFlow<VisiblyUninhabited> {
 155         if is_enum || vis.is_visible_from(self.db.upcast(), self.target_mod) {
 156             let ty = ty.clone().substitute(Interner, subst);
 157             ty.visit_with(self, DebruijnIndex::INNERMOST)
 158         } else {
 159             CONTINUE_OPAQUELY_INHABITED
 160         }
 161     }
 162 }
 163
 164 fn try_usize_const(c: &Const) -> Option<u128> {
 165     let data = &c.data(Interner);
 166     if data.ty.kind(Interner) != &TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)) {
 167         return None;
 168     }
 169     match data.value {
 170         ConstValue::Concrete(ConcreteConst { interned: ConstScalar::UInt(value) }) => Some(value),
 171         _ => None,
 172     }
 173 }