3 files changed, 50 insertions, 52 deletions

diff --git a/src/css.cc b/src/css.cc
index c95e43d9..c6c74f60 100644
--- a/src/css.cc
+++ b/src/css.cc
@@ -102,7 +102,7 @@ CssSelector::CssSelector () {
    cs = selectorList->getRef (selectorList->size () - 1);
 
    cs->notMatchingBefore = -1;
-   cs->combinator = CHILD;
+   cs->combinator = COMB_NONE;
    cs->selector = new CssSimpleSelector ();
 };
 
@@ -115,55 +115,47 @@ CssSelector::~CssSelector () {
 /**
  * \brief Return whether selector matches at a given node in the document tree.
  */
-bool CssSelector::match (Doctree *docTree, const DoctreeNode *node) {
-   CssSimpleSelector *sel;
-   Combinator comb = CHILD;
-   int *notMatchingBefore;
-   const DoctreeNode *n;
+bool CssSelector::match (Doctree *docTree, const DoctreeNode *node,
+                         int i, Combinator comb) {
+   assert (node);
 
-   for (int i = selectorList->size () - 1; i >= 0; i--) {
-      struct CombinatorAndSelector *cs = selectorList->getRef (i);
+   if (i < 0)
+      return true;
 
-      sel = cs->selector;
-      notMatchingBefore = &cs->notMatchingBefore;
+   struct CombinatorAndSelector *cs = selectorList->getRef (i);
+   CssSimpleSelector *sel = cs->selector;
 
-      if (node == NULL)
-         return false;
-
-      switch (comb) {
-         case CHILD:
-         case ADJACENT_SIBLING:
-            if (!sel->match (node))
-               return false;
-            break;
-         case DESCENDANT:
-            n = node;
-
-            while (true) {
-               if (node == NULL || node->num <= *notMatchingBefore) {
-                  *notMatchingBefore = n->num;
-                  return false;
-               }
-
-               if (sel->match (node))
-                  break;
+   switch (comb) {
+      case COMB_NONE:
+         break;
+      case COMB_CHILD:
+         node = docTree->parent (node);
+         break;
+      case COMB_ADJACENT_SIBLING:
+         node = docTree->sibling (node);
+         break;
+      case COMB_DESCENDANT:
+         node = docTree->parent (node);
 
-               node = docTree->parent (node);
-            }
-            break;
-         default:
-            return false; // \todo implement other combinators
-      }
+         for (const DoctreeNode *n = node;
+              n && n->num > cs->notMatchingBefore; n = docTree->parent (n))
+            if (sel->match (n) && match (docTree, n, i - 1, cs->combinator))
+               return true;
 
-      comb = cs->combinator;
+         if (node) // remember that it didn't match to avoid future tests
+            cs->notMatchingBefore = node->num;
 
-      if (comb == ADJACENT_SIBLING)
-         node = docTree->sibling (node);
-      else
-         node = docTree->parent (node);
+         return false;
+         break;
+      default:
+         return false; // \todo implement other combinators
    }
 
-   return true;
+   if (!node || !sel->match (node))
+      return false;
+
+   // tail recursion should be optimized by the compiler
+   return match (docTree, node, i - 1, cs->combinator);
 }
 
 void CssSelector::addSimpleSelector (Combinator c) {
@@ -198,13 +190,13 @@ void CssSelector::print () {
 
       if (i < selectorList->size () - 1) {
          switch (selectorList->getRef (i + 1)->combinator) {
-            case CHILD:
+            case COMB_CHILD:
                fprintf (stderr, "> ");
                break;
-            case DESCENDANT:
+            case COMB_DESCENDANT:
                fprintf (stderr, "\" \" ");
                break;
-            case ADJACENT_SIBLING:
+            case COMB_ADJACENT_SIBLING:
                fprintf (stderr, "+ ");
                break;
             default:
@@ -260,6 +252,7 @@ void CssSimpleSelector::setSelect (SelectType t, const char *v) {
  *        the document tree.
  */
 bool CssSimpleSelector::match (const DoctreeNode *n) {
+   assert (n);
    if (element != ELEMENT_ANY && element != n->element)
       return false;
    if (pseudo != NULL &&
diff --git a/src/css.hh b/src/css.hh
index 394f7add..6f6cc75f 100644
--- a/src/css.hh
+++ b/src/css.hh
@@ -355,9 +355,10 @@ class CssSimpleSelector {
 class CssSelector {
    public:
       typedef enum {
-         DESCENDANT,
-         CHILD,
-         ADJACENT_SIBLING,
+         COMB_NONE,
+         COMB_DESCENDANT,
+         COMB_CHILD,
+         COMB_ADJACENT_SIBLING,
       } Combinator;
 
    private:
@@ -370,6 +371,8 @@ class CssSelector {
       int refCount;
       lout::misc::SimpleVector <struct CombinatorAndSelector> *selectorList;
 
+      bool match (Doctree *dt, const DoctreeNode *node, int i, Combinator comb);
+
    public:
       CssSelector ();
       ~CssSelector ();
@@ -378,7 +381,9 @@ class CssSelector {
          return selectorList->getRef (selectorList->size () - 1)->selector;
       };
       inline int size () { return selectorList->size (); };
-      bool match (Doctree *dt, const DoctreeNode *node);
+      inline bool match (Doctree *dt, const DoctreeNode *node) {
+         return match (dt, node, selectorList->size () - 1, COMB_NONE);
+      };
       int specificity ();
       void print ();
       inline void ref () { refCount++; }
diff --git a/src/cssparser.cc b/src/cssparser.cc
index 6d5b3768..306aa58c 100644
--- a/src/cssparser.cc
+++ b/src/cssparser.cc
@@ -1292,13 +1292,13 @@ CssSelector *CssParser::parseSelector()
          (tval[0] == ',' || tval[0] == '{')) {
          break;
       } else if (ttype == CSS_TK_CHAR && tval[0] == '>') {
-         selector->addSimpleSelector (CssSelector::CHILD);
+         selector->addSimpleSelector (CssSelector::COMB_CHILD);
          nextToken();
       } else if (ttype == CSS_TK_CHAR && tval[0] == '+') {
-         selector->addSimpleSelector (CssSelector::ADJACENT_SIBLING);
+         selector->addSimpleSelector (CssSelector::COMB_ADJACENT_SIBLING);
          nextToken();
       } else if (ttype != CSS_TK_END && spaceSeparated) {
-         selector->addSimpleSelector (CssSelector::DESCENDANT);
+         selector->addSimpleSelector (CssSelector::COMB_DESCENDANT);
       } else {
          delete selector;
          selector = NULL;