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

Reply via email to