Merge remote-tracking branch 'upstream/master'

39 files changed, 70 insertions, 582 deletions

diff --git a/src/librustc_data_structures/base_n.rs b/src/librustc_data_structures/base_n.rs
index d3b47daa5b4..c9c1933f25b 100644
--- a/src/librustc_data_structures/base_n.rs
+++ b/src/librustc_data_structures/base_n.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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.
-
 /// Convert unsigned integers into a string representation with some base.
 /// Bases up to and including 36 can be used for case-insensitive things.
 
diff --git a/src/librustc_data_structures/bit_set.rs b/src/librustc_data_structures/bit_set.rs
index 28aad49b09b..8adfe3749af 100644
--- a/src/librustc_data_structures/bit_set.rs
+++ b/src/librustc_data_structures/bit_set.rs
@@ -1,13 +1,3 @@
-// Copyright 2015 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};
 use smallvec::SmallVec;
 use std::fmt;
diff --git a/src/librustc_data_structures/const_cstr.rs b/src/librustc_data_structures/const_cstr.rs
index 4589d973b6a..fbe2f29f706 100644
--- a/src/librustc_data_structures/const_cstr.rs
+++ b/src/librustc_data_structures/const_cstr.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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.
-
 /// This macro creates a zero-overhead &CStr by adding a NUL terminator to
 /// the string literal passed into it at compile-time. Use it like:
 ///
diff --git a/src/librustc_data_structures/fingerprint.rs b/src/librustc_data_structures/fingerprint.rs
index f8638213b3a..2e596ca3e44 100644
--- a/src/librustc_data_structures/fingerprint.rs
+++ b/src/librustc_data_structures/fingerprint.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 std::mem;
 use stable_hasher;
 use serialize;
diff --git a/src/librustc_data_structures/flock.rs b/src/librustc_data_structures/flock.rs
index 86e48e21626..2dea249f1c0 100644
--- a/src/librustc_data_structures/flock.rs
+++ b/src/librustc_data_structures/flock.rs
@@ -1,13 +1,3 @@
-// Copyright 2014-2015 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.
-
 //! Simple file-locking apis for each OS.
 //!
 //! This is not meant to be in the standard library, it does nothing with
@@ -41,12 +31,6 @@ cfg_if! {
                 // not actually here, but brings in line with freebsd
                 pub l_sysid: libc::c_int,
             }
-
-            pub const F_RDLCK: libc::c_short = 0;
-            pub const F_WRLCK: libc::c_short = 1;
-            pub const F_UNLCK: libc::c_short = 2;
-            pub const F_SETLK: libc::c_int = 6;
-            pub const F_SETLKW: libc::c_int = 7;
         }
 
         #[cfg(target_os = "freebsd")]
@@ -62,12 +46,6 @@ cfg_if! {
                 pub l_whence: libc::c_short,
                 pub l_sysid: libc::c_int,
             }
-
-            pub const F_RDLCK: libc::c_short = 1;
-            pub const F_UNLCK: libc::c_short = 2;
-            pub const F_WRLCK: libc::c_short = 3;
-            pub const F_SETLK: libc::c_int = 12;
-            pub const F_SETLKW: libc::c_int = 13;
         }
 
         #[cfg(any(target_os = "dragonfly",
@@ -88,12 +66,6 @@ cfg_if! {
                 // not actually here, but brings in line with freebsd
                 pub l_sysid: libc::c_int,
             }
-
-            pub const F_RDLCK: libc::c_short = 1;
-            pub const F_UNLCK: libc::c_short = 2;
-            pub const F_WRLCK: libc::c_short = 3;
-            pub const F_SETLK: libc::c_int = 8;
-            pub const F_SETLKW: libc::c_int = 9;
         }
 
         #[cfg(target_os = "haiku")]
@@ -111,12 +83,6 @@ cfg_if! {
                 // not actually here, but brings in line with freebsd
                 pub l_sysid: libc::c_int,
             }
-
-            pub const F_RDLCK: libc::c_short = 0x0040;
-            pub const F_UNLCK: libc::c_short = 0x0200;
-            pub const F_WRLCK: libc::c_short = 0x0400;
-            pub const F_SETLK: libc::c_int = 0x0080;
-            pub const F_SETLKW: libc::c_int = 0x0100;
         }
 
         #[cfg(any(target_os = "macos", target_os = "ios"))]
@@ -134,12 +100,6 @@ cfg_if! {
                 // not actually here, but brings in line with freebsd
                 pub l_sysid: libc::c_int,
             }
-
-            pub const F_RDLCK: libc::c_short = 1;
-            pub const F_UNLCK: libc::c_short = 2;
-            pub const F_WRLCK: libc::c_short = 3;
-            pub const F_SETLK: libc::c_int = 8;
-            pub const F_SETLKW: libc::c_int = 9;
         }
 
         #[cfg(target_os = "solaris")]
@@ -155,12 +115,6 @@ cfg_if! {
                 pub l_sysid: libc::c_int,
                 pub l_pid: libc::pid_t,
             }
-
-            pub const F_RDLCK: libc::c_short = 1;
-            pub const F_WRLCK: libc::c_short = 2;
-            pub const F_UNLCK: libc::c_short = 3;
-            pub const F_SETLK: libc::c_int = 6;
-            pub const F_SETLKW: libc::c_int = 7;
         }
 
         #[derive(Debug)]
@@ -192,9 +146,9 @@ cfg_if! {
                 }
 
                 let lock_type = if exclusive {
-                    os::F_WRLCK
+                    libc::F_WRLCK as libc::c_short
                 } else {
-                    os::F_RDLCK
+                    libc::F_RDLCK as libc::c_short
                 };
 
                 let flock = os::flock {
@@ -205,7 +159,7 @@ cfg_if! {
                     l_type: lock_type,
                     l_sysid: 0,
                 };
-                let cmd = if wait { os::F_SETLKW } else { os::F_SETLK };
+                let cmd = if wait { libc::F_SETLKW } else { libc::F_SETLK };
                 let ret = unsafe {
                     libc::fcntl(fd, cmd, &flock)
                 };
@@ -226,11 +180,11 @@ cfg_if! {
                     l_len: 0,
                     l_pid: 0,
                     l_whence: libc::SEEK_SET as libc::c_short,
-                    l_type: os::F_UNLCK,
+                    l_type: libc::F_UNLCK as libc::c_short,
                     l_sysid: 0,
                 };
                 unsafe {
-                    libc::fcntl(self.fd, os::F_SETLK, &flock);
+                    libc::fcntl(self.fd, libc::F_SETLK, &flock);
                     libc::close(self.fd);
                 }
             }
diff --git a/src/librustc_data_structures/fx.rs b/src/librustc_data_structures/fx.rs
index 7c7fc3a9346..a2afeffe730 100644
--- a/src/librustc_data_structures/fx.rs
+++ b/src/librustc_data_structures/fx.rs
@@ -1,11 +1 @@
-// Copyright 2015 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.
-
 pub use rustc_hash::{FxHasher, FxHashMap, FxHashSet};
diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index 9b7f4cec47b..536efffbb22 100644
--- a/src/librustc_data_structures/graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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.
-
 //! Algorithm citation:
 //! A Simple, Fast Dominance Algorithm.
 //! Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
diff --git a/src/librustc_data_structures/graph/dominators/test.rs b/src/librustc_data_structures/graph/dominators/test.rs
index 0af878cac2d..5d17ce9e909 100644
--- a/src/librustc_data_structures/graph/dominators/test.rs
+++ b/src/librustc_data_structures/graph/dominators/test.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 super::super::test::TestGraph;
 
 use super::*;
diff --git a/src/librustc_data_structures/graph/implementation/mod.rs b/src/librustc_data_structures/graph/implementation/mod.rs
index c31321fa374..0768873f836 100644
--- a/src/librustc_data_structures/graph/implementation/mod.rs
+++ b/src/librustc_data_structures/graph/implementation/mod.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-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.
-
 //! A graph module for use in dataflow, region resolution, and elsewhere.
 //!
 //! # Interface details
diff --git a/src/librustc_data_structures/graph/implementation/tests.rs b/src/librustc_data_structures/graph/implementation/tests.rs
index 3814827b5df..a7a25042396 100644
--- a/src/librustc_data_structures/graph/implementation/tests.rs
+++ b/src/librustc_data_structures/graph/implementation/tests.rs
@@ -1,13 +1,3 @@
-// Copyright 2015 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 graph::implementation::*;
 use std::fmt::Debug;
 
diff --git a/src/librustc_data_structures/graph/iterate/mod.rs b/src/librustc_data_structures/graph/iterate/mod.rs
index 3afdc88d602..c09364b0a53 100644
--- a/src/librustc_data_structures/graph/iterate/mod.rs
+++ b/src/librustc_data_structures/graph/iterate/mod.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 super::super::indexed_vec::IndexVec;
 use super::{DirectedGraph, WithSuccessors, WithNumNodes};
 
diff --git a/src/librustc_data_structures/graph/iterate/test.rs b/src/librustc_data_structures/graph/iterate/test.rs
index 100881ddfdd..62e48aaec53 100644
--- a/src/librustc_data_structures/graph/iterate/test.rs
+++ b/src/librustc_data_structures/graph/iterate/test.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 super::super::test::TestGraph;
 
 use super::*;
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index 7265e4e8c7c..3d47b7d49fb 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 super::indexed_vec::Idx;
 
 pub mod dominators;
diff --git a/src/librustc_data_structures/graph/reference.rs b/src/librustc_data_structures/graph/reference.rs
index a7b763db8da..5ad2a71e1d7 100644
--- a/src/librustc_data_structures/graph/reference.rs
+++ b/src/librustc_data_structures/graph/reference.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 super::*;
 
 impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G {
diff --git a/src/librustc_data_structures/graph/scc/mod.rs b/src/librustc_data_structures/graph/scc/mod.rs
index 64de0c2f565..baab377ef12 100644
--- a/src/librustc_data_structures/graph/scc/mod.rs
+++ b/src/librustc_data_structures/graph/scc/mod.rs
@@ -1,13 +1,3 @@
-// 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.
-
 //! Routine to compute the strongly connected components (SCCs) of a
 //! graph, as well as the resulting DAG if each SCC is replaced with a
 //! node in the graph. This uses Tarjan's algorithm that completes in
diff --git a/src/librustc_data_structures/graph/scc/test.rs b/src/librustc_data_structures/graph/scc/test.rs
index 405e1b3a617..e23cb1348b0 100644
--- a/src/librustc_data_structures/graph/scc/test.rs
+++ b/src/librustc_data_structures/graph/scc/test.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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.
-
 #![cfg(test)]
 
 use graph::test::TestGraph;
diff --git a/src/librustc_data_structures/graph/test.rs b/src/librustc_data_structures/graph/test.rs
index 26cc2c9f17c..3d482e448bd 100644
--- a/src/librustc_data_structures/graph/test.rs
+++ b/src/librustc_data_structures/graph/test.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 fx::FxHashMap;
 use std::cmp::max;
 use std::slice;
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 6522dbe1179..8d8fbe588a0 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 std::fmt::Debug;
 use std::iter::{self, FromIterator};
 use std::slice;
diff --git a/src/librustc_data_structures/interner.rs b/src/librustc_data_structures/interner.rs
index 29e5aefee7f..36ccbb704a7 100644
--- a/src/librustc_data_structures/interner.rs
+++ b/src/librustc_data_structures/interner.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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 std::hash::Hash;
 use std::hash::BuildHasher;
 use std::hash::Hasher;
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index bc2b8f1d652..ec71f515894 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -1,13 +1,3 @@
-// Copyright 2015 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.
-
 //! Various data structures used by the Rust compiler. The intention
 //! is that code in here should be not be *specific* to rustc, so that
 //! it can be easily unit tested and so forth.
@@ -28,10 +18,10 @@
 #![feature(optin_builtin_traits)]
 #![feature(nll)]
 #![feature(allow_internal_unstable)]
-#![feature(vec_resize_with)]
 #![feature(hash_raw_entry)]
 #![feature(stmt_expr_attributes)]
 #![feature(core_intrinsics)]
+#![feature(integer_atomics)]
 
 #![cfg_attr(unix, feature(libc))]
 #![cfg_attr(test, feature(test))]
@@ -113,12 +103,14 @@ pub struct OnDrop<F: Fn()>(pub F);
 impl<F: Fn()> OnDrop<F> {
       /// Forgets the function which prevents it from running.
       /// Ensure that the function owns no memory, otherwise it will be leaked.
+      #[inline]
       pub fn disable(self) {
             std::mem::forget(self);
       }
 }
 
 impl<F: Fn()> Drop for OnDrop<F> {
+      #[inline]
       fn drop(&mut self) {
             (self.0)();
       }
diff --git a/src/librustc_data_structures/macros.rs b/src/librustc_data_structures/macros.rs
index 286a374b280..a661f0c78ab 100644
--- a/src/librustc_data_structures/macros.rs
+++ b/src/librustc_data_structures/macros.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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.
-
 /// A simple static assertion macro. The first argument should be a unique
 /// ALL_CAPS identifier that describes the condition.
 #[macro_export]
diff --git a/src/librustc_data_structures/obligation_forest/graphviz.rs b/src/librustc_data_structures/obligation_forest/graphviz.rs
index dcd448ee44f..c2e3938b305 100644
--- a/src/librustc_data_structures/obligation_forest/graphviz.rs
+++ b/src/librustc_data_structures/obligation_forest/graphviz.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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 graphviz as dot;
 use obligation_forest::{ForestObligation, ObligationForest};
 use std::env::var_os;
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 2a1958357e0..59497f0df18 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -1,13 +1,3 @@
-// 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.
-
 //! The `ObligationForest` is a utility data structure used in trait
 //! matching to track the set of outstanding obligations (those not
 //! yet resolved to success or error). It also tracks the "backtrace"
diff --git a/src/librustc_data_structures/obligation_forest/node_index.rs b/src/librustc_data_structures/obligation_forest/node_index.rs
index d89bd22ec96..69ea473e054 100644
--- a/src/librustc_data_structures/obligation_forest/node_index.rs
+++ b/src/librustc_data_structures/obligation_forest/node_index.rs
@@ -1,13 +1,3 @@
-// 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 std::num::NonZeroU32;
 use std::u32;
 
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/test.rs
index 2a418973fbd..27d4bf4959e 100644
--- a/src/librustc_data_structures/obligation_forest/test.rs
+++ b/src/librustc_data_structures/obligation_forest/test.rs
@@ -1,13 +1,3 @@
-// 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.
-
 #![cfg(test)]
 
 use super::{Error, DoCompleted, ObligationForest, ObligationProcessor, Outcome, ProcessResult};
diff --git a/src/librustc_data_structures/ptr_key.rs b/src/librustc_data_structures/ptr_key.rs
index 6835dab38df..322dcbe8f08 100644
--- a/src/librustc_data_structures/ptr_key.rs
+++ b/src/librustc_data_structures/ptr_key.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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 std::{hash, ptr};
 use std::ops::Deref;
 
diff --git a/src/librustc_data_structures/sip128.rs b/src/librustc_data_structures/sip128.rs
index 1f0b0d9cbfb..9ec9a398400 100644
--- a/src/librustc_data_structures/sip128.rs
+++ b/src/librustc_data_structures/sip128.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-2015 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.
-
 //! This is a copy of `core::hash::sip` adapted to providing 128 bit hashes.
 
 use std::cmp;
diff --git a/src/librustc_data_structures/small_c_str.rs b/src/librustc_data_structures/small_c_str.rs
index 08794fbec8d..bde7911267f 100644
--- a/src/librustc_data_structures/small_c_str.rs
+++ b/src/librustc_data_structures/small_c_str.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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 std::ffi;
 use std::ops::Deref;
 
diff --git a/src/librustc_data_structures/snapshot_map/mod.rs b/src/librustc_data_structures/snapshot_map/mod.rs
index c256506a19d..d408727aea5 100644
--- a/src/librustc_data_structures/snapshot_map/mod.rs
+++ b/src/librustc_data_structures/snapshot_map/mod.rs
@@ -1,13 +1,3 @@
-// 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 fx::FxHashMap;
 use std::hash::Hash;
 use std::ops;
diff --git a/src/librustc_data_structures/snapshot_map/test.rs b/src/librustc_data_structures/snapshot_map/test.rs
index b4ecb85fc43..72ca53c2be9 100644
--- a/src/librustc_data_structures/snapshot_map/test.rs
+++ b/src/librustc_data_structures/snapshot_map/test.rs
@@ -1,13 +1,3 @@
-// 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 super::SnapshotMap;
 
 #[test]
diff --git a/src/librustc_data_structures/sorted_map.rs b/src/librustc_data_structures/sorted_map.rs
index 3bd3d116607..64bbb8d7c08 100644
--- a/src/librustc_data_structures/sorted_map.rs
+++ b/src/librustc_data_structures/sorted_map.rs
@@ -1,13 +1,3 @@
-// Copyright 2018 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 std::borrow::Borrow;
 use std::cmp::Ordering;
 use std::iter::FromIterator;
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index c85d771a181..4583f12ec8c 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 std::hash::{Hash, Hasher, BuildHasher};
 use std::marker::PhantomData;
 use std::mem;
diff --git a/src/librustc_data_structures/svh.rs b/src/librustc_data_structures/svh.rs
index 3d17824608c..74947953497 100644
--- a/src/librustc_data_structures/svh.rs
+++ b/src/librustc_data_structures/svh.rs
@@ -1,13 +1,3 @@
-// Copyright 2012-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.
-
 //! Calculation and management of a Strict Version Hash for crates
 //!
 //! The SVH is used for incremental compilation to track when HIR
diff --git a/src/librustc_data_structures/sync.rs b/src/librustc_data_structures/sync.rs
index 6a4012c8198..f9f94f0be7b 100644
--- a/src/librustc_data_structures/sync.rs
+++ b/src/librustc_data_structures/sync.rs
@@ -1,13 +1,3 @@
-// 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.
-
 //! This module defines types which are thread safe if cfg!(parallel_queries) is true.
 //!
 //! `Lrc` is an alias of either Rc or Arc.
@@ -20,10 +10,6 @@
 //! It internally uses `parking_lot::RwLock` if cfg!(parallel_queries) is true,
 //! `RefCell` otherwise.
 //!
-//! `LockCell` is a thread safe version of `Cell`, with `set` and `get` operations.
-//! It can never deadlock. It uses `Cell` when
-//! cfg!(parallel_queries) is false, otherwise it is a `Lock`.
-//!
 //! `MTLock` is a mutex which disappears if cfg!(parallel_queries) is false.
 //!
 //! `MTRef` is a immutable reference if cfg!(parallel_queries), and an mutable reference otherwise.
@@ -33,11 +19,7 @@
 
 use std::collections::HashMap;
 use std::hash::{Hash, BuildHasher};
-use std::cmp::Ordering;
 use std::marker::PhantomData;
-use std::fmt::Debug;
-use std::fmt::Formatter;
-use std::fmt;
 use std::ops::{Deref, DerefMut};
 use owning_ref::{Erased, OwningRef};
 
@@ -64,6 +46,9 @@ pub fn serial_scope<F, R>(f: F) -> R
     f(&SerialScope)
 }
 
+pub use std::sync::atomic::Ordering::SeqCst;
+pub use std::sync::atomic::Ordering;
+
 cfg_if! {
     if #[cfg(not(parallel_queries))] {
         pub auto trait Send {}
@@ -79,6 +64,62 @@ cfg_if! {
             }
         }
 
+        use std::ops::Add;
+
+        #[derive(Debug)]
+        pub struct Atomic<T: Copy>(Cell<T>);
+
+        impl<T: Copy> Atomic<T> {
+            pub fn new(v: T) -> Self {
+                Atomic(Cell::new(v))
+            }
+        }
+
+        impl<T: Copy + PartialEq> Atomic<T> {
+            pub fn into_inner(self) -> T {
+                self.0.into_inner()
+            }
+
+            pub fn load(&self, _: Ordering) -> T {
+                self.0.get()
+            }
+
+            pub fn store(&self, val: T, _: Ordering) {
+                self.0.set(val)
+            }
+
+            pub fn swap(&self, val: T, _: Ordering) -> T {
+                self.0.replace(val)
+            }
+
+            pub fn compare_exchange(&self,
+                                    current: T,
+                                    new: T,
+                                    _: Ordering,
+                                    _: Ordering)
+                                    -> Result<T, T> {
+                let read = self.0.get();
+                if read == current {
+                    self.0.set(new);
+                    Ok(read)
+                } else {
+                    Err(read)
+                }
+            }
+        }
+
+        impl<T: Add<Output=T> + Copy> Atomic<T> {
+            pub fn fetch_add(&self, val: T, _: Ordering) -> T {
+                let old = self.0.get();
+                self.0.set(old + val);
+                old
+            }
+        }
+
+        pub type AtomicUsize = Atomic<usize>;
+        pub type AtomicBool = Atomic<bool>;
+        pub type AtomicU64 = Atomic<u64>;
+
         pub use self::serial_join as join;
         pub use self::serial_scope as scope;
 
@@ -170,47 +211,6 @@ cfg_if! {
                 MTLock(self.0.clone())
             }
         }
-
-        pub struct LockCell<T>(Cell<T>);
-
-        impl<T> LockCell<T> {
-            #[inline(always)]
-            pub fn new(inner: T) -> Self {
-                LockCell(Cell::new(inner))
-            }
-
-            #[inline(always)]
-            pub fn into_inner(self) -> T {
-                self.0.into_inner()
-            }
-
-            #[inline(always)]
-            pub fn set(&self, new_inner: T) {
-                self.0.set(new_inner);
-            }
-
-            #[inline(always)]
-            pub fn get(&self) -> T where T: Copy {
-                self.0.get()
-            }
-
-            #[inline(always)]
-            pub fn set_mut(&mut self, new_inner: T) {
-                self.0.set(new_inner);
-            }
-
-            #[inline(always)]
-            pub fn get_mut(&mut self) -> T where T: Copy {
-                self.0.get()
-            }
-        }
-
-        impl<T> LockCell<Option<T>> {
-            #[inline(always)]
-            pub fn take(&self) -> Option<T> {
-                unsafe { (*self.0.as_ptr()).take() }
-            }
-        }
     } else {
         pub use std::marker::Send as Send;
         pub use std::marker::Sync as Sync;
@@ -223,6 +223,8 @@ cfg_if! {
         pub use parking_lot::MutexGuard as LockGuard;
         pub use parking_lot::MappedMutexGuard as MappedLockGuard;
 
+        pub use std::sync::atomic::{AtomicBool, AtomicUsize, AtomicU64};
+
         pub use std::sync::Arc as Lrc;
         pub use std::sync::Weak as Weak;
 
@@ -288,51 +290,11 @@ cfg_if! {
                 v.erase_send_sync_owner()
             }}
         }
-
-        pub struct LockCell<T>(Lock<T>);
-
-        impl<T> LockCell<T> {
-            #[inline(always)]
-            pub fn new(inner: T) -> Self {
-                LockCell(Lock::new(inner))
-            }
-
-            #[inline(always)]
-            pub fn into_inner(self) -> T {
-                self.0.into_inner()
-            }
-
-            #[inline(always)]
-            pub fn set(&self, new_inner: T) {
-                *self.0.lock() = new_inner;
-            }
-
-            #[inline(always)]
-            pub fn get(&self) -> T where T: Copy {
-                *self.0.lock()
-            }
-
-            #[inline(always)]
-            pub fn set_mut(&mut self, new_inner: T) {
-                *self.0.get_mut() = new_inner;
-            }
-
-            #[inline(always)]
-            pub fn get_mut(&mut self) -> T where T: Copy {
-                *self.0.get_mut()
-            }
-        }
-
-        impl<T> LockCell<Option<T>> {
-            #[inline(always)]
-            pub fn take(&self) -> Option<T> {
-                self.0.lock().take()
-            }
-        }
     }
 }
 
 pub fn assert_sync<T: ?Sized + Sync>() {}
+pub fn assert_send<T: ?Sized + Send>() {}
 pub fn assert_send_val<T: ?Sized + Send>(_t: &T) {}
 pub fn assert_send_sync_val<T: ?Sized + Sync + Send>(_t: &T) {}
 
@@ -476,65 +438,6 @@ impl<T> Once<T> {
     }
 }
 
-impl<T: Copy + Debug> Debug for LockCell<T> {
-    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        f.debug_struct("LockCell")
-            .field("value", &self.get())
-            .finish()
-    }
-}
-
-impl<T:Default> Default for LockCell<T> {
-    /// Creates a `LockCell<T>`, with the `Default` value for T.
-    #[inline]
-    fn default() -> LockCell<T> {
-        LockCell::new(Default::default())
-    }
-}
-
-impl<T:PartialEq + Copy> PartialEq for LockCell<T> {
-    #[inline]
-    fn eq(&self, other: &LockCell<T>) -> bool {
-        self.get() == other.get()
-    }
-}
-
-impl<T:Eq + Copy> Eq for LockCell<T> {}
-
-impl<T:PartialOrd + Copy> PartialOrd for LockCell<T> {
-    #[inline]
-    fn partial_cmp(&self, other: &LockCell<T>) -> Option<Ordering> {
-        self.get().partial_cmp(&other.get())
-    }
-
-    #[inline]
-    fn lt(&self, other: &LockCell<T>) -> bool {
-        self.get() < other.get()
-    }
-
-    #[inline]
-    fn le(&self, other: &LockCell<T>) -> bool {
-        self.get() <= other.get()
-    }
-
-    #[inline]
-    fn gt(&self, other: &LockCell<T>) -> bool {
-        self.get() > other.get()
-    }
-
-    #[inline]
-    fn ge(&self, other: &LockCell<T>) -> bool {
-        self.get() >= other.get()
-    }
-}
-
-impl<T:Ord + Copy> Ord for LockCell<T> {
-    #[inline]
-    fn cmp(&self, other: &LockCell<T>) -> Ordering {
-        self.get().cmp(&other.get())
-    }
-}
-
 #[derive(Debug)]
 pub struct Lock<T>(InnerLock<T>);
 
diff --git a/src/librustc_data_structures/thin_vec.rs b/src/librustc_data_structures/thin_vec.rs
index 5b7ea161b28..359f9b7842d 100644
--- a/src/librustc_data_structures/thin_vec.rs
+++ b/src/librustc_data_structures/thin_vec.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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.
-
 /// A vector type optimized for cases where this size is usually 0 (cf. `SmallVector`).
 /// The `Option<Box<..>>` wrapping allows us to represent a zero sized vector with `None`,
 /// which uses only a single (null) pointer.
diff --git a/src/librustc_data_structures/tiny_list.rs b/src/librustc_data_structures/tiny_list.rs
index 9dbf0ea9f43..d660486d584 100644
--- a/src/librustc_data_structures/tiny_list.rs
+++ b/src/librustc_data_structures/tiny_list.rs
@@ -1,14 +1,3 @@
-// Copyright 2018 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.
-
-
 //! A singly-linked list.
 //!
 //! Using this data structure only makes sense under very specific
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 250dad8136e..9d675ed3096 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -1,13 +1,3 @@
-// Copyright 2015 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 bit_set::BitMatrix;
 use fx::FxHashMap;
 use sync::Lock;
diff --git a/src/librustc_data_structures/vec_linked_list.rs b/src/librustc_data_structures/vec_linked_list.rs
index 390dca6b905..3b6984dd075 100644
--- a/src/librustc_data_structures/vec_linked_list.rs
+++ b/src/librustc_data_structures/vec_linked_list.rs
@@ -1,13 +1,3 @@
-// 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>(
diff --git a/src/librustc_data_structures/work_queue.rs b/src/librustc_data_structures/work_queue.rs
index eff80a98c9d..0a928de7961 100644
--- a/src/librustc_data_structures/work_queue.rs
+++ b/src/librustc_data_structures/work_queue.rs
@@ -1,13 +1,3 @@
-// Copyright 2016 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 bit_set::BitSet;
 use indexed_vec::Idx;
 use std::collections::VecDeque;