diff --git a/.gitignore b/.gitignore index 59de723..c7edac1 100644 --- a/.gitignore +++ b/.gitignore @@ -1,84 +1,83 @@ # 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/*~ *~ - +# XREATE 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-* +**/tmp-* cpp/tests/vendorsAPI/ - diff --git a/config/default.json b/config/default.json index 90aa4c0..e2db4c2 100644 --- a/config/default.json +++ b/config/default.json @@ -1,74 +1,74 @@ { "containers": { "id": { "implementations": "containers_impl", "linkedlist": "linkedlist" }, "impl": { "solid": "solid", "onthefly": "on_the_fly" } }, "logging": { "id": "logging" }, "function-entry": "entry", "transcend": { "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": "documentation", + "template": "troubleshooting", "templates": { - "troubleshooting":"Transcend.Doc_*", - "documentation":"Modules.Doc_*:Interpretation.Doc_*:AST.Doc_*:Loop.Doc_*:LateReasoning.Doc_*:Latex.Doc_*:Polymorphs.Doc_*:Transcend.Doc_*", + "troubleshooting":"ASTCorrespondence.Doc_*:Virtualization.Doc_*:Exploitation.Doc_*", + "documentation":"Modules.Doc_*:Interpretation.Doc_*:AST.Doc_*:Loop.Doc_*:LateReasoning.Doc_*:Latex.Doc_*:Polymorphs.Doc_*:Transcend.Doc_*:ASTCorrespondence.Doc_*:Virtualization.Doc_*:Exploitation.Doc_*", "default": "*", "ast": "AST.*", "effects": "Effects.*", "basic": "Attachments.*", "compilation": "Compilation.*", "communication": "Communication.*", "cfa": "CFA.*", "containers": "Containers.*", "dfa": "DFA.*", "diagnostic": "Diagnostic.*", "dsl": "Association.*:Interpretation.*", "exploitation": "Exploitation.*", "ExpressionSerializer": "ExpressionSerializer.*", "externc": "InterfaceExternC.*", "loops": "Loop.*", "latereasoning": "LateReasoning.*", "latex": "Latex.*", "modules": "Modules.*", "polymorphs": "Polymorphs.*", "intrinsic-query": "Types.SlaveTypes*:Association.TypedQuery*", "types": "Types.*", "virtualization": "Virtualization.*", "vendorsAPI/clang": "ClangAPI.*", "vendorsAPI/xml2": "libxml2.*" } } } diff --git a/cpp/src/CMakeLists.txt b/cpp/src/CMakeLists.txt index 93ad47b..cb91525 100644 --- a/cpp/src/CMakeLists.txt +++ b/cpp/src/CMakeLists.txt @@ -1,236 +1,238 @@ 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(STATUS "LLVM DEFS: " ${LLVM_DEFINITIONS}) execute_process( COMMAND llvm-config --libs OUTPUT_VARIABLE LLVM_LIBS OUTPUT_STRIP_TRAILING_WHITESPACE) message(STATUS "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}/../grammar/) set(COCO_SOURCE_FILES_MAIN ${COCO_GRAMMAR_PATH}/main/Parser.cpp ${COCO_GRAMMAR_PATH}/main/Scanner.cpp ) set(COCO_SOURCE_FILES_MODULES ${COCO_GRAMMAR_PATH}/modules/Parser.cpp ${COCO_GRAMMAR_PATH}/modules/Scanner.cpp ) set(COCO_SOURCE_FILES ${COCO_SOURCE_FILES_MODULES} ${COCO_SOURCE_FILES_MAIN}) INCLUDE_DIRECTORIES(${COCO_GRAMMAR_PATH}) add_custom_command(OUTPUT ${COCO_SOURCE_FILES_MAIN} COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar main ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/xreate.ATG ) add_custom_command(OUTPUT ${COCO_SOURCE_FILES_MODULES} COMMAND ${COCO_GRAMMAR_PATH}/gen-grammar modules ${COCO_EXECUTABLE} ${COCO_FRAMES_PATH} WORKING_DIRECTORY ${COCO_GRAMMAR_PATH} MAIN_DEPENDENCY ${COCO_GRAMMAR_PATH}/modules.ATG ) message(STATUS "COCO GRAMMAR BUILD STATUS:" ${COCO_OUTPUT}) # XREATE #====================== set(SOURCE_FILES + analysis/temporalseqgraph.cpp + pass/cfatemporalseqpass.cpp + analysis/cfagraph.cpp + pass/cfapass.cpp modules.cpp - analysis/DominatorsAnalysisProvider.cpp compilation/interpretation-instructions.cpp ExternLayer.cpp analysis/cfagraph.cpp compilation/latereasoning.cpp analysis/interpretation.cpp query/latex.cpp query/polymorph.cpp compilation/polymorph.cpp aux/latereasoning.cpp compilation/latex.cpp analysis/typeinference.cpp xreatemanager.cpp transcendlayer.cpp analysis/dfagraph.cpp llvmlayer.cpp pass/compilepass.cpp analysis/utils.cpp pass/dfapass.cpp compilation/targetinterpretation.cpp pass/interpretationpass.cpp ast.cpp aux/xreatemanager-decorators.cpp compilation/operators.cpp compilation/transformations.cpp compilation/transformersaturation.cpp pass/versionspass.cpp attachments.cpp compilation/containers.cpp compilation/advancedinstructions.cpp utils.cpp pass/abstractpass.cpp - pass/cfapass.cpp contextrule.cpp query/containers.cpp aux/serialization/expressionserializer.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 ${COCO_SOURCE_FILES} ${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 boost_system boost_filesystem ) #${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/analysis/DominatorsAnalysisProvider.cpp b/cpp/src/analysis/DominatorsAnalysisProvider.cpp deleted file mode 100644 index 57b24f0..0000000 --- a/cpp/src/analysis/DominatorsAnalysisProvider.cpp +++ /dev/null @@ -1,284 +0,0 @@ -/* 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: DominatorsAnalysisProvider.cpp - * Author: pgess - * - * Created on May 13, 2016, 11:39 AM - */ - -/** - * \file DominatorsAnalysisProvider.h - * \brief Dominators Tree analysis - */ - -#include "analysis/cfagraph.h" -#include "analysis/DominatorsAnalysisProvider.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; - CFAGraphAdapter* parent; - std::list nodesFrom; - std::list nodesTo; - - CFAGraphAdapter* getParent(){ return parent; } - void printAsOperand(llvm::raw_ostream&, bool) {} - ScopeNode(ScopePacked scope, CFAGraphAdapter* parentAdapter): - id(scope), parent(parentAdapter) {} -}; - -} -} //end of namespace xreate::dominators - -namespace llvm { -using namespace xreate::dominators; - -template<> -struct GraphTraits { - typedef ScopeNode* NodeRef; - typedef std::list::iterator ChildIteratorType; - - static ChildIteratorType - child_begin(ScopeNode* node) { - return node->nodesTo.begin(); - } - - static ChildIteratorType - child_end(ScopeNode* node) { - return node->nodesTo.end(); - } -}; - -template<> -struct GraphTraits> -{ - typedef ScopeNode* NodeRef; - typedef std::list::iterator ChildIteratorType; - - static ChildIteratorType - child_begin(ScopeNode* node) { - return node->nodesFrom.begin(); - } - - static ChildIteratorType - child_end(ScopeNode* node) { - return node->nodesFrom.end(); - } -}; - -template<> -struct 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 ScopeNode* - getEntryNode(CFAGraphAdapter* F) { - return F->nodeRoot; - } - - static unsigned int - size(CFAGraphAdapter* graph) { - return graph->nodes.size(); - } - - static nodes_iterator - child_begin(ScopeNode* node) { - return node->nodesTo.begin(); - } - - static nodes_iterator - child_end(ScopeNode* node) { - return node->nodesTo.end(); - } -}; -} - -namespace xreate { -namespace dominators { - -class DominatorTree : public llvm::DominatorTreeBase { -friend class DominatorsAnalysisProvider; -public: - DominatorTree() : llvm::DominatorTreeBase() {} - - void - run(CFAGraphAdapter& program) { - recalculate(program); - updateDFSNumbers(); - - //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< { -friend class DominatorsAnalysisProvider; -public: - PostDominatorTree() : llvm::DominatorTreeBase() {} - - void - run(CFAGraphAdapter& program) { - recalculate(program); - updateDFSNumbers(); - //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<id < b->id;}; - auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), &elemNew, fnComp); - - if(posLowerBound==nodes.end()|| (*posLowerBound)->id > scope){ - ScopeNode* elemNewP = new ScopeNode(elemNew); - *elemNewP = elemNew; - return *nodes.insert(posLowerBound, elemNewP); - } - - return *posLowerBound; -} - -CFAGraphAdapter* -CFAGraphAdapter::build(const cfa::CFAGraph* graph) { - return build(graph->__dependencyRelations); -} - -CFAGraphAdapter* -CFAGraphAdapter::build(const std::multimap& dataScopesOrder){ - CFAGraphAdapter* tree=new CFAGraphAdapter(); - - enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT}; - std::unordered_map nodeMarks; - for (const auto& edge: dataScopesOrder){ - - ScopeNode* nodeTo = tree->registerScope(edge.first); - ScopeNode* nodeFrom = tree->registerScope(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->registerScope(SCOPE_ABSTRACT_GLOBAL); - for(auto rootLocal: nodeRoots){ - ScopeNode* nodeLocalRoot = tree->registerScope(rootLocal); - nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot); - nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot); - } - - tree->nodeRoot = nodeGlobalRoot; - - } else if (nodeRoots.size()==1){ - tree->nodeRoot = tree->registerScope(nodeRoots.front()); - - } else { - ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL); - tree->nodeRoot = nodeGlobalRoot; - } - - return tree; -} - -void -DominatorsAnalysisProvider::run(CFAGraphAdapter* program) { - treeForwardDominators.reset(new DominatorTree()); - treePostDominators.reset(new PostDominatorTree()); - - treeForwardDominators->run(*program); - treePostDominators->run(*program); -} - -void -DominatorsAnalysisProvider::print(std::ostringstream& output) const { - treeForwardDominators->print(output, "cfa_forwdom"); - treePostDominators->print(output, "cfa_postdom"); -} - -const DominatorsAnalysisProvider::Dominators& -DominatorsAnalysisProvider::getForwardDominators() const { - return treeForwardDominators->dominators; -} - -const DominatorsAnalysisProvider::Dominators& -DominatorsAnalysisProvider::getPostDominators() const { - return treePostDominators->dominators; -} - -DominatorsAnalysisProvider::DominatorsAnalysisProvider() {} -DominatorsAnalysisProvider::~DominatorsAnalysisProvider() { } - - -}} //end of namespace xreate::dominators diff --git a/cpp/src/analysis/DominatorsAnalysisProvider.h b/cpp/src/analysis/DominatorsAnalysisProvider.h deleted file mode 100644 index a7124cc..0000000 --- a/cpp/src/analysis/DominatorsAnalysisProvider.h +++ /dev/null @@ -1,56 +0,0 @@ -/* 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: DominatorsAnalysisProvider.h - * Author: pgess - * - * Created on May 13, 2016, 11:39 AM - */ - -#ifndef DominatorsAnalysisProvider_H -#define DominatorsAnalysisProvider_H - -#include "transcendlayer.h" -#include - -namespace xreate{namespace dominators{ - -class DominatorTree; -class PostDominatorTree; -class ScopeNode; - -struct CFAGraphAdapter { - std::list nodes; - ScopeNode* nodeRoot; - - ScopeNode* registerScope(ScopePacked scope); - static CFAGraphAdapter* build(const cfa::CFAGraph* graph); - static CFAGraphAdapter* build(const std::multimap& dataScopesOrder); - CFAGraphAdapter() { } -}; - -/** \brief Dominators Analysis report */ -class DominatorsAnalysisProvider: public IAnalysisReport { -public: - typedef std::pair DominatedRange; - typedef std::map Dominators; - - DominatorsAnalysisProvider(); - virtual ~DominatorsAnalysisProvider(); - - void run(CFAGraphAdapter* program); - void print(std::ostringstream& output) const override; - - const Dominators& getForwardDominators() const; - const Dominators& getPostDominators() const; - -private: - boost::shared_ptr treeForwardDominators; - boost::shared_ptr treePostDominators; -}; - -}} //end of namespace xreate::dominators - -#endif /* DominatorsAnalysisProvider_H */ - diff --git a/cpp/src/analysis/cfagraph.cpp b/cpp/src/analysis/cfagraph.cpp index df29784..ef0c679 100644 --- a/cpp/src/analysis/cfagraph.cpp +++ b/cpp/src/analysis/cfagraph.cpp @@ -1,220 +1,191 @@ /* 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: CFAGraph.cpp * Author: pgess * * Created on June 27, 2016, 2:09 PM */ /** * \file cfagraph.h * \brief Control Flow Analysis(CFA) graph data - * */ #include "analysis/cfagraph.h" #include "analysis/utils.h" using namespace xreate::cfa; using namespace std; void CFAGraph::print(std::ostringstream& output) const { - const std::string& atomBinding = Config::get("transcend.bindings.function"); - const std::string& atomBindingScope = Config::get("transcend.bindings.scope"); - - output << endl << "%\t\tStatic analysis: CFA" << endl; - output << __outputPrecomputed.str(); - - //show function tags - int counterTags = 0; - std::ostringstream bufFunctionNames; - boost::format formatFunction("function(%1%)."); - boost::format formatBind(atomBinding + "(%1%, %2%)."); - for (auto function : this->__nodesFunction.left) { - const auto tags = this->__functionTags.equal_range(function.first); - if (tags.first == tags.second) { - //no tags - bufFunctionNames << "; " << function.second ; - continue; - } - - output << formatFunction % (function.second) << std::endl; - for (const auto& tag_ : boost::make_iterator_range(tags)) { - const Expression& tag = tag_.second; - - list tagRaw = xreate::analysis::compile(tag); - assert(tagRaw.size() == 1); - - output << formatBind - % (function.second) - % (tagRaw.front()) - << endl; - ++counterTags; - } - } - - if (bufFunctionNames.tellp()) { - output << formatFunction % (bufFunctionNames.str().substr(2)) << std::endl; - } - - if (counterTags == 0) { - output << "%no function tags at all" << endl; - } - - //declare scopes - boost::format formatScope("scope(0..%1%)."); - output << formatScope % (__transcend->getScopesCount() - 1) << std::endl; - - //show context rules: - for (auto rule : this->__contextRules) { - output << ContextRule(rule.second).compile(rule.first) << std::endl; - }; - - //show scope tags: - counterTags = 0; - boost::format formatScopeBind(atomBindingScope + "(%1%, %2%, strong)."); - for (auto entry : this->__scopeTags) { - ScopePacked scopeId = entry.first; - const Expression& tag = entry.second; - list tagRaw = xreate::analysis::compile(tag); - assert(tagRaw.size() == 1); - - output << formatScopeBind % scopeId % (tagRaw.front()) << endl; - ++counterTags; - } - - if (counterTags == 0) { - output << "%scope tags: no tags at all" << endl; - } - - //parent connections - //TOTEST CFG parent function - boost::format formatFunctionParent("cfa_parent(%1%, function(%2%))."); - for (const auto &relation : this->__parentFunctionRelations) { - const string& function = this->__nodesFunction.left.at(relation.right); - - output << formatFunctionParent % relation.left % function << endl; - } - - //TOTEST CFG parent scope - boost::format formatScopeParent("cfa_parent(%1%, scope(%2%))."); - for (const auto &relation : this->__parentScopeRelations) { - output << formatScopeParent % relation.first % relation.second << endl; - } - - //call connections - boost::format formatCall("cfa_call(%1%, %2%)."); - - for (const auto &relation : this->__callRelations) { - const ScopePacked scopeFrom = relation.left; - const string& functionTo = this->__nodesFunction.left.at(relation.right); - - output << formatCall % (scopeFrom) % (functionTo) << endl; - } - - //function specializations description - boost::format formatSpecializations("cfa_function_specializations(%1%, %2%)."); - const list& functions = __transcend->ast->getAllFunctions(); - for (auto f : functions) { - if (f->guard.isValid()) { - list guardRaw = xreate::analysis::compile(f->guard); - assert(guardRaw.size() == 1); - output << formatSpecializations % (f->getName()) % (guardRaw.front()) << endl; - } - } - - //Dependencies - boost::format formatDependencies("cfa_scope_depends(%1%, %2%)."); - for(const auto relation : __dependencyRelations) { - output << formatDependencies % relation.first % relation.second << endl; - } - std::multimap __dependencyRelations; + const std::string& atomBinding = Config::get("transcend.bindings.function"); + const std::string& atomBindingScope = Config::get("transcend.bindings.scope"); + + output << endl << "%\t\tStatic analysis: CFA" << endl; + output << __outputPrecomputed.str(); + + //show function tags + int counterTags = 0; + std::ostringstream bufFunctionNames; + boost::format formatFunction("function(%1%)."); + boost::format formatBind(atomBinding + "(%1%, %2%)."); + for (auto function : this->__fnNodes.left) { + const auto tags = this->__fnTags.equal_range(function.first); + if (tags.first == tags.second) { + //no tags + bufFunctionNames << "; " << function.second ; + continue; + } + + output << formatFunction % (function.second) << std::endl; + for (const auto& tag_ : boost::make_iterator_range(tags)) { + const Expression& tag = tag_.second; + + list tagRaw = xreate::analysis::compile(tag); + assert(tagRaw.size() == 1); + + output << formatBind + % (function.second) + % (tagRaw.front()) + << endl; + ++counterTags; + } + } + + if (bufFunctionNames.tellp()) { + output << formatFunction % (bufFunctionNames.str().substr(2)) << std::endl; + } + + if (counterTags == 0) { + output << "%no function tags at all" << endl; + } + + //declare scopes + boost::format formatScope("scope(0..%1%)."); + output << formatScope % (__transcend->getScopesCount() - 1) << std::endl; + + //show context rules: + for (auto rule : this->__contextRules) { + output << ContextRule(rule.second).compile(rule.first) << std::endl; + }; + + //show scope tags: + counterTags = 0; + boost::format formatScopeBind(atomBindingScope + "(%1%, %2%, strong)."); + for (auto entry : this->__scopeTags) { + ScopePacked scopeId = entry.first; + const Expression& tag = entry.second; + list tagRaw = xreate::analysis::compile(tag); + assert(tagRaw.size() == 1); + + output << formatScopeBind % scopeId % (tagRaw.front()) << endl; + ++counterTags; + } + + if (counterTags == 0) { + output << "%scope tags: no tags at all" << endl; + } + + //parent connections + //TOTEST CFG parent function + boost::format formatFunctionParent("cfa_parent(%1%, function(%2%))."); + for (const auto &relation : this->__parentFnRelation) { + const string& function = this->__fnNodes.left.at(relation.right); + + output << formatFunctionParent % relation.left % function << endl; + } + + //TOTEST CFG parent scope + boost::format formatScopeParent("cfa_parent(%1%, scope(%2%))."); + for (const auto &relation : this->__parentScopeRelation) { + output << formatScopeParent % relation.first % relation.second << endl; + } + + //call connections + boost::format formatCall("cfa_call(%1%, %2%)."); + + for (const auto &relation : this->__callRelations) { + const ScopePacked scopeFrom = relation.left; + const string& functionTo = this->__fnNodes.left.at(relation.right); + + output << formatCall % (scopeFrom) % (functionTo) << endl; + } + + //function specializations description + boost::format formatSpecializations("cfa_function_specializations(%1%, %2%)."); + const list& functions = __transcend->ast->getAllFunctions(); + for (auto f : functions) { + if (f->guard.isValid()) { + list guardRaw = xreate::analysis::compile(f->guard); + assert(guardRaw.size() == 1); + output << formatSpecializations % (f->getName()) % (guardRaw.front()) << endl; + } + } } void -CFAGraph::addFunctionAnnotations(const std::string& function, const std::map& tags) { - unsigned int fid = registerNodeFunction(function); +CFAGraph::addFunctionAnnotations(const std::string& fn, const std::map& tags) { + unsigned int fid = registerNodeFunction(fn); - for (auto& tag : tags) { - __functionTags.emplace(fid, tag.second); - } + for (auto& tag : tags) { + __fnTags.emplace(fid, tag.second); + } } void CFAGraph::addScopeAnnotations(const ScopePacked& scope, const std::vector& tags) { - for (Expression tag : tags) { - __scopeTags.emplace(scope, tag); - } + for (Expression tag : tags) { + __scopeTags.emplace(scope, tag); + } } void CFAGraph::addContextRules(const ScopePacked& scope, const std::vector& rules) { - for (Expression rule : rules) { - __contextRules.emplace(scope, rule); - } + for (Expression rule : rules) { + __contextRules.emplace(scope, rule); + } } void -CFAGraph::addCallConnection(const ScopePacked& scopeFrom, const std::string& functionTo) { - unsigned int idFuncTo = registerNodeFunction(functionTo); +CFAGraph::addCallConnection(const ScopePacked& callerScope, const std::string& calleeFn) { + unsigned int idFuncTo = registerNodeFunction(calleeFn); - __callRelations.insert(CALL_RELATIONS::value_type(scopeFrom, idFuncTo)); + __callRelations.insert(CALL_RELATIONS::value_type(callerScope, idFuncTo)); } void -CFAGraph::addParentConnection(const ScopePacked& scope, const std::string& functionParent) { - __parentFunctionRelations.insert(PARENT_FUNCTION_RELATIONS::value_type(scope, registerNodeFunction(functionParent))); +CFAGraph::addParentConnection(const ScopePacked& scopeEntry, const std::string& fnParent) { + __parentFnRelation.insert(PARENT_FUNCTION_RELATIONS::value_type(scopeEntry, registerNodeFunction(fnParent))); } void -CFAGraph::addParentConnection(const ScopePacked& scope, const ScopePacked& scopeParent) { - __parentScopeRelations.emplace(scope, scopeParent); +CFAGraph::addParentConnection(const ScopePacked& scopeChild, const ScopePacked& scopeParent) { + __parentScopeRelation.emplace(scopeChild, scopeParent); } unsigned int CFAGraph::registerNodeFunction(const std::string& fname) { - auto pos = __nodesFunction.left.insert(make_pair(__nodesFunction.size(), fname)); - - return pos.first->first; -} - -void -CFAGraph::addDependency(const ScopePacked& scope, const ScopePacked& scopeDependency) { - __dependencyRelations.emplace(scope, scopeDependency); -} - -bool -CFAGraph::isDependent(const ScopePacked& scope) const { - return __dependencyRelations.count(scope) > 0; -} - -void -CFAGraph::transmitDependencies(const ScopePacked& scopeTo, const ScopePacked& scopeFrom) { - auto range = __dependencyRelations.equal_range(scopeFrom); + auto pos = __fnNodes.left.insert(make_pair(__fnNodes.size(), fname)); - std::list dependencies; - for (auto pairI = range.first; pairI != range.second; ++pairI) { - dependencies.push_back(pairI->second); - } - - for(auto dep : dependencies) { - __dependencyRelations.emplace(scopeTo, dep); - } + return pos.first->first; } void CFAGraph::addScope(CodeScope* scope) { - boost::format formatScopeBinding("ast_scope_binding(%1%, %2%, \"%3%\")."); - - ScopePacked scopeId = __transcend->pack(scope); - for (int id=0, size = scope->__bindings.size(); id < size; ++id) { - __outputPrecomputed << formatScopeBinding - % scopeId - % id - % scope->__bindings.at(id) - << endl; - } + boost::format formatScopeBinding("ast_scope_binding(%1%, %2%, \"%3%\")."); + + ScopePacked scopeId = __transcend->pack(scope); + __scopesCount = max(scopeId + 1, __scopesCount); + + for (int id = 0, size = scope->__bindings.size(); id < size; ++id) { + __outputPrecomputed << formatScopeBinding + % scopeId + % id + % scope->__bindings.at(id) + << endl; + } } + diff --git a/cpp/src/analysis/cfagraph.h b/cpp/src/analysis/cfagraph.h index a4e1dc4..543731a 100644 --- a/cpp/src/analysis/cfagraph.h +++ b/cpp/src/analysis/cfagraph.h @@ -1,64 +1,66 @@ /* 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: CFAGraph.h * Author: pgess * * Created on June 27, 2016, 2:09 PM */ #ifndef CFAGRAPH_H #define CFAGRAPH_H #include "transcendlayer.h" -namespace xreate {namespace cfa { - - /** \brief Represents CFA analysis data produced by CFAPass */ - class CFAGraph: public IAnalysisReport { - public: - typedef boost::bimap> PARENT_FUNCTION_RELATIONS; - PARENT_FUNCTION_RELATIONS __parentFunctionRelations; - std::map __parentScopeRelations; - std::multimap __dependencyRelations; - - typedef boost::bimap< - boost::bimaps::multiset_of, - boost::bimaps::multiset_of, - boost::bimaps::set_of_relation<> - > CALL_RELATIONS; - - CALL_RELATIONS __callRelations; - - boost::bimap __nodesFunction; - std::multimap __functionTags; - std::multimap __scopeTags; - std::multimap __contextRules; - - void print(std::ostringstream& output) const override; - CFAGraph(TranscendLayer* engine): __transcend(engine){} - - void addFunctionAnnotations(const std::string& function, const std::map& tags); - void addScopeAnnotations(const ScopePacked& scope, const std::vector&tags); - void addContextRules(const ScopePacked& scope, const std::vector&rules); - void addCallConnection(const ScopePacked& scopeFrom, const std::string& functionTo); - void addParentConnection(const ScopePacked& scope, const std::string& functionParent); - void addParentConnection(const ScopePacked& scope, const ScopePacked& scopeParent); - void addDependency(const ScopePacked& scope, const ScopePacked& scopeDependency); - bool isDependent(const ScopePacked& scope) const; - void transmitDependencies(const ScopePacked& scopeTo, const ScopePacked& scopeFrom); - void addScope(CodeScope* scope); - - private: - TranscendLayer* __transcend; - std::ostringstream __outputPrecomputed; - - unsigned int registerNodeFunction(const std::string& fname); - - }; - -}} //end of namespace xreate::cfa +namespace xreate{ +namespace cfa{ + +/** \brief Represents CFA analysis data produced by CFAPass */ +class CFAGraph: public IAnalysisReport{ + friend class TemporalSeqGraph; +public: + typedef boost::bimap> PARENT_FUNCTION_RELATIONS; + PARENT_FUNCTION_RELATIONS __parentFnRelation; + std::map __parentScopeRelation; + + typedef boost::bimap< + boost::bimaps::multiset_of, + boost::bimaps::multiset_of, + boost::bimaps::set_of_relation<> + > CALL_RELATIONS; + + CALL_RELATIONS __callRelations; + + boost::bimap __fnNodes; + std::multimap __fnTags; + std::multimap __scopeTags; + std::multimap __contextRules; + unsigned int __scopesCount = 0; + + void print(std::ostringstream &output) const override; + + CFAGraph(TranscendLayer* engine): __transcend(engine){ } + + void addFunctionAnnotations(const std::string &fn, const std::map &tags); + void addScopeAnnotations(const ScopePacked &scope, const std::vector &tags); + void addContextRules(const ScopePacked &scope, const std::vector &rules); + void addCallConnection(const ScopePacked &callerScope, const std::string &calleeFn); + void addParentConnection(const ScopePacked &scopeEntry, const std::string &fnParent); + void addParentConnection(const ScopePacked &scopeChild, const ScopePacked &scopeParent); + void addScope(CodeScope* scope); + +private: + TranscendLayer* __transcend; + std::ostringstream __outputPrecomputed; + + unsigned int registerNodeFunction(const std::string &fname); +}; + + + +} +} //end of namespace xreate::cfa #endif /* CFAGRAPH_H */ diff --git a/cpp/src/analysis/temporalseqgraph.cpp b/cpp/src/analysis/temporalseqgraph.cpp new file mode 100644 index 0000000..47a09d7 --- /dev/null +++ b/cpp/src/analysis/temporalseqgraph.cpp @@ -0,0 +1,219 @@ +/* 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: temporalseqgraph.cpp + * Author: pgess + * + * Created on February 4, 2019, 4:51 PM + */ + +#include "temporalseqgraph.h" + +using namespace xreate::cfa; +using namespace std; + +namespace std { + bool operator<(const xreate::cfa::TemporalNode& x, const xreate::cfa::TemporalNode& y) { + if(x.scope != y.scope) return x.scope < y.scope; + return x.mark < y.mark; + } +}; + +TemporalSeqGraph::TemporalSeqGraph(TranscendLayer* transcend) +: __transcend(transcend) { } + +void +TemporalSeqGraph::addSubScopes(const CodeScope* scopeIn, const std::list& scopesChild) { + auto socket = addSocket(scopeIn, TemporalOperator::AND); + + for(auto scopeChild : scopesChild) { + TemporalNode nodeChild = TemporalNode{__transcend->pack(scopeChild), TemporalOperator::SCOPE}; + connect(socket.first, nodeChild); + connect(nodeChild, socket.second); + } +} + +void +TemporalSeqGraph::addBranchScopes(const CodeScope* scopeIn, const std::list& scopesChild) { + auto socket = addSocket(scopeIn, TemporalOperator::AND); + TemporalNode toNode{__idNextVacant++, TemporalOperator::OR}; + connect(toNode, socket.second); + + for(auto scopeChild : scopesChild) { + TemporalNode nodeChild = TemporalNode{__transcend->pack(scopeChild), TemporalOperator::SCOPE}; + connect(socket.first, nodeChild); + connect(nodeChild, toNode); + } +} + +std::pair +TemporalSeqGraph::addSocket(const CodeScope* scopeIn, TemporalOperator mark) { + TemporalNode nodeFrom; + TemporalNode nodeIn = TemporalNode{__transcend->pack(scopeIn), TemporalOperator::SCOPE}; + + auto rangeInward = graph.right.equal_range(nodeIn); + size_t sizeInward = std::distance(rangeInward.first, rangeInward.second); + + if (sizeInward == 1) { + //if scope has single inward connection + nodeFrom = rangeInward.first->second; + + } else if (sizeInward > 1) { + //if scope has multy inward con: + nodeFrom = insertBefore(nodeIn, EMPTY); + + } else { + //no inward connections: + nodeFrom = insertBefore(nodeIn, EMPTY); + } + + TemporalNode nodeTo = insertAfter(nodeIn, mark); + return {nodeFrom, nodeTo}; +} + +Socket +TemporalSeqGraph::getFnSocket(ManagedFnPtr calleeFn) { + if(__cacheFnSockets.count(calleeFn)) { + return __cacheFnSockets.at(calleeFn); + } + + TemporalNode fromNode{__idNextVacant++, TemporalOperator::EMPTY}; + TemporalNode toNode{__idNextVacant++, TemporalOperator::EMPTY}; + Socket fnSock = make_pair(fromNode, toNode); + __cacheFnSockets.emplace(calleeFn, fnSock); + + return fnSock; +} + +Socket +TemporalSeqGraph::getUncertainFnSocket(const std::string& calleeName, const std::list& candidates) { + if(__cacheUncertainFnSockets.count(calleeName)) { + return __cacheUncertainFnSockets.at(calleeName); + } + + Socket fnSock; + if(candidates.size() == 0) { + //External Function + TemporalNode node{__idNextVacant++, TemporalOperator::EMPTY}; + fnSock = make_pair(node, node); + + } else { + //Multiple specializations + TemporalNode fromNode{__idNextVacant++, TemporalOperator::EMPTY}; + TemporalNode toNode{__idNextVacant++, TemporalOperator::OR}; + fnSock = make_pair(fromNode, toNode); + + for (const ManagedFnPtr& candidate : candidates) { + Socket candidateSock = getFnSocket(candidate); + connect(fromNode, candidateSock.first); + connect(candidateSock.second, toNode); + } + } + __cacheUncertainFnSockets.emplace(calleeName, fnSock); + + return fnSock; +} + +TemporalNode +TemporalSeqGraph::insertBefore(TemporalNode node, TemporalOperator mark) { + TemporalNode nodeNew{__idNextVacant++, mark}; + + auto nodesInRange = graph.right.equal_range(node); + list nodesIn; + for(auto nodeInIt = nodesInRange.first; nodeInIt != nodesInRange.second; ++nodeInIt) { + nodesIn.push_back(nodeInIt->second); + } + + graph.right.erase(node); + for(auto nodeIn : nodesIn) { + connect(nodeIn, nodeNew); + } + + connect(nodeNew, node); + return nodeNew; +} + +TemporalNode +TemporalSeqGraph::insertAfter(TemporalNode node, TemporalOperator mark) { + TemporalNode nodeNew{__idNextVacant++, mark}; + + auto nodesOutRange = graph.left.equal_range(node); + list nodesOut; + for(auto nodeOutIt = nodesOutRange.first; nodeOutIt != nodesOutRange.second; ++nodeOutIt) { + nodesOut.push_back(nodeOutIt->second); + } + + graph.left.erase(node); + for(auto nodeOut : nodesOut) { + connect(nodeNew, nodeOut); + } + + connect(node, nodeNew); + return nodeNew; +} + +void +TemporalSeqGraph::connect(TemporalNode nodeFrom, TemporalNode nodeTo) { + graph.insert(Graph::value_type(nodeFrom, nodeTo)); +} + +void +TemporalSeqGraph::connectGuarded(const Socket& from, const Socket& to) { + unsigned int guard = __guardNextVacant++; + + graphGuarded.emplace(from.first, make_pair(to.first, TemporalGuard{TemporalGuard::IN, guard})); + graphGuarded.emplace(to.second, make_pair(from.second, TemporalGuard{TemporalGuard::OUT, guard})); +} + +void +TemporalSeqGraph::print(std::ostringstream &output) const { + for (auto entry : graph) { + output + << "cfa_seq(" + << entry.left << ", " + << entry.right << ").\n"; + } + + for (auto entry : graphGuarded) { + output + << "cfa_seq_guarded(" + << entry.first << ", " + << entry.second.first << ", " + << (entry.second.second.mark == TemporalGuard::IN ? "in(" : "out(") + << entry.second.second.id << ")).\n"; + } +} + +bool TemporalSeqGraph::isOrdered(const ScopePacked& scopeAfter, const ScopePacked& scopeBefore) const { + set visitedNodes; + return isOrdered(TemporalNode{scopeAfter, TemporalOperator::SCOPE}, + TemporalNode{scopeBefore, TemporalOperator::SCOPE}, + visitedNodes); +} + +bool +TemporalSeqGraph::isOrdered(const TemporalNode& nodeAfter, const TemporalNode& nodeBefore, set& visitedNodes) const { + if (nodeAfter.scope == nodeBefore.scope && nodeAfter.mark == nodeBefore.mark) return true; + if (visitedNodes.count(nodeAfter)) return false; + visitedNodes.insert(nodeAfter); + + auto frontierList = graph.right.equal_range(nodeAfter); + for(auto frontierIt = frontierList.first; frontierIt != frontierList.second; ++frontierIt) { + if(isOrdered(frontierIt->second, nodeBefore, visitedNodes)) return true; + } + return false; +} + +namespace xreate { +namespace cfa { + static string dictNodes[] = {"scope", "empty", "and", "or"}; + + std::ostream& + operator << (std::ostream& output, const TemporalNode& node) { + string op = dictNodes[node.mark]; + output << op << "(" << node.scope << ")"; + + return output; + } +}} \ No newline at end of file diff --git a/cpp/src/analysis/temporalseqgraph.h b/cpp/src/analysis/temporalseqgraph.h new file mode 100644 index 0000000..c3672ec --- /dev/null +++ b/cpp/src/analysis/temporalseqgraph.h @@ -0,0 +1,77 @@ +/* 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: temporalseqgraph.h + * Author: pgess + * + * Created on February 4, 2019, 4:51 PM + */ + +#ifndef TEMPORALSEQGRAPH_H +#define TEMPORALSEQGRAPH_H + +#include "transcendlayer.h" + +namespace xreate{ namespace cfa{ + +enum TemporalOperator {SCOPE, EMPTY, AND, OR}; + +struct TemporalNode{ + ScopePacked scope; + TemporalOperator mark; + + friend std::ostream& operator << (std::ostream& output, const TemporalNode& node); + bool operator==(const TemporalNode& other) const + { return other.scope == scope && other.mark == mark; } +}; + +struct TemporalGuard{ + enum{IN, OUT} mark; + unsigned int id; +}; + +typedef std::pair Socket; + +}} namespace std { + + bool operator<(const xreate::cfa::TemporalNode& x, const xreate::cfa::TemporalNode& y); + +} namespace xreate {namespace cfa { + +class TemporalSeqGraph: public IAnalysisReport{ + typedef boost::bimap< + boost::bimaps::multiset_of, + boost::bimaps::multiset_of> Graph; + +public: + TemporalSeqGraph(TranscendLayer* transcend); + + void addSubScopes(const CodeScope*, const std::list&); + void addBranchScopes(const CodeScope*, const std::list&); + Socket addSocket(const CodeScope*, TemporalOperator mark); + TemporalNode insertBefore(TemporalNode node, TemporalOperator mark); + TemporalNode insertAfter(TemporalNode node, TemporalOperator mark); + void connect(TemporalNode, TemporalNode); + void connectGuarded(const Socket& from, const Socket& to); + Socket getFnSocket(ManagedFnPtr calleeFn); + Socket getUncertainFnSocket(const std::string& calleeName, const std::list& candidates); + + bool isOrdered(const ScopePacked& scopeAfter, const ScopePacked& scopeBefore) const; + bool isOrdered(const TemporalNode& nodeAfter, const TemporalNode& nodeBefore, std::set&) const; + void print(std::ostringstream &output) const override; + +private: + Graph graph; + std::multimap> graphGuarded; + ScopePacked __idNextVacant = 0; + unsigned int __guardNextVacant = 0; + TranscendLayer* __transcend; + std::map __cacheFnSockets; + std::map __cacheUncertainFnSockets; +}; +} +} //end of namespace xreate::cfa + +#endif /* TEMPORALSEQGRAPH_H */ + diff --git a/cpp/src/aux/xreatemanager-decorators.cpp b/cpp/src/aux/xreatemanager-decorators.cpp index 40bf519..07bd480 100644 --- a/cpp/src/aux/xreatemanager-decorators.cpp +++ b/cpp/src/aux/xreatemanager-decorators.cpp @@ -1,74 +1,75 @@ /* 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/. * * xreatemanager-decorators.cpp * * Author: pgess * Created on July 16, 2017, 4:40 PM */ /** * \file xreatemanager-decorators.h * \brief \ref xreate::XreateManager decorators to provide various functionality */ #include "aux/xreatemanager-decorators.h" #include "main/Parser.h" #include "pass/compilepass.h" #include "pass/cfapass.h" #include "pass/dfapass.h" #include "pass/interpretationpass.h" #include "pass/versionspass.h" namespace xreate{ void XreateManagerDecoratorBase::initPasses() { } void XreateManagerDecoratorBase::prepareCode(std::string&& code) { grammar::main::Scanner scanner(reinterpret_cast (code.c_str()), code.size()); grammar::main::Parser parser(&scanner); parser.Parse(); assert(!parser.errors->count && "Parser errors"); PassManager::prepare(parser.root->finalize()); } void XreateManagerDecoratorBase::prepareCode(FILE* code) { grammar::main::Scanner scanner(code); grammar::main::Parser parser(&scanner); parser.Parse(); assert(!parser.errors->count && "Parser errors"); PassManager::prepare(parser.root->finalize()); } void XreateManagerDecoratorBase::analyse() { CompilePass::prepareQueries(transcend); transcend->run(); } void XreateManagerDecoratorFull::initPasses() { cfa::CFAPass* passCFG = new cfa::CFAPass(this); registerPass(new dfa::DFAPass(this), PassId::DFAPass); registerPass(passCFG, PassId::CFAPass); registerPass(new interpretation::InterpretationPass(this), PassId::InterpretationPass); registerPass(new versions::VersionsPass(this), PassId::VersionsPass); } void* XreateManagerDecoratorFull::run() { + transcend->deleteReports(); std::unique_ptr compiler(new compilation::CompilePassCustomDecorators<>(this)); compiler->run(); llvm->print(); llvm->initJit(); return llvm->getFunctionPointer(compiler->getEntryFunction()); } } //namespace xreate diff --git a/cpp/src/compilation/targets.h b/cpp/src/compilation/targets.h index 0b31ddd..9a0b8cd 100644 --- a/cpp/src/compilation/targets.h +++ b/cpp/src/compilation/targets.h @@ -1,213 +1,223 @@ /* 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: targetabstract.h * Author: pgess * * Created on July 2, 2016, 1:25 PM */ /** * \file * \brief Compilation targets infrastructure */ #ifndef TARGETABSTRACT_H #define TARGETABSTRACT_H #include "ast.h" #include #include #include -namespace xreate{ namespace compilation { - -template +namespace xreate{ +namespace compilation{ + +template struct TargetInfo{ - //typedef Result - //typedef Function - //typedef Scope + //typedef Result + //typedef Function + //typedef Scope }; - + template class Function; template class Target; template class Scope{ - typedef typename TargetInfo::Scope Self; - + typedef typename TargetInfo::Scope Self; + public: - const CodeScope* scope; - Function* function=0; - - typename TargetInfo::Result - processSymbol(const Symbol& s){ - const CodeScope* scope = s.scope; - Self* self = function->getScope(scope); - - if (self->__bindings.count(s.identifier)) { - return self->__bindings[s.identifier]; - } - - const Expression& declaration = CodeScope::getDefinition(s, true); - if (!declaration.isDefined()){ - assert(false); //for bindings there should be result already - } - - return self->__bindings[s.identifier] = self->process(declaration); - } - - typename TargetInfo::Result - processScope() { - return process(scope->getBody()); - } - -// 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(const CodeScope* codeScope, Function* f) - : scope(codeScope), function(f) {} - - virtual ~Scope(){} - - void - overrideBindings(std::list::Result, std::string>> bindings){ - std::list::Result, ScopedSymbol>> bindingsSymbols; - - for (auto entry: bindings){ - assert(scope->__identifiers.count(entry.second)); - ScopedSymbol id{scope->__identifiers.at(entry.second), versions::VERSION_NONE}; - bindingsSymbols.push_back(std::make_pair(entry.first, id)); - } - - overrideBindings(bindingsSymbols); - } - - void - overrideBindings(std::list::Result, ScopedSymbol>> bindings){ - reset(); - - for (auto entry: bindings){ - __bindings[entry.second] = entry.first; - } + const CodeScope* scope; + Function* function = 0; + + typename TargetInfo::Result + processSymbol(const Symbol& s){ + const CodeScope* scope = s.scope; + Self* self = function->getScope(scope); + + if(self->__bindings.count(s.identifier)){ + return self->__bindings[s.identifier]; } - - bool - isBindingDefined(const ScopedSymbol& id){ - return __bindings.count(id); + + const Expression& declaration = CodeScope::getDefinition(s, true); + if(!declaration.isDefined()){ + assert(false); //for bindings there should be result already } - - void registerChildScope(std::shared_ptr scope){ - __childScopes.push_back(scope); + + return self->__bindings[s.identifier] = self->process(declaration); + } + + typename TargetInfo::Result + processScope(){ + return process(scope->getBody()); + } + + // 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(const CodeScope* codeScope, Function* f) + : scope(codeScope), function(f){ } + + virtual + ~Scope(){ } + + void + overrideBindings(std::list::Result, std::string>> bindings){ + std::list < std::pair::Result, ScopedSymbol>> bindingsSymbols; + + for(auto entry: bindings){ + assert(scope->__identifiers.count(entry.second)); + ScopedSymbol id{scope->__identifiers.at(entry.second), versions::VERSION_NONE}; + bindingsSymbols.push_back(std::make_pair(entry.first, id)); } - void reset(){ - __bindings.clear(); - __childScopes.clear(); + overrideBindings(bindingsSymbols); + } + + void + overrideBindings(std::list::Result, ScopedSymbol>> bindings){ + reset(); + + for(auto entry: bindings){ + __bindings[entry.second] = entry.first; } - + } + + bool + isBindingDefined(const ScopedSymbol& id){ + return __bindings.count(id); + } + + void + registerChildScope(std::shared_ptr scope){ + __childScopes.push_back(scope); + } + + void + reset(){ + __bindings.clear(); + __childScopes.clear(); + } + protected: - std::map::Result> __bindings; - std::list> __childScopes; + std::map::Result> __bindings; + std::list> __childScopes; }; template class Function{ - typedef typename TargetInfo::Result Result; - typedef typename TargetInfo::Scope ConcreteScope; - + typedef typename TargetInfo::Result Result; + typedef typename TargetInfo::Scope ConcreteScope; + public: - Function(const ManagedFnPtr& function, Target* target) - : man(target), __function(function) {} - - virtual ~Function(){}; - - ConcreteScope* - getScope(const CodeScope* const scope){ - if (__scopes.count(scope)) { - auto result = __scopes.at(scope).lock(); - - if (result){ - return result.get(); - } - } - - std::shared_ptr unit(new ConcreteScope(scope, this)); - - if (scope->__parent != nullptr){ - getScope(scope->__parent)->registerChildScope(unit); - - } else { - assert(!__entryScope); - __entryScope = unit; - } - - if (!__scopes.emplace(scope, unit).second){ - __scopes[scope] = unit; - } - - return unit.get(); + + Function(const ManagedFnPtr& function, Target* target) + : man(target), __function(function){ } + + virtual + ~Function(){ }; + + ConcreteScope* + getScope(const CodeScope * const scope){ + if(__scopes.count(scope)){ + auto result = __scopes.at(scope).lock(); + + if(result){ + return result.get(); + } } - - virtual Result - process(const std::vector& args)=0; - - Target* man=0; - ManagedFnPtr __function; + + std::shared_ptr unit(new ConcreteScope(scope, this)); + + if(scope->__parent != nullptr){ + getScope(scope->__parent)->registerChildScope(unit); + + } else{ + assert(!__entryScope); + __entryScope = unit; + } + + if(!__scopes.emplace(scope, unit).second){ + __scopes[scope] = unit; + } + + return unit.get(); + } + + virtual Result + process(const std::vector& args) = 0; + + Target* man = 0; + ManagedFnPtr __function; protected: - std::map> __scopes; - std::shared_ptr __entryScope; + std::map> __scopes; + std::shared_ptr __entryScope; }; /** \brief Similar to xreate::IPass */ 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; +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 */ diff --git a/cpp/src/pass/abstractpass.h b/cpp/src/pass/abstractpass.h index 9c8648b..77e1f0b 100644 --- a/cpp/src/pass/abstractpass.h +++ b/cpp/src/pass/abstractpass.h @@ -1,206 +1,205 @@ /* 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 */ #ifndef ABSTRACTPASS_H #define ABSTRACTPASS_H + #include "ast.h" #include "xreatemanager.h" #include -namespace xreate -{ - /** \brief Holds current position in %AST while traversing*/ - struct PassContext - { - const CodeScope* scope = 0; - ManagedFnPtr function; - ManagedRulePtr rule; - std::string varDecl; - - PassContext() - {} - - PassContext updateScope(const CodeScope* scopeNew) { - PassContext context2{*this}; - context2.scope = scopeNew; - return context2; - } - - ~PassContext(){} - }; - - /** \brief Base class for all passes to inherit */ - class IPass { - public: - IPass(PassManager* manager); - virtual ~IPass(){} - - /** \brief Executes pass */ - virtual void run()=0; - - /** \brief Finalizes pass. Empty by default*/ - virtual void finish(); - - PassManager* man; - }; - - template - Output defaultValue(); - - template<> - void defaultValue(); - - /** \brief Stores processing results for already visited nodes */ - 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); - } - }; - - /** \brief Set of already visited nodes */ - 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){ - } - }; - -/** \brief Minimal useful IPass implementation*/ -template -class AbstractPass: public IPass { - SymbolCache __visitedSymbols; -protected: - virtual Output processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol=""){ - if (__visitedSymbols.isCached(symbol)) - return __visitedSymbols.getCachedValue(symbol); +namespace xreate { +/** \brief Holds current position in %AST while traversing*/ +struct PassContext { + const CodeScope* scope = 0; + ManagedFnPtr function; + ManagedRulePtr rule; + std::string varDecl; - const Expression& declaration = CodeScope::getDefinition(symbol, true); - if (declaration.isDefined()){ - PassContext context2 = context.updateScope(symbol.scope); + PassContext() {} - Output&& result = process(declaration, context2, hintSymbol); - return __visitedSymbols.setCachedValue(symbol, std::move(result)); - } + PassContext updateScope(const CodeScope* scopeNew) { + PassContext context2{*this}; + context2.scope = scopeNew; + return context2; + } - return defaultValue(); - } + ~PassContext() {} +}; - Output processExpressionCall(const Expression& expression, PassContext context){ - const std::string &calleeName = expression.getValueString(); - std::list callees = man->root->getFunctionSpecializations(calleeName); - if (callees.size() == 1 && callees.front()){ - return processFnCall(callees.front(), context); +/** \brief Base class for all passes to inherit */ +class IPass { +public: + IPass(PassManager* manager); - } else { - for (const ManagedFnPtr& callee: callees){ - processFnCallUncertain(callee, context); - } + virtual ~IPass() {} - return defaultValue(); - } - } + /** \brief Executes pass */ + virtual void run() = 0; - SymbolCache& getSymbolCache(){ - return __visitedSymbols; - } + /** \brief Finalizes pass. Empty by default*/ + virtual void finish(); + + PassManager* man; +}; + +template +Output +defaultValue(); + +template<> +void +defaultValue(); + +/** \brief Stores processing results for already visited nodes */ +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); + } +}; +/** \brief Set of already visited nodes */ +template<> +class SymbolCache : private std::set { public: - AbstractPass(PassManager* manager) - : IPass(manager){} + bool isCached(const Symbol &symbol) { + bool result = this->count(symbol) > 0; + return result; + } - /** \brief Processes function invocation instruction */ - virtual Output processFnCall(ManagedFnPtr functionCallee, PassContext context){ - return defaultValue(); - } + void setCachedValue(const Symbol &symbol) { + this->insert(symbol); + } + + void getCachedValue(const Symbol &symbol) { + } +}; + +/** \brief Minimal useful IPass implementation*/ +template +class AbstractPass : public IPass { + SymbolCache __visitedSymbols; - /** \brief Processes function invocation instruction in uncertain cases - * \details Executed when it's impossible statically determine exact function invocation. - * In this case get executed for all possible candidates - */ - virtual void processFnCallUncertain(ManagedFnPtr functionCallee, PassContext context) - {} +protected: + virtual Output processSymbol(const Symbol &symbol, PassContext context, const std::string &hintSymbol = "") { + if(__visitedSymbols.isCached(symbol)) + return __visitedSymbols.getCachedValue(symbol); - /** \brief Processes Logic Rule */ - virtual void process(ManagedRulePtr rule) - {} + const Expression &declaration = CodeScope::getDefinition(symbol, true); + if(declaration.isDefined()) { + PassContext context2 = context.updateScope(symbol.scope); - /** \brief Processes Function */ - virtual Output process(ManagedFnPtr function) - { - PassContext context; - context.function = function; + Output &&result = process(declaration, context2, hintSymbol); + return __visitedSymbols.setCachedValue(symbol, std::move(result)); + } - return process(function->getEntryScope(), context); - } + return defaultValue(); + } - /** \brief Processes single CodeScope */ - virtual Output process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl=""){ - context.scope = scope; + Output processExpressionCall(const Expression &expression, PassContext context) { + const std::string &calleeName = expression.getValueString(); + std::list callees = man->root->getFunctionSpecializations(calleeName); - return processSymbol(Symbol{ScopedSymbol::RetSymbol, scope}, context); + //Determined specialization + if(callees.size() == 1 && callees.front()) { + return processFnCall(callees.front(), context); } - //TODO expose Symbol instead of varDecl. Required by DFAPass. - /** \brief Processes single Expression */ - virtual Output process(const Expression& expression, PassContext context, const std::string& varDecl=""){ - if (expression.__state == Expression::IDENT){ - assert(context.scope); - return processSymbol(Attachments::get(expression), context, expression.getValueString()); - } - - assert(false); - return defaultValue(); + //Several specializations or External Fn + return processFnCallUncertain(calleeName, callees, context); + } + + SymbolCache &getSymbolCache() { + return __visitedSymbols; + } + +public: + AbstractPass(PassManager* manager) + : IPass(manager) {} + + /** \brief Processes function invocation instruction */ + virtual Output processFnCall(ManagedFnPtr functionCallee, PassContext context) { + return defaultValue(); + } + + /** \brief Processes function invocation instruction in uncertain cases + * \details Executed when it's impossible statically determine which exactly function is invoked. + */ + virtual Output processFnCallUncertain(const std::string& calleeName, const std::list& candidates, PassContext context) { + return defaultValue(); + } + + /** \brief Processes Logic Rule */ + virtual void process(ManagedRulePtr rule) {} + + /** \brief Processes Function */ + virtual Output process(ManagedFnPtr function) { + PassContext context; + context.function = function; + + return process(function->getEntryScope(), context); + } + + /** \brief Processes single CodeScope */ + virtual Output process(CodeScope* scope, PassContext context, const std::string &hintBlockDecl = "") { + context.scope = scope; + + return processSymbol(Symbol{ScopedSymbol::RetSymbol, scope}, context); + } + + //TODO expose Symbol instead of varDecl. Required by DFAPass. + /** \brief Processes single Expression */ + virtual Output process(const Expression &expression, PassContext context, const std::string &varDecl = "") { + if(expression.__state == Expression::IDENT) { + assert(context.scope); + return processSymbol(Attachments::get(expression), context, expression.getValueString()); + } + + assert(false); + return defaultValue(); + } + + /** \brief Executes AST traverse */ + void run() { + ManagedRulePtr rule = man->root->begin(); + while(rule.isValid()) { + process(rule); + ++rule; } - /** \brief Executes AST traverse */ - void run() { - ManagedRulePtr rule = man->root->begin(); - while (rule.isValid()) { - process(rule); - ++rule; - } - - ManagedFnPtr f = man->root->begin(); - while (f.isValid()) { - process(f); - ++f; - } + ManagedFnPtr f = man->root->begin(); + while(f.isValid()) { + process(f); + ++f; } + } }; template<> void -AbstractPass::processSymbol(const Symbol& symbol, PassContext context, const std::string& hintSymbol); +AbstractPass::processSymbol(const Symbol &symbol, PassContext context, const std::string &hintSymbol); template<> void -AbstractPass::process(const Expression& expression, PassContext context, const std::string& hintSymbol); +AbstractPass::process(const Expression &expression, PassContext context, const std::string &hintSymbol); -} +} #endif diff --git a/cpp/src/pass/cfapass.cpp b/cpp/src/pass/cfapass.cpp index 2a51dc4..3756331 100644 --- a/cpp/src/pass/cfapass.cpp +++ b/cpp/src/pass/cfapass.cpp @@ -1,198 +1,124 @@ /* 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/. * * cfapass.cpp * * Author: pgess */ /** * \file cfapass.h * \brief Control Flow Analysis(CFA) */ -#include "cfapass.h" +#include "pass/cfapass.h" #include "analysis/cfagraph.h" -#include "analysis/DominatorsAnalysisProvider.h" - #include using namespace std; -using namespace xreate::cfa; -void -CFAPassBasic::initSignatures(){ - auto range = man->root->__interfacesData.equal_range(CFA); - for (auto i = range.first; i!= range.second; ++i){ - __signatures.emplace(i->second.op, i->second); - } -} +namespace xreate { +namespace cfa { void -CFAPassBasic::run(){ - initSignatures(); - - return AbstractPass::run(); +CFAPass::initSignatures() { + auto range = man->root->__interfacesData.equal_range(CFA); + for(auto i = range.first; i != range.second; ++i) { + __signatures.emplace(i->second.op, i->second); + } } void -CFAPassBasic::finish(){ - man->transcend->registerReport(__context.graph); - boost::scoped_ptr cfaAdapter(dominators::CFAGraphAdapter::build(__context.graph)); - dominators::DominatorsAnalysisProvider* reportDominators = new dominators::DominatorsAnalysisProvider(); - reportDominators->run(cfaAdapter.get()); - man->transcend->registerReport(reportDominators); - - return AbstractPass::finish(); +CFAPass::run() { + initSignatures(); + + return AbstractPass::run(); } void -CFAPassBasic::processFnCall(ManagedFnPtr function, PassContext context){ - TranscendLayer* transcend = man->transcend; - __context.graph->addCallConnection(transcend->pack(context.scope), function->getName()); +CFAPass::finish() { + man->transcend->registerReport(__context.graph); - return AbstractPass::processFnCall(function, context); + return AbstractPass::finish(); } void -CFAPassBasic::processFnCallUncertain(ManagedFnPtr function, PassContext context){ - TranscendLayer* transcend = man->transcend; - __context.graph->addCallConnection(transcend->pack(context.scope), function->getName()); +CFAPass::processFnCall(ManagedFnPtr function, PassContext context) { + TranscendLayer* transcend = man->transcend; + __context.graph->addCallConnection(transcend->pack(context.scope), function->getName()); - return AbstractPass::processFnCallUncertain(function, context); + return AbstractPass::processFnCall(function, context); } void -CFAPassBasic::process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl){ - TranscendLayer* transcend = man->transcend; - - const CodeScope* scopeParent = context.scope; - ScopePacked scopeId = transcend->pack(scope); - - __context.graph->addScope(scope); - - //Parent Relations - if (scopeParent){ - __context.graph->addParentConnection(scopeId, transcend->pack(scopeParent)); - } else { - __context.graph->addParentConnection(scopeId, context.function->getName()); - } +CFAPass::processFnCallUncertain(const std::string& calleeName, const std::list& candidates, PassContext context) { + TranscendLayer* transcend = man->transcend; + __context.graph->addCallConnection(transcend->pack(context.scope), calleeName); - //TOTEST scope annotations - //SECTIONTAG context gather scope annotations - __context.graph->addScopeAnnotations(scopeId, scope->tags); - - __context.graph->addContextRules(scopeId, scope->contextRules); - - return AbstractPass::process(scope, context, hintBlockDecl); + return AbstractPass::processFnCallUncertain(calleeName, candidates, context); } -//TOTEST scope annotations via scheme void -CFAPassBasic::process(const Expression& expression, PassContext context, const std::string& varDecl){ - TranscendLayer* transcend = man->transcend; +CFAPass::process(CodeScope* scope, PassContext context, const std::string &hintBlockDecl) { + TranscendLayer* transcend = man->transcend; - if (expression.__state == Expression::COMPOUND){ - Operator op= expression.op; + const CodeScope* scopeParent = context.scope; + ScopePacked scopeId = transcend->pack(scope); - if (__signatures.count(op)) { - assert(expression.blocks.size()); + __context.graph->addScope(scope); - for (const auto& scheme: boost::make_iterator_range(__signatures.equal_range(expression.op))) { - __context.graph->addScopeAnnotations(transcend->pack(expression.blocks.front()), scheme.second.getOperands()); - } - } - } + //Parent Relations + if(scopeParent) { + __context.graph->addParentConnection(scopeId, transcend->pack(scopeParent)); + } else { + __context.graph->addParentConnection(scopeId, context.function->getName()); + } - return AbstractPass::process(expression, context, varDecl); -} + //TOTEST scope annotations + //SECTIONTAG context gather scope annotations + __context.graph->addScopeAnnotations(scopeId, scope->tags); -void -CFAPassBasic::process(ManagedFnPtr function){ - __context.graph->addFunctionAnnotations(function->getName(), function->getTags()); - return AbstractPass::process(function); + __context.graph->addContextRules(scopeId, scope->contextRules); + + return AbstractPass::process(scope, context, hintBlockDecl); } -CFAPassBasic::CFAPassBasic(PassManager* manager) -: AbstractPass(manager) - , __context{new CFAGraph(manager->transcend)} -{} +//TOTEST scope annotations via scheme -/****************************SCOPE DEPENDENCIES********************************/ void -CFAPassDependenciesDecorator::process(const Expression& expression, PassContext context, const std::string& varDecl){ - TranscendLayer* transcend = man->transcend; - - if (expression.__state == Expression::COMPOUND) - switch(expression.op){ - case Operator::SEQUENCE:{ - ScopePacked scopePrev = transcend->pack(expression.blocks.front()); - for(auto scopeIt= ++expression.blocks.begin(); scopeIt != expression.blocks.end(); ++scopeIt){ - ScopePacked scopeCurrent = transcend->pack(*scopeIt); - __context.graph->addDependency(scopeCurrent, scopePrev); - scopePrev = scopeCurrent; - } - break; - } - - default: break; - } +CFAPass::process(const Expression &expression, PassContext context, const std::string &varDecl) { + TranscendLayer* transcend = man->transcend; - return Parent::process(expression, context, varDecl); -} + if(expression.__state == Expression::COMPOUND) { + Operator op = expression.op; -void -CFAPassDependenciesDecorator::processFnCall(ManagedFnPtr function, PassContext context){ - TranscendLayer* transcend = man->transcend; + if(__signatures.count(op)) { + assert(expression.blocks.size()); - const CodeScope* scopeCaller = context.scope; - assert(scopeCaller); - ScopePacked scopeCallerPacked = transcend->pack(scopeCaller); - - if(__context.graph->isDependent(scopeCallerPacked)){ - ScopePacked scopeCalleePacked = transcend->pack(function->getEntryScope()); - __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); + for(const auto &scheme : boost::make_iterator_range(__signatures.equal_range(expression.op))) { + __context.graph->addScopeAnnotations(transcend->pack(expression.blocks.front()), scheme.second.getOperands()); + } } + } - Parent::processFnCall(function, context); + return AbstractPass::process(expression, context, varDecl); } void -CFAPassDependenciesDecorator::processFnCallUncertain(ManagedFnPtr function, PassContext context){ - TranscendLayer* transcend = man->transcend; - - const CodeScope* scopeCaller = context.scope; - assert(scopeCaller); - ScopePacked scopeCallerPacked = transcend->pack(scopeCaller); - - if(__context.graph->isDependent(scopeCallerPacked)){ - ScopePacked scopeCalleePacked = transcend->pack(function->getEntryScope()); - __context.graph->transmitDependencies(scopeCalleePacked, scopeCallerPacked); - } - - Parent::processFnCallUncertain(function, context); +CFAPass::process(ManagedFnPtr function) { + __context.graph->addFunctionAnnotations(function->getName(), function->getTags()); + return AbstractPass::process(function); } -void -CFAPassDependenciesDecorator::process(CodeScope* scope, - PassContext context, const std::string& hintBlockDecl){ - - TranscendLayer* transcend = man->transcend; - const CodeScope* scopeParent = context.scope; - - if (scopeParent){ - ScopePacked scopePacked = transcend->pack(scope); - ScopePacked scopeParentPacked = transcend->pack(scopeParent); - if (!__context.graph->isDependent(scopePacked) && - __context.graph->isDependent(scopeParentPacked)) { - __context.graph->transmitDependencies(scopePacked, scopeParentPacked); - } - } +CFAPass::CFAPass(PassManager* manager) +: AbstractPass(manager), __context{new CFAGraph(manager->transcend)} +{ +} - Parent::process(scope, context, hintBlockDecl); +} } /** * \class xreate::cfa::CFAPass * \details Provides CFA, important analysis for reasoning. Iterates over AST and stores collected data in CFAGraph */ diff --git a/cpp/src/pass/cfapass.h b/cpp/src/pass/cfapass.h index 20f7467..b4ee3c8 100644 --- a/cpp/src/pass/cfapass.h +++ b/cpp/src/pass/cfapass.h @@ -1,67 +1,51 @@ /* 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 * * cfapass.cpp * Control Flow Graph building pass */ #ifndef CFGPASS_H #define CFGPASS_H #include "xreatemanager.h" #include "transcendlayer.h" #include "abstractpass.h" +#include "analysis/cfagraph.h" namespace xreate{namespace cfa { class CFAGraph; /** \brief Control Flow Analysis Pass(%CFA)*/ -class CFAPassBasic : public AbstractPass{ +class CFAPass : public AbstractPass{ public: void process(ManagedFnPtr function) override; void processFnCall(ManagedFnPtr function, PassContext context) override; - void processFnCallUncertain(ManagedFnPtr function, PassContext context) override; + void processFnCallUncertain(const std::string& calleeName, const std::list& candidates, PassContext context) override; void process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl="") override; void process(const Expression& expression, PassContext context, const std::string& varDecl="") override; - CFAPassBasic(PassManager* manager); + CFAPass(PassManager* manager); void finish() override; void run() override; const CFAGraph* getReport() const {return __context.graph; } protected: struct { CFAGraph* graph; } __context; std::multimap __signatures; //CFA data for particular operators void initSignatures(); }; -class CFAPassDependenciesDecorator: public CFAPassBasic{ - typedef CFAPassBasic Parent; - -public: - CFAPassDependenciesDecorator(PassManager* manager): CFAPassBasic(manager) {} - - void process(const Expression& expression, PassContext context, const std::string& varDecl) override; - void processFnCall(ManagedFnPtr function, PassContext context) override; - void processFnCallUncertain(ManagedFnPtr function, PassContext context) override; - void process(CodeScope* scope, PassContext context, const std::string& hintBlockDecl) override; -}; - -class CFAPass: public CFAPassDependenciesDecorator{ -public: - CFAPass(PassManager* manager): CFAPassDependenciesDecorator(manager) {} -}; - }} //end of namespace xreate::cfa #endif // CFGPASS_H diff --git a/cpp/src/pass/cfatemporalseqpass.cpp b/cpp/src/pass/cfatemporalseqpass.cpp new file mode 100644 index 0000000..9710e61 --- /dev/null +++ b/cpp/src/pass/cfatemporalseqpass.cpp @@ -0,0 +1,125 @@ +/* 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: cfatemporalseqpass.cpp + * Author: pgess + * + * Created on February 4, 2019, 4:43 PM + */ + +/** + * \file cfatemporalseqpass.h + * \brief Context Blocks' compilation order analysis. + */ + +#include "pass/cfatemporalseqpass.h" +#include "analysis/temporalseqgraph.h" + +using namespace xreate::cfa; +using namespace std; + +namespace xreate { + template<> + cfa::Socket defaultValue() { + const cfa::TemporalNode invalidNode{(ScopePacked) - 1, cfa::TemporalOperator::EMPTY}; + return make_pair(invalidNode, invalidNode); + }; +} + +CFATemporalSeqPass::CFATemporalSeqPass(PassManager* manager) +: AbstractPass(manager), __graph(new TemporalSeqGraph(manager->transcend)) { } + +void +CFATemporalSeqPass::finish() { + man->transcend->registerReport(__graph); + return AbstractPass::finish(); +} + +void +CFATemporalSeqPass::process( + const Expression &expression, + PassContext context, + const std::string &varDecl) { + + TranscendLayer* transcend = man->transcend; + + if(expression.__state == Expression::COMPOUND) { + Operator op = expression.op; + + switch(op) { + case Operator::QUERY_LATE: + case Operator::MAP: + case Operator::FOLD: + case Operator::INF: + { + __graph->addSubScopes(context.scope, + expression.blocks); + break; + } + + case Operator::IF: + case Operator::SWITCH: + case Operator::SWITCH_LATE: + case Operator::SWITCH_VARIANT: + { + __graph->addBranchScopes(context.scope, + expression.blocks); + break; + } + + case Operator::SEQUENCE: + { + auto socket = __graph->addSocket(context.scope, TemporalOperator::AND); + auto nodeFrom = socket.first; + + for(auto scopeIt = expression.blocks.begin(); scopeIt != expression.blocks.end(); ++scopeIt) { + ScopePacked scope = transcend->pack(*scopeIt); + TemporalNode node{scope, TemporalOperator::SCOPE}; + + __graph->connect(nodeFrom, node); + nodeFrom = node; + } + + __graph->connect(nodeFrom, socket.second); + } + + default: + break; + } + } + + return Parent::process(expression, context, varDecl); +} + +void +CFATemporalSeqPass::processFnCall(ManagedFnPtr functionCallee, PassContext context) { + auto callerSock = __graph->addSocket(context.scope, TemporalOperator::AND); + auto calleeSock = __graph->getFnSocket(functionCallee); + + __graph->connectGuarded(callerSock, calleeSock); +} + +void +CFATemporalSeqPass::processFnCallUncertain(const std::string& calleeName, const std::list& candidates, PassContext context) { + auto callerSock = __graph->addSocket(context.scope, TemporalOperator::AND); + auto calleeSock = __graph->getUncertainFnSocket(calleeName, candidates); + + __graph->connectGuarded(callerSock, calleeSock); +} + +void +CFATemporalSeqPass::process(ManagedFnPtr function) { + TranscendLayer* transcend = man->transcend; + + Socket fnSocket = __graph->getFnSocket(function); + TemporalNode entryNode{ + transcend->pack(function->getEntryScope()), + TemporalOperator::SCOPE + }; + + __graph->connect(fnSocket.first, entryNode); + __graph->connect(entryNode, fnSocket.second); + + return Parent::process(function); +} \ No newline at end of file diff --git a/cpp/src/pass/cfatemporalseqpass.h b/cpp/src/pass/cfatemporalseqpass.h new file mode 100644 index 0000000..c5d15e6 --- /dev/null +++ b/cpp/src/pass/cfatemporalseqpass.h @@ -0,0 +1,41 @@ +/* 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: cfatemporalseqpass.h + * Author: pgess + * + * Created on February 4, 2019, 4:43 PM + */ + +#ifndef CFATEMPORALSEQPASS_H +#define CFATEMPORALSEQPASS_H + +#include "xreatemanager.h" +#include "abstractpass.h" + +namespace xreate{namespace cfa { + +class TemporalSeqGraph; + +class CFATemporalSeqPass: public AbstractPass{ + typedef AbstractPass Parent; + +public: + CFATemporalSeqPass(PassManager* manager); + void processFnCall(ManagedFnPtr functionCallee, PassContext context) override; + void processFnCallUncertain(const std::string& calleeName, const std::list& candidates, PassContext context) override; + void process(const Expression& expression, PassContext context, const std::string& varDecl="") override; + void process(ManagedFnPtr function) override; + + const TemporalSeqGraph* getReport() const {return __graph; } + void finish() override; + +private: + TemporalSeqGraph* __graph; +}; + +}} //end of namespace xreate::cfa + +#endif /* CFATEMPORALSEQPASS_H */ + diff --git a/cpp/src/transcendlayer.cpp b/cpp/src/transcendlayer.cpp index 26ced04..adfda07 100644 --- a/cpp/src/transcendlayer.cpp +++ b/cpp/src/transcendlayer.cpp @@ -1,496 +1,501 @@ /* 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 * File: transcendlayer.cpp */ /** * \file transcendlayer.h * \brief Reasoner. Wrapper over the external Clasp reasoner library */ #include "transcendlayer.h" #include "analysis/utils.h" #include "utils.h" #include #include #include #include #include #include using namespace std; //TODO escape identifiers started with upper case symbol namespace xreate{ bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2) { return s1.id == s2.id && s1.flagIsUsed == s2.flagIsUsed; } struct VisitorSymbolNodeHash : public boost::static_visitor{ std::size_t operator()(const xreate::SymbolPacked& node) const noexcept { return 2 * (node.identifier + 3 * node.scope + 5 * std::abs(node.version)); } std::size_t operator()(const xreate::SymbolAnonymous& node) const noexcept { return 7 * node.id; } } ; } namespace std{ std::size_t hash::operator()(xreate::SymbolNode const& s) const noexcept { return boost::apply_visitor(xreate::VisitorSymbolNodeHash(), s); } std::size_t hash::operator()(xreate::SymbolGeneralized const& s) const noexcept { return xreate::AttachmentsId::getId(s); } } namespace xreate{ void TranscendLayer::printWarnings(std::ostream& out) { const std::string warningTag = "warning"; auto warningsModel = query(warningTag); if(warningsModel.size()) for(auto warning : warningsModel) { unsigned int warningId; Gringo::Symbol params; std::tie(warningId, params) = parse(warning.second); cout << "Warning: " << __warnings.at(warningId) << " "; params.print(out); out << params; } } bool TranscendLayer::processSolution(Gringo::Model const &model) { cout << "Model: " << endl; const string& atomBindVar = Config::get("transcend.bindings.variable"); const string& atomBindFunc = Config::get("transcend.bindings.function"); const string& atomBindScope = Config::get("transcend.bindings.scope"); for(Gringo::Symbol atom : model.atoms(clingo_show_type_atoms)) { atom.print(cout); cout << " | " << endl; string atomName(atom.name().c_str()); if(atomName == atomBindVar || atomName == atomBindFunc || atomName == atomBindScope) { string atomAlias = std::get<1>(parse(atom)).name().c_str(); __model.emplace(atomAlias, atom); continue; } __model.emplace(atomName, atom); } return true; } void TranscendLayer::registerReport(IAnalysisReport * report) { __reports.push_back(report); } void -TranscendLayer::runReports() { +TranscendLayer::printReports() { for(IAnalysisReport* report : __reports) { report->print(__partGeneral); - delete report; } +} - __reports.clear(); +void +TranscendLayer::deleteReports(){ + for(IAnalysisReport* report : __reports) { + delete report; + } + __reports.clear(); } void TranscendLayer::addRuleWarning(const RuleWarning & rule) { //__partGeneral << rule << endl; list domains; boost::format formatDef("%1%(%2%)"); std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(domains, domains.begin()), [&formatDef](const std::pair &argument) { string domain; switch(argument.second) { case DomainAnnotation::FUNCTION: domain = "function"; break; case DomainAnnotation::VARIABLE: domain = "variable"; break; } return boost::str(formatDef % domain % argument.first); }); list vars; std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(vars, vars.begin()), [](const std::pair &argument) { return argument.first.c_str(); }); list> guardsRaw; std::transform(rule.__guards.begin(), rule.__guards.end(), std::inserter(guardsRaw, guardsRaw.begin()), [this](const Expression & guard) { return xreate::analysis::compile(guard); }); const list& guards = xreate::analysis::multiplyLists(std::move(guardsRaw)); list &&branches = xreate::analysis::compileNeg(rule.__condition); boost::format formatWarning("warning(%1%, (%2%)):- %3%, %4%, %5%."); for(const string &guardsJoined : guards) for(const string &branch : branches) { unsigned int hook = registerWarning(string(rule.__message)); __partGeneral << formatWarning % (hook) % (boost::algorithm::join(vars, ", ")) % (branch) % (guardsJoined) % (boost::algorithm::join(domains, ", ")) << endl; } } unsigned int TranscendLayer::registerWarning(std::string && message) { static int warningId = 0; __warnings.emplace(warningId, message); return warningId++; } void TranscendLayer::involveImports() { ostream &out = __partGeneral; if(ast) for(string fn : ast->__rawImports) { std::ifstream file(fn); if(!file) { std::cout << "Can't process script file: " << fn << std::endl; assert(false); } while(!file.eof()) { string line; std::getline(file, line); out << line << endl; } } } void TranscendLayer::addRawScript(std::string && script) { __partGeneral << script; } void TranscendLayer::run() { involveImports(); - runReports(); + printReports(); ostringstream program; program << __partTags.str() << __partGeneral.str(); cout << FYEL(program.str()) << endl; std::vector args{"clingo", nullptr}; DefaultGringoModule moduleDefault; Gringo::Scripts scriptsDefault(moduleDefault); ClingoLib ctl(scriptsDefault, 0, args.data(), { }, 0); ctl.add("base",{}, program.str()); ctl.ground({ {"base", {}} }, nullptr); // solve Gringo::SolveResult result = ctl.solve([this](Gringo::Model const &model) { this->processSolution(model); return true; }, { }); if(result.satisfiable() == Gringo::SolveResult::Satisfiable) { cout << FGRN("SUCCESSFULLY") << endl; } else { cout << FRED("UNSUCCESSFULLY") << endl; } // invoke all query plugins to process solution for(auto q : __queries) { q.second->init(this); } } TranscendLayer::TranscendLayer() : ast(nullptr) { } StaticModel TranscendLayer::query(const std::string & atom) const { StaticModel result; if (! __model.count(atom)) { return result; } auto currentDataRange = __model.equal_range(atom); std::copy(currentDataRange.first, currentDataRange.second, std::inserter(result, result.end())); return result; } ScopePacked TranscendLayer::pack(const CodeScope * const scope) { auto pos = __indexScopes.emplace(scope, __indexScopes.size()); if(pos.second) __registryScopes.push_back(scope); return pos.first->second; } size_t TranscendLayer::getScopesCount() const { return __registryScopes.size(); } SymbolPacked TranscendLayer::pack(const Symbol& symbol, std::string hintSymbolName) { SymbolPacked result(symbol.identifier.id, symbol.identifier.version, pack(symbol.scope)); __indexSymbolNameHints.emplace(result, hintSymbolName); return result; } Symbol TranscendLayer::unpack(const SymbolPacked & symbol) const { return Symbol{ScopedSymbol {symbol.identifier, symbol.version}, __registryScopes[symbol.scope]}; }; std::string TranscendLayer::getHintForPackedSymbol(const SymbolPacked & symbol) { auto result = __indexSymbolNameHints.find(symbol); return(result == __indexSymbolNameHints.end()) ? "" : result->second; } IQuery * TranscendLayer::registerQuery(IQuery *query, const QueryId & id) { return __queries.emplace(id, query).first->second; } IQuery * TranscendLayer::getQuery(const QueryId & id) { assert(__queries.count(id) && "Undefined query"); return __queries.at(id); } class VisitorUnpackSymbol : public boost::static_visitor{ public: VisitorUnpackSymbol(const TranscendLayer* transcend) : __transcend(transcend) { } SymbolGeneralized operator()(const SymbolPacked& symbol) const { return __transcend->unpack(symbol); } SymbolGeneralized operator()(const SymbolAnonymous& symbol) const { return symbol; } private: const TranscendLayer* __transcend; } ; class VisitorPackSymbol : public boost::static_visitor{ public: VisitorPackSymbol(TranscendLayer* transcend, const std::string& hintSymbolName) : __transcend(transcend), __hint(hintSymbolName) { } SymbolNode operator()(const Symbol& symbol) const { return __transcend->pack(symbol, __hint); } SymbolNode operator()(const SymbolAnonymous& symbol) const { return symbol; } private: TranscendLayer* __transcend; std::string __hint; } ; SymbolNode TranscendLayer::pack(const SymbolGeneralized& symbol, const std::string & hintSymbolName) { return boost::apply_visitor(VisitorPackSymbol(this, hintSymbolName), symbol); } SymbolGeneralized TranscendLayer::unpack(const SymbolNode & symbol) const { return boost::apply_visitor(VisitorUnpackSymbol(this), symbol); } bool operator==(const SymbolPacked& s1, const SymbolPacked & s2) { return s1.identifier == s2.identifier && s1.scope == s2.scope; } bool operator<(const SymbolPacked& s1, const SymbolPacked & s2) { return s1.scope < s2.scope || (s1.scope == s2.scope && s1.identifier < s2.identifier); } Expression ParseImplAtom ::get(const Gringo::Symbol & atom) { switch(atom.type()) { case Gringo::SymbolType::Num: return Expression(atom.num()); case Gringo::SymbolType::Str: return Expression(Atom(std::string(atom.string().c_str()))); case Gringo::SymbolType::Fun: { //FUNC Expression result(Operator::CALL,{Expression(Atom(std::string(atom.name().c_str())))}); for(const Gringo::Symbol& arg : atom.args()) { result.addArg(ParseImplAtom::get(arg)); } return result; } default: { assert(false); } } } int ParseImplAtom ::get(const Gringo::Symbol & atom) { switch(atom.type()) { case Gringo::SymbolType::Num: return atom.num(); default: break; } assert(false && "Inappropriate symbol type"); } std::string ParseImplAtom ::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"); } SymbolPacked ParseImplAtom ::get(const Gringo::Symbol & atom) { auto result = TranscendLayer::parse(atom); return SymbolPacked(std::get<0>(result), std::get<1>(result), std::get<2>(result)); }; Gringo::Symbol ParseImplAtom ::get(const Gringo::Symbol & atom) { return atom; } SymbolNode ParseImplAtom ::get(const Gringo::Symbol & atom) { assert(atom.type() == Gringo::SymbolType::Fun && "Inappropriate symbol type"); if(atom.name() == "a") { return SymbolAnonymous{(unsigned int) std::get<0>(TranscendLayer::parse(atom))}; } else if(atom.name() == "s") { return ParseImplAtom::get(atom); } assert(false && "Wrong symbol format"); } class VisitorSymbolId : public boost::static_visitor{ public: unsigned int operator()(const Symbol& symbol) const { return AttachmentsId::getId(symbol); } unsigned int operator()(const SymbolAnonymous& symbol) const { return symbol.id; } } ; unsigned int AttachmentsId ::getId(const SymbolGeneralized & symbol) { return boost::apply_visitor(VisitorSymbolId(), symbol); } } //end of xreate namespace /** * \class xreate::TranscendLayer * \brief Reasoning and logic Solver. * * Wraps external brilliant fantastic tool [Clasp solver](https://potassco.org/clasp/) * * For building *logic program* for reasoning TranscendLayer takes input from: * - Raw scripts. Client could append arbitrary ASP script to _logic program_. \ref addRawScript() * - Includes. There is possibility to specify external files with ASP scripts * to append to _logic program_. \ref involveImports() (private member) * - Diagnostic rules. Rules that produce diagnostic messages during * compilation(warnings) or even able to halt compilation with errors. * addRuleWarning(), \ref registerWarning() * - DFA data. \ref setDFAData() * - CFA data. \ref setCFAData() * - Dominators Analysis. See xreate::dominators::DominatorsAnalysisProvider. * Executed by \ref run() * - Context rules. See xreate::ContextRule and general [Context Explanation](/w/concepts/context) * * Data sources implement xreate::IAnalysisReport. Generally, input could be loosely divided into three categories: * - *Internally derived* data. CFA, DFA, Dominators analyses *automatically* feed reasoner by * useful insights about data, structure and algorithms of a program * - *User provided* data. CFA, DFA, Diagnostic/Context rules feed reasoner by * annotations Developer specifically provides manually * - *External* data. Raw scripts and includes feed reasoner with third-party data * related to a different aspects of a program possibly produced by external analyzers * * Once TranscendLayer got input from all providers and logic program is fully constructed * it runs external Clasp reasoner and receives back desired solutions. * * Output of the external Clasp reasoner is recognized and accessed via *queries*. * IQuery represents an interface between reasoner's output and rest of Xreate. * Each query inherits xreate::IQuery interface. Currently there are queries as follows: * - xreate::containers::Query to catch solutions regarding Containers implementation. See [Containers Explanation](/w/concepts/containers) * - xreate::context::ContextQuery to catch solution regarding Context. See [Context Explanation](/w/concepts/context) * * \sa See xreate::dfa::DFAPass, xreate::cfa::CFAPass, xreate::IQuery, xreate::IAnalysisReport, xreate::dominators::DominatorsAnalysisProvider */ diff --git a/cpp/src/transcendlayer.h b/cpp/src/transcendlayer.h index e657c1c..e0051bb 100644 --- a/cpp/src/transcendlayer.h +++ b/cpp/src/transcendlayer.h @@ -1,283 +1,284 @@ /* 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 * File: transcendlayer.h */ #ifndef transcendLAYER_H #define transcendLAYER_H #include "ast.h" #include "contextrule.h" #include #include #include #include #include #include #include #include #include #include namespace xreate { typedef unsigned int ScopePacked; const ScopePacked SCOPE_ABSTRACT_GLOBAL = std::numeric_limits::max(); struct SymbolPacked { SymbolPacked(){} SymbolPacked(ScopedSymbol i, ScopePacked s): identifier(i.id), version(i.version), scope(s){} SymbolPacked(VNameId symbolId, versions::VariableVersion symbolVersion, ScopePacked symbolScope) : identifier(symbolId), version(symbolVersion), scope(symbolScope){} VNameId identifier; versions::VariableVersion version; ScopePacked scope; }; bool operator==(const SymbolPacked& s1, const SymbolPacked& s2); bool operator<(const SymbolPacked& s1, const SymbolPacked& s2); struct SymbolAnonymous { unsigned int id; bool flagIsUsed = false; }; bool operator==(const SymbolAnonymous& s1, const SymbolAnonymous& s2); typedef boost::variant SymbolNode; //DEBT use SymbolGeneralized communicating with Analysis rather than Symbol typedef boost::variant SymbolGeneralized; template<> struct AttachmentsId{ static unsigned int getId(const SymbolGeneralized& symbol); }; } namespace std { template<> struct hash { std::size_t operator()(xreate::SymbolNode const& s) const noexcept; }; template<> struct hash { std::size_t operator()(xreate::SymbolGeneralized const& s) const noexcept; }; } namespace xreate { enum class DFGConnection { STRONG, WEAK, PROTOTYPE }; /** \brief Designated to mark analysis results that can be composed as *logic program* */ class IAnalysisReport { public: /** \brief Composes *logic program* based on analysis data into ASP format and appends to a stream*/ virtual void print(std::ostringstream& output) const = 0; virtual ~IAnalysisReport(){}; }; /** \brief Logic program query interface */ class IQuery { public: virtual void init(TranscendLayer* transcend) = 0; virtual ~IQuery() {} }; enum class QueryId { ContainersQuery, PolymorphQuery, LatexQuery }; namespace dfa{ class DFAGraph; } namespace cfa { class CFAGraph; } typedef std::multimap StaticModel; typedef StaticModel::const_iterator StaticModelIterator; class TranscendLayer { friend class ContextRule; /**\name Data Providers Management */ ///@{ public: void registerReport(IAnalysisReport* report); - void runReports(); + void printReports(); + void deleteReports(); /** \brief Appends arbitrary string to *logic program* */ void addRawScript(std::string&& script); private: std::list __reports; /** Includes external text files to a *logic program* */ void involveImports(); ///@} /**\name Queries Management */ ///@{ public: /** \brief Adds query. See xreate::IQuery */ IQuery* registerQuery(IQuery* query, const QueryId& id); /** \brief Returns particular query. See xreate::IQuery */ IQuery* getQuery(const QueryId& id); template static std::tuple parse(const Gringo::Symbol& atom); StaticModel query(const std::string& atom) const; size_t getScopesCount() const; SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName = ""); ScopePacked pack(const CodeScope * const scope); Symbol unpack(const SymbolPacked& symbol) const; SymbolNode pack(const SymbolGeneralized& symbol, const std::string& hintSymbolName); SymbolGeneralized unpack(const SymbolNode& symbol) const; std::string getHintForPackedSymbol(const SymbolPacked& symbol); ///@} private: std::map __queries; std::map __indexSymbolNameHints; std::unordered_map __indexScopes; std::vector __registryScopes; /**\name Diagnostic */ ///@{ //TODO diagnostic move over to separate provider/query public: /** \brief Adds diagnostic rule */ void addRuleWarning(const RuleWarning &rule); /** \brief Registers diagnostic messages */ unsigned int registerWarning(std::string &&message); private: std::map __warnings; void printWarnings(std::ostream& out); ///@} ///@{ public: TranscendLayer(); /** \brief Executes reasoning */ void run(); ///@} AST *ast; protected: virtual bool processSolution(Gringo::Model const &model); private: StaticModel __model; std::ostringstream __partTags; std::ostringstream __partGeneral; }; template struct ParseImplAtom { static typ get(const Gringo::Symbol& atom) { return atom.num(); } }; template<> struct ParseImplAtom { static int get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static std::string get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static SymbolPacked get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static SymbolNode get(const Gringo::Symbol& atom); }; template<> struct ParseImplAtom { static Gringo::Symbol get(const Gringo::Symbol& atom); }; template struct ParseImplAtom>{ static std::list get(const Gringo::Symbol& atom){ bool flagIsList = (atom.type() == Gringo::SymbolType::Fun) && atom.name().empty(); std::list result; if(!flagIsList) { //treat as degenerate case: list with a single element result.push_back(ParseImplAtom::get(atom)); return result; } for (const Gringo::Symbol& arg: atom.args()) { result.push_back(ParseImplAtom::get(arg)); } return result; } }; template<> struct ParseImplAtom { static Expression get(const Gringo::Symbol& atom); }; 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 TranscendLayer::parse(const Gringo::Symbol& atom) { typedef std::tuple < Types...> Tuple; Tuple tup; Parse_Impl::value>::parse(tup, atom.args().first); return tup; } } //end of xreate namespace #endif diff --git a/cpp/src/utils.h b/cpp/src/utils.h index b45173b..626ec4a 100644 --- a/cpp/src/utils.h +++ b/cpp/src/utils.h @@ -1,167 +1,172 @@ /* 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/. * * utils.cpp * * Author: pgess */ #ifndef UTILS_H #define UTILS_H #include "jeayeson/jeayeson.hpp" namespace xreate { template struct AddTag { explicit AddTag(const Source &src) : __src(src) { } explicit AddTag(Source &&src) : __src(std::move(src)) { } operator const Source&() const{ return __src; } const Source& get() const{ return __src; } const Source* operator->() const { return &__src; } private: Source __src; }; struct Expand_t{}; template using Expanded = AddTag; //DEBT move to resources compiler. https://github.com/markusfisch/cpprc class Config { private: json_map __storage; static Config __self; Config(); public: static std::string get(std::string key) { return __self.__storage.get_for_path(key).get(); } }; /** \brief Decorators support */ template struct DecoratorsDict{ //typedef ConcreteDecoratorForTag result; }; template struct Decorators{ typedef typename DecoratorsDict::result Instance; template static Instance* getInterface(Base* obj){ Instance* result = dynamic_cast< Instance* > (obj); assert(result); return result; } }; 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; } + + bool operator< (const ManagedPtr& other) const{ + if(__storage != other.__storage) return __storage < other.__storage; + return __id < other.__id; + } private: unsigned int __id = 0; const std::vector * __storage = 0; }; } std::wstring utf8_to_wstring(const std::string& str); std::string wstring_to_utf8(const std::wstring& str); #define RST "\x1B[0m" #define KRED "\x1B[31m" #define KGRN "\x1B[32m" #define KYEL "\x1B[33m" #define KBLU "\x1B[34m" #define KMAG "\x1B[35m" #define KCYN "\x1B[36m" #define KWHT "\x1B[37m" #define FRED(x) KRED << x << RST #define FGRN(x) KGRN < * Created on July 3, 2017, 6:03 PM */ /** * \file * \brief Entry point of Xreate API. * */ #ifndef PASSMANAGER_H #define PASSMANAGER_H #include #include //stdio external struct _IO_FILE; typedef struct _IO_FILE FILE; namespace xreate { namespace grammar { namespace main { class Scanner; }}} namespace xreate { class IPass; class TranscendLayer; class LLVMLayer; class AST; enum class PassId { - CFAPass, + CFAPass, CFATemporalSeqPass, CompilePass, DFAPass, EnvironmentTestsPass, LoggerPass, RulesPass, InterpretationPass, VersionsPass }; /** * \class PassManager * \brief Base class to control passes */ class PassManager{ public: void prepare(AST* ast); void registerPass(IPass* pass, const PassId& id, IPass* prerequisite=nullptr); IPass* getPassById(const PassId& id); bool isPassRegistered(const PassId& id); void executePasses(); virtual ~PassManager(); TranscendLayer* transcend; LLVMLayer* llvm; AST* root; private: std::map __passes; std::multimap __passDependencies; }; namespace details{ namespace tier2{ class XreateManager: public virtual PassManager{ public: virtual ~XreateManager(){}; virtual void initPasses()=0; // virtual void executePasses()=0; virtual void analyse()=0; virtual void* run()=0; static XreateManager* prepare(std::string&& code); static XreateManager* prepare(FILE* code); }; template class XreateManagerImpl: public Decorator { public: }; }} //namespace details::tier2 namespace details{ namespace tier1{ class XreateManager: public virtual PassManager{ public: virtual void analyse()=0; virtual void* run()=0; static XreateManager* prepare(std::string&& code); static XreateManager* prepare(FILE* code); }; template class XreateManagerImpl: public XreateManager, public details::tier2::XreateManagerImpl { typedef details::tier2::XreateManagerImpl PARENT; public: void analyse(){ PARENT::initPasses(); PARENT::executePasses(); PARENT::analyse(); } void* run(){ return PARENT::run(); } }; }} //namespace details::tier1 class XreateManager: public virtual PassManager{ public: virtual void* run()=0; static XreateManager* prepare(std::string&& code); static XreateManager* prepare(FILE* code); }; template class XreateManagerImpl: public XreateManager, public details::tier1::XreateManagerImpl{ typedef details::tier1::XreateManagerImpl PARENT; public: void* run(){ PARENT::analyse(); return PARENT::run(); } }; } //namespace xreate #endif diff --git a/cpp/tests/CMakeLists.txt b/cpp/tests/CMakeLists.txt index ee87e1a..a178bcc 100644 --- a/cpp/tests/CMakeLists.txt +++ b/cpp/tests/CMakeLists.txt @@ -1,57 +1,58 @@ 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) set(TEST_FILES + transcend-ast.cpp supplemental/docutils latetranscend.cpp cfa.cpp latex.cpp polymorph.cpp transcend.cpp virtualization.cpp exploitation.cpp effects-communication.cpp association.cpp main.cpp modules.cpp attachments.cpp ast.cpp dfa.cpp compilation.cpp ExpressionSerializer.cpp externc.cpp types.cpp #vendorsAPI/clangAPI.cpp - vendorsAPI/xml2.cpp + #vendorsAPI/xml2.cpp #vendorsAPI/json.cpp containers.cpp interpretation.cpp loops.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/ast.cpp b/cpp/tests/ast.cpp index ab020ca..2c5ce06 100644 --- a/cpp/tests/ast.cpp +++ b/cpp/tests/ast.cpp @@ -1,205 +1,204 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * ast.cpp * * Created on: Jun 11, 2015 * Author: pgess */ #include "supplemental/docutils.h" #include "xreatemanager.h" #include "main/Parser.h" #include "gtest/gtest.h" using namespace std; using namespace xreate; using namespace xreate::grammar::main; TEST(AST, Containers1) { FILE* input = fopen("scripts/containers/Containers_Implementation_LinkedList1.xreate", "r"); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); assert(!parser.errors->count && "Parser errors"); fclose(input); } TEST(AST, InterfacesDataCFA) { XreateManager* man = XreateManager::prepare ("interface(cfa){\n" " operator map :: annotation1.\n" "}"); auto answer = man->root->__interfacesData.equal_range(CFA); EXPECT_EQ(1, std::distance(answer.first, answer.second)); Expression&& scheme = move(answer.first->second); EXPECT_EQ(Operator::MAP, scheme.op); EXPECT_EQ("annotation1", scheme.getOperands().at(0).getValueString()); } TEST(AST, syntax_recognizeIdentifiers) { XreateManager* man = XreateManager::prepare(R"Code( test= function(a:: num):: num; entry { a = b:: int. b = 8:: int. a } )Code"); } TEST(AST, syntax_operatorIndex) { XreateManager* man = XreateManager::prepare(R"Code( test= function(a:: num):: num; entry { b = a[1]. b } )Code"); } TEST(AST, Variants_switch) { XreateManager* man = XreateManager::prepare(R"Code( Color = type variant{Blue, White, Green}. main = function:: int { x = White()::Color. switch variant(x)::int case (Green) {0} case (White) {1} case (Blue){2} } )Code"); Expression e = man->root->findFunction("main")->getEntryScope()->getBody(); ASSERT_EQ(4, e.getOperands().size()); ASSERT_EQ(3, e.blocks.size()); } TEST(AST, DISABLED_InterfacesDataDFA) { } TEST(AST, DISABLED_InterfacesDataExtern) { } TEST(AST, Doc_LiteralsAndExpressions) { XreateManager* man = XreateManager::prepare( R"Code( Record1 = type {year:: int, month:: string}. isOdd = function(x :: int) :: bool {true} test = function:: bool; entry { x1 = 5 :: int. x2 = "Nimefurahi kukujua":: string. x3 = {year = 1934, month = "april"}:: Record1. x4 = {16, 8, 3} :: [int]. x5 = 8>=3:: bool. x6 = "Blue" <> "Green" :: bool. colors = {"Green", "Blue"} :: [string]. color = colors[0] :: string. date = {year = 1934, month = "april"}:: Record1. year = date["year"] :: int. a = 0::int. b = 0 :: int. x7 = a - b:: int. result = isOdd(6) :: bool. true } )Code"); ASSERT_TRUE(true); } TEST(AST, Doc_CodeBlocks1) { XreateManager* man = XreateManager::prepare( getDocumentationExampleById("documentation/Syntax/syntax.xml", "CodeBlocks1")); ASSERT_TRUE(true); } TEST(AST, Doc_Functions1) { XreateManager* man = XreateManager::prepare( getDocumentationExampleById("documentation/Syntax/syntax.xml", "Functions1")); ASSERT_TRUE(true); } TEST(AST, Doc_FunctionSpecializations1) { XreateManager* man = XreateManager::prepare( getDocumentationExampleById("documentation/Syntax/syntax.xml", "FunctionSpecialization1")); ASSERT_TRUE(true); } TEST(AST, Doc_BranchStatements) { string code_IfStatement1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "IfStatement1"); string code_SwitchStatement1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "SwitchStatement1"); string code = R"Code( test = function:: int; entry { question = "Favorite color?":: string. monthNum = 2:: int. %IfStatement1 %SwitchStatement1 monthName } )Code"; replace(code, "%IfStatement1", code_IfStatement1); replace(code, "%SwitchStatement1", code_SwitchStatement1); XreateManager* man = XreateManager::prepare(move(code)); ASSERT_TRUE(true); } TEST(AST, Doc_LoopStatements) { string code_LoopStatement1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "LoopStatement1"); string code_LoopStatement2 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "LoopStatement2"); string code_FoldStatement1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "FoldStatement1"); string code_MapStatement1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "MapStatement1"); string code = R"Code( test = function:: int; entry { %LoopStatement1 %LoopStatement2 %FoldStatement1 %MapStatement1 min } )Code"; replace(code, "%LoopStatement1", code_LoopStatement1); replace(code, "%LoopStatement2", code_LoopStatement2); replace(code, "%FoldStatement1", code_FoldStatement1); replace(code, "%MapStatement1", code_MapStatement1); - replace(code, "COUNTEREXAMPLE", ""); XreateManager::prepare(move(code)); ASSERT_TRUE(true); } TEST(AST, Doc_Types){ string code = getDocumentationExampleById("documentation/Syntax/syntax.xml", "Types1"); XreateManager::prepare(move(code)); ASSERT_TRUE(true); } TEST(AST, Doc_Variants){ string code_Variants1 = getDocumentationExampleById("documentation/Syntax/syntax.xml", "Variants1"); XreateManager::prepare(move(code_Variants1)); ASSERT_TRUE(true); } \ No newline at end of file diff --git a/cpp/tests/cfa.cpp b/cpp/tests/cfa.cpp index 472e186..b15a9e1 100644 --- a/cpp/tests/cfa.cpp +++ b/cpp/tests/cfa.cpp @@ -1,223 +1,193 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * cfa.cpp * * Created on: Jul 17, 2015 * Author: pgess */ #include "xreatemanager.h" #include "pass/dfapass.h" #include "pass/cfapass.h" -#include "analysis/DominatorsAnalysisProvider.h" #include "analysis/cfagraph.h" +#include "pass/cfatemporalseqpass.h" +#include "analysis/temporalseqgraph.h" #include "pass/compilepass.h" #include "compilation/scopedecorators.h" #include "gtest/gtest.h" #include "aux/xreatemanager-decorators.h" #include #include #include using namespace xreate; using namespace xreate::cfa; using namespace std; TEST(CFA, testFunctionAnnotations) { - string&& program = - "f2 = function::int; annotationF2 {\n" - " 0\n" - "}\n" - "\n" - "f1 = function:: int; entry; annotationF1 {\n" - " f2() + 10\n" - "}"; + string&& program = + "f2 = function::int; annotationF2 {\n" + " 0\n" + "}\n" + "\n" + "f1 = function:: int; entry; annotationF1 {\n" + " f2() + 10\n" + "}"; - details::tier1::XreateManager* man = details::tier1::XreateManager::prepare(move(program)); - man->analyse(); + details::tier1::XreateManager* man = details::tier1::XreateManager::prepare(move(program)); + man->analyse(); - StaticModel answer = man->transcend->query("annotationF1"); - EXPECT_EQ(1, answer.size()); + StaticModel answer = man->transcend->query("annotationF1"); + EXPECT_EQ(1, answer.size()); - answer = man->transcend->query("annotationF2"); - EXPECT_EQ(1, answer.size()); + answer = man->transcend->query("annotationF2"); + EXPECT_EQ(1, answer.size()); } TEST(CFA, testLoopContextExists) { - details::tier1::XreateManager* man = details::tier1::XreateManager::prepare ( - "interface(cfa){\n" - " operator fold:: annotation1.\n" - "}\n" - "\n" - "main = function:: int; entry {\n" - " x = [1..10]:: [int].\n" - " sum = loop fold (x->el:: int, 0->sum):: int {\n" - " el + sum + f1()\n" - " }. \n" - " sum\n" - "}" - "guard:: annotation1 {" - " f1 = function::int {\n" - " x = 0:: int. " - " x\n" - " }" - "}" - ); - - man->analyse(); - StaticModel model = man->transcend->query("annotation1"); - ScopePacked scopeIdActual = std::get<0>(TranscendLayer::parse(model.begin()->second)); - - CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); - const Expression& exprSum = scopeEntry->getDefinition(scopeEntry->getSymbol("sum")); - CodeScope* scopeExpected = exprSum.blocks.front(); - - ScopePacked scopeIdExpected = man->transcend->pack(scopeExpected); - ASSERT_EQ(scopeIdExpected, scopeIdActual); + details::tier1::XreateManager* man = details::tier1::XreateManager::prepare ( + "interface(cfa){\n" + " operator fold:: annotation1.\n" + "}\n" + "\n" + "main = function:: int; entry {\n" + " x = [1..10]:: [int].\n" + " sum = loop fold (x->el:: int, 0->sum):: int {\n" + " el + sum + f1()\n" + " }. \n" + " sum\n" + "}" + "guard:: annotation1 {" + " f1 = function::int {\n" + " x = 0:: int. " + " x\n" + " }" + "}" + ); + + man->analyse(); + StaticModel model = man->transcend->query("annotation1"); + ScopePacked scopeIdActual = std::get<0>(TranscendLayer::parse(model.begin()->second)); + + CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); + const Expression& exprSum = scopeEntry->getDefinition(scopeEntry->getSymbol("sum")); + CodeScope* scopeExpected = exprSum.blocks.front(); + + ScopePacked scopeIdExpected = man->transcend->pack(scopeExpected); + ASSERT_EQ(scopeIdExpected, scopeIdActual); } -TEST(CFA, DependenciesFnCall) { - details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( - R"Code( - a = function::int{ - seq - {x = 0:: int. x} - {x = b():: int. x}::int - } - - b = function::int {y = 0. y} - )Code"); - - CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); - CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); - CodeScope* scopeB = man->root->findFunction("b")->getEntryScope(); - - ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); - ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); - ScopePacked psB = man->transcend->pack(scopeB); - - CFAPass* pass = new CFAPass(man); - - man->registerPass(pass, PassId::CFAPass); - man->executePasses(); - const CFAGraph* report = dynamic_cast (man->getPassById(PassId::CFAPass))->getReport(); - auto dependencies = report->__dependencyRelations; - delete pass; +TEST(CFA, TemporalFnCall) { + details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( + R"Code( + a = function::int{ + seq + {x = b():: int. x} + {x = 0 :: int. x}::int + } - ASSERT_EQ(1, dependencies.count(psSeq2)); - ASSERT_EQ(1, dependencies.count(psB)); + b = function::int {y = 0. y} +)Code"); + + CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); + CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); + CodeScope* scopeB = man->root->findFunction("b")->getEntryScope(); + CodeScope* scopeA = man->root->findFunction("a")->getEntryScope(); + + ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); + ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); + ScopePacked psB = man->transcend->pack(scopeB); + ScopePacked psA = man->transcend->pack(scopeA); + + CFATemporalSeqPass* pass = new CFATemporalSeqPass(man); + man->registerPass(pass, PassId::CFATemporalSeqPass); + man->executePasses(); + + const TemporalSeqGraph* report = dynamic_cast ( + man->getPassById(PassId::CFATemporalSeqPass))->getReport(); + delete pass; + + std::ostringstream output; + report->print(output); + cout << output.str() << endl; + ASSERT_TRUE(report->isOrdered(psSeq2, psSeq1)); + //ASSERT_TRUE(report->isOrdered(psSeq2, psB)); + ASSERT_FALSE(report->isOrdered(psSeq1, psA)); } -TEST(CFA, DependenciesChildScope) { - details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( - R"Code( +TEST(CFA, TemporalChildScope) { + details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( + R"Code( a = function::int{ seq {x = 0:: int. x} {x=0::int. if(x>0)::int{1} else {0}}::int } )Code"); - CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); - CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); - CodeScope* scopeIf1 = scopeSeq2->getBody().blocks.front(); - CodeScope* scopeIf2 = *(++scopeSeq2->getBody().blocks.begin()); - - ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); - ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); - ScopePacked psIf1 = man->transcend->pack(scopeIf1); - ScopePacked psIf2 = man->transcend->pack(scopeIf2); - - CFAPass* pass = new CFAPass(man); - - man->registerPass(pass, PassId::CFAPass); - man->executePasses(); - const CFAGraph* report = dynamic_cast (man->getPassById(PassId::CFAPass))->getReport(); - auto dependencies = report->__dependencyRelations; - delete pass; - - ASSERT_EQ(0, dependencies.count(psSeq1)); - ASSERT_EQ(1, dependencies.count(psSeq2)); - ASSERT_EQ(1, dependencies.count(psIf1)); - ASSERT_EQ(1, dependencies.count(psIf2)); - - for(auto rec : dependencies) { - std::cout << rec.first << " " << rec.second << std::endl; - } -} - -TEST(CFA, Dominators1){ - std::multimap dataScopes = { - {1, 0}, {2, 0}, {3, 1}, {4, 1}, {4, 2} - }; - - dominators::DominatorsAnalysisProvider domProvider; - boost::scoped_ptr adapter(dominators::CFAGraphAdapter::build(dataScopes)); - domProvider.run(adapter.get()); - - dominators::DominatorsAnalysisProvider::Dominators expectedFDom= { - {0, {0, 9}} - ,{1, {1, 4}} - ,{2, {7, 8}} - ,{3, {2, 3}} - ,{4, {5, 6}} - }; - - dominators::DominatorsAnalysisProvider::Dominators expectedPostDom= { - {0, {5, 6}} - ,{1, {3, 4}} - ,{2, {8, 9}} - ,{3, {1, 2}} - ,{4, {7, 10}} - }; - - ASSERT_EQ(expectedFDom, domProvider.getForwardDominators()); - ASSERT_EQ(expectedPostDom, domProvider.getPostDominators()); + CodeScope* scopeSeq1 = man->root->findFunction("a")->getEntryScope()->getBody().blocks.front(); + CodeScope* scopeSeq2 = *(++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); + CodeScope* scopeIf1 = scopeSeq2->getBody().blocks.front(); + CodeScope* scopeIf2 = *(++scopeSeq2->getBody().blocks.begin()); + + ScopePacked psSeq1 = man->transcend->pack(scopeSeq1); + ScopePacked psSeq2 = man->transcend->pack(scopeSeq2); + ScopePacked psIf1 = man->transcend->pack(scopeIf1); + ScopePacked psIf2 = man->transcend->pack(scopeIf2); + + CFATemporalSeqPass* pass = new CFATemporalSeqPass(man); + man->registerPass(pass, PassId::CFATemporalSeqPass); + man->executePasses(); + const TemporalSeqGraph* report = dynamic_cast ( + man->getPassById(PassId::CFATemporalSeqPass))->getReport(); + delete pass; + + std::ostringstream output; + report->print(output); + cout << output.str() << endl; + + ASSERT_TRUE(report->isOrdered(psSeq2, psSeq1)); + ASSERT_TRUE(report->isOrdered(psIf1, psSeq1)); + ASSERT_TRUE(report->isOrdered(psIf2, psSeq1)); + ASSERT_FALSE(report->isOrdered(psIf2, psSeq2)); } -TEST(CFA, Dominators2) { - std::string program = - R"CODE( - a = function:: int; entry{ - seq - {x = 0:: int. x} - {x = 1:: int. x}::int - } -)CODE"; - - std::unique_ptr man(details::tier2::XreateManager::prepare(move(program))); - - CFAPass* pass = new CFAPass(man.get()); - man->registerPass(pass, PassId::CFAPass); - pass->run(); - - ScopePacked scope1 = man->transcend->pack(man->root->findFunction("a")->getEntryScope()->getBody().blocks.front()); - ScopePacked scope2 = man->transcend->pack(*++man->root->findFunction("a")->getEntryScope()->getBody().blocks.begin()); - - dominators::DominatorsAnalysisProvider* providerDomAnalysis = new dominators::DominatorsAnalysisProvider(); - boost::scoped_ptr adapter(dominators::CFAGraphAdapter::build(pass->getReport())); - providerDomAnalysis->run(adapter.get()); - - dominators::DominatorsAnalysisProvider::Dominators expectedFDom = { - {1, {0, 3}}, - {2, {1, 2}} - }; - - dominators::DominatorsAnalysisProvider::Dominators expectedPostDom = { - {2, {1, 4}}, - {1, {2, 3}} - }; - - auto actualFDom = providerDomAnalysis->getForwardDominators(); - auto actualPostDom = providerDomAnalysis->getPostDominators(); - - ASSERT_EQ(expectedFDom, actualFDom); - ASSERT_EQ(expectedPostDom, actualPostDom); +TEST(CFA, Temporal_Payload_PathCollapse_1){ + details::tier2::XreateManager* man = details::tier2::XreateManager::prepare( + R"Code( + import raw("scripts/cfa/payload.lp"). + b = function::int {d()} + c = function::int {d()} + d = function::int {0} + a = function:: int { + seq {context:: test. 0} {b() + c()} + } + )Code"); - delete providerDomAnalysis; - delete pass; -} + string script = + R"Code( + cfa_payload(P, scope(Scope), ()):- + bind_scope(Scope, P, strong). + )Code"; + + CFATemporalSeqPass* pass = new CFATemporalSeqPass(man); + man->registerPass(pass, PassId::CFATemporalSeqPass); + man->registerPass(new CFAPass(man), PassId::CFAPass); + man->executePasses(); + const TemporalSeqGraph* report = dynamic_cast ( + man->getPassById(PassId::CFATemporalSeqPass))->getReport(); + + man->transcend->addRawScript(move(script)); + testing::internal::CaptureStdout(); + man->analyse(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + + string outputExpected = "cfa_payload(test,scope(2),())"; + ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); + delete pass; +} \ No newline at end of file diff --git a/cpp/tests/exploitation.cpp b/cpp/tests/exploitation.cpp index 9ac2d1d..217f1a4 100644 --- a/cpp/tests/exploitation.cpp +++ b/cpp/tests/exploitation.cpp @@ -1,25 +1,38 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * exploitation.cpp * * Author: pgess * Created on February 15, 2018, 6:17 PM */ #include "xreatemanager.h" +#include "analysis/cfagraph.h" +#include "pass/cfapass.h" +#include "pass/cfatemporalseqpass.h" +#include "supplemental/docutils.h" + #include "gtest/gtest.h" using namespace xreate; +using namespace xreate::cfa; +using namespace std; -TEST(Exploitation, test1){ - FILE* input = fopen("scripts/exploitation/test1.xreate","r"); - assert(input != nullptr); +TEST(Exploitation, Doc_ResourceInit_1) { + string example = getDocumentationExampleFromFile("scripts/exploitation/test1.xreate"); + string body = getDocumentationExampleById("documentation/exploitation.xml", "ResourceInit_1"); + replace(example, "", body); - std::unique_ptr man(XreateManager::prepare(input)); + details::tier1::XreateManager* man = details::tier1::XreateManager::prepare(move(example)); + CFATemporalSeqPass* pass = new CFATemporalSeqPass(man); + man->registerPass(pass, PassId::CFATemporalSeqPass); + man->analyse(); - int (*main)() = (int (*)())man->run(); - int result = main(); + int (* main)() = (int (*)()) man->run(); + int result = main(); + delete pass; + delete man; - ASSERT_EQ(1, result); + ASSERT_EQ(1, result); } \ No newline at end of file diff --git a/cpp/tests/interpretation.cpp b/cpp/tests/interpretation.cpp index a032b19..4609b15 100644 --- a/cpp/tests/interpretation.cpp +++ b/cpp/tests/interpretation.cpp @@ -1,568 +1,485 @@ /* 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 "analysis/interpretation.h" +#include "supplemental/docutils.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; +using namespace std; -TEST(Interpretation, Analysis_StatementIF_1){ - XreateManager* man = XreateManager::prepare( +TEST(Interpretation, Analysis_StatementIF_1) { + XreateManager* man = XreateManager::prepare( -R"Code( + R"Code( main = function::bool { x = "a":: string. y = if (x=="b"):: bool; i12n(on) { 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, Doc_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; i12n(on) - {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(); - } +)Code"); + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); - int (*main)() = (int (*)())man->run(); - int result = main(); + CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); + Symbol symbolY{scopeEntry->getSymbol("y"), scopeEntry}; + InterpretationData &dataSymbolY = Attachments::get(symbolY); - ASSERT_EQ(0, result); + ASSERT_EQ(INTR_ONLY, dataSymbolY.resolution); } -TEST(Interpretation, Analysis_StatementIF_InterpretCondition_1){ - XreateManager* man = XreateManager::prepare( +TEST(Interpretation, Analysis_StatementIF_InterpretCondition_1) { + XreateManager* man = XreateManager::prepare( -R"Code( + R"Code( main = function(x:: int):: int { comm= "inc":: string; i12n(on). 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, Doc_Compilation_StatementIF_InterpretCondition_1){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( - -R"Code( - test = function(x:: int):: int; entry { - comm= "inc":: string; i12n(on). - - 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, Doc_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]; i12n(on). - - 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, Doc_StatementCall_RecursionNo_1){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( - unwrap = function(data::unknType, keys::unknType):: unknType; i12n(on) - { - loop fold(keys->key::string, data->record):: unknType - { - record[key] - } - } - - test = function:: bool; entry - { - book = unwrap({ - Library = { - Shelf = { - Book = "Aristotle's Politics" - }}}, {"Library", "Shelf", "Book"}):: unknType. - - book == "Aristotle's Politics" - } -)Code" ); - - man->analyse(); - - InterpretationPass* pass; - if (man->isPassRegistered(PassId::InterpretationPass)){ - pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); - } else { - pass = new InterpretationPass(man); - pass->run(); - } - - unsigned char (*main)() = (unsigned char (*)())man->run(); - unsigned char result = main(); - - ASSERT_EQ(1, result); -} - -TEST(Interpretation, Doc_StatementCall_RecursionNo_2){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( - unwrap = function(data::unknType, keys::unknType):: unknType - { - loop fold(keys->key::string, data->record):: unknType - { - record[key] - } - } - - test = function:: bool; entry - { - book = unwrap({ - Library = { - Shelf = { - Book = "Aristotle's Politics" - }}}, {"Library", "Shelf", "Book"}):: unknType; i12n(on). - - book == "Aristotle's Politics" - } -)Code" ); - - man->analyse(); +)Code"); - InterpretationPass* pass; - if (man->isPassRegistered(PassId::InterpretationPass)){ - pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); - } else { - pass = new InterpretationPass(man); - pass->run(); - } + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); - unsigned char (*main)() = (unsigned char (*)())man->run(); - unsigned char result = main(); + CodeScope* scopeEntry = man->root->findFunction("main")->getEntryScope(); + Symbol symbolY{scopeEntry->getSymbol("y"), scopeEntry}; + InterpretationData &dataSymbolY = Attachments::get(symbolY); - ASSERT_EQ(1, result); + ASSERT_EQ(CMPL_ONLY, dataSymbolY.resolution); + ASSERT_EQ(IF_INTERPRET_CONDITION, dataSymbolY.op); } -TEST(Interpretation, Doc_StatementCall_RecursionDirect_1){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( - unwrap = function(data:: X):: bool - { - if (data[0] == "the-end"):: bool - {true} else {unwrap(data[0])} - } - - entry = function:: bool; entry { - unwrap({{{{"the-end"}}}}):: bool; i12n(on) - } -)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); - - unsigned char (*main)() = (unsigned char (*)())man->run(); - unsigned char result = main(); - - ASSERT_NE(0, result); -} - -TEST(Interpretation, StatementCall_RecursionIndirect_1){ - XreateManager* man = XreateManager::prepare( -R"Code( +TEST(Interpretation, StatementCall_RecursionIndirect_1) { + XreateManager* man = XreateManager::prepare( + R"Code( searchNemo = function(data:: Data):: bool { if (data == "nemo"):: bool {false} else {searchDory(data)} } searchDory = function(data:: Data):: bool { if (data == "dory"):: bool {true} else {searchNemo(data)} } entry = function:: bool; entry { searchNemo(""):: bool; i12n(on) } -)Code" ); +)Code"); - InterpretationPass* pass = new InterpretationPass(man); - ASSERT_DEATH(pass->run(), "Indirect recursion detected"); + InterpretationPass* pass = new InterpretationPass(man); + ASSERT_DEATH(pass->run(), "Indirect recursion detected"); } -TEST(Interpretation, PartialIntr_1){ - XreateManager* man = XreateManager::prepare( -R"Code( +TEST(Interpretation, PartialIntr_1) { + XreateManager* man = XreateManager::prepare( + R"Code( evaluate= function(argument:: num, code:: string; i12n(on)):: num { switch(code):: num case ("inc") {argument + 1} case ("dec") {argument - 1} case ("double") {argument * 2} case default {argument} } main = function:: int; entry { commands= {"inc", "double", "dec"}:: [string]; i12n(on). 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, Doc_Compilation_PartialIntr_2){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( -evaluate= function(argument:: num, code:: string; i12n(on)):: num { - switch(code):: num - case ("inc") {argument + 1} - case ("dec") {argument - 1} - case ("double") {argument * 2} - case default {argument} -} - -main = function(init::int):: int; entry { - commands= {"inc", "double", "dec"}:: [string]; i12n(on). - - loop fold(commands->comm::string, init->operand):: int - { - evaluate(operand, comm) - } -} -)Code" ); +)Code"); - man->analyse(); - if (!man->isPassRegistered(PassId::InterpretationPass)){ - InterpretationPass* pass = new InterpretationPass(man); - pass->run(); - } + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); - int (*main)(int) = (int (*)(int))man->run(); - int result = main(10); + ManagedFnPtr fnEvaluate = man->root->findFunction("evaluate"); + InterpretationResolution resFnEvaluate = pass->process(fnEvaluate); + ASSERT_EQ(CMPL_ONLY, resFnEvaluate); + ASSERT_TRUE(FunctionInterpretationHelper::needPartialInterpretation(fnEvaluate)); - ASSERT_EQ(21, result); + 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, PartialIntr_3){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( +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; i12n(on)):: 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]; i12n(on). loop fold(commands->comm::Command, 10->operand):: int{ evaluate(operand, comm) } } -)Code" ); +)Code"); - man->analyse(); - if (!man->isPassRegistered(PassId::InterpretationPass)){ - InterpretationPass* pass = new InterpretationPass(man); - pass->run(); - } + man->analyse(); + if(!man->isPassRegistered(PassId::InterpretationPass)) { + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); + } - int (*main)() = (int (*)())man->run(); - int result = main(); + int (* main)() = (int (*)()) man->run(); + int result = main(); - ASSERT_EQ(21, result); + ASSERT_EQ(21, result); } -TEST(Interpretation, PartialIntr_4){ - xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( -R"Code( +TEST(Interpretation, PartialIntr_4) { + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare( + R"Code( Command= type variant {INC, DEC, DOUBLE}. evaluate= function(argument:: num, code:: Command; i12n(on)):: num { switch variant(code)::num case (INC) {argument + 1} case (DEC) {argument - 1} case (DOUBLE) {argument * 2} } main = function::int; entry { evaluate(4, DEC()) } -)Code" ); +)Code"); - man->analyse(); - if (!man->isPassRegistered(PassId::InterpretationPass)){ - InterpretationPass* pass = new InterpretationPass(man); - pass->run(); - } + man->analyse(); + if(!man->isPassRegistered(PassId::InterpretationPass)) { + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); + } - int (*main)() = (int (*)())man->run(); - int result = main(); + int (* main)() = (int (*)()) man->run(); + int result = main(); - ASSERT_EQ(3, result); + ASSERT_EQ(3, result); } -TEST(Interpretation, SwitchVariant){ - xreate::XreateManager* man = xreate::XreateManager::prepare( -R"Code( +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; i12n(on). switch variant(program)::int case (ADD) {program["x"]+program["y"]} case (DEC) {1} case (DOUBLE) {2} } -)Code" ); +)Code"); - int (*main)() = (int (*)())man->run(); - int result = main(); - ASSERT_EQ(5, result); + int (* main)() = (int (*)()) man->run(); + int result = main(); + ASSERT_EQ(5, result); } -TEST(Interpretation, SwitchVariantAlias){ - xreate::XreateManager* man = xreate::XreateManager::prepare( -R"Code( +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]; i12n(on). switch variant(program[0]->program::Command)::int case (ADD) {program["x"]+program["y"]} case (DEC) {1} case (DOUBLE) {2} } -)Code" ); +)Code"); - int (*main)() = (int (*)())man->run(); - int result = main(); - ASSERT_EQ(5, result); + int (* main)() = (int (*)()) man->run(); + int result = main(); + ASSERT_EQ(5, result); } -TEST(Interpretation, Multiindex1){ - std::string script2= -R"Code( +TEST(Interpretation, Multiindex1) { + std::string script2 = + R"Code( extract = function(program::unknType)::int; i12n(on){ program["arguments"][1] } main = function::int; entry { x = {arguments = {10, 9, 8, 7}}:: unknType; i12n(on). extract(x) } )Code"; - std::unique_ptr man(XreateManager::prepare(std::move(script2))); + std::unique_ptr man(XreateManager::prepare(std::move(script2))); - int (*main)() = (int (*)())man->run(); - int result = main(); + int (* main)() = (int (*)()) man->run(); + int result = main(); - ASSERT_EQ(9, result); + ASSERT_EQ(9, result); } -TEST(InterpretationExamples, Regexp1){ - FILE* input = fopen("scripts/dsl/regexp.xreate","r"); - assert(input != nullptr); +TEST(InterpretationExamples, Regexp1) { + FILE* input = fopen("scripts/dsl/regexp.xreate", "r"); + assert(input != nullptr); - std::unique_ptr man(XreateManager::prepare(input)); + std::unique_ptr man(XreateManager::prepare(input)); - int (*main)() = (int (*)())man->run(); - int result = main(); + int (* main)() = (int (*)()) man->run(); + int result = main(); - ASSERT_EQ(4, result); + ASSERT_EQ(4, result); } -TEST(Interpretation, Variant1){ - std::string script= -R"Code( +TEST(Interpretation, Variant1) { + std::string script = + R"Code( Data = type {Num:: [int], String::string}. DataPacked = type variant { Var1:: Data, Var2:: Data }. extractInt = function(data::DataPacked):: int { resultWrong = 0 :: int. switch variant(data)::int case (Var1) {data["Num", 0]} case (Var2) {resultWrong} } main = function :: int; entry { dataActual = 10. dataPacked = Var1({Num = {dataActual}, String = "whatever"}):: DataPacked. extractInt(dataPacked):: int; i12n(on) } )Code"; - std::unique_ptr man(XreateManager::prepare(std::move(script))); + std::unique_ptr man(XreateManager::prepare(std::move(script))); + + int (* main)() = (int (*)()) man->run(); + int result = main(); + + ASSERT_EQ(10, result); +} + +TEST(Interpretation, Doc_Intr_1) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "Intr_1"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + 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, Doc_FnIntr_1) { + string example1 = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "FnIntr_1"); + string example2 = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "Alt_FnIntr_1"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example1)); + + man->analyse(); + + InterpretationPass* pass; + if(man->isPassRegistered(PassId::InterpretationPass)) { + pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); + } else { + pass = new InterpretationPass(man); + pass->run(); + } + + unsigned char (* main)() = (unsigned char (*)()) man->run(); + unsigned char result = main(); + + ASSERT_EQ(1, result); + + XreateManager* man2 = XreateManager::prepare(move(example2)); + ASSERT_TRUE(true); +} + +TEST(Interpretation, Doc_FnIntr_2) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "FnIntr_2"); + + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + man->analyse(); + + InterpretationPass* pass; + if(man->isPassRegistered(PassId::InterpretationPass)) { + pass = (InterpretationPass*) man->getPassById(PassId::InterpretationPass); + } else { + pass = new InterpretationPass(man); + pass->run(); + } + + unsigned char (* main)() = (unsigned char (*)()) man->run(); + unsigned char result = main(); + + ASSERT_EQ(1, result); +} + +TEST(Interpretation, Doc_FnIntr_3) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "FnIntr_3"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + 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); + + unsigned char (* main)() = (unsigned char (*)()) man->run(); + unsigned char result = main(); + + ASSERT_NE(0, result); +} + +TEST(Interpretation, Doc_LateIntr_1) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "LateIntr_1"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + 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, Doc_LateIntr_2) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "LateIntr_2"); + string example2 = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "Alt_LateIntr_2"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + 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); + + XreateManager* man2 = XreateManager::prepare(move(example2)); + ASSERT_TRUE(true); +} + +TEST(Interpretation, Doc_LateFnIntr_1) { + string example = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "LateFnIntr_1"); + string example2 = getDocumentationExampleById("documentation/Concepts/interpretation.xml", "Alt_LateFnIntr_1"); + xreate::details::tier1::XreateManager* man = xreate::details::tier1::XreateManager::prepare(move(example)); + + man->analyse(); + if(!man->isPassRegistered(PassId::InterpretationPass)) { + InterpretationPass* pass = new InterpretationPass(man); + pass->run(); + } + + int (* main)(int) = (int (*)(int)) man->run(); + int result = main(10); - int (*main)() = (int (*)())man->run(); - int result = main(); + ASSERT_EQ(21, result); - ASSERT_EQ(10, result); + XreateManager* man2 = XreateManager::prepare(move(example2)); + ASSERT_TRUE(true); } //TOTEST call indirect recursion(w/o tags) //TASk implement and test Loop Inf (fix acc types in coco grammar) diff --git a/cpp/tests/latetranscend.cpp b/cpp/tests/latetranscend.cpp index 51d3666..0c02ef8 100644 --- a/cpp/tests/latetranscend.cpp +++ b/cpp/tests/latetranscend.cpp @@ -1,208 +1,122 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * latereasoning.cpp * * Author: pgess * Created on April 21, 2018, 5:10 PM */ #include "xreatemanager.h" #include "transcendlayer.h" #include "pass/latereasoningpass.h" #include "aux/latereasoning.h" -#include "pass/dfapass.h" -#include +#include "supplemental/docutils.h" #include "gtest/gtest.h" using namespace std; using namespace xreate; using namespace xreate::latereasoning; TEST(LateReasoning, Syntax1) { - XreateManager* man = XreateManager::prepare(R"Code( + XreateManager* man = XreateManager::prepare(R"Code( test = function:: int { x = 0::int. y1= switch late (x)::int{0}. y2= switch late(x+y1->a::int)::int{1}. y1+y2 } )Code"); - CodeScope* scope = man->root->findFunction("test")->getEntryScope(); - Expression y1 = scope->getDefinition(scope->getSymbol("y1")); - Expression y2 = scope->getDefinition(scope->getSymbol("y2")); + CodeScope* scope = man->root->findFunction("test")->getEntryScope(); + Expression y1 = scope->getDefinition(scope->getSymbol("y1")); + Expression y2 = scope->getDefinition(scope->getSymbol("y2")); - ASSERT_EQ(1, y1.bindings.size()); - ASSERT_STRCASEEQ("x", y1.bindings.at(0).c_str()); + ASSERT_EQ(1, y1.bindings.size()); + ASSERT_STRCASEEQ("x", y1.bindings.at(0).c_str()); - ASSERT_EQ(1, y2.bindings.size()); - ASSERT_STRCASEEQ("a", y2.bindings.at(0).c_str()); + ASSERT_EQ(1, y2.bindings.size()); + ASSERT_STRCASEEQ("a", y2.bindings.at(0).c_str()); } -TEST(LateReasoning, Pass_DFAPassDec_1){ - typedef LateReasoningTranscendDecorator LRTranscend; +TEST(LateReasoning, Pass_DFAPassDec_1) { + typedef LateReasoningTranscendDecorator LRTranscend; - auto man = details::tier2::XreateManager::prepare(R"Code( + auto man = details::tier2::XreateManager::prepare(R"Code( Dom = type slave dom. test = function:: int; entry { LateIdent = 0:: Dom. 0:: int; ann1(LateIdent) } )Code"); - CodeScope* scopeEntry = man->root->findFunction("test")->getEntryScope(); - ScopedSymbol keyS = scopeEntry->getSymbol("LateIdent"); - SymbolPacked keySP = man->transcend->pack(Symbol{keyS, scopeEntry}); - - std::shared_ptr scopeLateEntry(new LateReasoningScope(nullptr)); - scopeLateEntry->addIdentifier("LateIdent", keySP); - - typedef LateReasoningDFAPassDecorator LRDFAPass; - LRDFAPass* dfaPass = new LRDFAPass(man); - dfaPass->registerLateScope(scopeEntry, scopeLateEntry.get()); - - man->transcend->addRawScript("dom(guard1; guard2).\n"); - - man->registerPass(dfaPass, PassId::DFAPass, nullptr); - man->executePasses(); - - testing::internal::CaptureStdout(); - man->analyse(); - std::string outputActual = testing::internal::GetCapturedStdout(); - cout << outputActual << endl; - - string outputExpected = "late(s(0,-2,0), (s(1,-2,0)), (LateIdent), ann1(LateIdent)):- dom(LateIdent)."; - ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); + CodeScope* scopeEntry = man->root->findFunction("test")->getEntryScope(); + ScopedSymbol keyS = scopeEntry->getSymbol("LateIdent"); + SymbolPacked keySP = man->transcend->pack(Symbol{keyS, scopeEntry}); + + std::shared_ptr scopeLateEntry(new LateReasoningScope(nullptr)); + scopeLateEntry->addIdentifier("LateIdent", keySP); + + typedef LateReasoningDFAPassDecorator LRDFAPass; + LRDFAPass* dfaPass = new LRDFAPass(man); + dfaPass->registerLateScope(scopeEntry, scopeLateEntry.get()); + + man->transcend->addRawScript("dom(guard1; guard2).\n"); + + man->registerPass(dfaPass, PassId::DFAPass, nullptr); + man->executePasses(); + + testing::internal::CaptureStdout(); + man->analyse(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + + string outputExpected = "late(s(0,-2,0), (s(1,-2,0)), (LateIdent), ann1(LateIdent)):- dom(LateIdent)."; + ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); } -//TEST(LateReasoning, Transcend_LRTransDec_1) { -// Attachments::init(); -// typedef LateReasoningTranscendDecorator LRTranscend; -// std::unique_ptr transcend(new LRTranscend()); - -// std::unique_ptr scope(new CodeScope(nullptr)); -// Symbol symbA = scope->addDefinition(Atom("a"), Expression()); -// Symbol symbB = scope->addDefinition(Atom("b"), Expression()); -// Symbol symbC = scope->addDefinition(Atom("c"), Expression()); -// Symbol symbTarget1 = scope->addDefinition(Atom("target1"), Expression()); -// Symbol symbTarget2 = scope->addDefinition(Atom("target2"), Expression()); - -// SymbolPacked symbpA = transcend->pack(symbA, "a"); -// SymbolPacked symbpB = transcend->pack(symbB, "b"); -// SymbolPacked symbpC = transcend->pack(symbC, "c"); -// SymbolPacked symbTarget1P = transcend->pack(symbTarget1, "target1"); -// SymbolPacked symbTarget2P = transcend->pack(symbTarget2, "target2"); - -// boost::format formatSymb("s(%1%,%2%,%3%)"); -// boost::format formatLateAnnotation1("late(%1%, (%2%, %3%, %4%), (%5%, %6%, %7%), %8%)."); -// boost::format formatLateAnnotation2("late(%1%, (%2%, %3%), (%4%, %5%), %6%)."); -// #define FORMATSYMBOL(s) (formatSymb % s.identifier % s.version % s.scope).str() - -// // Ann1, `variant1` -// transcend->addRawScript((formatLateAnnotation1 -// % FORMATSYMBOL(symbTarget1P) -// % FORMATSYMBOL(symbpA) % FORMATSYMBOL(symbpB) % FORMATSYMBOL(symbpC) -// % "guard1" % "guard1" % "guard1" -// % "result(variant1)" -// ). str()); - -// //Ann1 `result2` variant -// transcend->addRawScript((formatLateAnnotation1 -// % FORMATSYMBOL(symbTarget1P) -// % FORMATSYMBOL(symbpA) % FORMATSYMBOL(symbpB) % FORMATSYMBOL(symbpC) -// % "guard2" % "guard2" % "guard2" -// % "result(variant2)" -// ). str()); - -// //Ann2 `result3` variant -// transcend->addRawScript((formatLateAnnotation2 -// % FORMATSYMBOL(symbTarget2P) -// % FORMATSYMBOL(symbpA) % FORMATSYMBOL(symbpB) -// % "guard3" % "guard3" -// % "result(variant3)" -// ). str()); - -// transcend->run(); -// LateAnnotationsGroup group = transcend->queryLate("result"); -// ASSERT_EQ(2, group.annotations.size()); - -// for(const auto& annEntry: group.annotations){ -// annEntry.first.print(cout); -// cout <(transcend->parse(targetWrapped)); -// if (targetSP == symbTarget1P){ -// LateAnnotation ann = annEntry.second; -// ASSERT_EQ(2, ann.guardedContent.size()); - -// Expression selector(Operator::CALL, {Atom("guard2")}); -// auto answer = ann.select({selector, selector, selector}, man->root, man->transcend); -// ASSERT_TRUE(answer); -// string answerS = get<0>(transcend->parse(*answer)); -// ASSERT_STREQ("variant2", answerS.c_str()); - -// } else if (targetSP == symbTarget2P) { -// LateAnnotation ann = annEntry.second; -// ASSERT_EQ(1, ann.guardedContent.size()); - -// Expression selector(Operator::CALL, {Atom("guard3")}); -// auto answer = ann.select({selector, selector, selector}); -// ASSERT_TRUE(answer); -// ASSERT_STREQ("variant3", get<0>(transcend->parse(*answer)).c_str()); - -// } else { -// ASSERT_TRUE(false); -// } -// } -//} - -TEST(LateReasoning, Doc_SwitchLateOperation){ - auto man = details::tier2::XreateManager::prepare( -R"Code( - -mul = function(x::float, y::float):: float +TEST(LateReasoning, Doc_SwitchLateOperation) { + string example = R"Code( +mul = function(x::float, y::float):: float { x * y } + +)Code"; -ArithmeticT = type slave arithmetic. + string codeTranscend = + R"Code( +arithmetic(fast; accurate). +)Code"; -test = function(a::float, b::float, ArithmX::ArithmeticT):: float; entry -{ - switch late (ArithmX):: float - { - mul(a, b)::float; arithmetic(ArithmX) - } -} + string example_LateAnn_1 = getDocumentationExampleById("documentation/Transcend/latetranscend.xml", "LateAnn_1"); + string example_SwitchLate_1 = getDocumentationExampleById("documentation/Transcend/latetranscend.xml", "SwitchLate_1"); + string outputExpected = getDocumentationExampleById("documentation/Transcend/latetranscend.xml", "Output_LateAnn_1"); + replace(example, "", example_SwitchLate_1); -)Code"); - - string codeTranscend = -R"Code( - arithmetic(fast; accurate). -)Code"; - - typedef LateReasoningTranscendDecorator LateTranscend; - typedef LateReasoningDFAPassDecorator LTDFAPass; - - std::unique_ptr transcend(new LateTranscend()); - man->transcend = transcend.get(); - man->transcend->addRawScript(move(codeTranscend)); - LTDFAPass* pass = new LTDFAPass(man); - - man->registerPass(pass, PassId::DFAPass, nullptr); - man->executePasses(); - man->analyse(); - - auto result = transcend->queryLate("arithmetic"); - ASSERT_EQ(1, result.annotations.size()); - ASSERT_EQ(2, result.annotations.begin()->second.guardedContent.size()); - //man->run(); + ASSERT_NE(std::string::npos, example_SwitchLate_1.find(example_LateAnn_1)); + + typedef LateReasoningTranscendDecorator LateTranscend; + typedef LateReasoningDFAPassDecorator LTDFAPass; + + auto man = details::tier2::XreateManager::prepare(move(example)); + std::unique_ptr transcend(new LateTranscend()); + man->transcend = transcend.get(); + man->transcend->addRawScript(move(codeTranscend)); + LTDFAPass* pass = new LTDFAPass(man); + + man->registerPass(pass, PassId::DFAPass, nullptr); + man->executePasses(); + + testing::internal::CaptureStdout(); + man->analyse(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + ASSERT_NE(std::string::npos, outputActual.find(outputExpected)); + + auto result = transcend->queryLate("arithmetic"); + ASSERT_EQ(1, result.annotations.size()); + ASSERT_EQ(2, result.annotations.begin()->second.guardedContent.size()); } diff --git a/cpp/tests/supplemental/docutils.cpp b/cpp/tests/supplemental/docutils.cpp index 627daf4..6fac2ad 100644 --- a/cpp/tests/supplemental/docutils.cpp +++ b/cpp/tests/supplemental/docutils.cpp @@ -1,54 +1,81 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * \file docutils.cpp * \brief Documentation processing * */ #include "docutils.h" #include +#include #include #include #include #include using namespace std; std::string getDocumentationExampleById(std::string filename, std::string id) { - string query = string("(//db:programlisting | //db:code)[@xml:id='") + id + "']"; + string query = string("(//db:programlisting | //db:code | //db:screen)[@xml:id='") + id + "']"; xmlDocPtr doc = xmlParseFile(filename.c_str()); - if (!doc) { + if(!doc) { cout << "Can't find documentation file: " << filename << endl; assert(false); return ""; } xmlXPathContextPtr context = xmlXPathNewContext(doc); - xmlXPathRegisterNs(context, BAD_CAST "db", BAD_CAST "http://docbook.org/ns/docbook"); + xmlXPathRegisterNs(context, BAD_CAST "db", BAD_CAST "http://docbook.org/ns/docbook"); xmlXPathObjectPtr response = xmlXPathEvalExpression((xmlChar*) query.c_str(), context); xmlXPathFreeContext(context); xmlNodeSetPtr nodeset = response->nodesetval; - if (nodeset->nodeNr != 1) { + if(nodeset->nodeNr != 1) { cout << "Can't find specified example " << id << endl; assert(false); return ""; } + string tag = (char*) nodeset->nodeTab[0]->name; + bool flagIsPrgListing = tag == "programlisting"; xmlChar* contentC = xmlNodeListGetString(doc, nodeset->nodeTab[0]->xmlChildrenNode, 1); string content = (char*) contentC; xmlFree(contentC); - xmlXPathFreeObject (response); + xmlXPathFreeObject(response); + if(flagIsPrgListing){ + //skip first line(used as header) + content = content.substr(content.find('\n')+1); + } assert(content.size() && "Empty example"); return content; } +std::string +getDocumentationExampleFromFile(std::string filename) { + std::ifstream stream(filename); + std::string result; + + stream.seekg(0, std::ios::end); + result.reserve(stream.tellg()); + stream.seekg(0, std::ios::beg); + + result.assign((std::istreambuf_iterator(stream)), + std::istreambuf_iterator()); + + assert(result.size() && "Empty example"); + + return result; +} + void -replace(std::string& str, const std::string& subA, const std::string& subB) { - str.replace(str.find(subA), subA.size(), subB); +replace(std::string &str, const std::string &subA, const std::string &subB) { + size_t posA = str.find(subA); + assert(posA != string::npos); + + str.replace(posA, subA.size(), subB); } \ No newline at end of file diff --git a/cpp/tests/supplemental/docutils.h b/cpp/tests/supplemental/docutils.h index c6c50f4..3f17d8f 100644 --- a/cpp/tests/supplemental/docutils.h +++ b/cpp/tests/supplemental/docutils.h @@ -1,21 +1,24 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * File: docuils.h * Author: pgess * * Created on November 29, 2018, 3:58 PM * - * \brief Documentation processing\ + * \brief Documentation processing */ #ifndef DOC_H #define DOC_H #include -std::string getDocumentationExampleById(std::string filename, std::string id); -void replace(std::string& str, const std::string& subA, const std::string& subB); +std::string getDocumentationExampleById (std::string filename, std::string id); +std::string getDocumentationExampleFromFile (std::string filename); +void replace (std::string& str, + const std::string& subA, + const std::string& subB); #endif /* DOC_H */ diff --git a/cpp/tests/transcend-ast.cpp b/cpp/tests/transcend-ast.cpp new file mode 100644 index 0000000..c8c6044 --- /dev/null +++ b/cpp/tests/transcend-ast.cpp @@ -0,0 +1,77 @@ +/* Any copyright is dedicated to the Public Domain. + * http://creativecommons.org/publicdomain/zero/1.0/ + * + * AST-Transcend Correspondence Tests + * + * Created on: Dec 2, 2018 + * Author: pgess + */ + +#include +#include "xreatemanager.h" +#include "pass/dfapass.h" +#include "supplemental/docutils.h" + +#include +#include "gtest/gtest.h" + +using namespace xreate; +using namespace std; + +struct TestRec { + string refExample; + string refOutput; + PassId pass; +}; + +std::list tests = { + {"ExprAnn_1", "Output_ExprAnn_1", PassId::DFAPass}, + {"CodeBlock_1", "Output_CodeBlock_1", PassId::CFAPass}, + {"CodeBlockAnns_1", "Output_CodeBlockAnns_1", PassId::CFAPass}, + {"CodeBlockBinds_1", "Output_CodeBlockBinds_1", PassId::CFAPass}, + {"CodeBlockParents_1", "Output_CodeBlockParents_1",PassId::CFAPass}, + {"Fn_1", "Output_Fn_1", PassId::CFAPass}, + {"FnAnns_1", "Output_FnAnns_1", PassId::CFAPass}, + {"FnSpecs_1", "Output_FnSpecs_1", PassId::CFAPass}, + {"FnEntry_1", "Output_FnEntry_1", PassId::CFAPass}, + {"FnResult_1", "Output_FnResult_1", PassId::CFAPass}, + {"OpInvoc_1", "Output_OpInvoc_1", (PassId) 1000}, + {"OpLoops_1", "Output_OpLoops_1", PassId::DFAPass} +}; + +TEST(ASTCorrespondence, Doc_BasicTests) { + for(auto test: tests) { + string program = getDocumentationExampleById("documentation/Transcend/ast-api.xml", test.refExample); + string outputExpected = getDocumentationExampleById("documentation/Transcend/ast-api.xml", test.refOutput); + + std::unique_ptr man(details::tier2::XreateManager::prepare(move(program))); + switch(test.pass) { + case PassId::CFAPass: + man->registerPass(new cfa::CFAPass(man.get()), test.pass); + break; + case PassId::DFAPass: + man->registerPass(new dfa::DFAPass(man.get()), test.pass); + break; + default: + man->registerPass(new dfa::DFAPass(man.get()), PassId::DFAPass); + man->registerPass(new cfa::CFAPass(man.get()), PassId::CFAPass); + break; + } + man->registerPass(new dfa::DFAPass(man.get()), test.pass); + man->executePasses(); + + cout << "Test: " << test.refExample << endl; + testing::internal::CaptureStdout(); + man->analyse(); + std::string outputActual = testing::internal::GetCapturedStdout(); + //cout << outputActual << endl; + + //check every line independently if outputActual is multi-line string + std::vector lines; + boost::split(lines, outputExpected, [](char c){return c == '\n';}); + for(auto line: lines) { + ASSERT_NE(std::string::npos, outputActual.find(line)); + } + } +} + diff --git a/cpp/tests/virtualization.cpp b/cpp/tests/virtualization.cpp index 033a706..a4eb9c7 100644 --- a/cpp/tests/virtualization.cpp +++ b/cpp/tests/virtualization.cpp @@ -1,60 +1,72 @@ /* Any copyright is dedicated to the Public Domain. * http://creativecommons.org/publicdomain/zero/1.0/ * * virtualization.cpp * * Author: pgess * Created on February 24, 2018, 4:30 PM */ #include "xreatemanager.h" #include "ast.h" #include "analysis/interpretation.h" #include "gtest/gtest.h" +#include "supplemental/docutils.h" + using namespace xreate; using namespace std; -TEST(Virtualization, UniqueSizoPrefix_1) { - FILE* input = fopen("scripts/virtualization/test1.xreate", "r"); - assert(input != nullptr); - - std::unique_ptr man(details::tier1::XreateManager::prepare(input)); - man->analyse(); - - ExpandedType typeDictSizoS = man->root->findType("DictSizo"); - ExpandedType typeDictSizo = interpretation::dereferenceSlaveType(typeDictSizoS, man->transcend); - ASSERT_EQ(TypeOperator::LIST_RECORD, typeDictSizo->__operator); - int (*main)() = (int (*)())man->run(); - - testing::internal::CaptureStdout(); - main(); - std::string outputActual = testing::internal::GetCapturedStdout(); - cout << outputActual << endl; - ASSERT_STREQ("file opened: /0/test1 file opened: /1/test1 ", outputActual.c_str()); -} +TEST(Virtualization, Doc_AccControl_1) { + string example = getDocumentationExampleFromFile("scripts/virtualization/test-AccControl_1.xreate"); + string exampleBody = getDocumentationExampleById("documentation/virtualization.xml", "AccControl_1"); + string output = getDocumentationExampleById("documentation/virtualization.xml", "Output_AccControl_1"); + replace(example, "", exampleBody); + + std::unique_ptr man(XreateManager::prepare(move(example))); + int (* main)() = (int (*)()) man->run(); -TEST(Virtualization, GlobalDereferenceStrategy_1) { - FILE* input = fopen("scripts/virtualization/test2.xreate", "r"); - assert(input != nullptr); - std::unique_ptr man(XreateManager::prepare(input)); - int (*main)() = (int (*)())man->run(); - - testing::internal::CaptureStdout(); - main(); - std::string outputActual = testing::internal::GetCapturedStdout(); - cout << outputActual << endl; - ASSERT_STREQ("file opened: test1 file opened: test1 ", outputActual.c_str()); + testing::internal::CaptureStdout(); + main(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + ASSERT_STREQ(output.c_str(), outputActual.c_str()); } -TEST(Virtualization, LocalDereferenceStrategy_1) { -FILE* input = fopen("scripts/virtualization/test3.xreate", "r"); - assert(input != nullptr); - std::unique_ptr man(XreateManager::prepare(input)); - int (*main)() = (int (*)())man->run(); - - testing::internal::CaptureStdout(); - main(); - std::string outputActual = testing::internal::GetCapturedStdout(); - cout << outputActual << endl; - ASSERT_STREQ("file opened: test1 file opened: 1/test1 ", outputActual.c_str()); +TEST(Virtualization, Doc_Isolation_1) { + string example = getDocumentationExampleFromFile("scripts/virtualization/test-Isolation_1.xreate"); + string partA = getDocumentationExampleById("documentation/virtualization.xml", "Isolation_1"); + string partB = getDocumentationExampleById("documentation/virtualization.xml", "Isolation_2"); + string output = getDocumentationExampleById("documentation/virtualization.xml", "Output_Isolation_1"); + replace(example, "", partA); + replace(example, "", partB); + + std::unique_ptr man(details::tier1::XreateManager::prepare(move(example))); + man->analyse(); + + ExpandedType typeDictSizoS = man->root->findType("DictSizo"); + ExpandedType typeDictSizo = interpretation::dereferenceSlaveType(typeDictSizoS, man->transcend); + ASSERT_EQ(TypeOperator::LIST_RECORD, typeDictSizo->__operator); + int (* main)() = (int (*)()) man->run(); + + testing::internal::CaptureStdout(); + main(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + ASSERT_STREQ(output.c_str(), outputActual.c_str()); } + +TEST(Virtualization, Doc_IsolationCat_1) { + string content = getDocumentationExampleFromFile("scripts/virtualization/test-IsolationCat_1.xreate"); + string example = getDocumentationExampleById("documentation/virtualization.xml", "IsolationCat_1"); + string output = getDocumentationExampleById("documentation/virtualization.xml", "Output_IsolationCat_1"); + replace(content, "", example); + + std::unique_ptr man(XreateManager::prepare(move(content))); + int (* main)() = (int (*)()) man->run(); + + testing::internal::CaptureStdout(); + main(); + std::string outputActual = testing::internal::GetCapturedStdout(); + cout << outputActual << endl; + ASSERT_STREQ(output.c_str(), outputActual.c_str()); +} \ No newline at end of file diff --git a/documentation-api/exploitation.graphml b/documentation-api/exploitation.graphml new file mode 100644 index 0000000..1eb1f56 --- /dev/null +++ b/documentation-api/exploitation.graphml @@ -0,0 +1,231 @@ + + + + + + + + + + + + + + + + + + + + + + + Exploitation + Output + Processing + Input + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + expl_siteUser + + + + + + + + + + + + + + + + + + expl_siteInit + + + + + + + + + + + + + + + + + + expl_assignments + + + + + + + + + + + + + + + + + + + Payload + + + + + + + + + + expl_supdom + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/documentation/Concepts/interpretation.xml b/documentation/Concepts/interpretation.xml index 7ebcaa2..50b46cb 100644 --- a/documentation/Concepts/interpretation.xml +++ b/documentation/Concepts/interpretation.xml @@ -1,415 +1,638 @@ - Interpretation + - Interpretation is mode in which Xreate interprets - given program i.e. evaluates, expands and simplifies parts of program based - on information if any known at compilation time. On another hand, - Interpretation is a middle man or intermediate level between Transcend and - Brute levels, it facilitates communication between them by means of - interpreting data of respective layers. It can be further divided into Upper - and Lower Interpretations depending on interacting with which layer we are - focused at the moment. + <?xxe-sn 26cy4nalqsw pu35zrt1abya?>Interpretation - main= function:: int; entry + Interpretation is a compiler's mode + reserved to evaluate, expand and simplify parts of a given program based on + information available in this mode. On the other hand, Interpretation is a + middle man, or an intermediate level, between the Transcend and Brute + levels, as it facilitates communication between those by means of + interpreting data of respective layers. It can be further divided into Upper + and Lower Interpretations depending on the interaction with the layer we are + focused on at the moment. + + mode + whereby - как это перевести? - это режим с помощью которого xreate + интерпретирует? Авторский смысл: это режим(компилятора) В КОТОРОМ компилятор + интерпретирует. + + Program: Речь идет о компьютерной программе, + или может приложении для смартфона, или алгоритме? Тогда лучше употребить + соответственно software ('piece of software') / app / algorithm. Вообще + "наши" компьютерные программы - это у них software, а не programs - - + ДА ТУТ СЛОВО PROGRAM ПОДХОДИТ, + особенно в контексте обработки программы с какимито целями, как здесь, чтоб + ее интерпретировать. + + name="tests/interpretation.cpp: Interpretation.Doc_Intr_1" +main= function:: int; entry { - x= "a"::string. + x= "a":: string. - y= if (x=="b")::string; i12n(on) - {1} else {0}. - y -} - + y= if (x=="b"):: string; i12n(on) + {1} else {0}. + y +} - In this example, identifier y has annotation - i12(on) which indicates that compiler should use compile-time - interpretation to evaluate y. After simplification, the - function's result is 0 with neither memory allocations for - string variable x nor any computation at runtime. + In this example, the identifier + y has an attached annotation + i12(on) which indicates that + the compiler should use compile-time interpretation to evaluate + y. Once the simplification + process is over, the function returns 0, + with neither memory allocations for the string variable x + nor any computation at runtime. - There are two annotations reserved to control interpretation - process: + Annotation - может лучше value или + parameter? - да Annotation + подходит + + There are two annotations reserved + to control the interpretation process: + + - i12n(on) Forces compiler to interpret annotated - expression, function, function argument. It yields error if expression - impossible to interpret + + + i12n(on) + Forces compiler to interpret the annotated expression, function, or + function argument. It yields error if the expression is impossible to + interpret. - i12n(off) Disables interpretation for annotated - expression + + + i12n(off) + Disables interpretation for the annotated expression.
- Eligible Expressions + + + <?xxe-sn 26cy4nalqsw pu35zrt1abyt?>Eligible Expressions - Currently compiler able to interpret following expressions: + Currently the compiler is able to + interpret the following expressions: + + - Atomic instructions: numbers, strings, identifiers + + + Atomic instructions: numbers, + strings, identifiers. - Relational and logic operators e.g. x==true, - x!=0 + + + Relational and logic + operators e.g. x==true, + x!=0. - if, switch statements. - [[#expansion|Statement expansion]] allowed + + + if, + switch statements. + [[#late-interpretation-or-e|Statement expansion]] allowed. - loop statements. [[#expansion|Statement expansion]] - allowed + + + Loop statements. + [[#late-interpretation-or-e|Statement expansion]] allowed. - Functions. [[#function-call-interpreta|Function calls]], - [[#partial-function|Partial function call interpretation]] + + + Functions. + [[#function-interpretation|Function calls]], + [[#partial-or-late-function|Partial function call + interpretation]]. + + interpreta - это так и нужно, или + неполное слово? - этот + кусок текста на сайте превратится в ссылку, это адрес ссылки, такой + должен быть - index operator e.g. x= {1, 2, 3}. y= x[0], - info= {planet="Earth"}. x= info["planet"]. + + + Index operator e.g. + x = {1, 2, 3}. + y = x[0], info = {planet="Earth"}. + x = info["planet"]. - list operators e.g. x= [1..10]. y={"day", - "night"}. + + + List operators e.g. + x = [1..10]. y={"day", + "night"}.
- Function Interpretation + - Whole function body could be subject to interpretation if it only - consists of interpretable expressions. + <?xxe-sn 26cy4nalqsw pu35zrt1abzi?>Function Interpretation - unwrap = function(data::unknType, keys::unknType):: unknType; i12n(on) + The whole function body may be + subject to interpretation if it consists of interpretable expressions + only. + + name="tests/interpretation.cpp: Interpretation.Doc_FnIntr_1" +unwrap = function(data::unknType, keys::unknType):: unknType; i12n(on) { - loop fold(keys->key::string, data->record):: unknType - { - record[key] - } + loop fold(keys->key::string, data->record):: unknType + { + record[key] + } } -test = function:: bool; entry +test = function:: bool; entry { - book = unwrap({ - Library = { - Shelf = { - Book = "Aristotle's Politics" - }}}, {"Library", "Shelf", "Book"}):: unknType. + book = unwrap({ + Library = { + Shelf = { + Book = "Aristotle's Politics" + }}}, {"Library", "Shelf", "Book"}):: unknType. - book == "Aristotle's Politics" -} - + book == "Aristotle's Politics" +} - The example demonstrates function unwrap which is - intended to be fully interpretable as depicted by function header - annotation. Obviously, the interpretable function requires all its - arguments be also interpretable. In this case compiler able to calculate - function's result at compile time and nothing of function's body goes to - compiled code. Compiled code looks like(which also optimized out during - consequent compilation phases): + The above example demonstrates + the unwrap function which + is intended to be fully interpretable, as indicated by the function + header's annotation. Obviously, the interpretable function requires that + all its arguments are also interpretable. In this case the compiler is + able to calculate the function's result at compile time with no byte code + produced. Here is what the compiled code looks like (which will be also + optimized out during the consequent compilation phases): - test = function:: bool; entry + name="tests/interpretation.cpp: Interpretation.Doc_FnIntr_1" +test = function:: bool; entry { - book = "Aristotle's Politics":: string. + book = "Aristotle's Politics":: string; i12n(on). book == "Aristotle's Politics" } - The example also reveals number of similarities with a dynamically - typed programming languages: + The example also reveals a number + of similarities with dynamically typed programming languages: + + number of similarities - тут точно нужен + артикль, неопределенный (a) если в смысле "много схожестей", и + определенный (the) - если речь идет о точном их количестве. a dynamically + typed - неопределенный артикль никогда не употребляется при множественных + объектах - OK + + - Relaxed types. Notice unknType - type which has not been defined. It's interpreted well because - compiler does not look at type system at all since everything can be - checked at compile time anyway. Interpretation mode is exactly level - where relaxed type system is possible without any penalties during - runtime. + + + Relaxed + types. Notice unknType + type which has not been defined. It's interpreted well because the + compiler completely ignores the type system since everything can be + checked at compile time anyway. The Interpretation mode is exactly the + level where the relaxed type system is possible without any + performance penalties or safety concerns. - Introspection abilities. Notice how it's - allowed to treat list fields as string keys, so functions like - unwrap can get list field name as a parameter. If list - does not have requested field it just leads to a compilation error and - no hard to catch runtime bugs. + + + Introspection + abilities. Notice how it is allowed to treat list fields as + string keys, so functions like unwrap + can get list field name as a parameter. Possible errors, such as the + list not having the requested field are easily spotted by the compiler + during interpretation and there are no concealed runtime bugs. In a + sense, it is a fair trade off between introspection expressiveness and + possible compilation errors. + + no hard to catch runtime bugs - не + вполне ясно. В смысле, "легко заметить баги проявившиеся во время + операции"? Тогда лучше "its is easy to see runtime bugs", или может + "the runtime bugs are possible" (если смысл такой, что могут + проявиться ошибки/баги"). It's и другие подобные сокращения: лучше + употреблять полную форму - it is, так как it's это разговорный вариант + - OK. - Additional reason for an arbitrary undefined type - unknType being used in the example is to ensure that no - compilation occurs and everything done on purely interpretation - level + + + Additional reason for the + arbitrary undefined type unknType + being used in the example is to ensure that no compilation occurs and + everything is done at the interpretation mode. - In simple cases Interpretation Analysis could determine that - function is subject to interpretation with no annotation hints - provided. - - unwrap = function(data::unknType, keys::unknType):: unknType - { - loop fold(keys->key::string, data->record):: unknType - { - record[key] - } - } - - test = function:: bool; entry - { - book = unwrap({ - Library = { - Shelf = { - Book = "Aristotle's Politics" - }}}, {"Library", "Shelf", "Book"}):: unknType; i12n(on). - - book == "Aristotle's Politics" - } - + In simple cases interpretation + analysis could determine that a function is subject to interpretation with + no annotation hints provided. + + name="tests/interpretation.cpp: Interpretation.Doc_FnIntr_2" +unwrap = function(data::unknType, keys::unknType):: unknType +{ + loop fold(keys->key::string, data->record):: unknType + { + record[key] + } +} + +test = function:: bool; entry +{ + book = unwrap({ + Library = { + Shelf = { + Book = "Aristotle's Politics" + }}}, {"Library", "Shelf", "Book"}):: unknType; i12n(on). + + book == "Aristotle's Politics" +} - The only difference from example above is lack of annotation hint - for unwrap. Developer requires interpretation of - book variable which in its turn depends on - unwrap. In this case Analysis able to recognize - unwrap is possible to interpret, so no errors occur. + The only difference from the + example above is the lack of annotation hint for unwrap. + It can be seen that interpretation of the variable book + is required which in its turn depends on unwrap. + In this case analysis is capable enough to determine that unwrap + is indeed possible to interpret, so no errors occur. - There are, however, more complicated cases for Interpretation - Analysis: + "Developer requires interpretation" - тут + речь о разработчике-программисте? Не вполне понятен смысл, поэтому пока + оставляю как есть. - да + программист, исправил + + There are, however, more + complicated cases for interpretation analysis: + + - Direct recursion. Interpretation Analysis is able to correctly - find out whether function involving direct recursion(in which a - function calls itself) is subject to interpretation + + + Direct recursion. + Interpretation analysis is able to correctly determine whether a + function involving direct recursion (where the function calls itself) + is subject to interpretation or not. - Indirect recursion. As of now for processing of indirect - recursion(in which a function is called not by itself but by another - function) analysis usually fails and rely on manually provided - annotation hints + + + Indirect recursion. + Currently, when processing the indirect recursion (where a function is + called not by itself but rather by another function), the analysis + usually fails and relies on manually provided annotation hints. - Below is an example of a direct recursion: + Below is an example of a direct + recursion: - unwrap = function(data:: X):: bool + name="tests/interpretation.cpp: Interpretation.Doc_FnIntr_3" +unwrap = function(data:: X):: bool { - if (data[0] == "the-end"):: bool - {true} else {unwrap(data[0])} + if (data[0] == "the-end"):: bool + {true} else {unwrap(data[0])} } -entry = function:: bool; entry { - unwrap({{{{"the-end"}}}}):: bool; i12n(on) +entry = function:: bool; entry +{ + unwrap({{{{"the-end"}}}}):: bool; i12n(on) } - Function unwrap unwraps nested list until it finds - desired value. No function level annotation required. + Function unwrap + unwraps the nested list until the desired value is found. No function + level annotation is required.
- Expansion or Late Interpretation + - Expansion is a partial simplification or elimination of - interpretable parts of certain statements. + <?xxe-sn 26cy4nalqsw pu35zrt1ac0j?>Late Interpretation or + Expansion - test = function(x:: int):: int; entry { - comm= "inc":: string; i12n(on). + Late + Interpretation can be conceptualized as a partial + expansion, i.e. a simplification or elimination of interpretable parts of + certain statements. - y= if (comm == "inc"):: int - {x + 1} else {x}. - y -} - + name="tests/interpretation.cpp: Interpretation.Doc_LateIntr_1" +test = function(x:: int):: int; entry +{ + comm= "inc":: string; i12n(on). - In this example, computation of y depends on - comm and x. On one side, comm has - an annotation that requires interpretation, on another side x - is unknown at compile-time and can't be interpreted. In this case the only - way to satisfy contradictory requirements is to - expand IF statement, since there is a - possibility to only interpret condition part of the statement, leaving - conditional blocks unchanged. In another words, IF statement - is expanded and just one of the child blocks is - compiled , x+1 in this example based on already known fact - that the other block would never be executed. - - With regard to the fact that expansion leaves some code for - compilation which has to be executed later as opposed to the "pure - interpretation" it can be also called late - interpretation as having runtime footprint. - - Below more complex example of a loop expansion: - - main = function(x:: int):: int; entry { - commands = {"inc", "double", "dec"}:: [string]; i12n(on). - - loop fold(commands->comm::string, x->operand):: int - { - switch(comm):: int - case ("inc") {operand + 1} - case ("dec") {operand - 1} - case ("double") {operand * 2} - } -} - + y= if (comm == "inc"):: int + {x + 1} else {x}. + y +} - commands contains list of operations that should be - interpreted as indicated by corresponding annotation. Operand - x gets assigned at runtime. This is the same situation as in - previous example and triggers expansion as expected. Result after - expansion looks as follows: - - main = function(x:: int):: int; entry { - x{1} = x + 1. - x{2} = x{1} * 2. - x{3} = x{2} - 1. - x{3} + In this example, computation of + y depends on + comm and x. + On the one hand, comm has + an annotation that requires interpretation, while on the other hand + x is unknown at the + compile-time and thus cannot be interpreted. In this case the only way to + satisfy contradictory requirements is to expand + the if statement, since it + is only possible to interpret condition part of the statement, leaving + conditional blocks unchanged. In other words, the if + statement is expanded + which results in only one of the child blocks being compiled, + x+1 in this example, based + on already known fact that the else + block would never be executed. + + "to interpret condition part of the + statement" - это не смог понять. - `if + (...) {..} else {...}` is a statement. It consists of condition part `if + (..)`, and two blocks - "if-true" block and "if-false" block + + + Due to the fact that expansion, + as opposed to "pure interpretation", leaves some portion of the code for + subsequent compilation it can also be called late + interpretation for the result depends on runtime information + and has memory and performance footprint. + + as having runtime footprint - не понял. + Что-то связанное с требованиями к памяти? Но это кажется о программах, а + не о interpretation - переписал + фразу + + Below is a more complex example + of a loop expansion: + + name="tests/interpretation.cpp: Interpretation.Doc_LateIntr_2" +main = function(x:: int):: int; entry +{ + commands = {"inc", "double", "dec"}:: [string]; i12n(on). + + loop fold(commands->comm::string, x->operand):: int + { + switch(comm):: int + case ("inc") {operand + 1} + case ("dec") {operand - 1} + case ("double") {operand * 2} + } } - In other words, this mimics well known loop unrolling technique by - putting several copies of the loop body in a row, each one for every item - of a list of `commands`. + Identifier commands + contains a list of operations that need to be interpreted as indicated by + the corresponding annotation. Operand x + is assigned at runtime. This is the same situation as in previous example, + and it triggers expansion as expected. The result after expansion looks as + follows: + + name="tests/interpretation.cpp: Interpretation.Doc_LateIntr_2" +main = function(x:: int):: int; entry +{ + x{1} = x + 1:: int. + x{2} = x{1} * 2:: int. + x{3} = x{2} * 1:: int. + x{3} +} - As of now follow statements support late interpretation: + In other words, this mimics the + well known loop unrolling technique by putting several copies of the loop + body in a row, each one for every item in the list commands. + + As of now, the following + statements support late interpretation: + + - Branching statements: if, switch, - switch variant, switch late + + + Branching statements: + if, switch, + switch variant, + switch late. - Loop statements: loop fold + + + Loop statements: + loop fold. - functions + + + Functions. - Other operators: query late + + + Other operators: + query late.
- Partial or Late Function Interpretation - - Xreate supports case when function has mixed arguments in regard to - interpretation, some should be interpreted, while others - - compiled. - - evaluate= function(argument:: num, code:: string; i12n(on)):: num { - switch(code):: num - case ("inc") {argument + 1} - case ("dec") {argument - 1} - case ("double") {argument * 2} - case default {argument} -} + -main = function(init::int):: int; entry { - commands= {"inc", "double", "dec"}:: [string]; i12n(on). + <?xxe-sn 26cy4nalqsw pu35zrt1ac1n?>Partial or Late Function + Interpretation - loop fold(commands->comm::string, init->operand):: int - { - evaluate(operand, comm) - } -} - + Xreate supports cases where a + function has mixed arguments in terms of interpretation, some of which + need to be interpreted, while others need to be compiled. - Looking at function evaluate's signature in this - example we can see only one argument code requires - interpretation. This means that function evaluate is subject - to a partial interpretation or in other words late function - interpretation. To enable late interpretation for function at - least one of its arguments should be annotated as i12n(on). - What compiler does next is to generate number of distinctive - function specializations. Each unique combination of - interpretable argument values corresponds to its own function - specialization. This should be used with cautiousness for compiler can - generate a lot of code for some cases. - - Example above generates three different evaluate - specializations as follows - - evaluate1= function(argument:: num):: num { - argument + 1 + name="tests/interpretation.cpp: Interpretation.Doc_LateFnIntr_1" +evaluate= function(argument:: num, code:: string; i12n(on)):: num +{ + switch(code):: num + case ("inc") {argument + 1} + case ("dec") {argument - 1} + case ("double") {argument * 2} + case default {argument} } -evaluate2= function(argument:: num):: num { - argument * 2 -} +main = function(init::int):: int; entry +{ + commands= {"inc", "double", "dec"}:: [string]; i12n(on). -evaluate3= function(argument:: num):: num { - argument - 1 -} + loop fold(commands->comm::string, init->operand):: int + { + evaluate(operand, comm) + } +} -main= function(init::int):: int; entry { - operand= init:: int. - - operand{1}= evaluate1(operand). - operand{2}= evaluate2(operand(1)). - operand{3}= evaluate3(operand(2)). - - operand(3) -} - + Looking at the function + evaluate's signature in + this example we can see only one argument code + that requires interpretation. This means that the function evaluate + is subject to a partial interpretation or, in other words, + late function + interpretation. + + In general, to enable late interpretation + for a function, at least one of its arguments should be annotated as + i12n(on). What compiler + does next is to generate a number of distinctive function + specializations. Each unique combination of interpretable + argument values corresponds to its own function specialization. This + should be used with cautiousness, since compiler can generate large + amounts of code in some cases. + + What compiler does next is to generate + number - то же самое, что в примеч. ниже (a number - несколько, the number + - конкретное число).To enable late interpretation for function - тут перед + function обязательно нужен артикль - определенный (the), если речь идет о + evaluate, или неопределенный (а) если речь идет о любой функции (я указал + the) - OK + + Based on the above example, three + different evaluate + specializations are generated as follows: + + name="tests/interpretation.cpp: Interpretation.Doc_LateFnIntr_1" +main= function(init::int):: int; entry +{ + operand = init:: int. + + operand{1} = evaluate1(operand):: int. + operand{2} = evaluate2(operand{1})::int. + operand{3} = evaluate3(operand{2})::int. + + operand(3) +}
- Domain Specific Languages and Interpretation - - DSL is an idea of expressing various concepts in a lapidary and - concise form. Xreate recognizes and acknowledges very successful and - beneficial DSL usage in certain areas, primarily to express - queries and configs, to name a - few. It is possible to use interpretation abilities to emulate DSL. - Developer can express desired functionality as a nested lists of numbers, - variants and strings which then processed by partially interpreted - function. Such function in its turn transforms input data into set of low - level compilation instructions so there is no runtime overhead. + + + <?xxe-sn 26cy4nalqsw pu35zrt1ac21?>Domain Specific Languages and + Interpretation + + DSL is an idea of expressing + various concepts in a lapidary and concise form. Xreate recognizes and + acknowledges very successful and beneficial DSL usage in certain areas, + primarily to express queries + and configs, to + name a few. It is possible to use interpretation abilities to emulate DSL. + Developer can express the desired functionality in the form of nested + lists of numbers, variants and strings which are then processed by a + partially interpreted function. Such function in its turn transforms the + input data into a set of low level compilation instructions so there is no + runtime overhead.
- On Interpretation Analysis + - Analysis follows classical type reconstruction algorithms to - determine which expressions are subject to an interpretation and check - correctness of reconstruction w.r.t. developer-provided annotations. - Analysis consists of two general parts: + <?xxe-sn 26cy4nalqsw pu35zrt1ac26?>On Interpretation + Analysis + + Analysis follows classical + type reconstruction + algorithms to determine which expressions are subject to interpretation + and check the correctness of reconstruction w.r.t. developer-provided + annotations. Analysis consists of two general parts: + + - Inference. Infers is it possible to - interpret expression based on known decisions for its arguments + + + Inference. + Infers if it is possible to interpret an expression based on its + already inferred argument's decisions. - Unification. Assigns appropriate decision - w.r.t. to a previously inferred expectations and developer-provided - hints as well + + + Unification. + Assigns an appropriate decision w.r.t. previously inferred + expectations and developer-provided hints as well.
+ \ No newline at end of file diff --git a/documentation/Concepts/polymorphism.xml b/documentation/Concepts/polymorphism.xml index d1e0674..c453c27 100644 --- a/documentation/Concepts/polymorphism.xml +++ b/documentation/Concepts/polymorphism.xml @@ -1,182 +1,224 @@ - Polymorphism + - Polymorphism is an umbrella term to denote number - of techniques across different programing paradigms. They all share the same - intention to provide ability easily recombine software components in a - different way with as little as possible manual work on developer's side. It - serves two major goals: specialization, when software, + <?xxe-sn 26n42fz1reo 2?>Polymorphism + + Polymorphism + is an umbrella term to denote number of techniques across different + programing paradigms. They all share the same intention to provide ability + easily recombine software components in a different way with as little as + possible manual work on developer's side. It serves two major goals: + specialization, when software, initially designed to support wide range of use cases, is configured for - concrete particular case and extension - adapting - software to an environment and conditions it was not specifically designed - for. + concrete particular case and extension + - adapting software to an environment and conditions it was not specifically + designed for. - In course of software engineering evolution, number of polymorphism - techniques was proposed and experimented with, all suited for different - use-cases. Xreate presents generalized and elegant approach that - exhaustively covers wide landscape of polymorphism variations. + In course of software engineering evolution, + number of polymorphism techniques was proposed and experimented with, all + suited for different use-cases. Xreate presents generalized and elegant + approach that exhaustively covers wide landscape of polymorphism + variations. - Polymorphism in Xreate can be applied on two levels: + Polymorphism in Xreate can be applied on two + levels: + + - Functions level. Function in Xreate can have - a multiple specializations and polymorphism is - compiler's ability to decide which exactly specialization to use - depending on various factors + + + Functions + level. Function in Xreate can have a multiple + specializations and + polymorphism is compiler's ability to decide which exactly + specialization to use depending on various factors - Modules level. Multiple modules can provide - the same service for users. Modules + + + Modules + level. Multiple modules can provide the same service for + users. Modules Resolution is a process to decide which exactly module to use
- Function Level Polymorphism - - Basic idea is to allow developer to define several functions with - the same name or, in other words, several - specializations. Caller code then invokes necessary - function by its shared name but can't directly specify particular - specialization. Exact specialization to be invoked is decided later by - decision process called polymorphism resolution - carried out by Transcend. This indirect invocation approach gives enough - flexibility to use or replace different specializations depending on - various conditions during compile time as well as at runtime. - - Please refer to syntax for details - about function specializations. Each specialization must have unique - guard(among all specializations with the same name) - to be discernible from others. To summarize, function invocation is a two - layered process, in which client code specifies callee function's shared - name, and polymorphism resolution specifies specialization guard if - needed. - - For an example, assume that we develop program to operate under - specified time constraints. To model implementation suitable for real time - environment, one specialization of crucialOperation is - defined with env(realtime) guard i.e. satisfies some fixed - execution time constraints. Caller main specifies only - function name crucialOperation thus delegating decision on - guard to a polymorphism resolution done elsewhere, based on environment's - constraints the code is executed in. - - guard:: env(realtime) + + + <?xxe-sn 26n42fz1reo j?>Function Level Polymorphism + + Basic idea is to allow developer to define + several functions with the same name or, in other words, several + specializations. Caller code + then invokes necessary function by its shared name but can't directly + specify particular specialization. Exact specialization to be invoked is + decided later by decision process called polymorphism + resolution carried out by Transcend. This indirect invocation + approach gives enough flexibility to use or replace different + specializations depending on various conditions during compile time as + well as at runtime. + + Please refer to syntax + for details about function specializations. Each specialization must have + unique guard(among all + specializations with the same name) to be discernible from others. To + summarize, function invocation is a two layered process, in which client + code specifies callee function's shared name, and polymorphism resolution + specifies specialization guard if needed. + + For an example, assume that we develop + program to operate under specified time constraints. To model + implementation suitable for real time environment, one specialization of + crucialOperation is defined with + env(realtime) guard i.e. satisfies + some fixed execution time constraints. Caller main + specifies only function name crucialOperation + thus delegating decision on guard to a polymorphism resolution done + elsewhere, based on environment's constraints the code is executed + in. + + guard:: env(realtime) { crucialOperation = function:: int { 0 } } main = function:: int; entry { crucialOperation() }
- Polymorphism Resolution + + + <?xxe-sn 26n42fz1reo x?>Polymorphism Resolution - SYNTAX: + SYNTAX: **dfa_callguard**(//call-site-ref//, //guard//) + + - call-site-ref reference to a call site in - AST + + + call-site-ref + reference to a call site in AST - guard resolved function specialization - guard + + + guard + resolved function specialization guard - When compiler encounters function invocation that has several - specialization it refers to the table dfa_callguard to find - out which specialization to call. It must have entry with appropriate - guard for every invocation site call-site-ref of - a polymorphic function. Polymorphism resolution is a process of filling - out dfa_callguard for a compiler based on custom Transcend - rules reflecting one or another polymorphism strategy. + When compiler encounters function + invocation that has several specialization it refers to the table + dfa_callguard to find out which + specialization to call. It must have entry with appropriate + guard for every invocation site + call-site-ref of a polymorphic + function. Polymorphism resolution is a process of filling out + dfa_callguard for a compiler based + on custom Transcend rules reflecting one or another polymorphism + strategy.
- Late Polymorphism + + + <?xxe-sn 26n42fz1reo 1c?>Late Polymorphism - Late Polymorphism is an extension to allow polymorphism resolution - to be based on data known only at runtime, i.e. resolve function - specializations dynamically. The Idea is to use Late Transcend to access - runtime data. See Late + Late Polymorphism is an extension to allow + polymorphism resolution to be based on data known only at runtime, i.e. + resolve function specializations dynamically. The Idea is to use Late + Transcend to access runtime data. See Late Transcend for details. - Example below demonstrates test invoking polymorphic - function compute: + Example below demonstrates test + invoking polymorphic function compute: - Strategy = type variant {fast, precise}. + Strategy = type variant {fast, precise}. guard:: fast { compute = function:: int {0} } guard:: precise { compute = function:: int {1} } test = function(s:: Strategy; alias(strategy)):: int; entry { switch late (s):: int { compute():: int; guardalias(strategy) } } - Function compute has two specializations, - fast and precise. We see that test - gets parameter s that dictates exact strategy to use. - Clearly, resolution should work dynamically to cope with cases like this, - for value of parameter s not only is unknown at compile time, - but it can change with each test execution. - - Operation Switch Late is compiled into several branches, two in this - case, each branch executing appropriate compute - specialization. Correct branch executed depending on current - s value. Custom annotations alias(Alias) and - guardalias(Alias) used to assign an alias in order to specify - which parameter to use for as basis for resolution + Function compute + has two specializations, fast and + precise. We see that test + gets parameter s that dictates exact + strategy to use. Clearly, resolution should work dynamically to cope with + cases like this, for value of parameter s + not only is unknown at compile time, but it can change with each + test execution. + + Operation Switch Late is compiled into + several branches, two in this case, each branch executing appropriate + compute specialization. Correct + branch executed depending on current s + value. Custom annotations alias(Alias) + and guardalias(Alias) used to assign + an alias in order to specify which parameter to use for as basis for + resolution
- Auto Expansion of Late Parameters - - In previous example, switch late operation was used to facilitate - calling of polymorphic function with late polymorphism resolution. It's - not that convenient to wrap each invocation by switch late whenever there - is need to call late polymorphic function. Specifically to handle cases - like this, compiler uses late parameter auto expansion technique. - - If compiler discovers that late(dfa_callguard()) entry - exists for current invocation and it does not have enclosing switch late - already, compiler automatically generates different branches that invoke - relevant specializations and transfers control to a branch depending on - late parameter value. In other words invocation implicitly wrapped into - switch late instruction if needed. + + + <?xxe-sn 26n42fz1reo 1x?>Auto Expansion of Late Parameters + + In previous example, switch late operation + was used to facilitate calling of polymorphic function with late + polymorphism resolution. It's not that convenient to wrap each invocation + by switch late whenever there is need to call late polymorphic function. + Specifically to handle cases like this, compiler uses late parameter auto + expansion technique. + + If compiler discovers that late(dfa_callguard()) + entry exists for current invocation and it does not have enclosing switch + late already, compiler automatically generates different branches that + invoke relevant specializations and transfers control to a branch + depending on late parameter value. In other words invocation implicitly + wrapped into switch late instruction if needed.
+ \ No newline at end of file diff --git a/documentation/Syntax/modules.xml b/documentation/Syntax/modules.xml index cf61944..c08f132 100644 --- a/documentation/Syntax/modules.xml +++ b/documentation/Syntax/modules.xml @@ -1,262 +1,325 @@ - Modules - - Xreate offers modules as a way to organize and - reuse source code. For simplicity, it's implemented as one file—one - module. - - Modules often require prior compilation of other modules for correct - work. It leads to a problem of a resolution where - required module is located. Especially since modern software products - usually have complicated and volatile file structure depending on exact - configuration and platform to build. Common practice is to rely on build - configuration tools to provide exact path for each module. - - For this reason Xreate interferes as little as possible with - resolution. Language does not support for module to directly specify any - path be it relative or absolute of other required modules. Also compiler - does not search modules in some predefined list of directories and does not - assume anything about project's file structure. It expects resolution - information already fully defined before compilation. - - However compiler has optional built-in functionality to facilitate - resolution. It is the very kind of problems the transcend level suited - excellently for. It is modeled as supply and demand - approach and lets modules to declare what they provide - and what require expressed by annotations. Compiler - then tries to satisfy requirements and find a match. Alternatively, external - tools always can be used. + + + <?xxe-sn 26n42fz1reo 22?>Modules + + Xreate offers modules + as a way to organize and reuse source code. For simplicity, it's implemented + as one file—one module. + + Modules often require prior compilation of + other modules for correct work. It leads to a problem of a + resolution where required + module is located. Especially since modern software products usually have + complicated and volatile file structure depending on exact configuration and + platform to build. Common practice is to rely on build configuration tools + to provide exact path for each module. + + For this reason Xreate interferes as little + as possible with resolution. Language does not support for module to + directly specify any path be it relative or absolute of other required + modules. Also compiler does not search modules in some predefined list of + directories and does not assume anything about project's file structure. It + expects resolution information already fully defined before + compilation. + + However compiler has optional built-in + functionality to facilitate resolution. It is the very kind of problems the + transcend level suited excellently for. It is modeled as supply + and demand approach and lets modules to declare what they + provide and what + require expressed by + annotations. Compiler then tries to satisfy requirements and find a match. + Alternatively, external tools always can be used.
- Module Headers + - SYNTAX: + <?xxe-sn 26n42fz1reo 2d?>Module Headers + + SYNTAX: **module** [:: //annotations-list// ] (Full form) { //module-statement//... } - **module** :: //annotations-list// . (Simplified form) + **module** :: //annotations-list// . (Simplified form) - //module-statement// ::= + //module-statement// ::= | **require** ( //annotation// ). (1) | **discover** ( //path// ). (2) | **controller** (//path//). (3) + + - annotations-list List of annotations delimited by - semicolon + + + annotations-list + List of annotations delimited by semicolon - annotation Any valid transcend expression + + + annotation + Any valid transcend expression - path Absolute or relative path to controller + + + path + Absolute or relative path to controller - Xreate recognizes number of module management statements. Those - statements should be located in specific section module {...} - of a source code which is called module header. - Module can have several headers. All headers gathered from a whole file - are combined into one before actual processing. + Xreate recognizes number of module + management statements. Those statements should be located in specific + section module {...} of a source + code which is called module + header. Module can have several headers. All headers gathered + from a whole file are combined into one before actual processing. - Modules processing happens before compilation. It means any data - produced in course of compilation is inaccessible at this stage + + + Modules processing happens before + compilation. It means any data produced in course of compilation is + inaccessible at this stage
- Requesting Modules + + + <?xxe-sn 26n42fz1reo 2x?>Requesting Modules - Statement require(..) expresses which modules are - required for correct compilation. + Statement require(..) + expresses which modules are required for correct compilation. - module { + module { require(logger). } - In this example module in question requires some other module that - provides feature called logger. There is - no way to specify direct external module location. Instead, module - expresses requirement in abstract form as propositional expression which - is later used by resolution to find exact match. + In this example module in question requires + some other module that provides + feature called logger. There is no + way to specify direct external module location. Instead, module expresses + requirement in abstract form as propositional expression which is later + used by resolution to find exact match. - module{require(stringslib).} + module{require(stringslib).} processString = function(a:: string):: string { someStrFunc(a) } module{require(mathlib).} processNumber = function(a:: num):: num { someMathFunc(a) } - Example above demonstrates using several headers in one file. It's - particularly useful if developer finds it convenient to put requirements - near the actual code that uses it. This way it can be easily spotted when - requirements are no more needed. After all, code locality improves - readability. + Example above demonstrates using several + headers in one file. It's particularly useful if developer finds it + convenient to put requirements near the actual code that uses it. This way + it can be easily spotted when requirements are no more needed. After all, + code locality improves readability.
- Module Annotations + - Module can declare additional information for various uses. This is - expressed by annotations located in the header. They are called module - annotations. For instance, module annotations can be used by module - resolution to find modules that satisfy requirements of others. + <?xxe-sn 26n42fz1reo 37?>Module Annotations - module:: status(obsolete). + Module can declare additional information + for various uses. This is expressed by annotations located in the header. + They are called module annotations. For instance, module annotations can + be used by module resolution to find modules that satisfy requirements of + others. - The example shows module that declares its status. It can be used by - resolution to choose most appropriate module out of number of candidates. - One way to view annotations used by resolution is to treat them as - something that module provides. + module:: status(obsolete). + + The example shows module that declares its + status. It can be used by resolution to choose most appropriate module out + of number of candidates. One way to view annotations used by resolution is + to treat them as something that module provides. - There are no predefined module annotations and developer can put - arbitrary information there. + + + There are no predefined module + annotations and developer can put arbitrary information there.
- Modules Resolution + - Modules resolution is a process to find exact modules locations that - match requests. Compiler does not search modules in predefined directories - and does not assume anything about project's file structure. In order to - allow developer to determine it themselves the compiler refers to two - transcend tables + <?xxe-sn 26n42fz1reo 3f?>Modules Resolution - SYNTAX: + Modules resolution is a process to find + exact modules locations that match requests. Compiler does not search + modules in predefined directories and does not assume anything about + project's file structure. In order to allow developer to determine it + themselves the compiler refers to two transcend tables + + SYNTAX: **modules_resolution**(//request//, //module-resolved//). (1) **modules_resolution**(//request//, //module-resolved//, //module-context//). (2) + + - request annotation used in statement - request(...) + + + request + annotation used in statement request(...) - module-resolved Path or identifier of a - module that matches request + + + module-resolved + Path or identifier of a module that matches request - module-context Path or identifier of a - module that requires other module + + + module-context + Path or identifier of a module that requires other module - These tables contain resolved modules for all possible requests. - Form (1) contains requests that should always be resolved to the same - module. Form (2) contains such requests for which resolution depends on - requesting module module-context. + These tables contain resolved modules for + all possible requests. Form (1) contains requests that should always be + resolved to the same module. Form (2) contains such requests for which + resolution depends on requesting module module-context. - modules_resolution(numlib, "/path/to/numlib"). + modules_resolution(numlib, "/path/to/numlib"). modules_resolution(strings, "/path/to/ansi-lib", "moduleA"). modules_resolution(strings, "/path/to/utf8-lib", "moduleB"). - For the example above the compiler would always resolve path to - numerical lib(numlib) as "/path/to/numlib" (line 1). However - strings library would be resolved as "/path/to/ansi-lib" if - requested in moduleA(line 2) and as "/path/to/utf8-lib" if - requested in moduleB(line 3). + For the example above the compiler would + always resolve path to numerical lib(numlib) + as "/path/to/numlib" (line 1). However strings + library would be resolved as "/path/to/ansi-lib" if requested in + moduleA(line 2) and as + "/path/to/utf8-lib" if requested in moduleB(line + 3). - When compiler encounters module request it looks up table - modules_resolution (first or second form) to find path of the - requested module. Tables can be populated by any means be it either - transcend reasoning or external tools. + When compiler encounters module request it + looks up table modules_resolution + (first or second form) to find path of the requested module. Tables can be + populated by any means be it either transcend reasoning or external + tools. - There is no defined order or priority or fall back behavior while - looking into tables. If the same request occurs in both tables they are - considered to be ill-formed + + + There is no defined order or priority or + fall back behavior while looking into tables. If the same request occurs + in both tables they are considered to be ill-formed
- Advanced Modules Resolution + + + <?xxe-sn 26n42fz1reo 46?>Advanced Modules Resolution - Xreate provide additional layer, optional helper to simplify modules - management. It introduces two more built-in statements that can be used in - module header: Discover statement and - Controller Statement. + Xreate provide additional layer, optional + helper to simplify modules management. It introduces two more built-in + statements that can be used in module header: Discover + statement and Controller + Statement. + + - Discover Statement has the form - discover (path).It allows to specify - directory where compiler would recursively search for all xreate files - and extract module header annotations. It gathers info about all found - source files. + + + Discover + Statement has the form discover + (path).It allows + to specify directory where compiler would recursively search for all + xreate files and extract module header annotations. It gathers info + about all found source files. - Controller Statement has the form - controller (path) and specifies path - to modules resolution controller. Controller is a file that contains - transcend rules in order to process data gathered by discovery and - populate resolution tables as its result of work. + + + Controller + Statement has the form controller + (path) and + specifies path to modules resolution controller. Controller is a file + that contains transcend rules in order to process data gathered by + discovery and populate resolution tables as its result of work. - Example below shows 3 modules: + Example below shows 3 modules: - //First Module + //First Module module:: name(testA); provide(superService); status(needToTestEvenMore). //Second Module module:: name(testB); provide(superService); status(needToTest). //Third Module module { require(superService). discover("/modules/path/"). controller("/path/to/controller"). } - Two modules offer the same feature - provide(superSerivce). Third module requires it and specifies - directory where to look up for needed files. Controller's task is to - populate resolution table if needed module is found and choose appropriate - candidate, if more than one module offer this service. - - One way to decide what to choose in this example is to look at - status of both modules. Let score be assigned to each possible status. - Let's say 0 for status(needToTestEvenMore), - 1 for status(needToTest). Then controller would - proceed with the best scoring module, Second Module in this - case. + Two modules offer the same feature + provide(superSerivce). Third module + requires it and specifies directory where to look up for needed files. + Controller's task is to populate resolution table if needed module is + found and choose appropriate candidate, if more than one module offer this + service. + + One way to decide what to choose in this + example is to look at status of both modules. Let score be assigned to + each possible status. Let's say 0 + for status(needToTestEvenMore), + 1 for status(needToTest). + Then controller would proceed with the best scoring module, + Second Module in this case.
- See Also + + + <?xxe-sn 26n42fz1reo 4w?>See Also - Transcend: Modules + Transcend: Modules API
+ \ No newline at end of file diff --git a/documentation/Syntax/syntax.xml b/documentation/Syntax/syntax.xml index e03c42a..95f2184 100644 --- a/documentation/Syntax/syntax.xml +++ b/documentation/Syntax/syntax.xml @@ -1,707 +1,956 @@ - Syntax + + + <?xxe-sn 26yv439af40 5a?>Syntax + + + - + + + + - Literals, Expressions, Basic Statements + + + Literals, Expressions, Basic + Statements - Annotations + Annotations - Intrinsics: query + Intrinsics: query - Identifiers, Code Blocks + + + Identifiers, Code Blocks - Branch Statements + Branch Statements - Interfaces: Extern-C + Interfaces: Extern-C - Functions + - Loops + Functions - Other: Transcend, Versions + Loops + + Other: Transcend, Versions - Types + + + Types - Variants + Variants - + - There are number of principles Xreate syntax based on: + There are number of principles Xreate syntax + based on: + + - Follows SSA form: each identifier is defined only once and no - redefinitions allowed + + + Follows SSA form: each identifier is + defined only once and no redefinitions allowed - Order in which identifiers are defined does not influence - computation order. Identifiers are computed in order based on - dependencies between expressions. Order in which identifiers are defines - reflects preferences and what is convenient for a developer. + + + Order in which identifiers are defined + does not influence computation order. Identifiers are computed in order + based on dependencies between expressions. Order in which identifiers + are defines reflects personal preferences and what is convenient for a + developer.
- Literals and expressions + + + <?xxe-sn 26yv439af40 62?>Literals and expressions - In Xreate expressions have a form: + Xreate expressions have a form: - SYNTAX: + SYNTAX: //expression// [:: //type//; //annotations-list// ] - where annotation-list is a list of annotations - delimited by semicolon. + + - Expressions consist of literals and various operations as - follows: + + + + annotation-list + is a list of annotations delimited by semicolon. + + + + Expressions consist of literals and various + operations as follows: + + - + + + - + + + - Literals + + + Literals - numbers, strings: 5, "Nimefurahi - kukujua" + numbers, strings: 5, + "Nimefurahi kukujua" - Lists, records + + + Lists, records - Record is a collection of elements of different types - - {year = 1934, month = "april"}. List is a collection - of elements of the same type without keys - {16, 8, + Record is a collection of elements + of different types - {year = 1934, + month = "april"}. List is a collection of elements of the + same type without keys - {16, 8, 3} - Arithmetic operations + - Basic arithmetic operations: +, -, *, - / + Arithmetic operations + + Basic arithmetic operations: + +, -, *, / - Relations + + + Relations - ==, !=, <>, <, <=, >, >=. - Both !=, <> mean not equal - relation. Examples: 8>=3, "Blue" <> + ==, + !=, <>, <, <=, >, >=. Both + !=, <> mean + not equal relation. + Examples: 8>=3, "Blue" <> "Green" - List and struct operations + + + List and struct operations - index operation to access individual - elements of a list or a record. Example: colors = {"Green", + index + operation to access individual elements of a list or a record. + Example: colors = {"Green", "Blue"}::[string]. color = colors[0]:: string. Record's - element access: date = {year = 1934, month = "april"}. year - = date["year"] + element access: date = {year = + 1934, month = "april"}. year = date["year"] - Identifiers + - Example: a - b + Identifiers + + Example: a + - b - Functions + + + Functions - Example: result = isOdd(6). + Example: result + = isOdd(6).
- Code Blocks + + + <?xxe-sn 26yv439af40 7c?>Code Blocks - Block is a list of expressions delimited by period. It has a - body - main expression and optionally some identifier - definitions. + Block is a list of expressions delimited by + period. It has a body - main + expression and optionally some identifier definitions. - SYNTAX: + SYNTAX: { [//ident// = //expression// . | //body-expression// . ].. } - Code block consists of expression called body + Code block consists of body expression and optional set of assignments to define - identifiers used by body expression. Block computation is defined as - result of associated body expression computation. If any expression - encountered during computation includes some identifiers they are computed - first. + identifiers used in body expression. Block's computation is defined as a + result of associated body expression's computation. Identifiers are + computed before expressions they are used in. - test = function:: int + name="tests/ast.cpp: AST.Doc_CodeBlocks1" +test = function:: int { a = 10:: int. b = 2:: int. a + b:: int } - Above is an example of code block which have a+b as a - body expression. In this case body depends on identifiers a, - b so compiler computes both of them beforehand. + Above is an example of code block which + have a+b as a body expression. In + this case body depends on identifiers a, + b so compiler computes both of them + beforehand. - Computation order depends only on dependencies between expressions. - This approach has properties as follows: + Computation order depends only on + dependencies between expressions. This approach has properties as + follows: + + - Mutually independent identifiers can be evaluated in any - order + + + Mutually independent identifiers can be + evaluated in any order - Identifier gets computed only if it's required by block body - expression or other required identifier + + + Identifier gets computed only if it's + required(even transitively) by block's body expression.
- Functions + + + <?xxe-sn 26yv439af40 7u?>Functions - SYNTAX: + SYNTAX: //function-name// = **function** ([//argument//:: //type//[; //annotation-list//]]...):: //return-type// [; //annotations//]... //function-block// + + - function-name name of function + + + function-name + name of function - argument formal parameter. Arguments - delimited by comma. + + + argument + formal parameter. Arguments are delimited by comma. - type, return-type - formal parameter and returning value types + + + type, + return-type formal + parameter and returning value types - function-block code block that holds - function definition + + + function-block + code block that acts as a function's definition - annotations list of annotations delimited - by semicolon + + + annotations + list of annotations delimited by semicolon - Below is an example of a function sum. It takes two - arguments and returns their sum. Also it has few annotations. First - annotation entry has a special meaning - it depicts entry - point or main function in a program. Second annotation - status(needs_review) is an example that developers can - annotate function using custom annotations to express different - properties. - - sum = function(x:: int, y:: int):: int; entry; status(needs_review) + Below is an example of a function + sum. It takes two arguments and + returns their sum. Also it defines several annotations. First annotation + entry has a special meaning — it + depicts entry point or main function in a program. Second annotation + status(needs_review) is a + demonstration that developers can annotate function using custom + annotations to express different properties. + + name="tests/ast.cpp: AST.Doc_Functions1" +sum = function(x:: int, y:: int):: int; entry; status(needs_review) { x+y }
- Function Specializations + - SYNTAX: + <?xxe-sn 26yv439af40 8j?>Function Specializations + + SYNTAX: **guard**:: //annotation// { //functions-list// } + + - annotation Guard expressed by - annotation + + + annotation + Guard expressed by annotation - functions-list one or more function that - share the same guard + + + functions-list + one or more function that share the same guard - Xreate allows several functions called - specializations to share the same name. This is - syntactic foundation for function level polymorphism + Xreate allows several functions to share + the same name. In which case they are called + specializations. This is syntactic foundation for + function level polymorphism, i.e. ability for compiler to decide which exactly function is called out - of several options. Resolution can happen during compilation or at - run-time. + of several options. Polymorphism resolution can happen during compilation + or at run-time. - Functions with the same name i.e. different specializations should - have unique identifiers called guards. When function - is actually called it's expected that resolution is already done at some + Functions with the same name, i.e. + different specializations should have additional unique identifiers called + guards. When function is + actually called it's expected that resolution is already done at some point before and supplies correct guard to uniquely specify which exactly specialization to call. - Example: + Example: - guard:: safe_enviroment + name="tests/ast.cpp: AST.Doc_FunctionSpecializations1" +guard:: safe_enviroment { sum = function (a::int, b::int) :: int { a + b } } - See API to - get more information on how guards are processed + + + See API + to get more information on how guards are processed
- Branch Statements + + + <?xxe-sn 26yv439af40 93?>Branch Statements
- IF Statement + - SYNTAX: + <?xxe-sn 26yv439af40 95?>IF Statement + + SYNTAX: **if** (//condition//):: //type// [; //annotations// ].. //block-true// **else** //block-false// - IF statement executes block-true or - block-false depending on - condition evaluation result. + IF + statement executes block-true + or block-false depending + on condition evaluation + result. - Example: + Example: - answer = if (question == "Favorite color?"):: string + name="tests/ast.cpp: AST.Doc_BranchStatements" +answer = if (question == "Favorite color?"):: string {"Yellow"} else {"Don't know"}.
- SWITCH Statement + + + <?xxe-sn 26yv439af40 9e?>SWITCH Statement - SYNTAX: + SYNTAX: **switch** ( //condition// ) :: //type// [; //annotations//].. [**case** ( //guard// ) code-block].. **case default** //default-code-block// + + - condition's result is used to decide - which branch to execute next + + + condition's + result is used to decide which branch to execute next - guard value to match against - condition + + + guard + value to match against condition - default-code-block executed if no - appropriate case found + + + default-code-block + executed if no appropriate case found - SWITCH statement evaluation's result is that of branch whose - guard matches - condition. + SWITCH statement evaluation's result is + that of branch whose guard + matches condition. - Example: + Example: - monthName = switch(monthNum) :: string + name="tests/ast.cpp: AST.Doc_BranchStatements" +monthName = switch(monthNum) :: string case (1) {"Jan"} case (2) {"Feb"} case default {"Strange.. Don't know this month"}.
- Loop Statements + + + <?xxe-sn 26yv439af40 9x?>Loop Statements
- LOOP Statement + - SYNTAX: + <?xxe-sn 26yv439af40 9z?>LOOP Statement + SYNTAX: **loop** ( //init-value// -> //accumulator// ):: //type// [; //annotations//] //loop-body// + + - init-value initial value loop starts - from + + + init-value + initial value loop starts from - accumulator identifier which holds loop's - result after each iteration + + + accumulator + identifier which holds loop's result after each iteration - For each iteration accumulator assumes result - of previous iteration or init-value during first - iteration. Result of the loop-body evaluation is - used as accumulator's next iteration value and as - overall loop statement result after the last iteration. + For each iteration accumulator + assumes result of previous iteration or init-value + during first iteration. Result of the loop-body + evaluation is used as accumulator's + next iteration value and as overall loop statement result after the last + iteration. - This notation does not have termination condition. Compiler relies - on loop body fixed point in order to decide when to interrupt loop. - Let's consider example: + This notation does not have termination + condition. Compiler relies on loop body's fixed point in order to decide + when to interrupt loop. Let's consider example: - COUNTEREXAMPLE + COUNTEREXAMPLE, name="tests/ast.cpp: AST.Doc_LoopStatements" //infinite loop answer = loop (2->x) :: int { if(IsPerfect(x)):: int {x} else {x+1} }. - The example tests numbers for being perfect(sum of all proper - divisors equals to the number itself). While iterating accumulator - x assumes values as follows: 2, 3, 4, 5, 6, 6 ... After it - founds first perfect number any further iteration do not change result - anymore since there is no increment and it continues to test the same - number again and again. Obviously, x=6 is a fixed point in + The example tests numbers for being + perfect(sum of all proper divisors equals to the number itself). While + iterating accumulator x assumes + values as follows: 2, 3, 4, 5, 6, 6 ... After it founds first perfect + number any further iteration do not change result anymore since there is + no increment and it continues to test the same number again and again. + Obviously, x=6 is a fixed point in this example. There is no point to continue going through further iterations once fixed point is evaluated and hence loop can be safely interrupted. - Compiler relies on manually provided annotations to recognize when - fixed point is reached. There is special annotation final - to specify fixed point for loops. Once expression marked as - final gets evaluated it's assumed to be fixed point or in - other words compiler knows it's the very last iteration after which loop - ends. Correct code for the example above is: + Compiler relies on manually provided + annotations to recognize when fixed point is reached. There is special + annotation final to specify fixed + point for loops. Once expression marked as final + gets evaluated it's assumed to be a fixed point or in other words + compiler knows it's the very last iteration after which loop ends. + Correct code for the example above is: - //loop exits after first perfect number is found + name="tests/ast.cpp: AST.Doc_LoopStatements" +//loop exits after first perfect number is found answer2 = loop (2->x) :: int { if(IsPerfect(x))::int {x:: int; final} else {x+1} }. - In this case compiler able to recognize when fixed point is - reached to exit loop. After loops is done answer is - 6. + In this case compiler able to recognize + when fixed point is reached to exit loop. After loops is done + answer is 6.
- LOOP FOLD Statement + - SYNTAX: + <?xxe-sn 26yv439af40 aq?>LOOP FOLD Statement + SYNTAX: **loop fold** (//list// **->** //element//:: //type// [; //annotations//], //init-value// **->** //accumulator//):: //type// [; //annotations//] //loop-body// + + - list to iterate through + + + list + to iterate through - element identifier that assumes value of - currently processed list element + + + element + identifier that assumes value of currently processed list + element - type, annotations - expression types and optional annotations delimited by - semicolon + + + type, + annotations expression + types and optional annotations delimited by semicolon - init-value accumulator's initial value - loop starts with + + + init-value + accumulator's initial value loop starts with - accumulator identifier assumes loop-body - evaluation result after each iteration + + + accumulator + identifier assumes loop-body evaluation result after each + iteration - Iterates over list in order to accumulate - result by applying loop-body transformation to each - element and intermediate - accumulator. Overall loop value is a accumulator's - value after the last iteration. If fixed point is found an execution - terminates earlier. + Iterates over list + in order to accumulate result by applying loop-body + transformation to each element + and intermediate accumulator. + Overall loop value is a accumulator's value after the last iteration. If + fixed point is found an execution terminates earlier. - Example shows code excerpt that looks for a minimal element in the - given list(and less then initial value 10). + Example shows code excerpt that looks for + a minimal element in the given list(and less then initial value + 10). - numbers = {4, 8, 7, 1, 5}:: [int]. + name="tests/ast.cpp: AST.Doc_LoopStatements" +numbers = {4, 8, 7, 1, 5}:: [int]. min = loop fold(numbers->x:: int, 10->acc):: int { if (acc > x):: int {x} else {acc} }.
- LOOP MAP Statement + - SYNTAX: + <?xxe-sn 26yv439af40 bi?>LOOP MAP Statement -**loop map** ( //list// **->** //element// :: //type// [; //annotations// ] ) :: //type// [; //annotations// ] + SYNTAX: +**loop map** (//list// **->** //element// :: //type// [; //annotations// ] ) :: //type// [; //annotations// ] //loop-body// + + - list to iterate through + + + list + to iterate through - element identifier that assumes value of - currently processed list element + + + element + identifier that assumes value of currently processed list + element - type, annotations - type and optional annotations delimited by semicolon. + + + type, + annotations type and + optional annotations delimited by semicolon. - loop-body + + + loop-body - Iterates over input list and applies - loop-body transformation to each element. Result is - a list that consists of all transformed elements. + Iterates over input list + and applies loop-body + transformation to each element. Result is a list that consists of all + transformed elements. - odd_numbers = {1, 3, 5}:: [int]. + name="tests/ast.cpp: AST.Doc_LoopStatements" +odd_numbers = {1, 3, 5}:: [int]. even_numbers = loop map(odd_numbers->number::int) :: [int] { 2 * number }. - Example demonstrates creating even_number list by - multiplying by 2 every element of odd_numbers. + Example demonstrates creating + even_number list by multiplying by + 2 every element of odd_numbers.
- Types + - Primitive Types + <?xxe-sn 26yv439af40 c6?>Types + + Primitive Types + + - + + + - + + + - num + + + num - i32 alias. Reserved for auto detected most - appropriate either integral of floating-point number type + i32 + alias. Reserved for auto detected most appropriate either integral + of floating-point number type - int + + + int - i32 alias. Reserved for auto detected most - appropriate integral number type + i32 + alias. Reserved for auto detected most appropriate integral number + type - float + - Double precision floating-point number + float + + Double precision floating-point + number - bool + + + bool - Boolean type + Boolean type - i8, i32, i64 + + + i8, + i32, i64 - Signed integers. 8, 32, 64 bit wide respectively + Signed integers. 8, 32, 64 bit + wide respectively - string + - Pointer to a null terminated ANSI char string. Reserved for - auto detected most appropriate string type. + string + + Pointer to a null terminated ANSI + char string. Reserved for auto detected most appropriate string + type. - * + + + * - Unspecified type. Example x = {amount=200, + Unspecified type. Example + x = {amount=200, currency="USD"}::*. - Compound types: + Compound types: + + - + - + + + + + - [ element-type ] + + + [ + element-type + ] - List of elements of the same type - element-type. Example: [int] - - list of int's + List of elements of the same type + element-type. + Example: [int] - list of + int's - {key:: - type, ...} + - List of elements of different type possibly with named - keys. Examples: {int, string}, {name::string, + {key:: + type, + ...} + + List of elements of different type + possibly with named keys. Examples: {int, + string}, {name::string, age::int} - variant {option :: - (type, ...}, ...} + + + variant + {option :: + (type, ...}, + ...} - Holds a single element of type of one out of number of - options. Examples: variant {FullAddress:: {string, string, - string}, ShortAddress:: {string}} + Holds a single element of type of + one out of number of options. Examples: variant + {FullAddress:: {string, string, string}, ShortAddress:: + {string}} - slave identifier + + + slave + identifier - Type determined by Transcend. Example: slave + Type determined by Transcend. + Example: slave unit_test - compound-type [ - key ] + - Accessing elements of compound type. Example: Bio = - type {birth_year:: int, name:: string}. Year = type + compound-type + [ key + ] + + Accessing elements of compound + type. Example: Bio = type + {birth_year:: int, name:: string}. Year = type Bio[birth_year]. - New types defined as: - - SYNTAX: + New types defined as: + SYNTAX: //type-name// = **type** (//parameters//...) //type-definition// . - Example: + Example: - Tuple = type {string, int}. + name="tests/ast.cpp: AST.Doc_Types" +Tuple = type {string, int}. Int = type Tuple[1]. //accessing by index
- Variants and SWITCH VARIANT Instruction + - SYNTAX: + <?xxe-sn 26yv439af40 ej?>Variants and SWITCH VARIANT + Instruction + SYNTAX: **switch variant** ( //condition// [-> //alias// ] [:: //type// [; //annotations//... ] ] ) :: type [; annotations... ] [ **case** ( //guard// ) //case-branch// ]... + + - condition expression of variant type + + + condition + expression of variant type - alias identifier to denote unwrapped - content of condition withing case branches. + + + alias + identifier to denote unwrapped content of condition withing case + branches. - guard name of variant to match against - actual condition's variant + + + guard + name of variant to match against actual condition's variant - case-branch block of code to execute in - case of matched variant. Content is accessible by using alias Within - the branch . + + + case-branch + block of code to execute in case of matched variant. Content is + accessible by using alias Within the branch . - Sometimes it is useful for a variable to have value of different - types depending on some conditions, in other words it has - variant type. + Sometimes it is useful for a variable to + have value of different types depending on some conditions, in other words + it has variant type. - Let's consider example with variable month of - variant type Month: + Let's consider example with variable + month of variant type + Month: - Month = type variant { + name="tests/ast.cpp: AST.Doc_Variants" +Month = type variant { MonName :: {string}, MonNumber:: {int} }. test = function:: Month { month = MonName("April"):: Month. month } - Variable month holds value of either - string or int type. Value is not accessible - directly. It should be unwrapped before using. Xreate - supports switch variant instruction for this - operation. + Variable month + holds value of either string or + int type. Value is not accessible + directly. It should be unwrapped + before using. Xreate supports switch variant + instruction for this operation. - As an example below is nextMonth function - definition: + As an example below is function + nextMonth's definition: - nextMonth = funcrtion(month:: Month):: Month + nextMonth = function(month:: Month):: Month { switch variant(month):: Month case (MonName) { // } case (MonNumber) - }
+ \ No newline at end of file diff --git a/documentation/Transcend/ast-api.xml b/documentation/Transcend/ast-api.xml index 75f4cb0..5fae63b 100644 --- a/documentation/Transcend/ast-api.xml +++ b/documentation/Transcend/ast-api.xml @@ -1,450 +1,495 @@ AST API In order to reason about program, code model is translated into form suited for processing by Transcend. Translation details are described below.
Expression Annotations: 'bind' SYNTAX: **bind**(//symbol-ref//, //annotation//) - symbol-ref assigned reference to the - expression or identifier + symbol-ref reference to the expression or + identifier annotation expression's annotation - Generated for each expression's annotation. Example: + Declares expression's annotations. - x = 5:: int; expected(even_number). + Example: + + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int +{ + x = 5:: int; expected(even_number). + + x +} gets translated into: - bind(v(1,-2,0), expected(even_number)). + bind(s(1,-2,0),expected(even_number))
Code Block: 'scope' SYNTAX: **scope**(//scope-ref//) scope-ref reference to the code block Declares code block under its unique reference identifier. Example: - { - x = 0.3:: float. - y = 0.8:: float. + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: float +{ + x = 3:: float. + y = 8:: float. x + y } - Translation result: scope(2). + Translation result: scope(0)
Code Block Annotations: 'bind_scope' + + Pending syntax changes + + SYNTAX: **bind_scope**(//scope-ref//, //annotation//, strong) (1) **bind_scope**(//scope-ref//, //annotation//, weak(..)) (2) scope-ref child block's reference annotation code block's annotation Declares code block's annotations called context. There are two forms for different context' type: strong context known at compile time weak possible context, can't be decided for sure at compile time Example: - { - context:: arithmetic(fast). + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: float +{ + context:: arithmetic(fast). - x = 0.3:: float. - y = 0.8:: float. + x = 3:: float. + y = 8:: float. x + y } Translation's result: - bind_scope(0, arithmetic(fast), strong). + bind_scope(0,arithmetic(fast),strong)
Code Block Bindings: 'ast_scope_binding' SYNTAX: -**ast_scope_binding**(//scope-ref//, //binding-id//, //binding-alias//) - +**ast_scope_binding**(//scope-ref//, //binding-id//, //binding-alias//) scope-ref code block's reference binding-id number of code block's binding binding-alias name of a binding - Code blocks can have bindings, i.e. Identifiers - that have special meaning within a block. Declared for each block's - binding. + Code blocks have zero or more bindings, i.e. + Identifiers that have special meaning within the block. Predicate declares + such code block's bindings. Bindings organized into ordered list. Order is + conveyed by specifying binding-id for each + binding-alias. Example: - loop ( 0 -> acc ) :: int + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int { - if(acc > 10) {acc:: int; final} else {acc + 1} + loop ( 0 -> acc ):: int + { + if(acc > 10):: int {acc:: int; final} else {acc + 1} + } } - Translation result: ast_scope_binding(2, 0, acc) + Translation result: ast_scope_binding(1,0,"acc")
Code Block Parents: 'cfa_parent' SYNTAX: -**cfa_parent**(//scope-ref//, scope(//scope-parent-ref//)) +**cfa_parent**(//scope-ref//, **scope**(//scope-parent-ref//)) scope-ref child block's reference scope-parent-ref parent block's reference Represents nested code blocks structure in terms of child-parent relation. Example: - { + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int +{ + x = 19:: int. + if (x>5):: int {x + 1} else {x - 1} } Translation's result: - cfa_parent(1, scope(0)). + cfa_parent(1, scope(0)). cfa_parent(2, scope(0)).
Function: 'function' SYNTAX: **function**(//fn-name//) fn-name function name - Declares function known by its name. + Declares function identified by its name. Example: - test = function:: int {0} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int {0} - Translation's result: function(test) + Translation's result: function(test)
Function's Annotations: 'bind_func' SYNTAX: **bind_func**(//fn-name//, //annotation//) fn-name function's name Declares function's annotations. Example: - test = function:: int; status(obsolete) {0} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int; status(obsolete) {0} - Translation's result: - bind_func(test,status(obsolete)) + Translation's result: bind_func(test,status(obsolete))
Function's Specialization: 'cfa_function_specializations' SYNTAX: **cfa_function_specializations**(//fn-name//, //guard//) fn-name name of function guard specialization guard There is a possibility to have several functions with the same name called specializations. Each specialization is uniquely determined by annotation of special kind called guard. Example: - guard:: arch(amd64) + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +guard:: arch(amd64) { test = function:: i64 {0} } - Translation's result: - cfa_function_specializations(test,arch(amd64)) + Translation's result: cfa_function_specializations(test,arch(amd64)) See also specializations syntax
Function's Entry: 'cfa_parent' SYNTAX: **cfa_parent**(//scope-entry-ref//, functon(//fn-name//)) scope-entry-ref function's entry code block reference fn-name function's name Each function has a single entry code block and is declared in terms of child-parent relation between entry block(which is top-level in blocks hierarchy of the given function) and the function itself. Example: - test = function:: int {0} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int {0} - Translation's result: cfa_parent(0, - function(test)) + Translation's result: cfa_parent(0,function(test))
Function's Result: 'dfa_fnret' SYNTAX: **dfa_fnret**(//fn-name//, //symbol-ret-ref//) symbol-ret-ref reference to a function's return expression Specifies which expression is used to compute function's return value. Example: - test = function:: int {0} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int {0} - Translation's result: dfa_fnret(test, v(0,-2,0)) + Translation's result: dfa_fnret(test,s(0,-2,0))
Operations. Invocation: 'cfa_call', 'dfa_callfn', 'dfa_callargs' SYNTAX: **cfa_call**(//scope-caller-ref//, //fn-callee-name//) (1) **dfa_callfn**(//symbol-ref//, //fn-callee-name//) (2) **dfa_callargs**(//symbol-ref//, //arg-formal-name//, //arg-actual-ref//) (3) **weak**(**dfa_callargs**(//symbol-ref//, //arg-formal-name//, //arg-actual-ref//)) (4) scope-caller-ref caller's code block's reference fn-callee-name callee function name symbol-ref invocation operation reference arg-formal-name function's formal argument arg-actual-ref actual argument reference Each function invocation is transformed into several transcend facts as explained below: (1) cfa_call Specifies caller's code block and callee function name (2) dfa_callfn Declares unique reference to a particular invocation site.The reference used by other facts to supply additional information (3) dfa_callargs Declares assignment relations between actual arguments and formal arguments (4) weak(dfa_callargs) The same as form (3). Weak relation used in cases when there is no enough information at compile time. One such case is when several function specializations exist and it's impossible to say which exactly specialization is called Example: - inc = function (x::int) :: int {x + 1} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +inc = function (x::int):: int +{ + x + 1 +} -main = function:: int +main = function:: int { - arg = 10:: int + arg = 10:: int. inc(arg) } After translation following transcend facts are present: - cfa_call(1, test) -dfa_callfn(v(0,1,-2), test) -dfa_callargs(v(0,1,-2), x, v(1,1,-2) + cfa_call(1,inc) +dfa_callfn(s(0,-2,1),inc) +weak(dfa_callargs(s(0,-2,1),s(1,-2,0),s(1,-2,1))) +dfa_callargs(s(0,-2,1),s(1,-2,0),s(1,-2,1))
Operations. Loops **ast_op_map**(//symbol-result-ref//, //symbol-source-ref//, //loop-body-ref//) **ast_op_fold**(//symbol-result-ref//, //symbol-source-ref//, //symbol-acc-ref//, //loop-body-ref//) symbol-source-ref input list reference symbol-acc-ref accumulator reference symbol-result-ref result list reference - loop-body-ref refers to a loop body's code block + loop-body-ref refers to a loop body expression Facts declare loop operations. Example: - singles = {1, 2, 3}:: [int]. -doubles = loop map(singles->element)::[int]{2 * element} + name="tests/transcend-ast.cpp: ASTCorrespondence.Doc_BasicTests" +test = function:: int; entry +{ + singles = {1, 2, 3}:: [int]. + doubles = loop map(singles->element:: int)::[int] {2 * element}. + doubles[0] +} - produces fact: ast_op_map(v(0,-2,0),v(1,-2,0),1) + produces fact: ast_op_map(s(2,-2,0),s(1,-2,0),s(0,-2,1))
diff --git a/documentation/Transcend/latetranscend.xml b/documentation/Transcend/latetranscend.xml index e627b48..fb97ae8 100644 --- a/documentation/Transcend/latetranscend.xml +++ b/documentation/Transcend/latetranscend.xml @@ -1,168 +1,171 @@ Late Transcend Transcend is a powerful tool and as a consequence it's computationally inefficient. Well, expressiveness has its cost. That's the reason why it's mostly suited only for a compile time where it shines unequivocally. Obviously, at this stage compiler lacks dynamic part - the data that is known for sure only during actual program execution. In other words, Early Transcend reasons over weak data - set of facts reflecting possible states and conditions the program could go through during execution. Before that, there is no way to be sure what exactly is going to happen, only set of possibilities is available. Nevertheless, in many cases it's not enough and that's why Late Transcend is introduced - reasoning and making decisions based on data available at runtime. Late Transcend approach can be described as having three phases: Input: at compile time Transcend working with weak data produces decisions for all possible alternatives. Generated set is used as an input for Late Transcend. As it's unknown which exactly decision turns out to be true, every decision has a guards - set of pairs (variable, value) that describe exact state for which it's possible to reach given decision. Validation: A decision is considered to be valid only if all guards are met, i.e. variables from guard pairs actually have required values. In a sense Late Transcend decisions are deferred until correspondent preconditions proved to be true. Execution: DIfferent guarded decisions may produce different code branches. All correspondent code branches are compiled and present in the code in order to be used when needed. At branching point guards are tested and appropriate branch is selected to be executed next.
Late Annotations and ASP Representation Late annotations is a particular type of annotations that depend on parameters known only at runtime. Example: - y = mul(a, b)::float; arithmetic(ArithmX) + name="tests/latetranscend.cpp: LateReasoning.Doc_SwitchLateOperation" +mul(a, b)::float; arithmetic(ArithmX) Suppose we have different specializations of mul function each implementing different multiplication precision and it controlled by using arithmetic(fast), arithmetic(accurate) and similar annotations. In this example arithmetic(ArithmX) is a late annotation, if ArithmX is a parameter known only during program execution. Currently, late annotations do not differ syntactically from other annotations. Only if annotation is recognized to have late arguments it's marked internally as a late and special rules of conversion to ASP form apply. - Late annotation in ASP form presented as follows: + Late annotation in ASP form is presented as follows: - **late**(//target//, (//guard-identifiers-list//), (//guard-values-list//), //body//):- //parameter-types-list//. + SYNTAX: +**late**(//target//, (//guard-identifiers-list//), (//guard-values-list//), //body//):- //parameter-types-list//. target References entity for which late annotation is applicable guard-identifiers-list List of guard identifiers guard-values-list List of guard values body Decision deemed valid if guards are met parameter-types-list List of types of late parameters Meaning that a fact body wrapped by modifier late() alongside with two lists: guards' identifiers and guards' values. For an example above, arithmetic(ArithmX) translated into form below where exact references depend on a program: - late(s(0,-2,2), (s(1,-2,2)), (ArithmX), arithmetic(ArithmX)):- arithmetic(ArithmX). + late(s(0,-2,2), (s(1,-2,2)), (ArithmX), arithmetic(ArithmX)):- arithmetic(ArithmX). This rule generates different facts for each possible x alternative. At runtime only those facts are selected whose guards are met, i.e. referenced variables actually have specified values.
Switch Late Operation SYNTAX: **switch late** ( //condition// [-> //alias// ] [:: //condition-type// [; //annotations-list//] ] ) :: //type// [; //annotations-list//] //switch-block// condition switch's condition alias optional alias to denote condition's result within internal code block annotations. If there is no alias and condition is just one identifier it's accessible by its own name condition-type Condition must have slave type Switch Late operation allows to designate alias as a late parameter to use in late annotation. It can be conceptualised as lifting Brute value to Transcend level. During compilation it generates different switch-block branches for each possible condition value and only branch is executed whose guard correspond condition. Example: - ArithmeticT = type slave arithmetic. + name="tests/latetranscend.cpp: LateReasoning.Doc_SwitchLateOperation" +ArithmeticT = type slave arithmetic. -test = function(a::float, b::float, ArithmX::ArithmeticT):: float; entry +test = function(a::float, b::float, ArithmX::ArithmeticT):: float; entry { switch late (ArithmX):: float { mul(a, b)::float; arithmetic(ArithmX) } } Compiler generates several branches for all possible arithmetic variants. Only one branch executed depending on arithmX.
diff --git a/documentation/exploitation.xml b/documentation/exploitation.xml new file mode 100644 index 0000000..43ac71c --- /dev/null +++ b/documentation/exploitation.xml @@ -0,0 +1,487 @@ + + + + + <?xxe-sn 26yv439af40 2?>Exploitation + + This chapter discusses exploiting + external resources, such as files, as a particular instance of a + side effects problem that + inevitably stems from an interaction with the outside world. Unlike virtualization, + an another documentation's topic that tackles I/O, exploitation approaches + subject from a different angle — it is concerned with an order + of operations, sequence in which different clients jointly use + the same resource and it deals with corresponding difficulties, e.g. ensures + proper resource initialization before actual usage. + +
+ + + <?xxe-sn 29je46abuev -wunr7fl0rw8u?>Syntax + +
+ + + <?xxe-sn 29je46abuev -wunr7fl0rw8r?>Annotations + + SYNTAX: +**use**(//resource-id//) +**init**(//resource-id//) + + + + + + + + resource-id + — user-defined resource identifier + + + + Annotates function or code + block as such that exploits resource resource-id. + +
+ +
+ + + <?xxe-sn 29je46abuev -wunr7fl0rw8i?>Guards + + SYNTAX: +**exploitation(init)** +**exploitation(none)** + + Specializations that are + recognized by exploitation reasoning. Each specialization corresponds to + an initialization strategy: + + + + + + + + exploitation(init) + is expected to perform actual resource initialization. + + + + + + exploitation(none) + is expected to do nothing as initialization isn't necessary or done + elsewhere. + + +
+
+ +
+ + + <?xxe-sn 26yv439af40 4?>Background + + In software engineering, the idea to avoid + side effects have received considerable traction. Indeed, side effects is + something that is hard to take into account and thus programs that have + side effects are inherently unsafe, thus best coding practices are + rightfully suggest to isolate side effects producing code as much as + possible. It's so called pure functional languages whose philosophy goes + even further and frames side effects as something opposite of "pure", and + everything is built around effectless computations to the point that some + languages' design itself includes side effects producing constructs, such + as I/O, as an afterthought, as something almost unnecessary. + + However, in reality the opposite is true, + most applications' sole responsibility is to communicate with "outside + world", reacting to the external events and change "world state" + accordingly. As a consequence, side effects usually are the + only important effects the + program produce and surely deserve first class support from a programming + language and justify efforts to develop approach to alleviate related + safety and performance concerns. +
+ +
+ + + <?xxe-sn 26yv439af40 10?>Exploitation Plan + + One complexity of taking side effects into + account is the fact that final result depends on an exact + operations order. This harshly impacts both performance and + safety, for many techniques, e.g. caching, parallelization can neither be + automatically performed nor validated since they are based on various + degrees of reordering or deal with possibly undetermined beforehand order + of execution. + + In this chapter, it is assumed, that final + effects of execution fully defined by exploitation + path — for a particular code path that can occur during + execution, it is its part consisting of only relevant code blocks., i.e. + those that deal with an exploited resource. Other code blocks do not + influence exploitation effects and so are excluded from consideration. + Thus reasoning about effects is reduced to considering all possible + exploitation paths, checking do they meet certain requirements that define + valid exploitation and making corrections if needed and possible. + + Result of the reasoning is called + exploitation plan — + specification that defines exact order and strategy of using a given + resource in order to comply with imposed requirements. + + With all above said, the discussed approach + can be presented as follows: + + + + + + + + Annotations are used to express some + aspects of side effects to enable further reasoning. They indicate + code blocks that deal with resource as well as provide additional + information about how exactly it is exploited, e.g. use, initialize or + deinitialize resource. + + + + + + Existing code paths, extracted during + source code processing, coupled with relevant annotations is enough to + construct all possible exploitation paths and analyze them. Analysis + determines possible(weak) + paths that can occur or not during particular execution as well as + certain paths(strong) + that occur always no matter what. Also it checks are exploitation + paths valid against certain rules, e.g. initialization occurs always + before actual usage and is it possible to correct invalid + paths. + + + + + + Reasoning's result is an exploitation + plan that dictates order and strategy of exploitation is presented in + form of appropriate specialization for polymorphic functions that deal + with resources in order to ensure safe exploitation to the extent + based on provided annotations. + + + + + + Exploitation related side effects are + viewed as a set of additional restrictions over operations order. Only + subset of possible reorders is still valid w.r.t. side effects. + Transcend's task is to find out refined set of valid orders. Thus + techniques that rely on reordering enjoy additional information to + make safe optimizations. + + + + ... and it serves three major goals: + + + + + + + + Safety. Validates existing exploitation + plan or is it possible to safely exploit given resource at all. + Compiler signals error if a given exploitation plan is invalid, i.e. + does not satisfy requirements w.r.t. side effects as expressed by + annotations. + + + + + + Regression Resilience. When + it comes to using external resources, some spurious dependencies + usually occur between otherwise isolated, independent components of a + program. Sometimes refactoring and other code changes break those + dependencies inevitably introducing regressions. Exploitation catches + this sort of regressions and automatically regenerates exploitation + plan suited for a changed conditions. + + + + + + Performance. Generated exploitation + plans are optimal in a sense that they cut off superfluous operations, + for example, removing resource initialization in several places if it + can be done safely in a single one, thus reducing overall + overhead. + + +
+ +
+ + + <?xxe-sn 27ay8x1a5mo 2?>Domination Analysis + + When it comes to a reasoning about order of + execution flow and possible code paths, crucial vehicle for that is + domination analysis producing + dominator tree as an + output. + + Unlike the usual function-bounded domination + analysis, when separate domination tree is produced for each function + defined in a program, Exploitation requires program bound analysis, that + is to take into account control flow across all functions in a program. It + is computationally intensive task to perform analysis over a whole + program, however it is compensated by the fact that Exploitation only + takes into account code blocks that deal with, or in other words, exploit + external resources. Thus there is no necessity to build full dominator + tree, only the relevant parts are constructed, just enough to make sound + exploitation plan decisions. +
+ +
+ + + <?xxe-sn 28h47d43thc j?>Empty Exploitation Plan. Effect Free + Computations + + Validation of exploitation path is done + against some predefined constraints. Depending on complexity of a + constraints, i.e. number of different exploitation events that are seeking + for in each path, reasoning goals categorized into several groups: + + + + + + + + Zero Order Exploitation. + Meaning that all paths are checked in terms is there exploitation at + all or no, is there at least a single exploitation event along the + path. + + + + + + First Order Exploitation. + Deals with a situations when it's enough to check only two different + exploitation event occur in a required order. It can be useful for + example, to check whether all resource uses occur after it is + initialized. + + + + + + Higher Order Exploitation. + Expresses constraints involving several(more than two) exploitation + events and relations between them. + + + + Empty + Exploitation is an important instance of zero order constraint. + It useful mechanism for developer to annotate function or part of a + program as effect free in terms of exploitation. Thus, efectless, clean or + pure code can be clearly separated from effectfull part and compiler + raises compilation error in case of accidental mixing or using "wrong" + type of code in non appropriate environment. +
+ +
+ + + <?xxe-sn 26yv439af40 v?>Resource Initialization + + One important problem related to an + exploitation order is to ensure that a given resource is properly + initialized before its first usage and additionally it is not initialized + more then once during exploitation session. This is instance of first + order exploitation since in a validation mode it is enough to check + exploitation plan to ensure that every resource usage preceded by resource + initialization at some point in the past, + i.e. previously in the exploitation path. + + For planning mode, the problem is addressed + as follows: + + + + + + + + Central idea of the algorithm is to + consider candidates for initialization only among code blocks that + dominate given usage + site. Obviously, initialization in dominating block precedes usage for + any possible code path. + + + + + + One or more dominator blocks are chosen + for actual initialization in such way that they are cover all found + usage sites. + + + + + + For code blocks chosen for + initialization specialization exploitation(init) + is set, for the rest specialization exploitation(none) + is used. + + + + Look at the example below: + + name="tests/exploitation.cpp: Doc_ResourceInit_1", lines=15 +import raw("scripts/cfa/payload.lp"). +import raw("scripts/exploitation/exploitation.lp"). //exploitation reasoning +import raw("scripts/exploitation/test1.assembly.lp"). + +guard:: exploitation(init) +{ + openFile = function(filePrev:: FILE_P):: FILE_P; init(file) + { + fopen("/tmp/test", "w")::FILE_P + } +} + +guard:: exploitation(none) +{ + openFile = function(filePrev:: FILE_P):: FILE_P + { + filePrev::int + } +} + +test = function:: int; entry +{ + seq + { f0 = undef:: FILE_P. f0 } + { + //Scope #1: + f1 = openFile(f0):: FILE_P. + f1 + } + + { //Scope #2: + f2 = openFile(f1):: FILE_P. + f2 + } + { + //Scope #3: + sizeWritten = fwrite("Attempt to write..", 12, 1, f2):: int; use(file). + sizeWritten + } + { + //Scope #4: + fclose(f2):: int; use(file) + } + { sizeWritten :: int} +} + + There is the function test + that executes sequentially next commands: open a file(scopes #1, #2), + write some text(scope #3) and finally, close the file(scope #4). It + represents simple work flow with an external resource. + + In order to connect the code to the + exploitation the functions fwrite and + fclose in scopes #3 and #4 + respectively are annotated with annotation use(file). + This information is used by reasoning to look whether it is possible to + initialize given resource before actual usage as well as where and when + exactly to initialize it. Function openFile + is annotated as init(file) meaning it + can initialize depending on + chosen strategy. The function is invoked both in scope #1 and scope #2. + Both scopes are executed strictly + before scopes #3, #4. Thus it is indeed possible to initialize + resource before usage. Next task for exploitation is to choose correct + exploitation plan, i.e. to assign strategies for all possible + initialization places in the effort to initialize resource only once. + Here, it means that only one invocation of openFile + is assigned with exploitation(init) + to actually initialize the file. Other one is automatically marked with + exploitation(none) to invoke + different specialization of openFile + that does nothing since the files is already initialized. +
+ + \ No newline at end of file diff --git a/documentation/virtualization.xml b/documentation/virtualization.xml new file mode 100644 index 0000000..8876674 --- /dev/null +++ b/documentation/virtualization.xml @@ -0,0 +1,497 @@ + + + + + <?xxe-sn 26yv439af40 1l?>Virtualization + + The chapter expands on a usage of context + based polymorphism, in other words, reasoning over CFG, as a ground to + implement application level + virtualization. + + One way to approach virtualization problem is + to model it in terms of satisfying constraints imposed by environment over + agents that operate within it, as presented below: + + + + + + + + sizo + (distorted abbreviation of SEcurity ZOne) — logical entity introduced to + represent environment and describe desired virtualization + outcome. + + + + + + zek + (distorted abbreviation of SEcurity aGent) — represents behaviour of the + code in terms of virtualized resources access. + + + + Basic idea is to automatically reason over + information defined by sizos and zeks and produce virtualization + plan as a solution that dictates which parts of code should be + virtualized and how exactly. Such reasoning enables two features: + + + + + + + + Optimization. Allows choosing + virtualization technique with a least performance penalty nevertheless + satisfying necessary requirements. + + + + + + Safety. Validates manually chosen + virtualization plan to be safe and sound by checking that it indeed + satisfies requirements. + + + + In other words, context based reasoning + provides improvements by virtualizing only necessary sections of code, only + for necessary type of resources and by employing as lightweight as possible + virtualization strategy just enough to comply with safety and security + requirements expressed by annotations in the code. + +
+ + + <?xxe-sn 26yv439af40 25?>Background + + Virtualization + refers to an abstracting code from underlying resources + used by it. Here term resource depicts any external entity such as + devices, files, network connections, etc, for which it is desirable to + regulate access. + + Virtualization is a vast area and broad + term that includes number of techniques on different levels to achieve + several important goals such as: + + + + + + + + Shared access — to allow several + clients use the same resource while behaving as if each client is the + sole resource user simplifying development and testing. + + + + + + Isolation — cornerstone of safety and + behaviour repeatability achieved by minimizing influence of isolated + clients between each other and external environment. + + + + + + Adaptation — to allow client + application work within an unexpected environment it was not developed + for, by emulating "native" familiar environment thus reducing + adaptation and support costs. + + + + Due to importance of goals achievable with + virtualization, it is unavoidable in a long run. That being said, basic + virtualization techniques have performance penalties arising from indirect + and regulated access to underlying resources. + + Further discussion is concerned with what + can be done to alleviate major virtualization inefficiencies by + fine-grained control over what, when, and how should be + virtualized. +
+ +
+ + + <?xxe-sn 26yv439af40 2k?>Access Control + + Whole program can be broken down into one + or more virtualization zones, each having different appropriate type of + virtualization strategy. Such approach allows to model hybrid + virtualization, i.e. different parts of program are virtualized + differently depending on some conditions. To capture this concept, term + sizo is introduced and + refers to a logical entity that holds information about particular zone + necessary to find best suited virtualization strategy. + + + + + Sizo is associated with context, + i.e. each zone spans over one or more code blocks. + + + There is a annotation assign_sizo + to specify sizo a code block is assigned to: + + SYNTAX: +**assign_sizo**(//sizo-ref//). + + + + + + + + sizo-ref + unique sizo's identifier + + + + Next thing is to specify which resources a + particular sizo controls access to, as below: + + SYNTAX: +**assign_sizo_control**(//resource-type//). + + It indicates that current sizo(sizo that + spans over code block the annotation located within) regulates all access + to a resources of a given type resource-type. + Conversely, If for a particular environment there is no need to control, + for example, file system access, no virtualization for file operations is + applied. + + On the other hand, there is an annotation + to mark function that accesses one or another resource: + + SYNTAX: +**assign_zek_access**(//resource-type//). + + Let's consider an example to demonstrate + all above: + + name="tests/virtualization.cpp: Virtualization.Doc_AccControl_1", lines=15 +import raw ("scripts/cfa/context.lp"). //enable context reasoning +import raw ("scripts/virtualization/virtualization.lp"). //enable virtualization reasoning + +guard:: strategy(direct) +{ + openFile = function(filename::string):: int + { + printf("direct file access") + } +} + +guard:: strategy(common) +{ + openFile = function(filename::string):: int; + assign_zek_access(files) + { + printf("virtualized file access") + } +} + +main = function:: int; entry +{ + context:: assign_sizo(zoneA); + assign_sizo_control(files). + openFile("/some/file") +} + + Example outlines dummy function + openFile to model file system + access. The function has two specializations with guards strategy(direct) + to model direct access, and strategy(common) + to be invoked if virtualization is enabled. It also annotated with + assign_zek_access(files) to indicate + that it accesses file system. On the other hand, context of function + main defines sizo zoneA + and enables control over file operations. + + Reasoning works with provided information + and decides whether it is necessary to enable virtualization. In this + case, the answer is yes for zoneA, + because of the fact that sizo controls file operations and there is + actually function within the sizo that requires files access. + Consequently, example outputs:virtualized file accessconfirming + that specifically virtualized specialization of openFile + was invoked. +
+ +
+ + + <?xxe-sn 26yv439af40 3i?>Isolation + + As shown in the previous section, it is + possible to enable(or disable) virtualization on per resource basis. + However such functionality is limited in a sense that if several sizos + allow access to the same resource they can interfere with each other. + Thus, next step to consider is isolation, + i.e. zeks in different sizos should not have ability to access the same + resource, but rather work with their own set of resources associated with + particular sizo. As previously, following examples are focused on file + operations as most ubiquitous type of resources. + + One way to isolate file access is to + associate unique file prefix with each sizo. If virtualization enabled, + all filenames in the sizo are silently transformed on the fly by adding + assigned prefix. This way, all the file operations from one sizo are + confined within specific directory allocated solely for that particular + sizo or simply have unique prefix if the same directory contains files + belonging to a different sizos. + + name="tests/virtualization.cpp: Doc_Isolation_1", lines=15 +main = function:: int; entry +{ + seq + { + context:: assign_sizo(domainA); + assign_sizo_control(files). + openFile("test") + } + { + context:: assign_sizo(domainA). + + openFile("test") + } + { + context:: assign_sizo(domainB); + assign_sizo_control(files). + openFile("test") + } +} + + In this example file test + is accessed from different sizos domainA + and domanB. As there are several + "competing" sizos are declared, they are isolated and openFile + resolves test to a different + filename depending on from which sizo it is called. One possible way to + implement discussed strategy shown below: + + name="tests/virtualization.cpp: Doc_Isolation_1", lines=15 +import raw ("scripts/cfa/context.lp"). //enable context reasoning +import raw ("scripts/virtualization/virtualization.lp"). //enable virtualization reasoning +import raw ("scripts/virtualization/test-Isolation_1.assembly.lp"). //additional configuration + +DictSizo = type slave dict_sizo. +Sizo = type slave virt_sizo. + +guard:: strategy(direct) +{ + resolveFilename = function(filename:: string):: string; + assign_zek_access(files) + { + filename + } +} + +guard:: strategy(prefix) +{ + resolveFilename = function(filename:: string):: string; + assign_zek_access(files) + { + dictSizo = intrinsic query("dict_sizo")::[DictSizo]. + sizoId = intrinsic query late("sizo_current"->sizoCurrent:: Sizo):: int; + demand(sizo) + { + loop fold(dictSizo->entry::DictSizo, 0->id):: int + { + if(entry[0] == sizoCurrent):: int { entry[1] } else { id } + } + }. + + buf = "00"::string. + seq + { sprintf(buf, "%d/%s", sizoId, filename) } + { buf } + } +} + +openFile = function(filename:: string):: int +{ + filenameReal = resolveFilename(filename):: string. + printf("File opened: '%s'%c", filenameReal, 10) +} + + Example outputs: + + File opened: '0/test' +File opened: '0/test' +File opened: '1/test' + + + In this example function openFile + calls resolveFilename to find out + real filename. It can be said, that resolveFilername + serves as hypervisor + dereferencing file pseudonym into real filename. In order to do that, + resolveFilername consists of two + specializations: specialization strategy(direct) + serves non virtualized environmentб leaving filename without any + processing, and the other specialization strategy(prefix) + implements resolving strategy by adding sizo-associated prefix to each + file. More specifically, unique index is assigned to each sizo and + resolveFilename uses the index as + file name prefix. + + Resolution function resolveFilename + has only one parameter filename, + deriving required prefix from late + context associated with particular sizo. + + + + + Client code has no way to influence + resolving process and force to use unapproved prefix, thus accessing and + interfering with files that belong to other sizos. + +
+ +
+ + + <?xxe-sn 26yv439af40 4c?>Isolation Categories + + Every optimization technique applicable + only if some specific preconditions are met. Indeed, only general approach + can handle general task. However, for practical instances there are always + some improvements possible by tailoring to the particular use case + specifics and subtle details. In other words, the more information + available the more space for improvements is there. And first step on this + road is the very ability to express and reason about such additional + information. + + As a demonstration, in order to improve + reasoning to find out optimal virtualization strategy for particular use + case, different sizo + categories can be introduced, as below: + + + + + + + + Inward + Isolation. The category describes sizo that prohibits + access from other sizos to its internal resources, but able to access + external resources freely. For example, monitoring and supervision + software may have been assigned this type of isolation — freely + accesses subordinate zones but can't be influenced from the + outside. + + + + + + Outward + isolation. The exact opposite of inward isolation. Allows + access from external sizos but is only allowed to use its own internal + resources, so no influence to the outside world is possible. + Appropriate for various sandboxes and testing environments to run + possibly insecure code. + + + + For file operations inward isolation may be + implemented as virtualization strategy that requires from + other sizos compulsory usage + of file prefixes so no other sizo can access internal data of inwardly + isolated sizo. Conversely, outward isolation is compatible with strategy + that assigns prefix for this very sizo, so it can in no way access any + external data, being at the same time exposed to the outside world for any + sizo that have permission to know unique assigned prefix able to access + internal data of sizo in question. To put it simply, strategy for these + types can be described with following points: + + + + + + + + Inward isolation — requires prefixes + for other sizos. + + + + + + Outward isolation — requires prefix for + itself. + + + + There is an annotation introduced to + declare category for the current sizo: + + SYNTAX: +**assign_sizo_category(inward)**. +**assign_sizo_category(outward)**. + + Consider the example below: + + name="tests/virtualization.cpp: Doc_IsolationCat_1", lines=15 +test = function:: int; entry +{ + seq + { + context:: assign_sizo(zoneA); + assign_sizo_control(files); + assign_sizo_category(inward). + openFile("test1") + } + { + context:: assign_sizo(zoneB); + assign_sizo_control(files); + assign_sizo_category(outward). + openFile("test1") + } +} + + + There are two sizos declared in the code + above. Using reasoning apparatus developed in previous sections, both + sizos activate virtualization, for both of them control file resources and + both contain openFile that actually + requires file access. However, this time additional bits of information + are available, namely zoneA and + zoneB declared as inward and + outward, respectively. By strategy outlines above, zoneA + enables prefix based isolation strategy for zoneB, + and zoneB enables isolation for + itself as well. As a result, it's enough to virtualize only one + zone(zoneB) leaving zoneA + to enjoy direct access to file resources. Example output's is shown below, + confirming that direct file access is granted for zoneA: + + File opened: 'test1' +File opened: '1/test1' + +
+ + \ No newline at end of file diff --git a/scripts/cfa/context.lp b/scripts/cfa/context.lp index f97d57a..0543063 100644 --- a/scripts/cfa/context.lp +++ b/scripts/cfa/context.lp @@ -1,106 +1,105 @@ % 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/. %% INPUT: %% - latex_scope_demand(Scope, Subject) %% Initial demand from clients %% %% - latex_registered_subjects(Subject, PossibleDecision) %% Clients register possible decisions for respective subjects %% %% - latex_fn_signature %% %% OUTPUT: %% - latex_fn_demand(Fn, Subject) %% Which functions demand hidden latex arguments %% %% - latex_decision(Scope, Subject, Decision) %% Provided decisions, values for hidden latex arguments %% %% SIGNATURES: %% -Subject: string %% % CONTEXT PROPAGATION %=========================================================== % nested scope propagation: bind_scope(Scope, Context, Info):- bind_scope(ScopeParent, Context, Info); cfa_parent(Scope, scope(ScopeParent)). % Strong or Uniform inter-function propagation: bind_scope(Scope, Context, Info):- bind_scope(ScopeParent, Context, Info): cfa_call(ScopeParent, FnCurrent); cfa_parent(Scope, function(FnCurrent)); cfa_call(_, FnCurrent); bind_scope(_, Context, Info); scope(Scope). % weak inter-function propagation bind_scope(Scope, Context, weak(ScopeParent)):- not bind_scope(Scope, Context, strong); bind_scope(ScopeParent, Context, strong); cfa_call(ScopeParent, FnCurrent); cfa_parent(Scope, function(FnCurrent)). % DEMAND %=========================================================== %demand propagations: scope level latex_scope_demand(Scope, Subject):- latex_scope_demand(ScopeChild, Subject); cfa_parent(ScopeChild, scope(Scope)). %propagation: fn level latex_fn_demand(Fn, Subject):- latex_scope_demand(ScopeFnBody, Subject); cfa_parent(ScopeFnBody, function(Fn)). latex_fn_demand_ordered(Fn, Subject, Id):- Id= #sum{ 1, SubjLess : latex_fn_demand(Fn, SubjLess), SubjLess < Subject}; latex_fn_demand(Fn, Subject). %propagation: inter-fn level latex_scope_demand(Scope, Subject):- latex_fn_demand(FnCallee, Subject); not latex_decision(Scope, Subject, _); cfa_call(Scope, FnCallee). % DECISIONS %=========================================================== latex_decision(Scope, Subject, Decision):- latex_fn_demand(FnCallee, Subject); bind_scope(Scope, Decision, strong); cfa_call(Scope, FnCallee); latex_registered_subjects(Subject, Decision). %late decision late((ScopeCaller, Subject), SubjectS, (AnyDecision), latex_decision(ScopeCaller, Subject, AnyDecision)):- - scope_fn(ScopeCaller, FnCaller); - cfa_parent(FnCallerBody, function(FnCaller)); - latex_symbol(FnCaller, Subject, SubjectS); + scope_fnbody(ScopeCaller, FnCallerBody); + latex_symbol(FnCallerBody, Subject, SubjectS); cfa_call(ScopeCaller, FnCallee); latex_fn_demand(FnCallee, Subject); latex_registered_subjects(Subject, AnyDecision). % UTILITY %=========================================================== -latex_symbol(Fn, Topic, s(TopicsOffset + TopicId, -2, FnBody)):- +latex_symbol(FnBody, Topic, s(TopicsOffset + TopicId, -2, FnBody)):- cfa_parent(FnBody, function(Fn)); latex_parameters_offset(TopicsOffset); latex_fn_demand_ordered(Fn, Topic, TopicId). % IMPLEMENTATION %=========================================================== -scope_fn(Scope, Fn):-cfa_parent(Scope, function(Fn)). -scope_fn(Scope, Fn):- - scope_fn(ScopeParent, Fn); +scope_fnbody(Scope, Scope):-cfa_parent(Scope, function(_)). +scope_fnbody(Scope, FnBody):- + scope_fnbody(ScopeParent, FnBody); cfa_parent(Scope, scope(ScopeParent)). latex_parameters_offset(1000). diff --git a/scripts/cfa/payload.lp b/scripts/cfa/payload.lp new file mode 100644 index 0000000..99662e1 --- /dev/null +++ b/scripts/cfa/payload.lp @@ -0,0 +1,68 @@ +%cfa_seq(From, To) +%cfa_payload(X, Node, Path) + + %EXTERNAL CALL + %constraints: fn's entry/final scope does not have prev/next scopes resp. +:- cfa_seq_guarded(_, NodeTo, in(_)); cfa_seq(_, NodeTo). +:- cfa_seq_guarded(NodeFrom, _, out(_)); cfa_seq(NodeFrom, _). + +cfa_payload(P, NodeTo, (Guard, Path)):- + cfa_payload(P, NodeFrom, Path); + cfa_seq_guarded(NodeFrom, NodeTo, in(Guard)). + +weak(cfa_payload(P, NodeTo, (Guard, Path))):- + weak(cfa_payload(P, NodeFrom, Path)); + cfa_seq_guarded(NodeFrom, NodeTo, in(Guard)). + + %Path collapse +cfa_payload(P, Node, Path):- + cfa_payload(P, NodeFrom, Path) : cfa_seq_guarded(NodeFrom, Node, in(_)); + cfa_payload(P, Node, (_, Path)); + cfa_seq_guarded(_, Node, in(_)). + + %EXTERNAL RET +cfa_payload(P, NodeTo, Path2):- + cfa_payload(P, NodeFrom, Path); Path = (Guard, Path2); + cfa_seq_guarded(NodeFrom, NodeTo, out(Guard)). + +cfa_payload(P, NodeTo, ()):- + cfa_payload(P, NodeFrom, ()); + cfa_seq_guarded(NodeFrom, NodeTo, out(_)). + +weak(cfa_payload(P, NodeTo, Path2)):- + weak(cfa_payload(P, NodeFrom, Path)); Path = (Guard, Path2); + cfa_seq_guarded(NodeFrom, NodeTo, out(Guard)). + + %INTERNAL +weak(cfa_payload(P, Node, Path)):- + weak(cfa_payload(P, NodeFrom, Path)); + cfa_seq(NodeFrom, Node). + + %INTERNAL AND +cfa_payload(P, Node, Path):- + cfa_payload(P, NodeFrom, Path); + cfa_seq(NodeFrom, Node); Node = and(_). + + + %INTERNAL OR +weak(cfa_payload(P, Node, Path)):- + cfa_payload(P, NodeFrom, Path); + cfa_seq(NodeFrom, Node); Node = or(_). + +cfa_payload(P, Node, Path):- + cfa_payload(P, NodeFrom, Path) : cfa_seq(NodeFrom, Node); + Node = or(_); + cfa_seq(N, Node); cfa_payload(P, N, Path). + + %INTERNAL EMPTY + %INTERNAL SCOPE +:- cfa_seq(A, empty(X)); cfa_seq(B, empty(X)); A<>B. +:- cfa_seq(A, scope(X)); cfa_seq(B, scope(X)); A<>B. + +cfa_payload(P, Node, Path):- + cfa_payload(P, NodeFrom, Path); + cfa_seq(NodeFrom, Node); Node = empty(_). + +cfa_payload(P, Node, Path):- + cfa_payload(P, NodeFrom, Path); + cfa_seq(NodeFrom, Node); Node = scope(_). diff --git a/scripts/exploitation/exploitation.lp b/scripts/exploitation/exploitation.lp index d4643a3..fc4d7ee 100644 --- a/scripts/exploitation/exploitation.lp +++ b/scripts/exploitation/exploitation.lp @@ -1,86 +1,24 @@ -% INPUT: -% cfa: cfa_forwdom -% expl_siteUser(Resource, UserScope), expl_siteInit(Resource, ScopeInit) -% - - -% PARTITION -%============================================================= -expl_mutual_dom(UserScope1, UserScope2, DomHighest):- - Ahighest = #max{ AD, (AD, BD): cfa_forwdom(Dom, range(AD, BD)), AD B1, BD > B2}; - cfa_forwdom(DomHighest, range(Ahighest, _)); - cfa_forwdom(UserScope1, range(A1, B1)); - cfa_forwdom(UserScope2, range(A2, B2)); - UserScope1B1}; - cfa_forwdom(DomHighest, range(Ahighest, _)); - cfa_forwdom(UserRoot, range(A1, B1)); - not expl_partition(Resource, UserRoot, _, _); - expl_partition_root(Resource, UserRoot). - -expl_init_assignments(Resource, SiteInitAssigned):- - A_Highest = #max{AI, (AI, BI): expl_siteInit(Resource, SiteI), cfa_forwdom(SiteI, range(AI, BI))}; - cfa_forwdom(SiteInitAssigned, range(A_Highest, _)); - expl_partition_root(Resource, _). - -% SOLUTIONS -%============================================================= - - -% ORDER -%============================================================= - +%DOMINATOR ANALYSIS BASED ON PAYLOAD +%=========================================================== +cfa_payload(expl_siteInit(Resource, Scope), scope(Scope), ()):- + expl_siteInit(Resource, Scope). -% Doms/PostDom trees -%============================================================= -%cfa_forwdom - - -% LANDSCAPE -%============================================================= -%expl_landscape(X, ) - - -% GARBAGE -%============================================================= -%expl_parent(Site, Parent):- -% A Scope. + + +%ASSIGNMENTS +%=========================================================== + +expl_assignments(Init, Resource, init):- + expl_siteUser(Resource, User); + cfa_payload(expl_siteInit(Resource, Init), scope(User), ()); + expl_supdom(Resource, Init). + +expl_assignments(Init, Resource, none):- + expl_siteInit(Resource, Init); + not expl_assignments(Init, Resource, init). diff --git a/scripts/exploitation/test1.assembly.lp b/scripts/exploitation/test1.assembly.lp index 7fcdb32..21efa4f 100644 --- a/scripts/exploitation/test1.assembly.lp +++ b/scripts/exploitation/test1.assembly.lp @@ -1,27 +1,24 @@ -% INPUT +% Connect to Exploitation %=========================================================== -expl_siteUser(Res, Scope):- - dictVarScope(Var, Scope); - bind(Var, expl_user(Res)). +expl_siteInit(Resource, CallerS):- + bind_func(Fn, init(Resource)); + cfa_call(CallerS, Fn). -expl_siteInit(Res, Scope):- - dictVarScope(Var, Scope); - bind(Var, expl_init(Res)). +expl_siteUser(Resource, Scope):- + bind(V, use(Resource)); + var_scope(V, Scope). -% OUTPUT +% Connect to Polymorphism %=========================================================== -dfa_callguard(Var, explInitRealImpl):- - expl_init_assignments(Res, SiteInitAssigned); - bind(Var, expl_init(Res)); - dictVarScope(Var, SiteInitAssigned). - -dfa_callguard(Var, explInitBogusImpl):- - not expl_init_assignments(Res, SiteInit); - bind(Var, expl_init(Res)); - dictVarScope(Var, SiteInit). +dfa_callguard(V, exploitation(Strategy)):- + expl_assignments(Scope, Resource, Strategy); + dfa_callfn(V, Fn); + bind_func(Fn, init(Resource)); + var_scope(V, Scope). + -% GENERAL +% Utility %=========================================================== -dictVarScope(Var, Scope):- Var=s(_, _, Scope); v(Var). +var_scope(Var, Scope):- Var=s(_, _, Scope); v(Var). diff --git a/scripts/exploitation/test1.xreate b/scripts/exploitation/test1.xreate index 75dc1a5..4406768 100644 --- a/scripts/exploitation/test1.xreate +++ b/scripts/exploitation/test1.xreate @@ -1,32 +1,9 @@ interface(extern-c){ xml2 = library:: pkgconfig("libxml-2.0"). include { xml2 = {"scripts/exploitation/test1.h"} }. } -import raw ("scripts/exploitation/exploitation.lp"). -import raw ("scripts/exploitation/test1.assembly.lp"). - -guard:: explInitRealImpl { - openFile = function(filePrev:: FILE_P):: FILE_P { - fopen("/tmp/test", "w")::FILE_P - } -} - -guard:: explInitBogusImpl { - openFile = function(filePrev:: FILE_P):: FILE_P { - filePrev::int - } -} - -test = function::int; entry { - seq - { f0 = undef:: FILE_P. f0 } - { f1 = openFile(f0):: FILE_P; expl_init(r1). f1 /*first attempt to open file*/} - { f2 = openFile(f1):: FILE_P; expl_init(r1). f2 /*second attempt to open file*/} - { sizeWritten = fwrite("WriteAttempt", 12, 1, f2):: int; expl_user(r1). sizeWritten } - { fclose(f2)::int; expl_use(r1)} - { sizeWritten :: int} -} + diff --git a/scripts/virtualization/test1.h b/scripts/virtualization/defs.h similarity index 100% rename from scripts/virtualization/test1.h rename to scripts/virtualization/defs.h diff --git a/scripts/virtualization/test-AccControl_1.xreate b/scripts/virtualization/test-AccControl_1.xreate new file mode 100644 index 0000000..32bd0a0 --- /dev/null +++ b/scripts/virtualization/test-AccControl_1.xreate @@ -0,0 +1,9 @@ +interface(extern-c){ + externalLibs = library:: pkgconfig("libxml-2.0"). + + include { + externalLibs = {"scripts/virtualization/defs.h"} + }. +} + + diff --git a/scripts/virtualization/test-IsolationCat_1.assembly.lp b/scripts/virtualization/test-IsolationCat_1.assembly.lp new file mode 100644 index 0000000..a11434c --- /dev/null +++ b/scripts/virtualization/test-IsolationCat_1.assembly.lp @@ -0,0 +1,40 @@ +% Register late query for `sizo_current` +%----------------------------------- +late(Target, SymbolSizo, (SizoAny), sizo_current(SizoAny)):- + bind(Target, demand(sizo)); + Target=s(_, _, TargetS); + scope_fnbody(TargetS, FnBody); + latex_symbol(FnBody, sizo, SymbolSizo); + virt_sizo(SizoAny). + + +% Categories Reasoning +%=========================================================== . +virt_sizo_category(Sizo, Category):- + bind_scope(Scope, assign_sizo_category(Category), strong); + bind_scope(Scope, assign_sizo(Sizo), strong); + virt_sizo(Sizo). + +2{ + virt_sizo_strategy(SizoOther, files, prefix); + decided(virt_strategy(SizoOther, files), 3;2) +}:- + virt_sizo_control(SizoSelf, files); + virt_sizo_category(SizoSelf, inward); + + virt_sizo_control(SizoOther, files); + SizoOther <> SizoSelf. + +2{ + virt_sizo_strategy(SizoSelf, files, prefix); + decided(virt_strategy(SizoSelf, files), 3;2) +}:- + virt_sizo_control(SizoSelf, files); + virt_sizo_category(SizoSelf, outward). + +2{ + virt_sizo_strategy(Sizo, files, direct); + decided(virt_strategy(Sizo, files), 2) +}:- + virt_sizo_control(Sizo, files); + not decided(virt_strategy(Sizo, files), 3). diff --git a/scripts/virtualization/test-IsolationCat_1.xreate b/scripts/virtualization/test-IsolationCat_1.xreate new file mode 100644 index 0000000..df32737 --- /dev/null +++ b/scripts/virtualization/test-IsolationCat_1.xreate @@ -0,0 +1,53 @@ +interface(extern-c){ + externalLibs = library:: pkgconfig("libxml-2.0"). + + include { + externalLibs = {"scripts/virtualization/defs.h"} + }. +} + +import raw ("scripts/cfa/context.lp"). //enable context reasoning +import raw ("scripts/virtualization/virtualization.lp"). //enable virtualization reasoning +import raw ("scripts/virtualization/test-IsolationCat_1.assembly.lp"). //additional configuration + +DictSizo = type slave dict_sizo. +Sizo = type slave virt_sizo. + +guard:: strategy(direct) +{ + resolveFilename = function(filename:: string):: string; + assign_zek_access(files) + { + filename + } +} + +guard:: strategy(prefix) +{ + resolveFilename = function(filename:: string):: string; + assign_zek_access(files) + { + dictSizo = intrinsic query("dict_sizo")::[DictSizo]. + sizoId = intrinsic query late("sizo_current"->sizoCurrent:: Sizo):: int; + demand(sizo) + { + loop fold(dictSizo->entry::DictSizo, 0->id):: int + { + if(entry[0] == sizoCurrent):: int { entry[1] } else { id } + } + }. + + buf = "00"::string. + seq + { sprintf(buf, "%d/%s", sizoId, filename) } + { buf } + } +} + +openFile = function(filename:: string):: int +{ + filenameReal = resolveFilename(filename):: string. + printf("File opened: '%s'%c", filenameReal, 10) +} + + diff --git a/scripts/virtualization/test-Isolation_1.assembly.lp b/scripts/virtualization/test-Isolation_1.assembly.lp new file mode 100644 index 0000000..908391e --- /dev/null +++ b/scripts/virtualization/test-Isolation_1.assembly.lp @@ -0,0 +1,8 @@ +% Register late query for `sizo_current` +%----------------------------------- +late(Target, SymbolSizo, (SizoAny), sizo_current(SizoAny)):- + bind(Target, demand(sizo)); + Target=s(_, _, TargetS); + scope_fnbody(TargetS, FnBody); + latex_symbol(FnBody, sizo, SymbolSizo); + virt_sizo(SizoAny). diff --git a/scripts/virtualization/test-Isolation_1.xreate b/scripts/virtualization/test-Isolation_1.xreate new file mode 100644 index 0000000..4fe8fae --- /dev/null +++ b/scripts/virtualization/test-Isolation_1.xreate @@ -0,0 +1,10 @@ +interface(extern-c){ + externalLibs = library:: pkgconfig("libxml-2.0"). + + include { + externalLibs = {"scripts/virtualization/defs.h"} + }. +} + + + diff --git a/scripts/virtualization/test1.assembly.lp b/scripts/virtualization/test1.assembly.lp deleted file mode 100644 index 91f2ae1..0000000 --- a/scripts/virtualization/test1.assembly.lp +++ /dev/null @@ -1,35 +0,0 @@ -% INPUT -%----------------------------------- -% sizo(..). - -sizo(Sizo):- - bind_scope(_, attachedSizo(Sizo), strong). - -dict_sizo(Sizo, Id):- - Id= #sum{ 1, SizoLess : sizo(SizoLess), SizoLess < Sizo}; - sizo(Sizo). - -% connect to latex -%----------------------------------- -latex_registered_subjects(sizo, Sizo):- sizo(Sizo). - -latex_scope_demand(ScopeDemandSizo, sizo):- - bind(Target, demand(sizo)); - Target = s(_, _, ScopeDemandSizo). - -bind_scope(Scope, Sizo, strong):- - bind_scope(Scope, attachedSizo(Sizo), strong). - -% register late query -%----------------------------------- -late(Target, SymbolSizo, (SizoAny), sizo_current(SizoAny)):- - bind(Target, demand(sizo)); - Target=s(_, _, TargetS); - scope_fn(TargetS, Fn); - cfa_parent(FnBody, function(Fn)); - latex_symbol(Fn, sizo, SymbolSizo); - sizo(SizoAny). - - -% IMPLEMENTATION -%=========================================================== . diff --git a/scripts/virtualization/test1.xreate b/scripts/virtualization/test1.xreate deleted file mode 100644 index 3ad7ce8..0000000 --- a/scripts/virtualization/test1.xreate +++ /dev/null @@ -1,47 +0,0 @@ -interface(extern-c){ - externalLibs = library:: pkgconfig("libxml-2.0"). - - include { - externalLibs = {"scripts/virtualization/test1.h"} - }. -} - -import raw ("scripts/virtualization/test1.assembly.lp"). -import raw ("scripts/cfa/context.lp"). - -DictSizo = type slave dict_sizo. -Sizo = type slave sizo. - -virt_getPrefix = function:: string -{ - dictSizo = intrinsic query("dict_sizo")::[DictSizo]. - - sizoId = intrinsic query late("sizo_current"->sizoCurrent:: Sizo):: int; demand(sizo) - { - loop fold(dictSizo->entry::DictSizo, 0->id):: int { - if(entry[0] == sizoCurrent):: int { entry[1] } else { id } - } - }. - - buf = "000000000"::string. - seq - { sprintf(buf, "%d", sizoId) } - { buf } -} - -openFile = function(filename::string):: int -{ - buf = "0000000000":: string. - prefix = virt_getPrefix():: string. - seq - {sprintf(buf, "/%s/%s", prefix, filename)} - {printf("file opened: %s ", buf)} -} - -main = function:: int; entry -{ - seq - { context::attachedSizo(domainA). openFile("test1") } - { context::attachedSizo(domainB). openFile("test1") } - { 0 } -} diff --git a/scripts/virtualization/test2.assembly.lp b/scripts/virtualization/test2.assembly.lp deleted file mode 100644 index 8ce61dc..0000000 --- a/scripts/virtualization/test2.assembly.lp +++ /dev/null @@ -1,45 +0,0 @@ -% INPUT -%----------------------------------- -% assign_sizo(..). - -sizo(Sizo):- - bind_scope(_, assign_sizo(Sizo), strong). - -dict_sizo(Sizo, Id):- - Id= #sum{ 1, SizoLess : sizo(SizoLess), SizoLess < Sizo}; - sizo(Sizo). - -% connect to latex -%----------------------------------- -latex_registered_subjects(sizo, Sizo):- sizo(Sizo). - -latex_scope_demand(ScopeDemandSizo, sizo):- - bind(Target, demand(sizo)); - Target = s(_, _, ScopeDemandSizo). - -bind_scope(Scope, Sizo, strong):- - bind_scope(Scope, assign_sizo(Sizo), strong). - -% register late query -%----------------------------------- -late(Target, SymbolSizo, (SizoAny), sizo_current(SizoAny)):- - bind(Target, demand(sizo)); - Target=s(_, _, TargetS); - scope_fn(TargetS, Fn); - latex_symbol(Fn, sizo, SymbolSizo); - sizo(SizoAny). - -% polymorphism based on virtualizaion strategy -%----------------------------------- -dfa_callguard(SymbRet, strategy(Strategy)):- - dfa_callfn(SymbRet, FnName); - bind_func(FnName, requires(virt_dereference_strategy)); - virt_dereference_strategy(Strategy). - - -% IMPLEMENTATION -%=========================================================== . -virt_dereference_strategy(prefix) :- 2 #count{Sizo: sizo(Sizo)}. -virt_dereference_strategy(none) :- not virt_dereference_strategy(prefix). - - diff --git a/scripts/virtualization/test2.xreate b/scripts/virtualization/test2.xreate deleted file mode 100644 index 0051bd4..0000000 --- a/scripts/virtualization/test2.xreate +++ /dev/null @@ -1,57 +0,0 @@ -interface(extern-c){ - externalLibs = library:: pkgconfig("libxml-2.0"). - - include { - externalLibs = {"scripts/virtualization/test1.h"} - }. -} - -import raw ("scripts/virtualization/test2.assembly.lp"). -import raw ("scripts/cfa/context.lp"). - -DictSizo = type slave dict_sizo. -Sizo = type slave sizo. - -guard:: strategy(prefix) -{ - virt_dereferenceFilename = function(filename:: string):: string; requires(virt_dereference_strategy) - { - dictSizo = intrinsic query("dict_sizo")::[DictSizo]. - - sizoId = intrinsic query late("sizo_current"->sizoCurrent:: Sizo):: int; demand(sizo) - { - loop fold(dictSizo->entry::DictSizo, 0->id):: int - { - if(entry[0] == sizoCurrent):: int { entry[1] } else { id } - } - }. - - buf = "000000000"::string. - seq - { sprintf(buf, "%d/%s", sizoId, filename) } - { buf } - } -} - -guard:: strategy(none) -{ - virt_dereferenceFilename = function(filename:: string):: string; requires(virt_dereference_strategy) - { - filename - } -} - -virt_openFile = function(filename:: string):: int -{ - filenameReal = virt_dereferenceFilename(filename):: string. - seq{printf("file opened: %s ", filenameReal)} -} - -main = function:: int; entry -{ - seq - { context::assign_sizo(domainA). virt_openFile("test1") } - { context::assign_sizo(domainA). virt_openFile("test1") } - { 0 } -} - diff --git a/scripts/virtualization/test3.assembly.lp b/scripts/virtualization/test3.assembly.lp deleted file mode 100644 index cb7af52..0000000 --- a/scripts/virtualization/test3.assembly.lp +++ /dev/null @@ -1,63 +0,0 @@ -% INPUT -%----------------------------------- -% assign_sizo(..). - -sizo(Sizo):- - bind_scope(_, assign_sizo(Sizo), strong). - -dict_sizo(Sizo, Id):- - Id= #sum{ 1, SizoLess : sizo(SizoLess), SizoLess < Sizo}; - sizo(Sizo). - -% connect to latex -%----------------------------------- -latex_registered_subjects(sizo, Sizo):- sizo(Sizo). - -latex_scope_demand(ScopeDemandSizo, sizo):- - bind(Target, demand(sizo)); - Target = s(_, _, ScopeDemandSizo). - -bind_scope(Scope, Sizo, strong):- - bind_scope(Scope, assign_sizo(Sizo), strong). - -% register late query -%----------------------------------- -late(Target, SymbolSizo, (SizoAny), sizo_current(SizoAny)):- - bind(Target, demand(sizo)); - Target=s(_, _, TargetS); - scope_fn(TargetS, Fn); - latex_symbol(Fn, sizo, SymbolSizo); - sizo(SizoAny). - -% polymorphism based on virtualizaion strategy -%----------------------------------- -late(SymbRet, SymbolSizo, Sizo, dfa_callguard(SymbRet, strategy(Strategy))):- - dfa_callfn(SymbRet, FnName); - bind_func(FnName, requires(virt_dereference_strategy)); - SymbRet=s(_, _, ScopeCaller); - scope_fn(ScopeCaller, Fn); - latex_symbol(Fn, sizo, SymbolSizo); - sizo(Sizo); - virt_dereference_strategy(Sizo, Strategy). - - -% IMPLEMENTATION -%=========================================================== . - -sizo_properties(Sizo, Prop):- - bind_scope(Scope, define_sizo_prop(Prop), strong); - bind_scope(Scope, Sizo, strong); - sizo(Sizo). - -virt_dereference_strategy(SizoOther, prefix):- - sizo_properties(Sizo, inner); - SizoOther <> Sizo; - sizo(SizoOther). - -virt_dereference_strategy(Sizo, prefix):- - sizo_properties(Sizo, outer). - -virt_dereference_strategy(Sizo, none) :- - not virt_dereference_strategy(Sizo, prefix); - sizo(Sizo). - diff --git a/scripts/virtualization/test3.xreate b/scripts/virtualization/test3.xreate deleted file mode 100644 index 468a25d..0000000 --- a/scripts/virtualization/test3.xreate +++ /dev/null @@ -1,57 +0,0 @@ -interface(extern-c){ - externalLibs = library:: pkgconfig("libxml-2.0"). - - include { - externalLibs = {"scripts/virtualization/test1.h"} - }. -} - -import raw ("scripts/virtualization/test3.assembly.lp"). -import raw ("scripts/cfa/context.lp"). - -DictSizo = type slave dict_sizo. -Sizo = type slave sizo. - -guard:: strategy(prefix) -{ - virt_dereferenceFilename = function(filename:: string):: string; requires(virt_dereference_strategy) - { - dictSizo = intrinsic query("dict_sizo")::[DictSizo]. - - sizoId = intrinsic query late("sizo_current"->sizoCurrent:: Sizo):: int; demand(sizo) - { - loop fold(dictSizo->entry::DictSizo, 0->id):: int - { - if(entry[0] == sizoCurrent):: int { entry[1] } else { id } - } - }. - - buf = "000000000"::string. - seq - { sprintf(buf, "%d/%s", sizoId, filename) } - { buf } - } -} - -guard:: strategy(none) -{ - virt_dereferenceFilename = function(filename:: string):: string; requires(virt_dereference_strategy) - { - filename - } -} - -virt_openFile = function(filename:: string):: int -{ - filenameReal = virt_dereferenceFilename(filename):: string. - printf("file opened: %s ", filenameReal) -} - -main = function:: int; entry -{ - seq - { context::assign_sizo(domainA); define_sizo_prop(inner). virt_openFile("test1") } - { context::assign_sizo(domainB); define_sizo_prop(outer). virt_openFile("test1") } - { 0 } -} - diff --git a/scripts/virtualization/virtualization.lp b/scripts/virtualization/virtualization.lp new file mode 100644 index 0000000..2fa8f73 --- /dev/null +++ b/scripts/virtualization/virtualization.lp @@ -0,0 +1,63 @@ +virt_sizo(Sizo):- + bind_scope(_, assign_sizo(Sizo), strong). + +virt_resource(files). + +virt_sizo_control(Sizo, Resource):- + bind_scope(Scope, assign_sizo_control(Resource), strong); + bind_scope(Scope, assign_sizo(Sizo), strong). + +% Decisions +%----------------------------------- +virt_sizo_strategy(Sizo, Resource, direct):- + not virt_sizo_control(Sizo, Resource); + virt_resource(Resource); + virt_sizo(Sizo). + +activate_strategy_prefix(prefix) :- + 2 #count{Sizo: virt_sizo_control(Sizo, files)}. + +virt_sizo_strategy(Sizo, files, prefix):- + activate_strategy_prefix(prefix); + virt_sizo_control(Sizo, files); + not decided(virt_strategy(Sizo, files), 2). + +virt_sizo_strategy(Sizo, Resource, common):- + virt_sizo_control(Sizo, Resource); + not virt_sizo_strategy(Sizo, Resource, prefix); + not decided(virt_strategy(Sizo, files), 2). + + +dict_sizo(Sizo, Id):- + Id= #sum{ 1, SizoLess : virt_sizo(SizoLess), SizoLess < Sizo}; + virt_sizo(Sizo). + +% Connect to Latex +%----------------------------------- +latex_registered_subjects(sizo, Sizo):- virt_sizo(Sizo). + +latex_scope_demand(ScopeDemandSizo, sizo):- + bind(Target, demand(sizo)); + Target = s(_, _, ScopeDemandSizo). + +bind_scope(Scope, Sizo, strong):- + bind_scope(Scope, assign_sizo(Sizo), strong). + +% Polymorphism based on virtualizaion strategy +%----------------------------------- +dfa_callguard(SymbRet, strategy(Strategy)):- + dfa_callfn(SymbRet, Fn); + bind_func(Fn, assign_zek_access(Resource)); + SymbRet = s(_, _, Scope); + bind_scope(Scope, assign_sizo(Sizo), strong); + virt_sizo_strategy(Sizo, Resource, Strategy). + +late(SymbRet, SymbolSizo, Sizo, dfa_callguard(SymbRet, strategy(Strategy))):- + bind_func(FnName, assign_zek_access(Resource)); + virt_sizo_strategy(Sizo, Resource, Strategy); + + dfa_callfn(SymbRet, FnName); + SymbRet=s(_, _, ScopeCaller); + scope_fnbody(ScopeCaller, FnCallerBody); + latex_symbol(FnCallerBody, sizo, SymbolSizo); + virt_sizo(Sizo).