Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
108 kB · 3224 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/* * Main authors: * Guido Tack <guido.tack@monash.edu> */
/* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include <minizinc/astexception.hh>#include <minizinc/astiterator.hh>#include <minizinc/copy.hh>#include <minizinc/eval_par.hh>#include <minizinc/flat_exp.hh>#include <minizinc/flatten.hh>#include <minizinc/hash.hh>#include <minizinc/iter.hh>
#include <cmath>
namespace MiniZinc {
bool check_par_domain(EnvI& env, Expression* e, Expression* domain) { if (e->type() == Type::parint()) { IntSetVal* isv = eval_intset(env, domain); if (!isv->contains(eval_int(env, e))) { return false; } } else if (e->type() == Type::parfloat()) { FloatSetVal* fsv = eval_floatset(env, domain); if (!fsv->contains(eval_float(env, e))) { return false; } } else if (e->type() == Type::parsetint()) { IntSetVal* isv = eval_intset(env, domain); IntSetRanges ir(isv); IntSetVal* rsv = eval_intset(env, e); IntSetRanges rr(rsv); if (!Ranges::subset(rr, ir)) { return false; } } else if (e->type() == Type::parsetfloat()) { FloatSetVal* fsv = eval_floatset(env, domain); FloatSetRanges fr(fsv); FloatSetVal* rsv = eval_floatset(env, e); FloatSetRanges rr(rsv); if (!Ranges::subset(rr, fr)) { return false; } } return true;}
void check_par_declaration(EnvI& env, VarDecl* vd) { if (vd->type().dim() > 0) { check_index_sets(env, vd, vd->e()); if (vd->ti()->domain() != nullptr) { ArrayLit* al = eval_array_lit(env, vd->e()); for (unsigned int i = 0; i < al->size(); i++) { if (!check_par_domain(env, (*al)[i], vd->ti()->domain())) { throw ResultUndefinedError(env, vd->e()->loc(), "parameter value out of range"); } } } } else { if (vd->ti()->domain() != nullptr) { if (!check_par_domain(env, vd->e(), vd->ti()->domain())) { throw ResultUndefinedError(env, vd->e()->loc(), "parameter value out of range"); } } }}
template <class E>typename E::Val eval_id(EnvI& env, Expression* e) { Id* id = e->cast<Id>(); if (!id->decl()) { throw EvalError(env, e->loc(), "undeclared identifier", id->str()); } VarDecl* vd = id->decl(); while (vd->flat() && vd->flat() != vd) { vd = vd->flat(); } if (!vd->e()) { throw EvalError(env, vd->loc(), "cannot evaluate expression", id->str()); } typename E::Val r = E::e(env, vd->e()); if (!vd->evaluated() && (vd->toplevel() || vd->type().dim() > 0)) { Expression* ne = E::exp(r); vd->e(ne); vd->evaluated(true); } return r;}
bool EvalBase::evalBoolCV(EnvI& env, Expression* e) { GCLock lock; if (e->type().cv()) { return eval_bool(env, flat_cv_exp(env, Ctx(), e)()); } return eval_bool(env, e);};
KeepAlive EvalBase::flattenCV(EnvI& env, Expression* e) { GCLock lock; Ctx ctx; ctx.i = C_MIX; ctx.b = (e->type().bt() == Type::BT_BOOL) ? C_MIX : C_ROOT; EE ee = flat_exp(env, ctx, e, nullptr, constants().varTrue); return ee.r;}
class EvalIntLit : public EvalBase {public: typedef IntLit* Val; typedef Expression* ArrayVal; static IntLit* e(EnvI& env, Expression* e) { return IntLit::a(eval_int(env, e)); } static Expression* exp(IntLit* e) { return e; }};class EvalIntVal : public EvalBase {public: typedef IntVal Val; typedef IntVal ArrayVal; static IntVal e(EnvI& env, Expression* e) { return eval_int(env, e); } static Expression* exp(IntVal e) { return IntLit::a(e); } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) { if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) { IntSetVal* isv = eval_intset(env, fi->ti()->domain()); if (!isv->contains(v)) { throw ResultUndefinedError(env, Location().introduce(), "function result violates function type-inst"); } } }};class EvalFloatVal : public EvalBase {public: typedef FloatVal Val; typedef FloatVal ArrayVal; static FloatVal e(EnvI& env, Expression* e) { return eval_float(env, e); } static Expression* exp(FloatVal e) { return FloatLit::a(e); } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) { if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) { FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain()); if (!fsv->contains(v)) { throw ResultUndefinedError(env, Location().introduce(), "function result violates function type-inst"); } } }};class EvalFloatLit : public EvalBase {public: typedef FloatLit* Val; typedef Expression* ArrayVal; static FloatLit* e(EnvI& env, Expression* e) { return FloatLit::a(eval_float(env, e)); } static Expression* exp(Expression* e) { return e; }};class EvalString : public EvalBase {public: typedef std::string Val; typedef std::string ArrayVal; static std::string e(EnvI& env, Expression* e) { return eval_string(env, e); } static Expression* exp(const std::string& e) { return new StringLit(Location(), e); } static void checkRetVal(EnvI& env, const Val& v, FunctionI* fi) {}};class EvalStringLit : public EvalBase {public: typedef StringLit* Val; typedef Expression* ArrayVal; static StringLit* e(EnvI& env, Expression* e) { return new StringLit(Location(), eval_string(env, e)); } static Expression* exp(Expression* e) { return e; }};class EvalBoolLit : public EvalBase {public: typedef BoolLit* Val; typedef Expression* ArrayVal; static BoolLit* e(EnvI& env, Expression* e) { return constants().boollit(eval_bool(env, e)); } static Expression* exp(Expression* e) { return e; }};class EvalBoolVal : public EvalBase {public: typedef bool Val; static bool e(EnvI& env, Expression* e) { return eval_bool(env, e); } static Expression* exp(bool e) { return constants().boollit(e); } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}};class EvalArrayLit : public EvalBase {public: typedef ArrayLit* Val; typedef Expression* ArrayVal; static ArrayLit* e(EnvI& env, Expression* e) { return eval_array_lit(env, e); } static Expression* exp(Expression* e) { return e; }};class EvalArrayLitCopy : public EvalBase {public: typedef ArrayLit* Val; typedef Expression* ArrayVal; static ArrayLit* e(EnvI& env, Expression* e) { return copy(env, eval_array_lit(env, e), true)->cast<ArrayLit>(); } static Expression* exp(Expression* e) { return e; } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) { for (unsigned int i = 0; i < fi->ti()->ranges().size(); i++) { if ((fi->ti()->ranges()[i]->domain() != nullptr) && !fi->ti()->ranges()[i]->domain()->isa<TIId>()) { IntSetVal* isv = eval_intset(env, fi->ti()->ranges()[i]->domain()); bool bothEmpty = isv->min() > isv->max() && v->min(i) > v->max(i); if (!bothEmpty && (v->min(i) != isv->min() || v->max(i) != isv->max())) { std::ostringstream oss; oss << "array index set " << (i + 1) << " of function result violates function type-inst"; throw ResultUndefinedError(env, fi->e()->loc(), oss.str()); } } } if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>() && fi->ti()->type().ti() == Type::TI_PAR) { Type base_t = fi->ti()->type(); if (base_t.bt() == Type::BT_INT) { IntSetVal* isv = eval_intset(env, fi->ti()->domain()); if (base_t.st() == Type::ST_PLAIN) { for (unsigned int i = 0; i < v->size(); i++) { IntVal iv = eval_int(env, (*v)[i]); if (!isv->contains(iv)) { std::ostringstream oss; oss << "array contains value " << iv << " which is not contained in " << *isv; throw ResultUndefinedError( env, fi->e()->loc(), "function result violates function type-inst, " + oss.str()); } } } else { for (unsigned int i = 0; i < v->size(); i++) { IntSetVal* iv = eval_intset(env, (*v)[i]); IntSetRanges isv_r(isv); IntSetRanges v_r(iv); if (!Ranges::subset(v_r, isv_r)) { std::ostringstream oss; oss << "array contains value " << *iv << " which is not a subset of " << *isv; throw ResultUndefinedError( env, fi->e()->loc(), "function result violates function type-inst, " + oss.str()); } } } } else if (base_t.bt() == Type::BT_FLOAT) { FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain()); if (base_t.st() == Type::ST_PLAIN) { for (unsigned int i = 0; i < v->size(); i++) { FloatVal fv = eval_float(env, (*v)[i]); if (!fsv->contains(fv)) { std::ostringstream oss; oss << "array contains value " << fv << " which is not contained in " << *fsv; throw ResultUndefinedError( env, fi->e()->loc(), "function result violates function type-inst, " + oss.str()); } } } else { for (unsigned int i = 0; i < v->size(); i++) { FloatSetVal* fv = eval_floatset(env, (*v)[i]); FloatSetRanges fsv_r(fsv); FloatSetRanges v_r(fv); if (!Ranges::subset(v_r, fsv_r)) { std::ostringstream oss; oss << "array contains value " << *fv << " which is not a subset of " << *fsv; throw ResultUndefinedError( env, fi->e()->loc(), "function result violates function type-inst, " + oss.str()); } } } } } }};class EvalIntSet : public EvalBase {public: typedef IntSetVal* Val; static IntSetVal* e(EnvI& env, Expression* e) { return eval_intset(env, e); } static Expression* exp(IntSetVal* e) { return new SetLit(Location(), e); } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) { if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) { IntSetVal* isv = eval_intset(env, fi->ti()->domain()); IntSetRanges isv_r(isv); IntSetRanges v_r(v); if (!Ranges::subset(v_r, isv_r)) { throw ResultUndefinedError(env, Location().introduce(), "function result violates function type-inst"); } } }};class EvalFloatSet : public EvalBase {public: typedef FloatSetVal* Val; static FloatSetVal* e(EnvI& env, Expression* e) { return eval_floatset(env, e); } static Expression* exp(FloatSetVal* e) { return new SetLit(Location(), e); } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) { if ((fi->ti()->domain() != nullptr) && !fi->ti()->domain()->isa<TIId>()) { FloatSetVal* fsv = eval_floatset(env, fi->ti()->domain()); FloatSetRanges fsv_r(fsv); FloatSetRanges v_r(v); if (!Ranges::subset(v_r, fsv_r)) { throw ResultUndefinedError(env, Location().introduce(), "function result violates function type-inst"); } } }};class EvalBoolSet : public EvalBase {public: typedef IntSetVal* Val; static IntSetVal* e(EnvI& env, Expression* e) { return eval_boolset(env, e); } static Expression* exp(IntSetVal* e) { auto* sl = new SetLit(Location(), e); sl->type(Type::parsetbool()); return sl; } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}};class EvalSetLit : public EvalBase {public: typedef SetLit* Val; typedef Expression* ArrayVal; static SetLit* e(EnvI& env, Expression* e) { return eval_set_lit(env, e); } static Expression* exp(Expression* e) { return e; }};class EvalFloatSetLit : public EvalBase {public: typedef SetLit* Val; typedef Expression* ArrayVal; static SetLit* e(EnvI& env, Expression* e) { return new SetLit(e->loc(), eval_floatset(env, e)); } static Expression* exp(Expression* e) { return e; }};class EvalBoolSetLit : public EvalBase {public: typedef SetLit* Val; typedef Expression* ArrayVal; static SetLit* e(EnvI& env, Expression* e) { auto* sl = new SetLit(e->loc(), eval_boolset(env, e)); sl->type(Type::parsetbool()); return sl; } static Expression* exp(Expression* e) { return e; }};class EvalCopy : public EvalBase {public: typedef Expression* Val; typedef Expression* ArrayVal; static Expression* e(EnvI& env, Expression* e) { return copy(env, e, true); } static Expression* exp(Expression* e) { return e; }};class EvalPar : public EvalBase {public: typedef Expression* Val; typedef Expression* ArrayVal; static Expression* e(EnvI& env, Expression* e) { return eval_par(env, e); } static Expression* exp(Expression* e) { return e; } static void checkRetVal(EnvI& env, Val v, FunctionI* fi) {}};
void check_dom(EnvI& env, Id* arg, IntSetVal* dom, Expression* e) { bool oob = false; if (!e->type().isOpt()) { if (e->type().isIntSet()) { IntSetVal* ev = eval_intset(env, e); IntSetRanges ev_r(ev); IntSetRanges dom_r(dom); oob = !Ranges::subset(ev_r, dom_r); } else { oob = !dom->contains(eval_int(env, e)); } } if (oob) { std::ostringstream oss; oss << "value for argument `" << *arg << "' out of bounds"; throw EvalError(env, e->loc(), oss.str()); }}
void check_dom(EnvI& env, Id* arg, FloatVal dom_min, FloatVal dom_max, Expression* e) { if (!e->type().isOpt()) { FloatVal ev = eval_float(env, e); if (ev < dom_min || ev > dom_max) { std::ostringstream oss; oss << "value for argument `" << *arg << "' out of bounds"; throw EvalError(env, e->loc(), oss.str()); } }}
template <class Eval, class CallClass = Call>typename Eval::Val eval_call(EnvI& env, CallClass* ce) { std::vector<Expression*> previousParameters(ce->decl()->paramCount()); std::vector<Expression*> params(ce->decl()->paramCount()); for (unsigned int i = 0; i < ce->decl()->paramCount(); i++) { params[i] = eval_par(env, ce->arg(i)); } for (unsigned int i = ce->decl()->paramCount(); i--;) { VarDecl* vd = ce->decl()->param(i); if (vd->type().dim() > 0) { // Check array index sets auto* al = params[i]->cast<ArrayLit>(); for (unsigned int j = 0; j < vd->ti()->ranges().size(); j++) { TypeInst* range_ti = vd->ti()->ranges()[j]; if (range_ti->domain() && !range_ti->domain()->isa<TIId>()) { IntSetVal* isv = eval_intset(env, range_ti->domain()); if (isv->min() != al->min(j) || isv->max() != al->max(j)) { std::ostringstream oss; oss << "array index set " << (j + 1) << " of argument " << (i + 1) << " does not match declared index set"; throw EvalError(env, ce->loc(), oss.str()); } } } } previousParameters[i] = vd->e(); vd->flat(vd); vd->e(params[i]); if (vd->e()->type().isPar()) { if (Expression* dom = vd->ti()->domain()) { if (!dom->isa<TIId>()) { if (vd->e()->type().bt() == Type::BT_INT) { IntSetVal* isv = eval_intset(env, dom); if (vd->e()->type().dim() > 0) { ArrayLit* al = eval_array_lit(env, vd->e()); for (unsigned int i = 0; i < al->size(); i++) { check_dom(env, vd->id(), isv, (*al)[i]); } } else { check_dom(env, vd->id(), isv, vd->e()); } } else if (vd->e()->type().bt() == Type::BT_FLOAT) { GCLock lock; FloatSetVal* fsv = eval_floatset(env, dom); FloatVal dom_min = fsv->min(); FloatVal dom_max = fsv->max(); check_dom(env, vd->id(), dom_min, dom_max, vd->e()); } } } } } KeepAlive previousCapture; if (ce->decl()->capturedAnnotationsVar() != nullptr) { previousCapture = ce->decl()->capturedAnnotationsVar()->e(); GCLock lock; ce->decl()->capturedAnnotationsVar()->flat(ce->decl()->capturedAnnotationsVar()); ce->decl()->capturedAnnotationsVar()->e(env.createAnnotationArray(C_MIX)); } typename Eval::Val ret = Eval::e(env, ce->decl()->e()); Eval::checkRetVal(env, ret, ce->decl()); for (unsigned int i = ce->decl()->paramCount(); i--;) { VarDecl* vd = ce->decl()->param(i); vd->e(previousParameters[i]); vd->flat(vd->e() ? vd : nullptr); } if (ce->decl()->capturedAnnotationsVar() != nullptr) { ce->decl()->capturedAnnotationsVar()->e(previousCapture()); ce->decl()->capturedAnnotationsVar()->flat(ce->decl()->capturedAnnotationsVar()->e() != nullptr ? ce->decl()->capturedAnnotationsVar() : nullptr); } return ret;}
ArrayLit* eval_array_comp(EnvI& env, Comprehension* e) { ArrayLit* ret; if (e->type() == Type::parint(1)) { std::vector<Expression*> a = eval_comp<EvalIntLit>(env, e); ret = new ArrayLit(e->loc(), a); } else if (e->type() == Type::parbool(1)) { std::vector<Expression*> a = eval_comp<EvalBoolLit>(env, e); ret = new ArrayLit(e->loc(), a); } else if (e->type() == Type::parfloat(1)) { std::vector<Expression*> a = eval_comp<EvalFloatLit>(env, e); ret = new ArrayLit(e->loc(), a); } else if (e->type().st() == Type::ST_SET) { std::vector<Expression*> a = eval_comp<EvalSetLit>(env, e); ret = new ArrayLit(e->loc(), a); } else if (e->type() == Type::parstring(1)) { std::vector<Expression*> a = eval_comp<EvalStringLit>(env, e); ret = new ArrayLit(e->loc(), a); } else { std::vector<Expression*> a = eval_comp<EvalCopy>(env, e); ret = new ArrayLit(e->loc(), a); } ret->type(e->type()); return ret;}
ArrayLit* eval_array_lit(EnvI& env, Expression* e) { CallStackItem csi(env, e); switch (e->eid()) { case Expression::E_INTLIT: case Expression::E_FLOATLIT: case Expression::E_BOOLLIT: case Expression::E_STRINGLIT: case Expression::E_SETLIT: case Expression::E_ANON: case Expression::E_TI: case Expression::E_TIID: case Expression::E_VARDECL: throw EvalError(env, e->loc(), "not an array expression"); case Expression::E_ID: return eval_id<EvalArrayLit>(env, e); case Expression::E_ARRAYLIT: return e->cast<ArrayLit>(); case Expression::E_ARRAYACCESS: throw EvalError(env, e->loc(), "arrays of arrays not supported"); case Expression::E_COMP: return eval_array_comp(env, e->cast<Comprehension>()); case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_array_lit(env, ite->thenExpr(i)); } } return eval_array_lit(env, ite->elseExpr()); } case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if (bo->op() == BOT_PLUSPLUS) { ArrayLit* al0 = eval_array_lit(env, bo->lhs()); ArrayLit* al1 = eval_array_lit(env, bo->rhs()); std::vector<Expression*> v(al0->size() + al1->size()); for (unsigned int i = al0->size(); (i--) != 0U;) { v[i] = (*al0)[i]; } for (unsigned int i = al1->size(); (i--) != 0U;) { v[al0->size() + i] = (*al1)[i]; } auto* ret = new ArrayLit(e->loc(), v); ret->flat(al0->flat() && al1->flat()); ret->type(e->type()); return ret; } if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalArrayLitCopy, BinOp>(env, bo); } throw EvalError(env, e->loc(), "not an array expression", bo->opToString());
} break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalArrayLitCopy, UnOp>(env, uo); } throw EvalError(env, e->loc(), "not an array expression"); } case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.e != nullptr) { return eval_array_lit(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalArrayLitCopy>(env, ce); } case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } ArrayLit* l_in = eval_array_lit(env, l->in()); auto* ret = copy(env, l_in, true)->cast<ArrayLit>(); ret->flat(l_in->flat()); l->popbindings(); return ret; } } assert(false); return nullptr;}
Expression* eval_arrayaccess(EnvI& env, ArrayLit* al, const std::vector<IntVal>& idx, bool& success) { success = true; assert(al->dims() == idx.size()); IntVal realidx = 0; int realdim = 1; for (int i = 0; i < al->dims(); i++) { realdim *= al->max(i) - al->min(i) + 1; } for (int i = 0; i < al->dims(); i++) { IntVal ix = idx[i]; if (ix < al->min(i) || ix > al->max(i)) { success = false; Type t = al->type(); t.dim(0); if (t.isint()) { return IntLit::a(0); } if (t.isbool()) { return constants().literalFalse; } if (t.isfloat()) { return FloatLit::a(0.0); } if (t.st() == Type::ST_SET || t.isbot()) { auto* ret = new SetLit(Location(), std::vector<Expression*>()); ret->type(t); return ret; } if (t.isstring()) { return new StringLit(Location(), ""); } throw EvalError(env, al->loc(), "Internal error: unexpected type in array access expression"); } realdim /= al->max(i) - al->min(i) + 1; realidx += (ix - al->min(i)) * realdim; } assert(realidx >= 0 && realidx <= al->size()); return (*al)[static_cast<unsigned int>(realidx.toInt())];}Expression* eval_arrayaccess(EnvI& env, ArrayAccess* e, bool& success) { ArrayLit* al = eval_array_lit(env, e->v()); std::vector<IntVal> dims(e->idx().size()); for (unsigned int i = e->idx().size(); (i--) != 0U;) { dims[i] = eval_int(env, e->idx()[i]); } return eval_arrayaccess(env, al, dims, success);}Expression* eval_arrayaccess(EnvI& env, ArrayAccess* e) { bool success; Expression* ret = eval_arrayaccess(env, e, success); if (success) { return ret; } throw ResultUndefinedError(env, e->loc(), "array access out of bounds");}
SetLit* eval_set_lit(EnvI& env, Expression* e) { switch (e->type().bt()) { case Type::BT_INT: case Type::BT_BOT: return new SetLit(e->loc(), eval_intset(env, e)); case Type::BT_BOOL: { auto* sl = new SetLit(e->loc(), eval_boolset(env, e)); sl->type(Type::parsetbool()); return sl; } case Type::BT_FLOAT: return new SetLit(e->loc(), eval_floatset(env, e)); default: throw InternalError("invalid set literal type"); }}
IntSetVal* eval_intset(EnvI& env, Expression* e) { if (auto* sl = e->dynamicCast<SetLit>()) { if (sl->isv() != nullptr) { return sl->isv(); } } CallStackItem csi(env, e); switch (e->eid()) { case Expression::E_SETLIT: { auto* sl = e->cast<SetLit>(); std::vector<IntVal> vals; for (unsigned int i = 0; i < sl->v().size(); i++) { Expression* vi = eval_par(env, sl->v()[i]); if (vi != constants().absent) { vals.push_back(eval_int(env, vi)); } } return IntSetVal::a(vals); } case Expression::E_BOOLLIT: case Expression::E_INTLIT: case Expression::E_FLOATLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not a set of int expression"); break; case Expression::E_ARRAYLIT: { auto* al = e->cast<ArrayLit>(); std::vector<IntVal> vals(al->size()); for (unsigned int i = 0; i < al->size(); i++) { vals[i] = eval_int(env, (*al)[i]); } return IntSetVal::a(vals); } break; case Expression::E_COMP: { auto* c = e->cast<Comprehension>(); std::vector<IntVal> a = eval_comp<EvalIntVal>(env, c); return IntSetVal::a(a); } case Expression::E_ID: { GCLock lock; return eval_id<EvalSetLit>(env, e)->isv(); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_intset(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_intset(env, ite->thenExpr(i)); } } return eval_intset(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalIntSet, BinOp>(env, bo); } Expression* lhs = eval_par(env, bo->lhs()); Expression* rhs = eval_par(env, bo->rhs()); if (lhs->type().isIntSet() && rhs->type().isIntSet()) { IntSetVal* v0 = eval_intset(env, lhs); IntSetVal* v1 = eval_intset(env, rhs); IntSetRanges ir0(v0); IntSetRanges ir1(v1); switch (bo->op()) { case BOT_UNION: { Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } case BOT_DIFF: { Ranges::Diff<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } case BOT_SYMDIFF: { Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> i(ir0, ir1); Ranges::Diff<IntVal, Ranges::Union<IntVal, IntSetRanges, IntSetRanges>, Ranges::Inter<IntVal, IntSetRanges, IntSetRanges>> sd(u, i); return IntSetVal::ai(sd); } case BOT_INTERSECT: { Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } default: throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString()); } } else if (lhs->type().isint() && rhs->type().isint()) { if (bo->op() != BOT_DOTDOT) { throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString()); } return IntSetVal::a(eval_int(env, lhs), eval_int(env, rhs)); } else { throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalIntSet, UnOp>(env, uo); } throw EvalError(env, e->loc(), "not a set of int expression"); } case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.s != nullptr) { return ce->decl()->builtins.s(env, ce); }
if (ce->decl()->builtins.e != nullptr) { return eval_intset(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalIntSet>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } IntSetVal* ret = eval_intset(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return nullptr; }}
FloatSetVal* eval_floatset(EnvI& env, Expression* e) { if (auto* sl = e->dynamicCast<SetLit>()) { if (sl->fsv() != nullptr) { return sl->fsv(); } if (sl->isv() != nullptr) { IntSetRanges isr(sl->isv()); return FloatSetVal::ai(isr); } } CallStackItem csi(env, e); switch (e->eid()) { case Expression::E_SETLIT: { auto* sl = e->cast<SetLit>(); std::vector<FloatVal> vals; for (unsigned int i = 0; i < sl->v().size(); i++) { Expression* vi = eval_par(env, sl->v()[i]); if (vi != constants().absent) { vals.push_back(eval_float(env, vi)); } } return FloatSetVal::a(vals); } case Expression::E_BOOLLIT: case Expression::E_INTLIT: case Expression::E_FLOATLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not a set of float expression"); break; case Expression::E_ARRAYLIT: { auto* al = e->cast<ArrayLit>(); std::vector<FloatVal> vals(al->size()); for (unsigned int i = 0; i < al->size(); i++) { vals[i] = eval_float(env, (*al)[i]); } return FloatSetVal::a(vals); } break; case Expression::E_COMP: { auto* c = e->cast<Comprehension>(); std::vector<FloatVal> a = eval_comp<EvalFloatVal>(env, c); return FloatSetVal::a(a); } case Expression::E_ID: { GCLock lock; return eval_floatset(env, eval_id<EvalFloatSetLit>(env, e)); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_floatset(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_floatset(env, ite->thenExpr(i)); } } return eval_floatset(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalFloatSet, BinOp>(env, bo); } Expression* lhs = eval_par(env, bo->lhs()); Expression* rhs = eval_par(env, bo->rhs()); if (lhs->type().isFloatSet() && rhs->type().isFloatSet()) { FloatSetVal* v0 = eval_floatset(env, lhs); FloatSetVal* v1 = eval_floatset(env, rhs); FloatSetRanges fr0(v0); FloatSetRanges fr1(v1); switch (bo->op()) { case BOT_UNION: { Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1); return FloatSetVal::ai(u); } case BOT_DIFF: { Ranges::Diff<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1); return FloatSetVal::ai(u); } case BOT_SYMDIFF: { Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1); Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges> i(fr0, fr1); Ranges::Diff<FloatVal, Ranges::Union<FloatVal, FloatSetRanges, FloatSetRanges>, Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges>> sd(u, i); return FloatSetVal::ai(sd); } case BOT_INTERSECT: { Ranges::Inter<FloatVal, FloatSetRanges, FloatSetRanges> u(fr0, fr1); return FloatSetVal::ai(u); } default: throw EvalError(env, e->loc(), "not a set of int expression", bo->opToString()); } } else if (lhs->type().isfloat() && rhs->type().isfloat()) { if (bo->op() != BOT_DOTDOT) { throw EvalError(env, e->loc(), "not a set of float expression", bo->opToString()); } return FloatSetVal::a(eval_float(env, lhs), eval_float(env, rhs)); } else { throw EvalError(env, e->loc(), "not a set of float expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalFloatSet, UnOp>(env, uo); } throw EvalError(env, e->loc(), "not a set of float expression"); } case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.e != nullptr) { return eval_floatset(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalFloatSet>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } FloatSetVal* ret = eval_floatset(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return nullptr; }}
bool eval_bool(EnvI& env, Expression* e) { CallStackItem csi(env, e); try { if (auto* bl = e->dynamicCast<BoolLit>()) { return bl->v(); } switch (e->eid()) { case Expression::E_INTLIT: case Expression::E_FLOATLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_SETLIT: case Expression::E_ARRAYLIT: case Expression::E_COMP: case Expression::E_VARDECL: case Expression::E_TI: assert(false); throw EvalError(env, e->loc(), "not a bool expression"); break; case Expression::E_ID: { GCLock lock; return eval_id<EvalBoolLit>(env, e)->v(); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_bool(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_bool(env, ite->thenExpr(i)); } } return eval_bool(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); Expression* lhs = bo->lhs(); if (lhs->type().bt() == Type::BT_TOP) { lhs = eval_par(env, lhs); } Expression* rhs = bo->rhs(); if (rhs->type().bt() == Type::BT_TOP) { rhs = eval_par(env, rhs); } if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalBoolVal, BinOp>(env, bo); }
if (lhs->type().isbool() && rhs->type().isbool()) { try { switch (bo->op()) { case BOT_LE: return static_cast<int>(eval_bool(env, lhs)) < static_cast<int>(eval_bool(env, rhs)); case BOT_LQ: return static_cast<int>(eval_bool(env, lhs)) <= static_cast<int>(eval_bool(env, rhs)); case BOT_GR: return static_cast<int>(eval_bool(env, lhs)) > static_cast<int>(eval_bool(env, rhs)); case BOT_GQ: return static_cast<int>(eval_bool(env, lhs)) >= static_cast<int>(eval_bool(env, rhs)); case BOT_EQ: return eval_bool(env, lhs) == eval_bool(env, rhs); case BOT_NQ: return eval_bool(env, lhs) != eval_bool(env, rhs); case BOT_EQUIV: return eval_bool(env, lhs) == eval_bool(env, rhs); case BOT_IMPL: return (!eval_bool(env, lhs)) || eval_bool(env, rhs); case BOT_RIMPL: return (!eval_bool(env, rhs)) || eval_bool(env, lhs); case BOT_OR: return eval_bool(env, lhs) || eval_bool(env, rhs); case BOT_AND: return eval_bool(env, lhs) && eval_bool(env, rhs); case BOT_XOR: return eval_bool(env, lhs) ^ eval_bool(env, rhs); default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isint() && rhs->type().isint()) { try { IntVal v0 = eval_int(env, lhs); IntVal v1 = eval_int(env, rhs); switch (bo->op()) { case BOT_LE: return v0 < v1; case BOT_LQ: return v0 <= v1; case BOT_GR: return v0 > v1; case BOT_GQ: return v0 >= v1; case BOT_EQ: return v0 == v1; case BOT_NQ: return v0 != v1; default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isfloat() && rhs->type().isfloat()) { try { FloatVal v0 = eval_float(env, lhs); FloatVal v1 = eval_float(env, rhs); switch (bo->op()) { case BOT_LE: return v0 < v1; case BOT_LQ: return v0 <= v1; case BOT_GR: return v0 > v1; case BOT_GQ: return v0 >= v1; case BOT_EQ: return v0 == v1; case BOT_NQ: return v0 != v1; default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isint() && rhs->type().isIntSet()) { try { IntVal v0 = eval_int(env, lhs); GCLock lock; IntSetVal* v1 = eval_intset(env, rhs); switch (bo->op()) { case BOT_IN: return v1->contains(v0); default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isfloat() && rhs->type().isFloatSet()) { try { FloatVal v0 = eval_float(env, lhs); GCLock lock; FloatSetVal* v1 = eval_floatset(env, rhs); switch (bo->op()) { case BOT_IN: return v1->contains(v0); default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isSet() && rhs->type().isSet()) { try { GCLock lock; IntSetVal* v0 = eval_intset(env, lhs); IntSetVal* v1 = eval_intset(env, rhs); IntSetRanges ir0(v0); IntSetRanges ir1(v1); switch (bo->op()) { case BOT_LE: return Ranges::less(ir0, ir1); case BOT_LQ: return Ranges::less_eq(ir0, ir1); case BOT_GR: return Ranges::less(ir1, ir0); case BOT_GQ: return Ranges::less_eq(ir1, ir0); case BOT_EQ: return Ranges::equal(ir0, ir1); case BOT_NQ: return !Ranges::equal(ir0, ir1); case BOT_SUBSET: return Ranges::subset(ir0, ir1); case BOT_SUPERSET: return Ranges::subset(ir1, ir0); default: throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (lhs->type().isstring() && rhs->type().isstring()) { try { GCLock lock; std::string s0 = eval_string(env, lhs); std::string s1 = eval_string(env, rhs); switch (bo->op()) { case BOT_EQ: return s0 == s1; case BOT_NQ: return s0 != s1; case BOT_LE: return s0 < s1; case BOT_LQ: return s0 <= s1; case BOT_GR: return s0 > s1; case BOT_GQ: return s0 >= s1; default: throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } catch (ResultUndefinedError&) { return false; } } else if (bo->op() == BOT_EQ && lhs->type().isAnn()) { // follow ann id to value, since there might be indirection (e.g. func argument, see // test_equality_of_indirect_annotations.mzn) return Expression::equal(follow_id_to_value(lhs), follow_id_to_value(rhs)); } else if (bo->op() == BOT_EQ && lhs->type().dim() > 0 && rhs->type().dim() > 0) { try { ArrayLit* al0 = eval_array_lit(env, lhs); ArrayLit* al1 = eval_array_lit(env, rhs); if (al0->size() != al1->size()) { return false; } for (unsigned int i = 0; i < al0->size(); i++) { if (!Expression::equal(eval_par(env, (*al0)[i]), eval_par(env, (*al1)[i]))) { return false; } } return true; } catch (ResultUndefinedError&) { return false; } } else { throw EvalError(env, e->loc(), "not a bool expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalBoolVal, UnOp>(env, uo); } bool v0 = eval_bool(env, uo->e()); switch (uo->op()) { case UOT_NOT: return !v0; default: assert(false); throw EvalError(env, e->loc(), "not a bool expression", uo->opToString()); } } break; case Expression::E_CALL: { try { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.b != nullptr) { return ce->decl()->builtins.b(env, ce); }
if (ce->decl()->builtins.e != nullptr) { return eval_bool(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalBoolVal>(env, ce); } catch (ResultUndefinedError&) { return false; } } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); bool ret = true; for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); bool maybe_partial = vdi->ann().contains(constants().ann.maybe_partial); if (maybe_partial) { env.inMaybePartial++; } try { check_par_declaration(env, vdi); } catch (ResultUndefinedError&) { ret = false; } if (maybe_partial) { env.inMaybePartial--; } } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is false. if (!eval_bool(env, l->let()[i])) { if (l->let()[i]->ann().contains(constants().ann.maybe_partial)) { ret = false; } else { throw ResultUndefinedError(env, l->let()[i]->loc(), "domain constraint in let failed"); } } } } ret = ret && eval_bool(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return false; } } catch (ResultUndefinedError&) { // undefined means false return false; }}
IntSetVal* eval_boolset(EnvI& env, Expression* e) { CallStackItem csi(env, e); switch (e->eid()) { case Expression::E_SETLIT: { auto* sl = e->cast<SetLit>(); if (sl->isv() != nullptr) { return sl->isv(); } std::vector<IntVal> vals; for (unsigned int i = 0; i < sl->v().size(); i++) { Expression* vi = eval_par(env, sl->v()[i]); if (vi != constants().absent) { vals.push_back(eval_int(env, vi)); } } return IntSetVal::a(vals); } case Expression::E_BOOLLIT: case Expression::E_INTLIT: case Expression::E_FLOATLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not a set of bool expression"); break; case Expression::E_ARRAYLIT: { auto* al = e->cast<ArrayLit>(); std::vector<IntVal> vals(al->size()); for (unsigned int i = 0; i < al->size(); i++) { vals[i] = static_cast<long long>(eval_bool(env, (*al)[i])); } return IntSetVal::a(vals); } break; case Expression::E_COMP: { auto* c = e->cast<Comprehension>(); std::vector<IntVal> a = eval_comp<EvalIntVal>(env, c); return IntSetVal::a(a); } case Expression::E_ID: { GCLock lock; return eval_id<EvalBoolSetLit>(env, e)->isv(); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_boolset(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_boolset(env, ite->thenExpr(i)); } } return eval_boolset(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalBoolSet, BinOp>(env, bo); } Expression* lhs = eval_par(env, bo->lhs()); Expression* rhs = eval_par(env, bo->rhs()); if (lhs->type().isIntSet() && rhs->type().isIntSet()) { IntSetVal* v0 = eval_boolset(env, lhs); IntSetVal* v1 = eval_boolset(env, rhs); IntSetRanges ir0(v0); IntSetRanges ir1(v1); switch (bo->op()) { case BOT_UNION: { Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } case BOT_DIFF: { Ranges::Diff<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } case BOT_SYMDIFF: { Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> i(ir0, ir1); Ranges::Diff<IntVal, Ranges::Union<IntVal, IntSetRanges, IntSetRanges>, Ranges::Inter<IntVal, IntSetRanges, IntSetRanges>> sd(u, i); return IntSetVal::ai(sd); } case BOT_INTERSECT: { Ranges::Inter<IntVal, IntSetRanges, IntSetRanges> u(ir0, ir1); return IntSetVal::ai(u); } default: throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString()); } } else if (lhs->type().isbool() && rhs->type().isbool()) { if (bo->op() != BOT_DOTDOT) { throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString()); } return IntSetVal::a(static_cast<long long>(eval_bool(env, lhs)), static_cast<long long>(eval_bool(env, rhs))); } else { throw EvalError(env, e->loc(), "not a set of bool expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalBoolSet, UnOp>(env, uo); } throw EvalError(env, e->loc(), "not a set of bool expression"); } case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.s != nullptr) { return ce->decl()->builtins.s(env, ce); }
if (ce->decl()->builtins.e != nullptr) { return eval_boolset(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalBoolSet>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } IntSetVal* ret = eval_boolset(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return nullptr; }}
IntVal eval_int(EnvI& env, Expression* e) { if (e->type().isbool()) { return static_cast<long long>(eval_bool(env, e)); } if (auto* il = e->dynamicCast<IntLit>()) { return il->v(); } CallStackItem csi(env, e); try { switch (e->eid()) { case Expression::E_FLOATLIT: case Expression::E_BOOLLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_SETLIT: case Expression::E_ARRAYLIT: case Expression::E_COMP: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not an integer expression"); break; case Expression::E_ID: { GCLock lock; return eval_id<EvalIntLit>(env, e)->v(); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_int(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_int(env, ite->thenExpr(i)); } } return eval_int(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalIntVal, BinOp>(env, bo); } IntVal v0 = eval_int(env, bo->lhs()); IntVal v1 = eval_int(env, bo->rhs()); switch (bo->op()) { case BOT_PLUS: return v0 + v1; case BOT_MINUS: return v0 - v1; case BOT_MULT: return v0 * v1; case BOT_POW: return v0.pow(v1); case BOT_IDIV: if (v1 == 0) { throw ResultUndefinedError(env, e->loc(), "division by zero"); } return v0 / v1; case BOT_MOD: if (v1 == 0) { throw ResultUndefinedError(env, e->loc(), "division by zero"); } return v0 % v1; default: throw EvalError(env, e->loc(), "not an integer expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalIntVal, UnOp>(env, uo); } IntVal v0 = eval_int(env, uo->e()); switch (uo->op()) { case UOT_PLUS: return v0; case UOT_MINUS: return -v0; default: throw EvalError(env, e->loc(), "not an integer expression", uo->opToString()); } } break; case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); } if (ce->decl()->builtins.i != nullptr) { return ce->decl()->builtins.i(env, ce); }
if (ce->decl()->builtins.e != nullptr) { return eval_int(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalIntVal>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } IntVal ret = eval_int(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return 0; } } catch (ArithmeticError& err) { throw EvalError(env, e->loc(), err.msg()); }}
FloatVal eval_float(EnvI& env, Expression* e) { if (e->type().isint()) { return static_cast<double>(eval_int(env, e).toInt()); } if (e->type().isbool()) { return static_cast<double>(eval_bool(env, e)); } CallStackItem csi(env, e); try { if (auto* fl = e->dynamicCast<FloatLit>()) { return fl->v(); } switch (e->eid()) { case Expression::E_INTLIT: case Expression::E_BOOLLIT: case Expression::E_STRINGLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_SETLIT: case Expression::E_ARRAYLIT: case Expression::E_COMP: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not a float expression"); break; case Expression::E_ID: { GCLock lock; return eval_id<EvalFloatLit>(env, e)->v(); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_float(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_float(env, ite->thenExpr(i)); } } return eval_float(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalFloatVal, BinOp>(env, bo); } FloatVal v0 = eval_float(env, bo->lhs()); FloatVal v1 = eval_float(env, bo->rhs()); switch (bo->op()) { case BOT_PLUS: return v0 + v1; case BOT_MINUS: return v0 - v1; case BOT_MULT: return v0 * v1; case BOT_POW: return std::pow(v0.toDouble(), v1.toDouble()); case BOT_DIV: if (v1 == 0.0) { throw ResultUndefinedError(env, e->loc(), "division by zero"); } return v0 / v1; default: throw EvalError(env, e->loc(), "not a float expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalFloatVal, UnOp>(env, uo); } FloatVal v0 = eval_float(env, uo->e()); switch (uo->op()) { case UOT_PLUS: return v0; case UOT_MINUS: return -v0; default: throw EvalError(env, e->loc(), "not a float expression", uo->opToString()); } } break; case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); } if (ce->decl()->builtins.f != nullptr) { return ce->decl()->builtins.f(env, ce); }
if (ce->decl()->builtins.e != nullptr) { return eval_float(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalFloatVal>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } FloatVal ret = eval_float(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return 0.0; } } catch (ArithmeticError& err) { throw EvalError(env, e->loc(), err.msg()); }}
std::string eval_string(EnvI& env, Expression* e) { CallStackItem csi(env, e); switch (e->eid()) { case Expression::E_STRINGLIT: { ASTString str = e->cast<StringLit>()->v(); return std::string(str.c_str(), str.size()); } case Expression::E_FLOATLIT: case Expression::E_INTLIT: case Expression::E_BOOLLIT: case Expression::E_ANON: case Expression::E_TIID: case Expression::E_SETLIT: case Expression::E_ARRAYLIT: case Expression::E_COMP: case Expression::E_VARDECL: case Expression::E_TI: throw EvalError(env, e->loc(), "not a string expression"); break; case Expression::E_ID: { GCLock lock; ASTString str = eval_id<EvalStringLit>(env, e)->v(); return std::string(str.c_str(), str.size()); } break; case Expression::E_ARRAYACCESS: { GCLock lock; return eval_string(env, eval_arrayaccess(env, e->cast<ArrayAccess>())); } break; case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (eval_bool(env, ite->ifExpr(i))) { return eval_string(env, ite->thenExpr(i)); } } return eval_string(env, ite->elseExpr()); } break; case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalString, BinOp>(env, bo); } std::string v0 = eval_string(env, bo->lhs()); std::string v1 = eval_string(env, bo->rhs()); switch (bo->op()) { case BOT_PLUSPLUS: return v0 + v1; default: throw EvalError(env, e->loc(), "not a string expression", bo->opToString()); } } break; case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalString, UnOp>(env, uo); } throw EvalError(env, e->loc(), "not a string expression"); } break; case Expression::E_CALL: { Call* ce = e->cast<Call>(); if (ce->decl() == nullptr) { throw EvalError(env, e->loc(), "undeclared function", ce->id()); }
if (ce->decl()->builtins.str != nullptr) { return ce->decl()->builtins.str(env, ce); } if (ce->decl()->builtins.e != nullptr) { return eval_string(env, ce->decl()->builtins.e(env, ce)); }
if (ce->decl()->e() == nullptr) { std::ostringstream ss; ss << "internal error: missing builtin '" << ce->id() << "'"; throw EvalError(env, ce->loc(), ss.str()); }
return eval_call<EvalString>(env, ce); } break; case Expression::E_LET: { Let* l = e->cast<Let>(); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } std::string ret = eval_string(env, l->in()); l->popbindings(); return ret; } break; default: assert(false); return ""; }}
Expression* eval_par(EnvI& env, Expression* e) { if (e == nullptr) { return nullptr; } switch (e->eid()) { case Expression::E_ANON: case Expression::E_TIID: { return e; } case Expression::E_COMP: if (e->cast<Comprehension>()->set()) { return EvalSetLit::e(env, e); } // fall through case Expression::E_ARRAYLIT: { ArrayLit* al = eval_array_lit(env, e); std::vector<Expression*> args(al->size()); bool allFlat = true; for (unsigned int i = 0; i < al->size(); i++) { Expression* ali = (*al)[i]; if (!ali->isa<IntLit>() && !ali->isa<FloatLit>() && !ali->isa<BoolLit>() && !(ali->isa<SetLit>() && ali->cast<SetLit>()->evaluated())) { allFlat = false; args[i] = eval_par(env, ali); } else { args[i] = ali; } } if (allFlat) { return al; } std::vector<std::pair<int, int>> dims(al->dims()); for (unsigned int i = al->dims(); (i--) != 0U;) { dims[i].first = al->min(i); dims[i].second = al->max(i); } auto* ret = new ArrayLit(al->loc(), args, dims); Type t = al->type(); if (t.isbot() && ret->size() > 0) { t.bt((*ret)[0]->type().bt()); } ret->type(t); return ret; } case Expression::E_VARDECL: { auto* vd = e->cast<VarDecl>(); throw EvalError(env, vd->loc(), "cannot evaluate variable declaration", vd->id()->v()); } case Expression::E_TI: { auto* t = e->cast<TypeInst>(); ASTExprVec<TypeInst> r; if (t->ranges().size() > 0) { std::vector<TypeInst*> rv(t->ranges().size()); for (unsigned int i = t->ranges().size(); (i--) != 0U;) { rv[i] = static_cast<TypeInst*>(eval_par(env, t->ranges()[i])); } r = ASTExprVec<TypeInst>(rv); } return new TypeInst(Location(), t->type(), r, eval_par(env, t->domain())); } case Expression::E_ID: { if (e == constants().absent) { return e; } Id* id = e->cast<Id>(); if (id->decl() == nullptr) { throw EvalError(env, e->loc(), "undefined identifier", id->v()); } if (id->decl()->ti()->domain() != nullptr) { if (auto* bl = id->decl()->ti()->domain()->dynamicCast<BoolLit>()) { return bl; } if (id->decl()->ti()->type().isint()) { if (auto* sl = id->decl()->ti()->domain()->dynamicCast<SetLit>()) { if ((sl->isv() != nullptr) && sl->isv()->min() == sl->isv()->max()) { return IntLit::a(sl->isv()->min()); } } } else if (id->decl()->ti()->type().isfloat()) { if (id->decl()->ti()->domain() != nullptr) { FloatSetVal* fsv = eval_floatset(env, id->decl()->ti()->domain()); if (fsv->min() == fsv->max()) { return FloatLit::a(fsv->min()); } } } } if (id->decl()->e() == nullptr) { return id; } return eval_par(env, id->decl()->e()); } case Expression::E_STRINGLIT: return e; default: { if (e->type().dim() != 0) { ArrayLit* al = eval_array_lit(env, e); std::vector<Expression*> args(al->size()); for (unsigned int i = al->size(); (i--) != 0U;) { args[i] = eval_par(env, (*al)[i]); } std::vector<std::pair<int, int>> dims(al->dims()); for (unsigned int i = al->dims(); (i--) != 0U;) { dims[i].first = al->min(i); dims[i].second = al->max(i); } auto* ret = new ArrayLit(al->loc(), args, dims); Type t = al->type(); if ((t.bt() == Type::BT_BOT || t.bt() == Type::BT_TOP) && ret->size() > 0) { t.bt((*ret)[0]->type().bt()); } ret->type(t); return ret; } if (e->type().isPar()) { if (e->type().isSet()) { return EvalSetLit::e(env, e); } if (e->type() == Type::parint()) { return EvalIntLit::e(env, e); } if (e->type() == Type::parbool()) { return EvalBoolLit::e(env, e); } if (e->type() == Type::parfloat()) { return EvalFloatLit::e(env, e); } if (e->type() == Type::parstring()) { return EvalStringLit::e(env, e); } } switch (e->eid()) { case Expression::E_ITE: { ITE* ite = e->cast<ITE>(); for (int i = 0; i < ite->size(); i++) { if (ite->ifExpr(i)->type() == Type::parbool()) { if (eval_bool(env, ite->ifExpr(i))) { return eval_par(env, ite->thenExpr(i)); } } else { std::vector<Expression*> e_ifthen(ite->size() * 2); for (int i = 0; i < ite->size(); i++) { e_ifthen[2 * i] = eval_par(env, ite->ifExpr(i)); e_ifthen[2 * i + 1] = eval_par(env, ite->thenExpr(i)); } ITE* n_ite = new ITE(ite->loc(), e_ifthen, eval_par(env, ite->elseExpr())); n_ite->type(ite->type()); return n_ite; } } return eval_par(env, ite->elseExpr()); } case Expression::E_CALL: { Call* c = e->cast<Call>(); if (c->decl() != nullptr) { if (c->decl()->builtins.e != nullptr) { return eval_par(env, c->decl()->builtins.e(env, c)); } if (c->decl()->e() == nullptr) { if (c->id() == "deopt" && Expression::equal(c->arg(0), constants().absent)) { throw ResultUndefinedError(env, e->loc(), "deopt(<>) is undefined"); } return c; } return eval_call<EvalPar>(env, c); } std::vector<Expression*> args(c->argCount()); for (unsigned int i = 0; i < args.size(); i++) { args[i] = eval_par(env, c->arg(i)); } Call* nc = new Call(c->loc(), c->id(), args); nc->type(c->type()); return nc; } case Expression::E_BINOP: { auto* bo = e->cast<BinOp>(); if ((bo->decl() != nullptr) && (bo->decl()->e() != nullptr)) { return eval_call<EvalPar, BinOp>(env, bo); } auto* nbo = new BinOp(e->loc(), eval_par(env, bo->lhs()), bo->op(), eval_par(env, bo->rhs())); nbo->type(bo->type()); return nbo; } case Expression::E_UNOP: { UnOp* uo = e->cast<UnOp>(); if ((uo->decl() != nullptr) && (uo->decl()->e() != nullptr)) { return eval_call<EvalPar, UnOp>(env, uo); } UnOp* nuo = new UnOp(e->loc(), uo->op(), eval_par(env, uo->e())); nuo->type(uo->type()); return nuo; } case Expression::E_ARRAYACCESS: { auto* aa = e->cast<ArrayAccess>(); for (unsigned int i = 0; i < aa->idx().size(); i++) { if (!aa->idx()[i]->type().isPar()) { std::vector<Expression*> idx(aa->idx().size()); for (unsigned int j = 0; j < aa->idx().size(); j++) { idx[j] = eval_par(env, aa->idx()[j]); } auto* aa_new = new ArrayAccess(e->loc(), eval_par(env, aa->v()), idx); aa_new->type(aa->type()); return aa_new; } } return eval_par(env, eval_arrayaccess(env, aa)); } case Expression::E_LET: { Let* l = e->cast<Let>(); assert(l->type().isPar()); l->pushbindings(); for (unsigned int i = 0; i < l->let().size(); i++) { // Evaluate all variable declarations if (auto* vdi = l->let()[i]->dynamicCast<VarDecl>()) { vdi->e(eval_par(env, vdi->e())); check_par_declaration(env, vdi); } else { // This is a constraint item. Since the let is par, // it can only be a par bool expression. If it evaluates // to false, it means that the value of this let is undefined. if (!eval_bool(env, l->let()[i])) { throw ResultUndefinedError(env, l->let()[i]->loc(), "constraint in let failed"); } } } Expression* ret = eval_par(env, l->in()); l->popbindings(); return ret; } default: return e; } } }}
class ComputeIntBounds : public EVisitor {public: typedef std::pair<IntVal, IntVal> Bounds; std::vector<Bounds> bounds; bool valid; EnvI& env; ComputeIntBounds(EnvI& env0) : valid(true), env(env0) {} bool enter(Expression* e) { if (e->type().isAnn()) { return false; } if (e->isa<VarDecl>()) { return false; } if (e->type().dim() > 0) { return false; } if (e->type().isPar()) { if (e->type().isint()) { Expression* exp = eval_par(env, e); if (exp == constants().absent) { valid = false; } else { IntVal v = exp->cast<IntLit>()->v(); bounds.emplace_back(v, v); } } else { valid = false; } return false; } if (e->type().isint()) { if (ITE* ite = e->dynamicCast<ITE>()) { Bounds itebounds(IntVal::infinity(), -IntVal::infinity()); for (int i = 0; i < ite->size(); i++) { if (ite->ifExpr(i)->type().isPar() && static_cast<int>(ite->ifExpr(i)->type().cv()) == Type::CV_NO) { if (eval_bool(env, ite->ifExpr(i))) { BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run(ite->thenExpr(i)); Bounds& back = bounds.back(); back.first = std::min(itebounds.first, back.first); back.second = std::max(itebounds.second, back.second); return false; } } else { BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run(ite->thenExpr(i)); Bounds back = bounds.back(); bounds.pop_back(); itebounds.first = std::min(itebounds.first, back.first); itebounds.second = std::max(itebounds.second, back.second); } } BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run(ite->elseExpr()); Bounds& back = bounds.back(); back.first = std::min(itebounds.first, back.first); back.second = std::max(itebounds.second, back.second); return false; } return true; } return false; } /// Visit integer literal void vIntLit(const IntLit& i) { bounds.emplace_back(i.v(), i.v()); } /// Visit floating point literal void vFloatLit(const FloatLit& /*f*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit Boolean literal void vBoolLit(const BoolLit& /*b*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit set literal void vSetLit(const SetLit& /*sl*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit string literal void vStringLit(const StringLit& /*sl*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit identifier void vId(const Id& id) { VarDecl* vd = id.decl(); while ((vd->flat() != nullptr) && vd->flat() != vd) { vd = vd->flat(); } if (vd->ti()->domain() != nullptr) { GCLock lock; IntSetVal* isv = eval_intset(env, vd->ti()->domain()); if (isv->size() == 0) { valid = false; bounds.emplace_back(0, 0); } else { bounds.emplace_back(isv->min(0), isv->max(isv->size() - 1)); } } else { if (vd->e() != nullptr) { BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run(vd->e()); } else { bounds.emplace_back(-IntVal::infinity(), IntVal::infinity()); } } } /// Visit anonymous variable void vAnonVar(const AnonVar& /*v*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit array literal void vArrayLit(const ArrayLit& /*al*/) {} /// Visit array access void vArrayAccess(ArrayAccess& aa) { bool parAccess = true; for (unsigned int i = aa.idx().size(); (i--) != 0U;) { bounds.pop_back(); if (!aa.idx()[i]->type().isPar()) { parAccess = false; } } if (Id* id = aa.v()->dynamicCast<Id>()) { while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) { id = id->decl()->e()->cast<Id>(); } if (parAccess && (id->decl()->e() != nullptr)) { bool success; Expression* e = eval_arrayaccess(env, &aa, success); if (success) { BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run(e); return; } } if (id->decl()->ti()->domain() != nullptr) { GCLock lock; IntSetVal* isv = eval_intset(env, id->decl()->ti()->domain()); if (isv->size() > 0) { bounds.emplace_back(isv->min(0), isv->max(isv->size() - 1)); return; } } } valid = false; bounds.emplace_back(0, 0); } /// Visit array comprehension void vComprehension(const Comprehension& c) { valid = false; bounds.emplace_back(0, 0); } /// Visit if-then-else void vITE(const ITE& /*ite*/) { valid = false; bounds.emplace_back(0, 0); } /// Visit binary operator void vBinOp(const BinOp& bo) { Bounds b1 = bounds.back(); bounds.pop_back(); Bounds b0 = bounds.back(); bounds.pop_back(); if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() || !b0.second.isFinite()) { valid = false; bounds.emplace_back(0, 0); } else { switch (bo.op()) { case BOT_PLUS: bounds.emplace_back(b0.first + b1.first, b0.second + b1.second); break; case BOT_MINUS: bounds.emplace_back(b0.first - b1.second, b0.second - b1.first); break; case BOT_MULT: { IntVal x0 = b0.first * b1.first; IntVal x1 = b0.first * b1.second; IntVal x2 = b0.second * b1.first; IntVal x3 = b0.second * b1.second; IntVal m = std::min(x0, std::min(x1, std::min(x2, x3))); IntVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_IDIV: { IntVal b0f = b0.first == 0 ? 1 : b0.first; IntVal b0s = b0.second == 0 ? -1 : b0.second; IntVal b1f = b1.first == 0 ? 1 : b1.first; IntVal b1s = b1.second == 0 ? -1 : b1.second; IntVal x0 = b0f / b1f; IntVal x1 = b0f / b1s; IntVal x2 = b0s / b1f; IntVal x3 = b0s / b1s; IntVal m = std::min(x0, std::min(x1, std::min(x2, x3))); IntVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_MOD: { IntVal b0f = b0.first == 0 ? 1 : b0.first; IntVal b0s = b0.second == 0 ? -1 : b0.second; IntVal b1f = b1.first == 0 ? 1 : b1.first; IntVal b1s = b1.second == 0 ? -1 : b1.second; IntVal x0 = b0f % b1f; IntVal x1 = b0f % b1s; IntVal x2 = b0s % b1f; IntVal x3 = b0s % b1s; IntVal m = std::min(x0, std::min(x1, std::min(x2, x3))); IntVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_POW: { IntVal exp_min = std::min(0, b1.first); IntVal exp_max = std::min(0, b1.second);
IntVal x0 = b0.first.pow(exp_min); IntVal x1 = b0.first.pow(exp_max); IntVal x2 = b0.second.pow(exp_min); IntVal x3 = b0.second.pow(exp_max); IntVal m = std::min(x0, std::min(x1, std::min(x2, x3))); IntVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_DIV: case BOT_LE: case BOT_LQ: case BOT_GR: case BOT_GQ: case BOT_EQ: case BOT_NQ: case BOT_IN: case BOT_SUBSET: case BOT_SUPERSET: case BOT_UNION: case BOT_DIFF: case BOT_SYMDIFF: case BOT_INTERSECT: case BOT_PLUSPLUS: case BOT_EQUIV: case BOT_IMPL: case BOT_RIMPL: case BOT_OR: case BOT_AND: case BOT_XOR: case BOT_DOTDOT: valid = false; bounds.emplace_back(0, 0); } } } /// Visit unary operator void vUnOp(const UnOp& uo) { switch (uo.op()) { case UOT_PLUS: break; case UOT_MINUS: bounds.back().first = -bounds.back().first; bounds.back().second = -bounds.back().second; std::swap(bounds.back().first, bounds.back().second); break; case UOT_NOT: valid = false; } } /// Visit call void vCall(Call& c) { if (c.id() == constants().ids.lin_exp || c.id() == constants().ids.sum) { bool le = c.id() == constants().ids.lin_exp; ArrayLit* coeff = le ? eval_array_lit(env, c.arg(0)) : nullptr; if (c.arg(le ? 1 : 0)->type().isOpt()) { valid = false; bounds.emplace_back(0, 0); return; } ArrayLit* al = eval_array_lit(env, c.arg(le ? 1 : 0)); if (le) { bounds.pop_back(); // remove constant (third arg) from stack }
IntVal d = le ? c.arg(2)->cast<IntLit>()->v() : 0; int stacktop = static_cast<int>(bounds.size()); for (unsigned int i = al->size(); (i--) != 0U;) { BottomUpIterator<ComputeIntBounds> cbi(*this); cbi.run((*al)[i]); if (!valid) { for (unsigned int j = al->size() - 1; j > i; j--) { bounds.pop_back(); } return; } } assert(stacktop + al->size() == bounds.size()); IntVal lb = d; IntVal ub = d; for (unsigned int i = 0; i < al->size(); i++) { Bounds b = bounds.back(); bounds.pop_back(); IntVal cv = le ? eval_int(env, (*coeff)[i]) : 1; if (cv > 0) { if (b.first.isFinite()) { if (lb.isFinite()) { lb += cv * b.first; } } else { lb = b.first; } if (b.second.isFinite()) { if (ub.isFinite()) { ub += cv * b.second; } } else { ub = b.second; } } else { if (b.second.isFinite()) { if (lb.isFinite()) { lb += cv * b.second; } } else { lb = -b.second; } if (b.first.isFinite()) { if (ub.isFinite()) { ub += cv * b.first; } } else { ub = -b.first; } } } bounds.emplace_back(lb, ub); } else if (c.id() == "card") { if (IntSetVal* isv = compute_intset_bounds(env, c.arg(0))) { IntSetRanges isr(isv); bounds.emplace_back(0, Ranges::cardinality(isr)); } else { valid = false; bounds.emplace_back(0, 0); } } else if (c.id() == "int_times") { Bounds b1 = bounds.back(); bounds.pop_back(); Bounds b0 = bounds.back(); bounds.pop_back(); if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() || !b0.second.isFinite()) { valid = false; bounds.emplace_back(0, 0); } else { IntVal x0 = b0.first * b1.first; IntVal x1 = b0.first * b1.second; IntVal x2 = b0.second * b1.first; IntVal x3 = b0.second * b1.second; IntVal m = std::min(x0, std::min(x1, std::min(x2, x3))); IntVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } } else if (c.id() == constants().ids.bool2int) { bounds.emplace_back(0, 1); } else if (c.id() == "abs") { Bounds b0 = bounds.back(); if (b0.first < 0) { bounds.pop_back(); if (b0.second < 0) { bounds.emplace_back(-b0.second, -b0.first); } else { bounds.emplace_back(0, std::max(-b0.first, b0.second)); } } } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) && !c.decl()->ti()->domain()->isa<TIId>()) { for (int i = 0; i < c.argCount(); i++) { if (c.arg(i)->type().isint()) { assert(!bounds.empty()); bounds.pop_back(); } } IntSetVal* isv = eval_intset(env, c.decl()->ti()->domain()); bounds.emplace_back(isv->min(), isv->max()); } else { valid = false; bounds.emplace_back(0, 0); } } /// Visit let void vLet(const Let& l) { valid = false; bounds.emplace_back(0, 0); } /// Visit variable declaration void vVarDecl(const VarDecl& vd) { valid = false; bounds.emplace_back(0, 0); } /// Visit annotation void vAnnotation(const Annotation& e) { valid = false; bounds.emplace_back(0, 0); } /// Visit type inst void vTypeInst(const TypeInst& e) { valid = false; bounds.emplace_back(0, 0); } /// Visit TIId void vTIId(const TIId& e) { valid = false; bounds.emplace_back(0, 0); }};
IntBounds compute_int_bounds(EnvI& env, Expression* e) { try { ComputeIntBounds cb(env); BottomUpIterator<ComputeIntBounds> cbi(cb); cbi.run(e); if (cb.valid) { assert(cb.bounds.size() == 1); return IntBounds(cb.bounds.back().first, cb.bounds.back().second, true); } return IntBounds(0, 0, false);
} catch (ResultUndefinedError&) { return IntBounds(0, 0, false); }}
class ComputeFloatBounds : public EVisitor {protected: typedef std::pair<FloatVal, FloatVal> FBounds;
public: std::vector<FBounds> bounds; bool valid; EnvI& env; ComputeFloatBounds(EnvI& env0) : valid(true), env(env0) {} bool enter(Expression* e) { if (e->type().isAnn()) { return false; } if (e->isa<VarDecl>()) { return false; } if (e->type().dim() > 0) { return false; } if (e->type().isPar()) { if (e->type().isfloat()) { Expression* exp = eval_par(env, e); if (exp == constants().absent) { valid = false; } else { FloatVal v = exp->cast<FloatLit>()->v(); bounds.emplace_back(v, v); } } return false; } if (e->type().isfloat()) { if (ITE* ite = e->dynamicCast<ITE>()) { FBounds itebounds(FloatVal::infinity(), -FloatVal::infinity()); for (int i = 0; i < ite->size(); i++) { if (ite->ifExpr(i)->type().isPar() && static_cast<int>(ite->ifExpr(i)->type().cv()) == Type::CV_NO) { if (eval_bool(env, ite->ifExpr(i))) { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(ite->thenExpr(i)); FBounds& back = bounds.back(); back.first = std::min(itebounds.first, back.first); back.second = std::max(itebounds.second, back.second); return false; } } else { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(ite->thenExpr(i)); FBounds back = bounds.back(); bounds.pop_back(); itebounds.first = std::min(itebounds.first, back.first); itebounds.second = std::max(itebounds.second, back.second); } } BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(ite->elseExpr()); FBounds& back = bounds.back(); back.first = std::min(itebounds.first, back.first); back.second = std::max(itebounds.second, back.second); return false; } return true; } return false; } /// Visit integer literal void vIntLit(const IntLit& i) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit floating point literal void vFloatLit(const FloatLit& f) { bounds.emplace_back(f.v(), f.v()); } /// Visit Boolean literal void vBoolLit(const BoolLit& /*b*/) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit set literal void vSetLit(const SetLit& /*sl*/) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit string literal void vStringLit(const StringLit& /*sl*/) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit identifier void vId(const Id& id) { VarDecl* vd = id.decl(); while ((vd->flat() != nullptr) && vd->flat() != vd) { vd = vd->flat(); } if (vd->ti()->domain() != nullptr) { GCLock lock; FloatSetVal* fsv = eval_floatset(env, vd->ti()->domain()); if (fsv->size() == 0) { valid = false; bounds.emplace_back(0, 0); } else { bounds.emplace_back(fsv->min(0), fsv->max(fsv->size() - 1)); } } else { if (vd->e() != nullptr) { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(vd->e()); } else { bounds.emplace_back(-FloatVal::infinity(), FloatVal::infinity()); } } } /// Visit anonymous variable void vAnonVar(const AnonVar& v) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit array literal void vArrayLit(const ArrayLit& al) {} /// Visit array access void vArrayAccess(ArrayAccess& aa) { bool parAccess = true; for (unsigned int i = aa.idx().size(); (i--) != 0U;) { if (!aa.idx()[i]->type().isPar()) { parAccess = false; } } if (Id* id = aa.v()->dynamicCast<Id>()) { while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) { id = id->decl()->e()->cast<Id>(); } if (parAccess && (id->decl()->e() != nullptr)) { bool success; Expression* e = eval_arrayaccess(env, &aa, success); if (success) { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(e); return; } } if (id->decl()->ti()->domain() != nullptr) { FloatSetVal* fsv = eval_floatset(env, id->decl()->ti()->domain()); FBounds b(fsv->min(), fsv->max()); bounds.push_back(b); return; } } valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit array comprehension void vComprehension(const Comprehension& c) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit if-then-else void vITE(const ITE& ite) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit binary operator void vBinOp(const BinOp& bo) { FBounds b1 = bounds.back(); bounds.pop_back(); FBounds b0 = bounds.back(); bounds.pop_back(); if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() || !b0.second.isFinite()) { valid = false; bounds.emplace_back(0.0, 0.0); } else { switch (bo.op()) { case BOT_PLUS: bounds.emplace_back(b0.first + b1.first, b0.second + b1.second); break; case BOT_MINUS: bounds.emplace_back(b0.first - b1.second, b0.second - b1.first); break; case BOT_MULT: { FloatVal x0 = b0.first * b1.first; FloatVal x1 = b0.first * b1.second; FloatVal x2 = b0.second * b1.first; FloatVal x3 = b0.second * b1.second; FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3))); FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_POW: { FloatVal x0 = std::pow(b0.first.toDouble(), b1.first.toDouble()); FloatVal x1 = std::pow(b0.first.toDouble(), b1.second.toDouble()); FloatVal x2 = std::pow(b0.second.toDouble(), b1.first.toDouble()); FloatVal x3 = std::pow(b0.second.toDouble(), b1.second.toDouble()); FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3))); FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } break; case BOT_DIV: case BOT_IDIV: case BOT_MOD: case BOT_LE: case BOT_LQ: case BOT_GR: case BOT_GQ: case BOT_EQ: case BOT_NQ: case BOT_IN: case BOT_SUBSET: case BOT_SUPERSET: case BOT_UNION: case BOT_DIFF: case BOT_SYMDIFF: case BOT_INTERSECT: case BOT_PLUSPLUS: case BOT_EQUIV: case BOT_IMPL: case BOT_RIMPL: case BOT_OR: case BOT_AND: case BOT_XOR: case BOT_DOTDOT: valid = false; bounds.emplace_back(0.0, 0.0); } } } /// Visit unary operator void vUnOp(const UnOp& uo) { switch (uo.op()) { case UOT_PLUS: break; case UOT_MINUS: bounds.back().first = -bounds.back().first; bounds.back().second = -bounds.back().second; break; case UOT_NOT: valid = false; bounds.emplace_back(0.0, 0.0); } } /// Visit call void vCall(Call& c) { if (c.id() == constants().ids.lin_exp || c.id() == constants().ids.sum) { bool le = c.id() == constants().ids.lin_exp; ArrayLit* coeff = le ? eval_array_lit(env, c.arg(0)) : nullptr; if (le) { bounds.pop_back(); // remove constant (third arg) from stack } if (c.arg(le ? 1 : 0)->type().isOpt()) { valid = false; bounds.emplace_back(0.0, 0.0); return; } ArrayLit* al = eval_array_lit(env, c.arg(le ? 1 : 0)); FloatVal d = le ? c.arg(2)->cast<FloatLit>()->v() : 0.0; int stacktop = static_cast<int>(bounds.size()); for (unsigned int i = al->size(); (i--) != 0U;) { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run((*al)[i]); if (!valid) { return; } } assert(stacktop + al->size() == bounds.size()); FloatVal lb = d; FloatVal ub = d; for (unsigned int i = 0; i < (*al).size(); i++) { FBounds b = bounds.back(); bounds.pop_back(); FloatVal cv = le ? eval_float(env, (*coeff)[i]) : 1.0;
if (cv > 0) { if (b.first.isFinite()) { if (lb.isFinite()) { lb += cv * b.first; } } else { lb = b.first; } if (b.second.isFinite()) { if (ub.isFinite()) { ub += cv * b.second; } } else { ub = b.second; } } else { if (b.second.isFinite()) { if (lb.isFinite()) { lb += cv * b.second; } } else { lb = -b.second; } if (b.first.isFinite()) { if (ub.isFinite()) { ub += cv * b.first; } } else { ub = -b.first; } } } bounds.emplace_back(lb, ub); } else if (c.id() == "float_times") { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(c.arg(0)); cbi.run(c.arg(1)); FBounds b1 = bounds.back(); bounds.pop_back(); FBounds b0 = bounds.back(); bounds.pop_back(); if (!b1.first.isFinite() || !b1.second.isFinite() || !b0.first.isFinite() || !b0.second.isFinite()) { valid = false; bounds.emplace_back(0, 0); } else { FloatVal x0 = b0.first * b1.first; FloatVal x1 = b0.first * b1.second; FloatVal x2 = b0.second * b1.first; FloatVal x3 = b0.second * b1.second; FloatVal m = std::min(x0, std::min(x1, std::min(x2, x3))); FloatVal n = std::max(x0, std::max(x1, std::max(x2, x3))); bounds.emplace_back(m, n); } } else if (c.id() == "int2float") { ComputeIntBounds ib(env); BottomUpIterator<ComputeIntBounds> cbi(ib); cbi.run(c.arg(0)); if (!ib.valid) { valid = false; } ComputeIntBounds::Bounds result = ib.bounds.back(); if (!result.first.isFinite() || !result.second.isFinite()) { valid = false; bounds.emplace_back(0.0, 0.0); } else { bounds.emplace_back(static_cast<double>(result.first.toInt()), static_cast<double>(result.second.toInt())); } } else if (c.id() == "abs") { BottomUpIterator<ComputeFloatBounds> cbi(*this); cbi.run(c.arg(0)); FBounds b0 = bounds.back(); if (b0.first < 0) { bounds.pop_back(); if (b0.second < 0) { bounds.emplace_back(-b0.second, -b0.first); } else { bounds.emplace_back(0.0, std::max(-b0.first, b0.second)); } } } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) && !c.decl()->ti()->domain()->isa<TIId>()) { for (int i = 0; i < c.argCount(); i++) { if (c.arg(i)->type().isfloat()) { assert(!bounds.empty()); bounds.pop_back(); } } FloatSetVal* fsv = eval_floatset(env, c.decl()->ti()->domain()); bounds.emplace_back(fsv->min(), fsv->max()); } else { valid = false; bounds.emplace_back(0.0, 0.0); } } /// Visit let void vLet(const Let& l) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit variable declaration void vVarDecl(const VarDecl& vd) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit annotation void vAnnotation(const Annotation& e) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit type inst void vTypeInst(const TypeInst& e) { valid = false; bounds.emplace_back(0.0, 0.0); } /// Visit TIId void vTIId(const TIId& e) { valid = false; bounds.emplace_back(0.0, 0.0); }};
FloatBounds compute_float_bounds(EnvI& env, Expression* e) { try { ComputeFloatBounds cb(env); BottomUpIterator<ComputeFloatBounds> cbi(cb); cbi.run(e); if (cb.valid) { assert(!cb.bounds.empty()); return FloatBounds(cb.bounds.back().first, cb.bounds.back().second, true); } return FloatBounds(0.0, 0.0, false);
} catch (ResultUndefinedError&) { return FloatBounds(0.0, 0.0, false); }}
class ComputeIntSetBounds : public EVisitor {public: std::vector<IntSetVal*> bounds; bool valid; EnvI& env; ComputeIntSetBounds(EnvI& env0) : valid(true), env(env0) {} bool enter(Expression* e) { if (e->type().isAnn()) { return false; } if (e->isa<VarDecl>()) { return false; } if (e->type().dim() > 0) { return false; } if (!e->type().isIntSet()) { return false; } if (e->type().isPar()) { bounds.push_back(eval_intset(env, e)); return false; } return true; } /// Visit set literal void vSetLit(const SetLit& sl) { assert(sl.type().isvar()); assert(sl.isv() == nullptr);
IntSetVal* isv = IntSetVal::a(); for (unsigned int i = 0; i < sl.v().size(); i++) { IntSetRanges i0(isv); IntBounds ib = compute_int_bounds(env, sl.v()[i]); if (!ib.valid || !ib.l.isFinite() || !ib.u.isFinite()) { valid = false; bounds.push_back(nullptr); return; } Ranges::Const<IntVal> cr(ib.l, ib.u); Ranges::Union<IntVal, IntSetRanges, Ranges::Const<IntVal>> u(i0, cr); isv = IntSetVal::ai(u); } bounds.push_back(isv); } /// Visit identifier void vId(const Id& id) { if ((id.decl()->ti()->domain() != nullptr) && !id.decl()->ti()->domain()->isa<TIId>()) { bounds.push_back(eval_intset(env, id.decl()->ti()->domain())); } else { if (id.decl()->e() != nullptr) { BottomUpIterator<ComputeIntSetBounds> cbi(*this); cbi.run(id.decl()->e()); } else { valid = false; bounds.push_back(nullptr); } } } /// Visit anonymous variable void vAnonVar(const AnonVar& v) { valid = false; bounds.push_back(nullptr); } /// Visit array access void vArrayAccess(ArrayAccess& aa) { bool parAccess = true; for (unsigned int i = aa.idx().size(); (i--) != 0U;) { if (!aa.idx()[i]->type().isPar()) { parAccess = false; break; } } if (Id* id = aa.v()->dynamicCast<Id>()) { while ((id->decl()->e() != nullptr) && id->decl()->e()->isa<Id>()) { id = id->decl()->e()->cast<Id>(); } if (parAccess && (id->decl()->e() != nullptr)) { bool success; Expression* e = eval_arrayaccess(env, &aa, success); if (success) { BottomUpIterator<ComputeIntSetBounds> cbi(*this); cbi.run(e); return; } } if (id->decl()->ti()->domain() != nullptr) { bounds.push_back(eval_intset(env, id->decl()->ti()->domain())); return; } } valid = false; bounds.push_back(nullptr); } /// Visit array comprehension void vComprehension(const Comprehension& c) { valid = false; bounds.push_back(nullptr); } /// Visit if-then-else void vITE(const ITE& ite) { valid = false; bounds.push_back(nullptr); } /// Visit binary operator void vBinOp(const BinOp& bo) { if (bo.op() == BOT_DOTDOT) { IntBounds lb = compute_int_bounds(env, bo.lhs()); IntBounds ub = compute_int_bounds(env, bo.rhs()); valid = valid && lb.valid && ub.valid; bounds.push_back(IntSetVal::a(lb.l, ub.u)); } else { IntSetVal* b1 = bounds.back(); bounds.pop_back(); IntSetVal* b0 = bounds.back(); bounds.pop_back(); switch (bo.op()) { case BOT_INTERSECT: case BOT_UNION: { IntSetRanges b0r(b0); IntSetRanges b1r(b1); Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(b0r, b1r); bounds.push_back(IntSetVal::ai(u)); } break; case BOT_DIFF: { bounds.push_back(b0); } break; case BOT_SYMDIFF: valid = false; bounds.push_back(nullptr); break; case BOT_PLUS: case BOT_MINUS: case BOT_MULT: case BOT_POW: case BOT_DIV: case BOT_IDIV: case BOT_MOD: case BOT_LE: case BOT_LQ: case BOT_GR: case BOT_GQ: case BOT_EQ: case BOT_NQ: case BOT_IN: case BOT_SUBSET: case BOT_SUPERSET: case BOT_PLUSPLUS: case BOT_EQUIV: case BOT_IMPL: case BOT_RIMPL: case BOT_OR: case BOT_AND: case BOT_XOR: case BOT_DOTDOT: valid = false; bounds.push_back(nullptr); } } } /// Visit unary operator void vUnOp(const UnOp& uo) { valid = false; bounds.push_back(nullptr); } /// Visit call void vCall(Call& c) { if (valid && (c.id() == "set_intersect" || c.id() == "set_union")) { IntSetVal* b0 = bounds.back(); bounds.pop_back(); IntSetVal* b1 = bounds.back(); bounds.pop_back(); IntSetRanges b0r(b0); IntSetRanges b1r(b1); Ranges::Union<IntVal, IntSetRanges, IntSetRanges> u(b0r, b1r); bounds.push_back(IntSetVal::ai(u)); } else if (valid && c.id() == "set_diff") { IntSetVal* b0 = bounds.back(); bounds.pop_back(); bounds.pop_back(); // don't need bounds of right hand side bounds.push_back(b0); } else if ((c.decl() != nullptr) && (c.decl()->ti()->domain() != nullptr) && !c.decl()->ti()->domain()->isa<TIId>()) { for (int i = 0; i < c.argCount(); i++) { if (c.arg(i)->type().isIntSet()) { assert(!bounds.empty()); bounds.pop_back(); } } IntSetVal* fsv = eval_intset(env, c.decl()->ti()->domain()); bounds.push_back(fsv); } else { valid = false; bounds.push_back(nullptr); } } /// Visit let void vLet(const Let& l) { valid = false; bounds.push_back(nullptr); } /// Visit variable declaration void vVarDecl(const VarDecl& vd) { valid = false; bounds.push_back(nullptr); } /// Visit annotation void vAnnotation(const Annotation& e) { valid = false; bounds.push_back(nullptr); } /// Visit type inst void vTypeInst(const TypeInst& e) { valid = false; bounds.push_back(nullptr); } /// Visit TIId void vTIId(const TIId& e) { valid = false; bounds.push_back(nullptr); }};
IntSetVal* compute_intset_bounds(EnvI& env, Expression* e) { try { ComputeIntSetBounds cb(env); BottomUpIterator<ComputeIntSetBounds> cbi(cb); cbi.run(e); if (cb.valid) { return cb.bounds.back(); } return nullptr;
} catch (ResultUndefinedError&) { return nullptr; }}
Expression* follow_id(Expression* e) { for (;;) { if (e == nullptr) { return nullptr; } if (e->eid() == Expression::E_ID && e != constants().absent) { e = e->cast<Id>()->decl()->e(); } else { return e; } }}
Expression* follow_id_to_decl(Expression* e) { for (;;) { if (e == nullptr) { return nullptr; } if (e == constants().absent) { return e; } switch (e->eid()) { case Expression::E_ID: e = e->cast<Id>()->decl(); break; case Expression::E_VARDECL: { Expression* vd_e = e->cast<VarDecl>()->e(); if ((vd_e != nullptr) && vd_e->isa<Id>() && vd_e != constants().absent) { e = vd_e; } else { return e; } break; } default: return e; } }}
Expression* follow_id_to_value(Expression* e) { Expression* decl = follow_id_to_decl(e); if (auto* vd = decl->dynamicCast<VarDecl>()) { if ((vd->e() != nullptr) && vd->e()->type().isPar()) { return vd->e(); } return vd->id(); } return decl;}
} // namespace MiniZinc