src/librustc/infer/unify_key.rs

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