34fa54be5cdfdbd55de73ed3465c2ad102f84ed4
[WebKit-https.git] / WebCore / editing / TextIterator.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 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 "CharacterNames.h"
31 #include "Document.h"
32 #include "HTMLElement.h"
33 #include "HTMLNames.h"
34 #include "htmlediting.h"
35 #include "InlineTextBox.h"
36 #include "Position.h"
37 #include "Range.h"
38 #include "RenderTableCell.h"
39 #include "RenderTableRow.h"
40 #include "RenderTextControl.h"
41 #include "VisiblePosition.h"
42 #include "visible_units.h"
43
44 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
45 #include <unicode/usearch.h>
46 #endif
47
48 using namespace WTF::Unicode;
49 using namespace std;
50
51 namespace WebCore {
52
53 using namespace HTMLNames;
54
55 // Buffer that knows how to compare with a search target.
56 // Keeps enough of the previous text to be able to search in the future, but no more.
57 // Non-breaking spaces are always equal to normal spaces.
58 // Case folding is also done if <isCaseSensitive> is false.
59 class SearchBuffer : Noncopyable {
60 public:
61     SearchBuffer(const String& target, bool isCaseSensitive);
62     ~SearchBuffer();
63
64     // Returns number of characters appended; guaranteed to be in the range [1, length].
65     size_t append(const UChar*, size_t length);
66     void reachedBreak();
67
68     // Result is the size in characters of what was found.
69     // And <startOffset> is the number of characters back to the start of what was found.
70     size_t search(size_t& startOffset);
71     bool atBreak() const;
72
73 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
74
75 private:
76     String m_target;
77     Vector<UChar> m_buffer;
78     size_t m_overlap;
79     bool m_atBreak;
80
81 #else
82
83 private:
84     void append(UChar, bool isCharacterStart);
85     size_t length() const;
86
87     String m_target;
88     bool m_isCaseSensitive;
89
90     Vector<UChar> m_buffer;
91     Vector<bool> m_isCharacterStartBuffer;
92     bool m_isBufferFull;
93     size_t m_cursor;
94
95 #endif
96 };
97
98 // --------
99
100 TextIterator::TextIterator()
101     : m_startContainer(0)
102     , m_startOffset(0)
103     , m_endContainer(0)
104     , m_endOffset(0)
105     , m_positionNode(0)
106     , m_textCharacters(0)
107     , m_textLength(0)
108     , m_lastCharacter(0)
109     , m_emitCharactersBetweenAllVisiblePositions(false)
110     , m_enterTextControls(false)
111 {
112 }
113
114 TextIterator::TextIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls) 
115     : m_inShadowContent(false)
116     , m_startContainer(0) 
117     , m_startOffset(0)
118     , m_endContainer(0)
119     , m_endOffset(0)
120     , m_positionNode(0)
121     , m_textCharacters(0)
122     , m_textLength(0)
123     , m_emitCharactersBetweenAllVisiblePositions(emitCharactersBetweenAllVisiblePositions)
124     , m_enterTextControls(enterTextControls)
125 {
126     if (!r)
127         return;
128
129     // get and validate the range endpoints
130     Node* startContainer = r->startContainer();
131     if (!startContainer)
132         return;
133     int startOffset = r->startOffset();
134     Node* endContainer = r->endContainer();
135     int endOffset = r->endOffset();
136
137     // Callers should be handing us well-formed ranges. If we discover that this isn't
138     // the case, we could consider changing this assertion to an early return.
139     ASSERT(r->boundaryPointsValid());
140
141     // remember range - this does not change
142     m_startContainer = startContainer;
143     m_startOffset = startOffset;
144     m_endContainer = endContainer;
145     m_endOffset = endOffset;
146
147     for (Node* n = startContainer; n; n = n->parentNode()) {
148         if (n->isShadowNode()) {
149             m_inShadowContent = true;
150             break;
151         }
152     }
153
154     // set up the current node for processing
155     m_node = r->firstNode();
156     if (m_node == 0)
157         return;
158     m_offset = m_node == m_startContainer ? m_startOffset : 0;
159     m_handledNode = false;
160     m_handledChildren = false;
161
162     // calculate first out of bounds node
163     m_pastEndNode = r->pastLastNode();
164
165     // initialize node processing state
166     m_needAnotherNewline = false;
167     m_textBox = 0;
168
169     // initialize record of previous node processing
170     m_haveEmitted = false;
171     m_lastTextNode = 0;
172     m_lastTextNodeEndedWithCollapsedSpace = false;
173     m_lastCharacter = 0;
174
175 #ifndef NDEBUG
176     // need this just because of the assert in advance()
177     m_positionNode = m_node;
178 #endif
179
180     // identify the first run
181     advance();
182 }
183
184 void TextIterator::advance()
185 {
186     // reset the run information
187     m_positionNode = 0;
188     m_textLength = 0;
189
190     // handle remembered node that needed a newline after the text node's newline
191     if (m_needAnotherNewline) {
192         // Emit the extra newline, and position it *inside* m_node, after m_node's 
193         // contents, in case it's a block, in the same way that we position the first 
194         // newline.  The range for the emitted newline should start where the line 
195         // break begins.
196         // FIXME: It would be cleaner if we emitted two newlines during the last 
197         // iteration, instead of using m_needAnotherNewline.
198         Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
199         emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
200         m_needAnotherNewline = false;
201         return;
202     }
203
204     // handle remembered text box
205     if (m_textBox) {
206         handleTextBox();
207         if (m_positionNode)
208             return;
209     }
210
211     while (m_node && m_node != m_pastEndNode) {
212         // if the range ends at offset 0 of an element, represent the
213         // position, but not the content, of that element e.g. if the
214         // node is a blockflow element, emit a newline that
215         // precedes the element
216         if (m_node == m_endContainer && m_endOffset == 0) {
217             representNodeOffsetZero();
218             m_node = 0;
219             return;
220         }
221         
222         RenderObject *renderer = m_node->renderer();
223         if (!renderer) {
224             m_handledNode = true;
225             m_handledChildren = true;
226         } else {
227             // handle current node according to its type
228             if (!m_handledNode) {
229                 if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) // FIXME: What about CDATA_SECTION_NODE?
230                     m_handledNode = handleTextNode();
231                 else if (renderer && (renderer->isImage() || renderer->isWidget() ||
232                          (renderer->node() && renderer->node()->isElementNode() &&
233                           static_cast<Element*>(renderer->node())->isFormControlElement())))
234                     m_handledNode = handleReplacedElement();
235                 else
236                     m_handledNode = handleNonTextNode();
237                 if (m_positionNode)
238                     return;
239             }
240         }
241
242         // find a new current node to handle in depth-first manner,
243         // calling exitNode() as we come back thru a parent node
244         Node *next = m_handledChildren ? 0 : m_node->firstChild();
245         m_offset = 0;
246         if (!next) {
247             next = m_node->nextSibling();
248             if (!next) {
249                 bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;
250                 Node* parentNode = m_node->parentNode();
251                 if (!parentNode && m_inShadowContent) {
252                     m_inShadowContent = false;
253                     parentNode = m_node->shadowParentNode();
254                 }
255                 while (!next && parentNode) {
256                     if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))
257                         return;
258                     bool haveRenderer = m_node->renderer();
259                     m_node = parentNode;
260                     parentNode = m_node->parentNode();
261                     if (!parentNode && m_inShadowContent) {
262                         m_inShadowContent = false;
263                         parentNode = m_node->shadowParentNode();
264                     }
265                     if (haveRenderer)
266                         exitNode();
267                     if (m_positionNode) {
268                         m_handledNode = true;
269                         m_handledChildren = true;
270                         return;
271                     }
272                     next = m_node->nextSibling();
273                 }
274             }
275         }
276
277         // set the new current node
278         m_node = next;
279         m_handledNode = false;
280         m_handledChildren = false;
281
282         // how would this ever be?
283         if (m_positionNode)
284             return;
285     }
286 }
287
288 static inline bool compareBoxStart(const InlineTextBox *first, const InlineTextBox *second)
289 {
290     return first->start() < second->start();
291 }
292
293 bool TextIterator::handleTextNode()
294 {
295     RenderText* renderer = toRenderText(m_node->renderer());
296     if (renderer->style()->visibility() != VISIBLE)
297         return false;
298         
299     m_lastTextNode = m_node;
300     String str = renderer->text();
301
302     // handle pre-formatted text
303     if (!renderer->style()->collapseWhiteSpace()) {
304         int runStart = m_offset;
305         if (m_lastTextNodeEndedWithCollapsedSpace) {
306             emitCharacter(' ', m_node, 0, runStart, runStart);
307             return false;
308         }
309         int strLength = str.length();
310         int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
311         int runEnd = min(strLength, end);
312
313         if (runStart >= runEnd)
314             return true;
315
316         emitText(m_node, runStart, runEnd);
317         return true;
318     }
319
320     if (!renderer->firstTextBox() && str.length() > 0) {
321         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
322         return true;
323     }
324
325     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
326     if (renderer->containsReversedText()) {
327         m_sortedTextBoxes.clear();
328         for (InlineTextBox * textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
329             m_sortedTextBoxes.append(textBox);
330         }
331         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 
332         m_sortedTextBoxesPosition = 0;
333     }
334     
335     m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
336     handleTextBox();
337     return true;
338 }
339
340 void TextIterator::handleTextBox()
341 {    
342     RenderText *renderer = toRenderText(m_node->renderer());
343     String str = renderer->text();
344     int start = m_offset;
345     int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
346     while (m_textBox) {
347         int textBoxStart = m_textBox->start();
348         int runStart = max(textBoxStart, start);
349
350         // Check for collapsed space at the start of this run.
351         InlineTextBox *firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
352         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
353             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
354         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {
355             if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {
356                 unsigned spaceRunStart = runStart - 1;
357                 while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')
358                     --spaceRunStart;
359                 emitText(m_node, spaceRunStart, spaceRunStart + 1);
360             } else
361                 emitCharacter(' ', m_node, 0, runStart, runStart);
362             return;
363         }
364         int textBoxEnd = textBoxStart + m_textBox->len();
365         int runEnd = min(textBoxEnd, end);
366         
367         // Determine what the next text box will be, but don't advance yet
368         InlineTextBox *nextTextBox = 0;
369         if (renderer->containsReversedText()) {
370             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
371                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
372         } else 
373             nextTextBox = m_textBox->nextTextBox();
374
375         if (runStart < runEnd) {
376             // Handle either a single newline character (which becomes a space),
377             // or a run of characters that does not include a newline.
378             // This effectively translates newlines to spaces without copying the text.
379             if (str[runStart] == '\n') {
380                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
381                 m_offset = runStart + 1;
382             } else {
383                 int subrunEnd = str.find('\n', runStart);
384                 if (subrunEnd == -1 || subrunEnd > runEnd)
385                     subrunEnd = runEnd;
386     
387                 m_offset = subrunEnd;
388                 emitText(m_node, runStart, subrunEnd);
389             }
390
391             // If we are doing a subrun that doesn't go to the end of the text box,
392             // come back again to finish handling this text box; don't advance to the next one.
393             if (m_positionEndOffset < textBoxEnd)
394                 return;
395
396             // Advance and return
397             int nextRunStart = nextTextBox ? nextTextBox->start() : str.length();
398             if (nextRunStart > runEnd)
399                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
400             m_textBox = nextTextBox;
401             if (renderer->containsReversedText())
402                 ++m_sortedTextBoxesPosition;
403             return;
404         }
405         // Advance and continue
406         m_textBox = nextTextBox;
407         if (renderer->containsReversedText())
408             ++m_sortedTextBoxesPosition;
409     }
410 }
411
412 bool TextIterator::handleReplacedElement()
413 {
414     RenderObject* renderer = m_node->renderer();
415     if (renderer->style()->visibility() != VISIBLE)
416         return false;
417
418     if (m_lastTextNodeEndedWithCollapsedSpace) {
419         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
420         return false;
421     }
422
423     if (m_enterTextControls && renderer->isTextControl()) {
424         m_node = toRenderTextControl(renderer)->innerTextElement();
425         m_offset = 0;
426         m_inShadowContent = true;
427         return false;
428     }
429
430     m_haveEmitted = true;
431
432     if (m_emitCharactersBetweenAllVisiblePositions) {
433         // We want replaced elements to behave like punctuation for boundary 
434         // finding, and to simply take up space for the selection preservation 
435         // code in moveParagraphs, so we use a comma.
436         emitCharacter(',', m_node->parentNode(), m_node, 0, 1);
437         return true;
438     }
439
440     m_positionNode = m_node->parentNode();
441     m_positionOffsetBaseNode = m_node;
442     m_positionStartOffset = 0;
443     m_positionEndOffset = 1;
444
445     m_textCharacters = 0;
446     m_textLength = 0;
447
448     m_lastCharacter = 0;
449
450     return true;
451 }
452
453 static bool shouldEmitTabBeforeNode(Node* node)
454 {
455     RenderObject* r = node->renderer();
456     
457     // Table cells are delimited by tabs.
458     if (!r || !isTableCell(node))
459         return false;
460     
461     // Want a tab before every cell other than the first one
462     RenderTableCell* rc = static_cast<RenderTableCell*>(r);
463     RenderTable* t = rc->table();
464     return t && (t->cellBefore(rc) || t->cellAbove(rc));
465 }
466
467 static bool shouldEmitNewlineForNode(Node* node)
468 {
469     // br elements are represented by a single newline.
470     RenderObject* r = node->renderer();
471     if (!r)
472         return node->hasTagName(brTag);
473         
474     return r->isBR();
475 }
476
477 static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)
478 {
479     // Block flow (versus inline flow) is represented by having
480     // a newline both before and after the element.
481     RenderObject* r = node->renderer();
482     if (!r) {
483         return (node->hasTagName(blockquoteTag)
484                 || node->hasTagName(ddTag)
485                 || node->hasTagName(divTag)
486                 || node->hasTagName(dlTag)
487                 || node->hasTagName(dtTag)
488                 || node->hasTagName(h1Tag)
489                 || node->hasTagName(h2Tag)
490                 || node->hasTagName(h3Tag)
491                 || node->hasTagName(h4Tag)
492                 || node->hasTagName(h5Tag)
493                 || node->hasTagName(h6Tag)
494                 || node->hasTagName(hrTag)
495                 || node->hasTagName(liTag)
496                 || node->hasTagName(listingTag)
497                 || node->hasTagName(olTag)
498                 || node->hasTagName(pTag)
499                 || node->hasTagName(preTag)
500                 || node->hasTagName(trTag)
501                 || node->hasTagName(ulTag));
502     }
503     
504     // Need to make an exception for table cells, because they are blocks, but we
505     // want them tab-delimited rather than having newlines before and after.
506     if (isTableCell(node))
507         return false;
508     
509     // Need to make an exception for table row elements, because they are neither
510     // "inline" or "RenderBlock", but we want newlines for them.
511     if (r->isTableRow()) {
512         RenderTable* t = static_cast<RenderTableRow*>(r)->table();
513         if (t && !t->isInline())
514             return true;
515     }
516     
517     return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();
518 }
519
520 static bool shouldEmitNewlineAfterNode(Node* node)
521 {
522     // FIXME: It should be better but slower to create a VisiblePosition here.
523     if (!shouldEmitNewlinesBeforeAndAfterNode(node))
524         return false;
525     // Check if this is the very last renderer in the document.
526     // If so, then we should not emit a newline.
527     while ((node = node->traverseNextSibling()))
528         if (node->renderer())
529             return true;
530     return false;
531 }
532
533 static bool shouldEmitNewlineBeforeNode(Node* node)
534 {
535     return shouldEmitNewlinesBeforeAndAfterNode(node); 
536 }
537
538 static bool shouldEmitExtraNewlineForNode(Node* node)
539 {
540     // When there is a significant collapsed bottom margin, emit an extra
541     // newline for a more realistic result.  We end up getting the right
542     // result even without margin collapsing. For example: <div><p>text</p></div>
543     // will work right even if both the <div> and the <p> have bottom margins.
544     RenderObject* r = node->renderer();
545     if (!r || !r->isBox())
546         return false;
547     
548     // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears
549     // not to do this at all
550     if (node->hasTagName(h1Tag)
551         || node->hasTagName(h2Tag)
552         || node->hasTagName(h3Tag)
553         || node->hasTagName(h4Tag)
554         || node->hasTagName(h5Tag)
555         || node->hasTagName(h6Tag)
556         || node->hasTagName(pTag)) {
557         RenderStyle* style = r->style();
558         if (style) {
559             int bottomMargin = toRenderBox(r)->collapsedMarginBottom();
560             int fontSize = style->fontDescription().computedPixelSize();
561             if (bottomMargin * 2 >= fontSize)
562                 return true;
563         }
564     }
565     
566     return false;
567 }
568
569 // 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).
570 bool TextIterator::shouldRepresentNodeOffsetZero()
571 {
572     if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable())
573         return true;
574         
575     // Leave element positioned flush with start of a paragraph
576     // (e.g. do not insert tab before a table cell at the start of a paragraph)
577     if (m_lastCharacter == '\n')
578         return false;
579     
580     // Otherwise, show the position if we have emitted any characters
581     if (m_haveEmitted)
582         return true;
583     
584     // We've not emitted anything yet. Generally, there is no need for any positioning then.
585     // The only exception is when the element is visually not in the same line as
586     // the start of the range (e.g. the range starts at the end of the previous paragraph).
587     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we
588     // make quicker checks to possibly avoid that. Another check that we could make is
589     // is whether the inline vs block flow changed since the previous visible element.
590     // I think we're already in a special enough case that that won't be needed, tho.
591
592     // No character needed if this is the first node in the range.
593     if (m_node == m_startContainer)
594         return false;
595     
596     // If we are outside the start container's subtree, assume we need to emit.
597     // FIXME: m_startContainer could be an inline block
598     if (!m_node->isDescendantOf(m_startContainer))
599         return true;
600
601     // If we started as m_startContainer offset 0 and the current node is a descendant of
602     // the start container, we already had enough context to correctly decide whether to
603     // emit after a preceding block. We chose not to emit (m_haveEmitted is false),
604     // so don't second guess that now.
605     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably
606     // immaterial since we likely would have already emitted something by now.
607     if (m_startOffset == 0)
608         return false;
609         
610     // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning.
611     // Additionally, if the range we are iterating over contains huge sections of unrendered content, 
612     // we would create VisiblePositions on every call to this function without this check.
613     if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE)
614         return false;
615     
616     // The currPos.isNotNull() check is needed because positions in non-html content
617     // (like svg) do not have visible positions, and we don't want to emit for them either.
618     VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM);
619     VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM);
620     return currPos.isNotNull() && !inSameLine(startPos, currPos);
621 }
622
623 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)
624 {
625     return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitCharactersBetweenAllVisiblePositions);
626 }
627
628 void TextIterator::representNodeOffsetZero()
629 {
630     // Emit a character to show the positioning of m_node.
631     
632     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 
633     // create VisiblePositions, which is expensive.  So, we perform the inexpensive checks
634     // on m_node to see if it necessitates emitting a character first and will early return 
635     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
636     if (shouldEmitTabBeforeNode(m_node)) {
637         if (shouldRepresentNodeOffsetZero())
638             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);
639     } else if (shouldEmitNewlineBeforeNode(m_node)) {
640         if (shouldRepresentNodeOffsetZero())
641             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);
642     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {
643         if (shouldRepresentNodeOffsetZero())
644             emitCharacter(' ', m_node->parentNode(), m_node, 0, 0);
645     }
646 }
647
648 bool TextIterator::handleNonTextNode()
649 {
650     if (shouldEmitNewlineForNode(m_node))
651         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
652     else if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())
653         emitCharacter(' ', m_node->parentNode(), m_node, 0, 1);
654     else
655         representNodeOffsetZero();
656
657     return true;
658 }
659
660 void TextIterator::exitNode()
661 {
662     // prevent emitting a newline when exiting a collapsed block at beginning of the range
663     // FIXME: !m_haveEmitted does not necessarily mean there was a collapsed block... it could
664     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
665     // therefore look like a blank line.
666     if (!m_haveEmitted)
667         return;
668         
669     // Emit with a position *inside* m_node, after m_node's contents, in 
670     // case it is a block, because the run should start where the 
671     // emitted character is positioned visually.
672     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
673     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
674     // the logic in _web_attributedStringFromRange match.  We'll get that for free when we switch to use
675     // TextIterator in _web_attributedStringFromRange.
676     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
677     if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {
678         // use extra newline to represent margin bottom, as needed
679         bool addNewline = shouldEmitExtraNewlineForNode(m_node);
680         
681         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
682         // contain a VisiblePosition when doing selection preservation.
683         if (m_lastCharacter != '\n') {
684             // insert a newline with a position following this block's contents.
685             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
686             // remember whether to later add a newline for the current node
687             ASSERT(!m_needAnotherNewline);
688             m_needAnotherNewline = addNewline;
689         } else if (addNewline)
690             // insert a newline with a position following this block's contents.
691             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
692     }
693     
694     // If nothing was emitted, see if we need to emit a space.
695     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))
696         emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1);
697 }
698
699 void TextIterator::emitCharacter(UChar c, Node *textNode, Node *offsetBaseNode, int textStartOffset, int textEndOffset)
700 {
701     m_haveEmitted = true;
702     
703     // remember information with which to construct the TextIterator::range()
704     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
705     m_positionNode = textNode;
706     m_positionOffsetBaseNode = offsetBaseNode;
707     m_positionStartOffset = textStartOffset;
708     m_positionEndOffset = textEndOffset;
709  
710     // remember information with which to construct the TextIterator::characters() and length()
711     m_singleCharacterBuffer = c;
712     m_textCharacters = &m_singleCharacterBuffer;
713     m_textLength = 1;
714
715     // remember some iteration state
716     m_lastTextNodeEndedWithCollapsedSpace = false;
717     m_lastCharacter = c;
718 }
719
720 void TextIterator::emitText(Node* textNode, int textStartOffset, int textEndOffset)
721 {
722     RenderText* renderer = toRenderText(m_node->renderer());
723     String str = renderer->text();
724     ASSERT(str.characters());
725
726     m_positionNode = textNode;
727     m_positionOffsetBaseNode = 0;
728     m_positionStartOffset = textStartOffset;
729     m_positionEndOffset = textEndOffset;
730     m_textCharacters = str.characters() + textStartOffset;
731     m_textLength = textEndOffset - textStartOffset;
732     m_lastCharacter = str[textEndOffset - 1];
733
734     m_lastTextNodeEndedWithCollapsedSpace = false;
735     m_haveEmitted = true;
736 }
737
738 PassRefPtr<Range> TextIterator::range() const
739 {
740     // use the current run information, if we have it
741     if (m_positionNode) {
742         if (m_positionOffsetBaseNode) {
743             int index = m_positionOffsetBaseNode->nodeIndex();
744             m_positionStartOffset += index;
745             m_positionEndOffset += index;
746             m_positionOffsetBaseNode = 0;
747         }
748         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
749     }
750
751     // otherwise, return the end of the overall range we were given
752     if (m_endContainer)
753         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
754         
755     return 0;
756 }
757     
758 Node* TextIterator::node() const
759 {
760     RefPtr<Range> textRange = range();
761     if (!textRange)
762         return 0;
763
764     Node* node = textRange->startContainer();
765     if (!node)
766         return 0;
767     if (node->offsetInCharacters())
768         return node;
769     
770     return node->childNode(textRange->startOffset());
771 }
772
773 // --------
774
775 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
776 {
777 }
778
779 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range *r)
780 {
781     m_positionNode = 0;
782
783     if (!r)
784         return;
785
786     Node* startNode = r->startContainer();
787     if (!startNode)
788         return;
789     Node* endNode = r->endContainer();
790     int startOffset = r->startOffset();
791     int endOffset = r->endOffset();
792
793     if (!startNode->offsetInCharacters()) {
794         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
795             startNode = startNode->childNode(startOffset);
796             startOffset = 0;
797         }
798     }
799     if (!endNode->offsetInCharacters()) {
800         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {
801             endNode = endNode->childNode(endOffset - 1);
802             endOffset = endNode->offsetInCharacters() ? endNode->maxCharacterOffset() : endNode->childNodeCount();
803         }
804     }
805
806     m_node = endNode;
807     m_offset = endOffset;
808     m_handledNode = false;
809     m_handledChildren = endOffset == 0;
810
811     m_startNode = startNode;
812     m_startOffset = startOffset;
813     m_endNode = endNode;
814     m_endOffset = endOffset;
815     
816 #ifndef NDEBUG
817     // Need this just because of the assert.
818     m_positionNode = endNode;
819 #endif
820
821     m_lastTextNode = 0;
822     m_lastCharacter = '\n';
823     
824     if (startOffset == 0 || !startNode->firstChild()) {
825         m_pastStartNode = startNode->previousSibling();
826         while (!m_pastStartNode && startNode->parentNode()) {
827             startNode = startNode->parentNode();
828             m_pastStartNode = startNode->previousSibling();
829         }
830     } else
831         m_pastStartNode = startNode->childNode(startOffset - 1);
832
833     advance();
834 }
835
836 void SimplifiedBackwardsTextIterator::advance()
837 {
838     ASSERT(m_positionNode);
839
840     m_positionNode = 0;
841     m_textLength = 0;
842
843     while (m_node && m_node != m_pastStartNode) {
844         // Don't handle node if we start iterating at [node, 0].
845         if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) {
846             RenderObject *renderer = m_node->renderer();
847             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
848                 // FIXME: What about CDATA_SECTION_NODE?
849                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
850                     m_handledNode = handleTextNode();
851             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
852                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
853                     m_handledNode = handleReplacedElement();
854             } else
855                 m_handledNode = handleNonTextNode();
856             if (m_positionNode)
857                 return;
858         }
859
860         Node* next = m_handledChildren ? 0 : m_node->lastChild();
861         if (!next) {
862             // Exit empty containers as we pass over them or containers
863             // where [container, 0] is where we started iterating.
864             if (!m_handledNode &&
865                 canHaveChildrenForEditing(m_node) && 
866                 m_node->parentNode() && 
867                 (!m_node->lastChild() || (m_node == m_endNode && m_endOffset == 0))) {
868                 exitNode();
869                 if (m_positionNode) {
870                     m_handledNode = true;
871                     m_handledChildren = true;
872                     return;
873                 }            
874             }
875             // Exit all other containers.
876             next = m_node->previousSibling();
877             while (!next) {
878                 if (!m_node->parentNode())
879                     break;
880                 m_node = m_node->parentNode();
881                 exitNode();
882                 if (m_positionNode) {
883                     m_handledNode = true;
884                     m_handledChildren = true;
885                     return;
886                 }
887                 next = m_node->previousSibling();
888             }
889         }
890         
891         m_node = next;
892         m_offset = m_node ? caretMaxOffset(m_node) : 0;
893         m_handledNode = false;
894         m_handledChildren = false;
895         
896         if (m_positionNode)
897             return;
898     }
899 }
900
901 bool SimplifiedBackwardsTextIterator::handleTextNode()
902 {
903     m_lastTextNode = m_node;
904
905     RenderText *renderer = toRenderText(m_node->renderer());
906     String str = renderer->text();
907
908     if (!renderer->firstTextBox() && str.length() > 0)
909         return true;
910
911     m_positionEndOffset = m_offset;
912
913     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
914     m_positionNode = m_node;
915     m_positionStartOffset = m_offset;
916     m_textLength = m_positionEndOffset - m_positionStartOffset;
917     m_textCharacters = str.characters() + m_positionStartOffset;
918
919     m_lastCharacter = str[m_positionEndOffset - 1];
920
921     return true;
922 }
923
924 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
925 {
926     unsigned index = m_node->nodeIndex();
927     // We want replaced elements to behave like punctuation for boundary 
928     // finding, and to simply take up space for the selection preservation 
929     // code in moveParagraphs, so we use a comma.  Unconditionally emit
930     // here because this iterator is only used for boundary finding.
931     emitCharacter(',', m_node->parentNode(), index, index + 1);
932     return true;
933 }
934
935 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
936 {    
937     // We can use a linefeed in place of a tab because this simple iterator is only used to
938     // find boundaries, not actual content.  A linefeed breaks words, sentences, and paragraphs.
939     if (shouldEmitNewlineForNode(m_node) ||
940         shouldEmitNewlineAfterNode(m_node) ||
941         shouldEmitTabBeforeNode(m_node)) {
942         unsigned index = m_node->nodeIndex();
943         // The start of this emitted range is wrong, ensuring correctness would require
944         // VisiblePositions and so would be slow.  previousBoundary expects this.
945         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
946     }
947     
948     return true;
949 }
950
951 void SimplifiedBackwardsTextIterator::exitNode()
952 {
953     if (shouldEmitNewlineForNode(m_node) ||
954         shouldEmitNewlineBeforeNode(m_node) ||
955         shouldEmitTabBeforeNode(m_node))
956         // The start of this emitted range is wrong, ensuring correctness would require
957         // VisiblePositions and so would be slow.  previousBoundary expects this.
958         emitCharacter('\n', m_node, 0, 0);
959 }
960
961 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node *node, int startOffset, int endOffset)
962 {
963     m_singleCharacterBuffer = c;
964     m_positionNode = node;
965     m_positionStartOffset = startOffset;
966     m_positionEndOffset = endOffset;
967     m_textCharacters = &m_singleCharacterBuffer;
968     m_textLength = 1;
969     m_lastCharacter = c;
970 }
971
972 PassRefPtr<Range> SimplifiedBackwardsTextIterator::range() const
973 {
974     if (m_positionNode)
975         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
976     
977     return Range::create(m_startNode->document(), m_startNode, m_startOffset, m_startNode, m_startOffset);
978 }
979
980 // --------
981
982 CharacterIterator::CharacterIterator()
983     : m_offset(0)
984     , m_runOffset(0)
985     , m_atBreak(true)
986 {
987 }
988
989 CharacterIterator::CharacterIterator(const Range *r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls)
990     : m_offset(0)
991     , m_runOffset(0)
992     , m_atBreak(true)
993     , m_textIterator(r, emitCharactersBetweenAllVisiblePositions, enterTextControls)
994 {
995     while (!atEnd() && m_textIterator.length() == 0)
996         m_textIterator.advance();
997 }
998
999 PassRefPtr<Range> CharacterIterator::range() const
1000 {
1001     RefPtr<Range> r = m_textIterator.range();
1002     if (!m_textIterator.atEnd()) {
1003         if (m_textIterator.length() <= 1) {
1004             ASSERT(m_runOffset == 0);
1005         } else {
1006             Node* n = r->startContainer();
1007             ASSERT(n == r->endContainer());
1008             int offset = r->startOffset() + m_runOffset;
1009             ExceptionCode ec = 0;
1010             r->setStart(n, offset, ec);
1011             r->setEnd(n, offset + 1, ec);
1012             ASSERT(!ec);
1013         }
1014     }
1015     return r.release();
1016 }
1017
1018 void CharacterIterator::advance(int count)
1019 {
1020     if (count <= 0) {
1021         ASSERT(count == 0);
1022         return;
1023     }
1024     
1025     m_atBreak = false;
1026
1027     // easy if there is enough left in the current m_textIterator run
1028     int remaining = m_textIterator.length() - m_runOffset;
1029     if (count < remaining) {
1030         m_runOffset += count;
1031         m_offset += count;
1032         return;
1033     }
1034
1035     // exhaust the current m_textIterator run
1036     count -= remaining;
1037     m_offset += remaining;
1038     
1039     // move to a subsequent m_textIterator run
1040     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1041         int runLength = m_textIterator.length();
1042         if (runLength == 0)
1043             m_atBreak = true;
1044         else {
1045             // see whether this is m_textIterator to use
1046             if (count < runLength) {
1047                 m_runOffset = count;
1048                 m_offset += count;
1049                 return;
1050             }
1051             
1052             // exhaust this m_textIterator run
1053             count -= runLength;
1054             m_offset += runLength;
1055         }
1056     }
1057
1058     // ran to the end of the m_textIterator... no more runs left
1059     m_atBreak = true;
1060     m_runOffset = 0;
1061 }
1062
1063 String CharacterIterator::string(int numChars)
1064 {
1065     Vector<UChar> result;
1066     result.reserveInitialCapacity(numChars);
1067     while (numChars > 0 && !atEnd()) {
1068         int runSize = min(numChars, length());
1069         result.append(characters(), runSize);
1070         numChars -= runSize;
1071         advance(runSize);
1072     }
1073     return String::adopt(result);
1074 }
1075
1076 static PassRefPtr<Range> characterSubrange(CharacterIterator& it, int offset, int length)
1077 {
1078     it.advance(offset);
1079     RefPtr<Range> start = it.range();
1080
1081     if (length > 1)
1082         it.advance(length - 1);
1083     RefPtr<Range> end = it.range();
1084
1085     return Range::create(start->startContainer()->document(), 
1086         start->startContainer(), start->startOffset(), 
1087         end->endContainer(), end->endOffset());
1088 }
1089
1090 BackwardsCharacterIterator::BackwardsCharacterIterator()
1091     : m_offset(0)
1092     , m_runOffset(0)
1093     , m_atBreak(true)
1094 {
1095 }
1096
1097 BackwardsCharacterIterator::BackwardsCharacterIterator(const Range* range)
1098     : m_offset(0)
1099     , m_runOffset(0)
1100     , m_atBreak(true)
1101     , m_textIterator(range)
1102 {
1103     while (!atEnd() && !m_textIterator.length())
1104         m_textIterator.advance();
1105 }
1106
1107 PassRefPtr<Range> BackwardsCharacterIterator::range() const
1108 {
1109     RefPtr<Range> r = m_textIterator.range();
1110     if (!m_textIterator.atEnd()) {
1111         if (m_textIterator.length() <= 1)
1112             ASSERT(m_runOffset == 0);
1113         else {
1114             Node* n = r->startContainer();
1115             ASSERT(n == r->endContainer());
1116             int offset = r->endOffset() - m_runOffset;
1117             ExceptionCode ec = 0;
1118             r->setStart(n, offset - 1, ec);
1119             r->setEnd(n, offset, ec);
1120             ASSERT(!ec);
1121         }
1122     }
1123     return r.release();
1124 }
1125
1126 void BackwardsCharacterIterator::advance(int count)
1127 {
1128     if (count <= 0) {
1129         ASSERT(!count);
1130         return;
1131     }
1132
1133     m_atBreak = false;
1134
1135     int remaining = m_textIterator.length() - m_runOffset;
1136     if (count < remaining) {
1137         m_runOffset += count;
1138         m_offset += count;
1139         return;
1140     }
1141
1142     count -= remaining;
1143     m_offset += remaining;
1144
1145     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1146         int runLength = m_textIterator.length();
1147         if (runLength == 0)
1148             m_atBreak = true;
1149         else {
1150             if (count < runLength) {
1151                 m_runOffset = count;
1152                 m_offset += count;
1153                 return;
1154             }
1155             
1156             count -= runLength;
1157             m_offset += runLength;
1158         }
1159     }
1160
1161     m_atBreak = true;
1162     m_runOffset = 0;
1163 }
1164
1165 // --------
1166
1167 WordAwareIterator::WordAwareIterator()
1168 : m_previousText(0), m_didLookAhead(false)
1169 {
1170 }
1171
1172 WordAwareIterator::WordAwareIterator(const Range *r)
1173 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
1174 {
1175     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
1176     advance();              // get in position over the first chunk of text
1177 }
1178
1179 // We're always in one of these modes:
1180 // - The current chunk in the text iterator is our current chunk
1181 //      (typically its a piece of whitespace, or text that ended with whitespace)
1182 // - The previous chunk in the text iterator is our current chunk
1183 //      (we looked ahead to the next chunk and found a word boundary)
1184 // - We built up our own chunk of text from many chunks from the text iterator
1185
1186 // FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
1187
1188 void WordAwareIterator::advance()
1189 {
1190     m_previousText = 0;
1191     m_buffer.clear();      // toss any old buffer we built up
1192
1193     // If last time we did a look-ahead, start with that looked-ahead chunk now
1194     if (!m_didLookAhead) {
1195         ASSERT(!m_textIterator.atEnd());
1196         m_textIterator.advance();
1197     }
1198     m_didLookAhead = false;
1199
1200     // Go to next non-empty chunk 
1201     while (!m_textIterator.atEnd() && m_textIterator.length() == 0)
1202         m_textIterator.advance();
1203     m_range = m_textIterator.range();
1204
1205     if (m_textIterator.atEnd())
1206         return;
1207     
1208     while (1) {
1209         // If this chunk ends in whitespace we can just use it as our chunk.
1210         if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1]))
1211             return;
1212
1213         // If this is the first chunk that failed, save it in previousText before look ahead
1214         if (m_buffer.isEmpty()) {
1215             m_previousText = m_textIterator.characters();
1216             m_previousLength = m_textIterator.length();
1217         }
1218
1219         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
1220         m_textIterator.advance();
1221         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) {
1222             m_didLookAhead = true;
1223             return;
1224         }
1225
1226         if (m_buffer.isEmpty()) {
1227             // Start gobbling chunks until we get to a suitable stopping point
1228             m_buffer.append(m_previousText, m_previousLength);
1229             m_previousText = 0;
1230         }
1231         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
1232         int exception = 0;
1233         m_range->setEnd(m_textIterator.range()->endContainer(), m_textIterator.range()->endOffset(), exception);
1234     }
1235 }
1236
1237 int WordAwareIterator::length() const
1238 {
1239     if (!m_buffer.isEmpty())
1240         return m_buffer.size();
1241     if (m_previousText)
1242         return m_previousLength;
1243     return m_textIterator.length();
1244 }
1245
1246 const UChar* WordAwareIterator::characters() const
1247 {
1248     if (!m_buffer.isEmpty())
1249         return m_buffer.data();
1250     if (m_previousText)
1251         return m_previousText;
1252     return m_textIterator.characters();
1253 }
1254
1255 // --------
1256
1257 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
1258
1259 static const size_t minimumSearchBufferSize = 8192;
1260
1261 #ifndef NDEBUG
1262 static bool searcherInUse;
1263 #endif
1264
1265 static UStringSearch* createSearcher()
1266 {
1267     // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
1268     // but it doesn't matter exactly what it is, since we don't perform any searches
1269     // without setting both the pattern and the text.
1270
1271     // Pass empty string for the locale for now to get the Unicode Collation Algorithm,
1272     // rather than something locale-specific.
1273
1274     UErrorCode status = U_ZERO_ERROR;
1275     UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, "", 0, &status);
1276     ASSERT(status == U_ZERO_ERROR);
1277     return searcher;
1278 }
1279
1280 static UStringSearch* searcher()
1281 {
1282     static UStringSearch* searcher = createSearcher();
1283     return searcher;
1284 }
1285
1286 static inline void lockSearcher()
1287 {
1288 #ifndef NDEBUG
1289     ASSERT(!searcherInUse);
1290     searcherInUse = true;
1291 #endif
1292 }
1293
1294 static inline void unlockSearcher()
1295 {
1296 #ifndef NDEBUG
1297     ASSERT(searcherInUse);
1298     searcherInUse = false;
1299 #endif
1300 }
1301
1302 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1303     : m_target(target)
1304     , m_atBreak(true)
1305 {
1306     ASSERT(!m_target.isEmpty());
1307
1308     size_t targetLength = target.length();
1309     m_buffer.reserveInitialCapacity(max(targetLength * 8, minimumSearchBufferSize));
1310     m_overlap = m_buffer.capacity() / 4;
1311
1312     // Grab the single global searcher.
1313     // If we ever have a reason to do more than once search buffer at once, we'll have
1314     // to move to multiple searchers.
1315     lockSearcher();
1316
1317     UStringSearch* searcher = WebCore::searcher();
1318     UCollator* collator = usearch_getCollator(searcher);
1319
1320     UCollationStrength strength = isCaseSensitive ? UCOL_TERTIARY : UCOL_PRIMARY;
1321     if (ucol_getStrength(collator) != strength) {
1322         ucol_setStrength(collator, strength);
1323         usearch_reset(searcher);
1324     }
1325
1326     UErrorCode status = U_ZERO_ERROR;
1327     usearch_setPattern(searcher, m_target.characters(), targetLength, &status);
1328     ASSERT(status == U_ZERO_ERROR);
1329 }
1330
1331 inline SearchBuffer::~SearchBuffer()
1332 {
1333     unlockSearcher();
1334 }
1335
1336 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1337 {
1338     ASSERT(length);
1339
1340     if (m_atBreak) {
1341         m_buffer.shrink(0);
1342         m_atBreak = false;
1343     } else if (m_buffer.size() == m_buffer.capacity()) {
1344         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
1345         m_buffer.shrink(m_overlap);
1346     }
1347
1348     size_t usableLength = min(m_buffer.capacity() - m_buffer.size(), length);
1349     ASSERT(usableLength);
1350     m_buffer.append(characters, usableLength);
1351     return usableLength;
1352 }
1353
1354 inline bool SearchBuffer::atBreak() const
1355 {
1356     return m_atBreak;
1357 }
1358
1359 inline void SearchBuffer::reachedBreak()
1360 {
1361     m_atBreak = true;
1362 }
1363
1364 inline size_t SearchBuffer::search(size_t& start)
1365 {
1366     size_t size = m_buffer.size();
1367     if (m_atBreak) {
1368         if (!size)
1369             return 0;
1370     } else {
1371         if (size != m_buffer.capacity())
1372             return 0;
1373     }
1374
1375     UStringSearch* searcher = WebCore::searcher();
1376
1377     UErrorCode status = U_ZERO_ERROR;
1378     usearch_setText(searcher, m_buffer.data(), size, &status);
1379     ASSERT(status == U_ZERO_ERROR);
1380
1381     int matchStart = usearch_first(searcher, &status);
1382     ASSERT(status == U_ZERO_ERROR);
1383     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
1384         ASSERT(matchStart == USEARCH_DONE);
1385         return 0;
1386     }
1387
1388     // Matches that start in the overlap area are only tentative.
1389     // The same match may appear later, matching more characters,
1390     // possibly including a combining character that's not yet in the buffer.
1391     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
1392         memcpy(m_buffer.data(), m_buffer.data() + size - m_overlap, m_overlap * sizeof(UChar));
1393         m_buffer.shrink(m_overlap);
1394         return 0;
1395     }
1396
1397     size_t newSize = size - (matchStart + 1);
1398     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
1399     m_buffer.shrink(newSize);
1400
1401     start = size - matchStart;
1402     return usearch_getMatchedLength(searcher);
1403 }
1404
1405 #else // !ICU_UNICODE
1406
1407 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1408     : m_target(isCaseSensitive ? target : target.foldCase())
1409     , m_isCaseSensitive(isCaseSensitive)
1410     , m_buffer(m_target.length())
1411     , m_isCharacterStartBuffer(m_target.length())
1412     , m_isBufferFull(false)
1413     , m_cursor(0)
1414 {
1415     ASSERT(!m_target.isEmpty());
1416     m_target.replace(noBreakSpace, ' ');
1417 }
1418
1419 inline SearchBuffer::~SearchBuffer()
1420 {
1421 }
1422
1423 inline void SearchBuffer::reachedBreak()
1424 {
1425     m_cursor = 0;
1426     m_isBufferFull = false;
1427 }
1428
1429 inline bool SearchBuffer::atBreak() const
1430 {
1431     return !m_cursor && !m_isBufferFull;
1432 }
1433
1434 inline void SearchBuffer::append(UChar c, bool isStart)
1435 {
1436     m_buffer[m_cursor] = c == noBreakSpace ? ' ' : c;
1437     m_isCharacterStartBuffer[m_cursor] = isStart;
1438     if (++m_cursor == m_target.length()) {
1439         m_cursor = 0;
1440         m_isBufferFull = true;
1441     }
1442 }
1443
1444 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1445 {
1446     ASSERT(length);
1447     if (m_isCaseSensitive) {
1448         append(characters[0], true);
1449         return 1;
1450     }
1451     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
1452     UChar foldedCharacters[maxFoldedCharacters];
1453     bool error;
1454     int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, characters, 1, &error);
1455     ASSERT(!error);
1456     ASSERT(numFoldedCharacters);
1457     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
1458     if (!error && numFoldedCharacters) {
1459         numFoldedCharacters = min(numFoldedCharacters, maxFoldedCharacters);
1460         append(foldedCharacters[0], true);
1461         for (int i = 1; i < numFoldedCharacters; ++i)
1462             append(foldedCharacters[i], false);
1463     }
1464     return 1;
1465 }
1466
1467 inline size_t SearchBuffer::search(size_t& start)
1468 {
1469     if (!m_isBufferFull)
1470         return 0;
1471     if (!m_isCharacterStartBuffer[m_cursor])
1472         return 0;
1473
1474     size_t tailSpace = m_target.length() - m_cursor;
1475     if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
1476         return 0;
1477     if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
1478         return 0;
1479
1480     start = length();
1481
1482     // Now that we've found a match once, we don't want to find it again, because those
1483     // are the SearchBuffer semantics, allowing for a buffer where you append more than one
1484     // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if
1485     // we want to get rid of that in the future we could track this with a separate boolean
1486     // or even move the characters to the start of the buffer and set m_isBufferFull to false.
1487     m_isCharacterStartBuffer[m_cursor] = false;
1488
1489     return start;
1490 }
1491
1492 // Returns the number of characters that were appended to the buffer (what we are searching in).
1493 // That's not necessarily the same length as the passed-in target string, because case folding
1494 // can make two strings match even though they're not the same length.
1495 size_t SearchBuffer::length() const
1496 {
1497     size_t bufferSize = m_target.length();
1498     size_t length = 0;
1499     for (size_t i = 0; i < bufferSize; ++i)
1500         length += m_isCharacterStartBuffer[i];
1501     return length;
1502 }
1503
1504 #endif // !ICU_UNICODE
1505
1506 // --------
1507
1508 int TextIterator::rangeLength(const Range *r, bool forSelectionPreservation)
1509 {
1510     int length = 0;
1511     for (TextIterator it(r, forSelectionPreservation); !it.atEnd(); it.advance())
1512         length += it.length();
1513     
1514     return length;
1515 }
1516
1517 PassRefPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
1518 {
1519     CharacterIterator entireRangeIterator(entireRange);
1520     return characterSubrange(entireRangeIterator, characterOffset, characterCount);
1521 }
1522
1523 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
1524 {
1525     RefPtr<Range> resultRange = scope->document()->createRange();
1526
1527     int docTextPosition = 0;
1528     int rangeEnd = rangeLocation + rangeLength;
1529     bool startRangeFound = false;
1530
1531     RefPtr<Range> textRunRange;
1532
1533     TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation);
1534     
1535     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
1536     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
1537         textRunRange = it.range();
1538         
1539         ExceptionCode ec = 0;
1540         resultRange->setStart(textRunRange->startContainer(), 0, ec);
1541         ASSERT(!ec);
1542         resultRange->setEnd(textRunRange->startContainer(), 0, ec);
1543         ASSERT(!ec);
1544         
1545         return resultRange.release();
1546     }
1547
1548     for (; !it.atEnd(); it.advance()) {
1549         int len = it.length();
1550         textRunRange = it.range();
1551         
1552         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len;
1553         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len;
1554         
1555         // Fix textRunRange->endPosition(), but only if foundStart || foundEnd, because it is only
1556         // in those cases that textRunRange is used.
1557         if (foundStart || foundEnd) {
1558             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
1559             // position for emitted '\n's.
1560             if (len == 1 && it.characters()[0] == '\n') {
1561                 Position runStart = textRunRange->startPosition();
1562                 Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
1563                 if (runEnd.isNotNull()) {
1564                     ExceptionCode ec = 0;
1565                     textRunRange->setEnd(runEnd.node(), runEnd.deprecatedEditingOffset(), ec);
1566                     ASSERT(!ec);
1567                 }
1568             }
1569         }
1570
1571         if (foundStart) {
1572             startRangeFound = true;
1573             int exception = 0;
1574             if (textRunRange->startContainer()->isTextNode()) {
1575                 int offset = rangeLocation - docTextPosition;
1576                 resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1577             } else {
1578                 if (rangeLocation == docTextPosition)
1579                     resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1580                 else
1581                     resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1582             }
1583         }
1584
1585         if (foundEnd) {
1586             int exception = 0;
1587             if (textRunRange->startContainer()->isTextNode()) {
1588                 int offset = rangeEnd - docTextPosition;
1589                 resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1590             } else {
1591                 if (rangeEnd == docTextPosition)
1592                     resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1593                 else
1594                     resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1595             }
1596             docTextPosition += len;
1597             break;
1598         }
1599         docTextPosition += len;
1600     }
1601     
1602     if (!startRangeFound)
1603         return 0;
1604     
1605     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1606         int exception = 0;
1607         resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1608     }
1609     
1610     return resultRange.release();
1611 }
1612
1613 // --------
1614     
1615 UChar* plainTextToMallocAllocatedBuffer(const Range* r, unsigned& bufferLength, bool isDisplayString) 
1616 {
1617     UChar* result = 0;
1618
1619     // Do this in pieces to avoid massive reallocations if there is a large amount of text.
1620     // Use system malloc for buffers since they can consume lots of memory and current TCMalloc is unable return it back to OS.
1621     static const unsigned cMaxSegmentSize = 1 << 16;
1622     bufferLength = 0;
1623     typedef pair<UChar*, unsigned> TextSegment;
1624     Vector<TextSegment>* textSegments = 0;
1625     Vector<UChar> textBuffer;
1626     textBuffer.reserveInitialCapacity(cMaxSegmentSize);
1627     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1628         if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) {
1629             UChar* newSegmentBuffer = static_cast<UChar*>(malloc(textBuffer.size() * sizeof(UChar)));
1630             if (!newSegmentBuffer)
1631                 goto exit;
1632             memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1633             if (!textSegments)
1634                 textSegments = new Vector<TextSegment>;
1635             textSegments->append(make_pair(newSegmentBuffer, (unsigned)textBuffer.size()));
1636             textBuffer.clear();
1637         }
1638         textBuffer.append(it.characters(), it.length());
1639         bufferLength += it.length();
1640     }
1641
1642     if (!bufferLength)
1643         return 0;
1644
1645     // Since we know the size now, we can make a single buffer out of the pieces with one big alloc
1646     result = static_cast<UChar*>(malloc(bufferLength * sizeof(UChar)));
1647     if (!result)
1648         goto exit;
1649
1650     {
1651         UChar* resultPos = result;
1652         if (textSegments) {
1653             unsigned size = textSegments->size();
1654             for (unsigned i = 0; i < size; ++i) {
1655                 const TextSegment& segment = textSegments->at(i);
1656                 memcpy(resultPos, segment.first, segment.second * sizeof(UChar));
1657                 resultPos += segment.second;
1658             }
1659         }
1660         memcpy(resultPos, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1661     }
1662
1663 exit:
1664     if (textSegments) {
1665         unsigned size = textSegments->size();
1666         for (unsigned i = 0; i < size; ++i)
1667             free(textSegments->at(i).first);
1668         delete textSegments;
1669     }
1670     
1671     if (isDisplayString && r->ownerDocument())
1672         r->ownerDocument()->displayBufferModifiedByEncoding(result, bufferLength);
1673
1674     return result;
1675 }
1676
1677 String plainText(const Range* r)
1678 {
1679     unsigned length;
1680     UChar* buf = plainTextToMallocAllocatedBuffer(r, length, false);
1681     if (!buf)
1682         return "";
1683     String result(buf, length);
1684     free(buf);
1685     return result;
1686 }
1687
1688 static inline bool isAllCollapsibleWhitespace(const String& string)
1689 {
1690     const UChar* characters = string.characters();
1691     unsigned length = string.length();
1692     for (unsigned i = 0; i < length; ++i) {
1693         if (!isCollapsibleWhitespace(characters[i]))
1694             return false;
1695     }
1696     return true;
1697 }
1698
1699 static PassRefPtr<Range> collapsedToBoundary(const Range* range, bool forward)
1700 {
1701     ExceptionCode ec = 0;
1702     RefPtr<Range> result = range->cloneRange(ec);
1703     ASSERT(!ec);
1704     result->collapse(!forward, ec);
1705     ASSERT(!ec);
1706     return result.release();
1707 }
1708
1709 static size_t findPlainText(CharacterIterator& it, const String& target, bool forward, bool caseSensitive, size_t& matchStart)
1710 {
1711     matchStart = 0;
1712     size_t matchLength = 0;
1713
1714     SearchBuffer buffer(target, caseSensitive);
1715
1716     while (!it.atEnd()) {
1717         it.advance(buffer.append(it.characters(), it.length()));
1718 tryAgain:
1719         size_t matchStartOffset;
1720         if (size_t newMatchLength = buffer.search(matchStartOffset)) {
1721             // Note that we found a match, and where we found it.
1722             size_t lastCharacterInBufferOffset = it.characterOffset();
1723             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
1724             matchStart = lastCharacterInBufferOffset - matchStartOffset;
1725             matchLength = newMatchLength;
1726             // If searching forward, stop on the first match.
1727             // If searching backward, don't stop, so we end up with the last match.
1728             if (forward)
1729                 break;
1730             goto tryAgain;
1731         }
1732         if (it.atBreak() && !buffer.atBreak()) {
1733             buffer.reachedBreak();
1734             goto tryAgain;
1735         }
1736     }
1737
1738     return matchLength;
1739 }
1740
1741 PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
1742 {
1743     // We can't search effectively for a string that's entirely made of collapsible
1744     // whitespace, so we won't even try. This also takes care of the empty string case.
1745     if (isAllCollapsibleWhitespace(target))
1746         return collapsedToBoundary(range, forward);
1747
1748     // First, find the text.
1749     size_t matchStart;
1750     size_t matchLength;
1751     {
1752         CharacterIterator findIterator(range, false, true);
1753         matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart);
1754         if (!matchLength)
1755             return collapsedToBoundary(range, forward);
1756     }
1757
1758     // Then, find the document position of the start and the end of the text.
1759     CharacterIterator computeRangeIterator(range, false, true);
1760     return characterSubrange(computeRangeIterator, matchStart, matchLength);
1761 }
1762
1763 }