vendor/chalk-solve/src/infer/var.rs

   1 use chalk_ir::cast::Cast;
   2 use chalk_ir::interner::Interner;
   3 use chalk_ir::*;
   4 use ena::unify::{UnifyKey, UnifyValue};
   5 use std::cmp::min;
   6 use std::fmt;
   7 use std::marker::PhantomData;
   8 use std::u32;
   9
  10 /// Wrapper around `chalk_ir::InferenceVar` for coherence purposes.
  11 /// An inference variable represents an unknown term -- either a type
  12 /// or a lifetime. The variable itself is just an index into the
  13 /// unification table; the unification table maps it to an
  14 /// `InferenceValue`.
  15 ///
  16 /// Inference variables can be in one of two states (represents by the variants
  17 /// of an `InferenceValue`):
  18 ///
  19 /// - Unbound(`ui`). In this case, the value of the variable is not yet known. We carry
  20 ///   along a universe index `ui` that tracks the universe in which the variable was
  21 ///   created; this determines what names may appear in the variable's value.
  22 ///   - In this state, we do **not** track the kind of this variable
  23 ///     (i.e., whether it represents a type or a lifetime). There is
  24 ///     no need: if it represents a lifetime, for example, then there
  25 ///     should only ever be constraints that relate it to other
  26 ///     lifetimes, or use it in lifetime position.
  27 /// - Bound. In this case, the value of the variable is known. We
  28 ///   carry along the value. We discard the universe index in which
  29 ///   the variable was created, since that was only needed to help us
  30 ///   reject illegal values. Once the value of a variable is known, it
  31 ///   can never change.
  32 ///   - The value we actually store for variables is a
  33 ///     `ir::GenericArg`, and hence it does carry along the kind of the
  34 ///     variable via the enum variant. However, we should always know
  35 ///     the kind of the variable from context, and hence we typically
  36 ///     "downcast" the resulting variable using
  37 ///     e.g. `value.ty().unwrap()`.
  38 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
  39 pub struct EnaVariable<I: Interner> {
  40     var: InferenceVar,
  41     phantom: PhantomData<I>,
  42 }
  43
  44 impl<I: Interner> From<InferenceVar> for EnaVariable<I> {
  45     fn from(var: InferenceVar) -> EnaVariable<I> {
  46         EnaVariable {
  47             var,
  48             phantom: PhantomData,
  49         }
  50     }
  51 }
  52
  53 impl<I: Interner> From<EnaVariable<I>> for InferenceVar {
  54     fn from(ena_var: EnaVariable<I>) -> InferenceVar {
  55         ena_var.var
  56     }
  57 }
  58
  59 impl<I: Interner> EnaVariable<I> {
  60     /// Convert this inference variable into a type. When using this
  61     /// method, naturally you should know from context that the kind
  62     /// of this inference variable is a type (we can't check it).
  63     pub fn to_ty_with_kind(self, interner: I, kind: TyVariableKind) -> Ty<I> {
  64         self.var.to_ty(interner, kind)
  65     }
  66
  67     /// Same as `to_ty_with_kind`, but the kind is set to `TyVariableKind::General`.
  68     /// This should be used instead of `to_ty_with_kind` when creating a new
  69     /// inference variable (when the kind is not known).
  70     pub fn to_ty(self, interner: I) -> Ty<I> {
  71         self.var.to_ty(interner, TyVariableKind::General)
  72     }
  73
  74     /// Convert this inference variable into a lifetime. When using this
  75     /// method, naturally you should know from context that the kind
  76     /// of this inference variable is a lifetime (we can't check it).
  77     pub fn to_lifetime(self, interner: I) -> Lifetime<I> {
  78         self.var.to_lifetime(interner)
  79     }
  80
  81     /// Convert this inference variable into a const. When using this
  82     /// method, naturally you should know from context that the kind
  83     /// of this inference variable is a const (we can't check it).
  84     pub fn to_const(self, interner: I, ty: Ty<I>) -> Const<I> {
  85         self.var.to_const(interner, ty)
  86     }
  87 }
  88
  89 impl<I: Interner> UnifyKey for EnaVariable<I> {
  90     type Value = InferenceValue<I>;
  91
  92     fn index(&self) -> u32 {
  93         self.var.index()
  94     }
  95
  96     fn from_index(u: u32) -> Self {
  97         EnaVariable::from(InferenceVar::from(u))
  98     }
  99
 100     fn tag() -> &'static str {
 101         "EnaVariable"
 102     }
 103 }
 104
 105 /// The value of an inference variable. We start out as `Unbound` with a
 106 /// universe index; when the inference variable is assigned a value, it becomes
 107 /// bound and records that value. See `EnaVariable` for more details.
 108 #[derive(Clone, Debug, PartialEq, Eq)]
 109 pub enum InferenceValue<I: Interner> {
 110     Unbound(UniverseIndex),
 111     Bound(GenericArg<I>),
 112 }
 113
 114 impl<I: Interner> InferenceValue<I> {
 115     pub fn from_ty(interner: I, ty: Ty<I>) -> Self {
 116         InferenceValue::Bound(ty.cast(interner))
 117     }
 118
 119     pub fn from_lifetime(interner: I, lifetime: Lifetime<I>) -> Self {
 120         InferenceValue::Bound(lifetime.cast(interner))
 121     }
 122
 123     pub fn from_const(interner: I, constant: Const<I>) -> Self {
 124         InferenceValue::Bound(constant.cast(interner))
 125     }
 126 }
 127
 128 impl<I: Interner> UnifyValue for InferenceValue<I> {
 129     type Error = (InferenceValue<I>, InferenceValue<I>);
 130
 131     fn unify_values(
 132         a: &InferenceValue<I>,
 133         b: &InferenceValue<I>,
 134     ) -> Result<InferenceValue<I>, (InferenceValue<I>, InferenceValue<I>)> {
 135         match (a, b) {
 136             (&InferenceValue::Unbound(ui_a), &InferenceValue::Unbound(ui_b)) => {
 137                 Ok(InferenceValue::Unbound(min(ui_a, ui_b)))
 138             }
 139             (bound @ &InferenceValue::Bound(_), &InferenceValue::Unbound(_))
 140             | (&InferenceValue::Unbound(_), bound @ &InferenceValue::Bound(_)) => Ok(bound.clone()),
 141             (&InferenceValue::Bound(_), &InferenceValue::Bound(_)) => {
 142                 panic!("we should not be asked to unify two bound things")
 143             }
 144         }
 145     }
 146 }
 147
 148 impl<I: Interner> fmt::Debug for EnaVariable<I> {
 149     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
 150         write!(fmt, "{:?}", self.var)
 151     }
 152 }