[Editing] Speed up PositionIterator::computePosition

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

Index: third_party/WebKit/Source/core/editing/PositionIterator.cpp
diff --git a/third_party/WebKit/Source/core/editing/PositionIterator.cpp b/third_party/WebKit/Source/core/editing/PositionIterator.cpp
index a7b7258df5fdca7a7ca0c362c6425f7226ba7195..4943b0a9a9ae5e848da96b0020c105cc52a44f4d 100644
--- a/third_party/WebKit/Source/core/editing/PositionIterator.cpp
+++ b/third_party/WebKit/Source/core/editing/PositionIterator.cpp
@@ -28,12 +28,25 @@
 
 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)
@@ -46,18 +59,23 @@ 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);
@@ -67,37 +85,100 @@ PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::deprecatedComput
 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;
     }
@@ -106,31 +187,100 @@ void PositionIteratorAlgorithm<Strategy>::increment()
 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);
         }
     }
 }
@@ -138,6 +288,7 @@ void PositionIteratorAlgorithm<Strategy>::decrement()
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atStart() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (Strategy::parent(*m_anchorNode))
@@ -148,6 +299,7 @@ bool PositionIteratorAlgorithm<Strategy>::atStart() const
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atEnd() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (m_nodeAfterPositionInAnchor)
@@ -158,6 +310,7 @@ bool PositionIteratorAlgorithm<Strategy>::atEnd() const
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atStartOfNode() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (!m_nodeAfterPositionInAnchor)
@@ -168,6 +321,7 @@ bool PositionIteratorAlgorithm<Strategy>::atStartOfNode() const
 template <typename Strategy>
 bool PositionIteratorAlgorithm<Strategy>::atEndOfNode() const
 {
+    ASSERT(isValid());
     if (!m_anchorNode)
         return true;
     if (m_nodeAfterPositionInAnchor)