Incremental flow tree construction

How render object construction works in WebKit

There are three cases to consider:

• Adding a DOM node—A RenderObject is created for the DOM node in question and then the addChild method is called on the RenderObject belonging to the DOM node's parent. addChild is a virtual method and will perform different fixups depending on its type. For example, RenderBlocks create anonymous boxes if necessary to accommodate the new RenderObject child.

• Removing a DOM node—As above, the RenderObject belonging to the former DOM node's parent is retrieved and removeChild is called on it to remove the child's render object. removeChild is a virtual method and does different things depending on the class's type. For instance, RenderBlock removes anonymous boxes as necessary.

• Modifying the style of a DOM node—The RenderObject corresponding to the DOM node is retrieved and the old and new styles are compared to determine a StyleDifference. Then styleDidChange is called on the DOM node. This floods m_needsLayout bits (and possibly other bits) around the tree. m_needsLayout seems to be roughly equivalent to "needs the assign-heights pass to run". Constraint solving passes are skipped as necessary if the appropriate bits are set.

Possible algorithm for Servo

Adding and removing nodes

Observe that what WebKit does works out to a bottom-up traversal: it creates render objects and then stitches them in recursively by calling appendChild. This suggests that an analogous parallel bottom-up computation is possible. Suppose that we have a data type FlowManipulation which looks as follows:

enum FlowManipulation {
    AddFlows([Flow]),
    AddBoxes([Box]),
    RemoveFlows([Flow]),
    RemoveBoxes([Box]),
}

Then for each node we have a kernel function with this type:

• Input: A DOM node, associated computed style, and possibly FlowManipulations for kids.
• Output: A FlowManipulation instance.

The algorithm for this kernel function is as follows:

1. Use the display, position, and content properties of the computed style, as well as DOM node properties, to create the appropriate flows or render boxes (if any).

2. If any flows are to be generated, create a FlowManipulation describing them.

3. Perform flow manipulations for kids as necessary: for example, if this is a div node that created a BlockFlow, then AddFlows operations will create children of this BlockFlow. Each type of flow will have a different implementation for the various methods: for example, for BlockFlow instances, AddFlows or AddBoxes methods can create anonymous blocks. It is important that FlowManipulations be executed in the correct order, and in the right place in the tree: for this, the DOM node that each member of the AddFlows or AddBoxes instruction corresponds to needs to be consulted.

We run this kernel function on each node that was added or removed until no more flow manipulations occur. The root node must always produce an AddFlows manipulation with a single root element.

Modifying nodes

This can just be done sequentially with markDirty style operations, since it's not likely to be high in the profile. (It isn't in Gecko.) We should be able to fairly easily parallelize if we have to. Constraint solving passes will ignore nodes that are not dirty.