Approach to fix selection with CSS Regions (WebKitGTK+ hackfest late wrap-up)
As you probably know if you have been following this blog, we’ve been working for a while in selection interaction with CSS Regions inside a collaboration between Adobe and Igalia. First of all, let’s contextualize this post.
WebKitGTK+ Hackfest 2013
Back in December it was organized the 5th WebKitGTK+ Hackfest at Igalia offices in A Coruña (Spain). During that week Mihnea, Javi and myself were working together trying to find a good solution for selection in CSS Regions.
As Javi has already explained in his last post, our initial implementation to fix the issues of selection in documents with CSS Regions was discarded due to several problems.
At that point, the main goal was to find an approach that will make selection in CSS Regions spec compliant and might be validated by the editing experts in order to get it integrated upstream.
Current problem
According to editing spec selection is DOM based. If you select some stuff in a page with CSS Regions, the content is retrieved properly from the DOM tree. In a selection retrieved content and highlighted content should match. However, this is not happening with CSS Regions.
CSS Regions introduces a divergence between DOM and render trees. In CSS Regions some nodes of the DOM tree (called content nodes, the ones that have -flow-into property) are moved from the “regular” render tree (under RenderHTML) to the RenderFlowThread (a sibling of RenderHTML).
During the selection we have a start and end positions in the DOM tree that are mapped into positions in the render tree. Selection algorithms traverse the render tree from start to end, which has some issues with CSS Regions in several situations. Let’s use the following diagram to explain some of them.
Diagram showing DOM and render trees together with visual display of a CSS Regions example
Let’s imagine we perform a selection from content-1 to content-2.
- DOM selection: Returns the following nodes: content-1, source-1 and content-2.
- Render tree selection: We start and end the selection outside the flow thread. However, source-1 which is selected in the DOM tree is under the RenderFlowThread and it’s not processed by the algorithm while traversing the render tree from start to end. Thus, it’s not highlighted.
- Issue: source-1 is not highlighted.
Example of current and expected behaviors for selection in CSS Regions
Ideas
After some discussion and lots of diagrams representing the DOM and render trees on paper, we came up with 2 ideas:
- Subtrees approach: The idea is to split the render tree in subtrees calculating the start and end positions of the selection for each of them. Then it will use current selection methods to perform the selection inside each subtree.
- DOM order approach: In this case we would use DOM order to traverse the render tree. Also when looking for the container of a node, we will follow the DOM tree too if it’s a content node.
Handwritten diagrams representing DOM and render trees
During the hackfest we implemented 2 quick prototypes to check if previous ideas would solve the problems. In both cases results were satisfactory.
However, DOM order idea seems more complicated as some elements in the DOM tree might not be present in the render tree. On top of that, we should review carefully the different methods involved in the selection and modify how they traverse the tree (or look for their container) in some cases. This would imply several changes in the more complex parts of the selection code.
On a first sight the subtrees approach is more promising as it looks simpler and cleaner. After talking with Ryosuke Niwa and David Hyatt on IRC it was confirmed as the preferred approach and likely valid to be integrated into WebKit. In addition, it seems that more performance optimizations could be done with this approach. So, let’s explain deeply how this solution would work.
Subtrees approach
All selection algorithms are thought to work in a single render tree under RenderView. Actually, RenderHTML is the top element of the render tree where selection state is set (see RenderBoxModelObject::setSelectionState()).
Inside this render tree the start object is always before than the end object. But that’s not always true in the case of CSS Regions, as you can see in the diagram above. For example, if you start selection inside the source-1 element (depending on its position inside the DOM tree) start position could be under the RenderFlowThread and end under the RenderHTML.
So, this solution will split the render tree in subtrees where the root objects would be:
- On one hand, the RenderHTML (for the “regular” render tree).
- On the other hand, all the RenderFlowThreads (there will be 1 per flow thread in the page).
Then the total number of subtrees we’ll be 1 (the RenderHTML subtree) + number of flow threads.
For each subtree we’ll calculate the start and end positions (start will be always before end). And then we’ll call selection algorithms for each subtree using that positions.
In the previous example we’ll have 2 subtrees:
- RenderHTML subtree.
- RenderFlowThread (flow-1) subtree.
Let’s calculate start and end positions for each subtree taking into account the example above:
- RenderHTML subtree:
- start: content-1, offset: start offset set by user’s selection.
- end: content-2, offset: end offset set by user’s selection.
- RenderFlowThread (flow-1) subtree:
- start: source-1, offset: start of source-1 object.
- end: source-1, offset: end of source-1 object.
Subtrees approach DOM and render trees selection example
Using these subtrees RenderView::setSelection() method will be called for each of them. Subtree’s root object will need to store information about start and end positions (together with their offsets).
Conclusion
This is an important milestone for the work we have been doing lately, and it allows us to have a clear path to make progress on this field and eventually fixing the selection in CSS Regions.
Of course, there’s still quite a lot of work to do. We’ll improve current prototype to convert it in a real patch to be uploaded at WebKit’s bugzilla and got it integrated after the review iterations. Then, as usual, we’ll try to get integrated into Blink too.
Finally, thanks to The GNOME Foundation and Igalia for sponsoring the WebKitGTK+ Hackfest, and also to Mihnea for attending and helping us to move this topic forward sharing his experience on the CSS Regions standard.
Exciting times ahead, stay tuned! Happy hacking. :-)
