crates/ra_ide_db/src/line_index.rs

   1 //! `LineIndex` maps flat `TextUnit` offsets into `(Line, Column)`
   2 //! representation.
   3
   4 use ra_syntax::TextUnit;
   5 use rustc_hash::FxHashMap;
   6 use superslice::Ext;
   7
   8 #[derive(Clone, Debug, PartialEq, Eq)]
   9 pub struct LineIndex {
  10     pub(crate) newlines: Vec<TextUnit>,
  11     pub(crate) utf16_lines: FxHashMap<u32, Vec<Utf16Char>>,
  12 }
  13
  14 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
  15 pub struct LineCol {
  16     /// Zero-based
  17     pub line: u32,
  18     /// Zero-based
  19     pub col_utf16: u32,
  20 }
  21
  22 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
  23 pub(crate) struct Utf16Char {
  24     pub(crate) start: TextUnit,
  25     pub(crate) end: TextUnit,
  26 }
  27
  28 impl Utf16Char {
  29     fn len(&self) -> TextUnit {
  30         self.end - self.start
  31     }
  32 }
  33
  34 impl LineIndex {
  35     pub fn new(text: &str) -> LineIndex {
  36         let mut utf16_lines = FxHashMap::default();
  37         let mut utf16_chars = Vec::new();
  38
  39         let mut newlines = vec![0.into()];
  40         let mut curr_row = 0.into();
  41         let mut curr_col = 0.into();
  42         let mut line = 0;
  43         for c in text.chars() {
  44             curr_row += TextUnit::of_char(c);
  45             if c == '\n' {
  46                 newlines.push(curr_row);
  47
  48                 // Save any utf-16 characters seen in the previous line
  49                 if !utf16_chars.is_empty() {
  50                     utf16_lines.insert(line, utf16_chars);
  51                     utf16_chars = Vec::new();
  52                 }
  53
  54                 // Prepare for processing the next line
  55                 curr_col = 0.into();
  56                 line += 1;
  57                 continue;
  58             }
  59
  60             let char_len = TextUnit::of_char(c);
  61             if char_len.to_usize() > 1 {
  62                 utf16_chars.push(Utf16Char { start: curr_col, end: curr_col + char_len });
  63             }
  64
  65             curr_col += char_len;
  66         }
  67
  68         // Save any utf-16 characters seen in the last line
  69         if !utf16_chars.is_empty() {
  70             utf16_lines.insert(line, utf16_chars);
  71         }
  72
  73         LineIndex { newlines, utf16_lines }
  74     }
  75
  76     pub fn line_col(&self, offset: TextUnit) -> LineCol {
  77         let line = self.newlines.upper_bound(&offset) - 1;
  78         let line_start_offset = self.newlines[line];
  79         let col = offset - line_start_offset;
  80
  81         LineCol { line: line as u32, col_utf16: self.utf8_to_utf16_col(line as u32, col) as u32 }
  82     }
  83
  84     pub fn offset(&self, line_col: LineCol) -> TextUnit {
  85         //FIXME: return Result
  86         let col = self.utf16_to_utf8_col(line_col.line, line_col.col_utf16);
  87         self.newlines[line_col.line as usize] + col
  88     }
  89
  90     fn utf8_to_utf16_col(&self, line: u32, mut col: TextUnit) -> usize {
  91         if let Some(utf16_chars) = self.utf16_lines.get(&line) {
  92             let mut correction = TextUnit::from_usize(0);
  93             for c in utf16_chars {
  94                 if col >= c.end {
  95                     correction += c.len() - TextUnit::from_usize(1);
  96                 } else {
  97                     // From here on, all utf16 characters come *after* the character we are mapping,
  98                     // so we don't need to take them into account
  99                     break;
 100                 }
 101             }
 102
 103             col -= correction;
 104         }
 105
 106         col.to_usize()
 107     }
 108
 109     fn utf16_to_utf8_col(&self, line: u32, col: u32) -> TextUnit {
 110         let mut col: TextUnit = col.into();
 111         if let Some(utf16_chars) = self.utf16_lines.get(&line) {
 112             for c in utf16_chars {
 113                 if col >= c.start {
 114                     col += c.len() - TextUnit::from_usize(1);
 115                 } else {
 116                     // From here on, all utf16 characters come *after* the character we are mapping,
 117                     // so we don't need to take them into account
 118                     break;
 119                 }
 120             }
 121         }
 122
 123         col
 124     }
 125 }
 126
 127 #[cfg(test)]
 128 /// Simple reference implementation to use in proptests
 129 pub fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
 130     let mut res = LineCol { line: 0, col_utf16: 0 };
 131     for (i, c) in text.char_indices() {
 132         if i + c.len_utf8() > offset.to_usize() {
 133             // if it's an invalid offset, inside a multibyte char
 134             // return as if it was at the start of the char
 135             break;
 136         }
 137         if c == '\n' {
 138             res.line += 1;
 139             res.col_utf16 = 0;
 140         } else {
 141             res.col_utf16 += 1;
 142         }
 143     }
 144     res
 145 }
 146
 147 #[cfg(test)]
 148 mod test_line_index {
 149     use super::*;
 150     use proptest::{prelude::*, proptest};
 151     use ra_text_edit::test_utils::{arb_offset, arb_text};
 152
 153     #[test]
 154     fn test_line_index() {
 155         let text = "hello\nworld";
 156         let index = LineIndex::new(text);
 157         assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
 158         assert_eq!(index.line_col(1.into()), LineCol { line: 0, col_utf16: 1 });
 159         assert_eq!(index.line_col(5.into()), LineCol { line: 0, col_utf16: 5 });
 160         assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 0 });
 161         assert_eq!(index.line_col(7.into()), LineCol { line: 1, col_utf16: 1 });
 162         assert_eq!(index.line_col(8.into()), LineCol { line: 1, col_utf16: 2 });
 163         assert_eq!(index.line_col(10.into()), LineCol { line: 1, col_utf16: 4 });
 164         assert_eq!(index.line_col(11.into()), LineCol { line: 1, col_utf16: 5 });
 165         assert_eq!(index.line_col(12.into()), LineCol { line: 1, col_utf16: 6 });
 166
 167         let text = "\nhello\nworld";
 168         let index = LineIndex::new(text);
 169         assert_eq!(index.line_col(0.into()), LineCol { line: 0, col_utf16: 0 });
 170         assert_eq!(index.line_col(1.into()), LineCol { line: 1, col_utf16: 0 });
 171         assert_eq!(index.line_col(2.into()), LineCol { line: 1, col_utf16: 1 });
 172         assert_eq!(index.line_col(6.into()), LineCol { line: 1, col_utf16: 5 });
 173         assert_eq!(index.line_col(7.into()), LineCol { line: 2, col_utf16: 0 });
 174     }
 175
 176     fn arb_text_with_offset() -> BoxedStrategy<(TextUnit, String)> {
 177         arb_text().prop_flat_map(|text| (arb_offset(&text), Just(text))).boxed()
 178     }
 179
 180     fn to_line_col(text: &str, offset: TextUnit) -> LineCol {
 181         let mut res = LineCol { line: 0, col_utf16: 0 };
 182         for (i, c) in text.char_indices() {
 183             if i + c.len_utf8() > offset.to_usize() {
 184                 // if it's an invalid offset, inside a multibyte char
 185                 // return as if it was at the start of the char
 186                 break;
 187             }
 188             if c == '\n' {
 189                 res.line += 1;
 190                 res.col_utf16 = 0;
 191             } else {
 192                 res.col_utf16 += 1;
 193             }
 194         }
 195         res
 196     }
 197
 198     proptest! {
 199         #[test]
 200         fn test_line_index_proptest((offset, text) in arb_text_with_offset()) {
 201             let expected = to_line_col(&text, offset);
 202             let line_index = LineIndex::new(&text);
 203             let actual = line_index.line_col(offset);
 204
 205             assert_eq!(actual, expected);
 206         }
 207     }
 208 }
 209
 210 #[cfg(test)]
 211 mod test_utf8_utf16_conv {
 212     use super::*;
 213
 214     #[test]
 215     fn test_char_len() {
 216         assert_eq!('メ'.len_utf8(), 3);
 217         assert_eq!('メ'.len_utf16(), 1);
 218     }
 219
 220     #[test]
 221     fn test_empty_index() {
 222         let col_index = LineIndex::new(
 223             "
 224 const C: char = 'x';
 225 ",
 226         );
 227         assert_eq!(col_index.utf16_lines.len(), 0);
 228     }
 229
 230     #[test]
 231     fn test_single_char() {
 232         let col_index = LineIndex::new(
 233             "
 234 const C: char = 'メ';
 235 ",
 236         );
 237
 238         assert_eq!(col_index.utf16_lines.len(), 1);
 239         assert_eq!(col_index.utf16_lines[&1].len(), 1);
 240         assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
 241
 242         // UTF-8 to UTF-16, no changes
 243         assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
 244
 245         // UTF-8 to UTF-16
 246         assert_eq!(col_index.utf8_to_utf16_col(1, 22.into()), 20);
 247
 248         // UTF-16 to UTF-8, no changes
 249         assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from(15));
 250
 251         // UTF-16 to UTF-8
 252         assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from(21));
 253     }
 254
 255     #[test]
 256     fn test_string() {
 257         let col_index = LineIndex::new(
 258             "
 259 const C: char = \"メ メ\";
 260 ",
 261         );
 262
 263         assert_eq!(col_index.utf16_lines.len(), 1);
 264         assert_eq!(col_index.utf16_lines[&1].len(), 2);
 265         assert_eq!(col_index.utf16_lines[&1][0], Utf16Char { start: 17.into(), end: 20.into() });
 266         assert_eq!(col_index.utf16_lines[&1][1], Utf16Char { start: 21.into(), end: 24.into() });
 267
 268         // UTF-8 to UTF-16
 269         assert_eq!(col_index.utf8_to_utf16_col(1, 15.into()), 15);
 270
 271         assert_eq!(col_index.utf8_to_utf16_col(1, 21.into()), 19);
 272         assert_eq!(col_index.utf8_to_utf16_col(1, 25.into()), 21);
 273
 274         assert!(col_index.utf8_to_utf16_col(2, 15.into()) == 15);
 275
 276         // UTF-16 to UTF-8
 277         assert_eq!(col_index.utf16_to_utf8_col(1, 15), TextUnit::from_usize(15));
 278
 279         assert_eq!(col_index.utf16_to_utf8_col(1, 18), TextUnit::from_usize(20));
 280         assert_eq!(col_index.utf16_to_utf8_col(1, 19), TextUnit::from_usize(23));
 281
 282         assert_eq!(col_index.utf16_to_utf8_col(2, 15), TextUnit::from_usize(15));
 283     }
 284 }