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