fix empty cell representation

[jerch]

Currently an empty cell in the buffer is represented by a single white space, which leads to several issues for any functionality operating on the string representations. At least affected by this are:

• selection manager
• linkifier
• search addon
• prolly copy & paste (not tested)
• reflow resize, once we support this

Most of these rely on Buffer.translateBufferLineToString, that tries to deal with empty cells with the trimRight flag. Still there are circumstances where it cannot be decided at buffer level, how to create the correct string represenation, see #791 (comment).
Some workarounds are in place that try to fix those wrongly gathered string data by peeking again into the buffer, others will simply break at the edge cases (esp. the last right border cell thing is really nasty).

To get a more uniform handling of empty cells without the need of quirky patches here and there I suggest to define an empty cell to be a value that cannot be part of buffer string by normal means - any of the control chars would do (since the input handler will filter/trigger actions for control chars those will not end up as cell content values in the buffer). Imho the "hottest" candidate is the null byte '\x00' for several reasons:

• a 0 value kinda implies there is nothing
• easy translation with upcoming content pointer (where integer value stands for the UTF32 value, ergo 0 translates to '\u0000')

Why not simply use an empty string or null for an empty cell? Imho this would complicate things even further, since empty cells between others would "collapse" in a JS string while a placeholder can preserve the cell padding (There is another reason - we have to cover a third state and use this for cells after fullwidth chars, that would return an empty string). Imagine this input:

• string 'ab'
• cursor move one right
• string 'c'
• cursor move one right
• string ' ' (one whitespace)

leads to these buffer states:

current
['a', 'b', ' ', 'd', ' ', ' ', ' ']          ==> 'ab d   ' // trim would cut input whitespace
vs. ''
['a', 'b', '', 'd', '', ' ', '']             ==> 'abd '    // collapsed, padding broken
vs. '\x00'
['a', 'b', '\x00', 'd', '\x00', ' ', '\x00'] ==> 'ab\x00d\x00 \x00'

The third string resembles the buffer state better than the others. The right border problem now can be solved by simply trimming '\x00' which correctly leads to

'ab\x00d\x00 '

In a last step the placeholder could be replaced by whatever is needed for further processing (most likely with whitespace).

Up for discussion. There might be other representation tricks to leverage fast built in string methods with the fullwidth chars too. Also it might have a negative impact on the renderer speed due to an additional check against the placeholder.

cc: @Tyriar, @mofux, @bgw

[jerch]

Marked this as bug since it is faulty behavior as it is atm and already has one bug report #1286.

[Tyriar]

I don't think we should have a "null cell" character like this because of the fact that the cursor can move to an arbitrary column and enter data there, if all the cells were the null cell then they would need to be changed, leading to an O(n) operation (n=line length).

I wonder if we could instead imply trimRight in most cases by whether the line has isWrapped?

[jerch]

I wonder if we could instead imply trimRight in most cases by whether the line has isWrapped?

This will not cover all cases, imagine a terminal with 6 cols width and the input of several fullwidth chars with whitespace, e.g. input '￥￥ ￥' (one whitespace in between).

This leads to

['￥', '', '￥', '', ' ', ' ']
['￥', ' ', ' ', ' ', ' ', ' ']

To trim or not to trim - both leads to the wrong string version, the correct behavior would remove just one whitespace at the end of the first row. But there is no way to tell from the buffer state alone since it is equal to the input of '￥￥ ￥' (with 2 whitespaces).

The additional cost for an extra null cell character would be a check against this placeholder in the renderer or for any functionality, that operates directly on the string representation, an additional s.replace(/\x00/g, ' '), yeah.

[Tyriar]

@jerch So that example is an extreme edge case which we could handle specifically with some null character, this would be preferable imo that to say all cells are some null character that need to be changes to a space. So this instead:

['￥', '', '￥', '', ' ', \0]
['￥', ' ', ' ', ' ', ' ', ' ']

Where the first line is wrapped because there's only one character available.

[egmontkob]

Someone not knowing anything about xterm.js's internals chiming in:

When the output is "ab" followed by cursor right movements followed by "c" (or "d", the opening post is inconsistent here, nevermind), the desired behavior for all kinds of operations like copy-n-paste, autolocating URLs, searching etc. are to treat it as "ab[spaces]c" and not "abc", correct? That is, those "unused" cells have to be treated as spaces. This kind of output is easily possible with screen drawing libraries like ncurses which don't make a difference between spaces and unused cells.

Another typical example is when the output is "ab[tab]c". Most terminal emulators (not sure about xterm.js) treat TAB as a cursor moving operation only, preserving the characters and their attributes that it skips over. Again, for copy-pasting and such, you wish to get "ab[spaces]c", or even better "ab[tab]c" if you have some extra special magic to preserve tabs, but definitely not "abc".

With this in mind, if we're on the same track so far, can you think of any example where a line would contain an "unused" ('\x00', or whatever you pick) cell followed by a "used" one? We in VTE cannot. If you agree, probably the cleanest approach is to start with a new per-row variable containing the number of used cells (aka the offset where the unused ones begin). This can be maintained in O(1).

With the help of this variable, you may on may not still put spaces in the used part and 0's in the unused. If you want to, you can probably do it in O(1) average time given the average use of the terminal, just adjust the cells between the old and new value of this variable. O(n) would be the worst case, I wouldn't worry too much about it. Or you can maybe even have spaces everywhere and keep this operation O(1) all the time.

(Probably VTE isn't ideal here either. We do have this per-row "used length" variable, but we also tend to have spaces in used cells and '\x00's in unused ones. It might even be more messy than this. I'm not that super familiar with this part of our code. And on a side note, "unused" cells still have their background color tracked.)

I wonder if we could instead imply trimRight in most cases by whether the line has isWrapped?

isWrapped (assuming it is what I believe it is :)) should be kept separate from whether or not there are trailing unused cells in a line, these two are orthogonal. All 4 possibilities are (or should be) possible. 3 of them are trivial. A line can have just a few characters (after which unused cells remain) and then an explicit newline. It can have exactly as many characters as the width (no unused cells) and then an explicit newline. Or it can overflow to the next line (no unused cells, isWrapped).

The 4th, nontrivial case, assuming 80 columns: print 79 English letters followed by a CJK. There's no room to place it at the end of the line, hence an unused cell remains there, but the line isWrapped to the next one, beginning with this CJK (is this xterm.js's behavior?). That empty cell should be ignored for copy-pasting, searching etc. actions, and possibly re-filled (and similarly unused fields appearing newly) once you support reflow on resize.

[jerch]

@egmontkob yeah already thought about maintaining the current used width of a line as a separate line attribute. This would give the "trim border" for free during reading the buffer content, but it will also put some burden on the input side (writes and cursor jumps). From my usual "get the freaking data as fast as possible into the buffer"-view I still favour the explicit null char (it moves the burden to the output side - not my business 😄). Well I guess we have to find out the hard way...

About translating TAB back into '\t' - eww I really dont like that idea. I am not against doing this, its just I suspect it to need complicated heuristics to get the job halfway correctly done. What about the jumped over cell content? The tabstop width? Curses apps that like to use the terminal as canvas? Oh right we could read ICANON + alt buffer usage + guess the app to patch all the ifs and elses at runtime...
Whoever feels ready to get the hands dirty - go for it, but dont blame me because appXY does some weird stuff with tabs and the copy&paste stuff is broken again. Just my 2 cents 😸

With this in mind, if we're on the same track so far, can you think of any example where a line would contain an "unused" ('\x00', or whatever you pick) cell followed by a "used" one? We in VTE cannot.

Well my proposal would nullify all cells before anything got written to it, therefore any cursor jump over cells would keep them as "never written to it", even in the middle of the line. For our current canvas renderer this is not even a problem (it would just jump to next cell or line), the DOM renderer and all other features, that work JS string representation would need the extra replace after trimming to get the closest string representation, e.g. trimmed_line.replace(/<placeholder>/g, ' ').

[egmontkob]

From my usual "get the freaking data as fast as possible into the buffer"-view I still favour the explicit null char (it moves the burden to the output side - not my business smile). Well I guess we have to find out the hard way...

Well, this is obviously another possible way to go. On the output side chop off the trailing unused cells, and then convert the remaining unused ones to spaces.

I have to admit I was lost around the ￥ stuff, I don't know how you denote the second cell of a CJK, but it seemed to somewhat conflict with your new idea, and sentences like:

To trim or not to trim - both leads to the wrong string version, the correct behavior would remove just one whitespace at the end of the first row.

are truly scary, I hope you'll find a cleaner solution here. (Or I just don't understand it and you know it's not scary :))

[tab copy-pasting] I suspect it to need complicated heuristics to get the job halfway correctly done.

That's indeed true :) But let's keep it for a separate discussion, if at all.

[jerch]

@egmontkob
Ah well our current cell/line model works like this:

• a line consists of several cells
• any halfwidth char takes a single cell
• a cell contains the string data (either a single char or combining or surrogate) + text attrs + wcwidth
• if wraparound-mode is enabled and max cols is reached, the line is marked as wrapped and the next chars go into the next line

A fullwidth chars simply takes 2 cells, the first containing the actual char, a width of 2 and the second one being nullified (no content, no width). The right border is where it gets interesting - we allow a fullwidth char to wrap early, if it is at the last possible cell in wraparound-mode leaving the last cell untouched. And thats where the trim method struggles atm - this last cell looks the same at buffer level for early wraparound and a input whitespace at the last cell. Imho thats a bug in our current buffer representation, we lost the information about the source of that last space char.
For more remarks about the possible cell states see #791 (comment).

[egmontkob]

Thanks for the info!

It's essentially pretty similar to VTE. Probably one notable difference is that for the second cell of a CJK we do explicitly store that it's a "fragment" as we call it, this might (or might not) make certain operations simpler than just treating it identical to an unused cell.

And thats where the trim method struggles atm - this last cell looks the same at buffer level for early wraparound and a input whitespace at the last cell.

I see. An interesting, relevant question that occurred to me: what if there's already a nonempty cell (an actual letter) there at the last position?

xterm, vte, konsole and kitty leave that cell there in the last column. pterm (putty) wipes out that cell, making it an empty one. I guess I prefer pterm's behavior here.

[jerch]

I see. An interesting, relevant question that occurred to me: what if there's already a nonempty cell (an actual letter) there at the last position?

Its not touched at all, so any content there would stay. The corresponding code is here

xterm.js/src/InputHandler.ts

Line 406 in 69a6c04

if (buffer.x + chWidth - 1 >= cols) {

Edit: Thinking about it, I'd prefer pterm's behavior as well, the other seems like a bug to me. Thanks for pointing me to this 👍

This whole method is the "hot input loop" that gets called from the parser for any printable chars and takes most of the runtime during input (beside intermediate renderer updates, yeah we in single thread land still lol).

[Tyriar]

@egmontkob thanks for chiming in, your input is always invaluable ❤️

It's essentially pretty similar to VTE. Probably one notable difference is that for the second cell of a CJK we do explicitly store that it's a "fragment" as we call it, this might (or might not) make certain operations simpler than just treating it identical to an unused cell.

We're baically doing the same thing, the "empty cell" contains a string of '' and a width of 0, and a width of 0 can only mean that it's following a full width character.

Edit: Thinking about it, I'd prefer pterm's behavior as well, the other seems like a bug to me. Thanks for pointing me to this 👍

Yeah it makes sense to clear it.