9df66ad99a8492bac263c1856bcfd613a2c5d866
[WebKit-https.git] / WebCore / khtml / editing / visible_text.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 "visible_text.h"
29
30 #include "htmlnames.h"
31 #include "rendering/render_text.h"
32 #include "xml/dom_nodeimpl.h"
33 #include "xml/dom_position.h"
34 #include "xml/dom2_rangeimpl.h"
35
36 using namespace DOM::HTMLNames;
37
38 using DOM::DocumentImpl;
39 using DOM::DOMString;
40 using DOM::Node;
41 using DOM::NodeImpl;
42 using DOM::offsetInCharacters;
43 using DOM::RangeImpl;
44
45 // FIXME: These classes should probably use the render tree and not the DOM tree, since elements could
46 // be hidden using CSS, or additional generated content could be added.  For now, we just make sure
47 // text objects walk their renderers' InlineTextBox objects, so that we at least get the whitespace 
48 // stripped out properly and obey CSS visibility for text runs.
49
50 namespace khtml {
51
52 const unsigned short nonBreakingSpace = 0xA0;
53
54 // Buffer that knows how to compare with a search target.
55 // Keeps enough of the previous text to be able to search in the future,
56 // but no more.
57 class CircularSearchBuffer {
58 public:
59     CircularSearchBuffer(const QString &target, bool isCaseSensitive);
60     ~CircularSearchBuffer() { fastFree(m_buffer); }
61
62     void clear() { m_cursor = m_buffer; m_bufferFull = false; }
63     void append(int length, const QChar *characters);
64     void append(const QChar &);
65
66     int neededCharacters() const;
67     bool isMatch() const;
68     int length() const { return m_target.length(); }
69
70 private:
71     QString m_target;
72     bool m_isCaseSensitive;
73
74     QChar *m_buffer;
75     QChar *m_cursor;
76     bool m_bufferFull;
77
78     CircularSearchBuffer(const CircularSearchBuffer&);
79     CircularSearchBuffer &operator=(const CircularSearchBuffer&);
80 };
81
82 TextIterator::TextIterator() : m_endContainer(0), m_endOffset(0), m_positionNode(0)
83 {
84 }
85
86 TextIterator::TextIterator(const RangeImpl *r, IteratorKind kind) : m_endContainer(0), m_endOffset(0), m_positionNode(0)
87 {
88     if (!r)
89         return;
90
91     int exceptionCode = 0;
92
93     // get and validate the range endpoints
94     NodeImpl *startContainer = r->startContainer(exceptionCode);
95     int startOffset = r->startOffset(exceptionCode);
96     NodeImpl *endContainer = r->endContainer(exceptionCode);
97     int endOffset = r->endOffset(exceptionCode);
98     if (exceptionCode != 0)
99         return;
100
101     // remember ending place - this does not change
102     m_endContainer = endContainer;
103     m_endOffset = endOffset;
104
105     // set up the current node for processing
106     m_node = r->startNode();
107     if (m_node == 0)
108         return;
109     m_offset = m_node == startContainer ? startOffset : 0;
110     m_handledNode = false;
111     m_handledChildren = false;
112
113     // calculate first out of bounds node
114     m_pastEndNode = r->pastEndNode();
115
116     // initialize node processing state
117     m_needAnotherNewline = false;
118     m_textBox = 0;
119
120     // initialize record of previous node processing
121     m_lastTextNode = 0;
122     m_lastTextNodeEndedWithCollapsedSpace = false;
123     if (kind == RUNFINDER)
124         m_lastCharacter = 0;
125     else
126         m_lastCharacter = '\n';
127
128 #ifndef NDEBUG
129     // need this just because of the assert in advance()
130     m_positionNode = m_node;
131 #endif
132
133     // identify the first run
134     advance();
135 }
136
137 void TextIterator::advance()
138 {
139     // otherwise, where are we advancing from?
140     assert(m_positionNode);
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
162     while (m_node && m_node != m_pastEndNode) {
163         // handle current node according to its type
164         if (!m_handledNode) {
165             RenderObject *renderer = m_node->renderer();
166             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
167                 // FIXME: What about CDATA_SECTION_NODE?
168                 if (renderer->style()->visibility() == VISIBLE) {
169                     m_handledNode = handleTextNode();
170                 }
171             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
172                 if (renderer->style()->visibility() == VISIBLE) {
173                     m_handledNode = handleReplacedElement();
174                 }
175             } else {
176                 m_handledNode = handleNonTextNode();
177             }
178             if (m_positionNode) {
179                 return;
180             }
181         }
182
183         // find a new current node to handle in depth-first manner,
184         // calling exitNode() as we come back thru a parent node
185         NodeImpl *next = m_handledChildren ? 0 : m_node->firstChild();
186         m_offset = 0;
187         if (!next) {
188             next = m_node->nextSibling();
189             if (!next) {
190                 if (m_node->traverseNextNode() == m_pastEndNode)
191                     break;
192                 while (!next && m_node->parentNode()) {
193                     m_node = m_node->parentNode();
194                     exitNode();
195                     if (m_positionNode) {
196                         m_handledNode = true;
197                         m_handledChildren = true;
198                         return;
199                     }
200                     next = m_node->nextSibling();
201                 }
202             }
203         }
204
205         // set the new current node
206         m_node = next;
207         m_handledNode = false;
208         m_handledChildren = false;
209
210         // how would this ever be?
211         if (m_positionNode) {
212             return;
213         }
214     }
215 }
216
217 bool TextIterator::handleTextNode()
218 {
219     m_lastTextNode = m_node;
220
221     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
222     DOMString str = renderer->string();
223
224     // handle pre-formatted text
225     if (!renderer->style()->collapseWhiteSpace()) {
226         int runStart = m_offset;
227         if (m_lastTextNodeEndedWithCollapsedSpace) {
228             emitCharacter(' ', m_node, 0, runStart, runStart);
229             return false;
230         }
231         int strLength = str.length();
232         int end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
233         int runEnd = kMin(strLength, end);
234
235         if (runStart >= runEnd)
236             return true;
237
238         m_positionNode = m_node;
239         m_positionOffsetBaseNode = 0;
240         m_positionStartOffset = runStart;
241         m_positionEndOffset = runEnd;
242         m_textCharacters = str.unicode() + runStart;
243         m_textLength = runEnd - runStart;
244
245         m_lastCharacter = str[runEnd - 1];
246
247         return true;
248     }
249
250     if (!renderer->firstTextBox() && str.length() > 0) {
251         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
252         return true;
253     }
254
255     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
256     if (renderer->containsReversedText()) {
257         m_sortedTextBoxes.clear();
258         for (InlineTextBox * textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
259             m_sortedTextBoxes.append(textBox);
260         }
261         m_sortedTextBoxes.sort(); 
262     }
263     
264     m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes.first() : renderer->firstTextBox();
265     handleTextBox();
266     return true;
267 }
268
269 void TextIterator::handleTextBox()
270 {    
271     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
272     DOMString str = renderer->string();
273     int start = m_offset;
274     int end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
275     while (m_textBox) {
276         int textBoxStart = m_textBox->m_start;
277         int runStart = kMax(textBoxStart, start);
278
279         // Check for collapsed space at the start of this run.
280         InlineTextBox *firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes.getFirst() : renderer->firstTextBox();
281         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
282             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
283         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && !m_lastCharacter.isNull()) {
284             emitCharacter(' ', m_node, 0, runStart, runStart);
285             return;
286         }
287         int textBoxEnd = textBoxStart + m_textBox->m_len;
288         int runEnd = kMin(textBoxEnd, end);
289         
290         // Determine what the next text box will be, but don't advance yet
291         InlineTextBox *nextTextBox = renderer->containsReversedText() ? m_sortedTextBoxes.getNext() : m_textBox->nextTextBox();
292
293         if (runStart < runEnd) {
294             // Handle either a single newline character (which becomes a space),
295             // or a run of characters that does not include a newline.
296             // This effectively translates newlines to spaces without copying the text.
297             if (str[runStart] == '\n') {
298                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
299                 m_offset = runStart + 1;
300             } else {
301                 int subrunEnd = str.find('\n', runStart);
302                 if (subrunEnd == -1 || subrunEnd > runEnd) {
303                     subrunEnd = runEnd;
304                 }
305
306                 m_offset = subrunEnd;
307
308                 m_positionNode = m_node;
309                 m_positionOffsetBaseNode = 0;
310                 m_positionStartOffset = runStart;
311                 m_positionEndOffset = subrunEnd;
312                 m_textCharacters = str.unicode() + runStart;
313                 m_textLength = subrunEnd - runStart;
314
315                 m_lastTextNodeEndedWithCollapsedSpace = false;
316                 m_lastCharacter = str[subrunEnd - 1];
317             }
318
319             // If we are doing a subrun that doesn't go to the end of the text box,
320             // come back again to finish handling this text box; don't advance to the next one.
321             if (m_positionEndOffset < textBoxEnd) {
322                 return;
323             }
324
325             // Advance and return
326             int nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();
327             if (nextRunStart > runEnd) {
328                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
329             }
330             m_textBox = nextTextBox;
331             if (renderer->containsReversedText())
332                 m_sortedTextBoxes.next();
333             return;
334         }
335         // Advance and continue
336         m_textBox = nextTextBox;
337         if (renderer->containsReversedText())
338             m_sortedTextBoxes.next();
339     }
340 }
341
342 bool TextIterator::handleReplacedElement()
343 {
344     if (m_lastTextNodeEndedWithCollapsedSpace) {
345         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
346         return false;
347     }
348
349     m_positionNode = m_node->parentNode();
350     m_positionOffsetBaseNode = m_node;
351     m_positionStartOffset = 0;
352     m_positionEndOffset = 1;
353
354     m_textCharacters = 0;
355     m_textLength = 0;
356
357     m_lastCharacter = 0;
358
359     return true;
360 }
361
362 bool TextIterator::handleNonTextNode()
363 {
364     if (m_node->hasTagName(brTag)) {
365         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
366     } else if (m_node->hasTagName(tdTag) || m_node->hasTagName(thTag)) {
367         if (m_lastCharacter != '\n' && m_lastTextNode) {
368             emitCharacter('\t', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
369         }
370     } else if (m_node->hasTagName(blockquoteTag) || m_node->hasTagName(ddTag) ||
371                m_node->hasTagName(divTag) ||
372                m_node->hasTagName(dlTag) || m_node->hasTagName(dtTag) || 
373                m_node->hasTagName(h1Tag) || m_node->hasTagName(h2Tag) ||
374                m_node->hasTagName(h3Tag) || m_node->hasTagName(h4Tag) ||
375                m_node->hasTagName(h5Tag) || m_node->hasTagName(h6Tag) ||
376                m_node->hasTagName(hrTag) || m_node->hasTagName(liTag) ||
377                m_node->hasTagName(olTag) || m_node->hasTagName(pTag) ||
378                m_node->hasTagName(preTag) || m_node->hasTagName(trTag) ||
379                m_node->hasTagName(ulTag)) {
380         if (m_lastCharacter != '\n' && m_lastTextNode) {
381             emitCharacter('\n', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
382         }
383     }
384
385     return true;
386 }
387
388 void TextIterator::exitNode()
389 {
390     bool endLine = false;
391     bool addNewline = false;
392
393     if (m_node->hasTagName(blockquoteTag) || m_node->hasTagName(ddTag) ||
394                m_node->hasTagName(divTag) ||
395                m_node->hasTagName(dlTag) || m_node->hasTagName(dtTag) || 
396                m_node->hasTagName(hrTag) || m_node->hasTagName(liTag) ||
397                m_node->hasTagName(olTag) ||
398                m_node->hasTagName(preTag) || m_node->hasTagName(trTag) ||
399                m_node->hasTagName(ulTag))
400         endLine = true;
401     else if (m_node->hasTagName(h1Tag) || m_node->hasTagName(h2Tag) ||
402              m_node->hasTagName(h3Tag) || m_node->hasTagName(h4Tag) ||
403              m_node->hasTagName(h5Tag) || m_node->hasTagName(h6Tag) ||
404              m_node->hasTagName(pTag)) {
405         endLine = true;
406
407         // In certain cases, emit a new newline character for this node
408         // regardless of whether we emit another one.
409         // FIXME: Some day we could do this for other tags.
410         // However, doing it just for the tags above makes it more likely
411         // we'll end up getting the right result without margin collapsing.
412         // For example: <div><p>text</p></div> will work right even if both
413         // the <div> and the <p> have bottom margins.
414         RenderObject *renderer = m_node->renderer();
415         if (renderer) {
416             RenderStyle *style = renderer->style();
417             if (style) {
418                 int bottomMargin = renderer->collapsedMarginBottom();
419                 int fontSize = style->htmlFont().getFontDef().computedPixelSize();
420                 if (bottomMargin * 2 >= fontSize) {
421                     addNewline = true;
422                 }
423             }
424         }
425     }
426
427     // emit character(s) iff there is an earlier text node and we need at least one newline
428     if (m_lastTextNode && endLine) {
429         if (m_lastCharacter != '\n') {
430             // insert a newline with a position following this block
431             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
432
433             //...and, if needed, set flag to later add a newline for the current node
434             assert(!m_needAnotherNewline);
435             m_needAnotherNewline = addNewline;
436         } else if (addNewline) {
437             // insert a newline with a position following this block
438             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
439         }
440     }
441 }
442
443 void TextIterator::emitCharacter(QChar c, NodeImpl *textNode, NodeImpl *offsetBaseNode, int textStartOffset, int textEndOffset)
444 {
445     // remember information with which to construct the TextIterator::range()
446     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
447     m_positionNode = textNode;
448     m_positionOffsetBaseNode = offsetBaseNode;
449     m_positionStartOffset = textStartOffset;
450     m_positionEndOffset = textEndOffset;
451  
452     // remember information with which to construct the TextIterator::characters() and length()
453     m_singleCharacterBuffer = c;
454     m_textCharacters = &m_singleCharacterBuffer;
455     m_textLength = 1;
456
457     // remember some iteration state
458     m_lastTextNodeEndedWithCollapsedSpace = false;
459     m_lastCharacter = c;
460 }
461
462 RefPtr<RangeImpl> TextIterator::range() const
463 {
464     // use the current run information, if we have it
465     if (m_positionNode) {
466         if (m_positionOffsetBaseNode) {
467             int index = m_positionOffsetBaseNode->nodeIndex();
468             m_positionStartOffset += index;
469             m_positionEndOffset += index;
470             m_positionOffsetBaseNode = 0;
471         }
472         return RefPtr<RangeImpl>(new RangeImpl(m_positionNode->getDocument(),
473             m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset));
474     }
475
476     // otherwise, return the end of the overall range we were given
477     if (m_endContainer)
478         return RefPtr<RangeImpl>(new RangeImpl(m_endContainer->getDocument(), 
479             m_endContainer, m_endOffset, m_endContainer, m_endOffset));
480         
481     return RefPtr<RangeImpl>();
482 }
483
484 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
485 {
486 }
487
488 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const RangeImpl *r)
489 {
490     m_positionNode = 0;
491
492     if (!r)
493         return;
494
495     int exception = 0;
496     NodeImpl *startNode = r->startContainer(exception);
497     if (exception)
498         return;
499     NodeImpl *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 (!offsetInCharacters(startNode->nodeType())) {
510         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
511             startNode = startNode->childNode(startOffset);
512             startOffset = 0;
513         }
514     }
515     if (!offsetInCharacters(endNode->nodeType())) {
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         NodeImpl *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             NodeImpl *block = m_node->enclosingBlockFlowElement();
598             if (block) {
599                 NodeImpl *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     DOMString 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, NodeImpl *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 RefPtr<RangeImpl> SimplifiedBackwardsTextIterator::range() const
716 {
717     if (m_positionNode) {
718         return RefPtr<RangeImpl>(new RangeImpl(m_positionNode->getDocument(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset));
719     } else {
720         return RefPtr<RangeImpl>(new RangeImpl(m_startNode->getDocument(), m_startNode, m_startOffset, m_startNode, m_startOffset));
721     }
722 }
723
724 CharacterIterator::CharacterIterator()
725     : m_offset(0), m_runOffset(0), m_atBreak(true)
726 {
727 }
728
729 CharacterIterator::CharacterIterator(const RangeImpl *r)
730     : m_offset(0), m_runOffset(0), m_atBreak(true), m_textIterator(r, RUNFINDER)
731 {
732     while (!atEnd() && m_textIterator.length() == 0) {
733         m_textIterator.advance();
734     }
735 }
736
737 RefPtr<RangeImpl> CharacterIterator::range() const
738 {
739     RefPtr<RangeImpl> r = m_textIterator.range();
740     if (!m_textIterator.atEnd()) {
741         if (m_textIterator.length() <= 1) {
742             assert(m_runOffset == 0);
743         } else {
744             int exception = 0;
745             NodeImpl *n = r->startContainer(exception);
746             assert(n == r->endContainer(exception));
747             int offset = r->startOffset(exception) + m_runOffset;
748             r->setStart(n, offset, exception);
749             r->setEnd(n, offset + 1, exception);
750         }
751     }
752     return r;
753 }
754
755 void CharacterIterator::advance(int count)
756 {
757     assert(!atEnd());
758
759     m_atBreak = false;
760
761     // easy if there is enough left in the current m_textIterator run
762     int remaining = m_textIterator.length() - m_runOffset;
763     if (count < remaining) {
764         m_runOffset += count;
765         m_offset += count;
766         return;
767     }
768
769     // exhaust the current m_textIterator run
770     count -= remaining;
771     m_offset += remaining;
772     
773     // move to a subsequent m_textIterator run
774     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
775         int runLength = m_textIterator.length();
776         if (runLength == 0) {
777             m_atBreak = true;
778         } else {
779             // see whether this is m_textIterator to use
780             if (count < runLength) {
781                 m_runOffset = count;
782                 m_offset += count;
783                 return;
784             }
785             
786             // exhaust this m_textIterator run
787             count -= runLength;
788             m_offset += runLength;
789         }
790     }
791
792     // ran to the end of the m_textIterator... no more runs left
793     m_atBreak = true;
794     m_runOffset = 0;
795 }
796
797 QString CharacterIterator::string(int numChars)
798 {
799     QString result;
800     result.reserve(numChars);
801     while (numChars > 0 && !atEnd()) {
802         int runSize = kMin(numChars, length());
803         result.append(characters(), runSize);
804         numChars -= runSize;
805         advance(runSize);
806     }
807     return result;
808 }
809
810 WordAwareIterator::WordAwareIterator()
811 : m_previousText(0), m_didLookAhead(false)
812 {
813 }
814
815 WordAwareIterator::WordAwareIterator(const RangeImpl *r)
816 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
817 {
818     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
819     advance();              // get in position over the first chunk of text
820 }
821
822 // We're always in one of these modes:
823 // - The current chunk in the text iterator is our current chunk
824 //      (typically its a piece of whitespace, or text that ended with whitespace)
825 // - The previous chunk in the text iterator is our current chunk
826 //      (we looked ahead to the next chunk and found a word boundary)
827 // - We built up our own chunk of text from many chunks from the text iterator
828
829 //FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
830
831 void WordAwareIterator::advance()
832 {
833     m_previousText = 0;
834     m_buffer = "";      // toss any old buffer we built up
835
836     // If last time we did a look-ahead, start with that looked-ahead chunk now
837     if (!m_didLookAhead) {
838         assert(!m_textIterator.atEnd());
839         m_textIterator.advance();
840     }
841     m_didLookAhead = false;
842
843     // Go to next non-empty chunk 
844     while (!m_textIterator.atEnd() && m_textIterator.length() == 0) {
845         m_textIterator.advance();
846     }
847     m_range = m_textIterator.range();
848
849     if (m_textIterator.atEnd()) {
850         return;
851     }
852     
853     while (1) {
854         // If this chunk ends in whitespace we can just use it as our chunk.
855         if (m_textIterator.characters()[m_textIterator.length()-1].isSpace()) {
856             return;
857         }
858
859         // If this is the first chunk that failed, save it in previousText before look ahead
860         if (m_buffer.isEmpty()) {
861             m_previousText = m_textIterator.characters();
862             m_previousLength = m_textIterator.length();
863         }
864
865         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
866         m_textIterator.advance();
867         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || m_textIterator.characters()[0].isSpace()) {
868             m_didLookAhead = true;
869             return;
870         }
871
872         if (m_buffer.isEmpty()) {
873             // Start gobbling chunks until we get to a suitable stopping point
874             m_buffer.append(m_previousText, m_previousLength);
875             m_previousText = 0;
876         }
877         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
878         int exception = 0;
879         m_range->setEnd(m_textIterator.range()->endContainer(exception),
880             m_textIterator.range()->endOffset(exception), exception);
881     }
882 }
883
884 int WordAwareIterator::length() const
885 {
886     if (!m_buffer.isEmpty()) {
887         return m_buffer.length();
888     } else if (m_previousText) {
889         return m_previousLength;
890     } else {
891         return m_textIterator.length();
892     }
893 }
894
895 const QChar *WordAwareIterator::characters() const
896 {
897     if (!m_buffer.isEmpty()) {
898         return m_buffer.unicode();
899     } else if (m_previousText) {
900         return m_previousText;
901     } else {
902         return m_textIterator.characters();
903     }
904 }
905
906 CircularSearchBuffer::CircularSearchBuffer(const QString &s, bool isCaseSensitive)
907     : m_target(s)
908 {
909     assert(!s.isEmpty());
910
911     if (!isCaseSensitive) {
912         m_target = s.lower();
913     }
914     m_target.replace(nonBreakingSpace, ' ');
915     m_isCaseSensitive = isCaseSensitive;
916
917     m_buffer = static_cast<QChar *>(fastMalloc(s.length() * sizeof(QChar)));
918     m_cursor = m_buffer;
919     m_bufferFull = false;
920 }
921
922 void CircularSearchBuffer::append(const QChar &c)
923 {
924     if (m_isCaseSensitive) {
925         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
926     } else {
927         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
928     }
929     if (m_cursor == m_buffer + length()) {
930         m_cursor = m_buffer;
931         m_bufferFull = true;
932     }
933 }
934
935 // This function can only be used when the buffer is not yet full,
936 // and when then count is small enough to fit in the buffer.
937 // No need for a more general version for the search algorithm.
938 void CircularSearchBuffer::append(int count, const QChar *characters)
939 {
940     int tailSpace = m_buffer + length() - m_cursor;
941
942     assert(!m_bufferFull);
943     assert(count <= tailSpace);
944
945     if (m_isCaseSensitive) {
946         for (int i = 0; i != count; ++i) {
947             QChar c = characters[i];
948             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
949         }
950     } else {
951         for (int i = 0; i != count; ++i) {
952             QChar c = characters[i];
953             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
954         }
955     }
956     if (count < tailSpace) {
957         m_cursor += count;
958     } else {
959         m_bufferFull = true;
960         m_cursor = m_buffer;
961     }
962 }
963
964 int CircularSearchBuffer::neededCharacters() const
965 {
966     return m_bufferFull ? 0 : m_buffer + length() - m_cursor;
967 }
968
969 bool CircularSearchBuffer::isMatch() const
970 {
971     assert(m_bufferFull);
972
973     int headSpace = m_cursor - m_buffer;
974     int tailSpace = length() - headSpace;
975     return memcmp(m_cursor, m_target.unicode(), tailSpace * sizeof(QChar)) == 0
976         && memcmp(m_buffer, m_target.unicode() + tailSpace, headSpace * sizeof(QChar)) == 0;
977 }
978
979 int TextIterator::rangeLength(const RangeImpl *r)
980 {
981     int length = 0;
982     for (TextIterator it(r); !it.atEnd(); it.advance()) {
983         length += it.length();
984     }
985     return length;
986 }
987
988 RangeImpl *TextIterator::rangeFromLocationAndLength(DocumentImpl *doc, int rangeLocation, int rangeLength)
989 {
990     RangeImpl *resultRange = doc->createRange();
991
992     int docTextPosition = 0;
993     int rangeEnd = rangeLocation + rangeLength;
994     bool startRangeFound = false;
995
996     RefPtr<RangeImpl> textRunRange;
997
998     TextIterator it(rangeOfContents(doc).get());
999     
1000     if (rangeLocation == 0 && rangeLength == 0) {
1001         int exception = 0;
1002         textRunRange = it.range();
1003         
1004         resultRange->setStart(textRunRange->startContainer(exception), 0, exception);
1005         assert(exception == 0);
1006         resultRange->setEnd(textRunRange->startContainer(exception), 0, exception);
1007         assert(exception == 0);
1008         
1009         return resultRange;
1010     }
1011
1012     for (; !it.atEnd(); it.advance()) {
1013         int len = it.length();
1014         textRunRange = it.range();
1015
1016         if (rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len) {
1017             startRangeFound = true;
1018             int exception = 0;
1019             if (textRunRange->startContainer(exception)->isTextNode()) {
1020                 int offset = rangeLocation - docTextPosition;
1021                 resultRange->setStart(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
1022             } else {
1023                 if (rangeLocation == docTextPosition) {
1024                     resultRange->setStart(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
1025                 } else {
1026                     resultRange->setStart(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1027                 }
1028             }
1029         }
1030
1031         if (rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len) {
1032             int exception = 0;
1033             if (textRunRange->startContainer(exception)->isTextNode()) {
1034                 int offset = rangeEnd - docTextPosition;
1035                 resultRange->setEnd(textRunRange->startContainer(exception), offset + textRunRange->startOffset(exception), exception);
1036             } else {
1037                 if (rangeEnd == docTextPosition) {
1038                     resultRange->setEnd(textRunRange->startContainer(exception), textRunRange->startOffset(exception), exception);
1039                 } else {
1040                     resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1041                 }
1042             }
1043             if (!(rangeLength == 0 && rangeEnd == docTextPosition + len)) {
1044                 docTextPosition += len;
1045                 break;
1046             }
1047         }
1048         docTextPosition += len;
1049     }
1050     
1051     if (!startRangeFound) {
1052         delete resultRange;
1053         return 0;
1054     }
1055     
1056     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1057         int exception = 0;
1058         resultRange->setEnd(textRunRange->endContainer(exception), textRunRange->endOffset(exception), exception);
1059     }
1060     
1061     return resultRange;
1062 }
1063
1064 QString plainText(const RangeImpl *r)
1065 {
1066     QString result("");
1067     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1068         result.append(it.characters(), it.length());
1069     }
1070     return result;
1071 }
1072
1073 RefPtr<RangeImpl> findPlainText(const RangeImpl *r, const QString &s, bool forward, bool caseSensitive)
1074 {
1075     // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
1076
1077     // FIXME: This code does not allow \n at the moment because of issues with <br>.
1078     // Once we fix those, we can remove this check.
1079     if (s.isEmpty() || s.find('\n') != -1) {
1080         int exception = 0;
1081         RangeImpl *result = r->cloneRange(exception);
1082         result->collapse(forward, exception);
1083         return RefPtr<RangeImpl>(result);
1084     }
1085
1086     CircularSearchBuffer buffer(s, caseSensitive);
1087
1088     bool found = false;
1089     CharacterIterator rangeEnd;
1090
1091     {
1092         CharacterIterator it(r);
1093         while (1) {
1094             // Fill the buffer.
1095             while (int needed = buffer.neededCharacters()) {
1096                 if (it.atBreak()) {
1097                     if (it.atEnd()) {
1098                         goto done;
1099                     }
1100                     buffer.clear();
1101                 }
1102                 int available = it.length();
1103                 int runLength = kMin(needed, available);
1104                 buffer.append(runLength, it.characters());
1105                 it.advance(runLength);
1106             }
1107
1108             // Do the search.
1109             while (1) {
1110                 if (buffer.isMatch()) {
1111                     // Compute the range for the result.
1112                     found = true;
1113                     rangeEnd = it;
1114                     // If searching forward, stop on the first match.
1115                     // If searching backward, don't stop, so we end up with the last match.
1116                     if (forward) {
1117                         goto done;
1118                     }
1119                 }
1120                 if (it.atBreak())
1121                     break;
1122                 buffer.append(it.characters()[0]);
1123                 it.advance(1);
1124             }
1125             buffer.clear();
1126         }
1127     }
1128
1129 done:
1130     int exception = 0;
1131     RangeImpl *result = r->cloneRange(exception);
1132     if (!found) {
1133         result->collapse(!forward, exception);
1134     } else {
1135         CharacterIterator it(r);
1136         it.advance(rangeEnd.characterOffset() - buffer.length());
1137         result->setStart(it.range()->startContainer(exception), it.range()->startOffset(exception), exception);
1138         it.advance(buffer.length() - 1);
1139         result->setEnd(it.range()->endContainer(exception), it.range()->endOffset(exception), exception);
1140     }
1141     return RefPtr<RangeImpl>(result);
1142 }
1143
1144 }