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