Simple line layout: Add <br> support.
[WebKit-https.git] / Source / WebCore / editing / TextIterator.cpp
1 /*
2  * Copyright (C) 2004-2014 Apple Inc. All rights reserved.
3  * Copyright (C) 2005 Alexey Proskuryakov.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
25  */
26
27 #include "config.h"
28 #include "TextIterator.h"
29
30 #include "Document.h"
31 #include "ExceptionCodePlaceholder.h"
32 #include "FontCascade.h"
33 #include "Frame.h"
34 #include "HTMLElement.h"
35 #include "HTMLNames.h"
36 #include "HTMLParagraphElement.h"
37 #include "HTMLTextFormControlElement.h"
38 #include "InlineTextBox.h"
39 #include "NodeTraversal.h"
40 #include "RenderImage.h"
41 #include "RenderIterator.h"
42 #include "RenderTableCell.h"
43 #include "RenderTableRow.h"
44 #include "RenderTextControl.h"
45 #include "RenderTextFragment.h"
46 #include "ShadowRoot.h"
47 #include "SimpleLineLayout.h"
48 #include "SimpleLineLayoutResolver.h"
49 #include "TextBoundaries.h"
50 #include "TextBreakIterator.h"
51 #include "TextControlInnerElements.h"
52 #include "VisiblePosition.h"
53 #include "VisibleUnits.h"
54 #include "htmlediting.h"
55 #include <wtf/text/CString.h>
56 #include <wtf/text/StringBuilder.h>
57 #include <wtf/unicode/CharacterNames.h>
58
59 #if !UCONFIG_NO_COLLATION
60 #include "TextBreakIteratorInternalICU.h"
61 #include <unicode/usearch.h>
62 #endif
63
64 using namespace WTF::Unicode;
65
66 namespace WebCore {
67
68 using namespace HTMLNames;
69
70 // Buffer that knows how to compare with a search target.
71 // Keeps enough of the previous text to be able to search in the future, but no more.
72 // Non-breaking spaces are always equal to normal spaces.
73 // Case folding is also done if the CaseInsensitive option is specified.
74 // Matches are further filtered if the AtWordStarts option is specified, although some
75 // matches inside a word are permitted if TreatMedialCapitalAsWordStart is specified as well.
76 class SearchBuffer {
77     WTF_MAKE_NONCOPYABLE(SearchBuffer);
78 public:
79     SearchBuffer(const String& target, FindOptions);
80     ~SearchBuffer();
81
82     // Returns number of characters appended; guaranteed to be in the range [1, length].
83     size_t append(StringView);
84     bool needsMoreContext() const;
85     void prependContext(StringView);
86     void reachedBreak();
87
88     // Result is the size in characters of what was found.
89     // And <startOffset> is the number of characters back to the start of what was found.
90     size_t search(size_t& startOffset);
91     bool atBreak() const;
92
93 #if !UCONFIG_NO_COLLATION
94
95 private:
96     bool isBadMatch(const UChar*, size_t length) const;
97     bool isWordStartMatch(size_t start, size_t length) const;
98     bool isWordEndMatch(size_t start, size_t length) const;
99
100     const String m_target;
101     const StringView::UpconvertedCharacters m_targetCharacters;
102     FindOptions m_options;
103
104     Vector<UChar> m_buffer;
105     size_t m_overlap;
106     size_t m_prefixLength;
107     bool m_atBreak;
108     bool m_needsMoreContext;
109
110     const bool m_targetRequiresKanaWorkaround;
111     Vector<UChar> m_normalizedTarget;
112     mutable Vector<UChar> m_normalizedMatch;
113
114 #else
115
116 private:
117     void append(UChar, bool isCharacterStart);
118     size_t length() const;
119
120     String m_target;
121     FindOptions m_options;
122
123     Vector<UChar> m_buffer;
124     Vector<bool> m_isCharacterStartBuffer;
125     bool m_isBufferFull;
126     size_t m_cursor;
127
128 #endif
129 };
130
131 // --------
132
133 static const unsigned bitsInWord = sizeof(unsigned) * 8;
134 static const unsigned bitInWordMask = bitsInWord - 1;
135
136 BitStack::BitStack()
137     : m_size(0)
138 {
139 }
140
141 BitStack::~BitStack()
142 {
143 }
144
145 void BitStack::push(bool bit)
146 {
147     unsigned index = m_size / bitsInWord;
148     unsigned shift = m_size & bitInWordMask;
149     if (!shift && index == m_words.size()) {
150         m_words.grow(index + 1);
151         m_words[index] = 0;
152     }
153     unsigned& word = m_words[index];
154     unsigned mask = 1U << shift;
155     if (bit)
156         word |= mask;
157     else
158         word &= ~mask;
159     ++m_size;
160 }
161
162 void BitStack::pop()
163 {
164     if (m_size)
165         --m_size;
166 }
167
168 bool BitStack::top() const
169 {
170     if (!m_size)
171         return false;
172     unsigned shift = (m_size - 1) & bitInWordMask;
173     return m_words.last() & (1U << shift);
174 }
175
176 unsigned BitStack::size() const
177 {
178     return m_size;
179 }
180
181 // --------
182
183 #if !ASSERT_DISABLED
184
185 static unsigned depthCrossingShadowBoundaries(Node& node)
186 {
187     unsigned depth = 0;
188     for (Node* parent = node.parentOrShadowHostNode(); parent; parent = parent->parentOrShadowHostNode())
189         ++depth;
190     return depth;
191 }
192
193 #endif
194
195 // This function is like Range::pastLastNode, except for the fact that it can climb up out of shadow trees.
196 static Node* nextInPreOrderCrossingShadowBoundaries(Node& rangeEndContainer, int rangeEndOffset)
197 {
198     if (rangeEndOffset >= 0 && !rangeEndContainer.offsetInCharacters()) {
199         if (Node* next = rangeEndContainer.traverseToChildAt(rangeEndOffset))
200             return next;
201     }
202     for (Node* node = &rangeEndContainer; node; node = node->parentOrShadowHostNode()) {
203         if (Node* next = node->nextSibling())
204             return next;
205     }
206     return nullptr;
207 }
208
209 static inline bool fullyClipsContents(Node& node)
210 {
211     auto* renderer = node.renderer();
212     if (!is<RenderBox>(renderer) || !renderer->hasOverflowClip())
213         return false;
214     return downcast<RenderBox>(*renderer).size().isEmpty();
215 }
216
217 static inline bool ignoresContainerClip(Node& node)
218 {
219     auto* renderer = node.renderer();
220     if (!renderer || renderer->isTextOrLineBreak())
221         return false;
222     return renderer->style().hasOutOfFlowPosition();
223 }
224
225 static void pushFullyClippedState(BitStack& stack, Node& node)
226 {
227     ASSERT(stack.size() == depthCrossingShadowBoundaries(node));
228
229     // Push true if this node full clips its contents, or if a parent already has fully
230     // clipped and this is not a node that ignores its container's clip.
231     stack.push(fullyClipsContents(node) || (stack.top() && !ignoresContainerClip(node)));
232 }
233
234 static void setUpFullyClippedStack(BitStack& stack, Node& node)
235 {
236     // Put the nodes in a vector so we can iterate in reverse order.
237     Vector<Node*, 100> ancestry;
238     for (Node* parent = node.parentOrShadowHostNode(); parent; parent = parent->parentOrShadowHostNode())
239         ancestry.append(parent);
240
241     // Call pushFullyClippedState on each node starting with the earliest ancestor.
242     size_t size = ancestry.size();
243     for (size_t i = 0; i < size; ++i)
244         pushFullyClippedState(stack, *ancestry[size - i - 1]);
245     pushFullyClippedState(stack, node);
246
247     ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));
248 }
249
250 // FIXME: editingIgnoresContent and isRendererReplacedElement try to do the same job.
251 // It's not good to have both of them.
252 bool isRendererReplacedElement(RenderObject* renderer)
253 {
254     if (!renderer)
255         return false;
256     
257     if (renderer->isImage() || renderer->isWidget() || renderer->isMedia())
258         return true;
259
260     if (is<Element>(renderer->node())) {
261         Element& element = downcast<Element>(*renderer->node());
262         if (is<HTMLFormControlElement>(element) || is<HTMLLegendElement>(element) || is<HTMLMeterElement>(element) || is<HTMLProgressElement>(element))
263             return true;
264         if (equalIgnoringCase(element.fastGetAttribute(roleAttr), "img"))
265             return true;
266     }
267
268     return false;
269 }
270
271 // --------
272
273 inline void TextIteratorCopyableText::reset()
274 {
275     m_singleCharacter = 0;
276     m_string = String();
277     m_offset = 0;
278     m_length = 0;
279 }
280
281 inline void TextIteratorCopyableText::set(String&& string)
282 {
283     m_singleCharacter = 0;
284     m_string = WTF::move(string);
285     m_offset = 0;
286     m_length = m_string.length();
287 }
288
289 inline void TextIteratorCopyableText::set(String&& string, unsigned offset, unsigned length)
290 {
291     ASSERT(offset < string.length());
292     ASSERT(length);
293     ASSERT(length <= string.length() - offset);
294
295     m_singleCharacter = 0;
296     m_string = WTF::move(string);
297     m_offset = offset;
298     m_length = length;
299 }
300
301 inline void TextIteratorCopyableText::set(UChar singleCharacter)
302 {
303     m_singleCharacter = singleCharacter;
304     m_string = String();
305     m_offset = 0;
306     m_length = 0;
307 }
308
309 void TextIteratorCopyableText::appendToStringBuilder(StringBuilder& builder) const
310 {
311     if (m_singleCharacter)
312         builder.append(m_singleCharacter);
313     else
314         builder.append(m_string, m_offset, m_length);
315 }
316
317 // --------
318
319 TextIterator::TextIterator(const Range* range, TextIteratorBehavior behavior)
320     : m_behavior(behavior)
321     , m_handledNode(false)
322     , m_handledChildren(false)
323     , m_startContainer(nullptr)
324     , m_startOffset(0)
325     , m_endContainer(nullptr)
326     , m_endOffset(0)
327     , m_positionNode(nullptr)
328     , m_needsAnotherNewline(false)
329     , m_textBox(nullptr)
330     , m_remainingTextBox(nullptr)
331     , m_firstLetterText(nullptr)
332     , m_lastTextNode(nullptr)
333     , m_lastTextNodeEndedWithCollapsedSpace(false)
334     , m_lastCharacter(0)
335     , m_sortedTextBoxesPosition(0)
336     , m_hasEmitted(false)
337     , m_handledFirstLetter(false)
338 {
339     // FIXME: Only m_positionNode above needs to be initialized if range is null.
340     if (!range)
341         return;
342
343     range->ownerDocument().updateLayoutIgnorePendingStylesheets();
344
345     m_startContainer = range->startContainer();
346     if (!m_startContainer)
347         return;
348     ASSERT(range->endContainer());
349
350     // Callers should be handing us well-formed ranges. If we discover that this isn't
351     // the case, we could consider changing this assertion to an early return.
352     ASSERT(range->boundaryPointsValid());
353
354     m_startOffset = range->startOffset();
355     m_endContainer = range->endContainer();
356     m_endOffset = range->endOffset();
357
358     // Set up the current node for processing.
359     m_node = range->firstNode();
360     if (!m_node)
361         return;
362     setUpFullyClippedStack(m_fullyClippedStack, *m_node);
363     m_offset = m_node == m_startContainer ? m_startOffset : 0;
364
365     m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(*m_endContainer, m_endOffset);
366
367 #ifndef NDEBUG
368     // Need this just because of the assert in advance().
369     m_positionNode = m_node;
370 #endif
371
372     advance();
373 }
374
375 TextIterator::~TextIterator()
376 {
377 }
378
379 void TextIterator::advance()
380 {
381     ASSERT(!atEnd());
382
383     // reset the run information
384     m_positionNode = nullptr;
385     m_copyableText.reset();
386     m_text = StringView();
387
388     // handle remembered node that needed a newline after the text node's newline
389     if (m_needsAnotherNewline) {
390         // Emit the extra newline, and position it *inside* m_node, after m_node's 
391         // contents, in case it's a block, in the same way that we position the first 
392         // newline. The range for the emitted newline should start where the line
393         // break begins.
394         // FIXME: It would be cleaner if we emitted two newlines during the last 
395         // iteration, instead of using m_needsAnotherNewline.
396         Node& baseNode = m_node->lastChild() ? *m_node->lastChild() : *m_node;
397         emitCharacter('\n', *baseNode.parentNode(), &baseNode, 1, 1);
398         m_needsAnotherNewline = false;
399         return;
400     }
401
402     if (!m_textBox && m_remainingTextBox) {
403         m_textBox = m_remainingTextBox;
404         m_remainingTextBox = nullptr;
405         m_firstLetterText = nullptr;
406         m_offset = 0;
407     }
408     // handle remembered text box
409     if (m_textBox) {
410         handleTextBox();
411         if (m_positionNode)
412             return;
413     }
414
415     while (m_node && m_node != m_pastEndNode) {
416         if ((m_behavior & TextIteratorStopsOnFormControls) && HTMLFormControlElement::enclosingFormControlElement(m_node))
417             return;
418
419         // if the range ends at offset 0 of an element, represent the
420         // position, but not the content, of that element e.g. if the
421         // node is a blockflow element, emit a newline that
422         // precedes the element
423         if (m_node == m_endContainer && !m_endOffset) {
424             representNodeOffsetZero();
425             m_node = nullptr;
426             return;
427         }
428         
429         auto* renderer = m_node->renderer();
430         if (!renderer) {
431             m_handledNode = true;
432             m_handledChildren = true;
433         } else {
434             // handle current node according to its type
435             if (!m_handledNode) {
436                 if (renderer->isText() && m_node->isTextNode())
437                     m_handledNode = handleTextNode();
438                 else if (isRendererReplacedElement(renderer))
439                     m_handledNode = handleReplacedElement();
440                 else
441                     m_handledNode = handleNonTextNode();
442                 if (m_positionNode)
443                     return;
444             }
445         }
446
447         // find a new current node to handle in depth-first manner,
448         // calling exitNode() as we come back thru a parent node
449         Node* next = m_handledChildren ? nullptr : m_node->firstChild();
450         m_offset = 0;
451         if (!next) {
452             next = m_node->nextSibling();
453             if (!next) {
454                 bool pastEnd = NodeTraversal::next(*m_node) == m_pastEndNode;
455                 Node* parentNode = m_node->parentOrShadowHostNode();
456                 while (!next && parentNode) {
457                     if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))
458                         return;
459                     bool haveRenderer = m_node->renderer();
460                     m_node = parentNode;
461                     m_fullyClippedStack.pop();
462                     parentNode = m_node->parentOrShadowHostNode();
463                     if (haveRenderer)
464                         exitNode();
465                     if (m_positionNode) {
466                         m_handledNode = true;
467                         m_handledChildren = true;
468                         return;
469                     }
470                     next = m_node->nextSibling();
471                 }
472             }
473             m_fullyClippedStack.pop();            
474         }
475
476         // set the new current node
477         m_node = next;
478         if (m_node)
479             pushFullyClippedState(m_fullyClippedStack, *m_node);
480         m_handledNode = false;
481         m_handledChildren = false;
482         m_handledFirstLetter = false;
483         m_firstLetterText = nullptr;
484
485         // how would this ever be?
486         if (m_positionNode)
487             return;
488     }
489 }
490
491 static bool hasVisibleTextNode(RenderText& renderer)
492 {
493     if (renderer.style().visibility() == VISIBLE)
494         return true;
495     if (is<RenderTextFragment>(renderer)) {
496         if (auto firstLetter = downcast<RenderTextFragment>(renderer).firstLetter()) {
497             if (firstLetter->style().visibility() == VISIBLE)
498                 return true;
499         }
500     }
501     return false;
502 }
503
504 bool TextIterator::handleTextNode()
505 {
506     Text& textNode = downcast<Text>(*m_node);
507
508     if (m_fullyClippedStack.top() && !(m_behavior & TextIteratorIgnoresStyleVisibility))
509         return false;
510
511     auto& renderer = *textNode.renderer();
512     const auto* previousTextNode = m_lastTextNode;
513     m_lastTextNode = &textNode;
514     String rendererText = renderer.text();
515
516     // handle pre-formatted text
517     if (!renderer.style().collapseWhiteSpace()) {
518         int runStart = m_offset;
519         if (m_lastTextNodeEndedWithCollapsedSpace && hasVisibleTextNode(renderer)) {
520             emitCharacter(' ', textNode, nullptr, runStart, runStart);
521             return false;
522         }
523         if (!m_handledFirstLetter && is<RenderTextFragment>(renderer) && !m_offset) {
524             handleTextNodeFirstLetter(downcast<RenderTextFragment>(renderer));
525             if (m_firstLetterText) {
526                 String firstLetter = m_firstLetterText->text();
527                 emitText(textNode, *m_firstLetterText, m_offset, m_offset + firstLetter.length());
528                 m_firstLetterText = nullptr;
529                 m_textBox = nullptr;
530                 return false;
531             }
532         }
533         if (renderer.style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility))
534             return false;
535         int rendererTextLength = rendererText.length();
536         int end = (&textNode == m_endContainer) ? m_endOffset : INT_MAX;
537         int runEnd = std::min(rendererTextLength, end);
538
539         if (runStart >= runEnd)
540             return true;
541
542         emitText(textNode, renderer, runStart, runEnd);
543         return true;
544     }
545
546     if (const auto* layout = renderer.simpleLineLayout()) {
547         if (renderer.style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility))
548             return true;
549         // Use the simple layout runs to iterate over the text content.
550         ASSERT(renderer.parent() && is<RenderBlockFlow>(renderer.parent()));
551         unsigned endPosition = (m_node == m_endContainer) ? static_cast<unsigned>(m_endOffset) : rendererText.length();
552         const auto& blockFlow = downcast<RenderBlockFlow>(*renderer.parent());
553         if (!m_flowRunResolverCache || &m_flowRunResolverCache->flow() != &blockFlow) {
554             m_flowRunResolverCache = std::make_unique<SimpleLineLayout::RunResolver>(blockFlow, *layout);
555             m_previousTextLengthInFlow = 0;
556         } else if (previousTextNode && previousTextNode != &textNode) {
557             // Simple line layout run positions are all absolute to the parent flow.
558             // Offsetting is required when multiple renderers are present.
559             m_previousTextLengthInFlow += previousTextNode->renderer()->text()->length();
560         }
561         // Skip to m_offset position.
562         auto range = m_flowRunResolverCache->rangeForRenderer(renderer);
563         auto it = range.begin();
564         auto end = range.end();
565         while (it != end && (*it).end() <= (static_cast<unsigned>(m_offset) + m_previousTextLengthInFlow))
566             ++it;
567         if (m_nextRunNeedsWhitespace && rendererText[m_offset - 1] == '\n') {
568             emitCharacter(' ', textNode, nullptr, m_offset, m_offset + 1);
569             return it == end;
570         }
571         if (it == end) {
572             // Collapsed trailing whitespace.
573             m_offset = endPosition;
574             m_lastTextNodeEndedWithCollapsedSpace = true;
575             return true;
576         }
577         if (m_nextRunNeedsWhitespace) {
578             emitCharacter(' ', textNode, nullptr, m_offset, m_offset + 1);
579             return false;
580         }
581         const auto run = *it;
582         ASSERT(run.end() - run.start() <= rendererText.length());
583         // contentStart skips leading whitespace.
584         unsigned contentStart = std::max<unsigned>(m_offset, run.start() - m_previousTextLengthInFlow);
585         unsigned contentEnd = std::min(endPosition, run.end() - m_previousTextLengthInFlow);
586         // Check if whitespace adjustment is needed when crossing renderer boundary.
587         if (previousTextNode && previousTextNode != &textNode) {
588             bool lastCharacterIsNotWhitespace = m_lastCharacter && !renderer.style().isCollapsibleWhiteSpace(m_lastCharacter);
589             bool addTrailingWhitespaceForPrevious = m_lastTextNodeEndedWithCollapsedSpace && lastCharacterIsNotWhitespace;
590             bool leadingWhitespaceIsNeededForCurrent = contentStart > static_cast<unsigned>(m_offset) && lastCharacterIsNotWhitespace;
591             if (addTrailingWhitespaceForPrevious || leadingWhitespaceIsNeededForCurrent) {
592                 emitCharacter(' ', textNode, nullptr, m_offset, m_offset + 1);
593                 return false;
594             }
595         }
596         // \n \t single whitespace characters need replacing so that the new line/tab character won't show up.
597         unsigned stopPosition = contentStart;
598         while (stopPosition < contentEnd) {
599             if (rendererText[stopPosition] == '\n' || rendererText[stopPosition] == '\t') {
600                 emitText(textNode, renderer, contentStart, stopPosition);
601                 m_offset = stopPosition + 1;
602                 m_nextRunNeedsWhitespace = true;
603                 return false;
604             }
605             ++stopPosition;
606         }
607         emitText(textNode, renderer, contentStart, contentEnd);
608         // When line ending with collapsed whitespace is present, we need to carry over one whitespace: foo(end of line)bar -> foo bar (otherwise we would end up with foobar).
609         m_nextRunNeedsWhitespace = run.isEndOfLine() && contentEnd < endPosition && renderer.style().isCollapsibleWhiteSpace(rendererText[contentEnd]);
610         m_offset = contentEnd;
611         return static_cast<unsigned>(m_offset) == endPosition;
612     }
613
614     if (renderer.firstTextBox())
615         m_textBox = renderer.firstTextBox();
616
617     bool shouldHandleFirstLetter = !m_handledFirstLetter && is<RenderTextFragment>(renderer) && !m_offset;
618     if (shouldHandleFirstLetter)
619         handleTextNodeFirstLetter(downcast<RenderTextFragment>(renderer));
620
621     if (!renderer.firstTextBox() && rendererText.length() && !shouldHandleFirstLetter) {
622         if (renderer.style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility))
623             return false;
624         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
625         return true;
626     }
627
628     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
629     auto& boxesRenderer = m_firstLetterText ? *m_firstLetterText : renderer;
630     if (boxesRenderer.containsReversedText()) {
631         m_sortedTextBoxes.clear();
632         for (InlineTextBox* textBox = boxesRenderer.firstTextBox(); textBox; textBox = textBox->nextTextBox())
633             m_sortedTextBoxes.append(textBox);
634         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), InlineTextBox::compareByStart);
635         m_sortedTextBoxesPosition = 0;
636         m_textBox = m_sortedTextBoxes.isEmpty() ? nullptr : m_sortedTextBoxes[0];
637     }
638
639     handleTextBox();
640     return true;
641 }
642
643 void TextIterator::handleTextBox()
644 {    
645     Text& textNode = downcast<Text>(*m_node);
646
647     auto& renderer = m_firstLetterText ? *m_firstLetterText : *textNode.renderer();
648     if (renderer.style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility)) {
649         m_textBox = nullptr;
650         return;
651     }
652     String rendererText = renderer.text();
653     unsigned start = m_offset;
654     unsigned end = (&textNode == m_endContainer) ? static_cast<unsigned>(m_endOffset) : UINT_MAX;
655     while (m_textBox) {
656         unsigned textBoxStart = m_textBox->start();
657         unsigned runStart = std::max(textBoxStart, start);
658
659         // Check for collapsed space at the start of this run.
660         InlineTextBox* firstTextBox = renderer.containsReversedText() ? (m_sortedTextBoxes.isEmpty() ? nullptr : m_sortedTextBoxes[0]) : renderer.firstTextBox();
661         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace || (m_textBox == firstTextBox && textBoxStart == runStart && runStart);
662         if (needSpace && !renderer.style().isCollapsibleWhiteSpace(m_lastCharacter) && m_lastCharacter) {
663             if (m_lastTextNode == &textNode && runStart && rendererText[runStart - 1] == ' ') {
664                 unsigned spaceRunStart = runStart - 1;
665                 while (spaceRunStart && rendererText[spaceRunStart - 1] == ' ')
666                     --spaceRunStart;
667                 emitText(textNode, renderer, spaceRunStart, spaceRunStart + 1);
668             } else
669                 emitCharacter(' ', textNode, nullptr, runStart, runStart);
670             return;
671         }
672         unsigned textBoxEnd = textBoxStart + m_textBox->len();
673         unsigned runEnd = std::min(textBoxEnd, end);
674         
675         // Determine what the next text box will be, but don't advance yet
676         InlineTextBox* nextTextBox = nullptr;
677         if (renderer.containsReversedText()) {
678             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
679                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
680         } else 
681             nextTextBox = m_textBox->nextTextBox();
682         ASSERT(!nextTextBox || &nextTextBox->renderer() == &renderer);
683
684         if (runStart < runEnd) {
685             // Handle either a single newline character (which becomes a space),
686             // or a run of characters that does not include a newline.
687             // This effectively translates newlines to spaces without copying the text.
688             if (rendererText[runStart] == '\n') {
689                 emitCharacter(' ', textNode, nullptr, runStart, runStart + 1);
690                 m_offset = runStart + 1;
691             } else {
692                 size_t subrunEnd = rendererText.find('\n', runStart);
693                 if (subrunEnd == notFound || subrunEnd > runEnd) {
694                     subrunEnd = runEnd;
695                     bool lastSpaceCollapsedByNextNonTextBox = !nextTextBox && (m_behavior & TextIteratorBehavesAsIfNodesFollowing) && rendererText.length() > runEnd;
696                     if (lastSpaceCollapsedByNextNonTextBox)
697                         ++subrunEnd; // runEnd stopped before last space. Increment by one to restore the space.
698                 }
699                 m_offset = subrunEnd;
700                 emitText(textNode, renderer, runStart, subrunEnd);
701             }
702
703             // If we are doing a subrun that doesn't go to the end of the text box,
704             // come back again to finish handling this text box; don't advance to the next one.
705             if (static_cast<unsigned>(m_positionEndOffset) < textBoxEnd)
706                 return;
707
708             // Advance and return
709             unsigned nextRunStart = nextTextBox ? nextTextBox->start() : rendererText.length();
710             if (nextRunStart > runEnd)
711                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
712             m_textBox = nextTextBox;
713             if (renderer.containsReversedText())
714                 ++m_sortedTextBoxesPosition;
715             return;
716         }
717         // Advance and continue
718         m_textBox = nextTextBox;
719         if (renderer.containsReversedText())
720             ++m_sortedTextBoxesPosition;
721     }
722     if (!m_textBox && m_remainingTextBox) {
723         m_textBox = m_remainingTextBox;
724         m_remainingTextBox = nullptr;
725         m_firstLetterText = nullptr;
726         m_offset = 0;
727         handleTextBox();
728     }
729 }
730
731 static inline RenderText* firstRenderTextInFirstLetter(RenderBoxModelObject* firstLetter)
732 {
733     if (!firstLetter)
734         return nullptr;
735
736     // FIXME: Should this check descendent objects?
737     return childrenOfType<RenderText>(*firstLetter).first();
738 }
739
740 void TextIterator::handleTextNodeFirstLetter(RenderTextFragment& renderer)
741 {
742     if (auto* firstLetter = renderer.firstLetter()) {
743         if (firstLetter->style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility))
744             return;
745         if (auto* firstLetterText = firstRenderTextInFirstLetter(firstLetter)) {
746             m_handledFirstLetter = true;
747             m_remainingTextBox = m_textBox;
748             m_textBox = firstLetterText->firstTextBox();
749             m_sortedTextBoxes.clear();
750             m_firstLetterText = firstLetterText;
751         }
752     }
753     m_handledFirstLetter = true;
754 }
755
756 bool TextIterator::handleReplacedElement()
757 {
758     if (m_fullyClippedStack.top())
759         return false;
760
761     auto& renderer = *m_node->renderer();
762     if (renderer.style().visibility() != VISIBLE && !(m_behavior & TextIteratorIgnoresStyleVisibility))
763         return false;
764
765     if (m_lastTextNodeEndedWithCollapsedSpace) {
766         emitCharacter(' ', *m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
767         return false;
768     }
769
770     if ((m_behavior & TextIteratorEntersTextControls) && is<RenderTextControl>(renderer)) {
771         if (TextControlInnerTextElement* innerTextElement = downcast<RenderTextControl>(renderer).textFormControlElement().innerTextElement()) {
772             m_node = innerTextElement->containingShadowRoot();
773             pushFullyClippedState(m_fullyClippedStack, *m_node);
774             m_offset = 0;
775             return false;
776         }
777     }
778
779     m_hasEmitted = true;
780
781     if ((m_behavior & TextIteratorEmitsObjectReplacementCharacters) && renderer.isReplaced()) {
782         emitCharacter(objectReplacementCharacter, *m_node->parentNode(), m_node, 0, 1);
783         // Don't process subtrees for embedded objects. If the text there is required,
784         // it must be explicitly asked by specifying a range falling inside its boundaries.
785         m_handledChildren = true;
786         return true;
787     }
788
789     if (m_behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions) {
790         // We want replaced elements to behave like punctuation for boundary 
791         // finding, and to simply take up space for the selection preservation 
792         // code in moveParagraphs, so we use a comma.
793         emitCharacter(',', *m_node->parentNode(), m_node, 0, 1);
794         return true;
795     }
796
797     m_positionNode = m_node->parentNode();
798     m_positionOffsetBaseNode = m_node;
799     m_positionStartOffset = 0;
800     m_positionEndOffset = 1;
801
802     if ((m_behavior & TextIteratorEmitsImageAltText) && is<RenderImage>(renderer)) {
803         String altText = downcast<RenderImage>(renderer).altText();
804         if (unsigned length = altText.length()) {
805             m_lastCharacter = altText[length - 1];
806             m_copyableText.set(WTF::move(altText));
807             m_text = m_copyableText.text();
808             return true;
809         }
810     }
811
812     m_copyableText.reset();
813     m_text = StringView();
814     m_lastCharacter = 0;
815     return true;
816 }
817
818 static bool shouldEmitTabBeforeNode(Node& node)
819 {
820     auto* renderer = node.renderer();
821     
822     // Table cells are delimited by tabs.
823     if (!renderer || !isTableCell(&node))
824         return false;
825     
826     // Want a tab before every cell other than the first one.
827     RenderTableCell& cell = downcast<RenderTableCell>(*renderer);
828     RenderTable* table = cell.table();
829     return table && (table->cellBefore(&cell) || table->cellAbove(&cell));
830 }
831
832 static bool shouldEmitNewlineForNode(Node* node, bool emitsOriginalText)
833 {
834     auto* renderer = node->renderer();
835     if (!(renderer ? renderer->isBR() : node->hasTagName(brTag)))
836         return false;
837     return emitsOriginalText || !(node->isInShadowTree() && node->shadowHost()->toInputElement());
838 }
839
840 static bool hasHeaderTag(HTMLElement& element)
841 {
842     return element.hasTagName(h1Tag)
843         || element.hasTagName(h2Tag)
844         || element.hasTagName(h3Tag)
845         || element.hasTagName(h4Tag)
846         || element.hasTagName(h5Tag)
847         || element.hasTagName(h6Tag);
848 }
849
850 static bool shouldEmitNewlinesBeforeAndAfterNode(Node& node)
851 {
852     // Block flow (versus inline flow) is represented by having
853     // a newline both before and after the element.
854     auto* renderer = node.renderer();
855     if (!renderer) {
856         if (!is<HTMLElement>(node))
857             return false;
858         auto& element = downcast<HTMLElement>(node);
859         return hasHeaderTag(element)
860             || element.hasTagName(blockquoteTag)
861             || element.hasTagName(ddTag)
862             || element.hasTagName(divTag)
863             || element.hasTagName(dlTag)
864             || element.hasTagName(dtTag)
865             || element.hasTagName(hrTag)
866             || element.hasTagName(liTag)
867             || element.hasTagName(listingTag)
868             || element.hasTagName(olTag)
869             || element.hasTagName(pTag)
870             || element.hasTagName(preTag)
871             || element.hasTagName(trTag)
872             || element.hasTagName(ulTag);
873     }
874     
875     // Need to make an exception for table cells, because they are blocks, but we
876     // want them tab-delimited rather than having newlines before and after.
877     if (isTableCell(&node))
878         return false;
879     
880     // Need to make an exception for table row elements, because they are neither
881     // "inline" or "RenderBlock", but we want newlines for them.
882     if (is<RenderTableRow>(*renderer)) {
883         RenderTable* table = downcast<RenderTableRow>(*renderer).table();
884         if (table && !table->isInline())
885             return true;
886     }
887     
888     return !renderer->isInline()
889         && is<RenderBlock>(*renderer)
890         && !renderer->isFloatingOrOutOfFlowPositioned()
891         && !renderer->isBody()
892         && !renderer->isRubyText();
893 }
894
895 static bool shouldEmitNewlineAfterNode(Node& node)
896 {
897     // FIXME: It should be better but slower to create a VisiblePosition here.
898     if (!shouldEmitNewlinesBeforeAndAfterNode(node))
899         return false;
900     // Check if this is the very last renderer in the document.
901     // If so, then we should not emit a newline.
902     Node* subsequentNode = &node;
903     while ((subsequentNode = NodeTraversal::nextSkippingChildren(*subsequentNode))) {
904         if (subsequentNode->renderer())
905             return true;
906     }
907     return false;
908 }
909
910 static bool shouldEmitNewlineBeforeNode(Node& node)
911 {
912     return shouldEmitNewlinesBeforeAndAfterNode(node); 
913 }
914
915 static bool shouldEmitExtraNewlineForNode(Node& node)
916 {
917     // When there is a significant collapsed bottom margin, emit an extra
918     // newline for a more realistic result. We end up getting the right
919     // result even without margin collapsing. For example: <div><p>text</p></div>
920     // will work right even if both the <div> and the <p> have bottom margins.
921
922     auto* renderer = node.renderer();
923     if (!is<RenderBox>(renderer))
924         return false;
925
926     // NOTE: We only do this for a select set of nodes, and WinIE appears not to do this at all.
927     if (!is<HTMLElement>(node))
928         return false;
929
930     HTMLElement& element = downcast<HTMLElement>(node);
931     if (!hasHeaderTag(element) && !is<HTMLParagraphElement>(element))
932         return false;
933
934     int bottomMargin = downcast<RenderBox>(*renderer).collapsedMarginAfter();
935     int fontSize = downcast<RenderBox>(*renderer).style().fontDescription().computedPixelSize();
936     return bottomMargin * 2 >= fontSize;
937 }
938
939 static int collapsedSpaceLength(RenderText& renderer, int textEnd)
940 {
941     StringImpl& text = *renderer.text();
942     unsigned length = text.length();
943     for (unsigned i = textEnd; i < length; ++i) {
944         if (!renderer.style().isCollapsibleWhiteSpace(text[i]))
945             return i - textEnd;
946     }
947     return length - textEnd;
948 }
949
950 static int maxOffsetIncludingCollapsedSpaces(Node& node)
951 {
952     int offset = caretMaxOffset(&node);
953     if (auto* renderer = node.renderer()) {
954         if (is<RenderText>(*renderer))
955             offset += collapsedSpaceLength(downcast<RenderText>(*renderer), offset);
956     }
957     return offset;
958 }
959
960 // Whether or not we should emit a character as we enter m_node (if it's a container) or as we hit it (if it's atomic).
961 bool TextIterator::shouldRepresentNodeOffsetZero()
962 {
963     if ((m_behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions) && m_node->renderer() && m_node->renderer()->isTable())
964         return true;
965         
966     // Leave element positioned flush with start of a paragraph
967     // (e.g. do not insert tab before a table cell at the start of a paragraph)
968     if (m_lastCharacter == '\n')
969         return false;
970     
971     // Otherwise, show the position if we have emitted any characters
972     if (m_hasEmitted)
973         return true;
974     
975     // We've not emitted anything yet. Generally, there is no need for any positioning then.
976     // The only exception is when the element is visually not in the same line as
977     // the start of the range (e.g. the range starts at the end of the previous paragraph).
978     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we
979     // make quicker checks to possibly avoid that. Another check that we could make is
980     // is whether the inline vs block flow changed since the previous visible element.
981     // I think we're already in a special enough case that that won't be needed, tho.
982
983     // No character needed if this is the first node in the range.
984     if (m_node == m_startContainer)
985         return false;
986     
987     // If we are outside the start container's subtree, assume we need to emit.
988     // FIXME: m_startContainer could be an inline block
989     if (!m_node->isDescendantOf(m_startContainer))
990         return true;
991
992     // If we started as m_startContainer offset 0 and the current node is a descendant of
993     // the start container, we already had enough context to correctly decide whether to
994     // emit after a preceding block. We chose not to emit (m_hasEmitted is false),
995     // so don't second guess that now.
996     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably
997     // immaterial since we likely would have already emitted something by now.
998     if (m_startOffset == 0)
999         return false;
1000         
1001     // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning.
1002     // Additionally, if the range we are iterating over contains huge sections of unrendered content, 
1003     // we would create VisiblePositions on every call to this function without this check.
1004     if (!m_node->renderer() || m_node->renderer()->style().visibility() != VISIBLE
1005         || (is<RenderBlockFlow>(*m_node->renderer()) && !downcast<RenderBlockFlow>(*m_node->renderer()).height() && !is<HTMLBodyElement>(*m_node)))
1006         return false;
1007
1008     // The startPos.isNotNull() check is needed because the start could be before the body,
1009     // and in that case we'll get null. We don't want to put in newlines at the start in that case.
1010     // The currPos.isNotNull() check is needed because positions in non-HTML content
1011     // (like SVG) do not have visible positions, and we don't want to emit for them either.
1012     VisiblePosition startPos = VisiblePosition(Position(m_startContainer, m_startOffset, Position::PositionIsOffsetInAnchor), DOWNSTREAM);
1013     VisiblePosition currPos = VisiblePosition(positionBeforeNode(m_node), DOWNSTREAM);
1014     return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos);
1015 }
1016
1017 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node& node)
1018 {
1019     return node.renderer() && node.renderer()->isTable() && (node.renderer()->isInline() || (m_behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions));
1020 }
1021
1022 void TextIterator::representNodeOffsetZero()
1023 {
1024     // Emit a character to show the positioning of m_node.
1025     
1026     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 
1027     // create VisiblePositions, which is expensive. So, we perform the inexpensive checks
1028     // on m_node to see if it necessitates emitting a character first and will early return 
1029     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
1030     if (shouldEmitTabBeforeNode(*m_node)) {
1031         if (shouldRepresentNodeOffsetZero())
1032             emitCharacter('\t', *m_node->parentNode(), m_node, 0, 0);
1033     } else if (shouldEmitNewlineBeforeNode(*m_node)) {
1034         if (shouldRepresentNodeOffsetZero())
1035             emitCharacter('\n', *m_node->parentNode(), m_node, 0, 0);
1036     } else if (shouldEmitSpaceBeforeAndAfterNode(*m_node)) {
1037         if (shouldRepresentNodeOffsetZero())
1038             emitCharacter(' ', *m_node->parentNode(), m_node, 0, 0);
1039     }
1040 }
1041
1042 bool TextIterator::handleNonTextNode()
1043 {
1044     if (shouldEmitNewlineForNode(m_node, m_behavior & TextIteratorEmitsOriginalText))
1045         emitCharacter('\n', *m_node->parentNode(), m_node, 0, 1);
1046     else if ((m_behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions) && m_node->renderer() && m_node->renderer()->isHR())
1047         emitCharacter(' ', *m_node->parentNode(), m_node, 0, 1);
1048     else
1049         representNodeOffsetZero();
1050
1051     return true;
1052 }
1053
1054 void TextIterator::exitNode()
1055 {
1056     // prevent emitting a newline when exiting a collapsed block at beginning of the range
1057     // FIXME: !m_hasEmitted does not necessarily mean there was a collapsed block... it could
1058     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
1059     // therefore look like a blank line.
1060     if (!m_hasEmitted)
1061         return;
1062         
1063     // Emit with a position *inside* m_node, after m_node's contents, in 
1064     // case it is a block, because the run should start where the 
1065     // emitted character is positioned visually.
1066     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
1067     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
1068     // the logic in _web_attributedStringFromRange match. We'll get that for free when we switch to use
1069     // TextIterator in _web_attributedStringFromRange.
1070     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
1071     if (m_lastTextNode && shouldEmitNewlineAfterNode(*m_node)) {
1072         // use extra newline to represent margin bottom, as needed
1073         bool addNewline = shouldEmitExtraNewlineForNode(*m_node);
1074         
1075         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
1076         // contain a VisiblePosition when doing selection preservation.
1077         if (m_lastCharacter != '\n') {
1078             // insert a newline with a position following this block's contents.
1079             emitCharacter('\n', *baseNode->parentNode(), baseNode, 1, 1);
1080             // remember whether to later add a newline for the current node
1081             ASSERT(!m_needsAnotherNewline);
1082             m_needsAnotherNewline = addNewline;
1083         } else if (addNewline)
1084             // insert a newline with a position following this block's contents.
1085             emitCharacter('\n', *baseNode->parentNode(), baseNode, 1, 1);
1086     }
1087     
1088     // If nothing was emitted, see if we need to emit a space.
1089     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(*m_node))
1090         emitCharacter(' ', *baseNode->parentNode(), baseNode, 1, 1);
1091 }
1092
1093 void TextIterator::emitCharacter(UChar character, Node& characterNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset)
1094 {
1095     m_hasEmitted = true;
1096     
1097     // remember information with which to construct the TextIterator::range()
1098     m_positionNode = &characterNode;
1099     m_positionOffsetBaseNode = offsetBaseNode;
1100     m_positionStartOffset = textStartOffset;
1101     m_positionEndOffset = textEndOffset;
1102
1103     m_copyableText.set(character);
1104     m_text = m_copyableText.text();
1105     m_lastCharacter = character;
1106     m_lastTextNodeEndedWithCollapsedSpace = false;
1107     m_nextRunNeedsWhitespace = false;
1108 }
1109
1110 void TextIterator::emitText(Text& textNode, RenderText& renderer, int textStartOffset, int textEndOffset)
1111 {
1112     ASSERT(textStartOffset >= 0);
1113     ASSERT(textEndOffset >= 0);
1114     ASSERT(textStartOffset <= textEndOffset);
1115
1116     // FIXME: This probably yields the wrong offsets when text-transform: lowercase turns a single character into two characters.
1117     String string = (m_behavior & TextIteratorEmitsOriginalText) ? renderer.originalText()
1118         : ((m_behavior & TextIteratorEmitsTextsWithoutTranscoding) ? renderer.textWithoutConvertingBackslashToYenSymbol() : renderer.text());
1119
1120     ASSERT(string.length() >= static_cast<unsigned>(textEndOffset));
1121
1122     m_positionNode = &textNode;
1123     m_positionOffsetBaseNode = nullptr;
1124     m_positionStartOffset = textStartOffset;
1125     m_positionEndOffset = textEndOffset;
1126
1127     m_lastCharacter = string[textEndOffset - 1];
1128     m_copyableText.set(WTF::move(string), textStartOffset, textEndOffset - textStartOffset);
1129     m_text = m_copyableText.text();
1130
1131     m_lastTextNodeEndedWithCollapsedSpace = false;
1132     m_nextRunNeedsWhitespace = false;
1133     m_hasEmitted = true;
1134 }
1135
1136 Ref<Range> TextIterator::range() const
1137 {
1138     ASSERT(!atEnd());
1139
1140     // use the current run information, if we have it
1141     if (m_positionOffsetBaseNode) {
1142         unsigned index = m_positionOffsetBaseNode->computeNodeIndex();
1143         m_positionStartOffset += index;
1144         m_positionEndOffset += index;
1145         m_positionOffsetBaseNode = nullptr;
1146     }
1147     return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
1148 }
1149     
1150 Node* TextIterator::node() const
1151 {
1152     Ref<Range> textRange = range();
1153
1154     Node* node = textRange->startContainer();
1155     if (node->offsetInCharacters())
1156         return node;
1157     
1158     return node->traverseToChildAt(textRange->startOffset());
1159 }
1160
1161 // --------
1162
1163 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range& range, TextIteratorBehavior behavior)
1164     : m_behavior(behavior)
1165     , m_node(nullptr)
1166     , m_offset(0)
1167     , m_handledNode(false)
1168     , m_handledChildren(false)
1169     , m_startContainer(nullptr)
1170     , m_startOffset(0)
1171     , m_endContainer(nullptr)
1172     , m_endOffset(0)
1173     , m_positionNode(nullptr)
1174     , m_positionStartOffset(0)
1175     , m_positionEndOffset(0)
1176     , m_lastTextNode(nullptr)
1177     , m_lastCharacter(0)
1178     , m_havePassedStartContainer(false)
1179     , m_shouldHandleFirstLetter(false)
1180 {
1181     ASSERT(behavior == TextIteratorDefaultBehavior || behavior == TextIteratorStopsOnFormControls);
1182
1183     range.ownerDocument().updateLayoutIgnorePendingStylesheets();
1184
1185     Node* startNode = range.startContainer();
1186     if (!startNode)
1187         return;
1188     Node* endNode = range.endContainer();
1189     int startOffset = range.startOffset();
1190     int endOffset = range.endOffset();
1191
1192     if (!startNode->offsetInCharacters()) {
1193         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->countChildNodes())) {
1194             startNode = startNode->traverseToChildAt(startOffset);
1195             startOffset = 0;
1196         }
1197     }
1198     if (!endNode->offsetInCharacters()) {
1199         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->countChildNodes())) {
1200             endNode = endNode->traverseToChildAt(endOffset - 1);
1201             endOffset = lastOffsetInNode(endNode);
1202         }
1203     }
1204
1205     m_node = endNode;
1206     setUpFullyClippedStack(m_fullyClippedStack, *m_node);
1207     m_offset = endOffset;
1208     m_handledNode = false;
1209     m_handledChildren = endOffset == 0;
1210
1211     m_startContainer = startNode;
1212     m_startOffset = startOffset;
1213     m_endContainer = endNode;
1214     m_endOffset = endOffset;
1215     
1216 #ifndef NDEBUG
1217     // Need this just because of the assert.
1218     m_positionNode = endNode;
1219 #endif
1220
1221     m_lastTextNode = nullptr;
1222     m_lastCharacter = '\n';
1223
1224     m_havePassedStartContainer = false;
1225
1226     advance();
1227 }
1228
1229 void SimplifiedBackwardsTextIterator::advance()
1230 {
1231     ASSERT(!atEnd());
1232
1233     m_positionNode = nullptr;
1234     m_copyableText.reset();
1235     m_text = StringView();
1236
1237     if ((m_behavior & TextIteratorStopsOnFormControls) && HTMLFormControlElement::enclosingFormControlElement(m_node))
1238         return;
1239
1240     while (m_node && !m_havePassedStartContainer) {
1241         // Don't handle node if we start iterating at [node, 0].
1242         if (!m_handledNode && !(m_node == m_endContainer && !m_endOffset)) {
1243             auto* renderer = m_node->renderer();
1244             if (renderer && renderer->isText() && m_node->isTextNode()) {
1245                 if (renderer->style().visibility() == VISIBLE && m_offset > 0)
1246                     m_handledNode = handleTextNode();
1247             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
1248                 if (renderer->style().visibility() == VISIBLE && m_offset > 0)
1249                     m_handledNode = handleReplacedElement();
1250             } else
1251                 m_handledNode = handleNonTextNode();
1252             if (m_positionNode)
1253                 return;
1254         }
1255
1256         if (!m_handledChildren && m_node->hasChildNodes()) {
1257             m_node = m_node->lastChild();
1258             pushFullyClippedState(m_fullyClippedStack, *m_node);
1259         } else {
1260             // Exit empty containers as we pass over them or containers
1261             // where [container, 0] is where we started iterating.
1262             if (!m_handledNode
1263                     && canHaveChildrenForEditing(m_node)
1264                     && m_node->parentNode()
1265                     && (!m_node->lastChild() || (m_node == m_endContainer && !m_endOffset))) {
1266                 exitNode();
1267                 if (m_positionNode) {
1268                     m_handledNode = true;
1269                     m_handledChildren = true;
1270                     return;
1271                 }
1272             }
1273
1274             // Exit all other containers.
1275             while (!m_node->previousSibling()) {
1276                 if (!advanceRespectingRange(m_node->parentOrShadowHostNode()))
1277                     break;
1278                 m_fullyClippedStack.pop();
1279                 exitNode();
1280                 if (m_positionNode) {
1281                     m_handledNode = true;
1282                     m_handledChildren = true;
1283                     return;
1284                 }
1285             }
1286
1287             m_fullyClippedStack.pop();
1288             if (advanceRespectingRange(m_node->previousSibling()))
1289                 pushFullyClippedState(m_fullyClippedStack, *m_node);
1290             else
1291                 m_node = nullptr;
1292         }
1293
1294         // For the purpose of word boundary detection,
1295         // we should iterate all visible text and trailing (collapsed) whitespaces. 
1296         m_offset = m_node ? maxOffsetIncludingCollapsedSpaces(*m_node) : 0;
1297         m_handledNode = false;
1298         m_handledChildren = false;
1299         
1300         if (m_positionNode)
1301             return;
1302     }
1303 }
1304
1305 bool SimplifiedBackwardsTextIterator::handleTextNode()
1306 {
1307     Text& textNode = downcast<Text>(*m_node);
1308
1309     m_lastTextNode = &textNode;
1310
1311     int startOffset;
1312     int offsetInNode;
1313     RenderText* renderer = handleFirstLetter(startOffset, offsetInNode);
1314     if (!renderer)
1315         return true;
1316
1317     String text = renderer->text();
1318     if (!renderer->hasRenderedText() && text.length())
1319         return true;
1320
1321     if (startOffset + offsetInNode == m_offset) {
1322         ASSERT(!m_shouldHandleFirstLetter);
1323         return true;
1324     }
1325
1326     m_positionEndOffset = m_offset;
1327     m_offset = startOffset + offsetInNode;
1328     m_positionNode = m_node;
1329     m_positionStartOffset = m_offset;
1330
1331     ASSERT(m_positionStartOffset < m_positionEndOffset);
1332     ASSERT(m_positionStartOffset - offsetInNode >= 0);
1333     ASSERT(m_positionEndOffset - offsetInNode > 0);
1334     ASSERT(m_positionEndOffset - offsetInNode <= static_cast<int>(text.length()));
1335
1336     m_lastCharacter = text[m_positionEndOffset - offsetInNode - 1];
1337     m_copyableText.set(WTF::move(text), m_positionStartOffset - offsetInNode, m_positionEndOffset - m_positionStartOffset);
1338     m_text = m_copyableText.text();
1339
1340     return !m_shouldHandleFirstLetter;
1341 }
1342
1343 RenderText* SimplifiedBackwardsTextIterator::handleFirstLetter(int& startOffset, int& offsetInNode)
1344 {
1345     RenderText& renderer = downcast<RenderText>(*m_node->renderer());
1346     startOffset = (m_node == m_startContainer) ? m_startOffset : 0;
1347
1348     if (!is<RenderTextFragment>(renderer)) {
1349         offsetInNode = 0;
1350         return &renderer;
1351     }
1352
1353     RenderTextFragment& fragment = downcast<RenderTextFragment>(renderer);
1354     int offsetAfterFirstLetter = fragment.start();
1355     if (startOffset >= offsetAfterFirstLetter) {
1356         ASSERT(!m_shouldHandleFirstLetter);
1357         offsetInNode = offsetAfterFirstLetter;
1358         return &renderer;
1359     }
1360
1361     if (!m_shouldHandleFirstLetter && startOffset + offsetAfterFirstLetter < m_offset) {
1362         m_shouldHandleFirstLetter = true;
1363         offsetInNode = offsetAfterFirstLetter;
1364         return &renderer;
1365     }
1366
1367     m_shouldHandleFirstLetter = false;
1368     offsetInNode = 0;
1369     return firstRenderTextInFirstLetter(fragment.firstLetter());
1370 }
1371
1372 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
1373 {
1374     unsigned index = m_node->computeNodeIndex();
1375     // We want replaced elements to behave like punctuation for boundary 
1376     // finding, and to simply take up space for the selection preservation 
1377     // code in moveParagraphs, so we use a comma. Unconditionally emit
1378     // here because this iterator is only used for boundary finding.
1379     emitCharacter(',', *m_node->parentNode(), index, index + 1);
1380     return true;
1381 }
1382
1383 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
1384 {    
1385     // We can use a linefeed in place of a tab because this simple iterator is only used to
1386     // find boundaries, not actual content. A linefeed breaks words, sentences, and paragraphs.
1387     if (shouldEmitNewlineForNode(m_node, m_behavior & TextIteratorEmitsOriginalText) || shouldEmitNewlineAfterNode(*m_node) || shouldEmitTabBeforeNode(*m_node)) {
1388         unsigned index = m_node->computeNodeIndex();
1389         // The start of this emitted range is wrong. Ensuring correctness would require
1390         // VisiblePositions and so would be slow. previousBoundary expects this.
1391         emitCharacter('\n', *m_node->parentNode(), index + 1, index + 1);
1392     }
1393     return true;
1394 }
1395
1396 void SimplifiedBackwardsTextIterator::exitNode()
1397 {
1398     if (shouldEmitNewlineForNode(m_node, m_behavior & TextIteratorEmitsOriginalText) || shouldEmitNewlineBeforeNode(*m_node) || shouldEmitTabBeforeNode(*m_node)) {
1399         // The start of this emitted range is wrong. Ensuring correctness would require
1400         // VisiblePositions and so would be slow. previousBoundary expects this.
1401         emitCharacter('\n', *m_node, 0, 0);
1402     }
1403 }
1404
1405 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node& node, int startOffset, int endOffset)
1406 {
1407     m_positionNode = &node;
1408     m_positionStartOffset = startOffset;
1409     m_positionEndOffset = endOffset;
1410     m_copyableText.set(c);
1411     m_text = m_copyableText.text();
1412     m_lastCharacter = c;
1413 }
1414
1415 bool SimplifiedBackwardsTextIterator::advanceRespectingRange(Node* next)
1416 {
1417     if (!next)
1418         return false;
1419     m_havePassedStartContainer |= m_node == m_startContainer;
1420     if (m_havePassedStartContainer)
1421         return false;
1422     m_node = next;
1423     return true;
1424 }
1425
1426 Ref<Range> SimplifiedBackwardsTextIterator::range() const
1427 {
1428     ASSERT(!atEnd());
1429
1430     return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
1431 }
1432
1433 // --------
1434
1435 CharacterIterator::CharacterIterator(const Range& range, TextIteratorBehavior behavior)
1436     : m_underlyingIterator(&range, behavior)
1437     , m_offset(0)
1438     , m_runOffset(0)
1439     , m_atBreak(true)
1440 {
1441     while (!atEnd() && !m_underlyingIterator.text().length())
1442         m_underlyingIterator.advance();
1443 }
1444
1445 Ref<Range> CharacterIterator::range() const
1446 {
1447     Ref<Range> range = m_underlyingIterator.range();
1448     if (!m_underlyingIterator.atEnd()) {
1449         if (m_underlyingIterator.text().length() <= 1) {
1450             ASSERT(m_runOffset == 0);
1451         } else {
1452             Node* n = range->startContainer();
1453             ASSERT(n == range->endContainer());
1454             int offset = range->startOffset() + m_runOffset;
1455             range->setStart(n, offset);
1456             range->setEnd(n, offset + 1);
1457         }
1458     }
1459     return range;
1460 }
1461
1462 void CharacterIterator::advance(int count)
1463 {
1464     if (count <= 0) {
1465         ASSERT(count == 0);
1466         return;
1467     }
1468     
1469     m_atBreak = false;
1470
1471     // easy if there is enough left in the current m_underlyingIterator run
1472     int remaining = m_underlyingIterator.text().length() - m_runOffset;
1473     if (count < remaining) {
1474         m_runOffset += count;
1475         m_offset += count;
1476         return;
1477     }
1478
1479     // exhaust the current m_underlyingIterator run
1480     count -= remaining;
1481     m_offset += remaining;
1482     
1483     // move to a subsequent m_underlyingIterator run
1484     for (m_underlyingIterator.advance(); !atEnd(); m_underlyingIterator.advance()) {
1485         int runLength = m_underlyingIterator.text().length();
1486         if (!runLength)
1487             m_atBreak = true;
1488         else {
1489             // see whether this is m_underlyingIterator to use
1490             if (count < runLength) {
1491                 m_runOffset = count;
1492                 m_offset += count;
1493                 return;
1494             }
1495             
1496             // exhaust this m_underlyingIterator run
1497             count -= runLength;
1498             m_offset += runLength;
1499         }
1500     }
1501
1502     // ran to the end of the m_underlyingIterator... no more runs left
1503     m_atBreak = true;
1504     m_runOffset = 0;
1505 }
1506
1507 static Ref<Range> characterSubrange(Document& document, CharacterIterator& it, int offset, int length)
1508 {
1509     it.advance(offset);
1510     if (it.atEnd())
1511         return Range::create(document);
1512
1513     Ref<Range> start = it.range();
1514
1515     if (length > 1)
1516         it.advance(length - 1);
1517     if (it.atEnd())
1518         return Range::create(document);
1519
1520     Ref<Range> end = it.range();
1521
1522     return Range::create(document,
1523         start->startContainer(), start->startOffset(), 
1524         end->endContainer(), end->endOffset());
1525 }
1526
1527 BackwardsCharacterIterator::BackwardsCharacterIterator(const Range& range)
1528     : m_underlyingIterator(range, TextIteratorDefaultBehavior)
1529     , m_offset(0)
1530     , m_runOffset(0)
1531     , m_atBreak(true)
1532 {
1533     while (!atEnd() && !m_underlyingIterator.text().length())
1534         m_underlyingIterator.advance();
1535 }
1536
1537 Ref<Range> BackwardsCharacterIterator::range() const
1538 {
1539     Ref<Range> r = m_underlyingIterator.range();
1540     if (!m_underlyingIterator.atEnd()) {
1541         if (m_underlyingIterator.text().length() <= 1)
1542             ASSERT(m_runOffset == 0);
1543         else {
1544             Node* n = r->startContainer();
1545             ASSERT(n == r->endContainer());
1546             int offset = r->endOffset() - m_runOffset;
1547             r->setStart(n, offset - 1);
1548             r->setEnd(n, offset);
1549         }
1550     }
1551     return r;
1552 }
1553
1554 void BackwardsCharacterIterator::advance(int count)
1555 {
1556     if (count <= 0) {
1557         ASSERT(!count);
1558         return;
1559     }
1560
1561     m_atBreak = false;
1562
1563     int remaining = m_underlyingIterator.text().length() - m_runOffset;
1564     if (count < remaining) {
1565         m_runOffset += count;
1566         m_offset += count;
1567         return;
1568     }
1569
1570     count -= remaining;
1571     m_offset += remaining;
1572
1573     for (m_underlyingIterator.advance(); !atEnd(); m_underlyingIterator.advance()) {
1574         int runLength = m_underlyingIterator.text().length();
1575         if (runLength == 0)
1576             m_atBreak = true;
1577         else {
1578             if (count < runLength) {
1579                 m_runOffset = count;
1580                 m_offset += count;
1581                 return;
1582             }
1583             
1584             count -= runLength;
1585             m_offset += runLength;
1586         }
1587     }
1588
1589     m_atBreak = true;
1590     m_runOffset = 0;
1591 }
1592
1593 // --------
1594
1595 WordAwareIterator::WordAwareIterator(const Range& range)
1596     : m_underlyingIterator(&range)
1597     , m_didLookAhead(true) // so we consider the first chunk from the text iterator
1598 {
1599     advance(); // get in position over the first chunk of text
1600 }
1601
1602 // We're always in one of these modes:
1603 // - The current chunk in the text iterator is our current chunk
1604 //      (typically its a piece of whitespace, or text that ended with whitespace)
1605 // - The previous chunk in the text iterator is our current chunk
1606 //      (we looked ahead to the next chunk and found a word boundary)
1607 // - We built up our own chunk of text from many chunks from the text iterator
1608
1609 // FIXME: Performance could be bad for huge spans next to each other that don't fall on word boundaries.
1610
1611 void WordAwareIterator::advance()
1612 {
1613     m_previousText.reset();
1614     m_buffer.clear();
1615
1616     // If last time we did a look-ahead, start with that looked-ahead chunk now
1617     if (!m_didLookAhead) {
1618         ASSERT(!m_underlyingIterator.atEnd());
1619         m_underlyingIterator.advance();
1620     }
1621     m_didLookAhead = false;
1622
1623     // Go to next non-empty chunk 
1624     while (!m_underlyingIterator.atEnd() && !m_underlyingIterator.text().length())
1625         m_underlyingIterator.advance();
1626     if (m_underlyingIterator.atEnd())
1627         return;
1628
1629     while (1) {
1630         // If this chunk ends in whitespace we can just use it as our chunk.
1631         if (isSpaceOrNewline(m_underlyingIterator.text()[m_underlyingIterator.text().length() - 1]))
1632             return;
1633
1634         // If this is the first chunk that failed, save it in previousText before look ahead
1635         if (m_buffer.isEmpty())
1636             m_previousText = m_underlyingIterator.copyableText();
1637
1638         // Look ahead to next chunk. If it is whitespace or a break, we can use the previous stuff
1639         m_underlyingIterator.advance();
1640         if (m_underlyingIterator.atEnd() || !m_underlyingIterator.text().length() || isSpaceOrNewline(m_underlyingIterator.text()[0])) {
1641             m_didLookAhead = true;
1642             return;
1643         }
1644
1645         if (m_buffer.isEmpty()) {
1646             // Start gobbling chunks until we get to a suitable stopping point
1647             append(m_buffer, m_previousText.text());
1648             m_previousText.reset();
1649         }
1650         append(m_buffer, m_underlyingIterator.text());
1651     }
1652 }
1653
1654 StringView WordAwareIterator::text() const
1655 {
1656     if (!m_buffer.isEmpty())
1657         return StringView(m_buffer.data(), m_buffer.size());
1658     if (m_previousText.text().length())
1659         return m_previousText.text();
1660     return m_underlyingIterator.text();
1661 }
1662
1663 // --------
1664
1665 static inline UChar foldQuoteMark(UChar c)
1666 {
1667     switch (c) {
1668         case hebrewPunctuationGershayim:
1669         case leftDoubleQuotationMark:
1670         case rightDoubleQuotationMark:
1671             return '"';
1672         case hebrewPunctuationGeresh:
1673         case leftSingleQuotationMark:
1674         case rightSingleQuotationMark:
1675             return '\'';
1676         default:
1677             return c;
1678     }
1679 }
1680
1681 // FIXME: We'd like to tailor the searcher to fold quote marks for us instead
1682 // of doing it in a separate replacement pass here, but ICU doesn't offer a way
1683 // to add tailoring on top of the locale-specific tailoring as of this writing.
1684 static inline String foldQuoteMarks(String string)
1685 {
1686     string.replace(hebrewPunctuationGeresh, '\'');
1687     string.replace(hebrewPunctuationGershayim, '"');
1688     string.replace(leftDoubleQuotationMark, '"');
1689     string.replace(leftSingleQuotationMark, '\'');
1690     string.replace(rightDoubleQuotationMark, '"');
1691     string.replace(rightSingleQuotationMark, '\'');
1692
1693     return string;
1694 }
1695
1696 #if !UCONFIG_NO_COLLATION
1697
1698 const size_t minimumSearchBufferSize = 8192;
1699
1700 #ifndef NDEBUG
1701 static bool searcherInUse;
1702 #endif
1703
1704 static UStringSearch* createSearcher()
1705 {
1706     // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
1707     // but it doesn't matter exactly what it is, since we don't perform any searches
1708     // without setting both the pattern and the text.
1709     UErrorCode status = U_ZERO_ERROR;
1710     String searchCollatorName = makeString(currentSearchLocaleID(), "@collation=search");
1711     UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, searchCollatorName.utf8().data(), 0, &status);
1712     ASSERT(status == U_ZERO_ERROR || status == U_USING_FALLBACK_WARNING || status == U_USING_DEFAULT_WARNING);
1713     return searcher;
1714 }
1715
1716 static UStringSearch* searcher()
1717 {
1718     static UStringSearch* searcher = createSearcher();
1719     return searcher;
1720 }
1721
1722 static inline void lockSearcher()
1723 {
1724 #ifndef NDEBUG
1725     ASSERT(!searcherInUse);
1726     searcherInUse = true;
1727 #endif
1728 }
1729
1730 static inline void unlockSearcher()
1731 {
1732 #ifndef NDEBUG
1733     ASSERT(searcherInUse);
1734     searcherInUse = false;
1735 #endif
1736 }
1737
1738 // ICU's search ignores the distinction between small kana letters and ones
1739 // that are not small, and also characters that differ only in the voicing
1740 // marks when considering only primary collation strength differences.
1741 // This is not helpful for end users, since these differences make words
1742 // distinct, so for our purposes we need these to be considered.
1743 // The Unicode folks do not think the collation algorithm should be
1744 // changed. To work around this, we would like to tailor the ICU searcher,
1745 // but we can't get that to work yet. So instead, we check for cases where
1746 // these differences occur, and skip those matches.
1747
1748 // We refer to the above technique as the "kana workaround". The next few
1749 // functions are helper functinos for the kana workaround.
1750
1751 static inline bool isKanaLetter(UChar character)
1752 {
1753     // Hiragana letters.
1754     if (character >= 0x3041 && character <= 0x3096)
1755         return true;
1756
1757     // Katakana letters.
1758     if (character >= 0x30A1 && character <= 0x30FA)
1759         return true;
1760     if (character >= 0x31F0 && character <= 0x31FF)
1761         return true;
1762
1763     // Halfwidth katakana letters.
1764     if (character >= 0xFF66 && character <= 0xFF9D && character != 0xFF70)
1765         return true;
1766
1767     return false;
1768 }
1769
1770 static inline bool isSmallKanaLetter(UChar character)
1771 {
1772     ASSERT(isKanaLetter(character));
1773
1774     switch (character) {
1775     case 0x3041: // HIRAGANA LETTER SMALL A
1776     case 0x3043: // HIRAGANA LETTER SMALL I
1777     case 0x3045: // HIRAGANA LETTER SMALL U
1778     case 0x3047: // HIRAGANA LETTER SMALL E
1779     case 0x3049: // HIRAGANA LETTER SMALL O
1780     case 0x3063: // HIRAGANA LETTER SMALL TU
1781     case 0x3083: // HIRAGANA LETTER SMALL YA
1782     case 0x3085: // HIRAGANA LETTER SMALL YU
1783     case 0x3087: // HIRAGANA LETTER SMALL YO
1784     case 0x308E: // HIRAGANA LETTER SMALL WA
1785     case 0x3095: // HIRAGANA LETTER SMALL KA
1786     case 0x3096: // HIRAGANA LETTER SMALL KE
1787     case 0x30A1: // KATAKANA LETTER SMALL A
1788     case 0x30A3: // KATAKANA LETTER SMALL I
1789     case 0x30A5: // KATAKANA LETTER SMALL U
1790     case 0x30A7: // KATAKANA LETTER SMALL E
1791     case 0x30A9: // KATAKANA LETTER SMALL O
1792     case 0x30C3: // KATAKANA LETTER SMALL TU
1793     case 0x30E3: // KATAKANA LETTER SMALL YA
1794     case 0x30E5: // KATAKANA LETTER SMALL YU
1795     case 0x30E7: // KATAKANA LETTER SMALL YO
1796     case 0x30EE: // KATAKANA LETTER SMALL WA
1797     case 0x30F5: // KATAKANA LETTER SMALL KA
1798     case 0x30F6: // KATAKANA LETTER SMALL KE
1799     case 0x31F0: // KATAKANA LETTER SMALL KU
1800     case 0x31F1: // KATAKANA LETTER SMALL SI
1801     case 0x31F2: // KATAKANA LETTER SMALL SU
1802     case 0x31F3: // KATAKANA LETTER SMALL TO
1803     case 0x31F4: // KATAKANA LETTER SMALL NU
1804     case 0x31F5: // KATAKANA LETTER SMALL HA
1805     case 0x31F6: // KATAKANA LETTER SMALL HI
1806     case 0x31F7: // KATAKANA LETTER SMALL HU
1807     case 0x31F8: // KATAKANA LETTER SMALL HE
1808     case 0x31F9: // KATAKANA LETTER SMALL HO
1809     case 0x31FA: // KATAKANA LETTER SMALL MU
1810     case 0x31FB: // KATAKANA LETTER SMALL RA
1811     case 0x31FC: // KATAKANA LETTER SMALL RI
1812     case 0x31FD: // KATAKANA LETTER SMALL RU
1813     case 0x31FE: // KATAKANA LETTER SMALL RE
1814     case 0x31FF: // KATAKANA LETTER SMALL RO
1815     case 0xFF67: // HALFWIDTH KATAKANA LETTER SMALL A
1816     case 0xFF68: // HALFWIDTH KATAKANA LETTER SMALL I
1817     case 0xFF69: // HALFWIDTH KATAKANA LETTER SMALL U
1818     case 0xFF6A: // HALFWIDTH KATAKANA LETTER SMALL E
1819     case 0xFF6B: // HALFWIDTH KATAKANA LETTER SMALL O
1820     case 0xFF6C: // HALFWIDTH KATAKANA LETTER SMALL YA
1821     case 0xFF6D: // HALFWIDTH KATAKANA LETTER SMALL YU
1822     case 0xFF6E: // HALFWIDTH KATAKANA LETTER SMALL YO
1823     case 0xFF6F: // HALFWIDTH KATAKANA LETTER SMALL TU
1824         return true;
1825     }
1826     return false;
1827 }
1828
1829 enum VoicedSoundMarkType { NoVoicedSoundMark, VoicedSoundMark, SemiVoicedSoundMark };
1830
1831 static inline VoicedSoundMarkType composedVoicedSoundMark(UChar character)
1832 {
1833     ASSERT(isKanaLetter(character));
1834
1835     switch (character) {
1836     case 0x304C: // HIRAGANA LETTER GA
1837     case 0x304E: // HIRAGANA LETTER GI
1838     case 0x3050: // HIRAGANA LETTER GU
1839     case 0x3052: // HIRAGANA LETTER GE
1840     case 0x3054: // HIRAGANA LETTER GO
1841     case 0x3056: // HIRAGANA LETTER ZA
1842     case 0x3058: // HIRAGANA LETTER ZI
1843     case 0x305A: // HIRAGANA LETTER ZU
1844     case 0x305C: // HIRAGANA LETTER ZE
1845     case 0x305E: // HIRAGANA LETTER ZO
1846     case 0x3060: // HIRAGANA LETTER DA
1847     case 0x3062: // HIRAGANA LETTER DI
1848     case 0x3065: // HIRAGANA LETTER DU
1849     case 0x3067: // HIRAGANA LETTER DE
1850     case 0x3069: // HIRAGANA LETTER DO
1851     case 0x3070: // HIRAGANA LETTER BA
1852     case 0x3073: // HIRAGANA LETTER BI
1853     case 0x3076: // HIRAGANA LETTER BU
1854     case 0x3079: // HIRAGANA LETTER BE
1855     case 0x307C: // HIRAGANA LETTER BO
1856     case 0x3094: // HIRAGANA LETTER VU
1857     case 0x30AC: // KATAKANA LETTER GA
1858     case 0x30AE: // KATAKANA LETTER GI
1859     case 0x30B0: // KATAKANA LETTER GU
1860     case 0x30B2: // KATAKANA LETTER GE
1861     case 0x30B4: // KATAKANA LETTER GO
1862     case 0x30B6: // KATAKANA LETTER ZA
1863     case 0x30B8: // KATAKANA LETTER ZI
1864     case 0x30BA: // KATAKANA LETTER ZU
1865     case 0x30BC: // KATAKANA LETTER ZE
1866     case 0x30BE: // KATAKANA LETTER ZO
1867     case 0x30C0: // KATAKANA LETTER DA
1868     case 0x30C2: // KATAKANA LETTER DI
1869     case 0x30C5: // KATAKANA LETTER DU
1870     case 0x30C7: // KATAKANA LETTER DE
1871     case 0x30C9: // KATAKANA LETTER DO
1872     case 0x30D0: // KATAKANA LETTER BA
1873     case 0x30D3: // KATAKANA LETTER BI
1874     case 0x30D6: // KATAKANA LETTER BU
1875     case 0x30D9: // KATAKANA LETTER BE
1876     case 0x30DC: // KATAKANA LETTER BO
1877     case 0x30F4: // KATAKANA LETTER VU
1878     case 0x30F7: // KATAKANA LETTER VA
1879     case 0x30F8: // KATAKANA LETTER VI
1880     case 0x30F9: // KATAKANA LETTER VE
1881     case 0x30FA: // KATAKANA LETTER VO
1882         return VoicedSoundMark;
1883     case 0x3071: // HIRAGANA LETTER PA
1884     case 0x3074: // HIRAGANA LETTER PI
1885     case 0x3077: // HIRAGANA LETTER PU
1886     case 0x307A: // HIRAGANA LETTER PE
1887     case 0x307D: // HIRAGANA LETTER PO
1888     case 0x30D1: // KATAKANA LETTER PA
1889     case 0x30D4: // KATAKANA LETTER PI
1890     case 0x30D7: // KATAKANA LETTER PU
1891     case 0x30DA: // KATAKANA LETTER PE
1892     case 0x30DD: // KATAKANA LETTER PO
1893         return SemiVoicedSoundMark;
1894     }
1895     return NoVoicedSoundMark;
1896 }
1897
1898 static inline bool isCombiningVoicedSoundMark(UChar character)
1899 {
1900     switch (character) {
1901     case 0x3099: // COMBINING KATAKANA-HIRAGANA VOICED SOUND MARK
1902     case 0x309A: // COMBINING KATAKANA-HIRAGANA SEMI-VOICED SOUND MARK
1903         return true;
1904     }
1905     return false;
1906 }
1907
1908 static inline bool containsKanaLetters(const String& pattern)
1909 {
1910     if (pattern.is8Bit())
1911         return false;
1912     const UChar* characters = pattern.characters16();
1913     unsigned length = pattern.length();
1914     for (unsigned i = 0; i < length; ++i) {
1915         if (isKanaLetter(characters[i]))
1916             return true;
1917     }
1918     return false;
1919 }
1920
1921 static void normalizeCharacters(const UChar* characters, unsigned length, Vector<UChar>& buffer)
1922 {
1923     ASSERT(length);
1924
1925     buffer.resize(length);
1926
1927     UErrorCode status = U_ZERO_ERROR;
1928     size_t bufferSize = unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), length, &status);
1929     ASSERT(status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING || status == U_BUFFER_OVERFLOW_ERROR);
1930     ASSERT(bufferSize);
1931
1932     buffer.resize(bufferSize);
1933
1934     if (status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING)
1935         return;
1936
1937     status = U_ZERO_ERROR;
1938     unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), bufferSize, &status);
1939     ASSERT(status == U_STRING_NOT_TERMINATED_WARNING);
1940 }
1941
1942 static bool isNonLatin1Separator(UChar32 character)
1943 {
1944     ASSERT_ARG(character, character >= 256);
1945
1946     return U_GET_GC_MASK(character) & (U_GC_S_MASK | U_GC_P_MASK | U_GC_Z_MASK | U_GC_CF_MASK);
1947 }
1948
1949 static inline bool isSeparator(UChar32 character)
1950 {
1951     static const bool latin1SeparatorTable[256] = {
1952         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1953         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1954         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // space ! " # $ % & ' ( ) * + , - . /
1955         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, //                         : ; < = > ?
1956         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //   @
1957         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, //                         [ \ ] ^ _
1958         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //   `
1959         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, //                           { | } ~
1960         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1961         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1962         0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
1963         1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
1964         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1965         0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
1966         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1967         0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
1968     };
1969
1970     if (character < 256)
1971         return latin1SeparatorTable[character];
1972
1973     return isNonLatin1Separator(character);
1974 }
1975
1976 inline SearchBuffer::SearchBuffer(const String& target, FindOptions options)
1977     : m_target(foldQuoteMarks(target))
1978     , m_targetCharacters(StringView(m_target).upconvertedCharacters())
1979     , m_options(options)
1980     , m_prefixLength(0)
1981     , m_atBreak(true)
1982     , m_needsMoreContext(options & AtWordStarts)
1983     , m_targetRequiresKanaWorkaround(containsKanaLetters(m_target))
1984 {
1985     ASSERT(!m_target.isEmpty());
1986
1987     size_t targetLength = m_target.length();
1988     m_buffer.reserveInitialCapacity(std::max(targetLength * 8, minimumSearchBufferSize));
1989     m_overlap = m_buffer.capacity() / 4;
1990
1991     if ((m_options & AtWordStarts) && targetLength) {
1992         UChar32 targetFirstCharacter;
1993         U16_GET(m_target, 0, 0, targetLength, targetFirstCharacter);
1994         // Characters in the separator category never really occur at the beginning of a word,
1995         // so if the target begins with such a character, we just ignore the AtWordStart option.
1996         if (isSeparator(targetFirstCharacter)) {
1997             m_options &= ~AtWordStarts;
1998             m_needsMoreContext = false;
1999         }
2000     }
2001
2002     // Grab the single global searcher.
2003     // If we ever have a reason to do more than once search buffer at once, we'll have
2004     // to move to multiple searchers.
2005     lockSearcher();
2006
2007     UStringSearch* searcher = WebCore::searcher();
2008     UCollator* collator = usearch_getCollator(searcher);
2009
2010     UCollationStrength strength;
2011     USearchAttributeValue comparator;
2012     if (m_options & CaseInsensitive) {
2013         // Without loss of generality, have 'e' match {'e', 'E', 'é', 'É'} and 'é' match {'é', 'É'}.
2014         strength = UCOL_SECONDARY;
2015         comparator = USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD;
2016     } else {
2017         // Without loss of generality, have 'e' match {'e'} and 'é' match {'é'}.
2018         strength = UCOL_TERTIARY;
2019         comparator = USEARCH_STANDARD_ELEMENT_COMPARISON;
2020     }
2021     if (ucol_getStrength(collator) != strength) {
2022         ucol_setStrength(collator, strength);
2023         usearch_reset(searcher);
2024     }
2025
2026     UErrorCode status = U_ZERO_ERROR;
2027     usearch_setAttribute(searcher, USEARCH_ELEMENT_COMPARISON, comparator, &status);
2028     ASSERT(status == U_ZERO_ERROR);
2029
2030     usearch_setPattern(searcher, m_targetCharacters, targetLength, &status);
2031     ASSERT(status == U_ZERO_ERROR);
2032
2033     // The kana workaround requires a normalized copy of the target string.
2034     if (m_targetRequiresKanaWorkaround)
2035         normalizeCharacters(m_targetCharacters, targetLength, m_normalizedTarget);
2036 }
2037
2038 inline SearchBuffer::~SearchBuffer()
2039 {
2040     // Leave the static object pointing to a valid string.
2041     UErrorCode status = U_ZERO_ERROR;
2042     usearch_setPattern(WebCore::searcher(), &newlineCharacter, 1, &status);
2043     ASSERT(status == U_ZERO_ERROR);
2044     usearch_setText(WebCore::searcher(), &newlineCharacter, 1, &status);
2045     ASSERT(status == U_ZERO_ERROR);
2046
2047     unlockSearcher();
2048 }
2049
2050 inline size_t SearchBuffer::append(StringView text)
2051 {
2052     ASSERT(text.length());
2053
2054     if (m_atBreak) {
2055         m_buffer.shrink(0);
2056         m_prefixLength = 0;
2057         m_atBreak = false;
2058     } else if (m_buffer.size() == m_buffer.capacity()) {
2059         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
2060         m_prefixLength -= std::min(m_prefixLength, m_buffer.size() - m_overlap);
2061         m_buffer.shrink(m_overlap);
2062     }
2063
2064     size_t oldLength = m_buffer.size();
2065     size_t usableLength = std::min<size_t>(m_buffer.capacity() - oldLength, text.length());
2066     ASSERT(usableLength);
2067     m_buffer.grow(oldLength + usableLength);
2068     for (unsigned i = 0; i < usableLength; ++i)
2069         m_buffer[oldLength + i] = foldQuoteMark(text[i]);
2070     return usableLength;
2071 }
2072
2073 inline bool SearchBuffer::needsMoreContext() const
2074 {
2075     return m_needsMoreContext;
2076 }
2077
2078 inline void SearchBuffer::prependContext(StringView text)
2079 {
2080     ASSERT(m_needsMoreContext);
2081     ASSERT(m_prefixLength == m_buffer.size());
2082
2083     if (!text.length())
2084         return;
2085
2086     m_atBreak = false;
2087
2088     size_t wordBoundaryContextStart = text.length();
2089     if (wordBoundaryContextStart) {
2090         U16_BACK_1(text, 0, wordBoundaryContextStart);
2091         wordBoundaryContextStart = startOfLastWordBoundaryContext(text.substring(0, wordBoundaryContextStart));
2092     }
2093
2094     size_t usableLength = std::min(m_buffer.capacity() - m_prefixLength, text.length() - wordBoundaryContextStart);
2095     WTF::append(m_buffer, text.substring(text.length() - usableLength, usableLength));
2096     m_prefixLength += usableLength;
2097
2098     if (wordBoundaryContextStart || m_prefixLength == m_buffer.capacity())
2099         m_needsMoreContext = false;
2100 }
2101
2102 inline bool SearchBuffer::atBreak() const
2103 {
2104     return m_atBreak;
2105 }
2106
2107 inline void SearchBuffer::reachedBreak()
2108 {
2109     m_atBreak = true;
2110 }
2111
2112 inline bool SearchBuffer::isBadMatch(const UChar* match, size_t matchLength) const
2113 {
2114     // This function implements the kana workaround. If usearch treats
2115     // it as a match, but we do not want to, then it's a "bad match".
2116     if (!m_targetRequiresKanaWorkaround)
2117         return false;
2118
2119     // Normalize into a match buffer. We reuse a single buffer rather than
2120     // creating a new one each time.
2121     normalizeCharacters(match, matchLength, m_normalizedMatch);
2122
2123     const UChar* a = m_normalizedTarget.begin();
2124     const UChar* aEnd = m_normalizedTarget.end();
2125
2126     const UChar* b = m_normalizedMatch.begin();
2127     const UChar* bEnd = m_normalizedMatch.end();
2128
2129     while (true) {
2130         // Skip runs of non-kana-letter characters. This is necessary so we can
2131         // correctly handle strings where the target and match have different-length
2132         // runs of characters that match, while still double checking the correctness
2133         // of matches of kana letters with other kana letters.
2134         while (a != aEnd && !isKanaLetter(*a))
2135             ++a;
2136         while (b != bEnd && !isKanaLetter(*b))
2137             ++b;
2138
2139         // If we reached the end of either the target or the match, we should have
2140         // reached the end of both; both should have the same number of kana letters.
2141         if (a == aEnd || b == bEnd) {
2142             ASSERT(a == aEnd);
2143             ASSERT(b == bEnd);
2144             return false;
2145         }
2146
2147         // Check for differences in the kana letter character itself.
2148         if (isSmallKanaLetter(*a) != isSmallKanaLetter(*b))
2149             return true;
2150         if (composedVoicedSoundMark(*a) != composedVoicedSoundMark(*b))
2151             return true;
2152         ++a;
2153         ++b;
2154
2155         // Check for differences in combining voiced sound marks found after the letter.
2156         while (1) {
2157             if (!(a != aEnd && isCombiningVoicedSoundMark(*a))) {
2158                 if (b != bEnd && isCombiningVoicedSoundMark(*b))
2159                     return true;
2160                 break;
2161             }
2162             if (!(b != bEnd && isCombiningVoicedSoundMark(*b)))
2163                 return true;
2164             if (*a != *b)
2165                 return true;
2166             ++a;
2167             ++b;
2168         }
2169     }
2170 }
2171     
2172 inline bool SearchBuffer::isWordEndMatch(size_t start, size_t length) const
2173 {
2174     ASSERT(length);
2175     ASSERT(m_options & AtWordEnds);
2176
2177     int endWord;
2178     // Start searching at the end of matched search, so that multiple word matches succeed.
2179     findEndWordBoundary(StringView(m_buffer.data(), m_buffer.size()), start + length - 1, &endWord);
2180     return static_cast<size_t>(endWord) == (start + length);
2181 }
2182
2183 inline bool SearchBuffer::isWordStartMatch(size_t start, size_t length) const
2184 {
2185     ASSERT(m_options & AtWordStarts);
2186
2187     if (!start)
2188         return true;
2189
2190     int size = m_buffer.size();
2191     int offset = start;
2192     UChar32 firstCharacter;
2193     U16_GET(m_buffer.data(), 0, offset, size, firstCharacter);
2194
2195     if (m_options & TreatMedialCapitalAsWordStart) {
2196         UChar32 previousCharacter;
2197         U16_PREV(m_buffer.data(), 0, offset, previousCharacter);
2198
2199         if (isSeparator(firstCharacter)) {
2200             // The start of a separator run is a word start (".org" in "webkit.org").
2201             if (!isSeparator(previousCharacter))
2202                 return true;
2203         } else if (isASCIIUpper(firstCharacter)) {
2204             // The start of an uppercase run is a word start ("Kit" in "WebKit").
2205             if (!isASCIIUpper(previousCharacter))
2206                 return true;
2207             // The last character of an uppercase run followed by a non-separator, non-digit
2208             // is a word start ("Request" in "XMLHTTPRequest").
2209             offset = start;
2210             U16_FWD_1(m_buffer.data(), offset, size);
2211             UChar32 nextCharacter = 0;
2212             if (offset < size)
2213                 U16_GET(m_buffer.data(), 0, offset, size, nextCharacter);
2214             if (!isASCIIUpper(nextCharacter) && !isASCIIDigit(nextCharacter) && !isSeparator(nextCharacter))
2215                 return true;
2216         } else if (isASCIIDigit(firstCharacter)) {
2217             // The start of a digit run is a word start ("2" in "WebKit2").
2218             if (!isASCIIDigit(previousCharacter))
2219                 return true;
2220         } else if (isSeparator(previousCharacter) || isASCIIDigit(previousCharacter)) {
2221             // The start of a non-separator, non-uppercase, non-digit run is a word start,
2222             // except after an uppercase. ("org" in "webkit.org", but not "ore" in "WebCore").
2223             return true;
2224         }
2225     }
2226
2227     // Chinese and Japanese lack word boundary marks, and there is no clear agreement on what constitutes
2228     // a word, so treat the position before any CJK character as a word start.
2229     if (FontCascade::isCJKIdeographOrSymbol(firstCharacter))
2230         return true;
2231
2232     size_t wordBreakSearchStart = start + length;
2233     while (wordBreakSearchStart > start)
2234         wordBreakSearchStart = findNextWordFromIndex(StringView(m_buffer.data(), m_buffer.size()), wordBreakSearchStart, false /* backwards */);
2235     return wordBreakSearchStart == start;
2236 }
2237
2238 inline size_t SearchBuffer::search(size_t& start)
2239 {
2240     size_t size = m_buffer.size();
2241     if (m_atBreak) {
2242         if (!size)
2243             return 0;
2244     } else {
2245         if (size != m_buffer.capacity())
2246             return 0;
2247     }
2248
2249     UStringSearch* searcher = WebCore::searcher();
2250
2251     UErrorCode status = U_ZERO_ERROR;
2252     usearch_setText(searcher, m_buffer.data(), size, &status);
2253     ASSERT(status == U_ZERO_ERROR);
2254
2255     usearch_setOffset(searcher, m_prefixLength, &status);
2256     ASSERT(status == U_ZERO_ERROR);
2257
2258     int matchStart = usearch_next(searcher, &status);
2259     ASSERT(status == U_ZERO_ERROR);
2260
2261 nextMatch:
2262     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
2263         ASSERT(matchStart == USEARCH_DONE);
2264         return 0;
2265     }
2266
2267     // Matches that start in the overlap area are only tentative.
2268     // The same match may appear later, matching more characters,
2269     // possibly including a combining character that's not yet in the buffer.
2270     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
2271         size_t overlap = m_overlap;
2272         if (m_options & AtWordStarts) {
2273             // Ensure that there is sufficient context before matchStart the next time around for
2274             // determining if it is at a word boundary.
2275             unsigned wordBoundaryContextStart = matchStart;
2276             U16_BACK_1(m_buffer.data(), 0, wordBoundaryContextStart);
2277             wordBoundaryContextStart = startOfLastWordBoundaryContext(StringView(m_buffer.data(), wordBoundaryContextStart));
2278             overlap = std::min(size - 1, std::max(overlap, size - wordBoundaryContextStart));
2279         }
2280         memcpy(m_buffer.data(), m_buffer.data() + size - overlap, overlap * sizeof(UChar));
2281         m_prefixLength -= std::min(m_prefixLength, size - overlap);
2282         m_buffer.shrink(overlap);
2283         return 0;
2284     }
2285
2286     size_t matchedLength = usearch_getMatchedLength(searcher);
2287     ASSERT_WITH_SECURITY_IMPLICATION(matchStart + matchedLength <= size);
2288
2289     // If this match is "bad", move on to the next match.
2290     if (isBadMatch(m_buffer.data() + matchStart, matchedLength)
2291         || ((m_options & AtWordStarts) && !isWordStartMatch(matchStart, matchedLength))
2292         || ((m_options & AtWordEnds) && !isWordEndMatch(matchStart, matchedLength))) {
2293         matchStart = usearch_next(searcher, &status);
2294         ASSERT(status == U_ZERO_ERROR);
2295         goto nextMatch;
2296     }
2297
2298     size_t newSize = size - (matchStart + 1);
2299     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
2300     m_prefixLength -= std::min<size_t>(m_prefixLength, matchStart + 1);
2301     m_buffer.shrink(newSize);
2302
2303     start = size - matchStart;
2304     return matchedLength;
2305 }
2306
2307 #else
2308
2309 inline SearchBuffer::SearchBuffer(const String& target, FindOptions options)
2310     : m_target(options & CaseInsensitive ? target.foldCase() : target)
2311     , m_options(options)
2312     , m_buffer(m_target.length())
2313     , m_isCharacterStartBuffer(m_target.length())
2314     , m_isBufferFull(false)
2315     , m_cursor(0)
2316 {
2317     ASSERT(!m_target.isEmpty());
2318     m_target.replace(noBreakSpace, ' ');
2319     foldQuoteMarks(m_target);
2320 }
2321
2322 inline SearchBuffer::~SearchBuffer()
2323 {
2324 }
2325
2326 inline void SearchBuffer::reachedBreak()
2327 {
2328     m_cursor = 0;
2329     m_isBufferFull = false;
2330 }
2331
2332 inline bool SearchBuffer::atBreak() const
2333 {
2334     return !m_cursor && !m_isBufferFull;
2335 }
2336
2337 inline void SearchBuffer::append(UChar c, bool isStart)
2338 {
2339     m_buffer[m_cursor] = c == noBreakSpace ? ' ' : foldQuoteMark(c);
2340     m_isCharacterStartBuffer[m_cursor] = isStart;
2341     if (++m_cursor == m_target.length()) {
2342         m_cursor = 0;
2343         m_isBufferFull = true;
2344     }
2345 }
2346
2347 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
2348 {
2349     ASSERT(length);
2350     if (!(m_options & CaseInsensitive)) {
2351         append(characters[0], true);
2352         return 1;
2353     }
2354     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
2355     UChar foldedCharacters[maxFoldedCharacters];
2356     UErrorCode status = U_ZERO_ERROR;
2357     int numFoldedCharacters = u_strFoldCase(foldedCharacters, maxFoldedCharacters, characters, 1, U_FOLD_CASE_DEFAULT, &status);
2358     ASSERT(U_SUCCESS(status));
2359     ASSERT(numFoldedCharacters);
2360     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
2361     if (U_SUCCESS(status) && numFoldedCharacters) {
2362         numFoldedCharacters = std::min(numFoldedCharacters, maxFoldedCharacters);
2363         append(foldedCharacters[0], true);
2364         for (int i = 1; i < numFoldedCharacters; ++i)
2365             append(foldedCharacters[i], false);
2366     }
2367     return 1;
2368 }
2369
2370 inline bool SearchBuffer::needsMoreContext() const
2371 {
2372     return false;
2373 }
2374
2375 void SearchBuffer::prependContext(const UChar*, size_t)
2376 {
2377     ASSERT_NOT_REACHED();
2378 }
2379
2380 inline size_t SearchBuffer::search(size_t& start)
2381 {
2382     if (!m_isBufferFull)
2383         return 0;
2384     if (!m_isCharacterStartBuffer[m_cursor])
2385         return 0;
2386
2387     size_t tailSpace = m_target.length() - m_cursor;
2388     if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
2389         return 0;
2390     if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
2391         return 0;
2392
2393     start = length();
2394
2395     // Now that we've found a match once, we don't want to find it again, because those
2396     // are the SearchBuffer semantics, allowing for a buffer where you append more than one
2397     // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if
2398     // we want to get rid of that in the future we could track this with a separate boolean
2399     // or even move the characters to the start of the buffer and set m_isBufferFull to false.
2400     m_isCharacterStartBuffer[m_cursor] = false;
2401
2402     return start;
2403 }
2404
2405 // Returns the number of characters that were appended to the buffer (what we are searching in).
2406 // That's not necessarily the same length as the passed-in target string, because case folding
2407 // can make two strings match even though they're not the same length.
2408 size_t SearchBuffer::length() const
2409 {
2410     size_t bufferSize = m_target.length();
2411     size_t length = 0;
2412     for (size_t i = 0; i < bufferSize; ++i)
2413         length += m_isCharacterStartBuffer[i];
2414     return length;
2415 }
2416
2417 #endif
2418
2419 // --------
2420
2421 int TextIterator::rangeLength(const Range* range, bool forSelectionPreservation)
2422 {
2423     unsigned length = 0;
2424     for (TextIterator it(range, forSelectionPreservation ? TextIteratorEmitsCharactersBetweenAllVisiblePositions : TextIteratorDefaultBehavior); !it.atEnd(); it.advance())
2425         length += it.text().length();
2426     return length;
2427 }
2428
2429 Ref<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
2430 {
2431     CharacterIterator entireRangeIterator(*entireRange);
2432     return characterSubrange(entireRange->ownerDocument(), entireRangeIterator, characterOffset, characterCount);
2433 }
2434
2435 static inline bool isInsideReplacedElement(TextIterator& iterator)
2436 {
2437     ASSERT(!iterator.atEnd());
2438     ASSERT(iterator.text().length() == 1);
2439     Node* node = iterator.node();
2440     return node && isRendererReplacedElement(node->renderer());
2441 }
2442
2443 RefPtr<Range> TextIterator::rangeFromLocationAndLength(ContainerNode* scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
2444 {
2445     Ref<Range> resultRange = scope->document().createRange();
2446
2447     int docTextPosition = 0;
2448     int rangeEnd = rangeLocation + rangeLength;
2449     bool startRangeFound = false;
2450
2451     Ref<Range> textRunRange = rangeOfContents(*scope);
2452
2453     TextIterator it(textRunRange.ptr(), forSelectionPreservation ? TextIteratorEmitsCharactersBetweenAllVisiblePositions : TextIteratorDefaultBehavior);
2454     
2455     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
2456     if (!rangeLocation && !rangeLength && it.atEnd()) {
2457         resultRange->setStart(textRunRange->startContainer(), 0);
2458         resultRange->setEnd(textRunRange->startContainer(), 0);
2459         return WTF::move(resultRange);
2460     }
2461
2462     for (; !it.atEnd(); it.advance()) {
2463         int length = it.text().length();
2464         textRunRange = it.range();
2465
2466         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + length;
2467         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + length;
2468
2469         if (foundEnd) {
2470             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
2471             // position for emitted '\n's or if the renderer of the current node is a replaced element.
2472             if (length == 1 && (it.text()[0] == '\n' || isInsideReplacedElement(it))) {
2473                 it.advance();
2474                 if (!it.atEnd()) {
2475                     Ref<Range> range = it.range();
2476                     textRunRange->setEnd(range->startContainer(), range->startOffset());
2477                 } else {
2478                     Position runStart = textRunRange->startPosition();
2479                     Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
2480                     if (runEnd.isNotNull())
2481                         textRunRange->setEnd(runEnd.containerNode(), runEnd.computeOffsetInContainerNode());
2482                 }
2483             }
2484         }
2485
2486         if (foundStart) {
2487             startRangeFound = true;
2488             if (textRunRange->startContainer()->isTextNode()) {
2489                 int offset = rangeLocation - docTextPosition;
2490                 resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset());
2491             } else {
2492                 if (rangeLocation == docTextPosition)
2493                     resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset());
2494                 else
2495                     resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset());
2496             }
2497         }
2498
2499         if (foundEnd) {
2500             if (textRunRange->startContainer()->isTextNode()) {
2501                 int offset = rangeEnd - docTextPosition;
2502                 resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset());
2503             } else {
2504                 if (rangeEnd == docTextPosition)
2505                     resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset());
2506                 else
2507                     resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset());
2508             }
2509             docTextPosition += length;
2510             break;
2511         }
2512
2513         docTextPosition += length;
2514     }
2515     
2516     if (!startRangeFound)
2517         return nullptr;
2518     
2519     if (rangeLength && rangeEnd > docTextPosition) // rangeEnd is out of bounds
2520         resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset());
2521     
2522     return WTF::move(resultRange);
2523 }
2524
2525 bool TextIterator::getLocationAndLengthFromRange(Node* scope, const Range* range, size_t& location, size_t& length)
2526 {
2527     location = notFound;
2528     length = 0;
2529
2530     if (!range->startContainer())
2531         return false;
2532
2533     // The critical assumption is that this only gets called with ranges that
2534     // concentrate on a given area containing the selection root. This is done
2535     // because of text fields and textareas. The DOM for those is not
2536     // directly in the document DOM, so ensure that the range does not cross a
2537     // boundary of one of those.
2538     if (range->startContainer() != scope && !range->startContainer()->isDescendantOf(scope))
2539         return false;
2540     if (range->endContainer() != scope && !range->endContainer()->isDescendantOf(scope))
2541         return false;
2542
2543     Ref<Range> testRange = Range::create(scope->document(), scope, 0, range->startContainer(), range->startOffset());
2544     ASSERT(testRange->startContainer() == scope);
2545     location = TextIterator::rangeLength(testRange.ptr());
2546
2547     testRange->setEnd(range->endContainer(), range->endOffset(), IGNORE_EXCEPTION);
2548     ASSERT(testRange->startContainer() == scope);
2549     length = TextIterator::rangeLength(testRange.ptr()) - location;
2550     return true;
2551 }
2552
2553 // --------
2554
2555 String plainText(const Range* r, TextIteratorBehavior defaultBehavior, bool isDisplayString)
2556 {
2557     // The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
2558     static const unsigned initialCapacity = 1 << 15;
2559
2560     unsigned bufferLength = 0;
2561     StringBuilder builder;
2562     builder.reserveCapacity(initialCapacity);
2563     TextIteratorBehavior behavior = defaultBehavior;
2564     if (!isDisplayString)
2565         behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsTextsWithoutTranscoding);
2566     
2567     for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) {
2568         it.appendTextToStringBuilder(builder);
2569         bufferLength += it.text().length();
2570     }
2571
2572     if (!bufferLength)
2573         return emptyString();
2574
2575     String result = builder.toString();
2576
2577     if (isDisplayString)
2578         r->ownerDocument().displayStringModifiedByEncoding(result);
2579
2580     return result;
2581 }
2582
2583 String plainTextReplacingNoBreakSpace(const Range* range, TextIteratorBehavior defaultBehavior, bool isDisplayString)
2584 {
2585     return plainText(range, defaultBehavior, isDisplayString).replace(noBreakSpace, ' ');
2586 }
2587
2588 static Ref<Range> collapsedToBoundary(const Range& range, bool forward)
2589 {
2590     Ref<Range> result = range.cloneRange(ASSERT_NO_EXCEPTION).releaseNonNull();
2591     result->collapse(!forward, ASSERT_NO_EXCEPTION);
2592     return result;
2593 }
2594
2595 static size_t findPlainText(const Range& range, const String& target, FindOptions options, size_t& matchStart)
2596 {
2597     matchStart = 0;
2598     size_t matchLength = 0;
2599
2600     SearchBuffer buffer(target, options);
2601
2602     if (buffer.needsMoreContext()) {
2603         Ref<Range> beforeStartRange = range.ownerDocument().createRange();
2604         beforeStartRange->setEnd(range.startContainer(), range.startOffset());
2605         for (SimplifiedBackwardsTextIterator backwardsIterator(beforeStartRange.get()); !backwardsIterator.atEnd(); backwardsIterator.advance()) {
2606             buffer.prependContext(backwardsIterator.text());
2607             if (!buffer.needsMoreContext())
2608                 break;
2609         }
2610     }
2611
2612     CharacterIterator findIterator(range, TextIteratorEntersTextControls);
2613
2614     while (!findIterator.atEnd()) {
2615         findIterator.advance(buffer.append(findIterator.text()));
2616 tryAgain:
2617         size_t matchStartOffset;
2618         if (size_t newMatchLength = buffer.search(matchStartOffset)) {
2619             // Note that we found a match, and where we found it.
2620             size_t lastCharacterInBufferOffset = findIterator.characterOffset();
2621             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
2622             matchStart = lastCharacterInBufferOffset - matchStartOffset;
2623             matchLength = newMatchLength;
2624             // If searching forward, stop on the first match.
2625             // If searching backward, don't stop, so we end up with the last match.
2626             if (!(options & Backwards))
2627                 break;
2628             goto tryAgain;
2629         }
2630         if (findIterator.atBreak() && !buffer.atBreak()) {
2631             buffer.reachedBreak();
2632             goto tryAgain;
2633         }
2634     }
2635
2636     return matchLength;
2637 }
2638
2639 Ref<Range> findPlainText(const Range& range, const String& target, FindOptions options)
2640 {
2641     // First, find the text.
2642     size_t matchStart;
2643     size_t matchLength;
2644     {
2645         matchLength = findPlainText(range, target, options, matchStart);
2646         if (!matchLength)
2647             return collapsedToBoundary(range, !(options & Backwards));
2648     }
2649
2650     // Then, find the document position of the start and the end of the text.
2651     CharacterIterator computeRangeIterator(range, TextIteratorEntersTextControls);
2652     return characterSubrange(range.ownerDocument(), computeRangeIterator, matchStart, matchLength);
2653 }
2654
2655 }