diff --git a/config/default.json b/config/default.json index 549acb7..d5965dd 100644 --- a/config/default.json +++ b/config/default.json @@ -1,73 +1,73 @@ { "containers": { "id": { "implementations": "impl_fulfill_cluster", "clusters": "var_cluster", "prototypes": "proto_cluster", "linkedlist": "linkedlist" }, "impl": { "solid": "solid", "onthefly": "on_the_fly" } }, "logging": { "id": "logging" }, "function-entry": "entry", "clasp": { "bindings" : { "variable": "bind", "function": "bind_func", "scope": "bind_scope", "function_demand" : "bind_function_demand", "scope_decision": "bind_scope_decision" }, "context" : { "decisions":{ "dependent": "resolution_dependency" } }, "nonevalue": "nonevalue", "ret": { "symbol": "retv", "tag": "ret" } }, "tests": { - "template": "exploitation", + "template": "default", "templates": { - "current-fix":"CFA.DomReportOneRoot", + "current-fix":"*", "default": "*-Adhoc.*:Containers.*:Compilation.full_IFStatementWithVariantType:Types.full_VariantType_Switch1:Context.full_LateContext:Context.pathDependentContext", - "exploitation": "Exploitation.*", "ast": "AST.*", "adhocs": "Adhoc.*", "effects": "Effects.*", "basic": "Attachments.*", "context": "Context.*", "compilation": "Compilation.*-Compilation.full_IFStatementWithVariantType", "communication": "Communication.*", "cfa": "CFA.*", "containers": "Containers.*", "dfa": "DFA.*", "diagnostic": "Diagnostic.*", "dsl": "Association.*:Interpretation.SwitchVariantAlias", + "exploitation": "Exploitation.*", "ExpressionSerializer": "ExpressionSerializer.*", "externc": "InterfaceExternC.*", "loops": "Loop.*", "modules": "Modules.*", "polymorphs": "Polymorphs.call1", "types": "Types.*", "vendorsAPI/clang": "ClangAPI.*", "vendorsAPI/xml2": "libxml2*" } } } diff --git a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp b/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp index 4aaab5b..cb185db 100644 --- a/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp +++ b/cpp/src/analysis/DominatorsTreeAnalysisProvider.cpp @@ -1,241 +1,245 @@ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * File: DominatorsTreeAnalysisProvider.cpp * Author: pgess * * Created on May 13, 2016, 11:39 AM */ /** * \file DominatorsTreeAnalysisProvider.h * \brief Dominators Tree analysis */ #include "analysis/cfagraph.h" #include "analysis/DominatorsTreeAnalysisProvider.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/Support/GenericDomTreeConstruction.h" #include "llvm/Support/GenericDomTree.h" #include #include #include using namespace std; using namespace xreate; using namespace boost; using namespace boost::bimaps; namespace xreate { namespace dominators { struct CFAGraphAdapter; struct ScopeNode { ScopePacked id; std::list nodesFrom; std::list nodesTo; }; struct CFAGraphAdapter { std::list nodes; ScopeNode* nodeRoot; ScopeNode* getOrCreateNode(ScopePacked id){ ScopeNode elemNew; elemNew.id = id; auto fnComp = [](const ScopeNode &a, const ScopeNode &b){return a.id < b.id;}; auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), elemNew, fnComp); if(posLowerBound==nodes.end()|| posLowerBound->id > id){ return &*nodes.insert(posLowerBound, elemNew); } return &*posLowerBound; } static CFAGraphAdapter* build(const cfa::CFAGraph* graph) { CFAGraphAdapter* tree=new CFAGraphAdapter(); enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT}; std::unordered_map nodeMarks; for (const auto& edge: graph->__dependencyRelations){ ScopeNode* nodeTo = tree->getOrCreateNode(edge.first); ScopeNode* nodeFrom = tree->getOrCreateNode(edge.second); nodeTo->nodesFrom.push_back(nodeFrom); nodeFrom->nodesTo.push_back(nodeTo); nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update if(!result.second){ result.first->second = NO_ROOT; } } std::list nodeRoots; for(auto nodeMark: nodeMarks){ if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first); } if(nodeRoots.size()>1){ ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL); for(auto rootLocal: nodeRoots){ ScopeNode* nodeLocalRoot = tree->getOrCreateNode(rootLocal); nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot); nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot); } - } else { - assert(nodeRoots.size()==1); + + } else if (nodeRoots.size()==1){ tree->nodeRoot = tree->getOrCreateNode(nodeRoots.front()); + + } else { + ScopeNode* nodeGlobalRoot = tree->getOrCreateNode(SCOPE_ABSTRACT_GLOBAL); + tree->nodeRoot = nodeGlobalRoot; } return tree; } CFAGraphAdapter() { } }; } } //end of namespace xreate::dominators namespace llvm { using namespace xreate::dominators; template<> struct GraphTraits { typedef ScopeNode NodeType; typedef std::list::iterator ChildIteratorType; static ChildIteratorType child_begin(NodeType* node) { return node->nodesTo.begin(); } static ChildIteratorType child_end(NodeType* node) { return node->nodesTo.end(); } }; template<> struct GraphTraits : public GraphTraits { typedef std::list::iterator nodes_iterator; static nodes_iterator nodes_begin(CFAGraphAdapter* graph) { return graph->nodes.begin(); } static nodes_iterator nodes_end(CFAGraphAdapter* graph) { return graph->nodes.end(); } static NodeType* getEntryNode(CFAGraphAdapter* F) { return F->nodeRoot; } static unsigned int size(CFAGraphAdapter* graph) { return graph->nodes.size(); } }; template<> struct GraphTraits> { typedef ScopeNode NodeType; typedef std::list::iterator ChildIteratorType; static ChildIteratorType child_begin(NodeType* node) { return node->nodesFrom.begin(); } static ChildIteratorType child_end(NodeType* node) { return node->nodesFrom.end(); } }; } namespace xreate { namespace dominators { class DominatorTree : public llvm::DominatorTreeBase { public: DominatorsTreeAnalysisProvider::Dominators dominators; DominatorTree(bool isPostDom) : llvm::DominatorTreeBase(isPostDom) { } void run(CFAGraphAdapter& program) { recalculate(program); //extract dominators info for(auto& entry : DomTreeNodes) { if(!entry.getFirst()) continue; dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut())); } } void print(std::ostringstream& output, const std::string& atom) const { boost::format formatAtom(atom+"(%1%, range(%2%, %3%))."); for(auto entry : dominators) { output< program(CFAGraphAdapter::build(graph)); treeForwardDominators->run(*program); treePostDominators->run(*program); } void DominatorsTreeAnalysisProvider::print(std::ostringstream& output) const { treeForwardDominators->print(output, "cfa_forwdom"); treePostDominators->print(output, "cfa_postdom"); } const DominatorsTreeAnalysisProvider::Dominators& DominatorsTreeAnalysisProvider::getForwardDominators() const { return treeForwardDominators->dominators; } const DominatorsTreeAnalysisProvider::Dominators& DominatorsTreeAnalysisProvider::getPostDominators() const { return treePostDominators->dominators; } DominatorsTreeAnalysisProvider::DominatorsTreeAnalysisProvider() : treeForwardDominators(new DominatorTree(false)) , treePostDominators(new DominatorTree(true)) { } DominatorsTreeAnalysisProvider::~DominatorsTreeAnalysisProvider() { } } } //end of namespace xreate::dominators //void //CodeScopesTree::print(){ // typedef llvm::GraphTraits Traits; // for (size_t i=0; i" << (*j)->scope << endl; // } // } //} diff --git a/cpp/tests/interpretation.cpp b/cpp/tests/interpretation.cpp index 9af16a9..a017579 100644 --- a/cpp/tests/interpretation.cpp +++ b/cpp/tests/interpretation.cpp @@ -1,468 +1,468 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * interpretation.cpp * * Created on: - * Author: pgess */ #include "attachments.h" using namespace xreate; #include "xreatemanager.h" #include "compilation/targetinterpretation.h" #include "gtest/gtest.h" #include "boost/scoped_ptr.hpp" //#define FRIENDS_INTERPRETATION_TESTS \ // friend class ::Modules_AST2_Test; \ // friend class ::Modules_Discovery1_Test; \ // friend class ::Modules_Solve1_Test; #include "pass/interpretationpass.h" using namespace xreate::grammar::main; using namespace xreate::interpretation; TEST(Interpretation, Analysis_StatementIF_1){ XreateManager* man = XreateManager::prepare( R"Code( main = function::bool { x = "a":: string. y = if (x=="b"):: bool; interpretation(force) { true } else { false }. y } )Code" ); InterpretationPass* pass = new InterpretationPass(man); pass->run(); CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); Symbol symbolY{scopeEntry->getSymbol("y"), scopeEntry}; InterpretationData& dataSymbolY = Attachments::get(symbolY); ASSERT_EQ(INTR_ONLY, dataSymbolY.resolution); } TEST(Interpretation, Compilation_StatementIF_1){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"Code( main = function::int; entry { x = "a":: string. y = if (x=="b"):: string; interpretation(force) { 1 } else { 0 }. y } )Code" ); man->analyse(); 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){ XreateManager* man = XreateManager::prepare( R"Code( main = function(x:: int):: int { comm= "inc":: string; interpretation(force). y = if (comm == "inc")::int {x+1} else {x}. y } )Code" ); InterpretationPass* pass = new InterpretationPass(man); pass->run(); CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); Symbol symbolY{scopeEntry->getSymbol("y"), scopeEntry}; InterpretationData& dataSymbolY = Attachments::get(symbolY); ASSERT_EQ(CMPL_ONLY, dataSymbolY.resolution); ASSERT_EQ(IF_INTERPRET_CONDITION, dataSymbolY.op); } TEST(Interpretation, Compilation_StatementIF_InterpretCondition_1){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"Code( main = function(x:: int):: int; entry { comm= "inc":: string; interpretation(force). y = if (comm == "inc")::int {x+1} else {x}. y } )Code" ); man->analyse(); 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){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( 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->analyse(); InterpretationPass* pass; if (man->isPassRegistered(PassId::InterpretationPass)){ pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); } else { pass = new InterpretationPass(man); pass->run(); } const ManagedFnPtr& funcMain = man->root->findFunction("main"); InterpretationData& dataBody = Attachments::get(funcMain); ASSERT_EQ(FOLD_INTERPRET_INPUT, dataBody.op); int (*main)(int) = (int (*)(int))man->run(); int result = main(10); ASSERT_EQ(21, result); } TEST(Interpretation, StatementCall_RecursionNo_1){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"Code( - unwrap = function(data::undef, keys::undef):: undef; interpretation(force){ - loop fold(keys->key::string, data->a):: undef { + unwrap = function(data::unknType, keys::unknType):: unknType; interpretation(force){ + loop fold(keys->key::string, data->a):: unknType { a[key] } } start = function::num; entry{ result = unwrap( { a = { b = { c = "core" } } - }, ["a", "b", "c"])::undef. + }, ["a", "b", "c"])::unknType. result == "core" } )Code" ); man->analyse(); 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){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( 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->analyse(); 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){ XreateManager* man = XreateManager::prepare( 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){ XreateManager* man = XreateManager::prepare( 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, versions::VERSION_NONE}, exprLoop.blocks.front()}; InterpretationData dataCallEv = Attachments::get(symbCallEv); ASSERT_EQ(CMPL_ONLY, dataCallEv.resolution); ASSERT_EQ(CALL_INTERPRET_PARTIAL, dataCallEv.op); } TEST(Interpretation, Compilation_PartialIntr_2){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( 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" ); man->analyse(); if (!man->isPassRegistered(PassId::InterpretationPass)){ InterpretationPass* pass = new InterpretationPass(man); pass->run(); } int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(21, result); } TEST(Interpretation, PartialIntr_3){ xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( R"Code( Command= type variant {INC, DEC, DOUBLE}. evaluate= function(argument:: num, code:: Command; interpretation(force)):: num { switch variant(code)::int case (INC) {argument + 1} case (DEC) {argument - 1} case (DOUBLE) {argument * 2} } main = function::int; entry { commands= [INC(), DOUBLE(), DEC()]:: [Command]; interpretation(force). loop fold(commands->comm::Command, 10->operand):: int{ evaluate(operand, comm) } } )Code" ); man->analyse(); if (!man->isPassRegistered(PassId::InterpretationPass)){ InterpretationPass* pass = new InterpretationPass(man); pass->run(); } int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(21, result); } TEST(Interpretation, SwitchVariant){ xreate::XreateManager* man = xreate::XreateManager::prepare( R"Code( OneArgument = type{x::int}. TWoArgument = type {x::int, y::int}. Command= type variant { ADD::TwoArguments, DEC:: OneArgument, DOUBLE::OneArgument }. main = function::int; entry{ program = ADD({x=2, y=3})::Command; interpretation(force). switch variant(program)::int case (ADD) {program["x"]+program["y"]} case (DEC) {1} case (DOUBLE) {2} } )Code" ); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(5, result); } TEST(Interpretation, SwitchVariantAlias){ xreate::XreateManager* man = xreate::XreateManager::prepare( R"Code( OneArgument = type{x::int}. TWoArgument = type {x::int, y::int}. Command= type variant { ADD::TwoArguments, DEC:: OneArgument, DOUBLE::OneArgument }. main = function::int; entry{ program = [ADD({x=2, y=3}), DEC({x=8})]::[Command]; interpretation(force). switch variant(program[0]->program::Command)::int case (ADD) {program["x"]+program["y"]} case (DEC) {1} case (DOUBLE) {2} } )Code" ); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(5, result); } TEST(Interpretation, Multiindex1){ std::string script2= R"Code( - extract = function(program::undef)::int; interpretation(force){ + extract = function(program::unknType)::int; interpretation(force){ program["arguments"][1] } main = function::int; entry { - x = {arguments = [10, 9, 8, 7]}:: undef; interpretation(force). + x = {arguments = [10, 9, 8, 7]}:: unknType; interpretation(force). extract(x) } )Code"; std::unique_ptr man(XreateManager::prepare(std::move(script2))); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(9, result); } TEST(InterpretationExamples, Regexp1){ FILE* input = fopen("scripts/dsl/regexp.xreate","r"); assert(input != nullptr); std::unique_ptr man(XreateManager::prepare(input)); int (*main)() = (int (*)())man->run(); int result = main(); ASSERT_EQ(4, result); } //TOTEST call indirect recursion(w/o tags) //TASk implement and test Loop Inf (fix acc types in coco grammar) diff --git a/scripts/dsl/regexp.xreate b/scripts/dsl/regexp.xreate index 608d708..3651cc1 100644 --- a/scripts/dsl/regexp.xreate +++ b/scripts/dsl/regexp.xreate @@ -1,76 +1,76 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ */ interface(extern-c){ xml2 = library:: pkgconfig("libxml-2.0"). include { xml2 = ["string.h"] }. } Matcher = type variant {Sequence, ZeroOrMore, Text}. matchText = function(text::string, matcher::string, posStart::i64):: i64 { textLength = strlen(text):: i64. matcherLength = strlen(matcher):: i64. if(textLength >= posStart + matcherLength):: i64{ if(strncmp(text + posStart, matcher, matcherLength) == 0):: i64 { matcherLength } else {-1:: i64} } else {-2:: i64} } -matchSequence = function(text::string, pattern::undef; interpretation(force), posStart::i64):: i64; interpretation(suppress){ +matchSequence = function(text::string, pattern::undefType; interpretation(force), posStart::i64):: i64; interpretation(suppress){ textLength = length(text):: i64. - loop fold(pattern-> matcher:: undef, posStart->pos):: i64{ + loop fold(pattern-> matcher:: undefType, posStart->pos):: i64{ recognizedSymbols = match(text, matcher, pos):: i64. if (recognizedSymbols > 0):: i64{ pos+recognizedSymbols } else { pos:: i64; break } } } -matchZeroOrMore= function(text::string, matcher::undef; interpretation(force), posStart::i64):: i64; interpretation(suppress){ +matchZeroOrMore= function(text::string, matcher::undefType; interpretation(force), posStart::i64):: i64; interpretation(suppress){ textLength = length(text):: i64. loop fold inf(posStart->pos):: i64{ recognizedSymbols = match(text, matcher, pos):: i64. if (recognizedSymbols > 0):: i64{ pos+recognizedSymbols } else { pos:: i64; break } } } -match = function(text::string, pattern::undef; interpretation(force), posStart::i64)::i64; interpretation(suppress){ +match = function(text::string, pattern::undefType; interpretation(force), posStart::i64)::i64; interpretation(suppress){ key= pattern[0]::Matcher. switch variant(key) :: int case (Sequence) {matchSequence(text, pattern[1], posStart)} case (ZeroOrMore) {matchZeroOrMore(text, pattern[1], posStart)} case (Text) {matchText(text, pattern[1], posStart)} } main = function:: i64; entry { patternAB = [Sequence(), [[ZeroOrMore(), [Text(), "a"]], - [Text(), "b"]]] :: undef; interpretation(force). + [Text(), "b"]]] :: undefType; interpretation(force). // matchers = ["The ", "only ", "way "] :: [string]; interpretation(force). match("aaab", patternAB, 0):: i64 }