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)
    }
}
```

2 files changed, 29 insertions, 18 deletions

diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index c790463e47a..c5ffb003399 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -53,11 +53,19 @@ pub struct IdxSet<T: Idx> {
 }
 
 impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
+    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
+        w.debug_list()
+         .entries(self.iter())
+         .finish()
+    }
 }
 
 impl<T: Idx> fmt::Debug for IdxSet<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) }
+    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
+        w.debug_list()
+         .entries(self.iter())
+         .finish()
+    }
 }
 
 impl<T: Idx> IdxSetBuf<T> {
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 1d1b367de20..0660cd96a4a 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -47,7 +47,7 @@ macro_rules! newtype_index {
         newtype_index!(
             @type[$name]
             @max[::std::u32::MAX]
-            @debug_name[unsafe {::std::intrinsics::type_name::<$name>() }]);
+            @debug_format["{}"]);
     );
 
     // Define any constants
@@ -55,14 +55,14 @@ macro_rules! newtype_index {
         newtype_index!(
             @type[$name]
             @max[::std::u32::MAX]
-            @debug_name[unsafe {::std::intrinsics::type_name::<$name>() }]
+            @debug_format["{}"]
             $($tokens)+);
     );
 
     // ---- private rules ----
 
     // Base case, user-defined constants (if any) have already been defined
-    (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]) => (
+    (@type[$type:ident] @max[$max:expr] @debug_format[$debug_format:expr]) => (
         #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord,
             RustcEncodable, RustcDecodable)]
         pub struct $type(pub u32);
@@ -79,40 +79,43 @@ macro_rules! newtype_index {
 
         impl ::std::fmt::Debug for $type {
             fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
-                write!(fmt, "{}{}", $debug_name, self.0)
+                write!(fmt, $debug_format, self.0)
             }
         }
     );
 
     // Rewrite final without comma to one that includes comma
-    (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]
+    (@type[$type:ident] @max[$max:expr] @debug_format[$debug_format:expr]
             $name:ident = $constant:expr) => (
-        newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $name = $constant,);
+        newtype_index!(@type[$type] @max[$max] @debug_format[$debug_format] $name = $constant,);
     );
 
     // Rewrite final const without comma to one that includes comma
-    (@type[$type:ident] @max[$_max:expr] @debug_name[$debug_name:expr]
+    (@type[$type:ident] @max[$_max:expr] @debug_format[$debug_format:expr]
             const $name:ident = $constant:expr) => (
-        newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] const $name = $constant,);
+        newtype_index!(@type[$type]
+                       @max[$max]
+                       @debug_format[$debug_format]
+                       const $name = $constant,);
     );
 
     // Replace existing default for max
-    (@type[$type:ident] @max[$_max:expr] @debug_name[$debug_name:expr]
+    (@type[$type:ident] @max[$_max:expr] @debug_format[$debug_format:expr]
             MAX = $max:expr, $($tokens:tt)*) => (
-        newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
+        newtype_index!(@type[$type] @max[$max] @debug_format[$debug_format] $($tokens)*);
     );
 
-    // Replace existing default for debug_name
-    (@type[$type:ident] @max[$max:expr] @debug_name[$_debug_name:expr]
-            DEBUG_NAME = $debug_name:expr, $($tokens:tt)*) => (
-        newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
+    // Replace existing default for debug_format
+    (@type[$type:ident] @max[$max:expr] @debug_format[$_debug_format:expr]
+            DEBUG_FORMAT = $debug_format:expr, $($tokens:tt)*) => (
+        newtype_index!(@type[$type] @max[$max] @debug_format[$debug_format] $($tokens)*);
     );
 
     // Assign a user-defined constant (as final param)
-    (@type[$type:ident] @max[$max:expr] @debug_name[$debug_name:expr]
+    (@type[$type:ident] @max[$max:expr] @debug_format[$debug_format:expr]
             const $name:ident = $constant:expr, $($tokens:tt)*) => (
         pub const $name: $type = $type($constant);
-        newtype_index!(@type[$type] @max[$max] @debug_name[$debug_name] $($tokens)*);
+        newtype_index!(@type[$type] @max[$max] @debug_format[$debug_format] $($tokens)*);
     );
 }