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