src/third_party/WebKit/Source/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 "platform/text/BidiCharacterRun.h"
  26 #include "platform/text/BidiContext.h"
  27 #include "platform/text/BidiRunList.h"
  28 #include "platform/text/TextDirection.h"
  29 #include "wtf/HashMap.h"
  30 #include "wtf/Noncopyable.h"
  31 #include "wtf/PassRefPtr.h"
  32 #include "wtf/Vector.h"
  33
  34 namespace WebCore {
  35
  36 class RenderObject;
  37
  38 template <class Iterator> class MidpointState {
  39 public:
  40     MidpointState()
  41     {
  42         reset();
  43     }
  44
  45     void reset()
  46     {
  47         m_numMidpoints = 0;
  48         m_currentMidpoint = 0;
  49         m_betweenMidpoints = false;
  50     }
  51
  52     void startIgnoringSpaces(const Iterator& midpoint)
  53     {
  54         ASSERT(!(m_numMidpoints % 2));
  55         addMidpoint(midpoint);
  56     }
  57
  58     void stopIgnoringSpaces(const Iterator& midpoint)
  59     {
  60         ASSERT(m_numMidpoints % 2);
  61         addMidpoint(midpoint);
  62     }
  63
  64     // When ignoring spaces, this needs to be called for objects that need line boxes such as RenderInlines or
  65     // hard line breaks to ensure that they're not ignored.
  66     void ensureLineBoxInsideIgnoredSpaces(RenderObject* renderer)
  67     {
  68         Iterator midpoint(0, renderer, 0);
  69         stopIgnoringSpaces(midpoint);
  70         startIgnoringSpaces(midpoint);
  71     }
  72
  73     // Adding a pair of midpoints before a character will split it out into a new line box.
  74     void ensureCharacterGetsLineBox(Iterator& textParagraphSeparator)
  75     {
  76         Iterator midpoint(0, textParagraphSeparator.object(), textParagraphSeparator.offset());
  77         startIgnoringSpaces(Iterator(0, textParagraphSeparator.object(), textParagraphSeparator.offset() - 1));
  78         stopIgnoringSpaces(Iterator(0, textParagraphSeparator.object(), textParagraphSeparator.offset()));
  79     }
  80
  81     void checkMidpoints(Iterator& lBreak)
  82     {
  83         // Check to see if our last midpoint is a start point beyond the line break. If so,
  84         // shave it off the list, and shave off a trailing space if the previous end point doesn't
  85         // preserve whitespace.
  86         if (lBreak.object() && m_numMidpoints && !(m_numMidpoints % 2)) {
  87             Iterator* midpointsIterator = m_midpoints.data();
  88             Iterator& endpoint = midpointsIterator[m_numMidpoints - 2];
  89             const Iterator& startpoint = midpointsIterator[m_numMidpoints - 1];
  90             Iterator currpoint = endpoint;
  91             while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)
  92                 currpoint.increment();
  93             if (currpoint == lBreak) {
  94                 // We hit the line break before the start point. Shave off the start point.
  95                 m_numMidpoints--;
  96                 if (endpoint.object()->style()->collapseWhiteSpace() && endpoint.object()->isText())
  97                     endpoint.setOffset(endpoint.offset() - 1);
  98             }
  99         }
 100     }
 101
 102     Vector<Iterator>& midpoints() { return m_midpoints; }
 103     const unsigned& numMidpoints() const { return m_numMidpoints; }
 104     const unsigned& currentMidpoint() const { return m_currentMidpoint; }
 105     void incrementCurrentMidpoint() { m_currentMidpoint++; }
 106     const bool& betweenMidpoints() const { return m_betweenMidpoints; }
 107     void setBetweenMidpoints(bool betweenMidpoint) { m_betweenMidpoints = betweenMidpoint; }
 108 private:
 109     // The goal is to reuse the line state across multiple
 110     // lines so we just keep an array around for midpoints and never clear it across multiple
 111     // lines. We track the number of items and position using the two other variables.
 112     Vector<Iterator> m_midpoints;
 113     unsigned m_numMidpoints;
 114     unsigned m_currentMidpoint;
 115     bool m_betweenMidpoints;
 116
 117     void addMidpoint(const Iterator& midpoint)
 118     {
 119         if (m_midpoints.size() <= m_numMidpoints)
 120             m_midpoints.grow(m_numMidpoints + 10);
 121
 122         Iterator* midpointsIterator = m_midpoints.data();
 123         midpointsIterator[m_numMidpoints++] = midpoint;
 124     }
 125 };
 126
 127 // The BidiStatus at a given position (typically the end of a line) can
 128 // be cached and then used to restart bidi resolution at that position.
 129 struct BidiStatus {
 130     BidiStatus()
 131         : eor(WTF::Unicode::OtherNeutral)
 132         , lastStrong(WTF::Unicode::OtherNeutral)
 133         , last(WTF::Unicode::OtherNeutral)
 134     {
 135     }
 136
 137     // Creates a BidiStatus representing a new paragraph root with a default direction.
 138     // Uses TextDirection as it only has two possibilities instead of WTF::Unicode::Direction which has 19.
 139     BidiStatus(TextDirection textDirection, bool isOverride)
 140     {
 141         WTF::Unicode::Direction direction = textDirection == LTR ? WTF::Unicode::LeftToRight : WTF::Unicode::RightToLeft;
 142         eor = lastStrong = last = direction;
 143         context = BidiContext::create(textDirection == LTR ? 0 : 1, direction, isOverride);
 144     }
 145
 146     BidiStatus(WTF::Unicode::Direction eorDir, WTF::Unicode::Direction lastStrongDir, WTF::Unicode::Direction lastDir, PassRefPtr<BidiContext> bidiContext)
 147         : eor(eorDir)
 148         , lastStrong(lastStrongDir)
 149         , last(lastDir)
 150         , context(bidiContext)
 151     {
 152     }
 153
 154     WTF::Unicode::Direction eor;
 155     WTF::Unicode::Direction lastStrong;
 156     WTF::Unicode::Direction last;
 157     RefPtr<BidiContext> context;
 158 };
 159
 160 class BidiEmbedding {
 161 public:
 162     BidiEmbedding(WTF::Unicode::Direction direction, BidiEmbeddingSource source)
 163     : m_direction(direction)
 164     , m_source(source)
 165     {
 166     }
 167
 168     WTF::Unicode::Direction direction() const { return m_direction; }
 169     BidiEmbeddingSource source() const { return m_source; }
 170 private:
 171     WTF::Unicode::Direction m_direction;
 172     BidiEmbeddingSource m_source;
 173 };
 174
 175 inline bool operator==(const BidiStatus& status1, const BidiStatus& status2)
 176 {
 177     return status1.eor == status2.eor && status1.last == status2.last && status1.lastStrong == status2.lastStrong && *(status1.context) == *(status2.context);
 178 }
 179
 180 inline bool operator!=(const BidiStatus& status1, const BidiStatus& status2)
 181 {
 182     return !(status1 == status2);
 183 }
 184
 185 enum VisualDirectionOverride {
 186     NoVisualOverride,
 187     VisualLeftToRightOverride,
 188     VisualRightToLeftOverride
 189 };
 190
 191 // BidiResolver is WebKit's implementation of the Unicode Bidi Algorithm
 192 // http://unicode.org/reports/tr9
 193 template <class Iterator, class Run> class BidiResolver {
 194     WTF_MAKE_NONCOPYABLE(BidiResolver);
 195 public:
 196     BidiResolver()
 197         : m_direction(WTF::Unicode::OtherNeutral)
 198         , m_reachedEndOfLine(false)
 199         , m_emptyRun(true)
 200         , m_nestedIsolateCount(0)
 201         , m_trailingSpaceRun(0)
 202     {
 203     }
 204
 205 #ifndef NDEBUG
 206     ~BidiResolver();
 207 #endif
 208
 209     const Iterator& position() const { return m_current; }
 210     Iterator& position() { return m_current; }
 211     void setPositionIgnoringNestedIsolates(const Iterator& position) { m_current = position; }
 212     void setPosition(const Iterator& position, unsigned nestedIsolatedCount)
 213     {
 214         m_current = position;
 215         m_nestedIsolateCount = nestedIsolatedCount;
 216     }
 217
 218     BidiContext* context() const { return m_status.context.get(); }
 219     void setContext(PassRefPtr<BidiContext> c) { m_status.context = c; }
 220
 221     void setLastDir(WTF::Unicode::Direction lastDir) { m_status.last = lastDir; }
 222     void setLastStrongDir(WTF::Unicode::Direction lastStrongDir) { m_status.lastStrong = lastStrongDir; }
 223     void setEorDir(WTF::Unicode::Direction eorDir) { m_status.eor = eorDir; }
 224
 225     WTF::Unicode::Direction dir() const { return m_direction; }
 226     void setDir(WTF::Unicode::Direction d) { m_direction = d; }
 227
 228     const BidiStatus& status() const { return m_status; }
 229     void setStatus(const BidiStatus s)
 230     {
 231         ASSERT(s.context);
 232         m_status = s;
 233         m_paragraphDirectionality = s.context->dir() == WTF::Unicode::LeftToRight ? LTR : RTL;
 234     }
 235
 236     MidpointState<Iterator>& midpointState() { return m_midpointState; }
 237
 238     // The current algorithm handles nested isolates one layer of nesting at a time.
 239     // But when we layout each isolated span, we will walk into (and ignore) all
 240     // child isolated spans.
 241     void enterIsolate() { m_nestedIsolateCount++; }
 242     void exitIsolate() { ASSERT(m_nestedIsolateCount >= 1); m_nestedIsolateCount--; }
 243     bool inIsolate() const { return m_nestedIsolateCount; }
 244
 245     void embed(WTF::Unicode::Direction, BidiEmbeddingSource);
 246     bool commitExplicitEmbedding();
 247
 248     void createBidiRunsForLine(const Iterator& end, VisualDirectionOverride = NoVisualOverride, bool hardLineBreak = false, bool reorderRuns = true);
 249
 250     BidiRunList<Run>& runs() { return m_runs; }
 251
 252     // FIXME: This used to be part of deleteRuns() but was a layering violation.
 253     // It's unclear if this is still needed.
 254     void markCurrentRunEmpty() { m_emptyRun = true; }
 255
 256     Vector<Run*>& isolatedRuns() { return m_isolatedRuns; }
 257
 258     bool isEndOfLine(const Iterator& end) { return m_current == end || m_current.atEnd(); }
 259
 260     TextDirection determineParagraphDirectionality(bool* hasStrongDirectionality = 0);
 261
 262     void setMidpointStateForIsolatedRun(Run*, const MidpointState<Iterator>&);
 263     MidpointState<Iterator> midpointStateForIsolatedRun(Run*);
 264
 265     Iterator endOfLine() const { return m_endOfLine; }
 266
 267     Run* trailingSpaceRun() const { return m_trailingSpaceRun; }
 268
 269 protected:
 270     void increment() { m_current.increment(); }
 271     // FIXME: Instead of InlineBidiResolvers subclassing this method, we should
 272     // pass in some sort of Traits object which knows how to create runs for appending.
 273     void appendRun();
 274
 275     Run* addTrailingRun(int, int, Run*, BidiContext*, TextDirection) { return 0; }
 276     Iterator m_current;
 277     // sor and eor are "start of run" and "end of run" respectively and correpond
 278     // to abreviations used in UBA spec: http://unicode.org/reports/tr9/#BD7
 279     Iterator m_sor; // Points to the first character in the current run.
 280     Iterator m_eor; // Points to the last character in the current run.
 281     Iterator m_last;
 282     BidiStatus m_status;
 283     WTF::Unicode::Direction m_direction;
 284     // m_endOfRunAtEndOfLine is "the position last eor in the end of line"
 285     Iterator m_endOfRunAtEndOfLine;
 286     Iterator m_endOfLine;
 287     bool m_reachedEndOfLine;
 288     Iterator m_lastBeforeET; // Before a EuropeanNumberTerminator
 289     bool m_emptyRun;
 290
 291     // FIXME: This should not belong to the resolver, but rather be passed
 292     // into createBidiRunsForLine by the caller.
 293     BidiRunList<Run> m_runs;
 294
 295     MidpointState<Iterator> m_midpointState;
 296
 297     unsigned m_nestedIsolateCount;
 298     Vector<Run*> m_isolatedRuns;
 299     Run* m_trailingSpaceRun;
 300     TextDirection m_paragraphDirectionality;
 301
 302 private:
 303     void raiseExplicitEmbeddingLevel(WTF::Unicode::Direction from, WTF::Unicode::Direction to);
 304     void lowerExplicitEmbeddingLevel(WTF::Unicode::Direction from);
 305     void checkDirectionInLowerRaiseEmbeddingLevel();
 306
 307     void updateStatusLastFromCurrentDirection(WTF::Unicode::Direction);
 308     void reorderRunsFromLevels();
 309
 310     bool needsToApplyL1Rule() { return false; }
 311     int findFirstTrailingSpaceAtRun(Run*) { return 0; }
 312     // http://www.unicode.org/reports/tr9/#L1
 313     void applyL1Rule();
 314
 315     Vector<BidiEmbedding, 8> m_currentExplicitEmbeddingSequence;
 316     HashMap<Run *, MidpointState<Iterator> > m_midpointStateForIsolatedRun;
 317 };
 318
 319 #ifndef NDEBUG
 320 template <class Iterator, class Run>
 321 BidiResolver<Iterator, Run>::~BidiResolver()
 322 {
 323     // The owner of this resolver should have handled the isolated runs.
 324     ASSERT(m_isolatedRuns.isEmpty());
 325 }
 326 #endif
 327
 328 template <class Iterator, class Run>
 329 void BidiResolver<Iterator, Run>::appendRun()
 330 {
 331     if (!m_emptyRun && !m_eor.atEnd()) {
 332         unsigned startOffset = m_sor.offset();
 333         unsigned endOffset = m_eor.offset();
 334
 335         if (!m_endOfRunAtEndOfLine.atEnd() && endOffset >= m_endOfRunAtEndOfLine.offset()) {
 336             m_reachedEndOfLine = true;
 337             endOffset = m_endOfRunAtEndOfLine.offset();
 338         }
 339
 340         if (endOffset >= startOffset)
 341             m_runs.addRun(new Run(startOffset, endOffset + 1, context(), m_direction));
 342
 343         m_eor.increment();
 344         m_sor = m_eor;
 345     }
 346
 347     m_direction = WTF::Unicode::OtherNeutral;
 348     m_status.eor = WTF::Unicode::OtherNeutral;
 349 }
 350
 351 template <class Iterator, class Run>
 352 void BidiResolver<Iterator, Run>::embed(WTF::Unicode::Direction dir, BidiEmbeddingSource source)
 353 {
 354     // Isolated spans compute base directionality during their own UBA run.
 355     // Do not insert fake embed characters once we enter an isolated span.
 356     ASSERT(!inIsolate());
 357     using namespace WTF::Unicode;
 358
 359     ASSERT(dir == PopDirectionalFormat || dir == LeftToRightEmbedding || dir == LeftToRightOverride || dir == RightToLeftEmbedding || dir == RightToLeftOverride);
 360     m_currentExplicitEmbeddingSequence.append(BidiEmbedding(dir, source));
 361 }
 362
 363 template <class Iterator, class Run>
 364 void BidiResolver<Iterator, Run>::checkDirectionInLowerRaiseEmbeddingLevel()
 365 {
 366     using namespace WTF::Unicode;
 367
 368     ASSERT(m_status.eor != OtherNeutral || m_eor.atEnd());
 369     ASSERT(m_status.last != NonSpacingMark
 370         && m_status.last != BoundaryNeutral
 371         && m_status.last != RightToLeftEmbedding
 372         && m_status.last != LeftToRightEmbedding
 373         && m_status.last != RightToLeftOverride
 374         && m_status.last != LeftToRightOverride
 375         && m_status.last != PopDirectionalFormat);
 376     if (m_direction == OtherNeutral)
 377         m_direction = m_status.lastStrong == LeftToRight ? LeftToRight : RightToLeft;
 378 }
 379
 380 template <class Iterator, class Run>
 381 void BidiResolver<Iterator, Run>::lowerExplicitEmbeddingLevel(WTF::Unicode::Direction from)
 382 {
 383     using namespace WTF::Unicode;
 384
 385     if (!m_emptyRun && m_eor != m_last) {
 386         checkDirectionInLowerRaiseEmbeddingLevel();
 387         // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
 388         if (from == LeftToRight) {
 389             // bidi.sor ... bidi.eor ... bidi.last L
 390             if (m_status.eor == EuropeanNumber) {
 391                 if (m_status.lastStrong != LeftToRight) {
 392                     m_direction = EuropeanNumber;
 393                     appendRun();
 394                 }
 395             } else if (m_status.eor == ArabicNumber) {
 396                 m_direction = ArabicNumber;
 397                 appendRun();
 398             } else if (m_status.lastStrong != LeftToRight) {
 399                 appendRun();
 400                 m_direction = LeftToRight;
 401             }
 402         } else if (m_status.eor == EuropeanNumber || m_status.eor == ArabicNumber || m_status.lastStrong == LeftToRight) {
 403             appendRun();
 404             m_direction = RightToLeft;
 405         }
 406         m_eor = m_last;
 407     }
 408
 409     appendRun();
 410     m_emptyRun = true;
 411
 412     // sor for the new run is determined by the higher level (rule X10)
 413     setLastDir(from);
 414     setLastStrongDir(from);
 415     m_eor = Iterator();
 416 }
 417
 418 template <class Iterator, class Run>
 419 void BidiResolver<Iterator, Run>::raiseExplicitEmbeddingLevel(WTF::Unicode::Direction from, WTF::Unicode::Direction to)
 420 {
 421     using namespace WTF::Unicode;
 422
 423     if (!m_emptyRun && m_eor != m_last) {
 424         checkDirectionInLowerRaiseEmbeddingLevel();
 425         // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
 426         if (to == LeftToRight) {
 427             // bidi.sor ... bidi.eor ... bidi.last L
 428             if (m_status.eor == EuropeanNumber) {
 429                 if (m_status.lastStrong != LeftToRight) {
 430                     m_direction = EuropeanNumber;
 431                     appendRun();
 432                 }
 433             } else if (m_status.eor == ArabicNumber) {
 434                 m_direction = ArabicNumber;
 435                 appendRun();
 436             } else if (m_status.lastStrong != LeftToRight && from == LeftToRight) {
 437                 appendRun();
 438                 m_direction = LeftToRight;
 439             }
 440         } else if (m_status.eor == ArabicNumber
 441             || (m_status.eor == EuropeanNumber && (m_status.lastStrong != LeftToRight || from == RightToLeft))
 442             || (m_status.eor != EuropeanNumber && m_status.lastStrong == LeftToRight && from == RightToLeft)) {
 443             appendRun();
 444             m_direction = RightToLeft;
 445         }
 446         m_eor = m_last;
 447     }
 448
 449     appendRun();
 450     m_emptyRun = true;
 451
 452     setLastDir(to);
 453     setLastStrongDir(to);
 454     m_eor = Iterator();
 455 }
 456
 457 template <class Iterator, class Run>
 458 void BidiResolver<Iterator, Run>::applyL1Rule()
 459 {
 460     ASSERT(m_runs.runCount());
 461     if (!needsToApplyL1Rule())
 462         return;
 463
 464     Run* trailingSpaceRun = m_runs.logicallyLastRun();
 465
 466     int firstSpace = findFirstTrailingSpaceAtRun(trailingSpaceRun);
 467     if (firstSpace == trailingSpaceRun->stop())
 468         return;
 469
 470     bool shouldReorder = trailingSpaceRun != (m_paragraphDirectionality == LTR ? m_runs.lastRun() : m_runs.firstRun());
 471     if (firstSpace != trailingSpaceRun->start()) {
 472         BidiContext* baseContext = context();
 473         while (BidiContext* parent = baseContext->parent())
 474             baseContext = parent;
 475
 476         m_trailingSpaceRun = addTrailingRun(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun, baseContext, m_paragraphDirectionality);
 477         ASSERT(m_trailingSpaceRun);
 478         trailingSpaceRun->m_stop = firstSpace;
 479         return;
 480     }
 481     if (!shouldReorder) {
 482         m_trailingSpaceRun = trailingSpaceRun;
 483         return;
 484     }
 485
 486     if (m_paragraphDirectionality == LTR) {
 487         m_runs.moveRunToEnd(trailingSpaceRun);
 488         trailingSpaceRun->m_level = 0;
 489     } else {
 490         m_runs.moveRunToBeginning(trailingSpaceRun);
 491         trailingSpaceRun->m_level = 1;
 492     }
 493     m_trailingSpaceRun = trailingSpaceRun;
 494 }
 495
 496 template <class Iterator, class Run>
 497 bool BidiResolver<Iterator, Run>::commitExplicitEmbedding()
 498 {
 499     // When we're "inIsolate()" we're resolving the parent context which
 500     // ignores (skips over) the isolated content, including embedding levels.
 501     // We should never accrue embedding levels while skipping over isolated content.
 502     ASSERT(!inIsolate() || m_currentExplicitEmbeddingSequence.isEmpty());
 503
 504     using namespace WTF::Unicode;
 505
 506     unsigned char fromLevel = context()->level();
 507     RefPtr<BidiContext> toContext = context();
 508
 509     for (size_t i = 0; i < m_currentExplicitEmbeddingSequence.size(); ++i) {
 510         BidiEmbedding embedding = m_currentExplicitEmbeddingSequence[i];
 511         if (embedding.direction() == PopDirectionalFormat) {
 512             if (BidiContext* parentContext = toContext->parent())
 513                 toContext = parentContext;
 514         } else {
 515             Direction direction = (embedding.direction() == RightToLeftEmbedding || embedding.direction() == RightToLeftOverride) ? RightToLeft : LeftToRight;
 516             bool override = embedding.direction() == LeftToRightOverride || embedding.direction() == RightToLeftOverride;
 517             unsigned char level = toContext->level();
 518             if (direction == RightToLeft)
 519                 level = nextGreaterOddLevel(level);
 520             else
 521                 level = nextGreaterEvenLevel(level);
 522             if (level < BidiContext::kMaxLevel)
 523                 toContext = BidiContext::create(level, direction, override, embedding.source(), toContext.get());
 524         }
 525     }
 526
 527     unsigned char toLevel = toContext->level();
 528
 529     if (toLevel > fromLevel)
 530         raiseExplicitEmbeddingLevel(fromLevel % 2 ? RightToLeft : LeftToRight, toLevel % 2 ? RightToLeft : LeftToRight);
 531     else if (toLevel < fromLevel)
 532         lowerExplicitEmbeddingLevel(fromLevel % 2 ? RightToLeft : LeftToRight);
 533
 534     setContext(toContext);
 535
 536     m_currentExplicitEmbeddingSequence.clear();
 537
 538     return fromLevel != toLevel;
 539 }
 540
 541 template <class Iterator, class Run>
 542 inline void BidiResolver<Iterator, Run>::updateStatusLastFromCurrentDirection(WTF::Unicode::Direction dirCurrent)
 543 {
 544     using namespace WTF::Unicode;
 545     switch (dirCurrent) {
 546     case EuropeanNumberTerminator:
 547         if (m_status.last != EuropeanNumber)
 548             m_status.last = EuropeanNumberTerminator;
 549         break;
 550     case EuropeanNumberSeparator:
 551     case CommonNumberSeparator:
 552     case SegmentSeparator:
 553     case WhiteSpaceNeutral:
 554     case OtherNeutral:
 555         switch (m_status.last) {
 556         case LeftToRight:
 557         case RightToLeft:
 558         case RightToLeftArabic:
 559         case EuropeanNumber:
 560         case ArabicNumber:
 561             m_status.last = dirCurrent;
 562             break;
 563         default:
 564             m_status.last = OtherNeutral;
 565         }
 566         break;
 567     case NonSpacingMark:
 568     case BoundaryNeutral:
 569     case RightToLeftEmbedding:
 570     case LeftToRightEmbedding:
 571     case RightToLeftOverride:
 572     case LeftToRightOverride:
 573     case PopDirectionalFormat:
 574         // ignore these
 575         break;
 576     case EuropeanNumber:
 577         // fall through
 578     default:
 579         m_status.last = dirCurrent;
 580     }
 581 }
 582
 583 template <class Iterator, class Run>
 584 inline void BidiResolver<Iterator, Run>::reorderRunsFromLevels()
 585 {
 586     unsigned char levelLow = BidiContext::kMaxLevel;
 587     unsigned char levelHigh = 0;
 588     for (Run* run = m_runs.firstRun(); run; run = run->next()) {
 589         levelHigh = std::max(run->level(), levelHigh);
 590         levelLow = std::min(run->level(), levelLow);
 591     }
 592
 593     // This implements reordering of the line (L2 according to Bidi spec):
 594     // http://unicode.org/reports/tr9/#L2
 595     // L2. From the highest level found in the text to the lowest odd level on each line,
 596     // reverse any contiguous sequence of characters that are at that level or higher.
 597
 598     // Reversing is only done up to the lowest odd level.
 599     if (!(levelLow % 2))
 600         levelLow++;
 601
 602     unsigned count = m_runs.runCount() - 1;
 603
 604     while (levelHigh >= levelLow) {
 605         unsigned i = 0;
 606         Run* run = m_runs.firstRun();
 607         while (i < count) {
 608             for (;i < count && run && run->level() < levelHigh; i++)
 609                 run = run->next();
 610             unsigned start = i;
 611             for (;i <= count && run && run->level() >= levelHigh; i++)
 612                 run = run->next();
 613             unsigned end = i - 1;
 614             m_runs.reverseRuns(start, end);
 615         }
 616         levelHigh--;
 617     }
 618 }
 619
 620 template <class Iterator, class Run>
 621 TextDirection BidiResolver<Iterator, Run>::determineParagraphDirectionality(bool* hasStrongDirectionality)
 622 {
 623     while (!m_current.atEnd()) {
 624         if (inIsolate()) {
 625             increment();
 626             continue;
 627         }
 628         if (m_current.atParagraphSeparator())
 629             break;
 630         UChar32 current = m_current.current();
 631         if (UNLIKELY(U16_IS_SURROGATE(current))) {
 632             increment();
 633             // If this not the high part of the surrogate pair, then drop it and move to the next.
 634             if (!U16_IS_SURROGATE_LEAD(current))
 635                 continue;
 636             UChar high = static_cast<UChar>(current);
 637             if (m_current.atEnd())
 638                 continue;
 639             UChar low = m_current.current();
 640             // Verify the low part. If invalid, then assume an invalid surrogate pair and retry.
 641             if (!U16_IS_TRAIL(low))
 642                 continue;
 643             current = U16_GET_SUPPLEMENTARY(high, low);
 644         }
 645         WTF::Unicode::Direction charDirection = WTF::Unicode::direction(current);
 646         if (charDirection == WTF::Unicode::LeftToRight) {
 647             if (hasStrongDirectionality)
 648                 *hasStrongDirectionality = true;
 649             return LTR;
 650         }
 651         if (charDirection == WTF::Unicode::RightToLeft || charDirection == WTF::Unicode::RightToLeftArabic) {
 652             if (hasStrongDirectionality)
 653                 *hasStrongDirectionality = true;
 654             return RTL;
 655         }
 656         increment();
 657     }
 658     if (hasStrongDirectionality)
 659         *hasStrongDirectionality = false;
 660     return LTR;
 661 }
 662
 663 template <class Iterator, class Run>
 664 void BidiResolver<Iterator, Run>::createBidiRunsForLine(const Iterator& end, VisualDirectionOverride override, bool hardLineBreak, bool reorderRuns)
 665 {
 666     using namespace WTF::Unicode;
 667
 668     ASSERT(m_direction == OtherNeutral);
 669     m_trailingSpaceRun = 0;
 670
 671     m_endOfLine = end;
 672
 673     if (override != NoVisualOverride) {
 674         m_emptyRun = false;
 675         m_sor = m_current;
 676         m_eor = Iterator();
 677         while (m_current != end && !m_current.atEnd()) {
 678             m_eor = m_current;
 679             increment();
 680         }
 681         m_direction = override == VisualLeftToRightOverride ? LeftToRight : RightToLeft;
 682         appendRun();
 683         m_runs.setLogicallyLastRun(m_runs.lastRun());
 684         if (override == VisualRightToLeftOverride && m_runs.runCount())
 685             m_runs.reverseRuns(0, m_runs.runCount() - 1);
 686         return;
 687     }
 688
 689     m_emptyRun = true;
 690
 691     m_eor = Iterator();
 692
 693     m_last = m_current;
 694     bool lastLineEnded = false;
 695     BidiResolver<Iterator, Run> stateAtEnd;
 696
 697     while (true) {
 698         if (inIsolate() && m_emptyRun) {
 699             m_sor = m_current;
 700             m_emptyRun = false;
 701         }
 702
 703         if (!lastLineEnded && isEndOfLine(end)) {
 704             if (m_emptyRun)
 705                 break;
 706
 707             stateAtEnd.m_status = m_status;
 708             stateAtEnd.m_sor = m_sor;
 709             stateAtEnd.m_eor = m_eor;
 710             stateAtEnd.m_last = m_last;
 711             stateAtEnd.m_reachedEndOfLine = m_reachedEndOfLine;
 712             stateAtEnd.m_lastBeforeET = m_lastBeforeET;
 713             stateAtEnd.m_emptyRun = m_emptyRun;
 714             m_endOfRunAtEndOfLine = m_last;
 715             lastLineEnded = true;
 716         }
 717         Direction dirCurrent;
 718         if (lastLineEnded && (hardLineBreak || m_current.atEnd())) {
 719             BidiContext* c = context();
 720             if (hardLineBreak) {
 721                 // A deviation from the Unicode Bidi Algorithm in order to match
 722                 // WinIE and user expectations: hard line breaks reset bidi state
 723                 // coming from unicode bidi control characters, but not those from
 724                 // DOM nodes with specified directionality
 725                 stateAtEnd.setContext(c->copyStackRemovingUnicodeEmbeddingContexts());
 726
 727                 dirCurrent = stateAtEnd.context()->dir();
 728                 stateAtEnd.setEorDir(dirCurrent);
 729                 stateAtEnd.setLastDir(dirCurrent);
 730                 stateAtEnd.setLastStrongDir(dirCurrent);
 731             } else {
 732                 while (c->parent())
 733                     c = c->parent();
 734                 dirCurrent = c->dir();
 735             }
 736         } else {
 737             dirCurrent = m_current.direction();
 738             if (context()->override()
 739                 && dirCurrent != RightToLeftEmbedding
 740                 && dirCurrent != LeftToRightEmbedding
 741                 && dirCurrent != RightToLeftOverride
 742                 && dirCurrent != LeftToRightOverride
 743                 && dirCurrent != PopDirectionalFormat)
 744                 dirCurrent = context()->dir();
 745             else if (dirCurrent == NonSpacingMark)
 746                 dirCurrent = m_status.last;
 747         }
 748
 749         // We ignore all character directionality while in unicode-bidi: isolate spans.
 750         // We'll handle ordering the isolated characters in a second pass.
 751         if (inIsolate())
 752             dirCurrent = OtherNeutral;
 753
 754         ASSERT(m_status.eor != OtherNeutral || m_eor.atEnd());
 755         switch (dirCurrent) {
 756
 757         // embedding and overrides (X1-X9 in the Bidi specs)
 758         case RightToLeftEmbedding:
 759         case LeftToRightEmbedding:
 760         case RightToLeftOverride:
 761         case LeftToRightOverride:
 762         case PopDirectionalFormat:
 763             embed(dirCurrent, FromUnicode);
 764             commitExplicitEmbedding();
 765             break;
 766
 767         // strong types
 768         case LeftToRight:
 769             switch (m_status.last) {
 770             case RightToLeft:
 771             case RightToLeftArabic:
 772             case EuropeanNumber:
 773             case ArabicNumber:
 774                 if (m_status.last != EuropeanNumber || m_status.lastStrong != LeftToRight)
 775                     appendRun();
 776                 break;
 777             case LeftToRight:
 778                 break;
 779             case EuropeanNumberSeparator:
 780             case EuropeanNumberTerminator:
 781             case CommonNumberSeparator:
 782             case BoundaryNeutral:
 783             case BlockSeparator:
 784             case SegmentSeparator:
 785             case WhiteSpaceNeutral:
 786             case OtherNeutral:
 787                 if (m_status.eor == EuropeanNumber) {
 788                     if (m_status.lastStrong != LeftToRight) {
 789                         // the numbers need to be on a higher embedding level, so let's close that run
 790                         m_direction = EuropeanNumber;
 791                         appendRun();
 792                         if (context()->dir() != LeftToRight) {
 793                             // the neutrals take the embedding direction, which is R
 794                             m_eor = m_last;
 795                             m_direction = RightToLeft;
 796                             appendRun();
 797                         }
 798                     }
 799                 } else if (m_status.eor == ArabicNumber) {
 800                     // Arabic numbers are always on a higher embedding level, so let's close that run
 801                     m_direction = ArabicNumber;
 802                     appendRun();
 803                     if (context()->dir() != LeftToRight) {
 804                         // the neutrals take the embedding direction, which is R
 805                         m_eor = m_last;
 806                         m_direction = RightToLeft;
 807                         appendRun();
 808                     }
 809                 } else if (m_status.lastStrong != LeftToRight) {
 810                     // last stuff takes embedding dir
 811                     if (context()->dir() == RightToLeft) {
 812                         m_eor = m_last;
 813                         m_direction = RightToLeft;
 814                     }
 815                     appendRun();
 816                 }
 817             default:
 818                 break;
 819             }
 820             m_eor = m_current;
 821             m_status.eor = LeftToRight;
 822             m_status.lastStrong = LeftToRight;
 823             m_direction = LeftToRight;
 824             break;
 825         case RightToLeftArabic:
 826         case RightToLeft:
 827             switch (m_status.last) {
 828             case LeftToRight:
 829             case EuropeanNumber:
 830             case ArabicNumber:
 831                 appendRun();
 832             case RightToLeft:
 833             case RightToLeftArabic:
 834                 break;
 835             case EuropeanNumberSeparator:
 836             case EuropeanNumberTerminator:
 837             case CommonNumberSeparator:
 838             case BoundaryNeutral:
 839             case BlockSeparator:
 840             case SegmentSeparator:
 841             case WhiteSpaceNeutral:
 842             case OtherNeutral:
 843                 if (m_status.eor == EuropeanNumber) {
 844                     if (m_status.lastStrong == LeftToRight && context()->dir() == LeftToRight)
 845                         m_eor = m_last;
 846                     appendRun();
 847                 } else if (m_status.eor == ArabicNumber) {
 848                     appendRun();
 849                 } else if (m_status.lastStrong == LeftToRight) {
 850                     if (context()->dir() == LeftToRight)
 851                         m_eor = m_last;
 852                     appendRun();
 853                 }
 854             default:
 855                 break;
 856             }
 857             m_eor = m_current;
 858             m_status.eor = RightToLeft;
 859             m_status.lastStrong = dirCurrent;
 860             m_direction = RightToLeft;
 861             break;
 862
 863             // weak types:
 864
 865         case EuropeanNumber:
 866             if (m_status.lastStrong != RightToLeftArabic) {
 867                 // if last strong was AL change EN to AN
 868                 switch (m_status.last) {
 869                 case EuropeanNumber:
 870                 case LeftToRight:
 871                     break;
 872                 case RightToLeft:
 873                 case RightToLeftArabic:
 874                 case ArabicNumber:
 875                     m_eor = m_last;
 876                     appendRun();
 877                     m_direction = EuropeanNumber;
 878                     break;
 879                 case EuropeanNumberSeparator:
 880                 case CommonNumberSeparator:
 881                     if (m_status.eor == EuropeanNumber)
 882                         break;
 883                 case EuropeanNumberTerminator:
 884                 case BoundaryNeutral:
 885                 case BlockSeparator:
 886                 case SegmentSeparator:
 887                 case WhiteSpaceNeutral:
 888                 case OtherNeutral:
 889                     if (m_status.eor == EuropeanNumber) {
 890                         if (m_status.lastStrong == RightToLeft) {
 891                             // ENs on both sides behave like Rs, so the neutrals should be R.
 892                             // Terminate the EN run.
 893                             appendRun();
 894                             // Make an R run.
 895                             m_eor = m_status.last == EuropeanNumberTerminator ? m_lastBeforeET : m_last;
 896                             m_direction = RightToLeft;
 897                             appendRun();
 898                             // Begin a new EN run.
 899                             m_direction = EuropeanNumber;
 900                         }
 901                     } else if (m_status.eor == ArabicNumber) {
 902                         // Terminate the AN run.
 903                         appendRun();
 904                         if (m_status.lastStrong == RightToLeft || context()->dir() == RightToLeft) {
 905                             // Make an R run.
 906                             m_eor = m_status.last == EuropeanNumberTerminator ? m_lastBeforeET : m_last;
 907                             m_direction = RightToLeft;
 908                             appendRun();
 909                             // Begin a new EN run.
 910                             m_direction = EuropeanNumber;
 911                         }
 912                     } else if (m_status.lastStrong == RightToLeft) {
 913                         // Extend the R run to include the neutrals.
 914                         m_eor = m_status.last == EuropeanNumberTerminator ? m_lastBeforeET : m_last;
 915                         m_direction = RightToLeft;
 916                         appendRun();
 917                         // Begin a new EN run.
 918                         m_direction = EuropeanNumber;
 919                     }
 920                 default:
 921                     break;
 922                 }
 923                 m_eor = m_current;
 924                 m_status.eor = EuropeanNumber;
 925                 if (m_direction == OtherNeutral)
 926                     m_direction = LeftToRight;
 927                 break;
 928             }
 929         case ArabicNumber:
 930             dirCurrent = ArabicNumber;
 931             switch (m_status.last) {
 932             case LeftToRight:
 933                 if (context()->dir() == LeftToRight)
 934                     appendRun();
 935                 break;
 936             case ArabicNumber:
 937                 break;
 938             case RightToLeft:
 939             case RightToLeftArabic:
 940             case EuropeanNumber:
 941                 m_eor = m_last;
 942                 appendRun();
 943                 break;
 944             case CommonNumberSeparator:
 945                 if (m_status.eor == ArabicNumber)
 946                     break;
 947             case EuropeanNumberSeparator:
 948             case EuropeanNumberTerminator:
 949             case BoundaryNeutral:
 950             case BlockSeparator:
 951             case SegmentSeparator:
 952             case WhiteSpaceNeutral:
 953             case OtherNeutral:
 954                 if (m_status.eor == ArabicNumber
 955                     || (m_status.eor == EuropeanNumber && (m_status.lastStrong == RightToLeft || context()->dir() == RightToLeft))
 956                     || (m_status.eor != EuropeanNumber && m_status.lastStrong == LeftToRight && context()->dir() == RightToLeft)) {
 957                     // Terminate the run before the neutrals.
 958                     appendRun();
 959                     // Begin an R run for the neutrals.
 960                     m_direction = RightToLeft;
 961                 } else if (m_direction == OtherNeutral) {
 962                     m_direction = m_status.lastStrong == LeftToRight ? LeftToRight : RightToLeft;
 963                 }
 964                 m_eor = m_last;
 965                 appendRun();
 966             default:
 967                 break;
 968             }
 969             m_eor = m_current;
 970             m_status.eor = ArabicNumber;
 971             if (m_direction == OtherNeutral)
 972                 m_direction = ArabicNumber;
 973             break;
 974         case EuropeanNumberSeparator:
 975         case CommonNumberSeparator:
 976             break;
 977         case EuropeanNumberTerminator:
 978             if (m_status.last == EuropeanNumber) {
 979                 dirCurrent = EuropeanNumber;
 980                 m_eor = m_current;
 981                 m_status.eor = dirCurrent;
 982             } else if (m_status.last != EuropeanNumberTerminator) {
 983                 m_lastBeforeET = m_emptyRun ? m_eor : m_last;
 984             }
 985             break;
 986
 987         // boundary neutrals should be ignored
 988         case BoundaryNeutral:
 989             if (m_eor == m_last)
 990                 m_eor = m_current;
 991             break;
 992             // neutrals
 993         case BlockSeparator:
 994             // ### what do we do with newline and paragraph seperators that come to here?
 995             break;
 996         case SegmentSeparator:
 997             // ### implement rule L1
 998             break;
 999         case WhiteSpaceNeutral:
1000             break;
1001         case OtherNeutral:
1002             break;
1003         default:
1004             break;
1005         }
1006
1007         if (lastLineEnded && m_eor == m_current) {
1008             if (!m_reachedEndOfLine) {
1009                 m_eor = m_endOfRunAtEndOfLine;
1010                 switch (m_status.eor) {
1011                 case LeftToRight:
1012                 case RightToLeft:
1013                 case ArabicNumber:
1014                     m_direction = m_status.eor;
1015                     break;
1016                 case EuropeanNumber:
1017                     m_direction = m_status.lastStrong == LeftToRight ? LeftToRight : EuropeanNumber;
1018                     break;
1019                 default:
1020                     ASSERT_NOT_REACHED();
1021                 }
1022                 appendRun();
1023             }
1024             m_current = end;
1025             m_status = stateAtEnd.m_status;
1026             m_sor = stateAtEnd.m_sor;
1027             m_eor = stateAtEnd.m_eor;
1028             m_last = stateAtEnd.m_last;
1029             m_reachedEndOfLine = stateAtEnd.m_reachedEndOfLine;
1030             m_lastBeforeET = stateAtEnd.m_lastBeforeET;
1031             m_emptyRun = stateAtEnd.m_emptyRun;
1032             m_direction = OtherNeutral;
1033             break;
1034         }
1035
1036         updateStatusLastFromCurrentDirection(dirCurrent);
1037         m_last = m_current;
1038
1039         if (m_emptyRun) {
1040             m_sor = m_current;
1041             m_emptyRun = false;
1042         }
1043
1044         increment();
1045         if (!m_currentExplicitEmbeddingSequence.isEmpty()) {
1046             bool committed = commitExplicitEmbedding();
1047             if (committed && lastLineEnded) {
1048                 m_current = end;
1049                 m_status = stateAtEnd.m_status;
1050                 m_sor = stateAtEnd.m_sor;
1051                 m_eor = stateAtEnd.m_eor;
1052                 m_last = stateAtEnd.m_last;
1053                 m_reachedEndOfLine = stateAtEnd.m_reachedEndOfLine;
1054                 m_lastBeforeET = stateAtEnd.m_lastBeforeET;
1055                 m_emptyRun = stateAtEnd.m_emptyRun;
1056                 m_direction = OtherNeutral;
1057                 break;
1058             }
1059         }
1060     }
1061
1062     m_runs.setLogicallyLastRun(m_runs.lastRun());
1063     if (reorderRuns)
1064         reorderRunsFromLevels();
1065     m_endOfRunAtEndOfLine = Iterator();
1066     m_endOfLine = Iterator();
1067
1068     if (!hardLineBreak && m_runs.runCount())
1069         applyL1Rule();
1070 }
1071
1072 template <class Iterator, class Run>
1073 void BidiResolver<Iterator, Run>::setMidpointStateForIsolatedRun(Run* run, const MidpointState<Iterator>& midpoint)
1074 {
1075     ASSERT(!m_midpointStateForIsolatedRun.contains(run));
1076     m_midpointStateForIsolatedRun.add(run, midpoint);
1077 }
1078
1079 template<class Iterator, class Run>
1080 MidpointState<Iterator> BidiResolver<Iterator, Run>::midpointStateForIsolatedRun(Run* run)
1081 {
1082     return m_midpointStateForIsolatedRun.take(run);
1083 }
1084
1085
1086 } // namespace WebCore
1087
1088 #endif // BidiResolver_h