Introduce TextAccumulator for Progressive Extraction from Text Iterators

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 1c2cc34de9fcb3fb27b1b42ddada1fbe53c0ec59..2c699c4c28c0f54796595c3fd5cc6e95b72ad976 100644
--- a/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
+++ b/third_party/WebKit/Source/core/editing/VisibleUnits.cpp
@@ -41,6 +41,7 @@
 #include "core/editing/iterators/BackwardsCharacterIterator.h"
 #include "core/editing/iterators/BackwardsTextBuffer.h"
 #include "core/editing/iterators/CharacterIterator.h"
+#include "core/editing/iterators/ExponentialAccumulator.h"
 #include "core/editing/iterators/ForwardsTextBuffer.h"
 #include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
 #include "core/editing/iterators/TextIterator.h"
@@ -686,6 +687,7 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         }
     }
 
+    ExponentialAccumulator accumulator;
     BackwardsTextBuffer string;
     string.pushRange(suffixString.data(), suffixString.size());
 
@@ -697,19 +699,24 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         // iterate to get chunks until the searchFunction returns a non-zero
         // value.
         if (!inTextSecurityMode) {
-            it.copyTextTo(&string);
+            while (!next && accumulator.size() < it.length()) {
+                int accumulated = it.copyTextTo(&string, accumulator.size(), accumulator.capacity());
+                accumulator.grow(accumulated);
+                // 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.
+                next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
+            }
+            if (next)
+                break;
         } else {
             // Treat bullets used in the text security mode as regular
             // characters when looking for boundaries
             string.pushCharacters('x', it.length());
+            next = 0;
         }
-        // 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.
-        next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
-        if (next)
-            break;
         it.advance();
+        accumulator.reset();
     }
     if (needMoreContext) {
         // The last search returned the beginning of the buffer and asked for
@@ -724,9 +731,10 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         return createVisiblePosition(it.atEnd() ? it.startPosition() : pos);
 
     Node* node = it.startContainer();
-    if (node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) {
+    int boundaryOffset = it.length() - accumulator.size() + 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
@@ -767,6 +775,7 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
         }
     }
 
+    ExponentialAccumulator accumulator;
     ForwardsTextBuffer string;
     string.pushRange(prefixString.data(), prefixString.size());
 
@@ -783,22 +792,27 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
         // it.
         bool inTextSecurityMode = it.isInTextSecurityMode();
         if (!inTextSecurityMode) {
-            it.copyTextTo(&string);
+            while ((next == string.size() || next == invalidOffset) && accumulator.size() < it.length()) {
+                int accumulated = it.copyTextTo(&string, accumulator.size(), accumulator.capacity());
+                accumulator.grow(accumulated);
+                next = searchFunction(string.data(), string.size(), offset, MayHaveMoreContext, needMoreContext);
+                if (!needMoreContext) {
+                    // When the search does not need more context, skip all examined
+                    // characters except the last one, in case it is a boundary.
+                    offset = string.size();
+                    U16_BACK_1(string.data(), 0, offset);
+                }
+            }
+            if (next != string.size())
+                break;
         } else {
             // Treat bullets used in the text security mode as regular
             // characters when looking for boundaries
             string.pushCharacters('x', it.length());
+            next = string.size();
         }
-        next = searchFunction(string.data(), string.size(), offset, MayHaveMoreContext, needMoreContext);
-        if (next != string.size())
-            break;
         it.advance();
-        if (!needMoreContext) {
-            // When the search does not need more context, skip all examined
-            // characters except the last one, in case it is a boundary.
-            offset = string.size();
-            U16_BACK_1(string.data(), 0, offset);
-        }
+        accumulator.reset();
     }
     if (needMoreContext) {
         // The last search returned the end of the buffer and asked for more