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