rustc_infer/infer/region_constraints/
mod.rs

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

rustc_infer/infer/region_constraints/
mod.rs
