1 /* 2 * Copyright (C) 2000 Lars Knoll (knoll (at) 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 "core/rendering/BidiRun.h" 27 #include "core/rendering/RenderBlock.h" 28 #include "core/rendering/RenderText.h" 29 #include "wtf/StdLibExtras.h" 30 31 namespace WebCore { 32 33 // This class is used to RenderInline subtrees, stepping by character within the 34 // text children. InlineIterator will use bidiNext to find the next RenderText 35 // optionally notifying a BidiResolver every time it steps into/out of a RenderInline. 36 class InlineIterator { 37 public: 38 InlineIterator() 39 : m_root(0) 40 , m_obj(0) 41 , m_pos(0) 42 , m_nextBreakablePosition(-1) 43 { 44 } 45 46 InlineIterator(RenderObject* root, RenderObject* o, unsigned p) 47 : m_root(root) 48 , m_obj(o) 49 , m_pos(p) 50 , m_nextBreakablePosition(-1) 51 { 52 } 53 54 void clear() { moveTo(0, 0); } 55 56 void moveToStartOf(RenderObject* object) 57 { 58 moveTo(object, 0); 59 } 60 61 void moveTo(RenderObject* object, unsigned offset, int nextBreak = -1) 62 { 63 m_obj = object; 64 m_pos = offset; 65 m_nextBreakablePosition = nextBreak; 66 } 67 68 RenderObject* object() const { return m_obj; } 69 unsigned offset() const { return m_pos; } 70 RenderObject* root() const { return m_root; } 71 72 void fastIncrementInTextNode(); 73 void increment(InlineBidiResolver* = 0); 74 bool atEnd() const; 75 76 inline bool atTextParagraphSeparator() 77 { 78 return m_obj && m_obj->preservesNewline() && m_obj->isText() && toRenderText(m_obj)->textLength() 79 && !toRenderText(m_obj)->isWordBreak() && toRenderText(m_obj)->characterAt(m_pos) == '\n'; 80 } 81 82 inline bool atParagraphSeparator() 83 { 84 return (m_obj && m_obj->isBR()) || atTextParagraphSeparator(); 85 } 86 87 UChar characterAt(unsigned) const; 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 static bool isEmptyInline(RenderObject* object) 179 { 180 if (!object->isRenderInline()) 181 return false; 182 183 for (RenderObject* curr = object->firstChild(); curr; curr = curr->nextSibling()) { 184 if (curr->isFloatingOrOutOfFlowPositioned()) 185 continue; 186 if (curr->isText() && toRenderText(curr)->isAllCollapsibleWhitespace()) 187 continue; 188 189 if (!isEmptyInline(curr)) 190 return false; 191 } 192 return true; 193 } 194 195 // FIXME: This function is misleadingly named. It has little to do with bidi. 196 // This function will iterate over inlines within a block, optionally notifying 197 // a bidi resolver as it enters/exits inlines (so it can push/pop embedding levels). 198 template <class Observer> 199 static inline RenderObject* bidiNextShared(RenderObject* root, RenderObject* current, Observer* observer = 0, EmptyInlineBehavior emptyInlineBehavior = SkipEmptyInlines, bool* endOfInlinePtr = 0) 200 { 201 RenderObject* next = 0; 202 // oldEndOfInline denotes if when we last stopped iterating if we were at the end of an inline. 203 bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false; 204 bool endOfInline = false; 205 206 while (current) { 207 next = 0; 208 if (!oldEndOfInline && !isIteratorTarget(current)) { 209 next = current->firstChild(); 210 notifyObserverEnteredObject(observer, next); 211 } 212 213 // We hit this when either current has no children, or when current is not a renderer we care about. 214 if (!next) { 215 // If it is a renderer we care about, and we're doing our inline-walk, return it. 216 if (emptyInlineBehavior == IncludeEmptyInlines && !oldEndOfInline && current->isRenderInline()) { 217 next = current; 218 endOfInline = true; 219 break; 220 } 221 222 while (current && current != root) { 223 notifyObserverWillExitObject(observer, current); 224 225 next = current->nextSibling(); 226 if (next) { 227 notifyObserverEnteredObject(observer, next); 228 break; 229 } 230 231 current = current->parent(); 232 if (emptyInlineBehavior == IncludeEmptyInlines && current && current != root && current->isRenderInline()) { 233 next = current; 234 endOfInline = true; 235 break; 236 } 237 } 238 } 239 240 if (!next) 241 break; 242 243 if (isIteratorTarget(next) 244 || ((emptyInlineBehavior == IncludeEmptyInlines || isEmptyInline(next)) // Always return EMPTY inlines. 245 && next->isRenderInline())) 246 break; 247 current = next; 248 } 249 250 if (endOfInlinePtr) 251 *endOfInlinePtr = endOfInline; 252 253 return next; 254 } 255 256 template <class Observer> 257 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current, Observer* observer) 258 { 259 // The SkipEmptyInlines callers never care about endOfInlinePtr. 260 return bidiNextShared(root, current, observer, SkipEmptyInlines); 261 } 262 263 // This makes callers cleaner as they don't have to specify a type for the observer when not providing one. 264 static inline RenderObject* bidiNextSkippingEmptyInlines(RenderObject* root, RenderObject* current) 265 { 266 InlineBidiResolver* observer = 0; 267 return bidiNextSkippingEmptyInlines(root, current, observer); 268 } 269 270 static inline RenderObject* bidiNextIncludingEmptyInlines(RenderObject* root, RenderObject* current, bool* endOfInlinePtr = 0) 271 { 272 InlineBidiResolver* observer = 0; // Callers who include empty inlines, never use an observer. 273 return bidiNextShared(root, current, observer, IncludeEmptyInlines, endOfInlinePtr); 274 } 275 276 static inline RenderObject* bidiFirstSkippingEmptyInlines(RenderObject* root, InlineBidiResolver* resolver = 0) 277 { 278 RenderObject* o = root->firstChild(); 279 if (!o) 280 return 0; 281 282 if (o->isRenderInline()) { 283 notifyObserverEnteredObject(resolver, o); 284 if (!isEmptyInline(o)) 285 o = bidiNextSkippingEmptyInlines(root, o, resolver); 286 else { 287 // Never skip empty inlines. 288 if (resolver) 289 resolver->commitExplicitEmbedding(); 290 return o; 291 } 292 } 293 294 // FIXME: Unify this with the bidiNext call above. 295 if (o && !isIteratorTarget(o)) 296 o = bidiNextSkippingEmptyInlines(root, o, resolver); 297 298 if (resolver) 299 resolver->commitExplicitEmbedding(); 300 return o; 301 } 302 303 // FIXME: This method needs to be renamed when bidiNext finds a good name. 304 static inline RenderObject* bidiFirstIncludingEmptyInlines(RenderObject* root) 305 { 306 RenderObject* o = root->firstChild(); 307 // If either there are no children to walk, or the first one is correct 308 // then just return it. 309 if (!o || o->isRenderInline() || isIteratorTarget(o)) 310 return o; 311 312 return bidiNextIncludingEmptyInlines(root, o); 313 } 314 315 inline void InlineIterator::fastIncrementInTextNode() 316 { 317 ASSERT(m_obj); 318 ASSERT(m_obj->isText()); 319 ASSERT(m_pos <= toRenderText(m_obj)->textLength()); 320 if (m_pos < INT_MAX) 321 m_pos++; 322 } 323 324 // FIXME: This is used by RenderBlock for simplified layout, and has nothing to do with bidi 325 // it shouldn't use functions called bidiFirst and bidiNext. 326 class InlineWalker { 327 public: 328 InlineWalker(RenderObject* root) 329 : m_root(root) 330 , m_current(0) 331 , m_atEndOfInline(false) 332 { 333 // FIXME: This class should be taught how to do the SkipEmptyInlines codepath as well. 334 m_current = bidiFirstIncludingEmptyInlines(m_root); 335 } 336 337 RenderObject* root() { return m_root; } 338 RenderObject* current() { return m_current; } 339 340 bool atEndOfInline() { return m_atEndOfInline; } 341 bool atEnd() const { return !m_current; } 342 343 RenderObject* advance() 344 { 345 // FIXME: Support SkipEmptyInlines and observer parameters. 346 m_current = bidiNextIncludingEmptyInlines(m_root, m_current, &m_atEndOfInline); 347 return m_current; 348 } 349 private: 350 RenderObject* m_root; 351 RenderObject* m_current; 352 bool m_atEndOfInline; 353 }; 354 355 inline void InlineIterator::increment(InlineBidiResolver* resolver) 356 { 357 if (!m_obj) 358 return; 359 if (m_obj->isText()) { 360 fastIncrementInTextNode(); 361 if (m_pos < toRenderText(m_obj)->textLength()) 362 return; 363 } 364 // bidiNext can return 0, so use moveTo instead of moveToStartOf 365 moveTo(bidiNextSkippingEmptyInlines(m_root, m_obj, resolver), 0); 366 } 367 368 inline bool InlineIterator::atEnd() const 369 { 370 return !m_obj; 371 } 372 373 inline UChar InlineIterator::characterAt(unsigned index) const 374 { 375 if (!m_obj || !m_obj->isText()) 376 return 0; 377 378 return toRenderText(m_obj)->characterAt(index); 379 } 380 381 inline UChar InlineIterator::current() const 382 { 383 return characterAt(m_pos); 384 } 385 386 inline UChar InlineIterator::previousInSameNode() const 387 { 388 if (!m_pos) 389 return 0; 390 391 return characterAt(m_pos - 1); 392 } 393 394 ALWAYS_INLINE WTF::Unicode::Direction InlineIterator::direction() const 395 { 396 if (UChar c = current()) 397 return WTF::Unicode::direction(c); 398 399 if (m_obj && m_obj->isListMarker()) 400 return m_obj->style()->isLeftToRightDirection() ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft; 401 402 return WTF::Unicode::OtherNeutral; 403 } 404 405 template<> 406 inline void InlineBidiResolver::increment() 407 { 408 m_current.increment(this); 409 } 410 411 static inline bool isIsolatedInline(RenderObject* object) 412 { 413 ASSERT(object); 414 return object->isRenderInline() && isIsolated(object->style()->unicodeBidi()); 415 } 416 417 static inline RenderObject* highestContainingIsolateWithinRoot(RenderObject* object, RenderObject* root) 418 { 419 ASSERT(object); 420 RenderObject* containingIsolateObj = 0; 421 while (object && object != root) { 422 if (isIsolatedInline(object)) 423 containingIsolateObj = object; 424 425 object = object->parent(); 426 } 427 return containingIsolateObj; 428 } 429 430 static inline unsigned numberOfIsolateAncestors(const InlineIterator& iter) 431 { 432 RenderObject* object = iter.object(); 433 if (!object) 434 return 0; 435 unsigned count = 0; 436 while (object && object != iter.root()) { 437 if (isIsolatedInline(object)) 438 count++; 439 object = object->parent(); 440 } 441 return count; 442 } 443 444 // FIXME: This belongs on InlineBidiResolver, except it's a template specialization 445 // of BidiResolver which knows nothing about RenderObjects. 446 static inline void addPlaceholderRunForIsolatedInline(InlineBidiResolver& resolver, RenderObject* obj, unsigned pos) 447 { 448 ASSERT(obj); 449 BidiRun* isolatedRun = new BidiRun(pos, 0, obj, resolver.context(), resolver.dir()); 450 resolver.runs().addRun(isolatedRun); 451 // FIXME: isolatedRuns() could be a hash of object->run and then we could cheaply 452 // ASSERT here that we didn't create multiple objects for the same inline. 453 resolver.isolatedRuns().append(isolatedRun); 454 } 455 456 class IsolateTracker { 457 public: 458 explicit IsolateTracker(unsigned nestedIsolateCount) 459 : m_nestedIsolateCount(nestedIsolateCount) 460 , m_haveAddedFakeRunForRootIsolate(false) 461 { 462 } 463 464 void enterIsolate() { m_nestedIsolateCount++; } 465 void exitIsolate() 466 { 467 ASSERT(m_nestedIsolateCount >= 1); 468 m_nestedIsolateCount--; 469 if (!inIsolate()) 470 m_haveAddedFakeRunForRootIsolate = false; 471 } 472 bool inIsolate() const { return m_nestedIsolateCount; } 473 474 // We don't care if we encounter bidi directional overrides. 475 void embed(WTF::Unicode::Direction, BidiEmbeddingSource) { } 476 void commitExplicitEmbedding() { } 477 478 void addFakeRunIfNecessary(RenderObject* obj, unsigned pos, InlineBidiResolver& resolver) 479 { 480 // We only need to add a fake run for a given isolated span once during each call to createBidiRunsForLine. 481 // We'll be called for every span inside the isolated span so we just ignore subsequent calls. 482 // We also avoid creating a fake run until we hit a child that warrants one, e.g. we skip floats. 483 if (m_haveAddedFakeRunForRootIsolate || RenderBlock::shouldSkipCreatingRunsForObject(obj)) 484 return; 485 m_haveAddedFakeRunForRootIsolate = true; 486 // obj and pos together denote a single position in the inline, from which the parsing of the isolate will start. 487 // We don't need to mark the end of the run because this is implicit: it is either endOfLine or the end of the 488 // isolate, when we call createBidiRunsForLine it will stop at whichever comes first. 489 addPlaceholderRunForIsolatedInline(resolver, obj, pos); 490 // FIXME: Inline isolates don't work properly with collapsing whitespace, see webkit.org/b/109624 491 // For now, if we enter an isolate between midpoints, we increment our current midpoint or else 492 // we'll leave the isolate and ignore the content that follows. 493 MidpointState<InlineIterator>& midpointState = resolver.midpointState(); 494 if (midpointState.betweenMidpoints && midpointState.midpoints[midpointState.currentMidpoint].object() == obj) { 495 midpointState.betweenMidpoints = false; 496 ++midpointState.currentMidpoint; 497 } 498 } 499 500 private: 501 unsigned m_nestedIsolateCount; 502 bool m_haveAddedFakeRunForRootIsolate; 503 }; 504 505 template <> 506 inline void InlineBidiResolver::appendRun() 507 { 508 if (!m_emptyRun && !m_eor.atEnd() && !m_reachedEndOfLine) { 509 // Keep track of when we enter/leave "unicode-bidi: isolate" inlines. 510 // Initialize our state depending on if we're starting in the middle of such an inline. 511 // FIXME: Could this initialize from this->inIsolate() instead of walking up the render tree? 512 IsolateTracker isolateTracker(numberOfIsolateAncestors(m_sor)); 513 int start = m_sor.m_pos; 514 RenderObject* obj = m_sor.m_obj; 515 while (obj && obj != m_eor.m_obj && obj != endOfLine.m_obj) { 516 if (isolateTracker.inIsolate()) 517 isolateTracker.addFakeRunIfNecessary(obj, start, *this); 518 else 519 RenderBlock::appendRunsForObject(m_runs, start, obj->length(), obj, *this); 520 // FIXME: start/obj should be an InlineIterator instead of two separate variables. 521 start = 0; 522 obj = bidiNextSkippingEmptyInlines(m_sor.root(), obj, &isolateTracker); 523 } 524 if (obj) { 525 unsigned pos = obj == m_eor.m_obj ? m_eor.m_pos : INT_MAX; 526 if (obj == endOfLine.m_obj && endOfLine.m_pos <= pos) { 527 m_reachedEndOfLine = true; 528 pos = endOfLine.m_pos; 529 } 530 // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be 531 int end = obj->length() ? pos + 1 : 0; 532 if (isolateTracker.inIsolate()) 533 isolateTracker.addFakeRunIfNecessary(obj, start, *this); 534 else 535 RenderBlock::appendRunsForObject(m_runs, start, end, obj, *this); 536 } 537 538 m_eor.increment(); 539 m_sor = m_eor; 540 } 541 542 m_direction = WTF::Unicode::OtherNeutral; 543 m_status.eor = WTF::Unicode::OtherNeutral; 544 } 545 546 } 547 548 #endif // InlineIterator_h 549