Eyes Above The Waves

I had another lovely Labour Day weekend away with my family at the beach. Naturally my thoughts turned to browser engines and again I'll take the liberty of recording them here...

One of the reasons Web layout is difficult is that you have to handle incremental layout efficiently. That means whenever your layout code accesses style data (e.g., GetStylePosition()->GetOffsets()), you need to think about what happens if 'left' changes. How do you guarantee that the layout will be updated?

In Gecko, this is mostly handled using "style change hints". When style changes, we compare the old and new styles and produce a set of bits summarizing what needs to be changed. One bit indicates that the frame (i.e. layout object) associated with the element needs to be reflowed. When a style change finds that bit set, we mark the associated frame "dirty" and eventually a reflow will happen for that frame.

The problem with this approach (and other similar approaches that we use for incremental layout and rendering) is that it decouples the code that consumes style data from the code that causes updates when that style data changes. This is fragile. For example, if you add new code that reads style data during layout, you'd better make sure that the style change hints are set correctly for when that style changes (and this code will be in an entirely different place), otherwise you will have subtle incremental layout bugs. It's also inflexible because it forces a strict pattern of dependencies; the layout of a frame can depend only on the style of its own element; if you want to look at the style of other elements, that's just not supported and you'll have to hack around it with more fragile code.

It would be helpful to have a technique that let us write only on the code that consumes style data, automatically ensuring that sufficient updates are issued when that data changes. Actually we would want this technique to extend beyond style data to other data sources too.

(What I'm asking for is really a form of reactive programming. I unfortunately don't know much about research in that area, except that it seems to be mostly conducted in specialized domains with exotic languages such as Haskell and Esterel, so probably not of much use to us.)

Of course the hard part is performance; we'd want a solution that's as least as efficient as what we currently do. For example, a solution that creates a pile of explicit one-way constraints, one per dependence, would be hopeless.

So here's one idea. Define an Updater class representing a no-arg function that will cause a computation (say layout of an element) to be re-executed in response to a change in underlying data. Make style data getters take an Updater parameter:

class Updater {
virtual void Update() = 0;
};
class nsIFrame {
...
nsMargin GetStylePositionOffsets(Updater* updater);
...
};

The contract is that when the offsets change, the updater will be invoked. I've moved style data access from a style object directly to the frame, because changes to the frame's style need to be tracked, not changes to the style context itself (it's basically immutable in Gecko). GetStylePositionOffsets will record a set of updaters that depend on the offsets of this frame. The caller will do something like:

class ReflowUpdater {
ReflowUpdater(nsIFrame* frame) : mFrame(frame) {}
void Update() { mFrame->PresShell()->FrameNeedsReflow(mFrame); }
nsIFrame* Frame();
nsIFrame* frame;
};
...
nsBlockFrame::Reflow(...) {
ReflowUpdater* updater = new ReflowUpdater(this);
...
nsMargin offsets = GetStylePositionOffsets(updater);
...
}

Now it's impossible, or at least hard, to depend on style data without the dependency being recorded.

This would of course be appallingly inefficient, so how can we make it efficient? We can adapt Gecko's current approach. Let's make a rule that changing certain style properties, such as the offsets, will always force the frame to be reflowed. In that case we don't need to record the dynamic dependency. If we're a little bit clever we can avoid almost all run-time overhead. First let's index all the style properties with integers and then have a table that tells us if we need to reflow when that property changes:

enum nsStylePropID { ..., POSITION_OFFSETS, ... };
const PRPackedBool styleChangeForcesReflow[];

We delay realization of dynamic Updater objects until they're really necessary:

class Updater {
class Realized {
virtual void Updater() = 0;
};
virtual Realized* Realize() = 0;
};

Then we refactor the style getters:

class nsIFrame {
...
template <class U> nsMargin GetStylePositionOffsets(const U& updater) {
TrackDependency(updater, POSITION_OFFSETS);
return GetStylePosition()->GetOffsets();
}
void TrackDependency(const Updater& updater, nsStylePropID style) {
... add updater->Realize() to dynamic dependency storage ...
}
void TrackDependency(const ReflowUpdater& updater, nsStylePropID style) {
if (styleChangeForcesReflow[style] && updater->Frame() == this)
return;
TrackDependency(static_cast<const Updater&>(updater), style);
}
...
};

Assuming the compiler can constant-fold the load of styleChangeForcesReflow[style], this becomes very low overhead. When properties are accessed in a scope where the compiler knows updater->Frame() == this, there is no overhead.

So what's gained? It's now much harder to screw up, and we support more complex dependencies (such as dynamically conditional dependencies, and dependence of one frame on another's style) along with static dependencies in a uniform API. The hard-coded dependencies are now just an optimization that we can easily meter and tune. Similar tricks can be used to track dependencies of painting and other activities.)

Other things you'd want to do when implementing this: support revocation of outstanding ReflowUpdater::Realized objects when a frame is actually reflowed; have the style change processing actually use the same styleChangeForcesReflow array to decide whether to reflow frames.

There is extra complexity in some places, so it's not a no-brainer. Just something to think about.