Use Virtual DOM for rendering

[mofux]

I'd like to discuss the usage of a virtual dom implementation for rendering the output (lines, selection, links...).

At the moment, we implement something similar by caching spans that we can reuse for the next render cycle. Although this is okay for the moment, I feel it is very constraining:

1. There is no real view / model that is used to render the DOM nodes in the viewport. At the moment there is a quite complex and difficult to extend block of logical statements that directly create the DOM nodes from the somewhat flat row / col array. I feel it would be much nicer if those logical statements would produce a data structure (view model) that can be efficiently rendered, cached and extended by a virtual dom library.

2. It is very hard to delay rendering for certain features, like the linkifier. It would be much nicer if the linkifier could asynchronously process the data and eventually update the targeted cols with a flag, that will then be reflected in the rendered output automatically.

3. The current data structure is neither optimised for rendering performance, nor for scenarios like linkify or find that have to get context from the data.

Challenges

I believe the biggest challenge is to convert a flat data structure (row/col data) into a optimised, reusable view model. For example the string:

Hello World

would have to end up as

Hello <span class="xterm-bold">World</span>

In other words, cols have to be grouped based on their flags. Cols that share the exact same flags can go into the same group (DOM node).

My approach would be to use the following (possibly extendable) flags for every col:

• fg number: The foreground color
• bg number: The background color
• bold boolean: Bold col
• underline boolean: Underlined col
• blink boolean: Blink col
• inverse boolean: Invert fg/bg
• invisible boolean: Col is invisible (.xterm-hidden)
• cursor boolean: Cursor is at this position
• wide boolean: Is a wide character being rendered
• noAscii boolean: Is the character a non-ascii character (charcode > 255)
• selected boolean: Col is currently selected (Selection Manager)
• matched boolean: Col is currently matched by a search term (find addon)
• link string: Col is linked with this url (Linkifier)

And process them into an array of lines, where every line contains the definition of the grouped cols that share the same flags:

[[
  { chars: 'Hello ', flags: {} }, 
  { chars: 'World', flags: { bold: true } }
]]

This view model would be easy to convert into virtual dom by looping over the rows, rendering a div for every row, and then looping over the groups and creating a span or a for every group and add a class or style to reflect the flags.

In order for the linkifier, selection manager or the find addon to set / remove flags, they would have to register themselves as a middleware before the grouping stage, so they can flag cols before they are grouped.

Any thoughts?

[Tyriar]

So I would like to add a view model soon, the initial version would be focused on pulling the wrapping out of CircularList and into the view model so that we can support reflow #622 (wrote up ideas for this in #644 (comment)).

[[
  { chars: 'Hello ', flags: {} }, 
  { chars: 'World', flags: { bold: true } }
]]

This is similar to what I proposed in #791, where the attributes are assigned to chunks of characters, rather than single characters. This also has benefits in performance as we would only need to evaluate the attribute's styles once.

Needing to create another structure like this could introduce a more memory issues that I'm trying to solve right now. I don't feel like xterm.js is a typical web app where we could defer to something like react and get efficiency benefits from it, I'd love to be proven wrong but I see the amount of data xterm.js needs to house and the performance/memory standards I have for it as being too high. Plus we depending on such a library would increase the payload size and force users into using some particular framework. Note that I have very limited experience with such virtual DOM frameworks, but we're trying to store so much data we're avoiding the typical JS way of doing things with objects and properties and opting for arrays and bit fields instead to avoid that additional cpu/memory burden.

• selected boolean: Col is currently selected (Selection Manager)
• matched boolean: Col is currently matched by a search term (find addon)
• link string: Col is linked with this url (Linkifier)

Currently these are completely separated from the rendering part, living in their own little modules that the core lib doesn't know about. This is good because it reduces the complexity and number of external dependencies of the core rendering logic.

With links in particular also, this is a lot of work we can completely avoid unless the buffer stops moving. Links take a bunch of time to generate because we need to parse the text, create the node, insert it cleverly. While we would avoid the insertion logic if we put this into the renderer it would increase the complexity of the renderer quite a lot for little gain. Right now if you run a command that generated heaps of output, links will not be generated until the output stops.

[mofux]

@Tyriar thanks for your thoughts!

I was thinking about writing our own small Virtual DOM implementation that is optimised for our own needs. There is an excellent article on how it can be done here. In fact, the current spanObjectPool idea is not too far away from it :)

The selected, matched and link flags are very important parts of the idea above, because they will solve some problems we currently encounter:

SelectionManager: Invert selection color
At the moment we maintain a separate layer that draws the selection. This comes with the drawback that the text and background is always underneath the selection, plus the inability to invert the selection color. With my approach, the selected cols would automatically be grouped up to the point where the selection ends, and every group that is within a selection could get a class like xterm-selected - which would simply allow us to overwrite the background color with the selection color via css.

Find Addon (Enhancement): Show all found matches
At the moment it is not possible to mark all matched instances of the search term in the viewport. With my approach, matches are automatically grouped, and could get a class like xterm-matched to style them via css.

Example
Have a look at this API example, that can be used by Addons and Core components to set flags and modify the rendered output:

term.middleware('SelectionManager', {

  // onRefresh will be throttled and called after
  // idle for this time of ms
  refreshDelay: 100,

  // Called if the viewport is refreshed (throttled by the delay above)
  onRefresh(rows, startIndex, endIndex) {

    // Rows are the current CircularList rows that are in the viewport
    // Here we can loop over the rows and cols and add / remove flags
    for (let i=selectionStartRow; i<=selectionEndRow; i++) {

      let cols = rows[i];
      if (i !== selectionStartRow || i !== selectionEndRow) {
        for (let col of cols) col.flags.selected = true;
      } else {
        // figure out the cols that belong to the selection and mark them selected
      }
    }
  },

  // Called for every group that is drawn to the DOM if there was a change
  onDraw(group, element) {

    // group is the affected view model data structure, 
    // element is the DOM node drawn for that group
    if (group.flags.selected) element.classList.add('xterm-selected');
  }

});

// Somewhere in SelectionManager...
// Manually trigger a refresh for the selection manager (will call onRefresh)
// because mouse is down and the user is dragging and the selection has to be updated
term.render('SelectionManager');

[Tyriar]

@mofux wouldn't the structure you propose get very complex and verbose quickly as flags can overlap?

[[
  { chars: 'He', flags: {} }, 
  { chars: 'll', flags: {link: 'http://xtermjs.org'} }, 
  { chars: 'o', flags: {selected: true, link: 'http://xtermjs.org'} }, 
  { chars: ' ', flags: {link: 'http://xtermjs.org'} }, 
  { chars: 'W', flags: {fg: x, link: 'http://xtermjs.org'} }, 
  { chars: 'o', flags: {fg: x, bold: true, link: 'http://xtermjs.org'} }, 
  { chars: 'rld', flags: { bold: true } }
]]

Seems better to me with the current thinking where we would essentially have this:

line = "Hello World";
selectionStart = [4, 0];
selectionEnd = [5, 0];
styles = [
  [0, x, 0],
  [bold, x, 0],
  [bold, 0, 0]
]

And then use that to draw the lines when necessary. It would be nice to cache links against lines but that could be a lot of memory to gain speed in an area that doesn't need it.

While the code in the term.middleware('SelectionManager' example certainly looks nice and simple, we would still need SelectionManager.ts in its current form, it would only replace Renderer.refreshSelection which is fairly simple already. This would be at the cost of a selected flag against the data of every span inside the selection, as opposed to currently where we just have 4 integers.

Plus would it also duplicate all the data inside the CircularList to come up with the view model? That would probably more than double memory usage of the buffer, no? My thinking for a view model was to keep the data it needs very minimal, say storing the indexes that a line wraps and providing a nice method to get the actual wrapped row at some index.

I feel like this problem tackles rendering simplicity and performance via caching at the cost of memory. Rendering performance isn't an issue currently imo.

I do like the structure in your code example. Perhaps we should pursue better componentization in general so we have the core library and then a bunch of components plugged in (composition, selection, find, linkifier, etc.). Less interdependent parts would make the lib a lot simpler.

[Tyriar]

Also 👍 to lessons learned on minimizing DOM interaction from https://medium.com/@deathmood/how-to-write-your-own-virtual-dom-ee74acc13060 without additional memory overhead.

[mofux]

Perhaps we should pursue better componentization in general

I think this should be the ultimate goal, especially because it would allow for some really awesome plugins - plus it adds simplicity when it comes to writing tests. Something like a component interface that must be implemented or extended by a component, and which provides all the lifecycle hooks:

Interface IComponent {
  onRefresh(rows: CircularList, startIndex: number, endIndex: number): void
  onDraw(group: RenderGroup, element: HTMLElement): void
  onMousedown(evt: MouseEvent): void
  onMouseup(evt: MouseEvent): void
  onInput(evt: KeyboardEvent): void
  onFocus(): void
  onBlur(): void
  onScroll(): void
  onOpen(term: ITerminal): void
  onResize(rows: number, cols: number)
  // ...
}

class SelectionManager implements IComponent {
  constructor(term: ITerminal) { ... }
  // ... hook to what is needed
}

// register
term.middleware('SelectionManager', SelectionManager);

wouldn't the structure you propose get very complex and verbose quickly as flags can overlap?

Yes... it is also not very optimised because it would potentially create spans that could be avoided (by nesting groups, where child groups would share the same flags with the parent).

Mmmmhh... it is really hard to get this right. I think basically we are looking for a way to tag a certain range of characters within the viewport, and then render the visual representation of this character range based on its tags. To efficiently render those tagged ranges, the Renderer would have to figure out how to use the fewest elements to archive it, and how to re-use elements to avoid DOM manipulation. Ideally it should key on a unique row id, so scroll events or static re-render doesn't cause DOM manipulation for rows that remained in the viewport and did not change.

[Tyriar]

Interface IComponent

A BaseComponent that implements the IComponent with empty implementations for each interface would probably be ideal, not many components would use everything.

I think basically we are looking for a way to tag a certain range of characters within the viewport, and then render the visual representation of this character range based on its tags.

Pushing this component idea, instead of trying to do this all at once, we could split it all up completely:

• Renderer component renders the text
• BackgroundRenderer component renders the background
• Linkifier component renders the links on top (don't even touch the spans with text, just overlap ones on top?)
• Selection component renders the selection

We can keep talking about this, but I wouldn't want any work to begin until the follow issues are resolved:

• TS conversion Migrate code base to TypeScript #335
• Investigate screen readers (may impact the design) Support screen readers #731
• Truecolor support Terminal does not render true color  #484
• Buffer memory improvements Buffer performance improvements #791

Maybe componentization belongs in a new issue though?

[mofux]

@Tyriar I agree . Let me summarise on the Virtual DOM concept and your ideas above:

A Virtual DOM is a representation of the real DOM, but not based on actual DOM nodes, but on a data structure. If this data structure is mutated, the Virtual DOM implementation will diff the changes between the old and the new data structure, and update the underlying real DOM to reflect those changes.

This means that components that want to modify the DOM have to alter the data structure, which will then be automatically reflected on the real DOM.

The way this Virtual DOM data structure looks is up to us. React and other Virtual DOM implementations use hyperscript h(...) or jsx (which transpiles to hyperscript) to describe the Virtual DOM data structure.

The big advantage we have is that we operate on a fixed sized grid (rows / cols), where the position and boundaries of a character within the grid / viewport can be easily calculated. This allows us to have multiple stacked layers (background, foreground, selection, links, ...) where elements inside those layers can be absolutely positioned. One example would be a background layer, where the background color would be a div with that background-color, that is absolutely positioned to exactly match the position of the characters that have this background color. Another example is the text layer, where every row is a div that contains the plain text entries (with the exception of double-width and non-ascii characters that would have to be wrapped into a span to maintain a fixed size).

So what is our hyperscript?
I think components should use an API where they can request a layer, and then draw stuff onto that layer using relative x, y row/col coordinates (like in term.buffer.lines.get(y)[x]). The Virtual DOM renderer will then take care of translating those relative positions to the actual position in the DOM (also respecting double-width characters etc).

Example: Selection Manager

// gets a new blank layer that can be diffed with 
// a previous layer of the same name (if existent)
let layer = term.getLayer('SelectionManager');
layer.class('selection-manager');

// draw the upper rect of the selection
// usage: layer.draw(type, startX, startY, endX, endY);
let rect = layer.draw('div', selectionStartCol, selectionStartRow, ...);

// set background and class
rect.style('background-color', '#ABABAB');
rect.class('xterm-selection-start');
...

Example: Text Renderer

let layer = term.getLayer('TextRenderer');
layer.class('text');

for (let y=0; y<rows.lengths; y++) {
  let row = rows[y];
  let rowRect = layer.draw('div', 0, y, term.rows, y + 1);

  for (let x=0; x<row.length; x++) {
    // get consecutive single-width ascii chars and draw them in the
    // same rect. create a new rect for every other char
    let char = row[x];
    let charRect = rowRect.draw('span', x, y, x + 1, y + 1);
    charRect.text(char[1]);
    ...
  }
}

Can you feel it? This feels nice! Drawing something is completely decoupled, no need for a shared underlying view model and no more messing around with the DOM directly!

[Tyriar]

Moved the component idea to #808

[Tyriar]

@mofux something like that would be cool yeah. Doing the actual text would be the hardest part as it happens so frequently, we might need to continue doing that layer non-absolutely. It is also the main one that needs to work on screen readers.

[mofux]

I actually think that positioning things absolutely should speed up the render performance, because the browser can skip many layout calculations. For screen readers... I'm not sure if they really consider for the position css attribute, or if they are interested in the order of the DOM nodes (which should be okay then).

I would like to write a prototype of the Virtual DOM renderer with the concept stated above and share once I find some time, so we can further iterate and performance test on that 🤓

[Tyriar]

@mofux sounds good.

RE absolute: It's definitely worth benchmarking the two, I would think the fact that each absolutely positioned span is a new layer and there could potentially be hundreds would be bad for perf.

[mofux]

Oh now I see what you mean, maybe there should be an additional api like this:

let rowRect = layer.draw('div', ...);

rowRect.appendText('I like ');

let specialCharSpan = rowRect.appendInline('span');
specialCharSpan.class('xterm-normal');
specialCharSpan.text('🤓');

rowRect.appendText(' faces');

Which would create a stack:

['I like ', <span class="xterm-normal">🤓</span>, ' faces']

That is finally rendered as:

<div>I like <span class="xterm-normal">🤓</span> faces</div>

where only the div is absolutely positioned. I'll try to figure out a nicer and more consistent API syntax when implementing the prototype.

[mofux]

Just thinking, another perk of having a drawing abstraction in between: it would allow us to implement a drawing engine that is not based on actual DOM elements - for example we could render the screen in a canvas or svg or even in webgl, which should boost the performance even further 😎

[Tyriar]

Closing in favor of #935, the IRenderLayer interface I landed on ended up being very similar in shape to the IComponent above 😄