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 WebCore {
  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 };
  51 typedef unsigned TextIteratorBehaviorFlags;
  52
  53 String plainText(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  54 PassRefPtrWillBeRawPtr<Range> findPlainText(const Range*, const String&, FindOptions);
  55 void findPlainText(const Position& inputStart, const Position& inputEnd, const String&, FindOptions, Position& resultStart, Position& resultEnd);
  56
  57 class BitStack {
  58 public:
  59     BitStack();
  60     ~BitStack();
  61
  62     void push(bool);
  63     void pop();
  64
  65     bool top() const;
  66     unsigned size() const;
  67
  68 private:
  69     unsigned m_size;
  70     Vector<unsigned, 1> m_words;
  71 };
  72
  73 // Iterates through the DOM range, returning all the text, and 0-length boundaries
  74 // at points where replaced elements break up the text flow.  The text comes back in
  75 // chunks so as to optimize for performance of the iteration.
  76
  77 class TextIterator {
  78     STACK_ALLOCATED();
  79 public:
  80     explicit TextIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  81     // [start, end] indicates the document range that the iteration should take place within (both ends inclusive).
  82     TextIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
  83     ~TextIterator();
  84
  85     bool atEnd() const { return !m_positionNode || m_shouldStop; }
  86     void advance();
  87
  88     int length() const { return m_textLength; }
  89     UChar characterAt(unsigned index) const;
  90     String substring(unsigned position, unsigned length) const;
  91     void appendTextToStringBuilder(StringBuilder&, unsigned position = 0, unsigned maxLength = UINT_MAX) const;
  92
  93     template<typename BufferType>
  94     void appendTextTo(BufferType& output, unsigned position = 0)
  95     {
  96         ASSERT_WITH_SECURITY_IMPLICATION(position <= static_cast<unsigned>(length()));
  97         unsigned lengthToAppend = length() - position;
  98         if (!lengthToAppend)
  99             return;
 100         if (m_singleCharacterBuffer) {
 101             ASSERT(!position);
 102             ASSERT(length() == 1);
 103             output.append(&m_singleCharacterBuffer, 1);
 104         } else {
 105             string().appendTo(output, startOffset() + position, lengthToAppend);
 106         }
 107     }
 108
 109     PassRefPtrWillBeRawPtr<Range> range() const;
 110     Node* node() const;
 111
 112     static int rangeLength(const Range*, bool spacesForReplacedElements = false);
 113     static PassRefPtrWillBeRawPtr<Range> subrange(Range* entireRange, int characterOffset, int characterCount);
 114
 115 private:
 116     enum IterationProgress {
 117         HandledNone,
 118         HandledAuthorShadowRoots,
 119         HandledUserAgentShadowRoot,
 120         HandledNode,
 121         HandledChildren
 122     };
 123
 124     void initialize(const Position& start, const Position& end);
 125
 126     int startOffset() const { return m_positionStartOffset; }
 127     const String& string() const { return m_text; }
 128     void exitNode();
 129     bool shouldRepresentNodeOffsetZero();
 130     bool shouldEmitSpaceBeforeAndAfterNode(Node*);
 131     void representNodeOffsetZero();
 132     bool handleTextNode();
 133     bool handleReplacedElement();
 134     bool handleNonTextNode();
 135     void handleTextBox();
 136     void handleTextNodeFirstLetter(RenderTextFragment*);
 137     bool hasVisibleTextNode(RenderText*);
 138     void emitCharacter(UChar, Node* textNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset);
 139     void emitText(Node* textNode, RenderObject* renderObject, int textStartOffset, int textEndOffset);
 140     void emitText(Node* textNode, int textStartOffset, int textEndOffset);
 141
 142     // Current position, not necessarily of the text being returned, but position
 143     // as we walk through the DOM tree.
 144     RawPtrWillBeMember<Node> m_node;
 145     int m_offset;
 146     IterationProgress m_iterationProgress;
 147     BitStack m_fullyClippedStack;
 148     int m_shadowDepth;
 149
 150     // The range.
 151     RawPtrWillBeMember<Node> m_startContainer;
 152     int m_startOffset;
 153     RawPtrWillBeMember<Node> m_endContainer;
 154     int m_endOffset;
 155     RawPtrWillBeMember<Node> m_pastEndNode;
 156
 157     // The current text and its position, in the form to be returned from the iterator.
 158     RawPtrWillBeMember<Node> m_positionNode;
 159     mutable RawPtrWillBeMember<Node> m_positionOffsetBaseNode;
 160     mutable int m_positionStartOffset;
 161     mutable int m_positionEndOffset;
 162     int m_textLength;
 163     String m_text;
 164
 165     // Used when there is still some pending text from the current node; when these
 166     // are false and 0, we go back to normal iterating.
 167     bool m_needsAnotherNewline;
 168     InlineTextBox* m_textBox;
 169     // Used when iteration over :first-letter text to save pointer to
 170     // remaining text box.
 171     InlineTextBox* m_remainingTextBox;
 172     // Used to point to RenderText object for :first-letter.
 173     RenderText *m_firstLetterText;
 174
 175     // Used to do the whitespace collapsing logic.
 176     RawPtrWillBeMember<Node> m_lastTextNode;
 177     bool m_lastTextNodeEndedWithCollapsedSpace;
 178     UChar m_lastCharacter;
 179
 180     // Used for whitespace characters that aren't in the DOM, so we can point at them.
 181     // If non-zero, overrides m_text.
 182     UChar m_singleCharacterBuffer;
 183
 184     // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)
 185     Vector<InlineTextBox*> m_sortedTextBoxes;
 186     size_t m_sortedTextBoxesPosition;
 187
 188     // Used when deciding whether to emit a "positioning" (e.g. newline) before any other content
 189     bool m_hasEmitted;
 190
 191     // Used by selection preservation code.  There should be one character emitted between every VisiblePosition
 192     // in the Range used to create the TextIterator.
 193     // FIXME <rdar://problem/6028818>: This functionality should eventually be phased out when we rewrite
 194     // moveParagraphs to not clone/destroy moved content.
 195     bool m_emitsCharactersBetweenAllVisiblePositions;
 196     bool m_entersTextControls;
 197
 198     // Used in pasting inside password field.
 199     bool m_emitsOriginalText;
 200     // Used when deciding text fragment created by :first-letter should be looked into.
 201     bool m_handledFirstLetter;
 202     // Used when the visibility of the style should not affect text gathering.
 203     bool m_ignoresStyleVisibility;
 204     // Used when the iteration should stop if form controls are reached.
 205     bool m_stopsOnFormControls;
 206     // Used when m_stopsOnFormControls is set to determine if the iterator should keep advancing.
 207     bool m_shouldStop;
 208
 209     bool m_emitsImageAltText;
 210
 211     bool m_entersAuthorShadowRoots;
 212
 213     bool m_emitsObjectReplacementCharacter;
 214 };
 215
 216 // Iterates through the DOM range, returning all the text, and 0-length boundaries
 217 // at points where replaced elements break up the text flow. The text comes back in
 218 // chunks so as to optimize for performance of the iteration.
 219 class SimplifiedBackwardsTextIterator {
 220     STACK_ALLOCATED();
 221 public:
 222     explicit SimplifiedBackwardsTextIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 223
 224     bool atEnd() const { return !m_positionNode || m_shouldStop; }
 225     void advance();
 226
 227     int length() const { return m_textLength; }
 228
 229     Node* node() const { return m_node; }
 230
 231     template<typename BufferType>
 232     void prependTextTo(BufferType& output)
 233     {
 234         if (!m_textLength)
 235             return;
 236         if (m_singleCharacterBuffer)
 237             output.prepend(&m_singleCharacterBuffer, 1);
 238         else
 239             m_textContainer.prependTo(output, m_textOffset, m_textLength);
 240     }
 241
 242     PassRefPtrWillBeRawPtr<Range> range() const;
 243
 244 private:
 245     void exitNode();
 246     bool handleTextNode();
 247     RenderText* handleFirstLetter(int& startOffset, int& offsetInNode);
 248     bool handleReplacedElement();
 249     bool handleNonTextNode();
 250     void emitCharacter(UChar, Node*, int startOffset, int endOffset);
 251     bool advanceRespectingRange(Node*);
 252
 253     // Current position, not necessarily of the text being returned, but position
 254     // as we walk through the DOM tree.
 255     RawPtrWillBeMember<Node> m_node;
 256     int m_offset;
 257     bool m_handledNode;
 258     bool m_handledChildren;
 259     BitStack m_fullyClippedStack;
 260
 261     // End of the range.
 262     RawPtrWillBeMember<Node> m_startNode;
 263     int m_startOffset;
 264     // Start of the range.
 265     RawPtrWillBeMember<Node> m_endNode;
 266     int m_endOffset;
 267
 268     // The current text and its position, in the form to be returned from the iterator.
 269     RawPtrWillBeMember<Node> m_positionNode;
 270     int m_positionStartOffset;
 271     int m_positionEndOffset;
 272
 273     String m_textContainer; // We're interested in the range [m_textOffset, m_textOffset + m_textLength) of m_textContainer.
 274     int m_textOffset;
 275     int m_textLength;
 276
 277     // Used to do the whitespace logic.
 278     RawPtrWillBeMember<Node> m_lastTextNode;
 279     UChar m_lastCharacter;
 280
 281     // Used for whitespace characters that aren't in the DOM, so we can point at them.
 282     UChar m_singleCharacterBuffer;
 283
 284     // Whether m_node has advanced beyond the iteration range (i.e. m_startNode).
 285     bool m_havePassedStartNode;
 286
 287     // Should handle first-letter renderer in the next call to handleTextNode.
 288     bool m_shouldHandleFirstLetter;
 289
 290     // Used when the iteration should stop if form controls are reached.
 291     bool m_stopsOnFormControls;
 292
 293     // Used when m_stopsOnFormControls is set to determine if the iterator should keep advancing.
 294     bool m_shouldStop;
 295
 296     // Used in pasting inside password field.
 297     bool m_emitsOriginalText;
 298 };
 299
 300 // Builds on the text iterator, adding a character position so we can walk one
 301 // character at a time, or faster, as needed. Useful for searching.
 302 class CharacterIterator {
 303     STACK_ALLOCATED();
 304 public:
 305     explicit CharacterIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 306     CharacterIterator(const Position& start, const Position& end, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 307
 308     void advance(int numCharacters);
 309
 310     bool atBreak() const { return m_atBreak; }
 311     bool atEnd() const { return m_textIterator.atEnd(); }
 312
 313     int length() const { return m_textIterator.length() - m_runOffset; }
 314     UChar characterAt(unsigned index) const { return m_textIterator.characterAt(m_runOffset + index); }
 315
 316     template<typename BufferType>
 317     void appendTextTo(BufferType& output) { m_textIterator.appendTextTo(output, m_runOffset); }
 318
 319     int characterOffset() const { return m_offset; }
 320     PassRefPtrWillBeRawPtr<Range> range() const;
 321
 322 private:
 323     void initialize();
 324
 325     int m_offset;
 326     int m_runOffset;
 327     bool m_atBreak;
 328
 329     TextIterator m_textIterator;
 330 };
 331
 332 class BackwardsCharacterIterator {
 333     STACK_ALLOCATED();
 334 public:
 335     explicit BackwardsCharacterIterator(const Range*, TextIteratorBehaviorFlags = TextIteratorDefaultBehavior);
 336
 337     void advance(int);
 338
 339     bool atEnd() const { return m_textIterator.atEnd(); }
 340
 341     PassRefPtrWillBeRawPtr<Range> range() const;
 342
 343 private:
 344     int m_offset;
 345     int m_runOffset;
 346     bool m_atBreak;
 347
 348     SimplifiedBackwardsTextIterator m_textIterator;
 349 };
 350
 351 // Very similar to the TextIterator, except that the chunks of text returned are "well behaved",
 352 // meaning they never end split up a word.  This is useful for spellcheck or (perhaps one day) searching.
 353 class WordAwareIterator {
 354     STACK_ALLOCATED();
 355 public:
 356     explicit WordAwareIterator(const Range*);
 357     ~WordAwareIterator();
 358
 359     bool atEnd() const { return !m_didLookAhead && m_textIterator.atEnd(); }
 360     void advance();
 361
 362     String substring(unsigned position, unsigned length) const;
 363     UChar characterAt(unsigned index) const;
 364     int length() const;
 365
 366 private:
 367     Vector<UChar> m_buffer;
 368     // Did we have to look ahead in the textIterator to confirm the current chunk?
 369     bool m_didLookAhead;
 370     RefPtrWillBeMember<Range> m_range;
 371     TextIterator m_textIterator;
 372 };
 373
 374 }
 375
 376 #endif