Unreviewed, silence "enumeral and non-enumeral type in conditional expression" warning
[WebKit-https.git] / Source / WebCore / rendering / InlineIterator.h
1 /*
2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3  * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009, 2010 Apple Inc. All right reserved.
4  * Copyright (C) 2010 Google Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22
23 #pragma once
24
25 #include "BidiRun.h"
26 #include "RenderBlockFlow.h"
27 #include "RenderChildIterator.h"
28 #include "RenderInline.h"
29 #include "RenderText.h"
30 #include <wtf/StdLibExtras.h>
31
32 namespace WebCore {
33
34 struct BidiIsolatedRun {
35     BidiIsolatedRun(RenderObject& object, unsigned position, RenderElement& root, BidiRun& runToReplace)
36         : object(object)
37         , root(root)
38         , runToReplace(runToReplace)
39         , position(position)
40     {
41     }
42
43     RenderObject& object;
44     RenderElement& root;
45     BidiRun& runToReplace;
46     unsigned position;
47 };
48
49 // This class is used to RenderInline subtrees, stepping by character within the
50 // text children. InlineIterator will use bidiNext to find the next RenderText
51 // optionally notifying a BidiResolver every time it steps into/out of a RenderInline.
52 class InlineIterator {
53 public:
54     InlineIterator()
55     {
56     }
57
58     InlineIterator(RenderElement* root, RenderObject* o, unsigned p)
59         : m_root(root)
60         , m_renderer(o)
61         , m_pos(p)
62         , m_refersToEndOfPreviousNode(false)
63     {
64     }
65
66     void clear()
67     {
68         setRenderer(nullptr);
69         setOffset(0);
70         setNextBreakablePosition(std::numeric_limits<unsigned>::max());
71     }
72     void moveToStartOf(RenderObject& object)
73     {
74         moveTo(object, 0);
75     }
76
77     void moveTo(RenderObject& object, unsigned offset, std::optional<unsigned> nextBreak = std::optional<unsigned>())
78     {
79         setRenderer(&object);
80         setOffset(offset);
81         setNextBreakablePosition(nextBreak);
82     }
83
84     RenderObject* renderer() const { return m_renderer; }
85     void setRenderer(RenderObject* renderer) { m_renderer = renderer; }
86     unsigned offset() const { return m_pos; }
87     void setOffset(unsigned position);
88     RenderElement* root() const { return m_root; }
89     std::optional<unsigned> nextBreakablePosition() const { return m_nextBreakablePosition; }
90     void setNextBreakablePosition(std::optional<unsigned> position) { m_nextBreakablePosition = position; }
91     bool refersToEndOfPreviousNode() const { return m_refersToEndOfPreviousNode; }
92     void setRefersToEndOfPreviousNode();
93
94     void fastIncrementInTextNode();
95     void increment(InlineBidiResolver* = nullptr);
96     void fastDecrement();
97     bool atEnd() const;
98
99     bool atTextParagraphSeparator() const
100     {
101         return is<RenderText>(m_renderer) && m_renderer->preservesNewline() && downcast<RenderText>(*m_renderer).characterAt(m_pos) == '\n';
102     }
103     
104     bool atParagraphSeparator() const
105     {
106         return (m_renderer && m_renderer->isBR()) || atTextParagraphSeparator();
107     }
108
109     UChar current() const;
110     UChar previousInSameNode() const;
111     ALWAYS_INLINE UCharDirection direction() const;
112
113 private:
114     UChar characterAt(unsigned) const;
115
116     UCharDirection surrogateTextDirection(UChar currentCodeUnit) const;
117
118     RenderElement* m_root { nullptr };
119     RenderObject* m_renderer { nullptr };
120
121     std::optional<unsigned> m_nextBreakablePosition;
122     unsigned m_pos { 0 };
123
124     // There are a couple places where we want to decrement an InlineIterator.
125     // Usually this take the form of decrementing m_pos; however, m_pos might be 0.
126     // However, we shouldn't ever need to decrement an InlineIterator more than
127     // once, so rather than implementing a decrement() function which traverses
128     // nodes, we can simply keep track of this state and handle it.
129     bool m_refersToEndOfPreviousNode { false };
130 };
131
132 inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
133 {
134     return it1.offset() == it2.offset() && it1.renderer() == it2.renderer();
135 }
136
137 inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
138 {
139     return it1.offset() != it2.offset() || it1.renderer() != it2.renderer();
140 }
141
142 static inline UCharDirection embedCharFromDirection(TextDirection direction, EUnicodeBidi unicodeBidi)
143 {
144     if (unicodeBidi == Embed)
145         return direction == RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING;
146     return direction == RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE;
147 }
148
149 template <class Observer>
150 static inline void notifyObserverEnteredObject(Observer* observer, RenderObject* object)
151 {
152     if (!observer || !object || !object->isRenderInline())
153         return;
154
155     const RenderStyle& style = object->style();
156     EUnicodeBidi unicodeBidi = style.unicodeBidi();
157     if (unicodeBidi == UBNormal) {
158         // http://dev.w3.org/csswg/css3-writing-modes/#unicode-bidi
159         // "The element does not open an additional level of embedding with respect to the bidirectional algorithm."
160         // Thus we ignore any possible dir= attribute on the span.
161         return;
162     }
163     if (isIsolated(unicodeBidi)) {
164         // Make sure that explicit embeddings are committed before we enter the isolated content.
165         observer->commitExplicitEmbedding();
166         observer->enterIsolate();
167         // Embedding/Override characters implied by dir= will be handled when
168         // we process the isolated span, not when laying out the "parent" run.
169         return;
170     }
171
172     if (!observer->inIsolate())
173         observer->embed(embedCharFromDirection(style.direction(), unicodeBidi), FromStyleOrDOM);
174 }
175
176 template <class Observer>
177 static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
178 {
179     if (!observer || !object || !object->isRenderInline())
180         return;
181
182     EUnicodeBidi unicodeBidi = object->style().unicodeBidi();
183     if (unicodeBidi == UBNormal)
184         return; // Nothing to do for unicode-bidi: normal
185     if (isIsolated(unicodeBidi)) {
186         observer->exitIsolate();
187         return;
188     }
189
190     // Otherwise we pop any embed/override character we added when we opened this tag.
191     if (!observer->inIsolate())
192         observer->embed(U_POP_DIRECTIONAL_FORMAT, FromStyleOrDOM);
193 }
194
195 static inline bool isIteratorTarget(RenderObject* object)
196 {
197     ASSERT(object); // The iterator will of course return 0, but its not an expected argument to this function.
198     return object->isTextOrLineBreak() || object->isFloating() || object->isOutOfFlowPositioned() || object->isReplaced();
199 }
200
201 // This enum is only used for bidiNextShared()
202 enum EmptyInlineBehavior {
203     SkipEmptyInlines,
204     IncludeEmptyInlines,
205 };
206
207 static bool isEmptyInline(const RenderInline& renderer)
208 {
209     for (auto& current : childrenOfType<RenderObject>(renderer)) {
210         if (current.isFloatingOrOutOfFlowPositioned())
211             continue;
212         if (is<RenderText>(current)) {
213             if (!downcast<RenderText>(current).isAllCollapsibleWhitespace())
214                 return false;
215             continue;
216         }
217         if (!is<RenderInline>(current) || !isEmptyInline(downcast<RenderInline>(current)))
218             return false;
219     }
220     return true;
221 }
222
223 // FIXME: This function is misleadingly named. It has little to do with bidi.
224 // This function will iterate over inlines within a block, optionally notifying
225 // a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels).
226 template <class Observer>
227 static inline RenderObject* bidiNextShared(RenderElement& root, RenderObject* current, Observer* observer = nullptr, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = nullptr)
228 {
229     RenderObject* next = nullptr;
230     // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline.
231     bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
232     bool endOfInline = false;
233
234     while (current) {
235         next = nullptr;
236         if (!oldEndOfInline && !isIteratorTarget(current)) {
237             next = downcast<RenderElement>(*current).firstChild();
238             notifyObserverEnteredObject(observer, next);
239         }
240
241         // We hit this when either current has no children, or when current is not a renderer we care about.
242         if (!next) {
243             // If it is a renderer we care about, and we're doing our inline-walk, return it.
244             if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && is<RenderInline>(*current)) {
245                 next = current;
246                 endOfInline = true;
247                 break;
248             }
249
250             while (current && current != &root) {
251                 notifyObserverWillExitObject(observer, current);
252
253                 next = current->nextSibling();
254                 if (next) {
255                     notifyObserverEnteredObject(observer, next);
256                     break;
257                 }
258
259                 current = current->parent();
260                 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != &root && is<RenderInline>(*current)) {
261                     next = current;
262                     endOfInline = true;
263                     break;
264                 }
265             }
266         }
267
268         if (!next)
269             break;
270
271         if (isIteratorTarget(next)
272             || (is<RenderInline>(*next) && (emptyInlineBehavior == IncludeEmptyInlines || isEmptyInline(downcast<RenderInline>(*next)))))
273             break;
274         current = next;
275     }
276
277     if (endOfInlinePtr)
278         *endOfInlinePtr = endOfInline;
279
280     return next;
281 }
282
283 template <class Observer>
284 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current, Observer* observer)
285 {
286     // The SkipEmptyInlines callers never care about endOfInlinePtr.
287     return bidiNextShared(root, current, observer, SkipEmptyInlines);
288 }
289
290 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
291 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current)
292 {
293     InlineBidiResolver* observer = nullptr;
294     return bidiNextSkippingEmptyInlines(root, current, observer);
295 }
296
297 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderElement& root, RenderObject* current, bool* endOfInlinePtr = nullptr)
298 {
299     InlineBidiResolver* observer = nullptr; // Callers who include empty inlines, never use an observer.
300     return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
301 }
302
303 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderElement& root, InlineBidiResolver* resolver = nullptr)
304 {
305     RenderObject* renderer = root.firstChild();
306     if (!renderer)
307         return nullptr;
308
309     if (is<RenderInline>(*renderer)) {
310         notifyObserverEnteredObject(resolver, renderer);
311         if (!isEmptyInline(downcast<RenderInline>(*renderer)))
312             renderer = bidiNextSkippingEmptyInlines(root, renderer, resolver);
313         else {
314             // Never skip empty inlines.
315             if (resolver)
316                 resolver->commitExplicitEmbedding();
317             return renderer;
318         }
319     }
320
321     // FIXME: Unify this with the bidiNext call above.
322     if (renderer && !isIteratorTarget(renderer))
323         renderer = bidiNextSkippingEmptyInlines(root, renderer, resolver);
324
325     if (resolver)
326         resolver->commitExplicitEmbedding();
327     return renderer;
328 }
329
330 // FIXME: This method needs to be renamed when bidiNext finds a good name.
331 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderElement& root)
332 {
333     RenderObject* o = root.firstChild();
334     // If either there are no children to walk, or the first one is correct
335     // then just return it.
336     if (!o || o->isRenderInline() || isIteratorTarget(o))
337         return o;
338
339     return bidiNextIncludingEmptyInlines(root, o);
340 }
341
342 inline void InlineIterator::fastIncrementInTextNode()
343 {
344     ASSERT(m_renderer);
345     ASSERT(m_pos <= downcast<RenderText>(*m_renderer).text().length());
346     ++m_pos;
347 }
348
349 inline void InlineIterator::setOffset(unsigned position)
350 {
351     ASSERT(position <= UINT_MAX - 10); // Sanity check
352     m_pos = position;
353 }
354
355 inline void InlineIterator::setRefersToEndOfPreviousNode()
356 {
357     ASSERT(!m_pos);
358     ASSERT(!m_refersToEndOfPreviousNode);
359     m_refersToEndOfPreviousNode = true;
360 }
361
362 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
363 // it shouldn't use functions called bidiFirst and bidiNext.
364 class InlineWalker {
365 public:
366     InlineWalker(RenderElement& root)
367         : m_root(root)
368         , m_current(nullptr)
369         , m_atEndOfInline(false)
370     {
371         // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
372         m_current = bidiFirstIncludingEmptyInlines(m_root);
373     }
374
375     RenderElement& root() { return m_root; }
376     RenderObject* current() { return m_current; }
377
378     bool atEndOfInline() { return m_atEndOfInline; }
379     bool atEnd() const { return !m_current; }
380
381     RenderObject* advance()
382     {
383         // FIXME: Support SkipEmptyInlines and observer parameters.
384         m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
385         return m_current;
386     }
387 private:
388     RenderElement& m_root;
389     RenderObject* m_current;
390     bool m_atEndOfInline;
391 };
392
393 inline void InlineIterator::increment(InlineBidiResolver* resolver)
394 {
395     if (!m_renderer)
396         return;
397     if (is<RenderText>(*m_renderer)) {
398         fastIncrementInTextNode();
399         if (m_pos < downcast<RenderText>(*m_renderer).text().length())
400             return;
401     }
402     // bidiNext can return nullptr
403     RenderObject* bidiNext = bidiNextSkippingEmptyInlines(*m_root, m_renderer, resolver);
404     if (bidiNext)
405         moveToStartOf(*bidiNext);
406     else
407         clear();
408 }
409
410 inline void InlineIterator::fastDecrement()
411 {
412     ASSERT(!refersToEndOfPreviousNode());
413     if (m_pos)
414         setOffset(m_pos - 1);
415     else
416         setRefersToEndOfPreviousNode();
417 }
418
419 inline bool InlineIterator::atEnd() const
420 {
421     return !m_renderer;
422 }
423
424 inline UChar InlineIterator::characterAt(unsigned index) const
425 {
426     if (!is<RenderText>(m_renderer))
427         return 0;
428
429     return downcast<RenderText>(*m_renderer).characterAt(index);
430 }
431
432 inline UChar InlineIterator::current() const
433 {
434     return characterAt(m_pos);
435 }
436
437 inline UChar InlineIterator::previousInSameNode() const
438 {
439     return characterAt(m_pos - 1);
440 }
441
442 ALWAYS_INLINE UCharDirection InlineIterator::direction() const
443 {
444     if (UNLIKELY(!m_renderer))
445         return U_OTHER_NEUTRAL;
446
447     if (LIKELY(is<RenderText>(*m_renderer))) {
448         UChar codeUnit = downcast<RenderText>(*m_renderer).characterAt(m_pos);
449         if (LIKELY(U16_IS_SINGLE(codeUnit)))
450             return u_charDirection(codeUnit);
451         return surrogateTextDirection(codeUnit);
452     }
453
454     if (m_renderer->isListMarker())
455         return m_renderer->style().isLeftToRightDirection() ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
456
457     return U_OTHER_NEUTRAL;
458 }
459
460 template<>
461 inline void InlineBidiResolver::incrementInternal()
462 {
463     m_current.increment(this);
464 }
465
466 static inline bool isIsolatedInline(RenderObject& object)
467 {
468     return object.isRenderInline() && isIsolated(object.style().unicodeBidi());
469 }
470
471 static inline RenderObject* highestContainingIsolateWithinRoot(RenderObject& initialObject, RenderObject* root)
472 {
473     RenderObject* containingIsolateObject = nullptr;
474     for (RenderObject* object = &initialObject; object && object != root; object = object->parent()) {
475         if (isIsolatedInline(*object))
476             containingIsolateObject = object;
477     }
478     return containingIsolateObject;
479 }
480
481 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
482 {
483     unsigned count = 0;
484     typedef RenderObject* RenderObjectPtr;
485     for (RenderObjectPtr object = iter.renderer(), root = iter.root(); object && object != root; object = object->parent()) {
486         if (isIsolatedInline(*object))
487             count++;
488     }
489     return count;
490 }
491
492 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization
493 // of BidiResolver which knows nothing about RenderObjects.
494 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject& obj, unsigned pos, RenderElement& root)
495 {
496     std::unique_ptr<BidiRun> isolatedRun = std::make_unique<BidiRun>(pos, pos, obj, resolver.context(), resolver.dir());
497     // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
498     // ASSERT here that we didn't create multiple objects for the same inline.
499     resolver.setWhitespaceCollapsingTransitionForIsolatedRun(*isolatedRun, resolver.whitespaceCollapsingState().currentTransition());
500     resolver.isolatedRuns().append(BidiIsolatedRun(obj, pos, root, *isolatedRun));
501     resolver.runs().appendRun(WTFMove(isolatedRun));
502 }
503
504 class IsolateTracker {
505 public:
506     explicit IsolateTracker(unsigned nestedIsolateCount)
507         : m_nestedIsolateCount(nestedIsolateCount)
508         , m_haveAddedFakeRunForRootIsolate(false)
509     {
510     }
511
512     void enterIsolate() { m_nestedIsolateCount++; }
513     void exitIsolate()
514     {
515         ASSERT(m_nestedIsolateCount >= 1);
516         m_nestedIsolateCount--;
517         if (!inIsolate())
518             m_haveAddedFakeRunForRootIsolate = false;
519     }
520     bool inIsolate() const { return m_nestedIsolateCount; }
521
522     // We don't care if we encounter bidi directional overrides.
523     void embed(UCharDirection, BidiEmbeddingSource) { }
524     void commitExplicitEmbedding() { }
525
526     void addFakeRunIfNecessary(RenderObject& obj, unsigned pos, unsigned end, RenderElement& root, InlineBidiResolver& resolver)
527     {
528         // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine.
529         // We'll be called for every span inside the isolated span so we just ignore subsequent calls.
530         // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats.
531         if (RenderBlock::shouldSkipCreatingRunsForObject(obj))
532             return;
533         if (!m_haveAddedFakeRunForRootIsolate) {
534             // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start.
535             // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the
536             // isolate, when we call createBidiRunsForLine it will stop at whichever comes first.
537             addPlaceholderRunForIsolatedInline(resolver, obj, pos, root);
538         }
539         m_haveAddedFakeRunForRootIsolate = true;
540         RenderBlockFlow::appendRunsForObject(nullptr, pos, end, obj, resolver);
541     }
542
543 private:
544     unsigned m_nestedIsolateCount;
545     bool m_haveAddedFakeRunForRootIsolate;
546 };
547
548 template<>
549 inline void InlineBidiResolver::appendRunInternal()
550 {
551     if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
552         // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
553         // Initialize our state depending on if we're starting in the middle of such an inline.
554         // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
555         IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor));
556         int start = m_sor.offset();
557         RenderObject* obj = m_sor.renderer();
558         while (obj && obj != m_eor.renderer() && obj != endOfLine.renderer()) {
559             if (isolateTracker.inIsolate())
560                 isolateTracker.addFakeRunIfNecessary(*obj, start, obj->length(), *m_sor.root(), *this);
561             else
562                 RenderBlockFlow::appendRunsForObject(&m_runs, start, obj->length(), *obj, *this);
563             // FIXME: start/obj should be an InlineIterator instead of two separate variables.
564             start = 0;
565             obj = bidiNextSkippingEmptyInlines(*m_sor.root(), obj, &isolateTracker);
566         }
567         if (obj) {
568             unsigned pos = obj == m_eor.renderer() ? m_eor.offset() : UINT_MAX;
569             if (obj == endOfLine.renderer() && endOfLine.offset() <= pos) {
570                 m_reachedEndOfLine = true;
571                 pos = endOfLine.offset();
572             }
573             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
574             int end = obj->length() ? pos + 1 : 0;
575             if (isolateTracker.inIsolate())
576                 isolateTracker.addFakeRunIfNecessary(*obj, start, obj->length(), *m_sor.root(), *this);
577             else
578                 RenderBlockFlow::appendRunsForObject(&m_runs, start, end, *obj, *this);
579         }
580
581         m_eor.increment();
582         m_sor = m_eor;
583     }
584
585     m_direction = U_OTHER_NEUTRAL;
586     m_status.eor = U_OTHER_NEUTRAL;
587 }
588
589 template<>
590 inline bool InlineBidiResolver::needsContinuePastEndInternal() const
591 {
592     // We don't collect runs beyond the endOfLine renderer. Stop traversing when the iterator moves to the next renderer to prevent O(n^2).
593     return m_current.renderer() == endOfLine.renderer();
594 }
595
596 } // namespace WebCore