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