Hi,
dbaron and bz have been saying that they’re not satisfied with the
current memory representation of CSS selectors in Gecko. As I understand
it, it is too expensive both in space and number of allocation.
This is a set of Rust data structures whose memory layout should be very
close what Gecko has (assuming Option<~T> is optimized to a nullable
pointer,) although Rust already makes it more type-safe. (Some of the
unique pointers here might not actually be unique in the overall
implementation, but that’s not my focus here.)
type Atom = ...; // Interned string, somehow
type Namespace = i32 // Is this some kind of interning as well?
struct AtomList {
value: Atom,
next: Option<~Atom>,
}
struct PseudoClassList {
pseudo: PseudoClass,
next: Option<~PseudoClassList>,
}
enum PseudoClass {
Empty,
Root,
Lang(Atom),
NthChild(~[u32 ..2]),
NthLastChild(~[u32 ..2]),
Not(~Selector),
Matches(~Selector), // a.k.a. :-moz-any
// ... and many more, but these cover the data types.
}
struct AttrSelector {
next: Option<~PseudoClassList>,
lowercase_name: Atom,
cased_name: Atom,
namespace: Namespace,
function: AttrSelectorOperator,
}
enum AttrSelectorOperator {
AttrExists, // [foo]
AttrEqual(~str), // [foo=bar]
AttrIncludes(~str), // [foo~=bar]
AttrDashMatch(~str), // [foo|=bar]
AttrPrefixMatch(~str), // [foo^=bar]
AttrSubstringMatch(~str), // [foo*=bar]
AttrSuffixMatch(~str), // [foo$=bar]
}
struct Selector {
lowercase_tag: Atom, // Element local name
cased_tag: Atom,
namespace: Namespace,
id_list: Option<~AtomList>,
class_list: Option<~ClassList>,
pseudo_class_list: Option<~PseudoClassList>,
attr_list: Option<~AttrSelector>,
negations: Option<~CompoundSelector>,
pseudo_element: PseudoElement,
combinator: Combinator,
next: Option<~CompoundSelector>
}
enum PseudoElement {
Element, // No pseudo-element
Before,
After,
FirstLine,
FirstLetter,
// A few more, prefixed
}
enum Combinator {
Subject, // Right-most part, no combinator
Child,
Descendant,
NextSibling,
LaterSibling,
}
struct SelectorList {
selectors: ~Selector,
specificity: u32,
next: Option<~SelectorList>,
}
Here are a few ideas to reduce the space usage or number of allocations.
They are applicable to Gecko as much as Servo, but what I mean to do
here is determine what to use in Servo right now.
Are there downsides to these changes? Are there more changes that could
be interesting to make?
* Use vectors / arrays instead of linked lists for AtomList,
PseudoClassList and SelectorList. (Less allocations) This could make it
more difficult to point somewhere in the middle of list (especially in
Rust), but I don’t know how important that is.
* Use a single optional string for an ID selector instead of a list. If
a (combinator-separated part in Selectors L4 spec terminology) "compound
selector" that has more than ID simple selector selector, either they
are all the same and we only need one string (#foo#foo is the same as
#foo), or they are different and the selector never matches.
* Use a bit field for simple (non-functional) pseudo-classes. Same as ID
selectors, repeating the same pseudo-class does not change the selector.
(eg. :empty:empty is the same as :empty. This is true for all
pseudo-classes defined in Selectors 4 AFAIK.)
--
Simon Sapin
_______________________________________________
dev-servo mailing list
[email protected]
https://lists.mozilla.org/listinfo/dev-servo