diff options
author | Stefan Radomski <radomski@tk.informatik.tu-darmstadt.de> | 2014-10-20 07:20:16 (GMT) |
---|---|---|
committer | Stefan Radomski <radomski@tk.informatik.tu-darmstadt.de> | 2014-10-20 07:20:16 (GMT) |
commit | 59c9ae81b4911c6458cbe8a5ed78554bdcc82861 (patch) | |
tree | aab941294ccd67c8379f2dfb71ca107236d51f05 /src/uscxml | |
parent | 9ba649b087df2bc161759e55549facc2f8f80878 (diff) | |
download | uscxml-59c9ae81b4911c6458cbe8a5ed78554bdcc82861.zip uscxml-59c9ae81b4911c6458cbe8a5ed78554bdcc82861.tar.gz uscxml-59c9ae81b4911c6458cbe8a5ed78554bdcc82861.tar.bz2 |
SCXML -> Promela skips intermediate explicit flat SCXML for ridiculous better memory footprint
Diffstat (limited to 'src/uscxml')
17 files changed, 1731 insertions, 993 deletions
diff --git a/src/uscxml/CMakeLists.txt b/src/uscxml/CMakeLists.txt index 979f8fd..8e27980 100644 --- a/src/uscxml/CMakeLists.txt +++ b/src/uscxml/CMakeLists.txt @@ -45,7 +45,7 @@ if (NOT BUILD_MINIMAL) transform/*.h ) source_group("Interpreter" FILES ${USCXML_TRANSFORM}) - list (APPEND USCXML_FILES ${USCXML_TRANSFORM}) + list (APPEND USCXML_TRANSFORM_FILES ${USCXML_TRANSFORM}) endif() file(GLOB_RECURSE USCXML_INTERPRETERS @@ -109,4 +109,5 @@ SET(USCXML_LANGUAGE_BINDINGS ${USCXML_LANGUAGE_BINDINGS} PARENT_SCOPE) set(USCXML_INCLUDE_DIRS ${USCXML_INCLUDE_DIRS} PARENT_SCOPE) set(USCXML_OPT_LIBS ${USCXML_OPT_LIBS} PARENT_SCOPE) set(USCXML_FILES ${USCXML_FILES} PARENT_SCOPE) +set(USCXML_TRANSFORM_FILES ${USCXML_TRANSFORM_FILES} PARENT_SCOPE) SET(PLUMA ${PLUMA} PARENT_SCOPE)
\ No newline at end of file diff --git a/src/uscxml/Interpreter.cpp b/src/uscxml/Interpreter.cpp index 50917f3..717000e 100644 --- a/src/uscxml/Interpreter.cpp +++ b/src/uscxml/Interpreter.cpp @@ -487,56 +487,44 @@ Interpreter Interpreter::fromInputSource(Arabica::SAX::InputSource<std::string>& } Interpreter Interpreter::fromClone(const Interpreter& other) { - boost::shared_ptr<INTERPRETER_IMPL> interpreterImpl = boost::shared_ptr<INTERPRETER_IMPL>(new INTERPRETER_IMPL); + tthread::lock_guard<tthread::recursive_mutex> lock(_instanceMutex); - other.getImpl()->copyTo(interpreterImpl); + boost::shared_ptr<INTERPRETER_IMPL> interpreterImpl = boost::shared_ptr<INTERPRETER_IMPL>(new INTERPRETER_IMPL); + interpreterImpl->cloneFrom(other.getImpl()); Interpreter interpreter(interpreterImpl); + + _instances[interpreterImpl->getSessionId()] = interpreterImpl; return interpreter; } -void InterpreterImpl::copyTo(InterpreterImpl* other) { - if (getDocument()) { -#if 0 - std::stringstream* ss = new std::stringstream(); - (*ss) << getDocument(); - // we need an auto_ptr for arabica to assume ownership - std::auto_ptr<std::istream> ssPtr(ss); - Arabica::SAX::InputSource<std::string> inputSource; - inputSource.setByteStream(ssPtr); - - NameSpacingParser parser; - if (parser.parse(inputSource) && parser.getDocument() && parser.getDocument().hasChildNodes()) { - other->setNameSpaceInfo(parser.nameSpace); - other->_document = parser.getDocument(); - other->setupDOM(); - } else { - if (parser.errorsReported()) { - LOG(ERROR) << parser.errors(); - } - } +void InterpreterImpl::writeTo(std::ostream& stream) { + stream << getDocument(); +} -#else - Arabica::DOM::Document<std::string> clonedDocument; +void InterpreterImpl::cloneFrom(InterpreterImpl* other) { + if (other->getDocument()) { + const Arabica::DOM::Document<std::string>& otherDoc = other->_document; DOMImplementation<std::string> domFactory = Arabica::SimpleDOM::DOMImplementation<std::string>::getDOMImplementation(); - clonedDocument = domFactory.createDocument(getDocument().getNamespaceURI(), "", 0); + _document = domFactory.createDocument(otherDoc.getNamespaceURI(), "", 0); - Node<std::string> child = getDocument().getFirstChild(); + Node<std::string> child = otherDoc.getFirstChild(); while (child) { - Node<std::string> newNode = clonedDocument.importNode(child, true); - clonedDocument.appendChild(newNode); + Node<std::string> newNode = _document.importNode(child, true); + _document.appendChild(newNode); child = child.getNextSibling(); } - other->_document = clonedDocument; + setNameSpaceInfo(other->_nsInfo); + + _baseURI = other->_baseURI; + _sourceURI = other->_sourceURI; - other->setNameSpaceInfo(_nsInfo); - other->setupDOM(); -#endif + setupDOM(); } } -void InterpreterImpl::copyTo(boost::shared_ptr<InterpreterImpl> other) { - copyTo(other.get()); +void InterpreterImpl::cloneFrom(boost::shared_ptr<InterpreterImpl> other) { + cloneFrom(other.get()); } void InterpreterImpl::setName(const std::string& name) { diff --git a/src/uscxml/Interpreter.h b/src/uscxml/Interpreter.h index 4b6d26a..6772a59 100644 --- a/src/uscxml/Interpreter.h +++ b/src/uscxml/Interpreter.h @@ -228,9 +228,10 @@ public: virtual ~InterpreterImpl(); - void copyTo(InterpreterImpl* other); - void copyTo(boost::shared_ptr<InterpreterImpl> other); - + void cloneFrom(InterpreterImpl* other); + void cloneFrom(boost::shared_ptr<InterpreterImpl> other); + virtual void writeTo(std::ostream& stream); + // TODO: We need to move the destructor to the implementations to make these pure virtual virtual InterpreterState interpret(); virtual InterpreterState step(int waitForMS = 0); @@ -601,6 +602,10 @@ public: return *this; } + virtual void writeTo(std::ostream& stream) { + return _impl->writeTo(stream); + } + void reset() { return _impl->reset(); } diff --git a/src/uscxml/interpreter/InterpreterDraft6.cpp b/src/uscxml/interpreter/InterpreterDraft6.cpp index 7dcb768..2bab937 100644 --- a/src/uscxml/interpreter/InterpreterDraft6.cpp +++ b/src/uscxml/interpreter/InterpreterDraft6.cpp @@ -553,7 +553,7 @@ void InterpreterDraft6::handleDOMEvent(Arabica::DOM::Events::Event<std::string>& if (event.getType().compare("DOMAttrModified") == 0) // we do not care about attributes return; Node<std::string> target = Arabica::DOM::Node<std::string>(event.getTarget()); - NodeSet<std::string> transitions = InterpreterImpl::filterChildElements(_nsInfo.xmlNSPrefix + "transition", target); + NodeSet<std::string> transitions = InterpreterImpl::filterChildElements(_nsInfo.xmlNSPrefix + "transition", target, true); for (int i = 0; i < transitions.size(); i++) { const Element<std::string> transElem = Element<std::string>(transitions[i]); if (_transWithinParallel.find(transElem) != _transWithinParallel.end()) diff --git a/src/uscxml/interpreter/InterpreterRC.cpp b/src/uscxml/interpreter/InterpreterRC.cpp index 8f16cb0..b58a236 100644 --- a/src/uscxml/interpreter/InterpreterRC.cpp +++ b/src/uscxml/interpreter/InterpreterRC.cpp @@ -181,6 +181,7 @@ function computeExitSet(transitions) return statesToExit */ Arabica::XPath::NodeSet<std::string> InterpreterRC::computeExitSet(const Arabica::XPath::NodeSet<std::string>& transitions) { + NodeSet<std::string> statesToExit; for (unsigned int i = 0; i < transitions.size(); i++) { Element<std::string> t(transitions[i]); @@ -203,13 +204,21 @@ Arabica::XPath::NodeSet<std::string> InterpreterRC::computeExitSet(const Arabica } std::cout << std::endl; #endif + return statesToExit; } Arabica::XPath::NodeSet<std::string> InterpreterRC::computeExitSet(const Arabica::DOM::Node<std::string>& transition) { + if (_exitSet.find(transition) != _exitSet.end()) // speed up removeConflicting + return _exitSet[transition]; + Arabica::XPath::NodeSet<std::string> transitions; transitions.push_back(transition); - return computeExitSet(transitions); + + Arabica::XPath::NodeSet<std::string> exitSet = computeExitSet(transitions); + _exitSet[transition] = exitSet; + + return exitSet; } void InterpreterRC::enterStates(const Arabica::XPath::NodeSet<std::string>& enabledTransitions) { @@ -622,4 +631,16 @@ BREAK_LOOP: return findLCCA(states); } +void InterpreterRC::handleDOMEvent(Arabica::DOM::Events::Event<std::string>& event) { + InterpreterImpl::handleDOMEvent(event); + + if (event.getType().compare("DOMAttrModified") == 0) // we do not care about attributes + return; + +// Node<std::string> target = Arabica::DOM::Node<std::string>(event.getTarget()); +// NodeSet<std::string> transitions = InterpreterImpl::filterChildElements(_nsInfo.xmlNSPrefix + "transition", target, true); +// if (transitions.size() > 0) + _exitSet.clear(); + +} }
\ No newline at end of file diff --git a/src/uscxml/interpreter/InterpreterRC.h b/src/uscxml/interpreter/InterpreterRC.h index 52b45ff..36aca3d 100644 --- a/src/uscxml/interpreter/InterpreterRC.h +++ b/src/uscxml/interpreter/InterpreterRC.h @@ -57,7 +57,10 @@ protected: Arabica::XPath::NodeSet<std::string>& statesToEnter, Arabica::XPath::NodeSet<std::string>& statesForDefaultEntry, std::map<std::string, Arabica::DOM::Node<std::string> >& defaultHistoryContent); + virtual void handleDOMEvent(Arabica::DOM::Events::Event<std::string>& event); +private: + std::map<Arabica::DOM::Node<std::string>, Arabica::XPath::NodeSet<std::string> > _exitSet; }; } diff --git a/src/uscxml/transform/FSMToCPP.cpp b/src/uscxml/transform/ChartToCPP.cpp index 980c389..6b78374 100644 --- a/src/uscxml/transform/FSMToCPP.cpp +++ b/src/uscxml/transform/ChartToCPP.cpp @@ -18,7 +18,7 @@ */ #include "uscxml/transform/ChartToFSM.h" -#include "uscxml/transform/FSMToCPP.h" +#include "uscxml/transform/ChartToCPP.h" #include <DOM/io/Stream.hpp> #include <iostream> #include "uscxml/UUID.h" @@ -31,17 +31,17 @@ namespace uscxml { using namespace Arabica::DOM; using namespace Arabica::XPath; -void FSMToCPP::writeProgram(std::ostream& stream, +void ChartToCPP::writeProgram(std::ostream& stream, const Interpreter& interpreter) { - FSMToCPP promelaWriter; - interpreter.getImpl()->copyTo(&promelaWriter); + ChartToCPP promelaWriter; + promelaWriter.cloneFrom(interpreter.getImpl()); promelaWriter.writeProgram(stream); } -FSMToCPP::FSMToCPP() : _eventTrie(".") { +ChartToCPP::ChartToCPP() : _eventTrie(".") { } -void FSMToCPP::writeEvents(std::ostream& stream) { +void ChartToCPP::writeEvents(std::ostream& stream) { std::list<TrieNode*> eventNames = _eventTrie.getWordsWithPrefix(""); std::list<TrieNode*>::iterator eventIter = eventNames.begin(); stream << "// event name identifiers" << std::endl; @@ -52,7 +52,7 @@ void FSMToCPP::writeEvents(std::ostream& stream) { } } -void FSMToCPP::writeStates(std::ostream& stream) { +void ChartToCPP::writeStates(std::ostream& stream) { stream << "// state name identifiers" << std::endl; for (int i = 0; i < _globalStates.size(); i++) { stream << "#define " << "s" << i << " " << i; @@ -61,7 +61,7 @@ void FSMToCPP::writeStates(std::ostream& stream) { } -Arabica::XPath::NodeSet<std::string> FSMToCPP::getTransientContent(const Arabica::DOM::Element<std::string>& state) { +Arabica::XPath::NodeSet<std::string> ChartToCPP::getTransientContent(const Arabica::DOM::Element<std::string>& state) { Arabica::XPath::NodeSet<std::string> content; Arabica::DOM::Element<std::string> currState = state; for (;;) { @@ -77,7 +77,7 @@ Arabica::XPath::NodeSet<std::string> FSMToCPP::getTransientContent(const Arabica return content; } -Node<std::string> FSMToCPP::getUltimateTarget(const Arabica::DOM::Element<std::string>& transition) { +Node<std::string> ChartToCPP::getUltimateTarget(const Arabica::DOM::Element<std::string>& transition) { Arabica::DOM::Element<std::string> currState = _states[ATTR(transition, "target")]; for (;;) { @@ -88,7 +88,7 @@ Node<std::string> FSMToCPP::getUltimateTarget(const Arabica::DOM::Element<std::s } } -void FSMToCPP::writeInlineComment(std::ostream& stream, const Arabica::DOM::Element<std::string>& node) { +void ChartToCPP::writeInlineComment(std::ostream& stream, const Arabica::DOM::Element<std::string>& node) { if (node.getNodeType() != Node_base::COMMENT_NODE) return; @@ -107,7 +107,7 @@ void FSMToCPP::writeInlineComment(std::ostream& stream, const Arabica::DOM::Elem } } -void FSMToCPP::writeExecutableContent(std::ostream& stream, const Arabica::DOM::Element<std::string>& node, int indent) { +void ChartToCPP::writeExecutableContent(std::ostream& stream, const Arabica::DOM::Element<std::string>& node, int indent) { std::string padding; for (int i = 0; i < indent; i++) { @@ -227,7 +227,7 @@ void FSMToCPP::writeExecutableContent(std::ostream& stream, const Arabica::DOM:: } -void FSMToCPP::writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& condChain, int indent) { +void ChartToCPP::writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& condChain, int indent) { if (condChain.size() == 0) return; @@ -294,7 +294,7 @@ void FSMToCPP::writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet< } -std::string FSMToCPP::beautifyIndentation(const std::string& code, int indent) { +std::string ChartToCPP::beautifyIndentation(const std::string& code, int indent) { std::string padding; for (int i = 0; i < indent; i++) { @@ -325,7 +325,7 @@ std::string FSMToCPP::beautifyIndentation(const std::string& code, int indent) { return beautifiedSS.str(); } -void FSMToCPP::writeDeclarations(std::ostream& stream) { +void ChartToCPP::writeDeclarations(std::ostream& stream) { // get all data elements NodeSet<std::string> datas = _xpath.evaluate("//" + _nsInfo.xpathPrefix + "data", _scxml).asNodeSet(); @@ -352,7 +352,7 @@ void FSMToCPP::writeDeclarations(std::ostream& stream) { } -void FSMToCPP::writeFSM(std::ostream& stream) { +void ChartToCPP::writeFSM(std::ostream& stream) { NodeSet<std::string> transitions; stream << "proctype step() {" << std::endl; @@ -397,7 +397,7 @@ void FSMToCPP::writeFSM(std::ostream& stream) { stream << "}" << std::endl; } -void FSMToCPP::writeEventDispatching(std::ostream& stream) { +void ChartToCPP::writeEventDispatching(std::ostream& stream) { for (int i = 0; i < _globalStates.size(); i++) { if (_globalStates[i] == _startState) continue; @@ -411,7 +411,7 @@ void FSMToCPP::writeEventDispatching(std::ostream& stream) { } } -void FSMToCPP::writeDispatchingBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& transChain, int indent) { +void ChartToCPP::writeDispatchingBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& transChain, int indent) { if (transChain.size() == 0) return; @@ -461,7 +461,7 @@ void FSMToCPP::writeDispatchingBlock(std::ostream& stream, const Arabica::XPath: } -void FSMToCPP::writeMain(std::ostream& stream) { +void ChartToCPP::writeMain(std::ostream& stream) { stream << std::endl; stream << "init {" << std::endl; stream << " run step();" << std::endl; @@ -469,7 +469,7 @@ void FSMToCPP::writeMain(std::ostream& stream) { } -void FSMToCPP::initNodes() { +void ChartToCPP::initNodes() { // get all states NodeSet<std::string> states = filterChildElements(_nsInfo.xmlNSPrefix + "state", _scxml); for (int i = 0; i < states.size(); i++) { @@ -511,7 +511,7 @@ void FSMToCPP::initNodes() { } } -void FSMToCPP::writeProgram(std::ostream& stream) { +void ChartToCPP::writeProgram(std::ostream& stream) { if (!HAS_ATTR(_scxml, "flat") || !DOMUtils::attributeIsTrue(ATTR(_scxml, "flat"))) { LOG(ERROR) << "Given SCXML document was not flattened"; diff --git a/src/uscxml/transform/FSMToCPP.h b/src/uscxml/transform/ChartToCPP.h index 18df7c1..8cdebb9 100644 --- a/src/uscxml/transform/FSMToCPP.h +++ b/src/uscxml/transform/ChartToCPP.h @@ -31,7 +31,7 @@ namespace uscxml { -class USCXML_API FSMToCPP : public InterpreterDraft6 { +class USCXML_API ChartToCPP : public InterpreterDraft6 { public: static void writeProgram(std::ostream& stream, const Interpreter& interpreter); @@ -39,7 +39,7 @@ public: static std::string beautifyIndentation(const std::string& code, int indent = 0); protected: - FSMToCPP(); + ChartToCPP(); void writeProgram(std::ostream& stream); void initNodes(); diff --git a/src/uscxml/transform/ChartToFSM.cpp b/src/uscxml/transform/ChartToFSM.cpp index 2c5aacd..8eda0a5 100644 --- a/src/uscxml/transform/ChartToFSM.cpp +++ b/src/uscxml/transform/ChartToFSM.cpp @@ -33,6 +33,26 @@ #undef max #include <limits> +#define DUMP_STATS(nrTrans) \ +uint64_t now = tthread::chrono::system_clock::now(); \ +if (now - _lastTimeStamp > 1000) { \ + std::cerr << "T: " << _perfTransTotal << " [" << _perfTransProcessed << "/sec]"; \ + if (nrTrans > 0) { \ + std::cerr << " - 2**" << nrTrans << " = " << pow(2.0, static_cast<double>(nrTrans)); \ + } \ + std::cerr << std::endl; \ + std::cerr << "S: " << _globalConf.size() << " [" << _perfStatesProcessed << "/sec]" << std::endl; \ + std::cerr << "C: " << _perfStatesCachedTotal << " [" << _perfStatesCachedProcessed << "/sec]" << std::endl; \ + std::cerr << "X: " << _perfStatesSkippedTotal << " [" << _perfStatesSkippedProcessed << "/sec]" << std::endl; \ + std::cerr << std::endl; \ + _perfTransProcessed = 0; \ + _perfStatesProcessed = 0; \ + _perfStatesCachedProcessed = 0; \ + _perfStatesSkippedProcessed = 0; \ + _lastTimeStamp = now; \ +} + + #define DUMP_TRANSSET(where) \ {\ std::cout << std::endl;\ @@ -41,26 +61,13 @@ std::cout << "** " << transitions.size() << " ** " << where << std::endl;\ std::cout << transitions[m] << std::endl;\ }\ } + namespace uscxml { using namespace Arabica::DOM; using namespace Arabica::XPath; -#define CREATE_TRANSIENT_STATE_WITH_CHILDS(stateId) \ -if (childs.size() > 0) { \ - Element<std::string> transientState = _flatDoc.createElementNS(_nsInfo.nsURL, "state"); \ - _nsInfo.setPrefix(transientState);\ - transientState.setAttribute("transient", "true"); \ - if (stateId.length() > 0) \ - transientState.setAttribute("id", stateId); \ - for (int i = 0; i < childs.size(); i++) { \ - Node<std::string> imported = _flatDoc.importNode(childs[i], true); \ - transientState.appendChild(imported); \ - } \ - transientStateChain.push_back(transientState); \ -} \ -childs = NodeSet<std::string>(); #define DETAIL_EXEC_CONTENT(field, actPtr) \ std::cerr << " " << #field << " / " << TAGNAME_CAST(actPtr->field) << " ("; \ @@ -71,19 +78,7 @@ for (int i = 0; i < contents.size(); i++) { \ std::cerr << ")"; -Interpreter ChartToFSM::flatten(const Interpreter& other) { - - // instantiate a new InterpreterImpl to do the flattening - boost::shared_ptr<InterpreterImpl> flattener = boost::shared_ptr<InterpreterImpl>(new FlatteningInterpreter(other.getDocument())); - flattener->setNameSpaceInfo(other.getNameSpaceInfo()); - flattener->interpret(); - - // clone the flattener implementation to a new interpreter - Interpreter flat = Interpreter::fromClone(flattener); - return flat; -} - -uint64_t ChartToFSM::stateMachineComplexity(const Arabica::DOM::Element<std::string>& root) { +uint64_t Complexity::stateMachineComplexity(const Arabica::DOM::Element<std::string>& root) { Complexity complexity = calculateStateMachineComplexity(root); uint64_t value = complexity.value; for (std::list<uint64_t>::const_iterator histIter = complexity.history.begin(); histIter != complexity.history.end(); histIter++) { @@ -93,7 +88,7 @@ uint64_t ChartToFSM::stateMachineComplexity(const Arabica::DOM::Element<std::str return value; } -ChartToFSM::Complexity ChartToFSM::calculateStateMachineComplexity(const Arabica::DOM::Element<std::string>& root) { +Complexity Complexity::calculateStateMachineComplexity(const Arabica::DOM::Element<std::string>& root) { Complexity complexity; bool hasFlatHistory = false; @@ -144,56 +139,66 @@ ChartToFSM::Complexity ChartToFSM::calculateStateMachineComplexity(const Arabica } -FlatteningInterpreter::FlatteningInterpreter(const Document<std::string>& doc) { +ChartToFSM::ChartToFSM(const Interpreter& other) { - _perfProcessed = 0; - _perfTotal = 0; + cloneFrom(other.getImpl()); + _lastTimeStamp = tthread::chrono::system_clock::now(); + _perfTransProcessed = 0; + _perfTransTotal = 0; + _perfStatesProcessed = 0; + _perfStatesSkippedProcessed = 0; + _perfStatesSkippedTotal = 0; + _perfStatesCachedProcessed = 0; + _perfStatesCachedTotal = 0; + + _start = NULL; _currGlobalTransition = NULL; _lastTransientStateId = 0; - // just copy given doc into _document an create _flatDoc for the FSM + _lastStateIndex = 0; + _lastTransIndex = 0; + + // create a _flatDoc for the FSM DOMImplementation<std::string> domFactory = Arabica::SimpleDOM::DOMImplementation<std::string>::getDOMImplementation(); - _document = domFactory.createDocument(doc.getNamespaceURI(), "", 0); - _flatDoc = domFactory.createDocument(doc.getNamespaceURI(), "", 0); - - Node<std::string> child = doc.getFirstChild(); - while (child) { - Node<std::string> newNode = _document.importNode(child, true); - _document.appendChild(newNode); - child = child.getNextSibling(); - } + _flatDoc = domFactory.createDocument(other.getDocument().getNamespaceURI(), "", 0); addMonitor(this); } -FlatteningInterpreter::~FlatteningInterpreter() { +ChartToFSM::~ChartToFSM() { std::map<std::string, GlobalState*>::iterator confIter = _globalConf.begin(); while(confIter != _globalConf.end()) { - std::map<std::string, GlobalTransition*>::iterator transIter = confIter->second->outgoing.begin(); - while (transIter != confIter->second->outgoing.end()) { - delete transIter->second; + std::list<GlobalTransition*>::iterator transIter = confIter->second->sortedOutgoing.begin(); + while (transIter != confIter->second->sortedOutgoing.end()) { + delete *transIter; transIter++; } delete confIter->second; confIter++; } + + // tear down caches + Arabica::XPath::NodeSet<std::string> allTransitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _scxml, true); + for (int i = 0; i < allTransitions.size(); i++) { + _transParents.erase(allTransitions[i]); + } } -Document<std::string> FlatteningInterpreter::getDocument() const { +Document<std::string> ChartToFSM::getDocument() const { // std::cerr << "######################" << std::endl; // std::cerr << _flatDoc << std::endl; // std::cerr << "######################" << std::endl; return _flatDoc; } -InterpreterState FlatteningInterpreter::interpret() { +InterpreterState ChartToFSM::interpret() { init(); setupIOProcessors(); - uint64_t complexity = ChartToFSM::stateMachineComplexity(_scxml) + 1; + uint64_t complexity = Complexity::stateMachineComplexity(_scxml) + 1; std::cerr << "Approximate Complexity: " << complexity << std::endl; // initialize the datamodel @@ -216,6 +221,16 @@ InterpreterState FlatteningInterpreter::interpret() { LOG(ERROR) << "No datamodel for " << datamodelName << " registered"; } + // setup caches + { + Arabica::XPath::NodeSet<std::string> allTransitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _scxml, true); + indexedTransitions.reserve(allTransitions.size()); + for (int i = 0; i < allTransitions.size(); i++) { + _transParents[allTransitions[i]] = InterpreterImpl::getParentState(allTransitions[i]); + } + } + + _binding = (HAS_ATTR(_scxml, "binding") && iequals(ATTR(_scxml, "binding"), "late") ? LATE : EARLY); // set invokeid for all invokers to parent state if none given @@ -229,10 +244,9 @@ InterpreterState FlatteningInterpreter::interpret() { _currGlobalTransition = NULL; // very first state - GlobalState::gIndex = 0; - _start = new GlobalState(_configuration, _alreadyEntered, _historyValue, _nsInfo.xmlNSPrefix); + _start = new GlobalState(_configuration, _alreadyEntered, _historyValue, _nsInfo.xmlNSPrefix, this); _globalConf[_start->stateId] = _start; - _globalConf[_start->stateId]->index = toStr(GlobalState::gIndex++); + _globalConf[_start->stateId]->index = _lastStateIndex++; NodeSet<std::string> initialTransitions; @@ -255,14 +269,47 @@ InterpreterState FlatteningInterpreter::interpret() { // weightTransitions(); indexTransitions(_scxml); + // reverse indices for most prior to be in front + std::reverse(indexedTransitions.begin(), indexedTransitions.end()); + + // add initial transitions as least prior + for (int i = 0; i < initialTransitions.size() ; i++) { + indexedTransitions.push_back(Element<std::string>(initialTransitions[i])); + } + + // set index attribute for transitions + for (int i = 0; i < indexedTransitions.size(); i++) { + indexedTransitions[i].setAttribute("index", toStr(i)); + } + +// int lastTransIndex = indexedTransitions.size(); +// for (int i = 0; i < initialTransitions.size() ; i++, lastTransIndex++) { +// indexedTransitions[i].setAttribute("index", toStr(indexedTransitions.size() - 1 - i)); +// } + + // gather and set index attribute o states + NodeSet<std::string> allStates = getAllStates(); + allStates.to_document_order(); + + indexedStates.resize(allStates.size()); + for (int i = 0; i < allStates.size(); i++) { + Element<std::string> state = Element<std::string>(allStates[i]); + state.setAttribute("index", toStr(i)); + indexedStates[i] = state; + } + // std::cerr << _scxml << std::endl; GlobalTransition* globalTransition = new GlobalTransition(initialTransitions, _dataModel, this); - _start->outgoing[globalTransition->transitionId] = globalTransition; + globalTransition->index = _lastTransIndex++; + + _start->sortedOutgoing.push_back(globalTransition); globalTransition->source = _start->stateId; _currGlobalTransition = globalTransition; enterStates(initialTransitions); + globalTransition->destination = FlatStateIdentifier::toStateId(_configuration); + explode(); #if 0 @@ -275,9 +322,6 @@ InterpreterState FlatteningInterpreter::interpret() { std::cerr << _globalConf.size() << std::endl; #endif - createDocument(); - -// std::cout << _scxml << std::endl; NodeSet<std::string> elements = InterpreterImpl::filterChildType(Node_base::ELEMENT_NODE, _scxml, true); uint64_t nrStates = 0; @@ -294,14 +338,14 @@ InterpreterState FlatteningInterpreter::interpret() { return _state; } -void FlatteningInterpreter::executeContent(const Arabica::DOM::Element<std::string>& content, bool rethrow) { +void ChartToFSM::executeContent(const Arabica::DOM::Element<std::string>& content, bool rethrow) { // std::cerr << content << std::endl; // std::cerr << TAGNAME(content) << std::endl; GlobalTransition::Action action; if (false) { - } else if (TAGNAME(content) == "transition") { + } else if (TAGNAME(content) == "transition" && content.hasChildNodes()) { action.transition = content; } else if (TAGNAME(content) == "onexit") { action.onExit = content; @@ -313,23 +357,24 @@ void FlatteningInterpreter::executeContent(const Arabica::DOM::Element<std::stri return; } _currGlobalTransition->actions.push_back(action); + _currGlobalTransition->hasExecutableContent = true; } -void FlatteningInterpreter::invoke(const Arabica::DOM::Element<std::string>& element) { +void ChartToFSM::invoke(const Arabica::DOM::Element<std::string>& element) { GlobalTransition::Action action; action.invoke = element; _currGlobalTransition->actions.push_back(action); - _currGlobalTransition->invoke.push_back(element); + _currGlobalTransition->hasExecutableContent = true; } -void FlatteningInterpreter::cancelInvoke(const Arabica::DOM::Element<std::string>& element) { +void ChartToFSM::cancelInvoke(const Arabica::DOM::Element<std::string>& element) { GlobalTransition::Action action; action.uninvoke = element; _currGlobalTransition->actions.push_back(action); - _currGlobalTransition->uninvoke.push_back(element); + _currGlobalTransition->hasExecutableContent = true; } -void FlatteningInterpreter::internalDoneSend(const Arabica::DOM::Element<std::string>& state) { +void ChartToFSM::internalDoneSend(const Arabica::DOM::Element<std::string>& state) { Arabica::DOM::Element<std::string> stateElem = (Arabica::DOM::Element<std::string>)state; if (parentIsScxmlState(state)) @@ -367,34 +412,38 @@ void FlatteningInterpreter::internalDoneSend(const Arabica::DOM::Element<std::st action.onEntry = onentry; _currGlobalTransition->actions.push_back(action); + _currGlobalTransition->hasExecutableContent = true; } static bool isSuperset(const GlobalTransition* t1, const GlobalTransition* t2) { bool isSuperset = true; - if (t1->transitions.size() >= t2->transitions.size()) + if (t1->transitionRefs.size() >= t2->transitionRefs.size()) return false; - for (int i = 0; i < t1->transitions.size(); i++) { - if (!InterpreterImpl::isMember(t1->transitions[i], t2->transitions)) { + NodeSet<std::string> t1Trans = t1->getTransitions(); + NodeSet<std::string> t2Trans = t2->getTransitions(); + + for (int i = 0; i < t1Trans.size(); i++) { + if (!InterpreterImpl::isMember(t1Trans[i], t2Trans)) { isSuperset = false; } } return isSuperset; } -static bool filterSameState(const NodeSet<std::string>& transitions) { - NodeSet<std::string> filteredTransitions; +// return false if two transitions have the same source +std::map<Arabica::DOM::Node<std::string>, Arabica::DOM::Node<std::string> > ChartToFSM::_transParents; +bool ChartToFSM::filterSameState(const NodeSet<std::string>& transitions) { + for (unsigned int i = 0; i < transitions.size(); i++) { - Node<std::string> t1 = transitions[i]; - Node<std::string> p1 = InterpreterImpl::getParentState(t1); + Node<std::string> p1 = _transParents[transitions[i]]; - for (unsigned int j = 0; j < transitions.size(); j++) { - if (i == j) - continue; - Node<std::string> t2 = transitions[j]; - Node<std::string> p2 = InterpreterImpl::getParentState(t2); + for (unsigned int j = i + 1; j < transitions.size(); j++) { +// if (i == j) +// continue; + Node<std::string> p2 = _transParents[transitions[j]]; if (p1 == p2) return false; @@ -433,7 +482,7 @@ static bool filterChildEnabled(const NodeSet<std::string>& transitions) { } -void FlatteningInterpreter::indexTransitions(const Arabica::DOM::Element<std::string>& root) { +void ChartToFSM::indexTransitions(const Arabica::DOM::Element<std::string>& root) { // breadth first traversal of transitions Arabica::XPath::NodeSet<std::string> levelTransitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", root); for (int i = levelTransitions.size() - 1; i >= 0; i--) { @@ -450,187 +499,163 @@ void FlatteningInterpreter::indexTransitions(const Arabica::DOM::Element<std::st } bool GlobalTransition::operator< (const GlobalTransition& other) const { - const std::list<Arabica::DOM::Element<std::string> >& indexedTransitions = interpreter->indexedTransitions; - for (std::list<Element<std::string> >::const_reverse_iterator transIter = indexedTransitions.rbegin(); transIter != indexedTransitions.rend(); transIter++) { + const std::vector<Arabica::DOM::Element<std::string> >& indexedTransitions = interpreter->indexedTransitions; + NodeSet<std::string> transitions = getTransitions(); + + for (std::vector<Element<std::string> >::const_iterator transIter = indexedTransitions.begin(); transIter != indexedTransitions.end(); transIter++) { const Element<std::string>& refTrans = *transIter; + NodeSet<std::string> otherTransitions = other.getTransitions(); - if (InterpreterImpl::isMember(refTrans, transitions) && !InterpreterImpl::isMember(refTrans, other.transitions)) { + if (InterpreterImpl::isMember(refTrans, transitions) && !InterpreterImpl::isMember(refTrans, otherTransitions)) { return true; } - if (!InterpreterImpl::isMember(refTrans, transitions) && InterpreterImpl::isMember(refTrans, other.transitions)) { + if (!InterpreterImpl::isMember(refTrans, transitions) && InterpreterImpl::isMember(refTrans, otherTransitions)) { return false; } } return true; // actually, they are equal } +template <typename T> bool PtrComp(const T * const & a, const T * const & b) { + return *a < *b; +} -void FlatteningInterpreter::explode() { - - // save global configuration elements to restore after recursive explode - Arabica::XPath::NodeSet<std::string> configuration = _configuration; - Arabica::XPath::NodeSet<std::string> alreadyEntered = _alreadyEntered; - std::map<std::string, Arabica::XPath::NodeSet<std::string> > historyValue = _historyValue; - - // create current state from global configuration - GlobalState* globalState = new GlobalState(configuration, alreadyEntered, historyValue, _nsInfo.xmlNSPrefix); - // remember that the last transition lead here - if (_currGlobalTransition) { - _currGlobalTransition->destination = globalState->stateId; - globalState->incoming[_currGlobalTransition->transitionId] = _currGlobalTransition; +/** + * subset only removes transitions without cond -> superset will always be enabled + */ +bool hasUnconditionalSuperset (GlobalTransition* first, GlobalTransition* second) { -// if (!_currGlobalTransition->isEventless) { - // if it was an eventful transition, add all invokers - for (unsigned int i = 0; i < _statesToInvoke.size(); i++) { - NodeSet<std::string> invokes = filterChildElements(_nsInfo.xmlNSPrefix + "invoke", _statesToInvoke[i]); - for (unsigned int j = 0; j < invokes.size(); j++) { - invoke(Element<std::string>(invokes[j])); + NodeSet<std::string> firstTransitions = first->getTransitions(); + NodeSet<std::string> secondTransitions = first->getTransitions(); + + if (isSuperset(second, first)) { + for (int i = 0; i < firstTransitions.size(); i++) { + if (!InterpreterImpl::isMember(firstTransitions[i], secondTransitions)) { + if (HAS_ATTR_CAST(firstTransitions[i], "cond")) { + return false; // second can't be removed + } } } - _statesToInvoke = NodeSet<std::string>(); -// } + return true; // remove second } + return false; //second can't be removed +} - if (_globalConf.find(globalState->stateId) != _globalConf.end()) { - delete globalState; - return; // we have already been here +bool hasEarlierUnconditionalMatch(GlobalTransition* first, GlobalTransition* second) { + if (first->eventDesc == second->eventDesc) { + if (first->condition.size() == 0) + return true; } + return false; +} - _globalConf[globalState->stateId] = globalState; - _globalConf[globalState->stateId]->index = toStr(GlobalState::gIndex++); -// assert(isLegalConfiguration(configuration)); - - if(_globalConf[globalState->stateId]->isFinal) - return; // done in this branch +// for some reason, unique is not quite up to the task +std::list<GlobalTransition*> reapplyUniquePredicates(std::list<GlobalTransition*> list) { + + for (std::list<GlobalTransition*>::iterator outerIter = list.begin(); + outerIter != list.end(); + outerIter++) { + for (std::list<GlobalTransition*>::iterator innerIter = outerIter; + innerIter != list.end(); + innerIter++) { + + if (innerIter == outerIter) + continue; + + GlobalTransition* t1 = *outerIter; + GlobalTransition* t2 = *innerIter; + + if (hasUnconditionalSuperset(t1, t2)) { + list.erase(outerIter++); + continue; + } else if (hasUnconditionalSuperset(t2, t1)) { + list.erase(innerIter++); + continue; + } + if (hasEarlierUnconditionalMatch(t1, t2)) { + list.erase(innerIter++); + continue; + } + } + } + + return list; +} +void ChartToFSM::getPotentialTransitionsForConf(const Arabica::XPath::NodeSet<std::string>& conf, std::map<std::string, GlobalTransition*>& outMap) { // get all transition elements from states in the current configuration - NodeSet<std::string> allTransitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", configuration); - - /** - * From http://www.w3.org/TR/scxml/#SelectingTransitions - * - * A transition T is enabled by named event E in atomic state S if - * a) T's source state is S or an ancestor of S - * b) T matches E's name - * c) T lacks a 'cond' attribute or its 'cond' attribute evaluates to "true" - * - * A transition is enabled by NULL in atomic state S if - * a) T lacks an 'event' attribute - * b) T's source state is S or an ancestor of S - * c) T lacks an 'cond' attribute or its 'cond' attribute evaluates to "true" - * - * The _source state_ of a transition is the <state> or <parallel> element that it occurs in. - * The _target state(s)_ of the transition is the state or set of states specified by its 'target' attribute. - * The _complete target_ set of a transition consists of all the states that will be active after the transition is taken. - * - * A transition T is optimally enabled by event E in atomic state S if - * a) T is enabled by E in S - * b) no transition that precedes T in document order in T's source state is enabled by E in S - * c) no transition is enabled by E in S in any descendant of T's source state. - * - * Two transitions T1 and T2 conflict in state configuration C if their exit sets in C have a non-null intersection. - * let transitions T1 and T2 conflict: - * T1 is optimally enabled in atomic state S1 - * T2 is optimally enabled in atomic state S2 - * S1 and S2 are both active - * T1 has a higher priority than T2 if: - * a) T1's source state is a descendant of T2's source state, or - * b) S1 precedes S2 in document order - * - * The _optimal transition set_ enabled by event E in state configuration C is - * the largest set of transitions such that: - * a) each transition in the set is optimally enabled by E in an atomic state in C - * b) no transition conflicts with another transition in the set - * c) there is no optimally enabled transition outside the set that has a higher priority than some member of the set - * - * A _microstep_ consists of the execution of the transitions in an optimal enabled transition set - * - * A _macrostep_ is a series of one or more microsteps ending in a configuration - * where the internal event queue is empty and no transitions are enabled by NULL - */ - - + NodeSet<std::string> allTransitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", conf); + if (allTransitions.size() == 0) return; // no transitions - + int nrElements = allTransitions.size(); int k = 0; int* stack = (int*)malloc((nrElements + 1) * sizeof(int)); memset(stack, 0, (nrElements + 1) * sizeof(int)); - - // subset of powerset we already processed - std::map<std::string, GlobalTransition*> transitionSets; - + while(1) { // create the power set of all potential transitions - this is expensive! // see: http://www.programminglogic.com/powerset-algorithm-in-c/ - + if (stack[k] < nrElements) { stack[k+1] = stack[k] + 1; k++; } - + else { stack[k-1]++; k--; } - + if (k==0) break; - + NodeSet<std::string> transitions; -// std::cerr << globalState->stateId << " [" << nrElements << "]: " << std::endl; + // std::cerr << globalState->stateId << " [" << nrElements << "]: " << std::endl; for (int i = 1; i <= k; i++) { -// std::cerr << stack[i] - 1 << ", "; + // std::cerr << stack[i] - 1 << ", "; transitions.push_back(allTransitions[stack[i] - 1]); } -// std::cerr << std::endl; - -// transitions.push_back(allTransitions[0]); -// transitions.push_back(allTransitions[4]); -// transitions.push_back(allTransitions[5]); -// transitions.push_back(allTransitions[7]); - + // std::cerr << std::endl; + + // transitions.push_back(allTransitions[0]); + // transitions.push_back(allTransitions[4]); + // transitions.push_back(allTransitions[5]); + // transitions.push_back(allTransitions[7]); + bool dump = false; - -// if (k == 4 && stack[1] == 1 && stack[2] == 5 && stack[3] == 6 && stack[4] == 8) { -// dump = true; -// } - + + // if (k == 4 && stack[1] == 1 && stack[2] == 5 && stack[3] == 6 && stack[4] == 8) { + // dump = true; + // } + if (dump) DUMP_TRANSSET("at start"); - - _perfTotal++; - _perfProcessed++; - - if (tthread::chrono::system_clock::now() - _lastTimeStamp > 1000) { - _lastTimeStamp = tthread::chrono::system_clock::now(); -// std::cerr << globalState->stateId << " [" << nrElements << "]: " << std::endl; - std::cerr << "States: " << _globalConf.size() << " - "; - std::cerr << "Tested: " << _perfTotal << " [" << _perfProcessed << "/sec] - "; - std::cerr << "Current Complexity: 2**" << nrElements << " = " << pow(2.0, static_cast<double>(nrElements)); - std::cerr << std::endl; - _perfProcessed = 0; - } - + + _perfTransTotal++; + _perfTransProcessed++; + + DUMP_STATS(nrElements); + // remove transitions in the same state if(!filterSameState(transitions)) continue; if (dump) DUMP_TRANSSET("after same state filtered"); - + // remove those transitions with a child transition if(!filterChildEnabled(transitions)) continue; if (dump) DUMP_TRANSSET("after child enabled filtered"); - + // reduce to conflict-free subset // transitions.to_document_order(); transitions = removeConflictingTransitions(transitions); if (dump) DUMP_TRANSSET("after conflicting filtered"); - + // algorithm can never reduce to empty set assert(transitions.size() > 0); - + // create a GlobalTransition object from the set GlobalTransition* transition = new GlobalTransition(transitions, _dataModel, this); if (!transition->isValid) { @@ -638,447 +663,152 @@ void FlatteningInterpreter::explode() { delete transition; continue; } + transition->index = _lastTransIndex++; // two combinations might have projected onto the same conflict-free set - if (transitionSets.find(transition->transitionId) != transitionSets.end()) { -// std::cerr << "skipping as projected onto existing conflict-free subset" << std::endl; + if (outMap.find(transition->transitionId) != outMap.end()) { + // std::cerr << "skipping as projected onto existing conflict-free subset" << std::endl; delete transition; continue; } - + // remember this conflict-free set -// std::cerr << "New conflict-free subset: " << transition->transitionId << ":" << transition->eventDesc << std::endl; - transitionSets[transition->transitionId] = transition; + // std::cerr << "New conflict-free subset: " << transition->transitionId << ":" << transition->eventDesc << std::endl; + outMap[transition->transitionId] = transition; } - - // TODO: reduce and sort transition sets - std::list<GlobalTransition*> transitionList; - for(std::map<std::string, GlobalTransition*>::iterator transSetIter = transitionSets.begin(); - transSetIter != transitionSets.end(); - transSetIter++) { - transitionList.push_back(transSetIter->second); - } - - for(std::list<GlobalTransition*>::iterator transListIter = transitionList.begin(); - transListIter != transitionList.end(); - transListIter++) { - - // add transition set to current global state - globalState->outgoing[(*transListIter)->transitionId] = *transListIter; - (*transListIter)->source = globalState->stateId; - - _currGlobalTransition = *transListIter; - microstep((*transListIter)->transitions); -// if (!isLegalConfiguration(_configuration)) { -// FlatStateIdentifier fromState(configuration, alreadyEntered, historyValue); -// FlatStateIdentifier toState(_configuration, _alreadyEntered, _historyValue); -// std::cerr << "invalid configuration after transition " << std::endl -// << "from \t" << fromState.getStateId() << std::endl -// << "to \t" << toState.getStateId() << std::endl -// << "via ------" << std::endl; -// for (int i = 0; i < (*transListIter)->transitions.size(); i++) { -// std::cerr << (*transListIter)->transitions[i] << std::endl; -// } -// std::cerr << "----------" << std::endl; -// assert(false); -// } - explode(); - - // reset state for next transition set - _configuration = configuration; - _alreadyEntered = alreadyEntered; - _historyValue = historyValue; - - } -} - -static bool sortStatesByIndex(const std::pair<std::string,GlobalState*>& s1, const std::pair<std::string,GlobalState*>& s2) { - return s1.second->index < s2.second->index; + return; } - -void FlatteningInterpreter::createDocument() { - Element<std::string> _origSCXML = _scxml; - - _scxml = _flatDoc.createElementNS(_nsInfo.nsURL, "scxml"); - _nsInfo.setPrefix(_scxml); - - _scxml.setAttribute("flat", "true"); - _flatDoc.appendChild(_scxml); - - if (HAS_ATTR(_origSCXML, "datamodel")) { - _scxml.setAttribute("datamodel", ATTR(_origSCXML, "datamodel")); - } - - if (HAS_ATTR(_origSCXML, "name")) { - _scxml.setAttribute("name", ATTR(_origSCXML, "name")); - } - - if (HAS_ATTR(_origSCXML, "binding")) { - _scxml.setAttribute("binding", ATTR(_origSCXML, "binding")); - } - - _scxml.setAttribute("initial", _start->stateId); - - NodeSet<std::string> datas; - if (_binding == InterpreterImpl::LATE) { - // with late binding, just copy direct datamodel childs - datas = filterChildElements(_nsInfo.xmlNSPrefix + "datamodel", _origSCXML); - } else { - // with early binding, copy all datamodel elements into scxml element - datas = _xpath.evaluate("//" + _nsInfo.xpathPrefix + "datamodel", _origSCXML).asNodeSet(); - } - for (int i = 0; i < datas.size(); i++) { - if (isInEmbeddedDocument(datas[i])) - continue; // nested document - Node<std::string> imported = _flatDoc.importNode(datas[i], true); - _scxml.appendChild(imported); - } - - - NodeSet<std::string> scripts = filterChildElements(_nsInfo.xmlNSPrefix + "script", _origSCXML); - for (int i = 0; i < scripts.size(); i++) { - Node<std::string> imported = _flatDoc.importNode(scripts[i], true); - _scxml.appendChild(imported); - } - - NodeSet<std::string> comments = filterChildType(Node_base::COMMENT_NODE, _origSCXML); - for (int i = 0; i < comments.size(); i++) { - Node<std::string> imported = _flatDoc.importNode(comments[i], true); - _scxml.appendChild(imported); - } - - std::vector<std::pair<std::string,GlobalState*> > sortedStates; - sortedStates.insert(sortedStates.begin(), _globalConf.begin(), _globalConf.end()); - std::sort(sortedStates.begin(), sortedStates.end(), sortStatesByIndex); - - int index = 0; - for (std::list<Element<std::string> >::reverse_iterator transIter = indexedTransitions.rbegin(); transIter != indexedTransitions.rend(); transIter++) { - const Element<std::string>& refTrans = *transIter; - std::cerr << index++ << ": " << refTrans << std::endl; - } - std::cerr << std::endl; - - for (std::vector<std::pair<std::string,GlobalState*> >::iterator confIter = sortedStates.begin(); - confIter != sortedStates.end(); - confIter++) { - appendGlobalStateNode(confIter->second); - } -// exit(0); - -} - - -template <typename T> bool PtrComp(const T * const & a, const T * const & b) { - return *a < *b; -} - - -/** - * subset only removes transitions without cond -> superset will always be enabled - */ -bool hasUnconditionalSuperset (GlobalTransition* first, GlobalTransition* second) { - if (isSuperset(second, first)) { - for (int i = 0; i < first->transitions.size(); i++) { - if (!InterpreterImpl::isMember(first->transitions[i], second->transitions)) { - if (HAS_ATTR_CAST(first->transitions[i], "cond")) { - return false; // second can't be removed - } - } - } - return true; // remove second - } - return false; //second can't be removed -} - -bool hasEarlierUnconditionalMatch(GlobalTransition* first, GlobalTransition* second) { - if (first->eventDesc == second->eventDesc) { - if (first->condition.size() == 0) - return true; - } - return false; -} - -// for some reason, unique is not quite up to the task -std::list<GlobalTransition*> reapplyUniquePredicates(std::list<GlobalTransition*> list) { - - for (std::list<GlobalTransition*>::iterator outerIter = list.begin(); - outerIter != list.end(); - outerIter++) { - for (std::list<GlobalTransition*>::iterator innerIter = outerIter; - innerIter != list.end(); - innerIter++) { - - if (innerIter == outerIter) - continue; - - GlobalTransition* t1 = *outerIter; - GlobalTransition* t2 = *innerIter; - - if (hasUnconditionalSuperset(t1, t2)) { - list.erase(outerIter++); - continue; - } else if (hasUnconditionalSuperset(t2, t1)) { - list.erase(innerIter++); - continue; - } - if (hasEarlierUnconditionalMatch(t1, t2)) { - list.erase(innerIter++); - continue; - } + +void ChartToFSM::explode() { + + std::list<GlobalState*> statesRemaining; + statesRemaining.push_back(new GlobalState(_configuration, _alreadyEntered, _historyValue, _nsInfo.xmlNSPrefix, this)); + + // add all invokers for initial transition + for (unsigned int i = 0; i < _statesToInvoke.size(); i++) { + NodeSet<std::string> invokes = filterChildElements(_nsInfo.xmlNSPrefix + "invoke", _statesToInvoke[i]); + for (unsigned int j = 0; j < invokes.size(); j++) { + invoke(Element<std::string>(invokes[j])); } } + _statesToInvoke = NodeSet<std::string>(); - return list; -} - -void FlatteningInterpreter::appendGlobalStateNode(GlobalState* globalState) { - Element<std::string> state = _flatDoc.createElementNS(_nsInfo.nsURL, "state"); - _nsInfo.setPrefix(state); - - state.setAttribute("ref", globalState->index); - state.setAttribute("id", globalState->stateId); - - if (globalState->isFinal) - state.setAttribute("final", "true"); - - std::list<GlobalTransition*> transitionList; - for (std::map<std::string, GlobalTransition*>::iterator outIter = globalState->outgoing.begin(); - outIter != globalState->outgoing.end(); - outIter++) { - transitionList.push_back(outIter->second); - } - -// transitionList = sortTransitions(transitionList); - transitionList.sort(PtrComp<GlobalTransition>); - transitionList.unique(hasUnconditionalSuperset); - transitionList.unique(hasEarlierUnconditionalMatch); - // unique is not quite like what we need, but it was a start - transitionList = reapplyUniquePredicates(transitionList); - - // apend here, for transient state chains to trail the state - _scxml.appendChild(state); - - size_t index = 0; - for (std::list<GlobalTransition*>::iterator outIter = transitionList.begin(); - outIter != transitionList.end(); - outIter++) { - (*outIter)->index = globalState->index + ":" + toStr(index); - state.appendChild(globalTransitionToNode(*outIter)); - index++; - } -} - -/** - * Creates transient states for executable content as a side-effect - */ -Node<std::string> FlatteningInterpreter::globalTransitionToNode(GlobalTransition* globalTransition) { - Element<std::string> transition = _flatDoc.createElementNS(_nsInfo.nsURL, "transition"); - _nsInfo.setPrefix(transition); - -// transition.setAttribute("ref", globalTransition->index); - -#if 1 - transition.setAttribute("members", globalTransition->members); -#endif - // transition.setAttribute("priority", toStr(globalTransition->priority)); - - if (!globalTransition->isEventless) { - transition.setAttribute("event", globalTransition->eventDesc); - } - - if (globalTransition->condition.size() > 0) { - transition.setAttribute("cond", globalTransition->condition); - } - - if (globalTransition->destination.size() > 0) { - transition.setAttribute("final-target", globalTransition->destination); - } - - NodeSet<std::string> transientStateChain; - - // current active state set - FlatStateIdentifier flatId(globalTransition->source); - std::list<std::string> currActiveStates = flatId.getActive(); - -// std::cerr << "From " << globalTransition->source << " to " << globalTransition->destination << ":" << std::endl; - - // gather content for new transient state - NodeSet<std::string> childs; - // iterate all actions taken during the transition - for (std::list<GlobalTransition::Action>::iterator actionIter = globalTransition->actions.begin(); - actionIter != globalTransition->actions.end(); - actionIter++) { - - if (actionIter->transition) { -// DETAIL_EXEC_CONTENT(transition, actionIter); - - Element<std::string> onexit = _flatDoc.createElementNS(_nsInfo.nsURL, "onexit"); - _nsInfo.setPrefix(onexit); - Node<std::string> child = actionIter->transition.getFirstChild(); - while(child) { - Node<std::string> imported = _flatDoc.importNode(child, true); - onexit.appendChild(imported); - child = child.getNextSibling(); - } - // only append if there is something done - if (onexit.hasChildNodes()) - childs.push_back(onexit); - - continue; - } - - if (actionIter->onExit) { -// DETAIL_EXEC_CONTENT(onExit, actionIter); - - childs.push_back(actionIter->onExit); - continue; - } - - if (actionIter->onEntry) { -// DETAIL_EXEC_CONTENT(onEntry, actionIter); - - childs.push_back(actionIter->onEntry); - continue; - } - - if (actionIter->invoke) { -// DETAIL_EXEC_CONTENT(invoke, actionIter); - if (!globalTransition->isTargetless) { -// CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); - } - Element<std::string> invokeElem = Element<std::string>(actionIter->invoke); - invokeElem.setAttribute("persist", "true"); - childs.push_back(invokeElem); - continue; + /** + We need this to be a recursion in order not to exhaust the stack + */ + + // append new global states and pop from front + while(statesRemaining.size() > 0) { + DUMP_STATS(0); + + GlobalState* globalState = statesRemaining.front(); + statesRemaining.pop_front(); + + // used to be conditionalized, we will just assum + assert(_currGlobalTransition); + + if (_globalConf.find(globalState->stateId) != _globalConf.end()) { + delete globalState; + _perfStatesSkippedTotal++; + _perfStatesSkippedProcessed++; + continue; // we have already been here } - if (actionIter->uninvoke) { -// DETAIL_EXEC_CONTENT(uninvoke, actionIter); - Element<std::string> uninvokeElem = _flatDoc.createElementNS(_nsInfo.nsURL, "uninvoke"); - _nsInfo.setPrefix(uninvokeElem); - - if (HAS_ATTR(actionIter->uninvoke, "type")) { - uninvokeElem.setAttribute("type", ATTR(actionIter->uninvoke, "type")); - } - if (HAS_ATTR(actionIter->uninvoke, "typeexpr")) { - uninvokeElem.setAttribute("typeexpr", ATTR(actionIter->uninvoke, "typeexpr")); - } - if (HAS_ATTR(actionIter->uninvoke, "id")) { - uninvokeElem.setAttribute("id", ATTR(actionIter->uninvoke, "id")); + _perfStatesProcessed++; + + _configuration = globalState->getActiveStates(); + _alreadyEntered = globalState->getAlreadyEnteredStates(); + _historyValue = globalState->getHistoryStates(); + + // remember as global configuration + _globalConf[globalState->stateId] = globalState; + _globalConf[globalState->stateId]->index = _lastStateIndex++; + + if(_globalConf[globalState->stateId]->isFinal) + continue; // done in this branch + + if (_transPerActiveConf.find(globalState->activeId) != _transPerActiveConf.end()) { + // we already know these transition sets, just copy over + std::list<GlobalTransition*>::iterator sortTransIter = _transPerActiveConf[globalState->activeId]->sortedOutgoing.begin(); + while(sortTransIter != _transPerActiveConf[globalState->activeId]->sortedOutgoing.end()) { + globalState->sortedOutgoing.push_back(new GlobalTransition(**sortTransIter)); // copy constructor + globalState->sortedOutgoing.back()->index = _lastTransIndex++; + sortTransIter++; } - if (HAS_ATTR(actionIter->uninvoke, "idlocation")) { - uninvokeElem.setAttribute("idlocation", ATTR(actionIter->uninvoke, "idlocation")); - } - childs.push_back(uninvokeElem); - continue; - } + _perfStatesCachedTotal++; + _perfStatesCachedProcessed++; - if (actionIter->exited) { -// std::cerr << " exited(" << ATTR_CAST(actionIter->exited, "id") << ")"; - currActiveStates.remove(ATTR_CAST(actionIter->exited, "id")); - if (childs.size() > 0) { - CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); // create a new transient state to update its id + } else { + // we need to calculate the potential optimal transition sets + std::map<std::string, GlobalTransition*> transitionSets; + getPotentialTransitionsForConf(refsToStates(globalState->activeStatesRefs), transitionSets); + + // TODO: reduce and sort transition sets + for(std::map<std::string, GlobalTransition*>::iterator transSetIter = transitionSets.begin(); + transSetIter != transitionSets.end(); + transSetIter++) { + globalState->sortedOutgoing.push_back(transSetIter->second); } + + globalState->sortedOutgoing.sort(PtrComp<GlobalTransition>); + globalState->sortedOutgoing.unique(hasUnconditionalSuperset); + globalState->sortedOutgoing.unique(hasEarlierUnconditionalMatch); + // unique is not quite like what we need, but it was a start + globalState->sortedOutgoing = reapplyUniquePredicates(globalState->sortedOutgoing); + + _transPerActiveConf[globalState->activeId] = globalState; } - - if (actionIter->entered) { -// std::cerr << " entered(" << ATTR_CAST(actionIter->entered, "id") << ")"; - if (childs.size() > 0) - CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); // create a new transient state to update its id - currActiveStates.push_back(ATTR_CAST(actionIter->entered, "id")); - - // we entered a new child - check if it has a datamodel and we entered for the first time - if (_binding == InterpreterImpl::LATE) { - NodeSet<std::string> datamodel = filterChildElements(_nsInfo.xmlNSPrefix + "datamodel", actionIter->entered); - if (datamodel.size() > 0 && !isMember(actionIter->entered, _globalConf[globalTransition->source]->alreadyEnteredStates)) { - childs.push_back(datamodel); + + // append resulting new states + for(std::list<GlobalTransition*>::iterator transListIter = globalState->sortedOutgoing.begin(); + transListIter != globalState->sortedOutgoing.end(); + transListIter++) { + + (*transListIter)->source = globalState->stateId; + _currGlobalTransition = *transListIter; + + microstep(refsToTransitions((*transListIter)->transitionRefs)); + statesRemaining.push_back(new GlobalState(_configuration, _alreadyEntered, _historyValue, _nsInfo.xmlNSPrefix, this)); + + // add all invokers + for (unsigned int i = 0; i < _statesToInvoke.size(); i++) { + NodeSet<std::string> invokes = filterChildElements(_nsInfo.xmlNSPrefix + "invoke", _statesToInvoke[i]); + for (unsigned int j = 0; j < invokes.size(); j++) { + invoke(Element<std::string>(invokes[j])); } } - } - if (!globalTransition->isTargetless) { -// CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) - } - } - -// std::cerr << std::endl; - -// if (globalTransition->isTargetless) { -// for (int i = 0; i < childs.size(); i++) { -// Node<std::string> imported = _flatDoc.importNode(childs[i], true); -// transition.appendChild(imported); -// // CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) -// } -// return transition; -// } - - CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) - - if (transientStateChain.size() > 0) { - Element<std::string> prevExitTransitionElem; - - for (int i = 0; i < transientStateChain.size(); i++) { - Element<std::string> transientStateElem = Element<std::string>(transientStateChain[i]); - transientStateElem.setAttribute("id", transientStateElem.getAttribute("id") + "-via-" + toStr(_lastTransientStateId++)); - - Element<std::string> exitTransition = _flatDoc.createElementNS(_nsInfo.nsURL, "transition"); - _nsInfo.setPrefix(exitTransition); - - if (prevExitTransitionElem) { - // point previous to this one - prevExitTransitionElem.setAttribute("target", transientStateElem.getAttribute("id")); - } else { - // update globalTransition->source target - } + _statesToInvoke = NodeSet<std::string>(); - transientStateElem.appendChild(exitTransition); - prevExitTransitionElem = exitTransition; + // remember that the last transition lead here + (*transListIter)->destination = statesRemaining.back()->stateId; - if (i == 0) - transition.setAttribute("target", transientStateElem.getAttribute("id")); - - _scxml.appendChild(transientStateElem); + // reset state for next transition set + _configuration = globalState->getActiveStates(); + _alreadyEntered = globalState->getAlreadyEnteredStates(); + _historyValue = globalState->getHistoryStates(); } - - // last one points to actual target - assert(prevExitTransitionElem); - prevExitTransitionElem.setAttribute("target", globalTransition->destination); - - } else { - transition.setAttribute("target", globalTransition->destination); } - assert(HAS_ATTR_CAST(transition, "target")); - return transition; } -#if 0 -void FlatteningInterpreter::weightTransitions() { - maxDepth = 0; - maxOrder = 0; - - int depth = 0; - Arabica::XPath::NodeSet<std::string> states = getChildStates(_scxml); - while(states.size() > 0) { - NodeSet<std::string> transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", states); - NodeSet<std::string> initials = filterChildElements(_nsInfo.xmlNSPrefix + "initial", states); - transitions.push_back(filterChildElements(_nsInfo.xmlNSPrefix + "transition", initials)); +Arabica::XPath::NodeSet<std::string> ChartToFSM::refsToStates(const std::set<int>& stateRefs) { + NodeSet<std::string> states; + for (std::set<int>::const_iterator stateIter = stateRefs.begin(); stateIter != stateRefs.end(); stateIter++) { + states.push_back(indexedStates[*stateIter]); + } + return states; +} - for (int j = 0; j < transitions.size(); j++) { - if (depth > maxDepth) - maxDepth = depth; - if (j > maxOrder) - maxOrder = j; - Element<std::string> transition = Element<std::string>(transitions[j]); - transition.setAttribute("depth", toStr(depth)); - transition.setAttribute("order", toStr(j)); - } - depth++; - states = getChildStates(states); +Arabica::XPath::NodeSet<std::string> ChartToFSM::refsToTransitions(const std::set<int>& transRefs) { + NodeSet<std::string> transitions; + for (std::set<int>::const_iterator transIter = transRefs.begin(); transIter != transRefs.end(); transIter++) { + transitions.push_back(indexedTransitions[*transIter]); } + return transitions; } -#endif -void FlatteningInterpreter::labelTransitions() { + +void ChartToFSM::labelTransitions() { // put a unique id on each transition Arabica::XPath::NodeSet<std::string> states = getAllStates(); states.push_back(_scxml); @@ -1096,39 +826,50 @@ void FlatteningInterpreter::labelTransitions() { } } -void FlatteningInterpreter::beforeMicroStep(Interpreter interpreter) { +void ChartToFSM::beforeMicroStep(Interpreter interpreter) { } -void FlatteningInterpreter::onStableConfiguration(Interpreter interpreter) { +void ChartToFSM::onStableConfiguration(Interpreter interpreter) { } -void FlatteningInterpreter::beforeExitingState(Interpreter interpreter, const Arabica::DOM::Element<std::string>& state, bool moreComing) { +void ChartToFSM::beforeExitingState(Interpreter interpreter, const Arabica::DOM::Element<std::string>& state, bool moreComing) { GlobalTransition::Action action; action.exited = state; _currGlobalTransition->actions.push_back(action); - _currGlobalTransition->exited.push_back(state); } -void FlatteningInterpreter::beforeEnteringState(Interpreter interpreter, const Arabica::DOM::Element<std::string>& state, bool moreComing) { +void ChartToFSM::beforeEnteringState(Interpreter interpreter, const Arabica::DOM::Element<std::string>& state, bool moreComing) { GlobalTransition::Action action; action.entered = state; _currGlobalTransition->actions.push_back(action); - _currGlobalTransition->entered.push_back(state); } -void FlatteningInterpreter::beforeTakingTransition(Interpreter interpreter, const Arabica::DOM::Element<std::string>& transition, bool moreComing) { +void ChartToFSM::beforeTakingTransition(Interpreter interpreter, const Arabica::DOM::Element<std::string>& transition, bool moreComing) { } -int GlobalState::gIndex = 0; GlobalState::GlobalState(const Arabica::XPath::NodeSet<std::string>& activeStates_, const Arabica::XPath::NodeSet<std::string>& alreadyEnteredStates_, // we need to remember for binding=late const std::map<std::string, Arabica::XPath::NodeSet<std::string> >& historyStates_, - const std::string& xmlNSPrefix) { + const std::string& xmlNSPrefix, + ChartToFSM* flattener) { + interpreter = flattener; + + // take references + for (int i = 0; i < activeStates_.size(); i++) { + activeStatesRefs.insert(strTo<int>(ATTR_CAST(activeStates_[i], "index"))); + } + + for (int i = 0; i < alreadyEnteredStates_.size(); i++) { + alreadyEnteredStatesRefs.insert(strTo<int>(ATTR_CAST(alreadyEnteredStates_[i], "index"))); + } + + for (std::map<std::string, Arabica::XPath::NodeSet<std::string> >::const_iterator histIter = historyStates_.begin(); histIter != historyStates_.end(); histIter++) { + for (int i = 0; i < histIter->second.size(); i++) { + historyStatesRefs[histIter->first].insert(strTo<int>(ATTR_CAST(histIter->second[i], "index"))); + } + } - // make copies and sort - activeStates = activeStates_; - alreadyEnteredStates = alreadyEnteredStates_; - historyStates = historyStates_; isFinal = false; - for(int i = 0; i < activeStates.size(); i++) { - Arabica::DOM::Element<std::string> state = Arabica::DOM::Element<std::string>(activeStates[i]); + // is state this final? + for(int i = 0; i < activeStates_.size(); i++) { + Arabica::DOM::Element<std::string> state = Arabica::DOM::Element<std::string>(activeStates_[i]); Arabica::DOM::Element<std::string> parentElem = (Arabica::DOM::Element<std::string>)state.getParentNode(); if(InterpreterImpl::isFinal(state) && iequals(parentElem.getTagName(), xmlNSPrefix + "scxml")) { isFinal = true; @@ -1136,25 +877,30 @@ GlobalState::GlobalState(const Arabica::XPath::NodeSet<std::string>& activeState } } - // sort configuration - activeStates.to_document_order(); - alreadyEnteredStates.to_document_order(); - for(std::map<std::string, Arabica::XPath::NodeSet<std::string> >::iterator historyIter = historyStates.begin(); - historyIter != historyStates.end(); - historyIter++) { - historyIter->second.to_document_order(); - } - - FlatStateIdentifier flatStateId(activeStates, alreadyEnteredStates, historyStates); + FlatStateIdentifier flatStateId(getActiveStates(), getAlreadyEnteredStates(), getHistoryStates()); stateId = flatStateId.getStateId(); + activeId = flatStateId.getFlatActive(); } -GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitionSet, DataModel dataModel, FlatteningInterpreter* flattener) { +GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitionSet, DataModel dataModel, ChartToFSM* flattener) { interpreter = flattener; - transitions = transitionSet; + + for (int i = 0; i < transitionSet.size(); i++) { + transitionRefs.insert(strTo<int>(ATTR_CAST(transitionSet[i], "index"))); + } + + std::ostringstream setId; // also build id for subset + std::string seperator = ""; + for (std::set<int>::iterator transIter = transitionRefs.begin(); transIter != transitionRefs.end(); transIter++) { + setId << seperator << *transIter; + seperator = "-"; + } + transitionId = setId.str(); + + hasExecutableContent = false; isValid = true; isEventless = true; - + #if 0 std::cerr << "################" << std::endl; for (int i = 0; i < transitions.size(); i++) { @@ -1163,39 +909,7 @@ GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& t std::cerr << "################" << std::endl; #endif - std::list<std::string> conditions; - std::ostringstream setId; // also build id for subset - for (int i = 0; i < transitions.size(); i++) { - Arabica::DOM::Element<std::string> transElem = Arabica::DOM::Element<std::string>(transitions[i]); - // get a unique string for the transition - we assume it is sorted - assert(HAS_ATTR(transElem, "id")); - setId << ATTR(transElem, "id") << "-"; - - // gather conditions while we are iterating anyway - if (HAS_ATTR(transElem, "cond")) { - conditions.push_back(ATTR(transElem, "cond")); - } - } - transitionId = setId.str(); - - int index = 0; - std::string seperator; - for (std::list<Element<std::string> >::iterator transIter = interpreter->indexedTransitions.begin(); transIter != interpreter->indexedTransitions.end(); transIter++) { - const Element<std::string>& refTrans = *transIter; - if (InterpreterImpl::isMember(refTrans, transitions)) { - members += seperator + toStr(index); - } else { - members += seperator; - for (int i = 0; i < toStr(index).size(); i++) { - members += " "; - } - } - seperator = " "; - index++; - } - -// if (members == " 4 6 7 ") -// std::cout << "asdfadf"; + // first establish whether this is a valid set /** * Can these events event occur together? They can't if: @@ -1209,8 +923,8 @@ GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& t bool foundWithTarget = false; bool foundTargetLess = false; - for (int i = 0; i < transitions.size(); i++) { - Arabica::DOM::Element<std::string> transElem = Arabica::DOM::Element<std::string>(transitions[i]); + for (int i = 0; i < transitionSet.size(); i++) { + Arabica::DOM::Element<std::string> transElem = Arabica::DOM::Element<std::string>(transitionSet[i]); if (HAS_ATTR(transElem, "eventexpr")) { ERROR_EXECUTION_THROW("Cannot flatten document with eventexpr attributes"); } @@ -1253,7 +967,7 @@ GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& t // is there a set of event names that would enable this conflict-free transition set? if (foundWithEvent) { // get the set of longest event descriptors that will enable this transition set - eventNames = getCommonEvents(transitions); + eventNames = getCommonEvents(transitionSet); if (eventNames.size() == 0) { // LOG(INFO) << "No event will activate this conflict-free subset" << std::endl; isValid = false; @@ -1271,6 +985,35 @@ GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& t eventDesc = "*"; } + // extract conditions + std::list<std::string> conditions; + for (int i = 0; i < transitionSet.size(); i++) { + Arabica::DOM::Element<std::string> transElem = Arabica::DOM::Element<std::string>(transitionSet[i]); + // gather conditions while we are iterating anyway + if (HAS_ATTR(transElem, "cond")) { + conditions.push_back(ATTR(transElem, "cond")); + } + } + + int index = 0; + seperator = ""; + for (std::vector<Element<std::string> >::iterator transIter = interpreter->indexedTransitions.begin(); transIter != interpreter->indexedTransitions.end(); transIter++) { + const Element<std::string>& refTrans = *transIter; + if (InterpreterImpl::isMember(refTrans, transitionSet)) { + members += seperator + toStr(index); + } else { + members += seperator; + for (int i = 0; i < toStr(index).size(); i++) { + members += " "; + } + } + seperator = " "; + index++; + } + + // if (members == " 4 6 7 ") + // std::cout << "asdfadf"; + if (conditions.size() > 1) { condition = dataModel.andExpressions(conditions); if (condition.size() == 0) { @@ -1281,6 +1024,27 @@ GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& t } } +Arabica::XPath::NodeSet<std::string> GlobalState::getActiveStates() { + return interpreter->refsToStates(activeStatesRefs); +} + +Arabica::XPath::NodeSet<std::string> GlobalState::getAlreadyEnteredStates() { + return interpreter->refsToStates(alreadyEnteredStatesRefs); +} + +std::map<std::string, Arabica::XPath::NodeSet<std::string> > GlobalState::getHistoryStates() { + std::map<std::string, Arabica::XPath::NodeSet<std::string> > historyValue; + for (std::map<std::string, std::set<int> >::iterator histIter = historyStatesRefs.begin(); histIter != historyStatesRefs.end(); histIter++) { + historyValue[histIter->first] = interpreter->refsToStates(histIter->second); + } + return historyValue; +} + + +Arabica::XPath::NodeSet<std::string> GlobalTransition::getTransitions() const { + return interpreter->refsToTransitions(transitionRefs); +} + std::list<std::string> GlobalTransition::getCommonEvents(const NodeSet<std::string>& transitions) { std::list<std::string> prefixes; std::list<std::string> longestPrefixes; diff --git a/src/uscxml/transform/ChartToFSM.h b/src/uscxml/transform/ChartToFSM.h index 2f97a24..9e583b1 100644 --- a/src/uscxml/transform/ChartToFSM.h +++ b/src/uscxml/transform/ChartToFSM.h @@ -31,7 +31,33 @@ namespace uscxml { class GlobalState; class GlobalTransition; -class FlatteningInterpreter; +class ChartToFSM; + +class USCXML_API Complexity { +public: + Complexity() : value(0) {} + Complexity(uint64_t value) : value(value) {} + + Complexity& operator+=(const Complexity& rhs) { + value += rhs.value; + history.insert(history.end(), rhs.history.begin(), rhs.history.end()); + return *this; + } + + Complexity& operator*=(const Complexity& rhs) { + value *= rhs.value; + history.insert(history.end(), rhs.history.begin(), rhs.history.end()); + return *this; + } + + static uint64_t stateMachineComplexity(const Arabica::DOM::Element<std::string>& root); + +protected: + static Complexity calculateStateMachineComplexity(const Arabica::DOM::Element<std::string>& root); + + uint64_t value; + std::list<uint64_t> history; +}; class USCXML_API GlobalState { public: @@ -40,20 +66,25 @@ public: GlobalState(const Arabica::XPath::NodeSet<std::string>& activeStates, const Arabica::XPath::NodeSet<std::string>& alreadyEnteredStates, // we need to remember for binding=late const std::map<std::string, Arabica::XPath::NodeSet<std::string> >& historyStates, - const std::string& xmlNSPrefix); - - Arabica::XPath::NodeSet<std::string> activeStates; - Arabica::XPath::NodeSet<std::string> alreadyEnteredStates; - std::map<std::string, Arabica::XPath::NodeSet<std::string> > historyStates; - - std::map<std::string, GlobalTransition*> incoming; - std::map<std::string, GlobalTransition*> outgoing; + const std::string& xmlNSPrefix, + ChartToFSM* flattener); + + std::set<int> activeStatesRefs; + std::set<int> alreadyEnteredStatesRefs; + std::map<std::string, std::set<int> > historyStatesRefs; + + Arabica::XPath::NodeSet<std::string> getActiveStates(); + Arabica::XPath::NodeSet<std::string> getAlreadyEnteredStates(); + std::map<std::string, Arabica::XPath::NodeSet<std::string> > getHistoryStates(); + + std::list<GlobalTransition*> sortedOutgoing; std::string stateId; + std::string activeId; - static int gIndex; - - std::string index; + long index; bool isFinal; + + ChartToFSM* interpreter; }; @@ -70,19 +101,17 @@ public: Arabica::DOM::Element<std::string> uninvoke; }; - GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitions, DataModel dataModel, FlatteningInterpreter* flattener); + GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitions, DataModel dataModel, ChartToFSM* flattener); bool isValid; // constructor will determine, calling code will delete if not bool isEventless; // whether or not all our transitions are eventless bool isTargetless; // whether or not all our transitions are eventless bool isSubset; // there is a superset to this set - -// std::vector<long> firstElemPerLevel; -// std::vector<long> nrElemPerLevel; -// std::vector<long> prioPerLevel; - - Arabica::XPath::NodeSet<std::string> transitions; // constituting transitions - + bool hasExecutableContent; + + std::set<int> transitionRefs; // indizes of constituting transitions + Arabica::XPath::NodeSet<std::string> getTransitions() const; + std::list<std::string> eventNames; // the list of longest event names that will enable this set std::string eventDesc; // space-seperated eventnames for convenience std::string condition; // conjunction of all the set's conditions @@ -91,18 +120,12 @@ public: // executable content we gathered when we took the transition std::list<Action> actions; - Arabica::XPath::NodeSet<std::string> entered; - Arabica::XPath::NodeSet<std::string> exited; - - Arabica::XPath::NodeSet<std::string> invoke; - Arabica::XPath::NodeSet<std::string> uninvoke; - std::string transitionId; std::string source; std::string destination; - std::string index; - FlatteningInterpreter* interpreter; + long index; + ChartToFSM* interpreter; bool operator< (const GlobalTransition& other) const; @@ -110,17 +133,23 @@ protected: std::list<std::string> getCommonEvents(const Arabica::XPath::NodeSet<std::string>& transitions); }; -class USCXML_API FlatteningInterpreter : public InterpreterRC, public InterpreterMonitor { + +class USCXML_API ChartToFSM : public InterpreterRC, public InterpreterMonitor { public: - FlatteningInterpreter(const Arabica::DOM::Document<std::string>& doc); - virtual ~FlatteningInterpreter(); + virtual ~ChartToFSM(); + +protected: + ChartToFSM(const Interpreter& other); Arabica::DOM::Document<std::string> getDocument() const; // overwrite to return flat FSM InterpreterState interpret(); + + Arabica::XPath::NodeSet<std::string> refsToStates(const std::set<int>&); + Arabica::XPath::NodeSet<std::string> refsToTransitions(const std::set<int>&); + + std::vector<Arabica::DOM::Element<std::string> > indexedTransitions; + std::vector<Arabica::DOM::Element<std::string> > indexedStates; - std::list<Arabica::DOM::Element<std::string> > indexedTransitions; - -protected: // gather executable content per microstep void executeContent(const Arabica::DOM::Element<std::string>& content, bool rethrow = false); @@ -140,61 +169,38 @@ protected: virtual void beforeTakingTransition(Interpreter interpreter, const Arabica::DOM::Element<std::string>& transition, bool moreComing); void explode(); + void getPotentialTransitionsForConf(const Arabica::XPath::NodeSet<std::string>& conf, std::map<std::string, GlobalTransition*>& outMap); void labelTransitions(); -// void weightTransitions(); - void createDocument(); void indexTransitions(const Arabica::DOM::Element<std::string>& root); std::list<GlobalTransition*> sortTransitions(std::list<GlobalTransition*> list); - void appendGlobalStateNode(GlobalState* globalState); - Arabica::DOM::Node<std::string> globalTransitionToNode(GlobalTransition* globalTransition); - - GlobalState* _start; - GlobalTransition* _currGlobalTransition; - - uint64_t _perfProcessed; - uint64_t _perfTotal; + // we need this static as we use it in a sort function + static std::map<Arabica::DOM::Node<std::string>, Arabica::DOM::Node<std::string> > _transParents; + + static bool filterSameState(const Arabica::XPath::NodeSet<std::string>& transitions); + + uint64_t _perfTransProcessed; + uint64_t _perfTransTotal; + uint64_t _perfStatesProcessed; + uint64_t _perfStatesSkippedProcessed; + uint64_t _perfStatesSkippedTotal; + uint64_t _perfStatesCachedProcessed; + uint64_t _perfStatesCachedTotal; uint64_t _lastTimeStamp; - int maxDepth; - int maxOrder; - size_t _lastTransientStateId; + size_t _lastStateIndex; + size_t _lastTransIndex; + GlobalState* _start; + GlobalTransition* _currGlobalTransition; Arabica::DOM::Document<std::string> _flatDoc; std::map<std::string, GlobalState*> _globalConf; -}; - -class USCXML_API ChartToFSM { -public: - static Interpreter flatten(const Interpreter& other); - static uint64_t stateMachineComplexity(const Arabica::DOM::Element<std::string>& root); - -protected: - class USCXML_API Complexity { - public: - Complexity() : value(0) {} - Complexity(uint64_t value) : value(value) {} - - Complexity& operator+=(const Complexity& rhs) { - value += rhs.value; - history.insert(history.end(), rhs.history.begin(), rhs.history.end()); - return *this; - } - - Complexity& operator*=(const Complexity& rhs) { - value *= rhs.value; - history.insert(history.end(), rhs.history.begin(), rhs.history.end()); - return *this; - } - - uint64_t value; - std::list<uint64_t> history; - }; - - static Complexity calculateStateMachineComplexity(const Arabica::DOM::Element<std::string>& root); - + std::map<std::string, GlobalState*> _transPerActiveConf; // potentially enabled transition sets per active configuration + + friend class GlobalTransition; + friend class GlobalState; }; } diff --git a/src/uscxml/transform/ChartToFlatSCXML.cpp b/src/uscxml/transform/ChartToFlatSCXML.cpp new file mode 100644 index 0000000..f279a67 --- /dev/null +++ b/src/uscxml/transform/ChartToFlatSCXML.cpp @@ -0,0 +1,351 @@ +/** + * @file + * @author 2012-2014 Stefan Radomski (stefan.radomski@cs.tu-darmstadt.de) + * @copyright Simplified BSD + * + * @cond + * This program is free software: you can redistribute it and/or modify + * it under the terms of the FreeBSD license as published by the FreeBSD + * project. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * You should have received a copy of the FreeBSD license along with this + * program. If not, see <http://www.opensource.org/licenses/bsd-license>. + * @endcond + */ + +#include "ChartToFlatSCXML.h" +#include "uscxml/transform/FlatStateIdentifier.h" + +#define CREATE_TRANSIENT_STATE_WITH_CHILDS(stateId) \ +if (childs.size() > 0) { \ + Element<std::string> transientState = _flatDoc.createElementNS(_nsInfo.nsURL, "state"); \ + _nsInfo.setPrefix(transientState);\ + transientState.setAttribute("transient", "true"); \ + if (stateId.length() > 0) \ + transientState.setAttribute("id", stateId); \ + for (int i = 0; i < childs.size(); i++) { \ + Node<std::string> imported = _flatDoc.importNode(childs[i], true); \ + transientState.appendChild(imported); \ + } \ + transientStateChain.push_back(transientState); \ +} \ +childs = NodeSet<std::string>(); + +namespace uscxml { + +using namespace Arabica::DOM; +using namespace Arabica::XPath; + +ChartToFlatSCXML::operator Interpreter() { + if (!HAS_ATTR(_scxml, "flat") || !DOMUtils::attributeIsTrue(ATTR(_scxml, "flat"))) { + createDocument(); + } + return Interpreter::fromClone(shared_from_this()); +} + +Transformer ChartToFlatSCXML::transform(const Interpreter& other) { + return boost::shared_ptr<TransformerImpl>(new ChartToFlatSCXML(other)); +} + +void ChartToFlatSCXML::writeTo(std::ostream& stream) { + if (!HAS_ATTR(_scxml, "flat") || !DOMUtils::attributeIsTrue(ATTR(_scxml, "flat"))) { + createDocument(); + } + stream << _scxml; +} + +void ChartToFlatSCXML::createDocument() { + + if (HAS_ATTR(_scxml, "flat") && DOMUtils::attributeIsTrue(ATTR(_scxml, "flat"))) + return; + + if (_start == NULL) + interpret(); // only if not already flat! + + Element<std::string> _origSCXML = _scxml; + + _scxml = _flatDoc.createElementNS(_nsInfo.nsURL, "scxml"); + _nsInfo.setPrefix(_scxml); + + _scxml.setAttribute("flat", "true"); + _flatDoc.appendChild(_scxml); + + if (HAS_ATTR(_origSCXML, "datamodel")) { + _scxml.setAttribute("datamodel", ATTR(_origSCXML, "datamodel")); + } + + if (HAS_ATTR(_origSCXML, "name")) { + _scxml.setAttribute("name", ATTR(_origSCXML, "name")); + } + + if (HAS_ATTR(_origSCXML, "binding")) { + _scxml.setAttribute("binding", ATTR(_origSCXML, "binding")); + } + + _scxml.setAttribute("initial", _start->stateId); + + NodeSet<std::string> datas; + if (_binding == InterpreterImpl::LATE) { + // with late binding, just copy direct datamodel childs + datas = filterChildElements(_nsInfo.xmlNSPrefix + "datamodel", _origSCXML); + } else { + // with early binding, copy all datamodel elements into scxml element + datas = _xpath.evaluate("//" + _nsInfo.xpathPrefix + "datamodel", _origSCXML).asNodeSet(); + } + for (int i = 0; i < datas.size(); i++) { + if (isInEmbeddedDocument(datas[i])) + continue; // nested document + Node<std::string> imported = _flatDoc.importNode(datas[i], true); + _scxml.appendChild(imported); + } + + + NodeSet<std::string> scripts = filterChildElements(_nsInfo.xmlNSPrefix + "script", _origSCXML); + for (int i = 0; i < scripts.size(); i++) { + Node<std::string> imported = _flatDoc.importNode(scripts[i], true); + _scxml.appendChild(imported); + } + + NodeSet<std::string> comments = filterChildType(Node_base::COMMENT_NODE, _origSCXML); + for (int i = 0; i < comments.size(); i++) { + Node<std::string> imported = _flatDoc.importNode(comments[i], true); + _scxml.appendChild(imported); + } + + std::vector<std::pair<std::string,GlobalState*> > sortedStates; + sortedStates.insert(sortedStates.begin(), _globalConf.begin(), _globalConf.end()); + std::sort(sortedStates.begin(), sortedStates.end(), sortStatesByIndex); + + // int index = 0; + // for (std::vector<Element<std::string> >::iterator transIter = indexedTransitions.begin(); transIter != indexedTransitions.end(); transIter++) { + // const Element<std::string>& refTrans = *transIter; + // std::cerr << index++ << ": " << refTrans << std::endl; + // } + // std::cerr << std::endl; + + for (std::vector<std::pair<std::string,GlobalState*> >::iterator confIter = sortedStates.begin(); + confIter != sortedStates.end(); + confIter++) { + appendGlobalStateNode(confIter->second); + } + + _document = _flatDoc; +} + +void ChartToFlatSCXML::appendGlobalStateNode(GlobalState* globalState) { + Element<std::string> state = _flatDoc.createElementNS(_nsInfo.nsURL, "state"); + _nsInfo.setPrefix(state); + + state.setAttribute("ref", toStr(globalState->index)); + state.setAttribute("id", globalState->stateId); + + if (globalState->isFinal) + state.setAttribute("final", "true"); + + std::list<GlobalTransition*>& transitionList = globalState->sortedOutgoing; + + // apend here, for transient state chains to trail the state + _scxml.appendChild(state); + + size_t index = 0; + for (std::list<GlobalTransition*>::iterator outIter = transitionList.begin(); + outIter != transitionList.end(); + outIter++) { +// (*outIter)->index = globalState->index + ":" + toStr(index); + state.appendChild(globalTransitionToNode(*outIter)); + index++; + } +} + +/** + * Creates transient states for executable content as a side-effect + */ +Node<std::string> ChartToFlatSCXML::globalTransitionToNode(GlobalTransition* globalTransition) { + Element<std::string> transition = _flatDoc.createElementNS(_nsInfo.nsURL, "transition"); + _nsInfo.setPrefix(transition); + + // transition.setAttribute("ref", globalTransition->index); + +#if 1 + transition.setAttribute("members", globalTransition->members); +#endif + // transition.setAttribute("priority", toStr(globalTransition->priority)); + + if (!globalTransition->isEventless) { + transition.setAttribute("event", globalTransition->eventDesc); + } + + if (globalTransition->condition.size() > 0) { + transition.setAttribute("cond", globalTransition->condition); + } + + if (globalTransition->destination.size() > 0) { + transition.setAttribute("final-target", globalTransition->destination); + } + + NodeSet<std::string> transientStateChain; + + // current active state set + FlatStateIdentifier flatId(globalTransition->source); + std::list<std::string> currActiveStates = flatId.getActive(); + + // std::cerr << "From " << globalTransition->source << " to " << globalTransition->destination << ":" << std::endl; + + // gather content for new transient state + NodeSet<std::string> childs; + // iterate all actions taken during the transition + for (std::list<GlobalTransition::Action>::iterator actionIter = globalTransition->actions.begin(); + actionIter != globalTransition->actions.end(); + actionIter++) { + + if (actionIter->transition) { + // DETAIL_EXEC_CONTENT(transition, actionIter); + + Element<std::string> onexit = _flatDoc.createElementNS(_nsInfo.nsURL, "onexit"); + _nsInfo.setPrefix(onexit); + Node<std::string> child = actionIter->transition.getFirstChild(); + while(child) { + Node<std::string> imported = _flatDoc.importNode(child, true); + onexit.appendChild(imported); + child = child.getNextSibling(); + } + // only append if there is something done + if (onexit.hasChildNodes()) + childs.push_back(onexit); + + continue; + } + + if (actionIter->onExit) { + // DETAIL_EXEC_CONTENT(onExit, actionIter); + + childs.push_back(actionIter->onExit); + continue; + } + + if (actionIter->onEntry) { + // DETAIL_EXEC_CONTENT(onEntry, actionIter); + + childs.push_back(actionIter->onEntry); + continue; + } + + if (actionIter->invoke) { + // DETAIL_EXEC_CONTENT(invoke, actionIter); + if (!globalTransition->isTargetless) { + // CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); + } + Element<std::string> invokeElem = Element<std::string>(actionIter->invoke); + invokeElem.setAttribute("persist", "true"); + childs.push_back(invokeElem); + continue; + } + + if (actionIter->uninvoke) { + // DETAIL_EXEC_CONTENT(uninvoke, actionIter); + Element<std::string> uninvokeElem = _flatDoc.createElementNS(_nsInfo.nsURL, "uninvoke"); + _nsInfo.setPrefix(uninvokeElem); + + if (HAS_ATTR(actionIter->uninvoke, "type")) { + uninvokeElem.setAttribute("type", ATTR(actionIter->uninvoke, "type")); + } + if (HAS_ATTR(actionIter->uninvoke, "typeexpr")) { + uninvokeElem.setAttribute("typeexpr", ATTR(actionIter->uninvoke, "typeexpr")); + } + if (HAS_ATTR(actionIter->uninvoke, "id")) { + uninvokeElem.setAttribute("id", ATTR(actionIter->uninvoke, "id")); + } + if (HAS_ATTR(actionIter->uninvoke, "idlocation")) { + uninvokeElem.setAttribute("idlocation", ATTR(actionIter->uninvoke, "idlocation")); + } + childs.push_back(uninvokeElem); + continue; + } + + if (actionIter->exited) { + // std::cerr << " exited(" << ATTR_CAST(actionIter->exited, "id") << ")"; + currActiveStates.remove(ATTR_CAST(actionIter->exited, "id")); + if (childs.size() > 0) { + CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); // create a new transient state to update its id + } + } + + if (actionIter->entered) { + // std::cerr << " entered(" << ATTR_CAST(actionIter->entered, "id") << ")"; + if (childs.size() > 0) + CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)); // create a new transient state to update its id + currActiveStates.push_back(ATTR_CAST(actionIter->entered, "id")); + + // we entered a new child - check if it has a datamodel and we entered for the first time + if (_binding == InterpreterImpl::LATE) { + NodeSet<std::string> datamodel = filterChildElements(_nsInfo.xmlNSPrefix + "datamodel", actionIter->entered); + if (datamodel.size() > 0 && !isMember(actionIter->entered, _globalConf[globalTransition->source]->getAlreadyEnteredStates())) { + childs.push_back(datamodel); + } + } + } + if (!globalTransition->isTargetless) { + // CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) + } + } + + // std::cerr << std::endl; + + // if (globalTransition->isTargetless) { + // for (int i = 0; i < childs.size(); i++) { + // Node<std::string> imported = _flatDoc.importNode(childs[i], true); + // transition.appendChild(imported); + // // CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) + // } + // return transition; + // } + + CREATE_TRANSIENT_STATE_WITH_CHILDS(FlatStateIdentifier::toStateId(currActiveStates)) + + if (transientStateChain.size() > 0) { + Element<std::string> prevExitTransitionElem; + + for (int i = 0; i < transientStateChain.size(); i++) { + Element<std::string> transientStateElem = Element<std::string>(transientStateChain[i]); + transientStateElem.setAttribute("id", transientStateElem.getAttribute("id") + "-via-" + toStr(_lastTransientStateId++)); + + Element<std::string> exitTransition = _flatDoc.createElementNS(_nsInfo.nsURL, "transition"); + _nsInfo.setPrefix(exitTransition); + + if (prevExitTransitionElem) { + // point previous to this one + prevExitTransitionElem.setAttribute("target", transientStateElem.getAttribute("id")); + } else { + // update globalTransition->source target + } + + transientStateElem.appendChild(exitTransition); + prevExitTransitionElem = exitTransition; + + if (i == 0) + transition.setAttribute("target", transientStateElem.getAttribute("id")); + + _scxml.appendChild(transientStateElem); + } + + // last one points to actual target + assert(prevExitTransitionElem); + prevExitTransitionElem.setAttribute("target", globalTransition->destination); + + } else { + transition.setAttribute("target", globalTransition->destination); + } + + assert(HAS_ATTR_CAST(transition, "target")); + return transition; +} + +bool ChartToFlatSCXML::sortStatesByIndex(const std::pair<std::string,GlobalState*>& s1, const std::pair<std::string,GlobalState*>& s2) { + return s1.second->index < s2.second->index; +} + +}
\ No newline at end of file diff --git a/src/uscxml/transform/ChartToFlatSCXML.h b/src/uscxml/transform/ChartToFlatSCXML.h new file mode 100644 index 0000000..b6dd616 --- /dev/null +++ b/src/uscxml/transform/ChartToFlatSCXML.h @@ -0,0 +1,52 @@ +/** + * @file + * @author 2012-2014 Stefan Radomski (stefan.radomski@cs.tu-darmstadt.de) + * @copyright Simplified BSD + * + * @cond + * This program is free software: you can redistribute it and/or modify + * it under the terms of the FreeBSD license as published by the FreeBSD + * project. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * You should have received a copy of the FreeBSD license along with this + * program. If not, see <http://www.opensource.org/licenses/bsd-license>. + * @endcond + */ + +#ifndef FSMTOSCXML_H_DC0B5E09 +#define FSMTOSCXML_H_DC0B5E09 + +#include "ChartToFSM.h" +#include "Transformer.h" + +namespace uscxml { + +class USCXML_API ChartToFlatSCXML : public TransformerImpl, public ChartToFSM { +public: + virtual ~ChartToFlatSCXML() {} + static Transformer transform(const Interpreter& other); + + operator Interpreter(); + + Arabica::DOM::Document<std::string> getDocument() const { + return _flatDoc; + } + +protected: + void writeTo(std::ostream& stream); + + ChartToFlatSCXML(const Interpreter& other) : TransformerImpl(), ChartToFSM(other) {} + void createDocument(); + + void appendGlobalStateNode(GlobalState* globalState); + Arabica::DOM::Node<std::string> globalTransitionToNode(GlobalTransition* globalTransition); + static bool sortStatesByIndex(const std::pair<std::string,GlobalState*>& s1, const std::pair<std::string,GlobalState*>& s2); + +}; + +} +#endif /* end of include guard: FSMTOSCXML_H_DC0B5E09 */ diff --git a/src/uscxml/transform/FSMToPromela.cpp b/src/uscxml/transform/ChartToPromela.cpp index 8c2836f..1ae6c8d 100644 --- a/src/uscxml/transform/FSMToPromela.cpp +++ b/src/uscxml/transform/ChartToPromela.cpp @@ -18,7 +18,7 @@ */ #include "uscxml/transform/ChartToFSM.h" -#include "uscxml/transform/FSMToPromela.h" +#include "uscxml/transform/ChartToPromela.h" #include "uscxml/transform/FlatStateIdentifier.h" #include "uscxml/plugins/datamodel/promela/PromelaParser.h" #include "uscxml/plugins/datamodel/promela/parser/promela.tab.hpp" @@ -30,10 +30,20 @@ #include <boost/algorithm/string.hpp> #include <glog/logging.h> +#define MSG_QUEUE_LENGTH 5 #define MAX_MACRO_CHARS 64 #define MIN_COMMENT_PADDING 60 #define BIT_WIDTH(number) (number > 1 ? (int)ceil(log((double)number) / log((double)2.0)) : 1) +#define LENGTH_FOR_NUMBER(input, output) \ +{ \ + int number = input; \ + int output = 0; \ + do { \ + number /= 10; \ + output++; \ + } while (number != 0); \ +} #define INDENT_MIN(stream, start, cols) \ for (int indentIndex = start; indentIndex < cols; indentIndex++) \ @@ -44,14 +54,12 @@ namespace uscxml { using namespace Arabica::DOM; using namespace Arabica::XPath; -void FSMToPromela::writeProgram(std::ostream& stream, - const Interpreter& interpreter) { - FSMToPromela promelaWriter; - interpreter.getImpl()->copyTo(&promelaWriter); - promelaWriter.writeProgram(stream); +Transformer ChartToPromela::transform(const Interpreter& other) { + return boost::shared_ptr<TransformerImpl>(new ChartToPromela(other)); } -FSMToPromela::FSMToPromela() { +void ChartToPromela::writeTo(std::ostream& stream) { + writeProgram(stream); } void PromelaEventSource::writeStartEventSources(std::ostream& stream, int indent) { @@ -153,7 +161,7 @@ void PromelaEventSource::writeEventSource(std::ostream& stream) { eventNameIter++; } - stream << FSMToPromela::beautifyIndentation(content, 2) << std::endl; + stream << ChartToPromela::beautifyIndentation(content, 2) << std::endl; } else { stream << " " << " if" << std::endl; @@ -209,6 +217,9 @@ void PromelaCodeAnalyzer::addCode(const std::string& code) { PromelaParserNode* node = astNodes.front(); astNodes.pop_front(); + bool hasValue = false; + int assignedValue = 0; + switch (node->type) { case PML_STRING: { std::string unquoted = node->value; @@ -218,10 +229,23 @@ void PromelaCodeAnalyzer::addCode(const std::string& code) { addLiteral(unquoted); break; } + case PML_ASGN: +// node->dump(); + if (node->operands.back()->type == PML_CONST) { + hasValue = true; + if (isInteger(node->operands.back()->value.c_str(), 10)) { + assignedValue = strTo<int>(node->operands.back()->value); + } + } + if (node->operands.front()->type == PML_CMPND) + node = node->operands.front(); case PML_CMPND: { std::string nameOfType; std::list<PromelaParserNode*>::iterator opIter = node->operands.begin(); - assert((*opIter)->type == PML_NAME); + if ((*opIter)->type != PML_NAME) { + node->dump(); + assert(false); + } PromelaTypedef* td = &_typeDefs; std::string seperator; @@ -249,6 +273,10 @@ void PromelaCodeAnalyzer::addCode(const std::string& code) { break; } default: + if ((*opIter)->type == PML_CONST) { + // break fall through from ASGN + break; + } node->dump(); assert(false); break; @@ -267,13 +295,25 @@ void PromelaCodeAnalyzer::addCode(const std::string& code) { } opIter++; } - break; + + if (hasValue) { + if (td->maxValue < assignedValue) + td->maxValue = assignedValue; + if (td->minValue > assignedValue) + td->minValue = assignedValue; + } + + continue; // skip processing nested AST nodes } case PML_NAME: { + _typeDefs.types[node->value].minValue = 0; + _typeDefs.types[node->value].maxValue = 1; + break; } + default: +// node->dump(); break; -// node->dump(); // assert(false); } @@ -293,12 +333,20 @@ void PromelaCodeAnalyzer::addEvent(const std::string& eventName) { _lastEventIndex++; } +void PromelaCodeAnalyzer::addOrigState(const std::string& stateName) { + if (_origStateIndex.find(stateName) == _origStateIndex.end()) { + _origStateIndex[stateName] = _lastStateIndex++; + createMacroName(stateName); + } +} + void PromelaCodeAnalyzer::addState(const std::string& stateName) { if (_states.find(stateName) != _states.end()) return; createMacroName(stateName); +#if 0 // addLiteral(stateName); // _states[stateName] = enumerateLiteral(stateName); if (_origStateMap.find(stateName) == _origStateMap.end()) { @@ -312,13 +360,16 @@ void PromelaCodeAnalyzer::addState(const std::string& stateName) { } } } +#endif } +#if 0 int PromelaCodeAnalyzer::arrayIndexForOrigState(const std::string& stateName) { if (_origStateIndex.find(stateName) == _origStateIndex.end()) throw std::runtime_error("No original state " + stateName + " known"); return _origStateIndex[stateName]; } +#endif void PromelaCodeAnalyzer::addLiteral(const std::string& literal, int forceIndex) { if (boost::starts_with(literal, "'")) @@ -432,7 +483,7 @@ std::set<std::string> PromelaCodeAnalyzer::getEventsWithPrefix(const std::string } -void FSMToPromela::writeEvents(std::ostream& stream) { +void ChartToPromela::writeEvents(std::ostream& stream) { std::map<std::string, int> events = _analyzer.getEvents(); std::map<std::string, int>::iterator eventIter = events.begin(); stream << "/* event name identifiers */" << std::endl; @@ -445,15 +496,23 @@ void FSMToPromela::writeEvents(std::ostream& stream) { } } -void FSMToPromela::writeStates(std::ostream& stream) { +void ChartToPromela::writeStates(std::ostream& stream) { stream << "/* state name identifiers */" << std::endl; - for (int i = 0; i < _globalStates.size(); i++) { - stream << "#define " << "s" << i << " " << i; - stream << " /* from \"" << ATTR_CAST(_globalStates[i], "id") << "\" */" << std::endl; - } + + std::map<std::string, GlobalState*>::iterator stateIter = _globalConf.begin(); + while(stateIter != _globalConf.end()) { + stream << "#define " << "s" << stateIter->second->index << " " << stateIter->second->index; + stream << " /* from \"" << stateIter->first << "\" */" << std::endl; + stateIter++; + } + +// for (int i = 0; i < _globalConf.size(); i++) { +// stream << "#define " << "s" << i << " " << i; +// stream << " /* from \"" << ATTR_CAST(_globalStates[i], "id") << "\" */" << std::endl; +// } } -void FSMToPromela::writeStateMap(std::ostream& stream) { +void ChartToPromela::writeStateMap(std::ostream& stream) { stream << "/* macros for original state names */" << std::endl; std::map<std::string, int> origStates = _analyzer.getOrigStates(); for (std::map<std::string, int>::iterator origIter = origStates.begin(); origIter != origStates.end(); origIter++) { @@ -473,7 +532,7 @@ void FSMToPromela::writeStateMap(std::ostream& stream) { // } } -void FSMToPromela::writeTypeDefs(std::ostream& stream) { +void ChartToPromela::writeTypeDefs(std::ostream& stream) { stream << "/* typedefs */" << std::endl; PromelaCodeAnalyzer::PromelaTypedef typeDefs = _analyzer.getTypes(); if (typeDefs.types.size() == 0) @@ -498,15 +557,7 @@ void FSMToPromela::writeTypeDefs(std::ostream& stream) { PromelaCodeAnalyzer::PromelaTypedef currDef = *rIter; if (currDef.types.size() == 0 || currDef.name.size() == 0) continue; -// if (currDef.name.compare("_x_t") == 0) { -// stream << "typedef platform_t {" << std::endl; -// if (_analyzer.usesInPredicate()) { -// stream << " bool states[" << _analyzer.getOrigStates().size() << "];" << std::endl; -// } -// stream << "};" << std::endl; -// -// continue; -// } + stream << "typedef " << currDef.name << " {" << std::endl; if (currDef.name.compare("_event_t") == 0 && currDef.types.find("name") == currDef.types.end()) { // special treatment for _event stream << " int name;" << std::endl; @@ -517,7 +568,8 @@ void FSMToPromela::writeTypeDefs(std::ostream& stream) { continue; } if (tIter->second.types.size() == 0) { - stream << " int " << tIter->first << ";" << std::endl; // not further nested + stream << " " << declForRange(tIter->first, tIter->second.minValue, tIter->second.maxValue, true) << ";" << std::endl; // not further nested +// stream << " int " << tIter->first << ";" << std::endl; // not further nested } else { stream << " " << tIter->second.name << " " << tIter->first << ";" << std::endl; } @@ -525,17 +577,52 @@ void FSMToPromela::writeTypeDefs(std::ostream& stream) { stream << "};" << std::endl << std::endl; } - stream << "/* typedef instances */" << std::endl; - PromelaCodeAnalyzer::PromelaTypedef allTypes = _analyzer.getTypes(); - std::map<std::string, PromelaCodeAnalyzer::PromelaTypedef>::iterator typeIter = allTypes.types.begin(); - while(typeIter != allTypes.types.end()) { - stream << typeIter->second.name << " " << typeIter->first << ";" << std::endl; - typeIter++; - } +// stream << "/* typedef instances */" << std::endl; +// PromelaCodeAnalyzer::PromelaTypedef allTypes = _analyzer.getTypes(); +// std::map<std::string, PromelaCodeAnalyzer::PromelaTypedef>::iterator typeIter = allTypes.types.begin(); +// while(typeIter != allTypes.types.end()) { +// if (typeIter->second.types.size() > 0) { +// // an actual typedef +// stream << "hidden " << typeIter->second.name << " " << typeIter->first << ";" << std::endl; +// } else { +// stream << "hidden " << declForRange(typeIter->first, typeIter->second.minValue, typeIter->second.maxValue) << ";" << std::endl; +// } +// typeIter++; +// } } -Arabica::XPath::NodeSet<std::string> FSMToPromela::getTransientContent(const Arabica::DOM::Element<std::string>& state, const std::string& source) { +std::string ChartToPromela::declForRange(const std::string& identifier, long minValue, long maxValue, bool nativeOnly) { +// return "int " + identifier; // just for testing + + // we know nothing about this type + if (minValue == 0 && maxValue == 0) + return "int " + identifier; + + if (minValue < 0) { + // only short or int for negatives + if (minValue < -32769 || maxValue > 32767) + return "int " + identifier; + return "short " + identifier; + } + + // type is definitely positive + if (nativeOnly) { + if (maxValue > 32767) + return "int " + identifier; + if (maxValue > 255) + return "short " + identifier; + if (maxValue > 1) + return "byte " + identifier; + return "bool " + identifier; + } else { + return "unsigned " + identifier + " : " + toStr(BIT_WIDTH(maxValue)); + } +} + + +#if 0 +Arabica::XPath::NodeSet<std::string> ChartToPromela::getTransientContent(const Arabica::DOM::Element<std::string>& state, const std::string& source) { Arabica::XPath::NodeSet<std::string> content; Arabica::DOM::Element<std::string> currState = state; FlatStateIdentifier prevFlatId(source); @@ -584,8 +671,10 @@ Arabica::XPath::NodeSet<std::string> FSMToPromela::getTransientContent(const Ara } return content; } - -Node<std::string> FSMToPromela::getUltimateTarget(const Arabica::DOM::Element<std::string>& transition) { +#endif + +#if 0 +Node<std::string> ChartToPromela::getUltimateTarget(const Arabica::DOM::Element<std::string>& transition) { if (!HAS_ATTR(transition, "target")) { return transition.getParentNode(); } @@ -599,8 +688,9 @@ Node<std::string> FSMToPromela::getUltimateTarget(const Arabica::DOM::Element<st currState = _states[ATTR_CAST(transitions[0], "target")]; } } +#endif -void FSMToPromela::writeInlineComment(std::ostream& stream, const Arabica::DOM::Node<std::string>& node) { +void ChartToPromela::writeInlineComment(std::ostream& stream, const Arabica::DOM::Node<std::string>& node) { if (node.getNodeType() != Node_base::COMMENT_NODE) return; @@ -619,7 +709,291 @@ void FSMToPromela::writeInlineComment(std::ostream& stream, const Arabica::DOM:: } } -void FSMToPromela::writeExecutableContent(std::ostream& stream, const Arabica::DOM::Node<std::string>& node, int indent) { +void ChartToPromela::writeTransition(std::ostream& stream, const GlobalTransition* transition, int indent) { + std::string padding; + for (int i = 0; i < indent; i++) { + padding += " "; + } + + stream << "t" << transition->index << ":"; + int digits = 0; + LENGTH_FOR_NUMBER(transition->index, digits); + + INDENT_MIN(stream, 2 + digits, MIN_COMMENT_PADDING); + stream << " /* from state " << transition->source << " */" << std::endl; + + stream << padding << "atomic {" << std::endl; + indent++; + + for (std::list<GlobalTransition::Action>::const_iterator actionIter = transition->actions.begin(); actionIter != transition->actions.end(); actionIter++) { + if (actionIter->transition) { + // this is executable content from a transition + writeExecutableContent(stream, actionIter->transition, indent); + continue; + } + + if (actionIter->onExit) { + // executable content from an onexit element + writeExecutableContent(stream, actionIter->onExit, indent); + continue; + } + + if (actionIter->onEntry) { + // executable content from an onentry element + writeExecutableContent(stream, actionIter->onEntry, indent); + continue; + } + + if (actionIter->invoke) { + // an invoke element + continue; + } + + if (actionIter->uninvoke) { + // an invoke element to uninvoke + continue; + } + + if (actionIter->exited) { + // we left a state + if (_analyzer.usesInPredicate()) { + stream << padding << "_x.states[" << _analyzer.macroForLiteral(ATTR(actionIter->exited, "id")) << "] = false; " << std::endl; + } + continue; + } + + if (actionIter->entered) { + // we entered a state + if (_analyzer.usesInPredicate()) { + stream << padding << "_x.states[" << _analyzer.macroForLiteral(ATTR(actionIter->entered, "id")) << "] = true; " << std::endl; + } + continue; + } + } + + GlobalState* newState = _globalConf[transition->destination]; + assert(newState != NULL); + + stream << padding << " s = s" << newState->index << ";"; + LENGTH_FOR_NUMBER(newState->index, digits); + INDENT_MIN(stream, 10 + digits, MIN_COMMENT_PADDING); + + stream << " /* to state " << transition->destination << " */" << std::endl; + + + if (newState->isFinal) { + stream << padding << " goto terminate;"; + INDENT_MIN(stream, padding.length() + 14, MIN_COMMENT_PADDING); + stream << "/* final state */" << std::endl; + } else if (transition->isEventless) { + stream << padding << " goto nextTransition;"; + INDENT_MIN(stream, padding.length() + 19, MIN_COMMENT_PADDING); + stream << "/* spontaneous transition, check for more transitions */" << std::endl; + } else { + stream << padding << " eventLess = true;" << std::endl; + stream << padding << " goto nextTransition;"; + INDENT_MIN(stream, padding.length() + 21, MIN_COMMENT_PADDING); + stream << "/* ordinary transition, check for spontaneous transitions */" << std::endl; + } + stream << padding << "}" << std::endl; + +} + +void ChartToPromela::writeExecutableContent(std::ostream& stream, const Arabica::DOM::Node<std::string>& node, int indent) { + if (!node) + return; + + std::string padding; + for (int i = 0; i < indent; i++) { + padding += " "; + } + + if (node.getNodeType() == Node_base::COMMENT_NODE) { + // we cannot have labels in an atomic block, just process inline promela + PromelaInlines promInls = getInlinePromela(boost::trim_copy(node.getNodeValue())); + // TODO! + // if (promInls) { + // stream << padding << "skip;" << std::endl; + // stream << beautifyIndentation(inlinePromela.str(), indent) << std::endl; + // } + } + + if (node.getNodeType() == Node_base::TEXT_NODE) { + if (boost::trim_copy(node.getNodeValue()).length() > 0) + stream << beautifyIndentation(_analyzer.replaceLiterals(node.getNodeValue()), indent) << std::endl; + } + + if (node.getNodeType() != Node_base::ELEMENT_NODE) + return; // skip anything not an element + + Arabica::DOM::Element<std::string> nodeElem = Arabica::DOM::Element<std::string>(node); + + if (false) { + } else if(TAGNAME(nodeElem) == "onentry" || TAGNAME(nodeElem) == "onexit" || TAGNAME(nodeElem) == "transition") { + // descent into childs and write their contents + Arabica::DOM::Node<std::string> child = node.getFirstChild(); + while(child) { + writeExecutableContent(stream, child, indent); + child = child.getNextSibling(); + } + } else if(TAGNAME(nodeElem) == "script") { + NodeSet<std::string> scriptText = filterChildType(Node_base::TEXT_NODE, node, true); + for (int i = 0; i < scriptText.size(); i++) { + stream << _analyzer.replaceLiterals(beautifyIndentation(scriptText[i].getNodeValue(), indent)) << std::endl; + } + + } else if(TAGNAME(nodeElem) == "log") { + std::string label = (HAS_ATTR(nodeElem, "label") ? ATTR(nodeElem, "label") : ""); + std::string expr = (HAS_ATTR(nodeElem, "expr") ? ATTR(nodeElem, "expr") : ""); + std::string trimmedExpr = boost::trim_copy(expr); + bool isStringLiteral = (boost::starts_with(trimmedExpr, "\"") || boost::starts_with(trimmedExpr, "'")); + + std::string formatString; + std::string varString; + std::string seperator; + + if (label.size() > 0) { + formatString += label + ": "; + } + + if (isStringLiteral) { + formatString += expr; + } else { + formatString += "%d"; + varString += seperator + expr; + } + + if (varString.length() > 0) { + stream << padding << "printf(\"" + formatString + "\", " + varString + ");" << std::endl; + } else { + stream << padding << "printf(\"" + formatString + "\");" << std::endl; + } + + } else if(TAGNAME(nodeElem) == "foreach") { + stream << padding << "for (" << (HAS_ATTR(nodeElem, "index") ? ATTR(nodeElem, "index") : "_index") << " in " << ATTR(nodeElem, "array") << ") {" << std::endl; + if (HAS_ATTR(nodeElem, "item")) { + stream << padding << " " << ATTR(nodeElem, "item") << " = " << ATTR(nodeElem, "array") << "[" << (HAS_ATTR(nodeElem, "index") ? ATTR(nodeElem, "index") : "_index") << "];" << std::endl; + } + Arabica::DOM::Node<std::string> child = node.getFirstChild(); + while(child) { + writeExecutableContent(stream, child, indent + 1); + child = child.getNextSibling(); + } + if (HAS_ATTR(nodeElem, "index")) + stream << padding << " " << ATTR(nodeElem, "index") << "++;" << std::endl; + stream << padding << "}" << std::endl; + + } else if(TAGNAME(nodeElem) == "if") { + NodeSet<std::string> condChain; + condChain.push_back(node); + condChain.push_back(filterChildElements(_nsInfo.xmlNSPrefix + "elseif", node)); + condChain.push_back(filterChildElements(_nsInfo.xmlNSPrefix + "else", node)); + + writeIfBlock(stream, condChain, indent); + + } else if(TAGNAME(nodeElem) == "assign") { + if (HAS_ATTR(nodeElem, "location")) { + stream << padding << ATTR(nodeElem, "location") << " = "; + } + if (HAS_ATTR(nodeElem, "expr")) { + stream << _analyzer.replaceLiterals(ATTR(nodeElem, "expr")) << ";" << std::endl; + } else { + NodeSet<std::string> assignTexts = filterChildType(Node_base::TEXT_NODE, nodeElem, true); + if (assignTexts.size() > 0) { + stream << _analyzer.replaceLiterals(boost::trim_copy(assignTexts[0].getNodeValue())) << ";" << std::endl; + } + } + } else if(TAGNAME(nodeElem) == "send" || TAGNAME(nodeElem) == "raise") { + std::string targetQueue; + if (TAGNAME(nodeElem) == "raise") { + targetQueue = "iQ!"; + } else if (!HAS_ATTR(nodeElem, "target")) { + targetQueue = "tmpQ!"; + } else if (ATTR(nodeElem, "target").compare("#_internal") == 0) { + targetQueue = "iQ!"; + } + if (targetQueue.length() > 0) { + // this is for our external queue + std::string event; + + if (HAS_ATTR(nodeElem, "event")) { + event = _analyzer.macroForLiteral(ATTR(nodeElem, "event")); + } else if (HAS_ATTR(nodeElem, "eventexpr")) { + event = ATTR(nodeElem, "eventexpr"); + } + if (_analyzer.usesComplexEventStruct()) { + stream << padding << "{" << std::endl; + stream << padding << " _event_t tmpEvent;" << std::endl; + stream << padding << " tmpEvent.name = " << event << ";" << std::endl; + + if (HAS_ATTR(nodeElem, "idlocation")) { + stream << padding << " /* idlocation */" << std::endl; + stream << padding << " _lastSendId = _lastSendId + 1;" << std::endl; + stream << padding << " " << ATTR(nodeElem, "idlocation") << " = _lastSendId;" << std::endl; + stream << padding << " tmpEvent.sendid = _lastSendId;" << std::endl; + stream << padding << " if" << std::endl; + stream << padding << " :: _lastSendId == 2147483647 -> _lastSendId = 0;" << std::endl; + stream << padding << " :: timeout -> skip;" << std::endl; + stream << padding << " fi;" << std::endl; + } else if (HAS_ATTR(nodeElem, "id")) { + stream << padding << " tmpEvent.sendid = " << _analyzer.macroForLiteral(ATTR(nodeElem, "id")) << ";" << std::endl; + } + + if (_analyzer.usesEventField("origintype") && targetQueue.compare("iQ!") != 0) { + stream << padding << " tmpEvent.origintype = " << _analyzer.macroForLiteral("http://www.w3.org/TR/scxml/#SCXMLEventProcessor") << ";" << std::endl; + } + + if (_analyzer.usesEventField("type")) { + std::string eventType = (targetQueue.compare("iQ!") == 0 ? _analyzer.macroForLiteral("internal") : _analyzer.macroForLiteral("external")); + stream << padding << " tmpEvent.type = " << eventType << ";" << std::endl; + } + + NodeSet<std::string> sendParams = filterChildElements(_nsInfo.xmlNSPrefix + "param", nodeElem); + NodeSet<std::string> sendContents = filterChildElements(_nsInfo.xmlNSPrefix + "content", nodeElem); + std::string sendNameList = ATTR(nodeElem, "namelist"); + if (sendParams.size() > 0) { + for (int i = 0; i < sendParams.size(); i++) { + Element<std::string> paramElem = Element<std::string>(sendParams[i]); + stream << padding << " tmpEvent.data." << ATTR(paramElem, "name") << " = " << ATTR(paramElem, "expr") << ";" << std::endl; + } + } + if (sendNameList.size() > 0) { + std::list<std::string> nameListIds = tokenizeIdRefs(sendNameList); + std::list<std::string>::iterator nameIter = nameListIds.begin(); + while(nameIter != nameListIds.end()) { + stream << padding << " tmpEvent.data." << *nameIter << " = " << *nameIter << ";" << std::endl; + nameIter++; + } + } + + if (sendParams.size() == 0 && sendNameList.size() == 0 && sendContents.size() > 0) { + Element<std::string> contentElem = Element<std::string>(sendContents[0]); + if (contentElem.hasChildNodes() && contentElem.getFirstChild().getNodeType() == Node_base::TEXT_NODE) { + stream << padding << " tmpEvent.data = " << spaceNormalize(contentElem.getFirstChild().getNodeValue()) << ";" << std::endl; + } else if (HAS_ATTR(contentElem, "expr")) { + stream << padding << " tmpEvent.data = " << _analyzer.replaceLiterals(ATTR(contentElem, "expr")) << ";" << std::endl; + } + } + stream << padding << " " << targetQueue << "tmpEvent;" << std::endl; + stream << padding << "}" << std::endl; + } else { + stream << padding << targetQueue << event << ";" << std::endl; + } + } + } else if(TAGNAME(nodeElem) == "invoke") { + _invokers[ATTR(nodeElem, "invokeid")].writeStartEventSources(stream, indent); + } else if(TAGNAME(nodeElem) == "uninvoke") { + stream << padding << ATTR(nodeElem, "invokeid") << "EventSourceDone" << "= 1;" << std::endl; + } else if(TAGNAME(nodeElem) == "cancel") { + // noop + } else { + std::cerr << "'" << TAGNAME(nodeElem) << "'" << std::endl << nodeElem << std::endl; + assert(false); + } +} + +#if 0 +void ChartToPromela::writeExecutableContent(std::ostream& stream, const Arabica::DOM::Node<std::string>& node, int indent) { // std::cout << std::endl << node << std::endl; if (!node) @@ -914,6 +1288,8 @@ void FSMToPromela::writeExecutableContent(std::ostream& stream, const Arabica::D _invokers[ATTR(nodeElem, "invokeid")].writeStartEventSources(stream, indent); } else if(TAGNAME(nodeElem) == "uninvoke") { stream << padding << ATTR(nodeElem, "invokeid") << "EventSourceDone" << "= 1;" << std::endl; + } else if(TAGNAME(nodeElem) == "cancel") { + // noop } else { std::cerr << "'" << TAGNAME(nodeElem) << "'" << std::endl << nodeElem << std::endl; @@ -921,8 +1297,9 @@ void FSMToPromela::writeExecutableContent(std::ostream& stream, const Arabica::D } } - -PromelaInlines FSMToPromela::getInlinePromela(const std::string& content) { +#endif + +PromelaInlines ChartToPromela::getInlinePromela(const std::string& content) { PromelaInlines prom; std::stringstream ssLine(content); @@ -996,13 +1373,13 @@ PromelaInlines FSMToPromela::getInlinePromela(const std::string& content) { return prom; } -PromelaInlines FSMToPromela::getInlinePromela(const Arabica::DOM::Node<std::string>& node) { +PromelaInlines ChartToPromela::getInlinePromela(const Arabica::DOM::Node<std::string>& node) { if (node.getNodeType() != Node_base::COMMENT_NODE) return getInlinePromela(std::string()); return getInlinePromela(node.getNodeValue()); } -PromelaInlines FSMToPromela::getInlinePromela(const Arabica::XPath::NodeSet<std::string>& elements, bool recurse) { +PromelaInlines ChartToPromela::getInlinePromela(const Arabica::XPath::NodeSet<std::string>& elements, bool recurse) { PromelaInlines allPromInls; Arabica::XPath::NodeSet<std::string> comments = filterChildType(Node_base::COMMENT_NODE, elements, recurse); @@ -1012,7 +1389,7 @@ PromelaInlines FSMToPromela::getInlinePromela(const Arabica::XPath::NodeSet<std: return allPromInls; } -void FSMToPromela::writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& condChain, int indent) { +void ChartToPromela::writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& condChain, int indent) { if (condChain.size() == 0) return; @@ -1082,7 +1459,8 @@ void FSMToPromela::writeIfBlock(std::ostream& stream, const Arabica::XPath::Node } -std::string FSMToPromela::beautifyIndentation(const std::string& code, int indent) { + +std::string ChartToPromela::beautifyIndentation(const std::string& code, int indent) { std::string padding; for (int i = 0; i < indent; i++) { @@ -1113,7 +1491,7 @@ std::string FSMToPromela::beautifyIndentation(const std::string& code, int inden return beautifiedSS.str(); } -void FSMToPromela::writeStrings(std::ostream& stream) { +void ChartToPromela::writeStrings(std::ostream& stream) { stream << "/* string literals */" << std::endl; std::set<std::string> literals = _analyzer.getLiterals(); std::map<std::string, int> events = _analyzer.getEvents(); @@ -1125,50 +1503,85 @@ void FSMToPromela::writeStrings(std::ostream& stream) { } } -void FSMToPromela::writeDeclarations(std::ostream& stream) { +void ChartToPromela::writeDeclarations(std::ostream& stream) { + + stream << "/* global variables */" << std::endl; + + if (_analyzer.usesComplexEventStruct()) { + // event is defined with the typedefs + stream << "_event_t _event; /* current state */" << std::endl; + stream << "unsigned s : " << BIT_WIDTH(_globalConf.size() + 1) << "; /* current state */" << std::endl; + stream << "chan iQ = [" << MSG_QUEUE_LENGTH << "] of {_event_t} /* internal queue */" << std::endl; + stream << "chan eQ = [" << MSG_QUEUE_LENGTH << "] of {_event_t} /* external queue */" << std::endl; + stream << "chan tmpQ = [" << MSG_QUEUE_LENGTH << "] of {_event_t} /* temporary queue for external events in transitions */" << std::endl; + stream << "hidden _event_t tmpQItem;" << std::endl; + } else { + stream << "unsigned _event : " << BIT_WIDTH(_analyzer.getEvents().size() + 1) << "; /* current event */" << std::endl; + stream << "unsigned s : " << BIT_WIDTH(_globalConf.size() + 1) << "; /* current state */" << std::endl; + stream << "chan iQ = [" << MSG_QUEUE_LENGTH << "] of {int} /* internal queue */" << std::endl; + stream << "chan eQ = [" << MSG_QUEUE_LENGTH << "] of {int} /* external queue */" << std::endl; + stream << "chan tmpQ = [" << MSG_QUEUE_LENGTH << "] of {int} /* temporary queue for external events in transitions */" << std::endl; + stream << "hidden unsigned tmpQItem : " << BIT_WIDTH(_analyzer.getEvents().size() + 1) << ";" << std::endl; + } + stream << "bool eventLess = true; /* whether to process event-less only n this step */" << std::endl; + stream << "hidden int _index; /* helper for indexless foreach loops */" << std::endl; + + if (_analyzer.getTypes().types.find("_ioprocessors") != _analyzer.getTypes().types.end()) { + stream << "hidden _ioprocessors_t _ioprocessors;" << std::endl; + } + + if (_analyzer.usesEventField("sendid")) { + stream << "hidden int _lastSendId = 0; /* sequential counter for send ids */"; + } + +// if (_analyzer.usesPlatformVars()) { +// stream << "_x_t _x;" << std::endl; +// } + + stream << std::endl; // get all data elements NodeSet<std::string> datas = _xpath.evaluate("//" + _nsInfo.xpathPrefix + "data", _scxml).asNodeSet(); -// NodeSet<std::string> dataText = filterChildType(Node_base::TEXT_NODE, datas, true); - + // NodeSet<std::string> dataText = filterChildType(Node_base::TEXT_NODE, datas, true); + // write their text content stream << "/* datamodel variables */" << std::endl; std::set<std::string> processedIdentifiers; for (int i = 0; i < datas.size(); i++) { - + Node<std::string> data = datas[i]; if (isInEmbeddedDocument(data)) continue; - + std::string identifier = (HAS_ATTR_CAST(data, "id") ? ATTR_CAST(data, "id") : ""); std::string expression = (HAS_ATTR_CAST(data, "expr") ? ATTR_CAST(data, "expr") : ""); std::string type = boost::trim_copy(HAS_ATTR_CAST(data, "type") ? ATTR_CAST(data, "type") : ""); - + if (processedIdentifiers.find(identifier) != processedIdentifiers.end()) continue; processedIdentifiers.insert(identifier); - + if (boost::starts_with(type, "string")) { type = "int" + type.substr(6, type.length() - 6); } std::string arrSize; - + NodeSet<std::string> dataText = filterChildType(Node_base::TEXT_NODE, data, true); std::string value; if (dataText.size() > 0) { value = dataText[0].getNodeValue(); boost::trim(value); } - + if (identifier.length() > 0) { - + size_t bracketPos = type.find("["); if (bracketPos != std::string::npos) { arrSize = type.substr(bracketPos, type.length() - bracketPos); type = type.substr(0, bracketPos); } std::string decl = type + " " + identifier + arrSize; - + if (arrSize.length() > 0) { stream << decl << ";" << std::endl; _varInitializers.push_back(value); @@ -1190,36 +1603,29 @@ void FSMToPromela::writeDeclarations(std::ostream& stream) { stream << beautifyIndentation(value) << std::endl; } } - - stream << std::endl; - stream << "/* global variables */" << std::endl; - - if (_analyzer.usesComplexEventStruct()) { - // event is defined with the typedefs - stream << "unsigned s : " << BIT_WIDTH(_globalStates.size() + 1) << "; /* current state */" << std::endl; - stream << "chan iQ = [10] of {_event_t} /* internal queue */" << std::endl; - stream << "chan eQ = [10] of {_event_t} /* external queue */" << std::endl; - stream << "chan tmpQ = [10] of {_event_t} /* temporary queue for external events in transitions */" << std::endl; - stream << "_event_t tmpQItem;" << std::endl; - } else { - stream << "unsigned _event : " << BIT_WIDTH(_analyzer.getEvents().size() + 1) << "; /* current event */" << std::endl; - stream << "unsigned s : " << BIT_WIDTH(_globalStates.size() + 1) << "; /* current state */" << std::endl; - stream << "chan iQ = [10] of {int} /* internal queue */" << std::endl; - stream << "chan eQ = [10] of {int} /* external queue */" << std::endl; - stream << "chan tmpQ = [10] of {int} /* temporary queue for external events in transitions */" << std::endl; - stream << "unsigned tmpQItem : " << BIT_WIDTH(_analyzer.getEvents().size() + 1) << ";" << std::endl; - } - stream << "bool eventLess = true; /* whether to process event-less only n this step */" << std::endl; - stream << "hidden int _index; /* helper for indexless foreach loops */" << std::endl; - - if (_analyzer.usesEventField("sendid")) { - stream << "hidden int _lastSendId = 0; /* sequential counter for send ids */"; + + PromelaCodeAnalyzer::PromelaTypedef allTypes = _analyzer.getTypes(); + std::map<std::string, PromelaCodeAnalyzer::PromelaTypedef>::iterator typeIter = allTypes.types.begin(); + while(typeIter != allTypes.types.end()) { + if (processedIdentifiers.find(typeIter->first) != processedIdentifiers.end()) { + typeIter++; + continue; + } + if (typeIter->first == "_event" || typeIter->first == "_ioprocessors" || typeIter->first == "_SESSIONID" || typeIter->first == "_NAME") { + typeIter++; + continue; + } + + processedIdentifiers.insert(typeIter->first); + + if (typeIter->second.types.size() == 0) { + stream << "hidden " << declForRange(typeIter->first, typeIter->second.minValue, typeIter->second.maxValue) << ";" << std::endl; + } else { + stream << "hidden " << typeIter->second.name << " " << typeIter->first << ";" << std::endl; + } + typeIter++; } -// if (_analyzer.usesPlatformVars()) { -// stream << "_x_t _x;" << std::endl; -// } - stream << std::endl; stream << "/* event sources */" << std::endl; @@ -1235,7 +1641,7 @@ void FSMToPromela::writeDeclarations(std::ostream& stream) { } -void FSMToPromela::writeEventSources(std::ostream& stream) { +void ChartToPromela::writeEventSources(std::ostream& stream) { std::list<PromelaInline>::iterator inlineIter; if (_globalEventSource) { @@ -1249,22 +1655,28 @@ void FSMToPromela::writeEventSources(std::ostream& stream) { } } -void FSMToPromela::writeFSM(std::ostream& stream) { +void ChartToPromela::writeFSM(std::ostream& stream) { NodeSet<std::string> transitions; stream << "proctype step() {" << std::endl; // write initial transition - transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _startState); - assert(transitions.size() == 1); +// transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _startState); +// assert(transitions.size() == 1); stream << " /* transition's executable content */" << std::endl; - writeExecutableContent(stream, transitions[0], 1); - for (int i = 0; i < _globalStates.size(); i++) { - if (_globalStates[i] == _startState) - continue; - NodeSet<std::string> transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _globalStates[i]); - for (int j = 0; j < transitions.size(); j++) { - writeExecutableContent(stream, transitions[j], 1); + assert(_start->sortedOutgoing.size() == 1); + // initial transition has to be first one for control flow at start + writeTransition(stream, _start->sortedOutgoing.front(), 1); + + // every other transition + for (std::map<std::string, GlobalState*>::iterator stateIter = _globalConf.begin(); stateIter != _globalConf.end(); stateIter++) { + for (std::list<GlobalTransition*>::iterator transIter = stateIter->second->sortedOutgoing.begin(); transIter != stateIter->second->sortedOutgoing.end(); transIter++) { + // don't write initial transition + if (_start->sortedOutgoing.front() == *transIter) + continue; + // don't write trivial transitions + if ((*transIter)->hasExecutableContent) + writeTransition(stream, *transIter, 1); } } @@ -1304,37 +1716,35 @@ void FSMToPromela::writeFSM(std::ostream& stream) { stream << "}" << std::endl; } -void FSMToPromela::writeEventDispatching(std::ostream& stream) { - for (int i = 0; i < _globalStates.size(); i++) { - if (_globalStates[i] == _startState) - continue; +void ChartToPromela::writeEventDispatching(std::ostream& stream) { + for (std::map<std::string, GlobalState*>::iterator stateIter = _globalConf.begin(); stateIter != _globalConf.end(); stateIter++) { +// if (_globalStates[i] == _startState) +// continue; - int number = i; + const std::string& stateId = stateIter->first; + const GlobalState* state = stateIter->second; + int digits = 0; - do { - number /= 10; - digits++; - } while (number != 0); - stream << " :: (s == s" << i << ") -> {"; + LENGTH_FOR_NUMBER(state->index, digits); + stream << " :: (s == s" << state->index << ") -> {"; INDENT_MIN(stream, 18 + digits, MIN_COMMENT_PADDING); - stream << " /* from state " << ATTR_CAST(_globalStates[i], "id") << " */" << std::endl; + stream << " /* from state " << stateId << " */" << std::endl; - NodeSet<std::string> transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _globalStates[i]); - writeDispatchingBlock(stream, transitions, 2); + writeDispatchingBlock(stream, state->sortedOutgoing, 2); // stream << " goto nextStep;"; stream << " }" << std::endl; } } - -void FSMToPromela::writeDispatchingBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& transChain, int indent) { + +void ChartToPromela::writeDispatchingBlock(std::ostream& stream, std::list<GlobalTransition*> transitions, int indent) { std::string padding; for (int i = 0; i < indent; i++) { padding += " "; } - if (transChain.size() == 0) { + if (transitions.size() == 0) { stream << padding << "eventLess = false;" << std::endl; stream << padding << "goto nextStep;"; INDENT_MIN(stream, padding.size() + 13, MIN_COMMENT_PADDING); @@ -1343,22 +1753,23 @@ void FSMToPromela::writeDispatchingBlock(std::ostream& stream, const Arabica::XP } - Element<std::string> currTrans = Element<std::string>(transChain[0]); + GlobalTransition* currTrans = transitions.front(); + transitions.pop_front(); std::stringstream tmpSS; tmpSS << padding << "if" << std::endl; size_t lineStart = tmpSS.tellp(); - if (HAS_ATTR(currTrans, "cond")) { + if (currTrans->condition.size() > 0) { tmpSS << padding << ":: (("; } else { tmpSS << padding << ":: ("; } - if (!HAS_ATTR(currTrans, "event")) { + if (currTrans->isEventless) { tmpSS << "eventLess"; } else { - std::string eventDescs = ATTR(currTrans, "event"); + std::string eventDescs = currTrans->eventDesc; std::list<std::string> eventNames = tokenizeIdRefs(eventDescs); std::set<std::string> eventPrefixes; @@ -1396,33 +1807,53 @@ void FSMToPromela::writeDispatchingBlock(std::ostream& stream, const Arabica::XP } tmpSS << ")"; - if (HAS_ATTR(currTrans, "cond")) { - tmpSS << (HAS_ATTR(currTrans, "cond") ? " && " + _analyzer.replaceLiterals(ATTR(currTrans, "cond")) + ")": ""); - } - tmpSS << " -> goto t" << _transitions[currTrans] << ";"; - size_t lineEnd = tmpSS.tellp(); - size_t lineLength = lineEnd - lineStart; - - for (int i = lineLength; i < MIN_COMMENT_PADDING; i++) - tmpSS << " "; + if (currTrans->condition.size() > 0) { + tmpSS << " && " + _analyzer.replaceLiterals(currTrans->condition) + ")"; + } + if (currTrans->hasExecutableContent) { + tmpSS << " -> goto t" << currTrans->index << ";"; + size_t lineEnd = tmpSS.tellp(); + size_t lineLength = lineEnd - lineStart; + + for (int i = lineLength; i < MIN_COMMENT_PADDING; i++) + tmpSS << " "; + + tmpSS << " /* transition to " << currTrans->destination << " */" << std::endl; + } else { + + tmpSS << " -> {" << std::endl; + GlobalState* newState = _globalConf[currTrans->destination]; + assert(newState != NULL); + tmpSS << padding << " s = s" << newState->index << ";" << std::endl; + + if (newState->isFinal) { + tmpSS << padding << " goto terminate;"; + INDENT_MIN(tmpSS, padding.length() + 14, MIN_COMMENT_PADDING); + tmpSS << "/* final state */" << std::endl; + } else if (currTrans->isEventless) { + tmpSS << padding << " goto nextTransition;"; + INDENT_MIN(tmpSS, padding.length() + 19, MIN_COMMENT_PADDING); + tmpSS << "/* spontaneous transition, check for more transitions */" << std::endl; + } else { + tmpSS << padding << " eventLess = true;" << std::endl; + tmpSS << padding << " goto nextTransition;"; + INDENT_MIN(tmpSS, padding.length() + 21, MIN_COMMENT_PADDING); + tmpSS << "/* ordinary transition, check for spontaneous transitions */" << std::endl; + } - tmpSS << " /* transition to " << ATTR_CAST(getUltimateTarget(currTrans), "id") << " */" << std::endl; + tmpSS << padding << "}" << std::endl; + } stream << tmpSS.str(); stream << padding << ":: else {" << std::endl; - Arabica::XPath::NodeSet<std::string> cdrTransChain; - for (int i = 1; i < transChain.size(); i++) { - cdrTransChain.push_back(transChain[i]); - } - writeDispatchingBlock(stream, cdrTransChain, indent + 1); + writeDispatchingBlock(stream, transitions, indent + 1); stream << padding << "}" << std::endl; stream << padding << "fi;" << std::endl; } - -void FSMToPromela::writeMain(std::ostream& stream) { +void ChartToPromela::writeMain(std::ostream& stream) { stream << std::endl; stream << "init {" << std::endl; if (_varInitializers.size() > 0) { @@ -1441,20 +1872,20 @@ void FSMToPromela::writeMain(std::ostream& stream) { } -void FSMToPromela::initNodes() { +void ChartToPromela::initNodes() { + // get all states - NodeSet<std::string> states = filterChildElements(_nsInfo.xmlNSPrefix + "state", _scxml); + NodeSet<std::string> states = getAllStates(); for (int i = 0; i < states.size(); i++) { if (InterpreterImpl::isInEmbeddedDocument(states[i])) continue; - _states[ATTR_CAST(states[i], "id")] = Element<std::string>(states[i]); - _analyzer.addState(ATTR_CAST(states[i], "id")); - if (HAS_ATTR_CAST(states[i], "transient") && DOMUtils::attributeIsTrue(ATTR_CAST(states[i], "transient"))) - continue; - _globalStates.push_back(states[i]); + Element<std::string> stateElem(states[i]); + _analyzer.addOrigState(ATTR(stateElem, "id")); + if (isCompound(stateElem) || isParallel(stateElem)) { + _analyzer.addEvent("done.state." + ATTR(stateElem, "id")); + } } - _startState = _states[ATTR(_scxml, "initial")]; - + // initialize event trie with all events that might occur NodeSet<std::string> internalEventNames; internalEventNames.push_back(_xpath.evaluate("//" + _nsInfo.xpathPrefix + "transition", _scxml).asNodeSet()); @@ -1499,6 +1930,7 @@ void FSMToPromela::initNodes() { } } + // external event names from comments NodeSet<std::string> promelaEventSourceComments; NodeSet<std::string> invokers = _xpath.evaluate("//" + _nsInfo.xpathPrefix + "invoke", _scxml).asNodeSet(); @@ -1527,13 +1959,15 @@ void FSMToPromela::initNodes() { } } +#if 0 // enumerate transitions NodeSet<std::string> transitions = filterChildElements(_nsInfo.xmlNSPrefix + "transition", _scxml, true); int index = 0; for (int i = 0; i < transitions.size(); i++) { _transitions[Element<std::string>(transitions[i])] = index++; } - +#endif + // add platform variables as string literals _analyzer.addLiteral("_sessionid"); _analyzer.addLiteral("_name"); @@ -1622,7 +2056,7 @@ void FSMToPromela::initNodes() { } -std::string FSMToPromela::sanitizeCode(const std::string& code) { +std::string ChartToPromela::sanitizeCode(const std::string& code) { std::string replaced = code; boost::replace_all(replaced, "\"", "'"); boost::replace_all(replaced, "_sessionid", "_SESSIONID"); @@ -1643,18 +2077,17 @@ void PromelaInline::dump() { } } -void FSMToPromela::writeProgram(std::ostream& stream) { - - if (!HAS_ATTR(_scxml, "flat") || !DOMUtils::attributeIsTrue(ATTR(_scxml, "flat"))) { - LOG(ERROR) << "Given SCXML document was not flattened"; - return; - } +void ChartToPromela::writeProgram(std::ostream& stream) { if (!HAS_ATTR(_scxml, "datamodel") || ATTR(_scxml, "datamodel") != "promela") { LOG(ERROR) << "Can only convert SCXML documents with \"promela\" datamodel"; return; } + if (_start == NULL) { + interpret(); + } + if (HAS_ATTR(_scxml, "binding") && ATTR(_scxml, "binding") != "early") { LOG(ERROR) << "Can only convert for early data bindings"; return; @@ -1688,10 +2121,11 @@ void FSMToPromela::writeProgram(std::ostream& stream) { // write ltl expression for success std::stringstream acceptingStates; std::string seperator; - for (int i = 0; i < _globalStates.size(); i++) { - FlatStateIdentifier flatId(ATTR_CAST(_globalStates[i], "id")); + + for (std::map<std::string, GlobalState*>::iterator stateIter = _globalConf.begin(); stateIter != _globalConf.end(); stateIter++) { + FlatStateIdentifier flatId(stateIter->first); if (std::find(flatId.getActive().begin(), flatId.getActive().end(), "pass") != flatId.getActive().end()) { - acceptingStates << seperator << "s == s" << i; + acceptingStates << seperator << "s == s" << stateIter->second->index; seperator = " || "; } } diff --git a/src/uscxml/transform/FSMToPromela.h b/src/uscxml/transform/ChartToPromela.h index 3a9e263..75e3339 100644 --- a/src/uscxml/transform/FSMToPromela.h +++ b/src/uscxml/transform/ChartToPromela.h @@ -17,9 +17,11 @@ * @endcond */ -#ifndef FSMTOPROMELA_H_RP48RFDJ -#define FSMTOPROMELA_H_RP48RFDJ +#ifndef CHARTTOPROMELA_H_RP48RFDJ +#define CHARTTOPROMELA_H_RP48RFDJ +#include "Transformer.h" +#include "ChartToFSM.h" #include "uscxml/interpreter/InterpreterDraft6.h" #include "uscxml/DOMUtils.h" #include "uscxml/util/Trie.h" @@ -88,10 +90,12 @@ class USCXML_API PromelaCodeAnalyzer { public: class PromelaTypedef { public: - PromelaTypedef() : arraySize(0) {} + PromelaTypedef() : arraySize(0), minValue(0), maxValue(0) {} std::string name; std::string type; size_t arraySize; + size_t minValue; + size_t maxValue; std::map<std::string, PromelaTypedef> types; bool operator==(const PromelaTypedef& other) const { @@ -106,10 +110,11 @@ public: void addCode(const std::string& code); void addEvent(const std::string& eventName); void addState(const std::string& stateName); + void addOrigState(const std::string& stateName); void addLiteral(const std::string& stateName, int forceIndex = -1); bool usesComplexEventStruct() { - return _typeDefs.types.find("_event") != _typeDefs.types.end(); + return _typeDefs.types.find("_event") != _typeDefs.types.end() && _typeDefs.types["_event"].types.size() > 0; } bool usesEventField(const std::string& fieldName) { if (usesComplexEventStruct() && _typeDefs.types["_event"].types.find(fieldName) != _typeDefs.types["_event"].types.end()) @@ -126,7 +131,6 @@ public: std::string macroForLiteral(const std::string& literal); int indexForLiteral(const std::string& literal); - int arrayIndexForOrigState(const std::string& stateName); std::set<std::string> getLiterals() { return _strLiterals; @@ -144,11 +148,6 @@ public: return _origStateIndex; } - std::list<std::string>& getOrigStates(const std::string& state) { - if (_origStateMap.find(state) == _origStateMap.end()) - throw std::runtime_error("No original states known for " + state); - return _origStateMap[state]; - } Trie& getTrie() { return _eventTrie; @@ -156,7 +155,7 @@ public: std::string replaceLiterals(const std::string code); - PromelaTypedef getTypes() { + PromelaTypedef& getTypes() { return _typeDefs; } @@ -170,7 +169,6 @@ protected: std::map<std::string, int> _origStateIndex; // state enumeration for original states std::map<std::string, int> _states; - std::map<std::string, std::list<std::string> > _origStateMap; // states from the original state chart std::map<std::string, int> _events; PromelaTypedef _typeDefs; @@ -214,19 +212,23 @@ public: PromelaCodeAnalyzer* analyzer; }; -class USCXML_API FSMToPromela : public InterpreterDraft6 { +class USCXML_API ChartToPromela : public TransformerImpl, public ChartToFSM { public: - static void writeProgram(std::ostream& stream, - const Interpreter& interpreter); - - static std::string beautifyIndentation(const std::string& code, int indent = 0); + virtual ~ChartToPromela() {} + static Transformer transform(const Interpreter& other); + + void writeTo(std::ostream& stream); + protected: - FSMToPromela(); - void writeProgram(std::ostream& stream); + ChartToPromela(const Interpreter& other) : TransformerImpl(), ChartToFSM(other) {} void initNodes(); + static std::string beautifyIndentation(const std::string& code, int indent = 0); + + void writeProgram(std::ostream& stream); + void writeEvents(std::ostream& stream); void writeStates(std::ostream& stream); void writeStateMap(std::ostream& stream); @@ -234,6 +236,7 @@ protected: void writeStrings(std::ostream& stream); void writeDeclarations(std::ostream& stream); void writeEventSources(std::ostream& stream); + void writeTransition(std::ostream& stream, const GlobalTransition* transition, int indent = 0); void writeExecutableContent(std::ostream& stream, const Arabica::DOM::Node<std::string>& node, int indent = 0); void writeInlineComment(std::ostream& stream, const Arabica::DOM::Node<std::string>& node); void writeFSM(std::ostream& stream); @@ -241,32 +244,36 @@ protected: void writeMain(std::ostream& stream); void writeIfBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& condChain, int indent = 0); - void writeDispatchingBlock(std::ostream& stream, const Arabica::XPath::NodeSet<std::string>& transChain, int indent = 0); + void writeDispatchingBlock(std::ostream& stream, std::list<GlobalTransition*>, int indent = 0); Arabica::XPath::NodeSet<std::string> getTransientContent(const Arabica::DOM::Element<std::string>& state, const std::string& source = ""); - Arabica::DOM::Node<std::string> getUltimateTarget(const Arabica::DOM::Element<std::string>& transition); + //Arabica::DOM::Node<std::string> getUltimateTarget(const Arabica::DOM::Element<std::string>& transition); static PromelaInlines getInlinePromela(const std::string&); static PromelaInlines getInlinePromela(const Arabica::XPath::NodeSet<std::string>& elements, bool recurse = false); static PromelaInlines getInlinePromela(const Arabica::DOM::Node<std::string>& elements); + static std::string declForRange(const std::string& identifier, long minValue, long maxValue, bool nativeOnly = false); + // std::string replaceStringsInExpression(const std::string& expr); std::string sanitizeCode(const std::string& code); - Arabica::XPath::NodeSet<std::string> _globalStates; - Arabica::DOM::Node<std::string> _startState; - std::map<std::string, Arabica::DOM::Element<std::string> > _states; - std::map<Arabica::DOM::Element<std::string>, int> _transitions; +// Arabica::XPath::NodeSet<std::string> _globalStates; +// Arabica::DOM::Node<std::string> _startState; +// std::map<std::string, Arabica::DOM::Element<std::string> > _states; +// std::map<Arabica::DOM::Element<std::string>, int> _transitions; - std::list<std::string> _varInitializers; + std::list<std::string> _varInitializers; // pending initializations for arrays PromelaCodeAnalyzer _analyzer; std::map<std::string, PromelaEventSource> _invokers; PromelaEventSource _globalEventSource; + + friend class PromelaEventSource; }; } -#endif /* end of include guard: FSMTOPROMELA_H_RP48RFDJ */ +#endif /* end of include guard: CHARTTOPROMELA_H_RP48RFDJ */ diff --git a/src/uscxml/transform/FlatStateIdentifier.h b/src/uscxml/transform/FlatStateIdentifier.h index 5cbd5f2..92e6e8a 100644 --- a/src/uscxml/transform/FlatStateIdentifier.h +++ b/src/uscxml/transform/FlatStateIdentifier.h @@ -88,6 +88,13 @@ public: return tmp.getStateId(); } + static std::string toStateId(const Arabica::XPath::NodeSet<std::string> activeStates, + const Arabica::XPath::NodeSet<std::string> alreadyEnteredStates = Arabica::XPath::NodeSet<std::string>(), + const std::map<std::string, Arabica::XPath::NodeSet<std::string> > historyStates = std::map<std::string, Arabica::XPath::NodeSet<std::string> >()) { + FlatStateIdentifier tmp(activeStates, alreadyEnteredStates, historyStates); + return tmp.getStateId(); + } + FlatStateIdentifier(const std::string& identifier) : stateId(identifier) { std::string parsedName; // parse unique state identifier diff --git a/src/uscxml/transform/Transformer.cpp b/src/uscxml/transform/Transformer.cpp new file mode 100644 index 0000000..fd4920a --- /dev/null +++ b/src/uscxml/transform/Transformer.cpp @@ -0,0 +1,20 @@ +/** + * @file + * @author 2012-2014 Stefan Radomski (stefan.radomski@cs.tu-darmstadt.de) + * @copyright Simplified BSD + * + * @cond + * This program is free software: you can redistribute it and/or modify + * it under the terms of the FreeBSD license as published by the FreeBSD + * project. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * You should have received a copy of the FreeBSD license along with this + * program. If not, see <http://www.opensource.org/licenses/bsd-license>. + * @endcond + */ + +#include "Transformer.h"
\ No newline at end of file diff --git a/src/uscxml/transform/Transformer.h b/src/uscxml/transform/Transformer.h new file mode 100644 index 0000000..8ea19d9 --- /dev/null +++ b/src/uscxml/transform/Transformer.h @@ -0,0 +1,79 @@ +/** + * @file + * @author 2012-2014 Stefan Radomski (stefan.radomski@cs.tu-darmstadt.de) + * @copyright Simplified BSD + * + * @cond + * This program is free software: you can redistribute it and/or modify + * it under the terms of the FreeBSD license as published by the FreeBSD + * project. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * You should have received a copy of the FreeBSD license along with this + * program. If not, see <http://www.opensource.org/licenses/bsd-license>. + * @endcond + */ + +#ifndef TRANSFORMER_H_32113356 +#define TRANSFORMER_H_32113356 + +#include "uscxml/interpreter/InterpreterRC.h" +#include <ostream> + +namespace uscxml { + +class USCXML_API TransformerImpl { +public: + TransformerImpl() {} + + virtual void writeTo(std::ostream& stream) = 0; + virtual operator Interpreter() { + throw std::runtime_error("Transformer cannot be interpreted as an Interpreter again"); + } + +}; + +class USCXML_API Transformer { +public: +// Transformer(const Interpreter& source) { _impl = new (source) } + + Transformer() : _impl() {} // the empty, invalid interpreter + Transformer(boost::shared_ptr<TransformerImpl> const impl) : _impl(impl) { } + Transformer(const Transformer& other) : _impl(other._impl) { } + virtual ~Transformer() {}; + + operator bool() const { + return (_impl); + } + bool operator< (const Transformer& other) const { + return _impl < other._impl; + } + bool operator==(const Transformer& other) const { + return _impl == other._impl; + } + bool operator!=(const Transformer& other) const { + return _impl != other._impl; + } + Transformer& operator= (const Transformer& other) { + _impl = other._impl; + return *this; + } + + virtual void writeTo(std::ostream& stream) { + _impl->writeTo(stream); + } + operator Interpreter() { + return _impl->operator Interpreter(); + } + +protected: + boost::shared_ptr<TransformerImpl> _impl; + +}; + +} + +#endif /* end of include guard: TRANSFORMER_H_32113356 */ |