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