rustc_utils/source_map/
range.rs

1use std::{
2  cell::RefCell, collections::hash_map::Entry, default::Default, ffi::OsStr,
3  path::PathBuf, sync::Arc,
4};
5
6use anyhow::{Context, Result, bail, ensure};
7use rustc_data_structures::fx::FxHashMap as HashMap;
8use rustc_hir::{
9  BodyId,
10  intravisit::{self, Visitor},
11};
12use rustc_index::IndexVec;
13use rustc_middle::ty::TyCtxt;
14use rustc_span::{
15  FileName, RemapPathScopeComponents, SourceFile, Span, source_map::SourceMap,
16};
17#[cfg(feature = "serde")]
18use serde::Serialize;
19#[cfg(feature = "ts-rs")]
20use ts_rs::TS;
21
22use super::filename::{Filename, FilenameIndex};
23use crate::cache::Cache;
24
25struct CharByteMapping {
26  byte_to_char: HashMap<BytePos, CharPos>,
27  char_to_byte: HashMap<CharPos, BytePos>,
28}
29
30impl CharByteMapping {
31  pub fn build(file: &SourceFile) -> Self {
32    let mut byte_to_char = HashMap::default();
33    let mut char_to_byte = HashMap::default();
34
35    macro_rules! check_insert {
36      ($bpos:expr, $cpos:expr) => {
37        let _r = byte_to_char.insert($bpos, $cpos);
38        debug_assert!(
39          _r.is_none(),
40          "byte_to_char: bytepos={:?}, charpos={:?}",
41          $bpos,
42          $cpos
43        );
44        let _r = char_to_byte.insert($cpos, $bpos);
45        debug_assert!(
46          _r.is_none(),
47          "char_to_byte: bytepos={:?}, charpos={:?}",
48          $bpos,
49          $cpos
50        );
51      };
52    }
53
54    for line in 0 .. file.count_lines() {
55      let line_str = file.get_line(line).unwrap();
56      let line_bounds = file.line_bounds(line);
57      let line_start = line_bounds.start.0 as usize;
58      let mut last_column = 0;
59      let mut last_offset = 0;
60      for (column, (byte_offset, c)) in line_str.char_indices().enumerate() {
61        let bpos = BytePos(line_start + byte_offset);
62        let cpos = CharPos { line, column };
63        check_insert!(bpos, cpos);
64        last_column = column + 1;
65        last_offset = byte_offset + c.len_utf8();
66      }
67
68      let bpos = BytePos(line_start + last_offset);
69      let cpos = CharPos {
70        line,
71        column: last_column,
72      };
73      check_insert!(bpos, cpos);
74    }
75
76    CharByteMapping {
77      byte_to_char,
78      char_to_byte,
79    }
80  }
81
82  #[allow(unused)]
83  pub fn byte_to_char(&self, pos: BytePos) -> CharPos {
84    *self
85      .byte_to_char
86      .get(&pos)
87      .unwrap_or_else(|| panic!("Could not find char pos for {pos:?}"))
88  }
89
90  pub fn char_to_byte(&self, pos: CharPos) -> BytePos {
91    *self
92      .char_to_byte
93      .get(&pos)
94      .unwrap_or_else(|| panic!("Could not find byte pos for {pos:?}"))
95  }
96}
97
98#[derive(Default)]
99pub struct RangeContext {
100  filenames: IndexVec<FilenameIndex, Filename>,
101  path_mapping: HashMap<FilenameIndex, Arc<SourceFile>>,
102  char_byte_mapping: Cache<FilenameIndex, CharByteMapping>,
103}
104
105thread_local! {
106  static CONTEXT: RefCell<RangeContext> = RefCell::new(RangeContext::default());
107}
108
109impl Filename {
110  fn intern_with_ctx(self, ctx: &mut RangeContext) -> FilenameIndex {
111    let existing = ctx.filenames.iter_enumerated().find(|(_, f)| &self == *f);
112    match existing {
113      Some((index, _)) => index,
114      None => ctx.filenames.push(self),
115    }
116  }
117
118  pub fn intern<T: ?Sized + AsRef<OsStr>>(t: &T) -> FilenameIndex {
119    let filename = Filename(PathBuf::from(t));
120    CONTEXT.with(|ctx| filename.intern_with_ctx(&mut ctx.borrow_mut()))
121  }
122}
123
124impl FilenameIndex {
125  pub fn find_source_file(self, source_map: &SourceMap) -> Result<Arc<SourceFile>> {
126    CONTEXT.with(|ctx| {
127      let ctx = &mut *ctx.borrow_mut();
128      match ctx.path_mapping.entry(self) {
129        Entry::Occupied(entry) => Ok(Arc::clone(entry.get())),
130        Entry::Vacant(entry) => {
131          let files = source_map.files();
132          ensure!(
133            ctx.filenames.get(self).is_some(),
134            "Missing file index!"
135          );
136          let filename = &ctx.filenames[self];
137          let filename = filename.0
138            .canonicalize()
139            .unwrap_or_else(|_| filename.0.clone());
140          let rustc_filename = files
141            .iter()
142            .map(|file| &file.name)
143            .find(|name| match &name {
144              // rustc seems to store relative paths to files in the workspace, so if filename is absolute,
145              // we can compare them using Path::ends_with
146              FileName::Real(real_file_name) => {
147                let other = real_file_name.path(RemapPathScopeComponents::DOCUMENTATION).to_path_buf();
148                let canonical = other.canonicalize();
149                let other = canonical.as_ref().unwrap_or(&other);
150                filename.ends_with(other)
151              }
152              _ => false,
153            })
154            .with_context(|| {
155              format!(
156                "Could not find SourceFile for path: {}. Available SourceFiles were: [{}]",
157                filename.display(),
158                files
159                  .iter()
160                  .filter_map(|file| match &file.name {
161                    FileName::Real(other) =>
162                      Some(other.path(RemapPathScopeComponents::DOCUMENTATION).display().to_string()),
163                    _ => None,
164                  })
165                  .collect::<Vec<_>>()
166                  .join(", ")
167              )
168            })?;
169          let file = source_map.get_source_file(rustc_filename).unwrap();
170          entry.insert(Arc::clone(&file));
171          Ok(file)
172        }
173      }
174    })
175  }
176}
177
178#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
179#[cfg_attr(feature = "serde", derive(Serialize))]
180#[cfg_attr(feature = "ts-rs", derive(TS))]
181pub struct BytePos(pub usize);
182
183/// CharPos is designed to match VSCode's vscode.Position type.
184/// Both line and column are 0-based.
185///
186/// A previous version of CharPos used a global character-based index,
187/// naively thinking this was the same as VSCode's notion of an "offset".
188/// However, for files using CRLF line endings, VSCode ignores the `\r`
189/// when computing offsets, while Rustc does not. The unhappy compromise
190/// is to use line-column as a common coordinate system, which is robust
191/// to choice of line endings.
192#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord)]
193#[cfg_attr(feature = "serde", derive(Serialize))]
194#[cfg_attr(feature = "ts-rs", derive(TS))]
195pub struct CharPos {
196  pub line: usize,
197  pub column: usize,
198}
199
200#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
201#[cfg_attr(feature = "serde", derive(Serialize))]
202#[cfg_attr(feature = "ts-rs", derive(TS))]
203pub struct ByteRange {
204  pub start: BytePos,
205  pub end: BytePos,
206  pub filename: FilenameIndex,
207}
208
209/// Data structure for sharing spans outside rustc.
210///
211/// Rustc uses byte indexes to describe ranges of source code, whereas
212/// most Javascript-based editors I've encountered (e.g. VSCode) use
213/// character-based (really grapheme-based) indexes. This data structure
214/// along with [`ByteRange`] helps convert between the two representations.
215#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
216#[cfg_attr(feature = "serde", derive(Serialize))]
217#[cfg_attr(feature = "ts-rs", derive(TS))]
218pub struct CharRange {
219  pub start: CharPos,
220  pub end: CharPos,
221  pub filename: FilenameIndex,
222}
223
224impl ByteRange {
225  pub fn as_char_range(&self, source_map: &SourceMap) -> CharRange {
226    let file = self.filename.find_source_file(source_map).unwrap();
227
228    CONTEXT.with(|ctx| {
229      let ctx = ctx.borrow();
230      let mapping: &CharByteMapping = ctx
231        .char_byte_mapping
232        .get(&self.filename, |_| CharByteMapping::build(&file));
233
234      let char_start = mapping.byte_to_char(self.start);
235      let char_end = mapping.byte_to_char(self.end);
236
237      CharRange {
238        start: char_start,
239        end: char_end,
240        filename: self.filename,
241      }
242    })
243  }
244
245  pub fn from_char_range(
246    char_start: CharPos,
247    char_end: CharPos,
248    filename: FilenameIndex,
249    source_map: &SourceMap,
250  ) -> Result<ByteRange> {
251    let file = filename.find_source_file(source_map)?;
252
253    CONTEXT.with(|ctx| {
254      let ctx = ctx.borrow();
255      let mapping = ctx
256        .char_byte_mapping
257        .get(&filename, |_| CharByteMapping::build(&file));
258      let byte_start = mapping.char_to_byte(char_start);
259      let byte_end = mapping.char_to_byte(char_end);
260      Ok(ByteRange {
261        start: byte_start,
262        end: byte_end,
263        filename,
264      })
265    })
266  }
267
268  pub fn from_span(span: Span, source_map: &SourceMap) -> Result<Self> {
269    CONTEXT.with(|ctx| {
270      let mut ctx = ctx.borrow_mut();
271
272      log::trace!("Converting to range: {span:?}");
273      let file = source_map.lookup_source_file(span.lo());
274      let filename = match &file.name {
275        FileName::Real(real_file_name) => {
276          let filename = real_file_name.path(RemapPathScopeComponents::DOCUMENTATION);
277          Filename(filename.to_path_buf()).intern_with_ctx(&mut ctx)
278        }
279        filename => bail!("Range::from_span doesn't support {filename:?}"),
280      };
281
282      ensure!(
283        source_map.ensure_source_file_source_present(&file),
284        "Could not load source for file: {:?}",
285        file.name
286      );
287      let external = file.external_src.borrow();
288      let _src = file
289        .src
290        .as_deref()
291        .map(String::as_str)
292        .unwrap_or_else(|| external.get_source().as_ref().unwrap());
293
294      let byte_start = BytePos(span.lo().0 as usize);
295      let byte_end = BytePos(span.hi().0 as usize);
296
297      Ok(ByteRange {
298        start: byte_start,
299        end: byte_end,
300        filename,
301      })
302    })
303  }
304
305  pub fn substr(&self, s: &str) -> String {
306    s[self.start.0 .. self.end.0].to_string()
307  }
308}
309
310impl CharRange {
311  pub fn from_span(span: Span, source_map: &SourceMap) -> Result<Self> {
312    let byte_range = ByteRange::from_span(span, source_map)?;
313    Ok(byte_range.as_char_range(source_map))
314  }
315}
316
317/// Used to convert objects into a [`Span`] with access to [`TyCtxt`]
318pub trait ToSpan {
319  fn to_span(&self, tcx: TyCtxt) -> Result<Span>;
320}
321
322impl ToSpan for ByteRange {
323  fn to_span(&self, _tcx: TyCtxt) -> Result<Span> {
324    Ok(Span::with_root_ctxt(
325      rustc_span::BytePos(u32::try_from(self.start.0).unwrap()),
326      rustc_span::BytePos(u32::try_from(self.end.0).unwrap()),
327    ))
328  }
329}
330
331impl ToSpan for CharRange {
332  fn to_span(&self, tcx: TyCtxt) -> Result<Span> {
333    let range = ByteRange::from_char_range(
334      self.start,
335      self.end,
336      self.filename,
337      tcx.sess.source_map(),
338    )?;
339    range.to_span(tcx)
340  }
341}
342
343fn qpath_to_span(tcx: TyCtxt, qpath: String) -> Result<Span> {
344  struct Finder<'tcx> {
345    tcx: TyCtxt<'tcx>,
346    qpath: String,
347    span: Option<Span>,
348  }
349
350  impl<'tcx> Visitor<'tcx> for Finder<'tcx> {
351    fn visit_nested_body(&mut self, id: BodyId) {
352      intravisit::walk_body(self, self.tcx.hir_body(id));
353
354      let local_def_id = self.tcx.hir_body_owner_def_id(id);
355      let function_path = self
356        .tcx
357        .def_path(local_def_id.to_def_id())
358        .to_string_no_crate_verbose();
359      if function_path[2 ..] == self.qpath {
360        self.span = Some(self.tcx.hir_span(id.hir_id));
361      }
362    }
363  }
364
365  let mut finder = Finder {
366    tcx,
367    qpath,
368    span: None,
369  };
370  tcx.hir_visit_all_item_likes_in_crate(&mut finder);
371  finder
372    .span
373    .with_context(|| format!("No function with qpath {}", finder.qpath))
374}
375
376/// An externally-provided identifier of a function
377pub enum FunctionIdentifier {
378  /// Name of a function
379  Qpath(String),
380
381  /// Range of code possibly inside a function
382  Range(CharRange),
383}
384
385impl ToSpan for FunctionIdentifier {
386  fn to_span(&self, tcx: TyCtxt) -> Result<Span> {
387    match self {
388      FunctionIdentifier::Qpath(qpath) => qpath_to_span(tcx, qpath.clone()),
389      FunctionIdentifier::Range(range) => range.to_span(tcx),
390    }
391  }
392}
393
394#[cfg(test)]
395mod test {
396  use super::*;
397  use crate::test_utils::{self, CompileResult};
398
399  #[test]
400  fn test_range() {
401    let emoji = "🦀";
402    let input = &format!(
403      r#"fn main() {{
404  let x = "{emoji}";
405}}
406
407// mysterious bytes
408"#
409    );
410
411    test_utils::CompileBuilder::new(input).compile(|CompileResult { tcx }| {
412      let source_map = tcx.sess.source_map();
413      let filename = Filename::intern("dummy.rs");
414      filename.find_source_file(source_map).unwrap();
415
416      let id = FunctionIdentifier::Qpath(String::from("main"));
417      id.to_span(tcx).unwrap();
418
419      let id = FunctionIdentifier::Qpath(String::from("foobar"));
420      id.to_span(tcx).unwrap_err();
421
422      let id = FunctionIdentifier::Range(CharRange {
423        start: CharPos { line: 0, column: 0 },
424        end: CharPos { line: 0, column: 1 },
425        filename,
426      });
427      id.to_span(tcx).unwrap();
428
429      let emoji_index = input.find(emoji).unwrap();
430      let byte_range = ByteRange {
431        start: BytePos(emoji_index),
432        end: BytePos(emoji_index + emoji.len()),
433        filename,
434      };
435      let char_range = byte_range.as_char_range(source_map);
436      let emoji_line = 1;
437      let emoji_column = 11;
438      assert_eq!(char_range, CharRange {
439        start: CharPos {
440          line: emoji_line,
441          column: emoji_column
442        },
443        end: CharPos {
444          line: emoji_line,
445          column: emoji_column + 1
446        },
447        filename
448      });
449    });
450  }
451}
rustc_utils/source_map/range.rs

rustc_utils/source_map/
range.rs
