CSSS! and computational complexity of selectors.

Posted on by c-smile

Lets say we have following markup:

<ul>
   <li>First</li>
   <li>Second (with <a href=#>hyperlink</a>)</li>
   <li>Third</li>
   <li>Fourth (with <a href=#>hyperlink</a> too)</li>
</ul>

and the styling task: all <li> that have <a> elements inside have yellow background.

If we would have hypothetic selector :with-child(selector) then we could write this as:

li:with-child(a:link) { background:yellow; }

Problem with this selector lies in its complexity – to compute such selectors you need to scan whole subtree of the element (<li> here). That is a task of complexity O(n). n here is a number of children of the element. Potentially it could be the whole DOM ( html:with-child(a:link) ).

And again that O(n) is not that bad if it happens only once but for the case:

html:with-child(a:hover) p { ... }

all <p> elements of the document should get new styles each time when some <a> in document will get :hover state. And that is really bad. Standard methods of optimizing such cases (e.g. caching) may not be acceptable as they may require significant amount of RAM and/or again CPU resources.

… back to the original task of styling "<li> that have <a> elements inside". It is still possible to solve it while keeping resource consumption at the same level.

Imagine that we would have some magic engine that will assign, say, attribute has-a-inside to such <li> elements. Then our task of styling <li>s will turn into simple rule that is known to be effective: 

li[has-a-inside] { background:yellow; }

In real world scenarios people these days use JavaScript for that. Requires some programming but works reasonably well.

But our desire to do this solely by CSS as JS is not always available. Here is the method of how to accomplish this by CSSS! (so called active CSS) introduced in recent versions of h-smile core (htmlayout and the Sciter).

In CSSS! we need to create one helper rule that will create attribute has-a-inside for each <li> with <a> inside:

li  
{  
  assigned!: self.has-a-inside = self.$1( a[href] )? "true" # null;
}

This rule simply means:

When element li will get this style declaration first time (so when assigned!) this statement do:

  1. assign "true" to the attribute has-a-inside if that li element (self) has at least one element inside matching the selector a[href].
  2. or assign null to that attribute – so to remove it form the element.

The only rule left is the one that I’ve already mentioned:

li[has-a-inside] 
{ 
  background:yellow;
}

Thus after loading such document all <li>s with hyperlinks will have yellow background. Done.

Of course it is not so abstractedly perfect if to compare with with-child(a[href]). E.g. our solution will not reflect dynamic DOM updates but that was the problem we were trying to solve anyway.

Nevertheless it will allow to solve the task in most of practical cases and will at least not make selectors matching implementation worse than it is now.