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