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

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

Index: third_party/WebKit/Source/core/editing/PositionIterator.h
diff --git a/third_party/WebKit/Source/core/editing/PositionIterator.h b/third_party/WebKit/Source/core/editing/PositionIterator.h
index 0383cf1fff1c8103d69814ba720e5e5523237808..1826fefa4ec2afc6e46de9508ba8c96ed96fd2e5 100644
--- a/third_party/WebKit/Source/core/editing/PositionIterator.h
+++ b/third_party/WebKit/Source/core/editing/PositionIterator.h
@@ -34,9 +34,11 @@
 
 namespace blink {
 
-// A Position iterator with constant-time
+// A Position iterator with nearly constant-time
 // increment, decrement, and several predicates on the Position it is at.
-// Conversion to/from Position is O(n) in the offset.
+// Conversion from Position is O(n) in the depth.
+// Conversion to Position is O(1).
+// PositionIteratorAlgorithm must be used without DOM tree change.
 template <typename Strategy>
 class PositionIteratorAlgorithm {
     STACK_ALLOCATED();
@@ -49,7 +51,13 @@ public:
     PositionTemplate<Strategy> deprecatedComputePosition() const;
     PositionTemplate<Strategy> computePosition() const;
 
+    // increment() takes O(1) other than increment into new parent.

[hajimehoshi, 2015/10/08 04:57:27]

I don't understand this sentence.

[yoichio, 2015/10/21 04:35:05]

Update

+    // In later case, it takes time of O(<number of childlen>) but the case

[hajimehoshi, 2015/10/08 04:57:27]

nit: In the latter case

[yoichio, 2015/10/21 04:35:05]

Done.

+    // happens at most depth-of-the-tree times over whole tree traversal.
     void increment();
+    // decrement() takes O(1) other than decrement into new node that has 
+    // childlen.
+    // In later case, it takes time of O(<number of childlen>).

[hajimehoshi, 2015/10/08 04:57:27]

nit: ditto

[yoichio, 2015/10/21 04:35:05]

Done.

     void decrement();
 
     Node* node() const { return m_anchorNode; }
@@ -65,7 +73,15 @@ private:
 
     RawPtrWillBeMember<Node> m_anchorNode;
     RawPtrWillBeMember<Node> m_nodeAfterPositionInAnchor; // If this is non-null, Strategy::parent(*m_nodeAfterPositionInAnchor) == m_anchorNode;
+    // TOOD: Replace |m_offsetInAnchor| with
+    // m_offsetOfNodeAfterPositionInAnchor[m_depthToAnchorNode].
     int m_offsetInAnchor;
+    size_t m_depthToAnchorNode;
+    // If |m_nodeAfterPositionInAnchor| is not null,
+    // m_offsetsInAnchorNode[m_depthToAnchorNode] ==
+    //    Strategy::index(m_nodeAfterPositionInAnchor).
+    Vector<int> m_offsetsInAnchorNode;
+    uint64_t m_domTreeVersion;
 };
 
 extern template class PositionIteratorAlgorithm<EditingStrategy>;