1 /*************************************************************************************
2 * Copyright (C) 2007-2011 by Aleix Pol <aleixpol@kde.org> *
3 * *
4 * This program is free software; you can redistribute it and/or *
5 * modify it under the terms of the GNU General Public License *
6 * as published by the Free Software Foundation; either version 2 *
7 * of the License, or (at your option) any later version. *
8 * *
9 * This program is distributed in the hope that it will be useful, *
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12 * GNU General Public License for more details. *
13 * *
14 * You should have received a copy of the GNU General Public License *
15 * along with this program; if not, write to the Free Software *
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
17 *************************************************************************************/
18
19 #include "analyzer.h"
20
21 #include <QCoreApplication>
22
23 #include "operations.h"
24 #include "value.h"
25 #include "vector.h"
26 #include "variables.h"
27 #include "container.h"
28 #include "object.h"
29 #include "list.h"
30 #include "variable.h"
31 #include "analitzautils.h"
32 #include "expressiontypechecker.h"
33 #include "apply.h"
34 #include "providederivative.h"
35 #include "polynomial.h"
36 #include "transformation.h"
37 #include "substituteexpression.h"
38 #include "expressionstream.h"
39 #include "matrix.h"
40 #include "commands/realpower.h"
41 #include "commands/listcommands.h"
42 #include "commands/vectorcommands.h"
43 #include "commands/matrixcommands.h"
44 #include "commands/blockmatrixcommands.h"
45 #include "commands/matrixqueries.h"
46
47 #include <config-analitza.h>
48 #ifdef HAVE_EIGEN3
49 #include "commands/eigencommands.h"
50 #endif
51
52 // #define SCRIPT_PROFILER
53
54 #ifdef SCRIPT_PROFILER
55 #include <QTime>
56 #include <QFile>
57
58 class ScriptProfiler
59 {
60 public:
ScriptProfiler()61 ScriptProfiler()
62 {
63 f=new QFile("/tmp/analitza_profile");
64 bool a=f->open(QFile::WriteOnly);
65 Q_ASSERT(a);
66 stream=new QTextStream(f);
67
68 t.start();
69 }
70
~ScriptProfiler()71 ~ScriptProfiler() {
72 delete f; delete stream;
73 }
74
push(const QString & name)75 void push(const QString& name)
76 {
77 if(times.isEmpty())
78 t.restart();
79 times.push(Node(name, t.elapsed()));
80 }
81
pop()82 void pop() {
83 Node n = times.pop();
84
85 *stream << "callf" << n.name << QString::number(t.elapsed()-n.start) << endl;
86 if(times.isEmpty()) {
87 t.restart();
88 *stream << endl;
89 }
90 }
91 private:
92 struct Node {
NodeScriptProfiler::Node93 Node(const QString& name, int time) : name(name), start(time) {}
NodeScriptProfiler::Node94 Node() : start(-1) {}
95
96 QString name; int start;
97 };
98
99 QTime t;
100 QStack<Node> times;
101 QTextStream* stream;
102 QFile* f;
103 };
104
105 ScriptProfiler profiler;
106 #endif
107
108 using namespace AnalitzaUtils;
109 using namespace Analitza;
110
111 namespace Analitza
112 {
113 class BoundingIterator
114 {
115 public:
~BoundingIterator()116 virtual ~BoundingIterator() {}
117 virtual bool hasNext()=0;
118 };
119 }
120
121 template <class T>
printAll(const QVector<T * > & p)122 QStringList printAll(const QVector<T*> & p)
123 {
124 QStringList ret;
125 foreach(T* v, p)
126 if(v)
127 ret += v->toString();
128 else
129 ret += QStringLiteral("<null>");
130 return ret;
131 }
132
133 const int defsize = /*500*/0;
134
Analyzer()135 Analyzer::Analyzer()
136 : m_vars(new Variables), m_runStackTop(-1), m_hasdeps(true)
137 {
138 m_runStack.reserve(defsize);
139 registerBuiltinMethods();
140 }
141
Analyzer(Variables * v)142 Analyzer::Analyzer(Variables* v)
143 : Analyzer(QSharedPointer<Variables>(new Variables(*v)))
144 {}
145
Analyzer(const QSharedPointer<Variables> & v)146 Analyzer::Analyzer(const QSharedPointer<Variables> & v)
147 : m_vars(v), m_runStackTop(-1), m_hasdeps(true)
148 {
149 m_runStack.reserve(defsize);
150 Q_ASSERT(v);
151 registerBuiltinMethods();
152 }
153
Analyzer(const Analyzer & a)154 Analyzer::Analyzer(const Analyzer& a)
155 : m_exp(a.m_exp), m_vars(new Variables(*a.m_vars)), m_err(a.m_err), m_runStackTop(-1), m_hasdeps(a.m_hasdeps)
156 {
157 m_runStack.reserve(defsize);
158 registerBuiltinMethods();
159 }
160
~Analyzer()161 Analyzer::~Analyzer()
162 {
163 }
164
registerBuiltinMethods()165 void Analyzer::registerBuiltinMethods()
166 {
167 m_builtin.insertFunction(RealPower::id, RealPower::type, new RealPower);
168 m_builtin.insertFunction(RangeCommand::id, RangeCommand::type, new RangeCommand);
169 m_builtin.insertFunction(VectorCommand::id, VectorCommand::type, new VectorCommand);
170 m_builtin.insertFunction(MatrixCommand::id, MatrixCommand::type, new MatrixCommand);
171 m_builtin.insertFunction(BlockMatrixCommand::id, BlockMatrixCommand::type, new BlockMatrixCommand);
172 m_builtin.insertFunction(IdentityMatrixCommand::id, IdentityMatrixCommand::type, new IdentityMatrixCommand);
173 m_builtin.insertFunction(DiagonalMatrixCommand::id, DiagonalMatrixCommand::type, new DiagonalMatrixCommand);
174 m_builtin.insertFunction(BlockDiagonalMatrixCommand::id, BlockDiagonalMatrixCommand::type, new BlockDiagonalMatrixCommand);
175 m_builtin.insertFunction(TridiagonalMatrixCommand::id, TridiagonalMatrixCommand::type, new TridiagonalMatrixCommand);
176 m_builtin.insertFunction(IsZeroMatrixCommand::id, IsZeroMatrixCommand::type, new IsZeroMatrixCommand);
177 m_builtin.insertFunction(IsIdentityMatrixCommand::id, IsIdentityMatrixCommand::type, new IsIdentityMatrixCommand);
178 m_builtin.insertFunction(IsDiagonalMatrixCommand::id, IsDiagonalMatrixCommand::type, new IsDiagonalMatrixCommand);
179 #ifdef HAVE_EIGEN3
180 m_builtin.insertFunction(EigenvaluesCommand::id, EigenvaluesCommand::type, new EigenvaluesCommand);
181 m_builtin.insertFunction(EigenvectorsCommand::id, EigenvectorsCommand::type, new EigenvectorsCommand);
182 #endif
183 }
184
setExpression(const Expression & e)185 void Analyzer::setExpression(const Expression & e)
186 {
187 m_exp=e;
188 flushErrors();
189 if(!e.tree()) {
190 m_err << QCoreApplication::tr("Cannot calculate an empty expression");
191 } else if(m_exp.isCorrect()) {
192 ExpressionTypeChecker check(m_vars.data());
193 check.initializeVars(m_builtin.varTypes());
194 m_currentType=check.check(m_exp);
195
196 QMap<QString, ExpressionType> types=check.variablesTypes();
197 for(QMap<QString, ExpressionType>::const_iterator it=types.constBegin(), itEnd=types.constEnd(); it!=itEnd; ++it)
198 m_variablesTypes.insert(it.key(), it.value());
199
200 m_err += check.errors();
201 m_hasdeps = check.hasDependencies();
202 }
203 }
204
setVariables(const QSharedPointer<Analitza::Variables> & v)205 void Analitza::Analyzer::setVariables(const QSharedPointer<Analitza::Variables>& v)
206 {
207 m_vars = v;
208 }
209
importScript(QTextStream * stream)210 void Analyzer::importScript(QTextStream* stream)
211 {
212 ExpressionStream s(stream);
213 for(; !s.atEnd(); ) {
214 setExpression(s.next());
215 if(!s.isInterrupted())
216 calculate();
217
218 if(!isCorrect()) {
219 m_err += s.lastLine();
220 break;
221 }
222 }
223 }
224
evaluate()225 Expression Analyzer::evaluate()
226 {
227 Expression e;
228
229 if(isCorrect()) {
230 m_runStackTop = 0;
231 m_runStack.clear();
232 Object *o=eval(m_exp.tree(), true, QSet<QString>());
233
234 o=simp(o);
235 e.setTree(o);
236 } else {
237 m_err << QCoreApplication::tr("Must specify a correct operation");
238 }
239 return e;
240 }
241
calculate()242 Expression Analyzer::calculate()
243 {
244 Expression e;
245
246 if(!m_hasdeps && isCorrect()) {
247 m_runStackTop = 0;
248 m_runStack.clear();
249 e.setTree(calc(m_exp.tree()));
250 } else {
251 if(m_exp.isCorrect() && m_hasdeps)
252 m_err << QCoreApplication::tr("Unknown identifier: '%1'").arg(
253 dependencies(m_exp.tree(), m_vars->keys()+m_builtin.identifiers()).join(
254 QCoreApplication::translate("identifier separator in error message", "', '")));
255 else
256 m_err << QCoreApplication::tr("Must specify a correct operation");
257 }
258 return e;
259 }
260
calculateLambda()261 Expression Analyzer::calculateLambda()
262 {
263 Expression e;
264
265 if(Q_LIKELY(!m_hasdeps && m_exp.isCorrect())) {
266 Q_ASSERT(m_exp.tree()->isContainer());
267 Container* math=(Container*) m_exp.tree();
268 Q_ASSERT(math->m_params.first()->isContainer());
269 if(math->containerType()==Container::math) {
270 math=(Container*) math->m_params.first();
271 Q_ASSERT(math->m_params.first()->isContainer());
272 }
273
274 Container* lambda=(Container*) math;
275 Q_ASSERT(lambda->containerType()==Container::lambda);
276
277 if(Q_UNLIKELY(m_runStack.first()!=lambda))
278 m_runStack.prepend(lambda);
279 m_runStackTop = 0;
280 e.setTree(calc(lambda->m_params.last()));
281 } else {
282 m_err << QCoreApplication::tr("Must specify a correct operation");
283
284 if(m_exp.isCorrect() && m_hasdeps)
285 m_err << QCoreApplication::tr("Unknown identifier: '%1'").arg(
286 dependencies(m_exp.tree(), m_vars->keys()).join(
287 QCoreApplication::translate("identifier separator in error message", "', '")));
288 }
289 return e;
290 }
291
292 template<typename T, typename Tcontained>
evalElements(const Analitza::Object * branch,T * nv,bool resolve,const QSet<QString> & unscoped)293 Analitza::Object * Analyzer::evalElements(const Analitza::Object* branch, T* nv, bool resolve, const QSet<QString>& unscoped)
294 {
295 const T* v=static_cast<const T*>(branch);
296 auto itEnd=v->constEnd();
297 for(auto it=v->constBegin(); it!=itEnd; ++it) {
298 Object* res=eval(*it, resolve, unscoped);
299 nv->appendBranch(static_cast<Tcontained*>(res));
300 }
301 return nv;
302 }
303
eval(const Object * branch,bool resolve,const QSet<QString> & unscoped)304 Object* Analyzer::eval(const Object* branch, bool resolve, const QSet<QString>& unscoped)
305 {
306 Q_ASSERT(branch);
307 Object *ret=nullptr;
308 // qDebug() << "POPOPO" << branch->toString();
309
310 //Won't calc() so would be a good idea to have it simplified
311 if(branch->isContainer()) {
312 const Container* c = (Container*) branch;
313
314 // Q_ASSERT(!c->isEmpty());
315 switch(c->containerType()) {
316 case Container::declare: {
317 Ci *var = (Ci*) c->m_params[0];
318 delete m_vars->take(var->name());
319 ret = eval(c->m_params[1], true, unscoped);
320 ret = simp(ret);
321 Expression::computeDepth(ret);
322 insertVariable(var->name(), ret);
323 } break;
324 case Container::piecewise: {
325 Container::const_iterator it=c->m_params.constBegin(), itEnd=c->constEnd();
326
327 bool allfalse=true;
328 for(; !ret && it!=itEnd; ++it) {
329 Container *p=static_cast<Container*>(*it);
330 Q_ASSERT( (*it)->isContainer() &&
331 (p->containerType()==Container::piece || p->containerType()==Container::otherwise) );
332 bool isPiece = p->containerType()==Container::piece;
333 if(isPiece) {
334 Object *cond=simp(eval(p->m_params[1], resolve, unscoped));
335
336 if(cond->type()==Object::value) {
337 Cn* cval=static_cast<Cn*>(cond);
338 if(cval->isTrue()) {
339 allfalse=false;
340 ret=eval(p->m_params[0], resolve, unscoped);
341 }
342 } else
343 allfalse=false;
344 // qDebug() << "%%%%%" << cond->toString() << p->m_params[1]->toString() << allfalse;
345
346 delete cond;
347 } else if(allfalse) {
348 ret=eval(p->m_params[0], resolve, unscoped);
349 }
350 }
351 if(!ret)
352 ret=c->copy();
353
354 } break;
355 case Container::lambda: {
356 QSet<QString> newUnscoped(unscoped);
357 newUnscoped+=c->bvarStrings().toSet();
358
359 Container *r = c->copy();
360 Object* old=r->m_params.last();
361
362
363 int top = m_runStackTop;
364 m_runStackTop = m_runStack.size();
365 m_runStack.resize(m_runStackTop+c->bvarCount()+1);
366
367 r->m_params.last()=eval(old, false, newUnscoped);
368 delete old;
369
370 m_runStack.resize(m_runStackTop);
371 m_runStackTop = top;
372
373 alphaConversion(r, r->bvarCi().at(0)->depth());
374 Expression::computeDepth(r);
375 ret=r;
376 } break;
377 case Container::math:
378 ret=nullptr;
379 foreach(const Object* o, c->m_params) {
380 delete ret;
381 ret=eval(o, resolve, unscoped);
382 }
383 break;
384 default:
385 Q_ASSERT(false);
386 break;
387 }
388 } else if(resolve && branch->type()==Object::variable) {
389 Ci* var=(Ci*) branch;
390
391 if(!unscoped.contains(var->name())) {
392 Object* val = variableValue(var);
393
394 if(val && !equalTree(var, val)) {
395 QSet<QString> newUnscoped=unscoped;
396 newUnscoped.insert(var->name());
397 ret = eval(val, resolve, newUnscoped);
398 }
399 }
400
401 // qDebug() << "peeee" << var->name() << val << resolve << unscoped;
402 } else if(branch->type()==Object::vector) {
403 ret = evalElements<Vector>(branch, new Vector(static_cast<const Vector*>(branch)->size()), resolve, unscoped);
404 } else if(branch->type()==Object::list) {
405 ret = evalElements<List>(branch, new List, resolve, unscoped);
406 } else if(branch->type()==Object::matrix) {
407 ret = evalElements<Matrix, MatrixRow>(branch, new Matrix, resolve, unscoped);
408 } else if(branch->type()==Object::matrixrow) {
409 ret = evalElements<MatrixRow>(branch, new MatrixRow, resolve, unscoped);
410 } else if(branch->type()==Object::apply) {
411 const Apply* c=static_cast<const Apply*>(branch);
412 Operator op = c->firstOperator();
413
414 switch(op.operatorType()) {
415 case Operator::diff: {
416 //FIXME: Must support multiple bvars
417 QStringList bvars = c->bvarStrings();
418
419 Q_ASSERT(!c->isEmpty());
420 Object* o=derivative(bvars[0], *c->firstValue());
421
422 Container* cc=new Container(Container::lambda);
423 foreach(const QString& v, bvars) {
424 Container* bvar=new Container(Container::bvar);
425 bvar->appendBranch(new Ci(v));
426 cc->appendBranch(bvar);
427 }
428 cc->appendBranch(simp(o));
429 ret=cc;
430
431 Expression::computeDepth(ret);
432 } break;
433 case Operator::function: {
434 //it is a function. I'll take only this case for the moment
435 //it is only meant for operations with scoped variables that _change_ its value => have a value
436 Object* body=simp(eval(c->m_params[0], true, unscoped));
437
438 const Container *cbody = dynamic_cast<Container*>(body);
439 if(resolve && cbody && cbody->m_params.size()==c->m_params.size() && cbody->containerType()==Container::lambda) {
440 int bvarsSize = cbody->bvarCount();
441 QVector<Object*> args(bvarsSize+1);
442
443 args[0]=cbody->copy();
444 for(int i=0; i<bvarsSize; i++) {
445 args[i+1]=simp(eval(c->m_params[i+1], resolve, unscoped));
446 }
447 int aux = m_runStackTop;
448 m_runStackTop = m_runStack.size();
449 m_runStack.resize(m_runStackTop+bvarsSize+1);
450
451 int i=0;
452 foreach(Object* o, args)
453 m_runStack[m_runStackTop+i++]=o;
454 ret=eval(cbody->m_params.last(), resolve, unscoped);
455
456 qDeleteAll(m_runStack.begin()+m_runStackTop, m_runStack.end());
457 m_runStack.resize(m_runStackTop);
458 m_runStackTop = aux;
459
460 Expression::computeDepth(ret);
461 }
462
463 if(!ret)
464 ret=c->copy();
465
466 delete body;
467 } break;
468 case Operator::forall:
469 case Operator::exists:
470 case Operator::sum:
471 case Operator::product: {
472 Apply *r = c->copy();
473
474 QSet<QString> newUnscoped(unscoped);
475 int top = m_runStack.size();
476 bool resolved=false;
477
478 QSet<QString> bvars = c->bvarStrings().toSet();
479 newUnscoped += bvars;
480 m_runStack.resize(top + bvars.size());
481
482 if(r->domain()) {
483 QScopedPointer<Object> o(r->domain());
484 r->domain()=eval(r->domain(), resolve, unscoped);
485 resolved=r->domain()->type()==Object::list || r->domain()->type()==Object::vector || r->domain()->type()==Object::matrix;
486 } else {
487 if(r->dlimit()) {
488 QScopedPointer<Object> o(r->dlimit());
489 r->dlimit()=eval(r->dlimit(), resolve, unscoped);
490 }
491 if(r->ulimit()) {
492 QScopedPointer<Object> o(r->ulimit());
493 r->ulimit()=eval(r->ulimit(), resolve, unscoped);
494 }
495
496 resolved=r->dlimit()->type()==Object::value && r->ulimit()->type()==Object::value;
497 }
498
499 if(resolved && hasVars(*r->firstValue(), newUnscoped.values())) {
500 BoundingIterator *it = r->domain()? initBVarsContainer(r, top, r->domain()->copy()) : initBVarsRange(r, top, r->dlimit(), r->ulimit());
501
502 if(it) {
503 QVector<Object*> values;
504 Object* element = r->m_params.first();
505 do {
506 values += eval(element, resolve, unscoped);
507 } while(it->hasNext());
508
509 if(values.size()==1)
510 ret = values.first();
511 else {
512 r->ulimit()=nullptr;
513 r->dlimit()=nullptr;
514 r->domain()=nullptr;
515
516 Apply *newC = new Apply;
517 Operator::OperatorType t;
518 switch(op.operatorType()) {
519 case Operator::product: t = Operator::times; break;
520 case Operator::sum: t = Operator::plus; break;
521 case Operator::forall: t = Operator::_and; break;
522 default: /*exists*/ t = Operator::_or; break;
523 }
524
525 newC->appendBranch(new Operator(t));
526 newC->m_params = values;
527 ret = newC;
528 }
529 delete r;
530 } else
531 ret = r;
532
533 delete it;
534 } else {
535 Apply::iterator it=r->firstValue(), itEnd=r->end();
536 for(; it!=itEnd; ++it) {
537 Object *o=*it;
538 *it= eval(*it, resolve, newUnscoped);
539 delete o;
540 }
541 ret=r;
542 }
543
544 // qDeleteAll(m_runStack.begin()+top, m_runStack.end());
545 m_runStack.resize(top);
546
547 } break;
548 default: {
549 Q_ASSERT(!op.isBounded());
550 Apply *r = c->copy();
551
552 Apply::iterator it=r->firstValue(), itEnd=r->end();
553 for(; it!=itEnd; ++it) {
554 Object *o=*it;
555 *it= eval(*it, resolve, unscoped);
556 delete o;
557 }
558
559 // ret=simp(r);
560 ret=r;
561
562 } break;
563 }
564 }
565
566 if(!ret)
567 ret=branch->copy();
568 Q_ASSERT(ret);
569
570 return ret;
571 }
572
derivative(const QString & var,const Object * o)573 Object* Analyzer::derivative(const QString &var, const Object* o)
574 {
575 Q_ASSERT(o);
576
577 ProvideDerivative v(var);
578 Object* ret = v.run(o);
579
580 if(!v.isCorrect())
581 m_err += v.errors();
582 return ret;
583 }
584
calcPiecewise(const Container * c)585 Object* Analyzer::calcPiecewise(const Container* c)
586 {
587 Object* ret=nullptr;
588 //Here we have a list of options and finally the otherwise option
589 foreach(Object *o, c->m_params) {
590 Container *p=static_cast<Container*>(o);
591 Q_ASSERT( o->isContainer() &&
592 (p->containerType()==Container::piece ||
593 p->containerType()==Container::otherwise) );
594 bool isPiece = p->containerType()==Container::piece;
595 if(isPiece) {
596 QScopedPointer<Cn> condition((Cn*) calc(p->m_params[1]));
597 if(condition->isTrue()) {
598 ret=calc(p->m_params[0]);
599 break;
600 }
601
602 } else {
603 //it is an otherwise
604 ret=calc(p->m_params.first());
605 break;
606 }
607 }
608
609 if(Q_UNLIKELY(!ret)) {
610 m_err << QCoreApplication::translate("Error message, no proper condition found.", "Could not find a proper choice for a condition statement.");
611 ret=new Cn(0.);
612 }
613
614 return ret;
615 }
616
calcMath(const Container * c)617 Object* Analyzer::calcMath(const Container* c)
618 {
619 return calc(*c->constBegin());
620 }
621
calcLambda(const Container * c)622 Object* Analyzer::calcLambda(const Container* c)
623 {
624 Container * cc=c->copy();
625 if(cc->bvarCount()>0)
626 alphaConversion(cc, cc->bvarCi().at(0)->depth());
627 Expression::computeDepth(cc);
628 return cc;
629 }
630
calcDeclare(const Container * c)631 Object* Analyzer::calcDeclare(const Container* c)
632 {
633 Object *ret=nullptr;
634
635 const Ci *var = (const Ci*) c->m_params[0];
636 ret=simp(c->m_params[1]->copy());
637 Expression::computeDepth(ret);
638 bool corr = insertVariable(var->name(), ret);
639
640 Q_ASSERT(ret && corr);
641 return ret;
642 }
643
644 template<class T, class Tcontained>
calcElements(const Object * root,T * nv)645 Object* Analyzer::calcElements(const Object* root, T* nv)
646 {
647 const T *v=static_cast<const T*>(root);
648 auto itEnd=v->constEnd();
649
650 for(auto it=v->constBegin(); it!=itEnd; ++it)
651 nv->appendBranch(static_cast<Tcontained*>(calc(*it)));
652
653 return nv;
654 }
655
calc(const Object * root)656 Object* Analyzer::calc(const Object* root)
657 {
658 Q_ASSERT(root);
659 Object* ret=nullptr;
660
661 switch(root->type()) {
662 case Object::container:
663 ret = operate((const Container*) root);
664 break;
665 case Object::apply:
666 ret = operate((const Apply*) root);
667 break;
668 case Object::vector:
669 ret = calcElements<Vector>(root, new Vector(static_cast<const Vector*>(root)->size()));
670 break;
671 case Object::list:
672 ret = calcElements<List>(root, new List);
673 break;
674 case Object::matrix:
675 ret = calcElements<Matrix, MatrixRow>(root, new Matrix);
676 break;
677 case Object::matrixrow:
678 ret = calcElements<MatrixRow>(root, new MatrixRow);
679 break;
680 case Object::value:
681 case Object::custom:
682 ret=root->copy();
683 break;
684 case Object::variable:
685 ret=variableValue((Ci*) root);
686 if(ret)
687 ret = calc(ret);
688 else {
689 Container* c= new Container(Container::lambda);
690 c->appendBranch(root->copy());
691 ret=c;
692 }
693 break;
694 case Object::oper:
695 case Object::none:
696 break;
697 }
698 Q_ASSERT(ret);
699 return ret;
700 }
701
isNull(Analitza::Operator::OperatorType opt,Object * ret)702 bool isNull(Analitza::Operator::OperatorType opt, Object* ret)
703 {
704 return ret->type()==Object::value &&
705 ((opt==Operator::_and && static_cast<Cn*>(ret)->value()==0.) || (opt==Operator::_or && static_cast<Cn*>(ret)->value()==1.));
706 }
707
operate(const Apply * c)708 Object* Analyzer::operate(const Apply* c)
709 {
710 Object* ret=nullptr;
711 const Operator& op = c->firstOperator();
712 Operator::OperatorType opt=op.operatorType();
713
714 switch(opt) {
715 case Operator::sum:
716 ret = sum(*c);
717 break;
718 case Operator::product:
719 ret = product(*c);
720 break;
721 case Operator::forall:
722 ret = forall(*c);
723 break;
724 case Operator::exists:
725 ret = exists(*c);
726 break;
727 case Operator::function:
728 ret = func(*c);
729 break;
730 case Operator::diff:
731 ret = calcDiff(c);
732 break;
733 case Operator::map:
734 ret = calcMap(c);
735 break;
736 case Operator::filter:
737 ret = calcFilter(c);
738 break;
739 default: {
740 int count=c->countValues();
741 Q_ASSERT(count>0);
742 Q_ASSERT( (op.nparams()< 0 && count>1) ||
743 (op.nparams()>-1 && count==op.nparams()) ||
744 opt==Operator::minus);
745
746 QString* error=nullptr;
747 if(count>=2) {
748 Apply::const_iterator it = c->firstValue(), itEnd=c->constEnd();
749 ret = calc(*it);
750 ++it;
751 bool stop=isNull(opt, ret);
752 for(; !stop && it!=itEnd; ++it) {
753 bool isValue = (*it)->type()==Object::value;
754 Object* v = isValue ? *it : calc(*it);
755 if(Q_UNLIKELY(v->isNone())) {
756 Q_ASSERT(!isValue);
757 ret = v;
758 break;
759 }
760 ret=Operations::reduce(opt, ret, v, &error);
761 if(!isValue)
762 delete v;
763
764 if(Q_UNLIKELY(error)) {
765 m_err.append(*error);
766 delete error;
767 error=nullptr;
768 break;
769 }
770
771 stop=isNull(opt, ret);
772 }
773 } else {
774 ret = calc(*c->firstValue());
775 if(Q_LIKELY(!ret->isNone())) {
776 ret=Operations::reduceUnary(opt, ret, &error);
777 if(Q_UNLIKELY(error)) {
778 m_err.append(*error);
779 delete error;
780 }
781 }
782 }
783 } break;
784 }
785
786 Q_ASSERT(ret);
787 return ret;
788 }
789
790 Analyzer::funcContainer Analyzer::operateContainer[Container::domainofapplication+1] =
791 {nullptr, &Analyzer::calcMath, &Analyzer::calcDeclare, &Analyzer::calcLambda, nullptr,nullptr,nullptr,nullptr,&Analyzer::calcPiecewise,nullptr,nullptr};
792
operate(const Container * c)793 Object* Analyzer::operate(const Container* c)
794 {
795 Q_ASSERT(c);
796 funcContainer f=operateContainer[c->containerType()];
797 Q_ASSERT(f);
798 Object* ret=(this->*f)(c);
799
800 Q_ASSERT(ret);
801 return ret;
802 }
803
804 namespace Analitza
805 {
806 template <typename T, typename Iterator>
807 class TypeBoundingIterator : public BoundingIterator
808 {
809 public:
TypeBoundingIterator(QVector<Object * > & runStack,int top,const QVector<Ci * > & vars,T * l)810 TypeBoundingIterator(QVector<Object*>& runStack, int top, const QVector<Ci*>& vars, T* l)
811 : iterators(vars.size()), list(l)
812 , itBegin(l->constBegin()), itEnd(l->constEnd())
813 , m_runStack(runStack), m_top(top)
814 {
815 int s=vars.size();
816 for(int i=0; i<s; i++) {
817 m_runStack[m_top+i]=*itBegin;
818 iterators[i]=itBegin;
819 }
820 }
821
~TypeBoundingIterator()822 ~TypeBoundingIterator() override { delete list; }
823
hasNext()824 virtual bool hasNext() override
825 {
826 bool cont=true;
827 for(int i=iterators.size()-1; cont && i>=0; i--) {
828 ++iterators[i];
829 cont=(iterators[i]==itEnd);
830
831 if(cont)
832 iterators[i]=itBegin;
833 m_runStack[m_top+i]=*iterators[i];
834 }
835
836 return !cont;
837 }
838 private:
839 QVector<Iterator> iterators;
840 T* list;
841 const Iterator itBegin, itEnd;
842 QVector<Object*>& m_runStack;
843 int m_top;
844 };
845
846 class RangeBoundingIterator : public BoundingIterator
847 {
848 public:
RangeBoundingIterator(const QVector<Cn * > & values,Cn * oul,Cn * odl,double step)849 RangeBoundingIterator(const QVector<Cn*>& values, Cn* oul, Cn* odl, double step)
850 : values(values), dl(odl->value()), ul(oul->value()), step(step), objdl(odl), objul(oul)
851 {}
852
~RangeBoundingIterator()853 ~RangeBoundingIterator() override
854 {
855 qDeleteAll(values);
856 delete objdl;
857 delete objul;
858 }
859
hasNext()860 bool hasNext() override
861 {
862 bool cont=true;
863 for(int i=values.size()-1; cont && i>=0; i--) {
864 Cn* v=values[i];
865 double curr=v->value()+step;
866 cont=curr>ul;
867
868 v->setValue(cont ? dl : curr);
869 }
870
871 return !cont;
872 }
873
874 private:
875 const QVector<Cn*> values;
876 const double dl, ul, step;
877 Object* objdl;
878 Object* objul;
879 };
880 }
881
initializeBVars(const Apply * n,int base)882 BoundingIterator* Analyzer::initializeBVars(const Apply* n, int base)
883 {
884 BoundingIterator* ret=nullptr;
885
886 Object* domain=n->domain();
887
888 if(domain)
889 {
890 domain=calc(domain);
891 ret = initBVarsContainer(n, base, domain);
892
893 if(!ret)
894 delete domain;
895 }
896 else
897 {
898 Object *objul=calc(n->ulimit());
899 Object *objdl=calc(n->dlimit());
900
901 ret = initBVarsRange(n, base, objdl, objul);
902
903 if(!ret) {
904 delete objdl;
905 delete objul;
906 }
907 }
908 return ret;
909 }
initBVarsContainer(const Analitza::Apply * n,int base,Object * domain)910 BoundingIterator* Analyzer::initBVarsContainer(const Analitza::Apply* n, int base, Object* domain)
911 {
912 BoundingIterator* ret = nullptr;
913 QVector<Ci*> bvars=n->bvarCi();
914
915 switch(domain->type()) {
916 case Object::matrix:
917 Q_ASSERT(false && "fixme: properly iterate through elements when bounding");
918 if(static_cast<Matrix*>(domain)->rowCount()>0)
919 ret=new TypeBoundingIterator<Matrix, Matrix::const_iterator>(m_runStack, base, bvars, static_cast<Matrix*>(domain));
920 break;
921 case Object::list:
922 if(static_cast<List*>(domain)->size()>0)
923 ret=new TypeBoundingIterator<List, List::const_iterator>(m_runStack, base, bvars, static_cast<List*>(domain));
924 break;
925 case Object::vector:
926 if(static_cast<Vector*>(domain)->size()>0)
927 ret=new TypeBoundingIterator<Vector, Vector::const_iterator>(m_runStack, base, bvars, static_cast<Vector*>(domain));
928 break;
929 default:
930 Q_ASSERT(false && "Type not supported for bounding.");
931 m_err.append(QCoreApplication::tr("Type not supported for bounding."));
932 }
933 return ret;
934 }
935
initBVarsRange(const Apply * n,int base,Object * objdl,Object * objul)936 BoundingIterator* Analyzer::initBVarsRange(const Apply* n, int base, Object* objdl, Object* objul)
937 {
938 BoundingIterator* ret = nullptr;
939 if(isCorrect() && objul->type()==Object::value && objdl->type()==Object::value) {
940 Cn *u=static_cast<Cn*>(objul);
941 Cn *d=static_cast<Cn*>(objdl);
942 double ul=u->value();
943 double dl=d->value();
944
945 if(dl<=ul) {
946 QVector<Ci*> bvars=n->bvarCi();
947 QVector<Cn*> rr(bvars.size());
948
949 for(int i=0; i<bvars.size(); ++i) {
950 rr[i]=new Cn(dl);
951 m_runStack[base+i]=rr[i];
952 }
953
954 ret=new RangeBoundingIterator(rr, u, d, 1);
955 } else
956 m_err.append(QCoreApplication::tr("The downlimit is greater than the uplimit"));
957 } else
958 m_err.append(QCoreApplication::tr("Incorrect uplimit or downlimit."));
959 return ret;
960 }
961
boundedOperation(const Apply & n,const Operator & t,Object * initial)962 Object* Analyzer::boundedOperation(const Apply& n, const Operator& t, Object* initial)
963 {
964 Object* ret=initial;
965 int top = m_runStack.size();
966 m_runStack.resize(top+n.bvarCi().size());
967
968 BoundingIterator* it=initializeBVars(&n, top);
969 if(!it)
970 return initial;
971
972 QString* correct=nullptr;
973 Operator::OperatorType type=t.operatorType();
974 do {
975 Object *val=calc(n.m_params.last());
976 ret=Operations::reduce(type, ret, val, &correct);
977 delete val;
978 delete correct;
979 } while(Q_LIKELY(it->hasNext() && !correct && !isNull(type, ret)));
980
981 m_runStack.resize(top);
982
983 delete it;
984 Q_ASSERT(ret);
985 return ret;
986 }
987
product(const Apply & n)988 Object* Analyzer::product(const Apply& n)
989 {
990 return boundedOperation(n, Operator(Operator::times), new Cn(1.));
991 }
992
sum(const Apply & n)993 Object* Analyzer::sum(const Apply& n)
994 {
995 return boundedOperation(n, Operator(Operator::plus), new Cn(0.));
996 }
997
forall(const Apply & n)998 Object* Analyzer::forall(const Apply& n)
999 {
1000 return boundedOperation(n, Operator(Operator::_and), new Cn(true));
1001 }
1002
exists(const Apply & n)1003 Object* Analyzer::exists(const Apply& n)
1004 {
1005 return boundedOperation(n, Operator(Operator::_or), new Cn(false));
1006 }
1007
func(const Apply & n)1008 Object* Analyzer::func(const Apply& n)
1009 {
1010 bool borrowed = n.m_params[0]->type()==Object::variable;
1011 Container *function = static_cast<Container*>(borrowed ? variableValue((Ci*) n.m_params[0]) : calc(n.m_params[0]));
1012
1013 // static int ind=0;
1014 // qDebug() << "calling" << qPrintable(QString(++ind, '.')) << n.m_params.first()->toString() << n.toString();
1015
1016 int bvarsize = n.m_params.size()-1;
1017 QVector<Object*> args(bvarsize);
1018
1019 for(int i=1; i<bvarsize+1; i++) {
1020 args[i-1]=calc(n.m_params[i]);
1021 // qDebug() << "argumen" << qPrintable(QString(ind, '.')) << n.m_params[i]->toString() << "=" << args[i-1]->toString();
1022 }
1023
1024 Object* ret = calcCallFunction(function, args, n.m_params[0]);
1025
1026 // qDebug() << "called " << qPrintable(QString(ind--, '.')) << n.m_params.first()->toString() << ret->toString();
1027 if(!borrowed)
1028 delete function;
1029
1030 return ret;
1031 }
1032
calcCallFunction(Container * function,const QVector<Object * > & args,const Object * oper)1033 Object* Analyzer::calcCallFunction(Container* function, const QVector<Object*>& args, const Object* oper)
1034 {
1035 Object* ret=nullptr;
1036 int bvarsize = args.size();
1037
1038 if(function && function->m_params.size()>1) {
1039 #ifdef SCRIPT_PROFILER
1040 profiler.push(borrowed? static_cast<Ci*>(n.m_params[0])->name() : function->toString());
1041 #endif
1042 int top = m_runStack.size(), aux=m_runStackTop;
1043 m_runStack.resize(top+bvarsize+1);
1044
1045 m_runStack[top] = function;
1046 for(int i=0; i<args.size(); i++) {
1047 if (args[i]->type() != Object::none) {
1048 m_runStack[top+i+1] = args[i];
1049 } else {
1050 m_err += QCoreApplication::tr("Invalid type for parameter '%1'").arg(i+1);
1051 ret = new None();
1052
1053 return ret;
1054 }
1055 }
1056 m_runStackTop = top;
1057
1058 // qDebug() << "diiiiiiiii" << function->toString() << m_runStack.size() << bvarsize << m_runStackTop << printAll(m_runStack);
1059 ret=calc(function->m_params.last());
1060
1061 qDeleteAll(m_runStack.begin()+top+1, m_runStack.end());
1062
1063 m_runStackTop = aux;
1064 m_runStack.resize(top);
1065 } else {
1066 // Q_ASSERT(function ? (function->m_params[0]->type()==Object::variable && function->m_params.size()==1) : n.m_params[0]->type()==Object::variable);
1067 QString id=static_cast<const Ci*>(function ? function->m_params[0] : oper)->name();
1068 FunctionDefinition* func=m_builtin.function(id);
1069 QList<Expression> expargs;
1070
1071 for(int i=0; i<args.size(); i++) {
1072 if (args[i]->type() != Object::none) {
1073 expargs += Expression(args[i]);
1074 } else {
1075 m_err += QCoreApplication::tr("Invalid type for parameter '%1'").arg(i+1);
1076 ret = new None();
1077
1078 return ret;
1079 }
1080 }
1081 #ifdef SCRIPT_PROFILER
1082 profiler.push(id);
1083 #endif
1084 Expression exp=(*func)(expargs);
1085 if(Q_UNLIKELY(exp.isCorrect())) {
1086 ret=exp.tree();
1087 exp.setTree(nullptr);
1088 } else {
1089 m_err += exp.error();
1090 ret = new None();
1091 }
1092 }
1093 #ifdef SCRIPT_PROFILER
1094 profiler.pop();
1095 #endif
1096
1097 return ret;
1098 }
1099
calcMap(const Apply * c)1100 Object* Analyzer::calcMap(const Apply* c)
1101 {
1102 Container* f=static_cast<Container*>(calc(*c->firstValue()));
1103 List* l=static_cast<List*>(calc(*(c->firstValue()+1)));
1104
1105 List::iterator it=l->begin(), itEnd=l->end();
1106 for(; it!=itEnd; ++it) {
1107 *it = calcCallFunction(f, { *it }, f);
1108 }
1109
1110 delete f;
1111 return l;
1112 }
1113
calcFilter(const Apply * c)1114 Object* Analyzer::calcFilter(const Apply* c)
1115 {
1116 Container* f=static_cast<Container*>(calc(*c->firstValue()));
1117 List* l=static_cast<List*>(calc(*(c->firstValue()+1)));
1118
1119 List::iterator it=l->begin(), itEnd=l->end();
1120 List* ret = new List;
1121 for(; it!=itEnd; ++it) {
1122 QVector<Object*> args(1, (*it)->copy());
1123
1124 Object* ss=*it;
1125 Cn* val = static_cast<Cn*>(calcCallFunction(f, args, f));
1126
1127 if(val->isTrue()) {
1128 ret->appendBranch(ss->copy());
1129 }
1130 delete val;
1131 }
1132
1133 delete l;
1134 delete f;
1135 return ret;
1136 }
1137
1138
calcDiff(const Apply * c)1139 Object* Analyzer::calcDiff(const Apply* c)
1140 {
1141 //TODO: Make multibvar
1142 QVector<Ci*> bvars=c->bvarCi();
1143
1144 //We construct the lambda
1145 Object* o=derivative(bvars[0]->name(), *c->firstValue());
1146 o=simp(o);
1147
1148 Container* cc=new Container(Container::lambda);
1149 foreach(const Ci* v, bvars) {
1150 Container* bvar=new Container(Container::bvar);
1151 bvar->appendBranch(v->copy());
1152 cc->appendBranch(bvar);
1153 }
1154
1155 cc->appendBranch(o);
1156
1157 Expression::computeDepth(cc);
1158 return cc;
1159 }
1160
1161 /////////////////////////////////////////////
1162 /////////////////////////////////////////////
1163 /////////////////////////////////////////////
1164
simplify()1165 void Analyzer::simplify()
1166 {
1167 if(m_exp.isCorrect() && m_exp.tree()) {
1168 m_runStackTop = 0;
1169 Object* o=simp(m_exp.tree());
1170 m_exp.setTree(o);
1171 setExpression(m_exp);
1172 }
1173 }
1174
1175 template <class T, class Tcontained>
iterateAndSimp(T * v)1176 void Analyzer::iterateAndSimp(T* v)
1177 {
1178 auto it = v->begin(), itEnd=v->end();
1179
1180 for(; it!=itEnd; ++it)
1181 *it = static_cast<Tcontained*>(simp(*it));
1182 }
1183
simp(Object * root)1184 Object* Analyzer::simp(Object* root)
1185 {
1186 Q_ASSERT(root && root->type()!=Object::none);
1187 if(!isCorrect())
1188 return root;
1189
1190 if(!root->isContainer() && !hasVars(root))
1191 {
1192 if(root->type()!=Object::value && root->type() !=Object::oper) {
1193 Object* aux=root;
1194 root = calc(root);
1195 delete aux;
1196
1197 if(isLambda(root))
1198 root = simp(root);
1199 }
1200 } else if(root->type()==Object::vector) {
1201 iterateAndSimp<Vector>(static_cast<Vector*>(root));
1202 } else if(root->type()==Object::matrix) {
1203 iterateAndSimp<Matrix, MatrixRow>(static_cast<Matrix*>(root));
1204 } else if(root->type()==Object::matrixrow) {
1205 iterateAndSimp<MatrixRow>(static_cast<MatrixRow*>(root));
1206 } else if(root->type()==Object::list) {
1207 iterateAndSimp<List>(static_cast<List*>(root));
1208 } else if(root->type()==Object::apply) {
1209 root = simpApply((Apply*) root);
1210 } else if(root->isContainer()) {
1211 Container *c= (Container*) root;
1212
1213 switch(c->containerType()) {
1214 case Container::piecewise:
1215 root=simpPiecewise(c);
1216 break;
1217 case Container::lambda: {
1218 int top = m_runStackTop;
1219 m_runStackTop = m_runStack.size();
1220 m_runStack.resize(m_runStackTop+c->bvarCount()+1);
1221
1222 c->m_params.last()=simp(c->m_params.last());
1223 m_runStack.resize(m_runStackTop);
1224 m_runStackTop = top;
1225 } break;
1226 default:
1227 iterateAndSimp<Container>(c);
1228 break;
1229 }
1230 }
1231 return root;
1232 }
1233
applyTransformations(Object * root,const QList<Transformation> & trans)1234 Object* applyTransformations(Object* root, const QList<Transformation>& trans)
1235 {
1236 foreach(const Transformation& t, trans) {
1237 Object* o = t.applyTransformation(root);
1238 if(o) {
1239 delete root;
1240 return o;
1241 }
1242 }
1243 return root;
1244 }
1245
actuallyE(const Object * o)1246 bool actuallyE(const Object* o)
1247 {
1248 return o->type()==Object::variable && static_cast<const Ci*>(o)->name()==QLatin1String("e");
1249 }
1250
simplifications()1251 QList<Transformation> simplifications()
1252 {
1253 static QList<Transformation> ret;
1254 if(Q_UNLIKELY(ret.isEmpty())) {
1255 //divide
1256 ret += Transformation(Transformation::parse(QStringLiteral("f/f")), Transformation::parse(QStringLiteral("1")));
1257 ret += Transformation(Transformation::parse(QStringLiteral("f/1")), Transformation::parse(QStringLiteral("f")));
1258
1259 //power
1260 ret += Transformation(Transformation::parse(QStringLiteral("0**k")), Transformation::parse(QStringLiteral("0")));
1261 ret += Transformation(Transformation::parse(QStringLiteral("1**k")), Transformation::parse(QStringLiteral("1")));
1262 ret += Transformation(Transformation::parse(QStringLiteral("x**1")), Transformation::parse(QStringLiteral("x")));
1263 ret += Transformation(Transformation::parse(QStringLiteral("(x**y)**z")), Transformation::parse(QStringLiteral("x**(y*z)")));
1264
1265 //ln
1266 QMap<QString, Transformation::treeCheck> eulerNumber;
1267 eulerNumber.insert(QStringLiteral("e"), actuallyE);
1268 ret += Transformation(Transformation::parse(QStringLiteral("ln e")), Transformation::parse(QStringLiteral("1")), eulerNumber);
1269 }
1270
1271 return ret;
1272 }
1273
simpApply(Apply * c)1274 Object* Analyzer::simpApply(Apply* c)
1275 {
1276 Object* root=c;
1277 Apply::iterator it;
1278 Operator o = c->firstOperator();
1279
1280 switch(o.operatorType()) {
1281 case Operator::times:
1282 for(it=c->firstValue(); c->countValues()>1 && it!=c->end();) {
1283 bool d=false;
1284 *it = simp(*it);
1285
1286 if((*it)->type() == Object::value) {
1287 Cn* n = (Cn*) (*it);
1288 if(n->value()==1. && c->countValues()>1) { //1*exp=exp
1289 d=true;
1290 } else if(n->value()==0.) { //0*exp=0 //TODO Change to isZero and return the same type in 0
1291 delete root;
1292 root = new Cn(0.);
1293 return root;
1294 }
1295 }
1296
1297 if(!d)
1298 ++it;
1299 else {
1300 delete *it;
1301 it = c->m_params.erase(it);
1302 }
1303 }
1304
1305 root=simpPolynomials(c);
1306 break;
1307 case Operator::minus:
1308 case Operator::plus: {
1309 // qDebug() << "........................" << c->toString();
1310 for(Apply::iterator it=c->begin(), itEnd=c->end(); it!=itEnd; ++it) {
1311 *it = simp(*it);
1312 }
1313
1314 // qDebug()<< "PEPEPE" << c->toString();
1315 if(c->isUnary()) {
1316 if(o==Operator::minus && (*c->firstValue())->type()==Object::value) {
1317 Cn* v = static_cast<Cn*>(*c->firstValue());
1318 v->rvalue() *= -1;
1319
1320 root=v;
1321 *c->firstValue()=nullptr;
1322 delete c;
1323 c=nullptr;
1324 }
1325 } else {
1326 root=simpPolynomials(c);
1327 c=nullptr;
1328 }
1329 // qDebug()<< "PAAPPA" << root->toString();
1330 static QList<Transformation> addTrans;
1331 if(addTrans.isEmpty()) {
1332 addTrans += Transformation(Transformation::parse(QStringLiteral("--x")), Transformation::parse(QStringLiteral("x")));
1333 addTrans += Transformation(Transformation::parse(QStringLiteral("-a--b")), Transformation::parse(QStringLiteral("b-a")));
1334 }
1335
1336 root = applyTransformations(root, addTrans);
1337 } break;
1338 //TODO: extend to ::product
1339 case Operator::sum: {
1340
1341 QStringList bvars=c->bvarStrings();
1342 if(c->ulimit()) c->ulimit()=simp(c->ulimit());
1343 if(c->dlimit()) c->dlimit()=simp(c->dlimit());
1344 if(c->domain()) c->domain()=simp(c->domain());
1345
1346 Object *uplimit=c->ulimit(), *downlimit=c->dlimit(), *domain=c->domain();
1347
1348 //TODO: simplify this code
1349 for(it = c->m_params.begin(); it!=c->end(); ++it)
1350 *it = simp(*it);
1351
1352 //if bvars is empty, we are dealing with an invalid sum()
1353 Object* function = *c->firstValue();
1354 if(!bvars.isEmpty() && !domain && !hasTheVar(bvars.toSet(), function)) {
1355 Apply *cDiff=new Apply;
1356 cDiff->appendBranch(new Operator(Operator::minus));
1357 cDiff->appendBranch(uplimit ->copy());
1358 cDiff->appendBranch(downlimit->copy());
1359
1360 Apply *aPlusOne = new Apply;
1361 aPlusOne->appendBranch(new Operator(Operator::plus));
1362 aPlusOne->appendBranch(new Cn(1.));
1363 aPlusOne->appendBranch(cDiff);
1364
1365 Apply *nc=new Apply;
1366 nc->appendBranch(new Operator(Operator::times));
1367 nc->appendBranch(aPlusOne);
1368 nc->appendBranch(function);
1369
1370 c->m_params.last()=nullptr;
1371 delete c;
1372 root=simp(nc);
1373 } else if(function->isApply()) {
1374 root=simpSum(c);
1375 }
1376
1377 } break;
1378 case Operator::card: {
1379 Object* val=simp(*c->firstValue());
1380 if(val->type()==Object::vector)
1381 {
1382 c->m_params.last()=nullptr;
1383 QString* err=nullptr;
1384 val=Operations::reduceUnary(Operator::card, val, &err);
1385 if(Q_UNLIKELY(err)) { delete err; }
1386 delete c;
1387 root=val;
1388 }
1389 } break;
1390 case Operator::selector: {
1391 c->m_params[0]=simp(c->m_params[0]);
1392 c->m_params[1]=simp(c->m_params[1]);
1393
1394 Object* idx=c->m_params[0];
1395 Object* value=c->m_params[1];
1396 if(idx->type()==Object::value && value->type()==Object::vector) {
1397 QString* err=nullptr;
1398 Object* ret=Operations::reduce(Operator::selector, idx, value, &err);
1399 delete err;
1400
1401 if(ret) {
1402 root=ret;
1403 c->m_params[0]=nullptr;
1404 c->m_params[1]=nullptr;
1405
1406 delete c;
1407 }
1408 }
1409 } break;
1410 case Operator::_union: {
1411 Apply::iterator it=c->firstValue(), itEnd=c->end();
1412
1413 QVector<Object*> newParams;
1414 for(; it!=itEnd; ++it) {
1415 *it=simp(*it);
1416
1417 if(newParams.isEmpty())
1418 newParams.append(*it);
1419 else {
1420 if((*it)->type()==Object::list && newParams.last()->type()==Object::list) {
1421 QString* err=nullptr;
1422 Object* ret=Operations::reduce(Operator::_union, newParams.last(), *it, &err);
1423 delete err;
1424 newParams.last()=ret;
1425 delete *it;
1426 } else {
1427 newParams.append(*it);
1428 }
1429 }
1430 *it=nullptr;
1431 }
1432
1433 if(newParams.last()==nullptr)
1434 newParams.resize(newParams.size()-1);
1435
1436 //if only one, remove union
1437 if(newParams.size()==1) {
1438 delete c;
1439 root=newParams.last();
1440 } else {
1441 qDeleteAll(c->m_params);
1442 c->m_params=newParams;
1443 root=c;
1444 }
1445
1446 } break;
1447 case Operator::eq: {
1448 bool alleq=true, existsjustvar=false, allButFirstZero=false;
1449 QStringList deps = AnalitzaUtils::dependencies(c, QStringList());
1450
1451 for(Apply::iterator it=c->firstValue(), itEnd=c->end(); it!=itEnd; ++it) {
1452 *it = simp(*it);
1453 alleq = alleq && equalTree(*c->firstValue(), *it);
1454 existsjustvar = existsjustvar || (*it)->type()==Object::variable;
1455 allButFirstZero = (it==c->firstValue() || (*it)->isZero());
1456 }
1457
1458 if(alleq) {
1459 delete c;
1460 root = new Cn(true);
1461 } else if(!existsjustvar && deps.size()==1) {
1462 if(allButFirstZero) {
1463 Analitza::Apply::iterator first = c->firstValue();
1464 root = *first;
1465 c->m_params.erase(first);
1466 delete c;
1467 } else {
1468 Apply* a = new Apply;
1469 a->appendBranch(new Operator(Operator::minus));
1470
1471 for(Apply::const_iterator it=c->constBegin(), itEnd=c->constEnd(); it!=itEnd; ++it) {
1472 a->appendBranch(*it);
1473 }
1474 c->m_params.clear();
1475 delete c;
1476
1477 root = simp(a);
1478 }
1479
1480 if(root->type()==Object::apply) {
1481 QList<Object*> r = findRoots(deps.first(), static_cast<Apply*>(root));
1482
1483 if(r.isEmpty()) {
1484 Apply* na = new Apply;
1485 na->appendBranch(new Operator(Operator::eq));
1486 na->appendBranch(root);
1487 na->appendBranch(new Cn(0.));
1488 root=na;
1489 } else if(r.size() == 1) {
1490 Apply* a = new Apply;
1491 a->appendBranch(new Operator(Operator::eq));
1492 a->appendBranch(new Ci(deps.first()));
1493 a->appendBranch(r.first());
1494 delete root;
1495 root = a;
1496 } else {
1497 Apply* na = new Apply;
1498 na->appendBranch(new Operator(Operator::_or));
1499 foreach(Object* o, r) {
1500 Apply* a = new Apply;
1501 a->appendBranch(new Operator(Operator::eq));
1502 a->appendBranch(new Ci(deps.first()));
1503 a->appendBranch(o);
1504 na->appendBranch(a);
1505 }
1506 delete root;
1507 root = na;
1508 }
1509 } else if(!root->isZero()) {
1510 delete root;
1511 root = new Cn(false);
1512 }
1513 }
1514
1515 } break;
1516 case Operator::function: {
1517 Object* function=c->m_params[0];
1518
1519 Container* cfunc=nullptr;
1520 QList<Ci*> bvars;
1521 if(function->isContainer()) {
1522 cfunc=(Container*) function;
1523 Q_ASSERT(cfunc->containerType()==Container::lambda);
1524 bvars=cfunc->bvarCi();
1525 }
1526
1527 bool canRemove=true;
1528 it=c->begin()+1;
1529 for(int i=0; it!=c->end(); ++it, ++i) {
1530 *it = simp(*it);
1531 canRemove &= (*it)->type()==Object::variable || (cfunc && countDepth(bvars[i]->depth(), cfunc->m_params.last())==1);
1532 }
1533
1534 if(cfunc && canRemove) {
1535 int i=0;
1536 foreach(Ci* var, bvars) {
1537 replaceDepth(var->depth(), cfunc->m_params.last(), c->m_params[i+1]);
1538 i++;
1539 }
1540
1541 root=simp(cfunc->m_params.last());
1542 cfunc->m_params.last()=nullptr;
1543 delete c;
1544 }
1545 } break;
1546 default:
1547 if(c->ulimit())
1548 c->ulimit()=simp(c->ulimit());
1549 if(c->dlimit())
1550 c->dlimit()=simp(c->dlimit());
1551 if(c->domain())
1552 c->domain()=simp(c->domain());
1553
1554 iterateAndSimp<Apply>(c);
1555
1556 root = applyTransformations(root, simplifications());
1557 break;
1558 }
1559
1560 return root;
1561 }
1562
findRoots(const QString & dep,const Object * o)1563 QList<Object*> Analyzer::findRoots(const QString& dep, const Object* o)
1564 {
1565 switch(o->type()) {
1566 case Object::apply: return findRootsApply(dep, static_cast<const Apply*>(o));
1567 case Object::variable: return QList<Object*>() << new Cn(0.);
1568 default:
1569 return QList<Object*>();
1570 }
1571 }
1572
findRootsApply(const QString & dep,const Apply * a)1573 QList<Object*> Analyzer::findRootsApply(const QString& dep, const Apply* a)
1574 {
1575 Operator op=a->firstOperator();
1576 QList<Object*> ret;
1577 switch(op.operatorType()) {
1578 case Operator::plus:
1579 case Operator::minus: {
1580 Object* varTree = nullptr;
1581 //f(x)-w=0 => f(x)=w => x=f-1(x)
1582 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) {
1583 bool hasvars = hasVars(*it);
1584 if(hasvars && varTree) {
1585 varTree = nullptr; //we don't support having more than 1 variable in the minus yet
1586 return QList<Object*>();
1587 }
1588
1589 if(hasvars && ((*it)->type() == Object::variable || (*it)->isApply())) {
1590 if((*it)->isApply()) {
1591 const Apply* a = static_cast<const Apply*>(*it);
1592 if(!a->isUnary() || a->firstOperator().inverse().operatorType()==Operator::none)
1593 break;
1594 }
1595 varTree = *it;
1596 }
1597 }
1598
1599 if(varTree) {
1600 Apply* na = nullptr;
1601 Object* value = nullptr;
1602 if(a->countValues()>2) {
1603 na = new Apply;
1604 na->appendBranch(new Operator(a->firstOperator().inverse()));
1605 value = na;
1606 }
1607
1608 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) {
1609 if(*it != varTree) {
1610 if(na)
1611 na->appendBranch((*it)->copy());
1612 else {
1613 Q_ASSERT(!value);
1614 value = (*it)->copy();
1615 }
1616 }
1617 }
1618
1619 Q_ASSERT(value);
1620 if(varTree->isApply()) {
1621 Operator inv = static_cast<const Apply*>(varTree)->firstOperator().inverse();
1622 Apply* aa = new Apply;
1623 aa->appendBranch(inv.copy());
1624 aa->appendBranch(value);
1625 value = calc(aa);
1626 delete aa;
1627 }
1628
1629 if(op==Operator::minus) {
1630 ret += value;
1631 } else {
1632 Apply* aa = new Apply;
1633 aa->appendBranch(new Operator(Operator::minus));
1634 aa->appendBranch(value);
1635 ret += calc(aa);
1636 delete aa;
1637 }
1638 }
1639 } break;
1640 case Operator::times:
1641 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) {
1642 ret += findRoots(dep, static_cast<Apply*>(*it));
1643 }
1644 break;
1645 case Operator::divide: { // f/g
1646 Object* f = *a->firstValue();
1647 Object* g = *(a->firstValue()+1);
1648 ret = findRoots(dep, f);
1649
1650 for(QList<Object*>::iterator it = ret.begin(), itEnd=ret.end(); it!=itEnd; ) {
1651 bool erase = false;
1652
1653 Object* val = testResult(g, dep, *it);
1654 erase = val->isZero();
1655 delete val;
1656
1657 if(erase) {
1658 delete *it;
1659 it = ret.erase(it);
1660 } else
1661 ++it;
1662 }
1663 } break;
1664 default: {
1665 Operator inv = op.inverse();
1666 if(inv.operatorType()!=Operator::none && a->isUnary()) {
1667 Apply* aa = new Apply;
1668 aa->appendBranch(inv.copy());
1669 aa->appendBranch(new Cn(0.));
1670 ret += calc(aa);
1671 delete aa;
1672 }
1673 } break;
1674 }
1675 return ret;
1676 }
1677
testResult(const Object * o,const QString & var,const Object * val)1678 Object* Analyzer::testResult(const Object* o, const QString& var, const Object* val)
1679 {
1680 SubstituteExpression s;
1681 QMap<QString, const Object*> subs;
1682 subs.insert(var, val);
1683
1684 QScopedPointer<Object> sometree(s.run(o, subs));
1685 return calc(sometree.data());
1686 }
1687
simpPolynomials(Apply * c)1688 Object* Analyzer::simpPolynomials(Apply* c)
1689 {
1690 Q_ASSERT(c!=nullptr && c->isApply());
1691
1692 Polynomial monos(c);
1693
1694 c->m_params.clear();
1695 delete c;
1696 c=nullptr;
1697
1698 Object *root=monos.toObject();
1699
1700 return root;
1701 }
1702
simpSum(Apply * c)1703 Object* Analyzer::simpSum(Apply* c)
1704 {
1705 Object* ret=c;
1706 Apply* cval=static_cast<Apply*>(*c->firstValue());
1707
1708 if(cval->isApply() && cval->firstOperator()==Operator::times) {
1709 QSet<QString> bvars=c->bvarStrings().toSet();
1710 QVector<Object*> sum, out;
1711 Apply::iterator it=cval->firstValue(), itEnd=cval->end();
1712 int removed=0;
1713 for(; it!=itEnd; ++it) {
1714 if(hasTheVar(bvars, *it)) {
1715 sum.append(*it);
1716 } else {
1717 out.append(*it);
1718 *it=nullptr;
1719 ++removed;
1720 }
1721 }
1722
1723 if(removed>0) {
1724 Apply* nc=new Apply;
1725 nc->appendBranch(new Operator(Operator::times));
1726 nc->m_params << out << c;
1727
1728 if(sum.count()==1) {
1729 cval->m_params.clear();
1730 delete cval;
1731 c->m_params.last()=sum.last();
1732 } else {
1733 cval->m_params=sum;
1734 }
1735
1736 ret=simp(nc);
1737 }
1738 }
1739
1740 return ret;
1741 }
1742
simpPiecewise(Container * c)1743 Object* Analyzer::simpPiecewise(Container *c)
1744 {
1745 Object *root=c;
1746 //Here we have a list of options and finally the otherwise option
1747 Container *otherwise=nullptr;
1748 Container::const_iterator it=c->m_params.constBegin(), itEnd=c->constEnd();
1749 QList<Object*> newList;
1750
1751 for(; !otherwise && it!=itEnd; ++it) {
1752 Container *p=static_cast<Container*>(*it);
1753 Q_ASSERT( (*it)->isContainer() &&
1754 (p->containerType()==Container::piece || p->containerType()==Container::otherwise) );
1755 bool isPiece = p->containerType()==Container::piece;
1756
1757 p->m_params.last()=simp(p->m_params.last());
1758
1759 if(isPiece) {
1760 if(p->m_params[1]->type()==Object::value) {
1761 Cn* cond=static_cast<Cn*>(p->m_params[1]);
1762 if(cond->isTrue()) {
1763 delete p->m_params.takeLast();
1764 p->setContainerType(Container::otherwise);
1765 isPiece=false;
1766
1767 p->m_params[0]=simp(p->m_params[0]);
1768 otherwise=p;
1769 newList.append(p);
1770 } else {
1771 delete p;
1772 }
1773 } else {
1774 //TODO: It would be nice if we could simplify:
1775 // if(x=n) simplify x as n
1776 p->m_params[0]=simp(p->m_params[0]);
1777 newList.append(p);
1778 }
1779 } else { //it is an otherwise
1780 otherwise=p;
1781 newList.append(p);
1782 }
1783 }
1784 qDeleteAll(it, itEnd);
1785
1786 if(newList.count()==1 && otherwise) {
1787 root=otherwise->m_params.takeAt(0);
1788 delete otherwise;
1789 c->m_params.clear();
1790 delete c;
1791 } else
1792 c->m_params = newList;
1793 return root;
1794 }
1795
derivative(const QString & var)1796 Expression Analyzer::derivative(const QString& var)
1797 {
1798 Q_ASSERT(m_exp.isCorrect() && m_exp.tree());
1799
1800 QStringList vars;
1801 Object* deriv=m_exp.tree();
1802 if(m_exp.isLambda()){
1803 Q_ASSERT(deriv->isContainer());
1804 Container* lambda=(Container*) deriv;
1805 if(lambda->containerType()==Container::math) {
1806 Q_ASSERT(lambda->m_params.first()->isContainer());
1807 lambda = (Container*) lambda->m_params.first();
1808 }
1809 Q_ASSERT(lambda->containerType()==Container::lambda);
1810
1811 vars=lambda->bvarStrings();
1812 deriv=lambda->m_params.last();
1813 } else
1814 vars += var;
1815
1816 // Q_ASSERT(hasTheVar(QSet<QString>() << var, deriv));
1817 Object* o = derivative(var, deriv);
1818 o=simp(o);
1819 Container* lambda=new Container(Container::lambda);
1820 foreach(const QString& dep, vars) {
1821 Container* bvar=new Container(Container::bvar);
1822 bvar->appendBranch(new Ci(dep));
1823 lambda->appendBranch(bvar);
1824 }
1825 lambda->appendBranch(o);
1826 Expression::computeDepth(lambda);
1827 return Expression(lambda);
1828 }
1829
dependenciesToLambda() const1830 Expression Analyzer::dependenciesToLambda() const
1831 {
1832 if(m_hasdeps && m_exp.tree()) {
1833 QStringList deps=dependencies(m_exp.tree(), m_vars->keys());
1834 Container* cc=new Container(Container::lambda);
1835 foreach(const QString& dep, deps) {
1836 Container* bvar=new Container(Container::bvar);
1837 bvar->appendBranch(new Ci(dep));
1838 cc->appendBranch(bvar);
1839 }
1840
1841 const Object* root=m_exp.tree();
1842 if(root->isContainer()) {
1843 const Container* c=static_cast<const Container*>(root);
1844 if(c->containerType()==Container::math) {
1845 root=c->m_params.first();
1846 }
1847 }
1848 cc->appendBranch(root->copy());
1849
1850 Container* math=new Container(Container::math);
1851 math->appendBranch(cc);
1852
1853 Expression::computeDepth(math);
1854 return Expression(math);
1855 } else {
1856 return m_exp;
1857 }
1858 }
1859
insertVariable(const QString & name,const Expression & value)1860 bool Analyzer::insertVariable(const QString & name, const Expression & value)
1861 {
1862 return insertVariable(name, value.tree());
1863 }
1864
insertVariable(const QString & name,const Object * value)1865 bool Analyzer::insertVariable(const QString & name, const Object * value)
1866 {
1867 bool wrong=!isLambda(value) && hasTheVar(QSet<QString>() << name, value);
1868 if(wrong)
1869 m_err << QCoreApplication::translate("By a cycle i mean a variable that depends on itself", "Defined a variable cycle");
1870 else
1871 m_vars->modify(name, value);
1872
1873 return !wrong;
1874 }
1875
insertValueVariable(const QString & name,double value)1876 Cn* Analyzer::insertValueVariable(const QString& name, double value)
1877 {
1878 Cn* val=m_vars->modify(name, value);
1879 return val;
1880 }
1881
derivative(const QVector<Object * > & values)1882 double Analyzer::derivative(const QVector<Object*>& values )
1883 {
1884 //c++ numerical recipes p. 192. Only for f'
1885 //Image
1886 Q_ASSERT(m_exp.isCorrect() && m_exp.tree());
1887 Q_ASSERT(values.size()==m_exp.bvarList().size());
1888
1889 setStack(values);
1890
1891 Expression e1(calculateLambda());
1892 if(!isCorrect())
1893 return 0.;
1894
1895 //Image+h
1896 double h=0.0000000001;
1897 for(int i=0; i<values.size(); i++) {
1898 // volatile double temp=valp.second+h;
1899 // double hh=temp-valp.second;
1900
1901 Q_ASSERT(values[i]->type()==Object::value);
1902 Cn* v=static_cast<Cn*>(values[i]);
1903 v->setValue(v->value()+h);
1904 }
1905
1906 Expression e2(calculateLambda());
1907 if(!isCorrect())
1908 return 0.;
1909
1910 if(!e1.isReal() || !e2.isReal()) {
1911 m_err << QCoreApplication::tr("The result is not a number");
1912 return 0;
1913 }
1914
1915 return (e2.toReal().value()-e1.toReal().value())/h;
1916 }
1917
variableValue(Ci * var)1918 Analitza::Object* Analyzer::variableValue(Ci* var)
1919 {
1920 Object* ret;
1921
1922 // qDebug() << "ziiiiiiii" << var->name() << '('<< m_runStackTop << '+' << var->depth() << ')' << printAll(m_runStack);
1923 if(var->depth()>=0)
1924 ret = m_runStack[m_runStackTop + var->depth()];
1925 else
1926 ret = m_vars->value(var->name());
1927
1928 // static int hits = 0, misses = 0;
1929 // if(var->depth()>=0) hits++; else misses++;
1930 // qDebug() << "pepepe" << hits << misses;
1931 return ret;
1932 }
1933
applyAlpha(Object * o,int min)1934 Object* Analyzer::applyAlpha(Object* o, int min)
1935 {
1936 if(o)
1937 switch(o->type()) {
1938 case Object::container: alphaConversion(static_cast<Container*>(o), min); break;
1939 case Object::vector: alphaConversion<Vector>(static_cast<Vector*>(o), min); break;
1940 case Object::list: alphaConversion<List>(static_cast<List*>(o), min); break;
1941 case Object::matrix: alphaConversion<Matrix, MatrixRow>(static_cast<Matrix*>(o), min); break;
1942 case Object::matrixrow: alphaConversion<MatrixRow>(static_cast<MatrixRow*>(o), min); break;
1943 case Object::apply: alphaConversion(static_cast<Apply*>(o), min); break;
1944 case Object::variable: {
1945 Ci *var = static_cast<Ci*>(o);
1946 int depth = var->depth();
1947 // qDebug() << "puuuu" << var->name() << depth << '<' << min << printAll(m_runStack);
1948 if(depth>0 && depth<min && m_runStackTop+var->depth()<m_runStack.size()) {
1949 Object* newvalue = variableValue(var);
1950 if(newvalue) {
1951 delete var;
1952 return newvalue->copy();
1953 }
1954 }
1955 } break;
1956 case Object::none:
1957 case Object::value:
1958 case Object::oper:
1959 case Object::custom:
1960 break;
1961 }
1962 return o;
1963 }
1964
1965 template <class T, class Tcontained>
alphaConversion(T * o,int min)1966 void Analyzer::alphaConversion(T* o, int min)
1967 {
1968 Q_ASSERT(o);
1969 auto it=o->begin(), itEnd=o->end();
1970 for(; it!=itEnd; ++it) {
1971 *it = static_cast<Tcontained*>(applyAlpha(*it, min));
1972 }
1973 }
1974
alphaConversion(Container * o,int min)1975 void Analyzer::alphaConversion(Container* o, int min)
1976 {
1977 Q_ASSERT(o);
1978 Container::iterator it=o->begin(), itEnd=o->end();
1979 for(; it!=itEnd; ++it) {
1980 if((*it)->type()==Object::container && static_cast<Container*>(*it)->containerType()==Container::bvar)
1981 continue;
1982
1983 *it = applyAlpha(*it, min);
1984 }
1985 }
1986
alphaConversion(Apply * o,int min)1987 void Analyzer::alphaConversion(Apply* o, int min)
1988 {
1989 Q_ASSERT(o);
1990 o->ulimit()=applyAlpha(o->ulimit(), min);
1991 o->dlimit()=applyAlpha(o->dlimit(), min);
1992 o->domain()=applyAlpha(o->domain(), min);
1993
1994 Apply::iterator it=o->firstValue(), itEnd=o->end();
1995 for(; it!=itEnd; ++it)
1996 *it = applyAlpha(*it, min);
1997 }
1998
builtinMethods()1999 BuiltinMethods* Analyzer::builtinMethods()
2000 {
2001 return &m_builtin;
2002 }
2003