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