Source/WebCore/platform/text/BidiResolver.h

   1 /*
   2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
   3  * Copyright (C) 2003, 2004, 2006, 2007, 2008 Apple Inc.  All right reserved.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this library; see the file COPYING.LIB.  If not, write to
  17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 #ifndef BidiResolver_h
  23 #define BidiResolver_h
  24
  25 #include "BidiContext.h"
  26 #include "BidiRunList.h"
  27 #include "TextDirection.h"
  28 #include <wtf/Noncopyable.h>
  29 #include <wtf/PassRefPtr.h>
  30 #include <wtf/Vector.h>
  31
  32 namespace WebCore {
  33
  34 class RenderObject;
  35
  36 template <class Iterator> class MidpointState {
  37 public:
  38     MidpointState()
  39     {
  40         reset();
  41     }
  42
  43     void reset()
  44     {
  45         numMidpoints = 0;
  46         currentMidpoint = 0;
  47         betweenMidpoints = false;
  48     }
  49
  50     // The goal is to reuse the line state across multiple
  51     // lines so we just keep an array around for midpoints and never clear it across multiple
  52     // lines.  We track the number of items and position using the two other variables.
  53     Vector<Iterator> midpoints;
  54     unsigned numMidpoints;
  55     unsigned currentMidpoint;
  56     bool betweenMidpoints;
  57
  58     void startIgnoringSpaces(const Iterator& midpoint)
  59     {
  60         ASSERT(!(numMidpoints % 2));
  61         deprecatedAddMidpoint(midpoint);
  62     }
  63
  64     void stopIgnoringSpaces(const Iterator& midpoint)
  65     {
  66         ASSERT(numMidpoints % 2);
  67         deprecatedAddMidpoint(midpoint);
  68     }
  69
  70     // When ignoring spaces, this needs to be called for objects that need line boxes such as RenderInlines or
  71     // hard line breaks to ensure that they're not ignored.
  72     void ensureLineBoxInsideIgnoredSpaces(RenderObject* renderer)
  73     {
  74         Iterator midpoint(0, renderer, 0);
  75         stopIgnoringSpaces(midpoint);
  76         startIgnoringSpaces(midpoint);
  77     }
  78 private:
  79     void deprecatedAddMidpoint(const Iterator& midpoint)
  80     {
  81         if (midpoints.size() <= numMidpoints)
  82             midpoints.grow(numMidpoints + 10);
  83
  84         Iterator* midpointsIterator = midpoints.data();
  85         midpointsIterator[numMidpoints++] = midpoint;
  86     }
  87 };
  88
  89 // The BidiStatus at a given position (typically the end of a line) can
  90 // be cached and then used to restart bidi resolution at that position.
  91 struct BidiStatus {
  92     BidiStatus()
  93         : eor(U_OTHER_NEUTRAL)
  94         , lastStrong(U_OTHER_NEUTRAL)
  95         , last(U_OTHER_NEUTRAL)
  96     {
  97     }
  98
  99     // Creates a BidiStatus representing a new paragraph root with a default direction.
 100     // Uses TextDirection as it only has two possibilities instead of UCharDirection which has at least 19.
 101     BidiStatus(TextDirection textDirection, bool isOverride)
 102     {
 103         UCharDirection direction = textDirection == LTR ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
 104         eor = lastStrong = last = direction;
 105         context = BidiContext::create(textDirection == LTR ? 0 : 1, direction, isOverride);
 106     }
 107
 108     BidiStatus(UCharDirection eorDir, UCharDirection lastStrongDir, UCharDirection lastDir, PassRefPtr<BidiContext> bidiContext)
 109         : eor(eorDir)
 110         , lastStrong(lastStrongDir)
 111         , last(lastDir)
 112         , context(bidiContext)
 113     {
 114     }
 115
 116     UCharDirection eor;
 117     UCharDirection lastStrong;
 118     UCharDirection last;
 119     RefPtr<BidiContext> context;
 120 };
 121
 122 class BidiEmbedding {
 123 public:
 124     BidiEmbedding(UCharDirection direction, BidiEmbeddingSource source)
 125     : m_direction(direction)
 126     , m_source(source)
 127     {
 128     }
 129
 130     UCharDirection direction() const { return m_direction; }
 131     BidiEmbeddingSource source() const { return m_source; }
 132 private:
 133     UCharDirection m_direction;
 134     BidiEmbeddingSource m_source;
 135 };
 136
 137 inline bool operator==(const BidiStatus& status1, const BidiStatus& status2)
 138 {
 139     return status1.eor == status2.eor && status1.last == status2.last && status1.lastStrong == status2.lastStrong && *(status1.context) == *(status2.context);
 140 }
 141
 142 inline bool operator!=(const BidiStatus& status1, const BidiStatus& status2)
 143 {
 144     return !(status1 == status2);
 145 }
 146
 147 struct BidiCharacterRun {
 148     BidiCharacterRun(int start, int stop, BidiContext* context, UCharDirection direction)
 149         : m_override(context->override())
 150         , m_next(0)
 151         , m_start(start)
 152         , m_stop(stop)
 153     {
 154         if (direction == U_OTHER_NEUTRAL)
 155             direction = context->dir();
 156
 157         m_level = context->level();
 158
 159         // add level of run (cases I1 & I2)
 160         if (m_level % 2) {
 161             if (direction == U_LEFT_TO_RIGHT || direction == U_ARABIC_NUMBER || direction == U_EUROPEAN_NUMBER)
 162                 m_level++;
 163         } else {
 164             if (direction == U_RIGHT_TO_LEFT)
 165                 m_level++;
 166             else if (direction == U_ARABIC_NUMBER || direction == U_EUROPEAN_NUMBER)
 167                 m_level += 2;
 168         }
 169     }
 170
 171     int start() const { return m_start; }
 172     int stop() const { return m_stop; }
 173     unsigned char level() const { return m_level; }
 174     bool reversed(bool visuallyOrdered) { return m_level % 2 && !visuallyOrdered; }
 175     bool dirOverride(bool visuallyOrdered) { return m_override || visuallyOrdered; }
 176
 177     BidiCharacterRun* next() const { return m_next; }
 178     void setNext(BidiCharacterRun* next) { m_next = next; }
 179
 180     // Do not add anything apart from bitfields until after m_next. See https://bugs.webkit.org/show_bug.cgi?id=100173
 181     bool m_override : 1;
 182     bool m_hasHyphen : 1; // Used by BidiRun subclass which is a layering violation but enables us to save 8 bytes per object on 64-bit.
 183 #if ENABLE(CSS_SHAPES)
 184     bool m_startsSegment : 1; // Same comment as m_hasHyphen.
 185 #endif
 186     unsigned char m_level;
 187     BidiCharacterRun* m_next;
 188     int m_start;
 189     int m_stop;
 190 };
 191
 192 enum VisualDirectionOverride {
 193     NoVisualOverride,
 194     VisualLeftToRightOverride,
 195     VisualRightToLeftOverride
 196 };
 197
 198 // BidiResolver is WebKit's implementation of the Unicode Bidi Algorithm
 199 // http://unicode.org/reports/tr9
 200 template <class Iterator, class Run> class BidiResolver {
 201     WTF_MAKE_NONCOPYABLE(BidiResolver);
 202 public:
 203     BidiResolver()
 204         : m_direction(U_OTHER_NEUTRAL)
 205         , m_reachedEndOfLine(false)
 206         , m_emptyRun(true)
 207         , m_nestedIsolateCount(0)
 208     {
 209     }
 210
 211 #ifndef NDEBUG
 212     ~BidiResolver();
 213 #endif
 214
 215     const Iterator& position() const { return m_current; }
 216     void setPositionIgnoringNestedIsolates(const Iterator& position) { m_current = position; }
 217     void setPosition(const Iterator& position, unsigned nestedIsolatedCount)
 218     {
 219         m_current = position;
 220         m_nestedIsolateCount = nestedIsolatedCount;
 221     }
 222
 223     void increment() { m_current.increment(); }
 224
 225     BidiContext* context() const { return m_status.context.get(); }
 226     void setContext(PassRefPtr<BidiContext> c) { m_status.context = c; }
 227
 228     void setLastDir(UCharDirection lastDir) { m_status.last = lastDir; }
 229     void setLastStrongDir(UCharDirection lastStrongDir) { m_status.lastStrong = lastStrongDir; }
 230     void setEorDir(UCharDirection eorDir) { m_status.eor = eorDir; }
 231
 232     UCharDirection dir() const { return m_direction; }
 233     void setDir(UCharDirection d) { m_direction = d; }
 234
 235     const BidiStatus& status() const { return m_status; }
 236     void setStatus(const BidiStatus s) { m_status = s; }
 237
 238     MidpointState<Iterator>& midpointState() { return m_midpointState; }
 239
 240     // The current algorithm handles nested isolates one layer of nesting at a time.
 241     // But when we layout each isolated span, we will walk into (and ignore) all
 242     // child isolated spans.
 243     void enterIsolate() { m_nestedIsolateCount++; }
 244     void exitIsolate() { ASSERT(m_nestedIsolateCount >= 1); m_nestedIsolateCount--; }
 245     bool inIsolate() const { return m_nestedIsolateCount; }
 246
 247     void embed(UCharDirection, BidiEmbeddingSource);
 248     bool commitExplicitEmbedding();
 249
 250     void createBidiRunsForLine(const Iterator& end, VisualDirectionOverride = NoVisualOverride, bool hardLineBreak = false);
 251
 252     BidiRunList<Run>& runs() { return m_runs; }
 253
 254     // FIXME: This used to be part of deleteRuns() but was a layering violation.
 255     // It's unclear if this is still needed.
 256     void markCurrentRunEmpty() { m_emptyRun = true; }
 257
 258     Vector<Run*>& isolatedRuns() { return m_isolatedRuns; }
 259
 260 protected:
 261     // FIXME: Instead of InlineBidiResolvers subclassing this method, we should
 262     // pass in some sort of Traits object which knows how to create runs for appending.
 263     void appendRun();
 264
 265     Iterator m_current;
 266     // sor and eor are "start of run" and "end of run" respectively and correpond
 267     // to abreviations used in UBA spec: http://unicode.org/reports/tr9/#BD7
 268     Iterator m_sor; // Points to the first character in the current run.
 269     Iterator m_eor; // Points to the last character in the current run.
 270     Iterator m_last;
 271     BidiStatus m_status;
 272     UCharDirection m_direction;
 273     Iterator endOfLine;
 274     bool m_reachedEndOfLine;
 275     Iterator m_lastBeforeET; // Before a U_EUROPEAN_NUMBER_TERMINATOR
 276     bool m_emptyRun;
 277
 278     // FIXME: This should not belong to the resolver, but rather be passed
 279     // into createBidiRunsForLine by the caller.
 280     BidiRunList<Run> m_runs;
 281
 282     MidpointState<Iterator> m_midpointState;
 283
 284     unsigned m_nestedIsolateCount;
 285     Vector<Run*> m_isolatedRuns;
 286
 287 private:
 288     void raiseExplicitEmbeddingLevel(UCharDirection from, UCharDirection to);
 289     void lowerExplicitEmbeddingLevel(UCharDirection from);
 290     void checkDirectionInLowerRaiseEmbeddingLevel();
 291
 292     void updateStatusLastFromCurrentDirection(UCharDirection);
 293     void reorderRunsFromLevels();
 294
 295     Vector<BidiEmbedding, 8> m_currentExplicitEmbeddingSequence;
 296 };
 297
 298 #ifndef NDEBUG
 299 template <class Iterator, class Run>
 300 BidiResolver<Iterator, Run>::~BidiResolver()
 301 {
 302     // The owner of this resolver should have handled the isolated runs
 303     // or should never have called enterIsolate().
 304     ASSERT(m_isolatedRuns.isEmpty());
 305     ASSERT(!m_nestedIsolateCount);
 306 }
 307 #endif
 308
 309 template <class Iterator, class Run>
 310 void BidiResolver<Iterator, Run>::appendRun()
 311 {
 312     if (!m_emptyRun && !m_eor.atEnd()) {
 313         unsigned startOffset = m_sor.offset();
 314         unsigned endOffset = m_eor.offset();
 315
 316         if (!endOfLine.atEnd() && endOffset >= endOfLine.offset()) {
 317             m_reachedEndOfLine = true;
 318             endOffset = endOfLine.offset();
 319         }
 320
 321         if (endOffset >= startOffset)
 322             m_runs.addRun(new Run(startOffset, endOffset + 1, context(), m_direction));
 323
 324         m_eor.increment();
 325         m_sor = m_eor;
 326     }
 327
 328     m_direction = U_OTHER_NEUTRAL;
 329     m_status.eor = U_OTHER_NEUTRAL;
 330 }
 331
 332 template <class Iterator, class Run>
 333 void BidiResolver<Iterator, Run>::embed(UCharDirection dir, BidiEmbeddingSource source)
 334 {
 335     // Isolated spans compute base directionality during their own UBA run.
 336     // Do not insert fake embed characters once we enter an isolated span.
 337     ASSERT(!inIsolate());
 338
 339     ASSERT(dir == U_POP_DIRECTIONAL_FORMAT || dir == U_LEFT_TO_RIGHT_EMBEDDING || dir == U_LEFT_TO_RIGHT_OVERRIDE || dir == U_RIGHT_TO_LEFT_EMBEDDING || dir == U_RIGHT_TO_LEFT_OVERRIDE);
 340     m_currentExplicitEmbeddingSequence.append(BidiEmbedding(dir, source));
 341 }
 342
 343 template <class Iterator, class Run>
 344 void BidiResolver<Iterator, Run>::checkDirectionInLowerRaiseEmbeddingLevel()
 345 {
 346     ASSERT(m_status.eor != U_OTHER_NEUTRAL || m_eor.atEnd());
 347     ASSERT(m_status.last != U_DIR_NON_SPACING_MARK
 348         && m_status.last != U_BOUNDARY_NEUTRAL
 349         && m_status.last != U_RIGHT_TO_LEFT_EMBEDDING
 350         && m_status.last != U_LEFT_TO_RIGHT_EMBEDDING
 351         && m_status.last != U_RIGHT_TO_LEFT_OVERRIDE
 352         && m_status.last != U_LEFT_TO_RIGHT_OVERRIDE
 353         && m_status.last != U_POP_DIRECTIONAL_FORMAT);
 354     if (m_direction == U_OTHER_NEUTRAL)
 355         m_direction = m_status.lastStrong == U_LEFT_TO_RIGHT ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
 356 }
 357
 358 template <class Iterator, class Run>
 359 void BidiResolver<Iterator, Run>::lowerExplicitEmbeddingLevel(UCharDirection from)
 360 {
 361     if (!m_emptyRun && m_eor != m_last) {
 362         checkDirectionInLowerRaiseEmbeddingLevel();
 363         // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
 364         if (from == U_LEFT_TO_RIGHT) {
 365             // bidi.sor ... bidi.eor ... bidi.last L
 366             if (m_status.eor == U_EUROPEAN_NUMBER) {
 367                 if (m_status.lastStrong != U_LEFT_TO_RIGHT) {
 368                     m_direction = U_EUROPEAN_NUMBER;
 369                     appendRun();
 370                 }
 371             } else if (m_status.eor == U_ARABIC_NUMBER) {
 372                 m_direction = U_ARABIC_NUMBER;
 373                 appendRun();
 374             } else if (m_status.lastStrong != U_LEFT_TO_RIGHT) {
 375                 appendRun();
 376                 m_direction = U_LEFT_TO_RIGHT;
 377             }
 378         } else if (m_status.eor == U_EUROPEAN_NUMBER || m_status.eor == U_ARABIC_NUMBER || m_status.lastStrong == U_LEFT_TO_RIGHT) {
 379             appendRun();
 380             m_direction = U_RIGHT_TO_LEFT;
 381         }
 382         m_eor = m_last;
 383     }
 384
 385     appendRun();
 386     m_emptyRun = true;
 387
 388     // sor for the new run is determined by the higher level (rule X10)
 389     setLastDir(from);
 390     setLastStrongDir(from);
 391     m_eor = Iterator();
 392 }
 393
 394 template <class Iterator, class Run>
 395 void BidiResolver<Iterator, Run>::raiseExplicitEmbeddingLevel(UCharDirection from, UCharDirection to)
 396 {
 397     if (!m_emptyRun && m_eor != m_last) {
 398         checkDirectionInLowerRaiseEmbeddingLevel();
 399         // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
 400         if (to == U_LEFT_TO_RIGHT) {
 401             // bidi.sor ... bidi.eor ... bidi.last L
 402             if (m_status.eor == U_EUROPEAN_NUMBER) {
 403                 if (m_status.lastStrong != U_LEFT_TO_RIGHT) {
 404                     m_direction = U_EUROPEAN_NUMBER;
 405                     appendRun();
 406                 }
 407             } else if (m_status.eor == U_ARABIC_NUMBER) {
 408                 m_direction = U_ARABIC_NUMBER;
 409                 appendRun();
 410             } else if (m_status.lastStrong != U_LEFT_TO_RIGHT && from == U_LEFT_TO_RIGHT) {
 411                 appendRun();
 412                 m_direction = U_LEFT_TO_RIGHT;
 413             }
 414         } else if (m_status.eor == U_ARABIC_NUMBER
 415             || (m_status.eor == U_EUROPEAN_NUMBER && (m_status.lastStrong != U_LEFT_TO_RIGHT || from == U_RIGHT_TO_LEFT))
 416             || (m_status.eor != U_EUROPEAN_NUMBER && m_status.lastStrong == U_LEFT_TO_RIGHT && from == U_RIGHT_TO_LEFT)) {
 417             appendRun();
 418             m_direction = U_RIGHT_TO_LEFT;
 419         }
 420         m_eor = m_last;
 421     }
 422
 423     appendRun();
 424     m_emptyRun = true;
 425
 426     setLastDir(to);
 427     setLastStrongDir(to);
 428     m_eor = Iterator();
 429 }
 430
 431 template <class Iterator, class Run>
 432 bool BidiResolver<Iterator, Run>::commitExplicitEmbedding()
 433 {
 434     // When we're "inIsolate()" we're resolving the parent context which
 435     // ignores (skips over) the isolated content, including embedding levels.
 436     // We should never accrue embedding levels while skipping over isolated content.
 437     ASSERT(!inIsolate() || m_currentExplicitEmbeddingSequence.isEmpty());
 438
 439     unsigned char fromLevel = context()->level();
 440     RefPtr<BidiContext> toContext = context();
 441
 442     for (size_t i = 0; i < m_currentExplicitEmbeddingSequence.size(); ++i) {
 443         BidiEmbedding embedding = m_currentExplicitEmbeddingSequence[i];
 444         if (embedding.direction() == U_POP_DIRECTIONAL_FORMAT) {
 445             if (BidiContext* parentContext = toContext->parent())
 446                 toContext = parentContext;
 447         } else {
 448             UCharDirection direction = (embedding.direction() == U_RIGHT_TO_LEFT_EMBEDDING || embedding.direction() == U_RIGHT_TO_LEFT_OVERRIDE) ? U_RIGHT_TO_LEFT : U_LEFT_TO_RIGHT;
 449             bool override = embedding.direction() == U_LEFT_TO_RIGHT_OVERRIDE || embedding.direction() == U_RIGHT_TO_LEFT_OVERRIDE;
 450             unsigned char level = toContext->level();
 451             if (direction == U_RIGHT_TO_LEFT)
 452                 level = nextGreaterOddLevel(level);
 453             else
 454                 level = nextGreaterEvenLevel(level);
 455             if (level < 61)
 456                 toContext = BidiContext::create(level, direction, override, embedding.source(), toContext.get());
 457         }
 458     }
 459
 460     unsigned char toLevel = toContext->level();
 461
 462     if (toLevel > fromLevel)
 463         raiseExplicitEmbeddingLevel(fromLevel % 2 ? U_RIGHT_TO_LEFT : U_LEFT_TO_RIGHT, toLevel % 2 ? U_RIGHT_TO_LEFT : U_LEFT_TO_RIGHT);
 464     else if (toLevel < fromLevel)
 465         lowerExplicitEmbeddingLevel(fromLevel % 2 ? U_RIGHT_TO_LEFT : U_LEFT_TO_RIGHT);
 466
 467     setContext(toContext);
 468
 469     m_currentExplicitEmbeddingSequence.clear();
 470
 471     return fromLevel != toLevel;
 472 }
 473
 474 template <class Iterator, class Run>
 475 inline void BidiResolver<Iterator, Run>::updateStatusLastFromCurrentDirection(UCharDirection dirCurrent)
 476 {
 477     switch (dirCurrent) {
 478     case U_EUROPEAN_NUMBER_TERMINATOR:
 479         if (m_status.last != U_EUROPEAN_NUMBER)
 480             m_status.last = U_EUROPEAN_NUMBER_TERMINATOR;
 481         break;
 482     case U_EUROPEAN_NUMBER_SEPARATOR:
 483     case U_COMMON_NUMBER_SEPARATOR:
 484     case U_SEGMENT_SEPARATOR:
 485     case U_WHITE_SPACE_NEUTRAL:
 486     case U_OTHER_NEUTRAL:
 487         switch (m_status.last) {
 488         case U_LEFT_TO_RIGHT:
 489         case U_RIGHT_TO_LEFT:
 490         case U_RIGHT_TO_LEFT_ARABIC:
 491         case U_EUROPEAN_NUMBER:
 492         case U_ARABIC_NUMBER:
 493             m_status.last = dirCurrent;
 494             break;
 495         default:
 496             m_status.last = U_OTHER_NEUTRAL;
 497         }
 498         break;
 499     case U_DIR_NON_SPACING_MARK:
 500     case U_BOUNDARY_NEUTRAL:
 501     case U_RIGHT_TO_LEFT_EMBEDDING:
 502     case U_LEFT_TO_RIGHT_EMBEDDING:
 503     case U_RIGHT_TO_LEFT_OVERRIDE:
 504     case U_LEFT_TO_RIGHT_OVERRIDE:
 505     case U_POP_DIRECTIONAL_FORMAT:
 506         // ignore these
 507         break;
 508     case U_EUROPEAN_NUMBER:
 509         // fall through
 510     default:
 511         m_status.last = dirCurrent;
 512     }
 513 }
 514
 515 template <class Iterator, class Run>
 516 inline void BidiResolver<Iterator, Run>::reorderRunsFromLevels()
 517 {
 518     unsigned char levelLow = 128;
 519     unsigned char levelHigh = 0;
 520     for (Run* run = m_runs.firstRun(); run; run = run->next()) {
 521         levelHigh = std::max(run->level(), levelHigh);
 522         levelLow = std::min(run->level(), levelLow);
 523     }
 524
 525     // This implements reordering of the line (L2 according to Bidi spec):
 526     // http://unicode.org/reports/tr9/#L2
 527     // L2. From the highest level found in the text to the lowest odd level on each line,
 528     // reverse any contiguous sequence of characters that are at that level or higher.
 529
 530     // Reversing is only done up to the lowest odd level.
 531     if (!(levelLow % 2))
 532         levelLow++;
 533
 534     unsigned count = m_runs.runCount() - 1;
 535
 536     while (levelHigh >= levelLow) {
 537         unsigned i = 0;
 538         Run* run = m_runs.firstRun();
 539         while (i < count) {
 540             for (;i < count && run && run->level() < levelHigh; i++)
 541                 run = run->next();
 542             unsigned start = i;
 543             for (;i <= count && run && run->level() >= levelHigh; i++)
 544                 run = run->next();
 545             unsigned end = i - 1;
 546             m_runs.reverseRuns(start, end);
 547         }
 548         levelHigh--;
 549     }
 550 }
 551
 552 template <class Iterator, class Run>
 553 void BidiResolver<Iterator, Run>::createBidiRunsForLine(const Iterator& end, VisualDirectionOverride override, bool hardLineBreak)
 554 {
 555     ASSERT(m_direction == U_OTHER_NEUTRAL);
 556
 557     if (override != NoVisualOverride) {
 558         m_emptyRun = false;
 559         m_sor = m_current;
 560         m_eor = Iterator();
 561         while (m_current != end && !m_current.atEnd()) {
 562             m_eor = m_current;
 563             increment();
 564         }
 565         m_direction = override == VisualLeftToRightOverride ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
 566         appendRun();
 567         m_runs.setLogicallyLastRun(m_runs.lastRun());
 568         if (override == VisualRightToLeftOverride && m_runs.runCount())
 569             m_runs.reverseRuns(0, m_runs.runCount() - 1);
 570         return;
 571     }
 572
 573     m_emptyRun = true;
 574
 575     m_eor = Iterator();
 576
 577     m_last = m_current;
 578     bool pastEnd = false;
 579     BidiResolver<Iterator, Run> stateAtEnd;
 580
 581     while (true) {
 582         UCharDirection dirCurrent;
 583         if (pastEnd && (hardLineBreak || m_current.atEnd())) {
 584             BidiContext* c = context();
 585             if (hardLineBreak) {
 586                 // A deviation from the Unicode Bidi Algorithm in order to match
 587                 // WinIE and user expectations: hard line breaks reset bidi state
 588                 // coming from unicode bidi control characters, but not those from
 589                 // DOM nodes with specified directionality
 590                 stateAtEnd.setContext(c->copyStackRemovingUnicodeEmbeddingContexts());
 591
 592                 dirCurrent = stateAtEnd.context()->dir();
 593                 stateAtEnd.setEorDir(dirCurrent);
 594                 stateAtEnd.setLastDir(dirCurrent);
 595                 stateAtEnd.setLastStrongDir(dirCurrent);
 596             } else {
 597                 while (c->parent())
 598                     c = c->parent();
 599                 dirCurrent = c->dir();
 600             }
 601         } else {
 602             dirCurrent = m_current.direction();
 603             if (context()->override()
 604                     && dirCurrent != U_RIGHT_TO_LEFT_EMBEDDING
 605                     && dirCurrent != U_LEFT_TO_RIGHT_EMBEDDING
 606                     && dirCurrent != U_RIGHT_TO_LEFT_OVERRIDE
 607                     && dirCurrent != U_LEFT_TO_RIGHT_OVERRIDE
 608                     && dirCurrent != U_POP_DIRECTIONAL_FORMAT)
 609                 dirCurrent = context()->dir();
 610             else if (dirCurrent == U_DIR_NON_SPACING_MARK)
 611                 dirCurrent = m_status.last;
 612         }
 613
 614         // We ignore all character directionality while in unicode-bidi: isolate spans.
 615         // We'll handle ordering the isolated characters in a second pass.
 616         if (inIsolate())
 617             dirCurrent = U_OTHER_NEUTRAL;
 618
 619         ASSERT(m_status.eor != U_OTHER_NEUTRAL || m_eor.atEnd());
 620         switch (dirCurrent) {
 621
 622         // embedding and overrides (X1-X9 in the Bidi specs)
 623         case U_RIGHT_TO_LEFT_EMBEDDING:
 624         case U_LEFT_TO_RIGHT_EMBEDDING:
 625         case U_RIGHT_TO_LEFT_OVERRIDE:
 626         case U_LEFT_TO_RIGHT_OVERRIDE:
 627         case U_POP_DIRECTIONAL_FORMAT:
 628             embed(dirCurrent, FromUnicode);
 629             commitExplicitEmbedding();
 630             break;
 631
 632         // strong types
 633         case U_LEFT_TO_RIGHT:
 634             switch(m_status.last) {
 635                 case U_RIGHT_TO_LEFT:
 636                 case U_RIGHT_TO_LEFT_ARABIC:
 637                 case U_EUROPEAN_NUMBER:
 638                 case U_ARABIC_NUMBER:
 639                     if (m_status.last != U_EUROPEAN_NUMBER || m_status.lastStrong != U_LEFT_TO_RIGHT)
 640                         appendRun();
 641                     break;
 642                 case U_LEFT_TO_RIGHT:
 643                     break;
 644                 case U_EUROPEAN_NUMBER_SEPARATOR:
 645                 case U_EUROPEAN_NUMBER_TERMINATOR:
 646                 case U_COMMON_NUMBER_SEPARATOR:
 647                 case U_BOUNDARY_NEUTRAL:
 648                 case U_BLOCK_SEPARATOR:
 649                 case U_SEGMENT_SEPARATOR:
 650                 case U_WHITE_SPACE_NEUTRAL:
 651                 case U_OTHER_NEUTRAL:
 652                     if (m_status.eor == U_EUROPEAN_NUMBER) {
 653                         if (m_status.lastStrong != U_LEFT_TO_RIGHT) {
 654                             // the numbers need to be on a higher embedding level, so let's close that run
 655                             m_direction = U_EUROPEAN_NUMBER;
 656                             appendRun();
 657                             if (context()->dir() != U_LEFT_TO_RIGHT) {
 658                                 // the neutrals take the embedding direction, which is R
 659                                 m_eor = m_last;
 660                                 m_direction = U_RIGHT_TO_LEFT;
 661                                 appendRun();
 662                             }
 663                         }
 664                     } else if (m_status.eor == U_ARABIC_NUMBER) {
 665                         // Arabic numbers are always on a higher embedding level, so let's close that run
 666                         m_direction = U_ARABIC_NUMBER;
 667                         appendRun();
 668                         if (context()->dir() != U_LEFT_TO_RIGHT) {
 669                             // the neutrals take the embedding direction, which is R
 670                             m_eor = m_last;
 671                             m_direction = U_RIGHT_TO_LEFT;
 672                             appendRun();
 673                         }
 674                     } else if (m_status.lastStrong != U_LEFT_TO_RIGHT) {
 675                         //last stuff takes embedding dir
 676                         if (context()->dir() == U_RIGHT_TO_LEFT) {
 677                             m_eor = m_last;
 678                             m_direction = U_RIGHT_TO_LEFT;
 679                         }
 680                         appendRun();
 681                     }
 682                 default:
 683                     break;
 684             }
 685             m_eor = m_current;
 686             m_status.eor = U_LEFT_TO_RIGHT;
 687             m_status.lastStrong = U_LEFT_TO_RIGHT;
 688             m_direction = U_LEFT_TO_RIGHT;
 689             break;
 690         case U_RIGHT_TO_LEFT_ARABIC:
 691         case U_RIGHT_TO_LEFT:
 692             switch (m_status.last) {
 693                 case U_LEFT_TO_RIGHT:
 694                 case U_EUROPEAN_NUMBER:
 695                 case U_ARABIC_NUMBER:
 696                     appendRun();
 697                 case U_RIGHT_TO_LEFT:
 698                 case U_RIGHT_TO_LEFT_ARABIC:
 699                     break;
 700                 case U_EUROPEAN_NUMBER_SEPARATOR:
 701                 case U_EUROPEAN_NUMBER_TERMINATOR:
 702                 case U_COMMON_NUMBER_SEPARATOR:
 703                 case U_BOUNDARY_NEUTRAL:
 704                 case U_BLOCK_SEPARATOR:
 705                 case U_SEGMENT_SEPARATOR:
 706                 case U_WHITE_SPACE_NEUTRAL:
 707                 case U_OTHER_NEUTRAL:
 708                     if (m_status.eor == U_EUROPEAN_NUMBER) {
 709                         if (m_status.lastStrong == U_LEFT_TO_RIGHT && context()->dir() == U_LEFT_TO_RIGHT)
 710                             m_eor = m_last;
 711                         appendRun();
 712                     } else if (m_status.eor == U_ARABIC_NUMBER)
 713                         appendRun();
 714                     else if (m_status.lastStrong == U_LEFT_TO_RIGHT) {
 715                         if (context()->dir() == U_LEFT_TO_RIGHT)
 716                             m_eor = m_last;
 717                         appendRun();
 718                     }
 719                 default:
 720                     break;
 721             }
 722             m_eor = m_current;
 723             m_status.eor = U_RIGHT_TO_LEFT;
 724             m_status.lastStrong = dirCurrent;
 725             m_direction = U_RIGHT_TO_LEFT;
 726             break;
 727
 728             // weak types:
 729
 730         case U_EUROPEAN_NUMBER:
 731             if (m_status.lastStrong != U_RIGHT_TO_LEFT_ARABIC) {
 732                 // if last strong was AL change EN to AN
 733                 switch (m_status.last) {
 734                     case U_EUROPEAN_NUMBER:
 735                     case U_LEFT_TO_RIGHT:
 736                         break;
 737                     case U_RIGHT_TO_LEFT:
 738                     case U_RIGHT_TO_LEFT_ARABIC:
 739                     case U_ARABIC_NUMBER:
 740                         m_eor = m_last;
 741                         appendRun();
 742                         m_direction = U_EUROPEAN_NUMBER;
 743                         break;
 744                     case U_EUROPEAN_NUMBER_SEPARATOR:
 745                     case U_COMMON_NUMBER_SEPARATOR:
 746                         if (m_status.eor == U_EUROPEAN_NUMBER)
 747                             break;
 748                     case U_EUROPEAN_NUMBER_TERMINATOR:
 749                     case U_BOUNDARY_NEUTRAL:
 750                     case U_BLOCK_SEPARATOR:
 751                     case U_SEGMENT_SEPARATOR:
 752                     case U_WHITE_SPACE_NEUTRAL:
 753                     case U_OTHER_NEUTRAL:
 754                         if (m_status.eor == U_EUROPEAN_NUMBER) {
 755                             if (m_status.lastStrong == U_RIGHT_TO_LEFT) {
 756                                 // ENs on both sides behave like Rs, so the neutrals should be R.
 757                                 // Terminate the EN run.
 758                                 appendRun();
 759                                 // Make an R run.
 760                                 m_eor = m_status.last == U_EUROPEAN_NUMBER_TERMINATOR ? m_lastBeforeET : m_last;
 761                                 m_direction = U_RIGHT_TO_LEFT;
 762                                 appendRun();
 763                                 // Begin a new EN run.
 764                                 m_direction = U_EUROPEAN_NUMBER;
 765                             }
 766                         } else if (m_status.eor == U_ARABIC_NUMBER) {
 767                             // Terminate the AN run.
 768                             appendRun();
 769                             if (m_status.lastStrong == U_RIGHT_TO_LEFT || context()->dir() == U_RIGHT_TO_LEFT) {
 770                                 // Make an R run.
 771                                 m_eor = m_status.last == U_EUROPEAN_NUMBER_TERMINATOR ? m_lastBeforeET : m_last;
 772                                 m_direction = U_RIGHT_TO_LEFT;
 773                                 appendRun();
 774                                 // Begin a new EN run.
 775                                 m_direction = U_EUROPEAN_NUMBER;
 776                             }
 777                         } else if (m_status.lastStrong == U_RIGHT_TO_LEFT) {
 778                             // Extend the R run to include the neutrals.
 779                             m_eor = m_status.last == U_EUROPEAN_NUMBER_TERMINATOR ? m_lastBeforeET : m_last;
 780                             m_direction = U_RIGHT_TO_LEFT;
 781                             appendRun();
 782                             // Begin a new EN run.
 783                             m_direction = U_EUROPEAN_NUMBER;
 784                         }
 785                     default:
 786                         break;
 787                 }
 788                 m_eor = m_current;
 789                 m_status.eor = U_EUROPEAN_NUMBER;
 790                 if (m_direction == U_OTHER_NEUTRAL)
 791                     m_direction = U_LEFT_TO_RIGHT;
 792                 break;
 793             }
 794         case U_ARABIC_NUMBER:
 795             dirCurrent = U_ARABIC_NUMBER;
 796             switch (m_status.last) {
 797                 case U_LEFT_TO_RIGHT:
 798                     if (context()->dir() == U_LEFT_TO_RIGHT)
 799                         appendRun();
 800                     break;
 801                 case U_ARABIC_NUMBER:
 802                     break;
 803                 case U_RIGHT_TO_LEFT:
 804                 case U_RIGHT_TO_LEFT_ARABIC:
 805                 case U_EUROPEAN_NUMBER:
 806                     m_eor = m_last;
 807                     appendRun();
 808                     break;
 809                 case U_COMMON_NUMBER_SEPARATOR:
 810                     if (m_status.eor == U_ARABIC_NUMBER)
 811                         break;
 812                 case U_EUROPEAN_NUMBER_SEPARATOR:
 813                 case U_EUROPEAN_NUMBER_TERMINATOR:
 814                 case U_BOUNDARY_NEUTRAL:
 815                 case U_BLOCK_SEPARATOR:
 816                 case U_SEGMENT_SEPARATOR:
 817                 case U_WHITE_SPACE_NEUTRAL:
 818                 case U_OTHER_NEUTRAL:
 819                     if (m_status.eor == U_ARABIC_NUMBER
 820                         || (m_status.eor == U_EUROPEAN_NUMBER && (m_status.lastStrong == U_RIGHT_TO_LEFT || context()->dir() == U_RIGHT_TO_LEFT))
 821                         || (m_status.eor != U_EUROPEAN_NUMBER && m_status.lastStrong == U_LEFT_TO_RIGHT && context()->dir() == U_RIGHT_TO_LEFT)) {
 822                         // Terminate the run before the neutrals.
 823                         appendRun();
 824                         // Begin an R run for the neutrals.
 825                         m_direction = U_RIGHT_TO_LEFT;
 826                     } else if (m_direction == U_OTHER_NEUTRAL)
 827                         m_direction = m_status.lastStrong == U_LEFT_TO_RIGHT ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
 828                     m_eor = m_last;
 829                     appendRun();
 830                 default:
 831                     break;
 832             }
 833             m_eor = m_current;
 834             m_status.eor = U_ARABIC_NUMBER;
 835             if (m_direction == U_OTHER_NEUTRAL)
 836                 m_direction = U_ARABIC_NUMBER;
 837             break;
 838         case U_EUROPEAN_NUMBER_SEPARATOR:
 839         case U_COMMON_NUMBER_SEPARATOR:
 840             break;
 841         case U_EUROPEAN_NUMBER_TERMINATOR:
 842             if (m_status.last == U_EUROPEAN_NUMBER) {
 843                 dirCurrent = U_EUROPEAN_NUMBER;
 844                 m_eor = m_current;
 845                 m_status.eor = dirCurrent;
 846             } else if (m_status.last != U_EUROPEAN_NUMBER_TERMINATOR)
 847                 m_lastBeforeET = m_emptyRun ? m_eor : m_last;
 848             break;
 849
 850         // boundary neutrals should be ignored
 851         case U_BOUNDARY_NEUTRAL:
 852             if (m_eor == m_last)
 853                 m_eor = m_current;
 854             break;
 855             // neutrals
 856         case U_BLOCK_SEPARATOR:
 857             // FIXME: What do we do with newline and paragraph separators that come to here?
 858             break;
 859         case U_SEGMENT_SEPARATOR:
 860             // FIXME: Implement rule L1.
 861             break;
 862         case U_WHITE_SPACE_NEUTRAL:
 863             break;
 864         case U_OTHER_NEUTRAL:
 865             break;
 866         default:
 867             break;
 868         }
 869
 870         if (pastEnd && m_eor == m_current) {
 871             if (!m_reachedEndOfLine) {
 872                 m_eor = endOfLine;
 873                 switch (m_status.eor) {
 874                     case U_LEFT_TO_RIGHT:
 875                     case U_RIGHT_TO_LEFT:
 876                     case U_ARABIC_NUMBER:
 877                         m_direction = m_status.eor;
 878                         break;
 879                     case U_EUROPEAN_NUMBER:
 880                         m_direction = m_status.lastStrong == U_LEFT_TO_RIGHT ? U_LEFT_TO_RIGHT : U_EUROPEAN_NUMBER;
 881                         break;
 882                     default:
 883                         ASSERT_NOT_REACHED();
 884                 }
 885                 appendRun();
 886             }
 887             m_current = end;
 888             m_status = stateAtEnd.m_status;
 889             m_sor = stateAtEnd.m_sor;
 890             m_eor = stateAtEnd.m_eor;
 891             m_last = stateAtEnd.m_last;
 892             m_reachedEndOfLine = stateAtEnd.m_reachedEndOfLine;
 893             m_lastBeforeET = stateAtEnd.m_lastBeforeET;
 894             m_emptyRun = stateAtEnd.m_emptyRun;
 895             m_direction = U_OTHER_NEUTRAL;
 896             break;
 897         }
 898
 899         updateStatusLastFromCurrentDirection(dirCurrent);
 900         m_last = m_current;
 901
 902         if (m_emptyRun) {
 903             m_sor = m_current;
 904             m_emptyRun = false;
 905         }
 906
 907         increment();
 908         if (!m_currentExplicitEmbeddingSequence.isEmpty()) {
 909             bool committed = commitExplicitEmbedding();
 910             if (committed && pastEnd) {
 911                 m_current = end;
 912                 m_status = stateAtEnd.m_status;
 913                 m_sor = stateAtEnd.m_sor;
 914                 m_eor = stateAtEnd.m_eor;
 915                 m_last = stateAtEnd.m_last;
 916                 m_reachedEndOfLine = stateAtEnd.m_reachedEndOfLine;
 917                 m_lastBeforeET = stateAtEnd.m_lastBeforeET;
 918                 m_emptyRun = stateAtEnd.m_emptyRun;
 919                 m_direction = U_OTHER_NEUTRAL;
 920                 break;
 921             }
 922         }
 923
 924         if (!pastEnd && (m_current == end || m_current.atEnd())) {
 925             if (m_emptyRun)
 926                 break;
 927             stateAtEnd.m_status = m_status;
 928             stateAtEnd.m_sor = m_sor;
 929             stateAtEnd.m_eor = m_eor;
 930             stateAtEnd.m_last = m_last;
 931             stateAtEnd.m_reachedEndOfLine = m_reachedEndOfLine;
 932             stateAtEnd.m_lastBeforeET = m_lastBeforeET;
 933             stateAtEnd.m_emptyRun = m_emptyRun;
 934             endOfLine = m_last;
 935             pastEnd = true;
 936         }
 937     }
 938
 939     m_runs.setLogicallyLastRun(m_runs.lastRun());
 940     reorderRunsFromLevels();
 941     endOfLine = Iterator();
 942 }
 943
 944 } // namespace WebCore
 945
 946 #endif // BidiResolver_h