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