2009-12-08 Carol Szabo <carol.szabo@nokia.com>
[WebKit-https.git] / WebCore / rendering / RenderCounter.cpp
index 6a07616220ae5e7ec5f4b8296f3daccf394307b7..b0aefc50b6fc1934f5501d21c55e3e4ebf778531 100644 (file)
@@ -109,55 +109,120 @@ static bool planCounter(RenderObject* object, const AtomicString& counterName, b
     return false;
 }
 
-static bool findPlaceForCounter(RenderObject* object, const AtomicString& counterName,
-    bool isReset, CounterNode*& parent, CounterNode*& previousSibling)
+// - Finds the insertion point for the counter described by counterOwner, isReset and 
+// identifier in the CounterNode tree for identifier and sets parent and
+// previousSibling accordingly.
+// - The function returns true if the counter whose insertion point is searched is NOT
+// the root of the tree.
+// - The root of the tree is a counter reference that is not in the scope of any other
+// counter with the same identifier.
+// - All the counter references with the same identifier as this one that are in
+// children or subsequent siblings of the renderer that owns the root of the tree
+// form the rest of of the nodes of the tree.
+// - The root of the tree is always a reset type reference.
+// - A subtree rooted at any reset node in the tree is equivalent to all counter 
+// references that are in the scope of the counter or nested counter defined by that
+// reset node.
+// - Non-reset CounterNodes cannot have descendants.
+
+static bool findPlaceForCounter(RenderObject* counterOwner, const AtomicString& identifier, bool isReset, CounterNode*& parent, CounterNode*& previousSibling)
 {
-    // Find the appropriate previous sibling for insertion into the parent node
-    // by searching in render tree order for a child of the counter.
-    parent = 0;
+    // We cannot stop searching for counters with the same identifier before we also
+    // check this renderer, because it may affect the positioning in the tree of our counter.
+    RenderObject* searchEndRenderer = previousSiblingOrParent(counterOwner);
+    // We check renderers in preOrder from the renderer that our counter is attached to
+    // towards the begining of the document for counters with the same identifier as the one
+    // we are trying to find a place for. This is the next renderer to be checked.
+    RenderObject* currentRenderer = counterOwner->previousInPreOrder();
     previousSibling = 0;
-    RenderObject* resetCandidate = isReset ? object->parent() : previousSiblingOrParent(object);
-    RenderObject* prevCounterCandidate = object;
-    CounterNode* candidateCounter = 0;
-    // When a reset counter is chosen as candidateCounter, we'll
-    // decide the new node should be a child of the reset node or a
-    // sibling or the reset node. This flag controls it.
-    bool createChildForReset = true;
-    while ((prevCounterCandidate = prevCounterCandidate->previousInPreOrder())) {
-        CounterNode* c = makeCounterNode(prevCounterCandidate, counterName, false);
-        if (prevCounterCandidate == resetCandidate) {
-            if (!candidateCounter) {
-                candidateCounter = c;
-                createChildForReset = true;
-            }
-            if (candidateCounter) {
-                if (createChildForReset && candidateCounter->isReset()) {
-                    parent = candidateCounter;
-                    previousSibling = 0;
-                } else {
-                    parent = candidateCounter->parent();
-                    previousSibling = candidateCounter;
+    while (currentRenderer) {
+        CounterNode* currentCounter = makeCounterNode(currentRenderer, identifier, false);
+        if (searchEndRenderer == currentRenderer) {
+            // We may be at the end of our search.
+            if (currentCounter) {
+                // We have a suitable counter on the EndSearchRenderer.
+                if (previousSibling) { // But we already found another counter that we come after.
+                    if (currentCounter->isReset()) {
+                        // We found a reset counter that is on a renderer that is a sibling of ours or a parent.
+                        if (isReset && currentRenderer->parent() == counterOwner->parent()) {
+                            // We are also a reset counter and the previous reset was on a sibling renderer
+                            // hence we are the next sibling of that counter if that reset is not a root or
+                            // we are a root node if that reset is a root.
+                            parent = currentCounter->parent();
+                            previousSibling = parent ? currentCounter : 0;
+                            return parent;
+                        }
+                        // We are not a reset node or the previous reset must be on an ancestor of our renderer
+                        // hence we must be a child of that reset counter.
+                        parent = currentCounter;
+                        ASSERT(previousSibling->parent() == currentCounter);
+                        return true;
+                    }
+                    // CurrentCounter, the counter at the EndSearchRenderer, is not reset.
+                    if (!isReset || currentRenderer->parent() != counterOwner->parent()) {
+                        // If the node we are placing is not reset or we have found a counter that is attached
+                        // to an ancestor of the placed counter's renderer we know we are a sibling of that node.
+                        ASSERT(currentCounter->parent() == previousSibling->parent());
+                        parent = currentCounter->parent();
+                        return true;
+                    }
+                } else { 
+                    // We are at the potential end of the search, but we had no previous sibling candidate
+                    // In this case we follow pretty much the same logic as above but no ASSERTs about 
+                    // previousSibling, and when we are a sibling of the end counter we must set previousSibling
+                    // to currentCounter.
+                    if (currentCounter->isReset()) {
+                        if (isReset && currentRenderer->parent() == counterOwner->parent()) {
+                            parent = currentCounter->parent();
+                            previousSibling = currentCounter;
+                            return parent;
+                        }
+                        parent = currentCounter;
+                        return true;
+                    }
+                    if (!isReset || currentRenderer->parent() != counterOwner->parent()) {
+                        parent = currentCounter->parent();
+                        previousSibling = currentCounter;
+                        return true;
+                    }
+                    previousSibling = currentCounter;
                 }
-                return true;
             }
-            resetCandidate = previousSiblingOrParent(resetCandidate);
-        } else if (c) {
-            if (c->isReset()) {
-                if (c->parent()) {
-                    // The new node may be the next sibling of this reset node.
-                    createChildForReset = false;
-                    candidateCounter = c;
-                } else {
-                    createChildForReset = true;
-                    candidateCounter = 0;
-                }
-            } else if (!candidateCounter) {
-                createChildForReset = true;
-                candidateCounter = c;
+            // We come here if the previous sibling or parent of our renderer had no 
+            // good counter, or we are a reset node and the counter on the previous sibling
+            // of our renderer was not a reset counter.
+            // Set a new goal for the end of the search.
+            searchEndRenderer = previousSiblingOrParent(currentRenderer);
+        } else {
+            // We are searching descendants of a previous sibling of the renderer that the
+            // counter being placed is attached to.
+            if (currentCounter) {
+                // We found a suitable counter.
+                if (previousSibling) {
+                    // Since we had a suitable previous counter before, we should only consider this one as our 
+                    // previousSibling if it is a reset counter and hence the current previousSibling is its child.
+                    if (currentCounter->isReset()) {
+                        previousSibling = currentCounter;
+                        // We are no longer interested in previous siblings of the currentRenderer or their children
+                        // as counters they may have attached cannot be the previous sibling of the counter we are placing.
+                        currentRenderer = currentRenderer->parent();
+                        continue;
+                    }
+                } else
+                    previousSibling = currentCounter;
+                currentRenderer = previousSiblingOrParent(currentRenderer);
+                continue;
             }
         }
+        // This function is designed so that the same test is not done twice in an iteration, except for this one
+        // which may be done twice in some cases. Rearranging the decision points though, to accommodate this 
+        // performance improvement would create more code duplication than is worthwhile in my oppinion and may further
+        // impede the readability of this already complex algorithm.
+        if (previousSibling)
+            currentRenderer = previousSiblingOrParent(currentRenderer);
+        else
+            currentRenderer = currentRenderer->previousInPreOrder();
     }
-
     return false;
 }