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