← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WebCore/rendering/InlineIterator.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
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)->characterAt(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->characterAt(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->characterAt(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