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