00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
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
00125 const Token Token::null;
00126
00127
00128
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
00163
00164 if( text == "==" ) result = Token::Equal;
00165 }
00166
00167 return result;
00168 }
00169
00170
00171
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
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
00211
00212
00213
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
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
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
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
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
00357
00358
00359
00360 static bool isIdentifier( QChar ch )
00361 {
00362 return ( ch.unicode() == '_' ) || (ch.unicode() == '$' ) || ( ch.isLetter() );
00363 }
00364
00365
00366
00367
00368
00369
00370
00371
00372
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
00389
00390 Formula::~Formula()
00391 {
00392 delete d;
00393 }
00394
00395 KSpreadCell* Formula::cell()
00396 {
00397 return d->cell;
00398 }
00399
00400
00401
00402
00403
00404 void Formula::setExpression( const QString& expr )
00405 {
00406 d->expression = expr;
00407 d->dirty = true;
00408 d->valid = false;
00409 }
00410
00411
00412
00413 QString Formula::expression() const
00414 {
00415 return d->expression;
00416 }
00417
00418
00419
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
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
00447
00448
00449
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
00460 Tokens tokens;
00461
00462
00463 enum { Start, Finish, Bad, InNumber, InDecimal, InExpIndicator, InExponent,
00464 InString, InIdentifier, InCell, InRange, InSheetName } state;
00465
00466
00467 QString thousand = locale ? locale->thousandsSeparator() : "";
00468 QString decimal = locale ? locale->decimalSymbol() : ".";
00469
00470
00471 state = Start;
00472 unsigned int i = 0;
00473 QString ex = expr;
00474 QString tokenText;
00475 int tokenStart = 0;
00476
00477
00478 if( ex[0] != '=' )
00479 return tokens;
00480
00481
00482 ex.remove( 0, 1 );
00483
00484
00485 ex.append( QChar() );
00486
00487
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
00500 if( ch.isSpace() ) i++;
00501
00502
00503 else if( ch.isDigit() )
00504 {
00505 state = InNumber;
00506 }
00507
00508
00509 else if ( ch == '"' )
00510 {
00511 tokenText.append( ex[i++] );
00512 state = InString;
00513 }
00514
00515
00516
00517 else if( isIdentifier( ch ) )
00518 {
00519 state = InIdentifier;
00520 }
00521
00522
00523 else if ( ch.unicode() == 39 )
00524 {
00525 i++;
00526 state = InSheetName;
00527 tokenText.append( QChar( 39 ) );
00528 }
00529
00530
00531 else if ( ch == decimal )
00532 {
00533 tokenText.append( ex[i++] );
00534 state = InDecimal;
00535 }
00536
00537
00538 else if ( ch == QChar::null )
00539 state = Finish;
00540
00541
00542 else
00543 {
00544 int op;
00545 QString s;
00546
00547
00548 s.append( ch ).append( ex[i+1] );
00549 op = matchOperator( s );
00550
00551
00552 if( op == Token::InvalidOp )
00553 {
00554 s = QString( ch );
00555 op = matchOperator( s );
00556 }
00557
00558
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
00572 if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
00573
00574
00575 else if( ch == '!' )
00576 {
00577 tokenText.append( ex[i++] );
00578 state = InCell;
00579 }
00580
00581
00582 else
00583 {
00584
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
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
00614 if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
00615
00616
00617
00618 else
00619 {
00620
00621
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
00633 tokens.append( Token( Token::Range, tokenText, tokenStart ) );
00634 tokenText = "";
00635 state = Start;
00636 }
00637
00638 else
00639 {
00640
00641
00642
00643 if( ch == ':' )
00644 {
00645 tokenText.append( ex[i++] );
00646 state = InRange;
00647 }
00648 else
00649 {
00650
00651 tokens.append( Token( Token::Cell, tokenText, tokenStart ) );
00652 tokenText = "";
00653 state = Start;
00654 }
00655 }
00656 }
00657 break;
00658
00659 case InRange:
00660
00661
00662 if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
00663
00664
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
00676 if( ch.unicode() != 39 ) tokenText.append( ex[i++] );
00677
00678 else
00679 {
00680
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
00694 if( ch.isDigit() ) tokenText.append( ex[i++] );
00695
00696
00697 else if( !thousand.isEmpty() && ( ch ==thousand[0] ) ) i++;
00698
00699
00700
00701 else if(( !decimal.isEmpty() && ( ch == decimal[0] ) ) || (ch == '.'))
00702 {
00703 tokenText.append( '.' );
00704 i++;
00705 state = InDecimal;
00706 }
00707
00708
00709 else if( ch.upper() == 'E' )
00710 {
00711 tokenText.append( 'E' );
00712 i++;
00713 state = InExpIndicator;
00714 }
00715
00716
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
00728 if( ch.isDigit() ) tokenText.append( ex[i++] );
00729
00730
00731 else if( ch.upper() == 'E' )
00732 {
00733 tokenText.append( 'E' );
00734 i++;
00735 state = InExpIndicator;
00736 }
00737
00738
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
00750 if( ( ch == '+' ) || ( ch == '-' ) ) tokenText.append( ex[i++] );
00751
00752
00753 else if( ch.isDigit() ) state = InExponent;
00754
00755
00756 else state = Bad;
00757
00758 break;
00759
00760 case InExponent:
00761
00762
00763 if( ch.isDigit() ) tokenText.append( ex[i++] );
00764
00765
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
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
00801 void Formula::compile( const Tokens& tokens ) const
00802 {
00803
00804 d->dirty = false;
00805 d->valid = false;
00806 d->codes.clear();
00807 d->constants.clear();
00808
00809
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
00819 Token token = ( i < tokens.count() ) ? tokens[i] : Token( Token::Operator );
00820 Token::Type tokenType = token.type();
00821
00822
00823 if( tokenType == Token::Unknown ) break;
00824
00825
00826
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
00836
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
00851
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
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
00879 if( tokenType == Token::Operator )
00880 if( token.asOperator() != Token::Percent )
00881 {
00882
00883 for( ; ; )
00884 {
00885 bool ruleFound = false;
00886
00887
00888
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
00913
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
00938
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
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
00980
00981
00982
00983
00984
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
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
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
01019 case Token::NotEqual:
01020 d->codes.append( Opcode::Equal );
01021 d->codes.append( Opcode::Not );
01022 break;
01023
01024
01025 case Token::LessEqual:
01026 d->codes.append( Opcode::Greater );
01027 d->codes.append( Opcode::Not );
01028 break;
01029
01030
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
01041
01042
01043
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
01066
01067
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
01091 if( token.asOperator() != Token::Percent )
01092 syntaxStack.push( token );
01093 }
01094 }
01095
01096
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
01105 if( !d->valid )
01106 {
01107 d->constants.clear();
01108 d->codes.clear();
01109 }
01110 }
01111
01112
01113
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
01162 case Opcode::Nop:
01163 break;
01164
01165
01166 case Opcode::Load:
01167 val1 = d->constants[index];
01168 stack.push( val1 );
01169 break;
01170
01171
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
01179
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
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
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
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
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
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
01313 case Opcode::Function:
01314 return KSpreadValue::errorVALUE();
01315
01316 if( stack.count() < index )
01317
01318
01319 return KSpreadValue::errorVALUE();
01320 args.clear();
01321 for( ; index; index-- )
01322 args.insert( args.begin(), stack.pop() );
01323
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();
01330 stack.push( function->exec( this, args ) );
01331
01332 break;
01333
01334 default:
01335 break;
01336 }
01337 }
01338
01339
01340 if( stack.count() != 1 )
01341 return KSpreadValue::errorVALUE();
01342
01343 return stack.pop();
01344
01345 }
01346
01347
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 }