Repository: openlawlibrary/pygls

Issue:
position_from_utf16 in workspace.py may return incorrect result.
The following code that mimics the way position_from_utf16 calculates the result, demonstrates the issue:

```python
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)

s = '😋😋'

def position_from_utf16(line, pos):
    return pos - utf16_unit_offset(line[:pos])

print(position_from_utf16(s, 2))
```

The result is zero, but it should be one.

Although, this may not have a large real-world impact (you don't get many high-plane chars in python code), it would be nice to have a correct calculation.


Discussion:
pyscripter: Please see the comments in the code.   I would just use (skipping the comments):

```python
def position_from_utf16(lines: List[str], position: Position) -> Position:
    if position.line >= len(lines):
        # start of the line after last
        return Position(len(lines), 0)  # or return position

    line = lines[position.line]

    _utf32_len = len(line)
    _utf32_index = 0
    _utf16_index = 0
    while (_utf16_index < position.character) and (_utf32_index < _utf32_len):
        _current_char = line[line_index]
        is_double_width = is_char_beyond_multilingual_plane(_current_char)
        if (is_double_width):
            _utf16_index += 2
        else:
            _utf16_index += 1
        _utf32_index += 1

    position = Position(
        line=position.line,
        character=_utf32_index
    )
    return position

```
tombh: Thanks for the feedback and extra test cases, they're really useful. Before making these amends, can you have a look at Pygls' [`Document.offset_at_position()`](https://github.com/openlawlibrary/pygls/blob/2a052539aef0e5ada2c619ae7df9baae5e7f8939/tests/test_document.py#L250). It's the main reason I made those conditional guards at the beginning of the function. I don't know who uses `offset_at_position()`, or what it's for, but Pygls supports it, so we should probably continue to do so.
pyscripter: > I don't know who uses `offset_at_position()`

Well, some editors may internally store the actual text of a file instead of a list of lines like pygls does and they may wont to convert from a position to an offset to the string representation of the file.  Since offset_at_position does not account for line breaks, users of the function need to adjust for line breaks.

The function will work correctly if position_from_utf16 provides the correct result, so it should not be a concern.
tombh: Ok I've pushed some changes. I made the variables names a bit more verbose. I added a guard clause for when a queried `Position` goes over the length of the line. And I added all your tests cases.

How does it look to you?
tombh: I'm thinking of merging this as is...
pyscripter: _utf16_end_of_line = utf16_num_units(_line) - 1

This is definitely wrong.  See my comments above.
tombh: Did you miss my question here? https://github.com/openlawlibrary/pygls/pull/304#discussion_r1089369599
tombh: Just taking a small step back for a moment. This is surprisingly a lot more complicated than I first thought. We have 2 things going on here.

1. The first one, and the reason that this PR exists, is the `position_from_utf16` bug you identified in #302. And I think the PR here addresses that?
2. The second one is the tangentially associated `offset_at_position` tests that fail because of the fix for 1. (We have some comments on that in [a now stale commit](https://github.com/openlawlibrary/pygls/commit/3b36463bf1476e51758a04dfee2fc6024b388001).)

Copying your comments from point 2 here:
> But why include the control line end characters in lines?
> ...
> You also seem to assume that the control characters are always /n. This is not true on Windows or for the last line.

Very good questions. I had to look this up and you were indeed right to bring it up. If I'm interpreting it correctly the LSP spec says that that `\n` and `\r\n` should be considered and considered as the same length. [The relevant section is here](https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#textDocuments). And I've added a new test for that called `test_position_for_line_endings`.

To further complicate things, I also learnt from reading the spec that the position encodings can be negotiated by the client and server! See:
![image](https://github.com/openlawlibrary/pygls/assets/160835/b71888e1-1e13-4c60-af3c-cfa02357df09)
https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#clientCapabilities

It does say that it defaults to utf-16 positioning, which is what Pygls does already. So maybe we can just create an issue to acknowledge that Pygls doesn't currently support clients requesting specific position encodings.

tombh: I'm thinking of merging this then.
tombh: After 8 months, it's as ready as it'll ever be I think!

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 95ed61e..a1a037d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -15,6 +15,7 @@ and this project adheres to [Semantic Versioning][semver].
 
 ### Changed
 ### Fixed
+[#304]: https://github.com/openlawlibrary/pygls/issues/304
 
 - `pygls` no longer overrides the event loop for the current thread when given an explicit loop to use. ([#334])
 - Fixed `MethodTypeNotRegisteredError` when registering a `TEXT_DOCUMENT_DID_SAVE` feature with options. ([#338])
diff --git a/pygls/workspace.py b/pygls/workspace.py
index bfd5aa5..dad7343 100644
--- a/pygls/workspace.py
+++ b/pygls/workspace.py
@@ -37,13 +37,17 @@ RE_START_WORD = re.compile('[A-Za-z_0-9]*$')
 log = logging.getLogger(__name__)
 
 
+def is_char_beyond_multilingual_plane(char: str) -> bool:
+    return ord(char) > 0xFFFF
+
+
 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)
+    return sum(is_char_beyond_multilingual_plane(ch) for ch in chars)
 
 
 def utf16_num_units(chars: str):
@@ -59,7 +63,7 @@ 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
+    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
@@ -80,14 +84,44 @@ def position_from_utf16(lines: List[str], position: Position) -> Position:
     Returns:
         The position with `character` being converted to utf-32 code units.
     """
-    try:
-        return Position(
-            line=position.line,
-            character=position.character
-            - utf16_unit_offset(lines[position.line][:position.character])
+    if len(lines) == 0:
+        return Position(0, 0)
+    if position.line >= len(lines):
+        return Position(len(lines) - 1, utf16_num_units(lines[-1]))
+
+    _line = lines[position.line]
+    _line = _line.replace('\r\n', '\n')  # TODO: it's a bit of a hack
+    _utf16_len = utf16_num_units(_line)
+    _utf32_len = len(_line)
+
+    if _utf16_len == 0:
+        return Position(position.line, 0)
+
+    _utf16_end_of_line = utf16_num_units(_line)
+    if position.character > _utf16_end_of_line:
+        position.character = _utf16_end_of_line - 1
+
+    _utf16_index = 0
+    utf32_index = 0
+    while True:
+        _is_searching_queried_position = _utf16_index < position.character
+        _is_before_end_of_line = utf32_index < _utf32_len
+        _is_searching_for_position = (
+            _is_searching_queried_position and _is_before_end_of_line
         )
-    except IndexError:
-        return Position(line=len(lines), character=0)
+        if not _is_searching_for_position:
+            break
+
+        _current_char = _line[utf32_index]
+        _is_double_width = is_char_beyond_multilingual_plane(_current_char)
+        if _is_double_width:
+            _utf16_index += 2
+        else:
+            _utf16_index += 1
+        utf32_index += 1
+
+    position = Position(line=position.line, character=utf32_index)
+    return position
 
 
 def position_to_utf16(lines: List[str], position: Position) -> Position:
@@ -137,10 +171,11 @@ def range_from_utf16(lines: List[str], range: Range) -> Range:
     Returns:
         The range with `character` offsets being converted to utf-16 code units.
     """
-    return Range(
+    range_new = Range(
         start=position_from_utf16(lines, range.start),
         end=position_from_utf16(lines, range.end)
     )
+    return range_new
 
 
 def range_to_utf16(lines: List[str], range: Range) -> Range:
@@ -280,7 +315,7 @@ class Document(object):
         lines = self.lines
         pos = position_from_utf16(lines, position)
         row, col = pos.line, pos.character
-        return col + sum(len(line) for line in lines[:row])
+        return col + sum(utf16_num_units(line) for line in lines[:row])
 
     @property
     def source(self) -> str:


Test patch:
diff --git a/tests/test_document.py b/tests/test_document.py
index 5c3c36b..8b21ac2 100644
--- a/tests/test_document.py
+++ b/tests/test_document.py
@@ -220,10 +220,11 @@ def test_range_from_utf16():
     range = Range(
         start=Position(line=0, character=3), end=Position(line=0, character=5)
     )
-    range_from_utf16(['x="😋"'], range)
-    assert range == Range(
-        start=Position(line=0, character=3), end=Position(line=0, character=5)
+    actual = range_from_utf16(['x="😋😋"'], range)
+    expected = Range(
+        start=Position(line=0, character=3), end=Position(line=0, character=4)
     )
+    assert actual == expected
 
 
 def test_range_to_utf16():
@@ -239,23 +240,40 @@ def test_range_to_utf16():
     range = Range(
         start=Position(line=0, character=3), end=Position(line=0, character=4)
     )
-    range_to_utf16(['x="😋"'], range)
-    assert range == Range(
-        start=Position(line=0, character=3), end=Position(line=0, character=4)
+    actual = range_to_utf16(['x="😋😋"'], range)
+    expected = Range(
+        start=Position(line=0, character=3), end=Position(line=0, character=5)
     )
+    assert actual == expected
 
 
 def test_offset_at_position(doc):
     assert doc.offset_at_position(Position(line=0, character=8)) == 8
-    assert doc.offset_at_position(Position(line=1, character=5)) == 14
+    assert doc.offset_at_position(Position(line=1, character=5)) == 12
     assert doc.offset_at_position(Position(line=2, character=0)) == 13
     assert doc.offset_at_position(Position(line=2, character=4)) == 17
     assert doc.offset_at_position(Position(line=3, character=6)) == 27
-    assert doc.offset_at_position(Position(line=3, character=7)) == 27
+    assert doc.offset_at_position(Position(line=3, character=7)) == 28
     assert doc.offset_at_position(Position(line=3, character=8)) == 28
-    assert doc.offset_at_position(Position(line=4, character=0)) == 39
-    assert doc.offset_at_position(Position(line=5, character=0)) == 39
-
+    assert doc.offset_at_position(Position(line=4, character=0)) == 40
+    assert doc.offset_at_position(Position(line=5, character=0)) == 40
+
+def test_utf16_to_utf32_position_cast(doc):
+    lines = ['', '😋😋', '']
+    assert position_from_utf16(lines, Position(line=0, character=0)) == Position(line=0, character=0)
+    assert position_from_utf16(lines, Position(line=0, character=1)) == Position(line=0, character=0)
+    assert position_from_utf16(lines, Position(line=1, character=0)) == Position(line=1, character=0)
+    assert position_from_utf16(lines, Position(line=1, character=2)) == Position(line=1, character=1)
+    assert position_from_utf16(lines, Position(line=1, character=3)) == Position(line=1, character=2)
+    assert position_from_utf16(lines, Position(line=1, character=4)) == Position(line=1, character=2)
+    assert position_from_utf16(lines, Position(line=1, character=100)) == Position(line=1, character=2)
+    assert position_from_utf16(lines, Position(line=3, character=0)) == Position(line=2, character=0)
+    assert position_from_utf16(lines, Position(line=4, character=10)) == Position(line=2, character=0)
+
+def test_position_for_line_endings(doc):
+    lines = ['x\r\n', 'y\n']
+    assert position_from_utf16(lines, Position(line=0, character=10)) == Position(line=0, character=1)
+    assert position_from_utf16(lines, Position(line=1, character=10)) == Position(line=1, character=1)
 
 def test_word_at_position(doc):
     """