summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMichael Drake <tlsa@netsurf-browser.org>2013-12-01 19:02:37 +0000
committerMichael Drake <tlsa@netsurf-browser.org>2013-12-01 19:02:37 +0000
commitcea0f412145c239a7583c10554c2d88964e94fd7 (patch)
tree7c8919bc45001c596ad6dc21a6035077fa48ad68 /src
parentd2460b3a2f2690813abdf3b350be9dc5ebf2fe18 (diff)
downloadlibcss-cea0f412145c239a7583c10554c2d88964e94fd7.tar.gz
libcss-cea0f412145c239a7583c10554c2d88964e94fd7.tar.bz2
Significantly optimise CSS selection performance.
Now we pass a node bloom filter to css_get_style. That node bloom filter is filled with the node's ancestor element, class, and id names. Internally, libcss also generates a bloom filter for each selector chain. If the selector chain's bloom filter is not a subset of the node bloom filter, we know that the selector chain's rule does not apply to the node. This avoids the slow selector chain matching process. Other smaller optimisations to move the ruling out of selector chains for inapplicable media types and other reasons to before we start comparing rules from different sources to find the next rule. All this is now done in hash.c so select.c never sees the trivially ruled out rules.
Diffstat (limited to 'src')
-rw-r--r--src/select/hash.c466
-rw-r--r--src/select/hash.h17
-rw-r--r--src/select/select.c82
-rw-r--r--src/select/select.h2
4 files changed, 444 insertions, 123 deletions
diff --git a/src/select/hash.c b/src/select/hash.c
index 37492c1..5420d6d 100644
--- a/src/select/hash.c
+++ b/src/select/hash.c
@@ -12,8 +12,11 @@
#include "select/hash.h"
#include "utils/utils.h"
+#undef PRINT_CHAIN_BLOOM_DETAILS
+
typedef struct hash_entry {
const css_selector *sel;
+ css_bloom sel_chain_bloom[CSS_BLOOM_SIZE];
struct hash_entry *next;
} hash_entry;
@@ -41,7 +44,7 @@ struct css_selector_hash {
static hash_entry empty_slot;
-static inline uint32_t _hash_name(lwc_string *name);
+static inline uint32_t _hash_name(const lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
@@ -49,15 +52,88 @@ static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
static css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
const css_selector *selector);
-static css_error _iterate_elements(const css_selector **current,
+static css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_classes(const css_selector **current,
+static css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_ids(const css_selector **current,
+static css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
-static css_error _iterate_universal(const css_selector **current,
+static css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next);
+
+/* No bytecode if rule body is empty or wholly invalid --
+ * Only interested in rules with bytecode */
+#define RULE_HAS_BYTECODE(r) \
+ (((css_rule_selector *)(r->sel->rule))->style != NULL)
+
+
+/**
+ * Test first selector on selector chain for having matching element name.
+ *
+ * If source of rule is element or universal hash, we know the
+ * element name is a match. If it comes from the class or id hash,
+ * we have to test for a match.
+ *
+ * \param selector selector chain head to test
+ * \param qname element name to look for
+ * \return true iff chain head doesn't fail to match element name
+ */
+static inline bool _chain_good_for_element_name(const css_selector *selector,
+ const css_qname *qname)
+{
+ if (lwc_string_length(selector->data.qname.name) != 1 ||
+ lwc_string_data(selector->data.qname.name)[0] != '*') {
+ bool match;
+ if (lwc_string_caseless_isequal(
+ selector->data.qname.name, qname->name,
+ &match) == lwc_error_ok && match == false) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Test whether the rule applies for current media.
+ *
+ * \param rule Rule to test
+ * \meaid media Current media type(s)
+ * \return true iff chain's rule applies for media
+ */
+static inline bool _rule_good_for_media(const css_rule *rule, uint64_t media)
+{
+ bool applies = true;
+ const css_rule *ancestor = rule;
+
+ while (ancestor != NULL) {
+ const css_rule_media *m = (const css_rule_media *) ancestor;
+
+ if (ancestor->type == CSS_RULE_MEDIA &&
+ (m->media & media) == 0) {
+ applies = false;
+ break;
+ }
+
+ if (ancestor->ptype != CSS_RULE_PARENT_STYLESHEET)
+ ancestor = ancestor->parent;
+ else
+ ancestor = NULL;
+ }
+
+ return applies;
+}
+
+
/**
* Create a hash
*
@@ -288,19 +364,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || qname == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->elements.n_slots - 1;
- index = _hash_name(qname->name) & mask;
+ index = _hash_name(req->qname.name) & mask;
head = &hash->elements.slots[index];
@@ -311,13 +387,22 @@ css_error css__selector_hash_find(css_selector_hash *hash,
bool match = false;
lerror = lwc_string_caseless_isequal(
- qname->name, head->sel->data.qname.name,
+ req->qname.name,
+ head->sel->data.qname.name,
&match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
head = head->next;
}
@@ -344,19 +429,20 @@ css_error css__selector_hash_find(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->class == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->classes.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->class) & mask;
head = &hash->classes.slots[index];
@@ -370,12 +456,24 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
n = _class_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->class, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -403,19 +501,20 @@ css_error css__selector_hash_find_by_class(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
uint32_t index, mask;
hash_entry *head;
- if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
+ if (hash == NULL || req == NULL || req->id == NULL ||
+ iterator == NULL || matched == NULL)
return CSS_BADPARM;
/* Find index */
mask = hash->ids.n_slots - 1;
- index = _hash_name(name) & mask;
+ index = _hash_name(req->id) & mask;
head = &hash->ids.slots[index];
@@ -429,12 +528,24 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
n = _id_name(head->sel);
if (n != NULL) {
lerror = lwc_string_caseless_isequal(
- name, n, &match);
+ req->id, n, &match);
if (lerror != lwc_error_ok)
return css_error_from_lwc_error(lerror);
- if (match)
- break;
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
}
head = head->next;
@@ -461,14 +572,39 @@ css_error css__selector_hash_find_by_id(css_selector_hash *hash,
* If nothing matches, CSS_OK will be returned and **matched == NULL
*/
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const css_selector ***matched)
{
- if (hash == NULL || iterator == NULL || matched == NULL)
+ hash_entry *head;
+
+ if (hash == NULL || req == NULL || iterator == NULL || matched == NULL)
return CSS_BADPARM;
+ head = &hash->universal;
+
+ if (head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+
+ head = head->next;
+ }
+
+ if (head == NULL)
+ head = &empty_slot;
+ }
+
(*iterator) = _iterate_universal;
- (*matched) = (const css_selector **) &hash->universal;
+ (*matched) = (const css_selector **) head;
return CSS_OK;
}
@@ -503,7 +639,7 @@ css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
* \param name Name to hash
* \return hash value
*/
-uint32_t _hash_name(lwc_string *name)
+uint32_t _hash_name(const lwc_string *name)
{
uint32_t z = 0x811c9dc5;
const char *data = lwc_string_data(name);
@@ -573,6 +709,119 @@ lwc_string *_id_name(const css_selector *selector)
return name;
}
+
+/**
+ * Add a selector detail to the bloom filter, if the detail is relevant.
+ *
+ * \param d Selector detail to consider and add if relevant
+ * \param bloom Bloom filter to add to.
+ */
+static inline void _chain_bloom_add_detail(
+ const css_selector_detail *d,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ lwc_string *add = NULL; /* String to add to bloom */
+
+ switch (d->type) {
+ case CSS_SELECTOR_ELEMENT:
+ /* Don't add universal element selector to bloom */
+ if (lwc_string_length(d->qname.name) == 1 &&
+ lwc_string_data(d->qname.name)[0] == '*') {
+ return;
+ }
+
+ /* TODO: Remain case sensitive for XML */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ case CSS_SELECTOR_CLASS:
+ case CSS_SELECTOR_ID:
+ /* TODO: Remain case sensitive in standards mode */
+ if (d->qname.name->insensitive == NULL) {
+ lwc__intern_caseless_string(d->qname.name);
+ }
+ add = d->qname.name->insensitive;
+ break;
+
+ default:
+ return;
+ }
+
+ /* Don't really care if intern for caseless string failed, if we're
+ * out of memory, something else will panic. Everything still works
+ * if the string isn't added the the rule bloom. Just less optimally.
+ */
+ if (add != NULL) {
+ css_bloom_add_hash(bloom, lwc_string_hash_value(add));
+ }
+
+ return;
+}
+
+
+/**
+ * Generate a selector chain's bloom filter
+ *
+ * \param s Selector at head of selector chain
+ * \param bloom Bloom filter to generate.
+ */
+static void _chain_bloom_generate(const css_selector *s,
+ css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ css_bloom_init(bloom);
+
+ /* Work back through selector chain... */
+ do {
+ /* ...looking for Ancestor/Parent combinators */
+ if (s->data.comb == CSS_COMBINATOR_ANCESTOR ||
+ s->data.comb == CSS_COMBINATOR_PARENT) {
+ const css_selector_detail *d = &s->combinator->data;
+ while (d != NULL) {
+ if (d->negate == 0) {
+ _chain_bloom_add_detail(d, bloom);
+ }
+ d = (d->next != 0) ? d + 1 : NULL;
+ }
+ }
+
+ s = s->combinator;
+ } while (s != NULL);
+}
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+/* Count bits set in uint32_t */
+static int bits_set(uint32_t n) {
+ n = n - ((n >> 1) & 0x55555555);
+ n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
+ n = (n + (n >> 4)) & 0x0f0f0f0f;
+ n = n + (n >> 8);
+ n = n + (n >> 16);
+ return n & 0x0000003f;
+}
+
+/* Selector chain bloom instrumentation ouput display. */
+static void print_chain_bloom_details(css_bloom bloom[CSS_BLOOM_SIZE])
+{
+ printf("Chain bloom:\t");
+ int total = 0, i;
+ int set[4];
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ set[i] = bits_set(bloom[i]);
+ total += set[i];
+ }
+ printf("bits set:");
+ for (i = 0; i < CSS_BLOOM_SIZE; i++) {
+ printf(" %2i", set[i]);
+ }
+ printf(" (total:%4i of %i) saturation: %3i%%\n", total,
+ (32 * CSS_BLOOM_SIZE),
+ (100 * total) / (32 * CSS_BLOOM_SIZE));
+}
+#endif
+
/**
* Insert a selector into a hash chain
*
@@ -588,6 +837,11 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
if (head->sel == NULL) {
head->sel = selector;
head->next = NULL;
+ _chain_bloom_generate(selector, head->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(head->sel_chain_bloom);
+#endif
} else {
hash_entry *search = head;
hash_entry *prev = NULL;
@@ -612,13 +866,19 @@ css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head,
search = search->next;
} while (search != NULL);
+ entry->sel = selector;
+ _chain_bloom_generate(selector, entry->sel_chain_bloom);
+
+#ifdef PRINT_CHAIN_BLOOM_DETAILS
+ print_chain_bloom_details(entry->sel_chain_bloom);
+#endif
+
if (prev == NULL) {
- entry->sel = head->sel;
- entry->next = head->next;
- head->sel = selector;
- head->next = entry;
+ hash_entry temp = *entry;
+ *entry = *head;
+ temp.next = entry;
+ *head = temp;
} else {
- entry->sel = selector;
entry->next = prev->next;
prev->next = entry;
}
@@ -685,7 +945,9 @@ css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_elements(const css_selector **current,
+css_error _iterate_elements(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -693,14 +955,29 @@ css_error _iterate_elements(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name;
- name = head->sel->data.qname.name;
+ name = req->qname.name;
+ head = head->next;
+
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ lerror = lwc_string_caseless_isequal(name,
+ head->sel->data.qname.name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- lerror = lwc_string_caseless_isequal(
- name, head->sel->data.qname.name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -720,7 +997,9 @@ css_error _iterate_elements(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_classes(const css_selector **current,
+css_error _iterate_classes(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -728,18 +1007,37 @@ css_error _iterate_classes(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _class_name(head->sel);
+ ref = req->class;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _class_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _class_name(head->sel);
+
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &(req->qname)) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -759,7 +1057,9 @@ css_error _iterate_classes(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_ids(const css_selector **current,
+css_error _iterate_ids(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
@@ -767,18 +1067,37 @@ css_error _iterate_ids(const css_selector **current,
lwc_error lerror = lwc_error_ok;
lwc_string *name, *ref;
- ref = _id_name(head->sel);
+ ref = req->id;
+ head = head->next;
- /* Look for the next selector that matches the key */
- while (match == false && (head = head->next) != NULL) {
- name = _id_name(head->sel);
- if (name == NULL)
- continue;
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ name = _id_name(head->sel);
- lerror = lwc_string_caseless_isequal(
- ref, name, &match);
- if (lerror != lwc_error_ok)
- return css_error_from_lwc_error(lerror);
+ if (name != NULL) {
+ lerror = lwc_string_caseless_isequal(
+ ref, name, &match);
+ if (lerror != lwc_error_ok)
+ return css_error_from_lwc_error(lerror);
+
+ if (match && RULE_HAS_BYTECODE(head)) {
+ if (css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _chain_good_for_element_name(
+ head->sel,
+ &req->qname) &&
+ _rule_good_for_media(
+ head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ }
+ }
+ head = head->next;
+ }
}
if (head == NULL)
@@ -798,15 +1117,32 @@ css_error _iterate_ids(const css_selector **current,
*
* If nothing further matches, CSS_OK will be returned and **next == NULL
*/
-css_error _iterate_universal(const css_selector **current,
+css_error _iterate_universal(
+ const struct css_hash_selection_requirments *req,
+ const css_selector **current,
const css_selector ***next)
{
const hash_entry *head = (const hash_entry *) current;
+ head = head->next;
- if (head->next == NULL)
+ if (head != NULL && head->sel != NULL) {
+ /* Search through chain for first match */
+ while (head != NULL) {
+ if (RULE_HAS_BYTECODE(head) &&
+ css_bloom_in_bloom(
+ head->sel_chain_bloom,
+ req->node_bloom) &&
+ _rule_good_for_media(head->sel->rule,
+ req->media)) {
+ /* Found a match */
+ break;
+ }
+ head = head->next;
+ }
+ }
+
+ if (head == NULL)
head = &empty_slot;
- else
- head = head->next;
(*next) = (const css_selector **) head;
diff --git a/src/select/hash.h b/src/select/hash.h
index 06c27a9..2217cbd 100644
--- a/src/select/hash.h
+++ b/src/select/hash.h
@@ -10,6 +10,7 @@
#include <libwapcaplet/libwapcaplet.h>
+#include <libcss/bloom.h>
#include <libcss/errors.h>
#include <libcss/functypes.h>
@@ -18,7 +19,16 @@ struct css_selector;
typedef struct css_selector_hash css_selector_hash;
+struct css_hash_selection_requirments {
+ css_qname qname; /* Element name, or universal '*' */
+ lwc_string *class; /* Name of class, or NULL */
+ lwc_string *id; /* Name of id, or NULL */
+ uint64_t media; /* Media type(s) we're selecting for */
+ const css_bloom *node_bloom; /* Node's bloom filter */
+};
+
typedef css_error (*css_selector_hash_iterator)(
+ const struct css_hash_selection_requirments *req,
const struct css_selector **current,
const struct css_selector ***next);
@@ -32,18 +42,19 @@ css_error css__selector_hash_remove(css_selector_hash *hash,
const struct css_selector *selector);
css_error css__selector_hash_find(css_selector_hash *hash,
- css_qname *qname,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
- lwc_string *name,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
css_error css__selector_hash_find_universal(css_selector_hash *hash,
+ const struct css_hash_selection_requirments *req,
css_selector_hash_iterator *iterator,
const struct css_selector ***matched);
diff --git a/src/select/select.c b/src/select/select.c
index 2a56dec..cfafe32 100644
--- a/src/select/select.c
+++ b/src/select/select.c
@@ -355,6 +355,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
*
* \param ctx Selection context to use
* \param node Node to select style for
+ * \param bloom Node's bloom filter filled with ancestor tag,id,class
* \param media Currently active media types
* \param inline_style Corresponding inline style for node, or NULL
* \param handler Dispatch table of handler functions
@@ -372,6 +373,7 @@ css_error css_select_ctx_get_sheet(css_select_ctx *ctx, uint32_t index,
* update the fully computed style for a node when layout changes.
*/
css_error css_select_style(css_select_ctx *ctx, void *node,
+ const css_bloom bloom[CSS_BLOOM_SIZE],
uint64_t media, const css_stylesheet *inline_style,
css_select_handler *handler, void *pw,
css_select_results **result)
@@ -394,6 +396,7 @@ css_error css_select_style(css_select_ctx *ctx, void *node,
state.pw = pw;
state.next_reject = state.reject_cache +
(N_ELEMENTS(state.reject_cache) - 1);
+ state.bloom = bloom;
/* Allocate the result set */
state.results = ctx->alloc(NULL, sizeof(css_select_results), ctx->pw);
@@ -1331,31 +1334,6 @@ static const css_selector *_selector_next(const css_selector **node,
return ret;
}
-static bool _rule_good_for_element_name(const css_selector *selector,
- css_select_rule_source *src, css_select_state *state)
-{
- /* If source of rule is element or universal hash, we know the
- * element name is a match. If it comes from the class or id hash,
- * we have to test for a match */
- if (src->source == CSS_SELECT_RULE_SRC_ID ||
- src->source == CSS_SELECT_RULE_SRC_CLASS) {
- if (lwc_string_length(selector->data.qname.name) != 1 ||
- lwc_string_data(
- selector->data.qname.name)[0] != '*') {
- bool match;
- if (lwc_string_caseless_isequal(
- selector->data.qname.name,
- state->element.name,
- &match) == lwc_error_ok &&
- match == false) {
- return false;
- }
- }
- }
-
- return true;
-}
-
css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_stylesheet *sheet, css_select_state *state)
{
@@ -1371,11 +1349,17 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
const css_selector **univ_selectors = &empty_selector;
css_selector_hash_iterator univ_iterator;
css_select_rule_source src = { CSS_SELECT_RULE_SRC_ELEMENT, 0 };
+ struct css_hash_selection_requirments req;
css_error error;
+ /* Set up general selector chain requirments */
+ req.media = state->media;
+ req.node_bloom = state->bloom;
+
/* Find hash chain that applies to current node */
+ req.qname = state->element;
error = css__selector_hash_find(sheet->selectors,
- &state->element, &node_iterator,
+ &req, &node_iterator,
&node_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1391,8 +1375,9 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
}
for (i = 0; i < n_classes; i++) {
+ req.class = state->classes[i];
error = css__selector_hash_find_by_class(
- sheet->selectors, state->classes[i],
+ sheet->selectors, &req,
&class_iterator, &class_selectors[i]);
if (error != CSS_OK)
goto cleanup;
@@ -1401,14 +1386,15 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
if (state->id != NULL) {
/* Find hash chain for node ID */
+ req.id = state->id;
error = css__selector_hash_find_by_id(sheet->selectors,
- state->id, &id_iterator, &id_selectors);
+ &req, &id_iterator, &id_selectors);
if (error != CSS_OK)
goto cleanup;
}
/* Find hash chain for universal selector */
- error = css__selector_hash_find_universal(sheet->selectors,
+ error = css__selector_hash_find_universal(sheet->selectors, &req,
&univ_iterator, &univ_selectors);
if (error != CSS_OK)
goto cleanup;
@@ -1431,46 +1417,32 @@ css_error match_selectors_in_sheet(css_select_ctx *ctx,
* selector here */
assert(selector != NULL);
- /* No bytecode if rule body is empty or wholly invalid --
- * Only interested in rules with bytecode */
- if (((css_rule_selector *) selector->rule)->style != NULL) {
- /* Ignore any selectors contained in rules which are a
- * child of an @media block that doesn't match the
- * current media requirements. */
- if (_rule_applies_to_media(selector->rule,
- state->media)) {
- if (_rule_good_for_element_name(selector, &src,
- state)) {
- error = match_selector_chain(
- ctx, selector,
- state);
- if (error != CSS_OK)
- goto cleanup;
- }
- }
- }
+ /* Match and handle the selector chain */
+ error = match_selector_chain(ctx, selector, state);
+ if (error != CSS_OK)
+ goto cleanup;
/* Advance to next selector in whichever chain we extracted
* the processed selector from. */
switch (src.source) {
case CSS_SELECT_RULE_SRC_ELEMENT:
- error = node_iterator(
- node_selectors, &node_selectors);
+ error = node_iterator(&req, node_selectors,
+ &node_selectors);
break;
case CSS_SELECT_RULE_SRC_ID:
- error = id_iterator(
- id_selectors, &id_selectors);
+ error = id_iterator(&req, id_selectors,
+ &id_selectors);
break;
case CSS_SELECT_RULE_SRC_UNIVERSAL:
- error = univ_iterator(
- univ_selectors, &univ_selectors);
+ error = univ_iterator(&req, univ_selectors,
+ &univ_selectors);
break;
case CSS_SELECT_RULE_SRC_CLASS:
- error = class_iterator(
- class_selectors[src.class],
+ req.class = state->classes[src.class];
+ error = class_iterator(&req, class_selectors[src.class],
&class_selectors[src.class]);
break;
}
diff --git a/src/select/select.h b/src/select/select.h
index ee8e42a..43c29d2 100644
--- a/src/select/select.h
+++ b/src/select/select.h
@@ -58,6 +58,8 @@ typedef struct css_select_state {
reject_item reject_cache[128]; /* Reject cache (filled from end) */
reject_item *next_reject; /* Next free slot in reject cache */
+ const css_bloom *bloom; /* Bloom filter */
+
prop_state props[CSS_N_PROPERTIES][CSS_PSEUDO_ELEMENT_COUNT];
} css_select_state;