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