Merge branch 'master' into escape-reason-docs

5 files changed, 187 insertions, 2 deletions

diff --git a/src/librustc_data_structures/base_n.rs b/src/librustc_data_structures/base_n.rs
index bf3e682f86f..4359581a897 100644
--- a/src/librustc_data_structures/base_n.rs
+++ b/src/librustc_data_structures/base_n.rs
@@ -14,6 +14,8 @@
 use std::str;
 
 pub const MAX_BASE: u64 = 64;
+pub const ALPHANUMERIC_ONLY: u64 = 62;
+
 const BASE_64: &'static [u8; MAX_BASE as usize] =
     b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@$";
 
diff --git a/src/librustc_data_structures/flock.rs b/src/librustc_data_structures/flock.rs
index 510c9ceef09..33d71ba8626 100644
--- a/src/librustc_data_structures/flock.rs
+++ b/src/librustc_data_structures/flock.rs
@@ -31,6 +31,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_type: libc::c_short,
             pub l_whence: libc::c_short,
@@ -53,6 +54,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_start: libc::off_t,
             pub l_len: libc::off_t,
@@ -76,6 +78,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_start: libc::off_t,
             pub l_len: libc::off_t,
@@ -98,6 +101,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_type: libc::c_short,
             pub l_whence: libc::c_short,
@@ -119,6 +123,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_start: libc::off_t,
             pub l_len: libc::off_t,
@@ -141,6 +146,7 @@ mod imp {
     mod os {
         use libc;
 
+        #[repr(C)]
         pub struct flock {
             pub l_type: libc::c_short,
             pub l_whence: libc::c_short,
diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/tests.rs
index a87410e6e1c..bdefc39a61a 100644
--- a/src/librustc_data_structures/graph/tests.rs
+++ b/src/librustc_data_structures/graph/tests.rs
@@ -11,8 +11,6 @@
 use graph::*;
 use std::fmt::Debug;
 
-type TestNode = Node<&'static str>;
-type TestEdge = Edge<&'static str>;
 type TestGraph = Graph<&'static str, &'static str>;
 
 fn create_graph() -> TestGraph {
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index de13b9bf4be..86f244d65dd 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -44,6 +44,8 @@ extern crate serialize as rustc_serialize; // used by deriving
 #[cfg(unix)]
 extern crate libc;
 
+pub use rustc_serialize::hex::ToHex;
+
 pub mod array_vec;
 pub mod accumulate_vec;
 pub mod small_vec;
@@ -59,6 +61,7 @@ pub mod indexed_vec;
 pub mod obligation_forest;
 pub mod snapshot_map;
 pub mod snapshot_vec;
+pub mod stable_hasher;
 pub mod transitive_relation;
 pub mod unify;
 pub mod fnv;
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
new file mode 100644
index 00000000000..ed97c3dde5e
--- /dev/null
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -0,0 +1,176 @@
+// 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::Hasher;
+use std::marker::PhantomData;
+use std::mem;
+use blake2b::Blake2bHasher;
+use rustc_serialize::leb128;
+
+fn write_unsigned_leb128_to_buf(buf: &mut [u8; 16], value: u64) -> usize {
+    leb128::write_unsigned_leb128_to(value, |i, v| buf[i] = v)
+}
+
+fn write_signed_leb128_to_buf(buf: &mut [u8; 16], value: i64) -> usize {
+    leb128::write_signed_leb128_to(value, |i, v| buf[i] = v)
+}
+
+/// When hashing something that ends up affecting properties like symbol names. We
+/// want these symbol names to be calculated independent of other factors like
+/// what architecture you're compiling *from*.
+///
+/// The hashing just uses the standard `Hash` trait, but the implementations of
+/// `Hash` for the `usize` and `isize` types are *not* architecture independent
+/// (e.g. they has 4 or 8 bytes). As a result we want to avoid `usize` and
+/// `isize` completely when hashing.
+///
+/// To do that, we encode all integers to be hashed with some
+/// arch-independent encoding.
+///
+/// At the moment, we pass i8/u8 straight through and encode
+/// all other integers using leb128.
+///
+/// This hasher currently always uses the stable Blake2b algorithm
+/// and allows for variable output lengths through its type
+/// parameter.
+#[derive(Debug)]
+pub struct StableHasher<W> {
+    state: Blake2bHasher,
+    bytes_hashed: u64,
+    width: PhantomData<W>,
+}
+
+pub trait StableHasherResult: Sized {
+    fn finish(hasher: StableHasher<Self>) -> Self;
+}
+
+impl<W: StableHasherResult> StableHasher<W> {
+    pub fn new() -> Self {
+        StableHasher {
+            state: Blake2bHasher::new(mem::size_of::<W>(), &[]),
+            bytes_hashed: 0,
+            width: PhantomData,
+        }
+    }
+
+    pub fn finish(self) -> W {
+        W::finish(self)
+    }
+}
+
+impl StableHasherResult for [u8; 20] {
+    fn finish(mut hasher: StableHasher<Self>) -> Self {
+        let mut result: [u8; 20] = [0; 20];
+        result.copy_from_slice(hasher.state.finalize());
+        result
+    }
+}
+
+impl StableHasherResult for u64 {
+    fn finish(mut hasher: StableHasher<Self>) -> Self {
+        hasher.state.finalize();
+        hasher.state.finish()
+    }
+}
+
+impl<W> StableHasher<W> {
+    #[inline]
+    pub fn finalize(&mut self) -> &[u8] {
+        self.state.finalize()
+    }
+
+    #[inline]
+    pub fn bytes_hashed(&self) -> u64 {
+        self.bytes_hashed
+    }
+
+    #[inline]
+    fn write_uleb128(&mut self, value: u64) {
+        let mut buf = [0; 16];
+        let len = write_unsigned_leb128_to_buf(&mut buf, value);
+        self.state.write(&buf[..len]);
+        self.bytes_hashed += len as u64;
+    }
+
+    #[inline]
+    fn write_ileb128(&mut self, value: i64) {
+        let mut buf = [0; 16];
+        let len = write_signed_leb128_to_buf(&mut buf, value);
+        self.state.write(&buf[..len]);
+        self.bytes_hashed += len as u64;
+    }
+}
+
+// For the non-u8 integer cases we leb128 encode them first. Because small
+// integers dominate, this significantly and cheaply reduces the number of
+// bytes hashed, which is good because blake2b is expensive.
+impl<W> Hasher for StableHasher<W> {
+    fn finish(&self) -> u64 {
+        panic!("use StableHasher::finish instead");
+    }
+
+    #[inline]
+    fn write(&mut self, bytes: &[u8]) {
+        self.state.write(bytes);
+        self.bytes_hashed += bytes.len() as u64;
+    }
+
+    #[inline]
+    fn write_u8(&mut self, i: u8) {
+        self.state.write_u8(i);
+        self.bytes_hashed += 1;
+    }
+
+    #[inline]
+    fn write_u16(&mut self, i: u16) {
+        self.write_uleb128(i as u64);
+    }
+
+    #[inline]
+    fn write_u32(&mut self, i: u32) {
+        self.write_uleb128(i as u64);
+    }
+
+    #[inline]
+    fn write_u64(&mut self, i: u64) {
+        self.write_uleb128(i);
+    }
+
+    #[inline]
+    fn write_usize(&mut self, i: usize) {
+        self.write_uleb128(i as u64);
+    }
+
+    #[inline]
+    fn write_i8(&mut self, i: i8) {
+        self.state.write_i8(i);
+        self.bytes_hashed += 1;
+    }
+
+    #[inline]
+    fn write_i16(&mut self, i: i16) {
+        self.write_ileb128(i as i64);
+    }
+
+    #[inline]
+    fn write_i32(&mut self, i: i32) {
+        self.write_ileb128(i as i64);
+    }
+
+    #[inline]
+    fn write_i64(&mut self, i: i64) {
+        self.write_ileb128(i);
+    }
+
+    #[inline]
+    fn write_isize(&mut self, i: isize) {
+        self.write_ileb128(i as i64);
+    }
+}