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