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

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

 /*
  * 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 16 matching lines @@
 #define PositionIterator_h
 
 #include "core/dom/Node.h"
 #include "core/editing/EditingStrategy.h"
 #include "core/editing/EditingUtilities.h"
 #include "core/html/HTMLHtmlElement.h"
 #include "core/layout/LayoutBlock.h"
 
 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();
 public:
     explicit PositionIteratorAlgorithm(const PositionTemplate<Strategy>&);
     PositionIteratorAlgorithm();
 
     // Since |deprecatedComputePosition()| is slow, new code should use
     // |computePosition()| instead.
     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; }
     int offsetInLeafNode() const { return m_offsetInAnchor; }
 
     bool atStart() const;
     bool atEnd() const;
     bool atStartOfNode() const;
     bool atEndOfNode() const;
 
 private:
     PositionIteratorAlgorithm(Node* anchorNode, int offsetInAnchorNode);
 
     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>;
 extern template class PositionIteratorAlgorithm<EditingInComposedTreeStrategy>;
 
 using PositionIterator = PositionIteratorAlgorithm<EditingStrategy>;
 using PositionIteratorInComposedTree = PositionIteratorAlgorithm<EditingInComposedTreeStrategy>;
 
 } // namespace blink
 
 #endif // PositionIterator_h