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