Fix #124: Treat :character offsets as UTF-16 code units

[mkcms]

https://microsoft.github.io/language-server-protocol/specification#text-documents

The spec says that :character offsets are based on a UTF-16
representation. Previously we were assuming that :character specifies
the number of characters.

• eglot.el (eglot--count-utf-16-code-units): New function.
  (eglot--pos-to-lsp-position):
  (eglot--lsp-position-to-point): Use it.

[MaskRay]

Rather than use UTF-16 unconditionally, you may consider hiding this under an option (I would even suggest using code points for performance consideration). Some other language clients don't UTF-8 (LanguageClient-neovim, lsp-mode) either and this isn't an issue in practice because code points in Supplementary Planes are rarely used. I dislike UTF-16 so much that I didn't even consider doing the conversion in cquery and now in ccls.

There is a bug tracking the conversion to code points and you may raise that topic again microsoft/language-server-protocol#376

[joaotavora]

Rather than use UTF-16 unconditionally, you may consider hiding this under an option

What potential problems could arise from using it unconditionally?

I would even suggest using code points for performance consideration

For the UTF-16-ignorant like me, what are code points?

[MaskRay]

A code point usually represents a single character (the closest concept is probably "grapheme cluster"). 𝛱 has 1 code point but requires 2 UTF-16 code units to encode, thus causing the incorrect computation of character

I find the time spent on forward-line is positively related to the distance. Converting between position and LSP Location is already slow, doing transcoding will make it even slower (I discovered this when optimizing semantic highlight). I understand that clangd conforms to LSP in this respect and you want make clients to do so, but I believe switching to code points is possible and this should not punish other language servers/clients using code points.

[mkcms]

@MaskRay

Supplementary Planes are rarely used

LSP can be used for things other than just programming. I didn't really benchmark this change, but maybe you're right and it will make eglot slower, although probably not by a large factor.

[MaskRay]

@mkcms although probably not by a large factor.

Yes if line/character -> position conversion is only done a few times. But in some scenarios (semantic highlight, codeLens), computation through (forward-line) exhibits noticeable overhead. I had strong feelings when I was optimizing the semantic highlight feature. There are many clang .cpp files with 5000+ lines of code. liblmdb/mdb.c has more than 10000+.

Many language servers may deliberately choose not to conform to LSP for the UTF-16 transcoding. It seems palantir/python-language-server diverges from LSP, too.

Please provide the UTF-16 transcoding under a defvar-local (or whatever) toggle.

[mkcms]

@MaskRay

Please provide the UTF-16 transcoding under a defvar-local (or whatever) toggle.

I pushed a commit which adds a defvar which controls whether UTF-16 encoding is used.

[joaotavora]

I have to say @mkcms, I don't like this at all. It's:

• very bad from a readability point of view;
• bad in performance, more than probably;
• questionable in benefit (though I have understood your Issues when buffer contains special characters #124 bug report, and it is indeed a bug)

I feel some effort should be made to use "normal" emacs abstractions. I'll have a better look at the problem, until then, let's shelve this.

[joaotavora]

"If non-nil, calculate positions in full compliance with standard"

[joaotavora]

You probably meant: "wider than one".

[joaotavora]

I'd name this "eglot--lsp-chars-between"

[joaotavora]

You don't need so many newlines, it makes reading very strenuous, for me at least.

[joaotavora]

This whole section is extremely hacky, counting character lengths one by one, it's like you're reimplementing Emacs's coding systems.

[joaotavora]

@mkcms, have a look at 1999245 and tell me what you think. There's a very simple test, which we could overhaul with many difficult situations.

It'd be interesting to compare the performance of your approach and mine's (which I think uses more of Emacs's built-in machinery to do what you do by hand, and is therefore more readable).

Interestingly, Emacs's bufferpos-to-filepos can return exact or approximate char positions, which supposedly affects performance. I'm using exact but we could use something else.

[joaotavora]

Actually look here (3bbc937), I bungled that other commit quite badly with some stuff that wasn't supposed to go in.

[mkcms]

@joaotavora Thanks for the review.

• bad in performance, more than probably;

Yes, of course it will slow down the position conversion functions. What I meant before was overall performance that affects the user. My reasoning was that converting Emacs to LSP positions only takes a fraction of the overall time (e.g. when applying workspace edits, I/O and buffer modifications take the most time). Obviously, I haven't really benchmarked, so it's possible that my change would slow down Eglot by a large factor in other use cases. I only tested this change by doing regular coding work and I haven't noticed any slowdown.

• questionable in benefit (though I have understood your Issues when buffer contains special characters #124 bug report, and it is indeed a bug)

I agree that 99% of the time, this is just redundant computation. Actually this issue only happened to me exactly once, and it wasn't even serious.

---

Actually look here (3bbc937),

I also looked at the bufferpos/filepos functions before. I didn't use them because they always calculate the position from beginning of buffer. This seems like significant overhead, although I have no idea how they're implemented. Maybe they're heavily optimized.

---

Maybe instead of unconditionally converting the positions, perhaps we could add a eglot-position-conversion-function (or just agree to keep eglot--lsp-position-to-point and eglot--pos-to-lsp-position always backwards-compatible) so that users who experience this problem can override those functions, and add a note in README.

[joaotavora]

My reasoning was that converting Emacs to LSP positions only takes a fraction of the overall time

Depends. Consider a very big file with a very large list of diagnostics. It might take a much larger fraction there.

I agree that 99% of the time, this is just redundant computation. Actually this issue only happened to me exactly once, and it wasn't even serious.

Actually, it doesn't just happen with crazy characters like the one you had, my name João is also a candidade because of the ã. But I don't write my name often in code, only in the header at the most.
I would say 90%.

I also looked at the bufferpos/filepos functions before. I didn't use them because they always calculate the position from beginning of buffer.

This is true, but the buffer we're talking about doesn't need to be the buffer visiting the file, but a temporary buffer whose only contents are the line you're trying to discover the column in (EDIT: and this is what my version does).

This seems like significant overhead, although I have no idea how they're implemented. Maybe they're heavily optimized.

Most likely. They also offer this exactness/performance trade-off

Maybe instead of unconditionally converting the positions, perhaps we could add a eglot-position-conversion-function

This is a good idea.

[mkcms]

This is a good idea.

Alright, I will do this.

---

I also did some benchmarks, comparing execution times of eglot--lsp-position-to-point on master, this branch and scratch/fix-124-idea.
The test case is converting a couple of thousand lsp positions to emacs points in a 1000 line file with some wide characters.
Here are the results:

$ ./run-benchmark.sh 
master 1.4869308209999998s
fix/issue-124 1.803970126s
scratch/fix-124-idea 7.018219207s

I've also managed to optimize my solution to get these times:

$ ./run-benchmark.sh 
master 1.389679567s
fix/issue-124 1.4014020470000002s
scratch/fix-124-idea 6.454922788999999s

The benchmark suite: benchmark.zip

[joaotavora]

@mkcms, I'll have a look at your benchmark but in the meantime, to avoid confusion of mental translations I've pushed two branches scratch/fix-124-joaotavora and scratch/fix-125-mkcms to hold the two approaches. I'll push tweaks to the first while you push to the second, and in the end we can decide which is the best.

[joaotavora]

@mkcms your benchmark idea is very good, but I don't understand insert-file-contents-literally. Shouldn't we be opening the test file normally, with its utf-8 encoding?

Also, positions.el as returned from an hypothetical UTF-16-counting LSP server doesn't point to the positions of the multibyte characters in the generated text.txt file. Please verify on your side.

[mkcms]

I don't understand insert-file-contents-literally. Shouldn't we be opening the test file normally, with its utf-8 encoding?

Right, I missed that.

Attached is a new benchmark suite which will also test the number of times each solution was incorrect.
Here is my output for now:

$ ./run-benchmark.sh 
master 1.687929406s mismatches: 16960
scratch/fix-124-mkcms 2.620455026s mismatches: 0
scratch/fix-124-joaotavora 15.336856984s mismatches: 0

With optimization:

$ ./run-benchmark.sh 
master 1.655803003s mismatches: 17320
scratch/fix-124-mkcms 1.7465138349999998s mismatches: 0
scratch/fix-124-joaotavora 13.732144245s mismatches: 0

The optimization is this:
Instead of iterating from the beginning of line, first forward-char the same number of chars as :character, then iterate backwards until the number of code units between point-at-bol and point equals :character.

---

benchmark.zip

[joaotavora]

@mkcms, so I basically did the same as you and rewrote the benchmark to verify correctness.

Indeed the Emacs function bufferpos-to-filepos isn't suitable at all for the job. I though they were some kind of highly optimized C function but they're just plain Emacs Lisp that has to cater to multiple coding systems and therefore really really slow. So I came up with this solution, which is basically yours but a somes lines shorter

(defun eglot--lsp-char-to-column (lsp-charpos)
  "Helper for `eglot--lsp-position-to-point' with LSP-CHARPOS."
  (save-excursion
    (goto-char (line-beginning-position))
    (cl-loop
     with i = 0 while (< i (* 2 lsp-charpos))
     do (cl-incf i (- (length (encode-coding-region (point) (1+ (point))
                                                    'utf-16 t))
                      2))
     sum 1 do (forward-char))))

I pushed it to scratch/fix-124-joaotavora. It's a 50% slowdown, but I think we can take it.

master 1.023066238s total time, 8415 misses
scratch/fix-124-joaotavora 1.4330311040000001s total time, 0 misses
scratch/fix-124-mkcms 1.451512525s total time, 0 misses

I'm using your unoptimized version, I think. What is the optimization you had? Can it be applied to my version?

[joaotavora]

And some followup questions: won't this break those servers that are not following the standard and returning just the actual column number when confronted with complex utf-something characters? Are those the majority or the minority?

[mkcms]

What is the optimization you had? Can it be applied to my version?

Yes, it can be applied from what I can see.
Consider this line:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyy𐐀x𐐀zyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy

To get to :character 35 (33rd column), currently we're iterating from beginning of line one by one until we get there (33 iterations).
Instead of doing that, we can simply forward 35 characters at once (this will put us on 35th column, 37th code unit), then simply iterate backward until the number of code units between point-at-bol and point is equal to 35. This will take only two iterations.
We can always do this because skipping :character chars forward will always put as exactly at desired column or somewhere after it.

won't this break those servers that are not following the standard and returning just the actual column number when confronted with complex utf-something characters? Are those the majority or the minority?

Good question. I will test some servers and report the stats here.

[joaotavora]

Yes, it can be applied from what I can see.

Nice. I thought of that just now, too. It's a little faster indeed

(defun eglot--lsp-char-to-column (lsp-charpos)
  "Helper for `eglot--lsp-position-to-point' with LSP-CHARPOS."
  (save-excursion
    (let ((lbp (line-beginning-position)))
      (move-to-column lsp-charpos)
      (cl-loop
       while (< lsp-charpos
                (/ (- (length (encode-coding-region lbp (point)
                                                    'utf-16 t))
                      2)
                   2))
       do (backward-char)
       finally (cl-return (current-column))))))

But it might take more than two iterations if there are more multibyte chars before the target column.

[joaotavora]

Continuing this fun project, I've managed to optimized it a tad further by using a binary search:

(defun eglot--lsp-char-to-column (lsp-charpos)
  "Helper for `eglot--lsp-position-to-point' with LSP-CHARPOS."
  (save-excursion
    (cl-loop
     initially (move-to-column lsp-charpos)
     with lbp = (line-beginning-position)
     for diff = (- lsp-charpos
                   (/ (- (length (encode-coding-region lbp (point)
                                                       'utf-16 t))
                         2)
                      2))
     until (zerop diff)
     for offset = (max 1 (abs (/ diff 2)))
     do (if (> diff 0) (forward-char offset) (backward-char offset))
     finally
     (cl-return (current-column)))))

More seriously though, this breaks at least pyls, so I'm thinking of introducing an eglot--move-to-column function but leave it set to move-to-column.

[mkcms]

@joaotavora Don't we need to also have a variable for eglot--point-to-lsp-position?

[MaskRay]

Nice:) This is interpolation search.

forward-char works on negative argment. Can

for offset = (max 1 (abs (/ diff 2)))
     do (if (> diff 0) (forward-char offset) (backward-char offset))

be simplified to something like (forward-char (if (> diff 0) (/ (1+ diff) 2) (/ (1- diff) 2)))

[joaotavora]

be simplified to something like (forward-char (if (> diff 0) (/ (1+ diff) 2) (/ (1- diff) 2)))

lol, not sure if that would be simplifying it. I was looking for a sign function though, and couldn't find it.

@joaotavora Don't we need to also have a variable for eglot--point-to-lsp-position?

I don't think so. Do we? Don't we just need an alternate way to move to the LSP column?

[joaotavora]

(forward-char (if (> diff 0) (/ (1+ diff) 2) (/ (1- diff) 2)))

Actually, it isn't a bad idea, especially if I change this to (forward-char (/ (if (> diff 0) (1+ diff) (1- diff)) 2)

[mkcms]

@joaotavora Don't we need to also have a variable for eglot--point-to-lsp-position?

I don't think so. Do we? Don't we just need an alternate way to move to the LSP column?

Yes, we do.
When I have a buffer with the same contents as in #124 and I manually fix the error by changing circle_are to circle_area, clangd gives me this diagnostic on the circle_area symbol:

Use of undeclared identifier 'circle_arae'; did you mean 'circle_area'?

[joaotavora]

When I have a buffer with the same contents as in #124 and I manually fix the error by changing circle_are to circle_area, clangd gives me this diagnostic on the circle_area symbol:

Curious, but I don't understand what is happening, in what situation did eglot move to the wrong position?

[joaotavora]

@joaotavora Don't we need to also have a variable for eglot--point-to-lsp-position?

Never mind. Of course we do: we need to translate back to the format that clangd is expecting.

So I'd make a second variable indeed that is commonly set to current-column but could be set to eglot-lsp-abiding-column, which we have to write.

Then we can take care of the problem of setting both variables at once, if it is indeed a problem.

[joaotavora]

@mkcms have a look at my latest commit. Curiously, the problem in #124 hasn't gone away, at least in clangd-6.0. It's like my clang is reporting for utf-8, so the function that corrects in my case is

(defun eglot-move-to-lsp-abiding-column (column)
  "Move to COLUMN abiding by the LSP spec."
  (cl-loop
   initially (move-to-column column)
   with lbp = (line-beginning-position)
   for diff = (- column
                 (/ (- (length (encode-coding-region lbp (point) 'utf-8 t))
                       0)
                    1))
   until (zerop diff)
   do (forward-char (/ (if (> diff 0) (1+ diff) (1- diff)) 2))))

What clangd version are you using?

[mkcms]

@joaotavora Thanks, that seems to fix the issue.
I'm building newest clangd from source.

clangd version 8.0.0 (https://git.llvm.org/git/clang 551269913315bd099dbf45e2d37caf7bcfc57e74) (https://git.llvm.org/git/llvm 57aa4fc38b0878c6328ab565a128bb79805e29bd)

EDIT: If clangd-6.0 is older than April 27 2018, then it won't use UTF-16 code units:
llvm-mirror/clang-tools-extra@aa3548e

[joaotavora]

@mkcms, thanks for the tests.

To solve the problem of automatically setting the variables for clangd or other servers, I think the next step would be to introduce a new variable eglot-server-bindings, an association between server and variable bindings. The bindings would be set buffer locally in buffers managed by a server, and reset when the server stops managing it. But one has to think first about how to match a server to a group of bindings. As far as I see there is no standard way for a server to report its identity/version, so we would probably have to regexp-match the server executable (which would fail for TCP connections).

Also, in retrospect, I think my original review of your PR was too harsh :-) I wasn't reading it correctly and had kind of a knee-jerk reaction.

[mkcms]

I think the next step would be to introduce a new variable eglot-server-bindings, an association between server and variable bindings.

That's a cool idea, I opened #152 for it.

Also, in retrospect, I think my original review of your PR was too harsh

No problem, I appreciate how much you pay attention to code quality. I'm not a professional lisper myself, so hopefully your reviews will make me a better emacs hacker.

[astoff]

@MaskRay Since you participated in this discussion and in the definition of positionEncodings capability of LSP, I would like to point out this thread pertaining to the latter in emacs-bugs: https://yhetil.org/emacs-bugs/87a614g628.fsf@gmail.com/

Also, do you know about any servers that already implement positionEncodings?