Crash due to bidi style in isolated run
[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 "RenderBlock.h"
28 #include "RenderText.h"
29 #include <wtf/AlwaysInline.h>
30 #include <wtf/StdLibExtras.h>
31
32 namespace WebCore {
33
34 // This class is used to RenderInline subtrees, stepping by character within the
35 // text children. InlineIterator will use bidiNext to find the next RenderText
36 // optionally notifying a BidiResolver every time it steps into/out of a RenderInline.
37 class InlineIterator {
38 public:
39     InlineIterator()
40         : m_root(0)
41         , m_obj(0)
42         , m_pos(0)
43         , m_nextBreakablePosition(-1)
44     {
45     }
46
47     InlineIterator(RenderObject* root, RenderObject* o, unsigned p)
48         : m_root(root)
49         , m_obj(o)
50         , m_pos(p)
51         , m_nextBreakablePosition(-1)
52     {
53     }
54
55     void clear() { moveTo(0, 0); }
56
57     void moveToStartOf(RenderObject* object)
58     {
59         moveTo(object, 0);
60     }
61
62     void moveTo(RenderObject* object, unsigned offset, int nextBreak = -1)
63     {
64         m_obj = object;
65         m_pos = offset;
66         m_nextBreakablePosition = nextBreak;
67     }
68
69     RenderObject* object() const { return m_obj; }
70     unsigned offset() const { return m_pos; }
71     RenderObject* root() const { return m_root; }
72
73     void fastIncrementInTextNode();
74     void increment(InlineBidiResolver* = 0);
75     bool atEnd() const;
76
77     inline bool atTextParagraphSeparator()
78     {
79         return m_obj && m_obj->preservesNewline() && m_obj->isText() && toRenderText(m_obj)->textLength()
80             && !toRenderText(m_obj)->isWordBreak() && toRenderText(m_obj)->characters()[m_pos] == '\n';
81     }
82     
83     inline bool atParagraphSeparator()
84     {
85         return (m_obj && m_obj->isBR()) || atTextParagraphSeparator();
86     }
87
88     UChar current() const;
89     UChar previousInSameNode() const;
90     ALWAYS_INLINE WTF::Unicode::Direction direction() const;
91
92 private:
93     RenderObject* m_root;
94
95     // FIXME: These should be private.
96 public:
97     RenderObject* m_obj;
98     unsigned m_pos;
99     int m_nextBreakablePosition;
100 };
101
102 inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
103 {
104     return it1.m_pos == it2.m_pos && it1.m_obj == it2.m_obj;
105 }
106
107 inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
108 {
109     return it1.m_pos != it2.m_pos || it1.m_obj != it2.m_obj;
110 }
111
112 static inline WTF::Unicode::Direction embedCharFromDirection(TextDirection dir, EUnicodeBidi unicodeBidi)
113 {
114     using namespace WTF::Unicode;
115     if (unicodeBidi == Embed)
116         return dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding;
117     return dir == RTL ? RightToLeftOverride : LeftToRightOverride;
118 }
119
120 template <class Observer>
121 static inline void notifyObserverEnteredObject(Observer* observer, RenderObject* object)
122 {
123     if (!observer || !object || !object->isRenderInline())
124         return;
125
126     RenderStyle* style = object->style();
127     EUnicodeBidi unicodeBidi = style->unicodeBidi();
128     if (unicodeBidi == UBNormal) {
129         // http://dev.w3.org/csswg/css3-writing-modes/#unicode-bidi
130         // "The element does not open an additional level of embedding with respect to the bidirectional algorithm."
131         // Thus we ignore any possible dir= attribute on the span.
132         return;
133     }
134     if (unicodeBidi == Isolate) {
135         observer->enterIsolate();
136         // Embedding/Override characters implied by dir= are handled when
137         // we process the isolated span, not when laying out the "parent" run.
138         return;
139     }
140
141     // FIXME: Should unicode-bidi: plaintext really be embedding override/embed characters here?
142     if (!observer->inIsolate())
143         observer->embed(embedCharFromDirection(style->direction(), unicodeBidi), FromStyleOrDOM);
144 }
145
146 template <class Observer>
147 static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
148 {
149     if (!observer || !object || !object->isRenderInline())
150         return;
151
152     EUnicodeBidi unicodeBidi = object->style()->unicodeBidi();
153     if (unicodeBidi == UBNormal)
154         return; // Nothing to do for unicode-bidi: normal
155     if (unicodeBidi == Isolate) {
156         observer->exitIsolate();
157         return;
158     }
159
160     // Otherwise we pop any embed/override character we added when we opened this tag.
161     if (!observer->inIsolate())
162         observer->embed(WTF::Unicode::PopDirectionalFormat, FromStyleOrDOM);
163 }
164
165 static inline bool isIteratorTarget(RenderObject* object)
166 {
167     ASSERT(object); // The iterator will of course return 0, but its not an expected argument to this function.
168     return object->isText() || object->isFloating() || object->isPositioned() || object->isReplaced();
169 }
170
171 // This enum is only used for bidiNextShared()
172 enum EmptyInlineBehavior {
173     SkipEmptyInlines,
174     IncludeEmptyInlines,
175 };
176
177 // FIXME: This function is misleadingly named. It has little to do with bidi.
178 // This function will iterate over inlines within a block, optionally notifying
179 // a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels).
180 template <class Observer>
181 static inline RenderObject* bidiNextShared(RenderObject* root, RenderObject* current, Observer* observer = 0, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = 0)
182 {
183     RenderObject* next = 0;
184     // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline.
185     bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
186     bool endOfInline = false;
187
188     while (current) {
189         next = 0;
190         if (!oldEndOfInline && !isIteratorTarget(current)) {
191             next = current->firstChild();
192             notifyObserverEnteredObject(observer, next);
193         }
194
195         // We hit this when either current has no children, or when current is not a renderer we care about.
196         if (!next) {
197             // If it is a renderer we care about, and we're doing our inline-walk, return it.
198             if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && current->isRenderInline()) {
199                 next = current;
200                 endOfInline = true;
201                 break;
202             }
203
204             while (current && current != root) {
205                 notifyObserverWillExitObject(observer, current);
206
207                 next = current->nextSibling();
208                 if (next) {
209                     notifyObserverEnteredObject(observer, next);
210                     break;
211                 }
212
213                 current = current->parent();
214                 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != root && current->isRenderInline()) {
215                     next = current;
216                     endOfInline = true;
217                     break;
218                 }
219             }
220         }
221
222         if (!next)
223             break;
224
225         if (isIteratorTarget(next)
226             || ((emptyInlineBehavior == IncludeEmptyInlines || !next->firstChild()) // Always return EMPTY inlines.
227                 && next->isRenderInline()))
228             break;
229         current = next;
230     }
231
232     if (endOfInlinePtr)
233         *endOfInlinePtr = endOfInline;
234
235     return next;
236 }
237
238 template <class Observer>
239 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current, Observer* observer)
240 {
241     // The SkipEmptyInlines callers never care about endOfInlinePtr.
242     return bidiNextShared(root, current, observer, SkipEmptyInlines);
243 }
244
245 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
246 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current)
247 {
248     InlineBidiResolver* observer = 0;
249     return bidiNextSkippingEmptyInlines(root, current, observer);
250 }
251
252 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderObject* root, RenderObject* current, bool* endOfInlinePtr = 0)
253 {
254     InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer.
255     return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
256 }
257
258 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderObject* root, InlineBidiResolver* resolver)
259 {
260     ASSERT(resolver);
261     RenderObject* o = root->firstChild();
262     if (!o)
263         return 0;
264
265     if (o->isRenderInline()) {
266         notifyObserverEnteredObject(resolver, o);
267         if (o->firstChild())
268             o = bidiNextSkippingEmptyInlines(root, o, resolver);
269         else {
270             // Never skip empty inlines.
271             if (resolver)
272                 resolver->commitExplicitEmbedding();
273             return o; 
274         }
275     }
276
277     // FIXME: Unify this with the bidiNext call above.
278     if (o && !isIteratorTarget(o))
279         o = bidiNextSkippingEmptyInlines(root, o, resolver);
280
281     resolver->commitExplicitEmbedding();
282     return o;
283 }
284
285 // FIXME: This method needs to be renamed when bidiNext finds a good name.
286 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderObject* root)
287 {
288     RenderObject* o = root->firstChild();
289     // If either there are no children to walk, or the first one is correct
290     // then just return it.
291     if (!o || o->isRenderInline() || isIteratorTarget(o))
292         return o;
293
294     return bidiNextIncludingEmptyInlines(root, o);
295 }
296
297 inline void InlineIterator::fastIncrementInTextNode()
298 {
299     ASSERT(m_obj);
300     ASSERT(m_obj->isText());
301     ASSERT(m_pos <= toRenderText(m_obj)->textLength());
302     m_pos++;
303 }
304
305 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
306 // it shouldn't use functions called bidiFirst and bidiNext.
307 class InlineWalker {
308 public:
309     InlineWalker(RenderObject* root)
310         : m_root(root)
311         , m_current(0)
312         , m_atEndOfInline(false)
313     {
314         // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
315         m_current = bidiFirstIncludingEmptyInlines(m_root);
316     }
317
318     RenderObject* root() { return m_root; }
319     RenderObject* current() { return m_current; }
320
321     bool atEndOfInline() { return m_atEndOfInline; }
322     bool atEnd() const { return !m_current; }
323
324     RenderObject* advance()
325     {
326         // FIXME: Support SkipEmptyInlines and observer parameters.
327         m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
328         return m_current;
329     }
330 private:
331     RenderObject* m_root;
332     RenderObject* m_current;
333     bool m_atEndOfInline;
334 };
335
336 inline void InlineIterator::increment(InlineBidiResolver* resolver)
337 {
338     if (!m_obj)
339         return;
340     if (m_obj->isText()) {
341         fastIncrementInTextNode();
342         if (m_pos < toRenderText(m_obj)->textLength())
343             return;
344     }
345     // bidiNext can return 0, so use moveTo instead of moveToStartOf
346     moveTo(bidiNextSkippingEmptyInlines(m_root, m_obj, resolver), 0);
347 }
348
349 inline bool InlineIterator::atEnd() const
350 {
351     return !m_obj;
352 }
353
354 inline UChar InlineIterator::current() const
355 {
356     if (!m_obj || !m_obj->isText())
357         return 0;
358
359     RenderText* text = toRenderText(m_obj);
360     if (m_pos >= text->textLength())
361         return 0;
362
363     return text->characters()[m_pos];
364 }
365
366 inline UChar InlineIterator::previousInSameNode() const
367 {
368     if (!m_obj || !m_obj->isText() || !m_pos)
369         return 0;
370
371     RenderText* text = toRenderText(m_obj);
372     return text->characters()[m_pos - 1];
373 }
374
375 ALWAYS_INLINE WTF::Unicode::Direction InlineIterator::direction() const
376 {
377     if (UChar c = current())
378         return WTF::Unicode::direction(c);
379
380     if (m_obj && m_obj->isListMarker())
381         return m_obj->style()->isLeftToRightDirection() ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft;
382
383     return WTF::Unicode::OtherNeutral;
384 }
385
386 template<>
387 inline void InlineBidiResolver::increment()
388 {
389     m_current.increment(this);
390 }
391
392 static inline bool isIsolatedInline(RenderObject* object)
393 {
394     ASSERT(object);
395     return object->isRenderInline() && object->style()->unicodeBidi() == Isolate;
396 }
397
398 static inline RenderObject* containingIsolate(RenderObject* object, RenderObject* root)
399 {
400     ASSERT(object);
401     while (object && object != root) {
402         if (isIsolatedInline(object))
403             return object;
404         object = object->parent();
405     }
406     return 0;
407 }
408
409 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization
410 // of BidiResolver which knows nothing about RenderObjects.
411 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject* isolatedInline)
412 {
413     ASSERT(isolatedInline);
414     BidiRun* isolatedRun = new (isolatedInline->renderArena()) BidiRun(0, 0, isolatedInline, resolver.context(), resolver.dir());
415     resolver.runs().addRun(isolatedRun);
416     // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
417     // ASSERT here that we didn't create multiple objects for the same inline.
418     resolver.isolatedRuns().append(isolatedRun);
419 }
420
421 class IsolateTracker {
422 public:
423     explicit IsolateTracker(bool inIsolate)
424         : m_nestedIsolateCount(inIsolate ? 1 : 0)
425         , m_haveAddedFakeRunForRootIsolate(false)
426     {
427     }
428
429     void enterIsolate() { m_nestedIsolateCount++; }
430     void exitIsolate()
431     {
432         ASSERT(m_nestedIsolateCount >= 1);
433         m_nestedIsolateCount--;
434         if (!inIsolate())
435             m_haveAddedFakeRunForRootIsolate = false;
436     }
437     bool inIsolate() const { return m_nestedIsolateCount; }
438
439     // We don't care if we encounter bidi directional overrides.
440     void embed(WTF::Unicode::Direction, BidiEmbeddingSource) { }
441
442     void addFakeRunIfNecessary(RenderObject* obj, InlineBidiResolver& resolver)
443     {
444         // We only need to lookup the root isolated span and add a fake run
445         // for it once, but we'll be called for every span inside the isolated span
446         // so we just ignore the call.
447         if (m_haveAddedFakeRunForRootIsolate)
448             return;
449         m_haveAddedFakeRunForRootIsolate = true;
450
451         // FIXME: position() could be outside the run and may be the wrong call here.
452         // If we were passed an InlineIterator instead that would have the right root().
453         RenderObject* isolatedInline = containingIsolate(obj, resolver.position().root());
454         // FIXME: Because enterIsolate is not passed a RenderObject, we have to crawl up the
455         // tree to see which parent inline is the isolate. We could change enterIsolate
456         // to take a RenderObject and do this logic there, but that would be a layering
457         // violation for BidiResolver (which knows nothing about RenderObject).
458         addPlaceholderRunForIsolatedInline(resolver, isolatedInline);
459     }
460
461 private:
462     unsigned m_nestedIsolateCount;
463     bool m_haveAddedFakeRunForRootIsolate;
464 };
465
466 template <>
467 inline void InlineBidiResolver::appendRun()
468 {
469     if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
470         // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
471         // Initialize our state depending on if we're starting in the middle of such an inline.
472         // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
473         IsolateTracker isolateTracker(containingIsolate(m_sor.m_obj, m_sor.root()));
474         int start = m_sor.m_pos;
475         RenderObject* obj = m_sor.m_obj;
476         while (obj && obj != m_eor.m_obj && obj != endOfLine.m_obj) {
477             if (isolateTracker.inIsolate())
478                 isolateTracker.addFakeRunIfNecessary(obj, *this);
479             else
480                 RenderBlock::appendRunsForObject(m_runs, start, obj->length(), obj, *this);
481             // FIXME: start/obj should be an InlineIterator instead of two separate variables.
482             start = 0;
483             obj = bidiNextSkippingEmptyInlines(m_sor.root(), obj, &isolateTracker);
484         }
485         if (obj) {
486             unsigned pos = obj == m_eor.m_obj ? m_eor.m_pos : UINT_MAX;
487             if (obj == endOfLine.m_obj && endOfLine.m_pos <= pos) {
488                 m_reachedEndOfLine = true;
489                 pos = endOfLine.m_pos;
490             }
491             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
492             int end = obj->length() ? pos + 1 : 0;
493             if (isolateTracker.inIsolate())
494                 isolateTracker.addFakeRunIfNecessary(obj, *this);
495             else
496                 RenderBlock::appendRunsForObject(m_runs, start, end, obj, *this);
497         }
498
499         m_eor.increment();
500         m_sor = m_eor;
501     }
502
503     m_direction = WTF::Unicode::OtherNeutral;
504     m_status.eor = WTF::Unicode::OtherNeutral;
505 }
506
507 }
508
509 #endif // InlineIterator_h