From 99457229adecc63246e900b01aee360039e7183d Mon Sep 17 00:00:00 2001 From: Stefan Radomski Date: Wed, 20 Jan 2016 17:19:38 +0100 Subject: Added transition-less histories as an issue and completed C transformation --- src/uscxml/debug/InterpreterIssue.cpp | 4 +- src/uscxml/transform/ChartToC.cpp | 186 +++++++++++++--- src/uscxml/transform/ChartToC.h | 1 + test/src/test-c-machine.machine.c | 238 ++++++++++----------- test/uscxml/automated/ecma/deep-histories2.scxml | 31 +++ .../automated/ecma/uncompleted-history.scxml | 11 + 6 files changed, 312 insertions(+), 159 deletions(-) create mode 100644 test/uscxml/automated/ecma/deep-histories2.scxml create mode 100644 test/uscxml/automated/ecma/uncompleted-history.scxml diff --git a/src/uscxml/debug/InterpreterIssue.cpp b/src/uscxml/debug/InterpreterIssue.cpp index 7d55f3a..5fb3965 100644 --- a/src/uscxml/debug/InterpreterIssue.cpp +++ b/src/uscxml/debug/InterpreterIssue.cpp @@ -302,7 +302,9 @@ std::list InterpreterIssue::forInterpreter(InterpreterImpl* in NodeSet transitions = InterpreterImpl::filterChildElements(_nsInfo.xmlNSPrefix + "transition", state, false); if (transitions.size() > 1) { issues.push_back(InterpreterIssue("History pseudo-state with id '" + stateId + "' has multiple transitions", state, InterpreterIssue::USCXML_ISSUE_FATAL)); - } else if (transitions.size() == 1) { + } else if (transitions.size() == 0) { + issues.push_back(InterpreterIssue("History pseudo-state with id '" + stateId + "' has no default transition", state, InterpreterIssue::USCXML_ISSUE_FATAL)); + } else { Element transition = Element(transitions[0]); if (HAS_ATTR(transition, "cond")) { issues.push_back(InterpreterIssue("Transition in history pseudo-state '" + stateId + "' must not have a condition", transition, InterpreterIssue::USCXML_ISSUE_FATAL)); diff --git a/src/uscxml/transform/ChartToC.cpp b/src/uscxml/transform/ChartToC.cpp index ec5c017..477b1c7 100644 --- a/src/uscxml/transform/ChartToC.cpp +++ b/src/uscxml/transform/ChartToC.cpp @@ -46,31 +46,123 @@ ChartToC::ChartToC(const Interpreter& other) : TransformerImpl() { cloneFrom(other.getImpl()); } +void ChartToC::setHistoryResponsibility(Arabica::DOM::Node& node) { + std::set elements; + elements.insert(_nsInfo.xmlNSPrefix + "history"); + Arabica::XPath::NodeSet histories = inPostFixOrder(elements, _scxml); + + NodeSet covered; + NodeSet perParentcovered; + Node parent; + + for (size_t i = 0; i < histories.size(); i++) { + Element history(histories[i]); + NodeSet completion; + + if (parent != history.getParentNode()) { + covered.push_back(perParentcovered); + perParentcovered = NodeSet(); + parent = history.getParentNode(); + } + + bool deep = (HAS_ATTR(history, "type") && iequals(ATTR(history, "type"), "deep")); + for (size_t j = 0; j < _states.size(); j++) { + if (_states[j] == history) + continue; + + if (isDescendant(_states[j], history.getParentNode()) && isHistory(Element(_states[j]))) { + history.setAttribute("hasNestedHistory", "true"); + } + + if (isMember(_states[j], covered)) + continue; + + if (deep) { + if (isDescendant(_states[j], history.getParentNode()) && !isHistory(Element(_states[j]))) { + completion.push_back(_states[j]); + } + } else { + if (_states[j].getParentNode() == history.getParentNode() && !isHistory(Element(_states[j]))) { + completion.push_back(_states[j]); + } + } + } + perParentcovered.push_back(completion); + + std::string respBools; + std::string respBoolsIdx; + for (size_t j = 0; j < _states.size(); j++) { + if (isMember(_states[j], completion)) { + respBools += "1"; + respBoolsIdx += " " + toStr(j); + } else { + respBools += "0"; + } + } + history.setAttribute("respBools", respBools); + history.setAttribute("respBoolsIdx", respBoolsIdx); + } +} + + void ChartToC::resortStates(Arabica::DOM::Node& node) { if (node.getNodeType() != Node_base::ELEMENT_NODE) return; - // move history states to top + /** + initials + deep histories + shallow histories + everything else + */ + Element element(node); + + // shallow history states to top Node child = element.getFirstChild(); while(child) { resortStates(child); - if (child.getNodeType() == Node_base::ELEMENT_NODE && TAGNAME_CAST(child) == _nsInfo.xmlNSPrefix + "history") { + if (child.getNodeType() == Node_base::ELEMENT_NODE && + TAGNAME_CAST(child) == _nsInfo.xmlNSPrefix + "history" && + (!HAS_ATTR(element, "type") || iequals(ATTR(element, "type"), "shallow"))) { + Node tmp = child.getNextSibling(); + if (child != element.getFirstChild()) { + element.insertBefore(child, element.getFirstChild()); + } + child = tmp; + } else { + child = child.getNextSibling(); + } + } + + // deep history states to top + child = element.getFirstChild(); + while(child) { + resortStates(child); + if (child.getNodeType() == Node_base::ELEMENT_NODE && + TAGNAME_CAST(child) == _nsInfo.xmlNSPrefix + "history" && + HAS_ATTR(element, "type") && + iequals(ATTR(element, "type"), "deep")) { + Node tmp = child.getNextSibling(); - element.insertBefore(child, element.getFirstChild()); + if (child != element.getFirstChild()) { + element.insertBefore(child, element.getFirstChild()); + } child = tmp; } else { child = child.getNextSibling(); } } - // move initial states on top of histories even + // initial states on top of histories even child = element.getFirstChild(); while(child) { resortStates(child); if (child.getNodeType() == Node_base::ELEMENT_NODE && TAGNAME_CAST(child) == _nsInfo.xmlNSPrefix + "initial") { Node tmp = child.getNextSibling(); - element.insertBefore(child, element.getFirstChild()); + if (child != element.getFirstChild()) { + element.insertBefore(child, element.getFirstChild()); + } child = tmp; } else { child = child.getNextSibling(); @@ -84,7 +176,7 @@ void ChartToC::writeTo(std::ostream& stream) { _name = (HAS_ATTR(_scxml, "name") ? ATTR(_scxml, "name") : ""); // make sure initial and history elements always precede propoer states - + resortStates(_scxml); std::set elements; elements.insert(_nsInfo.xmlNSPrefix + "scxml"); @@ -154,6 +246,9 @@ void ChartToC::writeTo(std::ostream& stream) { _transDataType = "uint64_t"; } + // set the responsibility of history elements + setHistoryResponsibility(_scxml); + writeIncludes(stream); writeMacros(stream); writeTypes(stream); @@ -220,7 +315,9 @@ void ChartToC::writeMacros(std::ostream& stream) { stream << "#define SCXML_STATE_HISTORY_DEEP 0x05" << std::endl; stream << "#define SCXML_STATE_HISTORY_SHALLOW 0x06" << std::endl; stream << "#define SCXML_STATE_INITIAL 0x07" << std::endl; - + stream << "#define SCXML_STATE_HAS_HISTORY 0x80 // highest bit" << std::endl; + stream << "#define SCXML_STATE_MASK(t) (t & 0x7F) // mask highest bit" << std::endl; + stream << "" << std::endl; stream << "#define SCXML_CTX_PRISTINE 0x00" << std::endl; stream << "#define SCXML_CTX_SPONTANEOUS 0x01" << std::endl; @@ -1001,11 +1098,15 @@ void ChartToC::writeStates(std::ostream& stream) { stream << "," << std::endl; // children + bool hasHistoryChild = false; std::string childBools; std::string childBoolsIdx; for (size_t j = 0; j < _states.size(); j++) { if (_states[j].getParentNode() == state) { - childBools += "1"; + if (isHistory(Element(_states[j]))) { + hasHistoryChild = true; + } + childBools += "1"; childBoolsIdx += " " + toStr(j); } else { childBools += "0"; @@ -1017,20 +1118,16 @@ void ChartToC::writeStates(std::ostream& stream) { stream << " }," << std::endl; // default completion + std::string descBools; + std::string descBoolsIdx; + NodeSet completion; if (isHistory(state)) { - bool deep = (HAS_ATTR(state, "type") && iequals(ATTR(state, "type"), "deep")); - for (size_t j = 0; j < _states.size(); j++) { - if (deep) { - if (isDescendant(_states[j], state.getParentNode()) && !isHistory(Element(_states[j]))) { - completion.push_back(_states[j]); - } - } else { - if (_states[j].getParentNode() == state.getParentNode() && !isHistory(Element(_states[j]))) { - completion.push_back(_states[j]); - } - } - } + // we already precalculated everything + descBools = ATTR(state, "respBools"); + descBoolsIdx = ATTR(state, "respBoolsIdx"); + hasHistoryChild = HAS_ATTR(state, "hasNestedHistory"); + goto WRITE_COMPLETION; } if (isParallel(state)) { completion = getChildStates(state); @@ -1056,8 +1153,6 @@ void ChartToC::writeStates(std::ostream& stream) { } } - std::string descBools; - std::string descBoolsIdx; for (size_t j = 0; j < _states.size(); j++) { if (isMember(_states[j], completion)) { descBools += "1"; @@ -1066,6 +1161,8 @@ void ChartToC::writeStates(std::ostream& stream) { descBools += "0"; } } + WRITE_COMPLETION: + stream << " /* completion */ { "; writeCharArrayInitList(stream, descBools); stream << " /* " << descBools << "," << descBoolsIdx << " */"; @@ -1112,6 +1209,10 @@ void ChartToC::writeStates(std::ostream& stream) { } else { // stream << "SCXML_STATE_COMPOUND"; } + if (hasHistoryChild) { + stream << " | SCXML_STATE_HAS_HISTORY"; + } + stream << "," << std::endl; stream << " }" << (i + 1 < _states.size() ? ",": "") << std::endl; @@ -1456,7 +1557,8 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << "// REMEMBER_HISTORY:" << std::endl; stream << " for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) {" << std::endl; - stream << " if unlikely(scxml_states[i].type == SCXML_STATE_HISTORY_SHALLOW || scxml_states[i].type == SCXML_STATE_HISTORY_DEEP) {" << std::endl; + stream << " if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_SHALLOW ||" << std::endl; + stream << " SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_DEEP) {" << std::endl; stream << " // a history state whose parent is about to be exited" << std::endl; stream << " if unlikely(IS_SET(scxml_states[i].parent, exit_set)) {" << std::endl; stream << " char history[" << _stateCharArraySize << "] = " << _stateCharArrayInit << ";" << std::endl; @@ -1490,7 +1592,7 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " // iterate for descendants" << std::endl; stream << " for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) {" << std::endl; stream << " if (IS_SET(i, entry_set)) {" << std::endl; - stream << " switch (scxml_states[i].type) {" << std::endl; + stream << " switch (SCXML_STATE_MASK(scxml_states[i].type)) {" << std::endl; stream << " case SCXML_STATE_PARALLEL: {" << std::endl; stream << " bit_or(entry_set, scxml_states[i].completion, " << _stateCharArraySize << ");" << std::endl; stream << " break;" << std::endl; @@ -1507,12 +1609,30 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " SET_BIT(j, trans_set);" << std::endl; stream << " break;" << std::endl; stream << " }" << std::endl; + stream << " // Note: SCXML mandates every history to have a transition!" << std::endl; stream << " }" << std::endl; - stream << " // TODO: enter parents default completion here" << std::endl; stream << " } else {" << std::endl; stream << " bit_copy(history_targets, scxml_states[i].completion, " << _stateCharArraySize << ");" << std::endl; stream << " bit_and(history_targets, ctx->history, " << _stateCharArraySize << ");" << std::endl; stream << " bit_or(entry_set, history_targets, " << _stateCharArraySize << ");" << std::endl; + stream << " if (scxml_states[i].type == (SCXML_STATE_HAS_HISTORY | SCXML_STATE_HISTORY_DEEP)) {" << std::endl; + stream << " // a deep history state with nested histories -> more completion" << std::endl; + stream << " for (size_t j = i + 1; j < SCXML_NUMBER_STATES; j++) {" << std::endl; + stream << " if (IS_SET(j, scxml_states[i].completion) &&" << std::endl; + stream << " IS_SET(j, entry_set) &&" << std::endl; + stream << " (scxml_states[j].type & SCXML_STATE_HAS_HISTORY)) {" << std::endl; + stream << " for (size_t k = j + 1; k < SCXML_NUMBER_STATES; k++) {" << std::endl; + stream << " // add nested history to entry_set" << std::endl; + stream << " if ((scxml_states[k].type == SCXML_STATE_HISTORY_DEEP ||" << std::endl; + stream << " scxml_states[k].type == SCXML_STATE_HISTORY_SHALLOW) &&" << std::endl; + stream << " IS_SET(k, scxml_states[j].children)) {" << std::endl; + stream << " // a nested history state" << std::endl; + stream << " SET_BIT(k, entry_set);" << std::endl; + stream << " }" << std::endl; + stream << " }" << std::endl; + stream << " }" << std::endl; + stream << " }" << std::endl; + stream << " }" << std::endl; stream << " }" << std::endl; stream << " break;" << std::endl; stream << " }" << std::endl; @@ -1522,7 +1642,7 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " SET_BIT(j, trans_set);" << std::endl; stream << " CLEARBIT(i, entry_set);" << std::endl; stream << " bit_or(entry_set, scxml_transitions[j].target, " << _stateCharArraySize << ");" << std::endl; - stream << " for (size_t k = 0; k < SCXML_NUMBER_STATES; k++) {" << std::endl; + stream << " for (size_t k = i + 1; k < SCXML_NUMBER_STATES; k++) {" << std::endl; stream << " if (IS_SET(k, scxml_transitions[j].target)) {" << std::endl; stream << " bit_or(entry_set, scxml_states[k].ancestors, " << _stateCharArraySize << ");" << std::endl; stream << " }" << std::endl; @@ -1539,7 +1659,7 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " bit_or(entry_set, scxml_states[i].completion, " << _stateCharArraySize << ");" << std::endl; stream << " if (!bit_has_and(scxml_states[i].completion, scxml_states[i].children, " << _stateCharArraySize << ")) {" << std::endl; stream << " // deep completion" << std::endl; - stream << " for (size_t j = 0; j < SCXML_NUMBER_STATES; j++) {" << std::endl; + stream << " for (size_t j = i + 1; j < SCXML_NUMBER_STATES; j++) {" << std::endl; stream << " if (IS_SET(j, scxml_states[i].completion)) {" << std::endl; stream << " bit_or(entry_set, scxml_states[j].ancestors, " << _stateCharArraySize << ");" << std::endl; stream << " break; // completion of compound is single state" << std::endl; @@ -1598,9 +1718,9 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) {" << std::endl; stream << " if (IS_SET(i, entry_set) && !IS_SET(i, ctx->config)) {" << std::endl; stream << " // these are no proper states" << std::endl; - stream << " if unlikely(scxml_states[i].type == SCXML_STATE_HISTORY_DEEP ||" << std::endl; - stream << " scxml_states[i].type == SCXML_STATE_HISTORY_SHALLOW ||" << std::endl; - stream << " scxml_states[i].type == SCXML_STATE_INITIAL)" << std::endl; + stream << " if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_DEEP ||" << std::endl; + stream << " SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_SHALLOW ||" << std::endl; + stream << " SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_INITIAL)" << std::endl; stream << " continue;" << std::endl; stream << std::endl; @@ -1639,7 +1759,7 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << std::endl; stream << " // handle final states" << std::endl; - stream << " if unlikely(scxml_states[i].type == SCXML_STATE_FINAL) {" << std::endl; + stream << " if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_FINAL) {" << std::endl; stream << " if unlikely(scxml_states[i].ancestors[0] == 0x01) {" << std::endl; stream << " ctx->flags |= SCXML_CTX_TOP_LEVEL_FINAL;" << std::endl; stream << " } else {" << std::endl; @@ -1662,12 +1782,12 @@ void ChartToC::writeFSM(std::ostream& stream) { stream << " * 4. If a state remains, not all children of a parallel are final" << std::endl; stream << " */" << std::endl; stream << " for (size_t j = 0; j < SCXML_NUMBER_STATES; j++) {" << std::endl; - stream << " if unlikely(scxml_states[j].type == SCXML_STATE_PARALLEL) {" << std::endl; + stream << " if unlikely(SCXML_STATE_MASK(scxml_states[j].type) == SCXML_STATE_PARALLEL) {" << std::endl; stream << " char parallel_children[" << _stateCharArraySize << "] = " << _stateCharArrayInit << ";" << std::endl; stream << " size_t parallel = j;" << std::endl; stream << " for (size_t k = 0; k < SCXML_NUMBER_STATES; k++) {" << std::endl; stream << " if unlikely(IS_SET(parallel, scxml_states[k].ancestors) && IS_SET(k, ctx->config)) {" << std::endl; - stream << " if (scxml_states[k].type == SCXML_STATE_FINAL) {" << std::endl; + stream << " if (SCXML_STATE_MASK(scxml_states[k].type) == SCXML_STATE_FINAL) {" << std::endl; stream << " bit_and_not(parallel_children, scxml_states[k].ancestors, " << _stateCharArraySize << ");" << std::endl; stream << " } else {" << std::endl; stream << " SET_BIT(k, parallel_children);" << std::endl; diff --git a/src/uscxml/transform/ChartToC.h b/src/uscxml/transform/ChartToC.h index 7de6e00..74363dd 100644 --- a/src/uscxml/transform/ChartToC.h +++ b/src/uscxml/transform/ChartToC.h @@ -72,6 +72,7 @@ protected: Arabica::XPath::NodeSet computeExitSet(const Arabica::DOM::Element& transition); void resortStates(Arabica::DOM::Node& node); + void setHistoryResponsibility(Arabica::DOM::Node& node); Interpreter interpreter; diff --git a/test/src/test-c-machine.machine.c b/test/src/test-c-machine.machine.c index 30d687c..d42d577 100644 --- a/test/src/test-c-machine.machine.c +++ b/test/src/test-c-machine.machine.c @@ -25,8 +25,8 @@ #define SCXML_ERR_UNSUPPORTED 8 #define SCXML_MACHINE_NAME "" -#define SCXML_NUMBER_STATES 12 -#define SCXML_NUMBER_TRANSITIONS 7 +#define SCXML_NUMBER_STATES 10 +#define SCXML_NUMBER_TRANSITIONS 5 #define SCXML_TRANS_SPONTANEOUS 0x01 #define SCXML_TRANS_TARGETLESS 0x02 @@ -41,6 +41,8 @@ #define SCXML_STATE_HISTORY_DEEP 0x05 #define SCXML_STATE_HISTORY_SHALLOW 0x06 #define SCXML_STATE_INITIAL 0x07 +#define SCXML_STATE_HAS_HISTORY 0x80 // highest bit +#define SCXML_STATE_MASK(t) (t & 0x7F) // mask highest bit #define SCXML_CTX_PRISTINE 0x00 #define SCXML_CTX_SPONTANEOUS 0x01 @@ -211,7 +213,7 @@ static int global_script(const scxml_ctx* ctx, const scxml_state* state, const v return SCXML_ERR_OK; } -static int s0_0_1_on_entry_0(const scxml_ctx* ctx, const scxml_state* state, const void* event) { +static int s0_0_0_on_entry_0(const scxml_ctx* ctx, const scxml_state* state, const void* event) { int err = SCXML_ERR_OK; if likely(ctx->exec_content_assign != NULL) { if ((ctx->exec_content_assign(ctx, "Var1", "Var1 + 1")) != SCXML_ERR_OK) return err; @@ -221,21 +223,36 @@ static int s0_0_1_on_entry_0(const scxml_ctx* ctx, const scxml_state* state, con return SCXML_ERR_OK; } -static int s0_0_1_on_entry(const scxml_ctx* ctx, const scxml_state* state, const void* event) { - s0_0_1_on_entry_0(ctx, state, event); +static int s0_0_0_on_entry(const scxml_ctx* ctx, const scxml_state* state, const void* event) { + s0_0_0_on_entry_0(ctx, state, event); return SCXML_ERR_OK; } -static const scxml_state scxml_states[12] = { +static int s1_on_entry_0(const scxml_ctx* ctx, const scxml_state* state, const void* event) { + int err = SCXML_ERR_OK; + if likely(ctx->exec_content_assign != NULL) { + if ((ctx->exec_content_assign(ctx, "Var1", "Var1 + 1")) != SCXML_ERR_OK) return err; + } else { + return SCXML_ERR_MISSING_CALLBACK; + } + return SCXML_ERR_OK; +} + +static int s1_on_entry(const scxml_ctx* ctx, const scxml_state* state, const void* event) { + s1_on_entry_0(ctx, state, event); + return SCXML_ERR_OK; +} + +static const scxml_state scxml_states[10] = { { /* state number 0 */ /* name */ NULL, /* parent */ 0, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x02, 0x0f /* 010000001111, 1 8 9 10 11 */ }, - /* completion */ { 0x02, 0x00 /* 010000000000, 1 */ }, - /* ancestors */ { 0x00, 0x00 /* 000000000000, */ }, + /* children */ { 0x82, 0x03 /* 0100000111, 1 7 8 9 */ }, + /* completion */ { 0x02, 0x00 /* 0100000000, 1 */ }, + /* ancestors */ { 0x00, 0x00 /* 0000000000, */ }, /* data */ &scxml_elem_datas[0], /* type */ SCXML_STATE_COMPOUND, }, @@ -245,23 +262,23 @@ static const scxml_state scxml_states[12] = { /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x8c, 0x00 /* 001100010000, 2 3 7 */ }, - /* completion */ { 0x08, 0x00 /* 000100000000, 3 */ }, - /* ancestors */ { 0x01, 0x00 /* 100000000000, 0 */ }, + /* children */ { 0x0c, 0x00 /* 0011000000, 2 3 */ }, + /* completion */ { 0x08, 0x00 /* 0001000000, 3 */ }, + /* ancestors */ { 0x01, 0x00 /* 1000000000, 0 */ }, /* data */ NULL, - /* type */ SCXML_STATE_COMPOUND, + /* type */ SCXML_STATE_COMPOUND | SCXML_STATE_HAS_HISTORY, }, { /* state number 2 */ - /* name */ "s0.h0", + /* name */ "h0", /* parent */ 1, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0xe8, 0x00 /* 000101110000, 3 5 6 7 */ }, - /* ancestors */ { 0x03, 0x00 /* 110000000000, 0 1 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x08, 0x00 /* 0001000000, 3 */ }, + /* ancestors */ { 0x03, 0x00 /* 1100000000, 0 1 */ }, /* data */ NULL, - /* type */ SCXML_STATE_HISTORY_DEEP, + /* type */ SCXML_STATE_HISTORY_DEEP | SCXML_STATE_HAS_HISTORY, }, { /* state number 3 */ /* name */ "s0.0", @@ -269,194 +286,146 @@ static const scxml_state scxml_states[12] = { /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x70, 0x00 /* 000011100000, 4 5 6 */ }, - /* completion */ { 0x20, 0x00 /* 000001000000, 5 */ }, - /* ancestors */ { 0x03, 0x00 /* 110000000000, 0 1 */ }, + /* children */ { 0x70, 0x00 /* 0000111000, 4 5 6 */ }, + /* completion */ { 0x20, 0x00 /* 0000010000, 5 */ }, + /* ancestors */ { 0x03, 0x00 /* 1100000000, 0 1 */ }, /* data */ NULL, - /* type */ SCXML_STATE_COMPOUND, + /* type */ SCXML_STATE_COMPOUND | SCXML_STATE_HAS_HISTORY, }, { /* state number 4 */ - /* name */ "s0.0.h0", + /* name */ "h1", /* parent */ 3, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x60, 0x00 /* 000001100000, 5 6 */ }, - /* ancestors */ { 0x0b, 0x00 /* 110100000000, 0 1 3 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x60, 0x00 /* 0000011000, 5 6 */ }, + /* ancestors */ { 0x0b, 0x00 /* 1101000000, 0 1 3 */ }, /* data */ NULL, - /* type */ SCXML_STATE_HISTORY_SHALLOW, + /* type */ SCXML_STATE_HISTORY_DEEP, }, { /* state number 5 */ /* name */ "s0.0.0", /* parent */ 3, - /* onentry */ NULL, + /* onentry */ s0_0_0_on_entry, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x0b, 0x00 /* 110100000000, 0 1 3 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x00, 0x00 /* 0000000000, */ }, + /* ancestors */ { 0x0b, 0x00 /* 1101000000, 0 1 3 */ }, /* data */ NULL, /* type */ SCXML_STATE_ATOMIC, }, { /* state number 6 */ /* name */ "s0.0.1", /* parent */ 3, - /* onentry */ s0_0_1_on_entry, - /* onexit */ NULL, - /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x0b, 0x00 /* 110100000000, 0 1 3 */ }, - /* data */ NULL, - /* type */ SCXML_STATE_ATOMIC, - }, - { /* state number 7 */ - /* name */ "s0.1", - /* parent */ 1, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x03, 0x00 /* 110000000000, 0 1 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x00, 0x00 /* 0000000000, */ }, + /* ancestors */ { 0x0b, 0x00 /* 1101000000, 0 1 3 */ }, /* data */ NULL, /* type */ SCXML_STATE_ATOMIC, }, - { /* state number 8 */ + { /* state number 7 */ /* name */ "s1", /* parent */ 0, - /* onentry */ NULL, - /* onexit */ NULL, - /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x01, 0x00 /* 100000000000, 0 */ }, - /* data */ NULL, - /* type */ SCXML_STATE_ATOMIC, - }, - { /* state number 9 */ - /* name */ "s2", - /* parent */ 0, - /* onentry */ NULL, + /* onentry */ s1_on_entry, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x01, 0x00 /* 100000000000, 0 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x00, 0x00 /* 0000000000, */ }, + /* ancestors */ { 0x01, 0x00 /* 1000000000, 0 */ }, /* data */ NULL, /* type */ SCXML_STATE_ATOMIC, }, - { /* state number 10 */ + { /* state number 8 */ /* name */ "pass", /* parent */ 0, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x01, 0x00 /* 100000000000, 0 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x00, 0x00 /* 0000000000, */ }, + /* ancestors */ { 0x01, 0x00 /* 1000000000, 0 */ }, /* data */ NULL, /* type */ SCXML_STATE_FINAL, }, - { /* state number 11 */ + { /* state number 9 */ /* name */ "fail", /* parent */ 0, /* onentry */ NULL, /* onexit */ NULL, /* invoke */ NULL, - /* children */ { 0x00, 0x00 /* 000000000000, */ }, - /* completion */ { 0x00, 0x00 /* 000000000000, */ }, - /* ancestors */ { 0x01, 0x00 /* 100000000000, 0 */ }, + /* children */ { 0x00, 0x00 /* 0000000000, */ }, + /* completion */ { 0x00, 0x00 /* 0000000000, */ }, + /* ancestors */ { 0x01, 0x00 /* 1000000000, 0 */ }, /* data */ NULL, /* type */ SCXML_STATE_FINAL, } }; -static const scxml_transition scxml_transitions[7] = { +static const scxml_transition scxml_transitions[5] = { { /* transition number 0 with priority 0 target: s0.0.1 */ /* name */ 5, - /* target */ { 0x40, 0x00 /* 000000100000, 6 */ }, + /* target */ { 0x40, 0x00 /* 0000001000, 6 */ }, /* event */ NULL, - /* condition */ NULL, + /* condition */ "Var1 == 1", /* ontrans */ NULL, /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0x70, 0x00 /* 000011100000, 4 5 6 */ } + /* conflicts */ { 0x0f /* 11110, 0 1 2 3 */ }, + /* exit set */ { 0x70, 0x00 /* 0000111000, 4 5 6 */ } }, { /* transition number 1 with priority 1 target: s1 */ /* name */ 6, - /* target */ { 0x00, 0x01 /* 000000001000, 8 */ }, + /* target */ { 0x80, 0x00 /* 0000000100, 7 */ }, /* event */ NULL, /* condition */ "Var1 == 1", /* ontrans */ NULL, /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0xfe, 0x0f /* 011111111111, 1 2 3 4 5 6 7 8 9 10 11 */ } + /* conflicts */ { 0x0f /* 11110, 0 1 2 3 */ }, + /* exit set */ { 0xfe, 0x03 /* 0111111111, 1 2 3 4 5 6 7 8 9 */ } }, { /* transition number 2 with priority 2 - target: s2 - */ - /* name */ 7, - /* target */ { 0x00, 0x02 /* 000000000100, 9 */ }, - /* event */ NULL, - /* condition */ NULL, - /* ontrans */ NULL, - /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0xfe, 0x0f /* 011111111111, 1 2 3 4 5 6 7 8 9 10 11 */ } - }, - { /* transition number 3 with priority 3 target: pass */ /* name */ 1, - /* target */ { 0x00, 0x04 /* 000000000010, 10 */ }, + /* target */ { 0x00, 0x01 /* 0000000010, 8 */ }, /* event */ NULL, /* condition */ "Var1 == 2", /* ontrans */ NULL, /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0xfe, 0x0f /* 011111111111, 1 2 3 4 5 6 7 8 9 10 11 */ } + /* conflicts */ { 0x0f /* 11110, 0 1 2 3 */ }, + /* exit set */ { 0xfe, 0x03 /* 0111111111, 1 2 3 4 5 6 7 8 9 */ } }, - { /* transition number 4 with priority 4 + { /* transition number 3 with priority 3 target: fail */ /* name */ 1, - /* target */ { 0x00, 0x08 /* 000000000001, 11 */ }, - /* event */ NULL, - /* condition */ NULL, - /* ontrans */ NULL, - /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0xfe, 0x0f /* 011111111111, 1 2 3 4 5 6 7 8 9 10 11 */ } - }, - { /* transition number 5 with priority 5 - target: s0.1 - */ - /* name */ 8, - /* target */ { 0x80, 0x00 /* 000000010000, 7 */ }, + /* target */ { 0x00, 0x02 /* 0000000001, 9 */ }, /* event */ NULL, /* condition */ NULL, /* ontrans */ NULL, /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x3f /* 1111110, 0 1 2 3 4 5 */ }, - /* exit set */ { 0xfe, 0x0f /* 011111111111, 1 2 3 4 5 6 7 8 9 10 11 */ } + /* conflicts */ { 0x0f /* 11110, 0 1 2 3 */ }, + /* exit set */ { 0xfe, 0x03 /* 0111111111, 1 2 3 4 5 6 7 8 9 */ } }, - { /* transition number 6 with priority 6 - target: s0.0.h0 + { /* transition number 4 with priority 4 + target: h0 */ - /* name */ 9, - /* target */ { 0x10, 0x00 /* 000010000000, 4 */ }, + /* name */ 7, + /* target */ { 0x04, 0x00 /* 0010000000, 2 */ }, /* event */ NULL, - /* condition */ NULL, + /* condition */ "Var1 == 2", /* ontrans */ NULL, /* type */ SCXML_TRANS_SPONTANEOUS, - /* conflicts */ { 0x40 /* 0000001, 6 */ }, - /* exit set */ { 0x00, 0x00 /* 000000000000, */ } + /* conflicts */ { 0x10 /* 00001, 4 */ }, + /* exit set */ { 0x00, 0x00 /* 0000000000, */ } } }; @@ -616,7 +585,8 @@ SELECT_TRANSITIONS: // REMEMBER_HISTORY: for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) { - if unlikely(scxml_states[i].type == SCXML_STATE_HISTORY_SHALLOW || scxml_states[i].type == SCXML_STATE_HISTORY_DEEP) { + if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_SHALLOW || + SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_DEEP) { // a history state whose parent is about to be exited if unlikely(IS_SET(scxml_states[i].parent, exit_set)) { char history[2] = {0, 0}; @@ -648,7 +618,7 @@ ESTABLISH_ENTRY_SET: // iterate for descendants for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) { if (IS_SET(i, entry_set)) { - switch (scxml_states[i].type) { + switch (SCXML_STATE_MASK(scxml_states[i].type)) { case SCXML_STATE_PARALLEL: { bit_or(entry_set, scxml_states[i].completion, 2); break; @@ -671,6 +641,24 @@ ESTABLISH_ENTRY_SET: bit_copy(history_targets, scxml_states[i].completion, 2); bit_and(history_targets, ctx->history, 2); bit_or(entry_set, history_targets, 2); + if (scxml_states[i].type == (SCXML_STATE_HAS_HISTORY | SCXML_STATE_HISTORY_DEEP)) { + // a deep history state with nested histories -> more completion + for (size_t j = i + 1; j < SCXML_NUMBER_STATES; j++) { + if (IS_SET(j, scxml_states[i].completion) && + IS_SET(j, entry_set) && + (scxml_states[j].type & SCXML_STATE_HAS_HISTORY)) { + for (size_t k = j + 1; k < SCXML_NUMBER_STATES; k++) { + // add nested history to entry_set + if ((scxml_states[k].type == SCXML_STATE_HISTORY_DEEP || + scxml_states[k].type == SCXML_STATE_HISTORY_SHALLOW) && + IS_SET(k, scxml_states[j].children)) { + // a nested history state + SET_BIT(k, entry_set); + } + } + } + } + } } break; } @@ -751,9 +739,9 @@ ESTABLISH_ENTRY_SET: for (size_t i = 0; i < SCXML_NUMBER_STATES; i++) { if (IS_SET(i, entry_set) && !IS_SET(i, ctx->config)) { // these are no proper states - if unlikely(scxml_states[i].type == SCXML_STATE_HISTORY_DEEP || - scxml_states[i].type == SCXML_STATE_HISTORY_SHALLOW || - scxml_states[i].type == SCXML_STATE_INITIAL) + if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_DEEP || + SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_HISTORY_SHALLOW || + SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_INITIAL) continue; SET_BIT(i, ctx->config); @@ -787,7 +775,7 @@ ESTABLISH_ENTRY_SET: } // handle final states - if unlikely(scxml_states[i].type == SCXML_STATE_FINAL) { + if unlikely(SCXML_STATE_MASK(scxml_states[i].type) == SCXML_STATE_FINAL) { if unlikely(scxml_states[i].ancestors[0] == 0x01) { ctx->flags |= SCXML_CTX_TOP_LEVEL_FINAL; } else { @@ -809,12 +797,12 @@ ESTABLISH_ENTRY_SET: * 4. If a state remains, not all children of a parallel are final */ for (size_t j = 0; j < SCXML_NUMBER_STATES; j++) { - if unlikely(scxml_states[j].type == SCXML_STATE_PARALLEL) { + if unlikely(SCXML_STATE_MASK(scxml_states[j].type) == SCXML_STATE_PARALLEL) { char parallel_children[2] = {0, 0}; size_t parallel = j; for (size_t k = 0; k < SCXML_NUMBER_STATES; k++) { if unlikely(IS_SET(parallel, scxml_states[k].ancestors) && IS_SET(k, ctx->config)) { - if (scxml_states[k].type == SCXML_STATE_FINAL) { + if (SCXML_STATE_MASK(scxml_states[k].type) == SCXML_STATE_FINAL) { bit_and_not(parallel_children, scxml_states[k].ancestors, 2); } else { SET_BIT(k, parallel_children); diff --git a/test/uscxml/automated/ecma/deep-histories2.scxml b/test/uscxml/automated/ecma/deep-histories2.scxml new file mode 100644 index 0000000..e19f029 --- /dev/null +++ b/test/uscxml/automated/ecma/deep-histories2.scxml @@ -0,0 +1,31 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/test/uscxml/automated/ecma/uncompleted-history.scxml b/test/uscxml/automated/ecma/uncompleted-history.scxml new file mode 100644 index 0000000..f6c3c04 --- /dev/null +++ b/test/uscxml/automated/ecma/uncompleted-history.scxml @@ -0,0 +1,11 @@ + + + + + + + + + + + \ No newline at end of file -- cgit v0.12