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

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..27ca8b1352f5e4af4b258b973ac1c55c6ca43b5a 100644
--- a/third_party/WebKit/Source/core/editing/PositionIterator.cpp
+++ b/third_party/WebKit/Source/core/editing/PositionIterator.cpp
@@ -33,7 +33,17 @@ PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm(Node* anchorNode,
     : m_anchorNode(anchorNode)
     , m_nodeAfterPositionInAnchor(Strategy::childAt(*anchorNode, offsetInAnchor))
     , m_offsetInAnchor(m_nodeAfterPositionInAnchor ? 0 : offsetInAnchor)
+    , m_domTreeVersion(anchorNode->document().domTreeVersion())
+    , m_depthToAnchorNode(0)
 {
+    for (Node* node = Strategy::parent(*anchorNode); node; node = Strategy::parent(*node)) {
+        // Each m_offsetsInAnchorNode[offset] should be index of node,

[yosin_UTC9, 2015/10/21 06:01:15]

should be an index of node in parent node.

[yoichio, 2015/10/22 04:33:57]

Done.

+        // but let's delay to calculate the index until it is needed.

[yosin_UTC9, 2015/10/21 06:01:16]

Please add a reason why we want to postpone.

[yoichio, 2015/10/22 04:33:58]

Done.

+        m_offsetsInAnchorNode.append(-1);

[yosin_UTC9, 2015/10/21 06:01:16]

Could you name |-1|?

[yoichio, 2015/10/22 04:33:57]

Done.

+        m_depthToAnchorNode++;

[yosin_UTC9, 2015/10/21 06:01:16]

nit: prefer prefix: |++m_depthToAnchorNode|.

[yoichio, 2015/10/22 04:33:58]

Done.

+    }
+    if (m_nodeAfterPositionInAnchor)

[yosin_UTC9, 2015/10/21 06:01:16]

nit: early return?

[yoichio, 2015/10/22 04:33:57]

We need initialize |m_OffsetsInAnchorNode| and |m_depthToAnchorNode|
 though |m_nodeAfterPositionInAnchor| is null.

+        m_offsetsInAnchorNode.append(offsetInAnchor);
 }
 template <typename Strategy>
 PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm(const PositionTemplate<Strategy>& pos)
@@ -46,18 +56,22 @@ PositionIteratorAlgorithm<Strategy>::PositionIteratorAlgorithm()
     : m_anchorNode(nullptr)
     , m_nodeAfterPositionInAnchor(nullptr)
     , m_offsetInAnchor(0)
+    , m_domTreeVersion(0)

[yosin_UTC9, 2015/10/21 06:01:16]

m_domTreeVersion(anchorNode->document().domTreeVersion())

[yoichio, 2015/10/22 04:33:57]

Because anchorNode is null we can't.

+    , m_depthToAnchorNode(0)
 {
 }
 
 template <typename Strategy>
 PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::deprecatedComputePosition() const
 {
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());

[yosin_UTC9, 2015/10/21 06:01:16]

Having function for checking is better, e.g. |EphemeralRange|.
We may want to have base class for it to share code between |PositionIterator|
and |EphemeralRange|, in another patch.

[yoichio, 2015/10/22 04:33:58]

Add comment.

     if (m_nodeAfterPositionInAnchor) {
         ASSERT(Strategy::parent(*m_nodeAfterPositionInAnchor) == m_anchorNode);
+        ASSERT(m_offsetsInAnchorNode[m_depthToAnchorNode] >= 0);

[yosin_UTC9, 2015/10/21 06:01:16]

Once we have |kInvalidOffset|, or another, we can write
ASSERT(m_offsetInAnchorNode[m_depthToAnchorNode] != kInvalidOffset);

[yoichio, 2015/10/22 04:33:57]

Done.

         // 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,16 +81,34 @@ PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::deprecatedComput
 template <typename Strategy>
 PositionTemplate<Strategy> PositionIteratorAlgorithm<Strategy>::computePosition() const
 {
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
+    // 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] >= 0);
+        // FIXME: This should be

[yosin_UTC9, 2015/10/21 06:01:15]

s/FIXME/TODO(yoichio)/

[yoichio, 2015/10/22 04:33:57]

Done.

+        // PositionTemplate<Strategy>(m_anchorNode, PositionAnchorType::BeforeAnchor);

[yosin_UTC9, 2015/10/21 06:01:15]

Not sure meaning of this comment.
Do you try to say "equivalent to BeforeAnchor"?

[yoichio, 2015/10/22 04:33:57]

Done.

+        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);
 }
 
@@ -85,19 +117,63 @@ void PositionIteratorAlgorithm<Strategy>::increment()
 {
     if (!m_anchorNode)
         return;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
 
+    // 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.
+        // 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++;

[yosin_UTC9, 2015/10/21 06:01:16]

nit: prefer prefix form: |++m_depthToAnchorNode|.

[yoichio, 2015/10/22 04:33:57]

Done.

+        if (m_depthToAnchorNode >= m_offsetsInAnchorNode.size())

[yosin_UTC9, 2015/10/21 06:01:16]

m_depthToAnchorNode == m_offsetsInAnchorNode.size()?
Do we have m_depthToAnchorNode > m_offsetsInAnchorNode.size()?
Should we fill zero(?)?

[yoichio, 2015/10/22 04:33:58]

Done.

+            m_offsetsInAnchorNode.append(0);

[yosin_UTC9, 2015/10/21 06:01:15]

why zero?

[yoichio, 2015/10/22 04:33:57]

Because m_nodeAfterPositionInAnchor is firstChild of parent anchornode.
Read this code block and comment.

+        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--;

[yosin_UTC9, 2015/10/21 06:01:16]

nit: prefer prefix form.

[yoichio, 2015/10/22 04:33:58]

Done.

+        // Increment offset of |child| or initialize if it have never been
+        // used.
+        if (m_offsetsInAnchorNode[m_depthToAnchorNode] == -1)
+            m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor) + 1;
+        else
+            m_offsetsInAnchorNode[m_depthToAnchorNode]++;

[yosin_UTC9, 2015/10/21 06:01:16]

nit: prefer prefix form.

[yoichio, 2015/10/22 04:33:57]

Done.

         m_nodeAfterPositionInAnchor = Strategy::nextSibling(*m_nodeAfterPositionInAnchor);
         m_offsetInAnchor = 0;
     }
@@ -108,29 +184,95 @@ void PositionIteratorAlgorithm<Strategy>::decrement()
 {
     if (!m_anchorNode)
         return;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
 
+    // 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] == -1)
+                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;
         } 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] == -1)
+                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(-1);
+        else
+            m_offsetsInAnchorNode[m_depthToAnchorNode] = -1;
+        m_depthToAnchorNode++;
     } 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);
         } 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] == -1)
+                m_offsetsInAnchorNode[m_depthToAnchorNode] = Strategy::index(*m_nodeAfterPositionInAnchor);
         }
     }
 }
@@ -140,6 +282,7 @@ bool PositionIteratorAlgorithm<Strategy>::atStart() const
 {
     if (!m_anchorNode)
         return true;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
     if (Strategy::parent(*m_anchorNode))
         return false;
     return (!Strategy::hasChildren(*m_anchorNode) && !m_offsetInAnchor) || (m_nodeAfterPositionInAnchor && !Strategy::previousSibling(*m_nodeAfterPositionInAnchor));
@@ -150,6 +293,7 @@ bool PositionIteratorAlgorithm<Strategy>::atEnd() const
 {
     if (!m_anchorNode)
         return true;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
     if (m_nodeAfterPositionInAnchor)
         return false;
     return !Strategy::parent(*m_anchorNode) && (Strategy::hasChildren(*m_anchorNode) || m_offsetInAnchor >= Strategy::lastOffsetForEditing(m_anchorNode));
@@ -160,6 +304,7 @@ bool PositionIteratorAlgorithm<Strategy>::atStartOfNode() const
 {
     if (!m_anchorNode)
         return true;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
     if (!m_nodeAfterPositionInAnchor)
         return !Strategy::hasChildren(*m_anchorNode) && !m_offsetInAnchor;
     return !Strategy::previousSibling(*m_nodeAfterPositionInAnchor);
@@ -170,6 +315,7 @@ bool PositionIteratorAlgorithm<Strategy>::atEndOfNode() const
 {
     if (!m_anchorNode)
         return true;
+    ASSERT(m_domTreeVersion == m_anchorNode->document().domTreeVersion());
     if (m_nodeAfterPositionInAnchor)
         return false;
     return Strategy::hasChildren(*m_anchorNode) || m_offsetInAnchor >= Strategy::lastOffsetForEditing(m_anchorNode);