CellMarker

[jerch]

With PR #2751 AttributeData got extended by "extended attributes". While it is quickly hardcoded there for the special needs to hold underline style and colors with small buffer footprint in mind, this approach is very limited in its static nature. If we can get this working in a more dynamic fashion, we can solve a long missing feature in xterm.js - cell markers.

Proposal

Early idea of a CellMarker API (for internal usage first):

interface ICellMarker {
  // mark cells in selection if condition is true
  markCells(selection: ICellRange, condition?: (position: CursorPos, cell: CellData) => boolean): void;
  // unmark cells in selection if condition is true
  unmarkCells(selection: ICellRange, condition?: (position: CursorPos, cell: CellData) => boolean): void;
  // marks a cell during cell write if condition is true
  markOnWrite(condition?: (position: CursorPos, cell: CellData) => boolean): void;
  // remove marker from write action
  removeFromWrite(): void;
  // get ranges of marked cell in selection
  getMarked(selection: ICellRange): ICellRange[];
}

Basic idea of this marker interface is:

• A cell marker moves with the cell data, thus strictly it is not a cell marker, but a data marker on cell level (not sure if we ever need true cell markers in the sense of grid position).
• A cell marker can either be placed on certain cells or into the write-chain (to be placed on write), filterable by a condition. The write thingy seems awkward at first, but on a closer look - it is basically the same as with other text attributes currently.
• A cell marker will have certain events to register on (not yet shown above), like onDispose etc. (TBD)
• Cell markers should only be used for rare cases, like annotating rarely occurring attributes to a cell.
• The meaning of a cell marker is left to the registering side.
• The low level storage in the buffer will be done similar to the extended attributes, thus only takes additional memory on a cell, if a marker was placed.

Additionally a cell marker might follow these cell marker types:

const enum CellMarkerType {
  // treated as content in the buffer (removed by follow-up write action from cell)
  CONTENT,
  // treated as text attribute:
  // --> removed by SGR 0 from write chain (following write will not place it anymore)
  ATTRIBUTE,
  // Not sure if we need this:
  // PERMA cell marker would stick to a cell until it got disposed by other means
  PERMA
}

This is basically a rewrite of the extended attributes in a more general and reusable fashion. The API idea is still convoluted, will see if this can be made simpler.

Why even care for cell markers?
We have several loose ends, where cell markers will help:

• hyperlink terminal sequence (see PR hyperlinks addon #2904, where I currently misuse the extended attribs)
• image/SIXEL handling in xterm.js (see my early PR image support #2503), with proper cell markers the ugly private buffer write hooks there are a no-brainer
• protection attributes (we dont support any yet, see ED/EL vs. DECED/DECEL)
• custom cell annotations in general

The last point might be the most important - currently we have no way to attach some custom functionality on individual cell level. For example - with cell markers it will be pretty easy to hook up some custom overlay when hovering over a cell (in conjunction with the new LinkProvider).

Up for discussion.

FYI: @Tyriar, @mofux

[jerch]

The conditional marking during writing is too much of a burden, thus I gonna remove the condition (term.write already runs >5 times slower with 2 conditional markers, guess due to heavy branching). It is still possible to get a similar result without it by doing slightly different steps:

• place a marker into write (now unconditionally)
• grab active cursor area start position (top-left cell reachable by the cursor)
• write something to the terminal, all written cells now contain the new marker
• grab active cursor area end position (bottom-right cell reachable by the cursor)
• unmark cells within the positions with negated condition

In the end the same cells will be marked as with the conditional write marking in the first place.

The methods markCells, unmarkCells and getMarked are still quite costly, but I think thats ok since they only run on explicit marker needs.

[Tyriar]

Can you expand on the API proposal to show where ICellMarker comes from? My thinking when I was talking about this was something along these lines:

export class Terminal {
    addMarker(x: number, y: number): ICellMarker | undefined;
}

export interface ICellMarker extends IDisposable {
    readonly id: number;
    readonly isDisposed: boolean;
    readonly position: IBufferCellPosition;
}

I guess with an onDispose event too.

Then allowing embedders to store data in their own way, eg:

interface IHyperlink {
    link: string;
    startPosition: ICellMarker
}

const hyperlinks: IHyperlink[] = [];
// ...
hyperlinks.push({
    link: url,
    startPosition: term.addMarker(x, y)
});

Essentially a pretty simple thing like the current IMarker that is just aware of the column position. Looks like you want to leverage the lean extended attributes work as well?

[jerch]

@Tyriar Well the API idea is still early and needs refinement to be usable/useful. I started from the line marker interface to shape this (basically what your interfaces look like).

Several problems popped up early with a direct transition of line markers into cell level. Esp. they are very wasteful on the buffer, if they can only represent a single cell, thus the idea to expand it to cell ranges. It is still possible to get the same behavior as your interface:

// your interface
const marker = addMarker(x, y);

// compared to the range based interface
const marker = new CellMarker(CellMarkerType.CONTENT);
marker.markCells({start: {x, y}, end: {x: x+1, y}});

Here a cell marker has a life of its own, and the proper creation / lifecycling is not yet clear from above. I have not shaped that part yet, but maybe some kind of a marker manager living on CoreTerminal might implement the needed bits. On public API all it needs would be:

export class Terminal {
  // Create a cell marker of attribute or content type.
  createCellMarker(type: 'attribute' | 'content'): ICellMarker;
}
// + interface definitions from above

Next problem I stumbled over are position updates - if the marker itself should always know its correct position in the buffer, any buffer action will suffer bad due to the need to update all markers' positions. Sadly I see no speedy way to get auto-updated positions on the marker working. Thus I turned the problem upside-down - if you need to get a hold of cell marker positions you have to actively request the positions from the buffer with getMarked. The result is only valid w'o buffer updates in between.

Btw the same is true for an onDispose event, no clue yet how to get this done w'o big perf sacrifices. It'll need some way of ref counting, will see.

Looks like you want to leverage the lean extended attributes work as well?

Yes, once I got this working the extended attributes could be replace with this. And prolly be used by addons later on as well. But I am not yet there, lol.

[Tyriar]

Next problem I stumbled over are position updates - if the marker itself should always know its correct position in the buffer, any buffer action will suffer bad due to the need to update all markers' positions.

Don't we only need to change it when it scrolls off the scrollback or on resize?

createCellMarker(type: 'attribute' | 'content'): ICellMarker

Is the intent here that any change in content or attribute invalidate the marker?

Btw the same is true for an onDispose event, no clue yet how to get this done w'o big perf sacrifices.

I was thinking they would only get disposed when they leave scrollback just like markers today which already fire an event, it's just not included in the API:

xterm.js/src/common/buffer/Marker.ts

Line 34 in 92fdf0c

this._onDispose.fire();

[Tyriar]

If perf here is a concern, another idea that I've been thinking about for a while is that we could avoid the marker line shift all together (within scrollback at least) if we just marked each line with an index, starting at 0. So if your scrollback is 1000 and 2000 lines have gone by, the buffer lines would have ids 1000-1999.

We could then remove this all together when that line leaves the viewport (as it's the only mutable part of the buffer):

xterm.js/src/common/buffer/Buffer.ts

Lines 585 to 607 in 92fdf0c

	marker.register(this.lines.onTrim(amount => {
	marker.line -= amount;
	// The marker should be disposed when the line is trimmed from the buffer
	if (marker.line < 0) {
	marker.dispose();
	}
	}));
	marker.register(this.lines.onInsert(event => {
	if (marker.line >= event.index) {
	marker.line += event.amount;
	}
	}));
	marker.register(this.lines.onDelete(event => {
	// Delete the marker if it's within the range
	if (marker.line >= event.index && marker.line < event.index + event.amount) {
	marker.dispose();
	}
	// Shift the marker if it's after the deleted range
	if (marker.line > event.index) {
	marker.line -= event.amount;
	}
	}));

delete/insert within the viewport could get complicated but still seems doable, slightly slower for the handful of lines in the viewport for no cost in the many lines of scrollback would be a win.

[jerch]

Don't we only need to change it when it scrolls off the scrollback or on resize?

Well we have tons of "cell moving" sequences, they would have to update the positions. and yes, resize will suffer really bad as it has to go through all buffer cells and re-eval marker positions.

Is the intent here that any change in content or attribute invalidate the marker?

Yepp:

• content type: behaves like normal cell content, thus gets overwritten by new cell data, that does not contain that particular marker itself
• attribute type: same as content, plus gets removed from newly written cell data on SGR 0 (basically behaves like a text attribute)

The attribute type is basically there to replace extended attrs later on (to not clutter the buffer with tons of optional additional types, that all have to be eval'ed during buffer manipulations). The content type is there for pretty much the same reason, but with another domain in mind: as I currently abuse the extended attrs in the hyperlink-addon it has a really nasty drawback - calling SGR 0 would remove the link annotation from follow-up cells, because extended attrs undergo the text attribute handling, where SGR 0 should reset any. While in fact the link annotation is cell "content" (not being SGR sensitive).

But as I said above, this is still not thought out in depth, prolly missing several things. Yet it already covers almost all cell marking needs I have from the hyperlink addon, the image addon and even the underline extension.

If perf here is a concern, another idea that I've been thinking about for a while is that we could avoid the marker line shift all together (within scrollback at least) if we just marked each line with an index, starting at 0. So if your scrollback is 1000 and 2000 lines have gone by, the buffer lines would have ids 1000-1999.

You mean like an always incrementing line index? I guess this would simplifly several position awkwardities throughout the whole codebase, prolly a good idea. Would only need special care during resize, and once we hit the max number (around 2³¹-1 I guess), and line inserts/removal.

[jerch]

Turned out, its not acutally needed for what I has in mind, thus closing.