src/librustc/infer/const_variable.rs

   1 use crate::mir::interpret::ConstValue;
   2 use syntax::symbol::InternedString;
   3 use syntax_pos::Span;
   4 use crate::ty::{self, InferConst};
   5
   6 use std::cmp;
   7 use std::marker::PhantomData;
   8 use rustc_data_structures::fx::FxHashMap;
   9 use rustc_data_structures::snapshot_vec as sv;
  10 use rustc_data_structures::unify as ut;
  11
  12 pub struct ConstVariableTable<'tcx> {
  13     values: sv::SnapshotVec<Delegate<'tcx>>,
  14
  15     relations: ut::UnificationTable<ut::InPlace<ty::ConstVid<'tcx>>>,
  16 }
  17
  18 /// Reasons to create a const inference variable
  19 #[derive(Copy, Clone, Debug)]
  20 pub enum ConstVariableOrigin {
  21     MiscVariable(Span),
  22     ConstInference(Span),
  23     ConstParameterDefinition(Span, InternedString),
  24     SubstitutionPlaceholder(Span),
  25 }
  26
  27 pub type ConstVariableMap<'tcx> = FxHashMap<ty::ConstVid<'tcx>, ConstVariableOrigin>;
  28
  29 struct ConstVariableData {
  30     origin: ConstVariableOrigin,
  31 }
  32
  33 #[derive(Copy, Clone, Debug)]
  34 pub enum ConstVariableValue<'tcx> {
  35     Known { value: &'tcx ty::LazyConst<'tcx> },
  36     Unknown { universe: ty::UniverseIndex },
  37 }
  38
  39 impl<'tcx> ConstVariableValue<'tcx> {
  40     /// If this value is known, returns the const it is known to be.
  41     /// Otherwise, `None`.
  42     pub fn known(&self) -> Option<&'tcx ty::LazyConst<'tcx>> {
  43         match *self {
  44             ConstVariableValue::Unknown { .. } => None,
  45             ConstVariableValue::Known { value } => Some(value),
  46         }
  47     }
  48
  49     pub fn is_unknown(&self) -> bool {
  50         match *self {
  51             ConstVariableValue::Unknown { .. } => true,
  52             ConstVariableValue::Known { .. } => false,
  53         }
  54     }
  55 }
  56
  57 pub struct Snapshot<'tcx> {
  58     snapshot: sv::Snapshot,
  59     relation_snapshot: ut::Snapshot<ut::InPlace<ty::ConstVid<'tcx>>>,
  60 }
  61
  62 struct Instantiate<'tcx> {
  63     _vid: ty::ConstVid<'tcx>,
  64 }
  65
  66 struct Delegate<'tcx> {
  67     pub phantom: PhantomData<&'tcx ()>,
  68 }
  69
  70 impl<'tcx> ConstVariableTable<'tcx> {
  71     pub fn new() -> ConstVariableTable<'tcx> {
  72         ConstVariableTable {
  73             values: sv::SnapshotVec::new(),
  74             relations: ut::UnificationTable::new(),
  75         }
  76     }
  77
  78     /// Returns the origin that was given when `vid` was created.
  79     ///
  80     /// Note that this function does not return care whether
  81     /// `vid` has been unified with something else or not.
  82     pub fn var_origin(&self, vid: ty::ConstVid<'tcx>) -> &ConstVariableOrigin {
  83         &self.values[vid.index as usize].origin
  84     }
  85
  86     pub fn unify_var_var(
  87         &mut self,
  88         a_id: ty::ConstVid<'tcx>,
  89         b_id: ty::ConstVid<'tcx>,
  90     ) -> Result<(), (&'tcx ty::LazyConst<'tcx>, &'tcx ty::LazyConst<'tcx>)> {
  91         self.relations.unify_var_var(a_id, b_id)
  92     }
  93
  94     pub fn unify_var_value(
  95         &mut self,
  96         a_id: ty::ConstVid<'tcx>,
  97         b: ConstVariableValue<'tcx>,
  98     ) -> Result<(), (&'tcx ty::LazyConst<'tcx>, &'tcx ty::LazyConst<'tcx>)> {
  99         self.relations.unify_var_value(a_id, b)
 100     }
 101
 102     /// Creates a new const variable.
 103     ///
 104     /// - `origin`: indicates *why* the const variable was created.
 105     ///   The code in this module doesn't care, but it can be useful
 106     ///   for improving error messages.
 107     pub fn new_var(
 108         &mut self,
 109         universe: ty::UniverseIndex,
 110         origin: ConstVariableOrigin,
 111     ) -> ty::ConstVid<'tcx> {
 112         let vid = self.relations.new_key(ConstVariableValue::Unknown{ universe });
 113
 114         let index = self.values.push(ConstVariableData {
 115             origin,
 116         });
 117         assert_eq!(vid.index, index as u32);
 118
 119         debug!("new_var(index={:?}, origin={:?}", vid, origin);
 120
 121         vid
 122     }
 123
 124     /// Retrieves the type to which `vid` has been instantiated, if
 125     /// any.
 126     pub fn probe(
 127         &mut self,
 128         vid: ty::ConstVid<'tcx>
 129     ) -> ConstVariableValue<'tcx> {
 130         self.relations.probe_value(vid)
 131     }
 132
 133     /// If `t` is a type-inference variable, and it has been
 134     /// instantiated, then return the with which it was
 135     /// instantiated. Otherwise, returns `t`.
 136     pub fn replace_if_possible(
 137         &mut self,
 138         c: &'tcx ty::LazyConst<'tcx>
 139     ) -> &'tcx ty::LazyConst<'tcx> {
 140         if let ty::LazyConst::Evaluated(ty::Const {
 141             val: ConstValue::Infer(InferConst::Var(vid)),
 142             ..
 143         }) = c {
 144             match self.probe(*vid).known() {
 145                 Some(c) => c,
 146                 None => c,
 147             }
 148         } else {
 149             c
 150         }
 151     }
 152
 153     /// Creates a snapshot of the type variable state.  This snapshot
 154     /// must later be committed (`commit()`) or rolled back
 155     /// (`rollback_to()`).  Nested snapshots are permitted, but must
 156     /// be processed in a stack-like fashion.
 157     pub fn snapshot(&mut self) -> Snapshot<'tcx> {
 158         Snapshot {
 159             snapshot: self.values.start_snapshot(),
 160             relation_snapshot: self.relations.snapshot(),
 161         }
 162     }
 163
 164     /// Undoes all changes since the snapshot was created. Any
 165     /// snapshots created since that point must already have been
 166     /// committed or rolled back.
 167     pub fn rollback_to(&mut self, s: Snapshot<'tcx>) {
 168         debug!("rollback_to{:?}", {
 169             for action in self.values.actions_since_snapshot(&s.snapshot) {
 170                 if let sv::UndoLog::NewElem(index) = *action {
 171                     debug!("inference variable _#{}t popped", index)
 172                 }
 173             }
 174         });
 175
 176         let Snapshot { snapshot, relation_snapshot } = s;
 177         self.values.rollback_to(snapshot);
 178         self.relations.rollback_to(relation_snapshot);
 179     }
 180
 181     /// Commits all changes since the snapshot was created, making
 182     /// them permanent (unless this snapshot was created within
 183     /// another snapshot). Any snapshots created since that point
 184     /// must already have been committed or rolled back.
 185     pub fn commit(&mut self, s: Snapshot<'tcx>) {
 186         let Snapshot { snapshot, relation_snapshot } = s;
 187         self.values.commit(snapshot);
 188         self.relations.commit(relation_snapshot);
 189     }
 190
 191     /// Returns a map `{V1 -> V2}`, where the keys `{V1}` are
 192     /// const-variables created during the snapshot, and the values
 193     /// `{V2}` are the root variables that they were unified with,
 194     /// along with their origin.
 195     pub fn consts_created_since_snapshot(
 196         &mut self,
 197         s: &Snapshot<'tcx>
 198     ) -> ConstVariableMap<'tcx> {
 199         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 200
 201         actions_since_snapshot
 202             .iter()
 203             .filter_map(|action| match action {
 204                 &sv::UndoLog::NewElem(index) => Some(ty::ConstVid {
 205                     index: index as u32,
 206                     phantom: PhantomData,
 207                 }),
 208                 _ => None,
 209             })
 210             .map(|vid| {
 211                 let origin = self.values.get(vid.index as usize).origin.clone();
 212                 (vid, origin)
 213             })
 214             .collect()
 215     }
 216 }
 217
 218 impl<'tcx> ut::UnifyKey for ty::ConstVid<'tcx> {
 219     type Value = ConstVariableValue<'tcx>;
 220     fn index(&self) -> u32 { self.index }
 221     fn from_index(i: u32) -> Self { ty::ConstVid { index: i, phantom: PhantomData } }
 222     fn tag() -> &'static str { "ConstVid" }
 223 }
 224
 225 impl<'tcx> ut::UnifyValue for ConstVariableValue<'tcx> {
 226     type Error = (&'tcx ty::LazyConst<'tcx>, &'tcx ty::LazyConst<'tcx>);
 227
 228     fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> {
 229         match (value1, value2) {
 230             (
 231                 &ConstVariableValue::Known { value: value1 },
 232                 &ConstVariableValue::Known { value: value2 }
 233             ) => {
 234                 match <&'tcx ty::LazyConst<'tcx>>::unify_values(&value1, &value2) {
 235                     Ok(value) => Ok(ConstVariableValue::Known { value }),
 236                     Err(err) => Err(err),
 237                 }
 238             }
 239
 240             // If one side is known, prefer that one.
 241             (&ConstVariableValue::Known { .. }, &ConstVariableValue::Unknown { .. }) => Ok(*value1),
 242             (&ConstVariableValue::Unknown { .. }, &ConstVariableValue::Known { .. }) => Ok(*value2),
 243
 244             // If both sides are *unknown*, it hardly matters, does it?
 245             (&ConstVariableValue::Unknown { universe: universe1 },
 246              &ConstVariableValue::Unknown { universe: universe2 }) =>  {
 247                 // If we unify two unbound variables, ?T and ?U, then whatever
 248                 // value they wind up taking (which must be the same value) must
 249                 // be nameable by both universes. Therefore, the resulting
 250                 // universe is the minimum of the two universes, because that is
 251                 // the one which contains the fewest names in scope.
 252                 let universe = cmp::min(universe1, universe2);
 253                 Ok(ConstVariableValue::Unknown { universe })
 254             }
 255         }
 256     }
 257 }
 258
 259 impl<'tcx> ut::EqUnifyValue for &'tcx ty::LazyConst<'tcx> {}
 260
 261 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
 262     type Value = ConstVariableData;
 263     type Undo = Instantiate<'tcx>;
 264
 265     fn reverse(_values: &mut Vec<ConstVariableData>, _action: Instantiate<'tcx>) {
 266         // We don't actually have to *do* anything to reverse an
 267         // instantiation; the value for a variable is stored in the
 268         // `relations` and hence its rollback code will handle
 269         // it.
 270     }
 271 }