src/libsyntax_pos/analyze_source_file.rs

   1 // Copyright 2018 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 use unicode_width::UnicodeWidthChar;
  12 use super::*;
  13
  14 /// Find all newlines, multi-byte characters, and non-narrow characters in a
  15 /// SourceFile.
  16 ///
  17 /// This function will use an SSE2 enhanced implementation if hardware support
  18 /// is detected at runtime.
  19 pub fn analyze_source_file(
  20     src: &str,
  21     source_file_start_pos: BytePos)
  22     -> (Vec<BytePos>, Vec<MultiByteChar>, Vec<NonNarrowChar>)
  23 {
  24     let mut lines = vec![source_file_start_pos];
  25     let mut multi_byte_chars = vec![];
  26     let mut non_narrow_chars = vec![];
  27
  28     // Calls the right implementation, depending on hardware support available.
  29     analyze_source_file_dispatch(src,
  30                              source_file_start_pos,
  31                              &mut lines,
  32                              &mut multi_byte_chars,
  33                              &mut non_narrow_chars);
  34
  35     // The code above optimistically registers a new line *after* each \n
  36     // it encounters. If that point is already outside the source_file, remove
  37     // it again.
  38     if let Some(&last_line_start) = lines.last() {
  39         let file_map_end = source_file_start_pos + BytePos::from_usize(src.len());
  40         assert!(file_map_end >= last_line_start);
  41         if last_line_start == file_map_end {
  42             lines.pop();
  43         }
  44     }
  45
  46     (lines, multi_byte_chars, non_narrow_chars)
  47 }
  48
  49 cfg_if! {
  50     if #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"),
  51                  not(stage0)))] {
  52         fn analyze_source_file_dispatch(src: &str,
  53                                     source_file_start_pos: BytePos,
  54                                     lines: &mut Vec<BytePos>,
  55                                     multi_byte_chars: &mut Vec<MultiByteChar>,
  56                                     non_narrow_chars: &mut Vec<NonNarrowChar>) {
  57             if is_x86_feature_detected!("sse2") {
  58                 unsafe {
  59                     analyze_source_file_sse2(src,
  60                                          source_file_start_pos,
  61                                          lines,
  62                                          multi_byte_chars,
  63                                          non_narrow_chars);
  64                 }
  65             } else {
  66                 analyze_source_file_generic(src,
  67                                         src.len(),
  68                                         source_file_start_pos,
  69                                         lines,
  70                                         multi_byte_chars,
  71                                         non_narrow_chars);
  72
  73             }
  74         }
  75
  76         /// Check 16 byte chunks of text at a time. If the chunk contains
  77         /// something other than printable ASCII characters and newlines, the
  78         /// function falls back to the generic implementation. Otherwise it uses
  79         /// SSE2 intrinsics to quickly find all newlines.
  80         #[target_feature(enable = "sse2")]
  81         unsafe fn analyze_source_file_sse2(src: &str,
  82                                        output_offset: BytePos,
  83                                        lines: &mut Vec<BytePos>,
  84                                        multi_byte_chars: &mut Vec<MultiByteChar>,
  85                                        non_narrow_chars: &mut Vec<NonNarrowChar>) {
  86             #[cfg(target_arch = "x86")]
  87             use std::arch::x86::*;
  88             #[cfg(target_arch = "x86_64")]
  89             use std::arch::x86_64::*;
  90
  91             const CHUNK_SIZE: usize = 16;
  92
  93             let src_bytes = src.as_bytes();
  94
  95             let chunk_count = src.len() / CHUNK_SIZE;
  96
  97             // This variable keeps track of where we should start decoding a
  98             // chunk. If a multi-byte character spans across chunk boundaries,
  99             // we need to skip that part in the next chunk because we already
 100             // handled it.
 101             let mut intra_chunk_offset = 0;
 102
 103             for chunk_index in 0 .. chunk_count {
 104                 let ptr = src_bytes.as_ptr() as *const __m128i;
 105                 // We don't know if the pointer is aligned to 16 bytes, so we
 106                 // use `loadu`, which supports unaligned loading.
 107                 let chunk = _mm_loadu_si128(ptr.offset(chunk_index as isize));
 108
 109                 // For character in the chunk, see if its byte value is < 0, which
 110                 // indicates that it's part of a UTF-8 char.
 111                 let multibyte_test = _mm_cmplt_epi8(chunk, _mm_set1_epi8(0));
 112                 // Create a bit mask from the comparison results.
 113                 let multibyte_mask = _mm_movemask_epi8(multibyte_test);
 114
 115                 // If the bit mask is all zero, we only have ASCII chars here:
 116                 if multibyte_mask == 0 {
 117                     assert!(intra_chunk_offset == 0);
 118
 119                     // Check if there are any control characters in the chunk. All
 120                     // control characters that we can encounter at this point have a
 121                     // byte value less than 32 or ...
 122                     let control_char_test0 = _mm_cmplt_epi8(chunk, _mm_set1_epi8(32));
 123                     let control_char_mask0 = _mm_movemask_epi8(control_char_test0);
 124
 125                     // ... it's the ASCII 'DEL' character with a value of 127.
 126                     let control_char_test1 = _mm_cmpeq_epi8(chunk, _mm_set1_epi8(127));
 127                     let control_char_mask1 = _mm_movemask_epi8(control_char_test1);
 128
 129                     let control_char_mask = control_char_mask0 | control_char_mask1;
 130
 131                     if control_char_mask != 0 {
 132                         // Check for newlines in the chunk
 133                         let newlines_test = _mm_cmpeq_epi8(chunk, _mm_set1_epi8(b'\n' as i8));
 134                         let newlines_mask = _mm_movemask_epi8(newlines_test);
 135
 136                         if control_char_mask == newlines_mask {
 137                             // All control characters are newlines, record them
 138                             let mut newlines_mask = 0xFFFF0000 | newlines_mask as u32;
 139                             let output_offset = output_offset +
 140                                 BytePos::from_usize(chunk_index * CHUNK_SIZE + 1);
 141
 142                             loop {
 143                                 let index = newlines_mask.trailing_zeros();
 144
 145                                 if index >= CHUNK_SIZE as u32 {
 146                                     // We have arrived at the end of the chunk.
 147                                     break
 148                                 }
 149
 150                                 lines.push(BytePos(index) + output_offset);
 151
 152                                 // Clear the bit, so we can find the next one.
 153                                 newlines_mask &= (!1) << index;
 154                             }
 155
 156                             // We are done for this chunk. All control characters were
 157                             // newlines and we took care of those.
 158                             continue
 159                         } else {
 160                             // Some of the control characters are not newlines,
 161                             // fall through to the slow path below.
 162                         }
 163                     } else {
 164                         // No control characters, nothing to record for this chunk
 165                         continue
 166                     }
 167                 }
 168
 169                 // The slow path.
 170                 // There are control chars in here, fallback to generic decoding.
 171                 let scan_start = chunk_index * CHUNK_SIZE + intra_chunk_offset;
 172                 intra_chunk_offset = analyze_source_file_generic(
 173                     &src[scan_start .. ],
 174                     CHUNK_SIZE - intra_chunk_offset,
 175                     BytePos::from_usize(scan_start) + output_offset,
 176                     lines,
 177                     multi_byte_chars,
 178                     non_narrow_chars
 179                 );
 180             }
 181
 182             // There might still be a tail left to analyze
 183             let tail_start = chunk_count * CHUNK_SIZE + intra_chunk_offset;
 184             if tail_start < src.len() {
 185                 analyze_source_file_generic(&src[tail_start as usize ..],
 186                                         src.len() - tail_start,
 187                                         output_offset + BytePos::from_usize(tail_start),
 188                                         lines,
 189                                         multi_byte_chars,
 190                                         non_narrow_chars);
 191             }
 192         }
 193     } else {
 194
 195         // The target (or compiler version) does not support SSE2 ...
 196         fn analyze_source_file_dispatch(src: &str,
 197                                     source_file_start_pos: BytePos,
 198                                     lines: &mut Vec<BytePos>,
 199                                     multi_byte_chars: &mut Vec<MultiByteChar>,
 200                                     non_narrow_chars: &mut Vec<NonNarrowChar>) {
 201             analyze_source_file_generic(src,
 202                                     src.len(),
 203                                     source_file_start_pos,
 204                                     lines,
 205                                     multi_byte_chars,
 206                                     non_narrow_chars);
 207         }
 208     }
 209 }
 210
 211 // `scan_len` determines the number of bytes in `src` to scan. Note that the
 212 // function can read past `scan_len` if a multi-byte character start within the
 213 // range but extends past it. The overflow is returned by the function.
 214 fn analyze_source_file_generic(src: &str,
 215                            scan_len: usize,
 216                            output_offset: BytePos,
 217                            lines: &mut Vec<BytePos>,
 218                            multi_byte_chars: &mut Vec<MultiByteChar>,
 219                            non_narrow_chars: &mut Vec<NonNarrowChar>)
 220                            -> usize
 221 {
 222     assert!(src.len() >= scan_len);
 223     let mut i = 0;
 224     let src_bytes = src.as_bytes();
 225
 226     while i < scan_len {
 227         let byte = unsafe {
 228             // We verified that i < scan_len <= src.len()
 229             *src_bytes.get_unchecked(i as usize)
 230         };
 231
 232         // How much to advance in order to get to the next UTF-8 char in the
 233         // string.
 234         let mut char_len = 1;
 235
 236         if byte < 32 {
 237             // This is an ASCII control character, it could be one of the cases
 238             // that are interesting to us.
 239
 240             let pos = BytePos::from_usize(i) + output_offset;
 241
 242             match byte {
 243                 b'\n' => {
 244                     lines.push(pos + BytePos(1));
 245                 }
 246                 b'\t' => {
 247                     non_narrow_chars.push(NonNarrowChar::Tab(pos));
 248                 }
 249                 _ => {
 250                     non_narrow_chars.push(NonNarrowChar::ZeroWidth(pos));
 251                 }
 252             }
 253         } else if byte >= 127 {
 254             // The slow path:
 255             // This is either ASCII control character "DEL" or the beginning of
 256             // a multibyte char. Just decode to `char`.
 257             let c = (&src[i..]).chars().next().unwrap();
 258             char_len = c.len_utf8();
 259
 260             let pos = BytePos::from_usize(i) + output_offset;
 261
 262             if char_len > 1 {
 263                 assert!(char_len >=2 && char_len <= 4);
 264                 let mbc = MultiByteChar {
 265                     pos,
 266                     bytes: char_len as u8,
 267                 };
 268                 multi_byte_chars.push(mbc);
 269             }
 270
 271             // Assume control characters are zero width.
 272             // FIXME: How can we decide between `width` and `width_cjk`?
 273             let char_width = UnicodeWidthChar::width(c).unwrap_or(0);
 274
 275             if char_width != 1 {
 276                 non_narrow_chars.push(NonNarrowChar::new(pos, char_width));
 277             }
 278         }
 279
 280         i += char_len;
 281     }
 282
 283     i - scan_len
 284 }
 285
 286
 287
 288 macro_rules! test {
 289     (case: $test_name:ident,
 290      text: $text:expr,
 291      source_file_start_pos: $source_file_start_pos:expr,
 292      lines: $lines:expr,
 293      multi_byte_chars: $multi_byte_chars:expr,
 294      non_narrow_chars: $non_narrow_chars:expr,) => (
 295
 296     #[test]
 297     fn $test_name() {
 298
 299         let (lines, multi_byte_chars, non_narrow_chars) =
 300             analyze_source_file($text, BytePos($source_file_start_pos));
 301
 302         let expected_lines: Vec<BytePos> = $lines
 303             .into_iter()
 304             .map(|pos| BytePos(pos))
 305             .collect();
 306
 307         assert_eq!(lines, expected_lines);
 308
 309         let expected_mbcs: Vec<MultiByteChar> = $multi_byte_chars
 310             .into_iter()
 311             .map(|(pos, bytes)| MultiByteChar {
 312                 pos: BytePos(pos),
 313                 bytes,
 314             })
 315             .collect();
 316
 317         assert_eq!(multi_byte_chars, expected_mbcs);
 318
 319         let expected_nncs: Vec<NonNarrowChar> = $non_narrow_chars
 320             .into_iter()
 321             .map(|(pos, width)| {
 322                 NonNarrowChar::new(BytePos(pos), width)
 323             })
 324             .collect();
 325
 326         assert_eq!(non_narrow_chars, expected_nncs);
 327     })
 328 }
 329
 330 test!(
 331     case: empty_text,
 332     text: "",
 333     source_file_start_pos: 0,
 334     lines: vec![],
 335     multi_byte_chars: vec![],
 336     non_narrow_chars: vec![],
 337 );
 338
 339 test!(
 340     case: newlines_short,
 341     text: "a\nc",
 342     source_file_start_pos: 0,
 343     lines: vec![0, 2],
 344     multi_byte_chars: vec![],
 345     non_narrow_chars: vec![],
 346 );
 347
 348 test!(
 349     case: newlines_long,
 350     text: "012345678\nabcdef012345678\na",
 351     source_file_start_pos: 0,
 352     lines: vec![0, 10, 26],
 353     multi_byte_chars: vec![],
 354     non_narrow_chars: vec![],
 355 );
 356
 357 test!(
 358     case: newline_and_multi_byte_char_in_same_chunk,
 359     text: "01234β789\nbcdef0123456789abcdef",
 360     source_file_start_pos: 0,
 361     lines: vec![0, 11],
 362     multi_byte_chars: vec![(5, 2)],
 363     non_narrow_chars: vec![],
 364 );
 365
 366 test!(
 367     case: newline_and_control_char_in_same_chunk,
 368     text: "01234\u{07}6789\nbcdef0123456789abcdef",
 369     source_file_start_pos: 0,
 370     lines: vec![0, 11],
 371     multi_byte_chars: vec![],
 372     non_narrow_chars: vec![(5, 0)],
 373 );
 374
 375 test!(
 376     case: multi_byte_char_short,
 377     text: "aβc",
 378     source_file_start_pos: 0,
 379     lines: vec![0],
 380     multi_byte_chars: vec![(1, 2)],
 381     non_narrow_chars: vec![],
 382 );
 383
 384 test!(
 385     case: multi_byte_char_long,
 386     text: "0123456789abcΔf012345β",
 387     source_file_start_pos: 0,
 388     lines: vec![0],
 389     multi_byte_chars: vec![(13, 2), (22, 2)],
 390     non_narrow_chars: vec![],
 391 );
 392
 393 test!(
 394     case: multi_byte_char_across_chunk_boundary,
 395     text: "0123456789abcdeΔ123456789abcdef01234",
 396     source_file_start_pos: 0,
 397     lines: vec![0],
 398     multi_byte_chars: vec![(15, 2)],
 399     non_narrow_chars: vec![],
 400 );
 401
 402 test!(
 403     case: multi_byte_char_across_chunk_boundary_tail,
 404     text: "0123456789abcdeΔ....",
 405     source_file_start_pos: 0,
 406     lines: vec![0],
 407     multi_byte_chars: vec![(15, 2)],
 408     non_narrow_chars: vec![],
 409 );
 410
 411 test!(
 412     case: non_narrow_short,
 413     text: "0\t2",
 414     source_file_start_pos: 0,
 415     lines: vec![0],
 416     multi_byte_chars: vec![],
 417     non_narrow_chars: vec![(1, 4)],
 418 );
 419
 420 test!(
 421     case: non_narrow_long,
 422     text: "01\t3456789abcdef01234567\u{07}9",
 423     source_file_start_pos: 0,
 424     lines: vec![0],
 425     multi_byte_chars: vec![],
 426     non_narrow_chars: vec![(2, 4), (24, 0)],
 427 );
 428
 429 test!(
 430     case: output_offset_all,
 431     text: "01\t345\n789abcΔf01234567\u{07}9\nbcΔf",
 432     source_file_start_pos: 1000,
 433     lines: vec![0 + 1000, 7 + 1000, 27 + 1000],
 434     multi_byte_chars: vec![(13 + 1000, 2), (29 + 1000, 2)],
 435     non_narrow_chars: vec![(2 + 1000, 4), (24 + 1000, 0)],
 436 );