diff options
Diffstat (limited to 'src/uscxml')
-rw-r--r-- | src/uscxml/interpreter/InterpreterDraft6.cpp | 2 | ||||
-rw-r--r-- | src/uscxml/transform/ChartToFSM.cpp | 177 | ||||
-rw-r--r-- | src/uscxml/transform/ChartToFSM.h | 18 | ||||
-rw-r--r-- | src/uscxml/transform/FlatStateIdentifier.h | 18 |
4 files changed, 157 insertions, 58 deletions
diff --git a/src/uscxml/interpreter/InterpreterDraft6.cpp b/src/uscxml/interpreter/InterpreterDraft6.cpp index 92333f1..aedf516 100644 --- a/src/uscxml/interpreter/InterpreterDraft6.cpp +++ b/src/uscxml/interpreter/InterpreterDraft6.cpp @@ -916,7 +916,6 @@ void InterpreterDraft6::enterStates(const Arabica::XPath::NodeSet<std::string>& _configuration.push_back(stateElem); _statesToInvoke.push_back(stateElem); -// if (_binding == LATE && stateElem.getAttribute("isFirstEntry").size() > 0) { if (_binding == LATE && !isMember(stateElem, _alreadyEntered)) { NodeSet<std::string> dataModelElems = filterChildElements(_nsInfo.xmlNSPrefix + "datamodel", stateElem); if(dataModelElems.size() > 0 && _dataModel) { @@ -927,7 +926,6 @@ void InterpreterDraft6::enterStates(const Arabica::XPath::NodeSet<std::string>& } } _alreadyEntered.push_back(stateElem); -// stateElem.setAttribute("isFirstEntry", ""); } // execute onentry executable content NodeSet<std::string> onEntryElems = filterChildElements(_nsInfo.xmlNSPrefix + "onEntry", stateElem); diff --git a/src/uscxml/transform/ChartToFSM.cpp b/src/uscxml/transform/ChartToFSM.cpp index 0aac811..0a04771 100644 --- a/src/uscxml/transform/ChartToFSM.cpp +++ b/src/uscxml/transform/ChartToFSM.cpp @@ -131,7 +131,8 @@ FlatteningInterpreter::FlatteningInterpreter(const Document<std::string>& doc) { _perfTotal = 0; _lastTimeStamp = tthread::chrono::system_clock::now(); _currGlobalTransition = NULL; - + _lastTransientStateId = 0; + // just copy given doc into _document an create _flatDoc for the FSM DOMImplementation<std::string> domFactory = Arabica::SimpleDOM::DOMImplementation<std::string>::getDOMImplementation(); _document = domFactory.createDocument(doc.getNamespaceURI(), "", 0); @@ -227,10 +228,11 @@ InterpreterState FlatteningInterpreter::interpret() { } labelTransitions(); weightTransitions(); - + indexTransitions(_scxml); + // std::cout << _scxml << std::endl; - GlobalTransition* globalTransition = new GlobalTransition(initialTransitions, _dataModel); + GlobalTransition* globalTransition = new GlobalTransition(initialTransitions, _dataModel, this); _start->outgoing[globalTransition->transitionId] = globalTransition; globalTransition->source = _start->stateId; _currGlobalTransition = globalTransition; @@ -401,44 +403,38 @@ static bool filterChildEnabled(const NodeSet<std::string>& transitions) { return true; } -static std::list<GlobalTransition*> sortTransitions(std::list<GlobalTransition*> list) { - bool stable = false; - while(!stable) { - for (std::list<GlobalTransition*>::iterator outerIter = list.begin(); - outerIter != list.end(); - outerIter++) { - for (std::list<GlobalTransition*>::iterator innerIter = outerIter; - innerIter != list.end(); - innerIter++) { - GlobalTransition* t1 = *outerIter; - GlobalTransition* t2 = *innerIter; - - if (isSuperset(t1, t2)) { -// std::cout << "swapping " << t1->transitionId << " / " << t2->transitionId << std::endl; - std::swap(*innerIter, *outerIter); - goto NEXT_ITER; - } - for (int i = t1->firstElemPerLevel.size() - 1; i >= 0 ; i--) { - if (t1->firstElemPerLevel[i] == std::numeric_limits<int32_t>::max() || t2->firstElemPerLevel[i] == std::numeric_limits<int32_t>::max()) - break; - if (t1->firstElemPerLevel[i] > t2->firstElemPerLevel[i]) { -// std::cout << "swapping at " << i << " " << t1->transitionId << " / " << t2->transitionId << std::endl; - std::swap(*innerIter, *outerIter); - goto NEXT_ITER; - } else { - break; - } - } - } - } - stable = true; -NEXT_ITER: - ; + +void FlatteningInterpreter::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--) { + indexedTransitions.push_back(Element<std::string>(levelTransitions[i])); + } + + Arabica::XPath::NodeSet<std::string> nextLevel = filterChildType(Arabica::DOM::Node_base::ELEMENT_NODE, root); + for (int i = nextLevel.size() - 1; i >= 0; i--) { + Element<std::string> stateElem = Element<std::string>(nextLevel[i]); + if (isState(stateElem)) + indexTransitions(stateElem); } - return list; -} +} +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 Element<std::string>& refTrans = *transIter; + + if (InterpreterImpl::isMember(refTrans, transitions) && !InterpreterImpl::isMember(refTrans, other.transitions)) { + return true; + } + if (!InterpreterImpl::isMember(refTrans, transitions) && InterpreterImpl::isMember(refTrans, other.transitions)) { + return false; + } + } + return true; // actually, they are equal +} + void FlatteningInterpreter::explode() { @@ -590,7 +586,7 @@ void FlatteningInterpreter::explode() { assert(transitions.size() > 0); // create a GlobalTransition object from the set - GlobalTransition* transition = new GlobalTransition(transitions, _dataModel); + GlobalTransition* transition = new GlobalTransition(transitions, _dataModel, this); if (!transition->isValid) { // this set of transitions can not be enabled together delete transition; @@ -747,17 +743,72 @@ void FlatteningInterpreter::createDocument() { 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::cout << index++ << ": " << refTrans << std::endl; + } + std::cout << std::endl; + for (std::vector<std::pair<std::string,GlobalState*> >::iterator confIter = sortedStates.begin(); confIter != sortedStates.end(); confIter++) { - Node<std::string> state = globalStateToNode(confIter->second); - _scxml.appendChild(state); + appendGlobalStateNode(confIter->second); } // exit(0); } -Node<std::string> FlatteningInterpreter::globalStateToNode(GlobalState* globalState) { + +template <typename T> bool PtrComp(const T * const & a, const T * const & b) +{ + return *a < *b; +} + + +bool isRedundantSubset (GlobalTransition* first, GlobalTransition* second) { + if (isSuperset(second, first)) { +// std::cout << second->transitions.size() << " / " << first->transitions.size() << std::endl; + 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 +} + +std::list<GlobalTransition*> filterRedundantSubset(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 (isRedundantSubset(t1, t2)) { + list.erase(outerIter++); + } else if (isRedundantSubset(t2, t1)) { + list.erase(innerIter++); + } + + } + } + + return list; +} + +void FlatteningInterpreter::appendGlobalStateNode(GlobalState* globalState) { Element<std::string> state = _flatDoc.createElementNS(_nsInfo.nsURL, "state"); _nsInfo.setPrefix(state); @@ -774,9 +825,15 @@ Node<std::string> FlatteningInterpreter::globalStateToNode(GlobalState* globalSt transitionList.push_back(outIter->second); } - transitionList = sortTransitions(transitionList); +// transitionList = sortTransitions(transitionList); + transitionList.sort(PtrComp<GlobalTransition>); + transitionList.unique(isRedundantSubset); + // unique is not quite like what we need, but it was a start + transitionList = filterRedundantSubset(transitionList); + + // apend here, for transient state chains to trail the state + _scxml.appendChild(state); -// std::cout << "/////////////////" << std::endl; size_t index = 0; for (std::list<GlobalTransition*>::iterator outIter = transitionList.begin(); outIter != transitionList.end(); @@ -785,9 +842,6 @@ Node<std::string> FlatteningInterpreter::globalStateToNode(GlobalState* globalSt state.appendChild(globalTransitionToNode(*outIter)); index++; } -// std::cout << "/////////////////" << std::endl; - - return state; } /** @@ -799,6 +853,26 @@ Node<std::string> FlatteningInterpreter::globalTransitionToNode(GlobalTransition // transition.setAttribute("ref", globalTransition->index); +#if 1 + std::string members; + int index = 0; + std::string seperator; + for (std::list<Element<std::string> >::reverse_iterator transIter = indexedTransitions.rbegin(); transIter != indexedTransitions.rend(); transIter++) { + const Element<std::string>& refTrans = *transIter; + if (isMember(refTrans, globalTransition->transitions)) { + members += seperator + toStr(index); + } else { + members += seperator; + for (int i = 0; i < toStr(index).size(); i++) { + members += " "; + } + } + seperator = " "; + index++; + } + transition.setAttribute("members", members); +#endif + if (!globalTransition->isEventless) { transition.setAttribute("event", globalTransition->eventDesc); } @@ -931,7 +1005,8 @@ Node<std::string> FlatteningInterpreter::globalTransitionToNode(GlobalTransition if (transientStateChain.size() > 0) { for (int i = 0; i < transientStateChain.size(); i++) { Element<std::string> transientStateElem = Element<std::string>(transientStateChain[i]); - transientStateElem.setAttribute("id", "transient-" + globalTransition->transitionId + "-" + globalTransition->source + "-" + toStr(i)); +// transientStateElem.setAttribute("id", "transient-" + globalTransition->transitionId + "-" + globalTransition->source + "-" + toStr(i)); + transientStateElem.setAttribute("id", globalTransition->destination + "-via-" + toStr(_lastTransientStateId++)); Element<std::string> exitTransition = _flatDoc.createElementNS(_nsInfo.nsURL, "transition"); _nsInfo.setPrefix(exitTransition); @@ -939,7 +1014,8 @@ Node<std::string> FlatteningInterpreter::globalTransitionToNode(GlobalTransition if (i == transientStateChain.size() - 1) { exitTransition.setAttribute("target", globalTransition->destination); } else { - exitTransition.setAttribute("target", "transient-" + globalTransition->transitionId + "-" + globalTransition->source + "-" + toStr(i + 1)); +// exitTransition.setAttribute("target", "transient-" + globalTransition->transitionId + "-" + globalTransition->source + "-" + toStr(i + 1)); + exitTransition.setAttribute("target", globalTransition->destination + "-via-" + toStr(_lastTransientStateId)); } transientStateElem.appendChild(exitTransition); @@ -1051,7 +1127,8 @@ GlobalState::GlobalState(const Arabica::XPath::NodeSet<std::string>& activeState stateId = flatStateId.getStateId(); } -GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitionSet, DataModel dataModel) { +GlobalTransition::GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitionSet, DataModel dataModel, FlatteningInterpreter* flattener) { + interpreter = flattener; transitions = transitionSet; isValid = true; isEventless = true; diff --git a/src/uscxml/transform/ChartToFSM.h b/src/uscxml/transform/ChartToFSM.h index 64b3640..923304c 100644 --- a/src/uscxml/transform/ChartToFSM.h +++ b/src/uscxml/transform/ChartToFSM.h @@ -31,7 +31,8 @@ namespace uscxml { class GlobalState; class GlobalTransition; - +class FlatteningInterpreter; + class USCXML_API GlobalState { public: @@ -69,7 +70,7 @@ public: Arabica::DOM::Element<std::string> uninvoke; }; - GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitions, DataModel dataModel); + GlobalTransition(const Arabica::XPath::NodeSet<std::string>& transitions, DataModel dataModel, FlatteningInterpreter* flattener); bool isValid; // constructor will determine, calling code will delete if not bool isEventless; // whether or not all our transitions are eventless @@ -100,6 +101,10 @@ public: std::string destination; std::string index; + FlatteningInterpreter* interpreter; + + bool operator< (const GlobalTransition& other) const; + protected: std::list<std::string> getCommonEvents(const Arabica::XPath::NodeSet<std::string>& transitions); }; @@ -112,6 +117,8 @@ public: Arabica::DOM::Document<std::string> getDocument() const; // overwrite to return flat FSM InterpreterState interpret(); + 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); @@ -136,7 +143,10 @@ protected: void weightTransitions(); void createDocument(); - Arabica::DOM::Node<std::string> globalStateToNode(GlobalState* globalState); + 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; @@ -149,6 +159,8 @@ protected: int maxDepth; int maxOrder; + size_t _lastTransientStateId; + Arabica::DOM::Document<std::string> _flatDoc; std::map<std::string, GlobalState*> _globalConf; }; diff --git a/src/uscxml/transform/FlatStateIdentifier.h b/src/uscxml/transform/FlatStateIdentifier.h index 61d0f1b..08451c2 100644 --- a/src/uscxml/transform/FlatStateIdentifier.h +++ b/src/uscxml/transform/FlatStateIdentifier.h @@ -21,6 +21,7 @@ #define FLATSTATEIDENTIFIER_H_E9534AF9 #include "uscxml/Common.h" +#include "uscxml/Convenience.h" #include "uscxml/DOMUtils.h" #include <XPath/XPath.hpp> @@ -44,7 +45,18 @@ public: } for (int i = 0; i < alreadyEnteredStates.size(); i++) { - visited.push_back(ATTR_CAST(alreadyEnteredStates[i], "id")); + const Arabica::DOM::NodeList<std::string>& children = alreadyEnteredStates[i].getChildNodes(); + bool isRelevant = false; + for (int j = 0; j < children.getLength(); j++) { + if (children.item(j).getNodeType() != Arabica::DOM::Node_base::ELEMENT_NODE) + continue; + if (iequals(LOCALNAME_CAST(children.item(j)), "data") || iequals(LOCALNAME_CAST(children.item(j)), "datamodel")) { + isRelevant = true; + break; + } + } + if (isRelevant) + visited.push_back(ATTR_CAST(alreadyEnteredStates[i], "id")); } std::map<std::string, Arabica::XPath::NodeSet<std::string> >::const_iterator histIter; @@ -79,7 +91,7 @@ public: active.push_back(state); } } - } else if (boost::starts_with(section, "entered:{")) { + } else if (boost::starts_with(section, "visited:{")) { // entered:{s0,s1,s2} std::stringstream stateSS(section.substr(9, section.size() - 10)); std::string state; @@ -152,7 +164,7 @@ protected: if (visited.size() > 0) { seperator = ""; - stateIdSS << ";entered:{"; + stateIdSS << ";visited:{"; for (std::list<std::string>::const_iterator visitIter = visited.begin(); visitIter != visited.end(); visitIter++) { stateIdSS << seperator << *visitIter; seperator = ","; |