khtml Library API Documentation

bidi.cpp

00001 
00023 #include "bidi.h"
00024 #include "break_lines.h"
00025 #include "render_flow.h"
00026 #include "render_text.h"
00027 using namespace khtml;
00028 
00029 #include "kdebug.h"
00030 #include "qdatetime.h"
00031 #include "qfontmetrics.h"
00032 
00033 #define BIDI_DEBUG 0
00034 //#define DEBUG_LINEBREAKS
00035 
00036 #if BIDI_DEBUG > 1
00037 
00038 // the ones from the QChar class
00039 static const char *directions[] = {
00040     "DirL", "DirR", "DirEN", "DirES", "DirET", "DirAN", "DirCS", "DirB", "DirS", "DirWS", "DirON",
00041     "DirLRE", "DirLRO", "DirAL", "DirRLE", "DirRLO", "DirPDF", "DirNSM", "DirBN"
00042 };
00043 
00044 inline kdbgstream &operator<<(kdbgstream &stream, QChar::Direction d) {
00045     return (stream << directions[d]);
00046 }
00047 
00048 
00049 #endif
00050 
00051 inline BidiIterator::BidiIterator()
00052 {
00053     par = 0;
00054     obj = 0;
00055     pos = 0;
00056 }
00057 
00058 static BidiIterator sor;
00059 static BidiIterator eor;
00060 static BidiIterator last;
00061 static BidiIterator current;
00062 static BidiContext *context;
00063 static BidiStatus status;
00064 static QPtrList<BidiRun> *sruns = 0;
00065 static QChar::Direction dir;
00066 static bool adjustEmbeddding = false;
00067 static bool emptyRun = true;
00068 static int numSpaces;
00069 
00070 static void embed( QChar::Direction d );
00071 static void appendRun();
00072 
00073 // ---------------------------------------------------------------------
00074 
00075 /* a small helper class used internally to resolve Bidi embedding levels.
00076    Each line of text caches the embedding level at the start of the line for faster
00077    relayouting
00078 */
00079 BidiContext::BidiContext(unsigned char l, QChar::Direction e, BidiContext *p, bool o)
00080     : level(l) , override(o), dir(e)
00081 {
00082     parent = p;
00083     if(p) {
00084         p->ref();
00085         basicDir = p->basicDir;
00086     } else
00087         basicDir = e;
00088     count = 0;
00089 }
00090 
00091 BidiContext::~BidiContext()
00092 {
00093     if(parent) parent->deref();
00094 }
00095 
00096 void BidiContext::ref() const
00097 {
00098     count++;
00099 }
00100 
00101 void BidiContext::deref() const
00102 {
00103     count--;
00104     if(count <= 0) delete this;
00105 }
00106 
00107 // ---------------------------------------------------------------------
00108 
00109 inline bool operator==( const BidiIterator &it1, const BidiIterator &it2 )
00110 {
00111     if(it1.pos != it2.pos) return false;
00112     if(it1.obj != it2.obj) return false;
00113     return true;
00114 }
00115 
00116 inline bool operator!=( const BidiIterator &it1, const BidiIterator &it2 )
00117 {
00118     if(it1.pos != it2.pos) return true;
00119     if(it1.obj != it2.obj) return true;
00120     return false;
00121 }
00122 
00123 static inline RenderObject *Bidinext(RenderObject *par, RenderObject *current)
00124 {
00125     RenderObject *next = 0;
00126     while(current != 0)
00127     {
00128         //kdDebug( 6040 ) << "current = " << current << endl;
00129         if(!current->isFloating() && !current->isReplaced() && !current->isPositioned()) {
00130             next = current->firstChild();
00131             if ( next && adjustEmbeddding ) {
00132                 EUnicodeBidi ub = next->style()->unicodeBidi();
00133                 if ( ub != UBNormal ) {
00134                     EDirection dir = next->style()->direction();
00135 //                  qDebug("element: unicode-bidi=%d, dir=%d", ub, dir);
00136                     QChar::Direction d = ( ub == Embed ? ( dir == RTL ? QChar::DirRLE : QChar::DirLRE )
00137                                            : ( dir == RTL ? QChar::DirRLO : QChar::DirLRO ) );
00138                     embed( d );
00139                 }
00140             }
00141         }
00142         if(!next) {
00143             while(current && current != par) {
00144                 next = current->nextSibling();
00145                 if(next) break;
00146                 if ( adjustEmbeddding && current->style()->unicodeBidi() != UBNormal && !emptyRun ) {
00147                     embed( QChar::DirPDF );
00148                 }
00149                 current = current->parent();
00150             }
00151         }
00152 
00153         if(!next) break;
00154 
00155         if(next->isText() || next->isBR() || next->isFloating() || next->isReplaced() || next->isPositioned())
00156             break;
00157         current = next;
00158     }
00159     return next;
00160 }
00161 
00162 static RenderObject *first( RenderObject *par )
00163 {
00164     if(!par->firstChild()) return 0;
00165     RenderObject *o = par->firstChild();
00166 
00167     if(!o->isText() && !o->isBR() && !o->isReplaced() && !o->isFloating() && !o->isPositioned())
00168         o = Bidinext( par, o );
00169 
00170     return o;
00171 }
00172 
00173 BidiIterator::BidiIterator(RenderFlow *_par)
00174 {
00175     par = _par;
00176     if ( par && adjustEmbeddding ) {
00177         EUnicodeBidi ub = par->style()->unicodeBidi();
00178         if ( ub != UBNormal ) {
00179             EDirection dir = par->style()->direction();
00180 //          qDebug("element: unicode-bidi=%d, dir=%d", ub, dir);
00181             QChar::Direction d = ( ub == Embed ? ( dir == RTL ? QChar::DirRLE : QChar::DirLRE )
00182                                    : ( dir == RTL ? QChar::DirRLO : QChar::DirLRO ) );
00183             embed( d );
00184         }
00185     }
00186     obj = first( par );
00187     pos = 0;
00188     isText = obj ? obj->isText() : false;
00189 }
00190 
00191 inline BidiIterator::BidiIterator(const BidiIterator &it)
00192 {
00193     par = it.par;
00194     obj = it.obj;
00195     pos = it.pos;
00196     isText = obj ? obj->isText() : false;
00197 }
00198 
00199 inline BidiIterator::BidiIterator(RenderFlow *_par, RenderObject *_obj, int _pos)
00200 {
00201     par = _par;
00202     obj = _obj;
00203     pos = _pos;
00204     isText = obj ? obj->isText() : false;
00205 }
00206 
00207 inline BidiIterator &BidiIterator::operator = (const BidiIterator &it)
00208 {
00209     obj = it.obj;
00210     pos = it.pos;
00211     par = it.par;
00212     isText = obj ? obj->isText() : false;
00213     return *this;
00214 }
00215 
00216 inline void BidiIterator::operator ++ ()
00217 {
00218     if(!obj) return;
00219     if(isText) {
00220         pos++;
00221         if(pos >= static_cast<RenderText *>(obj)->stringLength()) {
00222             obj = Bidinext( par, obj );
00223             isText = obj ? obj->isText() : false;
00224             pos = 0;
00225         }
00226     } else {
00227         obj = Bidinext( par, obj );
00228         isText = obj ? obj->isText() : false;
00229         pos = 0;
00230     }
00231 }
00232 
00233 inline bool BidiIterator::atEnd() const
00234 {
00235     if(!obj) return true;
00236     return false;
00237 }
00238 
00239 static const QChar nbsp = QChar(0xA0);
00240 
00241 inline const QChar &BidiIterator::current() const
00242 {
00243     if( !isText ) return nbsp; // non breaking space
00244     return static_cast<RenderText *>(obj)->text()[pos];
00245 }
00246 
00247 inline QChar::Direction BidiIterator::direction() const
00248 {
00249     if( !isText ) return QChar::DirON;
00250 
00251     RenderText *renderTxt = static_cast<RenderText *>( obj );
00252     if ( pos >= renderTxt->stringLength() )
00253         return QChar::DirON;
00254     return renderTxt->text()[pos].direction();
00255 }
00256 
00257 // -------------------------------------------------------------------------------------------------
00258 
00259 static void appendRun()
00260 {
00261     if ( emptyRun ) return;
00262 #if BIDI_DEBUG > 1
00263     kdDebug(6041) << "appendRun: dir="<<(int)dir<<endl;
00264 #endif
00265 
00266     bool b = adjustEmbeddding;
00267     adjustEmbeddding = false;
00268 
00269     int start = sor.pos;
00270     RenderObject *obj = sor.obj;
00271     while( obj && obj != eor.obj ) {
00272         if(!obj->isHidden()) {
00273             //kdDebug(6041) << "appendRun: "<< start << "/" << obj->length() <<endl;
00274             sruns->append( new BidiRun(start, obj->length(), obj, context, dir) );
00275         }
00276         start = 0;
00277         obj = Bidinext( sor.par, obj );
00278     }
00279     if( obj && !obj->isHidden()) {
00280         //kdDebug(6041) << "appendRun: "<< start << "/" << eor.pos <<endl;
00281         sruns->append( new BidiRun(start, eor.pos + 1, obj, context, dir) );
00282     }
00283 
00284     ++eor;
00285     sor = eor;
00286     dir = QChar::DirON;
00287     status.eor = QChar::DirON;
00288     adjustEmbeddding = b;
00289 }
00290 
00291 static void embed( QChar::Direction d )
00292 {
00293 #if BIDI_DEBUG > 1
00294     qDebug("*** embed dir=%d emptyrun=%d", d, emptyRun );
00295 #endif
00296     bool b = adjustEmbeddding ;
00297     adjustEmbeddding = false;
00298     if ( d == QChar::DirPDF ) {
00299         BidiContext *c = context->parent;
00300         if(c && sruns) {
00301             if ( eor != last ) {
00302                 appendRun();
00303                 eor = last;
00304             }
00305             appendRun();
00306             emptyRun = true;
00307             status.last = context->dir;
00308             context->deref();
00309             context = c;
00310             if(context->override)
00311                 dir = context->dir;
00312             else
00313                 dir = QChar::DirON;
00314             status.lastStrong = context->dir;
00315         }
00316     } else {
00317         QChar::Direction runDir;
00318         if( d == QChar::DirRLE || d == QChar::DirRLO )
00319             runDir = QChar::DirR;
00320         else
00321             runDir = QChar::DirL;
00322         bool override;
00323         if( d == QChar::DirLRO || d == QChar::DirRLO )
00324             override = true;
00325         else
00326             override = false;
00327 
00328         unsigned char level = context->level;
00329         if ( runDir == QChar::DirR ) {
00330             if(level%2) // we have an odd level
00331                 level += 2;
00332             else
00333                 level++;
00334         } else {
00335             if(level%2) // we have an odd level
00336                 level++;
00337             else
00338                 level += 2;
00339         }
00340 
00341         if(level < 61) {
00342             if ( sruns ) {
00343                 if ( eor != last ) {
00344                     appendRun();
00345                     eor = last;
00346                 }
00347                 appendRun();
00348                 emptyRun = true;
00349 
00350             }
00351             context = new BidiContext(level, runDir, context, override);
00352             context->ref();
00353             if ( override )
00354                 dir = runDir;
00355             status.last = runDir;
00356             status.lastStrong = runDir;
00357         }
00358     }
00359     adjustEmbeddding = b;
00360 }
00361 
00362 
00363 // collects one line of the paragraph and transforms it to visual order
00364 void RenderFlow::bidiReorderLine(const BidiIterator &start, const BidiIterator &end)
00365 {
00366     if ( start == end ) {
00367         if ( start.current() == '\n' ) {
00368             m_height += lineHeight( firstLine );
00369         }
00370         return;
00371     }
00372 #if BIDI_DEBUG > 1
00373     kdDebug(6041) << "reordering Line from " << start.obj << "/" << start.pos << " to " << end.obj << "/" << end.pos << endl;
00374 #endif
00375 
00376     QPtrList<BidiRun> runs;
00377     runs.setAutoDelete(true);
00378     sruns = &runs;
00379 
00380     //    context->ref();
00381 
00382     dir = QChar::DirON;
00383     emptyRun = true;
00384 
00385     numSpaces = 0;
00386 
00387     current = start;
00388     last = current;
00389     bool atEnd = false;
00390     while( 1 ) {
00391 
00392         QChar::Direction dirCurrent;
00393         if(atEnd ) {
00394             //kdDebug(6041) << "atEnd" << endl;
00395             BidiContext *c = context;
00396             if ( current.atEnd())
00397                 while ( c->parent )
00398                     c = c->parent;
00399             dirCurrent = c->dir;
00400         } else {
00401             dirCurrent = current.direction();
00402         }
00403 
00404 #ifndef QT_NO_UNICODETABLES
00405 
00406         if ( context->override &&
00407              dirCurrent != QChar::DirRLE &&
00408              dirCurrent != QChar::DirLRE &&
00409              dirCurrent != QChar::DirRLO &&
00410              dirCurrent != QChar::DirLRO &&
00411              dirCurrent != QChar::DirPDF ) {
00412             eor = current;
00413             goto skipbidi;
00414         }
00415 
00416 #if BIDI_DEBUG > 1
00417         kdDebug(6041) << "directions: dir=" << dir << " current=" << dirCurrent << " last=" << status.last << " eor=" << status.eor << " lastStrong=" << status.lastStrong << " embedding=" << (int)context->dir << " level =" << (int)context->level << endl;
00418 #endif
00419         switch(dirCurrent) {
00420 
00421             // embedding and overrides (X1-X9 in the Bidi specs)
00422         case QChar::DirRLE:
00423         case QChar::DirLRE:
00424         case QChar::DirRLO:
00425         case QChar::DirLRO:
00426         case QChar::DirPDF:
00427             eor = last;
00428             embed( dirCurrent );
00429             break;
00430 
00431             // strong types
00432         case QChar::DirL:
00433             if(dir == QChar::DirON)
00434                 dir = QChar::DirL;
00435             switch(status.last)
00436                 {
00437                 case QChar::DirL:
00438                     eor = current; status.eor = QChar::DirL; break;
00439                 case QChar::DirR:
00440                 case QChar::DirAL:
00441                 case QChar::DirEN:
00442                 case QChar::DirAN:
00443                     appendRun();
00444                     break;
00445                 case QChar::DirES:
00446                 case QChar::DirET:
00447                 case QChar::DirCS:
00448                 case QChar::DirBN:
00449                 case QChar::DirB:
00450                 case QChar::DirS:
00451                 case QChar::DirWS:
00452                 case QChar::DirON:
00453                     if(dir != QChar::DirL) {
00454                         //last stuff takes embedding dir
00455                         if( context->dir == QChar::DirR ) {
00456                             if(!(status.eor == QChar::DirR)) {
00457                                 // AN or EN
00458                                 appendRun();
00459                                 dir = QChar::DirR;
00460                             }
00461                             else
00462                                 eor = last;
00463                             appendRun();
00464                             dir = QChar::DirL;
00465                             status.eor = QChar::DirL;
00466                         } else {
00467                             if(status.eor == QChar::DirR) {
00468                                 appendRun();
00469                                 dir = QChar::DirL;
00470                             } else {
00471                                 eor = current; status.eor = QChar::DirL; break;
00472                             }
00473                         }
00474                     } else {
00475                         eor = current; status.eor = QChar::DirL;
00476                     }
00477                 default:
00478                     break;
00479                 }
00480             status.lastStrong = QChar::DirL;
00481             break;
00482         case QChar::DirAL:
00483         case QChar::DirR:
00484             if(dir == QChar::DirON) dir = QChar::DirR;
00485             switch(status.last)
00486                 {
00487                 case QChar::DirR:
00488                 case QChar::DirAL:
00489                     eor = current; status.eor = QChar::DirR; break;
00490                 case QChar::DirL:
00491                 case QChar::DirEN:
00492                 case QChar::DirAN:
00493                     appendRun();
00494                     dir = QChar::DirR;
00495                     eor = current;
00496                     status.eor = QChar::DirR;
00497                     break;
00498                 case QChar::DirES:
00499                 case QChar::DirET:
00500                 case QChar::DirCS:
00501                 case QChar::DirBN:
00502                 case QChar::DirB:
00503                 case QChar::DirS:
00504                 case QChar::DirWS:
00505                 case QChar::DirON:
00506                     if( !(status.eor == QChar::DirR) && !(status.eor == QChar::DirAL) ) {
00507                         //last stuff takes embedding dir
00508                         if(context->dir == QChar::DirR || status.lastStrong == QChar::DirR) {
00509                             appendRun();
00510                             dir = QChar::DirR;
00511                             eor = current;
00512                             status.eor = QChar::DirR;
00513                         } else {
00514                             eor = last;
00515                             appendRun();
00516                             dir = QChar::DirR;
00517                             status.eor = QChar::DirR;
00518                         }
00519                     } else {
00520                         eor = current; status.eor = QChar::DirR;
00521                     }
00522                 default:
00523                     break;
00524                 }
00525             status.lastStrong = dirCurrent;
00526             break;
00527 
00528             // weak types:
00529 
00530         case QChar::DirNSM:
00531             // ### if @sor, set dir to dirSor
00532             break;
00533         case QChar::DirEN:
00534             if(!(status.lastStrong == QChar::DirAL)) {
00535                 // if last strong was AL change EN to AN
00536                 if(dir == QChar::DirON) {
00537                     if(status.lastStrong == QChar::DirAL)
00538                         dir = QChar::DirAN;
00539                     else
00540                         dir = QChar::DirL;
00541                 }
00542                 switch(status.last)
00543                     {
00544                     case QChar::DirET:
00545                         if ( status.lastStrong == QChar::DirR || status.lastStrong == QChar::DirAL ) {
00546                             appendRun();
00547                             dir = QChar::DirEN;
00548                             status.eor = QChar::DirEN;
00549                         }
00550                         // fall through
00551                     case QChar::DirEN:
00552                     case QChar::DirL:
00553                         eor = current;
00554                         status.eor = dirCurrent;
00555                         break;
00556                     case QChar::DirR:
00557                     case QChar::DirAL:
00558                     case QChar::DirAN:
00559                         appendRun();
00560                         status.eor = QChar::DirEN;
00561                         dir = QChar::DirEN;
00562                         break;
00563                     case QChar::DirES:
00564                     case QChar::DirCS:
00565                         if(status.eor == QChar::DirEN) {
00566                             eor = current; break;
00567                         }
00568                     case QChar::DirBN:
00569                     case QChar::DirB:
00570                     case QChar::DirS:
00571                     case QChar::DirWS:
00572                     case QChar::DirON:
00573                         if(status.eor == QChar::DirR) {
00574                             // neutrals go to R
00575                             eor = last;
00576                             appendRun();
00577                             dir = QChar::DirEN;
00578                             status.eor = QChar::DirEN;
00579                         }
00580                         else if( status.eor == QChar::DirL ||
00581                                  (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {
00582                             eor = current; status.eor = dirCurrent;
00583                         } else {
00584                             // numbers on both sides, neutrals get right to left direction
00585                             if(dir != QChar::DirL) {
00586                                 appendRun();
00587                                 eor = last;
00588                                 dir = QChar::DirR;
00589                                 appendRun();
00590                                 dir = QChar::DirEN;
00591                                 status.eor = QChar::DirEN;
00592                             } else {
00593                                 eor = current; status.eor = dirCurrent;
00594                             }
00595                         }
00596                     default:
00597                         break;
00598                     }
00599                 break;
00600             }
00601         case QChar::DirAN:
00602             dirCurrent = QChar::DirAN;
00603             if(dir == QChar::DirON) dir = QChar::DirAN;
00604             switch(status.last)
00605                 {
00606                 case QChar::DirL:
00607                 case QChar::DirAN:
00608                     eor = current; status.eor = QChar::DirAN; break;
00609                 case QChar::DirR:
00610                 case QChar::DirAL:
00611                 case QChar::DirEN:
00612                     appendRun();
00613                     dir = QChar::DirAN; status.eor = QChar::DirAN;
00614                     break;
00615                 case QChar::DirCS:
00616                     if(status.eor == QChar::DirAN) {
00617                         eor = current; status.eor = QChar::DirR; break;
00618                     }
00619                 case QChar::DirES:
00620                 case QChar::DirET:
00621                 case QChar::DirBN:
00622                 case QChar::DirB:
00623                 case QChar::DirS:
00624                 case QChar::DirWS:
00625                 case QChar::DirON:
00626                     if(status.eor == QChar::DirR) {
00627                         // neutrals go to R
00628                         eor = last;
00629                         appendRun();
00630                         dir = QChar::DirAN;
00631                         status.eor = QChar::DirAN;
00632                     } else if( status.eor == QChar::DirL ||
00633                                (status.eor == QChar::DirEN && status.lastStrong == QChar::DirL)) {
00634                         eor = current; status.eor = dirCurrent;
00635                     } else {
00636                         // numbers on both sides, neutrals get right to left direction
00637                         if(dir != QChar::DirL) {
00638                             appendRun();
00639                             eor = last;
00640                             dir = QChar::DirR;
00641                             appendRun();
00642                             dir = QChar::DirAN;
00643                             status.eor = QChar::DirAN;
00644                         } else {
00645                             eor = current; status.eor = dirCurrent;
00646                         }
00647                     }
00648                 default:
00649                     break;
00650                 }
00651             break;
00652         case QChar::DirES:
00653         case QChar::DirCS:
00654             break;
00655         case QChar::DirET:
00656             if(status.last == QChar::DirEN) {
00657                 dirCurrent = QChar::DirEN;
00658                 eor = current; status.eor = dirCurrent;
00659                 break;
00660             }
00661             break;
00662 
00663         // boundary neutrals should be ignored
00664         case QChar::DirBN:
00665             break;
00666             // neutrals
00667         case QChar::DirB:
00668             // ### what do we do with newline and paragraph seperators that come to here?
00669             break;
00670         case QChar::DirS:
00671             // ### implement rule L1
00672             break;
00673         case QChar::DirWS:
00674             numSpaces++;
00675         case QChar::DirON:
00676             break;
00677         default:
00678             break;
00679         }
00680 
00681     skipbidi:
00682         //cout << "     after: dir=" << //        dir << " current=" << dirCurrent << " last=" << status.last << " eor=" << status.eor << " lastStrong=" << status.lastStrong << " embedding=" << context->dir << endl;
00683 
00684         if(current.atEnd()) break;
00685 
00686         // set status.last as needed.
00687         switch(dirCurrent)
00688             {
00689             case QChar::DirET:
00690             case QChar::DirES:
00691             case QChar::DirCS:
00692             case QChar::DirS:
00693             case QChar::DirWS:
00694             case QChar::DirON:
00695                 switch(status.last)
00696                     {
00697                     case QChar::DirL:
00698                     case QChar::DirR:
00699                     case QChar::DirAL:
00700                     case QChar::DirEN:
00701                     case QChar::DirAN:
00702                         status.last = dirCurrent;
00703                         break;
00704                     default:
00705                         status.last = QChar::DirON;
00706                     }
00707                 break;
00708             case QChar::DirNSM:
00709             case QChar::DirBN:
00710                 // ignore these
00711                 break;
00712             case QChar::DirEN:
00713                 if ( status.last == QChar::DirL ) {
00714                     status.last = QChar::DirL;
00715                     break;
00716                 }
00717                 // fall through
00718             default:
00719                 status.last = dirCurrent;
00720             }
00721 #endif
00722 
00723         if ( atEnd ) break;
00724         last = current;
00725 
00726         if ( emptyRun ) {
00727             sor = current;
00728             eor = current;
00729             emptyRun = false;
00730         }
00731 
00732         // this causes the operator ++ to open and close embedding levels as needed
00733         // for the CSS unicode-bidi property
00734         adjustEmbeddding = true;
00735         ++current;
00736         adjustEmbeddding = false;
00737 
00738         if ( current == end ) {
00739             if ( emptyRun )
00740                 break;
00741             atEnd = true;
00742         }
00743     }
00744 
00745 #if BIDI_DEBUG > 0
00746     kdDebug(6041) << "reached end of line current=" << current.obj << "/" << current.pos
00747                   << ", eor=" << eor.obj << "/" << eor.pos << endl;
00748 #endif
00749     if ( !emptyRun && sor != current ) {
00750             eor = last;
00751             appendRun();
00752     }
00753 
00754     BidiContext *endEmbed = context;
00755     // both commands below together give a noop...
00756     //endEmbed->ref();
00757     //context->deref();
00758 
00759     // reorder line according to run structure...
00760 
00761     // first find highest and lowest levels
00762     uchar levelLow = 128;
00763     uchar levelHigh = 0;
00764     BidiRun *r = runs.first();
00765 
00766     while ( r ) {
00767         //paintf("level = %d\n", r->level);
00768         if ( r->level > levelHigh )
00769             levelHigh = r->level;
00770         if ( r->level < levelLow )
00771             levelLow = r->level;
00772         r = runs.next();
00773     }
00774 
00775     // implements reordering of the line (L2 according to Bidi spec):
00776     // L2. From the highest level found in the text to the lowest odd level on each line,
00777     // reverse any contiguous sequence of characters that are at that level or higher.
00778 
00779     // reversing is only done up to the lowest odd level
00780     if( !(levelLow%2) ) levelLow++;
00781 
00782 #if BIDI_DEBUG > 0
00783     kdDebug(6041) << "lineLow = " << (uint)levelLow << ", lineHigh = " << (uint)levelHigh << endl;
00784     kdDebug(6041) << "logical order is:" << endl;
00785     QPtrListIterator<BidiRun> it2(runs);
00786     BidiRun *r2;
00787     for ( ; (r2 = it2.current()); ++it2 )
00788         kdDebug(6041) << "    " << r2 << "  start=" << r2->start << "  stop=" << r2->stop << "  level=" << (uint)r2->level << endl;
00789 #endif
00790 
00791     int count = runs.count() - 1;
00792 
00793     // do not reverse for visually ordered web sites
00794     if(!style()->visuallyOrdered()) {
00795         while(levelHigh >= levelLow) {
00796             int i = 0;
00797             while ( i < count ) {
00798                 while(i < count && runs.at(i)->level < levelHigh)
00799                     i++;
00800                 int start = i;
00801                 while(i <= count && runs.at(i)->level >= levelHigh)
00802                     i++;
00803                 int end = i-1;
00804 
00805                 if(start != end) {
00806                     //kdDebug(6041) << "reversing from " << start << " to " << end << endl;
00807                     for(int j = 0; j < (end-start+1)/2; j++)
00808                         {
00809                             BidiRun *first = runs.take(start+j);
00810                             BidiRun *last = runs.take(end-j-1);
00811                             runs.insert(start+j, last);
00812                             runs.insert(end-j, first);
00813                         }
00814                 }
00815                 i++;
00816                 if(i >= count) break;
00817             }
00818             levelHigh--;
00819         }
00820     }
00821 
00822 #if BIDI_DEBUG > 0
00823     kdDebug(6041) << "visual order is:" << endl;
00824     QPtrListIterator<BidiRun> it3(runs);
00825     BidiRun *r3;
00826     for ( ; (r3 = it3.current()); ++it3 )
00827     {
00828         kdDebug(6041) << "    " << r3 << endl;
00829     }
00830 #endif
00831 
00832     int maxPositionTop = 0;
00833     int maxPositionBottom = 0;
00834     int maxAscent = 0;
00835     int maxDescent = 0;
00836     r = runs.first();
00837     while ( r ) {
00838         r->height = r->obj->lineHeight( firstLine );
00839         r->baseline = r->obj->baselinePosition( firstLine );
00840 //      if ( r->baseline > r->height )
00841 //          r->baseline = r->height;
00842         r->vertical = r->obj->verticalPositionHint( firstLine );
00843         //kdDebug(6041) << "object="<< r->obj << " height="<<r->height<<" baseline="<< r->baseline << " vertical=" << r->vertical <<endl;
00844         //int ascent;
00845         if ( r->vertical == PositionTop ) {
00846             if ( maxPositionTop < r->height ) maxPositionTop = r->height;
00847         }
00848         else if ( r->vertical == PositionBottom ) {
00849             if ( maxPositionBottom < r->height ) maxPositionBottom = r->height;
00850         }
00851         else {
00852             int ascent = r->baseline - r->vertical;
00853             int descent = r->height - ascent;
00854             if(maxAscent < ascent) maxAscent = ascent;
00855             if(maxDescent < descent) maxDescent = descent;
00856         }
00857         r = runs.next();
00858     }
00859     if ( maxAscent+maxDescent < QMAX( maxPositionTop, maxPositionBottom ) ) {
00860         // now the computed lineheight needs to be extended for the
00861         // positioned elements
00862         // see khtmltests/rendering/html_align.html
00863         // ### only iterate over the positioned ones!
00864         for ( r = runs.first(); r; r = runs.next() ) {
00865             if ( r->vertical == PositionTop ) {
00866                 if ( maxAscent + maxDescent < r->height )
00867                     maxDescent = r->height - maxAscent;
00868             }
00869             else if ( r->vertical == PositionBottom ) {
00870                 if ( maxAscent + maxDescent < r->height )
00871                     maxAscent = r->height - maxDescent;
00872             }
00873             else
00874                 continue;
00875 
00876             if ( maxAscent + maxDescent >= QMAX( maxPositionTop, maxPositionBottom ) )
00877                 break;
00878 
00879         }
00880     }
00881     int maxHeight = maxAscent + maxDescent;
00882     // CSS2: 10.8.1: line-height on the block level element specifies the *minimum*
00883     // height of the generated line box
00884     r = runs.first();
00885     // ### we have no reliable way of detecting empty lineboxes - which
00886     // are not allowed to have any height. sigh.(Dirk)
00887 //     if ( r ) {
00888 //         int blockHeight = lineHeight( firstLine );
00889 //         if ( blockHeight > maxHeight )
00890 //             maxHeight = blockHeight;
00891 //     }
00892     int totWidth = 0;
00893 #if BIDI_DEBUG > 0
00894     kdDebug( 6040 ) << "starting run.." << endl;
00895 #endif
00896     while ( r ) {
00897         if(r->vertical == PositionTop)
00898             r->vertical = m_height;
00899         else if(r->vertical == PositionBottom)
00900             r->vertical = m_height + maxHeight - r->height;
00901         else
00902             r->vertical += m_height + maxAscent - r->baseline;
00903 
00904         if(r->obj->isText())
00905             r->width = static_cast<RenderText *>(r->obj)->width(r->start, r->stop-r->start, firstLine);
00906         else {
00907             r->obj->calcWidth();
00908             r->width = r->obj->width()+r->obj->marginLeft()+r->obj->marginRight();
00909         }
00910 #if BIDI_DEBUG > 0
00911         kdDebug(6040) << "object="<< r->obj << " placing at vertical=" << r->vertical <<" width=" << r->width <<endl;
00912 #endif
00913         totWidth += r->width;
00914         r = runs.next();
00915     }
00916     //kdDebug(6040) << "yPos of line=" << m_height << "  lineBoxHeight=" << maxHeight << endl;
00917 
00918     // now construct the reordered string out of the runs...
00919 
00920     r = runs.first();
00921     int x = leftOffset(m_height);
00922     int availableWidth = lineWidth(m_height);
00923     switch(style()->textAlign()) {
00924     case LEFT:
00925         numSpaces = 0;
00926         break;
00927     case JUSTIFY:
00928         if(numSpaces != 0 && !current.atEnd() && !current.obj->isBR() )
00929             break;
00930         // fall through
00931     case TAAUTO:
00932         numSpaces = 0;
00933         // for right to left fall through to right aligned
00934         if ( endEmbed->basicDir == QChar::DirL )
00935             break;
00936     case RIGHT:
00937         x += availableWidth - totWidth;
00938         numSpaces = 0;
00939         break;
00940     case CENTER:
00941     case KONQ_CENTER:
00942         int xd = (availableWidth - totWidth)/2;
00943         x += xd>0?xd:0;
00944         numSpaces = 0;
00945         break;
00946     }
00947     while ( r ) {
00948 #if BIDI_DEBUG > 1
00949         kdDebug(6040) << "positioning " << r->obj << " start=" << r->start << " stop=" << r->stop << " x=" << x << " width=" << r->width << " yPos=" << r->vertical << endl;
00950 #endif
00951         int spaceAdd = 0;
00952         if ( numSpaces > 0 ) {
00953             if ( r->obj->isText() ) {
00954                 // get number of spaces in run
00955                 int spaces = 0;
00956                 for ( int i = r->start; i < r->stop; i++ )
00957                     if ( static_cast<RenderText *>(r->obj)->text()[i].direction() == QChar::DirWS )
00958                         spaces++;
00959                 if ( spaces > numSpaces ) // should never happen...
00960                     spaces = numSpaces;
00961                 spaceAdd = (availableWidth - totWidth)*spaces/numSpaces;
00962                 numSpaces -= spaces;
00963                 totWidth += spaceAdd;
00964             }
00965         }
00966         r->obj->position(x, r->vertical, r->start, r->stop - r->start, r->width, r->level%2, firstLine, spaceAdd);
00967         x += r->width + spaceAdd;
00968         r = runs.next();
00969     }
00970 
00971     m_height += maxHeight;
00972 
00973     sruns = 0;
00974 }
00975 
00976 
00977 void RenderFlow::layoutInlineChildren( bool relayoutChildren )
00978 {
00979     invalidateVerticalPositions();
00980 #ifdef DEBUG_LAYOUT
00981     QTime qt;
00982     qt.start();
00983     kdDebug( 6040 ) << renderName() << " layoutInlineChildren( " << this <<" )" << endl;
00984 #endif
00985 #if BIDI_DEBUG > 1 || defined( DEBUG_LINEBREAKS )
00986     kdDebug(6041) << " ------- bidi start " << this << " -------" << endl;
00987 #endif
00988     int toAdd = style()->borderBottomWidth();
00989     m_height = style()->borderTopWidth();
00990 
00991     emptyRun = true;
00992 
00993     m_height += paddingTop();
00994     toAdd += paddingBottom();
00995 
00996     if(firstChild()) {
00997         // layout replaced elements
00998         RenderObject *o = first( this );
00999         while ( o ) {
01000             if(o->isReplaced() || o->isFloating() || o->isPositioned()) {
01001                 //kdDebug(6041) << "layouting replaced or floating child" << endl;
01002                 if (relayoutChildren || o->style()->width().isPercent() || o->style()->height().isPercent())
01003                     o->setLayouted(false);
01004                 if( !o->layouted() )
01005                     o->layout();
01006                 if(o->isPositioned())
01007                     static_cast<RenderFlow*>(o->containingBlock())->insertSpecialObject(o);
01008             }
01009             else if(o->isText())
01010                 static_cast<RenderText *>(o)->deleteSlaves();
01011             o = Bidinext( this, o );
01012         }
01013 
01014         BidiContext *startEmbed;
01015         status = BidiStatus();
01016         if( style()->direction() == LTR ) {
01017             startEmbed = new BidiContext( 0, QChar::DirL );
01018             status.eor = QChar::DirL;
01019         } else {
01020             startEmbed = new BidiContext( 1, QChar::DirR );
01021             status.eor = QChar::DirR;
01022         }
01023         startEmbed->ref();
01024 
01025         context = startEmbed;
01026         adjustEmbeddding = true;
01027         BidiIterator start(this);
01028         adjustEmbeddding = false;
01029         BidiIterator end(this);
01030 
01031         firstLine = true;
01032         while( !end.atEnd() ) {
01033             start = end;
01034 
01035             end = findNextLineBreak(start);
01036             if( start.atEnd() ) break;
01037             bidiReorderLine(start, end);
01038 
01039             if( end == start || (end.obj && end.obj->isBR() && !start.obj->isBR() ) ) {
01040                 adjustEmbeddding = true;
01041                 ++end;
01042                 adjustEmbeddding = false;
01043             } else if(m_pre && end.current() == QChar('\n') ) {
01044                 adjustEmbeddding = true;
01045                 ++end;
01046                 adjustEmbeddding = false;
01047             }
01048 
01049             newLine();
01050             firstLine = false;
01051         }
01052 
01053         // clean up
01054         while ( context ) {
01055             BidiContext *parent = context->parent;
01056             delete context;
01057             context = parent;
01058         }
01059     }
01060     m_height += toAdd;
01061 
01062     // in case we have a float on the last line, it might not be positioned up to now.
01063     positionNewFloats();
01064 
01065 #if BIDI_DEBUG > 1
01066     kdDebug(6041) << " ------- bidi end " << this << " -------" << endl;
01067 #endif
01068     //kdDebug() << "RenderFlow::layoutInlineChildren time used " << qt.elapsed() << endl;
01069     //kdDebug(6040) << "height = " << m_height <<endl;
01070 }
01071 
01072 BidiIterator RenderFlow::findNextLineBreak(BidiIterator &start)
01073 {
01074     int width = lineWidth(m_height);
01075     int w = 0;
01076     int tmpW = 0;
01077 #ifdef DEBUG_LINEBREAKS
01078     kdDebug(6041) << "RenderFlow::findNextLineBreak: " << this << endl;
01079     kdDebug(6041) << "findNextLineBreak: line at " << m_height << " line width " << width << endl;
01080     kdDebug(6041) << "sol: " << start.obj << " " << start.pos << endl;
01081 #endif
01082 
01083 
01084     // eliminate spaces at beginning of line
01085     if(!m_pre) {
01086         // remove leading spaces
01087         while(!start.atEnd() &&
01088 #ifndef QT_NO_UNICODETABLES
01089               ( start.direction() == QChar::DirWS || start.obj->isSpecial() )
01090 #else
01091               ( start.current() == ' ' || start.obj->isSpecial() )
01092 #endif
01093               ) {
01094                 if( start.obj->isSpecial() ) {
01095                     RenderObject *o = start.obj;
01096                     // add to special objects...
01097                     if(o->isFloating()) {
01098                         insertSpecialObject(o);
01099                         // check if it fits in the current line.
01100                         // If it does, position it now, otherwise, position
01101                         // it after moving to next line (in newLine() func)
01102                         if (o->width()+o->marginLeft()+o->marginRight()+w+tmpW <= width) {
01103                             positionNewFloats();
01104                             width = lineWidth(m_height);
01105                         }
01106                     } else if(o->isPositioned()) {
01107                         static_cast<RenderFlow*>(o->containingBlock())->insertSpecialObject(o);
01108                     }
01109                 }
01110 
01111                 adjustEmbeddding = true;
01112                 ++start;
01113                 adjustEmbeddding = false;
01114         }
01115     }
01116     if ( start.atEnd() )
01117         return start;
01118 
01119     BidiIterator lBreak = start;
01120 
01121     RenderObject *o = start.obj;
01122     RenderObject *last = o;
01123     int pos = start.pos;
01124 
01125     while( o ) {
01126 #ifdef DEBUG_LINEBREAKS
01127         kdDebug(6041) << "new object "<< o <<" width = " << w <<" tmpw = " << tmpW << endl;
01128 #endif
01129         if(o->isBR()) {
01130             if( w + tmpW <= width ) {
01131                 lBreak = o;
01132                 //check the clear status
01133                 m_clearStatus =  (EClear) (m_clearStatus | o->style()->clear());
01134             }
01135             goto end;
01136         } else if(o->isFloating()) {
01137             insertSpecialObject(o);
01138             // check if it fits in the current line.
01139             // If it does, position it now, otherwise, position
01140             // it after moving to next line (in newLine() func)
01141             if (o->width()+o->marginLeft()+o->marginRight()+w+tmpW <= width) {
01142                 positionNewFloats();
01143                 width = lineWidth(m_height);
01144             }
01145         } else if(o->isPositioned()) {
01146             static_cast<RenderFlow*>(o->containingBlock())->insertSpecialObject(o);
01147         } else if ( o->isText() ) {
01148             RenderText *t = static_cast<RenderText *>(o);
01149             int strlen = t->stringLength();
01150             int len = strlen - pos;
01151             QChar *str = t->text();
01152             if (style()->whiteSpace() == NOWRAP || t->style()->whiteSpace() == NOWRAP) {
01153                 tmpW += t->maxWidth();
01154                 pos = len;
01155                 len = 0;
01156             } else {
01157                 const Font *f = t->htmlFont( firstLine );
01158                 // proportional font, needs a bit more work.
01159                 int lastSpace = pos;
01160                 bool isPre = style()->whiteSpace() == PRE;
01161                 while(len) {
01162                     if( (isPre && str[pos] == '\n') ||
01163                         (!isPre && isBreakable( str, pos, strlen ) ) ) {
01164                     tmpW += t->width(lastSpace, pos - lastSpace, f);
01165 #ifdef DEBUG_LINEBREAKS
01166                     kdDebug(6041) << "found space: '" << QString( str, pos ).latin1() << "' +" << tmpW << " -> w = " << w << endl;
01167 #endif
01168                     if ( !isPre && w + tmpW > width && w == 0 ) {
01169                         int fb = floatBottom();
01170                         int newLineWidth = lineWidth(fb);
01171                         if(!w && m_height < fb && width < newLineWidth) {
01172                             m_height = fb;
01173                             width = newLineWidth;
01174 #ifdef DEBUG_LINEBREAKS
01175                             kdDebug() << "RenderFlow::findNextLineBreak new position at " << m_height << " newWidth " << width << endl;
01176 #endif
01177                         }
01178                     }
01179                     if ( !isPre && w + tmpW > width )
01180                         goto end;
01181 
01182                     lBreak.obj = o;
01183                     lBreak.pos = pos;
01184 
01185                     if( str[pos] == '\n' ) {
01186 #ifdef DEBUG_LINEBREAKS
01187                         kdDebug(6041) << "forced break sol: " << start.obj << " " << start.pos << "   end: " << lBreak.obj << " " << lBreak.pos << "   width=" << w << endl;
01188 #endif
01189                         return lBreak;
01190                     }
01191                     w += tmpW;
01192                     tmpW = 0;
01193                     lastSpace = pos;
01194                 }
01195                 pos++;
01196                 len--;
01197                 }
01198                 // IMPORTANT: pos is > length here!
01199                 tmpW += t->width(lastSpace, pos - lastSpace, f);
01200                 if (!isPre && w + tmpW < width && pos && str[pos-1] != nbsp)
01201                     lBreak =  Bidinext( start.par, o );
01202             }
01203         } else if ( o->isReplaced() ) {
01204             tmpW += o->width()+o->marginLeft()+o->marginRight();
01205 
01206             if ( w + tmpW > width )
01207                 goto end;
01208 
01209             if (o->style()->whiteSpace() != NOWRAP) {
01210                 w += tmpW;
01211                 tmpW = 0;
01212                 lBreak = o;
01213                 lBreak.pos = pos;
01214             }
01215         } else
01216             KHTMLAssert( false );
01217 
01218         if( w + tmpW > width+1 && style()->whiteSpace() == NORMAL /*&& o->style()->whiteSpace() != NOWRAP*/ ) {
01219             //kdDebug() << " too wide w=" << w << " tmpW = " << tmpW << " width = " << width << endl;
01220             //kdDebug() << "start=" << start.obj << " current=" << o << endl;
01221             // if we have floats, try to get below them.
01222             int fb = floatBottom();
01223             int newLineWidth = lineWidth(fb);
01224             if( !w && m_height < fb && width < newLineWidth ) {
01225                 m_height = fb;
01226                 width = newLineWidth;
01227 #ifdef DEBUG_LINEBREAKS
01228                 kdDebug() << "RenderFlow::findNextLineBreak new position at " << m_height << " newWidth " << width << endl;
01229 #endif
01230             }
01231             if( !w && w + tmpW > width+1 && (o != start.obj || (unsigned) pos != start.pos) ) {
01232                 // getting below floats wasn't enough...
01233                 //kdDebug() << "still too wide w=" << w << " tmpW = " << tmpW << " width = " << width << endl;
01234                 lBreak = o;
01235                 if (o == last)
01236                     lBreak.pos = pos;
01237                 if (unsigned ( pos ) >= o->length())
01238                     lBreak = Bidinext(start.par, o);
01239             }
01240             goto end;
01241         }
01242 
01243         last = o;
01244         o = Bidinext( start.par, o );
01245         pos = 0;
01246     }
01247 
01248 #ifdef DEBUG_LINEBREAKS
01249     kdDebug( 6041 ) << "end of par, width = " << width << " linewidth = " << w + tmpW << endl;
01250 #endif
01251     if( w + tmpW <= width )
01252         lBreak = 0;
01253 
01254  end:
01255 
01256     if( lBreak == start && !lBreak.obj->isBR() ) {
01257         // we just add as much as possible
01258         if ( m_pre )
01259             lBreak = pos ? Bidinext(start.par, o) : o;
01260         else {
01261             if( last != o ) {
01262                 // better break between object boundaries than in the middle of a word
01263                 lBreak = o;
01264             } else {
01265                 int w = 0;
01266                 if( lBreak.obj->isText() )
01267                     w += static_cast<RenderText *>(lBreak.obj)->width(lBreak.pos, 1);
01268                 else
01269                     w += lBreak.obj->width();
01270                 while( lBreak.obj && w < width ) {
01271                     ++lBreak;
01272                     if( !lBreak.obj ) break;
01273                     if( lBreak.obj->isText() )
01274                         w += static_cast<RenderText *>(lBreak.obj)->width(lBreak.pos, 1);
01275                     else
01276                         w += lBreak.obj->width();
01277                 }
01278             }
01279         }
01280     }
01281 
01282     // make sure we consume at least one char/object.
01283     if( lBreak == start )
01284         ++lBreak;
01285 
01286 #ifdef DEBUG_LINEBREAKS
01287     kdDebug(6041) << "regular break sol: " << start.obj << " " << start.pos << "   end: " << lBreak.obj << " " << lBreak.pos << "   width=" << w << "/" << width << endl;
01288 #endif
01289     return lBreak;
01290 }
01291 
01292 // For --enable-final
01293 #undef BIDI_DEBUG
01294 #undef DEBUG_LINEBREAKS
01295 #undef DEBUG_LAYOUT
KDE Logo
This file is part of the documentation for kdelibs Version 3.1.5.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Wed Jan 28 13:33:28 2004 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001