changeset 763:df8153796f48

initial implementation of a CSS selector matching optimization The idea is to avoid repeated checks of CssSimpleSelector against the same part of the doctree. E.g .navigation * { background-color:green } Would result in checking for class="navigation" all the way down to the document root for all elements. The optimization shortcuts this, for parts of the doctree that have been checked before.
author Johannes Hofmann <Johannes.Hofmann@gmx.de>
date Tue, 13 Jan 2009 09:02:41 +0100
parents 336ae7ab06a8
children 570b3440dc19
files src/css.cc src/css.hh src/doctree.hh src/styleengine.cc src/styleengine.hh
diffstat 5 files changed, 22 insertions(+), 3 deletions(-) [+]
line wrap: on
line diff
--- a/src/css.cc	Mon Jan 12 18:12:33 2009 +0100
+++ b/src/css.cc	Tue Jan 13 09:02:41 2009 +0100
@@ -51,6 +51,7 @@
    selectorList = new lout::misc::SimpleVector
                                   <struct CombinatorAndSelector> (1);
    selectorList->increase ();
+   selectorList->getRef (0)->notMatchingBefore = -1;
    top ()->element = element;
    top ()->klass = klass;
    top ()->pseudo = pseudo;
@@ -64,7 +65,8 @@
 bool CssSelector::match (Doctree *docTree) {
    CssSimpleSelector *sel;
    Combinator comb;
-   const DoctreeNode *node = docTree->top ();
+   int *notMatchingBefore;
+   const DoctreeNode *n, *node = docTree->top ();
 
    assert (selectorList->size () > 0);
 
@@ -76,6 +78,7 @@
    for (int i = selectorList->size () - 2; i >= 0; i--) {
       sel = &selectorList->getRef (i)->selector;
       comb = selectorList->getRef (i + 1)->combinator;
+      notMatchingBefore = &selectorList->getRef (i + 1)->notMatchingBefore;
       node = docTree->parent (node);
 
       if (node == NULL)
@@ -87,10 +90,19 @@
                return false;
             break;
          case DESCENDENT:
+            n = node;
             while (!sel->match (node)) {
+               if (node == NULL || *notMatchingBefore >= node->num) {
+                  *notMatchingBefore = n->num; 
+                  return false;
+               }
+
                node = docTree->parent (node);
-               if (node == NULL)
+
+               if (node == NULL || *notMatchingBefore >= node->num) {
+                  *notMatchingBefore = n->num; 
                   return false;
+               }
             }
             break;
          default:
@@ -107,6 +119,7 @@
    selectorList->increase ();
 
    selectorList->getRef (selectorList->size () - 1)->combinator = c;
+   selectorList->getRef (selectorList->size () - 1)->notMatchingBefore = -1;
    top ()->element = element;
    top ()->klass = klass;
    top ()->pseudo = pseudo;
--- a/src/css.hh	Mon Jan 12 18:12:33 2009 +0100
+++ b/src/css.hh	Tue Jan 13 09:02:41 2009 +0100
@@ -223,6 +223,7 @@
 
    private:
       struct CombinatorAndSelector {
+         int notMatchingBefore; // used for optimizing CSS selector matching
          Combinator combinator;
          CssSimpleSelector selector;
       };
--- a/src/doctree.hh	Mon Jan 12 18:12:33 2009 +0100
+++ b/src/doctree.hh	Tue Jan 13 09:02:41 2009 +0100
@@ -3,6 +3,7 @@
 
 class DoctreeNode {
    public:
+      int num; // unique ascending id
       int depth;
       int element;
       const char *klass;
--- a/src/styleengine.cc	Mon Jan 12 18:12:33 2009 +0100
+++ b/src/styleengine.cc	Tue Jan 13 09:02:41 2009 +0100
@@ -23,6 +23,7 @@
    stack = new lout::misc::SimpleVector <Node> (1);
    cssContext = new CssContext ();
    this->layout = layout;
+   num = 0;
 
    stack->increase ();
    Node *n =  stack->getRef (stack->size () - 1);
@@ -37,7 +38,8 @@
    style_attrs.font = Font::create (layout, &font_attrs);
    style_attrs.color = Color::create (layout, 0);
    style_attrs.backgroundColor = Color::create (layout, 0xffffff);
-   
+
+   n->num = num++;
    n->style = Style::create (layout, &style_attrs);
    n->wordStyle = NULL;
    n->pseudo = NULL;
@@ -62,6 +64,7 @@
 
    stack->increase ();
    Node *n =  stack->getRef (stack->size () - 1);
+   n->num = num++;
    n->style = NULL;
    n->wordStyle = NULL;
    n->depth = stack->size () - 1;
--- a/src/styleengine.hh	Mon Jan 12 18:12:33 2009 +0100
+++ b/src/styleengine.hh	Tue Jan 13 09:02:41 2009 +0100
@@ -19,6 +19,7 @@
       dw::core::Layout *layout;
       lout::misc::SimpleVector <Node> *stack;
       CssContext *cssContext;
+      int num;
 
       dw::core::style::Style *style0 (CssPropertyList *nonCssHints = NULL);
       dw::core::style::Style *wordStyle0 (CssPropertyList *nonCssHints = NULL);