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