Rename isPositioned to isOutOfFlowPositioned for clarity
[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 (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 // FIXME: This function is misleadingly named. It has little to do with bidi.
179 // This function will iterate over inlines within a block, optionally notifying
180 // a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels).
181 template <class Observer>
182 static inline RenderObject* bidiNextShared(RenderObject* root, RenderObject* current, Observer* observer = 0, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = 0)
183 {
184     RenderObject* next = 0;
185     // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline.
186     bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
187     bool endOfInline = false;
188
189     while (current) {
190         next = 0;
191         if (!oldEndOfInline && !isIteratorTarget(current)) {
192             next = current->firstChild();
193             notifyObserverEnteredObject(observer, next);
194         }
195
196         // We hit this when either current has no children, or when current is not a renderer we care about.
197         if (!next) {
198             // If it is a renderer we care about, and we're doing our inline-walk, return it.
199             if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && current->isRenderInline()) {
200                 next = current;
201                 endOfInline = true;
202                 break;
203             }
204
205             while (current && current != root) {
206                 notifyObserverWillExitObject(observer, current);
207
208                 next = current->nextSibling();
209                 if (next) {
210                     notifyObserverEnteredObject(observer, next);
211                     break;
212                 }
213
214                 current = current->parent();
215                 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != root && current->isRenderInline()) {
216                     next = current;
217                     endOfInline = true;
218                     break;
219                 }
220             }
221         }
222
223         if (!next)
224             break;
225
226         if (isIteratorTarget(next)
227             || ((emptyInlineBehavior == IncludeEmptyInlines || !next->firstChild()) // Always return EMPTY inlines.
228                 && next->isRenderInline()))
229             break;
230         current = next;
231     }
232
233     if (endOfInlinePtr)
234         *endOfInlinePtr = endOfInline;
235
236     return next;
237 }
238
239 template <class Observer>
240 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current, Observer* observer)
241 {
242     // The SkipEmptyInlines callers never care about endOfInlinePtr.
243     return bidiNextShared(root, current, observer, SkipEmptyInlines);
244 }
245
246 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one.
247 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current)
248 {
249     InlineBidiResolver* observer = 0;
250     return bidiNextSkippingEmptyInlines(root, current, observer);
251 }
252
253 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderObject* root, RenderObject* current, bool* endOfInlinePtr = 0)
254 {
255     InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer.
256     return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
257 }
258
259 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderObject* root, InlineBidiResolver* resolver = 0)
260 {
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     if (resolver)
282         resolver->commitExplicitEmbedding();
283     return o;
284 }
285
286 // FIXME: This method needs to be renamed when bidiNext finds a good name.
287 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderObject* root)
288 {
289     RenderObject* o = root->firstChild();
290     // If either there are no children to walk, or the first one is correct
291     // then just return it.
292     if (!o || o->isRenderInline() || isIteratorTarget(o))
293         return o;
294
295     return bidiNextIncludingEmptyInlines(root, o);
296 }
297
298 inline void InlineIterator::fastIncrementInTextNode()
299 {
300     ASSERT(m_obj);
301     ASSERT(m_obj->isText());
302     ASSERT(m_pos <= toRenderText(m_obj)->textLength());
303     m_pos++;
304 }
305
306 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi
307 // it shouldn't use functions called bidiFirst and bidiNext.
308 class InlineWalker {
309 public:
310     InlineWalker(RenderObject* root)
311         : m_root(root)
312         , m_current(0)
313         , m_atEndOfInline(false)
314     {
315         // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
316         m_current = bidiFirstIncludingEmptyInlines(m_root);
317     }
318
319     RenderObject* root() { return m_root; }
320     RenderObject* current() { return m_current; }
321
322     bool atEndOfInline() { return m_atEndOfInline; }
323     bool atEnd() const { return !m_current; }
324
325     RenderObject* advance()
326     {
327         // FIXME: Support SkipEmptyInlines and observer parameters.
328         m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
329         return m_current;
330     }
331 private:
332     RenderObject* m_root;
333     RenderObject* m_current;
334     bool m_atEndOfInline;
335 };
336
337 inline void InlineIterator::increment(InlineBidiResolver* resolver)
338 {
339     if (!m_obj)
340         return;
341     if (m_obj->isText()) {
342         fastIncrementInTextNode();
343         if (m_pos < toRenderText(m_obj)->textLength())
344             return;
345     }
346     // bidiNext can return 0, so use moveTo instead of moveToStartOf
347     moveTo(bidiNextSkippingEmptyInlines(m_root, m_obj, resolver), 0);
348 }
349
350 inline bool InlineIterator::atEnd() const
351 {
352     return !m_obj;
353 }
354
355 inline UChar InlineIterator::current() const
356 {
357     if (!m_obj || !m_obj->isText())
358         return 0;
359
360     RenderText* text = toRenderText(m_obj);
361     if (m_pos >= text->textLength())
362         return 0;
363
364     return text->characters()[m_pos];
365 }
366
367 inline UChar InlineIterator::previousInSameNode() const
368 {
369     if (!m_obj || !m_obj->isText() || !m_pos)
370         return 0;
371
372     RenderText* text = toRenderText(m_obj);
373     return text->characters()[m_pos - 1];
374 }
375
376 ALWAYS_INLINE WTF::Unicode::Direction InlineIterator::direction() const
377 {
378     if (UChar c = current())
379         return WTF::Unicode::direction(c);
380
381     if (m_obj && m_obj->isListMarker())
382         return m_obj->style()->isLeftToRightDirection() ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft;
383
384     return WTF::Unicode::OtherNeutral;
385 }
386
387 template<>
388 inline void InlineBidiResolver::increment()
389 {
390     m_current.increment(this);
391 }
392
393 static inline bool isIsolatedInline(RenderObject* object)
394 {
395     ASSERT(object);
396     return object->isRenderInline() && isIsolated(object->style()->unicodeBidi());
397 }
398
399 static inline RenderObject* containingIsolate(RenderObject* object, RenderObject* root)
400 {
401     ASSERT(object);
402     while (object && object != root) {
403         if (isIsolatedInline(object))
404             return object;
405         object = object->parent();
406     }
407     return 0;
408 }
409
410 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
411 {
412     RenderObject* object = iter.object();
413     if (!object)
414         return 0;
415     unsigned count = 0;
416     while (object && object != iter.root()) {
417         if (isIsolatedInline(object))
418             count++;
419         object = object->parent();
420     }
421     return count;
422 }
423
424 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization
425 // of BidiResolver which knows nothing about RenderObjects.
426 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject* obj, unsigned pos)
427 {
428     ASSERT(obj);
429     BidiRun* isolatedRun = new (obj->renderArena()) BidiRun(pos, 0, obj, resolver.context(), resolver.dir());
430     resolver.runs().addRun(isolatedRun);
431     // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply
432     // ASSERT here that we didn't create multiple objects for the same inline.
433     resolver.isolatedRuns().append(isolatedRun);
434 }
435
436 class IsolateTracker {
437 public:
438     explicit IsolateTracker(unsigned nestedIsolateCount)
439         : m_nestedIsolateCount(nestedIsolateCount)
440         , m_haveAddedFakeRunForRootIsolate(false)
441     {
442     }
443
444     void enterIsolate() { m_nestedIsolateCount++; }
445     void exitIsolate()
446     {
447         ASSERT(m_nestedIsolateCount >= 1);
448         m_nestedIsolateCount--;
449         if (!inIsolate())
450             m_haveAddedFakeRunForRootIsolate = false;
451     }
452     bool inIsolate() const { return m_nestedIsolateCount; }
453
454     // We don't care if we encounter bidi directional overrides.
455     void embed(WTF::Unicode::Direction, BidiEmbeddingSource) { }
456     void commitExplicitEmbedding() { }
457
458     void addFakeRunIfNecessary(RenderObject* obj, unsigned pos, InlineBidiResolver& resolver)
459     {
460         // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine.
461         // We'll be called for every span inside the isolated span so we just ignore subsequent calls.
462         // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats.
463         if (m_haveAddedFakeRunForRootIsolate || RenderBlock::shouldSkipCreatingRunsForObject(obj))
464             return;
465         m_haveAddedFakeRunForRootIsolate = true;
466         // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start.
467         // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the
468         // isolate, when we call createBidiRunsForLine it will stop at whichever comes first.
469         addPlaceholderRunForIsolatedInline(resolver, obj, pos);
470     }
471
472 private:
473     unsigned m_nestedIsolateCount;
474     bool m_haveAddedFakeRunForRootIsolate;
475 };
476
477 template <>
478 inline void InlineBidiResolver::appendRun()
479 {
480     if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) {
481         // Keep track of when we enter/leave "unicode-bidi: isolate" inlines.
482         // Initialize our state depending on if we're starting in the middle of such an inline.
483         // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree?
484         IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor));
485         int start = m_sor.m_pos;
486         RenderObject* obj = m_sor.m_obj;
487         while (obj && obj != m_eor.m_obj && obj != endOfLine.m_obj) {
488             if (isolateTracker.inIsolate())
489                 isolateTracker.addFakeRunIfNecessary(obj, start, *this);
490             else
491                 RenderBlock::appendRunsForObject(m_runs, start, obj->length(), obj, *this);
492             // FIXME: start/obj should be an InlineIterator instead of two separate variables.
493             start = 0;
494             obj = bidiNextSkippingEmptyInlines(m_sor.root(), obj, &isolateTracker);
495         }
496         if (obj) {
497             unsigned pos = obj == m_eor.m_obj ? m_eor.m_pos : UINT_MAX;
498             if (obj == endOfLine.m_obj && endOfLine.m_pos <= pos) {
499                 m_reachedEndOfLine = true;
500                 pos = endOfLine.m_pos;
501             }
502             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
503             int end = obj->length() ? pos + 1 : 0;
504             if (isolateTracker.inIsolate())
505                 isolateTracker.addFakeRunIfNecessary(obj, start, *this);
506             else
507                 RenderBlock::appendRunsForObject(m_runs, start, end, obj, *this);
508         }
509
510         m_eor.increment();
511         m_sor = m_eor;
512     }
513
514     m_direction = WTF::Unicode::OtherNeutral;
515     m_status.eor = WTF::Unicode::OtherNeutral;
516 }
517
518 }
519
520 #endif // InlineIterator_h