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