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