lsp-lang 2.0.0

Language Server Protocol scaffolding on our own stack: server lifecycle, incremental document sync, diagnostics, and typed semantic tokens, symbols, hover, definition, and completion. No third-party dependencies.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
//! The line index behind every [`Document`](crate::Document): line start
//! offsets, kept current under edits, and the conversions between byte offsets
//! and protocol positions.
//!
//! # Line breaks
//!
//! The protocol counts `\n`, `\r\n`, and a lone `\r` as line breaks, so a byte
//! offset `s > 0` starts a line exactly when the byte before it is `\n`, or is
//! `\r` not followed by `\n`. Whether `s` starts a line therefore depends only on
//! the bytes at `s - 1` and `s`. That locality is what makes the incremental
//! update in [`LineIndex::edit`] exact: only starts whose two deciding bytes an
//! edit touched can change, and those are recomputed from the new text.
//!
//! # Columns
//!
//! A column is the length of the line's text before the offset, measured in the
//! session [`Encoding`]. UTF-8 columns are byte counts and need no scan. UTF-16
//! columns are counted over the line prefix with branch-free byte arithmetic
//! (every non-continuation byte begins a scalar value; every 4-byte lead adds a
//! surrogate), which the compiler vectorizes.

use crate::position::{Encoding, Position};

/// Byte offsets at which each line starts. `starts[0]` is always `0`, so the
/// index of an empty text has one (empty) line, as the protocol expects.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct LineIndex {
    starts: Vec<u32>,
}

impl LineIndex {
    /// Indexes `text` from scratch.
    pub(crate) fn new(text: &str) -> Self {
        let bytes = text.as_bytes();
        let mut starts = Vec::with_capacity(1 + bytes.len() / 40);
        starts.push(0);
        starts.extend(breaks(bytes, 0, bytes.len()));
        Self { starts }
    }

    /// Number of lines (always at least one).
    pub(crate) fn len(&self) -> usize {
        self.starts.len()
    }

    /// Brings the index up to date after the bytes `start..old_end` were
    /// replaced by `inserted` bytes. `text` is the text *after* the edit.
    ///
    /// Starts in `max(start, 1)..=old_end` are the only ones whose deciding
    /// bytes changed (see the module docs); they are dropped and recomputed by
    /// scanning the new bytes from one before the edit to its new end. Starts
    /// after `old_end` keep their line-breaking bytes and shift by the change in
    /// length. The cost is a binary search, a scan of the inserted text, and one
    /// pass adding a constant over the starts after the edit.
    pub(crate) fn edit(&mut self, text: &str, start: u32, old_end: u32, inserted: u32) {
        let lo = start.max(1);
        let first = self.starts.partition_point(|&s| s < lo);
        let last = self.starts.partition_point(|&s| s <= old_end).max(first);

        // Modular arithmetic: every shifted start lands inside the new text, so
        // the wrapped sum is the exact result.
        let delta = inserted.wrapping_sub(old_end - start);
        for s in &mut self.starts[last..] {
            *s = s.wrapping_add(delta);
        }

        let bytes = text.as_bytes();
        let from = (lo - 1) as usize;
        let to = (start + inserted) as usize;
        drop(
            self.starts
                .splice(first..last, breaks(bytes, from, to.max(from))),
        );
    }

    /// Converts a byte offset into a position.
    ///
    /// An offset past the end is clamped to the end; one inside a multi-byte
    /// character is rounded down to that character's first byte.
    pub(crate) fn position(&self, text: &str, offset: u32, encoding: Encoding) -> Position {
        let offset = floor_boundary(text, offset);
        let line = self.line_of(offset);
        let start = self.starts[line] as usize;
        let character = width(&text.as_bytes()[start..offset], encoding);
        Position::new(line as u32, character)
    }

    /// Converts many byte offsets at once: `out[i]` becomes the position of
    /// `offsets[i]`, exactly as [`position`](LineIndex::position) would give.
    ///
    /// Converting one offset counts its line from the start; converting `n`
    /// offsets on one long line one by one would count the same prefix `n`
    /// times. Here the offsets are visited in ascending order (through
    /// `order`, a reused scratch buffer) and each column continues from the
    /// previous offset on the same line, so every byte of text is counted at
    /// most once: `O(n log n)` plus the text spanned, whatever the order of
    /// `offsets`.
    pub(crate) fn positions(
        &self,
        text: &str,
        offsets: &[u32],
        encoding: Encoding,
        order: &mut Vec<u32>,
        out: &mut Vec<Position>,
    ) {
        out.clear();
        out.resize(offsets.len(), Position::default());
        order.clear();
        order.extend(0..offsets.len() as u32);
        order.sort_unstable_by_key(|&i| offsets[i as usize]);
        let bytes = text.as_bytes();
        // (line, byte offset, column) of the previous conversion.
        let mut cursor: Option<(usize, usize, u32)> = None;
        for &i in order.iter() {
            let offset = floor_boundary(text, offsets[i as usize]);
            let line = self.line_of(offset);
            let (from, base) = match cursor {
                // Ascending order: an earlier offset on the same line is never
                // past this one.
                Some((at_line, at, column)) if at_line == line => (at, column),
                _ => (self.starts[line] as usize, 0),
            };
            let column = base + width(&bytes[from..offset], encoding);
            cursor = Some((line, offset, column));
            out[i as usize] = Position::new(line as u32, column);
        }
    }

    /// The line containing byte `offset` (a character boundary within the
    /// text).
    #[inline]
    fn line_of(&self, offset: usize) -> usize {
        self.starts
            .partition_point(|&s| s as usize <= offset)
            .saturating_sub(1)
    }

    /// Converts a position into a byte offset.
    ///
    /// Follows the protocol's leniency rules rather than rejecting input: a line
    /// past the last one maps to the end of the text, and a column past the end
    /// of its line maps to the end of that line (before its line break). A column
    /// that falls inside a character — in the middle of a surrogate pair, or
    /// between the bytes of a UTF-8 sequence — is rounded down to the start of
    /// that character, so the result is always a character boundary.
    pub(crate) fn offset(&self, text: &str, position: Position, encoding: Encoding) -> u32 {
        let line = position.line as usize;
        let Some(&start) = self.starts.get(line) else {
            return text.len() as u32;
        };
        let start = start as usize;
        let bytes = text.as_bytes();
        let end = match self.starts.get(line + 1) {
            Some(&next) => content_end(bytes, start, next as usize),
            None => bytes.len(),
        };
        // `start` follows a line break (or is 0) and `end` precedes one (or is
        // the end), so both are character boundaries.
        let content = &text[start..end];
        let column = position.character as usize;
        let within = match encoding {
            Encoding::Utf8 => {
                let mut at = column.min(content.len());
                while !content.is_char_boundary(at) {
                    at -= 1;
                }
                at
            }
            Encoding::Utf16 => utf16_column_to_byte(content, column),
        };
        (start + within) as u32
    }
}

/// `offset` clamped to the text and rounded down to a character boundary.
#[inline]
fn floor_boundary(text: &str, offset: u32) -> usize {
    let mut offset = (offset as usize).min(text.len());
    while !text.is_char_boundary(offset) {
        offset -= 1;
    }
    offset
}

/// Width of `prefix` (valid UTF-8 on character boundaries) in `encoding`.
#[inline]
pub(crate) fn width(prefix: &[u8], encoding: Encoding) -> u32 {
    match encoding {
        Encoding::Utf8 => prefix.len() as u32,
        Encoding::Utf16 => utf16_len(prefix),
    }
}

/// Line starts produced by the line breaks in `bytes[from..to]`, in order.
///
/// Each `\n` and each `\r` not followed by `\n` at index `p` yields `p + 1`. The
/// `\r\n` test may read the byte just past `to`, which is what the line-break
/// rule asks for.
fn breaks(bytes: &[u8], from: usize, to: usize) -> impl Iterator<Item = u32> + '_ {
    BreakBytes::new(&bytes[from..to]).filter_map(move |i| {
        let p = from + i;
        if bytes[p] == b'\r' && bytes.get(p + 1) == Some(&b'\n') {
            None
        } else {
            Some((p + 1) as u32)
        }
    })
}

/// The index of the first line-break byte (`\n` or `\r`) of `bytes`.
pub(crate) fn find_line_break(bytes: &[u8]) -> Option<usize> {
    BreakBytes::new(bytes).next()
}

/// The indexes of the `\n` and `\r` bytes of a slice, in order.
///
/// Source text is mostly bytes that are not line breaks, so the scan looks at
/// eight bytes per step: a word has a break byte exactly when one of its bytes
/// XORed with `\n` (or `\r`) is zero, which the classic "has a zero byte" bit
/// trick answers for the whole word at once. Only a word that has one is
/// examined byte by byte. This is plain safe Rust; the word test compiles to
/// a handful of instructions.
struct BreakBytes<'a> {
    bytes: &'a [u8],
    at: usize,
}

impl<'a> BreakBytes<'a> {
    fn new(bytes: &'a [u8]) -> Self {
        Self { bytes, at: 0 }
    }
}

/// Whether any byte of `word` is zero. Exact as a yes/no answer: the borrow
/// the subtraction can carry upward only appears above a byte that is itself
/// zero.
#[inline]
const fn has_zero_byte(word: u64) -> bool {
    const LOW: u64 = 0x0101_0101_0101_0101;
    const HIGH: u64 = 0x8080_8080_8080_8080;
    (word.wrapping_sub(LOW) & !word & HIGH) != 0
}

impl Iterator for BreakBytes<'_> {
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        const LF: u64 = 0x0A0A_0A0A_0A0A_0A0A;
        const CR: u64 = 0x0D0D_0D0D_0D0D_0D0D;
        let rest = self.bytes.get(self.at..)?;
        let mut offset = 0;
        for chunk in rest.chunks_exact(8) {
            let word = chunk
                .first_chunk::<8>()
                .map_or(0, |b| u64::from_le_bytes(*b));
            if has_zero_byte(word ^ LF) || has_zero_byte(word ^ CR) {
                break;
            }
            offset += 8;
        }
        let found = rest
            .get(offset..)?
            .iter()
            .position(|&b| b == b'\n' || b == b'\r')?;
        let index = self.at + offset + found;
        self.at = index + 1;
        Some(index)
    }
}

/// End of a line's content: `next` (the start of the following line) less the
/// line break that precedes it.
fn content_end(bytes: &[u8], start: usize, next: usize) -> usize {
    let mut end = next;
    if end > start && bytes[end - 1] == b'\n' {
        end -= 1;
    }
    if end > start && bytes[end - 1] == b'\r' {
        end -= 1;
    }
    end
}

/// Byte offset within `line` of the character at UTF-16 `column`. Stops at
/// the character that would straddle `column` (the first half of a surrogate
/// pair), so the result is a character boundary.
fn utf16_column_to_byte(line: &str, column: usize) -> usize {
    let bytes = line.as_bytes();
    let limit = column.min(bytes.len());
    // An ASCII character is one UTF-16 unit, so an ASCII prefix maps column to
    // byte one to one.
    let ascii = bytes[..limit]
        .iter()
        .position(|b| !b.is_ascii())
        .unwrap_or(limit);
    if ascii == limit {
        return limit;
    }
    let mut units = ascii;
    for (i, c) in line[ascii..].char_indices() {
        let width = c.len_utf16();
        if units + width > column {
            return ascii + i;
        }
        units += width;
    }
    line.len()
}

/// Number of UTF-16 code units in `bytes` (valid UTF-8): one per scalar value,
/// plus one more for each 4-byte sequence, which needs a surrogate pair.
#[inline]
fn utf16_len(bytes: &[u8]) -> u32 {
    bytes
        .iter()
        .map(|&b| u32::from((b as i8) >= -0x40) + u32::from(b >= 0xF0))
        .sum()
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;

    use super::*;

    /// Line starts by the protocol's definition, computed the slow, obvious way.
    fn model_starts(text: &str) -> Vec<u32> {
        let b = text.as_bytes();
        let mut starts = vec![0];
        for s in 1..=b.len() {
            let prev = b[s - 1];
            if prev == b'\n' || (prev == b'\r' && b.get(s) != Some(&b'\n')) {
                starts.push(s as u32);
            }
        }
        starts
    }

    fn model_width(s: &str, encoding: Encoding) -> u32 {
        match encoding {
            Encoding::Utf8 => s.len() as u32,
            Encoding::Utf16 => s.encode_utf16().count() as u32,
        }
    }

    const ALL: [Encoding; 2] = [Encoding::Utf8, Encoding::Utf16];

    #[test]
    fn test_break_bytes_finds_every_break_at_every_alignment() {
        // A break at each position of a run, so every lane of the word test and
        // the remainder path are exercised.
        for len in 0..40usize {
            for at in 0..len {
                for byte in *b"\n\r" {
                    let mut bytes = vec![b'x'; len];
                    bytes[at] = byte;
                    let found: Vec<usize> = BreakBytes::new(&bytes).collect();
                    assert_eq!(found, vec![at], "len {len}, at {at}");
                }
            }
        }
        let all: Vec<usize> = BreakBytes::new(b"\n\r\n\rabcdefghij\n").collect();
        assert_eq!(all, vec![0, 1, 2, 3, 14]);
        assert_eq!(BreakBytes::new(b"").count(), 0);
        // Bytes near the break values must not match.
        let near = [0x0B, 0x0C, 0x0E, 0x8A, 0x8D, 0x0B, 0x0C, 0x0E, 0x8A, 0x8D];
        assert_eq!(BreakBytes::new(&near).count(), 0);
    }

    #[test]
    fn test_index_new_empty_text_has_one_line() {
        let index = LineIndex::new("");
        assert_eq!(index.len(), 1);
        assert_eq!(index.position("", 0, Encoding::Utf16), Position::new(0, 0));
        assert_eq!(index.offset("", Position::new(0, 5), Encoding::Utf16), 0);
    }

    #[test]
    fn test_index_new_counts_every_break_style() {
        let text = "a\nb\r\nc\rd";
        assert_eq!(LineIndex::new(text).starts, vec![0, 2, 5, 7]);
        // A trailing break opens a final empty line.
        assert_eq!(LineIndex::new("x\n").starts, vec![0, 2]);
        assert_eq!(LineIndex::new("x\r").starts, vec![0, 2]);
        assert_eq!(LineIndex::new("\r\n\r\n").starts, vec![0, 2, 4]);
    }

    #[test]
    fn test_position_counts_columns_in_each_encoding() {
        let text = "é😀x";
        let index = LineIndex::new(text);
        // Offset of `x`: 2 bytes for é, 4 for 😀.
        assert_eq!(index.position(text, 6, Encoding::Utf8), Position::new(0, 6));
        assert_eq!(
            index.position(text, 6, Encoding::Utf16),
            Position::new(0, 3)
        );
    }

    #[test]
    fn test_position_inside_character_rounds_down() {
        let text = "a😀b";
        let index = LineIndex::new(text);
        for inside in 2..5 {
            assert_eq!(
                index.position(text, inside, Encoding::Utf16),
                Position::new(0, 1)
            );
        }
    }

    #[test]
    fn test_position_past_end_clamps_to_end() {
        let text = "ab\ncd";
        let index = LineIndex::new(text);
        assert_eq!(
            index.position(text, 999, Encoding::Utf16),
            Position::new(1, 2)
        );
    }

    #[test]
    fn test_offset_column_past_line_end_clamps_before_break() {
        let text = "ab\r\ncd";
        let index = LineIndex::new(text);
        assert_eq!(index.offset(text, Position::new(0, 99), Encoding::Utf16), 2);
        assert_eq!(index.offset(text, Position::new(1, 99), Encoding::Utf16), 6);
    }

    #[test]
    fn test_offset_line_past_end_maps_to_end() {
        let text = "ab\ncd";
        let index = LineIndex::new(text);
        assert_eq!(index.offset(text, Position::new(7, 0), Encoding::Utf8), 5);
    }

    #[test]
    fn test_offset_inside_surrogate_pair_rounds_down() {
        let text = "a😀b";
        let index = LineIndex::new(text);
        // Column 2 is between the two surrogates of 😀.
        assert_eq!(index.offset(text, Position::new(0, 2), Encoding::Utf16), 1);
        assert_eq!(index.offset(text, Position::new(0, 3), Encoding::Utf16), 5);
        // A UTF-8 column inside the sequence also rounds down.
        assert_eq!(index.offset(text, Position::new(0, 3), Encoding::Utf8), 1);
    }

    #[test]
    fn test_edit_joining_cr_and_lf_merges_the_break() {
        // "x\ry": inserting "\n" after "\r" turns two breaks' worth into one.
        let mut index = LineIndex::new("x\ry");
        index.edit("x\r\ny", 2, 2, 1);
        assert_eq!(index, LineIndex::new("x\r\ny"));
        // Deleting the "\n" of "\r\n" leaves a lone "\r" break.
        index.edit("x\ry", 2, 3, 0);
        assert_eq!(index, LineIndex::new("x\ry"));
    }

    #[test]
    fn test_edit_at_start_keeps_line_zero() {
        let mut index = LineIndex::new("\nab");
        index.edit("ab", 0, 1, 0);
        assert_eq!(index, LineIndex::new("ab"));
        index.edit("\n\nab", 0, 0, 2);
        assert_eq!(index, LineIndex::new("\n\nab"));
    }

    fn text_strategy() -> impl Strategy<Value = String> {
        prop::collection::vec(
            prop::sample::select(vec!["a", "b", " ", "\n", "\r", "\r\n", "é", "😀", "中"]),
            0..40,
        )
        .prop_map(|parts| parts.concat())
    }

    /// Snaps a byte offset down to a character boundary of `text`.
    fn floor(text: &str, mut at: usize) -> usize {
        at = at.min(text.len());
        while !text.is_char_boundary(at) {
            at -= 1;
        }
        at
    }

    proptest! {
        #![proptest_config(ProptestConfig::with_cases(512))]

        #[test]
        fn prop_new_matches_model(text in text_strategy()) {
            prop_assert_eq!(LineIndex::new(&text).starts, model_starts(&text));
        }

        #[test]
        fn prop_edits_match_fresh_index(
            initial in text_strategy(),
            edits in prop::collection::vec((0usize..64, 0usize..64, text_strategy()), 1..8),
        ) {
            let mut text = initial;
            let mut index = LineIndex::new(&text);
            for (a, b, insert) in edits {
                let (a, b) = (floor(&text, a.min(b)), floor(&text, a.max(b)));
                text.replace_range(a..b, &insert);
                index.edit(&text, a as u32, b as u32, insert.len() as u32);
                prop_assert_eq!(&index.starts, &model_starts(&text));
            }
        }

        #[test]
        fn prop_position_matches_model_and_round_trips(text in text_strategy(), at in 0usize..200) {
            let index = LineIndex::new(&text);
            let offset = floor(&text, at);
            let starts = model_starts(&text);
            let line = starts.iter().rposition(|&s| s as usize <= offset).unwrap_or(0);
            let start = starts[line] as usize;
            // An offset between the `\r` and `\n` of one break is not a caret
            // position and does not round-trip; every other boundary does.
            let inside_crlf = offset > 0
                && text.as_bytes()[offset - 1] == b'\r'
                && text.as_bytes().get(offset) == Some(&b'\n');
            for encoding in ALL {
                let pos = index.position(&text, offset as u32, encoding);
                prop_assert_eq!(pos.line as usize, line);
                prop_assert_eq!(pos.character, model_width(&text[start..offset], encoding));
                if !inside_crlf {
                    prop_assert_eq!(index.offset(&text, pos, encoding) as usize, offset);
                }
            }
        }

        #[test]
        fn prop_batch_positions_match_single_positions(
            text in text_strategy(),
            offsets in prop::collection::vec(0u32..220, 0..24),
        ) {
            let index = LineIndex::new(&text);
            let (mut order, mut out) = (Vec::new(), Vec::new());
            for encoding in ALL {
                index.positions(&text, &offsets, encoding, &mut order, &mut out);
                let single: Vec<Position> =
                    offsets.iter().map(|&o| index.position(&text, o, encoding)).collect();
                prop_assert_eq!(&out, &single);
            }
        }

        #[test]
        fn prop_offset_is_always_a_boundary_in_range(
            text in text_strategy(),
            line in 0u32..12,
            character in 0u32..40,
        ) {
            let index = LineIndex::new(&text);
            for encoding in ALL {
                let offset = index.offset(&text, Position::new(line, character), encoding) as usize;
                prop_assert!(offset <= text.len());
                prop_assert!(text.is_char_boundary(offset));
            }
        }
    }
}