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 syntax_pos::*;
  21 pub use syntax_pos::hygiene::{ExpnFormat, ExpnInfo, NameAndSpan};
  22 pub use self::ExpnFormat::*;
  23
  24 use std::cell::{RefCell, Ref};
  25 use std::path::{Path, PathBuf};
  26 use std::rc::Rc;
  27
  28 use std::env;
  29 use std::fs;
  30 use std::io::{self, Read};
  31 use errors::CodeMapper;
  32
  33 /// Return the span itself if it doesn't come from a macro expansion,
  34 /// otherwise return the call site span up to the `enclosing_sp` by
  35 /// following the `expn_info` chain.
  36 pub fn original_sp(sp: Span, enclosing_sp: Span) -> Span {
  37     let call_site1 = sp.ctxt.outer().expn_info().map(|ei| ei.call_site);
  38     let call_site2 = enclosing_sp.ctxt.outer().expn_info().map(|ei| ei.call_site);
  39     match (call_site1, call_site2) {
  40         (None, _) => sp,
  41         (Some(call_site1), Some(call_site2)) if call_site1 == call_site2 => sp,
  42         (Some(call_site1), _) => original_sp(call_site1, enclosing_sp),
  43     }
  44 }
  45
  46 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
  47 pub struct Spanned<T> {
  48     pub node: T,
  49     pub span: Span,
  50 }
  51
  52 pub fn respan<T>(sp: Span, t: T) -> Spanned<T> {
  53     Spanned {node: t, span: sp}
  54 }
  55
  56 pub fn dummy_spanned<T>(t: T) -> Spanned<T> {
  57     respan(DUMMY_SP, t)
  58 }
  59
  60 // _____________________________________________________________________________
  61 // FileMap, MultiByteChar, FileName, FileLines
  62 //
  63
  64 /// An abstraction over the fs operations used by the Parser.
  65 pub trait FileLoader {
  66     /// Query the existence of a file.
  67     fn file_exists(&self, path: &Path) -> bool;
  68
  69     /// Return an absolute path to a file, if possible.
  70     fn abs_path(&self, path: &Path) -> Option<PathBuf>;
  71
  72     /// Read the contents of an UTF-8 file into memory.
  73     fn read_file(&self, path: &Path) -> io::Result<String>;
  74 }
  75
  76 /// A FileLoader that uses std::fs to load real files.
  77 pub struct RealFileLoader;
  78
  79 impl FileLoader for RealFileLoader {
  80     fn file_exists(&self, path: &Path) -> bool {
  81         fs::metadata(path).is_ok()
  82     }
  83
  84     fn abs_path(&self, path: &Path) -> Option<PathBuf> {
  85         if path.is_absolute() {
  86             Some(path.to_path_buf())
  87         } else {
  88             env::current_dir()
  89                 .ok()
  90                 .map(|cwd| cwd.join(path))
  91         }
  92     }
  93
  94     fn read_file(&self, path: &Path) -> io::Result<String> {
  95         let mut src = String::new();
  96         fs::File::open(path)?.read_to_string(&mut src)?;
  97         Ok(src)
  98     }
  99 }
 100
 101 // _____________________________________________________________________________
 102 // CodeMap
 103 //
 104
 105 pub struct CodeMap {
 106     pub(super) files: RefCell<Vec<Rc<FileMap>>>,
 107     file_loader: Box<FileLoader>,
 108     // This is used to apply the file path remapping as specified via
 109     // -Zremap-path-prefix to all FileMaps allocated within this CodeMap.
 110     path_mapping: FilePathMapping,
 111 }
 112
 113 impl CodeMap {
 114     pub fn new(path_mapping: FilePathMapping) -> CodeMap {
 115         CodeMap {
 116             files: RefCell::new(Vec::new()),
 117             file_loader: Box::new(RealFileLoader),
 118             path_mapping: path_mapping,
 119         }
 120     }
 121
 122     pub fn with_file_loader(file_loader: Box<FileLoader>,
 123                             path_mapping: FilePathMapping)
 124                             -> CodeMap {
 125         CodeMap {
 126             files: RefCell::new(Vec::new()),
 127             file_loader: file_loader,
 128             path_mapping: path_mapping,
 129         }
 130     }
 131
 132     pub fn path_mapping(&self) -> &FilePathMapping {
 133         &self.path_mapping
 134     }
 135
 136     pub fn file_exists(&self, path: &Path) -> bool {
 137         self.file_loader.file_exists(path)
 138     }
 139
 140     pub fn load_file(&self, path: &Path) -> io::Result<Rc<FileMap>> {
 141         let src = self.file_loader.read_file(path)?;
 142         Ok(self.new_filemap(path.to_str().unwrap().to_string(), src))
 143     }
 144
 145     pub fn files(&self) -> Ref<Vec<Rc<FileMap>>> {
 146         self.files.borrow()
 147     }
 148
 149     fn next_start_pos(&self) -> usize {
 150         let files = self.files.borrow();
 151         match files.last() {
 152             None => 0,
 153             // Add one so there is some space between files. This lets us distinguish
 154             // positions in the codemap, even in the presence of zero-length files.
 155             Some(last) => last.end_pos.to_usize() + 1,
 156         }
 157     }
 158
 159     /// Creates a new filemap without setting its line information. If you don't
 160     /// intend to set the line information yourself, you should use new_filemap_and_lines.
 161     pub fn new_filemap(&self, filename: FileName, mut src: String) -> Rc<FileMap> {
 162         let start_pos = self.next_start_pos();
 163         let mut files = self.files.borrow_mut();
 164
 165         // Remove utf-8 BOM if any.
 166         if src.starts_with("\u{feff}") {
 167             src.drain(..3);
 168         }
 169
 170         let end_pos = start_pos + src.len();
 171
 172         let (filename, was_remapped) = self.path_mapping.map_prefix(filename);
 173
 174         let filemap = Rc::new(FileMap {
 175             name: filename,
 176             name_was_remapped: was_remapped,
 177             crate_of_origin: 0,
 178             src: Some(Rc::new(src)),
 179             start_pos: Pos::from_usize(start_pos),
 180             end_pos: Pos::from_usize(end_pos),
 181             lines: RefCell::new(Vec::new()),
 182             multibyte_chars: RefCell::new(Vec::new()),
 183         });
 184
 185         files.push(filemap.clone());
 186
 187         filemap
 188     }
 189
 190     /// Creates a new filemap and sets its line information.
 191     pub fn new_filemap_and_lines(&self, filename: &str, src: &str) -> Rc<FileMap> {
 192         let fm = self.new_filemap(filename.to_string(), src.to_owned());
 193         let mut byte_pos: u32 = fm.start_pos.0;
 194         for line in src.lines() {
 195             // register the start of this line
 196             fm.next_line(BytePos(byte_pos));
 197
 198             // update byte_pos to include this line and the \n at the end
 199             byte_pos += line.len() as u32 + 1;
 200         }
 201         fm
 202     }
 203
 204
 205     /// Allocates a new FileMap representing a source file from an external
 206     /// crate. The source code of such an "imported filemap" is not available,
 207     /// but we still know enough to generate accurate debuginfo location
 208     /// information for things inlined from other crates.
 209     pub fn new_imported_filemap(&self,
 210                                 filename: FileName,
 211                                 name_was_remapped: bool,
 212                                 crate_of_origin: u32,
 213                                 source_len: usize,
 214                                 mut file_local_lines: Vec<BytePos>,
 215                                 mut file_local_multibyte_chars: Vec<MultiByteChar>)
 216                                 -> Rc<FileMap> {
 217         let start_pos = self.next_start_pos();
 218         let mut files = self.files.borrow_mut();
 219
 220         let end_pos = Pos::from_usize(start_pos + source_len);
 221         let start_pos = Pos::from_usize(start_pos);
 222
 223         for pos in &mut file_local_lines {
 224             *pos = *pos + start_pos;
 225         }
 226
 227         for mbc in &mut file_local_multibyte_chars {
 228             mbc.pos = mbc.pos + start_pos;
 229         }
 230
 231         let filemap = Rc::new(FileMap {
 232             name: filename,
 233             name_was_remapped: name_was_remapped,
 234             crate_of_origin: crate_of_origin,
 235             src: None,
 236             start_pos: start_pos,
 237             end_pos: end_pos,
 238             lines: RefCell::new(file_local_lines),
 239             multibyte_chars: RefCell::new(file_local_multibyte_chars),
 240         });
 241
 242         files.push(filemap.clone());
 243
 244         filemap
 245     }
 246
 247     pub fn mk_substr_filename(&self, sp: Span) -> String {
 248         let pos = self.lookup_char_pos(sp.lo);
 249         (format!("<{}:{}:{}>",
 250                  pos.file.name,
 251                  pos.line,
 252                  pos.col.to_usize() + 1)).to_string()
 253     }
 254
 255     /// Lookup source information about a BytePos
 256     pub fn lookup_char_pos(&self, pos: BytePos) -> Loc {
 257         let chpos = self.bytepos_to_file_charpos(pos);
 258         match self.lookup_line(pos) {
 259             Ok(FileMapAndLine { fm: f, line: a }) => {
 260                 let line = a + 1; // Line numbers start at 1
 261                 let linebpos = (*f.lines.borrow())[a];
 262                 let linechpos = self.bytepos_to_file_charpos(linebpos);
 263                 debug!("byte pos {:?} is on the line at byte pos {:?}",
 264                        pos, linebpos);
 265                 debug!("char pos {:?} is on the line at char pos {:?}",
 266                        chpos, linechpos);
 267                 debug!("byte is on line: {}", line);
 268                 assert!(chpos >= linechpos);
 269                 Loc {
 270                     file: f,
 271                     line: line,
 272                     col: chpos - linechpos,
 273                 }
 274             }
 275             Err(f) => {
 276                 Loc {
 277                     file: f,
 278                     line: 0,
 279                     col: chpos,
 280                 }
 281             }
 282         }
 283     }
 284
 285     // If the relevant filemap is empty, we don't return a line number.
 286     fn lookup_line(&self, pos: BytePos) -> Result<FileMapAndLine, Rc<FileMap>> {
 287         let idx = self.lookup_filemap_idx(pos);
 288
 289         let files = self.files.borrow();
 290         let f = (*files)[idx].clone();
 291
 292         match f.lookup_line(pos) {
 293             Some(line) => Ok(FileMapAndLine { fm: f, line: line }),
 294             None => Err(f)
 295         }
 296     }
 297
 298     pub fn lookup_char_pos_adj(&self, pos: BytePos) -> LocWithOpt {
 299         let loc = self.lookup_char_pos(pos);
 300         LocWithOpt {
 301             filename: loc.file.name.to_string(),
 302             line: loc.line,
 303             col: loc.col,
 304             file: Some(loc.file)
 305         }
 306     }
 307
 308     /// Returns `Some(span)`, a union of the lhs and rhs span.  The lhs must precede the rhs. If
 309     /// there are gaps between lhs and rhs, the resulting union will cross these gaps.
 310     /// For this to work, the spans have to be:
 311     ///    * the ctxt of both spans much match
 312     ///    * the lhs span needs to end on the same line the rhs span begins
 313     ///    * the lhs span must start at or before the rhs span
 314     pub fn merge_spans(&self, sp_lhs: Span, sp_rhs: Span) -> Option<Span> {
 315         use std::cmp;
 316
 317         // make sure we're at the same expansion id
 318         if sp_lhs.ctxt != sp_rhs.ctxt {
 319             return None;
 320         }
 321
 322         let lhs_end = match self.lookup_line(sp_lhs.hi) {
 323             Ok(x) => x,
 324             Err(_) => return None
 325         };
 326         let rhs_begin = match self.lookup_line(sp_rhs.lo) {
 327             Ok(x) => x,
 328             Err(_) => return None
 329         };
 330
 331         // if we must cross lines to merge, don't merge
 332         if lhs_end.line != rhs_begin.line {
 333             return None;
 334         }
 335
 336         // ensure these follow the expected order and we don't overlap
 337         if (sp_lhs.lo <= sp_rhs.lo) && (sp_lhs.hi <= sp_rhs.lo) {
 338             Some(Span {
 339                 lo: cmp::min(sp_lhs.lo, sp_rhs.lo),
 340                 hi: cmp::max(sp_lhs.hi, sp_rhs.hi),
 341                 ctxt: sp_lhs.ctxt,
 342             })
 343         } else {
 344             None
 345         }
 346     }
 347
 348     pub fn span_to_string(&self, sp: Span) -> String {
 349         if self.files.borrow().is_empty() && sp.source_equal(&DUMMY_SP) {
 350             return "no-location".to_string();
 351         }
 352
 353         let lo = self.lookup_char_pos_adj(sp.lo);
 354         let hi = self.lookup_char_pos_adj(sp.hi);
 355         return (format!("{}:{}:{}: {}:{}",
 356                         lo.filename,
 357                         lo.line,
 358                         lo.col.to_usize() + 1,
 359                         hi.line,
 360                         hi.col.to_usize() + 1)).to_string()
 361     }
 362
 363     pub fn span_to_filename(&self, sp: Span) -> FileName {
 364         self.lookup_char_pos(sp.lo).file.name.to_string()
 365     }
 366
 367     pub fn span_to_lines(&self, sp: Span) -> FileLinesResult {
 368         debug!("span_to_lines(sp={:?})", sp);
 369
 370         if sp.lo > sp.hi {
 371             return Err(SpanLinesError::IllFormedSpan(sp));
 372         }
 373
 374         let lo = self.lookup_char_pos(sp.lo);
 375         debug!("span_to_lines: lo={:?}", lo);
 376         let hi = self.lookup_char_pos(sp.hi);
 377         debug!("span_to_lines: hi={:?}", hi);
 378
 379         if lo.file.start_pos != hi.file.start_pos {
 380             return Err(SpanLinesError::DistinctSources(DistinctSources {
 381                 begin: (lo.file.name.clone(), lo.file.start_pos),
 382                 end: (hi.file.name.clone(), hi.file.start_pos),
 383             }));
 384         }
 385         assert!(hi.line >= lo.line);
 386
 387         let mut lines = Vec::with_capacity(hi.line - lo.line + 1);
 388
 389         // The span starts partway through the first line,
 390         // but after that it starts from offset 0.
 391         let mut start_col = lo.col;
 392
 393         // For every line but the last, it extends from `start_col`
 394         // and to the end of the line. Be careful because the line
 395         // numbers in Loc are 1-based, so we subtract 1 to get 0-based
 396         // lines.
 397         for line_index in lo.line-1 .. hi.line-1 {
 398             let line_len = lo.file.get_line(line_index)
 399                                   .map(|s| s.chars().count())
 400                                   .unwrap_or(0);
 401             lines.push(LineInfo { line_index: line_index,
 402                                   start_col: start_col,
 403                                   end_col: CharPos::from_usize(line_len) });
 404             start_col = CharPos::from_usize(0);
 405         }
 406
 407         // For the last line, it extends from `start_col` to `hi.col`:
 408         lines.push(LineInfo { line_index: hi.line - 1,
 409                               start_col: start_col,
 410                               end_col: hi.col });
 411
 412         Ok(FileLines {file: lo.file, lines: lines})
 413     }
 414
 415     pub fn span_to_snippet(&self, sp: Span) -> Result<String, SpanSnippetError> {
 416         if sp.lo > sp.hi {
 417             return Err(SpanSnippetError::IllFormedSpan(sp));
 418         }
 419
 420         let local_begin = self.lookup_byte_offset(sp.lo);
 421         let local_end = self.lookup_byte_offset(sp.hi);
 422
 423         if local_begin.fm.start_pos != local_end.fm.start_pos {
 424             return Err(SpanSnippetError::DistinctSources(DistinctSources {
 425                 begin: (local_begin.fm.name.clone(),
 426                         local_begin.fm.start_pos),
 427                 end: (local_end.fm.name.clone(),
 428                       local_end.fm.start_pos)
 429             }));
 430         } else {
 431             match local_begin.fm.src {
 432                 Some(ref src) => {
 433                     let start_index = local_begin.pos.to_usize();
 434                     let end_index = local_end.pos.to_usize();
 435                     let source_len = (local_begin.fm.end_pos -
 436                                       local_begin.fm.start_pos).to_usize();
 437
 438                     if start_index > end_index || end_index > source_len {
 439                         return Err(SpanSnippetError::MalformedForCodemap(
 440                             MalformedCodemapPositions {
 441                                 name: local_begin.fm.name.clone(),
 442                                 source_len: source_len,
 443                                 begin_pos: local_begin.pos,
 444                                 end_pos: local_end.pos,
 445                             }));
 446                     }
 447
 448                     return Ok((&src[start_index..end_index]).to_string())
 449                 }
 450                 None => {
 451                     return Err(SpanSnippetError::SourceNotAvailable {
 452                         filename: local_begin.fm.name.clone()
 453                     });
 454                 }
 455             }
 456         }
 457     }
 458
 459     /// Given a `Span`, try to get a shorter span ending before the first occurrence of `c` `char`
 460     pub fn span_until_char(&self, sp: Span, c: char) -> Span {
 461         match self.span_to_snippet(sp) {
 462             Ok(snippet) => {
 463                 let snippet = snippet.split(c).nth(0).unwrap_or("").trim_right();
 464                 if !snippet.is_empty() && !snippet.contains('\n') {
 465                     Span { hi: BytePos(sp.lo.0 + snippet.len() as u32), ..sp }
 466                 } else {
 467                     sp
 468                 }
 469             }
 470             _ => sp,
 471         }
 472     }
 473
 474     pub fn def_span(&self, sp: Span) -> Span {
 475         self.span_until_char(sp, '{')
 476     }
 477
 478     pub fn get_filemap(&self, filename: &str) -> Option<Rc<FileMap>> {
 479         for fm in self.files.borrow().iter() {
 480             if filename == fm.name {
 481                 return Some(fm.clone());
 482             }
 483         }
 484         None
 485     }
 486
 487     /// For a global BytePos compute the local offset within the containing FileMap
 488     pub fn lookup_byte_offset(&self, bpos: BytePos) -> FileMapAndBytePos {
 489         let idx = self.lookup_filemap_idx(bpos);
 490         let fm = (*self.files.borrow())[idx].clone();
 491         let offset = bpos - fm.start_pos;
 492         FileMapAndBytePos {fm: fm, pos: offset}
 493     }
 494
 495     /// Converts an absolute BytePos to a CharPos relative to the filemap.
 496     pub fn bytepos_to_file_charpos(&self, bpos: BytePos) -> CharPos {
 497         let idx = self.lookup_filemap_idx(bpos);
 498         let files = self.files.borrow();
 499         let map = &(*files)[idx];
 500
 501         // The number of extra bytes due to multibyte chars in the FileMap
 502         let mut total_extra_bytes = 0;
 503
 504         for mbc in map.multibyte_chars.borrow().iter() {
 505             debug!("{}-byte char at {:?}", mbc.bytes, mbc.pos);
 506             if mbc.pos < bpos {
 507                 // every character is at least one byte, so we only
 508                 // count the actual extra bytes.
 509                 total_extra_bytes += mbc.bytes - 1;
 510                 // We should never see a byte position in the middle of a
 511                 // character
 512                 assert!(bpos.to_usize() >= mbc.pos.to_usize() + mbc.bytes);
 513             } else {
 514                 break;
 515             }
 516         }
 517
 518         assert!(map.start_pos.to_usize() + total_extra_bytes <= bpos.to_usize());
 519         CharPos(bpos.to_usize() - map.start_pos.to_usize() - total_extra_bytes)
 520     }
 521
 522     // Return the index of the filemap (in self.files) which contains pos.
 523     pub fn lookup_filemap_idx(&self, pos: BytePos) -> usize {
 524         let files = self.files.borrow();
 525         let files = &*files;
 526         let count = files.len();
 527
 528         // Binary search for the filemap.
 529         let mut a = 0;
 530         let mut b = count;
 531         while b - a > 1 {
 532             let m = (a + b) / 2;
 533             if files[m].start_pos > pos {
 534                 b = m;
 535             } else {
 536                 a = m;
 537             }
 538         }
 539
 540         assert!(a < count, "position {} does not resolve to a source location", pos.to_usize());
 541
 542         return a;
 543     }
 544
 545     pub fn count_lines(&self) -> usize {
 546         self.files().iter().fold(0, |a, f| a + f.count_lines())
 547     }
 548 }
 549
 550 impl CodeMapper for CodeMap {
 551     fn lookup_char_pos(&self, pos: BytePos) -> Loc {
 552         self.lookup_char_pos(pos)
 553     }
 554     fn span_to_lines(&self, sp: Span) -> FileLinesResult {
 555         self.span_to_lines(sp)
 556     }
 557     fn span_to_string(&self, sp: Span) -> String {
 558         self.span_to_string(sp)
 559     }
 560     fn span_to_filename(&self, sp: Span) -> FileName {
 561         self.span_to_filename(sp)
 562     }
 563     fn merge_spans(&self, sp_lhs: Span, sp_rhs: Span) -> Option<Span> {
 564         self.merge_spans(sp_lhs, sp_rhs)
 565     }
 566 }
 567
 568 #[derive(Clone)]
 569 pub struct FilePathMapping {
 570     mapping: Vec<(String, String)>,
 571 }
 572
 573 impl FilePathMapping {
 574     pub fn empty() -> FilePathMapping {
 575         FilePathMapping {
 576             mapping: vec![]
 577         }
 578     }
 579
 580     pub fn new(mapping: Vec<(String, String)>) -> FilePathMapping {
 581         FilePathMapping {
 582             mapping: mapping
 583         }
 584     }
 585
 586     /// Applies any path prefix substitution as defined by the mapping.
 587     /// The return value is the remapped path and a boolean indicating whether
 588     /// the path was affected by the mapping.
 589     pub fn map_prefix(&self, path: String) -> (String, bool) {
 590         // NOTE: We are iterating over the mapping entries from last to first
 591         //       because entries specified later on the command line should
 592         //       take precedence.
 593         for &(ref from, ref to) in self.mapping.iter().rev() {
 594             if path.starts_with(from) {
 595                 let mapped = path.replacen(from, to, 1);
 596                 return (mapped, true);
 597             }
 598         }
 599
 600         (path, false)
 601     }
 602 }
 603
 604 // _____________________________________________________________________________
 605 // Tests
 606 //
 607
 608 #[cfg(test)]
 609 mod tests {
 610     use super::*;
 611     use std::rc::Rc;
 612
 613     #[test]
 614     fn t1 () {
 615         let cm = CodeMap::new(FilePathMapping::empty());
 616         let fm = cm.new_filemap("blork.rs".to_string(),
 617                                 "first line.\nsecond line".to_string());
 618         fm.next_line(BytePos(0));
 619         // Test we can get lines with partial line info.
 620         assert_eq!(fm.get_line(0), Some("first line."));
 621         // TESTING BROKEN BEHAVIOR: line break declared before actual line break.
 622         fm.next_line(BytePos(10));
 623         assert_eq!(fm.get_line(1), Some("."));
 624         fm.next_line(BytePos(12));
 625         assert_eq!(fm.get_line(2), Some("second line"));
 626     }
 627
 628     #[test]
 629     #[should_panic]
 630     fn t2 () {
 631         let cm = CodeMap::new(FilePathMapping::empty());
 632         let fm = cm.new_filemap("blork.rs".to_string(),
 633                                 "first line.\nsecond line".to_string());
 634         // TESTING *REALLY* BROKEN BEHAVIOR:
 635         fm.next_line(BytePos(0));
 636         fm.next_line(BytePos(10));
 637         fm.next_line(BytePos(2));
 638     }
 639
 640     fn init_code_map() -> CodeMap {
 641         let cm = CodeMap::new(FilePathMapping::empty());
 642         let fm1 = cm.new_filemap("blork.rs".to_string(),
 643                                  "first line.\nsecond line".to_string());
 644         let fm2 = cm.new_filemap("empty.rs".to_string(),
 645                                  "".to_string());
 646         let fm3 = cm.new_filemap("blork2.rs".to_string(),
 647                                  "first line.\nsecond line".to_string());
 648
 649         fm1.next_line(BytePos(0));
 650         fm1.next_line(BytePos(12));
 651         fm2.next_line(fm2.start_pos);
 652         fm3.next_line(fm3.start_pos);
 653         fm3.next_line(fm3.start_pos + BytePos(12));
 654
 655         cm
 656     }
 657
 658     #[test]
 659     fn t3() {
 660         // Test lookup_byte_offset
 661         let cm = init_code_map();
 662
 663         let fmabp1 = cm.lookup_byte_offset(BytePos(23));
 664         assert_eq!(fmabp1.fm.name, "blork.rs");
 665         assert_eq!(fmabp1.pos, BytePos(23));
 666
 667         let fmabp1 = cm.lookup_byte_offset(BytePos(24));
 668         assert_eq!(fmabp1.fm.name, "empty.rs");
 669         assert_eq!(fmabp1.pos, BytePos(0));
 670
 671         let fmabp2 = cm.lookup_byte_offset(BytePos(25));
 672         assert_eq!(fmabp2.fm.name, "blork2.rs");
 673         assert_eq!(fmabp2.pos, BytePos(0));
 674     }
 675
 676     #[test]
 677     fn t4() {
 678         // Test bytepos_to_file_charpos
 679         let cm = init_code_map();
 680
 681         let cp1 = cm.bytepos_to_file_charpos(BytePos(22));
 682         assert_eq!(cp1, CharPos(22));
 683
 684         let cp2 = cm.bytepos_to_file_charpos(BytePos(25));
 685         assert_eq!(cp2, CharPos(0));
 686     }
 687
 688     #[test]
 689     fn t5() {
 690         // Test zero-length filemaps.
 691         let cm = init_code_map();
 692
 693         let loc1 = cm.lookup_char_pos(BytePos(22));
 694         assert_eq!(loc1.file.name, "blork.rs");
 695         assert_eq!(loc1.line, 2);
 696         assert_eq!(loc1.col, CharPos(10));
 697
 698         let loc2 = cm.lookup_char_pos(BytePos(25));
 699         assert_eq!(loc2.file.name, "blork2.rs");
 700         assert_eq!(loc2.line, 1);
 701         assert_eq!(loc2.col, CharPos(0));
 702     }
 703
 704     fn init_code_map_mbc() -> CodeMap {
 705         let cm = CodeMap::new(FilePathMapping::empty());
 706         // € is a three byte utf8 char.
 707         let fm1 =
 708             cm.new_filemap("blork.rs".to_string(),
 709                            "fir€st €€€€ line.\nsecond line".to_string());
 710         let fm2 = cm.new_filemap("blork2.rs".to_string(),
 711                                  "first line€€.\n€ second line".to_string());
 712
 713         fm1.next_line(BytePos(0));
 714         fm1.next_line(BytePos(28));
 715         fm2.next_line(fm2.start_pos);
 716         fm2.next_line(fm2.start_pos + BytePos(20));
 717
 718         fm1.record_multibyte_char(BytePos(3), 3);
 719         fm1.record_multibyte_char(BytePos(9), 3);
 720         fm1.record_multibyte_char(BytePos(12), 3);
 721         fm1.record_multibyte_char(BytePos(15), 3);
 722         fm1.record_multibyte_char(BytePos(18), 3);
 723         fm2.record_multibyte_char(fm2.start_pos + BytePos(10), 3);
 724         fm2.record_multibyte_char(fm2.start_pos + BytePos(13), 3);
 725         fm2.record_multibyte_char(fm2.start_pos + BytePos(18), 3);
 726
 727         cm
 728     }
 729
 730     #[test]
 731     fn t6() {
 732         // Test bytepos_to_file_charpos in the presence of multi-byte chars
 733         let cm = init_code_map_mbc();
 734
 735         let cp1 = cm.bytepos_to_file_charpos(BytePos(3));
 736         assert_eq!(cp1, CharPos(3));
 737
 738         let cp2 = cm.bytepos_to_file_charpos(BytePos(6));
 739         assert_eq!(cp2, CharPos(4));
 740
 741         let cp3 = cm.bytepos_to_file_charpos(BytePos(56));
 742         assert_eq!(cp3, CharPos(12));
 743
 744         let cp4 = cm.bytepos_to_file_charpos(BytePos(61));
 745         assert_eq!(cp4, CharPos(15));
 746     }
 747
 748     #[test]
 749     fn t7() {
 750         // Test span_to_lines for a span ending at the end of filemap
 751         let cm = init_code_map();
 752         let span = Span {lo: BytePos(12), hi: BytePos(23), ctxt: NO_EXPANSION};
 753         let file_lines = cm.span_to_lines(span).unwrap();
 754
 755         assert_eq!(file_lines.file.name, "blork.rs");
 756         assert_eq!(file_lines.lines.len(), 1);
 757         assert_eq!(file_lines.lines[0].line_index, 1);
 758     }
 759
 760     /// Given a string like " ~~~~~~~~~~~~ ", produces a span
 761     /// coverting that range. The idea is that the string has the same
 762     /// length as the input, and we uncover the byte positions.  Note
 763     /// that this can span lines and so on.
 764     fn span_from_selection(input: &str, selection: &str) -> Span {
 765         assert_eq!(input.len(), selection.len());
 766         let left_index = selection.find('~').unwrap() as u32;
 767         let right_index = selection.rfind('~').map(|x|x as u32).unwrap_or(left_index);
 768         Span { lo: BytePos(left_index), hi: BytePos(right_index + 1), ctxt: NO_EXPANSION }
 769     }
 770
 771     /// Test span_to_snippet and span_to_lines for a span coverting 3
 772     /// lines in the middle of a file.
 773     #[test]
 774     fn span_to_snippet_and_lines_spanning_multiple_lines() {
 775         let cm = CodeMap::new(FilePathMapping::empty());
 776         let inputtext = "aaaaa\nbbbbBB\nCCC\nDDDDDddddd\neee\n";
 777         let selection = "     \n    ~~\n~~~\n~~~~~     \n   \n";
 778         cm.new_filemap_and_lines("blork.rs", inputtext);
 779         let span = span_from_selection(inputtext, selection);
 780
 781         // check that we are extracting the text we thought we were extracting
 782         assert_eq!(&cm.span_to_snippet(span).unwrap(), "BB\nCCC\nDDDDD");
 783
 784         // check that span_to_lines gives us the complete result with the lines/cols we expected
 785         let lines = cm.span_to_lines(span).unwrap();
 786         let expected = vec![
 787             LineInfo { line_index: 1, start_col: CharPos(4), end_col: CharPos(6) },
 788             LineInfo { line_index: 2, start_col: CharPos(0), end_col: CharPos(3) },
 789             LineInfo { line_index: 3, start_col: CharPos(0), end_col: CharPos(5) }
 790             ];
 791         assert_eq!(lines.lines, expected);
 792     }
 793
 794     #[test]
 795     fn t8() {
 796         // Test span_to_snippet for a span ending at the end of filemap
 797         let cm = init_code_map();
 798         let span = Span {lo: BytePos(12), hi: BytePos(23), ctxt: NO_EXPANSION};
 799         let snippet = cm.span_to_snippet(span);
 800
 801         assert_eq!(snippet, Ok("second line".to_string()));
 802     }
 803
 804     #[test]
 805     fn t9() {
 806         // Test span_to_str for a span ending at the end of filemap
 807         let cm = init_code_map();
 808         let span = Span {lo: BytePos(12), hi: BytePos(23), ctxt: NO_EXPANSION};
 809         let sstr =  cm.span_to_string(span);
 810
 811         assert_eq!(sstr, "blork.rs:2:1: 2:12");
 812     }
 813
 814     /// Test failing to merge two spans on different lines
 815     #[test]
 816     fn span_merging_fail() {
 817         let cm = CodeMap::new(FilePathMapping::empty());
 818         let inputtext  = "bbbb BB\ncc CCC\n";
 819         let selection1 = "     ~~\n      \n";
 820         let selection2 = "       \n   ~~~\n";
 821         cm.new_filemap_and_lines("blork.rs", inputtext);
 822         let span1 = span_from_selection(inputtext, selection1);
 823         let span2 = span_from_selection(inputtext, selection2);
 824
 825         assert!(cm.merge_spans(span1, span2).is_none());
 826     }
 827
 828     /// Returns the span corresponding to the `n`th occurrence of
 829     /// `substring` in `source_text`.
 830     trait CodeMapExtension {
 831         fn span_substr(&self,
 832                     file: &Rc<FileMap>,
 833                     source_text: &str,
 834                     substring: &str,
 835                     n: usize)
 836                     -> Span;
 837     }
 838
 839     impl CodeMapExtension for CodeMap {
 840         fn span_substr(&self,
 841                     file: &Rc<FileMap>,
 842                     source_text: &str,
 843                     substring: &str,
 844                     n: usize)
 845                     -> Span
 846         {
 847             println!("span_substr(file={:?}/{:?}, substring={:?}, n={})",
 848                     file.name, file.start_pos, substring, n);
 849             let mut i = 0;
 850             let mut hi = 0;
 851             loop {
 852                 let offset = source_text[hi..].find(substring).unwrap_or_else(|| {
 853                     panic!("source_text `{}` does not have {} occurrences of `{}`, only {}",
 854                         source_text, n, substring, i);
 855                 });
 856                 let lo = hi + offset;
 857                 hi = lo + substring.len();
 858                 if i == n {
 859                     let span = Span {
 860                         lo: BytePos(lo as u32 + file.start_pos.0),
 861                         hi: BytePos(hi as u32 + file.start_pos.0),
 862                         ctxt: NO_EXPANSION,
 863                     };
 864                     assert_eq!(&self.span_to_snippet(span).unwrap()[..],
 865                             substring);
 866                     return span;
 867                 }
 868                 i += 1;
 869             }
 870         }
 871     }
 872 }