Merge remote-tracking branch 'origin/master' into mpk/add-long-error-message-for-E0311

5 files changed, 195 insertions, 148 deletions

diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs
index 265f45b72d1..c8b09cffe01 100644
--- a/compiler/rustc_data_structures/src/lib.rs
+++ b/compiler/rustc_data_structures/src/lib.rs
@@ -28,6 +28,8 @@
 #![feature(vec_into_raw_parts)]
 #![allow(rustc::default_hash_types)]
 #![allow(rustc::potential_query_instability)]
+#![deny(rustc::untranslatable_diagnostic)]
+#![deny(rustc::diagnostic_outside_of_impl)]
 
 #[macro_use]
 extern crate tracing;
diff --git a/compiler/rustc_data_structures/src/map_in_place.rs b/compiler/rustc_data_structures/src/map_in_place.rs
index 874de03d37a..d912211443a 100644
--- a/compiler/rustc_data_structures/src/map_in_place.rs
+++ b/compiler/rustc_data_structures/src/map_in_place.rs
@@ -1,3 +1,4 @@
+use crate::thin_vec::ThinVec;
 use smallvec::{Array, SmallVec};
 use std::ptr;
 
@@ -15,94 +16,64 @@ pub trait MapInPlace<T>: Sized {
         I: IntoIterator<Item = T>;
 }
 
-impl<T> MapInPlace<T> for Vec<T> {
-    fn flat_map_in_place<F, I>(&mut self, mut f: F)
-    where
-        F: FnMut(T) -> I,
-        I: IntoIterator<Item = T>,
-    {
-        let mut read_i = 0;
-        let mut write_i = 0;
-        unsafe {
-            let mut old_len = self.len();
-            self.set_len(0); // make sure we just leak elements in case of panic
+// The implementation of this method is syntactically identical for all the
+// different vector types.
+macro_rules! flat_map_in_place {
+    () => {
+        fn flat_map_in_place<F, I>(&mut self, mut f: F)
+        where
+            F: FnMut(T) -> I,
+            I: IntoIterator<Item = T>,
+        {
+            let mut read_i = 0;
+            let mut write_i = 0;
+            unsafe {
+                let mut old_len = self.len();
+                self.set_len(0); // make sure we just leak elements in case of panic
 
-            while read_i < old_len {
-                // move the read_i'th item out of the vector and map it
-                // to an iterator
-                let e = ptr::read(self.as_ptr().add(read_i));
-                let iter = f(e).into_iter();
-                read_i += 1;
+                while read_i < old_len {
+                    // move the read_i'th item out of the vector and map it
+                    // to an iterator
+                    let e = ptr::read(self.as_ptr().add(read_i));
+                    let iter = f(e).into_iter();
+                    read_i += 1;
 
-                for e in iter {
-                    if write_i < read_i {
-                        ptr::write(self.as_mut_ptr().add(write_i), e);
-                        write_i += 1;
-                    } else {
-                        // If this is reached we ran out of space
-                        // in the middle of the vector.
-                        // However, the vector is in a valid state here,
-                        // so we just do a somewhat inefficient insert.
-                        self.set_len(old_len);
-                        self.insert(write_i, e);
+                    for e in iter {
+                        if write_i < read_i {
+                            ptr::write(self.as_mut_ptr().add(write_i), e);
+                            write_i += 1;
+                        } else {
+                            // If this is reached we ran out of space
+                            // in the middle of the vector.
+                            // However, the vector is in a valid state here,
+                            // so we just do a somewhat inefficient insert.
+                            self.set_len(old_len);
+                            self.insert(write_i, e);
 
-                        old_len = self.len();
-                        self.set_len(0);
+                            old_len = self.len();
+                            self.set_len(0);
 
-                        read_i += 1;
-                        write_i += 1;
+                            read_i += 1;
+                            write_i += 1;
+                        }
                     }
                 }
-            }
 
-            // write_i tracks the number of actually written new items.
-            self.set_len(write_i);
+                // write_i tracks the number of actually written new items.
+                self.set_len(write_i);
+            }
         }
-    }
+    };
 }
 
-impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> {
-    fn flat_map_in_place<F, I>(&mut self, mut f: F)
-    where
-        F: FnMut(T) -> I,
-        I: IntoIterator<Item = T>,
-    {
-        let mut read_i = 0;
-        let mut write_i = 0;
-        unsafe {
-            let mut old_len = self.len();
-            self.set_len(0); // make sure we just leak elements in case of panic
-
-            while read_i < old_len {
-                // move the read_i'th item out of the vector and map it
-                // to an iterator
-                let e = ptr::read(self.as_ptr().add(read_i));
-                let iter = f(e).into_iter();
-                read_i += 1;
-
-                for e in iter {
-                    if write_i < read_i {
-                        ptr::write(self.as_mut_ptr().add(write_i), e);
-                        write_i += 1;
-                    } else {
-                        // If this is reached we ran out of space
-                        // in the middle of the vector.
-                        // However, the vector is in a valid state here,
-                        // so we just do a somewhat inefficient insert.
-                        self.set_len(old_len);
-                        self.insert(write_i, e);
-
-                        old_len = self.len();
-                        self.set_len(0);
+impl<T> MapInPlace<T> for Vec<T> {
+    flat_map_in_place!();
+}
 
-                        read_i += 1;
-                        write_i += 1;
-                    }
-                }
-            }
+impl<T, A: Array<Item = T>> MapInPlace<T> for SmallVec<A> {
+    flat_map_in_place!();
+}
 
-            // write_i tracks the number of actually written new items.
-            self.set_len(write_i);
-        }
-    }
+impl<T> MapInPlace<T> for ThinVec<T> {
+    flat_map_in_place!();
 }
diff --git a/compiler/rustc_data_structures/src/thin_vec.rs b/compiler/rustc_data_structures/src/thin_vec.rs
index 716259142d1..fce42e709ab 100644
--- a/compiler/rustc_data_structures/src/thin_vec.rs
+++ b/compiler/rustc_data_structures/src/thin_vec.rs
@@ -27,6 +27,51 @@ impl<T> ThinVec<T> {
             ThinVec(None) => *self = vec![item].into(),
         }
     }
+
+    /// Note: if `set_len(0)` is called on a non-empty `ThinVec`, it will
+    /// remain in the `Some` form. This is required for some code sequences
+    /// (such as the one in `flat_map_in_place`) that call `set_len(0)` before
+    /// an operation that might panic, and then call `set_len(n)` again
+    /// afterwards.
+    pub unsafe fn set_len(&mut self, new_len: usize) {
+        match *self {
+            ThinVec(None) => {
+                // A prerequisite of `Vec::set_len` is that `new_len` must be
+                // less than or equal to capacity(). The same applies here.
+                if new_len != 0 {
+                    panic!("unsafe ThinVec::set_len({})", new_len);
+                }
+            }
+            ThinVec(Some(ref mut vec)) => vec.set_len(new_len),
+        }
+    }
+
+    pub fn insert(&mut self, index: usize, value: T) {
+        match *self {
+            ThinVec(None) => {
+                if index == 0 {
+                    *self = vec![value].into();
+                } else {
+                    panic!("invalid ThinVec::insert");
+                }
+            }
+            ThinVec(Some(ref mut vec)) => vec.insert(index, value),
+        }
+    }
+
+    pub fn remove(&mut self, index: usize) -> T {
+        match self {
+            ThinVec(None) => panic!("invalid ThinVec::remove"),
+            ThinVec(Some(vec)) => vec.remove(index),
+        }
+    }
+
+    pub fn as_slice(&self) -> &[T] {
+        match self {
+            ThinVec(None) => &[],
+            ThinVec(Some(vec)) => vec.as_slice(),
+        }
+    }
 }
 
 impl<T> From<Vec<T>> for ThinVec<T> {
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs
index 0ff64969b07..f016c391fe7 100644
--- a/compiler/rustc_data_structures/src/transitive_relation.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation.rs
@@ -1,45 +1,57 @@
+use crate::frozen::Frozen;
 use crate::fx::FxIndexSet;
-use crate::sync::Lock;
 use rustc_index::bit_set::BitMatrix;
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::mem;
+use std::ops::Deref;
 
 #[cfg(test)]
 mod tests;
 
 #[derive(Clone, Debug)]
-pub struct TransitiveRelation<T> {
+pub struct TransitiveRelationBuilder<T> {
     // List of elements. This is used to map from a T to a usize.
     elements: FxIndexSet<T>,
 
     // List of base edges in the graph. Require to compute transitive
     // closure.
     edges: Vec<Edge>,
+}
+
+#[derive(Debug)]
+pub struct TransitiveRelation<T> {
+    // Frozen transitive relation elements and edges.
+    builder: Frozen<TransitiveRelationBuilder<T>>,
 
-    // This is a cached transitive closure derived from the edges.
-    // Currently, we build it lazily and just throw out any existing
-    // copy whenever a new edge is added. (The Lock is to permit
-    // the lazy computation.) This is kind of silly, except for the
-    // fact its size is tied to `self.elements.len()`, so I wanted to
-    // wait before building it up to avoid reallocating as new edges
-    // are added with new elements. Perhaps better would be to ask the
-    // user for a batch of edges to minimize this effect, but I
-    // already wrote the code this way. :P -nmatsakis
-    closure: Lock<Option<BitMatrix<usize, usize>>>,
+    // Cached transitive closure derived from the edges.
+    closure: Frozen<BitMatrix<usize, usize>>,
 }
 
-// HACK(eddyb) manual impl avoids `Default` bound on `T`.
-impl<T: Eq + Hash> Default for TransitiveRelation<T> {
-    fn default() -> Self {
+impl<T> Deref for TransitiveRelation<T> {
+    type Target = Frozen<TransitiveRelationBuilder<T>>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.builder
+    }
+}
+
+impl<T: Clone> Clone for TransitiveRelation<T> {
+    fn clone(&self) -> Self {
         TransitiveRelation {
-            elements: Default::default(),
-            edges: Default::default(),
-            closure: Default::default(),
+            builder: Frozen::freeze(self.builder.deref().clone()),
+            closure: Frozen::freeze(self.closure.deref().clone()),
         }
     }
 }
 
+// HACK(eddyb) manual impl avoids `Default` bound on `T`.
+impl<T: Eq + Hash> Default for TransitiveRelationBuilder<T> {
+    fn default() -> Self {
+        TransitiveRelationBuilder { elements: Default::default(), edges: Default::default() }
+    }
+}
+
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Debug)]
 struct Index(usize);
 
@@ -49,7 +61,7 @@ struct Edge {
     target: Index,
 }
 
-impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
+impl<T: Eq + Hash + Copy> TransitiveRelationBuilder<T> {
     pub fn is_empty(&self) -> bool {
         self.edges.is_empty()
     }
@@ -63,23 +75,19 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
     }
 
     fn add_index(&mut self, a: T) -> Index {
-        let (index, added) = self.elements.insert_full(a);
-        if added {
-            // if we changed the dimensions, clear the cache
-            *self.closure.get_mut() = None;
-        }
+        let (index, _added) = self.elements.insert_full(a);
         Index(index)
     }
 
     /// Applies the (partial) function to each edge and returns a new
-    /// relation. If `f` returns `None` for any end-point, returns
-    /// `None`.
-    pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelation<U>>
+    /// relation builder. If `f` returns `None` for any end-point,
+    /// returns `None`.
+    pub fn maybe_map<F, U>(&self, mut f: F) -> Option<TransitiveRelationBuilder<U>>
     where
         F: FnMut(T) -> Option<U>,
         U: Clone + Debug + Eq + Hash + Copy,
     {
-        let mut result = TransitiveRelation::default();
+        let mut result = TransitiveRelationBuilder::default();
         for edge in &self.edges {
             result.add(f(self.elements[edge.source.0])?, f(self.elements[edge.target.0])?);
         }
@@ -93,10 +101,38 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
         let edge = Edge { source: a, target: b };
         if !self.edges.contains(&edge) {
             self.edges.push(edge);
+        }
+    }
+
+    /// Compute the transitive closure derived from the edges, and converted to
+    /// the final result. After this, all elements will be immutable to maintain
+    /// the correctness of the result.
+    pub fn freeze(self) -> TransitiveRelation<T> {
+        let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
+        let mut changed = true;
+        while changed {
+            changed = false;
+            for edge in &self.edges {
+                // add an edge from S -> T
+                changed |= matrix.insert(edge.source.0, edge.target.0);
 
-            // added an edge, clear the cache
-            *self.closure.get_mut() = None;
+                // add all outgoing edges from T into S
+                changed |= matrix.union_rows(edge.target.0, edge.source.0);
+            }
         }
+        TransitiveRelation { builder: Frozen::freeze(self), closure: Frozen::freeze(matrix) }
+    }
+}
+
+impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
+    /// Applies the (partial) function to each edge and returns a new
+    /// relation including transitive closures.
+    pub fn maybe_map<F, U>(&self, f: F) -> Option<TransitiveRelation<U>>
+    where
+        F: FnMut(T) -> Option<U>,
+        U: Clone + Debug + Eq + Hash + Copy,
+    {
+        Some(self.builder.maybe_map(f)?.freeze())
     }
 
     /// Checks whether `a < target` (transitively)
@@ -322,30 +358,7 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
     where
         OP: FnOnce(&BitMatrix<usize, usize>) -> R,
     {
-        let mut closure_cell = self.closure.borrow_mut();
-        let mut closure = closure_cell.take();
-        if closure.is_none() {
-            closure = Some(self.compute_closure());
-        }
-        let result = op(closure.as_ref().unwrap());
-        *closure_cell = closure;
-        result
-    }
-
-    fn compute_closure(&self) -> BitMatrix<usize, usize> {
-        let mut matrix = BitMatrix::new(self.elements.len(), self.elements.len());
-        let mut changed = true;
-        while changed {
-            changed = false;
-            for edge in &self.edges {
-                // add an edge from S -> T
-                changed |= matrix.insert(edge.source.0, edge.target.0);
-
-                // add all outgoing edges from T into S
-                changed |= matrix.union_rows(edge.target.0, edge.source.0);
-            }
-        }
-        matrix
+        op(&self.closure)
     }
 
     /// Lists all the base edges in the graph: the initial _non-transitive_ set of element
diff --git a/compiler/rustc_data_structures/src/transitive_relation/tests.rs b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
index e1f4c7ee073..e756c546e41 100644
--- a/compiler/rustc_data_structures/src/transitive_relation/tests.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
@@ -10,9 +10,10 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
 
 #[test]
 fn test_one_step() {
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "b");
     relation.add("a", "c");
+    let relation = relation.freeze();
     assert!(relation.contains("a", "c"));
     assert!(relation.contains("a", "b"));
     assert!(!relation.contains("b", "a"));
@@ -21,7 +22,7 @@ fn test_one_step() {
 
 #[test]
 fn test_many_steps() {
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "b");
     relation.add("a", "c");
     relation.add("a", "f");
@@ -31,6 +32,7 @@ fn test_many_steps() {
     relation.add("b", "e");
 
     relation.add("e", "g");
+    let relation = relation.freeze();
 
     assert!(relation.contains("a", "b"));
     assert!(relation.contains("a", "c"));
@@ -51,9 +53,10 @@ fn mubs_triangle() {
     //      ^
     //      |
     //      b
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "tcx");
     relation.add("b", "tcx");
+    let relation = relation.freeze();
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["tcx"]);
     assert_eq!(relation.parents("a"), vec!["tcx"]);
     assert_eq!(relation.parents("b"), vec!["tcx"]);
@@ -72,7 +75,7 @@ fn mubs_best_choice1() {
     // need the second pare down call to get the right result (after
     // intersection, we have [1, 2], but 2 -> 1).
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -80,6 +83,7 @@ fn mubs_best_choice1() {
 
     relation.add("3", "1");
     relation.add("3", "2");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["2"]);
     assert_eq!(relation.parents("0"), vec!["2"]);
@@ -99,7 +103,7 @@ fn mubs_best_choice2() {
     // Like the preceding test, but in this case intersection is [2,
     // 1], and hence we rely on the first pare down call.
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -107,6 +111,7 @@ fn mubs_best_choice2() {
 
     relation.add("3", "1");
     relation.add("3", "2");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
     assert_eq!(relation.parents("0"), vec!["1"]);
@@ -118,12 +123,13 @@ fn mubs_best_choice2() {
 fn mubs_no_best_choice() {
     // in this case, the intersection yields [1, 2], and the "pare
     // down" calls find nothing to remove.
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
     relation.add("3", "1");
     relation.add("3", "2");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1", "2"]);
     assert_eq!(relation.parents("0"), vec!["1", "2"]);
@@ -135,7 +141,7 @@ fn mubs_best_choice_scc() {
     // in this case, 1 and 2 form a cycle; we pick arbitrarily (but
     // consistently).
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("0", "1");
     relation.add("0", "2");
 
@@ -144,6 +150,7 @@ fn mubs_best_choice_scc() {
 
     relation.add("3", "1");
     relation.add("3", "2");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("0", "3"), vec!["1"]);
     assert_eq!(relation.parents("0"), vec!["1"]);
@@ -157,13 +164,14 @@ fn pdub_crisscross() {
     //   /\       |
     // b -> b1 ---+
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "a1");
     relation.add("a", "b1");
     relation.add("b", "a1");
     relation.add("b", "b1");
     relation.add("a1", "x");
     relation.add("b1", "x");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
     assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
@@ -179,7 +187,7 @@ fn pdub_crisscross_more() {
     //   /\    /\             |
     // b -> b1 -> b2 ---------+
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "a1");
     relation.add("a", "b1");
     relation.add("b", "a1");
@@ -194,6 +202,7 @@ fn pdub_crisscross_more() {
 
     relation.add("a3", "x");
     relation.add("b2", "x");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["a1", "b1"]);
     assert_eq!(relation.minimal_upper_bounds("a1", "b1"), vec!["a2", "b2"]);
@@ -210,11 +219,12 @@ fn pdub_lub() {
     //            |
     // b -> b1 ---+
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "a1");
     relation.add("b", "b1");
     relation.add("a1", "x");
     relation.add("b1", "x");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["x"]);
     assert_eq!(relation.postdom_upper_bound("a", "b"), Some("x"));
@@ -233,10 +243,11 @@ fn mubs_intermediate_node_on_one_side_only() {
     //           b
 
     // "digraph { a -> c -> d; b -> d; }",
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("b", "d");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["d"]);
 }
@@ -252,12 +263,13 @@ fn mubs_scc_1() {
     //           b
 
     // "digraph { a -> c -> d; d -> c; a -> d; b -> d; }",
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "c");
     relation.add("a", "d");
     relation.add("b", "d");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
 }
@@ -272,12 +284,13 @@ fn mubs_scc_2() {
     //      +--- b
 
     // "digraph { a -> c -> d; d -> c; b -> d; b -> c; }",
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "c");
     relation.add("b", "d");
     relation.add("b", "c");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
 }
@@ -292,13 +305,14 @@ fn mubs_scc_3() {
     //           b ---+
 
     // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "e");
     relation.add("e", "c");
     relation.add("b", "d");
     relation.add("b", "e");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
 }
@@ -314,13 +328,14 @@ fn mubs_scc_4() {
     //           b ---+
 
     // "digraph { a -> c -> d -> e -> c; a -> d; b -> e; }"
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     relation.add("a", "c");
     relation.add("c", "d");
     relation.add("d", "e");
     relation.add("e", "c");
     relation.add("a", "d");
     relation.add("b", "e");
+    let relation = relation.freeze();
 
     assert_eq!(relation.minimal_upper_bounds("a", "b"), vec!["c"]);
 }
@@ -352,10 +367,11 @@ fn parent() {
         (1, /*->*/ 3),
     ];
 
-    let mut relation = TransitiveRelation::default();
+    let mut relation = TransitiveRelationBuilder::default();
     for (a, b) in pairs {
         relation.add(a, b);
     }
+    let relation = relation.freeze();
 
     let p = relation.postdom_parent(3);
     assert_eq!(p, Some(0));