diff options
6 files changed, 137 insertions, 67 deletions
diff --git a/src/librustc_mir/borrow_check/nll/constraint_set.rs b/src/librustc_mir/borrow_check/nll/constraint_set.rs new file mode 100644 index 00000000000..4c6e445293d --- /dev/null +++ b/src/librustc_mir/borrow_check/nll/constraint_set.rs @@ -0,0 +1,116 @@ +// Copyright 2017 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::mir::Location; +use rustc::ty::RegionVid; +use rustc_data_structures::indexed_vec::{Idx, IndexVec}; + +use std::fmt; +use syntax_pos::Span; +use std::ops::Deref; + +#[derive(Clone, Default)] +crate struct ConstraintSet { + constraints: IndexVec<ConstraintIndex, OutlivesConstraint>, +} + +impl ConstraintSet { + pub fn push(&mut self, constraint: OutlivesConstraint) { + debug!( + "add_outlives({:?}: {:?} @ {:?}", + constraint.sup, constraint.sub, constraint.point + ); + if constraint.sup == constraint.sub { + // 'a: 'a is pretty uninteresting + return; + } + self.constraints.push(constraint); + } + + /// Once all constraints have been added, `link()` is used to thread together the constraints + /// based on which would be affected when a particular region changes. See the next field of + /// `OutlivesContraint` for more details. + /// link returns a map that is needed later by `each_affected_by_dirty`. + pub fn link(&mut self, len: usize) -> IndexVec<RegionVid, Option<ConstraintIndex>> { + let mut map = IndexVec::from_elem_n(None, len); + + for (idx, constraint) in self.constraints.iter_enumerated_mut().rev() { + let mut head = &mut map[constraint.sub]; + debug_assert!(constraint.next.is_none()); + constraint.next = *head; + *head = Some(idx); + } + + map + } + + /// When a region R1 changes, we need to reprocess all constraints R2: R1 to take into account + /// any new elements that R1 now has. This method will quickly enumerate all such constraints + /// (that is, constraints where R1 is in the "subregion" position). + /// To use it, invoke with `map[R1]` where map is the map returned by `link`; + /// the callback op will be invoked for each affected constraint. + pub fn each_affected_by_dirty( + &self, + mut opt_dep_idx: Option<ConstraintIndex>, + mut op: impl FnMut(ConstraintIndex), + ) { + while let Some(dep_idx) = opt_dep_idx { + op(dep_idx); + opt_dep_idx = self.constraints[dep_idx].next; + } + } +} + +impl Deref for ConstraintSet { + type Target = IndexVec<ConstraintIndex, OutlivesConstraint>; + + fn deref(&self) -> &Self::Target { &self.constraints } +} + +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct OutlivesConstraint { + // NB. The ordering here is not significant for correctness, but + // it is for convenience. Before we dump the constraints in the + // debugging logs, we sort them, and we'd like the "super region" + // to be first, etc. (In particular, span should remain last.) + /// The region SUP must outlive SUB... + pub sup: RegionVid, + + /// Region that must be outlived. + pub sub: RegionVid, + + /// At this location. + pub point: Location, + + /// Later on, we thread the constraints onto a linked list + /// grouped by their `sub` field. So if you had: + /// + /// Index | Constraint | Next Field + /// ----- | ---------- | ---------- + /// 0 | `'a: 'b` | Some(2) + /// 1 | `'b: 'c` | None + /// 2 | `'c: 'b` | None + pub next: Option<ConstraintIndex>, + + /// Where did this constraint arise? + pub span: Span, +} + +impl fmt::Debug for OutlivesConstraint { + fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + write!( + formatter, + "({:?}: {:?} @ {:?}) due to {:?}", + self.sup, self.sub, self.point, self.span + ) + } +} + +newtype_index!(ConstraintIndex { DEBUG_FORMAT = "ConstraintIndex({})" }); diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index e26665e8291..07b160ed66f 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -45,6 +45,8 @@ mod renumber; crate mod type_check; mod universal_regions; +crate mod constraint_set; + use self::facts::AllFacts; use self::region_infer::RegionInferenceContext; use self::universal_regions::UniversalRegions; diff --git a/src/librustc_mir/borrow_check/nll/region_infer/graphviz.rs b/src/librustc_mir/borrow_check/nll/region_infer/graphviz.rs index c02e4ff3156..106dd003cea 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/graphviz.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/graphviz.rs @@ -17,6 +17,8 @@ use rustc_data_structures::indexed_vec::Idx; use std::borrow::Cow; use std::io::{self, Write}; use super::*; +use borrow_check::nll::constraint_set::OutlivesConstraint; + impl<'tcx> RegionInferenceContext<'tcx> { /// Write out the region constraint graph. diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs index 2e1f7fc9e70..a576dc5f7f4 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -10,6 +10,7 @@ use super::universal_regions::UniversalRegions; use borrow_check::nll::region_infer::values::ToElementIndex; +use borrow_check::nll::constraint_set::{ConstraintIndex, ConstraintSet, OutlivesConstraint}; use rustc::hir::def_id::DefId; use rustc::infer::canonical::QueryRegionConstraint; use rustc::infer::error_reporting::nice_region_error::NiceRegionError; @@ -25,7 +26,6 @@ use rustc::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable}; use rustc::util::common::{self, ErrorReported}; use rustc_data_structures::bitvec::BitVector; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; -use std::fmt; use std::rc::Rc; use syntax_pos::Span; @@ -65,7 +65,7 @@ pub struct RegionInferenceContext<'tcx> { dependency_map: Option<IndexVec<RegionVid, Option<ConstraintIndex>>>, /// The constraints we have accumulated and used during solving. - constraints: IndexVec<ConstraintIndex, OutlivesConstraint>, + constraints: ConstraintSet, /// Type constraints that we check after solving. type_tests: Vec<TypeTest<'tcx>>, @@ -114,37 +114,6 @@ pub(crate) enum Cause { UniversalRegion(RegionVid), } -#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub struct OutlivesConstraint { - // NB. The ordering here is not significant for correctness, but - // it is for convenience. Before we dump the constraints in the - // debugging logs, we sort them, and we'd like the "super region" - // to be first, etc. (In particular, span should remain last.) - /// The region SUP must outlive SUB... - pub sup: RegionVid, - - /// Region that must be outlived. - pub sub: RegionVid, - - /// At this location. - pub point: Location, - - /// Later on, we thread the constraints onto a linked list - /// grouped by their `sub` field. So if you had: - /// - /// Index | Constraint | Next Field - /// ----- | ---------- | ---------- - /// 0 | `'a: 'b` | Some(2) - /// 1 | `'b: 'c` | None - /// 2 | `'c: 'b` | None - pub next: Option<ConstraintIndex>, - - /// Where did this constraint arise? - pub span: Span, -} - -newtype_index!(ConstraintIndex { DEBUG_FORMAT = "ConstraintIndex({})" }); - /// A "type test" corresponds to an outlives constraint between a type /// and a lifetime, like `T: 'x` or `<T as Foo>::Bar: 'x`. They are /// translated from the `Verify` region constraints in the ordinary @@ -243,7 +212,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { var_infos: VarInfos, universal_regions: UniversalRegions<'tcx>, mir: &Mir<'tcx>, - outlives_constraints: Vec<OutlivesConstraint>, + outlives_constraints: ConstraintSet, type_tests: Vec<TypeTest<'tcx>>, ) -> Self { // The `next` field should not yet have been initialized: @@ -266,7 +235,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { liveness_constraints: RegionValues::new(elements, num_region_variables), inferred_values: None, dependency_map: None, - constraints: IndexVec::from_raw(outlives_constraints), + constraints: outlives_constraints, type_tests, universal_regions, }; @@ -392,7 +361,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { sub: RegionVid, point: Location, ) { - debug!("add_outlives({:?}: {:?} @ {:?}", sup, sub, point); assert!(self.inferred_values.is_none(), "values already inferred"); self.constraints.push(OutlivesConstraint { span, @@ -400,7 +368,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { sub, point, next: None, - }); + }) } /// Perform region inference and report errors if we see any @@ -498,13 +466,11 @@ impl<'tcx> RegionInferenceContext<'tcx> { debug!("propagate_constraints: sub={:?}", constraint.sub); debug!("propagate_constraints: sup={:?}", constraint.sup); - let mut opt_dep_idx = dependency_map[constraint.sup]; - while let Some(dep_idx) = opt_dep_idx { + self.constraints.each_affected_by_dirty(dependency_map[constraint.sup], |dep_idx| { if clean_bit_vec.remove(dep_idx.index()) { dirty_list.push(dep_idx); } - opt_dep_idx = self.constraints[dep_idx].next; - } + }); } debug!("\n"); @@ -518,16 +484,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { /// These are constraints like Y: X @ P -- so if X changed, we may /// need to grow Y. fn build_dependency_map(&mut self) -> IndexVec<RegionVid, Option<ConstraintIndex>> { - let mut map = IndexVec::from_elem(None, &self.definitions); - - for (idx, constraint) in self.constraints.iter_enumerated_mut().rev() { - let mut head = &mut map[constraint.sub]; - debug_assert!(constraint.next.is_none()); - constraint.next = *head; - *head = Some(idx); - } - - map + self.constraints.link(self.definitions.len()) } /// Once regions have been propagated, this method is used to see @@ -1115,7 +1072,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { while changed { changed = false; - for constraint in &self.constraints { + for constraint in self.constraints.iter() { if let Some(n) = result_set[constraint.sup] { let m = n + 1; if result_set[constraint.sub] @@ -1146,16 +1103,6 @@ impl<'tcx> RegionDefinition<'tcx> { } } -impl fmt::Debug for OutlivesConstraint { - fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { - write!( - formatter, - "({:?}: {:?} @ {:?}) due to {:?}", - self.sup, self.sub, self.point, self.span - ) - } -} - pub trait ClosureRegionRequirementsExt<'gcx, 'tcx> { fn apply_requirements( &self, diff --git a/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs b/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs index 900899b9cde..3100df3e8f6 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs @@ -9,10 +9,12 @@ // except according to those terms. use borrow_check::location::LocationTable; +use borrow_check::nll::constraint_set::OutlivesConstraint; use borrow_check::nll::facts::AllFacts; -use borrow_check::nll::region_infer::{OutlivesConstraint, RegionTest, TypeTest}; +use borrow_check::nll::region_infer::{RegionTest, TypeTest}; use borrow_check::nll::type_check::Locations; use borrow_check::nll::universal_regions::UniversalRegions; +use borrow_check::nll::constraint_set::ConstraintSet; use rustc::infer::canonical::QueryRegionConstraint; use rustc::infer::outlives::obligations::{TypeOutlives, TypeOutlivesDelegate}; use rustc::infer::region_constraints::{GenericKind, VerifyBound}; @@ -31,7 +33,7 @@ crate struct ConstraintConversion<'a, 'gcx: 'tcx, 'tcx: 'a> { implicit_region_bound: Option<ty::Region<'tcx>>, param_env: ty::ParamEnv<'tcx>, locations: Locations, - outlives_constraints: &'a mut Vec<OutlivesConstraint>, + outlives_constraints: &'a mut ConstraintSet, type_tests: &'a mut Vec<TypeTest<'tcx>>, all_facts: &'a mut Option<AllFacts>, } @@ -46,7 +48,7 @@ impl<'a, 'gcx, 'tcx> ConstraintConversion<'a, 'gcx, 'tcx> { implicit_region_bound: Option<ty::Region<'tcx>>, param_env: ty::ParamEnv<'tcx>, locations: Locations, - outlives_constraints: &'a mut Vec<OutlivesConstraint>, + outlives_constraints: &'a mut ConstraintSet, type_tests: &'a mut Vec<TypeTest<'tcx>>, all_facts: &'a mut Option<AllFacts>, ) -> Self { diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs index 9b6e3e0cab6..611050a4060 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -12,9 +12,10 @@ #![allow(unreachable_code)] use borrow_check::location::LocationTable; +use borrow_check::nll::constraint_set::ConstraintSet; use borrow_check::nll::facts::AllFacts; use borrow_check::nll::region_infer::Cause; -use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, OutlivesConstraint, TypeTest}; +use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest}; use borrow_check::nll::universal_regions::UniversalRegions; use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; @@ -621,7 +622,7 @@ crate struct MirTypeckRegionConstraints<'tcx> { /// hence it must report on their liveness constraints. crate liveness_set: Vec<(ty::Region<'tcx>, Location, Cause)>, - crate outlives_constraints: Vec<OutlivesConstraint>, + crate outlives_constraints: ConstraintSet, crate type_tests: Vec<TypeTest<'tcx>>, } |