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