Fix nested unicode-bidi: isolate
[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/StdLibExtras.h>
30
31 namespace WebCore {
32
33 // This class is used to RenderInline subtrees, stepping by character within the
34 // text children. InlineIterator will use bidiNext to find the next RenderText
35 // optionally notifying a BidiResolver every time it steps into/out of a RenderInline.
36 class InlineIterator {
37 public:
38     InlineIterator()
39         : m_root(0)
40         , m_obj(0)
41         , m_pos(0)
42         , m_nextBreakablePosition(-1)
43     {
44     }
45
46     InlineIterator(RenderObject* root, RenderObject* o, unsigned p)
47         : m_root(root)
48         , m_obj(o)
49         , m_pos(p)
50         , m_nextBreakablePosition(-1)
51     {
52     }
53
54     void clear() { moveTo(0, 0); }
55
56     void moveToStartOf(RenderObject* object)
57     {
58         moveTo(object, 0);
59     }
60
61     void moveTo(RenderObject* object, unsigned offset, int nextBreak = -1)
62     {
63         m_obj = object;
64         m_pos = offset;
65         m_nextBreakablePosition = nextBreak;
66     }
67
68     RenderObject* object() const { return m_obj; }
69     unsigned offset() const { return m_pos; }
70     RenderObject* root() const { return m_root; }
71
72     void fastIncrementInTextNode();
73     void increment(InlineBidiResolver* = 0);
74     bool atEnd() const;
75
76     inline bool atTextParagraphSeparator()
77     {
78         return m_obj && m_obj->preservesNewline() && m_obj->isText() && toRenderText(m_obj)->textLength()
79             && !toRenderText(m_obj)->isWordBreak() && toRenderText(m_obj)->characterAt(m_pos) == '\n';
80     }
81     
82     inline bool atParagraphSeparator()
83     {
84         return (m_obj && m_obj->isBR()) || atTextParagraphSeparator();
85     }
86
87     UChar characterAt(unsigned) const;
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 (isIsolated(unicodeBidi)) {
135         // Make sure that explicit embeddings are committed before we enter the isolated content.
136         observer->commitExplicitEmbedding();
137         observer->enterIsolate();
138         // Embedding/Override characters implied by dir= will be handled when
139         // we process the isolated span, not when laying out the "parent" run.
140         return;
141     }
142
143     if (!observer->inIsolate())
144         observer->embed(embedCharFromDirection(style->direction(), unicodeBidi), FromStyleOrDOM);
145 }
146
147 template <class Observer>
148 static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
149 {
150     if (!observer || !object || !object->isRenderInline())
151         return;
152
153     EUnicodeBidi unicodeBidi = object->style()->unicodeBidi();
154     if (unicodeBidi == UBNormal)
155         return; // Nothing to do for unicode-bidi: normal
156     if (isIsolated(unicodeBidi)) {
157         observer->exitIsolate();
158         return;
159     }
160
161     // Otherwise we pop any embed/override character we added when we opened this tag.
162     if (!observer->inIsolate())
163         observer->embed(WTF::Unicode::PopDirectionalFormat, FromStyleOrDOM);
164 }
165
166 static inline bool isIteratorTarget(RenderObject* object)
167 {
168     ASSERT(object); // The iterator will of course return 0, but its not an expected argument to this function.
169     return object->isText() || object->isFloating() || object->isOutOfFlowPositioned() || object->isReplaced();
170 }
171
172 // This enum is only used for bidiNextShared()
173 enum EmptyInlineBehavior {
174     SkipEmptyInlines,
175     IncludeEmptyInlines,
176 };
177
178 static bool isEmptyInline(RenderObject* object)
179 {
180     if (!object->isRenderInline())
181         return false;
182
183     for (RenderObject* curr = object->firstChild(); curr; curr = curr->nextSibling()) {
184         if (curr->isFloatingOrOutOfFlowPositioned())
185             continue;
186         if (curr->isText() && toRenderText(curr)->isAllCollapsibleWhitespace())
187             continue;
188
189         if (!isEmptyInline(curr))
190             return false;
191     }
192     return true;
193 }
194
195 // FIXME: This function is misleadingly named. It has little to do with bidi.
196 // This function will iterate over inlines within a block, optionally notifying
197 // a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels).
198 template <class Observer>
199 static inline RenderObject* bidiNextShared(RenderObject* root, RenderObject* current, Observer* observer = 0, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = 0)
200 {
201     RenderObject* next = 0;
202     // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline.
203     bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
204     bool endOfInline = false;
205
206     while (current) {
207         next = 0;
208         if (!oldEndOfInline && !isIteratorTarget(current)) {
209             next = current->firstChild();
210             notifyObserverEnteredObject(observer, next);
211         }
212
213         // We hit this when either current has no children, or when current is not a renderer we care about.
214         if (!next) {
215             // If it is a renderer we care about, and we're doing our inline-walk, return it.
216             if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && current->isRenderInline()) {
217                 next = current;
218                 endOfInline = true;
219                 break;
220             }
221
222             while (current && current != root) {
223                 notifyObserverWillExitObject(observer, current);
224
225                 next = current->nextSibling();
226                 if (next) {
227                     notifyObserverEnteredObject(observer, next);
228                     break;
229                 }
230
231                 current = current->parent();
232                 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != root && current->isRenderInline()) {
233                     next = current;
234                     endOfInline = true;
235                     break;
236                 }
237             }
238         }
239
240         if (!next)
241             break;
242
243         if (isIteratorTarget(next)
244             || ((emptyInlineBehavior == IncludeEmptyInlines || isEmptyInline(next)) // Always return EMPTY inlines.
245                 && next->isRenderInline()))
246             break;
247         current = next;
248     }
249
250     if (endOfInlinePtr)
251         *endOfInlinePtr = endOfInline;
252
253     return next;
254 }
255
256 template <class Observer>
257 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current, Observer* observer)
258 {
259     // The SkipEmptyInlines callers never care about endOfInlinePtr.
260     return bidiNextShared(root, current, observer, SkipEmptyInlines);
261 }
262
263 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
264 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current)
265 {
266     InlineBidiResolver* observer = 0;
267     return bidiNextSkippingEmptyInlines(root, current, observer);
268 }
269
270 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderObject* root, RenderObject* current, bool* endOfInlinePtr = 0)
271 {
272     InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer.
273     return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
274 }
275
276 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderObject* root, InlineBidiResolver* resolver = 0)
277 {
278     RenderObject* o = root->firstChild();
279     if (!o)
280         return 0;
281
282     if (o->isRenderInline()) {
283         notifyObserverEnteredObject(resolver, o);
284         if (!isEmptyInline(o))
285             o = bidiNextSkippingEmptyInlines(root, o, resolver);
286         else {
287             // Never skip empty inlines.
288             if (resolver)
289                 resolver->commitExplicitEmbedding();
290             return o; 
291         }
292     }
293
294     // FIXME: Unify this with the bidiNext call above.
295     if (o && !isIteratorTarget(o))
296         o = bidiNextSkippingEmptyInlines(root, o, resolver);
297
298     if (resolver)
299         resolver->commitExplicitEmbedding();
300     return o;
301 }
302
303 // FIXME: This method needs to be renamed when bidiNext finds a good name.
304 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderObject* root)
305 {
306     RenderObject* o = root->firstChild();
307     // If either there are no children to walk, or the first one is correct
308     // then just return it.
309     if (!o || o->isRenderInline() || isIteratorTarget(o))
310         return o;
311
312     return bidiNextIncludingEmptyInlines(root, o);
313 }
314
315 inline void InlineIterator::fastIncrementInTextNode()
316 {
317     ASSERT(m_obj);
318     ASSERT(m_obj->isText());
319     ASSERT(m_pos <= toRenderText(m_obj)->textLength());
320     m_pos++;
321 }
322
323 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
324 // it shouldn't use functions called bidiFirst and bidiNext.
325 class InlineWalker {
326 public:
327     InlineWalker(RenderObject* root)
328         : m_root(root)
329         , m_current(0)
330         , m_atEndOfInline(false)
331     {
332         // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
333         m_current = bidiFirstIncludingEmptyInlines(m_root);
334     }
335
336     RenderObject* root() { return m_root; }
337     RenderObject* current() { return m_current; }
338
339     bool atEndOfInline() { return m_atEndOfInline; }
340     bool atEnd() const { return !m_current; }
341
342     RenderObject* advance()
343     {
344         // FIXME: Support SkipEmptyInlines and observer parameters.
345         m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
346         return m_current;
347     }
348 private:
349     RenderObject* m_root;
350     RenderObject* m_current;
351     bool m_atEndOfInline;
352 };
353
354 inline void InlineIterator::increment(InlineBidiResolver* resolver)
355 {
356     if (!m_obj)
357         return;
358     if (m_obj->isText()) {
359         fastIncrementInTextNode();
360         if (m_pos < toRenderText(m_obj)->textLength())
361             return;
362     }
363     // bidiNext can return 0, so use moveTo instead of moveToStartOf
364     moveTo(bidiNextSkippingEmptyInlines(m_root, m_obj, resolver), 0);
365 }
366
367 inline bool InlineIterator::atEnd() const
368 {
369     return !m_obj;
370 }
371
372 inline UChar InlineIterator::characterAt(unsigned index) const
373 {
374     if (!m_obj || !m_obj->isText())
375         return 0;
376
377     RenderText* text = toRenderText(m_obj);
378     if (index >= text->textLength())
379         return 0;
380
381     return text->characterAt(index);
382 }
383
384 inline UChar InlineIterator::current() const
385 {
386     return characterAt(m_pos);
387 }
388
389 inline UChar InlineIterator::previousInSameNode() const
390 {
391     if (!m_pos)
392         return 0;
393
394     return characterAt(m_pos - 1);
395 }
396
397 ALWAYS_INLINE WTF::Unicode::Direction InlineIterator::direction() const
398 {
399     if (UChar c = current())
400         return WTF::Unicode::direction(c);
401
402     if (m_obj && m_obj->isListMarker())
403         return m_obj->style()->isLeftToRightDirection() ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft;
404
405     return WTF::Unicode::OtherNeutral;
406 }
407
408 template<>
409 inline void InlineBidiResolver::increment()
410 {
411     m_current.increment(this);
412 }
413
414 static inline bool isIsolatedInline(RenderObject* object)
415 {
416     ASSERT(object);
417     return object->isRenderInline() && isIsolated(object->style()->unicodeBidi());
418 }
419
420 static inline RenderObject* containingIsolate(RenderObject* object, RenderObject* root)
421 {
422     ASSERT(object);
423     RenderObject* containingIsolateObject = 0;
424     while (object && object != root) {
425         if (containingIsolateObject && !isIsolatedInline(object))
426             break;
427
428         if (isIsolatedInline(object))
429             containingIsolateObject = object;
430
431         object = object->parent();
432     }
433     return containingIsolateObject;
434 }
435
436 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
437 {
438     RenderObject* object = iter.object();
439     if (!object)
440         return 0;
441     unsigned count = 0;
442     while (object && object != iter.root()) {
443         if (isIsolatedInline(object))
444             count++;
445         object = object->parent();
446     }
447     return count;
448 }
449
450 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization
451 // of BidiResolver which knows nothing about RenderObjects.
452 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject* obj, unsigned pos)
453 {
454     ASSERT(obj);
455     BidiRun* isolatedRun = new (obj->renderArena()) BidiRun(pos, 0, obj, resolver.context(), resolver.dir());
456     resolver.runs().addRun(isolatedRun);
457     // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
458     // ASSERT here that we didn't create multiple objects for the same inline.
459     resolver.isolatedRuns().append(isolatedRun);
460 }
461
462 class IsolateTracker {
463 public:
464     explicit IsolateTracker(unsigned nestedIsolateCount)
465         : m_nestedIsolateCount(nestedIsolateCount)
466         , m_haveAddedFakeRunForRootIsolate(false)
467     {
468     }
469
470     void enterIsolate() { m_nestedIsolateCount++; }
471     void exitIsolate()
472     {
473         ASSERT(m_nestedIsolateCount >= 1);
474         m_nestedIsolateCount--;
475         if (!inIsolate())
476             m_haveAddedFakeRunForRootIsolate = false;
477     }
478     bool inIsolate() const { return m_nestedIsolateCount; }
479
480     // We don't care if we encounter bidi directional overrides.
481     void embed(WTF::Unicode::Direction, BidiEmbeddingSource) { }
482     void commitExplicitEmbedding() { }
483
484     void addFakeRunIfNecessary(RenderObject* obj, unsigned pos, InlineBidiResolver& resolver)
485     {
486         // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine.
487         // We'll be called for every span inside the isolated span so we just ignore subsequent calls.
488         // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats.
489         if (m_haveAddedFakeRunForRootIsolate || RenderBlock::shouldSkipCreatingRunsForObject(obj))
490             return;
491         m_haveAddedFakeRunForRootIsolate = true;
492         // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start.
493         // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the
494         // isolate, when we call createBidiRunsForLine it will stop at whichever comes first.
495         addPlaceholderRunForIsolatedInline(resolver, obj, pos);
496         // FIXME: Inline isolates don't work properly with collapsing whitespace, see webkit.org/b/109624
497         // For now, if we enter an isolate between midpoints, we increment our current midpoint or else
498         // we'll leave the isolate and ignore the content that follows.
499         MidpointState<InlineIterator>& midpointState = resolver.midpointState();
500         if (midpointState.betweenMidpoints && midpointState.midpoints[midpointState.currentMidpoint].object() == obj) {
501             midpointState.betweenMidpoints = false;
502             ++midpointState.currentMidpoint;
503         }
504     }
505
506 private:
507     unsigned m_nestedIsolateCount;
508     bool m_haveAddedFakeRunForRootIsolate;
509 };
510
511 template <>
512 inline void InlineBidiResolver::appendRun()
513 {
514     if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
515         // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
516         // Initialize our state depending on if we're starting in the middle of such an inline.
517         // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
518         IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor));
519         int start = m_sor.m_pos;
520         RenderObject* obj = m_sor.m_obj;
521         while (obj && obj != m_eor.m_obj && obj != endOfLine.m_obj) {
522             if (isolateTracker.inIsolate())
523                 isolateTracker.addFakeRunIfNecessary(obj, start, *this);
524             else
525                 RenderBlock::appendRunsForObject(m_runs, start, obj->length(), obj, *this);
526             // FIXME: start/obj should be an InlineIterator instead of two separate variables.
527             start = 0;
528             obj = bidiNextSkippingEmptyInlines(m_sor.root(), obj, &isolateTracker);
529         }
530         if (obj) {
531             unsigned pos = obj == m_eor.m_obj ? m_eor.m_pos : UINT_MAX;
532             if (obj == endOfLine.m_obj && endOfLine.m_pos <= pos) {
533                 m_reachedEndOfLine = true;
534                 pos = endOfLine.m_pos;
535             }
536             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
537             int end = obj->length() ? pos + 1 : 0;
538             if (isolateTracker.inIsolate())
539                 isolateTracker.addFakeRunIfNecessary(obj, start, *this);
540             else
541                 RenderBlock::appendRunsForObject(m_runs, start, end, obj, *this);
542         }
543
544         m_eor.increment();
545         m_sor = m_eor;
546     }
547
548     m_direction = WTF::Unicode::OtherNeutral;
549     m_status.eor = WTF::Unicode::OtherNeutral;
550 }
551
552 }
553
554 #endif // InlineIterator_h