diff --git a/.gitignore b/.gitignore index 672d37a..d6ce9c6 100644 --- a/.gitignore +++ b/.gitignore @@ -1,81 +1,82 @@ # Compiled Object files *.slo *.lo *.o *.obj # Compiled Dynamic libraries *.so *.so.* *.dylib *.dll # Compiled Static libraries *.lai *.la *.a *.lib # Executables *.exe *.out *.app *.class # Mobile Tools for Java (J2ME) .mtj.tmp/ # Package Files # *.jar *.war *.ear # virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml hs_err_pid* # Qt-es /.qmake.cache /.qmake.stash *.pro.user *.pro.user.* *.moc moc_*.cpp qrc_*.cpp ui_*.h Makefile* *-build-* # QtCreator *.autosave coco/*.old coco/*~ *~ cpp/build-*/* cpp/xreate-debug/* cpp/xreate-release/* cpp/.idea CMakeLists.txt.user cmake_install.cmake project/* nb*.xml .* target/* /tools/phabricator/xreate-frontend/nbproject/private/ documentation/trash4/ trash/ CMakeFiles/ gen-cpp/ generated-cpp/ gen-php/ generated-js/ books/ build/ coco/Parser.* coco/Scanner.* tools/phabricator/administration/ +scripts/**/tmp-* diff --git a/config/default.json b/config/default.json index a1dae44..9770109 100644 --- a/config/default.json +++ b/config/default.json @@ -1,71 +1,71 @@ { "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": "compilation", + "template": "communication", "templates": { "default": "*-Adhoc.*:Compilation.full_IFStatementWithVariantType:Types.full_VariantType_Switch1", "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": "Interpretation.SwitchVariantAlias-Association.*", "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/dfagraph.cpp b/cpp/src/analysis/dfagraph.cpp index f5c01e5..f64be93 100644 --- a/cpp/src/analysis/dfagraph.cpp +++ b/cpp/src/analysis/dfagraph.cpp @@ -1,227 +1,239 @@ /* 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: DFAGraph.h * Author: pgess * */ /** * \file dfagraph.h * \brief Data Flow Analysis(DFA) graph data * */ #include "analysis/dfagraph.h" #include "analysis/aux.h" #include using namespace std; namespace xreate {namespace dfa { struct VisitorNodeHash : public boost::static_visitor { std::size_t operator()(const xreate::SymbolPacked& node) const noexcept { return 2* (node.identifier + 2 * node.scope + 3 * std::abs(node.version)) + 1; } std::size_t operator()(const xreate::dfa::SymbolAnonymous& node) const noexcept { return 2 * node.id; } }; }} std::size_t hash::operator()(xreate::dfa::SymbolNode const& s) const noexcept { return boost::apply_visitor(xreate::dfa::VisitorNodeHash(), s); } namespace xreate { namespace dfa { bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2){ return s1.id == s2.id && s1.flagIsUsed == s2.flagIsUsed; } class VisitorFormatSymbol: public boost::static_visitor { public: boost::format operator()(const SymbolPacked& node) const { //boost::format formatSymbNamed("s(%1%, %2%, %3%)"); boost::format formatSymbNamed("s%1%%2%"); return formatSymbNamed % node.identifier /*% node.version*/ % node.scope ; } boost::format operator()(const SymbolAnonymous& node) const { //boost::format formatSymbAnonymous("anon(%1%)"); boost::format formatSymbAnonymous("a%1%"); return formatSymbAnonymous % node.id; } }; void DFACallInstance::print(std::ostringstream& output) const{ + boost::format formatArgs; boost::format formatInstance("dfa_callinstance(%1%, %2%)."); - boost::format formatArgs("dfa_callargs(%1%, %2%, %3%)."); boost::format formatRet("dfa_callret(%1%, %2%)."); + switch (type) { + case WEAK: + formatArgs = boost::format("weak(dfa_callargs(%1%, %2%, %3%))."); + break; + + case STRONG: + formatArgs = boost::format("weak(dfa_callargs(%1%, %2%, %3%)).\ndfa_callargs(%1%, %2%, %3%)."); + break; + } + output << formatInstance % id % fnName << endl; for(std::pair rec: args) { SymbolNode argFormal(rec.first); output << formatArgs % id % boost::apply_visitor(VisitorFormatSymbol(), argFormal) % boost::apply_visitor(VisitorFormatSymbol(), rec.second) << endl; } output << formatRet % id % boost::apply_visitor(VisitorFormatSymbol(), retActual) << endl; } void DFAGraph::addDependency(const SymbolNode& node, const SymbolNode& subnode){ __dependencies.emplace(node, subnode); + + if (boost::get(&node)){ + __usedSymbols.insert(node); + } + + if (boost::get(&subnode)){ + __usedSymbols.insert(node); + } } void DFAGraph::printDependencies(std::ostringstream& output) const{ for(const SymbolNode& root: __roots){ printDependency(output, root, root); } } void DFAGraph::printDependency(std::ostringstream& output, const SymbolNode& nodeCurrent, const SymbolNode& nodeDependent) const { auto range = __dependencies.equal_range(nodeCurrent); for (auto it = range.first; it != range.second; ++it){ - if (const SymbolAnonymous* symbAnon = boost::get(&it->second)){ - if (!__usedAnonymousSymbols.count(symbAnon->id)){ + if (boost::get(&it->second)){ + if (!__usedSymbols.count(it->second)){ printDependency(output, it->second, nodeDependent); continue; } } boost::format formatDependency("dfa_depends(%1%, %2%)."); output << formatDependency % boost::apply_visitor(VisitorFormatSymbol(), nodeDependent) % boost::apply_visitor(VisitorFormatSymbol(), it->second) << endl; printDependency(output, it->second, it->second); } } void DFAGraph::printInplaceAnnotations(SymbolNode node, const Expression& expression) { // write down in-place expression tags: boost::format formatBind("bind(%1%, %2%)."); - if (expression.tags.size()) - if (boost::get(&node)){ - markSymbolsAsUsed(vector({node})); - } + if (expression.tags.size()) __usedSymbols.insert(node); - for (const pair& tag : expression.tags) { + for (const pair& tag : expression.tags){ for (const string& tagPart: xreate::analysis::compile(tag.second)) { __output << formatBind % boost::apply_visitor(VisitorFormatSymbol(), node) % tagPart << endl; } } } void -DFAGraph::printAlias(const SymbolNode& symbolFormal, const SymbolNode& symbActual){ +DFAGraph::printAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual){ + __usedSymbols.insert(symbFormal); __usedSymbols.insert(symbActual); + boost::format formatAlias("dfa_alias(%1%, %2%)."); __output << formatAlias - % boost::apply_visitor(VisitorFormatSymbol(), symbolFormal) + % boost::apply_visitor(VisitorFormatSymbol(), symbFormal) + % boost::apply_visitor(VisitorFormatSymbol(), symbActual) + << endl; +} + +void +DFAGraph::printWeakAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual){ + __usedSymbols.insert(symbFormal); __usedSymbols.insert(symbActual); + + boost::format formatAlias("weak(dfa_alias(%1%, %2%))."); + __output << formatAlias + % boost::apply_visitor(VisitorFormatSymbol(), symbFormal) % boost::apply_visitor(VisitorFormatSymbol(), symbActual) << endl; } void DFAGraph::printFunctionRet(ManagedFnPtr function, const SymbolNode& symbolRet){ boost::format formatRet("dfa_fnret(%1%, %2%)."); + __usedSymbols.insert(symbolRet); __output << formatRet % function->getName() % boost::apply_visitor(VisitorFormatSymbol(), symbolRet) << endl; __roots.insert(symbolRet); } void DFAGraph::addCallInstance(DFACallInstance&& instance){ + __usedSymbols.insert(instance.retActual); + for(const auto arg: instance.args){ + __usedSymbols.insert(SymbolNode(arg.first)); + __usedSymbols.insert(arg.second); + } + __callInstances.push_back(std::move(instance)); } void DFAGraph::print(std::ostringstream& output) const{ output << endl << "%\t\tStatic analysis: DFA" << endl; //Dependencies printDependencies(output); //Add generated report output << __output.str() << endl; //Call instances for(const DFACallInstance& instance: __callInstances){ instance.print(output); } output << endl; } -void -DFAGraph::markSymbolsAsUsed(const std::vector& usedNodes){ - for (const SymbolNode& node: usedNodes){ - if (const SymbolAnonymous* symbol = boost::get(&node)){ - __usedAnonymousSymbols.insert(symbol->id); - } - } -} - -bool -DFAGraph::isSymbolUsed(const SymbolNode& node) const{ - if (const SymbolAnonymous* symbol = boost::get(&node)){ - if (!__usedAnonymousSymbols.count(symbol->id)) {return false;} - } - - return true; -} - void DFAGraph::printSymbols(ClaspLayer* clasp){ - std::unordered_set symbols; - - for (auto entry: __dependencies){ - if (isSymbolUsed(entry.first)) {symbols.insert(entry.first);} - if (isSymbolUsed(entry.second)) {symbols.insert(entry.second);} - } + boost::format formatHint("shint(%1%, \"%2%\")."); - for (const SymbolNode& node : symbols) { - __output << "v(" << boost::apply_visitor(VisitorFormatSymbol(), node) << ")."; + for (const SymbolNode& node : __usedSymbols) { + __output << "v(" << boost::apply_visitor(VisitorFormatSymbol(), node) << "). "; if (const SymbolPacked* symbol = boost::get(&node)){ - __output << " %" << clasp->getHintForPackedSymbol(*symbol); + __output << formatHint % boost::apply_visitor(VisitorFormatSymbol(), node) % clasp->getHintForPackedSymbol(*symbol); } __output << endl; } } }} //end of namespace xreate::dfa diff --git a/cpp/src/analysis/dfagraph.h b/cpp/src/analysis/dfagraph.h index ff297e5..44ff5f3 100644 --- a/cpp/src/analysis/dfagraph.h +++ b/cpp/src/analysis/dfagraph.h @@ -1,74 +1,79 @@ /* 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: dfa.h * Author: pgess * * Created on June 27, 2016, 1:50 PM */ #ifndef DFA_H #define DFA_H #include "clasplayer.h" #include -namespace xreate {namespace dfa { +namespace xreate { namespace dfa { + struct SymbolAnonymous { unsigned int id; bool flagIsUsed = false; }; - - bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2); + bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2); typedef boost::variant SymbolNode; }} -namespace std{ +namespace std { + template<> - struct hash{ + struct hash { std::size_t operator()(xreate::dfa::SymbolNode const& s) const noexcept; }; } namespace xreate {namespace dfa { -class DFACallInstance{ + +enum DFACallInstanceType { + STRONG, WEAK +}; + +class DFACallInstance { public: unsigned int id; std::string fnName; std::vector> args; SymbolNode retActual; - + DFACallInstanceType type; + void print(std::ostringstream& output) const; }; /** \brief Holds DFA Analysis report produced by DFAPass */ -class DFAGraph: public IAnalysisReport{ +class DFAGraph : public IAnalysisReport { public: - // DFAGraph(ClaspLayer* engine): __clasp(engine){} + // DFAGraph(ClaspLayer* engine): __clasp(engine){} virtual void print(std::ostringstream& output) const override; void addCallInstance(DFACallInstance && instance); void addDependency(const SymbolNode& node, const SymbolNode& subnodeBlock); void printInplaceAnnotations(SymbolNode node, const Expression& expression); - void printAlias(const SymbolNode& symbolFormal, const SymbolNode& symbActual); + void printAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual); + void printWeakAlias(const SymbolNode& symbFormal, const SymbolNode& symbActual); void printFunctionRet(ManagedFnPtr function, const SymbolNode& symbolRet); void printDependencies(std::ostringstream& output) const; - void markSymbolsAsUsed(const std::vector& usedNodes); void printSymbols(ClaspLayer* clasp); - + private: mutable std::ostringstream __output; std::list __callInstances; std::unordered_multimap __dependencies; - std::unordered_set __usedAnonymousSymbols; + std::unordered_set __usedSymbols; std::unordered_set __roots; - - + void printDependency(std::ostringstream& output, const SymbolNode& nodeCurrent, const SymbolNode& nodeDependent) const; - bool isSymbolUsed(const SymbolNode& node) const; }; }} // end of namespace xreate::dfa #endif /* DFA_H */ diff --git a/cpp/src/pass/dfapass.cpp b/cpp/src/pass/dfapass.cpp index 030a4ad..8958eb0 100644 --- a/cpp/src/pass/dfapass.cpp +++ b/cpp/src/pass/dfapass.cpp @@ -1,204 +1,242 @@ /* 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/. * * Author: pgess * * dfapass.cpp */ /** * \file dfapass.h * \brief Data Flow Analysis(DFA) */ //DEBT DFA represent VersionaPass in declarative form using applyDependencies // applyDependencies(expression, context, cache, decl); //DEBT DFA prepare static annotations and represent InterpretationPass in declarative form // applyStaticAnnotations(expression, context, cache, decl); //DEBT DFA Eliminate dfa schemes #include "pass/dfapass.h" #include "xreatemanager.h" #include "clasplayer.h" #include #include using namespace std; -namespace xreate { namespace dfa { +namespace xreate {namespace dfa { DFAPass::DFAPass(PassManager* manager) - : AbstractPass(manager) - , graph{new DFAGraph()} - , clasp(manager->clasp) -{} +: AbstractPass(manager) +, graph{new DFAGraph()} + +, clasp(manager->clasp) { } void -DFAPass::processCallInstance(const Expression& expr, PassContext context, const SymbolNode& result){ - const string &nameCalleeFunction = expr.getValueString(); +DFAPass::processCallInstance(const Expression& expr, PassContext context, const SymbolNode& result) { + const string &nameCalleeFunction=expr.getValueString(); //TODO implement processFnCall/Uncertain - list variantsCalleeFunction = man->root->getFunctionSpecializations(nameCalleeFunction); + list variantsCalleeFunction=man->root->getFunctionSpecializations(nameCalleeFunction); vector operands; operands.reserve(expr.getOperands().size()); - for (const Expression& arg: expr.getOperands()){ + for(const Expression& arg : expr.getOperands()) { operands.push_back(process(arg, context)); } - graph->markSymbolsAsUsed(operands); - graph->markSymbolsAsUsed(std::vector{result}); //Set calling relations: - for (ManagedFnPtr function: variantsCalleeFunction){ - CodeScope *scopeRemote = function->getEntryScope(); + DFACallInstanceType type=variantsCalleeFunction.size()>1?WEAK:STRONG; + for(ManagedFnPtr function : variantsCalleeFunction) { + CodeScope *scopeRemote=function->getEntryScope(); DFACallInstance callInstance; - callInstance.id = expr.id; - callInstance.fnName = function->getName(); + callInstance.id=expr.id; + callInstance.fnName=function->getName(); + callInstance.type=type; - std::vector::const_iterator nodeActual = operands.begin(); - for (const std::string &identFormal: scopeRemote->__bindings){ + std::vector::const_iterator nodeActual=operands.begin(); + for(const std::string &identFormal : scopeRemote->__bindings) { const ScopedSymbol symbolFormal{scopeRemote->__identifiers.at(identFormal), versions::VERSION_NONE}; - SymbolPacked symbolFormalPacked = clasp->pack(Symbol{symbolFormal, scopeRemote}); + SymbolPacked symbolFormalPacked=clasp->pack(Symbol{symbolFormal, scopeRemote}, nameCalleeFunction+":"+identFormal); callInstance.args.push_back(std::make_pair(symbolFormalPacked, *nodeActual)); - graph->addDependency(symbolFormalPacked, *nodeActual); ++nodeActual; } - callInstance.retActual = result; - SymbolNode retFormal = SymbolNode(clasp->pack(Symbol{ScopedSymbol::RetSymbol, scopeRemote})); - graph->addDependency(result, retFormal); + callInstance.retActual=result; + SymbolNode retFormal=SymbolNode(clasp->pack(Symbol{ScopedSymbol::RetSymbol, scopeRemote}, nameCalleeFunction+":[ret]")); graph->addCallInstance(std::move(callInstance)); } - - } void -DFAPass::processDependencies(const SymbolNode& node, const Expression& expression, PassContext context, ProcessingCache& cache){ +DFAPass::processDependencies(const SymbolNode& node, const Expression& expression, PassContext context, ProcessingCache& cache) { cache.operands.reserve(expression.getOperands().size()); - for (const Expression &op: expression.getOperands()) { - const SymbolNode& subnodeOperand = process(op, context); + for(const Expression &op : expression.getOperands()) { + const SymbolNode& subnodeOperand=process(op, context); cache.operands.push_back(subnodeOperand); graph->addDependency(node, subnodeOperand); } cache.blocks.reserve(expression.blocks.size()); - for (CodeScope* block : expression.blocks) { - const SymbolNode& subnodeBlock = process(block, context); + for(CodeScope* block : expression.blocks) { + const SymbolNode& subnodeBlock=process(block, context); cache.blocks.push_back(subnodeBlock); graph->addDependency(node, subnodeBlock); } } SymbolNode -DFAPass::process(const Expression& expression, PassContext context, const std::string& varDecl) -{ +DFAPass::process(const Expression& expression, PassContext context, const std::string& varDecl) { SymbolNode result; - if (Attachments::exists(expression)) - { - Symbol varSymbol = Attachments::get(expression); - result = clasp->pack(varSymbol, varDecl); + if(Attachments::exists(expression)){ + Symbol varSymbol=Attachments::get(expression); + result=clasp->pack(varSymbol, varDecl); - } else if (expression.__state == Expression::IDENT && expression.tags.size() == 0) { - Symbol varSymbol = Attachments::get(expression); - result = clasp->pack(varSymbol, expression.getValueString()); + } else if(expression.__state==Expression::IDENT&&expression.tags.size()==0){ + Symbol varSymbol=Attachments::get(expression); + result=clasp->pack(varSymbol, expression.getValueString()); } else { - result = SymbolAnonymous{expression.id}; + result=SymbolAnonymous{expression.id}; } graph->printInplaceAnnotations(result, expression); - switch(expression.__state){ - case Expression::COMPOUND: { - switch (expression.op) { - case Operator::CALL: - processCallInstance(expression, context, result); - break; - - default: - ProcessingCache cache; - processDependencies(result, expression, context, cache); - break; - } + switch(expression.__state) { + case Expression::COMPOUND: + { + switch(expression.op) { + case Operator::CALL: + { + processCallInstance(expression, context, result); break; } - case Expression::IDENT: { - SymbolNode symbIdent = AbstractPass::process(expression, context, varDecl); + case Operator::IF: + { + const SymbolNode& scopeA=process(expression.blocks.front(), context, "ifTrue" + std::to_string(expression.id)); + const SymbolNode& scopeB=process(expression.blocks.back(), context, "ifFalse" + std::to_string(expression.id)); + const SymbolNode& condition=process(expression.operands.at(0), context); + + graph->addDependency(result, scopeA); + graph->addDependency(result, scopeB); + graph->addDependency(result, condition); + graph->printWeakAlias(result, scopeA); + graph->printWeakAlias(result, scopeB); + break; + } + + case Operator::SWITCH: + case Operator::SWITCH_VARIANT: + { + for(CodeScope* block : expression.blocks) { + const SymbolNode& subnodeBlock=process(block, context, "case"+to_string(block->getBody().id)); - if (!(result == symbIdent)) { - graph->addDependency(result, symbIdent); - graph->printAlias(result, symbIdent); + graph->addDependency(result, subnodeBlock); + graph->printWeakAlias(result, subnodeBlock); } + const SymbolNode& condition=process(expression.operands.at(0), context); + graph->addDependency(result, condition); break; } - case Expression::NUMBER: - case Expression::STRING: { + default: + { + ProcessingCache cache; + processDependencies(result, expression, context, cache); break; } + } + break; + } - case Expression::INVALID: - case Expression::BINDING: { - assert(false); - break; + case Expression::IDENT: + { + SymbolNode symbIdent=AbstractPass::process(expression, context, varDecl); + + if(!(result==symbIdent)){ + graph->addDependency(result, symbIdent); + graph->printAlias(result, symbIdent); } + + break; + } + + case Expression::NUMBER: + case Expression::STRING: + { + break; + } + + case Expression::INVALID: + case Expression::BINDING: + { + assert(false); + break; + } } return result; } SymbolNode -DFAPass::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ - for(const std::string& binding: scope->__bindings){ +DFAPass::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl) { + if (!hintBlockDecl.empty()) { + Symbol symbRet{ScopedSymbol::RetSymbol, scope}; + clasp->pack(symbRet, hintBlockDecl + ":[ret]"); + } + + for(const std::string& binding : scope->__bindings) { Symbol bindingSymbol{scope->getSymbol(binding), scope}; - SymbolPacked bindingPacked = clasp->pack(bindingSymbol, binding); + SymbolPacked bindingPacked=clasp->pack(bindingSymbol, binding); getSymbolCache().setCachedValue(bindingSymbol, SymbolNode(bindingPacked)); } return AbstractPass::process(scope, context, hintBlockDecl); } SymbolNode -DFAPass::process(ManagedFnPtr function){ - SymbolNode result = AbstractPass::process(function); +DFAPass::process(ManagedFnPtr function) { + clasp->pack(Symbol{ScopedSymbol::RetSymbol, function->getEntryScope()}, function->getName()+to_string(function.id())+":[ret]"); + SymbolNode result=AbstractPass::process(function); graph->printFunctionRet(function, result); return result; } void -DFAPass::finish(){ +DFAPass::finish() { clasp->registerReport(graph); //Declare symbols: graph->printSymbols(clasp); AbstractPass::finish(); } } //end of namespace dfa template<> -dfa::SymbolNode defaultValue(){ +dfa::SymbolNode +defaultValue() { assert(false); } } //xreate namespace /** * \class xreate::dfa::DFAPass * \details Provides DFA, important analysis for reasoning. Iterates over AST and stores collected data in DFAGraph */ diff --git a/cpp/tests/communication.cpp b/cpp/tests/communication.cpp index 0b89e90..652b88b 100644 --- a/cpp/tests/communication.cpp +++ b/cpp/tests/communication.cpp @@ -1,51 +1,73 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * communication.cpp * * Author: pgess * Created on October 14, 2017, 5:24 PM */ #include "xreatemanager.h" #include "gtest/gtest.h" using namespace xreate; -TEST(Communication, ast1){ +TEST(Communication, ast_Basic1){ FILE* script = fopen("scripts/effects-communication/example1-wr.xreate", "r"); std::unique_ptr program(XreateManager::prepare(script)); ASSERT_TRUE(true); fclose(script); } -TEST(Communication, Analysis1){ +TEST(Communication, analysis_Basic1){ FILE* script = fopen("scripts/effects-communication/example1-wr.xreate", "r"); std::unique_ptr program(details::tier1::XreateManager::prepare(script)); fclose(script); program->analyse(); ASSERT_TRUE(true); } -TEST(Communication, FullOnlyDirect1){ +TEST(Communication, full_Basic1){ FILE* script = fopen("scripts/effects-communication/example1-wr.xreate", "r"); std::unique_ptr program(XreateManager::prepare(script)); fclose(script); int (*programEntry)() = (int (*)())program->run(); int result = programEntry(); ASSERT_EQ(1, result); } -TEST(Communication, FullDirectAndGuarded1){ +TEST(Communication, full_Basic2){ FILE* script = fopen("scripts/effects-communication/example2-wr.xreate", "r"); std::unique_ptr program(XreateManager::prepare(script)); fclose(script); int (*programEntry)() = (int (*)())program->run(); int result = programEntry(); ASSERT_EQ(1, result); +} + +TEST(Communication, analysis_Weak1){ + FILE* script = fopen("scripts/effects-communication/example3-wrwr.xreate", "r"); + + std::unique_ptr program(details::tier1::XreateManager::prepare(script)); + fclose(script); + + program->analyse(); + ASSERT_TRUE(true); +} + +TEST(Communication, full_Weak1){ + FILE* script = fopen("scripts/effects-communication/example3-wrwr.xreate", "r"); + + std::unique_ptr program(XreateManager::prepare(script)); + fclose(script); + + int (*programEntry)(int) = (int (*)(int))program->run(); + + ASSERT_EQ(1, programEntry(1)); + ASSERT_EQ(-1, programEntry(0)); } \ No newline at end of file diff --git a/scripts/dfa/polymorphism.lp b/scripts/dfa/polymorphism.lp index 9c11fe3..a3bbcff 100644 --- a/scripts/dfa/polymorphism.lp +++ b/scripts/dfa/polymorphism.lp @@ -1,15 +1,15 @@ %INPUT % bind(Symb, callguard(..)) - binded Ann %OUTPUT % dfa_callguard(..) - ready for processing dfa_callguard(Instance, Guard):- bind(ArgActual, callguard(Guard)); - dfa_callargs(Instance,_, ArgActual); + weak(dfa_callargs(Instance, _, ArgActual)); dfa_callret(Instance, SymbRet); bind(SymbRet, dfa_polym(arg)). dfa_callguard(Instance, Guard):- bind(SymbRet, callguard(Guard)); dfa_callret(Instance, SymbRet); bind(SymbRet, dfa_polym(ret)). diff --git a/scripts/dfa/propagation.lp b/scripts/dfa/propagation.lp index ac8e81e..8fbba25 100644 --- a/scripts/dfa/propagation.lp +++ b/scripts/dfa/propagation.lp @@ -1,20 +1,32 @@ %Propagates symbol bindings registered by dfa_propagation over dfa_uppy edges % % INPUT: % dfa_propagation(X) - register propagated Ann % bind(Symb, X) - initial symbol % -% CALCULATED: -% dfa_uppy - UPdate or coPY +% OUTPUT: +% w/dfa_uppy - UPdate or coPY bind(SymbA, DfaAnn):- bind(SymbB, DfaAnn); dfa_propagation(DfaAnn); - 1{dfa_uppy(SymbA, SymbB); dfa_uppy(SymbB,SymbA)}; + 1{weak(dfa_uppy(SymbA, SymbB)); weak(dfa_uppy(SymbB,SymbA))}; v(SymbA); v(SymbB). dfa_uppy(X, Y):- bind(X, dfa_uppy(Pseudo)); bind(Y, dfa_pseudo(Pseudo)). dfa_uppy(X, Y):- dfa_alias(X, Y). dfa_uppy(ArgFormal, ArgActual):- dfa_callargs(_,ArgFormal, ArgActual). dfa_uppy(RetActual, RetFormal):- + dfa_callret(CallId, RetActual); dfa_callinstance(CallId, FnName); + dfa_fnret(FnName, RetFormal); + #count{1: dfa_fnret(FnName, RetFormal)}1. + + +% WEAK ANALYSIS +%============================================================= +weak(dfa_uppy(X, Y)):- dfa_uppy(X, Y). +weak(dfa_uppy(X, Y)):- weak(dfa_alias(X, Y)). + +weak(dfa_uppy(ArgFormal, ArgActual)):- weak(dfa_callargs(_,ArgFormal, ArgActual)). +weak(dfa_uppy(RetActual, RetFormal)):- dfa_callret(CallId, RetActual); dfa_callinstance(CallId, FnName); dfa_fnret(FnName, RetFormal). diff --git a/scripts/effects-communication/communication.lp b/scripts/effects-communication/communication.lp index 481a564..ec62f55 100644 --- a/scripts/effects-communication/communication.lp +++ b/scripts/effects-communication/communication.lp @@ -1,77 +1,121 @@ %INPUT: % const horizon - Max Depth of communication analysis % comm_order(Alias)), bind(X, comm_alias(Alias) - to apply additional order constraints % dfa_uppy from dfa-propagation % INIT %=========================================================== comm_bind(end, end). comm_bind(begin, begin). comm_bind(X, Op):- bind(X, commop(Op)). % ORDER %============================================================ comm_path(X2, X1) :- bind(X2, comm_order(Alias)); bind(X1, comm_alias(Alias)). % INHERITS %============================================================ comm_path(X, Y) :- dfa_uppy(X, Y). -comm_path(end, X) :- v(X); #sum{1: comm_path(Smth, X), v(Smth)}0. -comm_path(X, begin):- v(X); #sum{1: comm_path(X, Smth), v(Smth)}0. +comm_path(end, X) :- v(X); #sum{1: weak(comm_path(Smth, X)), v(Smth)}0. +comm_path(X, begin):- v(X); #sum{1: weak(comm_path(X, Smth)), v(Smth)}0. % SCAN %============================================================ %SOURCE scan(X, source(X), length(0)) :- comm_bind(X, write). scan(Z, source(X), length(Length + 1)) :- comm_path(Z, Y); scan(Y, source(X), length(Length)); Length < horizon; not comm_bind(Z, _). scan(Z, source(X), report(Op)) :- comm_path(Z, Y); scan(Y, source(X), length(Length)); Length < horizon; comm_bind(Z, Op). %SINK scan(X, sink(X), length(0)) :- comm_bind(X, read). scan(Z, sink(X), length(Length + 1)) :- comm_path(Y, Z); scan(Y, sink(X), length(Length)); Length < horizon; not comm_bind(Z, _). scan(Z, sink(X), report(Op)) :- comm_path(Y, Z); scan(Y, sink(X), length(Length)); Length < horizon; comm_bind(Z, Op). + -% ISSUES +% REPORTS %============================================================== -comm_spot_lost_end(Source) :- scan(_, source(Source), report(end)). -comm_spot_lost(Source, Spot) :- scan(Spot, source(Source), report(write)). -comm_spot_outofreach(X, Spot) :- scan(Spot, source(X), length(horizon)). -comm_spot_outofreach(X, Spot) :- scan(Spot, sink(X), length(horizon)). +comm_reports_type(rprtLostEnd; rprtLost; rprtCorruptNull; rprtDup; rprtOutOfReach). + +comm_reports(rprtLostEnd , Source, undef) :- scan(_, source(Source), report(end)). +comm_reports(rprtLost , Source, Spot) :- scan(Spot, source(Source), report(write)). +comm_reports(rprtCorruptNull, Sink, undef) :- scan(_, sink(Sink), report(begin)). +comm_reports(rprtDup , Sink, Spot) :- scan(Spot, sink(Sink), report(read)). + +comm_halt(Source):- comm_reports(rprtLostEnd, Source, undef). +comm_halt(Source):- comm_reports(rprtLost, Source, _). +comm_halt(Sink):- comm_reports(rprtCorruptNull, Sink, undef). +comm_halt(Sink):- comm_reports(rprtDup, Sink, Spot). + -comm_spot_corrupt_null(Sink) :- scan(_, sink(Sink), report(begin_)). -comm_spot_dup(Sink, Spot) :- scan(Spot, sink(Sink), report(read)). +% WEAK REPORTS +%============================================================= +weak(comm_reports(rprtLostEnd , Source)) :- weak(scan(_, source(Source), report(end))). +weak(comm_reports(rprtLost , Source, Spot)) :- weak(scan(Spot, source(Source), report(write))). +weak(comm_reports(rprtCorruptNull, Sink)) :- weak(scan(_, sink(Sink), report(begin))). +weak(comm_reports(rprtDup, Sink, Spot)) :- weak(scan(Spot, sink(Sink), report(read))). -comm_spot(Source):-comm_spot_lost_end(Source). -comm_spot(Source):-comm_spot_lost(Source, Spot). -comm_spot(X):-comm_spot_outofreach(X, Spot). -comm_spot(Sink):-comm_spot_corrupt_null(Sink). -comm_spot(Sink):-comm_spot_dup(Sink, Spot). +comm_reports(rprtOutOfReach, X, Spot) :- weak(scan(Spot, source(X), length(horizon))). +comm_reports(rprtOutOfReach, X, Spot) :- weak(scan(Spot, sink(X), length(horizon))). -% IMPLEMENTATION +% SOLUTIONS %============================================================= -comm_impl(Source, commDirect):- comm_bind(Source, write); not comm_spot(Source). +comm_impl(Source, commGuarded):- comm_bind(Source, write); + not comm_halt(Source); + 1{ weak(comm_reports(Type, Source, _)): comm_reports_type(Type) }. + +comm_impl(Source, commDirect):- comm_bind(Source, write); + not comm_halt(Source); + not comm_impl(Source, commGuarded). + bind(Source, callguard(commDirect)):- comm_impl(Source, commDirect). +bind(Source, callguard(commGuarded)):- comm_impl(Source, commGuarded). + + +% WEAK ANALYSIS +%============================================================= +weak(comm_path(X, Y)) :- weak(dfa_uppy(X, Y)). +weak(scan(Arg1, Arg2, Arg3)) :- scan(Arg1, Arg2, Arg3). + +weak(scan(Z, sink(X), length(Length + 1))):- + weak(comm_path(Y, Z)); + weak(scan(Y, sink(X), length(Length))); Length < horizon; + not comm_bind(Z, _). + +weak(scan(Z, sink(X), report(Op))):- + weak(comm_path(Y, Z)); + weak(scan(Y, sink(X), length(Length))); Length < horizon; + comm_bind(Z, Op). + + +weak(scan(Z, source(X), length(Length + 1))) :- + weak(comm_path(Z, Y)); + weak(scan(Y, source(X), length(Length))); Length < horizon; + not comm_bind(Z, _). +weak(scan(Z, source(X), report(Op))) :- + weak(comm_path(Z, Y)); + weak(scan(Y, source(X), length(Length))); Length < horizon; + comm_bind(Z, Op). diff --git a/scripts/effects-communication/config.lp b/scripts/effects-communication/config.lp index c6867d9..0f59d5a 100644 --- a/scripts/effects-communication/config.lp +++ b/scripts/effects-communication/config.lp @@ -1,2 +1,2 @@ #const horizon = 10. -dfa_propagation(callguard(commDirect)). +dfa_propagation(X) :- bind(_, X); X = callguard(_). diff --git a/scripts/effects-communication/example1-wr.xreate b/scripts/effects-communication/example1-wr.xreate index d5d734a..738486c 100644 --- a/scripts/effects-communication/example1-wr.xreate +++ b/scripts/effects-communication/example1-wr.xreate @@ -1,38 +1,38 @@ //Only Direct implementatino defined -import raw ("scripts/effects-communication/communication.lp"). -import raw ("scripts/effects-communication/dfa/propagation.lp"). +import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). +import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { init=function::CommDirect{ {value = 0} } read= function(vault1:: CommDirect):: int{ (vault1::CommDirect; commop(read))["value"] } write= function(vault2:: CommDirect, valueNew:: int)::CommDirect{ (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) } } main=function::int; entry { - x1 = init():: Comm; dfa_polym(ret). - x2 = write(x1, 1)::Comm; dfa_polym(arg). - a = read(x2):: int; dfa_polym(arg). + x1 = init()::Comm; dfa_polym(ret). + x2 = write(x1, 1)::Comm; dfa_polym(arg). + a = read(x2)::int; dfa_polym(arg). a } diff --git a/scripts/effects-communication/example2-wr.xreate b/scripts/effects-communication/example2-wr.xreate index 95aba14..fd4b342 100644 --- a/scripts/effects-communication/example2-wr.xreate +++ b/scripts/effects-communication/example2-wr.xreate @@ -1,76 +1,76 @@ //Direct and Guarded implementation defined import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { init=function::CommDirect{ {value = 0} } read= function(vault1:: CommDirect):: int{ (vault1::CommDirect; commop(read))["value"] } write= function(vault2:: CommDirect, valueNew:: int)::CommDirect{ (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) } } errorRead = function:: int { -1 } errorWrite = function:: CommGuarded{ { value = -1, state = Invalid() } } guard:: commGuarded{ init=function::CommGuarded{ { value = 0, state = Invalid() } } read=function(vault3:: CommGuarded):: int { switch variant (vault3::CommGuarded;commop(read)):: int case (Invalid) { errorRead() } case (Outdated) { errorRead() } case (Valid) { vault3["value"] } } write=function(vault4:: CommGuarded, valueNew:: int)::CommGuarded{ switch variant (vault4)::int case (Invalid) { {value = valueNew, state = Valid()} } case (Outdated) { {value = valueNew, state = Valid()} } case (Valid) { errorWrite() } } } main=function::int; entry { x1 = init():: Comm; dfa_polym(ret). x2 = write(x1, 1)::Comm; dfa_polym(arg). - a = read(x2):: int; dfa_polym(arg). + a = read(x2):: int; dfa_polym(arg). a } diff --git a/scripts/effects-communication/example2-wr.xreate b/scripts/effects-communication/example3-wrwr.xreate similarity index 60% copy from scripts/effects-communication/example2-wr.xreate copy to scripts/effects-communication/example3-wrwr.xreate index 95aba14..29796c7 100644 --- a/scripts/effects-communication/example2-wr.xreate +++ b/scripts/effects-communication/example3-wrwr.xreate @@ -1,76 +1,86 @@ //Direct and Guarded implementation defined import raw ("scripts/effects-communication/communication.lp"). import raw ("scripts/dfa/propagation.lp"). import raw ("scripts/dfa/polymorphism.lp"). import raw ("scripts/effects-communication/config.lp"). CommGuard = type variant{Invalid, Valid, Outdated}. CommDirect = type { value:: int }. CommGuarded = type { value:: int, state:: CommGuard }. guard:: commDirect { init=function::CommDirect{ {value = 0} } read= function(vault1:: CommDirect):: int{ (vault1::CommDirect; commop(read))["value"] } - write= function(vault2:: CommDirect, valueNew:: int)::CommDirect{ - (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew}:: int; commop(write); dfa_uppy(vault2) + write= function(vault2:: CommDirect, valueNew1:: int)::CommDirect{ + (vault2::CommDirect;dfa_pseudo(vault2)) + {value = valueNew1}:: int; commop(write); dfa_uppy(vault2) } } errorRead = function:: int { -1 } errorWrite = function:: CommGuarded{ { value = -1, state = Invalid() } } guard:: commGuarded{ init=function::CommGuarded{ { value = 0, state = Invalid() } } read=function(vault3:: CommGuarded):: int { - switch variant (vault3::CommGuarded;commop(read)):: int + switch variant (vault3["state"]->whatever::CommGuard;commop(read)):: int case (Invalid) { errorRead() } case (Outdated) { errorRead() } case (Valid) { vault3["value"] } } - write=function(vault4:: CommGuarded, valueNew:: int)::CommGuarded{ - switch variant (vault4)::int + write=function(vault4:: CommGuarded, valueNew2:: int)::CommGuarded{ + switch variant (vault4["state"]->whatever::CommGuard;commop(write); dfa_pseudo(vault4))::int case (Invalid) { - {value = valueNew, state = Valid()} + {value = valueNew2, state = Valid()}:: CommGuarded; dfa_uppy(vault4) } case (Outdated) { - {value = valueNew, state = Valid()} + {value = valueNew2, state = Valid()}:: CommGuarded; dfa_uppy(vault4) } - case (Valid) { errorWrite() } + case (Valid) { errorWrite():: CommGuarded; dfa_uppy(vault4) } } } -main=function::int; entry { +main=function(cmd:: num)::int; entry { x1 = init():: Comm; dfa_polym(ret). x2 = write(x1, 1)::Comm; dfa_polym(arg). - a = read(x2):: int; dfa_polym(arg). - a + + x3 = if (cmd > 0)::Comm { + y = read(x2):: int; dfa_polym(arg). + y + + } else { + z = write(x2, 2)::Comm; dfa_polym(arg). + a = read(z):: int; dfa_polym(arg). + a + }. + + x3 }