Auto merge of #45538 - nikomatsakis:nll-liveness, r=pnkfelix

enable non-lexical lifetimes in the MIR borrow checker

This PR, joint work with @spastorino, fills out the NLL infrastructure and integrates it with the borrow checker. **Don't get too excited:** it includes still a number of hacks (the subtyping code is particularly hacky). However, it *does* kinda' work. =)

The final commit demonstrates this by including a test that -- with both the AST borrowck and MIR borrowck -- reports an error by default. But if you pass `-Znll`, you only get an error from the AST borrowck, demonstrating that the integration succeeds:

```
struct MyStruct {
    field: String
}

fn main() {
    let mut my_struct = MyStruct { field: format!("Hello") };

    let value = &my_struct.field;
    if value.is_empty() {
        my_struct.field.push_str("Hello, world!");
        //~^ ERROR cannot borrow (Ast)
    }
}
```

4 files changed, 54 insertions, 9 deletions

diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index fa4ee7c0092..e725592ff99 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -158,7 +158,7 @@ pub struct BlockRemainder {
 
 newtype_index!(FirstStatementIndex
     {
-        DEBUG_NAME = "",
+        DEBUG_FORMAT = "{}",
         MAX = SCOPE_DATA_REMAINDER_MAX,
     });
 
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index f5a3c1989cf..c4a33bb07cd 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -417,7 +417,7 @@ pub enum BorrowKind {
 
 newtype_index!(Local
     {
-        DEBUG_NAME = "_",
+        DEBUG_FORMAT = "_{}",
         const RETURN_POINTER = 0,
     });
 
@@ -553,7 +553,7 @@ pub struct UpvarDecl {
 ///////////////////////////////////////////////////////////////////////////
 // BasicBlock
 
-newtype_index!(BasicBlock { DEBUG_NAME = "bb" });
+newtype_index!(BasicBlock { DEBUG_FORMAT = "bb{}" });
 
 ///////////////////////////////////////////////////////////////////////////
 // BasicBlockData and Terminator
@@ -1135,7 +1135,7 @@ pub type LvalueProjection<'tcx> = Projection<'tcx, Lvalue<'tcx>, Local, Ty<'tcx>
 /// and the index is a local.
 pub type LvalueElem<'tcx> = ProjectionElem<'tcx, Local, Ty<'tcx>>;
 
-newtype_index!(Field { DEBUG_NAME = "field" });
+newtype_index!(Field { DEBUG_FORMAT = "field[{}]" });
 
 impl<'tcx> Lvalue<'tcx> {
     pub fn field(self, f: Field, ty: Ty<'tcx>) -> Lvalue<'tcx> {
@@ -1202,7 +1202,7 @@ impl<'tcx> Debug for Lvalue<'tcx> {
 
 newtype_index!(VisibilityScope
     {
-        DEBUG_NAME = "scope",
+        DEBUG_FORMAT = "scope[{}]",
         const ARGUMENT_VISIBILITY_SCOPE = 0,
     });
 
@@ -1529,7 +1529,7 @@ pub struct Constant<'tcx> {
     pub literal: Literal<'tcx>,
 }
 
-newtype_index!(Promoted { DEBUG_NAME = "promoted" });
+newtype_index!(Promoted { DEBUG_FORMAT = "promoted[{}]" });
 
 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub enum Literal<'tcx> {
@@ -1637,6 +1637,14 @@ impl fmt::Debug for Location {
 }
 
 impl Location {
+    /// Returns the location immediately after this one within the enclosing block.
+    ///
+    /// Note that if this location represents a terminator, then the
+    /// resulting location would be out of bounds and invalid.
+    pub fn successor_within_block(&self) -> Location {
+        Location { block: self.block, statement_index: self.statement_index + 1 }
+    }
+
     pub fn dominates(&self, other: &Location, dominators: &Dominators<BasicBlock>) -> bool {
         if self.block == other.block {
             self.statement_index <= other.statement_index
diff --git a/src/librustc/mir/transform.rs b/src/librustc/mir/transform.rs
index f29405e6650..6c90a5f38d0 100644
--- a/src/librustc/mir/transform.rs
+++ b/src/librustc/mir/transform.rs
@@ -39,13 +39,13 @@ pub enum MirSource {
     GeneratorDrop(NodeId),
 }
 
-impl<'a, 'tcx> MirSource {
-    pub fn from_local_def_id(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> MirSource {
+impl<'a, 'gcx, 'tcx> MirSource {
+    pub fn from_local_def_id(tcx: TyCtxt<'a, 'gcx, 'tcx>, def_id: DefId) -> MirSource {
         let id = tcx.hir.as_local_node_id(def_id).expect("mir source requires local def-id");
         Self::from_node(tcx, id)
     }
 
-    pub fn from_node(tcx: TyCtxt<'a, 'tcx, 'tcx>, id: NodeId) -> MirSource {
+    pub fn from_node(tcx: TyCtxt<'a, 'gcx, 'tcx>, id: NodeId) -> MirSource {
         use hir::*;
 
         // Handle constants in enum discriminants, types, and repeat expressions.
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index edd4329fa41..149999e0eee 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -218,6 +218,43 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     {
         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
     }
+
+    pub fn for_each_free_region<T,F>(self,
+                                     value: &T,
+                                     callback: F)
+        where F: FnMut(ty::Region<'tcx>),
+              T: TypeFoldable<'tcx>,
+    {
+        value.visit_with(&mut RegionVisitor { current_depth: 0, callback });
+
+        struct RegionVisitor<F> {
+            current_depth: u32,
+            callback: F,
+        }
+
+        impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<F>
+            where F : FnMut(ty::Region<'tcx>)
+        {
+            fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
+                self.current_depth += 1;
+                t.skip_binder().visit_with(self);
+                self.current_depth -= 1;
+
+                false // keep visiting
+            }
+
+            fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
+                match *r {
+                    ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => {
+                        /* ignore bound regions */
+                    }
+                    _ => (self.callback)(r),
+                }
+
+                false // keep visiting
+            }
+        }
+    }
 }
 
 /// Folds over the substructure of a type, visiting its component