a5d0ea12abafa22584b9a8eb0734434f25ce44bc
[WebKit-https.git] / Source / WebCore / editing / TextIterator.h
1 /*
2  * Copyright (C) 2004-2020 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 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 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 #pragma once
27
28 #include "FindOptions.h"
29 #include "LineLayoutTraversal.h"
30 #include "SimpleRange.h"
31 #include "TextIteratorBehavior.h"
32 #include <wtf/Vector.h>
33 #include <wtf/text/StringView.h>
34
35 namespace WebCore {
36
37 class Range;
38 class RenderText;
39 class RenderTextFragment;
40
41 WEBCORE_EXPORT String plainText(Position start, Position end, TextIteratorBehavior = TextIteratorDefaultBehavior, bool isDisplayString = false);
42 WEBCORE_EXPORT String plainTextReplacingNoBreakSpace(Position start, Position end, TextIteratorBehavior = TextIteratorDefaultBehavior, bool isDisplayString = false);
43
44 WEBCORE_EXPORT String plainText(const Range*, TextIteratorBehavior = TextIteratorDefaultBehavior, bool isDisplayString = false);
45 WEBCORE_EXPORT String plainTextReplacingNoBreakSpace(const Range*, TextIteratorBehavior = TextIteratorDefaultBehavior, bool isDisplayString = false);
46 WEBCORE_EXPORT String plainTextUsingBackwardsTextIteratorForTesting(const SimpleRange&);
47
48 SimpleRange findPlainText(const SimpleRange&, const String&, FindOptions);
49 WEBCORE_EXPORT SimpleRange findClosestPlainText(const SimpleRange&, const String&, FindOptions, unsigned);
50 WEBCORE_EXPORT bool hasAnyPlainText(const SimpleRange&, TextIteratorBehavior = TextIteratorDefaultBehavior);
51 bool containsPlainText(const String& document, const String&, FindOptions); // Lets us use the search algorithm on a string.
52 WEBCORE_EXPORT String foldQuoteMarks(const String&);
53
54 // FIXME: Move this somewhere else in the editing directory. It doesn't belong here.
55 bool isRendererReplacedElement(RenderObject*);
56
57 // FIXME: Move each iterator class into a separate header file.
58
59 class BitStack {
60 public:
61     void push(bool);
62     void pop();
63     bool top() const;
64
65 private:
66     unsigned m_size { 0 };
67     Vector<unsigned, 1> m_words;
68 };
69
70 class TextIteratorCopyableText {
71 public:
72     StringView text() const { return m_singleCharacter ? StringView(&m_singleCharacter, 1) : StringView(m_string).substring(m_offset, m_length); }
73     void appendToStringBuilder(StringBuilder&) const;
74
75     void reset();
76     void set(String&&);
77     void set(String&&, unsigned offset, unsigned length);
78     void set(UChar);
79
80 private:
81     UChar m_singleCharacter { 0 };
82     String m_string;
83     unsigned m_offset { 0 };
84     unsigned m_length { 0 };
85 };
86
87 // Iterates through the DOM range, returning all the text, and 0-length boundaries
88 // at points where replaced elements break up the text flow. The text is delivered in
89 // the chunks it's already stored in, to avoid copying any text.
90
91 class TextIterator {
92     WTF_MAKE_FAST_ALLOCATED;
93 public:
94     WEBCORE_EXPORT TextIterator(Position start, Position end, TextIteratorBehavior = TextIteratorDefaultBehavior);
95     WEBCORE_EXPORT explicit TextIterator(const Range*, TextIteratorBehavior = TextIteratorDefaultBehavior);
96     WEBCORE_EXPORT ~TextIterator();
97
98     bool atEnd() const { return !m_positionNode; }
99     WEBCORE_EXPORT void advance();
100
101     StringView text() const { ASSERT(!atEnd()); return m_text; }
102     WEBCORE_EXPORT SimpleRange range() const;
103     WEBCORE_EXPORT Node* node() const;
104
105     const TextIteratorCopyableText& copyableText() const { ASSERT(!atEnd()); return m_copyableText; }
106     void appendTextToStringBuilder(StringBuilder& builder) const { copyableText().appendToStringBuilder(builder); }
107
108     WEBCORE_EXPORT static int rangeLength(const Range*, bool spacesForReplacedElements = false);
109     WEBCORE_EXPORT static RefPtr<Range> rangeFromLocationAndLength(ContainerNode* scope, int rangeLocation, int rangeLength, bool spacesForReplacedElements = false);
110     WEBCORE_EXPORT static bool getLocationAndLengthFromRange(Node* scope, const Range*, size_t& location, size_t& length);
111     WEBCORE_EXPORT static Ref<Range> subrange(Range& entireRange, int characterOffset, int characterCount);
112
113 private:
114     void init();
115     void exitNode(Node*);
116     bool shouldRepresentNodeOffsetZero();
117     bool shouldEmitSpaceBeforeAndAfterNode(Node&);
118     void representNodeOffsetZero();
119     bool handleTextNode();
120     bool handleReplacedElement();
121     bool handleNonTextNode();
122     void handleTextBox();
123     void handleTextNodeFirstLetter(RenderTextFragment&);
124     void emitCharacter(UChar, Node& characterNode, Node* offsetBaseNode, int textStartOffset, int textEndOffset);
125     void emitText(Text& textNode, RenderText&, int textStartOffset, int textEndOffset);
126
127     Node* baseNodeForEmittingNewLine() const;
128
129     const TextIteratorBehavior m_behavior { TextIteratorDefaultBehavior };
130
131     // Current position, not necessarily of the text being returned, but position as we walk through the DOM tree.
132     Node* m_node { nullptr };
133     int m_offset { 0 };
134     bool m_handledNode { false };
135     bool m_handledChildren { false };
136     BitStack m_fullyClippedStack;
137
138     // The range.
139     Node* m_startContainer { nullptr };
140     int m_startOffset { 0 };
141     Node* m_endContainer { nullptr };
142     int m_endOffset { 0 };
143     Node* m_pastEndNode { nullptr };
144
145     // The current text and its position, in the form to be returned from the iterator.
146     Node* m_positionNode { nullptr };
147     mutable Node* m_positionOffsetBaseNode { nullptr };
148     mutable int m_positionStartOffset { 0 };
149     mutable int m_positionEndOffset { 0 };
150     TextIteratorCopyableText m_copyableText;
151     StringView m_text;
152
153     // Used when there is still some pending text from the current node; when these are false and null, we go back to normal iterating.
154     Node* m_nodeForAdditionalNewline { nullptr };
155     LineLayoutTraversal::TextBoxIterator m_textBox;
156
157     // Used when iterating over :first-letter text to save pointer to remaining text box.
158     LineLayoutTraversal::TextBoxIterator m_remainingTextBox;
159
160     // Used to point to RenderText object for :first-letter.
161     RenderText* m_firstLetterText { nullptr };
162
163     // Used to do the whitespace collapsing logic.
164     Text* m_lastTextNode { nullptr };
165     bool m_lastTextNodeEndedWithCollapsedSpace { false };
166     UChar m_lastCharacter { 0 };
167
168     // Used when deciding whether to emit a "positioning" (e.g. newline) before any other content
169     bool m_hasEmitted { false };
170
171     // Used when deciding text fragment created by :first-letter should be looked into.
172     bool m_handledFirstLetter { false };
173 };
174
175 // Iterates through the DOM range, returning all the text, and 0-length boundaries
176 // at points where replaced elements break up the text flow. The text comes back in
177 // chunks so as to optimize for performance of the iteration.
178 class SimplifiedBackwardsTextIterator {
179 public:
180     explicit SimplifiedBackwardsTextIterator(const Range&);
181
182     bool atEnd() const { return !m_positionNode; }
183     void advance();
184
185     StringView text() const { ASSERT(!atEnd()); return m_text; }
186     WEBCORE_EXPORT SimpleRange range() const;
187     Node* node() const { ASSERT(!atEnd()); return m_node; }
188
189 private:
190     void exitNode();
191     bool handleTextNode();
192     RenderText* handleFirstLetter(int& startOffset, int& offsetInNode);
193     bool handleReplacedElement();
194     bool handleNonTextNode();
195     void emitCharacter(UChar, Node&, int startOffset, int endOffset);
196     bool advanceRespectingRange(Node*);
197
198     const TextIteratorBehavior m_behavior { TextIteratorDefaultBehavior };
199
200     // Current position, not necessarily of the text being returned, but position as we walk through the DOM tree.
201     Node* m_node { nullptr };
202     int m_offset { 0 };
203     bool m_handledNode { false };
204     bool m_handledChildren { false };
205     BitStack m_fullyClippedStack;
206
207     // The range.
208     Node* m_startContainer { nullptr };
209     int m_startOffset { 0 };
210     Node* m_endContainer { nullptr };
211     int m_endOffset { 0 };
212     
213     // The current text and its position, in the form to be returned from the iterator.
214     Node* m_positionNode { nullptr };
215     int m_positionStartOffset { 0 };
216     int m_positionEndOffset { 0 };
217     TextIteratorCopyableText m_copyableText;
218     StringView m_text;
219
220     // Used to do the whitespace logic.
221     Text* m_lastTextNode { nullptr };
222     UChar m_lastCharacter { 0 };
223
224     // Whether m_node has advanced beyond the iteration range (i.e. m_startContainer).
225     bool m_havePassedStartContainer { false };
226
227     // Should handle first-letter renderer in the next call to handleTextNode.
228     bool m_shouldHandleFirstLetter { false };
229 };
230
231 // Builds on the text iterator, adding a character position so we can walk one
232 // character at a time, or faster, as needed. Useful for searching.
233 class CharacterIterator {
234 public:
235     WEBCORE_EXPORT explicit CharacterIterator(const Range&, TextIteratorBehavior = TextIteratorDefaultBehavior);
236     WEBCORE_EXPORT explicit CharacterIterator(Position start, Position end, TextIteratorBehavior = TextIteratorDefaultBehavior);
237     
238     bool atEnd() const { return m_underlyingIterator.atEnd(); }
239     WEBCORE_EXPORT void advance(int numCharacters);
240     
241     StringView text() const { return m_underlyingIterator.text().substring(m_runOffset); }
242     WEBCORE_EXPORT SimpleRange range() const;
243
244     bool atBreak() const { return m_atBreak; }
245     unsigned characterOffset() const { return m_offset; }
246
247 private:
248     TextIterator m_underlyingIterator;
249
250     unsigned m_offset { 0 };
251     unsigned m_runOffset { 0 };
252     bool m_atBreak { true };
253 };
254     
255 class BackwardsCharacterIterator {
256 public:
257     explicit BackwardsCharacterIterator(const Range&);
258
259     bool atEnd() const { return m_underlyingIterator.atEnd(); }
260     void advance(int numCharacters);
261
262     SimpleRange range() const;
263
264 private:
265     SimplifiedBackwardsTextIterator m_underlyingIterator;
266
267     unsigned m_offset { 0 };
268     unsigned m_runOffset { 0 };
269     bool m_atBreak { true };
270 };
271
272 // Similar to the TextIterator, except that the chunks of text returned are "well behaved", meaning
273 // they never split up a word. This is useful for spell checking and perhaps one day for searching as well.
274 class WordAwareIterator {
275 public:
276     explicit WordAwareIterator(const Range&);
277
278     bool atEnd() const { return !m_didLookAhead && m_underlyingIterator.atEnd(); }
279     void advance();
280
281     StringView text() const;
282
283 private:
284     TextIterator m_underlyingIterator;
285
286     // Text from the previous chunk from the text iterator.
287     TextIteratorCopyableText m_previousText;
288
289     // Many chunks from text iterator concatenated.
290     Vector<UChar> m_buffer;
291
292     // Did we have to look ahead in the text iterator to confirm the current chunk?
293     bool m_didLookAhead { true };
294 };
295
296 } // namespace WebCore