KOffice – TDE office suite
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1536 lines
41KB

  1. /* This file is part of the KDE project
  2. Copyright (C) 2003,2004 Ariya Hidayat <ariya@kde.org>
  3. Copyright (C) 2005 Tomas Mecir <mecirt@gmail.com>
  4. This library is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU Library General Public
  6. License as published by the Free Software Foundation; either
  7. version 2 of the License.
  8. This library is distributed in the hope that it will be useful,
  9. but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. Library General Public License for more details.
  12. You should have received a copy of the GNU Library General Public License
  13. along with this library; see the file COPYING.LIB. If not, write to
  14. the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  15. * Boston, MA 02110-1301, USA.
  16. */
  17. #include "formula.h"
  18. #include "kspread_cell.h"
  19. #include "kspread_sheet.h"
  20. #include "kspread_doc.h"
  21. #include "kspread_util.h"
  22. #include "kspread_value.h"
  23. #include "valuecalc.h"
  24. #include "valueconverter.h"
  25. #include "valueparser.h"
  26. #include "functions.h"
  27. #include <limits.h>
  28. #include <tqregexp.h>
  29. #include <tqstring.h>
  30. #include <tqvaluevector.h>
  31. #include <tqvaluestack.h>
  32. #include <tdelocale.h>
  33. /*
  34. To understand how this formula engine works, please refer to the documentation
  35. in file DESIGN.html.
  36. Useful references:
  37. - "Principles of Compiler Design", A.V.Aho, J.D.Ullman, Addison Wesley, 1978
  38. - "Writing Interactive Compilers and Interpreters", P.J. Brown,
  39. John Wiley and Sons, 1979.
  40. - "The Theory and Practice of Compiler Writing", J.Tremblay, P.G.Sorenson,
  41. McGraw-Hill, 1985.
  42. - "The Java(TM) Virtual Machine Specification", T.Lindholm, F.Yellin,
  43. Addison-Wesley, 1997.
  44. - "Java Virtual Machine", J.Meyer, T.Downing, O'Reilly, 1997.
  45. */
  46. /*
  47. TODO - features:
  48. - handle Intersection
  49. - cell reference is made relative (absolute now)
  50. - shared formula (different owner, same data)
  51. - relative internal representation (independent of owner)
  52. - OASIS support
  53. TODO - optimizations:
  54. - handle initial formula marker = (and +)
  55. - reuse constant already in the pool
  56. - reuse references already in the pool
  57. - expression optimization (e.g. 1+2+A1 becomes 3+A1)
  58. */
  59. namespace KSpread
  60. {
  61. class Opcode
  62. {
  63. public:
  64. enum { Nop = 0, Load, Ref, Cell, Range, Function, Add, Sub, Neg, Mul, Div,
  65. Pow, Concat, Not, Equal, Less, Greater };
  66. unsigned type;
  67. unsigned index;
  68. Opcode(): type(Nop), index(0) {};
  69. Opcode( unsigned t ): type(t), index(0) {};
  70. Opcode( unsigned t, unsigned i ): type(t), index(i) {};
  71. };
  72. class Formula::Private
  73. {
  74. public:
  75. Formula *formula;
  76. Cell *cell;
  77. Sheet *sheet;
  78. bool dirty;
  79. bool valid;
  80. TQString expression;
  81. TQValueVector<Opcode> codes;
  82. TQValueVector<Value> constants;
  83. };
  84. class TokenStack : public TQValueVector<Token>
  85. {
  86. public:
  87. TokenStack();
  88. bool isEmpty() const;
  89. unsigned itemCount() const;
  90. void push( const Token& token );
  91. Token pop();
  92. const Token& top();
  93. const Token& top( unsigned index );
  94. private:
  95. void ensureSpace();
  96. unsigned topIndex;
  97. };
  98. }
  99. using namespace KSpread;
  100. // for null token
  101. const Token Token::null;
  102. // helper function: return operator of given token text
  103. // e.g. "*" yields Operator::Asterisk, and so on
  104. Token::Op KSpread::matchOperator( const TQString& text )
  105. {
  106. Token::Op result = Token::InvalidOp;
  107. if( text.length() == 1 )
  108. {
  109. TQChar p = text[0];
  110. switch( p.unicode() )
  111. {
  112. case '+': result = Token::Plus; break;
  113. case '-': result = Token::Minus; break;
  114. case '*': result = Token::Asterisk; break;
  115. case '/': result = Token::Slash; break;
  116. case '^': result = Token::Caret; break;
  117. case ',': result = Token::Comma; break;
  118. case ';': result = Token::Semicolon; break;
  119. case '(': result = Token::LeftPar; break;
  120. case ')': result = Token::RightPar; break;
  121. case '&': result = Token::Ampersand; break;
  122. case '=': result = Token::Equal; break;
  123. case '<': result = Token::Less; break;
  124. case '>': result = Token::Greater; break;
  125. case '%': result = Token::Percent; break;
  126. default : result = Token::InvalidOp; break;
  127. }
  128. }
  129. if( text.length() == 2 )
  130. {
  131. if( text == "<>" ) result = Token::NotEqual;
  132. if( text == "<=" ) result = Token::LessEqual;
  133. if( text == ">=" ) result = Token::GreaterEqual;
  134. if( text == "==" ) result = Token::Equal;
  135. }
  136. return result;
  137. }
  138. // helper function: give operator precedence
  139. // e.g. "+" is 1 while "*" is 3
  140. static int opPrecedence( Token::Op op )
  141. {
  142. int prec = -1;
  143. switch( op )
  144. {
  145. case Token::Percent : prec = 8; break;
  146. case Token::Caret : prec = 7; break;
  147. case Token::Asterisk : prec = 5; break;
  148. case Token::Slash : prec = 6; break;
  149. case Token::Plus : prec = 3; break;
  150. case Token::Minus : prec = 3; break;
  151. case Token::Ampersand : prec = 2; break;
  152. case Token::Equal : prec = 1; break;
  153. case Token::NotEqual : prec = 1; break;
  154. case Token::Less : prec = 1; break;
  155. case Token::Greater : prec = 1; break;
  156. case Token::LessEqual : prec = 1; break;
  157. case Token::GreaterEqual : prec = 1; break;
  158. case Token::Semicolon : prec = 0; break;
  159. case Token::RightPar : prec = 0; break;
  160. case Token::LeftPar : prec = -1; break;
  161. default: prec = -1; break;
  162. }
  163. return prec;
  164. }
  165. // helper function
  166. static Value tokenAsValue( const Token& token )
  167. {
  168. Value value;
  169. if( token.isBoolean() ) value = Value( token.asBoolean() );
  170. else if( token.isInteger() ) value = Value( token.asInteger() );
  171. else if( token.isFloat() ) value = Value( token.asFloat() );
  172. else if( token.isString() ) value = Value( token.asString() );
  173. return value;
  174. }
  175. /**********************
  176. Token
  177. **********************/
  178. // creates a token
  179. Token::Token( Type type, const TQString& text, int pos )
  180. {
  181. m_type = type;
  182. m_text = text;
  183. m_pos = pos;
  184. }
  185. // copy constructor
  186. Token::Token( const Token& token )
  187. {
  188. m_type = token.m_type;
  189. m_text = token.m_text;
  190. m_pos = token.m_pos;
  191. }
  192. // assignment operator
  193. Token& Token::operator=( const Token& token )
  194. {
  195. m_type = token.m_type;
  196. m_text = token.m_text;
  197. m_pos = token.m_pos;
  198. return *this;
  199. }
  200. bool Token::asBoolean() const
  201. {
  202. if( !isBoolean() ) return false;
  203. return m_text.lower() == "true";
  204. // FIXME check also for i18n version
  205. }
  206. long Token::asInteger() const
  207. {
  208. if( isInteger() ) return m_text.toLong();
  209. else return 0;
  210. }
  211. double Token::asFloat() const
  212. {
  213. if( isFloat() ) return m_text.toDouble();
  214. else return 0.0;
  215. }
  216. TQString Token::asString() const
  217. {
  218. if( isString() ) return m_text.mid( 1, m_text.length()-2 );
  219. else return TQString();
  220. }
  221. Token::Op Token::asOperator() const
  222. {
  223. if( isOperator() ) return matchOperator( m_text );
  224. else return InvalidOp;
  225. }
  226. TQString Token::sheetName() const
  227. {
  228. if( !isCell() && !isRange() ) return TQString();
  229. int i = m_text.find( '!' );
  230. if( i < 0 ) return TQString();
  231. TQString sheet = m_text.left( i );
  232. return sheet;
  233. }
  234. TQString Token::description() const
  235. {
  236. TQString desc;
  237. switch (m_type )
  238. {
  239. case Boolean: desc = "Boolean"; break;
  240. case Integer: desc = "Integer"; break;
  241. case Float: desc = "Float"; break;
  242. case String: desc = "String"; break;
  243. case Identifier: desc = "Identifier"; break;
  244. case Cell: desc = "Cell"; break;
  245. case Range: desc = "Range"; break;
  246. case Operator: desc = "Operator"; break;
  247. default: desc = "Unknown"; break;
  248. }
  249. while( desc.length() < 10 ) desc.prepend( ' ' );
  250. desc.prepend( " " );
  251. desc.prepend( TQString::number( m_pos ) );
  252. desc.append( " : " ).append( m_text );
  253. return desc;
  254. }
  255. /**********************
  256. TokenStack
  257. **********************/
  258. TokenStack::TokenStack(): TQValueVector<Token>()
  259. {
  260. topIndex = 0;
  261. ensureSpace();
  262. }
  263. bool TokenStack::isEmpty() const
  264. {
  265. return topIndex == 0;
  266. }
  267. unsigned TokenStack::itemCount() const
  268. {
  269. return topIndex;
  270. }
  271. void TokenStack::push( const Token& token )
  272. {
  273. ensureSpace();
  274. at( topIndex++ ) = token;
  275. }
  276. Token TokenStack::pop()
  277. {
  278. return (topIndex > 0 ) ? Token( at( --topIndex ) ) : Token();
  279. }
  280. const Token& TokenStack::top()
  281. {
  282. return top( 0 );
  283. }
  284. const Token& TokenStack::top( unsigned index )
  285. {
  286. if( topIndex > index )
  287. return at( topIndex-index-1 );
  288. return Token::null;
  289. }
  290. void TokenStack::ensureSpace()
  291. {
  292. while( topIndex >= size() )
  293. resize( size() + 10 );
  294. }
  295. /**********************
  296. FormulaPrivate
  297. **********************/
  298. // helper function: return true for valid identifier character
  299. bool KSpread::isIdentifier( TQChar ch )
  300. {
  301. return ( ch.unicode() == '_' ) || (ch.unicode() == '$' ) || ( ch.isLetter() );
  302. }
  303. /**********************
  304. Formula
  305. **********************/
  306. // Constructor
  307. Formula::Formula (Sheet *sheet, Cell *cell)
  308. {
  309. d = new Private;
  310. d->cell = cell;
  311. d->sheet = sheet;
  312. clear();
  313. }
  314. Formula::Formula()
  315. {
  316. d = new Private;
  317. d->cell = 0;
  318. d->sheet = 0;
  319. clear();
  320. }
  321. // Destructor
  322. Formula::~Formula()
  323. {
  324. delete d;
  325. }
  326. Cell* Formula::cell() const
  327. {
  328. return d->cell;
  329. }
  330. Sheet* Formula::sheet() const
  331. {
  332. return d->sheet;
  333. }
  334. // Sets a new expression for this formula.
  335. // note that both the real lex and parse processes will happen later on
  336. // when needed (i.e. "lazy parse"), for example during formula evaluation.
  337. void Formula::setExpression( const TQString& expr )
  338. {
  339. d->expression = expr;
  340. d->dirty = true;
  341. d->valid = false;
  342. }
  343. // Returns the expression associated with this formula.
  344. TQString Formula::expression() const
  345. {
  346. return d->expression;
  347. }
  348. // Returns the validity of the formula.
  349. // note: empty formula is always invalid.
  350. bool Formula::isValid() const
  351. {
  352. if( d->dirty )
  353. {
  354. TDELocale* locale = d->cell ? d->cell->locale() : 0;
  355. if ((!locale) && d->sheet)
  356. locale = d->sheet->doc()->locale();
  357. Tokens tokens = scan( d->expression, locale );
  358. if( tokens.valid() )
  359. compile( tokens );
  360. else
  361. d->valid = false;
  362. }
  363. return d->valid;
  364. }
  365. // Clears everything, also mark the formula as invalid.
  366. void Formula::clear()
  367. {
  368. d->expression = TQString();
  369. d->dirty = true;
  370. d->valid = false;
  371. d->constants.clear();
  372. d->codes.clear();
  373. }
  374. // Returns list of token for the expression.
  375. // this triggers again the lexical analysis step. it is however preferable
  376. // (even when there's small performance penalty) because otherwise we need to
  377. // store parsed tokens all the time which serves no good purpose.
  378. Tokens Formula::tokens() const
  379. {
  380. TDELocale* locale = d->cell ? d->cell->locale() : 0;
  381. if ((!locale) && d->sheet)
  382. locale = d->sheet->doc()->locale();
  383. return scan( d->expression, locale );
  384. }
  385. Tokens Formula::scan( const TQString& expr, TDELocale* locale ) const
  386. {
  387. // to hold the result
  388. Tokens tokens;
  389. // parsing state
  390. enum { Start, Finish, Bad, InNumber, InDecimal, InExpIndicator, InExponent,
  391. InString, InIdentifier, InCell, InRange, InSheetOrAreaName } state;
  392. // use locale settings if specified
  393. TQString thousand = locale ? locale->thousandsSeparator() : "";
  394. TQString decimal = locale ? locale->decimalSymbol() : ".";
  395. // initialize variables
  396. state = Start;
  397. unsigned int i = 0;
  398. TQString ex = expr;
  399. TQString tokenText;
  400. int tokenStart = 0;
  401. // first character must be equal sign (=)
  402. if( ex[0] != '=' )
  403. return tokens;
  404. // but the scanner should not see this equal sign
  405. ex.remove( 0, 1 );
  406. // force a terminator
  407. ex.append( TQChar() );
  408. // main loop
  409. while( (state != Bad) && (state != Finish) && (i < ex.length()) )
  410. {
  411. TQChar ch = ex[i];
  412. switch( state )
  413. {
  414. case Start:
  415. tokenStart = i;
  416. // skip any whitespaces
  417. if( ch.isSpace() ) i++;
  418. // check for number
  419. else if( ch.isDigit() )
  420. {
  421. state = InNumber;
  422. }
  423. // a string ?
  424. else if ( ch == '"' )
  425. {
  426. tokenText.append( ex[i++] );
  427. state = InString;
  428. }
  429. // beginning with alphanumeric ?
  430. // could be identifier, cell, range, or function...
  431. else if( isIdentifier( ch ) )
  432. {
  433. state = InIdentifier;
  434. }
  435. // aposthrophe (') marks sheet name for 3-d cell, e.g 'Sales Q3'!A4, or a named range
  436. else if ( ch.unicode() == '\'' )
  437. {
  438. i++;
  439. state = InSheetOrAreaName;
  440. }
  441. // decimal dot ?
  442. else if ( ch == decimal )
  443. {
  444. tokenText.append( ex[i++] );
  445. state = InDecimal;
  446. }
  447. // terminator character
  448. else if ( ch == TQChar::null )
  449. state = Finish;
  450. // look for operator match
  451. else
  452. {
  453. int op;
  454. TQString s;
  455. // check for two-chars operator, such as '<=', '>=', etc
  456. s.append( ch ).append( ex[i+1] );
  457. op = matchOperator( s );
  458. // check for one-char operator, such as '+', ';', etc
  459. if( op == Token::InvalidOp )
  460. {
  461. s = TQString( ch );
  462. op = matchOperator( s );
  463. }
  464. // any matched operator ?
  465. if( op != Token::InvalidOp )
  466. {
  467. int len = s.length();
  468. i += len;
  469. tokens.append( Token( Token::Operator, s.left( len ), tokenStart ) );
  470. }
  471. else state = Bad;
  472. }
  473. break;
  474. case InIdentifier:
  475. // consume as long as alpha, dollar sign, underscore, or digit
  476. if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
  477. // a '!' ? then this must be sheet name, e.g "Sheet4!"
  478. else if( ch == '!' )
  479. {
  480. tokenText.append( ex[i++] );
  481. state = InCell;
  482. }
  483. // a '(' ? then this must be a function identifier
  484. else if( ch == '(' )
  485. {
  486. tokens.append (Token (Token::Identifier, tokenText, tokenStart));
  487. tokenStart = i;
  488. tokenText = "";
  489. state = Start;
  490. }
  491. // we're done with identifier
  492. else
  493. {
  494. // check for cell reference, e.g A1, VV123, ...
  495. TQRegExp exp("(\\$?)([a-zA-Z]+)(\\$?)([0-9]+)$");
  496. int n = exp.search( tokenText );
  497. if( n >= 0 )
  498. state = InCell;
  499. else
  500. {
  501. if ( isNamedArea( tokenText ) )
  502. tokens.append (Token (Token::Range, tokenText, tokenStart));
  503. else
  504. tokens.append (Token (Token::Identifier, tokenText, tokenStart));
  505. tokenStart = i;
  506. tokenText = "";
  507. state = Start;
  508. }
  509. }
  510. break;
  511. case InCell:
  512. // consume as long as alpha, dollar sign, underscore, or digit
  513. if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
  514. // we're done with cell ref, possibly with sheet name (like "Sheet2!B2")
  515. // note that "Sheet2!TotalSales" is also possible, in which "TotalSales" is a named area
  516. else
  517. {
  518. // check if it's a cell ref like A32, not named area
  519. TQString cell;
  520. for( int j = tokenText.length()-1; j>=0; j-- )
  521. if( tokenText[j] == '!' )
  522. break;
  523. else
  524. cell.prepend( tokenText[j] );
  525. TQRegExp exp("(\\$?)([a-zA-Z]+)(\\$?)([0-9]+)$");
  526. if( exp.search( cell ) != 0 )
  527. {
  528. // we're done with named area
  529. // (Tomas) huh? this doesn't seem to check for named areas ...
  530. tokens.append( Token( Token::Range, tokenText, tokenStart ) );
  531. tokenText = "";
  532. state = Start;
  533. }
  534. else
  535. {
  536. // so up to now we've got something like A2 or Sheet2!F4
  537. // check for range reference
  538. if( ch == ':' )
  539. {
  540. tokenText.append( ex[i++] );
  541. state = InRange;
  542. }
  543. else
  544. {
  545. // we're done with cell reference
  546. tokens.append( Token( Token::Cell, tokenText, tokenStart ) );
  547. tokenText = "";
  548. state = Start;
  549. }
  550. }
  551. }
  552. break;
  553. case InRange:
  554. // consume as long as alpha, dollar sign, underscore, or digit
  555. if( isIdentifier( ch ) || ch.isDigit() ) tokenText.append( ex[i++] );
  556. // we're done with range reference
  557. else
  558. {
  559. tokens.append( Token( Token::Range, tokenText, tokenStart ) );
  560. tokenText = "";
  561. state = Start;
  562. }
  563. break;
  564. case InSheetOrAreaName:
  565. // consume until '
  566. if ( ch.unicode() != '\'' )
  567. tokenText.append( ex[i++] );
  568. else
  569. {
  570. // eat the aposthrophe itself
  571. ++i;
  572. // must be followed by '!' to be sheet name
  573. if( ex[i] == '!' )
  574. {
  575. tokenText.append( ex[i++] );
  576. state = InCell;
  577. }
  578. else
  579. {
  580. if ( isNamedArea( tokenText ) )
  581. tokens.append (Token (Token::Range, tokenText, tokenStart));
  582. else
  583. tokens.append (Token (Token::Identifier, tokenText, tokenStart));
  584. tokenStart = i;
  585. tokenText = "";
  586. state = Start;
  587. }
  588. }
  589. break;
  590. case InNumber:
  591. // consume as long as it's digit
  592. if( ch.isDigit() ) tokenText.append( ex[i++] );
  593. // skip thousand separator
  594. else if( !thousand.isEmpty() && ( ch ==thousand[0] ) ) i++;
  595. // convert decimal separator to '.', also support '.' directly
  596. // we always support '.' because of bug #98455
  597. else if(( !decimal.isEmpty() && ( ch == decimal[0] ) ) || (ch == '.'))
  598. {
  599. tokenText.append( '.' );
  600. i++;
  601. state = InDecimal;
  602. }
  603. // exponent ?
  604. else if( ch.upper() == 'E' )
  605. {
  606. tokenText.append( 'E' );
  607. i++;
  608. state = InExpIndicator;
  609. }
  610. // reference sheet delimiter?
  611. else if( ch == '!' )
  612. {
  613. tokenText.append( ex[i++] );
  614. state = InCell;
  615. }
  616. // identifier?
  617. else if( isIdentifier( ch ) )
  618. {
  619. // has to be a sheet or area name then
  620. state = InIdentifier;
  621. }
  622. // we're done with integer number
  623. else
  624. {
  625. tokens.append( Token( Token::Integer, tokenText, tokenStart ) );
  626. tokenText = "";
  627. state = Start;
  628. };
  629. break;
  630. case InDecimal:
  631. // consume as long as it's digit
  632. if( ch.isDigit() ) tokenText.append( ex[i++] );
  633. // exponent ?
  634. else if( ch.upper() == 'E' )
  635. {
  636. tokenText.append( 'E' );
  637. i++;
  638. state = InExpIndicator;
  639. }
  640. // we're done with floating-point number
  641. else
  642. {
  643. tokens.append( Token( Token::Float, tokenText, tokenStart ) );
  644. tokenText = "";
  645. state = Start;
  646. };
  647. break;
  648. case InExpIndicator:
  649. // possible + or - right after E, e.g 1.23E+12 or 4.67E-8
  650. if( ( ch == '+' ) || ( ch == '-' ) ) tokenText.append( ex[i++] );
  651. // consume as long as it's digit
  652. else if( ch.isDigit() ) state = InExponent;
  653. // invalid thing here
  654. else state = Bad;
  655. break;
  656. case InExponent:
  657. // consume as long as it's digit
  658. if( ch.isDigit() ) tokenText.append( ex[i++] );
  659. // we're done with floating-point number
  660. else
  661. {
  662. tokens.append( Token( Token::Float, tokenText, tokenStart ) );
  663. tokenText = "";
  664. state = Start;
  665. };
  666. break;
  667. case InString:
  668. // consume until "
  669. if( ch != '"' ) tokenText.append( ex[i++] );
  670. else
  671. {
  672. tokenText.append( ch ); i++;
  673. tokens.append( Token( Token::String, tokenText, tokenStart ) );
  674. tokenText = "";
  675. state = Start;
  676. }
  677. break;
  678. case Bad:
  679. default:
  680. break;
  681. };
  682. };
  683. if( state == Bad )
  684. tokens.setValid( false );
  685. return tokens;
  686. }
  687. // will affect: dirty, valid, codes, constants
  688. void Formula::compile( const Tokens& tokens ) const
  689. {
  690. // initialize variables
  691. d->dirty = false;
  692. d->valid = false;
  693. d->codes.clear();
  694. d->constants.clear();
  695. // sanity check
  696. if( tokens.count() == 0 ) return;
  697. TokenStack syntaxStack;
  698. TQValueStack<int> argStack;
  699. unsigned argCount = 1;
  700. for( unsigned i = 0; i <= tokens.count(); i++ )
  701. {
  702. // helper token: InvalidOp is end-of-formula
  703. Token token = ( i < tokens.count() ) ? tokens[i] : Token( Token::Operator );
  704. Token::Type tokenType = token.type();
  705. // unknown token is invalid
  706. if( tokenType == Token::Unknown ) break;
  707. // for constants, push immediately to stack
  708. // generate code to load from a constant
  709. if ( ( tokenType == Token::Integer ) || ( tokenType == Token::Float ) ||
  710. ( tokenType == Token::String ) || ( tokenType == Token::Boolean ) )
  711. {
  712. syntaxStack.push( token );
  713. d->constants.append( tokenAsValue( token ) );
  714. d->codes.append( Opcode( Opcode::Load, d->constants.count()-1 ) );
  715. }
  716. // for cell, range, or identifier, push immediately to stack
  717. // generate code to load from reference
  718. if( ( tokenType == Token::Cell ) || ( tokenType == Token::Range ) ||
  719. ( tokenType == Token::Identifier ) )
  720. {
  721. syntaxStack.push( token );
  722. d->constants.append( Value( token.text() ) );
  723. if (tokenType == Token::Cell)
  724. d->codes.append( Opcode( Opcode::Cell, d->constants.count()-1 ) );
  725. else if (tokenType == Token::Range)
  726. d->codes.append( Opcode( Opcode::Range, d->constants.count()-1 ) );
  727. else
  728. d->codes.append( Opcode( Opcode::Ref, d->constants.count()-1 ) );
  729. }
  730. // are we entering a function ?
  731. // if token is operator, and stack already has: id ( arg
  732. if( tokenType == Token::Operator )
  733. if( syntaxStack.itemCount() >= 3 )
  734. {
  735. Token arg = syntaxStack.top();
  736. Token par = syntaxStack.top( 1 );
  737. Token id = syntaxStack.top( 2 );
  738. if( !arg.isOperator() )
  739. if( par.asOperator() == Token::LeftPar )
  740. if( id.isIdentifier() )
  741. {
  742. argStack.push( argCount );
  743. argCount = 1;
  744. }
  745. }
  746. // special case for percentage
  747. if( tokenType == Token::Operator )
  748. if( token.asOperator() == Token::Percent )
  749. if( syntaxStack.itemCount() >= 1 )
  750. if( !syntaxStack.top().isOperator() )
  751. {
  752. d->constants.append( Value( 0.01 ) );
  753. d->codes.append( Opcode( Opcode::Load, d->constants.count()-1 ) );
  754. d->codes.append( Opcode( Opcode::Mul ) );
  755. }
  756. // for any other operator, try to apply all parsing rules
  757. if( tokenType == Token::Operator )
  758. if( token.asOperator() != Token::Percent )
  759. {
  760. // repeat until no more rule applies
  761. for( ; ; )
  762. {
  763. bool ruleFound = false;
  764. // rule for function arguments, if token is ; or )
  765. // id ( arg1 ; arg2 -> id ( arg
  766. if( !ruleFound )
  767. if( syntaxStack.itemCount() >= 5 )
  768. if( ( token.asOperator() == Token::RightPar ) ||
  769. ( token.asOperator() == Token::Semicolon ) )
  770. {
  771. Token arg2 = syntaxStack.top();
  772. Token sep = syntaxStack.top( 1 );
  773. Token arg1 = syntaxStack.top( 2 );
  774. Token par = syntaxStack.top( 3 );
  775. Token id = syntaxStack.top( 4 );
  776. if( !arg2.isOperator() )
  777. if( sep.asOperator() == Token::Semicolon )
  778. if( !arg1.isOperator() )
  779. if( par.asOperator() == Token::LeftPar )
  780. if( id.isIdentifier() )
  781. {
  782. ruleFound = true;
  783. syntaxStack.pop();
  784. syntaxStack.pop();
  785. argCount++;
  786. }
  787. }
  788. // rule for function last argument:
  789. // id ( arg ) -> arg
  790. if( !ruleFound )
  791. if( syntaxStack.itemCount() >= 4 )
  792. {
  793. Token par2 = syntaxStack.top();
  794. Token arg = syntaxStack.top( 1 );
  795. Token par1 = syntaxStack.top( 2 );
  796. Token id = syntaxStack.top( 3 );
  797. if( par2.asOperator() == Token::RightPar )
  798. if( !arg.isOperator() )
  799. if( par1.asOperator() == Token::LeftPar )
  800. if( id.isIdentifier() )
  801. {
  802. ruleFound = true;
  803. syntaxStack.pop();
  804. syntaxStack.pop();
  805. syntaxStack.pop();
  806. syntaxStack.pop();
  807. syntaxStack.push( arg );
  808. d->codes.append( Opcode( Opcode::Function, argCount ) );
  809. argCount = argStack.empty() ? 0 : argStack.pop();
  810. }
  811. }
  812. // rule for function call with parentheses, but without argument
  813. // e.g. "2*PI()"
  814. if( !ruleFound )
  815. if( syntaxStack.itemCount() >= 3 )
  816. {
  817. Token par2 = syntaxStack.top();
  818. Token par1 = syntaxStack.top( 1 );
  819. Token id = syntaxStack.top( 2 );
  820. if( par2.asOperator() == Token::RightPar )
  821. if( par1.asOperator() == Token::LeftPar )
  822. if( id.isIdentifier() )
  823. {
  824. ruleFound = true;
  825. syntaxStack.pop();
  826. syntaxStack.pop();
  827. syntaxStack.pop();
  828. syntaxStack.push( Token( Token::Integer ) );
  829. d->codes.append( Opcode( Opcode::Function, 0 ) );
  830. }
  831. }
  832. // rule for parenthesis: ( Y ) -> Y
  833. if( !ruleFound )
  834. if( syntaxStack.itemCount() >= 3 )
  835. {
  836. Token right = syntaxStack.top();
  837. Token y = syntaxStack.top( 1 );
  838. Token left = syntaxStack.top( 2 );
  839. if( right.isOperator() )
  840. if( !y.isOperator() )
  841. if( left.isOperator() )
  842. if( right.asOperator() == Token::RightPar )
  843. if( left.asOperator() == Token::LeftPar )
  844. {
  845. ruleFound = true;
  846. syntaxStack.pop();
  847. syntaxStack.pop();
  848. syntaxStack.pop();
  849. syntaxStack.push( y );
  850. }
  851. }
  852. // rule for binary operator: A (op) B -> A
  853. // conditions: precedence of op >= precedence of token
  854. // action: push (op) to result
  855. // e.g. "A * B" becomes "A" if token is operator "+"
  856. // exception: for caret (power operator), if op is another caret
  857. // then the rule doesn't apply, e.g. "2^3^2" is evaluated as "2^(3^2)"
  858. if( !ruleFound )
  859. if( syntaxStack.itemCount() >= 3 )
  860. {
  861. Token b = syntaxStack.top();
  862. Token op = syntaxStack.top( 1 );
  863. Token a = syntaxStack.top( 2 );
  864. if( !a.isOperator() )
  865. if( !b.isOperator() )
  866. if( op.isOperator() )
  867. if( token.asOperator() != Token::LeftPar )
  868. if( token.asOperator() != Token::Caret )
  869. if( opPrecedence( op.asOperator() ) >= opPrecedence( token.asOperator() ) )
  870. {
  871. ruleFound = true;
  872. syntaxStack.pop();
  873. syntaxStack.pop();
  874. syntaxStack.pop();
  875. syntaxStack.push( b );
  876. switch( op.asOperator() )
  877. {
  878. // simple binary operations
  879. case Token::Plus: d->codes.append( Opcode::Add ); break;
  880. case Token::Minus: d->codes.append( Opcode::Sub ); break;
  881. case Token::Asterisk: d->codes.append( Opcode::Mul ); break;
  882. case Token::Slash: d->codes.append( Opcode::Div ); break;
  883. case Token::Caret: d->codes.append( Opcode::Pow ); break;
  884. case Token::Ampersand: d->codes.append( Opcode::Concat ); break;
  885. // simple value comparisons
  886. case Token::Equal: d->codes.append( Opcode::Equal ); break;
  887. case Token::Less: d->codes.append( Opcode::Less ); break;
  888. case Token::Greater: d->codes.append( Opcode::Greater ); break;
  889. // NotEqual is Equal, followed by Not
  890. case Token::NotEqual:
  891. d->codes.append( Opcode::Equal );
  892. d->codes.append( Opcode::Not );
  893. break;
  894. // LessOrEqual is Greater, followed by Not
  895. case Token::LessEqual:
  896. d->codes.append( Opcode::Greater );
  897. d->codes.append( Opcode::Not );
  898. break;
  899. // GreaterOrEqual is Less, followed by Not
  900. case Token::GreaterEqual:
  901. d->codes.append( Opcode::Less );
  902. d->codes.append( Opcode::Not );
  903. break;
  904. default: break;
  905. };
  906. }
  907. }
  908. // rule for unary operator: (op1) (op2) X -> (op1) X
  909. // conditions: op2 is unary, token is not '('
  910. // action: push (op2) to result
  911. // e.g. "* - 2" becomes "*"
  912. if( !ruleFound )
  913. if( token.asOperator() != Token::LeftPar )
  914. if( syntaxStack.itemCount() >= 3 )
  915. {
  916. Token x = syntaxStack.top();
  917. Token op2 = syntaxStack.top( 1 );
  918. Token op1 = syntaxStack.top( 2 );
  919. if( !x.isOperator() )
  920. if( op1.isOperator() )
  921. if( op2.isOperator() )
  922. if( ( op2.asOperator() == Token::Plus ) ||
  923. ( op2.asOperator() == Token::Minus ) )
  924. {
  925. ruleFound = true;
  926. syntaxStack.pop();
  927. syntaxStack.pop();
  928. syntaxStack.push( x );
  929. if( op2.asOperator() == Token::Minus )
  930. d->codes.append( Opcode( Opcode::Neg ) );
  931. }
  932. }
  933. // auxilary rule for unary operator: (op) X -> X
  934. // conditions: op is unary, op is first in syntax stack, token is not '('
  935. // action: push (op) to result
  936. if( !ruleFound )
  937. if( token.asOperator() != Token::LeftPar )
  938. if( syntaxStack.itemCount() == 2 )
  939. {
  940. Token x = syntaxStack.top();
  941. Token op = syntaxStack.top( 1 );
  942. if( !x.isOperator() )
  943. if( op.isOperator() )
  944. if( ( op.asOperator() == Token::Plus ) ||
  945. ( op.asOperator() == Token::Minus ) )
  946. {
  947. ruleFound = true;
  948. syntaxStack.pop();
  949. syntaxStack.pop();
  950. syntaxStack.push( x );
  951. if( op.asOperator() == Token::Minus )
  952. d->codes.append( Opcode( Opcode::Neg ) );
  953. }
  954. }
  955. if( !ruleFound ) break;
  956. }
  957. // can't apply rules anymore, push the token
  958. if( token.asOperator() != Token::Percent )
  959. syntaxStack.push( token );
  960. }
  961. }
  962. // syntaxStack must left only one operand and end-of-formula (i.e. InvalidOp)
  963. d->valid = false;
  964. if( syntaxStack.itemCount() == 2 )
  965. if( syntaxStack.top().isOperator() )
  966. if( syntaxStack.top().asOperator() == Token::InvalidOp )
  967. if( !syntaxStack.top(1).isOperator() )
  968. d->valid = true;
  969. // bad parsing ? clean-up everything
  970. if( !d->valid )
  971. {
  972. d->constants.clear();
  973. d->codes.clear();
  974. }
  975. }
  976. bool Formula::isNamedArea( const TQString& expr ) const
  977. {
  978. TQString tokenText( expr );
  979. // check for named areas ...
  980. if (d->sheet) {
  981. const TQValueList<Reference> areas = d->sheet->doc()->listArea();
  982. TQValueList<Reference>::const_iterator it;
  983. for (it = areas.begin(); it != areas.end(); ++it) {
  984. if ((*it).ref_name.lower() == tokenText.lower()) {
  985. // we got a named area
  986. return true;
  987. }
  988. }
  989. }
  990. return false;
  991. }
  992. // Evaluates the formula, returns the result.
  993. struct stackEntry {
  994. void reset () { row1 = col1 = row2 = col2 = -1; };
  995. Value val;
  996. int row1, col1, row2, col2;
  997. };
  998. Value Formula::eval() const
  999. {
  1000. TQValueStack<stackEntry> stack;
  1001. stackEntry entry;
  1002. unsigned index;
  1003. Value val1, val2;
  1004. TQString c;
  1005. TQValueVector<Value> args;
  1006. Sheet *sheet = 0;
  1007. ValueParser* parser = 0;
  1008. ValueConverter* converter = 0;
  1009. ValueCalc* calc = 0;
  1010. if (d->sheet)
  1011. {
  1012. sheet = d->sheet;
  1013. converter = sheet->doc()->converter();
  1014. calc = sheet->doc()->calc();
  1015. }
  1016. else
  1017. {
  1018. parser = new ValueParser( TDEGlobal::locale() );
  1019. converter = new ValueConverter( parser );
  1020. calc = new ValueCalc( converter );
  1021. }
  1022. Function* function;
  1023. FuncExtra fe;
  1024. fe.mycol = fe.myrow = 0;
  1025. if (d->cell) {
  1026. fe.mycol = d->cell->column();
  1027. fe.myrow = d->cell->row();
  1028. }
  1029. if( d->dirty )
  1030. {
  1031. Tokens tokens = scan( d->expression );
  1032. d->valid = tokens.valid();
  1033. if( tokens.valid() )
  1034. compile( tokens );
  1035. }
  1036. if( !d->valid )
  1037. return Value::errorVALUE();
  1038. for( unsigned pc = 0; pc < d->codes.count(); pc++ )
  1039. {
  1040. Value ret; // for the function caller
  1041. Opcode& opcode = d->codes[pc];
  1042. index = opcode.index;
  1043. switch( opcode.type )
  1044. {
  1045. // no operation
  1046. case Opcode::Nop:
  1047. break;
  1048. // load a constant, push to stack
  1049. case Opcode::Load:
  1050. entry.reset();
  1051. entry.val = d->constants[index];
  1052. stack.push (entry);
  1053. break;
  1054. // unary operation
  1055. case Opcode::Neg:
  1056. entry.reset();
  1057. entry.val = stack.pop().val;
  1058. if (!entry.val.isError()) // do nothing if we got an error
  1059. entry.val = calc->mul (entry.val, -1);
  1060. stack.push (entry);
  1061. break;
  1062. // binary operation: take two values from stack, do the operation,
  1063. // push the result to stack
  1064. case Opcode::Add:
  1065. entry.reset();
  1066. val2 = stack.pop().val;
  1067. val1 = stack.pop().val;
  1068. val2 = calc->add( val1, val2 );
  1069. entry.reset();
  1070. entry.val = val2;
  1071. stack.push (entry);
  1072. break;
  1073. case Opcode::Sub:
  1074. val2 = stack.pop().val;
  1075. val1 = stack.pop().val;
  1076. val2 = calc->sub( val1, val2 );
  1077. entry.reset();
  1078. entry.val = val2;
  1079. stack.push (entry);
  1080. break;
  1081. case Opcode::Mul:
  1082. val2 = stack.pop().val;
  1083. val1 = stack.pop().val;
  1084. val2 = calc->mul( val1, val2 );
  1085. entry.reset();
  1086. entry.val = val2;
  1087. stack.push (entry);
  1088. break;
  1089. case Opcode::Div:
  1090. val2 = stack.pop().val;
  1091. val1 = stack.pop().val;
  1092. val2 = calc->div( val1, val2 );
  1093. entry.reset();
  1094. entry.val = val2;
  1095. stack.push (entry);
  1096. break;
  1097. case Opcode::Pow:
  1098. val2 = stack.pop().val;
  1099. val1 = stack.pop().val;
  1100. val2 = calc->pow( val1, val2 );
  1101. entry.reset();
  1102. entry.val = val2;
  1103. stack.push (entry);
  1104. break;
  1105. // string concatenation
  1106. case Opcode::Concat:
  1107. val1 = converter->asString (stack.pop().val);
  1108. val2 = converter->asString (stack.pop().val);
  1109. if (val1.isError() || val2.isError())
  1110. val1 = Value::errorVALUE();
  1111. else
  1112. val1.setValue( val2.asString().append( val1.asString() ) );
  1113. entry.reset();
  1114. entry.val = val1;
  1115. stack.push (entry);
  1116. break;
  1117. // logical not
  1118. case Opcode::Not:
  1119. val1 = converter->asBoolean (stack.pop().val);
  1120. if( val1.isError() )
  1121. val1 = Value::errorVALUE();
  1122. else
  1123. val1.setValue( !val1.asBoolean() );
  1124. entry.reset();
  1125. entry.val = val1;
  1126. stack.push (entry);
  1127. break;
  1128. // comparison
  1129. case Opcode::Equal:
  1130. val1 = stack.pop().val;
  1131. val2 = stack.pop().val;
  1132. if( !val1.allowComparison( val2 ) )
  1133. val1 = Value::errorNA();
  1134. else if( val2.compare( val1 ) == 0 )
  1135. val1 = Value (true);
  1136. else
  1137. val1 = Value (false);
  1138. entry.reset();
  1139. entry.val = val1;
  1140. stack.push (entry);
  1141. break;
  1142. // less than
  1143. case Opcode::Less:
  1144. val1 = stack.pop().val;
  1145. val2 = stack.pop().val;
  1146. if( !val1.allowComparison( val2 ) )
  1147. val1 = Value::errorNA();
  1148. else if( val2.compare( val1 ) < 0 )
  1149. val1 = Value (true);
  1150. else
  1151. val1 = Value (false);
  1152. entry.reset();
  1153. entry.val = val1;
  1154. stack.push (entry);
  1155. break;
  1156. // greater than
  1157. case Opcode::Greater:
  1158. val1 = stack.pop().val;
  1159. val2 = stack.pop().val;
  1160. if( !val1.allowComparison( val2 ) )
  1161. val1 = Value::errorNA();
  1162. else if( val2.compare( val1 ) > 0 )
  1163. val1 = Value (true);
  1164. else
  1165. val1 = Value (false);
  1166. entry.reset();
  1167. entry.val = val1;
  1168. stack.push (entry);
  1169. break;
  1170. case Opcode::Cell:
  1171. c = d->constants[index].asString();
  1172. val1 = Value::empty();
  1173. entry.reset();
  1174. if (sheet)
  1175. {
  1176. Point cell (c, sheet->workbook(), sheet);
  1177. if (cell.isValid())
  1178. {
  1179. val1 = cell.sheet()->value (cell.column(), cell.row());
  1180. // store the reference, so we can use it within functions
  1181. entry.col1 = entry.col2 = cell.column();
  1182. entry.row1 = entry.row2 = cell.row();
  1183. }
  1184. }
  1185. entry.val = val1;
  1186. stack.push (entry);
  1187. break;
  1188. case Opcode::Range:
  1189. c = d->constants[index].asString();
  1190. val1 = Value::empty();
  1191. entry.reset();
  1192. if (sheet)
  1193. {
  1194. Range range (c, sheet->workbook(), sheet);
  1195. if (range.isValid())
  1196. {
  1197. val1 = range.sheet()->valueRange (range.startCol(), range.startRow(),
  1198. range.endCol(), range.endRow());
  1199. // store the reference, so we can use it within functions
  1200. entry.col1 = range.startCol();
  1201. entry.row1 = range.startRow();
  1202. entry.col2 = range.endCol();
  1203. entry.row2 = range.endRow();
  1204. }
  1205. }
  1206. entry.val = val1;
  1207. stack.push (entry);
  1208. break;
  1209. case Opcode::Ref:
  1210. val1 = d->constants[index];
  1211. entry.reset();
  1212. entry.val = val1;
  1213. stack.push (entry);
  1214. break;
  1215. // calling function
  1216. case Opcode::Function:
  1217. if( stack.count() < index )
  1218. // (Tomas) umm, how could that be ? I mean, the index value
  1219. // is computed from the stack *confused*
  1220. return Value::errorVALUE(); // not enough arguments
  1221. args.clear();
  1222. fe.ranges.clear ();
  1223. fe.ranges.reserve (index);
  1224. fe.sheet = sheet;
  1225. for( ; index; index-- )
  1226. {
  1227. stackEntry e = stack.pop();
  1228. args.insert (args.begin(), e.val);
  1229. // TODO: create and fill a FunctionExtra object, if needed
  1230. // problem: we don't know if we need it, as we don't have the
  1231. // fuction name yet ...
  1232. fe.ranges[index - 1].col1 = e.col1;
  1233. fe.ranges[index - 1].row1 = e.row1;
  1234. fe.ranges[index - 1].col2 = e.col2;
  1235. fe.ranges[index - 1].row2 = e.row2;
  1236. }
  1237. // function name as string value
  1238. val1 = converter->asString (stack.pop().val);
  1239. if( val1.isError() )
  1240. return Value::errorVALUE();
  1241. function = FunctionRepository::self()->function ( val1.asString() );
  1242. if( !function )
  1243. return Value::errorVALUE(); // no such function
  1244. ret = function->exec (args, calc, &fe);
  1245. entry.reset();
  1246. entry.val = ret;
  1247. stack.push (entry);
  1248. break;
  1249. default:
  1250. break;
  1251. }
  1252. }
  1253. if (!d->sheet) {
  1254. delete parser;
  1255. delete converter;
  1256. delete calc;
  1257. }
  1258. // more than one value in stack ? unsuccesful execution...
  1259. if( stack.count() != 1 )
  1260. return Value::errorVALUE();
  1261. return stack.pop().val;
  1262. }
  1263. // Debugging aid
  1264. TQString Formula::dump() const
  1265. {
  1266. TQString result;
  1267. if( d->dirty )
  1268. {
  1269. Tokens tokens = scan( d->expression );
  1270. compile( tokens );
  1271. }
  1272. result = TQString("Expression: [%1]\n").arg( d->expression );
  1273. #if 0
  1274. Value value = eval();
  1275. result.append( TQString("Result: %1\n").arg(
  1276. converter->asString(value).asString() ) );
  1277. #endif
  1278. result.append(" Constants:\n");
  1279. for( unsigned c = 0; c < d->constants.count(); c++ )
  1280. {
  1281. TQString vtext;
  1282. Value val = d->constants[c];
  1283. if( val.isString() ) vtext = TQString("[%1]").arg( val.asString() );
  1284. else if( val.isNumber() ) vtext = TQString("%1").arg( val.asFloat() );
  1285. else if( val.isBoolean() ) vtext = TQString("%1").arg( val.asBoolean() ? "True":"False");
  1286. else if( val.isError() ) vtext = "error";
  1287. else vtext = "???";
  1288. result += TQString(" #%1 = %2\n").arg(c).arg( vtext );
  1289. }
  1290. result.append("\n");
  1291. result.append(" Code:\n");
  1292. for( unsigned i = 0; i < d->codes.count(); i++ )
  1293. {
  1294. TQString ctext;
  1295. switch( d->codes[i].type )
  1296. {
  1297. case Opcode::Load: ctext = TQString("Load #%1").arg( d->codes[i].index ); break;
  1298. case Opcode::Ref: ctext = TQString("Ref #%1").arg( d->codes[i].index ); break;
  1299. case Opcode::Function: ctext = TQString("Function (%1)").arg( d->codes[i].index ); break;
  1300. case Opcode::Add: ctext = "Add"; break;
  1301. case Opcode::Sub: ctext = "Sub"; break;
  1302. case Opcode::Mul: ctext = "Mul"; break;
  1303. case Opcode::Div: ctext = "Div"; break;
  1304. case Opcode::Neg: ctext = "Neg"; break;
  1305. case Opcode::Concat: ctext = "Concat"; break;
  1306. case Opcode::Pow: ctext = "Pow"; break;
  1307. case Opcode::Equal: ctext = "Equal"; break;
  1308. case Opcode::Not: ctext = "Not"; break;
  1309. case Opcode::Less: ctext = "Less"; break;
  1310. case Opcode::Greater: ctext = "Greater"; break;
  1311. default: ctext = "Unknown"; break;
  1312. }
  1313. result.append( " " ).append( ctext ).append("\n");
  1314. }
  1315. return result;
  1316. }
  1317. TQTextStream& operator<<( TQTextStream& ts, Formula formula )
  1318. {
  1319. ts << formula.dump();
  1320. return ts;
  1321. }