src/librustc_middle/infer/unify_key.rs

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