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