1	/* This file is part of the KDE project
2	Copyright (C) 2008-2010 Marijn Kruisselbrink <mkruisselbrink@kde.org>
3	Copyright (C) 2003,2004 Ariya Hidayat <ariya@kde.org>
4	Copyright (C) 2005 Tomas Mecir <mecirt@gmail.com>
5
6	This library is free software; you can redistribute it and/or
7	modify it under the terms of the GNU Library General Public
8	License as published by the Free Software Foundation; only
9	version 2 of the License.
10
11	This library is distributed in the hope that it will be useful,
12	but WITHOUT ANY WARRANTY; without even the implied warranty of
13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14	Library General Public License for more details.
15
16	You should have received a copy of the GNU Library General Public License
17	along with this library; see the file COPYING.LIB. If not, write to
18	the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19	Boston, MA 02110-1301, USA.
20	*/
21
22	#include "Formula.h"
23
24	#include "CalculationSettings.h"
25	#include "Cell.h"
26	#include "CellStorage.h"
27	#include "Function.h"
28	#include "FunctionRepository.h"
29	#include "Sheet.h"
30	#include "Map.h"
31	#include "NamedAreaManager.h"
32	#include "Region.h"
33	#include "Value.h"
34	#include "Util.h"
35
36	#include "ValueCalc.h"
37	#include "ValueConverter.h"
38	#include "ValueParser.h"
39
40	#include <limits.h>
41
42	#include <QStack>
43	#include <QString>
44	#include <QTextStream>
45
46	#include <klocale.h>
47
48	#define CALLIGRA_SHEETS_UNICODE_OPERATORS
49
50	/*
51	To understand how this formula engine works, please refer to the documentation
52	in file DESIGN.html.
53
54	Useful references:
55	- "Principles of Compiler Design", A.V.Aho, J.D.Ullman, Addison Wesley, 1978
56	- "Writing Interactive Compilers and Interpreters", P.J. Brown,
57	John Wiley and Sons, 1979.
58	- "The Theory and Practice of Compiler Writing", J.Tremblay, P.G.Sorenson,
59	McGraw-Hill, 1985.
60	- "The Java(TM) Virtual Machine Specification", T.Lindholm, F.Yellin,
61	Addison-Wesley, 1997.
62	- "Java Virtual Machine", J.Meyer, T.Downing, O'Reilly, 1997.
63
64	*/
65
66
67	/*
68	TODO - features:
69	- handle Intersection
70	- cell reference is made relative (absolute now)
71	- shared formula (different owner, same data)
72	- relative internal representation (independent of owner)
73	- OASIS support
74	TODO - optimizations:
75	- handle initial formula marker = (and +)
76	- reuse constant already in the pool
77	- reuse references already in the pool
78	- expression optimization (e.g. 1+2+A1 becomes 3+A1)
79	*/
80
81	namespace Calligra
82	{
83	namespace Sheets
84	{
85
86	class Opcode
87	{
88	public:
89
90	enum { Nop = 0, Load, Ref, Cell, Range, Function, Add, Sub, Neg, Mul, Div,
91	Pow, Concat, Intersect, Not, Equal, Less, Greater, Array, Union
92	};
93
94	unsigned type;
95	unsigned index;
96
97	Opcode(): type(Nop), index(0) {}
98	Opcode(unsigned t): type(t), index(0) {}
99	Opcode(unsigned t, unsigned i): type(t), index(i) {}
100	};
101
102	// used when evaluation formulas
103	struct stackEntry {
104	void reset() {
105	row1 = col1 = row2 = col2 = -1;
106	reg = Calligra::Sheets::Region();
107	regIsNamedOrLabeled = false;
108	}
109	Value val;
110	Calligra::Sheets::Region reg;
111	bool regIsNamedOrLabeled;
112	int row1, col1, row2, col2;
113	};
114
115	class Formula::Private : public QSharedData
116	{
117	public:
118	Cell cell;
119	Sheet *sheet;
120	mutable bool dirty;
121	mutable bool valid;
122	QString expression;
123	mutable QVector<Opcode> codes;
124	mutable QVector<Value> constants;
125
126	Value valueOrElement(FuncExtra &fe, const stackEntry& entry) const;
127	};
128
129	class TokenStack : public QVector<Token>
130	{
131	public:
132	TokenStack();
133	unsigned itemCount() const;
134	void push(const Token& token);
135	Token pop();
136	const Token& top();
137	const Token& top(unsigned index);
138	};
139
140	} // namespace Sheets
141	} // namespace Calligra
142
143	using namespace Calligra::Sheets;
144
145	// for null token
146	const Token Token::null;
147
148	// helper function: return operator of given token text
149	// e.g. '*' yields Operator::Asterisk, and so on
150	Token::Op Calligra::Sheets::matchOperator(const QString& text)
151	{
152	Token::Op result = Token::InvalidOp;
153
154	if (text.length() == 1) {
155	QChar p = text[0];
156	switch (p.unicode()) {
157	case '+': result = Token::Plus; break;
158	case '-': result = Token::Minus; break;
159	case '*': result = Token::Asterisk; break;
160	case '/': result = Token::Slash; break;
161	case '^': result = Token::Caret; break;
162	case ',': result = Token::Comma; break;
163	case ';': result = Token::Semicolon; break;
164	case ' ': result = Token::Intersect; break;
165	case '(': result = Token::LeftPar; break;
166	case ')': result = Token::RightPar; break;
167	case '&': result = Token::Ampersand; break;
168	case '=': result = Token::Equal; break;
169	case '<': result = Token::Less; break;
170	case '>': result = Token::Greater; break;
171	case '%': result = Token::Percent; break;
172	case '~': result = Token::Union; break;
173	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
174	case '{': result = Token::CurlyBra; break;
175	case '}': result = Token::CurlyKet; break;
176	case '|': result = Token::Pipe; break;
177	#endif
178	#ifdef CALLIGRA_SHEETS_UNICODE_OPERATORS
179	case 0x2212: result = Token::Minus; break;
180	case 0x00D7: result = Token::Asterisk; break;
181	case 0x00F7: result = Token::Slash; break;
182	case 0x2215: result = Token::Slash; break;
183	#endif
184	default : result = Token::InvalidOp; break;
185	}
186	}
187
188	if (text.length() == 2) {
189	if (text == "<>") result = Token::NotEqual;
190	if (text == "!=") result = Token::NotEqual;
191	if (text == "<=") result = Token::LessEqual;
192	if (text == ">=") result = Token::GreaterEqual;
193	if (text == "==") result = Token::Equal;
194	}
195
196	return result;
197	}
198
199	bool Calligra::Sheets::parseOperator(const QChar *&data, QChar *&out)
200	{
201	bool retval = true;
202	switch(data->unicode()) {
203	case '+':
204	case '-':
205	case '*':
206	case '/':
207	case '^':
208	case ',':
209	case ';':
210	case ' ':
211	case '(':
212	case ')':
213	case '&':
214	case '%':
215	case '~':
216	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
217	case '{':
218	case '}':
219	case '|':
220	#endif
221	#ifdef CALLIGRA_SHEETS_UNICODE_OPERATORS
222	case 0x2212:
223	case 0x00D7:
224	case 0x00F7:
225	case 0x2215:
226	#endif
227	*out = *data;
228	++out;
229	++data;
230	break;
231	case '<':
232	*out = *data;
233	++out;
234	++data;
235	if (!data->isNull()) {
236	if (*data == QChar('>', 0) || *data == QChar('=', 0)) {
237	*out = *data;
238	++out;
239	++data;
240	}
241	}
242	break;
243	case '>':
244	*out = *data;
245	++out;
246	++data;
247	if (!data->isNull() && *data == QChar('=', 0)) {
248	*out = *data;
249	++out;
250	++data;
251	}
252	break;
253	case '=':
254	*out++ = *data++;
255	if (!data->isNull() && *data == QChar('=', 0)) {
256	*out++ = *data++;
257	}
258	break;
259	case '!': {
260	const QChar * next = data + 1;
261	if (!next->isNull() && *next == QChar('=', 0)) {
262	*out = *data;
263	++out;
264	++data;
265	*out = *data;
266	++out;
267	++data;
268	}
269	else {
270	retval = false;
271	}
272	} break;
273	default:
274	retval = false;
275	break;
276	}
277	return retval;
278	}
279
280	// helper function: give operator precedence
281	// e.g. '+' is 1 while '*' is 3
282	static int opPrecedence(Token::Op op)
283	{
284	int prec = -1;
285	switch (op) {
286	case Token::Percent : prec = 8; break;
287	case Token::Caret : prec = 7; break;
288	case Token::Asterisk : prec = 5; break;
289	case Token::Slash : prec = 6; break;
290	case Token::Plus : prec = 3; break;
291	case Token::Minus : prec = 3; break;
292	case Token::Union : prec = 2; break;
293	case Token::Ampersand : prec = 2; break;
294	case Token::Intersect : prec = 2; break;
295	case Token::Equal : prec = 1; break;
296	case Token::NotEqual : prec = 1; break;
297	case Token::Less : prec = 1; break;
298	case Token::Greater : prec = 1; break;
299	case Token::LessEqual : prec = 1; break;
300	case Token::GreaterEqual : prec = 1; break;
301	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
302	// FIXME Stefan: I don't know whether zero is right for this case. :-(
303	case Token::CurlyBra : prec = 0; break;
304	case Token::CurlyKet : prec = 0; break;
305	case Token::Pipe : prec = 0; break;
306	#endif
307	case Token::Semicolon : prec = 0; break;
308	case Token::RightPar : prec = 0; break;
309	case Token::LeftPar : prec = -1; break;
310	default: prec = -1; break;
311	}
312	return prec;
313	}
314
315	// helper function
316	static Value tokenAsValue(const Token& token)
317	{
318	Value value;
319	if (token.isBoolean()) value = Value(token.asBoolean());
320	else if (token.isInteger()) value = Value(token.asInteger());
321	else if (token.isFloat()) value = Value(token.asFloat());
322	else if (token.isString()) value = Value(token.asString());
323	else if (token.isError()) {
324	const QString error = token.asError();
325	if (error == Value::errorCIRCLE().errorMessage())
326	value = Value::errorCIRCLE();
327	else if (error == Value::errorDEPEND().errorMessage())
328	value = Value::errorDEPEND();
329	else if (error == Value::errorDIV0().errorMessage())
330	value = Value::errorDIV0();
331	else if (error == Value::errorNA().errorMessage())
332	value = Value::errorNA();
333	else if (error == Value::errorNAME().errorMessage())
334	value = Value::errorNAME();
335	else if (error == Value::errorNUM().errorMessage())
336	value = Value::errorNUM();
337	else if (error == Value::errorNULL().errorMessage())
338	value = Value::errorNULL();
339	else if (error == Value::errorPARSE().errorMessage())
340	value = Value::errorPARSE();
341	else if (error == Value::errorREF().errorMessage())
342	value = Value::errorREF();
343	else if (error == Value::errorVALUE().errorMessage())
344	value = Value::errorVALUE();
345	else {
346	value = Value(Value::Error);
347	value.setError(error);
348	}
349	}
350	return value;
351	}
352
353	/**********************
354	Token
355	**********************/
356
357	// creates a token
358	Token::Token(Type type, const QString& text, int pos)
359	: m_type(type)
360	, m_text(text)
361	, m_pos(pos)
362	{
363	// the detach is needed as we manipulate the string we use as input afterwards
364	// by writing to QChar * data point which does nto detach automatically.
365	m_text.detach();
366	}
367
368	// copy constructor
369	Token::Token(const Token& token)
370	: m_type(token.m_type)
371	, m_text(token.m_text)
372	, m_pos(token.m_pos)
373	{
374	}
375
376	// assignment operator
377	Token& Token::operator=(const Token & token)
378	{
379	m_type = token.m_type;
380	m_text = token.m_text;
381	m_pos = token.m_pos;
382	return *this;
383	}
384
385	bool Token::asBoolean() const
386	{
387	if (!isBoolean()) return false;
388	return m_text.toLower() == "true";
389	// FIXME check also for i18n version
390	}
391
392	qint64 Token::asInteger() const
393	{
394	if (isInteger()) return m_text.toLongLong();
395	else return 0;
396	}
397
398	double Token::asFloat() const
399	{
400	if (isFloat()) return m_text.toDouble();
401	else return 0.0;
402	}
403
404	QString Token::asString() const
405	{
406	if (isString()) return m_text.mid(1, m_text.length() - 2);
407	else return QString();
408	}
409
410	QString Token::asError() const
411	{
412	if (isError())
413	return m_text;
414	else
415	return QString();
416	}
417
418	Token::Op Token::asOperator() const
419	{
420	if (isOperator()) return matchOperator(m_text);
421	else return InvalidOp;
422	}
423
424	QString Token::sheetName() const
425	{
426	if (!isCell() && !isRange()) return QString();
427	int i = m_text.indexOf('!');
428	if (i < 0) return QString();
429	QString sheet = m_text.left(i);
430	return sheet;
431	}
432
433	QString Token::description() const
434	{
435	QString desc;
436
437	switch (m_type) {
438	case Boolean: desc = "Boolean"; break;
439	case Integer: desc = "Integer"; break;
440	case Float: desc = "Float"; break;
441	case String: desc = "String"; break;
442	case Identifier: desc = "Identifier"; break;
443	case Cell: desc = "Cell"; break;
444	case Range: desc = "Range"; break;
445	case Operator: desc = "Operator"; break;
446	case Error: desc = "Error"; break;
447	default: desc = "Unknown"; break;
448	}
449
450	while (desc.length() < 10) desc.prepend(' ');
451	desc.prepend(" ");
452	desc.prepend(QString::number(m_pos));
453	desc.append(" : ").append(m_text);
454
455	return desc;
456	}
457
458
459	/**********************
460	TokenStack
461	**********************/
462
463	TokenStack::TokenStack(): QVector<Token>()
464	{
465	}
466
467	unsigned TokenStack::itemCount() const
468	{
469	return size();
470	}
471
472	void TokenStack::push(const Token& token)
473	{
474	append(token);
475	}
476
477	Token TokenStack::pop()
478	{
479	if (!isEmpty()) {
480	Token token = last();
481	pop_back();
482	return token;
483	}
484	return Token();
485	}
486
487	const Token& TokenStack::top()
488	{
489	return top(0);
490	}
491
492	const Token& TokenStack::top(unsigned index)
493	{
494	unsigned top = size();
495	if (top > index)
496	return at(top - index - 1);
497	return Token::null;
498	}
499
500
501	/**********************
502	FormulaPrivate
503	**********************/
504
505	// helper function: return true for valid identifier character
506	bool Calligra::Sheets::isIdentifier(QChar ch)
507	{
508	switch(ch.unicode()) {
509	case '_':
510	case '$':
511	case '.':
512	return true;
513	default:
514	return ch.isLetter();
515	}
516	}
517
518
519
520
521	/**********************
522	Formula
523	**********************/
524
525	// Constructor
526
527	Formula::Formula(Sheet *sheet, const Cell& cell)
528	: d(new Private)
529	{
530	d->cell = cell;
531	d->sheet = sheet;
532	clear();
533	}
534
535	Formula::Formula(Sheet *sheet)
536	: d(new Private)
537	{
538	d->cell = Cell();
539	d->sheet = sheet;
540	clear();
541	}
542
543	Formula::Formula()
544	: d(new Private)
545	{
546	d->cell = Cell();
547	d->sheet = 0;
548	clear();
549	}
550
551	Formula Formula::empty()
552	{
553	static Formula f;
554	return f;
555	}
556
557	Formula::Formula(const Formula& other)
558	: d(other.d)
559	{
560	}
561
562	// Destructor
563
564	Formula::~Formula()
565	{
566	}
567
568	const Cell& Formula::cell() const
569	{
570	return d->cell;
571	}
572
573	Sheet* Formula::sheet() const
574	{
575	return d->sheet;
576	}
577
578	// Sets a new expression for this formula.
579	// note that both the real lex and parse processes will happen later on
580	// when needed (i.e. "lazy parse"), for example during formula evaluation.
581
582	void Formula::setExpression(const QString& expr)
583	{
584	d->expression = expr;
585	d->dirty = true;
586	d->valid = false;
587	}
588
589	// Returns the expression associated with this formula.
590
591	QString Formula::expression() const
592	{
593	return d->expression;
594	}
595
596	// Returns the validity of the formula.
597	// note: empty formula is always invalid.
598
599	bool Formula::isValid() const
600	{
601	if (d->dirty) {
602	KLocale* locale = !d->cell.isNull() ? d->cell.locale() : 0;
603	if ((!locale) && d->sheet)
604	locale = d->sheet->map()->calculationSettings()->locale();
605	Tokens tokens = scan(d->expression, locale);
606
607	if (tokens.valid())
608	compile(tokens);
609	else
610	d->valid = false;
611	}
612	return d->valid;
613	}
614
615	// Clears everything, also mark the formula as invalid.
616
617	void Formula::clear()
618	{
619	d->expression.clear();
620	d->dirty = true;
621	d->valid = false;
622	d->constants.clear();
623	d->codes.clear();
624	}
625
626	// Returns list of token for the expression.
627	// this triggers again the lexical analysis step. it is however preferable
628	// (even when there's small performance penalty) because otherwise we need to
629	// store parsed tokens all the time which serves no good purpose.
630
631	Tokens Formula::tokens() const
632	{
633	KLocale* locale = !d->cell.isNull() ? d->cell.locale() : 0;
634	if ((!locale) && d->sheet)
635	locale = d->sheet->map()->calculationSettings()->locale();
636	return scan(d->expression, locale);
637	}
638
639	Tokens Formula::scan(const QString &expr, const KLocale* locale) const
640	{
641	// parsing state
642	enum { Start, Finish, InNumber, InDecimal, InExpIndicator, InExponent,
643	InString, InIdentifier, InCell, InRange, InSheetOrAreaName, InError
644	} state;
645
646	// use locale settings if specified
647	QString thousand = locale ? locale->thousandsSeparator() : "";
648	QString decimal = locale ? locale->decimalSymbol() : ".";
649
650	const QChar *data = expr.constData();
651
652	Tokens tokens;
653	if (data->isNull() || *data != QChar('=', 0)) {
654	return tokens;
655	}
656	tokens.reserve(50);
657
658	++data;
659	const QChar * const start = data;
660	const QChar * const end = start + expr.length();
661	const QChar *tokenStart = data;
662	const QChar *cellStart = data;
663
664	state = Start;
665	bool parseError = false;
666
667	int length = expr.length() * 1.1; // TODO check if that is needed at all
668	QString token(length, QChar());
669	token.reserve(length); // needed to not realloc at the resize at the end
670	QChar * out = token.data();
671	QChar * const outStart = token.data();
672
673	while (state != Finish && data < end) {
674	switch (state) {
675	case Start:
676	tokenStart = data;
677	// Whitespaces can be used as intersect-operator for two arrays.
678	if (data->isSpace()) {
679	++data;
680	}
681	// check for number
682	else if (data->isDigit()) {
683	state = InNumber;
684	*out++ = *data++;
685	}
686	// terminator character
687	else if (data->isNull()) {
688	state = Finish;
689	}
690	else {
691	switch (data->unicode()) {
692	case '"': // a string ?
693	*out++ = *data++;
694	state = InString;
695	break;
696	case '\'': // aposthrophe (') marks sheet name for 3-d cell, e.g 'Sales Q3'!A4, or a named range
697	++data;
698	state = InSheetOrAreaName;
699	break;
700	case '#': // error value?
701	*out++ = *data++;
702	state = InError;
703	break;
704	default:
705	// decimal dot ?
706	if (*data == decimal[0]) {
707	*out++ = *data++;
708	state = InDecimal;
709	}
710	// beginning with alphanumeric ?
711	// could be identifier, cell, range, or function...
712	else if (isIdentifier(*data)) {
713	*out++ = *data++;
714	state = InIdentifier;
715	}
716	else {
717	// look for operator match
718	if (parseOperator(data, out)) {
719	token.resize(out - outStart);
720	tokens.append(Token(Token::Operator, token, tokenStart - start));
721	token.resize(length);
722	out = outStart;
723	}
724	else {
725	// not matched an operator, add an Unknown token and remember we had a parse error
726	parseError = true;
727	*out++ = *data++;
728	token.resize(out - outStart);
729	tokens.append(Token(Token::Unknown, token, tokenStart - start));
730	token.resize(length);
731	out = outStart;
732	}
733	}
734	break;
735	}
736	}
737	break;
738	case InIdentifier:
739	// consume as long as alpha, dollar sign, underscore, or digit
740	if (isIdentifier(*data) || data->isDigit()) {
741	*out = *data;
742	++out;
743	++data;
744	}
745	// a '!' ? then this must be sheet name, e.g "Sheet4!", unless the next character is '='
746	else if (*data == QChar('!', 0) && !(data + 1)->isNull() && *(data + 1) != QChar('=', 0)) {
747	*out++ = *data++;
748	cellStart = out;
749	state = InCell;
750	}
751	// a '(' ? then this must be a function identifier
752	else if (*data == QChar('(', 0)) {
753	token.resize(out - outStart);
754	tokens.append(Token(Token::Identifier, token, tokenStart - start));
755	token.resize(length);
756	out = outStart;
757	state = Start;
758	}
759	// we're done with identifier
760	else {
761	*out = QChar();
762	// check for cell reference, e.g A1, VV123, ...
763	if (Util::isCellReference(token)) {
764	// so up to now we've got something like A2 or Sheet2!F4
765	// check for range reference
766	if (*data == QChar(':', 0)) {
767	*out++ = *data++;
768	state = InRange;
769	}
770	// we're done with cell reference
771	else {
772	token.resize(out - outStart);
773	tokens.append(Token(Token::Cell, token, tokenStart - start));
774	token.resize(length);
775	out = outStart;
776	state = Start;
777	}
778	}
779	else {
780	token.resize(out - outStart);
781	if (isNamedArea(token)) {
782	tokens.append(Token(Token::Range, token, tokenStart - start));
783	}
784	else {
785	tokens.append(Token(Token::Identifier, token, tokenStart - start));
786	}
787	token.resize(length);
788	out = outStart;
789	state = Start;
790	}
791	}
792	break;
793	case InCell:
794	// consume as long as alpha, dollar sign, underscore, or digit
795	if (isIdentifier(*data) || data->isDigit()) {
796	*out++ = *data++;
797	}
798	else {
799	*out = QChar();
800	// check if it's a cell ref like A32, not named area
801	if (!Util::isCellReference(token, cellStart - outStart)) {
802	// test failed, means we have something like "Sheet2!TotalSales"
803	// and not "Sheet2!A2"
804	// thus, assume so far that it's a named area
805	token.resize(out - outStart);
806	tokens.append(Token(Token::Range, token, tokenStart - start));
807	token.resize(length);
808	out = outStart;
809	state = Start;
810	}
811	else {
812	// so up to now we've got something like A2 or Sheet2!F4
813	// check for range reference
814	if (*data == QChar(':', 0)) {
815	*out++ = *data++;
816	state = InRange;
817	}
818	else {
819	// we're done with cell reference
820	token.resize(out - outStart);
821	tokens.append(Token(Token::Cell, token, tokenStart - start));
822	token.resize(length);
823	out = outStart;
824	state = Start;
825	}
826	}
827	}
828	break;
829	case InRange:
830	// consume as long as alpha, dollar sign, underscore, or digit or !
831	if (isIdentifier(*data) || data->isDigit() || *data == QChar('!', 0)) {
832	*out++ = *data++;
833	}
834	// we're done with range reference
835	else {
836	token.resize(out - outStart);
837	tokens.append(Token(Token::Range, token, tokenStart - start));
838	token.resize(length);
839	out = outStart;
840	state = Start;
841	}
842	break;
843	case InSheetOrAreaName:
844	// consume until '
845	if (data->isNull()) {
846	parseError = true;
847	token.resize(out - outStart);
848	tokens.append(Token(Token::Unknown, '\'' + token + '\'', tokenStart - start));
849	state = Start;
850	}
851	else if (*data != QChar('\'', 0)) {
852	*out++ = *data++;
853	}
854	else {
855	// eat the aposthrophe itself
856	++data;
857	// must be followed by '!' to be sheet name
858	if (!data->isNull() && *data == QChar('!', 0)) {
859	*out++ = *data++;
860	cellStart = out;
861	state = InCell;
862	}
863	else {
864	token.resize(out - outStart);
865	if (isNamedArea(token)) {
866	tokens.append(Token(Token::Range, token, tokenStart - start));
867	}
868	else {
869	// for compatibility with oocalc (and the openformula spec), don't parse single-quoted
870	// text as an identifier, instead add an Unknown token and remember we had an error
871	parseError = true;
872	tokens.append(Token(Token::Unknown, '\'' + token + '\'', tokenStart - start));
873	}
874	token.resize(length);
875	out = outStart;
876	state = Start;
877	}
878	}
879	break;
880	case InNumber:
881	// consume as long as it's digit
882	if (data->isDigit()) {
883	*out++ = *data++;
884	}
885	// skip thousand separator
886	else if (!thousand.isEmpty() && (*data == thousand[0])) {
887	++data;
888	}
889	// convert decimal separator to '.', also support '.' directly
890	// we always support '.' because of bug #98455
891	else if ((!decimal.isEmpty() && (*data == decimal[0])) || *data == QChar('.', 0)) {
892	*out++ = QChar('.', 0);
893	++data;
894	state = InDecimal;
895	}
896	// exponent ?
897	else if (*data == QChar('E', 0) || *data == QChar('e', 0)) {
898	*out++ = QChar('E', 0);
899	++data;
900	state = InExpIndicator;
901	}
902	// reference sheet delimiter?
903	else if (*data == QChar('!', 0)) {
904	*out++ = *data++;
905	cellStart = out;
906	state = InCell;
907	}
908	// identifier?
909	else if (isIdentifier(*data)) {
910	// has to be a sheet or area name then
911	*out++ = *data++;
912	state = InIdentifier;
913	}
914	// we're done with integer number
915	else {
916	token.resize(out - outStart);
917	tokens.append(Token(Token::Integer, token, tokenStart - start));
918	token.resize(length);
919	out = outStart;
920	state = Start;
921	}
922	break;
923	case InDecimal:
924	// consume as long as it's digit
925	if (data->isDigit()) {
926	*out++ = *data++;
927	}
928	// exponent ?
929	else if (*data == QChar('E', 0) || *data == QChar('e', 0)) {
930	*out++ = QChar('E', 0);
931	++data;
932	state = InExpIndicator;
933	}
934	// we're done with floating-point number
935	else {
936	token.resize(out - outStart);
937	tokens.append(Token(Token::Float, token, tokenStart - start));
938	token.resize(length);
939	out = outStart;
940	state = Start;
941	}
942	break;
943	case InExpIndicator:
944	// possible + or - right after E, e.g 1.23E+12 or 4.67E-8
945	if (*data == QChar('+', 0) || *data == QChar('-', 0)) {
946	*out++ = *data++;
947	}
948	// consume as long as it's digit
949	else if (data->isDigit()) {
950	*out++ = *data++;
951	state = InExponent;
952	}
953	// invalid thing here
954	else {
955	parseError = true;
956	token.resize(out - outStart);
957	tokens.append(Token(Token::Unknown, token, tokenStart - start));
958	token.resize(length);
959	out = outStart;
960	state = Start;
961	}
962	break;
963	case InExponent:
964	// consume as long as it's digit
965	if (data->isDigit()) {
966	*out++ = *data++;
967	}
968	// we're done with floating-point number
969	else {
970	token.resize(out - outStart);
971	tokens.append(Token(Token::Float, token, tokenStart - start));
972	token.resize(length);
973	out = outStart;
974	state = Start;
975	}
976	break;
977	case InString:
978	// consume until "
979	if (*data != QChar('"', 0)) {
980	*out++ = *data++;
981	}
982	else {
983	*out++ = *data++;
984	// check for escaped ""
985	if (data->isNull() || *data != QChar('"', 0)) {
986	token.resize(out - outStart);
987	tokens.append(Token(Token::String, token, tokenStart - start));
988	token.resize(length);
989	out = outStart;
990	state = Start;
991	}
992	else {
993	++data;
994	}
995	}
996	break;
997	case InError: {
998	ushort c = data->unicode();
999	switch (c) {
1000	case '!':
1001	case '?':
1002	// TODO check if there is at least one char that needs to be there
1003	*out++ = *data++;
1004	token.resize(out - outStart);
1005	tokens.append(Token(Token::Error, token, tokenStart - start));
1006	token.resize(length);
1007	out = outStart;
1008	state = Start;
1009	break;
1010	case '/':
1011	*out++ = *data++;
1012	if (!data->isNull()) {
1013	bool error = false;
1014	if (*data >= 'A' && *data <= 'Z') {
1015	*out++ = *data++;
1016	}
1017	else if (*data >= '0' && *data <= '9'){
1018	*out++ = *data++;
1019	if (!data->isNull() && (*data == QChar('!', 0) || *data == QChar('?', 0))) {
1020	*out++ = *data++;
1021	}
1022	}
1023	else {
1024	error = true;
1025	}
1026	if (error) {
1027	parseError = true;
1028	token.resize(out - outStart);
1029	tokens.append(Token(Token::Unknown, token, tokenStart - start));
1030	token.resize(length);
1031	out = outStart;
1032	state = Start;
1033	}
1034	else {
1035	token.resize(out - outStart);
1036	tokens.append(Token(Token::Error, token, tokenStart - start));
1037	token.resize(length);
1038	out = outStart;
1039	state = Start;
1040	}
1041	}
1042	break;
1043	default:
1044	if ((c >= 'A' && c <= 'Z') || (c >= '0' && c<= '9')) {
1045	*out++ = *data++;
1046	}
1047	else {
1048	parseError = true;
1049	token.resize(out - outStart);
1050	tokens.append(Token(Token::Unknown, token, tokenStart - start));
1051	token.resize(length);
1052	out = outStart;
1053	state = Start;
1054	}
1055	break;
1056	}
1057	} break;
1058	default:
1059	break;
1060	}
1061	}
1062
1063	// parse error if any text remains
1064	if (data+1 < end) {
1065	tokens.append(Token(Token::Unknown, expr.mid(tokenStart - start), tokenStart - start));
1066	parseError = true;
1067	}
1068
1069	if (parseError)
1070	tokens.setValid(false);
1071	return tokens;
1072	}
1073
1074	// will affect: dirty, valid, codes, constants
1075	void Formula::compile(const Tokens& tokens) const
1076	{
1077	// initialize variables
1078	d->dirty = false;
1079	d->valid = false;
1080	d->codes.clear();
1081	d->constants.clear();
1082
1083	// sanity check
1084	if (tokens.count() == 0) return;
1085
1086	TokenStack syntaxStack;
1087	QStack<int> argStack;
1088	unsigned argCount = 1;
1089
1090	for (int i = 0; i <= tokens.count(); i++) {
1091	// helper token: InvalidOp is end-of-formula
1092	Token token = (i < tokens.count()) ? tokens[i] : Token(Token::Operator);
1093	Token::Type tokenType = token.type();
1094
1095	// unknown token is invalid
1096	if (tokenType == Token::Unknown) break;
1097
1098	// are we entering a function ?
1099	// if stack already has: id (
1100	if (syntaxStack.itemCount() >= 2) {
1101	Token par = syntaxStack.top();
1102	Token id = syntaxStack.top(1);
1103	if (par.asOperator() == Token::LeftPar)
1104	if (id.isIdentifier()) {
1105	argStack.push(argCount);
1106	argCount = 1;
1107	}
1108	}
1109
1110	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
1111	// are we entering an inline array ?
1112	// if stack already has: {
1113	if (syntaxStack.itemCount() >= 1) {
1114	Token bra = syntaxStack.top();
1115	if (bra.asOperator() == Token::CurlyBra) {
1116	argStack.push(argCount);
1117	argStack.push(1); // row count
1118	argCount = 1;
1119	}
1120	}
1121	#endif
1122
1123	// for constants, push immediately to stack
1124	// generate code to load from a constant
1125	if ((tokenType == Token::Integer) || (tokenType == Token::Float) ||
1126	(tokenType == Token::String) || (tokenType == Token::Boolean) ||
1127	(tokenType == Token::Error)) {
1128	syntaxStack.push(token);
1129	d->constants.append(tokenAsValue(token));
1130	d->codes.append(Opcode(Opcode::Load, d->constants.count() - 1));
1131	}
1132
1133	// for cell, range, or identifier, push immediately to stack
1134	// generate code to load from reference
1135	if ((tokenType == Token::Cell) || (tokenType == Token::Range) ||
1136	(tokenType == Token::Identifier)) {
1137	syntaxStack.push(token);
1138	d->constants.append(Value(token.text()));
1139	if (tokenType == Token::Cell)
1140	d->codes.append(Opcode(Opcode::Cell, d->constants.count() - 1));
1141	else if (tokenType == Token::Range)
1142	d->codes.append(Opcode(Opcode::Range, d->constants.count() - 1));
1143	else
1144	d->codes.append(Opcode(Opcode::Ref, d->constants.count() - 1));
1145	}
1146
1147	// special case for percentage
1148	if (tokenType == Token::Operator)
1149	if (token.asOperator() == Token::Percent)
1150	if (syntaxStack.itemCount() >= 1)
1151	if (!syntaxStack.top().isOperator()) {
1152	d->constants.append(Value(0.01));
1153	d->codes.append(Opcode(Opcode::Load, d->constants.count() - 1));
1154	d->codes.append(Opcode(Opcode::Mul));
1155	}
1156
1157	// for any other operator, try to apply all parsing rules
1158	if (tokenType == Token::Operator)
1159	if (token.asOperator() != Token::Percent) {
1160	// repeat until no more rule applies
1161	for (; ;) {
1162	bool ruleFound = false;
1163
1164	// rule for function arguments, if token is ; or )
1165	// id ( arg1 ; arg2 -> id ( arg
1166	if (!ruleFound)
1167	if (syntaxStack.itemCount() >= 5)
1168	if ((token.asOperator() == Token::RightPar) ||
1169	(token.asOperator() == Token::Semicolon)) {
1170	Token arg2 = syntaxStack.top();
1171	Token sep = syntaxStack.top(1);
1172	Token arg1 = syntaxStack.top(2);
1173	Token par = syntaxStack.top(3);
1174	Token id = syntaxStack.top(4);
1175	if (!arg2.isOperator())
1176	if (sep.asOperator() == Token::Semicolon)
1177	if (!arg1.isOperator())
1178	if (par.asOperator() == Token::LeftPar)
1179	if (id.isIdentifier()) {
1180	ruleFound = true;
1181	syntaxStack.pop();
1182	syntaxStack.pop();
1183	argCount++;
1184	}
1185	}
1186
1187	// rule for empty function arguments, if token is ; or )
1188	// id ( arg ; -> id ( arg
1189	if (!ruleFound)
1190	if (syntaxStack.itemCount() >= 3)
1191	if ((token.asOperator() == Token::RightPar) ||
1192	(token.asOperator() == Token::Semicolon)) {
1193	Token sep = syntaxStack.top();
1194	Token arg = syntaxStack.top(1);
1195	Token par = syntaxStack.top(2);
1196	Token id = syntaxStack.top(3);
1197	if (sep.asOperator() == Token::Semicolon)
1198	if (!arg.isOperator())
1199	if (par.asOperator() == Token::LeftPar)
1200	if (id.isIdentifier()) {
1201	ruleFound = true;
1202	syntaxStack.pop();
1203	d->constants.append(Value::null());
1204	d->codes.append(Opcode(Opcode::Load, d->constants.count() - 1));
1205	argCount++;
1206	}
1207	}
1208
1209	// rule for function last argument:
1210	// id ( arg ) -> arg
1211	if (!ruleFound)
1212	if (syntaxStack.itemCount() >= 4) {
1213	Token par2 = syntaxStack.top();
1214	Token arg = syntaxStack.top(1);
1215	Token par1 = syntaxStack.top(2);
1216	Token id = syntaxStack.top(3);
1217	if (par2.asOperator() == Token::RightPar)
1218	if (!arg.isOperator())
1219	if (par1.asOperator() == Token::LeftPar)
1220	if (id.isIdentifier()) {
1221	ruleFound = true;
1222	syntaxStack.pop();
1223	syntaxStack.pop();
1224	syntaxStack.pop();
1225	syntaxStack.pop();
1226	syntaxStack.push(arg);
1227	d->codes.append(Opcode(Opcode::Function, argCount));
1228	Q_ASSERT(!argStack.empty());
1229	argCount = argStack.empty() ? 0 : argStack.pop();
1230	}
1231	}
1232
1233	// rule for function call with parentheses, but without argument
1234	// e.g. "2*PI()"
1235	if (!ruleFound)
1236	if (syntaxStack.itemCount() >= 3) {
1237	Token par2 = syntaxStack.top();
1238	Token par1 = syntaxStack.top(1);
1239	Token id = syntaxStack.top(2);
1240	if (par2.asOperator() == Token::RightPar)
1241	if (par1.asOperator() == Token::LeftPar)
1242	if (id.isIdentifier()) {
1243	ruleFound = true;
1244	syntaxStack.pop();
1245	syntaxStack.pop();
1246	syntaxStack.pop();
1247	syntaxStack.push(Token(Token::Integer));
1248	d->codes.append(Opcode(Opcode::Function, 0));
1249	Q_ASSERT(!argStack.empty());
1250	argCount = argStack.empty() ? 0 : argStack.pop();
1251	}
1252	}
1253
1254	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
1255	// rule for inline array elements, if token is ; or | or }
1256	// { arg1 ; arg2 -> { arg
1257	if (!ruleFound)
1258	if (syntaxStack.itemCount() >= 4)
1259	if ((token.asOperator() == Token::Semicolon) ||
1260	(token.asOperator() == Token::CurlyKet) ||
1261	(token.asOperator() == Token::Pipe)) {
1262	Token arg2 = syntaxStack.top();
1263	Token sep = syntaxStack.top(1);
1264	Token arg1 = syntaxStack.top(2);
1265	Token bra = syntaxStack.top(3);
1266	if (!arg2.isOperator())
1267	if (sep.asOperator() == Token::Semicolon)
1268	if (!arg1.isOperator())
1269	if (bra.asOperator() == Token::CurlyBra) {
1270	ruleFound = true;
1271	syntaxStack.pop();
1272	syntaxStack.pop();
1273	argCount++;
1274	}
1275	}
1276
1277	// rule for last array row element, if token is ; or | or }
1278	// { arg1 | arg2 -> { arg
1279	if (!ruleFound)
1280	if (syntaxStack.itemCount() >= 4)
1281	if ((token.asOperator() == Token::Semicolon) ||
1282	(token.asOperator() == Token::CurlyKet) ||
1283	(token.asOperator() == Token::Pipe)) {
1284	Token arg2 = syntaxStack.top();
1285	Token sep = syntaxStack.top(1);
1286	Token arg1 = syntaxStack.top(2);
1287	Token bra = syntaxStack.top(3);
1288	if (!arg2.isOperator())
1289	if (sep.asOperator() == Token::Pipe)
1290	if (!arg1.isOperator())
1291	if (bra.asOperator() == Token::CurlyBra) {
1292	ruleFound = true;
1293	syntaxStack.pop();
1294	syntaxStack.pop();
1295	int rowCount = argStack.pop();
1296	argStack.push(++rowCount);
1297	argCount = 1;
1298	}
1299	}
1300
1301	// rule for last array element:
1302	// { arg } -> arg
1303	if (!ruleFound)
1304	if (syntaxStack.itemCount() >= 3) {
1305	Token ket = syntaxStack.top();
1306	Token arg = syntaxStack.top(1);
1307	Token bra = syntaxStack.top(2);
1308	if (ket.asOperator() == Token::CurlyKet)
1309	if (!arg.isOperator())
1310	if (bra.asOperator() == Token::CurlyBra) {
1311	ruleFound = true;
1312	syntaxStack.pop();
1313	syntaxStack.pop();
1314	syntaxStack.pop();
1315	syntaxStack.push(arg);
1316	const int rowCount = argStack.pop();
1317	d->constants.append(Value((int)argCount)); // cols
1318	d->constants.append(Value(rowCount));
1319	d->codes.append(Opcode(Opcode::Array, d->constants.count() - 2));
1320	Q_ASSERT(!argStack.empty());
1321	argCount = argStack.empty() ? 0 : argStack.pop();
1322	}
1323	}
1324	#endif
1325	// rule for parenthesis: ( Y ) -> Y
1326	if (!ruleFound)
1327	if (syntaxStack.itemCount() >= 3) {
1328	Token right = syntaxStack.top();
1329	Token y = syntaxStack.top(1);
1330	Token left = syntaxStack.top(2);
1331	if (right.isOperator())
1332	if (!y.isOperator())
1333	if (left.isOperator())
1334	if (right.asOperator() == Token::RightPar)
1335	if (left.asOperator() == Token::LeftPar) {
1336	ruleFound = true;
1337	syntaxStack.pop();
1338	syntaxStack.pop();
1339	syntaxStack.pop();
1340	syntaxStack.push(y);
1341	}
1342	}
1343
1344	// rule for binary operator: A (op) B -> A
1345	// conditions: precedence of op >= precedence of token
1346	// action: push (op) to result
1347	// e.g. "A * B" becomes 'A' if token is operator '+'
1348	if (!ruleFound)
1349	if (syntaxStack.itemCount() >= 3) {
1350	Token b = syntaxStack.top();
1351	Token op = syntaxStack.top(1);
1352	Token a = syntaxStack.top(2);
1353	if (!a.isOperator())
1354	if (!b.isOperator())
1355	if (op.isOperator())
1356	if (token.asOperator() != Token::LeftPar)
1357	if (opPrecedence(op.asOperator()) >= opPrecedence(token.asOperator())) {
1358	ruleFound = true;
1359	syntaxStack.pop();
1360	syntaxStack.pop();
1361	syntaxStack.pop();
1362	syntaxStack.push(b);
1363	switch (op.asOperator()) {
1364	// simple binary operations
1365	case Token::Plus: d->codes.append(Opcode::Add); break;
1366	case Token::Minus: d->codes.append(Opcode::Sub); break;
1367	case Token::Asterisk: d->codes.append(Opcode::Mul); break;
1368	case Token::Slash: d->codes.append(Opcode::Div); break;
1369	case Token::Caret: d->codes.append(Opcode::Pow); break;
1370	case Token::Ampersand: d->codes.append(Opcode::Concat); break;
1371	case Token::Intersect: d->codes.append(Opcode::Intersect); break;
1372	case Token::Union: d->codes.append(Opcode::Union); break;
1373
1374	// simple value comparisons
1375	case Token::Equal: d->codes.append(Opcode::Equal); break;
1376	case Token::Less: d->codes.append(Opcode::Less); break;
1377	case Token::Greater: d->codes.append(Opcode::Greater); break;
1378
1379	// NotEqual is Equal, followed by Not
1380	case Token::NotEqual:
1381	d->codes.append(Opcode::Equal);
1382	d->codes.append(Opcode::Not);
1383	break;
1384
1385	// LessOrEqual is Greater, followed by Not
1386	case Token::LessEqual:
1387	d->codes.append(Opcode::Greater);
1388	d->codes.append(Opcode::Not);
1389	break;
1390
1391	// GreaterOrEqual is Less, followed by Not
1392	case Token::GreaterEqual:
1393	d->codes.append(Opcode::Less);
1394	d->codes.append(Opcode::Not);
1395	break;
1396	default: break;
1397	};
1398	}
1399	}
1400
1401	// rule for unary operator: (op1) (op2) X -> (op1) X
1402	// conditions: op2 is unary, token is not '('
1403	// action: push (op2) to result
1404	// e.g. "* - 2" becomes '*'
1405	if (!ruleFound)
1406	if (token.asOperator() != Token::LeftPar)
1407	if (syntaxStack.itemCount() >= 3) {
1408	Token x = syntaxStack.top();
1409	Token op2 = syntaxStack.top(1);
1410	Token op1 = syntaxStack.top(2);
1411	if (!x.isOperator())
1412	if (op1.isOperator())
1413	if (op2.isOperator())
1414	if ((op2.asOperator() == Token::Plus) ||
1415	(op2.asOperator() == Token::Minus)) {
1416	ruleFound = true;
1417	syntaxStack.pop();
1418	syntaxStack.pop();
1419	syntaxStack.push(x);
1420	if (op2.asOperator() == Token::Minus)
1421	d->codes.append(Opcode(Opcode::Neg));
1422	}
1423	}
1424
1425	// auxiliary rule for unary operator: (op) X -> X
1426	// conditions: op is unary, op is first in syntax stack, token is not '('
1427	// action: push (op) to result
1428	if (!ruleFound)
1429	if (token.asOperator() != Token::LeftPar)
1430	if (syntaxStack.itemCount() == 2) {
1431	Token x = syntaxStack.top();
1432	Token op = syntaxStack.top(1);
1433	if (!x.isOperator())
1434	if (op.isOperator())
1435	if ((op.asOperator() == Token::Plus) ||
1436	(op.asOperator() == Token::Minus)) {
1437	ruleFound = true;
1438	syntaxStack.pop();
1439	syntaxStack.pop();
1440	syntaxStack.push(x);
1441	if (op.asOperator() == Token::Minus)
1442	d->codes.append(Opcode(Opcode::Neg));
1443	}
1444	}
1445
1446	if (!ruleFound) break;
1447	}
1448
1449	// can't apply rules anymore, push the token
1450	if (token.asOperator() != Token::Percent)
1451	syntaxStack.push(token);
1452	}
1453	}
1454
1455	// syntaxStack must left only one operand and end-of-formula (i.e. InvalidOp)
1456	d->valid = false;
1457	if (syntaxStack.itemCount() == 2)
1458	if (syntaxStack.top().isOperator())
1459	if (syntaxStack.top().asOperator() == Token::InvalidOp)
1460	if (!syntaxStack.top(1).isOperator())
1461	d->valid = true;
1462
1463	// bad parsing ? clean-up everything
1464	if (!d->valid) {
1465	d->constants.clear();
1466	d->codes.clear();
1467	}
1468	}
1469
1470	bool Formula::isNamedArea(const QString& expr) const
1471	{
1472	return d->sheet ? d->sheet->map()->namedAreaManager()->contains(expr) : false;
1473	}
1474
1475
1476	// Evaluates the formula, returns the result.
1477
1478	// evaluate the cellIndirections
1479	Value Formula::eval(CellIndirection cellIndirections) const
1480	{
1481	QHash<Cell, Value> values;
1482	return evalRecursive(cellIndirections, values);
1483	}
1484
1485	// We need to unroll arrays. Do use the same logic to unroll like OpenOffice.org and Excel are using.
1486	Value Formula::Private::valueOrElement(FuncExtra &fe, const stackEntry& entry) const
1487	{
1488	const Value& v = entry.val;
1489	const Region& region = entry.reg;
1490	if(v.isArray()) {
1491	if(v.count() == 1) // if there is only one item, use that one
1492	return v.element(0);
1493
1494	if(region.isValid() && entry.regIsNamedOrLabeled) {
1495	const QPoint position = region.firstRange().topLeft();
1496	const int idx = fe.myrow - position.y(); // do we need to do the same for columns?
1497	if(idx >= 0 && idx < int(v.count()))
1498	return v.element(idx); // within the range returns the selected element
1499	}
1500	}
1501	return v;
1502	}
1503
1504	// On OO.org Calc and MS Excel operations done with +, -, * and / do fail if one of the values is
1505	// non-numeric. This differs from formulas like SUM which just ignores non numeric values.
1506	Value numericOrError(const ValueConverter* converter, const Value &v)
1507	{
1508	switch (v.type()) {
1509	case Value::Empty:
1510	case Value::Boolean:
1511	case Value::Integer:
1512	case Value::Float:
1513	case Value::Complex:
1514	case Value::Error:
1515	return v;
1516	case Value::String: {
1517	if (v.asString().isEmpty())
1518	return v;
1519	bool ok;
1520	converter->asNumeric(v, &ok);
1521	if (ok)
1522	return v;
1523	} break;
1524	case Value::Array:
1525	case Value::CellRange:
1526	return v;
1527	}
1528	return Value::errorVALUE();
1529	}
1530
1531	Value Formula::evalRecursive(CellIndirection cellIndirections, QHash<Cell, Value>& values) const
1532	{
1533	QStack<stackEntry> stack;
1534	stackEntry entry;
1535	int index;
1536	Value val1, val2;
1537	QString c;
1538	QVector<Value> args;
1539
1540	const Map* map = d->sheet ? d->sheet->map() : new Map(0 /*document*/);
1541	const ValueConverter* converter = map->converter();
1542	ValueCalc* calc = map->calc();
1543
1544	QSharedPointer<Function> function;
1545	FuncExtra fe;
1546	fe.mycol = fe.myrow = 0;
1547	if (!d->cell.isNull()) {
1548	fe.mycol = d->cell.column();
1549	fe.myrow = d->cell.row();
1550	}
1551
1552	if (d->dirty) {
1553	Tokens tokens = scan(d->expression);
1554	d->valid = tokens.valid();
1555	if (tokens.valid())
1556	compile(tokens);
1557	}
1558
1559	if (!d->valid)
1560	return Value::errorPARSE();
1561
1562	for (int pc = 0; pc < d->codes.count(); pc++) {
1563	Value ret; // for the function caller
1564	Opcode& opcode = d->codes[pc];
1565	index = opcode.index;
1566	switch (opcode.type) {
1567	// no operation
1568	case Opcode::Nop:
1569	break;
1570
1571	// load a constant, push to stack
1572	case Opcode::Load:
1573	entry.reset();
1574	entry.val = d->constants[index];
1575	stack.push(entry);
1576	break;
1577
1578	// unary operation
1579	case Opcode::Neg:
1580	entry.reset();
1581	entry.val = d->valueOrElement(fe, stack.pop());
1582	if (!entry.val.isError()) // do nothing if we got an error
1583	entry.val = calc->mul(entry.val, -1);
1584	stack.push(entry);
1585	break;
1586
1587	// binary operation: take two values from stack, do the operation,
1588	// push the result to stack
1589	case Opcode::Add:
1590	entry.reset();
1591	val2 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1592	val1 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1593	val2 = calc->add(val1, val2);
1594	entry.reset();
1595	entry.val = val2;
1596	stack.push(entry);
1597	break;
1598
1599	case Opcode::Sub:
1600	val2 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1601	val1 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1602	val2 = calc->sub(val1, val2);
1603	entry.reset();
1604	entry.val = val2;
1605	stack.push(entry);
1606	break;
1607
1608	case Opcode::Mul:
1609	val2 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1610	val1 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1611	val2 = calc->mul(val1, val2);
1612	entry.reset();
1613	entry.val = val2;
1614	stack.push(entry);
1615	break;
1616
1617	case Opcode::Div:
1618	val2 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1619	val1 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1620	val2 = calc->div(val1, val2);
1621	entry.reset();
1622	entry.val = val2;
1623	stack.push(entry);
1624	break;
1625
1626	case Opcode::Pow:
1627	val2 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1628	val1 = numericOrError(converter, d->valueOrElement(fe, stack.pop()));
1629	val2 = calc->pow(val1, val2);
1630	entry.reset();
1631	entry.val = val2;
1632	stack.push(entry);
1633	break;
1634
1635	// string concatenation
1636	case Opcode::Concat:
1637	val1 = converter->asString(stack.pop().val);
1638	val2 = converter->asString(stack.pop().val);
1639	if (val1.isError() || val2.isError())
1640	val1 = Value::errorVALUE();
1641	else
1642	val1 = Value(val2.asString().append(val1.asString()));
1643	entry.reset();
1644	entry.val = val1;
1645	stack.push(entry);
1646	break;
1647
1648	// array intersection
1649	case Opcode::Intersect: {
1650	val1 = stack.pop().val;
1651	val2 = stack.pop().val;
1652	Region r1(d->constants[index].asString(), map, d->sheet);
1653	Region r2(d->constants[index+1].asString(), map, d->sheet);
1654	if(!r1.isValid() || !r2.isValid()) {
1655	val1 = Value::errorNULL();
1656	} else {
1657	Region r = r1.intersected(r2);
1658	QRect rect = r.boundingRect();
1659	Cell cell;
1660	if(rect.top() == rect.bottom())
1661	cell = Cell(r.firstSheet(), fe.mycol, rect.top());
1662	else if(rect.left() == rect.right())
1663	cell = Cell(r.firstSheet(), rect.left(), fe.mycol);
1664	if(cell.isNull())
1665	val1 = Value::errorNULL();
1666	else if(cell.isEmpty())
1667	val1 = Value::errorNULL();
1668	else
1669	val1 = cell.value();
1670	}
1671	entry.reset();
1672	entry.val = val1;
1673	stack.push(entry);
1674	} break;
1675
1676	// region union
1677	case Opcode::Union: {
1678	Region r = stack.pop().reg;
1679	Region r2 = stack.pop().reg;
1680	entry.reset();
1681	if (!r.isValid() || !r2.isValid()) {
1682	val1 = Value::errorVALUE();
1683	r = Region();
1684	} else {
1685	r.add(r2);
1686	r.firstSheet()->cellStorage()->valueRegion(r);
1687	// store the reference, so we can use it within functions (not entirely correct)
1688	entry.col1 = r.boundingRect().left();
1689	entry.row1 = r.boundingRect().top();
1690	entry.col2 = r.boundingRect().right();
1691	entry.row2 = r.boundingRect().bottom();
1692	}
1693	entry.val = val1;
1694	entry.reg = r;
1695	stack.push(entry);
1696	} break;
1697
1698	// logical not
1699	case Opcode::Not:
1700	val1 = converter->asBoolean(d->valueOrElement(fe, stack.pop()));
1701	if (val1.isError())
1702	val1 = Value::errorVALUE();
1703	else
1704	val1 = Value(!val1.asBoolean());
1705	entry.reset();
1706	entry.val = val1;
1707	stack.push(entry);
1708	break;
1709
1710	// comparison
1711	case Opcode::Equal:
1712	val1 = d->valueOrElement(fe, stack.pop());
1713	val2 = d->valueOrElement(fe, stack.pop());
1714	if (val1.isError())
1715	;
1716	else if (val2.isError())
1717	val1 = val2;
1718	else if (val2.compare(val1, calc->settings()->caseSensitiveComparisons()) == 0)
1719	val1 = Value(true);
1720	else
1721	val1 = Value(false);
1722	entry.reset();
1723	entry.val = val1;
1724	stack.push(entry);
1725	break;
1726
1727	// less than
1728	case Opcode::Less:
1729	val1 = d->valueOrElement(fe, stack.pop());
1730	val2 = d->valueOrElement(fe, stack.pop());
1731	if (val1.isError())
1732	;
1733	else if (val2.isError())
1734	val1 = val2;
1735	else if (val2.compare(val1, calc->settings()->caseSensitiveComparisons()) < 0)
1736	val1 = Value(true);
1737	else
1738	val1 = Value(false);
1739	entry.reset();
1740	entry.val = val1;
1741	stack.push(entry);
1742	break;
1743
1744	// greater than
1745	case Opcode::Greater: {
1746	val1 = d->valueOrElement(fe, stack.pop());
1747	val2 = d->valueOrElement(fe, stack.pop());
1748	if (val1.isError())
1749	;
1750	else if (val2.isError())
1751	val1 = val2;
1752	else if (val2.compare(val1, calc->settings()->caseSensitiveComparisons()) > 0)
1753	val1 = Value(true);
1754	else
1755	val1 = Value(false);
1756	entry.reset();
1757	entry.val = val1;
1758	stack.push(entry);
1759	}
1760	break;
1761
1762	// cell in a sheet
1763	case Opcode::Cell: {
1764	c = d->constants[index].asString();
1765	val1 = Value::empty();
1766	entry.reset();
1767
1768	const Region region(c, map, d->sheet);
1769	if (!region.isValid()) {
1770	val1 = Value::errorREF();
1771	} else if (region.isSingular()) {
1772	const QPoint position = region.firstRange().topLeft();
1773	if (cellIndirections.isEmpty())
1774	val1 = Cell(region.firstSheet(), position).value();
1775	else {
1776	Cell cell(region.firstSheet(), position);
1777	cell = cellIndirections.value(cell, cell);
1778	if (values.contains(cell))
1779	val1 = values.value(cell);
1780	else {
1781	values[cell] = Value::errorCIRCLE();
1782	if (cell.isFormula())
1783	val1 = cell.formula().evalRecursive(cellIndirections, values);
1784	else
1785	val1 = cell.value();
1786	values[cell] = val1;
1787	}
1788	}
1789	// store the reference, so we can use it within functions
1790	entry.col1 = entry.col2 = position.x();
1791	entry.row1 = entry.row2 = position.y();
1792	entry.reg = region;
1793	entry.regIsNamedOrLabeled = map->namedAreaManager()->contains(c);
1794	} else {
1795	kWarning() << "Unhandled non singular region in Opcode::Cell with rects=" << region.rects();
1796	}
1797	entry.val = val1;
1798	stack.push(entry);
1799	}
1800	break;
1801
1802	// selected range in a sheet
1803	case Opcode::Range: {
1804	c = d->constants[index].asString();
1805	val1 = Value::empty();
1806	entry.reset();
1807
1808	const Region region(c, map, d->sheet);
1809	if (region.isValid()) {
1810	val1 = region.firstSheet()->cellStorage()->valueRegion(region);
1811	// store the reference, so we can use it within functions
1812	entry.col1 = region.firstRange().left();
1813	entry.row1 = region.firstRange().top();
1814	entry.col2 = region.firstRange().right();
1815	entry.row2 = region.firstRange().bottom();
1816	entry.reg = region;
1817	entry.regIsNamedOrLabeled = map->namedAreaManager()->contains(c);
1818	}
1819
1820	entry.val = val1; // any array is valid here
1821	stack.push(entry);
1822	}
1823	break;
1824
1825	// reference
1826	case Opcode::Ref:
1827	val1 = d->constants[index];
1828	entry.reset();
1829	entry.val = val1;
1830	stack.push(entry);
1831	break;
1832
1833	// calling function
1834	case Opcode::Function:
1835	// sanity check, this should not happen unless opcode is wrong
1836	// (i.e. there's a bug in the compile() function)
1837	if (stack.count() < index)
1838	return Value::errorVALUE(); // not enough arguments
1839
1840	args.clear();
1841	fe.ranges.clear();
1842	fe.ranges.resize(index);
1843	fe.regions.clear();
1844	fe.regions.resize(index);
1845	fe.sheet = d->sheet;
1846	for (; index; index--) {
1847	stackEntry e = stack.pop();
1848	args.insert(args.begin(), e.val);
1849	// fill the FunctionExtra object
1850	fe.ranges[index - 1].col1 = e.col1;
1851	fe.ranges[index - 1].row1 = e.row1;
1852	fe.ranges[index - 1].col2 = e.col2;
1853	fe.ranges[index - 1].row2 = e.row2;
1854	fe.regions[index - 1] = e.reg;
1855	}
1856
1857	// function name as string value
1858	val1 = converter->asString(stack.pop().val);
1859	if (val1.isError())
1860	return val1;
1861	function = FunctionRepository::self()->function(val1.asString());
1862	if (!function)
1863	return Value::errorNAME(); // no such function
1864
1865	ret = function->exec(args, calc, &fe);
1866	entry.reset();
1867	entry.val = ret;
1868	stack.push(entry);
1869
1870	break;
1871
1872	#ifdef CALLIGRA_SHEETS_INLINE_ARRAYS
1873	// creating an array
1874	case Opcode::Array: {
1875	const int cols = d->constants[index].asInteger();
1876	const int rows = d->constants[index+1].asInteger();
1877	// check if enough array elements are available
1878	if (stack.count() < cols * rows)
1879	return Value::errorVALUE();
1880	Value array(Value::Array);
1881	for (int row = rows - 1; row >= 0; --row) {
1882	for (int col = cols - 1; col >= 0; --col) {
1883	array.setElement(col, row, stack.pop().val);
1884	}
1885	}
1886	entry.reset();
1887	entry.val = array;
1888	stack.push(entry);
1889	break;
1890	}
1891	#endif
1892	default:
1893	break;
1894	}
1895	}
1896
1897	if (!d->sheet)
1898	delete map;
1899
1900	// more than one value in stack ? unsuccessful execution...
1901	if (stack.count() != 1)
1902	return Value::errorVALUE();
1903
1904	return stack.pop().val;
1905	}
1906
1907	Formula& Formula::operator=(const Formula & other)
1908	{
1909	d = other.d;
1910	return *this;
1911	}
1912
1913	bool Formula::operator==(const Formula& other) const
1914	{
1915	return (d->expression == other.d->expression);
1916	}
1917
1918	// Debugging aid
1919
1920	QString Formula::dump() const
1921	{
1922	QString result;
1923
1924	if (d->dirty) {
1925	Tokens tokens = scan(d->expression);
1926	compile(tokens);
1927	}
1928
1929	result = QString("Expression: [%1]\n").arg(d->expression);
1930	#if 0
1931	Value value = eval();
1932	result.append(QString("Result: %1\n").arg(
1933	converter->asString(value).asString()));
1934	#endif
1935
1936	result.append(" Constants:\n");
1937	for (int c = 0; c < d->constants.count(); c++) {
1938	QString vtext;
1939	Value val = d->constants[c];
1940	if (val.isString()) vtext = QString("[%1]").arg(val.asString());
1941	else if (val.isNumber()) vtext = QString("%1").arg((double) numToDouble(val.asFloat()));
1942	else if (val.isBoolean()) vtext = QString("%1").arg(val.asBoolean() ? "True" : "False");
1943	else if (val.isError()) vtext = "error";
1944	else vtext = "???";
1945	result += QString(" #%1 = %2\n").arg(c).arg(vtext);
1946	}
1947
1948	result.append("\n");
1949	result.append(" Code:\n");
1950	for (int i = 0; i < d->codes.count(); i++) {
1951	QString ctext;
1952	switch (d->codes[i].type) {
1953	case Opcode::Load: ctext = QString("Load #%1").arg(d->codes[i].index); break;
1954	case Opcode::Ref: ctext = QString("Ref #%1").arg(d->codes[i].index); break;
1955	case Opcode::Function: ctext = QString("Function (%1)").arg(d->codes[i].index); break;
1956	case Opcode::Add: ctext = "Add"; break;
1957	case Opcode::Sub: ctext = "Sub"; break;
1958	case Opcode::Mul: ctext = "Mul"; break;
1959	case Opcode::Div: ctext = "Div"; break;
1960	case Opcode::Neg: ctext = "Neg"; break;
1961	case Opcode::Concat: ctext = "Concat"; break;
1962	case Opcode::Pow: ctext = "Pow"; break;
1963	case Opcode::Intersect: ctext = "Intersect"; break;
1964	case Opcode::Equal: ctext = "Equal"; break;
1965	case Opcode::Not: ctext = "Not"; break;
1966	case Opcode::Less: ctext = "Less"; break;
1967	case Opcode::Greater: ctext = "Greater"; break;
1968	case Opcode::Array: ctext = QString("Array (%1x%2)").arg(d->constants[d->codes[i].index].asInteger()).arg(d->constants[d->codes[i].index+1].asInteger()); break;
1969	case Opcode::Nop: ctext = "Nop"; break;
1970	case Opcode::Cell: ctext = "Cell"; break;
1971	case Opcode::Range: ctext = "Range"; break;
1972	default: ctext = "Unknown"; break;
1973	}
1974	result.append(" ").append(ctext).append("\n");
1975	}
1976
1977	return result;
1978	}
1979
1980	QTextStream& operator<<(QTextStream& ts, Formula formula)
1981	{
1982	ts << formula.dump();
1983	return ts;
1984	}
1985

---

Generated on 2014-Aug-04 from project calligra revision v2.8.79.3-471-g1a19fdb
Powered by Code Browser 1.7