analitza/analitza/expressiontype.cpp

0001 /*************************************************************************************
0002  *  Copyright (C) 2010 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 "expressiontype.h"
0020 #include <QStringList>
0021 #include <QDebug>
0022
0023 using namespace Analitza;
0024
0025 QDebug operator<<(QDebug dbg, const ExpressionType &c);
0026 namespace Analitza { void printAssumptions(const QString& prefix, const ExpressionType& current); }
0027 QDebug operator<<(QDebug dbg, const QMap<int, Analitza::ExpressionType> &c);
0028
0029 bool ExpressionType::assumptionsMerge(QMap<QString, ExpressionType>& data, const QMap<QString, ExpressionType>& newmap)
0030 {
0031     if(data.isEmpty() && newmap.isEmpty())
0032         return true;
0033
0034 //     static int i=0;
0035 //     qDebug() << "merging!" << i++ << data << newmap;
0036     QMap<int, ExpressionType> stars;
0037     QMap<QString, ExpressionType>::const_iterator it=newmap.constBegin(), itEnd=newmap.constEnd();
0038     for(; it!=itEnd; ++it) {
0039         QMap<QString, ExpressionType>::iterator current = data.find(it.key());
0040
0041         if(current!=data.end()) {
0042             if(!current->isError()) {
0043                 ExpressionType t=ExpressionType::minimumType(*it, *current);
0044 //                 qDebug() << "miiiiiiin" << it.key() << *it << *current << t << "|||" << it->assumptions() << current->assumptions() << t.assumptions();
0045                 if(t.isError())
0046                     return false;
0047
0048                 stars=computeStars(stars, *it, *current);
0049                 *current = t.starsToType(stars);
0050             }
0051         } else
0052             data.insert(it.key(), it.value());
0053     }
0054 //     qDebug() << "merging_" << data;
0055
0056     for(QMap<QString, ExpressionType>::iterator it=data.begin(); it!=data.end(); ++it) {
0057         *it=it->starsToType(stars);
0058     }
0059
0060 //     i--;
0061     return true;
0062 }
0063
0064 void ExpressionType::assumptionsUnion(QMap<QString, ExpressionType>& data, const QMap<QString, ExpressionType>& newmap)
0065 {
0066 //     qDebug() << "-----------" << data << newmap;
0067     QMap<QString, ExpressionType>::const_iterator it=newmap.constBegin(), itEnd=newmap.constEnd();
0068     for(; it!=itEnd; ++it) {
0069         QMap<QString, ExpressionType>::iterator current = data.find(it.key());
0070
0071         if(current!=data.end()) {
0072             if(current->canReduceTo(*it)) {
0073                 data.insert(it.key(), minimumType(*current, *it));
0074             } else {
0075                 bool correct=false;
0076                 ExpressionType t(Many);
0077                 ExpressionType t1(*it);            correct= t1.addAssumption(it.key(), *it);
0078                 ExpressionType t2(*current);    correct|=t2.addAssumption(it.key(), *current);
0079
0080                 Q_ASSERT(correct);
0081                 t.addAlternative(t1);
0082                 t.addAlternative(t2);
0083
0084                 data.insert(it.key(), t);
0085             }
0086         } else
0087             data.insert(it.key(), it.value());
0088     }
0089
0090 //     qDebug() << "leeeeee" << data;
0091 }
0092
0093 ExpressionType::ExpressionType(const ExpressionType& t)
0094     : m_type(t.m_type), m_contained(t.m_contained)
0095     , m_assumptions(t.m_assumptions), m_size(t.m_size), m_objectName(t.m_objectName)
0096 {}
0097
0098 ExpressionType::ExpressionType(ExpressionType::Type t, int any)
0099     : m_type(t), m_any(any)
0100 {Q_ASSERT(m_type==Any || m_type==Error || m_type==Value || m_type==Bool || m_type==Char || m_type==Many || m_type==Lambda); }
0101
0102 ExpressionType::ExpressionType(ExpressionType::Type t, const ExpressionType& contained, int s)
0103     : m_type(t), m_contained(QList<ExpressionType>() << contained), m_size(s)
0104 {
0105     Q_ASSERT(m_type==List || m_type==Vector || m_type==Matrix || m_type==Any); // Any for variadic functions with same contained type
0106     Q_ASSERT(m_type!=Vector || m_size!=0);
0107     Q_ASSERT(m_type!=Matrix || contained.type()==Vector);
0108     m_assumptions=contained.assumptions();
0109 }
0110
0111 ExpressionType::ExpressionType(const QString& objectName)
0112     : m_type(Object), m_size(-1), m_objectName(objectName)
0113 {}
0114
0115 ExpressionType::ExpressionType(ExpressionType::Type t, const QList< ExpressionType >& alternatives)
0116     : m_type(Many), m_size(-1)
0117 {
0118     Q_ASSERT(t==Many);
0119     foreach(const ExpressionType& t, alternatives)
0120         addAlternative(t);
0121 }
0122
0123 QStringList typesToString(const QList<ExpressionType>& types)
0124 {
0125     QStringList ret;
0126     foreach(const ExpressionType& t, types) {
0127         QString str=t.toString();
0128         if(t.type()==ExpressionType::Lambda)
0129             ret += '('+str+')';
0130         else
0131             ret += str;
0132     }
0133     return ret;
0134 }
0135
0136 QString ExpressionType::toString() const
0137 {
0138     QString ret;
0139     switch(m_type) {
0140         case ExpressionType::Value:ret=QStringLiteral("num");  break;
0141         case ExpressionType::Char: ret=QStringLiteral("char"); break;
0142         case ExpressionType::Bool: ret=QStringLiteral("bool"); break;
0143         case ExpressionType::List:
0144             ret='['+typesToString(m_contained).join(QStringLiteral("$"))+']';
0145             break;
0146         case ExpressionType::Vector:
0147             ret='<'+typesToString(m_contained).join(QStringLiteral("$"))+','+QString::number(m_size)+'>';
0148             break;
0149         case ExpressionType::Matrix:
0150             ret=QStringLiteral("{%1,%2x%3}").arg(contained().contained().toString()).arg(m_size).arg(contained().size());
0151             break;
0152         case ExpressionType::Error:
0153             ret=QStringLiteral("err");
0154             break;
0155         case ExpressionType::Lambda:
0156             ret=typesToString(m_contained).join(QStringLiteral(" -> "));
0157             break;
0158         case ExpressionType::Any: {
0159 //             ret=QString(m_any, '*');
0160             QString id;
0161             for(int i=m_any; i>0; i/='z'-'a') {
0162                 id.prepend(QChar('a'-1+(i%('z'-'a'))));
0163             }
0164             ret=id;
0165 //             ret+=QString::number(m_any);
0166         }    break;
0167         case ExpressionType::Many:
0168             ret=/*"{"+*/typesToString(m_contained).join(QStringLiteral(" | "))/*+"}"*/;
0169             break;
0170         case ExpressionType::Object:
0171             ret="obj:"+m_objectName;
0172             break;
0173     }
0174
0175     return ret;
0176 }
0177
0178 bool ExpressionType::isError() const
0179 {
0180     if(m_type==Error)
0181         return true;
0182     else if(m_type==Many && m_contained.isEmpty())
0183         return true;
0184     foreach (const ExpressionType& t, m_contained) {
0185         if(t.isError())
0186             return true;
0187     }
0188     return false;
0189 }
0190
0191 ExpressionType ExpressionType::operator=(const ExpressionType& et)
0192 {
0193     if(&et!=this) {
0194         m_type=et.m_type;
0195         m_contained=et.m_contained;
0196         m_size=et.m_size;
0197         m_assumptions=et.m_assumptions;
0198         m_objectName=et.m_objectName;
0199     }
0200
0201     return *this;
0202 }
0203
0204 bool ExpressionType::operator==(const ExpressionType& t) const
0205 {
0206 //     qDebug() <<"seeee" << m_type << t.m_type << t.m_contained << m_contained << t << *this;
0207     bool ret=t.m_type==m_type;
0208     ret=ret            && (m_type==ExpressionType::Any ? m_any==t.m_any : (m_size<1 || t.m_size<1 || m_size==t.m_size));
0209     ret=ret            && t.m_contained==m_contained;
0210
0211     if(!ret && t.type()==ExpressionType::Many && t.alternatives().size()==1)
0212         ret=*this==t.alternatives().at(0);
0213
0214     if(!ret &&   type()==ExpressionType::Many &&   alternatives().size()==1)
0215         ret=t==alternatives().at(0);
0216
0217     ret &= m_objectName==t.m_objectName;
0218 //     qDebug() << "++++++++" << t << *this << ret;
0219     return ret;
0220 }
0221
0222 bool ExpressionType::addAssumption(const QString& bvar, const Analitza::ExpressionType& t)
0223 {
0224     ExpressionType toadd=t;
0225     addAssumptions(t.assumptions());
0226     toadd.clearAssumptions();
0227
0228     QMap< QString, ExpressionType >::iterator it=m_assumptions.find(bvar);
0229     if(it==m_assumptions.end())
0230         m_assumptions.insert(bvar, toadd);
0231     else {
0232         toadd=minimumType(toadd,*it);
0233         if(toadd.isError())
0234             return false;
0235         *it=toadd;
0236     }
0237
0238     return true;
0239 }
0240
0241 void ExpressionType::removeAssumptions(const QStringList& bvarStrings)
0242 {
0243     foreach(const QString& bvar, bvarStrings)
0244         m_assumptions.remove(bvar);
0245
0246     QList<ExpressionType>::iterator it=m_contained.begin(), itEnd=m_contained.end();
0247     for(; it!=itEnd; ++it) {
0248         it->removeAssumptions(bvarStrings);
0249     }
0250 }
0251
0252 void ExpressionType::addAssumptions(const QMap<QString, ExpressionType>& a)
0253 {
0254 //     qDebug() << "=====1" << m_assumptions << a;
0255     bool valid=assumptionsMerge(m_assumptions, a);
0256 //     qDebug() << "=====2" << m_assumptions;
0257     Q_ASSERT(valid);
0258 }
0259
0260 ExpressionType ExpressionType::starsToType(const QMap<int, ExpressionType>& info) const
0261 {
0262 #if defined(QT_NO_DEBUG) && !defined(QT_FORCE_ASSERTS)
0263     for(QMap<int, ExpressionType>::const_iterator it=info.cbegin(); it!=info.cend(); ++it) {
0264         Q_ASSERT(it->type()!=ExpressionType::Any || it->anyValue()!=it.key());
0265     }
0266 #endif
0267
0268     ExpressionType ret;
0269 //     static int deep=0;
0270 //     qDebug() << qPrintable("hohohoho"+QString(++deep, '-')) << *this << info << &info;
0271
0272 //     qDebug() << ".........." << *this << info.keys();
0273     if(m_type==ExpressionType::Any && info.contains(m_any)) {
0274         ret=info.value(m_any);
0275         ret.m_assumptions=m_assumptions;
0276     } else if((m_type==ExpressionType::Vector || m_type==ExpressionType::Matrix) && m_size<0 && info.contains(m_size)) {
0277         ret=*this;
0278         QMap<int, ExpressionType> info2(info);
0279         ExpressionType sometype = info2.take(m_size);
0280         ret.m_size = sometype.m_size;
0281         ret.m_contained.first() = m_contained.first().starsToType(info2);
0282         ret.m_assumptions=m_assumptions;
0283     } else {
0284         ret=*this;
0285
0286         bool hasMany=false;
0287         for(QList<ExpressionType>::iterator it=ret.m_contained.begin(), itEnd=ret.m_contained.end(); it!=itEnd; ++it) {
0288             *it=it->starsToType(info);
0289             hasMany|=(it->type()==ExpressionType::Many);
0290         }
0291
0292         if(hasMany) {
0293             QList<ExpressionType> args=manyFromArgs(ret.m_contained);
0294             QList<ExpressionType> alts;
0295             foreach(const ExpressionType& t, args) {
0296                 ExpressionType tt=ret;
0297                 tt.m_contained=t.m_contained;
0298
0299                 bool b=assumptionsMerge(tt.m_assumptions, t.m_assumptions);
0300                 if(b)
0301                     alts += tt;
0302             }
0303             ret=ExpressionType(ExpressionType::Many, alts);
0304         }
0305     }
0306
0307     for(QMap<QString, ExpressionType>::iterator it=ret.m_assumptions.begin(), itEnd=ret.m_assumptions.end(); it!=itEnd; ++it) {
0308         *it=it->starsToType(info);
0309     }
0310
0311 //     qDebug() << qPrintable("fuuuuuuu"+QString(deep, '-')) << info << &info;
0312
0313 //     deep--;
0314 //     qDebug() << "MMMMMMMM" << ret << ret.assumptions() << m_assumptions;
0315
0316     return ret;
0317 }
0318
0319 bool ExpressionType::canCompareTo(const ExpressionType& type) const
0320 {
0321     bool ret=type==*this;
0322     if(!ret && type.m_type==m_type) {
0323         switch(m_type) {
0324             case ExpressionType::List:
0325                 ret=contained().canCompareTo(type.contained());
0326                 break;
0327             case ExpressionType::Matrix:
0328             case ExpressionType::Vector:
0329                 ret=contained().canCompareTo(type.contained());
0330                 if(ret && m_size>0 && type.m_size>0)
0331                     ret = m_size == type.m_size;
0332                 break;
0333             case ExpressionType::Object:
0334                 ret = m_objectName==type.m_objectName;
0335                 break;
0336             case ExpressionType::Lambda:
0337                 ret = m_contained.size()==type.m_contained.size();
0338                 break;
0339             case ExpressionType::Error:
0340             case ExpressionType::Bool:
0341             case ExpressionType::Char:
0342             case ExpressionType::Value:
0343             case ExpressionType::Any:
0344             case ExpressionType::Many: //todo?
0345                 ret=true;
0346                 break;
0347         }
0348     } else if(!ret)
0349         ret = (m_type==Any || m_type==Error) || (type.m_type==Any || type.m_type==Error);
0350     return ret;
0351 }
0352
0353 bool ExpressionType::canReduceTo(const ExpressionType& type) const
0354 {
0355     bool ret=false;
0356
0357     if(type==*this || m_type==Any || isError())
0358         ret=true;
0359     else if(m_type==Many) {
0360         foreach(const ExpressionType& t, m_contained) {
0361             if(t.canReduceTo(type)) {
0362                 ret=true;
0363                 break;
0364             }
0365         }
0366     } else if(type.m_type==Many) {
0367         foreach(const ExpressionType& t, type.m_contained) {
0368             if(canReduceTo(t)) {
0369                 ret=true;
0370                 break;
0371             }
0372         }
0373     } else if(m_type==Lambda) {
0374         ret = m_contained.size()==type.m_contained.size();
0375         QMap<int, ExpressionType> reductionsApplied;
0376         for(int i=0; ret && i<m_contained.size(); i++) {
0377             ExpressionType a=m_contained[i].starsToType(reductionsApplied), b=type.m_contained[i].starsToType(reductionsApplied);
0378             ret&=a.canReduceTo(b);
0379
0380             if(ret && a.type()==Any && a!=b) {
0381                 b.clearAssumptions();
0382                 reductionsApplied.insert(a.anyValue(), b);
0383             }
0384         }
0385     } else if(m_type==Vector && type.m_type==Vector) {
0386         ret  = m_size<0 || type.m_size<0 || m_size==type.m_size;
0387         ret &= contained().canReduceTo(type.contained());
0388     } else if(m_type==List && type.m_type==List) {
0389         ret = contained().canReduceTo(type.contained());
0390     } else if(m_type==Matrix && type.m_type==Matrix) {
0391         ret = contained().canReduceTo(type.contained());
0392     }
0393
0394 //     qDebug() << "OOOOOOOOOOOOO" << *this << type << ret;
0395
0396     return ret;
0397 }
0398
0399 QMap<QString, ExpressionType> ExpressionType::assumptions() const
0400 {
0401 //     printAssumptions(*this);
0402     return m_assumptions;
0403 }
0404
0405 QMap< QString, ExpressionType >& ExpressionType::assumptions()
0406 {
0407     return m_assumptions;
0408 }
0409
0410 int ExpressionType::increaseStars(int stars)
0411 {
0412     int ret=stars;
0413
0414     if(m_type==ExpressionType::Any) {
0415         m_any=stars+m_any;
0416         if(m_any>ret)
0417             ret=m_any+1;
0418     }
0419
0420     for(QList<ExpressionType>::iterator it=m_contained.begin(), itEnd=m_contained.end(); it!=itEnd; ++it) {
0421         ret=qMax(it->increaseStars(stars), ret);
0422     }
0423
0424     for(QMap<QString,ExpressionType>::iterator it=m_assumptions.begin(), itEnd=m_assumptions.end(); it!=itEnd; ++it) {
0425         ret=qMax(it->increaseStars(stars), ret);
0426     }
0427
0428     return ret;
0429 }
0430
0431 void ExpressionType::starsSimplification(ExpressionType& t, QMap<int, int>& reductions, int &next)
0432 {
0433     switch(t.m_type) {
0434         case ExpressionType::Any:
0435             if(reductions.contains(t.m_any))
0436                 t.m_any=reductions.value(t.m_any);
0437             else {
0438                 reductions.insert(t.m_any, next);
0439                 t.m_any=next++;
0440             }
0441
0442             break;
0443         case ExpressionType::Many:
0444         case ExpressionType::Vector:
0445         case ExpressionType::Matrix:
0446         case ExpressionType::List:
0447         case ExpressionType::Lambda:
0448             for(QList<ExpressionType>::iterator it=t.m_contained.begin(), itEnd=t.m_contained.end(); it!=itEnd; ++it) {
0449                 starsSimplification(*it, reductions, next);
0450             }
0451             break;
0452         case ExpressionType::Object:
0453         case ExpressionType::Value:
0454         case ExpressionType::Char:
0455         case ExpressionType::Bool:
0456         case ExpressionType::Error:
0457             break;
0458     }
0459 }
0460
0461 ExpressionType& ExpressionType::simplifyStars()
0462 {
0463     int next=1;
0464     QMap<int, int> map;
0465     starsSimplification(*this, map, next);
0466     return *this;
0467 }
0468
0469 ExpressionType ExpressionType::returnValue() const
0470 {
0471     ExpressionType ret;
0472
0473     if(m_type==Analitza::ExpressionType::Many) {
0474         ret=ExpressionType(ExpressionType::Many);
0475         foreach(const ExpressionType& t, m_contained)
0476             ret.addAlternative(t.returnValue());
0477     } else if(m_type==Analitza::ExpressionType::Lambda)
0478         ret=m_contained.last();
0479
0480     return ret;
0481 }
0482
0483 void ExpressionType::reduce(const Analitza::ExpressionType& type)
0484 {
0485     if(m_type == Many) {
0486         QList<ExpressionType> newcontained;
0487
0488         foreach(const ExpressionType& t, m_contained) {
0489             if(t.canReduceTo(type))
0490                 newcontained.append(t);
0491         }
0492
0493         if(newcontained.size()==1) {
0494             bool b=assumptionsMerge(newcontained.first().assumptions(), m_assumptions);
0495             Q_ASSERT(b);
0496             *this = newcontained.first();
0497         } else if(newcontained.isEmpty())
0498             ;
0499         else
0500             m_contained = newcontained;
0501
0502     }
0503
0504     if(m_type == Many) {
0505         QList<ExpressionType>::iterator it=m_contained.begin(), itEnd=m_contained.end();
0506         for(; it!=itEnd; ) {
0507             bool b = assumptionsMerge(it->assumptions(), type.assumptions());
0508
0509 //             qDebug() << "LLLLL" << b << *it << it->assumptions();
0510             if(b)
0511                 ++it;
0512             else
0513                 it=m_contained.erase(it);
0514         }
0515     } else {
0516         bool b = assumptionsMerge(m_assumptions, type.assumptions());
0517         if(!b)
0518             *this = ExpressionType(Error);
0519         else if(m_type==ExpressionType::Any && *this!=type) {
0520             QMap<int, ExpressionType> t;
0521             t.insert(m_any, type);
0522
0523             QMap<QString, ExpressionType> resassumptions=assumptions();
0524             *this = type.starsToType(t);
0525             addAssumptions(resassumptions);
0526         }
0527     }
0528
0529     if(m_type==Lambda && type.m_type==Lambda && canReduceTo(type)) {
0530         QList< ExpressionType >::iterator it1=m_contained.begin();
0531         QList< ExpressionType >::const_iterator it2=type.m_contained.constBegin();
0532
0533         for(; it1!=m_contained.end(); ++it1, ++it2) {
0534             *it1=minimumType(*it1, *it2);
0535         }
0536     }
0537 }
0538
0539 ExpressionType ExpressionType::minimumType(const ExpressionType& t1, const ExpressionType& t2)
0540 {
0541     if(t1.type()==ExpressionType::Many && t2.type()==ExpressionType::Many) {
0542         QList<ExpressionType> alts;
0543 //         qDebug() << "IIIIIIIIII" << t1 << t2;
0544         foreach(const ExpressionType& alt1, t1.alternatives()) {
0545             foreach(const ExpressionType& alt2, t2.alternatives()) {
0546                 if(alt1.canReduceTo(alt2)) {
0547                     ExpressionType alt(alt1);
0548                     alt.reduce(alt2);
0549
0550                     if(!alt.isError()) {
0551                         alts+=alt;
0552                     }
0553                 }
0554             }
0555         }
0556
0557         if(alts.isEmpty())
0558             return ExpressionType(ExpressionType::Error);
0559         else {
0560 //             qDebug() << "aaaaaaaaaaaaaaaaaaaaaaaaaaa" << alts << "\n\t --- " << alts.first().assumptions() << "\n\t --- " << alts.last().assumptions()
0561 //                         << "\n\t --- " << t1.assumptions() << t2.assumptions();
0562             ExpressionType ret=ExpressionType(ExpressionType::Many, alts);
0563             ret.addAssumptions(t1.assumptions());
0564             ret.addAssumptions(t2.assumptions());
0565             return ret;
0566         }
0567     }
0568     else if(t2.isError())
0569         return t1;
0570     else if(t1.isError())
0571         return t2;
0572     else if(t1.type()==ExpressionType::Any && t2.type()==ExpressionType::Any)
0573         return t1.anyValue()>t2.anyValue() ? t1 : t2;
0574     else if(t1.type()==ExpressionType::Lambda && t2.type()==ExpressionType::Lambda && t1.parameters().size()==t2.parameters().size()) {
0575         ExpressionType t(ExpressionType::Lambda);
0576         for(int i=0; i<t1.parameters().size(); i++) {
0577             t.addParameter(minimumType(t1.parameters().at(i), t2.parameters().at(i)));
0578         }
0579         if(!t.isError()) {
0580             t.addAssumptions(t1.assumptions());
0581             t.addAssumptions(t2.assumptions());
0582         }
0583
0584         return t;
0585     } else if(t1.canReduceTo(t2)) {
0586 //         qDebug() << "zas" << t1 << t2 << "|||" << t1.assumptions() << t2.assumptions();
0587         ExpressionType t(t2);
0588         t.reduce(t1);
0589 //         qDebug() << "zus" << t << t.assumptions();
0590         return t;
0591     } else if(t2.canReduceTo(t1)) {
0592         ExpressionType t(t1);
0593         t.reduce(t2);
0594         return t;
0595     }
0596
0597     return ExpressionType();
0598 }
0599
0600 ExpressionType& ExpressionType::addParameter(const ExpressionType& t)
0601 {
0602     Q_ASSERT(m_type==Lambda);
0603     m_contained.append(t);
0604     return *this;
0605 }
0606
0607 void ExpressionType::addAlternative(const ExpressionType& t)
0608 {
0609     Q_ASSERT(m_type==Many);
0610     /*int i=m_contained.indexOf(t);
0611     if(i>=0) {
0612         m_contained[i].addAssumptions(t.assumptions());//TODO??
0613     } else */
0614     if(t.m_type==Many) {
0615         foreach(const ExpressionType& tt, t.alternatives())
0616             addAlternative(tt);
0617
0618         addAssumptions(t.m_assumptions);
0619 //         m_contained=t.m_contained;
0620     } else
0621         m_contained.append(t);
0622 }
0623
0624 void ExpressionType::clearAssumptions()
0625 {
0626     m_assumptions.clear();
0627     QList< ExpressionType >::iterator it=m_contained.begin(), itEnd=m_contained.end();
0628     for(; it!=itEnd; ++it) {
0629         it->clearAssumptions();
0630     }
0631 }
0632
0633 QMap<int, ExpressionType> ExpressionType::processContained(const QMap<int, ExpressionType>& initial, const ExpressionType& candidate, const ExpressionType& type)
0634 {
0635     auto ret=computeStars(initial, candidate.contained(), type.contained());
0636
0637     if(candidate.size()<0) {
0638         ExpressionType t=type;
0639         t.m_contained.first()=t.m_contained.first().starsToType(ret);
0640         ret[candidate.size()] = t;
0641     }
0642     return ret;
0643 }
0644
0645 QMap<int, ExpressionType> ExpressionType::computeStars(const QMap<int, ExpressionType>& initial, const ExpressionType& candidate, const ExpressionType& type)
0646 {
0647     QMap<int, ExpressionType> ret(initial);
0648
0649     switch(candidate.type()) {
0650         case ExpressionType::Any: {
0651             int stars=candidate.anyValue();
0652
0653             if(ret.contains(stars)) {
0654                 ExpressionType t=ret.take(stars);
0655                 ret=computeStars(ret, t, type);
0656
0657                 t=t.starsToType(ret);
0658                 if(t.type()!=ExpressionType::Any || t.m_any!=stars)
0659                     ret.insert(stars, t);
0660             } else if(type.type()!=ExpressionType::Any || type.m_any!=stars) {
0661                 ret[stars]=type;
0662             }
0663         }    break;
0664         case ExpressionType::List:
0665             if(type.type()==ExpressionType::List) { // remove? assert?
0666                 ret=computeStars(initial, candidate.contained(), type.contained());
0667             }
0668             break;
0669         case ExpressionType::Matrix:
0670             if(type.type()==ExpressionType::Matrix) { // remove? assert?
0671                 ret = processContained(initial, candidate, type);
0672             }
0673             break;
0674         case ExpressionType::Vector:
0675             if(type.type()==ExpressionType::Vector) { // remove?
0676                 ret = processContained(initial, candidate, type);
0677             }
0678             break;
0679         case ExpressionType::Lambda:
0680             if(type.type()!=ExpressionType::Lambda)
0681                 break;
0682             Q_ASSERT(type.parameters().size()==candidate.parameters().size());
0683             for(int i=0; i<type.parameters().size(); i++) {
0684                 ret=computeStars(ret, candidate.parameters().at(i), type.parameters().at(i));
0685             }
0686             break;
0687         case ExpressionType::Many:
0688         case ExpressionType::Object:
0689         case ExpressionType::Value:
0690         case ExpressionType::Bool:
0691         case ExpressionType::Char:
0692         case ExpressionType::Error:
0693 //             Q_ASSERT(false && "bffff");
0694             break;
0695     }
0696
0697     for(QMap<int, ExpressionType>::iterator it=ret.begin(), itEnd=ret.end(); it!=itEnd; ++it) {
0698         ExpressionType t=it->starsToType(ret);
0699         if(t.type()!=ExpressionType::Any || t.m_any!=it.key()) {
0700             *it=t;
0701         }
0702     }
0703
0704 //     qDebug() << ";;;;;;;" << candidate.type() << candidate << type << ret;
0705 //     bool b = matchAssumptions(&ret, type.assumptions(), candidate.assumptions());
0706 //     qDebug() << "feeeee" << ret;
0707
0708     return ret;
0709 }
0710
0711 bool ExpressionType::matchAssumptions(QMap< int, ExpressionType >* stars,
0712                                                 const QMap< QString, ExpressionType >& assum1,
0713                                                 const QMap< QString, ExpressionType >& assum2)
0714 {
0715     bool ret=true;
0716     QMap<QString, ExpressionType>::const_iterator it=assum1.constBegin(), itEnd=assum1.constEnd();
0717     QMap<QString, ExpressionType>::const_iterator itFind, itFindEnd=assum2.constEnd();
0718
0719     for(; ret && it!=itEnd; ++it) {
0720         itFind=assum2.find(it.key());
0721
0722         if(itFind!=itFindEnd && *itFind!=*it) {
0723 //             qDebug() << "sih" << it.key() << *it << *itFind;
0724             if(itFind->canReduceTo(*it))
0725                 *stars=ExpressionType::computeStars(*stars, *itFind, *it);
0726             else if(it->canReduceTo(*itFind))
0727                 *stars=ExpressionType::computeStars(*stars, *it, *itFind);
0728             else
0729                 ret=false;
0730 //             qDebug() << "seh" << *stars << ret;
0731         }
0732     }
0733
0734     return ret;
0735 }
0736
0737 QStringList ExpressionType::wrongAssumptions(const QMap< QString, ExpressionType >& assum1, const QMap< QString, ExpressionType >& assum2)
0738 {
0739     QStringList ret;
0740     QMap<QString, ExpressionType>::const_iterator it=assum1.constBegin(), itEnd=assum1.constEnd();
0741     QMap<QString, ExpressionType>::const_iterator itFind, itFindEnd=assum2.constEnd();
0742
0743     for(; it!=itEnd; ++it) {
0744         itFind=assum2.find(it.key());
0745
0746         if(itFind!=itFindEnd && *itFind!=*it && !itFind->canReduceTo(*it) && !it->canReduceTo(*itFind)) {
0747             ret += it.key();
0748         }
0749     }
0750
0751     return ret;
0752 }
0753
0754 QList<ExpressionType> ExpressionType::manyFromArgs(const QList<ExpressionType>& args)
0755 {
0756     QList<ExpressionType> funcs = QList<ExpressionType>() << ExpressionType(ExpressionType::Many);
0757
0758     foreach(const ExpressionType& e, args) {
0759         QList<ExpressionType> alts = e.type()==ExpressionType::Many ? e.alternatives() : QList<ExpressionType>() << e;
0760         QList<ExpressionType> newfuncs;
0761         foreach(const ExpressionType& rr, alts) {
0762             foreach(const ExpressionType& f, funcs) {
0763                 newfuncs += f;
0764
0765                 QMap<int, ExpressionType> stars;
0766 //                 qDebug() << "&&&&&&&" << rr << newfuncs.last().assumptions() << rr.assumptions();
0767                 bool m=ExpressionType::assumptionsMerge(newfuncs.last().assumptions(), rr.assumptions());
0768                 m|=ExpressionType::matchAssumptions(&stars, newfuncs.last().assumptions(), rr.assumptions());
0769 //                 qDebug() << "falala" << m;
0770
0771                 if(m)
0772                     newfuncs.last().addAlternative(rr.starsToType(stars));
0773                 else
0774                     newfuncs.removeLast();
0775             }
0776         }
0777
0778         funcs = newfuncs;
0779     }
0780
0781     return funcs;
0782 }
0783
0784 QList<ExpressionType> ExpressionType::lambdaFromArgs(const QList<ExpressionType>& args)
0785 {
0786     QList<ExpressionType> funcs = QList<ExpressionType>() << ExpressionType(ExpressionType::Lambda);
0787
0788     foreach(const ExpressionType& e, args) {
0789         QList<ExpressionType> alts = e.type()==ExpressionType::Many ? e.alternatives() : QList<ExpressionType>() << e;
0790         QList<ExpressionType> newfuncs;
0791         foreach(const ExpressionType& rr, alts) {
0792             foreach(const ExpressionType& f, funcs) {
0793                 newfuncs += f;
0794
0795                 QMap<int, ExpressionType> stars;
0796 //                 qDebug() << "&&&&&&&" << rr << newfuncs.last().assumptions() << rr.assumptions();
0797                 bool m=ExpressionType::assumptionsMerge(newfuncs.last().assumptions(), rr.assumptions());
0798                 m|=matchAssumptions(&stars, newfuncs.last().assumptions(), rr.assumptions());
0799 //                 qDebug() << "falala" << m;
0800
0801                 if(m)
0802                     newfuncs.last().addParameter(rr.starsToType(stars));
0803                 else
0804                     newfuncs.removeLast();
0805             }
0806         }
0807
0808         funcs = newfuncs;
0809     }
0810
0811     return funcs;
0812 }
0813
0814 QString ExpressionType::objectName() const
0815 {
0816     return m_objectName;
0817 }
0818
0819 bool ExpressionType::hasContained() const
0820 {
0821     Q_ASSERT(m_type==Vector || m_type==List || m_type==Matrix || m_type==Any);
0822     return !m_contained.isEmpty();
0823 }
0824
0825 ExpressionType ExpressionType::contained() const
0826 {
0827     Q_ASSERT(m_type==Vector || m_type==List || m_type==Matrix || m_type==Any);
0828     Q_ASSERT(m_contained.size()==1);
0829     return m_contained.first();
0830 }