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