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