123
-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|407|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> C/C++/C#/Other -> Implementing complicated CSS selectors in C
Sun, 24 Jul 2011, 00:14
HoboBen
 		I'm working on a GUI, where elements will be styled using what are essentially CSS stylesheets.

I thought of giving each GUI element a pointer to a :normal, :hover, :active, :focus and :disabled style structure, but this isn't enough in cases where, for example, you're relying on the parent:hover style, e.g.:





I'm not sure how to define my data structures so that I can efficiently use all of these styles, particularly if you chain a really long selector such as ".options .tab radiogroup radiobutton:hover".

I can see three options:

1) Simply restrict any selector to a maximum of two elements, e.g. allowing only "parent:hover child" and "parent child:hover". This isn't really possible though, without cutting features.

2) Store each selector that could possibly apply as a string, e.g. ".mainmenu button:hover", and parsing it whenever an input event changes the state of a parent and recursively its children. (yuck!)

3) Break each selector into "opcodes", and parse the binary opcodes whenever an input event changes the state of a parent and recursively its children.

e.g. selector "#ui .options:hover .tab radiogroup radiobutton:focus"

The parent element "#ui .options" would be the highest element in the selector that could be identified for certain at initialisation. Any element matching "#ui .options" can be found at the start, and only the ".options" element is important.

Then ":hover .tab radiogroup radiobutton:focus" becomes stored in memory in each ".options" element as the following opcodes:



If this can be followed, and any matching element is found, then apply the style. Obviously for a selector with many children and grandchildren, this may have to iterate over many generations, so might be slow in some cases.

---

Is this over-engineering the problem? Can you think of a simpler solution?


-=-=-
blog | work | code | more code
Sun, 24 Jul 2011, 02:43
JL235
 		Something you might find interesting, Mozilla allow you to use CSS to style UIs but ban the child selector due to it's bad performance.

So instead of:

... you have to use ...

Which means .c must be a direct child of .b, who in turn must be a direct child of .a.

For web development I've also started to use the direct child selector over the all child selector, and it gives you a _huge_ performance boost. So you could just ban it.

Solution 1

However if I were to approach this then I would parse the selectors and store them in some kind of data structure for fast lookup, maybe a trie, where each part of the selection makes up the key for each node. But only the leaf nodes would be allowed to apply styles.

When the application first starts you do lots of search to find all inputs affected by the CSS. Then the inputs store a link to the styles that affect them in the trie.

If the input changes then...
  • it looks up the current styles, and checks if they should be removed
  • records (but does not apply) the changes which are being removed
  • unlinks itself from that style
  • from the root of the trie it searches for the new styles that affect it
  • if it is not already attached to that style, then it adds a link to it
  • using the recorded data before, it removes any style attributes not listed in the new style
  • applies all other style changes
The last bit is to avoid removing/applying things that have not changed.

Special style selectors like 'hover' and 'focus' would need a special case to help keep them working instantly, so the input can go straight to it (or have it setup before hand without having to go to the trie at all).

Solution 2

I'm pretty certain Gecko is for more then just webpages, it's for UI's too, so just use that and you'll have all this (and more) out of the box (plus free upstream updates and support).

I don't know about WebKit, but it wouldn't surprise me if you could use that too for building a GUI.
Sun, 24 Jul 2011, 04:17
HoboBen
 		Thanks for the info about the direct child selector. To support some of the features I want, I won't ban it completely, but I will strongly discourage it in most places!

Thinking about Solution 1...

I could represent the following styles in some sort of trie:



|edit| Scratch my diagram, I think it was wrong |edit|

So, thinking through it, any element can tell if it belongs to a style by recursively seeing if any branch of the trie fits, until it either finds a leaf or has no true branches left to evaluate.

This would involve each child gui element having a pointer to its parent element, and for each branch to test, following parent pointers until either the branch fits or the parent pointer is NULL.

A static list of potential styles could be built by ignoring psuedo-selectors like :hover, so that checking if a style applies after input changes can be done quickly.

When a pseudo-selector fires, e.g. :hover, the element then recursively tells its child elements to re-evaluate what styles in this potential list are now active.

As an optimisation, this could be ignored if no styles take its :hover status into account.

If there are no changes, do nothing. If there are cosmetic changes, redraw the child. If there are dimension changes, the gui has to be updated to reflow and reposition everything.

---

Compared to my idea, which would have involved:

For each style that applies to the highest-parent:
---- Recursively, for each child and sub-child:
-------- See if the style fits
-------- Otherwise don't recurse any deeper

The "bottom-up" alternative:

Recursively, for each child and sub-child:
---- For a small set of potential styles
-------- See if the style fits (by a quick recursion upwards through parents)

That looks better to me! Does it sound like I'm on the right track?

Thanks very much for the ideas, btw.


-=-=-
blog | work | code | more code
Sun, 24 Jul 2011, 20:22
HoboBen
 		Option 1:

A style rule is stores as a tree, where the right-most CSS element becomes
the root of the tree:

CSS ".menu .group button" and ".menu .group:disabled button" becomes:



If an element fits the root node, the tree applies to the node (a list of
potential trees for different suedo-selectors can be build at start).

If an element can trace up to a leaf node, the leaf node holds a style.


Option 2:

Each style rule is a separate chain, where the right-most CSS element becomes
the start of the chain.

CSS ".menu .group button" and ".menu .group:disabled button" becomes:



Each chain has knows whether it always applies (depending on
suedo-selectors), which means that those chains only have to be checked to
see if they apply once, at the start.

If an element can trace to the end of the chain, the style applies.

The advantage of Option 2 is that it doesn't have to check as many selectors,
as some can be determined to always apply (or never apply)

However, if two chains are very similar up to the end, there is less to check
if it's a tree as described in Option 1.

As an example, the CSS styles:

div.four:hover > div.three > div.two > div.one > button
div.four:active > div.three > div.two > div.one > button

As chains:



As a tree:



Trees win in that case.

However, given something like "#mainmenu button", every button would have to check if it had a #mainmenu parent. Which is awful.

One idea might be to have a master set of selector trees, then each element builds a set of local selector trees for only the selectors that can ever potentially apply to it. Starting to get a bit complicated, though. Given the overhead of managing a local selector tree for each and every element, maybe I should stick with each element having array of pointers to the applicable master selector chains.

-=-=-
blog | work | code | more code