[Editing] Speed up PositionIterator::computePosition from O(n) to O(1).

third_party/WebKit/Source/core/editing/PositionIterator.cpp

 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 10 matching lines @@
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "config.h"
 #include "core/editing/PositionIterator.h"
 
 namespace blink {
 
+static const int kInvalidOffset = -1;
+
 template <typename Strategy>
 PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm(Node* anchorNode, int offsetInAnchor)
     : m_anchorNode(anchorNode)
     , m_nodeAfterPositionInAnchor(Strategy::childAt(*anchorNode, offsetInAnchor))
     , m_offsetInAnchor(m_nodeAfterPositionInAnchor ? 0 : offsetInAnchor)
+    , m_depthToAnchorNode(0)
+    , m_domTreeVersion(anchorNode->document().domTreeVersion())
 {
+    for (Node* node = Strategy::parent(*anchorNode); node; node = Strategy::parent(*node)) {
+        // Each m_offsetsInAnchorNode[offset] should be an index of node in
+        // parent, but delay to calculate the index until it is needed for
+        // performance.
+        m_offsetsInAnchorNode.append(kInvalidOffset);
+        ++m_depthToAnchorNode;
+    }
+    if (m_nodeAfterPositionInAnchor)
+        m_offsetsInAnchorNode.append(offsetInAnchor);
 }
 template <typename Strategy>
 PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm(const PositionTemplate<Strategy>& pos)
     : PositionIteratorAlgorithm(pos.anchorNode(), pos.computeEditingOffset())
 {
 }
 
 template <typename Strategy>
 PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm()
     : m_anchorNode(nullptr)
     , m_nodeAfterPositionInAnchor(nullptr)
     , m_offsetInAnchor(0)
+    , m_depthToAnchorNode(0)
+    , m_domTreeVersion(0)
 {
 }
 
 template <typename Strategy>
 PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::deprecatedComputePosition() const
 {
+    // TODO(yoichio): Share code to check domTreeVersion with EphemeralRange.
+    ASSERT(isValid());
     if (m_nodeAfterPositionInAnchor) {
         ASSERT(Strategy::parent(*m_nodeAfterPositionInAnchor) == m_anchorNode);
+        ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] != kInvalidOffset);
         // FIXME: This check is inadaquete because any ancestor could be ignored by editing
         if (Strategy::editingIgnoresContent(Strategy::parent(*m_nodeAfterPositionInAnchor)))
             return PositionTemplate<Strategy>::beforeNode(m_anchorNode);
-        return PositionTemplate<Strategy>::inParentBeforeNode(*m_nodeAfterPositionInAnchor);
+        return PositionTemplate<Strategy>(m_anchorNode, m_offsetsInAnchorNode[m_depthToAnchorNode]);
     }
     if (Strategy::hasChildren(*m_anchorNode))
         return PositionTemplate<Strategy>::lastPositionInOrAfterNode(m_anchorNode);
     return PositionTemplate<Strategy>::editingPositionOf(m_anchorNode, m_offsetInAnchor);
 }
 
 template <typename Strategy>
 PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::computePosition() const
 {
+    ASSERT(isValid());
+    // Assume that we have the following DOM tree:
+    // A
+    // |-B
+    // | |-E
+    // | +-F
+    // |
+    // |-C
+    // +-D
+    //   |-G
+    //   +-H
     if (m_nodeAfterPositionInAnchor) {
+        // For example, position is before E, F.
         ASSERT(Strategy::parent(*m_nodeAfterPositionInAnchor) == m_anchorNode);
-        return PositionTemplate<Strategy>::inParentBeforeNode(*m_nodeAfterPositionInAnchor);
+        ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] != kInvalidOffset);
+        // TODO(yoichio): This should be equivalent to
+        // PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::BeforeAnchor);
+        return PositionTemplate<Strategy>(m_anchorNode, m_offsetsInAnchorNode[m_depthToAnchorNode]);
     }
     if (Strategy::hasChildren(*m_anchorNode))
+        // For example, position is the end of B.
         return PositionTemplate<Strategy>::lastPositionInOrAfterNode(m_anchorNode);
     if (m_anchorNode->isTextNode())
         return PositionTemplate<Strategy>(m_anchorNode, m_offsetInAnchor);
     if (m_offsetInAnchor)
+        // For example, position is after G.
         return PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::AfterAnchor);
+    // For example, position is before G.
     return PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::BeforeAnchor);
 }
 
 template <typename Strategy>
 void PositionIteratorAlgorithm<Strategy>::increment()
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return;
 
+    // Assume that we have the following DOM tree:
+    // A
+    // |-B
+    // | |-E
+    // | +-F
+    // |
+    // |-C
+    // +-D
+    //   |-G
+    //   +-H
+    // Let |anchor| as |m_anchorNode| and
+    // |child| as |m_nodeAfterPositionInAnchor|.
     if (m_nodeAfterPositionInAnchor) {
+        // Case #1: Move to position before the first child of
+        // |m_nodeAfterPositionInAnchor|.
+        // This is a point just before |child|.
+        // Let |anchor| is A and |child| is B,
+        // then next |anchor| is B and |child| is E.
         m_anchorNode = m_nodeAfterPositionInAnchor;
         m_nodeAfterPositionInAnchor = Strategy::firstChild(*m_anchorNode);
         m_offsetInAnchor = 0;
+        // Increment depth intializing with 0.
+        ++m_depthToAnchorNode;
+        if (m_depthToAnchorNode == m_offsetsInAnchorNode.size())
+            m_offsetsInAnchorNode.append(0);
+        else
+            m_offsetsInAnchorNode[m_depthToAnchorNode] = 0;
         return;
     }
 
     if (m_anchorNode->layoutObject() && !Strategy::hasChildren(*m_anchorNode) && m_offsetInAnchor < Strategy::lastOffsetForEditing(m_anchorNode)) {
+        // Case #2. This is the next of Case #1 or #2 itself.
+        // Position is (|anchor|, |m_offsetInAchor|).
+        // In this case |anchor| is a leaf(E,F,C,G or H) and
+        // |m_offsetInAnchor| is not on the end of |anchor|.
+        // Then just increment |m_offsetInAnchor|.
         m_offsetInAnchor = uncheckedNextOffset(m_anchorNode, m_offsetInAnchor);
     } else {
+        // Case #3. This is the next of Case #2 or #3.
+        // Position is the end of |anchor|.
+        // 3-a. If |anchor| has next sibling (let E),
+        //      next |anchor| is B and |child| is F (next is Case #1.)
+        // 3-b. If |anchor| doesn't have next sibling (let F),
+        //      next |anchor| is B and |child| is null. (next is Case #3.)
         m_nodeAfterPositionInAnchor = m_anchorNode;
         m_anchorNode = Strategy::parent(*m_nodeAfterPositionInAnchor);
+        if (!m_anchorNode)
+            return;
+        ASSERT(m_depthToAnchorNode > 0);
+        --m_depthToAnchorNode;
+        // Increment offset of |child| or initialize if it have never been
+        // used.
+        if (m_offsetsInAnchorNode[m_depthToAnchorNode] == kInvalidOffset)
+            m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor) + 1;
+        else
+            ++m_offsetsInAnchorNode[m_depthToAnchorNode];
         m_nodeAfterPositionInAnchor = Strategy::nextSibling(*m_nodeAfterPositionInAnchor);
         m_offsetInAnchor = 0;
     }
 }
 
 template <typename Strategy>
 void PositionIteratorAlgorithm<Strategy>::decrement()
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return;
 
+    // Assume that we have the following DOM tree:
+    // A
+    // |-B
+    // | |-E
+    // | +-F
+    // |
+    // |-C
+    // +-D
+    //   |-G
+    //   +-H
+    // Let |anchor| as |m_anchorNode| and
+    // |child| as |m_nodeAfterPositionInAnchor|.
+    // decrement() is complex but logically reverse of increment(), of course:)
     if (m_nodeAfterPositionInAnchor) {
         m_anchorNode = Strategy::previousSibling(*m_nodeAfterPositionInAnchor);
         if (m_anchorNode) {
+            // Case #1-a. This is a revese of increment()::Case#3-a.
+            // |child| has a previous sibling.
+            // Let |anchor| is B and |child| is F,
+            // next |anchor| is E and |child| is null.
             m_nodeAfterPositionInAnchor = nullptr;
             m_offsetInAnchor = Strategy::hasChildren(*m_anchorNode) ? 0 : Strategy::lastOffsetForEditing(m_anchorNode);
+            // Decrement offset of |child| or initialize if it have never been
+            // used.
+            if (m_offsetsInAnchorNode[m_depthToAnchorNode] == kInvalidOffset)
+                m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor);
+            else
+                --m_offsetsInAnchorNode[m_depthToAnchorNode];
+            ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] >= 0);
+            // Increment depth intializing with last offset.
+            ++m_depthToAnchorNode;
+            if (m_depthToAnchorNode >= m_offsetsInAnchorNode.size())
+                m_offsetsInAnchorNode.append(m_offsetInAnchor);
+            else
+                m_offsetsInAnchorNode[m_depthToAnchorNode] = m_offsetInAnchor;
+            return;
         } else {
+            // Case #1-b. This is a revese of increment()::Case#1.
+            // |child| doesn't have a previous sibling.
+            // Let |anchor| is B and |child| is E,
+            // next |anchor| is A and |child| is B.
             m_nodeAfterPositionInAnchor = Strategy::parent(*m_nodeAfterPositionInAnchor);
             m_anchorNode = Strategy::parent(*m_nodeAfterPositionInAnchor);
+            if (!m_anchorNode)
+                return;
             m_offsetInAnchor = 0;
+            // Decrement depth and intialize if needs.
+            ASSERT(m_depthToAnchorNode > 0);
+            --m_depthToAnchorNode;
+            if (m_offsetsInAnchorNode[m_depthToAnchorNode] == kInvalidOffset)
+                m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor);
         }
         return;
     }
 
     if (Strategy::hasChildren(*m_anchorNode)) {
+        // Case #2. This is a reverse of increment()::Case3-b.
+        // Let |anchor| is B, next |anchor| is F.
         m_anchorNode = Strategy::lastChild(*m_anchorNode);
         m_offsetInAnchor = Strategy::hasChildren(*m_anchorNode)? 0 : Strategy::lastOffsetForEditing(m_anchorNode);
+        // Decrement depth initializing with -1 because
+        // |m_nodeAfterPositionInAnchor| is null so still unneeded.
+        if (m_depthToAnchorNode >= m_offsetsInAnchorNode.size())
+            m_offsetsInAnchorNode.append(kInvalidOffset);
+        else
+            m_offsetsInAnchorNode[m_depthToAnchorNode] = kInvalidOffset;
+        ++m_depthToAnchorNode;
+        return;
     } else {
         if (m_offsetInAnchor && m_anchorNode->layoutObject()) {
+            // Case #3-a. This is a reverse of increment()::Case#2.
+            // In this case |anchor| is a leaf(E,F,C,G or H) and
+            // |m_offsetInAnchor| is not on the beginning of |anchor|.
+            // Then just decrement |m_offsetInAnchor|.
             m_offsetInAnchor = uncheckedPreviousOffset(m_anchorNode, m_offsetInAnchor);
+            return;
         } else {
+            // Case #3-b. This is a reverse of increment()::Case#1.
+            // In this case |anchor| is a leaf(E,F,C,G or H) and
+            // |m_offsetInAnchor| is on the beginning of |anchor|.
+            // Let |anchor| is E,
+            // next |anchor| is B and |child| is E.
             m_nodeAfterPositionInAnchor = m_anchorNode;
             m_anchorNode = Strategy::parent(*m_anchorNode);
+            if (!m_anchorNode)
+                return;
+            ASSERT(m_depthToAnchorNode > 0);
+            --m_depthToAnchorNode;
+            if (m_offsetsInAnchorNode[m_depthToAnchorNode] == kInvalidOffset)
+                m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor);
         }
     }
 }
 
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atStart() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (Strategy::parent(*m_anchorNode))
         return false;
     return (!Strategy::hasChildren(*m_anchorNode) && !m_offsetInAnchor) || (m_nodeAfterPositionInAnchor && !Strategy::previousSibling(*m_nodeAfterPositionInAnchor));
 }
 
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atEnd() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (m_nodeAfterPositionInAnchor)
         return false;
     return !Strategy::parent(*m_anchorNode) && (Strategy::hasChildren(*m_anchorNode) || m_offsetInAnchor >= Strategy::lastOffsetForEditing(m_anchorNode));
 }
 
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atStartOfNode() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (!m_nodeAfterPositionInAnchor)
         return !Strategy::hasChildren(*m_anchorNode) && !m_offsetInAnchor;
     return !Strategy::previousSibling(*m_nodeAfterPositionInAnchor);
 }
 
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atEndOfNode() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (m_nodeAfterPositionInAnchor)
         return false;
     return Strategy::hasChildren(*m_anchorNode) || m_offsetInAnchor >= Strategy::lastOffsetForEditing(m_anchorNode);
 }
 
 template class PositionIteratorAlgorithm<EditingStrategy>;
 template class PositionIteratorAlgorithm<EditingInComposedTreeStrategy>;
 
 } // namespace blink