analitza/analitza/expressiontypechecker.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 "expressiontypechecker.h"
0020 #include "variable.h"
0021 #include "variables.h"
0022 #include "list.h"
0023 #include "vector.h"
0024 #include "container.h"
0025 #include "expression.h"
0026 #include "analitzautils.h"
0027 #include "operations.h"
0028 #include "apply.h"
0029 #include "value.h"
0030 #include "matrix.h"
0031 #include <QCoreApplication>
0032
0033 QDebug operator<<(QDebug dbg, const Analitza::ExpressionType &c)
0034 {
0035     dbg.nospace() << "("<< qPrintable(c.toString());
0036 //     if(!c.assumptions().isEmpty())
0037 //         dbg.nospace() <<", " << c.assumptions();
0038     dbg.nospace() << /*":"<< c.type() <<*/")";
0039
0040     return dbg.space();
0041 }
0042
0043 QDebug operator<<(QDebug dbg, const QMap<int, Analitza::ExpressionType> &c)
0044 {
0045     dbg.nospace() << "starsMap(";
0046     for(QMap<int,Analitza::ExpressionType>::const_iterator it=c.constBegin(); it!=c.constEnd(); ++it) {
0047         QString str = Analitza::ExpressionType(Analitza::ExpressionType::Any, it.key()<0? -it.key():it.key()).toString();
0048         if(it.key()<0)
0049             str="<-"+str+"->";
0050
0051         dbg.space() << "["<< str << ":" << it.value() << "]";
0052     }
0053     dbg.space() << ")";
0054
0055     return dbg.nospace();
0056 }
0057
0058 namespace Analitza
0059 {
0060
0061 void printAssumptions(const QString& prefix, const ExpressionType& current)
0062 {
0063     qDebug() << qPrintable(prefix) << current << current.assumptions();
0064     if(current.type()==ExpressionType::Many) {
0065         foreach(const ExpressionType& t, current.alternatives()) {
0066             qDebug() << qPrintable(prefix) << "XXXSSS" << t << t.assumptions();
0067         }
0068     }
0069     qDebug() << qPrintable(prefix) << "--";
0070 }
0071
0072 ExpressionTypeChecker::ExpressionTypeChecker(Variables* v)
0073     : m_stars(0)
0074     , m_v(v)
0075 {}
0076
0077 ExpressionType ExpressionTypeChecker::check(const Expression& exp)
0078 {
0079     m_deps.clear();
0080     m_stars=1;
0081     current=ExpressionType(ExpressionType::Error);
0082
0083     exp.tree()->accept(this);
0084
0085 //     qDebug() << "cheeeeeeck" << m_vars;
0086     return current;
0087 }
0088
0089 QVariant ExpressionTypeChecker::visit(const Operator*) { Q_ASSERT(false && "should not get here"); return QVariant(); }
0090
0091 bool ExpressionTypeChecker::inferType(const ExpressionType& found, const ExpressionType& targetType, QMap<QString, ExpressionType>* assumptions)
0092 {
0093     Q_ASSERT(!targetType.isError() && assumptions);
0094     Q_ASSERT(found.type()!=ExpressionType::Many);
0095
0096     QMap<int, ExpressionType> stars;
0097     stars=ExpressionType::computeStars(stars, found, targetType);
0098     bool ret=found.canReduceTo(targetType);
0099     ret&=ExpressionType::matchAssumptions(&stars, found.assumptions(), targetType.assumptions());
0100     ret&=ExpressionType::assumptionsMerge(*assumptions, found.assumptions());
0101
0102     for(QMap<QString, ExpressionType>::iterator it=assumptions->begin(), itEnd=assumptions->end(); it!=itEnd; ++it) {
0103         *it=it->starsToType(stars);
0104     }
0105 //     qDebug() << "fuuuuu" << stars << *assumptions << ret;
0106
0107     return ret;
0108 }
0109
0110 QList<ExpressionType> ExpressionTypeChecker::computePairs(const QList<ExpressionType>& options, const ExpressionType& param)
0111 {
0112     QList<ExpressionType> ret;
0113
0114     if(param.type()==ExpressionType::Any) {
0115         int basestars=m_stars;
0116         foreach(const ExpressionType& opt, options) {
0117             ExpressionType toadd=opt;
0118             m_stars=qMax<int>(m_stars, toadd.increaseStars(basestars));
0119             QMap<int, ExpressionType> stars;
0120
0121             //We know the parameter is any, we don't have to infer
0122             stars=ExpressionType::computeStars(stars, param, toadd.parameters().first());
0123
0124             toadd.parameters().last().addAssumptions(param.assumptions());
0125             toadd.parameters().last()=toadd.parameters().last().starsToType(stars);
0126             ret += toadd;
0127         }
0128     } else
0129         foreach(const ExpressionType& opt, options) {
0130             if(opt.parameters().at(0).canReduceTo(param)) {//Infer on param!=param but canReduce?
0131                 QMap<int, ExpressionType> stars = ExpressionType::computeStars(QMap<int, ExpressionType>(), opt.parameters().at(0), param);
0132                 ret += opt.starsToType(stars);
0133             }
0134         }
0135
0136 //     qDebug() << "_______" << param << exp->toString() << ret;
0137     return ret;
0138 }
0139
0140 ExpressionType ExpressionTypeChecker::solve(const Operator* o, const QVector< Object* >& parameters)
0141 {
0142     Q_ASSERT(o->operatorType()!=Operator::function);
0143
0144     QList<ExpressionType> paramtypes;
0145     for(QVector<Object*>::const_iterator it=parameters.constBegin(), itEnd=parameters.constEnd(); it!=itEnd; ++it) {
0146         (*it)->accept(this);
0147         paramtypes += current;
0148     }
0149
0150     QList<ExpressionType> ret;
0151     if(parameters.size()==1) {
0152         QList<ExpressionType> types=paramtypes.first().type()==ExpressionType::Many ? paramtypes.first().alternatives() : QList<ExpressionType>() << paramtypes.first();
0153 //         const QMap<QString, ExpressionType> assumptions=current.assumptions();
0154
0155         foreach(const ExpressionType& t, types) {
0156             QList<ExpressionType> thing=computePairs(Operations::inferUnary(o->operatorType()), t);
0157             foreach(const ExpressionType& opt, thing) {
0158                 ExpressionType tt(opt.parameters().constLast());
0159                 tt.addAssumptions(t.assumptions());
0160                 ret+=tt;
0161             }
0162         }
0163 //         qDebug() << "bam" << ret ;
0164     } else {
0165         Q_ASSERT(parameters.size()>=2);
0166 //         QMap<int, ExpressionType> stars;
0167
0168         ExpressionType firstType=paramtypes.first();
0169         QList<ExpressionType> firstTypes= firstType.type()==ExpressionType::Many ?  firstType.alternatives() : QList<ExpressionType>() << firstType;
0170
0171         const QList<ExpressionType> res=Operations::infer(o->operatorType());
0172
0173         bool firstPair=true;
0174         for(QList<ExpressionType>::const_iterator it=paramtypes.constBegin()+1, itEnd=paramtypes.constEnd(); it!=itEnd; ++it, firstPair=false)
0175         {
0176             ExpressionType secondType=*it;
0177
0178             QList<ExpressionType> secondTypes=secondType.type()==ExpressionType::Many ? secondType.alternatives() : QList<ExpressionType>() << secondType;
0179             int starsbase=m_stars;
0180 //             static int ind=3;
0181 //             qDebug() << qPrintable("+" +QString(ind++, '-')) << o->toString() << firstType << secondType;
0182
0183             bool found = false;
0184             foreach(const ExpressionType& _first, firstTypes) {
0185                 foreach(const ExpressionType& _second, secondTypes) {
0186                     QMap<int, ExpressionType> _starToType;
0187                     bool matches=ExpressionType::matchAssumptions(&_starToType, _first.assumptions(), _second.assumptions());
0188
0189                     if(!matches) {
0190 //                         qDebug() << "peee" << ExpressionType::wrongAssumptions(_first.assumptions(), _second.assumptions());
0191                         continue;
0192                     }
0193                     foreach(const ExpressionType& _opt, res) {
0194                         ExpressionType opt(_opt);
0195                         m_stars=qMax<int>(m_stars, opt.increaseStars(starsbase));
0196
0197                         Q_ASSERT(!opt.parameters().last().isError());
0198                         QMap<int, ExpressionType> starToType, starToParam;
0199
0200                         bool valid = false;
0201                         QMap<QString, ExpressionType> assumptions;
0202
0203                         //NOTE In matrix multiplication (A*B) A may or not be reduced to B, since is allowed
0204                         //different matrix sizes provided that are valid sizes for the multiplication,
0205                         //thus we need a special case for matrix type
0206                         if (current.type() == ExpressionType::Matrix) {
0207                             ExpressionType first =_first .starsToType(_starToType);
0208                             ExpressionType second=_second.starsToType(_starToType);
0209
0210     //                         qDebug() << "9999999" << _first.assumptions() << first.assumptions() << starToType;
0211
0212                             starToType=ExpressionType::computeStars(starToType, first,  opt.parameters()[0]);
0213                             first =first .starsToType(starToType);
0214                             starToType=ExpressionType::computeStars(starToType, second, opt.parameters()[1]);
0215                             second=second.starsToType(starToType);
0216
0217                             assumptions=first.assumptions();
0218                             valid=ExpressionType::assumptionsMerge(assumptions, second.assumptions());
0219
0220     //                         qDebug() << "PPPPPP" << opt << first << second << "|||||" << first.assumptions() << second.assumptions();
0221
0222                             valid &= !first.isError() && !second.isError();
0223                             starToParam=ExpressionType::computeStars(starToParam, opt.parameters()[0], first);
0224     //                         qDebug() << "XXXXXX1" << starToParam;
0225                             valid &= first .canReduceTo(opt.parameters()[0].starsToType(starToParam));
0226                             starToParam=ExpressionType::computeStars(starToParam, opt.parameters()[1], second);
0227     //                         qDebug() << "XXXXXX2" << starToParam;
0228                             valid &= second.canReduceTo(opt.parameters()[1].starsToType(starToParam));
0229                         } else {
0230                             ExpressionType first =_first .starsToType(_starToType);
0231                             ExpressionType second=_second.starsToType(_starToType);
0232     //                         qDebug() << "9999999" << _first.assumptions() << first.assumptions() << starToType;
0233
0234                             starToType=ExpressionType::computeStars(starToType, first,  opt.parameters()[0]);
0235                             starToType=ExpressionType::computeStars(starToType, second, opt.parameters()[1]);
0236
0237                             first =first .starsToType(starToType);
0238                             second=second.starsToType(starToType);
0239
0240                             starToParam=ExpressionType::computeStars(starToParam, opt.parameters()[0], first);
0241                             starToParam=ExpressionType::computeStars(starToParam, opt.parameters()[1], second);
0242     //                         qDebug() << "XXXXXX" << starToParam;
0243     //                         qDebug() << "PPPPPP" << opt << first << second << "|||||" << first.assumptions() << second.assumptions();
0244
0245     //                         starToType=ExpressionType::computeStars(starToType, first,  opt.parameters()[0].starsToType(starToParam));
0246     //                         starToType=ExpressionType::computeStars(starToType, second, opt.parameters()[1].starsToType(starToParam));
0247
0248     //                         first =first .starsToType(starToType);
0249     //                         second=second.starsToType(starToType);
0250
0251                             assumptions=first.assumptions();
0252                             valid=ExpressionType::assumptionsMerge(assumptions, second.assumptions());
0253
0254     //                         qDebug() << "fifuuuuuuu" << first << (it-1)->toString() <<
0255     //                                                     second << it->toString() << assumptions << valid;
0256
0257                             valid &= !first.isError() && !second.isError();
0258                             valid &= first .canReduceTo(opt.parameters()[0].starsToType(starToParam));
0259                             valid &= second.canReduceTo(opt.parameters()[1].starsToType(starToParam));
0260
0261     //                         qDebug() << "POPOPO" << (it-1)->toString() << it->toString() << valid << first << second << starToParam;
0262                         }
0263
0264 //                         qDebug() << "POPOPO" << (it-1)->toString() << it->toString() << valid << first << second << starToParam;
0265                         if(valid) {
0266                             ExpressionType toadd=opt.parameters().last();
0267                             toadd.addAssumptions(assumptions);
0268                             toadd=toadd.starsToType(starToParam);
0269
0270                             if(firstPair) {
0271                                 ret += toadd;
0272                                 found = true;
0273                             } else {
0274                                 QList<ExpressionType>::iterator it=ret.begin(), itEnd=ret.end();
0275                                 for(; it!=itEnd; ++it) {
0276                                     QMap<int, ExpressionType> stars;
0277                                     if(toadd.canReduceTo(*it) && ExpressionType::matchAssumptions(&stars, it->assumptions(), toadd.assumptions())) {
0278                                         bool b=ExpressionType::assumptionsMerge(it->assumptions(), toadd.starsToType(stars).assumptions());
0279                                         Q_ASSERT(b);
0280                                         found = true;
0281                                         break;
0282                                     } else if(it->canReduceTo(toadd) && ExpressionType::matchAssumptions(&stars, it->assumptions(), toadd.assumptions())) {
0283                                         toadd=toadd.starsToType(stars);
0284                                         bool b=ExpressionType::assumptionsMerge(toadd.assumptions(), it->assumptions());
0285                                         Q_ASSERT(b);
0286                                         *it=toadd;
0287                                         found = true;
0288                                         break;
0289                                     }
0290                                 }
0291                             }
0292                         }
0293 //                         else
0294 //                         {
0295 //                             qDebug() << "lalala" << first << second;
0296 //                         }
0297                     }
0298                 }
0299             }
0300             if(!found) {
0301                 addError(QCoreApplication::tr("Could not find a type that unifies '%1'").arg(o->toString()));
0302             }
0303 //             qDebug() << qPrintable("\\"+QString(--ind, '-')) << o->toString() << ret;
0304         }
0305     }
0306
0307     if(ret.isEmpty())
0308         return ExpressionType(ExpressionType::Error);
0309     else if(ret.count()==1)
0310         return ret.first();
0311     else {
0312         ExpressionType t(ExpressionType::Many);
0313         foreach(const ExpressionType& alt, ret)
0314             t.addAlternative(alt);
0315         return t;
0316     }
0317 }
0318
0319 QVariant ExpressionTypeChecker::visit(const Ci* var)
0320 {
0321     if(m_typeForBVar.contains(var->name())) {
0322         current=m_typeForBVar.value(var->name());
0323     } else if(!m_lambdascope.contains(var->name()) && isVariableDefined(var->name())) {
0324         current=typeForVar(var->name());
0325     } else {
0326         current=ExpressionType(Analitza::ExpressionType::Any, m_stars++);
0327         bool ret = current.addAssumption(var->name(), current);
0328         Q_ASSERT(ret);
0329
0330         if(var->depth()<0 && !isVariableDefined(var->name()) && !m_calculating.contains(var->name()))
0331             m_deps += var->name();
0332     }
0333
0334     return QString();
0335 }
0336
0337 bool ExpressionTypeChecker::isVariableDefined(const QString& id) const
0338 {
0339     return m_v->contains(id) || m_vars.contains(id);
0340 }
0341
0342 QVariant ExpressionTypeChecker::visit(const Cn* c)
0343 {
0344     ExpressionType::Type type;
0345
0346     switch(c->format()) {
0347         case Cn::Boolean:
0348             type=ExpressionType::Bool;
0349             break;
0350         case Cn::Char:
0351             type=ExpressionType::Char;
0352             break;
0353         default:
0354             type=ExpressionType::Value;
0355             break;
0356     }
0357
0358     current=ExpressionType(type);
0359     return QString();
0360 }
0361
0362 QStringList objectsToString(const QList<Object*>& objs) {
0363     QStringList ret;
0364     foreach(const Object* o, objs) {
0365         ret+=o->toString();
0366     }
0367     return ret;
0368 }
0369
0370 ExpressionType ExpressionTypeChecker::commonType(const QList<Object*>& values)
0371 {
0372     ExpressionType ret;
0373
0374     if(values.isEmpty()) {
0375         ret=ExpressionType(ExpressionType::Any, m_stars++);
0376     } else foreach(const Object* o, values) {
0377         o->accept(this);
0378
0379 //         qDebug()<< "sususu" << current << ret << "||" << current.assumptions() << ret.assumptions();
0380
0381 //         qDebug() << "falala" << ret << current << stars;
0382         QList<ExpressionType> retalts;
0383         QList<ExpressionType> alts1=current.type()==ExpressionType::Many ? current.alternatives() : QList<ExpressionType>() << current;
0384         QList<ExpressionType> alts2=ret.type()==ExpressionType::Many ? ret.alternatives() : QList<ExpressionType>() << ret;
0385 // #error foreach + canReduce + computestars to tell that type of:foldr1==f==elems
0386
0387         foreach(const ExpressionType& t1, alts1) {
0388             QMap<int, ExpressionType> _stars;
0389             QMap<QString, ExpressionType> assumptions(ret.assumptions());
0390             bool b=ExpressionType::matchAssumptions(&_stars, current.assumptions(), assumptions);
0391             b &= ExpressionType::assumptionsMerge(assumptions, current.assumptions());
0392             if(!b) {
0393                 continue;
0394             }
0395
0396             foreach(const ExpressionType& t2, alts2) {
0397                 QMap<int, ExpressionType> stars(_stars);
0398
0399 //                 printAssumptions("commonnnnXX", t1);
0400 //                 printAssumptions("commonnnnYY", t2);
0401                 ExpressionType rr=ExpressionType::minimumType(t1, t2);
0402                 if(!rr.isError() && ExpressionType::matchAssumptions(&stars, t2.assumptions(), t1.assumptions())) {
0403                     stars=ExpressionType::computeStars(stars, t2, t1);
0404                     bool b=ExpressionType::assumptionsMerge(rr.assumptions(), assumptions);
0405 //                     Q_ASSERT(b);
0406 //                     qDebug() << "*************" << o->toString() << rr << b << "||||||" << stars;
0407 //                     printAssumptions("commonnnnWW", rr);
0408                     if(b)
0409                         retalts += rr.starsToType(stars);
0410 //                     printAssumptions("commonnnnZZ", retalts.last());
0411                 }
0412             }
0413         }
0414
0415         if(retalts.size()==1)
0416             ret=retalts.first();
0417         else if(retalts.isEmpty())
0418             ret=ExpressionType::Error;
0419         else
0420             ret=ExpressionType(ExpressionType::Many, retalts);
0421     }
0422
0423 //     printAssumptions("ffffffff", ret);
0424
0425     return ret;
0426 }
0427
0428 QVariant ExpressionTypeChecker::visit(const Apply* c)
0429 {
0430     QMap<QString, ExpressionType> ctx=m_typeForBVar;
0431     QMap<QString, ExpressionType> assumptions;
0432     Operator o=c->firstOperator();
0433
0434     if(o.isBounded()) {
0435         Object* ul=c->ulimit();
0436         ExpressionType tt;
0437         if(ul) {
0438             Object* dl=c->dlimit();
0439             ul->accept(this);
0440
0441             tt=current; //FIXME: should remove when done
0442             if(!current.isError() && current.type()!=ExpressionType::Any)
0443                 assumptions=typeIs(dl, ExpressionType(current));
0444             else {
0445                 dl->accept(this);
0446                 tt=current;
0447
0448                 if(!current.isError())
0449                     assumptions=typeIs(ul, ExpressionType(current));
0450             }
0451         } else if(c->domain()) {
0452             c->domain()->accept(this);
0453
0454             if(current.type()==ExpressionType::Any) {
0455                 ExpressionType anyItem(ExpressionType::Any, m_stars++);
0456
0457                 ExpressionType anyList(ExpressionType::List, anyItem);
0458                 ExpressionType anyVector(ExpressionType::Vector, anyItem, -1);
0459                 ExpressionType anyMatrix(ExpressionType::Matrix, ExpressionType(ExpressionType::Vector, anyItem, -2), -3);
0460
0461                 ExpressionType anyContainer(ExpressionType::Many);
0462                 anyContainer.addAlternative(anyList);
0463                 anyContainer.addAlternative(anyVector);
0464                 anyContainer.addAlternative(anyMatrix);
0465
0466                 bool ret = anyItem.addAssumption(static_cast<Ci*>(c->domain())->name(), anyContainer);
0467                 if(ret)
0468                     tt=anyItem;
0469             } else if(current.type()==ExpressionType::Vector || current.type()==ExpressionType::List || current.type()==ExpressionType::Matrix) {
0470                 tt=current.contained();
0471                 tt.addAssumptions(current.assumptions());
0472             } else
0473                 addError(QCoreApplication::tr("The domain should be either a vector or a list"));
0474             //TODO: should control the many case
0475         }
0476
0477         //FIXME: should remove when done
0478         foreach(const QString& s, c->bvarStrings())
0479             m_typeForBVar[s]=ExpressionType(tt);
0480     }
0481
0482     switch(o.operatorType()) {
0483         case Operator::none:
0484         case Operator::sum:
0485         case Operator::product:
0486             (*c->firstValue())->accept(this);
0487             current.addAssumptions(assumptions);
0488             break;
0489         case Operator::diff:
0490             //TODO Check inside
0491
0492             current=ExpressionType(ExpressionType::Lambda);
0493             current.addParameter(ExpressionType::Value);
0494             current.addParameter(ExpressionType::Value);
0495             break;
0496         case Operator::function: {
0497 //                     qDebug() << "calling" << c->toString();
0498             c->m_params.first()->accept(this);
0499 //                     qDebug() << "retrieved lambda" << c->m_params.first()->toString() << current << current.assumptions();
0500             ExpressionType returned = current;
0501             assumptions=current.assumptions();
0502
0503             QList<ExpressionType> exps;
0504             Apply::const_iterator it=c->firstValue()+1, itEnd=c->constEnd();
0505             for(; it!=itEnd; ++it) {
0506                 (*it)->accept(this);
0507
0508                 exps += current;
0509             }
0510
0511             if(returned.type()==ExpressionType::Any) {
0512                 ExpressionType ret=ExpressionType(ExpressionType::Any, m_stars++);
0513 //                 qDebug() << "fffffffffffffff" << m_stars;
0514                 ret.addAssumptions(assumptions);
0515
0516                 exps += ret;
0517                 QList<ExpressionType> t=ExpressionType::lambdaFromArgs(exps);
0518 //                 qDebug() << "OOOOOOOOOOOOOOOOOOOOOOO" << c->toString() << ret /*<< stars*/ << ret.assumptions() << "||||" << t << exps;
0519
0520                 ExpressionType ret2(ExpressionType::Many);
0521                 bool error=false;
0522                 foreach(const ExpressionType& type, t) {
0523                     ExpressionType returntype(type.parameters().constLast());
0524                     returntype.addAssumptions(type.assumptions());
0525                     if(c->m_params.first()->type()==Object::variable) {
0526                         QString name=static_cast<Ci*>(c->m_params.first())->name();
0527                         QMap<QString, ExpressionType>::const_iterator itf=returntype.assumptions().constFind(name);
0528
0529                         if(itf!=returntype.assumptions().constEnd() && itf->type()==ExpressionType::Lambda) {
0530                             ExpressionType oldt=ExpressionType::minimumType(*itf, type);
0531                             error=!oldt.addAssumption(name, oldt);
0532                             if(error)
0533                                 break;
0534                             QMap<int,ExpressionType> stars;
0535                             stars=ExpressionType::computeStars(stars, type, oldt);
0536                             bool b=ExpressionType::matchAssumptions(&stars, oldt.assumptions(), type.assumptions());
0537                             Q_ASSERT(b);
0538
0539                             oldt=oldt.starsToType(stars);
0540 //                             qDebug() << "hmmm..." << oldt << stars << type << "::::::\n\t" << oldt.assumptions() << "\n\t" << type.assumptions();
0541                             returntype=oldt.parameters().constLast();
0542 //                             printAssumptions("reeeeet", returntype);
0543
0544                             error = !returntype.addAssumption(name, oldt); //can't happen, we already checked it's not an assumption
0545                             Q_ASSERT(!error);
0546                         } else {
0547                             error = !returntype.addAssumption(name, type);
0548                             if(error)
0549                                 break;
0550                         }
0551                     }
0552                     returntype.addAssumptions(type.assumptions());
0553
0554                     ret2.addAlternative(returntype);
0555                 }
0556
0557                 if(error) {
0558                     addError(QCoreApplication::translate("type error message", "Cannot call '%1'").arg(c->m_params.first()->toString()));
0559                     current=ExpressionType(ExpressionType::Error);
0560                 } else
0561                     current=ret2;
0562             } else if(returned.isError()) {
0563                 current=ExpressionType(ExpressionType::Error);
0564             }
0565             else {
0566                 ExpressionType ret(ExpressionType::Many), signature(returned);
0567
0568                 QList<ExpressionType> alts=signature.type()==ExpressionType::Many ? signature.alternatives() : QList<ExpressionType>() << signature;
0569                 QList<ExpressionType> args=ExpressionType::lambdaFromArgs(exps);
0570                 bool exit=false;
0571                 foreach(const ExpressionType& opt, alts) {
0572                     if(opt.type()!=ExpressionType::Lambda) {
0573 //                                 addError(i18n("We can only call functions."));
0574                         continue;
0575                     }
0576
0577                     const bool isvariadic = (opt.parameters().at(0).type() == ExpressionType::Any);
0578                     //if we have a variadic check only the return type (that is why we put 0 as args count here)
0579                     const int nargs = opt.parameters().size()-1;
0580
0581                     foreach(const ExpressionType& f, args) {
0582                         QList<ExpressionType> altargs=f.parameters();
0583
0584                         bool valid=true;
0585
0586                         if (isvariadic) { // if is variadic don't check the number of args
0587                             Q_ASSERT(opt.parameters().size() == 2); // Any and return type
0588
0589                             //when use Any with contained we need to check if all args must be of the contained type
0590                             if (opt.parameters().at(0).hasContained()) {
0591                                 for(int i=0; valid && i<altargs.size(); i++) {
0592                                     if(!altargs[i].canReduceTo(opt.parameters().at(0).contained())) {
0593                                         addError(QCoreApplication::tr("Cannot reduce '%1' to '%2'. Invalid type of parameter '%3' for '%4'").
0594                                         arg(altargs[i].toString(), opt.parameters().at(0).contained().toString()).
0595                                         arg(i+1).
0596                                         arg(c->toString()));
0597
0598                                         valid=false;
0599                                         break;
0600                                     }
0601                                 }
0602                             }
0603                         } else if(opt.parameters().size()!=altargs.size()+1) {
0604                             addError(QCoreApplication::tr("Invalid parameter count for '%2'. Should have %1 parameters.").arg(opt.parameters().size()-1).arg(c->toString()));
0605                             exit=true;
0606                             break;
0607                         }
0608
0609                         QMap<QString, ExpressionType> assumptions;
0610                         QMap<int, ExpressionType> starToType, starToParam;
0611
0612                         for(int i=0; valid && i<nargs; i++) {
0613                             if (i<opt.parameters().size() && i<altargs.size()) {
0614                                 if(!altargs[i].canCompareTo(opt.parameters().at(i))) {
0615                                     if (isvariadic)
0616                                         addError(QCoreApplication::tr("Cannot compare '%1' to '%2'. Invalid type of parameter '%3' for '%4'").
0617                                         arg(altargs[i].toString(), opt.parameters().at(i).toString()).
0618                                         arg(i+1).
0619                                         arg(c->toString()));
0620
0621                                     valid=false;
0622                                     break;
0623                                 }
0624
0625                                 starToType=ExpressionType::computeStars(starToType, opt.parameters().at(i), altargs[i]);
0626
0627                                 ExpressionType t=opt.parameters().at(i).starsToType(starToType);
0628                                 starToParam=ExpressionType::computeStars(starToParam, altargs[i], t);
0629                                 valid=!t.isError() && inferType(altargs[i].starsToType(starToParam), t, &assumptions);
0630
0631 //                                 qDebug() << "pepeluis" << c->toString() << c->m_params[i+1]->toString() << altargs[i] << t << valid;
0632                             }
0633                         }
0634
0635                         valid &= ExpressionType::matchAssumptions(&starToType, opt.parameters().constLast().assumptions(), assumptions);
0636
0637                         if(valid) {
0638                             ExpressionType t=opt.parameters().constLast();
0639
0640                             t.addAssumptions(assumptions);
0641
0642                             ret.addAlternative(t.starsToType(starToType));
0643                         }
0644                     }
0645
0646                     if(exit)
0647                         break;
0648                 }
0649
0650                 if(ret.alternatives().isEmpty()) {
0651 //                     qDebug() << "peee" << c->toString() << signature << exps;
0652
0653                     current=ExpressionType(ExpressionType::Error);
0654                     addError(QCoreApplication::tr("Could not call '%1'").arg(c->toString()));
0655                 } else
0656                     current=ret;
0657             }
0658         } break;
0659         default:
0660             current=solve(&o, c->values());
0661             if(current.type()==ExpressionType::Error)
0662                 addError(QCoreApplication::tr("Could not solve '%1'").arg(c->toString()));
0663             break;
0664     }
0665
0666     current.removeAssumptions(c->bvarStrings());
0667
0668     m_typeForBVar=ctx;
0669
0670     if(current.type()==ExpressionType::Many && current.alternatives().size()==1) {
0671         current=current.alternatives().at(0);
0672     }
0673
0674     return QString();
0675 }
0676
0677 QVariant ExpressionTypeChecker::visit(const CustomObject*)
0678 {
0679     Q_ASSERT(false && "we shouldn't have to construct any custom object");
0680     return QString();
0681 }
0682
0683 ExpressionType ExpressionTypeChecker::tellTypeIdentity(const QString& name, const ExpressionType& type)
0684 {
0685     QList<ExpressionType> opts=type.type()==ExpressionType::Many ? type.alternatives() : QList<ExpressionType>() << type;
0686
0687     for(QList< ExpressionType >::iterator it=opts.begin(), itEnd=opts.end(); it!=itEnd; ++it) {
0688         QMap< QString, ExpressionType >::const_iterator itFound=it->assumptions().constFind(name);
0689
0690         if(itFound!=it->assumptions().constEnd()) {
0691             QList<ExpressionType> optsFound=itFound->type()==ExpressionType::Many ? itFound->alternatives() : QList<ExpressionType>() << *itFound;
0692             for(QList< ExpressionType >::iterator itf=optsFound.begin(), itfEnd=optsFound.end(); itf!=itfEnd; ++itf) {
0693                 if(!itf->canReduceTo(type)) {
0694 //                     qDebug() << "incoherent type" << *itf << type;
0695                     addError(QCoreApplication::tr("Incoherent type for the variable '%1'").arg(name));
0696                     break;
0697                 }
0698                 QMap<int, ExpressionType> stars;
0699                 stars=ExpressionType::computeStars(stars, *itf, *it);
0700 //                 qDebug() << "fiiiiiiiii" << stars  << "\n\t" << *it << "\n\t" << *itFound;
0701                 *it=it->starsToType(stars);
0702             }
0703         }
0704     }
0705     return ExpressionType(ExpressionType::Many, opts);
0706 }
0707
0708 //1. Check if parameters are applied correctly
0709 //2. Return the operator result type
0710 QVariant ExpressionTypeChecker::visit(const Container* c)
0711 {
0712 //     qDebug() << "XIUXIU" << c->toString();
0713     switch(c->containerType()) {
0714         case Container::piecewise: {
0715             ExpressionType type=commonType(c->m_params);
0716
0717             if(type.isError()) {
0718                 addError(QCoreApplication::tr("Could not determine the type for piecewise"));
0719                 current=type;
0720             } else {
0721                 QList<ExpressionType> alts=type.type()==ExpressionType::Many ? type.alternatives() : QList<ExpressionType>() << type, alts2;
0722
0723                 for(QList< ExpressionType >::iterator it=alts.begin(), itEnd=alts.end(); it!=itEnd; ++it) {
0724                     QMap<QString, ExpressionType> assumptions=typeIs(c->constBegin(), c->constEnd(), *it);
0725
0726     //                 QMap<int, ExpressionType> stars;
0727     //                 bool b=ExpressionType::matchAssumptions(&stars, assumptions, type.assumptions());
0728     //                 Q_ASSERT(b);
0729     //                 type=type.starsToType(stars);
0730
0731 //                     qDebug() << "suuuuu\n\t" << it->assumptions() << "\n\t" << assumptions;
0732                     QMap<int, ExpressionType> stars;
0733                     bool b=ExpressionType::matchAssumptions(&stars, it->assumptions(), assumptions);
0734                     b&=ExpressionType::assumptionsMerge(it->assumptions(), assumptions);
0735 //                     qDebug() << "fefefe" << b << it->assumptions();
0736
0737                     if(b) {
0738                         alts2 += *it;
0739 //                         qDebug() << "!!!" << it->assumptions() << b;
0740                     }
0741                 }
0742                 current=ExpressionType(ExpressionType::Many, alts2);
0743             }
0744
0745         }    break;
0746         case Container::piece: {
0747             QMap<QString, ExpressionType> assumptions=typeIs(c->m_params.constLast(), ExpressionType(ExpressionType::Bool)); //condition check
0748             c->m_params.first()->accept(this); //we return the body
0749             QList<ExpressionType> alts=current.type()==ExpressionType::Many ? current.alternatives() : QList<ExpressionType>() << current, rets;
0750             foreach(const ExpressionType& t, alts) {
0751                 QMap<int, ExpressionType> stars;
0752                 ExpressionType toadd=t;
0753                 bool b=ExpressionType::assumptionsMerge(toadd.assumptions(), assumptions);
0754
0755                 b&=ExpressionType::matchAssumptions(&stars, assumptions, t.assumptions());
0756
0757                 if(b) {
0758                     toadd=toadd.starsToType(stars);
0759
0760                     rets += toadd;
0761                 }
0762             }
0763             current=ExpressionType(ExpressionType::Many, rets);
0764         }    break;
0765         case Container::declare:{
0766             Q_ASSERT(c->m_params.first()->type()==Object::variable);
0767             Ci* var = static_cast<Ci*>(c->m_params.first());
0768
0769             m_calculating.append(var->name());
0770             c->m_params.constLast()->accept(this);
0771             m_calculating.removeLast();
0772
0773             current=tellTypeIdentity(var->name(), current);
0774         }    break;
0775         case Container::lambda: {
0776             QSet<QString> aux=m_lambdascope;
0777             QStringList bvars=c->bvarStrings();
0778             m_lambdascope+=QSet<QString>(bvars.begin(), bvars.end());
0779             c->m_params.constLast()->accept(this);
0780             m_lambdascope=aux;
0781
0782             QList<ExpressionType> alts=current.type()==ExpressionType::Many ? current.alternatives() : QList<ExpressionType>() << current;
0783             ExpressionType res=ExpressionType(ExpressionType::Many);
0784             foreach(const ExpressionType& alt, alts) {
0785                 QList<ExpressionType> args;
0786                 foreach(const QString& bvar, bvars) {
0787                     ExpressionType toadd;
0788                     if(alt.assumptions().contains(bvar))
0789                         toadd=alt.assumptionFor(bvar);
0790                     else
0791                         toadd=ExpressionType(ExpressionType::Any, m_stars++);
0792
0793 //                     qDebug() << "valueee" << bvar << toadd;
0794                     args += toadd;
0795                 }
0796                 args += alt;
0797
0798                 args=ExpressionType::lambdaFromArgs(args);
0799
0800                 res.addAlternative(ExpressionType(ExpressionType::Many, args));
0801             }
0802             current=res;
0803             current.removeAssumptions(bvars);
0804         }    break;
0805         case Container::otherwise:
0806         case Container::math:
0807         case Container::none:
0808         case Container::downlimit:
0809         case Container::uplimit:
0810         case Container::bvar:
0811         case Container::domainofapplication:
0812 //             for(Container::const_iterator it=c->constBegin(); it!=c->constEnd(); ++it)
0813 //             Q_ASSERT(c->constBegin()+1==c->constEnd());
0814             if(c->constBegin()+1==c->constEnd())
0815                 (*c->constBegin())->accept(this);
0816             break;
0817     }
0818
0819     if(current.type()==ExpressionType::Many) {
0820         if(current.alternatives().isEmpty())
0821             current=ExpressionType(ExpressionType::Error);
0822         else if(current.alternatives().count()==1)
0823             current=current.alternatives().at(0);
0824     }
0825
0826     return QString();
0827 }
0828
0829 template <class T>
0830 QVariant ExpressionTypeChecker::visitListOrVector(const T* v, ExpressionType::Type t, int size)
0831 {
0832     ExpressionType cont=commonType(v->values());
0833
0834     if(cont.type()==ExpressionType::Many) {
0835         ExpressionType toret(ExpressionType::Many);
0836         foreach(const ExpressionType& contalt, cont.alternatives()) {
0837             QMap<QString, ExpressionType> assumptions;
0838             assumptions=typeIs(v->constBegin(), v->constEnd(), contalt);
0839             ExpressionType cc(t, contalt, size);
0840
0841             bool b=ExpressionType::assumptionsMerge(cc.assumptions(), assumptions);
0842             if(b)
0843                 toret.addAlternative(cc);
0844         }
0845
0846         current=toret;
0847     } else if(!cont.isError()) {
0848         QMap<QString, ExpressionType> assumptions=typeIs(v->constBegin(), v->constEnd(), cont);
0849         current=ExpressionType(t, cont, size);
0850         current.addAssumptions(assumptions);
0851     } else
0852         current=ExpressionType(ExpressionType::Error);
0853
0854     return QString();
0855 }
0856
0857 QVariant ExpressionTypeChecker::visit(const List* l)
0858 {
0859     visitListOrVector(l, ExpressionType::List, 0);
0860     return QString();
0861 }
0862
0863 QVariant ExpressionTypeChecker::visit(const Vector* l)
0864 {
0865     visitListOrVector(l, ExpressionType::Vector, l->size());
0866     return QString();
0867 }
0868
0869 QVariant ExpressionTypeChecker::visit(const Matrix* m)
0870 {
0871     const Matrix* v = m;
0872     ExpressionType::Type t = ExpressionType::Matrix;
0873     int size = m->rowCount();
0874
0875     QList<Object*> values;
0876     foreach(MatrixRow *row, m->rows())
0877         values.append(row);
0878
0879     ExpressionType cont=commonType(values);
0880
0881     if(cont.type()==ExpressionType::Many) {
0882         ExpressionType toret(ExpressionType::Many);
0883         foreach(const ExpressionType& contalt, cont.alternatives()) {
0884             QMap<QString, ExpressionType> assumptions;
0885             assumptions=typeIs(v->constBegin(), v->constEnd(), contalt);
0886             ExpressionType cc(t, contalt, size);
0887
0888             bool b=ExpressionType::assumptionsMerge(cc.assumptions(), assumptions);
0889             if(b)
0890                 toret.addAlternative(cc);
0891         }
0892
0893         current=toret;
0894     } else if(!cont.isError()) {
0895         QMap<QString, ExpressionType> assumptions=typeIs(v->constBegin(), v->constEnd(), cont);
0896         current=ExpressionType(t, cont, size);
0897         current.addAssumptions(assumptions);
0898     } else
0899         current=ExpressionType(ExpressionType::Error);
0900
0901     return QString();
0902 }
0903
0904 QVariant ExpressionTypeChecker::visit(const MatrixRow* mr)
0905 {
0906     visitListOrVector(mr, ExpressionType::Vector, mr->size());
0907     return QString();
0908 }
0909
0910 template <class T>
0911 QMap<QString, ExpressionType> ExpressionTypeChecker::typeIs(T it, const T& itEnd, const ExpressionType& type)
0912 {
0913     QList<ExpressionType> types;
0914     for(; it!=itEnd; ++it) {
0915         (*it)->accept(this);
0916         types+=current;
0917     }
0918     types=ExpressionType::manyFromArgs(types);
0919
0920     bool valid=false;
0921     QMap<QString, ExpressionType> ret;
0922
0923     foreach(const ExpressionType& tmany, types) {
0924         bool v=true;
0925         QMap<QString, ExpressionType> ret2;
0926         foreach(const ExpressionType& t, tmany.alternatives()) {
0927             v&=inferType(t, type, &ret2);
0928         }
0929
0930         if(v) {
0931             valid=true;
0932             ExpressionType::assumptionsUnion(ret, ret2);
0933         }
0934     }
0935
0936     if(!valid)
0937         addError(QCoreApplication::tr("Unexpected type"));
0938     return ret;
0939 }
0940
0941 QMap<QString, ExpressionType> ExpressionTypeChecker::typeIs(const Object* o, const ExpressionType& type)
0942 {
0943     o->accept(this);
0944 //     qDebug() << "fluuuu" << current << type;
0945
0946     bool corr=false;
0947     QList<ExpressionType> alts = current.type()==ExpressionType::Many ? current.alternatives() : QList<ExpressionType>() << current;
0948
0949     QMap<QString, ExpressionType> assumptions(m_typeForBVar);
0950     foreach(const ExpressionType& t, alts) {
0951         QMap<QString, ExpressionType> ass;
0952         bool correct = inferType(t, type, &ass);
0953         if(correct) {
0954             ExpressionType::assumptionsUnion(assumptions, ass);
0955         }
0956         corr|=correct;
0957     }
0958
0959     if(!corr)
0960         addError(QCoreApplication::tr("Cannot convert '%1' to '%2'").arg(o->toString(), type.toString()));
0961
0962     return assumptions;
0963 }
0964
0965 ExpressionType ExpressionTypeChecker::typeForVar(const QString& var)
0966 {
0967     if(m_calculating.contains(var))
0968         return ExpressionType(ExpressionType::Any, m_stars++);
0969     else if(!m_vars.contains(var)) {
0970 //         qDebug() << "checking..." << var;
0971         Q_ASSERT(m_v->contains(var));
0972         m_calculating += var;
0973         m_v->value(var)->accept(this);
0974         m_calculating.removeLast();
0975         current=tellTypeIdentity(var, current);
0976         current.clearAssumptions();
0977         current.simplifyStars();
0978         m_vars[var]=current;
0979 //         qDebug() << "checked type" << var << "=" << current;
0980     }
0981
0982     ExpressionType ret=m_vars.value(var);
0983
0984 //     qDebug() << "P/P/P/P/P/" << ret;
0985     m_stars=ret.increaseStars(m_stars);
0986 //     qDebug() << "P/P/P/P/P/" << ret;
0987     return ret;
0988 }
0989
0990 QStringList ExpressionTypeChecker::errors() const
0991 {
0992     QStringList ret;
0993     foreach(const QStringList& errs, m_err)
0994         ret << errs;
0995     return ret;
0996 }
0997
0998 void ExpressionTypeChecker::addError(const QString& err)
0999 {
1000     if(m_err.isEmpty())
1001         m_err += QStringList();
1002
1003     m_err.last().append(err);
1004 }
1005
1006 void ExpressionTypeChecker::initializeVars(const QMap< QString, ExpressionType >& types)
1007 {
1008     m_vars=types;
1009 }
1010
1011 QMap<QString, ExpressionType> ExpressionTypeChecker::variablesTypes() const
1012 {
1013     return m_vars;
1014 }
1015
1016 QVariant ExpressionTypeChecker::visit(const None* ) { Q_ASSERT(false && "should not get here"); return QVariant(); }
1017
1018 }