Clean up BidiRun a little bit.
[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 // 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(RenderElement* 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     RenderElement* 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)->characterAt(m_pos) == '\n';
81     }
82     
83     inline bool atParagraphSeparator()
84     {
85         return (m_obj && m_obj->isBR()) || atTextParagraphSeparator();
86     }
87
88     UChar characterAt(unsigned) const;
89     UChar current() const;
90     UChar previousInSameNode() const;
91     ALWAYS_INLINE UCharDirection direction() const;
92
93 private:
94     RenderElement* m_root;
95
96     // FIXME: These should be private.
97 public:
98     RenderObject* m_obj;
99     unsigned m_pos;
100     int m_nextBreakablePosition;
101 };
102
103 inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
104 {
105     return it1.m_pos == it2.m_pos && it1.m_obj == it2.m_obj;
106 }
107
108 inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
109 {
110     return it1.m_pos != it2.m_pos || it1.m_obj != it2.m_obj;
111 }
112
113 static inline UCharDirection embedCharFromDirection(TextDirection direction, EUnicodeBidi unicodeBidi)
114 {
115     using namespace WTF::Unicode;
116     if (unicodeBidi == Embed)
117         return direction == RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING;
118     return direction == RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE;
119 }
120
121 template <class Observer>
122 static inline void notifyObserverEnteredObject(Observer* observer, RenderObject* object)
123 {
124     if (!observer || !object || !object->isRenderInline())
125         return;
126
127     const RenderStyle& style = object->style();
128     EUnicodeBidi unicodeBidi = style.unicodeBidi();
129     if (unicodeBidi == UBNormal) {
130         // http://dev.w3.org/csswg/css3-writing-modes/#unicode-bidi
131         // "The element does not open an additional level of embedding with respect to the bidirectional algorithm."
132         // Thus we ignore any possible dir= attribute on the span.
133         return;
134     }
135     if (isIsolated(unicodeBidi)) {
136         // Make sure that explicit embeddings are committed before we enter the isolated content.
137         observer->commitExplicitEmbedding();
138         observer->enterIsolate();
139         // Embedding/Override characters implied by dir= will be handled when
140         // we process the isolated span, not when laying out the "parent" run.
141         return;
142     }
143
144     if (!observer->inIsolate())
145         observer->embed(embedCharFromDirection(style.direction(), unicodeBidi), FromStyleOrDOM);
146 }
147
148 template <class Observer>
149 static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
150 {
151     if (!observer || !object || !object->isRenderInline())
152         return;
153
154     EUnicodeBidi unicodeBidi = object->style().unicodeBidi();
155     if (unicodeBidi == UBNormal)
156         return; // Nothing to do for unicode-bidi: normal
157     if (isIsolated(unicodeBidi)) {
158         observer->exitIsolate();
159         return;
160     }
161
162     // Otherwise we pop any embed/override character we added when we opened this tag.
163     if (!observer->inIsolate())
164         observer->embed(U_POP_DIRECTIONAL_FORMAT, FromStyleOrDOM);
165 }
166
167 static inline bool isIteratorTarget(RenderObject* object)
168 {
169     ASSERT(object); // The iterator will of course return 0, but its not an expected argument to this function.
170     return object->isTextOrLineBreak() || object->isFloating() || object->isOutOfFlowPositioned() || object->isReplaced();
171 }
172
173 // This enum is only used for bidiNextShared()
174 enum EmptyInlineBehavior {
175     SkipEmptyInlines,
176     IncludeEmptyInlines,
177 };
178
179 static bool isEmptyInline(const RenderInline& renderer)
180 {
181     for (RenderObject* curr = renderer.firstChild(); curr; curr = curr->nextSibling()) {
182         if (curr->isFloatingOrOutOfFlowPositioned())
183             continue;
184         if (curr->isText()) {
185             if (!toRenderText(curr)->isAllCollapsibleWhitespace())
186                 return false;
187             continue;
188         }
189         if (!curr->isRenderInline() || !isEmptyInline(toRenderInline(*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(RenderElement& 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 = toRenderElement(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             || (next->isRenderInline() && (emptyInlineBehavior == IncludeEmptyInlines || isEmptyInline(toRenderInline(*next)))))
245             break;
246         current = next;
247     }
248
249     if (endOfInlinePtr)
250         *endOfInlinePtr = endOfInline;
251
252     return next;
253 }
254
255 template <class Observer>
256 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current, Observer* observer)
257 {
258     // The SkipEmptyInlines callers never care about endOfInlinePtr.
259     return bidiNextShared(root, current, observer, SkipEmptyInlines);
260 }
261
262 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
263 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderElement& root, RenderObject* current)
264 {
265     InlineBidiResolver* observer = 0;
266     return bidiNextSkippingEmptyInlines(root, current, observer);
267 }
268
269 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderElement& root, RenderObject* current, bool* endOfInlinePtr = 0)
270 {
271     InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer.
272     return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
273 }
274
275 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderElement& root, InlineBidiResolver* resolver = 0)
276 {
277     RenderObject* o = root.firstChild();
278     if (!o)
279         return nullptr;
280
281     if (o->isRenderInline()) {
282         notifyObserverEnteredObject(resolver, o);
283         if (!isEmptyInline(toRenderInline(*o)))
284             o = bidiNextSkippingEmptyInlines(root, o, resolver);
285         else {
286             // Never skip empty inlines.
287             if (resolver)
288                 resolver->commitExplicitEmbedding();
289             return o; 
290         }
291     }
292
293     // FIXME: Unify this with the bidiNext call above.
294     if (o && !isIteratorTarget(o))
295         o = bidiNextSkippingEmptyInlines(root, o, resolver);
296
297     if (resolver)
298         resolver->commitExplicitEmbedding();
299     return o;
300 }
301
302 // FIXME: This method needs to be renamed when bidiNext finds a good name.
303 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderElement& root)
304 {
305     RenderObject* o = root.firstChild();
306     // If either there are no children to walk, or the first one is correct
307     // then just return it.
308     if (!o || o->isRenderInline() || isIteratorTarget(o))
309         return o;
310
311     return bidiNextIncludingEmptyInlines(root, o);
312 }
313
314 inline void InlineIterator::fastIncrementInTextNode()
315 {
316     ASSERT(m_obj);
317     ASSERT(m_obj->isText());
318     ASSERT(m_pos <= toRenderText(m_obj)->textLength());
319     m_pos++;
320 }
321
322 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
323 // it shouldn't use functions called bidiFirst and bidiNext.
324 class InlineWalker {
325 public:
326     InlineWalker(RenderElement& root)
327         : m_root(root)
328         , m_current(0)
329         , m_atEndOfInline(false)
330     {
331         // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
332         m_current = bidiFirstIncludingEmptyInlines(m_root);
333     }
334
335     RenderElement& root() { return m_root; }
336     RenderObject* current() { return m_current; }
337
338     bool atEndOfInline() { return m_atEndOfInline; }
339     bool atEnd() const { return !m_current; }
340
341     RenderObject* advance()
342     {
343         // FIXME: Support SkipEmptyInlines and observer parameters.
344         m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
345         return m_current;
346     }
347 private:
348     RenderElement& m_root;
349     RenderObject* m_current;
350     bool m_atEndOfInline;
351 };
352
353 inline void InlineIterator::increment(InlineBidiResolver* resolver)
354 {
355     if (!m_obj)
356         return;
357     if (m_obj->isText()) {
358         fastIncrementInTextNode();
359         if (m_pos < toRenderText(m_obj)->textLength())
360             return;
361     }
362     // bidiNext can return 0, so use moveTo instead of moveToStartOf
363     moveTo(bidiNextSkippingEmptyInlines(*m_root, m_obj, resolver), 0);
364 }
365
366 inline bool InlineIterator::atEnd() const
367 {
368     return !m_obj;
369 }
370
371 inline UChar InlineIterator::characterAt(unsigned index) const
372 {
373     if (!m_obj || !m_obj->isText())
374         return 0;
375
376     RenderText* text = toRenderText(m_obj);
377     if (index >= text->textLength())
378         return 0;
379
380     return text->characterAt(index);
381 }
382
383 inline UChar InlineIterator::current() const
384 {
385     return characterAt(m_pos);
386 }
387
388 inline UChar InlineIterator::previousInSameNode() const
389 {
390     if (!m_pos)
391         return 0;
392
393     return characterAt(m_pos - 1);
394 }
395
396 ALWAYS_INLINE UCharDirection InlineIterator::direction() const
397 {
398     if (UChar character = current())
399         return u_charDirection(character);
400
401     if (m_obj && m_obj->isListMarker())
402         return m_obj->style().isLeftToRightDirection() ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
403
404     return U_OTHER_NEUTRAL;
405 }
406
407 template<>
408 inline void InlineBidiResolver::increment()
409 {
410     m_current.increment(this);
411 }
412
413 static inline bool isIsolatedInline(RenderObject* object)
414 {
415     ASSERT(object);
416     return object->isRenderInline() && isIsolated(object->style().unicodeBidi());
417 }
418
419 static inline RenderObject* containingIsolate(RenderObject* object, RenderObject* root)
420 {
421     ASSERT(object);
422     RenderObject* containingIsolateObject = 0;
423     while (object && object != root) {
424         if (containingIsolateObject && !isIsolatedInline(object))
425             break;
426
427         if (isIsolatedInline(object))
428             containingIsolateObject = object;
429
430         object = object->parent();
431     }
432     return containingIsolateObject;
433 }
434
435 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
436 {
437     RenderObject* object = iter.object();
438     if (!object)
439         return 0;
440     unsigned count = 0;
441     while (object && object != iter.root()) {
442         if (isIsolatedInline(object))
443             count++;
444         object = object->parent();
445     }
446     return count;
447 }
448
449 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization
450 // of BidiResolver which knows nothing about RenderObjects.
451 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject& obj, unsigned pos)
452 {
453     BidiRun* isolatedRun = new BidiRun(pos, 0, obj, resolver.context(), resolver.dir());
454     resolver.runs().addRun(isolatedRun);
455     // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
456     // ASSERT here that we didn't create multiple objects for the same inline.
457     resolver.isolatedRuns().append(isolatedRun);
458 }
459
460 class IsolateTracker {
461 public:
462     explicit IsolateTracker(unsigned nestedIsolateCount)
463         : m_nestedIsolateCount(nestedIsolateCount)
464         , m_haveAddedFakeRunForRootIsolate(false)
465     {
466     }
467
468     void enterIsolate() { m_nestedIsolateCount++; }
469     void exitIsolate()
470     {
471         ASSERT(m_nestedIsolateCount >= 1);
472         m_nestedIsolateCount--;
473         if (!inIsolate())
474             m_haveAddedFakeRunForRootIsolate = false;
475     }
476     bool inIsolate() const { return m_nestedIsolateCount; }
477
478     // We don't care if we encounter bidi directional overrides.
479     void embed(UCharDirection, BidiEmbeddingSource) { }
480     void commitExplicitEmbedding() { }
481
482     void addFakeRunIfNecessary(RenderObject& obj, unsigned pos, InlineBidiResolver& resolver)
483     {
484         // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine.
485         // We'll be called for every span inside the isolated span so we just ignore subsequent calls.
486         // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats.
487         if (m_haveAddedFakeRunForRootIsolate || RenderBlock::shouldSkipCreatingRunsForObject(&obj))
488             return;
489         m_haveAddedFakeRunForRootIsolate = true;
490         // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start.
491         // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the
492         // isolate, when we call createBidiRunsForLine it will stop at whichever comes first.
493         addPlaceholderRunForIsolatedInline(resolver, obj, pos);
494         // FIXME: Inline isolates don't work properly with collapsing whitespace, see webkit.org/b/109624
495         // For now, if we enter an isolate between midpoints, we increment our current midpoint or else
496         // we'll leave the isolate and ignore the content that follows.
497         MidpointState<InlineIterator>& midpointState = resolver.midpointState();
498         if (midpointState.betweenMidpoints && midpointState.midpoints[midpointState.currentMidpoint].object() == &obj) {
499             midpointState.betweenMidpoints = false;
500             ++midpointState.currentMidpoint;
501         }
502     }
503
504 private:
505     unsigned m_nestedIsolateCount;
506     bool m_haveAddedFakeRunForRootIsolate;
507 };
508
509 template <>
510 inline void InlineBidiResolver::appendRun()
511 {
512     if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
513         // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
514         // Initialize our state depending on if we're starting in the middle of such an inline.
515         // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
516         IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor));
517         int start = m_sor.m_pos;
518         RenderObject* obj = m_sor.m_obj;
519         while (obj && obj != m_eor.m_obj && obj != endOfLine.m_obj) {
520             if (isolateTracker.inIsolate())
521                 isolateTracker.addFakeRunIfNecessary(*obj, start, *this);
522             else
523                 RenderBlockFlow::appendRunsForObject(m_runs, start, obj->length(), obj, *this);
524             // FIXME: start/obj should be an InlineIterator instead of two separate variables.
525             start = 0;
526             obj = bidiNextSkippingEmptyInlines(*m_sor.root(), obj, &isolateTracker);
527         }
528         if (obj) {
529             unsigned pos = obj == m_eor.m_obj ? m_eor.m_pos : UINT_MAX;
530             if (obj == endOfLine.m_obj && endOfLine.m_pos <= pos) {
531                 m_reachedEndOfLine = true;
532                 pos = endOfLine.m_pos;
533             }
534             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
535             int end = obj->length() ? pos + 1 : 0;
536             if (isolateTracker.inIsolate())
537                 isolateTracker.addFakeRunIfNecessary(*obj, start, *this);
538             else
539                 RenderBlockFlow::appendRunsForObject(m_runs, start, end, obj, *this);
540         }
541
542         m_eor.increment();
543         m_sor = m_eor;
544     }
545
546     m_direction = U_OTHER_NEUTRAL;
547     m_status.eor = U_OTHER_NEUTRAL;
548 }
549
550 }
551
552 #endif // InlineIterator_h