diff --git a/coco/xreate.ATG b/coco/xreate.ATG index 61a41af..8b39f34 100644 --- a/coco/xreate.ATG +++ b/coco/xreate.ATG @@ -1,550 +1,570 @@ //TODO add ListLiteral //TODO ExprTyped: assign default(none) type #include "ast.h" #include "ExternLayer.h" #include #include #define wprintf(format, ...) \ char __buffer[100]; \ wcstombs(__buffer, format, 100); \ fprintf(stderr, __buffer, __VA_ARGS__) using namespace xreate; using namespace std; + COMPILER Xreate xreate::AST root; // current program unit struct { std::stack scopesOld; xreate::CodeScope* scope = nullptr; } context; void pushContextScope(CodeScope* scope){ context.scopesOld.push(context.scope); context.scope = scope; } void popContextScope(){ context.scope = context.scopesOld.top(); context.scopesOld.pop(); } -int skipIdent() +int nextToken() { - int kind = 0; scanner->ResetPeek(); - while ((kind = scanner->Peek()->kind) == _colon) - if (scanner->Peek()->kind != _ident) - return 0; - - return kind; + return scanner->Peek()->kind; } bool checkParametersList() { - return la->kind == _ident && skipIdent() == _lparen; + return la->kind == _ident && nextToken() == _lparen; } bool checkInfix() { - return la->kind == _ident && skipIdent() == _ident; + return la->kind == _ident && nextToken() == _ident; } bool checkIndex() { - return la->kind == _ident && skipIdent() == _lbrack; + return la->kind == _ident && nextToken() == _lbrack; } bool checkFuncDecl() { if (la->kind != _ident) return false; - int xkind = skipIdent(); - Token* y = scanner->Peek(); - return xkind == _assign && (y->kind == _function || y->kind == _pre); + int token2 = nextToken(); + int token3 = scanner->Peek()->kind; + + return token2 == _assign && (token3 == _function || token3 == _pre); } bool checkAssignment() { + if (la->kind != _ident) return false; + scanner->ResetPeek(); - Token* x = scanner->Peek(); - return la->kind == _ident && x->kind == _assign; + int token2 = scanner->Peek()->kind; + if (token2 == _lcurbrack) { + scanner->Peek(); + int token3 = scanner->Peek()->kind; + if (token3 != _rcurbrack) return false; + + int token4 = scanner->Peek()->kind; + return token4 == _assign; + } + + return token2 == _assign; +} + +void recognizeIdentifier(Expression& i){ + if (!context.scope->recognizeIdentifier(i)){ + root.postponeIdentifier(context.scope, i); + } } CHARACTERS letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz". any = ANY - '"'. digit = "0123456789". cr = '\r'. lf = '\n'. tab = '\t'. TOKENS ident = (letter | '_') {letter | digit | '_'}. number = digit {digit}. string = '"' { any } '"'. function = "function". pre = "pre". lparen = '('. rparen = ')'. lbrack = '['. rbrack = ']'. lcurbrack = '{'. rcurbrack = '}'. equal = "==". assign = '='. implic = '-' '>'. colon = ':'. context = "context". tagcolon = "::". lse = "<=". lss = "<". gte = ">=". gtr = ">". ne1 = "!=". ne2= "<>". COMMENTS FROM "/*" TO "*/" NESTED COMMENTS FROM "//" TO lf IGNORE cr + lf + tab PRODUCTIONS Xreate = (. Function* function; .) -{ ( RuleDecl | InterfaceData | Imprt | ContextSection +{( RuleDecl + | InterfaceData | Imprt | ContextSection | IF(checkFuncDecl()) FDecl (. root.add(function); .) - | TDecl ) }. + | TDecl +)} (. root.recognizePostponedIdentifiers(); .) +. Ident -= ident {':' ident} (. name = t->val; .). += ident (. name = t->val; .). + +VarIdent += ident (. e = Expression(Atom(t->val)); .) + [ lcurbrack ( + ident (. SemErr(coco_string_create("var version as ident is not implemented yet")); .) + | number (. Attachments::put(e, Atom(t->val).get()); .) + ) rcurbrack ] . + FDecl = (. std::wstring fname; std::wstring argName; TypeAnnotation typIn; TypeAnnotation typOut; bool flagIsPrefunct = false; Expression binding; .) Ident assign [pre (. flagIsPrefunct = true; .)] function (. f = new Function(fname); f->isPrefunction = flagIsPrefunct; CodeScope* entry = f->getEntryScope(); .) ['(' Ident tagcolon ExprAnnotations (. f->addBinding(Atom(argName), move(binding)); .) {',' Ident tagcolon ExprAnnotations (. f->addBinding(Atom (argName), move(binding));.) } ')'] [ tagcolon ( IF(flagIsPrefunct) FnTag - | Type (. f->setReturnType(typOut); .) + | Type ) {';' FnTag }] BDecl (. entry->getBody().bindType(move(typOut));.) . ContextSection<>= (. Expression context; Function* f; .) "case" "context" tagcolon MetaSimpExpr lcurbrack { FDecl (. f->guardContext = context; root.add(f); .) } rcurbrack. /** * TYPES * */ TypeTerm = (. std::wstring tid; .) ("string" | "num" | "int" | "i8" | "i32" | "float" | "bool") (. typ = Atom(t->val); .) . Type = (. TypeAnnotation typ2; TypeAtom typ3; std::wstring tid, field; .) ( TList | TStruct | TypeTerm (. typ = TypeAnnotation(typ3); .) |IF (checkIndex()) Ident lbrack Ident (. typ = TypeAnnotation(TypeOperator::ACCESS, {}); typ.__valueCustom = Atom(tid).get(); typ.fields.push_back(Atom(field).get()); .) {',' Ident (. typ.fields.push_back(Atom(field).get()); .) } rbrack | Ident (. typ = TypeAnnotation(TypeOperator::CUSTOM, {}); typ.__valueCustom = Atom(tid).get(); .) ['(' Type (. typ.__operator = TypeOperator::CALL; typ.__operands.push_back(typ2); .) {',' Type (. typ.__operands.push_back(typ2); .) } ')'] ) . TList = (. TypeAnnotation ty; .) '[' Type (. typ = TypeAnnotation(TypeOperator::ARRAY, {ty}); .) {',' Type (. typ.__operator = TypeOperator::TUPLE; typ.__operands.push_back(ty); .) }']' . TStruct = (. TypeAnnotation t; std::wstring field; .) - '{' + lcurbrack Ident tagcolon Type (. typ = TypeAnnotation(TypeOperator::STRUCT, {t}); typ.fields.push_back(Atom(field).get()); .) {',' Ident tagcolon Type} (. typ.__operands.push_back(t); typ.fields.push_back(Atom(field).get()); .) - '}'. + rcurbrack. TDecl = (. std::wstring ttag; TypeAnnotation t, t1; std::wstring tname, arg; std::vector> args; .) Ident assign "type" ( "alias" Type (. root.add(move(t), Atom(tname)); .) | "variant" lparen Ident (. t = TypeAnnotation(TypeOperator::VARIANT, {}); args.push_back(Atom(arg)); .) {',' Ident (. args.push_back(Atom(arg)); .) } rparen (. t.addFields(move(args)); root.add(move(t), Atom(tname)); .) | Ident ['(' Ident (. args.push_back(Atom(arg)); .) {',' Ident (. args.push_back(Atom(arg)); .) } ')'] Type (. t.addBindings(move(args)); root.add(move(t), Atom(tname)); .) ) '.' . -VDecl = (. std::wstring vname; Expression e;.) -Ident assign ExprTyped (. f->addDeclaration(Atom(vname), move(e)); .) -. - ContextDecl = (. Expression tag; .) context tagcolon MetaSimpExpr (. scope->tags.push_back(tag); .) {';' MetaSimpExpr (. scope->tags.push_back(tag); .) }. +VDecl = (. std::wstring vname; Expression var, value;.) + VarIdent assign ExprTyped (. f->addDeclaration(move(var), move(value)); .) +. + //TODO forbid multiple body declaration (ExprTyped) -BDecl = '{' (. Expression body; pushContextScope(scope); - .) - { (RuleContextDecl | ContextDecl '.' - | IF(checkAssignment()) VDecl '.' - | ExprTyped (. scope->setBody(body); popContextScope();.) -)} '}'. +BDecl = lcurbrack (. Expression body; pushContextScope(scope); .) + {(IF(checkAssignment()) VDecl '.' + | RuleContextDecl + | ContextDecl'.' + | ExprTyped (. scope->setBody(body); .) + )} (. popContextScope(); .) + rcurbrack . IfDecl = (. Expression cond; ManagedScpPtr blockTrue = root.add(new xreate::CodeScope(context.scope)); ManagedScpPtr blockFalse = root.add(new xreate::CodeScope(context.scope)); .) "if" '(' Expr ')' (. e = Expression(Operator::IF, {cond}); .) tagcolon ExprAnnotations BDecl<&*blockTrue> "else" BDecl<&*blockFalse> (. e.addBlock(blockTrue); e.addBlock(blockFalse); .) . LoopDecl = (. Expression eIn, eAcc, eFilters; std::wstring varEl, varAcc, contextClass; Expression tagsEl; ManagedScpPtr block = root.add(new xreate::CodeScope(context.scope)); .) "loop" ("map" '(' Expr implic Ident (. e = Expression(Operator::MAP, {eIn}); .) tagcolon ExprAnnotations ')' tagcolon ExprAnnotations BDecl<&*block> (. e.addBindings({Atom(varEl)}); block->addBinding(Atom(varEl), move(tagsEl)); e.addBlock(block); .) |"fold" ("inf" '(' Expr implic Ident ')' (. e = Expression(Operator::FOLD_INF, {eAcc}); e.addBindings({Atom(varAcc)}); .) tagcolon ExprAnnotations BDecl<&*block> (. block->addBinding(Atom(varAcc), Expression()); e.addBlock(block); .) | '(' Expr implic Ident tagcolon ExprAnnotations ['|' Expr ] ',' Expr implic Ident')' (. e = Expression(Operator::FOLD, {eIn, eAcc}); e.addBindings({Atom(varEl), Atom(varAcc)}); .) tagcolon ExprAnnotations BDecl<&*block> (. block->addBinding(Atom(varEl), move(tagsEl)); block->addBinding(Atom(varAcc), Expression()); e.addBlock(block); .) ) | "context" '(' string (. contextClass = t->val; .) ')' BDecl<&*block> (. e = Expression(Operator::LOOP_CONTEXT, {Expression(Atom(std::move(contextClass)))}); e.addBlock(block); .) ). SwitchDecl = (. TypeAnnotation typ; eSwitch = Expression(Operator::SWITCH, {}); Expression eCondition; Expression tag;.) ["switch" ( "ad" "hoc" lparen Expr tagcolon MetaSimpExpr rparen (. eSwitch.op = Operator::SWITCH_ADHOC; eSwitch.operands.push_back(eCondition); eSwitch.tags.emplace(tag.getValueString(), move(tag)); .) | lparen Expr rparen tagcolon ExprAnnotations (. eSwitch.operands.push_back(eCondition);.) ) ] CaseDecl {CaseDecl} . CaseDecl = (. ManagedScpPtr scope = root.add(new xreate::CodeScope(context.scope)); .) "case" ( "default" BDecl<&*scope> (. Expression exprCase(Operator::CASE_DEFAULT, {}); exprCase.addBlock(scope); outer.operands.insert(++outer.operands.begin(), exprCase); .) | CaseParams<&*scope> (. ManagedScpPtr scopeBody = root.add(new xreate::CodeScope(&*scope)); .) BDecl<&*scopeBody> (. Expression exprCase(Operator::CASE, {}); exprCase.addBlock(scope); exprCase.addBlock(scopeBody); outer.addArg(move(exprCase)); .) ). -CaseParams = (. Expression e; Expression guard(Operator::LOGIC_AND, {}); pushContextScope(scope); .) - CaseParam - {',' CaseParam - } (. scope->setBody(guard); popContextScope(); .). - -CaseParam = (. Expression condition; .) - ( - IF(checkAssignment()) VDecl - | ExprTyped (. guard.addArg(move(condition)); .) - ). - -SequenceDecl = -"sequence" ListLiteral (. sequence.setOp(Operator::SEQUENCE); .). - +CaseParams = (. Expression condition; Expression guard(Operator::LOGIC_AND, {}); pushContextScope(scope); .) + ExprTyped (. guard.addArg(Expression(condition)); .) + {',' ExprTyped (. guard.addArg(Expression(condition)); .) + } (. scope->setBody(guard); popContextScope(); .). + /*============================ INTERFACES ===============================*/ Imprt<> = "import" "raw" lparen string (. root.__rawImports.push_back(Atom(t->val).get()); .) rparen . InterfaceData<> = "interface" '(' ( "dfa" ')' InterfaceDFA | "extern-c" ')' InterfaceExternC | "cfa" ')' InterfaceCFA | "adhoc" ')' InterfaceAdhoc ). InterfaceAdhoc<> = '{' [ PrefunctionSchemeDecl ] '}'. PrefunctionSchemeDecl<> = (. TypeAnnotation typReturn; std::wstring prefName; Expression exprCases; .) pre function Ident tagcolon Type '{' SwitchDecl '}' (. Expression prefData(Operator::CALL, {Atom(prefName), exprCases}); prefData.type = typReturn; root.addInterfaceData(Adhoc, move(prefData)); .). InterfaceExternC<> = (.xreate::ExternData data; .) '{' {IncludeExternDecl | LibExternDecl } '}' (. root.addExternData(move(data)); .) . LibExternDecl = (. std::wstring pkgname, libname; .) Ident assign "library" tagcolon "pkgconfig" '(' string (. pkgname = t->val; .) ')' '.' (. data.addLibrary(Atom(libname), Atom(pkgname)); .) . IncludeExternDecl = (. Expression inc; .) "include" StructLiteral '.' (. data.addIncludeDecl(move(inc)); .) . InterfaceDFA<> = '{' { InstructDecl } '}' . InstructDecl = (.Operator op; Expression tag; Expression scheme; std::vector& tags = scheme.operands; tags.push_back(Expression()); /* return value */ .) "operator" InstructAlias tagcolon '(' (.scheme.setOp(op); .) [ MetaSimpExpr (. tags.push_back(tag); .) { ',' MetaSimpExpr (. tags.push_back(tag); .) } ] ')' [ implic MetaSimpExpr (. tags[0] = tag; .) ] (. root.addDFAData(move(scheme)); .) '.'. InstructAlias = ( "map" (. op = Operator::MAP; .) | "list_range" (. op = Operator::LIST_RANGE; .) | "list" (. op = Operator::LIST; .) | "fold" (. op = Operator::FOLD; .) | "index" (. op = Operator::INDEX; .) ). InterfaceCFA<> = '{' { InstructCFADecl } '}' . InstructCFADecl<> = (.Operator op; Expression tag; Expression scheme; std::vector& tags = scheme.operands; .) "operator" InstructAlias tagcolon (. scheme.setOp(op); .) [ MetaSimpExpr (. tags.push_back(tag); .) { ',' MetaSimpExpr (. tags.push_back(tag); .) } ] '.' (. root.addInterfaceData(CFA, move(scheme)); .). /*============================ METAPROGRAMMING ===============================*/ // TagsDecl = (. Expression tag; TagModifier mod = TagModifier::NONE; .) // ':' { MetaSimpExpr (. /*f.addTag(std::move(tag), mod); */ .) // }. FnTag = (. Expression tag; TagModifier mod = TagModifier::NONE; .) MetaSimpExpr ['-' TagMod] (. f->addTag(std::move(tag), mod); .). TagMod = ( "assert" (. mod = TagModifier::ASSERT; .) | "require" (. mod = TagModifier::REQUIRE; .) ). RuleDecl<> = "rule" tagcolon (. RuleArguments args; RuleGuards guards; DomainAnnotation typ; std::wstring arg; .) '(' Ident tagcolon Domain (. args.add(arg, typ); .) {',' Ident tagcolon Domain (. args.add(arg, typ); .) } ')' ["case" RGuard {',' RGuard}] '{' RBody '}' . /* - TODO use RGuard for guards-*/ RuleContextDecl = (.Expression eHead, eGuards, eBody; .) "rule" "context" tagcolon MetaSimpExpr "case" MetaSimpExpr '{' MetaSimpExpr '}' (.scope->contextRules.push_back(Expression(Operator::CONTEXT_RULE, {eHead, eGuards, eBody})); .). 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 ===============================*/ ExprAnnotations = (. TypeAnnotation typ; Expression tag; e.tags.clear();.) Type (. e.bindType(move(typ)); .) {';' MetaSimpExpr (. e.tags.emplace(tag.getValueString(), tag); .) }. ExprTyped = Expr [tagcolon ExprAnnotations]. Expr< Expression& e> (. Operator op; Expression e2; .) -= SimExpr += ExprArithmAdd [ RelOp -SimExpr (. e = Expression(op, {e, e2}); .) + ExprArithmAdd (. e = Expression(op, {e, e2}); .) ]. -SimExpr< Expression& e> (. Operator op; Expression e2; .) -= Term< e> - { AddOp< op> - Term< e2> (. e = Expression(op, {e, e2});.) - }. +ExprArithmAdd< Expression& e>= (. Operator op; Expression e2; .) + ExprArithmMul< e> + [ AddOp< op> + ExprArithmAdd< e2> (. e = Expression(op, {e, e2});.) + ]. -Term< Expression& e> (. Operator op; Expression e2; .) -= Factor< e> - { MulOp< op> - Factor< e2> (. e = Expression(op, {e, e2}); .) - }. +ExprArithmMul< Expression& e> (. Operator op; Expression e2; .) += ExprPostfix< e> + [ MulOp< op> + ExprArithmMul< e2> (. e = Expression(op, {e, e2}); .) + ]. -Factor< Expression& e> (. std::wstring name; e = Expression(); .) +ExprPostfix += Term + [lbrack (. e = Expression(Operator::INDEX, {e}); .) + CalleeParams rbrack + ]. + + +Term< Expression& e> (. std::wstring name; e = Expression(); .) = (IF (checkParametersList()) Ident< name> (. e = Expression(Operator::CALL, {Atom(name)}); .) '(' [CalleeParams] ')' - |IF (checkIndex()) Ident - lbrack CalleeParams rbrack (. e.setOp(Operator::INDEX); e.setValue({Atom(name)}); .) - | Ident< name> (. e = Expression(Atom(name)); root.recognizeVariantIdentifier(e); .) + | VarIdent (. recognizeIdentifier(e); .) | ListLiteral (. /* tuple */.) | StructLiteral (. /* struct */.) - | SequenceDecl | LoopDecl - | IfDecl + | IfDecl | SwitchDecl | AdhocDecl - | number (. e = Expression(Atom(t->val)); .) | string (. e = Expression(Atom(t->val)); .) - | '-' Factor< e> (. e = Expression(Operator::NEG, {e}); .) + | '-' Term (. e = Expression(Operator::NEG, {e}); .) | '(' ExprTyped ')' ). StructLiteral = (. std::wstring key; Expression val; std::list> keys; .) '{' Ident '=' Expr (. keys.push_back(Atom(key)); e = Expression(Operator::LIST_NAMED, {val}); .) {',' Ident '=' Expr (.e.addArg(Expression(val)); keys.push_back(Atom(key)); .) } '}' (. e.addBindings(keys.begin(), keys.end()); .) . ListLiteral = (. Expression eFrom, eTo; .) '[' [ Expr (. e.addArg(Expression(eFrom)); .) (".." Expr (. e.addArg(Expression(eTo)); e.setOp(Operator::LIST_RANGE); .) |{',' Expr (. e.addArg(Expression(eFrom)); .) } (. e.setOp(Operator::LIST); .) ) ] ']'. AdhocDecl = (. Expression command; .) "ad" "hoc" Expr (. e.setOp(Operator::ADHOC); e.addArg(std::move(command)); .). CalleeParams = (. Expression e2; .) ExprTyped (. e.addArg(Expression(e2)); .) {',' ExprTyped (. e.addArg(Expression(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 | (ne1 | ne2) (. op = Operator::NE; .) | lse (. op = Operator::LSE; .) | lss (. op = Operator::LSS; .) | gte (. op = Operator::GTE; .) | gtr (. op = Operator::GTR; .) ). END Xreate. diff --git a/cpp/src/CMakeLists.txt b/cpp/src/CMakeLists.txt index e51bf9c..0e79032 100644 --- a/cpp/src/CMakeLists.txt +++ b/cpp/src/CMakeLists.txt @@ -1,210 +1,216 @@ cmake_minimum_required(VERSION 2.8.11) project(xreate) cmake_policy(SET CMP0022 NEW) message("MODULES" ${CMAKE_MODULE_PATH}) # LLVM #====================== FIND_PACKAGE (LLVM REQUIRED) set(LLVM_VERSION ${LLVM_VERSION_MAJOR}.${LLVM_VERSION_MINOR}) message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}") message("LLVM LIB PATH:" ${LLVM_LIBRARY_DIRS}) message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}") INCLUDE_DIRECTORIES(${LLVM_INCLUDE_DIRS}) message(STATUS "INCLUDE DIR: ${LLVM_INCLUDE_DIRS}") add_definitions(${LLVM_DEFINITIONS}) message("LLVM DEFS: " ${LLVM_DEFINITIONS}) llvm_map_components_to_libnames(LLVM_LIBS core nativecodegen native executionengine mcjit support option) message("LLVM LIBS: " ${LLVM_LIBS}) # CLANG #====================== set(CLANG_LIBS clangCodeGen clangASTMatchers clangQuery clangTooling clangFrontend clangSerialization clangDriver clangParse clangSema clangAnalysis clangAST clangEdit clangLex clangBasic ) # POTASSCO #====================== set(POTASSCO_PATH "/opt/potassco/clingo" CACHE PATH "Path to potassco sources") set(POTASSCO_INCLUDE_PATH ${POTASSCO_PATH}/libgringo ${POTASSCO_PATH}/libclasp ${POTASSCO_PATH}/libclingo ${POTASSCO_PATH}/libprogram_opts ${POTASSCO_PATH}/liblp ) INCLUDE_DIRECTORIES(${POTASSCO_INCLUDE_PATH}) set(LIBCLASP_LIBS clingo clasp gringo program_opts reify lp ) message("CLASP LIBS: " ${LIBCLASP_LIBS}) # OTHER DEPENDENCIES #=========================== set(JEAYESON_INCLUDE_PATH ${CMAKE_HOME_DIRECTORY}/../vendors/jeayeson/include/ ) INCLUDE_DIRECTORIES(${JEAYESON_INCLUDE_PATH}) # COCO #=========================== set(COCO_EXECUTABLE "" CACHE PATH "Path to coco executable") +set(COCO_FRAMES_PATH "" CACHE PATH "Path to coco frames") set(COCO_GRAMMAR_PATH ${CMAKE_HOME_DIRECTORY}/../coco/) set(COCO_SOURCE_FILES ${COCO_GRAMMAR_PATH}/Parser.cpp ${COCO_GRAMMAR_PATH}/Scanner.cpp) INCLUDE_DIRECTORIES(${COCO_GRAMMAR_PATH}) add_custom_command(OUTPUT ${COCO_SOURCE_FILES} - COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar ${COCO_EXECUTABLE} + COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/xreate.ATG ) message(STATUS "COCO GRAMMAR BUILD STATUS:" ${COCO_OUTPUT}) # XREATE #====================== set(SOURCE_FILES - pass/compilepass.cpp - ast.cpp - ExternLayer.cpp - attachments.cpp - analysis/cfagraph.cpp - analysis/dfagraph.cpp - analysis/aux.cpp - compilation/containers.cpp - compilation/advanced.cpp - compilation/transformations.cpp - clasplayer.cpp - compilation/latecontextcompiler2.cpp - query/context.cpp - #compilation/latecontextcompiler.cpp - serialization/expressionserializer2.cpp - llvmlayer.cpp - utils.cpp - passmanager.cpp - pass/abstractpass.cpp pass/dfapass.cpp - pass/cfapass.cpp - pass/adhocpass.cpp - contextrule.cpp - query/containers.cpp - pass/loggerpass.cpp - pass/interpretationpass.cpp - serialization/expressionserializer.cpp - compilation/targetinterpretation.cpp - analysis/DominatorsTreeAnalysisProvider.cpp + +# attachments.cpp +# ast.cpp +# pass/compilepass.cpp + +# ExternLayer.cpp + +# analysis/cfagraph.cpp +# analysis/dfagraph.cpp +# analysis/aux.cpp +# compilation/containers.cpp +# compilation/advanced.cpp +# compilation/transformations.cpp +# clasplayer.cpp +# compilation/latecontextcompiler2.cpp +# query/context.cpp +# #compilation/latecontextcompiler.cpp +# serialization/expressionserializer2.cpp +# llvmlayer.cpp + utils.cpp +# passmanager.cpp +# pass/abstractpass.cpp pass/dfapass.cpp +# pass/cfapass.cpp +# pass/adhocpass.cpp +# contextrule.cpp +# query/containers.cpp +# #pass/loggerpass.cpp +# pass/interpretationpass.cpp +# serialization/expressionserializer.cpp +# compilation/targetinterpretation.cpp +# analysis/DominatorsTreeAnalysisProvider.cpp #query/ptrvalid.cpp #pass/rulespass.cpp # ) set(XREATE_INCLUDE_DIRS ${CMAKE_CURRENT_SOURCE_DIR}/ ) INCLUDE_DIRECTORIES(${XREATE_INCLUDE_DIRS}) set(XREATE_PRIVATE_INCLUDE_DIRS ${XREATE_INCLUDE_DIRS} ${COCO_GRAMMAR_PATH} ${JEAYESON_INCLUDE_PATH} ${LLVM_INCLUDE_DIRS} ${POTASSCO_INCLUDE_PATH} ) -add_library(${PROJECT_NAME} SHARED ${SOURCE_FILES} ${COCO_SOURCE_FILES}) +add_library(${PROJECT_NAME} SHARED ${SOURCE_FILES} ) +#${COCO_SOURCE_FILES} + target_link_libraries(${PROJECT_NAME}) target_include_directories(${PROJECT_NAME} INTERFACE ${XREATE_INCLUDE_DIRS} ${COCO_GRAMMAR_PATH} ${JEAYESON_INCLUDE_PATH} ${LLVM_INCLUDE_DIRS} ${POTASSCO_INCLUDE_PATH} ) get_directory_property(DEFINITIONS_ALL DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR} COMPILE_DEFINITIONS) message("definitions all: " ${DEFINITIONS_ALL}) target_compile_definitions(${PROJECT_NAME} INTERFACE ${DEFINITIONS_ALL}) get_directory_property(COMPILATION_OPTIONS_ALL DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR} COMPILE_OPTIONS) message("compilations all: " ${COMPILATION_OPTIONS_ALL}) target_compile_options(${PROJECT_NAME} INTERFACE ${COMPILATION_OPTIONS_ALL}) SET_PROPERTY(TARGET ${PROJECT_NAME} PROPERTY INTERFACE_LINK_LIBRARIES ${LIBCLASP_LIBS} ${CLANG_LIBS} ${LLVM_LIBS} tbb ) #${CLANG_LIBS} #set (LINK_INTERFACE_LIBRARIES "") # FUNCTION(PREPEND var prefix) # SET(listVar "") # FOREACH(f ${ARGN}) # LIST(APPEND listVar "${prefix}/${f}") # ENDFOREACH(f) # SET(${var} "${listVar}" PARENT_SCOPE) # ENDFUNCTION(PREPEND) #set(COTIRE_UNITY_SOURCE_MAXIMUM_NUMBER_OF_INCLUDES "-j4") #cotire(xreate) # MACRO (ADD_PCH_RULE _header_filename _src_list) # SET(_gch_filename "${_header_filename}.gch") # LIST(APPEND ${_src_list} ${_gch_filename}) # SET (_args ${CMAKE_CXX_FLAGS}) # LIST(APPEND _args -c ${_header_filename} -o ${_gch_filename}) # GET_DIRECTORY_PROPERTY(DIRINC INCLUDE_DIRECTORIES) # foreach (_inc ${DIRINC}) # LIST(APPEND _args "-I" ${_inc}) # endforeach(_inc ${DIRINC}) # SEPARATE_ARGUMENTS(_args) # add_custom_command(OUTPUT ${_gch_filename} # COMMAND rm -f ${_gch_filename} # COMMAND ${CMAKE_CXX_COMPILER} ${CMAKE_CXX_COMPILER_ARG1} ${_args} # DEPENDS ${_header_filename}) # ENDMACRO(ADD_PCH_RULE _header_filename _src_list) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/ast.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/llvmlayer.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/clasplayer.h SOURCE_FILES) # ADD_PCH_RULE (${CMAKE_HOME_DIRECTORY}/src/pass/abstractpass.h SOURCE_FILES) diff --git a/cpp/src/ast.cpp b/cpp/src/ast.cpp index 0ae05a9..918bb75 100644 --- a/cpp/src/ast.cpp +++ b/cpp/src/ast.cpp @@ -1,816 +1,833 @@ #include "ast.h" #include "ExternLayer.h" #include #include -#include + +namespace std{ + + std::size_t + hash::operator()(xreate::ScopedSymbol const& s) const + {return s.id ^ (s.version << 2);} + + bool + equal_to::operator()(const xreate::ScopedSymbol& __x, const xreate::ScopedSymbol& __y) const + { return __x.id == __y.id && __x.version == __y.version; } +} using namespace std; -namespace xreate{ -class ExpressionHints{ -public: - static bool - isStringValueValid(const Expression& e){ - switch (e.__state){ - case Expression::INVALID: - case Expression::VARIANT: - assert(false); +namespace xreate { - case Expression::IDENT: - case Expression::STRING: - return true; + class ExpressionHints { + public: - case Expression::NUMBER: - case Expression::BINDING: - return false; + static bool + isStringValueValid(const Expression& e) { + switch (e.__state) { + case Expression::INVALID: + case Expression::VARIANT: + assert(false); - case Expression::COMPOUND: { - switch (e.op){ - case Operator::CALL: - case Operator::INDEX: - return true; + case Expression::IDENT: + case Expression::STRING: + return true; - default: return false; + case Expression::NUMBER: + case Expression::BINDING: + return false; + + case Expression::COMPOUND: + { + switch (e.op) { + case Operator::CALL: + return true; + + default: return false; + } } } + + return false; } - return false; - } + static bool + isDoubleValueValid(const Expression& e) { + switch (e.__state) { + case Expression::NUMBER: + return true; + + case Expression::INVALID: + case Expression::VARIANT: + assert(false); + + case Expression::IDENT: + case Expression::STRING: + case Expression::COMPOUND: + case Expression::BINDING: + return false; + } - static bool - isDoubleValueValid(const Expression& e){ - switch (e.__state){ - case Expression::NUMBER: - return true; + return false; + } + }; - case Expression::INVALID: - case Expression::VARIANT: - assert(false); + class TypesResolver { + private: + const AST* ast; + std::map scope; + std::map signatures; - case Expression::IDENT: - case Expression::STRING: - case Expression::COMPOUND: - case Expression::BINDING: - return false; + ExpandedType expandType(const TypeAnnotation &t, const std::vector &args = std::vector()) { + return TypesResolver(ast, scope, signatures)(t, args); } - return false; - } -}; + std::vector + expandOperands(const std::vector& operands) { + std::vector pack; -class TypesResolver { -private: - const AST* ast; - std::map scope; - std::map signatures; + pack.reserve(operands.size()); + std::transform(operands.begin(), operands.end(), std::inserter(pack, pack.end()), + [this](const TypeAnnotation & t) { + return expandType(t); + }); + return pack; + } - ExpandedType expandType(const TypeAnnotation &t, const std::vector &args = std::vector()){ - return TypesResolver(ast, scope, signatures)(t, args); - } + public: - std::vector - expandOperands(const std::vector& operands) { - std::vector pack; - - pack.reserve(operands.size()); - std::transform(operands.begin(), operands.end(), std::inserter(pack, pack.end()), - [this](const TypeAnnotation& t){ - return expandType(t); - }); - - return pack; - } - -public: - TypesResolver(const AST* root, const std::map& scopeOuter = std::map(), - std::map signaturesOuter = std::map()) - : ast(root), scope(scopeOuter), signatures(signaturesOuter) { - } + TypesResolver(const AST* root, const std::map& scopeOuter = std::map(), + std::map signaturesOuter = std::map()) + : ast(root), scope(scopeOuter), signatures(signaturesOuter) { + } + ExpandedType + operator()(const TypeAnnotation &t, const std::vector &args = std::vector()) { + //assert(args.size() == t.bindings.size()); // invalid number of arguments + for (size_t i = 0; i < args.size(); ++i) { + scope[t.bindings.at(i)] = args.at(i); + } + switch (t.__operator) { + case TypeOperator::ARRAY: + { + assert(t.__operands.size() == 1); - ExpandedType - operator()(const TypeAnnotation &t, const std::vector &args = std::vector()) - { - //assert(args.size() == t.bindings.size()); // invalid number of arguments - for (size_t i=0; i elTy = expandType(t.__operands.at(0)); + return ExpandedType(TypeAnnotation(tag_array, elTy, 0)); + } - Expanded elTy = expandType(t.__operands.at(0)); - return ExpandedType(TypeAnnotation(tag_array, elTy, 0)); - } + case TypeOperator::STRUCT: + { + assert(t.__operands.size()); - case TypeOperator::STRUCT: - { - assert(t.__operands.size()); + std::vector&& pack = expandOperands(t.__operands); + auto tnew = TypeAnnotation(TypeOperator::STRUCT, move(pack)); + tnew.fields = t.fields; - std::vector&& pack = expandOperands(t.__operands); - auto tnew = TypeAnnotation(TypeOperator::STRUCT, move(pack)); - tnew.fields = t.fields; + return ExpandedType(move(tnew)); + }; - return ExpandedType(move(tnew)); - }; + case TypeOperator::CALL: + { + std::string alias = t.__valueCustom; - case TypeOperator::CALL: - { - std::string alias = t.__valueCustom; + //find in local scope: + TypeAnnotation ty; + if (scope.count(alias)) { + ty = scope.at(alias); - //find in local scope: - TypeAnnotation ty; - if (scope.count(alias)) { - ty = scope.at(alias); + } else if (ast->__indexTypeAliases.count(alias)) { + ty = ast->__indexTypeAliases.at(alias); - } else if (ast->__indexTypeAliases.count(alias)){ - ty = ast->__indexTypeAliases.at(alias); + } else { + assert(false && "Undefined or external type"); + } - } else { - assert(false && "Undefined or external type"); - } + std::vector&& operands = expandOperands(t.__operands); + TypeAnnotation signature(TypeOperator::CALL, move(operands)); + signature.__valueCustom = alias; - std::vector&& operands = expandOperands(t.__operands); - TypeAnnotation signature(TypeOperator::CALL, move(operands)); - signature.__valueCustom = alias; + if (signatures.count(signature)) { + auto link = TypeAnnotation(TypeOperator::LINK,{}); + link.conjuctionId = signatures.at(signature); - if (signatures.count(signature)) { - auto link = TypeAnnotation(TypeOperator::LINK, {}); - link.conjuctionId = signatures.at(signature); + return ExpandedType(move(link)); + } - return ExpandedType(move(link)); - } + int cid = signatures.size(); + signatures[signature] = cid; + TypeAnnotation tyResult = expandType(ty, operands); + tyResult.conjuctionId = cid; - int cid = signatures.size(); - signatures[signature] = cid; - TypeAnnotation tyResult = expandType(ty, operands); - tyResult.conjuctionId = cid; + return ExpandedType(move(tyResult)); + }; - return ExpandedType(move(tyResult)); - }; + case TypeOperator::CUSTOM: + { + std::string alias = t.__valueCustom; - case TypeOperator::CUSTOM: - { - std::string alias = t.__valueCustom; - - /* - if (signatures.count(alias)) { - return ExpandedType(TypeAnnotation(TypeOperator::LINK, {t})); - } - signatures[alias].emplace(t); - */ - - //find in local scope: - if (scope.count(alias)) - { - return expandType(scope.at(alias)); - } - - // find in general scope: - if(ast->__indexTypeAliases.count(alias)) { - return expandType(ast->__indexTypeAliases.at(t.__valueCustom)); - } - - //if type is unknown keep it as is. - return ExpandedType(TypeAnnotation(t)); - }; - - case TypeOperator::ACCESS: - { - std::string alias = t.__valueCustom; - ExpandedType tyAlias= ExpandedType(TypeAnnotation()); + /* + if (signatures.count(alias)) { + return ExpandedType(TypeAnnotation(TypeOperator::LINK, {t})); + } + signatures[alias].emplace(t); + */ - //find in local scope: - if (scope.count(alias)) { - tyAlias = expandType(scope.at(alias)); - - //find in global scope: - } else if((ast->__indexTypeAliases.count(alias))) { - tyAlias = expandType(ast->__indexTypeAliases.at(alias)); - - } else { - assert(false && "Undefined or external type"); - } + //find in local scope: + if (scope.count(alias)) { + return expandType(scope.at(alias)); + } - assert(tyAlias->__operator == TypeOperator::STRUCT); - - for (const string& field: t.fields){ - auto fieldIt = std::find(tyAlias->fields.begin(), tyAlias->fields.end(), field); - assert(fieldIt != tyAlias->fields.end() && "unknown field"); + // find in general scope: + if (ast->__indexTypeAliases.count(alias)) { + return expandType(ast->__indexTypeAliases.at(t.__valueCustom)); + } - int fieldId = fieldIt - tyAlias->fields.begin(); - tyAlias = expandType(tyAlias->__operands.at(fieldId)); - } + //if type is unknown keep it as is. + return ExpandedType(TypeAnnotation(t)); + }; - return tyAlias; - } + case TypeOperator::ACCESS: + { + std::string alias = t.__valueCustom; + ExpandedType tyAlias = ExpandedType(TypeAnnotation()); - case TypeOperator::TUPLE: { - assert(t.__operands.size()); + //find in local scope: + if (scope.count(alias)) { + tyAlias = expandType(scope.at(alias)); - std::vector pack; - pack.reserve(t.__operands.size()); + //find in global scope: + } else if ((ast->__indexTypeAliases.count(alias))) { + tyAlias = expandType(ast->__indexTypeAliases.at(alias)); - std::transform(t.__operands.begin(), t.__operands.end(), std::inserter(pack, pack.end()), - [this](const TypeAnnotation& t){ - return expandType(t); - }); + } else { + assert(false && "Undefined or external type"); + } - return ExpandedType(TypeAnnotation(TypeOperator::TUPLE, move(pack))); - } - - case TypeOperator::VARIANT: { - return ExpandedType(TypeAnnotation(t)); - } + assert(tyAlias->__operator == TypeOperator::STRUCT); - case TypeOperator::NONE: { - return ExpandedType(TypeAnnotation(t)); - } - - default: - assert(false); - } - - assert(false); - return ExpandedType(TypeAnnotation()); - } -}; + for (const string& field : t.fields) { + auto fieldIt = std::find(tyAlias->fields.begin(), tyAlias->fields.end(), field); + assert(fieldIt != tyAlias->fields.end() && "unknown field"); -TypeAnnotation::TypeAnnotation() -{ -} + int fieldId = fieldIt - tyAlias->fields.begin(); + tyAlias = expandType(tyAlias->__operands.at(fieldId)); + } -TypeAnnotation::TypeAnnotation(const Atom &typ) - : __value(typ.get()) -{ - ; -} + return tyAlias; + } -TypeAnnotation::TypeAnnotation (TypePrimitive typ) - : __value(typ) -{} + case TypeOperator::TUPLE: + { + assert(t.__operands.size()); -TypeAnnotation::TypeAnnotation(TypeOperator op, std::initializer_list operands) - : __operator(op), __operands(operands) -{ + std::vector pack; + pack.reserve(t.__operands.size()); -} + std::transform(t.__operands.begin(), t.__operands.end(), std::inserter(pack, pack.end()), + [this](const TypeAnnotation & t) { + return expandType(t); + }); -TypeAnnotation::TypeAnnotation (TypeOperator op, std::vector&& operands) - : __operator(op), __operands(operands) -{} + return ExpandedType(TypeAnnotation(TypeOperator::TUPLE, move(pack))); + } + case TypeOperator::VARIANT: + { + return ExpandedType(TypeAnnotation(t)); + } -TypeAnnotation::TypeAnnotation (llvm_array_tag, TypeAnnotation typ, int size) - :TypeAnnotation(TypeOperator::ARRAY, {typ}) -{ - __size=size; -} + case TypeOperator::NONE: + { + return ExpandedType(TypeAnnotation(t)); + } -bool -TypeAnnotation::operator< (const TypeAnnotation& t) const{ - if (__operator != t.__operator) return __operator < t.__operator; + default: + assert(false); + } - if (__operator == TypeOperator::NONE) - return __value < t.__value; + assert(false); + return ExpandedType(TypeAnnotation()); + } + }; - if (__operator == TypeOperator::CALL || __operator == TypeOperator::CUSTOM || __operator == TypeOperator::ACCESS){ - if (__valueCustom != t.__valueCustom) - return __valueCustom < t.__valueCustom; - } + TypeAnnotation::TypeAnnotation() { + } - return __operands < t.__operands; -} + TypeAnnotation::TypeAnnotation(const Atom &typ) + : __value(typ.get()) { + ; + } -/* -TypeAnnotation (struct_tag, std::initializer_list) -{} -*/ + TypeAnnotation::TypeAnnotation(TypePrimitive typ) + : __value(typ) { + } -void -TypeAnnotation::addBindings(std::vector>&& params) -{ - bindings.reserve(bindings.size() + params.size()); + TypeAnnotation::TypeAnnotation(TypeOperator op, std::initializer_list operands) + : __operator(op), __operands(operands) { - std::transform(params.begin(), params.end(), std::inserter(bindings, bindings.end()), - [](const Atom& ident){return ident.get(); }); -} + } + + TypeAnnotation::TypeAnnotation(TypeOperator op, std::vector&& operands) + : __operator(op), __operands(operands) { + } -void -TypeAnnotation::addFields(std::vector>&& listFields) -{ - fields.reserve(fields.size() + listFields.size()); + TypeAnnotation::TypeAnnotation(llvm_array_tag, TypeAnnotation typ, int size) + : TypeAnnotation(TypeOperator::ARRAY,{typ}) { + __size = size; + } - std::transform(listFields.begin(), listFields.end(), std::inserter(fields, fields.end()), - [](const Atom& ident){return ident.get(); }); -} + bool + TypeAnnotation::operator<(const TypeAnnotation& t) const { + if (__operator != t.__operator) return __operator < t.__operator; -Expression::Expression(const Atom& number) -: __state(NUMBER), op(Operator::NONE), __valueD(number.get()) -{ -} + if (__operator == TypeOperator::NONE) + return __value < t.__value; -Expression::Expression(const Atom& a) - : __state(STRING), op(Operator::NONE), __valueS(a.get()) -{ -} + if (__operator == TypeOperator::CALL || __operator == TypeOperator::CUSTOM || __operator == TypeOperator::ACCESS) { + if (__valueCustom != t.__valueCustom) + return __valueCustom < t.__valueCustom; + } -Expression::Expression(const Atom &ident) - : __state(IDENT), op(Operator::NONE), __valueS(ident.get()) -{ -} + return __operands < t.__operands; + } -Expression::Expression(const Operator &oprt, std::initializer_list params) - : __state(COMPOUND), op(oprt) -{ - if (op == Operator::CALL) - { - assert(params.size() > 0); - Expression arg = *params.begin(); + /* + TypeAnnotation (struct_tag, std::initializer_list) + {} + */ - assert(arg.__state == Expression::IDENT); - __valueS = std::move(arg.__valueS); + void + TypeAnnotation::addBindings(std::vector>&& params) { + bindings.reserve(bindings.size() + params.size()); - operands.insert(operands.end(), params.begin()+1, params.end()); - return; + std::transform(params.begin(), params.end(), std::inserter(bindings, bindings.end()), + [](const Atom& ident) { + return ident.get(); }); } - operands.insert(operands.end(), params.begin(), params.end()); -} + void + TypeAnnotation::addFields(std::vector>&& listFields) { + fields.reserve(fields.size() + listFields.size()); -void -Expression::setOp(Operator oprt) -{ - op = oprt; + std::transform(listFields.begin(), listFields.end(), std::inserter(fields, fields.end()), + [](const Atom& ident) { + return ident.get(); }); + } - switch (op) - { - case Operator::NONE: - __state = INVALID; - break; + unsigned int Expression::nextVacantId = 0; - default: - __state = COMPOUND; - break; + Expression::Expression(const Atom& number) + : Expression() { + __state=NUMBER; op=Operator::NONE; __valueD=number.get(); } -} -void -Expression::addArg(Expression &&arg) -{ - operands.push_back(arg); -} + Expression::Expression(const Atom& a) + : Expression(){ + __state=STRING; op=Operator::NONE; __valueS=a.get(); + } -void -Expression::addBindings(std::initializer_list> params) -{ - addBindings(params.begin(), params.end()); -} + Expression::Expression(const Atom &ident) + : Expression() { + __state=IDENT; op=Operator::NONE; __valueS=ident.get(); + } -void -Expression::bindType(TypeAnnotation t) -{ - type = move(t); -} + Expression::Expression(const Operator &oprt, std::initializer_list params) + : Expression() { + __state=COMPOUND; op=oprt; -void -Expression::addBlock(ManagedScpPtr scope) -{ - blocks.push_back(scope.operator ->()); -} + if (op == Operator::CALL) { + assert(params.size() > 0); + Expression arg = *params.begin(); -const std::vector& -Expression::getOperands() const -{ - return operands; -} + assert(arg.__state == Expression::IDENT); + __valueS = std::move(arg.__valueS); -double -Expression::getValueDouble() const -{ - return __valueD; -} + operands.insert(operands.end(), params.begin() + 1, params.end()); + return; + } -const std::string& -Expression::getValueString() const -{ - return __valueS; -} + operands.insert(operands.end(), params.begin(), params.end()); + } -void -Expression::setValue(const Atom&& v){ - __valueS = v.get(); -} + void + Expression::setOp(Operator oprt) { + op = oprt; -void Expression::setValueDouble(double value){ - __valueD = value; -} + switch (op) { + case Operator::NONE: + __state = INVALID; + break; -bool -Expression::isValid() const{ - return (__state != INVALID); -} + default: + __state = COMPOUND; + break; + } + } -bool -Expression::isDefined() const{ - return (__state != BINDING); -} + void + Expression::addArg(Expression &&arg) { + operands.push_back(arg); + } -Expression::Expression() - : __state(INVALID), op(Operator::NONE) -{} + void + Expression::addBindings(std::initializer_list> params) { + addBindings(params.begin(), params.end()); + } -bool -Expression::operator==(const Expression& other) const{ - assert(!this->blocks.size()); - assert(!other.blocks.size()); + void + Expression::bindType(TypeAnnotation t) { + type = move(t); + } - if (this->__state != other.__state) return false; + void + Expression::addBlock(ManagedScpPtr scope) { + blocks.push_back(scope.operator->()); + } - if (ExpressionHints::isStringValueValid(*this)){ - if (this->__valueS != other.__valueS) return false; + const std::vector& + Expression::getOperands() const { + return operands; } - if (ExpressionHints::isDoubleValueValid(*this)){ - if (this->__valueD != other.__valueD) return false; + double + Expression::getValueDouble() const { + return __valueD; } - if (this->__state != Expression::COMPOUND){ - return true; + const std::string& + Expression::getValueString() const { + return __valueS; } - if (this->operands.size() != other.operands.size()){ - return false; + void + Expression::setValue(const Atom&& v) { + __valueS = v.get(); } - for (size_t i=0; ioperands.size(); ++i){ - if (!(this->operands[i]==other.operands[i])) return false; + void Expression::setValueDouble(double value) { + __valueD = value; } - return true; -} + bool + Expression::isValid() const { + return (__state != INVALID); + } + bool + Expression::isDefined() const { + return (__state != BINDING); + } -AST::AST() -{ -} + Expression::Expression() + : __state(INVALID), op(Operator::NONE), id(nextVacantId++) + { } + bool + Expression::operator==(const Expression& other) const { + assert(!this->blocks.size()); + assert(!other.blocks.size()); -void -AST::addInterfaceData(const ASTInterface& interface, Expression&& data ) { - __interfacesData.emplace(interface, move(data)); -} + if (this->__state != other.__state) return false; -void -AST::addDFAData(Expression &&data) { - __dfadata.push_back(data); -} + if (ExpressionHints::isStringValueValid(*this)) { + if (this->__valueS != other.__valueS) return false; + } -void -AST::addExternData(ExternData &&data) { - __externdata.insert(__externdata.end(), data.entries.begin(), data.entries.end()); -} + if (ExpressionHints::isDoubleValueValid(*this)) { + if (this->__valueD != other.__valueD) return false; + } -void -AST::add(Function* f) -{ - __functions.push_back(f); - __indexFunctions.emplace(f->getName(), __functions.size()-1); -} + if (this->__state != Expression::COMPOUND) { + return true; + } -void -AST::add(MetaRuleAbstract *r) -{ - __rules.push_back(r); -} + if (this->operands.size() != other.operands.size()) { + return false; + } -void -AST::add(TypeAnnotation t, Atom alias){ - if (t.__operator == TypeOperator::VARIANT){ - for (int i=0, size=t.fields.size(); i< size; ++i){ - __dictVariants.emplace(t.fields[i], make_pair(t, i)); - } - } + for (size_t i = 0; ioperands.size(); ++i) { + if (!(this->operands[i] == other.operands[i])) return false; + } - __indexTypeAliases.emplace(alias.get(), move(t)); -} + return true; + } -ManagedScpPtr -AST::add(CodeScope* scope) -{ - this->__scopes.push_back(scope); - return ManagedScpPtr(this->__scopes.size()-1, &this->__scopes); -} + AST::AST() { + Attachments::init(); + Attachments::init(); + } -std::string -AST::getModuleName() -{ - const std::string name = "moduleTest"; + void + AST::addInterfaceData(const ASTInterface& interface, Expression&& data) { + __interfacesData.emplace(interface, move(data)); + } - return name; -} + void + AST::addDFAData(Expression &&data) { + __dfadata.push_back(data); + } -ManagedPtr -AST::findFunction(const std::string& name) -{ - int count = __indexFunctions.count(name); - if (!count) { - return ManagedFnPtr::Invalid(); + void + AST::addExternData(ExternData &&data) { + __externdata.insert(__externdata.end(), data.entries.begin(), data.entries.end()); } - assert(count ==1); + void + AST::add(Function* f) { + __functions.push_back(f); + __indexFunctions.emplace(f->getName(), __functions.size() - 1); + } - auto range = __indexFunctions.equal_range(name); - return ManagedPtr(range.first->second, &this->__functions); -} + void + AST::add(MetaRuleAbstract *r) { + __rules.push_back(r); + } -std::list -AST::getAllFunctions() const{ - const size_t size = __functions.size(); + void + AST::add(TypeAnnotation t, Atom alias) { + if (t.__operator == TypeOperator::VARIANT) { + for (int i = 0, size = t.fields.size(); i < size; ++i) { + __dictVariants.emplace(t.fields[i], make_pair(t, i)); + } + } - std::list result; - for (size_t i=0; i__functions)); - } + __indexTypeAliases.emplace(alias.get(), move(t)); + } - return result; -} + ManagedScpPtr + AST::add(CodeScope* scope) { + this->__scopes.push_back(scope); + return ManagedScpPtr(this->__scopes.size() - 1, &this->__scopes); + } -//TASK select default specializations -std::list -AST::getFunctionVariants(const std::string& name) const{ - auto functions = __indexFunctions.equal_range(name); + std::string + AST::getModuleName() { + const std::string name = "moduleTest"; - std::list result; - std::transform(functions.first, functions.second, inserter(result, result.end()), - [this](auto f){return ManagedFnPtr(f.second, &this->__functions);}); + return name; + } - return result; -} + ManagedPtr + AST::findFunction(const std::string& name) { + int count = __indexFunctions.count(name); + if (!count) { + return ManagedFnPtr::Invalid(); + } - template<> -ManagedPtr -AST::begin() -{return ManagedPtr(0, &this->__functions);} + assert(count == 1); -template<> -ManagedPtr -AST::begin() -{return ManagedPtr(0, &this->__scopes);} + auto range = __indexFunctions.equal_range(name); + return ManagedPtr(range.first->second, &this->__functions); + } -template<> -ManagedPtr -AST::begin() -{return ManagedPtr(0, &this->__rules);} + std::list + AST::getAllFunctions() const { + const size_t size = __functions.size(); + std::list result; + for (size_t i = 0; i < size; ++i) { + result.push_back(ManagedFnPtr(i, &this->__functions)); + } -Expanded -AST::expandType(const TypeAnnotation &t) const -{ - return TypesResolver(this)(t); -} + return result; + } -Expanded -AST::findType(const std::string& name){ - // find in general scope: - if(__indexTypeAliases.count(name)) - return expandType(__indexTypeAliases.at(name)); + //TASK select default specializations - //if type is unknown keep it as is. - TypeAnnotation t(TypeOperator::CUSTOM, {}); - t.__valueCustom = name; - return ExpandedType(move(t)); -} + std::list + AST::getFunctionVariants(const std::string& name) const { + auto functions = __indexFunctions.equal_range(name); -void -AST::recognizeVariantIdentifier(Expression& identifier){ + std::list result; + std::transform(functions.first, functions.second, inserter(result, result.end()), + [this](auto f) { + return ManagedFnPtr(f.second, &this->__functions); + }); -// TODO get rid of findSymbol. Determine symbol while AST parsing. Re-find symbols not found while first pass. -// * move to codescope -// * use findSymbol to find Symbol -// * register var as alias to -// * ident __doubleValue holds VID of an alias + return result; + } - assert(identifier.__state == Expression::IDENT); + template<> + ManagedPtr + AST::begin() { + return ManagedPtr(0, &this->__functions); + } - std::string name = identifier.getValueString(); - if (__dictVariants.count(name)){ - auto record = __dictVariants.at(name); - const TypeAnnotation& typ = record.first; + template<> + ManagedPtr + AST::begin() { + return ManagedPtr(0, &this->__scopes); + } - identifier.__state = Expression::VARIANT; - identifier.setValueDouble(record.second); - identifier.type = typ; - } -} + template<> + ManagedPtr + AST::begin() { + return ManagedPtr(0, &this->__rules); + } -Function::Function(const Atom& name) - : __entry(new CodeScope(0)) -{ - __name = name.get(); -} + Expanded + AST::expandType(const TypeAnnotation &t) const { + return TypesResolver(this)(t); + } -void -Function::addTag(Expression&& tag, const TagModifier mod) -{ - string name = tag.getValueString(); - __tags.emplace(move(name), move(tag)); -} + Expanded + AST::findType(const std::string& name) { + // find in general scope: + if (__indexTypeAliases.count(name)) + return expandType(__indexTypeAliases.at(name)); -const std::map& -Function::getTags() const -{ - return __tags; -} + //if type is unknown keep it as is. + TypeAnnotation t(TypeOperator::CUSTOM,{}); + t.__valueCustom = name; + return ExpandedType(move(t)); + } -CodeScope* -Function::getEntryScope() const -{ - return __entry; -} + void + AST::recognizeVariantIdentifier(Expression& identifier) { -void -Function::addBinding(Atom && name, Expression&& argument) -{ - __entry->addBinding(move(name), move(argument)); -} + // * move to codescope + // * register var as alias to -void -Function::setReturnType(const TypeAnnotation &rtyp) -{ + assert(identifier.__state == Expression::IDENT); - __entry->__declarations[0].type = rtyp; -} + std::string name = identifier.getValueString(); + if (__dictVariants.count(name)) { + auto record = __dictVariants.at(name); + const TypeAnnotation& typ = record.first; -const std::string& -Function::getName() const -{ - return __name; -} + identifier.__state = Expression::VARIANT; + identifier.setValueDouble(record.second); + identifier.type = typ; + } + } -Symbol -CodeScope::registerIdentifier(Atom &&name) -{ - __identifiers.emplace(name.get(), ++__vCounter); - return {__vCounter, this}; -} + Function::Function(const Atom& name) + : __entry(new CodeScope(0)) { + __name = name.get(); + } -void -CodeScope::addBinding(Atom && name, Expression&& argument) -{ - __bindings.push_back(name.get()); - Symbol binding = registerIdentifier(move(name)); - argument.__state = Expression::BINDING; - __declarations[binding.identifier] = move(argument); -} + void + Function::addTag(Expression&& tag, const TagModifier mod) { + string name = tag.getValueString(); + __tags.emplace(move(name), move(tag)); + } -void -CodeScope::addDeclaration(Atom && name, Expression&& body) -{ - Symbol s = registerIdentifier(move(name)); - __declarations[s.identifier] = move(body); -} + const std::map& + Function::getTags() const { + return __tags; + } -CodeScope::CodeScope(CodeScope* parent) - :__parent(parent) -{} + CodeScope* + Function::getEntryScope() const { + return __entry; + } -CodeScope::~CodeScope() -{} + void + Function::addBinding(Atom && name, Expression&& argument) { + __entry->addBinding(move(name), move(argument)); + } -void -CodeScope::setBody(const Expression &body) -{ - __declarations[0] = body; -} + const std::string& + Function::getName() const { + return __name; + } -Expression& -CodeScope::getBody(){ - return __declarations[0]; -} + ScopedSymbol + CodeScope::registerIdentifier(const Expression& identifier) { + VariableVersion version = Attachments::get(identifier, VERSION_NONE); -Symbol -CodeScope::findSymbol(const std::string &name) -{ - //search identifier in the current block - if (__identifiers.count(name)) - { - VID vId = __identifiers.at(name); - Symbol result{vId, this}; - return result; + auto result = __identifiers.emplace(identifier.getValueString(), __vCounter); + if (result.second){ + ++__vCounter; + return {__vCounter-1, version}; + } + + return {result.first->second, version}; } + bool + CodeScope::recognizeIdentifier(const Expression& identifier) const{ + VariableVersion version = Attachments::get(identifier, VERSION_NONE); + const std::string& name = identifier.getValueString(); + + //search identifier in the current block + if (__identifiers.count(name)){ + VNameId id = __identifiers.at(name); + + Symbol s; + s.identifier = ScopedSymbol{id, version}; + s.scope = const_cast(this); + Attachments::put(s); + + return true; + } + //search in the parent scope - if (__parent) - { - return __parent->findSymbol(name); + if (__parent) + { + return __parent->recognizeIdentifier(identifier); + } + + return false; } - //exception: Ident not found - std::cout << "Unknown symbol: "<< name << std::endl; - assert(false && "Symbol not found"); -} + void + AST::postponeIdentifier(CodeScope* scope, const Expression& id) { + binUnrecognizedIdentifiers.emplace(scope, id); + } -const Expression& -CodeScope::findDeclaration(const Symbol& symbol) -{ - CodeScope* self = symbol.scope; - return self->__declarations[symbol.identifier]; -} + void + AST::recognizePostponedIdentifiers() { + for(const auto& identifier: binUnrecognizedIdentifiers){ + if (!identifier.first->recognizeIdentifier(identifier.second)){ + //exception: Ident not found + std::cout << "Unknown symbol: "<< identifier.second.getValueString() << std::endl; + assert(false && "Symbol not found"); + } + } + } + void + CodeScope::addBinding(Expression&& var, Expression&& argument) { + argument.__state = Expression::BINDING; + __bindings.push_back(var.getValueString()); + ScopedSymbol binding = registerIdentifier(var); + __declarations[binding] = move(argument); + } -void -RuleArguments::add(const Atom &arg, DomainAnnotation typ) -{ - emplace_back(arg.get(), typ); -} + void + CodeScope::addDeclaration(Expression&& var, Expression&& body) { + ScopedSymbol s = registerIdentifier(var); + __declarations[s] = move(body); + } -void -RuleGuards::add(Expression&& e) -{ - push_back(e); -} + CodeScope::CodeScope(CodeScope* parent) + : __parent(parent) { + } -MetaRuleAbstract:: -MetaRuleAbstract(RuleArguments&& args, RuleGuards&& guards) - : __args(std::move(args)), __guards(std::move(guards)) -{} + CodeScope::~CodeScope() { + } -MetaRuleAbstract::~MetaRuleAbstract(){} + void + CodeScope::setBody(const Expression &body) { + __declarations[ScopedSymbol::RetSymbol] = body; + } -RuleWarning:: -RuleWarning(RuleArguments&& args, RuleGuards&& guards, Expression&& condition, Atom&& message) - : MetaRuleAbstract(std::move(args), std::move(guards)), __message(message.get()), __condition(condition) -{} + Expression& + CodeScope::getBody() { + return __declarations[ScopedSymbol::RetSymbol]; + } -RuleWarning::~RuleWarning(){} + const Expression& + CodeScope::findDeclaration(const Symbol& symbol) { + CodeScope* self = symbol.scope; + return self->__declarations.at(symbol.identifier); + } -void -RuleWarning::compile(ClaspLayer& layer) -{ - //TODO restore addRuleWarning - //layer.addRuleWarning(*this); -} + void + RuleArguments::add(const Atom &arg, DomainAnnotation typ) { + emplace_back(arg.get(), typ); + } -bool operator< (const Symbol& s1, const Symbol& s2) -{ - return (s1.scope < s2.scope) || (s1.scope==s2.scope && s1.identifier&& message) + : MetaRuleAbstract(std::move(args), std::move(guards)), __message(message.get()), __condition(condition) { + } + + RuleWarning::~RuleWarning() { + } - for(size_t i=0; i + struct AttachmentsStorage { -return false; -} + static Attachments* + get(const Symbol& s) { + return &s.scope->findDeclaration(s).tagsInternal; + } + }; + + template<> + struct AttachmentsStorage { + + static Attachments* + get(const Expression& e) { + return &e.tagsInternal; + } + }; } + diff --git a/cpp/src/ast.h b/cpp/src/ast.h index cd070ab..55866ba 100644 --- a/cpp/src/ast.h +++ b/cpp/src/ast.h @@ -1,562 +1,604 @@ #ifndef AST_H #define AST_H #include "attachments.h" #include #include #include #include #include #include #include #include "utils.h" #include namespace llvm { class Value; } namespace xreate { struct String_t { }; struct Identifier_t { }; struct Number_t { }; struct Type_t { }; template class Atom { }; //DEBT hold for all atoms/identifiers Parser::Token data, like line:col position 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) { assert(value.size()); __value = std::string(++value.begin(), --value.end()); } const std::string& get() const { return __value; } private: std::string __value; }; enum class TypePrimitive { Bool, Num, Int, I32, I8, Float, String, }; 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 == "num") { __value = TypePrimitive::Num; } else if (buffer == "int") { __value = TypePrimitive::Int; } else if (buffer == "i8") { __value = TypePrimitive::I8; } else if (buffer == "i32") { __value = TypePrimitive::I32; } else if (buffer == "float") { __value = TypePrimitive::Float; } else if (buffer == "string") { __value = TypePrimitive::String; } } Atom() { } TypePrimitive get() const { return __value; } private: TypePrimitive __value; }; typedef Atom TypeAtom; enum class TypeOperator { NONE, CALL, CUSTOM, VARIANT, ARRAY, TUPLE, STRUCT, ACCESS, LINK }; 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, TypeAnnotation typ, int size); TypeAnnotation(TypeOperator op, std::initializer_list operands); TypeAnnotation(TypeOperator op, std::vector&& operands); void addBindings(std::vector>&& params); void addFields(std::vector>&& listFields); bool operator<(const TypeAnnotation& t) const; // TypeAnnotation (struct_tag, std::initializer_list); TypeOperator __operator = TypeOperator::NONE; std::vector __operands; TypePrimitive __value; std::string __valueCustom; int conjuctionId = -1; //conjunction point id (relevant for recursive types) uint64_t __size = 0; std::vector fields; std::vector bindings; private: }; enum class Operator { - ADD, SUB, MUL, DIV, EQU, NE, NEG, LSS, LSE, GTR, GTE, LIST, LIST_RANGE, LIST_NAMED, CALL, NONE, IMPL/* implication */, MAP, FOLD, FOLD_INF, LOOP_CONTEXT, INDEX, IF, SWITCH, SWITCH_ADHOC, CASE, CASE_DEFAULT, LOGIC_AND, ADHOC, CONTEXT_RULE, SEQUENCE + ADD, SUB, MUL, DIV, + EQU, NE, NEG, LSS, + LSE, GTR, GTE, LIST, + LIST_RANGE, LIST_NAMED, + CALL, CALL_INTRINSIC, NONE, + IMPL/* implication */, MAP, + FOLD, FOLD_INF, LOOP_CONTEXT, + INDEX, IF, SWITCH, SWITCH_ADHOC, + CASE, CASE_DEFAULT, LOGIC_AND, + ADHOC, CONTEXT_RULE }; class Function; class AST; class CodeScope; class MetaRuleAbstract; template struct ManagedPtr { static ManagedPtr Invalid() { return ManagedPtr(); } ManagedPtr() : __storage(0) { } ManagedPtr(unsigned int id, const std::vector* storage) : __id(id), __storage(storage) { } Target& operator*() const { assert(isValid() && "Invalid Ptr"); 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() && "Invalid Ptr"); return __storage->at(__id); } inline bool isValid() const { return (__storage) && (0 <= __id) && (__id < __storage->size()); } inline operator bool() const { return isValid(); } ManagedPtr& operator++() { ++__id; return *this; } inline unsigned int id() const { 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); //To update ExpressionHints in case of any changes struct Expression { friend class CodeScope; friend class ClaspLayer; friend class CFAPass; friend class ExpressionHints; Expression(const Operator &oprt, std::initializer_list params); Expression(const Atom& ident); Expression(const Atom& number); Expression(const Atom& a); + Expression(); void setOp(Operator oprt); void addArg(Expression&& arg); void addBindings(std::initializer_list> params); void bindType(TypeAnnotation t); template void addBindings(InputIt paramsBegin, InputIt paramsEnd); void addBlock(ManagedScpPtr scope); const std::vector& getOperands() const; double getValueDouble() const; void setValueDouble(double value); const std::string& getValueString() const; void setValue(const Atom&& v); bool isValid() const; bool isDefined() const; bool operator==(const Expression& other) const; enum { INVALID, COMPOUND, IDENT, NUMBER, STRING, VARIANT, BINDING } __state = INVALID; + Operator op; + unsigned int id; std::vector bindings; std::map __indexBindings; std::vector operands; TypeAnnotation type; mutable std::map tags; - mutable Attachments tagsInternal; std::list blocks; private: std::string __valueS; double __valueD; + + static unsigned int nextVacantId; }; bool operator< (const Expression&, const Expression&); template void Expression::addBindings(InputIt paramsBegin, InputIt paramsEnd) { size_t index = bindings.size(); std::transform(paramsBegin, paramsEnd, std::inserter(bindings, bindings.end()), [&index, this] (const Atom atom) { std::string key = atom.get(); this->__indexBindings[key] = index++; return key; }); } 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 + typedef unsigned int VNameId; + + typedef int VariableVersion; + const VariableVersion VERSION_NONE = -2; + + template<> + struct AttachmentsDict { - friend class CFGPass; - - public: - llvm::Value* compile(LLVMLayer& l, Function* f, std::string* hintRetVar=0) const; + typedef VariableVersion Data; + static const unsigned int key = 6; + }; + + struct ScopedSymbol{ + VNameId id; + VariableVersion version; + + static const ScopedSymbol RetSymbol; + }; + + struct Symbol { + ScopedSymbol identifier; + CodeScope * scope; + }; + + template<> + struct AttachmentsDict + { + typedef Symbol Data; + static const unsigned int key = 7; + }; + +} +namespace std +{ + template<> + struct hash{ + std::size_t operator()(xreate::ScopedSymbol const& s) const; }; - */ + template<> + struct equal_to{ + bool operator()(const xreate::ScopedSymbol& __x, const xreate::ScopedSymbol& __y) const; + }; +} +namespace xreate { + 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 PassManager; public: CodeScope(CodeScope* parent = 0); void setBody(const Expression& body); Expression& getBody(); - void addDeclaration(Atom && name, Expression&& body); - void addBinding(Atom && name, Expression&& argument); - Symbol findSymbol(const std::string &name); + void addDeclaration(Expression&& var, Expression&& body); + void addBinding(Expression&& var, Expression&& argument); static const Expression& findDeclaration(const Symbol& symbol); ~CodeScope(); std::vector __bindings; - std::map __identifiers; - /** - * definition of return type has variable index Zero(0) - */ + std::map __identifiers; + //TODO move __definitions to SymbolsAttachments data - std::unordered_map __declarations; + //NOTE: definition of return type has zero(0) variable index + std::unordered_map __declarations; std::vector tags; std::vector contextRules; private: - VID __vCounter = 0; + VNameId __vCounter = 1; CodeScope* __parent; - Symbol registerIdentifier(Atom && name); + ScopedSymbol registerIdentifier(const Expression& identifier); + public: + bool recognizeIdentifier(const Expression& identifier) const; }; class Function { friend class Expression; friend class CodeScope; friend class AST; public: Function(const Atom& name); void addBinding(Atom && name, Expression&& argument); void addTag(Expression&& tag, const TagModifier mod); - void setReturnType(const TypeAnnotation& rtyp); - const std::string& getName() const; const std::map& getTags() const; CodeScope* getEntryScope() const; CodeScope* __entry; std::string __name; bool isPrefunction = false; //SECTIONTAG adhoc Function::isPrefunction flag Expression guardContext; private: std::map __tags; }; class ExternData; struct ExternEntry { std::string package; std::vector headers; }; typedef Expanded ExpandedType; enum ASTInterface { CFA, DFA, Extern, Adhoc }; struct FunctionSpecialization { std::string guard; size_t id; }; struct FunctionSpecializationQuery { std::unordered_set context; }; template<> - struct AttachmentsStorage { - - static Attachments* - get(const Symbol& s) { - return &s.scope->findDeclaration(s).tagsInternal; + struct AttachmentsId{ + static unsigned int getId(const Expression& expression){ + return expression.id; } }; - + template<> - struct AttachmentsStorage { - - static Attachments* - get(const Expression& e) { - return &e.tagsInternal; + struct AttachmentsId{ + static unsigned int getId(const Symbol& s){ + return s.scope->__declarations.at(s.identifier).id; } }; - + class AST { public: AST(); //TASK extern and DFA interfaces move into addInterfaceData /** * DFA Interface */ void addDFAData(Expression&& data); /** * Extern Interface */ void addExternData(ExternData&& data); void addInterfaceData(const ASTInterface& interface, Expression&& data); void add(Function* f); void add(MetaRuleAbstract* r); ManagedScpPtr add(CodeScope* scope); std::string getModuleName(); ManagedPtr findFunction(const std::string& name); typedef std::multimap FUNCTIONS_REGISTRY; std::list getAllFunctions() const; std::list getFunctionVariants(const std::string& name) const; template ManagedPtr begin(); std::vector __externdata; std::list __dfadata; //TODO move to more appropriate place std::list __rawImports; //TODO move to more appropriate place std::multimap __interfacesData; //TODO CFA data here. private: std::vector __rules; std::vector __functions; std::vector __scopes; FUNCTIONS_REGISTRY __indexFunctions; // ***** TYPES SECTION ***** public: std::map __indexTypeAliases; ExpandedType expandType(const TypeAnnotation &t) const; ExpandedType findType(const std::string& name); void add(TypeAnnotation t, Atom alias); + + //TODO revisit enums/variants void recognizeVariantIdentifier(Expression& identifier); private: std::map> __dictVariants; ExpandedType expandType(const TypeAnnotation &t, std::map scope, const std::vector &args = std::vector()) const; - // ***** TYPES SECTION END ***** + // ***** SYMBOL RECOGNITION ***** + public: + std::set> binUnrecognizedIdentifiers; + + public: + void postponeIdentifier(CodeScope* scope, const Expression& id); + void recognizePostponedIdentifiers(); }; 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 index 83a54d1..6dd9515 100644 --- a/cpp/src/attachments.cpp +++ b/cpp/src/attachments.cpp @@ -1,30 +1,5 @@ // // Created by pgess on 3/15/15. // -#include "attachments.h" - -namespace xreate { - void* xreate::Attachments::put(unsigned int key, void *data) { - auto result = __data.emplace(key, data); - - void* ptrOld = nullptr; - if (!result.second){ - ptrOld = result.first->second; - result.first->second = data; - } - - return ptrOld; - } - - void *xreate::Attachments::get(unsigned int key) { - assert(__data.count(key)); - return __data.at(key); - } - - bool - xreate::Attachments::exists(unsigned int key) - { - return __data.count(key)>0; - } -} \ No newline at end of file +#include "attachments.h" \ No newline at end of file diff --git a/cpp/src/attachments.h b/cpp/src/attachments.h index 03b8711..6e09a7c 100644 --- a/cpp/src/attachments.h +++ b/cpp/src/attachments.h @@ -1,124 +1,125 @@ // // Created by pgess on 3/15/15. // #ifndef _XREATE_ATTACHMENTS_H_ #define _XREATE_ATTACHMENTS_H_ #include +#include #include #include namespace xreate { //Attachments dictionary template struct AttachmentsDict { // typedef void Data; - // static const unsigned int key (current unreserved - 6); + // static const unsigned int key (current unreserved - 8); }; - template - struct AttachmentsStorage - { - //static Attachments* get(const T&); + template + struct AttachmentsId{ + //static unsigned int getId(const Object& object); }; - namespace detail { - - template - typename std::enable_if::value, void*>::type - __wrap(const Typ& value){ - return value; - } - - template - typename std::enable_if::value, Typ>::type - __unwrap(void* value){ - return reinterpret_cast(value); + //TODO add specialization for pointers + template + class AttachmentsStorage + { + public: + void put(unsigned int id, Data data) + { + __data.emplace(id, data); } - - template - typename std::enable_if::value, void*>::type - __wrap(const Typ& value){ - Typ* holder = new Typ(value); - return holder; + + Data& get(unsigned int id) + { + return __data.at(id); } - template - typename std::enable_if::value, Typ&>::type - __unwrap(void* value){ - return *reinterpret_cast(value); + Data get(unsigned int id, Data dataDefault) + { + if (! exists(id)){ + return dataDefault; + } + + return __data.at(id); } - template - typename std::enable_if::value, void>::type - __delete(void* value){ - delete reinterpret_cast(value); - } - - template - typename std::enable_if::value, void>::type - __delete(void* value){ - delete reinterpret_cast(value); + bool exists(unsigned int id) + { + return __data.count(id); } - } + + private: + std::map __data; + }; - //TODO copy whole data from symbol to symbol: copy(sTo, sFrom); - class Attachments - { + class Attachments{ public: - //TODO add specialization for pointers template using Data = typename AttachmentsDict::Data; - template - static void put(const Holder& holder, const Data& data) + template + static Data& get(const Id& object) { - const unsigned int key = AttachmentsDict::key; - Attachments* self = AttachmentsStorage::get(holder); + unsigned int id = AttachmentsId::getId(object); + AttachmentsStorage>* self = reinterpret_cast>*>(__storage[AttachmentsDict::key]); - void* dataWaste = self->put(key, detail::__wrap(data)); - detail::__delete>(dataWaste); + return self->exists(id); } - - template - static Data& get(const Holder& holder) + + template + static Data& get(const Id& object) { - const unsigned int key = AttachmentsDict::key; - Attachments* self = AttachmentsStorage::get(holder); + unsigned int id = AttachmentsId::getId(object); + AttachmentsStorage>* self = reinterpret_cast>*>(__storage[AttachmentsDict::key]); - return detail::__unwrap>(self->get(key)); + return self->get(id); } - template - static Data get(const Holder& holder, Data&& dataDefault) + template + static Data get(const Id& object, Data dataDefault) { - if (! exists(holder)){ - return dataDefault; - } - - const unsigned int key = AttachmentsDict::key; - Attachments* self = AttachmentsStorage::get(holder); + unsigned int id = AttachmentsId::getId(object); + AttachmentsStorage>* self = reinterpret_cast>*>(__storage[AttachmentsDict::key]); - return detail::__unwrap>(self->get(key)); + return self->get(id, dataDefault); } - - template - static bool exists(const Holder& holder) + + template + static void put(const Id& object, Data data) { - const unsigned int key = AttachmentsDict::key; - Attachments* self = AttachmentsStorage::get(holder); - return self->exists(key); + unsigned int id = AttachmentsId::getId(object); + AttachmentsStorage>* self = reinterpret_cast>*>(__storage[AttachmentsDict::key]); + + self->put(id, std::move(data)); } + + template + static void put(const Id& object) + { + unsigned int id = AttachmentsId::getId(object); + AttachmentsStorage>* self = reinterpret_cast>*>(__storage[AttachmentsDict::key]); + return self->exists(id); + } + + template + static void init(){ + unsigned int keyStorage = AttachmentsDict::key; + if (keyStorage+1 > __storage.size()){ + __storage.resize(keyStorage + 1, nullptr); + } + + __storage[keyStorage] = new AttachmentsStorage>(); + } + private: - std::map __data; - - void* put(unsigned int key, void *data); - void* get(unsigned int key); - bool exists(unsigned int key); + static std::vector __storage; }; } -#endif //_XREATE_ATTACHMENTS_H_ +#endif //_XREATE_ATTACHMENTS_H_ \ No newline at end of file diff --git a/cpp/src/clasplayer.h b/cpp/src/clasplayer.h index 6961026..eccdff9 100644 --- a/cpp/src/clasplayer.h +++ b/cpp/src/clasplayer.h @@ -1,230 +1,230 @@ #ifndef CLASPLAYER_H #define CLASPLAYER_H #include "ast.h" #include "contextrule.h" #include #include #include #include #include #include #include #include namespace xreate { typedef unsigned int ScopePacked; struct SymbolPacked { - VID identifier; + ScopedSymbol identifier; ScopePacked scope; bool categoryTransient; SymbolPacked(): categoryTransient(false){} - SymbolPacked(VID i, ScopePacked s, bool isTransient = false): identifier(i), scope(s), categoryTransient(isTransient){} + SymbolPacked(ScopedSymbol i, ScopePacked s, bool isTransient = false): identifier(i), scope(s), categoryTransient(isTransient){} }; bool operator==(const SymbolPacked& s1, const SymbolPacked& s2); bool operator<(const SymbolPacked& s1, const SymbolPacked& s2); enum class DFGConnection { STRONG, WEAK, PROTOTYPE }; class IAnalysisData { public: void print(std::ostringstream& output) const; virtual ~IAnalysisData(){}; }; class IQuery { public: virtual void init(ClaspLayer* clasp) = 0; virtual ~IQuery() {} }; enum class QueryId { ContainersQuery, ContextQuery, PtrvalidQuery }; namespace analysis{ class DFAGraph; class CFAGraph; } class ClaspLayer { friend class ContextRule; //PROVIDERS: public: boost::scoped_ptr dataDFA; void setDFAData(xreate::analysis::DFAGraph* graph); boost::scoped_ptr dataCFA; void setCFAData(xreate::analysis::CFAGraph* graph); void addRawScript(std::string&& script); private: void involveImports(); //QUERIES public: IQuery* registerQuery(IQuery* query, const QueryId& id); IQuery* getQuery(const QueryId& id); template static std::tuple parse(const Gringo::Symbol& atom); typedef std::multimap::const_iterator ModelIterator; typedef boost::optional> ModelFragment; ModelFragment query(const std::string& atom); size_t getScopesCount() const; SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName = ""); ScopePacked pack(CodeScope * const scope); Symbol unpack(const SymbolPacked& symbol); std::string getHintForPackedSymbol(const SymbolPacked& symbol); private: std::map __queries; std::multimap __model; std::map __indexSymbolNameHints; std::unordered_map __indexScopes; std::vector __registryScopes; //WARNINGS //TODO move to separate provider/query public: void addRuleWarning(const RuleWarning &rule); unsigned int registerWarning(std::string &&message); private: std::map __warnings; void printWarnings(std::ostream& out); //DEFAULT public: AST *ast; ClaspLayer(); void run(); private: std::ostringstream __partTags; std::ostringstream __partGeneral; bool handleSolution(Gringo::Model const &model); }; template struct ParseImplAtom { static typ get(const Gringo::Symbol& atom) { return atom.num(); } }; template<> struct ParseImplAtom { static std::string get(const Gringo::Symbol& atom) { switch (atom.type()) { case Gringo::SymbolType::Str: return atom.string().c_str(); case Gringo::SymbolType::Fun: return atom.name().c_str(); default: break; } assert(false && "Inappropriate symbol type"); } }; template<> struct ParseImplAtom { static SymbolPacked get(const Gringo::Symbol& atom) { auto result = ClaspLayer::parse(atom); return SymbolPacked(std::get<0>(result), std::get<1>(result)); } }; template<> struct ParseImplAtom { static Gringo::Symbol get(const Gringo::Symbol& atom) { return atom; } }; template<> struct ParseImplAtom { static Expression get(const Gringo::Symbol& atom) { switch (atom.type()) { case Gringo::SymbolType::Num: return Expression(atom.num()); case Gringo::SymbolType::Str: return Expression(std::string(atom.string().c_str())); case Gringo::SymbolType::Fun: { //ID if (!atom.args().size){ return Expression(std::string(atom.name().c_str())); } //FUNC Expression result(Operator::CALL,{Expression(std::string(atom.name().c_str()))}); for (const Gringo::Symbol& arg : atom.args()) { result.addArg(ParseImplAtom::get(arg)); } return result; } default: { assert(false); } } } }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { const size_t tupleSize = std::tuple_size::value; typedef typename std::tuple_element < tupleSize - index, Tuple>::type ElType; ElType& el = std::get < tupleSize - index > (tup); Gringo::Symbol atom = *arg; el = ParseImplAtom::get(atom); Parse_Impl ::parse(tup, ++arg); } }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { } }; template std::tuple ClaspLayer::parse(const Gringo::Symbol& atom) { typedef std::tuple < Types...> Tuple; Tuple tup; Parse_Impl::value>::parse(tup, atom.args().first); return tup; } } #endif \ No newline at end of file diff --git a/cpp/src/compilation/advanced.cpp b/cpp/src/compilation/advanced.cpp index d49ede8..40465ac 100644 --- a/cpp/src/compilation/advanced.cpp +++ b/cpp/src/compilation/advanced.cpp @@ -1,432 +1,431 @@ /* * File: InstructionsAdvanced.cpp * Author: pgess * * Created on June 26, 2016, 6:00 PM */ #include #include "compilation/advanced.h" #include "compilation/containers.h" #include "query/context.h" #include "query/containers.h" #include "llvmlayer.h" #include "ast.h" using namespace std; using namespace llvm; using namespace xreate; using namespace xreate::containers; using namespace xreate::compilation; #define NAME(x) (hintRetVar.empty()? x : hintRetVar) #define UNUSED(x) (void)(x) #define EXPAND_CONTEXT \ LLVMLayer* llvm = context.pass->man->llvm; \ compilation::CodeScopeUnit* scope = context.scope; \ compilation::FunctionUnit* function = context.function; Advanced::Advanced(compilation::Context ctx) : context(ctx), tyNum(static_cast (ctx.pass->man->llvm->toLLVMType(ExpandedType(TypeAnnotation(TypePrimitive::Num))))) { } llvm::Value* Advanced::compileMapSolidOutput(const Expression &expr, const std::string hintRetVar) { EXPAND_CONTEXT //initialization - std::string varIn = expr.getOperands()[0].getValueString(); - Symbol symbolIn = scope->scope->findSymbol(varIn); + Symbol symbolIn = Attachments::get(expr.getOperands()[0]); ImplementationRec implIn = containers::Query::queryImplementation(symbolIn).extract(); // impl of input list size_t size = implIn.size; CodeScope* scopeLoop = expr.blocks.front(); std::string varEl = scopeLoop->__bindings[0]; Iterator* it = Iterator::create(context, symbolIn); llvm::Value *rangeFrom = it->begin(); llvm::Value *rangeTo = it->end(); //definitions ArrayType* tyNumArray = (ArrayType*) (llvm->toLLVMType(ExpandedType(TypeAnnotation(tag_array, TypePrimitive::Num, size)))); llvm::IRBuilder<> &builder = llvm->builder; llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "loop", function->raw); llvm::BasicBlock *blockBeforeLoop = builder.GetInsertBlock(); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postloop", function->raw); 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 = it->get(stateLoop, varEl); compilation::CodeScopeUnit* scopeLoopUnit = function->getScopeUnit(scopeLoop); scopeLoopUnit->bindArg(elIn, move(varEl)); Value* elOut = scopeLoopUnit->compile(); 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; } Value* Advanced::compileArrayIndex(llvm::Value* aggregate, std::vector indexes, std::string hintRetVar) { EXPAND_CONTEXT UNUSED(function); indexes.insert(indexes.begin(), llvm::ConstantInt::get(tyNum, 0)); llvm::Value *pEl = llvm->builder.CreateGEP(aggregate, llvm::ArrayRef(indexes)); return llvm->builder.CreateLoad(pEl, NAME("el")); } Value* Advanced::compileStructIndex(llvm::Value* aggregate, const ExpandedType& t, const std::string& idx) { EXPAND_CONTEXT UNUSED(scope); TypeUtils types(llvm); std::vector&& fields = types.getStructFields(t); for (unsigned i = 0, size = fields.size(); i < size; ++i) { if (fields.at(i) == idx) { std::vector refs; llvm::IntegerType* tyInt = llvm::Type::getInt32Ty(llvm::getGlobalContext()); llvm::ConstantInt* zero = llvm::ConstantInt::get(tyInt, 0, false); llvm::BasicBlock *blockSafe = llvm::BasicBlock::Create(llvm::getGlobalContext(), "safe", function->raw); // TODO review safety check: validPtr for `aggregate` // SECTIONTAG validptr exception PointerType* tyAggr = dyn_cast(aggregate->getType()); llvm::Value* null = llvm::ConstantPointerNull::get(tyAggr); Value* condNull = llvm->builder.CreateICmpNE(aggregate, null); llvm::BasicBlock *blockException = llvm::BasicBlock::Create(llvm::getGlobalContext(), "exception", function->raw); llvm->builder.CreateCondBr(condNull, blockSafe, blockException); llvm->initExceptionBlock(blockException); llvm->builder.SetInsertPoint(blockSafe); std::vector indexes; //dereference pointer if (types.isPointer(t)) { indexes.push_back(zero); } indexes.push_back(ConstantInt::get(tyInt, i)); Value* addr = llvm->builder.CreateGEP(aggregate, indexes); return llvm->builder.CreateLoad(addr); } } assert(false && "not found required struct field"); return nullptr; } llvm::Value* Advanced::compileFold(const Expression& fold, const std::string& hintRetVar) { EXPAND_CONTEXT assert(fold.op == Operator::FOLD); //initialization: - Symbol varInSymbol = scope->scope->findSymbol(fold.getOperands()[0].getValueString()); + Symbol varInSymbol = Attachments::get(fold.getOperands()[0]); Implementation info = Query::queryImplementation(varInSymbol); Iterator* it = Iterator::create(context, varInSymbol); llvm::Value* rangeBegin = it->begin(); llvm::Value* rangeEnd = it->end(); llvm::Value* accumInit = scope->process(fold.getOperands()[1]); std::string varIn = fold.getOperands()[0].getValueString(); std::string varAccum = fold.bindings[1]; std::string varEl = fold.bindings[0]; TransformerSaturation* transformerSaturation = context.pass->transformations->get(); llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold", function->raw); llvm::BasicBlock *blockBody = llvm::BasicBlock::Create(llvm::getGlobalContext(), "body", function->raw); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postfold", function->raw); llvm->builder.CreateBr(blockLoop); // * create phi llvm->builder.SetInsertPoint(blockLoop); llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, NAME("accum")); accum->addIncoming(accumInit, blockBeforeLoop); llvm::PHINode *itLoop = llvm->builder.CreatePHI(rangeBegin->getType(), 2, "foldIt"); itLoop->addIncoming(rangeBegin, blockBeforeLoop); // * loop body llvm->builder.SetInsertPoint(blockBody); CodeScope* scopeLoop = fold.blocks.front(); compilation::CodeScopeUnit* loopUnit = function->getScopeUnit(scopeLoop); Value* elIn = it->get(itLoop); loopUnit->bindArg(accum, move(varAccum)); loopUnit->bindArg(elIn, move(varEl)); Value* accumNext = loopUnit->compile(); // * computing next iteration state Value *itLoopNext = it->advance(itLoop); accum->addIncoming(accumNext, llvm->builder.GetInsertBlock()); itLoop->addIncoming(itLoopNext, llvm->builder.GetInsertBlock()); llvm->builder.CreateBr(blockLoop); // * break checks, continue checks //!! only after compiled Loop Body in order to fetch saturation expression llvm->builder.SetInsertPoint(blockLoop); if (transformerSaturation->exists()) { transformerSaturation->inject(blockBeforeLoop, blockAfterLoop, context); } // * next iteration checks Value* condRange = llvm->builder.CreateICmpNE(itLoop, rangeEnd); llvm->builder.CreateCondBr(condRange, blockBody, blockAfterLoop); // finalization: llvm->builder.SetInsertPoint(blockAfterLoop); return accum; } llvm::Value* Advanced::compileFoldInf(const Expression& fold, const std::string& hintRetVar) { EXPAND_CONTEXT assert(fold.op == Operator::FOLD_INF); std::string accumName = fold.bindings[0]; llvm::Value* accumInit = scope->process(fold.getOperands()[0]); llvm::BasicBlock *blockBeforeLoop = llvm->builder.GetInsertBlock(); llvm::BasicBlock *blockLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "fold", function->raw); llvm::BasicBlock *blockBody = llvm::BasicBlock::Create(llvm::getGlobalContext(), "body", function->raw); llvm::BasicBlock *blockAfterLoop = llvm::BasicBlock::Create(llvm::getGlobalContext(), "postfold", function->raw); TransformerSaturation* transformerSaturation = context.pass->transformations->get(); llvm->builder.CreateBr(blockLoop); // * create phi llvm->builder.SetInsertPoint(blockLoop); llvm::PHINode *accum = llvm->builder.CreatePHI(accumInit->getType(), 2, NAME("accum")); accum->addIncoming(accumInit, blockBeforeLoop); // * loop body llvm->builder.SetInsertPoint(blockBody); CodeScope* scopeLoop = fold.blocks.front(); compilation::CodeScopeUnit* unitLoop = function->getScopeUnit(scopeLoop); unitLoop->bindArg(accum, move(accumName)); Value* accumNext = unitLoop->compile(); // * computing next iteration state accum->addIncoming(accumNext, llvm->builder.GetInsertBlock()); llvm->builder.CreateBr(blockLoop); // * break checks, continue checks assert(transformerSaturation->exists()); llvm->builder.SetInsertPoint(blockLoop); transformerSaturation->inject(blockBeforeLoop, blockAfterLoop, context); llvm->builder.CreateBr(blockBody); // finalization: llvm->builder.SetInsertPoint(blockAfterLoop); return accum; } llvm::Value* Advanced::compileLoopContext(const Expression& expression, const std::string& hintRetVar) { EXPAND_CONTEXT llvm::IRBuilder<>& builder = llvm->builder; ContextQuery* queryContext = reinterpret_cast (context.pass->man->clasp->getQuery(QueryId::ContextQuery)); ScopePacked scopeOuterId = context.pass->man->clasp->pack(scope->scope); const Domain& contextScopeOuter = queryContext->getContext(scopeOuterId); std::string classSelected = expression.operands[0].getValueString(); std::list elementsSelected; for (const Expression& c : contextScopeOuter) { if (c.op == Operator::CALL && c.getValueString() == classSelected) { assert(c.operands.size()); elementsSelected.push_back(c.operands[0]); } } assert(expression.blocks.size()); CodeScope* scopeInner = expression.blocks.front(); compilation::CodeScopeUnit* scopeInnerUnit = function->getScopeUnit(scopeInner); ScopePacked scopeInnerId = context.pass->man->clasp->pack(scopeInner); llvm::Value* result = nullptr; for (const Expression& element : elementsSelected) { std::string blockName = "context" + element.getValueString(); llvm::BasicBlock *blockInner = llvm::BasicBlock::Create(llvm::getGlobalContext(), blockName, function->raw); builder.CreateBr(blockInner); builder.SetInsertPoint(blockInner); queryContext->forceContext(scopeInnerId,{element}); scopeInnerUnit->reset(); result = scopeInnerUnit->compile(); } return result; } llvm::Value* Advanced::compileIf(const Expression& exprIf, const std::string& hintRetVar) { EXPAND_CONTEXT //initialization: const Expression& condExpr = exprIf.getOperands()[0]; llvm::IRBuilder<>& builder = llvm->builder; llvm::Type* tyResultType = llvm->toLLVMType(llvm->ast->expandType(exprIf.type)); llvm::BasicBlock *blockAfter = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifAfter", function->raw); llvm::BasicBlock *blockTrue = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifTrue", function->raw); llvm::BasicBlock *blockFalse = llvm::BasicBlock::Create(llvm::getGlobalContext(), "ifFalse", function->raw); llvm::Value* cond = scope->process(condExpr); llvm->builder.CreateCondBr(cond, blockTrue, blockFalse); builder.SetInsertPoint(blockTrue); CodeScope* scopeTrue = exprIf.blocks.front(); llvm::Value* resultTrue = function->getScopeUnit(scopeTrue)->compile(); builder.CreateBr(blockAfter); builder.SetInsertPoint(blockFalse); CodeScope* scopeFalse = exprIf.blocks.back(); llvm::Value* resultFalse = function->getScopeUnit(scopeFalse)->compile(); builder.CreateBr(blockAfter); builder.SetInsertPoint(blockAfter); llvm::PHINode *ret = builder.CreatePHI(tyResultType, 2, NAME("if")); ret->addIncoming(resultTrue, blockTrue); ret->addIncoming(resultFalse, blockFalse); return ret; } //TODO Switch: default variant no needed when all possible conditions are considered llvm::Value* Advanced::compileSwitch(const Expression& exprSwitch, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); assert(exprSwitch.operands.size() >= 2); assert(exprSwitch.operands[1].op == Operator::CASE_DEFAULT && "No default case in Switch Statement"); int countCases = exprSwitch.operands.size() - 1; llvm::IRBuilder<>& builder = llvm->builder; llvm::BasicBlock* blockProlog = builder.GetInsertBlock(); llvm::BasicBlock *blockEpilog = llvm::BasicBlock::Create(llvm::getGlobalContext(), "switchAfter", function->raw); builder.SetInsertPoint(blockEpilog); llvm::Type* exprSwitchType = llvm->toLLVMType(ExpandedType(exprSwitch.type)); llvm::PHINode *ret = builder.CreatePHI(exprSwitchType, countCases, NAME("switch")); builder.SetInsertPoint(blockProlog); llvm::Value * conditionSwitch = scope->process(exprSwitch.operands[0]); llvm::BasicBlock *blockDefault = llvm::BasicBlock::Create(llvm::getGlobalContext(), "caseDefault", function->raw); llvm::SwitchInst * instructionSwitch = builder.CreateSwitch(conditionSwitch, blockDefault, countCases); for (int size = exprSwitch.operands.size(), i = 2; i < size; ++i) { llvm::BasicBlock *blockCase = llvm::BasicBlock::Create(llvm::getGlobalContext(), "case" + std::to_string(i), function->raw); llvm::Value* condCase = function->getScopeUnit(exprSwitch.operands[i].blocks.front())->compile(); builder.SetInsertPoint(blockCase); llvm::Value* resultCase = function->getScopeUnit(exprSwitch.operands[i].blocks.back())->compile(); builder.CreateBr(blockEpilog); ret->addIncoming(resultCase, builder.GetInsertBlock()); builder.SetInsertPoint(blockProlog); instructionSwitch->addCase(dyn_cast(condCase), blockCase); } //compile default block: builder.SetInsertPoint(blockDefault); CodeScope* scopeDefault = exprSwitch.operands[1].blocks.front(); llvm::Value* resultDefault = function->getScopeUnit(scopeDefault)->compile(); builder.CreateBr(blockEpilog); ret->addIncoming(resultDefault, builder.GetInsertBlock()); builder.SetInsertPoint(blockEpilog); return ret; } //TODO recognize cases to make const arrays/stored in global mem/stack alloced. llvm::Value* Advanced::compileListAsSolidArray(const Expression &expr, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(scope); UNUSED(function); AST* root = context.pass->man->root; const size_t& length = expr.getOperands().size(); const Expression& expression = expr; llvm::Value* zero = ConstantInt::get(tyNum, 0); llvm::Value* one = ConstantInt::get(tyNum, 1); ExpandedType typAggrExpanded = root->expandType(expression.type); assert(typAggrExpanded->__operator == TypeOperator::ARRAY); llvm::Type* typEl = llvm->toLLVMType(ExpandedType(typAggrExpanded->__operands[0])); ArrayType* typAggr = (ArrayType*) llvm::ArrayType::get(typEl, length); llvm::Value* list = llvm->builder.CreateAlloca(typAggr, ConstantInt::get(Type::getInt32Ty(llvm::getGlobalContext()), length, false), hintRetVar); const std::vector& operands = expression.getOperands(); llvm::Value* addrOperand = llvm->builder.CreateGEP(typAggr, list, ArrayRef(std::vector{zero, zero})); llvm->builder.CreateStore(scope->process(operands.front()), addrOperand) ; for (auto i=++operands.begin(); i!=operands.end(); ++i){ addrOperand = llvm->builder.CreateGEP(typEl, addrOperand, ArrayRef(std::vector{one})); llvm->builder.CreateStore(scope->process(*i), addrOperand) ; } return list; // Value* listDest = l.builder.CreateAlloca(typList, ConstantInt::get(typI32, __size), *hintRetVar); // l.buil1der.CreateMemCpy(listDest, listSource, __size, 16); } llvm::Value* Advanced::compileConstantStringAsPChar(const string& data, const std::string& hintRetVar) { EXPAND_CONTEXT UNUSED(function); UNUSED(scope); Type* typPchar = PointerType::getUnqual(Type::getInt8Ty(llvm::getGlobalContext())); //ArrayType* typStr = (ArrayType*) (llvm->toLLVMType(ExpandedType(TypeAnnotation(tag_array, TypePrimitive::I8, size+1)))); /* std::vector chars; chars.reserve(size+1); for (size_t i=0; i< size; ++i){ chars[i] = ConstantInt::get(typI8, (unsigned char) data[i]); } chars[size] = ConstantInt::get(typI8, 0); */ Value* rawData = ConstantDataArray::getString(llvm::getGlobalContext(), data); Value* rawPtrData = llvm->builder.CreateAlloca(rawData->getType(), ConstantInt::get(Type::getInt32Ty(llvm::getGlobalContext()), 1, false)); llvm->builder.CreateStore(rawData, rawPtrData); return llvm->builder.CreateCast(llvm::Instruction::BitCast, rawPtrData, typPchar, hintRetVar); } diff --git a/cpp/src/compilation/containers.cpp b/cpp/src/compilation/containers.cpp index df7c9e3..eb3c4cc 100644 --- a/cpp/src/compilation/containers.cpp +++ b/cpp/src/compilation/containers.cpp @@ -1,195 +1,195 @@ #include "compilation/containers.h" using namespace std; using namespace llvm; using namespace xreate; using namespace xreate::containers; Iterator* Iterator::create(xreate::compilation::Context context, const xreate::Symbol& var){ const Implementation& data = Query::queryImplementation(var); switch(data.impl){ case ON_THE_FLY: return new IteratorForward(context, var, data.extract()); case SOLID: return new IteratorForward(context, var, data.extract()); default: assert(true); } assert(false && "Unknown declaration"); return nullptr; } llvm::Value* IteratorForward::begin() { switch(sourceDecl.op) { case xreate::Operator::LIST: { sourceRawType = llvm::Type::getInt32Ty(llvm::getGlobalContext()); return llvm::ConstantInt::get(Type::getInt32Ty(llvm::getGlobalContext()), 0); }; case xreate::Operator::LIST_RANGE:{ assert(sourceDecl.operands.size()==2); llvm::Value* result = sourceUnit->process(sourceDecl.operands.at(0)); sourceRawType = result->getType(); return result; }; default: break; } if (linkedlist){ llvm::Value* result = sourceUnit->process(sourceDecl); sourceRawType = result->getType(); return result; } assert(false); } llvm::Value* IteratorForward::end(){ switch(sourceDecl.op) { case xreate::Operator::LIST: { size_t idLast = sourceDecl.operands.size() - 1; return ConstantInt::get(sourceRawType, idLast); } case xreate::Operator::LIST_RANGE: { assert(sourceDecl.operands.size() == 2); llvm::Value* valueEndOfRange = sourceUnit->process(sourceDecl.operands.at(1)); llvm::Value* valueConstOne = llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), 1); return llvm->builder.CreateAdd(valueEndOfRange, valueConstOne); }; default: break; } //return null pointer if (linkedlist){ return ConstantPointerNull::getNullValue(sourceRawType); } assert(false && "Unknown declaration"); return nullptr; } llvm::Value* IteratorForward::get(Value* index,const std::string& hintRetVar){ const Expression& currentDecl = CodeScope::findDeclaration(current); switch (currentDecl.op) { case xreate::Operator::LIST: { //TODO re check is it right scope(source) to compile currentDecl. Provide unittests. llvm::Value* currentValue = sourceUnit->compileSymbol(current); return xreate::compilation::Advanced(context).compileArrayIndex(currentValue, std::vector{index}); }; case xreate::Operator::LIST_RANGE: { return index; }; case xreate::Operator::MAP: { assert(currentDecl.getOperands().size()==1); assert(currentDecl.bindings.size()); assert(currentDecl.blocks.size()); CodeScope* scopeLoop = currentDecl.blocks.front(); - const std::string& varIn = currentDecl.getOperands()[0].getValueString(); std::string varEl = currentDecl.bindings[0]; - const Symbol& symbIn = current.scope->findSymbol(varIn); + const Symbol& symbIn = Attachments::get(currentDecl.getOperands()[0]); auto it = std::unique_ptr(Iterator::create(context, symbIn)); Value* elIn = it->get(index, varEl); compilation::CodeScopeUnit* unitLoop = function->getScopeUnit(scopeLoop); unitLoop->bindArg(elIn, std::move(varEl)); return unitLoop->compile(); } case xreate::Operator::NONE: { //TODO review iterator determination strategy for case of Expression::BINDING assert(currentDecl.__state==Expression::IDENT); - const Symbol& symbIn = current.scope->findSymbol(currentDecl.getValueString()); + + const Symbol& symbIn = Attachments::get(currentDecl); auto it = std::unique_ptr(Iterator::create(context, symbIn)); return it->get(index); }; default: break; } if (linkedlist){ return index; } assert(false && "Unknown declaration"); return nullptr; } llvm::Value* IteratorForward::advance(Value* index, const std::string& hintRetVar){ switch(sourceDecl.op) { case xreate::Operator::LIST: case xreate::Operator::LIST_RANGE: return llvm->builder.CreateAdd(index, llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), 1), hintRetVar); default: break; } if (linkedlist){ ExpandedType tySource = llvm->ast->expandType(CodeScope::findDeclaration(source).type); assert(tySource->__operator == TypeOperator::ARRAY && "Linked list implementation has to have ARRAY type"); assert(tySource->__operands.size()); return xreate::compilation::Advanced(context).compileStructIndex(index, ExpandedType(TypeAnnotation(tySource->__operands.at(0))), linkedlist.fieldPointer); } assert(false && "Unknown declaration"); return nullptr; } //const ImplementationRec& implementation IteratorForward::IteratorForward(const compilation::Context& ctx, const xreate::Symbol& symbolContainer, const ImplementationRec& implementation) : Iterator(), llvm(ctx.pass->man->llvm), __length(implementation.size) { __container = ctx.function->getScopeUnit(symbolContainer.scope)->compileSymbol(symbolContainer); } llvm::Value* IteratorForward::begin(){ //0 return llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), 0); } llvm::Value* IteratorForward::end(){ //length return llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), __length); } llvm::Value* IteratorForward::get(llvm::Value* index,const std::string& hintRetVar){ //GEP[index]] llvm::Type* tyNum = llvm::Type::getInt32Ty(llvm::getGlobalContext()); llvm::Value* pResult = llvm->builder.CreateGEP(__container, ArrayRef(std::vector{ConstantInt::get(tyNum, 0), index})); return llvm->builder.CreateLoad(pResult, hintRetVar); } llvm::Value* IteratorForward::advance(llvm::Value* index, const std::string& hintRetVar){ //index + 1 llvm::Type* tyNum = llvm::Type::getInt32Ty(llvm::getGlobalContext()); return llvm->builder.CreateAdd(index, llvm::ConstantInt::get(tyNum, 1), hintRetVar); } diff --git a/cpp/src/compilation/targetinterpretation.cpp b/cpp/src/compilation/targetinterpretation.cpp index b50bf13..2825235 100644 --- a/cpp/src/compilation/targetinterpretation.cpp +++ b/cpp/src/compilation/targetinterpretation.cpp @@ -1,446 +1,443 @@ /* * File: targetinterpretation.cpp * Author: pgess * * Created on June 29, 2016, 6:45 PM */ #include "compilation/targetinterpretation.h" #include "pass/interpretationpass.h" #include "llvmlayer.h" #include #include using namespace std; namespace xreate{ namespace compilation { const Expression EXPRESSION_FALSE = Expression(Atom(0)); const Expression EXPRESSION_TRUE = Expression(Atom(1)); //Expression //InterpretationScope::compile(const Expression& expression){} CodeScope* InterpretationScope::processOperatorIf(const Expression& expression){ const Expression& exprCondition = process(expression.getOperands()[0]); if (exprCondition == EXPRESSION_TRUE){ return expression.blocks.front(); } return expression.blocks.back(); } CodeScope* InterpretationScope::processOperatorSwitch(const Expression& expression) { const Expression& exprCondition = process(expression.operands[0]); bool flagHasDefault = expression.operands[1].op == Operator::CASE_DEFAULT; //TODO check that one and only one case variant is appropriate for (size_t size = expression.operands.size(), i= flagHasDefault? 2: 1; igetScope(exprCase.blocks.front())->processScope() == exprCondition){ return exprCase.blocks.back(); } } if (flagHasDefault){ const Expression& exprCaseDefault = expression.operands[1]; return exprCaseDefault.blocks.front(); } assert(false && "Switch has no appropriate variant"); return nullptr; } llvm::Value* InterpretationScope::compileHybrid(const InterpretationOperator& op, const Expression& expression, const Context& context){ switch(op){ case IF_INTERPRET_CONDITION: { CodeScope* scopeResult = processOperatorIf(expression); llvm::Value* result = context.function->getScopeUnit(scopeResult)->compile(); return result; } case SWITCH_INTERPRET_CONDITION:{ CodeScope* scopeResult = processOperatorSwitch(expression); llvm::Value* result = context.function->getScopeUnit(scopeResult)->compile(); return result; } case FOLD_INTERPRET_INPUT: { //initialization const Expression& exprInput = process(expression.getOperands()[0]); assert(exprInput.op == Operator::LIST); CodeScope* scopeBody = expression.blocks.front(); const string& nameEl = expression.bindings[0]; const Symbol& symbolEl = scopeBody->findSymbol(nameEl); const std::string& idAccum = expression.bindings[1]; llvm::Value* rawAccum = context.scope->process(expression.getOperands()[1]); compilation::CodeScopeUnit* unitBody = context.function->getScopeUnit(scopeBody); InterpretationScope* intrBody = function->getScope(scopeBody); const std::vector elementsInput= exprInput.getOperands(); for (size_t i=0; ireset(); intrBody->overrideBinding(exprElement, nameEl); unitBody->overrideDeclaration(symbolEl, move(exprElement)); unitBody->bindArg(rawAccum, string(idAccum)); rawAccum = unitBody->compile(); } return rawAccum; } case CALL_INTERPRET_PARTIAL: { const std::string &calleeName = expression.getValueString(); CodeScopeUnit* scopeUnitSelf = context.scope; ManagedFnPtr callee = this->function->man->ast->findFunction(calleeName); const FunctionInterpretationData& calleeData = FunctionInterpretationHelper::getSignature(callee); std::vector argsActual; PIFSignature sig; sig.declaration = callee; for(size_t no=0, size = expression.operands.size(); no < size; ++no){ const Expression& op = expression.operands[no]; if (calleeData.signature.at(no) == INTR_ONLY){ sig.bindings.push_back(process(op)); continue; } argsActual.push_back(scopeUnitSelf->process(op)); } TargetInterpretation* man = dynamic_cast(this->function->man); PIFunction* pifunction = man->getFunction(move(sig)); llvm::Function* raw = pifunction->compile(); boost::scoped_ptr statement(new CallStatementRaw(raw, man->pass->man->llvm)); return (*statement)(move(argsActual)); } default: break; } assert(false&& "Unknown hybrid operator"); return nullptr; } llvm::Value* InterpretationScope::compile(const Expression& expression, const Context& context){ - const InterpretationData& data = Attachments::get(expression); + const InterpretationData& data = Attachments::get(expression); if (data.op != InterpretationOperator::NONE){ return compileHybrid(data.op, expression, context); } Expression result = process(expression); return context.scope->processLowlevel(result); } Expression InterpretationScope::process(const Expression& expression){ switch (expression.__state){ case Expression::VARIANT: case Expression::INVALID: assert(false); case Expression::NUMBER: case Expression::STRING: return expression; case Expression::IDENT:{ - const std::string &ident = expression.getValueString(); - - Symbol s = scope->findSymbol(ident); + Symbol s = Attachments::get(expression); return Parent::processSymbol(s); } case Expression::COMPOUND: break; default: assert(false); } switch (expression.op) { case Operator::EQU: { const Expression& left = process(expression.operands[0]); const Expression& right = process(expression.operands[1]); if (left == right) return EXPRESSION_TRUE; return EXPRESSION_FALSE; } case Operator::NE: { const Expression& left = process(expression.operands[0]); const Expression& right = process(expression.operands[1]); if (left == right) return EXPRESSION_FALSE; return EXPRESSION_TRUE; } case Operator::LOGIC_AND: { assert(expression.operands.size() == 1); return process (expression.operands[0]); } // case Operator::LOGIC_OR: case Operator::CALL: { const std::string &fnName = expression.getValueString(); ManagedFnPtr fnAst = this->function->man->ast->findFunction(fnName); InterpretationFunction* fnUnit = this->function->man->getFunction(fnAst); vector args; args.reserve(expression.getOperands().size()); for(size_t i=0, size = expression.getOperands().size(); iprocess(args); } case Operator::IF:{ CodeScope* scopeResult = processOperatorIf(expression); return function->getScope(scopeResult)->processScope(); } case Operator::SWITCH: { CodeScope* scopeResult = processOperatorSwitch(expression); return function->getScope(scopeResult)->processScope(); } case Operator::INDEX: { - const Expression& exprKey = process(expression.operands[0]); - const Expression& exprData = processSymbol(scope->findSymbol(expression.getValueString())); - + const Expression& exprKey = process(expression.operands[1]); + const Expression& exprData = process(expression.operands[0]); if (exprKey.__state == Expression::STRING){ const string& key = exprKey.getValueString(); assert(exprData.__indexBindings.count(key)); return exprData.operands[exprData.__indexBindings.at(key)]; } if (exprKey.__state == Expression::NUMBER){ int key = exprKey.getValueDouble(); return exprData.operands[key]; } assert(false); } case Operator::FOLD: { const Expression& exprInput = process(expression.getOperands()[0]); const Expression& exprInit = process(expression.getOperands()[1]); const std::string& argEl = expression.bindings[0]; const std::string& argAccum = expression.bindings[1]; InterpretationScope* body = function->getScope(expression.blocks.front()); Expression accum = exprInit; for(size_t size=exprInput.getOperands().size(), i=0; ioverrideBinding(exprInput.getOperands()[i], argEl); body->overrideBinding(accum, argAccum); accum = body->processScope(); } return accum; } // case Operator::MAP: { // break; // } default: break; } return expression; } InterpretationFunction* TargetInterpretation::getFunction(FunctionUnit* unit){ if (__dictFunctionsByUnit.count(unit)) { return __dictFunctionsByUnit.at(unit); } InterpretationFunction* f = new InterpretationFunction(unit->function, this); __dictFunctionsByUnit.emplace(unit, f); assert(__functions.emplace(unit->function.id(), f).second); return f; } PIFunction* TargetInterpretation::getFunction(PIFSignature&& sig){ auto f = __pifunctions.find(sig); if (f != __pifunctions.end()){ return f->second; } PIFunction* result = new PIFunction(PIFSignature(sig), __pifunctions.size(), this); __pifunctions.emplace(move(sig), result); assert(__dictFunctionsByUnit.emplace(result->functionUnit, result).second); return result; } InterpretationScope* TargetInterpretation::transformContext(const Context& c){ return this->getFunction(c.function)->getScope(c.scope->scope); } llvm::Value* TargetInterpretation::transform(const Expression& expression, llvm::Value* raw, const Context& ctx){ return raw; } Expression TargetInterpretation::transform(const Expression& expression, const Context& ctx){ return transformContext(ctx)->process(expression); } llvm::Value* TargetInterpretation::compile(const Expression& expression, const Context& ctx){ return transformContext(ctx)->compile(expression, ctx); } bool TargetInterpretation::isAcceptable(const Expression& expression){ - const InterpretationData& data = Attachments::get(expression, {ANY, NONE}); + const InterpretationData& data = Attachments::get(expression, {ANY, NONE}); return (data.resolution == INTR_ONLY || data.op != InterpretationOperator::NONE); } InterpretationFunction::InterpretationFunction(const ManagedFnPtr& function, Target* target) : Function(function, target) {} Expression InterpretationFunction::process(const std::vector& args){ InterpretationScope* body = getScope(__function->__entry); for(size_t i=0, size = args.size(); ioverrideBinding(args.at(i), string(body->scope->__bindings.at(i))); } return body->processScope(); } // Partial function interpretation typedef BasicFunctionDecorator PIFunctionUnitParent; class PIFunctionUnit: public PIFunctionUnitParent{ public: PIFunctionUnit(ManagedFnPtr f, std::set&& arguments, size_t id, CompilePass* p) : PIFunctionUnitParent(f, p), argumentsActual(move(arguments)), __id(id) {} protected: std::vector prepareArguments(){ LLVMLayer* llvm = PIFunctionUnitParent::pass->man->llvm; AST* ast = PIFunctionUnitParent::pass->man->root; CodeScope* entry = PIFunctionUnitParent::function->__entry; std::vector signature; for(size_t no: argumentsActual){ Symbol arg = entry->findSymbol(entry->__bindings[no]); signature.push_back(llvm->toLLVMType(ast->expandType(entry->__declarations[arg.identifier].type))); } return signature; } llvm::Function::arg_iterator prepareBindings(){ CodeScope* entry = PIFunctionUnitParent::function->__entry; CodeScopeUnit* entryCompilation = PIFunctionUnitParent::getScopeUnit(entry); llvm::Function::arg_iterator fargsI = PIFunctionUnitParent::raw->arg_begin(); for(size_t no: argumentsActual){ Symbol arg = entry->findSymbol(entry->__bindings[no]); entryCompilation->__rawVars[arg.identifier] = &*fargsI; fargsI->setName(entry->__bindings[no]); ++fargsI; } return fargsI; } virtual std::string prepareName(){ return PIFunctionUnitParent::prepareName() + "_" + std::to_string(__id); } private: std::set argumentsActual; size_t __id; }; PIFunction::PIFunction(PIFSignature&& sig, size_t id, TargetInterpretation* target) : InterpretationFunction(sig.declaration, target), signatureInstance(move(sig)) { const FunctionInterpretationData& functionData = FunctionInterpretationHelper::getSignature(signatureInstance.declaration); std::set argumentsActual; for (size_t no=0, size=functionData.signature.size(); no < size; ++no){ if (functionData.signature.at(no) != INTR_ONLY){ argumentsActual.insert(no); } } functionUnit = new PIFunctionUnit(signatureInstance.declaration, move(argumentsActual), id, target->pass); CodeScope* entry = signatureInstance.declaration->__entry; CodeScopeUnit* entryUnit = functionUnit->getEntry(); InterpretationScope* entryIntrp = InterpretationFunction::getScope(entry); for(size_t no=0, sigNo=0, size = entry->__bindings.size(); no < size; ++no){ if (functionData.signature.at(no) == INTR_ONLY){ entryIntrp->overrideBinding(signatureInstance.bindings[sigNo], entry->__bindings[no]); entryUnit->overrideDeclaration(entry->findSymbol(entry->__bindings[no]), Expression(signatureInstance.bindings[sigNo])); ++sigNo; } } } llvm::Function* PIFunction::compile(){ llvm::Function* raw = functionUnit->compile(); return raw; } bool operator<(const PIFSignature& lhs, const PIFSignature& rhs){ if (lhs.declaration.id() != rhs.declaration.id()) { return lhs.declaration.id() < rhs.declaration.id(); } return lhs.bindings < rhs.bindings; } bool operator<(const PIFSignature& lhs, PIFunction* const rhs){ return lhs < rhs->signatureInstance; } bool operator<(PIFunction* const lhs, const PIFSignature& rhs){ return lhs->signatureInstance < rhs; } }} \ No newline at end of file diff --git a/cpp/src/compilation/targets.h b/cpp/src/compilation/targets.h index f6b47bb..fbdf860 100644 --- a/cpp/src/compilation/targets.h +++ b/cpp/src/compilation/targets.h @@ -1,161 +1,161 @@ /* * File: targetabstract.h * Author: pgess * * Created on July 2, 2016, 1:25 PM */ #ifndef TARGETABSTRACT_H #define TARGETABSTRACT_H #include "ast.h" #include #include namespace xreate{ namespace compilation { template struct TargetInfo{ //typedef Result //typedef Function //typedef Scope }; template class Function; template class Target; template class Scope{ public: CodeScope* scope; typename TargetInfo::Result processSymbol(const Symbol& s){ CodeScope* scope = s.scope; typename TargetInfo::Scope* self = function->getScope(scope); if (self->__bindings.count(s.identifier)) { return self->__bindings[s.identifier]; } const Expression& declaration = CodeScope::findDeclaration(s); if (!declaration.isDefined()){ assert(false); //for bindings there should be result already } return self->__bindings[s.identifier] = self->process(declaration); } typename TargetInfo::Result processScope() { if (raw) return *raw; raw = process(scope->getBody()); return *raw; } // typename TargetInfo::Result // processFunction(typename TargetInfo::Function* fnRemote, const std::vector::Result>& args){ // Scope scopeRemote = fnRemote->getScope(fnRemote->__function->__entry); // // if (scopeRemote->raw){ // return scopeRemote->raw; // } // // return fnRemote->process(args); // } virtual typename TargetInfo::Result process(const Expression& expression)=0; Scope(CodeScope* codeScope, Function* f) : scope(codeScope), function(f) {} virtual ~Scope(){} void overrideBinding(typename TargetInfo::Result arg, const std::string& name){ assert(scope->__identifiers.count(name)); - VID id = scope->__identifiers.at(name); + ScopedSymbol id = scope->__identifiers.at(name); __bindings[id] = arg; //reset the result if any: raw.reset(); } protected: Function* function=0; - std::map::Result> __bindings; + std::map::Result> __bindings; typename boost::optional::Result> raw; //ResultType findFunction(const std::string& callee); }; template class Function{ typedef typename TargetInfo::Result Result; public: Function(const ManagedFnPtr& function, Target* target) : man(target), __function(function) {} virtual ~Function(){}; typename TargetInfo::Scope* getScope(CodeScope* scope){ if (!__scopes.count(scope)){ typename TargetInfo::Scope* unit = new typename TargetInfo::Scope(scope, this); __scopes.emplace(scope, std::unique_ptr::Scope>(unit)); } return __scopes.at(scope).get(); } virtual Result process(const std::vector& args)=0; Target* man=0; ManagedFnPtr __function; protected: std::map::Scope>> __scopes; }; template class Target { typedef typename TargetInfo::Function ConcreteFunction; public: Target(AST* root): ast(root){} ConcreteFunction* getFunction(const ManagedFnPtr& function){ unsigned int id = function.id(); if (!__functions.count(id)){ ConcreteFunction* unit = new ConcreteFunction(function, this); __functions.emplace(id, unit); return unit; } return __functions.at(id); } AST* ast; virtual ~Target(){ for (const auto& entry: __functions){ delete entry.second; } } protected: std::map __functions; }; }} #endif /* TARGETABSTRACT_H */ \ No newline at end of file diff --git a/cpp/src/compilation/transformations.cpp b/cpp/src/compilation/transformations.cpp index d77ca83..e179651 100644 --- a/cpp/src/compilation/transformations.cpp +++ b/cpp/src/compilation/transformations.cpp @@ -1,143 +1,144 @@ -/* +/* * File: Transformations.cpp * Author: pgess - * + * * Created on June 18, 2016, 6:23 PM */ #include "compilation/transformations.h" #include "pass/compilepass.h" #include "llvmlayer.h" #include using namespace llvm; namespace xreate { namespace compilation { Transformations::Transformations(CompilePass* passCompilation): pass(passCompilation) { + Attachments::init(); } void Transformations::subscribe(const std::string& annotation, int handler){ __subscriptions.emplace(annotation, handler); } -bool +bool Transformations::isAcceptable(const Expression& expression){ //check subscription based on expression attachments - if (Attachments::get(expression, {false, 0}).flagSubscribed){ + if (Attachments::get(expression, {false, 0}).flagSubscribed){ return true; } - + //subscription based on expression annotations; if (expression.tags.size() == 0) return false; - + for (auto tag: expression.tags) { if (__subscriptions.count(tag.first)){ return true; } } - + return false; } Expression Transformations::transform(const Expression& expression, const Context& ctx){ Expression result = expression; - + for (auto handler: getAppropriateTransformers(expression)){ result = handler->transform(result, ctx); } - + return result; } -llvm::Value* +llvm::Value* Transformations::transform(const Expression& expression, llvm::Value* raw, const Context& ctx){ for (auto handler: getAppropriateTransformers(expression)){ raw = handler->transform(expression, raw, ctx); } - + return raw; } std::list Transformations::getAppropriateTransformers(const Expression& expression){ std::list result; - + for (auto tag: expression.tags) { if (__subscriptions.count(tag.first)){ auto handlers = __subscriptions.equal_range(tag.first); - + for (auto handlerIt=handlers.first; handlerIt!= handlers.second; ++handlerIt){ Transformer* handler = __transformers[handlerIt->second]; - + if (handler->isAcceptable(expression)){ result.push_back(handler); } } } } - - auto subscriberInternal = Attachments::get(expression, {false, 0}); + + auto subscriberInternal = Attachments::get(expression, {false, 0}); if (subscriberInternal.flagSubscribed){ result.push_back(__transformers[subscriberInternal.subscriberId]); } - + return result; } TransformerSaturation::TransformerSaturation(Transformations* man) : __man(man) { - + man->subscribe("break", TransformerInfo::id); } -bool +bool TransformerSaturation::isAcceptable(const Expression& expression){ return true; } bool TransformerSaturation::exists() const{ return __block != nullptr; } llvm::Value* TransformerSaturation::transform(const Expression& expression, llvm::Value* raw, const Context& ctx){ __block = __man->pass->man->llvm->builder.GetInsertBlock(); - + return raw; } -llvm::BasicBlock* +llvm::BasicBlock* TransformerSaturation::getBlock() const{ return __block; } void TransformerSaturation::inject(llvm::BasicBlock* blockAllocation, llvm::BasicBlock* blockExit, compilation::Context context){ llvm::Type* tyInt1 = llvm::Type::getInt1Ty(llvm::getGlobalContext()); llvm::Value* valueConstOne = llvm::ConstantInt::get(tyInt1, 1); llvm::Value* valueConstFalse = llvm::ConstantInt::get(tyInt1, 0); //allocation of saturation flag IRBuilder<> builderAlloca(blockAllocation, blockAllocation->getFirstInsertionPt()); llvm::Value* flagSaturation = builderAlloca.CreateAlloca(tyInt1, valueConstOne, "flagSaturation"); builderAlloca.CreateStore(valueConstFalse, flagSaturation, true); //set up saturation flag llvm::BasicBlock* blockSaturation = __block; IRBuilder<> builderSaturation(blockSaturation, blockSaturation->getFirstInsertionPt()); builderSaturation.CreateStore(valueConstOne, flagSaturation, true); //check saturation flag: //TODO remove blockContinue, receive from caller block to continue. llvm::BasicBlock *blockContinue = llvm::BasicBlock::Create(llvm::getGlobalContext(), "continue", context.function->raw); context.pass->man->llvm->builder.CreateCondBr(context.pass->man->llvm->builder.CreateLoad(flagSaturation), blockExit, blockContinue); - + context.pass->man->llvm->builder.SetInsertPoint(blockContinue); } }} \ No newline at end of file diff --git a/cpp/src/compilation/versions.cpp b/cpp/src/compilation/versions.cpp new file mode 100644 index 0000000..e69c7ec --- /dev/null +++ b/cpp/src/compilation/versions.cpp @@ -0,0 +1,56 @@ + +/* + * versions.cpp + * + * Author: pgess + * Created on January 21, 2017, 1:24 PM + */ + +typename std::list VersionInferiorsList; + +template +class VersionsScopeDecorator: public Parent{ + llvm::Value* + compileSymbol(const Symbol& s, std::string hintSymbol=""){ + if (Attachments::exists(s)){ + const VersionInferiorsList& symbolsInf= Attachments::get(s); + + for (cont Symbol& inf: symbolsInf){ + Parent::compileSymbol(inf); + } + } + + return Parent::compileSymbol(s, hintSymbol); + } + +llvm::Value* +process(const Expression& expr, const std::string& hintVarDecl){ + case Operator::CALL_INTRINSIC: { + enum INRINSIC{INIT, COPY}; + const llvm::IntegerType* tyInt = llvm::Type::getInt32Ty(llvm::getGlobalContext()); + const llvm::ConstantInt* constOne = llvm::ConstantInt::get(tyInt, 1, false); + const ExpandedType& typSymbol = pass->man->root->expandType(expr.type); + + INTRINSIC op = (INTRINSIC) expr.getValueDouble(); + + switch (op){ + case INIT: { + llvm::Type* typSymbolRaw = l.toLLVMType(typSymbol); + llvm::Value* storage = l.builder.CreateAlloca(typSymbolRaw, constOne, hintVarDecl); + + return storage; + } + + case COPY: { + llvm::Type* typSymbolRaw = l.toLLVMType(typSymbol); + llvm::value* valueOriginal = process(expr.getOperands()[0], hintVarDecl); + llvm::Value* storage = l.builder.CreateAlloca(typSymbolRaw, constOne, hintVarDecl); + llvm::Value* valueCopy = l.builder.CreateStore(valueOriginal, storage); + + return valueCopy; + } + } + return; + } +} +}; \ No newline at end of file diff --git a/cpp/src/pass/abstractpass.cpp b/cpp/src/pass/abstractpass.cpp index fc4e19f..057805a 100644 --- a/cpp/src/pass/abstractpass.cpp +++ b/cpp/src/pass/abstractpass.cpp @@ -1,35 +1,56 @@ #include "abstractpass.h" #include "attachments.h" #include "passmanager.h" using namespace std; namespace xreate { - template<> - void defaultValue(){} +template<> +void defaultValue(){} - void AbstractPassBase::finish(){} +void AbstractPassBase::finish(){} - AbstractPassBase::AbstractPassBase(PassManager *manager) - : man(manager) { - } +AbstractPassBase::AbstractPassBase(PassManager *manager) + : man(manager) { +} + +template<> +void +AbstractPass::processSymbol(const Symbol& symbol, PassContext context) +{ + if (__visitedSymbols.isCached(symbol)) + return; - template<> - void - AbstractPass::processSymbol(const std::string& ident, PassContext context) - { - const Symbol& symbol = context.scope->findSymbol(ident); + __visitedSymbols.setCachedValue(symbol); + const Expression& declaration = CodeScope::findDeclaration(symbol); - if (__visitedSymbols.isCached(symbol)) - return; + if (declaration.isDefined()){ + PassContext context2 = context.updateScope(symbol.scope); + process(declaration, context2, ident); + } +} + +template<> +void +AbstractPass::process(const Expression& expression, PassContext context, const std::string& varDecl=""){ + if (expression.__state == Expression::COMPOUND){ + for (const Expression &op: expression.getOperands()) { + process(op, context); + } - __visitedSymbols.setCachedValue(symbol); - const Expression& declaration = CodeScope::findDeclaration(symbol); + for (CodeScope* scope: expression.blocks) { + process(scope, context); + } - if (declaration.isDefined()){ - PassContext context2 = context.updateScope(symbol.scope); - process(declaration, context2, ident); + if (expression.op == Operator::CALL){ + return processExpressionCall(expression, context); } + + return; } + + + assert(false); +} } \ No newline at end of file diff --git a/cpp/src/pass/abstractpass.h b/cpp/src/pass/abstractpass.h index 328a916..61ca873 100644 --- a/cpp/src/pass/abstractpass.h +++ b/cpp/src/pass/abstractpass.h @@ -1,201 +1,190 @@ #ifndef ABSTRACTPASS_H #define ABSTRACTPASS_H #include "ast.h" #include "passmanager.h" #include namespace xreate { struct PassContext { CodeScope* scope = 0; ManagedFnPtr function; ManagedRulePtr rule; std::string varDecl; PassContext() {} PassContext&& updateScope(CodeScope* scopeNew) { PassContext context2{*this}; context2.scope = scopeNew; return std::move(context2); } ~PassContext(){} }; class AbstractPassBase { public: AbstractPassBase(PassManager* manager); virtual void run()=0; virtual void finish(); PassManager* man; }; template Output defaultValue(); template<> void defaultValue(); template class SymbolCache: private std::map{ public: bool isCached(const Symbol& symbol){ return this->count(symbol); } Output setCachedValue(const Symbol& symbol, Output&& value){ (*this)[symbol] = value; return value; } Output getCachedValue(const Symbol& symbol){ assert(this->count(symbol)); return this->at(symbol); } }; template<> class SymbolCache: private std::set{ public: bool isCached(const Symbol& symbol){ bool result = this->count(symbol) > 0; return result; } void setCachedValue(const Symbol& symbol){ this->insert(symbol); } void getCachedValue(const Symbol& symbol){ } }; template class AbstractPass: public AbstractPassBase { SymbolCache __visitedSymbols; protected: - Output processSymbol(const std::string& ident, PassContext context){ - const Symbol& symbol = context.scope->findSymbol(ident); - + Output processSymbol(const Symbol& symbol, PassContext context, std::string hintSymbol=""){ if (__visitedSymbols.isCached(symbol)) return __visitedSymbols.getCachedValue(symbol); const Expression& declaration = CodeScope::findDeclaration(symbol); if (declaration.isDefined()){ PassContext context2 = context.updateScope(symbol.scope); Output&& result = process(declaration, context2, ident); return __visitedSymbols.setCachedValue(symbol, std::move(result)); } return defaultValue(); } + Output processExpressionCall(const Expression& expression, PassContext context){ + const std::string &calleeName = expression.getValueString(); + std::list callees = man->root->getFunctionVariants(calleeName); + if (callees.size() == 1 && callees.front()){ + return processFnCall(callees.front(), context); + + } else { + for (const ManagedFnPtr& callee: callees){ + processFnCallUncertain(callee, context); + } + + return defaultValue(); + } + } + SymbolCache& getSymbolCache(){ return __visitedSymbols; } + + public: AbstractPass(PassManager* manager) : AbstractPassBase(manager){} virtual Output processFnCall(ManagedFnPtr function, PassContext context){ return defaultValue(); } virtual void processFnCallUncertain(ManagedFnPtr function, PassContext context) {} virtual void process(ManagedRulePtr rule) {} virtual Output process(ManagedFnPtr function) { PassContext context; context.function = function; return process(function->getEntryScope(), context); } virtual Output process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl=""){ context.scope = scope; - return process(scope->getBody(), context); + + return processSymbol(Symbol{ScopedSymbol::RetSymbol, scope}, context); } virtual Output process(const Expression& expression, PassContext context, const std::string& varDecl=""){ - switch (expression.__state) { - case Expression::COMPOUND: - assert(expression.op != Operator::MAP || (expression.op == Operator::MAP && expression.blocks.size())); - - //TODO there are discrepancies for SWITCH CASE scopes.case body parent scope differs from context.scope. - for (const Expression &op: expression.getOperands()) { - process(op, context); - } - - // - for (CodeScope* scope: expression.blocks) { - process(scope, context); - } - - if (expression.op == Operator::CALL) { - const std::string &calleeName = expression.getValueString(); - std::list callees = man->root->getFunctionVariants(calleeName); - if (callees.size() == 1 && callees.front()){ - processFnCall(callees.front(), context); - } else { - for (const ManagedFnPtr& callee: callees){ - processFnCallUncertain(callee, context); - } - } - } - break; - - case Expression::IDENT: - assert(context.scope); - return processSymbol(expression.getValueString(), context); - - default: - break; + if (expression.__state == Expression::IDENT){ + assert(context.scope); + return processSymbol(Attachments::get(expression), context, expression.getValueString()); } - + + assert(false); return defaultValue(); } void run() { ManagedRulePtr rule = man->root->begin(); while (rule.isValid()) { process(rule); ++rule; } ManagedFnPtr f = man->root->begin(); while (f.isValid()) { process(f); ++f; } } - }; + + private: template<> void - AbstractPass::processSymbol(const std::string& ident, PassContext context); + AbstractPass::processSymbol(const Symbol& symbol, PassContext context); + } #endif //PROCESS FUNCTION: // const Symbol& symbolFunction{0, function->getEntryScope()}; // // if (__visitedSymbols.isCached(symbolFunction)) // return __visitedSymbols.getCachedValue(symbolFunction); // // PassContext context; // context.function = function; // // Output&& result = process(function->getEntryScope(), context); // return __visitedSymbols.setCachedValue(symbolFunction, std::move(result)); \ No newline at end of file diff --git a/cpp/src/pass/compilepass.cpp b/cpp/src/pass/compilepass.cpp index 78666b5..a0a44f9 100644 --- a/cpp/src/pass/compilepass.cpp +++ b/cpp/src/pass/compilepass.cpp @@ -1,829 +1,784 @@ #include "compilepass.h" #include "clasplayer.h" #include #include "llvmlayer.h" #include "query/containers.h" #include "query/context.h" #include "compilation/containers.h" #include "compilation/transformations.h" #include "compilation/latecontextcompiler2.h" #include "ExternLayer.h" #include "pass/adhocpass.h" #include "compilation/targetinterpretation.h" #include #include #include using namespace std; using namespace xreate; using namespace xreate::compilation; using namespace llvm; //TODO use Scope //SECTIONTAG types/convert implementation //TODO type conversion: //a) automatically expand types int -> bigger int; int -> floating //b) detect exact type of `num` based on max used numeral / function type //c) warning if need to truncate (allow/dissalow based on annotations) namespace xreate { llvm::Value* doAutomaticTypeConversion(llvm::Value* source, llvm::Type* tyTarget, llvm::IRBuilder<>& builder){ if (tyTarget->isIntegerTy() && source->getType()->isIntegerTy()) { llvm::IntegerType* tyTargetInt = llvm::dyn_cast(tyTarget); llvm::IntegerType* tySourceInt = llvm::dyn_cast(source->getType()); if (tyTargetInt->getBitWidth() < tySourceInt->getBitWidth()){ return builder.CreateCast(llvm::Instruction::Trunc, source, tyTarget); } if (tyTargetInt->getBitWidth() > tySourceInt->getBitWidth()){ return builder.CreateCast(llvm::Instruction::SExt, source, tyTarget); } } if (source->getType()->isIntegerTy() && tyTarget->isFloatingPointTy()){ return builder.CreateCast(llvm::Instruction::SIToFP, source, tyTarget); } return source; } std::string BasicFunctionDecorator::prepareName(){ AST* ast = FunctionUnit::pass->man->root; string name = ast->getFunctionVariants(FunctionUnit::function->__name).size() > 1? FunctionUnit::function->__name + std::to_string(FunctionUnit::function.id()) : FunctionUnit::function->__name; return name; } std::vector BasicFunctionDecorator::prepareArguments(){ LLVMLayer* llvm = FunctionUnit::pass->man->llvm; AST* ast = FunctionUnit::pass->man->root; CodeScope* entry = FunctionUnit::function->__entry; std::vector signature; std::transform(entry->__bindings.begin(), entry->__bindings.end(), std::inserter(signature, signature.end()), [llvm, ast, entry](const std::string &arg)->llvm::Type* { assert(entry->__identifiers.count(arg)); - VID argid = entry->__identifiers.at(arg); + ScopedSymbol argid{entry->__identifiers.at(arg), VERSION_NONE}; return llvm->toLLVMType(ast->expandType(entry->__declarations.at(argid).type)); }); return signature; } llvm::Type* BasicFunctionDecorator::prepareResult(){ LLVMLayer* llvm = FunctionUnit::pass->man->llvm; AST* ast = FunctionUnit::pass->man->root; CodeScope* entry = FunctionUnit::function->__entry; - return llvm->toLLVMType(ast->expandType(entry->__declarations[0].type)); + return llvm->toLLVMType(ast->expandType(entry->__declarations.at(ScopedSymbol::RetSymbol).type)); } llvm::Function::arg_iterator BasicFunctionDecorator::prepareBindings(){ CodeScope* entry = FunctionUnit::function->__entry; CodeScopeUnit* entryCompilation = FunctionUnit::getScopeUnit(entry); llvm::Function::arg_iterator fargsI = FunctionUnit::raw->arg_begin(); for (std::string &arg : entry->__bindings) { - VID argid = entry->__identifiers[arg]; + ScopedSymbol argid = entry->__identifiers[arg]; entryCompilation->__rawVars[argid] = &*fargsI; fargsI->setName(arg); ++fargsI; } return fargsI; } //SECTIONTAG late-context FunctionDecorator template class LateContextFunctionDecorator: public Parent{ public: LateContextFunctionDecorator(ManagedFnPtr f, CompilePass* p) : Parent(f, p), contextCompiler(this, p) {} protected: std::vector prepareArguments(){ std::vector&& arguments = Parent::prepareArguments(); size_t sizeLateContextDemand = contextCompiler.getFunctionDemandSize(); if (sizeLateContextDemand) { llvm::Type* ty32 = llvm::Type::getInt32Ty(llvm::getGlobalContext()); llvm::Type* tyDemand = llvm::ArrayType::get(ty32, sizeLateContextDemand); arguments.push_back(tyDemand); } return arguments; } llvm::Function::arg_iterator prepareBindings(){ llvm::Function::arg_iterator fargsI = Parent::prepareBindings(); size_t sizeLateContextDemand = contextCompiler.getFunctionDemandSize(); if (sizeLateContextDemand){ fargsI->setName("latecontext"); contextCompiler.rawContextArgument = &*fargsI; ++fargsI; } return fargsI; } public: LateContextCompiler2 contextCompiler; }; //SECTIONTAG adhoc FunctionDecorator template class AdhocFunctionDecorator: public Parent{ public: AdhocFunctionDecorator(ManagedFnPtr f, CompilePass* p) : Parent(f, p) {} protected: llvm::Type* prepareResult(){ PassManager* man = Parent::pass->man; CodeScope* entry = Parent::function->__entry; LLVMLayer* llvm = Parent::pass->man->llvm; AST* ast = Parent::pass->man->root; AdhocPass* adhocpass = reinterpret_cast(man->getPassById(PassId::AdhocPass)); if (! Parent::function->isPrefunction){ return Parent::prepareResult(); } adhocImplementation = adhocpass->determineForScope(entry); return llvm->toLLVMType(ast->expandType(adhocImplementation->getResultType())); } public: AdhocScheme* adhocImplementation=nullptr; }; typedef LateContextFunctionDecorator< AdhocFunctionDecorator< BasicFunctionDecorator>> DefaultFunctionUnit; CodeScopeUnit::CodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass) : scope(codeScope), pass(compilePass), function(f) {} llvm::Value* CallStatementRaw::operator() (std::vector&& args, const std::string& hintDecl) { llvm::Function* calleeInfo = dyn_cast(__callee); if (calleeInfo){ auto argsFormal = calleeInfo->args(); int pos=0; //SECTIONTAG types/convert function ret value for (auto argFormal = argsFormal.begin(); argFormal!=argsFormal.end(); ++argFormal, ++pos){ args[pos] = doAutomaticTypeConversion(args[pos], argFormal->getType(), llvm->builder); } } return llvm->builder.CreateCall(__calleeTy, __callee, args, hintDecl); } //DEBT implement inlining class CallStatementInline: public CallStatement{ public: CallStatementInline(FunctionUnit* caller, FunctionUnit* callee, LLVMLayer* l) : __caller(caller), __callee(callee), llvm(l) {} llvm::Value* operator() (std::vector&& args, const std::string& hintDecl) { //TOTEST inlining // CodeScopeUnit* entryCompilation = outer->getScopeUnit(function->__entry); // for(int i=0, size = args.size(); ibindArg(args.at(i), string(entryCompilation->scope->__bindings.at(i))); // } // // // return entryCompilation->compile(); } private: FunctionUnit* __caller; FunctionUnit* __callee; LLVMLayer* llvm; bool isInline(){ // Symbol ret = Symbol{0, function->__entry}; // bool flagOnTheFly = SymbolAttachments::get(ret, false); //TODO consider inlining return false; } }; } void CodeScopeUnit::overrideDeclaration(const Symbol binding, Expression&& declaration){ function->getScopeUnit(binding.scope)->__declarationsOverriden.emplace(binding.identifier, move(declaration)); } //SECTIONTAG late-context find callee function //TOTEST static late context decisions //TOTEST dynamic late context decisions CallStatement* CodeScopeUnit::findFunction(const std::string& calleeName){ LLVMLayer* llvm = pass->man->llvm; ClaspLayer* clasp = pass->man->clasp; DefaultFunctionUnit* function = dynamic_cast(this->function); ContextQuery* queryContext = pass->queryContext; const std::list& specializations = pass->man->root->getFunctionVariants(calleeName); //if no specializations registered - check external function if (specializations.size()==0){ llvm::Function* external = llvm->layerExtern->lookupFunction(calleeName); return new CallStatementRaw(external, llvm); } //no decisions required if (specializations.size()==1){ if (!specializations.front()->guardContext.isValid()) { return new CallStatementRaw( pass->getFunctionUnit(specializations.front())->compile(), llvm); } } //TODO move dictSpecialization over to a separate function in order to perform cache, etc. //prepare specializations dictionary std::map dictSpecializations; boost::optional variantDefault; boost::optional variant; for(const ManagedFnPtr& f: specializations){ const Expression& guard = f->guardContext; //default case: if (!guard.isValid()){ variantDefault = f; continue; } assert(dictSpecializations.emplace(guard, f).second && "Found several identical specializations"); } //check static context ScopePacked scopeCaller = clasp->pack(this->scope); const string atomSpecialization = "specialization"; const Expression topicSpecialization(Operator::CALL, {(Atom(string(atomSpecialization))), (Atom(string(calleeName))), (Atom(scopeCaller))}); const Decisions& decisions = queryContext->getFinalDecisions(scopeCaller); if (decisions.count(topicSpecialization)){ variant = dictSpecializations.at(decisions.at(topicSpecialization)); } //TODO check only demand for this particular topic. size_t sizeDemand = function->contextCompiler.getFunctionDemandSize(); //decision made if static context found or no late context exists(and there is default variant) bool flagHasStaticDecision = variant || (variantDefault && !sizeDemand); //if no late context exists if (flagHasStaticDecision) { FunctionUnit* calleeUnit = pass->getFunctionUnit(variant? *variant: *variantDefault); //inlining possible based on static decision only // if (calleeUnit->isInline()) { // return new CallStatementInline(function, calleeUnit); // } return new CallStatementRaw(calleeUnit->compile(), llvm); } //require default variant if no static decision made assert(variantDefault); llvm::Function* functionVariantDefault = this->pass->getFunctionUnit(*variantDefault)->compile(); llvm::Value* resultFn = function->contextCompiler.findFunction(calleeName, functionVariantDefault, scopeCaller); llvm::PointerType *resultPTy = cast(resultFn->getType()); llvm::FunctionType *resultFTy = cast(resultPTy->getElementType()); return new CallStatementRaw(resultFn, resultFTy, llvm); } void CodeScopeUnit::bindArg(llvm::Value* value, std::string&& alias) { //reset cached compiled value if any raw = nullptr; //ensure existing of an alias assert(scope->__identifiers.count(alias)); //memorize new value for an alias - VID id = scope->__identifiers.at(alias); + ScopedSymbol id = scope->__identifiers.at(alias); __rawVars[id] = value; } llvm::Value* CodeScopeUnit::process(const Expression& expr, const std::string& hintVarDecl){ Context ctx{this, this->function, this->pass}; if (pass->targetInterpretation->isAcceptable(expr)){ return pass->targetInterpretation->compile(expr, ctx); } llvm::Value* result = processLowlevel(expr, hintVarDecl); if (pass->transformations->isAcceptable(expr)){ return pass->transformations->transform(expr, result, ctx); } return result; } llvm::Value* CodeScopeUnit::processLowlevel(const Expression& expr, const std::string& hintVarDecl){ #define DEFAULT(x) (hintVarDecl.empty()? x: hintVarDecl) llvm::Value *left; llvm::Value *right; LLVMLayer& l = *pass->man->llvm; xreate::compilation::Advanced instructions = xreate::compilation::Advanced({this, function, pass}); switch (expr.op) { case Operator::ADD: case Operator::SUB: case Operator::MUL: case Operator::DIV: case Operator::EQU: case Operator::LSS: case Operator::GTR: case Operator::NE: case Operator::LSE: case Operator::GTE: assert(expr.__state == Expression::COMPOUND); assert(expr.operands.size() == 2); left = process(expr.operands[0]); right = process(expr.operands[1]); //SECTIONTAG types/convert binary operation right = doAutomaticTypeConversion(right, left->getType(), l.builder); break; default:; } switch (expr.op) { case Operator::ADD: return l.builder.CreateAdd(left, right, DEFAULT("tmp_add")); break; case Operator::SUB: return l.builder.CreateSub(left, right, DEFAULT("tmp_sub")); break; case Operator::MUL: return l.builder.CreateMul(left, right, DEFAULT("tmp_mul")); break; case Operator::DIV: return l.builder.CreateSDiv(left, right, DEFAULT("tmp_div")); break; case Operator::EQU: if (left->getType()->isIntegerTy()) return l.builder.CreateICmpEQ(left, right, DEFAULT("tmp_equ")); if (left->getType()->isFloatingPointTy()) return l.builder.CreateFCmpOEQ(left, right, DEFAULT("tmp_equ")); break; case Operator::NE: return l.builder.CreateICmpNE(left, right, DEFAULT("tmp_ne")); break; case Operator::LSS: return l.builder.CreateICmpSLT(left, right, DEFAULT("tmp_lss")); break; case Operator::LSE: return l.builder.CreateICmpSLE(left, right, DEFAULT("tmp_lse")); break; case Operator::GTR: return l.builder.CreateICmpSGT(left, right, DEFAULT("tmp_gtr")); break; case Operator::GTE: return l.builder.CreateICmpSGE(left, right, DEFAULT("tmp_gte")); break; case Operator::NEG: left = process(expr.operands[0]); return l.builder.CreateNeg(left, DEFAULT("tmp_neg")); break; case Operator::CALL: { assert(expr.__state == Expression::COMPOUND); std::string nameCallee = expr.getValueString(); shared_ptr callee(findFunction(nameCallee)); //prepare arguments std::vector args; args.reserve(expr.operands.size()); std::transform(expr.operands.begin(), expr.operands.end(), std::inserter(args, args.end()), [this](const Expression &operand) { return process(operand); } ); ScopePacked outerScopeId = pass->man->clasp->pack(this->scope); //TASK a) refactor CALL/ADHOC/find function //SECTIONTAG late-context propagation arg size_t calleeDemandSize = pass->queryContext->getFunctionDemand(nameCallee).size(); if (calleeDemandSize){ DefaultFunctionUnit* function = dynamic_cast(this->function); llvm::Value* argLateContext = function->contextCompiler.compileContextArgument(nameCallee, outerScopeId); args.push_back(argLateContext); } return (*callee)(move(args), DEFAULT("res_"+nameCallee)); } case Operator::IF: { return instructions.compileIf(expr, DEFAULT("tmp_if")); } case Operator::SWITCH: { return instructions.compileSwitch(expr, DEFAULT("tmp_switch")); } case Operator::LOOP_CONTEXT: { return instructions.compileLoopContext(expr, DEFAULT("tmp_loop")); } case Operator::LOGIC_AND: { assert(expr.operands.size() == 1); return process (expr.operands[0]); } case Operator::LIST: { return instructions.compileListAsSolidArray(expr, DEFAULT("tmp_list")); }; case Operator::LIST_RANGE: { assert(false); //no compilation phase for a range list // return InstructionList(this).compileConstantArray(expr, l, hintRetVar); }; case Operator::LIST_NAMED: { typedef Expanded ExpandedType; ExpandedType tyRaw = l.ast->expandType(expr.type); const std::vector fields = (tyRaw.get().__operator == TypeOperator::CUSTOM)? l.layerExtern->getStructFields(l.layerExtern->lookupType(tyRaw.get().__valueCustom)) : tyRaw.get().fields; std::map indexFields; for(size_t i=0, size = fields.size(); i(l.toLLVMType(tyRaw)); llvm::Value* record = llvm::UndefValue::get(tyRecord); for (size_t i=0; igetElementType(fieldId); // result = llvm::UndefValue::get(tyNullField); // // } else { result = process(operand); // } assert (result); record = l.builder.CreateInsertValue(record, result, llvm::ArrayRef({fieldId})); } return record; }; case Operator::MAP: { assert(expr.blocks.size()); return instructions.compileMapSolidOutput(expr, DEFAULT("map")); }; case Operator::FOLD: { return instructions.compileFold(expr, DEFAULT("fold")); }; case Operator::FOLD_INF: { return instructions.compileFoldInf(expr, DEFAULT("fold")); }; case Operator::INDEX: { //TODO allow multiindex - assert(expr.operands.size()==1); - const std::string &ident = expr.getValueString(); - Symbol s = scope->findSymbol(ident); - const TypeAnnotation& t = CodeScope::findDeclaration(s).type; - const ExpandedType& t2 = pass->man->root->expandType(t); - llvm::Value* aggr = compileSymbol(s, ident); + assert(expr.operands.size()==2); + assert(expr.operands[0].__state == Expression::IDENT); + + const std::string& hintIdent= expr.operands[0].getValueString(); + Symbol s = Attachments::get(expr.operands[0]); + const ExpandedType& t2 = pass->man->root->expandType(CodeScope::findDeclaration(s).type); + + llvm::Value* aggr = compileSymbol(s, hintIdent); switch (t2.get().__operator) { case TypeOperator::STRUCT: case TypeOperator::CUSTOM: { - Expression idx = expr.operands.at(0); + const Expression& idx = expr.operands.at(1); assert(idx.__state == Expression::STRING); std::string idxField = idx.getValueString(); return instructions.compileStructIndex(aggr, t2, idxField); }; case TypeOperator::ARRAY: { std::vector indexes; - std::transform(expr.operands.begin(), expr.operands.end(), std::inserter(indexes, indexes.end()), - [this] (const Expression& op){ - return process(op); - } + std::transform(++expr.operands.begin(), expr.operands.end(), std::inserter(indexes, indexes.end()), + [this] (const Expression& op){ + return process(op); + } ); - return instructions.compileArrayIndex(aggr, indexes, DEFAULT(string("el_") + ident)); + return instructions.compileArrayIndex(aggr, indexes, DEFAULT(string("el_") + hintIdent)); }; default: assert(false); } }; //SECTIONTAG adhoc actual compilation //TODO a) make sure that it's correct: function->adhocImplementation built for Entry scope and used in another scope case Operator::ADHOC: { DefaultFunctionUnit* function = dynamic_cast(this->function); assert(function->adhocImplementation && "Adhoc implementation not found"); string comm = expr.operands[0].getValueString(); CodeScope* scope = function->adhocImplementation->getImplementationForCommand(comm); CodeScopeUnit* unitScope = function->getScopeUnit(scope); //SECTIONTAG types/convert ADHOC ret convertation llvm::Type* resultTy = l.toLLVMType( pass->man->root->expandType(function->adhocImplementation->getResultType())); return doAutomaticTypeConversion(unitScope->compile(), resultTy, l.builder); }; - case Operator::SEQUENCE: { - assert (expr.getOperands().size()); - - llvm::Value* result; - for(const Expression &op: expr.getOperands()){ - result = process(op, ""); - } - - return result; - } - case Operator::NONE: assert(expr.__state != Expression::COMPOUND); switch (expr.__state) { case Expression::IDENT: { - const std::string &ident = expr.getValueString(); - Symbol s = scope->findSymbol(ident); - return compileSymbol(s, ident); + Symbol s = Attachments::get(expr); + return compileSymbol(s, expr.getValueString()); } case Expression::NUMBER: { int literal = expr.getValueDouble(); return llvm::ConstantInt::get(llvm::Type::getInt32Ty(llvm::getGlobalContext()), literal); } case Expression::STRING: { return instructions.compileConstantStringAsPChar(expr.getValueString(), DEFAULT("tmp_str")); }; case Expression::VARIANT: { const ExpandedType& typVariant = pass->man->root->expandType(expr.type); llvm::Type* typRaw = l.toLLVMType(typVariant); int value = expr.getValueDouble(); return llvm::ConstantInt::get(typRaw, value); } default: { break; } }; break; default: break; } assert(false); return 0; } llvm::Value* CodeScopeUnit::compile(const std::string& hintBlockDecl){ if (raw != nullptr) return raw; if (!hintBlockDecl.empty()) { llvm::BasicBlock *block = llvm::BasicBlock::Create(llvm::getGlobalContext(), hintBlockDecl, function->raw); pass->man->llvm->builder.SetInsertPoint(block); } raw = process(scope->getBody()); return raw; } llvm::Value* CodeScopeUnit::compileSymbol(const Symbol& s, std::string hintRetVar) { CodeScope* scope = s.scope; CodeScopeUnit* self = function->getScopeUnit(scope); if (self->__rawVars.count(s.identifier)) { return self->__rawVars[s.identifier]; } //compilation transformations could override symbol declarations. Expression declaration = CodeScope::findDeclaration(s); if (!declaration.isDefined()){ if (self->__declarationsOverriden.count(s.identifier)){ declaration = self->__declarationsOverriden[s.identifier]; } else { assert(false); //in case of bindings there should be raws already. } } return self->__rawVars[s.identifier] = self->process(declaration, hintRetVar); } llvm::Function* FunctionUnit::compile(){ if (raw != nullptr) return raw; LLVMLayer* llvm = pass->man->llvm; llvm::IRBuilder<>& builder = llvm->builder; string&& functionName = prepareName(); std::vector&& types = prepareArguments(); llvm::Type* expectedResultType = prepareResult(); llvm::FunctionType *ft = llvm::FunctionType::get(expectedResultType, types, false); raw = llvm::cast(llvm->module->getOrInsertFunction(functionName, ft)); prepareBindings(); const std::string&blockName = "entry"; llvm::BasicBlock* blockCurrent = builder.GetInsertBlock(); llvm::Value* result =getScopeUnit(function->__entry)->compile(blockName); assert(result); //SECTIONTAG types/convert function ret value builder.CreateRet(doAutomaticTypeConversion(result, expectedResultType, llvm->builder)); if (blockCurrent){ builder.SetInsertPoint(blockCurrent); } llvm->moveToGarbage(ft); return raw; } CodeScopeUnit* FunctionUnit::getScopeUnit(CodeScope* scope){ if (!scopes.count(scope)){ CodeScopeUnit* unit = new CodeScopeUnit(scope, this, pass); scopes.emplace(scope, std::unique_ptr(unit)); } return scopes.at(scope).get(); } CodeScopeUnit* FunctionUnit::getEntry(){ return getScopeUnit(function->getEntryScope()); } CodeScopeUnit* FunctionUnit::getScopeUnit(ManagedScpPtr scope){ return getScopeUnit(&*scope); } FunctionUnit* CompilePass::getFunctionUnit(const ManagedFnPtr& function){ unsigned int id = function.id(); if (!functions.count(id)){ FunctionUnit* unit = new DefaultFunctionUnit(function, this); functions.emplace(id, unit); return unit; } return functions.at(id); } void CompilePass::run(){ transformations = new Transformations(this); transformations->registerTransformer(new TransformerSaturation(transformations)); targetInterpretation = new TargetInterpretation(this->man->root, this); queryContext = reinterpret_cast (man->clasp->getQuery(QueryId::ContextQuery)); //Find out main function; ClaspLayer::ModelFragment model = man->clasp->query(Config::get("function-entry")); assert(model && "Error: No entry function found"); assert(model->first != model->second && "Error: Ambiguous entry function"); string nameMain = std::get<0>(ClaspLayer::parse(model->first->second)); FunctionUnit* unitMain = getFunctionUnit(man->root->findFunction(nameMain)); entry = unitMain->compile(); } llvm::Function* CompilePass::getEntryFunction(){ assert(entry); return entry; } void CompilePass::prepareQueries(ClaspLayer* clasp){ clasp->registerQuery(new containers::Query(), QueryId::ContainersQuery); clasp->registerQuery(new ContextQuery(), QueryId::ContextQuery); -} - -//CODESCOPE COMPILATION PHASE - - -//FIND SYMBOL(compilation phase): - //if (!forceCompile) - //{ - // return result; - //} - - // //search in already compiled vars - //if (__rawVars.count(vId)) - //{ - // return result; - //} - - //if (!__declarations.count(vId)) { - // //error: symbol is uncompiled scope arg - // assert(false); - //} - - //const Expression& e = __declarations.at(vId); - - //__rawVars[vId] = process(e, l, name); - - -//FIND FUNCTION - //llvm::Function* - //CompilePass::findFunction(const std::string& name){ - // ManagedFnPtr calleeFunc = man->root->findFunction(name); - // assert(calleeFunc.isValid()); - - // return nullptr; - //} - +} \ No newline at end of file diff --git a/cpp/src/pass/compilepass.h b/cpp/src/pass/compilepass.h index 416de88..06ee8eb 100644 --- a/cpp/src/pass/compilepass.h +++ b/cpp/src/pass/compilepass.h @@ -1,155 +1,162 @@ #ifndef COMPILEPASS_H #define COMPILEPASS_H #include "abstractpass.h" #include "llvm/IR/Function.h" namespace xreate { class AdhocScheme; class ClaspLayer; class ContextQuery; class LLVMLayer; } //namespace llvm { // class Function; // class Value; // class Type; //} namespace xreate { class CompilePass; namespace compilation { class CodeScopeUnit; class FunctionUnit; class TargetInterpretation; struct Context{ CodeScopeUnit* scope; FunctionUnit* function; CompilePass* pass; }; class CallStatement { public: virtual llvm::Value* operator() (std::vector&& args, const std::string& hintDecl="") = 0; }; class CallStatementRaw: public CallStatement{ public: CallStatementRaw(llvm::Function* callee, LLVMLayer* l) : __callee(callee), __calleeTy(callee->getFunctionType()), llvm(l) {} CallStatementRaw(llvm::Value* callee, llvm::FunctionType* ty, LLVMLayer* l) : __callee(callee), __calleeTy(ty), llvm(l) {} llvm::Value* operator() (std::vector&& args, const std::string& hintDecl=""); private: llvm::Value* __callee; llvm::FunctionType* __calleeTy; LLVMLayer* llvm; }; class CodeScopeUnit { public: CodeScopeUnit(CodeScope* codeScope, FunctionUnit* f, CompilePass* compilePass); void bindArg(llvm::Value* value, std::string&& alias); void overrideDeclaration(const Symbol binding, Expression&& declaration); - std::map __rawVars; + std::map __rawVars; void reset(){raw = nullptr;} llvm::Value* compile(const std::string& hintBlockDecl=""); - llvm::Value* compileSymbol(const Symbol& s, std::string hintRetVar=""); + llvm::Value* compileSymbol(const Symbol& s, std::string hintRetVar="");| llvm::Value* process(const Expression& expr, const std::string& hintVarDecl=""); llvm::Value* processLowlevel(const Expression& expr, const std::string& hintVarDecl=""); CodeScope* scope; private: CompilePass* pass; llvm::Value* raw = nullptr; FunctionUnit* function; - std::unordered_map __declarationsOverriden; + std::unordered_map __declarationsOverriden; CallStatement* findFunction(const std::string& callee); }; +class IScopeDecorator{ + virtual llvm::Value* compile(const std::string& hintBlockDecl=""); + virtual llvm::Value* process(const Expression& expr, const std::string& hintVarDecl=""); + + virtual ~IScopeDecorator(){} +}; + class IFunctionDecorator { protected: virtual std::string prepareName() = 0; virtual std::vector prepareArguments() = 0; virtual llvm::Type* prepareResult() = 0; virtual llvm::Function::arg_iterator prepareBindings() = 0; virtual ~IFunctionDecorator(){} }; class FunctionUnit: public IFunctionDecorator{ public: FunctionUnit(ManagedFnPtr f, CompilePass* p) : function(f), pass(p) {} llvm::Function* compile(); CodeScopeUnit* getEntry(); CodeScopeUnit* getScopeUnit(CodeScope* scope); CodeScopeUnit* getScopeUnit(ManagedScpPtr scope); ManagedFnPtr function; llvm::Function* raw = nullptr; protected: CompilePass* pass=nullptr; private: std::map> scopes; }; class BasicFunctionDecorator: public FunctionUnit{ public: BasicFunctionDecorator(ManagedFnPtr f, CompilePass* p) : FunctionUnit(f, p) {} protected: std::string prepareName(); virtual std::vector prepareArguments(); virtual llvm::Type* prepareResult(); virtual llvm::Function::arg_iterator prepareBindings(); }; class Transformations; } // end of namespace `xreate::compilation` class CompilePass : public AbstractPass { friend class LateContextCompiler; friend class LateContextCompiler2; friend class compilation::CodeScopeUnit; friend class compilation::FunctionUnit; public: compilation::Transformations* transformations; CompilePass(PassManager* manager): AbstractPass(manager) {} compilation::FunctionUnit* getFunctionUnit(const ManagedFnPtr& function); void run() override; llvm::Function* getEntryFunction(); static void prepareQueries(ClaspLayer* clasp); private: //TODO free `functions` in destructor std::map functions; llvm::Function* entry = 0; ContextQuery* queryContext; compilation::TargetInterpretation* targetInterpretation; }; } #endif // COMPILEPASS_H diff --git a/cpp/src/pass/dfapass.cpp b/cpp/src/pass/dfapass.cpp index 7a019e1..f9d79c4 100644 --- a/cpp/src/pass/dfapass.cpp +++ b/cpp/src/pass/dfapass.cpp @@ -1,240 +1,238 @@ #include "pass/dfapass.h" #include "analysis/dfagraph.h" #include "passmanager.h" #include "clasplayer.h" #include using namespace std; using namespace xreate::analysis; namespace xreate{ DFAPass::DFAPass(PassManager* manager) : AbstractPass(manager) , __context{new xreate::analysis::DFAGraph(manager->clasp)} , clasp(manager->clasp) {} SymbolNode DFAPass::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ const SymbolNode& retActual = AbstractPass::process(scope, context, hintBlockDecl); const SymbolPacked& retFormal{0, clasp->pack(scope)}; __context.graph->addConnection(retFormal, retActual, DFGConnection::STRONG); return retFormal; } SymbolNode DFAPass::process(const Expression& expression, PassContext context, const std::string& decl) { ExpressionCache cache; if (!decl.empty()){ cache.result = clasp->pack(context.scope->findSymbol(decl), context.function->getName() + ":" + decl); } else if (!expression.tags.empty()) { cache.result = __context.graph->createAnonymousSymbol(clasp->pack(context.scope)); } else { cache.result = SymbolTransient{{}, clasp->pack(context.scope)}; } cache.operands.reserve(expression.getOperands().size()); for (const Expression &op: expression.getOperands()) { cache.operands.push_back(process(op, context)); } cache.blocks.reserve(expression.blocks.size()); for (CodeScope* scope: expression.blocks) { cache.blocks.push_back(process(scope, context)); } if (expression.__state == Expression::COMPOUND) { processCompoundOp(expression, context, cache, decl); } else { processElementaryOp(expression, context, cache, decl); } applyDependencies(expression, context, cache, decl); applyStaticAnnotations(expression, context, cache, decl); applySignatureAnnotations(expression, context, cache, decl); applyInPlaceAnnotations(expression, context, cache, decl); //TODO Null ad hoc DFG implementation // if (expression.isNone()){ // return SymbolTransient{{Atom(Config::get("clasp.nonevalue"))}}; // } //non initialized(SymbolInvalid) value return cache.result; } void DFAPass::processElementaryOp(const Expression& expression, PassContext context, DFAPass::ExpressionCache& cache, const std::string& varDecl){ switch(expression.__state) { case Expression::IDENT: { std::string identifier = expression.getValueString(); SymbolNode nodeFrom = AbstractPass::process(expression, context, identifier); if (SymbolPacked* nodeTo = boost::get(&cache.result)){ __context.graph->addConnection(*nodeTo, nodeFrom, DFGConnection::STRONG); } else { // cache.result = nodeFrom; } break; } default: break; } } void DFAPass::processCompoundOp(const Expression& expression, PassContext context, ExpressionCache& cache, const std::string& varDecl){ switch(expression.op) { //apply calling relation case Operator::CALL: { const string &nameCalleeFunction = expression.getValueString(); //TODO implement processFnCall/Uncertain list variantsCalleeFunction = man->root->getFunctionVariants(nameCalleeFunction); if (variantsCalleeFunction.size()!=1) return; ManagedFnPtr function= variantsCalleeFunction.front(); // set calling relations: CodeScope *scopeRemote = function->getEntryScope(); std::vector::iterator nodeActual = cache.operands.begin(); for (const std::string &identFormal: scopeRemote->__bindings) { const Symbol &symbolFormal = scopeRemote->findSymbol(identFormal); __context.graph->addConnection(clasp->pack(symbolFormal, nameCalleeFunction + ":" + identFormal), *nodeActual, DFGConnection::WEAK); ++nodeActual; } //TODO represent RET connection break; } //apply PROTOTYPE relation case Operator::MAP: { SymbolNode nodeFrom= cache.operands.front(); SymbolPacked* nodeFromPacked = boost::get(&nodeFrom); assert(nodeFromPacked); SymbolPacked* nodeTo = boost::get(&cache.result); assert(nodeTo); __context.graph->addConnection(*nodeTo, *nodeFromPacked, DFGConnection::PROTOTYPE); break; } default: break; } } void DFAPass::applyDependencies(const Expression& expression, PassContext context, ExpressionCache& cache, const std::string& decl){ for (SymbolNode &op: cache.operands) { __context.graph->addDependencyConnection(cache.result, op); } for (SymbolNode &block: cache.blocks) { __context.graph->addDependencyConnection(cache.result, block); } switch(expression.__state) { case Expression::IDENT: { - const string& identName = expression.getValueString(); - - SymbolNode identSymbol = clasp->pack(context.scope->findSymbol(identName), context.function->getName() + ":" + identName); + SymbolNode identSymbol = clasp->pack(Attachments::get(expression), context.function->getName() + ":" + expression.getValueString()); __context.graph->addDependencyConnection(cache.result, identSymbol); } default: break; } } void DFAPass::applyStaticAnnotations(const Expression& expression, PassContext context, ExpressionCache& cache, const std::string& decl){ switch(expression.__state) { case Expression::NUMBER: case Expression::STRING: __context.graph->addAnnotation(cache.result, Expression(Atom("static"))); break; default: break; } } void DFAPass::applySignatureAnnotations(const Expression& expression, PassContext context, ExpressionCache& cache, const std::string& decl){ if (__signatures.count(expression.op)) { const Expression &scheme = __signatures.at(expression.op); //TODO add possibility to specifi signature for a particular function // if (expression.op == Operator::CALL || expression.op == Operator::INDEX){ // string caption = expression.getValueString(); // operands.push_back(process(Expression(move(caption)), context, "")); // } std::vector::iterator arg = cache.operands.begin(); std::vector::const_iterator tag = ++scheme.getOperands().begin(); while (tag != scheme.getOperands().end()) { if (tag->__state != Expression::INVALID) { __context.graph->addAnnotation(*arg, Expression(*tag)); } ++arg; ++tag; } //TODO represent RET connection // Expression retTag = *scheme.getOperands().begin(); // if (retTag.__state != Expression::INVALID) { // __context.graph->addAnnotation(node, move(retTag)); // } } } void DFAPass::applyInPlaceAnnotations(const Expression& expression, PassContext context, ExpressionCache& cache, const std::string& decl){ // write down in-place expression tags: for (pair tag: expression.tags) { __context.graph->addAnnotation(cache.result, Expression(tag.second)); } } void DFAPass::run() { init(); return AbstractPass::run(); } void DFAPass::init() { for (const Expression& scheme: man->root->__dfadata) { __signatures.emplace(scheme.op, scheme); } } void DFAPass::finish() { man->clasp->setDFAData(move(__context.graph)); } template<> SymbolNode defaultValue(){return SymbolInvalid();}; } diff --git a/cpp/src/pass/interpretationpass.cpp b/cpp/src/pass/interpretationpass.cpp index b4d399e..0fe16b4 100644 --- a/cpp/src/pass/interpretationpass.cpp +++ b/cpp/src/pass/interpretationpass.cpp @@ -1,406 +1,410 @@ /* * File: interpretationpass.cpp * Author: pgess * * Created on July 5, 2016, 5:21 PM */ #include "pass/interpretationpass.h" #include "compilation/transformations.h" #include #include "ast.h" //DEBT implement InterpretationPass purely in clasp //DEBT represent InterpretationPass as general type inference using namespace std; namespace xreate{ enum InterpretationQuery{QUERY_INTR_ONLY, QUERY_CMPL_ONLY}; template<> InterpretationResolution defaultValue(){ return CMPL_ONLY; } InterpretationResolution unify(InterpretationResolution flag) { return flag; } template InterpretationResolution unify(FLAG_A flagA, FLAG_B flagB, FLAGS... flags) { if (flagA== ANY){ return unify(flagB, flags...); } if (flagB == ANY) { return unify(flagA, flags...); } assert(flagA == flagB); return flagA; } namespace detail { template bool checkConstraints(InterpretationResolution flag) { return ( (flag==INTR_ONLY && FLAG_REQUIRED == QUERY_INTR_ONLY) || (flag==CMPL_ONLY && FLAG_REQUIRED == QUERY_CMPL_ONLY)); } } template bool checkConstraints(std::vector&& flags) { assert(flags.size()); InterpretationResolution flag = flags.front(); return detail::checkConstraints(flag); } template bool checkConstraints(std::vector&& flags) { assert(flags.size()); InterpretationResolution flag = flags.front(); flags.pop_back(); if (detail::checkConstraints(flag)){ return checkConstraints(move(flags)); } return false; } namespace details { InterpretationResolution recognizeTags(const map& tags){ auto i = tags.find("interpretation"); if (i== tags.end()){ return ANY; } assert(i->second.op == Operator::CALL); const string& cmd = i->second.operands.at(0).getValueString(); //TODO make consistent names of annotation and resolution if (cmd == "force"){ return INTR_ONLY; } else if (cmd == "suppress"){ return CMPL_ONLY; } return ANY; } } void recognizeTags(const Expression& e){ InterpretationData tag{details::recognizeTags(e.tags), NONE}; - Attachments::put(e, tag); + Attachments::put(e, tag); } InterpretationResolution recognizeTags(const ManagedFnPtr& f){ return details::recognizeTags(f->getTags()); } InterpretationPass::InterpretationPass(PassManager* manager) - : AbstractPass(manager) {} + : AbstractPass(manager) { + + Attachments::init(); + Attachments::init(); +} void InterpretationPass::run(){ ManagedFnPtr f = man->root->begin(); auto& visitedSymbols = getSymbolCache(); while (f.isValid()) { const Symbol& symbolFunction{0, f->getEntryScope()}; if (!visitedSymbols.isCached(symbolFunction)){ visitedSymbols.setCachedValue(symbolFunction, process(f)); } ++f; } } InterpretationResolution InterpretationPass::process(const Expression& expression, PassContext context, const std::string& decl){ recognizeTags(expression); InterpretationResolution resolution = ANY; InterpretationOperator op = NONE; switch (expression.__state){ case Expression::NUMBER: case Expression::STRING: { break; } case Expression::IDENT: { resolution = Parent::processSymbol(expression.getValueString(), context); break; } case Expression::COMPOUND: break; default: { resolution = INTR_ONLY; break;} } if (expression.__state == Expression::COMPOUND) switch(expression.op){ case Operator::EQU: case Operator::NE: { InterpretationResolution left = process(expression.operands[0], context); InterpretationResolution right = process(expression.operands[1], context); resolution = unify(left, right); break; } case Operator::LOGIC_AND: { assert(expression.operands.size() == 1); resolution = process (expression.operands[0], context); break; } case Operator::CALL: { //TODO cope with static/dynamic context //TODO BUG here: if several variants they all are processed as CMPL careless of signature list callees = man->root->getFunctionVariants(expression.getValueString()); if (callees.size()!=1){ resolution = CMPL_ONLY; break; } ManagedFnPtr callee = callees.front(); const Symbol& symbCalleeFunc{0, callee->getEntryScope()}; //recursion-aware processing: // - skip self recursion const Symbol& symbSelfFunc{0, context.function->getEntryScope()}; if (!(symbSelfFunc == symbCalleeFunc)){ InterpretationResolution resCallee = processFnCall(callee, context); assert(resCallee != FUNC_POSTPONED && "Indirect recursion detected: can't decide on interpretation resolution"); resolution = unify(resolution, resCallee); } //check arguments compatibility const FunctionInterpretationData& sig = FunctionInterpretationHelper::getSignature(callee); for (size_t op=0, size = expression.operands.size(); op < size; ++op){ const Expression &operand = expression.operands[op]; InterpretationResolution argActual = process(operand, context); if (argActual == ANY) continue; assert(sig.signature[op] == argActual); } if (FunctionInterpretationHelper::needPartialInterpretation(callee)){ op= CALL_INTERPRET_PARTIAL; } break; } case Operator::IF:{ InterpretationResolution flagCondition = process(expression.getOperands()[0], context); InterpretationResolution flagScope1 = Parent::process(expression.blocks.front(), context); InterpretationResolution flagScope2 = Parent::process(expression.blocks.back(), context); //special case: IF_INTERPRET_CONDITION if (checkConstraints({flagCondition})){ op= IF_INTERPRET_CONDITION; flagCondition = ANY; } resolution = unify(flagCondition, flagScope1, flagScope2); break; } case Operator::FOLD: { InterpretationResolution flagInput = process(expression.getOperands()[0], context); InterpretationResolution flagAccumInit = process(expression.getOperands()[1], context); CodeScope* scopeBody = expression.blocks.front(); const std::string& nameEl = expression.bindings[0]; getSymbolCache().setCachedValue(scopeBody->findSymbol(nameEl), InterpretationResolution(flagInput)); const std::string& nameAccum = expression.bindings[1]; getSymbolCache().setCachedValue(scopeBody->findSymbol(nameAccum), InterpretationResolution(flagAccumInit)); InterpretationResolution flagBody = Parent::process(expression.blocks.front(), context); //special case: FOLD_INTERPRET_INPUT if (checkConstraints({flagInput})){ op= FOLD_INTERPRET_INPUT; flagInput = ANY; } resolution = unify(flagInput, flagAccumInit, flagBody); break; } case Operator::INDEX: { resolution = unify( process(expression.operands[0], context), - Parent::processSymbol(expression.getValueString(), context) + process(expression.operands[1], context), ); break; } case Operator::SWITCH: { InterpretationResolution flagCondition = process(expression.operands[0], context); bool hasDefaultCase = expression.operands[1].op == Operator::CASE_DEFAULT; //determine conditions resolution InterpretationResolution flagHeaders = flagCondition; for (size_t size = expression.operands.size(), i= hasDefaultCase? 2: 1; i({flagHeaders})){ op= SWITCH_INTERPRET_CONDITION; flagHeaders = ANY; } //determine body resolutions resolution = flagHeaders; for (size_t size = expression.operands.size(), i= 1; i(expression, {ANY, NONE}) - .resolution; + InterpretationResolution resolutionExpected = + Attachments::get(expression, {ANY, NONE}).resolution; resolution = unify(resolution, resolutionExpected); if (op!=NONE || resolution == INTR_ONLY ){ - Attachments::put(expression, {resolution, op}); + Attachments::put(expression, {resolution, op}); } if (resolution == INTR_ONLY){ compilation::Transformations::subscribe(expression); } return resolution; } InterpretationResolution InterpretationPass::processFnCall(ManagedFnPtr function, PassContext context){ const Symbol& symbolFunction{0, function->getEntryScope()}; auto& visitedSymbols = getSymbolCache(); if (visitedSymbols.isCached(symbolFunction)) return visitedSymbols.getCachedValue(symbolFunction); PassContext context2; context2.function = function; return visitedSymbols.setCachedValue(symbolFunction, Parent::process(function->getEntryScope(), context2)); } InterpretationResolution InterpretationPass::process(ManagedFnPtr function){ CodeScope* entry = function->getEntryScope(); std::vector arguments = entry->__bindings; const Symbol& symbSelfFunc{0, function->getEntryScope()}; auto& cache = getSymbolCache(); const FunctionInterpretationData& dataIntrpr = FunctionInterpretationHelper::getSignature(function); InterpretationResolution resExpected = details::recognizeTags(function->getTags()); //mark preliminary function resolution as expected if (resExpected != ANY){ cache.setCachedValue(symbSelfFunc, move(resExpected)); } else { // - in order to recognize indirect recursion mark this function resolution as POSTPONED cache.setCachedValue(symbSelfFunc, FUNC_POSTPONED); } //set resolution for function arguments as expected for (int argNo = 0, size = arguments.size(); argNo< size; ++argNo){ Symbol symbArg = entry->findSymbol(arguments[argNo]); cache.setCachedValue(symbArg, InterpretationResolution(dataIntrpr.signature[argNo])); } InterpretationResolution resActual = Parent::process(function); return unify(resActual, resExpected); } const FunctionInterpretationData FunctionInterpretationHelper::getSignature(ManagedFnPtr function){ const Symbol& symbFunc{0, function->getEntryScope()}; - if (Attachments::exists(symbFunc)){ - return Attachments::get(symbFunc); + if (Attachments::exists(symbFunc)){ + return Attachments::get(symbFunc); } FunctionInterpretationData&& data = recognizeSignature(function); - Attachments::put(symbFunc, data); + Attachments::put(symbFunc, data); return data; } FunctionInterpretationData FunctionInterpretationHelper::recognizeSignature(ManagedFnPtr function){ CodeScope* entry = function->__entry; FunctionInterpretationData result; result.signature.reserve(entry->__bindings.size()); bool flagPartialInterpretation = false; for(size_t no=0, size=entry->__bindings.size(); no < size; ++no){ const std::string& argName = entry->__bindings[no]; const Expression& arg = entry->findDeclaration(entry->findSymbol(argName)); InterpretationResolution argResolution = details::recognizeTags(arg.tags); flagPartialInterpretation |= (argResolution == INTR_ONLY); result.signature.push_back(argResolution); } result.flagPartialInterpretation = flagPartialInterpretation; return result; } bool FunctionInterpretationHelper::needPartialInterpretation(ManagedFnPtr function){ const FunctionInterpretationData& data = getSignature(function); return data.flagPartialInterpretation; } } //if (res != INTR_ONLY){ // argumentsActual.insert(no); //} diff --git a/cpp/src/pass/loggerpass.cpp b/cpp/src/pass/loggerpass.cpp index f4471c8..c7124b5 100644 --- a/cpp/src/pass/loggerpass.cpp +++ b/cpp/src/pass/loggerpass.cpp @@ -1,108 +1,110 @@ /* * logging.cpp * * Created on: Jun 23, 2015 * Author: pgess */ #include #include "compilation/containers.h" #include "utils.h" using namespace std; using namespace llvm; namespace xreate { void LoggerPass::init(ClaspLayer* clasp){ auto model = clasp->query(Config::get("logging.id")); if(!model) return; for (ClaspLayer::ModelIterator rec = model->first; rec!=model->second; ++rec){ std::tuple _v =ClaspLayer::parse(rec->second); Symbol v = clasp->unpack(get<0>(_v)); - Attachments::put(v, true); + Attachments::put(v, true); } } void LoggerPass::process(const Expression& expression, PassContext context, const std::string& varDecl){ - if (varDecl.size()){ - Symbol v = context.scope->findSymbol(varDecl); - if (Attachments::get(v, false)){ - compilation::FunctionUnit* func = compiler->getFunctionUnit(context.function); - compilation::CodeScopeUnit* scope = func->getScopeUnit(context.scope); - - compilation::Context compilationContext{scope, func, compiler}; - inject(v, compilationContext); - } - } - - return AbstractPass::process(expression, context, varDecl); + if (varDecl.size()){ + Symbol v = context.scope->findSymbol(varDecl); + if (Attachments::get(v, false)){ + compilation::FunctionUnit* func = compiler->getFunctionUnit(context.function); + compilation::CodeScopeUnit* scope = func->getScopeUnit(context.scope); + + compilation::Context compilationContext{scope, func, compiler}; + inject(v, compilationContext); + } + } + + return AbstractPass::process(expression, context, varDecl); } void LoggerPass::inject(const Symbol& symbol, const compilation::Context& context){ //TODO fix log injection // llvm::Value* source = context.scope->compileSymbol(symbol); // ExpandedType typSource = man->root->expandType(CodeScope::findDefinition(symbol).type); // string format = ""; // switch (typSource->__value) { // case TypePrimitive::Int : case TypePrimitive::Num : case TypePrimitive::I32: case TypePrimitive::I8: // format = "%d\n"; // break; // // case TypePrimitive::String: // format = "%s\n"; // break; // // default: // assert(false && "No appropriate type for logging"); // } // // xreate::compilation::Advanced instructions(context); // // LLVMLayer* llvm = context.pass->man->llvm; // llvm->builder.SetInsertPoint(llvm->builder.GetInsertBlock(), *source->use_begin()); // llvm::Value* formatRaw = instructions.compileConstantStringAsPChar(format, "logformat"); // // llvm->builder.CreateCall2(refPrintf, formatRaw, source); } void LoggerPass::initOutput(){ LLVMLayer* llvm = man->llvm; refPrintf = llvm->module->getFunction("printf"); if (!refPrintf) { PointerType* typPtrI8 = PointerType::get(IntegerType::get(llvm->module->getContext(), 8), 0); std::vectorargsPrintf{typPtrI8}; FunctionType* signaturePrintf = FunctionType::get( /*Result=*/IntegerType::get(llvm->module->getContext(), 32), /*Params=*/argsPrintf, /*isVarArg=*/true); refPrintf = llvm::Function::Create( /*Type=*/signaturePrintf, /*Linkage=*/GlobalValue::ExternalLinkage, /*Name=*/"printf", llvm->module); // (external, no body) refPrintf->setCallingConv(CallingConv::C); } } LoggerPass::LoggerPass(PassManager* manager) : AbstractPass(manager) { initOutput(); init(man->clasp); + + Attachments::init(); } void LoggerPass::initDependencies(CompilePass* pass){ compiler = pass; } } /* namespace xreate */ diff --git a/cpp/src/pass/versionspass.cpp b/cpp/src/pass/versionspass.cpp new file mode 100644 index 0000000..c02a007 --- /dev/null +++ b/cpp/src/pass/versionspass.cpp @@ -0,0 +1,85 @@ +/* + * versionspass.cpp + * + * Author: pgess + * Created on January 4, 2017, 3:13 PM + */ + +#include "versionspass.h" +#include "ast.h" +#include "abstractpass.h" + +namespace xreate { + +Symbol +getNextVersion(const Symbol& s){ + return Symbol{ScopedSymbol{s.identifier.id, s.identifier.version+1}, s.scope}; +} + +void +applyDependentUpperBound(const Symbol& symbol, const list& dependancies){ + for (const Symbol& right: dependencies){ + auto rightEnd = right.getNextVersion(); + + VersionInferiorsList& infs = Attachments::get(rightEnd); + infs.push_back(left); + } +} + +std::list +VersionsPass::process(const Expression& expression, PassContext context, const std::string& varDecl = ""){ + if (expression.__state == Expression::COMPOUND){ + std::list resultDependencies; + + for (const Expression &op: expression.getOperands()) { + std::list deps = process(op, context); + + resultDependencies.insert(std::inserter(resultDependencies, resultDependencies.end()), + deps.begin(), deps.end()); + } + + for (CodeScope* scope: expression.blocks) { + std::list deps = process(scope, context); + + resultDependencies.insert(std::inserter(resultDependencies, resultDependencies.end()), + deps.begin(), deps.end()); + } + + return resultDependencies; + } + + if (expression.__state == Expression::IDENT){ + const Symbol symb = Attachments::get(expression); + processSymbol(symb, context, expression.getValueString()); + + return {symb}; + } + + return {}; +} + +void +VersionsPass::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol){ + enum {MODE_ALIAS, MODE_COPY } mode = MODE_ALIAS; + + const Expression& declaration = CodeScope::findDeclaration(symbol); + + if (declaration.op == Operator::CALL_INTRINSIC){ + if (declaration.getValueString() == "copy"){ + mode = MODE_COPY; + } + } + + if (symbol.identifier.version != VERSION_NONE){ + mode = MODE_COPY; + } + + std::list dependencies = process(declaration); + + switch (mode) { + case MODE_COPY: applyDependentUpperBound(left, dependencies); break; + case MODE_ALIAS: applyDependentUpperBound(left.getNextVersion(), dependencies); break; + } +} + +} \ No newline at end of file diff --git a/cpp/src/pass/versionspass.h b/cpp/src/pass/versionspass.h new file mode 100644 index 0000000..2b7efeb --- /dev/null +++ b/cpp/src/pass/versionspass.h @@ -0,0 +1,18 @@ +/* + * File: versionspass.h + * Author: v.melnychenko@xreate.org + * + * Created on January 4, 2017, 3:09 PM + */ + +#ifndef VERSIONSPASS_H +#define VERSIONSPASS_H + +namespace xreate { + class VersionsPass: public AbstractPass { + void process(const Expression& expression, PassContext context, const std::string& varDecl="") override; + }; +} + +#endif /* VERSIONSPASS_H */ + diff --git a/cpp/src/query/containers.cpp b/cpp/src/query/containers.cpp index 8f37165..78b1321 100644 --- a/cpp/src/query/containers.cpp +++ b/cpp/src/query/containers.cpp @@ -1,164 +1,167 @@ // // Created by pgess on 3/14/15. // #include #include "query/containers.h" using namespace std; using namespace xreate::containers; using namespace xreate; - - Implementation Query::queryImplementation(xreate::Symbol const &s) { typedef Attachments attach; if (attach::exists(s)) { return attach::get(s); } return Implementation::create(s); } + +Query::Query(){ + Attachments::init(); +} + void Query::init(ClaspLayer* clasp) { if (flagIsDataLoaded) return; map prototypes; map roots; //read all proto data auto range = clasp->query(Config::get("containers.id.prototypes")); if (range) for(ClaspLayer::ModelIterator atom = range->first; atom != range->second; ++atom) { auto data = ClaspLayer::parse(atom->second); Symbol root = clasp->unpack(get<0> (data)); Symbol prototype = clasp->unpack(get<1> (data)); prototypes[root] = prototype; } // fill implementation data for a data sources: range = clasp->query(Config::get("containers.id.implementations")); if (range) for(ClaspLayer::ModelIterator atom = range->first; atom != range->second; ++atom) { auto data = ClaspLayer::parse(atom->second); Symbol var = clasp->unpack(get<0>(data)); string implSerialized = get<1>(data); //data source, has no prototypes: if (!prototypes.count(var)) { Implementation impl = Implementation::create(var); - Attachments::put(var, move(impl)); + Attachments::put(var, move(impl)); continue; } roots.emplace(move(var), move(implSerialized)); } //fill implementation data for a cluster roots for (const pair & root: roots) { Symbol prototype = prototypes[root.first]; while (prototypes.count(prototype)) { prototype = prototypes.at(prototype); } - Attachments::put(root.first, Implementation(Attachments::get(prototype))); + Attachments::put(root.first, Implementation(Attachments::get(prototype))); } // read cluster data and fill implementation data for cluster members range = clasp->query(Config::get("containers.id.clusters")); if (range) for(ClaspLayer::ModelIterator atom = range->first; atom != range->second; ++atom) { auto info = ClaspLayer::parse(atom->second); Symbol root = clasp->unpack(get<0>(info)); Symbol child = clasp->unpack(get<1>(info)); if (!(child == root)) { - Implementation rootImpl = Attachments::get(root); - Attachments::put(child, move(rootImpl)); + Implementation rootImpl = Attachments::get(root); + Attachments::put(child, move(rootImpl)); } } flagIsDataLoaded = true; } //static ImplementationData* create(Symbol var, std::string implSerialized, const ImplementationData* implPrototype); Implementation Implementation::create(const Symbol &var) { //TODO review implementation determination strategy Expression varDecl = CodeScope::findDeclaration(var); switch (varDecl.op) { case Operator::LIST_RANGE: { ImplementationRec rec{var}; return {ON_THE_FLY, rec}; } case Operator::LIST: { return {SOLID, ImplementationRec {varDecl.getOperands().size()}}; } default: break; }; ImplementationLinkedList ill(var); if (ill){ return ill.getImplementationData(); } assert(false && "Unable to determine proper implementation for the symbol"); } Implementation Implementation::create(const Symbol& var, const std::string& implSerialized) { Expression varDecl = CodeScope::findDeclaration(var); if (implSerialized == Config::get("containers.impl.solid")) { return {SOLID, ImplementationRec{varDecl.operands.size()}}; } else if (implSerialized == Config::get("containers.impl.onthefly")) { return {ON_THE_FLY, ImplementationRec{var}}; } assert(false && "unable to determine proper implementation for the symbol"); } ImplementationLinkedList::ImplementationLinkedList(const Symbol& source) : flagIsValid(false), s(source){ const Expression& sourceExpr = CodeScope::findDeclaration(source); if (sourceExpr.tags.count(Config::get("containers.id.linkedlist"))){ flagIsValid = true; Expression tagLinkedlist = sourceExpr.tags.at(Config::get("containers.id.linkedlist")); assert(tagLinkedlist.operands.size() == 2); fieldPointer = tagLinkedlist.operands.at(0).getValueString(); terminator = tagLinkedlist.operands.at(1); } } ImplementationLinkedList:: operator bool () const{ return flagIsValid; } Implementation ImplementationLinkedList::getImplementationData() const { return {ON_THE_FLY, ImplementationRec{s}}; } diff --git a/cpp/src/query/containers.h b/cpp/src/query/containers.h index ec474d0..35db039 100644 --- a/cpp/src/query/containers.h +++ b/cpp/src/query/containers.h @@ -1,83 +1,84 @@ // // Created by pgess on 3/14/15. // #ifndef _XREATE_CONTAINERSQUERY_H_ #define _XREATE_CONTAINERSQUERY_H_ #include "passmanager.h" #include "clasplayer.h" #include namespace xreate { namespace containers { enum ImplementationType {SOLID, ON_THE_FLY, LINKED_LIST}; template struct ImplementationRec; template<> struct ImplementationRec { size_t size; }; template<> struct ImplementationRec{ Symbol source; }; struct Implementation; struct ImplementationLinkedList { bool flagIsValid; std::string fieldPointer; Expression terminator; ImplementationLinkedList(const Symbol& source); operator bool() const; Implementation getImplementationData() const; private: Symbol s; }; struct Implementation { typedef boost::variant, ImplementationRec> Variant; const ImplementationType impl; Variant data; static Implementation create(const Symbol &var); static Implementation create(const Symbol& var, const std::string &implSerialized); static Implementation create(const Symbol& var, const Implementation& proto); template const ImplementationRec& extract() const{ const ImplementationRec& rec = boost::get>(data); return rec; } }; class Query : public xreate::IQuery { public: static Implementation queryImplementation(xreate::Symbol const &s); void init(ClaspLayer* clasp); + Query(); ~Query(){} private: bool flagIsDataLoaded = false; PassManager *man; }; } template<> struct AttachmentsDict { typedef containers::Implementation Data; static const unsigned int key = 1; }; } #endif //_XREATE_CONTAINERSQUERY_H_ diff --git a/cpp/src/serialization/expressionserializer.cpp b/cpp/src/serialization/expressionserializer.cpp index 53d6ee5..447c7d1 100644 --- a/cpp/src/serialization/expressionserializer.cpp +++ b/cpp/src/serialization/expressionserializer.cpp @@ -1,316 +1,318 @@ /* * expressionserializer.cpp * * Created on: Jan 4, 2016 * Author: pgess */ #include "serialization/expressionserializer.h" #include +#include + #include using namespace std; //using namespace boost::bimaps; namespace xreate { struct Index { string name; size_t degree; //count of parameters unsigned char level; //level in expression tree (depth of tree layer) bool operator< (const Index other) const{ if (name != other.name) return name < other.name; if (degree != other.degree) return degree < other.degree; if (name != other.name) return level < other.level; return false; } }; class ExpressionSerializerPrivate { //boost::bimap> __registry; struct { map left; } __registry; map __range; public: void pack(const Expression& e, unsigned char level, OptionalPackedExpression& target){ if (!target) return; switch (e.op){ case Operator::NONE: { switch (e.__state) { case Expression::NUMBER: case Expression::STRING: case Expression::IDENT : { Index index; if ((e.__state == Expression::NUMBER)) index = {std::to_string(e.getValueDouble()), 0, level}; else index = {e.getValueString(), 0, level}; if (!__registry.left.count(index)){ target = boost::none; return; } size_t id = __registry.left.at(index); size_t range = __range[level]; (*target) << make_pair(id, range); return; } default: break; } break; } case Operator::CALL: { Index index{e.getValueString(), e.operands.size(), level}; if(!__registry.left.count(index)){ target = boost::none; return; } size_t id = __registry.left.at(index); size_t range = __range[level]; (*target) << make_pair(id, range); for (const Expression& operand: e.operands){ pack(operand, level+1, target); } return; } default: break; } assert(false && "Expression too complicate for serialization"); } void registerExpression(const Expression&e, unsigned char level){ switch (e.op){ case Operator::CALL: { Index index{e.getValueString(), e.operands.size(), level}; if (__registry.left.insert(make_pair(index, __range[level])).second){ __range[level]++; } for (const Expression& operand: e.operands){ registerExpression(operand, level+1); } return; } case Operator::NONE: { Index index; switch (e.__state) { case Expression::STRING: case Expression::IDENT: { index = {e.getValueString(), 0, level}; if (__registry.left.insert(make_pair(index, __range[level])).second){ __range[level]++; } return; } case Expression::NUMBER: { index = {std::to_string(e.getValueDouble()), 0, level}; if (__registry.left.insert(make_pair(index, __range[level])).second){ __range[level]++; } return; } default: break; } break; } default: break; } assert(false && "Expression too complicate for serialization"); } }; ExpressionSerializer::ExpressionSerializer() : strategy(new ExpressionSerializerPrivate()){ } ExpressionSerializer::~ExpressionSerializer() { delete strategy; } void ExpressionSerializer::registerExpression(const Expression&e){ if (e.isValid()) strategy->registerExpression(e, 0); } PackedExpression ExpressionSerializer::getId(const Expression& e){ OptionalPackedExpression result(boost::in_place()); //move(PackedExpression()) strategy->pack(e, 0, result); assert(result); return move(*result); } OptionalPackedExpression ExpressionSerializer::getIdOptional(const Expression& e) const{ OptionalPackedExpression result(boost::in_place()); //move(PackedExpression()) strategy->pack(e, 0, result); return result; } ExpressionSerializerIntegral::ExpressionSerializerIntegral():serializer(*this){} ExpressionSerializerIntegral::ExpressionSerializerIntegral(const std::vector&& expressions) : std::vector(move(expressions)), serializer(*this){ size_t id =0; for (const Expression& e: expressions){ __registry.emplace(serializer.getId(e), id++); } } size_t ExpressionSerializerIntegral::size() const{ return PARENT::size(); } size_t ExpressionSerializerIntegral::count(const Expression& e) const { return (getIdOptional(e)? 1: 0); } ExpressionSerializerIntegral::const_iterator ExpressionSerializerIntegral::begin() const { return PARENT::begin(); } ExpressionSerializerIntegral::const_iterator ExpressionSerializerIntegral::end() const { return PARENT::end(); } size_t ExpressionSerializerIntegral::getId(const Expression& e) const{ const OptionalPackedExpression exprPacked = serializer.getIdOptional(e); assert(exprPacked); return __registry.at(*exprPacked); } boost::optional ExpressionSerializerIntegral::getIdOptional(const Expression& e) const{ const OptionalPackedExpression exprPacked = serializer.getIdOptional(e); if (!exprPacked){ return boost::none; } return __registry.at(*exprPacked); } const Expression& ExpressionSerializerIntegral::get(size_t id) const{ return at(id); } void PackedExpression::operator<< (const std::pair& value){ static const size_t sizeSizeT = sizeof(size_t); const size_t& id = value.first; const size_t& range = value.second; int countSufficientBits = range <=1? 0 : ceil(log2(range)); if (0 < countRemainedBits && countRemainedBits < countSufficientBits) { size_t* tail = reinterpret_cast(__storage + size- sizeSizeT); (*tail) += id >> (countSufficientBits - countRemainedBits); countSufficientBits-=countRemainedBits; countRemainedBits = 0; } if (countRemainedBits == 0) { if (countSufficientBits == 0) return; char* __storageNew = new char[size+sizeSizeT]; std::memcpy (__storageNew, __storage, size); std::memset(__storageNew + size, 0, sizeSizeT); delete[] __storage; __storage = __storageNew; size += sizeSizeT; countRemainedBits = 8 * sizeSizeT; } if (countRemainedBits >= countSufficientBits) { size_t* tail = reinterpret_cast(__storage + size- sizeSizeT); (*tail) += id << (countRemainedBits - countSufficientBits); countRemainedBits -= countSufficientBits; return; } assert("Unreachable block"); } #if BOOST_VERSION <= 105500 PackedExpression::PackedExpression(const PackedExpression& other){ __storage = other.__storage; size = other.size; countRemainedBits = other.countRemainedBits; } #endif PackedExpression::PackedExpression(PackedExpression&& other){ __storage = other.__storage; size = other.size; countRemainedBits = other.countRemainedBits; other.__storage = nullptr; } bool PackedExpression::operator==(const PackedExpression& other) const{ if (size == other.size && countRemainedBits == other.countRemainedBits){ return std::memcmp(__storage, other.__storage, size) == 0 ; } return false; } bool PackedExpression::operator<(const PackedExpression& other) const{ if (size < other.size) { return true; } if (countRemainedBits < other.countRemainedBits) return true; if (size == other.size && countRemainedBits == other.countRemainedBits){ return std::memcmp(__storage, other.__storage, size) < 0 ; } return false; } bool PackedExpression::operator!=(const PackedExpression& other) const{ return ! ((*this) == other); } PackedExpression::~PackedExpression() { delete[] __storage; } //PackedExpression::PackedExpression (const PackedExpression& other) // : size(other.size), countRemainedBits(other.countRemainedBits) //{ // __storage = new char[size]; // std::memcpy (__storage, other.__storage, size); //} } /* namespace xreate */ \ No newline at end of file diff --git a/cpp/tests/CMakeLists.txt b/cpp/tests/CMakeLists.txt index 25f9a64..4a760f1 100644 --- a/cpp/tests/CMakeLists.txt +++ b/cpp/tests/CMakeLists.txt @@ -1,25 +1,31 @@ cmake_minimum_required(VERSION 2.8.11) project(xreate-tests) find_package(GTest REQUIRED) INCLUDE_DIRECTORIES(${GTEST_INCLUDE_DIRS}) INCLUDE_DIRECTORIES("/usr/include/libxml2") INCLUDE_DIRECTORIES($) # TESTS #========================= FIND_PACKAGE (LLVM REQUIRED) message("LLVM_LIBRARY_DIRS: " ${LLVM_LIBRARY_DIRS}) link_directories(${LLVM_LIBRARY_DIRS}) set (LIBCLASP_PATH ${POTASSCO_PATH}/build/debug) link_directories(${LIBCLASP_PATH}) -aux_source_directory(. TEST_FILES) +#aux_source_directory(. TEST_FILES) +set(TEST_FILES + main.cpp + #supplemental/versions-algorithm-data_dependency.cpp + effects-versions.cpp +) + add_executable(${PROJECT_NAME} ${TEST_FILES}) target_link_libraries(${PROJECT_NAME} xreate ${GTEST_LIBRARIES} pthread xml2 gcov) add_custom_target (coverage COMMAND ${CMAKE_CURRENT_SOURCE_DIR}/src/code-coverage.sh WORKING_DIRECTORY ${CMAKE_BINARY_DIR}) diff --git a/cpp/tests/containers.cpp b/cpp/tests/containers.cpp index 9d044d5..731da87 100644 --- a/cpp/tests/containers.cpp +++ b/cpp/tests/containers.cpp @@ -1,96 +1,96 @@ /* * containers.cpp * * Created on: Jun 9, 2015 - * Author: pgess + * Author: pgess */ #include "passmanager.h" #include "query/containers.h" #include "Parser.h" #include "gtest/gtest.h" using namespace std; using namespace xreate; using namespace containers; TEST(Containers, ListAsArray){ PassManager* man = PassManager::prepareForCode( R"Code( main = function(x:: int):: int;entry { a = [1, 2, 3]:: [int]. a[x] } )Code" ); void* mainPtr = man->run(); int (*main)(int) = (int (*)(int))mainPtr; ASSERT_EQ(2, main(1)); delete man; } TEST(Containers, ListAsArray2){ PassManager* man = PassManager::prepareForCode( R"Code( main = function:: int;entry { a= [1, 2, 3]:: [int]. b= loop map(a->el:: int):: [int]{ 2 * el }. sum = loop fold(b->el:: int, 0->acc):: int { acc + el }. sum } )Code" ); void* mainPtr = man->run(); int (*main)() = (int (*)())mainPtr; ASSERT_EQ(0, main()); delete man; } TEST(Containers, ContanierLinkedList1){ FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); AST& ast = parser.root; CodeScope* body = ast.findFunction("test")->getEntryScope(); Symbol symb_chilrenRaw = body->findSymbol("childrenRaw"); containers::ImplementationLinkedList iLL(symb_chilrenRaw); ASSERT_EQ(true, static_cast(iLL)); ASSERT_EQ("next", iLL.fieldPointer); Implementation impl = Implementation::create(symb_chilrenRaw); ASSERT_NO_FATAL_FAILURE(impl.extract()); ImplementationRec recOnthefly = impl.extract(); ASSERT_EQ(symb_chilrenRaw, recOnthefly.source); } TEST(Containers, Implementation_LinkedListFull){ FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); std::unique_ptr program(PassManager::prepareForCode(input)); void* mainPtr = program->run(); int (*main)() = (int (*)())(intptr_t)mainPtr; int answer = main(); ASSERT_EQ(17, answer); fclose(input); } diff --git a/cpp/tests/effects-versions.cpp b/cpp/tests/effects-versions.cpp new file mode 100644 index 0000000..0a5b4ba --- /dev/null +++ b/cpp/tests/effects-versions.cpp @@ -0,0 +1,75 @@ +/* + * Created on: Dec 16, 2016 + * Author: pgess + */ + +#include "passmanager.h" + +#include "gtest/gtest.h" + +using namespace xreate; + +TEST(Effects, syntax_recognizeIdentifiers){ + PassManager* man = PassManager::prepareForCode(R"Code( + test= function(a:: num):: num; entry { + a = b:: int. + b = 8:: int. + + a + } + )Code"); +} + +TEST(Effects, syntax_operatorIndex){ + PassManager* man = PassManager::prepareForCode(R"Code( + test= function(a:: num):: num; entry { + b = a[1]. + b + } + )Code"); +} + +TEST(Effects, syntax_versions_1){ + PassManager* man = PassManager::prepareForCode(R"Code( + test= function(a:: num):: num; entry { + x= b[8]. + b = 5:: num. + x{1} = a:: num. + + x{1} + a + } + )Code"); +} + +TEST(Effects, analysis_versions_1){ + PassManager* man = PassManager::prepareForCode(R"Code( + test= function(a:: num):: num; entry { + x= b[8]. + b = 5. + x{1} = a. + + x{1} + a + } + )Code"); + + + VersionsPass* pass = new VersionsPass(); + pass->run(); + pass->finish(); +} + +TEST(Effects, analysis_versions_copy){ + +} + +TEST(Effects, syntax_references1){ + +} + +TEST(Effects, syntax_scope_versions1){ + +} + +TEST(Effects, DynamicVersions_analysis){ + +} \ No newline at end of file diff --git a/cpp/tests/interpretation.cpp b/cpp/tests/interpretation.cpp index 615ad92..cfff9d1 100644 --- a/cpp/tests/interpretation.cpp +++ b/cpp/tests/interpretation.cpp @@ -1,340 +1,340 @@ #include "attachments.h" using namespace xreate; #include "passmanager.h" #include "compilation/targetinterpretation.h" #include "gtest/gtest.h" #include "boost/scoped_ptr.hpp" #define private public #include "Parser.h" #include "pass/interpretationpass.h" using namespace xreate; using namespace xreate::compilation; TEST(Interpretation, Analysis_StatementIF_1){ PassManager* man = PassManager::prepareForCode( R"Code( main = function::int { x = "a":: string. y = if (x=="b"):: string; interpretation(force) { 1 } else { 0 }. y } )Code" ); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } Symbol symbolY = man->root->findFunction("main")->__entry->findSymbol("y"); - InterpretationData& dataSymbolY = Attachments::get(symbolY); + InterpretationData& dataSymbolY = Attachments::get(symbolY); ASSERT_EQ(INTR_ONLY, dataSymbolY.resolution); } TEST(Interpretation, Compilation_StatementIF_1){ PassManager* man = PassManager::prepareForCode( R"Code( main = function::int; entry { x = "a":: string. y = if (x=="b"):: string; interpretation(force) { 1 } else { 0 }. y } )Code" ); man->runWithoutCompilation(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(0, result); } TEST(Interpretation, Analysis_StatementIF_InterpretCondition_1){ PassManager* man = PassManager::prepareForCode( R"Code( main = function(x:: int):: int { comm= "inc":: string. y = if (comm == "inc") {x+1} else {x}. y } )Code" ); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } Symbol symbolY = man->root->findFunction("main")->__entry->findSymbol("y"); - InterpretationData& dataSymbolY = Attachments::get(symbolY); + InterpretationData& dataSymbolY = Attachments::get(symbolY); ASSERT_EQ(ANY, dataSymbolY.resolution); ASSERT_EQ(IF_INTERPRET_CONDITION, dataSymbolY.op); } TEST(Interpretation, Compilation_StatementIF_InterpretCondition_1){ PassManager* man = PassManager::prepareForCode( R"Code( main = function(x:: int):: int; entry { comm= "inc":: string; interpretation(force). y = if (comm == "inc") {x+1} else {x}. y } )Code" ); man->runWithoutCompilation(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } int (*main)(int) = (int (*)(int))man->run(); int result = main(1); ASSERT_EQ(2, result); } TEST(Interpretation, Compilation_StatementFOLD_INTERPRET_INPUT_1){ PassManager* man = PassManager::prepareForCode( R"Code( main = function(x:: int):: int; entry { commands = ["inc", "double", "dec"]:: [string]; interpretation(force). loop fold(commands->comm::string, x->operand):: int{ switch(comm)::int case ("inc"){ operand + 1 } case ("dec"){ operand - 1 } case ("double"){ operand * 2 } } } )Code" ); man->runWithoutCompilation(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } int (*main)(int) = (int (*)(int))man->run(); int result = main(10); ASSERT_EQ(21, result); } TEST(Interpretation, StatementCall_RecursionNo_1){ PassManager* man = PassManager::prepareForCode( R"Code( unwrap = function(data::undef, keys::undef):: undef; interpretation(force){ loop fold(keys->key::string, data->a):: undef { a[key] } } start = function::num; entry{ result = unwrap( { a = { b = { c = "core" } } }, ["a", "b", "c"])::undef. result == "core" } )Code" ); man->runWithoutCompilation(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(1, result); } TEST(Interpretation, StatementCall_RecursionDirect_1){ PassManager* man = PassManager::prepareForCode( R"Code( unwrap = function(data:: X):: Y { if (data[0] == "a")::Y {0} else {unwrap(data[0])} } entry = function:: i8; entry { unwrap([[[["a"]]]]):: i8; interpretation(force) } )Code" ); man->runWithoutCompilation(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } InterpretationResolution resolutionActual = pass->process(man->root->findFunction("unwrap")); ASSERT_EQ(ANY, resolutionActual); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(0, result); } TEST(Interpretation, StatementCall_RecursionIndirect_1){ PassManager* man = PassManager::prepareForCode( R"Code( funcA = function(data:: X):: Y { if (data == "a")::Y {0} else {funcB(data)} } funcB = function(data:: X):: Y { if (data == "b")::Y {1} else {funcA(data)} } entry = function:: i8; entry { funcA(""):: i8; interpretation(force) } )Code" ); InterpretationPass* pass = new InterpretationPass(man); ASSERT_DEATH(pass->run(), "Indirect recursion detected"); } TEST(Interpretation, PartialIntr_1){ PassManager* man = PassManager::prepareForCode( R"Code( evaluate= function(argument:: num, code:: string; interpretation(force)):: num { switch(code)::int case ("inc") {argument + 1} case ("dec") {argument - 1} case ("double") {argument * 2} } main = function::int; entry { commands= ["inc", "double", "dec"]:: [string]; interpretation(force). loop fold(commands->comm::string, 10->operand):: int{ evaluate(operand, comm) } } )Code" ); InterpretationPass* pass = new InterpretationPass(man); pass->run(); ManagedFnPtr fnEvaluate = man->root->findFunction("evaluate"); InterpretationResolution resFnEvaluate= pass->process(fnEvaluate); ASSERT_EQ(CMPL_ONLY, resFnEvaluate); ASSERT_TRUE(FunctionInterpretationHelper::needPartialInterpretation(fnEvaluate)); const Expression& exprLoop = man->root->findFunction("main")->__entry->getBody(); Symbol symbCallEv{0, exprLoop.blocks.front()}; - InterpretationData dataCallEv = Attachments::get(symbCallEv); + InterpretationData dataCallEv = Attachments::get(symbCallEv); ASSERT_EQ(CMPL_ONLY, dataCallEv.resolution); ASSERT_EQ(CALL_INTERPRET_PARTIAL, dataCallEv.op); } TEST(Interpretation, PartialIntr_2){ PassManager* man = PassManager::prepareForCode( R"Code( evaluate= function(argument:: num, code:: string; interpretation(force)):: num { switch(code)::int case ("inc") {argument + 1} case ("dec") {argument - 1} case ("double") {argument * 2} case default {argument} } main = function::int; entry { commands= ["inc", "double", "dec"]:: [string]; interpretation(force). loop fold(commands->comm::string, 10->operand):: int{ evaluate(operand, comm) } } )Code" ); InterpretationPass* pass = new InterpretationPass(man); pass->run(); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(21, result); } //TOTEST call indirect recursion(w/o tags) //TASK implement and test Loop Inf (fix acc types in coco grammar) diff --git a/cpp/tests/supplemental/versions-algorithm-data_dependency.cpp b/cpp/tests/supplemental/versions-algorithm-data_dependency.cpp new file mode 100644 index 0000000..59ae20f --- /dev/null +++ b/cpp/tests/supplemental/versions-algorithm-data_dependency.cpp @@ -0,0 +1,260 @@ + +/* + * File: algorithm-data_dependency + * Date: Dec 23, 2016 + * Author: pgess + */ + +#include +#include +#include +#include +#include "gtest/gtest.h" +#include +#include + + +const int V_NOVERSION = -2; +const int V_ENDOFLIFE = -1; + +struct Symbol { + std::string name; + int version; + + Symbol getNextVersion() const{ + return Symbol{name, version+1}; + } +}; + +namespace std +{ + template<> + struct hash + { + typedef Symbol argument_type; + typedef std::size_t result_type; + result_type operator()(argument_type const& s) const + { + result_type const h1 ( std::hash()(s.name) ); + return h1 ^ (s.version << 1); // or use boost::hash_combine + } + }; + + template<> + struct equal_to + { + typedef Symbol argument_type; + + bool operator()(const argument_type& __x, const argument_type& __y) const + { return __x.name == __y.name && __x.version == __y.version; } + }; +} + +//Ограничения: +// - точно знаем следующую версию на этапе декл. (C.NV.1) + +class DDSolver{ +public: + + void l1_applyLowerBound(const Symbol& left, const std::initializer_list& dependencies){ + for (Symbol right: dependencies){ + //lower bound: + __infs.emplace(left, right); + __sups.emplace(right, left); + } + } + + void l1_applyOwnUpperBound(const Symbol& left){ + //own upper bound: + //C.NV.1 + __infs.emplace(left.getNextVersion(), left); + __sups.emplace(left, left.getNextVersion()); + } + + void l1_applyDependentUpperBound(const Symbol& left, const std::initializer_list& dependencies){ + // additionally apply dependent upper bound + for (Symbol right: dependencies){ + auto right2 = right.getNextVersion(); + + __infs.emplace(right2, left); + __sups.emplace(left, right2); + } + } + + void addVariable(const Symbol& left, const std::initializer_list& dependencies){ + l1_applyLowerBound(left, dependencies); + l1_applyOwnUpperBound(left); + + //initialization upper bound + l1_applyDependentUpperBound(left, dependencies); + + } + + //TODO assert: only aliases allowed + void addAlias(const Symbol& left, const std::initializer_list& dependencies){ + l1_applyLowerBound(left, dependencies); + l1_applyOwnUpperBound(left); + + //lifetime upper bound + l1_applyDependentUpperBound(left.getNextVersion(), dependencies); + } + + + bool checkCyclicComponent(const Symbol& s, std::unordered_set& symbolsVisited, std::unordered_set& symbolsSups){ + if (symbolsVisited.count(s)) return false; + + symbolsVisited.insert(s); + symbolsSups.insert(s); + + auto rangeInf = __infs.equal_range(s); + if (__infs.count(s)) + for (auto sInf = rangeInf.first; sInf != rangeInf.second; ++sInf){ + if (symbolsSups.count(sInf->second)) { + __flagCycle = std::make_pair(sInf->second, s); + return true; + } + if(checkCyclicComponent(sInf->second, symbolsVisited, symbolsSups)) return true; + } + + symbolsSups.erase(s); + return false; + } + + bool checkCyclicFull(){ + std::unordered_set symbolsVisited, symbolsSups; + + std::unordered_multimap::iterator s; + for (s = __infs.begin(); s != __infs.end(); ++s){ + if(checkCyclicComponent(s->first, symbolsVisited, symbolsSups)) return true; + } + + return false; + } + + bool validate(){ + return !checkCyclicFull(); + } + + void solve(){ + std::unordered_set binEnabled, binFrontier; + + //seed + for (auto edge: __sups){ + if (! __infs.count(edge.first)){ + binEnabled.insert(edge.first); + binFrontier.insert(edge.first); + } + } + + while (binFrontier.size()){ + const Symbol& node= *binFrontier.begin(); + + //print node: + std:: printf("put (%s, %d)\n", node.name.c_str(), node.version); + + auto rangeSups = __sups.equal_range(node); + for(auto sup=rangeSups.first; sup != rangeSups.second; ++sup){ + bool flagEnabled = true; + + auto rangeInfs = __infs.equal_range(sup->second); + for (auto inf=rangeInfs.first; inf != rangeInfs.second; ++inf){ + if (!binEnabled.count(inf->second)){ + flagEnabled = false; + break; + } + } + + if (flagEnabled){ + binEnabled.insert(sup->second); + binFrontier.insert(sup->second); + } + } + + binFrontier.erase(node); + } + } + + void solve2(Symbol nodeEntry, std::unordered_set& binPreviousNodes, std::unordered_set& binEnabledNodes){ + binPreviousNodes.insert(nodeEntry); + + auto rangeChilds = __infs.equal_range(nodeEntry); + for(auto node=rangeChilds.first; node != rangeChilds.second; ++node){ + if (binEnabledNodes.count(node->second)) continue; + + auto nodeError = binPreviousNodes.find(node->second); + if (nodeError != binPreviousNodes.end()){ + std:: printf("(%s, %d) - (%s, %d)", + nodeError->name.c_str(), nodeError->version, + node->second.name.c_str(), node->second.version); + assert(true); + } + + solve2(node->second, binPreviousNodes, binEnabledNodes); + } + + std:: printf("put (%s, %d)\n", nodeEntry.name.c_str(), nodeEntry.version); + binEnabledNodes.insert(nodeEntry); + binPreviousNodes.erase(nodeEntry); + +// auto rangeParents = __sups.equal_range(nodeEntry); +// for(auto node=rangeParents.first; node != rangeParents.second; ++node){ +// std::unordered_set binEmpty; +// solve2(node->second, binEmpty, binEnabledNodes); +// } + } + + void __debug_printGraph(){ + for (auto edge: __infs){ + std:: printf("(%s, %d) <- (%s, %d) \n", + edge.second.name.c_str(), edge.second.version, + edge.first.name.c_str(), edge.first.version); + } + } + +private: + std::unordered_multimap __sups; + std::unordered_multimap __infs; + +public: + std::pair __flagCycle; +}; + +//TEST(Datadependency, test1){ +// DDSolver solver; +// +// solver.addAlias(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}}); +// solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}}); +// solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}}); +// +// solver.__debug_printGraph(); +// +// ASSERT_FALSE(solver.validate()); +// +// std:: printf("(%s, %d) - (%s, %d)", +// solver.__flagCycle.first.name.c_str(), solver.__flagCycle.first.version, +// solver.__flagCycle.second.name.c_str(), solver.__flagCycle.second.version); +//} + +//TEST(Datadependency, test2){ +// DDSolver solver; +// +// solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}}); +// solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}}); +// solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}}); +// +// ASSERT_TRUE(solver.validate()); +// +// solver.solve(); +//} + +TEST(Datadependency, test3){ + DDSolver solver; + + solver.addVariable(Symbol{"c", V_NOVERSION}, {Symbol{"a", 0}}); + solver.addVariable(Symbol{"a", 1}, {Symbol{"b", 0}}); + solver.addVariable(Symbol{"b", 1}, {Symbol{"c", V_NOVERSION}}); + + std::unordered_set binPreviousNodes, binEnabledNodes; + solver.solve2(Symbol{"b", 1}, binPreviousNodes, binEnabledNodes); + ASSERT_TRUE(true); +} \ No newline at end of file