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

   1 /*
   2  * Copyright (C) 2004, 2006, 2009 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef TextIterator_h
  27 #define TextIterator_h
  28
  29 #include "core/dom/Range.h"
  30 #include "core/editing/FindOptions.h"
  31 #include "platform/heap/Handle.h"
  32 #include "wtf/Vector.h"
  33
  34 namespace blink {
  35
  36 class InlineTextBox;
  37 class RenderText;
  38 class RenderTextFragment;
  39
  40 enum TextIteratorBehavior {
  41     TextIteratorDefaultBehavior = 0,
  42     TextIteratorEmitsCharactersBetweenAllVisiblePositions = 1 << 0,
  43     TextIteratorEntersTextControls = 1 << 1,
  44     TextIteratorIgnoresStyleVisibility = 1 << 2,
  45     TextIteratorEmitsOriginalText = 1 << 3,
  46     TextIteratorStopsOnFormControls = 1 << 4,
  47     TextIteratorEmitsImageAltText = 1 << 5,
  48     TextIteratorEntersAuthorShadowRoots = 1 << 6,
  49     TextIteratorEmitsObjectReplacementCharacter = 1 << 7,
  50     TextIteratorDoesNotBreakAtReplacedElement = 1 << 8
  51 };
  52 typedef unsigned TextIteratorBehaviorFlags;
  53
  54 String plainText(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  55 String plainText(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  56 PassRefPtrWillBeRawPtr<Range> findPlainText(const Range*, const String&, FindOptions);
  57 void findPlainText(const Position& inputStart, const Position& inputEnd, const String&, FindOptions, Position& resultStart, Position& resultEnd);
  58
  59 class BitStack {
  60 public:
  61     BitStack();
  62     ~BitStack();
  63
  64     void push(bool);
  65     void pop();
  66
  67     bool top() const;
  68     unsigned size() const;
  69
  70 private:
  71     unsigned m_size;
  72     Vector<unsigned, 1> m_words;
  73 };
  74
  75 // Iterates through the DOM range, returning all the text, and 0-length boundaries
  76 // at points where replaced elements break up the text flow.  The text comes back in
  77 // chunks so as to optimize for performance of the iteration.
  78
  79 class TextIterator {
  80     STACK_ALLOCATED();
  81 public:
  82     explicit TextIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  83     // [start, end] indicates the document range that the iteration should take place within (both ends inclusive).
  84     TextIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  85     ~TextIterator();
  86
  87     bool atEnd() const { return !m_positionNode || m_shouldStop; }
  88     void advance();
  89     bool isInsideReplacedElement() const;
  90
  91     int length() const { return m_textLength; }
  92     UChar characterAt(unsigned index) const;
  93     String substring(unsigned position, unsigned length) const;
  94     void appendTextToStringBuilder(StringBuilder&, unsigned position = 0, unsigned maxLength = UINT_MAX) const;
  95
  96     template<typename BufferType>
  97     void appendTextTo(BufferType& output, unsigned position = 0)
  98     {
  99         ASSERT_WITH_SECURITY_IMPLICATION(position <= static_cast<unsigned>(length()));
 100         unsigned lengthToAppend = length() - position;
 101         if (!lengthToAppend)
 102             return;
 103         if (m_singleCharacterBuffer) {
 104             ASSERT(!position);
 105             ASSERT(length() == 1);
 106             output.append(&m_singleCharacterBuffer, 1);
 107         } else {
 108             string().appendTo(output, startOffset() + position, lengthToAppend);
 109         }
 110     }
 111
 112     PassRefPtrWillBeRawPtr<Range> createRange() const;
 113     Node* node() const;
 114
 115     Document* ownerDocument() const;
 116     Node* startContainer() const;
 117     Node* endContainer() const;
 118     int startOffset() const;
 119     int endOffset() const;
 120     Position startPosition() const;
 121     Position endPosition() const;
 122
 123     bool breaksAtReplacedElement() { return m_breaksAtReplacedElement; }
 124
 125     // Computes the length of the given range using a text iterator. The default
 126     // iteration behavior is to always emit object replacement characters for
 127     // replaced elements. When |forSelectionPreservation| is set to true, it
 128     // also emits spaces for other non-text nodes using the
 129     // |TextIteratorEmitsCharactersBetweenAllVisiblePosition| mode.
 130     static int rangeLength(const Range*, bool forSelectionPreservation = false);
 131     static int rangeLength(const Position& start, const Position& end, bool forSelectionPreservation = false);
 132     static PassRefPtrWillBeRawPtr<Range> subrange(Range* entireRange, int characterOffset, int characterCount);
 133     static void subrange(Position& start, Position& end, int characterOffset, int characterCount);
 134
 135 private:
 136     enum IterationProgress {
 137         HandledNone,
 138         HandledAuthorShadowRoots,
 139         HandledUserAgentShadowRoot,
 140         HandledNode,
 141         HandledChildren
 142     };
 143
 144     void initialize(const Position& start, const Position& end);
 145
 146     void flushPositionOffsets() const;
 147     int positionStartOffset() const { return m_positionStartOffset; }
 148     const String& string() const { return m_text; }
 149     void exitNode();
 150     bool shouldRepresentNodeOffsetZero();
 151     bool shouldEmitSpaceBeforeAndAfterNode(Node*);
 152     void representNodeOffsetZero();
 153     bool handleTextNode();
 154     bool handleReplacedElement();
 155     bool handleNonTextNode();
 156     void handleTextBox();
 157     void handleTextNodeFirstLetter(RenderTextFragment*);
 158     bool hasVisibleTextNode(RenderText*);
 159     void emitCharacter(UChar, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset);
 160     void emitText(Node* textNode, RenderText* renderer, int textStartOffset, int textEndOffset);
 161
 162     // Current position, not necessarily of the text being returned, but position
 163     // as we walk through the DOM tree.
 164     RawPtrWillBeMember<Node> m_node;
 165     int m_offset;
 166     IterationProgress m_iterationProgress;
 167     BitStack m_fullyClippedStack;
 168     int m_shadowDepth;
 169
 170     // The range.
 171     RawPtrWillBeMember<Node> m_startContainer;
 172     int m_startOffset;
 173     RawPtrWillBeMember<Node> m_endContainer;
 174     int m_endOffset;
 175     RawPtrWillBeMember<Node> m_pastEndNode;
 176
 177     // The current text and its position, in the form to be returned from the iterator.
 178     RawPtrWillBeMember<Node> m_positionNode;
 179     mutable RawPtrWillBeMember<Node> m_positionOffsetBaseNode;
 180     mutable int m_positionStartOffset;
 181     mutable int m_positionEndOffset;
 182     int m_textLength;
 183     String m_text;
 184
 185     // Used when there is still some pending text from the current node; when these
 186     // are false and 0, we go back to normal iterating.
 187     bool m_needsAnotherNewline;
 188     InlineTextBox* m_textBox;
 189     // Used when iteration over :first-letter text to save pointer to
 190     // remaining text box.
 191     InlineTextBox* m_remainingTextBox;
 192     // Used to point to RenderText object for :first-letter.
 193     RawPtrWillBeMember<RenderText> m_firstLetterText;
 194
 195     // Used to do the whitespace collapsing logic.
 196     RawPtrWillBeMember<Text> m_lastTextNode;
 197     bool m_lastTextNodeEndedWithCollapsedSpace;
 198     UChar m_lastCharacter;
 199
 200     // Used for whitespace characters that aren't in the DOM, so we can point at them.
 201     // If non-zero, overrides m_text.
 202     UChar m_singleCharacterBuffer;
 203
 204     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
 205     Vector<InlineTextBox*> m_sortedTextBoxes;
 206     size_t m_sortedTextBoxesPosition;
 207
 208     // Used when deciding whether to emit a "positioning" (e.g. newline) before any other content
 209     bool m_hasEmitted;
 210
 211     // Used by selection preservation code.  There should be one character emitted between every VisiblePosition
 212     // in the Range used to create the TextIterator.
 213     // FIXME <rdar://problem/6028818>: This functionality should eventually be phased out when we rewrite
 214     // moveParagraphs to not clone/destroy moved content.
 215     bool m_emitsCharactersBetweenAllVisiblePositions;
 216     bool m_entersTextControls;
 217
 218     // Used in pasting inside password field.
 219     bool m_emitsOriginalText;
 220     // Used when deciding text fragment created by :first-letter should be looked into.
 221     bool m_handledFirstLetter;
 222     // Used when the visibility of the style should not affect text gathering.
 223     bool m_ignoresStyleVisibility;
 224     // Used when the iteration should stop if form controls are reached.
 225     bool m_stopsOnFormControls;
 226     // Used when m_stopsOnFormControls is set to determine if the iterator should keep advancing.
 227     bool m_shouldStop;
 228
 229     bool m_emitsImageAltText;
 230
 231     bool m_entersAuthorShadowRoots;
 232
 233     bool m_emitsObjectReplacementCharacter;
 234
 235     bool m_breaksAtReplacedElement;
 236 };
 237
 238 // Iterates through the DOM range, returning all the text, and 0-length boundaries
 239 // at points where replaced elements break up the text flow. The text comes back in
 240 // chunks so as to optimize for performance of the iteration.
 241 class SimplifiedBackwardsTextIterator {
 242     STACK_ALLOCATED();
 243 public:
 244     explicit SimplifiedBackwardsTextIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 245     SimplifiedBackwardsTextIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 246
 247     bool atEnd() const { return !m_positionNode || m_shouldStop; }
 248     void advance();
 249
 250     int length() const { return m_textLength; }
 251
 252     Node* node() const { return m_node; }
 253
 254     template<typename BufferType>
 255     void prependTextTo(BufferType& output)
 256     {
 257         if (!m_textLength)
 258             return;
 259         if (m_singleCharacterBuffer)
 260             output.prepend(&m_singleCharacterBuffer, 1);
 261         else
 262             m_textContainer.prependTo(output, m_textOffset, m_textLength);
 263     }
 264
 265     Node* startContainer() const;
 266     int endOffset() const;
 267     Position startPosition() const;
 268     Position endPosition() const;
 269
 270 private:
 271     void init(Node* startNode, Node* endNode, int startOffset, int endOffset);
 272     void exitNode();
 273     bool handleTextNode();
 274     RenderText* handleFirstLetter(int& startOffset, int& offsetInNode);
 275     bool handleReplacedElement();
 276     bool handleNonTextNode();
 277     void emitCharacter(UChar, Node*, int startOffset, int endOffset);
 278     bool advanceRespectingRange(Node*);
 279
 280     // Current position, not necessarily of the text being returned, but position
 281     // as we walk through the DOM tree.
 282     RawPtrWillBeMember<Node> m_node;
 283     int m_offset;
 284     bool m_handledNode;
 285     bool m_handledChildren;
 286     BitStack m_fullyClippedStack;
 287
 288     // End of the range.
 289     RawPtrWillBeMember<Node> m_startNode;
 290     int m_startOffset;
 291     // Start of the range.
 292     RawPtrWillBeMember<Node> m_endNode;
 293     int m_endOffset;
 294
 295     // The current text and its position, in the form to be returned from the iterator.
 296     RawPtrWillBeMember<Node> m_positionNode;
 297     int m_positionStartOffset;
 298     int m_positionEndOffset;
 299
 300     String m_textContainer; // We're interested in the range [m_textOffset, m_textOffset + m_textLength) of m_textContainer.
 301     int m_textOffset;
 302     int m_textLength;
 303
 304     // Used to do the whitespace logic.
 305     RawPtrWillBeMember<Text> m_lastTextNode;
 306     UChar m_lastCharacter;
 307
 308     // Used for whitespace characters that aren't in the DOM, so we can point at them.
 309     UChar m_singleCharacterBuffer;
 310
 311     // Whether m_node has advanced beyond the iteration range (i.e. m_startNode).
 312     bool m_havePassedStartNode;
 313
 314     // Should handle first-letter renderer in the next call to handleTextNode.
 315     bool m_shouldHandleFirstLetter;
 316
 317     // Used when the iteration should stop if form controls are reached.
 318     bool m_stopsOnFormControls;
 319
 320     // Used when m_stopsOnFormControls is set to determine if the iterator should keep advancing.
 321     bool m_shouldStop;
 322
 323     // Used in pasting inside password field.
 324     bool m_emitsOriginalText;
 325 };
 326
 327 // Builds on the text iterator, adding a character position so we can walk one
 328 // character at a time, or faster, as needed. Useful for searching.
 329 class CharacterIterator {
 330     STACK_ALLOCATED();
 331 public:
 332     explicit CharacterIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 333     CharacterIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 334
 335     void advance(int numCharacters);
 336
 337     bool atBreak() const { return m_atBreak; }
 338     bool atEnd() const { return m_textIterator.atEnd(); }
 339
 340     int length() const { return m_textIterator.length() - m_runOffset; }
 341     UChar characterAt(unsigned index) const { return m_textIterator.characterAt(m_runOffset + index); }
 342
 343     template<typename BufferType>
 344     void appendTextTo(BufferType& output) { m_textIterator.appendTextTo(output, m_runOffset); }
 345
 346     int characterOffset() const { return m_offset; }
 347     PassRefPtrWillBeRawPtr<Range> createRange() const;
 348
 349     Document* ownerDocument() const;
 350     Node* startContainer() const;
 351     Node* endContainer() const;
 352     int startOffset() const;
 353     int endOffset() const;
 354     Position startPosition() const;
 355     Position endPosition() const;
 356
 357 private:
 358     void initialize();
 359
 360     int m_offset;
 361     int m_runOffset;
 362     bool m_atBreak;
 363
 364     TextIterator m_textIterator;
 365 };
 366
 367 class BackwardsCharacterIterator {
 368     STACK_ALLOCATED();
 369 public:
 370     explicit BackwardsCharacterIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 371     BackwardsCharacterIterator(const Position&, const Position&, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 372
 373     void advance(int);
 374
 375     bool atEnd() const { return m_textIterator.atEnd(); }
 376
 377     Position endPosition() const;
 378
 379 private:
 380     int m_offset;
 381     int m_runOffset;
 382     bool m_atBreak;
 383
 384     SimplifiedBackwardsTextIterator m_textIterator;
 385 };
 386
 387 // Very similar to the TextIterator, except that the chunks of text returned are "well behaved",
 388 // meaning they never end split up a word.  This is useful for spellcheck or (perhaps one day) searching.
 389 class WordAwareIterator {
 390     STACK_ALLOCATED();
 391 public:
 392     explicit WordAwareIterator(const Position& start, const Position& end);
 393     ~WordAwareIterator();
 394
 395     bool atEnd() const { return !m_didLookAhead && m_textIterator.atEnd(); }
 396     void advance();
 397
 398     String substring(unsigned position, unsigned length) const;
 399     UChar characterAt(unsigned index) const;
 400     int length() const;
 401
 402 private:
 403     Vector<UChar> m_buffer;
 404     // Did we have to look ahead in the textIterator to confirm the current chunk?
 405     bool m_didLookAhead;
 406     TextIterator m_textIterator;
 407 };
 408
 409 }
 410
 411 #endif