Repository: openlawlibrary/pygls (python)

Issue:
Make sure you handle UTF-16 character offsets
One of the major downsides of pyls is that it craps out at UTF-16 offsets.

I just want to make sure that this library doesn't fail in the same way. Just to be clear, the LSP spec says:

> A position inside a document (see Position definition below) is expressed as a zero-based line and character offset. **The offsets are based on a UTF-16 string representation**. So a string of the form a𐐀b the character offset of the character a is 0, the character offset of 𐐀 is 1 and the character offset of b is 3 since 𐐀 is represented using two code units in UTF-16.

Since python internally works with UTF-32 and indexes strings with UTF-32, you have to be very careful in translating LSP-ranges to pygls ranges. It is not as simple as converting a (row, col) to a character offset.

If you already accounted for this, then you may close this issue.

Pull request description:
Fix utf-16 to utf-32 character offsets.
Closes #116.

Python uses utf-32 for strings, but the language-server-protocol uses utf-16 to encode strings. Hence higher level unicode code points are represented by two utf-16 code units. Thus the `position.character` needs to be adjusted in case of the presence of such unicode characters.

see: https://github.com/openlawlibrary/pygls/issues/116, https://github.com/microsoft/language-server-protocol/issues/376

This PR therefore introduces two methods to the `Documents` class to handle conversion between utf-16 and utf-32 column offsets for general use.

The new methods are used in the `offset_at_position()`, `word_at_position()` and `_apply_incremental_change()` methods.

Notes:

1. The conversion needs information about the line's content. Hence it feels natural to add the functionality to the Document.

2. This change is unfortunately not transparent. Means a real server needs to proxy all positions through

   a) `Document.rowcol_to_position()` in order to create a `Position` with correct utf-16 code units to be sent to the client.

   b) `Document.position_to_rowcol()` to receive a corrected (row, col) tuple.

3. The methods convert between tuple <-> Position to make the difference clear and because row and column are needed explicitly in the current use cases anyway. A new type could be invented but it would need to make the difference obvious.

5. The `''.join(..)` statement in `offset_at_position()` is replaced as creating a maybe huge string just to count characters while the length of each line is a stored attribute seems too expensive.

## Description (e.g. "Related to ...", etc.)

_Please replace this description with a concise description of this Pull Request._

## Code review checklist (for code reviewer to complete)

- [ ] Pull request represents a single change (i.e. not fixing disparate/unrelated things in a single PR)
- [ ] Title summarizes what is changing
- [ ] Commit messages are meaningful (see [this][commit messages] for details)
- [ ] Tests have been included and/or updated, as appropriate
- [ ] Docstrings have been included and/or updated, as appropriate
- [ ] Standalone docs have been updated accordingly
- [ ] [CONTRIBUTORS.md][contributors] was updated, as appropriate
- [ ] Changelog has been updated, as needed (see [CHANGELOG.md][changelog])

[changelog]: https://github.com/openlawlibrary/pygls/blob/master/CHANGELOG.md
[commit messages]: https://chris.beams.io/posts/git-commit/
[contributors]: https://github.com/openlawlibrary/pygls/blob/master/CONTRIBUTORS.md


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 4ce9804..bae5965 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,12 +7,17 @@ and this project adheres to [Semantic Versioning][semver].
 
 ## [Unreleased]
 
+### Added
+
+- Functions to convert positions from and to utf-16 code units ([#117])
+
 ### Changed
 
 - Exit server normally when `ctrl+c` is pressed in command shell.
 - Optimize json-rpc message serialization ([#120])
 
 [#120]: https://github.com/openlawlibrary/pygls/pull/120
+[#117]: https://github.com/openlawlibrary/pygls/pull/117
 
 ## [0.9.0] - 04/20/2020
 
diff --git a/pygls/types.py b/pygls/types.py
index 78f0ac5..ead7468 100644
--- a/pygls/types.py
+++ b/pygls/types.py
@@ -839,6 +839,12 @@ class Position:
     def __ne__(self, other):
         return not self.__eq__(other)
 
+    def __hash__(self):
+        return hash((self.line, self.character))
+
+    def __iter__(self):
+        return iter((self.line, self.character))
+
     def __repr__(self):
         return '{}:{}'.format(self.line, self.character)
 
@@ -865,6 +871,12 @@ class Range:
             and self.start == other.start
             and self.end == other.end)
 
+    def __hash__(self):
+        return hash((self.start, self.end))
+
+    def __iter__(self):
+        return iter((self.start, self.end))
+
     def __repr__(self):
         return '{}-{}'.format(self.start, self.end)
 
diff --git a/pygls/workspace.py b/pygls/workspace.py
index 105e9bd..b608295 100644
--- a/pygls/workspace.py
+++ b/pygls/workspace.py
@@ -22,8 +22,8 @@ import os
 import re
 from typing import List
 
-from .types import (NumType, Position, TextDocumentContentChangeEvent, TextDocumentItem,
-                    TextDocumentSyncKind, WorkspaceFolder)
+from .types import (NumType, Position, Range, TextDocumentContentChangeEvent,
+                    TextDocumentItem, TextDocumentSyncKind, WorkspaceFolder)
 from .uris import to_fs_path, uri_scheme
 
 # TODO: this is not the best e.g. we capture numbers
@@ -33,6 +33,128 @@ RE_START_WORD = re.compile('[A-Za-z_0-9]*$')
 log = logging.getLogger(__name__)
 
 
+def utf16_unit_offset(chars: str):
+    """Calculate the number of characters which need two utf-16 code units.
+
+    Arguments:
+        chars (str): The string to count occurrences of utf-16 code units for.
+    """
+    return sum(ord(ch) > 0xFFFF for ch in chars)
+
+
+def utf16_num_units(chars: str):
+    """Calculate the length of `str` in utf-16 code units.
+
+    Arguments:
+        chars (str): The string to return the length in utf-16 code units for.
+    """
+    return len(chars) + utf16_unit_offset(chars)
+
+
+def position_from_utf16(lines: List[str], position: Position) -> Position:
+    """Convert the position.character from utf-16 code units to utf-32.
+
+    A python application can't use the character member of `Position`
+    directly as per specification it is represented as a zero-based line and
+    character offset based on a UTF-16 string representation.
+
+    All characters whose code point exceeds the Basic Multilingual Plane are
+    represented by 2 UTF-16 code units.
+
+    The offset of the closing quotation mark in x="😋" is
+    - 5 in UTF-16 representation
+    - 4 in UTF-32 representation
+
+    see: https://github.com/microsoft/language-server-protocol/issues/376
+
+    Arguments:
+        lines (list):
+            The content of the document which the position refers to.
+        position (Position):
+            The line and character offset in utf-16 code units.
+
+    Returns:
+        The position with `character` being converted to utf-32 code units.
+    """
+    try:
+        return Position(
+            position.line,
+            position.character - utf16_unit_offset(lines[position.line][:position.character])
+        )
+    except IndexError:
+        return Position(len(lines), 0)
+
+
+def position_to_utf16(lines: List[str], position: Position) -> Position:
+    """Convert the position.character from utf-32 to utf-16 code units.
+
+    A python application can't use the character member of `Position`
+    directly as per specification it is represented as a zero-based line and
+    character offset based on a UTF-16 string representation.
+
+    All characters whose code point exceeds the Basic Multilingual Plane are
+    represented by 2 UTF-16 code units.
+
+    The offset of the closing quotation mark in x="😋" is
+    - 5 in UTF-16 representation
+    - 4 in UTF-32 representation
+
+    see: https://github.com/microsoft/language-server-protocol/issues/376
+
+    Arguments:
+        lines (list):
+            The content of the document which the position refers to.
+        position (Position):
+            The line and character offset in utf-32 code units.
+
+    Returns:
+        The position with `character` being converted to utf-16 code units.
+    """
+    try:
+        return Position(
+            position.line,
+            position.character + utf16_unit_offset(lines[position.line][:position.character])
+        )
+    except IndexError:
+        return Position(len(lines), 0)
+
+
+def range_from_utf16(lines: List[str], range: Range) -> Range:
+    """Convert range.[start|end].character from utf-16 code units to utf-32.
+
+    Arguments:
+        lines (list):
+            The content of the document which the range refers to.
+        range (Range):
+            The line and character offset in utf-32 code units.
+
+    Returns:
+        The range with `character` offsets being converted to utf-16 code units.
+    """
+    return Range(
+        position_from_utf16(lines, range.start),
+        position_from_utf16(lines, range.end)
+    )
+
+
+def range_to_utf16(lines: List[str], range: Range) -> Range:
+    """Convert range.[start|end].character from utf-32 to utf-16 code units.
+
+    Arguments:
+        lines (list):
+            The content of the document which the range refers to.
+        range (Range):
+            The line and character offset in utf-16 code units.
+
+    Returns:
+        The range with `character` offsets being converted to utf-32 code units.
+    """
+    return Range(
+        position_to_utf16(lines, range.start),
+        position_to_utf16(lines, range.end)
+    )
+
+
 class Document(object):
 
     def __init__(self, uri, source=None, version=None, local=True,
@@ -54,16 +176,14 @@ class Document(object):
 
     def _apply_incremental_change(self, change: TextDocumentContentChangeEvent) -> None:
         """Apply an INCREMENTAL text change to the document"""
+        lines = self.lines
         text = change.text
         change_range = change.range
 
-        start_line = change_range.start.line
-        start_col = change_range.start.character
-        end_line = change_range.end.line
-        end_col = change_range.end.character
+        (start_line, start_col), (end_line, end_col) = range_from_utf16(lines, change_range)
 
-        # Check for an edit occuring at the very end of the file
-        if start_line == len(self.lines):
+        # Check for an edit occurring at the very end of the file
+        if start_line == len(lines):
             self._source = self.source + text
             return
 
@@ -72,7 +192,7 @@ class Document(object):
         # Iterate over the existing document until we hit the edit range,
         # at which point we write the new text, then loop until we hit
         # the end of the range and continue writing.
-        for i, line in enumerate(self.lines):
+        for i, line in enumerate(lines):
             if i < start_line:
                 new.write(line)
                 continue
@@ -151,8 +271,10 @@ class Document(object):
         return self.source.splitlines(True)
 
     def offset_at_position(self, position: Position) -> int:
-        """Return the byte-offset pointed at by the given position."""
-        return position.character + len(''.join(self.lines[:position.line]))
+        """Return the character offset pointed at by the given position."""
+        lines = self.lines
+        row, col = position_from_utf16(lines, position)
+        return col + sum(len(line) for line in lines[:row])
 
     @property
     def source(self) -> str:
@@ -165,14 +287,15 @@ class Document(object):
         """
         Get the word under the cursor returning the start and end positions.
         """
-        if position.line >= len(self.lines):
+        lines = self.lines
+        if position.line >= len(lines):
             return ''
 
-        line = self.lines[position.line]
-        i = position.character
+        row, col = position_from_utf16(lines, position)
+        line = lines[row]
         # Split word in two
-        start = line[:i]
-        end = line[i:]
+        start = line[:col]
+        end = line[col:]
 
         # Take end of start and start of end to find word
         # These are guaranteed to match, even if they match the empty string


Test patch:
diff --git a/tests/conftest.py b/tests/conftest.py
index 1ef4cc9..c3669a9 100644
--- a/tests/conftest.py
+++ b/tests/conftest.py
@@ -32,6 +32,7 @@ CALL_TIMEOUT = 2
 DOC = """document
 for
 testing
+with "😋" unicode.
 """
 DOC_URI = uris.from_fs_path(__file__)
 
diff --git a/tests/test_document.py b/tests/test_document.py
index 4c1666d..8fd93a4 100644
--- a/tests/test_document.py
+++ b/tests/test_document.py
@@ -18,7 +18,9 @@
 ############################################################################
 from pygls.types import (Position, Range, TextDocumentContentChangeEvent,
                          TextDocumentSyncKind)
-from pygls.workspace import Document
+from pygls.workspace import (
+    Document, position_from_utf16, position_to_utf16, range_from_utf16, range_to_utf16
+)
 
 from .conftest import DOC, DOC_URI
 
@@ -74,7 +76,7 @@ def test_document_line_edit():
 
 
 def test_document_lines(doc):
-    assert len(doc.lines) == 3
+    assert len(doc.lines) == 4
     assert doc.lines[0] == 'document\n'
 
 
@@ -120,12 +122,54 @@ def test_document_source_unicode():
     assert isinstance(document_mem.source, type(document_disk.source))
 
 
+def test_position_from_utf16():
+    assert position_from_utf16(['x="😋"'], Position(0, 3)) == Position(0, 3)
+    assert position_from_utf16(['x="😋"'], Position(0, 5)) == Position(0, 4)
+
+    position = Position(0, 5)
+    position_from_utf16(['x="😋"'], position)
+    assert position == Position(0, 5)
+
+
+def test_position_to_utf16():
+    assert position_to_utf16(['x="😋"'], Position(0, 3)) == Position(0, 3)
+    assert position_to_utf16(['x="😋"'], Position(0, 4)) == Position(0, 5)
+
+    position = Position(0, 4)
+    position_to_utf16(['x="😋"'], position)
+    assert position == Position(0, 4)
+
+
+def test_range_from_utf16():
+    assert range_from_utf16(
+        ['x="😋"'], Range(Position(0, 3), Position(0, 5))
+    ) == Range(Position(0, 3), Position(0, 4))
+
+    range = Range(Position(0, 3), Position(0, 5))
+    range_from_utf16(['x="😋"'], range)
+    assert range == Range(Position(0, 3), Position(0, 5))
+
+
+def test_range_to_utf16():
+    assert range_to_utf16(
+        ['x="😋"'], Range(Position(0, 3), Position(0, 4))
+    ) == Range(Position(0, 3), Position(0, 5))
+
+    range = Range(Position(0, 3), Position(0, 4))
+    range_to_utf16(['x="😋"'], range)
+    assert range == Range(Position(0, 3), Position(0, 4))
+
+
 def test_offset_at_position(doc):
     assert doc.offset_at_position(Position(0, 8)) == 8
     assert doc.offset_at_position(Position(1, 5)) == 14
     assert doc.offset_at_position(Position(2, 0)) == 13
     assert doc.offset_at_position(Position(2, 4)) == 17
-    assert doc.offset_at_position(Position(4, 0)) == 21
+    assert doc.offset_at_position(Position(3, 6)) == 27
+    assert doc.offset_at_position(Position(3, 7)) == 27
+    assert doc.offset_at_position(Position(3, 8)) == 28
+    assert doc.offset_at_position(Position(4, 0)) == 39
+    assert doc.offset_at_position(Position(5, 0)) == 39
 
 
 def test_word_at_position(doc):
@@ -136,4 +180,5 @@ def test_word_at_position(doc):
     assert doc.word_at_position(Position(0, 1000)) == 'document'
     assert doc.word_at_position(Position(1, 5)) == 'for'
     assert doc.word_at_position(Position(2, 0)) == 'testing'
+    assert doc.word_at_position(Position(3, 10)) == 'unicode'
     assert doc.word_at_position(Position(4, 0)) == ''