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