ALL-IN-ONE: Optimization to previousBoundary() and nextBoundary()

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

Index: third_party/WebKit/Source/core/editing/VisibleUnits.cpp
diff --git a/third_party/WebKit/Source/core/editing/VisibleUnits.cpp b/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
index 22b02341fb4fec49ef8fcf0858435885fd2d9178..edf4e836594317979051cd466eff433af6884266 100644
--- a/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
+++ b/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
@@ -40,6 +40,7 @@
 #include "core/editing/VisiblePosition.h"
 #include "core/editing/iterators/BackwardsCharacterIterator.h"
 #include "core/editing/iterators/CharacterIterator.h"
+#include "core/editing/iterators/ProgressiveTextAccumulator.h"
 #include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
 #include "core/editing/iterators/TextIterator.h"
 #include "core/frame/LocalFrame.h"
@@ -683,24 +684,13 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         }
     }
 
-    SimplifiedBackwardsTextIteratorAlgorithm<Strategy> it(start, end);
+    ProgressiveTextAccumulator<SimplifiedBackwardsTextIteratorAlgorithm<Strategy>> it(start, end);
     unsigned next = 0;
     bool needMoreContext = false;
     while (!it.atEnd()) {
-        bool inTextSecurityMode = it.isInTextSecurityMode();
         // iterate to get chunks until the searchFunction returns a non-zero
         // value.
-        // TODO(xiaochengh): Iterative prepending has quadratic running time
-        // in the worst case. Should improve it to linear.
-        if (!inTextSecurityMode) {
-            it.copyTextTo(string);
-        } else {
-            // Treat bullets used in the text security mode as regular
-            // characters when looking for boundaries
-            Vector<UChar, 1024> iteratorString;
-            iteratorString.fill('x', it.length());
-            string.prepend(iteratorString.data(), iteratorString.size());
-        }
+        it.accumulateTextTo(string);
         // TODO(xiaochengh): The following line takes O(string.size()) time,
         // which makes the while loop take quadratic time in the worst case.
         // Should improve it in some way.
@@ -719,12 +709,13 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
     }
 
     if (!next)
-        return createVisiblePosition(it.atEnd() ? it.startPosition() : pos);
+        return createVisiblePosition(it.iterator().atEnd() ? it.iterator().startPosition() : pos);
 
-    Node* node = it.startContainer();
-    if (node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) {
+    Node* node = it.iterator().startContainer();
+    int boundaryOffset = it.unaccumulatedLengthInCurrentNode() + next;
+    if (node->isTextNode() && boundaryOffset <= node->maxCharacterOffset()) {
         // The next variable contains a usable index into a text node
-        return createVisiblePosition(PositionTemplate<Strategy>(node, next));
+        return createVisiblePosition(PositionTemplate<Strategy>(node, boundaryOffset));
     }
 
     // Use the character iterator to translate the next value into a DOM
@@ -768,7 +759,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
 
     const PositionTemplate<Strategy> searchStart = PositionTemplate<Strategy>::editingPositionOf(start.anchorNode(), start.offsetInContainerNode());
     const PositionTemplate<Strategy> searchEnd = PositionTemplate<Strategy>::lastPositionInNode(boundary);
-    TextIteratorAlgorithm<Strategy> it(searchStart, searchEnd, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
+    ProgressiveTextAccumulator<TextIteratorAlgorithm<Strategy>> it(searchStart, searchEnd, TextIteratorEmitsCharactersBetweenAllVisiblePositions);

[yosin_UTC9, 2016/01/20 05:21:44]

We should have both |accumulator| and |it| rather than
|ProgressiveTextAccumulator| does both accumulation and iteration.
# It seems we don't need to have "Progressive" in class name, it is also
implementation detail.

Here is sketch:

TextIterator it(...);
TextAccumulator accumulator;

while (!it.atEnd()) {
  accumulator.extract(&it); // copy character from it with calling it.advance();
  const auto& string = accumulator.toString(); // construct new Vector<UChar>
  next = searchFunction(string.data(), string.size(), ...)
  ...
}

This model move character buffer management into |TextAccumulator| and we don't
need to make |Buffer| as template parameter.

     const unsigned invalidOffset = static_cast<unsigned>(-1);
     unsigned next = invalidOffset;
     unsigned offset = prefixLength;
@@ -777,16 +768,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
         // Keep asking the iterator for chunks until the search function
         // returns an end value not equal to the length of the string passed to
         // it.
-        bool inTextSecurityMode = it.isInTextSecurityMode();
-        if (!inTextSecurityMode) {
-            it.copyTextTo(string);
-        } else {
-            // Treat bullets used in the text security mode as regular
-            // characters when looking for boundaries
-            Vector<UChar, 1024> iteratorString;
-            iteratorString.fill('x', it.length());
-            string.append(iteratorString.data(), iteratorString.size());
-        }
+        it.accumulateTextTo(string);
         next = searchFunction(string.data(), string.size(), offset, MayHaveMoreContext, needMoreContext);
         if (next != string.size())
             break;
@@ -808,7 +790,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
     }
 
     if (it.atEnd() && next == string.size()) {
-        pos = it.startPositionInCurrentContainer();
+        pos = it.iterator().startPositionInCurrentContainer();
     } else if (next != invalidOffset && next != prefixLength) {
         // Use the character iterator to translate the next value into a DOM
         // position.