Proper updating of GutterMarker RangeSet through transactions

Fevol · September 2, 2023, 4:25pm

I am in the progress of rewriting a statefield extension used for rendering gutter markers, to reduce rerendering of said markers to a minimum.

Currently, I’ve ended up with below code (slightly simplified for demonstration purposes):

type Node: { from: number, to: number, /* ... */ };

export class Widget extends GutterMarker {
	constructor(public node: Node) {
		super();
	}

	toDOM() {
		/* Create a gutter marker containing the text between node.from, node.to */
	}
}

export const widgets = StateField.define<RangeSet<Widget>>({
	create(state) {
		const builder = new RangeSetBuilder<Widget>();

		// The nodes indicate where and how the widgets should be added, 
		// 	the set of nodes is directly generated from a Lezer parse tree
		for (const node: Node of state.field(nodesField)) {
			const block_from = state.doc.lineAt(node.from);
			builder.add(block_from.from, block_from.to - 1, new Marker(node));
		}
		return builder.finish();
	}

	update(oldSet, tr) {
		if (!tr.docChanged) return oldSet;

		const allNodes: Node[] = tr.state.field(nodesField);
		const changedNodes = /* All nodes that were changed/added */
		const removedNodes = /* All nodes that were changed/removed */

		// Any node that was changed, must have its widget updated
		const add: Range<Widget>[] = [ /* All changedNodes */ ]

		const filter: (from: number, to: number, value: Widget) => {
			/* If value.node in removedNodes, return 'false' */
		};

		return oldSet.map(tr.changes).update({ filter, add });
	}
});

In essence, above code should boil down to:

Gutter contains Widgets which render text
Multiple Widgets can exist in the same block
Widgets are created via nodes parsed by a Lezer parser
On Document change, update (re-render) Widgets to reflect changes in text
Optimization: Render operation for Widget is expensive, only re-render Widget if a Node was updated

My main questions are:

Am I understanding the add and filter of the update function correctly?
I have not been able to find examples of this method, except for the breakpoint example, but that’s used in the context of effects being applied to a state, not edit operations.
Tangential to the previous question: is this a reasonable way to implement this feature, or are there alternative (simpler) functions/structures I should use instead? At the moment, I’m unsure how I will be getting the changed/added nodes (from state A → B) in an efficient manner.

I’m hoping to use this code as an example for other developers to efficiently update and render their custom widgets (be it for a gutter or a viewplugin).

Many thanks in advance!

(Below is some additional information and a short demo of what this code is doing in practice)

Additional information

The document can contain text which is surrounded by {>> <<} tags (based on the CriticMarkup syntax)

Any text surrounded by these tags gets parsed by my custom grammar. The parser tree is stored within a StateField.

Every ‘Node’ (every instance of {>>TEXT<<}) gets turned into a Widget and added to a gutter.

On insert/deletion in ‘Node’ (i.e.: {>>TEXTinserted<<}), the corresponding Widget should be updated and re-rendered.

This is what the output currently looks like:
CM Discuss example

marijn · September 3, 2023, 1:40pm

I’m a bit confused what new Marker is—since builder.add takes a Range<Decoration>, why are you calling a constructor that constructs something else? Unless it is not a real constructor and always returns some other object, but then it might as well be a regular function.

Defining an eq method on your widget type (that probably just returns this.node == other.node) can make this a bunch easier—widgets simply kept in the view, not re-rendered, when they are replaced by an equal-testing widget. So you could just, on document changes, re-run the logic you currently have in your statefield constructor, and still get a minimal DOM update.

Also, unless you are certain that documents aren’t going to be big, it can be much more efficient to use a view plugin that only draws the decorations for the current viewport (view.visibleRanges), instead of keeping them for the entire document.

Fevol · September 4, 2023, 3:17pm

Thanks as always for your responses, I very much appreciate them.

Sorry for the delay in my answer, I wanted to make sure that I exhausted all options before I asked more questions.

(Also, a small practical note: the first and third foldable sections can be skipped, they just contain responses)

(minor, typo) Usage of new marker

Ah apologies, that is an artifact of me simplifying the original code. It should be new Widget instead of new Marker. I’m really sorry for the confusion!
(Side-note: in terms of terminology, I do think that new Marker would actually be the correct (less confusing) word, as I’m specifically referring to GutterMarkers here, I sadly can’t edit my original post anymore to correct this, but I’ve corrected it further on)

(issue, question) Issue with simplified update approach

Thank you, this is exactly what I needed! It does in fact simplify things a lot.
However, I’m running to one snag with this approach:

Goal: be able to re-use the constructMarkers function and just compare the old markers to the new set of markers (let the Gutter/Viewplugin handle re-rendering/adding of new markers through use of the eq method)
Issue: the nodes contained in the old set of markers do not get updated if the state changes, their ranges (from, to) still reflect the old state without the changes applied to it. This results in the equality comparison always being false (and thus constant rerendering).
Solution: iterate through the old markers and manually apply the changes to the nodes - however, if the changes were inside the node, do not apply the changes, in order to force a re-render. In theory, this should result in only changed/added nodes being rerendered.
Problem (aka ‘the snag’): it seems like I’m not correctly updating the node directly from the markers. On every second transaction, the comparison always returns false. The oldSet markers within the update function do get their nodes updated correctly, but within the eq function, the offsets were never added to the other (older) marker.

Essentially, the problem boils down to the fact that I’m not sure how to update the nodes in my original markers, such that the eq method will only return false for nodes that were effectively changed.

CODE

// Node also contains a slew of helper functions (but simplified here)
type Node: { from: number, to: number, /* ... */ };

export class Marker extends GutterMarker {
	constructor(public node: Node) {
		super();
	}

	eq(other: Node) {
		return this.node.from === other.from && this.node.to === other.to;
	}

	toDOM() { /* ... */ }
}

function constructMarkers(state: EditorState): RangSet<Marker> {
	const builder = new RangeSetBuilder<Marker>();
	for (const node: Node of state.field(nodesField)) {
		const block_from = state.doc.lineAt(node.from);
		builder.add(block_from.from, block_from.to - 1, new Marker(node));
	} 
	return builder.finish();
}

export const widgets = StateField.define<RangeSet<Marker>>({
	create(state) {
		return constructMarkers(state);
	}

	update(oldSet, tr) {
		if (!tr.docChanged) return oldSet;

		const updatedSet = oldSet.map(tr.changes);
		// This function returns a slightly simpler representation of the changes
		const changes: { from: number, to: number, added_char: number, removed_char: number}[] = getEditorChanges(tr.changes);
		let change = changes.pop(), offset = 0;
		const cursor = updateSet.iter();
		
		// Map all nodes inside the markers through the changes
		while (cursor.value && change) {
			const node = cursor.value.node;
			while (change && node.infront_of_change(change)) {
				offset += change.added_char - change.removed_char;
				change = changes.pop(); 
			}

			if (change && node.contains_change(change)) {
				offset += change.added_char - change.removed_char;
				change = changes.pop(); 
			} else {
				node.apply_offset(offset);
			}
		}
		while (cursor.value) {
			cursor.value.node.apply_offset(offset);
			cursor.next();
		}

		return createWidgets(tr.state);
	}
});

(minor) Usage of viewplugin

Thanks! I did not realise that the viewplugin could also be used as a providor of values for the gutter

Sadly, for the gutter I’m currently working on, I do think I’m forced to use a Statefield. My widgets (in-document) should be able to execute code on my markers (in the gutter), and it is not guaranteed that the marker will be in-view (since multiple markers can exist on the same line, each one pushing the others down).

For reference: here is a (hopefully not too messy/incorrect) overview of the entire system:

And for those interested, here is how this ViewPlugin code looks when used together with a Gutter.

const gutterMarkers = ViewPlugin.fromClass(class GutterMarkers implements PluginValue {
	markers: RangeSet<Marker> = RangeSet.empty;

	constructMarkers(view: EditorView) {
		const builder = new RangeSetBuilder<Marker>();
		// Make sure to use view.visibleRanges() to only generate markers within viewport
		return builder.finish();
	}

	constructor(view: EditorView) {
		this.constructMarkers(view);
	}

	update(update: ViewUpdate) {
		if (update.docChanged || update.viewportChanged || update.heightChanged)
			this.constructMarkers(update.view);
	}
});

const gutterExtension = [
	gutterMarkers,
	gutter({
		markers: v => v.plugin(gutterMarkers)!.markers
	})
];

marijn · September 4, 2023, 4:47pm

Can you define your nodes in terms of what they should contain/display, instead of in terms of their position? That should make it much easier to verify that they are the same in the way that matters.

Also, maybe (maybe not, I don’t know your requirements that well) the DecorationSet can be the canonical way you store the nodes in your nodesField, since those can be mapped over document changes very efficiently.

Fevol · September 5, 2023, 2:53am

Thank you! This turned out to be the most convenient solution, even if it required rewriting a lot of the underlying systems of my code. For those interested, the final code is as simple as:

type Node = { from: number, to: number, text: string, /* ... */ };

class Marker extends GutterMarker {
	constructor(public node: Node) {
		super();
	}

	eq(other: Marker) {
		return this.node.text === other.node.text;
	}
}

function constructMarkers(state: EditorState): RangeSet<Marker> {
	const builder = new RangeSetBuilder<Marker>();
	for (const node: Node of state.field(nodesField)) {
		const block_from = state.doc.lineAt(node.from);
		builder.add(block_from.from, block_from.to - 1, new Marker(node));
	} 
	return builder.finish();
}

export const gutterMarkers = StateField.define<RangeSet<Marker>>({
	create(state) {
		return constructMarkers(state);
	},

	update(oldSet, tr) {
		if (!tr.docChanged)
			return oldSet;
		return constructMarkers(tr.state);
	}
});

That’s a very interesting point, I’ll have to check whether it is viable to port everything I have to use the DecorationSet system, though currently, the performance overhead from nodes recomputations does not seem to be too drastic.

Regardless, many thanks again for your help. I truly appreciate everything that you do.