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

third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h

Index: third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
diff --git a/third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h b/third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
new file mode 100644
index 0000000000000000000000000000000000000000..43d1d8145a3c46091522a82d9472eec0c12b4e72
--- /dev/null
+++ b/third_party/WebKit/Source/core/editing/iterators/ProgressiveTextAccumulator.h
@@ -0,0 +1,76 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef ProgressiveTextAccumulator_h
+#define ProgressiveTextAccumulator_h
+
+#include "core/editing/iterators/SimplifiedBackwardsTextIterator.h"
+#include "core/editing/iterators/TextIterator.h"
+#include "wtf/Vector.h"
+
+namespace blink {
+
+template <typename Iterator>
+class CORE_TEMPLATE_CLASS_EXPORT ProgressiveTextAccumulator {
+    STACK_ALLOCATED();
+public:
+
+    using PositionType = typename Iterator::PositionType;
+
+    ProgressiveTextAccumulator(const PositionType& start, const PositionType& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
+
+    const Iterator& iterator() const { return m_iterator; }
+    bool atEnd() const { return m_iterator.atEnd(); }
+    int unaccumulatedLengthInCurrentNode() const { return m_iterator.length() - m_accumulatedInCurrentNode; }
+
+    // TODO(xiaochengh): When this function is repeatedly called for backwards
+    // text iterator, it results in quadratic running time in the worst case
+    // because it iteratively prepends content to the output buffer. Should
+    // improve the running time to linear in all cases.
+    template<typename Buffer>
+    void accumulateTextTo(Buffer& output)
+    {
+        ASSERT(m_maxAccumulate > 0);
+        ASSERT(m_accumulatedInCurrentNode >= 0);
+        ASSERT(m_accumulatedInCurrentNode <= m_iterator.length());
+
+        int accumulateLength = std::min(m_iterator.length() - m_accumulatedInCurrentNode, m_maxAccumulate);
+        if (m_iterator.isInTextSecurityMode()) {
+            // Treat bullets used in the text security mode as regular
+            // characters when looking for boundaries
+            Vector<UChar, 1024> bullets(accumulateLength, 'x');
+            if (Iterator::direction == TextIteratorDirection::TextIteratorForward)
+                output.append(bullets.data(), bullets.size());
+            else
+                output.prepend(bullets.data(), bullets.size());
+        } else {
+            accumulateLength = expandToValidLength(accumulateLength);
+            m_iterator.copyTextTo(output, m_accumulatedInCurrentNode, accumulateLength);
+        }
+        m_accumulatedInCurrentNode += accumulateLength;
+        if (accumulateLength >= m_maxAccumulate)
+            m_maxAccumulate *= 2;
+    }
+
+    void advance();
+
+private:
+
+    int expandToValidLength(int);
+
+    static bool arePairingSurrogates(UChar, UChar);
+
+    Iterator m_iterator;
+    int m_maxAccumulate;
+    int m_accumulatedInCurrentNode;
+};
+
+extern template class CORE_EXTERN_TEMPLATE_EXPORT ProgressiveTextAccumulator<TextIteratorAlgorithm<EditingStrategy>>;
+extern template class CORE_EXTERN_TEMPLATE_EXPORT ProgressiveTextAccumulator<TextIteratorAlgorithm<EditingInComposedTreeStrategy>>;
+extern template class CORE_EXTERN_TEMPLATE_EXPORT ProgressiveTextAccumulator<SimplifiedBackwardsTextIteratorAlgorithm<EditingStrategy>>;
+extern template class CORE_EXTERN_TEMPLATE_EXPORT ProgressiveTextAccumulator<SimplifiedBackwardsTextIteratorAlgorithm<EditingInComposedTreeStrategy>>;
+
+} // namespace blink
+
+#endif // ProgressiveTextAccumulator_h