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