Incremental update of parse tree?

[mblinsitu]

I am interested in Ohm because of its ability to do incremental parsing.
However, what I really would like to have is incremental updates of the parse tree.

This is for a project where I want to provide real-time preview of a Markdown-like language. With incremental updates to the tree, I could incrementally update the DOM, rather than either replace all of it, or figure out what has changed by comparing the trees.

I've tried to store weak references to the nodes in a WeakMap, but after incremental parsing it looks like the tree is entirely new, i.e. it's not reusing the nodes from the old tree.

Is this by design (i.e. due to the parsing algorithm - I am not familiar with PEG grammars)?
Is there a way to find out which part of the parse tree were not affected by the edit?

Thanks.

[pdubroy]

The documentation is somewhat vague about this¹, but the arguments to semantic actions aren't actually the parse tree nodes themselves, but rather wrappers around the parse tree (i.e., CST) nodes. You can access the raw CST node via the _node property of the wrapper.

While the wrappers will all be freshly created, the underlying CST nodes will be re-used where possible. So you should be able to use the raw CST nodes for the purposes you're describing here.

An interesting thing about our use of wrappers is that it allows us to track dependencies within the semantic actions (i.e., we can see which operations/attributes of which nodes were used). So theoretically, it should be possible to implement incremental semantic actions as well. I'd love to implement that but haven't had the time to.

Anyways, hope that helps!

Footnotes

1. We originally did this to avoid confusion, but in retrospect it would probably be clearer if the documentation distinguished between wrappers and CST nodes. ↩

[mblinsitu]

After a long pause I am back to this incremental parsing stuff.

Re-reading your response, I wonder what you mean by "we can see which operations/attributes of which nodes were used". Is that accessible throught the API?

I did a test with an attribute gen and an operation trace. genNumber is a number that I increment each time I parse again; trace is called after parsing to display the CST with the value of the gen attribute for each node:

	// Actions for the attribute `gen` that marks each node with a "generation" number.
	// `genNumber` is incremented after each call to `match`, 
	// so the `gen` attribute tells us when the node was created
	let genNumber = 0
	const cachingActions = { // store current genNumber in the `gen` attribute
		_terminal() { return genNumber },
		_iter(...children) { return genNumber },
		_nonterminal(...children) { return genNumber },
	}

	// Actions for operation `trace(depth)` that dumps the CST with the generation numbers
	// (`trace` is a print function that indents the line according to its first argument)
	const traceActions = {
		_terminal() { trace(this.args.depth, + "'"+this.sourceString+"' " + this.genNumber },
		_iter(...children) { 
			trace(this.args.depth + this.ctorName+': '+ this.gen + (this.gen  < genNumber ? ' !!' : ''))
			children.map(c => trace(this.args.depth+1))
		},
		_nonterminal(...children) { 
			trace(this.args.depth + this.ctorName+': '+ this.gen + (this.gen  < genNumber ? ' !!' : ''))
			children.map(c => trace(this.args.depth+1))
		},
	}

The result is that when doing incremental parsing, only the nodes that have been newly created have a generation number equal to the current generation. The others keep the generation number when they were created. This seems consistent with the documentation, which says: "An Attribute is an Operation whose result is memoized, i.e., it is evaluated at most once for any given node.",

My question is: Is that a reliable way to figure out which parts of the CST have been updated? And is it also the case that the subtree of an "old" node is also entirely "old"? (or, conversely, that when a new node is created, all the nodes of its parent chain are also (re-)created?)

Thanks!

[mblinsitu]

Thanks, it works! Using the _node property, I can see which nodes "survived" the edit!
BTW, is it safe to add a property to these _node objects? (Otherwise I can use a WeakMap of course).

Incremental semantic actions would be nice indeed :-)

[pdubroy]

Personally, I would probably just use the WeakMap. It's unlikely to cause problems if you store properties on the node objects themselves, however, we do rely on being able to store arbitrary, name-mangled properties on nodes for the purposes of memoizing attributes.