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