Improving selection in CSS Regions

I would like to introduce in this post the main problems we have detected in the Selection implementation of two of the most important web engines, such as Blink and WebKit. I’ve already described some of these issues, particularly for CSSRegions, but I’ll go a bit further now analyzing them and also introducing one of the proposal we have been working on at Igalia s part of the collaboration we have with Adobe.

Selection is a DOM Tree matter

At Igalia, we have been investigating how to adapt the selection to the new layout models which provide more complex ways of visualizing the content defined in the DOM Tree. Let’s consider the following basic example using CSSRegions layout:

base-case
Figure 1: base case

In the last post about this issue we have identified 4 main problems with selection in CSSRegions:

  • Selection direction
  • Highlighting and content mismatch
  • Incorrect block gaps filling
  • Clear the selection

I’ll describe some examples where these issues are present, where are the root causes and how they can be solved or, at least, improved. I’ll try as well to explain how the Selection works, starting from the mouse events the end user generates to perform a new selection, how those are mapped into a DOM Tree range and finally, how the rendering process produces the highlighting of the selected elements.

example-a1
Figure 2: Highlighting and selected content mismatch

I’ll use this first example (Figure 2) to briefly describe how the Selection is implemented and how all the involved components interact to generate both, the selected DOM Range and the corresponding highlighting by the RenderTree. Obviously the end user selects contents from the Visualized elements, in this case the content of two regular blocks (no regions involved). The mouse events are translated to VisiblePosition instances (Start and End)  in the DOM Tree using the positionForPoint method. Such VisiblePositions are then mapped into the corresponding RenderObjects in the Render Tree; these objects are the ones used to traverse the tree in the RenderView::setSelection method and mark the appropriated elements with one of the following flags: SelectionNone, SelectionStart, SelectionInside, SelectionEnd, SelectionBoth. These flags are also very important in the block gaps filling algorithm, implemented basically in the RenderBlock::selectionGaps method.

The algorithm implemented in the RenderVieww::setSelection method can be described, very simplified, as the following steps:

  • gathering information (RenderSelectionInfo and RenderblockSelectionInfo) of the old selection.
  • clearing the old selection (basically mark all the elements as SelectionNone)
  • updating the flags of the elements of the new selection.
  • gathering information of the new selection.
  • repainting old objects which might have changed.
  • painting the new selected objects.
  • repainting the old blocks which might have changed.
  • painting the new selected blocks.

The algorithm traverses the RenderTree, from the Start to the End using the RenderObject::nextInPreOrder function. Here is where the clear operation issues can appear. If not all objects can be reached by the pre-order traversal, the clear operation does not work properly. That’s why we introduced a way to traverse back the Tree (r155058) looking for elements which can be unreachable. One of the causes of this issue is the selection direction change.

This first example shows the highlighting and content mismatch issue, since the DOM Range considers the source (flow-into) element, while is not highlighted by the RenderTree.

The next example considers now selection from both regions and regular blocks and introduces also an interesting Selection topic: selection direction.

example-b1
Figure 3: Incorrect block gaps filling

As you can see in the diagram Figure 3, the user selected content upwards. In most of the cases the selection direction is not used at all, so Start  must be always above the End VisiblePosition in the DOM Tree. The VisibleSelection ensures that, but in this case, because of how the Source (flow-into) is defined according to the CSSRegions specification and where it was placed in the HTML code, the original Start and End position are not flipped. We will talk more about this in the next example. However,  the RenderObject associated to a DOM element with a flow-into property is located in the in the render tree under the RenderFlowThread object, which itself is placed at the end of normal render tree, thus causing the start render object to be below the end render object. This fact causes the highlighted content to be exactly the opposite to what the user actually selected.

This example illustrates also the issue of incorrect block gaps filling, since the element with the id content-1 is considered a block gap to be filled. This happens because of the changes introduced in the already mentioned revision  r155058  since the element with id content-2 and the body are flagged as SelectionEnd, the intermediate elements are considered as block gaps to be filled.

At this point is quite clear that the way the Render Tree is traversed is very important to produce a coherent selection rendering; notice that in this case, highlight and selected content match perfectly. The idea of using the Region DIV as container of the Source DIV content portion, which is rendered inside such region, looks like a promising approach. The next example will go further into this idea.

example-c1
Figure 4: Selection direction

In this example (Figure 4) the Start and End VisiblePosition instance have to be flipped by the generated VisibleSelection, since the DIV with the id content-1 is above the original Start element defined by the end user. By flipping both positions it makes the corresponding Start and End RenderObject instances to be consistent, that’s why there is no selection direction issue in this case. However, because of the position of the End element as child of the RenderFlowThread, the RenderElement with the id content-2  is selected, which, while being seamless from the user experience point of view, it does not match the selected content retrieved from the DOM Range.

The solution: Regions as containers

At this point is clear that the selection direction issues are one of the most important source of problems for the Selection with CSSRegions. The current algprithms, RenderView::setselection and RenderBlock::selectionGaps, require to traverse the RenderTree downwards from start to end. In fact, this is specially important for the block gaps filling algorithm.

It’s important to notice that the divergence of the DOM and Render trees when using CSSRegions comes from how these two concepts, the flow-into DOM element and the RenderFlowThread object, are managed and placed in each trees. Why not just using the region elements for the selection algorithms and considering both flow-into and RFT as “meta-elements” where the selected content is extracted from ?

Considering the steps defined previously for the selection algorithm the regions as containers approach could be described as follows:

  • Case 1: Start and Stop elements, either both or none, are children of the RenderFlowThread.
    • The current RenderView::setSelection algorithm works fine.
  • Case 2: Only Start is child of the RenderFlowThread.
    • First, determining the RenderElements range [RegionStart, RegionEnd] in the RenderFlowThread associated to the RenderRegion the Start element is rendered by.
    • Then, applying the current algorithm to the range of elements [Start, RegionEnd]
    • Finally, applying the current algorithm from the NextInPreOrder element of the RenderRegion until the Stop, as usual.
  • Case 3: Only Stop is child of the RenderFlowThread.
    • First, applying the current algorithm from the Start element to the RenderRegion the Stop element is rendered by.
    • Then, determining the RenderElements range [RegionStart, RegionEnd] in the RenderFlowThread associated to the RenderRegion the Stop element is rendered by.
    • Finally, applying the current algorithm to the range of elements [RegionStart, Stop]

Determining the selection direction, at VisibleSelection, is also affected by the structure of the RenderTree; even that the editing module in both WebKit and Blink is also using rendering info for certain operations, this is perhaps one of the weakest points of this approach. Let’s use one of the examples defined before to illustrate this situation.

example-b2
Figure 5: Block gaps filling issues solved

While traversing the RenderTree, once a RenderRegion is reached its corresponding range of RenderObjects is determined in the RenderFlowThread. The entire range will be traversed for the blocks flagged as SelectionInside. For the ones flagged as SelectionStart or SelectionEnd, the steps previously defined are applied.

The key of this new approach is that traversing is always downwards, from the Start to the End, which solves also the block gaps related issues.

Let’s considering now a more complex example (Figure 6), with several regions between a number of regular blocks. selection is more natural with this approach, coherent with what the user expects and also matching the DOM Tree range for most of the cases. This is, however, the biggest drawback of this approach, since it does not follow completely the Editing/Selection specs. I’ll talk  more about this in the last lines of this post.

example-d
Figure 6: Selection direction issues solved

The following video showcase our proposal on the WebKit MiniBrowser testing application using a real HTML example based on the Figure 6 diagram.

Even though selection is more natural an coherent, as I already mentioned, it does not follow completely the Editing/Selection specs. As I stated at the beginning of this post, selection is a DOM matter, defined by a Range of elements in the DOM Tree. This very simple case (Figure 7) is enough to describe this issue:

example-a
Figure 7: Regions as containers NON specs compliant

The regions as containers approach does not considers the Source (flow-into) elements as actual DOM elements, so they will never be part of the selection. This breaks the Editing/Selection specification, since those are regular DOM elements as they are defined in the CSS Region standard. This approach was our first try and perhaps too ambitious, providing a good user experience on selection with CSSRegions and specs compliant at the same time. Even that it was a good experience we can conclude that the problem is too complex and it requires a different strategy.

We had the opportunity to introduce and discuss our proposal during the last WebKitGtk+ Hackfest, where Rego, Mihnea and me had the chance to work hand in hand, carefully analyzing and digesting this proposal. Even that we finally discard it, we were able to design other approaches which some of them are really promising. Rego will introduce some of them shortly in a blog post. Hence, can’t end this post without thanking to Igalia and the GNOME Foundation for sponsoring such a productive and useful hackfest.

CSS Regions and Selection

Back in early June, Adobe and Igalia announced a collaboration to work on the CSS Regions and CSS Shapes W3C standards. Our first challenge has been to improve the Selection use cases when using complex layout models, like CSS Regions.

The CSS Regions model allows content to flow across multiple areas called Regions. This new approach offers web content designers a way to build richer and more complex layouts, mapping content with specific visual areas of a document. Defining different Flow Threads with multiple Regions, associating them to specific content, and applying different styles to a set of Regions is very powerful in terms of design and user experience. If you are interested, here you can find some examples of what is possible with CSS Regions.

But having this flexibility in web design requires overcoming quite a few technical challenges. The current implementation of CSS Regions in WebKit changes the way the Render Tree is created from the DOM Tree. This poses the challenge of making selection work with regions since selection is DOM based. Given its importance and frequent use, improving the interaction of selection and CSS Regions has been the main goal of our collaboration.

The W3C selection specification, which has not been updated since the last year, does not address the complexities introduced by new layout modules, like CSS Regions, CSS FlexBox and CSS Grid Layout module . We found out very quickly that selection had many issues, with respect to both visual appearance and selected content. We have created a tests suite to evaluate the different use cases of selection with CSS Regions.

test2
Selected content does not match the highlighted area.

test1
Selection direction issues

Let’s start with a very simple description of the concept of Selection Direction, which consist of the following points:

  • The WebCore::VisibleSelection class has two attributes called base and extent declared as dom::Position instances
  • Such positions refer respectively to the anchor and focus nodes in the DOM Tree.
  • Additionally, WebCore::VisibleSelection has two dom:Position attributes, start and end, which are used later during the rendering phase

Once the base and extent fields are set when instantiating a new VisibleSelection class, some adjustments and checks are performed to validate the selection. One of those checks is whether base position is before extent in the DOM Tree. Based on the result of this check, the start and end attributes will be set to either base or extent respectively.

In the first test, the selected content includes the entire region block, even when it was not selected by the user. The cause, as we will see in later, derives from the position of the source block in the DOM Tree, which in this case is defined between the two regular blocks.

The second example shows some selection direction related issues; in this case, what the user selected is precisely the content between the two highlighted areas. The problem here is that the base node of the original selection is below the extent node in the DOM Tree, so they are swapped in the selection logic. In addition, the CSS Regions implementation builds the Render Tree in a way that the source content defined by a RenderNamedFlowThread block is positioned below where it was defined in the DOM Tree. The consequence of this is that the start node is below the end node, so the highlighted area starts in the region block and continues from the root element (usually the body) until reaching the end node.

Our first approach was trying to provide a better user experience during selection with CSS Regions. We thought that adding multi-range capabilities to the DOM Selection API was the best way to go and we provided a patch. However, this approach was rejected by some Apple reviewers because multi-range selection introduces many problems, such as those detailed in the selection specification.

We have opened the debate again on the mailing list, though, because we think there might be some advantages to this approach, even without modifying the selection API. For instance, being able to handle independent Ranges and compose the expected selection will provide the flexibility needed to implement complex use cases. But, after some discussion with some of the Adobe Web Platform contributors, we have decided to focus on improving the selection following the current specification. While we feel this approach may lead to a non-optimal user experience for certain use cases, we expect implementing it will help us discover the problems inherent in the current selection specification. We have also been discussing these issues with some reviewers from Apple, Ryosuke Niwa and David Hyatt, and looking for alternatives to the multi-range approach.

We have posted additional patches, one to improve the selection behavior and another to revert the current limitation of selections related to including content from different Flow Threads. We think that this approach provides better integration of CSS Regions with HTML documents. Plus, it will allow us to properly evaluate the performance issues of selection with CSS Regions.

The other challenges we faced during this collaboration include:

  • changing how the selection rendering traverses the Render Tree in order to deal with the special RenderFlowThread blocks
  • adjusting the block gaps filling algorithm
  • clearing the selection
  • selection direction issues derived from the Render Tree and DOM Tree divergence

We detected a number of other issues,  such as how LayoutPoints are positioned in the DOM Tree when pointing to Region blocks, leading to an incorrect Selection extent node.  We are confident that we will ultimately have a fully-compliant selection specification implementation for CSS Regions, but the improvements using this approach are limited. Even after solving all the issues we have detected so far, selection might still seem weird and buggy from an end user perspective. Thus we think that the final solution, one which will provide the user with a more consistent experience, will be to complement the selection specification to consider not only the DOM Tree, but also how the Render Tree is built by the Layout Model.

Geolocation unit tests for WebKit using GeoClue

As you probably know, the WebKit project is focused on the implementation of  an open source web browser engine. Support for the W3C Geolocation API is available since 2008 and GeoClue was the selected choice for the WebKitGtk+ port implementation.

Since Igalia is very interested on the WebKit project, I’ve got the chance to devote some time  to explore the integration of GeoClue in WebKit and learning more about this project, which will be the main bet for our Innovation area. It’s really great to leave aside for a while my regular tasks and continue learning and deeper analyzing such an interesting project.

The current state of the GeoClue based implementation it’s somehow preliminary. Basic location services are provided by GeoClue, but the integration with the WebKit core is not fully covered and unit tests are most of them disabled at this moment.

So, I thought it would be a good challenge to complete the implementation and check the unit tests cases to see if I’m able to fix at least one of them. I think it would be a good start 🙂

There are 24 unit test cases defined and only 4 of them are enabled at this moment and they are basically just testing if GeoClue is installed and configured, or checking the input arguments type. I’ve thought that working on the enabled.html test would be interesting, because is very simple and it probes the GeoClue API is correctly used and it works as expected.

description(“Tests Geolocation success callback using the mock service.”);

var mockLatitude = 51.478;
var mockLongitude = -0.166;
var mockAccuracy = 100;

if (window.layoutTestController) {
layoutTestController.setGeolocationPermission(true);
layoutTestController.setMockGeolocationPosition(mockLatitude,
mockLongitude,
mockAccuracy);
} else
debug(‘This test can not be run without the LayoutTestController’);

var position;
navigator.geolocation.getCurrentPosition(function(p) {
position = p;
shouldBe(‘position.coords.latitude’, ‘mockLatitude’);
shouldBe(‘position.coords.longitude’, ‘mockLongitude’);
shouldBe(‘position.coords.accuracy’, ‘mockAccuracy’);
finishJSTest();
}, function(e) {
testFailed(‘Error callback invoked unexpectedly’);
finishJSTest();
});

window.jsTestIsAsync = true;
window.successfullyParsed = true;

So, the fist issue to face is the implementation of the setMockGeolocationPosition method, which is unimplemented (see bug 28624) in the Gtk port (LayoutTestControllerGtk.cpp). This method should set the mock position to be retrieved by the Geolocation API method.

The problem is that GeoClue has not such method, at least, as API method. Depending on the location provider selected its possible to establish  a dummy position through the DBus API.

Another problem is that the Master provider, the one used for the WebKitGtk+ port to implement the Geolocation API, has not a very good provider selection algorithm so one of the web services based provider is selected, causing the unit test to become stalled, waiting for a web response which never come.

Hence, it seemed that the work should start at the GeoClue side, talking to the community to look for the proper approach, discussing about the patches I’ve implemented and eventually push those patches to be committed. After some weeks of hard work, the patches are already at the GeoClue bugzilla; lets see how the discussion evolves.

Meanwhile, I started the WebKit tasks implementing the mock operation. The first approach, perhaps the easiest one, would be to directly use the GeoClue API for setting the mock position. using my own GeoClue branch with my patches applied, I was able to correctly execute the success.html unit test. The patch was not too complex, but it required a new dependency in the WebKitTools module, in order to use the GeoClue API from the LayoutTestControllerGtk component.

void LayoutTestController::setMockGeolocationPosition(double latitude, double longitude, double accuracy)
{
// FIXME: Implement for Geolocation layout tests.
// See https://bugs.webkit.org/show_bug.cgi?id=28264.
GeocluePosition *pos = NULL;
const char *service = “org.freedesktop.Geoclue.Providers.Manual”;
const char *path = “/org/freedesktop/Geoclue/Providers/Manual”;
const char *iface = “org.freedesktop.Geoclue.Manual”;
GError *error = NULL;

GeoclueMaster* master = geoclue_master_get_default();
GeoclueMasterClient* client = geoclue_master_create_client(master, 0, 0);
if (geoclue_master_client_set_requirements(client, GEOCLUE_ACCURACY_LEVEL_LOCALITY, 0,
false, GEOCLUE_RESOURCE_ALL, &error)) {

pos = geoclue_master_client_create_iface_position (client, service, path, iface, &error);
geoclue_position_set_position (pos, accuracy, longitude, latitude, 0, &error);
g_object_unref (pos);
}

g_object_unref(master);
}

In spite of being functionally correct, after talking with some of the WebKitGtk+ developers, it seems that might be not the best approach to follow. The Chromium port has solved the problem by implementing its own Location Cache system inside the WebKit code, delegating on the specific Geolocation tools only when no valid location is available. The mock method just set the mock position into this cache, so the unit tests don’t need any external dependency.

Next steps would be talking to the WebkitGtk+ team to evaluate my proposal and figuring out the best approach to follow, probably something similar to what Chromium have implemented.