Fix by Mitz Pettel, reviewed by Hyatt.
[WebKit-https.git] / WebCore / rendering / bidi.cpp
1 /**
2  * This file is part of the html renderer for KDE.
3  *
4  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
5  * Copyright (C) 2004, 2006 Apple Computer, Inc.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20  * Boston, MA 02111-1307, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "bidi.h"
26
27 #include "Document.h"
28 #include "Element.h"
29 #include "FrameView.h"
30 #include "InlineTextBox.h"
31 #include "RenderArena.h"
32 #include "RenderView.h"
33 #include "break_lines.h"
34 #include <wtf/AlwaysInline.h>
35 #include <wtf/Vector.h>
36
37 using namespace std;
38
39 namespace WebCore {
40
41 // an iterator which traverses all the objects within a block
42 struct BidiIterator {
43     BidiIterator() : block(0), obj(0), pos(0) {}
44     BidiIterator(RenderBlock* b, RenderObject* o, unsigned int p) 
45         : block(b), obj(o), pos(p) {}
46     
47     void increment(BidiState& state);
48     bool atEnd() const;
49     
50     UChar current() const;
51     UCharDirection direction() const;
52
53     RenderBlock* block;
54     RenderObject* obj;
55     unsigned int pos;
56 };
57
58 struct BidiState {
59     BidiState() : context(0), dir(U_OTHER_NEUTRAL), adjustEmbedding(false), reachedEndOfLine(false) {}
60     
61     BidiIterator sor;
62     BidiIterator eor;
63     BidiIterator last;
64     BidiIterator current;
65     RefPtr<BidiContext> context;
66     BidiStatus status;
67     UCharDirection dir;
68     bool adjustEmbedding;
69     BidiIterator endOfLine;
70     bool reachedEndOfLine;
71     BidiIterator lastBeforeET;
72 };
73
74 inline bool operator==(const BidiStatus& status1, const BidiStatus& status2)
75 {
76     return status1.eor == status2.eor && status1.last == status2.last && status1.lastStrong == status2.lastStrong;
77 }
78
79 inline bool operator!=(const BidiStatus& status1, const BidiStatus& status2)
80 {
81     return !(status1 == status2);
82 }
83
84 // Used to track a list of chained bidi runs.
85 static BidiRun* sFirstBidiRun;
86 static BidiRun* sLastBidiRun;
87 static BidiRun* sLogicallyLastBidiRun;
88 static int sBidiRunCount;
89 static BidiRun* sCompactFirstBidiRun;
90 static BidiRun* sCompactLastBidiRun;
91 static int sCompactBidiRunCount;
92 static bool sBuildingCompactRuns;
93
94 // Midpoint globals.  The goal is not to do any allocation when dealing with
95 // these midpoints, so we just keep an array around and never clear it.  We track
96 // the number of items and position using the two other variables.
97 static Vector<BidiIterator>* smidpoints;
98 static unsigned sNumMidpoints;
99 static unsigned sCurrMidpoint;
100 static bool betweenMidpoints;
101
102 static bool isLineEmpty = true;
103 static bool previousLineBrokeCleanly = true;
104 static bool emptyRun = true;
105 static int numSpaces;
106
107 static void embed(UCharDirection, BidiState&);
108 static void appendRun(BidiState&);
109
110 static int getBPMWidth(int childValue, Length cssUnit)
111 {
112     if (!cssUnit.isIntrinsicOrAuto())
113         return (cssUnit.isFixed() ? cssUnit.value() : childValue);
114     return 0;
115 }
116
117 static int getBorderPaddingMargin(RenderObject* child, bool endOfInline)
118 {
119     RenderStyle* cstyle = child->style();
120     int result = 0;
121     bool leftSide = (cstyle->direction() == LTR) ? !endOfInline : endOfInline;
122     result += getBPMWidth((leftSide ? child->marginLeft() : child->marginRight()),
123                           (leftSide ? cstyle->marginLeft() :
124                            cstyle->marginRight()));
125     result += getBPMWidth((leftSide ? child->paddingLeft() : child->paddingRight()),
126                           (leftSide ? cstyle->paddingLeft() :
127                            cstyle->paddingRight()));
128     result += leftSide ? child->borderLeft() : child->borderRight();
129     return result;
130 }
131
132 static int inlineWidth(RenderObject* child, bool start = true, bool end = true)
133 {
134     int extraWidth = 0;
135     RenderObject* parent = child->parent();
136     while (parent->isInline() && !parent->isInlineBlockOrInlineTable()) {
137         if (start && parent->firstChild() == child)
138             extraWidth += getBorderPaddingMargin(parent, false);
139         if (end && parent->lastChild() == child)
140             extraWidth += getBorderPaddingMargin(parent, true);
141         child = parent;
142         parent = child->parent();
143     }
144     return extraWidth;
145 }
146
147 #ifndef NDEBUG
148 static bool inBidiRunDestroy;
149 #endif
150
151 void BidiRun::destroy(RenderArena* renderArena)
152 {
153 #ifndef NDEBUG
154     inBidiRunDestroy = true;
155 #endif
156     delete this;
157 #ifndef NDEBUG
158     inBidiRunDestroy = false;
159 #endif
160
161     // Recover the size left there for us by operator delete and free the memory.
162     renderArena->free(*(size_t *)this, this);
163 }
164
165 void* BidiRun::operator new(size_t sz, RenderArena* renderArena) throw()
166 {
167     return renderArena->allocate(sz);
168 }
169
170 void BidiRun::operator delete(void* ptr, size_t sz)
171 {
172     assert(inBidiRunDestroy);
173
174     // Stash size where destroy() can find it.
175     *(size_t*)ptr = sz;
176 }
177
178 static void deleteBidiRuns(RenderArena* arena)
179 {
180     emptyRun = true;
181     if (!sFirstBidiRun)
182         return;
183
184     BidiRun* curr = sFirstBidiRun;
185     while (curr) {
186         BidiRun* s = curr->nextRun;
187         curr->destroy(arena);
188         curr = s;
189     }
190     
191     sFirstBidiRun = 0;
192     sLastBidiRun = 0;
193     sBidiRunCount = 0;
194 }
195
196 // ---------------------------------------------------------------------
197
198 /* a small helper class used internally to resolve Bidi embedding levels.
199    Each line of text caches the embedding level at the start of the line for faster
200    relayouting
201 */
202 BidiContext::BidiContext(unsigned char l, UCharDirection e, BidiContext *p, bool o)
203     : level(l), override(o), m_dir(e)
204 {
205     parent = p;
206     if (p) {
207         p->ref();
208         m_basicDir = p->basicDir();
209     } else
210         m_basicDir = e;
211     count = 0;
212 }
213
214 BidiContext::~BidiContext()
215 {
216     if (parent) 
217         parent->deref();
218 }
219
220 void BidiContext::ref() const
221 {
222     count++;
223 }
224
225 void BidiContext::deref() const
226 {
227     count--;
228     if (count <= 0)
229         delete this;
230 }
231
232 bool operator==(const BidiContext& c1, const BidiContext& c2)
233 {
234     if (&c1 == &c2)
235         return true;
236     if (c1.level != c2.level || c1.override != c2.override || c1.dir() != c2.dir() || c1.basicDir() != c2.basicDir())
237         return false;
238     if (!c1.parent)
239         return !c2.parent;
240     return c2.parent && *c1.parent == *c2.parent;
241 }
242
243 inline bool operator!=(const BidiContext& c1, const BidiContext& c2)
244 {
245     return !(c1 == c2);
246 }
247
248 // ---------------------------------------------------------------------
249
250 inline bool operator==(const BidiIterator& it1, const BidiIterator& it2)
251 {
252     if (it1.pos != it2.pos)
253         return false;
254     if (it1.obj != it2.obj)
255         return false;
256     return true;
257 }
258
259 inline bool operator!=(const BidiIterator& it1, const BidiIterator& it2)
260 {
261     if (it1.pos != it2.pos)
262         return true;
263     if (it1.obj != it2.obj)
264         return true;
265     return false;
266 }
267
268 static inline RenderObject* bidiNext(RenderBlock* block, RenderObject* current, BidiState& bidi,
269                                      bool skipInlines = true, bool* endOfInline = 0)
270 {
271     RenderObject* next = 0;
272     bool oldEndOfInline = endOfInline ? *endOfInline : false;
273     if (endOfInline)
274         *endOfInline = false;
275
276     while (current) {
277         if (!oldEndOfInline && !current->isFloating() && !current->isReplaced() && !current->isPositioned()) {
278             next = current->firstChild();
279             if (next && bidi.adjustEmbedding && next->isInlineFlow()) {
280                 EUnicodeBidi ub = next->style()->unicodeBidi();
281                 if (ub != UBNormal) {
282                     TextDirection dir = next->style()->direction();
283                     UCharDirection d = (ub == Embed
284                         ? (dir == RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING)
285                         : (dir == RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE));
286                     embed(d, bidi);
287                 }
288             }
289         }
290
291         if (!next) {
292             if (!skipInlines && !oldEndOfInline && current->isInlineFlow()) {
293                 next = current;
294                 if (endOfInline)
295                     *endOfInline = true;
296                 break;
297             }
298
299             while (current && current != block) {
300                 if (bidi.adjustEmbedding && current->isInlineFlow() && current->style()->unicodeBidi() != UBNormal)
301                     embed(U_POP_DIRECTIONAL_FORMAT, bidi);
302
303                 next = current->nextSibling();
304                 if (next) {
305                     if (bidi.adjustEmbedding && next->isInlineFlow()) {
306                         EUnicodeBidi ub = next->style()->unicodeBidi();
307                         if (ub != UBNormal) {
308                             TextDirection dir = next->style()->direction();
309                             UCharDirection d = (ub == Embed
310                                 ? (dir == RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING)
311                                 : (dir == RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE));
312                             embed(d, bidi);
313                         }
314                     }
315                     break;
316                 }
317                 
318                 current = current->parent();
319                 if (!skipInlines && current && current != block && current->isInlineFlow()) {
320                     next = current;
321                     if (endOfInline)
322                         *endOfInline = true;
323                     break;
324                 }
325             }
326         }
327
328         if (!next)
329             break;
330
331         if (next->isText() || next->isBR() || next->isFloating() || next->isReplaced() || next->isPositioned()
332             || ((!skipInlines || !next->firstChild()) // Always return EMPTY inlines.
333                 && next->isInlineFlow()))
334             break;
335         current = next;
336     }
337     return next;
338 }
339
340 static RenderObject* bidiFirst(RenderBlock* block, BidiState& bidi, bool skipInlines = true )
341 {
342     if (!block->firstChild())
343         return 0;
344     
345     RenderObject* o = block->firstChild();
346     if (o->isInlineFlow()) {
347         if (bidi.adjustEmbedding) {
348             EUnicodeBidi ub = o->style()->unicodeBidi();
349             if (ub != UBNormal) {
350                 TextDirection dir = o->style()->direction();
351                 UCharDirection d = (ub == Embed
352                     ? (dir == RTL ? U_RIGHT_TO_LEFT_EMBEDDING : U_LEFT_TO_RIGHT_EMBEDDING)
353                     : (dir == RTL ? U_RIGHT_TO_LEFT_OVERRIDE : U_LEFT_TO_RIGHT_OVERRIDE));
354                 embed(d, bidi);
355             }
356         }
357         if (skipInlines && o->firstChild())
358             o = bidiNext(block, o, bidi, skipInlines);
359         else
360             return o; // Never skip empty inlines.
361     }
362
363     if (o && !o->isText() && !o->isBR() && !o->isReplaced() && !o->isFloating() && !o->isPositioned())
364         o = bidiNext(block, o, bidi, skipInlines);
365     return o;
366 }
367
368 inline void BidiIterator::increment(BidiState& bidi)
369 {
370     if (!obj)
371         return;
372     if (obj->isText()) {
373         pos++;
374         if (pos >= static_cast<RenderText *>(obj)->stringLength()) {
375             obj = bidiNext(block, obj, bidi);
376             pos = 0;
377         }
378     } else {
379         obj = bidiNext(block, obj, bidi);
380         pos = 0;
381     }
382 }
383
384 inline bool BidiIterator::atEnd() const
385 {
386     return !obj;
387 }
388
389 UChar BidiIterator::current() const
390 {
391     if (!obj || !obj->isText())
392         return 0;
393     
394     RenderText* text = static_cast<RenderText*>(obj);
395     if (!text->text())
396         return 0;
397     
398     return text->text()[pos];
399 }
400
401 ALWAYS_INLINE UCharDirection BidiIterator::direction() const
402 {
403     if (!obj)
404         return U_OTHER_NEUTRAL;
405     if (obj->isListMarker())
406         return obj->style()->direction() == LTR ? U_LEFT_TO_RIGHT : U_RIGHT_TO_LEFT;
407     if (!obj->isText())
408         return U_OTHER_NEUTRAL;
409     RenderText* renderTxt = static_cast<RenderText*>(obj);
410     if (pos >= renderTxt->stringLength())
411         return U_OTHER_NEUTRAL;
412     return u_charDirection(renderTxt->text()[pos]);
413 }
414
415 // -------------------------------------------------------------------------------------------------
416
417 static void addRun(BidiRun* bidiRun)
418 {
419     if (!sFirstBidiRun)
420         sFirstBidiRun = sLastBidiRun = bidiRun;
421     else {
422         sLastBidiRun->nextRun = bidiRun;
423         sLastBidiRun = bidiRun;
424     }
425     sBidiRunCount++;
426     bidiRun->compact = sBuildingCompactRuns;
427
428     // Compute the number of spaces in this run,
429     if (bidiRun->obj && bidiRun->obj->isText()) {
430         RenderText* text = static_cast<RenderText*>(bidiRun->obj);
431         if (text->text()) {
432             for (int i = bidiRun->start; i < bidiRun->stop; i++) {
433                 UChar c = text->text()[i];
434                 if (c == ' ' || c == '\n' || c == '\t')
435                     numSpaces++;
436             }
437         }
438     }
439 }
440
441 static void reverseRuns(int start, int end)
442 {
443     if (start >= end)
444         return;
445
446     assert(start >= 0 && end < sBidiRunCount);
447     
448     // Get the item before the start of the runs to reverse and put it in
449     // |beforeStart|.  |curr| should point to the first run to reverse.
450     BidiRun* curr = sFirstBidiRun;
451     BidiRun* beforeStart = 0;
452     int i = 0;
453     while (i < start) {
454         i++;
455         beforeStart = curr;
456         curr = curr->nextRun;
457     }
458
459     BidiRun* startRun = curr;
460     while (i < end) {
461         i++;
462         curr = curr->nextRun;
463     }
464     BidiRun* endRun = curr;
465     BidiRun* afterEnd = curr->nextRun;
466
467     i = start;
468     curr = startRun;
469     BidiRun* newNext = afterEnd;
470     while (i <= end) {
471         // Do the reversal.
472         BidiRun* next = curr->nextRun;
473         curr->nextRun = newNext;
474         newNext = curr;
475         curr = next;
476         i++;
477     }
478
479     // Now hook up beforeStart and afterEnd to the newStart and newEnd.
480     if (beforeStart)
481         beforeStart->nextRun = endRun;
482     else
483         sFirstBidiRun = endRun;
484
485     startRun->nextRun = afterEnd;
486     if (!afterEnd)
487         sLastBidiRun = startRun;
488 }
489
490 static void chopMidpointsAt(RenderObject* obj, unsigned pos)
491 {
492     if (!sNumMidpoints)
493         return;
494     BidiIterator* midpoints = smidpoints->data();
495     for (unsigned i = 0; i < sNumMidpoints; i++) {
496         const BidiIterator& point = midpoints[i];
497         if (point.obj == obj && point.pos == pos) {
498             sNumMidpoints = i;
499             break;
500         }
501     }
502 }
503
504 static void checkMidpoints(BidiIterator& lBreak, BidiState& bidi)
505 {
506     // Check to see if our last midpoint is a start point beyond the line break.  If so,
507     // shave it off the list, and shave off a trailing space if the previous end point doesn't
508     // preserve whitespace.
509     if (lBreak.obj && sNumMidpoints && sNumMidpoints%2 == 0) {
510         BidiIterator* midpoints = smidpoints->data();
511         BidiIterator& endpoint = midpoints[sNumMidpoints-2];
512         const BidiIterator& startpoint = midpoints[sNumMidpoints-1];
513         BidiIterator currpoint = endpoint;
514         while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)
515             currpoint.increment(bidi);
516         if (currpoint == lBreak) {
517             // We hit the line break before the start point.  Shave off the start point.
518             sNumMidpoints--;
519             if (endpoint.obj->style()->collapseWhiteSpace()) {
520                 if (endpoint.obj->isText()) {
521                     // Don't shave a character off the endpoint if it was from a soft hyphen.
522                     RenderText* textObj = static_cast<RenderText*>(endpoint.obj);
523                     if (endpoint.pos+1 < textObj->length()) {
524                         if (textObj->text()[endpoint.pos+1] == SOFT_HYPHEN)
525                             return;
526                     } else if (startpoint.obj->isText()) {
527                         RenderText *startText = static_cast<RenderText*>(startpoint.obj);
528                         if (startText->length() > 0 && startText->text()[0] == SOFT_HYPHEN)
529                             return;
530                     }
531                 }
532                 endpoint.pos--;
533             }
534         }
535     }    
536 }
537
538 static void addMidpoint(const BidiIterator& midpoint)
539 {
540     if (!smidpoints)
541         return;
542
543     if (smidpoints->size() <= sNumMidpoints)
544         smidpoints->resize(sNumMidpoints + 10);
545
546     BidiIterator* midpoints = smidpoints->data();
547     midpoints[sNumMidpoints++] = midpoint;
548 }
549
550 static void appendRunsForObject(int start, int end, RenderObject* obj, BidiState &bidi)
551 {
552     if (start > end || obj->isFloating() ||
553         (obj->isPositioned() && !obj->hasStaticX() && !obj->hasStaticY() && !obj->container()->isInlineFlow()))
554         return;
555
556     bool haveNextMidpoint = (smidpoints && sCurrMidpoint < sNumMidpoints);
557     BidiIterator nextMidpoint;
558     if (haveNextMidpoint)
559         nextMidpoint = smidpoints->at(sCurrMidpoint);
560     if (betweenMidpoints) {
561         if (!(haveNextMidpoint && nextMidpoint.obj == obj))
562             return;
563         // This is a new start point. Stop ignoring objects and 
564         // adjust our start.
565         betweenMidpoints = false;
566         start = nextMidpoint.pos;
567         sCurrMidpoint++;
568         if (start < end)
569             return appendRunsForObject(start, end, obj, bidi);
570     }
571     else {
572         if (!smidpoints || !haveNextMidpoint || (obj != nextMidpoint.obj)) {
573             addRun(new (obj->renderArena()) BidiRun(start, end, obj, bidi.context.get(), bidi.dir));
574             return;
575         }
576         
577         // An end midpoint has been encountered within our object.  We
578         // need to go ahead and append a run with our endpoint.
579         if (int(nextMidpoint.pos+1) <= end) {
580             betweenMidpoints = true;
581             sCurrMidpoint++;
582             if (nextMidpoint.pos != UINT_MAX) { // UINT_MAX means stop at the object and don't include any of it.
583                 if (int(nextMidpoint.pos+1) > start)
584                     addRun(new (obj->renderArena())
585                         BidiRun(start, nextMidpoint.pos+1, obj, bidi.context.get(), bidi.dir));
586                 return appendRunsForObject(nextMidpoint.pos+1, end, obj, bidi);
587             }
588         }
589         else
590            addRun(new (obj->renderArena()) BidiRun(start, end, obj, bidi.context.get(), bidi.dir));
591     }
592 }
593
594 static void appendRun(BidiState &bidi)
595 {
596     if (emptyRun || !bidi.eor.obj)
597         return;
598 #if BIDI_DEBUG > 1
599     kdDebug(6041) << "appendRun: dir="<<(int)dir<<endl;
600 #endif
601
602     bool b = bidi.adjustEmbedding;
603     bidi.adjustEmbedding = false;
604
605     int start = bidi.sor.pos;
606     RenderObject *obj = bidi.sor.obj;
607     while (obj && obj != bidi.eor.obj && obj != bidi.endOfLine.obj) {
608         appendRunsForObject(start, obj->length(), obj, bidi);        
609         start = 0;
610         obj = bidiNext(bidi.sor.block, obj, bidi);
611     }
612     if (obj) {
613         unsigned pos = obj == bidi.eor.obj ? bidi.eor.pos : UINT_MAX;
614         if (obj == bidi.endOfLine.obj && bidi.endOfLine.pos <= pos) {
615             bidi.reachedEndOfLine = true;
616             pos = bidi.endOfLine.pos;
617         }
618         // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
619         int end = obj->length() ? pos+1 : 0;
620         appendRunsForObject(start, end, obj, bidi);
621     }
622     
623     bidi.eor.increment(bidi);
624     bidi.sor = bidi.eor;
625     bidi.dir = U_OTHER_NEUTRAL;
626     bidi.status.eor = U_OTHER_NEUTRAL;
627     bidi.adjustEmbedding = b;
628 }
629
630 static void embed(UCharDirection d, BidiState& bidi)
631 {
632     bool b = bidi.adjustEmbedding;
633     bidi.adjustEmbedding = false;
634     if (d == U_POP_DIRECTIONAL_FORMAT) {
635         BidiContext *c = bidi.context->parent;
636         if (c) {
637             if (!emptyRun && bidi.eor != bidi.last) {
638                 assert(bidi.status.eor != U_OTHER_NEUTRAL);
639                 // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
640                 assert(bidi.status.last == U_EUROPEAN_NUMBER_SEPARATOR
641                     || bidi.status.last == U_EUROPEAN_NUMBER_TERMINATOR
642                     || bidi.status.last == U_COMMON_NUMBER_SEPARATOR
643                     || bidi.status.last == U_BOUNDARY_NEUTRAL
644                     || bidi.status.last == U_BLOCK_SEPARATOR
645                     || bidi.status.last == U_SEGMENT_SEPARATOR
646                     || bidi.status.last == U_WHITE_SPACE_NEUTRAL
647                     || bidi.status.last == U_OTHER_NEUTRAL);
648                 if (bidi.dir == U_OTHER_NEUTRAL)
649                     bidi.dir = bidi.context->dir();
650                 if (bidi.context->dir() == U_LEFT_TO_RIGHT) {
651                     // bidi.sor ... bidi.eor ... bidi.last L
652                     if (bidi.status.eor == U_EUROPEAN_NUMBER) {
653                         if (bidi.status.lastStrong != U_LEFT_TO_RIGHT) {
654                             bidi.dir = U_EUROPEAN_NUMBER;
655                             appendRun(bidi);
656                         }
657                     } else if (bidi.status.eor == U_ARABIC_NUMBER) {
658                         bidi.dir = U_ARABIC_NUMBER;
659                         appendRun(bidi);
660                     } else if (bidi.status.eor != U_LEFT_TO_RIGHT)
661                         appendRun(bidi);
662                 } else if (bidi.status.eor != U_RIGHT_TO_LEFT && bidi.status.eor != U_RIGHT_TO_LEFT_ARABIC)
663                     appendRun(bidi);
664                 bidi.eor = bidi.last;
665             }
666             appendRun(bidi);
667             emptyRun = true;
668             // sor for the new run is determined by the higher level (rule X10)
669             bidi.status.last = bidi.context->dir();
670             bidi.status.lastStrong = bidi.context->dir();
671             bidi.context = c;
672             bidi.status.eor = bidi.context->dir();
673             bidi.eor.obj = 0;
674         }
675     } else {
676         UCharDirection runDir;
677         if (d == U_RIGHT_TO_LEFT_EMBEDDING || d == U_RIGHT_TO_LEFT_OVERRIDE)
678             runDir = U_RIGHT_TO_LEFT;
679         else
680             runDir = U_LEFT_TO_RIGHT;
681         bool override = d == U_LEFT_TO_RIGHT_OVERRIDE || d == U_RIGHT_TO_LEFT_OVERRIDE;
682
683         unsigned char level = bidi.context->level;
684         if (runDir == U_RIGHT_TO_LEFT) {
685             if (level%2) // we have an odd level
686                 level += 2;
687             else
688                 level++;
689         } else {
690             if (level%2) // we have an odd level
691                 level++;
692             else
693                 level += 2;
694         }
695
696         if (level < 61) {
697             if (!emptyRun && bidi.eor != bidi.last) {
698                 assert(bidi.status.eor != U_OTHER_NEUTRAL);
699                 // bidi.sor ... bidi.eor ... bidi.last eor; need to append the bidi.sor-bidi.eor run or extend it through bidi.last
700                 assert(bidi.status.last == U_EUROPEAN_NUMBER_SEPARATOR
701                     || bidi.status.last == U_EUROPEAN_NUMBER_TERMINATOR
702                     || bidi.status.last == U_COMMON_NUMBER_SEPARATOR
703                     || bidi.status.last == U_BOUNDARY_NEUTRAL
704                     || bidi.status.last == U_BLOCK_SEPARATOR
705                     || bidi.status.last == U_SEGMENT_SEPARATOR
706                     || bidi.status.last == U_WHITE_SPACE_NEUTRAL
707                     || bidi.status.last == U_OTHER_NEUTRAL);
708                 if (bidi.dir == U_OTHER_NEUTRAL)
709                     bidi.dir = runDir;
710                 if (runDir == U_LEFT_TO_RIGHT) {
711                     // bidi.sor ... bidi.eor ... bidi.last L
712                     if (bidi.status.eor == U_EUROPEAN_NUMBER) {
713                         if (bidi.status.lastStrong != U_LEFT_TO_RIGHT) {
714                             bidi.dir = U_EUROPEAN_NUMBER;
715                             appendRun(bidi);
716                             if (bidi.context->dir() != U_LEFT_TO_RIGHT)
717                                 bidi.dir = U_RIGHT_TO_LEFT;
718                         }
719                     } else if (bidi.status.eor == U_ARABIC_NUMBER) {
720                         bidi.dir = U_ARABIC_NUMBER;
721                         appendRun(bidi);
722                         if (bidi.context->dir() != U_LEFT_TO_RIGHT) {
723                             bidi.eor = bidi.last;
724                             bidi.dir = U_RIGHT_TO_LEFT;
725                             appendRun(bidi);
726                         }
727                     } else if (bidi.status.eor != U_LEFT_TO_RIGHT) {
728                         if (bidi.context->dir() == U_LEFT_TO_RIGHT || bidi.status.lastStrong == U_LEFT_TO_RIGHT)
729                             appendRun(bidi);
730                         else
731                             bidi.dir = U_RIGHT_TO_LEFT; 
732                     }
733                 } else if (bidi.status.eor != U_RIGHT_TO_LEFT && bidi.status.eor != U_RIGHT_TO_LEFT_ARABIC) {
734                     // bidi.sor ... bidi.eor ... bidi.last R; bidi.eor=L/EN/AN; EN,AN behave like R (rule N1)
735                     if (bidi.context->dir() == U_RIGHT_TO_LEFT || bidi.status.lastStrong == U_RIGHT_TO_LEFT || bidi.status.lastStrong == U_RIGHT_TO_LEFT_ARABIC)
736                         appendRun(bidi);
737                     else
738                         bidi.dir = U_LEFT_TO_RIGHT;
739                 }
740                 bidi.eor = bidi.last;
741             }
742             appendRun(bidi);
743             emptyRun = true;
744             bidi.context = new BidiContext(level, runDir, bidi.context.get(), override);
745             bidi.status.last = runDir;
746             bidi.status.lastStrong = runDir;
747             bidi.status.eor = runDir;
748             bidi.eor.obj = 0;
749         }
750     }
751     bidi.adjustEmbedding = b;
752 }
753
754 InlineFlowBox* RenderBlock::createLineBoxes(RenderObject* obj)
755 {
756     // See if we have an unconstructed line box for this object that is also
757     // the last item on the line.
758     ASSERT(obj->isInlineFlow() || obj == this);
759     RenderFlow* flow = static_cast<RenderFlow*>(obj);
760
761     // Get the last box we made for this render object.
762     InlineFlowBox* box = flow->lastLineBox();
763
764     // If this box is constructed then it is from a previous line, and we need
765     // to make a new box for our line.  If this box is unconstructed but it has
766     // something following it on the line, then we know we have to make a new box
767     // as well.  In this situation our inline has actually been split in two on
768     // the same line (this can happen with very fancy language mixtures).
769     if (!box || box->isConstructed() || box->nextOnLine()) {
770         // We need to make a new box for this render object.  Once
771         // made, we need to place it at the end of the current line.
772         InlineBox* newBox = obj->createInlineBox(false, obj == this);
773         ASSERT(newBox->isInlineFlowBox());
774         box = static_cast<InlineFlowBox*>(newBox);
775         box->setFirstLineStyleBit(m_firstLine);
776         
777         // We have a new box. Append it to the inline box we get by constructing our
778         // parent.  If we have hit the block itself, then |box| represents the root
779         // inline box for the line, and it doesn't have to be appended to any parent
780         // inline.
781         if (obj != this) {
782             InlineFlowBox* parentBox = createLineBoxes(obj->parent());
783             parentBox->addToLine(box);
784         }
785     }
786
787     return box;
788 }
789
790 RootInlineBox* RenderBlock::constructLine(const BidiIterator& start, const BidiIterator& end)
791 {
792     if (!sFirstBidiRun)
793         return 0; // We had no runs. Don't make a root inline box at all. The line is empty.
794
795     InlineFlowBox* parentBox = 0;
796     for (BidiRun* r = sFirstBidiRun; r; r = r->nextRun) {
797         // Create a box for our object.
798         bool isOnlyRun = (sBidiRunCount == 1);
799         if (sBidiRunCount == 2 && !r->obj->isListMarker())
800             isOnlyRun = ((style()->direction() == RTL) ? sLastBidiRun : sFirstBidiRun)->obj->isListMarker();
801         r->box = r->obj->createInlineBox(r->obj->isPositioned(), false, isOnlyRun);
802         if (r->box) {
803             // If we have no parent box yet, or if the run is not simply a sibling,
804             // then we need to construct inline boxes as necessary to properly enclose the
805             // run's inline box.
806             if (!parentBox || parentBox->object() != r->obj->parent())
807                 // Create new inline boxes all the way back to the appropriate insertion point.
808                 parentBox = createLineBoxes(r->obj->parent());
809
810             // Append the inline box to this line.
811             parentBox->addToLine(r->box);
812             
813             if (r->box->isInlineTextBox()) {
814                 InlineTextBox *text = static_cast<InlineTextBox*>(r->box);
815                 text->setStart(r->start);
816                 text->setLen(r->stop-r->start);
817             }
818         }
819     }
820
821     // We should have a root inline box.  It should be unconstructed and
822     // be the last continuation of our line list.
823     assert(lastLineBox() && !lastLineBox()->isConstructed());
824
825     // Set bits on our inline flow boxes that indicate which sides should
826     // paint borders/margins/padding.  This knowledge will ultimately be used when
827     // we determine the horizontal positions and widths of all the inline boxes on
828     // the line.
829     RenderObject* endObject = 0;
830     bool lastLine = !end.obj;
831     if (end.obj && end.pos == 0)
832         endObject = end.obj;
833     lastLineBox()->determineSpacingForFlowBoxes(lastLine, endObject);
834
835     // Now mark the line boxes as being constructed.
836     lastLineBox()->setConstructed();
837
838     // Return the last line.
839     return lastRootBox();
840 }
841
842 // usage: tw - (xpos % tw);
843 int RenderBlock::tabWidth(bool isWhitespacePre)
844 {
845     if (!isWhitespacePre)
846         return 0;
847
848     if (m_tabWidth == -1) {
849         const UChar spaceChar = ' ';
850         const Font& font = style()->font();
851         int spaceWidth = font.width(TextRun(&spaceChar, 1));
852         m_tabWidth = spaceWidth * 8;
853     }
854
855     return m_tabWidth;
856 }
857
858 void RenderBlock::computeHorizontalPositionsForLine(RootInlineBox* lineBox, BidiState& bidi)
859 {
860     // First determine our total width.
861     int availableWidth = lineWidth(m_height);
862     int totWidth = lineBox->getFlowSpacingWidth();
863     BidiRun* r = 0;
864     bool needsWordSpacing = false;
865     for (r = sFirstBidiRun; r; r = r->nextRun) {
866         if (!r->box || r->obj->isPositioned() || r->box->isLineBreak())
867             continue; // Positioned objects are only participating to figure out their
868                       // correct static x position.  They have no effect on the width.
869                       // Similarly, line break boxes have no effect on the width.
870         if (r->obj->isText()) {
871             RenderText* rt = static_cast<RenderText*>(r->obj);
872             int textWidth = rt->width(r->start, r->stop-r->start, totWidth, m_firstLine);
873             int effectiveWidth = textWidth;
874             int rtLength = rt->length();
875             if (rtLength != 0) {
876                 if (r->start == 0 && needsWordSpacing && DeprecatedChar(rt->text()[r->start]).isSpace())
877                     effectiveWidth += rt->font(m_firstLine)->wordSpacing();
878                 needsWordSpacing = !DeprecatedChar(rt->text()[r->stop-1]).isSpace() && r->stop == rtLength;          
879             }
880             r->box->setWidth(textWidth);
881         } else if (!r->obj->isInlineFlow()) {
882             r->obj->calcWidth();
883             r->box->setWidth(r->obj->width());
884             if (!r->compact)
885                  totWidth += r->obj->marginLeft() + r->obj->marginRight();
886         }
887
888         // Compacts don't contribute to the width of the line, since they are placed in the margin.
889         if (!r->compact)
890             totWidth += r->box->width();
891     }
892
893     if (totWidth > availableWidth && sLogicallyLastBidiRun->obj->style(m_firstLine)->autoWrap() &&
894         sLogicallyLastBidiRun->obj->style(m_firstLine)->breakOnlyAfterWhiteSpace() &&
895         !sLogicallyLastBidiRun->compact) {
896         sLogicallyLastBidiRun->box->setWidth(sLogicallyLastBidiRun->box->width() - totWidth + availableWidth);
897         totWidth = availableWidth;
898     }
899
900     // Armed with the total width of the line (without justification),
901     // we now examine our text-align property in order to determine where to position the
902     // objects horizontally.  The total width of the line can be increased if we end up
903     // justifying text.
904     int x = leftOffset(m_height);
905     switch(style()->textAlign()) {
906         case LEFT:
907         case KHTML_LEFT:
908             // The direction of the block should determine what happens with wide lines.  In
909             // particular with RTL blocks, wide lines should still spill out to the left.
910             if (style()->direction() == RTL && totWidth > availableWidth)
911                 x -= (totWidth - availableWidth);
912             numSpaces = 0;
913             break;
914         case JUSTIFY:
915             if (numSpaces != 0 && !bidi.current.atEnd() && !lineBox->endsWithBreak())
916                 break;
917             // fall through
918         case TAAUTO:
919             numSpaces = 0;
920             // for right to left fall through to right aligned
921             if (bidi.context->basicDir() == U_LEFT_TO_RIGHT)
922                 break;
923         case RIGHT:
924         case KHTML_RIGHT:
925             // Wide lines spill out of the block based off direction.
926             // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
927             // side of the block.
928             if (style()->direction() == RTL || totWidth < availableWidth)
929                 x += availableWidth - totWidth;
930             numSpaces = 0;
931             break;
932         case CENTER:
933         case KHTML_CENTER:
934             int xd = (availableWidth - totWidth)/2;
935             x += xd > 0 ? xd : 0;
936             numSpaces = 0;
937             break;
938     }
939
940     if (numSpaces > 0) {
941         for (r = sFirstBidiRun; r; r = r->nextRun) {
942             if (!r->box) continue;
943
944             int spaceAdd = 0;
945             if (numSpaces > 0 && r->obj->isText() && !r->compact) {
946                 // get the number of spaces in the run
947                 int spaces = 0;
948                 for ( int i = r->start; i < r->stop; i++ ) {
949                     UChar c = static_cast<RenderText*>(r->obj)->text()[i];
950                     if (c == ' ' || c == '\n' || c == '\t')
951                         spaces++;
952                 }
953
954                 ASSERT(spaces <= numSpaces);
955
956                 // Only justify text if whitespace is collapsed.
957                 if (r->obj->style()->collapseWhiteSpace()) {
958                     spaceAdd = (availableWidth - totWidth)*spaces/numSpaces;
959                     static_cast<InlineTextBox*>(r->box)->setSpaceAdd(spaceAdd);
960                     totWidth += spaceAdd;
961                 }
962                 numSpaces -= spaces;
963             }
964         }
965     }
966     
967     // The widths of all runs are now known.  We can now place every inline box (and
968     // compute accurate widths for the inline flow boxes).
969     int leftPosition = x;
970     int rightPosition = x;
971     needsWordSpacing = false;
972     lineBox->placeBoxesHorizontally(x, leftPosition, rightPosition, needsWordSpacing);
973     lineBox->setHorizontalOverflowPositions(leftPosition, rightPosition);
974 }
975
976 void RenderBlock::computeVerticalPositionsForLine(RootInlineBox* lineBox)
977 {
978     lineBox->verticallyAlignBoxes(m_height);
979     lineBox->setBlockHeight(m_height);
980
981     // See if the line spilled out.  If so set overflow height accordingly.
982     int bottomOfLine = lineBox->bottomOverflow();
983     if (bottomOfLine > m_height && bottomOfLine > m_overflowHeight)
984         m_overflowHeight = bottomOfLine;
985         
986     // Now make sure we place replaced render objects correctly.
987     for (BidiRun* r = sFirstBidiRun; r; r = r->nextRun) {
988         if (!r->box)
989             continue; // Skip runs with no line boxes.
990
991         // Align positioned boxes with the top of the line box.  This is
992         // a reasonable approximation of an appropriate y position.
993         if (r->obj->isPositioned())
994             r->box->setYPos(m_height);
995
996         // Position is used to properly position both replaced elements and
997         // to update the static normal flow x/y of positioned elements.
998         r->obj->position(r->box, r->start, r->stop - r->start, r->level%2, r->override);
999     }
1000 }
1001
1002 // collects one line of the paragraph and transforms it to visual order
1003 void RenderBlock::bidiReorderLine(const BidiIterator& start, const BidiIterator& end, BidiState& bidi)
1004 {
1005     if (start == end) {
1006         if (start.current() == '\n')
1007             m_height += lineHeight(m_firstLine, true);
1008         return;
1009     }
1010
1011     sFirstBidiRun = 0;
1012     sLastBidiRun = 0;
1013     sBidiRunCount = 0;
1014
1015     assert(bidi.dir == U_OTHER_NEUTRAL);
1016
1017     emptyRun = true;
1018
1019     bidi.eor.obj = 0;
1020
1021     numSpaces = 0;
1022
1023     bidi.current = start;
1024     bidi.last = bidi.current;
1025     bool pastEnd = false;
1026     BidiState stateAtEnd;
1027
1028     while (true) {
1029         UCharDirection dirCurrent;
1030         if (pastEnd && (previousLineBrokeCleanly || bidi.current.atEnd())) {
1031             BidiContext *c = bidi.context.get();
1032             while (c->parent)
1033                 c = c->parent;
1034             dirCurrent = c->dir();
1035             if (previousLineBrokeCleanly) {
1036                 // A deviation from the Unicode Bidi Algorithm in order to match
1037                 // Mac OS X text and WinIE: a hard line break resets bidi state.
1038                 stateAtEnd.context = c;
1039                 stateAtEnd.status.eor = dirCurrent;
1040                 stateAtEnd.status.last = dirCurrent;
1041                 stateAtEnd.status.lastStrong = dirCurrent;
1042             }
1043         } else {
1044             dirCurrent = bidi.current.direction();
1045             if (bidi.context->override
1046                     && dirCurrent != U_RIGHT_TO_LEFT_EMBEDDING
1047                     && dirCurrent != U_LEFT_TO_RIGHT_EMBEDDING
1048                     && dirCurrent != U_RIGHT_TO_LEFT_OVERRIDE
1049                     && dirCurrent != U_LEFT_TO_RIGHT_OVERRIDE
1050                     && dirCurrent != U_POP_DIRECTIONAL_FORMAT)
1051                 dirCurrent = bidi.context->dir();
1052             else if (dirCurrent == U_DIR_NON_SPACING_MARK)
1053                 dirCurrent = bidi.status.last;
1054         }
1055
1056         assert(bidi.status.eor != U_OTHER_NEUTRAL);
1057         switch (dirCurrent) {
1058
1059         // embedding and overrides (X1-X9 in the Bidi specs)
1060         case U_RIGHT_TO_LEFT_EMBEDDING:
1061         case U_LEFT_TO_RIGHT_EMBEDDING:
1062         case U_RIGHT_TO_LEFT_OVERRIDE:
1063         case U_LEFT_TO_RIGHT_OVERRIDE:
1064         case U_POP_DIRECTIONAL_FORMAT:
1065             embed(dirCurrent, bidi);
1066             break;
1067
1068             // strong types
1069         case U_LEFT_TO_RIGHT:
1070             switch(bidi.status.last) {
1071                 case U_RIGHT_TO_LEFT:
1072                 case U_RIGHT_TO_LEFT_ARABIC:
1073                 case U_EUROPEAN_NUMBER:
1074                 case U_ARABIC_NUMBER:
1075                     if (bidi.status.last != U_EUROPEAN_NUMBER || bidi.status.lastStrong != U_LEFT_TO_RIGHT)
1076                         appendRun(bidi);
1077                     break;
1078                 case U_LEFT_TO_RIGHT:
1079                     break;
1080                 case U_EUROPEAN_NUMBER_SEPARATOR:
1081                 case U_EUROPEAN_NUMBER_TERMINATOR:
1082                 case U_COMMON_NUMBER_SEPARATOR:
1083                 case U_BOUNDARY_NEUTRAL:
1084                 case U_BLOCK_SEPARATOR:
1085                 case U_SEGMENT_SEPARATOR:
1086                 case U_WHITE_SPACE_NEUTRAL:
1087                 case U_OTHER_NEUTRAL:
1088                     if (bidi.status.eor == U_EUROPEAN_NUMBER) {
1089                         if (bidi.status.lastStrong != U_LEFT_TO_RIGHT) {
1090                             // the numbers need to be on a higher embedding level, so let's close that run
1091                             bidi.dir = U_EUROPEAN_NUMBER;
1092                             appendRun(bidi);
1093                             if (bidi.context->dir() != U_LEFT_TO_RIGHT) {
1094                                 // the neutrals take the embedding direction, which is R
1095                                 bidi.eor = bidi.last;
1096                                 bidi.dir = U_RIGHT_TO_LEFT;
1097                                 appendRun(bidi);
1098                             }
1099                         }
1100                     } else if (bidi.status.eor == U_ARABIC_NUMBER) {
1101                         // Arabic numbers are always on a higher embedding level, so let's close that run
1102                         bidi.dir = U_ARABIC_NUMBER;
1103                         appendRun(bidi);
1104                         if (bidi.context->dir() != U_LEFT_TO_RIGHT) {
1105                             // the neutrals take the embedding direction, which is R
1106                             bidi.eor = bidi.last;
1107                             bidi.dir = U_RIGHT_TO_LEFT;
1108                             appendRun(bidi);
1109                         }
1110                     } else if(bidi.status.eor != U_LEFT_TO_RIGHT) {
1111                         //last stuff takes embedding dir
1112                         if (bidi.context->dir() != U_LEFT_TO_RIGHT && bidi.status.lastStrong != U_LEFT_TO_RIGHT) {
1113                             bidi.eor = bidi.last; 
1114                             bidi.dir = U_RIGHT_TO_LEFT; 
1115                         }
1116                         appendRun(bidi); 
1117                     }
1118                 default:
1119                     break;
1120             }
1121             bidi.eor = bidi.current;
1122             bidi.status.eor = U_LEFT_TO_RIGHT;
1123             bidi.status.lastStrong = U_LEFT_TO_RIGHT;
1124             bidi.dir = U_LEFT_TO_RIGHT;
1125             break;
1126         case U_RIGHT_TO_LEFT_ARABIC:
1127         case U_RIGHT_TO_LEFT:
1128             switch (bidi.status.last) {
1129                 case U_LEFT_TO_RIGHT:
1130                 case U_EUROPEAN_NUMBER:
1131                 case U_ARABIC_NUMBER:
1132                     appendRun(bidi);
1133                 case U_RIGHT_TO_LEFT:
1134                 case U_RIGHT_TO_LEFT_ARABIC:
1135                     break;
1136                 case U_EUROPEAN_NUMBER_SEPARATOR:
1137                 case U_EUROPEAN_NUMBER_TERMINATOR:
1138                 case U_COMMON_NUMBER_SEPARATOR:
1139                 case U_BOUNDARY_NEUTRAL:
1140                 case U_BLOCK_SEPARATOR:
1141                 case U_SEGMENT_SEPARATOR:
1142                 case U_WHITE_SPACE_NEUTRAL:
1143                 case U_OTHER_NEUTRAL:
1144                     if (bidi.status.eor != U_RIGHT_TO_LEFT && bidi.status.eor != U_RIGHT_TO_LEFT_ARABIC) {
1145                         //last stuff takes embedding dir
1146                         if (bidi.context->dir() != U_RIGHT_TO_LEFT && bidi.status.lastStrong != U_RIGHT_TO_LEFT 
1147                             && bidi.status.lastStrong != U_RIGHT_TO_LEFT_ARABIC) {
1148                             bidi.eor = bidi.last;
1149                             bidi.dir = U_LEFT_TO_RIGHT; 
1150                         }
1151                         appendRun(bidi);
1152                     }
1153                 default:
1154                     break;
1155             }
1156             bidi.eor = bidi.current;
1157             bidi.status.eor = U_RIGHT_TO_LEFT;
1158             bidi.status.lastStrong = dirCurrent;
1159             bidi.dir = U_RIGHT_TO_LEFT;
1160             break;
1161
1162             // weak types:
1163
1164         case U_EUROPEAN_NUMBER:
1165             if (bidi.status.lastStrong != U_RIGHT_TO_LEFT_ARABIC) {
1166                 // if last strong was AL change EN to AN
1167                 switch (bidi.status.last) {
1168                     case U_EUROPEAN_NUMBER:
1169                     case U_LEFT_TO_RIGHT:
1170                         break;
1171                     case U_RIGHT_TO_LEFT:
1172                     case U_RIGHT_TO_LEFT_ARABIC:
1173                     case U_ARABIC_NUMBER:
1174                         bidi.eor = bidi.last;
1175                         appendRun(bidi);
1176                         bidi.dir = U_EUROPEAN_NUMBER;
1177                         break;
1178                     case U_EUROPEAN_NUMBER_SEPARATOR:
1179                     case U_COMMON_NUMBER_SEPARATOR:
1180                         if (bidi.status.eor == U_EUROPEAN_NUMBER)
1181                             break;
1182                     case U_EUROPEAN_NUMBER_TERMINATOR:
1183                     case U_BOUNDARY_NEUTRAL:
1184                     case U_BLOCK_SEPARATOR:
1185                     case U_SEGMENT_SEPARATOR:
1186                     case U_WHITE_SPACE_NEUTRAL:
1187                     case U_OTHER_NEUTRAL:
1188                         if (bidi.status.eor == U_RIGHT_TO_LEFT) {
1189                             // neutrals go to R
1190                             bidi.eor = bidi.status.last == U_EUROPEAN_NUMBER_TERMINATOR ? bidi.lastBeforeET : bidi.last;
1191                             appendRun(bidi);
1192                             bidi.dir = U_EUROPEAN_NUMBER;
1193                         } else if (bidi.status.eor != U_LEFT_TO_RIGHT &&
1194                                  (bidi.status.eor != U_EUROPEAN_NUMBER || bidi.status.lastStrong != U_LEFT_TO_RIGHT) &&
1195                                  bidi.dir != U_LEFT_TO_RIGHT) {
1196                             // numbers on both sides, neutrals get right to left direction
1197                             appendRun(bidi);
1198                             bidi.eor = bidi.status.last == U_EUROPEAN_NUMBER_TERMINATOR ? bidi.lastBeforeET : bidi.last;
1199                             bidi.dir = U_RIGHT_TO_LEFT;
1200                             appendRun(bidi);
1201                             bidi.dir = U_EUROPEAN_NUMBER;
1202                         }
1203                     default:
1204                         break;
1205                 }
1206                 bidi.eor = bidi.current;
1207                 bidi.status.eor = U_EUROPEAN_NUMBER;
1208                 if (bidi.dir == U_OTHER_NEUTRAL)
1209                     bidi.dir = U_LEFT_TO_RIGHT;
1210                 break;
1211             }
1212         case U_ARABIC_NUMBER:
1213             dirCurrent = U_ARABIC_NUMBER;
1214             switch (bidi.status.last) {
1215                 case U_LEFT_TO_RIGHT:
1216                     if (bidi.context->dir() == U_LEFT_TO_RIGHT)
1217                         appendRun(bidi);
1218                     break;
1219                 case U_ARABIC_NUMBER:
1220                     break;
1221                 case U_RIGHT_TO_LEFT:
1222                 case U_RIGHT_TO_LEFT_ARABIC:
1223                 case U_EUROPEAN_NUMBER:
1224                     bidi.eor = bidi.last;
1225                     appendRun(bidi);
1226                     break;
1227                 case U_COMMON_NUMBER_SEPARATOR:
1228                     if (bidi.status.eor == U_ARABIC_NUMBER)
1229                         break;
1230                 case U_EUROPEAN_NUMBER_SEPARATOR:
1231                 case U_EUROPEAN_NUMBER_TERMINATOR:
1232                 case U_BOUNDARY_NEUTRAL:
1233                 case U_BLOCK_SEPARATOR:
1234                 case U_SEGMENT_SEPARATOR:
1235                 case U_WHITE_SPACE_NEUTRAL:
1236                 case U_OTHER_NEUTRAL:
1237                     if (bidi.status.eor != U_RIGHT_TO_LEFT && bidi.status.eor != U_RIGHT_TO_LEFT_ARABIC) {
1238                         // run of L before neutrals, neutrals take embedding dir (N2)
1239                         if (bidi.context->dir() == U_RIGHT_TO_LEFT || bidi.status.lastStrong == U_RIGHT_TO_LEFT 
1240                             || bidi.status.lastStrong == U_RIGHT_TO_LEFT_ARABIC) { 
1241                             // the embedding direction is R
1242                             // close the L run
1243                             appendRun(bidi);
1244                             // neutrals become an R run
1245                             bidi.dir = U_RIGHT_TO_LEFT;
1246                         } else {
1247                             // the embedding direction is L
1248                             // append neutrals to the L run and close it
1249                             bidi.dir = U_LEFT_TO_RIGHT; 
1250                         }
1251                     }
1252                     bidi.eor = bidi.last;
1253                     appendRun(bidi);
1254                 default:
1255                     break;
1256             }
1257             bidi.eor = bidi.current;
1258             bidi.status.eor = U_ARABIC_NUMBER;
1259             if (bidi.dir == U_OTHER_NEUTRAL)
1260                 bidi.dir = U_ARABIC_NUMBER;
1261             break;
1262         case U_EUROPEAN_NUMBER_SEPARATOR:
1263         case U_COMMON_NUMBER_SEPARATOR:
1264             break;
1265         case U_EUROPEAN_NUMBER_TERMINATOR:
1266             if (bidi.status.last == U_EUROPEAN_NUMBER) {
1267                 dirCurrent = U_EUROPEAN_NUMBER;
1268                 bidi.eor = bidi.current;
1269                 bidi.status.eor = dirCurrent;
1270             } else if (bidi.status.last != U_EUROPEAN_NUMBER_TERMINATOR)
1271                 bidi.lastBeforeET = emptyRun ? bidi.eor : bidi.last;
1272             break;
1273
1274         // boundary neutrals should be ignored
1275         case U_BOUNDARY_NEUTRAL:
1276             if (bidi.eor == bidi.last)
1277                 bidi.eor = bidi.current;
1278             break;
1279             // neutrals
1280         case U_BLOCK_SEPARATOR:
1281             // ### what do we do with newline and paragraph seperators that come to here?
1282             break;
1283         case U_SEGMENT_SEPARATOR:
1284             // ### implement rule L1
1285             break;
1286         case U_WHITE_SPACE_NEUTRAL:
1287             break;
1288         case U_OTHER_NEUTRAL:
1289             break;
1290         default:
1291             break;
1292         }
1293
1294         if (pastEnd) {
1295             if (bidi.eor == bidi.current) {
1296                 if (!bidi.reachedEndOfLine) {
1297                     bidi.eor = bidi.endOfLine;
1298                     switch (bidi.status.eor) {
1299                         case U_LEFT_TO_RIGHT:
1300                         case U_RIGHT_TO_LEFT:
1301                         case U_ARABIC_NUMBER:
1302                             bidi.dir = bidi.status.eor;
1303                             break;
1304                         case U_EUROPEAN_NUMBER:
1305                             bidi.dir = bidi.status.lastStrong == U_LEFT_TO_RIGHT ? U_LEFT_TO_RIGHT : U_EUROPEAN_NUMBER;
1306                             break;
1307                         default:
1308                             assert(false);
1309                     }
1310                     appendRun(bidi);
1311                 }
1312                 bidi = stateAtEnd;
1313                 bidi.dir = U_OTHER_NEUTRAL;
1314                 break;
1315             }
1316         }
1317
1318         // set status.last as needed.
1319         switch (dirCurrent) {
1320             case U_EUROPEAN_NUMBER_TERMINATOR:
1321                 if (bidi.status.last != U_EUROPEAN_NUMBER)
1322                     bidi.status.last = U_EUROPEAN_NUMBER_TERMINATOR;
1323                 break;
1324             case U_EUROPEAN_NUMBER_SEPARATOR:
1325             case U_COMMON_NUMBER_SEPARATOR:
1326             case U_SEGMENT_SEPARATOR:
1327             case U_WHITE_SPACE_NEUTRAL:
1328             case U_OTHER_NEUTRAL:
1329                 switch(bidi.status.last) {
1330                     case U_LEFT_TO_RIGHT:
1331                     case U_RIGHT_TO_LEFT:
1332                     case U_RIGHT_TO_LEFT_ARABIC:
1333                     case U_EUROPEAN_NUMBER:
1334                     case U_ARABIC_NUMBER:
1335                         bidi.status.last = dirCurrent;
1336                         break;
1337                     default:
1338                         bidi.status.last = U_OTHER_NEUTRAL;
1339                     }
1340                 break;
1341             case U_DIR_NON_SPACING_MARK:
1342             case U_BOUNDARY_NEUTRAL:
1343             case U_RIGHT_TO_LEFT_EMBEDDING:
1344             case U_LEFT_TO_RIGHT_EMBEDDING:
1345             case U_RIGHT_TO_LEFT_OVERRIDE:
1346             case U_LEFT_TO_RIGHT_OVERRIDE:
1347             case U_POP_DIRECTIONAL_FORMAT:
1348                 // ignore these
1349                 break;
1350             case U_EUROPEAN_NUMBER:
1351                 // fall through
1352             default:
1353                 bidi.status.last = dirCurrent;
1354         }
1355
1356         bidi.last = bidi.current;
1357
1358         if (emptyRun && !(dirCurrent == U_RIGHT_TO_LEFT_EMBEDDING
1359                 || dirCurrent == U_LEFT_TO_RIGHT_EMBEDDING
1360                 || dirCurrent == U_RIGHT_TO_LEFT_OVERRIDE
1361                 || dirCurrent == U_LEFT_TO_RIGHT_OVERRIDE
1362                 || dirCurrent == U_POP_DIRECTIONAL_FORMAT)) {
1363             bidi.sor = bidi.current;
1364             emptyRun = false;
1365         }
1366
1367         // this causes the operator ++ to open and close embedding levels as needed
1368         // for the CSS unicode-bidi property
1369         bidi.adjustEmbedding = true;
1370         bidi.current.increment(bidi);
1371         bidi.adjustEmbedding = false;
1372         if (emptyRun && (dirCurrent == U_RIGHT_TO_LEFT_EMBEDDING
1373                 || dirCurrent == U_LEFT_TO_RIGHT_EMBEDDING
1374                 || dirCurrent == U_RIGHT_TO_LEFT_OVERRIDE
1375                 || dirCurrent == U_LEFT_TO_RIGHT_OVERRIDE
1376                 || dirCurrent == U_POP_DIRECTIONAL_FORMAT)) {
1377             // exclude the embedding char itself from the new run so that ATSUI will never see it
1378             bidi.eor.obj = 0;
1379             bidi.last = bidi.current;
1380             bidi.sor = bidi.current;
1381         }
1382
1383         if (!pastEnd && (bidi.current == end || bidi.current.atEnd())) {
1384             if (emptyRun)
1385                 break;
1386             stateAtEnd = bidi;
1387             bidi.endOfLine = bidi.last;
1388             pastEnd = true;
1389         }
1390     }
1391
1392     sLogicallyLastBidiRun = sLastBidiRun;
1393
1394     // reorder line according to run structure...
1395     // do not reverse for visually ordered web sites
1396     if (!style()->visuallyOrdered()) {
1397
1398         // first find highest and lowest levels
1399         unsigned char levelLow = 128;
1400         unsigned char levelHigh = 0;
1401         BidiRun* r = sFirstBidiRun;
1402         while (r) {
1403             if (r->level > levelHigh)
1404                 levelHigh = r->level;
1405             if (r->level < levelLow)
1406                 levelLow = r->level;
1407             r = r->nextRun;
1408         }
1409
1410         // implements reordering of the line (L2 according to Bidi spec):
1411         // L2. From the highest level found in the text to the lowest odd level on each line,
1412         // reverse any contiguous sequence of characters that are at that level or higher.
1413
1414         // reversing is only done up to the lowest odd level
1415         if (!(levelLow%2))
1416             levelLow++;
1417
1418         int count = sBidiRunCount - 1;
1419
1420         while (levelHigh >= levelLow) {
1421             int i = 0;
1422             BidiRun* currRun = sFirstBidiRun;
1423             while (i < count) {
1424                 while (i < count && currRun && currRun->level < levelHigh) {
1425                     i++;
1426                     currRun = currRun->nextRun;
1427                 }
1428                 int start = i;
1429                 while (i <= count && currRun && currRun->level >= levelHigh) {
1430                     i++;
1431                     currRun = currRun->nextRun;
1432                 }
1433                 int end = i-1;
1434                 reverseRuns(start, end);
1435             }
1436             levelHigh--;
1437         }
1438     }
1439     bidi.endOfLine.obj = 0;
1440 }
1441
1442 static void buildCompactRuns(RenderObject* compactObj, BidiState& bidi)
1443 {
1444     sBuildingCompactRuns = true;
1445     if (!compactObj->isRenderBlock()) {
1446         // Just append a run for our object.
1447         isLineEmpty = false;
1448         addRun(new (compactObj->renderArena()) BidiRun(0, compactObj->length(), compactObj, bidi.context.get(), bidi.dir));
1449     }
1450     else {
1451         // Format the compact like it is its own single line.  We build up all the runs for
1452         // the little compact and then reorder them for bidi.
1453         RenderBlock* compactBlock = static_cast<RenderBlock*>(compactObj);
1454         bidi.adjustEmbedding = true;
1455         BidiIterator start(compactBlock, bidiFirst(compactBlock, bidi), 0);
1456         bidi.adjustEmbedding = false;
1457         BidiIterator end = start;
1458     
1459         betweenMidpoints = false;
1460         isLineEmpty = true;
1461         previousLineBrokeCleanly = true;
1462         
1463         end = compactBlock->findNextLineBreak(start, bidi);
1464         if (!isLineEmpty)
1465             compactBlock->bidiReorderLine(start, end, bidi);
1466     }
1467
1468     sCompactFirstBidiRun = sFirstBidiRun;
1469     sCompactLastBidiRun = sLastBidiRun;
1470     sCompactBidiRunCount = sBidiRunCount;
1471     
1472     sNumMidpoints = 0;
1473     sCurrMidpoint = 0;
1474     betweenMidpoints = false;
1475     sBuildingCompactRuns = false;
1476 }
1477
1478 IntRect RenderBlock::layoutInlineChildren(bool relayoutChildren)
1479 {
1480     BidiState bidi;
1481
1482     bool useRepaintRect = false;
1483     int repaintTop = 0;
1484     int repaintBottom = 0;
1485
1486     m_overflowHeight = 0;
1487     
1488     invalidateVerticalPositions();
1489     
1490     m_height = borderTop() + paddingTop();
1491     int toAdd = borderBottom() + paddingBottom();
1492     if (includeHorizontalScrollbarSize())
1493         toAdd += m_layer->horizontalScrollbarHeight();
1494     
1495     // Figure out if we should clear out our line boxes.
1496     // FIXME: Handle resize eventually!
1497     // FIXME: Do something better when floats are present.
1498     bool fullLayout = !firstLineBox() || !firstChild() || selfNeedsLayout() || relayoutChildren || containsFloats();
1499     if (fullLayout)
1500         deleteLineBoxes();
1501         
1502     // Text truncation only kicks in if your overflow isn't visible and your text-overflow-mode isn't
1503     // clip.
1504     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
1505     // difficult to figure out (especially in the middle of doing layout), and is really an esoteric pile of nonsense
1506     // anyway, so we won't worry about following the draft here.
1507     bool hasTextOverflow = style()->textOverflow() && hasOverflowClip();
1508     
1509     // Walk all the lines and delete our ellipsis line boxes if they exist.
1510     if (hasTextOverflow)
1511          deleteEllipsisLineBoxes();
1512
1513     if (firstChild()) {
1514         // layout replaced elements
1515         bool endOfInline = false;
1516         RenderObject *o = bidiFirst(this, bidi, false);
1517         bool hasFloat = false;
1518         while (o) {
1519             if (o->isReplaced() || o->isFloating() || o->isPositioned()) {
1520                 if (relayoutChildren || o->style()->width().isPercent() || o->style()->height().isPercent())
1521                     o->setChildNeedsLayout(true, false);
1522                 if (o->isPositioned())
1523                     o->containingBlock()->insertPositionedObject(o);
1524                 else {
1525                     if (o->isFloating())
1526                         hasFloat = true;
1527                     else if (fullLayout || o->needsLayout()) // Replaced elements
1528                         o->dirtyLineBoxes(fullLayout);
1529                     o->layoutIfNeeded();
1530                 }
1531             }
1532             else if (o->isText() || (o->isInlineFlow() && !endOfInline)) {
1533                 if (fullLayout || o->selfNeedsLayout())
1534                     o->dirtyLineBoxes(fullLayout);
1535                 o->setNeedsLayout(false);
1536             }
1537             o = bidiNext(this, o, bidi, false, &endOfInline);
1538         }
1539
1540         if (hasFloat)
1541             fullLayout = true; // FIXME: Will need to find a way to optimize floats some day.
1542         
1543         if (fullLayout && !selfNeedsLayout()) {
1544             setNeedsLayout(true, false);  // Mark ourselves as needing a full layout. This way we'll repaint like
1545                                           // we're supposed to.
1546             if (!document()->view()->needsFullRepaint() && m_layer) {
1547                 // Because we waited until we were already inside layout to discover
1548                 // that the block really needed a full layout, we missed our chance to repaint the layer
1549                 // before layout started.  Luckily the layer has cached the repaint rect for its original
1550                 // position and size, and so we can use that to make a repaint happen now.
1551                 RenderView* c = view();
1552                 if (c && !c->printingMode())
1553                     c->repaintViewRectangle(m_layer->repaintRect());
1554             }
1555         }
1556
1557         BidiContext *startEmbed;
1558         if (style()->direction() == LTR) {
1559             startEmbed = new BidiContext( 0, U_LEFT_TO_RIGHT, NULL, style()->unicodeBidi() == Override );
1560             bidi.status.eor = U_LEFT_TO_RIGHT;
1561         } else {
1562             startEmbed = new BidiContext( 1, U_RIGHT_TO_LEFT, NULL, style()->unicodeBidi() == Override );
1563             bidi.status.eor = U_RIGHT_TO_LEFT;
1564         }
1565
1566         bidi.status.lastStrong = startEmbed->dir();
1567         bidi.status.last = startEmbed->dir();
1568         bidi.status.eor = startEmbed->dir();
1569         bidi.context = startEmbed;
1570         bidi.dir = U_OTHER_NEUTRAL;
1571         
1572         if (!smidpoints)
1573             smidpoints = new Vector<BidiIterator>();
1574         
1575         sNumMidpoints = 0;
1576         sCurrMidpoint = 0;
1577         sCompactFirstBidiRun = sCompactLastBidiRun = 0;
1578         sCompactBidiRunCount = 0;
1579         
1580         // We want to skip ahead to the first dirty line
1581         BidiIterator start;
1582         RootInlineBox* startLine = determineStartPosition(fullLayout, start, bidi);
1583         
1584         // We also find the first clean line and extract these lines.  We will add them back
1585         // if we determine that we're able to synchronize after handling all our dirty lines.
1586         BidiIterator cleanLineStart;
1587         BidiStatus cleanLineBidiStatus;
1588         BidiContext* cleanLineBidiContext;
1589         int endLineYPos;
1590         RootInlineBox* endLine = (fullLayout || !startLine) ? 
1591                                  0 : determineEndPosition(startLine, cleanLineStart, cleanLineBidiStatus, cleanLineBidiContext, endLineYPos);
1592         if (endLine && cleanLineBidiContext)
1593             cleanLineBidiContext->ref();
1594         if (startLine) {
1595             useRepaintRect = true;
1596             repaintTop = m_height;
1597             repaintBottom = m_height;
1598             RenderArena* arena = renderArena();
1599             RootInlineBox* box = startLine;
1600             while (box) {
1601                 repaintTop = min(repaintTop, box->topOverflow());
1602                 repaintBottom = max(repaintBottom, box->bottomOverflow());
1603                 RootInlineBox* next = box->nextRootBox();
1604                 box->deleteLine(arena);
1605                 box = next;
1606             }
1607             startLine = 0;
1608         }
1609         
1610         BidiIterator end = start;
1611
1612         bool endLineMatched = false;
1613         while (!end.atEnd()) {
1614             start = end;
1615             if (endLine && (endLineMatched = matchedEndLine(start, bidi.status, bidi.context.get(), cleanLineStart, cleanLineBidiStatus, cleanLineBidiContext, endLine, endLineYPos, repaintBottom, repaintTop)))
1616                 break;
1617
1618             betweenMidpoints = false;
1619             isLineEmpty = true;
1620             if (m_firstLine && firstChild() && firstChild()->isCompact() && firstChild()->isRenderBlock()) {
1621                 buildCompactRuns(firstChild(), bidi);
1622                 start.obj = firstChild()->nextSibling();
1623                 end = start;
1624             }
1625             end = findNextLineBreak(start, bidi);
1626             if (start.atEnd())
1627                 break;
1628             if (!isLineEmpty) {
1629                 bidiReorderLine(start, end, bidi);
1630
1631                 // Now that the runs have been ordered, we create the line boxes.
1632                 // At the same time we figure out where border/padding/margin should be applied for
1633                 // inline flow boxes.
1634                 if (sCompactFirstBidiRun) {
1635                     // We have a compact line sharing this line.  Link the compact runs
1636                     // to our runs to create a single line of runs.
1637                     sCompactLastBidiRun->nextRun = sFirstBidiRun;
1638                     sFirstBidiRun = sCompactFirstBidiRun;
1639                     sBidiRunCount += sCompactBidiRunCount;
1640                 }
1641
1642                 RootInlineBox* lineBox = 0;
1643                 if (sBidiRunCount) {
1644                     lineBox = constructLine(start, end);
1645                     if (lineBox) {
1646                         lineBox->setEndsWithBreak(previousLineBrokeCleanly);
1647                         
1648                         // Now we position all of our text runs horizontally.
1649                         computeHorizontalPositionsForLine(lineBox, bidi);
1650         
1651                         // Now position our text runs vertically.
1652                         computeVerticalPositionsForLine(lineBox);
1653         
1654                         deleteBidiRuns(renderArena());
1655                     }
1656                 }
1657                 
1658                 if (end == start) {
1659                     bidi.adjustEmbedding = true;
1660                     end.increment(bidi);
1661                     bidi.adjustEmbedding = false;
1662                 }
1663
1664                 if (lineBox) {
1665                     lineBox->setLineBreakInfo(end.obj, end.pos, &bidi.status, bidi.context.get());
1666                     if (useRepaintRect) {
1667                         repaintTop = min(repaintTop, lineBox->topOverflow());
1668                         repaintBottom = max(repaintBottom, lineBox->bottomOverflow());
1669                     }
1670                 }
1671                 
1672                 m_firstLine = false;
1673                 newLine();
1674             }
1675              
1676             sNumMidpoints = 0;
1677             sCurrMidpoint = 0;
1678             sCompactFirstBidiRun = sCompactLastBidiRun = 0;
1679             sCompactBidiRunCount = 0;
1680         }
1681         
1682         if (endLine) {
1683             if (endLineMatched) {
1684                 // Attach all the remaining lines, and then adjust their y-positions as needed.
1685                 for (RootInlineBox* line = endLine; line; line = line->nextRootBox())
1686                     line->attachLine();
1687                 
1688                 // Now apply the offset to each line if needed.
1689                 int delta = m_height - endLineYPos;
1690                 if (delta) {
1691                     for (RootInlineBox* line = endLine; line; line = line->nextRootBox()) {
1692                         repaintTop = min(repaintTop, line->topOverflow() + (delta < 0 ? delta : 0));
1693                         repaintBottom = max(repaintBottom, line->bottomOverflow() + (delta > 0 ? delta : 0));
1694                         line->adjustPosition(0, delta);
1695                     }
1696                 }
1697                 m_height = lastRootBox()->blockHeight();
1698             } else {
1699                 // Delete all the remaining lines.
1700                 InlineRunBox* line = endLine;
1701                 RenderArena* arena = renderArena();
1702                 while (line) {
1703                     repaintTop = min(repaintTop, line->topOverflow());
1704                     repaintBottom = max(repaintBottom, line->bottomOverflow());
1705                     InlineRunBox* next = line->nextLineBox();
1706                     line->deleteLine(arena);
1707                     line = next;
1708                 }
1709             }
1710             if (cleanLineBidiContext)
1711                 cleanLineBidiContext->deref();
1712         }
1713     }
1714
1715     sNumMidpoints = 0;
1716     sCurrMidpoint = 0;
1717
1718     // in case we have a float on the last line, it might not be positioned up to now.
1719     // This has to be done before adding in the bottom border/padding, or the float will
1720     // include the padding incorrectly. -dwh
1721     positionNewFloats();
1722     
1723     // Now add in the bottom border/padding.
1724     m_height += toAdd;
1725
1726     // Always make sure this is at least our height.
1727     m_overflowHeight = max(m_height, m_overflowHeight);
1728     
1729     // See if any lines spill out of the block.  If so, we need to update our overflow width.
1730     checkLinesForOverflow();
1731
1732     IntRect repaintRect(0, 0, 0, 0);
1733     if (useRepaintRect) {
1734         repaintRect.setX(m_overflowLeft);
1735         repaintRect.setWidth(m_overflowWidth - m_overflowLeft);
1736         repaintRect.setY(repaintTop);
1737         repaintRect.setHeight(repaintBottom - repaintTop);
1738         if (hasOverflowClip())
1739             // Don't allow this rect to spill out of our overflow box.
1740             repaintRect.intersect(IntRect(0, 0, m_width, m_height));
1741     }
1742
1743     if (!firstLineBox() && hasLineIfEmpty())
1744         m_height += lineHeight(true);
1745
1746     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
1747     // truncate text.
1748     if (hasTextOverflow)
1749         checkLinesForTextOverflow();
1750
1751     return repaintRect;
1752
1753 #if BIDI_DEBUG > 1
1754     kdDebug(6041) << " ------- bidi end " << this << " -------" << endl;
1755 #endif
1756 }
1757
1758 RootInlineBox* RenderBlock::determineStartPosition(bool fullLayout, BidiIterator& start, BidiState& bidi)
1759 {
1760     RootInlineBox* curr = 0;
1761     RootInlineBox* last = 0;
1762     RenderObject* startObj = 0;
1763     int pos = 0;
1764     
1765     if (fullLayout) {
1766         // Nuke all our lines.
1767         if (firstRootBox()) {
1768             RenderArena* arena = renderArena();
1769             curr = firstRootBox(); 
1770             while (curr) {
1771                 RootInlineBox* next = curr->nextRootBox();
1772                 curr->deleteLine(arena);
1773                 curr = next;
1774             }
1775             ASSERT(!m_firstLineBox && !m_lastLineBox);
1776         }
1777     } else {
1778         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox());
1779         if (curr) {
1780             // We have a dirty line.
1781             if (curr->prevRootBox()) {
1782                 // We have a previous line.
1783                 if (!curr->prevRootBox()->endsWithBreak())
1784                     curr = curr->prevRootBox();  // The previous line didn't break cleanly, so treat it as dirty also.
1785             }
1786         } else {
1787             // No dirty lines were found.
1788             // If the last line didn't break cleanly, treat it as dirty.
1789             if (lastRootBox() && !lastRootBox()->endsWithBreak())
1790                 curr = lastRootBox();
1791         }
1792         
1793         // If we have no dirty lines, then last is just the last root box.
1794         last = curr ? curr->prevRootBox() : lastRootBox();
1795     }
1796     
1797     m_firstLine = !last;
1798     previousLineBrokeCleanly = !last || last->endsWithBreak();
1799     if (last) {
1800         m_height = last->blockHeight();
1801         startObj = last->lineBreakObj();
1802         pos = last->lineBreakPos();
1803         bidi.status = last->lineBreakBidiStatus();
1804         bidi.context = last->lineBreakBidiContext();
1805     } else {
1806         bidi.adjustEmbedding = true;
1807         startObj = bidiFirst(this, bidi, 0);
1808         bidi.adjustEmbedding = false;
1809     }
1810         
1811     start = BidiIterator(this, startObj, pos);
1812     
1813     return curr;
1814 }
1815
1816 RootInlineBox* RenderBlock::determineEndPosition(RootInlineBox* startLine, BidiIterator& cleanLineStart,
1817                                                  BidiStatus& cleanLineBidiStatus, BidiContext*& cleanLineBidiContext,
1818                                                  int& yPos)
1819 {
1820     RootInlineBox* last = 0;
1821     if (!startLine)
1822         last = 0;
1823     else {
1824         for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
1825             if (curr->isDirty())
1826                 last = 0;
1827             else if (!last)
1828                 last = curr;
1829         }
1830     }
1831     
1832     if (!last)
1833         return 0;
1834     
1835     RootInlineBox* prev = last->prevRootBox();
1836     cleanLineStart = BidiIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
1837     cleanLineBidiStatus = prev->lineBreakBidiStatus();
1838     cleanLineBidiContext = prev->lineBreakBidiContext();
1839     yPos = prev->blockHeight();
1840     
1841     for (RootInlineBox* line = last; line; line = line->nextRootBox())
1842         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
1843                              // their connections to one another.
1844     
1845     return last;
1846 }
1847
1848 bool RenderBlock::matchedEndLine(const BidiIterator& start, const BidiStatus& status, BidiContext* context,
1849                                  const BidiIterator& endLineStart, const BidiStatus& endLineStatus, BidiContext* endLineContext, 
1850                                  RootInlineBox*& endLine, int& endYPos, int& repaintBottom, int& repaintTop)
1851 {
1852     if (start == endLineStart)
1853         return status == endLineStatus && *context == *endLineContext;
1854     else {
1855         // The first clean line doesn't match, but we can check a handful of following lines to try
1856         // to match back up.
1857         static int numLines = 8; // The # of lines we're willing to match against.
1858         RootInlineBox* line = endLine;
1859         for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
1860             if (line->lineBreakObj() == start.obj && line->lineBreakPos() == start.pos) {
1861                 // We have a match.
1862                 if (line->lineBreakBidiStatus() != status || *line->lineBreakBidiContext() != *context)
1863                     return false; // ...but the bidi state doesn't match.
1864                 RootInlineBox* result = line->nextRootBox();
1865                                 
1866                 // Set our yPos to be the block height of endLine.
1867                 if (result)
1868                     endYPos = line->blockHeight();
1869                 
1870                 // Now delete the lines that we failed to sync.
1871                 RootInlineBox* boxToDelete = endLine;
1872                 RenderArena* arena = renderArena();
1873                 while (boxToDelete && boxToDelete != result) {
1874                     repaintTop = min(repaintTop, boxToDelete->topOverflow());
1875                     repaintBottom = max(repaintBottom, boxToDelete->bottomOverflow());
1876                     RootInlineBox* next = boxToDelete->nextRootBox();
1877                     boxToDelete->deleteLine(arena);
1878                     boxToDelete = next;
1879                 }
1880
1881                 endLine = result;
1882                 return result;
1883             }
1884         }
1885     }
1886     return false;
1887 }
1888
1889 static const unsigned short nonBreakingSpace = 0xa0;
1890
1891 static inline bool skipNonBreakingSpace(BidiIterator &it)
1892 {
1893     if (it.obj->style()->nbspMode() != SPACE || it.current() != nonBreakingSpace)
1894         return false;
1895  
1896     // FIXME: This is bad.  It makes nbsp inconsistent with space and won't work correctly
1897     // with m_minWidth/m_maxWidth.
1898     // Do not skip a non-breaking space if it is the first character
1899     // on a line after a clean line break (or on the first line, since previousLineBrokeCleanly starts off
1900     // |true|).
1901     if (isLineEmpty && previousLineBrokeCleanly)
1902         return false;
1903     
1904     return true;
1905 }
1906
1907 static inline bool shouldCollapseWhiteSpace(const RenderStyle* style)
1908 {
1909     return style->collapseWhiteSpace() || (style->whiteSpace() == PRE_WRAP && (!isLineEmpty || !previousLineBrokeCleanly));
1910 }
1911
1912 int RenderBlock::skipWhitespace(BidiIterator &it, BidiState &bidi)
1913 {
1914     // FIXME: The entire concept of the skipWhitespace function is flawed, since we really need to be building
1915     // line boxes even for containers that may ultimately collapse away.  Otherwise we'll never get positioned
1916     // elements quite right.  In other words, we need to build this function's work into the normal line
1917     // object iteration process.
1918     int w = lineWidth(m_height);
1919     while (!it.atEnd() && (it.obj->isInlineFlow() || (shouldCollapseWhiteSpace(it.obj->style()) && !it.obj->isBR() &&
1920           (it.current() == ' ' || it.current() == '\t' || (!it.obj->style()->preserveNewline() && it.current() == '\n') ||
1921           it.current() == SOFT_HYPHEN || skipNonBreakingSpace(it) || it.obj->isFloatingOrPositioned())))) {
1922         if (it.obj->isFloatingOrPositioned()) {
1923             RenderObject *o = it.obj;
1924             // add to special objects...
1925             if (o->isFloating()) {
1926                 insertFloatingObject(o);
1927                 positionNewFloats();
1928                 w = lineWidth(m_height);
1929             }
1930             else if (o->isPositioned()) {
1931                 // FIXME: The math here is actually not really right.  It's a best-guess approximation that
1932                 // will work for the common cases
1933                 RenderObject* c = o->container();
1934                 if (c->isInlineFlow()) {
1935                     // A relative positioned inline encloses us.  In this case, we also have to determine our
1936                     // position as though we were an inline.  Set |staticX| and |staticY| on the relative positioned
1937                     // inline so that we can obtain the value later.
1938                     c->setStaticX(style()->direction() == LTR ?
1939                                   leftOffset(m_height) : rightOffset(m_height));
1940                     c->setStaticY(m_height);
1941                 }
1942                 
1943                 if (o->hasStaticX()) {
1944                     bool wasInline = o->style()->isOriginalDisplayInlineType();
1945                     if (wasInline)
1946                         o->setStaticX(style()->direction() == LTR ?
1947                                       leftOffset(m_height) :
1948                                       width() - rightOffset(m_height));
1949                     else
1950                         o->setStaticX(style()->direction() == LTR ?
1951                                       borderLeft() + paddingLeft() :
1952                                       borderRight() + paddingRight());
1953                 }
1954                 if (o->hasStaticY())
1955                     o->setStaticY(m_height);
1956             }
1957         }
1958         
1959         bidi.adjustEmbedding = true;
1960         it.increment(bidi);
1961         bidi.adjustEmbedding = false;
1962     }
1963     return w;
1964 }
1965
1966 BidiIterator RenderBlock::findNextLineBreak(BidiIterator &start, BidiState &bidi)
1967 {
1968     // eliminate spaces at beginning of line
1969     int width = skipWhitespace(start, bidi);
1970     int w = 0;
1971     int tmpW = 0;
1972
1973     if (start.atEnd())
1974         return start;
1975
1976     // This variable is used only if whitespace isn't set to PRE, and it tells us whether
1977     // or not we are currently ignoring whitespace.
1978     bool ignoringSpaces = false;
1979     BidiIterator ignoreStart;
1980     
1981     // This variable tracks whether the very last character we saw was a space.  We use
1982     // this to detect when we encounter a second space so we know we have to terminate
1983     // a run.
1984     bool currentCharacterIsSpace = false;
1985     bool currentCharacterIsWS = false;
1986     RenderObject* trailingSpaceObject = 0;
1987
1988     BidiIterator lBreak = start;
1989
1990     RenderObject *o = start.obj;
1991     RenderObject *last = o;
1992     RenderObject *previous = o;
1993     int pos = start.pos;
1994
1995     bool prevLineBrokeCleanly = previousLineBrokeCleanly;
1996     previousLineBrokeCleanly = false;
1997     
1998     while (o) {
1999         if (o->isBR()) {
2000             if (w + tmpW <= width) {
2001                 lBreak.obj = o;
2002                 lBreak.pos = 0;
2003                 lBreak.increment(bidi);
2004
2005                 // A <br> always breaks a line, so don't let the line be collapsed
2006                 // away. Also, the space at the end of a line with a <br> does not
2007                 // get collapsed away.  It only does this if the previous line broke
2008                 // cleanly.  Otherwise the <br> has no effect on whether the line is
2009                 // empty or not.
2010                 if (prevLineBrokeCleanly)
2011                     isLineEmpty = false;
2012                 trailingSpaceObject = 0;
2013                 previousLineBrokeCleanly = true;
2014
2015                 if (!isLineEmpty) {
2016                     // only check the clear status for non-empty lines.
2017                     EClear clear = o->style()->clear();
2018                     if (clear != CNONE)
2019                         m_clearStatus = (EClear) (m_clearStatus | clear);
2020                 }
2021             }
2022             goto end;
2023         }
2024         if (o->isFloatingOrPositioned()) {
2025             // add to special objects...
2026             if (o->isFloating()) {
2027                 insertFloatingObject(o);
2028                 // check if it fits in the current line.
2029                 // If it does, position it now, otherwise, position
2030                 // it after moving to next line (in newLine() func)
2031                 if (o->width()+o->marginLeft()+o->marginRight()+w+tmpW <= width) {
2032                     positionNewFloats();
2033                     width = lineWidth(m_height);
2034                 }
2035             } else if (o->isPositioned()) {
2036                 // If our original display wasn't an inline type, then we can
2037                 // go ahead and determine our static x position now.
2038                 bool isInlineType = o->style()->isOriginalDisplayInlineType();
2039                 bool needToSetStaticX = o->hasStaticX();
2040                 if (o->hasStaticX() && !isInlineType) {
2041                     o->setStaticX(o->parent()->style()->direction() == LTR ?
2042                                   borderLeft()+paddingLeft() :
2043                                   borderRight()+paddingRight());
2044                     needToSetStaticX = false;
2045                 }
2046
2047                 // If our original display was an INLINE type, then we can go ahead
2048                 // and determine our static y position now.
2049                 bool needToSetStaticY = o->hasStaticY();
2050                 if (o->hasStaticY() && isInlineType) {
2051                     o->setStaticY(m_height);
2052                     needToSetStaticY = false;
2053                 }
2054                 
2055                 bool needToCreateLineBox = needToSetStaticX || needToSetStaticY;
2056                 RenderObject* c = o->container();
2057                 if (c->isInlineFlow() && (!needToSetStaticX || !needToSetStaticY))
2058                     needToCreateLineBox = true;
2059
2060                 // If we're ignoring spaces, we have to stop and include this object and
2061                 // then start ignoring spaces again.
2062                 if (needToCreateLineBox) {
2063                     trailingSpaceObject = 0;
2064                     ignoreStart.obj = o;
2065                     ignoreStart.pos = 0;
2066                     if (ignoringSpaces) {
2067                         addMidpoint(ignoreStart); // Stop ignoring spaces.
2068                         addMidpoint(ignoreStart); // Start ignoring again.
2069                     }
2070                     
2071                 }
2072             }
2073         } else if (o->isInlineFlow()) {
2074             // Only empty inlines matter.  We treat those similarly to replaced elements.
2075             assert(!o->firstChild());
2076             tmpW += o->marginLeft()+o->borderLeft()+o->paddingLeft()+
2077                     o->marginRight()+o->borderRight()+o->paddingRight();
2078         } else if (o->isReplaced()) {
2079             EWhiteSpace currWS = o->style()->whiteSpace();
2080             EWhiteSpace lastWS = last->style()->whiteSpace();
2081             
2082             // WinIE marquees have different whitespace characteristics by default when viewed from
2083             // the outside vs. the inside.  Text inside is NOWRAP, and so we altered the marquee's
2084             // style to reflect this, but we now have to get back to the original whitespace value
2085             // for the marquee when checking for line breaking.
2086             if (o->isHTMLMarquee() && o->layer() && o->layer()->marquee())
2087                 currWS = o->layer()->marquee()->whiteSpace();
2088             if (last->isHTMLMarquee() && last->layer() && last->layer()->marquee())
2089                 lastWS = last->layer()->marquee()->whiteSpace();
2090             
2091             // Break on replaced elements if either has normal white-space.
2092             // FIXME: This does not match WinIE, Opera, and Mozilla.  They treat replaced elements
2093             // like characters in a word, and require spaces between the replaced elements in order
2094             // to break.
2095             if (RenderStyle::autoWrap(currWS) || RenderStyle::autoWrap(lastWS)) {
2096                 w += tmpW;
2097                 tmpW = 0;
2098                 lBreak.obj = o;
2099                 lBreak.pos = 0;
2100             }
2101
2102             if (ignoringSpaces) {
2103                 BidiIterator startMid( 0, o, 0 );
2104                 addMidpoint(startMid);
2105             }
2106             isLineEmpty = false;
2107             ignoringSpaces = false;
2108             currentCharacterIsSpace = false;
2109             currentCharacterIsWS = false;
2110             trailingSpaceObject = 0;
2111             
2112             if (o->isListMarker() && o->style()->listStylePosition() == OUTSIDE) {
2113                 // The marker must not have an effect on whitespace at the start
2114                 // of the line.  We start ignoring spaces to make sure that any additional
2115                 // spaces we see will be discarded. 
2116                 //
2117                 // Optimize for a common case. If we can't find whitespace after the list
2118                 // item, then this is all moot. -dwh
2119                 RenderObject* next = bidiNext(start.block, o, bidi);
2120                 if (style()->collapseWhiteSpace() && next && !next->isBR() && next->isText() && static_cast<RenderText*>(next)->stringLength() > 0) {
2121                     RenderText *nextText = static_cast<RenderText*>(next);
2122                     UChar nextChar = nextText->text()[0];
2123                     if (nextText->style()->isCollapsibleWhiteSpace(nextChar)) {
2124                         currentCharacterIsSpace = true;
2125                         currentCharacterIsWS = true;
2126                         ignoringSpaces = true;
2127                         BidiIterator endMid( 0, o, 0 );
2128                         addMidpoint(endMid);
2129                     }
2130                 }
2131             } else
2132                 tmpW += o->width()+o->marginLeft()+o->marginRight()+inlineWidth(o);
2133         } else if (o->isText()) {
2134             RenderText *t = static_cast<RenderText *>(o);
2135             int strlen = t->stringLength();
2136             int len = strlen - pos;
2137             const UChar* str = t->text();
2138
2139             const Font *f = t->font(m_firstLine);
2140             // proportional font, needs a bit more work.
2141             int lastSpace = pos;
2142             int wordSpacing = o->style()->wordSpacing();
2143             int lastSpaceWordSpacing = 0;
2144
2145             bool appliedStartWidth = pos > 0; // If the span originated on a previous line,
2146                                               // then assume the start width has been applied.
2147             int wrapW = tmpW + inlineWidth(o, !appliedStartWidth, true);
2148             int nextBreakable = -1;
2149
2150             while (len) {
2151                 bool previousCharacterIsSpace = currentCharacterIsSpace;
2152                 bool previousCharacterIsWS = currentCharacterIsWS;
2153                 UChar c = str[pos];
2154                 currentCharacterIsSpace = c == ' ' || c == '\t' || (!o->style()->preserveNewline() && (c == '\n'));
2155
2156                 if (!o->style()->collapseWhiteSpace() || !currentCharacterIsSpace)
2157                     isLineEmpty = false;
2158                 
2159                 // Check for soft hyphens.  Go ahead and ignore them.
2160                 if (c == SOFT_HYPHEN) {
2161                     if (!ignoringSpaces) {
2162                         // Ignore soft hyphens
2163                         BidiIterator endMid;
2164                         if (pos > 0)
2165                             endMid = BidiIterator(0, o, pos-1);
2166                         else
2167                             endMid = BidiIterator(0, previous, previous->isText() ? static_cast<RenderText *>(previous)->stringLength() - 1 : 0);
2168                         // Two consecutive soft hyphens. Avoid overlapping midpoints.
2169                         if (sNumMidpoints && smidpoints->at(sNumMidpoints - 1).obj == endMid.obj && smidpoints->at(sNumMidpoints - 1).pos > endMid.pos)
2170                             sNumMidpoints--;
2171                         else
2172                             addMidpoint(endMid);
2173                         
2174                         // Add the width up to but not including the hyphen.
2175                         tmpW += t->width(lastSpace, pos - lastSpace, f, w+tmpW) + lastSpaceWordSpacing;
2176                         
2177                         // For wrapping text only, include the hyphen.  We need to ensure it will fit
2178                         // on the line if it shows when we break.
2179                         if (o->style()->autoWrap())
2180                             tmpW += t->width(pos, 1, f, w+tmpW);
2181                         
2182                         BidiIterator startMid(0, o, pos+1);
2183                         addMidpoint(startMid);
2184                     }
2185                     
2186                     pos++;
2187                     len--;
2188                     lastSpaceWordSpacing = 0;
2189                     lastSpace = pos; // Cheesy hack to prevent adding in widths of the run twice.
2190                     continue;
2191                 }
2192                 
2193                 bool applyWordSpacing = false;
2194                 bool allowBreak = o->style()->autoWrap();
2195                 bool breakNBSP = allowBreak && o->style()->nbspMode() == SPACE;
2196                 
2197                 // FIXME: This check looks suspicious. Why does w have to be 0?  
2198                 bool breakWords = o->style()->wordWrap() == BREAK_WORD && ((allowBreak && w == 0) || o->style()->whiteSpace() == PRE);
2199
2200                 currentCharacterIsWS = currentCharacterIsSpace || (breakNBSP && c == nonBreakingSpace);
2201
2202                 if (breakWords)
2203                     wrapW += t->width(pos, 1, f, w+wrapW);
2204                 bool midWordBreak = breakWords && (w + wrapW > width);
2205
2206                 if (c == '\n' || (o->style()->whiteSpace() != PRE && isBreakable(str, pos, strlen, nextBreakable, breakNBSP)) || midWordBreak) {
2207                     bool stoppedIgnoringSpaces = false;
2208                     if (ignoringSpaces) {
2209                         if (!currentCharacterIsSpace) {
2210                             // Stop ignoring spaces and begin at this
2211                             // new point.
2212                             ignoringSpaces = false;
2213                             lastSpaceWordSpacing = 0;
2214                             lastSpace = pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
2215                             BidiIterator startMid ( 0, o, pos );
2216                             addMidpoint(startMid);
2217                             stoppedIgnoringSpaces = true;
2218                         } else {
2219                             // Just keep ignoring these spaces.
2220                             pos++;
2221                             len--;
2222                             continue;
2223                         }
2224                     }
2225
2226                     int additionalTmpW = t->width(lastSpace, pos - lastSpace, f, w+tmpW) + lastSpaceWordSpacing;
2227                     tmpW += additionalTmpW;
2228                     if (!appliedStartWidth) {
2229                         tmpW += inlineWidth(o, true, false);
2230                         appliedStartWidth = true;
2231                     }
2232                     
2233                     applyWordSpacing =  wordSpacing && currentCharacterIsSpace && !previousCharacterIsSpace;
2234
2235                     if (o->style()->autoWrap() && w + tmpW > width && w == 0) {
2236                         int fb = nearestFloatBottom(m_height);
2237                         int newLineWidth = lineWidth(fb);
2238                         // See if |tmpW| will fit on the new line.  As long as it does not,
2239                         // keep adjusting our float bottom until we find some room.
2240                         int lastFloatBottom = m_height;
2241                         while (lastFloatBottom < fb && tmpW > newLineWidth) {
2242                             lastFloatBottom = fb;
2243                             fb = nearestFloatBottom(fb);
2244                             newLineWidth = lineWidth(fb);
2245                         }
2246                         
2247                         if (!w && m_height < fb && width < newLineWidth) {
2248                             m_height = fb;
2249                             width = newLineWidth;
2250                         }
2251                     }
2252         
2253                     if (o->style()->autoWrap() || breakWords) {
2254                         // If we break only after white-space, consider the current character
2255                         // as candidate width for this line.
2256                         int charWidth = o->style()->breakOnlyAfterWhiteSpace() && !midWordBreak ?
2257                                             t->width(pos, 1, f, w + tmpW) + (applyWordSpacing ? wordSpacing : 0) : 0;
2258                         if (w + tmpW + charWidth > width) {
2259                             if (o->style()->breakOnlyAfterWhiteSpace() && !midWordBreak) {
2260                                 // Check if line is too big even without the extra space
2261                                 // at the end of the line. If it is not, do nothing. 
2262                                 // If the line needs the extra whitespace to be too long, 
2263                                 // then move the line break to the space and skip all 
2264                                 // additional whitespace.
2265                                 if (w + tmpW <= width) {
2266                                     lBreak.obj = o;
2267                                     lBreak.pos = pos;
2268                                     if (pos > 0) {
2269                                         // Separate the trailing space into its own box, which we will
2270                                         // resize to fit on the line in computeHorizontalPositionsForLine().
2271                                         BidiIterator midpoint(0, o, pos);
2272                                         addMidpoint(BidiIterator(0, o, pos-1)); // Stop
2273                                         addMidpoint(BidiIterator(0, o, pos)); // Start
2274                                     }
2275                                     skipWhitespace(lBreak, bidi);
2276                                 }
2277                             }
2278                             if (lBreak.obj && lBreak.obj->style()->preserveNewline() && lBreak.obj->isText() && static_cast<RenderText*>(lBreak.obj)->text()[lBreak.pos] == '\n') {
2279                                 if (!stoppedIgnoringSpaces && pos > 0) {
2280                                     // We need to stop right before the newline and then start up again.
2281                                     BidiIterator midpoint(0, o, pos);
2282                                     addMidpoint(BidiIterator(0, o, pos-1)); // Stop
2283                                     addMidpoint(BidiIterator(0, o, pos)); // Start
2284                                 }
2285                                 lBreak.increment(bidi);
2286                                 previousLineBrokeCleanly = true;
2287                             }
2288                             goto end; // Didn't fit. Jump to the end.
2289                         } else {
2290                             if (midWordBreak)
2291                                 tmpW -= additionalTmpW;
2292                             if (pos > 0 && str[pos-1] == SOFT_HYPHEN)
2293                                 // Subtract the width of the soft hyphen out since we fit on a line.
2294                                 tmpW -= t->width(pos-1, 1, f, w+tmpW);
2295                         }
2296                     }
2297
2298                     if (c == '\n' && o->style()->preserveNewline()) {
2299                         if (!stoppedIgnoringSpaces && pos > 0) {
2300                             // We need to stop right before the newline and then start up again.
2301                             BidiIterator midpoint(0, o, pos);
2302                             addMidpoint(BidiIterator(0, o, pos-1)); // Stop
2303                             addMidpoint(BidiIterator(0, o, pos)); // Start
2304                         }
2305                         lBreak.obj = o;
2306                         lBreak.pos = pos;
2307                         lBreak.increment(bidi);
2308                         previousLineBrokeCleanly = true;
2309                         return lBreak;
2310                     }
2311
2312                     if (o->style()->autoWrap()) {
2313                         w += tmpW;
2314                         tmpW = 0;
2315                         lBreak.obj = o;
2316                         lBreak.pos = pos;
2317                     }
2318                     
2319                     if (midWordBreak) {
2320                         // Remember this as a breakable position in case
2321                         // adding the end width forces a break.
2322                         lBreak.obj = o;
2323                         lBreak.pos = pos;
2324                     } else {
2325                         lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
2326                         lastSpace = pos;
2327                     }
2328                     
2329                     if (!ignoringSpaces && o->style()->collapseWhiteSpace()) {
2330                         // If we encounter a newline, or if we encounter a
2331                         // second space, we need to go ahead and break up this
2332                         // run and enter a mode where we start collapsing spaces.
2333                         if (currentCharacterIsSpace && previousCharacterIsSpace) {
2334                             ignoringSpaces = true;
2335                             
2336                             // We just entered a mode where we are ignoring
2337                             // spaces. Create a midpoint to terminate the run
2338                             // before the second space. 
2339                             addMidpoint(ignoreStart);
2340                         }
2341                     }
2342                 } else if (ignoringSpaces) {
2343                     // Stop ignoring spaces and begin at this
2344                     // new point.
2345                     ignoringSpaces = false;
2346                     lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
2347                     lastSpace = pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
2348                     BidiIterator startMid(0, o, pos);
2349                     addMidpoint(startMid);
2350                 }
2351
2352                 if (currentCharacterIsSpace && !previousCharacterIsSpace) {
2353                     ignoreStart.obj = o;
2354                     ignoreStart.pos = pos;
2355                 }
2356
2357                 if (!currentCharacterIsWS && previousCharacterIsWS) {
2358                     if (o->style()->autoWrap() && o->style()->breakOnlyAfterWhiteSpace()) {
2359                         lBreak.obj = o;
2360                         lBreak.pos = pos;
2361                     }
2362                 }
2363                 
2364                 if (o->style()->collapseWhiteSpace() && currentCharacterIsSpace && !ignoringSpaces)
2365                     trailingSpaceObject = o;
2366                 else if (!o->style()->collapseWhiteSpace() || !currentCharacterIsSpace)
2367                     trailingSpaceObject = 0;
2368                     
2369                 pos++;
2370                 len--;
2371             }
2372             
2373             // IMPORTANT: pos is > length here!
2374             if (!ignoringSpaces)
2375                 tmpW += t->width(lastSpace, pos - lastSpace, f, w+tmpW) + lastSpaceWordSpacing;
2376             if (!appliedStartWidth)
2377                 tmpW += inlineWidth(o, true, false);
2378             tmpW += inlineWidth(o, false, true);
2379         } else
2380             ASSERT( false );
2381
2382         RenderObject* next = bidiNext(start.block, o, bidi);
2383         bool autoWrap = o->style()->autoWrap();
2384         bool checkForBreak = autoWrap;
2385         if (w && w + tmpW > width && lBreak.obj && o->style()->whiteSpace() == NOWRAP)
2386             checkForBreak = true;
2387         else if (next && o->isText() && next->isText() && !next->isBR()) {
2388             if (autoWrap || (next->style()->autoWrap())) {
2389                 if (currentCharacterIsSpace)
2390                     checkForBreak = true;
2391                 else {
2392                     checkForBreak = false;
2393                     RenderText* nextText = static_cast<RenderText*>(next);
2394                     if (nextText->stringLength() != 0) {
2395                         UChar c = nextText->text()[0];
2396                         if (c == ' ' || c == '\t' || (c == '\n' && !next->style()->preserveNewline()))
2397                             // If the next item on the line is text, and if we did not end with
2398                             // a space, then the next text run continues our word (and so it needs to
2399                             // keep adding to |tmpW|.  Just update and continue.
2400                             checkForBreak = true;
2401                     }
2402                     bool canPlaceOnLine = (w + tmpW <= width) || !autoWrap;
2403                     if (canPlaceOnLine && checkForBreak) {
2404                         w += tmpW;
2405                         tmpW = 0;
2406                         lBreak.obj = next;
2407                         lBreak.pos = 0;
2408                     }
2409                 }
2410             }
2411         }
2412
2413         if (checkForBreak && (w + tmpW > width)) {
2414             // if we have floats, try to get below them.
2415             if (currentCharacterIsSpace && !ignoringSpaces && o->style()->collapseWhiteSpace())
2416                 trailingSpaceObject = 0;
2417             
2418             int fb = nearestFloatBottom(m_height);
2419             int newLineWidth = lineWidth(fb);
2420             // See if |tmpW| will fit on the new line.  As long as it does not,
2421             // keep adjusting our float bottom until we find some room.
2422             int lastFloatBottom = m_height;
2423             while (lastFloatBottom < fb && tmpW > newLineWidth) {
2424                 lastFloatBottom = fb;
2425                 fb = nearestFloatBottom(fb);
2426                 newLineWidth = lineWidth(fb);
2427             }            
2428             if (!w && m_height < fb && width < newLineWidth) {
2429                 m_height = fb;
2430                 width = newLineWidth;
2431             }
2432
2433             // |width| may have been adjusted because we got shoved down past a float (thus
2434             // giving us more room), so we need to retest, and only jump to
2435             // the end label if we still don't fit on the line. -dwh
2436             if (w + tmpW > width)
2437                 goto end;
2438         }
2439
2440         last = o;
2441         if (!o->isFloating() && (!o->isPositioned() || o->hasStaticX() || o->hasStaticY() || !o->container()->isInlineFlow()))
2442             previous = o;
2443         o = next;
2444
2445         if (!last->isFloatingOrPositioned() && last->isReplaced() && last->style()->autoWrap() && 
2446             (!last->isListMarker() || last->style()->listStylePosition()==INSIDE)) {
2447             // Go ahead and add in tmpW.
2448             w += tmpW;
2449             tmpW = 0;
2450             lBreak.obj = o;
2451             lBreak.pos = 0;
2452         }
2453
2454         // Clear out our character space bool, since inline <pre>s don't collapse whitespace
2455         // with adjacent inline normal/nowrap spans.
2456         if (!last->style()->collapseWhiteSpace())
2457             currentCharacterIsSpace = false;
2458         
2459         pos = 0;
2460     }
2461
2462     if (w + tmpW <= width || (last && last->style()->whiteSpace() == NOWRAP)) {
2463         lBreak.obj = 0;
2464         lBreak.pos = 0;
2465     }
2466
2467  end:
2468
2469     if (lBreak == start && !lBreak.obj->isBR()) {
2470         // we just add as much as possible
2471         if (style()->whiteSpace() == PRE) {
2472             // FIXME: Don't really understand this case.
2473             if (pos != 0) {
2474                 lBreak.obj = o;
2475                 lBreak.pos = pos - 1;
2476             } else {
2477                 lBreak.obj = last;
2478                 lBreak.pos = last->isText() ? last->length() : 0;
2479             }
2480         } else if (lBreak.obj) {
2481             if (last != o && !last->isListMarker()) {
2482                 // better to break between object boundaries than in the middle of a word (except for list markers)
2483                 lBreak.obj = o;
2484                 lBreak.pos = 0;
2485             } else {
2486                 // Don't ever break in the middle of a word if we can help it.
2487                 // There's no room at all. We just have to be on this line,
2488                 // even though we'll spill out.
2489                 lBreak.obj = o;
2490                 lBreak.pos = pos;
2491             }
2492         }
2493     }
2494
2495     // make sure we consume at least one char/object.
2496     if (lBreak == start)
2497         lBreak.increment(bidi);
2498
2499     // Sanity check our midpoints.
2500     checkMidpoints(lBreak, bidi);
2501         
2502     if (trailingSpaceObject) {
2503         // This object is either going to be part of the last midpoint, or it is going
2504         // to be the actual endpoint.  In both cases we just decrease our pos by 1 level to
2505         // exclude the space, allowing it to - in effect - collapse into the newline.
2506         if (sNumMidpoints%2==1) {
2507             BidiIterator* midpoints = smidpoints->data();
2508             midpoints[sNumMidpoints-1].pos--;
2509         }
2510         //else if (lBreak.pos > 0)
2511         //    lBreak.pos--;
2512         else if (lBreak.obj == 0 && trailingSpaceObject->isText()) {
2513             // Add a new end midpoint that stops right at the very end.
2514             RenderText* text = static_cast<RenderText *>(trailingSpaceObject);
2515             unsigned pos = text->length() >=2 ? text->length() - 2 : UINT_MAX;
2516             BidiIterator endMid(0, trailingSpaceObject, pos);
2517             addMidpoint(endMid);
2518         }
2519     }
2520
2521     // We might have made lBreak an iterator that points past the end
2522     // of the object. Do this adjustment to make it point to the start
2523     // of the next object instead to avoid confusing the rest of the
2524     // code.
2525     if (lBreak.pos > 0) {
2526         lBreak.pos--;
2527         lBreak.increment(bidi);
2528     }
2529
2530     if (lBreak.obj && lBreak.pos >= 2 && lBreak.obj->isText()) {
2531         // For soft hyphens on line breaks, we have to chop out the midpoints that made us
2532         // ignore the hyphen so that it will render at the end of the line.
2533         UChar c = static_cast<RenderText*>(lBreak.obj)->text()[lBreak.pos-1];
2534         if (c == SOFT_HYPHEN)
2535             chopMidpointsAt(lBreak.obj, lBreak.pos-2);
2536     }
2537     
2538     return lBreak;
2539 }
2540
2541 void RenderBlock::checkLinesForOverflow()
2542 {
2543     m_overflowWidth = m_width;
2544     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2545         m_overflowLeft = min(curr->leftOverflow(), m_overflowLeft);
2546         m_overflowTop = min(curr->topOverflow(), m_overflowTop);
2547         m_overflowWidth = max(curr->rightOverflow(), m_overflowWidth);
2548         m_overflowHeight = max(curr->bottomOverflow(), m_overflowHeight);
2549     }
2550 }
2551
2552 void RenderBlock::deleteEllipsisLineBoxes()
2553 {
2554     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox())
2555         curr->clearTruncation();
2556 }
2557
2558 void RenderBlock::checkLinesForTextOverflow()
2559 {
2560     // Determine the width of the ellipsis using the current font.
2561     const UChar ellipsis = 0x2026; // FIXME: CSS3 says this is configurable, also need to use 0x002E (FULL STOP) if 0x2026 not renderable
2562     TextRun ellipsisRun(&ellipsis, 1);
2563     static AtomicString ellipsisStr(&ellipsis, 1);
2564     const Font& firstLineFont = firstLineStyle()->font();
2565     const Font& font = style()->font();
2566     int firstLineEllipsisWidth = firstLineFont.width(ellipsisRun);
2567     int ellipsisWidth = (font == firstLineFont) ? firstLineEllipsisWidth : font.width(ellipsisRun);
2568
2569     // For LTR text truncation, we want to get the right edge of our padding box, and then we want to see
2570     // if the right edge of a line box exceeds that.  For RTL, we use the left edge of the padding box and
2571     // check the left edge of the line box to see if it is less
2572     // Include the scrollbar for overflow blocks, which means we want to use "contentWidth()"
2573     bool ltr = style()->direction() == LTR;
2574     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2575         int blockEdge = ltr ? rightOffset(curr->yPos()) : leftOffset(curr->yPos());
2576         int lineBoxEdge = ltr ? curr->xPos() + curr->width() : curr->xPos();
2577         if ((ltr && lineBoxEdge > blockEdge) || (!ltr && lineBoxEdge < blockEdge)) {
2578             // This line spills out of our box in the appropriate direction.  Now we need to see if the line
2579             // can be truncated.  In order for truncation to be possible, the line must have sufficient space to
2580             // accommodate our truncation string, and no replaced elements (images, tables) can overlap the ellipsis
2581             // space.
2582             int width = curr == firstRootBox() ? firstLineEllipsisWidth : ellipsisWidth;
2583             if (curr->canAccommodateEllipsis(ltr, blockEdge, lineBoxEdge, width))
2584                 curr->placeEllipsis(ellipsisStr, ltr, blockEdge, width);
2585         }
2586     }
2587 }
2588
2589 }