diff --git a/.gitignore b/.gitignore index 5bbeeb6..04f629e 100644 --- a/.gitignore +++ b/.gitignore @@ -1,66 +1,67 @@ # Compiled Object files *.slo *.lo *.o *.obj # Compiled Dynamic libraries *.so *.so.* *.dylib *.dll # Compiled Static libraries *.lai *.la *.a *.lib # Executables *.exe *.out *.app *.class # Mobile Tools for Java (J2ME) .mtj.tmp/ # Package Files # *.jar *.war *.ear # virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml hs_err_pid* # Qt-es /.qmake.cache /.qmake.stash *.pro.user *.pro.user.* *.moc moc_*.cpp qrc_*.cpp ui_*.h Makefile* *-build-* # QtCreator *.autosave coco/*.old coco/*~ *~ -cpp/build-debug/* +cpp/build-*/* cpp/xreate-debug/* cpp/xreate-release/* cpp/.idea cpp/CMakeLists.txt.user* hs/* project/* nb*.xml +.* target/* diff --git a/coco/Parser.cpp b/coco/Parser.cpp index 3ec2513..9fe0289 100644 --- a/coco/Parser.cpp +++ b/coco/Parser.cpp @@ -1,719 +1,859 @@ /*---------------------------------------------------------------------- Compiler Generator Coco/R, Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz extended by M. Loeberbauer & A. Woess, Univ. of Linz ported to C++ by Csaba Balazs, University of Szeged with improvements by Pat Terry, Rhodes University This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. As an exception, it is allowed to write an extension of Coco/R that is used as a plugin in non-free software. If not otherwise stated, any source code generated by Coco/R (other than Coco/R itself) does not fall under the GNU General Public License. -----------------------------------------------------------------------*/ #include #include "Parser.h" #include "Scanner.h" void Parser::SynErr(int n) { if (errDist >= minErrDist) errors->SynErr(la->line, la->col, n); errDist = 0; } void Parser::SemErr(const wchar_t* msg) { if (errDist >= minErrDist) errors->Error(t->line, t->col, msg); errDist = 0; } void Parser::Get() { for (;;) { t = la; la = scanner->Scan(); if (la->kind <= maxT) { ++errDist; break; } if (dummyToken != t) { dummyToken->kind = t->kind; dummyToken->pos = t->pos; dummyToken->col = t->col; dummyToken->line = t->line; dummyToken->next = NULL; coco_string_delete(dummyToken->val); dummyToken->val = coco_string_create(t->val); t = dummyToken; } la = t; } } void Parser::Expect(int n) { if (la->kind==n) Get(); else { SynErr(n); } } void Parser::ExpectWeak(int n, int follow) { if (la->kind == n) Get(); else { SynErr(n); while (!StartOf(follow)) Get(); } } bool Parser::WeakSeparator(int n, int syFol, int repFol) { if (la->kind == n) {Get(); return true;} else if (StartOf(repFol)) {return false;} else { SynErr(n); while (!(StartOf(syFol) || StartOf(repFol) || StartOf(0))) { Get(); } return StartOf(syFol); } } void Parser::Xreate() { - while (la->kind == _ident || la->kind == 26 /* "rule" */) { + while (StartOf(1)) { if (la->kind == _ident) { FDecl(); - } else { + } else if (la->kind == 37 /* "rule" */) { RuleDecl(); + } else if (la->kind == 29 /* "pass" */) { + PassData(); + } else { + Imprt(); } } } void Parser::FDecl() { std::wstring fname; std::wstring varname; TypeAnnotation typIn; TypeAnnotation typOut; Ident(fname); Expect(_assign); - Expect(10 /* "function" */); - Expect(11 /* ":" */); - Function f = Function(fname); - if (StartOf(1)) { + Expect(11 /* "function" */); + Expect(12 /* ":" */); + Function* f = new Function(fname); CodeScope* entry = f->getEntryScope(); + if (StartOf(2)) { Type(typOut); - f.setReturnType(typOut); + f->setReturnType(typOut); } else if (la->kind == _lparen) { Get(); if (la->kind == _ident) { Ident(varname); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Type(typIn); - f.addArg(std::move(varname), move(typIn)); - while (la->kind == 12 /* "," */) { + f->addArg(std::move(varname), move(typIn)); + while (la->kind == 13 /* "," */) { Get(); Ident(varname); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Type(typIn); - f.addArg(std::move(varname), move(typIn)); + f->addArg(std::move(varname), move(typIn)); } } Expect(_rparen); Expect(_implic); Type(typOut); - f.setReturnType(typOut); - while (la->kind == 12 /* "," */) { + f->setReturnType(typOut); + while (la->kind == 13 /* "," */) { Get(); FnTag(f); } - } else SynErr(37); - BDecl(f.getEntryScope()); + } else SynErr(49); + BDecl(entry); root.add(f); } void Parser::RuleDecl() { - Expect(26 /* "rule" */); - Expect(11 /* ":" */); + Expect(37 /* "rule" */); + Expect(12 /* ":" */); RuleArguments args; RuleGuards guards; DomainAnnotation typ; std::wstring arg; Expect(_lparen); Ident(arg); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Domain(typ); args.add(arg, typ); - while (la->kind == 12 /* "," */) { + while (la->kind == 13 /* "," */) { Get(); Ident(arg); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Domain(typ); args.add(arg, typ); } Expect(_rparen); - if (la->kind == 27 /* "case" */) { + if (la->kind == 38 /* "case" */) { Get(); RGuard(guards); - while (la->kind == 12 /* "," */) { + while (la->kind == 13 /* "," */) { Get(); RGuard(guards); } } Expect(19 /* "{" */); RBody(args, guards); - Expect(20 /* "}" */); + Expect(21 /* "}" */); +} + +void Parser::PassData() { + Expect(29 /* "pass" */); + Expect(_lparen); + Expect(_ident); + Expect(_rparen); + Expect(19 /* "{" */); + while (la->kind == 30 /* "operator" */) { + InDecl(); + } + Expect(21 /* "}" */); +} + +void Parser::Imprt() { + Expect(27 /* "import" */); + Expect(28 /* "raw" */); + Expect(_lparen); + Expect(_string); + root.__rawImports.push_back(Atom(t->val).get()); + Expect(_rparen); + Expect(20 /* ";" */); } void Parser::Ident(std::wstring& name) { Expect(_ident); name = t->val; } void Parser::Type(TypeAnnotation& typ) { TypeAnnotation typ2; TypeAtom typ3; if (la->kind == _lbrack) { Get(); Type(typ2); Expect(_rbrack); typ = TypeAnnotation(TypeOperator::LIST, {typ2}); - } else if (StartOf(2)) { + } else if (StartOf(3)) { TypeTerm(typ3); typ = TypeAnnotation(typ3); - } else SynErr(38); + } else SynErr(50); } -void Parser::FnTag(Function& f) { +void Parser::FnTag(Function* f) { Expression tag; TagModifier mod = TagModifier::NONE; MetaSimpExpr(tag); - if (la->kind == 23 /* "-" */) { + if (la->kind == 34 /* "-" */) { Get(); TagMod(mod); } - f.addTag(std::move(tag), mod); + f->addTag(std::move(tag), mod); } -void Parser::BDecl(CodeScope& scope) { +void Parser::BDecl(CodeScope* scope) { Expression body; Expect(19 /* "{" */); - while (StartOf(3)) { + while (StartOf(4)) { if (checkAssignment()) { VDecl(scope); - Expect(18 /* ";" */); - } else if (la->kind == 11 /* ":" */) { + Expect(20 /* ";" */); + } else if (la->kind == 12 /* ":" */) { TagsDecl(scope); - Expect(18 /* ";" */); + Expect(20 /* ";" */); } else { Expr(body); - Expect(18 /* ";" */); - scope.setBody(body); + Expect(20 /* ";" */); + scope->setBody(body); } } - Expect(20 /* "}" */); + Expect(21 /* "}" */); } void Parser::TypeTerm(TypeAtom& typ) { - if (la->kind == 13 /* "string" */) { + if (la->kind == 14 /* "string" */) { Get(); - } else if (la->kind == 14 /* "int" */) { + } else if (la->kind == 15 /* "int" */) { Get(); - } else if (la->kind == 15 /* "num" */) { + } else if (la->kind == 16 /* "num" */) { Get(); - } else if (la->kind == 16 /* "float" */) { + } else if (la->kind == 17 /* "float" */) { Get(); - } else if (la->kind == 17 /* "bool" */) { + } else if (la->kind == 18 /* "bool" */) { Get(); - } else SynErr(39); + } else SynErr(51); typ = Atom(t->val); } -void Parser::VDecl(CodeScope& f) { +void Parser::VDecl(CodeScope* f) { std::wstring vname; Expression e; TypeAnnotation typ; Ident(vname); Expect(_assign); if (la->kind == _lbrack) { ListLiteral(e); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Type(typ); - } else if (la->kind == 21 /* "loop" */) { - LoopDecl(e, typ); - Expect(18 /* ";" */); - } else if (StartOf(4)) { + } else if (la->kind == 24 /* "loop" */) { + LoopDecl(e, typ, f); + } else if (la->kind == 22 /* "if" */) { + IfDecl(e, f, typ); + } else if (StartOf(5)) { Expr(e); - Expect(11 /* ":" */); + Expect(12 /* ":" */); Type(typ); - } else SynErr(40); - f.addDeclaration(move(vname), move(typ), move(e)); + } else SynErr(52); + f->addDeclaration(move(vname), move(typ), move(e)); } void Parser::ListLiteral(Expression& e) { - Expression e2; + Expression eFrom, eTo; Expect(_lbrack); - e.setOp(Operator::LIST); - if (StartOf(4)) { - Expr(e2); - e.addArg(std::move(e2)); - while (la->kind == 12 /* "," */) { + if (StartOf(5)) { + Expr(eFrom); + e.addArg(std::move(eFrom)); + if (la->kind == 42 /* ".." */) { Get(); - Expr(e2); - e.addArg(std::move(e2)); - } + Expr(eTo); + e.addArg(std::move(eTo)); e.setOp(Operator::LIST_RANGE); + } else if (la->kind == _rbrack || la->kind == 13 /* "," */) { + while (la->kind == 13 /* "," */) { + Get(); + Expr(eFrom); + e.addArg(std::move(eFrom)); + } + e.setOp(Operator::LIST); + } else SynErr(53); } Expect(_rbrack); } -void Parser::LoopDecl(Expression& e, TypeAnnotation& typOut) { - std::wstring varIn, varEl; TypeAnnotation typEl; CodeScope block; - Expect(21 /* "loop" */); - Expect(22 /* "map" */); +void Parser::LoopDecl(Expression& e, TypeAnnotation& typOut, CodeScope* f) { + std::wstring varIn, varEl, varAcc; TypeAnnotation typEl, typAcc; Expression eAcc; + ManagedScpPtr block = root.add(new xreate::CodeScope(f)); + Expect(24 /* "loop" */); + if (la->kind == 25 /* "map" */) { + Get(); + Expect(_lparen); + Ident(varIn); + Expect(_implic); + Ident(varEl); + Expect(12 /* ":" */); + Type(typEl); + Expect(_rparen); + Expect(12 /* ":" */); + Type(typOut); + BDecl(&*block); + e = Expression(Operator::MAP, {Expression(Atom(varIn))}); + e.addBindings({Atom(varEl)}); + block->addArg(Atom(varEl), move(typEl)); + e.addBlock(block); + } else if (la->kind == 26 /* "fold" */) { + Get(); + Expect(_lparen); + Ident(varIn); + Expect(_implic); + Ident(varEl); + Expect(12 /* ":" */); + Type(typEl); + Expect(13 /* "," */); + Expr(eAcc); + Expect(_implic); + Ident(varAcc); + Expect(12 /* ":" */); + Type(typAcc); + Expect(_rparen); + Expect(12 /* ":" */); + Type(typOut); + BDecl(&*block); + e = Expression(Operator::FOLD, {Expression(Atom(varIn)), eAcc}); + e.addBindings({Atom(varEl), Atom(varAcc)}); + block->addArg(Atom(varEl), move(typEl)); + block->addArg(Atom(varAcc), move(typAcc)); + e.addBlock(block); + + } else SynErr(54); +} + +void Parser::IfDecl(Expression& e, CodeScope* outer, TypeAnnotation typ) { + Expression cond; ManagedScpPtr blockTrue = root.add(new xreate::CodeScope(outer)); ManagedScpPtr blockFalse = root.add(new xreate::CodeScope(outer)); + TypeAnnotation typIf; + Expect(22 /* "if" */); Expect(_lparen); - Ident(varIn); - Expect(_implic); - Ident(varEl); - Expect(11 /* ":" */); - Type(typEl); + Expr(cond); Expect(_rparen); - Expect(11 /* ":" */); - Type(typOut); - BDecl(block); - e = Expression(Operator::LOOP, {Expression(Atom(varIn))}); e.addBindings({Atom(varEl)}); - block.addArg(Atom(varEl), move(typEl)); e.addBlock(move(block)); + Expect(12 /* ":" */); + Type(typIf); + BDecl(&*blockTrue); + Expect(23 /* "else" */); + BDecl(&*blockFalse); + e = Expression(Operator::IF, {cond}); e.addBlock(blockTrue); e.addBlock(blockFalse); } void Parser::Expr(Expression& e) { Operator op; Expression e2; SimExpr(e); - if (la->kind == _assign || la->kind == 34 /* "<" */ || la->kind == 35 /* ">" */) { + if (la->kind == _equal || la->kind == 46 /* "<" */ || la->kind == 47 /* ">" */) { RelOp(op); SimExpr(e2); e = Expression(op, {e, e2}); } } -void Parser::TagsDecl(CodeScope& f) { +void Parser::TagsDecl(CodeScope* f) { Expression tag; TagModifier mod = TagModifier::NONE; - Expect(11 /* ":" */); - while (la->kind == _ident || la->kind == 23 /* "-" */) { + Expect(12 /* ":" */); + while (la->kind == _ident || la->kind == 34 /* "-" */) { MetaSimpExpr(tag); - if (la->kind == 23 /* "-" */) { + if (la->kind == 34 /* "-" */) { Get(); TagMod(mod); } } } +void Parser::InDecl() { + Operator op; Expression tag; + Expression scheme; + std::vector& tags = scheme.operands; + tags.push_back(Expression()); /* return value */ + Expect(30 /* "operator" */); + InAlias(op); + Expect(12 /* ":" */); + Expect(_lparen); + scheme.setOp(op); + if (la->kind == _ident || la->kind == 34 /* "-" */) { + MetaSimpExpr(tag); + tags.push_back(tag); + while (la->kind == 13 /* "," */) { + Get(); + MetaSimpExpr(tag); + tags.push_back(tag); + } + } + Expect(_rparen); + if (la->kind == _implic) { + Get(); + MetaSimpExpr(tag); + tags[0] = tag; + } + root.addDFAData(move(scheme)); + Expect(20 /* ";" */); +} + +void Parser::InAlias(Operator& op) { + if (la->kind == 25 /* "map" */) { + Get(); + op = Operator::MAP; + } else if (la->kind == 31 /* "list_range" */) { + Get(); + op = Operator::LIST_RANGE; + } else if (la->kind == 32 /* "list" */) { + Get(); + op = Operator::LIST; + } else if (la->kind == 26 /* "fold" */) { + Get(); + op = Operator::FOLD; + } else if (la->kind == 33 /* "index" */) { + Get(); + op = Operator::INDEX; + } else SynErr(55); +} + void Parser::MetaSimpExpr(Expression& e) { std::wstring i1, infix; Expression e2; - if (la->kind == 23 /* "-" */) { + if (la->kind == 34 /* "-" */) { Get(); MetaSimpExpr(e2); e = Expression(Operator::NEG, {e2}); } else if (checkParametersList()) { Ident(i1); e = Expression(Operator::CALL, {Expression(Atom(i1))}); Expect(_lparen); - if (StartOf(4)) { + if (StartOf(5)) { CalleeParams(e); } Expect(_rparen); } else if (checkInfix()) { Ident(i1); Ident(infix); MetaSimpExpr(e2); e = Expression(Operator::CALL, {Expression(Atom(infix))}); e.addArg(Expression(Atom(i1))); e.addArg(std::move(e2)); } else if (la->kind == _ident) { Ident(i1); e = Expression(Atom(i1)); - } else SynErr(41); + } else SynErr(56); } void Parser::TagMod(TagModifier& mod) { - if (la->kind == 24 /* "assert" */) { + if (la->kind == 35 /* "assert" */) { Get(); mod = TagModifier::ASSERT; - } else if (la->kind == 25 /* "require" */) { + } else if (la->kind == 36 /* "require" */) { Get(); mod = TagModifier::REQUIRE; - } else SynErr(42); + } else SynErr(57); } void Parser::Domain(DomainAnnotation& dom) { - if (la->kind == 10 /* "function" */) { + if (la->kind == 11 /* "function" */) { Get(); dom = DomainAnnotation::FUNCTION; - } else if (la->kind == 28 /* "variable" */) { + } else if (la->kind == 39 /* "variable" */) { Get(); dom = DomainAnnotation::VARIABLE; - } else SynErr(43); + } else SynErr(58); } void Parser::RGuard(RuleGuards& guards) { Expression e; MetaExpr(e); guards.add(std::move(e)); } void Parser::RBody(const RuleArguments& args, const RuleGuards& guards) { Expression e; std::wstring msg; - Expect(29 /* "warning" */); + Expect(40 /* "warning" */); MetaExpr(e); - if (la->kind == 30 /* "message" */) { + if (la->kind == 41 /* "message" */) { Get(); Expect(_string); msg = t->val; } root.add(new RuleWarning(RuleArguments(args), RuleGuards(guards), std::move(e), Atom(msg))); } void Parser::MetaExpr(Expression& e) { Operator op; Expression e2; MetaExpr2(e); if (la->kind == _implic) { MetaOp(op); MetaExpr2(e2); e = Expression(op, {e, e2}); } } void Parser::MetaExpr2(Expression& e) { if (la->kind == _lparen) { Get(); MetaExpr(e); Expect(_rparen); - } else if (la->kind == _ident || la->kind == 23 /* "-" */) { + } else if (la->kind == _ident || la->kind == 34 /* "-" */) { MetaSimpExpr(e); - } else SynErr(44); + } else SynErr(59); } void Parser::MetaOp(Operator& op) { Expect(_implic); op = Operator::IMPL; } void Parser::CalleeParams(Expression& e) { Expression e2; Expr(e2); e.addArg(std::move(e2)); - while (la->kind == 12 /* "," */) { + while (la->kind == 13 /* "," */) { Get(); Expr(e2); e.addArg(std::move(e2)); } } void Parser::SimExpr(Expression& e) { Operator op; Expression e2; Term(e); - while (la->kind == 23 /* "-" */ || la->kind == 31 /* "+" */) { + while (la->kind == 34 /* "-" */ || la->kind == 43 /* "+" */) { AddOp(op); Term(e2); e = Expression(op, {e, e2}); } } void Parser::RelOp(Operator& op) { op = Operator::EQU; - if (la->kind == _assign) { + if (la->kind == _equal) { Get(); - Expect(_assign); - } else if (la->kind == 34 /* "<" */) { + } else if (la->kind == 46 /* "<" */) { Get(); op = Operator::LSS; - } else if (la->kind == 35 /* ">" */) { + } else if (la->kind == 47 /* ">" */) { Get(); op = Operator::GTR; - } else SynErr(45); + } else SynErr(60); } void Parser::Term(Expression& e) { Operator op; Expression e2; Factor(e); - while (la->kind == 32 /* "*" */ || la->kind == 33 /* "/" */) { + while (la->kind == 44 /* "*" */ || la->kind == 45 /* "/" */) { MulOp(op); Factor(e2); e = Expression(op, {e, e2}); } } void Parser::AddOp(Operator& op) { op = Operator::ADD; - if (la->kind == 31 /* "+" */) { + if (la->kind == 43 /* "+" */) { Get(); - } else if (la->kind == 23 /* "-" */) { + } else if (la->kind == 34 /* "-" */) { Get(); op = Operator::SUB; - } else SynErr(46); + } else SynErr(61); } void Parser::Factor(Expression& e) { std::wstring name; if (checkParametersList()) { Ident(name); e = Expression(Operator::CALL, {Atom(name)}); Expect(_lparen); - if (StartOf(4)) { + if (StartOf(5)) { CalleeParams(e); } Expect(_rparen); } else if (checkIndex()) { Ident(name); e = Expression(Operator::INDEX, {Atom(name)}); Expect(_lbrack); CalleeParams(e); Expect(_rbrack); } else if (la->kind == _ident) { Ident(name); e = Expression(Atom(name)); } else if (la->kind == _number) { Get(); e = Expression(Atom(t->val)); - } else if (la->kind == 23 /* "-" */) { + } else if (la->kind == 34 /* "-" */) { Get(); Factor(e); e = Expression(Operator::NEG, {e}); } else if (la->kind == _lparen) { Get(); Expr(e); Expect(_rparen); - } else SynErr(47); + } else SynErr(62); } void Parser::MulOp(Operator& op) { op = Operator::MUL; - if (la->kind == 32 /* "*" */) { + if (la->kind == 44 /* "*" */) { Get(); - } else if (la->kind == 33 /* "/" */) { + } else if (la->kind == 45 /* "/" */) { Get(); op = Operator::DIV; - } else SynErr(48); + } else SynErr(63); } // If the user declared a method Init and a mehtod Destroy they should // be called in the contructur and the destructor respctively. // // The following templates are used to recognize if the user declared // the methods Init and Destroy. template struct ParserInitExistsRecognizer { template struct ExistsIfInitIsDefinedMarker{}; struct InitIsMissingType { char dummy1; }; struct InitExistsType { char dummy1; char dummy2; }; // exists always template static InitIsMissingType is_here(...); // exist only if ExistsIfInitIsDefinedMarker is defined template static InitExistsType is_here(ExistsIfInitIsDefinedMarker*); enum { InitExists = (sizeof(is_here(NULL)) == sizeof(InitExistsType)) }; }; template struct ParserDestroyExistsRecognizer { template struct ExistsIfDestroyIsDefinedMarker{}; struct DestroyIsMissingType { char dummy1; }; struct DestroyExistsType { char dummy1; char dummy2; }; // exists always template static DestroyIsMissingType is_here(...); // exist only if ExistsIfDestroyIsDefinedMarker is defined template static DestroyExistsType is_here(ExistsIfDestroyIsDefinedMarker*); enum { DestroyExists = (sizeof(is_here(NULL)) == sizeof(DestroyExistsType)) }; }; // The folloing templates are used to call the Init and Destroy methods if they exist. // Generic case of the ParserInitCaller, gets used if the Init method is missing template::InitExists> struct ParserInitCaller { static void CallInit(T *t) { // nothing to do } }; // True case of the ParserInitCaller, gets used if the Init method exists template struct ParserInitCaller { static void CallInit(T *t) { t->Init(); } }; // Generic case of the ParserDestroyCaller, gets used if the Destroy method is missing template::DestroyExists> struct ParserDestroyCaller { static void CallDestroy(T *t) { // nothing to do } }; // True case of the ParserDestroyCaller, gets used if the Destroy method exists template struct ParserDestroyCaller { static void CallDestroy(T *t) { t->Destroy(); } }; void Parser::Parse() { t = NULL; la = dummyToken = new Token(); la->val = coco_string_create(L"Dummy Token"); Get(); Xreate(); Expect(0); } Parser::Parser(Scanner *scanner) { - maxT = 36; + maxT = 48; ParserInitCaller::CallInit(this); dummyToken = NULL; t = la = NULL; minErrDist = 2; errDist = minErrDist; this->scanner = scanner; errors = new Errors(); } bool Parser::StartOf(int s) { const bool T = true; const bool x = false; - static bool set[5][38] = { - {T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, - {x,x,x,x, x,x,T,x, x,x,x,x, x,T,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, - {x,x,x,x, x,x,x,x, x,x,x,x, x,T,T,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, - {x,T,T,x, T,x,x,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, - {x,T,T,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x} + static bool set[6][50] = { + {T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, + {x,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,T,x,x, x,x,x,x, x,T,x,x, x,x,x,x, x,x,x,x, x,x}, + {x,x,x,x, x,x,T,x, x,x,x,x, x,x,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, + {x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,T, T,T,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, + {x,T,T,x, T,x,x,x, x,x,x,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x}, + {x,T,T,x, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x} }; return set[s][la->kind]; } Parser::~Parser() { ParserDestroyCaller::CallDestroy(this); delete errors; delete dummyToken; } Errors::Errors() { count = 0; } void Errors::SynErr(int line, int col, int n) { wchar_t* s; switch (n) { case 0: s = coco_string_create(L"EOF expected"); break; case 1: s = coco_string_create(L"ident expected"); break; case 2: s = coco_string_create(L"number expected"); break; case 3: s = coco_string_create(L"string expected"); break; case 4: s = coco_string_create(L"lparen expected"); break; case 5: s = coco_string_create(L"rparen expected"); break; case 6: s = coco_string_create(L"lbrack expected"); break; case 7: s = coco_string_create(L"rbrack expected"); break; - case 8: s = coco_string_create(L"assign expected"); break; - case 9: s = coco_string_create(L"implic expected"); break; - case 10: s = coco_string_create(L"\"function\" expected"); break; - case 11: s = coco_string_create(L"\":\" expected"); break; - case 12: s = coco_string_create(L"\",\" expected"); break; - case 13: s = coco_string_create(L"\"string\" expected"); break; - case 14: s = coco_string_create(L"\"int\" expected"); break; - case 15: s = coco_string_create(L"\"num\" expected"); break; - case 16: s = coco_string_create(L"\"float\" expected"); break; - case 17: s = coco_string_create(L"\"bool\" expected"); break; - case 18: s = coco_string_create(L"\";\" expected"); break; + case 8: s = coco_string_create(L"equal expected"); break; + case 9: s = coco_string_create(L"assign expected"); break; + case 10: s = coco_string_create(L"implic expected"); break; + case 11: s = coco_string_create(L"\"function\" expected"); break; + case 12: s = coco_string_create(L"\":\" expected"); break; + case 13: s = coco_string_create(L"\",\" expected"); break; + case 14: s = coco_string_create(L"\"string\" expected"); break; + case 15: s = coco_string_create(L"\"int\" expected"); break; + case 16: s = coco_string_create(L"\"num\" expected"); break; + case 17: s = coco_string_create(L"\"float\" expected"); break; + case 18: s = coco_string_create(L"\"bool\" expected"); break; case 19: s = coco_string_create(L"\"{\" expected"); break; - case 20: s = coco_string_create(L"\"}\" expected"); break; - case 21: s = coco_string_create(L"\"loop\" expected"); break; - case 22: s = coco_string_create(L"\"map\" expected"); break; - case 23: s = coco_string_create(L"\"-\" expected"); break; - case 24: s = coco_string_create(L"\"assert\" expected"); break; - case 25: s = coco_string_create(L"\"require\" expected"); break; - case 26: s = coco_string_create(L"\"rule\" expected"); break; - case 27: s = coco_string_create(L"\"case\" expected"); break; - case 28: s = coco_string_create(L"\"variable\" expected"); break; - case 29: s = coco_string_create(L"\"warning\" expected"); break; - case 30: s = coco_string_create(L"\"message\" expected"); break; - case 31: s = coco_string_create(L"\"+\" expected"); break; - case 32: s = coco_string_create(L"\"*\" expected"); break; - case 33: s = coco_string_create(L"\"/\" expected"); break; - case 34: s = coco_string_create(L"\"<\" expected"); break; - case 35: s = coco_string_create(L"\">\" expected"); break; - case 36: s = coco_string_create(L"??? expected"); break; - case 37: s = coco_string_create(L"invalid FDecl"); break; - case 38: s = coco_string_create(L"invalid Type"); break; - case 39: s = coco_string_create(L"invalid TypeTerm"); break; - case 40: s = coco_string_create(L"invalid VDecl"); break; - case 41: s = coco_string_create(L"invalid MetaSimpExpr"); break; - case 42: s = coco_string_create(L"invalid TagMod"); break; - case 43: s = coco_string_create(L"invalid Domain"); break; - case 44: s = coco_string_create(L"invalid MetaExpr2"); break; - case 45: s = coco_string_create(L"invalid RelOp"); break; - case 46: s = coco_string_create(L"invalid AddOp"); break; - case 47: s = coco_string_create(L"invalid Factor"); break; - case 48: s = coco_string_create(L"invalid MulOp"); break; + case 20: s = coco_string_create(L"\";\" expected"); break; + case 21: s = coco_string_create(L"\"}\" expected"); break; + case 22: s = coco_string_create(L"\"if\" expected"); break; + case 23: s = coco_string_create(L"\"else\" expected"); break; + case 24: s = coco_string_create(L"\"loop\" expected"); break; + case 25: s = coco_string_create(L"\"map\" expected"); break; + case 26: s = coco_string_create(L"\"fold\" expected"); break; + case 27: s = coco_string_create(L"\"import\" expected"); break; + case 28: s = coco_string_create(L"\"raw\" expected"); break; + case 29: s = coco_string_create(L"\"pass\" expected"); break; + case 30: s = coco_string_create(L"\"operator\" expected"); break; + case 31: s = coco_string_create(L"\"list_range\" expected"); break; + case 32: s = coco_string_create(L"\"list\" expected"); break; + case 33: s = coco_string_create(L"\"index\" expected"); break; + case 34: s = coco_string_create(L"\"-\" expected"); break; + case 35: s = coco_string_create(L"\"assert\" expected"); break; + case 36: s = coco_string_create(L"\"require\" expected"); break; + case 37: s = coco_string_create(L"\"rule\" expected"); break; + case 38: s = coco_string_create(L"\"case\" expected"); break; + case 39: s = coco_string_create(L"\"variable\" expected"); break; + case 40: s = coco_string_create(L"\"warning\" expected"); break; + case 41: s = coco_string_create(L"\"message\" expected"); break; + case 42: s = coco_string_create(L"\"..\" expected"); break; + case 43: s = coco_string_create(L"\"+\" expected"); break; + case 44: s = coco_string_create(L"\"*\" expected"); break; + case 45: s = coco_string_create(L"\"/\" expected"); break; + case 46: s = coco_string_create(L"\"<\" expected"); break; + case 47: s = coco_string_create(L"\">\" expected"); break; + case 48: s = coco_string_create(L"??? expected"); break; + case 49: s = coco_string_create(L"invalid FDecl"); break; + case 50: s = coco_string_create(L"invalid Type"); break; + case 51: s = coco_string_create(L"invalid TypeTerm"); break; + case 52: s = coco_string_create(L"invalid VDecl"); break; + case 53: s = coco_string_create(L"invalid ListLiteral"); break; + case 54: s = coco_string_create(L"invalid LoopDecl"); break; + case 55: s = coco_string_create(L"invalid InAlias"); break; + case 56: s = coco_string_create(L"invalid MetaSimpExpr"); break; + case 57: s = coco_string_create(L"invalid TagMod"); break; + case 58: s = coco_string_create(L"invalid Domain"); break; + case 59: s = coco_string_create(L"invalid MetaExpr2"); break; + case 60: s = coco_string_create(L"invalid RelOp"); break; + case 61: s = coco_string_create(L"invalid AddOp"); break; + case 62: s = coco_string_create(L"invalid Factor"); break; + case 63: s = coco_string_create(L"invalid MulOp"); break; default: { wchar_t format[20]; coco_swprintf(format, 20, L"error %d", n); s = coco_string_create(format); } break; } wprintf(L"-- line %d col %d: %ls\n", line, col, s); coco_string_delete(s); count++; } void Errors::Error(int line, int col, const wchar_t *s) { wprintf(L"-- line %d col %d: %ls\n", line, col, s); count++; } void Errors::Warning(int line, int col, const wchar_t *s) { wprintf(L"-- line %d col %d: %ls\n", line, col, s); } void Errors::Warning(const wchar_t *s) { wprintf(L"%ls\n", s); } void Errors::Exception(const wchar_t* s) { wprintf(L"%ls", s); exit(1); } diff --git a/coco/Parser.h b/coco/Parser.h index 5d18bbc..56d39cd 100644 --- a/coco/Parser.h +++ b/coco/Parser.h @@ -1,163 +1,169 @@ /*---------------------------------------------------------------------- Compiler Generator Coco/R, Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz extended by M. Loeberbauer & A. Woess, Univ. of Linz ported to C++ by Csaba Balazs, University of Szeged with improvements by Pat Terry, Rhodes University This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. As an exception, it is allowed to write an extension of Coco/R that is used as a plugin in non-free software. If not otherwise stated, any source code generated by Coco/R (other than Coco/R itself) does not fall under the GNU General Public License. -----------------------------------------------------------------------*/ #if !defined(COCO_PARSER_H__) #define COCO_PARSER_H__ #include "ast.h" #include using namespace xreate; using namespace std; #include "Scanner.h" class Errors { public: int count; // number of errors detected Errors(); void SynErr(int line, int col, int n); void Error(int line, int col, const wchar_t *s); void Warning(int line, int col, const wchar_t *s); void Warning(const wchar_t *s); void Exception(const wchar_t *s); }; // Errors class Parser { private: enum { _EOF=0, _ident=1, _number=2, _string=3, _lparen=4, _rparen=5, _lbrack=6, _rbrack=7, - _assign=8, - _implic=9 + _equal=8, + _assign=9, + _implic=10 }; int maxT; Token *dummyToken; int errDist; int minErrDist; void SynErr(int n); void Get(); void Expect(int n); bool StartOf(int s); void ExpectWeak(int n, int follow); bool WeakSeparator(int n, int syFol, int repFol); public: Scanner *scanner; Errors *errors; Token *t; // last recognized token Token *la; // lookahead token -xreate::AST root; // current program unit (procedure or main program) +xreate::AST root; // current program unit bool checkParametersList() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _lparen; } bool checkInfix() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _ident; } bool checkIndex() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _lbrack; } bool checkAssignment() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _assign; } Parser(Scanner *scanner); ~Parser(); void SemErr(const wchar_t* msg); void Xreate(); void FDecl(); void RuleDecl(); + void PassData(); + void Imprt(); void Ident(std::wstring& name); void Type(TypeAnnotation& typ); - void FnTag(Function& f); - void BDecl(CodeScope& scope); + void FnTag(Function* f); + void BDecl(CodeScope* scope); void TypeTerm(TypeAtom& typ); - void VDecl(CodeScope& f); + void VDecl(CodeScope* f); void ListLiteral(Expression& e); - void LoopDecl(Expression& e, TypeAnnotation& typOut); + void LoopDecl(Expression& e, TypeAnnotation& typOut, CodeScope* f); + void IfDecl(Expression& e, CodeScope* outer, TypeAnnotation typ); void Expr(Expression& e); - void TagsDecl(CodeScope& f); + void TagsDecl(CodeScope* f); + void InDecl(); + void InAlias(Operator& op); void MetaSimpExpr(Expression& e); void TagMod(TagModifier& mod); void Domain(DomainAnnotation& dom); void RGuard(RuleGuards& guards); void RBody(const RuleArguments& args, const RuleGuards& guards); void MetaExpr(Expression& e); void MetaExpr2(Expression& e); void MetaOp(Operator& op); void CalleeParams(Expression& e); void SimExpr(Expression& e); void RelOp(Operator& op); void Term(Expression& e); void AddOp(Operator& op); void Factor(Expression& e); void MulOp(Operator& op); void Parse(); }; // end Parser #endif diff --git a/coco/Scanner.cpp b/coco/Scanner.cpp index c541a86..72d3c7c 100644 --- a/coco/Scanner.cpp +++ b/coco/Scanner.cpp @@ -1,766 +1,788 @@ /*---------------------------------------------------------------------- Compiler Generator Coco/R, Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz extended by M. Loeberbauer & A. Woess, Univ. of Linz ported to C++ by Csaba Balazs, University of Szeged with improvements by Pat Terry, Rhodes University This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. As an exception, it is allowed to write an extension of Coco/R that is used as a plugin in non-free software. If not otherwise stated, any source code generated by Coco/R (other than Coco/R itself) does not fall under the GNU General Public License. -----------------------------------------------------------------------*/ #include #include #include "Scanner.h" // string handling, wide character wchar_t* coco_string_create(const wchar_t* value) { return coco_string_create(value, 0); } wchar_t* coco_string_create(const wchar_t *value, int startIndex) { int valueLen = 0; int len = 0; if (value) { valueLen = wcslen(value); len = valueLen - startIndex; } return coco_string_create(value, startIndex, len); } wchar_t* coco_string_create(const wchar_t *value, int startIndex, int length) { int len = 0; wchar_t* data; if (value) { len = length; } data = new wchar_t[len + 1]; wcsncpy(data, &(value[startIndex]), len); data[len] = 0; return data; } wchar_t* coco_string_create_upper(const wchar_t* data) { if (!data) { return NULL; } int dataLen = 0; if (data) { dataLen = wcslen(data); } wchar_t *newData = new wchar_t[dataLen + 1]; for (int i = 0; i <= dataLen; i++) { if ((L'a' <= data[i]) && (data[i] <= L'z')) { newData[i] = data[i] + (L'A' - L'a'); } else { newData[i] = data[i]; } } newData[dataLen] = L'\0'; return newData; } wchar_t* coco_string_create_lower(const wchar_t* data) { if (!data) { return NULL; } int dataLen = wcslen(data); return coco_string_create_lower(data, 0, dataLen); } wchar_t* coco_string_create_lower(const wchar_t* data, int startIndex, int dataLen) { if (!data) { return NULL; } wchar_t* newData = new wchar_t[dataLen + 1]; for (int i = 0; i <= dataLen; i++) { wchar_t ch = data[startIndex + i]; if ((L'A' <= ch) && (ch <= L'Z')) { newData[i] = ch - (L'A' - L'a'); } else { newData[i] = ch; } } newData[dataLen] = L'\0'; return newData; } wchar_t* coco_string_create_append(const wchar_t* data1, const wchar_t* data2) { wchar_t* data; int data1Len = 0; int data2Len = 0; if (data1) { data1Len = wcslen(data1); } if (data2) {data2Len = wcslen(data2); } data = new wchar_t[data1Len + data2Len + 1]; if (data1) { wcscpy(data, data1); } if (data2) { wcscpy(data + data1Len, data2); } data[data1Len + data2Len] = 0; return data; } wchar_t* coco_string_create_append(const wchar_t *target, const wchar_t appendix) { int targetLen = coco_string_length(target); wchar_t* data = new wchar_t[targetLen + 2]; wcsncpy(data, target, targetLen); data[targetLen] = appendix; data[targetLen + 1] = 0; return data; } void coco_string_delete(wchar_t* &data) { delete [] data; data = NULL; } int coco_string_length(const wchar_t* data) { if (data) { return wcslen(data); } return 0; } bool coco_string_endswith(const wchar_t* data, const wchar_t *end) { int dataLen = wcslen(data); int endLen = wcslen(end); return (endLen <= dataLen) && (wcscmp(data + dataLen - endLen, end) == 0); } int coco_string_indexof(const wchar_t* data, const wchar_t value) { const wchar_t* chr = wcschr(data, value); if (chr) { return (chr-data); } return -1; } int coco_string_lastindexof(const wchar_t* data, const wchar_t value) { const wchar_t* chr = wcsrchr(data, value); if (chr) { return (chr-data); } return -1; } void coco_string_merge(wchar_t* &target, const wchar_t* appendix) { if (!appendix) { return; } wchar_t* data = coco_string_create_append(target, appendix); delete [] target; target = data; } bool coco_string_equal(const wchar_t* data1, const wchar_t* data2) { return wcscmp( data1, data2 ) == 0; } int coco_string_compareto(const wchar_t* data1, const wchar_t* data2) { return wcscmp(data1, data2); } int coco_string_hash(const wchar_t *data) { int h = 0; if (!data) { return 0; } while (*data != 0) { h = (h * 7) ^ *data; ++data; } if (h < 0) { h = -h; } return h; } // string handling, ascii character wchar_t* coco_string_create(const char* value) { int len = 0; if (value) { len = strlen(value); } wchar_t* data = new wchar_t[len + 1]; for (int i = 0; i < len; ++i) { data[i] = (wchar_t) value[i]; } data[len] = 0; return data; } char* coco_string_create_char(const wchar_t *value) { int len = coco_string_length(value); char *res = new char[len + 1]; for (int i = 0; i < len; ++i) { res[i] = (char) value[i]; } res[len] = 0; return res; } void coco_string_delete(char* &data) { delete [] data; data = NULL; } Token::Token() { kind = 0; pos = 0; col = 0; line = 0; val = NULL; next = NULL; } Token::~Token() { coco_string_delete(val); } Buffer::Buffer(FILE* s, bool isUserStream) { // ensure binary read on windows #if _MSC_VER >= 1300 _setmode(_fileno(s), _O_BINARY); #endif stream = s; this->isUserStream = isUserStream; if (CanSeek()) { fseek(s, 0, SEEK_END); fileLen = ftell(s); fseek(s, 0, SEEK_SET); bufLen = (fileLen < COCO_MAX_BUFFER_LENGTH) ? fileLen : COCO_MAX_BUFFER_LENGTH; bufStart = INT_MAX; // nothing in the buffer so far } else { fileLen = bufLen = bufStart = 0; } bufCapacity = (bufLen>0) ? bufLen : COCO_MIN_BUFFER_LENGTH; buf = new unsigned char[bufCapacity]; if (fileLen > 0) SetPos(0); // setup buffer to position 0 (start) else bufPos = 0; // index 0 is already after the file, thus Pos = 0 is invalid if (bufLen == fileLen && CanSeek()) Close(); } Buffer::Buffer(Buffer *b) { buf = b->buf; bufCapacity = b->bufCapacity; b->buf = NULL; bufStart = b->bufStart; bufLen = b->bufLen; fileLen = b->fileLen; bufPos = b->bufPos; stream = b->stream; b->stream = NULL; isUserStream = b->isUserStream; } Buffer::Buffer(const unsigned char* buf, int len) { this->buf = new unsigned char[len]; memcpy(this->buf, buf, len*sizeof(unsigned char)); bufStart = 0; bufCapacity = bufLen = len; fileLen = len; bufPos = 0; stream = NULL; } Buffer::~Buffer() { Close(); if (buf != NULL) { delete [] buf; buf = NULL; } } void Buffer::Close() { if (!isUserStream && stream != NULL) { fclose(stream); stream = NULL; } } int Buffer::Read() { if (bufPos < bufLen) { return buf[bufPos++]; } else if (GetPos() < fileLen) { SetPos(GetPos()); // shift buffer start to Pos return buf[bufPos++]; } else if ((stream != NULL) && !CanSeek() && (ReadNextStreamChunk() > 0)) { return buf[bufPos++]; } else { return EoF; } } int Buffer::Peek() { int curPos = GetPos(); int ch = Read(); SetPos(curPos); return ch; } // beg .. begin, zero-based, inclusive, in byte // end .. end, zero-based, exclusive, in byte wchar_t* Buffer::GetString(int beg, int end) { int len = 0; wchar_t *buf = new wchar_t[end - beg]; int oldPos = GetPos(); SetPos(beg); while (GetPos() < end) buf[len++] = (wchar_t) Read(); SetPos(oldPos); wchar_t *res = coco_string_create(buf, 0, len); coco_string_delete(buf); return res; } int Buffer::GetPos() { return bufPos + bufStart; } void Buffer::SetPos(int value) { if ((value >= fileLen) && (stream != NULL) && !CanSeek()) { // Wanted position is after buffer and the stream // is not seek-able e.g. network or console, // thus we have to read the stream manually till // the wanted position is in sight. while ((value >= fileLen) && (ReadNextStreamChunk() > 0)); } if ((value < 0) || (value > fileLen)) { wprintf(L"--- buffer out of bounds access, position: %d\n", value); exit(1); } if ((value >= bufStart) && (value < (bufStart + bufLen))) { // already in buffer bufPos = value - bufStart; } else if (stream != NULL) { // must be swapped in fseek(stream, value, SEEK_SET); bufLen = fread(buf, sizeof(unsigned char), bufCapacity, stream); bufStart = value; bufPos = 0; } else { bufPos = fileLen - bufStart; // make Pos return fileLen } } // Read the next chunk of bytes from the stream, increases the buffer // if needed and updates the fields fileLen and bufLen. // Returns the number of bytes read. int Buffer::ReadNextStreamChunk() { int free = bufCapacity - bufLen; if (free == 0) { // in the case of a growing input stream // we can neither seek in the stream, nor can we // foresee the maximum length, thus we must adapt // the buffer size on demand. bufCapacity = bufLen * 2; unsigned char *newBuf = new unsigned char[bufCapacity]; memcpy(newBuf, buf, bufLen*sizeof(unsigned char)); delete [] buf; buf = newBuf; free = bufLen; } int read = fread(buf + bufLen, sizeof(unsigned char), free, stream); if (read > 0) { fileLen = bufLen = (bufLen + read); return read; } // end of stream reached return 0; } bool Buffer::CanSeek() { return (stream != NULL) && (ftell(stream) != -1); } int UTF8Buffer::Read() { int ch; do { ch = Buffer::Read(); // until we find a utf8 start (0xxxxxxx or 11xxxxxx) } while ((ch >= 128) && ((ch & 0xC0) != 0xC0) && (ch != EoF)); if (ch < 128 || ch == EoF) { // nothing to do, first 127 chars are the same in ascii and utf8 // 0xxxxxxx or end of file character } else if ((ch & 0xF0) == 0xF0) { // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx int c1 = ch & 0x07; ch = Buffer::Read(); int c2 = ch & 0x3F; ch = Buffer::Read(); int c3 = ch & 0x3F; ch = Buffer::Read(); int c4 = ch & 0x3F; ch = (((((c1 << 6) | c2) << 6) | c3) << 6) | c4; } else if ((ch & 0xE0) == 0xE0) { // 1110xxxx 10xxxxxx 10xxxxxx int c1 = ch & 0x0F; ch = Buffer::Read(); int c2 = ch & 0x3F; ch = Buffer::Read(); int c3 = ch & 0x3F; ch = (((c1 << 6) | c2) << 6) | c3; } else if ((ch & 0xC0) == 0xC0) { // 110xxxxx 10xxxxxx int c1 = ch & 0x1F; ch = Buffer::Read(); int c2 = ch & 0x3F; ch = (c1 << 6) | c2; } return ch; } Scanner::Scanner(const unsigned char* buf, int len) { buffer = new Buffer(buf, len); Init(); } Scanner::Scanner(const wchar_t* fileName) { FILE* stream; char *chFileName = coco_string_create_char(fileName); if ((stream = fopen(chFileName, "rb")) == NULL) { wprintf(L"--- Cannot open file %ls\n", fileName); exit(1); } coco_string_delete(chFileName); buffer = new Buffer(stream, false); Init(); } Scanner::Scanner(FILE* s) { buffer = new Buffer(s, true); Init(); } Scanner::~Scanner() { char* cur = (char*) firstHeap; while(cur != NULL) { cur = *(char**) (cur + COCO_HEAP_BLOCK_SIZE); free(firstHeap); firstHeap = cur; } delete [] tval; delete buffer; } void Scanner::Init() { EOL = '\n'; eofSym = 0; - maxT = 36; - noSym = 36; + maxT = 48; + noSym = 48; int i; for (i = 65; i <= 90; ++i) start.set(i, 1); for (i = 97; i <= 122; ++i) start.set(i, 1); for (i = 48; i <= 57; ++i) start.set(i, 2); start.set(34, 3); start.set(40, 5); start.set(41, 6); start.set(91, 7); start.set(93, 8); - start.set(61, 9); - start.set(45, 21); - start.set(58, 11); - start.set(44, 12); - start.set(59, 13); + start.set(61, 11); + start.set(45, 24); + start.set(58, 12); + start.set(44, 13); start.set(123, 14); - start.set(125, 15); - start.set(43, 16); - start.set(42, 17); - start.set(47, 18); - start.set(60, 19); - start.set(62, 20); + start.set(59, 15); + start.set(125, 16); + start.set(46, 17); + start.set(43, 19); + start.set(42, 20); + start.set(47, 21); + start.set(60, 22); + start.set(62, 23); start.set(Buffer::EoF, -1); - keywords.set(L"function", 10); - keywords.set(L"string", 13); - keywords.set(L"int", 14); - keywords.set(L"num", 15); - keywords.set(L"float", 16); - keywords.set(L"bool", 17); - keywords.set(L"loop", 21); - keywords.set(L"map", 22); - keywords.set(L"assert", 24); - keywords.set(L"require", 25); - keywords.set(L"rule", 26); - keywords.set(L"case", 27); - keywords.set(L"variable", 28); - keywords.set(L"warning", 29); - keywords.set(L"message", 30); + keywords.set(L"function", 11); + keywords.set(L"string", 14); + keywords.set(L"int", 15); + keywords.set(L"num", 16); + keywords.set(L"float", 17); + keywords.set(L"bool", 18); + keywords.set(L"if", 22); + keywords.set(L"else", 23); + keywords.set(L"loop", 24); + keywords.set(L"map", 25); + keywords.set(L"fold", 26); + keywords.set(L"import", 27); + keywords.set(L"raw", 28); + keywords.set(L"pass", 29); + keywords.set(L"operator", 30); + keywords.set(L"list_range", 31); + keywords.set(L"list", 32); + keywords.set(L"index", 33); + keywords.set(L"assert", 35); + keywords.set(L"require", 36); + keywords.set(L"rule", 37); + keywords.set(L"case", 38); + keywords.set(L"variable", 39); + keywords.set(L"warning", 40); + keywords.set(L"message", 41); tvalLength = 128; tval = new wchar_t[tvalLength]; // text of current token // COCO_HEAP_BLOCK_SIZE byte heap + pointer to next heap block heap = malloc(COCO_HEAP_BLOCK_SIZE + sizeof(void*)); firstHeap = heap; heapEnd = (void**) (((char*) heap) + COCO_HEAP_BLOCK_SIZE); *heapEnd = 0; heapTop = heap; if (sizeof(Token) > COCO_HEAP_BLOCK_SIZE) { wprintf(L"--- Too small COCO_HEAP_BLOCK_SIZE\n"); exit(1); } pos = -1; line = 1; col = 0; charPos = -1; oldEols = 0; NextCh(); if (ch == 0xEF) { // check optional byte order mark for UTF-8 NextCh(); int ch1 = ch; NextCh(); int ch2 = ch; if (ch1 != 0xBB || ch2 != 0xBF) { wprintf(L"Illegal byte order mark at start of file"); exit(1); } Buffer *oldBuf = buffer; buffer = new UTF8Buffer(buffer); col = 0; charPos = -1; delete oldBuf; oldBuf = NULL; NextCh(); } pt = tokens = CreateToken(); // first token is a dummy } void Scanner::NextCh() { if (oldEols > 0) { ch = EOL; oldEols--; } else { pos = buffer->GetPos(); // buffer reads unicode chars, if UTF8 has been detected ch = buffer->Read(); col++; charPos++; // replace isolated '\r' by '\n' in order to make // eol handling uniform across Windows, Unix and Mac if (ch == L'\r' && buffer->Peek() != L'\n') ch = EOL; if (ch == EOL) { line++; col = 0; } } } void Scanner::AddCh() { if (tlen >= tvalLength) { tvalLength *= 2; wchar_t *newBuf = new wchar_t[tvalLength]; memcpy(newBuf, tval, tlen*sizeof(wchar_t)); delete [] tval; tval = newBuf; } if (ch != Buffer::EoF) { tval[tlen++] = ch; NextCh(); } } bool Scanner::Comment0() { int level = 1, pos0 = pos, line0 = line, col0 = col, charPos0 = charPos; NextCh(); if (ch == L'/') { NextCh(); for(;;) { if (ch == 10) { level--; if (level == 0) { oldEols = line - line0; NextCh(); return true; } NextCh(); } else if (ch == buffer->EoF) return false; else NextCh(); } } else { buffer->SetPos(pos0); NextCh(); line = line0; col = col0; charPos = charPos0; } return false; } bool Scanner::Comment1() { int level = 1, pos0 = pos, line0 = line, col0 = col, charPos0 = charPos; NextCh(); if (ch == L'*') { NextCh(); for(;;) { if (ch == L'*') { NextCh(); if (ch == L'/') { level--; if (level == 0) { oldEols = line - line0; NextCh(); return true; } NextCh(); } } else if (ch == L'/') { NextCh(); if (ch == L'*') { level++; NextCh(); } } else if (ch == buffer->EoF) return false; else NextCh(); } } else { buffer->SetPos(pos0); NextCh(); line = line0; col = col0; charPos = charPos0; } return false; } void Scanner::CreateHeapBlock() { void* newHeap; char* cur = (char*) firstHeap; while(((char*) tokens < cur) || ((char*) tokens > (cur + COCO_HEAP_BLOCK_SIZE))) { cur = *((char**) (cur + COCO_HEAP_BLOCK_SIZE)); free(firstHeap); firstHeap = cur; } // COCO_HEAP_BLOCK_SIZE byte heap + pointer to next heap block newHeap = malloc(COCO_HEAP_BLOCK_SIZE + sizeof(void*)); *heapEnd = newHeap; heapEnd = (void**) (((char*) newHeap) + COCO_HEAP_BLOCK_SIZE); *heapEnd = 0; heap = newHeap; heapTop = heap; } Token* Scanner::CreateToken() { Token *t; if (((char*) heapTop + (int) sizeof(Token)) >= (char*) heapEnd) { CreateHeapBlock(); } t = (Token*) heapTop; heapTop = (void*) ((char*) heapTop + sizeof(Token)); t->val = NULL; t->next = NULL; return t; } void Scanner::AppendVal(Token *t) { int reqMem = (tlen + 1) * sizeof(wchar_t); if (((char*) heapTop + reqMem) >= (char*) heapEnd) { if (reqMem > COCO_HEAP_BLOCK_SIZE) { wprintf(L"--- Too long token value\n"); exit(1); } CreateHeapBlock(); } t->val = (wchar_t*) heapTop; heapTop = (void*) ((char*) heapTop + reqMem); wcsncpy(t->val, tval, tlen); t->val[tlen] = L'\0'; } Token* Scanner::NextToken() { while (ch == ' ' || (ch >= 9 && ch <= 10) || ch == 13 ) NextCh(); if ((ch == L'/' && Comment0()) || (ch == L'/' && Comment1())) return NextToken(); int recKind = noSym; int recEnd = pos; t = CreateToken(); t->pos = pos; t->col = col; t->line = line; t->charPos = charPos; int state = start.state(ch); tlen = 0; AddCh(); switch (state) { case -1: { t->kind = eofSym; break; } // NextCh already done case 0: { case_0: if (recKind != noSym) { tlen = recEnd - t->pos; SetScannerBehindT(); } t->kind = recKind; break; } // NextCh already done case 1: case_1: recEnd = pos; recKind = 1; if ((ch >= L'0' && ch <= L'9') || (ch >= L'A' && ch <= L'Z') || ch == L'_' || (ch >= L'a' && ch <= L'z')) {AddCh(); goto case_1;} else {t->kind = 1; wchar_t *literal = coco_string_create(tval, 0, tlen); t->kind = keywords.get(literal, t->kind); coco_string_delete(literal); break;} case 2: case_2: recEnd = pos; recKind = 2; if ((ch >= L'0' && ch <= L'9')) {AddCh(); goto case_2;} else {t->kind = 2; break;} case 3: case_3: if (ch <= L'!' || (ch >= L'#' && ch <= 65535)) {AddCh(); goto case_3;} else if (ch == L'"') {AddCh(); goto case_4;} else {goto case_0;} case 4: case_4: {t->kind = 3; break;} case 5: {t->kind = 4; break;} case 6: {t->kind = 5; break;} case 7: {t->kind = 6; break;} case 8: {t->kind = 7; break;} case 9: + case_9: {t->kind = 8; break;} case 10: case_10: - {t->kind = 9; break;} + {t->kind = 10; break;} case 11: - {t->kind = 11; break;} + recEnd = pos; recKind = 9; + if (ch == L'=') {AddCh(); goto case_9;} + else {t->kind = 9; break;} case 12: {t->kind = 12; break;} case 13: - {t->kind = 18; break;} + {t->kind = 13; break;} case 14: {t->kind = 19; break;} case 15: {t->kind = 20; break;} case 16: - {t->kind = 31; break;} + {t->kind = 21; break;} case 17: - {t->kind = 32; break;} + if (ch == L'.') {AddCh(); goto case_18;} + else {goto case_0;} case 18: - {t->kind = 33; break;} + case_18: + {t->kind = 42; break;} case 19: - {t->kind = 34; break;} + {t->kind = 43; break;} case 20: - {t->kind = 35; break;} + {t->kind = 44; break;} case 21: - recEnd = pos; recKind = 23; + {t->kind = 45; break;} + case 22: + {t->kind = 46; break;} + case 23: + {t->kind = 47; break;} + case 24: + recEnd = pos; recKind = 34; if (ch == L'>') {AddCh(); goto case_10;} - else {t->kind = 23; break;} + else {t->kind = 34; break;} } AppendVal(t); return t; } void Scanner::SetScannerBehindT() { buffer->SetPos(t->pos); NextCh(); line = t->line; col = t->col; charPos = t->charPos; for (int i = 0; i < tlen; i++) NextCh(); } // get the next token (possibly a token already seen during peeking) Token* Scanner::Scan() { if (tokens->next == NULL) { return pt = tokens = NextToken(); } else { pt = tokens = tokens->next; return tokens; } } // peek for the next token, ignore pragmas Token* Scanner::Peek() { do { if (pt->next == NULL) { pt->next = NextToken(); } pt = pt->next; } while (pt->kind > maxT); // skip pragmas return pt; } // make sure that peeking starts at the current scan position void Scanner::ResetPeek() { pt = tokens; } diff --git a/coco/xreate.ATG b/coco/xreate.ATG index 8a7ea6e..dab9e71 100644 --- a/coco/xreate.ATG +++ b/coco/xreate.ATG @@ -1,242 +1,293 @@ #include "ast.h" #include using namespace xreate; using namespace std; COMPILER Xreate -xreate::AST root; // current program unit (procedure or main program) + xreate::AST root; // current program unit bool checkParametersList() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _lparen; } bool checkInfix() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _ident; } bool checkIndex() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _lbrack; } bool checkAssignment() { scanner->ResetPeek(); Token* x = scanner->Peek(); return la->kind == _ident && x->kind == _assign; } CHARACTERS letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz". any = ANY - '"'. digit = "0123456789". cr = '\r'. lf = '\n'. tab = '\t'. TOKENS ident = letter {letter | digit | '_'}. number = digit {digit}. string = '"' { any } '"'. lparen = '('. rparen = ')'. lbrack = '['. rbrack = ']'. + equal = "==". assign = '='. implic = '-' '>'. COMMENTS FROM "/*" TO "*/" NESTED COMMENTS FROM "//" TO lf IGNORE cr + lf + tab PRODUCTIONS -Xreate = { ( FDecl | RuleDecl ) }. +Xreate = { ( FDecl | RuleDecl | PassData | Imprt) }. Ident = ident (. name = t->val; .). FDecl<> = (. std::wstring fname; std::wstring varname; TypeAnnotation typIn; TypeAnnotation typOut; .) -Ident assign "function" ':' (. Function f = Function(fname); .) -( Type (. f.setReturnType(typOut); .) -| '(' [Ident ':' Type (. f.addArg(std::move(varname), move(typIn)); .) -{',' Ident ':' Type (. f.addArg(std::move(varname), move(typIn));.) -}] ')' implic Type (. f.setReturnType(typOut); .) -{',' FnTag } -) BDecl (. root.add(f); .) +Ident assign "function" ':' (. Function* f = new Function(fname); CodeScope* entry = f->getEntryScope(); .) +( Type (. f->setReturnType(typOut); .) +| '(' [Ident ':' Type (. f->addArg(std::move(varname), move(typIn)); .) +{',' Ident ':' Type (. f->addArg(std::move(varname), move(typIn));.) +}] ')' implic Type (. f->setReturnType(typOut); .) +{',' FnTag } +) BDecl (. root.add(f); .) . TypeTerm = ("string" | "int" | "num" | "float" | "bool") (. typ = Atom(t->val); .) . Type = (. TypeAnnotation typ2; TypeAtom typ3; .) ('[' Type ']' (. typ = TypeAnnotation(TypeOperator::LIST, {typ2}); .) | TypeTerm (. typ = TypeAnnotation(typ3); .) ) . -VDecl = (. std::wstring vname; Expression e; TypeAnnotation typ; .) +VDecl = (. std::wstring vname; Expression e; TypeAnnotation typ; .) Ident assign (ListLiteral ':' Type -| LoopDecl ';' +| LoopDecl +| IfDecl | Expr ':' Type -) (. f.addDeclaration(move(vname), move(typ), move(e)); .). +) (. f->addDeclaration(move(vname), move(typ), move(e)); .). -BDecl = (. Expression body; .) +BDecl = (. Expression body; .) '{' { ( IF(checkAssignment()) VDecl ';' | TagsDecl ';' - | Expr ';' (. scope.setBody(body); .) + | Expr ';' (. scope->setBody(body); .) )} '}'. -LoopDecl = (. std::wstring varIn, varEl; TypeAnnotation typEl; CodeScope block; .) - - "loop" "map" '(' Ident implic Ident ':' Type ')' ':' Type BDecl - (. e = Expression(Operator::LOOP, {Expression(Atom(varIn))}); e.addBindings({Atom(varEl)}); - block.addArg(Atom(varEl), move(typEl)); e.addBlock(move(block)); .) +IfDecl = (. Expression cond; ManagedScpPtr blockTrue = root.add(new xreate::CodeScope(outer)); ManagedScpPtr blockFalse = root.add(new xreate::CodeScope(outer)); + TypeAnnotation typIf; .) +"if" '(' Expr ')' ':' Type BDecl<&*blockTrue> "else" BDecl<&*blockFalse> +(. e = Expression(Operator::IF, {cond}); e.addBlock(blockTrue); e.addBlock(blockFalse); .) . +LoopDecl = + (. std::wstring varIn, varEl, varAcc; TypeAnnotation typEl, typAcc; Expression eAcc; + ManagedScpPtr block = root.add(new xreate::CodeScope(f)); .) + "loop" + ("map" '(' Ident implic Ident ':' Type ')' ':' Type BDecl<&*block> + (. e = Expression(Operator::MAP, {Expression(Atom(varIn))}); + e.addBindings({Atom(varEl)}); + block->addArg(Atom(varEl), move(typEl)); + e.addBlock(block); .) + |"fold" '(' Ident implic Ident ':' Type ',' Expr implic Ident ':' Type ')' ':' Type BDecl<&*block> + (. e = Expression(Operator::FOLD, {Expression(Atom(varIn)), eAcc}); + e.addBindings({Atom(varEl), Atom(varAcc)}); + block->addArg(Atom(varEl), move(typEl)); + block->addArg(Atom(varAcc), move(typAcc)); + e.addBlock(block); + .) +). + /*============================ METAPROGRAMMING ===============================*/ -TagsDecl = (. Expression tag; TagModifier mod = TagModifier::NONE; .) +Imprt<> = +"import" "raw" '(' string (. root.__rawImports.push_back(Atom(t->val).get()); .) +')' ';'. + +PassData<> = +"pass" '(' ident ')' '{' { InDecl } '}' . + +InDecl = (.Operator op; Expression tag; + Expression scheme; + std::vector& tags = scheme.operands; + tags.push_back(Expression()); /* return value */ .) +"operator" InAlias ':' '(' (.scheme.setOp(op); .) +[ + MetaSimpExpr (. tags.push_back(tag); .) + { + ',' MetaSimpExpr (. tags.push_back(tag); .) + } +] ')' [ implic MetaSimpExpr (. tags[0] = tag; .) + ] (. root.addDFAData(move(scheme)); .) +';'. + +InAlias = +( + "map" (. op = Operator::MAP; .) + | "list_range" (. op = Operator::LIST_RANGE; .) + | "list" (. op = Operator::LIST; .) + | "fold" (. op = Operator::FOLD; .) + | "index" (. op = Operator::INDEX; .) +). + +TagsDecl = (. Expression tag; TagModifier mod = TagModifier::NONE; .) ':' { MetaSimpExpr ['-' TagMod] (. /*f.addTag(std::move(tag), mod); */ .) }. -FnTag = (. Expression tag; TagModifier mod = TagModifier::NONE; .) +FnTag = (. Expression tag; TagModifier mod = TagModifier::NONE; .) MetaSimpExpr -['-' TagMod] (. f.addTag(std::move(tag), mod); .). +['-' TagMod] (. f->addTag(std::move(tag), mod); .). TagMod = ( "assert" (. mod = TagModifier::ASSERT; .) | "require" (. mod = TagModifier::REQUIRE; .) ). RuleDecl<> = "rule" ':' (. RuleArguments args; RuleGuards guards; DomainAnnotation typ; std::wstring arg; .) '(' Ident ':' Domain (. args.add(arg, typ); .) {',' Ident ':'Domain (. args.add(arg, typ); .) } ')' ["case" RGuard {',' RGuard}] '{' RBody '}' . Domain = ( "function" (. dom = DomainAnnotation::FUNCTION; .) | "variable" (. dom = DomainAnnotation::VARIABLE; .) ). RGuard= (. Expression e; .) MetaExpr (. guards.add(std::move(e)); .). MetaExpr= (.Operator op; Expression e2; .) MetaExpr2 [MetaOp MetaExpr2 (. e = Expression(op, {e, e2}); .) ]. MetaExpr2= ( '(' MetaExpr ')' | MetaSimpExpr ). MetaSimpExpr= (. std::wstring i1, infix; Expression e2; .) ( '-' MetaSimpExpr (. e = Expression(Operator::NEG, {e2}); .) | IF(checkParametersList()) Ident (. e = Expression(Operator::CALL, {Expression(Atom(i1))}); .) '(' [ CalleeParams ] ')' | IF(checkInfix()) Ident Ident MetaSimpExpr (. e = Expression(Operator::CALL, {Expression(Atom(infix))}); e.addArg(Expression(Atom(i1))); e.addArg(std::move(e2)); .) | Ident (. e = Expression(Atom(i1)); .) ). RBody = (. Expression e; std::wstring msg; .) "warning" MetaExpr ["message" string (. msg = t->val; .) ] (. root.add(new RuleWarning(RuleArguments(args), RuleGuards(guards), std::move(e), Atom(msg))); .) . MetaOp< Operator& op> = implic (. op = Operator::IMPL; .) . -/*============================ Expressions ===============================*/ + /*============================ Expressions ===============================*/ // dublicates CalleeParams -ListLiteral = (. Expression e2; .) -'[' (. e.setOp(Operator::LIST); .) -[ Expr (. e.addArg(std::move(e2)); .) -{',' Expr (. e.addArg(std::move(e2)); .) -}] ']'. +ListLiteral = (. Expression eFrom, eTo; .) +'[' +[ Expr (. e.addArg(std::move(eFrom)); .) +(".." Expr (. e.addArg(std::move(eTo)); e.setOp(Operator::LIST_RANGE); .) + |{',' Expr (. e.addArg(std::move(eFrom)); .) +} (. e.setOp(Operator::LIST); .) +) ] ']'. Expr< Expression& e> (. Operator op; Expression e2; .) = SimExpr< e> [ RelOp< op> SimExpr< e2> (. e = Expression(op, {e, e2}); .) ]. SimExpr< Expression& e> (. Operator op; Expression e2; .) = Term< e> { AddOp< op> Term< e2> (. e = Expression(op, {e, e2});.) }. Term< Expression& e> (. Operator op; Expression e2; .) = Factor< e> { MulOp< op> Factor< e2> (. e = Expression(op, {e, e2}); .) }. Factor< Expression& e> (. std::wstring name;.) = (IF (checkParametersList()) Ident< name> (. e = Expression(Operator::CALL, {Atom(name)}); .) '(' [CalleeParams] ')' - |IF (checkIndex()) Ident (. e = Expression(). e.setOp(Operator::INDEX); e.addArg(Atom(name)}); .) + |IF (checkIndex()) Ident (. e = Expression(Operator::INDEX, {Atom(name)}); .) lbrack CalleeParams rbrack | Ident< name> (. e = Expression(Atom(name)); .) | number (. e = Expression(Atom(t->val)); .) | '-' Factor< e> (. e = Expression(Operator::NEG, {e}); .) | '(' Expr ')' ). CalleeParams = (. Expression e2; .) Expr (. e.addArg(std::move(e2)); .) {',' Expr (. e.addArg(std::move(e2)); .) }. AddOp< Operator& op> = (. op = Operator::ADD; .) ( '+' | '-' (. op = Operator::SUB; .) ). MulOp< Operator& op> = (. op = Operator::MUL; .) ( '*' | '/' (. op = Operator::DIV; .) ). RelOp< Operator& op> = (. op = Operator::EQU; .) - ( '=' '=' + ( equal | '<' (. op = Operator::LSS; .) | '>' (. op = Operator::GTR; .) ). END Xreate. diff --git a/core/containers.lp b/core/containers.lp new file mode 100644 index 0000000..16b5432 --- /dev/null +++ b/core/containers.lp @@ -0,0 +1,44 @@ +%defines + impl(llvm_array; llvm_const_array; on_the_fly). + op(seqaccess). op(randaccess). + + relation(recommends; satisfied; unsupported). + relation_score(satisfied, 0). + relation_score(recommends, 1). + relation_score(unsupported, -1). + score(-1..1). + +%domain facts: + relation_op(seqaccess, on_the_fly, recommends). + relation_op(randaccess, llvm_const_array, recommends). + relation_op(randaccess, on_the_fly, unsupported). + +%dfa analysis: +% -- + +%compilation: +%-- + +%domain rules: + -impl_fulfill(OP, IMPL) :- relation_op(OP, IMPL, unsupported). + impl_fulfill(OP, IMPL, SCORE):- SCORE = #sum{SCORE1, (OP, IMPL, RL): relation_op(OP, IMPL, RL),relation_score(RL, SCORE1)} + ; op(OP); impl(IMPL); not -impl_fulfill(OP, IMPL). + + cluster_root(VAR) :- not dfa_connection(VAR, _, strong), v(VAR). + var_cluster(VAR0, VAR_TO) :- dfa_connection(VAR_TO, VAR0, strong), cluster_root(VAR0). + var_cluster(VAR0, VAR_TO2) :- dfa_connection(VAR_TO2, VAR_TO1, strong), var_cluster(VAR0, VAR_TO1). + var_cluster(VAR0, VAR0):- cluster_root(VAR0). + + -impl_fulfill_cluster(Var0, Impl) :- var_cluster(Var0, Var_Any); bind(Var_Any, op(Op)); -impl_fulfill(Op, Impl). + impl_fulfill_cluster(VAR0, IMPL, Score) :- + Score = #sum{SCORE, (OP, IMPL, VAR_ANY): impl_fulfill(OP, IMPL, SCORE), var_cluster(VAR0, VAR_ANY), bind(VAR_ANY, op(OP))} + ; bind(VAR0, impl(IMPL)); cluster_root(VAR0); not -impl_fulfill_cluster(VAR0, IMPL). + + + proto_cluster(V0, Vproto) :- cluster_root(V0); cluster_root(Vproto); var_cluster(Vproto, Vp); dfa_connection(V0, Vp, proto). + +%optimization +% #maximize {SCORE, (VAR0, IMPL) : impl_fulfill_cluster(VAR0, IMPL, SCORE)}. + +#show var_cluster/2. +#show impl_fulfill_cluster/3. diff --git a/cpp/CMakeLists.txt b/cpp/CMakeLists.txt index b93b617..16cb9ac 100644 --- a/cpp/CMakeLists.txt +++ b/cpp/CMakeLists.txt @@ -1,89 +1,94 @@ cmake_minimum_required(VERSION 2.8.11) project(xreate) find_package(LLVM REQUIRED CONFIG) find_package(Qt5Core) message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}") message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}") set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") set(SOURCE_FILES ./src/ast.cpp ./src/ast-compilation.cpp ./src/llvmlayer.cpp ./src/clasplayer.cpp - ./src/codeinstructions.cpp #./src/main.cpp ./tests/tests.cpp - ./src/pass/cfgpass.cpp ./src/pass/functiontagspass.cpp - ./src/pass/rulespass.cpp + ./src/passmanager.cpp + ./src/pass/abstractpass.cpp + ./src/pass/dfgpass.cpp + #./src/pass/cfgpass.cpp ./src/pass/functiontagspass.cpp + #./src/pass/rulespass.cpp ./src/pass/dfgpass.cpp + + src/instructions/instr-containers.cpp + src/query/containers.cpp src/attachments.cpp /opt/potassco/gringo-4.4.0-source/app/shared/src/clingocontrol.cc /opt/potassco/gringo-4.4.0-source/app/pyclingo/src/clingo_lib.cc ) set(COCO_PATH ${CMAKE_HOME_DIRECTORY}/../coco/) set(COCO_SOURCE_FILES ${COCO_PATH}/Parser.h ${COCO_PATH}/Scanner.h ${COCO_PATH}/Parser.cpp ${COCO_PATH}/Scanner.cpp ) set(POTASSCO_PATH "/opt/potassco/gringo-4.4.0-source") INCLUDE_DIRECTORIES(${COCO_PATH} ./src) INCLUDE_DIRECTORIES(${POTASSCO_PATH}/libgringo ${POTASSCO_PATH}/libclasp ${POTASSCO_PATH}/app/shared/include ${POTASSCO_PATH}/app/pyclingo/src ${POTASSCO_PATH}/libprogram_opts ) #execute_process(COMMAND ${COCO_PATH}/gen-xreate WORKING_DIRECTORY OUTPUT_VARIABLE COCO_OUTPUT) message(STATUS "COCO GRAMMAR BUILD STATUS:" ${COCO_OUTPUT}) include_directories(${LLVM_INCLUDE_DIRS}) add_definitions(${LLVM_DEFINITIONS}) -add_executable(xreate ${SOURCE_FILES} ${COCO_SOURCE_FILES}) +add_executable(xreate ${SOURCE_FILES} ${COCO_SOURCE_FILES} ) set(COCO_TARGET cocoTarget) add_custom_target(${COCO_TARGET} WORKING_DIRECTORY ${COCO_PATH} ) add_custom_command(TARGET ${COCO_TARGET} PRE_BUILD COMMAND ${COCO_PATH}/gen-xreate WORKING_DIRECTORY ${COCO_PATH} ) #add_dependencies(${PROJECT_NAME} ${COCO_TARGET}) llvm_map_components_to_libnames(llvm_libs support core irreader) message(STATUS "LLVM LIBS: " ${llvm_libs}) set (LIBCLASP_PATH ${POTASSCO_PATH}/build/debug) #find_library(LIBCLASP_LIBRARY_GRINGO NAMES gringo # HINTS ${LIBCLASP_PATH}) #find_library(LIBCLASP_LIBRARY_CLASP NAMES clasp # HINTS ${LIBCLASP_PATH}) set(LIBCLASP_LIBS ${LIBCLASP_PATH}/libclasp.a ${LIBCLASP_PATH}/libgringo.a ${LIBCLASP_PATH}/libprogram_opts.a ) message(STATUS ${LIBCLASP_LIBS}) target_link_libraries(xreate ${llvm_libs} pthread Qt5::Core ${LIBCLASP_LIBS}) add_definitions(-DWITH_THREADS=0) diff --git a/cpp/src/ast-compilation.cpp b/cpp/src/ast-compilation.cpp index 655a495..1bf4c97 100644 --- a/cpp/src/ast-compilation.cpp +++ b/cpp/src/ast-compilation.cpp @@ -1,185 +1,204 @@ #include -#include "codeinstructions.h" +#include +#include "query/containers.h" +#include "instructions/instr-containers.h" using namespace xreate; +using namespace std; llvm::Value * - CodeScope::compileExpression(const Expression &expr, LLVMLayer &l, const std::string * const hintRetVar) { - #define VARNAME(x) (hintRetVar==0 ? x: *hintRetVar) + CodeScope::compileExpression(const Expression &expr, LLVMLayer &l, std::string hintRetVar) { + #define VARNAME(x) (hintRetVar.empty()? x: hintRetVar) llvm::Value *left; llvm::Value *right; - switch (expr.__op) { + switch (expr.op) { case Operator::ADD: case Operator::SUB: case Operator::MUL: case Operator::DIV: case Operator::EQU: case Operator::LSS: case Operator::GTR: assert(expr.__state == Expression::COMPOUND); assert(expr.operands.size() == 2); left = compileExpression(expr.operands[0], l); right = compileExpression(expr.operands[1], l); break; default:; } - switch (expr.__op) { + switch (expr.op) { case Operator::ADD: return l.builder.CreateAdd(left, right, VARNAME("tmp_add")); break; case Operator::SUB: return l.builder.CreateSub(left, right, VARNAME("tmp_sub")); break; case Operator::MUL: return l.builder.CreateMul(left, right, VARNAME("tmp_mul")); break; case Operator::DIV: return l.builder.CreateSDiv(left, right, VARNAME("tmp_div")); break; case Operator::EQU: - left->getType()->dump(); - right->getType()->dump(); + left->dump(); + right->dump(); return l.builder.CreateICmpEQ(left, right, VARNAME("tmp_equ")); break; case Operator::LSS: return l.builder.CreateICmpSLT(left, right, VARNAME("tmp_lss")); break; case Operator::GTR: return l.builder.CreateICmpSGT(left, right, VARNAME("tmp_gtr")); break; case Operator::NEG: left = compileExpression(expr.operands[0], l); return l.builder.CreateNeg(left, VARNAME("tmp_neg")); break; case Operator::CALL: { assert(expr.__state == Expression::COMPOUND); const std::string &fname = expr.__valueS; - assert(l.ast->__indexFunctions.count(fname)); - const Function &calleeFunc = l.ast->getFunctionById(l.ast->__indexFunctions[fname]); - llvm::Function *callee = calleeFunc.__raw; + ManagedFnPtr calleeFunc = l.ast->findFunction(fname); + assert(calleeFunc.isValid()); + + llvm::Function *callee = calleeFunc->__raw; std::vector args; args.reserve(expr.operands.size() - 1); std::transform(expr.operands.begin(), expr.operands.end(), std::inserter(args, args.end()), [&l, this](const Expression &operand) { return compileExpression(operand, l); } ); return l.builder.CreateCall(callee, args, VARNAME("tmp_call")); } case Operator::LIST: { - return CodeInstruction(expr, l).compile(hintRetVar); + return containers::Instructions(this, &l).compileConstantArray(expr, VARNAME("list")); + }; + + case Operator::LIST_RANGE: + { + assert(false); //no compilation phase for a range list + // return InstructionList(this).compileConstantArray(expr, l, hintRetVar); + }; + + + + case Operator::MAP: + { + assert(expr.blocks.size()); + return containers::Instructions(this, &l).compileMapArray(expr, VARNAME("map")); + }; + + case Operator::FOLD: + { + return containers::Instructions(this, &l).compileFold(expr, VARNAME("fold")); }; case Operator::INDEX: { assert(expr.operands.size()); - const std::string &name = expr.__valueS; - llvm::Value* heap = findSymbol(name, l); - std::vector indexes; + const std::string &ident = expr.operands.begin()->getValueString(); + Symbol s = findSymbol(ident, l, true); - indexes.push_back(llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), 0)); - std::transform(expr.operands.begin(), expr.operands.end(), std::inserter(indexes, indexes.end()), - [this, &l] (const Expression& op){return compileExpression(op, l);} + std::vector indexes; + std::transform(++expr.operands.begin(), expr.operands.end(), std::inserter(indexes, indexes.end()), + [this, &l] (const Expression& op){return compileExpression(op, l);} ); - llvm::Value* result = l.builder.CreateGEP(heap, llvm::ArrayRef(indexes), VARNAME("tmp_el_of_arr")); - result->getType()->dump(); - return result; + return containers::Instructions(this, &l).compileIndex(s, indexes, VARNAME(string("el_") + ident)); }; case Operator::NONE: assert(expr.__state != Expression::COMPOUND); switch (expr.__state) { case Expression::IDENT: { const std::string &vname = expr.__valueS; - return findSymbol(vname, l); + const Symbol& var = findSymbol(vname, l, true); + return var.scope->__rawVars.at(var.identifier); } case Expression::NUMBER: int literal = expr.__valueD; return llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), literal); }; break; } assert(false); return 0; } llvm::Value * - CodeScope::compile(LLVMLayer &l, const std::string * const hintBlockName) { - if (hintBlockName) { - llvm::BasicBlock *block = llvm::BasicBlock::Create(llvm::getGlobalContext(), *hintBlockName, l.function); + CodeScope::compile(LLVMLayer &l, const std::string& hintBlockName) { + if (!hintBlockName.empty()) { + llvm::BasicBlock *block = llvm::BasicBlock::Create(llvm::getGlobalContext(), hintBlockName, l.context.function); l.builder.SetInsertPoint(block); } - return compileExpression(__body, l, 0); + return compileExpression(__body, l); } llvm::Function * Function::compile(LLVMLayer &l) { - std::vector types; - std::transform(__entry.__args.begin(), __entry.__args.end(), std::inserter(types, types.end()), + std::transform(__entry->__args.begin(), __entry->__args.end(), std::inserter(types, types.end()), [this](const std::string &arg)->llvm::Type* { - assert(__entry.__vartable.count(arg)); - VID argid = __entry.__vartable.at(arg); - assert(__entry.__definitions.count(argid)); - return __entry.__definitions.at(argid).toLLVMType(); + assert(__entry->__vartable.count(arg)); + VID argid = __entry->__vartable.at(arg); + assert(__entry->__definitions.count(argid)); + return __entry->__definitions.at(argid).toLLVMType(); }); - llvm::FunctionType *ft = llvm::FunctionType::get(__retType.toLLVMType(), types, false); + llvm::FunctionType *ft = llvm::FunctionType::get(__entry->__definitions[0].toLLVMType(), types, false); __raw = llvm::cast(l.module->getOrInsertFunction(__name, ft)); llvm::Function::arg_iterator fargsI = __raw->arg_begin(); - for (std::string &arg : __entry.__args) { - VID argid = __entry.__vartable[arg]; + for (std::string &arg : __entry->__args) { + VID argid = __entry->__vartable[arg]; - __entry.__rawVars[argid] = fargsI; + __entry->__rawVars[argid] = fargsI; fargsI->setName(arg); ++fargsI; } - l.function = __raw; + l.context.function = __raw; const std::string blockName = "entry"; - l.builder.CreateRet(__entry.compile(l, &blockName)); - l.function = nullptr; + l.builder.CreateRet(__entry->compile(l, blockName)); + l.context.function = nullptr; l.moveToGarbage(ft); return __raw; }; void AST::compile(LLVMLayer &layer) { layer.ast = this; layer.module = new llvm::Module(getModuleName(), llvm::getGlobalContext()); - int __debug_fcount = __functions.size(); - for (Function &f: __functions) { - llvm::Function *rawf = f.compile(layer); + for (Function* f: __functions) { + llvm::Function *rawf = f->compile(layer); } } \ No newline at end of file diff --git a/cpp/src/ast.cpp b/cpp/src/ast.cpp index 318aeaa..9051e77 100644 --- a/cpp/src/ast.cpp +++ b/cpp/src/ast.cpp @@ -1,384 +1,456 @@ #include "ast.h" #include #include #include #include using namespace std; namespace xreate{ TypeAnnotation::TypeAnnotation() { } TypeAnnotation::TypeAnnotation(const Atom &typ) : __value(typ.get()) { ; } TypeAnnotation::TypeAnnotation (TypePrimitive typ) : __value(typ) {} TypeAnnotation::TypeAnnotation(TypeOperator op, std::initializer_list operands) : __operator(op), __operands(operands) { } TypeAnnotation::TypeAnnotation (llvm_array_tag, TypePrimitive typ, int size) :TypeAnnotation(TypeOperator::LIST, {typ}) { __size=size; } /* TypeAnnotation (struct_tag, std::initializer_list) {} */ llvm::Type* TypeAnnotation::toLLVMType() { switch (__operator) { case TypeOperator::LIST: { assert(__operands.size()); TypeAnnotation elTy = __operands.at(0); return llvm::ArrayType::get(elTy.toLLVMType(), __size); } case TypeOperator::NONE: { switch (__value) { case TypePrimitive::Bool: return llvm::Type::getInt1Ty(llvm::getGlobalContext()); case TypePrimitive::Int: case TypePrimitive::i32: case TypePrimitive::Num: return llvm::Type::getInt32Ty(llvm::getGlobalContext()); case TypePrimitive::Float: return llvm::Type::getDoubleTy(llvm::getGlobalContext()); default: assert(false); } } default: assert(false); } assert(false); return nullptr; } Expression::Expression(const Atom& number) -: __state(NUMBER), __op(Operator::NONE), __valueD(number.get()) +: __state(NUMBER), op(Operator::NONE), __valueD(number.get()) { } Expression::Expression(const Atom &ident) - : __state(IDENT), __op(Operator::NONE), __valueS(ident.get()) + : __state(IDENT), op(Operator::NONE), __valueS(ident.get()) { } -Expression::Expression(const Operator &op, std::initializer_list params) - : __state(COMPOUND), __op(op) +Expression::Expression(const Operator &oprt, std::initializer_list params) + : __state(COMPOUND), op(oprt) { - if (op == Operator::CALL || op == Operator::INDEX) + if (op == Operator::CALL) { assert(params.size() > 0); Expression arg = *params.begin(); assert(arg.__state == Expression::IDENT); __valueS = std::move(arg.__valueS); return; } operands.insert(operands.end(), params); } void -Expression::setOp(Operator op) +Expression::setOp(Operator oprt) { - __op = op; + op = oprt; switch (op) { case Operator::NONE: __state = INVALID; break; default: __state = COMPOUND; break; } } void Expression::addArg(Expression &&arg) { operands.push_back(arg); } void Expression::addBindings(std::initializer_list> params) { - bindings.insert(bindings.end(), params); + std::transform(params.begin(), params.end(), std::inserter(bindings, bindings.end()), + [] (const Atom atom){ + return atom.get(); + }); } void -Expression::addBlock(CodeScope&& scope) +Expression::addBlock(ManagedScpPtr scope) { blocks.push_back(scope); } const std::vector& Expression::getOperands() const { return operands; } double Expression::getValueDouble() const { return __valueD; } const std::string& Expression::getValueString() const { return __valueS; } Expression::Expression() - : __op(Operator::NONE), __state(INVALID) + : op(Operator::NONE), __state(INVALID) {} AST::AST() { } void -AST::add(Function &f) +AST::addDFAData(Expression &&data) { + __dfadata.push_back(data); +} + +void +AST::add(Function* f) { __functions.push_back(f); - __indexFunctions[f.getName()] = __functions.size()-1; + __indexFunctions[f->getName()] = __functions.size()-1; } void AST::add(MetaRuleAbstract *r) { - __rules.push_back(unique_ptr(r)); + __rules.push_back(r); +} + +ManagedScpPtr +AST::add(CodeScope* scope) +{ + this->__scopes.push_back(scope); + return ManagedScpPtr(this->__scopes.size()-1, &this->__scopes); } std::string AST::getModuleName() { const std::string name = "moduleTest"; return name; } -FID -AST::getFunctionsCount() const -{ - return __functions.size(); -} - -const Function& -AST::getFunctionById(FID id)const +ManagedPtr +AST::findFunction(const std::string& name) { - assert(id>=0 && id < __functions.size()); - return __functions[id]; + assert (__indexFunctions.count(name)); + return ManagedPtr(__indexFunctions.at(name), &__functions); } void AST::run(LLVMLayer &l) { - llvm::PassManager PM; - PM.add(llvm::createPrintModulePass(llvm::outs())); + llvm::PassManager PM; + PM.addPass(llvm::PrintModulePass(llvm::outs(), "banner")); PM.run(*l.module); } + template<> + ManagedPtr + AST::begin() + {return ManagedPtr(0, &this->__functions);} + + template<> + ManagedPtr + AST::begin() + {return ManagedPtr(0, &this->__scopes);} + + template<> + ManagedPtr + AST::begin() + {return ManagedPtr(0, &this->__rules);} + Function::Function(const Atom& name) + : __entry(new CodeScope(0)) { __name = name.get(); } void Function::addTag(Expression&& tag, const TagModifier mod) { __tags.emplace_back(tag, mod); } const std::vector& Function::getAnnotations() const { return __tags; } -const CodeScope& +CodeScope* Function::getEntryScope() const { return __entry; } -CodeScope& -Function::getEntryScope() -{ - return __entry; -} - -void -Function::setEntryScope(CodeScope&& scope) -{ - __entry = scope; -} - void CodeScope::addArg(Atom && name, TypeAnnotation&& typ) { VID id = registerVar(std::move(const_cast(name.get())), std::move(typ)); __args.push_back(name.get()); } ; void Function::addArg(Atom && name, TypeAnnotation&& typ) { - __entry.addArg(move(name), move(typ)); + __entry->addArg(move(name), move(typ)); } void Function::setReturnType(const TypeAnnotation &rtyp) { - __retType = rtyp; + __entry->__definitions[0] = rtyp; } const std::string& Function::getName() const { return __name; } -CodeScope::CodeScope() -{ +CodeScope::CodeScope(CodeScope* parent) + :__parent(parent) +{} -} +CodeScope::~CodeScope() +{} VID CodeScope::registerVar(std::string&& name, TypeAnnotation &&typ) { __vartable[name] = ++__vCounter; __definitions[__vCounter] = typ; return __vCounter; } void CodeScope::bindArg(llvm::Value* var, std::string&& name) { assert(__vartable.count(name)); VID id = __vartable.at(name); __rawVars[id] = var; } void CodeScope::addDeclaration(const Atom &&name, TypeAnnotation &&typ, Expression&& body) { VID id = registerVar(std::move(const_cast(name.get())), move(typ)); __declarations[id] = body; } void CodeScope::setBody(const Expression &body) { __body = body; } -llvm::Value* -CodeScope::findSymbol(const std::string &name, LLVMLayer &l) +TypeAnnotation& +CodeScope::findDefinition(const Symbol& symbol) +{ + CodeScope* self = symbol.scope; + self->__definitions[symbol.identifier]; +} + +Symbol +CodeScope::findSymbol(const std::string &name, LLVMLayer &l, bool forceCompile) { //search var in current block if (__vartable.count(name)) { VID vId = __vartable.at(name); + Symbol result{vId, this}; + + if (!forceCompile) + { + return result; + } //search in already compiled vars if (__rawVars.count(vId)) { - return __rawVars.at(vId); + return result; } - //search in ordinary decls - if (__declarations.count(vId)){ - const Expression& e = __declarations.at(vId); - - llvm::Value* result = compileExpression(e, l, &name); - __rawVars[vId] = result; - return result; + if (!__declarations.count(vId)) { + //error: symbol is uncompiled scope arg + assert(false); } + + const Expression& e = __declarations.at(vId); + + __rawVars[vId] = compileExpression(e, l, name); + return result; } //search in parent scope if (__parent) { return __parent->findSymbol(name, l); } - //exception: Ident not found + //exception: Ident not found assert(false); } +bool +CodeScope:: hasDeclaration(const Symbol& symbol) +{ + CodeScope* self = symbol.scope; + return (self->__declarations.count(symbol.identifier)); +} + +llvm::Value* +CodeScope::compileExpression(const Symbol& s, LLVMLayer& l, std::string hintRetVar) +{ + CodeScope* self = s.scope; + + if (self->__rawVars.count(s.identifier)) + { + return self->__rawVars[s.identifier]; + } + + return self->__rawVars[s.identifier] = self->compileExpression(findDeclaration(s), l, hintRetVar); +} + +const Expression& +CodeScope::findDeclaration(const Symbol& symbol) +{ + CodeScope* self = symbol.scope; + + if (! self->__declarations.count(symbol.identifier)) + { + // no declaration exists + assert(false); + } + + return self->__declarations[symbol.identifier]; +} void RuleArguments::add(const Atom &arg, DomainAnnotation typ) { emplace_back(arg.get(), typ); } void RuleGuards::add(Expression&& e) { push_back(e); } MetaRuleAbstract:: MetaRuleAbstract(RuleArguments&& args, RuleGuards&& guards) : __args(std::move(args)), __guards(std::move(guards)) {} MetaRuleAbstract::~MetaRuleAbstract(){} RuleWarning:: RuleWarning(RuleArguments&& args, RuleGuards&& guards, Expression&& condition, Atom&& message) : MetaRuleAbstract(std::move(args), std::move(guards)), __condition(condition), __message(message.get()) {} RuleWarning::~RuleWarning(){} void RuleWarning::compile(ClaspLayer& layer) { layer.addRuleWarning(*this); } + +bool operator< (const Symbol& s1, const Symbol& s2) +{ + return (s1.scope < s2.scope) || (s1.scope==s2.scope && s1.identifier #include #include #include "llvmlayer.h" #include #include #include +#include +#include "attachments.h" namespace xreate { struct String_t{}; struct Identifier_t {}; struct Number_t {}; struct Type_t {}; template class Atom {}; template<> class Atom { public: Atom(const std::wstring& value) { char buffer[32]; wcstombs(buffer, value.c_str(), 32); __value = buffer; } + Atom(std::string && name): __value(name) {} const std::string& get() const{return __value; } private: std::string __value; }; template<> class Atom { public: Atom(wchar_t* value) { __value = wcstol(value, 0, 10); } + + Atom(int value) + : __value(value) + {} double get()const {return __value; } private: double __value; }; template<> class Atom { public: Atom(const std::wstring& value) - : __value(value.begin(), value.end()) - { - } + : __value(++value.begin(), --value.end()) + {} + const std::string& get() const {return __value; } private: std::string __value; }; enum class TypePrimitive {Bool, Int, Float, Num, String, i32}; template<> class Atom { public: Atom(wchar_t* value) { char buffer_[32]; wcstombs(buffer_, value, 32); std::string buffer(buffer_); if (buffer=="bool"){ __value = TypePrimitive ::Bool; } else if (buffer=="int") { __value = TypePrimitive::Int; } else if (buffer=="float") { __value = TypePrimitive::Float; } else if (buffer=="num") { __value = TypePrimitive::Num; } else if (buffer=="string") { __value = TypePrimitive::String; } } Atom() { } TypePrimitive get() const { return __value; } private: TypePrimitive __value; }; typedef Atom TypeAtom; enum class TypeOperator{NONE, LIST, STRUCT}; struct llvm_array_tag {}; struct struct_tag{}; const llvm_array_tag tag_array = llvm_array_tag(); const struct_tag tag_struct = struct_tag(); class TypeAnnotation { public: TypeAnnotation(); TypeAnnotation (const Atom& typ); TypeAnnotation (TypePrimitive typ); TypeAnnotation (llvm_array_tag, TypePrimitive typ, int size); TypeAnnotation (TypeOperator op, std::initializer_list operands); // TypeAnnotation (struct_tag, std::initializer_list); llvm::Type* toLLVMType(); -private: TypePrimitive __value; TypeOperator __operator = TypeOperator::NONE; std::vector __operands; int __size = 0; +private: + }; enum class Operator { -ADD, SUB, MUL, DIV, EQU, LSS, GTR, NEG, LIST, CALL, NONE, IMPL, LOOP, INDEX/* implication */ +ADD, SUB, MUL, DIV, EQU, LSS, GTR, NEG, LIST, LIST_RANGE, CALL, NONE, IMPL/* implication */, MAP, FOLD, INDEX, IF }; class Function; class AST; - class CodeScope; -class Expression +class MetaRuleAbstract; + +template +struct ManagedPtr +{ + ManagedPtr(){}; + + ManagedPtr(unsigned int id, const std::vector* storage) + : __id(id), __storage(storage) + {} + + Target& + operator*() const + { + return *(*__storage).at(__id); + } + + void operator=(const ManagedPtr& other) + { + __id = other.__id; + __storage = other.__storage; + } + + bool + operator == (const ManagedPtr& other) + { + return isValid() && (__id == other.__id); + } + + Target* + operator->() const noexcept + { + assert(isValid()); + return __storage->at(__id); + } + + inline bool isValid() const + { + return (__storage) && (0 <= __id) && (__id < __storage->size()); + } + + ManagedPtr& operator++() + { + ++__id; + return *this; + } + + inline unsigned int id() + { + return __id; + } + +private: + unsigned int __id =0; + const std::vector * __storage=0; +}; + +typedef ManagedPtr ManagedFnPtr; +typedef ManagedPtr ManagedScpPtr; +typedef ManagedPtr ManagedRulePtr; +const ManagedScpPtr NO_SCOPE = ManagedScpPtr(UINT_MAX, 0); + +struct Expression { friend class CodeScope; friend class ClaspLayer; friend class CFGPass; -public: - Expression(const Operator &op, std::initializer_list params); + + Expression(const Operator &oprt, std::initializer_list params); Expression(const Atom& ident); Expression(const Atom& number); Expression(); - void setOp(Operator op); + void setOp(Operator oprt); void addArg(Expression&& arg); void addBindings(std::initializer_list> params); - void addBlock(CodeScope&& scope); + void addBlock(ManagedScpPtr scope); const std::vector& getOperands() const; double getValueDouble() const; const std::string& getValueString() const; -private: - Operator __op ; + Operator op; + enum {INVALID, COMPOUND, IDENT, NUMBER, STRING} __state; + std::vector bindings; + std::list blocks; std::vector operands; - std::vector> bindings; - std::vector blocks; - +private: std::string __valueS; double __valueD; - - enum {INVALID, COMPOUND, IDENT, NUMBER, STRING} __state; }; typedef std::list ExpressionList; enum class TagModifier {NONE, ASSERT, REQUIRE}; enum class DomainAnnotation {FUNCTION, VARIABLE}; class RuleArguments: public std::vector> { public: void add(const Atom& name, DomainAnnotation typ); }; class RuleGuards: public std::vector { public: void add(Expression&& e); }; class ClaspLayer; +class LLVMLayer; + class MetaRuleAbstract { public: MetaRuleAbstract(RuleArguments&& args, RuleGuards&& guards); virtual ~MetaRuleAbstract(); virtual void compile(ClaspLayer& layer) =0; protected: RuleArguments __args; RuleGuards __guards; }; class RuleWarning: public MetaRuleAbstract { friend class ClaspLayer; public: RuleWarning(RuleArguments&& args, RuleGuards&& guards, Expression&& condition, Atom&& message); virtual void compile(ClaspLayer& layer); ~RuleWarning(); private: std::string __message; Expression __condition; }; typedef unsigned int VID; /* class Expression: ExpressionAbstract { friend class CFGPass; public: llvm::Value* compile(LLVMLayer& l, Function* f, std::string* hintRetVar=0) const; }; */ typedef std::pair VariableDefinition; typedef std::pair VariableDeclaration; typedef std::pair Tag; + +struct Symbol +{ + VID identifier; + CodeScope * scope; +}; + +bool operator< (const Symbol& s1, const Symbol& s2); +bool operator== (const Symbol& s1, const Symbol& s2); + class CodeScope { friend class Function; - friend class CFGPass; + friend class PassManager; public: - CodeScope(); + CodeScope(CodeScope* parent=0); void setBody(const Expression& body); void addDeclaration(const Atom &&name, TypeAnnotation &&typ, Expression&& body); void addArg(Atom && name, TypeAnnotation&& typ); void bindArg(llvm::Value* var, std::string&& name); - llvm::Value* compile(LLVMLayer &l, const std::string * const hintBlockName=0); - llvm::Value* findSymbol(const std::string &name, LLVMLayer &l); -private: - std::unordered_map __definitions; - std::unordered_map __declarations; - std::map __vartable; - std::vector __args; + //TODO exclude forceCompile partz + Symbol findSymbol(const std::string &name, LLVMLayer &l, bool forceCompile=false); + static const Expression& findDeclaration(const Symbol& symbol); + static TypeAnnotation& findDefinition(const Symbol& symbol); + static bool hasDeclaration(const Symbol& symbol); + static llvm::Value* compileExpression(const Symbol& s, LLVMLayer& l, std::string hintRetVar=""); + llvm::Value* compile(LLVMLayer &l, const std::string & hintBlockName=""); + - Expression __body; - VID __vCounter=0; + ~CodeScope(); + std::vector __args; + Expression __body; //TODO move __body to __declarations[0] std::map __rawVars; - CodeScope * __parent=0; + virtual llvm::Value* compileExpression(const Expression& expr, LLVMLayer& l, std::string hintRetVar=""); + SymbolAttachments attachments; +protected: + /** + * definition of return type have variable index Zero(0) + */ + //TODO move __definitions to SymbolsAttachments data + std::unordered_map __definitions; + std::unordered_map __declarations; + std::map __vartable; + VID __vCounter=1; + CodeScope* __parent; + std::list __storage; VID registerVar(std::string&& name, TypeAnnotation &&typ); - llvm::Value* compileExpression(const Expression& expr, LLVMLayer& l, const std::string* const hintRetVar = 0); + }; class Function { friend class Expression; friend class CodeScope; friend class AST; public: Function(const Atom& name); void addArg(Atom && name, TypeAnnotation&& typ); void addTag(Expression&& tag, const TagModifier mod); + void setReturnType(const TypeAnnotation& rtyp); const std::string& getName() const; llvm::Function* compile(LLVMLayer& l); const std::vector& getAnnotations() const; - const CodeScope& getEntryScope() const; - CodeScope& getEntryScope(); - void setEntryScope(CodeScope&& scope); + CodeScope* getEntryScope() const; private: - CodeScope __entry; + CodeScope* __entry; std::string __name; - TypeAnnotation __retType; std::vector __tags; llvm::Function* __raw; }; -typedef unsigned int FID; + + class AST { - friend class CodeScope; - friend class CFGPass; - friend class RulesPass; - public: AST(); - void add(Function& f); + void add(Function* f); void add(MetaRuleAbstract* r); + void addDFAData(Expression&& data); + ManagedScpPtr add(CodeScope* scope); void compile(LLVMLayer& l); void run(LLVMLayer& l); std::string getModuleName(); - FID getFunctionsCount() const; - const Function& getFunctionById(FID id) const; + ManagedPtr findFunction(const std::string& name); + + template + ManagedPtr begin(); + + std::list __dfadata; //TODO move to more appropriate place + std::list __rawImports; //TODO move to more appropriate place private: - std::list> __rules; - std::vector __functions; - std::map __indexFunctions; + std::vector __rules; + std::vector __functions; + std::vector __scopes; + + + std::map __indexFunctions; }; -} + template<> + ManagedPtr + AST::begin(); + template<> + ManagedPtr + AST::begin(); + + template<> + ManagedPtr + AST::begin(); +} #endif // AST_H diff --git a/cpp/src/attachments.cpp b/cpp/src/attachments.cpp new file mode 100644 index 0000000..d8c8af3 --- /dev/null +++ b/cpp/src/attachments.cpp @@ -0,0 +1,23 @@ +// +// Created by pgess on 3/15/15. +// + +#include "attachments.h" +#include "ast.h" + +void xreate::SymbolAttachments::put(xreate::Symbol const &symbol, unsigned int key, void *data) { + symbol.scope->attachments.__data[key].emplace(symbol.identifier, data); +} + +void *xreate::SymbolAttachments::get(xreate::Symbol const &symbol, unsigned int key, void *def) { + if (symbol.scope->attachments.__data[key].count(symbol.identifier)) + return symbol.scope->attachments.__data[key].at(symbol.identifier); + + return def; +} + +bool +xreate::SymbolAttachments::exists(const Symbol& symbol, unsigned int key) +{ + return symbol.scope->attachments.__data.count(key) && symbol.scope->attachments.__data.at(key).count(symbol.identifier); +} diff --git a/cpp/src/attachments.h b/cpp/src/attachments.h new file mode 100644 index 0000000..1b79036 --- /dev/null +++ b/cpp/src/attachments.h @@ -0,0 +1,109 @@ +// +// Created by pgess on 3/15/15. +// + +#ifndef _XREATE_ATTACHMENTS_H_ +#define _XREATE_ATTACHMENTS_H_ +#include + +namespace xreate +{ + //Attachemnt Tags: + struct IsDeclVisited{}; + + //Atachments dictionary + template + struct AttachmentsDictionary + { + // typedef void Data; + }; + + template<> + struct AttachmentsDictionary + { + typedef bool Data; + static const unsigned int key = 0; + }; + + + + class Symbol; + typedef unsigned int VID; + + class AttachmentsImpl + { + friend class SymbolAttachments; + + }; + + //TODO copy function to copy whole data from symbol to symbol: copy(sTo, sFrom); + class SymbolAttachments + { + public: + //TODO add specialization for pointers + template + static void put(const Symbol& symbol, typename AttachmentsDictionary::Data && data) + { + typedef typename AttachmentsDictionary::Data Typ; + const unsigned int key = AttachmentsDictionary::key; + Typ* ptr = new Typ(data); + + put(symbol, key, ptr); + } + + /* + template + using Tag2 = std::enable_if, Tag>:: + static void put(const Symbol& symbol, typename AttachmentsDictionary::Data && data) + { + typedef typename AttachmentsDictionary::Data Typ; + Typ* ptr = new Typ(data); + + AttachmentsImpl::put(symbol, ptr); + } + */ + + template + static typename AttachmentsDictionary::Data& get(const Symbol& symbol, typename AttachmentsDictionary::Data&& valueDefault) + { + typedef typename AttachmentsDictionary::Data Typ; + const unsigned int key = AttachmentsDictionary::key; + + Typ* def = new Typ(valueDefault); + Typ* result = static_cast (get(symbol, key, def)); + + if (result != def) delete def; + return *result; + } + + template + static typename AttachmentsDictionary::Data& get(const Symbol& symbol) + { + typedef typename AttachmentsDictionary::Data Typ; + const unsigned int key = AttachmentsDictionary::key; + + Typ* result = static_cast (get(symbol, key, nullptr)); + + assert(result != nullptr); // data not found for the symbol + return *result; + } + + template + static bool exists(const Symbol& symbol) + { + const unsigned int key = AttachmentsDictionary::key; + return exists(symbol, key); + } + + private: + typedef std::map Attachment; + std::map __data; + + static void put(const Symbol& symbol, unsigned int key, void* data); + static void* get(const Symbol& symbol, unsigned int key, void *def); + static bool exists(const Symbol& symbol, unsigned int key); + + }; +} + +#endif //_XREATE_ATTACHMENTS_H_ diff --git a/cpp/src/clasplayer.cpp b/cpp/src/clasplayer.cpp index 2faebad..b9707e8 100644 --- a/cpp/src/clasplayer.cpp +++ b/cpp/src/clasplayer.cpp @@ -1,305 +1,466 @@ #include "clasplayer.h" #include // for defining logic programs #include // unfounded set checkers #include // for enumerating answer sets #include #include #include #include using namespace std; namespace xreate { + + void + ClaspLayer::printWarnings(std::ostream& out) + { + const std::string warningTag = "warning"; + + auto warningsRange = __model.equal_range(warningTag); + + for (auto warning=warningsRange.first; warning!= warningsRange.second; ++warning) { + unsigned int warningId; + + Gringo::Value params; + std::tie(warningId, params) = parse(warning->second); + + cout << "Warning: " << __warnings.at(warningId) << " "; + params.print(out); + out< warnings; cout << "Model: " << endl; for (Gringo::Value atom : model.atoms(Gringo::Model::ATOMS)) { atom.print(cout); cout << endl; - auto hookI = __hooks.find(*(atom.name())); - - if (hookI != __hooks.end()) { - warnings.push_back(hookI->second); - } - } - - for (auto warning: warnings) { - cout << "Warning: " << warning << endl; + __model.emplace(*atom.name(), move(atom)); } } QStringList multiplyLists(std::list &&lists) { QStringList result = lists.front(); lists.pop_front(); for (QStringList &list: lists) { QStringList::const_iterator end = result.end(); for (QStringList::iterator expr1I = result.begin(); expr1I < end; ++expr1I) { if (list.size() == 0) continue; QStringList::const_iterator expr2I = list.begin(); for (int expr2No = 0, size = list.size() - 1; expr2No < size; ++expr2No, ++expr1I) result.append(QString("%1, %2").arg(*expr1I).arg(*expr2I)); *expr1I = QString("%1, %2").arg(*expr1I).arg(*expr2I); } } return result; } void - ClaspLayer::addCFGData(CFGraph &&graph) { + ClaspLayer::addCFAData(CFGraph &&graph) { ostream &cout = __partGeneral; - cout << endl << "%\t\tStatic analysis: CFG" << endl; + cout << endl << "%\t\tStatic analysis: CFA" << endl; - for (const std::pair &relation: graph.__relations) { + for (const std::pair &relation: graph.__relations) { const string &tagFrom = graph.__nodes.at(relation.first); const string &tagTo = graph.__nodes.at(relation.second); cout << (QString("call(%1, %2) .").arg(tagFrom.c_str()).arg(tagTo.c_str())).toStdString() << endl; } } + void + ClaspLayer::addDFAData(DFGraph &&graph) + { + dfgData = graph; + std::set symbols; + ostream &cout = __partGeneral; + + cout << endl << "%\t\tStatic analysis: DFA" << endl; + + std::vector>::iterator i1; + std::vector::iterator i2; + + for (i1=dfgData.__edges.begin(), i2 = dfgData.__data.begin(); i1!= dfgData.__edges.end(); ++i1, ++i2 ) + { + QString edgeData; + switch (*i2) + { + case DFGConnection::OPT: edgeData = "opt"; break; + case DFGConnection::STRONG: edgeData = "strong"; break; + case DFGConnection::PROTO: edgeData = "proto"; break; + } + + cout << QString("dfa_connection(%1, %2, %3).") + .arg(QString("(%1, %2)").arg(i1->first.identifier).arg(i1->first.scope)) + .arg(QString("(%1, %2)").arg(i1->second.identifier).arg(i1->second.scope)) + .arg(edgeData).toStdString() << endl; + + symbols.insert(i1->first); + symbols.insert(i1->second); + } + + for (const pair& tag: dfgData.__tags) + { + for (QString variant: compile(tag.second)) { + cout << QString("bind(%1, %2).") + .arg(QString("(%1, %2)").arg(tag.first.identifier).arg(tag.first.scope)) + .arg(variant).toStdString()< &tags) { ostream &cout = __partTags; cout << (QString("function(%1) .").arg(function.c_str())).toStdString() << std::endl; int tagsCount = 0; for (const Tag &tag: tags) { QStringList tagRaw = compile(tag.first); assert(tagRaw.size() == 1); cout << QString("tag(%1, %2).").arg(function.c_str()).arg(tagRaw.at(0)).toStdString() << endl; ++tagsCount; } if (tagsCount == 0) { cout << "%no tags at all" << endl; } } void ClaspLayer::addRuleWarning(const RuleWarning &rule) { //__partGeneral << rule << endl; QStringList domains; std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(domains, domains.begin()), [](const std::pair &argument) { - char *domain; + string domain; switch (argument.second) { case DomainAnnotation::FUNCTION: domain = "function"; break; case DomainAnnotation::VARIABLE: domain = "variable"; break; } - return QString("%1(%2)").arg(domain).arg(argument.first.c_str()); + return QString("%1(%2)").arg(domain.c_str()).arg(argument.first.c_str()); }); QStringList vars; std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(vars, vars.begin()), [](const std::pair &argument) { return argument.first.c_str(); }); std::list guardsRaw; std::transform(rule.__guards.begin(), rule.__guards.end(), std::inserter(guardsRaw, guardsRaw.begin()), [this](const Expression &guard) { return compile(guard); }); QStringList guards = multiplyLists(std::move(guardsRaw)); QStringList &&branches = compileNeg(rule.__condition); for (const QString &guardsJoined: guards) for (const QString &branch: branches) { - const std::string &&hook = registerHook(rule.__message); + unsigned int hook = registerWarning(string(rule.__message)); - QString result = QString("%1(%2):-%3, %4, %5.") - .arg(hook.c_str()) + QString result = QString("warning(%1, (%2)):- %3, %4, %5.") + .arg(hook) .arg(vars.join(", ")) .arg(branch) .arg(guardsJoined) .arg(domains.join(", ")); __partGeneral << result.toStdString() << endl; } } QStringList ClaspLayer::compile(const Expression &e) const { QStringList result; - switch (e.__op) { + switch (e.op) { case Operator::CALL: { assert(e.__state == Expression::COMPOUND); std::list operands; std::transform(e.operands.begin(), e.operands.end(), std::inserter(operands, operands.begin()), [this](const Expression &e) { return compile(e); }); QStringList &&operands_ = multiplyLists(std::move(operands)); result.append(QString("%1(%2)").arg(e.__valueS.c_str()).arg(operands_.join(", "))); break; } case Operator::NEG: { assert(e.operands.size() == 1); const Expression &op = e.operands.at(0); QStringList &&rawOp = compile(op); assert(rawOp.size() == 1); result.append(QString("not %1").arg(rawOp.at(0))); break; }; case Operator::NONE: { switch (e.__state) { case Expression::IDENT: result.append(QString(e.__valueS.c_str())); break; case Expression::NUMBER: result.append(QString::number(e.__valueD)); break; default: assert(true); } break; } } return result; } QStringList ClaspLayer::compileNeg(const Expression &e) const { QStringList result; - switch (e.__op) { + switch (e.op) { case Operator::IMPL: { assert(e.__state == Expression::COMPOUND); assert(e.operands.size() == 2); QStringList operands1 = compile(e.operands.at(0)); QStringList operands2 = compile(e.operands.at(1)); for (const auto &op1: operands1) for (const auto &op2: operands2) { result.append(QString("%1, not %2").arg(op1).arg(op2)); } break; } case Operator::NEG: { assert(e.operands.size() == 1); const Expression &op = e.operands.at(0); QStringList &&rawOp = compile(op); assert(rawOp.size() == 1); result.append(rawOp.at(0)); break; }; default: assert(true); } return result; } - std::string - ClaspLayer::registerHook(const std::string &message) { - static int i = 0; - std::string hookId = "hook" + std::to_string(++i); - __hooks.insert(make_pair(hookId, message)); + unsigned int + ClaspLayer::registerWarning(std::string &&message) { + static int warningId = 0; + __warnings.emplace(warningId, message); + return warningId++;; + } - return hookId; + void + ClaspLayer::addImports() { + ostream &out = __partGeneral; + + for (string fn: ast->__rawImports) + { + std::ifstream file(fn); + if (!file) continue; + + while(!file.eof()){ + string line; + std::getline(file, line); + out << line << endl; + } + } } void ClaspLayer::run() { + addImports(); + ostringstream program; program << __partTags.str() << __partGeneral.str(); cout << program.str() << endl; const char *argv[] = {nullptr, nullptr}; ClingoLib ctl(2, argv); //prg.add("p", ["t"], "q(t).") Gringo::FWStringVec vars{}; ctl.add("base", vars, program.str()); //prg.ground([("p", [2])]) Gringo::Control::GroundVec vals{std::make_pair("base", Gringo::FWValVec {})}; ctl.ground(vals, Gringo::Any()); //solve Gringo::Control::Assumptions as; Gringo::SolveResult result = ctl.solve(Gringo::Control::ModelHandler([&](Gringo::Model const &model) { return this->onModel(model); }), std::move(as)); if (result == Gringo::SolveResult::SAT) { cout << "SUCCESSFULLY" << endl; } else { cout << "UNSUCCESSFULLY" << endl; + } + + // invoke all query plugins to process clasp data + for (IQuery* q: __queries) + { + q->init(this); } } ClaspLayer::ClaspLayer() { } + std::pair + ClaspLayer::query(const std::string& atom) + { + return __model.equal_range(atom); + } + + + /* void AspOutPrinter::reportSolution(const Clasp::Solver&, const Clasp::Enumerator&, bool complete) { if (complete) std::cout << "No more models!" << std::endl; else std::cout << "More models possible!" << std::endl; } void AspOutPrinter::reportModel(const Clasp::Solver& s, const Clasp::Enumerator&) { std::cout << "Model " << s.stats.solve.models << ": \n"; // get the symbol table from the solver const Clasp::AtomIndex& symTab = *s.strategies().symTab; for (Clasp::AtomIndex::const_iterator it = symTab.begin(); it != symTab.end(); ++it) { // print each named atom that is true w.r.t the current assignment } std::cout << std::endl; } */ /***************************************** * CFGraph ***************************************** */ -void -CFGraph::addNode(FID function, std::string&& tag) -{ - __nodes.emplace(function, tag); -} + void + CFGraph::addNode(unsigned int function, std::string &&tag) { + __nodes.emplace(function, tag); + } -bool -CFGraph::existsNode(FID function) const -{ - return __nodes.count(function); -} + bool + CFGraph::existsNode(unsigned int function) const { + return __nodes.count(function); + } -void -CFGraph::addLink(FID nodeFrom, FID nodeTo) -{ - __relations.insert(std::make_pair(nodeFrom, nodeTo)); -} + void + CFGraph::addLink(unsigned int nodeFrom, unsigned int nodeTo) { + __relations.insert(std::make_pair(nodeFrom, nodeTo)); + } + + +/***************************************** + * DFGraph + ***************************************** + */ + bool + DFGraph::linkExists(const SymbolPacked& node1, const SymbolPacked& node2) + { + auto range = __outEdges.equal_range(node2); + + for(std::multimap::iterator edge = range.first; edge != range.second; ++edge) + { + if (__edges[edge->second].second == node1) + return true; + } + + return false; + } + + void + DFGraph::addLink(const SymbolPacked& nodeTo, const SymbolPacked& nodeFrom, DFGConnection link) { + if (!linkExists(nodeTo, nodeFrom)) + { + __edges.emplace_back(nodeTo, nodeFrom); + __data.push_back(link); + + EdgeId eid = __edges.size()-1; + __outEdges.emplace(nodeFrom, eid); + } + } + + void + DFGraph::addTag(const SymbolPacked &node, Expression &&tag) { + __tags.emplace(node, tag); + } + + SymbolPacked + DFGraph::pack(const Symbol& symbol, std::string hintSymbolName) + { + std::unordered_map::iterator pos + = __hash.emplace(symbol.scope, __hash.size()).first; + __hashedScopes.push_back(symbol.scope); + + SymbolPacked result; + result.scope = pos->second; + result.identifier = symbol.identifier; + } + + Symbol + DFGraph::unpack(const SymbolPacked& symbol) + { + return Symbol{symbol.identifier, __hashedScopes[symbol.scope]}; + }; + + bool SymbolPacked::isValid() const + { + return this->scope != SYMBOL_INVALID.scope && identifier != SYMBOL_INVALID.identifier; + } + + bool operator==(const SymbolPacked& s1, const SymbolPacked& s2) + { + return s1.identifier == s2.identifier && s1.scope == s2.scope; + } + + bool operator<(const SymbolPacked& s1, const SymbolPacked& s2) + { + return s1.scope < s2.scope || (s1.scope == s2.scope && s1.identifier < s2.identifier); + } + + void ClaspLayer::registerdQuery(IQuery *query) { + __queries.push_back(query); + } } \ No newline at end of file diff --git a/cpp/src/clasplayer.h b/cpp/src/clasplayer.h index fb2ca2c..3e883aa 100644 --- a/cpp/src/clasplayer.h +++ b/cpp/src/clasplayer.h @@ -1,52 +1,173 @@ #ifndef CLASPLAYER_H #define CLASPLAYER_H #include #include #include #include +#include namespace xreate { - class CFGraph; + class CFGraph { + friend class ClaspLayer; + + public: + void addNode(unsigned int function, std::string &&tag); + void addLink(unsigned int nodeFrom, unsigned int nodeTo); + bool existsNode(unsigned int function) const; + void print(std::ostream &cout) const; + + private: + std::map __relations; + std::map __nodes; + }; + + enum class DFGConnection{ + STRONG, OPT, PROTO}; + + + struct SymbolPacked + { + VID identifier; + unsigned int scope; + + bool isValid() const; + }; + + bool operator==(const SymbolPacked& s1, const SymbolPacked& s2); + bool operator<(const SymbolPacked& s1, const SymbolPacked& s2); + + const SymbolPacked SYMBOL_INVALID{UINT_MAX, UINT_MAX}; + + class DFGraph + { + friend class ClaspLayer; + public: + void addTag(const SymbolPacked& node, Expression&& tag); + void addLink(const SymbolPacked& nodeTo, const SymbolPacked& nodeFrom, DFGConnection link); + bool linkExists(const SymbolPacked& node1, const SymbolPacked& node2); + + SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName=""); + Symbol unpack(const SymbolPacked& symbol); + private: + typedef unsigned int EdgeId; + std::vector> __edges; + std::multimap __outEdges; + std::vector __data; + std::multimap __tags; + + std::unordered_map __hash; + std::vector __hashedScopes; + }; + + class IQuery + { + public: + virtual void init(ClaspLayer* clasp)=0; + virtual ~IQuery() {} + }; class ClaspLayer { public: AST *ast; + DFGraph dfgData; ClaspLayer(); + void registerdQuery(IQuery* query); void addFunctionTags(const std::string &function, const std::vector &tags); - void addCFGData(CFGraph &&graph); + void addCFAData(CFGraph &&graph); + void addDFAData(DFGraph &&graph); void addRuleWarning(const RuleWarning &rule); void run(); + template + static std::tuple parse(const Gringo::Value& atom); + + typedef std::multimap::const_iterator ModelIterator; + std::pair query(const std::string& atom); private: - std::map __hooks; + // all query plugins to process clasp data + std::list __queries; + std::multimap __model; + std::map __warnings; std::ostringstream __partTags; std::ostringstream __partGeneral; + void printWarnings(std::ostream& out); bool onModel(Gringo::Model const &model); QStringList compile(const Expression &e) const; QStringList compileNeg(const Expression &e) const; - std::string registerHook(const std::string &message); + unsigned int registerWarning(std::string &&message); + void addImports(); }; - class CFGraph { - friend class ClaspLayer; + template + struct ParseImplAtom { + static typ get(const Gringo::Value& atom) + { + return atom.num(); + } + }; - public: - void addNode(FID function, std::string &&tag); + template<> + struct ParseImplAtom { + static std::string get(const Gringo::Value& atom) + { + return *atom.string(); + }}; - void addLink(FID nodeFrom, FID nodeTo); + template<> + struct ParseImplAtom { + static SymbolPacked get(const Gringo::Value& atom) + { + auto result = ClaspLayer::parse(atom); + return SymbolPacked{std::get<0>(result), std::get<1>(result)}; + }}; - bool existsNode(FID function) const; + template<> + struct ParseImplAtom { + static Gringo::Value get(const Gringo::Value& atom) + { + return atom; + }}; - void print(std::ostream &cout) const; + template + struct Parse_Impl { + static void parse(Tuple& tup, Gringo::FWValVec::const_iterator arg) + { + const size_t tupleSize = std::tuple_size::value; + typedef typename std::tuple_element::type ElType; - private: - std::map __relations; - std::map __nodes; + ElType& el = std::get(tup); + + Gringo::Value atom = *arg; + el = ParseImplAtom::get(atom); + + Parse_Impl::parse(tup, ++arg); + } + }; + + template + struct Parse_Impl + { + static void parse(Tuple& tup, Gringo::FWValVec::const_iterator arg) + {} }; + + + template + std::tuple + ClaspLayer::parse(const Gringo::Value& atom) + { + typedef std::tuple Tuple; + Tuple tup; + Parse_Impl::value>::parse(tup, atom.args().begin()); + + return tup; + } + + } #endif diff --git a/cpp/src/codeinstructions.cpp b/cpp/src/codeinstructions.cpp deleted file mode 100644 index 837d8a5..0000000 --- a/cpp/src/codeinstructions.cpp +++ /dev/null @@ -1,86 +0,0 @@ -#include "codeinstructions.h" -#include "llvmlayer.h" -#include "ast.h" - -using namespace llvm; -namespace xreate { - llvm::Value* - InstructionMap::compileDefault(const std::string * const hintRetVar) { - - CodeScope body; - std::string varIn; - std::string varOut; - std::string varEl; - int size; - CodeScope *scopeOuter; - - llvm::IntegerType *i32Tag = (llvm::IntegerType*) TypeAnnotation(TypePrimitive::i32).toLLVMType(); - const std::string itLoopName = "it"; - - Value *vecIn = scopeOuter->findSymbol(varIn, llvm); - Value *vecOut = scopeOuter->findSymbol(varOut, llvm); - - llvm::IRBuilder<> &builder = llvm.builder; - - llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "loop", llvm.function); - llvm::BasicBlock *blockBeforeLoop = builder.GetInsertBlock(); - llvm::BasicBlock *blockAfterLoop = builder.GetInsertBlock(); - Value *cond1 = llvm.builder.CreateICmpEQ(0, ConstantInt::get((i32Tag), size)); - builder.CreateCondBr(cond1, blockAfterLoop, blockLoop); - - builder.SetInsertPoint(blockLoop); - llvm::PHINode *itLoop = builder.CreatePHI(i32Tag, 2, itLoopName); - itLoop->addIncoming(llvm::ConstantInt::get(i32Tag, 0), blockBeforeLoop); - - Value *pElIn = builder.CreateGEP(vecIn, ArrayRef(std::vector{ConstantInt::get(i32Tag, 0), itLoop})); - Value *pElOut = builder.CreateGEP(vecOut, ArrayRef(std::vector{ConstantInt::get(i32Tag, 0), itLoop})); - - Value *elIn = builder.CreateLoad(pElIn, varEl); - - body.bindArg(elIn, std::string(varEl)); - Value *elOut = body.compile(llvm); - - builder.CreateStore(elOut, pElOut); - Value *itNextLoop = builder.CreateAdd(itLoop, ConstantInt::get(i32Tag, 1)); - itLoop->addIncoming(itNextLoop, builder.GetInsertBlock()); - - Value *cond2 = llvm.builder.CreateICmpSLT(itNextLoop, ConstantInt::get(i32Tag, size)); - builder.CreateCondBr(cond2, blockLoop, blockAfterLoop); - - builder.SetInsertPoint(blockAfterLoop); - - return elOut; - } - - /* - void InstructionMap::compileComputation() { - - } - */ - - - InstructionList::InstructionList(const Expression& e, LLVMLayer& l) - : llvm(l), __data(e), __size(e.getOperands().size()) - { - } - - llvm::Value* - InstructionList::compileDefault(const std::string * const hintRetVar) { - ArrayType* typList = (ArrayType*) (TypeAnnotation(tag_array, TypePrimitive::i32, __size).toLLVMType()); - Type*typI32 = TypeAnnotation(TypePrimitive::i32).toLLVMType(); - - std::vector list; - list.reserve(__size); - - const std::vector operands = __data.getOperands(); - std::transform(operands.begin(), operands.end(), std::inserter(list, list.begin()), - [typI32](const Expression& e){return ConstantFP::get(typI32, e.getValueDouble());}); - - Value* listSource = ConstantArray::get(typList, ArrayRef(list)); - Value* listDest = llvm.builder.CreateAlloca(typList, ConstantFP::get(typI32, __size), *hintRetVar); - - llvm.builder.CreateMemCpy(listDest, listSource, __size, 16); - - return listDest; - } -} \ No newline at end of file diff --git a/cpp/src/codeinstructions.h b/cpp/src/codeinstructions.h deleted file mode 100644 index 09877fb..0000000 --- a/cpp/src/codeinstructions.h +++ /dev/null @@ -1,65 +0,0 @@ -#ifndef CODEINSTRUCTIONS_H -#define CODEINSTRUCTIONS_H - -#include "llvmlayer.h" -#include "ast.h" -#include - -namespace xreate { - -class InstructionMap -{ -public: - InstructionMap(const Expression& e, LLVMLayer& l); - llvm::Value* compileDefault(const std::string * const hintRetVar); - -private: - LLVMLayer& llvm; - const Expression& __data; -}; - -class InstructionList -{ -public: - InstructionList(const Expression& e, LLVMLayer& l); - llvm::Value* compileDefault(const std::string * const hintRetVar); - -private: - LLVMLayer& llvm; - int __size; - const Expression& __data; -}; - - - template - struct InstructionClasses {}; - - template<> - struct InstructionClasses { - typedef InstructionList base; - }; - - template<> - struct InstructionClasses { - typedef InstructionMap base; - }; - - template - class CodeInstruction: public InstructionClasses::base - { - typedef typename InstructionClasses::base InstructionImpl; - - public: - CodeInstruction(const Expression& e, LLVMLayer& l) - : InstructionImpl(e, l) - {} - - llvm::Value* compile(const std::string * const hintRetVar) - { - InstructionImpl::compileDefault(hintRetVar); - } - }; -} - - -#endif //CODEINSTRUCTIONS_H \ No newline at end of file diff --git a/cpp/src/instructions/instr-containers.cpp b/cpp/src/instructions/instr-containers.cpp new file mode 100644 index 0000000..bbfb330 --- /dev/null +++ b/cpp/src/instructions/instr-containers.cpp @@ -0,0 +1,276 @@ +#include "instr-containers.h" +#include "llvmlayer.h" +#include "ast.h" +#include "query/containers.h" + +using namespace std; +using namespace llvm; +using namespace xreate::containers; + +xreate::containers::Instructions::Instructions(CodeScope *current, LLVMLayer* layer) + : scope(current), llvm(layer), + tyNum (static_cast (TypeAnnotation(TypePrimitive::Num).toLLVMType())) +{} + +Value* +Instructions::compileIndex(const Symbol& dataSymbol, std::vector indexes, std::string ident) +{ + #define NAME(x) (ident.empty()? x : ident) + + const ImplementationData& info = containers::Query::queryImplementation(dataSymbol); + llvm::Value* data = dataSymbol.scope->__rawVars.at(dataSymbol.identifier); + + switch (info.impl) + { + case containers::LLVM_CONST_ARRAY: { + assert(indexes.size() == 1); + return llvm->builder.CreateExtractElement(data, indexes[0], NAME("el")); + } + + case containers::LLVM_ARRAY: { + indexes.insert(indexes.begin(), llvm::ConstantInt::get(tyNum, 0)); + Value *pEl = llvm->builder.CreateGEP(data, llvm::ArrayRef(indexes)); + return llvm->builder.CreateLoad(pEl, NAME("el")); + } + + default: + // non supported container implementation + assert(false); + } +} + +Value* +Instructions::compileGetElement(std::string varIn, Value* stateLoop, std::string ident) +{ + #define NAME(x) (ident.empty()? x : ident) + llvm::IRBuilder<> &builder = llvm->builder; + + const Symbol& symbolIn = scope->findSymbol(varIn, *llvm); + const Expression& exprIn = CodeScope::findDeclaration(symbolIn); + + if (exprIn.op == Operator::LIST_RANGE) + {return stateLoop; } + + if (exprIn.op == Operator::LIST) + { + llvm::Value* dataIn = CodeScope::compileExpression(symbolIn, *llvm); + return compileIndex(symbolIn, vector{stateLoop}, NAME(string("el_") + varIn)); + } + + if(exprIn.op == Operator::MAP) + { + assert(exprIn.getOperands().size()==1); + assert(exprIn.bindings.size()); + assert(exprIn.blocks.size()); + + const ManagedScpPtr& scopeLoop = exprIn.blocks.front(); + const std::string& varIn2 = exprIn.getOperands()[0].getValueString(); + std::string varEl = exprIn.bindings[0]; + + Value* elIn = compileGetElement(varIn2, stateLoop, varEl); + scopeLoop->bindArg(elIn, move(varEl)); + return scopeLoop->compileExpression(scopeLoop->__body, *llvm, NAME(string("el_") + varIn)); + } + + assert(false); + + + + /* + switch(implIn.impl) + { + case containers::LLVM_ARRAY: + case containers::LLVM_CONST_ARRAY: + stateLoopNext = builder.CreateAdd(stateLoop, ConstantInt::get(tyNum, 1)); + + + case containers::ON_THE_FLY: + stateLoopNext = compileIndexLoad(stateLoad); + } + */ + +} + +llvm::Value* +Instructions::compileMapArray(const Expression &expr, const std::string ident) { + #define NAME(x) (ident.empty()? x : ident) + + //initialization + std::string varIn = expr.getOperands()[0].getValueString(); + Symbol symbolIn = scope->findSymbol(varIn, *llvm); + + containers::ImplementationData implIn = containers::Query::queryImplementation(symbolIn); // impl of input list + unsigned int size = implIn.size; + ManagedScpPtr scopeLoop = expr.blocks.front(); + std::string varEl = scopeLoop->__args[0]; + + llvm::Value *rangeFrom = ConstantInt::get((tyNum), 0); + llvm::Value *rangeTo = ConstantInt::get((tyNum), size-1); + + //definitions + ArrayType* tyNumArray = (ArrayType*) (TypeAnnotation(tag_array, TypePrimitive::Num, size).toLLVMType()); + llvm::IRBuilder<> &builder = llvm->builder; + + llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "loop", llvm->context.function); + llvm::BasicBlock *blockBeforeLoop = builder.GetInsertBlock(); + llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postloop", llvm->context.function); + Value* dataOut = llvm->builder.CreateAlloca(tyNumArray, ConstantInt::get(tyNum, size), NAME("map")); + + // * initial check + Value* condBefore = builder.CreateICmpSLE(rangeFrom, rangeTo); + builder.CreateCondBr(condBefore, blockLoop, blockAfterLoop); + + // create PHI: + builder.SetInsertPoint(blockLoop); + llvm::PHINode *stateLoop = builder.CreatePHI(tyNum, 2, "mapIt"); + stateLoop->addIncoming(rangeFrom, blockBeforeLoop); + + // loop body: + Value* elIn = compileGetElement(varIn, stateLoop, varEl); + scopeLoop->bindArg(elIn, move(varEl)); + Value* elOut = scopeLoop->compileExpression(scopeLoop->__body, *llvm); + Value *pElOut = builder.CreateGEP(dataOut, ArrayRef(std::vector{ConstantInt::get(tyNum, 0), stateLoop})); + builder.CreateStore(elOut, pElOut); + + //next iteration preparing + Value *stateLoopNext = builder.CreateAdd(stateLoop,llvm::ConstantInt::get(tyNum, 1)); + stateLoop->addIncoming(stateLoopNext, blockLoop); + + //next iteration checks: + Value* condAfter = builder.CreateICmpSLE(stateLoopNext, rangeTo); + builder.CreateCondBr(condAfter, blockLoop, blockAfterLoop); + + //finalization: + builder.SetInsertPoint(blockAfterLoop); + + return dataOut; +} + +llvm::Value* +Instructions::compileFold(const Expression& fold, const std::string& ident) +{ + #define NAME(x) (ident.empty()? x : ident) + assert(fold.op == Operator::FOLD); + + //initialization: + Symbol varInSymbol = scope->findSymbol(fold.getOperands()[0].getValueString(), *llvm); + ImplementationData info = Query::queryImplementation(varInSymbol); + const pair& range = info.getRange(); + llvm::Value* rangeFrom = scope->compileExpression(range.first, *llvm); + llvm::Value* rangeTo = scope->compileExpression(range.second, *llvm); + llvm::Value* accumInit = scope->compileExpression(fold.getOperands()[1], *llvm); + std::string varIn = fold.getOperands()[0].getValueString(); + std::string varAccum = fold.bindings[1]; + std::string varEl = fold.bindings[0]; + llvm::Value* valSat; + bool flagHasSaturation = false; //false; // TODO add `saturation` ann. + + llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); + llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold", llvm->context.function); + llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postfold", llvm->context.function); + + // * initial check + Value* condBefore = llvm->builder.CreateICmpSLE(rangeFrom, rangeTo); + llvm->builder.CreateCondBr(condBefore, blockLoop, blockAfterLoop); + + if (flagHasSaturation) + { + Value* condSat = llvm->builder.CreateICmpNE(accumInit, valSat); + llvm->builder.CreateCondBr(condSat, blockLoop, blockAfterLoop); + } + + // * create phi + llvm->builder.SetInsertPoint(blockLoop); + llvm::PHINode *accum = llvm->builder.CreatePHI(tyNum, 2, NAME("accum")); + accum->addIncoming(accumInit, blockBeforeLoop); + + llvm::PHINode *stateLoop = llvm->builder.CreatePHI(tyNum, 2, "foldIt"); + stateLoop->addIncoming(rangeFrom, blockBeforeLoop); + + // * loop body + ManagedScpPtr scopeLoop = fold.blocks.front(); + Value* elIn = compileGetElement(varIn, stateLoop); + scopeLoop->bindArg(accum, move(varAccum)); + scopeLoop->bindArg(elIn, move(varEl)); + Value* accumNext = scopeLoop->compileExpression(scopeLoop->__body, *llvm); + + // * break checks, continue checks + if (flagHasSaturation) + { + llvm::BasicBlock *blockChecks = llvm::BasicBlock::Create(llvm::getGlobalContext(), "checks", llvm->context.function); + Value* condSat = llvm->builder.CreateICmpNE(accumNext, valSat); + llvm->builder.CreateCondBr(condSat, blockChecks, blockAfterLoop); + llvm->builder.SetInsertPoint(blockChecks); + } + // * computing next iteration state + Value *stateLoopNext = llvm->builder.CreateAdd(stateLoop, llvm::ConstantInt::get(tyNum, 1)); + accum->addIncoming(accumNext, llvm->builder.GetInsertBlock()); + stateLoop->addIncoming(stateLoopNext, llvm->builder.GetInsertBlock()); + + // * next iteration checks + Value* condAfter = llvm->builder.CreateICmpSLE(stateLoopNext, rangeTo); + llvm->builder.CreateCondBr(condAfter, blockLoop, blockAfterLoop); + + // finalization: + llvm->builder.SetInsertPoint(blockAfterLoop); + + return accum; +} + +llvm::Value* +Instructions::compileIf(const Expression& exprIf, const std::string& ident) +{ + #define NAME(x) (ident.empty()? x : ident) + + //initialization: + const Expression& condExpr = exprIf.getOperands()[0]; + llvm::IRBuilder<>& builder = llvm->builder; + + llvm::BasicBlock *blockAfter = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifAfter", llvm->context.function); + llvm::BasicBlock *blockTrue = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifTrue", llvm->context.function); + llvm::BasicBlock *blockFalse = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifFalse", llvm->context.function); + + llvm::Value* cond = scope->compileExpression(condExpr, *llvm); + llvm->builder.CreateCondBr(cond, blockTrue, blockFalse); + + builder.SetInsertPoint(blockTrue); + ManagedScpPtr scopeTrue = exprIf.blocks.front(); + llvm::Value* resultTrue = scopeTrue->compileExpression(scopeTrue->__body, *llvm); + builder.CreateBr(blockAfter); + + builder.SetInsertPoint(blockFalse); + ManagedScpPtr scopeFalse = exprIf.blocks.back(); + llvm::Value* resultFalse = scopeFalse->compileExpression(scopeFalse->__body, *llvm); + builder.CreateBr(blockAfter); + + builder.SetInsertPoint(blockAfter); + llvm::PHINode *ret = builder.CreatePHI(tyNum, 2, NAME("if")); + ret->addIncoming(resultTrue, blockTrue); + ret->addIncoming(resultFalse, blockFalse); + + return ret; +} + +llvm::Value* +Instructions::compileConstantArray(const Expression &expr, const std::string& hintRetVar) { + const int& __size = expr.getOperands().size(); + const Expression& __data = expr; + + ArrayType* typList = (ArrayType*) (TypeAnnotation(tag_array, TypePrimitive::i32, __size).toLLVMType()); + Type*typI32 = TypeAnnotation(TypePrimitive::i32).toLLVMType(); + + std::vector list; + list.reserve(__size); + + const std::vector operands = __data.getOperands(); + std::transform(operands.begin(), operands.end(), std::inserter(list, list.begin()), + [typI32](const Expression& e){return ConstantInt::get(typI32, e.getValueDouble());}); + + Value* listSource = ConstantArray::get(typList, ArrayRef(list)); + /* + Value* listDest = l.builder.CreateAlloca(typList, ConstantInt::get(typI32, __size), *hintRetVar); + l.buil1der.CreateMemCpy(listDest, listSource, __size, 16); + */ + + return listSource; +} \ No newline at end of file diff --git a/cpp/src/instructions/instr-containers.h b/cpp/src/instructions/instr-containers.h new file mode 100644 index 0000000..bbb89fb --- /dev/null +++ b/cpp/src/instructions/instr-containers.h @@ -0,0 +1,76 @@ +#ifndef CODEINSTRUCTIONS_H +#define CODEINSTRUCTIONS_H + +#include "llvmlayer.h" +#include "ast.h" +#include +#include + +namespace xreate { + namespace containers { + +class Instructions { +public: + Instructions(CodeScope *current, LLVMLayer* layer); + llvm::Value* compileIndex(const Symbol& dataSymbol, std::vector indexes, std::string ident=""); + llvm::Value* compileGetElement(std::string varIn, llvm::Value* stateLoop, std::string ident=""); + + /* + * - map Computation -> Llvm_Array: Prohibited, we do not know a result size + * - map Llvm_Array -> Computation: considered in `compileGetElement` + * - map Llvm_Array -> Llvm_Array considered by this method + */ + llvm::Value* compileMapArray(const Expression &expr, const std::string hintRetVar=""); + llvm::Value* compileFold(const Expression& fold, const std::string& ident=""); + llvm::Value* compileIf(const Expression& exprIf, const std::string& ident); + + llvm::Value *compileConstantArray(const Expression &expr, const std::string& hintRetVar=""); + +private: + CodeScope* scope; + LLVMLayer* llvm; + + llvm::IntegerType* const tyNum; +}; + + + + }} + +#endif //CODEINSTRUCTIONS_H + +/* + template + struct InstructionClasses {}; + + template<> + struct InstructionClasses { + typedef InstructionList Impl; + }; + + template<> + struct InstructionClasses { + typedef InstructionMap Impl; + }; + + template + class CodeInstruction: public InstructionClasses::Impl + { + typedef typename InstructionClasses::Impl InstructionImpl; + + public: + CodeInstruction(CodeScope* parent) + : InstructionImpl(parent) + {} + + llvm::Value * + compileExpression(const Expression &expr, LLVMLayer &l, const std::string * const hintRetVar) + { + if (expr.op == Instruction) + return InstructionImpl::compileDefault(expr, l, hintRetVar); + + return CodeScope::compileExpression(expr, l, hintRetVar); + } + }; +} +*/ \ No newline at end of file diff --git a/cpp/src/llvmlayer.h b/cpp/src/llvmlayer.h index 8fc6d4d..937143c 100644 --- a/cpp/src/llvmlayer.h +++ b/cpp/src/llvmlayer.h @@ -1,35 +1,38 @@ #ifndef LLVMLAYER_H #define LLVMLAYER_H #include "llvm/IR/Module.h" #include "llvm/IR/Function.h" -#include "llvm/PassManager.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/CallingConv.h" #include "llvm/IR/Verifier.h" #include "llvm/IR/IRPrintingPasses.h" #include "llvm/IR/IRBuilder.h" #include "llvm/Support/raw_ostream.h" #include "llvm/IR/LLVMContext.h" - +#include "utils.h" //#include "ast.h" namespace xreate { class AST; class LLVMLayer { public: LLVMLayer(); AST *ast; llvm::Module *module; llvm::IRBuilder<> builder; - llvm::Function *function = 0; + + struct { + llvm::Function* function = 0; + } context; void moveToGarbage(void *o); llvm::Value *compile() const; private: std::vector __garbage; }; } #endif // LLVMLAYER_H diff --git a/cpp/src/main.cpp b/cpp/src/main.cpp index e68bba5..a43eeed 100644 --- a/cpp/src/main.cpp +++ b/cpp/src/main.cpp @@ -1,59 +1,5 @@ -#include - -#include "llvm/IR/Module.h" -#include "llvm/Function.h" -#include "llvm/PassManager.h" -#include "llvm/CallingConv.h" -#include "llvm/Analysis/Verifier.h" -#include "llvm/Assembly/PrintModulePass.h" -#include "llvm/Support/IRBuilder.h" -#include "llvm/Support/raw_ostream.h" - -using namespace llvm; - int main() { - LLVMContext& ctx = makeLLVMModule(); - - Module* m = new Module("test"); - - Constant* c = m->getOrInsertFunction("mul_add", - /*ret type*/ IntegerType::get(ctx,32), - /*args*/ IntegerType::get(ctx,32), - IntegerType::get(ctx, 32), - IntegerType::get(ctx,32), - /*varargs terminated with null*/ NULL); - - Function* mul_add = cast(c); - mul_add->setCallingConv(CallingConv::C); - - - Function::arg_iterator args = mul_add->arg_begin(); - Value* x = args++; - x->setName("x"); - Value* y = args++; - y->setName("y"); - Value* z = args++; - z->setName("z"); - - BasicBlock* block = BasicBlock::Create(getGlobalContext(), "entry", mul_add); - IRBuilder<> builder(block); - - Value* tmp = builder.CreateBinOp(Instruction::Mul, - x, y, "tmp"); - Value* tmp2 = builder.CreateBinOp(Instruction::Add, - tmp, z, "tmp2"); - - builder.CreateRet(tmp2); - - verifyModule(*m, PrintMessageAction); - - PassManager man; - man.add(createPrintModulePass(&outs())); - man.run(*m); - - delete m; - return 0; } diff --git a/cpp/src/pass/abstractpass.cpp b/cpp/src/pass/abstractpass.cpp new file mode 100644 index 0000000..a729a75 --- /dev/null +++ b/cpp/src/pass/abstractpass.cpp @@ -0,0 +1,90 @@ +#include "abstractpass.h" +#include "attachments.h" +using namespace std; + +namespace xreate { + void + AbstractPass::process(ManagedRulePtr rule) + {} + + void + AbstractPass::process(ManagedFnPtr function) { + PassContext context; + context.function = function; + + process(function->getEntryScope(), context); + } + + void + AbstractPass::process(CodeScope *scope, PassContext context) { + context.scope = scope; + process(scope->__body, context); + } + + void + AbstractPass::process(const Expression& expression, PassContext context, const std::string& varDecl){ + switch (expression.__state) { + case Expression::COMPOUND: + for (const Expression &op: expression.getOperands()) { + process(op, context); + } + + assert(expression.op != Operator::MAP || expression.op == Operator::MAP && expression.blocks.size()); + for (ManagedScpPtr scope: expression.blocks) { + process(&*scope, context); + } + + /* + if (expression.op == Operator::CALL) { + const std::string &calleeName = expression.getValueString(); + ManagedFnPtr callee = root->findFunction(calleeName); + } + */ + break; + + case Expression::IDENT: + assert(context.scope); + + string ident = expression.getValueString(); + const Symbol& symbol = context.scope->findSymbol(ident, *man->llvm); + + if (SymbolAttachments::get (symbol, false)) {break;} + SymbolAttachments::put (symbol, true); + + PassContext context2 = context; + context2.scope = symbol.scope; + if (CodeScope::hasDeclaration(symbol)) { + process(CodeScope::findDeclaration(symbol), context2, ident); + } + + break; + } + } + + void + AbstractPass::processFnCall(ManagedFnPtr function, PassContext context) + { + } + + void + AbstractPass::run() { + ManagedRulePtr rule = man->root->begin(); + while (rule.isValid()) { + process(rule); + ++rule; + } + + ManagedFnPtr f = man->root->begin(); + while (f.isValid()) { + process(f); + ++f; + } + } + + void AbstractPass::finish() + {} + + AbstractPass::AbstractPass(PassManager *manager) + : man(manager) { + } +} \ No newline at end of file diff --git a/cpp/src/pass/abstractpass.h b/cpp/src/pass/abstractpass.h new file mode 100644 index 0000000..a49d1a1 --- /dev/null +++ b/cpp/src/pass/abstractpass.h @@ -0,0 +1,38 @@ +#ifndef ABSTRACTPASS_H +#define ABSTRACTPASS_H + +#include "passmanager.h" + +namespace xreate +{ + struct PassContext + { + CodeScope* scope = 0; + ManagedFnPtr function; + ManagedRulePtr rule; + std::string varDecl; + + PassContext() + {} + + ~PassContext(){} + }; + + class AbstractPass + { + public: + AbstractPass(PassManager* man); + virtual void run(); + virtual void finish(); + + virtual void processFnCall(ManagedFnPtr function, PassContext context); + virtual void process(ManagedFnPtr function); + virtual void process(ManagedRulePtr rule); + virtual void process(CodeScope* scope, PassContext context); + virtual void process(const Expression& expression, PassContext context, const std::string& varDecl=""); + + protected: + PassManager* man; + }; +} +#endif \ No newline at end of file diff --git a/cpp/src/pass/cfgpass.cpp b/cpp/src/pass/cfgpass.cpp index f243f73..c3195e7 100644 --- a/cpp/src/pass/cfgpass.cpp +++ b/cpp/src/pass/cfgpass.cpp @@ -1,99 +1,41 @@ #include "cfgpass.h" #include using namespace std; using namespace xreate; -CFGPass::CFGPass(ClaspLayer* claspLayer) - : clasp(claspLayer) + +void +CFGPass::start() { + __context.graph = CFGraph(); } void -CFGPass::process(const Expression& entity,const Context& context) +CFGPass::finish() { - switch(entity.__state) - { - case Expression::COMPOUND: - { - switch (entity.__op){ - // First of all process all parameters - case Operator::CALL : case Operator::LIST: case Operator::LOOP: - for (const Expression& op: entity.operands) - { - process(op, context); - } - } - - // this is what we are looking for - if (entity.__op == Operator::CALL) - { - const std::string& calleeName = entity.__valueS; - assert(clasp->ast->__indexFunctions.count(calleeName)); - FID calleeId = clasp->ast->__indexFunctions.at(calleeName); - - __graph.addLink(context.id, calleeId); - break; - } - - if (entity.__op == Operator::LOOP) - { - assert(entity.blocks.size()); - process(&(entity.blocks[0]), context); - } - - break; - } - - case Expression::IDENT: - const std::string& name = entity.__valueS; - //search in current scope: - if (context.scope->__vartable.count(name)) - { - VID ident = context.scope->__vartable.at(name); - - // if ident is scope arg then do nothing - if (! context.scope->__declarations.count(ident)) - { - break; - } - - // if ident declared within current scope, - const Expression& decl = context.scope->__declarations.at(ident); - process(decl, context); - } - - //search in parent scope - if (context.scope->__parent) - { - Context context2 = context; - context2.scope = context.scope->__parent; - - process(entity, context2); - }; - } + man->clasp->addCFGData(move(__context.graph)); } -void CFGPass:: process(const CodeScope* scope, Context context) +CFGPass::CFGPass(PassManager* manager) + : ASTPass(manager) { - context.scope = scope; - process(scope->__body, context); + man->registerFilter(this, PassFilter:: FUNCTION); + man->registerFilter(this, PassFilter:: FUNCTIONCALL); } void -CFGPass::run() +CFGPass::process(ManagedFnPtr function, PassContext context) { - __graph = CFGraph(); - cout << "CFGPass::run" << endl; - - for(FID f=0, fcount= clasp->ast->getFunctionsCount(); fast->getFunctionById(f); - __graph.addNode(f, string(func.getName())); + const string& name = function->getName(); - Context context{f, nullptr}; - process(&func.getEntryScope(), context); - }; + __context.graph.addNode(function.id(), string(name)); + return; + } - clasp->addCFGData(std::move(__graph)); -} + //FUNCTIONCALL decl + __context.graph.addLink(context.function.id(), function.id()); +} \ No newline at end of file diff --git a/cpp/src/pass/cfgpass.h b/cpp/src/pass/cfgpass.h index 11a0f36..0eb3ebf 100644 --- a/cpp/src/pass/cfgpass.h +++ b/cpp/src/pass/cfgpass.h @@ -1,31 +1,26 @@ // Control Flow Graph determination pass #ifndef CFGPASS_H #define CFGPASS_H -#include "ast.h" -#include -#include +#include "passmanager.h" #include "clasplayer.h" namespace xreate { -class CFGPass +class CFGPass : public ASTPass { public: - void run(); - CFGPass(ClaspLayer* claspLayer); + void init(); + CFGPass(PassManager* manager); + void process(ManagedFnPtr function, PassContext context); + virtual void start(); + virtual void finish(); private: - struct Context { - FID id; - const CodeScope* scope; - }; + struct { + CFGraph graph; + } __context; - CFGraph __graph; - ClaspLayer* clasp; - - void process(const Expression& entity, const Context& context); - void process(const CodeScope* scope, Context context); }; } #endif // CFGPASS_H diff --git a/cpp/src/pass/dfgpass.cpp b/cpp/src/pass/dfgpass.cpp new file mode 100644 index 0000000..3586b0b --- /dev/null +++ b/cpp/src/pass/dfgpass.cpp @@ -0,0 +1,144 @@ +#include +#include "dfgpass.h" +#include "../passmanager.h" + +using namespace xreate; +using namespace std; + +DFGPass::DFGPass(PassManager* manager) + : AbstractPass(manager) +{} + + + +SymbolPacked +DFGPass::processExpression(const Expression& expression, PassContext context, const std::string& decl) +{ + switch(expression.op) { + case Operator::CALL: { + const string &name = expression.getValueString(); + ManagedFnPtr function = man->root->findFunction(name); + CodeScope *scopeRemote = function->getEntryScope(); + + std::vector operands; + operands.reserve(expression.getOperands().size()); + for (const Expression &op: expression.getOperands()) { + operands.push_back(processExpression(op, context)); + } + + std::vector::iterator op = operands.begin(); + for (const std::string &arg: scopeRemote->__args) { + if (op->isValid()) { + const Symbol &nodeRemote = scopeRemote->findSymbol(arg, *man->llvm, false); + __context.graph.addLink(__context.graph.pack(nodeRemote), *op, DFGConnection::OPT); + } + + ++op; + } + + SymbolPacked ret = __context.graph.pack(Symbol{0, scopeRemote}); + if (!decl.empty()) { + __context.graph.addLink( + __context.graph.pack( + context.scope->findSymbol(decl, *man->llvm, false)), + ret, DFGConnection::OPT); + } + + return ret; + } + + default: { + std::vector operands; + + if (__schemes.count(expression.op)) { + const Expression &scheme = __schemes.at(expression.op); + + operands.reserve(expression.getOperands().size()); + for (const Expression &op: expression.getOperands()) { + operands.push_back(processExpression(op, context)); + } + + std::vector::const_iterator arg = operands.begin(); + std::vector::const_iterator tag = ++scheme.getOperands().begin(); + + while (tag != scheme.getOperands().end()) { + if (arg->isValid() && tag->__state != Expression::INVALID) { + __context.graph.addTag(*arg, Expression(*tag)); + } + + ++arg; ++tag; + } + + Expression retTag = *scheme.getOperands().begin(); + if (retTag.__state != Expression::INVALID) { + assert(!decl.empty()); + SymbolPacked pdecl = __context.graph.pack(context.scope->findSymbol(decl, *man->llvm, false)); + __context.graph.addTag(pdecl, move(retTag)); + } + } + + // adhoc for MAP case, TODO reorganize code in more clear manner + if (expression.op == Operator::MAP) { + SymbolPacked nodeFrom; + + if (operands.size()) { + nodeFrom = operands.at(0); + } else { + nodeFrom = processExpression(expression.getOperands().at(0), context); + } + + assert(!decl.empty()); + SymbolPacked nodeTo = __context.graph.pack(context.scope->findSymbol(decl, *man->llvm, false)); + __context.graph.addLink(move(nodeTo), move(nodeFrom), DFGConnection::PROTO); + } + } + + } + + switch(expression.__state) { + case Expression::IDENT: + AbstractPass::process(expression, context, decl); + + string ident = expression.getValueString(); + const Symbol& identSymbol = context.scope->findSymbol(ident, *man->llvm); + + SymbolPacked nodeFrom = __context.graph.pack(identSymbol); + if (!decl.empty()) { + SymbolPacked nodeTo = __context.graph.pack(context.scope->findSymbol(decl, *man->llvm)); + __context.graph.addLink(move(nodeTo), move(nodeFrom), DFGConnection::STRONG); + } + + return nodeFrom; + } + + AbstractPass::process(expression, context, decl); + return SYMBOL_INVALID; +} + +void +DFGPass::run() +{ + init(); + return AbstractPass::run(); +} + +void +DFGPass::process(const Expression& expression, PassContext context, const std::string& decl) +{ + processExpression(expression, context, decl); +} + + +void +DFGPass::init() +{ + for (const Expression& scheme: man->root->__dfadata) + { + __schemes.emplace(scheme.op, scheme); + } +} + +void DFGPass::finish() +{ + man->clasp->addDFAData(move(__context.graph)); +} \ No newline at end of file diff --git a/cpp/src/pass/dfgpass.h b/cpp/src/pass/dfgpass.h new file mode 100644 index 0000000..3d06d8b --- /dev/null +++ b/cpp/src/pass/dfgpass.h @@ -0,0 +1,32 @@ +// Data Flow Graph determination pass + +#ifndef DFGPASS_H +#define DFGPASS_H + +#include "abstractpass.h" +#include "clasplayer.h" + +namespace xreate { + +class DFGPass: public AbstractPass { +public: + void process(const Expression& expression, PassContext context, const std::string& varDecl=""); + SymbolPacked processExpression(const Expression& expression, PassContext context, const std::string& decl=""); + + DFGPass(PassManager* manager); + unsigned int hash(const CodeScope* scope); + + void init(); + void run(); + void finish(); +private: + struct + { + DFGraph graph; + } __context; + + std::map __schemes; +}; +}; + +#endif \ No newline at end of file diff --git a/cpp/src/pass/functiontagspass.cpp b/cpp/src/pass/functiontagspass.cpp index eb130de..6242d55 100644 --- a/cpp/src/pass/functiontagspass.cpp +++ b/cpp/src/pass/functiontagspass.cpp @@ -1,19 +1,21 @@ +/* #include "functiontagspass.h" #include using namespace std; using namespace xreate; FunctionTagsPass::FunctionTagsPass(AST& root) : __root(root) { } void FunctionTagsPass::run(ClaspLayer& clasp) { - for (FID id=0, count = __root.getFunctionsCount(); id < count; ++id) + for (ManagedFnPtr id=0, count = __root.getFunctionsCount(); id < count; ++id) { const Function& f = __root.getFunctionById(id); clasp.addFunctionTags(f.getName(), f.getAnnotations()); } } +*/ \ No newline at end of file diff --git a/cpp/src/pass/rulespass.cpp b/cpp/src/pass/rulespass.cpp index 066a530..a30c100 100644 --- a/cpp/src/pass/rulespass.cpp +++ b/cpp/src/pass/rulespass.cpp @@ -1,16 +1,16 @@ #include "rulespass.h" using namespace xreate; -RulesPass::RulesPass(const AST& ast) - : __root(ast) -{} +RulesPass::RulesPass(PassManager* manager) + : ASTPass(manager) +{ + man->registerFilter(this, PassFilter::RULE); +} void -RulesPass::run(ClaspLayer& clasp) +RulesPass::process(MetaRuleAbstract* rule, PassContext context) { - for(const auto& rule: __root.__rules) - { - rule->compile(clasp); - } + rule->compile(*man->clasp); } + diff --git a/cpp/src/pass/rulespass.h b/cpp/src/pass/rulespass.h index 7a82b71..fefd760 100644 --- a/cpp/src/pass/rulespass.h +++ b/cpp/src/pass/rulespass.h @@ -1,17 +1,13 @@ #ifndef RULESPASS_H #define RULESPASS_H -#include -#include +#include "passmanager.h" namespace xreate { -class RulesPass +class RulesPass : public ASTPass { public: - RulesPass(const AST& ast); - void run(ClaspLayer& clasp); - -private: - const AST& __root; + void process(MetaRuleAbstract* rule, PassContext context); + RulesPass(PassManager* manager); }; } #endif // RULESPASS_H diff --git a/cpp/src/passmanager.cpp b/cpp/src/passmanager.cpp new file mode 100644 index 0000000..5693aaf --- /dev/null +++ b/cpp/src/passmanager.cpp @@ -0,0 +1,25 @@ +#include +#include "query/containers.h" +#include "passmanager.h" +using namespace xreate; +using namespace std; + +void +PassManager::registerPass(AbstractPass* pass) +{ + __passes.push_back(pass); +} + +void +PassManager::run() +{ + for (AbstractPass* pass: __passes) + { + pass->run(); + pass->finish(); + } + + clasp->registerdQuery(new containers::Query()); +} + +PassManager::~PassManager(){} diff --git a/cpp/src/passmanager.h b/cpp/src/passmanager.h new file mode 100644 index 0000000..4875ee7 --- /dev/null +++ b/cpp/src/passmanager.h @@ -0,0 +1,27 @@ +#ifndef PASSMANAGER_H +#define PASSMANAGER_H + +#include "clasplayer.h" +#include "ast.h" +#include + + +namespace xreate { +class AbstractPass; +class PassManager +{ +public: + ~PassManager(); + void run(); + void registerPass(AbstractPass* pass); + + ClaspLayer* clasp; + LLVMLayer* llvm; + AST* root; +private: + //typedef std::multimap FILTERS_STORAGE; + //FILTERS_STORAGE __filters; + std::list __passes; +}; } + +#endif \ No newline at end of file diff --git a/cpp/src/query/containers.cpp b/cpp/src/query/containers.cpp new file mode 100644 index 0000000..c317bbd --- /dev/null +++ b/cpp/src/query/containers.cpp @@ -0,0 +1,155 @@ +// +// Created by pgess on 3/14/15. +// + +#include +#include "query/containers.h" + +using namespace std; +using namespace xreate::containers; +using namespace xreate; + +const std::string ID_IMPLEMENTATIONS = "impl_fulfill_cluster"; +const std::string ID_CLUSTERS = "var_cluster"; +const std::string ID_PROTOTYPES = "proto_cluster"; + +ImplementationData +Query::queryImplementation(xreate::Symbol const &s) { + + typedef SymbolAttachments attachs; + if (attachs::exists(s)) + { + return SymbolAttachments::get(s); + } + + return ImplementationData(s); +} + +void +Query::init(ClaspLayer* clasp) +{ + if (flagIsDataLoaded) return; + + map prototypes; + map roots; + + //read all proto data + auto range = clasp->query(ID_PROTOTYPES); + for(ClaspLayer::ModelIterator atom = range.first; atom != range.second; ++atom) { + auto data = ClaspLayer::parse(atom->second); + Symbol root = clasp->dfgData.unpack(get<0> (data)); + Symbol prototype = clasp->dfgData.unpack(get<1> (data)); + + prototypes[root] = prototype; + } + + // fill implementation data for a data sources: + range = clasp->query(ID_IMPLEMENTATIONS); + for(ClaspLayer::ModelIterator atom = range.first; atom != range.second; ++atom) + { + auto data = ClaspLayer::parse(atom->second); + + Symbol var = clasp->dfgData.unpack(get<0>(data)); + string implSerialized = get<1>(data); + + //data source, has no prototypes: + if (!prototypes.count(var)) + { + ImplementationData impl(var); + SymbolAttachments::put(var, move(impl)); + continue; + } + + roots.emplace(move(var), move(implSerialized)); + } + + //fill implementation dara for a cluster roots + for (const pair & root: roots) + { + Symbol prototype = prototypes[root.first]; + + while (prototypes.count(prototype)) { + prototype = prototypes.at(prototype); + } + + ImplementationData impl(root.first, root.second, SymbolAttachments::get(prototype)); + SymbolAttachments::put(root.first, move(impl)); + } + + // read cluster data and fill implementation data for cluster members + range = clasp->query(ID_CLUSTERS); + for(ClaspLayer::ModelIterator atom = range.first; atom != range.second; ++atom) + { + auto info = ClaspLayer::parse(atom->second); + + Symbol root = clasp->dfgData.unpack(get<0>(info)); + Symbol child = clasp->dfgData.unpack(get<1>(info)); + + if (!(child == root)) { + ImplementationData rootImpl = SymbolAttachments::get(root); + SymbolAttachments::put(child, move(rootImpl)); + } + + } + + flagIsDataLoaded = true; +} + +ImplementationData::ImplementationData(Symbol var) +{ + + Expression varDecl = CodeScope::findDeclaration(var); + switch (varDecl.op) + { + case Operator::LIST_RANGE: + range=var; + impl = ON_THE_FLY; + break; + + case Operator::LIST: + impl = LLVM_CONST_ARRAY; + size = varDecl.getOperands().size(); + break; + + default: + assert(false && "unable to determine proper implementation for the symbol"); + break; + }; +} + +ImplementationData::ImplementationData(Symbol var, std::string implSerialized, const ImplementationData& implPrototype) +{ + if (implSerialized == "llvm_array") + { + impl = LLVM_ARRAY; + size = implPrototype.size; + + } else if (implSerialized == "llvm_const_array") { + impl = LLVM_CONST_ARRAY; + size = implPrototype.size; + + } else if (implSerialized == "on_the_fly") { + impl = ON_THE_FLY; + range = implPrototype.range; + + } else { + assert(false && "unable to determine proper implementation for the symbol"); + } +} + +std::pair +ImplementationData::getRange() +{ + switch (impl) { + case ON_THE_FLY: { + Expression decl = CodeScope::findDeclaration(range); + + assert(decl.getOperands().size() == 2); + return make_pair(decl.getOperands()[0], decl.getOperands()[1]); + } + + default: { + return make_pair(Expression(Atom(0)), Expression(Atom(size - 1))); + } + }; +} diff --git a/cpp/src/query/containers.h b/cpp/src/query/containers.h new file mode 100644 index 0000000..d91a89d --- /dev/null +++ b/cpp/src/query/containers.h @@ -0,0 +1,49 @@ +// +// Created by pgess on 3/14/15. +// + +#ifndef _XREATE_CONTAINERSQUERY_H_ +#define _XREATE_CONTAINERSQUERY_H_ + +#include "passmanager.h" + +namespace xreate { +namespace containers { + + enum Implementation{ + LLVM_ARRAY, LLVM_CONST_ARRAY, ON_THE_FLY + }; + + struct ImplementationData { + Implementation impl; + union { + unsigned int size; //valid in case of LLVM_ARRAY impl. + struct { + Symbol range; + }; + }; + ImplementationData(Symbol var); + ImplementationData(Symbol var, std::string implSerialized, const ImplementationData& implPrototype); + std::pair getRange(); + }; + + class Query : public xreate::IQuery { + public: + static ImplementationData queryImplementation(xreate::Symbol const &s); + void init(ClaspLayer* clasp); + + ~Query(){} + private: + bool flagIsDataLoaded = false; + PassManager *man; + }; +} + + template<> + struct AttachmentsDictionary { + typedef containers::ImplementationData Data; + static const unsigned int key = 1; + }; +} + +#endif //_XREATE_CONTAINERSQUERY_H_ diff --git a/cpp/src/utils.h b/cpp/src/utils.h index 965be11..3eb314f 100644 --- a/cpp/src/utils.h +++ b/cpp/src/utils.h @@ -1,10 +1,65 @@ #ifndef UTILS_H #define UTILS_H + +#include "ast.h" + +//TODO mark dirty members + /* template struct DdesctructableClass { } */ +/* +template +struct TagUpdatable{ + TagUpdatable(const OriginalType& source) + : __source(source) + {} + + TagUpdatable() = delete; + + const OriginalType& __source; +}; + + +struct Updatable; + +template +struct TagsDictionary +{}; + +template +struct TagsDictionary +{ + typedef TagUpdatable TagName; +}; + +template +struct awareOf +{ + awareOf(OT& dest) + : __dest(dest) + {} + + awareOf& + operator= (const typename TagsDictionary::TagName& source) + { + __dest = source.__source; + } + +private: + OT& __dest; +}; + +template> +const OT& +awareOf(const Tag& holder) +{ + return std::forward(holder.__source); +} +*/ + #endif // UTILS_H diff --git a/cpp/tests/tests.cpp b/cpp/tests/tests.cpp index 5a8efae..81ce6e8 100644 --- a/cpp/tests/tests.cpp +++ b/cpp/tests/tests.cpp @@ -1,88 +1,113 @@ #include "Scanner.h" #include "Parser.h" #include "ast.h" #include #include -#include "pass/cfgpass.h" -#include "pass/functiontagspass.h" -#include "pass/rulespass.h" - #include "clasplayer.h" -#include +#include "passmanager.h" +#include "pass/dfgpass.h" using namespace std; void testParser_1() { shared_ptr scanner(new Scanner(L"scripts/input.xreate")); shared_ptr parser(new Parser(scanner.get())); parser->Parse(); flush(cout); AST& root = parser->root; LLVMLayer l; root.compile(l); root.run(l); } void testClasp2() { shared_ptr scanner(new Scanner(L"scripts/input.xreate")); shared_ptr parser(new Parser(scanner.get())); parser->Parse(); flush(cout); if (parser->errors->count) { cout << "Found " << parser->errors->count << " errors. Stop" << endl; exit(1); } AST& root = parser->root; ClaspLayer clasp; + /* FunctionTagsPass(root).run(clasp); RulesPass(root).run(clasp); CFGPass(&clasp).run(); - clasp.run(); + clasp.1 + run(); + */ } void testUnsafeCode1() { shared_ptr scanner(new Scanner(L"scripts/cases/bugs-code.xreate")); shared_ptr parser(new Parser(scanner.get())); parser->Parse(); flush(cout); if (parser->errors->count) { cout << "Found " << parser->errors->count << " errors. Stop" << endl; exit(1); } AST& root = parser->root; ClaspLayer clasp; + /* FunctionTagsPass(root).run(clasp); RulesPass(root).run(clasp); CFGPass(&clasp).run(); //clasp.addRule(":- call(X, Y), tag(Y, unsafe), not tag(X, unsafe), function(X), function(Y)."); clasp.run(); + */ } -void tests_ListsMultiply() +void test_DFG_1() { + shared_ptr scanner(new Scanner(L"scripts/input.xreate")); + shared_ptr parser(new Parser(scanner.get())); + parser->Parse(); + flush(cout); + + if (parser->errors->count) + { + cout << "Found " << parser->errors->count << " errors. Stop" << endl; + exit(1); + } + + PassManager m; + m.clasp = new ClaspLayer(); + + m.llvm = new LLVMLayer(); + m.root = & parser->root; + m.clasp->ast = m.root; + + m.registerPass(new DFGPass(&m)); + m.run(); + m.clasp->run(); + m.root->compile(*m.llvm); + m.root->run(*m.llvm); } int main() { - testParser_1(); + test_DFG_1(); return 0; } diff --git a/problems/cond.lp b/problems/basket/cond.lp similarity index 100% rename from problems/cond.lp rename to problems/basket/cond.lp diff --git a/problems/containers.lp b/problems/basket/containers.lp similarity index 100% rename from problems/containers.lp rename to problems/basket/containers.lp diff --git a/problems/example-computations.lp b/problems/basket/example-computations.lp similarity index 100% rename from problems/example-computations.lp rename to problems/basket/example-computations.lp diff --git a/problems/example-computations2.lp b/problems/basket/example-computations2.lp similarity index 100% rename from problems/example-computations2.lp rename to problems/basket/example-computations2.lp diff --git a/problems/gte.lp b/problems/basket/gte.lp similarity index 100% rename from problems/gte.lp rename to problems/basket/gte.lp diff --git a/problems/test-list.lp b/problems/basket/test-list.lp similarity index 100% rename from problems/test-list.lp rename to problems/basket/test-list.lp diff --git a/problems/test.lp b/problems/basket/test.lp similarity index 100% rename from problems/test.lp rename to problems/basket/test.lp diff --git a/problems/basket/timetable-tests.lp b/problems/basket/timetable-tests.lp new file mode 100644 index 0000000..32dcea6 --- /dev/null +++ b/problems/basket/timetable-tests.lp @@ -0,0 +1,54 @@ +man(brian; joe; chris; bob). +professor(brian; joe). +phd(chris). +asisstant(bob). + +lesson(1..10). +day(1..5). +week(even; odd). + +course(a;b;c;d;e;f;j;h;k;l;m;n). + +time(a, 10). +time(b, 12). +time(c, 20). +time(d, 3). +time(e, 17). +time(f, 15). +time(j, 9). +time(h, 7). +time(k, 11). +time(l, 14). +time(m, 8). +time(n, 17). + +room(402; 403; 404). + +course_room(a, 402). +course_room(c, 404). +course_room(d, 403). +course_room(d, 404). + +% ---- timetable(Teacher, Course, Lesson, Room, Day, Week) + + + + timetable(brian, a, 1, 402, 1, even). + timetable(brian, a, 3, 402, 1, even). + timetable(brian, a, 4, 402, 1, even). + + owl(joe) % no first lesson + :- owl(T); timetable(T, _, 1,_, _, _). + +earlybird(bob). +earlybird_score(T, Score) :- Score = #count {timetable(T, C, 1, R, D, W): course(C), room(R), day(D), week(W)}; earlybird(T) . +earlybird_score(Score) :- Score = #sum{Score2, 1: earlybird_score(T, Score2)}. +:- earlybird_score(X); X<2. + + +courseDuration(C, Span) :- Span = #count{(T, C, L, R, D, W):timetable(T, C, L, R, D, W), man(T), room(R), day(D), week(W), lesson(L)};course(C). + + + + +#show courseDuration/2. \ No newline at end of file diff --git a/problems/basket/timetable.lp b/problems/basket/timetable.lp new file mode 100644 index 0000000..7b0b924 --- /dev/null +++ b/problems/basket/timetable.lp @@ -0,0 +1,73 @@ +man(brian; joe; chris; bob). +professor(brian; joe). +phd(chris). +asisstant(bob). + +lesson(1..10). +day(1..5). +week(even; odd). + +course(a;b;c;d;e;f;j;h;k;l;m;n). + +time(a, 10). +time(b, 12). +time(c, 20). +time(d, 3). +time(e, 17). +time(f, 15). +time(j, 9). +time(h, 7). +time(k, 11). +time(l, 14). +time(m, 8). +time(n, 17). + +room(402; 403; 404). + +course_room(a, 402). +course_room(c, 404). +course_room(d, 403). +course_room(d, 404). + +% ---- timetable(Teacher, Course, Lesson, Room, Day, Week) + + {timetable(T, C, L, R, D, W) : lesson(L), room(R), course_assignment(T, C)} 4 :- man(T) ; day(D); week(W) . + :- timetable(T, C1, L, _, D, W); timetable(T, C2, L, _, D, W); C1 != C2. + :- timetable(T, _, L, R1, D, W); timetable(T, _, L, R2, D, W); R1 != R2. + :- timetable(T1, _, L, R, D, W); timetable(T2, _, L, R, D, W); T1 != T2. + + courseDuration(C, Span) :- Span = #count{(T, C, L, R, D, W):timetable(T, C, L, R, D, W), man(T), room(R), day(D), week(W), lesson(L)};course(C). + :- courseDuration(C, Dur); time(C, Time); Dur > Time + 10; course(C). + :- courseDuration(C, Dur); time(C, Time); Dur < Time - 10; course(C). + + %COURSE ASSIGNMENT +1{course_assignment(T, C): man(T)}1 :- course(C). + + % FIRST LESSONS ATTENDANCE, EARLY BIRDS, OWLS +owl(joe) % no first lesson +:- owl(T); timetable(T, _, 1,_, _, _). + +earlybird(bob). +earlybird_score(T, Score) :- Score = #count {timetable(T, C, 1, R, D, W): course(C), room(R), day(D), week(W)}; earlybird(T) . +earlybird_score(Score) :- Score = #sum{Score2, 1: earlybird_score(T, Score2)}. + + % CONSEQUENT LESSONS REQUIREMENTS +noholes(brian; joe). % consequent lessons +maxlesson(T, D, W, Max) :- Max = #max{L, 1: timetable(T, C, L, R, D, W), course(C), lesson(L), room(R)};day(D); week(W); noholes(T); timetable(T,_,_,_,D,W). +minlesson(T, D, W, Min) :- Min = #min{L, 1:timetable(T, C, L, R, D, W), course(C), lesson(L), room(R)};day(D); week(W); noholes(T);timetable(T,_,_,_,D,W). +numlessons(T, D, W, Nu) :- Nu = #count{L:timetable(T, C, L, R, D, W), course(C), lesson(L), room(R)};day(D); week(W); noholes(T);timetable(T,_,_,_,D,W). +noholes_score_neg(T, D, W, Score) :- Score = (1 + M1 - M2 - Num); maxlesson(T, D, W, M1); minlesson(T, D, W, M2); numlessons(T, D, W, Num); day(D); week(W); noholes(T). + + %ATTENDANCE +%scheme: attends(Man, Day, Week). +attends(chris, 1, even). % days he can attend +%:-timetable(T, _, _, _, D, W); not attends(T, D, W). + + +%spike(brian; bob). %spike load all in one day +%steady(chris). % load the same in all days + + +%order(e, k). +%order(a, n). +#show timetable/6. \ No newline at end of file diff --git a/problems/code-containers-impl.lp b/problems/code-containers-impl.lp new file mode 100644 index 0000000..fb5941d --- /dev/null +++ b/problems/code-containers-impl.lp @@ -0,0 +1,50 @@ +%defines + impl(llvm_array; llvm_const_array; on_the_fly). + op(seqaccess). op(randaccess). + + relation(recommends; satisfied; unsupported). + relation_score(satisfied, 0). + relation_score(recommends, 1). + relation_score(unsupported, -1). + score(-1..1). + +%domain facts: + relation_op(seqaccess, on_the_fly, recommends). + relation_op(randaccess, llvm_const_array, recommends). + relation_op(randaccess, on_the_fly, unsupported). + +%dfa analysis: + dfa_connection((5,0),(4,0),strong). + v((5,0)). %c c = b : [num]; + v((3,0)). %a2 a2 = [1 .. 100] : [num]; + v((4,0)). %b b = loop map (a1 -> el: num) : [num] + v((2,0)). %a1 a1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : [num]; + +%compilation: + bind((5,0), op(randaccess)). + bind((4,0),impl(llvm_array)). + bind((3,0),impl(on_the_fly)). + bind((3,0),op(seqaccess)). + bind((2,0),op(seqaccess)). + bind((2,0),impl(llvm_const_array)). + +%domain rules: + -impl_fulfill(OP, IMPL) :- relation_op(OP, IMPL, unsupported). + impl_fulfill(OP, IMPL, SCORE):- SCORE = #sum{SCORE1, (OP, IMPL, RL): relation_op(OP, IMPL, RL),relation_score(RL, SCORE1)} + ; op(OP); impl(IMPL); not -impl_fulfill(OP, IMPL). + + cluster_root(VAR) :- not dfa_connection(VAR, _, strong), v(VAR). + var_cluster(VAR0, VAR_TO) :- dfa_connection(VAR_TO, VAR0, strong), cluster_root(VAR0). + var_cluster(VAR0, VAR_TO2) :- dfa_connection(VAR_TO2, VAR_TO1, strong), var_cluster(VAR0, VAR_TO1). + var_cluster(VAR0, VAR0):- cluster_root(VAR0). + + -impl_fulfill_cluster(Var0, Impl) :- var_cluster(Var0, Var_Any); bind(Var_Any, op(Op)); -impl_fulfill(Op, Impl). + impl_fulfill_cluster(VAR0, IMPL, Score) :- + Score = #sum{SCORE, (OP, IMPL, VAR_ANY): impl_fulfill(OP, IMPL, SCORE), var_cluster(VAR0, VAR_ANY), bind(VAR_ANY, op(OP))} + ; bind(VAR0, impl(IMPL)); cluster_root(VAR0); not -impl_fulfill_cluster(VAR0, IMPL). + +%optimization: +% #maximize {SCORE, (VAR0, IMPL) : impl_fulfill_cluster(VAR0, IMPL, SCORE)}. + +#show var_cluster/2. +#show impl_fulfill_cluster/3. \ No newline at end of file diff --git a/problems/containers.lp~ b/problems/containers.lp~ deleted file mode 100644 index 37b2605..0000000 --- a/problems/containers.lp~ +++ /dev/null @@ -1,51 +0,0 @@ - var(a).var(b). -implementation(hashlist). implementation(linkedlist). implementation(treelist). -operation(at). operation(sort). operation(insert). -relation (recommends). relation (satisfied). relation(unsupported). - -relation_score(satisfied, 0). -relation_score(recommends, 1). -relation_score(unsupported, -1). - -relation_op(at, hashlist, recommends). relation_op(at,treelist, satisfied). -relation_op(sort, linkedlist, satisfied). relation_op(sort, treelist, satisfied). relation_op(sort, hashlist, unsupported). - - -impl_fulfill(OP, IMPL, SCORE):- relation_op(OP, IMPL, RL), relation_score(RL, SCORE), operation(OP), implementation(IMPL), RL!=unsupported. -impl_not_fulfill(OP, IMPL):- relation_op(OP, IMPL, unsupported). - -bind_var_op(a, at). -bind_var_op(a, sort). -bind_var_op(b, insert). -var_connection(a, b). - -%* var_connection(VAR_FROM, VAR_TO, connection_type) *% -%* var_cluster(VAR_FROM, VAR_TO) *% - -connection_type(ct_inherits). connection_type(ct_convert). - -var_connection(VAR_FROM, VAR_TO, CT):connection_type(CT) :- var_connection(VAR_FROM, VAR_TO). - -var_cluster_root(VAR) :- {var_connection(VAR_F, VAR, ct_inherits): var(VAR_F)} 0, var(VAR). -var_cluster(VAR0, VAR_TO) :- var_connection(VAR0, VAR_TO, ct_inherits), var_cluster_root(VAR0). -var_cluster(VAR0, VAR_TO2) :- var_connection(VAR_TO1, VAR_TO2, ct_inherits), var_cluster(VAR0, VAR_TO1). -var_cluster(VAR0, VAR0):- var_cluster_root(VAR0). - - -#domain implementation(IMPL). -%#domain var(VAR). - -impl_fulfill_cluster(VAR0, OP, IMPL, SCORE) :- var_cluster(VAR0, VAR_ANY), bind_var_op(VAR_ANY, OP), impl_fulfill(OP, IMPL, SCORE), var_cluster_root(VAR0). -impl_not_fulfill_cluster(VAR0, IMPL):-var_cluster(VAR0, VAR_ANY), bind_var_op(VAR_ANYm OP), impl_not_fulfill(OP, IMPL), var_cluster_root(VAR0). -%bind_cluster_op(VAR0, OP) :- bind_var_op(VAR0, OP). -bind_var_impl(VAR0, IMPL, SCORE_RESULT) :- SCORE_RESULT = #sum[impl_fulfill_cluster(VAR0, _, IMPL, SCORE) = SCORE], {impl_not_fulfill_cluster(VAR0, IMPL)}0, var_cluster_root(VAR0). -%:- bind_var_impl(VAR0, IMPL, _), var_cluster(VAR0, VAR_ANY), bind_var_op(VAR_ANY, OP), impl_not_fulfill(OP, IMPL). - -%impl_fulfill(OP, IMPL, SCORE) : bind_var_op(VAR, OP), var(VAR), SCORE_RESULT = 0 , relation_score(_, SCORE). -%%* *% - -#hide. -#show bind_var_impl/3. -#show var_cluster_owner/1. -#show var_connection/3. -#show bind_var_op/2. diff --git a/problems/test-list.lp~ b/problems/test-list.lp~ deleted file mode 100644 index 2febb6f..0000000 --- a/problems/test-list.lp~ +++ /dev/null @@ -1,8 +0,0 @@ -%eqqq(a, (0, 1)). -%eqqq(b, (0, 1)). - -eqq(x, (0, 0)). -eqq(y, (1, 1)). -iszerosum(X, Y) :- X1 == Y1, X2 == Y2, eqq(X, (X1, X2)), eqq(Y, (Y1, Y2)). - -%plus(X, Y) :- eq(X, (ax, ay)), eq(Y, (bx, by)), ax + ay + bx + by. \ No newline at end of file diff --git a/project/diploma.doc b/project/diploma.doc deleted file mode 100644 index 869f589..0000000 Binary files a/project/diploma.doc and /dev/null differ diff --git a/project/draft.odt b/project/draft.odt deleted file mode 100644 index 422f2ae..0000000 Binary files a/project/draft.odt and /dev/null differ diff --git a/scripts/cases/bugs-code.xreate b/scripts/cases/bugs-code.xreate index ebd32b6..dd8875a 100644 --- a/scripts/cases/bugs-code.xreate +++ b/scripts/cases/bugs-code.xreate @@ -1,33 +1,32 @@ - //unsafe code propagation rule rule: (X: function, Y: function) case X call Y, -X tag suppress(unsafe_propagation_warning) { warning Y tag unsafe -> X tag unsafe message "safe function should not call unsafe code" } //bugs propagation rule rule: (X: function, Y: function) case X call Y, - X tag suppress(bugs_propagation_warnings) { warning Y tag bug(no(No)) -> X tag bug(no(No)) message "Function should declare bugs it aware of" } -testfunc3 = function: (a: num, b: num)->num , unsafe, bug(no(1273)) //function tags list +testfunc3 = function: (a: num, b: num)->num,unsafe, bug(no(1273)) //function tags list { x = a+b: num; y = a - b: num; (x + y) / 2; } testfunc2 = function: (a: num)->bool // because of testfunc3 marked as unsafe code, // testfunc2 should be marked so too ,suppress(bugs_propagation_warnings), suppress(unsafe_propagation_warning) { b = testfunc3(a+1, a-1): num; (b==0); } \ No newline at end of file diff --git a/scripts/input.xreate b/scripts/input.xreate index 971d3f0..d588ab6 100644 --- a/scripts/input.xreate +++ b/scripts/input.xreate @@ -1,65 +1,28 @@ - -//unsafe code propagation rule -rule: (X: function, Y: function) -case X call Y - { - warning Y tag unsafe -> X tag unsafe - message "safe function should not call unsafe code" - } - -//unsafe code propagation rule -rule: (X: function, Y: function) -case X call Y - { - warning Y tag bug(no(No)) -> X tag bug(no(No)) - message "Function should declare bugs it aware of" - } - -testfunc3 = function: (a: num, b: num)->num , unsafe, bug(no(1273)) //function tags list -{ - x = a+b: num; - y = a - b: num; - - (x + y) / 2; +pass(dfa) { + operator map: (op(seqaccess)) -> impl(llvm_array); + operator list_range: ()->impl(on_the_fly); + operator list: ()->impl(llvm_const_array); + operator fold: (op(seqaccess)); + operator index: (op(randaccess)); + /* operator map: (op(seqaccess)) -> impl(llvm_array | on_the_fly); */ } -testfunc2 = function: (a: num)->bool // because of testfunc3 marked as unsafe code, - // testfunc2 should be marked so too -{ - b = testfunc3(a+1, a-1): num; - (b==0); -} +import raw("core/containers.lp"); + testfunc4 = function: ()->bool { - a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : [num]; - b = [1, 3, 2]: [num]; - - (a[1]==b[2]); -} + a1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : [num]; + a2 = [1 .. 100] : [num]; -/* -find6 = function: bool -{ - x = [1, 2, 3, 4, 5, 6, 7]: [num]; //эффективная инициализация - y = map (x) [el]-> {2 * el}; + b = loop map (a1 -> el: num) : [num] + {2 * el;}; + + c = b : [num]; + d = loop fold (a2->el: num, 0->acc: num): [num] + {acc + el;}; - y = loop map (x->el: num ): [num] - { - 2 * el; - } - - - exists(y, 12); + c[5]==d; } -exists = function: (list:[a], el: a)->bool -{ - acc: bool; - acc = reduce(list, false) [el, acc] -> - { - acc = acc & (el == e): saturated(true); - } -} -*/