//! Lexical region resolution.

use crate::infer::region_constraints::Constraint;
use crate::infer::region_constraints::GenericKind;
use crate::infer::region_constraints::MemberConstraint;
use crate::infer::region_constraints::RegionConstraintData;
use crate::infer::region_constraints::VarInfos;
use crate::infer::region_constraints::VerifyBound;
use crate::infer::RegionRelations;
use crate::infer::RegionVariableOrigin;
use crate::infer::RegionckMode;
use crate::infer::SubregionOrigin;
use rustc_data_structures::fx::FxHashSet;
use rustc_data_structures::graph::implementation::{
    Direction, Graph, NodeIndex, INCOMING, OUTGOING,
};
use rustc_index::vec::{Idx, IndexVec};
use rustc_middle::ty::fold::TypeFoldable;
use rustc_middle::ty::{self, Ty, TyCtxt};
use rustc_middle::ty::{ReEarlyBound, ReEmpty, ReErased, ReFree, ReStatic};
use rustc_middle::ty::{ReLateBound, RePlaceholder, ReVar};
use rustc_middle::ty::{Region, RegionVid};
use rustc_span::Span;
use std::fmt;

/// This function performs lexical region resolution given a complete
/// set of constraints and variable origins. It performs a fixed-point
/// iteration to find region values which satisfy all constraints,
/// assuming such values can be found. It returns the final values of
/// all the variables as well as a set of errors that must be reported.
pub fn resolve<'tcx>(
    region_rels: &RegionRelations<'_, 'tcx>,
    var_infos: VarInfos,
    data: RegionConstraintData<'tcx>,
    mode: RegionckMode,
) -> (LexicalRegionResolutions<'tcx>, Vec<RegionResolutionError<'tcx>>) {
    debug!("RegionConstraintData: resolve_regions()");
    let mut errors = vec![];
    let mut resolver = LexicalResolver { region_rels, var_infos, data };
    match mode {
        RegionckMode::Solve => {
            let values = resolver.infer_variable_values(&mut errors);
            (values, errors)
        }
        RegionckMode::Erase { suppress_errors: false } => {
            // Do real inference to get errors, then erase the results.
            let mut values = resolver.infer_variable_values(&mut errors);
            let re_erased = region_rels.tcx.lifetimes.re_erased;

            values.values.iter_mut().for_each(|v| match *v {
                VarValue::Value(ref mut r) => *r = re_erased,
                VarValue::ErrorValue => {}
            });
            (values, errors)
        }
        RegionckMode::Erase { suppress_errors: true } => {
            // Skip region inference entirely.
            (resolver.erased_data(region_rels.tcx), Vec::new())
        }
    }
}

/// Contains the result of lexical region resolution. Offers methods
/// to lookup up the final value of a region variable.
pub struct LexicalRegionResolutions<'tcx> {
    values: IndexVec<RegionVid, VarValue<'tcx>>,
    error_region: ty::Region<'tcx>,
}

#[derive(Copy, Clone, Debug)]
enum VarValue<'tcx> {
    Value(Region<'tcx>),
    ErrorValue,
}

#[derive(Clone, Debug)]
pub enum RegionResolutionError<'tcx> {
    /// `ConcreteFailure(o, a, b)`:
    ///
    /// `o` requires that `a <= b`, but this does not hold
    ConcreteFailure(SubregionOrigin<'tcx>, Region<'tcx>, Region<'tcx>),

    /// `GenericBoundFailure(p, s, a)
    ///
    /// The parameter/associated-type `p` must be known to outlive the lifetime
    /// `a` (but none of the known bounds are sufficient).
    GenericBoundFailure(SubregionOrigin<'tcx>, GenericKind<'tcx>, Region<'tcx>),

    /// `SubSupConflict(v, v_origin, sub_origin, sub_r, sup_origin, sup_r)`:
    ///
    /// Could not infer a value for `v` (which has origin `v_origin`)
    /// because `sub_r <= v` (due to `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
    /// `sub_r <= sup_r` does not hold.
    SubSupConflict(
        RegionVid,
        RegionVariableOrigin,
        SubregionOrigin<'tcx>,
        Region<'tcx>,
        SubregionOrigin<'tcx>,
        Region<'tcx>,
    ),

    /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
    /// cannot name the placeholder `'b`.
    UpperBoundUniverseConflict(
        RegionVid,
        RegionVariableOrigin,
        ty::UniverseIndex,     // the universe index of the region variable
        SubregionOrigin<'tcx>, // cause of the constraint
        Region<'tcx>,          // the placeholder `'b`
    ),

    /// Indicates a failure of a `MemberConstraint`. These arise during
    /// impl trait processing explicitly -- basically, the impl trait's hidden type
    /// included some region that it was not supposed to.
    MemberConstraintFailure { span: Span, hidden_ty: Ty<'tcx>, member_region: Region<'tcx> },
}

struct RegionAndOrigin<'tcx> {
    region: Region<'tcx>,
    origin: SubregionOrigin<'tcx>,
}

type RegionGraph<'tcx> = Graph<(), Constraint<'tcx>>;

struct LexicalResolver<'cx, 'tcx> {
    region_rels: &'cx RegionRelations<'cx, 'tcx>,
    var_infos: VarInfos,
    data: RegionConstraintData<'tcx>,
}

impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
    fn tcx(&self) -> TyCtxt<'tcx> {
        self.region_rels.tcx
    }

    fn infer_variable_values(
        &mut self,
        errors: &mut Vec<RegionResolutionError<'tcx>>,
    ) -> LexicalRegionResolutions<'tcx> {
        let mut var_data = self.construct_var_data(self.tcx());

        // Dorky hack to cause `dump_constraints` to only get called
        // if debug mode is enabled:
        debug!(
            "----() End constraint listing (context={:?}) {:?}---",
            self.region_rels.context,
            self.dump_constraints(self.region_rels)
        );

        let graph = self.construct_graph();
        self.expand_givens(&graph);
        loop {
            self.expansion(&mut var_data);
            if !self.enforce_member_constraints(&graph, &mut var_data) {
                break;
            }
        }
        self.collect_errors(&mut var_data, errors);
        self.collect_var_errors(&var_data, &graph, errors);
        var_data
    }

    fn num_vars(&self) -> usize {
        self.var_infos.len()
    }

    /// Initially, the value for all variables is set to `'empty`, the
    /// empty region. The `expansion` phase will grow this larger.
    fn construct_var_data(&self, tcx: TyCtxt<'tcx>) -> LexicalRegionResolutions<'tcx> {
        LexicalRegionResolutions {
            error_region: tcx.lifetimes.re_static,
            values: IndexVec::from_fn_n(
                |vid| {
                    let vid_universe = self.var_infos[vid].universe;
                    let re_empty = tcx.mk_region(ty::ReEmpty(vid_universe));
                    VarValue::Value(re_empty)
                },
                self.num_vars(),
            ),
        }
    }

    /// An erased version of the lexical region resolutions. Used when we're
    /// erasing regions and suppressing errors: in item bodies with
    /// `-Zborrowck=mir`.
    fn erased_data(&self, tcx: TyCtxt<'tcx>) -> LexicalRegionResolutions<'tcx> {
        LexicalRegionResolutions {
            error_region: tcx.lifetimes.re_static,
            values: IndexVec::from_elem_n(
                VarValue::Value(tcx.lifetimes.re_erased),
                self.num_vars(),
            ),
        }
    }

    fn dump_constraints(&self, free_regions: &RegionRelations<'_, 'tcx>) {
        debug!("----() Start constraint listing (context={:?}) ()----", free_regions.context);
        for (idx, (constraint, _)) in self.data.constraints.iter().enumerate() {
            debug!("Constraint {} => {:?}", idx, constraint);
        }
    }

    fn expand_givens(&mut self, graph: &RegionGraph<'_>) {
        // Givens are a kind of horrible hack to account for
        // constraints like 'c <= '0 that are known to hold due to
        // closure signatures (see the comment above on the `givens`
        // field). They should go away. But until they do, the role
        // of this fn is to account for the transitive nature:
        //
        //     Given 'c <= '0
        //     and   '0 <= '1
        //     then  'c <= '1

        let seeds: Vec<_> = self.data.givens.iter().cloned().collect();
        for (r, vid) in seeds {
            // While all things transitively reachable in the graph
            // from the variable (`'0` in the example above).
            let seed_index = NodeIndex(vid.index() as usize);
            for succ_index in graph.depth_traverse(seed_index, OUTGOING) {
                let succ_index = succ_index.0;

                // The first N nodes correspond to the region
                // variables. Other nodes correspond to constant
                // regions.
                if succ_index < self.num_vars() {
                    let succ_vid = RegionVid::new(succ_index);

                    // Add `'c <= '1`.
                    self.data.givens.insert((r, succ_vid));
                }
            }
        }
    }

    /// Enforce all member constraints and return true if anything
    /// changed. See `enforce_member_constraint` for more details.
    fn enforce_member_constraints(
        &self,
        graph: &RegionGraph<'tcx>,
        var_values: &mut LexicalRegionResolutions<'tcx>,
    ) -> bool {
        // Note: we don't use the `any` combinator because we don't
        // want to stop at the first constraint that makes a change.
        let mut any_changed = false;
        for member_constraint in &self.data.member_constraints {
            any_changed |= self.enforce_member_constraint(graph, member_constraint, var_values);
        }
        any_changed
    }

    /// Enforce a constraint like
    ///
    /// ```
    /// 'r member of ['c...]
    /// ```
    ///
    /// We look for all choice regions from the list `'c...` that:
    ///
    /// (a) are greater than the current value of `'r` (which is a lower bound)
    ///
    /// and
    ///
    /// (b) are compatible with the upper bounds of `'r` that we can
    /// find by traversing the graph.
    ///
    /// From that list, we look for a *minimal* option `'c_min`. If we
    /// find one, then we can enforce that `'r: 'c_min`.
    fn enforce_member_constraint(
        &self,
        graph: &RegionGraph<'tcx>,
        member_constraint: &MemberConstraint<'tcx>,
        var_values: &mut LexicalRegionResolutions<'tcx>,
    ) -> bool {
        debug!("enforce_member_constraint(member_constraint={:#?})", member_constraint);

        // The constraint is some inference variable (`vid`) which
        // must be equal to one of the options.
        let member_vid = match member_constraint.member_region {
            ty::ReVar(vid) => *vid,
            _ => return false,
        };

        // The current value of `vid` is a lower bound LB -- i.e., we
        // know that `LB <= vid` must be true.
        let member_lower_bound: ty::Region<'tcx> = match var_values.value(member_vid) {
            VarValue::ErrorValue => return false,
            VarValue::Value(r) => r,
        };

        // Find all the "upper bounds" -- that is, each region `b` such that
        // `r0 <= b` must hold.
        let (member_upper_bounds, ..) =
            self.collect_bounding_regions(graph, member_vid, OUTGOING, None);

        // Get an iterator over the *available choice* -- that is,
        // each choice region `c` where `lb <= c` and `c <= ub` for all the
        // upper bounds `ub`.
        debug!("enforce_member_constraint: upper_bounds={:#?}", member_upper_bounds);
        let mut options = member_constraint.choice_regions.iter().filter(|option| {
            self.sub_concrete_regions(member_lower_bound, option)
                && member_upper_bounds
                    .iter()
                    .all(|upper_bound| self.sub_concrete_regions(option, upper_bound.region))
        });

        // If there is more than one option, we only make a choice if
        // there is a single *least* choice -- i.e., some available
        // region that is `<=` all the others.
        let mut least_choice: ty::Region<'tcx> = match options.next() {
            Some(&r) => r,
            None => return false,
        };
        debug!("enforce_member_constraint: least_choice={:?}", least_choice);
        for &option in options {
            debug!("enforce_member_constraint: option={:?}", option);
            if !self.sub_concrete_regions(least_choice, option) {
                if self.sub_concrete_regions(option, least_choice) {
                    debug!("enforce_member_constraint: new least choice");
                    least_choice = option;
                } else {
                    debug!("enforce_member_constraint: no least choice");
                    return false;
                }
            }
        }

        // (#72087) Different `ty::Regions` can be known to be equal, for
        // example, we know that `'a` and `'static` are equal in a function
        // with a parameter of type `&'static &'a ()`.
        //
        // When we have two equal regions like this `expansion` will use
        // `lub_concrete_regions` to pick a canonical representative. The same
        // choice is needed here so that we don't end up in a cycle of
        // `expansion` changing the region one way and the code here changing
        // it back.
        let lub = self.lub_concrete_regions(least_choice, member_lower_bound);
        debug!(
            "enforce_member_constraint: final least choice = {:?}\nlub = {:?}",
            least_choice, lub
        );
        if lub != member_lower_bound {
            *var_values.value_mut(member_vid) = VarValue::Value(least_choice);
            true
        } else {
            false
        }
    }

    fn expansion(&self, var_values: &mut LexicalRegionResolutions<'tcx>) {
        let mut constraints = IndexVec::from_elem_n(Vec::new(), var_values.values.len());
        let mut changes = Vec::new();
        for constraint in self.data.constraints.keys() {
            let (a_vid, a_region, b_vid, b_data) = match *constraint {
                Constraint::RegSubVar(a_region, b_vid) => {
                    let b_data = var_values.value_mut(b_vid);
                    (None, a_region, b_vid, b_data)
                }
                Constraint::VarSubVar(a_vid, b_vid) => match *var_values.value(a_vid) {
                    VarValue::ErrorValue => continue,
                    VarValue::Value(a_region) => {
                        let b_data = var_values.value_mut(b_vid);
                        (Some(a_vid), a_region, b_vid, b_data)
                    }
                },
                Constraint::RegSubReg(..) | Constraint::VarSubReg(..) => {
                    // These constraints are checked after expansion
                    // is done, in `collect_errors`.
                    continue;
                }
            };
            if self.expand_node(a_region, b_vid, b_data) {
                changes.push(b_vid);
            }
            if let Some(a_vid) = a_vid {
                match *b_data {
                    VarValue::Value(ReStatic) | VarValue::ErrorValue => (),
                    _ => {
                        constraints[a_vid].push((a_vid, b_vid));
                        constraints[b_vid].push((a_vid, b_vid));
                    }
                }
            }
        }

        while let Some(vid) = changes.pop() {
            constraints[vid].retain(|&(a_vid, b_vid)| {
                let a_region = match *var_values.value(a_vid) {
                    VarValue::ErrorValue => return false,
                    VarValue::Value(a_region) => a_region,
                };
                let b_data = var_values.value_mut(b_vid);
                if self.expand_node(a_region, b_vid, b_data) {
                    changes.push(b_vid);
                }
                match *b_data {
                    VarValue::Value(ReStatic) | VarValue::ErrorValue => false,
                    _ => true,
                }
            });
        }
    }

    fn expand_node(
        &self,
        a_region: Region<'tcx>,
        b_vid: RegionVid,
        b_data: &mut VarValue<'tcx>,
    ) -> bool {
        debug!("expand_node({:?}, {:?} == {:?})", a_region, b_vid, b_data);

        match *a_region {
            // Check if this relationship is implied by a given.
            ty::ReEarlyBound(_) | ty::ReFree(_) => {
                if self.data.givens.contains(&(a_region, b_vid)) {
                    debug!("given");
                    return false;
                }
            }

            _ => {}
        }

        match *b_data {
            VarValue::Value(cur_region) => {
                // This is a specialized version of the `lub_concrete_regions`
                // check below for a common case, here purely as an
                // optimization.
                let b_universe = self.var_infos[b_vid].universe;
                if let ReEmpty(a_universe) = a_region {
                    if *a_universe == b_universe {
                        return false;
                    }
                }

                let mut lub = self.lub_concrete_regions(a_region, cur_region);
                if lub == cur_region {
                    return false;
                }

                // Watch out for `'b: !1` relationships, where the
                // universe of `'b` can't name the placeholder `!1`. In
                // that case, we have to grow `'b` to be `'static` for the
                // relationship to hold. This is obviously a kind of sub-optimal
                // choice -- in the future, when we incorporate a knowledge
                // of the parameter environment, we might be able to find a
                // tighter bound than `'static`.
                //
                // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
                if let ty::RePlaceholder(p) = lub {
                    if b_universe.cannot_name(p.universe) {
                        lub = self.tcx().lifetimes.re_static;
                    }
                }

                debug!("Expanding value of {:?} from {:?} to {:?}", b_vid, cur_region, lub);

                *b_data = VarValue::Value(lub);
                true
            }

            VarValue::ErrorValue => false,
        }
    }

    /// True if `a <= b`, but not defined over inference variables.
    fn sub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> bool {
        let tcx = self.tcx();
        let sub_free_regions = |r1, r2| self.region_rels.free_regions.sub_free_regions(tcx, r1, r2);

        // Check for the case where we know that `'b: 'static` -- in that case,
        // `a <= b` for all `a`.
        let b_free_or_static = self.region_rels.free_regions.is_free_or_static(b);
        if b_free_or_static && sub_free_regions(tcx.lifetimes.re_static, b) {
            return true;
        }

        // If both `a` and `b` are free, consult the declared
        // relationships.  Note that this can be more precise than the
        // `lub` relationship defined below, since sometimes the "lub"
        // is actually the `postdom_upper_bound` (see
        // `TransitiveRelation` for more details).
        let a_free_or_static = self.region_rels.free_regions.is_free_or_static(a);
        if a_free_or_static && b_free_or_static {
            return sub_free_regions(a, b);
        }

        // For other cases, leverage the LUB code to find the LUB and
        // check if it is equal to `b`.
        self.lub_concrete_regions(a, b) == b
    }

    /// Returns the least-upper-bound of `a` and `b`; i.e., the
    /// smallest region `c` such that `a <= c` and `b <= c`.
    ///
    /// Neither `a` nor `b` may be an inference variable (hence the
    /// term "concrete regions").
    fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> {
        let r = match (a, b) {
            (&ReLateBound(..), _) | (_, &ReLateBound(..)) | (&ReErased, _) | (_, &ReErased) => {
                bug!("cannot relate region: LUB({:?}, {:?})", a, b);
            }

            (&ReVar(v_id), _) | (_, &ReVar(v_id)) => {
                span_bug!(
                    self.var_infos[v_id].origin.span(),
                    "lub_concrete_regions invoked with non-concrete \
                     regions: {:?}, {:?}",
                    a,
                    b
                );
            }

            (&ReStatic, _) | (_, &ReStatic) => {
                // nothing lives longer than `'static`
                self.tcx().lifetimes.re_static
            }

            (&ReEmpty(_), r @ (ReEarlyBound(_) | ReFree(_)))
            | (r @ (ReEarlyBound(_) | ReFree(_)), &ReEmpty(_)) => {
                // All empty regions are less than early-bound, free,
                // and scope regions.
                r
            }

            (&ReEmpty(a_ui), &ReEmpty(b_ui)) => {
                // Empty regions are ordered according to the universe
                // they are associated with.
                let ui = a_ui.min(b_ui);
                self.tcx().mk_region(ReEmpty(ui))
            }

            (&ReEmpty(empty_ui), &RePlaceholder(placeholder))
            | (&RePlaceholder(placeholder), &ReEmpty(empty_ui)) => {
                // If this empty region is from a universe that can
                // name the placeholder, then the placeholder is
                // larger; otherwise, the only ancestor is `'static`.
                if empty_ui.can_name(placeholder.universe) {
                    self.tcx().mk_region(RePlaceholder(placeholder))
                } else {
                    self.tcx().lifetimes.re_static
                }
            }

            (&ReEarlyBound(_) | &ReFree(_), &ReEarlyBound(_) | &ReFree(_)) => {
                self.region_rels.lub_free_regions(a, b)
            }

            // For these types, we cannot define any additional
            // relationship:
            (&RePlaceholder(..), _) | (_, &RePlaceholder(..)) => {
                if a == b {
                    a
                } else {
                    self.tcx().lifetimes.re_static
                }
            }
        };

        debug!("lub_concrete_regions({:?}, {:?}) = {:?}", a, b, r);

        r
    }

    /// After expansion is complete, go and check upper bounds (i.e.,
    /// cases where the region cannot grow larger than a fixed point)
    /// and check that they are satisfied.
    fn collect_errors(
        &self,
        var_data: &mut LexicalRegionResolutions<'tcx>,
        errors: &mut Vec<RegionResolutionError<'tcx>>,
    ) {
        for (constraint, origin) in &self.data.constraints {
            debug!("collect_errors: constraint={:?} origin={:?}", constraint, origin);
            match *constraint {
                Constraint::RegSubVar(..) | Constraint::VarSubVar(..) => {
                    // Expansion will ensure that these constraints hold. Ignore.
                }

                Constraint::RegSubReg(sub, sup) => {
                    if self.sub_concrete_regions(sub, sup) {
                        continue;
                    }

                    debug!(
                        "collect_errors: region error at {:?}: \
                         cannot verify that {:?} <= {:?}",
                        origin, sub, sup
                    );

                    errors.push(RegionResolutionError::ConcreteFailure(
                        (*origin).clone(),
                        sub,
                        sup,
                    ));
                }

                Constraint::VarSubReg(a_vid, b_region) => {
                    let a_data = var_data.value_mut(a_vid);
                    debug!("contraction: {:?} == {:?}, {:?}", a_vid, a_data, b_region);

                    let a_region = match *a_data {
                        VarValue::ErrorValue => continue,
                        VarValue::Value(a_region) => a_region,
                    };

                    // Do not report these errors immediately:
                    // instead, set the variable value to error and
                    // collect them later.
                    if !self.sub_concrete_regions(a_region, b_region) {
                        debug!(
                            "collect_errors: region error at {:?}: \
                            cannot verify that {:?}={:?} <= {:?}",
                            origin, a_vid, a_region, b_region
                        );
                        *a_data = VarValue::ErrorValue;
                    }
                }
            }
        }

        // Check that all member constraints are satisfied.
        for member_constraint in &self.data.member_constraints {
            let member_region = var_data.normalize(self.tcx(), member_constraint.member_region);
            let choice_regions = member_constraint
                .choice_regions
                .iter()
                .map(|&choice_region| var_data.normalize(self.tcx(), choice_region));
            if !choice_regions.clone().any(|choice_region| member_region == choice_region) {
                let span = self.tcx().def_span(member_constraint.opaque_type_def_id);
                errors.push(RegionResolutionError::MemberConstraintFailure {
                    span,
                    hidden_ty: member_constraint.hidden_ty,
                    member_region,
                });
            }
        }

        for verify in &self.data.verifys {
            debug!("collect_errors: verify={:?}", verify);
            let sub = var_data.normalize(self.tcx(), verify.region);

            let verify_kind_ty = verify.kind.to_ty(self.tcx());
            if self.bound_is_met(&verify.bound, var_data, verify_kind_ty, sub) {
                continue;
            }

            debug!(
                "collect_errors: region error at {:?}: \
                 cannot verify that {:?} <= {:?}",
                verify.origin, verify.region, verify.bound
            );

            errors.push(RegionResolutionError::GenericBoundFailure(
                verify.origin.clone(),
                verify.kind,
                sub,
            ));
        }
    }

    /// Go over the variables that were declared to be error variables
    /// and create a `RegionResolutionError` for each of them.
    fn collect_var_errors(
        &self,
        var_data: &LexicalRegionResolutions<'tcx>,
        graph: &RegionGraph<'tcx>,
        errors: &mut Vec<RegionResolutionError<'tcx>>,
    ) {
        debug!("collect_var_errors, var_data = {:#?}", var_data.values);

        // This is the best way that I have found to suppress
        // duplicate and related errors. Basically we keep a set of
        // flags for every node. Whenever an error occurs, we will
        // walk some portion of the graph looking to find pairs of
        // conflicting regions to report to the user. As we walk, we
        // trip the flags from false to true, and if we find that
        // we've already reported an error involving any particular
        // node we just stop and don't report the current error.  The
        // idea is to report errors that derive from independent
        // regions of the graph, but not those that derive from
        // overlapping locations.
        let mut dup_vec = IndexVec::from_elem_n(None, self.num_vars());

        for (node_vid, value) in var_data.values.iter_enumerated() {
            match *value {
                VarValue::Value(_) => { /* Inference successful */ }
                VarValue::ErrorValue => {
                    // Inference impossible: this value contains
                    // inconsistent constraints.
                    //
                    // I think that in this case we should report an
                    // error now -- unlike the case above, we can't
                    // wait to see whether the user needs the result
                    // of this variable. The reason is that the mere
                    // existence of this variable implies that the
                    // region graph is inconsistent, whether or not it
                    // is used.
                    //
                    // For example, we may have created a region
                    // variable that is the GLB of two other regions
                    // which do not have a GLB. Even if that variable
                    // is not used, it implies that those two regions
                    // *should* have a GLB.
                    //
                    // At least I think this is true. It may be that
                    // the mere existence of a conflict in a region
                    // variable that is not used is not a problem, so
                    // if this rule starts to create problems we'll
                    // have to revisit this portion of the code and
                    // think hard about it. =) -- nikomatsakis
                    self.collect_error_for_expanding_node(graph, &mut dup_vec, node_vid, errors);
                }
            }
        }
    }

    fn construct_graph(&self) -> RegionGraph<'tcx> {
        let num_vars = self.num_vars();

        let mut graph = Graph::new();

        for _ in 0..num_vars {
            graph.add_node(());
        }

        // Issue #30438: two distinct dummy nodes, one for incoming
        // edges (dummy_source) and another for outgoing edges
        // (dummy_sink). In `dummy -> a -> b -> dummy`, using one
        // dummy node leads one to think (erroneously) there exists a
        // path from `b` to `a`. Two dummy nodes sidesteps the issue.
        let dummy_source = graph.add_node(());
        let dummy_sink = graph.add_node(());

        for constraint in self.data.constraints.keys() {
            match *constraint {
                Constraint::VarSubVar(a_id, b_id) => {
                    graph.add_edge(
                        NodeIndex(a_id.index() as usize),
                        NodeIndex(b_id.index() as usize),
                        *constraint,
                    );
                }
                Constraint::RegSubVar(_, b_id) => {
                    graph.add_edge(dummy_source, NodeIndex(b_id.index() as usize), *constraint);
                }
                Constraint::VarSubReg(a_id, _) => {
                    graph.add_edge(NodeIndex(a_id.index() as usize), dummy_sink, *constraint);
                }
                Constraint::RegSubReg(..) => {
                    // this would be an edge from `dummy_source` to
                    // `dummy_sink`; just ignore it.
                }
            }
        }

        graph
    }

    fn collect_error_for_expanding_node(
        &self,
        graph: &RegionGraph<'tcx>,
        dup_vec: &mut IndexVec<RegionVid, Option<RegionVid>>,
        node_idx: RegionVid,
        errors: &mut Vec<RegionResolutionError<'tcx>>,
    ) {
        // Errors in expanding nodes result from a lower-bound that is
        // not contained by an upper-bound.
        let (mut lower_bounds, lower_vid_bounds, lower_dup) =
            self.collect_bounding_regions(graph, node_idx, INCOMING, Some(dup_vec));
        let (mut upper_bounds, _, upper_dup) =
            self.collect_bounding_regions(graph, node_idx, OUTGOING, Some(dup_vec));

        if lower_dup || upper_dup {
            return;
        }

        // We place free regions first because we are special casing
        // SubSupConflict(ReFree, ReFree) when reporting error, and so
        // the user will more likely get a specific suggestion.
        fn region_order_key(x: &RegionAndOrigin<'_>) -> u8 {
            match *x.region {
                ReEarlyBound(_) => 0,
                ReFree(_) => 1,
                _ => 2,
            }
        }
        lower_bounds.sort_by_key(region_order_key);
        upper_bounds.sort_by_key(region_order_key);

        let node_universe = self.var_infos[node_idx].universe;

        for lower_bound in &lower_bounds {
            let effective_lower_bound = if let ty::RePlaceholder(p) = lower_bound.region {
                if node_universe.cannot_name(p.universe) {
                    self.tcx().lifetimes.re_static
                } else {
                    lower_bound.region
                }
            } else {
                lower_bound.region
            };

            for upper_bound in &upper_bounds {
                if !self.sub_concrete_regions(effective_lower_bound, upper_bound.region) {
                    let origin = self.var_infos[node_idx].origin;
                    debug!(
                        "region inference error at {:?} for {:?}: SubSupConflict sub: {:?} \
                         sup: {:?}",
                        origin, node_idx, lower_bound.region, upper_bound.region
                    );
                    errors.push(RegionResolutionError::SubSupConflict(
                        node_idx,
                        origin,
                        lower_bound.origin.clone(),
                        lower_bound.region,
                        upper_bound.origin.clone(),
                        upper_bound.region,
                    ));
                    return;
                }
            }
        }

        // If we have a scenario like `exists<'a> { forall<'b> { 'b:
        // 'a } }`, we wind up without any lower-bound -- all we have
        // are placeholders as upper bounds, but the universe of the
        // variable `'a`, or some variable that `'a` has to outlive, doesn't
        // permit those placeholders.
        let min_universe = lower_vid_bounds
            .into_iter()
            .map(|vid| self.var_infos[vid].universe)
            .min()
            .expect("lower_vid_bounds should at least include `node_idx`");

        for upper_bound in &upper_bounds {
            if let ty::RePlaceholder(p) = upper_bound.region {
                if min_universe.cannot_name(p.universe) {
                    let origin = self.var_infos[node_idx].origin;
                    errors.push(RegionResolutionError::UpperBoundUniverseConflict(
                        node_idx,
                        origin,
                        min_universe,
                        upper_bound.origin.clone(),
                        upper_bound.region,
                    ));
                    return;
                }
            }
        }

        // Errors in earlier passes can yield error variables without
        // resolution errors here; delay ICE in favor of those errors.
        self.tcx().sess.delay_span_bug(
            self.var_infos[node_idx].origin.span(),
            &format!(
                "collect_error_for_expanding_node() could not find \
                 error for var {:?} in universe {:?}, lower_bounds={:#?}, \
                 upper_bounds={:#?}",
                node_idx, node_universe, lower_bounds, upper_bounds
            ),
        );
    }

    /// Collects all regions that "bound" the variable `orig_node_idx` in the
    /// given direction.
    ///
    /// If `dup_vec` is `Some` it's used to track duplicates between successive
    /// calls of this function.
    ///
    /// The return tuple fields are:
    /// - a list of all concrete regions bounding the given region.
    /// - the set of all region variables bounding the given region.
    /// - a `bool` that's true if the returned region variables overlap with
    ///   those returned by a previous call for another region.
    fn collect_bounding_regions(
        &self,
        graph: &RegionGraph<'tcx>,
        orig_node_idx: RegionVid,
        dir: Direction,
        mut dup_vec: Option<&mut IndexVec<RegionVid, Option<RegionVid>>>,
    ) -> (Vec<RegionAndOrigin<'tcx>>, FxHashSet<RegionVid>, bool) {
        struct WalkState<'tcx> {
            set: FxHashSet<RegionVid>,
            stack: Vec<RegionVid>,
            result: Vec<RegionAndOrigin<'tcx>>,
            dup_found: bool,
        }
        let mut state = WalkState {
            set: Default::default(),
            stack: vec![orig_node_idx],
            result: Vec::new(),
            dup_found: false,
        };
        state.set.insert(orig_node_idx);

        // to start off the process, walk the source node in the
        // direction specified
        process_edges(&self.data, &mut state, graph, orig_node_idx, dir);

        while let Some(node_idx) = state.stack.pop() {
            // check whether we've visited this node on some previous walk
            if let Some(dup_vec) = &mut dup_vec {
                if dup_vec[node_idx].is_none() {
                    dup_vec[node_idx] = Some(orig_node_idx);
                } else if dup_vec[node_idx] != Some(orig_node_idx) {
                    state.dup_found = true;
                }

                debug!(
                    "collect_concrete_regions(orig_node_idx={:?}, node_idx={:?})",
                    orig_node_idx, node_idx
                );
            }

            process_edges(&self.data, &mut state, graph, node_idx, dir);
        }

        let WalkState { result, dup_found, set, .. } = state;
        return (result, set, dup_found);

        fn process_edges<'tcx>(
            this: &RegionConstraintData<'tcx>,
            state: &mut WalkState<'tcx>,
            graph: &RegionGraph<'tcx>,
            source_vid: RegionVid,
            dir: Direction,
        ) {
            debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);

            let source_node_index = NodeIndex(source_vid.index() as usize);
            for (_, edge) in graph.adjacent_edges(source_node_index, dir) {
                match edge.data {
                    Constraint::VarSubVar(from_vid, to_vid) => {
                        let opp_vid = if from_vid == source_vid { to_vid } else { from_vid };
                        if state.set.insert(opp_vid) {
                            state.stack.push(opp_vid);
                        }
                    }

                    Constraint::RegSubVar(region, _) | Constraint::VarSubReg(_, region) => {
                        state.result.push(RegionAndOrigin {
                            region,
                            origin: this.constraints.get(&edge.data).unwrap().clone(),
                        });
                    }

                    Constraint::RegSubReg(..) => panic!(
                        "cannot reach reg-sub-reg edge in region inference \
                         post-processing"
                    ),
                }
            }
        }
    }

    fn bound_is_met(
        &self,
        bound: &VerifyBound<'tcx>,
        var_values: &LexicalRegionResolutions<'tcx>,
        generic_ty: Ty<'tcx>,
        min: ty::Region<'tcx>,
    ) -> bool {
        match bound {
            VerifyBound::IfEq(k, b) => {
                (var_values.normalize(self.region_rels.tcx, *k) == generic_ty)
                    && self.bound_is_met(b, var_values, generic_ty, min)
            }

            VerifyBound::OutlivedBy(r) => {
                self.sub_concrete_regions(min, var_values.normalize(self.tcx(), r))
            }

            VerifyBound::IsEmpty => {
                if let ty::ReEmpty(_) = min {
                    true
                } else {
                    false
                }
            }

            VerifyBound::AnyBound(bs) => {
                bs.iter().any(|b| self.bound_is_met(b, var_values, generic_ty, min))
            }

            VerifyBound::AllBounds(bs) => {
                bs.iter().all(|b| self.bound_is_met(b, var_values, generic_ty, min))
            }
        }
    }
}

impl<'tcx> fmt::Debug for RegionAndOrigin<'tcx> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "RegionAndOrigin({:?},{:?})", self.region, self.origin)
    }
}

impl<'tcx> LexicalRegionResolutions<'tcx> {
    fn normalize<T>(&self, tcx: TyCtxt<'tcx>, value: T) -> T
    where
        T: TypeFoldable<'tcx>,
    {
        tcx.fold_regions(value, &mut false, |r, _db| match r {
            ty::ReVar(rid) => self.resolve_var(*rid),
            _ => r,
        })
    }

    fn value(&self, rid: RegionVid) -> &VarValue<'tcx> {
        &self.values[rid]
    }

    fn value_mut(&mut self, rid: RegionVid) -> &mut VarValue<'tcx> {
        &mut self.values[rid]
    }

    pub fn resolve_var(&self, rid: RegionVid) -> ty::Region<'tcx> {
        let result = match self.values[rid] {
            VarValue::Value(r) => r,
            VarValue::ErrorValue => self.error_region,
        };
        debug!("resolve_var({:?}) = {:?}", rid, result);
        result
    }
}