WebCore/rendering/bidi.cpp

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