1 /*************************************************************************************
2 * Copyright (C) 2007-2009 by Aleix Pol <aleixpol@kde.org> *
3 * Copyright (C) 2014 by Percy Camilo T. Aucahuasi <percy.camilo.ta@gmail.com> *
4 * *
5 * This program is free software; you can redistribute it and/or *
6 * modify it under the terms of the GNU General Public License *
7 * as published by the Free Software Foundation; either version 2 *
8 * of the License, or (at your option) any later version. *
9 * *
10 * This program is distributed in the hope that it will be useful, *
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13 * GNU General Public License for more details. *
14 * *
15 * You should have received a copy of the GNU General Public License *
16 * along with this program; if not, write to the Free Software *
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
18 *************************************************************************************/
19
20 #include "analitzautils.h"
21
22 #include "abstractexpressionvisitor.h"
23 #include "vector.h"
24 #include "value.h"
25 #include "list.h"
26 #include "variable.h"
27 #include "container.h"
28 #include "variables.h"
29 #include "expression.h"
30 #include "apply.h"
31 #include <QVariant>
32 #include "customobject.h"
33 #include "matrix.h"
34
35 using namespace Analitza;
36 namespace AnalitzaUtils
37 {
38
dependencies(const Object * o,const QStringList & scope)39 QStringList dependencies(const Object* o, const QStringList& scope)
40 {
41 Q_ASSERT(o);
42
43 QSet<QString> ret;
44 switch(o->type()) {
45 case Object::variable: {
46 Ci *i = (Ci*) o;
47 if(!scope.contains(i->name()))
48 ret += i->name();
49 } break;
50 case Object::matrix: {
51 const Matrix *v=(const Matrix*) o;
52 for(Matrix::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
53 ret += dependencies(*it, scope).toSet();
54 }
55 } break;
56 case Object::vector: {
57 const Vector *v=(const Vector*) o;
58 for(Vector::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
59 ret += dependencies(*it, scope).toSet();
60 }
61 } break;
62 case Object::list: {
63 const List *v=(const List*) o;
64 for(List::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
65 ret += dependencies(*it, scope).toSet();
66 }
67 } break;
68 case Object::matrixrow: {
69 const MatrixRow *v=(const MatrixRow*) o;
70 for(MatrixRow::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
71 ret += dependencies(*it, scope).toSet();
72 }
73 } break;
74 case Object::container: {
75 const Container *c = static_cast<const Container*>(o);
76 int skip=c->bvarCount();
77 QStringList newScope=scope+c->bvarStrings();
78 if(c->containerType()==Container::declare) {
79 newScope.append(static_cast<const Ci*>(*c->constBegin())->name());
80 skip++;
81 }
82
83 for(Container::const_iterator it=c->constBegin()+skip, itEnd=c->constEnd(); it!=itEnd; ++it) {
84 ret += dependencies(*it, newScope).toSet();
85 }
86 } break;
87 case Object::apply: {
88 const Apply* c = static_cast<const Apply*>(o);
89 Apply::const_iterator it = c->firstValue()/*, first = c->firstValue()*/;
90
91 Object* ul=c->ulimit(), *dl=c->dlimit(), *domain=c->domain();
92
93 //uplimit and downlimit are in the parent scope
94 if(ul) ret += dependencies(ul, scope).toSet();
95 if(dl) ret += dependencies(dl, scope).toSet();
96 if(domain) ret += dependencies(domain, scope).toSet();
97
98 if(c->firstOperator()==Operator::function) {
99 ret += dependencies(c->m_params[0], scope).toSet();
100 }
101
102 QStringList newScope=scope+c->bvarStrings();
103 for(; it!=c->constEnd(); ++it) {
104 ret += dependencies(*it, newScope).toSet();
105 }
106 } break;
107 case Object::none:
108 case Object::custom:
109 case Object::value:
110 case Object::oper:
111 break;
112 }
113
114 return ret.values();
115 }
116
hasTheVar(const QSet<QString> & vars,const Object * o)117 bool hasTheVar(const QSet<QString> & vars, const Object * o)
118 {
119 if(!o)
120 return false;
121
122 bool found=false;
123 const Ci* cand;
124 switch(o->type()) {
125 case Object::vector: {
126 const Vector *v=static_cast<const Vector*>(o);
127 Vector::const_iterator it, itEnd=v->constEnd();
128 for(it=v->constBegin(); it!=itEnd; ++it) {
129 found |= hasTheVar(vars, *it);
130 }
131 } break;
132 case Object::matrix: {
133 const Matrix *v=static_cast<const Matrix*>(o);
134 Matrix::const_iterator it, itEnd=v->constEnd();
135 for(it=v->constBegin(); it!=itEnd; ++it) {
136 found |= hasTheVar(vars, *it);
137 }
138 } break;
139 case Object::matrixrow: {
140 const MatrixRow *v=static_cast<const MatrixRow*>(o);
141 MatrixRow::const_iterator it, itEnd=v->constEnd();
142 for(it=v->constBegin(); it!=itEnd; ++it) {
143 found |= hasTheVar(vars, *it);
144 }
145 } break;
146 case Object::list: {
147 const List *v=static_cast<const List*>(o);
148 List::const_iterator it, itEnd=v->constEnd();
149 for(it=v->constBegin(); it!=itEnd; ++it) {
150 found |= hasTheVar(vars, *it);
151 }
152 } break;
153 case Object::container: {
154 const Container *c=static_cast<const Container*>(o);
155 QSet<QString> bvars=c->bvarStrings().toSet(), varsCopy=vars;
156 foreach(const QString &var, bvars) {
157 varsCopy.remove(var);
158 }
159 found=hasTheVar(varsCopy, c);
160 } break;
161 case Object::apply: {
162 const Apply *c=static_cast<const Apply*>(o);
163 QSet<QString> bvars=c->bvarStrings().toSet(), varsCopy=vars;
164 foreach(const QString &var, bvars) {
165 varsCopy.remove(var);
166 }
167 found=hasTheVar(varsCopy, c);
168 } break;
169 case Object::variable:
170 cand=static_cast<const Ci*>(o);
171 found=vars.contains(cand->name());
172 break;
173 case Object::value:
174 case Object::custom:
175 case Object::oper:
176 case Object::none:
177 found=false;
178 break;
179 }
180 return found;
181 }
182
hasTheVar(const QSet<QString> & vars,const Container * c)183 bool hasTheVar(const QSet<QString> & vars, const Container* c)
184 {
185 bool found=false;
186 if(c->containerType()!=Container::bvar) {
187 Container::const_iterator it=c->constBegin(), itEnd=c->constEnd();
188 for(; !found && it!=itEnd; ++it) {
189 found=hasTheVar(vars, *it);
190 }
191 }
192 return found;
193 }
194
hasTheVar(const QSet<QString> & vars,const Apply * a)195 bool hasTheVar(const QSet<QString> & vars, const Apply* a)
196 {
197 bool found=hasTheVar(vars, a->ulimit()) || hasTheVar(vars, a->dlimit()) || hasTheVar(vars, a->domain());
198 Apply::const_iterator it=a->firstValue(), itEnd=a->constEnd();
199 for(; !found && it!=itEnd; ++it) {
200 found=hasTheVar(vars, *it);
201 }
202 return found;
203 }
204
isLambda(const Object * o)205 bool isLambda(const Object* o)
206 {
207 return o->isContainer() && static_cast<const Container*>(o)->containerType()==Container::lambda;
208 }
209
hasVars(const Analitza::Object * o,const QStringList & bvars)210 bool hasVars(const Analitza::Object* o, const QStringList& bvars)
211 {
212 Q_ASSERT(o);
213
214 bool r=false;
215 switch(o->type()) {
216 case Object::variable: {
217 Ci *i = (Ci*) o;
218 r=!bvars.contains(i->name());
219
220 } break;
221 case Object::vector: {
222 Vector *v=(Vector*) o;
223 for(Vector::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
224 r |= hasVars(*it, bvars);
225 }
226 } break;
227 case Object::matrix: {
228 Matrix *v=(Matrix*) o;
229 for(Matrix::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
230 r |= hasVars(*it, bvars);
231 }
232 } break;
233 case Object::matrixrow: {
234 MatrixRow *v=(MatrixRow*) o;
235 for(MatrixRow::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
236 r |= hasVars(*it, bvars);
237 }
238 } break;
239 case Object::list: {
240 List *v=(List*) o;
241 for(List::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it) {
242 r |= hasVars(*it, bvars);
243 }
244 } break;
245 case Object::container: {
246 const Container *c = (const Container*) o;
247
248 QStringList newScope=bvars+c->bvarStrings();
249 Container::const_iterator it=c->m_params.constBegin(), itEnd=c->m_params.constEnd();
250 if(c->containerType()==Container::declare) {
251 newScope += static_cast<const Ci*>(*c->constBegin())->name();
252 ++it;
253 }
254
255 for(; it!=itEnd; ++it) {
256 r |= hasVars(*it, newScope);
257 }
258 } break;
259 case Object::apply: {
260 const Apply *c = (const Apply*) o;
261
262 const QStringList scope=bvars+c->bvarStrings();
263 Object* ul=c->ulimit(), *dl=c->dlimit(), *dn=c->domain();
264
265 //uplimit and downlimit are in the parent scope
266 if(ul) r |= hasVars(ul, bvars);
267 if(dl) r |= hasVars(dl, bvars);
268 if(dn) r |= hasVars(dn, bvars);
269
270 Apply::const_iterator it = c->firstValue();
271 for(; !r && it!=c->constEnd(); ++it) {
272 r |= hasVars(*it, scope);
273 }
274 } break;
275 case Object::none:
276 case Object::value:
277 case Object::oper:
278 case Object::custom:
279 r=false;
280 }
281 return r;
282 }
283
284 struct ObjectWalker : public AbstractExpressionVisitor
285 {
ObjectWalkerAnalitzaUtils::ObjectWalker286 ObjectWalker(const QByteArray& pref) : ind(0), m_prefix(pref) {}
287
visitAnalitzaUtils::ObjectWalker288 virtual QVariant visit(const None* var) override
289 { qDebug() << prefix().constData() << "| none: " << var->toString(); return QString(); }
290
visitAnalitzaUtils::ObjectWalker291 virtual QVariant visit(const Operator* root) override
292 { qDebug() << prefix().constData() << "| operator: " << root->toString(); return QString(); }
293
visitAnalitzaUtils::ObjectWalker294 virtual QVariant visit(const Ci* var) override
295 {
296 QString value;
297 if(var->depth()>=0)
298 value="stack("+QString::number(var->depth())+')';
299 else
300 value=QStringLiteral("symbols");
301
302 qDebug() << prefix().constData() << "| variable: " << var->name() << "depth:" << var->depth() << "Val:" << value;
303 return QString();
304 }
305
visitAnalitzaUtils::ObjectWalker306 virtual QVariant visit(const Cn* num) override
307 { qDebug() << prefix().constData() << "| num: " << num->value() << " format: " << num->format(); return QString(); }
308
visitAnalitzaUtils::ObjectWalker309 virtual QVariant visit(const CustomObject* c) override
310 { qDebug() << prefix().constData() << "| custom " << c; return QString(); }
311
312
visitAnalitzaUtils::ObjectWalker313 virtual QVariant visit(const Container* c) override
314 {
315 qDebug() << prefix().constData() << "| cont: " << c->tagName();// << "=" << c->toString();
316 ind++;
317 for(Container::const_iterator it=c->m_params.constBegin(); it<c->constEnd(); ++it)
318 visitNow(*it);
319 ind--;
320 return QString();
321 }
322
visitAnalitzaUtils::ObjectWalker323 virtual QVariant visit(const Apply* c) override
324 {
325 qDebug() << prefix().constData() << "| apply op:" << c->firstOperator().toString();
326 ind++;
327 if(c->ulimit()) { qDebug() << prefix().constData() << "ul: "; visitNow(c->ulimit()); }
328 if(c->dlimit()) { qDebug() << prefix().constData() << "dl: "; visitNow(c->dlimit()); }
329 if(!c->bvarCi().isEmpty()) { qDebug() << prefix().constData() << "bvars: " << c->bvarStrings(); }
330
331 for(Apply::const_iterator it=c->m_params.constBegin(); it<c->constEnd(); ++it)
332 visitNow(*it);
333 ind--;
334 return QString();
335 }
336
visitAnalitzaUtils::ObjectWalker337 virtual QVariant visit(const Vector* v) override
338 {
339 qDebug() << prefix().constData() << "| vector: " << v->size();
340 ind++;
341 for(Vector::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it)
342 visitNow(*it);
343 ind--;
344 return QString();
345 }
346
visitAnalitzaUtils::ObjectWalker347 virtual QVariant visit(const List* v) override
348 {
349 qDebug() << prefix().constData() << "| list: " << v->size();
350 ind++;
351 for(List::const_iterator it=v->constBegin(); it!=v->constEnd(); ++it)
352 visitNow(*it);
353 ind--;
354 return QString();
355 }
356
visitAnalitzaUtils::ObjectWalker357 virtual QVariant visit(const Matrix* m) override {
358 qDebug() << prefix().constData() << "| matrix: ";
359 ind++;
360 for(Matrix::const_iterator it=m->constBegin(); it!=m->constEnd(); ++it)
361 visitNow(*it);
362 ind--;
363 return QString();
364 }
365
visitAnalitzaUtils::ObjectWalker366 virtual QVariant visit(const MatrixRow* m) override {
367 qDebug() << prefix().constData() << "| matrix: ";
368 ind++;
369 for(MatrixRow::const_iterator it=m->constBegin(); it!=m->constEnd(); ++it)
370 visitNow(*it);
371 ind--;
372 return QString();
373 }
374
prefixAnalitzaUtils::ObjectWalker375 QByteArray prefix()
376 {
377 QByteArray ret(m_prefix);
378 for(int i=0; i<ind; i++)
379 ret += " |_____";
380 return ret;
381 }
382
visitNowAnalitzaUtils::ObjectWalker383 void visitNow(const Object* o) { if(o) o->accept(this); else qDebug() << prefix().constData() << "Null" ;}
384
resultAnalitzaUtils::ObjectWalker385 QVariant result() const override { return QString(); }
386
387 int ind;
388 QByteArray m_prefix;
389 };
390
objectWalker(const Analitza::Expression & o,const QByteArray & prefix)391 void objectWalker(const Analitza::Expression& o, const QByteArray& prefix)
392 {
393 objectWalker(o.tree(), prefix);
394 }
395
objectWalker(const Object * root,const QByteArray & prefix)396 void objectWalker(const Object* root, const QByteArray& prefix)
397 {
398 ObjectWalker o(prefix);
399 o.visitNow(root);
400
401 qDebug() << prefix.constData() << ';';
402 }
403
equalTree(const Object * o1,const Object * o2)404 bool equalTree(const Object * o1, const Object * o2)
405 {
406 Q_ASSERT((o1 && o2) || (!o1 && !o2));
407 if(o1==o2)
408 return true;
409 else if(o1->type()!=o2->type())
410 return false;
411
412 bool eq = false;
413 switch(o2->type()) {
414 case Object::variable:
415 eq = *static_cast<const Ci*>(o1)==*static_cast<const Ci*>(o2);
416 break;
417 case Object::value:
418 eq = *static_cast<const Cn*>(o1)==*static_cast<const Cn*>(o2);
419 break;
420 case Object::container:
421 eq = *static_cast<const Container*>(o1)==*static_cast<const Container*>(o2);
422 break;
423 case Object::oper:
424 eq = *static_cast<const Operator*>(o1)==*static_cast<const Operator*>(o2);
425 break;
426 case Object::vector:
427 eq = *static_cast<const Vector*>(o1)==*static_cast<const Vector*>(o2);
428 break;
429 case Object::list:
430 eq = *static_cast<const List*>(o1)==*static_cast<const List*>(o2);
431 break;
432 case Object::apply:
433 eq = *static_cast<const Apply*>(o1)==*static_cast<const Apply*>(o2);
434 break;
435 case Object::custom:
436 eq = *static_cast<const CustomObject*>(o1)==*static_cast<const CustomObject*>(o2);
437 break;
438 case Object::matrix:
439 eq = *static_cast<const Matrix*>(o1)==*static_cast<const Matrix*>(o2);
440 break;
441 case Object::matrixrow:
442 eq = *static_cast<const MatrixRow*>(o1)==*static_cast<const MatrixRow*>(o2);
443 break;
444 case Object::none:
445 eq=false;
446 Q_ASSERT(false && "Should not get here");
447 break;
448 }
449 return eq;
450 }
451
expressionToVariant(const Analitza::Expression & res)452 QVariant expressionToVariant(const Analitza::Expression& res)
453 {
454 QVariant ret;
455 if(res.isString()) {
456 ret = res.stringValue();
457 } else if(res.isVector() || res.isList()) {
458 QVariantList vals;
459
460 QList<Analitza::Expression> expressions = res.toExpressionList();
461 foreach(const Analitza::Expression& exp, expressions) {
462 vals << expressionToVariant(exp);
463 }
464
465 ret = vals;
466 } else if(res.isReal()) {
467 Analitza::Cn val = res.toReal();
468 switch(val.format()) {
469 case Analitza::Cn::Boolean:
470 ret = val.isTrue();
471 break;
472 case Analitza::Cn::Integer:
473 ret = int(val.value());
474 break;
475 case Analitza::Cn::Char:
476 ret = val.character();
477 break;
478 case Analitza::Cn::Complex: //TODO: figure out complex numbers on QVariant
479 case Analitza::Cn::Real:
480 ret = val.value();
481 break;
482 }
483 } else
484 ret = res.toString();
485
486 return ret;
487 }
488
variantToExpression(const QVariant & v)489 Analitza::Expression variantToExpression(const QVariant& v)
490 {
491 if(v.type() == QVariant::String)
492 return Analitza::Expression(v.toString());
493 else if(v.canConvert(QVariant::Double))
494 return Analitza::Expression(Analitza::Cn(v.toReal()));
495 else if(v.canConvert(QVariant::List)) {
496 QVariantList list = v.toList();
497 QList<Analitza::Expression> expressionList;
498
499 foreach(const QVariant& elem, list) {
500 expressionList << variantToExpression(elem);
501 }
502
503 return Analitza::Expression::constructList(expressionList);
504 } else if(v.canConvert<QObject*>()) {
505 return Analitza::Expression::constructCustomObject(v, nullptr);
506 }
507
508 Q_ASSERT(false && "couldn't figure out the type");
509 return Analitza::Expression();
510 }
511
listToString(const List * list)512 QString listToString(const List* list)
513 {
514 QString ret;
515 for(List::const_iterator it=list->constBegin(), itEnd=list->constEnd(); it!=itEnd; ++it)
516 ret += static_cast<const Cn*>(*it)->character();
517 return ret;
518 }
519
520 template<class T, class Tit, class Tcontained = Object>
521 T* replaceDepthTemplate(int depth, T* tree, Object* towhat)
522 {
523 Tit it=tree->begin(), itEnd=tree->end();
524 for(; it!=itEnd; ++it)
525 *it = static_cast<Tcontained*>(replaceDepth(depth, *it, towhat));
526 return tree;
527 }
528
replaceDepth(int depth,Object * tree,Object * towhat)529 Object* replaceDepth(int depth, Object* tree, Object* towhat)
530 {
531 if(!tree)
532 return nullptr;
533
534 Q_ASSERT(depth>=0);
535 switch(tree->type()) {
536 case Object::value:
537 case Object::custom:
538 case Object::none:
539 case Object::oper:
540 break;
541 case Object::list:
542 return replaceDepthTemplate<List, List::iterator>(depth, static_cast<List*>(tree), towhat);
543 case Object::vector:
544 return replaceDepthTemplate<Vector, Vector::iterator>(depth, static_cast<Vector*>(tree), towhat);
545 case Object::matrix:
546 return replaceDepthTemplate<Matrix, Matrix::iterator, MatrixRow>(depth, static_cast<Matrix*>(tree), towhat);
547 case Object::matrixrow:
548 return replaceDepthTemplate<MatrixRow, MatrixRow::iterator>(depth, static_cast<MatrixRow*>(tree), towhat);
549 case Object::container:
550 return replaceDepthTemplate<Container, Container::iterator>(depth, static_cast<Container*>(tree), towhat);
551 case Object::variable: {
552 Ci* var=(Ci*) tree;
553 if(var->depth()==depth) {
554 delete tree;
555 tree=towhat->copy();
556 }
557 } break;
558 case Object::apply: {
559 Apply* a=static_cast<Apply*>(tree);
560 Apply::iterator it=a->firstValue(), itEnd=a->end();
561 for(; it!=itEnd; ++it)
562 *it=replaceDepth(depth, *it, towhat);
563
564 a->domain()=replaceDepth(depth, a->domain(), towhat);
565 a->dlimit()=replaceDepth(depth, a->ulimit(), towhat);
566 a->ulimit()=replaceDepth(depth, a->dlimit(), towhat);
567 return a;
568 } break;
569 }
570 return tree;
571 }
572
573 template<class T, class Tit>
countDepthTemplate(int depth,const T * tree)574 int countDepthTemplate(int depth, const T* tree)
575 {
576 int ret=0;
577 Tit it=tree->constBegin(), itEnd=tree->constEnd();
578 for(; it!=itEnd; ++it)
579 ret += countDepth(depth, *it);
580 return ret;
581 }
582
countDepth(int depth,const Object * tree)583 int countDepth(int depth, const Object* tree)
584 {
585 if(!tree)
586 return 0;
587
588 Q_ASSERT(depth>=0);
589 switch(tree->type()) {
590 case Object::value:
591 case Object::custom:
592 case Object::none:
593 case Object::oper:
594 break;
595 case Object::list:
596 return countDepthTemplate<List, List::const_iterator>(depth, static_cast<const List*>(tree));
597 case Object::vector:
598 return countDepthTemplate<Vector, Vector::const_iterator>(depth, static_cast<const Vector*>(tree));
599 case Object::matrix:
600 return countDepthTemplate<Matrix, Matrix::const_iterator>(depth, static_cast<const Matrix*>(tree));
601 case Object::matrixrow:
602 return countDepthTemplate<MatrixRow, MatrixRow::const_iterator>(depth, static_cast<const MatrixRow*>(tree));
603 case Object::container:
604 return countDepthTemplate<Container, Container::const_iterator>(depth, static_cast<const Container*>(tree));
605 case Object::variable: {
606 Ci* var=(Ci*) tree;
607 return var->depth()==depth;
608 } break;
609 case Object::apply: {
610 const Apply* a=static_cast<const Apply*>(tree);
611 Apply::const_iterator it=a->firstValue(), itEnd=a->constEnd();
612 int ret=0;
613 for(; it!=itEnd; ++it)
614 ret+=countDepth(depth, *it);
615
616 ret+=countDepth(depth, a->domain());
617 ret+=countDepth(depth, a->ulimit());
618 ret+=countDepth(depth, a->dlimit());
619 return ret;
620 } break;
621 }
622 return 0;
623 }
624
generateDependencyGraph(const Variables * v)625 QString generateDependencyGraph(const Variables* v)
626 {
627 QStringList special=QStringList() << QStringLiteral("check");
628 QString ret;
629 ret += QLatin1String("digraph G {\n");
630
631 foreach(const QString& n, special) {
632 ret += '\t'+n+" [shape=doublecircle];\n";
633 }
634 ret += '\n';
635
636 for(Variables::const_iterator it=v->constBegin(), itEnd=v->constEnd(); it!=itEnd; ++it) {
637 QString current = it.key();
638 QStringList deps = dependencies(it.value(), QStringList());
639
640 foreach(const QString& d, deps) {
641 const Object* o=v->value(d);
642 if(o && isLambda(o)) {
643 ret += '\t'+current+" -> "+d+";\n";
644 }
645 }
646 }
647
648 ret += QLatin1String("}\n");
649 return ret;
650 }
651
652 }
653