#![deny(rust_2018_idioms)]
extern crate self as chalk_ir;
use crate::cast::{Cast, CastTo};
use crate::fold::shift::Shift;
use crate::fold::{Fold, Folder, Subst, SuperFold};
use crate::visit::{SuperVisit, Visit, VisitExt, VisitResult, Visitor};
use chalk_derive::{Fold, HasInterner, SuperVisit, Visit, Zip};
use std::iter;
use std::marker::PhantomData;
pub use crate::debug::SeparatorTraitRef;
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Void {}
pub type Fallible<T> = Result<T, NoSolution>;
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct NoSolution;
pub struct Floundered;
macro_rules! impl_debugs {
($($id:ident), *) => {
$(
impl<I: Interner> std::fmt::Debug for $id<I> {
fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
write!(fmt, "{}({:?})", stringify!($id), self.0)
}
}
)*
};
}
#[macro_use]
pub mod zip;
#[macro_use]
pub mod fold;
#[macro_use]
pub mod visit;
#[macro_use]
pub mod debug_macros;
pub mod cast;
pub mod interner;
use interner::{HasInterner, Interner};
pub mod could_match;
pub mod debug;
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
pub struct Environment<I: Interner> {
pub clauses: ProgramClauses<I>,
}
impl<I: Interner> Environment<I> {
pub fn new(interner: &I) -> Self {
Environment {
clauses: ProgramClauses::new(interner),
}
}
pub fn add_clauses<II>(&self, interner: &I, clauses: II) -> Self
where
II: IntoIterator<Item = ProgramClause<I>>,
{
let mut env = self.clone();
env.clauses =
ProgramClauses::from(interner, env.clauses.iter(interner).cloned().chain(clauses));
env
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit)]
pub struct InEnvironment<G: HasInterner> {
pub environment: Environment<G::Interner>,
pub goal: G,
}
impl<G: HasInterner> InEnvironment<G> {
pub fn new(environment: &Environment<G::Interner>, goal: G) -> Self {
InEnvironment {
environment: environment.clone(),
goal,
}
}
pub fn map<OP, H>(self, op: OP) -> InEnvironment<H>
where
OP: FnOnce(G) -> H,
H: HasInterner<Interner = G::Interner>,
{
InEnvironment {
environment: self.environment,
goal: op(self.goal),
}
}
}
impl<G: HasInterner> HasInterner for InEnvironment<G> {
type Interner = G::Interner;
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum IntTy {
Isize,
I8,
I16,
I32,
I64,
I128,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum UintTy {
Usize,
U8,
U16,
U32,
U64,
U128,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum FloatTy {
F32,
F64,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Scalar {
Bool,
Char,
Int(IntTy),
Uint(UintTy),
Float(FloatTy),
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Mutability {
Mut,
Not,
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Fold, Visit)]
pub enum TypeName<I: Interner> {
Adt(AdtId<I>),
AssociatedType(AssocTypeId<I>),
Scalar(Scalar),
Tuple(usize),
Array,
Slice,
Raw(Mutability),
Ref(Mutability),
OpaqueType(OpaqueTyId<I>),
FnDef(FnDefId<I>),
Str,
Never,
Error,
}
impl<I: Interner> HasInterner for TypeName<I> {
type Interner = I;
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct UniverseIndex {
pub counter: usize,
}
impl UniverseIndex {
pub const ROOT: UniverseIndex = UniverseIndex { counter: 0 };
pub fn root() -> UniverseIndex {
Self::ROOT
}
pub fn can_see(self, ui: UniverseIndex) -> bool {
self.counter >= ui.counter
}
pub fn next(self) -> UniverseIndex {
UniverseIndex {
counter: self.counter + 1,
}
}
}
#[derive(Clone, Debug)]
pub struct UniverseMap {
pub universes: Vec<UniverseIndex>,
}
impl UniverseMap {
pub fn new() -> Self {
UniverseMap {
universes: vec![UniverseIndex::root()],
}
}
pub fn num_canonical_universes(&self) -> usize {
self.universes.len()
}
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct AdtId<I: Interner>(pub I::InternedAdtId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct TraitId<I: Interner>(pub I::DefId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ImplId<I: Interner>(pub I::DefId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ClauseId<I: Interner>(pub I::DefId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct AssocTypeId<I: Interner>(pub I::DefId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct OpaqueTyId<I: Interner>(pub I::DefId);
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct FnDefId<I: Interner>(pub I::DefId);
impl_debugs!(ImplId, ClauseId);
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct Ty<I: Interner> {
interned: I::InternedType,
}
impl<I: Interner> Ty<I> {
pub fn new(interner: &I, data: impl CastTo<TyData<I>>) -> Self {
Ty {
interned: I::intern_ty(interner, data.cast(interner)),
}
}
pub fn interned(&self) -> &I::InternedType {
&self.interned
}
pub fn data(&self, interner: &I) -> &TyData<I> {
I::ty_data(interner, &self.interned)
}
pub fn from_env(&self) -> FromEnv<I> {
FromEnv::Ty(self.clone())
}
pub fn well_formed(&self) -> WellFormed<I> {
WellFormed::Ty(self.clone())
}
pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
self.from_env().cast(interner)
}
pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
if let TyData::BoundVar(bv) = self.data(interner) {
Some(*bv)
} else {
None
}
}
pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
if let TyData::InferenceVar(depth, _) = self.data(interner) {
Some(*depth)
} else {
None
}
}
pub fn is_var(&self, interner: &I) -> bool {
match self.data(interner) {
TyData::BoundVar(_) | TyData::InferenceVar(_, _) => true,
_ => false,
}
}
pub fn is_alias(&self, interner: &I) -> bool {
match self.data(interner) {
TyData::Alias(..) => true,
_ => false,
}
}
pub fn is_integer(&self, interner: &I) -> bool {
match self.data(interner) {
TyData::Apply(ApplicationTy {
name: TypeName::Scalar(Scalar::Int(_)),
..
})
| TyData::Apply(ApplicationTy {
name: TypeName::Scalar(Scalar::Uint(_)),
..
}) => true,
_ => false,
}
}
pub fn is_float(&self, interner: &I) -> bool {
match self.data(interner) {
TyData::Apply(ApplicationTy {
name: TypeName::Scalar(Scalar::Float(_)),
..
}) => true,
_ => false,
}
}
pub fn needs_shift(&self, interner: &I) -> bool {
self.has_free_vars(interner)
}
}
#[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
pub enum TyData<I: Interner> {
Apply(ApplicationTy<I>),
Placeholder(PlaceholderIndex),
Dyn(DynTy<I>),
Alias(AliasTy<I>),
Function(Fn<I>),
BoundVar(BoundVar),
InferenceVar(InferenceVar, TyKind),
}
impl<I: Interner> TyData<I> {
pub fn intern(self, interner: &I) -> Ty<I> {
Ty::new(interner, self)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct BoundVar {
pub debruijn: DebruijnIndex,
pub index: usize,
}
impl BoundVar {
pub fn new(debruijn: DebruijnIndex, index: usize) -> Self {
Self { debruijn, index }
}
pub fn to_ty<I: Interner>(self, interner: &I) -> Ty<I> {
TyData::<I>::BoundVar(self).intern(interner)
}
pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
LifetimeData::<I>::BoundVar(self).intern(interner)
}
pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
ConstData {
ty,
value: ConstValue::<I>::BoundVar(self),
}
.intern(interner)
}
pub fn bound_within(self, outer_binder: DebruijnIndex) -> bool {
self.debruijn.within(outer_binder)
}
#[must_use]
pub fn shifted_in(self) -> Self {
BoundVar::new(self.debruijn.shifted_in(), self.index)
}
#[must_use]
pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> Self {
BoundVar::new(self.debruijn.shifted_in_from(outer_binder), self.index)
}
#[must_use]
pub fn shifted_out(self) -> Option<Self> {
self.debruijn
.shifted_out()
.map(|db| BoundVar::new(db, self.index))
}
#[must_use]
pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<Self> {
self.debruijn
.shifted_out_to(outer_binder)
.map(|db| BoundVar::new(db, self.index))
}
pub fn index_if_innermost(self) -> Option<usize> {
self.index_if_bound_at(DebruijnIndex::INNERMOST)
}
pub fn index_if_bound_at(self, debruijn: DebruijnIndex) -> Option<usize> {
if self.debruijn == debruijn {
Some(self.index)
} else {
None
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct DebruijnIndex {
depth: u32,
}
impl DebruijnIndex {
pub const INNERMOST: DebruijnIndex = DebruijnIndex { depth: 0 };
pub const ONE: DebruijnIndex = DebruijnIndex { depth: 1 };
pub fn new(depth: u32) -> Self {
DebruijnIndex { depth }
}
pub fn depth(self) -> u32 {
self.depth
}
pub fn within(self, outer_binder: DebruijnIndex) -> bool {
self < outer_binder
}
#[must_use]
pub fn shifted_in(self) -> DebruijnIndex {
self.shifted_in_from(DebruijnIndex::ONE)
}
pub fn shift_in(&mut self) {
*self = self.shifted_in();
}
#[must_use]
pub fn shifted_in_from(self, outer_binder: DebruijnIndex) -> DebruijnIndex {
DebruijnIndex::new(self.depth() + outer_binder.depth())
}
#[must_use]
pub fn shifted_out(self) -> Option<DebruijnIndex> {
self.shifted_out_to(DebruijnIndex::ONE)
}
pub fn shift_out(&mut self) {
*self = self.shifted_out().unwrap();
}
pub fn shifted_out_to(self, outer_binder: DebruijnIndex) -> Option<DebruijnIndex> {
if self.within(outer_binder) {
None
} else {
Some(DebruijnIndex::new(self.depth() - outer_binder.depth()))
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct DynTy<I: Interner> {
pub bounds: Binders<QuantifiedWhereClauses<I>>,
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct InferenceVar {
index: u32,
}
impl From<u32> for InferenceVar {
fn from(index: u32) -> InferenceVar {
InferenceVar { index }
}
}
impl InferenceVar {
pub fn index(self) -> u32 {
self.index
}
pub fn to_ty<I: Interner>(self, interner: &I, kind: TyKind) -> Ty<I> {
TyData::<I>::InferenceVar(self, kind).intern(interner)
}
pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
LifetimeData::<I>::InferenceVar(self).intern(interner)
}
pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
ConstData {
ty,
value: ConstValue::<I>::InferenceVar(self),
}
.intern(interner)
}
}
#[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
pub struct Fn<I: Interner> {
pub num_binders: usize,
pub substitution: Substitution<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct Const<I: Interner> {
interned: I::InternedConst,
}
impl<I: Interner> Const<I> {
pub fn new(interner: &I, data: impl CastTo<ConstData<I>>) -> Self {
Const {
interned: I::intern_const(interner, data.cast(interner)),
}
}
pub fn interned(&self) -> &I::InternedConst {
&self.interned
}
pub fn data(&self, interner: &I) -> &ConstData<I> {
I::const_data(interner, &self.interned)
}
pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
if let ConstValue::BoundVar(bv) = &self.data(interner).value {
Some(*bv)
} else {
None
}
}
pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
if let ConstValue::InferenceVar(iv) = &self.data(interner).value {
Some(*iv)
} else {
None
}
}
pub fn needs_shift(&self, interner: &I) -> bool {
match &self.data(interner).value {
ConstValue::BoundVar(_) => true,
ConstValue::InferenceVar(_) => false,
ConstValue::Placeholder(_) => false,
ConstValue::Concrete(_) => false,
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
pub struct ConstData<I: Interner> {
pub ty: Ty<I>,
pub value: ConstValue<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, HasInterner)]
pub enum ConstValue<I: Interner> {
BoundVar(BoundVar),
InferenceVar(InferenceVar),
Placeholder(PlaceholderIndex),
Concrete(ConcreteConst<I>),
}
impl<I: Interner> ConstData<I> {
pub fn intern(self, interner: &I) -> Const<I> {
Const::new(interner, self)
}
}
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct ConcreteConst<I: Interner> {
pub interned: I::InternedConcreteConst,
}
impl<I: Interner> ConcreteConst<I> {
pub fn const_eq(&self, ty: &Ty<I>, other: &ConcreteConst<I>, interner: &I) -> bool {
interner.const_eq(&ty.interned, &self.interned, &other.interned)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct Lifetime<I: Interner> {
interned: I::InternedLifetime,
}
impl<I: Interner> Lifetime<I> {
pub fn new(interner: &I, data: impl CastTo<LifetimeData<I>>) -> Self {
Lifetime {
interned: I::intern_lifetime(interner, data.cast(interner)),
}
}
pub fn interned(&self) -> &I::InternedLifetime {
&self.interned
}
pub fn data(&self, interner: &I) -> &LifetimeData<I> {
I::lifetime_data(interner, &self.interned)
}
pub fn bound_var(&self, interner: &I) -> Option<BoundVar> {
if let LifetimeData::BoundVar(bv) = self.data(interner) {
Some(*bv)
} else {
None
}
}
pub fn inference_var(&self, interner: &I) -> Option<InferenceVar> {
if let LifetimeData::InferenceVar(depth) = self.data(interner) {
Some(*depth)
} else {
None
}
}
pub fn needs_shift(&self, interner: &I) -> bool {
match self.data(interner) {
LifetimeData::BoundVar(_) => true,
LifetimeData::InferenceVar(_) => false,
LifetimeData::Placeholder(_) => false,
LifetimeData::Phantom(..) => unreachable!(),
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub enum LifetimeData<I: Interner> {
BoundVar(BoundVar),
InferenceVar(InferenceVar),
Placeholder(PlaceholderIndex),
Phantom(Void, PhantomData<I>),
}
impl<I: Interner> LifetimeData<I> {
pub fn intern(self, interner: &I) -> Lifetime<I> {
Lifetime::new(interner, self)
}
}
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PlaceholderIndex {
pub ui: UniverseIndex,
pub idx: usize,
}
impl PlaceholderIndex {
pub fn to_lifetime<I: Interner>(self, interner: &I) -> Lifetime<I> {
LifetimeData::<I>::Placeholder(self).intern(interner)
}
pub fn to_ty<I: Interner>(self, interner: &I) -> Ty<I> {
TyData::Placeholder(self).intern(interner)
}
pub fn to_const<I: Interner>(self, interner: &I, ty: Ty<I>) -> Const<I> {
ConstData {
ty,
value: ConstValue::Placeholder(self),
}
.intern(interner)
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct ApplicationTy<I: Interner> {
pub name: TypeName<I>,
pub substitution: Substitution<I>,
}
impl<I: Interner> ApplicationTy<I> {
pub fn intern(self, interner: &I) -> Ty<I> {
Ty::new(interner, self)
}
pub fn type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a {
self.substitution
.iter(interner)
.filter_map(move |p| p.ty(interner))
.cloned()
}
pub fn first_type_parameter(&self, interner: &I) -> Option<Ty<I>> {
self.type_parameters(interner).next()
}
pub fn len_type_parameters(&self, interner: &I) -> usize {
self.type_parameters(interner).count()
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum TyKind {
General,
Integer,
Float,
}
#[derive(Clone, PartialEq, Eq, Hash)]
pub enum VariableKind<I: Interner> {
Ty(TyKind),
Lifetime,
Const(Ty<I>),
}
impl<I: Interner> VariableKind<I> {
fn to_bound_variable(&self, interner: &I, bound_var: BoundVar) -> GenericArg<I> {
match self {
VariableKind::Ty(_) => {
GenericArgData::Ty(TyData::BoundVar(bound_var).intern(interner)).intern(interner)
}
VariableKind::Lifetime => {
GenericArgData::Lifetime(LifetimeData::BoundVar(bound_var).intern(interner))
.intern(interner)
}
VariableKind::Const(ty) => GenericArgData::Const(
ConstData {
ty: ty.clone(),
value: ConstValue::BoundVar(bound_var),
}
.intern(interner),
)
.intern(interner),
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct GenericArg<I: Interner> {
interned: I::InternedGenericArg,
}
impl<I: Interner> GenericArg<I> {
pub fn new(interner: &I, data: GenericArgData<I>) -> Self {
let interned = I::intern_generic_arg(interner, data);
GenericArg { interned }
}
pub fn interned(&self) -> &I::InternedGenericArg {
&self.interned
}
pub fn data(&self, interner: &I) -> &GenericArgData<I> {
I::generic_arg_data(interner, &self.interned)
}
pub fn assert_ty_ref(&self, interner: &I) -> &Ty<I> {
self.ty(interner).unwrap()
}
pub fn assert_lifetime_ref(&self, interner: &I) -> &Lifetime<I> {
self.lifetime(interner).unwrap()
}
pub fn assert_const_ref(&self, interner: &I) -> &Const<I> {
self.constant(interner).unwrap()
}
pub fn is_ty(&self, interner: &I) -> bool {
match self.data(interner) {
GenericArgData::Ty(_) => true,
GenericArgData::Lifetime(_) => false,
GenericArgData::Const(_) => false,
}
}
pub fn ty(&self, interner: &I) -> Option<&Ty<I>> {
match self.data(interner) {
GenericArgData::Ty(t) => Some(t),
_ => None,
}
}
pub fn lifetime(&self, interner: &I) -> Option<&Lifetime<I>> {
match self.data(interner) {
GenericArgData::Lifetime(t) => Some(t),
_ => None,
}
}
pub fn constant(&self, interner: &I) -> Option<&Const<I>> {
match self.data(interner) {
GenericArgData::Const(c) => Some(c),
_ => None,
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Visit, Fold, Zip)]
pub enum GenericArgData<I: Interner> {
Ty(Ty<I>),
Lifetime(Lifetime<I>),
Const(Const<I>),
}
impl<I: Interner> GenericArgData<I> {
pub fn intern(self, interner: &I) -> GenericArg<I> {
GenericArg::new(interner, self)
}
}
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct WithKind<I: Interner, T> {
pub kind: VariableKind<I>,
value: T,
}
impl<I: Interner, T> HasInterner for WithKind<I, T> {
type Interner = I;
}
impl<I: Interner, T> From<WithKind<I, T>> for (VariableKind<I>, T) {
fn from(with_kind: WithKind<I, T>) -> Self {
(with_kind.kind, with_kind.value)
}
}
impl<I: Interner, T> WithKind<I, T> {
pub fn new(kind: VariableKind<I>, value: T) -> Self {
Self { kind, value }
}
pub fn map<U, OP>(self, op: OP) -> WithKind<I, U>
where
OP: FnOnce(T) -> U,
{
WithKind {
kind: self.kind,
value: op(self.value),
}
}
pub fn map_ref<U, OP>(&self, op: OP) -> WithKind<I, U>
where
OP: FnOnce(&T) -> U,
{
WithKind {
kind: self.kind.clone(),
value: op(&self.value),
}
}
pub fn skip_kind(&self) -> &T {
&self.value
}
}
#[allow(type_alias_bounds)]
pub type CanonicalVarKind<I: Interner> = WithKind<I, UniverseIndex>;
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub enum AliasTy<I: Interner> {
Projection(ProjectionTy<I>),
Opaque(OpaqueTy<I>),
}
impl<I: Interner> AliasTy<I> {
pub fn intern(self, interner: &I) -> Ty<I> {
Ty::new(interner, self)
}
pub fn self_type_parameter(&self, interner: &I) -> Ty<I> {
match self {
AliasTy::Projection(projection_ty) => projection_ty
.substitution
.iter(interner)
.find_map(move |p| p.ty(interner))
.unwrap()
.clone(),
_ => todo!(),
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct ProjectionTy<I: Interner> {
pub associated_ty_id: AssocTypeId<I>,
pub substitution: Substitution<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct OpaqueTy<I: Interner> {
pub opaque_ty_id: OpaqueTyId<I>,
pub substitution: Substitution<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct TraitRef<I: Interner> {
pub trait_id: TraitId<I>,
pub substitution: Substitution<I>,
}
impl<I: Interner> TraitRef<I> {
pub fn type_parameters<'a>(&'a self, interner: &'a I) -> impl Iterator<Item = Ty<I>> + 'a {
self.substitution
.iter(interner)
.filter_map(move |p| p.ty(interner))
.cloned()
}
pub fn self_type_parameter(&self, interner: &I) -> Ty<I> {
self.type_parameters(interner).next().unwrap()
}
pub fn from_env(self) -> FromEnv<I> {
FromEnv::Trait(self)
}
pub fn well_formed(self) -> WellFormed<I> {
WellFormed::Trait(self)
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct LifetimeOutlives<I: Interner> {
pub a: Lifetime<I>,
pub b: Lifetime<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, SuperVisit, HasInterner, Zip)]
pub enum WhereClause<I: Interner> {
Implemented(TraitRef<I>),
AliasEq(AliasEq<I>),
LifetimeOutlives(LifetimeOutlives<I>),
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub enum WellFormed<I: Interner> {
Trait(TraitRef<I>),
Ty(Ty<I>),
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub enum FromEnv<I: Interner> {
Trait(TraitRef<I>),
Ty(Ty<I>),
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, SuperVisit, HasInterner, Zip)]
pub enum DomainGoal<I: Interner> {
Holds(WhereClause<I>),
WellFormed(WellFormed<I>),
FromEnv(FromEnv<I>),
Normalize(Normalize<I>),
IsLocal(Ty<I>),
IsUpstream(Ty<I>),
IsFullyVisible(Ty<I>),
LocalImplAllowed(TraitRef<I>),
Compatible(()),
DownstreamType(Ty<I>),
Reveal(()),
ObjectSafe(TraitId<I>),
}
pub type QuantifiedWhereClause<I> = Binders<WhereClause<I>>;
impl<I: Interner> WhereClause<I> {
pub fn into_well_formed_goal(self, interner: &I) -> DomainGoal<I> {
match self {
WhereClause::Implemented(trait_ref) => WellFormed::Trait(trait_ref).cast(interner),
wc => wc.cast(interner),
}
}
pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
match self {
WhereClause::Implemented(trait_ref) => FromEnv::Trait(trait_ref).cast(interner),
wc => wc.cast(interner),
}
}
}
impl<I: Interner> QuantifiedWhereClause<I> {
pub fn into_well_formed_goal(self, interner: &I) -> Binders<DomainGoal<I>> {
self.map(|wc| wc.into_well_formed_goal(interner))
}
pub fn into_from_env_goal(self, interner: &I) -> Binders<DomainGoal<I>> {
self.map(|wc| wc.into_from_env_goal(interner))
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct QuantifiedWhereClauses<I: Interner> {
interned: I::InternedQuantifiedWhereClauses,
}
impl<I: Interner> QuantifiedWhereClauses<I> {
pub fn new(interner: &I) -> Self {
Self::from(interner, None::<QuantifiedWhereClause<I>>)
}
pub fn interned(&self) -> &I::InternedQuantifiedWhereClauses {
&self.interned
}
pub fn from(
interner: &I,
clauses: impl IntoIterator<Item = impl CastTo<QuantifiedWhereClause<I>>>,
) -> Self {
Self::from_fallible(
interner,
clauses
.into_iter()
.map(|p| -> Result<QuantifiedWhereClause<I>, ()> { Ok(p.cast(interner)) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
clauses: impl IntoIterator<Item = Result<impl CastTo<QuantifiedWhereClause<I>>, E>>,
) -> Result<Self, E> {
use crate::cast::Caster;
Ok(QuantifiedWhereClauses {
interned: I::intern_quantified_where_clauses(
interner,
clauses.into_iter().casted(interner),
)?,
})
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, QuantifiedWhereClause<I>> {
self.as_slice(interner).iter()
}
pub fn is_empty(&self, interner: &I) -> bool {
self.as_slice(interner).is_empty()
}
pub fn len(&self, interner: &I) -> usize {
self.as_slice(interner).len()
}
pub fn as_slice(&self, interner: &I) -> &[QuantifiedWhereClause<I>] {
interner.quantified_where_clauses_data(&self.interned)
}
}
impl<I: Interner> DomainGoal<I> {
pub fn into_from_env_goal(self, interner: &I) -> DomainGoal<I> {
match self {
DomainGoal::Holds(wc) => wc.into_from_env_goal(interner),
goal => goal,
}
}
pub fn inputs(&self, interner: &I) -> Vec<GenericArg<I>> {
match self {
DomainGoal::Holds(WhereClause::AliasEq(alias_eq)) => {
vec![GenericArgData::Ty(alias_eq.alias.clone().intern(interner)).intern(interner)]
}
_ => Vec::new(),
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
pub struct EqGoal<I: Interner> {
pub a: GenericArg<I>,
pub b: GenericArg<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
pub struct Normalize<I: Interner> {
pub alias: AliasTy<I>,
pub ty: Ty<I>,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, Zip)]
pub struct AliasEq<I: Interner> {
pub alias: AliasTy<I>,
pub ty: Ty<I>,
}
impl<I: Interner> HasInterner for AliasEq<I> {
type Interner = I;
}
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct Binders<T: HasInterner> {
pub binders: VariableKinds<T::Interner>,
value: T,
}
impl<T: HasInterner> HasInterner for Binders<T> {
type Interner = T::Interner;
}
impl<T: HasInterner> Binders<T> {
pub fn new(binders: VariableKinds<T::Interner>, value: T) -> Self {
Self { binders, value }
}
pub fn empty(interner: &T::Interner, value: T) -> Self {
let binders = VariableKinds::new(interner);
Self { binders, value }
}
pub fn skip_binders(&self) -> &T {
&self.value
}
pub fn as_ref(&self) -> Binders<&T> {
Binders {
binders: self.binders.clone(),
value: &self.value,
}
}
pub fn map<U, OP>(self, op: OP) -> Binders<U>
where
OP: FnOnce(T) -> U,
U: HasInterner<Interner = T::Interner>,
{
let value = op(self.value);
Binders {
binders: self.binders,
value,
}
}
pub fn filter_map<U, OP>(self, op: OP) -> Option<Binders<U>>
where
OP: FnOnce(T) -> Option<U>,
U: HasInterner<Interner = T::Interner>,
{
let value = op(self.value)?;
Some(Binders {
binders: self.binders,
value,
})
}
pub fn map_ref<'a, U, OP>(&'a self, op: OP) -> Binders<U>
where
OP: FnOnce(&'a T) -> U,
U: HasInterner<Interner = T::Interner>,
{
self.as_ref().map(op)
}
pub fn identity_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner> {
Substitution::from(
interner,
self.binders
.iter(interner)
.enumerate()
.map(|(i, pk)| (pk, i).to_generic_arg(interner)),
)
}
pub fn with_fresh_type_var(
interner: &T::Interner,
op: impl FnOnce(Ty<T::Interner>) -> T,
) -> Binders<T> {
let new_var = TyData::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0)).intern(interner);
let value = op(new_var);
let binders = VariableKinds::from(interner, iter::once(VariableKind::Ty(TyKind::General)));
Binders { binders, value }
}
pub fn len(&self, interner: &T::Interner) -> usize {
self.binders.len(interner)
}
}
impl<T, I> Binders<Binders<T>>
where
T: Fold<I, I> + HasInterner<Interner = I>,
T::Result: HasInterner<Interner = I>,
I: Interner,
{
pub fn fuse_binders(self, interner: &T::Interner) -> Binders<T::Result> {
let num_binders = self.len(interner);
let subst = Substitution::from(
interner,
self.value
.binders
.iter(interner)
.enumerate()
.map(|(i, pk)| (pk, i + num_binders).to_generic_arg(interner)),
);
let value = self.value.substitute(interner, &subst);
let binders = VariableKinds::from(
interner,
self.binders
.iter(interner)
.chain(self.value.binders.iter(interner))
.cloned(),
);
Binders { binders, value }
}
}
impl<T: HasInterner> From<Binders<T>> for (VariableKinds<T::Interner>, T) {
fn from(binders: Binders<T>) -> Self {
(binders.binders, binders.value)
}
}
impl<T, I> Binders<T>
where
T: Fold<I, I> + HasInterner<Interner = I>,
I: Interner,
{
pub fn substitute(
&self,
interner: &I,
parameters: &(impl AsParameters<I> + ?Sized),
) -> T::Result {
let parameters = parameters.as_parameters(interner);
assert_eq!(self.binders.len(interner), parameters.len());
Subst::apply(interner, parameters, &self.value)
}
}
impl<'a, V> IntoIterator for &'a Binders<V>
where
V: HasInterner,
&'a V: IntoIterator,
<&'a V as IntoIterator>::Item: HasInterner<Interner = V::Interner>,
{
type Item = Binders<<&'a V as IntoIterator>::Item>;
type IntoIter = BindersIntoIterator<&'a V>;
fn into_iter(self) -> Self::IntoIter {
self.map_ref(|r| r).into_iter()
}
}
impl<V, U> IntoIterator for Binders<V>
where
V: HasInterner + IntoIterator<Item = U>,
U: HasInterner<Interner = V::Interner>,
{
type Item = Binders<U>;
type IntoIter = BindersIntoIterator<V>;
fn into_iter(self) -> Self::IntoIter {
BindersIntoIterator {
iter: self.value.into_iter(),
binders: self.binders,
}
}
}
pub struct BindersIntoIterator<V: HasInterner + IntoIterator> {
iter: <V as IntoIterator>::IntoIter,
binders: VariableKinds<V::Interner>,
}
impl<V> Iterator for BindersIntoIterator<V>
where
V: HasInterner + IntoIterator,
<V as IntoIterator>::Item: HasInterner<Interner = V::Interner>,
{
type Item = Binders<<V as IntoIterator>::Item>;
fn next(&mut self) -> Option<Self::Item> {
self.iter
.next()
.map(|v| Binders::new(self.binders.clone(), v))
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub struct ProgramClauseImplication<I: Interner> {
pub consequence: DomainGoal<I>,
pub conditions: Goals<I>,
pub priority: ClausePriority,
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
pub enum ClausePriority {
High,
Low,
}
impl std::ops::BitAnd for ClausePriority {
type Output = ClausePriority;
fn bitand(self, rhs: ClausePriority) -> Self::Output {
match (self, rhs) {
(ClausePriority::High, ClausePriority::High) => ClausePriority::High,
_ => ClausePriority::Low,
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, HasInterner, Zip)]
pub enum ProgramClauseData<I: Interner> {
Implies(ProgramClauseImplication<I>),
ForAll(Binders<ProgramClauseImplication<I>>),
}
impl<I: Interner> ProgramClauseImplication<I> {
pub fn into_from_env_clause(self, interner: &I) -> ProgramClauseImplication<I> {
if self.conditions.is_empty(interner) {
ProgramClauseImplication {
consequence: self.consequence.into_from_env_goal(interner),
conditions: self.conditions.clone(),
priority: self.priority,
}
} else {
self
}
}
}
impl<I: Interner> ProgramClauseData<I> {
pub fn into_from_env_clause(self, interner: &I) -> ProgramClauseData<I> {
match self {
ProgramClauseData::Implies(implication) => {
ProgramClauseData::Implies(implication.into_from_env_clause(interner))
}
ProgramClauseData::ForAll(binders_implication) => ProgramClauseData::ForAll(
binders_implication.map(|i| i.into_from_env_clause(interner)),
),
}
}
pub fn intern(self, interner: &I) -> ProgramClause<I> {
ProgramClause {
interned: interner.intern_program_clause(self),
}
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct ProgramClause<I: Interner> {
interned: I::InternedProgramClause,
}
impl<I: Interner> ProgramClause<I> {
pub fn new(interner: &I, clause: ProgramClauseData<I>) -> Self {
let interned = interner.intern_program_clause(clause);
Self { interned }
}
pub fn into_from_env_clause(self, interner: &I) -> ProgramClause<I> {
let program_clause_data = self.data(interner);
let new_clause = program_clause_data.clone().into_from_env_clause(interner);
Self::new(interner, new_clause)
}
pub fn interned(&self) -> &I::InternedProgramClause {
&self.interned
}
pub fn data(&self, interner: &I) -> &ProgramClauseData<I> {
interner.program_clause_data(&self.interned)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct ProgramClauses<I: Interner> {
interned: I::InternedProgramClauses,
}
impl<I: Interner> ProgramClauses<I> {
pub fn new(interner: &I) -> Self {
Self::from(interner, None::<ProgramClause<I>>)
}
pub fn interned(&self) -> &I::InternedProgramClauses {
&self.interned
}
pub fn from(
interner: &I,
clauses: impl IntoIterator<Item = impl CastTo<ProgramClause<I>>>,
) -> Self {
Self::from_fallible(
interner,
clauses
.into_iter()
.map(|p| -> Result<ProgramClause<I>, ()> { Ok(p.cast(interner)) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
clauses: impl IntoIterator<Item = Result<impl CastTo<ProgramClause<I>>, E>>,
) -> Result<Self, E> {
use crate::cast::Caster;
Ok(ProgramClauses {
interned: I::intern_program_clauses(interner, clauses.into_iter().casted(interner))?,
})
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, ProgramClause<I>> {
self.as_slice(interner).iter()
}
pub fn is_empty(&self, interner: &I) -> bool {
self.as_slice(interner).is_empty()
}
pub fn len(&self, interner: &I) -> usize {
self.as_slice(interner).len()
}
pub fn as_slice(&self, interner: &I) -> &[ProgramClause<I>] {
interner.program_clauses_data(&self.interned)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct VariableKinds<I: Interner> {
interned: I::InternedVariableKinds,
}
impl<I: Interner> VariableKinds<I> {
pub fn new(interner: &I) -> Self {
Self::from(interner, None::<VariableKind<I>>)
}
pub fn interned(&self) -> &I::InternedVariableKinds {
&self.interned
}
pub fn from(interner: &I, variable_kinds: impl IntoIterator<Item = VariableKind<I>>) -> Self {
Self::from_fallible(
interner,
variable_kinds
.into_iter()
.map(|p| -> Result<VariableKind<I>, ()> { Ok(p) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
variable_kinds: impl IntoIterator<Item = Result<VariableKind<I>, E>>,
) -> Result<Self, E> {
Ok(VariableKinds {
interned: I::intern_generic_arg_kinds(interner, variable_kinds.into_iter())?,
})
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, VariableKind<I>> {
self.as_slice(interner).iter()
}
pub fn is_empty(&self, interner: &I) -> bool {
self.as_slice(interner).is_empty()
}
pub fn len(&self, interner: &I) -> usize {
self.as_slice(interner).len()
}
pub fn as_slice(&self, interner: &I) -> &[VariableKind<I>] {
interner.variable_kinds_data(&self.interned)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct CanonicalVarKinds<I: Interner> {
interned: I::InternedCanonicalVarKinds,
}
impl<I: Interner> CanonicalVarKinds<I> {
pub fn new(interner: &I) -> Self {
Self::from(interner, None::<CanonicalVarKind<I>>)
}
pub fn interned(&self) -> &I::InternedCanonicalVarKinds {
&self.interned
}
pub fn from(
interner: &I,
variable_kinds: impl IntoIterator<Item = CanonicalVarKind<I>>,
) -> Self {
Self::from_fallible(
interner,
variable_kinds
.into_iter()
.map(|p| -> Result<CanonicalVarKind<I>, ()> { Ok(p) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
variable_kinds: impl IntoIterator<Item = Result<CanonicalVarKind<I>, E>>,
) -> Result<Self, E> {
Ok(CanonicalVarKinds {
interned: I::intern_canonical_var_kinds(interner, variable_kinds.into_iter())?,
})
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, CanonicalVarKind<I>> {
self.as_slice(interner).iter()
}
pub fn is_empty(&self, interner: &I) -> bool {
self.as_slice(interner).is_empty()
}
pub fn len(&self, interner: &I) -> usize {
self.as_slice(interner).len()
}
pub fn as_slice(&self, interner: &I) -> &[CanonicalVarKind<I>] {
interner.canonical_var_kinds_data(&self.interned)
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Canonical<T: HasInterner> {
pub value: T,
pub binders: CanonicalVarKinds<T::Interner>,
}
impl<T: HasInterner> HasInterner for Canonical<T> {
type Interner = T::Interner;
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct UCanonical<T: HasInterner> {
pub canonical: Canonical<T>,
pub universes: usize,
}
impl<T: HasInterner> UCanonical<T> {
pub fn is_trivial_substitution(
&self,
interner: &T::Interner,
canonical_subst: &Canonical<AnswerSubst<T::Interner>>,
) -> bool {
let subst = &canonical_subst.value.subst;
assert_eq!(
self.canonical.binders.len(interner),
subst.parameters(interner).len()
);
subst.is_identity_subst(interner)
}
pub fn trivial_substitution(&self, interner: &T::Interner) -> Substitution<T::Interner> {
let binders = &self.canonical.binders;
Substitution::from(
interner,
binders
.iter(interner)
.enumerate()
.map(|(index, pk)| {
let bound_var = BoundVar::new(DebruijnIndex::INNERMOST, index);
match &pk.kind {
VariableKind::Ty(_) => {
GenericArgData::Ty(TyData::BoundVar(bound_var).intern(interner))
.intern(interner)
}
VariableKind::Lifetime => GenericArgData::Lifetime(
LifetimeData::BoundVar(bound_var).intern(interner),
)
.intern(interner),
VariableKind::Const(ty) => GenericArgData::Const(
ConstData {
ty: ty.clone(),
value: ConstValue::BoundVar(bound_var),
}
.intern(interner),
)
.intern(interner),
}
})
.collect::<Vec<_>>(),
)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, HasInterner)]
pub struct Goals<I: Interner> {
interned: I::InternedGoals,
}
impl<I: Interner> Goals<I> {
pub fn new(interner: &I) -> Self {
Self::from(interner, None::<Goal<I>>)
}
pub fn interned(&self) -> &I::InternedGoals {
&self.interned
}
pub fn from(interner: &I, goals: impl IntoIterator<Item = impl CastTo<Goal<I>>>) -> Self {
Self::from_fallible(
interner,
goals
.into_iter()
.map(|p| -> Result<Goal<I>, ()> { Ok(p.cast(interner)) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
goals: impl IntoIterator<Item = Result<impl CastTo<Goal<I>>, E>>,
) -> Result<Self, E> {
use crate::cast::Caster;
Ok(Goals {
interned: I::intern_goals(interner, goals.into_iter().casted(interner))?,
})
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, Goal<I>> {
self.as_slice(interner).iter()
}
pub fn is_empty(&self, interner: &I) -> bool {
self.as_slice(interner).is_empty()
}
pub fn len(&self, interner: &I) -> usize {
self.as_slice(interner).len()
}
pub fn as_slice(&self, interner: &I) -> &[Goal<I>] {
interner.goals_data(&self.interned)
}
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, HasInterner)]
pub struct Goal<I: Interner> {
interned: I::InternedGoal,
}
impl<I: Interner> Goal<I> {
pub fn new(interner: &I, interned: GoalData<I>) -> Self {
let interned = I::intern_goal(interner, interned);
Self { interned }
}
pub fn interned(&self) -> &I::InternedGoal {
&self.interned
}
pub fn data(&self, interner: &I) -> &GoalData<I> {
interner.goal_data(&self.interned)
}
pub fn quantify(
self,
interner: &I,
kind: QuantifierKind,
binders: VariableKinds<I>,
) -> Goal<I> {
GoalData::Quantified(kind, Binders::new(binders, self)).intern(interner)
}
pub fn negate(self, interner: &I) -> Self {
GoalData::Not(self).intern(interner)
}
pub fn compatible(self, interner: &I) -> Self {
GoalData::Quantified(
QuantifierKind::ForAll,
Binders::with_fresh_type_var(interner, |ty| {
GoalData::Implies(
ProgramClauses::from(
interner,
vec![DomainGoal::Compatible(()), DomainGoal::DownstreamType(ty)],
),
self.shifted_in(interner),
)
.intern(interner)
}),
)
.intern(interner)
}
pub fn implied_by(self, interner: &I, predicates: ProgramClauses<I>) -> Goal<I> {
GoalData::Implies(predicates, self).intern(interner)
}
pub fn is_trivially_true(&self, interner: &I) -> bool {
match self.data(interner) {
GoalData::All(goals) => goals.is_empty(interner),
_ => false,
}
}
}
impl<I> Goal<I>
where
I: Interner,
{
pub fn all<II>(interner: &I, iter: II) -> Self
where
II: IntoIterator<Item = Goal<I>>,
{
let mut iter = iter.into_iter();
if let Some(goal0) = iter.next() {
if let Some(goal1) = iter.next() {
let goals = Goals::from(
interner,
Some(goal0).into_iter().chain(Some(goal1)).chain(iter),
);
GoalData::All(goals).intern(interner)
} else {
goal0
}
} else {
GoalData::All(Goals::new(interner)).intern(interner)
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner, Zip)]
pub enum GoalData<I: Interner> {
Quantified(QuantifierKind, Binders<Goal<I>>),
Implies(ProgramClauses<I>, Goal<I>),
All(Goals<I>),
Not(Goal<I>),
EqGoal(EqGoal<I>),
DomainGoal(DomainGoal<I>),
CannotProve(()),
}
impl<I: Interner> GoalData<I> {
pub fn intern(self, interner: &I) -> Goal<I> {
Goal::new(interner, self)
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum QuantifierKind {
ForAll,
Exists,
}
#[derive(Clone, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
pub enum Constraint<I: Interner> {
Outlives(Lifetime<I>, Lifetime<I>),
}
#[derive(Copy, Clone, PartialEq, Eq, Hash, HasInterner)]
pub struct Substitution<I: Interner> {
interned: I::InternedSubstitution,
}
impl<I: Interner> Substitution<I> {
pub fn from(
interner: &I,
parameters: impl IntoIterator<Item = impl CastTo<GenericArg<I>>>,
) -> Self {
Self::from_fallible(
interner,
parameters
.into_iter()
.map(|p| -> Result<GenericArg<I>, ()> { Ok(p.cast(interner)) }),
)
.unwrap()
}
pub fn from_fallible<E>(
interner: &I,
parameters: impl IntoIterator<Item = Result<impl CastTo<GenericArg<I>>, E>>,
) -> Result<Self, E> {
use crate::cast::Caster;
Ok(Substitution {
interned: I::intern_substitution(interner, parameters.into_iter().casted(interner))?,
})
}
pub fn interned(&self) -> &I::InternedSubstitution {
&self.interned
}
pub fn at(&self, interner: &I, index: usize) -> &GenericArg<I> {
&self.parameters(interner)[index]
}
pub fn from1(interner: &I, parameter: impl CastTo<GenericArg<I>>) -> Self {
Self::from(interner, Some(parameter))
}
pub fn empty(interner: &I) -> Self {
Self::from(interner, None::<GenericArg<I>>)
}
pub fn is_empty(&self, interner: &I) -> bool {
self.parameters(interner).is_empty()
}
pub fn iter(&self, interner: &I) -> std::slice::Iter<'_, GenericArg<I>> {
self.parameters(interner).iter()
}
pub fn parameters(&self, interner: &I) -> &[GenericArg<I>] {
interner.substitution_data(&self.interned)
}
pub fn len(&self, interner: &I) -> usize {
self.parameters(interner).len()
}
pub fn is_identity_subst(&self, interner: &I) -> bool {
self.iter(interner).zip(0..).all(|(generic_arg, index)| {
let index_db = BoundVar::new(DebruijnIndex::INNERMOST, index);
match generic_arg.data(interner) {
GenericArgData::Ty(ty) => match ty.data(interner) {
TyData::BoundVar(depth) => index_db == *depth,
_ => false,
},
GenericArgData::Lifetime(lifetime) => match lifetime.data(interner) {
LifetimeData::BoundVar(depth) => index_db == *depth,
_ => false,
},
GenericArgData::Const(constant) => match &constant.data(interner).value {
ConstValue::BoundVar(depth) => index_db == *depth,
_ => false,
},
}
})
}
pub fn apply<T>(&self, value: &T, interner: &I) -> T::Result
where
T: Fold<I, I>,
{
value
.fold_with(
&mut &SubstFolder {
interner,
subst: self,
},
DebruijnIndex::INNERMOST,
)
.unwrap()
}
}
struct SubstFolder<'i, I: Interner> {
interner: &'i I,
subst: &'i Substitution<I>,
}
impl<I: Interner> SubstFolder<'_, I> {
pub fn at(&self, index: usize) -> &GenericArg<I> {
let interner = self.interner;
&self.subst.parameters(interner)[index]
}
}
pub trait AsParameters<I: Interner> {
fn as_parameters(&self, interner: &I) -> &[GenericArg<I>];
}
impl<I: Interner> AsParameters<I> for Substitution<I> {
#[allow(unreachable_code, unused_variables)]
fn as_parameters(&self, interner: &I) -> &[GenericArg<I>] {
self.parameters(interner)
}
}
impl<I: Interner> AsParameters<I> for [GenericArg<I>] {
fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
self
}
}
impl<I: Interner> AsParameters<I> for [GenericArg<I>; 1] {
fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
self
}
}
impl<I: Interner> AsParameters<I> for Vec<GenericArg<I>> {
fn as_parameters(&self, _interner: &I) -> &[GenericArg<I>] {
self
}
}
impl<T, I: Interner> AsParameters<I> for &T
where
T: ?Sized + AsParameters<I>,
{
fn as_parameters(&self, interner: &I) -> &[GenericArg<I>] {
T::as_parameters(self, interner)
}
}
pub trait ToGenericArg<I: Interner> {
fn to_generic_arg(&self, interner: &I) -> GenericArg<I> {
self.to_generic_arg_at_depth(interner, DebruijnIndex::INNERMOST)
}
fn to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I>;
}
impl<'a, I: Interner> ToGenericArg<I> for (&'a VariableKind<I>, usize) {
fn to_generic_arg_at_depth(&self, interner: &I, debruijn: DebruijnIndex) -> GenericArg<I> {
let &(binder, index) = self;
let bound_var = BoundVar::new(debruijn, index);
binder.to_bound_variable(interner, bound_var)
}
}
impl<'i, I: Interner> Folder<'i, I> for &SubstFolder<'i, I> {
fn as_dyn(&mut self) -> &mut dyn Folder<'i, I> {
self
}
fn fold_free_var_ty(
&mut self,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Ty<I>> {
assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
let ty = self.at(bound_var.index);
let ty = ty.assert_ty_ref(self.interner());
Ok(ty.shifted_in_from(self.interner(), outer_binder))
}
fn fold_free_var_lifetime(
&mut self,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Lifetime<I>> {
assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
let l = self.at(bound_var.index);
let l = l.assert_lifetime_ref(self.interner());
Ok(l.shifted_in_from(self.interner(), outer_binder))
}
fn fold_free_var_const(
&mut self,
_ty: &Ty<I>,
bound_var: BoundVar,
outer_binder: DebruijnIndex,
) -> Fallible<Const<I>> {
assert_eq!(bound_var.debruijn, DebruijnIndex::INNERMOST);
let c = self.at(bound_var.index);
let c = c.assert_const_ref(self.interner());
Ok(c.shifted_in_from(self.interner(), outer_binder))
}
fn interner(&self) -> &'i I {
self.interner
}
fn target_interner(&self) -> &'i I {
self.interner()
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
pub struct ConstrainedSubst<I: Interner> {
pub subst: Substitution<I>,
pub constraints: Vec<InEnvironment<Constraint<I>>>,
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, Fold, Visit, HasInterner)]
pub struct AnswerSubst<I: Interner> {
pub subst: Substitution<I>,
pub constraints: Vec<InEnvironment<Constraint<I>>>,
pub delayed_subgoals: Vec<InEnvironment<Goal<I>>>,
}