Auto merge of #79012 - tgnottingham:span_data_to_lines_and_cols, r=estebank

rustc_span: add span_data_to_lines_and_cols to caching source map view

3 files changed, 222 insertions, 56 deletions

diff --git a/compiler/rustc_middle/src/ich/hcx.rs b/compiler/rustc_middle/src/ich/hcx.rs
index 084fe4cfa16..addcb7a14e3 100644
--- a/compiler/rustc_middle/src/ich/hcx.rs
+++ b/compiler/rustc_middle/src/ich/hcx.rs
@@ -12,7 +12,7 @@ use rustc_hir::definitions::{DefPathHash, Definitions};
 use rustc_session::Session;
 use rustc_span::source_map::SourceMap;
 use rustc_span::symbol::Symbol;
-use rustc_span::{BytePos, CachingSourceMapView, SourceFile};
+use rustc_span::{BytePos, CachingSourceMapView, SourceFile, SpanData};
 
 use rustc_span::def_id::{CrateNum, CRATE_DEF_INDEX};
 use smallvec::SmallVec;
@@ -248,6 +248,13 @@ impl<'a> rustc_span::HashStableContext for StableHashingContext<'a> {
     ) -> Option<(Lrc<SourceFile>, usize, BytePos)> {
         self.source_map().byte_pos_to_line_and_col(byte)
     }
+
+    fn span_data_to_lines_and_cols(
+        &mut self,
+        span: &SpanData,
+    ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)> {
+        self.source_map().span_data_to_lines_and_cols(span)
+    }
 }
 
 pub fn hash_stable_trait_impls<'a>(
diff --git a/compiler/rustc_span/src/caching_source_map_view.rs b/compiler/rustc_span/src/caching_source_map_view.rs
index 15dd00fb483..8e21b9ff44a 100644
--- a/compiler/rustc_span/src/caching_source_map_view.rs
+++ b/compiler/rustc_span/src/caching_source_map_view.rs
@@ -1,5 +1,5 @@
 use crate::source_map::SourceMap;
-use crate::{BytePos, SourceFile};
+use crate::{BytePos, SourceFile, SpanData};
 use rustc_data_structures::sync::Lrc;
 use std::ops::Range;
 
@@ -24,6 +24,32 @@ struct CacheEntry {
     file_index: usize,
 }
 
+impl CacheEntry {
+    #[inline]
+    fn update(
+        &mut self,
+        new_file_and_idx: Option<(Lrc<SourceFile>, usize)>,
+        pos: BytePos,
+        time_stamp: usize,
+    ) {
+        if let Some((file, file_idx)) = new_file_and_idx {
+            self.file = file;
+            self.file_index = file_idx;
+        }
+
+        let line_index = self.file.lookup_line(pos).unwrap();
+        let line_bounds = self.file.line_bounds(line_index);
+        self.line_number = line_index + 1;
+        self.line = line_bounds;
+        self.touch(time_stamp);
+    }
+
+    #[inline]
+    fn touch(&mut self, time_stamp: usize) {
+        self.time_stamp = time_stamp;
+    }
+}
+
 #[derive(Clone)]
 pub struct CachingSourceMapView<'sm> {
     source_map: &'sm SourceMap,
@@ -57,59 +83,202 @@ impl<'sm> CachingSourceMapView<'sm> {
         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 cache_entry.line.contains(&pos) {
-                cache_entry.time_stamp = self.time_stamp;
+        let cache_idx = self.cache_entry_index(pos);
+        if cache_idx != -1 {
+            let cache_entry = &mut self.line_cache[cache_idx as usize];
+            cache_entry.touch(self.time_stamp);
 
-                return Some((
-                    cache_entry.file.clone(),
-                    cache_entry.line_number,
-                    pos - cache_entry.line.start,
-                ));
-            }
+            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 oldest = self.oldest_cache_entry_index();
+
+        // If the entry doesn't point to the correct file, get the new file and index.
+        let new_file_and_idx = if !file_contains(&self.line_cache[oldest].file, pos) {
+            Some(self.file_for_position(pos)?)
+        } else {
+            None
+        };
 
         let cache_entry = &mut self.line_cache[oldest];
+        cache_entry.update(new_file_and_idx, pos, self.time_stamp);
 
-        // If the entry doesn't point to the correct file, fix it up
-        if !file_contains(&cache_entry.file, 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 file_contains(&file, pos) {
-                    cache_entry.file = file;
-                    cache_entry.file_index = file_index;
-                    file_valid = true;
-                } else {
-                    file_valid = false;
+        Some((cache_entry.file.clone(), cache_entry.line_number, pos - cache_entry.line.start))
+    }
+
+    pub fn span_data_to_lines_and_cols(
+        &mut self,
+        span_data: &SpanData,
+    ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)> {
+        self.time_stamp += 1;
+
+        // Check if lo and hi are in the cached lines.
+        let lo_cache_idx = self.cache_entry_index(span_data.lo);
+        let hi_cache_idx = self.cache_entry_index(span_data.hi);
+
+        if lo_cache_idx != -1 && hi_cache_idx != -1 {
+            // Cache hit for span lo and hi. Check if they belong to the same file.
+            let result = {
+                let lo = &self.line_cache[lo_cache_idx as usize];
+                let hi = &self.line_cache[hi_cache_idx as usize];
+
+                if lo.file_index != hi.file_index {
+                    return None;
                 }
-            } else {
-                file_valid = false;
+
+                (
+                    lo.file.clone(),
+                    lo.line_number,
+                    span_data.lo - lo.line.start,
+                    hi.line_number,
+                    span_data.hi - hi.line.start,
+                )
+            };
+
+            self.line_cache[lo_cache_idx as usize].touch(self.time_stamp);
+            self.line_cache[hi_cache_idx as usize].touch(self.time_stamp);
+
+            return Some(result);
+        }
+
+        // No cache hit or cache hit for only one of span lo and hi.
+        let oldest = if lo_cache_idx != -1 || hi_cache_idx != -1 {
+            let avoid_idx = if lo_cache_idx != -1 { lo_cache_idx } else { hi_cache_idx };
+            self.oldest_cache_entry_index_avoid(avoid_idx as usize)
+        } else {
+            self.oldest_cache_entry_index()
+        };
+
+        // If the entry doesn't point to the correct file, get the new file and index.
+        // Return early if the file containing beginning of span doesn't contain end of span.
+        let new_file_and_idx = if !file_contains(&self.line_cache[oldest].file, span_data.lo) {
+            let new_file_and_idx = self.file_for_position(span_data.lo)?;
+            if !file_contains(&new_file_and_idx.0, span_data.hi) {
+                return None;
             }
 
-            if !file_valid {
+            Some(new_file_and_idx)
+        } else {
+            let file = &self.line_cache[oldest].file;
+            if !file_contains(&file, span_data.hi) {
                 return None;
             }
+
+            None
+        };
+
+        // Update the cache entries.
+        let (lo_idx, hi_idx) = match (lo_cache_idx, hi_cache_idx) {
+            // Oldest cache entry is for span_data.lo line.
+            (-1, -1) => {
+                let lo = &mut self.line_cache[oldest];
+                lo.update(new_file_and_idx, span_data.lo, self.time_stamp);
+
+                if !lo.line.contains(&span_data.hi) {
+                    let new_file_and_idx = Some((lo.file.clone(), lo.file_index));
+                    let next_oldest = self.oldest_cache_entry_index_avoid(oldest);
+                    let hi = &mut self.line_cache[next_oldest];
+                    hi.update(new_file_and_idx, span_data.hi, self.time_stamp);
+                    (oldest, next_oldest)
+                } else {
+                    (oldest, oldest)
+                }
+            }
+            // Oldest cache entry is for span_data.lo line.
+            (-1, _) => {
+                let lo = &mut self.line_cache[oldest];
+                lo.update(new_file_and_idx, span_data.lo, self.time_stamp);
+                let hi = &mut self.line_cache[hi_cache_idx as usize];
+                hi.touch(self.time_stamp);
+                (oldest, hi_cache_idx as usize)
+            }
+            // Oldest cache entry is for span_data.hi line.
+            (_, -1) => {
+                let hi = &mut self.line_cache[oldest];
+                hi.update(new_file_and_idx, span_data.hi, self.time_stamp);
+                let lo = &mut self.line_cache[lo_cache_idx as usize];
+                lo.touch(self.time_stamp);
+                (lo_cache_idx as usize, oldest)
+            }
+            _ => {
+                panic!();
+            }
+        };
+
+        let lo = &self.line_cache[lo_idx];
+        let hi = &self.line_cache[hi_idx];
+
+        // Span lo and hi may equal line end when last line doesn't
+        // end in newline, hence the inclusive upper bounds below.
+        debug_assert!(span_data.lo >= lo.line.start);
+        debug_assert!(span_data.lo <= lo.line.end);
+        debug_assert!(span_data.hi >= hi.line.start);
+        debug_assert!(span_data.hi <= hi.line.end);
+        debug_assert!(lo.file.contains(span_data.lo));
+        debug_assert!(lo.file.contains(span_data.hi));
+        debug_assert_eq!(lo.file_index, hi.file_index);
+
+        Some((
+            lo.file.clone(),
+            lo.line_number,
+            span_data.lo - lo.line.start,
+            hi.line_number,
+            span_data.hi - hi.line.start,
+        ))
+    }
+
+    fn cache_entry_index(&self, pos: BytePos) -> isize {
+        for (idx, cache_entry) in self.line_cache.iter().enumerate() {
+            if cache_entry.line.contains(&pos) {
+                return idx as isize;
+            }
+        }
+
+        -1
+    }
+
+    fn oldest_cache_entry_index(&self) -> usize {
+        let mut oldest = 0;
+
+        for idx in 1..self.line_cache.len() {
+            if self.line_cache[idx].time_stamp < self.line_cache[oldest].time_stamp {
+                oldest = idx;
+            }
         }
 
-        let line_index = cache_entry.file.lookup_line(pos).unwrap();
-        let line_bounds = cache_entry.file.line_bounds(line_index);
+        oldest
+    }
 
-        cache_entry.line_number = line_index + 1;
-        cache_entry.line = line_bounds;
-        cache_entry.time_stamp = self.time_stamp;
+    fn oldest_cache_entry_index_avoid(&self, avoid_idx: usize) -> usize {
+        let mut oldest = if avoid_idx != 0 { 0 } else { 1 };
 
-        Some((cache_entry.file.clone(), cache_entry.line_number, pos - cache_entry.line.start))
+        for idx in 0..self.line_cache.len() {
+            if idx != avoid_idx
+                && self.line_cache[idx].time_stamp < self.line_cache[oldest].time_stamp
+            {
+                oldest = idx;
+            }
+        }
+
+        oldest
+    }
+
+    fn file_for_position(&self, pos: BytePos) -> Option<(Lrc<SourceFile>, usize)> {
+        if !self.source_map.files().is_empty() {
+            let file_idx = self.source_map.lookup_source_file_idx(pos);
+            let file = &self.source_map.files()[file_idx];
+
+            if file_contains(file, pos) {
+                return Some((file.clone(), file_idx));
+            }
+        }
+
+        None
     }
 }
 
diff --git a/compiler/rustc_span/src/lib.rs b/compiler/rustc_span/src/lib.rs
index 62ca7b066d9..f0f9f940446 100644
--- a/compiler/rustc_span/src/lib.rs
+++ b/compiler/rustc_span/src/lib.rs
@@ -1871,6 +1871,10 @@ pub trait HashStableContext {
         &mut self,
         byte: BytePos,
     ) -> Option<(Lrc<SourceFile>, usize, BytePos)>;
+    fn span_data_to_lines_and_cols(
+        &mut self,
+        span: &SpanData,
+    ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)>;
 }
 
 impl<CTX> HashStable<CTX> for Span
@@ -1904,22 +1908,8 @@ where
         // 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 => {
-                Hash::hash(&TAG_INVALID_SPAN, hasher);
-                span.ctxt.hash_stable(ctx, hasher);
-                return;
-            }
-        };
-
-        if !file_lo.contains(span.hi) {
-            Hash::hash(&TAG_INVALID_SPAN, hasher);
-            span.ctxt.hash_stable(ctx, hasher);
-            return;
-        }
-
-        let (_, line_hi, col_hi) = match ctx.byte_pos_to_line_and_col(span.hi) {
+        let (file, line_lo, col_lo, line_hi, col_hi) = match ctx.span_data_to_lines_and_cols(&span)
+        {
             Some(pos) => pos,
             None => {
                 Hash::hash(&TAG_INVALID_SPAN, hasher);
@@ -1931,7 +1921,7 @@ where
         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.
-        Hash::hash(&(file_lo.name_hash as u64), hasher);
+        Hash::hash(&(file.name_hash as u64), hasher);
 
         // Hash both the length and the end location (line/column) of a span. If we
         // hash only the length, for example, then two otherwise equal spans with