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