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