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