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