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