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