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