Given an XHTML document and CSS rules, browsers obviously have to match the two - that is, they have to find out which rules apply to each element, and or find out which elements apply to each rule. The properties declared by the rules are assigned to the matching elements.

How does this work? Two simple approaches I thought of off the top of my head:

a) Iterate through the rules. For each rule, search the document for elements matching the rule's selector, attaching the rule to each match.

b) Traverse the document, testing each rule against each element, attaching rules whose selector matches the current element.

Those algorithms above appear to be quite expensive, which makes me think browsers use a different approach (and/or have optimized search techniques to make the above practical).

Understanding this problem will aid me greatly in my current academic research. If there are particular standards, technologies (such as algorithms and data structures) I need to study to understand this better, I need to do that. Any advice is greatly appreciated!