On Friday 2013-06-28 21:58 +0100, Simon Sapin wrote: > Hi, > > With my CSS parser being mostly complete, the next part to replacing > NetSurf’s LibCSS in Servo is selector matching. > > Part of that is doing it in a way that can meet our performance > requirements. I’ve been going through Gecko’s nsCSSRuleProcessor.cpp > source code and the Fast and Parallel Webpage Layout paper. > http://www.eecs.berkeley.edu/~lmeyerov/projects/pbrowser/pubfiles/playout.pdf > > > What I got so far: > > * Different rules can use the same selector. Map unique selectors > each to a list of rules, so that identical selectors do not need to > be matched more than once.
We actually don't do this in Gecko, but I agree it could be useful. Remember that at the end you'll need to put the rules back into their correct order somehow, for cascading. (At a minimum, this is a problem for different selectors with the same specificity that have interleaved rules.) > * Map ID values to selectors that requires their subjects to have > it. Then same with class names, element names, etc. Each time with > remaining selectors from the previous step. Have a list of the > remaining selectors. > > * For each element in the document, possibly in parallel, find > matching selectors. The maps defined above allow rejecting quickly > most selectors. > > * There is a bloom filter for descendant combinators. I don’t > understand exactly how this works yet, but more code reading should > fix that. > > Did I miss something important? Probably the most important bit is the change-handling optimizations (see HasStateDependentStyle, HasDocumentStateDependentStyle, HasAttributeDependentStyle -- both the implementations and users). -David -- 𝄞 L. David Baron http://dbaron.org/ 𝄂 𝄢 Mozilla http://www.mozilla.org/ 𝄂 _______________________________________________ dev-servo mailing list dev-servo@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-servo
