Text position encoding

Deep dive

How it works

In: text, plus an offset or a (line, column, unit) · Out: the other form · State: the line-start table, valid for one text version · Cost: O(log lines) + O(line length) per conversion

1. Choose the unit. Offsets: bytes of UTF-8 (Rust, Go, rustc BytePos) or UTF-16 code units (JavaScript, TypeScript, Java, C#). Columns: whatever the protocol says; LSP 3.17: client lists general.positionEncodings in preference order, server answers capabilities.positionEncoding, absent means utf-16.
2. Scan once for line terminators and push the offset after each: \n; \r not followed by \n; the \n of \r\n. starts[0] = 0.
3. Offset to line: partition_point(|s| s <= offset) - 1 on the table.
4. Offset to column: walk the characters from the line start to the offset, adding 1 (UTF-8 bytes: len_utf8; UTF-16: len_utf16 = 1 or 2; UTF-32: 1). ASCII-only line: column = offset - start.
5. Position to offset: starts[line], then walk characters, adding unit lengths until the column is reached. A column past the end of the line clamps to the line end (LSP).
6. Edits invalidate the table from the edit's line onward; rebuild the suffix or the whole table.

A UTF-16 column that lands inside a surrogate pair (emoji at units 3-4, column 4) is invalid input; round down to the character start rather than splitting it.

Code

LineIndex over a &str: line starts as u32, offset to (line, UTF-16 column) and back, CR, LF and CRLF.

pub struct LineIndex<'a> {
    text: &'a str,
    starts: Vec<u32>, // byte offset of each line's first byte; starts[0] == 0
}

impl<'a> LineIndex<'a> {
    pub fn new(text: &'a str) -> Self {
        assert!(text.len() <= u32::MAX as usize);
        let b = text.as_bytes();
        let mut starts = vec![0u32];
        for i in 0..b.len() {
            match b[i] {
                b'\n' => starts.push(i as u32 + 1),
                // lone CR ends a line; the CR of CR LF is covered by the LF
                b'\r' if b.get(i + 1) != Some(&b'\n') => starts.push(i as u32 + 1),
                _ => {}
            }
        }
        LineIndex { text, starts }
    }

    /// Content end of `line`, excluding its terminator.
    fn line_end(&self, line: usize) -> usize {
        let end = self.starts.get(line + 1).map_or(self.text.len(), |&s| s as usize);
        let t = &self.text[..end];
        t.strip_suffix("\r\n").or_else(|| t.strip_suffix(['\n', '\r'])).unwrap_or(t).len()
    }

    /// Byte offset (on a char boundary) -> (line, UTF-16 column).
    pub fn to_position(&self, offset: usize) -> (u32, u32) {
        let line = self.starts.partition_point(|&s| s as usize <= offset) - 1;
        let start = self.starts[line] as usize;
        let col = self.text[start..offset].chars().map(|c| c.len_utf16() as u32).sum();
        (line as u32, col)
    }

    /// (line, UTF-16 column) -> byte offset. A column past the line end clamps to
    /// the end; one inside a surrogate pair rounds down to the character start.
    pub fn to_offset(&self, line: u32, col: u32) -> Option<usize> {
        let line = line as usize;
        let start = *self.starts.get(line)? as usize;
        let (mut units, mut off) = (0u32, start);
        for c in self.text[start..self.line_end(line)].chars() {
            if units + c.len_utf16() as u32 > col { break; }
            units += c.len_utf16() as u32;
            off += c.len_utf8();
        }
        Some(off)
    }
}

fn main() {
    // 'é' = 2 bytes / 1 unit; '😀' = 4 bytes / 2 units; CRLF, lone CR, empty line
    let s = "é😀x\r\nab\rcd\n\nlast";
    let ix = LineIndex::new(s);
    assert_eq!(ix.starts, vec![0, 9, 12, 15, 16]);
    assert_eq!(ix.to_position(2), (0, 1)); // after é
    assert_eq!(ix.to_position(6), (0, 3)); // after 😀: two UTF-16 units
    assert_eq!(ix.to_position(9), (1, 0)); // after CRLF
    assert_eq!(ix.to_position(12), (2, 0)); // after lone CR
    assert_eq!(ix.to_offset(0, 3), Some(6));
    assert_eq!(ix.to_offset(0, 2), Some(2)); // inside the pair: rounds down
    assert_eq!(ix.to_offset(0, 99), Some(7)); // clamps before "\r\n"
    assert_eq!(ix.to_offset(9, 0), None);
    for off in (0..=s.len()).filter(|&o| s.is_char_boundary(o) && o != 8) {
        let (l, c) = ix.to_position(off); // 8 = between CR and LF: not addressable
        assert_eq!(ix.to_offset(l, c), Some(off));
    }
}

Compiled and run (stable Rust, all asserts pass).

Complexity and constants

• Build: one pass, O(file); the table is 4 bytes per line (a 200k-line file: 800 KB). Lookup of a line: log2(200k) is about 18 probes in a table that fits L2.
• Column: O(line length), because UTF-8 to UTF-16 has no closed form; ASCII lines are O(1).
• Measured (my bench, Apple M4 Pro, release build, 9.6 MB, 200k lines of ~48 bytes with a few non-ASCII chars; naive byte loop with match): build 3.9 ms (about 2.8 GB/s), to_position about 100 ns, to_offset about 55 ns per call, random lines.
• Cost drivers: bytes scanned per build, cache misses on the table (binary search), characters walked per column. Make it cheap by building once per document version and caching per-line "has non-ASCII" facts.

Efficiency

• Cost: build is branch/bandwidth bound (measured above: about 2.8 GB/s for a plain loop); a conversion is one binary search plus a short scan of one line (measured above: 55-100 ns incl. random access); no syscalls, no allocation after the build.
• Levers:
  • Vectorised newline search — faster than a byte loop when newlines are sparse (memchr is SIMD-accelerated; I did not measure it) — large files, built once.
  • u32 offsets and ranges — half the memory of usize, 8-byte spans (rustc Span, see source) — files under 4 GiB.
  • Keep only non-ASCII characters per line (rust-analyzer line-index) — ASCII lines convert in O(1) and cost no extra memory — mostly-ASCII source.
  • Negotiate utf-8 (LSP 3.17) — no conversion for UTF-8 servers, the server skips the scan entirely — when both sides support it.
  • Incremental table update on edit — rebuild only the suffix from the edited line — editor workloads with many small edits.
  • Batch: sort the offsets of a diagnostic list and walk the table once — O(n + lines) instead of O(n log lines) — thousands of positions per request.
• Naive → standard → state of the art:
  • Rescan from the file start for every position · O(file) per request
  • Line-start table + binary search + scan of one line · O(log lines + line)
  • Table plus per-line non-ASCII index, SIMD build, 8-byte compact spans, negotiated UTF-8 · O(log lines), usually no column scan

Implementation notes

• Keep byte offsets as the single source of truth; convert at the API boundary only. Store spans as (start: u32, len: u32), or pack more as rustc does (a compressed 8-byte Span with an interned fallback for large or rare cases).
• Never mix units in one type: a newtype per unit (Utf16Col, ByteOff) turns the classic bug into a compile error.
• Convert on the side that owns the text (LSP spec: usually the server).
• Reject or clamp invalid offsets (mid-character) explicitly; str slicing panics on them.
• TypeScript and JavaScript offsets are UTF-16 indices into the string already; they need no conversion for a UTF-16 peer.

Pitfalls

• Using JavaScript string length or Rust chars().count() as a "column": the first counts UTF-16 units, the second code points; they differ on non-BMP text (emoji).
• Treating \r\n as two lines, or counting \r as a column; a lone \r is also a line break in LSP.
• A tab is one column unit, not four; display width is a different problem.
• Grapheme clusters (a flag, a skin-toned emoji, e plus a combining accent) span several code points: no protocol counts them in columns; use them only for cursor movement (UAX #29).
• Stale table: reusing a table after an edit gives plausible but wrong positions; tie the table to a document version.
• Columns past the line end are legal input and clamp; offsets that are not character boundaries are not.

Variants and alternatives

In production

• Editors and IDEs: language servers convert at every request (rust-analyzer line-index crate; vscode-languageserver-node text documents); the debug adapter protocol has its own line and column base settings (linesStartAt1, columnsStartAt1, spec). Editors with rope buffers keep line and UTF-16 metadata in the tree.
• Compilers: rustc stores BytePos and Span and resolves lines lazily from a per-file line table for diagnostics.
• Web tooling: source maps count columns in UTF-16 code units for JavaScript and CSS (ECMA-426).
• Databases: PostgreSQL reports an error position as a 1-based character index into the query string, "in characters not bytes" (protocol).

Implementations

Sources

• Microsoft, Language Server Protocol Specification 3.17, sections "Position" and "Text Documents" (position encoding, end-of-line sequences). spec
• rust-analyzer, lib/line-index (LineIndex, WideEncoding). code · docs
• rustc, compiler/rustc_span/src/span_encoding.rs (Span layouts and rationale). code
• Andrew Gallant, memchr. code · docs
• Unicode Consortium, UAX #29: Unicode Text Segmentation. report