2a70d6acfba00560ca9125b535213d2f805f4717
[WebKit-https.git] / WebCore / rendering / RenderBlockLineLayout.cpp
1 /*
2  * Copyright (C) 2000 Lars Knoll (knoll@kde.org)
3  * Copyright (C) 2003, 2004, 2006, 2007, 2008, 2009 Apple Inc. All right reserved.
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Library General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  * Library General Public License for more details.
14  *
15  * You should have received a copy of the GNU Library General Public License
16  * along with this library; see the file COPYING.LIB.  If not, write to
17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21
22 #include "config.h"
23
24 #include "BidiResolver.h"
25 #include "CharacterNames.h"
26 #include "InlineTextBox.h"
27 #include "Logging.h"
28 #include "RenderArena.h"
29 #include "RenderInline.h"
30 #include "RenderListMarker.h"
31 #include "RenderView.h"
32 #include "break_lines.h"
33 #include <wtf/AlwaysInline.h>
34 #include <wtf/RefCountedLeakCounter.h>
35 #include <wtf/StdLibExtras.h>
36 #include <wtf/Vector.h>
37
38 using namespace std;
39 using namespace WTF;
40 using namespace Unicode;
41
42 namespace WebCore {
43
44 // We don't let our line box tree for a single line get any deeper than this.
45 const unsigned cMaxLineDepth = 200;
46
47 class InlineIterator {
48 public:
49     InlineIterator()
50         : block(0)
51         , obj(0)
52         , pos(0)
53         , nextBreakablePosition(-1)
54     {
55     }
56
57     InlineIterator(RenderBlock* b, RenderObject* o, unsigned p)
58         : block(b)
59         , obj(o)
60         , pos(p)
61         , nextBreakablePosition(-1)
62     {
63     }
64
65     void increment(InlineBidiResolver* resolver = 0);
66     bool atEnd() const;
67
68     UChar current() const;
69     Direction direction() const;
70
71     RenderBlock* block;
72     RenderObject* obj;
73     unsigned pos;
74     int nextBreakablePosition;
75 };
76
77 static int getBorderPaddingMargin(RenderBoxModelObject* child, bool endOfInline)
78 {
79     bool leftSide = (child->style()->direction() == LTR) ? !endOfInline : endOfInline;
80     if (leftSide)
81         return child->marginLeft() + child->paddingLeft() + child->borderLeft();
82     return child->marginRight() + child->paddingRight() + child->borderRight();
83 }
84
85 static int inlineWidth(RenderObject* child, bool start = true, bool end = true)
86 {
87     unsigned lineDepth = 1;
88     int extraWidth = 0;
89     RenderObject* parent = child->parent();
90     while (parent->isInline() && !parent->isInlineBlockOrInlineTable() && lineDepth++ < cMaxLineDepth) {
91         if (start && !child->previousSibling())
92             extraWidth += getBorderPaddingMargin(toRenderBoxModelObject(parent), false);
93         if (end && !child->nextSibling())
94             extraWidth += getBorderPaddingMargin(toRenderBoxModelObject(parent), true);
95         child = parent;
96         parent = child->parent();
97     }
98     return extraWidth;
99 }
100
101 struct BidiRun : BidiCharacterRun {
102     BidiRun(int start, int stop, RenderObject* object, BidiContext* context, Direction dir)
103         : BidiCharacterRun(start, stop, context, dir)
104         , m_object(object)
105         , m_box(0)
106     {
107     }
108
109     void destroy();
110
111     // Overloaded new operator.
112     void* operator new(size_t, RenderArena*) throw();
113
114     // Overridden to prevent the normal delete from being called.
115     void operator delete(void*, size_t);
116
117     BidiRun* next() { return static_cast<BidiRun*>(m_next); }
118
119 private:
120     // The normal operator new is disallowed.
121     void* operator new(size_t) throw();
122
123 public:
124     RenderObject* m_object;
125     InlineBox* m_box;
126 };
127
128 #ifndef NDEBUG
129 static RefCountedLeakCounter bidiRunCounter("BidiRun");
130
131 static bool inBidiRunDestroy;
132 #endif
133
134 void BidiRun::destroy()
135 {
136 #ifndef NDEBUG
137     inBidiRunDestroy = true;
138 #endif
139     RenderArena* renderArena = m_object->renderArena();
140     delete this;
141 #ifndef NDEBUG
142     inBidiRunDestroy = false;
143 #endif
144
145     // Recover the size left there for us by operator delete and free the memory.
146     renderArena->free(*reinterpret_cast<size_t*>(this), this);
147 }
148
149 void* BidiRun::operator new(size_t sz, RenderArena* renderArena) throw()
150 {
151 #ifndef NDEBUG
152     bidiRunCounter.increment();
153 #endif
154     return renderArena->allocate(sz);
155 }
156
157 void BidiRun::operator delete(void* ptr, size_t sz)
158 {
159 #ifndef NDEBUG
160     bidiRunCounter.decrement();
161 #endif
162     ASSERT(inBidiRunDestroy);
163
164     // Stash size where destroy() can find it.
165     *(size_t*)ptr = sz;
166 }
167
168 // ---------------------------------------------------------------------
169
170 inline bool operator==(const InlineIterator& it1, const InlineIterator& it2)
171 {
172     return it1.pos == it2.pos && it1.obj == it2.obj;
173 }
174
175 inline bool operator!=(const InlineIterator& it1, const InlineIterator& it2)
176 {
177     return it1.pos != it2.pos || it1.obj != it2.obj;
178 }
179
180 static inline RenderObject* bidiNext(RenderBlock* block, RenderObject* current, InlineBidiResolver* resolver = 0, bool skipInlines = true, bool* endOfInlinePtr = 0)
181 {
182     RenderObject* next = 0;
183     bool oldEndOfInline = endOfInlinePtr ? *endOfInlinePtr : false;
184     bool endOfInline = false;
185
186     while (current) {
187         next = 0;
188         if (!oldEndOfInline && !current->isFloating() && !current->isReplaced() && !current->isPositioned() && !current->isText()) {
189             next = current->firstChild();
190             if (next && resolver && next->isRenderInline()) {
191                 EUnicodeBidi ub = next->style()->unicodeBidi();
192                 if (ub != UBNormal) {
193                     TextDirection dir = next->style()->direction();
194                     Direction d = (ub == Embed
195                         ? (dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding)
196                         : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));
197                     resolver->embed(d);
198                 }
199             }
200         }
201
202         if (!next) {
203             if (!skipInlines && !oldEndOfInline && current->isRenderInline()) {
204                 next = current;
205                 endOfInline = true;
206                 break;
207             }
208
209             while (current && current != block) {
210                 if (resolver && current->isRenderInline() && current->style()->unicodeBidi() != UBNormal)
211                     resolver->embed(PopDirectionalFormat);
212
213                 next = current->nextSibling();
214                 if (next) {
215                     if (resolver && next->isRenderInline()) {
216                         EUnicodeBidi ub = next->style()->unicodeBidi();
217                         if (ub != UBNormal) {
218                             TextDirection dir = next->style()->direction();
219                             Direction d = (ub == Embed
220                                 ? (dir == RTL ? RightToLeftEmbedding: LeftToRightEmbedding)
221                                 : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));
222                             resolver->embed(d);
223                         }
224                     }
225                     break;
226                 }
227                 
228                 current = current->parent();
229                 if (!skipInlines && current && current != block && current->isRenderInline()) {
230                     next = current;
231                     endOfInline = true;
232                     break;
233                 }
234             }
235         }
236
237         if (!next)
238             break;
239
240         if (next->isText() || next->isFloating() || next->isReplaced() || next->isPositioned()
241             || ((!skipInlines || !next->firstChild()) // Always return EMPTY inlines.
242                 && next->isRenderInline()))
243             break;
244         current = next;
245     }
246
247     if (endOfInlinePtr)
248         *endOfInlinePtr = endOfInline;
249
250     return next;
251 }
252
253 static RenderObject* bidiFirst(RenderBlock* block, InlineBidiResolver* resolver, bool skipInlines = true)
254 {
255     if (!block->firstChild())
256         return 0;
257     
258     RenderObject* o = block->firstChild();
259     if (o->isRenderInline()) {
260         if (resolver) {
261             EUnicodeBidi ub = o->style()->unicodeBidi();
262             if (ub != UBNormal) {
263                 TextDirection dir = o->style()->direction();
264                 Direction d = (ub == Embed
265                     ? (dir == RTL ? RightToLeftEmbedding : LeftToRightEmbedding)
266                     : (dir == RTL ? RightToLeftOverride : LeftToRightOverride));
267                 resolver->embed(d);
268             }
269         }
270         if (skipInlines && o->firstChild())
271             o = bidiNext(block, o, resolver, skipInlines);
272         else {
273             // Never skip empty inlines.
274             if (resolver)
275                 resolver->commitExplicitEmbedding();
276             return o; 
277         }
278     }
279
280     if (o && !o->isText() && !o->isReplaced() && !o->isFloating() && !o->isPositioned())
281         o = bidiNext(block, o, resolver, skipInlines);
282
283     if (resolver)
284         resolver->commitExplicitEmbedding();
285     return o;
286 }
287
288 inline void InlineIterator::increment(InlineBidiResolver* resolver)
289 {
290     if (!obj)
291         return;
292     if (obj->isText()) {
293         pos++;
294         if (pos >= toRenderText(obj)->textLength()) {
295             obj = bidiNext(block, obj, resolver);
296             pos = 0;
297             nextBreakablePosition = -1;
298         }
299     } else {
300         obj = bidiNext(block, obj, resolver);
301         pos = 0;
302         nextBreakablePosition = -1;
303     }
304 }
305
306 template<>
307 inline void InlineBidiResolver::increment()
308 {
309     current.increment(this);
310 }
311
312 inline bool InlineIterator::atEnd() const
313 {
314     return !obj;
315 }
316
317 inline UChar InlineIterator::current() const
318 {
319     if (!obj || !obj->isText())
320         return 0;
321
322     RenderText* text = toRenderText(obj);
323     if (pos >= text->textLength())
324         return 0;
325
326     return text->characters()[pos];
327 }
328
329 ALWAYS_INLINE Direction InlineIterator::direction() const
330 {
331     if (UChar c = current())
332         return Unicode::direction(c);
333
334     if (obj && obj->isListMarker())
335         return obj->style()->direction() == LTR ? LeftToRight : RightToLeft;
336
337     return OtherNeutral;
338 }
339
340 // -------------------------------------------------------------------------------------------------
341
342 static void chopMidpointsAt(LineMidpointState& lineMidpointState, RenderObject* obj, unsigned pos)
343 {
344     if (!lineMidpointState.numMidpoints)
345         return;
346     InlineIterator* midpoints = lineMidpointState.midpoints.data();
347     for (int i = lineMidpointState.numMidpoints - 1; i >= 0; i--) {
348         const InlineIterator& point = midpoints[i];
349         if (point.obj == obj && point.pos == pos) {
350             lineMidpointState.numMidpoints = i;
351             break;
352         }
353     }
354 }
355
356 static void checkMidpoints(LineMidpointState& lineMidpointState, InlineIterator& lBreak)
357 {
358     // Check to see if our last midpoint is a start point beyond the line break.  If so,
359     // shave it off the list, and shave off a trailing space if the previous end point doesn't
360     // preserve whitespace.
361     if (lBreak.obj && lineMidpointState.numMidpoints && !(lineMidpointState.numMidpoints % 2)) {
362         InlineIterator* midpoints = lineMidpointState.midpoints.data();
363         InlineIterator& endpoint = midpoints[lineMidpointState.numMidpoints - 2];
364         const InlineIterator& startpoint = midpoints[lineMidpointState.numMidpoints - 1];
365         InlineIterator currpoint = endpoint;
366         while (!currpoint.atEnd() && currpoint != startpoint && currpoint != lBreak)
367             currpoint.increment();
368         if (currpoint == lBreak) {
369             // We hit the line break before the start point.  Shave off the start point.
370             lineMidpointState.numMidpoints--;
371             if (endpoint.obj->style()->collapseWhiteSpace()) {
372                 if (endpoint.obj->isText()) {
373                     // Don't shave a character off the endpoint if it was from a soft hyphen.
374                     RenderText* textObj = toRenderText(endpoint.obj);
375                     if (endpoint.pos + 1 < textObj->textLength()) {
376                         if (textObj->characters()[endpoint.pos+1] == softHyphen)
377                             return;
378                     } else if (startpoint.obj->isText()) {
379                         RenderText *startText = toRenderText(startpoint.obj);
380                         if (startText->textLength() && startText->characters()[0] == softHyphen)
381                             return;
382                     }
383                 }
384                 endpoint.pos--;
385             }
386         }
387     }    
388 }
389
390 static void addMidpoint(LineMidpointState& lineMidpointState, const InlineIterator& midpoint)
391 {
392     if (lineMidpointState.midpoints.size() <= lineMidpointState.numMidpoints)
393         lineMidpointState.midpoints.grow(lineMidpointState.numMidpoints + 10);
394
395     InlineIterator* midpoints = lineMidpointState.midpoints.data();
396     midpoints[lineMidpointState.numMidpoints++] = midpoint;
397 }
398
399 static void appendRunsForObject(int start, int end, RenderObject* obj, InlineBidiResolver& resolver)
400 {
401     if (start > end || obj->isFloating() ||
402         (obj->isPositioned() && !obj->style()->hasStaticX() && !obj->style()->hasStaticY() && !obj->container()->isRenderInline()))
403         return;
404
405     LineMidpointState& lineMidpointState = resolver.midpointState();
406     bool haveNextMidpoint = (lineMidpointState.currentMidpoint < lineMidpointState.numMidpoints);
407     InlineIterator nextMidpoint;
408     if (haveNextMidpoint)
409         nextMidpoint = lineMidpointState.midpoints[lineMidpointState.currentMidpoint];
410     if (lineMidpointState.betweenMidpoints) {
411         if (!(haveNextMidpoint && nextMidpoint.obj == obj))
412             return;
413         // This is a new start point. Stop ignoring objects and 
414         // adjust our start.
415         lineMidpointState.betweenMidpoints = false;
416         start = nextMidpoint.pos;
417         lineMidpointState.currentMidpoint++;
418         if (start < end)
419             return appendRunsForObject(start, end, obj, resolver);
420     } else {
421         if (!haveNextMidpoint || (obj != nextMidpoint.obj)) {
422             resolver.addRun(new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir()));
423             return;
424         }
425
426         // An end midpoint has been encountered within our object.  We
427         // need to go ahead and append a run with our endpoint.
428         if (static_cast<int>(nextMidpoint.pos + 1) <= end) {
429             lineMidpointState.betweenMidpoints = true;
430             lineMidpointState.currentMidpoint++;
431             if (nextMidpoint.pos != UINT_MAX) { // UINT_MAX means stop at the object and don't include any of it.
432                 if (static_cast<int>(nextMidpoint.pos + 1) > start)
433                     resolver.addRun(new (obj->renderArena())
434                         BidiRun(start, nextMidpoint.pos + 1, obj, resolver.context(), resolver.dir()));
435                 return appendRunsForObject(nextMidpoint.pos + 1, end, obj, resolver);
436             }
437         } else
438            resolver.addRun(new (obj->renderArena()) BidiRun(start, end, obj, resolver.context(), resolver.dir()));
439     }
440 }
441
442 template <>
443 void InlineBidiResolver::appendRun()
444 {
445     if (!emptyRun && !eor.atEnd()) {
446         int start = sor.pos;
447         RenderObject *obj = sor.obj;
448         while (obj && obj != eor.obj && obj != endOfLine.obj) {
449             appendRunsForObject(start, obj->length(), obj, *this);        
450             start = 0;
451             obj = bidiNext(sor.block, obj);
452         }
453         if (obj) {
454             unsigned pos = obj == eor.obj ? eor.pos : UINT_MAX;
455             if (obj == endOfLine.obj && endOfLine.pos <= pos) {
456                 reachedEndOfLine = true;
457                 pos = endOfLine.pos;
458             }
459             // It's OK to add runs for zero-length RenderObjects, just don't make the run larger than it should be
460             int end = obj->length() ? pos+1 : 0;
461             appendRunsForObject(start, end, obj, *this);
462         }
463         
464         eor.increment();
465         sor = eor;
466     }
467
468     m_direction = OtherNeutral;
469     m_status.eor = OtherNeutral;
470 }
471
472 static inline InlineBox* createInlineBoxForRenderer(RenderObject* obj, bool isRootLineBox, bool isOnlyRun = false)
473 {
474     if (isRootLineBox)
475         return toRenderBlock(obj)->createAndAppendRootInlineBox();
476     
477     if (obj->isText()) {
478         InlineTextBox* textBox = toRenderText(obj)->createInlineTextBox();
479         // We only treat a box as text for a <br> if we are on a line by ourself or in strict mode
480         // (Note the use of strict mode.  In "almost strict" mode, we don't treat the box for <br> as text.)
481         if (obj->isBR())
482             textBox->setIsText(isOnlyRun || obj->document()->inStrictMode());
483         return textBox;
484     }
485     
486     if (obj->isBox())
487         return toRenderBox(obj)->createInlineBox();
488     
489     return toRenderInline(obj)->createAndAppendInlineFlowBox();
490 }
491
492 static inline void dirtyLineBoxesForRenderer(RenderObject* o, bool fullLayout)
493 {
494     if (o->isText()) {
495         if (o->prefWidthsDirty() && o->isCounter())
496             toRenderText(o)->calcPrefWidths(0); // FIXME: Counters depend on this hack. No clue why. Should be investigated and removed.
497         toRenderText(o)->dirtyLineBoxes(fullLayout);
498     } else
499         toRenderInline(o)->dirtyLineBoxes(fullLayout);
500 }
501
502 InlineFlowBox* RenderBlock::createLineBoxes(RenderObject* obj, bool firstLine)
503 {
504     // See if we have an unconstructed line box for this object that is also
505     // the last item on the line.
506     unsigned lineDepth = 1;
507     InlineFlowBox* childBox = 0;
508     InlineFlowBox* parentBox = 0;
509     InlineFlowBox* result = 0;
510     do {
511         ASSERT(obj->isRenderInline() || obj == this);
512         
513         // Get the last box we made for this render object.
514         parentBox = obj->isRenderInline() ? toRenderInline(obj)->lastLineBox() : toRenderBlock(obj)->lastLineBox();
515
516         // If this box is constructed then it is from a previous line, and we need
517         // to make a new box for our line.  If this box is unconstructed but it has
518         // something following it on the line, then we know we have to make a new box
519         // as well.  In this situation our inline has actually been split in two on
520         // the same line (this can happen with very fancy language mixtures).
521         bool constructedNewBox = false;
522         if (!parentBox || parentBox->isConstructed() || parentBox->nextOnLine()) {
523             // We need to make a new box for this render object.  Once
524             // made, we need to place it at the end of the current line.
525             InlineBox* newBox = createInlineBoxForRenderer(obj, obj == this);
526             ASSERT(newBox->isInlineFlowBox());
527             parentBox = static_cast<InlineFlowBox*>(newBox);
528             parentBox->setFirstLineStyleBit(firstLine);
529             constructedNewBox = true;
530         }
531
532         if (!result)
533             result = parentBox;
534
535         // If we have hit the block itself, then |box| represents the root
536         // inline box for the line, and it doesn't have to be appended to any parent
537         // inline.
538         if (childBox)
539             parentBox->addToLine(childBox);
540
541         if (!constructedNewBox || obj == this)
542             break;
543
544         childBox = parentBox;        
545
546         // If we've exceeded our line depth, then jump straight to the root and skip all the remaining
547         // intermediate inline flows.
548         obj = (++lineDepth >= cMaxLineDepth) ? this : obj->parent();
549
550     } while (true);
551
552     return result;
553 }
554
555 RootInlineBox* RenderBlock::constructLine(unsigned runCount, BidiRun* firstRun, BidiRun* lastRun, bool firstLine, bool lastLine, RenderObject* endObject)
556 {
557     ASSERT(firstRun);
558
559     InlineFlowBox* parentBox = 0;
560     for (BidiRun* r = firstRun; r; r = r->next()) {
561         // Create a box for our object.
562         bool isOnlyRun = (runCount == 1);
563         if (runCount == 2 && !r->m_object->isListMarker())
564             isOnlyRun = ((style()->direction() == RTL) ? lastRun : firstRun)->m_object->isListMarker();
565
566         InlineBox* box = createInlineBoxForRenderer(r->m_object, false, isOnlyRun);
567         r->m_box = box;
568
569         ASSERT(box);
570         if (!box)
571             continue;
572
573         // If we have no parent box yet, or if the run is not simply a sibling,
574         // then we need to construct inline boxes as necessary to properly enclose the
575         // run's inline box.
576         if (!parentBox || parentBox->renderer() != r->m_object->parent())
577             // Create new inline boxes all the way back to the appropriate insertion point.
578             parentBox = createLineBoxes(r->m_object->parent(), firstLine);
579
580         // Append the inline box to this line.
581         parentBox->addToLine(box);
582
583         bool visuallyOrdered = r->m_object->style()->visuallyOrdered();
584         box->setBidiLevel(visuallyOrdered ? 0 : r->level());
585
586         if (box->isInlineTextBox()) {
587             InlineTextBox* text = static_cast<InlineTextBox*>(box);
588             text->setStart(r->m_start);
589             text->setLen(r->m_stop - r->m_start);
590             text->m_dirOverride = r->dirOverride(visuallyOrdered);
591         }
592     }
593
594     // We should have a root inline box.  It should be unconstructed and
595     // be the last continuation of our line list.
596     ASSERT(lastLineBox() && !lastLineBox()->isConstructed());
597
598     // Set bits on our inline flow boxes that indicate which sides should
599     // paint borders/margins/padding.  This knowledge will ultimately be used when
600     // we determine the horizontal positions and widths of all the inline boxes on
601     // the line.
602     lastLineBox()->determineSpacingForFlowBoxes(lastLine, endObject);
603
604     // Now mark the line boxes as being constructed.
605     lastLineBox()->setConstructed();
606
607     // Return the last line.
608     return lastRootBox();
609 }
610
611 void RenderBlock::computeHorizontalPositionsForLine(RootInlineBox* lineBox, bool firstLine, BidiRun* firstRun, BidiRun* trailingSpaceRun, bool reachedEnd)
612 {
613     // First determine our total width.
614     int availableWidth = lineWidth(height(), firstLine);
615     int totWidth = lineBox->getFlowSpacingWidth();
616     bool needsWordSpacing = false;
617     unsigned numSpaces = 0;
618     ETextAlign textAlign = style()->textAlign();
619
620     for (BidiRun* r = firstRun; r; r = r->next()) {
621         if (!r->m_box || r->m_object->isPositioned() || r->m_box->isLineBreak())
622             continue; // Positioned objects are only participating to figure out their
623                       // correct static x position.  They have no effect on the width.
624                       // Similarly, line break boxes have no effect on the width.
625         if (r->m_object->isText()) {
626             RenderText* rt = toRenderText(r->m_object);
627
628             if (textAlign == JUSTIFY && r != trailingSpaceRun) {
629                 const UChar* characters = rt->characters();
630                 for (int i = r->m_start; i < r->m_stop; i++) {
631                     UChar c = characters[i];
632                     if (c == ' ' || c == '\n' || c == '\t')
633                         numSpaces++;
634                 }
635             }
636
637             if (int length = rt->textLength()) {
638                 if (!r->m_start && needsWordSpacing && isSpaceOrNewline(rt->characters()[r->m_start]))
639                     totWidth += rt->style(firstLine)->font().wordSpacing();
640                 needsWordSpacing = !isSpaceOrNewline(rt->characters()[r->m_stop - 1]) && r->m_stop == length;          
641             }
642             HashSet<const SimpleFontData*> fallbackFonts;
643             r->m_box->setWidth(rt->width(r->m_start, r->m_stop - r->m_start, totWidth, firstLine, &fallbackFonts));
644             if (!fallbackFonts.isEmpty()
645 #if ENABLE(SVG)
646                     && !isSVGText()
647 #endif
648             ) {
649                 ASSERT(r->m_box->isText());
650                 static_cast<InlineTextBox*>(r->m_box)->setFallbackFonts(fallbackFonts);
651             }
652         } else if (!r->m_object->isRenderInline()) {
653             RenderBox* renderBox = toRenderBox(r->m_object);
654             renderBox->calcWidth();
655             r->m_box->setWidth(renderBox->width());
656             totWidth += renderBox->marginLeft() + renderBox->marginRight();
657         }
658
659         totWidth += r->m_box->width();
660     }
661
662     // Armed with the total width of the line (without justification),
663     // we now examine our text-align property in order to determine where to position the
664     // objects horizontally.  The total width of the line can be increased if we end up
665     // justifying text.
666     int x = leftOffset(height(), firstLine);
667     switch (textAlign) {
668         case LEFT:
669         case WEBKIT_LEFT:
670             // The direction of the block should determine what happens with wide lines.  In
671             // particular with RTL blocks, wide lines should still spill out to the left.
672             if (style()->direction() == LTR) {
673                 if (totWidth > availableWidth && trailingSpaceRun)
674                     trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));
675             } else {
676                 if (trailingSpaceRun)
677                     trailingSpaceRun->m_box->setWidth(0);
678                 else if (totWidth > availableWidth)
679                     x -= (totWidth - availableWidth);
680             }
681             break;
682         case JUSTIFY:
683             if (numSpaces && !reachedEnd && !lineBox->endsWithBreak()) {
684                 if (trailingSpaceRun) {
685                     totWidth -= trailingSpaceRun->m_box->width();
686                     trailingSpaceRun->m_box->setWidth(0);
687                 }
688                 break;
689             }
690             // fall through
691         case TAAUTO:
692             numSpaces = 0;
693             // for right to left fall through to right aligned
694             if (style()->direction() == LTR) {
695                 if (totWidth > availableWidth && trailingSpaceRun)
696                     trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));
697                 break;
698             }
699         case RIGHT:
700         case WEBKIT_RIGHT:
701             // Wide lines spill out of the block based off direction.
702             // So even if text-align is right, if direction is LTR, wide lines should overflow out of the right
703             // side of the block.
704             if (style()->direction() == LTR) {
705                 if (trailingSpaceRun) {
706                     totWidth -= trailingSpaceRun->m_box->width();
707                     trailingSpaceRun->m_box->setWidth(0);
708                 }
709                 if (totWidth < availableWidth)
710                     x += availableWidth - totWidth;
711             } else {
712                 if (totWidth > availableWidth && trailingSpaceRun) {
713                     trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceRun->m_box->width() - totWidth + availableWidth));
714                     totWidth -= trailingSpaceRun->m_box->width();
715                 } else
716                     x += availableWidth - totWidth;
717             }
718             break;
719         case CENTER:
720         case WEBKIT_CENTER:
721             int trailingSpaceWidth = 0;
722             if (trailingSpaceRun) {
723                 totWidth -= trailingSpaceRun->m_box->width();
724                 trailingSpaceWidth = min(trailingSpaceRun->m_box->width(), (availableWidth - totWidth + 1) / 2);
725                 trailingSpaceRun->m_box->setWidth(max(0, trailingSpaceWidth));
726             }
727             if (style()->direction() == LTR)
728                 x += max((availableWidth - totWidth) / 2, 0);
729             else
730                 x += totWidth > availableWidth ? (availableWidth - totWidth) : (availableWidth - totWidth) / 2 - trailingSpaceWidth;
731             break;
732     }
733
734     if (numSpaces) {
735         for (BidiRun* r = firstRun; r; r = r->next()) {
736             if (!r->m_box || r == trailingSpaceRun)
737                 continue;
738
739             int spaceAdd = 0;
740             if (r->m_object->isText()) {
741                 unsigned spaces = 0;
742                 const UChar* characters = toRenderText(r->m_object)->characters();
743                 for (int i = r->m_start; i < r->m_stop; i++) {
744                     UChar c = characters[i];
745                     if (c == ' ' || c == '\n' || c == '\t')
746                         spaces++;
747                 }
748
749                 ASSERT(spaces <= numSpaces);
750
751                 // Only justify text if whitespace is collapsed.
752                 if (r->m_object->style()->collapseWhiteSpace()) {
753                     spaceAdd = (availableWidth - totWidth) * spaces / numSpaces;
754                     static_cast<InlineTextBox*>(r->m_box)->setSpaceAdd(spaceAdd);
755                     totWidth += spaceAdd;
756                 }
757                 numSpaces -= spaces;
758                 if (!numSpaces)
759                     break;
760             }
761         }
762     }
763
764     // The widths of all runs are now known.  We can now place every inline box (and
765     // compute accurate widths for the inline flow boxes).
766     int leftPosition = x;
767     int rightPosition = x;
768     needsWordSpacing = false;
769     lineBox->placeBoxesHorizontally(x, leftPosition, rightPosition, needsWordSpacing);
770     lineBox->setHorizontalOverflowPositions(leftPosition, rightPosition);
771 }
772
773 void RenderBlock::computeVerticalPositionsForLine(RootInlineBox* lineBox, BidiRun* firstRun)
774 {
775     setHeight(lineBox->verticallyAlignBoxes(height()));
776     lineBox->setBlockHeight(height());
777
778     // See if the line spilled out.  If so set overflow height accordingly.
779     int bottomOfLine = lineBox->bottomOverflow();
780     if (bottomOfLine > height() && bottomOfLine > m_overflowHeight)
781         m_overflowHeight = bottomOfLine;
782
783     // Now make sure we place replaced render objects correctly.
784     for (BidiRun* r = firstRun; r; r = r->next()) {
785         ASSERT(r->m_box);
786         if (!r->m_box)
787             continue; // Skip runs with no line boxes.
788
789         // Align positioned boxes with the top of the line box.  This is
790         // a reasonable approximation of an appropriate y position.
791         if (r->m_object->isPositioned())
792             r->m_box->setY(height());
793
794         // Position is used to properly position both replaced elements and
795         // to update the static normal flow x/y of positioned elements.
796         if (r->m_object->isText())
797             toRenderText(r->m_object)->positionLineBox(r->m_box);
798         else if (r->m_object->isBox())
799             toRenderBox(r->m_object)->positionLineBox(r->m_box);
800     }
801     // Positioned objects and zero-length text nodes destroy their boxes in
802     // position(), which unnecessarily dirties the line.
803     lineBox->markDirty(false);
804 }
805
806 // collects one line of the paragraph and transforms it to visual order
807 void RenderBlock::bidiReorderLine(InlineBidiResolver& resolver, const InlineIterator& end, bool previousLineBrokeCleanly)
808 {
809     resolver.createBidiRunsForLine(end, style()->visuallyOrdered(), previousLineBrokeCleanly);
810 }
811
812 static inline bool isCollapsibleSpace(UChar character, RenderText* renderer)
813 {
814     if (character == ' ' || character == '\t' || character == softHyphen)
815         return true;
816     if (character == '\n')
817         return !renderer->style()->preserveNewline();
818     if (character == noBreakSpace)
819         return renderer->style()->nbspMode() == SPACE;
820     return false;
821 }
822
823 void RenderBlock::layoutInlineChildren(bool relayoutChildren, int& repaintTop, int& repaintBottom)
824 {
825     bool useRepaintBounds = false;
826     
827     m_overflowHeight = 0;
828         
829     setHeight(borderTop() + paddingTop());
830     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
831
832     // Figure out if we should clear out our line boxes.
833     // FIXME: Handle resize eventually!
834     bool fullLayout = !firstLineBox() || !firstChild() || selfNeedsLayout() || relayoutChildren;
835     if (fullLayout)
836         lineBoxes()->deleteLineBoxes(renderArena());
837
838     // Text truncation only kicks in if your overflow isn't visible and your text-overflow-mode isn't
839     // clip.
840     // FIXME: CSS3 says that descendants that are clipped must also know how to truncate.  This is insanely
841     // difficult to figure out (especially in the middle of doing layout), and is really an esoteric pile of nonsense
842     // anyway, so we won't worry about following the draft here.
843     bool hasTextOverflow = style()->textOverflow() && hasOverflowClip();
844
845     // Walk all the lines and delete our ellipsis line boxes if they exist.
846     if (hasTextOverflow)
847          deleteEllipsisLineBoxes();
848
849     if (firstChild()) {
850         // layout replaced elements
851         bool endOfInline = false;
852         RenderObject* o = bidiFirst(this, 0, false);
853         Vector<FloatWithRect> floats;
854         while (o) {
855             if (o->isReplaced() || o->isFloating() || o->isPositioned()) {
856                 RenderBox* box = toRenderBox(o);
857                 
858                 if (relayoutChildren || o->style()->width().isPercent() || o->style()->height().isPercent())
859                     o->setChildNeedsLayout(true, false);
860                     
861                 // If relayoutChildren is set and we have percentage padding, we also need to invalidate the child's pref widths.
862                 if (relayoutChildren && (o->style()->paddingLeft().isPercent() || o->style()->paddingRight().isPercent()))
863                     o->setPrefWidthsDirty(true, false);
864             
865                 if (o->isPositioned())
866                     o->containingBlock()->insertPositionedObject(box);
867                 else {
868                     if (o->isFloating())
869                         floats.append(FloatWithRect(box));
870                     else if (fullLayout || o->needsLayout()) // Replaced elements
871                         toRenderBox(o)->dirtyLineBoxes(fullLayout);
872
873                     o->layoutIfNeeded();
874                 }
875             } else if (o->isText() || (o->isRenderInline() && !endOfInline)) {
876                 if (fullLayout || o->selfNeedsLayout())
877                     dirtyLineBoxesForRenderer(o, fullLayout);
878                 o->setNeedsLayout(false);
879                 if (!o->isText())
880                     toRenderInline(o)->invalidateVerticalPosition(); // FIXME: Should do better here and not always invalidate everything.
881             }
882             o = bidiNext(this, o, 0, false, &endOfInline);
883         }
884
885         // We want to skip ahead to the first dirty line
886         InlineBidiResolver resolver;
887         unsigned floatIndex;
888         bool firstLine = true;
889         bool previousLineBrokeCleanly = true;
890         RootInlineBox* startLine = determineStartPosition(firstLine, fullLayout, previousLineBrokeCleanly, resolver, floats, floatIndex);
891
892         if (fullLayout && !selfNeedsLayout()) {
893             setNeedsLayout(true, false);  // Mark ourselves as needing a full layout. This way we'll repaint like
894                                           // we're supposed to.
895             RenderView* v = view();
896             if (v && !v->doingFullRepaint() && hasLayer()) {
897                 // Because we waited until we were already inside layout to discover
898                 // that the block really needed a full layout, we missed our chance to repaint the layer
899                 // before layout started.  Luckily the layer has cached the repaint rect for its original
900                 // position and size, and so we can use that to make a repaint happen now.
901                 repaintUsingContainer(containerForRepaint(), layer()->repaintRect());
902             }
903         }
904
905         FloatingObject* lastFloat = m_floatingObjects ? m_floatingObjects->last() : 0;
906
907         LineMidpointState& lineMidpointState = resolver.midpointState();
908
909         // We also find the first clean line and extract these lines.  We will add them back
910         // if we determine that we're able to synchronize after handling all our dirty lines.
911         InlineIterator cleanLineStart;
912         BidiStatus cleanLineBidiStatus;
913         int endLineYPos = 0;
914         RootInlineBox* endLine = (fullLayout || !startLine) ? 
915                                  0 : determineEndPosition(startLine, cleanLineStart, cleanLineBidiStatus, endLineYPos);
916
917         if (startLine) {
918             useRepaintBounds = true;
919             repaintTop = height();
920             repaintBottom = height();
921             RenderArena* arena = renderArena();
922             RootInlineBox* box = startLine;
923             while (box) {
924                 repaintTop = min(repaintTop, box->topOverflow());
925                 repaintBottom = max(repaintBottom, box->bottomOverflow());
926                 RootInlineBox* next = box->nextRootBox();
927                 box->deleteLine(arena);
928                 box = next;
929             }
930         }
931
932         InlineIterator end = resolver.position();
933
934         if (!fullLayout && lastRootBox() && lastRootBox()->endsWithBreak()) {
935             // If the last line before the start line ends with a line break that clear floats,
936             // adjust the height accordingly.
937             // A line break can be either the first or the last object on a line, depending on its direction.
938             if (InlineBox* lastLeafChild = lastRootBox()->lastLeafChild()) {
939                 RenderObject* lastObject = lastLeafChild->renderer();
940                 if (!lastObject->isBR())
941                     lastObject = lastRootBox()->firstLeafChild()->renderer();
942                 if (lastObject->isBR()) {
943                     EClear clear = lastObject->style()->clear();
944                     if (clear != CNONE)
945                         newLine(clear);
946                 }
947             }
948         }
949
950         bool endLineMatched = false;
951         bool checkForEndLineMatch = endLine;
952         bool checkForFloatsFromLastLine = false;
953         int lastHeight = height();
954
955         bool isLineEmpty = true;
956
957         while (!end.atEnd()) {
958             // FIXME: Is this check necessary before the first iteration or can it be moved to the end?
959             if (checkForEndLineMatch && (endLineMatched = matchedEndLine(resolver, cleanLineStart, cleanLineBidiStatus, endLine, endLineYPos, repaintBottom, repaintTop)))
960                 break;
961
962             lineMidpointState.reset();
963             
964             isLineEmpty = true;
965             
966             EClear clear = CNONE;
967             end = findNextLineBreak(resolver, firstLine, isLineEmpty, previousLineBrokeCleanly, &clear);
968             if (resolver.position().atEnd()) {
969                 resolver.deleteRuns();
970                 checkForFloatsFromLastLine = true;
971                 break;
972             }
973             ASSERT(end != resolver.position());
974
975             if (!isLineEmpty) {
976                 bidiReorderLine(resolver, end, previousLineBrokeCleanly);
977                 ASSERT(resolver.position() == end);
978
979                 BidiRun* trailingSpaceRun = 0;
980                 if (!previousLineBrokeCleanly && resolver.runCount() && resolver.logicallyLastRun()->m_object->style()->breakOnlyAfterWhiteSpace()
981                         && resolver.logicallyLastRun()->m_object->style()->autoWrap()) {
982                     trailingSpaceRun = resolver.logicallyLastRun();
983                     RenderObject* lastObject = trailingSpaceRun->m_object;
984                     if (lastObject->isText()) {
985                         RenderText* lastText = toRenderText(lastObject);
986                         const UChar* characters = lastText->characters();
987                         int firstSpace = trailingSpaceRun->stop();
988                         while (firstSpace > trailingSpaceRun->start()) {
989                             UChar current = characters[firstSpace - 1];
990                             if (!isCollapsibleSpace(current, lastText))
991                                 break;
992                             firstSpace--;
993                         }
994                         if (firstSpace == trailingSpaceRun->stop())
995                             trailingSpaceRun = 0;
996                         else {
997                             TextDirection direction = style()->direction();
998                             bool shouldReorder = trailingSpaceRun != (direction == LTR ? resolver.lastRun() : resolver.firstRun());
999                             if (firstSpace != trailingSpaceRun->start()) {
1000                                 BidiContext* baseContext = resolver.context();
1001                                 while (BidiContext* parent = baseContext->parent())
1002                                     baseContext = parent;
1003
1004                                 BidiRun* newTrailingRun = new (renderArena()) BidiRun(firstSpace, trailingSpaceRun->m_stop, trailingSpaceRun->m_object, baseContext, OtherNeutral);
1005                                 trailingSpaceRun->m_stop = firstSpace;
1006                                 if (direction == LTR)
1007                                     resolver.addRun(newTrailingRun);
1008                                 else
1009                                     resolver.prependRun(newTrailingRun);
1010                                 trailingSpaceRun = newTrailingRun;
1011                                 shouldReorder = false;
1012                             }
1013                             if (shouldReorder) {
1014                                 if (direction == LTR) {
1015                                     resolver.moveRunToEnd(trailingSpaceRun);
1016                                     trailingSpaceRun->m_level = 0;
1017                                 } else {
1018                                     resolver.moveRunToBeginning(trailingSpaceRun);
1019                                     trailingSpaceRun->m_level = 1;
1020                                 }
1021                             }
1022                         }
1023                     } else
1024                         trailingSpaceRun = 0;
1025                 }
1026
1027                 // Now that the runs have been ordered, we create the line boxes.
1028                 // At the same time we figure out where border/padding/margin should be applied for
1029                 // inline flow boxes.
1030
1031                 RootInlineBox* lineBox = 0;
1032                 if (resolver.runCount()) {
1033                     lineBox = constructLine(resolver.runCount(), resolver.firstRun(), resolver.lastRun(), firstLine, !end.obj, end.obj && !end.pos ? end.obj : 0);
1034                     if (lineBox) {
1035                         lineBox->setEndsWithBreak(previousLineBrokeCleanly);
1036
1037                         // Now we position all of our text runs horizontally.
1038                         computeHorizontalPositionsForLine(lineBox, firstLine, resolver.firstRun(), trailingSpaceRun, end.atEnd());
1039
1040                         // Now position our text runs vertically.
1041                         computeVerticalPositionsForLine(lineBox, resolver.firstRun());
1042
1043 #if ENABLE(SVG)
1044                         // Special SVG text layout code
1045                         lineBox->computePerCharacterLayoutInformation();
1046 #endif
1047
1048 #if PLATFORM(MAC)
1049                         // Highlight acts as an overflow inflation.
1050                         if (style()->highlight() != nullAtom)
1051                             lineBox->addHighlightOverflow();
1052 #endif
1053                     }
1054                 }
1055
1056                 resolver.deleteRuns();
1057
1058                 if (lineBox) {
1059                     lineBox->setLineBreakInfo(end.obj, end.pos, resolver.status());
1060                     if (useRepaintBounds) {
1061                         repaintTop = min(repaintTop, lineBox->topOverflow());
1062                         repaintBottom = max(repaintBottom, lineBox->bottomOverflow());
1063                     }
1064                 }
1065
1066                 firstLine = false;
1067                 newLine(clear);
1068             }
1069
1070             if (m_floatingObjects && lastRootBox()) {
1071                 if (lastFloat) {
1072                     for (FloatingObject* f = m_floatingObjects->last(); f != lastFloat; f = m_floatingObjects->prev()) {
1073                     }
1074                     m_floatingObjects->next();
1075                 } else
1076                     m_floatingObjects->first();
1077                 for (FloatingObject* f = m_floatingObjects->current(); f; f = m_floatingObjects->next()) {
1078                     if (f->m_bottom > lastHeight)
1079                         lastRootBox()->floats().append(f->m_renderer);
1080                     ASSERT(f->m_renderer == floats[floatIndex].object);
1081                     // If a float's geometry has changed, give up on syncing with clean lines.
1082                     if (floats[floatIndex].rect != IntRect(f->m_left, f->m_top, f->m_width, f->m_bottom - f->m_top))
1083                         checkForEndLineMatch = false;
1084                     floatIndex++;
1085                 }
1086                 lastFloat = m_floatingObjects->last();
1087             }
1088
1089             lastHeight = height();
1090             lineMidpointState.reset();
1091             resolver.setPosition(end);
1092         }
1093
1094         if (endLine) {
1095             if (endLineMatched) {
1096                 // Attach all the remaining lines, and then adjust their y-positions as needed.
1097                 int delta = height() - endLineYPos;
1098                 for (RootInlineBox* line = endLine; line; line = line->nextRootBox()) {
1099                     line->attachLine();
1100                     if (delta) {
1101                         repaintTop = min(repaintTop, line->topOverflow() + min(delta, 0));
1102                         repaintBottom = max(repaintBottom, line->bottomOverflow() + max(delta, 0));
1103                         line->adjustPosition(0, delta);
1104                     }
1105                     if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1106                         Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1107                         for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1108                             int floatTop = (*f)->y() - (*f)->marginTop();
1109                             insertFloatingObject(*f);
1110                             setHeight(floatTop + delta);
1111                             positionNewFloats();
1112                         }
1113                     }
1114                 }
1115                 setHeight(lastRootBox()->blockHeight());
1116             } else {
1117                 // Delete all the remaining lines.
1118                 InlineRunBox* line = endLine;
1119                 RenderArena* arena = renderArena();
1120                 while (line) {
1121                     repaintTop = min(repaintTop, line->topOverflow());
1122                     repaintBottom = max(repaintBottom, line->bottomOverflow());
1123                     InlineRunBox* next = line->nextLineBox();
1124                     line->deleteLine(arena);
1125                     line = next;
1126                 }
1127             }
1128         }
1129         if (m_floatingObjects && (checkForFloatsFromLastLine || positionNewFloats()) && lastRootBox()) {
1130             // In case we have a float on the last line, it might not be positioned up to now.
1131             // This has to be done before adding in the bottom border/padding, or the float will
1132             // include the padding incorrectly. -dwh
1133             if (lastFloat) {
1134                 for (FloatingObject* f = m_floatingObjects->last(); f != lastFloat; f = m_floatingObjects->prev()) {
1135                 }
1136                 m_floatingObjects->next();
1137             } else
1138                 m_floatingObjects->first();
1139             for (FloatingObject* f = m_floatingObjects->current(); f; f = m_floatingObjects->next()) {
1140                 if (f->m_bottom > lastHeight)
1141                     lastRootBox()->floats().append(f->m_renderer);
1142             }
1143             lastFloat = m_floatingObjects->last();
1144         }
1145         size_t floatCount = floats.size();
1146         // Floats that did not have layout did not repaint when we laid them out. They would have
1147         // painted by now if they had moved, but if they stayed at (0, 0), they still need to be
1148         // painted.
1149         for (size_t i = 0; i < floatCount; ++i) {
1150             if (!floats[i].everHadLayout) {
1151                 RenderBox* f = floats[i].object;
1152                 if (!f->x() && !f->y() && f->checkForRepaintDuringLayout())
1153                     f->repaint();
1154             }
1155         }
1156     }
1157
1158     // Now add in the bottom border/padding.
1159     setHeight(height() + toAdd);
1160
1161     // Always make sure this is at least our height.
1162     m_overflowHeight = max(height(), m_overflowHeight);
1163
1164     // See if any lines spill out of the block.  If so, we need to update our overflow width.
1165     checkLinesForOverflow();
1166
1167     if (!firstLineBox() && hasLineIfEmpty())
1168         setHeight(height() + lineHeight(true, true));
1169
1170     // See if we have any lines that spill out of our block.  If we do, then we will possibly need to
1171     // truncate text.
1172     if (hasTextOverflow)
1173         checkLinesForTextOverflow();
1174 }
1175
1176 RootInlineBox* RenderBlock::determineStartPosition(bool& firstLine, bool& fullLayout, bool& previousLineBrokeCleanly, 
1177                                                    InlineBidiResolver& resolver, Vector<FloatWithRect>& floats, unsigned& numCleanFloats)
1178 {
1179     RootInlineBox* curr = 0;
1180     RootInlineBox* last = 0;
1181
1182     bool dirtiedByFloat = false;
1183     if (!fullLayout) {
1184         size_t floatIndex = 0;
1185         for (curr = firstRootBox(); curr && !curr->isDirty(); curr = curr->nextRootBox()) {
1186             if (Vector<RenderBox*>* cleanLineFloats = curr->floatsPtr()) {
1187                 Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1188                 for (Vector<RenderBox*>::iterator o = cleanLineFloats->begin(); o != end; ++o) {
1189                     RenderBox* f = *o;
1190                     IntSize newSize(f->width() + f->marginLeft() +f->marginRight(), f->height() + f->marginTop() + f->marginBottom());
1191                     ASSERT(floatIndex < floats.size());
1192                     if (floats[floatIndex].object != f) {
1193                         // A new float has been inserted before this line or before its last known float.
1194                         // Just do a full layout.
1195                         fullLayout = true;
1196                         break;
1197                     }
1198                     if (floats[floatIndex].rect.size() != newSize) {
1199                         int floatTop = floats[floatIndex].rect.y();
1200                         curr->markDirty();
1201                         markLinesDirtyInVerticalRange(curr->blockHeight(), floatTop + max(floats[floatIndex].rect.height(), newSize.height()));
1202                         floats[floatIndex].rect.setSize(newSize);
1203                         dirtiedByFloat = true;
1204                     }
1205                     floatIndex++;
1206                 }
1207             }
1208             if (dirtiedByFloat || fullLayout)
1209                 break;
1210         }
1211         // Check if a new float has been inserted after the last known float.
1212         if (!curr && floatIndex < floats.size())
1213             fullLayout = true;
1214     }
1215
1216     if (fullLayout) {
1217         // Nuke all our lines.
1218         if (firstRootBox()) {
1219             RenderArena* arena = renderArena();
1220             curr = firstRootBox(); 
1221             while (curr) {
1222                 RootInlineBox* next = curr->nextRootBox();
1223                 curr->deleteLine(arena);
1224                 curr = next;
1225             }
1226             ASSERT(!firstLineBox() && !lastLineBox());
1227         }
1228     } else {
1229         if (curr) {
1230             // We have a dirty line.
1231             if (RootInlineBox* prevRootBox = curr->prevRootBox()) {
1232                 // We have a previous line.
1233                 if (!dirtiedByFloat && (!prevRootBox->endsWithBreak() || (prevRootBox->lineBreakObj()->isText() && prevRootBox->lineBreakPos() >= toRenderText(prevRootBox->lineBreakObj())->textLength())))
1234                     // The previous line didn't break cleanly or broke at a newline
1235                     // that has been deleted, so treat it as dirty too.
1236                     curr = prevRootBox;
1237             }
1238         } else {
1239             // No dirty lines were found.
1240             // If the last line didn't break cleanly, treat it as dirty.
1241             if (lastRootBox() && !lastRootBox()->endsWithBreak())
1242                 curr = lastRootBox();
1243         }
1244
1245         // If we have no dirty lines, then last is just the last root box.
1246         last = curr ? curr->prevRootBox() : lastRootBox();
1247     }
1248
1249     numCleanFloats = 0;
1250     if (!floats.isEmpty()) {
1251         int savedHeight = height();
1252         // Restore floats from clean lines.
1253         RootInlineBox* line = firstRootBox();
1254         while (line != curr) {
1255             if (Vector<RenderBox*>* cleanLineFloats = line->floatsPtr()) {
1256                 Vector<RenderBox*>::iterator end = cleanLineFloats->end();
1257                 for (Vector<RenderBox*>::iterator f = cleanLineFloats->begin(); f != end; ++f) {
1258                     insertFloatingObject(*f);
1259                     setHeight((*f)->y() - (*f)->marginTop());
1260                     positionNewFloats();
1261                     ASSERT(floats[numCleanFloats].object == *f);
1262                     numCleanFloats++;
1263                 }
1264             }
1265             line = line->nextRootBox();
1266         }
1267         setHeight(savedHeight);
1268     }
1269
1270     firstLine = !last;
1271     previousLineBrokeCleanly = !last || last->endsWithBreak();
1272
1273     RenderObject* startObj;
1274     int pos = 0;
1275     if (last) {
1276         setHeight(last->blockHeight());
1277         startObj = last->lineBreakObj();
1278         pos = last->lineBreakPos();
1279         resolver.setStatus(last->lineBreakBidiStatus());
1280     } else {
1281         bool ltr = style()->direction() == LTR
1282     #if ENABLE(SVG)   
1283             || (style()->unicodeBidi() == UBNormal && isSVGText())
1284     #endif
1285             ;
1286
1287         Direction direction = ltr ? LeftToRight : RightToLeft;
1288         resolver.setLastStrongDir(direction);
1289         resolver.setLastDir(direction);
1290         resolver.setEorDir(direction);
1291         resolver.setContext(BidiContext::create(ltr ? 0 : 1, direction, style()->unicodeBidi() == Override));
1292
1293         startObj = bidiFirst(this, &resolver);
1294     }
1295
1296     resolver.setPosition(InlineIterator(this, startObj, pos));
1297
1298     return curr;
1299 }
1300
1301 RootInlineBox* RenderBlock::determineEndPosition(RootInlineBox* startLine, InlineIterator& cleanLineStart, BidiStatus& cleanLineBidiStatus, int& yPos)
1302 {
1303     RootInlineBox* last = 0;
1304     if (!startLine)
1305         last = 0;
1306     else {
1307         for (RootInlineBox* curr = startLine->nextRootBox(); curr; curr = curr->nextRootBox()) {
1308             if (curr->isDirty())
1309                 last = 0;
1310             else if (!last)
1311                 last = curr;
1312         }
1313     }
1314
1315     if (!last)
1316         return 0;
1317
1318     RootInlineBox* prev = last->prevRootBox();
1319     cleanLineStart = InlineIterator(this, prev->lineBreakObj(), prev->lineBreakPos());
1320     cleanLineBidiStatus = prev->lineBreakBidiStatus();
1321     yPos = prev->blockHeight();
1322
1323     for (RootInlineBox* line = last; line; line = line->nextRootBox())
1324         line->extractLine(); // Disconnect all line boxes from their render objects while preserving
1325                              // their connections to one another.
1326
1327     return last;
1328 }
1329
1330 bool RenderBlock::matchedEndLine(const InlineBidiResolver& resolver, const InlineIterator& endLineStart, const BidiStatus& endLineStatus, RootInlineBox*& endLine, int& endYPos, int& repaintBottom, int& repaintTop)
1331 {
1332     if (resolver.position() == endLineStart) {
1333         if (resolver.status() != endLineStatus)
1334             return false;
1335
1336         int delta = height() - endYPos;
1337         if (!delta || !m_floatingObjects)
1338             return true;
1339
1340         // See if any floats end in the range along which we want to shift the lines vertically.
1341         int top = min(height(), endYPos);
1342
1343         RootInlineBox* lastLine = endLine;
1344         while (RootInlineBox* nextLine = lastLine->nextRootBox())
1345             lastLine = nextLine;
1346
1347         int bottom = lastLine->blockHeight() + abs(delta);
1348
1349         for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
1350             if (f->m_bottom >= top && f->m_bottom < bottom)
1351                 return false;
1352         }
1353
1354         return true;
1355     }
1356
1357     // The first clean line doesn't match, but we can check a handful of following lines to try
1358     // to match back up.
1359     static int numLines = 8; // The # of lines we're willing to match against.
1360     RootInlineBox* line = endLine;
1361     for (int i = 0; i < numLines && line; i++, line = line->nextRootBox()) {
1362         if (line->lineBreakObj() == resolver.position().obj && line->lineBreakPos() == resolver.position().pos) {
1363             // We have a match.
1364             if (line->lineBreakBidiStatus() != resolver.status())
1365                 return false; // ...but the bidi state doesn't match.
1366             RootInlineBox* result = line->nextRootBox();
1367
1368             // Set our yPos to be the block height of endLine.
1369             if (result)
1370                 endYPos = line->blockHeight();
1371
1372             int delta = height() - endYPos;
1373             if (delta && m_floatingObjects) {
1374                 // See if any floats end in the range along which we want to shift the lines vertically.
1375                 int top = min(height(), endYPos);
1376
1377                 RootInlineBox* lastLine = endLine;
1378                 while (RootInlineBox* nextLine = lastLine->nextRootBox())
1379                     lastLine = nextLine;
1380
1381                 int bottom = lastLine->blockHeight() + abs(delta);
1382
1383                 for (FloatingObject* f = m_floatingObjects->first(); f; f = m_floatingObjects->next()) {
1384                     if (f->m_bottom >= top && f->m_bottom < bottom)
1385                         return false;
1386                 }
1387             }
1388
1389             // Now delete the lines that we failed to sync.
1390             RootInlineBox* boxToDelete = endLine;
1391             RenderArena* arena = renderArena();
1392             while (boxToDelete && boxToDelete != result) {
1393                 repaintTop = min(repaintTop, boxToDelete->topOverflow());
1394                 repaintBottom = max(repaintBottom, boxToDelete->bottomOverflow());
1395                 RootInlineBox* next = boxToDelete->nextRootBox();
1396                 boxToDelete->deleteLine(arena);
1397                 boxToDelete = next;
1398             }
1399
1400             endLine = result;
1401             return result;
1402         }
1403     }
1404
1405     return false;
1406 }
1407
1408 static inline bool skipNonBreakingSpace(const InlineIterator& it, bool isLineEmpty, bool previousLineBrokeCleanly)
1409 {
1410     if (it.obj->style()->nbspMode() != SPACE || it.current() != noBreakSpace)
1411         return false;
1412
1413     // FIXME: This is bad.  It makes nbsp inconsistent with space and won't work correctly
1414     // with m_minWidth/m_maxWidth.
1415     // Do not skip a non-breaking space if it is the first character
1416     // on a line after a clean line break (or on the first line, since previousLineBrokeCleanly starts off
1417     // |true|).
1418     if (isLineEmpty && previousLineBrokeCleanly)
1419         return false;
1420
1421     return true;
1422 }
1423
1424 static inline bool shouldCollapseWhiteSpace(const RenderStyle* style, bool isLineEmpty, bool previousLineBrokeCleanly)
1425 {
1426     return style->collapseWhiteSpace() || (style->whiteSpace() == PRE_WRAP && (!isLineEmpty || !previousLineBrokeCleanly));
1427 }
1428
1429 static inline bool shouldPreserveNewline(RenderObject* object)
1430 {
1431 #if ENABLE(SVG)
1432     if (object->isSVGText())
1433         return false;
1434 #endif
1435
1436     return object->style()->preserveNewline();
1437 }
1438
1439 static bool inlineFlowRequiresLineBox(RenderInline* flow)
1440 {
1441     // FIXME: Right now, we only allow line boxes for inlines that are truly empty.
1442     // We need to fix this, though, because at the very least, inlines containing only
1443     // ignorable whitespace should should also have line boxes. 
1444     return !flow->firstChild() && flow->hasHorizontalBordersPaddingOrMargin();
1445 }
1446
1447 static inline bool requiresLineBox(const InlineIterator& it, bool isLineEmpty, bool previousLineBrokeCleanly)
1448 {
1449     if (it.obj->isFloatingOrPositioned())
1450         return false;
1451
1452     if (it.obj->isRenderInline() && !inlineFlowRequiresLineBox(toRenderInline(it.obj)))
1453         return false;
1454
1455     if (!shouldCollapseWhiteSpace(it.obj->style(), isLineEmpty, previousLineBrokeCleanly) || it.obj->isBR())
1456         return true;
1457
1458     UChar current = it.current();
1459     return current != ' ' && current != '\t' && current != softHyphen && (current != '\n' || shouldPreserveNewline(it.obj)) 
1460             && !skipNonBreakingSpace(it, isLineEmpty, previousLineBrokeCleanly);
1461 }
1462
1463 bool RenderBlock::generatesLineBoxesForInlineChild(RenderObject* inlineObj, bool isLineEmpty, bool previousLineBrokeCleanly)
1464 {
1465     ASSERT(inlineObj->parent() == this);
1466
1467     InlineIterator it(this, inlineObj, 0);
1468     while (!it.atEnd() && !requiresLineBox(it, isLineEmpty, previousLineBrokeCleanly))
1469         it.increment();
1470
1471     return !it.atEnd();
1472 }
1473
1474 // FIXME: The entire concept of the skipTrailingWhitespace function is flawed, since we really need to be building
1475 // line boxes even for containers that may ultimately collapse away.  Otherwise we'll never get positioned
1476 // elements quite right.  In other words, we need to build this function's work into the normal line
1477 // object iteration process.
1478 // NB. this function will insert any floating elements that would otherwise
1479 // be skipped but it will not position them.
1480 void RenderBlock::skipTrailingWhitespace(InlineIterator& iterator, bool isLineEmpty, bool previousLineBrokeCleanly)
1481 {
1482     while (!iterator.atEnd() && !requiresLineBox(iterator, isLineEmpty, previousLineBrokeCleanly)) {
1483         RenderObject* object = iterator.obj;
1484         if (object->isFloating()) {
1485             insertFloatingObject(toRenderBox(object));
1486         } else if (object->isPositioned()) {
1487             // FIXME: The math here is actually not really right.  It's a best-guess approximation that
1488             // will work for the common cases
1489             RenderObject* c = object->container();
1490             if (c->isRenderInline()) {
1491                 // A relative positioned inline encloses us.  In this case, we also have to determine our
1492                 // position as though we were an inline.  Set |staticX| and |staticY| on the relative positioned
1493                 // inline so that we can obtain the value later.
1494                 toRenderInline(c)->layer()->setStaticX(style()->direction() == LTR ? leftOffset(height(), false) : rightOffset(height(), false));
1495                 toRenderInline(c)->layer()->setStaticY(height());
1496             }
1497     
1498             RenderBox* box = toRenderBox(object);
1499             if (box->style()->hasStaticX()) {
1500                 if (box->style()->isOriginalDisplayInlineType())
1501                     box->layer()->setStaticX(style()->direction() == LTR ? leftOffset(height(), false) : width() - rightOffset(height(), false));
1502                 else
1503                     box->layer()->setStaticX(style()->direction() == LTR ? borderLeft() + paddingLeft() : borderRight() + paddingRight());
1504             }
1505     
1506             if (box->style()->hasStaticY())
1507                 box->layer()->setStaticY(height());
1508         }
1509         iterator.increment();
1510     }
1511 }
1512
1513 int RenderBlock::skipLeadingWhitespace(InlineBidiResolver& resolver, bool firstLine, bool isLineEmpty, bool previousLineBrokeCleanly)
1514 {
1515     int availableWidth = lineWidth(height(), firstLine);
1516     while (!resolver.position().atEnd() && !requiresLineBox(resolver.position(), isLineEmpty, previousLineBrokeCleanly)) {
1517         RenderObject* object = resolver.position().obj;
1518         if (object->isFloating()) {
1519             insertFloatingObject(toRenderBox(object));
1520             positionNewFloats();
1521             availableWidth = lineWidth(height(), firstLine);
1522         } else if (object->isPositioned()) {
1523             // FIXME: The math here is actually not really right.  It's a best-guess approximation that
1524             // will work for the common cases
1525             RenderObject* c = object->container();
1526             if (c->isRenderInline()) {
1527                 // A relative positioned inline encloses us.  In this case, we also have to determine our
1528                 // position as though we were an inline.  Set |staticX| and |staticY| on the relative positioned
1529                 // inline so that we can obtain the value later.
1530                 toRenderInline(c)->layer()->setStaticX(style()->direction() == LTR ? leftOffset(height(), firstLine) : rightOffset(height(), firstLine));
1531                 toRenderInline(c)->layer()->setStaticY(height());
1532             }
1533     
1534             RenderBox* box = toRenderBox(object);
1535             if (box->style()->hasStaticX()) {
1536                 if (box->style()->isOriginalDisplayInlineType())
1537                     box->layer()->setStaticX(style()->direction() == LTR ? leftOffset(height(), firstLine) : width() - rightOffset(height(), firstLine));
1538                 else
1539                     box->layer()->setStaticX(style()->direction() == LTR ? borderLeft() + paddingLeft() : borderRight() + paddingRight());
1540             }
1541     
1542             if (box->style()->hasStaticY())
1543                 box->layer()->setStaticY(height());
1544         }
1545         resolver.increment();
1546     }
1547     resolver.commitExplicitEmbedding();
1548     return availableWidth;
1549 }
1550
1551 // This is currently just used for list markers and inline flows that have line boxes. Neither should 
1552 // have an effect on whitespace at the start of the line. 
1553 static bool shouldSkipWhitespaceAfterStartObject(RenderBlock* block, RenderObject* o, LineMidpointState& lineMidpointState)
1554 {
1555     RenderObject* next = bidiNext(block, o);
1556     if (next && !next->isBR() && next->isText() && toRenderText(next)->textLength() > 0) {
1557         RenderText* nextText = toRenderText(next);
1558         UChar nextChar = nextText->characters()[0];
1559         if (nextText->style()->isCollapsibleWhiteSpace(nextChar)) {
1560             addMidpoint(lineMidpointState, InlineIterator(0, o, 0));
1561             return true;
1562         }
1563     }
1564
1565     return false;
1566 }
1567
1568 void RenderBlock::fitBelowFloats(int widthToFit, bool firstLine, int& availableWidth)
1569 {
1570     ASSERT(widthToFit > availableWidth);
1571
1572     int floatBottom;
1573     int lastFloatBottom = height();
1574     int newLineWidth = availableWidth;
1575     while (true) {
1576         floatBottom = nextFloatBottomBelow(lastFloatBottom);
1577         if (!floatBottom)
1578             break;
1579
1580         newLineWidth = lineWidth(floatBottom, firstLine);
1581         lastFloatBottom = floatBottom;
1582         if (newLineWidth >= widthToFit)
1583             break;
1584     }
1585
1586     if (newLineWidth > availableWidth) {
1587         setHeight(lastFloatBottom);
1588         availableWidth = newLineWidth;
1589     }
1590 }
1591
1592 static inline unsigned textWidth(RenderText* text, unsigned from, unsigned len, const Font& font, int xPos, bool isFixedPitch, bool collapseWhiteSpace)
1593 {
1594     if (isFixedPitch || (!from && len == text->textLength()))
1595         return text->width(from, len, font, xPos);
1596     return font.width(TextRun(text->characters() + from, len, !collapseWhiteSpace, xPos));
1597 }
1598
1599 InlineIterator RenderBlock::findNextLineBreak(InlineBidiResolver& resolver, bool firstLine,  bool& isLineEmpty, bool& previousLineBrokeCleanly, 
1600                                               EClear* clear)
1601 {
1602     ASSERT(resolver.position().block == this);
1603
1604     bool appliedStartWidth = resolver.position().pos > 0;
1605     LineMidpointState& lineMidpointState = resolver.midpointState();
1606     
1607     int width = skipLeadingWhitespace(resolver, firstLine, isLineEmpty, previousLineBrokeCleanly);
1608
1609     int w = 0;
1610     int tmpW = 0;
1611
1612     if (resolver.position().atEnd())
1613         return resolver.position();
1614
1615     // This variable is used only if whitespace isn't set to PRE, and it tells us whether
1616     // or not we are currently ignoring whitespace.
1617     bool ignoringSpaces = false;
1618     InlineIterator ignoreStart;
1619     
1620     // This variable tracks whether the very last character we saw was a space.  We use
1621     // this to detect when we encounter a second space so we know we have to terminate
1622     // a run.
1623     bool currentCharacterIsSpace = false;
1624     bool currentCharacterIsWS = false;
1625     RenderObject* trailingSpaceObject = 0;
1626
1627     InlineIterator lBreak = resolver.position();
1628
1629     RenderObject *o = resolver.position().obj;
1630     RenderObject *last = o;
1631     unsigned pos = resolver.position().pos;
1632     int nextBreakable = resolver.position().nextBreakablePosition;
1633     bool atStart = true;
1634
1635     bool prevLineBrokeCleanly = previousLineBrokeCleanly;
1636     previousLineBrokeCleanly = false;
1637
1638     bool autoWrapWasEverTrueOnLine = false;
1639     bool floatsFitOnLine = true;
1640     
1641     // Firefox and Opera will allow a table cell to grow to fit an image inside it under
1642     // very specific circumstances (in order to match common WinIE renderings). 
1643     // Not supporting the quirk has caused us to mis-render some real sites. (See Bugzilla 10517.) 
1644     bool allowImagesToBreak = !style()->htmlHacks() || !isTableCell() || !style()->width().isIntrinsicOrAuto();
1645
1646     EWhiteSpace currWS = style()->whiteSpace();
1647     EWhiteSpace lastWS = currWS;
1648     while (o) {
1649         currWS = o->isReplaced() ? o->parent()->style()->whiteSpace() : o->style()->whiteSpace();
1650         lastWS = last->isReplaced() ? last->parent()->style()->whiteSpace() : last->style()->whiteSpace();
1651         
1652         bool autoWrap = RenderStyle::autoWrap(currWS);
1653         autoWrapWasEverTrueOnLine = autoWrapWasEverTrueOnLine || autoWrap;
1654
1655 #if ENABLE(SVG)
1656         bool preserveNewline = o->isSVGText() ? false : RenderStyle::preserveNewline(currWS);
1657 #else
1658         bool preserveNewline = RenderStyle::preserveNewline(currWS);
1659 #endif
1660
1661         bool collapseWhiteSpace = RenderStyle::collapseWhiteSpace(currWS);
1662             
1663         if (o->isBR()) {
1664             if (w + tmpW <= width) {
1665                 lBreak.obj = o;
1666                 lBreak.pos = 0;
1667                 lBreak.nextBreakablePosition = -1;
1668                 lBreak.increment();
1669
1670                 // A <br> always breaks a line, so don't let the line be collapsed
1671                 // away. Also, the space at the end of a line with a <br> does not
1672                 // get collapsed away.  It only does this if the previous line broke
1673                 // cleanly.  Otherwise the <br> has no effect on whether the line is
1674                 // empty or not.
1675                 if (prevLineBrokeCleanly)
1676                     isLineEmpty = false;
1677                 trailingSpaceObject = 0;
1678                 previousLineBrokeCleanly = true;
1679
1680                 if (!isLineEmpty && clear)
1681                     *clear = o->style()->clear();
1682             }
1683             goto end;
1684         }
1685
1686         if (o->isFloatingOrPositioned()) {
1687             // add to special objects...
1688             if (o->isFloating()) {
1689                 RenderBox* floatBox = toRenderBox(o);
1690                 insertFloatingObject(floatBox);
1691                 // check if it fits in the current line.
1692                 // If it does, position it now, otherwise, position
1693                 // it after moving to next line (in newLine() func)
1694                 if (floatsFitOnLine && floatBox->width() + floatBox->marginLeft() + floatBox->marginRight() + w + tmpW <= width) {
1695                     positionNewFloats();
1696                     width = lineWidth(height(), firstLine);
1697                 } else
1698                     floatsFitOnLine = false;
1699             } else if (o->isPositioned()) {
1700                 // If our original display wasn't an inline type, then we can
1701                 // go ahead and determine our static x position now.
1702                 RenderBox* box = toRenderBox(o);
1703                 bool isInlineType = box->style()->isOriginalDisplayInlineType();
1704                 bool needToSetStaticX = box->style()->hasStaticX();
1705                 if (box->style()->hasStaticX() && !isInlineType) {
1706                     box->layer()->setStaticX(o->parent()->style()->direction() == LTR ?
1707                                   borderLeft() + paddingLeft() :
1708                                   borderRight() + paddingRight());
1709                     needToSetStaticX = false;
1710                 }
1711
1712                 // If our original display was an INLINE type, then we can go ahead
1713                 // and determine our static y position now.
1714                 bool needToSetStaticY = box->style()->hasStaticY();
1715                 if (box->style()->hasStaticY() && isInlineType) {
1716                     box->layer()->setStaticY(height());
1717                     needToSetStaticY = false;
1718                 }
1719                 
1720                 bool needToCreateLineBox = needToSetStaticX || needToSetStaticY;
1721                 RenderObject* c = o->container();
1722                 if (c->isRenderInline() && (!needToSetStaticX || !needToSetStaticY))
1723                     needToCreateLineBox = true;
1724
1725                 // If we're ignoring spaces, we have to stop and include this object and
1726                 // then start ignoring spaces again.
1727                 if (needToCreateLineBox) {
1728                     trailingSpaceObject = 0;
1729                     ignoreStart.obj = o;
1730                     ignoreStart.pos = 0;
1731                     if (ignoringSpaces) {
1732                         addMidpoint(lineMidpointState, ignoreStart); // Stop ignoring spaces.
1733                         addMidpoint(lineMidpointState, ignoreStart); // Start ignoring again.
1734                     }
1735                     
1736                 }
1737             }
1738         } else if (o->isRenderInline()) {
1739             // Right now, we should only encounter empty inlines here.
1740             ASSERT(!o->firstChild());
1741     
1742             RenderInline* flowBox = toRenderInline(o);
1743             
1744             // Now that some inline flows have line boxes, if we are already ignoring spaces, we need 
1745             // to make sure that we stop to include this object and then start ignoring spaces again. 
1746             // If this object is at the start of the line, we need to behave like list markers and 
1747             // start ignoring spaces.
1748             if (inlineFlowRequiresLineBox(flowBox)) {
1749                 isLineEmpty = false;
1750                 if (ignoringSpaces) {
1751                     trailingSpaceObject = 0;
1752                     addMidpoint(lineMidpointState, InlineIterator(0, o, 0)); // Stop ignoring spaces.
1753                     addMidpoint(lineMidpointState, InlineIterator(0, o, 0)); // Start ignoring again.
1754                 } else if (style()->collapseWhiteSpace() && resolver.position().obj == o
1755                     && shouldSkipWhitespaceAfterStartObject(this, o, lineMidpointState)) {
1756                     // Like with list markers, we start ignoring spaces to make sure that any 
1757                     // additional spaces we see will be discarded.
1758                     currentCharacterIsSpace = true;
1759                     currentCharacterIsWS = true;
1760                     ignoringSpaces = true;
1761                 }
1762             }
1763
1764             tmpW += flowBox->marginLeft() + flowBox->borderLeft() + flowBox->paddingLeft() +
1765                     flowBox->marginRight() + flowBox->borderRight() + flowBox->paddingRight();
1766         } else if (o->isReplaced()) {
1767             RenderBox* replacedBox = toRenderBox(o);
1768
1769             // Break on replaced elements if either has normal white-space.
1770             if ((autoWrap || RenderStyle::autoWrap(lastWS)) && (!o->isImage() || allowImagesToBreak)) {
1771                 w += tmpW;
1772                 tmpW = 0;
1773                 lBreak.obj = o;
1774                 lBreak.pos = 0;
1775                 lBreak.nextBreakablePosition = -1;
1776             }
1777
1778             if (ignoringSpaces)
1779                 addMidpoint(lineMidpointState, InlineIterator(0, o, 0));
1780
1781             isLineEmpty = false;
1782             ignoringSpaces = false;
1783             currentCharacterIsSpace = false;
1784             currentCharacterIsWS = false;
1785             trailingSpaceObject = 0;
1786             
1787             // Optimize for a common case. If we can't find whitespace after the list
1788             // item, then this is all moot. -dwh
1789             if (o->isListMarker() && !toRenderListMarker(o)->isInside()) {
1790                 if (style()->collapseWhiteSpace() && shouldSkipWhitespaceAfterStartObject(this, o, lineMidpointState)) {
1791                     // Like with inline flows, we start ignoring spaces to make sure that any 
1792                     // additional spaces we see will be discarded.
1793                     currentCharacterIsSpace = true;
1794                     currentCharacterIsWS = true;
1795                     ignoringSpaces = true;
1796                 }
1797             } else
1798                 tmpW += replacedBox->width() + replacedBox->marginLeft() + replacedBox->marginRight() + inlineWidth(o);
1799         } else if (o->isText()) {
1800             if (!pos)
1801                 appliedStartWidth = false;
1802
1803             RenderText* t = toRenderText(o);
1804
1805             int strlen = t->textLength();
1806             int len = strlen - pos;
1807             const UChar* str = t->characters();
1808
1809             const Font& f = t->style(firstLine)->font();
1810             bool isFixedPitch = f.isFixedPitch();
1811
1812             int lastSpace = pos;
1813             int wordSpacing = o->style()->wordSpacing();
1814             int lastSpaceWordSpacing = 0;
1815
1816             int wrapW = tmpW + inlineWidth(o, !appliedStartWidth, true);
1817             int charWidth = 0;
1818             bool breakNBSP = autoWrap && o->style()->nbspMode() == SPACE;
1819             // Auto-wrapping text should wrap in the middle of a word only if it could not wrap before the word,
1820             // which is only possible if the word is the first thing on the line, that is, if |w| is zero.
1821             bool breakWords = o->style()->breakWords() && ((autoWrap && !w) || currWS == PRE);
1822             bool midWordBreak = false;
1823             bool breakAll = o->style()->wordBreak() == BreakAllWordBreak && autoWrap;
1824
1825             if (t->isWordBreak()) {
1826                 w += tmpW;
1827                 tmpW = 0;
1828                 lBreak.obj = o;
1829                 lBreak.pos = 0;
1830                 lBreak.nextBreakablePosition = -1;
1831                 ASSERT(!len);
1832             }
1833
1834             while (len) {
1835                 bool previousCharacterIsSpace = currentCharacterIsSpace;
1836                 bool previousCharacterIsWS = currentCharacterIsWS;
1837                 UChar c = str[pos];
1838                 currentCharacterIsSpace = c == ' ' || c == '\t' || (!preserveNewline && (c == '\n'));
1839
1840                 if (!collapseWhiteSpace || !currentCharacterIsSpace)
1841                     isLineEmpty = false;
1842                 
1843                 // Check for soft hyphens.  Go ahead and ignore them.
1844                 if (c == softHyphen) {
1845                     if (!ignoringSpaces) {
1846                         // Ignore soft hyphens
1847                         InlineIterator beforeSoftHyphen;
1848                         if (pos)
1849                             beforeSoftHyphen = InlineIterator(0, o, pos - 1);
1850                         else
1851                             beforeSoftHyphen = InlineIterator(0, last, last->isText() ? toRenderText(last)->textLength() - 1 : 0);
1852                         // Two consecutive soft hyphens. Avoid overlapping midpoints.
1853                         if (lineMidpointState.numMidpoints && lineMidpointState.midpoints[lineMidpointState.numMidpoints - 1].obj == o && 
1854                             lineMidpointState.midpoints[lineMidpointState.numMidpoints - 1].pos == pos)
1855                             lineMidpointState.numMidpoints--;
1856                         else
1857                             addMidpoint(lineMidpointState, beforeSoftHyphen);
1858
1859                         // Add the width up to but not including the hyphen.
1860                         tmpW += textWidth(t, lastSpace, pos - lastSpace, f, w + tmpW, isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
1861
1862                         // For wrapping text only, include the hyphen.  We need to ensure it will fit
1863                         // on the line if it shows when we break.
1864                         if (autoWrap)
1865                             tmpW += textWidth(t, pos, 1, f, w + tmpW, isFixedPitch, collapseWhiteSpace);
1866
1867                         InlineIterator afterSoftHyphen(0, o, pos);
1868                         afterSoftHyphen.increment();
1869                         addMidpoint(lineMidpointState, afterSoftHyphen);
1870                     }
1871
1872                     pos++;
1873                     len--;
1874                     lastSpaceWordSpacing = 0;
1875                     lastSpace = pos; // Cheesy hack to prevent adding in widths of the run twice.
1876                     continue;
1877                 }
1878                 
1879                 bool applyWordSpacing = false;
1880                 
1881                 currentCharacterIsWS = currentCharacterIsSpace || (breakNBSP && c == noBreakSpace);
1882
1883                 if ((breakAll || breakWords) && !midWordBreak) {
1884                     wrapW += charWidth;
1885                     charWidth = textWidth(t, pos, 1, f, w + wrapW, isFixedPitch, collapseWhiteSpace);
1886                     midWordBreak = w + wrapW + charWidth > width;
1887                 }
1888
1889                 bool betweenWords = c == '\n' || (currWS != PRE && !atStart && isBreakable(str, pos, strlen, nextBreakable, breakNBSP));
1890     
1891                 if (betweenWords || midWordBreak) {
1892                     bool stoppedIgnoringSpaces = false;
1893                     if (ignoringSpaces) {
1894                         if (!currentCharacterIsSpace) {
1895                             // Stop ignoring spaces and begin at this
1896                             // new point.
1897                             ignoringSpaces = false;
1898                             lastSpaceWordSpacing = 0;
1899                             lastSpace = pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
1900                             addMidpoint(lineMidpointState, InlineIterator(0, o, pos));
1901                             stoppedIgnoringSpaces = true;
1902                         } else {
1903                             // Just keep ignoring these spaces.
1904                             pos++;
1905                             len--;
1906                             continue;
1907                         }
1908                     }
1909
1910                     int additionalTmpW = textWidth(t, lastSpace, pos - lastSpace, f, w + tmpW, isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
1911                     tmpW += additionalTmpW;
1912                     if (!appliedStartWidth) {
1913                         tmpW += inlineWidth(o, true, false);
1914                         appliedStartWidth = true;
1915                     }
1916                     
1917                     applyWordSpacing =  wordSpacing && currentCharacterIsSpace && !previousCharacterIsSpace;
1918
1919                     if (!w && autoWrap && tmpW > width)
1920                         fitBelowFloats(tmpW, firstLine, width);
1921
1922                     if (autoWrap || breakWords) {
1923                         // If we break only after white-space, consider the current character
1924                         // as candidate width for this line.
1925                         bool lineWasTooWide = false;
1926                         if (w + tmpW <= width && currentCharacterIsWS && o->style()->breakOnlyAfterWhiteSpace() && !midWordBreak) {
1927                             int charWidth = textWidth(t, pos, 1, f, w + tmpW, isFixedPitch, collapseWhiteSpace) + (applyWordSpacing ? wordSpacing : 0);
1928                             // Check if line is too big even without the extra space
1929                             // at the end of the line. If it is not, do nothing. 
1930                             // If the line needs the extra whitespace to be too long, 
1931                             // then move the line break to the space and skip all 
1932                             // additional whitespace.
1933                             if (w + tmpW + charWidth > width) {
1934                                 lineWasTooWide = true;
1935                                 lBreak.obj = o;
1936                                 lBreak.pos = pos;
1937                                 lBreak.nextBreakablePosition = nextBreakable;
1938                                 skipTrailingWhitespace(lBreak, isLineEmpty, previousLineBrokeCleanly);
1939                             }
1940                         }
1941                         if (lineWasTooWide || w + tmpW > width) {
1942                             if (lBreak.obj && shouldPreserveNewline(lBreak.obj) && lBreak.obj->isText() && !toRenderText(lBreak.obj)->isWordBreak() && toRenderText(lBreak.obj)->characters()[lBreak.pos] == '\n') {
1943                                 if (!stoppedIgnoringSpaces && pos > 0) {
1944                                     // We need to stop right before the newline and then start up again.
1945                                     addMidpoint(lineMidpointState, InlineIterator(0, o, pos - 1)); // Stop
1946                                     addMidpoint(lineMidpointState, InlineIterator(0, o, pos)); // Start
1947                                 }
1948                                 lBreak.increment();
1949                                 previousLineBrokeCleanly = true;
1950                             }
1951                             goto end; // Didn't fit. Jump to the end.
1952                         } else {
1953                             if (!betweenWords || (midWordBreak && !autoWrap))
1954                                 tmpW -= additionalTmpW;
1955                             if (pos > 0 && str[pos-1] == softHyphen)
1956                                 // Subtract the width of the soft hyphen out since we fit on a line.
1957                                 tmpW -= textWidth(t, pos - 1, 1, f, w + tmpW, isFixedPitch, collapseWhiteSpace);
1958                         }
1959                     }
1960
1961                     if (c == '\n' && preserveNewline) {
1962                         if (!stoppedIgnoringSpaces && pos > 0) {
1963                             // We need to stop right before the newline and then start up again.
1964                             addMidpoint(lineMidpointState, InlineIterator(0, o, pos - 1)); // Stop
1965                             addMidpoint(lineMidpointState, InlineIterator(0, o, pos)); // Start
1966                         }
1967                         lBreak.obj = o;
1968                         lBreak.pos = pos;
1969                         lBreak.nextBreakablePosition = nextBreakable;
1970                         lBreak.increment();
1971                         previousLineBrokeCleanly = true;
1972                         return lBreak;
1973                     }
1974
1975                     if (autoWrap && betweenWords) {
1976                         w += tmpW;
1977                         wrapW = 0;
1978                         tmpW = 0;
1979                         lBreak.obj = o;
1980                         lBreak.pos = pos;
1981                         lBreak.nextBreakablePosition = nextBreakable;
1982                         // Auto-wrapping text should not wrap in the middle of a word once it has had an
1983                         // opportunity to break after a word.
1984                         breakWords = false;
1985                     }
1986                     
1987                     if (midWordBreak) {
1988                         // Remember this as a breakable position in case
1989                         // adding the end width forces a break.
1990                         lBreak.obj = o;
1991                         lBreak.pos = pos;
1992                         lBreak.nextBreakablePosition = nextBreakable;
1993                         midWordBreak &= (breakWords || breakAll);
1994                     }
1995
1996                     if (betweenWords) {
1997                         lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
1998                         lastSpace = pos;
1999                     }
2000                     
2001                     if (!ignoringSpaces && o->style()->collapseWhiteSpace()) {
2002                         // If we encounter a newline, or if we encounter a
2003                         // second space, we need to go ahead and break up this
2004                         // run and enter a mode where we start collapsing spaces.
2005                         if (currentCharacterIsSpace && previousCharacterIsSpace) {
2006                             ignoringSpaces = true;
2007                             
2008                             // We just entered a mode where we are ignoring
2009                             // spaces. Create a midpoint to terminate the run
2010                             // before the second space. 
2011                             addMidpoint(lineMidpointState, ignoreStart);
2012                         }
2013                     }
2014                 } else if (ignoringSpaces) {
2015                     // Stop ignoring spaces and begin at this
2016                     // new point.
2017                     ignoringSpaces = false;
2018                     lastSpaceWordSpacing = applyWordSpacing ? wordSpacing : 0;
2019                     lastSpace = pos; // e.g., "Foo    goo", don't add in any of the ignored spaces.
2020                     addMidpoint(lineMidpointState, InlineIterator(0, o, pos));
2021                 }
2022
2023                 if (currentCharacterIsSpace && !previousCharacterIsSpace) {
2024                     ignoreStart.obj = o;
2025                     ignoreStart.pos = pos;
2026                 }
2027
2028                 if (!currentCharacterIsWS && previousCharacterIsWS) {
2029                     if (autoWrap && o->style()->breakOnlyAfterWhiteSpace()) {
2030                         lBreak.obj = o;
2031                         lBreak.pos = pos;
2032                         lBreak.nextBreakablePosition = nextBreakable;
2033                     }
2034                 }
2035                 
2036                 if (collapseWhiteSpace && currentCharacterIsSpace && !ignoringSpaces)
2037                     trailingSpaceObject = o;
2038                 else if (!o->style()->collapseWhiteSpace() || !currentCharacterIsSpace)
2039                     trailingSpaceObject = 0;
2040                     
2041                 pos++;
2042                 len--;
2043                 atStart = false;
2044             }
2045
2046             // IMPORTANT: pos is > length here!
2047             if (!ignoringSpaces)
2048                 tmpW += textWidth(t, lastSpace, pos - lastSpace, f, w + tmpW, isFixedPitch, collapseWhiteSpace) + lastSpaceWordSpacing;
2049             tmpW += inlineWidth(o, !appliedStartWidth, true);
2050         } else
2051             ASSERT_NOT_REACHED();
2052
2053         RenderObject* next = bidiNext(this, o);
2054         bool checkForBreak = autoWrap;
2055         if (w && w + tmpW > width && lBreak.obj && currWS == NOWRAP)
2056             checkForBreak = true;
2057         else if (next && o->isText() && next->isText() && !next->isBR()) {
2058             if (autoWrap || (next->style()->autoWrap())) {
2059                 if (currentCharacterIsSpace)
2060                     checkForBreak = true;
2061                 else {
2062                     checkForBreak = false;
2063                     RenderText* nextText = toRenderText(next);
2064                     if (nextText->textLength()) {
2065                         UChar c = nextText->characters()[0];
2066                         if (c == ' ' || c == '\t' || (c == '\n' && !shouldPreserveNewline(next)))
2067                             // If the next item on the line is text, and if we did not end with
2068                             // a space, then the next text run continues our word (and so it needs to
2069                             // keep adding to |tmpW|.  Just update and continue.
2070                             checkForBreak = true;
2071                     } else if (nextText->isWordBreak())
2072                         checkForBreak = true;
2073                     bool willFitOnLine = w + tmpW <= width;
2074                     if (!willFitOnLine && !w) {
2075                         fitBelowFloats(tmpW, firstLine, width);
2076                         willFitOnLine = tmpW <= width;
2077                     }
2078                     bool canPlaceOnLine = willFitOnLine || !autoWrapWasEverTrueOnLine;
2079                     if (canPlaceOnLine && checkForBreak) {
2080                         w += tmpW;
2081                         tmpW = 0;
2082                         lBreak.obj = next;
2083                         lBreak.pos = 0;
2084                         lBreak.nextBreakablePosition = -1;
2085                     }
2086                 }
2087             }
2088         }
2089
2090         if (checkForBreak && (w + tmpW > width)) {
2091             // if we have floats, try to get below them.
2092             if (currentCharacterIsSpace && !ignoringSpaces && o->style()->collapseWhiteSpace())
2093                 trailingSpaceObject = 0;
2094
2095             if (w)
2096                 goto end;
2097
2098             fitBelowFloats(tmpW, firstLine, width);
2099
2100             // |width| may have been adjusted because we got shoved down past a float (thus
2101             // giving us more room), so we need to retest, and only jump to
2102             // the end label if we still don't fit on the line. -dwh
2103             if (w + tmpW > width)
2104                 goto end;
2105         }
2106
2107         if (!o->isFloatingOrPositioned()) {
2108             last = o;
2109             if (last->isReplaced() && autoWrap && (!last->isImage() || allowImagesToBreak) && (!last->isListMarker() || toRenderListMarker(last)->isInside())) {
2110                 w += tmpW;
2111                 tmpW = 0;
2112                 lBreak.obj = next;
2113                 lBreak.pos = 0;
2114                 lBreak.nextBreakablePosition = -1;
2115             }
2116         }
2117
2118         o = next;
2119         nextBreakable = -1;
2120
2121         // Clear out our character space bool, since inline <pre>s don't collapse whitespace
2122         // with adjacent inline normal/nowrap spans.
2123         if (!collapseWhiteSpace)
2124             currentCharacterIsSpace = false;
2125         
2126         pos = 0;
2127         atStart = false;
2128     }
2129
2130     
2131     if (w + tmpW <= width || lastWS == NOWRAP) {
2132         lBreak.obj = 0;
2133         lBreak.pos = 0;
2134         lBreak.nextBreakablePosition = -1;
2135     }
2136
2137  end:
2138     if (lBreak == resolver.position() && (!lBreak.obj || !lBreak.obj->isBR())) {
2139         // we just add as much as possible
2140         if (style()->whiteSpace() == PRE) {
2141             // FIXME: Don't really understand this case.
2142             if (pos != 0) {
2143                 lBreak.obj = o;
2144                 lBreak.pos = pos - 1;
2145             } else {
2146                 lBreak.obj = last;
2147                 lBreak.pos = last->isText() ? last->length() : 0;
2148                 lBreak.nextBreakablePosition = -1;
2149             }
2150         } else if (lBreak.obj) {
2151             if (last != o && !last->isListMarker()) {
2152                 // better to break between object boundaries than in the middle of a word (except for list markers)
2153                 lBreak.obj = o;
2154                 lBreak.pos = 0;
2155                 lBreak.nextBreakablePosition = -1;
2156             } else {
2157                 // Don't ever break in the middle of a word if we can help it.
2158                 // There's no room at all. We just have to be on this line,
2159                 // even though we'll spill out.
2160                 lBreak.obj = o;
2161                 lBreak.pos = pos;
2162                 lBreak.nextBreakablePosition = -1;
2163             }
2164         }
2165     }
2166
2167     // make sure we consume at least one char/object.
2168     if (lBreak == resolver.position())
2169         lBreak.increment();
2170
2171     // Sanity check our midpoints.
2172     checkMidpoints(lineMidpointState, lBreak);
2173         
2174     if (trailingSpaceObject) {
2175         // This object is either going to be part of the last midpoint, or it is going
2176         // to be the actual endpoint.  In both cases we just decrease our pos by 1 level to
2177         // exclude the space, allowing it to - in effect - collapse into the newline.
2178         if (lineMidpointState.numMidpoints % 2) {
2179             InlineIterator* midpoints = lineMidpointState.midpoints.data();
2180             midpoints[lineMidpointState.numMidpoints - 1].pos--;
2181         }
2182         //else if (lBreak.pos > 0)
2183         //    lBreak.pos--;
2184         else if (lBreak.obj == 0 && trailingSpaceObject->isText()) {
2185             // Add a new end midpoint that stops right at the very end.
2186             RenderText* text = toRenderText(trailingSpaceObject);
2187             unsigned length = text->textLength();
2188             unsigned pos = length >= 2 ? length - 2 : UINT_MAX;
2189             InlineIterator endMid(0, trailingSpaceObject, pos);
2190             addMidpoint(lineMidpointState, endMid);
2191         }
2192     }
2193
2194     // We might have made lBreak an iterator that points past the end
2195     // of the object. Do this adjustment to make it point to the start
2196     // of the next object instead to avoid confusing the rest of the
2197     // code.
2198     if (lBreak.pos > 0) {
2199         lBreak.pos--;
2200         lBreak.increment();
2201     }
2202
2203     if (lBreak.obj && lBreak.pos >= 2 && lBreak.obj->isText()) {
2204         // For soft hyphens on line breaks, we have to chop out the midpoints that made us
2205         // ignore the hyphen so that it will render at the end of the line.
2206         UChar c = toRenderText(lBreak.obj)->characters()[lBreak.pos - 1];
2207         if (c == softHyphen)
2208             chopMidpointsAt(lineMidpointState, lBreak.obj, lBreak.pos - 2);
2209     }
2210     
2211     return lBreak;
2212 }
2213
2214 void RenderBlock::checkLinesForOverflow()
2215 {
2216     m_overflowWidth = width();
2217     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2218         m_overflowLeft = min(curr->leftOverflow(), m_overflowLeft);
2219         m_overflowTop = min(curr->topOverflow(), m_overflowTop);
2220         m_overflowWidth = max(curr->rightOverflow(), m_overflowWidth);
2221         m_overflowHeight = max(curr->bottomOverflow(), m_overflowHeight);
2222     }
2223 }
2224
2225 void RenderBlock::deleteEllipsisLineBoxes()
2226 {
2227     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox())
2228         curr->clearTruncation();
2229 }
2230
2231 void RenderBlock::checkLinesForTextOverflow()
2232 {
2233     // Determine the width of the ellipsis using the current font.
2234     // FIXME: CSS3 says this is configurable, also need to use 0x002E (FULL STOP) if horizontal ellipsis is "not renderable"
2235     TextRun ellipsisRun(&horizontalEllipsis, 1);
2236     DEFINE_STATIC_LOCAL(AtomicString, ellipsisStr, (&horizontalEllipsis, 1));
2237     const Font& firstLineFont = firstLineStyle()->font();
2238     const Font& font = style()->font();
2239     int firstLineEllipsisWidth = firstLineFont.width(ellipsisRun);
2240     int ellipsisWidth = (font == firstLineFont) ? firstLineEllipsisWidth : font.width(ellipsisRun);
2241
2242     // For LTR text truncation, we want to get the right edge of our padding box, and then we want to see
2243     // if the right edge of a line box exceeds that.  For RTL, we use the left edge of the padding box and
2244     // check the left edge of the line box to see if it is less
2245     // Include the scrollbar for overflow blocks, which means we want to use "contentWidth()"
2246     bool ltr = style()->direction() == LTR;
2247     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
2248         int blockRightEdge = rightOffset(curr->y(), curr == firstRootBox());
2249         int blockLeftEdge = leftOffset(curr->y(), curr == firstRootBox());
2250         int lineBoxEdge = ltr ? curr->x() + curr->width() : curr->x();
2251         if ((ltr && lineBoxEdge > blockRightEdge) || (!ltr && lineBoxEdge < blockLeftEdge)) {
2252             // This line spills out of our box in the appropriate direction.  Now we need to see if the line
2253             // can be truncated.  In order for truncation to be possible, the line must have sufficient space to
2254             // accommodate our truncation string, and no replaced elements (images, tables) can overlap the ellipsis
2255             // space.
2256             int width = curr == firstRootBox() ? firstLineEllipsisWidth : ellipsisWidth;
2257             int blockEdge = ltr ? blockRightEdge : blockLeftEdge;
2258             if (curr->canAccommodateEllipsis(ltr, blockEdge, lineBoxEdge, width))
2259                 curr->placeEllipsis(ellipsisStr, ltr, blockLeftEdge, blockRightEdge, width);
2260         }
2261     }
2262 }
2263
2264 }