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

NLL: experiment with inverting liveness

I got inspired to see what would happen here.

Fixes #52460

r? @pnkfelix

3 files changed, 88 insertions, 2 deletions

diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index e54147cbe7c..9b7f4cec47b 100644
--- a/src/librustc_data_structures/graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -38,13 +38,13 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>(
 
     // compute the post order index (rank) for each node
     let mut post_order_rank: IndexVec<G::Node, usize> =
-        IndexVec::from_elem_n(usize::default(), graph.num_nodes());
+        (0..graph.num_nodes()).map(|_| 0).collect();
     for (index, node) in rpo.iter().rev().cloned().enumerate() {
         post_order_rank[node] = index;
     }
 
     let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> =
-        IndexVec::from_elem_n(Option::default(), graph.num_nodes());
+        (0..graph.num_nodes()).map(|_| None).collect();
     immediate_dominators[start_node] = Some(start_node);
 
     let mut changed = true;
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 533b7f5e0af..936dec92409 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -20,6 +20,8 @@
       html_favicon_url = "https://www.rust-lang.org/favicon.ico",
       html_root_url = "https://doc.rust-lang.org/nightly/")]
 
+#![feature(in_band_lifetimes)]
+#![feature(impl_header_lifetime_elision)]
 #![feature(unboxed_closures)]
 #![feature(fn_traits)]
 #![feature(unsize)]
@@ -86,6 +88,7 @@ pub mod thin_vec;
 pub mod transitive_relation;
 pub mod tuple_slice;
 pub use ena::unify;
+pub mod vec_linked_list;
 pub mod work_queue;
 pub mod fingerprint;
 
diff --git a/src/librustc_data_structures/vec_linked_list.rs b/src/librustc_data_structures/vec_linked_list.rs
new file mode 100644
index 00000000000..390dca6b905
--- /dev/null
+++ b/src/librustc_data_structures/vec_linked_list.rs
@@ -0,0 +1,83 @@
+// Copyright 2014 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 indexed_vec::{Idx, IndexVec};
+
+pub fn iter<Ls>(
+    first: Option<Ls::LinkIndex>,
+    links: &'a Ls,
+) -> impl Iterator<Item = Ls::LinkIndex> + 'a
+where
+    Ls: Links,
+{
+    VecLinkedListIterator {
+        links: links,
+        current: first,
+    }
+}
+
+pub struct VecLinkedListIterator<Ls>
+where
+    Ls: Links,
+{
+    links: Ls,
+    current: Option<Ls::LinkIndex>,
+}
+
+impl<Ls> Iterator for VecLinkedListIterator<Ls>
+where
+    Ls: Links,
+{
+    type Item = Ls::LinkIndex;
+
+    fn next(&mut self) -> Option<Ls::LinkIndex> {
+        if let Some(c) = self.current {
+            self.current = <Ls as Links>::next(&self.links, c);
+            Some(c)
+        } else {
+            None
+        }
+    }
+}
+
+pub trait Links {
+    type LinkIndex: Copy;
+
+    fn next(links: &Self, index: Self::LinkIndex) -> Option<Self::LinkIndex>;
+}
+
+impl<Ls> Links for &Ls
+where
+    Ls: Links,
+{
+    type LinkIndex = Ls::LinkIndex;
+
+    fn next(links: &Self, index: Ls::LinkIndex) -> Option<Ls::LinkIndex> {
+        <Ls as Links>::next(links, index)
+    }
+}
+
+pub trait LinkElem {
+    type LinkIndex: Copy;
+
+    fn next(elem: &Self) -> Option<Self::LinkIndex>;
+}
+
+impl<L, E> Links for IndexVec<L, E>
+where
+    E: LinkElem<LinkIndex = L>,
+    L: Idx,
+{
+    type LinkIndex = L;
+
+    fn next(links: &Self, index: L) -> Option<L> {
+        <E as LinkElem>::next(&links[index])
+    }
+}