rustc_infer/infer/region_constraints/
mod.rs

1//! See `README.md`.
2
3use std::ops::Range;
4use std::{cmp, fmt, mem};
5
6use rustc_data_structures::fx::FxHashMap;
7use rustc_data_structures::undo_log::UndoLogs;
8use rustc_data_structures::unify as ut;
9use rustc_index::IndexVec;
10use rustc_macros::{TypeFoldable, TypeVisitable};
11use rustc_middle::ty::{self, ReBound, ReStatic, ReVar, Region, RegionVid, Ty, TyCtxt};
12use rustc_middle::{bug, span_bug};
13use tracing::{debug, instrument};
14
15use self::CombineMapType::*;
16use self::UndoLog::*;
17use super::{RegionVariableOrigin, Rollback, SubregionOrigin};
18use crate::infer::snapshot::undo_log::{InferCtxtUndoLogs, Snapshot};
19use crate::infer::unify_key::{RegionVariableValue, RegionVidKey};
20
21mod leak_check;
22
23#[derive(Clone, Default)]
24pub struct RegionConstraintStorage<'tcx> {
25    /// For each `RegionVid`, the corresponding `RegionVariableOrigin`.
26    pub(super) var_infos: IndexVec<RegionVid, RegionVariableInfo>,
27
28    pub(super) data: RegionConstraintData<'tcx>,
29
30    /// For a given pair of regions (R1, R2), maps to a region R3 that
31    /// is designated as their LUB (edges R1 <= R3 and R2 <= R3
32    /// exist). This prevents us from making many such regions.
33    lubs: CombineMap<'tcx>,
34
35    /// For a given pair of regions (R1, R2), maps to a region R3 that
36    /// is designated as their GLB (edges R3 <= R1 and R3 <= R2
37    /// exist). This prevents us from making many such regions.
38    glbs: CombineMap<'tcx>,
39
40    /// When we add a R1 == R2 constraint, we currently add (a) edges
41    /// R1 <= R2 and R2 <= R1 and (b) we unify the two regions in this
42    /// table. You can then call `opportunistic_resolve_var` early
43    /// which will map R1 and R2 to some common region (i.e., either
44    /// R1 or R2). This is important when fulfillment, dropck and other such
45    /// code is iterating to a fixed point, because otherwise we sometimes
46    /// would wind up with a fresh stream of region variables that have been
47    /// equated but appear distinct.
48    pub(super) unification_table: ut::UnificationTableStorage<RegionVidKey<'tcx>>,
49
50    /// a flag set to true when we perform any unifications; this is used
51    /// to micro-optimize `take_and_reset_data`
52    any_unifications: bool,
53}
54
55pub struct RegionConstraintCollector<'a, 'tcx> {
56    storage: &'a mut RegionConstraintStorage<'tcx>,
57    undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
58}
59
60pub type VarInfos = IndexVec<RegionVid, RegionVariableInfo>;
61
62/// The full set of region constraints gathered up by the collector.
63/// Describes constraints between the region variables and other
64/// regions, as well as other conditions that must be verified, or
65/// assumptions that can be made.
66#[derive(Debug, Default, Clone)]
67pub struct RegionConstraintData<'tcx> {
68    /// Constraints of the form `A <= B`, where either `A` or `B` can
69    /// be a region variable (or neither, as it happens).
70    pub constraints: Vec<(Constraint<'tcx>, SubregionOrigin<'tcx>)>,
71
72    /// A "verify" is something that we need to verify after inference
73    /// is done, but which does not directly affect inference in any
74    /// way.
75    ///
76    /// An example is a `A <= B` where neither `A` nor `B` are
77    /// inference variables.
78    pub verifys: Vec<Verify<'tcx>>,
79}
80
81/// Represents a constraint that influences the inference process.
82#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
83pub enum ConstraintKind {
84    /// A region variable is a subregion of another.
85    VarSubVar,
86
87    /// A concrete region is a subregion of region variable.
88    RegSubVar,
89
90    /// A region variable is a subregion of a concrete region. This does not
91    /// directly affect inference, but instead is checked after
92    /// inference is complete.
93    VarSubReg,
94
95    /// A constraint where neither side is a variable. This does not
96    /// directly affect inference, but instead is checked after
97    /// inference is complete.
98    RegSubReg,
99}
100
101/// Represents a constraint that influences the inference process.
102#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
103pub struct Constraint<'tcx> {
104    pub kind: ConstraintKind,
105    // If `kind` is `VarSubVar` or `VarSubReg`, this must be a `ReVar`.
106    pub sub: Region<'tcx>,
107    // If `kind` is `VarSubVar` or `RegSubVar`, this must be a `ReVar`.
108    pub sup: Region<'tcx>,
109}
110
111impl Constraint<'_> {
112    pub fn involves_placeholders(&self) -> bool {
113        self.sub.is_placeholder() || self.sup.is_placeholder()
114    }
115}
116
117#[derive(Debug, Clone)]
118pub struct Verify<'tcx> {
119    pub kind: GenericKind<'tcx>,
120    pub origin: SubregionOrigin<'tcx>,
121    pub region: Region<'tcx>,
122    pub bound: VerifyBound<'tcx>,
123}
124
125#[derive(Copy, Clone, PartialEq, Eq, Hash, TypeFoldable, TypeVisitable)]
126pub enum GenericKind<'tcx> {
127    Param(ty::ParamTy),
128    Placeholder(ty::PlaceholderType),
129    Alias(ty::AliasTy<'tcx>),
130}
131
132/// Describes the things that some `GenericKind` value `G` is known to
133/// outlive. Each variant of `VerifyBound` can be thought of as a
134/// function:
135/// ```ignore (pseudo-rust)
136/// fn(min: Region) -> bool { .. }
137/// ```
138/// where `true` means that the region `min` meets that `G: min`.
139/// (False means nothing.)
140///
141/// So, for example, if we have the type `T` and we have in scope that
142/// `T: 'a` and `T: 'b`, then the verify bound might be:
143/// ```ignore (pseudo-rust)
144/// fn(min: Region) -> bool {
145///    ('a: min) || ('b: min)
146/// }
147/// ```
148/// This is described with an `AnyRegion('a, 'b)` node.
149#[derive(Debug, Clone, TypeFoldable, TypeVisitable)]
150pub enum VerifyBound<'tcx> {
151    /// See [`VerifyIfEq`] docs
152    IfEq(ty::Binder<'tcx, VerifyIfEq<'tcx>>),
153
154    /// Given a region `R`, expands to the function:
155    ///
156    /// ```ignore (pseudo-rust)
157    /// fn(min) -> bool {
158    ///     R: min
159    /// }
160    /// ```
161    ///
162    /// This is used when we can establish that `G: R` -- therefore,
163    /// if `R: min`, then by transitivity `G: min`.
164    OutlivedBy(Region<'tcx>),
165
166    /// Given a region `R`, true if it is `'empty`.
167    IsEmpty,
168
169    /// Given a set of bounds `B`, expands to the function:
170    ///
171    /// ```ignore (pseudo-rust)
172    /// fn(min) -> bool {
173    ///     exists (b in B) { b(min) }
174    /// }
175    /// ```
176    ///
177    /// In other words, if we meet some bound in `B`, that suffices.
178    /// This is used when all the bounds in `B` are known to apply to `G`.
179    AnyBound(Vec<VerifyBound<'tcx>>),
180
181    /// Given a set of bounds `B`, expands to the function:
182    ///
183    /// ```ignore (pseudo-rust)
184    /// fn(min) -> bool {
185    ///     forall (b in B) { b(min) }
186    /// }
187    /// ```
188    ///
189    /// In other words, if we meet *all* bounds in `B`, that suffices.
190    /// This is used when *some* bound in `B` is known to suffice, but
191    /// we don't know which.
192    AllBounds(Vec<VerifyBound<'tcx>>),
193}
194
195/// This is a "conditional bound" that checks the result of inference
196/// and supplies a bound if it ended up being relevant. It's used in situations
197/// like this:
198///
199/// ```rust,ignore (pseudo-Rust)
200/// fn foo<'a, 'b, T: SomeTrait<'a>>
201/// where
202///    <T as SomeTrait<'a>>::Item: 'b
203/// ```
204///
205/// If we have an obligation like `<T as SomeTrait<'?x>>::Item: 'c`, then
206/// we don't know yet whether it suffices to show that `'b: 'c`. If `'?x` winds
207/// up being equal to `'a`, then the where-clauses on function applies, and
208/// in that case we can show `'b: 'c`. But if `'?x` winds up being something
209/// else, the bound isn't relevant.
210///
211/// In the [`VerifyBound`], this struct is enclosed in `Binder` to account
212/// for cases like
213///
214/// ```rust,ignore (pseudo-Rust)
215/// where for<'a> <T as SomeTrait<'a>::Item: 'a
216/// ```
217///
218/// The idea is that we have to find some instantiation of `'a` that can
219/// make `<T as SomeTrait<'a>>::Item` equal to the final value of `G`,
220/// the generic we are checking.
221///
222/// ```ignore (pseudo-rust)
223/// fn(min) -> bool {
224///     exists<'a> {
225///         if G == K {
226///             B(min)
227///         } else {
228///             false
229///         }
230///     }
231/// }
232/// ```
233#[derive(Debug, Copy, Clone, TypeFoldable, TypeVisitable)]
234pub struct VerifyIfEq<'tcx> {
235    /// Type which must match the generic `G`
236    pub ty: Ty<'tcx>,
237
238    /// Bound that applies if `ty` is equal.
239    pub bound: Region<'tcx>,
240}
241
242#[derive(Copy, Clone, PartialEq, Eq, Hash)]
243pub(crate) struct TwoRegions<'tcx> {
244    a: Region<'tcx>,
245    b: Region<'tcx>,
246}
247
248#[derive(Copy, Clone, PartialEq)]
249pub(crate) enum UndoLog<'tcx> {
250    /// We added `RegionVid`.
251    AddVar(RegionVid),
252
253    /// We added the given `constraint`.
254    AddConstraint(usize),
255
256    /// We added the given `verify`.
257    AddVerify(usize),
258
259    /// We added a GLB/LUB "combination variable".
260    AddCombination(CombineMapType, TwoRegions<'tcx>),
261}
262
263#[derive(Copy, Clone, PartialEq)]
264pub(crate) enum CombineMapType {
265    Lub,
266    Glb,
267}
268
269type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>;
270
271#[derive(Debug, Clone, Copy)]
272pub struct RegionVariableInfo {
273    pub origin: RegionVariableOrigin,
274    // FIXME: This is only necessary for `fn take_and_reset_data` and
275    // `lexical_region_resolve`. We should rework `lexical_region_resolve`
276    // in the near/medium future anyways and could move the unverse info
277    // for `fn take_and_reset_data` into a separate table which is
278    // only populated when needed.
279    //
280    // For both of these cases it is fine that this can diverge from the
281    // actual universe of the variable, which is directly stored in the
282    // unification table for unknown region variables. At some point we could
283    // stop emitting bidirectional outlives constraints if equate succeeds.
284    // This would be currently unsound as it would cause us to drop the universe
285    // changes in `lexical_region_resolve`.
286    pub universe: ty::UniverseIndex,
287}
288
289pub(crate) struct RegionSnapshot {
290    any_unifications: bool,
291}
292
293impl<'tcx> RegionConstraintStorage<'tcx> {
294    #[inline]
295    pub(crate) fn with_log<'a>(
296        &'a mut self,
297        undo_log: &'a mut InferCtxtUndoLogs<'tcx>,
298    ) -> RegionConstraintCollector<'a, 'tcx> {
299        RegionConstraintCollector { storage: self, undo_log }
300    }
301}
302
303impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
304    pub fn num_region_vars(&self) -> usize {
305        self.storage.var_infos.len()
306    }
307
308    /// Takes (and clears) the current set of constraints. Note that
309    /// the set of variables remains intact, but all relationships
310    /// between them are reset. This is used during NLL checking to
311    /// grab the set of constraints that arose from a particular
312    /// operation.
313    ///
314    /// We don't want to leak relationships between variables between
315    /// points because just because (say) `r1 == r2` was true at some
316    /// point P in the graph doesn't imply that it will be true at
317    /// some other point Q, in NLL.
318    ///
319    /// Not legal during a snapshot.
320    pub fn take_and_reset_data(&mut self) -> RegionConstraintData<'tcx> {
321        assert!(!UndoLogs::<UndoLog<'_>>::in_snapshot(&self.undo_log));
322
323        // If you add a new field to `RegionConstraintCollector`, you
324        // should think carefully about whether it needs to be cleared
325        // or updated in some way.
326        let RegionConstraintStorage {
327            var_infos: _,
328            data,
329            lubs,
330            glbs,
331            unification_table: _,
332            any_unifications,
333        } = self.storage;
334
335        // Clear the tables of (lubs, glbs), so that we will create
336        // fresh regions if we do a LUB operation. As it happens,
337        // LUB/GLB are not performed by the MIR type-checker, which is
338        // the one that uses this method, but it's good to be correct.
339        lubs.clear();
340        glbs.clear();
341
342        let data = mem::take(data);
343
344        // Clear all unifications and recreate the variables a "now
345        // un-unified" state. Note that when we unify `a` and `b`, we
346        // also insert `a <= b` and a `b <= a` edges, so the
347        // `RegionConstraintData` contains the relationship here.
348        if *any_unifications {
349            *any_unifications = false;
350            // Manually inlined `self.unification_table_mut()` as `self` is used in the closure.
351            ut::UnificationTable::with_log(&mut self.storage.unification_table, &mut self.undo_log)
352                .reset_unifications(|key| RegionVariableValue::Unknown {
353                    universe: self.storage.var_infos[key.vid].universe,
354                });
355        }
356
357        data
358    }
359
360    pub fn data(&self) -> &RegionConstraintData<'tcx> {
361        &self.storage.data
362    }
363
364    pub(super) fn start_snapshot(&self) -> RegionSnapshot {
365        debug!("RegionConstraintCollector: start_snapshot");
366        RegionSnapshot { any_unifications: self.storage.any_unifications }
367    }
368
369    pub(super) fn rollback_to(&mut self, snapshot: RegionSnapshot) {
370        debug!("RegionConstraintCollector: rollback_to({:?})", snapshot);
371        self.storage.any_unifications = snapshot.any_unifications;
372    }
373
374    pub(super) fn new_region_var(
375        &mut self,
376        universe: ty::UniverseIndex,
377        origin: RegionVariableOrigin,
378    ) -> RegionVid {
379        let vid = self.storage.var_infos.push(RegionVariableInfo { origin, universe });
380
381        let u_vid = self.unification_table_mut().new_key(RegionVariableValue::Unknown { universe });
382        assert_eq!(vid, u_vid.vid);
383        self.undo_log.push(AddVar(vid));
384        debug!("created new region variable {:?} in {:?} with origin {:?}", vid, universe, origin);
385        vid
386    }
387
388    /// Returns the origin for the given variable.
389    pub(super) fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin {
390        self.storage.var_infos[vid].origin
391    }
392
393    fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) {
394        // cannot add constraints once regions are resolved
395        debug!("RegionConstraintCollector: add_constraint({:?})", constraint);
396
397        let index = self.storage.data.constraints.len();
398        self.storage.data.constraints.push((constraint, origin));
399        self.undo_log.push(AddConstraint(index));
400    }
401
402    fn add_verify(&mut self, verify: Verify<'tcx>) {
403        // cannot add verifys once regions are resolved
404        debug!("RegionConstraintCollector: add_verify({:?})", verify);
405
406        // skip no-op cases known to be satisfied
407        if let VerifyBound::AllBounds(ref bs) = verify.bound
408            && bs.is_empty()
409        {
410            return;
411        }
412
413        let index = self.storage.data.verifys.len();
414        self.storage.data.verifys.push(verify);
415        self.undo_log.push(AddVerify(index));
416    }
417
418    pub(super) fn make_eqregion(
419        &mut self,
420        origin: SubregionOrigin<'tcx>,
421        a: Region<'tcx>,
422        b: Region<'tcx>,
423    ) {
424        if a != b {
425            // Eventually, it would be nice to add direct support for
426            // equating regions.
427            self.make_subregion(origin.clone(), a, b);
428            self.make_subregion(origin, b, a);
429
430            match (a.kind(), b.kind()) {
431                (ty::ReVar(a), ty::ReVar(b)) => {
432                    debug!("make_eqregion: unifying {:?} with {:?}", a, b);
433                    if self.unification_table_mut().unify_var_var(a, b).is_ok() {
434                        self.storage.any_unifications = true;
435                    }
436                }
437                (ty::ReVar(vid), _) => {
438                    debug!("make_eqregion: unifying {:?} with {:?}", vid, b);
439                    if self
440                        .unification_table_mut()
441                        .unify_var_value(vid, RegionVariableValue::Known { value: b })
442                        .is_ok()
443                    {
444                        self.storage.any_unifications = true;
445                    };
446                }
447                (_, ty::ReVar(vid)) => {
448                    debug!("make_eqregion: unifying {:?} with {:?}", a, vid);
449                    if self
450                        .unification_table_mut()
451                        .unify_var_value(vid, RegionVariableValue::Known { value: a })
452                        .is_ok()
453                    {
454                        self.storage.any_unifications = true;
455                    };
456                }
457                (_, _) => {}
458            }
459        }
460    }
461
462    #[instrument(skip(self, origin), level = "debug")]
463    pub(super) fn make_subregion(
464        &mut self,
465        origin: SubregionOrigin<'tcx>,
466        sub: Region<'tcx>,
467        sup: Region<'tcx>,
468    ) {
469        // cannot add constraints once regions are resolved
470        debug!("origin = {:#?}", origin);
471
472        match (sub.kind(), sup.kind()) {
473            (ReBound(..), _) | (_, ReBound(..)) => {
474                span_bug!(origin.span(), "cannot relate bound region: {:?} <= {:?}", sub, sup);
475            }
476            (_, ReStatic) => {
477                // all regions are subregions of static, so we can ignore this
478            }
479            (ReVar(sub_id), ReVar(sup_id)) => {
480                if sub_id != sup_id {
481                    self.add_constraint(
482                        Constraint { kind: ConstraintKind::VarSubVar, sub, sup },
483                        origin,
484                    );
485                }
486            }
487            (_, ReVar(_)) => self
488                .add_constraint(Constraint { kind: ConstraintKind::RegSubVar, sub, sup }, origin),
489            (ReVar(_), _) => self
490                .add_constraint(Constraint { kind: ConstraintKind::VarSubReg, sub, sup }, origin),
491            _ => {
492                if sub != sup {
493                    self.add_constraint(
494                        Constraint { kind: ConstraintKind::RegSubReg, sub, sup },
495                        origin,
496                    )
497                }
498            }
499        }
500    }
501
502    pub(super) fn verify_generic_bound(
503        &mut self,
504        origin: SubregionOrigin<'tcx>,
505        kind: GenericKind<'tcx>,
506        sub: Region<'tcx>,
507        bound: VerifyBound<'tcx>,
508    ) {
509        self.add_verify(Verify { kind, origin, region: sub, bound });
510    }
511
512    pub(super) fn lub_regions(
513        &mut self,
514        tcx: TyCtxt<'tcx>,
515        origin: SubregionOrigin<'tcx>,
516        a: Region<'tcx>,
517        b: Region<'tcx>,
518    ) -> Region<'tcx> {
519        // cannot add constraints once regions are resolved
520        debug!("RegionConstraintCollector: lub_regions({:?}, {:?})", a, b);
521        if a.is_static() || b.is_static() {
522            a // nothing lives longer than static
523        } else if a == b {
524            a // LUB(a,a) = a
525        } else {
526            self.combine_vars(tcx, Lub, a, b, origin)
527        }
528    }
529
530    pub(super) fn glb_regions(
531        &mut self,
532        tcx: TyCtxt<'tcx>,
533        origin: SubregionOrigin<'tcx>,
534        a: Region<'tcx>,
535        b: Region<'tcx>,
536    ) -> Region<'tcx> {
537        // cannot add constraints once regions are resolved
538        debug!("RegionConstraintCollector: glb_regions({:?}, {:?})", a, b);
539        if a.is_static() {
540            b // static lives longer than everything else
541        } else if b.is_static() {
542            a // static lives longer than everything else
543        } else if a == b {
544            a // GLB(a,a) = a
545        } else {
546            self.combine_vars(tcx, Glb, a, b, origin)
547        }
548    }
549
550    /// Resolves a region var to its value in the unification table, if it exists.
551    /// Otherwise, it is resolved to the root `ReVar` in the table.
552    pub fn opportunistic_resolve_var(
553        &mut self,
554        tcx: TyCtxt<'tcx>,
555        vid: ty::RegionVid,
556    ) -> ty::Region<'tcx> {
557        let mut ut = self.unification_table_mut();
558        let root_vid = ut.find(vid).vid;
559        match ut.probe_value(root_vid) {
560            RegionVariableValue::Known { value } => value,
561            RegionVariableValue::Unknown { .. } => ty::Region::new_var(tcx, root_vid),
562        }
563    }
564
565    pub fn probe_value(
566        &mut self,
567        vid: ty::RegionVid,
568    ) -> Result<ty::Region<'tcx>, ty::UniverseIndex> {
569        match self.unification_table_mut().probe_value(vid) {
570            RegionVariableValue::Known { value } => Ok(value),
571            RegionVariableValue::Unknown { universe } => Err(universe),
572        }
573    }
574
575    fn combine_map(&mut self, t: CombineMapType) -> &mut CombineMap<'tcx> {
576        match t {
577            Glb => &mut self.storage.glbs,
578            Lub => &mut self.storage.lubs,
579        }
580    }
581
582    fn combine_vars(
583        &mut self,
584        tcx: TyCtxt<'tcx>,
585        t: CombineMapType,
586        a: Region<'tcx>,
587        b: Region<'tcx>,
588        origin: SubregionOrigin<'tcx>,
589    ) -> Region<'tcx> {
590        let vars = TwoRegions { a, b };
591        if let Some(&c) = self.combine_map(t).get(&vars) {
592            return ty::Region::new_var(tcx, c);
593        }
594        let a_universe = self.universe(a);
595        let b_universe = self.universe(b);
596        let c_universe = cmp::max(a_universe, b_universe);
597        let c = self.new_region_var(c_universe, RegionVariableOrigin::Misc(origin.span()));
598        self.combine_map(t).insert(vars, c);
599        self.undo_log.push(AddCombination(t, vars));
600        let new_r = ty::Region::new_var(tcx, c);
601        for old_r in [a, b] {
602            match t {
603                Glb => self.make_subregion(origin.clone(), new_r, old_r),
604                Lub => self.make_subregion(origin.clone(), old_r, new_r),
605            }
606        }
607        debug!("combine_vars() c={:?}", c);
608        new_r
609    }
610
611    pub fn universe(&mut self, region: Region<'tcx>) -> ty::UniverseIndex {
612        match region.kind() {
613            ty::ReStatic
614            | ty::ReErased
615            | ty::ReLateParam(..)
616            | ty::ReEarlyParam(..)
617            | ty::ReError(_) => ty::UniverseIndex::ROOT,
618            ty::RePlaceholder(placeholder) => placeholder.universe,
619            ty::ReVar(vid) => match self.probe_value(vid) {
620                Ok(value) => self.universe(value),
621                Err(universe) => universe,
622            },
623            ty::ReBound(..) => bug!("universe(): encountered bound region {:?}", region),
624        }
625    }
626
627    pub fn vars_since_snapshot(
628        &self,
629        value_count: usize,
630    ) -> (Range<RegionVid>, Vec<RegionVariableOrigin>) {
631        let range =
632            RegionVid::from(value_count)..RegionVid::from(self.storage.unification_table.len());
633        (
634            range.clone(),
635            (range.start..range.end).map(|index| self.storage.var_infos[index].origin).collect(),
636        )
637    }
638
639    /// See `InferCtxt::region_constraints_added_in_snapshot`.
640    pub fn region_constraints_added_in_snapshot(&self, mark: &Snapshot<'tcx>) -> bool {
641        self.undo_log
642            .region_constraints_in_snapshot(mark)
643            .any(|&elt| matches!(elt, AddConstraint(_)))
644    }
645
646    #[inline]
647    fn unification_table_mut(&mut self) -> super::UnificationTable<'_, 'tcx, RegionVidKey<'tcx>> {
648        ut::UnificationTable::with_log(&mut self.storage.unification_table, self.undo_log)
649    }
650}
651
652impl fmt::Debug for RegionSnapshot {
653    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
654        write!(f, "RegionSnapshot")
655    }
656}
657
658impl<'tcx> fmt::Debug for GenericKind<'tcx> {
659    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
660        match *self {
661            GenericKind::Param(ref p) => write!(f, "{p:?}"),
662            GenericKind::Placeholder(ref p) => write!(f, "{p:?}"),
663            GenericKind::Alias(ref p) => write!(f, "{p:?}"),
664        }
665    }
666}
667
668impl<'tcx> fmt::Display for GenericKind<'tcx> {
669    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
670        match *self {
671            GenericKind::Param(ref p) => write!(f, "{p}"),
672            GenericKind::Placeholder(ref p) => write!(f, "{p}"),
673            GenericKind::Alias(ref p) => write!(f, "{p}"),
674        }
675    }
676}
677
678impl<'tcx> GenericKind<'tcx> {
679    pub fn to_ty(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
680        match *self {
681            GenericKind::Param(ref p) => p.to_ty(tcx),
682            GenericKind::Placeholder(ref p) => Ty::new_placeholder(tcx, *p),
683            GenericKind::Alias(ref p) => p.to_ty(tcx),
684        }
685    }
686}
687
688impl<'tcx> VerifyBound<'tcx> {
689    pub fn must_hold(&self) -> bool {
690        match self {
691            VerifyBound::IfEq(..) => false,
692            VerifyBound::OutlivedBy(re) => re.is_static(),
693            VerifyBound::IsEmpty => false,
694            VerifyBound::AnyBound(bs) => bs.iter().any(|b| b.must_hold()),
695            VerifyBound::AllBounds(bs) => bs.iter().all(|b| b.must_hold()),
696        }
697    }
698
699    pub fn cannot_hold(&self) -> bool {
700        match self {
701            VerifyBound::IfEq(..) => false,
702            VerifyBound::IsEmpty => false,
703            VerifyBound::OutlivedBy(_) => false,
704            VerifyBound::AnyBound(bs) => bs.iter().all(|b| b.cannot_hold()),
705            VerifyBound::AllBounds(bs) => bs.iter().any(|b| b.cannot_hold()),
706        }
707    }
708
709    pub fn or(self, vb: VerifyBound<'tcx>) -> VerifyBound<'tcx> {
710        if self.must_hold() || vb.cannot_hold() {
711            self
712        } else if self.cannot_hold() || vb.must_hold() {
713            vb
714        } else {
715            VerifyBound::AnyBound(vec![self, vb])
716        }
717    }
718}
719
720impl<'tcx> RegionConstraintData<'tcx> {
721    /// Returns `true` if this region constraint data contains no constraints, and `false`
722    /// otherwise.
723    pub fn is_empty(&self) -> bool {
724        let RegionConstraintData { constraints, verifys } = self;
725        constraints.is_empty() && verifys.is_empty()
726    }
727}
728
729impl<'tcx> Rollback<UndoLog<'tcx>> for RegionConstraintStorage<'tcx> {
730    fn reverse(&mut self, undo: UndoLog<'tcx>) {
731        match undo {
732            AddVar(vid) => {
733                self.var_infos.pop().unwrap();
734                assert_eq!(self.var_infos.len(), vid.index());
735            }
736            AddConstraint(index) => {
737                self.data.constraints.pop().unwrap();
738                assert_eq!(self.data.constraints.len(), index);
739            }
740            AddVerify(index) => {
741                self.data.verifys.pop();
742                assert_eq!(self.data.verifys.len(), index);
743            }
744            AddCombination(Glb, ref regions) => {
745                self.glbs.remove(regions);
746            }
747            AddCombination(Lub, ref regions) => {
748                self.lubs.remove(regions);
749            }
750        }
751    }
752}
rustc_infer/infer/region_constraints/mod.rs

rustc_infer/infer/region_constraints/
mod.rs
