2006-03-20 Eric Seidel <eseidel@apple.com>
[WebKit-https.git] / WebCore / editing / TextIterator.cpp
1 /*
2  * Copyright (C) 2004 Apple Computer, 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 "HTMLNames.h"
31 #include "InlineTextBox.h"
32 #include "Position.h"
33 #include "Range.h"
34 #include "Document.h"
35
36 using namespace WebCore::HTMLNames;
37 using namespace WebCore;
38
39 // FIXME: These classes should probably use the render tree and not the DOM tree, since elements could
40 // be hidden using CSS, or additional generated content could be added.  For now, we just make sure
41 // text objects walk their renderers' InlineTextBox objects, so that we at least get the whitespace 
42 // stripped out properly and obey CSS visibility for text runs.
43
44 namespace WebCore {
45
46 const unsigned short nonBreakingSpace = 0xA0;
47
48 // Buffer that knows how to compare with a search target.
49 // Keeps enough of the previous text to be able to search in the future,
50 // but no more.
51 class CircularSearchBuffer {
52 public:
53     CircularSearchBuffer(const String& target, bool isCaseSensitive);
54     ~CircularSearchBuffer() { fastFree(m_buffer); }
55
56     void clear() { m_cursor = m_buffer; m_bufferFull = false; }
57     void append(int length, const QChar *characters);
58     void append(const QChar&);
59
60     int neededCharacters() const;
61     bool isMatch() const;
62     int length() const { return m_target.length(); }
63
64 private:
65     String m_target;
66     bool m_isCaseSensitive;
67
68     QChar *m_buffer;
69     QChar *m_cursor;
70     bool m_bufferFull;
71
72     CircularSearchBuffer(const CircularSearchBuffer&);
73     CircularSearchBuffer &operator=(const CircularSearchBuffer&);
74 };
75
76 TextIterator::TextIterator() : m_endContainer(0), m_endOffset(0), m_positionNode(0)
77 {
78 }
79
80 TextIterator::TextIterator(const Range *r, IteratorKind kind) : m_endContainer(0), m_endOffset(0), m_positionNode(0)
81 {
82     if (!r)
83         return;
84
85     ExceptionCode ec = 0;
86
87     // get and validate the range endpoints
88     Node *startContainer = r->startContainer(ec);
89     int startOffset = r->startOffset(ec);
90     Node *endContainer = r->endContainer(ec);
91     int endOffset = r->endOffset(ec);
92     if (ec != 0)
93         return;
94
95     // remember ending place - this does not change
96     m_endContainer = endContainer;
97     m_endOffset = endOffset;
98
99     // set up the current node for processing
100     m_node = r->startNode();
101     if (m_node == 0)
102         return;
103     m_offset = m_node == startContainer ? startOffset : 0;
104     m_handledNode = false;
105     m_handledChildren = false;
106
107     // calculate first out of bounds node
108     m_pastEndNode = r->pastEndNode();
109
110     // initialize node processing state
111     m_needAnotherNewline = false;
112     m_textBox = 0;
113
114     // initialize record of previous node processing
115     m_lastTextNode = 0;
116     m_lastTextNodeEndedWithCollapsedSpace = false;
117     if (kind == RUNFINDER)
118         m_lastCharacter = 0;
119     else
120         m_lastCharacter = '\n';
121
122 #ifndef NDEBUG
123     // need this just because of the assert in advance()
124     m_positionNode = m_node;
125 #endif
126
127     // identify the first run
128     advance();
129 }
130
131 void TextIterator::advance()
132 {
133     // reset the run information
134     m_positionNode = 0;
135     m_textLength = 0;
136
137     // handle remembered node that needed a newline after the text node's newline
138     if (m_needAnotherNewline) {
139         // emit the newline, with position a collapsed range at the end of current node.
140         emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
141         m_needAnotherNewline = false;
142         return;
143     }
144
145     // handle remembered text box
146     if (m_textBox) {
147         handleTextBox();
148         if (m_positionNode)
149             return;
150     }
151
152     while (m_node && m_node != m_pastEndNode) {
153         // handle current node according to its type
154         if (!m_handledNode) {
155             RenderObject *renderer = m_node->renderer();
156             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
157                 // FIXME: What about CDATA_SECTION_NODE?
158                 if (renderer->style()->visibility() == VISIBLE)
159                     m_handledNode = handleTextNode();
160             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
161                 if (renderer->style()->visibility() == VISIBLE)
162                     m_handledNode = handleReplacedElement();
163             } else
164                 m_handledNode = handleNonTextNode();
165             if (m_positionNode)
166                 return;
167         }
168
169         // find a new current node to handle in depth-first manner,
170         // calling exitNode() as we come back thru a parent node
171         Node *next = m_handledChildren ? 0 : m_node->firstChild();
172         m_offset = 0;
173         if (!next) {
174             next = m_node->nextSibling();
175             if (!next) {
176                 if (m_node->traverseNextNode() == m_pastEndNode)
177                     break;
178                 while (!next && m_node->parentNode()) {
179                     m_node = m_node->parentNode();
180                     exitNode();
181                     if (m_positionNode) {
182                         m_handledNode = true;
183                         m_handledChildren = true;
184                         return;
185                     }
186                     next = m_node->nextSibling();
187                 }
188             }
189         }
190
191         // set the new current node
192         m_node = next;
193         m_handledNode = false;
194         m_handledChildren = false;
195
196         // how would this ever be?
197         if (m_positionNode)
198             return;
199     }
200 }
201
202 static inline bool compareBoxStart(const InlineTextBox *first, const InlineTextBox *second)
203 {
204     return first->start() < second->start();
205 }
206
207 bool TextIterator::handleTextNode()
208 {
209     m_lastTextNode = m_node;
210
211     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
212     String str = renderer->string();
213
214     // handle pre-formatted text
215     if (!renderer->style()->collapseWhiteSpace()) {
216         int runStart = m_offset;
217         if (m_lastTextNodeEndedWithCollapsedSpace) {
218             emitCharacter(' ', m_node, 0, runStart, runStart);
219             return false;
220         }
221         int strLength = str.length();
222         int end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
223         int runEnd = kMin(strLength, end);
224
225         if (runStart >= runEnd)
226             return true;
227
228         m_positionNode = m_node;
229         m_positionOffsetBaseNode = 0;
230         m_positionStartOffset = runStart;
231         m_positionEndOffset = runEnd;
232         m_textCharacters = str.unicode() + runStart;
233         m_textLength = runEnd - runStart;
234
235         m_lastCharacter = str[runEnd - 1];
236
237         return true;
238     }
239
240     if (!renderer->firstTextBox() && str.length() > 0) {
241         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
242         return true;
243     }
244
245     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
246     if (renderer->containsReversedText()) {
247         m_sortedTextBoxes.clear();
248         for (InlineTextBox * textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
249             m_sortedTextBoxes.append(textBox);
250         }
251         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 
252         m_sortedTextBoxesPosition = 0;
253     }
254     
255     m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
256     handleTextBox();
257     return true;
258 }
259
260 void TextIterator::handleTextBox()
261 {    
262     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
263     String str = renderer->string();
264     int start = m_offset;
265     int end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
266     while (m_textBox) {
267         int textBoxStart = m_textBox->m_start;
268         int runStart = kMax(textBoxStart, start);
269
270         // Check for collapsed space at the start of this run.
271         InlineTextBox *firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
272         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
273             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
274         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && !m_lastCharacter.isNull()) {
275             emitCharacter(' ', m_node, 0, runStart, runStart);
276             return;
277         }
278         int textBoxEnd = textBoxStart + m_textBox->m_len;
279         int runEnd = kMin(textBoxEnd, end);
280         
281         // Determine what the next text box will be, but don't advance yet
282         InlineTextBox *nextTextBox = 0;
283         if (renderer->containsReversedText()) {
284             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
285                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
286         } else 
287             nextTextBox = m_textBox->nextTextBox();
288
289         if (runStart < runEnd) {
290             // Handle either a single newline character (which becomes a space),
291             // or a run of characters that does not include a newline.
292             // This effectively translates newlines to spaces without copying the text.
293             if (str[runStart] == '\n') {
294                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
295                 m_offset = runStart + 1;
296             } else {
297                 int subrunEnd = str.find('\n', runStart);
298                 if (subrunEnd == -1 || subrunEnd > runEnd)
299                     subrunEnd = runEnd;
300
301                 m_offset = subrunEnd;
302
303                 m_positionNode = m_node;
304                 m_positionOffsetBaseNode = 0;
305                 m_positionStartOffset = runStart;
306                 m_positionEndOffset = subrunEnd;
307                 m_textCharacters = str.unicode() + runStart;
308                 m_textLength = subrunEnd - runStart;
309
310                 m_lastTextNodeEndedWithCollapsedSpace = false;
311                 m_lastCharacter = str[subrunEnd - 1];
312             }
313
314             // If we are doing a subrun that doesn't go to the end of the text box,
315             // come back again to finish handling this text box; don't advance to the next one.
316             if (m_positionEndOffset < textBoxEnd)
317                 return;
318
319             // Advance and return
320             int nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();
321             if (nextRunStart > runEnd)
322                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
323             m_textBox = nextTextBox;
324             if (renderer->containsReversedText())
325                 ++m_sortedTextBoxesPosition;
326             return;
327         }
328         // Advance and continue
329         m_textBox = nextTextBox;
330         if (renderer->containsReversedText())
331             ++m_sortedTextBoxesPosition;
332     }
333 }
334
335 bool TextIterator::handleReplacedElement()
336 {
337     if (m_lastTextNodeEndedWithCollapsedSpace) {
338         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
339         return false;
340     }
341
342     m_positionNode = m_node->parentNode();
343     m_positionOffsetBaseNode = m_node;
344     m_positionStartOffset = 0;
345     m_positionEndOffset = 1;
346
347     m_textCharacters = 0;
348     m_textLength = 0;
349
350     m_lastCharacter = 0;
351
352     return true;
353 }
354
355 bool TextIterator::handleNonTextNode()
356 {
357     if (m_node->hasTagName(brTag)) {
358         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
359     } else if (m_node->hasTagName(tdTag) || m_node->hasTagName(thTag)) {
360         if (m_lastCharacter != '\n' && m_lastTextNode)
361             emitCharacter('\t', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
362     } else if (m_node->hasTagName(blockquoteTag) || m_node->hasTagName(ddTag) ||
363                m_node->hasTagName(divTag) ||
364                m_node->hasTagName(dlTag) || m_node->hasTagName(dtTag) || 
365                m_node->hasTagName(h1Tag) || m_node->hasTagName(h2Tag) ||
366                m_node->hasTagName(h3Tag) || m_node->hasTagName(h4Tag) ||
367                m_node->hasTagName(h5Tag) || m_node->hasTagName(h6Tag) ||
368                m_node->hasTagName(hrTag) || m_node->hasTagName(liTag) ||
369                m_node->hasTagName(olTag) || m_node->hasTagName(pTag) ||
370                m_node->hasTagName(preTag) || m_node->hasTagName(trTag) ||
371                m_node->hasTagName(ulTag)) {
372         if (m_lastCharacter != '\n' && m_lastTextNode)
373             emitCharacter('\n', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
374     }
375
376     return true;
377 }
378
379 void TextIterator::exitNode()
380 {
381     bool endLine = false;
382     bool addNewline = false;
383
384     if (m_node->hasTagName(blockquoteTag) || m_node->hasTagName(ddTag) ||
385                m_node->hasTagName(divTag) ||
386                m_node->hasTagName(dlTag) || m_node->hasTagName(dtTag) || 
387                m_node->hasTagName(hrTag) || m_node->hasTagName(liTag) ||
388                m_node->hasTagName(olTag) ||
389                m_node->hasTagName(preTag) || m_node->hasTagName(trTag) ||
390                m_node->hasTagName(ulTag))
391         endLine = true;
392     else if (m_node->hasTagName(h1Tag) || m_node->hasTagName(h2Tag) ||
393              m_node->hasTagName(h3Tag) || m_node->hasTagName(h4Tag) ||
394              m_node->hasTagName(h5Tag) || m_node->hasTagName(h6Tag) ||
395              m_node->hasTagName(pTag)) {
396         endLine = true;
397
398         // In certain cases, emit a new newline character for this node
399         // regardless of whether we emit another one.
400         // FIXME: Some day we could do this for other tags.
401         // However, doing it just for the tags above makes it more likely
402         // we'll end up getting the right result without margin collapsing.
403         // For example: <div><p>text</p></div> will work right even if both
404         // the <div> and the <p> have bottom margins.
405         RenderObject *renderer = m_node->renderer();
406         if (renderer) {
407             RenderStyle *style = renderer->style();
408             if (style) {
409                 int bottomMargin = renderer->collapsedMarginBottom();
410                 int fontSize = style->fontDescription().computedPixelSize();
411                 if (bottomMargin * 2 >= fontSize)
412                     addNewline = true;
413             }
414         }
415     }
416
417     // emit character(s) iff there is an earlier text node and we need at least one newline
418     if (m_lastTextNode && endLine) {
419         if (m_lastCharacter != '\n') {
420             // insert a newline with a position following this block
421             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
422
423             //...and, if needed, set flag to later add a newline for the current node
424             assert(!m_needAnotherNewline);
425             m_needAnotherNewline = addNewline;
426         } else if (addNewline) {
427             // insert a newline with a position following this block
428             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
429         }
430     }
431 }
432
433 void TextIterator::emitCharacter(QChar c, Node *textNode, Node *offsetBaseNode, int textStartOffset, int textEndOffset)
434 {
435     // remember information with which to construct the TextIterator::range()
436     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
437     m_positionNode = textNode;
438     m_positionOffsetBaseNode = offsetBaseNode;
439     m_positionStartOffset = textStartOffset;
440     m_positionEndOffset = textEndOffset;
441  
442     // remember information with which to construct the TextIterator::characters() and length()
443     m_singleCharacterBuffer = c;
444     m_textCharacters = &m_singleCharacterBuffer;
445     m_textLength = 1;
446
447     // remember some iteration state
448     m_lastTextNodeEndedWithCollapsedSpace = false;
449     m_lastCharacter = c;
450 }
451
452 PassRefPtr<Range> TextIterator::range() const
453 {
454     // use the current run information, if we have it
455     if (m_positionNode) {
456         if (m_positionOffsetBaseNode) {
457             int index = m_positionOffsetBaseNode->nodeIndex();
458             m_positionStartOffset += index;
459             m_positionEndOffset += index;
460             m_positionOffsetBaseNode = 0;
461         }
462         return new Range(m_positionNode->getDocument(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
463     }
464
465     // otherwise, return the end of the overall range we were given
466     if (m_endContainer)
467         return new Range(m_endContainer->getDocument(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
468         
469     return 0;
470 }
471
472 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
473 {
474 }
475
476 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range *r)
477 {
478     m_positionNode = 0;
479
480     if (!r)
481         return;
482
483     int exception = 0;
484     Node *startNode = r->startContainer(exception);
485     if (exception)
486         return;
487     Node *endNode = r->endContainer(exception);
488     if (exception)
489         return;
490     int startOffset = r->startOffset(exception);
491     if (exception)
492         return;
493     int endOffset = r->endOffset(exception);
494     if (exception)
495         return;
496
497     if (!startNode->offsetInCharacters()) {
498         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
499             startNode = startNode->childNode(startOffset);
500             startOffset = 0;
501         }
502     }
503     if (!endNode->offsetInCharacters()) {
504         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {
505             endNode = endNode->childNode(endOffset - 1);
506             endOffset = endNode->hasChildNodes() ? endNode->childNodeCount() : endNode->maxOffset();
507         }
508     }
509
510     m_node = endNode;
511     m_offset = endOffset;
512     m_handledNode = false;
513     m_handledChildren = endOffset == 0;
514
515     m_startNode = startNode;
516     m_startOffset = startOffset;
517
518 #ifndef NDEBUG
519     // Need this just because of the assert.
520     m_positionNode = endNode;
521 #endif
522
523     m_lastTextNode = 0;
524     m_lastCharacter = '\n';
525
526     advance();
527 }
528
529 void SimplifiedBackwardsTextIterator::advance()
530 {
531     assert(m_positionNode);
532
533     m_positionNode = 0;
534     m_textLength = 0;
535
536     while (m_node) {
537         if (!m_handledNode) {
538             RenderObject *renderer = m_node->renderer();
539             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
540                 // FIXME: What about CDATA_SECTION_NODE?
541                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
542                     m_handledNode = handleTextNode();
543             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
544                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
545                     m_handledNode = handleReplacedElement();
546             } else
547                 m_handledNode = handleNonTextNode();
548             if (m_positionNode)
549                 return;
550         }
551
552         if (m_node == m_startNode)
553             return;
554
555         Node *next = 0;
556         if (!m_handledChildren) {
557             next = m_node->lastChild();
558             while (next && next->lastChild())
559                 next = next->lastChild();
560             m_handledChildren = true;
561         }
562         if (!next && m_node != m_startNode) {
563             next = m_node->previousSibling();
564             if (next) {
565                 exitNode();
566                 while (next->lastChild())
567                     next = next->lastChild();
568             }
569             else if (m_node->parentNode()) {
570                 next = m_node->parentNode();
571                 exitNode();
572             }
573         }
574         
575         // Check for leaving a node and iterating backwards
576         // into a different block that is an descendent of the
577         // block containing the node (as in leaving
578         // the "bar" node in this example: <p>foo</p>bar).
579         // Must emit newline when leaving node containing "bar".
580         if (next && m_node->renderer() && m_node->renderer()->style()->visibility() == VISIBLE) {
581             Node *block = m_node->enclosingBlockFlowElement();
582             if (block) {
583                 Node *nextBlock = next->enclosingBlockFlowElement();
584                 if (nextBlock && nextBlock->isAncestor(block))
585                     emitNewlineForBROrText();
586             }
587         }
588         
589         m_node = next;
590         if (m_node)
591             m_offset = m_node->caretMaxOffset();
592         else
593             m_offset = 0;
594         m_handledNode = false;
595         
596         if (m_positionNode)
597             return;
598     }
599 }
600
601 bool SimplifiedBackwardsTextIterator::handleTextNode()
602 {
603     m_lastTextNode = m_node;
604
605     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
606     String str = m_node->nodeValue();
607
608     if (!renderer->firstTextBox() && str.length() > 0)
609         return true;
610
611     m_positionEndOffset = m_offset;
612
613     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
614     m_positionNode = m_node;
615     m_positionStartOffset = m_offset;
616     m_textLength = m_positionEndOffset - m_positionStartOffset;
617     m_textCharacters = str.unicode() + m_positionStartOffset;
618
619     m_lastCharacter = str[m_positionEndOffset - 1];
620
621     return true;
622 }
623
624 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
625 {
626     int offset = m_node->nodeIndex();
627
628     m_positionNode = m_node->parentNode();
629     m_positionStartOffset = offset;
630     m_positionEndOffset = offset + 1;
631
632     m_textCharacters = 0;
633     m_textLength = 0;
634
635     m_lastCharacter = 0;
636
637     return true;
638 }
639
640 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
641 {
642     if (m_node->hasTagName(brTag))
643         emitNewlineForBROrText();
644     else if (m_node->hasTagName(tdTag) || m_node->hasTagName(thTag) ||
645              m_node->hasTagName(blockquoteTag) || m_node->hasTagName(ddTag) ||
646              m_node->hasTagName(divTag) ||
647              m_node->hasTagName(dlTag) || m_node->hasTagName(dtTag) || 
648              m_node->hasTagName(h1Tag) || m_node->hasTagName(h2Tag) ||
649              m_node->hasTagName(h3Tag) || m_node->hasTagName(h4Tag) ||
650              m_node->hasTagName(h5Tag) || m_node->hasTagName(h6Tag) ||
651              m_node->hasTagName(hrTag) || m_node->hasTagName(liTag) ||
652              m_node->hasTagName(olTag) || m_node->hasTagName(pTag) ||
653              m_node->hasTagName(preTag) || m_node->hasTagName(trTag) ||
654              m_node->hasTagName(ulTag)) {
655         // Emit a space to "break up" content. Any word break
656         // character will do.
657         emitCharacter(' ', m_node, 0, 0);
658     }
659
660     return true;
661 }
662
663 void SimplifiedBackwardsTextIterator::exitNode()
664 {
665     // Left this function in so that the name and usage patters remain similar to 
666     // TextIterator. However, the needs of this iterator are much simpler, and
667     // the handleNonTextNode() function does just what we want (i.e. insert a
668     // space for certain node types to "break up" text so that it does not seem
669     // like content is next to other text when it really isn't). 
670     handleNonTextNode();
671 }
672
673 void SimplifiedBackwardsTextIterator::emitCharacter(QChar c, Node *node, int startOffset, int endOffset)
674 {
675     m_singleCharacterBuffer = c;
676     m_positionNode = node;
677     m_positionStartOffset = startOffset;
678     m_positionEndOffset = endOffset;
679     m_textCharacters = &m_singleCharacterBuffer;
680     m_textLength = 1;
681     m_lastCharacter = c;
682 }
683
684 void SimplifiedBackwardsTextIterator::emitNewlineForBROrText()
685 {
686     int offset;
687     
688     if (m_lastTextNode) {
689         offset = m_lastTextNode->nodeIndex();
690         emitCharacter('\n', m_lastTextNode->parentNode(), offset, offset + 1);
691     } else {
692         offset = m_node->nodeIndex();
693         emitCharacter('\n', m_node->parentNode(), offset, offset + 1);
694     }
695 }
696
697 PassRefPtr<Range> SimplifiedBackwardsTextIterator::range() const
698 {
699     if (m_positionNode)
700         return new Range(m_positionNode->getDocument(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
701     
702     return new Range(m_startNode->getDocument(), m_startNode, m_startOffset, m_startNode, m_startOffset);
703 }
704
705 CharacterIterator::CharacterIterator()
706     : m_offset(0), m_runOffset(0), m_atBreak(true)
707 {
708 }
709
710 CharacterIterator::CharacterIterator(const Range *r)
711     : m_offset(0), m_runOffset(0), m_atBreak(true), m_textIterator(r, RUNFINDER)
712 {
713     while (!atEnd() && m_textIterator.length() == 0) {
714         m_textIterator.advance();
715     }
716 }
717
718 PassRefPtr<Range> CharacterIterator::range() const
719 {
720     RefPtr<Range> r = m_textIterator.range();
721     if (!m_textIterator.atEnd()) {
722         if (m_textIterator.length() <= 1) {
723             assert(m_runOffset == 0);
724         } else {
725             int exception = 0;
726             Node *n = r->startContainer(exception);
727             assert(n == r->endContainer(exception));
728             int offset = r->startOffset(exception) + m_runOffset;
729             r->setStart(n, offset, exception);
730             r->setEnd(n, offset + 1, exception);
731         }
732     }
733     return r.release();
734 }
735
736 void CharacterIterator::advance(int count)
737 {
738     m_atBreak = false;
739
740     // easy if there is enough left in the current m_textIterator run
741     int remaining = m_textIterator.length() - m_runOffset;
742     if (count < remaining) {
743         m_runOffset += count;
744         m_offset += count;
745         return;
746     }
747
748     // exhaust the current m_textIterator run
749     count -= remaining;
750     m_offset += remaining;
751     
752     // move to a subsequent m_textIterator run
753     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
754         int runLength = m_textIterator.length();
755         if (runLength == 0)
756             m_atBreak = true;
757         else {
758             // see whether this is m_textIterator to use
759             if (count < runLength) {
760                 m_runOffset = count;
761                 m_offset += count;
762                 return;
763             }
764             
765             // exhaust this m_textIterator run
766             count -= runLength;
767             m_offset += runLength;
768         }
769     }
770
771     // ran to the end of the m_textIterator... no more runs left
772     m_atBreak = true;
773     m_runOffset = 0;
774 }
775
776 DeprecatedString CharacterIterator::string(int numChars)
777 {
778     DeprecatedString result;
779     result.reserve(numChars);
780     while (numChars > 0 && !atEnd()) {
781         int runSize = kMin(numChars, length());
782         result.append(characters(), runSize);
783         numChars -= runSize;
784         advance(runSize);
785     }
786     return result;
787 }
788
789 WordAwareIterator::WordAwareIterator()
790 : m_previousText(0), m_didLookAhead(false)
791 {
792 }
793
794 WordAwareIterator::WordAwareIterator(const Range *r)
795 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
796 {
797     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
798     advance();              // get in position over the first chunk of text
799 }
800
801 // We're always in one of these modes:
802 // - The current chunk in the text iterator is our current chunk
803 //      (typically its a piece of whitespace, or text that ended with whitespace)
804 // - The previous chunk in the text iterator is our current chunk
805 //      (we looked ahead to the next chunk and found a word boundary)
806 // - We built up our own chunk of text from many chunks from the text iterator
807
808 //FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
809
810 void WordAwareIterator::advance()
811 {
812     m_previousText = 0;
813     m_buffer = "";      // toss any old buffer we built up
814
815     // If last time we did a look-ahead, start with that looked-ahead chunk now
816     if (!m_didLookAhead) {
817         assert(!m_textIterator.atEnd());
818         m_textIterator.advance();
819     }
820     m_didLookAhead = false;
821
822     // Go to next non-empty chunk 
823     while (!m_textIterator.atEnd() && m_textIterator.length() == 0) {
824         m_textIterator.advance();
825     }
826     m_range = m_textIterator.range();
827
828     if (m_textIterator.atEnd())
829         return;
830     
831     while (1) {
832         // If this chunk ends in whitespace we can just use it as our chunk.
833         if (m_textIterator.characters()[m_textIterator.length()-1].isSpace())
834             return;
835
836         // If this is the first chunk that failed, save it in previousText before look ahead
837         if (m_buffer.isEmpty()) {
838             m_previousText = m_textIterator.characters();
839             m_previousLength = m_textIterator.length();
840         }
841
842         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
843         m_textIterator.advance();
844         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || m_textIterator.characters()[0].isSpace()) {
845             m_didLookAhead = true;
846             return;
847         }
848
849         if (m_buffer.isEmpty()) {
850             // Start gobbling chunks until we get to a suitable stopping point
851             m_buffer.append(m_previousText, m_previousLength);
852             m_previousText = 0;
853         }
854         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
855         int exception = 0;
856         m_range->setEnd(m_textIterator.range()->endContainer(exception), m_textIterator.range()->endOffset(exception), exception);
857     }
858 }
859
860 int WordAwareIterator::length() const
861 {
862     if (!m_buffer.isEmpty())
863         return m_buffer.length();
864     else if (m_previousText)
865         return m_previousLength;
866     else
867         return m_textIterator.length();
868 }
869
870 const QChar *WordAwareIterator::characters() const
871 {
872     if (!m_buffer.isEmpty())
873         return m_buffer.unicode();
874     else if (m_previousText)
875         return m_previousText;
876     else
877         return m_textIterator.characters();
878 }
879
880 CircularSearchBuffer::CircularSearchBuffer(const String& s, bool isCaseSensitive)
881     : m_target(s)
882 {
883     assert(!s.isEmpty());
884
885     if (!isCaseSensitive)
886         m_target = s.lower();
887     m_target.replace(nonBreakingSpace, ' ');
888     m_isCaseSensitive = isCaseSensitive;
889
890     m_buffer = static_cast<QChar *>(fastMalloc(s.length() * sizeof(QChar)));
891     m_cursor = m_buffer;
892     m_bufferFull = false;
893 }
894
895 void CircularSearchBuffer::append(const QChar &c)
896 {
897     if (m_isCaseSensitive)
898         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
899     else
900         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
901     if (m_cursor == m_buffer + length()) {
902         m_cursor = m_buffer;
903         m_bufferFull = true;
904     }
905 }
906
907 // This function can only be used when the buffer is not yet full,
908 // and when then count is small enough to fit in the buffer.
909 // No need for a more general version for the search algorithm.
910 void CircularSearchBuffer::append(int count, const QChar *characters)
911 {
912     int tailSpace = m_buffer + length() - m_cursor;
913
914     assert(!m_bufferFull);
915     assert(count <= tailSpace);
916
917     if (m_isCaseSensitive) {
918         for (int i = 0; i != count; ++i) {
919             QChar c = characters[i];
920             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
921         }
922     } else {
923         for (int i = 0; i != count; ++i) {
924             QChar c = characters[i];
925             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
926         }
927     }
928     if (count < tailSpace)
929         m_cursor += count;
930     else {
931         m_bufferFull = true;
932         m_cursor = m_buffer;
933     }
934 }
935
936 int CircularSearchBuffer::neededCharacters() const
937 {
938     return m_bufferFull ? 0 : m_buffer + length() - m_cursor;
939 }
940
941 bool CircularSearchBuffer::isMatch() const
942 {
943     assert(m_bufferFull);
944
945     int headSpace = m_cursor - m_buffer;
946     int tailSpace = length() - headSpace;
947     return memcmp(m_cursor, m_target.unicode(), tailSpace * sizeof(QChar)) == 0
948         && memcmp(m_buffer, m_target.unicode() + tailSpace, headSpace * sizeof(QChar)) == 0;
949 }
950
951 int TextIterator::rangeLength(const Range *r)
952 {
953     int length = 0;
954     for (TextIterator it(r); !it.atEnd(); it.advance()) {
955         length += it.length();
956     }
957     return length;
958 }
959
960 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Document *doc, int rangeLocation, int rangeLength)
961 {
962     RefPtr<Range> resultRange = doc->createRange();
963
964     int docTextPosition = 0;
965     int rangeEnd = rangeLocation + rangeLength;
966     bool startRangeFound = false;
967
968     RefPtr<Range> textRunRange;
969
970     TextIterator it(rangeOfContents(doc).get());
971     
972     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugzilla.opendarwin.org/show_bug.cgi?id=6289>.
973     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
974         int exception = 0;
975         textRunRange = it.range();
976         
977         resultRange->setStart(textRunRange->startContainer(exception), 0, exception);
978         assert(exception == 0);
979         resultRange->setEnd(textRunRange->startContainer(exception), 0, exception);
980         assert(exception == 0);
981         
982         return resultRange.release();
983     }
984
985     for (; !it.atEnd(); it.advance()) {
986         int len = it.length();
987         textRunRange = it.range();
988
989         if (rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len) {
990             startRangeFound = true;
991             int exception = 0;
992             if (textRunRange->startContainer(exception)->isTextNode()) {
993                 int offset = rangeLocation - docTextPosition;
994                 resultRange->setStart(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
995             } else {
996                 if (rangeLocation == docTextPosition)
997                     resultRange->setStart(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
998                 else
999                     resultRange->setStart(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1000             }
1001         }
1002
1003         if (rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len) {
1004             int exception = 0;
1005             if (textRunRange->startContainer(exception)->isTextNode()) {
1006                 int offset = rangeEnd - docTextPosition;
1007                 resultRange->setEnd(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
1008             } else {
1009                 if (rangeEnd == docTextPosition)
1010                     resultRange->setEnd(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
1011                 else
1012                     resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1013             }
1014             if (!(rangeLength == 0 && rangeEnd == docTextPosition + len)) {
1015                 docTextPosition += len;
1016                 break;
1017             }
1018         }
1019         docTextPosition += len;
1020     }
1021     
1022     if (!startRangeFound)
1023         return 0;
1024     
1025     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1026         int exception = 0;
1027         resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1028     }
1029     
1030     return resultRange.release();
1031 }
1032
1033 DeprecatedString plainText(const Range *r)
1034 {
1035     DeprecatedString result("");
1036     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1037         result.append(it.characters(), it.length());
1038     }
1039     return result;
1040 }
1041
1042 PassRefPtr<Range> findPlainText(const Range *r, const String& s, bool forward, bool caseSensitive)
1043 {
1044     // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
1045
1046     // FIXME: This code does not allow \n at the moment because of issues with <br>.
1047     // Once we fix those, we can remove this check.
1048     if (s.isEmpty() || s.find('\n') != -1) {
1049         int exception = 0;
1050         RefPtr<Range> result = r->cloneRange(exception);
1051         result->collapse(forward, exception);
1052         return result.release();
1053     }
1054
1055     CircularSearchBuffer buffer(s, caseSensitive);
1056
1057     bool found = false;
1058     CharacterIterator rangeEnd;
1059
1060     {
1061         CharacterIterator it(r);
1062         while (1) {
1063             // Fill the buffer.
1064             while (int needed = buffer.neededCharacters()) {
1065                 if (it.atBreak()) {
1066                     if (it.atEnd())
1067                         goto done;
1068                     buffer.clear();
1069                 }
1070                 int available = it.length();
1071                 int runLength = kMin(needed, available);
1072                 buffer.append(runLength, it.characters());
1073                 it.advance(runLength);
1074             }
1075
1076             // Do the search.
1077             while (1) {
1078                 if (buffer.isMatch()) {
1079                     // Compute the range for the result.
1080                     found = true;
1081                     rangeEnd = it;
1082                     // If searching forward, stop on the first match.
1083                     // If searching backward, don't stop, so we end up with the last match.
1084                     if (forward)
1085                         goto done;
1086                 }
1087                 if (it.atBreak())
1088                     break;
1089                 buffer.append(it.characters()[0]);
1090                 it.advance(1);
1091             }
1092             buffer.clear();
1093         }
1094     }
1095
1096 done:
1097     int exception = 0;
1098     RefPtr<Range> result = r->cloneRange(exception);
1099     if (!found)
1100         result->collapse(!forward, exception);
1101     else {
1102         CharacterIterator it(r);
1103         it.advance(rangeEnd.characterOffset() - buffer.length());
1104         result->setStart(it.range()->startContainer(exception), it.range()->startOffset(exception), exception);
1105         it.advance(buffer.length() - 1);
1106         result->setEnd(it.range()->endContainer(exception), it.range()->endOffset(exception), exception);
1107     }
1108     return result.release();
1109 }
1110
1111 }