kspread Library API Documentation

formula.cc

00001 /* This file is part of the KDE project
00002    Copyright (C) 2003,2004 Ariya Hidayat <ariya@kde.org>
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License as published by the Free Software Foundation; either
00007    version 2 of the License.
00008 
00009    This library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Library General Public License for more details.
00013 
00014    You should have received a copy of the GNU Library General Public License
00015    along with this library; see the file COPYING.LIB.  If not, write to
00016    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017    Boston, MA 02111-1307, USA.
00018 */
00019 
00020 #include "formula.h"
00021 
00022 #include "kspread_cell.h"
00023 #include "kspread_sheet.h"
00024 #include "kspread_doc.h"
00025 #include "kspread_util.h"
00026 #include "kspread_value.h"
00027 
00028 #include "valuecalc.h"
00029 #include "valueconverter.h"
00030 #include "valueparser.h"
00031 
00032 #include "functions.h"
00033 
00034 #include <limits.h>
00035 
00036 #include <qregexp.h>
00037 #include <qstring.h>
00038 #include <qvaluevector.h>
00039 #include <qvaluestack.h>
00040 
00041 #include <klocale.h>
00042 
00043 /*
00044   To understand how this formula engine works, please refer to the documentation
00045   in file DESIGN.html.
00046       
00047   Useful references:
00048    - "Principles of Compiler Design", A.V.Aho, J.D.Ullman, Addison Wesley, 1978
00049    - "Writing Interactive Compilers and Interpreters", P.J. Brown,
00050      John Wiley and Sons, 1979.
00051    - "The Theory and Practice of Compiler Writing", J.Tremblay, P.G.Sorenson,
00052      McGraw-Hill, 1985.
00053    - "The Java(TM) Virtual Machine Specification", T.Lindholm, F.Yellin,
00054      Addison-Wesley, 1997.
00055    - "Java Virtual Machine", J.Meyer, T.Downing, O'Reilly, 1997.
00056 
00057  */
00058 
00059 
00060  /*
00061 TODO - features:
00062  - array/list for function arguments
00063  - handle Intersection
00064  - cell reference is made relative (absolute now)
00065  - shared formula (different owner, same data)
00066  - relative internal representation (independent of owner)
00067  - OASIS support
00068 TODO - optimizations:
00069  - handle initial formula marker = (and +)
00070  - reuse constant already in the pool
00071  - reuse references already in the pool
00072  - expression optimization (e.g. 1+2+A1 becomes 3+A1)
00073  */
00074 
00075 namespace KSpread
00076 {
00077 
00078 class Opcode
00079 {
00080 public:
00081 
00082   enum { Nop = 0, Load, Ref, Cell, Range, Function, Add, Sub, Neg, Mul, Div,
00083     Pow, Concat, Not, Equal, Less, Greater };
00084 
00085   unsigned type;
00086   unsigned index;
00087 
00088   Opcode(): type(Nop), index(0) {};
00089   Opcode( unsigned t ): type(t), index(0) {};
00090   Opcode( unsigned t, unsigned i ): type(t), index(i) {};
00091 };
00092 
00093 class Formula::Private
00094 {
00095 public:
00096   Formula *formula;
00097   KSpreadCell *cell;
00098   bool dirty;
00099   bool valid;
00100   QString expression;
00101   QValueVector<Opcode> codes;
00102   QValueVector<KSpreadValue> constants;
00103 };
00104 
00105 class TokenStack : public QValueVector<Token>
00106 {
00107 public:
00108   TokenStack();
00109   bool isEmpty() const;
00110   unsigned itemCount() const;
00111   void push( const Token& token );
00112   Token pop();
00113   const Token& top();
00114   const Token& top( unsigned index );
00115 private:
00116   void ensureSpace();
00117   unsigned topIndex;
00118 };
00119 
00120 }
00121 
00122 using namespace KSpread;
00123 
00124 // for null token
00125 const Token Token::null;
00126 
00127 // helper function: return operator of given token text
00128 // e.g. "*" yields Operator::Asterisk, and so on
00129 static Token::Op matchOperator( const QString& text )
00130 {
00131   Token::Op result = Token::InvalidOp;
00132 
00133   if( text.length() == 1 )
00134   {
00135     QChar p = text[0];
00136     switch( p.unicode() )
00137     {
00138         case '+': result = Token::Plus; break;
00139         case '-': result = Token::Minus; break;
00140         case '*': result = Token::Asterisk; break;
00141         case '/': result = Token::Slash; break;
00142         case '^': result = Token::Caret; break;
00143         case ',': result = Token::Comma; break;
00144         case ';': result = Token::Semicolon; break;
00145         case '(': result = Token::LeftPar; break;
00146         case ')': result = Token::RightPar; break;
00147         case '&': result = Token::Ampersand; break;
00148         case '=': result = Token::Equal; break;
00149         case '<': result = Token::Less; break;
00150         case '>': result = Token::Greater; break;
00151         case '%': result = Token::Percent; break;
00152         default : result = Token::InvalidOp; break;
00153     }
00154   }
00155 
00156   if( text.length() == 2 )
00157   {
00158     if( text == "<>" ) result = Token::NotEqual;
00159     if( text == "<=" ) result = Token::LessEqual;
00160     if( text == ">=" ) result = Token::GreaterEqual;
00161 
00162     // This is for old KScript backward compatibility
00163     // Remove in KOffice 2.0
00164     if( text == "==" ) result = Token::Equal;
00165   }
00166 
00167   return result;
00168 }
00169 
00170 // helper function: give operator precedence
00171 // e.g. "+" is 1 while "*" is 3
00172 static int opPrecedence( Token::Op op )
00173 {
00174   int prec = -1;
00175   switch( op )
00176   {
00177     case Token::Percent      : prec = 8; break;
00178     case Token::Caret        : prec = 7; break;
00179     case Token::Asterisk     : prec = 5; break;
00180     case Token::Slash        : prec = 6; break;
00181     case Token::Plus         : prec = 3; break;
00182     case Token::Minus        : prec = 3; break;
00183     case Token::Ampersand    : prec = 2; break;
00184     case Token::Equal        : prec = 1; break;
00185     case Token::NotEqual     : prec = 1; break;
00186     case Token::Less         : prec = 1; break;
00187     case Token::Greater      : prec = 1; break;
00188     case Token::LessEqual    : prec = 1; break;
00189     case Token::GreaterEqual : prec = 1; break;
00190     case Token::Semicolon    : prec = 0; break;
00191     case Token::RightPar     : prec = 0; break;
00192     case Token::LeftPar      : prec = -1; break;
00193     default: prec = -1; break;
00194   }
00195   return prec;
00196 }
00197 
00198 // helper function
00199 static KSpreadValue tokenAsValue( const Token& token )
00200 {
00201   KSpreadValue value;
00202   if( token.isBoolean() ) value = KSpreadValue( token.asBoolean() );
00203   else if( token.isInteger() ) value = KSpreadValue( token.asInteger() );
00204   else if( token.isFloat() ) value = KSpreadValue( token.asFloat() );
00205   else if( token.isString() ) value = KSpreadValue( token.asString() );
00206   return value;
00207 }
00208 
00209 /**********************
00210     Token
00211  **********************/
00212 
00213 // creates a token
00214 Token::Token( Type type, const QString& text, int pos )
00215 {
00216   m_type = type;
00217   m_text = text;
00218   m_pos = pos;
00219 }
00220 
00221 // copy constructor
00222 Token::Token( const Token& token )
00223 {
00224   m_type = token.m_type;
00225   m_text = token.m_text;
00226   m_pos = token.m_pos;
00227 }
00228 
00229 // assignment operator
00230 Token& Token::operator=( const Token& token )
00231 {
00232   m_type = token.m_type;
00233   m_text = token.m_text;
00234   m_pos = token.m_pos;
00235   return *this;
00236 }
00237 
00238 bool Token::asBoolean() const
00239 {
00240   if( !isBoolean() ) return false;
00241   return m_text.lower() == "true";
00242   // FIXME check also for i18n version
00243 }
00244 
00245 int Token::asInteger() const
00246 {
00247   if( isInteger() ) return m_text.toInt();
00248   else return 0;
00249 }
00250 
00251 double Token::asFloat() const
00252 {
00253   if( isFloat() ) return m_text.toDouble();
00254   else return 0.0;
00255 }
00256 
00257 QString Token::asString() const
00258 {
00259   if( isString() ) return m_text.mid( 1, m_text.length()-2 );
00260   else return QString::null;
00261 }
00262 
00263 Token::Op Token::asOperator() const
00264 {
00265   if( isOperator() ) return matchOperator( m_text );
00266   else return InvalidOp;
00267 }
00268 
00269 QString Token::sheetName() const
00270 {
00271   if( !isCell() && !isRange() ) return QString::null;
00272   int i = m_text.find( '!' );
00273   if( i < 0 ) return QString();
00274   QString sheet = m_text.left( i );
00275   if( sheet[0] == QChar(39) )
00276     sheet = sheet.mid( 1, sheet.length()-2 );
00277   return sheet;
00278 }
00279 
00280 QString Token::description() const
00281 {
00282   QString desc;
00283 
00284   switch (m_type )
00285   {
00286     case  Boolean:    desc = "Boolean"; break;
00287     case  Integer:    desc = "Integer"; break;
00288     case  Float:      desc = "Float"; break;
00289     case  String:     desc = "String"; break;
00290     case  Identifier: desc = "Identifier"; break;
00291     case  Cell:       desc = "Cell"; break;
00292     case  Range:      desc = "Range"; break;
00293     case  Operator:   desc = "Operator"; break;
00294     default:          desc = "Unknown"; break;
00295   }
00296 
00297   while( desc.length() < 10 ) desc.prepend( ' ' );
00298   desc.prepend( "  " );
00299   desc.prepend( QString::number( m_pos ) );
00300   desc.append( " : " ).append( m_text );
00301 
00302   return desc;
00303 }
00304 
00305 
00306 /**********************
00307     TokenStack
00308  **********************/
00309 
00310 TokenStack::TokenStack(): QValueVector<Token>()
00311 {
00312   topIndex = 0;
00313   ensureSpace();
00314 }
00315 
00316 bool TokenStack::isEmpty() const
00317 {
00318   return topIndex == 0;
00319 }
00320 
00321 unsigned TokenStack::itemCount() const
00322 {
00323   return topIndex;
00324 }
00325 
00326 void TokenStack::push( const Token& token )
00327 {
00328   ensureSpace();
00329   at( topIndex++ ) = token;
00330 }
00331 
00332 Token TokenStack::pop()
00333 {
00334   return (topIndex > 0 ) ? Token( at( --topIndex ) ) : Token();
00335 }
00336 
00337 const Token& TokenStack::top()
00338 {
00339   return top( 0 );
00340 }
00341 
00342 const Token& TokenStack::top( unsigned index )
00343 {
00344   if( topIndex > index )
00345     return at( topIndex-index-1 );
00346   return Token::null;
00347 }
00348 
00349 void TokenStack::ensureSpace()
00350 {
00351   while( topIndex >= size() )
00352     resize( size() + 10 );
00353 }
00354 
00355 /**********************
00356     FormulaPrivate
00357  **********************/
00358 
00359 // helper function: return true for valid identifier character
00360 static bool isIdentifier( QChar ch )
00361 {
00362   return ( ch.unicode() == '_' ) || (ch.unicode() == '$' ) || ( ch.isLetter() );
00363 }
00364 
00365 
00366 
00367 
00368 /**********************
00369     Formula
00370  **********************/
00371 
00372 // Constructor
00373 
00374 Formula::Formula( KSpreadCell *cell )
00375 {
00376   d = new Private;
00377   d->cell = cell;
00378   clear();
00379 }
00380 
00381 Formula::Formula()
00382 {
00383   d = new Private;
00384   d->cell = 0;
00385   clear();
00386 }
00387 
00388 // Destructor
00389 
00390 Formula::~Formula()
00391 {
00392   delete d;
00393 }
00394 
00395 KSpreadCell* Formula::cell()
00396 {
00397   return d->cell;
00398 }  
00399 
00400 // Sets a new expression for this formula.
00401 // note that both the real lex and parse processes will happen later on
00402 // when needed (i.e. "lazy parse"), for example during formula evaluation.
00403 
00404 void Formula::setExpression( const QString& expr )
00405 {
00406   d->expression = expr;
00407   d->dirty = true;
00408   d->valid = false;
00409 }
00410 
00411 // Returns the expression associated with this formula.
00412 
00413 QString Formula::expression() const
00414 {
00415   return d->expression;
00416 }
00417 
00418 // Returns the validity of the formula.
00419 // note: empty formula is always invalid.
00420 
00421 bool Formula::isValid() const
00422 {
00423   if( d->dirty )
00424   {
00425     KLocale* locale = d->cell ? d->cell->locale() : 0;
00426     Tokens tokens = scan( d->expression, locale );
00427     if( tokens.valid() )
00428       compile( tokens );
00429     else
00430       d->valid = false;
00431   }
00432   return d->valid;
00433 }
00434 
00435 // Clears everything, also mark the formula as invalid.
00436 
00437 void Formula::clear()
00438 {
00439   d->expression = QString::null;
00440   d->dirty = true;
00441   d->valid = false;
00442   d->constants.clear();
00443   d->codes.clear();
00444 }
00445 
00446 // Returns list of token for the expression.
00447 // this triggers again the lexical analysis step. it is however preferable
00448 // (even when there's small performance penalty) because otherwise we need to
00449 // store parsed tokens all the time which serves no good purpose.
00450 
00451 Tokens Formula::tokens() const
00452 {
00453   KLocale* locale = d->cell ? d->cell->locale() : 0;
00454   return scan( d->expression, locale );
00455 }
00456 
00457 Tokens Formula::scan( const QString& expr, KLocale* locale )
00458 {
00459   // to hold the result
00460   Tokens tokens;
00461 
00462   // parsing state
00463   enum { Start, Finish, Bad, InNumber, InDecimal, InExpIndicator, InExponent,
00464     InString, InIdentifier, InCell, InRange, InSheetName } state;
00465 
00466   // use locale settings if specified
00467   QString thousand = locale ? locale->thousandsSeparator() : "";
00468   QString decimal = locale ? locale->decimalSymbol() : ".";
00469 
00470   // initialize variables
00471   state = Start;
00472   unsigned int i = 0;
00473   QString ex = expr;
00474   QString tokenText;
00475   int tokenStart = 0;
00476   
00477   // first character must be equal sign (=)
00478   if( ex[0] != '=' )
00479     return tokens;
00480 
00481   // but the scanner should not see this equal sign
00482   ex.remove( 0, 1 );  
00483     
00484   // force a terminator
00485   ex.append( QChar() );
00486 
00487   // main loop
00488   while( (state != Bad) && (state != Finish) && (i < ex.length()) )
00489   {
00490     QChar ch = ex[i];
00491 
00492     switch( state )
00493     {
00494 
00495     case Start:
00496 
00497        tokenStart = i;
00498 
00499        // skip any whitespaces
00500        if( ch.isSpace() ) i++;
00501 
00502        // check for number
00503        else if( ch.isDigit() )
00504        {
00505          state = InNumber;
00506        }
00507 
00508        // a string ?
00509        else if ( ch == '"' )
00510        {
00511          tokenText.append( ex[i++] );
00512          state = InString;
00513        }
00514 
00515        // beginning with alphanumeric ?
00516        // could be identifier, cell, range, or function...
00517        else if( isIdentifier( ch ) )
00518        {
00519          state = InIdentifier;
00520        }
00521 
00522        // aposthrophe (') marks sheet name for 3-d cell, e.g 'Sales Q3'!A4
00523        else if ( ch.unicode() == 39 )
00524        {
00525          i++;
00526          state = InSheetName;
00527          tokenText.append( QChar( 39 ) );
00528        }
00529 
00530        // decimal dot ?
00531        else if ( ch == decimal )
00532        {
00533          tokenText.append( ex[i++] );
00534          state = InDecimal;
00535        }
00536 
00537        // terminator character
00538        else if ( ch == QChar::null )
00539           state = Finish;
00540 
00541        // look for operator match
00542        else
00543        {
00544          int op;
00545          QString s;
00546 
00547          // check for two-chars operator, such as '<=', '>=', etc
00548          s.append( ch ).append( ex[i+1] );
00549          op = matchOperator( s );
00550 
00551          // check for one-char operator, such as '+', ';', etc
00552          if( op == Token::InvalidOp )
00553          {
00554            s = QString( ch );
00555            op = matchOperator( s );
00556          }
00557 
00558          // any matched operator ?
00559          if( op != Token::InvalidOp )
00560          {
00561            int len = s.length();
00562            i += len;
00563            tokens.append( Token( Token::Operator, s.left( len ), tokenStart ) );
00564          }
00565          else state = Bad;
00566         }
00567        break;
00568 
00569     case InIdentifier:
00570 
00571        // consume as long as alpha, dollar sign, underscore, or digit
00572        if( isIdentifier( ch )  || ch.isDigit() ) tokenText.append( ex[i++] );
00573 
00574        // a '!' ? then this must be sheet name, e.g "Sheet4!"
00575        else if( ch == '!' )
00576        {
00577           tokenText.append( ex[i++] );
00578           state = InCell;
00579        }
00580 
00581        // we're done with identifier
00582        else
00583        {
00584          // check for "true" or "false"
00585          if( ( tokenText.lower() == "true" ) || ( tokenText.lower() == "false" ) )
00586          {
00587            tokens.append( Token( Token::Boolean, tokenText, tokenStart ) );
00588            tokenStart = i;
00589            tokenText = "";
00590            state = Start;
00591          }
00592 
00593          else
00594          {
00595            // check for cell reference,  e.g A1, VV123, ...
00596            QRegExp exp("(\\$?)([a-zA-Z]+)(\\$?)([0-9]+)$");
00597            int n = exp.search( tokenText );
00598            if( n >= 0 )
00599              state = InCell;
00600            else
00601            {
00602              tokens.append( Token( Token::Identifier, tokenText, tokenStart ) );
00603              tokenStart = i;
00604              tokenText = "";
00605              state = Start;
00606            }
00607           }
00608        }
00609        break;
00610 
00611     case InCell:
00612 
00613        // consume as long as alpha, dollar sign, underscore, or digit
00614        if( isIdentifier( ch )  || ch.isDigit() ) tokenText.append( ex[i++] );
00615 
00616        // we're done with cell ref, possibly with sheet name (like "Sheet2!B2")
00617        // note that "Sheet2!TotalSales" is also possible, in which "TotalSales" is a named area
00618        else
00619        {
00620 
00621          // check if it's a cell ref like A32, not named area
00622          QString cell;
00623          for( int j = tokenText.length()-1; j>=0; j-- )
00624            if( tokenText[j] == '!' )
00625                break;
00626            else
00627                cell.prepend( tokenText[j] );
00628          QRegExp exp("(\\$?)([a-zA-Z]+)(\\$?)([0-9]+)$");
00629          if( exp.search( cell ) != 0 )
00630          {
00631 
00632            // we're done with named area
00633            tokens.append( Token( Token::Range, tokenText, tokenStart ) );
00634            tokenText = "";
00635            state = Start;
00636          }
00637 
00638          else
00639          {
00640 
00641            // so up to now we've got something like A2 or Sheet2!F4
00642            // check for range reference
00643            if( ch == ':' )
00644            {
00645              tokenText.append( ex[i++] );
00646              state = InRange;
00647            }
00648            else
00649            {
00650              // we're done with cell reference
00651              tokens.append( Token( Token::Cell, tokenText, tokenStart ) );
00652              tokenText = "";
00653              state = Start;
00654            }
00655          }
00656        }
00657        break;
00658 
00659     case InRange:
00660 
00661        // consume as long as alpha, dollar sign, underscore, or digit
00662        if( isIdentifier( ch )  || ch.isDigit() ) tokenText.append( ex[i++] );
00663 
00664        // we're done with range reference
00665        else
00666        {
00667          tokens.append( Token( Token::Range, tokenText, tokenStart ) );
00668          tokenText = "";
00669          state = Start;
00670        }
00671        break;
00672 
00673     case InSheetName:
00674 
00675        // consume until '
00676        if( ch.unicode() != 39 ) tokenText.append( ex[i++] );
00677 
00678        else
00679        {
00680          // must be followed by '!'
00681          i++;
00682          if( ex[i] == '!' )
00683          {
00684            tokenText.append( ex[i++] );
00685            state = InCell;
00686          }
00687          else state = Bad;
00688        }
00689        break;
00690 
00691     case InNumber:
00692 
00693        // consume as long as it's digit
00694        if( ch.isDigit() ) tokenText.append( ex[i++] );
00695 
00696        // skip thousand separator
00697        else if( !thousand.isEmpty() && ( ch ==thousand[0] ) ) i++;
00698 
00699        // convert decimal separator to '.', also support '.' directly
00700        // we always support '.' because of bug #98455
00701        else if(( !decimal.isEmpty() && ( ch == decimal[0] ) ) || (ch == '.'))
00702        {
00703          tokenText.append( '.' );
00704          i++;
00705          state = InDecimal;
00706        }
00707 
00708        // exponent ?
00709        else if( ch.upper() == 'E' )
00710        {
00711          tokenText.append( 'E' );
00712          i++;
00713          state = InExpIndicator;
00714        }
00715 
00716        // we're done with integer number
00717        else
00718        {
00719          tokens.append( Token( Token::Integer, tokenText, tokenStart ) );
00720          tokenText = "";
00721          state = Start;
00722        };
00723        break;
00724 
00725     case InDecimal:
00726 
00727        // consume as long as it's digit
00728        if( ch.isDigit() ) tokenText.append( ex[i++] );
00729 
00730        // exponent ?
00731        else if( ch.upper() == 'E' )
00732        {
00733          tokenText.append( 'E' );
00734          i++;
00735          state = InExpIndicator;
00736        }
00737 
00738        // we're done with floating-point number
00739        else
00740        {
00741          tokens.append( Token( Token::Float, tokenText, tokenStart ) );
00742          tokenText = "";
00743          state = Start;
00744        };
00745        break;
00746 
00747     case InExpIndicator:
00748 
00749        // possible + or - right after E, e.g 1.23E+12 or 4.67E-8
00750        if( ( ch == '+' ) || ( ch == '-' ) ) tokenText.append( ex[i++] );
00751 
00752        // consume as long as it's digit
00753        else if( ch.isDigit() ) state = InExponent;
00754 
00755        // invalid thing here
00756        else state = Bad;
00757 
00758        break;
00759 
00760     case InExponent:
00761 
00762        // consume as long as it's digit
00763        if( ch.isDigit() ) tokenText.append( ex[i++] );
00764 
00765        // we're done with floating-point number
00766        else
00767        {
00768          tokens.append( Token( Token::Float, tokenText, tokenStart ) );
00769          tokenText = "";
00770          state = Start;
00771        };
00772        break;
00773 
00774     case InString:
00775 
00776        // consume until "'
00777        if( ch != '"' ) tokenText.append( ex[i++] );
00778 
00779        else
00780        {
00781          tokenText.append( ch ); i++;
00782          tokens.append( Token( Token::String, tokenText, tokenStart ) );
00783          tokenText = "";
00784          state = Start;
00785        }
00786        break;
00787 
00788     case Bad:
00789     default:
00790        break;
00791     };
00792   };
00793   
00794   if( state == Bad ) 
00795     tokens.setValid( false );
00796 
00797   return tokens;
00798 }
00799 
00800 // will affect: dirty, valid, codes, constants
00801 void Formula::compile( const Tokens& tokens ) const
00802 {
00803   // initialize variables
00804   d->dirty = false;
00805   d->valid = false;
00806   d->codes.clear();
00807   d->constants.clear();
00808 
00809   // sanity check
00810   if( tokens.count() == 0 ) return;
00811 
00812   TokenStack syntaxStack;
00813   QValueStack<int> argStack;
00814   unsigned argCount = 1;
00815 
00816   for( unsigned i = 0; i <= tokens.count(); i++ )
00817   {
00818     // helper token: InvalidOp is end-of-formula
00819     Token token =  ( i < tokens.count() ) ? tokens[i] : Token( Token::Operator );
00820     Token::Type tokenType = token.type();
00821 
00822     // unknown token is invalid
00823     if( tokenType == Token::Unknown ) break;
00824 
00825     // for constants, push immediately to stack
00826     // generate code to load from a constant
00827     if ( ( tokenType == Token::Integer ) || ( tokenType == Token::Float ) ||
00828     ( tokenType == Token::String ) || ( tokenType == Token::Boolean ) )
00829     {
00830       syntaxStack.push( token );
00831       d->constants.append( tokenAsValue( token ) );
00832       d->codes.append( Opcode( Opcode::Load, d->constants.count()-1 ) );
00833     }
00834 
00835     // for cell, range, or identifier, push immediately to stack
00836     // generate code to load from reference
00837     if( ( tokenType == Token::Cell ) || ( tokenType == Token::Range ) ||
00838     ( tokenType == Token::Identifier ) )
00839     {
00840       syntaxStack.push( token );
00841       d->constants.append( KSpreadValue( token.text() ) );
00842       if (tokenType == Token::Cell)
00843         d->codes.append( Opcode( Opcode::Cell, d->constants.count()-1 ) );
00844       else if (tokenType == Token::Range)
00845         d->codes.append( Opcode( Opcode::Range, d->constants.count()-1 ) );
00846       else
00847         d->codes.append( Opcode( Opcode::Ref, d->constants.count()-1 ) );
00848     }
00849 
00850     // are we entering a function ?
00851     // if token is operator, and stack already has: id ( arg
00852     if( tokenType == Token::Operator )
00853     if( syntaxStack.itemCount() >= 3 )
00854     {
00855         Token arg = syntaxStack.top();
00856         Token par = syntaxStack.top( 1 );
00857         Token id = syntaxStack.top( 2 );
00858         if( !arg.isOperator() )
00859         if( par.asOperator() == Token::LeftPar )
00860         if( id.isIdentifier() )
00861         {
00862           argStack.push( argCount );
00863           argCount = 1;
00864         }
00865      }
00866 
00867      // special case for percentage
00868     if( tokenType == Token::Operator )
00869     if( token.asOperator() == Token::Percent )
00870     if( syntaxStack.itemCount() >= 1 )
00871     if( !syntaxStack.top().isOperator() )
00872     {
00873       d->constants.append( KSpreadValue( 0.01 ) );
00874       d->codes.append( Opcode( Opcode::Load, d->constants.count()-1 ) );
00875       d->codes.append( Opcode( Opcode::Mul ) );
00876     }
00877 
00878     // for any other operator, try to apply all parsing rules
00879     if( tokenType == Token::Operator )
00880     if( token.asOperator() != Token::Percent )
00881     {
00882       // repeat until no more rule applies
00883       for( ; ; )
00884       {
00885         bool ruleFound = false;
00886 
00887         // rule for function arguments, if token is ; or )
00888         // id ( arg1 ; arg2 -> id ( arg
00889         if( !ruleFound )
00890         if( syntaxStack.itemCount() >= 5 )
00891         if( ( token.asOperator() == Token::RightPar ) ||
00892         ( token.asOperator() == Token::Semicolon ) )
00893         {
00894           Token arg2 = syntaxStack.top();
00895           Token sep = syntaxStack.top( 1 );
00896           Token arg1 = syntaxStack.top( 2 );
00897           Token par = syntaxStack.top( 3 );
00898           Token id = syntaxStack.top( 4 );
00899           if( !arg2.isOperator() )
00900           if( sep.asOperator() == Token::Semicolon )
00901           if( !arg1.isOperator() )
00902           if( par.asOperator() == Token::LeftPar )
00903           if( id.isIdentifier() )
00904           {
00905             ruleFound = true;
00906             syntaxStack.pop();
00907             syntaxStack.pop();
00908             argCount++;
00909           }
00910         }
00911 
00912         // rule for function last argument:
00913         //  id ( arg ) -> arg
00914         if( !ruleFound )
00915         if( syntaxStack.itemCount() >= 4 )
00916         {
00917           Token par2 = syntaxStack.top();
00918           Token arg = syntaxStack.top( 1 );
00919           Token par1 = syntaxStack.top( 2 );
00920           Token id = syntaxStack.top( 3 );
00921           if( par2.asOperator() == Token::RightPar )
00922           if( !arg.isOperator() )
00923           if( par1.asOperator() == Token::LeftPar )
00924           if( id.isIdentifier() )
00925           {
00926             ruleFound = true;
00927             syntaxStack.pop();
00928             syntaxStack.pop();
00929             syntaxStack.pop();
00930             syntaxStack.pop();
00931             syntaxStack.push( arg );
00932             d->codes.append( Opcode( Opcode::Function, argCount ) );
00933             argCount = argStack.empty() ? 0 : argStack.pop();
00934           }
00935         }
00936 
00937         // rule for function call with parentheses, but without argument
00938         // e.g. "2*PI()"
00939         if( !ruleFound )
00940         if( syntaxStack.itemCount() >= 3 )
00941         {
00942           Token par2 = syntaxStack.top();
00943           Token par1 = syntaxStack.top( 1 );
00944           Token id = syntaxStack.top( 2 );
00945           if( par2.asOperator() == Token::RightPar )
00946           if( par1.asOperator() == Token::LeftPar )
00947           if( id.isIdentifier() )
00948           {
00949             ruleFound = true;
00950             syntaxStack.pop();
00951             syntaxStack.pop();
00952             syntaxStack.pop();
00953             syntaxStack.push( Token( Token::Integer ) );
00954             d->codes.append( Opcode( Opcode::Function, 0 ) );
00955           }
00956         }
00957 
00958         // rule for parenthesis:  ( Y ) -> Y
00959         if( !ruleFound )
00960         if( syntaxStack.itemCount() >= 3 )
00961         {
00962           Token right = syntaxStack.top();
00963           Token y = syntaxStack.top( 1 );
00964           Token left = syntaxStack.top( 2 );
00965           if( right.isOperator() )
00966           if( !y.isOperator() )
00967           if( left.isOperator() )
00968           if( right.asOperator() == Token::RightPar )
00969           if( left.asOperator() == Token::LeftPar )
00970           {
00971             ruleFound = true;
00972             syntaxStack.pop();
00973             syntaxStack.pop();
00974             syntaxStack.pop();
00975             syntaxStack.push( y );
00976           }
00977         }
00978 
00979         // rule for binary operator:  A (op) B -> A
00980         // conditions: precedence of op >= precedence of token
00981         // action: push (op) to result
00982         // e.g. "A * B" becomes "A" if token is operator "+"
00983         // exception: for caret (power operator), if op is another caret
00984         // then the rule doesn't apply, e.g. "2^3^2" is evaluated as "2^(3^2)"
00985         if( !ruleFound )
00986         if( syntaxStack.itemCount() >= 3 )
00987         {
00988           Token b = syntaxStack.top();
00989           Token op = syntaxStack.top( 1 );
00990           Token a = syntaxStack.top( 2 );
00991           if( !a.isOperator() )
00992           if( !b.isOperator() )
00993           if( op.isOperator() )
00994           if( token.asOperator() != Token::LeftPar )
00995           if( token.asOperator() != Token::Caret )
00996           if( opPrecedence( op.asOperator() ) >= opPrecedence( token.asOperator() ) )
00997           {
00998             ruleFound = true;
00999             syntaxStack.pop();
01000             syntaxStack.pop();
01001             syntaxStack.pop();
01002             syntaxStack.push( b );
01003             switch( op.asOperator() )
01004             {
01005               // simple binary operations
01006               case Token::Plus:         d->codes.append( Opcode::Add ); break;
01007               case Token::Minus:        d->codes.append( Opcode::Sub ); break;
01008               case Token::Asterisk:     d->codes.append( Opcode::Mul ); break;
01009               case Token::Slash:        d->codes.append( Opcode::Div ); break;
01010               case Token::Caret:        d->codes.append( Opcode::Pow ); break;
01011               case Token::Ampersand:    d->codes.append( Opcode::Concat ); break;
01012 
01013               // simple value comparisons
01014               case Token::Equal:        d->codes.append( Opcode::Equal ); break;
01015               case Token::Less:         d->codes.append( Opcode::Less ); break;
01016               case Token::Greater:      d->codes.append( Opcode::Greater ); break;
01017 
01018               // NotEqual is Equal, followed by Not
01019               case Token::NotEqual:
01020                 d->codes.append( Opcode::Equal );
01021                 d->codes.append( Opcode::Not );
01022                 break;
01023 
01024               // LessOrEqual is Greater, followed by Not
01025               case Token::LessEqual:
01026                 d->codes.append( Opcode::Greater );
01027                 d->codes.append( Opcode::Not );
01028                 break;
01029 
01030               // GreaterOrEqual is Less, followed by Not
01031               case Token::GreaterEqual:
01032                 d->codes.append( Opcode::Less );
01033                 d->codes.append( Opcode::Not );
01034                 break;
01035               default: break;
01036             };
01037           }
01038          }
01039 
01040          // rule for unary operator:  (op1) (op2) X -> (op1) X
01041          // conditions: op2 is unary
01042          // action: push (op2) to result
01043          // e.g.  "* - 2" becomes "*"
01044          if( !ruleFound )
01045          if( syntaxStack.itemCount() >= 3 )
01046          {
01047             Token x = syntaxStack.top();
01048             Token op2 = syntaxStack.top( 1 );
01049             Token op1 = syntaxStack.top( 2 );
01050             if( !x.isOperator() )
01051             if( op1.isOperator() )
01052             if( op2.isOperator() )
01053             if( ( op2.asOperator() == Token::Plus ) ||
01054                ( op2.asOperator() == Token::Minus ) )
01055             {
01056               ruleFound = true;
01057               syntaxStack.pop();
01058               syntaxStack.pop();
01059               syntaxStack.push( x );
01060               if( op2.asOperator() == Token::Minus )
01061                 d->codes.append( Opcode( Opcode::Neg ) );
01062             }
01063           }
01064 
01065          // auxilary rule for unary operator:  (op) X -> X
01066          // conditions: op is unary, op is first in syntax stack
01067          // action: push (op) to result
01068          if( !ruleFound )
01069          if( syntaxStack.itemCount() == 2 )
01070          {
01071             Token x = syntaxStack.top();
01072             Token op = syntaxStack.top( 1 );
01073             if( !x.isOperator() )
01074             if( op.isOperator() )
01075             if( ( op.asOperator() == Token::Plus ) ||
01076                ( op.asOperator() == Token::Minus ) )
01077             {
01078               ruleFound = true;
01079               syntaxStack.pop();
01080               syntaxStack.pop();
01081               syntaxStack.push( x );
01082               if( op.asOperator() == Token::Minus )
01083                 d->codes.append( Opcode( Opcode::Neg ) );
01084             }
01085           }
01086 
01087         if( !ruleFound ) break;
01088       }
01089 
01090       // can't apply rules anymore, push the token
01091       if( token.asOperator() != Token::Percent )
01092         syntaxStack.push( token );
01093     }
01094   }
01095 
01096   // syntaxStack must left only one operand and end-of-formula (i.e. InvalidOp)
01097   d->valid = false;
01098   if( syntaxStack.itemCount() == 2 )
01099   if( syntaxStack.top().isOperator() )
01100   if( syntaxStack.top().asOperator() == Token::InvalidOp )
01101   if( !syntaxStack.top(1).isOperator() )
01102     d->valid = true;
01103 
01104   // bad parsing ? clean-up everything
01105   if( !d->valid )
01106   {
01107     d->constants.clear();
01108     d->codes.clear();
01109   }
01110 }
01111 
01112 
01113 // Evaluates the formula, returns the result.
01114 
01115 KSpreadValue Formula::eval() const
01116 {
01117   QValueStack<KSpreadValue> stack;
01118   unsigned index;
01119   KSpreadValue val1, val2;
01120   QString c;
01121   QValueVector<KSpreadValue> args;
01122 
01123   KSpreadSheet *sheet = 0;
01124   ValueParser* parser = 0;
01125   ValueConverter* converter = 0;
01126   ValueCalc* calc = 0;
01127   
01128   if( d->cell )
01129   {
01130     sheet = d->cell->sheet();
01131     converter = sheet->doc()->converter();
01132     calc = sheet->doc()->calc();
01133   }
01134   else
01135   {
01136     parser = new ValueParser( KGlobal::locale() );
01137     converter = new ValueConverter( parser );
01138     calc = new ValueCalc( converter );
01139   }
01140   
01141 
01142   Function* function;
01143   
01144   if( d->dirty )
01145   {
01146     Tokens tokens = scan( d->expression );
01147     d->valid = tokens.valid();
01148     if( tokens.valid() )
01149       compile( tokens );
01150   }
01151   
01152   if( !d->valid )
01153     return KSpreadValue::errorVALUE();
01154 
01155   for( unsigned pc = 0; pc < d->codes.count(); pc++ )
01156   {
01157     Opcode& opcode = d->codes[pc];
01158     index = opcode.index;
01159     switch( opcode.type )
01160     {
01161       // no operation
01162       case Opcode::Nop:
01163         break;
01164 
01165       // load a constant, push to stack
01166       case Opcode::Load:
01167         val1 = d->constants[index];
01168         stack.push( val1 );
01169         break;
01170 
01171       // unary operation
01172       case Opcode::Neg:
01173         val1 = converter->asFloat (stack.pop());
01174         if( val1.isError() ) return KSpreadValue::errorVALUE();
01175         stack.push( -val1.asFloat() );
01176         break;
01177 
01178       // binary operation: take two values from stack, do the operation,
01179       // push the result to stack
01180       case Opcode::Add:
01181         val2 = stack.pop();
01182         val1 = stack.pop();
01183         val2 = calc->add( val1, val2 );
01184         if( val2.isError() ) return val2;
01185         stack.push( val2 );
01186         break;
01187 
01188       case Opcode::Sub:
01189         val2 = stack.pop();
01190         val1 = stack.pop();
01191         val2 = calc->sub( val1, val2 );
01192         if( val2.isError() ) return val2;
01193         stack.push( val2 );
01194         break;
01195 
01196       case Opcode::Mul:
01197         val2 = stack.pop();
01198         val1 = stack.pop();
01199         val2 = calc->mul( val1, val2 );
01200         if( val2.isError() ) return val2;
01201         stack.push( val2 );
01202         break;
01203 
01204       case Opcode::Div:
01205         val2 = stack.pop();
01206         val1 = stack.pop();
01207         if( val1.isZero() ) return KSpreadValue::errorDIV0();
01208         val2 = calc->div( val1, val2 );
01209         if( val2.isError() ) return val2;
01210         stack.push( val2 );
01211         break;
01212 
01213       case Opcode::Pow:
01214         val2 = stack.pop();
01215         val1 = stack.pop();
01216         val2 = calc->pow( val1, val2 );
01217         if( val2.isError() ) return val2;
01218         stack.push( val2 );
01219         break;
01220 
01221       // string concatenation
01222       case Opcode::Concat:
01223         val1 = converter->asString( stack.pop());
01224         if( val1.isError() ) return KSpreadValue::errorVALUE();
01225         val2 = converter->asString( stack.pop());
01226         if( val2.isError() ) return KSpreadValue::errorVALUE();
01227         val1.setValue( val2.asString().append( val1.asString() ) );
01228         stack.push( val1 );
01229         break;
01230 
01231       // logical not
01232       case Opcode::Not:
01233         val1 = converter->asBoolean( stack.pop());
01234         if( val1.isError() ) return KSpreadValue::errorVALUE();
01235         val1.setValue( !val1.asBoolean() );
01236         stack.push( val1 );
01237         break;
01238 
01239       // comparison
01240       case Opcode::Equal:
01241         val1 = stack.pop();
01242         if( val1.isError() ) return KSpreadValue::errorVALUE();
01243         val2 = stack.pop();
01244         if( val2.isError() ) return KSpreadValue::errorVALUE();
01245         if( !val1.allowComparison( val2 ) )
01246           return KSpreadValue::errorVALUE();
01247         if( val2.compare( val1 ) == 0 )
01248           stack.push( KSpreadValue( true ) );
01249         else
01250           stack.push( KSpreadValue( false ) );
01251         break;
01252 
01253       // less than
01254       case Opcode::Less:
01255         val1 = stack.pop();
01256         if( val1.isError() ) return KSpreadValue::errorVALUE();
01257         val2 = stack.pop();
01258         if( val2.isError() ) return KSpreadValue::errorVALUE();
01259         if( !val1.allowComparison( val2 ) )
01260           return KSpreadValue::errorVALUE();
01261         if( val2.compare( val1 ) < 0 )
01262           stack.push( KSpreadValue( true ) );
01263         else
01264           stack.push( KSpreadValue( false ) );
01265         break;
01266 
01267       // greater than
01268       case Opcode::Greater:
01269         val1 = stack.pop();
01270         if( val1.isError() ) return KSpreadValue::errorVALUE();
01271         val2 = stack.pop();
01272         if( val2.isError() ) return KSpreadValue::errorVALUE();
01273         if( !val1.allowComparison( val2 ) )
01274           return KSpreadValue::errorVALUE();
01275         if( val2.compare( val1 ) > 0 )
01276           stack.push( KSpreadValue( true ) );
01277         else
01278           stack.push( KSpreadValue( false ) );
01279         break;
01280 
01281 
01282       case Opcode::Cell:
01283         c = d->constants[index].asString();
01284         val1 = KSpreadValue::empty();
01285         if (sheet)
01286         {
01287           KSpreadPoint cell (c, sheet->workbook(), sheet);
01288           if (cell.isValid())
01289             val1 = cell.sheet->value (cell.column(), cell.row());
01290         }
01291         stack.push( val1 );
01292         break;
01293       
01294       case Opcode::Range:
01295         c = d->constants[index].asString();
01296         val1 = KSpreadValue::empty();
01297         if (sheet)
01298         {
01299           KSpreadRange range (c, sheet->workbook(), sheet);
01300           if (range.isValid())
01301             val1 = range.sheet->valueRange (range.startCol(), range.startRow(),
01302                 range.endCol(), range.endRow());
01303         }
01304         stack.push( val1 );
01305         break;
01306       
01307       case Opcode::Ref:
01308         val1 = d->constants[index];
01309         stack.push( val1 );
01310         break;
01311 
01312       // calling function
01313       case Opcode::Function:
01314         return KSpreadValue::errorVALUE();
01315         
01316         if( stack.count() < index )
01317           // (Tomas) umm, how could that be ? I mean, the index value
01318           //  is computed from the stack *confused*
01319           return KSpreadValue::errorVALUE(); // not enough arguments
01320         args.clear();
01321         for( ; index; index-- )
01322           args.insert( args.begin(), stack.pop() );
01323         // function name as string value
01324         val1 = converter->asString (stack.pop());
01325         if( val1.isError() )
01326           return KSpreadValue::errorVALUE();
01327         function = FunctionRepository::self()->function ( val1.asString() );
01328         if( !function )
01329           return KSpreadValue::errorVALUE(); // no such function
01330         stack.push( function->exec( this, args ) );
01331         
01332         break;
01333 
01334       default:
01335         break;
01336     }
01337   }
01338 
01339   // more than one value in stack ? unsuccesful execution...
01340   if( stack.count() != 1 )
01341     return KSpreadValue::errorVALUE();
01342 
01343   return stack.pop();
01344 
01345 }
01346 
01347 // Debugging aid
01348 
01349 QString Formula::dump() const
01350 {
01351   QString result;
01352 
01353   if( d->dirty )
01354   {
01355     Tokens tokens = scan( d->expression );
01356     compile( tokens );
01357   }
01358 
01359   result = QString("Expression: [%1]\n").arg( d->expression );
01360 #if 0  
01361   KSpreadValue value = eval();
01362   result.append( QString("Result: %1\n").arg(
01363       converter->asString(value).asString() ) );
01364 #endif
01365 
01366   result.append("  Constants:\n");
01367   for( unsigned c = 0; c < d->constants.count(); c++ )
01368   {
01369     QString vtext;
01370     KSpreadValue val = d->constants[c];
01371     if( val.isString() ) vtext = QString("[%1]").arg( val.asString() );
01372     else if( val.isNumber() ) vtext = QString("%1").arg( val.asFloat() );
01373     else if( val.isBoolean() ) vtext = QString("%1").arg( val.asBoolean() ? "True":"False");
01374     else if( val.isError() ) vtext = "error";
01375     else vtext = "???";
01376     result += QString("    #%1 = %2\n").arg(c).arg( vtext );
01377   }
01378 
01379   result.append("\n");
01380   result.append("  Code:\n");
01381   for( unsigned i = 0; i < d->codes.count(); i++ )
01382   {
01383     QString ctext;
01384     switch( d->codes[i].type )
01385     {
01386       case Opcode::Load:     ctext = QString("Load #%1").arg( d->codes[i].index ); break;
01387       case Opcode::Ref:      ctext = QString("Ref #%1").arg( d->codes[i].index ); break;
01388       case Opcode::Function: ctext = QString("Function (%1)").arg( d->codes[i].index ); break;
01389       case Opcode::Add:      ctext = "Add"; break;
01390       case Opcode::Sub:      ctext = "Sub"; break;
01391       case Opcode::Mul:      ctext = "Mul"; break;
01392       case Opcode::Div:      ctext = "Div"; break;
01393       case Opcode::Neg:      ctext = "Neg"; break;
01394       case Opcode::Concat:   ctext = "Concat"; break;
01395       case Opcode::Pow:      ctext = "Pow"; break;
01396       case Opcode::Equal:    ctext = "Equal"; break;
01397       case Opcode::Not:      ctext = "Not"; break;
01398       case Opcode::Less:     ctext = "Less"; break;
01399       case Opcode::Greater:  ctext = "Greater"; break;
01400       default: ctext = "Unknown"; break;
01401     }
01402     result.append( "   " ).append( ctext ).append("\n");
01403   }
01404 
01405   return result;
01406 }
01407 
01408 QTextStream& operator<<( QTextStream& ts, Formula formula ) 
01409 {
01410   ts << formula.dump();
01411   return ts;
01412 }
KDE Logo
This file is part of the documentation for kspread Library Version 1.4.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Mon Feb 13 09:42:44 2006 by doxygen 1.4.2 written by Dimitri van Heesch, © 1997-2003