WebCore:
[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 "misc/htmltags.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::DOMString;
35 using DOM::Node;
36 using DOM::NodeImpl;
37 using DOM::offsetInCharacters;
38 using DOM::Range;
39 using DOM::RangeImpl;
40
41 // FIXME: These classes should probably use the render tree and not the DOM tree, since elements could
42 // be hidden using CSS, or additional generated content could be added.  For now, we just make sure
43 // text objects walk their renderers' InlineTextBox objects, so that we at least get the whitespace 
44 // stripped out properly and obey CSS visibility for text runs.
45
46 namespace khtml {
47
48 const unsigned short nonBreakingSpace = 0xA0;
49
50 // Buffer that knows how to compare with a search target.
51 // Keeps enough of the previous text to be able to search in the future,
52 // but no more.
53 class CircularSearchBuffer {
54 public:
55     CircularSearchBuffer(const QString &target, bool isCaseSensitive);
56     ~CircularSearchBuffer() { free(m_buffer); }
57
58     void clear() { m_cursor = m_buffer; m_bufferFull = false; }
59     void append(long length, const QChar *characters);
60     void append(const QChar &);
61
62     long neededCharacters() const;
63     bool isMatch() const;
64     long length() const { return m_target.length(); }
65
66 private:
67     QString m_target;
68     bool m_isCaseSensitive;
69
70     QChar *m_buffer;
71     QChar *m_cursor;
72     bool m_bufferFull;
73
74     CircularSearchBuffer(const CircularSearchBuffer&);
75     CircularSearchBuffer &operator=(const CircularSearchBuffer&);
76 };
77
78 TextIterator::TextIterator() : m_endContainer(0), m_endOffset(0), m_positionNode(0)
79 {
80 }
81
82 TextIterator::TextIterator(const Range &r, IteratorKind kind) : m_endContainer(0), m_endOffset(0), m_positionNode(0)
83 {
84     const RangeImpl *ri = r.handle();
85     if (!ri)
86         return;
87
88     int exceptionCode = 0;
89
90     // get and validate the range endpoints
91     NodeImpl *startContainer = ri->startContainer(exceptionCode);
92     long startOffset = ri->startOffset(exceptionCode);
93     NodeImpl *endContainer = ri->endContainer(exceptionCode);
94     long endOffset = ri->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 = ri->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 = ri->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         m_positionNode = m_node;
233         m_positionOffsetBaseNode = 0;
234         m_positionStartOffset = runStart;
235         m_positionEndOffset = runEnd;
236         m_textCharacters = str.unicode() + runStart;
237         m_textLength = runEnd - runStart;
238
239         m_lastCharacter = str[runEnd - 1];
240
241         return true;
242     }
243
244     if (!renderer->firstTextBox() && str.length() > 0) {
245         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
246         return true;
247     }
248
249     m_textBox = renderer->firstTextBox();
250     handleTextBox();
251     return true;
252 }
253
254 void TextIterator::handleTextBox()
255 {    
256     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
257     DOMString str = m_node->nodeValue();
258     long start = m_offset;
259     long end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
260     for (; m_textBox; m_textBox = m_textBox->nextTextBox()) {
261         long textBoxStart = m_textBox->m_start;
262         long runStart = kMax(textBoxStart, start);
263
264         // Check for collapsed space at the start of this run.
265         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
266             || (m_textBox == renderer->firstTextBox() && textBoxStart == runStart && runStart > 0);
267         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && !m_lastCharacter.isNull()) {
268             emitCharacter(' ', m_node, 0, runStart, runStart);
269             return;
270         }
271         long textBoxEnd = textBoxStart + m_textBox->m_len;
272         long runEnd = kMin(textBoxEnd, end);
273
274         if (runStart < runEnd) {
275             // Handle either a single newline character (which becomes a space),
276             // or a run of characters that does not include a newline.
277             // This effectively translates newlines to spaces without copying the text.
278             if (str[runStart] == '\n') {
279                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
280                 m_offset = runStart + 1;
281             } else {
282                 long subrunEnd = str.find('\n', runStart);
283                 if (subrunEnd == -1 || subrunEnd > runEnd) {
284                     subrunEnd = runEnd;
285                 }
286
287                 m_offset = subrunEnd;
288
289                 m_positionNode = m_node;
290                 m_positionOffsetBaseNode = 0;
291                 m_positionStartOffset = runStart;
292                 m_positionEndOffset = subrunEnd;
293                 m_textCharacters = str.unicode() + runStart;
294                 m_textLength = subrunEnd - runStart;
295
296                 m_lastTextNodeEndedWithCollapsedSpace = false;
297                 m_lastCharacter = str[subrunEnd - 1];
298             }
299
300             // If we are doing a subrun that doesn't go to the end of the text box,
301             // come back again to finish handling this text box; don't advance to the next one.
302             if (m_positionEndOffset < textBoxEnd) {
303                 return;
304             }
305
306             // Advance to the next text box.
307             InlineTextBox *nextTextBox = m_textBox->nextTextBox();
308             long nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();
309             if (nextRunStart > runEnd) {
310                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
311             }
312             m_textBox = nextTextBox;
313             return;
314         }
315     }
316 }
317
318 bool TextIterator::handleReplacedElement()
319 {
320     if (m_lastTextNodeEndedWithCollapsedSpace) {
321         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
322         return false;
323     }
324
325     m_positionNode = m_node->parentNode();
326     m_positionOffsetBaseNode = m_node;
327     m_positionStartOffset = 0;
328     m_positionEndOffset = 1;
329
330     m_textCharacters = 0;
331     m_textLength = 0;
332
333     m_lastCharacter = 0;
334
335     return true;
336 }
337
338 bool TextIterator::handleNonTextNode()
339 {
340     switch (m_node->id()) {
341         case ID_BR: {
342             emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
343             break;
344         }
345
346         case ID_TD:
347         case ID_TH:
348             if (m_lastCharacter != '\n' && m_lastTextNode) {
349                 emitCharacter('\t', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
350             }
351             break;
352
353         case ID_BLOCKQUOTE:
354         case ID_DD:
355         case ID_DIV:
356         case ID_DL:
357         case ID_DT:
358         case ID_H1:
359         case ID_H2:
360         case ID_H3:
361         case ID_H4:
362         case ID_H5:
363         case ID_H6:
364         case ID_HR:
365         case ID_LI:
366         case ID_OL:
367         case ID_P:
368         case ID_PRE:
369         case ID_TR:
370         case ID_UL:
371             if (m_lastCharacter != '\n' && m_lastTextNode) {
372                 emitCharacter('\n', m_lastTextNode->parentNode(), m_lastTextNode, 0, 1);
373             }
374             break;
375     }
376
377     return true;
378 }
379
380 void TextIterator::exitNode()
381 {
382     bool endLine = false;
383     bool addNewline = false;
384
385     switch (m_node->id()) {
386         case ID_BLOCKQUOTE:
387         case ID_DD:
388         case ID_DIV:
389         case ID_DL:
390         case ID_DT:
391         case ID_HR:
392         case ID_LI:
393         case ID_OL:
394         case ID_PRE:
395         case ID_TR:
396         case ID_UL:
397             endLine = true;
398             break;
399
400         case ID_H1:
401         case ID_H2:
402         case ID_H3:
403         case ID_H4:
404         case ID_H5:
405         case ID_H6:
406         case ID_P: {
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->htmlFont().getFontDef().computedPixelSize();
422                     if (bottomMargin * 2 >= fontSize) {
423                         addNewline = true;
424                     }
425                 }
426             }
427             break;
428         }
429     }
430
431     // emit character(s) iff there is an earlier text node and we need at least one newline
432     if (m_lastTextNode && endLine) {
433         if (m_lastCharacter != '\n') {
434             // insert a newline with a position following this block
435             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
436
437             //...and, if needed, set flag to later add a newline for the current node
438             assert(!m_needAnotherNewline);
439             m_needAnotherNewline = addNewline;
440         } else if (addNewline) {
441             // insert a newline with a position following this block
442             emitCharacter('\n', m_node->parentNode(), m_node, 1, 1);
443         }
444     }
445 }
446
447 void TextIterator::emitCharacter(QChar c, NodeImpl *textNode, NodeImpl *offsetBaseNode, long textStartOffset, long textEndOffset)
448 {
449     // remember information with which to construct the TextIterator::range()
450     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
451     m_positionNode = textNode;
452     m_positionOffsetBaseNode = offsetBaseNode;
453     m_positionStartOffset = textStartOffset;
454     m_positionEndOffset = textEndOffset;
455  
456     // remember information with which to construct the TextIterator::characters() and length()
457     m_singleCharacterBuffer = c;
458     m_textCharacters = &m_singleCharacterBuffer;
459     m_textLength = 1;
460
461     // remember some iteration state
462     m_lastTextNodeEndedWithCollapsedSpace = false;
463     m_lastCharacter = c;
464 }
465
466 Range TextIterator::range() const
467 {
468     // use the current run information, if we have it
469     if (m_positionNode) {
470         if (m_positionOffsetBaseNode) {
471             long index = m_positionOffsetBaseNode->nodeIndex();
472             m_positionStartOffset += index;
473             m_positionEndOffset += index;
474             m_positionOffsetBaseNode = 0;
475         }
476         return Range(m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
477     }
478
479     // otherwise, return the end of the overall range we were given
480     if (m_endContainer)
481         return Range(m_endContainer, m_endOffset, m_endContainer, m_endOffset);
482         
483     return Range();
484 }
485
486 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
487 {
488 }
489
490 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range &r)
491 {
492     if (r.isNull()) {
493         m_positionNode = 0;
494         return;
495     }
496
497     NodeImpl *startNode = r.startContainer().handle();
498     NodeImpl *endNode = r.endContainer().handle();
499     long startOffset = r.startOffset();
500     long endOffset = r.endOffset();
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     switch (m_node->id()) {
654         case ID_BR:
655             emitNewlineForBROrText();
656             break;
657         case ID_TD:
658         case ID_TH:
659         case ID_BLOCKQUOTE:
660         case ID_DD:
661         case ID_DIV:
662         case ID_DL:
663         case ID_DT:
664         case ID_H1:
665         case ID_H2:
666         case ID_H3:
667         case ID_H4:
668         case ID_H5:
669         case ID_H6:
670         case ID_HR:
671         case ID_P:
672         case ID_PRE:
673         case ID_TR:
674         case ID_OL:
675         case ID_UL:
676         case ID_LI:
677             // Emit a space to "break up" content. Any word break
678             // character will do.
679             emitCharacter(' ', m_node, 0, 0);
680             break;
681     }
682
683     return true;
684 }
685
686 void SimplifiedBackwardsTextIterator::exitNode()
687 {
688     // Left this function in so that the name and usage patters remain similar to 
689     // TextIterator. However, the needs of this iterator are much simpler, and
690     // the handleNonTextNode() function does just what we want (i.e. insert a
691     // space for certain node types to "break up" text so that it does not seem
692     // like content is next to other text when it really isn't). 
693     handleNonTextNode();
694 }
695
696 void SimplifiedBackwardsTextIterator::emitCharacter(QChar c, NodeImpl *node, long startOffset, long endOffset)
697 {
698     m_singleCharacterBuffer = c;
699     m_positionNode = node;
700     m_positionStartOffset = startOffset;
701     m_positionEndOffset = endOffset;
702     m_textCharacters = &m_singleCharacterBuffer;
703     m_textLength = 1;
704     m_lastCharacter = c;
705 }
706
707 void SimplifiedBackwardsTextIterator::emitNewlineForBROrText()
708 {
709     long offset;
710     
711     if (m_lastTextNode) {
712         offset = m_lastTextNode->nodeIndex();
713         emitCharacter('\n', m_lastTextNode->parentNode(), offset, offset + 1);
714     } else {
715         offset = m_node->nodeIndex();
716         emitCharacter('\n', m_node->parentNode(), offset, offset + 1);
717     }
718 }
719
720 Range SimplifiedBackwardsTextIterator::range() const
721 {
722     if (m_positionNode) {
723         return Range(m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
724     } else {
725         return Range(m_startNode, m_startOffset, m_startNode, m_startOffset);
726     }
727 }
728
729 CharacterIterator::CharacterIterator()
730     : m_offset(0), m_runOffset(0), m_atBreak(true)
731 {
732 }
733
734 CharacterIterator::CharacterIterator(const Range &r)
735     : m_offset(0), m_runOffset(0), m_atBreak(true), m_textIterator(r, RUNFINDER)
736 {
737     while (!atEnd() && m_textIterator.length() == 0) {
738         m_textIterator.advance();
739     }
740 }
741
742 Range CharacterIterator::range() const
743 {
744     Range r = m_textIterator.range();
745     if (!m_textIterator.atEnd()) {
746         if (m_textIterator.length() <= 1) {
747             assert(m_runOffset == 0);
748         } else {
749             Node n = r.startContainer();
750             assert(n == r.endContainer());
751             long offset = r.startOffset() + m_runOffset;
752             r.setStart(n, offset);
753             r.setEnd(n, offset + 1);
754         }
755     }
756     return r;
757 }
758
759 void CharacterIterator::advance(long count)
760 {
761     assert(!atEnd());
762
763     m_atBreak = false;
764
765     // easy if there is enough left in the current m_textIterator run
766     long remaining = m_textIterator.length() - m_runOffset;
767     if (count < remaining) {
768         m_runOffset += count;
769         m_offset += count;
770         return;
771     }
772
773     // exhaust the current m_textIterator run
774     count -= remaining;
775     m_offset += remaining;
776     
777     // move to a subsequent m_textIterator run
778     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
779         long runLength = m_textIterator.length();
780         if (runLength == 0) {
781             m_atBreak = true;
782         } else {
783             // see whether this is m_textIterator to use
784             if (count < runLength) {
785                 m_runOffset = count;
786                 m_offset += count;
787                 return;
788             }
789             
790             // exhaust this m_textIterator run
791             count -= runLength;
792             m_offset += runLength;
793         }
794     }
795
796     // ran to the end of the m_textIterator... no more runs left
797     m_atBreak = true;
798     m_runOffset = 0;
799 }
800
801 QString CharacterIterator::string(long numChars)
802 {
803     QString result;
804     result.reserve(numChars);
805     while (numChars > 0 && !atEnd()) {
806         long runSize = kMin(numChars, length());
807         result.append(characters(), runSize);
808         numChars -= runSize;
809         advance(runSize);
810     }
811     return result;
812 }
813
814 WordAwareIterator::WordAwareIterator()
815 : m_previousText(0), m_didLookAhead(false)
816 {
817 }
818
819 WordAwareIterator::WordAwareIterator(const Range &r)
820 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
821 {
822     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
823     advance();              // get in position over the first chunk of text
824 }
825
826 // We're always in one of these modes:
827 // - The current chunk in the text iterator is our current chunk
828 //      (typically its a piece of whitespace, or text that ended with whitespace)
829 // - The previous chunk in the text iterator is our current chunk
830 //      (we looked ahead to the next chunk and found a word boundary)
831 // - We built up our own chunk of text from many chunks from the text iterator
832
833 //FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
834
835 void WordAwareIterator::advance()
836 {
837     m_previousText = 0;
838     m_buffer = "";      // toss any old buffer we built up
839
840     // If last time we did a look-ahead, start with that looked-ahead chunk now
841     if (!m_didLookAhead) {
842         assert(!m_textIterator.atEnd());
843         m_textIterator.advance();
844     }
845     m_didLookAhead = false;
846
847     // Go to next non-empty chunk 
848     while (!m_textIterator.atEnd() && m_textIterator.length() == 0) {
849         m_textIterator.advance();
850     }
851     m_range = m_textIterator.range();
852
853     if (m_textIterator.atEnd()) {
854         return;
855     }
856     
857     while (1) {
858         // If this chunk ends in whitespace we can just use it as our chunk.
859         if (m_textIterator.characters()[m_textIterator.length()-1].isSpace()) {
860             return;
861         }
862
863         // If this is the first chunk that failed, save it in previousText before look ahead
864         if (m_buffer.isEmpty()) {
865             m_previousText = m_textIterator.characters();
866             m_previousLength = m_textIterator.length();
867         }
868
869         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
870         m_textIterator.advance();
871         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || m_textIterator.characters()[0].isSpace()) {
872             m_didLookAhead = true;
873             return;
874         }
875
876         if (m_buffer.isEmpty()) {
877             // Start gobbling chunks until we get to a suitable stopping point
878             m_buffer.append(m_previousText, m_previousLength);
879             m_previousText = 0;
880         }
881         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
882         m_range.setEnd(m_textIterator.range().endContainer(), m_textIterator.range().endOffset());
883     }
884 }
885
886 long WordAwareIterator::length() const
887 {
888     if (!m_buffer.isEmpty()) {
889         return m_buffer.length();
890     } else if (m_previousText) {
891         return m_previousLength;
892     } else {
893         return m_textIterator.length();
894     }
895 }
896
897 const QChar *WordAwareIterator::characters() const
898 {
899     if (!m_buffer.isEmpty()) {
900         return m_buffer.unicode();
901     } else if (m_previousText) {
902         return m_previousText;
903     } else {
904         return m_textIterator.characters();
905     }
906 }
907
908 CircularSearchBuffer::CircularSearchBuffer(const QString &s, bool isCaseSensitive)
909     : m_target(s)
910 {
911     assert(!s.isEmpty());
912
913     if (!isCaseSensitive) {
914         m_target = s.lower();
915     }
916     m_target.replace(nonBreakingSpace, ' ');
917     m_isCaseSensitive = isCaseSensitive;
918
919     m_buffer = static_cast<QChar *>(malloc(s.length() * sizeof(QChar)));
920     m_cursor = m_buffer;
921     m_bufferFull = false;
922 }
923
924 void CircularSearchBuffer::append(const QChar &c)
925 {
926     if (m_isCaseSensitive) {
927         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
928     } else {
929         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
930     }
931     if (m_cursor == m_buffer + length()) {
932         m_cursor = m_buffer;
933         m_bufferFull = true;
934     }
935 }
936
937 // This function can only be used when the buffer is not yet full,
938 // and when then count is small enough to fit in the buffer.
939 // No need for a more general version for the search algorithm.
940 void CircularSearchBuffer::append(long count, const QChar *characters)
941 {
942     long tailSpace = m_buffer + length() - m_cursor;
943
944     assert(!m_bufferFull);
945     assert(count <= tailSpace);
946
947     if (m_isCaseSensitive) {
948         for (long i = 0; i != count; ++i) {
949             QChar c = characters[i];
950             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
951         }
952     } else {
953         for (long i = 0; i != count; ++i) {
954             QChar c = characters[i];
955             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
956         }
957     }
958     if (count < tailSpace) {
959         m_cursor += count;
960     } else {
961         m_bufferFull = true;
962         m_cursor = m_buffer;
963     }
964 }
965
966 long CircularSearchBuffer::neededCharacters() const
967 {
968     return m_bufferFull ? 0 : m_buffer + length() - m_cursor;
969 }
970
971 bool CircularSearchBuffer::isMatch() const
972 {
973     assert(m_bufferFull);
974
975     long headSpace = m_cursor - m_buffer;
976     long tailSpace = length() - headSpace;
977     return memcmp(m_cursor, m_target.unicode(), tailSpace * sizeof(QChar)) == 0
978         && memcmp(m_buffer, m_target.unicode() + tailSpace, headSpace * sizeof(QChar)) == 0;
979 }
980
981 long TextIterator::rangeLength(const Range &r)
982 {
983     // Allocate string at the right size, rather than building it up by successive append calls.
984     long length = 0;
985     for (TextIterator it(r); !it.atEnd(); it.advance()) {
986         length += it.length();
987     }
988     return length;
989 }
990
991 void TextIterator::setRangeFromLocationAndLength (const Range &range, Range &resultRange, long rangeLocation, long rangeLength)
992 {
993     long docTextPosition = 0;
994     long rangeEnd = rangeLocation + rangeLength;
995
996     for (TextIterator it(range); !it.atEnd(); it.advance()) {
997         long len = it.length();
998         if (rangeLocation >= docTextPosition && rangeLocation < docTextPosition + len) {
999             resultRange.setStart(it.m_node, rangeLocation - docTextPosition);
1000         }
1001         if (rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len) {
1002             if ( !(rangeLength == 0 && rangeEnd == docTextPosition + len) ) {
1003                 resultRange.setEnd(it.m_node, rangeEnd - docTextPosition);
1004                 break;
1005             }
1006         }
1007         docTextPosition += it.length();
1008     }
1009 }
1010
1011 QString plainText(const Range &r)
1012 {
1013     // Allocate string at the right size, rather than building it up by successive append calls.
1014     long length = 0;
1015     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1016         length += it.length();
1017     }
1018     QString result("");
1019     result.reserve(length);
1020     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1021         result.append(it.characters(), it.length());
1022     }
1023     return result;
1024 }
1025
1026 Range findPlainText(const Range &r, const QString &s, bool forward, bool caseSensitive)
1027 {
1028     // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
1029
1030     // FIXME: This code does not allow \n at the moment because of issues with <br>.
1031     // Once we fix those, we can remove this check.
1032     if (s.isEmpty() || s.find('\n') != -1) {
1033         Range result = r;
1034         result.collapse(forward);
1035         return result;
1036     }
1037
1038     CircularSearchBuffer buffer(s, caseSensitive);
1039
1040     bool found = false;
1041     CharacterIterator rangeEnd;
1042
1043     {
1044         CharacterIterator it(r);
1045         while (1) {
1046             // Fill the buffer.
1047             while (long needed = buffer.neededCharacters()) {
1048                 if (it.atBreak()) {
1049                     if (it.atEnd()) {
1050                         goto done;
1051                     }
1052                     buffer.clear();
1053                 }
1054                 long available = it.length();
1055                 long runLength = kMin(needed, available);
1056                 buffer.append(runLength, it.characters());
1057                 it.advance(runLength);
1058             }
1059
1060             // Do the search.
1061             while (1) {
1062                 if (buffer.isMatch()) {
1063                     // Compute the range for the result.
1064                     found = true;
1065                     rangeEnd = it;
1066                     // If searching forward, stop on the first match.
1067                     // If searching backward, don't stop, so we end up with the last match.
1068                     if (forward) {
1069                         goto done;
1070                     }
1071                 }
1072                 if (it.atBreak())
1073                     break;
1074                 buffer.append(it.characters()[0]);
1075                 it.advance(1);
1076             }
1077             buffer.clear();
1078         }
1079     }
1080
1081 done:
1082     Range result = r;
1083     if (!found) {
1084         result.collapse(!forward);
1085     } else {
1086         CharacterIterator it(r);
1087         it.advance(rangeEnd.characterOffset() - buffer.length());
1088         result.setStart(it.range().startContainer(), it.range().startOffset());
1089         it.advance(buffer.length() - 1);
1090         result.setEnd(it.range().endContainer(), it.range().endOffset());
1091     }
1092     return result;
1093 }
1094
1095 }