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