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.
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.
11 use unicode_width::UnicodeWidthChar;
14 /// Find all newlines, multi-byte characters, and non-narrow characters in a
17 /// This function will use an SSE2 enhanced implementation if hardware support
18 /// is detected at runtime.
19 pub fn analyze_source_file(
21 source_file_start_pos: BytePos)
22 -> (Vec<BytePos>, Vec<MultiByteChar>, Vec<NonNarrowChar>)
24 let mut lines = vec![source_file_start_pos];
25 let mut multi_byte_chars = vec![];
26 let mut non_narrow_chars = vec![];
28 // Calls the right implementation, depending on hardware support available.
29 analyze_source_file_dispatch(src,
30 source_file_start_pos,
32 &mut multi_byte_chars,
33 &mut non_narrow_chars);
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
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 {
46 (lines, multi_byte_chars, non_narrow_chars)
50 if #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"),
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") {
59 analyze_source_file_sse2(src,
60 source_file_start_pos,
66 analyze_source_file_generic(src,
68 source_file_start_pos,
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::*;
91 const CHUNK_SIZE: usize = 16;
93 let src_bytes = src.as_bytes();
95 let chunk_count = src.len() / CHUNK_SIZE;
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
101 let mut intra_chunk_offset = 0;
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));
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);
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);
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);
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);
129 let control_char_mask = control_char_mask0 | control_char_mask1;
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);
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);
143 let index = newlines_mask.trailing_zeros();
145 if index >= CHUNK_SIZE as u32 {
146 // We have arrived at the end of the chunk.
150 lines.push(BytePos(index) + output_offset);
152 // Clear the bit, so we can find the next one.
153 newlines_mask &= (!1) << index;
156 // We are done for this chunk. All control characters were
157 // newlines and we took care of those.
160 // Some of the control characters are not newlines,
161 // fall through to the slow path below.
164 // No control characters, nothing to record for this chunk
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,
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),
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,
203 source_file_start_pos,
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,
216 output_offset: BytePos,
217 lines: &mut Vec<BytePos>,
218 multi_byte_chars: &mut Vec<MultiByteChar>,
219 non_narrow_chars: &mut Vec<NonNarrowChar>)
222 assert!(src.len() >= scan_len);
224 let src_bytes = src.as_bytes();
228 // We verified that i < scan_len <= src.len()
229 *src_bytes.get_unchecked(i as usize)
232 // How much to advance in order to get to the next UTF-8 char in the
234 let mut char_len = 1;
237 // This is an ASCII control character, it could be one of the cases
238 // that are interesting to us.
240 let pos = BytePos::from_usize(i) + output_offset;
244 lines.push(pos + BytePos(1));
247 non_narrow_chars.push(NonNarrowChar::Tab(pos));
250 non_narrow_chars.push(NonNarrowChar::ZeroWidth(pos));
253 } else if byte >= 127 {
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();
260 let pos = BytePos::from_usize(i) + output_offset;
263 assert!(char_len >=2 && char_len <= 4);
264 let mbc = MultiByteChar {
266 bytes: char_len as u8,
268 multi_byte_chars.push(mbc);
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);
276 non_narrow_chars.push(NonNarrowChar::new(pos, char_width));
289 (case: $test_name:ident,
291 source_file_start_pos: $source_file_start_pos:expr,
293 multi_byte_chars: $multi_byte_chars:expr,
294 non_narrow_chars: $non_narrow_chars:expr,) => (
299 let (lines, multi_byte_chars, non_narrow_chars) =
300 analyze_source_file($text, BytePos($source_file_start_pos));
302 let expected_lines: Vec<BytePos> = $lines
304 .map(|pos| BytePos(pos))
307 assert_eq!(lines, expected_lines);
309 let expected_mbcs: Vec<MultiByteChar> = $multi_byte_chars
311 .map(|(pos, bytes)| MultiByteChar {
317 assert_eq!(multi_byte_chars, expected_mbcs);
319 let expected_nncs: Vec<NonNarrowChar> = $non_narrow_chars
321 .map(|(pos, width)| {
322 NonNarrowChar::new(BytePos(pos), width)
326 assert_eq!(non_narrow_chars, expected_nncs);
333 source_file_start_pos: 0,
335 multi_byte_chars: vec![],
336 non_narrow_chars: vec![],
340 case: newlines_short,
342 source_file_start_pos: 0,
344 multi_byte_chars: vec![],
345 non_narrow_chars: vec![],
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![],
358 case: newline_and_multi_byte_char_in_same_chunk,
359 text: "01234β789\nbcdef0123456789abcdef",
360 source_file_start_pos: 0,
362 multi_byte_chars: vec![(5, 2)],
363 non_narrow_chars: vec![],
367 case: newline_and_control_char_in_same_chunk,
368 text: "01234\u{07}6789\nbcdef0123456789abcdef",
369 source_file_start_pos: 0,
371 multi_byte_chars: vec![],
372 non_narrow_chars: vec![(5, 0)],
376 case: multi_byte_char_short,
378 source_file_start_pos: 0,
380 multi_byte_chars: vec![(1, 2)],
381 non_narrow_chars: vec![],
385 case: multi_byte_char_long,
386 text: "0123456789abcΔf012345β",
387 source_file_start_pos: 0,
389 multi_byte_chars: vec![(13, 2), (22, 2)],
390 non_narrow_chars: vec![],
394 case: multi_byte_char_across_chunk_boundary,
395 text: "0123456789abcdeΔ123456789abcdef01234",
396 source_file_start_pos: 0,
398 multi_byte_chars: vec![(15, 2)],
399 non_narrow_chars: vec![],
403 case: multi_byte_char_across_chunk_boundary_tail,
404 text: "0123456789abcdeΔ....",
405 source_file_start_pos: 0,
407 multi_byte_chars: vec![(15, 2)],
408 non_narrow_chars: vec![],
412 case: non_narrow_short,
414 source_file_start_pos: 0,
416 multi_byte_chars: vec![],
417 non_narrow_chars: vec![(1, 4)],
421 case: non_narrow_long,
422 text: "01\t3456789abcdef01234567\u{07}9",
423 source_file_start_pos: 0,
425 multi_byte_chars: vec![],
426 non_narrow_chars: vec![(2, 4), (24, 0)],
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)],