compiler/rustc_middle/src/infer/unify_key.rs

   1 use crate::ty::{self, InferConst, Ty, TyCtxt};
   2 use rustc_data_structures::snapshot_vec;
   3 use rustc_data_structures::undo_log::UndoLogs;
   4 use rustc_data_structures::unify::{
   5     self, EqUnifyValue, InPlace, NoError, UnificationTable, UnifyKey, UnifyValue,
   6 };
   7 use rustc_span::def_id::DefId;
   8 use rustc_span::symbol::Symbol;
   9 use rustc_span::Span;
  10
  11 use std::cmp;
  12 use std::marker::PhantomData;
  13
  14 pub trait ToType {
  15     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx>;
  16 }
  17
  18 #[derive(PartialEq, Copy, Clone, Debug)]
  19 pub struct RegionVidKey {
  20     /// The minimum region vid in the unification set. This is needed
  21     /// to have a canonical name for a type to prevent infinite
  22     /// recursion.
  23     pub min_vid: ty::RegionVid,
  24 }
  25
  26 impl UnifyValue for RegionVidKey {
  27     type Error = NoError;
  28
  29     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
  30         let min_vid = if value1.min_vid.index() < value2.min_vid.index() {
  31             value1.min_vid
  32         } else {
  33             value2.min_vid
  34         };
  35
  36         Ok(RegionVidKey { min_vid })
  37     }
  38 }
  39
  40 impl UnifyKey for ty::RegionVid {
  41     type Value = RegionVidKey;
  42     fn index(&self) -> u32 {
  43         u32::from(*self)
  44     }
  45     fn from_index(i: u32) -> ty::RegionVid {
  46         ty::RegionVid::from(i)
  47     }
  48     fn tag() -> &'static str {
  49         "RegionVid"
  50     }
  51 }
  52
  53 impl ToType for ty::IntVarValue {
  54     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
  55         match *self {
  56             ty::IntType(i) => tcx.mk_mach_int(i),
  57             ty::UintType(i) => tcx.mk_mach_uint(i),
  58         }
  59     }
  60 }
  61
  62 impl ToType for ty::FloatVarValue {
  63     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
  64         tcx.mk_mach_float(self.0)
  65     }
  66 }
  67
  68 // Generic consts.
  69
  70 #[derive(Copy, Clone, Debug)]
  71 pub struct ConstVariableOrigin {
  72     pub kind: ConstVariableOriginKind,
  73     pub span: Span,
  74 }
  75
  76 /// Reasons to create a const inference variable
  77 #[derive(Copy, Clone, Debug)]
  78 pub enum ConstVariableOriginKind {
  79     MiscVariable,
  80     ConstInference,
  81     ConstParameterDefinition(Symbol, DefId),
  82     SubstitutionPlaceholder,
  83 }
  84
  85 #[derive(Copy, Clone, Debug)]
  86 pub enum ConstVariableValue<'tcx> {
  87     Known { value: &'tcx ty::Const<'tcx> },
  88     Unknown { universe: ty::UniverseIndex },
  89 }
  90
  91 impl<'tcx> ConstVariableValue<'tcx> {
  92     /// If this value is known, returns the const it is known to be.
  93     /// Otherwise, `None`.
  94     pub fn known(&self) -> Option<&'tcx ty::Const<'tcx>> {
  95         match *self {
  96             ConstVariableValue::Unknown { .. } => None,
  97             ConstVariableValue::Known { value } => Some(value),
  98         }
  99     }
 100
 101     pub fn is_unknown(&self) -> bool {
 102         match *self {
 103             ConstVariableValue::Unknown { .. } => true,
 104             ConstVariableValue::Known { .. } => false,
 105         }
 106     }
 107 }
 108
 109 #[derive(Copy, Clone, Debug)]
 110 pub struct ConstVarValue<'tcx> {
 111     pub origin: ConstVariableOrigin,
 112     pub val: ConstVariableValue<'tcx>,
 113 }
 114
 115 impl<'tcx> UnifyKey for ty::ConstVid<'tcx> {
 116     type Value = ConstVarValue<'tcx>;
 117     fn index(&self) -> u32 {
 118         self.index
 119     }
 120     fn from_index(i: u32) -> Self {
 121         ty::ConstVid { index: i, phantom: PhantomData }
 122     }
 123     fn tag() -> &'static str {
 124         "ConstVid"
 125     }
 126 }
 127
 128 impl<'tcx> UnifyValue for ConstVarValue<'tcx> {
 129     type Error = (&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>);
 130
 131     fn unify_values(&value1: &Self, &value2: &Self) -> Result<Self, Self::Error> {
 132         Ok(match (value1.val, value2.val) {
 133             (ConstVariableValue::Known { .. }, ConstVariableValue::Known { .. }) => {
 134                 bug!("equating two const variables, both of which have known values")
 135             }
 136
 137             // If one side is known, prefer that one.
 138             (ConstVariableValue::Known { .. }, ConstVariableValue::Unknown { .. }) => value1,
 139             (ConstVariableValue::Unknown { .. }, ConstVariableValue::Known { .. }) => value2,
 140
 141             // If both sides are *unknown*, it hardly matters, does it?
 142             (
 143                 ConstVariableValue::Unknown { universe: universe1 },
 144                 ConstVariableValue::Unknown { universe: universe2 },
 145             ) => {
 146                 // If we unify two unbound variables, ?T and ?U, then whatever
 147                 // value they wind up taking (which must be the same value) must
 148                 // be nameable by both universes. Therefore, the resulting
 149                 // universe is the minimum of the two universes, because that is
 150                 // the one which contains the fewest names in scope.
 151                 let universe = cmp::min(universe1, universe2);
 152                 ConstVarValue {
 153                     val: ConstVariableValue::Unknown { universe },
 154                     origin: value1.origin,
 155                 }
 156             }
 157         })
 158     }
 159 }
 160
 161 impl<'tcx> EqUnifyValue for &'tcx ty::Const<'tcx> {}
 162
 163 pub fn replace_if_possible<V, L>(
 164     table: &mut UnificationTable<InPlace<ty::ConstVid<'tcx>, V, L>>,
 165     c: &'tcx ty::Const<'tcx>,
 166 ) -> &'tcx ty::Const<'tcx>
 167 where
 168     V: snapshot_vec::VecLike<unify::Delegate<ty::ConstVid<'tcx>>>,
 169     L: UndoLogs<snapshot_vec::UndoLog<unify::Delegate<ty::ConstVid<'tcx>>>>,
 170 {
 171     if let ty::Const { val: ty::ConstKind::Infer(InferConst::Var(vid)), .. } = c {
 172         match table.probe_value(*vid).val.known() {
 173             Some(c) => c,
 174             None => c,
 175         }
 176     } else {
 177         c
 178     }
 179 }