src/third_party/WebKit/Source/core/editing/TextIterator.cpp

   1 /*
   2  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012 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 "core/editing/TextIterator.h"
  29
  30 #include "bindings/core/v8/ExceptionStatePlaceholder.h"
  31 #include "core/HTMLNames.h"
  32 #include "core/dom/Document.h"
  33 #include "core/dom/NodeTraversal.h"
  34 #include "core/dom/shadow/ShadowRoot.h"
  35 #include "core/editing/VisiblePosition.h"
  36 #include "core/editing/VisibleUnits.h"
  37 #include "core/editing/htmlediting.h"
  38 #include "core/frame/FrameView.h"
  39 #include "core/html/HTMLElement.h"
  40 #include "core/html/HTMLTextFormControlElement.h"
  41 #include "core/rendering/InlineTextBox.h"
  42 #include "core/rendering/RenderImage.h"
  43 #include "core/rendering/RenderTableCell.h"
  44 #include "core/rendering/RenderTableRow.h"
  45 #include "core/rendering/RenderTextControl.h"
  46 #include "core/rendering/RenderTextFragment.h"
  47 #include "platform/fonts/Character.h"
  48 #include "platform/fonts/Font.h"
  49 #include "platform/text/TextBoundaries.h"
  50 #include "platform/text/TextBreakIteratorInternalICU.h"
  51 #include "platform/text/UnicodeUtilities.h"
  52 #include "wtf/text/CString.h"
  53 #include "wtf/text/StringBuilder.h"
  54 #include "wtf/unicode/CharacterNames.h"
  55 #include <unicode/usearch.h>
  56 #include <unicode/utf16.h>
  57
  58 using namespace WTF::Unicode;
  59
  60 namespace blink {
  61
  62 using namespace HTMLNames;
  63
  64 // Buffer that knows how to compare with a search target.
  65 // Keeps enough of the previous text to be able to search in the future, but no more.
  66 // Non-breaking spaces are always equal to normal spaces.
  67 // Case folding is also done if the CaseInsensitive option is specified.
  68 // Matches are further filtered if the AtWordStarts option is specified, although some
  69 // matches inside a word are permitted if TreatMedialCapitalAsWordStart is specified as well.
  70 class SearchBuffer {
  71     WTF_MAKE_NONCOPYABLE(SearchBuffer);
  72 public:
  73     SearchBuffer(const String& target, FindOptions);
  74     ~SearchBuffer();
  75
  76     // Returns number of characters appended; guaranteed to be in the range [1, length].
  77     template<typename CharType>
  78     void append(const CharType*, size_t length);
  79     size_t numberOfCharactersJustAppended() const { return m_numberOfCharactersJustAppended; }
  80
  81     bool needsMoreContext() const;
  82     void prependContext(const UChar*, size_t length);
  83     void reachedBreak();
  84
  85     // Result is the size in characters of what was found.
  86     // And <startOffset> is the number of characters back to the start of what was found.
  87     size_t search(size_t& startOffset);
  88     bool atBreak() const;
  89
  90 private:
  91     bool isBadMatch(const UChar*, size_t length) const;
  92     bool isWordStartMatch(size_t start, size_t length) const;
  93
  94     Vector<UChar> m_target;
  95     FindOptions m_options;
  96
  97     Vector<UChar> m_buffer;
  98     size_t m_overlap;
  99     size_t m_prefixLength;
 100     size_t m_numberOfCharactersJustAppended;
 101     bool m_atBreak;
 102     bool m_needsMoreContext;
 103
 104     bool m_targetRequiresKanaWorkaround;
 105     Vector<UChar> m_normalizedTarget;
 106     mutable Vector<UChar> m_normalizedMatch;
 107 };
 108
 109 // --------
 110
 111 static const unsigned bitsInWord = sizeof(unsigned) * 8;
 112 static const unsigned bitInWordMask = bitsInWord - 1;
 113
 114 BitStack::BitStack()
 115     : m_size(0)
 116 {
 117 }
 118
 119 BitStack::~BitStack()
 120 {
 121 }
 122
 123 void BitStack::push(bool bit)
 124 {
 125     unsigned index = m_size / bitsInWord;
 126     unsigned shift = m_size & bitInWordMask;
 127     if (!shift && index == m_words.size()) {
 128         m_words.grow(index + 1);
 129         m_words[index] = 0;
 130     }
 131     unsigned& word = m_words[index];
 132     unsigned mask = 1U << shift;
 133     if (bit)
 134         word |= mask;
 135     else
 136         word &= ~mask;
 137     ++m_size;
 138 }
 139
 140 void BitStack::pop()
 141 {
 142     if (m_size)
 143         --m_size;
 144 }
 145
 146 bool BitStack::top() const
 147 {
 148     if (!m_size)
 149         return false;
 150     unsigned shift = (m_size - 1) & bitInWordMask;
 151     return m_words.last() & (1U << shift);
 152 }
 153
 154 unsigned BitStack::size() const
 155 {
 156     return m_size;
 157 }
 158
 159 // --------
 160
 161 #if ENABLE(ASSERT)
 162
 163 static unsigned depthCrossingShadowBoundaries(Node* node)
 164 {
 165     unsigned depth = 0;
 166     for (ContainerNode* parent = node->parentOrShadowHostNode(); parent; parent = parent->parentOrShadowHostNode())
 167         ++depth;
 168     return depth;
 169 }
 170
 171 #endif
 172
 173 // This function is like Range::pastLastNode, except for the fact that it can climb up out of shadow trees.
 174 static Node* nextInPreOrderCrossingShadowBoundaries(Node* rangeEndContainer, int rangeEndOffset)
 175 {
 176     if (!rangeEndContainer)
 177         return 0;
 178     if (rangeEndOffset >= 0 && !rangeEndContainer->offsetInCharacters()) {
 179         if (Node* next = NodeTraversal::childAt(*rangeEndContainer, rangeEndOffset))
 180             return next;
 181     }
 182     for (Node* node = rangeEndContainer; node; node = node->parentOrShadowHostNode()) {
 183         if (Node* next = node->nextSibling())
 184             return next;
 185     }
 186     return 0;
 187 }
 188
 189 // --------
 190
 191 static inline bool fullyClipsContents(Node* node)
 192 {
 193     RenderObject* renderer = node->renderer();
 194     if (!renderer || !renderer->isBox() || !renderer->hasOverflowClip())
 195         return false;
 196     return toRenderBox(renderer)->size().isEmpty();
 197 }
 198
 199 static inline bool ignoresContainerClip(Node* node)
 200 {
 201     RenderObject* renderer = node->renderer();
 202     if (!renderer || renderer->isText())
 203         return false;
 204     return renderer->style()->hasOutOfFlowPosition();
 205 }
 206
 207 static void pushFullyClippedState(BitStack& stack, Node* node)
 208 {
 209     ASSERT(stack.size() == depthCrossingShadowBoundaries(node));
 210
 211     // FIXME: m_fullyClippedStack was added in response to <https://bugs.webkit.org/show_bug.cgi?id=26364>
 212     // ("Search can find text that's hidden by overflow:hidden"), but the logic here will not work correctly if
 213     // a shadow tree redistributes nodes. m_fullyClippedStack relies on the assumption that DOM node hierarchy matches
 214     // the render tree, which is not necessarily true if there happens to be shadow DOM distribution or other mechanics
 215     // that shuffle around the render objects regardless of node tree hierarchy (like CSS flexbox).
 216     //
 217     // A more appropriate way to handle this situation is to detect overflow:hidden blocks by using only rendering
 218     // primitives, not with DOM primitives.
 219
 220     // Push true if this node full clips its contents, or if a parent already has fully
 221     // clipped and this is not a node that ignores its container's clip.
 222     stack.push(fullyClipsContents(node) || (stack.top() && !ignoresContainerClip(node)));
 223 }
 224
 225 static void setUpFullyClippedStack(BitStack& stack, Node* node)
 226 {
 227     // Put the nodes in a vector so we can iterate in reverse order.
 228     WillBeHeapVector<RawPtrWillBeMember<ContainerNode>, 100> ancestry;
 229     for (ContainerNode* parent = node->parentOrShadowHostNode(); parent; parent = parent->parentOrShadowHostNode())
 230         ancestry.append(parent);
 231
 232     // Call pushFullyClippedState on each node starting with the earliest ancestor.
 233     size_t size = ancestry.size();
 234     for (size_t i = 0; i < size; ++i)
 235         pushFullyClippedState(stack, ancestry[size - i - 1]);
 236     pushFullyClippedState(stack, node);
 237
 238     ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));
 239 }
 240
 241 // --------
 242
 243 TextIterator::TextIterator(const Range* range, TextIteratorBehaviorFlags behavior)
 244     : m_startContainer(nullptr)
 245     , m_startOffset(0)
 246     , m_endContainer(nullptr)
 247     , m_endOffset(0)
 248     , m_positionNode(nullptr)
 249     , m_textLength(0)
 250     , m_needsAnotherNewline(false)
 251     , m_textBox(0)
 252     , m_remainingTextBox(0)
 253     , m_firstLetterText(nullptr)
 254     , m_lastTextNode(nullptr)
 255     , m_lastTextNodeEndedWithCollapsedSpace(false)
 256     , m_lastCharacter(0)
 257     , m_sortedTextBoxesPosition(0)
 258     , m_hasEmitted(false)
 259     , m_emitsCharactersBetweenAllVisiblePositions(behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions)
 260     , m_entersTextControls(behavior & TextIteratorEntersTextControls)
 261     , m_emitsOriginalText(behavior & TextIteratorEmitsOriginalText)
 262     , m_handledFirstLetter(false)
 263     , m_ignoresStyleVisibility(behavior & TextIteratorIgnoresStyleVisibility)
 264     , m_stopsOnFormControls(behavior & TextIteratorStopsOnFormControls)
 265     , m_shouldStop(false)
 266     , m_emitsImageAltText(behavior & TextIteratorEmitsImageAltText)
 267     , m_entersAuthorShadowRoots(behavior & TextIteratorEntersAuthorShadowRoots)
 268     , m_emitsObjectReplacementCharacter(behavior & TextIteratorEmitsObjectReplacementCharacter)
 269     , m_breaksAtReplacedElement(!(behavior & TextIteratorDoesNotBreakAtReplacedElement))
 270 {
 271     if (range)
 272         initialize(range->startPosition(), range->endPosition());
 273 }
 274
 275 TextIterator::TextIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags behavior)
 276     : m_startContainer(nullptr)
 277     , m_startOffset(0)
 278     , m_endContainer(nullptr)
 279     , m_endOffset(0)
 280     , m_positionNode(nullptr)
 281     , m_textLength(0)
 282     , m_needsAnotherNewline(false)
 283     , m_textBox(0)
 284     , m_remainingTextBox(0)
 285     , m_firstLetterText(nullptr)
 286     , m_lastTextNode(nullptr)
 287     , m_lastTextNodeEndedWithCollapsedSpace(false)
 288     , m_lastCharacter(0)
 289     , m_sortedTextBoxesPosition(0)
 290     , m_hasEmitted(false)
 291     , m_emitsCharactersBetweenAllVisiblePositions(behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions)
 292     , m_entersTextControls(behavior & TextIteratorEntersTextControls)
 293     , m_emitsOriginalText(behavior & TextIteratorEmitsOriginalText)
 294     , m_handledFirstLetter(false)
 295     , m_ignoresStyleVisibility(behavior & TextIteratorIgnoresStyleVisibility)
 296     , m_stopsOnFormControls(behavior & TextIteratorStopsOnFormControls)
 297     , m_shouldStop(false)
 298     , m_emitsImageAltText(behavior & TextIteratorEmitsImageAltText)
 299     , m_entersAuthorShadowRoots(behavior & TextIteratorEntersAuthorShadowRoots)
 300     , m_emitsObjectReplacementCharacter(behavior & TextIteratorEmitsObjectReplacementCharacter)
 301     , m_breaksAtReplacedElement(!(behavior & TextIteratorDoesNotBreakAtReplacedElement))
 302 {
 303     initialize(start, end);
 304 }
 305
 306 void TextIterator::initialize(const Position& start, const Position& end)
 307 {
 308     ASSERT(comparePositions(start, end) <= 0);
 309
 310     // Get and validate |start| and |end|.
 311     Node* startContainer = start.containerNode();
 312     if (!startContainer)
 313         return;
 314     int startOffset = start.computeOffsetInContainerNode();
 315     Node* endContainer = end.containerNode();
 316     if (!endContainer)
 317         return;
 318     int endOffset = end.computeOffsetInContainerNode();
 319
 320     // Remember the range - this does not change.
 321     m_startContainer = startContainer;
 322     m_startOffset = startOffset;
 323     m_endContainer = endContainer;
 324     m_endOffset = endOffset;
 325
 326     // Figure out the initial value of m_shadowDepth: the depth of startContainer's tree scope from
 327     // the common ancestor tree scope.
 328     const TreeScope* commonAncestorTreeScope = startContainer->treeScope().commonAncestorTreeScope(endContainer->treeScope());
 329     ASSERT(commonAncestorTreeScope);
 330     m_shadowDepth = 0;
 331     for (const TreeScope* treeScope = &startContainer->treeScope(); treeScope != commonAncestorTreeScope; treeScope = treeScope->parentTreeScope())
 332         ++m_shadowDepth;
 333
 334     // Set up the current node for processing.
 335     if (startContainer->offsetInCharacters())
 336         m_node = startContainer;
 337     else if (Node* child = NodeTraversal::childAt(*startContainer, startOffset))
 338         m_node = child;
 339     else if (!startOffset)
 340         m_node = startContainer;
 341     else
 342         m_node = NodeTraversal::nextSkippingChildren(*startContainer);
 343
 344     if (!m_node)
 345         return;
 346
 347     m_node->document().updateLayoutIgnorePendingStylesheets();
 348
 349     setUpFullyClippedStack(m_fullyClippedStack, m_node);
 350     m_offset = m_node == m_startContainer ? m_startOffset : 0;
 351     m_iterationProgress = HandledNone;
 352
 353     // Calculate first out of bounds node.
 354     m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(endContainer, endOffset);
 355
 356     // Identify the first run.
 357     advance();
 358 }
 359
 360 TextIterator::~TextIterator()
 361 {
 362 }
 363
 364 bool TextIterator::isInsideReplacedElement() const
 365 {
 366     if (atEnd() || length() != 1 || !m_node)
 367         return false;
 368
 369     RenderObject* renderer = m_node->renderer();
 370     return renderer && renderer->isReplaced();
 371 }
 372
 373 void TextIterator::advance()
 374 {
 375     if (m_shouldStop)
 376         return;
 377
 378     ASSERT(!m_node || !m_node->document().needsRenderTreeUpdate());
 379
 380     // reset the run information
 381     m_positionNode = nullptr;
 382     m_textLength = 0;
 383
 384     // handle remembered node that needed a newline after the text node's newline
 385     if (m_needsAnotherNewline) {
 386         // Emit the extra newline, and position it *inside* m_node, after m_node's
 387         // contents, in case it's a block, in the same way that we position the first
 388         // newline. The range for the emitted newline should start where the line
 389         // break begins.
 390         // FIXME: It would be cleaner if we emitted two newlines during the last
 391         // iteration, instead of using m_needsAnotherNewline.
 392         Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node.get();
 393         emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
 394         m_needsAnotherNewline = false;
 395         return;
 396     }
 397
 398     if (!m_textBox && m_remainingTextBox) {
 399         m_textBox = m_remainingTextBox;
 400         m_remainingTextBox = 0;
 401         m_firstLetterText = nullptr;
 402         m_offset = 0;
 403     }
 404     // handle remembered text box
 405     if (m_textBox) {
 406         handleTextBox();
 407         if (m_positionNode)
 408             return;
 409     }
 410
 411     while (m_node && (m_node != m_pastEndNode || m_shadowDepth > 0)) {
 412         if (!m_shouldStop && m_stopsOnFormControls && HTMLFormControlElement::enclosingFormControlElement(m_node))
 413             m_shouldStop = true;
 414
 415         // if the range ends at offset 0 of an element, represent the
 416         // position, but not the content, of that element e.g. if the
 417         // node is a blockflow element, emit a newline that
 418         // precedes the element
 419         if (m_node == m_endContainer && !m_endOffset) {
 420             representNodeOffsetZero();
 421             m_node = nullptr;
 422             return;
 423         }
 424
 425         RenderObject* renderer = m_node->renderer();
 426         if (!renderer) {
 427             if (m_node->isShadowRoot()) {
 428                 // A shadow root doesn't have a renderer, but we want to visit children anyway.
 429                 m_iterationProgress = m_iterationProgress < HandledNode ? HandledNode : m_iterationProgress;
 430             } else {
 431                 m_iterationProgress = HandledChildren;
 432             }
 433         } else {
 434             // Enter author shadow roots, from youngest, if any and if necessary.
 435             if (m_iterationProgress < HandledAuthorShadowRoots) {
 436                 if (m_entersAuthorShadowRoots && m_node->isElementNode() && toElement(m_node)->hasAuthorShadowRoot()) {
 437                     ShadowRoot* youngestShadowRoot = toElement(m_node)->shadowRoot();
 438                     ASSERT(youngestShadowRoot->type() == ShadowRoot::AuthorShadowRoot);
 439                     m_node = youngestShadowRoot;
 440                     m_iterationProgress = HandledNone;
 441                     ++m_shadowDepth;
 442                     pushFullyClippedState(m_fullyClippedStack, m_node);
 443                     continue;
 444                 }
 445
 446                 m_iterationProgress = HandledAuthorShadowRoots;
 447             }
 448
 449             // Enter user-agent shadow root, if necessary.
 450             if (m_iterationProgress < HandledUserAgentShadowRoot) {
 451                 if (m_entersTextControls && renderer->isTextControl()) {
 452                     ShadowRoot* userAgentShadowRoot = toElement(m_node)->userAgentShadowRoot();
 453                     ASSERT(userAgentShadowRoot->type() == ShadowRoot::UserAgentShadowRoot);
 454                     m_node = userAgentShadowRoot;
 455                     m_iterationProgress = HandledNone;
 456                     ++m_shadowDepth;
 457                     pushFullyClippedState(m_fullyClippedStack, m_node);
 458                     continue;
 459                 }
 460                 m_iterationProgress = HandledUserAgentShadowRoot;
 461             }
 462
 463             // Handle the current node according to its type.
 464             if (m_iterationProgress < HandledNode) {
 465                 bool handledNode = false;
 466                 if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) { // FIXME: What about CDATA_SECTION_NODE?
 467                     handledNode = handleTextNode();
 468                 } else if (renderer && (renderer->isImage() || renderer->isRenderPart()
 469                     || (m_node && m_node->isHTMLElement()
 470                     && (isHTMLFormControlElement(toHTMLElement(*m_node))
 471                     || isHTMLLegendElement(toHTMLElement(*m_node))
 472                     || isHTMLMeterElement(toHTMLElement(*m_node))
 473                     || isHTMLProgressElement(toHTMLElement(*m_node)))))) {
 474                     handledNode = handleReplacedElement();
 475                 } else {
 476                     handledNode = handleNonTextNode();
 477                 }
 478                 if (handledNode)
 479                     m_iterationProgress = HandledNode;
 480                 if (m_positionNode)
 481                     return;
 482             }
 483         }
 484
 485         // Find a new current node to handle in depth-first manner,
 486         // calling exitNode() as we come back thru a parent node.
 487         //
 488         // 1. Iterate over child nodes, if we haven't done yet.
 489         Node* next = m_iterationProgress < HandledChildren ? m_node->firstChild() : 0;
 490         m_offset = 0;
 491         if (!next) {
 492             // 2. If we've already iterated children or they are not available, go to the next sibling node.
 493             next = m_node->nextSibling();
 494             if (!next) {
 495                 // 3. If we are at the last child, go up the node tree until we find a next sibling.
 496                 bool pastEnd = NodeTraversal::next(*m_node) == m_pastEndNode;
 497                 ContainerNode* parentNode = m_node->parentNode();
 498                 while (!next && parentNode) {
 499                     if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))
 500                         return;
 501                     bool haveRenderer = m_node->renderer();
 502                     m_node = parentNode;
 503                     m_fullyClippedStack.pop();
 504                     parentNode = m_node->parentNode();
 505                     if (haveRenderer)
 506                         exitNode();
 507                     if (m_positionNode) {
 508                         m_iterationProgress = HandledChildren;
 509                         return;
 510                     }
 511                     next = m_node->nextSibling();
 512                 }
 513
 514                 if (!next && !parentNode && m_shadowDepth > 0) {
 515                     // 4. Reached the top of a shadow root. If it's created by author, then try to visit the next
 516                     // sibling shadow root, if any.
 517                     ShadowRoot* shadowRoot = toShadowRoot(m_node);
 518                     if (shadowRoot->type() == ShadowRoot::AuthorShadowRoot) {
 519                         ShadowRoot* nextShadowRoot = shadowRoot->olderShadowRoot();
 520                         if (nextShadowRoot && nextShadowRoot->type() == ShadowRoot::AuthorShadowRoot) {
 521                             m_fullyClippedStack.pop();
 522                             m_node = nextShadowRoot;
 523                             m_iterationProgress = HandledNone;
 524                             // m_shadowDepth is unchanged since we exit from a shadow root and enter another.
 525                             pushFullyClippedState(m_fullyClippedStack, m_node);
 526                         } else {
 527                             // We are the last shadow root; exit from here and go back to where we were.
 528                             m_node = shadowRoot->host();
 529                             m_iterationProgress = HandledAuthorShadowRoots;
 530                             --m_shadowDepth;
 531                             m_fullyClippedStack.pop();
 532                         }
 533                     } else {
 534                         // If we are in a user-agent shadow root, then go back to the host.
 535                         ASSERT(shadowRoot->type() == ShadowRoot::UserAgentShadowRoot);
 536                         m_node = shadowRoot->host();
 537                         m_iterationProgress = HandledUserAgentShadowRoot;
 538                         --m_shadowDepth;
 539                         m_fullyClippedStack.pop();
 540                     }
 541                     m_handledFirstLetter = false;
 542                     m_firstLetterText = nullptr;
 543                     continue;
 544                 }
 545             }
 546             m_fullyClippedStack.pop();
 547         }
 548
 549         // set the new current node
 550         m_node = next;
 551         if (m_node)
 552             pushFullyClippedState(m_fullyClippedStack, m_node);
 553         m_iterationProgress = HandledNone;
 554         m_handledFirstLetter = false;
 555         m_firstLetterText = nullptr;
 556
 557         // how would this ever be?
 558         if (m_positionNode)
 559             return;
 560     }
 561 }
 562
 563 UChar TextIterator::characterAt(unsigned index) const
 564 {
 565     ASSERT_WITH_SECURITY_IMPLICATION(index < static_cast<unsigned>(length()));
 566     if (!(index < static_cast<unsigned>(length())))
 567         return 0;
 568
 569     if (m_singleCharacterBuffer) {
 570         ASSERT(!index);
 571         ASSERT(length() == 1);
 572         return m_singleCharacterBuffer;
 573     }
 574
 575     return string()[positionStartOffset() + index];
 576 }
 577
 578 String TextIterator::substring(unsigned position, unsigned length) const
 579 {
 580     ASSERT_WITH_SECURITY_IMPLICATION(position <= static_cast<unsigned>(this->length()));
 581     ASSERT_WITH_SECURITY_IMPLICATION(position + length <= static_cast<unsigned>(this->length()));
 582     if (!length)
 583         return emptyString();
 584     if (m_singleCharacterBuffer) {
 585         ASSERT(!position);
 586         ASSERT(length == 1);
 587         return String(&m_singleCharacterBuffer, 1);
 588     }
 589     return string().substring(positionStartOffset() + position, length);
 590 }
 591
 592 void TextIterator::appendTextToStringBuilder(StringBuilder& builder, unsigned position, unsigned maxLength) const
 593 {
 594     unsigned lengthToAppend = std::min(static_cast<unsigned>(length()) - position, maxLength);
 595     if (!lengthToAppend)
 596         return;
 597     if (m_singleCharacterBuffer) {
 598         ASSERT(!position);
 599         builder.append(m_singleCharacterBuffer);
 600     } else {
 601         builder.append(string(), positionStartOffset() + position, lengthToAppend);
 602     }
 603 }
 604
 605 bool TextIterator::handleTextNode()
 606 {
 607     if (m_fullyClippedStack.top() && !m_ignoresStyleVisibility)
 608         return false;
 609
 610     Text* textNode = toText(m_node);
 611     RenderText* renderer = textNode->renderer();
 612
 613     m_lastTextNode = textNode;
 614     String str = renderer->text();
 615
 616     // handle pre-formatted text
 617     if (!renderer->style()->collapseWhiteSpace()) {
 618         int runStart = m_offset;
 619         if (m_lastTextNodeEndedWithCollapsedSpace && hasVisibleTextNode(renderer)) {
 620             emitCharacter(space, textNode, 0, runStart, runStart);
 621             return false;
 622         }
 623         if (!m_handledFirstLetter && renderer->isTextFragment() && !m_offset) {
 624             handleTextNodeFirstLetter(toRenderTextFragment(renderer));
 625             if (m_firstLetterText) {
 626                 String firstLetter = m_firstLetterText->text();
 627                 emitText(textNode, m_firstLetterText, m_offset, m_offset + firstLetter.length());
 628                 m_firstLetterText = nullptr;
 629                 m_textBox = 0;
 630                 return false;
 631             }
 632         }
 633         if (renderer->style()->visibility() != VISIBLE && !m_ignoresStyleVisibility)
 634             return false;
 635         int strLength = str.length();
 636         int end = (textNode == m_endContainer) ? m_endOffset : INT_MAX;
 637         int runEnd = std::min(strLength, end);
 638
 639         if (runStart >= runEnd)
 640             return true;
 641
 642         emitText(textNode, textNode->renderer(), runStart, runEnd);
 643         return true;
 644     }
 645
 646     if (renderer->firstTextBox())
 647         m_textBox = renderer->firstTextBox();
 648
 649     bool shouldHandleFirstLetter = !m_handledFirstLetter && renderer->isTextFragment() && !m_offset;
 650     if (shouldHandleFirstLetter)
 651         handleTextNodeFirstLetter(toRenderTextFragment(renderer));
 652
 653     if (!renderer->firstTextBox() && str.length() > 0 && !shouldHandleFirstLetter) {
 654         if (renderer->style()->visibility() != VISIBLE && !m_ignoresStyleVisibility)
 655             return false;
 656         m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space
 657         return true;
 658     }
 659
 660     if (m_firstLetterText)
 661         renderer = m_firstLetterText;
 662
 663     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
 664     if (renderer->containsReversedText()) {
 665         m_sortedTextBoxes.clear();
 666         for (InlineTextBox* textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {
 667             m_sortedTextBoxes.append(textBox);
 668         }
 669         std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), InlineTextBox::compareByStart);
 670         m_sortedTextBoxesPosition = 0;
 671         m_textBox = m_sortedTextBoxes.isEmpty() ? 0 : m_sortedTextBoxes[0];
 672     }
 673
 674     handleTextBox();
 675     return true;
 676 }
 677
 678 void TextIterator::handleTextBox()
 679 {
 680     RenderText* renderer = m_firstLetterText ? m_firstLetterText.get() : toRenderText(m_node->renderer());
 681     if (renderer->style()->visibility() != VISIBLE && !m_ignoresStyleVisibility) {
 682         m_textBox = 0;
 683         return;
 684     }
 685     String str = renderer->text();
 686     unsigned start = m_offset;
 687     unsigned end = (m_node == m_endContainer) ? static_cast<unsigned>(m_endOffset) : INT_MAX;
 688     while (m_textBox) {
 689         unsigned textBoxStart = m_textBox->start();
 690         unsigned runStart = std::max(textBoxStart, start);
 691
 692         // Check for collapsed space at the start of this run.
 693         InlineTextBox* firstTextBox = renderer->containsReversedText() ? (m_sortedTextBoxes.isEmpty() ? 0 : m_sortedTextBoxes[0]) : renderer->firstTextBox();
 694         bool needSpace = m_lastTextNodeEndedWithCollapsedSpace
 695             || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);
 696         if (needSpace && !renderer->style()->isCollapsibleWhiteSpace(m_lastCharacter) && m_lastCharacter) {
 697             if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {
 698                 unsigned spaceRunStart = runStart - 1;
 699                 while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')
 700                     --spaceRunStart;
 701                 emitText(m_node, renderer, spaceRunStart, spaceRunStart + 1);
 702             } else {
 703                 emitCharacter(space, m_node, 0, runStart, runStart);
 704             }
 705             return;
 706         }
 707         unsigned textBoxEnd = textBoxStart + m_textBox->len();
 708         unsigned runEnd = std::min(textBoxEnd, end);
 709
 710         // Determine what the next text box will be, but don't advance yet
 711         InlineTextBox* nextTextBox = nullptr;
 712         if (renderer->containsReversedText()) {
 713             if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())
 714                 nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];
 715         } else {
 716             nextTextBox = m_textBox->nextTextBox();
 717         }
 718         ASSERT(!nextTextBox || nextTextBox->renderer() == renderer);
 719
 720         if (runStart < runEnd) {
 721             // Handle either a single newline character (which becomes a space),
 722             // or a run of characters that does not include a newline.
 723             // This effectively translates newlines to spaces without copying the text.
 724             if (str[runStart] == '\n') {
 725                 emitCharacter(space, m_node, 0, runStart, runStart + 1);
 726                 m_offset = runStart + 1;
 727             } else {
 728                 size_t subrunEnd = str.find('\n', runStart);
 729                 if (subrunEnd == kNotFound || subrunEnd > runEnd)
 730                     subrunEnd = runEnd;
 731
 732                 m_offset = subrunEnd;
 733                 emitText(m_node, renderer, runStart, subrunEnd);
 734             }
 735
 736             // If we are doing a subrun that doesn't go to the end of the text box,
 737             // come back again to finish handling this text box; don't advance to the next one.
 738             if (static_cast<unsigned>(m_positionEndOffset) < textBoxEnd)
 739                 return;
 740
 741             // Advance and return
 742             unsigned nextRunStart = nextTextBox ? nextTextBox->start() : str.length();
 743             if (nextRunStart > runEnd)
 744                 m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end
 745             m_textBox = nextTextBox;
 746             if (renderer->containsReversedText())
 747                 ++m_sortedTextBoxesPosition;
 748             return;
 749         }
 750         // Advance and continue
 751         m_textBox = nextTextBox;
 752         if (renderer->containsReversedText())
 753             ++m_sortedTextBoxesPosition;
 754     }
 755     if (!m_textBox && m_remainingTextBox) {
 756         m_textBox = m_remainingTextBox;
 757         m_remainingTextBox = 0;
 758         m_firstLetterText = nullptr;
 759         m_offset = 0;
 760         handleTextBox();
 761     }
 762 }
 763
 764 static inline RenderText* firstRenderTextInFirstLetter(RenderBoxModelObject* firstLetter)
 765 {
 766     if (!firstLetter)
 767         return 0;
 768
 769     // FIXME: Should this check descendent objects?
 770     for (RenderObject* current = firstLetter->slowFirstChild(); current; current = current->nextSibling()) {
 771         if (current->isText())
 772             return toRenderText(current);
 773     }
 774     return 0;
 775 }
 776
 777 void TextIterator::handleTextNodeFirstLetter(RenderTextFragment* renderer)
 778 {
 779     if (renderer->firstLetter()) {
 780         RenderBoxModelObject* r = renderer->firstLetter();
 781         if (r->style()->visibility() != VISIBLE && !m_ignoresStyleVisibility)
 782             return;
 783         if (RenderText* firstLetter = firstRenderTextInFirstLetter(r)) {
 784             m_handledFirstLetter = true;
 785             m_remainingTextBox = m_textBox;
 786             m_textBox = firstLetter->firstTextBox();
 787             m_sortedTextBoxes.clear();
 788             m_firstLetterText = firstLetter;
 789         }
 790     }
 791     m_handledFirstLetter = true;
 792 }
 793
 794 bool TextIterator::handleReplacedElement()
 795 {
 796     if (m_fullyClippedStack.top())
 797         return false;
 798
 799     RenderObject* renderer = m_node->renderer();
 800     if (renderer->style()->visibility() != VISIBLE && !m_ignoresStyleVisibility)
 801         return false;
 802
 803     if (m_emitsObjectReplacementCharacter) {
 804         emitCharacter(objectReplacementCharacter, m_node->parentNode(), m_node, 0, 1);
 805         return true;
 806     }
 807
 808     if (m_lastTextNodeEndedWithCollapsedSpace) {
 809         emitCharacter(space, m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);
 810         return false;
 811     }
 812
 813     if (m_entersTextControls && renderer->isTextControl()) {
 814         // The shadow tree should be already visited.
 815         return true;
 816     }
 817
 818     m_hasEmitted = true;
 819
 820     if (m_emitsCharactersBetweenAllVisiblePositions) {
 821         // We want replaced elements to behave like punctuation for boundary
 822         // finding, and to simply take up space for the selection preservation
 823         // code in moveParagraphs, so we use a comma.
 824         emitCharacter(',', m_node->parentNode(), m_node, 0, 1);
 825         return true;
 826     }
 827
 828     m_positionNode = m_node->parentNode();
 829     m_positionOffsetBaseNode = m_node;
 830     m_positionStartOffset = 0;
 831     m_positionEndOffset = 1;
 832     m_singleCharacterBuffer = 0;
 833
 834     if (m_emitsImageAltText && renderer->isImage() && renderer->isRenderImage()) {
 835         m_text = toRenderImage(renderer)->altText();
 836         if (!m_text.isEmpty()) {
 837             m_textLength = m_text.length();
 838             m_lastCharacter = m_text[m_textLength - 1];
 839             return true;
 840         }
 841     }
 842
 843     m_textLength = 0;
 844     m_lastCharacter = 0;
 845
 846     return true;
 847 }
 848
 849 bool TextIterator::hasVisibleTextNode(RenderText* renderer)
 850 {
 851     if (renderer->style()->visibility() == VISIBLE)
 852         return true;
 853     if (renderer->isTextFragment()) {
 854         RenderTextFragment* fragment = toRenderTextFragment(renderer);
 855         if (fragment->firstLetter() && fragment->firstLetter()->style()->visibility() == VISIBLE)
 856             return true;
 857     }
 858     return false;
 859 }
 860
 861 static bool shouldEmitTabBeforeNode(Node* node)
 862 {
 863     RenderObject* r = node->renderer();
 864
 865     // Table cells are delimited by tabs.
 866     if (!r || !isTableCell(node))
 867         return false;
 868
 869     // Want a tab before every cell other than the first one
 870     RenderTableCell* rc = toRenderTableCell(r);
 871     RenderTable* t = rc->table();
 872     return t && (t->cellBefore(rc) || t->cellAbove(rc));
 873 }
 874
 875 static bool shouldEmitNewlineForNode(Node* node, bool emitsOriginalText)
 876 {
 877     RenderObject* renderer = node->renderer();
 878
 879     if (renderer ? !renderer->isBR() : !isHTMLBRElement(node))
 880         return false;
 881     return emitsOriginalText || !(node->isInShadowTree() && isHTMLInputElement(*node->shadowHost()));
 882 }
 883
 884 static bool shouldEmitNewlinesBeforeAndAfterNode(Node& node)
 885 {
 886     // Block flow (versus inline flow) is represented by having
 887     // a newline both before and after the element.
 888     RenderObject* r = node.renderer();
 889     if (!r) {
 890         return (node.hasTagName(blockquoteTag)
 891             || node.hasTagName(ddTag)
 892             || node.hasTagName(divTag)
 893             || node.hasTagName(dlTag)
 894             || node.hasTagName(dtTag)
 895             || node.hasTagName(h1Tag)
 896             || node.hasTagName(h2Tag)
 897             || node.hasTagName(h3Tag)
 898             || node.hasTagName(h4Tag)
 899             || node.hasTagName(h5Tag)
 900             || node.hasTagName(h6Tag)
 901             || node.hasTagName(hrTag)
 902             || node.hasTagName(liTag)
 903             || node.hasTagName(listingTag)
 904             || node.hasTagName(olTag)
 905             || node.hasTagName(pTag)
 906             || node.hasTagName(preTag)
 907             || node.hasTagName(trTag)
 908             || node.hasTagName(ulTag));
 909     }
 910
 911     // Need to make an exception for option and optgroup, because we want to
 912     // keep the legacy behavior before we added renderers to them.
 913     if (isHTMLOptionElement(node) || isHTMLOptGroupElement(node))
 914         return false;
 915
 916     // Need to make an exception for table cells, because they are blocks, but we
 917     // want them tab-delimited rather than having newlines before and after.
 918     if (isTableCell(&node))
 919         return false;
 920
 921     // Need to make an exception for table row elements, because they are neither
 922     // "inline" or "RenderBlock", but we want newlines for them.
 923     if (r->isTableRow()) {
 924         RenderTable* t = toRenderTableRow(r)->table();
 925         if (t && !t->isInline())
 926             return true;
 927     }
 928
 929     return !r->isInline() && r->isRenderBlock()
 930         && !r->isFloatingOrOutOfFlowPositioned() && !r->isBody() && !r->isRubyText();
 931 }
 932
 933 static bool shouldEmitNewlineAfterNode(Node& node)
 934 {
 935     // FIXME: It should be better but slower to create a VisiblePosition here.
 936     if (!shouldEmitNewlinesBeforeAndAfterNode(node))
 937         return false;
 938     // Check if this is the very last renderer in the document.
 939     // If so, then we should not emit a newline.
 940     Node* next = &node;
 941     do {
 942         next = NodeTraversal::nextSkippingChildren(*next);
 943         if (next && next->renderer())
 944             return true;
 945     } while (next);
 946     return false;
 947 }
 948
 949 static bool shouldEmitNewlineBeforeNode(Node& node)
 950 {
 951     return shouldEmitNewlinesBeforeAndAfterNode(node);
 952 }
 953
 954 static bool shouldEmitExtraNewlineForNode(Node* node)
 955 {
 956     // When there is a significant collapsed bottom margin, emit an extra
 957     // newline for a more realistic result. We end up getting the right
 958     // result even without margin collapsing. For example: <div><p>text</p></div>
 959     // will work right even if both the <div> and the <p> have bottom margins.
 960     RenderObject* r = node->renderer();
 961     if (!r || !r->isBox())
 962         return false;
 963
 964     // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears
 965     // not to do this at all
 966     if (node->hasTagName(h1Tag)
 967         || node->hasTagName(h2Tag)
 968         || node->hasTagName(h3Tag)
 969         || node->hasTagName(h4Tag)
 970         || node->hasTagName(h5Tag)
 971         || node->hasTagName(h6Tag)
 972         || node->hasTagName(pTag)) {
 973         RenderStyle* style = r->style();
 974         if (style) {
 975             int bottomMargin = toRenderBox(r)->collapsedMarginAfter();
 976             int fontSize = style->fontDescription().computedPixelSize();
 977             if (bottomMargin * 2 >= fontSize)
 978                 return true;
 979         }
 980     }
 981
 982     return false;
 983 }
 984
 985 static int collapsedSpaceLength(RenderText* renderer, int textEnd)
 986 {
 987     const String& text = renderer->text();
 988     int length = text.length();
 989     for (int i = textEnd; i < length; ++i) {
 990         if (!renderer->style()->isCollapsibleWhiteSpace(text[i]))
 991             return i - textEnd;
 992     }
 993
 994     return length - textEnd;
 995 }
 996
 997 static int maxOffsetIncludingCollapsedSpaces(Node* node)
 998 {
 999     int offset = caretMaxOffset(node);
1000
1001     if (node->renderer() && node->renderer()->isText())
1002         offset += collapsedSpaceLength(toRenderText(node->renderer()), offset);
1003
1004     return offset;
1005 }
1006
1007 // 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).
1008 bool TextIterator::shouldRepresentNodeOffsetZero()
1009 {
1010     if (m_emitsCharactersBetweenAllVisiblePositions && isRenderedTableElement(m_node))
1011         return true;
1012
1013     // Leave element positioned flush with start of a paragraph
1014     // (e.g. do not insert tab before a table cell at the start of a paragraph)
1015     if (m_lastCharacter == '\n')
1016         return false;
1017
1018     // Otherwise, show the position if we have emitted any characters
1019     if (m_hasEmitted)
1020         return true;
1021
1022     // We've not emitted anything yet. Generally, there is no need for any positioning then.
1023     // The only exception is when the element is visually not in the same line as
1024     // the start of the range (e.g. the range starts at the end of the previous paragraph).
1025     // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we
1026     // make quicker checks to possibly avoid that. Another check that we could make is
1027     // is whether the inline vs block flow changed since the previous visible element.
1028     // I think we're already in a special enough case that that won't be needed, tho.
1029
1030     // No character needed if this is the first node in the range.
1031     if (m_node == m_startContainer)
1032         return false;
1033
1034     // If we are outside the start container's subtree, assume we need to emit.
1035     // FIXME: m_startContainer could be an inline block
1036     if (!m_node->isDescendantOf(m_startContainer))
1037         return true;
1038
1039     // If we started as m_startContainer offset 0 and the current node is a descendant of
1040     // the start container, we already had enough context to correctly decide whether to
1041     // emit after a preceding block. We chose not to emit (m_hasEmitted is false),
1042     // so don't second guess that now.
1043     // NOTE: Is this really correct when m_node is not a leftmost descendant? Probably
1044     // immaterial since we likely would have already emitted something by now.
1045     if (!m_startOffset)
1046         return false;
1047
1048     // If this node is unrendered or invisible the VisiblePosition checks below won't have much meaning.
1049     // Additionally, if the range we are iterating over contains huge sections of unrendered content,
1050     // we would create VisiblePositions on every call to this function without this check.
1051     if (!m_node->renderer() || m_node->renderer()->style()->visibility() != VISIBLE
1052         || (m_node->renderer()->isRenderBlockFlow() && !toRenderBlock(m_node->renderer())->height() && !isHTMLBodyElement(*m_node)))
1053         return false;
1054
1055     // The startPos.isNotNull() check is needed because the start could be before the body,
1056     // and in that case we'll get null. We don't want to put in newlines at the start in that case.
1057     // The currPos.isNotNull() check is needed because positions in non-HTML content
1058     // (like SVG) do not have visible positions, and we don't want to emit for them either.
1059     VisiblePosition startPos = VisiblePosition(Position(m_startContainer, m_startOffset, Position::PositionIsOffsetInAnchor), DOWNSTREAM);
1060     VisiblePosition currPos = VisiblePosition(positionBeforeNode(m_node), DOWNSTREAM);
1061     return startPos.isNotNull() && currPos.isNotNull() && !inSameLine(startPos, currPos);
1062 }
1063
1064 bool TextIterator::shouldEmitSpaceBeforeAndAfterNode(Node* node)
1065 {
1066     return isRenderedTableElement(node) && (node->renderer()->isInline() || m_emitsCharactersBetweenAllVisiblePositions);
1067 }
1068
1069 void TextIterator::representNodeOffsetZero()
1070 {
1071     // Emit a character to show the positioning of m_node.
1072
1073     // When we haven't been emitting any characters, shouldRepresentNodeOffsetZero() can
1074     // create VisiblePositions, which is expensive. So, we perform the inexpensive checks
1075     // on m_node to see if it necessitates emitting a character first and will early return
1076     // before encountering shouldRepresentNodeOffsetZero()s worse case behavior.
1077     if (shouldEmitTabBeforeNode(m_node)) {
1078         if (shouldRepresentNodeOffsetZero())
1079             emitCharacter('\t', m_node->parentNode(), m_node, 0, 0);
1080     } else if (shouldEmitNewlineBeforeNode(*m_node)) {
1081         if (shouldRepresentNodeOffsetZero())
1082             emitCharacter('\n', m_node->parentNode(), m_node, 0, 0);
1083     } else if (shouldEmitSpaceBeforeAndAfterNode(m_node)) {
1084         if (shouldRepresentNodeOffsetZero())
1085             emitCharacter(space, m_node->parentNode(), m_node, 0, 0);
1086     }
1087 }
1088
1089 bool TextIterator::handleNonTextNode()
1090 {
1091     if (shouldEmitNewlineForNode(m_node, m_emitsOriginalText))
1092         emitCharacter('\n', m_node->parentNode(), m_node, 0, 1);
1093     else if (m_emitsCharactersBetweenAllVisiblePositions && m_node->renderer() && m_node->renderer()->isHR())
1094         emitCharacter(space, m_node->parentNode(), m_node, 0, 1);
1095     else
1096         representNodeOffsetZero();
1097
1098     return true;
1099 }
1100
1101 void TextIterator::flushPositionOffsets() const
1102 {
1103     if (!m_positionOffsetBaseNode)
1104         return;
1105     int index = m_positionOffsetBaseNode->nodeIndex();
1106     m_positionStartOffset += index;
1107     m_positionEndOffset += index;
1108     m_positionOffsetBaseNode = nullptr;
1109 }
1110
1111 void TextIterator::exitNode()
1112 {
1113     // prevent emitting a newline when exiting a collapsed block at beginning of the range
1114     // FIXME: !m_hasEmitted does not necessarily mean there was a collapsed block... it could
1115     // have been an hr (e.g.). Also, a collapsed block could have height (e.g. a table) and
1116     // therefore look like a blank line.
1117     if (!m_hasEmitted)
1118         return;
1119
1120     // Emit with a position *inside* m_node, after m_node's contents, in
1121     // case it is a block, because the run should start where the
1122     // emitted character is positioned visually.
1123     Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node.get();
1124     // FIXME: This shouldn't require the m_lastTextNode to be true, but we can't change that without making
1125     // the logic in _web_attributedStringFromRange match. We'll get that for free when we switch to use
1126     // TextIterator in _web_attributedStringFromRange.
1127     // See <rdar://problem/5428427> for an example of how this mismatch will cause problems.
1128     if (m_lastTextNode && shouldEmitNewlineAfterNode(*m_node)) {
1129         // use extra newline to represent margin bottom, as needed
1130         bool addNewline = shouldEmitExtraNewlineForNode(m_node);
1131
1132         // FIXME: We need to emit a '\n' as we leave an empty block(s) that
1133         // contain a VisiblePosition when doing selection preservation.
1134         if (m_lastCharacter != '\n') {
1135             // insert a newline with a position following this block's contents.
1136             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
1137             // remember whether to later add a newline for the current node
1138             ASSERT(!m_needsAnotherNewline);
1139             m_needsAnotherNewline = addNewline;
1140         } else if (addNewline) {
1141             // insert a newline with a position following this block's contents.
1142             emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);
1143         }
1144     }
1145
1146     // If nothing was emitted, see if we need to emit a space.
1147     if (!m_positionNode && shouldEmitSpaceBeforeAndAfterNode(m_node))
1148         emitCharacter(space, baseNode->parentNode(), baseNode, 1, 1);
1149 }
1150
1151 void TextIterator::emitCharacter(UChar c, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset)
1152 {
1153     m_hasEmitted = true;
1154
1155     // remember information with which to construct the TextIterator::range()
1156     // NOTE: textNode is often not a text node, so the range will specify child nodes of positionNode
1157     m_positionNode = textNode;
1158     m_positionOffsetBaseNode = offsetBaseNode;
1159     m_positionStartOffset = textStartOffset;
1160     m_positionEndOffset = textEndOffset;
1161
1162     // remember information with which to construct the TextIterator::characters() and length()
1163     m_singleCharacterBuffer = c;
1164     ASSERT(m_singleCharacterBuffer);
1165     m_textLength = 1;
1166
1167     // remember some iteration state
1168     m_lastTextNodeEndedWithCollapsedSpace = false;
1169     m_lastCharacter = c;
1170 }
1171
1172 void TextIterator::emitText(Node* textNode, RenderText* renderer, int textStartOffset, int textEndOffset)
1173 {
1174     m_text = m_emitsOriginalText ? renderer->originalText() : renderer->text();
1175     ASSERT(!m_text.isEmpty());
1176     ASSERT(0 <= textStartOffset && textStartOffset < static_cast<int>(m_text.length()));
1177     ASSERT(0 <= textEndOffset && textEndOffset <= static_cast<int>(m_text.length()));
1178     ASSERT(textStartOffset <= textEndOffset);
1179
1180     m_positionNode = textNode;
1181     m_positionOffsetBaseNode = nullptr;
1182     m_positionStartOffset = textStartOffset;
1183     m_positionEndOffset = textEndOffset;
1184     m_singleCharacterBuffer = 0;
1185     m_textLength = textEndOffset - textStartOffset;
1186     m_lastCharacter = m_text[textEndOffset - 1];
1187
1188     m_lastTextNodeEndedWithCollapsedSpace = false;
1189     m_hasEmitted = true;
1190 }
1191
1192 PassRefPtrWillBeRawPtr<Range> TextIterator::createRange() const
1193 {
1194     // use the current run information, if we have it
1195     if (m_positionNode) {
1196         flushPositionOffsets();
1197         return Range::create(m_positionNode->document(), m_positionNode, m_positionStartOffset, m_positionNode, m_positionEndOffset);
1198     }
1199
1200     // otherwise, return the end of the overall range we were given
1201     if (m_endContainer)
1202         return Range::create(m_endContainer->document(), m_endContainer, m_endOffset, m_endContainer, m_endOffset);
1203
1204     return nullptr;
1205 }
1206
1207 Document* TextIterator::ownerDocument() const
1208 {
1209     if (m_positionNode)
1210         return &m_positionNode->document();
1211     if (m_endContainer)
1212         return &m_endContainer->document();
1213     return 0;
1214 }
1215
1216 Node* TextIterator::node() const
1217 {
1218     if (m_positionNode || m_endContainer) {
1219         Node* node = startContainer();
1220         if (node->offsetInCharacters())
1221             return node;
1222         return NodeTraversal::childAt(*node, startOffset());
1223     }
1224     return 0;
1225 }
1226
1227 int TextIterator::startOffset() const
1228 {
1229     if (m_positionNode) {
1230         flushPositionOffsets();
1231         return m_positionStartOffset;
1232     }
1233     ASSERT(m_endContainer);
1234     return m_endOffset;
1235 }
1236
1237 int TextIterator::endOffset() const
1238 {
1239     if (m_positionNode) {
1240         flushPositionOffsets();
1241         return m_positionEndOffset;
1242     }
1243     ASSERT(m_endContainer);
1244     return m_endOffset;
1245 }
1246
1247 Node* TextIterator::startContainer() const
1248 {
1249     if (m_positionNode) {
1250         return m_positionNode;
1251     }
1252     ASSERT(m_endContainer);
1253     return m_endContainer;
1254 }
1255
1256 Node* TextIterator::endContainer() const
1257 {
1258     return startContainer();
1259 }
1260
1261 Position TextIterator::startPosition() const
1262 {
1263     return createLegacyEditingPosition(startContainer(), startOffset());
1264 }
1265
1266 Position TextIterator::endPosition() const
1267 {
1268     return createLegacyEditingPosition(endContainer(), endOffset());
1269 }
1270
1271 // --------
1272
1273 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Range* r, TextIteratorBehaviorFlags behavior)
1274     : m_node(nullptr)
1275     , m_offset(0)
1276     , m_handledNode(false)
1277     , m_handledChildren(false)
1278     , m_startNode(nullptr)
1279     , m_startOffset(0)
1280     , m_endNode(nullptr)
1281     , m_endOffset(0)
1282     , m_positionNode(nullptr)
1283     , m_positionStartOffset(0)
1284     , m_positionEndOffset(0)
1285     , m_textOffset(0)
1286     , m_textLength(0)
1287     , m_lastTextNode(nullptr)
1288     , m_lastCharacter(0)
1289     , m_singleCharacterBuffer(0)
1290     , m_havePassedStartNode(false)
1291     , m_shouldHandleFirstLetter(false)
1292     , m_stopsOnFormControls(behavior & TextIteratorStopsOnFormControls)
1293     , m_shouldStop(false)
1294     , m_emitsOriginalText(false)
1295 {
1296     ASSERT(behavior == TextIteratorDefaultBehavior || behavior == TextIteratorStopsOnFormControls);
1297
1298     if (!r)
1299         return;
1300
1301     Node* startNode = r->startContainer();
1302     if (!startNode)
1303         return;
1304     Node* endNode = r->endContainer();
1305     int startOffset = r->startOffset();
1306     int endOffset = r->endOffset();
1307
1308     init(startNode, endNode, startOffset, endOffset);
1309 }
1310
1311 SimplifiedBackwardsTextIterator::SimplifiedBackwardsTextIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags behavior)
1312     : m_node(nullptr)
1313     , m_offset(0)
1314     , m_handledNode(false)
1315     , m_handledChildren(false)
1316     , m_startNode(nullptr)
1317     , m_startOffset(0)
1318     , m_endNode(nullptr)
1319     , m_endOffset(0)
1320     , m_positionNode(nullptr)
1321     , m_positionStartOffset(0)
1322     , m_positionEndOffset(0)
1323     , m_textOffset(0)
1324     , m_textLength(0)
1325     , m_lastTextNode(nullptr)
1326     , m_lastCharacter(0)
1327     , m_singleCharacterBuffer(0)
1328     , m_havePassedStartNode(false)
1329     , m_shouldHandleFirstLetter(false)
1330     , m_stopsOnFormControls(behavior & TextIteratorStopsOnFormControls)
1331     , m_shouldStop(false)
1332     , m_emitsOriginalText(false)
1333 {
1334     ASSERT(behavior == TextIteratorDefaultBehavior || behavior == TextIteratorStopsOnFormControls);
1335
1336     Node* startNode = start.deprecatedNode();
1337     if (!startNode)
1338         return;
1339     Node* endNode = end.deprecatedNode();
1340     int startOffset = start.deprecatedEditingOffset();
1341     int endOffset = end.deprecatedEditingOffset();
1342
1343     init(startNode, endNode, startOffset, endOffset);
1344 }
1345
1346 void SimplifiedBackwardsTextIterator::init(Node* startNode, Node* endNode, int startOffset, int endOffset)
1347 {
1348     if (!startNode->offsetInCharacters() && startOffset >= 0) {
1349         // NodeTraversal::childAt() will return 0 if the offset is out of range. We rely on this behavior
1350         // instead of calling countChildren() to avoid traversing the children twice.
1351         if (Node* childAtOffset = NodeTraversal::childAt(*startNode, startOffset)) {
1352             startNode = childAtOffset;
1353             startOffset = 0;
1354         }
1355     }
1356     if (!endNode->offsetInCharacters() && endOffset > 0) {
1357         // NodeTraversal::childAt() will return 0 if the offset is out of range. We rely on this behavior
1358         // instead of calling countChildren() to avoid traversing the children twice.
1359         if (Node* childAtOffset = NodeTraversal::childAt(*endNode, endOffset - 1)) {
1360             endNode = childAtOffset;
1361             endOffset = lastOffsetInNode(endNode);
1362         }
1363     }
1364
1365     m_node = endNode;
1366     setUpFullyClippedStack(m_fullyClippedStack, m_node);
1367     m_offset = endOffset;
1368     m_handledNode = false;
1369     m_handledChildren = !endOffset;
1370
1371     m_startNode = startNode;
1372     m_startOffset = startOffset;
1373     m_endNode = endNode;
1374     m_endOffset = endOffset;
1375
1376 #if ENABLE(ASSERT)
1377     // Need this just because of the assert.
1378     m_positionNode = endNode;
1379 #endif
1380
1381     m_lastTextNode = nullptr;
1382     m_lastCharacter = '\n';
1383
1384     m_havePassedStartNode = false;
1385
1386     advance();
1387 }
1388
1389 void SimplifiedBackwardsTextIterator::advance()
1390 {
1391     ASSERT(m_positionNode);
1392
1393     if (m_shouldStop)
1394         return;
1395
1396     if (m_stopsOnFormControls && HTMLFormControlElement::enclosingFormControlElement(m_node)) {
1397         m_shouldStop = true;
1398         return;
1399     }
1400
1401     m_positionNode = nullptr;
1402     m_textLength = 0;
1403
1404     while (m_node && !m_havePassedStartNode) {
1405         // Don't handle node if we start iterating at [node, 0].
1406         if (!m_handledNode && !(m_node == m_endNode && !m_endOffset)) {
1407             RenderObject* renderer = m_node->renderer();
1408             if (renderer && renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) {
1409                 // FIXME: What about CDATA_SECTION_NODE?
1410                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
1411                     m_handledNode = handleTextNode();
1412             } else if (renderer && (renderer->isImage() || renderer->isRenderPart())) {
1413                 if (renderer->style()->visibility() == VISIBLE && m_offset > 0)
1414                     m_handledNode = handleReplacedElement();
1415             } else {
1416                 m_handledNode = handleNonTextNode();
1417             }
1418             if (m_positionNode)
1419                 return;
1420         }
1421
1422         if (!m_handledChildren && m_node->hasChildren()) {
1423             m_node = m_node->lastChild();
1424             pushFullyClippedState(m_fullyClippedStack, m_node);
1425         } else {
1426             // Exit empty containers as we pass over them or containers
1427             // where [container, 0] is where we started iterating.
1428             if (!m_handledNode
1429                 && canHaveChildrenForEditing(m_node)
1430                 && m_node->parentNode()
1431                 && (!m_node->lastChild() || (m_node == m_endNode && !m_endOffset))) {
1432                 exitNode();
1433                 if (m_positionNode) {
1434                     m_handledNode = true;
1435                     m_handledChildren = true;
1436                     return;
1437                 }
1438             }
1439
1440             // Exit all other containers.
1441             while (!m_node->previousSibling()) {
1442                 if (!advanceRespectingRange(m_node->parentOrShadowHostNode()))
1443                     break;
1444                 m_fullyClippedStack.pop();
1445                 exitNode();
1446                 if (m_positionNode) {
1447                     m_handledNode = true;
1448                     m_handledChildren = true;
1449                     return;
1450                 }
1451             }
1452
1453             m_fullyClippedStack.pop();
1454             if (advanceRespectingRange(m_node->previousSibling()))
1455                 pushFullyClippedState(m_fullyClippedStack, m_node);
1456             else
1457                 m_node = nullptr;
1458         }
1459
1460         // For the purpose of word boundary detection,
1461         // we should iterate all visible text and trailing (collapsed) whitespaces.
1462         m_offset = m_node ? maxOffsetIncludingCollapsedSpaces(m_node) : 0;
1463         m_handledNode = false;
1464         m_handledChildren = false;
1465
1466         if (m_positionNode)
1467             return;
1468     }
1469 }
1470
1471 bool SimplifiedBackwardsTextIterator::handleTextNode()
1472 {
1473     m_lastTextNode = toText(m_node);
1474
1475     int startOffset;
1476     int offsetInNode;
1477     RenderText* renderer = handleFirstLetter(startOffset, offsetInNode);
1478     if (!renderer)
1479         return true;
1480
1481     String text = renderer->text();
1482     if (!renderer->firstTextBox() && text.length() > 0)
1483         return true;
1484
1485     m_positionEndOffset = m_offset;
1486     m_offset = startOffset + offsetInNode;
1487     m_positionNode = m_node;
1488     m_positionStartOffset = m_offset;
1489
1490     ASSERT(0 <= m_positionStartOffset - offsetInNode && m_positionStartOffset - offsetInNode <= static_cast<int>(text.length()));
1491     ASSERT(1 <= m_positionEndOffset - offsetInNode && m_positionEndOffset - offsetInNode <= static_cast<int>(text.length()));
1492     ASSERT(m_positionStartOffset <= m_positionEndOffset);
1493
1494     m_textLength = m_positionEndOffset - m_positionStartOffset;
1495     m_textOffset = m_positionStartOffset - offsetInNode;
1496     m_textContainer = text;
1497     m_singleCharacterBuffer = 0;
1498     RELEASE_ASSERT(static_cast<unsigned>(m_textOffset + m_textLength) <= text.length());
1499
1500     m_lastCharacter = text[m_positionEndOffset - 1];
1501
1502     return !m_shouldHandleFirstLetter;
1503 }
1504
1505 RenderText* SimplifiedBackwardsTextIterator::handleFirstLetter(int& startOffset, int& offsetInNode)
1506 {
1507     RenderText* renderer = toRenderText(m_node->renderer());
1508     startOffset = (m_node == m_startNode) ? m_startOffset : 0;
1509
1510     if (!renderer->isTextFragment()) {
1511         offsetInNode = 0;
1512         return renderer;
1513     }
1514
1515     RenderTextFragment* fragment = toRenderTextFragment(renderer);
1516     int offsetAfterFirstLetter = fragment->start();
1517     if (startOffset >= offsetAfterFirstLetter) {
1518         ASSERT(!m_shouldHandleFirstLetter);
1519         offsetInNode = offsetAfterFirstLetter;
1520         return renderer;
1521     }
1522
1523     if (!m_shouldHandleFirstLetter && offsetAfterFirstLetter < m_offset) {
1524         m_shouldHandleFirstLetter = true;
1525         offsetInNode = offsetAfterFirstLetter;
1526         return renderer;
1527     }
1528
1529     m_shouldHandleFirstLetter = false;
1530     offsetInNode = 0;
1531     RenderText* firstLetterRenderer = firstRenderTextInFirstLetter(fragment->firstLetter());
1532
1533     m_offset = firstLetterRenderer->caretMaxOffset();
1534     m_offset += collapsedSpaceLength(firstLetterRenderer, m_offset);
1535
1536     return firstLetterRenderer;
1537 }
1538
1539 bool SimplifiedBackwardsTextIterator::handleReplacedElement()
1540 {
1541     unsigned index = m_node->nodeIndex();
1542     // We want replaced elements to behave like punctuation for boundary
1543     // finding, and to simply take up space for the selection preservation
1544     // code in moveParagraphs, so we use a comma. Unconditionally emit
1545     // here because this iterator is only used for boundary finding.
1546     emitCharacter(',', m_node->parentNode(), index, index + 1);
1547     return true;
1548 }
1549
1550 bool SimplifiedBackwardsTextIterator::handleNonTextNode()
1551 {
1552     // We can use a linefeed in place of a tab because this simple iterator is only used to
1553     // find boundaries, not actual content. A linefeed breaks words, sentences, and paragraphs.
1554     if (shouldEmitNewlineForNode(m_node, m_emitsOriginalText) || shouldEmitNewlineAfterNode(*m_node) || shouldEmitTabBeforeNode(m_node)) {
1555         unsigned index = m_node->nodeIndex();
1556         // The start of this emitted range is wrong. Ensuring correctness would require
1557         // VisiblePositions and so would be slow. previousBoundary expects this.
1558         emitCharacter('\n', m_node->parentNode(), index + 1, index + 1);
1559     }
1560     return true;
1561 }
1562
1563 void SimplifiedBackwardsTextIterator::exitNode()
1564 {
1565     if (shouldEmitNewlineForNode(m_node, m_emitsOriginalText) || shouldEmitNewlineBeforeNode(*m_node) || shouldEmitTabBeforeNode(m_node)) {
1566         // The start of this emitted range is wrong. Ensuring correctness would require
1567         // VisiblePositions and so would be slow. previousBoundary expects this.
1568         emitCharacter('\n', m_node, 0, 0);
1569     }
1570 }
1571
1572 void SimplifiedBackwardsTextIterator::emitCharacter(UChar c, Node* node, int startOffset, int endOffset)
1573 {
1574     m_singleCharacterBuffer = c;
1575     m_positionNode = node;
1576     m_positionStartOffset = startOffset;
1577     m_positionEndOffset = endOffset;
1578     m_textOffset = 0;
1579     m_textLength = 1;
1580     m_lastCharacter = c;
1581 }
1582
1583 bool SimplifiedBackwardsTextIterator::advanceRespectingRange(Node* next)
1584 {
1585     if (!next)
1586         return false;
1587     m_havePassedStartNode |= m_node == m_startNode;
1588     if (m_havePassedStartNode)
1589         return false;
1590     m_node = next;
1591     return true;
1592 }
1593
1594 Node* SimplifiedBackwardsTextIterator::startContainer() const
1595 {
1596     if (m_positionNode)
1597         return m_positionNode;
1598     return m_startNode;
1599 }
1600
1601 int SimplifiedBackwardsTextIterator::endOffset() const
1602 {
1603     if (m_positionNode)
1604         return m_positionEndOffset;
1605     return m_startOffset;
1606 }
1607
1608 Position SimplifiedBackwardsTextIterator::startPosition() const
1609 {
1610     if (m_positionNode)
1611         return createLegacyEditingPosition(m_positionNode, m_positionStartOffset);
1612     return createLegacyEditingPosition(m_startNode, m_startOffset);
1613 }
1614
1615 Position SimplifiedBackwardsTextIterator::endPosition() const
1616 {
1617     if (m_positionNode)
1618         return createLegacyEditingPosition(m_positionNode, m_positionEndOffset);
1619     return createLegacyEditingPosition(m_startNode, m_startOffset);
1620 }
1621
1622 // --------
1623
1624 CharacterIterator::CharacterIterator(const Range* range, TextIteratorBehaviorFlags behavior)
1625     : m_offset(0)
1626     , m_runOffset(0)
1627     , m_atBreak(true)
1628     , m_textIterator(range, behavior)
1629 {
1630     initialize();
1631 }
1632
1633 CharacterIterator::CharacterIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags behavior)
1634     : m_offset(0)
1635     , m_runOffset(0)
1636     , m_atBreak(true)
1637     , m_textIterator(start, end, behavior)
1638 {
1639     initialize();
1640 }
1641
1642 void CharacterIterator::initialize()
1643 {
1644     while (!atEnd() && !m_textIterator.length())
1645         m_textIterator.advance();
1646 }
1647
1648 PassRefPtrWillBeRawPtr<Range> CharacterIterator::createRange() const
1649 {
1650     RefPtrWillBeRawPtr<Range> r = m_textIterator.createRange();
1651     if (!m_textIterator.atEnd()) {
1652         if (m_textIterator.length() <= 1) {
1653             ASSERT(!m_runOffset);
1654         } else {
1655             Node* n = r->startContainer();
1656             ASSERT(n == r->endContainer());
1657             int offset = r->startOffset() + m_runOffset;
1658             r->setStart(n, offset, ASSERT_NO_EXCEPTION);
1659             r->setEnd(n, offset + 1, ASSERT_NO_EXCEPTION);
1660         }
1661     }
1662     return r.release();
1663 }
1664
1665 Document* CharacterIterator::ownerDocument() const
1666 {
1667     return m_textIterator.ownerDocument();
1668 }
1669
1670 Node* CharacterIterator::startContainer() const
1671 {
1672     return m_textIterator.startContainer();
1673 }
1674
1675 Node* CharacterIterator::endContainer() const
1676 {
1677     return m_textIterator.endContainer();
1678 }
1679
1680 int CharacterIterator::startOffset() const
1681 {
1682     if (!m_textIterator.atEnd()) {
1683         if (m_textIterator.length() > 1)
1684             return m_textIterator.startOffset() + m_runOffset;
1685         ASSERT(!m_runOffset);
1686     }
1687     return m_textIterator.startOffset();
1688 }
1689
1690 int CharacterIterator::endOffset() const
1691 {
1692     if (!m_textIterator.atEnd()) {
1693         if (m_textIterator.length() > 1)
1694             return m_textIterator.startOffset() + m_runOffset + 1;
1695         ASSERT(!m_runOffset);
1696     }
1697     return m_textIterator.endOffset();
1698 }
1699
1700 Position CharacterIterator::startPosition() const
1701 {
1702     if (!m_textIterator.atEnd()) {
1703         if (m_textIterator.length() > 1) {
1704             Node* n = m_textIterator.startContainer();
1705             int offset = m_textIterator.startOffset() + m_runOffset;
1706             return createLegacyEditingPosition(n, offset);
1707         }
1708         ASSERT(!m_runOffset);
1709     }
1710     return m_textIterator.startPosition();
1711 }
1712
1713 Position CharacterIterator::endPosition() const
1714 {
1715     if (!m_textIterator.atEnd()) {
1716         if (m_textIterator.length() > 1) {
1717             Node* n = m_textIterator.startContainer();
1718             int offset = m_textIterator.startOffset() + m_runOffset;
1719             return createLegacyEditingPosition(n, offset + 1);
1720         }
1721         ASSERT(!m_runOffset);
1722     }
1723     return m_textIterator.endPosition();
1724 }
1725
1726 void CharacterIterator::advance(int count)
1727 {
1728     if (count <= 0) {
1729         ASSERT(!count);
1730         return;
1731     }
1732
1733     m_atBreak = false;
1734
1735     // easy if there is enough left in the current m_textIterator run
1736     int remaining = m_textIterator.length() - m_runOffset;
1737     if (count < remaining) {
1738         m_runOffset += count;
1739         m_offset += count;
1740         return;
1741     }
1742
1743     // exhaust the current m_textIterator run
1744     count -= remaining;
1745     m_offset += remaining;
1746
1747     // move to a subsequent m_textIterator run
1748     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1749         int runLength = m_textIterator.length();
1750         if (!runLength) {
1751             m_atBreak = m_textIterator.breaksAtReplacedElement();
1752         } else {
1753             // see whether this is m_textIterator to use
1754             if (count < runLength) {
1755                 m_runOffset = count;
1756                 m_offset += count;
1757                 return;
1758             }
1759
1760             // exhaust this m_textIterator run
1761             count -= runLength;
1762             m_offset += runLength;
1763         }
1764     }
1765
1766     // ran to the end of the m_textIterator... no more runs left
1767     m_atBreak = true;
1768     m_runOffset = 0;
1769 }
1770
1771 static void calculateCharacterSubrange(CharacterIterator& it, int offset, int length, Position& startPosition, Position& endPosition)
1772 {
1773     it.advance(offset);
1774     startPosition = it.startPosition();
1775
1776     if (length > 1)
1777         it.advance(length - 1);
1778     endPosition = it.endPosition();
1779 }
1780
1781 BackwardsCharacterIterator::BackwardsCharacterIterator(const Range* range, TextIteratorBehaviorFlags behavior)
1782     : m_offset(0)
1783     , m_runOffset(0)
1784     , m_atBreak(true)
1785     , m_textIterator(range, behavior)
1786 {
1787     while (!atEnd() && !m_textIterator.length())
1788         m_textIterator.advance();
1789 }
1790
1791 BackwardsCharacterIterator::BackwardsCharacterIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags behavior)
1792     : m_offset(0)
1793     , m_runOffset(0)
1794     , m_atBreak(true)
1795     , m_textIterator(start, end, behavior)
1796 {
1797     while (!atEnd() && !m_textIterator.length())
1798         m_textIterator.advance();
1799 }
1800
1801 Position BackwardsCharacterIterator::endPosition() const
1802 {
1803     if (!m_textIterator.atEnd()) {
1804         if (m_textIterator.length() > 1) {
1805             Node* n = m_textIterator.startContainer();
1806             return createLegacyEditingPosition(n, m_textIterator.endOffset() - m_runOffset);
1807         }
1808         ASSERT(!m_runOffset);
1809     }
1810     return m_textIterator.endPosition();
1811 }
1812
1813 void BackwardsCharacterIterator::advance(int count)
1814 {
1815     if (count <= 0) {
1816         ASSERT(!count);
1817         return;
1818     }
1819
1820     m_atBreak = false;
1821
1822     int remaining = m_textIterator.length() - m_runOffset;
1823     if (count < remaining) {
1824         m_runOffset += count;
1825         m_offset += count;
1826         return;
1827     }
1828
1829     count -= remaining;
1830     m_offset += remaining;
1831
1832     for (m_textIterator.advance(); !atEnd(); m_textIterator.advance()) {
1833         int runLength = m_textIterator.length();
1834         if (!runLength) {
1835             m_atBreak = true;
1836         } else {
1837             if (count < runLength) {
1838                 m_runOffset = count;
1839                 m_offset += count;
1840                 return;
1841             }
1842
1843             count -= runLength;
1844             m_offset += runLength;
1845         }
1846     }
1847
1848     m_atBreak = true;
1849     m_runOffset = 0;
1850 }
1851
1852 // --------
1853
1854 WordAwareIterator::WordAwareIterator(const Position& start, const Position& end)
1855     : m_didLookAhead(true) // So we consider the first chunk from the text iterator.
1856     , m_textIterator(start, end)
1857 {
1858     advance(); // Get in position over the first chunk of text.
1859 }
1860
1861 WordAwareIterator::~WordAwareIterator()
1862 {
1863 }
1864
1865 // FIXME: Performance could be bad for huge spans next to each other that don't fall on word boundaries.
1866
1867 void WordAwareIterator::advance()
1868 {
1869     m_buffer.clear();
1870
1871     // If last time we did a look-ahead, start with that looked-ahead chunk now
1872     if (!m_didLookAhead) {
1873         ASSERT(!m_textIterator.atEnd());
1874         m_textIterator.advance();
1875     }
1876     m_didLookAhead = false;
1877
1878     // Go to next non-empty chunk.
1879     while (!m_textIterator.atEnd() && !m_textIterator.length())
1880         m_textIterator.advance();
1881
1882     if (m_textIterator.atEnd())
1883         return;
1884
1885     while (1) {
1886         // If this chunk ends in whitespace we can just use it as our chunk.
1887         if (isSpaceOrNewline(m_textIterator.characterAt(m_textIterator.length() - 1)))
1888             return;
1889
1890         // If this is the first chunk that failed, save it in m_buffer before look ahead.
1891         if (m_buffer.isEmpty())
1892             m_textIterator.appendTextTo(m_buffer);
1893
1894         // Look ahead to next chunk. If it is whitespace or a break, we can use the previous stuff
1895         m_textIterator.advance();
1896         if (m_textIterator.atEnd() || !m_textIterator.length() || isSpaceOrNewline(m_textIterator.characterAt(0))) {
1897             m_didLookAhead = true;
1898             return;
1899         }
1900
1901         // Start gobbling chunks until we get to a suitable stopping point
1902         m_textIterator.appendTextTo(m_buffer);
1903     }
1904 }
1905
1906 int WordAwareIterator::length() const
1907 {
1908     if (!m_buffer.isEmpty())
1909         return m_buffer.size();
1910     return m_textIterator.length();
1911 }
1912
1913 String WordAwareIterator::substring(unsigned position, unsigned length) const
1914 {
1915     if (!m_buffer.isEmpty())
1916         return String(m_buffer.data() + position, length);
1917     return m_textIterator.substring(position, length);
1918 }
1919
1920 UChar WordAwareIterator::characterAt(unsigned index) const
1921 {
1922     if (!m_buffer.isEmpty())
1923         return m_buffer[index];
1924     return m_textIterator.characterAt(index);
1925 }
1926
1927 // --------
1928
1929 static const size_t minimumSearchBufferSize = 8192;
1930
1931 #if ENABLE(ASSERT)
1932 static bool searcherInUse;
1933 #endif
1934
1935 static UStringSearch* createSearcher()
1936 {
1937     // Provide a non-empty pattern and non-empty text so usearch_open will not fail,
1938     // but it doesn't matter exactly what it is, since we don't perform any searches
1939     // without setting both the pattern and the text.
1940     UErrorCode status = U_ZERO_ERROR;
1941     String searchCollatorName = currentSearchLocaleID() + String("@collation=search");
1942     UStringSearch* searcher = usearch_open(&newlineCharacter, 1, &newlineCharacter, 1, searchCollatorName.utf8().data(), 0, &status);
1943     ASSERT(status == U_ZERO_ERROR || status == U_USING_FALLBACK_WARNING || status == U_USING_DEFAULT_WARNING);
1944     return searcher;
1945 }
1946
1947 static UStringSearch* searcher()
1948 {
1949     static UStringSearch* searcher = createSearcher();
1950     return searcher;
1951 }
1952
1953 static inline void lockSearcher()
1954 {
1955 #if ENABLE(ASSERT)
1956     ASSERT(!searcherInUse);
1957     searcherInUse = true;
1958 #endif
1959 }
1960
1961 static inline void unlockSearcher()
1962 {
1963 #if ENABLE(ASSERT)
1964     ASSERT(searcherInUse);
1965     searcherInUse = false;
1966 #endif
1967 }
1968
1969 inline SearchBuffer::SearchBuffer(const String& target, FindOptions options)
1970     : m_options(options)
1971     , m_prefixLength(0)
1972     , m_numberOfCharactersJustAppended(0)
1973     , m_atBreak(true)
1974     , m_needsMoreContext(options & AtWordStarts)
1975     , m_targetRequiresKanaWorkaround(containsKanaLetters(target))
1976 {
1977     ASSERT(!target.isEmpty());
1978     target.appendTo(m_target);
1979
1980     // FIXME: We'd like to tailor the searcher to fold quote marks for us instead
1981     // of doing it in a separate replacement pass here, but ICU doesn't offer a way
1982     // to add tailoring on top of the locale-specific tailoring as of this writing.
1983     foldQuoteMarksAndSoftHyphens(m_target.data(), m_target.size());
1984
1985     size_t targetLength = m_target.size();
1986     m_buffer.reserveInitialCapacity(std::max(targetLength * 8, minimumSearchBufferSize));
1987     m_overlap = m_buffer.capacity() / 4;
1988
1989     if ((m_options & AtWordStarts) && targetLength) {
1990         UChar32 targetFirstCharacter;
1991         U16_GET(m_target.data(), 0, 0, targetLength, targetFirstCharacter);
1992         // Characters in the separator category never really occur at the beginning of a word,
1993         // so if the target begins with such a character, we just ignore the AtWordStart option.
1994         if (isSeparator(targetFirstCharacter)) {
1995             m_options &= ~AtWordStarts;
1996             m_needsMoreContext = false;
1997         }
1998     }
1999
2000     // Grab the single global searcher.
2001     // If we ever have a reason to do more than once search buffer at once, we'll have
2002     // to move to multiple searchers.
2003     lockSearcher();
2004
2005     UStringSearch* searcher = blink::searcher();
2006     UCollator* collator = usearch_getCollator(searcher);
2007
2008     UCollationStrength strength = m_options & CaseInsensitive ? UCOL_PRIMARY : UCOL_TERTIARY;
2009     if (ucol_getStrength(collator) != strength) {
2010         ucol_setStrength(collator, strength);
2011         usearch_reset(searcher);
2012     }
2013
2014     UErrorCode status = U_ZERO_ERROR;
2015     usearch_setPattern(searcher, m_target.data(), targetLength, &status);
2016     ASSERT(status == U_ZERO_ERROR);
2017
2018     // The kana workaround requires a normalized copy of the target string.
2019     if (m_targetRequiresKanaWorkaround)
2020         normalizeCharactersIntoNFCForm(m_target.data(), m_target.size(), m_normalizedTarget);
2021 }
2022
2023 inline SearchBuffer::~SearchBuffer()
2024 {
2025     // Leave the static object pointing to a valid string.
2026     UErrorCode status = U_ZERO_ERROR;
2027     usearch_setPattern(blink::searcher(), &newlineCharacter, 1, &status);
2028     ASSERT(status == U_ZERO_ERROR);
2029
2030     unlockSearcher();
2031 }
2032
2033 template<typename CharType>
2034 inline void SearchBuffer::append(const CharType* characters, size_t length)
2035 {
2036     ASSERT(length);
2037
2038     if (m_atBreak) {
2039         m_buffer.shrink(0);
2040         m_prefixLength = 0;
2041         m_atBreak = false;
2042     } else if (m_buffer.size() == m_buffer.capacity()) {
2043         memcpy(m_buffer.data(), m_buffer.data() + m_buffer.size() - m_overlap, m_overlap * sizeof(UChar));
2044         m_prefixLength -= std::min(m_prefixLength, m_buffer.size() - m_overlap);
2045         m_buffer.shrink(m_overlap);
2046     }
2047
2048     size_t oldLength = m_buffer.size();
2049     size_t usableLength = std::min(m_buffer.capacity() - oldLength, length);
2050     ASSERT(usableLength);
2051     m_buffer.resize(oldLength + usableLength);
2052     UChar* destination = m_buffer.data() + oldLength;
2053     StringImpl::copyChars(destination, characters, usableLength);
2054     foldQuoteMarksAndSoftHyphens(destination, usableLength);
2055     m_numberOfCharactersJustAppended = usableLength;
2056 }
2057
2058 inline bool SearchBuffer::needsMoreContext() const
2059 {
2060     return m_needsMoreContext;
2061 }
2062
2063 inline void SearchBuffer::prependContext(const UChar* characters, size_t length)
2064 {
2065     ASSERT(m_needsMoreContext);
2066     ASSERT(m_prefixLength == m_buffer.size());
2067
2068     if (!length)
2069         return;
2070
2071     m_atBreak = false;
2072
2073     size_t wordBoundaryContextStart = length;
2074     if (wordBoundaryContextStart) {
2075         U16_BACK_1(characters, 0, wordBoundaryContextStart);
2076         wordBoundaryContextStart = startOfLastWordBoundaryContext(characters, wordBoundaryContextStart);
2077     }
2078
2079     size_t usableLength = std::min(m_buffer.capacity() - m_prefixLength, length - wordBoundaryContextStart);
2080     m_buffer.prepend(characters + length - usableLength, usableLength);
2081     m_prefixLength += usableLength;
2082
2083     if (wordBoundaryContextStart || m_prefixLength == m_buffer.capacity())
2084         m_needsMoreContext = false;
2085 }
2086
2087 inline bool SearchBuffer::atBreak() const
2088 {
2089     return m_atBreak;
2090 }
2091
2092 inline void SearchBuffer::reachedBreak()
2093 {
2094     m_atBreak = true;
2095 }
2096
2097 inline bool SearchBuffer::isBadMatch(const UChar* match, size_t matchLength) const
2098 {
2099     // This function implements the kana workaround. If usearch treats
2100     // it as a match, but we do not want to, then it's a "bad match".
2101     if (!m_targetRequiresKanaWorkaround)
2102         return false;
2103
2104     // Normalize into a match buffer. We reuse a single buffer rather than
2105     // creating a new one each time.
2106     normalizeCharactersIntoNFCForm(match, matchLength, m_normalizedMatch);
2107
2108     return !checkOnlyKanaLettersInStrings(m_normalizedTarget.begin(), m_normalizedTarget.size(), m_normalizedMatch.begin(), m_normalizedMatch.size());
2109 }
2110
2111 inline bool SearchBuffer::isWordStartMatch(size_t start, size_t length) const
2112 {
2113     ASSERT(m_options & AtWordStarts);
2114
2115     if (!start)
2116         return true;
2117
2118     int size = m_buffer.size();
2119     int offset = start;
2120     UChar32 firstCharacter;
2121     U16_GET(m_buffer.data(), 0, offset, size, firstCharacter);
2122
2123     if (m_options & TreatMedialCapitalAsWordStart) {
2124         UChar32 previousCharacter;
2125         U16_PREV(m_buffer.data(), 0, offset, previousCharacter);
2126
2127         if (isSeparator(firstCharacter)) {
2128             // The start of a separator run is a word start (".org" in "webkit.org").
2129             if (!isSeparator(previousCharacter))
2130                 return true;
2131         } else if (isASCIIUpper(firstCharacter)) {
2132             // The start of an uppercase run is a word start ("Kit" in "WebKit").
2133             if (!isASCIIUpper(previousCharacter))
2134                 return true;
2135             // The last character of an uppercase run followed by a non-separator, non-digit
2136             // is a word start ("Request" in "XMLHTTPRequest").
2137             offset = start;
2138             U16_FWD_1(m_buffer.data(), offset, size);
2139             UChar32 nextCharacter = 0;
2140             if (offset < size)
2141                 U16_GET(m_buffer.data(), 0, offset, size, nextCharacter);
2142             if (!isASCIIUpper(nextCharacter) && !isASCIIDigit(nextCharacter) && !isSeparator(nextCharacter))
2143                 return true;
2144         } else if (isASCIIDigit(firstCharacter)) {
2145             // The start of a digit run is a word start ("2" in "WebKit2").
2146             if (!isASCIIDigit(previousCharacter))
2147                 return true;
2148         } else if (isSeparator(previousCharacter) || isASCIIDigit(previousCharacter)) {
2149             // The start of a non-separator, non-uppercase, non-digit run is a word start,
2150             // except after an uppercase. ("org" in "webkit.org", but not "ore" in "WebCore").
2151             return true;
2152         }
2153     }
2154
2155     // Chinese and Japanese lack word boundary marks, and there is no clear agreement on what constitutes
2156     // a word, so treat the position before any CJK character as a word start.
2157     if (Character::isCJKIdeographOrSymbol(firstCharacter))
2158         return true;
2159
2160     size_t wordBreakSearchStart = start + length;
2161     while (wordBreakSearchStart > start)
2162         wordBreakSearchStart = findNextWordFromIndex(m_buffer.data(), m_buffer.size(), wordBreakSearchStart, false /* backwards */);
2163     return wordBreakSearchStart == start;
2164 }
2165
2166 inline size_t SearchBuffer::search(size_t& start)
2167 {
2168     size_t size = m_buffer.size();
2169     if (m_atBreak) {
2170         if (!size)
2171             return 0;
2172     } else {
2173         if (size != m_buffer.capacity())
2174             return 0;
2175     }
2176
2177     UStringSearch* searcher = blink::searcher();
2178
2179     UErrorCode status = U_ZERO_ERROR;
2180     usearch_setText(searcher, m_buffer.data(), size, &status);
2181     ASSERT(status == U_ZERO_ERROR);
2182
2183     usearch_setOffset(searcher, m_prefixLength, &status);
2184     ASSERT(status == U_ZERO_ERROR);
2185
2186     int matchStart = usearch_next(searcher, &status);
2187     ASSERT(status == U_ZERO_ERROR);
2188
2189 nextMatch:
2190     if (!(matchStart >= 0 && static_cast<size_t>(matchStart) < size)) {
2191         ASSERT(matchStart == USEARCH_DONE);
2192         return 0;
2193     }
2194
2195     // Matches that start in the overlap area are only tentative.
2196     // The same match may appear later, matching more characters,
2197     // possibly including a combining character that's not yet in the buffer.
2198     if (!m_atBreak && static_cast<size_t>(matchStart) >= size - m_overlap) {
2199         size_t overlap = m_overlap;
2200         if (m_options & AtWordStarts) {
2201             // Ensure that there is sufficient context before matchStart the next time around for
2202             // determining if it is at a word boundary.
2203             int wordBoundaryContextStart = matchStart;
2204             U16_BACK_1(m_buffer.data(), 0, wordBoundaryContextStart);
2205             wordBoundaryContextStart = startOfLastWordBoundaryContext(m_buffer.data(), wordBoundaryContextStart);
2206             overlap = std::min(size - 1, std::max(overlap, size - wordBoundaryContextStart));
2207         }
2208         memcpy(m_buffer.data(), m_buffer.data() + size - overlap, overlap * sizeof(UChar));
2209         m_prefixLength -= std::min(m_prefixLength, size - overlap);
2210         m_buffer.shrink(overlap);
2211         return 0;
2212     }
2213
2214     size_t matchedLength = usearch_getMatchedLength(searcher);
2215     ASSERT_WITH_SECURITY_IMPLICATION(matchStart + matchedLength <= size);
2216
2217     // If this match is "bad", move on to the next match.
2218     if (isBadMatch(m_buffer.data() + matchStart, matchedLength) || ((m_options & AtWordStarts) && !isWordStartMatch(matchStart, matchedLength))) {
2219         matchStart = usearch_next(searcher, &status);
2220         ASSERT(status == U_ZERO_ERROR);
2221         goto nextMatch;
2222     }
2223
2224     size_t newSize = size - (matchStart + 1);
2225     memmove(m_buffer.data(), m_buffer.data() + matchStart + 1, newSize * sizeof(UChar));
2226     m_prefixLength -= std::min<size_t>(m_prefixLength, matchStart + 1);
2227     m_buffer.shrink(newSize);
2228
2229     start = size - matchStart;
2230     return matchedLength;
2231 }
2232
2233 // --------
2234
2235 int TextIterator::rangeLength(const Range* r, bool forSelectionPreservation)
2236 {
2237     int length = 0;
2238     TextIteratorBehaviorFlags behaviorFlags = TextIteratorEmitsObjectReplacementCharacter;
2239     if (forSelectionPreservation)
2240         behaviorFlags |= TextIteratorEmitsCharactersBetweenAllVisiblePositions;
2241     for (TextIterator it(r, behaviorFlags); !it.atEnd(); it.advance())
2242         length += it.length();
2243
2244     return length;
2245 }
2246
2247 int TextIterator::rangeLength(const Position& start, const Position& end, bool forSelectionPreservation)
2248 {
2249     int length = 0;
2250     TextIteratorBehaviorFlags behaviorFlags = TextIteratorEmitsObjectReplacementCharacter;
2251     if (forSelectionPreservation)
2252         behaviorFlags |= TextIteratorEmitsCharactersBetweenAllVisiblePositions;
2253     for (TextIterator it(start, end, behaviorFlags); !it.atEnd(); it.advance())
2254         length += it.length();
2255
2256     return length;
2257 }
2258
2259 PassRefPtrWillBeRawPtr<Range> TextIterator::subrange(Range* entireRange, int characterOffset, int characterCount)
2260 {
2261     CharacterIterator entireRangeIterator(entireRange, TextIteratorEmitsObjectReplacementCharacter);
2262     Position start;
2263     Position end;
2264     calculateCharacterSubrange(entireRangeIterator, characterOffset, characterCount, start, end);
2265     return Range::create(entireRange->ownerDocument(), start, end);
2266 }
2267
2268 void TextIterator::subrange(Position& start, Position& end, int characterOffset, int characterCount)
2269 {
2270     CharacterIterator entireRangeIterator(start, end, TextIteratorEmitsObjectReplacementCharacter);
2271     calculateCharacterSubrange(entireRangeIterator, characterOffset, characterCount, start, end);
2272 }
2273
2274 // --------
2275
2276 static String createPlainText(TextIterator& it)
2277 {
2278     // The initial buffer size can be critical for performance: https://bugs.webkit.org/show_bug.cgi?id=81192
2279     static const unsigned initialCapacity = 1 << 15;
2280
2281     unsigned bufferLength = 0;
2282     StringBuilder builder;
2283     builder.reserveCapacity(initialCapacity);
2284
2285     for (; !it.atEnd(); it.advance()) {
2286         it.appendTextToStringBuilder(builder);
2287         bufferLength += it.length();
2288     }
2289
2290     if (!bufferLength)
2291         return emptyString();
2292
2293     return builder.toString();
2294 }
2295
2296 String plainText(const Range* r, TextIteratorBehaviorFlags behavior)
2297 {
2298     TextIterator it(r, behavior);
2299     return createPlainText(it);
2300 }
2301
2302 String plainText(const Position& start, const Position& end, TextIteratorBehaviorFlags behavior)
2303 {
2304     TextIterator it(start, end, behavior);
2305     return createPlainText(it);
2306 }
2307
2308 static PassRefPtrWillBeRawPtr<Range> collapsedToBoundary(const Range* range, bool forward)
2309 {
2310     RefPtrWillBeRawPtr<Range> result = range->cloneRange();
2311     result->collapse(!forward);
2312     return result.release();
2313 }
2314
2315 // Check if there's any unpaird surrogate code point.
2316 // Non-character code points are not checked.
2317 static bool isValidUTF16(const String& s)
2318 {
2319     if (s.is8Bit())
2320         return true;
2321     const UChar* ustr = s.characters16();
2322     size_t length = s.length();
2323     size_t position = 0;
2324     while (position < length) {
2325         UChar32 character;
2326         U16_NEXT(ustr, position, length, character);
2327         if (U_IS_SURROGATE(character))
2328             return false;
2329     }
2330     return true;
2331 }
2332
2333 static size_t findPlainTextInternal(CharacterIterator& it, const String& target, FindOptions options, size_t& matchStart)
2334 {
2335     matchStart = 0;
2336     size_t matchLength = 0;
2337
2338     if (!isValidUTF16(target))
2339         return 0;
2340
2341     SearchBuffer buffer(target, options);
2342
2343     if (buffer.needsMoreContext()) {
2344         RefPtrWillBeRawPtr<Range> beforeStartRange = it.ownerDocument()->createRange();
2345         beforeStartRange->setEnd(it.startContainer(), it.startOffset(), IGNORE_EXCEPTION);
2346         for (SimplifiedBackwardsTextIterator backwardsIterator(beforeStartRange.get()); !backwardsIterator.atEnd(); backwardsIterator.advance()) {
2347             Vector<UChar, 1024> characters;
2348             backwardsIterator.prependTextTo(characters);
2349             buffer.prependContext(characters.data(), characters.size());
2350             if (!buffer.needsMoreContext())
2351                 break;
2352         }
2353     }
2354
2355     while (!it.atEnd()) {
2356         it.appendTextTo(buffer);
2357         it.advance(buffer.numberOfCharactersJustAppended());
2358 tryAgain:
2359         size_t matchStartOffset;
2360         if (size_t newMatchLength = buffer.search(matchStartOffset)) {
2361             // Note that we found a match, and where we found it.
2362             size_t lastCharacterInBufferOffset = it.characterOffset();
2363             ASSERT(lastCharacterInBufferOffset >= matchStartOffset);
2364             matchStart = lastCharacterInBufferOffset - matchStartOffset;
2365             matchLength = newMatchLength;
2366             // If searching forward, stop on the first match.
2367             // If searching backward, don't stop, so we end up with the last match.
2368             if (!(options & Backwards))
2369                 break;
2370             goto tryAgain;
2371         }
2372         if (it.atBreak() && !buffer.atBreak()) {
2373             buffer.reachedBreak();
2374             goto tryAgain;
2375         }
2376     }
2377
2378     return matchLength;
2379 }
2380
2381 static const TextIteratorBehaviorFlags iteratorFlagsForFindPlainText = TextIteratorEntersTextControls | TextIteratorEntersAuthorShadowRoots | TextIteratorDoesNotBreakAtReplacedElement;
2382
2383 PassRefPtrWillBeRawPtr<Range> findPlainText(const Range* range, const String& target, FindOptions options)
2384 {
2385     // First, find the text.
2386     size_t matchStart;
2387     size_t matchLength;
2388     {
2389         CharacterIterator findIterator(range, iteratorFlagsForFindPlainText);
2390         matchLength = findPlainTextInternal(findIterator, target, options, matchStart);
2391         if (!matchLength)
2392             return collapsedToBoundary(range, !(options & Backwards));
2393     }
2394
2395     // Then, find the document position of the start and the end of the text.
2396     CharacterIterator computeRangeIterator(range, iteratorFlagsForFindPlainText);
2397     Position resultStart;
2398     Position resultEnd;
2399     calculateCharacterSubrange(computeRangeIterator, matchStart, matchLength, resultStart, resultEnd);
2400     return Range::create(range->ownerDocument(), resultStart, resultEnd);
2401 }
2402
2403 void findPlainText(const Position& inputStart, const Position& inputEnd, const String& target, FindOptions options, Position& resultStart, Position& resultEnd)
2404 {
2405     resultStart.clear();
2406     resultEnd.clear();
2407     // CharacterIterator requires renderers to be up-to-date.
2408     if (!inputStart.inDocument())
2409         return;
2410     ASSERT(inputStart.document() == inputEnd.document());
2411
2412     // FIXME: Reduce the code duplication with above (but how?).
2413     size_t matchStart;
2414     size_t matchLength;
2415     {
2416         CharacterIterator findIterator(inputStart, inputEnd, iteratorFlagsForFindPlainText);
2417         matchLength = findPlainTextInternal(findIterator, target, options, matchStart);
2418         if (!matchLength) {
2419             const Position& collapseTo = options & Backwards ? inputStart : inputEnd;
2420             resultStart = collapseTo;
2421             resultEnd = collapseTo;
2422             return;
2423         }
2424     }
2425
2426     CharacterIterator computeRangeIterator(inputStart, inputEnd, iteratorFlagsForFindPlainText);
2427     calculateCharacterSubrange(computeRangeIterator, matchStart, matchLength, resultStart, resultEnd);
2428 }
2429
2430 }