Styling overview

<bz> I'm interested in how the results of the matching are organized
<bz> aka what the equivalent of the ruletree and style context setup in gecko is
<bz> (selector matching in gecko obviously works on the DOM too, not the frame tree, btw)
<pcwalton> oh, OK -- for some reason I thought it was on the frame tree
<pcwalton> and I didn't know how that worked ;)
<bz> well, the driver for it is walking the frame tree.
<pcwalton> do you mean how we do style structs? i.e. how we store the computed styles?
<bz> yes
<pcwalton> ah, OK
<bz> And in particular how you do sharing, if any.
<pcwalton> like Gecko, we group styles into style structs -- each style struct consists of entirely inherited or non-inherited properties that tend to go together
<bz> (I mean, you must have something, since simply attaching to every element a list of computed values for all CSS properties with no sharing anywhere is totally batshit)
<pcwalton> each style struct is atomically reference counted and can be shared with parents during cascading if none of the contents of the style structs changed (i.e. they're copy on write)
<pcwalton> the entire ComputedValues struct is also atomically reference counted and is copy on write
<pcwalton> that's the first way we do sharing
<bz> When you say "parent" you mean parent in the DOM, right?
<pcwalton> yes
<bz> OK.
<bz> So each Element has a pointer to ComputedValues
<bz> And ComputedValues has pointers to style structs
<bz> Correct?
<pcwalton> yes, essentially. (it's kind of not obvious from the code because we do a lot of work to try to prevent DOM from accessing it directly)
<bz> sure, sure
<pcwalton> because of off main thread layout
<pcwalton> but yes
<bz> but conceptually.
<pcwalton> yup
<bz> OK.  So when you want to determine the ComputedValues for an element, how do you do that?
<pcwalton> well, let me first mention the second way we do sharing
• bz listen
<pcwalton> the second way we do sharing is that during selector matching we maintain an LRU cache of the last few nodes we saw and if we can immediately and quickly prove prior to matching that the node we're looking at must have the same style as one of those, we just bump the reference count on the appropriate style and short circuit matching/cascading entirely
<pcwalton> there are a bunch of heuristics in there to quickly check that that I mostly just copied from Blink
<pcwalton> anyway, if that cache misses then we perform selector matching for real by making an array of applicable declarations on the stack (that will spill to the heap if it gets too big) and start throwing rules in there
<pcwalton> rules are indexed by tag name/class/ID and "provenance" (whether they come from the author, user, or UA), so this mostly involves hash table lookups on tag name/class/ID
<pcwalton> in addition, we have a set of "universal" rules that couldn't be indexed by tag name/class/ID, and we match those and throw the applicable declarations in the list too if needed
<pcwalton> then we sort the list according to the proper order and move on to cascading
<bz> Can you hold on just a sec?
<pcwalton> sure
<bz> So your second optimization handles siblings with identical specified styles, basically.
<bz> Does it share more widely than that?
<bz> I guess it could if cousins have parents with identical styles and you have a check for that
<pcwalton> I *think* it can share more than that -- right, that's what I was thinking of
<bz> ok
<bz> Alright, go on
<pcwalton> (we also have an "applicable declarations cache", but it doesn't seem to help much and I'm thinking of removing it)
<bz> So you take your sorted rule list
<bz> for the element
<bz> and start building a ComputedValues from it?
<bz> Or some other intermediate data structure?
<pcwalton> we create a new ComputedValues by just starting with the parent's ComputedValues struct, then march through the list in the right order and copy each declaration in, performing copy-on-write as necessary with each style struct
<dbaron left the chat room. (Quit: 8403864 bytes have been tenured, next gc will be global.)
<bz> hold on
<bz> That doesn't make sense
<pcwalton> so, for example, if only the borders changed from the parent, the resulting ComputedValues will share all the style structs with the parent except for Border
<bz> Because in the common case the Border in fact will differe from the parent
<bz> but the Color will not
<ehsan> nsm: looking
<bz> s/differe/differ/
<pcwalton> when I say "copy each declaration in" I mean "call to_computed_value" -- up to this point we've been working with specified values but now we actually compute computed values
<bz> You don't have any distinction between inherit and non-inherit structs here?
<bz> Sure.
<pcwalton> I'm not sure I understand what you mean
<bz> Let's say you start with the parent's ComputedValues
<pcwalton> we do have a difference between inherited and non-inherited structs
<bz> ok
<bkelly> nsm: don't think so... the resource should still load, but cross-origin restrictions everywhere
<bz> What is the difference?
<ehsan> nsm: doesn't that only handle tainting?
<ehsan> nsm: it doesn't affect origin checks
<pcwalton> oh sorry, I misspoke
<pcwalton> when initializing our ComputedValues, we start with a copy parent's style structs for inherited style structs only
<pcwalton> a copy of the parent's style structs, rather
<bz> aha!
<bz> That makes a _lot_ more sense
<bz> So start with the default structs for the reset one
<bz> and the parent's for the inherited ones
<pcwalton> for non-inherited style structs, we start with a copy of the "initial values" struct, which is essentially a global variable
<bz> OK, this makes sense
<bz> Good.
<bz> So the point is, all structs are computed eagerly, right?
<bz> So you don't need to hold on to a representation of the rule list once you're done, because you have all the info already)
<pcwalton> oh yes, we throw away all the rules after all of this
<pcwalton> the per-node rules, that is
<pcwalton> ("ApplicableDeclarations" in Servo speak)
<pcwalton> (obviously, we hang onto the parsed style sheets themselves because we don't want to reparse the style sheet every time we do layout)
<bz> sure
• bz thinks
<bz> Alright, thanks
<pcwalton> I should probably mention how we do preshints here: they get treated as special ApplicableDeclarations
bz listens
<bz> So they get inserted into the list, right?
<bz> How do they affect the sibling-sharing optimization, if at all?
<pcwalton> there is a method (synthesize_presentational_hints_for_legacy_attributes) that gets called when building up the list of ApplicableDeclarations. it looks at DOM attributes and inserts rules as appropriate
<bz> right
• bz was just looking at that code
<pcwalton> and as for how they affect the sibling sharing optimization, the answer is "badly"
<bz> ok
<pcwalton> I do the same thing Blink does
<bz> Which is?
<pcwalton> there is a list, COMMON_STYLE_AFFECTING_ATTRIBUTES, whereby you have to check to make sure all the attributes in that list match any candidate you want to share with
<bz> ok
<pcwalton> all attributes that affect preshints must either be in that list or another list, RARE_STYLE_AFFECTING_ATTRIBUTES
<bz> So they don't inhibit it entirely
<bz> ah, I see
<pcwalton> if a DOM node has an attribute in RARE_STYLE_AFFECTING_ATTRIBUTES, then sibling sharing is inhibited entirely
<bz> And RARE_STYLE_AFFECTING_ATTRIBUTES inhibits sibling-sharing entirely
<pcwalton> yeah
<pcwalton> well, that's a pretty bad bug then ;)
<pcwalton> but yeah
<bz> Alright, thanks.
• bz would love to see how memory usage compares between Gecko and servo for computed style data
<pcwalton> it's a bit of a tricky balance to determine what should go in "common" and "rare" because the code that determines whether styles can be shared ("can_share_style_with") is so hot
<bz> right
<pcwalton> but style sharing is such a huge win that you want to do it when you can
<pcwalton> I remember that implementing it was the biggest performance win we had
<bz> right
<pcwalton> BTW, these style sharing caches are per-thread
<pcwalton> to avoid synchronization
<bz> In fact it sounds like you share less than Gecko right now...
<bz> (at least in theory; how things look in practice is an interesting question)
<pcwalton> so there are more misses than in a single-threaded scenario