1 /*

     2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 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     bool isBadMatch(const UChar*, size_t length) const;

    77 

    78     String m_target;

    79     Vector<UChar> m_buffer;

    80     size_t m_overlap;

    81     bool m_atBreak;

    82 

    83     bool m_targetRequiresKanaWorkaround;

    84     Vector<UChar> m_normalizedTarget;

    85     mutable Vector<UChar> m_normalizedMatch;

    86 

    87 #else

    88 

    89 private:

    90     void append(UChar, bool isCharacterStart);

    91     size_t length() const;

    92 

    93     String m_target;

    94     bool m_isCaseSensitive;

    95 

    96     Vector<UChar> m_buffer;

    97     Vector<bool> m_isCharacterStartBuffer;

    98     bool m_isBufferFull;

    99     size_t m_cursor;

   100 

   101 #endif

   102 };

   103 

   104 // --------

   105 

   106 static const unsigned bitsInWord = sizeof(unsigned) * 8;

   107 static const unsigned bitInWordMask = bitsInWord - 1;

   108 

   109 BitStack::BitStack()

   110     : m_size(0)

   111 {

   112 }

   113 

   114 void BitStack::push(bool bit)

   115 {

   116     unsigned index = m_size / bitsInWord;

   117     unsigned shift = m_size & bitInWordMask;

   118     if (!shift && index == m_words.size()) {

   119         m_words.grow(index + 1);

   120         m_words[index] = 0;

   121     }

   122     unsigned& word = m_words[index];

   123     unsigned mask = 1U << shift;

   124     if (bit)

   125         word |= mask;

   126     else

   127         word &= ~mask;

   128     ++m_size;

   129 }

   130 

   131 void BitStack::pop()

   132 {

   133     if (m_size)

   134         --m_size;

   135 }

   136 

   137 bool BitStack::top() const

   138 {

   139     if (!m_size)

   140         return false;

   141     unsigned shift = (m_size - 1) & bitInWordMask;

   142     return m_words.last() & (1U << shift);

   143 }

   144 

   145 unsigned BitStack::size() const

   146 {

   147     return m_size;

   148 }

   149 

   150 // --------

   151 

   152 static inline Node* parentCrossingShadowBoundaries(Node* node)

   153 {

   154     if (Node* parent = node->parentNode())

   155         return parent;

   156     return node->shadowParentNode();

   157 }

   158 

   159 #if !ASSERT_DISABLED

   160 

   161 static unsigned depthCrossingShadowBoundaries(Node* node)

   162 {

   163     unsigned depth = 0;

   164     for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))

   165         ++depth;

   166     return depth;

   167 }

   168 

   169 #endif

   170 

   171 // This function is like Range::pastLastNode, except for the fact that it can climb up out of shadow trees.

   172 static Node* nextInPreOrderCrossingShadowBoundaries(Node* rangeEndContainer, int rangeEndOffset)

   173 {

   174     if (!rangeEndContainer)

   175         return 0;

   176     if (rangeEndOffset >= 0 && !rangeEndContainer->offsetInCharacters()) {

   177         if (Node* next = rangeEndContainer->childNode(rangeEndOffset))

   178             return next;

   179     }

   180     for (Node* node = rangeEndContainer; node; node = parentCrossingShadowBoundaries(node)) {

   181         if (Node* next = node->nextSibling())

   182             return next;

   183     }

   184     return 0;

   185 }

   186 

   187 static Node* previousInPostOrderCrossingShadowBoundaries(Node* rangeStartContainer, int rangeStartOffset)

   188 {

   189     if (!rangeStartContainer)

   190         return 0;

   191     if (rangeStartOffset > 0 && !rangeStartContainer->offsetInCharacters()) {

   192         if (Node* previous = rangeStartContainer->childNode(rangeStartOffset - 1))

   193             return previous;

   194     }

   195     for (Node* node = rangeStartContainer; node; node = parentCrossingShadowBoundaries(node)) {

   196         if (Node* previous = node->previousSibling())

   197             return previous;

   198     }

   199     return 0;

   200 }

   201 

   202 // --------

   203 

   204 static inline bool fullyClipsContents(Node* node)

   205 {

   206     RenderObject* renderer = node->renderer();

   207     if (!renderer || !renderer->isBox() || !renderer->hasOverflowClip())

   208         return false;

   209     return toRenderBox(renderer)->size().isEmpty();

   210 }

   211 

   212 static inline bool ignoresContainerClip(Node* node)

   213 {

   214     RenderObject* renderer = node->renderer();

   215     if (!renderer || renderer->isText())

   216         return false;

   217     EPosition position = renderer->style()->position();

   218     return position == AbsolutePosition || position == FixedPosition;

   219 }

   220 

   221 static void pushFullyClippedState(BitStack& stack, Node* node)

   222 {

   223     ASSERT(stack.size() == depthCrossingShadowBoundaries(node));

   224 

   225     // Push true if this node full clips its contents, or if a parent already has fully

   226     // clipped and this is not a node that ignores its container's clip.

   227     stack.push(fullyClipsContents(node) || (stack.top() && !ignoresContainerClip(node)));

   228 }

   229 

   230 static void setUpFullyClippedStack(BitStack& stack, Node* node)

   231 {

   232     // Put the nodes in a vector so we can iterate in reverse order.

   233     Vector<Node*, 100> ancestry;

   234     for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))

   235         ancestry.append(parent);

   236 

   237     // Call pushFullyClippedState on each node starting with the earliest ancestor.

   238     size_t size = ancestry.size();

   239     for (size_t i = 0; i < size; ++i)

   240         pushFullyClippedState(stack, ancestry[size - i - 1]);

   241     pushFullyClippedState(stack, node);

   242 

   243     ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));

   244 }

   245 

   246 // --------

   247 

   248 TextIterator::TextIterator()

   249     : m_startContainer(0)

   250     , m_startOffset(0)

   251     , m_endContainer(0)

   252     , m_endOffset(0)

   253     , m_positionNode(0)

   254     , m_textCharacters(0)

   255     , m_textLength(0)

   256     , m_lastCharacter(0)

   257     , m_emitsCharactersBetweenAllVisiblePositions(false)

   258     , m_entersTextControls(false)

   259     , m_emitsTextWithoutTranscoding(false)

   260 {

   261 }

   262 

   263 TextIterator::TextIterator(const Range* r, TextIteratorBehavior behavior)

   264     : m_startContainer(0)

   265     , m_startOffset(0)

   266     , m_endContainer(0)

   267     , m_endOffset(0)

   268     , m_positionNode(0)

   269     , m_textCharacters(0)

   270     , m_textLength(0)

   271     , m_emitsCharactersBetweenAllVisiblePositions(behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions)

   272     , m_entersTextControls(behavior & TextIteratorEntersTextControls)

   273     , m_emitsTextWithoutTranscoding(behavior & TextIteratorEmitsTextsWithoutTranscoding)

   274 {

   275     if (!r)

   276         return;

   277 

   278     // get and validate the range endpoints

   279     Node* startContainer = r->startContainer();

   280     if (!startContainer)

   281         return;

   282     int startOffset = r->startOffset();

   283     Node* endContainer = r->endContainer();

   284     int endOffset = r->endOffset();

   285 

   286     // Callers should be handing us well-formed ranges. If we discover that this isn't

   287     // the case, we could consider changing this assertion to an early return.

   288     ASSERT(r->boundaryPointsValid());

   289 

   290     // remember range - this does not change

   291     m_startContainer = startContainer;

   292     m_startOffset = startOffset;

   293     m_endContainer = endContainer;

   294     m_endOffset = endOffset;

   295 

   296     // set up the current node for processing

   297     m_node = r->firstNode();

   298     if (!m_node)

   299         return;

   300     setUpFullyClippedStack(m_fullyClippedStack, m_node);

   301     m_offset = m_node == m_startContainer ? m_startOffset : 0;

   302     m_handledNode = false;

   303     m_handledChildren = false;

   304 

   305     // calculate first out of bounds node

   306     m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(endContainer, endOffset);

   307 

   308     // initialize node processing state

   309     m_needsAnotherNewline = false;

   310     m_textBox = 0;

   311 

   312     // initialize record of previous node processing

   313     m_hasEmitted = false;

   314     m_lastTextNode = 0;

   315     m_lastTextNodeEndedWithCollapsedSpace = false;

   316     m_lastCharacter = 0;

   317 

   318 #ifndef NDEBUG

   319     // need this just because of the assert in advance()

   320     m_positionNode = m_node;

   321 #endif

   322 

   323     // identify the first run

   324     advance();

   325 }

   326 

   327 void TextIterator::advance()

   328 {

   329     // reset the run information

   330     m_positionNode = 0;

   331     m_textLength = 0;

   332 

   333     // handle remembered node that needed a newline after the text node's newline

   334     if (m_needsAnotherNewline) {

   335         // Emit the extra newline, and position it *inside* m_node, after m_node's 

   336         // contents, in case it's a block, in the same way that we position the first 

   337         // newline.  The range for the emitted newline should start where the line 

   338         // break begins.

   339         // FIXME: It would be cleaner if we emitted two newlines during the last 

   340         // iteration, instead of using m_needsAnotherNewline.

   341         Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;

   342         emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);

   343         m_needsAnotherNewline = false;

   344         return;

   345     }

   346 

   347     // handle remembered text box

   348     if (m_textBox) {

   349         handleTextBox();

   350         if (m_positionNode)

   351             return;

   352     }

   353 

   354     while (m_node && m_node != m_pastEndNode) {

   355         // if the range ends at offset 0 of an element, represent the

   356         // position, but not the content, of that element e.g. if the

   357         // node is a blockflow element, emit a newline that

   358         // precedes the element

   359         if (m_node == m_endContainer && m_endOffset == 0) {

   360             representNodeOffsetZero();

   361             m_node = 0;

   362             return;

   363         }

   364         

   365         RenderObject* renderer = m_node->renderer();

   366         if (!renderer) {

   367             m_handledNode = true;

   368             m_handledChildren = true;

   369         } else {

   370             // handle current node according to its type

   371             if (!m_handledNode) {

   372                 if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) // FIXME: What about CDATA_SECTION_NODE?

   373                     m_handledNode = handleTextNode();

   374                 else if (renderer && (renderer->isImage() || renderer->isWidget() ||

   375                          (renderer->node() && renderer->node()->isElementNode() &&

   376                           static_cast<Element*>(renderer->node())->isFormControlElement())))

   377                     m_handledNode = handleReplacedElement();

   378                 else

   379                     m_handledNode = handleNonTextNode();

   380                 if (m_positionNode)

   381                     return;

   382             }

   383         }

   384 

   385         // find a new current node to handle in depth-first manner,

   386         // calling exitNode() as we come back thru a parent node

   387         Node* next = m_handledChildren ? 0 : m_node->firstChild();

   388         m_offset = 0;

   389         if (!next) {

   390             next = m_node->nextSibling();

   391             if (!next) {

   392                 bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;

   393                 Node* parentNode = parentCrossingShadowBoundaries(m_node);

   394                 while (!next && parentNode) {

   395                     if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))

   396                         return;

   397                     bool haveRenderer = m_node->renderer();

   398                     m_node = parentNode;

   399                     m_fullyClippedStack.pop();

   400                     parentNode = parentCrossingShadowBoundaries(m_node);

   401                     if (haveRenderer)

   402                         exitNode();

   403                     if (m_positionNode) {

   404                         m_handledNode = true;

   405                         m_handledChildren = true;

   406                         return;

   407                     }

   408                     next = m_node->nextSibling();

   409                 }

   410             }

   411             m_fullyClippedStack.pop();            

   412         }

   413 

   414         // set the new current node

   415         m_node = next;

   416         if (m_node)

   417             pushFullyClippedState(m_fullyClippedStack, m_node);

   418         m_handledNode = false;

   419         m_handledChildren = false;

   420 

   421         // how would this ever be?

   422         if (m_positionNode)

   423             return;

   424     }

   425 }

   426 

   427 static inline bool compareBoxStart(const InlineTextBox* first, const InlineTextBox* second)

   428 {

   429     return first->start() < second->start();

   430 }

   431 

   432 bool TextIterator::handleTextNode()

   433 {

   434     if (m_fullyClippedStack.top())

   435         return false;

   436 

   437     RenderText* renderer = toRenderText(m_node->renderer());

   438     if (renderer->style()->visibility() != VISIBLE)

   439         return false;

   440         

   441     m_lastTextNode = m_node;

   442     String str = renderer->text();

   443 

   444     // handle pre-formatted text

   445     if (!renderer->style()->collapseWhiteSpace()) {

   446         int runStart = m_offset;

   447         if (m_lastTextNodeEndedWithCollapsedSpace) {

   448             emitCharacter(' ', m_node, 0, runStart, runStart);

   449             return false;

   450         }

   451         int strLength = str.length();

   452         int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;

   453         int runEnd = min(strLength, end);

   454 

   455         if (runStart >= runEnd)

   456             return true;

   457 

   458         emitText(m_node, runStart, runEnd);

   459         return true;

   460     }

   461 

   462     if (!renderer->firstTextBox() && str.length() > 0) {

   463         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space

   464         return true;

   465     }

   466 

   467     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)

   468     if (renderer->containsReversedText()) {

   469         m_sortedTextBoxes.clear();

   470         for (InlineTextBox* textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {

   471             m_sortedTextBoxes.append(textBox);

   472         }

   473         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 

   474         m_sortedTextBoxesPosition = 0;

   475     }

   476     

   477     m_textBox = renderer->containsReversedText() ? (m_sortedTextBoxes.isEmpty() ? 0 : m_sortedTextBoxes[0]) : renderer->firstTextBox();

   478     handleTextBox();

   479     return true;

   480 }

   481 

   482 void TextIterator::handleTextBox()

   483 {    

   484     RenderText* renderer = toRenderText(m_node->renderer());

   485     String str = renderer->text();

   486     int start = m_offset;

   487     int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;

   488     while (m_textBox) {

   489         int textBoxStart = m_textBox->start();

   490         int runStart = max(textBoxStart, start);

   491 

   492         // Check for collapsed space at the start of this run.

   493         InlineTextBox* firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();

   494         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace

   495             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);

   496         if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {

   497             if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {

   498                 unsigned spaceRunStart = runStart - 1;

   499                 while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')

   500                     --spaceRunStart;

   501                 emitText(m_node, spaceRunStart, spaceRunStart + 1);

   502             } else

   503                 emitCharacter(' ', m_node, 0, runStart, runStart);

   504             return;

   505         }

   506         int textBoxEnd = textBoxStart + m_textBox->len();

   507         int runEnd = min(textBoxEnd, end);

   508         

   509         // Determine what the next text box will be, but don't advance yet

   510         InlineTextBox* nextTextBox = 0;

   511         if (renderer->containsReversedText()) {

   512             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())

   513                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];

   514         } else 

   515             nextTextBox = m_textBox->nextTextBox();

   516 

   517         if (runStart < runEnd) {

   518             // Handle either a single newline character (which becomes a space),

   519             // or a run of characters that does not include a newline.

   520             // This effectively translates newlines to spaces without copying the text.

   521             if (str[runStart] == '\n') {

   522                 emitCharacter(' ', m_node, 0, runStart, runStart + 1);

   523                 m_offset = runStart + 1;

   524             } else {

   525                 int subrunEnd = str.find('\n', runStart);

   526                 if (subrunEnd == -1 || subrunEnd > runEnd)

   527                     subrunEnd = runEnd;

   528     

   529                 m_offset = subrunEnd;

   530                 emitText(m_node, runStart, subrunEnd);

   531             }

   532 

   533             // If we are doing a subrun that doesn't go to the end of the text box,

   534             // come back again to finish handling this text box; don't advance to the next one.

   535             if (m_positionEndOffset < textBoxEnd)

   536                 return;

   537 

   538             // Advance and return

   539             int nextRunStart = nextTextBox ? nextTextBox->start() : str.length();

   540             if (nextRunStart > runEnd)

   541                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end

   542             m_textBox = nextTextBox;

   543             if (renderer->containsReversedText())

   544                 ++m_sortedTextBoxesPosition;

   545             return;

   546         }

   547         // Advance and continue

   548         m_textBox = nextTextBox;

   549         if (renderer->containsReversedText())

   550             ++m_sortedTextBoxesPosition;

   551     }

   552 }

   553 

   554 bool TextIterator::handleReplacedElement()

   555 {

   556     if (m_fullyClippedStack.top())

   557         return false;

   558 

   559     RenderObject* renderer = m_node->renderer();

   560     if (renderer->style()->visibility() != VISIBLE)

   561         return false;

   562 

   563     if (m_lastTextNodeEndedWithCollapsedSpace) {

   564         emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);

   565         return false;

   566     }

   567 

   568     if (m_entersTextControls && renderer->isTextControl()) {

   569         if (HTMLElement* innerTextElement = toRenderTextControl(renderer)->innerTextElement()) {

   570             m_node = innerTextElement->shadowTreeRootNode();

   571             pushFullyClippedState(m_fullyClippedStack, m_node);

   572             m_offset = 0;

   573             return false;

   574         }

   575     }

   576 

   577     m_hasEmitted = true;

   578 

   579     if (m_emitsCharactersBetweenAllVisiblePositions) {

   580         // We want replaced elements to behave like punctuation for boundary 

   581         // finding, and to simply take up space for the selection preservation 

   582         // code in moveParagraphs, so we use a comma.

   583         emitCharacter(',', m_node->parentNode(), m_node, 0, 1);

   584         return true;

   585     }

   586 

   587     m_positionNode = m_node->parentNode();

   588     m_positionOffsetBaseNode = m_node;

   589     m_positionStartOffset = 0;

   590     m_positionEndOffset = 1;

   591 

   592     m_textCharacters = 0;

   593     m_textLength = 0;

   594 

   595     m_lastCharacter = 0;

   596 

   597     return true;

   598 }

   599 

   600 static bool shouldEmitTabBeforeNode(Node* node)

   601 {

   602     RenderObject* r = node->renderer();

   603     

   604     // Table cells are delimited by tabs.

   605     if (!r || !isTableCell(node))

   606         return false;

   607     

   608     // Want a tab before every cell other than the first one

   609     RenderTableCell* rc = toRenderTableCell(r);

   610     RenderTable* t = rc->table();

   611     return t && (t->cellBefore(rc) || t->cellAbove(rc));

   612 }

   613 

   614 static bool shouldEmitNewlineForNode(Node* node)

   615 {

   616     // br elements are represented by a single newline.

   617     RenderObject* r = node->renderer();

   618     if (!r)

   619         return node->hasTagName(brTag);

   620         

   621     return r->isBR();

   622 }

   623 

   624 static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)

   625 {

   626     // Block flow (versus inline flow) is represented by having

   627     // a newline both before and after the element.

   628     RenderObject* r = node->renderer();

   629     if (!r) {

   630         return (node->hasTagName(blockquoteTag)

   631                 || node->hasTagName(ddTag)

   632                 || node->hasTagName(divTag)

   633                 || node->hasTagName(dlTag)

   634                 || node->hasTagName(dtTag)

   635                 || node->hasTagName(h1Tag)

   636                 || node->hasTagName(h2Tag)

   637                 || node->hasTagName(h3Tag)

   638                 || node->hasTagName(h4Tag)

   639                 || node->hasTagName(h5Tag)

   640                 || node->hasTagName(h6Tag)

   641                 || node->hasTagName(hrTag)

   642                 || node->hasTagName(liTag)

   643                 || node->hasTagName(listingTag)

   644                 || node->hasTagName(olTag)

   645                 || node->hasTagName(pTag)

   646                 || node->hasTagName(preTag)

   647                 || node->hasTagName(trTag)

   648                 || node->hasTagName(ulTag));

   649     }

   650     

   651     // Need to make an exception for table cells, because they are blocks, but we

   652     // want them tab-delimited rather than having newlines before and after.

   653     if (isTableCell(node))

   654         return false;

   655     

   656     // Need to make an exception for table row elements, because they are neither

   657     // "inline" or "RenderBlock", but we want newlines for them.

   658     if (r->isTableRow()) {

   659         RenderTable* t = toRenderTableRow(r)->table();

   660         if (t && !t->isInline())

   661             return true;

   662     }

   663     

   664     return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();

   665 }

   666 

   667 static bool shouldEmitNewlineAfterNode(Node* node)

   668 {

   669     // FIXME: It should be better but slower to create a VisiblePosition here.

   670     if (!shouldEmitNewlinesBeforeAndAfterNode(node))

   671         return false;

   672     // Check if this is the very last renderer in the document.

   673     // If so, then we should not emit a newline.

   674     while ((node = node->traverseNextSibling()))

   675         if (node->renderer())

   676             return true;

   677     return false;

   678 }

   679 

   680 static bool shouldEmitNewlineBeforeNode(Node* node)

   681 {

   682     return shouldEmitNewlinesBeforeAndAfterNode(node); 

   683 }

   684 

   685 static bool shouldEmitExtraNewlineForNode(Node* node)

   686 {

   687     // When there is a significant collapsed bottom margin, emit an extra

   688     // newline for a more realistic result.  We end up getting the right

   689     // result even without margin collapsing. For example: <div><p>text</p></div>

   690     // will work right even if both the <div> and the <p> have bottom margins.

   691     RenderObject* r = node->renderer();

   692     if (!r || !r->isBox())

   693         return false;

   694     

   695     // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears

   696     // not to do this at all

   697     if (node->hasTagName(h1Tag)

   698         || node->hasTagName(h2Tag)

   699         || node->hasTagName(h3Tag)

   700         || node->hasTagName(h4Tag)

   701         || node->hasTagName(h5Tag)

   702         || node->hasTagName(h6Tag)

   703         || node->hasTagName(pTag)) {

   704         RenderStyle* style = r->style();

   705         if (style) {

   706             int bottomMargin = toRenderBox(r)->collapsedMarginBottom();

   707             int fontSize = style->fontDescription().computedPixelSize();

   708             if (bottomMargin * 2 >= fontSize)

   709                 return true;

   710         }

   711     }

   712     

   713     return false;

   714 }

   715 

   716 static int collapsedSpaceLength(RenderText* renderer, int textEnd)

   717 {

   718     const UChar* characters = renderer->text()->characters();

   719     int length = renderer->text()->length();

   720     for (int i = textEnd; i < length; ++i) {

   721         if (!renderer->style()->isCollapsibleWhiteSpace(characters[i]))

   722             return i - textEnd;

   723     }

   724 

   725     return length - textEnd;

   726 }

   727 

   728 static int maxOffsetIncludingCollapsedSpaces(Node* node)

   729 {

   730     int offset = caretMaxOffset(node);

   731 

   732     if (node->renderer() && node->renderer()->isText())

   733         offset += collapsedSpaceLength(toRenderText(node->renderer()), offset);

   734 

   735     return offset;

   736 }

   737 

   738 // 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).

   739 bool TextIterator::shouldRepresentNodeOffsetZero()

   740 {

   741     if (m_emitsCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isTable())

   742         return true;

   743         

   744     // Leave element positioned flush with start of a paragraph

   745     // (e.g. do not insert tab before a table cell at the start of a paragraph)

   746     if (m_lastCharacter == '\n')

   747         return false;

   748     

   749     // Otherwise, show the position if we have emitted any characters

   750     if (m_hasEmitted)

   751         return true;

   752     

   753     // We've not emitted anything yet. Generally, there is no need for any positioning then.

   754     // The only exception is when the element is visually not in the same line as

   755     // the start of the range (e.g. the range starts at the end of the previous paragraph).

   756     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we

   757     // make quicker checks to possibly avoid that. Another check that we could make is

   758     // is whether the inline vs block flow changed since the previous visible element.

   759     // I think we're already in a special enough case that that won't be needed, tho.

   760 

   761     // No character needed if this is the first node in the range.

   762     if (m_node == m_startContainer)

   763         return false;

   764     

   765     // If we are outside the start container's subtree, assume we need to emit.

   766     // FIXME: m_startContainer could be an inline block

   767     if (!m_node->isDescendantOf(m_startContainer))

   768         return true;

   769 

   770     // If we started as m_startContainer offset 0 and the current node is a descendant of

   771     // the start container, we already had enough context to correctly decide whether to

   772     // emit after a preceding block. We chose not to emit (m_hasEmitted is false),

   773     // so don't second guess that now.

   774     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably

   775     // immaterial since we likely would have already emitted something by now.

   776     if (m_startOffset == 0)

   777         return false;

   778         

   779     // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning.

   780     // Additionally, if the range we are iterating over contains huge sections of unrendered content, 

   781     // we would create VisiblePositions on every call to this function without this check.

   782     if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE)

   783         return false;

   784     

   785     // The startPos.isNotNull() check is needed because the start could be before the body,

   786     // and in that case we'll get null. We don't want to put in newlines at the start in that case.

   787     // The currPos.isNotNull() check is needed because positions in non-HTML content

   788     // (like SVG) do not have visible positions, and we don't want to emit for them either.

   789     VisiblePosition startPos = VisiblePosition(m_startContainer, m_startOffset, DOWNSTREAM);

   790     VisiblePosition currPos = VisiblePosition(m_node, 0, DOWNSTREAM);

   791     return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos);

   792 }

   793 

   794 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)

   795 {

   796     return node->renderer() && node->renderer()->isTable() && (node->renderer()->isInline() || m_emitsCharactersBetweenAllVisiblePositions);

   797 }

   798 

   799 void TextIterator::representNodeOffsetZero()

   800 {

   801     // Emit a character to show the positioning of m_node.

   802     

   803     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can 

   804     // create VisiblePositions, which is expensive.  So, we perform the inexpensive checks

   805     // on m_node to see if it necessitates emitting a character first and will early return 

   806     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.

   807     if (shouldEmitTabBeforeNode(m_node)) {

   808         if (shouldRepresentNodeOffsetZero())

   809             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);

   810     } else if (shouldEmitNewlineBeforeNode(m_node)) {

   811         if (shouldRepresentNodeOffsetZero())

   812             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);

   813     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {

   814         if (shouldRepresentNodeOffsetZero())

   815             emitCharacter(' ', m_node->parentNode(), m_node, 0, 0);

   816     }

   817 }

   818 

   819 bool TextIterator::handleNonTextNode()

   820 {

   821     if (shouldEmitNewlineForNode(m_node))

   822         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);

   823     else if (m_emitsCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())

   824         emitCharacter(' ', m_node->parentNode(), m_node, 0, 1);

   825     else

   826         representNodeOffsetZero();

   827 

   828     return true;

   829 }

   830 

   831 void TextIterator::exitNode()

   832 {

   833     // prevent emitting a newline when exiting a collapsed block at beginning of the range

   834     // FIXME: !m_hasEmitted does not necessarily mean there was a collapsed block... it could

   835     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and

   836     // therefore look like a blank line.

   837     if (!m_hasEmitted)

   838         return;

   839         

   840     // Emit with a position *inside* m_node, after m_node's contents, in 

   841     // case it is a block, because the run should start where the 

   842     // emitted character is positioned visually.

   843     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;

   844     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making

   845     // the logic in _web_attributedStringFromRange match.  We'll get that for free when we switch to use

   846     // TextIterator in _web_attributedStringFromRange.

   847     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.

   848     if (m_lastTextNode && shouldEmitNewlineAfterNode(m_node)) {

   849         // use extra newline to represent margin bottom, as needed

   850         bool addNewline = shouldEmitExtraNewlineForNode(m_node);

   851         

   852         // FIXME: We need to emit a '\n' as we leave an empty block(s) that

   853         // contain a VisiblePosition when doing selection preservation.

   854         if (m_lastCharacter != '\n') {

   855             // insert a newline with a position following this block's contents.

   856             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);

   857             // remember whether to later add a newline for the current node

   858             ASSERT(!m_needsAnotherNewline);

   859             m_needsAnotherNewline = addNewline;

   860         } else if (addNewline)

   861             // insert a newline with a position following this block's contents.

   862             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);

   863     }

   864     

   865     // If nothing was emitted, see if we need to emit a space.

   866     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))

   867         emitCharacter(' ', baseNode->parentNode(), baseNode, 1, 1);

   868 }

   869 

   870 void TextIterator::emitCharacter(UChar c, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset)

   871 {

   872     m_hasEmitted = true;

   873     

   874     // remember information with which to construct the TextIterator::range()

   875     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode

   876     m_positionNode = textNode;

   877     m_positionOffsetBaseNode = offsetBaseNode;

   878     m_positionStartOffset = textStartOffset;

   879     m_positionEndOffset = textEndOffset;

   880  

   881     // remember information with which to construct the TextIterator::characters() and length()

   882     m_singleCharacterBuffer = c;

   883     m_textCharacters = &m_singleCharacterBuffer;

   884     m_textLength = 1;

   885 

   886     // remember some iteration state

   887     m_lastTextNodeEndedWithCollapsedSpace = false;

   888     m_lastCharacter = c;

   889 }

   890 

   891 void TextIterator::emitText(Node* textNode, int textStartOffset, int textEndOffset)

   892 {

   893     RenderText* renderer = toRenderText(m_node->renderer());

   894     m_text = m_emitsTextWithoutTranscoding ? renderer->textWithoutTranscoding() : renderer->text();

   895     ASSERT(m_text.characters());

   896 

   897     m_positionNode = textNode;

   898     m_positionOffsetBaseNode = 0;

   899     m_positionStartOffset = textStartOffset;

   900     m_positionEndOffset = textEndOffset;

   901     m_textCharacters = m_text.characters() + textStartOffset;

   902     m_textLength = textEndOffset - textStartOffset;

   903     m_lastCharacter = m_text[textEndOffset - 1];

   904 

   905     m_lastTextNodeEndedWithCollapsedSpace = false;

   906     m_hasEmitted = true;

   907 }

   908 

   909 PassRefPtr<Range> TextIterator::range() const

   910 {

   911     // use the current run information, if we have it

   912     if (m_positionNode) {

   913         if (m_positionOffsetBaseNode) {

   914             int index = m_positionOffsetBaseNode->nodeIndex();

   915             m_positionStartOffset += index;

   916             m_positionEndOffset += index;

   917             m_positionOffsetBaseNode = 0;

   918         }

   919         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);

   920     }

   921 

   922     // otherwise, return the end of the overall range we were given

   923     if (m_endContainer)

   924         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);

   925         

   926     return 0;

   927 }

   928     

   929 Node* TextIterator::node() const

   930 {

   931     RefPtr<Range> textRange = range();

   932     if (!textRange)

   933         return 0;

   934 

   935     Node* node = textRange->startContainer();

   936     if (!node)

   937         return 0;

   938     if (node->offsetInCharacters())

   939         return node;

   940     

   941     return node->childNode(textRange->startOffset());

   942 }

   943 

   944 // --------

   945 

   946 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator()

   947     : m_positionNode(0)

   948 {

   949 }

   950 

   951 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range* r)

   952     : m_positionNode(0)

   953 {

   954     if (!r)

   955         return;

   956 

   957     Node* startNode = r->startContainer();

   958     if (!startNode)

   959         return;

   960     Node* endNode = r->endContainer();

   961     int startOffset = r->startOffset();

   962     int endOffset = r->endOffset();

   963 

   964     if (!startNode->offsetInCharacters()) {

   965         if (startOffset >= 0 && startOffset < static_cast<int>(startNode->childNodeCount())) {

   966             startNode = startNode->childNode(startOffset);

   967             startOffset = 0;

   968         }

   969     }

   970     if (!endNode->offsetInCharacters()) {

   971         if (endOffset > 0 && endOffset <= static_cast<int>(endNode->childNodeCount())) {

   972             endNode = endNode->childNode(endOffset - 1);

   973             endOffset = lastOffsetInNode(endNode);

   974         }

   975     }

   976 

   977     m_node = endNode;

   978     setUpFullyClippedStack(m_fullyClippedStack, m_node);    

   979     m_offset = endOffset;

   980     m_handledNode = false;

   981     m_handledChildren = endOffset == 0;

   982 

   983     m_startNode = startNode;

   984     m_startOffset = startOffset;

   985     m_endNode = endNode;

   986     m_endOffset = endOffset;

   987     

   988 #ifndef NDEBUG

   989     // Need this just because of the assert.

   990     m_positionNode = endNode;

   991 #endif

   992 

   993     m_lastTextNode = 0;

   994     m_lastCharacter = '\n';

   995 

   996     m_pastStartNode = previousInPostOrderCrossingShadowBoundaries(startNode, startOffset);

   997 

   998     advance();

   999 }

  1000 

  1001 void SimplifiedBackwardsTextIterator::advance()

  1002 {

  1003     ASSERT(m_positionNode);

  1004 

  1005     m_positionNode = 0;

  1006     m_textLength = 0;

  1007 

  1008     while (m_node && m_node != m_pastStartNode) {

  1009         // Don't handle node if we start iterating at [node, 0].

  1010         if (!m_handledNode && !(m_node == m_endNode && m_endOffset == 0)) {

  1011             RenderObject* renderer = m_node->renderer();

  1012             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {

  1013                 // FIXME: What about CDATA_SECTION_NODE?

  1014                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)

  1015                     m_handledNode = handleTextNode();

  1016             } else if (renderer && (renderer->isImage() || renderer->isWidget())) {

  1017                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)

  1018                     m_handledNode = handleReplacedElement();

  1019             } else

  1020                 m_handledNode = handleNonTextNode();

  1021             if (m_positionNode)

  1022                 return;

  1023         }

  1024 

  1025         Node* next = m_handledChildren ? 0 : m_node->lastChild();

  1026         if (!next) {

  1027             // Exit empty containers as we pass over them or containers

  1028             // where [container, 0] is where we started iterating.

  1029             if (!m_handledNode &&

  1030                 canHaveChildrenForEditing(m_node) && 

  1031                 m_node->parentNode() && 

  1032                 (!m_node->lastChild() || (m_node == m_endNode && m_endOffset == 0))) {

  1033                 exitNode();

  1034                 if (m_positionNode) {

  1035                     m_handledNode = true;

  1036                     m_handledChildren = true;

  1037                     return;

  1038                 }            

  1039             }

  1040             // Exit all other containers.

  1041             next = m_node->previousSibling();

  1042             while (!next) {

  1043                 Node* parentNode = parentCrossingShadowBoundaries(m_node);

  1044                 if (!parentNode)

  1045                     break;

  1046                 m_node = parentNode;

  1047                 m_fullyClippedStack.pop();

  1048                 exitNode();

  1049                 if (m_positionNode) {

  1050                     m_handledNode = true;

  1051                     m_handledChildren = true;

  1052                     return;

  1053                 }

  1054                 next = m_node->previousSibling();

  1055             }

  1056             m_fullyClippedStack.pop();

  1057         }

  1058         

  1059         m_node = next;

  1060         if (m_node)

  1061             pushFullyClippedState(m_fullyClippedStack, m_node);

  1062         // For the purpose of word boundary detection,

  1063         // we should iterate all visible text and trailing (collapsed) whitespaces. 

  1064         m_offset = m_node ? maxOffsetIncludingCollapsedSpaces(m_node) : 0;

  1065         m_handledNode = false;

  1066         m_handledChildren = false;

  1067         

  1068         if (m_positionNode)

  1069             return;

  1070     }

  1071 }

  1072 

  1073 bool SimplifiedBackwardsTextIterator::handleTextNode()

  1074 {

  1075     m_lastTextNode = m_node;

  1076 

  1077     RenderText* renderer = toRenderText(m_node->renderer());

  1078     String str = renderer->text();

  1079 

  1080     if (!renderer->firstTextBox() && str.length() > 0)

  1081         return true;

  1082 

  1083     m_positionEndOffset = m_offset;

  1084 

  1085     m_offset = (m_node == m_startNode) ? m_startOffset : 0;

  1086     m_positionNode = m_node;

  1087     m_positionStartOffset = m_offset;

  1088     m_textLength = m_positionEndOffset - m_positionStartOffset;

  1089     m_textCharacters = str.characters() + m_positionStartOffset;

  1090 

  1091     m_lastCharacter = str[m_positionEndOffset - 1];

  1092 

  1093     return true;

  1094 }

  1095 

  1096 bool SimplifiedBackwardsTextIterator::handleReplacedElement()

  1097 {

  1098     unsigned index = m_node->nodeIndex();

  1099     // We want replaced elements to behave like punctuation for boundary 

  1100     // finding, and to simply take up space for the selection preservation 

  1101     // code in moveParagraphs, so we use a comma.  Unconditionally emit

  1102     // here because this iterator is only used for boundary finding.

  1103     emitCharacter(',', m_node->parentNode(), index, index + 1);

  1104     return true;

  1105 }

  1106 

  1107 bool SimplifiedBackwardsTextIterator::handleNonTextNode()

  1108 {    

  1109     // We can use a linefeed in place of a tab because this simple iterator is only used to

  1110     // find boundaries, not actual content.  A linefeed breaks words, sentences, and paragraphs.

  1111     if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineAfterNode(m_node) || shouldEmitTabBeforeNode(m_node)) {

  1112         unsigned index = m_node->nodeIndex();

  1113         // The start of this emitted range is wrong. Ensuring correctness would require

  1114         // VisiblePositions and so would be slow. previousBoundary expects this.

  1115         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);

  1116     }

  1117     return true;

  1118 }

  1119 

  1120 void SimplifiedBackwardsTextIterator::exitNode()

  1121 {

  1122     if (shouldEmitNewlineForNode(m_node) || shouldEmitNewlineBeforeNode(m_node) || shouldEmitTabBeforeNode(m_node)) {

  1123         // The start of this emitted range is wrong. Ensuring correctness would require

  1124         // VisiblePositions and so would be slow. previousBoundary expects this.

  1125         emitCharacter('\n', m_node, 0, 0);

  1126     }

  1127 }

  1128 

  1129 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node* node, int startOffset, int endOffset)

  1130 {

  1131     m_singleCharacterBuffer = c;

  1132     m_positionNode = node;

  1133     m_positionStartOffset = startOffset;

  1134     m_positionEndOffset = endOffset;

  1135     m_textCharacters = &m_singleCharacterBuffer;