WebCore:
[WebKit-https.git] / WebCore / editing / TextIterator.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007 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 "Element.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 "visible_units.h"
41
42 using namespace std;
43 using namespace WTF::Unicode;
44
45 namespace WebCore {
46
47 using namespace HTMLNames;
48
49 // Buffer that knows how to compare with a search target.
50 // Keeps enough of the previous text to be able to search in the future, but no more.
51 class CircularSearchBuffer : Noncopyable {
52 public:
53     CircularSearchBuffer(const String& target, bool isCaseSensitive);
54
55     void clear() { m_cursor = 0; m_isBufferFull = false; }
56     void append(UChar);
57
58     bool isMatch() const;
59     unsigned length() const;
60
61 private:
62     void append(UChar, bool isCharacterStart);
63
64     String m_target;
65     bool m_isCaseSensitive;
66
67     Vector<UChar> m_characterBuffer;
68     Vector<bool> m_isCharacterStartBuffer;
69     bool m_isBufferFull;
70     unsigned m_cursor;
71 };
72
73 // --------
74
75 TextIterator::TextIterator() : m_startContainer(0), m_startOffset(0), m_endContainer(0), m_endOffset(0), m_positionNode(0), m_lastCharacter(0)
76 {
77 }
78
79 TextIterator::TextIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions) 
80     : m_startContainer(0) 
81     , m_startOffset(0)
82     , m_endContainer(0)
83     , m_endOffset(0)
84     , m_positionNode(0)
85     , m_emitCharactersBetweenAllVisiblePositions(emitCharactersBetweenAllVisiblePositions)
86 {
87     if (!r)
88         return;
89
90     ExceptionCode ec = 0;
91     
92     // get and validate the range endpoints
93     Node *startContainer = r->startContainer(ec);
94     int startOffset = r->startOffset(ec);
95     Node *endContainer = r->endContainer(ec);
96     int endOffset = r->endOffset(ec);
97     if (ec)
98         return;
99
100     // Callers should be handing us well-formed ranges. If we discover that this isn't
101     // the case, we could consider changing this assertion to an early return.
102     ASSERT(r->boundaryPointsValid());
103
104     // remember range - this does not change
105     m_startContainer = startContainer;
106     m_startOffset = startOffset;
107     m_endContainer = endContainer;
108     m_endOffset = endOffset;
109     
110     // set up the current node for processing
111     m_node = r->firstNode();
112     if (m_node == 0)
113         return;
114     m_offset = m_node == m_startContainer ? m_startOffset : 0;
115     m_handledNode = false;
116     m_handledChildren = false;
117
118     // calculate first out of bounds node
119     m_pastEndNode = r->pastLastNode();
120
121     // initialize node processing state
122     m_needAnotherNewline = false;
123     m_textBox = 0;
124
125     // initialize record of previous node processing
126     m_haveEmitted = false;
127     m_lastTextNode = 0;
128     m_lastTextNodeEndedWithCollapsedSpace = false;
129     m_lastCharacter = 0;
130
131 #ifndef NDEBUG
132     // need this just because of the assert in advance()
133     m_positionNode = m_node;
134 #endif
135
136     // identify the first run
137     advance();
138 }
139
140 void TextIterator::advance()
141 {
142     // reset the run information
143     m_positionNode = 0;
144     m_textLength = 0;
145
146     // handle remembered node that needed a newline after the text node's newline
147     if (m_needAnotherNewline) {
148         // Emit the extra newline, and position it *inside* m_node, after m_node's 
149         // contents, in case it's a block, in the same way that we position the first 
150         // newline.  The range for the emitted newline should start where the line 
151         // break begins.
152         // FIXME: It would be cleaner if we emitted two newlines during the last 
153         // iteration, instead of using m_needAnotherNewline.
154         Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
155         emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
156         m_needAnotherNewline = false;
157         return;
158     }
159
160     // handle remembered text box
161     if (m_textBox) {
162         handleTextBox();
163         if (m_positionNode)
164             return;
165     }
166
167     while (m_node && m_node != m_pastEndNode) {
168         // if the range ends at offset 0 of an element, represent the
169         // position, but not the content, of that element e.g. if the
170         // node is a blockflow element, emit a newline that
171         // precedes the element
172         if (m_node == m_endContainer && m_endOffset == 0) {
173             representNodeOffsetZero();
174             m_node = 0;
175             return;
176         }
177         
178         RenderObject *renderer = m_node->renderer();
179         if (!renderer) {
180             m_handledNode = true;
181             m_handledChildren = true;
182         } else {
183             // handle current node according to its type
184             if (!m_handledNode) {
185                 if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) // FIXME: What about CDATA_SECTION_NODE?
186                     m_handledNode = handleTextNode();
187                 else if (renderer && (renderer->isImage() || renderer->isWidget() || (renderer->element() && renderer->element()->isControl())))
188                     m_handledNode = handleReplacedElement();
189                 else
190                     m_handledNode = handleNonTextNode();
191                 if (m_positionNode)
192                     return;
193             }
194         }
195
196         // find a new current node to handle in depth-first manner,
197         // calling exitNode() as we come back thru a parent node
198         Node *next = m_handledChildren ? 0 : m_node->firstChild();
199         m_offset = 0;
200         if (!next) {
201             next = m_node->nextSibling();
202             if (!next) {
203                 bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;
204                 while (!next && m_node->parentNode()) {
205                     if (pastEnd && m_node->parentNode() == m_endContainer || m_endContainer->isDescendantOf(m_node->parentNode()))
206                         return;
207                     bool haveRenderer = m_node->renderer();
208                     m_node = m_node->parentNode();
209                     if (haveRenderer)
210                         exitNode();
211                     if (m_positionNode) {
212                         m_handledNode = true;
213                         m_handledChildren = true;
214                         return;
215                     }
216                     next = m_node->nextSibling();
217                 }
218             }
219         }
220
221         // set the new current node
222         m_node = next;
223         m_handledNode = false;
224         m_handledChildren = false;
225
226         // how would this ever be?
227         if (m_positionNode)
228             return;
229     }
230 }
231
232 static inline bool compareBoxStart(const InlineTextBox *first, const InlineTextBox *second)
233 {
234     return first->start() < second->start();
235 }
236
237 bool TextIterator::handleTextNode()
238 {
239     RenderText* renderer = static_cast<RenderText*>(m_node->renderer());
240     if (renderer->style()->visibility() != VISIBLE)
241         return false;
242         
243     m_lastTextNode = m_node;
244     String str = renderer->text();
245
246     // handle pre-formatted text
247     if (!renderer->style()->collapseWhiteSpace()) {
248         int runStart = m_offset;
249         if (m_lastTextNodeEndedWithCollapsedSpace) {
250             emitCharacter(' ', m_node, 0, runStart, runStart);
251             return false;
252         }
253         int strLength = str.length();
254         int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
255         int runEnd = min(strLength, end);
256
257         if (runStart >= runEnd)
258             return true;
259
260         emitText(m_node, runStart, runEnd);
261         return true;
262     }
263
264     if (!renderer->firstTextBox() && str.length() > 0) {
265         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
266         return true;
267     }
268
269     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
270     if (renderer->containsReversedText()) {
271         m_sortedTextBoxes.clear();
272         for (InlineTextBox * textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
273             m_sortedTextBoxes.append(textBox);
274         }
275         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 
276         m_sortedTextBoxesPosition = 0;
277     }
278     
279     m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
280     handleTextBox();
281     return true;
282 }
283
284 void TextIterator::handleTextBox()
285 {    
286     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
287     String str = renderer->text();
288     int start = m_offset;
289     int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
290     while (m_textBox) {
291         int textBoxStart = m_textBox->m_start;
292         int runStart = max(textBoxStart, start);
293
294         // Check for collapsed space at the start of this run.
295         InlineTextBox *firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
296         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
297             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
298         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {
299             emitCharacter(' ', m_node, 0, runStart, runStart);
300             return;
301         }
302         int textBoxEnd = textBoxStart + m_textBox->m_len;
303         int runEnd = min(textBoxEnd, end);
304         
305         // Determine what the next text box will be, but don't advance yet
306         InlineTextBox *nextTextBox = 0;
307         if (renderer->containsReversedText()) {
308             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
309                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
310         } else 
311             nextTextBox = m_textBox->nextTextBox();
312
313         if (runStart < runEnd) {
314             // Handle either a single newline character (which becomes a space),
315             // or a run of characters that does not include a newline.
316             // This effectively translates newlines to spaces without copying the text.
317             if (str[runStart] == '\n') {
318                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
319                 m_offset = runStart + 1;
320             } else {
321                 int subrunEnd = str.find('\n', runStart);
322                 if (subrunEnd == -1 || subrunEnd > runEnd)
323                     subrunEnd = runEnd;
324     
325                 m_offset = subrunEnd;
326                 emitText(m_node, runStart, subrunEnd);
327             }
328
329             // If we are doing a subrun that doesn't go to the end of the text box,
330             // come back again to finish handling this text box; don't advance to the next one.
331             if (m_positionEndOffset < textBoxEnd)
332                 return;
333
334             // Advance and return
335             int nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();
336             if (nextRunStart > runEnd)
337                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
338             m_textBox = nextTextBox;
339             if (renderer->containsReversedText())
340                 ++m_sortedTextBoxesPosition;
341             return;
342         }
343         // Advance and continue
344         m_textBox = nextTextBox;
345         if (renderer->containsReversedText())
346             ++m_sortedTextBoxesPosition;
347     }
348 }
349
350 bool TextIterator::handleReplacedElement()
351 {
352     if (m_node->renderer()->style()->visibility() != VISIBLE)
353         return false;
354
355     if (m_lastTextNodeEndedWithCollapsedSpace) {
356         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
357         return false;
358     }
359
360     m_haveEmitted = true;
361     
362     if (m_emitCharactersBetweenAllVisiblePositions) {
363         // We want replaced elements to behave like punctuation for boundary 
364         // finding, and to simply take up space for the selection preservation 
365         // code in moveParagraphs, so we use a comma.
366         emitCharacter(',', m_node->parentNode(), m_node, 0, 1);
367         return true;
368     }
369     
370     m_positionNode = m_node->parentNode();
371     m_positionOffsetBaseNode = m_node;
372     m_positionStartOffset = 0;
373     m_positionEndOffset = 1;
374
375     m_textCharacters = 0;
376     m_textLength = 0;
377
378     m_lastCharacter = 0;
379
380     return true;
381 }
382
383 static bool shouldEmitTabBeforeNode(Node* node)
384 {
385     RenderObject* r = node->renderer();
386     
387     // Table cells are delimited by tabs.
388     if (!r || !isTableCell(node))
389         return false;
390     
391     // Want a tab before every cell other than the first one
392     RenderTableCell* rc = static_cast<RenderTableCell*>(r);
393     RenderTable* t = rc->table();
394     return t && (t->cellBefore(rc) || t->cellAbove(rc));
395 }
396
397 static bool shouldEmitNewlineForNode(Node* node)
398 {
399     // br elements are represented by a single newline.
400     RenderObject* r = node->renderer();
401     if (!r)
402         return node->hasTagName(brTag);
403         
404     return r->isBR();
405 }
406
407 static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)
408 {
409     // Block flow (versus inline flow) is represented by having
410     // a newline both before and after the element.
411     RenderObject* r = node->renderer();
412     if (!r) {
413         return (node->hasTagName(blockquoteTag)
414                 || node->hasTagName(ddTag)
415                 || node->hasTagName(divTag)
416                 || node->hasTagName(dlTag)
417                 || node->hasTagName(dtTag)
418                 || node->hasTagName(h1Tag)
419                 || node->hasTagName(h2Tag)
420                 || node->hasTagName(h3Tag)
421                 || node->hasTagName(h4Tag)
422                 || node->hasTagName(h5Tag)
423                 || node->hasTagName(h6Tag)
424                 || node->hasTagName(hrTag)
425                 || node->hasTagName(liTag)
426                 || node->hasTagName(listingTag)
427                 || node->hasTagName(olTag)
428                 || node->hasTagName(pTag)
429                 || node->hasTagName(preTag)
430                 || node->hasTagName(trTag)
431                 || node->hasTagName(ulTag));
432     }
433     
434     // Need to make an exception for table cells, because they are blocks, but we
435     // want them tab-delimited rather than having newlines before and after.
436     if (isTableCell(node))
437         return false;
438     
439     // Need to make an exception for table row elements, because they are neither
440     // "inline" or "RenderBlock", but we want newlines for them.
441     if (r->isTableRow()) {
442         RenderTable* t = static_cast<RenderTableRow*>(r)->table();
443         if (t && !t->isInline())
444             return true;
445     }
446     
447     return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();
448 }
449
450 static bool shouldEmitNewlineAfterNode(Node* node)
451 {
452     // FIXME: It should be better but slower to create a VisiblePosition here.
453     if (!shouldEmitNewlinesBeforeAndAfterNode(node))
454         return false;
455     // Check if this is the very last renderer in the document.
456     // If so, then we should not emit a newline.
457     while ((node = node->traverseNextSibling()))
458         if (node->renderer())
459             return true;
460     return false;
461 }
462
463 static bool shouldEmitNewlineBeforeNode(Node* node)
464 {
465     return shouldEmitNewlinesBeforeAndAfterNode(node); 
466 }
467
468 static bool shouldEmitExtraNewlineForNode(Node* node)
469 {
470     // When there is a significant collapsed bottom margin, emit an extra
471     // newline for a more realistic result.  We end up getting the right
472     // result even without margin collapsing. For example: <div><p>text</p></div>
473     // will work right even if both the <div> and the <p> have bottom margins.
474     RenderObject* r = node->renderer();
475     if (!r)
476         return false;
477     
478     // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears
479     // not to do this at all
480     if (node->hasTagName(h1Tag)
481         || node->hasTagName(h2Tag)
482         || node->hasTagName(h3Tag)
483         || node->hasTagName(h4Tag)
484         || node->hasTagName(h5Tag)
485         || node->hasTagName(h6Tag)
486         || node->hasTagName(pTag)) {
487         RenderStyle* style = r->style();
488         if (style) {
489             int bottomMargin = r->collapsedMarginBottom();
490             int fontSize = style->fontDescription().computedPixelSize();
491             if (bottomMargin * 2 >= fontSize)
492                 return true;
493         }
494     }
495     
496     return false;
497 }
498
499 bool TextIterator::shouldRepresentNodeOffsetZero()
500 {
501     if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable())
502         return true;
503         
504     // Leave element positioned flush with start of a paragraph
505     // (e.g. do not insert tab before a table cell at the start of a paragraph)
506     if (m_lastCharacter == '\n')
507         return false;
508     
509     // Otherwise, show the position if we have emitted any characters
510     if (m_haveEmitted)
511         return true;
512     
513     // We've not emitted anything yet. Generally, there is no need for any positioning then.
514     // The only exception is when the element is visually not in the same line as
515     // the start of the range (e.g. the range starts at the end of the previous paragraph).
516     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we
517     // make quicker checks to possibly avoid that. Another check that we could make is
518     // is whether the inline vs block flow changed since the previous visible element.
519     // I think we're already in a special enough case that that won't be needed, tho.
520
521     // If we are at the start, obviously no newline is needed.
522     if (m_node == m_startContainer)
523         return false;
524     
525     // If we are outside the start container's subtree, assume we need a newline.
526     // FIXME: m_startContainer could be an inline block
527     if (!m_node->isDescendantOf(m_startContainer))
528         return true;
529
530     // If we started as m_startContainer offset 0 and the current node is a descendant of
531     // the start container, we already had enough context to correctly decide whether to
532     // emit a newline after a preceding block. We chose not to emit (m_haveEmitted is false),
533     // so don't second guess that now.
534     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably
535     // immaterial since we likely would have already emitted something by now.
536     if (m_startOffset == 0)
537         return false;
538     
539     // The currPos.isNotNull() check is needed because positions in non-html content
540     // (like svg) do not have visible positions, and we don't want to emit for them either.
541     VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM);
542     VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM);
543     return currPos.isNotNull() && !inSameLine(startPos, currPos);
544 }
545
546 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)
547 {
548     return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitCharactersBetweenAllVisiblePositions);
549 }
550
551 void TextIterator::representNodeOffsetZero()
552 {
553     // Emit a character to show the positioning of m_node.
554     
555     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 
556     // create VisiblePositions, which is expensive.  So, we perform the inexpensive checks
557     // on m_node to see if it necessitates emitting a character first and will early return 
558     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
559     if (shouldEmitTabBeforeNode(m_node)) {
560         if (shouldRepresentNodeOffsetZero())
561             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);
562     } else if (shouldEmitNewlineBeforeNode(m_node)) {
563         if (shouldRepresentNodeOffsetZero())
564             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);
565     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {
566         if (shouldRepresentNodeOffsetZero())
567             emitCharacter(' ', m_node->parentNode(), m_node, 0, 0);
568     }
569 }
570
571 bool TextIterator::handleNonTextNode()
572 {
573     if (shouldEmitNewlineForNode(m_node))
574         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
575     else if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())
576         emitCharacter(' ', m_node->parentNode(), m_node, 0, 1);
577     else
578         representNodeOffsetZero();
579
580     return true;
581 }
582
583 void TextIterator::exitNode()
584 {
585     // prevent emitting a newline when exiting a collapsed block at beginning of the range
586     // FIXME: !m_haveEmitted does not necessarily mean there was a collapsed block... it could
587     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
588     // therefore look like a blank line.
589     if (!m_haveEmitted)
590         return;
591         
592     // Emit with a position *inside* m_node, after m_node's contents, in 
593     // case it is a block, because the run should start where the 
594     // emitted character is positioned visually.
595     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
596     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
597     // the logic in _web_attributedStringFromRange match.  We'll get that for free when we switch to use
598     // TextIterator in _web_attributedStringFromRange.
599     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
600     if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {
601         // use extra newline to represent margin bottom, as needed
602         bool addNewline = shouldEmitExtraNewlineForNode(m_node);
603         
604         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
605         // contain a VisiblePosition when doing selection preservation.
606         if (m_lastCharacter != '\n') {
607             // insert a newline with a position following this block's contents.
608             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
609             // remember whether to later add a newline for the current node
610             ASSERT(!m_needAnotherNewline);
611             m_needAnotherNewline = addNewline;
612         } else if (addNewline)
613             // insert a newline with a position following this block's contents.
614             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
615     }
616     
617     // If nothing was emitted, see if we need to emit a space.
618     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))
619         emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1);
620 }
621
622 void TextIterator::emitCharacter(UChar c, Node *textNode, Node *offsetBaseNode, int textStartOffset, int textEndOffset)
623 {
624     m_haveEmitted = true;
625     
626     // remember information with which to construct the TextIterator::range()
627     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
628     m_positionNode = textNode;
629     m_positionOffsetBaseNode = offsetBaseNode;
630     m_positionStartOffset = textStartOffset;
631     m_positionEndOffset = textEndOffset;
632  
633     // remember information with which to construct the TextIterator::characters() and length()
634     m_singleCharacterBuffer = c;
635     m_textCharacters = &m_singleCharacterBuffer;
636     m_textLength = 1;
637
638     // remember some iteration state
639     m_lastTextNodeEndedWithCollapsedSpace = false;
640     m_lastCharacter = c;
641 }
642
643 void TextIterator::emitText(Node *textNode, int textStartOffset, int textEndOffset)
644 {
645     RenderText* renderer = static_cast<RenderText*>(m_node->renderer());
646     String str = renderer->text();
647
648     m_positionNode = textNode;
649     m_positionOffsetBaseNode = 0;
650     m_positionStartOffset = textStartOffset;
651     m_positionEndOffset = textEndOffset;
652     m_textCharacters = str.characters() + textStartOffset;
653     m_textLength = textEndOffset - textStartOffset;
654     m_lastCharacter = str[textEndOffset - 1];
655
656     m_lastTextNodeEndedWithCollapsedSpace = false;
657     m_haveEmitted = true;
658 }
659
660 PassRefPtr<Range> TextIterator::range() const
661 {
662     // use the current run information, if we have it
663     if (m_positionNode) {
664         if (m_positionOffsetBaseNode) {
665             int index = m_positionOffsetBaseNode->nodeIndex();
666             m_positionStartOffset += index;
667             m_positionEndOffset += index;
668             m_positionOffsetBaseNode = 0;
669         }
670         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
671     }
672
673     // otherwise, return the end of the overall range we were given
674     if (m_endContainer)
675         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
676         
677     return 0;
678 }
679
680 // --------
681
682 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
683 {
684 }
685
686 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range *r)
687 {
688     m_positionNode = 0;
689
690     if (!r)
691         return;
692
693     int exception = 0;
694     Node *startNode = r->startContainer(exception);
695     if (exception)
696         return;
697     Node *endNode = r->endContainer(exception);
698     if (exception)
699         return;
700     int startOffset = r->startOffset(exception);
701     if (exception)
702         return;
703     int endOffset = r->endOffset(exception);
704     if (exception)
705         return;
706
707     if (!startNode->offsetInCharacters()) {
708         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
709             startNode = startNode->childNode(startOffset);
710             startOffset = 0;
711         }
712     }
713     if (!endNode->offsetInCharacters()) {
714         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {
715             endNode = endNode->childNode(endOffset - 1);
716             endOffset = endNode->offsetInCharacters() ? endNode->maxCharacterOffset() : endNode->childNodeCount();
717         }
718     }
719
720     m_node = endNode;
721     m_offset = endOffset;
722     m_handledNode = false;
723     m_handledChildren = endOffset == 0;
724
725     m_startNode = startNode;
726     m_startOffset = startOffset;
727     m_endNode = endNode;
728     m_endOffset = endOffset;
729     
730 #ifndef NDEBUG
731     // Need this just because of the assert.
732     m_positionNode = endNode;
733 #endif
734
735     m_lastTextNode = 0;
736     m_lastCharacter = '\n';
737     
738     if (startOffset == 0 || !startNode->firstChild()) {
739         m_pastStartNode = startNode->previousSibling();
740         while (!m_pastStartNode && startNode->parentNode()) {
741             startNode = startNode->parentNode();
742             m_pastStartNode = startNode->previousSibling();
743         }
744     } else
745         m_pastStartNode = startNode->childNode(startOffset - 1);
746
747     advance();
748 }
749
750 void SimplifiedBackwardsTextIterator::advance()
751 {
752     ASSERT(m_positionNode);
753
754     m_positionNode = 0;
755     m_textLength = 0;
756
757     while (m_node && m_node != m_pastStartNode) {
758         // Don't handle node if we start iterating at [node, 0].
759         if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) {
760             RenderObject *renderer = m_node->renderer();
761             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
762                 // FIXME: What about CDATA_SECTION_NODE?
763                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
764                     m_handledNode = handleTextNode();
765             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
766                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
767                     m_handledNode = handleReplacedElement();
768             } else
769                 m_handledNode = handleNonTextNode();
770             if (m_positionNode)
771                 return;
772         }
773
774         Node* next = m_handledChildren ? 0 : m_node->lastChild();
775         if (!next) {
776             // Exit empty containers as we pass over them or containers
777             // where [container, 0] is where we started iterating.
778             if (!m_handledNode &&
779                 canHaveChildrenForEditing(m_node) && 
780                 m_node->parentNode() && 
781                 (!m_node->lastChild() || m_node == m_endNode && m_endOffset == 0)) {
782                 exitNode();
783                 if (m_positionNode) {
784                     m_handledNode = true;
785                     m_handledChildren = true;
786                     return;
787                 }            
788             }
789             // Exit all other containers.
790             next = m_node->previousSibling();
791             while (!next) {
792                 if (!m_node->parentNode())
793                     break;
794                 m_node = m_node->parentNode();
795                 exitNode();
796                 if (m_positionNode) {
797                     m_handledNode = true;
798                     m_handledChildren = true;
799                     return;
800                 }
801                 next = m_node->previousSibling();
802             }
803         }
804         
805         m_node = next;
806         m_offset = m_node ? caretMaxOffset(m_node) : 0;
807         m_handledNode = false;
808         m_handledChildren = false;
809         
810         if (m_positionNode)
811             return;
812     }
813 }
814
815 bool SimplifiedBackwardsTextIterator::handleTextNode()
816 {
817     m_lastTextNode = m_node;
818
819     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
820     String str = renderer->text();
821
822     if (!renderer->firstTextBox() && str.length() > 0)
823         return true;
824
825     m_positionEndOffset = m_offset;
826
827     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
828     m_positionNode = m_node;
829     m_positionStartOffset = m_offset;
830     m_textLength = m_positionEndOffset - m_positionStartOffset;
831     m_textCharacters = str.characters() + m_positionStartOffset;
832
833     m_lastCharacter = str[m_positionEndOffset - 1];
834
835     return true;
836 }
837
838 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
839 {
840     unsigned index = m_node->nodeIndex();
841     // We want replaced elements to behave like punctuation for boundary 
842     // finding, and to simply take up space for the selection preservation 
843     // code in moveParagraphs, so we use a comma.  Unconditionally emit
844     // here because this iterator is only used for boundary finding.
845     emitCharacter(',', m_node->parentNode(), index, index + 1);
846     return true;
847 }
848
849 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
850 {    
851     // We can use a linefeed in place of a tab because this simple iterator is only used to
852     // find boundaries, not actual content.  A linefeed breaks words, sentences, and paragraphs.
853     if (shouldEmitNewlineForNode(m_node) ||
854         shouldEmitNewlineAfterNode(m_node) ||
855         shouldEmitTabBeforeNode(m_node)) {
856         unsigned index = m_node->nodeIndex();
857         // The start of this emitted range is wrong, ensuring correctness would require
858         // VisiblePositions and so would be slow.  previousBoundary expects this.
859         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
860     }
861     
862     return true;
863 }
864
865 void SimplifiedBackwardsTextIterator::exitNode()
866 {
867     if (shouldEmitNewlineForNode(m_node) ||
868         shouldEmitNewlineBeforeNode(m_node) ||
869         shouldEmitTabBeforeNode(m_node))
870         // The start of this emitted range is wrong, ensuring correctness would require
871         // VisiblePositions and so would be slow.  previousBoundary expects this.
872         emitCharacter('\n', m_node, 0, 0);
873 }
874
875 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node *node, int startOffset, int endOffset)
876 {
877     m_singleCharacterBuffer = c;
878     m_positionNode = node;
879     m_positionStartOffset = startOffset;
880     m_positionEndOffset = endOffset;
881     m_textCharacters = &m_singleCharacterBuffer;
882     m_textLength = 1;
883     m_lastCharacter = c;
884 }
885
886 PassRefPtr<Range> SimplifiedBackwardsTextIterator::range() const
887 {
888     if (m_positionNode)
889         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
890     
891     return Range::create(m_startNode->document(), m_startNode, m_startOffset, m_startNode, m_startOffset);
892 }
893
894 // --------
895
896 CharacterIterator::CharacterIterator()
897     : m_offset(0), m_runOffset(0), m_atBreak(true)
898 {
899 }
900
901 CharacterIterator::CharacterIterator(const Range *r, bool emitCharactersBetweenAllVisiblePositions)
902     : m_offset(0), m_runOffset(0), m_atBreak(true), m_textIterator(r, emitCharactersBetweenAllVisiblePositions)
903 {
904     while (!atEnd() && m_textIterator.length() == 0)
905         m_textIterator.advance();
906 }
907
908 PassRefPtr<Range> CharacterIterator::range() const
909 {
910     RefPtr<Range> r = m_textIterator.range();
911     if (!m_textIterator.atEnd()) {
912         if (m_textIterator.length() <= 1) {
913             ASSERT(m_runOffset == 0);
914         } else {
915             int exception = 0;
916             Node *n = r->startContainer(exception);
917             ASSERT(n == r->endContainer(exception));
918             int offset = r->startOffset(exception) + m_runOffset;
919             r->setStart(n, offset, exception);
920             r->setEnd(n, offset + 1, exception);
921         }
922     }
923     return r.release();
924 }
925
926 void CharacterIterator::advance(int count)
927 {
928     if (count <= 0) {
929         ASSERT(count == 0);
930         return;
931     }
932     
933     m_atBreak = false;
934
935     // easy if there is enough left in the current m_textIterator run
936     int remaining = m_textIterator.length() - m_runOffset;
937     if (count < remaining) {
938         m_runOffset += count;
939         m_offset += count;
940         return;
941     }
942
943     // exhaust the current m_textIterator run
944     count -= remaining;
945     m_offset += remaining;
946     
947     // move to a subsequent m_textIterator run
948     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
949         int runLength = m_textIterator.length();
950         if (runLength == 0)
951             m_atBreak = true;
952         else {
953             // see whether this is m_textIterator to use
954             if (count < runLength) {
955                 m_runOffset = count;
956                 m_offset += count;
957                 return;
958             }
959             
960             // exhaust this m_textIterator run
961             count -= runLength;
962             m_offset += runLength;
963         }
964     }
965
966     // ran to the end of the m_textIterator... no more runs left
967     m_atBreak = true;
968     m_runOffset = 0;
969 }
970
971 String CharacterIterator::string(int numChars)
972 {
973     Vector<UChar> result;
974     result.reserveCapacity(numChars);
975     while (numChars > 0 && !atEnd()) {
976         int runSize = min(numChars, length());
977         result.append(characters(), runSize);
978         numChars -= runSize;
979         advance(runSize);
980     }
981     return String::adopt(result);
982 }
983
984 // --------
985
986 WordAwareIterator::WordAwareIterator()
987 : m_previousText(0), m_didLookAhead(false)
988 {
989 }
990
991 WordAwareIterator::WordAwareIterator(const Range *r)
992 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
993 {
994     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
995     advance();              // get in position over the first chunk of text
996 }
997
998 // We're always in one of these modes:
999 // - The current chunk in the text iterator is our current chunk
1000 //      (typically its a piece of whitespace, or text that ended with whitespace)
1001 // - The previous chunk in the text iterator is our current chunk
1002 //      (we looked ahead to the next chunk and found a word boundary)
1003 // - We built up our own chunk of text from many chunks from the text iterator
1004
1005 // FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
1006
1007 void WordAwareIterator::advance()
1008 {
1009     m_previousText = 0;
1010     m_buffer.clear();      // toss any old buffer we built up
1011
1012     // If last time we did a look-ahead, start with that looked-ahead chunk now
1013     if (!m_didLookAhead) {
1014         ASSERT(!m_textIterator.atEnd());
1015         m_textIterator.advance();
1016     }
1017     m_didLookAhead = false;
1018
1019     // Go to next non-empty chunk 
1020     while (!m_textIterator.atEnd() && m_textIterator.length() == 0)
1021         m_textIterator.advance();
1022     m_range = m_textIterator.range();
1023
1024     if (m_textIterator.atEnd())
1025         return;
1026     
1027     while (1) {
1028         // If this chunk ends in whitespace we can just use it as our chunk.
1029         if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1]))
1030             return;
1031
1032         // If this is the first chunk that failed, save it in previousText before look ahead
1033         if (m_buffer.isEmpty()) {
1034             m_previousText = m_textIterator.characters();
1035             m_previousLength = m_textIterator.length();
1036         }
1037
1038         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
1039         m_textIterator.advance();
1040         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) {
1041             m_didLookAhead = true;
1042             return;
1043         }
1044
1045         if (m_buffer.isEmpty()) {
1046             // Start gobbling chunks until we get to a suitable stopping point
1047             m_buffer.append(m_previousText, m_previousLength);
1048             m_previousText = 0;
1049         }
1050         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
1051         int exception = 0;
1052         m_range->setEnd(m_textIterator.range()->endContainer(exception), m_textIterator.range()->endOffset(exception), exception);
1053     }
1054 }
1055
1056 int WordAwareIterator::length() const
1057 {
1058     if (!m_buffer.isEmpty())
1059         return m_buffer.size();
1060     if (m_previousText)
1061         return m_previousLength;
1062     return m_textIterator.length();
1063 }
1064
1065 const UChar* WordAwareIterator::characters() const
1066 {
1067     if (!m_buffer.isEmpty())
1068         return m_buffer.data();
1069     if (m_previousText)
1070         return m_previousText;
1071     return m_textIterator.characters();
1072 }
1073
1074 // --------
1075
1076 CircularSearchBuffer::CircularSearchBuffer(const String& s, bool isCaseSensitive)
1077     : m_target(isCaseSensitive ? s : s.foldCase())
1078     , m_isCaseSensitive(isCaseSensitive)
1079     , m_characterBuffer(m_target.length())
1080     , m_isCharacterStartBuffer(m_target.length())
1081     , m_isBufferFull(false)
1082     , m_cursor(0)
1083 {
1084     ASSERT(!m_target.isEmpty());
1085     m_target.replace(noBreakSpace, ' ');
1086 }
1087
1088 inline void CircularSearchBuffer::append(UChar c, bool isStart)
1089 {
1090     m_characterBuffer[m_cursor] = c == noBreakSpace ? ' ' : c;
1091     m_isCharacterStartBuffer[m_cursor] = isStart;
1092     if (++m_cursor == m_target.length()) {
1093         m_cursor = 0;
1094         m_isBufferFull = true;
1095     }
1096 }
1097
1098 inline void CircularSearchBuffer::append(UChar c)
1099 {
1100     if (m_isCaseSensitive) {
1101         append(c, true);
1102         return;
1103     }
1104     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
1105     UChar foldedCharacters[maxFoldedCharacters];
1106     bool error;
1107     int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, &c, 1, &error);
1108     ASSERT(!error);
1109     ASSERT(numFoldedCharacters);
1110     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
1111     if (!error && numFoldedCharacters) {
1112         numFoldedCharacters = min(numFoldedCharacters, maxFoldedCharacters);
1113         append(foldedCharacters[0], true);
1114         for (int i = 1; i < numFoldedCharacters; ++i)
1115             append(foldedCharacters[i], false);
1116     }
1117 }
1118
1119 inline bool CircularSearchBuffer::isMatch() const
1120 {
1121     if (!m_isBufferFull)
1122         return false;
1123     if (!m_isCharacterStartBuffer[m_cursor])
1124         return false;
1125
1126     unsigned tailSpace = m_target.length() - m_cursor;
1127     return memcmp(&m_characterBuffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) == 0
1128         && memcmp(&m_characterBuffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) == 0;
1129 }
1130
1131 // Returns the number of characters that were appended to the buffer (what we are searching in).
1132 // That's not necessarily the same length as the passed-in target string, because case folding
1133 // can make two strings match even though they're not the same length.
1134 unsigned CircularSearchBuffer::length() const
1135 {
1136     ASSERT(isMatch());
1137
1138     unsigned bufferSize = m_target.length();
1139     unsigned length = 0;
1140     for (unsigned i = 0; i < bufferSize; ++i)
1141         length += m_isCharacterStartBuffer[i];
1142     return length;
1143 }
1144
1145 // --------
1146
1147 int TextIterator::rangeLength(const Range *r, bool forSelectionPreservation)
1148 {
1149     int length = 0;
1150     for (TextIterator it(r, forSelectionPreservation); !it.atEnd(); it.advance())
1151         length += it.length();
1152     
1153     return length;
1154 }
1155
1156 PassRefPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
1157 {
1158     CharacterIterator chars(entireRange);
1159
1160     chars.advance(characterOffset);
1161     RefPtr<Range> start = chars.range();
1162
1163     chars.advance(characterCount);
1164     RefPtr<Range> end = chars.range();
1165     
1166     ExceptionCode ec = 0;
1167     RefPtr<Range> result(Range::create(entireRange->ownerDocument(), 
1168                                     start->startContainer(ec), 
1169                                     start->startOffset(ec), 
1170                                     end->startContainer(ec), 
1171                                     end->startOffset(ec)));
1172     ASSERT(!ec);
1173     
1174     return result.release();
1175 }
1176
1177 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element *scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
1178 {
1179     RefPtr<Range> resultRange = scope->document()->createRange();
1180
1181     int docTextPosition = 0;
1182     int rangeEnd = rangeLocation + rangeLength;
1183     bool startRangeFound = false;
1184
1185     RefPtr<Range> textRunRange;
1186
1187     TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation);
1188     
1189     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
1190     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
1191         int exception = 0;
1192         textRunRange = it.range();
1193         
1194         resultRange->setStart(textRunRange->startContainer(exception), 0, exception);
1195         ASSERT(exception == 0);
1196         resultRange->setEnd(textRunRange->startContainer(exception), 0, exception);
1197         ASSERT(exception == 0);
1198         
1199         return resultRange.release();
1200     }
1201
1202     for (; !it.atEnd(); it.advance()) {
1203         int len = it.length();
1204         textRunRange = it.range();
1205         
1206         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len;
1207         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len;
1208         
1209         // Fix textRunRange->endPosition(), but only if foundStart || foundEnd, because it is only
1210         // in those cases that textRunRange is used.
1211         if (foundStart || foundEnd) {
1212             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
1213             // position for emitted '\n's.
1214             if (len == 1 && it.characters()[0] == UChar('\n')) {
1215                 Position runStart = textRunRange->startPosition();
1216                 Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
1217                 if (runEnd.isNotNull()) {
1218                     ExceptionCode ec = 0;
1219                     textRunRange->setEnd(runEnd.node(), runEnd.offset(), ec);
1220                 }
1221             }
1222         }
1223
1224         if (foundStart) {
1225             startRangeFound = true;
1226             int exception = 0;
1227             if (textRunRange->startContainer(exception)->isTextNode()) {
1228                 int offset = rangeLocation - docTextPosition;
1229                 resultRange->setStart(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
1230             } else {
1231                 if (rangeLocation == docTextPosition)
1232                     resultRange->setStart(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
1233                 else
1234                     resultRange->setStart(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1235             }
1236         }
1237
1238         if (foundEnd) {
1239             int exception = 0;
1240             if (textRunRange->startContainer(exception)->isTextNode()) {
1241                 int offset = rangeEnd - docTextPosition;
1242                 resultRange->setEnd(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
1243             } else {
1244                 if (rangeEnd == docTextPosition)
1245                     resultRange->setEnd(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
1246                 else
1247                     resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1248             }
1249             docTextPosition += len;
1250             break;
1251         }
1252         docTextPosition += len;
1253     }
1254     
1255     if (!startRangeFound)
1256         return 0;
1257     
1258     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1259         int exception = 0;
1260         resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1261     }
1262     
1263     return resultRange.release();
1264 }
1265
1266 // --------
1267     
1268 UChar* plainTextToMallocAllocatedBuffer(const Range* r, unsigned& bufferLength) 
1269 {
1270     UChar* result = 0;
1271
1272     // Do this in pieces to avoid massive reallocations if there is a large amount of text.
1273     // Use system malloc for buffers since they can consume lots of memory and current TCMalloc is unable return it back to OS.
1274     static const unsigned cMaxSegmentSize = 1 << 16;
1275     bufferLength = 0;
1276     typedef pair<UChar*, unsigned> TextSegment;
1277     Vector<TextSegment>* textSegments = 0;
1278     Vector<UChar> textBuffer;
1279     textBuffer.reserveCapacity(cMaxSegmentSize);
1280     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1281         if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) {
1282             UChar* newSegmentBuffer = static_cast<UChar*>(malloc(textBuffer.size() * sizeof(UChar)));
1283             if (!newSegmentBuffer)
1284                 goto exit;
1285             memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1286             if (!textSegments)
1287                 textSegments = new Vector<TextSegment>;
1288             textSegments->append(make_pair(newSegmentBuffer, textBuffer.size()));
1289             textBuffer.clear();
1290         }
1291         textBuffer.append(it.characters(), it.length());
1292         bufferLength += it.length();
1293     }
1294
1295     if (!bufferLength)
1296         return 0;
1297
1298     // Since we know the size now, we can make a single buffer out of the pieces with one big alloc
1299     result = static_cast<UChar*>(malloc(bufferLength * sizeof(UChar)));
1300     if (!result)
1301         goto exit;
1302
1303     {
1304         UChar* resultPos = result;
1305         if (textSegments) {
1306             unsigned size = textSegments->size();
1307             for (unsigned i = 0; i < size; ++i) {
1308                 const TextSegment& segment = textSegments->at(i);
1309                 memcpy(resultPos, segment.first, segment.second * sizeof(UChar));
1310                 resultPos += segment.second;
1311             }
1312         }
1313         memcpy(resultPos, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1314     }
1315
1316 exit:
1317     if (textSegments) {
1318         unsigned size = textSegments->size();
1319         for (unsigned i = 0; i < size; ++i)
1320             free(textSegments->at(i).first);
1321         delete textSegments;
1322     }
1323     return result;
1324 }
1325
1326 String plainText(const Range* r)
1327 {
1328     unsigned length;
1329     UChar* buf = plainTextToMallocAllocatedBuffer(r, length);
1330     if (!buf)
1331         return "";
1332     String result(buf, length);
1333     free(buf);
1334     return result;
1335 }
1336
1337 PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
1338 {
1339     // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
1340
1341     ExceptionCode ec = 0;
1342     RefPtr<Range> result = range->cloneRange(ec);
1343     result->collapse(!forward, ec);
1344
1345     // FIXME: This code does not allow \n at the moment because of issues with <br>.
1346     // Once we fix those, we can remove this check.
1347     if (target.isEmpty() || target.find('\n') != -1)
1348         return result.release();
1349
1350     unsigned matchStart = 0;
1351     unsigned matchLength = 0;
1352     {
1353         CircularSearchBuffer searchBuffer(target, caseSensitive);
1354         CharacterIterator it(range);
1355         for (;;) {
1356             if (searchBuffer.isMatch()) {
1357                 // Note that we found a match, and where we found it.
1358                 unsigned matchEnd = it.characterOffset();
1359                 matchLength = searchBuffer.length();
1360                 ASSERT(matchLength);
1361                 ASSERT(matchEnd >= matchLength);
1362                 matchStart = matchEnd - matchLength;
1363                 // If searching forward, stop on the first match.
1364                 // If searching backward, don't stop, so we end up with the last match.
1365                 if (forward)
1366                     break;
1367             }
1368             if (it.atBreak()) {
1369                 if (it.atEnd())
1370                     break;
1371                 searchBuffer.clear();
1372             }
1373             searchBuffer.append(it.characters()[0]);
1374             it.advance(1);
1375         }
1376     }
1377
1378     if (matchLength) {
1379         CharacterIterator it(range);
1380         it.advance(matchStart);
1381         result->setStart(it.range()->startContainer(ec), it.range()->startOffset(ec), ec);
1382         it.advance(matchLength - 1);
1383         result->setEnd(it.range()->endContainer(ec), it.range()->endOffset(ec), ec);
1384     }
1385
1386     return result.release();
1387 }
1388
1389 }