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.4.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Sun Feb 27 22:16:31 2005 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001