WebCore:
[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 startPos.isNotNull() check is needed because the start could be before the body,
617     // and in that case we'll get null. We don't want to put in newlines at the start in that case.
618     // The currPos.isNotNull() check is needed because positions in non-HTML content
619     // (like SVG) do not have visible positions, and we don't want to emit for them either.
620     VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM);
621     VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM);
622     return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos);
623 }
624
625 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)
626 {
627     return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitCharactersBetweenAllVisiblePositions);
628 }
629
630 void TextIterator::representNodeOffsetZero()
631 {
632     // Emit a character to show the positioning of m_node.
633     
634     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 
635     // create VisiblePositions, which is expensive.  So, we perform the inexpensive checks
636     // on m_node to see if it necessitates emitting a character first and will early return 
637     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
638     if (shouldEmitTabBeforeNode(m_node)) {
639         if (shouldRepresentNodeOffsetZero())
640             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);
641     } else if (shouldEmitNewlineBeforeNode(m_node)) {
642         if (shouldRepresentNodeOffsetZero())
643             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);
644     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {
645         if (shouldRepresentNodeOffsetZero())
646             emitCharacter(' ', m_node->parentNode(), m_node, 0, 0);
647     }
648 }
649
650 bool TextIterator::handleNonTextNode()
651 {
652     if (shouldEmitNewlineForNode(m_node))
653         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
654     else if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())
655         emitCharacter(' ', m_node->parentNode(), m_node, 0, 1);
656     else
657         representNodeOffsetZero();
658
659     return true;
660 }
661
662 void TextIterator::exitNode()
663 {
664     // prevent emitting a newline when exiting a collapsed block at beginning of the range
665     // FIXME: !m_haveEmitted does not necessarily mean there was a collapsed block... it could
666     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
667     // therefore look like a blank line.
668     if (!m_haveEmitted)
669         return;
670         
671     // Emit with a position *inside* m_node, after m_node's contents, in 
672     // case it is a block, because the run should start where the 
673     // emitted character is positioned visually.
674     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
675     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
676     // the logic in _web_attributedStringFromRange match.  We'll get that for free when we switch to use
677     // TextIterator in _web_attributedStringFromRange.
678     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
679     if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {
680         // use extra newline to represent margin bottom, as needed
681         bool addNewline = shouldEmitExtraNewlineForNode(m_node);
682         
683         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
684         // contain a VisiblePosition when doing selection preservation.
685         if (m_lastCharacter != '\n') {
686             // insert a newline with a position following this block's contents.
687             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
688             // remember whether to later add a newline for the current node
689             ASSERT(!m_needAnotherNewline);
690             m_needAnotherNewline = addNewline;
691         } else if (addNewline)
692             // insert a newline with a position following this block's contents.
693             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
694     }
695     
696     // If nothing was emitted, see if we need to emit a space.
697     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))
698         emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1);
699 }
700
701 void TextIterator::emitCharacter(UChar c, Node *textNode, Node *offsetBaseNode, int textStartOffset, int textEndOffset)
702 {
703     m_haveEmitted = true;
704     
705     // remember information with which to construct the TextIterator::range()
706     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
707     m_positionNode = textNode;
708     m_positionOffsetBaseNode = offsetBaseNode;
709     m_positionStartOffset = textStartOffset;
710     m_positionEndOffset = textEndOffset;
711  
712     // remember information with which to construct the TextIterator::characters() and length()
713     m_singleCharacterBuffer = c;
714     m_textCharacters = &m_singleCharacterBuffer;
715     m_textLength = 1;
716
717     // remember some iteration state
718     m_lastTextNodeEndedWithCollapsedSpace = false;
719     m_lastCharacter = c;
720 }
721
722 void TextIterator::emitText(Node* textNode, int textStartOffset, int textEndOffset)
723 {
724     RenderText* renderer = toRenderText(m_node->renderer());
725     String str = renderer->text();
726     ASSERT(str.characters());
727
728     m_positionNode = textNode;
729     m_positionOffsetBaseNode = 0;
730     m_positionStartOffset = textStartOffset;
731     m_positionEndOffset = textEndOffset;
732     m_textCharacters = str.characters() + textStartOffset;
733     m_textLength = textEndOffset - textStartOffset;
734     m_lastCharacter = str[textEndOffset - 1];
735
736     m_lastTextNodeEndedWithCollapsedSpace = false;
737     m_haveEmitted = true;
738 }
739
740 PassRefPtr<Range> TextIterator::range() const
741 {
742     // use the current run information, if we have it
743     if (m_positionNode) {
744         if (m_positionOffsetBaseNode) {
745             int index = m_positionOffsetBaseNode->nodeIndex();
746             m_positionStartOffset += index;
747             m_positionEndOffset += index;
748             m_positionOffsetBaseNode = 0;
749         }
750         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
751     }
752
753     // otherwise, return the end of the overall range we were given
754     if (m_endContainer)
755         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
756         
757     return 0;
758 }
759     
760 Node* TextIterator::node() const
761 {
762     RefPtr<Range> textRange = range();
763     if (!textRange)
764         return 0;
765
766     Node* node = textRange->startContainer();
767     if (!node)
768         return 0;
769     if (node->offsetInCharacters())
770         return node;
771     
772     return node->childNode(textRange->startOffset());
773 }
774
775 // --------
776
777 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
778 {
779 }
780
781 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range *r)
782 {
783     m_positionNode = 0;
784
785     if (!r)
786         return;
787
788     Node* startNode = r->startContainer();
789     if (!startNode)
790         return;
791     Node* endNode = r->endContainer();
792     int startOffset = r->startOffset();
793     int endOffset = r->endOffset();
794
795     if (!startNode->offsetInCharacters()) {
796         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
797             startNode = startNode->childNode(startOffset);
798             startOffset = 0;
799         }
800     }
801     if (!endNode->offsetInCharacters()) {
802         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {
803             endNode = endNode->childNode(endOffset - 1);
804             endOffset = endNode->offsetInCharacters() ? endNode->maxCharacterOffset() : endNode->childNodeCount();
805         }
806     }
807
808     m_node = endNode;
809     m_offset = endOffset;
810     m_handledNode = false;
811     m_handledChildren = endOffset == 0;
812
813     m_startNode = startNode;
814     m_startOffset = startOffset;
815     m_endNode = endNode;
816     m_endOffset = endOffset;
817     
818 #ifndef NDEBUG
819     // Need this just because of the assert.
820     m_positionNode = endNode;
821 #endif
822
823     m_lastTextNode = 0;
824     m_lastCharacter = '\n';
825     
826     if (startOffset == 0 || !startNode->firstChild()) {
827         m_pastStartNode = startNode->previousSibling();
828         while (!m_pastStartNode && startNode->parentNode()) {
829             startNode = startNode->parentNode();
830             m_pastStartNode = startNode->previousSibling();
831         }
832     } else
833         m_pastStartNode = startNode->childNode(startOffset - 1);
834
835     advance();
836 }
837
838 void SimplifiedBackwardsTextIterator::advance()
839 {
840     ASSERT(m_positionNode);
841
842     m_positionNode = 0;
843     m_textLength = 0;
844
845     while (m_node && m_node != m_pastStartNode) {
846         // Don't handle node if we start iterating at [node, 0].
847         if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) {
848             RenderObject *renderer = m_node->renderer();
849             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
850                 // FIXME: What about CDATA_SECTION_NODE?
851                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
852                     m_handledNode = handleTextNode();
853             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
854                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
855                     m_handledNode = handleReplacedElement();
856             } else
857                 m_handledNode = handleNonTextNode();
858             if (m_positionNode)
859                 return;
860         }
861
862         Node* next = m_handledChildren ? 0 : m_node->lastChild();
863         if (!next) {
864             // Exit empty containers as we pass over them or containers
865             // where [container, 0] is where we started iterating.
866             if (!m_handledNode &&
867                 canHaveChildrenForEditing(m_node) && 
868                 m_node->parentNode() && 
869                 (!m_node->lastChild() || (m_node == m_endNode && m_endOffset == 0))) {
870                 exitNode();
871                 if (m_positionNode) {
872                     m_handledNode = true;
873                     m_handledChildren = true;
874                     return;
875                 }            
876             }
877             // Exit all other containers.
878             next = m_node->previousSibling();
879             while (!next) {
880                 if (!m_node->parentNode())
881                     break;
882                 m_node = m_node->parentNode();
883                 exitNode();
884                 if (m_positionNode) {
885                     m_handledNode = true;
886                     m_handledChildren = true;
887                     return;
888                 }
889                 next = m_node->previousSibling();
890             }
891         }
892         
893         m_node = next;
894         m_offset = m_node ? caretMaxOffset(m_node) : 0;
895         m_handledNode = false;
896         m_handledChildren = false;
897         
898         if (m_positionNode)
899             return;
900     }
901 }
902
903 bool SimplifiedBackwardsTextIterator::handleTextNode()
904 {
905     m_lastTextNode = m_node;
906
907     RenderText *renderer = toRenderText(m_node->renderer());
908     String str = renderer->text();
909
910     if (!renderer->firstTextBox() && str.length() > 0)
911         return true;
912
913     m_positionEndOffset = m_offset;
914
915     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
916     m_positionNode = m_node;
917     m_positionStartOffset = m_offset;
918     m_textLength = m_positionEndOffset - m_positionStartOffset;
919     m_textCharacters = str.characters() + m_positionStartOffset;
920
921     m_lastCharacter = str[m_positionEndOffset - 1];
922
923     return true;
924 }
925
926 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
927 {
928     unsigned index = m_node->nodeIndex();
929     // We want replaced elements to behave like punctuation for boundary 
930     // finding, and to simply take up space for the selection preservation 
931     // code in moveParagraphs, so we use a comma.  Unconditionally emit
932     // here because this iterator is only used for boundary finding.
933     emitCharacter(',', m_node->parentNode(), index, index + 1);
934     return true;
935 }
936
937 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
938 {    
939     // We can use a linefeed in place of a tab because this simple iterator is only used to
940     // find boundaries, not actual content.  A linefeed breaks words, sentences, and paragraphs.
941     if (shouldEmitNewlineForNode(m_node) ||
942         shouldEmitNewlineAfterNode(m_node) ||
943         shouldEmitTabBeforeNode(m_node)) {
944         unsigned index = m_node->nodeIndex();
945         // The start of this emitted range is wrong, ensuring correctness would require
946         // VisiblePositions and so would be slow.  previousBoundary expects this.
947         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
948     }
949     
950     return true;
951 }
952
953 void SimplifiedBackwardsTextIterator::exitNode()
954 {
955     if (shouldEmitNewlineForNode(m_node) ||
956         shouldEmitNewlineBeforeNode(m_node) ||
957         shouldEmitTabBeforeNode(m_node))
958         // The start of this emitted range is wrong, ensuring correctness would require
959         // VisiblePositions and so would be slow.  previousBoundary expects this.
960         emitCharacter('\n', m_node, 0, 0);
961 }
962
963 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node *node, int startOffset, int endOffset)
964 {
965     m_singleCharacterBuffer = c;
966     m_positionNode = node;
967     m_positionStartOffset = startOffset;
968     m_positionEndOffset = endOffset;
969     m_textCharacters = &m_singleCharacterBuffer;
970     m_textLength = 1;
971     m_lastCharacter = c;
972 }
973
974 PassRefPtr<Range> SimplifiedBackwardsTextIterator::range() const
975 {
976     if (m_positionNode)
977         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
978     
979     return Range::create(m_startNode->document(), m_startNode, m_startOffset, m_startNode, m_startOffset);
980 }
981
982 // --------
983
984 CharacterIterator::CharacterIterator()
985     : m_offset(0)
986     , m_runOffset(0)
987     , m_atBreak(true)
988 {
989 }
990
991 CharacterIterator::CharacterIterator(const Range *r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls)
992     : m_offset(0)
993     , m_runOffset(0)
994     , m_atBreak(true)
995     , m_textIterator(r, emitCharactersBetweenAllVisiblePositions, enterTextControls)
996 {
997     while (!atEnd() && m_textIterator.length() == 0)
998         m_textIterator.advance();
999 }
1000
1001 PassRefPtr<Range> CharacterIterator::range() const
1002 {
1003     RefPtr<Range> r = m_textIterator.range();
1004     if (!m_textIterator.atEnd()) {
1005         if (m_textIterator.length() <= 1) {
1006             ASSERT(m_runOffset == 0);
1007         } else {
1008             Node* n = r->startContainer();
1009             ASSERT(n == r->endContainer());
1010             int offset = r->startOffset() + m_runOffset;
1011             ExceptionCode ec = 0;
1012             r->setStart(n, offset, ec);
1013             r->setEnd(n, offset + 1, ec);
1014             ASSERT(!ec);
1015         }
1016     }
1017     return r.release();
1018 }
1019
1020 void CharacterIterator::advance(int count)
1021 {
1022     if (count <= 0) {
1023         ASSERT(count == 0);
1024         return;
1025     }
1026     
1027     m_atBreak = false;
1028
1029     // easy if there is enough left in the current m_textIterator run
1030     int remaining = m_textIterator.length() - m_runOffset;
1031     if (count < remaining) {
1032         m_runOffset += count;
1033         m_offset += count;
1034         return;
1035     }
1036
1037     // exhaust the current m_textIterator run
1038     count -= remaining;
1039     m_offset += remaining;
1040     
1041     // move to a subsequent m_textIterator run
1042     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1043         int runLength = m_textIterator.length();
1044         if (runLength == 0)
1045             m_atBreak = true;
1046         else {
1047             // see whether this is m_textIterator to use
1048             if (count < runLength) {
1049                 m_runOffset = count;
1050                 m_offset += count;
1051                 return;
1052             }
1053             
1054             // exhaust this m_textIterator run
1055             count -= runLength;
1056             m_offset += runLength;
1057         }
1058     }
1059
1060     // ran to the end of the m_textIterator... no more runs left
1061     m_atBreak = true;
1062     m_runOffset = 0;
1063 }
1064
1065 String CharacterIterator::string(int numChars)
1066 {
1067     Vector<UChar> result;
1068     result.reserveInitialCapacity(numChars);
1069     while (numChars > 0 && !atEnd()) {
1070         int runSize = min(numChars, length());
1071         result.append(characters(), runSize);
1072         numChars -= runSize;
1073         advance(runSize);
1074     }
1075     return String::adopt(result);
1076 }
1077
1078 static PassRefPtr<Range> characterSubrange(CharacterIterator& it, int offset, int length)
1079 {
1080     it.advance(offset);
1081     RefPtr<Range> start = it.range();
1082
1083     if (length > 1)
1084         it.advance(length - 1);
1085     RefPtr<Range> end = it.range();
1086
1087     return Range::create(start->startContainer()->document(), 
1088         start->startContainer(), start->startOffset(), 
1089         end->endContainer(), end->endOffset());
1090 }
1091
1092 BackwardsCharacterIterator::BackwardsCharacterIterator()
1093     : m_offset(0)
1094     , m_runOffset(0)
1095     , m_atBreak(true)
1096 {
1097 }
1098
1099 BackwardsCharacterIterator::BackwardsCharacterIterator(const Range* range)
1100     : m_offset(0)
1101     , m_runOffset(0)
1102     , m_atBreak(true)
1103     , m_textIterator(range)
1104 {
1105     while (!atEnd() && !m_textIterator.length())
1106         m_textIterator.advance();
1107 }
1108
1109 PassRefPtr<Range> BackwardsCharacterIterator::range() const
1110 {
1111     RefPtr<Range> r = m_textIterator.range();
1112     if (!m_textIterator.atEnd()) {
1113         if (m_textIterator.length() <= 1)
1114             ASSERT(m_runOffset == 0);
1115         else {
1116             Node* n = r->startContainer();
1117             ASSERT(n == r->endContainer());
1118             int offset = r->endOffset() - m_runOffset;
1119             ExceptionCode ec = 0;
1120             r->setStart(n, offset - 1, ec);
1121             r->setEnd(n, offset, ec);
1122             ASSERT(!ec);
1123         }
1124     }
1125     return r.release();
1126 }
1127
1128 void BackwardsCharacterIterator::advance(int count)
1129 {
1130     if (count <= 0) {
1131         ASSERT(!count);
1132         return;
1133     }
1134
1135     m_atBreak = false;
1136
1137     int remaining = m_textIterator.length() - m_runOffset;
1138     if (count < remaining) {
1139         m_runOffset += count;
1140         m_offset += count;
1141         return;
1142     }
1143
1144     count -= remaining;
1145     m_offset += remaining;
1146
1147     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1148         int runLength = m_textIterator.length();
1149         if (runLength == 0)
1150             m_atBreak = true;
1151         else {
1152             if (count < runLength) {
1153                 m_runOffset = count;
1154                 m_offset += count;
1155                 return;
1156             }
1157             
1158             count -= runLength;
1159             m_offset += runLength;
1160         }
1161     }
1162
1163     m_atBreak = true;
1164     m_runOffset = 0;
1165 }
1166
1167 // --------
1168
1169 WordAwareIterator::WordAwareIterator()
1170 : m_previousText(0), m_didLookAhead(false)
1171 {
1172 }
1173
1174 WordAwareIterator::WordAwareIterator(const Range *r)
1175 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
1176 {
1177     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
1178     advance();              // get in position over the first chunk of text
1179 }
1180
1181 // We're always in one of these modes:
1182 // - The current chunk in the text iterator is our current chunk
1183 //      (typically its a piece of whitespace, or text that ended with whitespace)
1184 // - The previous chunk in the text iterator is our current chunk
1185 //      (we looked ahead to the next chunk and found a word boundary)
1186 // - We built up our own chunk of text from many chunks from the text iterator
1187
1188 // FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
1189
1190 void WordAwareIterator::advance()
1191 {
1192     m_previousText = 0;
1193     m_buffer.clear();      // toss any old buffer we built up
1194
1195     // If last time we did a look-ahead, start with that looked-ahead chunk now
1196     if (!m_didLookAhead) {
1197         ASSERT(!m_textIterator.atEnd());
1198         m_textIterator.advance();
1199     }
1200     m_didLookAhead = false;
1201
1202     // Go to next non-empty chunk 
1203     while (!m_textIterator.atEnd() && m_textIterator.length() == 0)
1204         m_textIterator.advance();
1205     m_range = m_textIterator.range();
1206
1207     if (m_textIterator.atEnd())
1208         return;
1209     
1210     while (1) {
1211         // If this chunk ends in whitespace we can just use it as our chunk.
1212         if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1]))
1213             return;
1214
1215         // If this is the first chunk that failed, save it in previousText before look ahead
1216         if (m_buffer.isEmpty()) {
1217             m_previousText = m_textIterator.characters();
1218             m_previousLength = m_textIterator.length();
1219         }
1220
1221         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
1222         m_textIterator.advance();
1223         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) {
1224             m_didLookAhead = true;
1225             return;
1226         }
1227
1228         if (m_buffer.isEmpty()) {
1229             // Start gobbling chunks until we get to a suitable stopping point
1230             m_buffer.append(m_previousText, m_previousLength);
1231             m_previousText = 0;
1232         }
1233         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
1234         int exception = 0;
1235         m_range->setEnd(m_textIterator.range()->endContainer(), m_textIterator.range()->endOffset(), exception);
1236     }
1237 }
1238
1239 int WordAwareIterator::length() const
1240 {
1241     if (!m_buffer.isEmpty())
1242         return m_buffer.size();
1243     if (m_previousText)
1244         return m_previousLength;
1245     return m_textIterator.length();
1246 }
1247
1248 const UChar* WordAwareIterator::characters() const
1249 {
1250     if (!m_buffer.isEmpty())
1251         return m_buffer.data();
1252     if (m_previousText)
1253         return m_previousText;
1254     return m_textIterator.characters();
1255 }
1256
1257 // --------
1258
1259 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
1260
1261 static const size_t minimumSearchBufferSize = 8192;
1262
1263 #ifndef NDEBUG
1264 static bool searcherInUse;
1265 #endif
1266
1267 static UStringSearch* createSearcher()
1268 {
1269     // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
1270     // but it doesn't matter exactly what it is, since we don't perform any searches
1271     // without setting both the pattern and the text.
1272
1273     // Pass empty string for the locale for now to get the Unicode Collation Algorithm,
1274     // rather than something locale-specific.
1275
1276     UErrorCode status = U_ZERO_ERROR;
1277     UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, "", 0, &status);
1278     ASSERT(status == U_ZERO_ERROR);
1279     return searcher;
1280 }
1281
1282 static UStringSearch* searcher()
1283 {
1284     static UStringSearch* searcher = createSearcher();
1285     return searcher;
1286 }
1287
1288 static inline void lockSearcher()
1289 {
1290 #ifndef NDEBUG
1291     ASSERT(!searcherInUse);
1292     searcherInUse = true;
1293 #endif
1294 }
1295
1296 static inline void unlockSearcher()
1297 {
1298 #ifndef NDEBUG
1299     ASSERT(searcherInUse);
1300     searcherInUse = false;
1301 #endif
1302 }
1303
1304 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1305     : m_target(target)
1306     , m_atBreak(true)
1307 {
1308     ASSERT(!m_target.isEmpty());
1309
1310     size_t targetLength = target.length();
1311     m_buffer.reserveInitialCapacity(max(targetLength * 8, minimumSearchBufferSize));
1312     m_overlap = m_buffer.capacity() / 4;
1313
1314     // Grab the single global searcher.
1315     // If we ever have a reason to do more than once search buffer at once, we'll have
1316     // to move to multiple searchers.
1317     lockSearcher();
1318
1319     UStringSearch* searcher = WebCore::searcher();
1320     UCollator* collator = usearch_getCollator(searcher);
1321
1322     UCollationStrength strength = isCaseSensitive ? UCOL_TERTIARY : UCOL_PRIMARY;
1323     if (ucol_getStrength(collator) != strength) {
1324         ucol_setStrength(collator, strength);
1325         usearch_reset(searcher);
1326     }
1327
1328     UErrorCode status = U_ZERO_ERROR;
1329     usearch_setPattern(searcher, m_target.characters(), targetLength, &status);
1330     ASSERT(status == U_ZERO_ERROR);
1331 }
1332
1333 inline SearchBuffer::~SearchBuffer()
1334 {
1335     unlockSearcher();
1336 }
1337
1338 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1339 {
1340     ASSERT(length);
1341
1342     if (m_atBreak) {
1343         m_buffer.shrink(0);
1344         m_atBreak = false;
1345     } else if (m_buffer.size() == m_buffer.capacity()) {
1346         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
1347         m_buffer.shrink(m_overlap);
1348     }
1349
1350     size_t usableLength = min(m_buffer.capacity() - m_buffer.size(), length);
1351     ASSERT(usableLength);
1352     m_buffer.append(characters, usableLength);
1353     return usableLength;
1354 }
1355
1356 inline bool SearchBuffer::atBreak() const
1357 {
1358     return m_atBreak;
1359 }
1360
1361 inline void SearchBuffer::reachedBreak()
1362 {
1363     m_atBreak = true;
1364 }
1365
1366 inline size_t SearchBuffer::search(size_t& start)
1367 {
1368     size_t size = m_buffer.size();
1369     if (m_atBreak) {
1370         if (!size)
1371             return 0;
1372     } else {
1373         if (size != m_buffer.capacity())
1374             return 0;
1375     }
1376
1377     UStringSearch* searcher = WebCore::searcher();
1378
1379     UErrorCode status = U_ZERO_ERROR;
1380     usearch_setText(searcher, m_buffer.data(), size, &status);
1381     ASSERT(status == U_ZERO_ERROR);
1382
1383     int matchStart = usearch_first(searcher, &status);
1384     ASSERT(status == U_ZERO_ERROR);
1385     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
1386         ASSERT(matchStart == USEARCH_DONE);
1387         return 0;
1388     }
1389
1390     // Matches that start in the overlap area are only tentative.
1391     // The same match may appear later, matching more characters,
1392     // possibly including a combining character that's not yet in the buffer.
1393     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
1394         memcpy(m_buffer.data(), m_buffer.data() + size - m_overlap, m_overlap * sizeof(UChar));
1395         m_buffer.shrink(m_overlap);
1396         return 0;
1397     }
1398
1399     size_t newSize = size - (matchStart + 1);
1400     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
1401     m_buffer.shrink(newSize);
1402
1403     start = size - matchStart;
1404     return usearch_getMatchedLength(searcher);
1405 }
1406
1407 #else // !ICU_UNICODE
1408
1409 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1410     : m_target(isCaseSensitive ? target : target.foldCase())
1411     , m_isCaseSensitive(isCaseSensitive)
1412     , m_buffer(m_target.length())
1413     , m_isCharacterStartBuffer(m_target.length())
1414     , m_isBufferFull(false)
1415     , m_cursor(0)
1416 {
1417     ASSERT(!m_target.isEmpty());
1418     m_target.replace(noBreakSpace, ' ');
1419 }
1420
1421 inline SearchBuffer::~SearchBuffer()
1422 {
1423 }
1424
1425 inline void SearchBuffer::reachedBreak()
1426 {
1427     m_cursor = 0;
1428     m_isBufferFull = false;
1429 }
1430
1431 inline bool SearchBuffer::atBreak() const
1432 {
1433     return !m_cursor && !m_isBufferFull;
1434 }
1435
1436 inline void SearchBuffer::append(UChar c, bool isStart)
1437 {
1438     m_buffer[m_cursor] = c == noBreakSpace ? ' ' : c;
1439     m_isCharacterStartBuffer[m_cursor] = isStart;
1440     if (++m_cursor == m_target.length()) {
1441         m_cursor = 0;
1442         m_isBufferFull = true;
1443     }
1444 }
1445
1446 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1447 {
1448     ASSERT(length);
1449     if (m_isCaseSensitive) {
1450         append(characters[0], true);
1451         return 1;
1452     }
1453     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
1454     UChar foldedCharacters[maxFoldedCharacters];
1455     bool error;
1456     int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, characters, 1, &error);
1457     ASSERT(!error);
1458     ASSERT(numFoldedCharacters);
1459     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
1460     if (!error && numFoldedCharacters) {
1461         numFoldedCharacters = min(numFoldedCharacters, maxFoldedCharacters);
1462         append(foldedCharacters[0], true);
1463         for (int i = 1; i < numFoldedCharacters; ++i)
1464             append(foldedCharacters[i], false);
1465     }
1466     return 1;
1467 }
1468
1469 inline size_t SearchBuffer::search(size_t& start)
1470 {
1471     if (!m_isBufferFull)
1472         return 0;
1473     if (!m_isCharacterStartBuffer[m_cursor])
1474         return 0;
1475
1476     size_t tailSpace = m_target.length() - m_cursor;
1477     if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
1478         return 0;
1479     if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
1480         return 0;
1481
1482     start = length();
1483
1484     // Now that we've found a match once, we don't want to find it again, because those
1485     // are the SearchBuffer semantics, allowing for a buffer where you append more than one
1486     // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if
1487     // we want to get rid of that in the future we could track this with a separate boolean
1488     // or even move the characters to the start of the buffer and set m_isBufferFull to false.
1489     m_isCharacterStartBuffer[m_cursor] = false;
1490
1491     return start;
1492 }
1493
1494 // Returns the number of characters that were appended to the buffer (what we are searching in).
1495 // That's not necessarily the same length as the passed-in target string, because case folding
1496 // can make two strings match even though they're not the same length.
1497 size_t SearchBuffer::length() const
1498 {
1499     size_t bufferSize = m_target.length();
1500     size_t length = 0;
1501     for (size_t i = 0; i < bufferSize; ++i)
1502         length += m_isCharacterStartBuffer[i];
1503     return length;
1504 }
1505
1506 #endif // !ICU_UNICODE
1507
1508 // --------
1509
1510 int TextIterator::rangeLength(const Range *r, bool forSelectionPreservation)
1511 {
1512     int length = 0;
1513     for (TextIterator it(r, forSelectionPreservation); !it.atEnd(); it.advance())
1514         length += it.length();
1515     
1516     return length;
1517 }
1518
1519 PassRefPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
1520 {
1521     CharacterIterator entireRangeIterator(entireRange);
1522     return characterSubrange(entireRangeIterator, characterOffset, characterCount);
1523 }
1524
1525 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
1526 {
1527     RefPtr<Range> resultRange = scope->document()->createRange();
1528
1529     int docTextPosition = 0;
1530     int rangeEnd = rangeLocation + rangeLength;
1531     bool startRangeFound = false;
1532
1533     RefPtr<Range> textRunRange;
1534
1535     TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation);
1536     
1537     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
1538     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
1539         textRunRange = it.range();
1540         
1541         ExceptionCode ec = 0;
1542         resultRange->setStart(textRunRange->startContainer(), 0, ec);
1543         ASSERT(!ec);
1544         resultRange->setEnd(textRunRange->startContainer(), 0, ec);
1545         ASSERT(!ec);
1546         
1547         return resultRange.release();
1548     }
1549
1550     for (; !it.atEnd(); it.advance()) {
1551         int len = it.length();
1552         textRunRange = it.range();
1553         
1554         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len;
1555         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len;
1556         
1557         // Fix textRunRange->endPosition(), but only if foundStart || foundEnd, because it is only
1558         // in those cases that textRunRange is used.
1559         if (foundStart || foundEnd) {
1560             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
1561             // position for emitted '\n's.
1562             if (len == 1 && it.characters()[0] == '\n') {
1563                 Position runStart = textRunRange->startPosition();
1564                 Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
1565                 if (runEnd.isNotNull()) {
1566                     ExceptionCode ec = 0;
1567                     textRunRange->setEnd(runEnd.node(), runEnd.deprecatedEditingOffset(), ec);
1568                     ASSERT(!ec);
1569                 }
1570             }
1571         }
1572
1573         if (foundStart) {
1574             startRangeFound = true;
1575             int exception = 0;
1576             if (textRunRange->startContainer()->isTextNode()) {
1577                 int offset = rangeLocation - docTextPosition;
1578                 resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1579             } else {
1580                 if (rangeLocation == docTextPosition)
1581                     resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1582                 else
1583                     resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1584             }
1585         }
1586
1587         if (foundEnd) {
1588             int exception = 0;
1589             if (textRunRange->startContainer()->isTextNode()) {
1590                 int offset = rangeEnd - docTextPosition;
1591                 resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1592             } else {
1593                 if (rangeEnd == docTextPosition)
1594                     resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1595                 else
1596                     resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1597             }
1598             docTextPosition += len;
1599             break;
1600         }
1601         docTextPosition += len;
1602     }
1603     
1604     if (!startRangeFound)
1605         return 0;
1606     
1607     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1608         int exception = 0;
1609         resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1610     }
1611     
1612     return resultRange.release();
1613 }
1614
1615 // --------
1616     
1617 UChar* plainTextToMallocAllocatedBuffer(const Range* r, unsigned& bufferLength, bool isDisplayString) 
1618 {
1619     UChar* result = 0;
1620
1621     // Do this in pieces to avoid massive reallocations if there is a large amount of text.
1622     // Use system malloc for buffers since they can consume lots of memory and current TCMalloc is unable return it back to OS.
1623     static const unsigned cMaxSegmentSize = 1 << 16;
1624     bufferLength = 0;
1625     typedef pair<UChar*, unsigned> TextSegment;
1626     Vector<TextSegment>* textSegments = 0;
1627     Vector<UChar> textBuffer;
1628     textBuffer.reserveInitialCapacity(cMaxSegmentSize);
1629     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1630         if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) {
1631             UChar* newSegmentBuffer = static_cast<UChar*>(malloc(textBuffer.size() * sizeof(UChar)));
1632             if (!newSegmentBuffer)
1633                 goto exit;
1634             memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1635             if (!textSegments)
1636                 textSegments = new Vector<TextSegment>;
1637             textSegments->append(make_pair(newSegmentBuffer, (unsigned)textBuffer.size()));
1638             textBuffer.clear();
1639         }
1640         textBuffer.append(it.characters(), it.length());
1641         bufferLength += it.length();
1642     }
1643
1644     if (!bufferLength)
1645         return 0;
1646
1647     // Since we know the size now, we can make a single buffer out of the pieces with one big alloc
1648     result = static_cast<UChar*>(malloc(bufferLength * sizeof(UChar)));
1649     if (!result)
1650         goto exit;
1651
1652     {
1653         UChar* resultPos = result;
1654         if (textSegments) {
1655             unsigned size = textSegments->size();
1656             for (unsigned i = 0; i < size; ++i) {
1657                 const TextSegment& segment = textSegments->at(i);
1658                 memcpy(resultPos, segment.first, segment.second * sizeof(UChar));
1659                 resultPos += segment.second;
1660             }
1661         }
1662         memcpy(resultPos, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1663     }
1664
1665 exit:
1666     if (textSegments) {
1667         unsigned size = textSegments->size();
1668         for (unsigned i = 0; i < size; ++i)
1669             free(textSegments->at(i).first);
1670         delete textSegments;
1671     }
1672     
1673     if (isDisplayString && r->ownerDocument())
1674         r->ownerDocument()->displayBufferModifiedByEncoding(result, bufferLength);
1675
1676     return result;
1677 }
1678
1679 String plainText(const Range* r)
1680 {
1681     unsigned length;
1682     UChar* buf = plainTextToMallocAllocatedBuffer(r, length, false);
1683     if (!buf)
1684         return "";
1685     String result(buf, length);
1686     free(buf);
1687     return result;
1688 }
1689
1690 static inline bool isAllCollapsibleWhitespace(const String& string)
1691 {
1692     const UChar* characters = string.characters();
1693     unsigned length = string.length();
1694     for (unsigned i = 0; i < length; ++i) {
1695         if (!isCollapsibleWhitespace(characters[i]))
1696             return false;
1697     }
1698     return true;
1699 }
1700
1701 static PassRefPtr<Range> collapsedToBoundary(const Range* range, bool forward)
1702 {
1703     ExceptionCode ec = 0;
1704     RefPtr<Range> result = range->cloneRange(ec);
1705     ASSERT(!ec);
1706     result->collapse(!forward, ec);
1707     ASSERT(!ec);
1708     return result.release();
1709 }
1710
1711 static size_t findPlainText(CharacterIterator& it, const String& target, bool forward, bool caseSensitive, size_t& matchStart)
1712 {
1713     matchStart = 0;
1714     size_t matchLength = 0;
1715
1716     SearchBuffer buffer(target, caseSensitive);
1717
1718     while (!it.atEnd()) {
1719         it.advance(buffer.append(it.characters(), it.length()));
1720 tryAgain:
1721         size_t matchStartOffset;
1722         if (size_t newMatchLength = buffer.search(matchStartOffset)) {
1723             // Note that we found a match, and where we found it.
1724             size_t lastCharacterInBufferOffset = it.characterOffset();
1725             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
1726             matchStart = lastCharacterInBufferOffset - matchStartOffset;
1727             matchLength = newMatchLength;
1728             // If searching forward, stop on the first match.
1729             // If searching backward, don't stop, so we end up with the last match.
1730             if (forward)
1731                 break;
1732             goto tryAgain;
1733         }
1734         if (it.atBreak() && !buffer.atBreak()) {
1735             buffer.reachedBreak();
1736             goto tryAgain;
1737         }
1738     }
1739
1740     return matchLength;
1741 }
1742
1743 PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
1744 {
1745     // We can't search effectively for a string that's entirely made of collapsible
1746     // whitespace, so we won't even try. This also takes care of the empty string case.
1747     if (isAllCollapsibleWhitespace(target))
1748         return collapsedToBoundary(range, forward);
1749
1750     // First, find the text.
1751     size_t matchStart;
1752     size_t matchLength;
1753     {
1754         CharacterIterator findIterator(range, false, true);
1755         matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart);
1756         if (!matchLength)
1757             return collapsedToBoundary(range, forward);
1758     }
1759
1760     // Then, find the document position of the start and the end of the text.
1761     CharacterIterator computeRangeIterator(range, false, true);
1762     return characterSubrange(computeRangeIterator, matchStart, matchLength);
1763 }
1764
1765 }