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.

5 files changed, 22 insertions, 3 deletions

diff --git a/src/css.cc b/src/css.cc
index 2b069f18..12db8b9c 100644
--- a/src/css.cc
+++ b/src/css.cc
@@ -51,6 +51,7 @@ CssSelector::CssSelector (int element, const char *klass,
    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 @@ CssSelector::~CssSelector () {
 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 @@ bool CssSelector::match (Doctree *docTree) {
    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 @@ bool CssSelector::match (Doctree *docTree) {
                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 @@ void CssSelector::addSimpleSelector (Combinator c, int element,
    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;
diff --git a/src/css.hh b/src/css.hh
index 515831e9..9acdb0e9 100644
--- a/src/css.hh
+++ b/src/css.hh
@@ -223,6 +223,7 @@ class CssSelector {
 
    private:
       struct CombinatorAndSelector {
+         int notMatchingBefore; // used for optimizing CSS selector matching
          Combinator combinator;
          CssSimpleSelector selector;
       };
diff --git a/src/doctree.hh b/src/doctree.hh
index 97686e40..f74350b0 100644
--- a/src/doctree.hh
+++ b/src/doctree.hh
@@ -3,6 +3,7 @@
 
 class DoctreeNode {
    public:
+      int num; // unique ascending id
       int depth;
       int element;
       const char *klass;
diff --git a/src/styleengine.cc b/src/styleengine.cc
index bd5c60ed..7dcd3dd5 100644
--- a/src/styleengine.cc
+++ b/src/styleengine.cc
@@ -23,6 +23,7 @@ StyleEngine::StyleEngine (dw::core::Layout *layout) {
    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 @@ StyleEngine::StyleEngine (dw::core::Layout *layout) {
    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 @@ void StyleEngine::startElement (int element) {
 
    stack->increase ();
    Node *n =  stack->getRef (stack->size () - 1);
+   n->num = num++;
    n->style = NULL;
    n->wordStyle = NULL;
    n->depth = stack->size () - 1;
diff --git a/src/styleengine.hh b/src/styleengine.hh
index d063fb27..9669ccf0 100644
--- a/src/styleengine.hh
+++ b/src/styleengine.hh
@@ -19,6 +19,7 @@ class StyleEngine : public Doctree {
       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);