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