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