charon_lib/ast/
types_utils.rs

1//! This file groups everything which is linked to implementations about [crate::types]
2use crate::ast::*;
3use crate::ids::Vector;
4use derive_generic_visitor::*;
5use std::collections::HashSet;
6use std::convert::Infallible;
7use std::fmt::Debug;
8use std::iter::Iterator;
9use std::mem;
10
11impl TraitClause {
12    /// Constructs the trait ref that refers to this clause.
13    pub fn identity_tref(&self) -> TraitRef {
14        self.identity_tref_at_depth(DeBruijnId::zero())
15    }
16
17    /// Like `identity_tref` but uses variables bound at the given depth.
18    pub fn identity_tref_at_depth(&self, depth: DeBruijnId) -> TraitRef {
19        TraitRef {
20            kind: TraitRefKind::Clause(DeBruijnVar::bound(depth, self.clause_id)),
21            trait_decl_ref: self.trait_.clone().move_under_binders(depth),
22        }
23    }
24}
25
26impl GenericParams {
27    pub fn empty() -> Self {
28        Self::default()
29    }
30
31    pub fn is_empty(&self) -> bool {
32        self.len() == 0
33    }
34    /// Whether this has any explicit arguments (types, regions or const generics).
35    pub fn has_explicits(&self) -> bool {
36        !self.regions.is_empty() || !self.types.is_empty() || !self.const_generics.is_empty()
37    }
38    /// Whether this has any implicit arguments (trait clauses, outlives relations, associated type
39    /// equality constraints).
40    pub fn has_predicates(&self) -> bool {
41        !self.trait_clauses.is_empty()
42            || !self.types_outlive.is_empty()
43            || !self.regions_outlive.is_empty()
44            || !self.trait_type_constraints.is_empty()
45    }
46
47    /// Run some sanity checks.
48    pub fn check_consistency(&self) {
49        // Sanity check: check the clause ids are consistent.
50        assert!(
51            self.trait_clauses
52                .iter()
53                .enumerate()
54                .all(|(i, c)| c.clause_id.index() == i)
55        );
56
57        // Sanity check: region names are pairwise distinct (this caused trouble when generating
58        // names for the backward functions in Aeneas): at some point, Rustc introduced names equal
59        // to `Some("'_")` for the anonymous regions, instead of using `None` (we now check in
60        // [translate_region_name] and ignore names equal to "'_").
61        let mut s = HashSet::new();
62        for r in &self.regions {
63            if let Some(name) = &r.name {
64                assert!(
65                    !s.contains(name),
66                    "Name \"{}\" reused for two different lifetimes",
67                    name
68                );
69                s.insert(name);
70            }
71        }
72    }
73
74    pub fn len(&self) -> usize {
75        let GenericParams {
76            regions,
77            types,
78            const_generics,
79            trait_clauses,
80            regions_outlive,
81            types_outlive,
82            trait_type_constraints,
83        } = self;
84        regions.elem_count()
85            + types.elem_count()
86            + const_generics.elem_count()
87            + trait_clauses.elem_count()
88            + regions_outlive.len()
89            + types_outlive.len()
90            + trait_type_constraints.elem_count()
91    }
92
93    /// Construct a set of generic arguments in the scope of `self` that matches `self` and feeds
94    /// each required parameter with itself. E.g. given parameters for `<T, U> where U:
95    /// PartialEq<T>`, the arguments would be `<T, U>[@TraitClause0]`.
96    pub fn identity_args(&self) -> GenericArgs {
97        self.identity_args_at_depth(DeBruijnId::zero())
98    }
99
100    /// Like `identity_args` but uses variables bound at the given depth.
101    pub fn identity_args_at_depth(&self, depth: DeBruijnId) -> GenericArgs {
102        GenericArgs {
103            regions: self
104                .regions
105                .map_ref_indexed(|id, _| Region::Var(DeBruijnVar::bound(depth, id))),
106            types: self
107                .types
108                .map_ref_indexed(|id, _| TyKind::TypeVar(DeBruijnVar::bound(depth, id)).into_ty()),
109            const_generics: self
110                .const_generics
111                .map_ref_indexed(|id, _| ConstGeneric::Var(DeBruijnVar::bound(depth, id))),
112            trait_refs: self
113                .trait_clauses
114                .map_ref(|clause| clause.identity_tref_at_depth(depth)),
115        }
116    }
117}
118
119impl<T> Binder<T> {
120    pub fn new(kind: BinderKind, params: GenericParams, skip_binder: T) -> Self {
121        Self {
122            params,
123            skip_binder,
124            kind,
125        }
126    }
127
128    /// Substitute the provided arguments for the variables bound in this binder and return the
129    /// substituted inner value.
130    pub fn apply(self, args: &GenericArgs) -> T
131    where
132        T: TyVisitable,
133    {
134        self.skip_binder.substitute(args)
135    }
136}
137
138impl<T: AstVisitable> Binder<Binder<T>> {
139    /// Flatten two levels of binders into a single one.
140    pub fn flatten(self) -> Binder<T> {
141        #[derive(Visitor)]
142        struct FlattenVisitor<'a> {
143            shift_by: &'a GenericParams,
144            binder_depth: DeBruijnId,
145        }
146        impl VisitorWithBinderDepth for FlattenVisitor<'_> {
147            fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
148                &mut self.binder_depth
149            }
150        }
151        impl VisitAstMut for FlattenVisitor<'_> {
152            fn visit<'a, T: AstVisitable>(&'a mut self, x: &mut T) -> ControlFlow<Self::Break> {
153                VisitWithBinderDepth::new(self).visit(x)
154            }
155
156            fn enter_de_bruijn_id(&mut self, db_id: &mut DeBruijnId) {
157                if *db_id > self.binder_depth {
158                    // We started visiting at the inner binder, so in this branch we're either
159                    // mentioning the outer binder or a binder further beyond. Either way we
160                    // decrease the depth; variables that point to the outer binder don't have to
161                    // be shifted.
162                    *db_id = db_id.decr();
163                }
164            }
165            fn enter_region(&mut self, x: &mut Region) {
166                if let Region::Var(var) = x
167                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
168                {
169                    *id += self.shift_by.regions.slot_count();
170                }
171            }
172            fn enter_ty_kind(&mut self, x: &mut TyKind) {
173                if let TyKind::TypeVar(var) = x
174                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
175                {
176                    *id += self.shift_by.types.slot_count();
177                }
178            }
179            fn enter_const_generic(&mut self, x: &mut ConstGeneric) {
180                if let ConstGeneric::Var(var) = x
181                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
182                {
183                    *id += self.shift_by.const_generics.slot_count();
184                }
185            }
186            fn enter_trait_ref_kind(&mut self, x: &mut TraitRefKind) {
187                if let TraitRefKind::Clause(var) = x
188                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
189                {
190                    *id += self.shift_by.trait_clauses.slot_count();
191                }
192            }
193        }
194
195        // We will concatenate both sets of params.
196        let mut outer_params = self.params;
197
198        // The inner value needs to change:
199        // - at binder level 0 we shift all variable ids to match the concatenated params;
200        // - at binder level > 0 we decrease binding level because there's one fewer binder.
201        let mut bound_value = self.skip_binder.skip_binder;
202        let _ = bound_value.drive_mut(&mut FlattenVisitor {
203            shift_by: &outer_params,
204            binder_depth: Default::default(),
205        });
206
207        // The inner params must also be updated, as they can refer to themselves and the outer
208        // one.
209        let mut inner_params = self.skip_binder.params;
210        let _ = inner_params.drive_mut(&mut FlattenVisitor {
211            shift_by: &outer_params,
212            binder_depth: Default::default(),
213        });
214        inner_params
215            .regions
216            .iter_mut()
217            .for_each(|v| v.index += outer_params.regions.slot_count());
218        inner_params
219            .types
220            .iter_mut()
221            .for_each(|v| v.index += outer_params.types.slot_count());
222        inner_params
223            .const_generics
224            .iter_mut()
225            .for_each(|v| v.index += outer_params.const_generics.slot_count());
226        inner_params
227            .trait_clauses
228            .iter_mut()
229            .for_each(|v| v.clause_id += outer_params.trait_clauses.slot_count());
230
231        let GenericParams {
232            regions,
233            types,
234            const_generics,
235            trait_clauses,
236            regions_outlive,
237            types_outlive,
238            trait_type_constraints,
239        } = &inner_params;
240        outer_params.regions.extend_from_slice(regions);
241        outer_params.types.extend_from_slice(types);
242        outer_params
243            .const_generics
244            .extend_from_slice(const_generics);
245        outer_params.trait_clauses.extend_from_slice(trait_clauses);
246        outer_params
247            .regions_outlive
248            .extend_from_slice(regions_outlive);
249        outer_params.types_outlive.extend_from_slice(types_outlive);
250        outer_params
251            .trait_type_constraints
252            .extend_from_slice(trait_type_constraints);
253
254        Binder {
255            params: outer_params,
256            skip_binder: bound_value,
257            kind: BinderKind::Other,
258        }
259    }
260}
261
262impl<T> RegionBinder<T> {
263    /// Wrap the value in an empty region binder, shifting variables appropriately.
264    pub fn empty(x: T) -> Self
265    where
266        T: TyVisitable,
267    {
268        RegionBinder {
269            regions: Default::default(),
270            skip_binder: x.move_under_binder(),
271        }
272    }
273
274    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> RegionBinder<U> {
275        RegionBinder {
276            regions: self.regions,
277            skip_binder: f(self.skip_binder),
278        }
279    }
280
281    pub fn map_ref<U>(&self, f: impl FnOnce(&T) -> U) -> RegionBinder<U> {
282        RegionBinder {
283            regions: self.regions.clone(),
284            skip_binder: f(&self.skip_binder),
285        }
286    }
287
288    /// Substitute the bound variables with the given lifetimes.
289    pub fn apply(self, regions: Vector<RegionId, Region>) -> T
290    where
291        T: AstVisitable,
292    {
293        assert_eq!(regions.slot_count(), self.regions.slot_count());
294        let args = GenericArgs {
295            regions,
296            ..GenericArgs::empty()
297        };
298        self.skip_binder.substitute(&args)
299    }
300
301    /// Substitute the bound variables with erased lifetimes.
302    pub fn erase(self) -> T
303    where
304        T: AstVisitable,
305    {
306        let regions = self.regions.map_ref_indexed(|_, _| Region::Erased);
307        self.apply(regions)
308    }
309}
310
311impl GenericArgs {
312    pub fn len(&self) -> usize {
313        let GenericArgs {
314            regions,
315            types,
316            const_generics,
317            trait_refs,
318        } = self;
319        regions.elem_count()
320            + types.elem_count()
321            + const_generics.elem_count()
322            + trait_refs.elem_count()
323    }
324
325    pub fn is_empty(&self) -> bool {
326        self.len() == 0
327    }
328    /// Whether this has any explicit arguments (types, regions or const generics).
329    pub fn has_explicits(&self) -> bool {
330        !self.regions.is_empty() || !self.types.is_empty() || !self.const_generics.is_empty()
331    }
332    /// Whether this has any implicit arguments (trait refs).
333    pub fn has_implicits(&self) -> bool {
334        !self.trait_refs.is_empty()
335    }
336
337    pub fn empty() -> Self {
338        GenericArgs {
339            regions: Default::default(),
340            types: Default::default(),
341            const_generics: Default::default(),
342            trait_refs: Default::default(),
343        }
344    }
345
346    pub fn new_for_builtin(types: Vector<TypeVarId, Ty>) -> Self {
347        GenericArgs {
348            types,
349            ..Self::empty()
350        }
351    }
352
353    pub fn new(
354        regions: Vector<RegionId, Region>,
355        types: Vector<TypeVarId, Ty>,
356        const_generics: Vector<ConstGenericVarId, ConstGeneric>,
357        trait_refs: Vector<TraitClauseId, TraitRef>,
358    ) -> Self {
359        Self {
360            regions,
361            types,
362            const_generics,
363            trait_refs,
364        }
365    }
366
367    pub fn new_types(types: Vector<TypeVarId, Ty>) -> Self {
368        Self {
369            types,
370            ..Self::empty()
371        }
372    }
373
374    /// Check whether this matches the given `GenericParams`.
375    /// TODO: check more things, e.g. that the trait refs use the correct trait and generics.
376    pub fn matches(&self, params: &GenericParams) -> bool {
377        params.regions.elem_count() == self.regions.elem_count()
378            && params.types.elem_count() == self.types.elem_count()
379            && params.const_generics.elem_count() == self.const_generics.elem_count()
380            && params.trait_clauses.elem_count() == self.trait_refs.elem_count()
381    }
382
383    /// Return the same generics, but where we pop the first type arguments.
384    /// This is useful for trait references (for pretty printing for instance),
385    /// because the first type argument is the type for which the trait is
386    /// implemented.
387    pub fn pop_first_type_arg(&self) -> (Ty, Self) {
388        let mut generics = self.clone();
389        let mut it = mem::take(&mut generics.types).into_iter();
390        let ty = it.next().unwrap();
391        generics.types = it.collect();
392        (ty, generics)
393    }
394
395    /// Concatenate this set of arguments with another one. Use with care, you must manage the
396    /// order of arguments correctly.
397    pub fn concat(mut self, other: &Self) -> Self {
398        let Self {
399            regions,
400            types,
401            const_generics,
402            trait_refs,
403        } = other;
404        self.regions.extend_from_slice(regions);
405        self.types.extend_from_slice(types);
406        self.const_generics.extend_from_slice(const_generics);
407        self.trait_refs.extend_from_slice(trait_refs);
408        self
409    }
410}
411
412impl IntTy {
413    /// Important: this returns the target byte count for the types.
414    /// Must not be used for host types from rustc.
415    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
416        match self {
417            IntTy::Isize => ptr_size as usize,
418            IntTy::I8 => size_of::<i8>(),
419            IntTy::I16 => size_of::<i16>(),
420            IntTy::I32 => size_of::<i32>(),
421            IntTy::I64 => size_of::<i64>(),
422            IntTy::I128 => size_of::<i128>(),
423        }
424    }
425}
426impl UIntTy {
427    /// Important: this returns the target byte count for the types.
428    /// Must not be used for host types from rustc.
429    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
430        match self {
431            UIntTy::Usize => ptr_size as usize,
432            UIntTy::U8 => size_of::<u8>(),
433            UIntTy::U16 => size_of::<u16>(),
434            UIntTy::U32 => size_of::<u32>(),
435            UIntTy::U64 => size_of::<u64>(),
436            UIntTy::U128 => size_of::<u128>(),
437        }
438    }
439}
440impl FloatTy {
441    /// Important: this returns the target byte count for the types.
442    /// Must not be used for host types from rustc.
443    pub fn target_size(&self) -> usize {
444        match self {
445            FloatTy::F16 => size_of::<u16>(),
446            FloatTy::F32 => size_of::<u32>(),
447            FloatTy::F64 => size_of::<u64>(),
448            FloatTy::F128 => size_of::<u128>(),
449        }
450    }
451}
452
453impl IntegerTy {
454    pub fn to_unsigned(&self) -> Self {
455        match self {
456            IntegerTy::Signed(IntTy::Isize) => IntegerTy::Unsigned(UIntTy::Usize),
457            IntegerTy::Signed(IntTy::I8) => IntegerTy::Unsigned(UIntTy::U8),
458            IntegerTy::Signed(IntTy::I16) => IntegerTy::Unsigned(UIntTy::U16),
459            IntegerTy::Signed(IntTy::I32) => IntegerTy::Unsigned(UIntTy::U32),
460            IntegerTy::Signed(IntTy::I64) => IntegerTy::Unsigned(UIntTy::U64),
461            IntegerTy::Signed(IntTy::I128) => IntegerTy::Unsigned(UIntTy::U128),
462            _ => *self,
463        }
464    }
465
466    /// Important: this returns the target byte count for the types.
467    /// Must not be used for host types from rustc.
468    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
469        match self {
470            IntegerTy::Signed(ty) => ty.target_size(ptr_size),
471            IntegerTy::Unsigned(ty) => ty.target_size(ptr_size),
472        }
473    }
474}
475
476impl LiteralTy {
477    pub fn to_integer_ty(&self) -> Option<IntegerTy> {
478        match self {
479            Self::Int(int_ty) => Some(IntegerTy::Signed(*int_ty)),
480            Self::UInt(uint_ty) => Some(IntegerTy::Unsigned(*uint_ty)),
481            _ => None,
482        }
483    }
484
485    /// Important: this returns the target byte count for the types.
486    /// Must not be used for host types from rustc.
487    pub fn target_size(&self, ptr_size: ByteCount) -> usize {
488        match self {
489            LiteralTy::Int(int_ty) => int_ty.target_size(ptr_size),
490            LiteralTy::UInt(uint_ty) => uint_ty.target_size(ptr_size),
491            LiteralTy::Float(float_ty) => float_ty.target_size(),
492            LiteralTy::Char => 4,
493            LiteralTy::Bool => 1,
494        }
495    }
496}
497
498/// A value of type `T` bound by the generic parameters of item
499/// `item`. Used when dealing with multiple items at a time, to
500/// ensure we don't mix up generics.
501///
502/// To get the value, use `under_binder_of` or `subst_for`.
503#[derive(Debug, Clone, Copy)]
504pub struct ItemBinder<ItemId, T> {
505    pub item_id: ItemId,
506    val: T,
507}
508
509impl<ItemId, T> ItemBinder<ItemId, T>
510where
511    ItemId: Debug + Copy + PartialEq,
512{
513    pub fn new(item_id: ItemId, val: T) -> Self {
514        Self { item_id, val }
515    }
516
517    pub fn as_ref(&self) -> ItemBinder<ItemId, &T> {
518        ItemBinder {
519            item_id: self.item_id,
520            val: &self.val,
521        }
522    }
523
524    pub fn map_bound<U>(self, f: impl FnOnce(T) -> U) -> ItemBinder<ItemId, U> {
525        ItemBinder {
526            item_id: self.item_id,
527            val: f(self.val),
528        }
529    }
530
531    fn assert_item_id(&self, item_id: ItemId) {
532        assert_eq!(
533            self.item_id, item_id,
534            "Trying to use item bound for {:?} as if it belonged to {:?}",
535            self.item_id, item_id
536        );
537    }
538
539    /// Assert that the value is bound for item `item_id`, and returns it. This is used when we
540    /// plan to store the returned value inside that item.
541    pub fn under_binder_of(self, item_id: ItemId) -> T {
542        self.assert_item_id(item_id);
543        self.val
544    }
545
546    /// Given generic args for `item_id`, assert that the value is bound for `item_id` and
547    /// substitute it with the provided generic arguments. Because the arguments are bound in the
548    /// context of another item, so it the resulting substituted value.
549    pub fn substitute<OtherItem: Debug + Copy + PartialEq>(
550        self,
551        args: ItemBinder<OtherItem, &GenericArgs>,
552    ) -> ItemBinder<OtherItem, T>
553    where
554        ItemId: Into<AnyTransId>,
555        T: TyVisitable,
556    {
557        args.map_bound(|args| self.val.substitute(args))
558    }
559}
560
561/// Dummy item identifier that represents the current item when not ambiguous.
562#[derive(Debug, Clone, Copy, PartialEq, Eq)]
563pub struct CurrentItem;
564
565impl<T> ItemBinder<CurrentItem, T> {
566    pub fn under_current_binder(self) -> T {
567        self.val
568    }
569}
570
571impl Ty {
572    /// Return the unit type
573    pub fn mk_unit() -> Ty {
574        Self::mk_tuple(vec![])
575    }
576
577    pub fn mk_tuple(tys: Vec<Ty>) -> Ty {
578        TyKind::Adt(TypeDeclRef {
579            id: TypeId::Tuple,
580            generics: Box::new(GenericArgs::new_for_builtin(tys.into())),
581        })
582        .into_ty()
583    }
584
585    pub fn mk_slice(ty: Ty) -> Ty {
586        TyKind::Adt(TypeDeclRef {
587            id: TypeId::Builtin(BuiltinTy::Slice),
588            generics: Box::new(GenericArgs::new_for_builtin(vec![ty].into())),
589        })
590        .into_ty()
591    }
592    /// Return true if it is actually unit (i.e.: 0-tuple)
593    pub fn is_unit(&self) -> bool {
594        match self.as_tuple() {
595            Some(tys) => tys.is_empty(),
596            None => false,
597        }
598    }
599
600    /// Return true if this is a scalar type
601    pub fn is_scalar(&self) -> bool {
602        match self.kind() {
603            TyKind::Literal(kind) => kind.is_int() || kind.is_uint(),
604            _ => false,
605        }
606    }
607
608    pub fn is_unsigned_scalar(&self) -> bool {
609        matches!(self.kind(), TyKind::Literal(LiteralTy::UInt(_)))
610    }
611
612    pub fn is_signed_scalar(&self) -> bool {
613        matches!(self.kind(), TyKind::Literal(LiteralTy::Int(_)))
614    }
615
616    /// Return true if the type is Box
617    pub fn is_box(&self) -> bool {
618        match self.kind() {
619            TyKind::Adt(ty_ref) if let TypeId::Builtin(BuiltinTy::Box) = ty_ref.id => true,
620            _ => false,
621        }
622    }
623
624    pub fn as_box(&self) -> Option<&Ty> {
625        match self.kind() {
626            TyKind::Adt(ty_ref) if let TypeId::Builtin(BuiltinTy::Box) = ty_ref.id => {
627                Some(&ty_ref.generics.types[0])
628            }
629            _ => None,
630        }
631    }
632
633    pub fn as_array_or_slice(&self) -> Option<&Ty> {
634        match self.kind() {
635            TyKind::Adt(ty_ref)
636                if let TypeId::Builtin(BuiltinTy::Array | BuiltinTy::Slice) = ty_ref.id =>
637            {
638                Some(&ty_ref.generics.types[0])
639            }
640            _ => None,
641        }
642    }
643
644    pub fn as_tuple(&self) -> Option<&Vector<TypeVarId, Ty>> {
645        match self.kind() {
646            TyKind::Adt(ty_ref) if let TypeId::Tuple = ty_ref.id => Some(&ty_ref.generics.types),
647            _ => None,
648        }
649    }
650
651    pub fn as_adt(&self) -> Option<&TypeDeclRef> {
652        self.kind().as_adt()
653    }
654}
655
656impl TyKind {
657    pub fn into_ty(self) -> Ty {
658        Ty::new(self)
659    }
660}
661
662impl From<TyKind> for Ty {
663    fn from(kind: TyKind) -> Ty {
664        kind.into_ty()
665    }
666}
667
668/// Convenience for migration purposes.
669impl std::ops::Deref for Ty {
670    type Target = TyKind;
671
672    fn deref(&self) -> &Self::Target {
673        self.kind()
674    }
675}
676/// For deref patterns.
677unsafe impl std::ops::DerefPure for Ty {}
678
679impl TypeDeclRef {
680    pub fn new(id: TypeId, generics: GenericArgs) -> Self {
681        Self {
682            id,
683            generics: Box::new(generics),
684        }
685    }
686}
687
688impl TraitDeclRef {
689    pub fn self_ty<'a>(&'a self, krate: &'a TranslatedCrate) -> Option<&'a Ty> {
690        match self.generics.types.iter().next() {
691            Some(ty) => return Some(ty),
692            // TODO(mono): A monomorphized trait takes no arguments.
693            None => {
694                let name = krate.item_name(self.id)?;
695                let args = name.name.last()?.as_monomorphized()?;
696                args.types.iter().next()
697            }
698        }
699    }
700}
701
702impl TraitRef {
703    pub fn new_builtin(
704        trait_id: TraitDeclId,
705        ty: Ty,
706        parents: Vector<TraitClauseId, TraitRef>,
707    ) -> Self {
708        let trait_decl_ref = RegionBinder::empty(TraitDeclRef {
709            id: trait_id,
710            generics: Box::new(GenericArgs::new_types([ty].into())),
711        });
712        TraitRef {
713            kind: TraitRefKind::BuiltinOrAuto {
714                trait_decl_ref: trait_decl_ref.clone(),
715                parent_trait_refs: parents,
716                types: Default::default(),
717            },
718            trait_decl_ref,
719        }
720    }
721}
722
723impl Field {
724    /// The new name for this field, as suggested by the `#[charon::rename]` attribute.
725    pub fn renamed_name(&self) -> Option<&str> {
726        self.attr_info.rename.as_deref().or(self.name.as_deref())
727    }
728
729    /// Whether this field has a `#[charon::opaque]` annotation.
730    pub fn is_opaque(&self) -> bool {
731        self.attr_info
732            .attributes
733            .iter()
734            .any(|attr| attr.is_opaque())
735    }
736}
737
738impl Variant {
739    /// The new name for this variant, as suggested by the `#[charon::rename]` and
740    /// `#[charon::variants_prefix]` attributes.
741    pub fn renamed_name(&self) -> &str {
742        self.attr_info
743            .rename
744            .as_deref()
745            .unwrap_or(self.name.as_ref())
746    }
747
748    /// Whether this variant has a `#[charon::opaque]` annotation.
749    pub fn is_opaque(&self) -> bool {
750        self.attr_info
751            .attributes
752            .iter()
753            .any(|attr| attr.is_opaque())
754    }
755}
756
757impl RefKind {
758    pub fn mutable(x: bool) -> Self {
759        if x { Self::Mut } else { Self::Shared }
760    }
761}
762
763/// Visitor for type-level variables. Used to visit the variables contained in a value, as seen
764/// from the outside of the value. This means that any variable bound inside the value will be
765/// skipped, and all the seen De Bruijn indices will count from the outside of the value. The
766/// returned value, if any, will be put in place of the variable.
767pub trait VarsVisitor {
768    fn visit_region_var(&mut self, _v: RegionDbVar) -> Option<Region> {
769        None
770    }
771    fn visit_type_var(&mut self, _v: TypeDbVar) -> Option<Ty> {
772        None
773    }
774    fn visit_const_generic_var(&mut self, _v: ConstGenericDbVar) -> Option<ConstGeneric> {
775        None
776    }
777    fn visit_clause_var(&mut self, _v: ClauseDbVar) -> Option<TraitRefKind> {
778        None
779    }
780    fn visit_self_clause(&mut self) -> Option<TraitRefKind> {
781        None
782    }
783}
784
785/// Visitor for the [TyVisitable::substitute] function.
786/// This substitutes variables bound at the level where we start to substitute (level 0).
787#[derive(Visitor)]
788pub(crate) struct SubstVisitor<'a> {
789    generics: &'a GenericArgs,
790    self_ref: &'a TraitRefKind,
791}
792impl<'a> SubstVisitor<'a> {
793    pub(crate) fn new(generics: &'a GenericArgs, self_ref: &'a TraitRefKind) -> Self {
794        Self { generics, self_ref }
795    }
796
797    /// Returns the value for this variable, if any.
798    fn process_var<Id, T>(&self, var: DeBruijnVar<Id>, get: impl Fn(Id) -> &'a T) -> Option<T>
799    where
800        Id: Copy,
801        T: Clone + TyVisitable,
802        DeBruijnVar<Id>: Into<T>,
803    {
804        match var {
805            DeBruijnVar::Bound(dbid, varid) => {
806                Some(if let Some(dbid) = dbid.sub(DeBruijnId::one()) {
807                    // This is bound outside the binder we're substituting for.
808                    DeBruijnVar::Bound(dbid, varid).into()
809                } else {
810                    get(varid).clone()
811                })
812            }
813            DeBruijnVar::Free(..) => None,
814        }
815    }
816}
817impl VarsVisitor for SubstVisitor<'_> {
818    fn visit_region_var(&mut self, v: RegionDbVar) -> Option<Region> {
819        self.process_var(v, |id| &self.generics[id])
820    }
821    fn visit_type_var(&mut self, v: TypeDbVar) -> Option<Ty> {
822        self.process_var(v, |id| &self.generics[id])
823    }
824    fn visit_const_generic_var(&mut self, v: ConstGenericDbVar) -> Option<ConstGeneric> {
825        self.process_var(v, |id| &self.generics[id])
826    }
827    fn visit_clause_var(&mut self, v: ClauseDbVar) -> Option<TraitRefKind> {
828        self.process_var(v, |id| &self.generics[id].kind)
829    }
830    fn visit_self_clause(&mut self) -> Option<TraitRefKind> {
831        Some(self.self_ref.clone())
832    }
833}
834
835/// Types that are involved at the type-level and may be substituted around.
836pub trait TyVisitable: Sized + AstVisitable {
837    /// Visit the variables contained in `self`, as seen from the outside of `self`. This means
838    /// that any variable bound inside `self` will be skipped, and all the seen De Bruijn indices
839    /// will count from the outside of `self`.
840    fn visit_vars(&mut self, v: &mut impl VarsVisitor) {
841        #[derive(Visitor)]
842        struct Wrap<'v, V> {
843            v: &'v mut V,
844            depth: DeBruijnId,
845        }
846        impl<V: VarsVisitor> VisitAstMut for Wrap<'_, V> {
847            fn enter_region_binder<T: AstVisitable>(&mut self, _: &mut RegionBinder<T>) {
848                self.depth = self.depth.incr()
849            }
850            fn exit_region_binder<T: AstVisitable>(&mut self, _: &mut RegionBinder<T>) {
851                self.depth = self.depth.decr()
852            }
853            fn enter_binder<T: AstVisitable>(&mut self, _: &mut Binder<T>) {
854                self.depth = self.depth.incr()
855            }
856            fn exit_binder<T: AstVisitable>(&mut self, _: &mut Binder<T>) {
857                self.depth = self.depth.decr()
858            }
859
860            fn exit_region(&mut self, r: &mut Region) {
861                if let Region::Var(var) = r
862                    && let Some(var) = var.move_out_from_depth(self.depth)
863                    && let Some(new_r) = self.v.visit_region_var(var)
864                {
865                    *r = new_r.move_under_binders(self.depth);
866                }
867            }
868            fn exit_ty(&mut self, ty: &mut Ty) {
869                if let TyKind::TypeVar(var) = ty.kind()
870                    && let Some(var) = var.move_out_from_depth(self.depth)
871                    && let Some(new_ty) = self.v.visit_type_var(var)
872                {
873                    *ty = new_ty.move_under_binders(self.depth);
874                }
875            }
876            fn exit_const_generic(&mut self, cg: &mut ConstGeneric) {
877                if let ConstGeneric::Var(var) = cg
878                    && let Some(var) = var.move_out_from_depth(self.depth)
879                    && let Some(new_cg) = self.v.visit_const_generic_var(var)
880                {
881                    *cg = new_cg.move_under_binders(self.depth);
882                }
883            }
884            fn exit_constant_expr(&mut self, ce: &mut ConstantExpr) {
885                if let RawConstantExpr::Var(var) = &mut ce.value
886                    && let Some(var) = var.move_out_from_depth(self.depth)
887                    && let Some(new_cg) = self.v.visit_const_generic_var(var)
888                {
889                    ce.value = new_cg.move_under_binders(self.depth).into();
890                }
891            }
892            fn exit_trait_ref_kind(&mut self, kind: &mut TraitRefKind) {
893                match kind {
894                    TraitRefKind::SelfId => {
895                        if let Some(new_kind) = self.v.visit_self_clause() {
896                            *kind = new_kind.move_under_binders(self.depth);
897                        }
898                    }
899                    TraitRefKind::Clause(var) => {
900                        if let Some(var) = var.move_out_from_depth(self.depth)
901                            && let Some(new_kind) = self.v.visit_clause_var(var)
902                        {
903                            *kind = new_kind.move_under_binders(self.depth);
904                        }
905                    }
906                    _ => {}
907                }
908            }
909        }
910        let _ = self.drive_mut(&mut Wrap {
911            v,
912            depth: DeBruijnId::zero(),
913        });
914    }
915
916    fn substitute(self, generics: &GenericArgs) -> Self {
917        self.substitute_with_self(generics, &TraitRefKind::SelfId)
918    }
919
920    fn substitute_with_self(mut self, generics: &GenericArgs, self_ref: &TraitRefKind) -> Self {
921        let _ = self.visit_vars(&mut SubstVisitor::new(generics, self_ref));
922        self
923    }
924
925    /// Move under one binder.
926    fn move_under_binder(self) -> Self {
927        self.move_under_binders(DeBruijnId::one())
928    }
929
930    /// Move under `depth` binders.
931    fn move_under_binders(mut self, depth: DeBruijnId) -> Self {
932        if !depth.is_zero() {
933            let Continue(()) = self.visit_db_id::<Infallible>(|id| {
934                *id = id.plus(depth);
935                Continue(())
936            });
937        }
938        self
939    }
940
941    /// Move from under one binder.
942    fn move_from_under_binder(self) -> Option<Self> {
943        self.move_from_under_binders(DeBruijnId::one())
944    }
945
946    /// Move the value out of `depth` binders. Returns `None` if it contains a variable bound in
947    /// one of these `depth` binders.
948    fn move_from_under_binders(mut self, depth: DeBruijnId) -> Option<Self> {
949        self.visit_db_id::<()>(|id| match id.sub(depth) {
950            Some(sub) => {
951                *id = sub;
952                Continue(())
953            }
954            None => Break(()),
955        })
956        .is_continue()
957        .then_some(self)
958    }
959
960    /// Visit the de Bruijn ids contained in `self`, as seen from the outside of `self`. This means
961    /// that any variable bound inside `self` will be skipped, and all the seen indices will count
962    /// from the outside of self.
963    fn visit_db_id<B>(
964        &mut self,
965        f: impl FnMut(&mut DeBruijnId) -> ControlFlow<B>,
966    ) -> ControlFlow<B> {
967        struct Wrap<F> {
968            f: F,
969            depth: DeBruijnId,
970        }
971        impl<B, F> Visitor for Wrap<F>
972        where
973            F: FnMut(&mut DeBruijnId) -> ControlFlow<B>,
974        {
975            type Break = B;
976        }
977        impl<B, F> VisitAstMut for Wrap<F>
978        where
979            F: FnMut(&mut DeBruijnId) -> ControlFlow<B>,
980        {
981            fn enter_region_binder<T: AstVisitable>(&mut self, _: &mut RegionBinder<T>) {
982                self.depth = self.depth.incr()
983            }
984            fn exit_region_binder<T: AstVisitable>(&mut self, _: &mut RegionBinder<T>) {
985                self.depth = self.depth.decr()
986            }
987            fn enter_binder<T: AstVisitable>(&mut self, _: &mut Binder<T>) {
988                self.depth = self.depth.incr()
989            }
990            fn exit_binder<T: AstVisitable>(&mut self, _: &mut Binder<T>) {
991                self.depth = self.depth.decr()
992            }
993
994            fn visit_de_bruijn_id(&mut self, x: &mut DeBruijnId) -> ControlFlow<Self::Break> {
995                if let Some(mut shifted) = x.sub(self.depth) {
996                    (self.f)(&mut shifted)?;
997                    *x = shifted.plus(self.depth)
998                }
999                Continue(())
1000            }
1001        }
1002        self.drive_mut(&mut Wrap {
1003            f,
1004            depth: DeBruijnId::zero(),
1005        })
1006    }
1007}
1008
1009impl TypeDecl {
1010    /// Looks up the variant corresponding to the tag (i.e. the in-memory bytes that represent the discriminant).
1011    /// Returns `None` for types that don't have a relevant discriminant (e.g. uninhabited types).
1012    ///
1013    /// If the `tag` does not correspond to any valid discriminant but there is a niche,
1014    /// the resulting `VariantId` will be for the untagged variant [`TagEncoding::Niche::untagged_variant`].
1015    pub fn get_variant_from_tag(&self, tag: ScalarValue) -> Option<VariantId> {
1016        let layout = self.layout.as_ref()?;
1017        if layout.uninhabited {
1018            return None;
1019        };
1020        let discr_layout = layout.discriminant_layout.as_ref()?;
1021
1022        let variant_for_tag =
1023            layout
1024                .variant_layouts
1025                .iter_indexed()
1026                .find_map(|(id, variant_layout)| {
1027                    if variant_layout.tag == Some(tag) {
1028                        Some(id)
1029                    } else {
1030                        None
1031                    }
1032                });
1033
1034        match &discr_layout.encoding {
1035            TagEncoding::Direct => {
1036                assert_eq!(tag.get_integer_ty(), discr_layout.tag_ty);
1037                variant_for_tag
1038            }
1039            TagEncoding::Niche { untagged_variant } => variant_for_tag.or(Some(*untagged_variant)),
1040        }
1041    }
1042}
1043
1044impl Layout {
1045    pub fn is_variant_uninhabited(&self, variant_id: VariantId) -> bool {
1046        if let Some(v) = self.variant_layouts.get(variant_id) {
1047            v.uninhabited
1048        } else {
1049            false
1050        }
1051    }
1052}
1053
1054impl<T: AstVisitable> TyVisitable for T {}
1055
1056impl Eq for TraitClause {}
1057
1058mk_index_impls!(GenericArgs.regions[RegionId]: Region);
1059mk_index_impls!(GenericArgs.types[TypeVarId]: Ty);
1060mk_index_impls!(GenericArgs.const_generics[ConstGenericVarId]: ConstGeneric);
1061mk_index_impls!(GenericArgs.trait_refs[TraitClauseId]: TraitRef);
1062mk_index_impls!(GenericParams.regions[RegionId]: RegionVar);
1063mk_index_impls!(GenericParams.types[TypeVarId]: TypeVar);
1064mk_index_impls!(GenericParams.const_generics[ConstGenericVarId]: ConstGenericVar);
1065mk_index_impls!(GenericParams.trait_clauses[TraitClauseId]: TraitClause);
charon_lib/ast/types_utils.rs

charon_lib/ast/
types_utils.rs
