compiler/rustc_middle/src/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     // FIXME(const_generics): Consider storing the `DefId` of the param here.
 128     ConstParameterDefinition(Symbol),
 129     SubstitutionPlaceholder,
 130 }
 131
 132 #[derive(Copy, Clone, Debug)]
 133 pub enum ConstVariableValue<'tcx> {
 134     Known { value: &'tcx ty::Const<'tcx> },
 135     Unknown { universe: ty::UniverseIndex },
 136 }
 137
 138 impl<'tcx> ConstVariableValue<'tcx> {
 139     /// If this value is known, returns the const it is known to be.
 140     /// Otherwise, `None`.
 141     pub fn known(&self) -> Option<&'tcx ty::Const<'tcx>> {
 142         match *self {
 143             ConstVariableValue::Unknown { .. } => None,
 144             ConstVariableValue::Known { value } => Some(value),
 145         }
 146     }
 147
 148     pub fn is_unknown(&self) -> bool {
 149         match *self {
 150             ConstVariableValue::Unknown { .. } => true,
 151             ConstVariableValue::Known { .. } => false,
 152         }
 153     }
 154 }
 155
 156 #[derive(Copy, Clone, Debug)]
 157 pub struct ConstVarValue<'tcx> {
 158     pub origin: ConstVariableOrigin,
 159     pub val: ConstVariableValue<'tcx>,
 160 }
 161
 162 impl<'tcx> UnifyKey for ty::ConstVid<'tcx> {
 163     type Value = ConstVarValue<'tcx>;
 164     fn index(&self) -> u32 {
 165         self.index
 166     }
 167     fn from_index(i: u32) -> Self {
 168         ty::ConstVid { index: i, phantom: PhantomData }
 169     }
 170     fn tag() -> &'static str {
 171         "ConstVid"
 172     }
 173 }
 174
 175 impl<'tcx> UnifyValue for ConstVarValue<'tcx> {
 176     type Error = (&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>);
 177
 178     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> {
 179         let val = match (value1.val, value2.val) {
 180             (ConstVariableValue::Known { .. }, ConstVariableValue::Known { .. }) => {
 181                 bug!("equating two const variables, both of which have known values")
 182             }
 183
 184             // If one side is known, prefer that one.
 185             (ConstVariableValue::Known { .. }, ConstVariableValue::Unknown { .. }) => {
 186                 Ok(value1.val)
 187             }
 188             (ConstVariableValue::Unknown { .. }, ConstVariableValue::Known { .. }) => {
 189                 Ok(value2.val)
 190             }
 191
 192             // If both sides are *unknown*, it hardly matters, does it?
 193             (
 194                 ConstVariableValue::Unknown { universe: universe1 },
 195                 ConstVariableValue::Unknown { universe: universe2 },
 196             ) => {
 197                 // If we unify two unbound variables, ?T and ?U, then whatever
 198                 // value they wind up taking (which must be the same value) must
 199                 // be nameable by both universes. Therefore, the resulting
 200                 // universe is the minimum of the two universes, because that is
 201                 // the one which contains the fewest names in scope.
 202                 let universe = cmp::min(universe1, universe2);
 203                 Ok(ConstVariableValue::Unknown { universe })
 204             }
 205         }?;
 206
 207         Ok(ConstVarValue {
 208             origin: ConstVariableOrigin {
 209                 kind: ConstVariableOriginKind::ConstInference,
 210                 span: DUMMY_SP,
 211             },
 212             val,
 213         })
 214     }
 215 }
 216
 217 impl<'tcx> EqUnifyValue for &'tcx ty::Const<'tcx> {}
 218
 219 pub fn replace_if_possible<V, L>(
 220     table: &mut UnificationTable<InPlace<ty::ConstVid<'tcx>, V, L>>,
 221     c: &'tcx ty::Const<'tcx>,
 222 ) -> &'tcx ty::Const<'tcx>
 223 where
 224     V: snapshot_vec::VecLike<unify::Delegate<ty::ConstVid<'tcx>>>,
 225     L: UndoLogs<snapshot_vec::UndoLog<unify::Delegate<ty::ConstVid<'tcx>>>>,
 226 {
 227     if let ty::Const { val: ty::ConstKind::Infer(InferConst::Var(vid)), .. } = c {
 228         match table.probe_value(*vid).val.known() {
 229             Some(c) => c,
 230             None => c,
 231         }
 232     } else {
 233         c
 234     }
 235 }