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