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