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