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.
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.
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.
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.
23 #ifndef InlineIterator_h
24 #define InlineIterator_h
27 #include "RenderBlock.h"
28 #include "RenderText.h"
29 #include <wtf/AlwaysInline.h>
30 #include <wtf/StdLibExtras.h>
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 {
43 , m_nextBreakablePosition(-1)
47 InlineIterator(RenderObject* root, RenderObject* o, unsigned p)
51 , m_nextBreakablePosition(-1)
55 void clear() { moveTo(0, 0); }
57 void moveToStartOf(RenderObject* object)
62 void moveTo(RenderObject* object, unsigned offset, int nextBreak = -1)
66 m_nextBreakablePosition = nextBreak;
69 RenderObject* object() const { return m_obj; }
70 unsigned offset() const { return m_pos; }
71 RenderObject* root() const { return m_root; }
73 void fastIncrementInTextNode();
74 void increment(InlineBidiResolver* = 0);
77 inline bool atTextParagraphSeparator()
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';
83 inline bool atParagraphSeparator()
85 return (m_obj && m_obj->isBR()) || atTextParagraphSeparator();
88 UChar current() const;
89 UChar previousInSameNode() const;
90 ALWAYS_INLINE WTF::Unicode::Direction direction() const;
95 // FIXME: These should be private.
99 int m_nextBreakablePosition;
102 inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
104 return it1.m_pos == it2.m_pos && it1.m_obj == it2.m_obj;
107 inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
109 return it1.m_pos != it2.m_pos || it1.m_obj != it2.m_obj;
112 static inline WTF::Unicode::Direction embedCharFromDirection(TextDirection dir, EUnicodeBidi unicodeBidi)
114 using namespace WTF::Unicode;
115 if (unicodeBidi == Embed)
116 return dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding;
117 return dir == RTL ? RightToLeftOverride : LeftToRightOverride;
120 template <class Observer>
121 static inline void notifyObserverEnteredObject(Observer* observer, RenderObject* object)
123 if (!observer || !object || !object->isRenderInline())
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.
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.
143 if (!observer->inIsolate())
144 observer->embed(embedCharFromDirection(style->direction(), unicodeBidi), FromStyleOrDOM);
147 template <class Observer>
148 static inline void notifyObserverWillExitObject(Observer* observer, RenderObject* object)
150 if (!observer || !object || !object->isRenderInline())
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();
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);
166 static inline bool isIteratorTarget(RenderObject* object)
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();
172 // This enum is only used for bidiNextShared()
173 enum EmptyInlineBehavior {
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)
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;
191 if (!oldEndOfInline && !isIteratorTarget(current)) {
192 next = current->firstChild();
193 notifyObserverEnteredObject(observer, next);
196 // We hit this when either current has no children, or when current is not a renderer we care about.
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()) {
205 while (current && current != root) {
206 notifyObserverWillExitObject(observer, current);
208 next = current->nextSibling();
210 notifyObserverEnteredObject(observer, next);
214 current = current->parent();
215 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != root && current->isRenderInline()) {
226 if (isIteratorTarget(next)
227 || ((emptyInlineBehavior == IncludeEmptyInlines || !next->firstChild()) // Always return EMPTY inlines.
228 && next->isRenderInline()))
234 *endOfInlinePtr = endOfInline;
239 template <class Observer>
240 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current, Observer* observer)
242 // The SkipEmptyInlines callers never care about endOfInlinePtr.
243 return bidiNextShared(root, current, observer, SkipEmptyInlines);
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)
249 InlineBidiResolver* observer = 0;
250 return bidiNextSkippingEmptyInlines(root, current, observer);
253 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderObject* root, RenderObject* current, bool* endOfInlinePtr = 0)
255 InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer.
256 return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr);
259 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderObject* root, InlineBidiResolver* resolver = 0)
261 RenderObject* o = root->firstChild();
265 if (o->isRenderInline()) {
266 notifyObserverEnteredObject(resolver, o);
268 o = bidiNextSkippingEmptyInlines(root, o, resolver);
270 // Never skip empty inlines.
272 resolver->commitExplicitEmbedding();
277 // FIXME: Unify this with the bidiNext call above.
278 if (o && !isIteratorTarget(o))
279 o = bidiNextSkippingEmptyInlines(root, o, resolver);
282 resolver->commitExplicitEmbedding();
286 // FIXME: This method needs to be renamed when bidiNext finds a good name.
287 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderObject* root)
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))
295 return bidiNextIncludingEmptyInlines(root, o);
298 inline void InlineIterator::fastIncrementInTextNode()
301 ASSERT(m_obj->isText());
302 ASSERT(m_pos <= toRenderText(m_obj)->textLength());
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.
310 InlineWalker(RenderObject* root)
313 , m_atEndOfInline(false)
315 // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well.
316 m_current = bidiFirstIncludingEmptyInlines(m_root);
319 RenderObject* root() { return m_root; }
320 RenderObject* current() { return m_current; }
322 bool atEndOfInline() { return m_atEndOfInline; }
323 bool atEnd() const { return !m_current; }
325 RenderObject* advance()
327 // FIXME: Support SkipEmptyInlines and observer parameters.
328 m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline);
332 RenderObject* m_root;
333 RenderObject* m_current;
334 bool m_atEndOfInline;
337 inline void InlineIterator::increment(InlineBidiResolver* resolver)
341 if (m_obj->isText()) {
342 fastIncrementInTextNode();
343 if (m_pos < toRenderText(m_obj)->textLength())
346 // bidiNext can return 0, so use moveTo instead of moveToStartOf
347 moveTo(bidiNextSkippingEmptyInlines(m_root, m_obj, resolver), 0);
350 inline bool InlineIterator::atEnd() const
355 inline UChar InlineIterator::current() const
357 if (!m_obj || !m_obj->isText())
360 RenderText* text = toRenderText(m_obj);
361 if (m_pos >= text->textLength())
364 return text->characters()[m_pos];
367 inline UChar InlineIterator::previousInSameNode() const
369 if (!m_obj || !m_obj->isText() || !m_pos)
372 RenderText* text = toRenderText(m_obj);
373 return text->characters()[m_pos - 1];
376 ALWAYS_INLINE WTF::Unicode::Direction InlineIterator::direction() const
378 if (UChar c = current())
379 return WTF::Unicode::direction(c);
381 if (m_obj && m_obj->isListMarker())
382 return m_obj->style()->isLeftToRightDirection() ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft;
384 return WTF::Unicode::OtherNeutral;
388 inline void InlineBidiResolver::increment()
390 m_current.increment(this);
393 static inline bool isIsolatedInline(RenderObject* object)
396 return object->isRenderInline() && isIsolated(object->style()->unicodeBidi());
399 static inline RenderObject* containingIsolate(RenderObject* object, RenderObject* root)
402 while (object && object != root) {
403 if (isIsolatedInline(object))
405 object = object->parent();
410 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter)
412 RenderObject* object = iter.object();
416 while (object && object != iter.root()) {
417 if (isIsolatedInline(object))
419 object = object->parent();
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)
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);
436 class IsolateTracker {
438 explicit IsolateTracker(unsigned nestedIsolateCount)
439 : m_nestedIsolateCount(nestedIsolateCount)
440 , m_haveAddedFakeRunForRootIsolate(false)
444 void enterIsolate() { m_nestedIsolateCount++; }
447 ASSERT(m_nestedIsolateCount >= 1);
448 m_nestedIsolateCount--;
450 m_haveAddedFakeRunForRootIsolate = false;
452 bool inIsolate() const { return m_nestedIsolateCount; }
454 // We don't care if we encounter bidi directional overrides.
455 void embed(WTF::Unicode::Direction, BidiEmbeddingSource) { }
456 void commitExplicitEmbedding() { }
458 void addFakeRunIfNecessary(RenderObject* obj, unsigned pos, InlineBidiResolver& resolver)
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))
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);
473 unsigned m_nestedIsolateCount;
474 bool m_haveAddedFakeRunForRootIsolate;
478 inline void InlineBidiResolver::appendRun()
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);
491 RenderBlock::appendRunsForObject(m_runs, start, obj->length(), obj, *this);
492 // FIXME: start/obj should be an InlineIterator instead of two separate variables.
494 obj = bidiNextSkippingEmptyInlines(m_sor.root(), obj, &isolateTracker);
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;
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);
507 RenderBlock::appendRunsForObject(m_runs, start, end, obj, *this);
514 m_direction = WTF::Unicode::OtherNeutral;
515 m_status.eor = WTF::Unicode::OtherNeutral;
520 #endif // InlineIterator_h