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 f9e705e999786c1fa634cd5961854fbd45829c9f..cf115751a76d4a2d631d3bd1f1aba98fcac71728 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/CharacterIterator.h"
 #include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
+#include "core/editing/iterators/TextAccumulator.h"
 #include "core/editing/iterators/TextIterator.h"
 #include "core/frame/LocalFrame.h"
 #include "core/frame/Settings.h"
@@ -666,16 +667,17 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
     const PositionTemplate<Strategy> start = PositionTemplate<Strategy>::editingPositionOf(boundary, 0).parentAnchoredEquivalent();
     const PositionTemplate<Strategy> end = pos.parentAnchoredEquivalent();
 
-    Vector<UChar, 1024> string;
+    ForwardsTextBuffer suffixString;
     unsigned suffixLength = 0;
 
     if (requiresContextForWordBoundary(characterBefore(c))) {
         TextIteratorAlgorithm<Strategy> forwardsIterator(end, PositionTemplate<Strategy>::afterNode(boundary));
         while (!forwardsIterator.atEnd()) {
-            Vector<UChar, 1024> characters;
+            // TODO(xiaochengh): Eliminate this intermediate buffer.
+            ForwardsTextBuffer characters;
             forwardsIterator.copyTextTo(characters);
             int i = endOfFirstWordBoundaryContext(characters.data(), characters.size());
-            string.append(characters.data(), i);
+            suffixString.push(characters.data(), i);
             suffixLength += i;
             if (static_cast<unsigned>(i) < characters.size())
                 break;
@@ -683,31 +685,23 @@ static VisiblePositionTemplate<Strategy> previousBoundary(const VisiblePositionT
         }
     }
 
+    BackwardsTextAccumulator string;
+    string.push(suffixString.data(), suffixString.size());
+
     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());
-        }
+        string.extract(it);

[yosin_UTC9, 2016/02/09 02:28:04]

it.copyTo(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.
         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
         if (next)
             break;
-        it.advance();
+        string.advance(it);

[yosin_UTC9, 2016/02/09 02:28:05]

if (string.isSomeCondition()) {
  string.resetAccumulatedInCurrentNode(); // Not sure
  it.advance();
}

Not sure about |isSomeCondition()|, it is |m_accumulatedInCurrentNode ==
it.length())|

     }
     if (needMoreContext) {
         // The last search returned the beginning of the buffer and asked for
@@ -722,9 +716,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() - string.accumulatedLengthInCurrentNode() + 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
@@ -746,19 +741,18 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
     Document& d = boundary->document();
     const PositionTemplate<Strategy> start(pos.parentAnchoredEquivalent());
 
-    Vector<UChar, 1024> string;
+    BackwardsTextBuffer prefixString;
     unsigned prefixLength = 0;
 
     if (requiresContextForWordBoundary(characterAfter(c))) {
         SimplifiedBackwardsTextIteratorAlgorithm<Strategy> backwardsIterator(PositionTemplate<Strategy>::firstPositionInNode(&d), start);
         while (!backwardsIterator.atEnd()) {
-            Vector<UChar, 1024> characters;
+            // TODO(xiaochengh): Eliminate this intermediate buffer.
+            BackwardsTextBuffer characters;
             backwardsIterator.copyTextTo(characters);
             int length = characters.size();
             int i = startOfLastWordBoundaryContext(characters.data(), length);
-            // TODO(xiaochengh): Iterative prepending has quadratic running
-            // time in the worst case. Should improve it to linear.
-            string.prepend(characters.data() + i, length - i);
+            prefixString.push(characters.data() + i, length - i);
             prefixLength += length - i;
             if (i > 0)
                 break;
@@ -766,6 +760,9 @@ static VisiblePositionTemplate<Strategy> nextBoundary(const VisiblePositionTempl
         }
     }
 
+    ForwardsTextAccumulator string;
+    string.push(prefixString.data(), prefixString.size());
+
     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);
@@ -777,20 +774,11 @@ 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());
-        }
+        string.extract(it);
         next = searchFunction(string.data(), string.size(), offset, MayHaveMoreContext, needMoreContext);
         if (next != string.size())
             break;
-        it.advance();
+        string.advance(it);
         if (!needMoreContext) {
             // When the search does not need more context, skip all examined
             // characters except the last one, in case it is a boundary.