Computational complexity of cascading stylesheets?

I am looking for any papers that analyze the design of cascading stylesheets with respect to bounded times. I could derive this myself, but it would be nice to have a peer reviewed authority. It would also be cool if anyone ever bothered to do this for Hakon Wum-Lie's original CHSS (Cascading HTML Style Sheets) and Bert Bos's original SSP (Stream-based Style Sheet Proposal) prior to them being merged into CSS 1.0. Also, Dynamic Properties that were in Internet Explorer from 5.0 through 7.0, but deprecated in 8.0.

The only thing I found so far was a webpage: CSS, selectors and computational complexity. However, this doesn't communicate the complexity on how selectors place solving constraints on the layout engine to update each widget's CSS box model.

I'm also interested in knowing if anybody has done anything to model compatibilities across browsers. All I found was this (mindblowing) Comparison of layout engines and their support for CSS.

I don't think anyone has actually done anything to formally investigate the most widely used DSL in the world and the affect it has on clockcycles as well as programmer man-hours...


Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I'm not sure which to write

I'm not sure which to write up for my master's thesis: either my work on what you just discussed or my JavaScript security stuff ;-)

CSS really has 3-4 computationally interesting things going on (ignoring the painting process):

1. Selector matching (what you linked to). Over 99% of selectors used are a 1-pass subset of REGEX.

2. Cascading (really about rule prioritization)

3. Tree normalization (e.g., inserting anonymous elements for tables and block vs. inline flows) --> linear bottom-up tree rewrite

4. Layout solving: to how far I've formalized it so far, it's a bounded sequence of linear tree passes. My interest is that there's parallelism in each pass.

A subtlety to all of this is the incremental factor. E.g., mouse over'ing stuff will trigger the :hover state, which you want to be a O(1) change in practice. Similarly, opening a menu shouldn't impact that much.

My goal here has been to make something 1) analyzable 2) parallel and 3) a DSL from which I can automatically generate a scriptable layout engine.

An old draft about my first stab at this particular part of our parallel browser project is on my site: fast and parallel layout . Currently making the camera-ready version, so input would be welcome :)

edit: Dave Baron, one of the main designers of CSS, believes the layout phase is O(n^2). I still don't understand enough of the spec to say yes or no; what I've understood so far isn't.


It's so funny how it seems like you, David Barbour and Sean McDirmid seem to have answers to things I am curious about :)

My interest isn't really in making the Web a better place for CSS, though :)

Have you seen Greg Bardos' Ph.D. thesis? I just linked to it on my tumbelog: Extending Interactive Graphical Applications with Constraints. Haven't read it yet, but it looks interesting, and I know Bardos is a genius (he is basically one of the top guys at Google).

Yes. Unfortunately, it has

Yes. Unfortunately, it has little to do with using constraints as a semantic basis for graphical applications: he extends parts to use them, and uses the core of CSS without. Sort of like adding a linear constraint library to Silverlight and then invoking it in the binding layer; close, but not quite it. The overall Cassowary project is very inspirational, but also a cautionary tale. This stuff is hard, especially once you care about performance.

My goal is a good layout language for mobile (i.e., resource-constrained) devices. I'm not the biggest fan of CSS, and it currently does not fit the bill in neither goodness nor performance; however, when doing research, I'm with Hoare on analyzing one thing at a time. Right now I'm doing static layout + rendering performance and, hopefully, this summer will start on incrementalism and analyzability. Given such a fundamental understanding (+ my own industry experience here), hopefully reach a point where I can do a cleaner approach to design (and/or graduate).

CSS criticism

I'm not the biggest fan of CSS, and it currently does not fit the bill in neither goodness nor performance;

Only criticisms I've found about CSS was in Chris Anderson's Essential WPF book (sort of handwaving, probably not trying to intimidate readers too much) and INRIA's Hop programming system; see section 2.2 of Serrano's The Hop Development Kit for Scheme.

Most of my interest in this point actually stems off of Anderson's comments that cascading stylesheets are not all that. I'll dig up the exact pages in the book at some point, it's in the chapter on Styles, and chances are you can just use Google Reader to snatch up the relevant discussion.

There are a lot of problems.

There are a lot of problems. Off the top of my head:

-- poor abstraction / reuse facilities in selectors and property lists
-- no notions like encapsulation or containment within the static stylesheet, must be encoded
-- specificity is used for selectors but not properties
-- poor handling of text (as opposed to boxes)
-- no GPU-ish support (textures, shaders, etc.)
-- box model (width/margin/padding/borders) are broken; even the creator wrote this in his thesis
-- ~12-pass rendering priority instead of a HTML-tree driven containment ordering
-- ambiguity on constraints (min/pref widths, float positioning)
-- poor orthogonality of many features (particular core relationships between display inline/block/inlineblock and floats and overflow).

Etc., etc. . Again -- I'm just working on the performance side right now, so don't expect much from me :) I believe either Reddit or Digg has their own Python-based CSS generator from a richer language, and I bet Google does too. The PL community hasn't done much for the web community in terms of pragmatics, as is becoming painfully obvious when researchers try to do formal (e.g., security analysis) stuff for web apps. XHTML, JavaScript, and CSS -- the core -- are painful. I'm not very knowledgeable about HTTP/protocols, but as obvious by the discussion here on Doloto, we aren't delivering applications to clients in the right way.

Feedback on paper

I'll update this as I move through the paper, but there is another component besides Google manually optimizing page designs - layout renders must be personalized per device to help with the UX. Chris Lord has a good summary on techniques used today in Displaying Web Content on Small Displays; he also has a similar overview in his Ph.D. dissertation: Small-Screen HTML Rendering on Memory Constrained Devices.

So I think there is an architecture / software engineering component to "next gen browsers".

I also see you cite Greg Bardos' Cassowary constraint solver project on Page 10, but you say they are insufficient for CSS. Yet you don't cite Bardos' Ph.D. thesis as the authoritative reference. Why not? (I still haven't read it of course!, but is there a paper discussing why this is specifically an "open problem"?)

layout renders must be

layout renders must be personalized per device to help with the UX.

I talked about that in my introduction section: instead of just rewriting their style for the new device, reusing existing JavaScript etc., developers switch languages entirely when going mobile. That's an indictment of modern browsers. Multitouch etc. APIs exist; performance doesn't.

. Yet you don't cite Bardos' Ph.D. thesis as the authoritative reference. Why not? (I still haven't read it of course!, but is there a paper discussing why this is specifically an "open problem"?)

I cited the computational core (the Cassowary solver) which I'm guessing Greg started to work on later -- I thought that was the canonical reference. I had to drop a lot of content in the paper due to low page count for WWW; will add to extended version.

It's an open problem because nobody has solved it ;-) As far as I can tell, Lin's paper at HP has made the most progress. Systems like Garnet and Amulet laid out a vision for a nice linguistic basis for these systems, but nobody has hit it.

Linear constraints, to me, sound like an optimistic choice when you have stuff like conditionals (and unevaluated by their proponents by say translating common layout languages into them). However, I came from a school where I saw Pascal Van Hentenryck and Meinolf Sellmann do amazing things with constraint problems, so I expect there's a more expressive formulation (e.g., I played with quadratic constraints a couple summers ago). I think we're close with the linearly-bounded attribute grammar stuff: CSS shows many common metaphors are good for layout, I've had promising results in this approach to formulating it, and there have been theoretical (though not practical) results in incrementalizing them.

Edit: The question of whether the layout engine should override the layout of a page is still open (there are papers about this every year in WWW/Multimedia/UIST/etc.). I think systems like CSS have the right approach, though the abstractions and tools are still primitive: let the designer specify how content works in different contexts. Subjectively, all of the content reformatting tools I've seen looks bad. That doesn't mean they always will nor that they're worse than the alternative (a layout aimed at the wrong format). However, I'm interested in the typical case where a designer is willing to target multiple mediums. CSS supports this to an extent (media types and constraints) but clearly falls down (see some of David Salesin's UI papers); exploring the boundary and abstractions further is fun but a distinct topic.

I was not being fair to Greg

I was not being fair to Greg Badros'' thesis. The relevant section is chapter 5. He shows

-- cascading can be understood in terms of prioritized constraints. I just didn't find that to be a surprise because that's how the CSS specification describes them: a rule prioritization algorithm.

-- many non-layout constraints, such as font family and size, are a question of inheritance or functional dependence (20% of 30% of 10% of 200px); he correctly points out mixing linear constraints with finite domain ones work here.

-- the problem is the layout language (once conflicting constraints are removed) where we have most of the confusion is not related to his work. E.g., word-wrapping (see Lin's paper) or floats and shrink-to-fit sizing (see mine). The box model is a beast.