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