src/libsyntax/codemap.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! The CodeMap tracks all the source code used within a single crate, mapping
  12 //! from integer byte positions to the original source code location. Each bit
  13 //! of source parsed during crate parsing (typically files, in-memory strings,
  14 //! or various bits of macro expansion) cover a continuous range of bytes in the
  15 //! CodeMap and are represented by FileMaps. Byte positions are stored in
  16 //! `spans` and used pervasively in the compiler. They are absolute positions
  17 //! within the CodeMap, which upon request can be converted to line and column
  18 //! information, source code snippets, etc.
  19
  20 pub use self::ExpnFormat::*;
  21
  22 use std::cell::RefCell;
  23 use std::path::{Path,PathBuf};
  24 use std::rc::Rc;
  25
  26 use std::env;
  27 use std::fs;
  28 use std::io::{self, Read};
  29 pub use syntax_pos::*;
  30 use errors::CodeMapper;
  31
  32 use ast::Name;
  33
  34 /// Return the span itself if it doesn't come from a macro expansion,
  35 /// otherwise return the call site span up to the `enclosing_sp` by
  36 /// following the `expn_info` chain.
  37 pub fn original_sp(cm: &CodeMap, sp: Span, enclosing_sp: Span) -> Span {
  38     let call_site1 = cm.with_expn_info(sp.expn_id, |ei| ei.map(|ei| ei.call_site));
  39     let call_site2 = cm.with_expn_info(enclosing_sp.expn_id, |ei| ei.map(|ei| ei.call_site));
  40     match (call_site1, call_site2) {
  41         (None, _) => sp,
  42         (Some(call_site1), Some(call_site2)) if call_site1 == call_site2 => sp,
  43         (Some(call_site1), _) => original_sp(cm, call_site1, enclosing_sp),
  44     }
  45 }
  46
  47 /// The source of expansion.
  48 #[derive(Clone, Hash, Debug, PartialEq, Eq)]
  49 pub enum ExpnFormat {
  50     /// e.g. #[derive(...)] <item>
  51     MacroAttribute(Name),
  52     /// e.g. `format!()`
  53     MacroBang(Name),
  54 }
  55
  56 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
  57 pub struct Spanned<T> {
  58     pub node: T,
  59     pub span: Span,
  60 }
  61
  62 pub fn spanned<T>(lo: BytePos, hi: BytePos, t: T) -> Spanned<T> {
  63     respan(mk_sp(lo, hi), t)
  64 }
  65
  66 pub fn respan<T>(sp: Span, t: T) -> Spanned<T> {
  67     Spanned {node: t, span: sp}
  68 }
  69
  70 pub fn dummy_spanned<T>(t: T) -> Spanned<T> {
  71     respan(DUMMY_SP, t)
  72 }
  73
  74 #[derive(Clone, Hash, Debug)]
  75 pub struct NameAndSpan {
  76     /// The format with which the macro was invoked.
  77     pub format: ExpnFormat,
  78     /// Whether the macro is allowed to use #[unstable]/feature-gated
  79     /// features internally without forcing the whole crate to opt-in
  80     /// to them.
  81     pub allow_internal_unstable: bool,
  82     /// The span of the macro definition itself. The macro may not
  83     /// have a sensible definition span (e.g. something defined
  84     /// completely inside libsyntax) in which case this is None.
  85     pub span: Option<Span>
  86 }
  87
  88 impl NameAndSpan {
  89     pub fn name(&self) -> Name {
  90         match self.format {
  91             ExpnFormat::MacroAttribute(s) => s,
  92             ExpnFormat::MacroBang(s) => s,
  93         }
  94     }
  95 }
  96
  97 /// Extra information for tracking spans of macro and syntax sugar expansion
  98 #[derive(Hash, Debug)]
  99 pub struct ExpnInfo {
 100     /// The location of the actual macro invocation or syntax sugar , e.g.
 101     /// `let x = foo!();` or `if let Some(y) = x {}`
 102     ///
 103     /// This may recursively refer to other macro invocations, e.g. if
 104     /// `foo!()` invoked `bar!()` internally, and there was an
 105     /// expression inside `bar!`; the call_site of the expression in
 106     /// the expansion would point to the `bar!` invocation; that
 107     /// call_site span would have its own ExpnInfo, with the call_site
 108     /// pointing to the `foo!` invocation.
 109     pub call_site: Span,
 110     /// Information about the expansion.
 111     pub callee: NameAndSpan
 112 }
 113
 114 // _____________________________________________________________________________
 115 // FileMap, MultiByteChar, FileName, FileLines
 116 //
 117
 118 /// An abstraction over the fs operations used by the Parser.
 119 pub trait FileLoader {
 120     /// Query the existence of a file.
 121     fn file_exists(&self, path: &Path) -> bool;
 122
 123     /// Return an absolute path to a file, if possible.
 124     fn abs_path(&self, path: &Path) -> Option<PathBuf>;
 125
 126     /// Read the contents of an UTF-8 file into memory.
 127     fn read_file(&self, path: &Path) -> io::Result<String>;
 128 }
 129
 130 /// A FileLoader that uses std::fs to load real files.
 131 pub struct RealFileLoader;
 132
 133 impl FileLoader for RealFileLoader {
 134     fn file_exists(&self, path: &Path) -> bool {
 135         fs::metadata(path).is_ok()
 136     }
 137
 138     fn abs_path(&self, path: &Path) -> Option<PathBuf> {
 139         if path.is_absolute() {
 140             Some(path.to_path_buf())
 141         } else {
 142             env::current_dir()
 143                 .ok()
 144                 .map(|cwd| cwd.join(path))
 145         }
 146     }
 147
 148     fn read_file(&self, path: &Path) -> io::Result<String> {
 149         let mut src = String::new();
 150         fs::File::open(path)?.read_to_string(&mut src)?;
 151         Ok(src)
 152     }
 153 }
 154
 155 // _____________________________________________________________________________
 156 // CodeMap
 157 //
 158
 159 pub struct CodeMap {
 160     pub files: RefCell<Vec<Rc<FileMap>>>,
 161     expansions: RefCell<Vec<ExpnInfo>>,
 162     file_loader: Box<FileLoader>
 163 }
 164
 165 impl CodeMap {
 166     pub fn new() -> CodeMap {
 167         CodeMap {
 168             files: RefCell::new(Vec::new()),
 169             expansions: RefCell::new(Vec::new()),
 170             file_loader: Box::new(RealFileLoader)
 171         }
 172     }
 173
 174     pub fn with_file_loader(file_loader: Box<FileLoader>) -> CodeMap {
 175         CodeMap {
 176             files: RefCell::new(Vec::new()),
 177             expansions: RefCell::new(Vec::new()),
 178             file_loader: file_loader
 179         }
 180     }
 181
 182     pub fn file_exists(&self, path: &Path) -> bool {
 183         self.file_loader.file_exists(path)
 184     }
 185
 186     pub fn load_file(&self, path: &Path) -> io::Result<Rc<FileMap>> {
 187         let src = self.file_loader.read_file(path)?;
 188         let abs_path = self.file_loader.abs_path(path).map(|p| p.to_str().unwrap().to_string());
 189         Ok(self.new_filemap(path.to_str().unwrap().to_string(), abs_path, src))
 190     }
 191
 192     fn next_start_pos(&self) -> usize {
 193         let files = self.files.borrow();
 194         match files.last() {
 195             None => 0,
 196             // Add one so there is some space between files. This lets us distinguish
 197             // positions in the codemap, even in the presence of zero-length files.
 198             Some(last) => last.end_pos.to_usize() + 1,
 199         }
 200     }
 201
 202     /// Creates a new filemap without setting its line information. If you don't
 203     /// intend to set the line information yourself, you should use new_filemap_and_lines.
 204     pub fn new_filemap(&self, filename: FileName, abs_path: Option<FileName>,
 205                        mut src: String) -> Rc<FileMap> {
 206         let start_pos = self.next_start_pos();
 207         let mut files = self.files.borrow_mut();
 208
 209         // Remove utf-8 BOM if any.
 210         if src.starts_with("\u{feff}") {
 211             src.drain(..3);
 212         }
 213
 214         let end_pos = start_pos + src.len();
 215
 216         let filemap = Rc::new(FileMap {
 217             name: filename,
 218             abs_path: abs_path,
 219             src: Some(Rc::new(src)),
 220             start_pos: Pos::from_usize(start_pos),
 221             end_pos: Pos::from_usize(end_pos),
 222             lines: RefCell::new(Vec::new()),
 223             multibyte_chars: RefCell::new(Vec::new()),
 224         });
 225
 226         files.push(filemap.clone());
 227
 228         filemap
 229     }
 230
 231     /// Creates a new filemap and sets its line information.
 232     pub fn new_filemap_and_lines(&self, filename: &str, abs_path: Option<&str>,
 233                                  src: &str) -> Rc<FileMap> {
 234         let fm = self.new_filemap(filename.to_string(),
 235                                   abs_path.map(|s| s.to_owned()),
 236                                   src.to_owned());
 237         let mut byte_pos: u32 = fm.start_pos.0;
 238         for line in src.lines() {
 239             // register the start of this line
 240             fm.next_line(BytePos(byte_pos));
 241
 242             // update byte_pos to include this line and the \n at the end
 243             byte_pos += line.len() as u32 + 1;
 244         }
 245         fm
 246     }
 247
 248
 249     /// Allocates a new FileMap representing a source file from an external
 250     /// crate. The source code of such an "imported filemap" is not available,
 251     /// but we still know enough to generate accurate debuginfo location
 252     /// information for things inlined from other crates.
 253     pub fn new_imported_filemap(&self,
 254                                 filename: FileName,
 255                                 abs_path: Option<FileName>,
 256                                 source_len: usize,
 257                                 mut file_local_lines: Vec<BytePos>,
 258                                 mut file_local_multibyte_chars: Vec<MultiByteChar>)
 259                                 -> Rc<FileMap> {
 260         let start_pos = self.next_start_pos();
 261         let mut files = self.files.borrow_mut();
 262
 263         let end_pos = Pos::from_usize(start_pos + source_len);
 264         let start_pos = Pos::from_usize(start_pos);
 265
 266         for pos in &mut file_local_lines {
 267             *pos = *pos + start_pos;
 268         }
 269
 270         for mbc in &mut file_local_multibyte_chars {
 271             mbc.pos = mbc.pos + start_pos;
 272         }
 273
 274         let filemap = Rc::new(FileMap {
 275             name: filename,
 276             abs_path: abs_path,
 277             src: None,
 278             start_pos: start_pos,
 279             end_pos: end_pos,
 280             lines: RefCell::new(file_local_lines),
 281             multibyte_chars: RefCell::new(file_local_multibyte_chars),
 282         });
 283
 284         files.push(filemap.clone());
 285
 286         filemap
 287     }
 288
 289     pub fn mk_substr_filename(&self, sp: Span) -> String {
 290         let pos = self.lookup_char_pos(sp.lo);
 291         (format!("<{}:{}:{}>",
 292                  pos.file.name,
 293                  pos.line,
 294                  pos.col.to_usize() + 1)).to_string()
 295     }
 296
 297     /// Lookup source information about a BytePos
 298     pub fn lookup_char_pos(&self, pos: BytePos) -> Loc {
 299         let chpos = self.bytepos_to_file_charpos(pos);
 300         match self.lookup_line(pos) {
 301             Ok(FileMapAndLine { fm: f, line: a }) => {
 302                 let line = a + 1; // Line numbers start at 1
 303                 let linebpos = (*f.lines.borrow())[a];
 304                 let linechpos = self.bytepos_to_file_charpos(linebpos);
 305                 debug!("byte pos {:?} is on the line at byte pos {:?}",
 306                        pos, linebpos);
 307                 debug!("char pos {:?} is on the line at char pos {:?}",
 308                        chpos, linechpos);
 309                 debug!("byte is on line: {}", line);
 310                 assert!(chpos >= linechpos);
 311                 Loc {
 312                     file: f,
 313                     line: line,
 314                     col: chpos - linechpos,
 315                 }
 316             }
 317             Err(f) => {
 318                 Loc {
 319                     file: f,
 320                     line: 0,
 321                     col: chpos,
 322                 }
 323             }
 324         }
 325     }
 326
 327     // If the relevant filemap is empty, we don't return a line number.
 328     fn lookup_line(&self, pos: BytePos) -> Result<FileMapAndLine, Rc<FileMap>> {
 329         let idx = self.lookup_filemap_idx(pos);
 330
 331         let files = self.files.borrow();
 332         let f = (*files)[idx].clone();
 333
 334         let len = f.lines.borrow().len();
 335         if len == 0 {
 336             return Err(f);
 337         }
 338
 339         let mut a = 0;
 340         {
 341             let lines = f.lines.borrow();
 342             let mut b = lines.len();
 343             while b - a > 1 {
 344                 let m = (a + b) / 2;
 345                 if (*lines)[m] > pos {
 346                     b = m;
 347                 } else {
 348                     a = m;
 349                 }
 350             }
 351             assert!(a <= lines.len());
 352         }
 353         Ok(FileMapAndLine { fm: f, line: a })
 354     }
 355
 356     pub fn lookup_char_pos_adj(&self, pos: BytePos) -> LocWithOpt {
 357         let loc = self.lookup_char_pos(pos);
 358         LocWithOpt {
 359             filename: loc.file.name.to_string(),
 360             line: loc.line,
 361             col: loc.col,
 362             file: Some(loc.file)
 363         }
 364     }
 365
 366     pub fn span_to_string(&self, sp: Span) -> String {
 367         if sp == COMMAND_LINE_SP {
 368             return "<command line option>".to_string();
 369         }
 370
 371         if self.files.borrow().is_empty() && sp.source_equal(&DUMMY_SP) {
 372             return "no-location".to_string();
 373         }
 374
 375         let lo = self.lookup_char_pos_adj(sp.lo);
 376         let hi = self.lookup_char_pos_adj(sp.hi);
 377         return (format!("{}:{}:{}: {}:{}",
 378                         lo.filename,
 379                         lo.line,
 380                         lo.col.to_usize() + 1,
 381                         hi.line,
 382                         hi.col.to_usize() + 1)).to_string()
 383     }
 384
 385     // Returns true if two spans have the same callee
 386     // (Assumes the same ExpnFormat implies same callee)
 387     fn match_callees(&self, sp_a: &Span, sp_b: &Span) -> bool {
 388         let fmt_a = self
 389             .with_expn_info(sp_a.expn_id,
 390                             |ei| ei.map(|ei| ei.callee.format.clone()));
 391
 392         let fmt_b = self
 393             .with_expn_info(sp_b.expn_id,
 394                             |ei| ei.map(|ei| ei.callee.format.clone()));
 395         fmt_a == fmt_b
 396     }
 397
 398     /// Returns a formatted string showing the expansion chain of a span
 399     ///
 400     /// Spans are printed in the following format:
 401     ///
 402     /// filename:start_line:col: end_line:col
 403     /// snippet
 404     ///   Callee:
 405     ///   Callee span
 406     ///   Callsite:
 407     ///   Callsite span
 408     ///
 409     /// Callees and callsites are printed recursively (if available, otherwise header
 410     /// and span is omitted), expanding into their own callee/callsite spans.
 411     /// Each layer of recursion has an increased indent, and snippets are truncated
 412     /// to at most 50 characters. Finally, recursive calls to the same macro are squashed,
 413     /// with '...' used to represent any number of recursive calls.
 414     pub fn span_to_expanded_string(&self, sp: Span) -> String {
 415         self.span_to_expanded_string_internal(sp, "")
 416     }
 417
 418     fn span_to_expanded_string_internal(&self, sp:Span, indent: &str) -> String {
 419         let mut indent = indent.to_owned();
 420         let mut output = "".to_owned();
 421         let span_str = self.span_to_string(sp);
 422         let mut span_snip = self.span_to_snippet(sp)
 423             .unwrap_or("Snippet unavailable".to_owned());
 424
 425         // Truncate by code points - in worst case this will be more than 50 characters,
 426         // but ensures at least 50 characters and respects byte boundaries.
 427         let char_vec: Vec<(usize, char)> = span_snip.char_indices().collect();
 428         if char_vec.len() > 50 {
 429             span_snip.truncate(char_vec[49].0);
 430             span_snip.push_str("...");
 431         }
 432
 433         output.push_str(&format!("{}{}\n{}`{}`\n", indent, span_str, indent, span_snip));
 434
 435         if sp.expn_id == NO_EXPANSION || sp.expn_id == COMMAND_LINE_EXPN {
 436             return output;
 437         }
 438
 439         let mut callee = self.with_expn_info(sp.expn_id,
 440                                              |ei| ei.and_then(|ei| ei.callee.span.clone()));
 441         let mut callsite = self.with_expn_info(sp.expn_id,
 442                                                |ei| ei.map(|ei| ei.call_site.clone()));
 443
 444         indent.push_str("  ");
 445         let mut is_recursive = false;
 446
 447         while callee.is_some() && self.match_callees(&sp, &callee.unwrap()) {
 448             callee = self.with_expn_info(callee.unwrap().expn_id,
 449                                          |ei| ei.and_then(|ei| ei.callee.span.clone()));
 450             is_recursive = true;
 451         }
 452         if let Some(span) = callee {
 453             output.push_str(&indent);
 454             output.push_str("Callee:\n");
 455             if is_recursive {
 456                 output.push_str(&indent);
 457                 output.push_str("...\n");
 458             }
 459             output.push_str(&(self.span_to_expanded_string_internal(span, &indent)));
 460         }
 461
 462         is_recursive = false;
 463         while callsite.is_some() && self.match_callees(&sp, &callsite.unwrap()) {
 464             callsite = self.with_expn_info(callsite.unwrap().expn_id,
 465                                            |ei| ei.map(|ei| ei.call_site.clone()));
 466             is_recursive = true;
 467         }
 468         if let Some(span) = callsite {
 469             output.push_str(&indent);
 470             output.push_str("Callsite:\n");
 471             if is_recursive {
 472                 output.push_str(&indent);
 473                 output.push_str("...\n");
 474             }
 475             output.push_str(&(self.span_to_expanded_string_internal(span, &indent)));
 476         }
 477         output
 478     }
 479
 480     /// Return the source span - this is either the supplied span, or the span for
 481     /// the macro callsite that expanded to it.
 482     pub fn source_callsite(&self, sp: Span) -> Span {
 483         let mut span = sp;
 484         // Special case - if a macro is parsed as an argument to another macro, the source
 485         // callsite is the first callsite, which is also source-equivalent to the span.
 486         let mut first = true;
 487         while span.expn_id != NO_EXPANSION && span.expn_id != COMMAND_LINE_EXPN {
 488             if let Some(callsite) = self.with_expn_info(span.expn_id,
 489                                                |ei| ei.map(|ei| ei.call_site.clone())) {
 490                 if first && span.source_equal(&callsite) {
 491                     if self.lookup_char_pos(span.lo).file.is_real_file() {
 492                         return Span { expn_id: NO_EXPANSION, .. span };
 493                     }
 494                 }
 495                 first = false;
 496                 span = callsite;
 497             }
 498             else {
 499                 break;
 500             }
 501         }
 502         span
 503     }
 504
 505     /// Return the source callee.
 506     ///
 507     /// Returns None if the supplied span has no expansion trace,
 508     /// else returns the NameAndSpan for the macro definition
 509     /// corresponding to the source callsite.
 510     pub fn source_callee(&self, sp: Span) -> Option<NameAndSpan> {
 511         let mut span = sp;
 512         // Special case - if a macro is parsed as an argument to another macro, the source
 513         // callsite is source-equivalent to the span, and the source callee is the first callee.
 514         let mut first = true;
 515         while let Some(callsite) = self.with_expn_info(span.expn_id,
 516                                             |ei| ei.map(|ei| ei.call_site.clone())) {
 517             if first && span.source_equal(&callsite) {
 518                 if self.lookup_char_pos(span.lo).file.is_real_file() {
 519                     return self.with_expn_info(span.expn_id,
 520                                                |ei| ei.map(|ei| ei.callee.clone()));
 521                 }
 522             }
 523             first = false;
 524             if let Some(_) = self.with_expn_info(callsite.expn_id,
 525                                                  |ei| ei.map(|ei| ei.call_site.clone())) {
 526                 span = callsite;
 527             }
 528             else {
 529                 return self.with_expn_info(span.expn_id,
 530                                            |ei| ei.map(|ei| ei.callee.clone()));
 531             }
 532         }
 533         None
 534     }
 535
 536     pub fn span_to_filename(&self, sp: Span) -> FileName {
 537         self.lookup_char_pos(sp.lo).file.name.to_string()
 538     }
 539
 540     pub fn span_to_lines(&self, sp: Span) -> FileLinesResult {
 541         debug!("span_to_lines(sp={:?})", sp);
 542
 543         if sp.lo > sp.hi {
 544             return Err(SpanLinesError::IllFormedSpan(sp));
 545         }
 546
 547         let lo = self.lookup_char_pos(sp.lo);
 548         debug!("span_to_lines: lo={:?}", lo);
 549         let hi = self.lookup_char_pos(sp.hi);
 550         debug!("span_to_lines: hi={:?}", hi);
 551
 552         if lo.file.start_pos != hi.file.start_pos {
 553             return Err(SpanLinesError::DistinctSources(DistinctSources {
 554                 begin: (lo.file.name.clone(), lo.file.start_pos),
 555                 end: (hi.file.name.clone(), hi.file.start_pos),
 556             }));
 557         }
 558         assert!(hi.line >= lo.line);
 559
 560         let mut lines = Vec::with_capacity(hi.line - lo.line + 1);
 561
 562         // The span starts partway through the first line,
 563         // but after that it starts from offset 0.
 564         let mut start_col = lo.col;
 565
 566         // For every line but the last, it extends from `start_col`
 567         // and to the end of the line. Be careful because the line
 568         // numbers in Loc are 1-based, so we subtract 1 to get 0-based
 569         // lines.
 570         for line_index in lo.line-1 .. hi.line-1 {
 571             let line_len = lo.file.get_line(line_index)
 572                                   .map(|s| s.chars().count())
 573                                   .unwrap_or(0);
 574             lines.push(LineInfo { line_index: line_index,
 575                                   start_col: start_col,
 576                                   end_col: CharPos::from_usize(line_len) });
 577             start_col = CharPos::from_usize(0);
 578         }
 579
 580         // For the last line, it extends from `start_col` to `hi.col`:
 581         lines.push(LineInfo { line_index: hi.line - 1,
 582                               start_col: start_col,
 583                               end_col: hi.col });
 584
 585         Ok(FileLines {file: lo.file, lines: lines})
 586     }
 587
 588     pub fn span_to_snippet(&self, sp: Span) -> Result<String, SpanSnippetError> {
 589         if sp.lo > sp.hi {
 590             return Err(SpanSnippetError::IllFormedSpan(sp));
 591         }
 592
 593         let local_begin = self.lookup_byte_offset(sp.lo);
 594         let local_end = self.lookup_byte_offset(sp.hi);
 595
 596         if local_begin.fm.start_pos != local_end.fm.start_pos {
 597             return Err(SpanSnippetError::DistinctSources(DistinctSources {
 598                 begin: (local_begin.fm.name.clone(),
 599                         local_begin.fm.start_pos),
 600                 end: (local_end.fm.name.clone(),
 601                       local_end.fm.start_pos)
 602             }));
 603         } else {
 604             match local_begin.fm.src {
 605                 Some(ref src) => {
 606                     let start_index = local_begin.pos.to_usize();
 607                     let end_index = local_end.pos.to_usize();
 608                     let source_len = (local_begin.fm.end_pos -
 609                                       local_begin.fm.start_pos).to_usize();
 610
 611                     if start_index > end_index || end_index > source_len {
 612                         return Err(SpanSnippetError::MalformedForCodemap(
 613                             MalformedCodemapPositions {
 614                                 name: local_begin.fm.name.clone(),
 615                                 source_len: source_len,
 616                                 begin_pos: local_begin.pos,
 617                                 end_pos: local_end.pos,
 618                             }));
 619                     }
 620
 621                     return Ok((&src[start_index..end_index]).to_string())
 622                 }
 623                 None => {
 624                     return Err(SpanSnippetError::SourceNotAvailable {
 625                         filename: local_begin.fm.name.clone()
 626                     });
 627                 }
 628             }
 629         }
 630     }
 631
 632     pub fn get_filemap(&self, filename: &str) -> Option<Rc<FileMap>> {
 633         for fm in self.files.borrow().iter() {
 634             if filename == fm.name {
 635                 return Some(fm.clone());
 636             }
 637         }
 638         None
 639     }
 640
 641     /// For a global BytePos compute the local offset within the containing FileMap
 642     pub fn lookup_byte_offset(&self, bpos: BytePos) -> FileMapAndBytePos {
 643         let idx = self.lookup_filemap_idx(bpos);
 644         let fm = (*self.files.borrow())[idx].clone();
 645         let offset = bpos - fm.start_pos;
 646         FileMapAndBytePos {fm: fm, pos: offset}
 647     }
 648
 649     /// Converts an absolute BytePos to a CharPos relative to the filemap.
 650     pub fn bytepos_to_file_charpos(&self, bpos: BytePos) -> CharPos {
 651         let idx = self.lookup_filemap_idx(bpos);
 652         let files = self.files.borrow();
 653         let map = &(*files)[idx];
 654
 655         // The number of extra bytes due to multibyte chars in the FileMap
 656         let mut total_extra_bytes = 0;
 657
 658         for mbc in map.multibyte_chars.borrow().iter() {
 659             debug!("{}-byte char at {:?}", mbc.bytes, mbc.pos);
 660             if mbc.pos < bpos {
 661                 // every character is at least one byte, so we only
 662                 // count the actual extra bytes.
 663                 total_extra_bytes += mbc.bytes - 1;
 664                 // We should never see a byte position in the middle of a
 665                 // character
 666                 assert!(bpos.to_usize() >= mbc.pos.to_usize() + mbc.bytes);
 667             } else {
 668                 break;
 669             }
 670         }
 671
 672         assert!(map.start_pos.to_usize() + total_extra_bytes <= bpos.to_usize());
 673         CharPos(bpos.to_usize() - map.start_pos.to_usize() - total_extra_bytes)
 674     }
 675
 676     // Return the index of the filemap (in self.files) which contains pos.
 677     fn lookup_filemap_idx(&self, pos: BytePos) -> usize {
 678         let files = self.files.borrow();
 679         let files = &*files;
 680         let count = files.len();
 681
 682         // Binary search for the filemap.
 683         let mut a = 0;
 684         let mut b = count;
 685         while b - a > 1 {
 686             let m = (a + b) / 2;
 687             if files[m].start_pos > pos {
 688                 b = m;
 689             } else {
 690                 a = m;
 691             }
 692         }
 693
 694         assert!(a < count, "position {} does not resolve to a source location", pos.to_usize());
 695
 696         return a;
 697     }
 698
 699     pub fn record_expansion(&self, expn_info: ExpnInfo) -> ExpnId {
 700         let mut expansions = self.expansions.borrow_mut();
 701         expansions.push(expn_info);
 702         let len = expansions.len();
 703         if len > u32::max_value() as usize {
 704             panic!("too many ExpnInfo's!");
 705         }
 706         ExpnId(len as u32 - 1)
 707     }
 708
 709     pub fn with_expn_info<T, F>(&self, id: ExpnId, f: F) -> T where
 710         F: FnOnce(Option<&ExpnInfo>) -> T,
 711     {
 712         match id {
 713             NO_EXPANSION | COMMAND_LINE_EXPN => f(None),
 714             ExpnId(i) => f(Some(&(*self.expansions.borrow())[i as usize]))
 715         }
 716     }
 717
 718     /// Check if a span is "internal" to a macro in which #[unstable]
 719     /// items can be used (that is, a macro marked with
 720     /// `#[allow_internal_unstable]`).
 721     pub fn span_allows_unstable(&self, span: Span) -> bool {
 722         debug!("span_allows_unstable(span = {:?})", span);
 723         let mut allows_unstable = false;
 724         let mut expn_id = span.expn_id;
 725         loop {
 726             let quit = self.with_expn_info(expn_id, |expninfo| {
 727                 debug!("span_allows_unstable: expninfo = {:?}", expninfo);
 728                 expninfo.map_or(/* hit the top level */ true, |info| {
 729
 730                     let span_comes_from_this_expansion =
 731                         info.callee.span.map_or(span.source_equal(&info.call_site), |mac_span| {
 732                             mac_span.contains(span)
 733                         });
 734
 735                     debug!("span_allows_unstable: span: {:?} call_site: {:?} callee: {:?}",
 736                            (span.lo, span.hi),
 737                            (info.call_site.lo, info.call_site.hi),
 738                            info.callee.span.map(|x| (x.lo, x.hi)));
 739                     debug!("span_allows_unstable: from this expansion? {}, allows unstable? {}",
 740                            span_comes_from_this_expansion,
 741                            info.callee.allow_internal_unstable);
 742                     if span_comes_from_this_expansion {
 743                         allows_unstable = info.callee.allow_internal_unstable;
 744                         // we've found the right place, stop looking
 745                         true
 746                     } else {
 747                         // not the right place, keep looking
 748                         expn_id = info.call_site.expn_id;
 749                         false
 750                     }
 751                 })
 752             });
 753             if quit {
 754                 break
 755             }
 756         }
 757         debug!("span_allows_unstable? {}", allows_unstable);
 758         allows_unstable
 759     }
 760
 761     pub fn count_lines(&self) -> usize {
 762         self.files.borrow().iter().fold(0, |a, f| a + f.count_lines())
 763     }
 764
 765     pub fn macro_backtrace(&self, span: Span) -> Vec<MacroBacktrace> {
 766         let mut last_span = DUMMY_SP;
 767         let mut span = span;
 768         let mut result = vec![];
 769         loop {
 770             let span_name_span = self.with_expn_info(span.expn_id, |expn_info| {
 771                 expn_info.map(|ei| {
 772                     let (pre, post) = match ei.callee.format {
 773                         MacroAttribute(..) => ("#[", "]"),
 774                         MacroBang(..) => ("", "!"),
 775                     };
 776                     let macro_decl_name = format!("{}{}{}",
 777                                                   pre,
 778                                                   ei.callee.name(),
 779                                                   post);
 780                     let def_site_span = ei.callee.span;
 781                     (ei.call_site, macro_decl_name, def_site_span)
 782                 })
 783             });
 784
 785             match span_name_span {
 786                 None => break,
 787                 Some((call_site, macro_decl_name, def_site_span)) => {
 788                     // Don't print recursive invocations
 789                     if !call_site.source_equal(&last_span) {
 790                         result.push(MacroBacktrace {
 791                             call_site: call_site,
 792                             macro_decl_name: macro_decl_name,
 793                             def_site_span: def_site_span,
 794                         });
 795                     }
 796                     last_span = span;
 797                     span = call_site;
 798                 }
 799             }
 800         }
 801         result
 802     }
 803 }
 804
 805 impl CodeMapper for CodeMap {
 806     fn lookup_char_pos(&self, pos: BytePos) -> Loc {
 807         self.lookup_char_pos(pos)
 808     }
 809     fn span_to_lines(&self, sp: Span) -> FileLinesResult {
 810         self.span_to_lines(sp)
 811     }
 812     fn span_to_string(&self, sp: Span) -> String {
 813         self.span_to_string(sp)
 814     }
 815     fn span_to_filename(&self, sp: Span) -> FileName {
 816         self.span_to_filename(sp)
 817     }
 818     fn macro_backtrace(&self, span: Span) -> Vec<MacroBacktrace> {
 819         self.macro_backtrace(span)
 820     }
 821 }
 822
 823 // _____________________________________________________________________________
 824 // Tests
 825 //
 826
 827 #[cfg(test)]
 828 mod tests {
 829     use super::*;
 830     use std::rc::Rc;
 831
 832     #[test]
 833     fn t1 () {
 834         let cm = CodeMap::new();
 835         let fm = cm.new_filemap("blork.rs".to_string(),
 836                                 None,
 837                                 "first line.\nsecond line".to_string());
 838         fm.next_line(BytePos(0));
 839         // Test we can get lines with partial line info.
 840         assert_eq!(fm.get_line(0), Some("first line."));
 841         // TESTING BROKEN BEHAVIOR: line break declared before actual line break.
 842         fm.next_line(BytePos(10));
 843         assert_eq!(fm.get_line(1), Some("."));
 844         fm.next_line(BytePos(12));
 845         assert_eq!(fm.get_line(2), Some("second line"));
 846     }
 847
 848     #[test]
 849     #[should_panic]
 850     fn t2 () {
 851         let cm = CodeMap::new();
 852         let fm = cm.new_filemap("blork.rs".to_string(),
 853                                 None,
 854                                 "first line.\nsecond line".to_string());
 855         // TESTING *REALLY* BROKEN BEHAVIOR:
 856         fm.next_line(BytePos(0));
 857         fm.next_line(BytePos(10));
 858         fm.next_line(BytePos(2));
 859     }
 860
 861     fn init_code_map() -> CodeMap {
 862         let cm = CodeMap::new();
 863         let fm1 = cm.new_filemap("blork.rs".to_string(),
 864                                  None,
 865                                  "first line.\nsecond line".to_string());
 866         let fm2 = cm.new_filemap("empty.rs".to_string(),
 867                                  None,
 868                                  "".to_string());
 869         let fm3 = cm.new_filemap("blork2.rs".to_string(),
 870                                  None,
 871                                  "first line.\nsecond line".to_string());
 872
 873         fm1.next_line(BytePos(0));
 874         fm1.next_line(BytePos(12));
 875         fm2.next_line(fm2.start_pos);
 876         fm3.next_line(fm3.start_pos);
 877         fm3.next_line(fm3.start_pos + BytePos(12));
 878
 879         cm
 880     }
 881
 882     #[test]
 883     fn t3() {
 884         // Test lookup_byte_offset
 885         let cm = init_code_map();
 886
 887         let fmabp1 = cm.lookup_byte_offset(BytePos(23));
 888         assert_eq!(fmabp1.fm.name, "blork.rs");
 889         assert_eq!(fmabp1.pos, BytePos(23));
 890
 891         let fmabp1 = cm.lookup_byte_offset(BytePos(24));
 892         assert_eq!(fmabp1.fm.name, "empty.rs");
 893         assert_eq!(fmabp1.pos, BytePos(0));
 894
 895         let fmabp2 = cm.lookup_byte_offset(BytePos(25));
 896         assert_eq!(fmabp2.fm.name, "blork2.rs");
 897         assert_eq!(fmabp2.pos, BytePos(0));
 898     }
 899
 900     #[test]
 901     fn t4() {
 902         // Test bytepos_to_file_charpos
 903         let cm = init_code_map();
 904
 905         let cp1 = cm.bytepos_to_file_charpos(BytePos(22));
 906         assert_eq!(cp1, CharPos(22));
 907
 908         let cp2 = cm.bytepos_to_file_charpos(BytePos(25));
 909         assert_eq!(cp2, CharPos(0));
 910     }
 911
 912     #[test]
 913     fn t5() {
 914         // Test zero-length filemaps.
 915         let cm = init_code_map();
 916
 917         let loc1 = cm.lookup_char_pos(BytePos(22));
 918         assert_eq!(loc1.file.name, "blork.rs");
 919         assert_eq!(loc1.line, 2);
 920         assert_eq!(loc1.col, CharPos(10));
 921
 922         let loc2 = cm.lookup_char_pos(BytePos(25));
 923         assert_eq!(loc2.file.name, "blork2.rs");
 924         assert_eq!(loc2.line, 1);
 925         assert_eq!(loc2.col, CharPos(0));
 926     }
 927
 928     fn init_code_map_mbc() -> CodeMap {
 929         let cm = CodeMap::new();
 930         // € is a three byte utf8 char.
 931         let fm1 =
 932             cm.new_filemap("blork.rs".to_string(),
 933                            None,
 934                            "fir€st €€€€ line.\nsecond line".to_string());
 935         let fm2 = cm.new_filemap("blork2.rs".to_string(),
 936                                  None,
 937                                  "first line€€.\n€ second line".to_string());
 938
 939         fm1.next_line(BytePos(0));
 940         fm1.next_line(BytePos(28));
 941         fm2.next_line(fm2.start_pos);
 942         fm2.next_line(fm2.start_pos + BytePos(20));
 943
 944         fm1.record_multibyte_char(BytePos(3), 3);
 945         fm1.record_multibyte_char(BytePos(9), 3);
 946         fm1.record_multibyte_char(BytePos(12), 3);
 947         fm1.record_multibyte_char(BytePos(15), 3);
 948         fm1.record_multibyte_char(BytePos(18), 3);
 949         fm2.record_multibyte_char(fm2.start_pos + BytePos(10), 3);
 950         fm2.record_multibyte_char(fm2.start_pos + BytePos(13), 3);
 951         fm2.record_multibyte_char(fm2.start_pos + BytePos(18), 3);
 952
 953         cm
 954     }
 955
 956     #[test]
 957     fn t6() {
 958         // Test bytepos_to_file_charpos in the presence of multi-byte chars
 959         let cm = init_code_map_mbc();
 960
 961         let cp1 = cm.bytepos_to_file_charpos(BytePos(3));
 962         assert_eq!(cp1, CharPos(3));
 963
 964         let cp2 = cm.bytepos_to_file_charpos(BytePos(6));
 965         assert_eq!(cp2, CharPos(4));
 966
 967         let cp3 = cm.bytepos_to_file_charpos(BytePos(56));
 968         assert_eq!(cp3, CharPos(12));
 969
 970         let cp4 = cm.bytepos_to_file_charpos(BytePos(61));
 971         assert_eq!(cp4, CharPos(15));
 972     }
 973
 974     #[test]
 975     fn t7() {
 976         // Test span_to_lines for a span ending at the end of filemap
 977         let cm = init_code_map();
 978         let span = Span {lo: BytePos(12), hi: BytePos(23), expn_id: NO_EXPANSION};
 979         let file_lines = cm.span_to_lines(span).unwrap();
 980
 981         assert_eq!(file_lines.file.name, "blork.rs");
 982         assert_eq!(file_lines.lines.len(), 1);
 983         assert_eq!(file_lines.lines[0].line_index, 1);
 984     }
 985
 986     /// Given a string like " ~~~~~~~~~~~~ ", produces a span
 987     /// coverting that range. The idea is that the string has the same
 988     /// length as the input, and we uncover the byte positions.  Note
 989     /// that this can span lines and so on.
 990     fn span_from_selection(input: &str, selection: &str) -> Span {
 991         assert_eq!(input.len(), selection.len());
 992         let left_index = selection.find('~').unwrap() as u32;
 993         let right_index = selection.rfind('~').map(|x|x as u32).unwrap_or(left_index);
 994         Span { lo: BytePos(left_index), hi: BytePos(right_index + 1), expn_id: NO_EXPANSION }
 995     }
 996
 997     /// Test span_to_snippet and span_to_lines for a span coverting 3
 998     /// lines in the middle of a file.
 999     #[test]
1000     fn span_to_snippet_and_lines_spanning_multiple_lines() {
1001         let cm = CodeMap::new();
1002         let inputtext = "aaaaa\nbbbbBB\nCCC\nDDDDDddddd\neee\n";
1003         let selection = "     \n    ~~\n~~~\n~~~~~     \n   \n";
1004         cm.new_filemap_and_lines("blork.rs", None, inputtext);
1005         let span = span_from_selection(inputtext, selection);
1006
1007         // check that we are extracting the text we thought we were extracting
1008         assert_eq!(&cm.span_to_snippet(span).unwrap(), "BB\nCCC\nDDDDD");
1009
1010         // check that span_to_lines gives us the complete result with the lines/cols we expected
1011         let lines = cm.span_to_lines(span).unwrap();
1012         let expected = vec![
1013             LineInfo { line_index: 1, start_col: CharPos(4), end_col: CharPos(6) },
1014             LineInfo { line_index: 2, start_col: CharPos(0), end_col: CharPos(3) },
1015             LineInfo { line_index: 3, start_col: CharPos(0), end_col: CharPos(5) }
1016             ];
1017         assert_eq!(lines.lines, expected);
1018     }
1019
1020     #[test]
1021     fn t8() {
1022         // Test span_to_snippet for a span ending at the end of filemap
1023         let cm = init_code_map();
1024         let span = Span {lo: BytePos(12), hi: BytePos(23), expn_id: NO_EXPANSION};
1025         let snippet = cm.span_to_snippet(span);
1026
1027         assert_eq!(snippet, Ok("second line".to_string()));
1028     }
1029
1030     #[test]
1031     fn t9() {
1032         // Test span_to_str for a span ending at the end of filemap
1033         let cm = init_code_map();
1034         let span = Span {lo: BytePos(12), hi: BytePos(23), expn_id: NO_EXPANSION};
1035         let sstr =  cm.span_to_string(span);
1036
1037         assert_eq!(sstr, "blork.rs:2:1: 2:12");
1038     }
1039
1040     #[test]
1041     fn t10() {
1042         // Test span_to_expanded_string works in base case (no expansion)
1043         let cm = init_code_map();
1044         let span = Span { lo: BytePos(0), hi: BytePos(11), expn_id: NO_EXPANSION };
1045         let sstr = cm.span_to_expanded_string(span);
1046         assert_eq!(sstr, "blork.rs:1:1: 1:12\n`first line.`\n");
1047
1048         let span = Span { lo: BytePos(12), hi: BytePos(23), expn_id: NO_EXPANSION };
1049         let sstr =  cm.span_to_expanded_string(span);
1050         assert_eq!(sstr, "blork.rs:2:1: 2:12\n`second line`\n");
1051     }
1052
1053     #[test]
1054     fn t11() {
1055         // Test span_to_expanded_string works with expansion
1056         use ast::Name;
1057         let cm = init_code_map();
1058         let root = Span { lo: BytePos(0), hi: BytePos(11), expn_id: NO_EXPANSION };
1059         let format = ExpnFormat::MacroBang(Name(0u32));
1060         let callee = NameAndSpan { format: format,
1061                                    allow_internal_unstable: false,
1062                                    span: None };
1063
1064         let info = ExpnInfo { call_site: root, callee: callee };
1065         let id = cm.record_expansion(info);
1066         let sp = Span { lo: BytePos(12), hi: BytePos(23), expn_id: id };
1067
1068         let sstr = cm.span_to_expanded_string(sp);
1069         assert_eq!(sstr,
1070                    "blork.rs:2:1: 2:12\n`second line`\n  Callsite:\n  \
1071                     blork.rs:1:1: 1:12\n  `first line.`\n");
1072     }
1073
1074     /// Returns the span corresponding to the `n`th occurrence of
1075     /// `substring` in `source_text`.
1076     trait CodeMapExtension {
1077         fn span_substr(&self,
1078                     file: &Rc<FileMap>,
1079                     source_text: &str,
1080                     substring: &str,
1081                     n: usize)
1082                     -> Span;
1083     }
1084
1085     impl CodeMapExtension for CodeMap {
1086         fn span_substr(&self,
1087                     file: &Rc<FileMap>,
1088                     source_text: &str,
1089                     substring: &str,
1090                     n: usize)
1091                     -> Span
1092         {
1093             println!("span_substr(file={:?}/{:?}, substring={:?}, n={})",
1094                     file.name, file.start_pos, substring, n);
1095             let mut i = 0;
1096             let mut hi = 0;
1097             loop {
1098                 let offset = source_text[hi..].find(substring).unwrap_or_else(|| {
1099                     panic!("source_text `{}` does not have {} occurrences of `{}`, only {}",
1100                         source_text, n, substring, i);
1101                 });
1102                 let lo = hi + offset;
1103                 hi = lo + substring.len();
1104                 if i == n {
1105                     let span = Span {
1106                         lo: BytePos(lo as u32 + file.start_pos.0),
1107                         hi: BytePos(hi as u32 + file.start_pos.0),
1108                         expn_id: NO_EXPANSION,
1109                     };
1110                     assert_eq!(&self.span_to_snippet(span).unwrap()[..],
1111                             substring);
1112                     return span;
1113                 }
1114                 i += 1;
1115             }
1116         }
1117     }
1118
1119     fn init_expansion_chain(cm: &CodeMap) -> Span {
1120         // Creates an expansion chain containing two recursive calls
1121         // root -> expA -> expA -> expB -> expB -> end
1122         use ast::Name;
1123
1124         let root = Span { lo: BytePos(0), hi: BytePos(11), expn_id: NO_EXPANSION };
1125
1126         let format_root = ExpnFormat::MacroBang(Name(0u32));
1127         let callee_root = NameAndSpan { format: format_root,
1128                                         allow_internal_unstable: false,
1129                                         span: Some(root) };
1130
1131         let info_a1 = ExpnInfo { call_site: root, callee: callee_root };
1132         let id_a1 = cm.record_expansion(info_a1);
1133         let span_a1 = Span { lo: BytePos(12), hi: BytePos(23), expn_id: id_a1 };
1134
1135         let format_a = ExpnFormat::MacroBang(Name(1u32));
1136         let callee_a = NameAndSpan { format: format_a,
1137                                       allow_internal_unstable: false,
1138                                       span: Some(span_a1) };
1139
1140         let info_a2 = ExpnInfo { call_site: span_a1, callee: callee_a.clone() };
1141         let id_a2 = cm.record_expansion(info_a2);
1142         let span_a2 = Span { lo: BytePos(12), hi: BytePos(23), expn_id: id_a2 };
1143
1144         let info_b1 = ExpnInfo { call_site: span_a2, callee: callee_a };
1145         let id_b1 = cm.record_expansion(info_b1);
1146         let span_b1 = Span { lo: BytePos(25), hi: BytePos(36), expn_id: id_b1 };
1147
1148         let format_b = ExpnFormat::MacroBang(Name(2u32));
1149         let callee_b = NameAndSpan { format: format_b,
1150                                      allow_internal_unstable: false,
1151                                      span: None };
1152
1153         let info_b2 = ExpnInfo { call_site: span_b1, callee: callee_b.clone() };
1154         let id_b2 = cm.record_expansion(info_b2);
1155         let span_b2 = Span { lo: BytePos(25), hi: BytePos(36), expn_id: id_b2 };
1156
1157         let info_end = ExpnInfo { call_site: span_b2, callee: callee_b };
1158         let id_end = cm.record_expansion(info_end);
1159         Span { lo: BytePos(37), hi: BytePos(48), expn_id: id_end }
1160     }
1161
1162     #[test]
1163     fn t12() {
1164         // Test span_to_expanded_string collapses recursive macros and handles
1165         // recursive callsite and callee expansions
1166         let cm = init_code_map();
1167         let end = init_expansion_chain(&cm);
1168         let sstr = cm.span_to_expanded_string(end);
1169         let res_str =
1170 r"blork2.rs:2:1: 2:12
1171 `second line`
1172   Callsite:
1173   ...
1174   blork2.rs:1:1: 1:12
1175   `first line.`
1176     Callee:
1177     blork.rs:2:1: 2:12
1178     `second line`
1179       Callee:
1180       blork.rs:1:1: 1:12
1181       `first line.`
1182       Callsite:
1183       blork.rs:1:1: 1:12
1184       `first line.`
1185     Callsite:
1186     ...
1187     blork.rs:2:1: 2:12
1188     `second line`
1189       Callee:
1190       blork.rs:1:1: 1:12
1191       `first line.`
1192       Callsite:
1193       blork.rs:1:1: 1:12
1194       `first line.`
1195 ";
1196         assert_eq!(sstr, res_str);
1197     }
1198 }