[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..5bc672845738b6b65ea29e601bfbfb84533906e5 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,14 @@ public:
     PositionTemplate<Strategy> deprecatedComputePosition() const;
     PositionTemplate<Strategy> computePosition() const;
 
+    // increment() takes O(1) other than incrementing to a element that has
+    // new parent.
+    // In the later case, it takes time of O(<number of childlen>) but the case
+    // 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 the later case, it takes time of O(<number of childlen>).
     void decrement();
 
     Node* node() const { return m_anchorNode; }
@@ -65,7 +74,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

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

nit: s/TODO:/TODO(yoichio):/

+    // m_offsetOfNodeAfterPositionInAnchor[m_depthToAnchorNode].

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

Not sure meaning of this comment.

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

Removed.

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