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