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