1 use crate::source_map::SourceMap;
2 use crate::{BytePos, SourceFile, SpanData};
3 use rustc_data_structures::sync::Lrc;
4 use std::ops::Range;
5
6 #[derive(Clone)]
7 struct CacheEntry {
8 time_stamp: usize,
9 line_number: usize,
10 // The line's byte position range in the `SourceMap`. This range will fail to contain a valid
11 // position in certain edge cases. Spans often start/end one past something, and when that
12 // something is the last character of a file (this can happen when a file doesn't end in a
13 // newline, for example), we'd still like for the position to be considered within the last
14 // line. However, it isn't according to the exclusive upper bound of this range. We cannot
15 // change the upper bound to be inclusive, because for most lines, the upper bound is the same
16 // as the lower bound of the next line, so there would be an ambiguity.
17 //
18 // Since the containment aspect of this range is only used to see whether or not the cache
19 // entry contains a position, the only ramification of the above is that we will get cache
20 // misses for these rare positions. A line lookup for the position via `SourceMap::lookup_line`
21 // after a cache miss will produce the last line number, as desired.
22 line: Range<BytePos>,
23 file: Lrc<SourceFile>,
24 file_index: usize,
25 }
26
27 impl CacheEntry {
28 #[inline]
update( &mut self, new_file_and_idx: Option<(Lrc<SourceFile>, usize)>, pos: BytePos, time_stamp: usize, )29 fn update(
30 &mut self,
31 new_file_and_idx: Option<(Lrc<SourceFile>, usize)>,
32 pos: BytePos,
33 time_stamp: usize,
34 ) {
35 if let Some((file, file_idx)) = new_file_and_idx {
36 self.file = file;
37 self.file_index = file_idx;
38 }
39
40 let line_index = self.file.lookup_line(pos).unwrap();
41 let line_bounds = self.file.line_bounds(line_index);
42 self.line_number = line_index + 1;
43 self.line = line_bounds;
44 self.touch(time_stamp);
45 }
46
47 #[inline]
touch(&mut self, time_stamp: usize)48 fn touch(&mut self, time_stamp: usize) {
49 self.time_stamp = time_stamp;
50 }
51 }
52
53 #[derive(Clone)]
54 pub struct CachingSourceMapView<'sm> {
55 source_map: &'sm SourceMap,
56 line_cache: [CacheEntry; 3],
57 time_stamp: usize,
58 }
59
60 impl<'sm> CachingSourceMapView<'sm> {
new(source_map: &'sm SourceMap) -> CachingSourceMapView<'sm>61 pub fn new(source_map: &'sm SourceMap) -> CachingSourceMapView<'sm> {
62 let files = source_map.files();
63 let first_file = files[0].clone();
64 let entry = CacheEntry {
65 time_stamp: 0,
66 line_number: 0,
67 line: BytePos(0)..BytePos(0),
68 file: first_file,
69 file_index: 0,
70 };
71
72 CachingSourceMapView {
73 source_map,
74 line_cache: [entry.clone(), entry.clone(), entry],
75 time_stamp: 0,
76 }
77 }
78
byte_pos_to_line_and_col( &mut self, pos: BytePos, ) -> Option<(Lrc<SourceFile>, usize, BytePos)>79 pub fn byte_pos_to_line_and_col(
80 &mut self,
81 pos: BytePos,
82 ) -> Option<(Lrc<SourceFile>, usize, BytePos)> {
83 self.time_stamp += 1;
84
85 // Check if the position is in one of the cached lines
86 let cache_idx = self.cache_entry_index(pos);
87 if cache_idx != -1 {
88 let cache_entry = &mut self.line_cache[cache_idx as usize];
89 cache_entry.touch(self.time_stamp);
90
91 return Some((
92 cache_entry.file.clone(),
93 cache_entry.line_number,
94 pos - cache_entry.line.start,
95 ));
96 }
97
98 // No cache hit ...
99 let oldest = self.oldest_cache_entry_index();
100
101 // If the entry doesn't point to the correct file, get the new file and index.
102 let new_file_and_idx = if !file_contains(&self.line_cache[oldest].file, pos) {
103 Some(self.file_for_position(pos)?)
104 } else {
105 None
106 };
107
108 let cache_entry = &mut self.line_cache[oldest];
109 cache_entry.update(new_file_and_idx, pos, self.time_stamp);
110
111 Some((cache_entry.file.clone(), cache_entry.line_number, pos - cache_entry.line.start))
112 }
113
span_data_to_lines_and_cols( &mut self, span_data: &SpanData, ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)>114 pub fn span_data_to_lines_and_cols(
115 &mut self,
116 span_data: &SpanData,
117 ) -> Option<(Lrc<SourceFile>, usize, BytePos, usize, BytePos)> {
118 self.time_stamp += 1;
119
120 // Check if lo and hi are in the cached lines.
121 let lo_cache_idx = self.cache_entry_index(span_data.lo);
122 let hi_cache_idx = self.cache_entry_index(span_data.hi);
123
124 if lo_cache_idx != -1 && hi_cache_idx != -1 {
125 // Cache hit for span lo and hi. Check if they belong to the same file.
126 let result = {
127 let lo = &self.line_cache[lo_cache_idx as usize];
128 let hi = &self.line_cache[hi_cache_idx as usize];
129
130 if lo.file_index != hi.file_index {
131 return None;
132 }
133
134 (
135 lo.file.clone(),
136 lo.line_number,
137 span_data.lo - lo.line.start,
138 hi.line_number,
139 span_data.hi - hi.line.start,
140 )
141 };
142
143 self.line_cache[lo_cache_idx as usize].touch(self.time_stamp);
144 self.line_cache[hi_cache_idx as usize].touch(self.time_stamp);
145
146 return Some(result);
147 }
148
149 // No cache hit or cache hit for only one of span lo and hi.
150 let oldest = if lo_cache_idx != -1 || hi_cache_idx != -1 {
151 let avoid_idx = if lo_cache_idx != -1 { lo_cache_idx } else { hi_cache_idx };
152 self.oldest_cache_entry_index_avoid(avoid_idx as usize)
153 } else {
154 self.oldest_cache_entry_index()
155 };
156
157 // If the entry doesn't point to the correct file, get the new file and index.
158 // Return early if the file containing beginning of span doesn't contain end of span.
159 let new_file_and_idx = if !file_contains(&self.line_cache[oldest].file, span_data.lo) {
160 let new_file_and_idx = self.file_for_position(span_data.lo)?;
161 if !file_contains(&new_file_and_idx.0, span_data.hi) {
162 return None;
163 }
164
165 Some(new_file_and_idx)
166 } else {
167 let file = &self.line_cache[oldest].file;
168 if !file_contains(&file, span_data.hi) {
169 return None;
170 }
171
172 None
173 };
174
175 // Update the cache entries.
176 let (lo_idx, hi_idx) = match (lo_cache_idx, hi_cache_idx) {
177 // Oldest cache entry is for span_data.lo line.
178 (-1, -1) => {
179 let lo = &mut self.line_cache[oldest];
180 lo.update(new_file_and_idx, span_data.lo, self.time_stamp);
181
182 if !lo.line.contains(&span_data.hi) {
183 let new_file_and_idx = Some((lo.file.clone(), lo.file_index));
184 let next_oldest = self.oldest_cache_entry_index_avoid(oldest);
185 let hi = &mut self.line_cache[next_oldest];
186 hi.update(new_file_and_idx, span_data.hi, self.time_stamp);
187 (oldest, next_oldest)
188 } else {
189 (oldest, oldest)
190 }
191 }
192 // Oldest cache entry is for span_data.lo line.
193 (-1, _) => {
194 let lo = &mut self.line_cache[oldest];
195 lo.update(new_file_and_idx, span_data.lo, self.time_stamp);
196 let hi = &mut self.line_cache[hi_cache_idx as usize];
197 hi.touch(self.time_stamp);
198 (oldest, hi_cache_idx as usize)
199 }
200 // Oldest cache entry is for span_data.hi line.
201 (_, -1) => {
202 let hi = &mut self.line_cache[oldest];
203 hi.update(new_file_and_idx, span_data.hi, self.time_stamp);
204 let lo = &mut self.line_cache[lo_cache_idx as usize];
205 lo.touch(self.time_stamp);
206 (lo_cache_idx as usize, oldest)
207 }
208 _ => {
209 panic!();
210 }
211 };
212
213 let lo = &self.line_cache[lo_idx];
214 let hi = &self.line_cache[hi_idx];
215
216 // Span lo and hi may equal line end when last line doesn't
217 // end in newline, hence the inclusive upper bounds below.
218 debug_assert!(span_data.lo >= lo.line.start);
219 debug_assert!(span_data.lo <= lo.line.end);
220 debug_assert!(span_data.hi >= hi.line.start);
221 debug_assert!(span_data.hi <= hi.line.end);
222 debug_assert!(lo.file.contains(span_data.lo));
223 debug_assert!(lo.file.contains(span_data.hi));
224 debug_assert_eq!(lo.file_index, hi.file_index);
225
226 Some((
227 lo.file.clone(),
228 lo.line_number,
229 span_data.lo - lo.line.start,
230 hi.line_number,
231 span_data.hi - hi.line.start,
232 ))
233 }
234
cache_entry_index(&self, pos: BytePos) -> isize235 fn cache_entry_index(&self, pos: BytePos) -> isize {
236 for (idx, cache_entry) in self.line_cache.iter().enumerate() {
237 if cache_entry.line.contains(&pos) {
238 return idx as isize;
239 }
240 }
241
242 -1
243 }
244
oldest_cache_entry_index(&self) -> usize245 fn oldest_cache_entry_index(&self) -> usize {
246 let mut oldest = 0;
247
248 for idx in 1..self.line_cache.len() {
249 if self.line_cache[idx].time_stamp < self.line_cache[oldest].time_stamp {
250 oldest = idx;
251 }
252 }
253
254 oldest
255 }
256
oldest_cache_entry_index_avoid(&self, avoid_idx: usize) -> usize257 fn oldest_cache_entry_index_avoid(&self, avoid_idx: usize) -> usize {
258 let mut oldest = if avoid_idx != 0 { 0 } else { 1 };
259
260 for idx in 0..self.line_cache.len() {
261 if idx != avoid_idx
262 && self.line_cache[idx].time_stamp < self.line_cache[oldest].time_stamp
263 {
264 oldest = idx;
265 }
266 }
267
268 oldest
269 }
270
file_for_position(&self, pos: BytePos) -> Option<(Lrc<SourceFile>, usize)>271 fn file_for_position(&self, pos: BytePos) -> Option<(Lrc<SourceFile>, usize)> {
272 if !self.source_map.files().is_empty() {
273 let file_idx = self.source_map.lookup_source_file_idx(pos);
274 let file = &self.source_map.files()[file_idx];
275
276 if file_contains(file, pos) {
277 return Some((file.clone(), file_idx));
278 }
279 }
280
281 None
282 }
283 }
284
285 #[inline]
file_contains(file: &SourceFile, pos: BytePos) -> bool286 fn file_contains(file: &SourceFile, pos: BytePos) -> bool {
287 // `SourceMap::lookup_source_file_idx` and `SourceFile::contains` both consider the position
288 // one past the end of a file to belong to it. Normally, that's what we want. But for the
289 // purposes of converting a byte position to a line and column number, we can't come up with a
290 // line and column number if the file is empty, because an empty file doesn't contain any
291 // lines. So for our purposes, we don't consider empty files to contain any byte position.
292 file.contains(pos) && !file.is_empty()
293 }
294