File indexing completed on 2024-04-28 03:40:40
0001 /************************************************************************************* 0002 * Copyright (C) 2007-2011 by Aleix Pol <aleixpol@kde.org> * 0003 * * 0004 * This program is free software; you can redistribute it and/or * 0005 * modify it under the terms of the GNU General Public License * 0006 * as published by the Free Software Foundation; either version 2 * 0007 * of the License, or (at your option) any later version. * 0008 * * 0009 * This program is distributed in the hope that it will be useful, * 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0012 * GNU General Public License for more details. * 0013 * * 0014 * You should have received a copy of the GNU General Public License * 0015 * along with this program; if not, write to the Free Software * 0016 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA * 0017 *************************************************************************************/ 0018 0019 #include "analyzer.h" 0020 0021 #include <QCoreApplication> 0022 0023 #include "operations.h" 0024 #include "value.h" 0025 #include "vector.h" 0026 #include "variables.h" 0027 #include "container.h" 0028 #include "object.h" 0029 #include "list.h" 0030 #include "variable.h" 0031 #include "analitzautils.h" 0032 #include "expressiontypechecker.h" 0033 #include "apply.h" 0034 #include "providederivative.h" 0035 #include "polynomial.h" 0036 #include "transformation.h" 0037 #include "substituteexpression.h" 0038 #include "expressionstream.h" 0039 #include "matrix.h" 0040 #include "commands/realpower.h" 0041 #include "commands/listcommands.h" 0042 #include "commands/vectorcommands.h" 0043 #include "commands/matrixcommands.h" 0044 #include "commands/blockmatrixcommands.h" 0045 #include "commands/matrixqueries.h" 0046 #include "commands/combinatronics.h" 0047 0048 #include <config-analitza.h> 0049 #ifdef HAVE_EIGEN3 0050 #include "commands/eigencommands.h" 0051 #endif 0052 0053 // #define SCRIPT_PROFILER 0054 0055 #ifdef SCRIPT_PROFILER 0056 #include <QTime> 0057 #include <QFile> 0058 0059 class ScriptProfiler 0060 { 0061 public: 0062 ScriptProfiler() 0063 { 0064 f=new QFile("/tmp/analitza_profile"); 0065 bool a=f->open(QFile::WriteOnly); 0066 Q_ASSERT(a); 0067 stream=new QTextStream(f); 0068 0069 t.start(); 0070 } 0071 0072 ~ScriptProfiler() { 0073 delete f; delete stream; 0074 } 0075 0076 void push(const QString& name) 0077 { 0078 if(times.isEmpty()) 0079 t.restart(); 0080 times.push(Node(name, t.elapsed())); 0081 } 0082 0083 void pop() { 0084 Node n = times.pop(); 0085 0086 *stream << "callf" << n.name << QString::number(t.elapsed()-n.start) << endl; 0087 if(times.isEmpty()) { 0088 t.restart(); 0089 *stream << endl; 0090 } 0091 } 0092 private: 0093 struct Node { 0094 Node(const QString& name, int time) : name(name), start(time) {} 0095 Node() : start(-1) {} 0096 0097 QString name; int start; 0098 }; 0099 0100 QTime t; 0101 QStack<Node> times; 0102 QTextStream* stream; 0103 QFile* f; 0104 }; 0105 0106 ScriptProfiler profiler; 0107 #endif 0108 0109 using namespace AnalitzaUtils; 0110 using namespace Analitza; 0111 0112 namespace Analitza 0113 { 0114 class BoundingIterator 0115 { 0116 public: 0117 virtual ~BoundingIterator() {} 0118 virtual bool hasNext()=0; 0119 }; 0120 } 0121 0122 template <class T> 0123 QStringList printAll(const QVector<T*> & p) 0124 { 0125 QStringList ret; 0126 foreach(T* v, p) 0127 if(v) 0128 ret += v->toString(); 0129 else 0130 ret += QStringLiteral("<null>"); 0131 return ret; 0132 } 0133 0134 const int defsize = /*500*/0; 0135 0136 Analyzer::Analyzer() 0137 : m_vars(new Variables), m_runStackTop(-1), m_hasdeps(true) 0138 { 0139 m_runStack.reserve(defsize); 0140 registerBuiltinMethods(); 0141 } 0142 0143 Analyzer::Analyzer(Variables* v) 0144 : Analyzer(QSharedPointer<Variables>(new Variables(*v))) 0145 {} 0146 0147 Analyzer::Analyzer(const QSharedPointer<Variables> & v) 0148 : m_vars(v), m_runStackTop(-1), m_hasdeps(true) 0149 { 0150 m_runStack.reserve(defsize); 0151 Q_ASSERT(v); 0152 registerBuiltinMethods(); 0153 } 0154 0155 Analyzer::Analyzer(const Analyzer& a) 0156 : 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) 0157 { 0158 m_runStack.reserve(defsize); 0159 registerBuiltinMethods(); 0160 } 0161 0162 Analyzer::~Analyzer() 0163 { 0164 } 0165 0166 void Analyzer::registerBuiltinMethods() 0167 { 0168 m_builtin.insertFunction(RealPower::id, RealPower::type, new RealPower); 0169 m_builtin.insertFunction(RangeCommand::id, RangeCommand::type, new RangeCommand); 0170 m_builtin.insertFunction(VectorCommand::id, VectorCommand::type, new VectorCommand); 0171 m_builtin.insertFunction(MatrixCommand::id, MatrixCommand::type, new MatrixCommand); 0172 m_builtin.insertFunction(BlockMatrixCommand::id, BlockMatrixCommand::type, new BlockMatrixCommand); 0173 m_builtin.insertFunction(IdentityMatrixCommand::id, IdentityMatrixCommand::type, new IdentityMatrixCommand); 0174 m_builtin.insertFunction(DiagonalMatrixCommand::id, DiagonalMatrixCommand::type, new DiagonalMatrixCommand); 0175 m_builtin.insertFunction(BlockDiagonalMatrixCommand::id, BlockDiagonalMatrixCommand::type, new BlockDiagonalMatrixCommand); 0176 m_builtin.insertFunction(TridiagonalMatrixCommand::id, TridiagonalMatrixCommand::type, new TridiagonalMatrixCommand); 0177 m_builtin.insertFunction(IsZeroMatrixCommand::id, IsZeroMatrixCommand::type, new IsZeroMatrixCommand); 0178 m_builtin.insertFunction(IsIdentityMatrixCommand::id, IsIdentityMatrixCommand::type, new IsIdentityMatrixCommand); 0179 m_builtin.insertFunction(IsDiagonalMatrixCommand::id, IsDiagonalMatrixCommand::type, new IsDiagonalMatrixCommand); 0180 m_builtin.insertFunction(CombinationCommand::id, CombinationCommand::type, new CombinationCommand); 0181 m_builtin.insertFunction(PermutationCommand::id, PermutationCommand::type, new PermutationCommand); 0182 #ifdef HAVE_EIGEN3 0183 m_builtin.insertFunction(EigenvaluesCommand::id, EigenvaluesCommand::type, new EigenvaluesCommand); 0184 m_builtin.insertFunction(EigenvectorsCommand::id, EigenvectorsCommand::type, new EigenvectorsCommand); 0185 #endif 0186 } 0187 0188 void Analyzer::setExpression(const Expression & e) 0189 { 0190 m_exp=e; 0191 flushErrors(); 0192 if(!e.tree()) { 0193 m_err << QCoreApplication::tr("Cannot calculate an empty expression"); 0194 } else if(m_exp.isCorrect()) { 0195 ExpressionTypeChecker check(m_vars.data()); 0196 check.initializeVars(m_builtin.varTypes()); 0197 m_currentType=check.check(m_exp); 0198 0199 QMap<QString, ExpressionType> types=check.variablesTypes(); 0200 for(QMap<QString, ExpressionType>::const_iterator it=types.constBegin(), itEnd=types.constEnd(); it!=itEnd; ++it) 0201 m_variablesTypes.insert(it.key(), it.value()); 0202 0203 m_err += check.errors(); 0204 m_hasdeps = check.hasDependencies(); 0205 } 0206 } 0207 0208 void Analitza::Analyzer::setVariables(const QSharedPointer<Analitza::Variables>& v) 0209 { 0210 m_vars = v; 0211 } 0212 0213 void Analyzer::importScript(QTextStream* stream) 0214 { 0215 ExpressionStream s(stream); 0216 for(; !s.atEnd(); ) { 0217 setExpression(s.next()); 0218 if(!s.isInterrupted()) 0219 calculate(); 0220 0221 if(!isCorrect()) { 0222 m_err += s.lastLine(); 0223 break; 0224 } 0225 } 0226 } 0227 0228 Expression Analyzer::evaluate() 0229 { 0230 Expression e; 0231 0232 if(isCorrect()) { 0233 m_runStackTop = 0; 0234 m_runStack.clear(); 0235 Object *o=eval(m_exp.tree(), true, QSet<QString>()); 0236 0237 o=simp(o); 0238 e.setTree(o); 0239 } else { 0240 m_err << QCoreApplication::tr("Must specify a correct operation"); 0241 } 0242 return e; 0243 } 0244 0245 Expression Analyzer::calculate() 0246 { 0247 Expression e; 0248 0249 if(!m_hasdeps && isCorrect()) { 0250 m_runStackTop = 0; 0251 m_runStack.clear(); 0252 e.setTree(calc(m_exp.tree())); 0253 } else { 0254 if(m_exp.isCorrect() && m_hasdeps) 0255 m_err << QCoreApplication::tr("Unknown identifier: '%1'").arg( 0256 dependencies(m_exp.tree(), m_vars->keys()+m_builtin.identifiers()).join( 0257 QCoreApplication::translate("identifier separator in error message", "', '"))); 0258 else 0259 m_err << QCoreApplication::tr("Must specify a correct operation"); 0260 } 0261 return e; 0262 } 0263 0264 Expression Analyzer::calculateLambda() 0265 { 0266 Expression e; 0267 0268 if(Q_LIKELY(!m_hasdeps && m_exp.isCorrect())) { 0269 Q_ASSERT(m_exp.tree()->isContainer()); 0270 Container* math=(Container*) m_exp.tree(); 0271 Q_ASSERT(math->m_params.first()->isContainer()); 0272 if(math->containerType()==Container::math) { 0273 math=(Container*) math->m_params.first(); 0274 Q_ASSERT(math->m_params.first()->isContainer()); 0275 } 0276 0277 Container* lambda=(Container*) math; 0278 Q_ASSERT(lambda->containerType()==Container::lambda); 0279 0280 if(Q_UNLIKELY(m_runStack.first()!=lambda)) 0281 m_runStack.prepend(lambda); 0282 m_runStackTop = 0; 0283 e.setTree(calc(lambda->m_params.last())); 0284 } else { 0285 m_err << QCoreApplication::tr("Must specify a correct operation"); 0286 0287 if(m_exp.isCorrect() && m_hasdeps) 0288 m_err << QCoreApplication::tr("Unknown identifier: '%1'").arg( 0289 dependencies(m_exp.tree(), m_vars->keys()).join( 0290 QCoreApplication::translate("identifier separator in error message", "', '"))); 0291 } 0292 return e; 0293 } 0294 0295 template<typename T, typename Tcontained> 0296 Analitza::Object * Analyzer::evalElements(const Analitza::Object* branch, T* nv, bool resolve, const QSet<QString>& unscoped) 0297 { 0298 const T* v=static_cast<const T*>(branch); 0299 auto itEnd=v->constEnd(); 0300 for(auto it=v->constBegin(); it!=itEnd; ++it) { 0301 Object* res=eval(*it, resolve, unscoped); 0302 nv->appendBranch(static_cast<Tcontained*>(res)); 0303 } 0304 return nv; 0305 } 0306 0307 Object* Analyzer::eval(const Object* branch, bool resolve, const QSet<QString>& unscoped) 0308 { 0309 Q_ASSERT(branch); 0310 Object *ret=nullptr; 0311 // qDebug() << "POPOPO" << branch->toString(); 0312 0313 //Won't calc() so would be a good idea to have it simplified 0314 if(branch->isContainer()) { 0315 const Container* c = (Container*) branch; 0316 0317 // Q_ASSERT(!c->isEmpty()); 0318 switch(c->containerType()) { 0319 case Container::declare: { 0320 Ci *var = (Ci*) c->m_params[0]; 0321 delete m_vars->take(var->name()); 0322 ret = eval(c->m_params[1], true, unscoped); 0323 ret = simp(ret); 0324 Expression::computeDepth(ret); 0325 insertVariable(var->name(), ret); 0326 } break; 0327 case Container::piecewise: { 0328 Container::const_iterator it=c->m_params.constBegin(), itEnd=c->constEnd(); 0329 0330 bool allfalse=true; 0331 for(; !ret && it!=itEnd; ++it) { 0332 Container *p=static_cast<Container*>(*it); 0333 Q_ASSERT( (*it)->isContainer() && 0334 (p->containerType()==Container::piece || p->containerType()==Container::otherwise) ); 0335 bool isPiece = p->containerType()==Container::piece; 0336 if(isPiece) { 0337 Object *cond=simp(eval(p->m_params[1], resolve, unscoped)); 0338 0339 if(cond->type()==Object::value) { 0340 Cn* cval=static_cast<Cn*>(cond); 0341 if(cval->isTrue()) { 0342 allfalse=false; 0343 ret=eval(p->m_params[0], resolve, unscoped); 0344 } 0345 } else 0346 allfalse=false; 0347 // qDebug() << "%%%%%" << cond->toString() << p->m_params[1]->toString() << allfalse; 0348 0349 delete cond; 0350 } else if(allfalse) { 0351 ret=eval(p->m_params[0], resolve, unscoped); 0352 } 0353 } 0354 if(!ret) 0355 ret=c->copy(); 0356 0357 } break; 0358 case Container::lambda: { 0359 QSet<QString> newUnscoped(unscoped); 0360 const auto &bvarString = c->bvarStrings(); 0361 newUnscoped += QSet<QString>(bvarString.begin(), bvarString.end()); 0362 0363 Container *r = c->copy(); 0364 Object* old=r->m_params.last(); 0365 0366 0367 int top = m_runStackTop; 0368 m_runStackTop = m_runStack.size(); 0369 m_runStack.resize(m_runStackTop+c->bvarCount()+1); 0370 0371 r->m_params.last()=eval(old, false, newUnscoped); 0372 delete old; 0373 0374 m_runStack.resize(m_runStackTop); 0375 m_runStackTop = top; 0376 0377 alphaConversion(r, r->bvarCi().at(0)->depth()); 0378 Expression::computeDepth(r); 0379 ret=r; 0380 } break; 0381 case Container::math: 0382 ret=nullptr; 0383 foreach(const Object* o, c->m_params) { 0384 delete ret; 0385 ret=eval(o, resolve, unscoped); 0386 } 0387 break; 0388 default: 0389 Q_ASSERT(false); 0390 break; 0391 } 0392 } else if(resolve && branch->type()==Object::variable) { 0393 Ci* var=(Ci*) branch; 0394 0395 if(!unscoped.contains(var->name())) { 0396 Object* val = variableValue(var); 0397 0398 if(val && !equalTree(var, val)) { 0399 QSet<QString> newUnscoped=unscoped; 0400 newUnscoped.insert(var->name()); 0401 ret = eval(val, resolve, newUnscoped); 0402 } 0403 } 0404 0405 // qDebug() << "peeee" << var->name() << val << resolve << unscoped; 0406 } else if(branch->type()==Object::vector) { 0407 ret = evalElements<Vector>(branch, new Vector(static_cast<const Vector*>(branch)->size()), resolve, unscoped); 0408 } else if(branch->type()==Object::list) { 0409 ret = evalElements<List>(branch, new List, resolve, unscoped); 0410 } else if(branch->type()==Object::matrix) { 0411 ret = evalElements<Matrix, MatrixRow>(branch, new Matrix, resolve, unscoped); 0412 } else if(branch->type()==Object::matrixrow) { 0413 ret = evalElements<MatrixRow>(branch, new MatrixRow, resolve, unscoped); 0414 } else if(branch->type()==Object::apply) { 0415 const Apply* c=static_cast<const Apply*>(branch); 0416 Operator op = c->firstOperator(); 0417 0418 switch(op.operatorType()) { 0419 case Operator::diff: { 0420 //FIXME: Must support multiple bvars 0421 QStringList bvars = c->bvarStrings(); 0422 0423 Q_ASSERT(!c->isEmpty()); 0424 Object* o=derivative(bvars[0], *c->firstValue()); 0425 0426 Container* cc=new Container(Container::lambda); 0427 foreach(const QString& v, bvars) { 0428 Container* bvar=new Container(Container::bvar); 0429 bvar->appendBranch(new Ci(v)); 0430 cc->appendBranch(bvar); 0431 } 0432 cc->appendBranch(simp(o)); 0433 ret=cc; 0434 0435 Expression::computeDepth(ret); 0436 } break; 0437 case Operator::function: { 0438 //it is a function. I'll take only this case for the moment 0439 //it is only meant for operations with scoped variables that _change_ its value => have a value 0440 Object* body=simp(eval(c->m_params[0], true, unscoped)); 0441 0442 const Container *cbody = dynamic_cast<Container*>(body); 0443 if(resolve && cbody && cbody->m_params.size()==c->m_params.size() && cbody->containerType()==Container::lambda) { 0444 int bvarsSize = cbody->bvarCount(); 0445 QVector<Object*> args(bvarsSize+1); 0446 0447 args[0]=cbody->copy(); 0448 for(int i=0; i<bvarsSize; i++) { 0449 args[i+1]=simp(eval(c->m_params[i+1], resolve, unscoped)); 0450 } 0451 int aux = m_runStackTop; 0452 m_runStackTop = m_runStack.size(); 0453 m_runStack.resize(m_runStackTop+bvarsSize+1); 0454 0455 int i=0; 0456 foreach(Object* o, args) 0457 m_runStack[m_runStackTop+i++]=o; 0458 ret=eval(cbody->m_params.last(), resolve, unscoped); 0459 0460 qDeleteAll(m_runStack.begin()+m_runStackTop, m_runStack.end()); 0461 m_runStack.resize(m_runStackTop); 0462 m_runStackTop = aux; 0463 0464 Expression::computeDepth(ret); 0465 } 0466 0467 if(!ret) 0468 ret=c->copy(); 0469 0470 delete body; 0471 } break; 0472 case Operator::forall: 0473 case Operator::exists: 0474 case Operator::sum: 0475 case Operator::product: { 0476 Apply *r = c->copy(); 0477 0478 QSet<QString> newUnscoped(unscoped); 0479 int top = m_runStack.size(); 0480 bool resolved=false; 0481 0482 const auto &bvarString = c->bvarStrings(); 0483 QSet<QString> bvars = QSet<QString>(bvarString.begin(), bvarString.end()); 0484 newUnscoped += bvars; 0485 m_runStack.resize(top + bvars.size()); 0486 0487 if(r->domain()) { 0488 QScopedPointer<Object> o(r->domain()); 0489 r->domain()=eval(r->domain(), resolve, unscoped); 0490 resolved=r->domain()->type()==Object::list || r->domain()->type()==Object::vector || r->domain()->type()==Object::matrix; 0491 } else { 0492 if(r->dlimit()) { 0493 QScopedPointer<Object> o(r->dlimit()); 0494 r->dlimit()=eval(r->dlimit(), resolve, unscoped); 0495 } 0496 if(r->ulimit()) { 0497 QScopedPointer<Object> o(r->ulimit()); 0498 r->ulimit()=eval(r->ulimit(), resolve, unscoped); 0499 } 0500 0501 resolved=r->dlimit()->type()==Object::value && r->ulimit()->type()==Object::value; 0502 } 0503 0504 if(resolved && hasVars(*r->firstValue(), newUnscoped.values())) { 0505 BoundingIterator *it = r->domain()? initBVarsContainer(r, top, r->domain()->copy()) : initBVarsRange(r, top, r->dlimit(), r->ulimit()); 0506 0507 if(it) { 0508 QVector<Object*> values; 0509 Object* element = r->m_params.first(); 0510 do { 0511 values += eval(element, resolve, unscoped); 0512 } while(it->hasNext()); 0513 0514 if(values.size()==1) 0515 ret = values.first(); 0516 else { 0517 r->ulimit()=nullptr; 0518 r->dlimit()=nullptr; 0519 r->domain()=nullptr; 0520 0521 Apply *newC = new Apply; 0522 Operator::OperatorType t; 0523 switch(op.operatorType()) { 0524 case Operator::product: t = Operator::times; break; 0525 case Operator::sum: t = Operator::plus; break; 0526 case Operator::forall: t = Operator::_and; break; 0527 default: /*exists*/ t = Operator::_or; break; 0528 } 0529 0530 newC->appendBranch(new Operator(t)); 0531 newC->m_params = values; 0532 ret = newC; 0533 } 0534 delete r; 0535 } else 0536 ret = r; 0537 0538 delete it; 0539 } else { 0540 Apply::iterator it=r->firstValue(), itEnd=r->end(); 0541 for(; it!=itEnd; ++it) { 0542 Object *o=*it; 0543 *it= eval(*it, resolve, newUnscoped); 0544 delete o; 0545 } 0546 ret=r; 0547 } 0548 0549 // qDeleteAll(m_runStack.begin()+top, m_runStack.end()); 0550 m_runStack.resize(top); 0551 0552 } break; 0553 default: { 0554 Q_ASSERT(!op.isBounded()); 0555 Apply *r = c->copy(); 0556 0557 Apply::iterator it=r->firstValue(), itEnd=r->end(); 0558 for(; it!=itEnd; ++it) { 0559 Object *o=*it; 0560 *it= eval(*it, resolve, unscoped); 0561 delete o; 0562 } 0563 0564 // ret=simp(r); 0565 ret=r; 0566 0567 } break; 0568 } 0569 } 0570 0571 if(!ret) 0572 ret=branch->copy(); 0573 Q_ASSERT(ret); 0574 0575 return ret; 0576 } 0577 0578 Object* Analyzer::derivative(const QString &var, const Object* o) 0579 { 0580 Q_ASSERT(o); 0581 0582 ProvideDerivative v(var); 0583 Object* ret = v.run(o); 0584 0585 if(!v.isCorrect()) 0586 m_err += v.errors(); 0587 return ret; 0588 } 0589 0590 Object* Analyzer::calcPiecewise(const Container* c) 0591 { 0592 Object* ret=nullptr; 0593 //Here we have a list of options and finally the otherwise option 0594 foreach(Object *o, c->m_params) { 0595 Container *p=static_cast<Container*>(o); 0596 Q_ASSERT( o->isContainer() && 0597 (p->containerType()==Container::piece || 0598 p->containerType()==Container::otherwise) ); 0599 bool isPiece = p->containerType()==Container::piece; 0600 if(isPiece) { 0601 QScopedPointer<Cn> condition((Cn*) calc(p->m_params[1])); 0602 if(condition->isTrue()) { 0603 ret=calc(p->m_params[0]); 0604 break; 0605 } 0606 0607 } else { 0608 //it is an otherwise 0609 ret=calc(p->m_params.first()); 0610 break; 0611 } 0612 } 0613 0614 if(Q_UNLIKELY(!ret)) { 0615 m_err << QCoreApplication::translate("Error message, no proper condition found.", "Could not find a proper choice for a condition statement."); 0616 ret=new Cn(0.); 0617 } 0618 0619 return ret; 0620 } 0621 0622 Object* Analyzer::calcMath(const Container* c) 0623 { 0624 return calc(*c->constBegin()); 0625 } 0626 0627 Object* Analyzer::calcLambda(const Container* c) 0628 { 0629 Container * cc=c->copy(); 0630 if(cc->bvarCount()>0) 0631 alphaConversion(cc, cc->bvarCi().at(0)->depth()); 0632 Expression::computeDepth(cc); 0633 return cc; 0634 } 0635 0636 Object* Analyzer::calcDeclare(const Container* c) 0637 { 0638 Object *ret=nullptr; 0639 0640 const Ci *var = (const Ci*) c->m_params[0]; 0641 ret=simp(c->m_params[1]->copy()); 0642 Expression::computeDepth(ret); 0643 bool corr = insertVariable(var->name(), ret); 0644 0645 Q_ASSERT(ret && corr); 0646 return ret; 0647 } 0648 0649 template<class T, class Tcontained> 0650 Object* Analyzer::calcElements(const Object* root, T* nv) 0651 { 0652 const T *v=static_cast<const T*>(root); 0653 auto itEnd=v->constEnd(); 0654 0655 for(auto it=v->constBegin(); it!=itEnd; ++it) 0656 nv->appendBranch(static_cast<Tcontained*>(calc(*it))); 0657 0658 return nv; 0659 } 0660 0661 Object* Analyzer::calc(const Object* root) 0662 { 0663 Q_ASSERT(root); 0664 Object* ret=nullptr; 0665 0666 switch(root->type()) { 0667 case Object::container: 0668 ret = operate((const Container*) root); 0669 break; 0670 case Object::apply: 0671 ret = operate((const Apply*) root); 0672 break; 0673 case Object::vector: 0674 ret = calcElements<Vector>(root, new Vector(static_cast<const Vector*>(root)->size())); 0675 break; 0676 case Object::list: 0677 ret = calcElements<List>(root, new List); 0678 break; 0679 case Object::matrix: 0680 ret = calcElements<Matrix, MatrixRow>(root, new Matrix); 0681 break; 0682 case Object::matrixrow: 0683 ret = calcElements<MatrixRow>(root, new MatrixRow); 0684 break; 0685 case Object::value: 0686 case Object::custom: 0687 ret=root->copy(); 0688 break; 0689 case Object::variable: 0690 ret=variableValue((Ci*) root); 0691 if(ret) 0692 ret = calc(ret); 0693 else { 0694 Container* c= new Container(Container::lambda); 0695 c->appendBranch(root->copy()); 0696 ret=c; 0697 } 0698 break; 0699 case Object::oper: 0700 case Object::none: 0701 break; 0702 } 0703 Q_ASSERT(ret); 0704 return ret; 0705 } 0706 0707 bool isNull(Analitza::Operator::OperatorType opt, Object* ret) 0708 { 0709 return ret->type()==Object::value && 0710 ((opt==Operator::_and && static_cast<Cn*>(ret)->value()==0.) || (opt==Operator::_or && static_cast<Cn*>(ret)->value()==1.)); 0711 } 0712 0713 Object* Analyzer::operate(const Apply* c) 0714 { 0715 Object* ret=nullptr; 0716 const Operator& op = c->firstOperator(); 0717 Operator::OperatorType opt=op.operatorType(); 0718 0719 switch(opt) { 0720 case Operator::sum: 0721 ret = sum(*c); 0722 break; 0723 case Operator::product: 0724 ret = product(*c); 0725 break; 0726 case Operator::forall: 0727 ret = forall(*c); 0728 break; 0729 case Operator::exists: 0730 ret = exists(*c); 0731 break; 0732 case Operator::function: 0733 ret = func(*c); 0734 break; 0735 case Operator::diff: 0736 ret = calcDiff(c); 0737 break; 0738 case Operator::map: 0739 ret = calcMap(c); 0740 break; 0741 case Operator::filter: 0742 ret = calcFilter(c); 0743 break; 0744 default: { 0745 int count=c->countValues(); 0746 Q_ASSERT(count>0); 0747 Q_ASSERT( (op.nparams()< 0 && count>1) || 0748 (op.nparams()>-1 && count==op.nparams()) || 0749 opt==Operator::minus); 0750 0751 QString* error=nullptr; 0752 if(count>=2) { 0753 Apply::const_iterator it = c->firstValue(), itEnd=c->constEnd(); 0754 ret = calc(*it); 0755 ++it; 0756 bool stop=isNull(opt, ret); 0757 for(; !stop && it!=itEnd; ++it) { 0758 bool isValue = (*it)->type()==Object::value; 0759 Object* v = isValue ? *it : calc(*it); 0760 if(Q_UNLIKELY(v->isNone())) { 0761 Q_ASSERT(!isValue); 0762 ret = v; 0763 break; 0764 } 0765 ret=Operations::reduce(opt, ret, v, &error); 0766 if(!isValue) 0767 delete v; 0768 0769 if(Q_UNLIKELY(error)) { 0770 m_err.append(*error); 0771 delete error; 0772 error=nullptr; 0773 break; 0774 } 0775 0776 stop=isNull(opt, ret); 0777 } 0778 } else { 0779 ret = calc(*c->firstValue()); 0780 if(Q_LIKELY(!ret->isNone())) { 0781 ret=Operations::reduceUnary(opt, ret, &error); 0782 if(Q_UNLIKELY(error)) { 0783 m_err.append(*error); 0784 delete error; 0785 } 0786 } 0787 } 0788 } break; 0789 } 0790 0791 Q_ASSERT(ret); 0792 return ret; 0793 } 0794 0795 Analyzer::funcContainer Analyzer::operateContainer[Container::domainofapplication+1] = 0796 {nullptr, &Analyzer::calcMath, &Analyzer::calcDeclare, &Analyzer::calcLambda, nullptr,nullptr,nullptr,nullptr,&Analyzer::calcPiecewise,nullptr,nullptr}; 0797 0798 Object* Analyzer::operate(const Container* c) 0799 { 0800 Q_ASSERT(c); 0801 funcContainer f=operateContainer[c->containerType()]; 0802 Q_ASSERT(f); 0803 Object* ret=(this->*f)(c); 0804 0805 Q_ASSERT(ret); 0806 return ret; 0807 } 0808 0809 namespace Analitza 0810 { 0811 template <typename T, typename Iterator> 0812 class TypeBoundingIterator : public BoundingIterator 0813 { 0814 public: 0815 TypeBoundingIterator(QVector<Object*>& runStack, int top, const QVector<Ci*>& vars, T* l) 0816 : iterators(vars.size()), list(l) 0817 , itBegin(l->constBegin()), itEnd(l->constEnd()) 0818 , m_runStack(runStack), m_top(top) 0819 { 0820 int s=vars.size(); 0821 for(int i=0; i<s; i++) { 0822 m_runStack[m_top+i]=*itBegin; 0823 iterators[i]=itBegin; 0824 } 0825 } 0826 0827 ~TypeBoundingIterator() override { delete list; } 0828 0829 virtual bool hasNext() override 0830 { 0831 bool cont=true; 0832 for(int i=iterators.size()-1; cont && i>=0; i--) { 0833 ++iterators[i]; 0834 cont=(iterators[i]==itEnd); 0835 0836 if(cont) 0837 iterators[i]=itBegin; 0838 m_runStack[m_top+i]=*iterators[i]; 0839 } 0840 0841 return !cont; 0842 } 0843 private: 0844 QVector<Iterator> iterators; 0845 T* list; 0846 const Iterator itBegin, itEnd; 0847 QVector<Object*>& m_runStack; 0848 int m_top; 0849 }; 0850 0851 class RangeBoundingIterator : public BoundingIterator 0852 { 0853 public: 0854 RangeBoundingIterator(const QVector<Cn*>& values, Cn* oul, Cn* odl, double step) 0855 : values(values), dl(odl->value()), ul(oul->value()), step(step), objdl(odl), objul(oul) 0856 {} 0857 0858 ~RangeBoundingIterator() override 0859 { 0860 qDeleteAll(values); 0861 delete objdl; 0862 delete objul; 0863 } 0864 0865 bool hasNext() override 0866 { 0867 bool cont=true; 0868 for(int i=values.size()-1; cont && i>=0; i--) { 0869 Cn* v=values[i]; 0870 double curr=v->value()+step; 0871 cont=curr>ul; 0872 0873 v->setValue(cont ? dl : curr); 0874 } 0875 0876 return !cont; 0877 } 0878 0879 private: 0880 const QVector<Cn*> values; 0881 const double dl, ul, step; 0882 Object* objdl; 0883 Object* objul; 0884 }; 0885 } 0886 0887 BoundingIterator* Analyzer::initializeBVars(const Apply* n, int base) 0888 { 0889 BoundingIterator* ret=nullptr; 0890 0891 Object* domain=n->domain(); 0892 0893 if(domain) 0894 { 0895 domain=calc(domain); 0896 ret = initBVarsContainer(n, base, domain); 0897 0898 if(!ret) 0899 delete domain; 0900 } 0901 else 0902 { 0903 Object *objul=calc(n->ulimit()); 0904 Object *objdl=calc(n->dlimit()); 0905 0906 ret = initBVarsRange(n, base, objdl, objul); 0907 0908 if(!ret) { 0909 delete objdl; 0910 delete objul; 0911 } 0912 } 0913 return ret; 0914 } 0915 BoundingIterator* Analyzer::initBVarsContainer(const Analitza::Apply* n, int base, Object* domain) 0916 { 0917 BoundingIterator* ret = nullptr; 0918 QVector<Ci*> bvars=n->bvarCi(); 0919 0920 switch(domain->type()) { 0921 case Object::matrix: 0922 Q_ASSERT(false && "fixme: properly iterate through elements when bounding"); 0923 if(static_cast<Matrix*>(domain)->rowCount()>0) 0924 ret=new TypeBoundingIterator<Matrix, Matrix::const_iterator>(m_runStack, base, bvars, static_cast<Matrix*>(domain)); 0925 break; 0926 case Object::list: 0927 if(static_cast<List*>(domain)->size()>0) 0928 ret=new TypeBoundingIterator<List, List::const_iterator>(m_runStack, base, bvars, static_cast<List*>(domain)); 0929 break; 0930 case Object::vector: 0931 if(static_cast<Vector*>(domain)->size()>0) 0932 ret=new TypeBoundingIterator<Vector, Vector::const_iterator>(m_runStack, base, bvars, static_cast<Vector*>(domain)); 0933 break; 0934 default: 0935 Q_ASSERT(false && "Type not supported for bounding."); 0936 m_err.append(QCoreApplication::tr("Type not supported for bounding.")); 0937 } 0938 return ret; 0939 } 0940 0941 BoundingIterator* Analyzer::initBVarsRange(const Apply* n, int base, Object* objdl, Object* objul) 0942 { 0943 BoundingIterator* ret = nullptr; 0944 if(isCorrect() && objul->type()==Object::value && objdl->type()==Object::value) { 0945 Cn *u=static_cast<Cn*>(objul); 0946 Cn *d=static_cast<Cn*>(objdl); 0947 double ul=u->value(); 0948 double dl=d->value(); 0949 0950 if(dl<=ul) { 0951 QVector<Ci*> bvars=n->bvarCi(); 0952 QVector<Cn*> rr(bvars.size()); 0953 0954 for(int i=0; i<bvars.size(); ++i) { 0955 rr[i]=new Cn(dl); 0956 m_runStack[base+i]=rr[i]; 0957 } 0958 0959 ret=new RangeBoundingIterator(rr, u, d, 1); 0960 } else 0961 m_err.append(QCoreApplication::tr("The downlimit is greater than the uplimit")); 0962 } else 0963 m_err.append(QCoreApplication::tr("Incorrect uplimit or downlimit.")); 0964 return ret; 0965 } 0966 0967 Object* Analyzer::boundedOperation(const Apply& n, const Operator& t, Object* initial) 0968 { 0969 Object* ret=initial; 0970 int top = m_runStack.size(); 0971 m_runStack.resize(top+n.bvarCi().size()); 0972 0973 BoundingIterator* it=initializeBVars(&n, top); 0974 if(!it) 0975 return initial; 0976 0977 QString* correct=nullptr; 0978 Operator::OperatorType type=t.operatorType(); 0979 do { 0980 Object *val=calc(n.m_params.last()); 0981 ret=Operations::reduce(type, ret, val, &correct); 0982 delete val; 0983 delete correct; 0984 } while(Q_LIKELY(it->hasNext() && !correct && !isNull(type, ret))); 0985 0986 m_runStack.resize(top); 0987 0988 delete it; 0989 Q_ASSERT(ret); 0990 return ret; 0991 } 0992 0993 Object* Analyzer::product(const Apply& n) 0994 { 0995 return boundedOperation(n, Operator(Operator::times), new Cn(1.)); 0996 } 0997 0998 Object* Analyzer::sum(const Apply& n) 0999 { 1000 return boundedOperation(n, Operator(Operator::plus), new Cn(0.)); 1001 } 1002 1003 Object* Analyzer::forall(const Apply& n) 1004 { 1005 return boundedOperation(n, Operator(Operator::_and), new Cn(true)); 1006 } 1007 1008 Object* Analyzer::exists(const Apply& n) 1009 { 1010 return boundedOperation(n, Operator(Operator::_or), new Cn(false)); 1011 } 1012 1013 Object* Analyzer::func(const Apply& n) 1014 { 1015 bool borrowed = n.m_params[0]->type()==Object::variable; 1016 Container *function = static_cast<Container*>(borrowed ? variableValue((Ci*) n.m_params[0]) : calc(n.m_params[0])); 1017 1018 // static int ind=0; 1019 // qDebug() << "calling" << qPrintable(QString(++ind, '.')) << n.m_params.first()->toString() << n.toString(); 1020 1021 int bvarsize = n.m_params.size()-1; 1022 QVector<Object*> args(bvarsize); 1023 1024 for(int i=1; i<bvarsize+1; i++) { 1025 args[i-1]=calc(n.m_params[i]); 1026 // qDebug() << "argumen" << qPrintable(QString(ind, '.')) << n.m_params[i]->toString() << "=" << args[i-1]->toString(); 1027 } 1028 1029 Object* ret = calcCallFunction(function, args, n.m_params[0]); 1030 1031 // qDebug() << "called " << qPrintable(QString(ind--, '.')) << n.m_params.first()->toString() << ret->toString(); 1032 if(!borrowed) 1033 delete function; 1034 1035 return ret; 1036 } 1037 1038 Object* Analyzer::calcCallFunction(Container* function, const QVector<Object*>& args, const Object* oper) 1039 { 1040 Object* ret=nullptr; 1041 int bvarsize = args.size(); 1042 1043 if(function && function->m_params.size()>1) { 1044 #ifdef SCRIPT_PROFILER 1045 profiler.push(borrowed? static_cast<Ci*>(n.m_params[0])->name() : function->toString()); 1046 #endif 1047 int top = m_runStack.size(), aux=m_runStackTop; 1048 m_runStack.resize(top+bvarsize+1); 1049 1050 m_runStack[top] = function; 1051 for(int i=0; i<args.size(); i++) { 1052 if (args[i]->type() != Object::none) { 1053 m_runStack[top+i+1] = args[i]; 1054 } else { 1055 m_err += QCoreApplication::tr("Invalid type for parameter '%1'").arg(i+1); 1056 ret = new None(); 1057 1058 return ret; 1059 } 1060 } 1061 m_runStackTop = top; 1062 1063 // qDebug() << "diiiiiiiii" << function->toString() << m_runStack.size() << bvarsize << m_runStackTop << printAll(m_runStack); 1064 ret=calc(function->m_params.last()); 1065 1066 qDeleteAll(m_runStack.begin()+top+1, m_runStack.end()); 1067 1068 m_runStackTop = aux; 1069 m_runStack.resize(top); 1070 } else { 1071 // Q_ASSERT(function ? (function->m_params[0]->type()==Object::variable && function->m_params.size()==1) : n.m_params[0]->type()==Object::variable); 1072 QString id=static_cast<const Ci*>(function ? function->m_params[0] : oper)->name(); 1073 FunctionDefinition* func=m_builtin.function(id); 1074 QList<Expression> expargs; 1075 1076 for(int i=0; i<args.size(); i++) { 1077 if (args[i]->type() != Object::none) { 1078 expargs += Expression(args[i]); 1079 } else { 1080 m_err += QCoreApplication::tr("Invalid type for parameter '%1'").arg(i+1); 1081 ret = new None(); 1082 1083 return ret; 1084 } 1085 } 1086 #ifdef SCRIPT_PROFILER 1087 profiler.push(id); 1088 #endif 1089 Expression exp=(*func)(expargs); 1090 if(Q_UNLIKELY(exp.isCorrect())) { 1091 ret=exp.tree(); 1092 exp.setTree(nullptr); 1093 } else { 1094 m_err += exp.error(); 1095 ret = new None(); 1096 } 1097 } 1098 #ifdef SCRIPT_PROFILER 1099 profiler.pop(); 1100 #endif 1101 1102 return ret; 1103 } 1104 1105 Object* Analyzer::calcMap(const Apply* c) 1106 { 1107 Container* f=static_cast<Container*>(calc(*c->firstValue())); 1108 List* l=static_cast<List*>(calc(*(c->firstValue()+1))); 1109 1110 List::iterator it=l->begin(), itEnd=l->end(); 1111 for(; it!=itEnd; ++it) { 1112 *it = calcCallFunction(f, { *it }, f); 1113 } 1114 1115 delete f; 1116 return l; 1117 } 1118 1119 Object* Analyzer::calcFilter(const Apply* c) 1120 { 1121 Container* f=static_cast<Container*>(calc(*c->firstValue())); 1122 List* l=static_cast<List*>(calc(*(c->firstValue()+1))); 1123 1124 List::iterator it=l->begin(), itEnd=l->end(); 1125 List* ret = new List; 1126 for(; it!=itEnd; ++it) { 1127 QVector<Object*> args(1, (*it)->copy()); 1128 1129 Object* ss=*it; 1130 Cn* val = static_cast<Cn*>(calcCallFunction(f, args, f)); 1131 1132 if(val->isTrue()) { 1133 ret->appendBranch(ss->copy()); 1134 } 1135 delete val; 1136 } 1137 1138 delete l; 1139 delete f; 1140 return ret; 1141 } 1142 1143 1144 Object* Analyzer::calcDiff(const Apply* c) 1145 { 1146 //TODO: Make multibvar 1147 QVector<Ci*> bvars=c->bvarCi(); 1148 1149 //We construct the lambda 1150 Object* o=derivative(bvars[0]->name(), *c->firstValue()); 1151 o=simp(o); 1152 1153 Container* cc=new Container(Container::lambda); 1154 foreach(const Ci* v, bvars) { 1155 Container* bvar=new Container(Container::bvar); 1156 bvar->appendBranch(v->copy()); 1157 cc->appendBranch(bvar); 1158 } 1159 1160 cc->appendBranch(o); 1161 1162 Expression::computeDepth(cc); 1163 return cc; 1164 } 1165 1166 ///////////////////////////////////////////// 1167 ///////////////////////////////////////////// 1168 ///////////////////////////////////////////// 1169 1170 void Analyzer::simplify() 1171 { 1172 if(m_exp.isCorrect() && m_exp.tree()) { 1173 m_runStackTop = 0; 1174 Object* o=simp(m_exp.tree()); 1175 m_exp.setTree(o); 1176 setExpression(m_exp); 1177 } 1178 } 1179 1180 template <class T, class Tcontained> 1181 void Analyzer::iterateAndSimp(T* v) 1182 { 1183 auto it = v->begin(), itEnd=v->end(); 1184 1185 for(; it!=itEnd; ++it) 1186 *it = static_cast<Tcontained*>(simp(*it)); 1187 } 1188 1189 Object* Analyzer::simp(Object* root) 1190 { 1191 Q_ASSERT(root && root->type()!=Object::none); 1192 if(!isCorrect()) 1193 return root; 1194 1195 if(!root->isContainer() && !hasVars(root)) 1196 { 1197 if(root->type()!=Object::value && root->type() !=Object::oper) { 1198 Object* aux=root; 1199 root = calc(root); 1200 delete aux; 1201 1202 if(isLambda(root)) 1203 root = simp(root); 1204 } 1205 } else if(root->type()==Object::vector) { 1206 iterateAndSimp<Vector>(static_cast<Vector*>(root)); 1207 } else if(root->type()==Object::matrix) { 1208 iterateAndSimp<Matrix, MatrixRow>(static_cast<Matrix*>(root)); 1209 } else if(root->type()==Object::matrixrow) { 1210 iterateAndSimp<MatrixRow>(static_cast<MatrixRow*>(root)); 1211 } else if(root->type()==Object::list) { 1212 iterateAndSimp<List>(static_cast<List*>(root)); 1213 } else if(root->type()==Object::apply) { 1214 root = simpApply((Apply*) root); 1215 } else if(root->isContainer()) { 1216 Container *c= (Container*) root; 1217 1218 switch(c->containerType()) { 1219 case Container::piecewise: 1220 root=simpPiecewise(c); 1221 break; 1222 case Container::lambda: { 1223 int top = m_runStackTop; 1224 m_runStackTop = m_runStack.size(); 1225 m_runStack.resize(m_runStackTop+c->bvarCount()+1); 1226 1227 c->m_params.last()=simp(c->m_params.last()); 1228 m_runStack.resize(m_runStackTop); 1229 m_runStackTop = top; 1230 } break; 1231 default: 1232 iterateAndSimp<Container>(c); 1233 break; 1234 } 1235 } 1236 return root; 1237 } 1238 1239 Object* applyTransformations(Object* root, const QList<Transformation>& trans) 1240 { 1241 foreach(const Transformation& t, trans) { 1242 Object* o = t.applyTransformation(root); 1243 if(o) { 1244 delete root; 1245 return o; 1246 } 1247 } 1248 return root; 1249 } 1250 1251 bool actuallyE(const Object* o) 1252 { 1253 return o->type()==Object::variable && static_cast<const Ci*>(o)->name()==QLatin1String("e"); 1254 } 1255 1256 QList<Transformation> simplifications() 1257 { 1258 static QList<Transformation> ret; 1259 if(Q_UNLIKELY(ret.isEmpty())) { 1260 //divide 1261 ret += Transformation(Transformation::parse(QStringLiteral("f/f")), Transformation::parse(QStringLiteral("1"))); 1262 ret += Transformation(Transformation::parse(QStringLiteral("f/1")), Transformation::parse(QStringLiteral("f"))); 1263 1264 //power 1265 ret += Transformation(Transformation::parse(QStringLiteral("0**k")), Transformation::parse(QStringLiteral("0"))); 1266 ret += Transformation(Transformation::parse(QStringLiteral("1**k")), Transformation::parse(QStringLiteral("1"))); 1267 ret += Transformation(Transformation::parse(QStringLiteral("x**1")), Transformation::parse(QStringLiteral("x"))); 1268 ret += Transformation(Transformation::parse(QStringLiteral("(x**y)**z")), Transformation::parse(QStringLiteral("x**(y*z)"))); 1269 1270 //ln 1271 QMap<QString, Transformation::treeCheck> eulerNumber; 1272 eulerNumber.insert(QStringLiteral("e"), actuallyE); 1273 ret += Transformation(Transformation::parse(QStringLiteral("ln e")), Transformation::parse(QStringLiteral("1")), eulerNumber); 1274 } 1275 1276 return ret; 1277 } 1278 1279 Object* Analyzer::simpApply(Apply* c) 1280 { 1281 Object* root=c; 1282 Apply::iterator it; 1283 Operator o = c->firstOperator(); 1284 1285 switch(o.operatorType()) { 1286 case Operator::times: 1287 for(it=c->firstValue(); c->countValues()>1 && it!=c->end();) { 1288 bool d=false; 1289 *it = simp(*it); 1290 1291 if((*it)->type() == Object::value) { 1292 Cn* n = (Cn*) (*it); 1293 if(n->value()==1. && c->countValues()>1) { //1*exp=exp 1294 d=true; 1295 } else if(n->value()==0.) { //0*exp=0 //TODO Change to isZero and return the same type in 0 1296 delete root; 1297 root = new Cn(0.); 1298 return root; 1299 } 1300 } 1301 1302 if(!d) 1303 ++it; 1304 else { 1305 delete *it; 1306 it = c->m_params.erase(it); 1307 } 1308 } 1309 1310 root=simpPolynomials(c); 1311 break; 1312 case Operator::minus: 1313 case Operator::plus: { 1314 // qDebug() << "........................" << c->toString(); 1315 for(Apply::iterator it2=c->begin(), itEnd=c->end(); it2!=itEnd; ++it2) { 1316 *it2 = simp(*it2); 1317 } 1318 1319 // qDebug()<< "PEPEPE" << c->toString(); 1320 if(c->isUnary()) { 1321 if(o==Operator::minus && (*c->firstValue())->type()==Object::value) { 1322 Cn* v = static_cast<Cn*>(*c->firstValue()); 1323 v->rvalue() *= -1; 1324 1325 root=v; 1326 *c->firstValue()=nullptr; 1327 delete c; 1328 c=nullptr; 1329 } 1330 } else { 1331 root=simpPolynomials(c); 1332 c=nullptr; 1333 } 1334 // qDebug()<< "PAAPPA" << root->toString(); 1335 static QList<Transformation> addTrans; 1336 if(addTrans.isEmpty()) { 1337 addTrans += Transformation(Transformation::parse(QStringLiteral("--x")), Transformation::parse(QStringLiteral("x"))); 1338 addTrans += Transformation(Transformation::parse(QStringLiteral("-a--b")), Transformation::parse(QStringLiteral("b-a"))); 1339 } 1340 1341 root = applyTransformations(root, addTrans); 1342 } break; 1343 //TODO: extend to ::product 1344 case Operator::sum: { 1345 1346 QStringList bvars=c->bvarStrings(); 1347 if(c->ulimit()) c->ulimit()=simp(c->ulimit()); 1348 if(c->dlimit()) c->dlimit()=simp(c->dlimit()); 1349 if(c->domain()) c->domain()=simp(c->domain()); 1350 1351 Object *uplimit=c->ulimit(), *downlimit=c->dlimit(), *domain=c->domain(); 1352 1353 //TODO: simplify this code 1354 for(it = c->m_params.begin(); it!=c->end(); ++it) 1355 *it = simp(*it); 1356 1357 //if bvars is empty, we are dealing with an invalid sum() 1358 Object* function = *c->firstValue(); 1359 1360 const auto barsSet = QSet<QString>(bvars.begin(), bvars.end()); 1361 if(!bvars.isEmpty() && !domain && !hasTheVar(barsSet, function)) { 1362 Apply *cDiff=new Apply; 1363 cDiff->appendBranch(new Operator(Operator::minus)); 1364 cDiff->appendBranch(uplimit ->copy()); 1365 cDiff->appendBranch(downlimit->copy()); 1366 1367 Apply *aPlusOne = new Apply; 1368 aPlusOne->appendBranch(new Operator(Operator::plus)); 1369 aPlusOne->appendBranch(new Cn(1.)); 1370 aPlusOne->appendBranch(cDiff); 1371 1372 Apply *nc=new Apply; 1373 nc->appendBranch(new Operator(Operator::times)); 1374 nc->appendBranch(aPlusOne); 1375 nc->appendBranch(function); 1376 1377 c->m_params.last()=nullptr; 1378 delete c; 1379 root=simp(nc); 1380 } else if(function->isApply()) { 1381 root=simpSum(c); 1382 } 1383 1384 } break; 1385 case Operator::card: { 1386 Object* val=simp(*c->firstValue()); 1387 if(val->type()==Object::vector) 1388 { 1389 c->m_params.last()=nullptr; 1390 QString* err=nullptr; 1391 val=Operations::reduceUnary(Operator::card, val, &err); 1392 if(Q_UNLIKELY(err)) { delete err; } 1393 delete c; 1394 root=val; 1395 } 1396 } break; 1397 case Operator::selector: { 1398 c->m_params[0]=simp(c->m_params[0]); 1399 c->m_params[1]=simp(c->m_params[1]); 1400 1401 Object* idx=c->m_params[0]; 1402 Object* value=c->m_params[1]; 1403 if(idx->type()==Object::value && value->type()==Object::vector) { 1404 QString* err=nullptr; 1405 Object* ret=Operations::reduce(Operator::selector, idx, value, &err); 1406 delete err; 1407 1408 if(ret) { 1409 root=ret; 1410 c->m_params[0]=nullptr; 1411 c->m_params[1]=nullptr; 1412 1413 delete c; 1414 } 1415 } 1416 } break; 1417 case Operator::_union: { 1418 Apply::iterator it2=c->firstValue(), itEnd=c->end(); 1419 1420 QVector<Object*> newParams; 1421 for(; it2!=itEnd; ++it2) { 1422 *it2=simp(*it2); 1423 1424 if(newParams.isEmpty()) 1425 newParams.append(*it2); 1426 else { 1427 if((*it2)->type()==Object::list && newParams.last()->type()==Object::list) { 1428 QString* err=nullptr; 1429 Object* ret=Operations::reduce(Operator::_union, newParams.last(), *it2, &err); 1430 delete err; 1431 newParams.last()=ret; 1432 delete *it2; 1433 } else { 1434 newParams.append(*it2); 1435 } 1436 } 1437 *it2=nullptr; 1438 } 1439 1440 if(newParams.last()==nullptr) 1441 newParams.resize(newParams.size()-1); 1442 1443 //if only one, remove union 1444 if(newParams.size()==1) { 1445 delete c; 1446 root=newParams.last(); 1447 } else { 1448 qDeleteAll(c->m_params); 1449 c->m_params=newParams; 1450 root=c; 1451 } 1452 1453 } break; 1454 case Operator::eq: { 1455 bool alleq=true, existsjustvar=false, allButFirstZero=false; 1456 QStringList deps = AnalitzaUtils::dependencies(c, QStringList()); 1457 1458 for(Apply::iterator it2=c->firstValue(), itEnd=c->end(); it2!=itEnd; ++it2) { 1459 *it2 = simp(*it2); 1460 alleq = alleq && equalTree(*c->firstValue(), *it2); 1461 existsjustvar = existsjustvar || (*it2)->type()==Object::variable; 1462 allButFirstZero = (it2==c->firstValue() || (*it2)->isZero()); 1463 } 1464 1465 if(alleq) { 1466 delete c; 1467 root = new Cn(true); 1468 } else if(!existsjustvar && deps.size()==1) { 1469 if(allButFirstZero) { 1470 Analitza::Apply::iterator first = c->firstValue(); 1471 root = *first; 1472 c->m_params.erase(first); 1473 delete c; 1474 } else { 1475 Apply* a = new Apply; 1476 a->appendBranch(new Operator(Operator::minus)); 1477 1478 for(Apply::const_iterator it2=c->constBegin(), itEnd=c->constEnd(); it2!=itEnd; ++it2) { 1479 a->appendBranch(*it2); 1480 } 1481 c->m_params.clear(); 1482 delete c; 1483 1484 root = simp(a); 1485 } 1486 1487 if(root->type()==Object::apply) { 1488 QList<Object*> r = findRoots(deps.first(), static_cast<Apply*>(root)); 1489 1490 if(r.isEmpty()) { 1491 Apply* na = new Apply; 1492 na->appendBranch(new Operator(Operator::eq)); 1493 na->appendBranch(root); 1494 na->appendBranch(new Cn(0.)); 1495 root=na; 1496 } else if(r.size() == 1) { 1497 Apply* a = new Apply; 1498 a->appendBranch(new Operator(Operator::eq)); 1499 a->appendBranch(new Ci(deps.first())); 1500 a->appendBranch(r.first()); 1501 delete root; 1502 root = a; 1503 } else { 1504 Apply* na = new Apply; 1505 na->appendBranch(new Operator(Operator::_or)); 1506 foreach(Object* o, r) { 1507 Apply* a = new Apply; 1508 a->appendBranch(new Operator(Operator::eq)); 1509 a->appendBranch(new Ci(deps.first())); 1510 a->appendBranch(o); 1511 na->appendBranch(a); 1512 } 1513 delete root; 1514 root = na; 1515 } 1516 } else if(!root->isZero()) { 1517 delete root; 1518 root = new Cn(false); 1519 } 1520 } 1521 1522 } break; 1523 case Operator::function: { 1524 Object* function=c->m_params[0]; 1525 1526 Container* cfunc=nullptr; 1527 QList<Ci*> bvars; 1528 if(function->isContainer()) { 1529 cfunc=(Container*) function; 1530 Q_ASSERT(cfunc->containerType()==Container::lambda); 1531 bvars=cfunc->bvarCi(); 1532 } 1533 1534 bool canRemove=true; 1535 it=c->begin()+1; 1536 for(int i=0; it!=c->end(); ++it, ++i) { 1537 *it = simp(*it); 1538 canRemove &= (*it)->type()==Object::variable || (cfunc && countDepth(bvars[i]->depth(), cfunc->m_params.last())==1); 1539 } 1540 1541 if(cfunc && canRemove) { 1542 int i=0; 1543 foreach(Ci* var, bvars) { 1544 replaceDepth(var->depth(), cfunc->m_params.last(), c->m_params[i+1]); 1545 i++; 1546 } 1547 1548 root=simp(cfunc->m_params.last()); 1549 cfunc->m_params.last()=nullptr; 1550 delete c; 1551 } 1552 } break; 1553 default: 1554 if(c->ulimit()) 1555 c->ulimit()=simp(c->ulimit()); 1556 if(c->dlimit()) 1557 c->dlimit()=simp(c->dlimit()); 1558 if(c->domain()) 1559 c->domain()=simp(c->domain()); 1560 1561 iterateAndSimp<Apply>(c); 1562 1563 root = applyTransformations(root, simplifications()); 1564 break; 1565 } 1566 1567 return root; 1568 } 1569 1570 QList<Object*> Analyzer::findRoots(const QString& dep, const Object* o) 1571 { 1572 switch(o->type()) { 1573 case Object::apply: return findRootsApply(dep, static_cast<const Apply*>(o)); 1574 case Object::variable: return QList<Object*>() << new Cn(0.); 1575 default: 1576 return QList<Object*>(); 1577 } 1578 } 1579 1580 QList<Object*> Analyzer::findRootsApply(const QString& dep, const Apply* a) 1581 { 1582 Operator op=a->firstOperator(); 1583 QList<Object*> ret; 1584 switch(op.operatorType()) { 1585 case Operator::plus: 1586 case Operator::minus: { 1587 Object* varTree = nullptr; 1588 //f(x)-w=0 => f(x)=w => x=f-1(x) 1589 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) { 1590 bool hasvars = hasVars(*it); 1591 if(hasvars && varTree) { 1592 varTree = nullptr; //we don't support having more than 1 variable in the minus yet 1593 return QList<Object*>(); 1594 } 1595 1596 if(hasvars && ((*it)->type() == Object::variable || (*it)->isApply())) { 1597 if((*it)->isApply()) { 1598 const Apply* a = static_cast<const Apply*>(*it); 1599 if(!a->isUnary() || a->firstOperator().inverse().operatorType()==Operator::none) 1600 break; 1601 } 1602 varTree = *it; 1603 } 1604 } 1605 1606 if(varTree) { 1607 Apply* na = nullptr; 1608 Object* value = nullptr; 1609 if(a->countValues()>2) { 1610 na = new Apply; 1611 na->appendBranch(new Operator(a->firstOperator().inverse())); 1612 value = na; 1613 } 1614 1615 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) { 1616 if(*it != varTree) { 1617 if(na) 1618 na->appendBranch((*it)->copy()); 1619 else { 1620 Q_ASSERT(!value); 1621 value = (*it)->copy(); 1622 } 1623 } 1624 } 1625 1626 Q_ASSERT(value); 1627 if(varTree->isApply()) { 1628 Operator inv = static_cast<const Apply*>(varTree)->firstOperator().inverse(); 1629 Apply* aa = new Apply; 1630 aa->appendBranch(inv.copy()); 1631 aa->appendBranch(value); 1632 value = calc(aa); 1633 delete aa; 1634 } 1635 1636 if(op==Operator::minus) { 1637 ret += value; 1638 } else { 1639 Apply* aa = new Apply; 1640 aa->appendBranch(new Operator(Operator::minus)); 1641 aa->appendBranch(value); 1642 ret += calc(aa); 1643 delete aa; 1644 } 1645 } 1646 } break; 1647 case Operator::times: 1648 for(Apply::const_iterator it=a->constBegin(), itEnd=a->constEnd(); it!=itEnd; ++it) { 1649 ret += findRoots(dep, static_cast<Apply*>(*it)); 1650 } 1651 break; 1652 case Operator::divide: { // f/g 1653 Object* f = *a->firstValue(); 1654 Object* g = *(a->firstValue()+1); 1655 ret = findRoots(dep, f); 1656 1657 for(QList<Object*>::iterator it = ret.begin(), itEnd=ret.end(); it!=itEnd; ) { 1658 bool erase = false; 1659 1660 Object* val = testResult(g, dep, *it); 1661 erase = val->isZero(); 1662 delete val; 1663 1664 if(erase) { 1665 delete *it; 1666 it = ret.erase(it); 1667 } else 1668 ++it; 1669 } 1670 } break; 1671 default: { 1672 Operator inv = op.inverse(); 1673 if(inv.operatorType()!=Operator::none && a->isUnary()) { 1674 Apply* aa = new Apply; 1675 aa->appendBranch(inv.copy()); 1676 aa->appendBranch(new Cn(0.)); 1677 ret += calc(aa); 1678 delete aa; 1679 } 1680 } break; 1681 } 1682 return ret; 1683 } 1684 1685 Object* Analyzer::testResult(const Object* o, const QString& var, const Object* val) 1686 { 1687 SubstituteExpression s; 1688 QMap<QString, const Object*> subs; 1689 subs.insert(var, val); 1690 1691 QScopedPointer<Object> sometree(s.run(o, subs)); 1692 return calc(sometree.data()); 1693 } 1694 1695 Object* Analyzer::simpPolynomials(Apply* c) 1696 { 1697 Q_ASSERT(c!=nullptr && c->isApply()); 1698 1699 Polynomial monos(c); 1700 1701 c->m_params.clear(); 1702 delete c; 1703 c=nullptr; 1704 1705 Object *root=monos.toObject(); 1706 1707 return root; 1708 } 1709 1710 Object* Analyzer::simpSum(Apply* c) 1711 { 1712 Object* ret=c; 1713 Apply* cval=static_cast<Apply*>(*c->firstValue()); 1714 1715 if(cval->isApply() && cval->firstOperator()==Operator::times) { 1716 const auto &bvarString = c->bvarStrings(); 1717 QSet<QString> bvars = QSet<QString>(bvarString.begin(), bvarString.end()); 1718 QVector<Object*> sum, out; 1719 Apply::iterator it=cval->firstValue(), itEnd=cval->end(); 1720 int removed=0; 1721 for(; it!=itEnd; ++it) { 1722 if(hasTheVar(bvars, *it)) { 1723 sum.append(*it); 1724 } else { 1725 out.append(*it); 1726 *it=nullptr; 1727 ++removed; 1728 } 1729 } 1730 1731 if(removed>0) { 1732 Apply* nc=new Apply; 1733 nc->appendBranch(new Operator(Operator::times)); 1734 nc->m_params << out << c; 1735 1736 if(sum.count()==1) { 1737 cval->m_params.clear(); 1738 delete cval; 1739 c->m_params.last()=sum.last(); 1740 } else { 1741 cval->m_params=sum; 1742 } 1743 1744 ret=simp(nc); 1745 } 1746 } 1747 1748 return ret; 1749 } 1750 1751 Object* Analyzer::simpPiecewise(Container *c) 1752 { 1753 Object *root=c; 1754 //Here we have a list of options and finally the otherwise option 1755 Container *otherwise=nullptr; 1756 Container::const_iterator it=c->m_params.constBegin(), itEnd=c->constEnd(); 1757 QList<Object*> newList; 1758 1759 for(; !otherwise && it!=itEnd; ++it) { 1760 Container *p=static_cast<Container*>(*it); 1761 Q_ASSERT( (*it)->isContainer() && 1762 (p->containerType()==Container::piece || p->containerType()==Container::otherwise) ); 1763 bool isPiece = p->containerType()==Container::piece; 1764 1765 p->m_params.last()=simp(p->m_params.last()); 1766 1767 if(isPiece) { 1768 if(p->m_params[1]->type()==Object::value) { 1769 Cn* cond=static_cast<Cn*>(p->m_params[1]); 1770 if(cond->isTrue()) { 1771 delete p->m_params.takeLast(); 1772 p->setContainerType(Container::otherwise); 1773 isPiece=false; 1774 1775 p->m_params[0]=simp(p->m_params[0]); 1776 otherwise=p; 1777 newList.append(p); 1778 } else { 1779 delete p; 1780 } 1781 } else { 1782 //TODO: It would be nice if we could simplify: 1783 // if(x=n) simplify x as n 1784 p->m_params[0]=simp(p->m_params[0]); 1785 newList.append(p); 1786 } 1787 } else { //it is an otherwise 1788 otherwise=p; 1789 newList.append(p); 1790 } 1791 } 1792 qDeleteAll(it, itEnd); 1793 1794 if(newList.count()==1 && otherwise) { 1795 root=otherwise->m_params.takeAt(0); 1796 delete otherwise; 1797 c->m_params.clear(); 1798 delete c; 1799 } else 1800 c->m_params = newList; 1801 return root; 1802 } 1803 1804 Expression Analyzer::derivative(const QString& var) 1805 { 1806 Q_ASSERT(m_exp.isCorrect() && m_exp.tree()); 1807 1808 QStringList vars; 1809 Object* deriv=m_exp.tree(); 1810 if(m_exp.isLambda()){ 1811 Q_ASSERT(deriv->isContainer()); 1812 Container* lambda=(Container*) deriv; 1813 if(lambda->containerType()==Container::math) { 1814 Q_ASSERT(lambda->m_params.first()->isContainer()); 1815 lambda = (Container*) lambda->m_params.first(); 1816 } 1817 Q_ASSERT(lambda->containerType()==Container::lambda); 1818 1819 vars=lambda->bvarStrings(); 1820 deriv=lambda->m_params.last(); 1821 } else 1822 vars += var; 1823 1824 // Q_ASSERT(hasTheVar(QSet<QString>() << var, deriv)); 1825 Object* o = derivative(var, deriv); 1826 o=simp(o); 1827 Container* lambda=new Container(Container::lambda); 1828 foreach(const QString& dep, vars) { 1829 Container* bvar=new Container(Container::bvar); 1830 bvar->appendBranch(new Ci(dep)); 1831 lambda->appendBranch(bvar); 1832 } 1833 lambda->appendBranch(o); 1834 Expression::computeDepth(lambda); 1835 return Expression(lambda); 1836 } 1837 1838 Expression Analyzer::dependenciesToLambda() const 1839 { 1840 if(m_hasdeps && m_exp.tree()) { 1841 QStringList deps=dependencies(m_exp.tree(), m_vars->keys()); 1842 Container* cc=new Container(Container::lambda); 1843 foreach(const QString& dep, deps) { 1844 Container* bvar=new Container(Container::bvar); 1845 bvar->appendBranch(new Ci(dep)); 1846 cc->appendBranch(bvar); 1847 } 1848 1849 const Object* root=m_exp.tree(); 1850 if(root->isContainer()) { 1851 const Container* c=static_cast<const Container*>(root); 1852 if(c->containerType()==Container::math) { 1853 root=c->m_params.first(); 1854 } 1855 } 1856 cc->appendBranch(root->copy()); 1857 1858 Container* math=new Container(Container::math); 1859 math->appendBranch(cc); 1860 1861 Expression::computeDepth(math); 1862 return Expression(math); 1863 } else { 1864 return m_exp; 1865 } 1866 } 1867 1868 bool Analyzer::insertVariable(const QString & name, const Expression & value) 1869 { 1870 return insertVariable(name, value.tree()); 1871 } 1872 1873 bool Analyzer::insertVariable(const QString & name, const Object * value) 1874 { 1875 bool wrong=!isLambda(value) && hasTheVar(QSet<QString>() << name, value); 1876 if(wrong) 1877 m_err << QCoreApplication::translate("By a cycle i mean a variable that depends on itself", "Defined a variable cycle"); 1878 else 1879 m_vars->modify(name, value); 1880 1881 return !wrong; 1882 } 1883 1884 Cn* Analyzer::insertValueVariable(const QString& name, double value) 1885 { 1886 Cn* val=m_vars->modify(name, value); 1887 return val; 1888 } 1889 1890 double Analyzer::derivative(const QVector<Object*>& values ) 1891 { 1892 //c++ numerical recipes p. 192. Only for f' 1893 //Image 1894 Q_ASSERT(m_exp.isCorrect() && m_exp.tree()); 1895 Q_ASSERT(values.size()==m_exp.bvarList().size()); 1896 1897 setStack(values); 1898 1899 Expression e1(calculateLambda()); 1900 if(!isCorrect()) 1901 return 0.; 1902 1903 //Image+h 1904 double h=0.0000000001; 1905 for(int i=0; i<values.size(); i++) { 1906 // volatile double temp=valp.second+h; 1907 // double hh=temp-valp.second; 1908 1909 Q_ASSERT(values[i]->type()==Object::value); 1910 Cn* v=static_cast<Cn*>(values[i]); 1911 v->setValue(v->value()+h); 1912 } 1913 1914 Expression e2(calculateLambda()); 1915 if(!isCorrect()) 1916 return 0.; 1917 1918 if(!e1.isReal() || !e2.isReal()) { 1919 m_err << QCoreApplication::tr("The result is not a number"); 1920 return 0; 1921 } 1922 1923 return (e2.toReal().value()-e1.toReal().value())/h; 1924 } 1925 1926 Analitza::Object* Analyzer::variableValue(Ci* var) 1927 { 1928 Object* ret; 1929 1930 // qDebug() << "ziiiiiiii" << var->name() << '('<< m_runStackTop << '+' << var->depth() << ')' << printAll(m_runStack); 1931 if(var->depth()>=0) 1932 ret = m_runStack[m_runStackTop + var->depth()]; 1933 else 1934 ret = m_vars->value(var->name()); 1935 1936 // static int hits = 0, misses = 0; 1937 // if(var->depth()>=0) hits++; else misses++; 1938 // qDebug() << "pepepe" << hits << misses; 1939 return ret; 1940 } 1941 1942 Object* Analyzer::applyAlpha(Object* o, int min) 1943 { 1944 if(o) 1945 switch(o->type()) { 1946 case Object::container: alphaConversion(static_cast<Container*>(o), min); break; 1947 case Object::vector: alphaConversion<Vector>(static_cast<Vector*>(o), min); break; 1948 case Object::list: alphaConversion<List>(static_cast<List*>(o), min); break; 1949 case Object::matrix: alphaConversion<Matrix, MatrixRow>(static_cast<Matrix*>(o), min); break; 1950 case Object::matrixrow: alphaConversion<MatrixRow>(static_cast<MatrixRow*>(o), min); break; 1951 case Object::apply: alphaConversion(static_cast<Apply*>(o), min); break; 1952 case Object::variable: { 1953 Ci *var = static_cast<Ci*>(o); 1954 int depth = var->depth(); 1955 // qDebug() << "puuuu" << var->name() << depth << '<' << min << printAll(m_runStack); 1956 if(depth>0 && depth<min && m_runStackTop+var->depth()<m_runStack.size()) { 1957 Object* newvalue = variableValue(var); 1958 if(newvalue) { 1959 delete var; 1960 return newvalue->copy(); 1961 } 1962 } 1963 } break; 1964 case Object::none: 1965 case Object::value: 1966 case Object::oper: 1967 case Object::custom: 1968 break; 1969 } 1970 return o; 1971 } 1972 1973 template <class T, class Tcontained> 1974 void Analyzer::alphaConversion(T* o, int min) 1975 { 1976 Q_ASSERT(o); 1977 auto it=o->begin(), itEnd=o->end(); 1978 for(; it!=itEnd; ++it) { 1979 *it = static_cast<Tcontained*>(applyAlpha(*it, min)); 1980 } 1981 } 1982 1983 void Analyzer::alphaConversion(Container* o, int min) 1984 { 1985 Q_ASSERT(o); 1986 Container::iterator it=o->begin(), itEnd=o->end(); 1987 for(; it!=itEnd; ++it) { 1988 if((*it)->type()==Object::container && static_cast<Container*>(*it)->containerType()==Container::bvar) 1989 continue; 1990 1991 *it = applyAlpha(*it, min); 1992 } 1993 } 1994 1995 void Analyzer::alphaConversion(Apply* o, int min) 1996 { 1997 Q_ASSERT(o); 1998 o->ulimit()=applyAlpha(o->ulimit(), min); 1999 o->dlimit()=applyAlpha(o->dlimit(), min); 2000 o->domain()=applyAlpha(o->domain(), min); 2001 2002 Apply::iterator it=o->firstValue(), itEnd=o->end(); 2003 for(; it!=itEnd; ++it) 2004 *it = applyAlpha(*it, min); 2005 } 2006 2007 BuiltinMethods* Analyzer::builtinMethods() 2008 { 2009 return &m_builtin; 2010 }