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