Replace every use of Node::offsetInCharacters() by Node::isCharacterDataNode()
[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.isCharacterDataNode()) {
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.isCharacterDataNode())
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->isCharacterDataNode()) {
1288         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->countChildNodes())) {
1289             startNode = startNode->traverseToChildAt(startOffset);
1290             startOffset = 0;
1291         }
1292     }
1293     if (!endNode->isCharacterDataNode()) {
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 ALLOW_DEPRECATED_DECLARATIONS_BEGIN
2015 // NOTE: ICU's unorm_normalize function is deprecated.
2016
2017 static void normalizeCharacters(const UChar* characters, unsigned length, Vector<UChar>& buffer)
2018 {
2019     ASSERT(length);
2020
2021     buffer.resize(length);
2022
2023     UErrorCode status = U_ZERO_ERROR;
2024     size_t bufferSize = unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), length, &status);
2025     ASSERT(status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING || status == U_BUFFER_OVERFLOW_ERROR);
2026     ASSERT(bufferSize);
2027
2028     buffer.resize(bufferSize);
2029
2030     if (status == U_ZERO_ERROR || status == U_STRING_NOT_TERMINATED_WARNING)
2031         return;
2032
2033     status = U_ZERO_ERROR;
2034     unorm_normalize(characters, length, UNORM_NFC, 0, buffer.data(), bufferSize, &status);
2035     ASSERT(status == U_STRING_NOT_TERMINATED_WARNING);
2036 }
2037
2038 ALLOW_DEPRECATED_DECLARATIONS_END
2039
2040 static bool isNonLatin1Separator(UChar32 character)
2041 {
2042     ASSERT_ARG(character, character >= 256);
2043
2044     return U_GET_GC_MASK(character) & (U_GC_S_MASK | U_GC_P_MASK | U_GC_Z_MASK | U_GC_CF_MASK);
2045 }
2046
2047 static inline bool isSeparator(UChar32 character)
2048 {
2049     static const bool latin1SeparatorTable[256] = {
2050         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2051         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2052         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // space ! " # $ % & ' ( ) * + , - . /
2053         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, //                         : ; < = > ?
2054         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //   @
2055         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, //                         [ \ ] ^ _
2056         1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //   `
2057         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, //                           { | } ~
2058         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2059         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2060         0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
2061         1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
2062         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2063         0, 0, 0, 0, 0, 0, 0, 1, 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, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
2066     };
2067
2068     if (character < 256)
2069         return latin1SeparatorTable[character];
2070
2071     return isNonLatin1Separator(character);
2072 }
2073
2074 inline SearchBuffer::SearchBuffer(const String& target, FindOptions options)
2075     : m_target(foldQuoteMarks(target))
2076     , m_targetCharacters(StringView(m_target).upconvertedCharacters())
2077     , m_options(options)
2078     , m_prefixLength(0)
2079     , m_atBreak(true)
2080     , m_needsMoreContext(options.contains(AtWordStarts))
2081     , m_targetRequiresKanaWorkaround(containsKanaLetters(m_target))
2082 {
2083     ASSERT(!m_target.isEmpty());
2084
2085     size_t targetLength = m_target.length();
2086     m_buffer.reserveInitialCapacity(std::max(targetLength * 8, minimumSearchBufferSize));
2087     m_overlap = m_buffer.capacity() / 4;
2088
2089     if (m_options.contains(AtWordStarts) && targetLength) {
2090         UChar32 targetFirstCharacter;
2091         U16_GET(m_target, 0, 0u, targetLength, targetFirstCharacter);
2092         // Characters in the separator category never really occur at the beginning of a word,
2093         // so if the target begins with such a character, we just ignore the AtWordStart option.
2094         if (isSeparator(targetFirstCharacter)) {
2095             m_options.remove(AtWordStarts);
2096             m_needsMoreContext = false;
2097         }
2098     }
2099
2100     // Grab the single global searcher.
2101     // If we ever have a reason to do more than once search buffer at once, we'll have
2102     // to move to multiple searchers.
2103     lockSearcher();
2104
2105     UStringSearch* searcher = WebCore::searcher();
2106     UCollator* collator = usearch_getCollator(searcher);
2107
2108     UCollationStrength strength;
2109     USearchAttributeValue comparator;
2110     if (m_options.contains(CaseInsensitive)) {
2111         // Without loss of generality, have 'e' match {'e', 'E', 'é', 'É'} and 'é' match {'é', 'É'}.
2112         strength = UCOL_SECONDARY;
2113         comparator = USEARCH_PATTERN_BASE_WEIGHT_IS_WILDCARD;
2114     } else {
2115         // Without loss of generality, have 'e' match {'e'} and 'é' match {'é'}.
2116         strength = UCOL_TERTIARY;
2117         comparator = USEARCH_STANDARD_ELEMENT_COMPARISON;
2118     }
2119     if (ucol_getStrength(collator) != strength) {
2120         ucol_setStrength(collator, strength);
2121         usearch_reset(searcher);
2122     }
2123
2124     UErrorCode status = U_ZERO_ERROR;
2125     usearch_setAttribute(searcher, USEARCH_ELEMENT_COMPARISON, comparator, &status);
2126     ASSERT(status == U_ZERO_ERROR);
2127
2128     usearch_setPattern(searcher, m_targetCharacters, targetLength, &status);
2129     ASSERT(status == U_ZERO_ERROR);
2130
2131     // The kana workaround requires a normalized copy of the target string.
2132     if (m_targetRequiresKanaWorkaround)
2133         normalizeCharacters(m_targetCharacters, targetLength, m_normalizedTarget);
2134 }
2135
2136 inline SearchBuffer::~SearchBuffer()
2137 {
2138     // Leave the static object pointing to a valid string.
2139     UErrorCode status = U_ZERO_ERROR;
2140     usearch_setPattern(WebCore::searcher(), &newlineCharacter, 1, &status);
2141     ASSERT(status == U_ZERO_ERROR);
2142     usearch_setText(WebCore::searcher(), &newlineCharacter, 1, &status);
2143     ASSERT(status == U_ZERO_ERROR);
2144
2145     unlockSearcher();
2146 }
2147
2148 inline size_t SearchBuffer::append(StringView text)
2149 {
2150     ASSERT(text.length());
2151
2152     if (m_atBreak) {
2153         m_buffer.shrink(0);
2154         m_prefixLength = 0;
2155         m_atBreak = false;
2156     } else if (m_buffer.size() == m_buffer.capacity()) {
2157         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
2158         m_prefixLength -= std::min(m_prefixLength, m_buffer.size() - m_overlap);
2159         m_buffer.shrink(m_overlap);
2160     }
2161
2162     size_t oldLength = m_buffer.size();
2163     size_t usableLength = std::min<size_t>(m_buffer.capacity() - oldLength, text.length());
2164     ASSERT(usableLength);
2165     m_buffer.grow(oldLength + usableLength);
2166     for (unsigned i = 0; i < usableLength; ++i)
2167         m_buffer[oldLength + i] = foldQuoteMark(text[i]);
2168     return usableLength;
2169 }
2170
2171 inline bool SearchBuffer::needsMoreContext() const
2172 {
2173     return m_needsMoreContext;
2174 }
2175
2176 inline void SearchBuffer::prependContext(StringView text)
2177 {
2178     ASSERT(m_needsMoreContext);
2179     ASSERT(m_prefixLength == m_buffer.size());
2180
2181     if (!text.length())
2182         return;
2183
2184     m_atBreak = false;
2185
2186     size_t wordBoundaryContextStart = text.length();
2187     if (wordBoundaryContextStart) {
2188         U16_BACK_1(text, 0, wordBoundaryContextStart);
2189         wordBoundaryContextStart = startOfLastWordBoundaryContext(text.substring(0, wordBoundaryContextStart));
2190     }
2191
2192     size_t usableLength = std::min(m_buffer.capacity() - m_prefixLength, text.length() - wordBoundaryContextStart);
2193     WTF::append(m_buffer, text.substring(text.length() - usableLength, usableLength));
2194     m_prefixLength += usableLength;
2195
2196     if (wordBoundaryContextStart || m_prefixLength == m_buffer.capacity())
2197         m_needsMoreContext = false;
2198 }
2199
2200 inline bool SearchBuffer::atBreak() const
2201 {
2202     return m_atBreak;
2203 }
2204
2205 inline void SearchBuffer::reachedBreak()
2206 {
2207     m_atBreak = true;
2208 }
2209
2210 inline bool SearchBuffer::isBadMatch(const UChar* match, size_t matchLength) const
2211 {
2212     // This function implements the kana workaround. If usearch treats
2213     // it as a match, but we do not want to, then it's a "bad match".
2214     if (!m_targetRequiresKanaWorkaround)
2215         return false;
2216
2217     // Normalize into a match buffer. We reuse a single buffer rather than
2218     // creating a new one each time.
2219     normalizeCharacters(match, matchLength, m_normalizedMatch);
2220
2221     const UChar* a = m_normalizedTarget.begin();
2222     const UChar* aEnd = m_normalizedTarget.end();
2223
2224     const UChar* b = m_normalizedMatch.begin();
2225     const UChar* bEnd = m_normalizedMatch.end();
2226
2227     while (true) {
2228         // Skip runs of non-kana-letter characters. This is necessary so we can
2229         // correctly handle strings where the target and match have different-length
2230         // runs of characters that match, while still double checking the correctness
2231         // of matches of kana letters with other kana letters.
2232         while (a != aEnd && !isKanaLetter(*a))
2233             ++a;
2234         while (b != bEnd && !isKanaLetter(*b))
2235             ++b;
2236
2237         // If we reached the end of either the target or the match, we should have
2238         // reached the end of both; both should have the same number of kana letters.
2239         if (a == aEnd || b == bEnd) {
2240             ASSERT(a == aEnd);
2241             ASSERT(b == bEnd);
2242             return false;
2243         }
2244
2245         // Check for differences in the kana letter character itself.
2246         if (isSmallKanaLetter(*a) != isSmallKanaLetter(*b))
2247             return true;
2248         if (composedVoicedSoundMark(*a) != composedVoicedSoundMark(*b))
2249             return true;
2250         ++a;
2251         ++b;
2252
2253         // Check for differences in combining voiced sound marks found after the letter.
2254         while (1) {
2255             if (!(a != aEnd && isCombiningVoicedSoundMark(*a))) {
2256                 if (b != bEnd && isCombiningVoicedSoundMark(*b))
2257                     return true;
2258                 break;
2259             }
2260             if (!(b != bEnd && isCombiningVoicedSoundMark(*b)))
2261                 return true;
2262             if (*a != *b)
2263                 return true;
2264             ++a;
2265             ++b;
2266         }
2267     }
2268 }
2269     
2270 inline bool SearchBuffer::isWordEndMatch(size_t start, size_t length) const
2271 {
2272     ASSERT(length);
2273     ASSERT(m_options.contains(AtWordEnds));
2274
2275     int endWord;
2276     // Start searching at the end of matched search, so that multiple word matches succeed.
2277     findEndWordBoundary(StringView(m_buffer.data(), m_buffer.size()), start + length - 1, &endWord);
2278     return static_cast<size_t>(endWord) == (start + length);
2279 }
2280
2281 inline bool SearchBuffer::isWordStartMatch(size_t start, size_t length) const
2282 {
2283     ASSERT(m_options.contains(AtWordStarts));
2284
2285     if (!start)
2286         return true;
2287
2288     int size = m_buffer.size();
2289     int offset = start;
2290     UChar32 firstCharacter;
2291     U16_GET(m_buffer.data(), 0, offset, size, firstCharacter);
2292
2293     if (m_options.contains(TreatMedialCapitalAsWordStart)) {
2294         UChar32 previousCharacter;
2295         U16_PREV(m_buffer.data(), 0, offset, previousCharacter);
2296
2297         if (isSeparator(firstCharacter)) {
2298             // The start of a separator run is a word start (".org" in "webkit.org").
2299             if (!isSeparator(previousCharacter))
2300                 return true;
2301         } else if (isASCIIUpper(firstCharacter)) {
2302             // The start of an uppercase run is a word start ("Kit" in "WebKit").
2303             if (!isASCIIUpper(previousCharacter))
2304                 return true;
2305             // The last character of an uppercase run followed by a non-separator, non-digit
2306             // is a word start ("Request" in "XMLHTTPRequest").
2307             offset = start;
2308             U16_FWD_1(m_buffer.data(), offset, size);
2309             UChar32 nextCharacter = 0;
2310             if (offset < size)
2311                 U16_GET(m_buffer.data(), 0, offset, size, nextCharacter);
2312             if (!isASCIIUpper(nextCharacter) && !isASCIIDigit(nextCharacter) && !isSeparator(nextCharacter))
2313                 return true;
2314         } else if (isASCIIDigit(firstCharacter)) {
2315             // The start of a digit run is a word start ("2" in "WebKit2").
2316             if (!isASCIIDigit(previousCharacter))
2317                 return true;
2318         } else if (isSeparator(previousCharacter) || isASCIIDigit(previousCharacter)) {
2319             // The start of a non-separator, non-uppercase, non-digit run is a word start,
2320             // except after an uppercase. ("org" in "webkit.org", but not "ore" in "WebCore").
2321             return true;
2322         }
2323     }
2324
2325     // Chinese and Japanese lack word boundary marks, and there is no clear agreement on what constitutes
2326     // a word, so treat the position before any CJK character as a word start.
2327     if (FontCascade::isCJKIdeographOrSymbol(firstCharacter))
2328         return true;
2329
2330     size_t wordBreakSearchStart = start + length;
2331     while (wordBreakSearchStart > start)
2332         wordBreakSearchStart = findNextWordFromIndex(StringView(m_buffer.data(), m_buffer.size()), wordBreakSearchStart, false /* backwards */);
2333     return wordBreakSearchStart == start;
2334 }
2335
2336 inline size_t SearchBuffer::search(size_t& start)
2337 {
2338     size_t size = m_buffer.size();
2339     if (m_atBreak) {
2340         if (!size)
2341             return 0;
2342     } else {
2343         if (size != m_buffer.capacity())
2344             return 0;
2345     }
2346
2347     UStringSearch* searcher = WebCore::searcher();
2348
2349     UErrorCode status = U_ZERO_ERROR;
2350     usearch_setText(searcher, m_buffer.data(), size, &status);
2351     ASSERT(status == U_ZERO_ERROR);
2352
2353     usearch_setOffset(searcher, m_prefixLength, &status);
2354     ASSERT(status == U_ZERO_ERROR);
2355
2356     int matchStart = usearch_next(searcher, &status);
2357     ASSERT(status == U_ZERO_ERROR);
2358
2359 nextMatch:
2360     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
2361         ASSERT(matchStart == USEARCH_DONE);
2362         return 0;
2363     }
2364
2365     // Matches that start in the overlap area are only tentative.
2366     // The same match may appear later, matching more characters,
2367     // possibly including a combining character that's not yet in the buffer.
2368     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
2369         size_t overlap = m_overlap;
2370         if (m_options.contains(AtWordStarts)) {
2371             // Ensure that there is sufficient context before matchStart the next time around for
2372             // determining if it is at a word boundary.
2373             unsigned wordBoundaryContextStart = matchStart;
2374             U16_BACK_1(m_buffer.data(), 0, wordBoundaryContextStart);
2375             wordBoundaryContextStart = startOfLastWordBoundaryContext(StringView(m_buffer.data(), wordBoundaryContextStart));
2376             overlap = std::min(size - 1, std::max(overlap, size - wordBoundaryContextStart));
2377         }
2378         memcpy(m_buffer.data(), m_buffer.data() + size - overlap, overlap * sizeof(UChar));
2379         m_prefixLength -= std::min(m_prefixLength, size - overlap);
2380         m_buffer.shrink(overlap);
2381         return 0;
2382     }
2383
2384     size_t matchedLength = usearch_getMatchedLength(searcher);
2385     ASSERT_WITH_SECURITY_IMPLICATION(matchStart + matchedLength <= size);
2386
2387     // If this match is "bad", move on to the next match.
2388     if (isBadMatch(m_buffer.data() + matchStart, matchedLength)
2389         || (m_options.contains(AtWordStarts) && !isWordStartMatch(matchStart, matchedLength))
2390         || (m_options.contains(AtWordEnds) && !isWordEndMatch(matchStart, matchedLength))) {
2391         matchStart = usearch_next(searcher, &status);
2392         ASSERT(status == U_ZERO_ERROR);
2393         goto nextMatch;
2394     }
2395
2396     size_t newSize = size - (matchStart + 1);
2397     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
2398     m_prefixLength -= std::min<size_t>(m_prefixLength, matchStart + 1);
2399     m_buffer.shrink(newSize);
2400
2401     start = size - matchStart;
2402     return matchedLength;
2403 }
2404
2405 #else
2406
2407 inline SearchBuffer::SearchBuffer(const String& target, FindOptions options)
2408     : m_target(options & CaseInsensitive ? target.foldCase() : target)
2409     , m_options(options)
2410     , m_buffer(m_target.length())
2411     , m_isCharacterStartBuffer(m_target.length())
2412     , m_isBufferFull(false)
2413     , m_cursor(0)
2414 {
2415     ASSERT(!m_target.isEmpty());
2416     m_target.replace(noBreakSpace, ' ');
2417     foldQuoteMarks(m_target);
2418 }
2419
2420 inline SearchBuffer::~SearchBuffer() = default;
2421
2422 inline void SearchBuffer::reachedBreak()
2423 {
2424     m_cursor = 0;
2425     m_isBufferFull = false;
2426 }
2427
2428 inline bool SearchBuffer::atBreak() const
2429 {
2430     return !m_cursor && !m_isBufferFull;
2431 }
2432
2433 inline void SearchBuffer::append(UChar c, bool isStart)
2434 {
2435     m_buffer[m_cursor] = c == noBreakSpace ? ' ' : foldQuoteMark(c);
2436     m_isCharacterStartBuffer[m_cursor] = isStart;
2437     if (++m_cursor == m_target.length()) {
2438         m_cursor = 0;
2439         m_isBufferFull = true;
2440     }
2441 }
2442
2443 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
2444 {
2445     ASSERT(length);
2446     if (!(m_options & CaseInsensitive)) {
2447         append(characters[0], true);
2448         return 1;
2449     }
2450     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
2451     UChar foldedCharacters[maxFoldedCharacters];
2452     UErrorCode status = U_ZERO_ERROR;
2453     int numFoldedCharacters = u_strFoldCase(foldedCharacters, maxFoldedCharacters, characters, 1, U_FOLD_CASE_DEFAULT, &status);
2454     ASSERT(U_SUCCESS(status));
2455     ASSERT(numFoldedCharacters);
2456     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
2457     if (U_SUCCESS(status) && numFoldedCharacters) {
2458         numFoldedCharacters = std::min(numFoldedCharacters, maxFoldedCharacters);
2459         append(foldedCharacters[0], true);
2460         for (int i = 1; i < numFoldedCharacters; ++i)
2461             append(foldedCharacters[i], false);
2462     }
2463     return 1;
2464 }
2465
2466 inline bool SearchBuffer::needsMoreContext() const
2467 {
2468     return false;
2469 }
2470
2471 void SearchBuffer::prependContext(const UChar*, size_t)
2472 {
2473     ASSERT_NOT_REACHED();
2474 }
2475
2476 inline size_t SearchBuffer::search(size_t& start)
2477 {
2478     if (!m_isBufferFull)
2479         return 0;
2480     if (!m_isCharacterStartBuffer[m_cursor])
2481         return 0;
2482
2483     size_t tailSpace = m_target.length() - m_cursor;
2484     if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
2485         return 0;
2486     if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
2487         return 0;
2488
2489     start = length();
2490
2491     // Now that we've found a match once, we don't want to find it again, because those
2492     // are the SearchBuffer semantics, allowing for a buffer where you append more than one
2493     // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if
2494     // we want to get rid of that in the future we could track this with a separate boolean
2495     // or even move the characters to the start of the buffer and set m_isBufferFull to false.
2496     m_isCharacterStartBuffer[m_cursor] = false;
2497
2498     return start;
2499 }
2500
2501 // Returns the number of characters that were appended to the buffer (what we are searching in).
2502 // That's not necessarily the same length as the passed-in target string, because case folding
2503 // can make two strings match even though they're not the same length.
2504 size_t SearchBuffer::length() const
2505 {
2506     size_t bufferSize = m_target.length();
2507     size_t length = 0;
2508     for (size_t i = 0; i < bufferSize; ++i)
2509         length += m_isCharacterStartBuffer[i];
2510     return length;
2511 }
2512
2513 #endif
2514
2515 // --------
2516
2517 int TextIterator::rangeLength(const Range* range, bool forSelectionPreservation)
2518 {
2519     unsigned length = 0;
2520     for (TextIterator it(range, forSelectionPreservation ? TextIteratorEmitsCharactersBetweenAllVisiblePositions : TextIteratorDefaultBehavior); !it.atEnd(); it.advance())
2521         length += it.text().length();
2522     return length;
2523 }
2524
2525 Ref<Range> TextIterator::subrange(Range& entireRange, int characterOffset, int characterCount)
2526 {
2527     CharacterIterator entireRangeIterator(entireRange);
2528     return characterSubrange(entireRange.ownerDocument(), entireRangeIterator, characterOffset, characterCount);
2529 }
2530
2531 static inline bool isInsideReplacedElement(TextIterator& iterator)
2532 {
2533     ASSERT(!iterator.atEnd());
2534     ASSERT(iterator.text().length() == 1);
2535     Node* node = iterator.node();
2536     return node && isRendererReplacedElement(node->renderer());
2537 }
2538
2539 RefPtr<Range> TextIterator::rangeFromLocationAndLength(ContainerNode* scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
2540 {
2541     Ref<Range> resultRange = scope->document().createRange();
2542
2543     int docTextPosition = 0;
2544     int rangeEnd = rangeLocation + rangeLength;
2545     bool startRangeFound = false;
2546
2547     Ref<Range> textRunRange = rangeOfContents(*scope);
2548
2549     TextIterator it(textRunRange.ptr(), forSelectionPreservation ? TextIteratorEmitsCharactersBetweenAllVisiblePositions : TextIteratorDefaultBehavior);
2550     
2551     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
2552     if (!rangeLocation && !rangeLength && it.atEnd()) {
2553         resultRange->setStart(textRunRange->startContainer(), 0);
2554         resultRange->setEnd(textRunRange->startContainer(), 0);
2555         return WTFMove(resultRange);
2556     }
2557
2558     for (; !it.atEnd(); it.advance()) {
2559         int length = it.text().length();
2560         textRunRange = it.range();
2561
2562         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + length;
2563         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + length;
2564
2565         if (foundEnd) {
2566             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
2567             // position for emitted '\n's or if the renderer of the current node is a replaced element.
2568             if (length == 1 && (it.text()[0] == '\n' || isInsideReplacedElement(it))) {
2569                 it.advance();
2570                 if (!it.atEnd()) {
2571                     Ref<Range> range = it.range();
2572                     textRunRange->setEnd(range->startContainer(), range->startOffset());
2573                 } else {
2574                     Position runStart = textRunRange->startPosition();
2575                     Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
2576                     if (runEnd.isNotNull())
2577                         textRunRange->setEnd(*runEnd.containerNode(), runEnd.computeOffsetInContainerNode());
2578                 }
2579             }
2580         }
2581
2582         if (foundStart) {
2583             startRangeFound = true;
2584             if (textRunRange->startContainer().isTextNode()) {
2585                 int offset = rangeLocation - docTextPosition;
2586                 resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset());
2587             } else {
2588                 if (rangeLocation == docTextPosition)
2589                     resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset());
2590                 else
2591                     resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset());
2592             }
2593         }
2594
2595         if (foundEnd) {
2596             if (textRunRange->startContainer().isTextNode()) {
2597                 int offset = rangeEnd - docTextPosition;
2598                 resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset());
2599             } else {
2600                 if (rangeEnd == docTextPosition)
2601                     resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset());
2602                 else
2603                     resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset());
2604             }
2605             docTextPosition += length;
2606             break;
2607         }
2608
2609         docTextPosition += length;
2610     }
2611     
2612     if (!startRangeFound)
2613         return nullptr;
2614     
2615     if (rangeLength && rangeEnd > docTextPosition) // rangeEnd is out of bounds
2616         resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset());
2617     
2618     return WTFMove(resultRange);
2619 }
2620
2621 bool TextIterator::getLocationAndLengthFromRange(Node* scope, const Range* range, size_t& location, size_t& length)
2622 {
2623     location = notFound;
2624     length = 0;
2625
2626     // The critical assumption is that this only gets called with ranges that
2627     // concentrate on a given area containing the selection root. This is done
2628     // because of text fields and textareas. The DOM for those is not
2629     // directly in the document DOM, so ensure that the range does not cross a
2630     // boundary of one of those.
2631     if (&range->startContainer() != scope && !range->startContainer().isDescendantOf(scope))
2632         return false;
2633     if (&range->endContainer() != scope && !range->endContainer().isDescendantOf(scope))
2634         return false;
2635
2636     Ref<Range> testRange = Range::create(scope->document(), scope, 0, &range->startContainer(), range->startOffset());
2637     ASSERT(&testRange->startContainer() == scope);
2638     location = TextIterator::rangeLength(testRange.ptr());
2639
2640     testRange->setEnd(range->endContainer(), range->endOffset());
2641     ASSERT(&testRange->startContainer() == scope);
2642     length = TextIterator::rangeLength(testRange.ptr()) - location;
2643     return true;
2644 }
2645
2646 // --------
2647
2648 bool hasAnyPlainText(const Range& range, TextIteratorBehavior behavior)
2649 {
2650     for (TextIterator iterator { &range, behavior }; !iterator.atEnd(); iterator.advance()) {
2651         if (!iterator.text().isEmpty())
2652             return true;
2653     }
2654     return false;
2655 }
2656
2657 String plainText(const Range* r, TextIteratorBehavior defaultBehavior, bool isDisplayString)
2658 {
2659     // The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
2660     static const unsigned initialCapacity = 1 << 15;
2661
2662     unsigned bufferLength = 0;
2663     StringBuilder builder;
2664     builder.reserveCapacity(initialCapacity);
2665     TextIteratorBehavior behavior = defaultBehavior;
2666     if (!isDisplayString)
2667         behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsTextsWithoutTranscoding);
2668     
2669     for (TextIterator it(r, behavior); !it.atEnd(); it.advance()) {
2670         it.appendTextToStringBuilder(builder);
2671         bufferLength += it.text().length();
2672     }
2673
2674     if (!bufferLength)
2675         return emptyString();
2676
2677     String result = builder.toString();
2678
2679     if (isDisplayString)
2680         r->ownerDocument().displayStringModifiedByEncoding(result);
2681
2682     return result;
2683 }
2684
2685 String plainTextReplacingNoBreakSpace(const Range* range, TextIteratorBehavior defaultBehavior, bool isDisplayString)
2686 {
2687     return plainText(range, defaultBehavior, isDisplayString).replace(noBreakSpace, ' ');
2688 }
2689
2690 static Ref<Range> collapsedToBoundary(const Range& range, bool forward)
2691 {
2692     Ref<Range> result = range.cloneRange();
2693     result->collapse(!forward);
2694     return result;
2695 }
2696
2697 static TextIteratorBehavior findIteratorOptions(FindOptions options)
2698 {
2699     TextIteratorBehavior iteratorOptions = TextIteratorEntersTextControls | TextIteratorClipsToFrameAncestors;
2700     if (!options.contains(DoNotTraverseFlatTree))
2701         iteratorOptions |= TextIteratorTraversesFlatTree;
2702     return iteratorOptions;
2703 }
2704
2705 static void findPlainTextMatches(const Range& range, const String& target, FindOptions options, const WTF::Function<bool(size_t, size_t)>& match)
2706 {
2707     SearchBuffer buffer(target, options);
2708     if (buffer.needsMoreContext()) {
2709         Ref<Range> beforeStartRange = range.ownerDocument().createRange();
2710         beforeStartRange->setEnd(range.startContainer(), range.startOffset());
2711         for (SimplifiedBackwardsTextIterator backwardsIterator(beforeStartRange.get()); !backwardsIterator.atEnd(); backwardsIterator.advance()) {
2712             buffer.prependContext(backwardsIterator.text());
2713             if (!buffer.needsMoreContext())
2714                 break;
2715         }
2716     }
2717
2718     CharacterIterator findIterator(range, findIteratorOptions(options));
2719     while (!findIterator.atEnd()) {
2720         findIterator.advance(buffer.append(findIterator.text()));
2721         while (1) {
2722             size_t matchStartOffset;
2723             size_t newMatchLength = buffer.search(matchStartOffset);
2724             if (!newMatchLength) {
2725                 if (findIterator.atBreak() && !buffer.atBreak()) {
2726                     buffer.reachedBreak();
2727                     continue;
2728                 }
2729                 break;
2730             }
2731             size_t lastCharacterInBufferOffset = findIterator.characterOffset();
2732             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
2733             if (match(lastCharacterInBufferOffset - matchStartOffset, newMatchLength))
2734                 return;
2735         }
2736     }
2737 }
2738
2739 static Ref<Range> rangeForMatch(const Range& range, FindOptions options, size_t matchStart, size_t matchLength, bool searchForward)
2740 {
2741     if (!matchLength)
2742         return collapsedToBoundary(range, searchForward);
2743     CharacterIterator rangeComputeIterator(range, findIteratorOptions(options));
2744     return characterSubrange(range.ownerDocument(), rangeComputeIterator, matchStart, matchLength);
2745 }
2746
2747 Ref<Range> findClosestPlainText(const Range& range, const String& target, FindOptions options, unsigned targetOffset)
2748 {
2749     size_t matchStart = 0;
2750     size_t matchLength = 0;
2751     size_t distance = std::numeric_limits<size_t>::max();
2752     auto match = [targetOffset, &distance, &matchStart, &matchLength] (size_t start, size_t length) {
2753         size_t newDistance = std::min(abs(static_cast<signed>(start - targetOffset)), abs(static_cast<signed>(start + length - targetOffset)));
2754         if (newDistance < distance) {
2755             matchStart = start;
2756             matchLength = length;
2757             distance = newDistance;
2758         }
2759         return false;
2760     };
2761
2762     findPlainTextMatches(range, target, options, WTFMove(match));
2763     return rangeForMatch(range, options, matchStart, matchLength, !options.contains(Backwards));
2764 }
2765
2766 Ref<Range> findPlainText(const Range& range, const String& target, FindOptions options)
2767 {
2768     bool searchForward = !options.contains(Backwards);
2769     size_t matchStart = 0;
2770     size_t matchLength = 0;
2771     auto match = [searchForward, &matchStart, &matchLength] (size_t start, size_t length) {
2772         matchStart = start;
2773         matchLength = length;
2774         // Look for the last match when searching backwards instead.
2775         return searchForward;
2776     };
2777
2778     findPlainTextMatches(range, target, options, WTFMove(match));
2779     return rangeForMatch(range, options, matchStart, matchLength, searchForward);
2780 }
2781
2782 bool findPlainText(const String& document, const String& target, FindOptions options)
2783 {
2784     SearchBuffer buffer { target, options };
2785     StringView remainingText { document };
2786     while (!remainingText.isEmpty()) {
2787         size_t charactersAppended = buffer.append(document);
2788         remainingText = remainingText.substring(charactersAppended);
2789         if (remainingText.isEmpty())
2790             buffer.reachedBreak();
2791         size_t matchStartOffset;
2792         if (buffer.search(matchStartOffset))
2793             return true;
2794     }
2795     return false;
2796 }
2797
2798 }