WebCore: Swedish search (and other languages as well) is broken while fixing Japanese...
[WebKit-https.git] / WebCore / editing / TextIterator.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple 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 "CharacterNames.h"
31 #include "Document.h"
32 #include "HTMLElement.h"
33 #include "HTMLNames.h"
34 #include "htmlediting.h"
35 #include "InlineTextBox.h"
36 #include "Range.h"
37 #include "RenderTableCell.h"
38 #include "RenderTableRow.h"
39 #include "RenderTextControl.h"
40 #include "VisiblePosition.h"
41 #include "visible_units.h"
42
43 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
44 #include "TextBreakIteratorInternalICU.h"
45 #include <unicode/usearch.h>
46 #endif
47
48 using namespace WTF::Unicode;
49 using namespace std;
50
51 namespace WebCore {
52
53 using namespace HTMLNames;
54
55 // Buffer that knows how to compare with a search target.
56 // Keeps enough of the previous text to be able to search in the future, but no more.
57 // Non-breaking spaces are always equal to normal spaces.
58 // Case folding is also done if <isCaseSensitive> is false.
59 class SearchBuffer : public Noncopyable {
60 public:
61     SearchBuffer(const String& target, bool isCaseSensitive);
62     ~SearchBuffer();
63
64     // Returns number of characters appended; guaranteed to be in the range [1, length].
65     size_t append(const UChar*, size_t length);
66     void reachedBreak();
67
68     // Result is the size in characters of what was found.
69     // And <startOffset> is the number of characters back to the start of what was found.
70     size_t search(size_t& startOffset);
71     bool atBreak() const;
72
73 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
74
75 private:
76     String m_target;
77     Vector<UChar> m_buffer;
78     size_t m_overlap;
79     bool m_atBreak;
80
81 #else
82
83 private:
84     void append(UChar, bool isCharacterStart);
85     size_t length() const;
86
87     String m_target;
88     bool m_isCaseSensitive;
89
90     Vector<UChar> m_buffer;
91     Vector<bool> m_isCharacterStartBuffer;
92     bool m_isBufferFull;
93     size_t m_cursor;
94
95 #endif
96 };
97
98 // --------
99
100 static const unsigned bitsInWord = sizeof(unsigned) * 8;
101 static const unsigned bitInWordMask = bitsInWord - 1;
102
103 BitStack::BitStack()
104     : m_size(0)
105 {
106 }
107
108 void BitStack::push(bool bit)
109 {
110     unsigned index = m_size / bitsInWord;
111     unsigned shift = m_size & bitInWordMask;
112     if (!shift && index == m_words.size()) {
113         m_words.grow(index + 1);
114         m_words[index] = 0;
115     }
116     unsigned& word = m_words[index];
117     unsigned mask = 1U << shift;
118     if (bit)
119         word |= mask;
120     else
121         word &= ~mask;
122     ++m_size;
123 }
124
125 void BitStack::pop()
126 {
127     if (m_size)
128         --m_size;
129 }
130
131 bool BitStack::top() const
132 {
133     if (!m_size)
134         return false;
135     unsigned shift = (m_size - 1) & bitInWordMask;
136     return m_words.last() & (1U << shift);
137 }
138
139 unsigned BitStack::size() const
140 {
141     return m_size;
142 }
143
144 // --------
145
146 static inline Node* parentCrossingShadowBoundaries(Node* node)
147 {
148     if (Node* parent = node->parentNode())
149         return parent;
150     return node->shadowParentNode();
151 }
152
153 #ifndef NDEBUG
154
155 static unsigned depthCrossingShadowBoundaries(Node* node)
156 {
157     unsigned depth = 0;
158     for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))
159         ++depth;
160     return depth;
161 }
162
163 #endif
164
165 // This function is like Range::pastLastNode, except for the fact that it can climb up out of shadow trees.
166 static Node* nextInPreOrderCrossingShadowBoundaries(Node* rangeEndContainer, int rangeEndOffset)
167 {
168     if (!rangeEndContainer)
169         return 0;
170     if (rangeEndOffset >= 0 && !rangeEndContainer->offsetInCharacters()) {
171         if (Node* next = rangeEndContainer->childNode(rangeEndOffset))
172             return next;
173     }
174     for (Node* node = rangeEndContainer; node; node = parentCrossingShadowBoundaries(node)) {
175         if (Node* next = node->nextSibling())
176             return next;
177     }
178     return 0;
179 }
180
181 static Node* previousInPostOrderCrossingShadowBoundaries(Node* rangeStartContainer, int rangeStartOffset)
182 {
183     if (!rangeStartContainer)
184         return 0;
185     if (rangeStartOffset > 0 && !rangeStartContainer->offsetInCharacters()) {
186         if (Node* previous = rangeStartContainer->childNode(rangeStartOffset - 1))
187             return previous;
188     }
189     for (Node* node = rangeStartContainer; node; node = parentCrossingShadowBoundaries(node)) {
190         if (Node* previous = node->previousSibling())
191             return previous;
192     }
193     return 0;
194 }
195
196 // --------
197
198 static inline bool fullyClipsContents(Node* node)
199 {
200     RenderObject* renderer = node->renderer();
201     if (!renderer || !renderer->isBox() || !renderer->hasOverflowClip())
202         return false;
203     return toRenderBox(renderer)->size().isEmpty();
204 }
205
206 static inline bool ignoresContainerClip(Node* node)
207 {
208     RenderObject* renderer = node->renderer();
209     if (!renderer || renderer->isText())
210         return false;
211     EPosition position = renderer->style()->position();
212     return position == AbsolutePosition || position == FixedPosition;
213 }
214
215 static void pushFullyClippedState(BitStack& stack, Node* node)
216 {
217     ASSERT(stack.size() == depthCrossingShadowBoundaries(node));
218
219     // Push true if this node full clips its contents, or if a parent already has fully
220     // clipped and this is not a node that ignores its container's clip.
221     stack.push(fullyClipsContents(node) || stack.top() && !ignoresContainerClip(node));
222 }
223
224 static void setUpFullyClippedStack(BitStack& stack, Node* node)
225 {
226     // Put the nodes in a vector so we can iterate in reverse order.
227     Vector<Node*, 100> ancestry;
228     for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))
229         ancestry.append(parent);
230
231     // Call pushFullyClippedState on each node starting with the earliest ancestor.
232     size_t size = ancestry.size();
233     for (size_t i = 0; i < size; ++i)
234         pushFullyClippedState(stack, ancestry[size - i - 1]);
235     pushFullyClippedState(stack, node);
236
237     ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));
238 }
239
240 // --------
241
242 TextIterator::TextIterator()
243     : m_startContainer(0)
244     , m_startOffset(0)
245     , m_endContainer(0)
246     , m_endOffset(0)
247     , m_positionNode(0)
248     , m_textCharacters(0)
249     , m_textLength(0)
250     , m_lastCharacter(0)
251     , m_emitCharactersBetweenAllVisiblePositions(false)
252     , m_enterTextControls(false)
253 {
254 }
255
256 TextIterator::TextIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls) 
257     : m_startContainer(0) 
258     , m_startOffset(0)
259     , m_endContainer(0)
260     , m_endOffset(0)
261     , m_positionNode(0)
262     , m_textCharacters(0)
263     , m_textLength(0)
264     , m_emitCharactersBetweenAllVisiblePositions(emitCharactersBetweenAllVisiblePositions)
265     , m_enterTextControls(enterTextControls)
266 {
267     if (!r)
268         return;
269
270     // get and validate the range endpoints
271     Node* startContainer = r->startContainer();
272     if (!startContainer)
273         return;
274     int startOffset = r->startOffset();
275     Node* endContainer = r->endContainer();
276     int endOffset = r->endOffset();
277
278     // Callers should be handing us well-formed ranges. If we discover that this isn't
279     // the case, we could consider changing this assertion to an early return.
280     ASSERT(r->boundaryPointsValid());
281
282     // remember range - this does not change
283     m_startContainer = startContainer;
284     m_startOffset = startOffset;
285     m_endContainer = endContainer;
286     m_endOffset = endOffset;
287
288     // set up the current node for processing
289     m_node = r->firstNode();
290     if (!m_node)
291         return;
292     setUpFullyClippedStack(m_fullyClippedStack, m_node);
293     m_offset = m_node == m_startContainer ? m_startOffset : 0;
294     m_handledNode = false;
295     m_handledChildren = false;
296
297     // calculate first out of bounds node
298     m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(endContainer, endOffset);
299
300     // initialize node processing state
301     m_needAnotherNewline = false;
302     m_textBox = 0;
303
304     // initialize record of previous node processing
305     m_haveEmitted = false;
306     m_lastTextNode = 0;
307     m_lastTextNodeEndedWithCollapsedSpace = false;
308     m_lastCharacter = 0;
309
310 #ifndef NDEBUG
311     // need this just because of the assert in advance()
312     m_positionNode = m_node;
313 #endif
314
315     // identify the first run
316     advance();
317 }
318
319 void TextIterator::advance()
320 {
321     // reset the run information
322     m_positionNode = 0;
323     m_textLength = 0;
324
325     // handle remembered node that needed a newline after the text node's newline
326     if (m_needAnotherNewline) {
327         // Emit the extra newline, and position it *inside* m_node, after m_node's 
328         // contents, in case it's a block, in the same way that we position the first 
329         // newline.  The range for the emitted newline should start where the line 
330         // break begins.
331         // FIXME: It would be cleaner if we emitted two newlines during the last 
332         // iteration, instead of using m_needAnotherNewline.
333         Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
334         emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
335         m_needAnotherNewline = false;
336         return;
337     }
338
339     // handle remembered text box
340     if (m_textBox) {
341         handleTextBox();
342         if (m_positionNode)
343             return;
344     }
345
346     while (m_node && m_node != m_pastEndNode) {
347         // if the range ends at offset 0 of an element, represent the
348         // position, but not the content, of that element e.g. if the
349         // node is a blockflow element, emit a newline that
350         // precedes the element
351         if (m_node == m_endContainer && m_endOffset == 0) {
352             representNodeOffsetZero();
353             m_node = 0;
354             return;
355         }
356         
357         RenderObject* renderer = m_node->renderer();
358         if (!renderer) {
359             m_handledNode = true;
360             m_handledChildren = true;
361         } else {
362             // handle current node according to its type
363             if (!m_handledNode) {
364                 if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) // FIXME: What about CDATA_SECTION_NODE?
365                     m_handledNode = handleTextNode();
366                 else if (renderer && (renderer->isImage() || renderer->isWidget() ||
367                          (renderer->node() && renderer->node()->isElementNode() &&
368                           static_cast<Element*>(renderer->node())->isFormControlElement())))
369                     m_handledNode = handleReplacedElement();
370                 else
371                     m_handledNode = handleNonTextNode();
372                 if (m_positionNode)
373                     return;
374             }
375         }
376
377         // find a new current node to handle in depth-first manner,
378         // calling exitNode() as we come back thru a parent node
379         Node* next = m_handledChildren ? 0 : m_node->firstChild();
380         m_offset = 0;
381         if (!next) {
382             next = m_node->nextSibling();
383             if (!next) {
384                 bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;
385                 Node* parentNode = parentCrossingShadowBoundaries(m_node);
386                 while (!next && parentNode) {
387                     if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))
388                         return;
389                     bool haveRenderer = m_node->renderer();
390                     m_node = parentNode;
391                     m_fullyClippedStack.pop();
392                     parentNode = parentCrossingShadowBoundaries(m_node);
393                     if (haveRenderer)
394                         exitNode();
395                     if (m_positionNode) {
396                         m_handledNode = true;
397                         m_handledChildren = true;
398                         return;
399                     }
400                     next = m_node->nextSibling();
401                 }
402             }
403             m_fullyClippedStack.pop();            
404         }
405
406         // set the new current node
407         m_node = next;
408         if (m_node)
409             pushFullyClippedState(m_fullyClippedStack, m_node);
410         m_handledNode = false;
411         m_handledChildren = false;
412
413         // how would this ever be?
414         if (m_positionNode)
415             return;
416     }
417 }
418
419 static inline bool compareBoxStart(const InlineTextBox* first, const InlineTextBox* second)
420 {
421     return first->start() < second->start();
422 }
423
424 bool TextIterator::handleTextNode()
425 {
426     if (m_fullyClippedStack.top())
427         return false;
428
429     RenderText* renderer = toRenderText(m_node->renderer());
430     if (renderer->style()->visibility() != VISIBLE)
431         return false;
432         
433     m_lastTextNode = m_node;
434     String str = renderer->text();
435
436     // handle pre-formatted text
437     if (!renderer->style()->collapseWhiteSpace()) {
438         int runStart = m_offset;
439         if (m_lastTextNodeEndedWithCollapsedSpace) {
440             emitCharacter(' ', m_node, 0, runStart, runStart);
441             return false;
442         }
443         int strLength = str.length();
444         int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
445         int runEnd = min(strLength, end);
446
447         if (runStart >= runEnd)
448             return true;
449
450         emitText(m_node, runStart, runEnd);
451         return true;
452     }
453
454     if (!renderer->firstTextBox() && str.length() > 0) {
455         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
456         return true;
457     }
458
459     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
460     if (renderer->containsReversedText()) {
461         m_sortedTextBoxes.clear();
462         for (InlineTextBox* textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
463             m_sortedTextBoxes.append(textBox);
464         }
465         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 
466         m_sortedTextBoxesPosition = 0;
467     }
468     
469     m_textBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
470     handleTextBox();
471     return true;
472 }
473
474 void TextIterator::handleTextBox()
475 {    
476     RenderText* renderer = toRenderText(m_node->renderer());
477     String str = renderer->text();
478     int start = m_offset;
479     int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;
480     while (m_textBox) {
481         int textBoxStart = m_textBox->start();
482         int runStart = max(textBoxStart, start);
483
484         // Check for collapsed space at the start of this run.
485         InlineTextBox* firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();
486         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
487             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
488         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {
489             if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {
490                 unsigned spaceRunStart = runStart - 1;
491                 while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')
492                     --spaceRunStart;
493                 emitText(m_node, spaceRunStart, spaceRunStart + 1);
494             } else
495                 emitCharacter(' ', m_node, 0, runStart, runStart);
496             return;
497         }
498         int textBoxEnd = textBoxStart + m_textBox->len();
499         int runEnd = min(textBoxEnd, end);
500         
501         // Determine what the next text box will be, but don't advance yet
502         InlineTextBox* nextTextBox = 0;
503         if (renderer->containsReversedText()) {
504             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
505                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
506         } else 
507             nextTextBox = m_textBox->nextTextBox();
508
509         if (runStart < runEnd) {
510             // Handle either a single newline character (which becomes a space),
511             // or a run of characters that does not include a newline.
512             // This effectively translates newlines to spaces without copying the text.
513             if (str[runStart] == '\n') {
514                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);
515                 m_offset = runStart + 1;
516             } else {
517                 int subrunEnd = str.find('\n', runStart);
518                 if (subrunEnd == -1 || subrunEnd > runEnd)
519                     subrunEnd = runEnd;
520     
521                 m_offset = subrunEnd;
522                 emitText(m_node, runStart, subrunEnd);
523             }
524
525             // If we are doing a subrun that doesn't go to the end of the text box,
526             // come back again to finish handling this text box; don't advance to the next one.
527             if (m_positionEndOffset < textBoxEnd)
528                 return;
529
530             // Advance and return
531             int nextRunStart = nextTextBox ? nextTextBox->start() : str.length();
532             if (nextRunStart > runEnd)
533                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
534             m_textBox = nextTextBox;
535             if (renderer->containsReversedText())
536                 ++m_sortedTextBoxesPosition;
537             return;
538         }
539         // Advance and continue
540         m_textBox = nextTextBox;
541         if (renderer->containsReversedText())
542             ++m_sortedTextBoxesPosition;
543     }
544 }
545
546 bool TextIterator::handleReplacedElement()
547 {
548     if (m_fullyClippedStack.top())
549         return false;
550
551     RenderObject* renderer = m_node->renderer();
552     if (renderer->style()->visibility() != VISIBLE)
553         return false;
554
555     if (m_lastTextNodeEndedWithCollapsedSpace) {
556         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
557         return false;
558     }
559
560     if (m_enterTextControls && renderer->isTextControl()) {
561         if (HTMLElement* innerTextElement = toRenderTextControl(renderer)->innerTextElement()) {
562             m_node = innerTextElement->shadowTreeRootNode();
563             pushFullyClippedState(m_fullyClippedStack, m_node);
564             m_offset = 0;
565             return false;
566         }
567     }
568
569     m_haveEmitted = true;
570
571     if (m_emitCharactersBetweenAllVisiblePositions) {
572         // We want replaced elements to behave like punctuation for boundary 
573         // finding, and to simply take up space for the selection preservation 
574         // code in moveParagraphs, so we use a comma.
575         emitCharacter(',', m_node->parentNode(), m_node, 0, 1);
576         return true;
577     }
578
579     m_positionNode = m_node->parentNode();
580     m_positionOffsetBaseNode = m_node;
581     m_positionStartOffset = 0;
582     m_positionEndOffset = 1;
583
584     m_textCharacters = 0;
585     m_textLength = 0;
586
587     m_lastCharacter = 0;
588
589     return true;
590 }
591
592 static bool shouldEmitTabBeforeNode(Node* node)
593 {
594     RenderObject* r = node->renderer();
595     
596     // Table cells are delimited by tabs.
597     if (!r || !isTableCell(node))
598         return false;
599     
600     // Want a tab before every cell other than the first one
601     RenderTableCell* rc = toRenderTableCell(r);
602     RenderTable* t = rc->table();
603     return t && (t->cellBefore(rc) || t->cellAbove(rc));
604 }
605
606 static bool shouldEmitNewlineForNode(Node* node)
607 {
608     // br elements are represented by a single newline.
609     RenderObject* r = node->renderer();
610     if (!r)
611         return node->hasTagName(brTag);
612         
613     return r->isBR();
614 }
615
616 static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)
617 {
618     // Block flow (versus inline flow) is represented by having
619     // a newline both before and after the element.
620     RenderObject* r = node->renderer();
621     if (!r) {
622         return (node->hasTagName(blockquoteTag)
623                 || node->hasTagName(ddTag)
624                 || node->hasTagName(divTag)
625                 || node->hasTagName(dlTag)
626                 || node->hasTagName(dtTag)
627                 || node->hasTagName(h1Tag)
628                 || node->hasTagName(h2Tag)
629                 || node->hasTagName(h3Tag)
630                 || node->hasTagName(h4Tag)
631                 || node->hasTagName(h5Tag)
632                 || node->hasTagName(h6Tag)
633                 || node->hasTagName(hrTag)
634                 || node->hasTagName(liTag)
635                 || node->hasTagName(listingTag)
636                 || node->hasTagName(olTag)
637                 || node->hasTagName(pTag)
638                 || node->hasTagName(preTag)
639                 || node->hasTagName(trTag)
640                 || node->hasTagName(ulTag));
641     }
642     
643     // Need to make an exception for table cells, because they are blocks, but we
644     // want them tab-delimited rather than having newlines before and after.
645     if (isTableCell(node))
646         return false;
647     
648     // Need to make an exception for table row elements, because they are neither
649     // "inline" or "RenderBlock", but we want newlines for them.
650     if (r->isTableRow()) {
651         RenderTable* t = toRenderTableRow(r)->table();
652         if (t && !t->isInline())
653             return true;
654     }
655     
656     return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();
657 }
658
659 static bool shouldEmitNewlineAfterNode(Node* node)
660 {
661     // FIXME: It should be better but slower to create a VisiblePosition here.
662     if (!shouldEmitNewlinesBeforeAndAfterNode(node))
663         return false;
664     // Check if this is the very last renderer in the document.
665     // If so, then we should not emit a newline.
666     while ((node = node->traverseNextSibling()))
667         if (node->renderer())
668             return true;
669     return false;
670 }
671
672 static bool shouldEmitNewlineBeforeNode(Node* node)
673 {
674     return shouldEmitNewlinesBeforeAndAfterNode(node); 
675 }
676
677 static bool shouldEmitExtraNewlineForNode(Node* node)
678 {
679     // When there is a significant collapsed bottom margin, emit an extra
680     // newline for a more realistic result.  We end up getting the right
681     // result even without margin collapsing. For example: <div><p>text</p></div>
682     // will work right even if both the <div> and the <p> have bottom margins.
683     RenderObject* r = node->renderer();
684     if (!r || !r->isBox())
685         return false;
686     
687     // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears
688     // not to do this at all
689     if (node->hasTagName(h1Tag)
690         || node->hasTagName(h2Tag)
691         || node->hasTagName(h3Tag)
692         || node->hasTagName(h4Tag)
693         || node->hasTagName(h5Tag)
694         || node->hasTagName(h6Tag)
695         || node->hasTagName(pTag)) {
696         RenderStyle* style = r->style();
697         if (style) {
698             int bottomMargin = toRenderBox(r)->collapsedMarginBottom();
699             int fontSize = style->fontDescription().computedPixelSize();
700             if (bottomMargin * 2 >= fontSize)
701                 return true;
702         }
703     }
704     
705     return false;
706 }
707
708 // Whether or not we should emit a character as we enter m_node (if it's a container) or as we hit it (if it's atomic).
709 bool TextIterator::shouldRepresentNodeOffsetZero()
710 {
711     if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable())
712         return true;
713         
714     // Leave element positioned flush with start of a paragraph
715     // (e.g. do not insert tab before a table cell at the start of a paragraph)
716     if (m_lastCharacter == '\n')
717         return false;
718     
719     // Otherwise, show the position if we have emitted any characters
720     if (m_haveEmitted)
721         return true;
722     
723     // We've not emitted anything yet. Generally, there is no need for any positioning then.
724     // The only exception is when the element is visually not in the same line as
725     // the start of the range (e.g. the range starts at the end of the previous paragraph).
726     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we
727     // make quicker checks to possibly avoid that. Another check that we could make is
728     // is whether the inline vs block flow changed since the previous visible element.
729     // I think we're already in a special enough case that that won't be needed, tho.
730
731     // No character needed if this is the first node in the range.
732     if (m_node == m_startContainer)
733         return false;
734     
735     // If we are outside the start container's subtree, assume we need to emit.
736     // FIXME: m_startContainer could be an inline block
737     if (!m_node->isDescendantOf(m_startContainer))
738         return true;
739
740     // If we started as m_startContainer offset 0 and the current node is a descendant of
741     // the start container, we already had enough context to correctly decide whether to
742     // emit after a preceding block. We chose not to emit (m_haveEmitted is false),
743     // so don't second guess that now.
744     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably
745     // immaterial since we likely would have already emitted something by now.
746     if (m_startOffset == 0)
747         return false;
748         
749     // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning.
750     // Additionally, if the range we are iterating over contains huge sections of unrendered content, 
751     // we would create VisiblePositions on every call to this function without this check.
752     if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE)
753         return false;
754     
755     // The startPos.isNotNull() check is needed because the start could be before the body,
756     // and in that case we'll get null. We don't want to put in newlines at the start in that case.
757     // The currPos.isNotNull() check is needed because positions in non-HTML content
758     // (like SVG) do not have visible positions, and we don't want to emit for them either.
759     VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM);
760     VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM);
761     return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos);
762 }
763
764 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)
765 {
766     return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitCharactersBetweenAllVisiblePositions);
767 }
768
769 void TextIterator::representNodeOffsetZero()
770 {
771     // Emit a character to show the positioning of m_node.
772     
773     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 
774     // create VisiblePositions, which is expensive.  So, we perform the inexpensive checks
775     // on m_node to see if it necessitates emitting a character first and will early return 
776     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
777     if (shouldEmitTabBeforeNode(m_node)) {
778         if (shouldRepresentNodeOffsetZero())
779             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);
780     } else if (shouldEmitNewlineBeforeNode(m_node)) {
781         if (shouldRepresentNodeOffsetZero())
782             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);
783     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {
784         if (shouldRepresentNodeOffsetZero())
785             emitCharacter(' ', m_node->parentNode(), m_node, 0, 0);
786     }
787 }
788
789 bool TextIterator::handleNonTextNode()
790 {
791     if (shouldEmitNewlineForNode(m_node))
792         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
793     else if (m_emitCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())
794         emitCharacter(' ', m_node->parentNode(), m_node, 0, 1);
795     else
796         representNodeOffsetZero();
797
798     return true;
799 }
800
801 void TextIterator::exitNode()
802 {
803     // prevent emitting a newline when exiting a collapsed block at beginning of the range
804     // FIXME: !m_haveEmitted does not necessarily mean there was a collapsed block... it could
805     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
806     // therefore look like a blank line.
807     if (!m_haveEmitted)
808         return;
809         
810     // Emit with a position *inside* m_node, after m_node's contents, in 
811     // case it is a block, because the run should start where the 
812     // emitted character is positioned visually.
813     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;
814     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
815     // the logic in _web_attributedStringFromRange match.  We'll get that for free when we switch to use
816     // TextIterator in _web_attributedStringFromRange.
817     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
818     if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {
819         // use extra newline to represent margin bottom, as needed
820         bool addNewline = shouldEmitExtraNewlineForNode(m_node);
821         
822         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
823         // contain a VisiblePosition when doing selection preservation.
824         if (m_lastCharacter != '\n') {
825             // insert a newline with a position following this block's contents.
826             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
827             // remember whether to later add a newline for the current node
828             ASSERT(!m_needAnotherNewline);
829             m_needAnotherNewline = addNewline;
830         } else if (addNewline)
831             // insert a newline with a position following this block's contents.
832             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
833     }
834     
835     // If nothing was emitted, see if we need to emit a space.
836     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))
837         emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1);
838 }
839
840 void TextIterator::emitCharacter(UChar c, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset)
841 {
842     m_haveEmitted = true;
843     
844     // remember information with which to construct the TextIterator::range()
845     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
846     m_positionNode = textNode;
847     m_positionOffsetBaseNode = offsetBaseNode;
848     m_positionStartOffset = textStartOffset;
849     m_positionEndOffset = textEndOffset;
850  
851     // remember information with which to construct the TextIterator::characters() and length()
852     m_singleCharacterBuffer = c;
853     m_textCharacters = &m_singleCharacterBuffer;
854     m_textLength = 1;
855
856     // remember some iteration state
857     m_lastTextNodeEndedWithCollapsedSpace = false;
858     m_lastCharacter = c;
859 }
860
861 void TextIterator::emitText(Node* textNode, int textStartOffset, int textEndOffset)
862 {
863     RenderText* renderer = toRenderText(m_node->renderer());
864     String str = renderer->text();
865     ASSERT(str.characters());
866
867     m_positionNode = textNode;
868     m_positionOffsetBaseNode = 0;
869     m_positionStartOffset = textStartOffset;
870     m_positionEndOffset = textEndOffset;
871     m_textCharacters = str.characters() + textStartOffset;
872     m_textLength = textEndOffset - textStartOffset;
873     m_lastCharacter = str[textEndOffset - 1];
874
875     m_lastTextNodeEndedWithCollapsedSpace = false;
876     m_haveEmitted = true;
877 }
878
879 PassRefPtr<Range> TextIterator::range() const
880 {
881     // use the current run information, if we have it
882     if (m_positionNode) {
883         if (m_positionOffsetBaseNode) {
884             int index = m_positionOffsetBaseNode->nodeIndex();
885             m_positionStartOffset += index;
886             m_positionEndOffset += index;
887             m_positionOffsetBaseNode = 0;
888         }
889         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
890     }
891
892     // otherwise, return the end of the overall range we were given
893     if (m_endContainer)
894         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
895         
896     return 0;
897 }
898     
899 Node* TextIterator::node() const
900 {
901     RefPtr<Range> textRange = range();
902     if (!textRange)
903         return 0;
904
905     Node* node = textRange->startContainer();
906     if (!node)
907         return 0;
908     if (node->offsetInCharacters())
909         return node;
910     
911     return node->childNode(textRange->startOffset());
912 }
913
914 // --------
915
916 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator()
917     : m_positionNode(0)
918 {
919 }
920
921 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range* r)
922     : m_positionNode(0)
923 {
924     if (!r)
925         return;
926
927     Node* startNode = r->startContainer();
928     if (!startNode)
929         return;
930     Node* endNode = r->endContainer();
931     int startOffset = r->startOffset();
932     int endOffset = r->endOffset();
933
934     if (!startNode->offsetInCharacters()) {
935         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {
936             startNode = startNode->childNode(startOffset);
937             startOffset = 0;
938         }
939     }
940     if (!endNode->offsetInCharacters()) {
941         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {
942             endNode = endNode->childNode(endOffset - 1);
943             endOffset = lastOffsetInNode(endNode);
944         }
945     }
946
947     m_node = endNode;
948     setUpFullyClippedStack(m_fullyClippedStack, m_node);    
949     m_offset = endOffset;
950     m_handledNode = false;
951     m_handledChildren = endOffset == 0;
952
953     m_startNode = startNode;
954     m_startOffset = startOffset;
955     m_endNode = endNode;
956     m_endOffset = endOffset;
957     
958 #ifndef NDEBUG
959     // Need this just because of the assert.
960     m_positionNode = endNode;
961 #endif
962
963     m_lastTextNode = 0;
964     m_lastCharacter = '\n';
965
966     m_pastStartNode = previousInPostOrderCrossingShadowBoundaries(startNode, startOffset);
967
968     advance();
969 }
970
971 void SimplifiedBackwardsTextIterator::advance()
972 {
973     ASSERT(m_positionNode);
974
975     m_positionNode = 0;
976     m_textLength = 0;
977
978     while (m_node && m_node != m_pastStartNode) {
979         // Don't handle node if we start iterating at [node, 0].
980         if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) {
981             RenderObject* renderer = m_node->renderer();
982             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
983                 // FIXME: What about CDATA_SECTION_NODE?
984                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
985                     m_handledNode = handleTextNode();
986             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {
987                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
988                     m_handledNode = handleReplacedElement();
989             } else
990                 m_handledNode = handleNonTextNode();
991             if (m_positionNode)
992                 return;
993         }
994
995         Node* next = m_handledChildren ? 0 : m_node->lastChild();
996         if (!next) {
997             // Exit empty containers as we pass over them or containers
998             // where [container, 0] is where we started iterating.
999             if (!m_handledNode &&
1000                 canHaveChildrenForEditing(m_node) && 
1001                 m_node->parentNode() && 
1002                 (!m_node->lastChild() || (m_node == m_endNode && m_endOffset == 0))) {
1003                 exitNode();
1004                 if (m_positionNode) {
1005                     m_handledNode = true;
1006                     m_handledChildren = true;
1007                     return;
1008                 }            
1009             }
1010             // Exit all other containers.
1011             next = m_node->previousSibling();
1012             while (!next) {
1013                 Node* parentNode = parentCrossingShadowBoundaries(m_node);
1014                 if (!parentNode)
1015                     break;
1016                 m_node = parentNode;
1017                 m_fullyClippedStack.pop();
1018                 exitNode();
1019                 if (m_positionNode) {
1020                     m_handledNode = true;
1021                     m_handledChildren = true;
1022                     return;
1023                 }
1024                 next = m_node->previousSibling();
1025             }
1026             m_fullyClippedStack.pop();
1027         }
1028         
1029         m_node = next;
1030         if (m_node)
1031             pushFullyClippedState(m_fullyClippedStack, m_node);
1032         m_offset = m_node ? caretMaxOffset(m_node) : 0;
1033         m_handledNode = false;
1034         m_handledChildren = false;
1035         
1036         if (m_positionNode)
1037             return;
1038     }
1039 }
1040
1041 bool SimplifiedBackwardsTextIterator::handleTextNode()
1042 {
1043     m_lastTextNode = m_node;
1044
1045     RenderText* renderer = toRenderText(m_node->renderer());
1046     String str = renderer->text();
1047
1048     if (!renderer->firstTextBox() && str.length() > 0)
1049         return true;
1050
1051     m_positionEndOffset = m_offset;
1052
1053     m_offset = (m_node == m_startNode) ? m_startOffset : 0;
1054     m_positionNode = m_node;
1055     m_positionStartOffset = m_offset;
1056     m_textLength = m_positionEndOffset - m_positionStartOffset;
1057     m_textCharacters = str.characters() + m_positionStartOffset;
1058
1059     m_lastCharacter = str[m_positionEndOffset - 1];
1060
1061     return true;
1062 }
1063
1064 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
1065 {
1066     unsigned index = m_node->nodeIndex();
1067     // We want replaced elements to behave like punctuation for boundary 
1068     // finding, and to simply take up space for the selection preservation 
1069     // code in moveParagraphs, so we use a comma.  Unconditionally emit
1070     // here because this iterator is only used for boundary finding.
1071     emitCharacter(',', m_node->parentNode(), index, index + 1);
1072     return true;
1073 }
1074
1075 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
1076 {    
1077     // We can use a linefeed in place of a tab because this simple iterator is only used to
1078     // find boundaries, not actual content.  A linefeed breaks words, sentences, and paragraphs.
1079     if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineAfterNode(m_node) || shouldEmitTabBeforeNode(m_node)) {
1080         unsigned index = m_node->nodeIndex();
1081         // The start of this emitted range is wrong. Ensuring correctness would require
1082         // VisiblePositions and so would be slow. previousBoundary expects this.
1083         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
1084     }
1085     return true;
1086 }
1087
1088 void SimplifiedBackwardsTextIterator::exitNode()
1089 {
1090     if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineBeforeNode(m_node) || shouldEmitTabBeforeNode(m_node)) {
1091         // The start of this emitted range is wrong. Ensuring correctness would require
1092         // VisiblePositions and so would be slow. previousBoundary expects this.
1093         emitCharacter('\n', m_node, 0, 0);
1094     }
1095 }
1096
1097 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node* node, int startOffset, int endOffset)
1098 {
1099     m_singleCharacterBuffer = c;
1100     m_positionNode = node;
1101     m_positionStartOffset = startOffset;
1102     m_positionEndOffset = endOffset;
1103     m_textCharacters = &m_singleCharacterBuffer;
1104     m_textLength = 1;
1105     m_lastCharacter = c;
1106 }
1107
1108 PassRefPtr<Range> SimplifiedBackwardsTextIterator::range() const
1109 {
1110     if (m_positionNode)
1111         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
1112     
1113     return Range::create(m_startNode->document(), m_startNode, m_startOffset, m_startNode, m_startOffset);
1114 }
1115
1116 // --------
1117
1118 CharacterIterator::CharacterIterator()
1119     : m_offset(0)
1120     , m_runOffset(0)
1121     , m_atBreak(true)
1122 {
1123 }
1124
1125 CharacterIterator::CharacterIterator(const Range* r, bool emitCharactersBetweenAllVisiblePositions, bool enterTextControls)
1126     : m_offset(0)
1127     , m_runOffset(0)
1128     , m_atBreak(true)
1129     , m_textIterator(r, emitCharactersBetweenAllVisiblePositions, enterTextControls)
1130 {
1131     while (!atEnd() && m_textIterator.length() == 0)
1132         m_textIterator.advance();
1133 }
1134
1135 PassRefPtr<Range> CharacterIterator::range() const
1136 {
1137     RefPtr<Range> r = m_textIterator.range();
1138     if (!m_textIterator.atEnd()) {
1139         if (m_textIterator.length() <= 1) {
1140             ASSERT(m_runOffset == 0);
1141         } else {
1142             Node* n = r->startContainer();
1143             ASSERT(n == r->endContainer());
1144             int offset = r->startOffset() + m_runOffset;
1145             ExceptionCode ec = 0;
1146             r->setStart(n, offset, ec);
1147             r->setEnd(n, offset + 1, ec);
1148             ASSERT(!ec);
1149         }
1150     }
1151     return r.release();
1152 }
1153
1154 void CharacterIterator::advance(int count)
1155 {
1156     if (count <= 0) {
1157         ASSERT(count == 0);
1158         return;
1159     }
1160     
1161     m_atBreak = false;
1162
1163     // easy if there is enough left in the current m_textIterator run
1164     int remaining = m_textIterator.length() - m_runOffset;
1165     if (count < remaining) {
1166         m_runOffset += count;
1167         m_offset += count;
1168         return;
1169     }
1170
1171     // exhaust the current m_textIterator run
1172     count -= remaining;
1173     m_offset += remaining;
1174     
1175     // move to a subsequent m_textIterator run
1176     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1177         int runLength = m_textIterator.length();
1178         if (runLength == 0)
1179             m_atBreak = true;
1180         else {
1181             // see whether this is m_textIterator to use
1182             if (count < runLength) {
1183                 m_runOffset = count;
1184                 m_offset += count;
1185                 return;
1186             }
1187             
1188             // exhaust this m_textIterator run
1189             count -= runLength;
1190             m_offset += runLength;
1191         }
1192     }
1193
1194     // ran to the end of the m_textIterator... no more runs left
1195     m_atBreak = true;
1196     m_runOffset = 0;
1197 }
1198
1199 String CharacterIterator::string(int numChars)
1200 {
1201     Vector<UChar> result;
1202     result.reserveInitialCapacity(numChars);
1203     while (numChars > 0 && !atEnd()) {
1204         int runSize = min(numChars, length());
1205         result.append(characters(), runSize);
1206         numChars -= runSize;
1207         advance(runSize);
1208     }
1209     return String::adopt(result);
1210 }
1211
1212 static PassRefPtr<Range> characterSubrange(CharacterIterator& it, int offset, int length)
1213 {
1214     it.advance(offset);
1215     RefPtr<Range> start = it.range();
1216
1217     if (length > 1)
1218         it.advance(length - 1);
1219     RefPtr<Range> end = it.range();
1220
1221     return Range::create(start->startContainer()->document(), 
1222         start->startContainer(), start->startOffset(), 
1223         end->endContainer(), end->endOffset());
1224 }
1225
1226 BackwardsCharacterIterator::BackwardsCharacterIterator()
1227     : m_offset(0)
1228     , m_runOffset(0)
1229     , m_atBreak(true)
1230 {
1231 }
1232
1233 BackwardsCharacterIterator::BackwardsCharacterIterator(const Range* range)
1234     : m_offset(0)
1235     , m_runOffset(0)
1236     , m_atBreak(true)
1237     , m_textIterator(range)
1238 {
1239     while (!atEnd() && !m_textIterator.length())
1240         m_textIterator.advance();
1241 }
1242
1243 PassRefPtr<Range> BackwardsCharacterIterator::range() const
1244 {
1245     RefPtr<Range> r = m_textIterator.range();
1246     if (!m_textIterator.atEnd()) {
1247         if (m_textIterator.length() <= 1)
1248             ASSERT(m_runOffset == 0);
1249         else {
1250             Node* n = r->startContainer();
1251             ASSERT(n == r->endContainer());
1252             int offset = r->endOffset() - m_runOffset;
1253             ExceptionCode ec = 0;
1254             r->setStart(n, offset - 1, ec);
1255             r->setEnd(n, offset, ec);
1256             ASSERT(!ec);
1257         }
1258     }
1259     return r.release();
1260 }
1261
1262 void BackwardsCharacterIterator::advance(int count)
1263 {
1264     if (count <= 0) {
1265         ASSERT(!count);
1266         return;
1267     }
1268
1269     m_atBreak = false;
1270
1271     int remaining = m_textIterator.length() - m_runOffset;
1272     if (count < remaining) {
1273         m_runOffset += count;
1274         m_offset += count;
1275         return;
1276     }
1277
1278     count -= remaining;
1279     m_offset += remaining;
1280
1281     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1282         int runLength = m_textIterator.length();
1283         if (runLength == 0)
1284             m_atBreak = true;
1285         else {
1286             if (count < runLength) {
1287                 m_runOffset = count;
1288                 m_offset += count;
1289                 return;
1290             }
1291             
1292             count -= runLength;
1293             m_offset += runLength;
1294         }
1295     }
1296
1297     m_atBreak = true;
1298     m_runOffset = 0;
1299 }
1300
1301 // --------
1302
1303 WordAwareIterator::WordAwareIterator()
1304     : m_previousText(0)
1305     , m_didLookAhead(false)
1306 {
1307 }
1308
1309 WordAwareIterator::WordAwareIterator(const Range* r)
1310     : m_previousText(0)
1311     , m_didLookAhead(true) // so we consider the first chunk from the text iterator
1312     , m_textIterator(r)
1313 {
1314     advance(); // get in position over the first chunk of text
1315 }
1316
1317 // We're always in one of these modes:
1318 // - The current chunk in the text iterator is our current chunk
1319 //      (typically its a piece of whitespace, or text that ended with whitespace)
1320 // - The previous chunk in the text iterator is our current chunk
1321 //      (we looked ahead to the next chunk and found a word boundary)
1322 // - We built up our own chunk of text from many chunks from the text iterator
1323
1324 // FIXME: Performance could be bad for huge spans next to each other that don't fall on word boundaries.
1325
1326 void WordAwareIterator::advance()
1327 {
1328     m_previousText = 0;
1329     m_buffer.clear();      // toss any old buffer we built up
1330
1331     // If last time we did a look-ahead, start with that looked-ahead chunk now
1332     if (!m_didLookAhead) {
1333         ASSERT(!m_textIterator.atEnd());
1334         m_textIterator.advance();
1335     }
1336     m_didLookAhead = false;
1337
1338     // Go to next non-empty chunk 
1339     while (!m_textIterator.atEnd() && m_textIterator.length() == 0)
1340         m_textIterator.advance();
1341     m_range = m_textIterator.range();
1342
1343     if (m_textIterator.atEnd())
1344         return;
1345     
1346     while (1) {
1347         // If this chunk ends in whitespace we can just use it as our chunk.
1348         if (isSpaceOrNewline(m_textIterator.characters()[m_textIterator.length() - 1]))
1349             return;
1350
1351         // If this is the first chunk that failed, save it in previousText before look ahead
1352         if (m_buffer.isEmpty()) {
1353             m_previousText = m_textIterator.characters();
1354             m_previousLength = m_textIterator.length();
1355         }
1356
1357         // Look ahead to next chunk.  If it is whitespace or a break, we can use the previous stuff
1358         m_textIterator.advance();
1359         if (m_textIterator.atEnd() || m_textIterator.length() == 0 || isSpaceOrNewline(m_textIterator.characters()[0])) {
1360             m_didLookAhead = true;
1361             return;
1362         }
1363
1364         if (m_buffer.isEmpty()) {
1365             // Start gobbling chunks until we get to a suitable stopping point
1366             m_buffer.append(m_previousText, m_previousLength);
1367             m_previousText = 0;
1368         }
1369         m_buffer.append(m_textIterator.characters(), m_textIterator.length());
1370         int exception = 0;
1371         m_range->setEnd(m_textIterator.range()->endContainer(), m_textIterator.range()->endOffset(), exception);
1372     }
1373 }
1374
1375 int WordAwareIterator::length() const
1376 {
1377     if (!m_buffer.isEmpty())
1378         return m_buffer.size();
1379     if (m_previousText)
1380         return m_previousLength;
1381     return m_textIterator.length();
1382 }
1383
1384 const UChar* WordAwareIterator::characters() const
1385 {
1386     if (!m_buffer.isEmpty())
1387         return m_buffer.data();
1388     if (m_previousText)
1389         return m_previousText;
1390     return m_textIterator.characters();
1391 }
1392
1393 // --------
1394
1395 static inline UChar foldQuoteMark(UChar c)
1396 {
1397     switch (c) {
1398         case hebrewPunctuationGershayim:
1399         case leftDoubleQuotationMark:
1400         case rightDoubleQuotationMark:
1401             return '"';
1402         case hebrewPunctuationGeresh:
1403         case leftSingleQuotationMark:
1404         case rightSingleQuotationMark:
1405             return '\'';
1406         default:
1407             return c;
1408     }
1409 }
1410
1411 static inline void foldQuoteMarks(String& s)
1412 {
1413     s.replace(hebrewPunctuationGeresh, '\'');
1414     s.replace(hebrewPunctuationGershayim, '"');
1415     s.replace(leftDoubleQuotationMark, '"');
1416     s.replace(leftSingleQuotationMark, '\'');
1417     s.replace(rightDoubleQuotationMark, '"');
1418     s.replace(rightSingleQuotationMark, '\'');
1419 }
1420
1421 #if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION
1422
1423 static inline void foldQuoteMarks(UChar* data, size_t length)
1424 {
1425     for (size_t i = 0; i < length; ++i)
1426         data[i] = foldQuoteMark(data[i]);
1427 }
1428
1429 static const size_t minimumSearchBufferSize = 8192;
1430
1431 #ifndef NDEBUG
1432 static bool searcherInUse;
1433 #endif
1434
1435 static UStringSearch* createSearcher()
1436 {
1437     // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
1438     // but it doesn't matter exactly what it is, since we don't perform any searches
1439     // without setting both the pattern and the text.
1440     UErrorCode status = U_ZERO_ERROR;
1441     UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, currentSearchLocaleID(), 0, &status);
1442     ASSERT(status == U_ZERO_ERROR || status == U_USING_FALLBACK_WARNING || status == U_USING_DEFAULT_WARNING);
1443     return searcher;
1444 }
1445
1446 static UStringSearch* searcher()
1447 {
1448     static UStringSearch* searcher = createSearcher();
1449     return searcher;
1450 }
1451
1452 static inline void lockSearcher()
1453 {
1454 #ifndef NDEBUG
1455     ASSERT(!searcherInUse);
1456     searcherInUse = true;
1457 #endif
1458 }
1459
1460 static inline void unlockSearcher()
1461 {
1462 #ifndef NDEBUG
1463     ASSERT(searcherInUse);
1464     searcherInUse = false;
1465 #endif
1466 }
1467
1468 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1469     : m_target(target)
1470     , m_atBreak(true)
1471 {
1472     ASSERT(!m_target.isEmpty());
1473
1474     // FIXME: We'd like to tailor the searcher to fold quote marks for us instead
1475     // of doing it in a separate replacement pass here, but ICU doesn't offer a way
1476     // to add tailoring on top of the locale-specific tailoring as of this writing.
1477     foldQuoteMarks(m_target);
1478
1479     size_t targetLength = m_target.length();
1480     m_buffer.reserveInitialCapacity(max(targetLength * 8, minimumSearchBufferSize));
1481     m_overlap = m_buffer.capacity() / 4;
1482
1483     // Grab the single global searcher.
1484     // If we ever have a reason to do more than once search buffer at once, we'll have
1485     // to move to multiple searchers.
1486     lockSearcher();
1487
1488     UStringSearch* searcher = WebCore::searcher();
1489     UCollator* collator = usearch_getCollator(searcher);
1490
1491     UCollationStrength strength = isCaseSensitive ? UCOL_TERTIARY : UCOL_PRIMARY;
1492     if (ucol_getStrength(collator) != strength) {
1493         ucol_setStrength(collator, strength);
1494         usearch_reset(searcher);
1495     }
1496
1497     UErrorCode status = U_ZERO_ERROR;
1498     usearch_setPattern(searcher, m_target.characters(), targetLength, &status);
1499     ASSERT(status == U_ZERO_ERROR);
1500 }
1501
1502 inline SearchBuffer::~SearchBuffer()
1503 {
1504     unlockSearcher();
1505 }
1506
1507 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1508 {
1509     ASSERT(length);
1510
1511     if (m_atBreak) {
1512         m_buffer.shrink(0);
1513         m_atBreak = false;
1514     } else if (m_buffer.size() == m_buffer.capacity()) {
1515         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
1516         m_buffer.shrink(m_overlap);
1517     }
1518
1519     size_t oldLength = m_buffer.size();
1520     size_t usableLength = min(m_buffer.capacity() - oldLength, length);
1521     ASSERT(usableLength);
1522     m_buffer.append(characters, usableLength);
1523     foldQuoteMarks(m_buffer.data() + oldLength, usableLength);
1524     return usableLength;
1525 }
1526
1527 inline bool SearchBuffer::atBreak() const
1528 {
1529     return m_atBreak;
1530 }
1531
1532 inline void SearchBuffer::reachedBreak()
1533 {
1534     m_atBreak = true;
1535 }
1536
1537 inline size_t SearchBuffer::search(size_t& start)
1538 {
1539     size_t size = m_buffer.size();
1540     if (m_atBreak) {
1541         if (!size)
1542             return 0;
1543     } else {
1544         if (size != m_buffer.capacity())
1545             return 0;
1546     }
1547
1548     UStringSearch* searcher = WebCore::searcher();
1549
1550     UErrorCode status = U_ZERO_ERROR;
1551     usearch_setText(searcher, m_buffer.data(), size, &status);
1552     ASSERT(status == U_ZERO_ERROR);
1553
1554     int matchStart = usearch_first(searcher, &status);
1555     ASSERT(status == U_ZERO_ERROR);
1556     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
1557         ASSERT(matchStart == USEARCH_DONE);
1558         return 0;
1559     }
1560
1561     // Matches that start in the overlap area are only tentative.
1562     // The same match may appear later, matching more characters,
1563     // possibly including a combining character that's not yet in the buffer.
1564     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
1565         memcpy(m_buffer.data(), m_buffer.data() + size - m_overlap, m_overlap * sizeof(UChar));
1566         m_buffer.shrink(m_overlap);
1567         return 0;
1568     }
1569
1570     size_t newSize = size - (matchStart + 1);
1571     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
1572     m_buffer.shrink(newSize);
1573
1574     start = size - matchStart;
1575     return usearch_getMatchedLength(searcher);
1576 }
1577
1578 #else // !ICU_UNICODE
1579
1580 inline SearchBuffer::SearchBuffer(const String& target, bool isCaseSensitive)
1581     : m_target(isCaseSensitive ? target : target.foldCase())
1582     , m_isCaseSensitive(isCaseSensitive)
1583     , m_buffer(m_target.length())
1584     , m_isCharacterStartBuffer(m_target.length())
1585     , m_isBufferFull(false)
1586     , m_cursor(0)
1587 {
1588     ASSERT(!m_target.isEmpty());
1589     m_target.replace(noBreakSpace, ' ');
1590     foldQuoteMarks(m_target);
1591 }
1592
1593 inline SearchBuffer::~SearchBuffer()
1594 {
1595 }
1596
1597 inline void SearchBuffer::reachedBreak()
1598 {
1599     m_cursor = 0;
1600     m_isBufferFull = false;
1601 }
1602
1603 inline bool SearchBuffer::atBreak() const
1604 {
1605     return !m_cursor && !m_isBufferFull;
1606 }
1607
1608 inline void SearchBuffer::append(UChar c, bool isStart)
1609 {
1610     m_buffer[m_cursor] = c == noBreakSpace ? ' ' : foldQuoteMark(c);
1611     m_isCharacterStartBuffer[m_cursor] = isStart;
1612     if (++m_cursor == m_target.length()) {
1613         m_cursor = 0;
1614         m_isBufferFull = true;
1615     }
1616 }
1617
1618 inline size_t SearchBuffer::append(const UChar* characters, size_t length)
1619 {
1620     ASSERT(length);
1621     if (m_isCaseSensitive) {
1622         append(characters[0], true);
1623         return 1;
1624     }
1625     const int maxFoldedCharacters = 16; // sensible maximum is 3, this should be more than enough
1626     UChar foldedCharacters[maxFoldedCharacters];
1627     bool error;
1628     int numFoldedCharacters = foldCase(foldedCharacters, maxFoldedCharacters, characters, 1, &error);
1629     ASSERT(!error);
1630     ASSERT(numFoldedCharacters);
1631     ASSERT(numFoldedCharacters <= maxFoldedCharacters);
1632     if (!error && numFoldedCharacters) {
1633         numFoldedCharacters = min(numFoldedCharacters, maxFoldedCharacters);
1634         append(foldedCharacters[0], true);
1635         for (int i = 1; i < numFoldedCharacters; ++i)
1636             append(foldedCharacters[i], false);
1637     }
1638     return 1;
1639 }
1640
1641 inline size_t SearchBuffer::search(size_t& start)
1642 {
1643     if (!m_isBufferFull)
1644         return 0;
1645     if (!m_isCharacterStartBuffer[m_cursor])
1646         return 0;
1647
1648     size_t tailSpace = m_target.length() - m_cursor;
1649     if (memcmp(&m_buffer[m_cursor], m_target.characters(), tailSpace * sizeof(UChar)) != 0)
1650         return 0;
1651     if (memcmp(&m_buffer[0], m_target.characters() + tailSpace, m_cursor * sizeof(UChar)) != 0)
1652         return 0;
1653
1654     start = length();
1655
1656     // Now that we've found a match once, we don't want to find it again, because those
1657     // are the SearchBuffer semantics, allowing for a buffer where you append more than one
1658     // character at a time. To do this we take advantage of m_isCharacterStartBuffer, but if
1659     // we want to get rid of that in the future we could track this with a separate boolean
1660     // or even move the characters to the start of the buffer and set m_isBufferFull to false.
1661     m_isCharacterStartBuffer[m_cursor] = false;
1662
1663     return start;
1664 }
1665
1666 // Returns the number of characters that were appended to the buffer (what we are searching in).
1667 // That's not necessarily the same length as the passed-in target string, because case folding
1668 // can make two strings match even though they're not the same length.
1669 size_t SearchBuffer::length() const
1670 {
1671     size_t bufferSize = m_target.length();
1672     size_t length = 0;
1673     for (size_t i = 0; i < bufferSize; ++i)
1674         length += m_isCharacterStartBuffer[i];
1675     return length;
1676 }
1677
1678 #endif // !ICU_UNICODE
1679
1680 // --------
1681
1682 int TextIterator::rangeLength(const Range* r, bool forSelectionPreservation)
1683 {
1684     int length = 0;
1685     for (TextIterator it(r, forSelectionPreservation); !it.atEnd(); it.advance())
1686         length += it.length();
1687     
1688     return length;
1689 }
1690
1691 PassRefPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
1692 {
1693     CharacterIterator entireRangeIterator(entireRange);
1694     return characterSubrange(entireRangeIterator, characterOffset, characterCount);
1695 }
1696
1697 PassRefPtr<Range> TextIterator::rangeFromLocationAndLength(Element* scope, int rangeLocation, int rangeLength, bool forSelectionPreservation)
1698 {
1699     RefPtr<Range> resultRange = scope->document()->createRange();
1700
1701     int docTextPosition = 0;
1702     int rangeEnd = rangeLocation + rangeLength;
1703     bool startRangeFound = false;
1704
1705     RefPtr<Range> textRunRange;
1706
1707     TextIterator it(rangeOfContents(scope).get(), forSelectionPreservation);
1708     
1709     // FIXME: the atEnd() check shouldn't be necessary, workaround for <http://bugs.webkit.org/show_bug.cgi?id=6289>.
1710     if (rangeLocation == 0 && rangeLength == 0 && it.atEnd()) {
1711         textRunRange = it.range();
1712         
1713         ExceptionCode ec = 0;
1714         resultRange->setStart(textRunRange->startContainer(), 0, ec);
1715         ASSERT(!ec);
1716         resultRange->setEnd(textRunRange->startContainer(), 0, ec);
1717         ASSERT(!ec);
1718         
1719         return resultRange.release();
1720     }
1721
1722     for (; !it.atEnd(); it.advance()) {
1723         int len = it.length();
1724         textRunRange = it.range();
1725         
1726         bool foundStart = rangeLocation >= docTextPosition && rangeLocation <= docTextPosition + len;
1727         bool foundEnd = rangeEnd >= docTextPosition && rangeEnd <= docTextPosition + len;
1728         
1729         // Fix textRunRange->endPosition(), but only if foundStart || foundEnd, because it is only
1730         // in those cases that textRunRange is used.
1731         if (foundStart || foundEnd) {
1732             // FIXME: This is a workaround for the fact that the end of a run is often at the wrong
1733             // position for emitted '\n's.
1734             if (len == 1 && it.characters()[0] == '\n') {
1735                 Position runStart = textRunRange->startPosition();
1736                 Position runEnd = VisiblePosition(runStart).next().deepEquivalent();
1737                 if (runEnd.isNotNull()) {
1738                     ExceptionCode ec = 0;
1739                     textRunRange->setEnd(runEnd.node(), runEnd.deprecatedEditingOffset(), ec);
1740                     ASSERT(!ec);
1741                 }
1742             }
1743         }
1744
1745         if (foundStart) {
1746             startRangeFound = true;
1747             int exception = 0;
1748             if (textRunRange->startContainer()->isTextNode()) {
1749                 int offset = rangeLocation - docTextPosition;
1750                 resultRange->setStart(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1751             } else {
1752                 if (rangeLocation == docTextPosition)
1753                     resultRange->setStart(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1754                 else
1755                     resultRange->setStart(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1756             }
1757         }
1758
1759         if (foundEnd) {
1760             int exception = 0;
1761             if (textRunRange->startContainer()->isTextNode()) {
1762                 int offset = rangeEnd - docTextPosition;
1763                 resultRange->setEnd(textRunRange->startContainer(), offset + textRunRange->startOffset(), exception);
1764             } else {
1765                 if (rangeEnd == docTextPosition)
1766                     resultRange->setEnd(textRunRange->startContainer(), textRunRange->startOffset(), exception);
1767                 else
1768                     resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1769             }
1770             docTextPosition += len;
1771             break;
1772         }
1773         docTextPosition += len;
1774     }
1775     
1776     if (!startRangeFound)
1777         return 0;
1778     
1779     if (rangeLength != 0 && rangeEnd > docTextPosition) { // rangeEnd is out of bounds
1780         int exception = 0;
1781         resultRange->setEnd(textRunRange->endContainer(), textRunRange->endOffset(), exception);
1782     }
1783     
1784     return resultRange.release();
1785 }
1786
1787 // --------
1788     
1789 UChar* plainTextToMallocAllocatedBuffer(const Range* r, unsigned& bufferLength, bool isDisplayString) 
1790 {
1791     UChar* result = 0;
1792
1793     // Do this in pieces to avoid massive reallocations if there is a large amount of text.
1794     // Use system malloc for buffers since they can consume lots of memory and current TCMalloc is unable return it back to OS.
1795     static const unsigned cMaxSegmentSize = 1 << 16;
1796     bufferLength = 0;
1797     typedef pair<UChar*, unsigned> TextSegment;
1798     Vector<TextSegment>* textSegments = 0;
1799     Vector<UChar> textBuffer;
1800     textBuffer.reserveInitialCapacity(cMaxSegmentSize);
1801     for (TextIterator it(r); !it.atEnd(); it.advance()) {
1802         if (textBuffer.size() && textBuffer.size() + it.length() > cMaxSegmentSize) {
1803             UChar* newSegmentBuffer = static_cast<UChar*>(malloc(textBuffer.size() * sizeof(UChar)));
1804             if (!newSegmentBuffer)
1805                 goto exit;
1806             memcpy(newSegmentBuffer, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1807             if (!textSegments)
1808                 textSegments = new Vector<TextSegment>;
1809             textSegments->append(make_pair(newSegmentBuffer, (unsigned)textBuffer.size()));
1810             textBuffer.clear();
1811         }
1812         textBuffer.append(it.characters(), it.length());
1813         bufferLength += it.length();
1814     }
1815
1816     if (!bufferLength)
1817         return 0;
1818
1819     // Since we know the size now, we can make a single buffer out of the pieces with one big alloc
1820     result = static_cast<UChar*>(malloc(bufferLength * sizeof(UChar)));
1821     if (!result)
1822         goto exit;
1823
1824     {
1825         UChar* resultPos = result;
1826         if (textSegments) {
1827             unsigned size = textSegments->size();
1828             for (unsigned i = 0; i < size; ++i) {
1829                 const TextSegment& segment = textSegments->at(i);
1830                 memcpy(resultPos, segment.first, segment.second * sizeof(UChar));
1831                 resultPos += segment.second;
1832             }
1833         }
1834         memcpy(resultPos, textBuffer.data(), textBuffer.size() * sizeof(UChar));
1835     }
1836
1837 exit:
1838     if (textSegments) {
1839         unsigned size = textSegments->size();
1840         for (unsigned i = 0; i < size; ++i)
1841             free(textSegments->at(i).first);
1842         delete textSegments;
1843     }
1844     
1845     if (isDisplayString && r->ownerDocument())
1846         r->ownerDocument()->displayBufferModifiedByEncoding(result, bufferLength);
1847
1848     return result;
1849 }
1850
1851 String plainText(const Range* r)
1852 {
1853     unsigned length;
1854     UChar* buf = plainTextToMallocAllocatedBuffer(r, length, false);
1855     if (!buf)
1856         return "";
1857     String result(buf, length);
1858     free(buf);
1859     return result;
1860 }
1861
1862 static inline bool isAllCollapsibleWhitespace(const String& string)
1863 {
1864     const UChar* characters = string.characters();
1865     unsigned length = string.length();
1866     for (unsigned i = 0; i < length; ++i) {
1867         if (!isCollapsibleWhitespace(characters[i]))
1868             return false;
1869     }
1870     return true;
1871 }
1872
1873 static PassRefPtr<Range> collapsedToBoundary(const Range* range, bool forward)
1874 {
1875     ExceptionCode ec = 0;
1876     RefPtr<Range> result = range->cloneRange(ec);
1877     ASSERT(!ec);
1878     result->collapse(!forward, ec);
1879     ASSERT(!ec);
1880     return result.release();
1881 }
1882
1883 static size_t findPlainText(CharacterIterator& it, const String& target, bool forward, bool caseSensitive, size_t& matchStart)
1884 {
1885     matchStart = 0;
1886     size_t matchLength = 0;
1887
1888     SearchBuffer buffer(target, caseSensitive);
1889
1890     while (!it.atEnd()) {
1891         it.advance(buffer.append(it.characters(), it.length()));
1892 tryAgain:
1893         size_t matchStartOffset;
1894         if (size_t newMatchLength = buffer.search(matchStartOffset)) {
1895             // Note that we found a match, and where we found it.
1896             size_t lastCharacterInBufferOffset = it.characterOffset();
1897             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
1898             matchStart = lastCharacterInBufferOffset - matchStartOffset;
1899             matchLength = newMatchLength;
1900             // If searching forward, stop on the first match.
1901             // If searching backward, don't stop, so we end up with the last match.
1902             if (forward)
1903                 break;
1904             goto tryAgain;
1905         }
1906         if (it.atBreak() && !buffer.atBreak()) {
1907             buffer.reachedBreak();
1908             goto tryAgain;
1909         }
1910     }
1911
1912     return matchLength;
1913 }
1914
1915 PassRefPtr<Range> findPlainText(const Range* range, const String& target, bool forward, bool caseSensitive)
1916 {
1917     // First, find the text.
1918     size_t matchStart;
1919     size_t matchLength;
1920     {
1921         CharacterIterator findIterator(range, false, true);
1922         matchLength = findPlainText(findIterator, target, forward, caseSensitive, matchStart);
1923         if (!matchLength)
1924             return collapsedToBoundary(range, forward);
1925     }
1926
1927     // Then, find the document position of the start and the end of the text.
1928     CharacterIterator computeRangeIterator(range, false, true);
1929     return characterSubrange(computeRangeIterator, matchStart, matchLength);
1930 }
1931
1932 }