diff --git a/core/containers.lp b/core/containers.lp index 8a46e89..aa8e996 100644 --- a/core/containers.lp +++ b/core/containers.lp @@ -1,41 +1,40 @@ %1. Domain definitions: impl(solid; on_the_fly; linked_list). op(seqaccess; randaccess). relation(recommends; satisfied; unsupported). relation_score(satisfied, 0). relation_score(recommends, 1). score(0..1). %2. Domain facts: relation_op(seqaccess, on_the_fly, recommends). relation_op(randaccess, solid, recommends). relation_op(randaccess, on_the_fly, unsupported). bind(X, impl(solid)):- bind(X, dfa_operator(list)). bind(X, impl(on_the_fly)):- bind(X, dfa_operator(list)). - bind(X, op(seqaccess)) :- bind(X, dfa_operator(loop_fold)). - bind(X, op(randaccess)) :- bind(X, dfa_operator(index)). + bind(X, l0_op(seqaccess)) :- bind(X, dfa_operator(loop_fold)). + bind(X, l0_op0(randaccess)) :- bind(X, dfa_operator(index)). %5. Manual input %2. Supplies %4. Best implemetation search: score(op(OP), IMPL, SCORE):- SCORE = #sum{SCORE1, SCORE1: relation_score(RL, SCORE1), relation_op(OP, IMPL, RL)}; op(OP); impl(IMPL); not relation_op(OP, IMPL, unsupported). {score(v(VAR), IMPL, SCORE)}:- score(op(OP), IMPL, SCORE); bind(VAR, op(OP)); bind(VAR, impl(IMPL)). :- 2{score(v(VAR), IMPL, SCORE): v(VAR)}. #maximize { SCORE, (VAR, SCORE): score(v(VAR), _, SCORE) }. %5. Output - %resolution(var, impl) + bind_decision(VAR, SUBJECT, RESOLUTION) :- SUBJECT=implementation; RESOLUTION=IMPL; score(v(VAR), IMPL, _). - %1. DFA input v(a). bind(a, dfa_operator(list)). bind(a, dfa_operator(loop_fold)). diff --git a/cpp/src/clasplayer.cpp b/cpp/src/clasplayer.cpp index 76509c6..59eb970 100644 --- a/cpp/src/clasplayer.cpp +++ b/cpp/src/clasplayer.cpp @@ -1,279 +1,311 @@ #include "clasplayer.h" #include #include "utils.h" #include #include #include #include "analysis/aux.h" #include "analysis/DominatorsTreeAnalysisProvider.h" #include "analysis/cfagraph.h" #include "analysis/dfagraph.h" using namespace std; //TODO escape identifiers started from upper case symbol namespace xreate { void ClaspLayer::printWarnings(std::ostream& out) { const std::string warningTag = "warning"; auto warningsRange = __model.equal_range(warningTag); for (auto warning=warningsRange.first; warning!= warningsRange.second; ++warning) { unsigned int warningId; Gringo::Symbol params; std::tie(warningId, params) = parse(warning->second); cout << "Warning: " << __warnings.at(warningId) << " "; params.print(out); out< warnings; cout << "Model: " << endl; const string& atomBindVar = Config::get("clasp.bindings.variable"); const string& atomBindFunc = Config::get("clasp.bindings.function"); const string& atomBindScope = Config::get("clasp.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 name = std::get<1>(parse(atom)).name().c_str(); __model.emplace(move(name), move(atom)); } __model.emplace(atomName, move(atom)); } return true; } void ClaspLayer::setCFAData(xreate::analysis::CFAGraph* graph) { dataCFA.reset(graph); } void ClaspLayer::setDFAData(xreate::analysis::DFAGraph* graph){ dataDFA.reset(graph); } void ClaspLayer::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, ", ")) <__rawImports) { std::ifstream file(fn); if (!file) continue; while(!file.eof()){ string line; std::getline(file, line); out << line << endl; } } } void ClaspLayer::addRawScript(std::string&& script){ __partGeneral << script; } void ClaspLayer::run() { involveImports(); if (this->dataDFA){ this->dataDFA->print(__partGeneral); } if (this->dataCFA){ this->dataCFA->print(__partGeneral); } DominatorsTreeAnalysisProvider providerDominators; providerDominators.run(this); providerDominators.print(__partGeneral); 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->handleSolution(model); return true; }, {}); if (result.satisfiable() == Gringo::SolveResult::Satisfiable) { cout << FGRN("SUCCESSFULLY") << endl; } else { cout << FRED("UNSUCCESSFULLY") << endl; } // invoke all query plugins to process clasp data for (auto q: __queries) { q.second->init(this); } } + bool + ClaspLayer::checkScript(std::string&& script, std::string&& atomCheckSuccess){ + //init + + 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); + + bool flagCheck = false; + Gringo::SolveResult result = ctl.solve([this, &flagCheck, const &atomCheckSuccess](Gringo::Model const &model) { + for (Gringo::Symbol atom : model.atoms(clingo_show_type_atoms)) { + + string atomName(atom.name().c_str()); + if (atomName == atomCheckSuccess){ + flagCheck = true; + break; + } + + return true; + }}, {}); + + if (!result.satisfiable()){ + return false; + } + + return flagCheck + } + ClaspLayer::ClaspLayer() { } ClaspLayer::ModelFragment ClaspLayer::query(const std::string& atom) { if (! __model.count(atom)){ return boost::none; } return ModelFragment(__model.equal_range(atom)); } ScopePacked ClaspLayer::pack(CodeScope* const scope) { auto pos = __indexScopes.emplace(scope, __indexScopes.size()); if (pos.second) __registryScopes.push_back(scope); return pos.first->second; } size_t ClaspLayer::getScopesCount() const{ return __registryScopes.size(); } SymbolPacked ClaspLayer::pack(const Symbol& symbol, std::string hintSymbolName) { SymbolPacked result; result.scope = pack(symbol.scope); result.identifier = symbol.identifier; __indexSymbolNameHints.emplace(result, hintSymbolName); return result; } Symbol ClaspLayer::unpack(const SymbolPacked& symbol) { return Symbol{symbol.identifier, __registryScopes[symbol.scope]}; }; std::string ClaspLayer::getHintForPackedSymbol(const SymbolPacked& symbol){ if (!symbol.categoryTransient) { auto result = __indexSymbolNameHints.find(symbol); return (result == __indexSymbolNameHints.end())? "" : result->second; } else { return "anonym(" + to_string(symbol.identifier) + ")"; } } bool operator==(const SymbolPacked& s1, const SymbolPacked& s2) { return s1.identifier == s2.identifier && s1.scope == s2.scope; } bool operator<(const SymbolPacked& s1, const SymbolPacked& s2) { return s1.scope < s2.scope || (s1.scope == s2.scope && s1.identifier < s2.identifier); } IQuery* ClaspLayer::registerQuery(IQuery *query, const QueryId& id) { return __queries.emplace(id, query).first->second; } IQuery* ClaspLayer::getQuery(const QueryId& id){ assert(__queries.count(id) && "Undefined query"); return __queries.at(id); } } diff --git a/cpp/src/clasplayer.h b/cpp/src/clasplayer.h index ad8da19..4c9ee84 100644 --- a/cpp/src/clasplayer.h +++ b/cpp/src/clasplayer.h @@ -1,227 +1,228 @@ #ifndef CLASPLAYER_H #define CLASPLAYER_H #include "ast.h" #include "contextrule.h" #include #include #include #include #include #include #include #include namespace xreate { typedef unsigned int ScopePacked; struct SymbolPacked { VID identifier; ScopePacked scope; bool categoryTransient = false; }; bool operator==(const SymbolPacked& s1, const SymbolPacked& s2); bool operator<(const SymbolPacked& s1, const SymbolPacked& s2); enum class DFGConnection { STRONG, WEAK, PROTOTYPE }; class IAnalysisData { public: void print(std::ostringstream& output) const; virtual ~IAnalysisData(){}; }; class IQuery { public: virtual void init(ClaspLayer* clasp) = 0; virtual ~IQuery() {} }; enum class QueryId { ContainersQuery, ContextQuery, PtrvalidQuery }; namespace analysis{ class DFAGraph; class CFAGraph; } class ClaspLayer { friend class ContextRule; //PROVIDERS: public: boost::scoped_ptr dataDFA; void setDFAData(xreate::analysis::DFAGraph* graph); boost::scoped_ptr dataCFA; void setCFAData(xreate::analysis::CFAGraph* graph); void addRawScript(std::string&& script); private: void involveImports(); //QUERIES public: IQuery* registerQuery(IQuery* query, const QueryId& id); IQuery* getQuery(const QueryId& id); template static std::tuple parse(const Gringo::Symbol& atom); typedef std::multimap::const_iterator ModelIterator; typedef boost::optional> ModelFragment; ModelFragment query(const std::string& atom); size_t getScopesCount() const; SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName = ""); ScopePacked pack(CodeScope * const scope); Symbol unpack(const SymbolPacked& symbol); std::string getHintForPackedSymbol(const SymbolPacked& symbol); private: std::map __queries; std::multimap __model; std::map __indexSymbolNameHints; std::unordered_map __indexScopes; std::vector __registryScopes; //WARNINGS //TODO move to separate provider/query public: void addRuleWarning(const RuleWarning &rule); unsigned int registerWarning(std::string &&message); private: std::map __warnings; void printWarnings(std::ostream& out); //DEFAULT public: AST *ast; ClaspLayer(); void run(); + bool checkScript(std::string&& script, std::string&& atomCheckSuccess); private: std::ostringstream __partTags; std::ostringstream __partGeneral; bool handleSolution(Gringo::Model const &model); }; template struct ParseImplAtom { static typ get(const Gringo::Symbol& atom) { return atom.num(); } }; template<> struct ParseImplAtom { static std::string get(const Gringo::Symbol& atom) { switch (atom.type()) { case Gringo::SymbolType::Str: return atom.string().c_str(); case Gringo::SymbolType::Fun: return atom.name().c_str(); default: break; } assert(false && "Inappropriate symbol type"); } }; template<> struct ParseImplAtom { static SymbolPacked get(const Gringo::Symbol& atom) { auto result = ClaspLayer::parse(atom); return SymbolPacked{std::get<0>(result), std::get<1>(result)}; } }; template<> struct ParseImplAtom { static Gringo::Symbol get(const Gringo::Symbol& atom) { return atom; } }; template<> struct ParseImplAtom { static Expression get(const Gringo::Symbol& atom) { switch (atom.type()) { case Gringo::SymbolType::Num: return Expression(atom.num()); case Gringo::SymbolType::Str: return Expression(std::string(atom.string().c_str())); case Gringo::SymbolType::Fun: { //ID if (!atom.args().size){ return Expression(std::string(atom.name().c_str())); } //FUNC Expression result(Operator::CALL,{Expression(std::string(atom.name().c_str()))}); for (const Gringo::Symbol& arg : atom.args()) { result.addArg(ParseImplAtom::get(arg)); } return result; } default: { assert(false); } } } }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { const size_t tupleSize = std::tuple_size::value; typedef typename std::tuple_element < tupleSize - index, Tuple>::type ElType; ElType& el = std::get < tupleSize - index > (tup); Gringo::Symbol atom = *arg; el = ParseImplAtom::get(atom); Parse_Impl ::parse(tup, ++arg); } }; template struct Parse_Impl { static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) { } }; template std::tuple ClaspLayer::parse(const Gringo::Symbol& atom) { typedef std::tuple < Types...> Tuple; Tuple tup; Parse_Impl::value>::parse(tup, atom.args().first); return tup; } } #endif diff --git a/cpp/tests/containers.cpp b/cpp/tests/containers.cpp index 9d044d5..d5cdf0e 100644 --- a/cpp/tests/containers.cpp +++ b/cpp/tests/containers.cpp @@ -1,96 +1,124 @@ /* * containers.cpp * * Created on: Jun 9, 2015 * Author: pgess */ #include "passmanager.h" #include "query/containers.h" #include "Parser.h" #include "gtest/gtest.h" using namespace std; using namespace xreate; using namespace containers; TEST(Containers, ListAsArray){ PassManager* man = PassManager::prepareForCode( R"Code( main = function(x:: int):: int;entry { a = [1, 2, 3]:: [int]. a[x] } )Code" ); void* mainPtr = man->run(); int (*main)(int) = (int (*)(int))mainPtr; ASSERT_EQ(2, main(1)); delete man; } TEST(Containers, ListAsArray2){ PassManager* man = PassManager::prepareForCode( R"Code( main = function:: int;entry { a= [1, 2, 3]:: [int]. b= loop map(a->el:: int):: [int]{ 2 * el }. sum = loop fold(b->el:: int, 0->acc):: int { acc + el }. sum } )Code" ); void* mainPtr = man->run(); int (*main)() = (int (*)())mainPtr; ASSERT_EQ(0, main()); delete man; } + + +//TEST(){ +// function test1(i:: num):: num{ +// a = [1..10]:: [num]. +// +// b = loop map(a->el:: num):: [num]{ +// a * a +// } +// +// b[i] +// } +// +// function test2(){ +// a= [1..10]:: [num]. +// +// b = loop map(a->el:: num):: [num]{ +// a * a +// } +// +// c = loop fold(b->el, 0->sum>)::num { +// sum + el +// } +// +// c +// } +//} + TEST(Containers, ContanierLinkedList1){ FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); Scanner scanner(input); Parser parser(&scanner); parser.Parse(); AST& ast = parser.root; CodeScope* body = ast.findFunction("test")->getEntryScope(); Symbol symb_chilrenRaw = body->findSymbol("childrenRaw"); containers::ImplementationLinkedList iLL(symb_chilrenRaw); ASSERT_EQ(true, static_cast(iLL)); ASSERT_EQ("next", iLL.fieldPointer); Implementation impl = Implementation::create(symb_chilrenRaw); ASSERT_NO_FATAL_FAILURE(impl.extract()); ImplementationRec recOnthefly = impl.extract(); ASSERT_EQ(symb_chilrenRaw, recOnthefly.source); } TEST(Containers, Implementation_LinkedListFull){ FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r"); assert(input != nullptr); std::unique_ptr program(PassManager::prepareForCode(input)); void* mainPtr = program->run(); int (*main)() = (int (*)())(intptr_t)mainPtr; int answer = main(); ASSERT_EQ(17, answer); fclose(input); } diff --git a/documentation/Concepts/containers.remarkup b/documentation/Concepts/containers.remarkup index 3e1602d..850f276 100644 --- a/documentation/Concepts/containers.remarkup +++ b/documentation/Concepts/containers.remarkup @@ -1,29 +1,62 @@ ==Introduction== A //Containers// is a general name for data structures intended to hold group of elements of certain type. Considering that almost every program needs containers to store, retrieve, search or otherwise process aggregate data, obviously efficiency of containers implementation is one of the top priorities for Xreate design. -Main idea behind containers in Xreate is to gather information on //how containers are used//, inferred from program sources. -On this ground it's possible to choose semi-automatically most appropriate data structure for container implementation to efficiently fullfil particular needs. +Main idea behind containers in Xreate is to gather information on //how containers are used//, by inferring from program sources. +On this ground it's possible to choose semi-automatically the most appropriate data structure for container implementation to efficiently fullfil particular needs. a= [1, 2, 3, 4, 5]:: [num]; impl(solid). //container definition b= a[0]:: num; op(randaccess). //operation on container In this example, definition of container(variable `a`) offers one or several implementations it supports, that is `impl(solid)` which is explicilty provided for clarity. On the other side, //retrieving by index// operation(variable `b`) demands certain implementations -to operate. Annotation `op(randaccess)` explicitly describes operation nature, i.e. it requires any data structure that supports //random access// . -Based on gathered information, most appropriate tradeoff //in supply and demand// is applied as given container implementation, i.e. `impl(solid)` in this simple case. +to operate on. Annotation `op(randaccess)` explicitly describes operation nature, i.e. it requires any data structure that supports //random access// . + +Based on gathered information, most appropriate tradeoff //in supply and demand// is assumed as implementation for a given container , i.e. `impl(solid)` in the case above. + +Here is a more complex example: + + function test1(i:: num):: num{ + a = [1..10]:: [num]. + + b = loop map(a->el:: num):: [num]{ + a * a + } + + b[i] + } + +Implementation of `b` assumed to be `impl(soild)` for index operation `b[i]` demands `randaccess` and `impl(solid)` is a most appropriate implementation operator `list` could provide(variable `a`). However, after slight changes as shown below + + function test2:: num { + a= [1..10]:: [num]. + + b = loop map(a->el:: num):: [num]{ + a * a + } + + c = loop fold(b->el, 0->sum>)::num { + sum + el + } + + c + } + +the situation is different. Definitions of `a` as well as `b` are intact, but there is different operaton over `b`, which is iterating to calculate sum of `b` elements. Iteration represented as `op(seqaccess)` depicting //sequental access// to a container data. Different container use leads implementation inference to a different outcomes, `impl(on_the_fly)` in this case. + +To conclude, the examples show ability to automatically reassign best suited implementations for a container variables reflecting how exactly variables are processed. In order to exppress possible and required implementations, describe operations, constraints and preferences an annotations are used, either manually provided or automatically inferred from program sources. ==Container definitions== ==Container operations== | `map` loop | `op(seqaccess)` | `impl(on_the_fly)`, `impl(solid)` | `fold` loop | `op(seqaccess)`| `impl(on_the_fly)`, `impl(solid)` | index retrieving | `op(randaccess` | `impl(solid)` \ No newline at end of file