Skip to main content

charon_lib/ast/
type_level.rs

1use derive_generic_visitor::*;
2use itertools::Itertools;
3use serde_state::{DeserializeState, SerializeState};
4use std::{collections::HashSet, mem};
5
6use crate::ast::*;
7
8pub mod regions;
9pub mod substitute;
10pub mod trait_proofs;
11pub mod type_info;
12pub mod types;
13pub mod vars;
14
15pub use regions::*;
16pub use substitute::*;
17pub use trait_proofs::*;
18pub use type_info::*;
19pub use types::*;
20pub use vars::*;
21
22/// A set of generic arguments.
23#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
24#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
25pub struct GenericArgs {
26    pub regions: IndexVec<RegionId, Region>,
27    pub types: IndexVec<TypeVarId, Ty>,
28    pub const_generics: IndexVec<ConstGenericVarId, ConstantExpr>,
29    pub trait_refs: IndexVec<TraitClauseId, PolyTraitRef>,
30}
31
32/// Region arguments used to instantiate a [`RegionBinder`].
33#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
34#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
35pub struct RegionArgs {
36    pub regions: IndexVec<RegionId, Region>,
37}
38
39/// A quantified trait predicate, e.g. `for<'a> Type<'a>: Trait<'a, Args>`.
40pub type PolyTraitDeclRef = RegionBinder<TraitDeclRef>;
41
42/// The predicate that the left region outlives the right region, i.e. `'l: 'r`. The left one is
43/// longer, and also contains fewer loans.
44///
45/// This can also represent `T: 'r`, by using `Region::Lub` for the left region. The right region
46/// may not be `Region::Lub`.
47#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
48#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
49pub struct OutlivesPred(pub Region, pub Region);
50
51pub type PolyOutlivesPred = RegionBinder<OutlivesPred>;
52
53/// A constraint over a trait associated type.
54///
55/// Example:
56/// ```text
57/// T : Foo<S = String>
58///         ^^^^^^^^^^
59/// ```
60#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
61#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
62pub struct TraitTypeConstraint {
63    pub trait_ref: TraitRef,
64    pub type_id: AssocTypeId,
65    pub ty: Ty,
66}
67
68pub type BoxedArgs = Box<GenericArgs>;
69
70/// Generic parameters for a declaration, including predicates.
71#[derive(Default, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
72#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
73pub struct GenericParams {
74    #[serde_state(stateless)]
75    pub regions: IndexVec<RegionId, RegionParam>,
76    #[serde_state(stateless)]
77    pub types: IndexVec<TypeVarId, TypeParam>,
78    pub const_generics: IndexVec<ConstGenericVarId, ConstGenericParam>,
79    // TODO: rename to match [GenericArgs]?
80    pub trait_clauses: IndexVec<TraitClauseId, TraitParam>,
81    /// The first region in the pair outlives the second region
82    pub outlives: Vec<PolyOutlivesPred>,
83    /// Constraints over trait associated types
84    pub trait_type_constraints: IndexVec<TraitTypeConstraintId, RegionBinder<TraitTypeConstraint>>,
85}
86
87#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
88#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
89#[cfg_attr(feature = "charon_on_charon", charon::variants_prefix("BK"))]
90pub enum BinderKind {
91    /// The parameters of a generic associated type.
92    TraitType(TraitDeclId, AssocTypeId),
93    /// The parameters of a trait method. Used in the `methods` lists in trait decls and trait
94    /// impls.
95    TraitMethod(TraitDeclId, TraitMethodId),
96    /// The parameters bound in a non-trait `impl` block. Used in the `Name`s of inherent methods.
97    InherentImplBlock,
98    /// Binder used for `dyn Trait` existential predicates.
99    Dyn,
100    /// Some other use of a binder outside the main Charon ast.
101    Other,
102}
103
104/// A value of type `T` bound by generic parameters. Used in any context where we're adding generic
105/// parameters that aren't on the top-level item, e.g. `for<'a>` clauses (uses `RegionBinder` for
106/// now), trait methods, GATs (TODO).
107#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
108#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
109pub struct Binder<T> {
110    #[cfg_attr(feature = "charon_on_charon", charon::rename("binder_params"))]
111    pub params: GenericParams,
112    /// Named this way to highlight accesses to the inner value that might be handling parameters
113    /// incorrectly. Prefer using helper methods.
114    #[cfg_attr(feature = "charon_on_charon", charon::rename("binder_value"))]
115    pub skip_binder: T,
116    /// The kind of binder this is.
117    #[cfg_attr(feature = "charon_on_charon", charon::opaque)]
118    pub kind: BinderKind,
119}
120
121/// A value of type `T` bound by regions. We should use `binder` instead but this causes name clash
122/// issues in the derived ocaml visitors.
123#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
124#[derive(SerializeState, DeserializeState, Drive, DriveMut, DriveTwo)]
125#[serde_state(state_implements = DedupSerializerState)] // Avoid corecursive impls due to perfect derive
126pub struct RegionBinder<T> {
127    #[cfg_attr(feature = "charon_on_charon", charon::rename("binder_regions"))]
128    #[serde_state(stateless)]
129    pub regions: IndexVec<RegionId, RegionParam>,
130    /// Outlives relations involving the bound regions.
131    pub outlives: Vec<PolyOutlivesPred>,
132    /// Named this way to highlight accesses to the inner value that might be handling parameters
133    /// incorrectly. Prefer using helper methods.
134    #[cfg_attr(feature = "charon_on_charon", charon::rename("binder_value"))]
135    pub skip_binder: T,
136}
137
138impl GenericArgs {
139    pub fn len(&self) -> usize {
140        let GenericArgs {
141            regions,
142            types,
143            const_generics,
144            trait_refs,
145        } = self;
146        regions.len() + types.len() + const_generics.len() + trait_refs.len()
147    }
148
149    pub fn is_empty(&self) -> bool {
150        self.len() == 0
151    }
152    /// Whether this has any explicit arguments (types, regions or const generics).
153    pub fn has_explicits(&self) -> bool {
154        !self.regions.is_empty() || !self.types.is_empty() || !self.const_generics.is_empty()
155    }
156    /// Whether this has any explicit arguments other than regions (types or const generics).
157    pub fn has_non_lt_explicits(&self) -> bool {
158        !self.types.is_empty() || !self.const_generics.is_empty()
159    }
160    /// Whether this has any implicit arguments (trait refs).
161    pub fn has_implicits(&self) -> bool {
162        !self.trait_refs.is_empty()
163    }
164
165    pub fn empty() -> Self {
166        GenericArgs {
167            regions: Default::default(),
168            types: Default::default(),
169            const_generics: Default::default(),
170            trait_refs: Default::default(),
171        }
172    }
173
174    pub fn new(
175        regions: IndexVec<RegionId, Region>,
176        types: IndexVec<TypeVarId, Ty>,
177        const_generics: IndexVec<ConstGenericVarId, ConstantExpr>,
178        trait_refs: IndexVec<TraitClauseId, PolyTraitRef>,
179    ) -> Self {
180        Self {
181            regions,
182            types,
183            const_generics,
184            trait_refs,
185        }
186    }
187    pub fn new_types(types: IndexVec<TypeVarId, Ty>) -> Self {
188        Self {
189            types,
190            ..Self::empty()
191        }
192    }
193    pub fn new_lifetimes(regions: IndexVec<RegionId, Region>) -> Self {
194        Self {
195            regions,
196            ..Self::empty()
197        }
198    }
199
200    /// Check whether this matches the given `GenericParams`.
201    /// TODO: check more things, e.g. that the trait refs use the correct trait and generics.
202    pub fn matches(&self, params: &GenericParams) -> bool {
203        params.regions.len() == self.regions.len()
204            && params.types.len() == self.types.len()
205            && params.const_generics.len() == self.const_generics.len()
206            && params.trait_clauses.len() == self.trait_refs.len()
207    }
208
209    /// Return the same generics, but where we pop the first type arguments.
210    /// This is useful for trait references (for pretty printing for instance),
211    /// because the first type argument is the type for which the trait is
212    /// implemented.
213    pub fn pop_first_type_arg(&self) -> (Ty, Self) {
214        let mut generics = self.clone();
215        let mut it = mem::take(&mut generics.types).into_iter();
216        let ty = it.next().unwrap();
217        generics.types = it.collect();
218        (ty, generics)
219    }
220
221    /// Concatenate this set of arguments with another one. Use with care, you must manage the
222    /// order of arguments correctly.
223    pub fn concat(mut self, other: &Self) -> Self {
224        let Self {
225            regions,
226            types,
227            const_generics,
228            trait_refs,
229        } = other;
230        self.regions.clone_extend_from_other(regions);
231        self.types.clone_extend_from_other(types);
232        self.const_generics.clone_extend_from_other(const_generics);
233        self.trait_refs.clone_extend_from_other(trait_refs);
234        self
235    }
236}
237
238impl RegionArgs {
239    pub fn empty() -> Self {
240        Self {
241            regions: Default::default(),
242        }
243    }
244
245    pub fn erased(len: usize) -> Self {
246        Self::new(std::iter::repeat_n(Region::Erased, len).collect())
247    }
248
249    pub fn new(regions: IndexVec<RegionId, Region>) -> Self {
250        Self { regions }
251    }
252
253    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &Region> + ExactSizeIterator {
254        self.regions.iter()
255    }
256
257    pub fn is_empty(&self) -> bool {
258        self.regions.is_empty()
259    }
260}
261
262impl OutlivesPred {
263    /// Normalize an outlives bound if it can be (e.g. `&'a T: 'b` becomes `'a: 'b` and `T: 'b`).
264    pub fn normalize(&self) -> impl Iterator<Item = Self> + use<'_> {
265        let Self(longer, shorter) = self;
266        let longers: SeqHashSet<_> = if let Region::Lub(ty) = longer
267            && !matches!(ty.kind(), TyKind::TypeVar(_) | TyKind::TraitType(..))
268        {
269            // Collect the regions and param types visible from the outside of this type.
270            #[derive(Visitor, Default)]
271            struct RequireTypeOutlives {
272                regions: SeqHashSet<Region>,
273                binder_depth: DeBruijnId,
274            }
275
276            impl VisitorWithBinderDepth for RequireTypeOutlives {
277                fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
278                    &mut self.binder_depth
279                }
280            }
281
282            impl VisitAst for RequireTypeOutlives {
283                fn visit<U: AstVisitable>(&mut self, value: &U) -> ControlFlow<Self::Break> {
284                    VisitWithBinderDepth::new(self).visit(value)
285                }
286
287                fn enter_region(&mut self, region: &Region) {
288                    if let Some(region) = region.clone().move_from_under_binders(self.binder_depth)
289                    {
290                        self.regions.insert(region);
291                    }
292                }
293
294                fn visit_ty(&mut self, ty: &Ty) -> ControlFlow<Self::Break> {
295                    if matches!(ty.kind(), TyKind::TypeVar(_) | TyKind::TraitType(..)) {
296                        self.enter_region(&Region::Lub(ty.clone()));
297                        // `T::Assoc: 'a` does not imply `T: 'a`.
298                        return ControlFlow::Continue(());
299                    }
300                    self.visit_inner(ty)
301                }
302            }
303
304            RequireTypeOutlives::default()
305                .visit_by_val_infallible(ty)
306                .regions
307        } else {
308            [longer.clone()].into()
309        };
310        longers
311            .into_iter()
312            .map(move |longer| OutlivesPred(longer, shorter.clone()))
313    }
314}
315
316impl GenericParams {
317    pub fn empty() -> Self {
318        Self::default()
319    }
320
321    pub fn is_empty(&self) -> bool {
322        self.len() == 0
323    }
324    /// Whether this has any explicit arguments (types, regions or const generics).
325    pub fn has_explicits(&self) -> bool {
326        !self.regions.is_empty() || !self.types.is_empty() || !self.const_generics.is_empty()
327    }
328    /// Whether this has any implicit arguments (trait clauses, outlives relations, associated type
329    /// equality constraints).
330    pub fn has_predicates(&self) -> bool {
331        !self.trait_clauses.is_empty()
332            || !self.outlives.is_empty()
333            || !self.trait_type_constraints.is_empty()
334    }
335
336    /// Run some sanity checks.
337    pub fn check_consistency(&self) {
338        // Sanity check: check the clause ids are consistent.
339        assert!(
340            self.trait_clauses
341                .iter()
342                .enumerate()
343                .all(|(i, c)| c.clause_id.index() == i)
344        );
345
346        // Sanity check: region names are pairwise distinct (this caused trouble when generating
347        // names for the backward functions in Aeneas): at some point, Rustc introduced names equal
348        // to `Some("'_")` for the anonymous regions, instead of using `None` (we now check in
349        // [translate_region_name] and ignore names equal to "'_").
350        let mut s = HashSet::new();
351        for r in &self.regions {
352            if let Some(name) = &r.name {
353                assert!(
354                    !s.contains(name),
355                    "Name \"{}\" reused for two different lifetimes",
356                    name
357                );
358                s.insert(name);
359            }
360        }
361    }
362
363    pub fn len(&self) -> usize {
364        let GenericParams {
365            regions,
366            types,
367            const_generics,
368            trait_clauses,
369            outlives,
370            trait_type_constraints,
371        } = self;
372        regions.len()
373            + types.len()
374            + const_generics.len()
375            + trait_clauses.len()
376            + outlives.len()
377            + trait_type_constraints.len()
378    }
379
380    /// Construct a set of generic arguments in the scope of `self` that matches `self` and feeds
381    /// each required parameter with itself. E.g. given parameters for `<T, U> where U:
382    /// PartialEq<T>`, the arguments would be `<T, U>[TraitClause0]`.
383    pub fn identity_args(&self) -> GenericArgs {
384        self.identity_args_at_depth(DeBruijnId::zero())
385    }
386
387    /// Like `identity_args` but uses variables bound at the given depth.
388    pub fn identity_args_at_depth(&self, depth: DeBruijnId) -> GenericArgs {
389        GenericArgs {
390            regions: self
391                .regions
392                .map_ref_indexed(|id, _| Region::Var(DeBruijnVar::bound(depth, id))),
393            types: self
394                .types
395                .map_ref_indexed(|id, _| TyKind::TypeVar(DeBruijnVar::bound(depth, id)).into_ty()),
396            const_generics: self.const_generics.map_ref_indexed(|id, c| {
397                ConstantExpr::new(
398                    ConstantExprKind::Var(DeBruijnVar::bound(depth, id)),
399                    c.ty.clone(),
400                )
401            }),
402            trait_refs: self
403                .trait_clauses
404                .map_ref(|clause| clause.identity_tref_at_depth(depth)),
405        }
406    }
407
408    /// Take the predicates from the another `GenericParams`. This assumes the clause ids etc are
409    /// already consistent.
410    pub fn take_predicates_from(&mut self, other: GenericParams) {
411        assert!(!other.has_explicits());
412        let num_clauses = self.trait_clauses.len();
413        let GenericParams {
414            regions: _,
415            types: _,
416            const_generics: _,
417            trait_clauses,
418            outlives,
419            trait_type_constraints,
420        } = other;
421        self.trait_clauses
422            .extend(trait_clauses.into_iter().update(|clause| {
423                clause.clause_id += num_clauses;
424            }));
425        self.outlives.extend(outlives);
426        self.trait_type_constraints.extend(trait_type_constraints);
427    }
428
429    /// Take the predicates from the another `GenericParams`. This assumes that the two
430    /// `GenericParams` are independent, hence will shift clause ids if `other` has any
431    /// trait refs that reference its own clauses.
432    pub fn merge_predicates_from(&mut self, mut other: GenericParams) {
433        // Drop the explicits params.
434        other.types.clear();
435        other.regions.clear();
436        other.const_generics.clear();
437        // The contents of `other` may refer to its own trait clauses, so we must shift clause ids.
438        struct ShiftClausesVisitor(usize);
439        impl VarsVisitor for ShiftClausesVisitor {
440            fn visit_clause_var(&mut self, v: ClauseDbVar) -> Option<ClauseReplacement> {
441                if let DeBruijnVar::Bound(DeBruijnId::ZERO, clause_id) = v {
442                    // Replace clause 0 and decrement the others.
443                    Some(ClauseReplacement::Var(DeBruijnVar::Bound(
444                        DeBruijnId::ZERO,
445                        clause_id + self.0,
446                    )))
447                } else {
448                    None
449                }
450            }
451        }
452        let num_clauses = self.trait_clauses.len();
453        other.visit_vars(&mut ShiftClausesVisitor(num_clauses));
454        self.take_predicates_from(other);
455    }
456}
457
458impl<T> Binder<T> {
459    /// Wrap the value in an empty binder, shifting variables appropriately.
460    pub fn empty(kind: BinderKind, x: T) -> Self
461    where
462        T: TyVisitable,
463    {
464        Binder {
465            params: Default::default(),
466            skip_binder: x.move_under_binder(),
467            kind,
468        }
469    }
470    pub fn new(kind: BinderKind, params: GenericParams, skip_binder: T) -> Self {
471        Self {
472            params,
473            skip_binder,
474            kind,
475        }
476    }
477
478    /// Whether this binder binds any variables.
479    pub fn binds_anything(&self) -> bool {
480        !self.params.is_empty()
481    }
482
483    /// Retreive the contents of this binder if the binder binds no variables. This is the invers
484    /// of `Binder::empty`.
485    pub fn get_if_binds_nothing(&self) -> Option<T>
486    where
487        T: TyVisitable + Clone,
488    {
489        self.params
490            .is_empty()
491            .then(|| self.skip_binder.clone().move_from_under_binder().unwrap())
492    }
493
494    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Binder<U> {
495        Binder {
496            params: self.params,
497            skip_binder: f(self.skip_binder),
498            kind: self.kind,
499        }
500    }
501
502    pub fn map_ref<U>(&self, f: impl FnOnce(&T) -> U) -> Binder<U> {
503        Binder {
504            params: self.params.clone(),
505            skip_binder: f(&self.skip_binder),
506            kind: self.kind.clone(),
507        }
508    }
509
510    /// Substitute the provided arguments for the variables bound in this binder and return the
511    /// substituted inner value.
512    pub fn apply(self, args: &GenericArgs) -> T
513    where
514        T: TyVisitable,
515    {
516        self.skip_binder.substitute(args)
517    }
518
519    /// Like `apply`, but also keep the parameters: predicates mention them and therefore need to
520    /// be substituted before use too.
521    pub fn apply_keep_params(self, args: &GenericArgs) -> (GenericParams, T)
522    where
523        T: TyVisitable,
524    {
525        (
526            self.params.substitute(args),
527            self.skip_binder.substitute(args),
528        )
529    }
530}
531
532impl<T: AstVisitable> Binder<Binder<T>> {
533    /// Flatten two levels of binders into a single one.
534    pub fn flatten(self) -> Binder<T> {
535        #[derive(Visitor)]
536        struct FlattenVisitor<'a> {
537            shift_by: &'a GenericParams,
538            binder_depth: DeBruijnId,
539        }
540        impl VisitorWithBinderDepth for FlattenVisitor<'_> {
541            fn binder_depth_mut(&mut self) -> &mut DeBruijnId {
542                &mut self.binder_depth
543            }
544        }
545        impl VisitAstMut for FlattenVisitor<'_> {
546            fn visit<T: AstVisitable>(&mut self, x: &mut T) -> ControlFlow<Self::Break> {
547                VisitWithBinderDepth::new(self).visit(x)
548            }
549
550            fn enter_de_bruijn_id(&mut self, db_id: &mut DeBruijnId) {
551                if *db_id > self.binder_depth {
552                    // We started visiting at the inner binder, so in this branch we're either
553                    // mentioning the outer binder or a binder further beyond. Either way we
554                    // decrease the depth; variables that point to the outer binder don't have to
555                    // be shifted.
556                    *db_id = db_id.decr();
557                }
558            }
559            fn enter_region(&mut self, x: &mut Region) {
560                if let Region::Var(var) = x
561                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
562                {
563                    *id += self.shift_by.regions.len();
564                }
565            }
566            fn enter_ty_kind(&mut self, x: &mut TyKind) {
567                if let TyKind::TypeVar(var) = x
568                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
569                {
570                    *id += self.shift_by.types.len();
571                }
572            }
573            fn enter_constant_expr_kind(&mut self, kind: &mut ConstantExprKind) {
574                if let ConstantExprKind::Var(var) = kind
575                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
576                {
577                    *id += self.shift_by.const_generics.len();
578                }
579            }
580            fn enter_trait_ref_kind(&mut self, x: &mut TraitRefKind) {
581                if let TraitRefKind::Clause(var, _) = x
582                    && let Some(id) = var.bound_at_depth_mut(self.binder_depth)
583                {
584                    *id += self.shift_by.trait_clauses.len();
585                }
586            }
587        }
588
589        // We will concatenate both sets of params.
590        let mut outer_params = self.params;
591
592        // The inner value needs to change:
593        // - at binder level 0 we shift all variable ids to match the concatenated params;
594        // - at binder level > 0 we decrease binding level because there's one fewer binder.
595        let mut bound_value = self.skip_binder.skip_binder;
596        let _ = bound_value.drive_mut(&mut FlattenVisitor {
597            shift_by: &outer_params,
598            binder_depth: Default::default(),
599        });
600
601        // The inner params must also be updated, as they can refer to themselves and the outer
602        // one.
603        let mut inner_params = self.skip_binder.params;
604        let _ = inner_params.drive_mut(&mut FlattenVisitor {
605            shift_by: &outer_params,
606            binder_depth: Default::default(),
607        });
608        inner_params
609            .regions
610            .iter_mut()
611            .for_each(|v| v.index += outer_params.regions.len());
612        inner_params
613            .types
614            .iter_mut()
615            .for_each(|v| v.index += outer_params.types.len());
616        inner_params
617            .const_generics
618            .iter_mut()
619            .for_each(|v| v.index += outer_params.const_generics.len());
620        inner_params
621            .trait_clauses
622            .iter_mut()
623            .for_each(|v| v.clause_id += outer_params.trait_clauses.len());
624
625        let GenericParams {
626            regions,
627            types,
628            const_generics,
629            trait_clauses,
630            outlives,
631            trait_type_constraints,
632        } = &inner_params;
633        outer_params.regions.clone_extend_from_other(regions);
634        outer_params.types.clone_extend_from_other(types);
635        outer_params
636            .const_generics
637            .clone_extend_from_other(const_generics);
638        outer_params
639            .trait_clauses
640            .clone_extend_from_other(trait_clauses);
641        outer_params.outlives.extend_from_slice(outlives);
642        outer_params
643            .trait_type_constraints
644            .clone_extend_from_other(trait_type_constraints);
645
646        Binder {
647            params: outer_params,
648            skip_binder: bound_value,
649            kind: BinderKind::Other,
650        }
651    }
652}
653
654impl<T> RegionBinder<T> {
655    /// Wrap the value in an empty region binder, shifting variables appropriately.
656    pub fn empty(x: T) -> Self
657    where
658        T: TyVisitable,
659    {
660        RegionBinder {
661            regions: Default::default(),
662            outlives: Default::default(),
663            skip_binder: x.move_under_binder(),
664        }
665    }
666
667    /// The parameters and predicates introduced by this binder.
668    pub fn to_params(&self) -> GenericParams {
669        GenericParams {
670            regions: self.regions.clone(),
671            outlives: self.outlives.clone(),
672            ..GenericParams::default()
673        }
674    }
675
676    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> RegionBinder<U> {
677        RegionBinder {
678            regions: self.regions,
679            outlives: self.outlives,
680            skip_binder: f(self.skip_binder),
681        }
682    }
683
684    pub fn map_ref<U>(&self, f: impl FnOnce(&T) -> U) -> RegionBinder<U> {
685        RegionBinder {
686            regions: self.regions.clone(),
687            outlives: self.outlives.clone(),
688            skip_binder: f(&self.skip_binder),
689        }
690    }
691
692    pub fn map_ref_opt<U>(&self, f: impl FnOnce(&T) -> Option<U>) -> Option<RegionBinder<U>> {
693        Some(RegionBinder {
694            regions: self.regions.clone(),
695            outlives: self.outlives.clone(),
696            skip_binder: f(&self.skip_binder)?,
697        })
698    }
699
700    /// Substitute the bound variables with the given lifetimes.
701    pub fn apply(self, args: RegionArgs) -> T
702    where
703        T: TyVisitable,
704    {
705        assert_eq!(args.regions.len(), self.regions.len());
706        let args = GenericArgs::new_lifetimes(args.regions);
707        self.skip_binder.substitute_inner_binder(&args)
708    }
709
710    /// Like `apply`, but also keep the predicates: they mention the bound regions and therefore
711    /// need to be substituted before use too.
712    pub fn apply_keep_params(self, args: RegionArgs) -> (T, Vec<PolyOutlivesPred>)
713    where
714        T: TyVisitable,
715    {
716        assert_eq!(args.regions.len(), self.regions.len());
717        let args = GenericArgs::new_lifetimes(args.regions);
718        (
719            self.skip_binder.substitute_inner_binder(&args),
720            self.outlives.substitute_inner_binder(&args),
721        )
722    }
723
724    /// Extract the contents when we now the binder binds nothing.
725    #[track_caller]
726    pub fn no_bound_vars(self) -> T
727    where
728        T: TyVisitable,
729    {
730        assert!(self.regions.is_empty());
731        self.skip_binder.move_from_under_binder().unwrap()
732    }
733
734    /// Substitute the bound variables with erased lifetimes.
735    pub fn erase(self) -> T
736    where
737        T: TyVisitable,
738    {
739        let args = RegionArgs::erased(self.regions.len());
740        self.apply(args)
741    }
742
743    /// Infer how the bound regions of `self` appear in `target`. The returned binder binds the
744    /// same regions as `target`; other lifetimes may differ.
745    pub fn infer_region_mapping(&self, target: &Self) -> Option<RegionBinder<RegionArgs>>
746    where
747        T: TyVisitable,
748    {
749        struct RegionMapping {
750            regions: IndexVec<RegionId, Option<Region>>,
751            depth: DeBruijnId,
752        }
753
754        impl Visitor for RegionMapping {
755            type Break = ();
756        }
757
758        impl ZipAst for RegionMapping {
759            fn visit_region_param(
760                &mut self,
761                _source: &RegionParam,
762                _target: &RegionParam,
763            ) -> ControlFlow<()> {
764                // Binder positions identify regions; names and metadata need not match.
765                ControlFlow::Continue(())
766            }
767
768            fn visit_region(&mut self, source: &Region, target: &Region) -> ControlFlow<()> {
769                if let (Region::Lub(source), Region::Lub(target)) = (source, target) {
770                    return self.visit(source, target);
771                }
772                // We're only concerned with mapping bound variables.
773                if let Region::Var(var @ DeBruijnVar::Bound(depth, _)) = source
774                    && *depth <= self.depth
775                {
776                    if let Some(id) = var.bound_at_depth(self.depth) {
777                        let Some(target) = target.clone().move_from_under_binders(self.depth)
778                        else {
779                            return ControlFlow::Break(());
780                        };
781                        let mapped = &mut self.regions[id];
782                        if let Some(previous) = mapped
783                            && *previous != target
784                        {
785                            return ControlFlow::Break(());
786                        }
787                        *mapped = Some(target);
788                        ControlFlow::Continue(())
789                    } else if source != target {
790                        ControlFlow::Break(())
791                    } else {
792                        ControlFlow::Continue(())
793                    }
794                } else {
795                    ControlFlow::Continue(())
796                }
797            }
798
799            fn visit_region_binder<T: AstVisitable>(
800                &mut self,
801                source: &RegionBinder<T>,
802                target: &RegionBinder<T>,
803            ) -> ControlFlow<()> {
804                self.depth = self.depth.incr();
805                let result = self.visit_inner(source, target);
806                self.depth = self.depth.decr();
807                result
808            }
809        }
810
811        let mut mapping = RegionMapping {
812            regions: self.regions.map_ref_indexed(|_, _| None),
813            depth: DeBruijnId::zero(),
814        };
815        if ZipAst::visit(&mut mapping, &self.skip_binder, &target.skip_binder).is_break() {
816            return None;
817        }
818        let regions = RegionArgs::new(mapping.regions.into_iter().collect::<Option<_>>()?);
819        Some(RegionBinder {
820            regions: target.regions.clone(),
821            outlives: target.outlives.clone(),
822            skip_binder: regions,
823        })
824    }
825}
826
827impl<Id: TypeLevelVar> std::ops::Index<Id> for GenericArgs {
828    type Output = Id::Arg;
829    fn index(&self, index: Id) -> &Self::Output {
830        &Id::get_arg_vec(self)[index]
831    }
832}
833impl<Id: TypeLevelVar> std::ops::IndexMut<Id> for GenericArgs {
834    fn index_mut(&mut self, index: Id) -> &mut Self::Output {
835        &mut Id::get_arg_vec_mut(self)[index]
836    }
837}
838impl<Id: TypeLevelVar> std::ops::Index<Id> for GenericParams {
839    type Output = Id::Param;
840    fn index(&self, index: Id) -> &Self::Output {
841        &Id::get_param_vec(self)[index]
842    }
843}
844impl<Id: TypeLevelVar> std::ops::IndexMut<Id> for GenericParams {
845    fn index_mut(&mut self, index: Id) -> &mut Self::Output {
846        &mut Id::get_param_vec_mut(self)[index]
847    }
848}
849
850impl FromIterator<Region> for RegionArgs {
851    fn from_iter<T: IntoIterator<Item = Region>>(iter: T) -> Self {
852        Self::new(iter.into_iter().collect())
853    }
854}