Execution-Context-independent SpanTrees

[kazcw]

Currently, the structure of a SpanTree depends on information the engine provides after executing the graph.

This is a cause of complexity, bugs like #6772, and performance issues.

To fix this:

• Execution results should not be an input to SpanTree generation; it should be a pure function of the syntax.
• We should not reparse text to SpanTrees to handle execution results; rather, we should change what execution-information is associated with the SpanTree nodes.

As a result:

• Crumbs will be stable references to ports (i.e. an expression will be the same shape after substituting _), fixing Malfunctioning edge after detaching source end #6772.
• Performance problems due to widgets being reloaded after graph execution will be fixed.

This will require deep changes to the SpanTree design, however it will fix some bugs that cannot be solved properly without design changes, and will result in cleaner separation of concerns.

(I'll add an estimate to this soon. It is at least a 5 day project.)

[farmaazon]

Currently, the structure of a SpanTree depends on information the engine provides after executing the graph.

In fact, the controllers already can give you a Span Tree without execution context, just use connections method of "non-executed" graph controller: https://github.com/enso-org/enso/blob/f8cb908095f90a10277b5852f65d0f766fe12a72/app/gui/src/controller/graph.rs passing Empty as SpanTreeContext.

Crumbs will be stable references to ports

I think it's not so simple. How do you want to handle "gray" ports? They depend on execution results. We could technically add them as additional info to method call span in span tree, but:

1. This may uproot the mechanics of creating widgets, am I right @Frizi ?
2. Still, it won't make crumbs stable: as after disconnecting the source of connection to one of the function arguments, the connection's target changes to gray port, possibly changing its crumbs anyway.
3. It would break the assumption that node port == Span Tree node, on which we may rely in many places.

Overall, I think it's a wrong solution to the problems mentioned in the issue. For "Malfunctioning Edge" I would rather find an alternative way for locating port than list of indexes: perhaps we should mix indexes with argument names?

GitHub

enso/graph.rs at f8cb908095f90a10277b5852f65d0f766fe12a72 · enso-org/enso

Hybrid visual and textual functional programming. Contribute to enso-org/enso development by creating an account on GitHub.

[Frizi]

This may uproot the mechanics of creating widgets, am I right @Frizi ?

Yes, the widget tree heavily relies on the AST IDs assigned to the span tree, as well as resolved method call metadata to produce expected argument nodes, appropriate insertion points and data necessary to properly query dynamic widgets.

There might also be an alternative approach. I think that with widget tree being a thing, we don't really have that strong need to have the span tree in the first place. I believe that Its existance is actually a complication in many different areas, notably the expression editing code. We could quite easily transform the widget tree to work on the new AST structure directly, and query/watch the suggestion database itself. We could inject appropriate widgets like argument placeholders directly at that level, without building an intermediate tree structure. There would also be no need for "insertion points". The code modifications could also be expressed easier as a set of AST operations, not span-tree "insert"/"erase" actions. I believe that our new AST representation is suitable for that.

[farmaazon]

I would still give span tree a chance.

There would also be no need for "insertion points".

Remember that the insertion points have made life easier when talking about connections: you could specify the connection endpoint by just span-tree crumbs. With you solution we must change it to AST crumbs + optional "insertion point" info (an argument by index or name, position on list, maybe add element to operator chain, etc.) Of course, we could manage it (expect significant refactoring here), but span tree was designed to unify such cases.

and query/watch the suggestion database itself.

This somehow mix the controller/view separation. The widget tree, being currently in the view, cannot access to any database. To fix that, the controllers should, basing on the information they have, create a good model, on which you can easily instantiate concrete widgets.

Once done, we can call this model "span-tree", and this way do the refactoring.

[Frizi]

Remember that the insertion points have made life easier when talking about connections: you could specify the connection endpoint by just span-tree crumbs.

I think that those are actually a significant source of issues. We had and still have many bugs caused by span-tree being modified while an edge is being dragged. The crumbs defined within the connection model are not stable across tree updates, therefore they get stale and either point to an incorrect node, or no node at all. We have no way of detecting that situation, or updating the crumbs accordingly. To solve this, we will need a better, more stable way to refer to the intended edge endpoint location.

For fully connected edges, we don't actually care too much. Every time the expression is updated, we basically rebuild the connected edge models completely from scratch, redoing alias analysis on the updated expressions. The edges that are detached on the source side (the target stays connected) are an exception though - they don't exist from the perspective of the controller. The view maintains their state using the aforementioned span tree crumbs. This is not really correct to do, as it is not a sufficiently stable identity of the location within the expression.

This somehow mix the controller/view separation.

I think I was a little too loose with my wording. We would need a model that would contain relevant information about all AST nodes within each node's expression. It could be prepared and updated by the graph controller. It doesn't have to be itself a tree though. The view would use that data while building the widgets from the AST.

[farmaazon]

For fully connected edges, we don't actually care too much. Every time the expression is updated, we basically rebuild the connected edge models completely from scratch

Do we? I thought we do not touch edge if its crumbs weren't changed. Or at least this was so before the widgets era.

The view would use that data while building the widgets from the AST.

And this is my point of concern: Isn't it too much of logic for the view?

[wdanilo]

Let's have a call about this design :) I've scheduled it for tomorrow :)

[Frizi]

Do we? I thought we do not touch edge if its crumbs weren't changed. Or at least this was so before the widgets era.

I think it depends on what you mean by "touch". The view update will be skipped for edges that were determined unchanged, but the road to get there is pretty bumpy. The connections model of the entire graph is actually computed on-demand for each view update:

enso/app/gui/src/presenter/graph.rs

Lines 563 to 569 in fe0a06d

	impl ViewUpdate {
	/// Create ViewUpdate information from Graph Presenter's model.
	fn new(model: &Model) -> FallibleResult<Self> {
	let state = model.state.clone_ref();
	let nodes = model.controller.graph().nodes()?;
	let connections_and_trees = model.controller.connections()?;
	let connections = connections_and_trees.connections.into_iter().collect();

enso/app/gui/controller/double-representation/src/graph.rs

Lines 96 to 99 in fe0a06d

	/// Gets the list of connections between the nodes in this graph.
	pub fn connections(&self) -> Vec<Connection> {
	connection::list(&self.source.ast.rarg)
	}

The same thing happens with span trees (in fact, it's part of the Connections structure for some reason). From the presenter point of view, both of those structures are completely ephemeral and derived from source just in time.

Nothing wrong with this approach in general, but those structures are definitely too expensive to rebuild for my comfort right now. We would likely benefit from making them cheaper to build (or eliminate completely), especially the span tree.

Per each "view update", the presenter then attempts to set the expression for each node, and add/remove connections.

enso/app/gui/src/presenter/graph.rs

Lines 716 to 717 in fe0a06d

	expression_update <= update_data.map(|update| update.set_node_expressions());
	update_node_expression <- expression_update.map(ExpressionUpdate::expression);

enso/app/gui/src/presenter/graph.rs

Lines 748 to 749 in fe0a06d

	remove_connection <= update_data.map(|update| update.remove_connections());
	add_connection <= update_data.map(|update| update.add_connections());

The edge update is actually interesting. Changing endpoind crumbs will effectively be translated into remove+add pair of operations. The edge views will not be reused.

Finally, the node updates specifically are filtered for changes, so that the unchanged node views don't need to be updated.

enso/app/gui/src/presenter/graph.rs

Lines 589 to 597 in fe0a06d

	fn set_node_expressions(&self) -> Vec<ExpressionUpdate> {
	self.nodes
	.iter()
	.filter(|node| self.state.should_receive_expression_auto_updates(node.id()))
	.filter_map(|node| {
	let id = node.main_line.id();
	let trees = self.trees.get(&id).cloned().unwrap_or_default();
	let change = self.state.update_from_controller();
	if let Some((id, expression)) = change.set_node_expression(node, trees) {

enso/app/gui/src/presenter/graph/state.rs

Lines 446 to 469 in fe0a06d

	/// Set the new node expression. If the expression actually changed, the to-be-updated view
	/// is returned with the new expression to set.
	pub fn set_node_expression(
	&self,
	node: &controller::graph::Node,
	trees: controller::graph::NodeTrees,
	) -> Option<(ViewNodeId, node_view::Expression)> {
	let ast_id = node.main_line.id();
	let new_displayed_expr = node_view::Expression {
	pattern: node.info.pattern().map(|t| t.repr()),
	code: node.info.expression().repr().into(),
	whole_expression_id: Some(node.info.id()),
	input_span_tree: trees.inputs,
	output_span_tree: trees.outputs.unwrap_or_else(default),
	};
	let mut nodes = self.nodes.borrow_mut();
	let displayed = nodes.get_mut_or_create(ast_id);
	let displayed_updated = displayed.expression != new_displayed_expr;
	let context_switch_updated = displayed.context_switch != node.info.ast_info.context_switch;
	let skip_updated = displayed.is_skipped != node.info.macros_info().skip;
	let freeze_updated = displayed.is_frozen != node.info.macros_info().freeze;
	if displayed_updated || context_switch_updated || skip_updated || freeze_updated {

Note that this check is in of itself actually quite expensive - we are deep-comparing the span tree structures, and again it happens for all nodes in the graph on each individual view update. Those contain a ton of boxed objects and strings. I believe that if we remove the span tree, we could directly pass AST updates to the relevant updated nodes, removing all of that logic completely.

For edges, the view updates are relatively cheap right now, but it could also be made significantly simpler. Each connection is a pair of endpoints, each containing an Rc<Vec<Crumb>> (and potentially a vec for var_crumbs, but this one is usually empty). At least four individual allocations per edge, per view update. On each update, those are also all placed in a hashmap and searched to determine adds and removes. That involves comparisons of those crumb vectors. We could easily simplify this data to a set of few UUIDs, and maybe a set of flags to denote insertion before/after certain AST nodes.

Also importantly, the detached edges are not affected by view updates. That means their endpoints can easily become invalid right now. I discovered this issue when adding support for named arguments, because the span tree structure is significantly affected when a connection to a named argument is broken. The detached edge's target endpoint crumbs had to be explicitly updated to match expected location of future insertion point. This logic is obviously incredibly brittle.

enso/app/gui/src/presenter/graph.rs

Lines 301 to 312 in fe0a06d

	let ast_to_remove = update.remove_connection(id)?;
	Some(self.controller.disconnect(&ast_to_remove).map(|target_crumbs| {
	if let Some(crumbs) = target_crumbs {
	trace!(
	"Updating edge target after disconnecting it. New crumbs: {crumbs:?}"
	);
	// If we are still using this edge (e.g. when dragging it), we need to
	// update its target endpoint. Otherwise it will not reflect expression
	// update performed on the target node.
	self.view.replace_detached_edge_target((id, crumbs));
	};
	}))

To be honest, I don't fully understand why we need the extra presenter layer, as a stateful mediator between controller and the proper graph view. It ends up replicating a lot of state that the view maintains anyway. We could probably make it significantly simpler by letting the graph view handle its state update more directly (not splitting into insert/update/remove, just batch "here is a list of all edges/nodes", deal with it). That would give us less opportunity to make the state inconsistent.

[kazcw]

We have planned this in a call: #6834