Krita Source Code Documentation
Loading...
Searching...
No Matches
EnhancedPathFormula.cpp
Go to the documentation of this file.
1/* This file is part of the KDE project
2 * SPDX-FileCopyrightText: 2007 Jan Hambrecht <jaham@gmx.net>
3 *
4 * SPDX-License-Identifier: LGPL-2.0-or-later
5 */
6
8#include "EnhancedPathShape.h"
9#include <QStack>
10#include <math.h>
11
12#include <QDebug>
13
14/*
15 The formula parsing, compiling and evaluating is based on
16 kspreads formula engine written by Ariya Hidayat.
17 There is a DESIGN.html file in the kspreads directory which
18 explains how the engine is working.
19 The engine was stripped down a little to only support the
20 operations needed for the odf enhanced path formula spec.
21*/
22
23// helper function: return operator of given token text
24FormulaToken::Operator matchOperator(const QString &text);
25// helper function: return true for valid identifier character
26bool isIdentifier(QChar ch);
27// helper function: give operator precedence
28// e.g. '+' is 1 while '*' is 3
30// helper function: return function of given token text
32// helper function: return function name from function identifier
34
35class FormulaToken;
36
37class FormulaTokenStack : public QVector<FormulaToken>
38{
39public:
45
46 bool isEmpty() const
47 {
48 return topIndex == 0;
49 }
50 unsigned itemCount() const
51 {
52 return topIndex;
53 }
54 void push(const FormulaToken &token)
55 {
57 insert(topIndex++, token);
58 }
60 {
61 return (topIndex > 0) ? FormulaToken(at(--topIndex)) : FormulaToken();
62 }
64 {
65 return top(0);
66 }
67 const FormulaToken &top(unsigned index)
68 {
69 static FormulaToken null;
70 if (topIndex > index) {
71 return at(topIndex - index - 1);
72 }
73 return null;
74 }
75private:
77 {
78 while ((int) topIndex >= size()) {
79 resize(size() + 10);
80 }
81 }
82 unsigned topIndex;
83};
84
85class Opcode
86{
87public:
88
89 enum { Nop = 0, Load, Ref, Function, Add, Sub, Neg, Mul, Div };
90
91 unsigned type;
92 unsigned index;
93
94 Opcode(): type(Nop), index(0) {}
95 Opcode(unsigned t): type(t), index(0) {}
96 Opcode(unsigned t, unsigned i): type(t), index(i) {}
97};
98
100 : m_valid(false)
101 , m_compiled(false)
102 , m_error(ErrorNone)
103 , m_text(text)
104 , m_parent(parent)
105{
106 Q_ASSERT(m_parent);
107}
108
112
114{
115 // shortcut
116 if (m_error != ErrorNone) {
117 return 0.0;
118 }
119
120 // lazy evaluation
121 if (!m_compiled) {
122 TokenList tokens = scan(m_text);
123 if (!compile(tokens)) {
124 debugOpcodes();
126 return 0.0;
127 }
128 m_compiled = true;
129 }
130
131 QStack<QVariant> stack;
132 // stack.reserve(3) here so that the stack is not resized all the time
133 // this reduces the number of a/de/re-llocations for documents with
134 // a lot of enhanced path shapes quite a lot.
135 stack.reserve(3);
136 int index = 0;
137
138 if (!m_valid) {
140 return 0.0;
141 }
142
143 for (int pc = 0; pc < m_codes.count(); pc++) {
144 QVariant ret; // for the function caller
145 Opcode &opcode = m_codes[pc];
146 index = opcode.index;
147 switch (opcode.type) {
148 // no operation
149 case Opcode::Nop:
150 break;
151
152 // load a constant, push to stack
153 case Opcode::Load:
154 stack.push(m_constants[index]);
155 break;
156
157 // unary operation
158 case Opcode::Neg: {
159 bool success = false;
160 qreal value = stack.pop().toDouble(&success);
161 if (success) { // do nothing if we got an error
162 value *= -1.0;
163 }
164 stack.push(QVariant(value));
165 break;
166 }
167
168 // binary operation: take two values from stack, do the operation,
169 // push the result to stack
170 case Opcode::Add: {
171 qreal val2 = stack.pop().toDouble();
172 qreal val1 = stack.pop().toDouble();
173 stack.push(QVariant(val1 + val2));
174 break;
175 }
176
177 case Opcode::Sub: {
178 qreal val2 = stack.pop().toDouble();
179 qreal val1 = stack.pop().toDouble();
180 stack.push(QVariant(val1 - val2));
181 break;
182 }
183
184 case Opcode::Mul: {
185 qreal val2 = stack.pop().toDouble();
186 qreal val1 = stack.pop().toDouble();
187 stack.push(QVariant(val1 * val2));
188 break;
189 }
190
191 case Opcode::Div: {
192 qreal val2 = stack.pop().toDouble();
193 qreal val1 = stack.pop().toDouble();
194 stack.push(QVariant(val1 / val2));
195 break;
196 }
197
198 case Opcode::Ref: {
199 QString reference = m_constants[index].toString();
200 // push function name if it is a function, else push evaluated reference
201 Function function = matchFunction(reference);
202 if (FunctionUnknown == function) {
203 stack.push(QVariant(m_parent->evaluateReference(reference)));
204 } else {
205 stack.push(function);
206 }
207 break;
208 }
209
210 // calling function
211 case Opcode::Function: {
212 // sanity check, this should not happen unless opcode is wrong
213 // (i.e. there's a bug in the compile() function)
214 if (stack.count() < index) {
215 qWarning() << "not enough arguments for function " << m_text;
216 m_error = ErrorValue; // not enough arguments
217 return 0.0;
218 }
219
221 QList<qreal> args;
222 for (; index; index--) {
223 qreal value = stack.pop().toDouble();
224 args.push_front(value);
225 }
226
227 // function identifier as int value
228 int function = stack.pop().toInt();
229 stack.push(QVariant(evaluateFunction((Function)function, args)));
230 break;
231 }
232
233 default:
234 break;
235 }
236 }
237
238 // more than one value in stack ? unsuccessful execution...
239 if (stack.count() != 1) {
241 return 0.0;
242 }
243
244 return stack.pop().toDouble();
245}
246
247qreal EnhancedPathFormula::evaluateFunction(Function function, const QList<qreal> &arguments) const
248{
249 switch (function) {
251 return fabs(arguments[0]);
252 break;
254 return sqrt(arguments[0]);
255 break;
257 return sin(arguments[0]);
258 break;
260 return cos(arguments[0]);
261 break;
263 return tan(arguments[0]);
264 break;
266 return atan(arguments[0]);
267 break;
269 // TODO atan2 with one argument as in odf spec ???
270 return atan2(arguments[0], arguments[1]);
271 break;
273 return qMin(arguments[0], arguments[1]);
274 break;
276 return qMax(arguments[0], arguments[1]);
277 break;
279 if (arguments[0] > 0.0) {
280 return arguments[1];
281 } else {
282 return arguments[2];
283 }
284 break;
285 default:
286 ;
287 }
288
289 return 0.0;
290}
291
292TokenList EnhancedPathFormula::scan(const QString &formula) const
293{
294 // parsing state
295 enum {
296 Start,
297 Finish,
298 Bad,
299 InNumber,
300 InDecimal,
301 InExpIndicator,
302 InExponent,
303 InString,
304 InIdentifier
305 } state;
306
307 TokenList tokens;
308
309 int i = 0;
310 state = Start;
311 int tokenStart = 0;
312 QString tokenText;
313 QString expr = formula + QChar();
314
315 // main loop
316 while ((state != Bad) && (state != Finish) && (i < expr.length())) {
317 QChar ch = expr[i];
318
319 switch (state) {
320 case Start:
321 tokenStart = i;
322
323 // skip any whitespaces
324 if (ch.isSpace()) {
325 i++;
326 } else if (ch.isDigit()) { // check for number
327 state = InNumber;
328 }
329 // beginning with alphanumeric ?
330 // could be identifier, function, function reference, modifier reference
331 else if (isIdentifier(ch)) {
332 state = InIdentifier;
333 } else if (ch == '.') { // decimal dot ?
334 tokenText.append(expr[i++]);
335 state = InDecimal;
336 } else if (ch == QChar::Null) { // terminator character
337 state = Finish;
338 } else { // look for operator match
339 QString opString(ch);
340 int op = matchOperator(opString);
341
342 // any matched operator ?
344 i++;
345 tokens.append(FormulaToken(FormulaToken::TypeOperator, opString, tokenStart));
346 } else {
347 state = Bad;
348 }
349 }
350 break;
351 case InIdentifier:
352 // consume as long as alpha, dollar sign, question mark, or digit
353 if (isIdentifier(ch) || ch.isDigit()) {
354 tokenText.append(expr[i++]);
355 } else if (ch == '(') { // a '(' ? then this must be a function identifier
356 tokens.append(FormulaToken(FormulaToken::TypeFunction, tokenText, tokenStart));
357 tokenStart = i;
358 tokenText.clear();
359 state = Start;
360 } else { // we're done with identifier
361 tokens.append(FormulaToken(FormulaToken::TypeReference, tokenText, tokenStart));
362 tokenStart = i;
363 tokenText.clear();
364 state = Start;
365 }
366 break;
367 case InNumber:
368 // consume as long as it's digit
369 if (ch.isDigit()) {
370 tokenText.append(expr[i++]);
371 } else if (ch == '.') { // decimal dot ?
372 tokenText.append('.');
373 i++;
374 state = InDecimal;
375 } else if (ch.toUpper() == 'E') { // exponent ?
376 tokenText.append('E');
377 i++;
378 state = InExpIndicator;
379 } else { // we're done with integer number
380 tokens.append(FormulaToken(FormulaToken::TypeNumber, tokenText, tokenStart));
381 tokenText.clear();
382 state = Start;
383 };
384 break;
385 case InDecimal:
386 // consume as long as it's digit
387 if (ch.isDigit()) {
388 tokenText.append(expr[i++]);
389 } else if (ch.toUpper() == 'E') { // exponent ?
390 tokenText.append('E');
391 i++;
392 state = InExpIndicator;
393 } else { // we're done with floating-point number
394 tokens.append(FormulaToken(FormulaToken::TypeNumber, tokenText, tokenStart));
395 tokenText.clear();
396 state = Start;
397 };
398 break;
399 case InExpIndicator:
400 // possible + or - right after E, e.g 1.23E+12 or 4.67E-8
401 if ((ch == '+') || (ch == '-')) {
402 tokenText.append(expr[i++]);
403 } else if (ch.isDigit()) { // consume as long as it's digit
404 state = InExponent;
405 } else { // invalid thing here
406 state = Bad;
407 }
408 break;
409 case InExponent:
410 // consume as long as it's digit
411 if (ch.isDigit()) {
412 tokenText.append(expr[i++]);
413 } else { // we're done with floating-point number
414 tokens.append(FormulaToken(FormulaToken::TypeNumber, tokenText, tokenStart));
415 tokenText.clear();
416 state = Start;
417 }
418 break;
419 default:
420 break;
421 }
422 }
423 return tokens;
424}
425
427{
428 // sanity check
429 if (tokens.count() == 0) {
430 return false;
431 }
432
433 FormulaTokenStack syntaxStack;
434 QStack<int> argStack;
435 unsigned argCount = 1;
436
437 for (int i = 0; i <= tokens.count(); i++) {
438 // helper token: InvalidOp is end-of-formula
439 FormulaToken token = (i < tokens.count()) ? tokens[i] : FormulaToken(FormulaToken::TypeOperator);
440 FormulaToken::Type tokenType = token.type();
441
442 // unknown token is invalid
443 if (tokenType == FormulaToken::TypeUnknown) {
444 break;
445 }
446
447 // for constants, push immediately to stack
448 // generate code to load from a constant
449 if (tokenType == FormulaToken::TypeNumber) {
450 syntaxStack.push(token);
451 m_constants.append(QVariant(token.asNumber()));
452 m_codes.append(Opcode(Opcode::Load, m_constants.count() - 1));
453 }
454 // for identifier, push immediately to stack
455 // generate code to load from reference
456 if (tokenType == FormulaToken::TypeFunction || tokenType == FormulaToken::TypeReference) {
457 syntaxStack.push(token);
458 m_constants.append(QVariant(token.text()));
459 m_codes.append(Opcode(Opcode::Ref, m_constants.count() - 1));
460 }
461 // are we entering a function ?
462 // if token is operator, and stack already has: id (arg
463 if (tokenType == FormulaToken::TypeOperator && syntaxStack.itemCount() >= 3) {
464 FormulaToken arg = syntaxStack.top();
465 FormulaToken par = syntaxStack.top(1);
466 FormulaToken id = syntaxStack.top(2);
467 if (!arg.isOperator() &&
469 id.isFunction()) {
470 argStack.push(argCount);
471 argCount = 1;
472 }
473 }
474 // for any other operator, try to apply all parsing rules
475 if (tokenType == FormulaToken::TypeOperator) {
476 // repeat until no more rule applies
477 for (;;) {
478 bool ruleFound = false;
479
480 // rule for function arguments, if token is , or)
481 // id (arg1 , arg2 -> id (arg
482 if (!ruleFound)
483 if (syntaxStack.itemCount() >= 5)
486 FormulaToken arg2 = syntaxStack.top();
487 FormulaToken sep = syntaxStack.top(1);
488 FormulaToken arg1 = syntaxStack.top(2);
489 FormulaToken par = syntaxStack.top(3);
490 FormulaToken id = syntaxStack.top(4);
491 if (!arg2.isOperator())
493 if (!arg1.isOperator())
495 if (id.isFunction()) {
496 ruleFound = true;
497 syntaxStack.pop();
498 syntaxStack.pop();
499 argCount++;
500 }
501 }
502 // rule for function last argument:
503 // id (arg) -> arg
504 if (!ruleFound)
505 if (syntaxStack.itemCount() >= 4) {
506 FormulaToken par2 = syntaxStack.top();
507 FormulaToken arg = syntaxStack.top(1);
508 FormulaToken par1 = syntaxStack.top(2);
509 FormulaToken id = syntaxStack.top(3);
511 if (!arg.isOperator())
513 if (id.isFunction()) {
514 ruleFound = true;
515 syntaxStack.pop();
516 syntaxStack.pop();
517 syntaxStack.pop();
518 syntaxStack.pop();
519 syntaxStack.push(arg);
520 m_codes.append(Opcode(Opcode::Function, argCount));
521 argCount = argStack.empty() ? 0 : argStack.pop();
522 }
523 }
524
525 // rule for parenthesis: (Y) -> Y
526 if (!ruleFound)
527 if (syntaxStack.itemCount() >= 3) {
528 FormulaToken right = syntaxStack.top();
529 FormulaToken y = syntaxStack.top(1);
530 FormulaToken left = syntaxStack.top(2);
531 if (right.isOperator())
532 if (!y.isOperator())
533 if (left.isOperator())
536 ruleFound = true;
537 syntaxStack.pop();
538 syntaxStack.pop();
539 syntaxStack.pop();
540 syntaxStack.push(y);
541 }
542 }
543
544 // rule for binary operator: A (op) B -> A
545 // conditions: precedence of op >= precedence of token
546 // action: push (op) to result
547 // e.g. "A * B" becomes 'A' if token is operator '+'
548 if (!ruleFound)
549 if (syntaxStack.itemCount() >= 3) {
550 FormulaToken b = syntaxStack.top();
551 FormulaToken op = syntaxStack.top(1);
552 FormulaToken a = syntaxStack.top(2);
553 if (!a.isOperator())
554 if (!b.isOperator())
555 if (op.isOperator())
557 if (opPrecedence(op.asOperator()) >= opPrecedence(token.asOperator())) {
558 ruleFound = true;
559 syntaxStack.pop();
560 syntaxStack.pop();
561 syntaxStack.pop();
562 syntaxStack.push(b);
563 switch (op.asOperator()) {
564 // simple binary operations
565 case FormulaToken::OperatorAdd: m_codes.append(Opcode::Add); break;
566 case FormulaToken::OperatorSub: m_codes.append(Opcode::Sub); break;
567 case FormulaToken::OperatorMul: m_codes.append(Opcode::Mul); break;
568 case FormulaToken::OperatorDiv: m_codes.append(Opcode::Div); break;
569 default: break;
570 }
571 }
572 }
573
574 // rule for unary operator: (op1) (op2) X -> (op1) X
575 // conditions: op2 is unary, token is not '('
576 // action: push (op2) to result
577 // e.g. "* - 2" becomes '*'
578 if (!ruleFound)
580 if (syntaxStack.itemCount() >= 3) {
581 FormulaToken x = syntaxStack.top();
582 FormulaToken op2 = syntaxStack.top(1);
583 FormulaToken op1 = syntaxStack.top(2);
584 if (!x.isOperator())
585 if (op1.isOperator())
586 if (op2.isOperator())
589 ruleFound = true;
590 syntaxStack.pop();
591 syntaxStack.pop();
592 syntaxStack.push(x);
594 m_codes.append(Opcode(Opcode::Neg));
595 }
596 }
597 }
598
599 // auxiliary rule for unary operator: (op) X -> X
600 // conditions: op is unary, op is first in syntax stack, token is not '('
601 // action: push (op) to result
602 if (!ruleFound)
604 if (syntaxStack.itemCount() == 2) {
605 FormulaToken x = syntaxStack.top();
606 FormulaToken op = syntaxStack.top(1);
607 if (!x.isOperator())
608 if (op.isOperator())
611 ruleFound = true;
612 syntaxStack.pop();
613 syntaxStack.pop();
614 syntaxStack.push(x);
616 m_codes.append(Opcode(Opcode::Neg));
617 }
618 }
619 }
620
621 if (!ruleFound) {
622 break;
623 }
624 }
625
626 syntaxStack.push(token);
627 }
628 }
629
630 // syntaxStack must left only one operand and end-of-formula (i.e. InvalidOp)
631 m_valid = false;
632 if (syntaxStack.itemCount() == 2)
633 if (syntaxStack.top().isOperator())
634 if (syntaxStack.top().asOperator() == FormulaToken::OperatorInvalid)
635 if (!syntaxStack.top(1).isOperator()) {
636 m_valid = true;
637 }
638
639 // bad parsing ? clean-up everything
640 if (!m_valid) {
641 m_constants.clear();
642 m_codes.clear();
643 qWarning() << "compiling of " << m_text << " failed";
644 }
645
646 return m_valid;
647}
648
650{
651 return m_text;
652}
653
654FormulaToken::FormulaToken(Type type, const QString &text, int position)
655 : m_type(type), m_text(text), m_position(position)
656{
657}
658
660{
661 if (this != &token) {
662 *this = token;
663 }
664}
665
667{
668 if (this == &rhs) {
669 return *this;
670 }
671
672 m_type = rhs.m_type;
673 m_text = rhs.m_text;
675
676 return *this;
677}
678
680{
681 if (isNumber()) {
682 return m_text.toDouble();
683 } else {
684 return 0.0;
685 }
686}
687
689{
690 if (isOperator()) {
691 return matchOperator(m_text);
692 } else {
693 return OperatorInvalid;
694 }
695}
696
697// helper function: return operator of given token text
699{
700 if (text.length() != 1) {
702 }
703
704 const char c = text[0].toLatin1();
705 switch (c) {
706 case '+': return FormulaToken::OperatorAdd; break;
707 case '-': return FormulaToken::OperatorSub; break;
708 case '*': return FormulaToken::OperatorMul; break;
709 case '/': return FormulaToken::OperatorDiv; break;
710 case '(': return FormulaToken::OperatorLeftPar; break;
711 case ')': return FormulaToken::OperatorRightPar; break;
712 case ',': return FormulaToken::OperatorComma; break;
713 default : return FormulaToken::OperatorInvalid; break;
714 }
715}
716
717// helper function: return true for valid identifier character
718bool isIdentifier(QChar ch)
719{
720 return (ch.unicode() == '?') || (ch.unicode() == '$') || (ch.isLetter());
721}
722
723// helper function: give operator precedence
724// e.g. '+' is 1 while '*' is 3
726{
727 int prec = -1;
728 switch (op) {
729 case FormulaToken::OperatorMul: prec = 5; break;
730 case FormulaToken::OperatorDiv: prec = 6; break;
731 case FormulaToken::OperatorAdd: prec = 3; break;
732 case FormulaToken::OperatorSub: prec = 3; break;
733 case FormulaToken::OperatorComma: prec = 0; break;
734 case FormulaToken::OperatorRightPar: prec = 0; break;
735 case FormulaToken::OperatorLeftPar: prec = -1; break;
736 default: prec = -1; break;
737 }
738 return prec;
739}
740
742{
743 if (text == "abs") {
745 }
746 if (text == "sqrt") {
748 }
749 if (text == "sin") {
751 }
752 if (text == "cos") {
754 }
755 if (text == "tan") {
757 }
758 if (text == "atan") {
760 }
761 if (text == "atan2") {
763 }
764 if (text == "min") {
766 }
767 if (text == "max") {
769 }
770 if (text == "if") {
772 }
773
775}
776
778{
779 switch (function) {
781 return "fabs";
782 break;
784 return "sqrt";
785 break;
787 return "sin";
788 break;
790 return "cos";
791 break;
793 return "tan";
794 break;
796 return "atan";
797 break;
799 return "atan2";
800 break;
802 return "min";
803 break;
805 return "max";
806 break;
808 return "if";
809 break;
810 default:
811 break;
812 }
813
814 return "unknown";
815}
816
818{
819#ifndef NDEBUG
820 for (int i = 0; i < tokens.count(); i++) {
821 qDebug() << tokens[i].text();
822 }
823#else
824 Q_UNUSED(tokens);
825#endif
826}
827
829{
830#ifndef NDEBUG
831 foreach (const Opcode &c, m_codes) {
832 QString ctext;
833 switch (c.type) {
834 case Opcode::Load: ctext = QString("Load #%1").arg(c.index); break;
835 case Opcode::Ref: ctext = QString("Ref #%1").arg(c.index); break;
836 case Opcode::Function: ctext = QString("Function (%1)").arg(c.index); break;
837 case Opcode::Add: ctext = "Add"; break;
838 case Opcode::Sub: ctext = "Sub"; break;
839 case Opcode::Mul: ctext = "Mul"; break;
840 case Opcode::Div: ctext = "Div"; break;
841 case Opcode::Neg: ctext = "Neg"; break;
842 default: ctext = "Unknown"; break;
843 }
844 qDebug() << ctext;
845 }
846#endif
847}
EnhancedPathFormula::Function matchFunction(const QString &text)
int opPrecedence(FormulaToken::Operator op)
bool isIdentifier(QChar ch)
FormulaToken::Operator matchOperator(const QString &text)
float value(const T *src, size_t ch)
EnhancedPathShape * m_parent
QString m_text
the formula text representation
QString toString() const
returns string representation of the formula
~EnhancedPathFormula()
Destroys the formula.
QList< QVariant > m_constants
constant values
qreal evaluateFunction(Function function, const QList< qreal > &arguments) const
bool m_compiled
flag that shows if function was compiled
bool m_valid
flag that shows if function is valid, i.e the function was compiled successfully
QList< Opcode > m_codes
the compiled byte code
void debugTokens(const TokenList &tokens)
Prints token list.
Error m_error
the last occurred error
TokenList scan(const QString &formula) const
Separates the given formula text into tokens.
EnhancedPathFormula(const QString &text, EnhancedPathShape *parent)
Constructs a new formula from the specified string representation.
@ ErrorValue
error when converting value
@ ErrorCompile
compiling error
Function
predefined functions
void debugOpcodes()
Prints byte code.
bool compile(const TokenList &tokens)
Compiles the formula tokens into byte code.
qreal evaluateReference(const QString &reference)
unsigned itemCount() const
const FormulaToken & top()
const FormulaToken & top(unsigned index)
void push(const FormulaToken &token)
Type type() const
Returns the type of the token.
FormulaToken & operator=(const FormulaToken &token)
assignment operator
QString text() const
Returns the text representation of the token.
FormulaToken(Type type=TypeUnknown, const QString &text=QString(), int position=-1)
Constructs token with given type, text and position.
Operator
operator types
@ OperatorLeftPar
(left parentheses
@ OperatorInvalid
invalid operator
@ OperatorRightPar
) right parentheses
@ OperatorDiv
/ division
bool isOperator() const
Returns if the token is a operator, OperatorInvalid if token is no operator.
Operator asOperator() const
Returns the token as operator.
qreal asNumber() const
Returns the token converted to qreal.
QString m_text
the token text representation
Type m_type
the token type
@ TypeReference
function reference, modifier reference or named variable
@ TypeOperator
+, *, /, -
@ TypeNumber
14, 3, 1977, 3.141592, 1e10, 5.9e-7
@ TypeUnknown
unknown type
@ TypeFunction
function name
bool isNumber() const
Returns if the token is a number.
int m_position
the tokens position
Opcode(unsigned t)
Opcode(unsigned t, unsigned i)