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.

1 files changed, 15 insertions, 2 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;