1use std::{
4 borrow::Borrow,
5 ops::{Deref, DerefMut, Index, IndexMut, RangeFrom},
6};
7
8use derive_generic_visitor::{Drive, DriveMut, DriveTwo};
9use enum_as_inner::EnumAsInner;
10use index_vec::Idx;
11use serde::{Deserialize, Serialize};
12use serde_state::{DeserializeState, SerializeState};
13
14use crate::{ast::*, impl_from_enum};
15
16#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
18#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
19#[serde(transparent)]
20#[cfg_attr(feature = "charon_on_charon", charon::transparent)]
21pub struct DeBruijnId {
22 pub index: usize,
23}
24
25impl DeBruijnId {
26 pub const ZERO: DeBruijnId = DeBruijnId { index: 0 };
27}
28
29#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
64#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
65pub enum DeBruijnVar<Id> {
66 Bound(#[serde_state(stateless)] DeBruijnId, Id),
68 Free(Id),
73}
74
75generate_index_type!(RegionId, "Region");
80generate_index_type!(TypeVarId, "T");
81generate_index_type!(ConstGenericVarId, "Const");
82generate_index_type!(TraitClauseId, "TraitClause");
83generate_index_type!(TraitTypeConstraintId, "TraitTypeConstraint");
84
85#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
87#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
88pub enum Variance {
89 Covariant,
90 Invariant,
91 Contravariant,
92 Bivariant,
94 #[cfg_attr(feature = "charon_on_charon", charon::rename("VaUnknown"))]
97 Unknown,
98}
99
100impl Variance {
101 pub fn compose(outer: Variance, inner: Variance) -> Variance {
102 match (outer, inner) {
103 (Variance::Unknown, _) | (_, Variance::Unknown) => Variance::Unknown,
104 (Variance::Bivariant, _) | (_, Variance::Bivariant) => Variance::Bivariant,
105 (Variance::Invariant, _) | (_, Variance::Invariant) => Variance::Invariant,
106 (Variance::Covariant, variance) => variance,
107 (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
108 (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
109 }
110 }
111}
112
113#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
115#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
116pub struct TypeParam {
117 pub index: TypeVarId,
119 pub name: String,
121 pub variance: Variance,
123}
124
125#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
127#[derive(Serialize, Deserialize, Drive, DriveMut, DriveTwo)]
128pub struct RegionParam {
129 pub index: RegionId,
131 pub name: Option<String>,
133 pub variance: Variance,
135 pub mutability: LifetimeMutability,
139 pub late_bound: bool,
142}
143
144#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
147#[derive(EnumAsInner)]
148#[derive(Serialize, Deserialize)]
149#[cfg_attr(feature = "charon_on_charon", charon::variants_prefix("Lt"))]
150pub enum LifetimeMutability {
151 Mutable,
153 Shared,
155 Unknown,
157}
158
159#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
161#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
162pub struct ConstGenericParam {
163 pub index: ConstGenericVarId,
165 pub name: String,
167 pub ty: Ty,
169}
170
171#[derive(Debug, Clone)]
174#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
175pub struct TraitParam {
176 pub clause_id: TraitClauseId,
178 pub span: Option<Span>,
180 pub origin: PredicateOrigin,
182 #[cfg_attr(feature = "charon_on_charon", charon::rename("trait"))]
184 pub trait_: PolyTraitDeclRef,
185}
186
187#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
189#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
190pub enum PredicateOrigin {
191 WhereClauseOnFn,
198 WhereClauseOnType,
204 WhereClauseOnImpl,
211 TraitSelf,
217 WhereClauseOnTrait,
224 TraitItem(AssocTypeId),
230 #[cfg_attr(feature = "charon_on_charon", charon::rename("OriginDyn"))]
232 Dyn,
233}
234
235impl TypeParam {
236 pub fn new(index: TypeVarId, name: String, variance: Variance) -> Self {
237 Self {
238 index,
239 name,
240 variance,
241 }
242 }
243}
244
245impl RegionParam {
246 pub fn new(index: RegionId, name: Option<String>, variance: Variance) -> Self {
247 Self {
248 index,
249 name,
250 variance,
251 mutability: LifetimeMutability::Unknown,
252 late_bound: false,
253 }
254 }
255}
256
257impl ConstGenericParam {
258 pub fn new(index: ConstGenericVarId, name: String, ty: Ty) -> Self {
259 Self { index, name, ty }
260 }
261}
262
263impl TraitParam {
264 pub fn identity_tref(&self) -> PolyTraitRef {
266 self.identity_tref_at_depth(DeBruijnId::zero())
267 }
268
269 pub fn identity_tref_at_depth(&self, depth: DeBruijnId) -> PolyTraitRef {
271 let regions = self.trait_.identity_region_args();
272 PolyTraitRef(
273 self.trait_
274 .clone()
275 .move_under_binders(depth)
276 .map(|trait_decl_ref| {
277 TraitRef::new(
278 TraitRefKind::Clause(
279 DeBruijnVar::bound(depth.incr(), self.clause_id),
280 regions,
281 ),
282 trait_decl_ref,
283 )
284 }),
285 )
286 }
287}
288
289impl PartialEq for TraitParam {
290 fn eq(&self, other: &Self) -> bool {
291 self.clause_id == other.clause_id && self.trait_ == other.trait_
293 }
294}
295
296impl Eq for TraitParam {}
297
298impl PartialOrd for TraitParam {
299 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
300 Some(self.cmp(other))
301 }
302}
303
304impl Ord for TraitParam {
305 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
306 (&self.clause_id, &self.trait_).cmp(&(&other.clause_id, &other.trait_))
307 }
308}
309
310impl std::hash::Hash for TraitParam {
311 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
312 self.clause_id.hash(state);
313 self.trait_.hash(state);
314 }
315}
316
317pub type RegionDbVar = DeBruijnVar<RegionId>;
318pub type TypeDbVar = DeBruijnVar<TypeVarId>;
319pub type ConstGenericDbVar = DeBruijnVar<ConstGenericVarId>;
320pub type ClauseDbVar = DeBruijnVar<TraitClauseId>;
321
322pub trait TypeLevelVar: Idx + std::fmt::Debug + std::fmt::Display + AstVisitable {
323 type Param;
324 type Arg;
325 fn get_param_vec(params: &GenericParams) -> &IndexVec<Self, Self::Param>;
326 fn get_param_vec_mut(params: &mut GenericParams) -> &mut IndexVec<Self, Self::Param>;
327 fn get_arg_vec(args: &GenericArgs) -> &IndexVec<Self, Self::Arg>;
328 fn get_arg_vec_mut(args: &mut GenericArgs) -> &mut IndexVec<Self, Self::Arg>;
329}
330
331macro_rules! impl_type_level_var {
332 ($id:ty: $param:ty = $param_field:ident, $arg:ty = $arg_field:ident) => {
333 impl TypeLevelVar for $id {
334 type Param = $param;
335 type Arg = $arg;
336 fn get_param_vec(params: &GenericParams) -> &IndexVec<Self, Self::Param> {
337 ¶ms.$param_field
338 }
339 fn get_param_vec_mut(params: &mut GenericParams) -> &mut IndexVec<Self, Self::Param> {
340 &mut params.$param_field
341 }
342 fn get_arg_vec(args: &GenericArgs) -> &IndexVec<Self, Self::Arg> {
343 &args.$arg_field
344 }
345 fn get_arg_vec_mut(args: &mut GenericArgs) -> &mut IndexVec<Self, Self::Arg> {
346 &mut args.$arg_field
347 }
348 }
349 };
350}
351impl_type_level_var!(RegionId: RegionParam = regions, Region = regions);
352impl_type_level_var!(TypeVarId: TypeParam = types, Ty = types);
353impl_type_level_var!(
354 ConstGenericVarId: ConstGenericParam = const_generics,
355 ConstantExpr = const_generics
356);
357impl_type_level_var!(TraitClauseId: TraitParam = trait_clauses, PolyTraitRef = trait_refs);
358
359impl_from_enum!(Region::Var(RegionDbVar));
360impl_from_enum!(TyKind::TypeVar(TypeDbVar));
361impl_from_enum!(ConstantExprKind::Var(ConstGenericDbVar));
362impl From<TypeDbVar> for Ty {
363 fn from(x: TypeDbVar) -> Self {
364 TyKind::TypeVar(x).into_ty()
365 }
366}
367
368impl DeBruijnId {
369 pub fn zero() -> Self {
370 DeBruijnId { index: 0 }
371 }
372
373 pub fn one() -> Self {
374 DeBruijnId { index: 1 }
375 }
376
377 pub fn new(index: usize) -> Self {
378 DeBruijnId { index }
379 }
380
381 pub fn is_zero(&self) -> bool {
382 self.index == 0
383 }
384
385 pub fn incr(&self) -> Self {
386 DeBruijnId {
387 index: self.index + 1,
388 }
389 }
390
391 pub fn decr(&self) -> Self {
392 DeBruijnId {
393 index: self.index - 1,
394 }
395 }
396
397 pub fn plus(&self, delta: Self) -> Self {
398 DeBruijnId {
399 index: self.index + delta.index,
400 }
401 }
402
403 pub fn sub(&self, delta: Self) -> Option<Self> {
404 Some(DeBruijnId {
405 index: self.index.checked_sub(delta.index)?,
406 })
407 }
408}
409
410impl<Id> DeBruijnVar<Id>
411where
412 Id: Copy,
413{
414 pub fn new_at_zero(id: Id) -> Self {
415 DeBruijnVar::Bound(DeBruijnId::new(0), id)
416 }
417
418 pub fn free(id: Id) -> Self {
419 DeBruijnVar::Free(id)
420 }
421
422 pub fn bound(index: DeBruijnId, id: Id) -> Self {
423 DeBruijnVar::Bound(index, id)
424 }
425
426 pub fn incr(&self) -> Self {
427 match *self {
428 DeBruijnVar::Bound(dbid, varid) => DeBruijnVar::Bound(dbid.incr(), varid),
429 DeBruijnVar::Free(varid) => DeBruijnVar::Free(varid),
430 }
431 }
432
433 pub fn decr(&self) -> Self {
434 match *self {
435 DeBruijnVar::Bound(dbid, varid) => DeBruijnVar::Bound(dbid.decr(), varid),
436 DeBruijnVar::Free(varid) => DeBruijnVar::Free(varid),
437 }
438 }
439
440 pub fn bound_at_depth(&self, depth: DeBruijnId) -> Option<Id> {
442 match *self {
443 DeBruijnVar::Bound(dbid, varid) if dbid == depth => Some(varid),
444 _ => None,
445 }
446 }
447 pub fn bound_at_depth_mut(&mut self, depth: DeBruijnId) -> Option<&mut Id> {
449 match self {
450 DeBruijnVar::Bound(dbid, varid) if *dbid == depth => Some(varid),
451 _ => None,
452 }
453 }
454
455 pub fn move_out_from_depth(&self, depth: DeBruijnId) -> Option<Self> {
458 Some(match *self {
459 DeBruijnVar::Bound(dbid, varid) => DeBruijnVar::Bound(dbid.sub(depth)?, varid),
460 DeBruijnVar::Free(_) => *self,
461 })
462 }
463
464 pub fn move_under_binders(&self, depth: DeBruijnId) -> Self {
466 match *self {
467 DeBruijnVar::Bound(dbid, varid) => DeBruijnVar::Bound(dbid.plus(depth), varid),
468 DeBruijnVar::Free(_) => *self,
469 }
470 }
471}
472
473impl Default for DeBruijnId {
474 fn default() -> Self {
475 Self::zero()
476 }
477}
478
479#[derive(Clone, Hash)]
484pub struct BindingStack<T> {
485 stack: Vec<T>,
488}
489
490impl<T> BindingStack<T> {
491 pub fn new(x: T) -> Self {
492 Self { stack: vec![x] }
493 }
494 pub fn empty() -> Self {
496 Self { stack: vec![] }
497 }
498
499 pub fn push(&mut self, x: T) {
500 self.stack.push(x);
501 }
502 pub fn pop(&mut self) -> Option<T> {
503 self.stack.pop()
504 }
505 pub fn into_iter(self) -> impl DoubleEndedIterator<Item = T> + ExactSizeIterator {
507 self.stack.into_iter().rev()
508 }
509}
510
511#[repr(transparent)]
513pub struct BinderSlice<T>([T]);
514
515impl<T> BinderSlice<T> {
516 fn from_slice(stack: &[T]) -> &Self {
517 unsafe { &*(stack as *const [T] as *const Self) }
519 }
520
521 fn from_slice_mut(stack: &mut [T]) -> &mut Self {
522 unsafe { &mut *(stack as *mut [T] as *mut Self) }
524 }
525
526 pub fn is_empty(&self) -> bool {
527 self.0.is_empty()
528 }
529 pub fn len(&self) -> usize {
530 self.0.len()
531 }
532 pub fn depth(&self) -> DeBruijnId {
533 DeBruijnId::new(self.0.len() - 1)
534 }
535
536 #[track_caller]
538 pub fn as_bound_var<Id>(&self, var: DeBruijnVar<Id>) -> (DeBruijnId, Id) {
539 match var {
540 DeBruijnVar::Bound(dbid, varid) => (dbid, varid),
541 DeBruijnVar::Free(..) => panic!("free variables are not bound anywhere"),
542 }
543 }
544 pub fn as_bound_var_with_outermost_free<Id>(&self, var: DeBruijnVar<Id>) -> (DeBruijnId, Id) {
547 match var {
548 DeBruijnVar::Bound(dbid, varid) => (dbid, varid),
549 DeBruijnVar::Free(varid) => (self.depth(), varid),
550 }
551 }
552 fn real_index(&self, id: DeBruijnId) -> Option<usize> {
554 self.0.len().checked_sub(id.index + 1)
555 }
556 pub fn get(&self, id: DeBruijnId) -> Option<&T> {
557 self.0.get(self.real_index(id)?)
558 }
559 #[track_caller]
561 pub fn get_var<Id: TypeLevelVar>(&self, var: DeBruijnVar<Id>) -> Option<&Id::Param>
562 where
563 T: Borrow<GenericParams>,
564 {
565 let (dbid, varid) = self.as_bound_var(var);
566 self.get(dbid)
567 .and_then(|x| Id::get_param_vec(x.borrow()).get(varid))
568 }
569 pub fn get_var_and_shift<'a, Id: TypeLevelVar, R>(
570 &'a self,
571 var: DeBruijnVar<Id>,
572 f: impl FnOnce(&'a Id::Param) -> R,
573 ) -> Option<R>
574 where
575 T: Borrow<GenericParams>,
576 R: TyVisitable,
577 {
578 let (depth, _) = self.as_bound_var(var);
579 self.get_var(var).map(|x| f(x).move_under_binders(depth))
580 }
581 pub fn get_var_with_outermost_free<Id: TypeLevelVar>(
582 &self,
583 var: DeBruijnVar<Id>,
584 ) -> Option<&Id::Param>
585 where
586 T: Borrow<GenericParams>,
587 {
588 let (dbid, varid) = self.as_bound_var_with_outermost_free(var);
589 self.get(dbid)
590 .and_then(|x| Id::get_param_vec(x.borrow()).get(varid))
591 }
592 pub fn get_mut(&mut self, id: DeBruijnId) -> Option<&mut T> {
593 let index = self.real_index(id)?;
594 self.0.get_mut(index)
595 }
596
597 pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator {
599 self.0.iter().rev()
600 }
601 pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> + ExactSizeIterator {
603 self.0.iter_mut().rev()
604 }
605 pub fn indices(
607 &self,
608 ) -> impl DoubleEndedIterator<Item = DeBruijnId> + ExactSizeIterator + use<T> {
609 (0..self.0.len()).map(DeBruijnId::new)
610 }
611 pub fn iter_enumerated(
613 &self,
614 ) -> impl DoubleEndedIterator<Item = (DeBruijnId, &T)> + ExactSizeIterator {
615 self.iter()
616 .enumerate()
617 .map(|(i, x)| (DeBruijnId::new(i), x))
618 }
619 pub fn iter_mut_enumerated(
621 &mut self,
622 ) -> impl DoubleEndedIterator<Item = (DeBruijnId, &mut T)> + ExactSizeIterator {
623 self.iter_mut()
624 .enumerate()
625 .map(|(i, x)| (DeBruijnId::new(i), x))
626 }
627
628 pub fn map_ref<'a, U>(&'a self, f: impl FnMut(&'a T) -> U) -> BindingStack<U> {
629 BindingStack {
630 stack: self.0.iter().map(f).collect(),
631 }
632 }
633
634 pub fn place_at_outermost<U>(&mut self, val: &U) -> (U, &mut T)
636 where
637 U: TyVisitable + Clone,
638 {
639 for (depth, binder) in self.iter_mut_enumerated().rev() {
640 if let Some(val) = val.clone().move_from_under_binders(depth) {
641 return (val, binder);
642 }
643 }
644 unreachable!()
646 }
647
648 pub fn innermost(&self) -> &T {
649 self.0.last().unwrap()
650 }
651 pub fn innermost_mut(&mut self) -> &mut T {
652 self.0.last_mut().unwrap()
653 }
654 pub fn outermost(&self) -> &T {
655 self.0.first().unwrap()
656 }
657 pub fn outermost_mut(&mut self) -> &mut T {
658 self.0.first_mut().unwrap()
659 }
660}
661
662impl<T> Deref for BindingStack<T> {
663 type Target = BinderSlice<T>;
664 fn deref(&self) -> &Self::Target {
665 BinderSlice::from_slice(&self.stack)
666 }
667}
668impl<T> DerefMut for BindingStack<T> {
669 fn deref_mut(&mut self) -> &mut Self::Target {
670 BinderSlice::from_slice_mut(&mut self.stack)
671 }
672}
673
674impl<T> Default for BindingStack<T> {
675 fn default() -> Self {
676 Self {
677 stack: Default::default(),
678 }
679 }
680}
681
682impl<T: std::fmt::Debug> std::fmt::Debug for BindingStack<T> {
683 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
684 write!(f, "{:?}", self.stack)
685 }
686}
687
688impl<T> Index<DeBruijnId> for BinderSlice<T> {
689 type Output = T;
690 fn index(&self, id: DeBruijnId) -> &Self::Output {
691 self.get(id).unwrap()
692 }
693}
694impl<T> IndexMut<DeBruijnId> for BinderSlice<T> {
695 fn index_mut(&mut self, id: DeBruijnId) -> &mut Self::Output {
696 self.get_mut(id).unwrap()
697 }
698}
699
700impl<T> Index<RangeFrom<DeBruijnId>> for BinderSlice<T> {
702 type Output = BinderSlice<T>;
703 fn index(&self, range: RangeFrom<DeBruijnId>) -> &Self::Output {
704 let end = self.0.len() - range.start.index;
705 BinderSlice::from_slice(&self.0[..end])
706 }
707}
708impl<T> IndexMut<RangeFrom<DeBruijnId>> for BinderSlice<T> {
709 fn index_mut(&mut self, range: RangeFrom<DeBruijnId>) -> &mut Self::Output {
710 let end = self.0.len() - range.start.index;
711 BinderSlice::from_slice_mut(&mut self.0[..end])
712 }
713}