Auto merge of #66279 - cjgillot:hashstable, r=Zoxc

Use proc-macro to derive HashStable everywhere

Hello,

A second proc-macro is added to derive HashStable for crates librustc depends on.
This proc-macro `HashStable_Generic` (to bikeshed) allows to decouple code and strip much of librustc's boilerplate.

Still, two implementations `Span` and `TokenKind` require to be placed in librustc.
The latter only depends on the `bug` macro. Advise welcome on how to sever that link.
A trait `StableHasingContextLike` has been introduced at each crate root,
in order to handle those implementations which require librustc's very `StableHashingContext`.

This overall effort allowed to remove the `impl_stable_hash_for` macro.

Each commit passes the `x.py check`.
I still have to double check there was no change in the implementation.

5 files changed, 207 insertions, 6 deletions

diff --git a/src/libsyntax_pos/caching_source_map_view.rs b/src/libsyntax_pos/caching_source_map_view.rs
new file mode 100644
index 00000000000..82371730876
--- /dev/null
+++ b/src/libsyntax_pos/caching_source_map_view.rs
@@ -0,0 +1,103 @@
+use rustc_data_structures::sync::Lrc;
+use crate::source_map::SourceMap;
+use crate::{BytePos, SourceFile};
+
+#[derive(Clone)]
+struct CacheEntry {
+    time_stamp: usize,
+    line_number: usize,
+    line_start: BytePos,
+    line_end: BytePos,
+    file: Lrc<SourceFile>,
+    file_index: usize,
+}
+
+#[derive(Clone)]
+pub struct CachingSourceMapView<'cm> {
+    source_map: &'cm SourceMap,
+    line_cache: [CacheEntry; 3],
+    time_stamp: usize,
+}
+
+impl<'cm> CachingSourceMapView<'cm> {
+    pub fn new(source_map: &'cm SourceMap) -> CachingSourceMapView<'cm> {
+        let files = source_map.files();
+        let first_file = files[0].clone();
+        let entry = CacheEntry {
+            time_stamp: 0,
+            line_number: 0,
+            line_start: BytePos(0),
+            line_end: BytePos(0),
+            file: first_file,
+            file_index: 0,
+        };
+
+        CachingSourceMapView {
+            source_map,
+            line_cache: [entry.clone(), entry.clone(), entry],
+            time_stamp: 0,
+        }
+    }
+
+    pub fn byte_pos_to_line_and_col(&mut self,
+                                    pos: BytePos)
+                                    -> Option<(Lrc<SourceFile>, usize, BytePos)> {
+        self.time_stamp += 1;
+
+        // Check if the position is in one of the cached lines
+        for cache_entry in self.line_cache.iter_mut() {
+            if pos >= cache_entry.line_start && pos < cache_entry.line_end {
+                cache_entry.time_stamp = self.time_stamp;
+
+                return Some((cache_entry.file.clone(),
+                             cache_entry.line_number,
+                             pos - cache_entry.line_start));
+            }
+        }
+
+        // No cache hit ...
+        let mut oldest = 0;
+        for index in 1 .. self.line_cache.len() {
+            if self.line_cache[index].time_stamp < self.line_cache[oldest].time_stamp {
+                oldest = index;
+            }
+        }
+
+        let cache_entry = &mut self.line_cache[oldest];
+
+        // If the entry doesn't point to the correct file, fix it up
+        if pos < cache_entry.file.start_pos || pos >= cache_entry.file.end_pos {
+            let file_valid;
+            if self.source_map.files().len() > 0 {
+                let file_index = self.source_map.lookup_source_file_idx(pos);
+                let file = self.source_map.files()[file_index].clone();
+
+                if pos >= file.start_pos && pos < file.end_pos {
+                    cache_entry.file = file;
+                    cache_entry.file_index = file_index;
+                    file_valid = true;
+                } else {
+                    file_valid = false;
+                }
+            } else {
+                file_valid = false;
+            }
+
+            if !file_valid {
+                return None;
+            }
+        }
+
+        let line_index = cache_entry.file.lookup_line(pos).unwrap();
+        let line_bounds = cache_entry.file.line_bounds(line_index);
+
+        cache_entry.line_number = line_index + 1;
+        cache_entry.line_start = line_bounds.0;
+        cache_entry.line_end = line_bounds.1;
+        cache_entry.time_stamp = self.time_stamp;
+
+        return Some((cache_entry.file.clone(),
+                     cache_entry.line_number,
+                     pos - cache_entry.line_start));
+    }
+}
diff --git a/src/libsyntax_pos/hygiene.rs b/src/libsyntax_pos/hygiene.rs
index 583c81143a5..3c1d19256e9 100644
--- a/src/libsyntax_pos/hygiene.rs
+++ b/src/libsyntax_pos/hygiene.rs
@@ -616,12 +616,13 @@ impl Span {
 
 /// A subset of properties from both macro definition and macro call available through global data.
 /// Avoid using this if you have access to the original definition or call structures.
-#[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
+#[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable_Generic)]
 pub struct ExpnData {
     // --- The part unique to each expansion.
     /// The kind of this expansion - macro or compiler desugaring.
     pub kind: ExpnKind,
     /// The expansion that produced this expansion.
+    #[stable_hasher(ignore)]
     pub parent: ExpnId,
     /// The location of the actual macro invocation or syntax sugar , e.g.
     /// `let x = foo!();` or `if let Some(y) = x {}`
diff --git a/src/libsyntax_pos/lib.rs b/src/libsyntax_pos/lib.rs
index 720ace90324..66f25770722 100644
--- a/src/libsyntax_pos/lib.rs
+++ b/src/libsyntax_pos/lib.rs
@@ -18,6 +18,8 @@ use rustc_serialize::{Encodable, Decodable, Encoder, Decoder};
 use rustc_macros::HashStable_Generic;
 
 pub mod source_map;
+mod caching_source_map_view;
+pub use self::caching_source_map_view::CachingSourceMapView;
 
 pub mod edition;
 use edition::Edition;
@@ -34,11 +36,13 @@ pub use symbol::{Symbol, sym};
 mod analyze_source_file;
 pub mod fatal_error;
 
-use rustc_data_structures::stable_hasher::StableHasher;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::sync::{Lrc, Lock};
+use rustc_data_structures::fx::FxHashMap;
 
 use std::borrow::Cow;
-use std::cell::Cell;
+use std::cell::{Cell, RefCell};
 use std::cmp::{self, Ordering};
 use std::fmt;
 use std::hash::{Hasher, Hash};
@@ -1562,3 +1566,96 @@ fn lookup_line(lines: &[BytePos], pos: BytePos) -> isize {
         Err(line) => line as isize - 1
     }
 }
+
+/// Requirements for a `StableHashingContext` to be used in this crate.
+/// This is a hack to allow using the `HashStable_Generic` derive macro
+/// instead of implementing everything in librustc.
+pub trait HashStableContext {
+    fn hash_spans(&self) -> bool;
+    fn byte_pos_to_line_and_col(&mut self, byte: BytePos)
+        -> Option<(Lrc<SourceFile>, usize, BytePos)>;
+}
+
+impl<CTX> HashStable<CTX> for Span
+    where CTX: HashStableContext
+{
+    /// Hashes a span in a stable way. We can't directly hash the span's `BytePos`
+    /// fields (that would be similar to hashing pointers, since those are just
+    /// offsets into the `SourceMap`). Instead, we hash the (file name, line, column)
+    /// triple, which stays the same even if the containing `SourceFile` has moved
+    /// within the `SourceMap`.
+    /// Also note that we are hashing byte offsets for the column, not unicode
+    /// codepoint offsets. For the purpose of the hash that's sufficient.
+    /// Also, hashing filenames is expensive so we avoid doing it twice when the
+    /// span starts and ends in the same file, which is almost always the case.
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        const TAG_VALID_SPAN: u8 = 0;
+        const TAG_INVALID_SPAN: u8 = 1;
+        const TAG_EXPANSION: u8 = 0;
+        const TAG_NO_EXPANSION: u8 = 1;
+
+        if !ctx.hash_spans() {
+            return
+        }
+
+        if *self == DUMMY_SP {
+            return std::hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
+        }
+
+        // If this is not an empty or invalid span, we want to hash the last
+        // position that belongs to it, as opposed to hashing the first
+        // position past it.
+        let span = self.data();
+        let (file_lo, line_lo, col_lo) = match ctx.byte_pos_to_line_and_col(span.lo) {
+            Some(pos) => pos,
+            None => {
+                return std::hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
+            }
+        };
+
+        if !file_lo.contains(span.hi) {
+            return std::hash::Hash::hash(&TAG_INVALID_SPAN, hasher);
+        }
+
+        std::hash::Hash::hash(&TAG_VALID_SPAN, hasher);
+        // We truncate the stable ID hash and line and column numbers. The chances
+        // of causing a collision this way should be minimal.
+        std::hash::Hash::hash(&(file_lo.name_hash as u64), hasher);
+
+        let col = (col_lo.0 as u64) & 0xFF;
+        let line = ((line_lo as u64) & 0xFF_FF_FF) << 8;
+        let len = ((span.hi - span.lo).0 as u64) << 32;
+        let line_col_len = col | line | len;
+        std::hash::Hash::hash(&line_col_len, hasher);
+
+        if span.ctxt == SyntaxContext::root() {
+            TAG_NO_EXPANSION.hash_stable(ctx, hasher);
+        } else {
+            TAG_EXPANSION.hash_stable(ctx, hasher);
+
+            // Since the same expansion context is usually referenced many
+            // times, we cache a stable hash of it and hash that instead of
+            // recursing every time.
+            thread_local! {
+                static CACHE: RefCell<FxHashMap<hygiene::ExpnId, u64>> = Default::default();
+            }
+
+            let sub_hash: u64 = CACHE.with(|cache| {
+                let expn_id = span.ctxt.outer_expn();
+
+                if let Some(&sub_hash) = cache.borrow().get(&expn_id) {
+                    return sub_hash;
+                }
+
+                let mut hasher = StableHasher::new();
+                expn_id.expn_data().hash_stable(ctx, &mut hasher);
+                let sub_hash: Fingerprint = hasher.finish();
+                let sub_hash = sub_hash.to_smaller_hash();
+                cache.borrow_mut().insert(expn_id, sub_hash);
+                sub_hash
+            });
+
+            sub_hash.hash_stable(ctx, hasher);
+        }
+    }
+}
diff --git a/src/libsyntax_pos/source_map.rs b/src/libsyntax_pos/source_map.rs
index 77d9807225e..b597fad080f 100644
--- a/src/libsyntax_pos/source_map.rs
+++ b/src/libsyntax_pos/source_map.rs
@@ -39,7 +39,7 @@ pub fn original_sp(sp: Span, enclosing_sp: Span) -> Span {
     }
 }
 
-#[derive(Clone, RustcEncodable, RustcDecodable, Debug, Copy)]
+#[derive(Clone, RustcEncodable, RustcDecodable, Debug, Copy, HashStable_Generic)]
 pub struct Spanned<T> {
     pub node: T,
     pub span: Span,
diff --git a/src/libsyntax_pos/symbol.rs b/src/libsyntax_pos/symbol.rs
index 70ca9c0f7ca..7d43c3c8d07 100644
--- a/src/libsyntax_pos/symbol.rs
+++ b/src/libsyntax_pos/symbol.rs
@@ -5,7 +5,7 @@
 use arena::DroplessArena;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::vec::Idx;
-use rustc_macros::symbols;
+use rustc_macros::{symbols, HashStable_Generic};
 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
 use rustc_serialize::{UseSpecializedDecodable, UseSpecializedEncodable};
 use rustc_data_structures::stable_hasher::{HashStable, ToStableHashKey, StableHasher};
@@ -754,7 +754,7 @@ symbols! {
     }
 }
 
-#[derive(Copy, Clone, Eq)]
+#[derive(Copy, Clone, Eq, HashStable_Generic)]
 pub struct Ident {
     pub name: Symbol,
     pub span: Span,