use std::cmp;
use std::marker::PhantomData;
use std::ops::Range;
use rustc_data_structures::undo_log::Rollback;
use rustc_data_structures::{snapshot_vec as sv, unify as ut};
use rustc_hir::def_id::DefId;
use rustc_index::IndexVec;
use rustc_middle::bug;
use rustc_middle::ty::{self, Ty, TyVid};
use rustc_span::Span;
use tracing::debug;
use crate::infer::InferCtxtUndoLogs;
impl<'tcx> Rollback<sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>> for TypeVariableStorage<'tcx> {
fn reverse(&mut self, undo: sv::UndoLog<ut::Delegate<TyVidEqKey<'tcx>>>) {
self.eq_relations.reverse(undo)
}
}
#[derive(Clone)]
pub struct TypeVariableStorage<'tcx> {
values: IndexVec<TyVid, TypeVariableData>,
eq_relations: ut::UnificationTableStorage<TyVidEqKey<'tcx>>,
}
pub struct TypeVariableTable<'a, 'tcx> {
storage: &'a mut TypeVariableStorage<'tcx>,
undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
}
#[derive(Copy, Clone, Debug)]
pub struct TypeVariableOrigin {
pub span: Span,
pub param_def_id: Option<DefId>,
}
#[derive(Clone)]
pub(crate) struct TypeVariableData {
origin: TypeVariableOrigin,
}
#[derive(Copy, Clone, Debug)]
pub enum TypeVariableValue<'tcx> {
Known { value: Ty<'tcx> },
Unknown { universe: ty::UniverseIndex },
}
impl<'tcx> TypeVariableValue<'tcx> {
pub fn known(&self) -> Option<Ty<'tcx>> {
match *self {
TypeVariableValue::Unknown { .. } => None,
TypeVariableValue::Known { value } => Some(value),
}
}
pub fn is_unknown(&self) -> bool {
match *self {
TypeVariableValue::Unknown { .. } => true,
TypeVariableValue::Known { .. } => false,
}
}
}
impl<'tcx> TypeVariableStorage<'tcx> {
pub fn new() -> TypeVariableStorage<'tcx> {
TypeVariableStorage {
values: Default::default(),
eq_relations: ut::UnificationTableStorage::new(),
}
}
#[inline]
pub(crate) fn with_log<'a>(
&'a mut self,
undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
) -> TypeVariableTable<'a, 'tcx> {
TypeVariableTable { storage: self, undo_log }
}
#[inline]
pub(crate) fn eq_relations_ref(&self) -> &ut::UnificationTableStorage<TyVidEqKey<'tcx>> {
&self.eq_relations
}
pub(super) fn finalize_rollback(&mut self) {
debug_assert!(self.values.len() >= self.eq_relations.len());
self.values.truncate(self.eq_relations.len());
}
}
impl<'tcx> TypeVariableTable<'_, 'tcx> {
pub fn var_origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
self.storage.values[vid].origin
}
pub fn equate(&mut self, a: ty::TyVid, b: ty::TyVid) {
debug_assert!(self.probe(a).is_unknown());
debug_assert!(self.probe(b).is_unknown());
self.eq_relations().union(a, b);
}
pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
let vid = self.root_var(vid);
debug_assert!(!ty.is_ty_var(), "instantiating ty var with var: {vid:?} {ty:?}");
debug_assert!(self.probe(vid).is_unknown());
debug_assert!(
self.eq_relations().probe_value(vid).is_unknown(),
"instantiating type variable `{vid:?}` twice: new-value = {ty:?}, old-value={:?}",
self.eq_relations().probe_value(vid)
);
self.eq_relations().union_value(vid, TypeVariableValue::Known { value: ty });
}
pub fn new_var(
&mut self,
universe: ty::UniverseIndex,
origin: TypeVariableOrigin,
) -> ty::TyVid {
let eq_key = self.eq_relations().new_key(TypeVariableValue::Unknown { universe });
let index = self.storage.values.push(TypeVariableData { origin });
debug_assert_eq!(eq_key.vid, index);
debug!("new_var(index={:?}, universe={:?}, origin={:?})", eq_key.vid, universe, origin);
index
}
pub fn num_vars(&self) -> usize {
self.storage.values.len()
}
pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
self.eq_relations().find(vid).vid
}
pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
self.inlined_probe(vid)
}
#[inline(always)]
pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> {
self.eq_relations().inlined_probe_value(vid)
}
pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
match *t.kind() {
ty::Infer(ty::TyVar(v)) => match self.probe(v) {
TypeVariableValue::Unknown { .. } => t,
TypeVariableValue::Known { value } => value,
},
_ => t,
}
}
#[inline]
fn eq_relations(&mut self) -> super::UnificationTable<'_, 'tcx, TyVidEqKey<'tcx>> {
self.storage.eq_relations.with_log(self.undo_log)
}
pub fn vars_since_snapshot(
&mut self,
value_count: usize,
) -> (Range<TyVid>, Vec<TypeVariableOrigin>) {
let range = TyVid::from_usize(value_count)..TyVid::from_usize(self.num_vars());
(
range.start..range.end,
(range.start..range.end).map(|index| self.var_origin(index)).collect(),
)
}
pub fn unresolved_variables(&mut self) -> Vec<ty::TyVid> {
(0..self.num_vars())
.filter_map(|i| {
let vid = ty::TyVid::from_usize(i);
match self.probe(vid) {
TypeVariableValue::Unknown { .. } => Some(vid),
TypeVariableValue::Known { .. } => None,
}
})
.collect()
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub(crate) struct TyVidEqKey<'tcx> {
vid: ty::TyVid,
phantom: PhantomData<TypeVariableValue<'tcx>>,
}
impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
#[inline] fn from(vid: ty::TyVid) -> Self {
TyVidEqKey { vid, phantom: PhantomData }
}
}
impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
type Value = TypeVariableValue<'tcx>;
#[inline(always)]
fn index(&self) -> u32 {
self.vid.as_u32()
}
#[inline]
fn from_index(i: u32) -> Self {
TyVidEqKey::from(ty::TyVid::from_u32(i))
}
fn tag() -> &'static str {
"TyVidEqKey"
}
}
impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
type Error = ut::NoError;
fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
match (value1, value2) {
(&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
bug!("equating two type variables, both of which have known types")
}
(&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
(&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
(
&TypeVariableValue::Unknown { universe: universe1 },
&TypeVariableValue::Unknown { universe: universe2 },
) => {
let universe = cmp::min(universe1, universe2);
Ok(TypeVariableValue::Unknown { universe })
}
}
}
}