Optimize Boundary Finding with Progressive Text Accumulation

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

 /*
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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 672 matching lines @@
             if (static_cast<unsigned>(i) < characters.size())
                 break;
             forwardsIterator.advance();
         }
     }
 
     BackwardsTextBuffer string;
     string.pushRange(suffixString.data(), suffixString.size());
 
     SimplifiedBackwardsTextIteratorAlgorithm<Strategy> it(start, end);
+    int remainingLength = 0;
     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.
         if (!inTextSecurityMode) {
-            it.copyTextTo(&string);
+            int runOffset = 0;
+            do {
+                runOffset += it.copyTextTo(&string, runOffset, string.capacity());
+                // TODO(xiaochengh): The following line takes O(string.size()) time,
+                // which makes quadratic overall running time in the worst case.
+                // Should improve it in some way.
+                next = searchFunction(string.data(), string.size(), string.size() - suffixLength, MayHaveMoreContext, needMoreContext);
+            } while (!next && runOffset < it.length());
+            if (next) {
+                remainingLength = it.length() - runOffset;
+                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();
     }
     if (needMoreContext) {
         // The last search returned the beginning of the buffer and asked for
         // more context, but there is no earlier text. Force a search with
         // what's available.
         // TODO(xiaochengh): Do we have to search the whole string?
         next = searchFunction(string.data(), string.size(), string.size() - suffixLength, DontHaveMoreContext, needMoreContext);
         ASSERT(!needMoreContext);
     }
 
     if (!next)
         return createVisiblePosition(it.atEnd() ? it.startPosition() : pos);
 
     Node* node = it.startContainer();
-    if (node->isTextNode() && static_cast<int>(next) <= node->maxCharacterOffset()) {
+    int boundaryOffset = remainingLength + 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
     // position.
     BackwardsCharacterIteratorAlgorithm<Strategy> charIt(start, end);
     charIt.advance(string.size() - suffixLength - next);
     // TODO(yosin) charIt can get out of shadow host.
     return createVisiblePosition(charIt.endPosition());
 }
 
@@ skipping 36 matching lines @@
     const unsigned invalidOffset = static_cast<unsigned>(-1);
     unsigned next = invalidOffset;
     unsigned offset = prefixLength;
     bool needMoreContext = false;
     while (!it.atEnd()) {
         // 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);
+            int runOffset = 0;
+            do {
+                runOffset += it.copyTextTo(&string, runOffset, string.capacity());
+                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);
+                }
+            } while (next == string.size() && runOffset < it.length());
+            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);
-        }
     }
     if (needMoreContext) {
         // The last search returned the end of the buffer and asked for more
         // context, but there is no further text. Force a search with what's
         // available.
         // TODO(xiaochengh): Do we still have to search the whole string?
         next = searchFunction(string.data(), string.size(), prefixLength, DontHaveMoreContext, needMoreContext);
         ASSERT(!needMoreContext);
     }
 
@@ skipping 2540 matching lines @@
 {
     return previousPositionOfAlgorithm<EditingStrategy>(visiblePosition, rule);
 }
 
 VisiblePositionInFlatTree previousPositionOf(const VisiblePositionInFlatTree& visiblePosition, EditingBoundaryCrossingRule rule)
 {
     return previousPositionOfAlgorithm<EditingInFlatTreeStrategy>(visiblePosition, rule);
 }
 
 } // namespace blink