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