Avoid unnecessary structure updates in renderer

[f1ames]

Extracted from #4303:

Background: #4296.

How does selection conversion work?

1. MODEL: <p><$text bold=true>xx</text></p> + selection[bold=true]
2. VIEW:
   1. <p><b>xx</b></p>
   2. <p>[]<b>xx</b></p> (after position conversion)
   3. <p><B>[]</B><b>xx</b></p> (during writer.wrap( selection ) )
   4. <p><B>[]xx</B></p> (after attribute conversion; we're merging to the left, so a new element <B> is left)
3. RENDERING:
   * actual DOM: <p><b>xx</b></p>
   * expected DOM <p><B>XX</B></p> (we need to replace the entire <b> element; IDEA: don't replace <b> with <B> because they are similar!)

BUT... WHAT IF SOMETHING ELSE HAS CHANGED?

• actual DOM: <p><b>xx</b></p>
• expected DOM <p><B>XXY</B></p> (don't replace <b> with <B> but recursively go deeper to apply other possible changes, see Rendering deeper changes fails to update text nodes #4174)

Possible solution:

1. Make diff( actual, expected, sameNode ) skip elements which have the same names and attributes (see view.Element#isSimilar()) - it is described in more details in Improve 'sameNodes' comparator inside 'renderer._updateChildren' #4296.
2. As a result, we won't replace <b> with <B>, which means that the view to DOM mapping will be outdated – the new view <B> element will be mapped to the new DOM <B> element which is not in the tree (because the old DOM <b> element was left there). Which means that we should update bindings after skipping such replacements. How to do that? Perhaps we can simply and blindly set new mappings after rendering: purge existing bindings (in a limited scope), updatedDomElements.forEach( mapToUpdatedViewElement ).

Also intersting analysis of a specific case is available in https://github.com/ckeditor/ckeditor5-engine/issues/1342#issuecomment-373778804.

[f1ames]

Typing inside empty bold

To understand what's exactly happening during rendering and how renderer can be improved (so this case is analyzed from Renderer point of view), let's take a look how typing inside empty strong element is handled.

Starting with HTML like:

<p>Foo Bar<strong>FILLER{}</strong></p>

DomConverter has 3 mappings in this state (all elements have existing parent):

1. RootEditableElement:div (which points to main editable div element)
2. ContainerElement:p
3. AttributeElement:strong

Typing a:

1. Mutations are handled via MutationObserver and input._handleTextNodeInsertion method which executes input command.
2. The input command enques changes with WeekInsertDelta (with one InsertOperation inserting a text node).
3. Changes are then processed and converted via DowncastDispatcher which leads to writer.wrap handling the character inseriton.
4. The writer.wrap internally calls writer._wrapRange as it is handling non-collpased range.
   • View structure is now P > text:'Foo Bar', text:'a', Bold.
5. Then writer._wrapChildren is called which wraps newly inserted character inside new bold element.
   • View structure is now P > text:'Foo Bar', Bold > text:'a', Bold.
6. On the end of writer._wrapRange attributes are merged. Since there are two bold elements, the first one is left and the second one is removed.
   • View structure is now P > text:'Foo Bar', Bold > text:'a'.
7. DomConverted still holds same 3 mappings, however AttributeElement:strong has no parent at this point (as it was removed from view structure in the previous step).
8. Rendere has two elements marked to update now:
   • AttributeElement:strong - marked by mutations observer (this is the old element so one without parent).
   • ContainerElement:p - marked by view.
9. Since AttributeElement:strong (the old one available through DomConverter mappings) has no children and real DOM strong element has one text child, the text from DOM strong element is removed by renderer._updateChildren.
10. After that, Renderer handles ContainerElement:p children. Real DOM strong element is empty (text was removed in a previous step) and expected one (mapped from view) has text (well it doesn't matter here because diff checks strict element equality and those two are different objects). The new strong element is inserted and the old one removed (in such order). Also DomConverter mappings are updated here.

Of course there is much more happening during typing, but this steps are important for renderer.

To sum up, transformations performed on the real DOM by the renderer:

1. <p>Foo Bar<strong>a</strong></p> (initial DOM state after typing)
2. <p>Foo Bar<strong></strong></p> (a removed)
3. <p>Foo Bar<strong>a</strong><strong></strong></p> (strong > a inserted)
4. <p>Foo Bar<strong>a</strong></p> (empty strong removed, final DOM state)

---

In this particular case Renderer basically shouldn't update the DOM as typed character is already inserted by the browser. However, as Renderer relies strongly on mappings (DomConverter) which are changed by the Writer (not directly, just elements are manipulated) and gets outdated due to view structure manipulation, Renderer does similar thing to Writer- inserts new and removes old element. Probably Renderer could try match DOM <-> View structure smartly in such cases and introduce only minimal changes (or no changes at all) to the DOM structure and update elements mappings when needed.

[f1ames]

Typing on the end of bolded link

I took a look also on case described in https://github.com/ckeditor/ckeditor5-engine/issues/1342#issuecomment-373778804, but now it seems there is only a problem with bold rendering (same as described above) and:

in domconverter we are unable to map it from an existing view element so the new element is created and then all children are moved from exisitng DOM element to a newly created one. As the new element is not attached to the DOM all moved children also becomes detached.

no longer occurs. Looks like it was affected by some changes along the way. The renderer.markedChildren order is different (now is strong, a, i, p and earlier it was strong, p, a, i), but I checked with previous order and it also works fine.

But I found similar behaviour when typing on the end of bolded link:

1. <p>Foo <a><strong>Bar{}</strong></a></p> (initial DOM state before typing)
2. <p>Foo <strong><a>Bar</a>a</strong></p> (initial DOM state after typing - the attributes order swap is native Chrome behaviour)
3. <p>Foo </p> (after renderer updates a children)
4. <p>Foo <a><strong><a>Bara{}</a></strong></a></p> (after renderer updates p children)
5. <p>Foo <a><strong>Bara{}</strong></a></p> (after renderer updates strong children)

This case is different, due to the fact that browser natively changes DOM structure. Here I'm not sure if it would be possible to somehow simplify rendering cycles. The situation here probably could be improved by implementing inline filler improvement mentioned in #4303 (Fillers section, point 1).

The fact that whole strong is removed in step 3 is caused by the DOM structure changes in step 2. The DOM a element is replaced by the browser in step 2 with the new one so DomConverter now holds outdated mappings, still pointing to an old a element.
Now the actual DOM children for a is empty (as it was modified and detached by the browser) and expected DOM children is the outermost strong element.
The renderer._updateChildren moves whole strong into detached (old) a element and so it disappears from DOM.

I also checked Firefox and there it works perfectly. DOM structure is not modified, typed character is inserted on the end of bolded link so renderer does not have to perform any changes as expected and actual DOM is exactly the same.

[f1ames]

Bolding selected text

Another interesting case is bolding part of the text. Starting with HTML like:

<p>Foo {Bar}</p>

and pressing ctrl/cmd + b (or Bold button) will result in:

1. <p>Foo Bar</p> (initial state)
2. <p>Foo Foo Bar</p> (Foo text inserted)
3. <p>Foo <strong>Bar</strong> Foo Bar</p> (strong element inserted)
4. <p>Foo <strong>Bar</strong</p> (old Foo Bar text removed)

All 2 - 4 steps are happening inside renderer._updateChildren (executed for ContainerElement:p).

The renderer works fine here (and quite optimal) as it needs to insert new bolded element. But now imagine that during collaboration one user is composing something inside Foo (e.g. <p>Fo{}o Bar</p>) and another one is bolding Bar text as described above.

In such case reinserting whole text will break the composition. So the reasonable way would be inserting only strong element after existing text and then removing unnecessary part of the text. It is rather an edge case, however main reason this whole issue was brought up was to improve composition handling so I think we should at least think about such cases.

---

Extracted to ckeditor/ckeditor5-engine#1425.

[f1ames]

To sum up, as also previously mentioned by @Reinmar (in #4303), it looks like the renderer would need a smarter approach when comparing expected and actual DOM so instead of replacing elements which are not identical, smartly reuse them. The part of the solution should be improving elements diff:

1. Make diff( actual, expected, sameNode ) skip elements which have the same names and attributes (see view.Element#isSimilar()).

which will then require updating mappings:

2. As a result, we won't replace <b> with <B>, which means that the view to DOM mapping will be outdated – the new view <B> element will be mapped to the new DOM <B> element which is not in the tree (because the old DOM <b> element was left there). Which means that we should update bindings after skipping such replacements. How to do that? Perhaps we can simply and blindly set new mappings after rendering: purge existing bindngs (in a limited scope), updatedDomElements.forEach( mapToUpdatedViewElement ).

I have some doubts if above will be enough, but it is a good starting point. Such approach should solve most cases similar to the first one (https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-388809745) described above, when elements are unnecessary replaced even though only its children have changed.

Important thing to keep in mind is that such cases (that new element is already in the DOM) are usually triggered by external actions (like typing). All changes which first appear in model and view will always need some rerendering, but we should always keep DOM modification minimal. It is especially important during collaboration (and while composing during collaboration). So this solution should also cover these situations.

---

Cases similar to the third one (https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-389191257) are a little different. Here rendering is needed (as change is triggered internally), but optimizing the number of elements replaced by the renderer is important here:

In such case reinserting whole text will break the composition. So the reasonable way would be inserting only strong element after existing text and then removing unnecessary part of the text. It is rather an edge case, however main reason this whole issue was brought up was to improve composition handling so I think we should at least think about such cases.

At first glance it looks like it may not be solved by the general solution implemented for this issue (mainly because of mixed element / partial text updates) so alternatively we may extract it to a separate issue and handle it after this one.

---

For the cases similar to second one (https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-389155640 - DOM modified by the browser before rendering), which are more rare and occurs not in all browsers, number of DOM modifications could be optmized. It should be covered (at least partially) by the general approach solution.
If not we may take a closer look on this (but after implementing first inline filler improvement from #4303). Still those are rather edge cases, so unless they causes any significant issues I wouldn't treat it as high priority for now.

[f1ames]

One more thing which comes to my mind is to check if order of rerendering elements makes a difference. As renderer.markedChildren are not sorted anywhere the order strictly depends on the particular case. The assumption is that elements could be sorted by the type (Container, Attribute, etc), so from outermost to most nested (or the opposite).

For the two first cases (3rd one has only one marked element so it is skipped):

Typing inside empty bold

1. Default order ( AttributeElement:strong, ContainerElement:p ), actions:
   • updateChildren( strong ) - delete
   • updateChildren( p ) - equal, insert, delete
2. From outermost ( ContainerElement:p, AttributeElement:strong ):
   • updateChildren( p ) - equal, insert, delete

AttributeElement:strong is not processed in the second case as it was removed in the first step (rerendering ContainerElement:p), which means there is basically one DOM operation less.

Typing on the end of bolded link

1. Default (AttributeElement:a, ContainerElement:p, AttributeElement:strong):
   • updateChildren( a ) - insert
   • updateChildren( p ) - equal, insert
   • updateChildren( strong ) - delete, delete, insert
2. From innermost (AttributeElement:a, AttributeElement:strong, ContainerElement:p):
   • updateChildren( a ) - insert
   • updateChildren( strong ) - delete, delete, insert
   • updateChildren( p ) - equal, insert
3. From outermost (ContainerElement:p, AttributeElement:a, AttributeElement:strong):
   • updateChildren( p ) - equal, insert, delete
   • updateChildren( a ) - insert
   • updateChildren( strong ) - equal

Two first orders have exactly the same set of additions/removals, however when outermost element (here ContainerElement:p) is processed first (3rd case), the number, of operations decreases.

I think for cases which needs rendering, we should consider sorting elements as it may decrease the number of operations performed on DOM structure.

[f1ames]

I basically built a PoC based on the above assumptions containing two main mechanism:

• Sorting renderer.markedChildren by the type so more general/outermost elements will be processed first.
• Updated diff comparator so that it treats elements with same tag name as same elements:
  • For such elements bindings in DomConverter are updated.
  • Also such elements are marked to be updated (renderer.markedChildren) so its direct children are also processed.

This works fine for typing inside empty bold (https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-388809745) or when the whole view structure is replaced with the same structure (mappings are refreshed properly and DOM stays untouched).

However, there is one case which makes this approach invalid. Consider HTML like:

<p>Foo1</p>
<p>Bar2</p>
<p>Baz3</p>

Now, second paragraph (<p>Bar2</p>) is removed, resulting in:

<p>Foo1</p>
<p>Baz3</p>

Previously diff (when comparing expected and actual elements) will return following set of operations: [ equal, delete, equal ], which means that second paragraph was removed (correct). However, when treating nodes with the same tag name as equal, diff will return [ equal, equal, delete ] which incorrectly states that third paragraph was removed. This is general problem for this approach and will always happen for groups of three or more nodes of the same type.

---

I see two solutions with which we may tweak the current approach:

1. Adjust the comparator function so diff will properly handle above issue.

TBH, I'm not sure if and how it can be done in a reasonable way since adding more and more logic to comparator will make it quite complex and subject to different edge cases.

2. Leave diff and comparator as it is and improve renderer._updateChildren.

We would like to prevent rerendering of elements which does not have to be rerendered. Such situation may only occur if diff returns set of operations/actions containing both insert and delete. Sets like [ equal, insert ], [ equal, delete ], [ insert ], etc can be skipped as this means elements are added or removed. Only both insert and delete means something needs to be replaced. Following this logic we could post process diff result, detecting replace situations based on operations pairs. This should give the same result as modified comparator but also properly handle other cases (like one with paragraphs mentioned above). And then proceed with mappings rebinding and updating renderer.markedChildren same as in PoC.

[f1ames]

We have decided to go with diff result post processing to try to detect DOM elements which can be reused instead of being replaced. However...

There are some cases in which it is not possible to reuse some existing DOM elements without moving them based on current diff results. Consider HTML:

<p>1 <b>2</b> <i>3</i> <a>4</a><p>

in short the p direct children structure can be described as:

t1 B t2 I t2 A  // This is actual DOM structure.

where B, I, T are attribute elements and tx are text nodes (notice that t2 is used twice as both text nodes have the same content/data so are treated as equal).

Now <b>2</b> (with following space) gets removed leaving <p>1 <i>3</i> <a>4</a><p> which is

t1 I t2 A // This is expected DOM structure.

Diffing actual and expected DOM will result in the following set of operation: equal, delete, insert, equal, delete, delete, delete, insert. This means:

operation -> actual DOM structure

1. equal:t1 -> t1 B t2 I t2 A
2. delete:B -> t1 t2 I t2 A
3. insert:I -> t1 [I] t2 I t2 A

Step 3 is the problematic one here. The structure is t1 t2 I t2 A and now we need to insert I between t1 and t2. It is not possible to reuse actual I without moving it (and by moving it we probably lost benefits of not rerendering it - however I haven't yet checked if composition breaks in such cases).
The fact that first t2 is used (instead of second one which in this case could help) is the result of how diff works. But I suppose it doesn't matter that much in general, if diff would work in the opposite way (so marking last not first element as equal) we would have exactly same issue in the similar, reversed structure.

For the first solution I suggest skipping such cases (and then see how and if they cause any issues and fix accordingly). This basically means that diff result post processing (described in https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-390615612) will try to match insert-delete pairs only between equal actions and not in the whole actions set (AFAIR @Reinmar mentioned something similar when we talked F2F).

[f1ames]

TL;DR The proposed solution refreshes DomConverter bindings at the beginning of renderer.render() by diffing (using our standard diff() function) groups in actual vs expected DOM structures. Based on the refreshed bindings renderer._updateChildren() will simply reuse DOM elements instead of replacing them with identical ones. Also due to the refreshed bindings it is possible now to correctly find the selection position (it was broken earlier due to outdated mappings in some cases).

---

There are a few ideas and reasons behind the way this solution was implemented, most of them already described in this issue, but I wanted to sum it up. As mentioned in the previous comment we decided to try with post processing the diff results (which finds elements which were replaced in the view, but do not have to be replaced in the DOM - just reused). There are three main concepts:

1. sorting renderer.markedChildren,
2. refreshing domConverter mappings,
3. post processing diff results.

sorting renderer.markedChildren

The current state is that renderer renders elements in the order they were marked to be rendered. As it is based on different events which order is not guaranteed to be always the same (especially in different browsers), the order is quite random. So we do not have control over it. Since with this improvement we would like to reuse the DOM nodes which do not have to be reinserted it makes more sense to start from the outermost elements (it also decreases number of renders in some cases see https://github.com/ckeditor/ckeditor5-engine/issues/1417#issuecomment-389503934).

refreshing domConverter mappings

The first approach was to just refresh the mappings during rendering (so in renderer._updateChildren), however as @Reinmar concluded, early mappings refresh will solve some inline filler issues so we have moved this whole logic on the beginning of the render function. This allows other mechanisms (like the selection position mapping) to also benefit from up-to-date mappings.

post processing diff results

This is actually the main part of the refreshing domConverter mappings process. The diff() function returns an array of actions (equal, insert, delete) which is then used to transform actual DOM into expected one.

During the course of action we tried two approaches out of which the first one failed:

1. Adjust the sameNodes() function so nodes with the same tag name are treated as equal.

This didn't work in some cases. Considering the following HTML:

<p>1</p>
<p>2</p> // this node gets modified to <p>4</p>
<p>3</p>

The original diff() function returns [ equal, insert, delete, equal ] (so the 2nd p is rerendered). The adjusted diff would return [ equal, equal, insert, delete ] which means 3rd p is reinserted which doesn't make much sense and breaks the rendering.

2. Manually post-process diff() result based on insert/delete action pairs.

In this approach we try to identify pairs of insert/delete actions which were returned by the diff() function in situations when a node was replaced by a similar node. For example, the diff() result like [ insert, delete, equal, insert, insert, delete ] contains two insert/delete groups which will be processed independently - 1st - insert, delete (starting on index 0) and 2nd - insert, insert, delete (starting on index 3). This is a valid assumption, however the crucial part is how elements in this groups are compared.

The naive approach is to simply match all inserts with all deletes in an action group and find similar nodes. Then to replace insert/delete action with e.g. a replace action which means that these elements mappings will be updated. It works, but not for all cases, consider the following example:

#	Actual DOM	Expected DOM	diff() result	postprocessed expected result
1	1<b>2</b>	3<B>4</B>	insert, insert, delete, delete	insert, delete, replace
2	1<b>2</b>	<B>4</B>3	insert, insert, delete, delete	delete, replace, insert
3	<b>2</b>1	<B>4</B>3	insert, insert, delete, delete	replace, insert, delete
4	<b>2</b>1	3<B>4</B>	insert, insert, delete, delete	insert, replace, delete

In the Actual DOM and Expected DOM columns above <b> and <B> means that it is a different element instance. Actions in bold (in 4th and 5th columns) are those which were identified as the ones replacing the <b> element with a similar one (same tag name so it should be reused instead).

The naive approach performs correctly for cases like 1st one (from the table above) where postprocessed expected result and initial diff() result has the same order of insert/delete actions (apart from the ones replaced by the replace action):

insert, insert, delete, delete

will be transformed into:

insert, delete, replace

However, if postprocessed expected result and initial diff() result order of actions is different like in 2nd case from the table above where:

insert, insert, delete, delete

should be transformed into:

delete, replace, insert

the transformation cannot be simply done by iteratively checking all insert/delete pairs for a matching element and requires running a full diff algorithm. So the post-processing runs the diff() function which compares parts of expected and actual DOM corresponding to a given insert/delete group. Elements with the same tag name (for example <b> and <B> from the table above) are treated by the diff() function as replaced ones, resulting in correct expected result, same as shown in table above.

[scofalik]

So I read it and tried to understand as much as I could on the first run :P. I think it is promising that you ended up with a double-diffing solution. I had similar kind of a problem in model.Differ class, where I also wanted to diff nodes, but in model. The trick there was to differentiate which nodes only changed attributes and which nodes were removed / inserted / did not change. At one point I had a very similar solution - I run two diffs, one of them was getting me insert/delete chains. Then I extracted those insert/delete chains and run the diff second time (with a different diffing function) to see what really changed.

At the end, we have now a different solution in Differ (not applicable here) but I am positive about your solution.

[Reinmar]

So the whole postprocessing basically boils down to running diff() again on insert/delete groups with assumption that same nodes are the ones with the same tag name. And this produces expected results.

TBH, I don't understand the last 3 paragraphs of your comment. I guess you're comparing two approaches but you haven't clearly stated that and how does the first one fails exactly. Could you extend that bit because I feel someone may need to get back to this one day.

[f1ames]

@Reinmar I modified the description you mentioned, trying to describe more precisely which cases doesn't work, I hope it is easier to understand now.