Reviewed by Ken Kocienda.
[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) : 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     NodeImpl *startContainer = ri->startContainer(exceptionCode);
91     long startOffset = ri->startOffset(exceptionCode);
92     NodeImpl *endContainer = ri->endContainer(exceptionCode);
93     long endOffset = ri->endOffset(exceptionCode);
94
95     if (exceptionCode != 0)
96         return;
97
98     m_endContainer = endContainer;
99     m_endOffset = endOffset;
100
101     m_node = ri->startNode();
102     if (m_node == 0)
103         return;
104
105     m_offset = m_node == startContainer ? startOffset : 0;
106     m_handledNode = false;
107     m_handledChildren = false;
108
109     m_pastEndNode = ri->pastEndNode();
110
111     m_needAnotherNewline = false;
112     m_textBox = 0;
113
114     m_lastTextNode = 0;
115     m_lastTextNodeEndedWithCollapsedSpace = false;
116     m_lastCharacter = '\n';
117
118 #ifndef NDEBUG
119     // Need this just because of the assert.
120     m_positionNode = m_node;
121 #endif
122
123     advance();
124 }
125
126 void TextIterator::advance()
127 {
128     assert(m_positionNode);
129
130     m_positionNode = 0;
131     m_textLength = 0;
132
133     if (m_needAnotherNewline) {
134         // Emit the newline, with position a collapsed range at the end of current node.
135         long offset = m_node->nodeIndex();
136         emitCharacter('\n', m_node->parentNode(), offset + 1, offset + 1);
137         m_needAnotherNewline = false;
138         return;
139     }
140
141     if (m_textBox) {
142         handleTextBox();
143         if (m_positionNode) {
144             return;
145         }
146     }
147
148     while (m_node && m_node != m_pastEndNode) {
149         if (!m_handledNode) {
150             RenderObject *renderer = m_node->renderer();
151             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
152                 // FIXME: What about CDATA_SECTION_NODE?
153                 if (renderer->style()->visibility() == VISIBLE) {
154                     m_handledNode = handleTextNode();
155                 }
156             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
157                 if (renderer->style()->visibility() == VISIBLE) {
158                     m_handledNode = handleReplacedElement();
159                 }
160             } else {
161                 m_handledNode = handleNonTextNode();
162             }
163             if (m_positionNode) {
164                 return;
165             }
166         }
167
168         NodeImpl *next = m_handledChildren ? 0 : m_node->firstChild();
169         m_offset = 0;
170         if (!next) {
171             next = m_node->nextSibling();
172             if (!next) {
173                 if (m_node->traverseNextNode() == m_pastEndNode)
174                     break;
175                 while (!next && m_node->parentNode()) {
176                     m_node = m_node->parentNode();
177                     exitNode();
178                     if (m_positionNode) {
179                         m_handledNode = true;
180                         m_handledChildren = true;
181                         return;
182                     }
183                     next = m_node->nextSibling();
184                 }
185             }
186         }
187
188         m_node = next;
189         m_handledNode = false;
190         m_handledChildren = false;
191
192         if (m_positionNode) {
193             return;
194         }
195     }
196 }
197
198 bool TextIterator::handleTextNode()
199 {
200     m_lastTextNode = m_node;
201
202     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
203     DOMString str = m_node->nodeValue();
204
205     if (renderer->style()->whiteSpace() == khtml::PRE) {
206         long runStart = m_offset;
207         if (m_lastTextNodeEndedWithCollapsedSpace) {
208             emitCharacter(' ', m_node, runStart, runStart);
209             return false;
210         }
211         long strLength = str.length();
212         long end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
213         long runEnd = kMin(strLength, end);
214
215         m_positionNode = m_node;
216         m_positionStartOffset = runStart;
217         m_positionEndOffset = runEnd;
218         m_textCharacters = str.unicode() + runStart;
219         m_textLength = runEnd - runStart;
220
221         m_lastCharacter = str[runEnd - 1];
222
223         return true;
224     }
225
226     if (!renderer->firstTextBox() && str.length() > 0) {
227         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
228         return true;
229     }
230
231     m_textBox = renderer->firstTextBox();
232     handleTextBox();
233     return true;
234 }
235
236 void TextIterator::handleTextBox()
237 {    
238     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
239     DOMString str = m_node->nodeValue();
240     long start = m_offset;
241     long end = (m_node == m_endContainer) ? m_endOffset : LONG_MAX;
242     for (; m_textBox; m_textBox = m_textBox->nextTextBox()) {
243         long textBoxStart = m_textBox->m_start;
244         long runStart = kMax(textBoxStart, start);
245
246         // Check for collapsed space at the start of this run.
247         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
248             || (m_textBox == renderer->firstTextBox() && textBoxStart == runStart && runStart > 0);
249         if (needSpace && !m_lastCharacter.isSpace()) {
250             emitCharacter(' ', m_node, runStart, runStart);
251             return;
252         }
253
254         long textBoxEnd = textBoxStart + m_textBox->m_len;
255         long runEnd = kMin(textBoxEnd, end);
256
257         if (runStart < runEnd) {
258             // Handle either a single newline character (which becomes a space),
259             // or a run of characters that does not include a newline.
260             // This effectively translates newlines to spaces without copying the text.
261             if (str[runStart] == '\n') {
262                 emitCharacter(' ', m_node, runStart, runStart + 1);
263                 m_offset = runStart + 1;
264             } else {
265                 long subrunEnd = str.find('\n', runStart);
266                 if (subrunEnd == -1 || subrunEnd > runEnd) {
267                     subrunEnd = runEnd;
268                 }
269
270                 m_offset = subrunEnd;
271
272                 m_positionNode = m_node;
273                 m_positionStartOffset = runStart;
274                 m_positionEndOffset = subrunEnd;
275                 m_textCharacters = str.unicode() + runStart;
276                 m_textLength = subrunEnd - runStart;
277
278                 m_lastTextNodeEndedWithCollapsedSpace = false;
279                 m_lastCharacter = str[subrunEnd - 1];
280             }
281
282             // If we are doing a subrun that doesn't go to the end of the text box,
283             // come back again to finish handling this text box; don't advance to the next one.
284             if (m_positionEndOffset < textBoxEnd) {
285                 return;
286             }
287
288             // Advance to the next text box.
289             InlineTextBox *nextTextBox = m_textBox->nextTextBox();
290             long nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();
291             if (nextRunStart > runEnd) {
292                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
293             }
294             m_textBox = nextTextBox;
295             return;
296         }
297     }
298 }
299
300 bool TextIterator::handleReplacedElement()
301 {
302     if (m_lastTextNodeEndedWithCollapsedSpace) {
303         long offset = m_lastTextNode->nodeIndex();
304         emitCharacter(' ', m_lastTextNode->parentNode(), offset + 1, offset + 1);
305         return false;
306     }
307
308     long offset = m_node->nodeIndex();
309
310     m_positionNode = m_node->parentNode();
311     m_positionStartOffset = offset;
312     m_positionEndOffset = offset + 1;
313
314     m_textCharacters = 0;
315     m_textLength = 0;
316
317     m_lastCharacter = 0;
318
319     return true;
320 }
321
322 bool TextIterator::handleNonTextNode()
323 {
324     switch (m_node->id()) {
325         case ID_BR: {
326             long offset = m_node->nodeIndex();
327             emitCharacter('\n', m_node->parentNode(), offset, offset + 1);
328             break;
329         }
330
331         case ID_TD:
332         case ID_TH:
333             if (m_lastCharacter != '\n' && m_lastTextNode) {
334                 long offset = m_lastTextNode->nodeIndex();
335                 emitCharacter('\t', m_lastTextNode->parentNode(), offset, offset + 1);
336             }
337             break;
338
339         case ID_BLOCKQUOTE:
340         case ID_DD:
341         case ID_DIV:
342         case ID_DL:
343         case ID_DT:
344         case ID_H1:
345         case ID_H2:
346         case ID_H3:
347         case ID_H4:
348         case ID_H5:
349         case ID_H6:
350         case ID_HR:
351         case ID_LI:
352         case ID_OL:
353         case ID_P:
354         case ID_PRE:
355         case ID_TR:
356         case ID_UL:
357             if (m_lastCharacter != '\n' && m_lastTextNode) {
358                 long offset = m_lastTextNode->nodeIndex();
359                 emitCharacter('\n', m_lastTextNode->parentNode(), offset, offset + 1);
360             }
361             break;
362     }
363
364     return true;
365 }
366
367 void TextIterator::exitNode()
368 {
369     bool endLine = false;
370     bool addNewline = false;
371
372     switch (m_node->id()) {
373         case ID_BLOCKQUOTE:
374         case ID_DD:
375         case ID_DIV:
376         case ID_DL:
377         case ID_DT:
378         case ID_HR:
379         case ID_LI:
380         case ID_OL:
381         case ID_PRE:
382         case ID_TR:
383         case ID_UL:
384             endLine = true;
385             break;
386
387         case ID_H1:
388         case ID_H2:
389         case ID_H3:
390         case ID_H4:
391         case ID_H5:
392         case ID_H6:
393         case ID_P:
394             endLine = true;
395             addNewline = true;
396             break;
397     }
398
399     if (endLine && m_lastCharacter != '\n' && m_lastTextNode) {
400         long offset = m_lastTextNode->nodeIndex();
401         emitCharacter('\n', m_lastTextNode->parentNode(), offset, offset + 1);
402         m_needAnotherNewline = addNewline;
403     } else if (addNewline && m_lastTextNode) {
404         long offset = m_node->childNodeCount();
405         emitCharacter('\n', m_node, offset, offset);
406     }
407 }
408
409 void TextIterator::emitCharacter(QChar c, NodeImpl *textNode, long textStartOffset, long textEndOffset)
410 {
411     m_singleCharacterBuffer = c;
412     m_positionNode = textNode;
413     m_positionStartOffset = textStartOffset;
414     m_positionEndOffset = textEndOffset;
415     m_textCharacters = &m_singleCharacterBuffer;
416     m_textLength = 1;
417
418     m_lastTextNodeEndedWithCollapsedSpace = false;
419     m_lastCharacter = c;
420 }
421
422 Range TextIterator::range() const
423 {
424     if (m_positionNode)
425         return Range(m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
426     if (m_endContainer)
427         return Range(m_endContainer, m_endOffset, m_endContainer, m_endOffset);
428     return Range();
429 }
430
431 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator() : m_positionNode(0)
432 {
433 }
434
435 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range &r)
436 {
437     if (r.isNull()) {
438         m_positionNode = 0;
439         return;
440     }
441
442     NodeImpl *startNode = r.startContainer().handle();
443     NodeImpl *endNode = r.endContainer().handle();
444     long startOffset = r.startOffset();
445     long endOffset = r.endOffset();
446
447     if (!offsetInCharacters(startNode->nodeType())) {
448         if (startOffset >= 0 && startOffset < static_cast<long>(startNode->childNodeCount())) {
449             startNode = startNode->childNode(startOffset);
450             startOffset = 0;
451         }
452     }
453     if (!offsetInCharacters(endNode->nodeType())) {
454         if (endOffset > 0 && endOffset <= static_cast<long>(endNode->childNodeCount())) {
455             endNode = endNode->childNode(endOffset - 1);
456             endOffset = endNode->hasChildNodes() ? endNode->childNodeCount() : endNode->maxOffset();
457         }
458     }
459
460     m_node = endNode;
461     m_offset = endOffset;
462     m_handledNode = false;
463     m_handledChildren = endOffset == 0;
464
465     m_startNode = startNode;
466     m_startOffset = startOffset;
467
468 #ifndef NDEBUG
469     // Need this just because of the assert.
470     m_positionNode = endNode;
471 #endif
472
473     m_lastTextNode = 0;
474     m_lastCharacter = '\n';
475
476     advance();
477 }
478
479 void SimplifiedBackwardsTextIterator::advance()
480 {
481     assert(m_positionNode);
482
483     m_positionNode = 0;
484     m_textLength = 0;
485
486     while (m_node) {
487         if (!m_handledNode) {
488             RenderObject *renderer = m_node->renderer();
489             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
490                 // FIXME: What about CDATA_SECTION_NODE?
491                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0) {
492                     m_handledNode = handleTextNode();
493                 }
494             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
495                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0) {
496                     m_handledNode = handleReplacedElement();
497                 }
498             } else {
499                 m_handledNode = handleNonTextNode();
500             }
501             if (m_positionNode) {
502                 return;
503             }
504         }
505
506         if (m_node == m_startNode)
507             return;
508
509         NodeImpl *next = 0;
510         if (!m_handledChildren) {
511             next = m_node->lastChild();
512             while (next && next->lastChild())
513                 next = next->lastChild();
514             m_handledChildren = true;
515         }
516         if (!next && m_node != m_startNode) {
517             next = m_node->previousSibling();
518             if (next) {
519                 exitNode();
520                 while (next->lastChild())
521                     next = next->lastChild();
522             }
523             else if (m_node->parentNode()) {
524                 next = m_node->parentNode();
525                 exitNode();
526             }
527         }
528         
529         m_node = next;
530         if (m_node)
531             m_offset = m_node->caretMaxOffset();
532         else
533             m_offset = 0;
534         m_handledNode = false;
535         
536         if (m_positionNode) {
537             return;
538         }
539     }
540 }
541
542 bool SimplifiedBackwardsTextIterator::handleTextNode()
543 {
544     m_lastTextNode = m_node;
545
546     RenderText *renderer = static_cast<RenderText *>(m_node->renderer());
547     DOMString str = m_node->nodeValue();
548
549     if (!renderer->firstTextBox() && str.length() > 0) {
550         return true;
551     }
552
553     m_positionEndOffset = m_offset;
554
555     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
556     m_positionNode = m_node;
557     m_positionStartOffset = m_offset;
558     m_textLength = m_positionEndOffset - m_positionStartOffset;
559     m_textCharacters = str.unicode() + m_positionStartOffset;
560
561     m_lastCharacter = str[m_positionEndOffset - 1];
562
563     return true;
564 }
565
566 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
567 {
568     long offset = m_node->nodeIndex();
569
570     m_positionNode = m_node->parentNode();
571     m_positionStartOffset = offset;
572     m_positionEndOffset = offset + 1;
573
574     m_textCharacters = 0;
575     m_textLength = 0;
576
577     m_lastCharacter = 0;
578
579     return true;
580 }
581
582 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
583 {
584     switch (m_node->id()) {
585         case ID_BR:
586         {
587             long offset;
588     
589             if (m_lastTextNode) {
590                 offset = m_lastTextNode->nodeIndex();
591                 emitCharacter('\n', m_lastTextNode->parentNode(), offset, offset + 1);
592             } else {
593                 offset = m_node->nodeIndex();
594                 emitCharacter('\n', m_node->parentNode(), offset, offset + 1);
595             }
596             break;
597         }
598
599         case ID_TD:
600         case ID_TH:
601         case ID_BLOCKQUOTE:
602         case ID_DD:
603         case ID_DIV:
604         case ID_DL:
605         case ID_DT:
606         case ID_H1:
607         case ID_H2:
608         case ID_H3:
609         case ID_H4:
610         case ID_H5:
611         case ID_H6:
612         case ID_HR:
613         case ID_P:
614         case ID_PRE:
615         case ID_TR:
616         case ID_OL:
617         case ID_UL:
618         case ID_LI:
619             // Emit a space to "break up" content. Any word break
620             // character will do.
621             emitCharacter(' ', m_node, 0, 0);
622             break;
623     }
624
625     return true;
626 }
627
628 void SimplifiedBackwardsTextIterator::exitNode()
629 {
630     // Left this function in so that the name and usage patters remain similar to 
631     // TextIterator. However, the needs of this iterator are much simpler, and
632     // the handleNonTextNode() function does just what we want (i.e. insert a
633     // space for certain node types to "break up" text so that it does not seem
634     // like content is next to other text when it really isn't). 
635     handleNonTextNode();
636 }
637
638 void SimplifiedBackwardsTextIterator::emitCharacter(QChar c, NodeImpl *node, long startOffset, long endOffset)
639 {
640     m_singleCharacterBuffer = c;
641     m_positionNode = node;
642     m_positionStartOffset = startOffset;
643     m_positionEndOffset = endOffset;
644     m_textCharacters = &m_singleCharacterBuffer;
645     m_textLength = 1;
646     m_lastCharacter = c;
647 }
648
649 Range SimplifiedBackwardsTextIterator::range() const
650 {
651     if (m_positionNode) {
652         return Range(m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
653     } else {
654         return Range(m_startNode, m_startOffset, m_startNode, m_startOffset);
655     }
656 }
657
658 CharacterIterator::CharacterIterator()
659     : m_offset(0), m_runOffset(0), m_atBreak(true)
660 {
661 }
662
663 CharacterIterator::CharacterIterator(const Range &r)
664     : m_offset(0), m_runOffset(0), m_atBreak(true), m_textIterator(r)
665 {
666     while (!atEnd() && m_textIterator.length() == 0) {
667         m_textIterator.advance();
668     }
669 }
670
671 Range CharacterIterator::range() const
672 {
673     Range r = m_textIterator.range();
674     if (!m_textIterator.atEnd()) {
675         if (m_textIterator.length() <= 1) {
676             assert(m_runOffset == 0);
677         } else {
678             Node n = r.startContainer();
679             assert(n == r.endContainer());
680             long offset = r.startOffset() + m_runOffset;
681             r.setStart(n, offset);
682             r.setEnd(n, offset + 1);
683         }
684     }
685     return r;
686 }
687
688 void CharacterIterator::advance(long count)
689 {
690     assert(!atEnd());
691
692     m_atBreak = false;
693
694     long remaining = m_textIterator.length() - m_runOffset;
695     if (count < remaining) {
696         m_runOffset += count;
697         m_offset += count;
698         return;
699     }
700
701     count -= remaining;
702     m_offset += remaining;
703     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
704         long runLength = m_textIterator.length();
705         if (runLength == 0) {
706             m_atBreak = true;
707         } else {
708             if (count < runLength) {
709                 m_runOffset = count;
710                 m_offset += count;
711                 return;
712             }
713             count -= runLength;
714             m_offset += runLength;
715         }
716     }
717
718     m_atBreak = true;
719     m_runOffset = 0;
720 }
721
722 QString CharacterIterator::string(long numChars)
723 {
724     QString result;
725     result.reserve(numChars);
726     while (numChars > 0 && !atEnd()) {
727         long runSize = kMin(numChars, length());
728         result.append(characters(), runSize);
729         numChars -= runSize;
730         advance(runSize);
731     }
732     return result;
733 }
734
735 WordAwareIterator::WordAwareIterator()
736 : m_previousText(0), m_didLookAhead(false)
737 {
738 }
739
740 WordAwareIterator::WordAwareIterator(const Range &r)
741 : m_previousText(0), m_didLookAhead(false), m_textIterator(r)
742 {
743     m_didLookAhead = true;  // so we consider the first chunk from the text iterator
744     advance();              // get in position over the first chunk of text
745 }
746
747 // We're always in one of these modes:
748 // - The current chunk in the text iterator is our current chunk
749 //      (typically its a piece of whitespace, or text that ended with whitespace)
750 // - The previous chunk in the text iterator is our current chunk
751 //      (we looked ahead to the next chunk and found a word boundary)
752 // - We built up our own chunk of text from many chunks from the text iterator
753
754 //FIXME: Perf could be bad for huge spans next to each other that don't fall on word boundaries
755
756 void WordAwareIterator::advance()
757 {
758     m_previousText = 0;
759     m_buffer = "";      // toss any old buffer we built up
760
761     // If last time we did a look-ahead, start with that looked-ahead chunk now
762     if (!m_didLookAhead) {
763         assert(!m_textIterator.atEnd());
764         m_textIterator.advance();
765     }
766     m_didLookAhead = false;
767
768     // Go to next non-empty chunk 
769     while (!m_textIterator.atEnd() && m_textIterator.length() == 0) {
770         m_textIterator.advance();
771     }
772     m_range = m_textIterator.range();
773
774     if (m_textIterator.atEnd()) {
775         return;
776     }
777     
778     while (1) {
779         // If this chunk ends in whitespace we can just use it as our chunk.
780         if (m_textIterator.characters()[m_textIterator.length()-1].isSpace()) {
781             return;
782         }
783
784         // If this is the first chunk that failed, save it in previousText before look ahead
785         if (m_buffer.isEmpty()) {
786             m_previousText = m_textIterator.characters();
787             m_previousLength = m_textIterator.length();
788         }
789
790         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
791         m_textIterator.advance();
792         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || m_textIterator.characters()[0].isSpace()) {
793             m_didLookAhead = true;
794             return;
795         }
796
797         if (m_buffer.isEmpty()) {
798             // Start gobbling chunks until we get to a suitable stopping point
799             m_buffer.append(m_previousText, m_previousLength);
800             m_previousText = 0;
801         }
802         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
803         m_range.setEnd(m_textIterator.range().endContainer(), m_textIterator.range().endOffset());
804     }
805 }
806
807 long WordAwareIterator::length() const
808 {
809     if (!m_buffer.isEmpty()) {
810         return m_buffer.length();
811     } else if (m_previousText) {
812         return m_previousLength;
813     } else {
814         return m_textIterator.length();
815     }
816 }
817
818 const QChar *WordAwareIterator::characters() const
819 {
820     if (!m_buffer.isEmpty()) {
821         return m_buffer.unicode();
822     } else if (m_previousText) {
823         return m_previousText;
824     } else {
825         return m_textIterator.characters();
826     }
827 }
828
829 CircularSearchBuffer::CircularSearchBuffer(const QString &s, bool isCaseSensitive)
830     : m_target(s)
831 {
832     assert(!s.isEmpty());
833
834     if (!isCaseSensitive) {
835         m_target = s.lower();
836     }
837     m_target.replace(nonBreakingSpace, ' ');
838     m_isCaseSensitive = isCaseSensitive;
839
840     m_buffer = static_cast<QChar *>(malloc(s.length() * sizeof(QChar)));
841     m_cursor = m_buffer;
842     m_bufferFull = false;
843 }
844
845 void CircularSearchBuffer::append(const QChar &c)
846 {
847     if (m_isCaseSensitive) {
848         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
849     } else {
850         *m_cursor++ = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
851     }
852     if (m_cursor == m_buffer + length()) {
853         m_cursor = m_buffer;
854         m_bufferFull = true;
855     }
856 }
857
858 // This function can only be used when the buffer is not yet full,
859 // and when then count is small enough to fit in the buffer.
860 // No need for a more general version for the search algorithm.
861 void CircularSearchBuffer::append(long count, const QChar *characters)
862 {
863     long tailSpace = m_buffer + length() - m_cursor;
864
865     assert(!m_bufferFull);
866     assert(count <= tailSpace);
867
868     if (m_isCaseSensitive) {
869         for (long i = 0; i != count; ++i) {
870             QChar c = characters[i];
871             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.unicode();
872         }
873     } else {
874         for (long i = 0; i != count; ++i) {
875             QChar c = characters[i];
876             m_cursor[i] = c.unicode() == nonBreakingSpace ? ' ' : c.lower().unicode();
877         }
878     }
879     if (count < tailSpace) {
880         m_cursor += count;
881     } else {
882         m_bufferFull = true;
883         m_cursor = m_buffer;
884     }
885 }
886
887 long CircularSearchBuffer::neededCharacters() const
888 {
889     return m_bufferFull ? 0 : m_buffer + length() - m_cursor;
890 }
891
892 bool CircularSearchBuffer::isMatch() const
893 {
894     assert(m_bufferFull);
895
896     long headSpace = m_cursor - m_buffer;
897     long tailSpace = length() - headSpace;
898     return memcmp(m_cursor, m_target.unicode(), tailSpace * sizeof(QChar)) == 0
899         && memcmp(m_buffer, m_target.unicode() + tailSpace, headSpace * sizeof(QChar)) == 0;
900 }
901
902 QString plainText(const Range &r)
903 {
904     // Allocate string at the right size, rather than building it up by successive append calls.
905     long length = 0;
906     for (TextIterator it(r); !it.atEnd(); it.advance()) {
907         length += it.length();
908     }
909     QString result("");
910     result.reserve(length);
911     for (TextIterator it(r); !it.atEnd(); it.advance()) {
912         result.append(it.characters(), it.length());
913     }
914     return result;
915 }
916
917 Range findPlainText(const Range &r, const QString &s, bool forward, bool caseSensitive)
918 {
919     // FIXME: Can we do Boyer-Moore or equivalent instead for speed?
920
921     // FIXME: This code does not allow \n at the moment because of issues with <br>.
922     // Once we fix those, we can remove this check.
923     if (s.isEmpty() || s.find('\n') != -1) {
924         Range result = r;
925         result.collapse(forward);
926         return result;
927     }
928
929     CircularSearchBuffer buffer(s, caseSensitive);
930
931     bool found = false;
932     CharacterIterator rangeEnd;
933
934     {
935         CharacterIterator it(r);
936         while (1) {
937             // Fill the buffer.
938             while (long needed = buffer.neededCharacters()) {
939                 if (it.atBreak()) {
940                     if (it.atEnd()) {
941                         goto done;
942                     }
943                     buffer.clear();
944                 }
945                 long available = it.length();
946                 long runLength = kMin(needed, available);
947                 buffer.append(runLength, it.characters());
948                 it.advance(runLength);
949             }
950
951             // Do the search.
952             while (1) {
953                 if (buffer.isMatch()) {
954                     // Compute the range for the result.
955                     found = true;
956                     rangeEnd = it;
957                     // If searching forward, stop on the first match.
958                     // If searching backward, don't stop, so we end up with the last match.
959                     if (forward) {
960                         goto done;
961                     }
962                 }
963                 if (it.atBreak())
964                     break;
965                 buffer.append(it.characters()[0]);
966                 it.advance(1);
967             }
968             buffer.clear();
969         }
970     }
971
972 done:
973     Range result = r;
974     if (!found) {
975         result.collapse(!forward);
976     } else {
977         CharacterIterator it(r);
978         it.advance(rangeEnd.characterOffset() - buffer.length());
979         result.setStart(it.range().startContainer(), it.range().startOffset());
980         it.advance(buffer.length() - 1);
981         result.setEnd(it.range().endContainer(), it.range().endOffset());
982     }
983     return result;
984 }
985
986 }