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