W3C home > Mailing lists > Public > www-style@w3.org > November 2005

Re: Computational complexity of CSS

From: Andrew Fedoniouk <news@terrainformatica.com>
Date: Wed, 16 Nov 2005 12:53:19 -0800
Message-ID: <003801c5eaef$c6daab70$c302000a@internal.toppro.net>
To: "Bjoern Hoehrmann" <derhoermi@gmx.net>
Cc: <www-style@w3.org>

----- Original Message ----- 
From: "Bjoern Hoehrmann" <derhoermi@gmx.net>
| * Andrew Fedoniouk wrote:
| >Think about specificity of style selectors. CSS *requires* them to be
| >placed in flat table.
| If one of the CSS specification explicitly requires specific algorithms
| or data structures when implementing rather than defining the effect it
| would be helpful as you could point these out. If they don't, I don't
| really understand, in fact, I don't understand the flat table part
| either; specifity per CSS 2.1 is a 4-digit number in a number system
| with a very large base, how is that relevant here?

4-digits number you've mentioned defines order in which style definition
must be scanned.  This number defines exact position of style definition
in style lookup table.  To resolve style of each element in the dom
you shall check *each* entry in the table. This 4-number does not
allow you to implement semantic grouping of styles. 4-number
requirement means exactly flat table lookup list organization.

See, declaration:

#one:hover  p em { ... }
#one em { ... }
#two p em {...}

will be scanned in the order:

#one em { ... }
#two p em {...}
#one:hover  p em { ... }

And don't forget that in the case of
selector: .a1[space].a2  you need to scan not
only current element with .a1 class but walk through
all parents of .a1 element up to the root of the dom
to decide does it contain .a2 class or not.

This by the way adds another coefficient in computational complexity:
O(N*M*D) where D is average depth of the DOM.

Let me know if it is still not clear what I mean.

I beleive that at least some recommendations should be
published on W3C site like:

".a1 > .a2" is better than ".a1 .a2"
"p[a1]" is better than just "[a1]",

Andrew Fedoniouk.

| -- 
| Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
| Weinh. Str. 22 · Telefon: +49(0)621/4309674 · http://www.bjoernsworld.de
| 68309 Mannheim · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/
Received on Wednesday, 16 November 2005 20:53:27 UTC

This archive was generated by hypermail 2.3.1 : Monday, 2 May 2016 14:27:21 UTC