Merge pull request #149 from tklab-tud/sradomski

remerge

6 files changed, 1446 insertions, 11 deletions

diff --git a/src/uscxml/debug/Benchmark.cpp b/src/uscxml/debug/Benchmark.cpp
new file mode 100644
index 0000000..0d2d789
--- /dev/null
+++ b/src/uscxml/debug/Benchmark.cpp
@@ -0,0 +1,55 @@
+/**
+ *  @file
+ *  @author     2017 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 "Benchmark.h"
+
+namespace uscxml {
+
+std::mutex Benchmark::benchMutex;
+std::map<std::string, size_t> Benchmark::benchmarks;
+    
+Benchmark::Benchmark(const std::string& domain) : domain(domain), started(std::chrono::system_clock::now()) {
+}
+
+Benchmark::~Benchmark() {
+    std::lock_guard<std::mutex> lock(benchMutex);
+    benchmarks[domain] += std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - started).count();
+}
+ 
+std::ostream& Benchmark::report(std::ostream& stream) {
+    std::lock_guard<std::mutex> lock(benchMutex);
+
+    size_t longestDomain = 0;
+    for (auto benchmark : benchmarks) {
+        longestDomain = (benchmark.first.size() > longestDomain ? benchmark.first.size() : longestDomain);
+    }
+    longestDomain += 8;
+    
+    for (auto benchmark : benchmarks) {
+        std::string padding;
+        for (int i = benchmark.first.size(); i < (longestDomain - log10(benchmark.second)); i++) {
+            padding += " ";
+        }
+        
+        stream << benchmark.first << ":" << padding << (double)benchmark.second / 1000.0 << "ms" << std::endl;
+    }
+    return stream;
+}
+
+}
diff --git a/src/uscxml/debug/Benchmark.h b/src/uscxml/debug/Benchmark.h
new file mode 100644
index 0000000..82ef583
--- /dev/null
+++ b/src/uscxml/debug/Benchmark.h
@@ -0,0 +1,48 @@
+/**
+ *  @file
+ *  @author     2017 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 BENCHMARK_H_532562
+#define BENCHMARK_H_532562
+
+#include <mutex>
+#include <map>
+#include <chrono>
+#include <string>
+#include <ostream>
+
+#include "uscxml/Common.h"              // for USCXML_API
+
+namespace uscxml {
+
+class USCXML_API Benchmark {
+public:
+	Benchmark(const std::string& domain);
+	~Benchmark();
+    
+    static std::ostream& report(std::ostream& stream);
+protected:
+    std::string domain;
+    std::chrono::time_point<std::chrono::system_clock> started;
+    
+	static std::map<std::string, size_t> benchmarks;
+	static std::mutex benchMutex;
+};
+
+}
+#endif /* end of include guard: BENCHMARK_H_532562 */
diff --git a/src/uscxml/interpreter/InterpreterImpl.cpp b/src/uscxml/interpreter/InterpreterImpl.cpp
index 18b27f8..4d98609 100644
--- a/src/uscxml/interpreter/InterpreterImpl.cpp
+++ b/src/uscxml/interpreter/InterpreterImpl.cpp
@@ -40,6 +40,7 @@
 #include <mutex>
 
 #include "uscxml/interpreter/FastMicroStep.h"
+#include "uscxml/interpreter/LargeMicroStep.h"
 #include "uscxml/interpreter/BasicContentExecutor.h"
 
 #include <xercesc/dom/DOM.hpp>
@@ -384,7 +385,7 @@ void InterpreterImpl::init() {
 	}
 
 	if (!_microStepper) {
-		_microStepper = MicroStep(std::shared_ptr<MicroStepImpl>(new FastMicroStep(this)));
+		_microStepper = MicroStep(std::shared_ptr<MicroStepImpl>(new LargeMicroStep(this)));
 	}
 	_microStepper.init(_scxml);
 
diff --git a/src/uscxml/interpreter/LargeMicroStep.cpp b/src/uscxml/interpreter/LargeMicroStep.cpp
new file mode 100644
index 0000000..50aa29c
--- /dev/null
+++ b/src/uscxml/interpreter/LargeMicroStep.cpp
@@ -0,0 +1,1143 @@
+/**
+ *  @file
+ *  @author     2017 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 "LargeMicroStep.h"
+#include "uscxml/debug/Benchmark.h"
+
+#include <algorithm>
+
+#define USCXML_CTX_PRISTINE           0x00
+#define USCXML_CTX_SPONTANEOUS        0x01
+#define USCXML_CTX_INITIALIZED        0x02
+#define USCXML_CTX_TOP_LEVEL_FINAL    0x04
+#define USCXML_CTX_TRANSITION_FOUND   0x08
+#define USCXML_CTX_FINISHED           0x10
+#define USCXML_CTX_STABLE             0x20 // only needed to signal onStable once
+
+#define USCXML_TRANS_SPONTANEOUS      0x01
+#define USCXML_TRANS_TARGETLESS       0x02
+#define USCXML_TRANS_INTERNAL         0x04
+#define USCXML_TRANS_HISTORY          0x08
+#define USCXML_TRANS_INITIAL          0x10
+
+#define USCXML_STATE_ATOMIC           0x01
+#define USCXML_STATE_PARALLEL         0x02
+#define USCXML_STATE_COMPOUND         0x03
+#define USCXML_STATE_FINAL            0x04
+#define USCXML_STATE_HISTORY_DEEP     0x05
+#define USCXML_STATE_HISTORY_SHALLOW  0x06
+#define USCXML_STATE_INITIAL          0x07
+#define USCXML_STATE_HAS_HISTORY      0x80  /* highest bit */
+#define USCXML_STATE_MASK(t)     (t & 0x7F) /* mask highest bit */
+
+#ifdef __GNUC__
+#  define likely(x)       (__builtin_expect(!!(x), 1))
+#  define unlikely(x)     (__builtin_expect(!!(x), 0))
+#else
+#  define likely(x)       (x)
+#  define unlikely(x)     (x)
+#endif
+
+#if 0
+#define BENCHMARK(domain) Benchmark bench(domain);
+#else
+#define BENCHMARK(domain)
+#endif
+
+#ifdef USCXML_VERBOSE
+#include <iostream>
+#endif
+namespace uscxml {
+
+using namespace XERCESC_NS;
+
+#ifdef USCXML_VERBOSE
+/**
+ * Print name of states contained in a (debugging).
+ */
+void LargeMicroStep::printStateNames(const boost::container::flat_set<LargeMicroStep::State*, LargeMicroStep::StateOrder>& a) {
+    const char* seperator = "";
+    for (auto state : a) {
+        std::cerr << seperator << (HAS_ATTR(state->element, X("id")) ? ATTR(state->element, X("id")) : "UNK");
+        seperator = ", ";
+    }
+    std::cerr << std::endl;
+}
+#endif
+
+LargeMicroStep::LargeMicroStep(MicroStepCallbacks* callbacks) : MicroStepImpl(callbacks) {
+}
+
+std::shared_ptr<MicroStepImpl> LargeMicroStep::create(MicroStepCallbacks* callbacks) {
+    return std::shared_ptr<MicroStepImpl>(new LargeMicroStep(callbacks));
+}
+
+LargeMicroStep::~LargeMicroStep() {
+    for (size_t i = 0; i < _states.size(); i++) {
+        delete(_states[i]);
+    }
+    for (size_t i = 0; i < _transitions.size(); i++) {
+        delete(_transitions[i]);
+    }
+}
+
+std::list<XERCESC_NS::DOMElement*> LargeMicroStep::getConfiguration() {
+    std::list<XERCESC_NS::DOMElement*> config;
+    for (auto state : _configuration) {
+        config.push_back(state->element);
+    }
+    return config;
+}
+
+void LargeMicroStep::markAsCancelled() {
+    _isCancelled = true;
+}
+
+void LargeMicroStep::reset() {
+    _isCancelled = false;
+    _flags = USCXML_CTX_PRISTINE;
+    _configuration.clear();
+    _history.clear();
+    _initializedData.clear();
+    _invocations.clear();
+    
+}
+
+bool LargeMicroStep::isInState(const std::string& stateId) {
+#ifdef USCXML_VERBOSE
+    printStateNames(_configuration);
+#endif
+    for (auto state : _configuration) {
+        if (HAS_ATTR(state->element, kXMLCharId) && ATTR(state->element, kXMLCharId) == stateId)
+            return true;
+    }
+    return false;
+}
+
+std::list<DOMElement*> LargeMicroStep::getHistoryCompletion(const DOMElement* history) {
+    std::set<std::string> elements;
+    elements.insert(_xmlPrefix.str() + "history");
+    std::list<DOMElement*> histories = DOMUtils::inPostFixOrder(elements, _scxml);
+    
+    std::list<DOMElement*> covered;
+    std::list<DOMElement*> perParentcovered;
+    const DOMNode* parent = NULL;
+    
+    std::list<DOMElement*> completion;
+    
+    if (parent != history->getParentNode()) {
+        covered.insert(covered.end(), perParentcovered.begin(), perParentcovered.end());
+        perParentcovered.clear();
+        parent = history->getParentNode();
+    }
+    
+    bool deep = (HAS_ATTR(history, kXMLCharType) && iequals(ATTR(history, kXMLCharType), "deep"));
+    
+    for (size_t j = 0; j < _states.size(); j++) {
+        if (_states[j]->element == history)
+            continue;
+        
+        if (DOMUtils::isDescendant((DOMNode*)_states[j]->element, history->getParentNode()) && isHistory(_states[j]->element)) {
+            ((DOMElement*)history)->setUserData(X("hasHistoryChild"), _states[j], NULL);
+        }
+        
+        if (DOMUtils::isMember(_states[j]->element, covered))
+            continue;
+        
+        if (deep) {
+            if (DOMUtils::isDescendant(_states[j]->element, history->getParentNode()) && !isHistory(_states[j]->element)) {
+                completion.push_back(_states[j]->element);
+            }
+        } else {
+            if (_states[j]->element->getParentNode() == history->getParentNode() && !isHistory(_states[j]->element)) {
+                completion.push_back(_states[j]->element);
+            }
+        }
+    }
+    
+    return completion;
+}
+
+std::list<DOMElement*> LargeMicroStep::getCompletion(const DOMElement* state) {
+    if (isHistory(state)) {
+        // we already did in setHistoryCompletion
+        return getHistoryCompletion(state);
+        
+    } else if (isParallel(state)) {
+        return getChildStates(state);
+        
+    } else if (HAS_ATTR(state, kXMLCharInitial)) {
+        return getStates(tokenize(ATTR(state, kXMLCharInitial)), _scxml);
+        
+    } else {
+        std::list<DOMElement*> completion;
+        
+        std::list<DOMElement*> initElems = DOMUtils::filterChildElements(_xmlPrefix.str() + "initial", state);
+        if(initElems.size() > 0) {
+            // initial element is first child
+            completion.push_back(initElems.front());
+        } else {
+            // first child state
+            for (auto childElem = state->getFirstElementChild(); childElem; childElem = childElem->getNextElementSibling()) {
+                if (isState(childElem)) {
+                    completion.push_back(childElem);
+                    break;
+                }
+            }
+        }
+        return completion;
+    }
+}
+
+void LargeMicroStep::init(XERCESC_NS::DOMElement* scxml) {
+    _scxml = scxml;
+    _binding = (HAS_ATTR(_scxml, kXMLCharBinding) && iequals(ATTR(_scxml, kXMLCharBinding), "late") ? LATE : EARLY);
+    _xmlPrefix = _scxml->getPrefix();
+    _xmlNS = _scxml->getNamespaceURI();
+    if (_xmlPrefix) {
+        _xmlPrefix = std::string(_xmlPrefix) + ":";
+    }
+
+    resortStates(_scxml, _xmlPrefix);
+
+    std::map<std::string, int> stateIds;
+    std::map<XERCESC_NS::DOMElement*, State*> stateElements;
+    std::map<XERCESC_NS::DOMElement*, Transition*> transElements;
+
+    
+    /** -- All things states -- */
+    
+    std::list<XERCESC_NS::DOMElement*> tmp;
+    size_t i, j;
+    
+    tmp = DOMUtils::inDocumentOrder({
+        _xmlPrefix.str() + "state",
+        _xmlPrefix.str() + "parallel",
+        _xmlPrefix.str() + "scxml",
+        _xmlPrefix.str() + "initial",
+        _xmlPrefix.str() + "final",
+        _xmlPrefix.str() + "history"
+    }, _scxml);
+
+    _states.resize(tmp.size());
+    
+    for (i = 0; i < _states.size(); i++) {
+        _states[i] = new State(i);
+        _states[i]->element = tmp.front();
+        stateElements[_states[i]->element] = _states[i];
+        tmp.pop_front();
+    }
+    assert(tmp.size() == 0);
+    
+    if (_binding == Binding::EARLY && _states.size() > 0) {
+        // add all data elements to the first state
+        std::list<DOMElement*> dataModels = DOMUtils::filterChildElements(_xmlPrefix.str() + "datamodel", _states[0]->element, true);
+        dataModels.erase(std::remove_if(dataModels.begin(),
+                                        dataModels.end(),
+                                        [this](DOMElement* elem) {
+                                            return !areFromSameMachine(elem, _scxml);
+                                        }),
+                         dataModels.end());
+        
+        std::list<XERCESC_NS::DOMElement*> dataList = DOMUtils::filterChildElements(_xmlPrefix.str() + "data", dataModels, false);
+        _states[0]->data = { std::make_move_iterator(std::begin(dataList)), std::make_move_iterator(std::end(dataList))};
+    }
+
+    for (i = 0; i < _states.size(); i++) {
+        // collect states with an id attribute
+        if (HAS_ATTR(_states[i]->element, kXMLCharId)) {
+            stateIds[ATTR(_states[i]->element, kXMLCharId)] = i;
+        }
+        
+        // check for executable content and datamodels
+        if (_states[i]->element->getChildElementCount() > 0) {
+            std::list<XERCESC_NS::DOMElement*> entryList = DOMUtils::filterChildElements(_xmlPrefix.str() + "onentry", _states[i]->element);
+            std::list<XERCESC_NS::DOMElement*> exitList = DOMUtils::filterChildElements(_xmlPrefix.str() + "onexit", _states[i]->element);
+            std::list<XERCESC_NS::DOMElement*> invokeList = DOMUtils::filterChildElements(_xmlPrefix.str() + "invoke", _states[i]->element);
+            _states[i]->onEntry = { std::make_move_iterator(std::begin(entryList)), std::make_move_iterator(std::end(entryList))};
+            _states[i]->onExit = { std::make_move_iterator(std::begin(exitList)), std::make_move_iterator(std::end(exitList))};
+            _states[i]->invoke = { std::make_move_iterator(std::begin(invokeList)), std::make_move_iterator(std::end(invokeList))};
+            
+            if (i == 0) {
+                // have global scripts as onentry of <scxml>
+                std::list<XERCESC_NS::DOMElement*> scriptList = DOMUtils::filterChildElements(_xmlPrefix.str() + "script", _states[i]->element, false);
+                _states[i]->onEntry = { std::make_move_iterator(std::begin(scriptList)), std::make_move_iterator(std::end(scriptList))};
+            }
+            
+            std::list<DOMElement*> doneDatas = DOMUtils::filterChildElements(_xmlPrefix.str() + "donedata", _states[i]->element);
+            if (doneDatas.size() > 0) {
+                _states[i]->doneData = doneDatas.front();
+            }
+            
+            if (_binding == Binding::LATE) {
+                std::list<DOMElement*> dataModels = DOMUtils::filterChildElements(_xmlPrefix.str() + "datamodel", _states[i]->element);
+                if (dataModels.size() > 0) {
+                    std::list<XERCESC_NS::DOMElement*> dataList = DOMUtils::filterChildElements(_xmlPrefix.str() + "data", dataModels, false);
+                    _states[i]->data = { std::make_move_iterator(std::begin(dataList)), std::make_move_iterator(std::end(dataList))};
+                }
+            }
+            
+        }
+        
+        // set the states type
+        if (false) {
+        } else if (iequals(TAGNAME(_states[i]->element), _xmlPrefix.str() + "initial")) {
+            _states[i]->type = USCXML_STATE_INITIAL;
+        } else if (isFinal(_states[i]->element)) {
+            _states[i]->type =  USCXML_STATE_FINAL;
+        } else if (isHistory(_states[i]->element)) {
+            if (HAS_ATTR(_states[i]->element, kXMLCharType) && iequals(ATTR(_states[i]->element, kXMLCharType), "deep")) {
+                _states[i]->type = USCXML_STATE_HISTORY_DEEP;
+            } else {
+                _states[i]->type = USCXML_STATE_HISTORY_SHALLOW;
+            }
+        } else if (isAtomic(_states[i]->element)) {
+            _states[i]->type = USCXML_STATE_ATOMIC;
+        } else if (isParallel(_states[i]->element)) {
+            _states[i]->type = USCXML_STATE_PARALLEL;
+        } else if (isCompound(_states[i]->element)) {
+            _states[i]->type = USCXML_STATE_COMPOUND;
+        } else { // <scxml>
+            _states[i]->type = USCXML_STATE_COMPOUND;
+        }
+
+        // establish the states' completion
+        std::list<DOMElement*> completionList = getCompletion(_states[i]->element);
+        
+        for (j = 0; completionList.size() > 0; j++) {
+            _states[i]->completion.insert(stateElements[completionList.front()]);
+            completionList.pop_front();
+        }
+        assert(completionList.size() == 0);
+        
+        // this is set when establishing the completion
+        if (_states[i]->element->getUserData(X("hasHistoryChild")) == _states[i]) {
+            _states[i]->type |= USCXML_STATE_HAS_HISTORY;
+        }
+
+        // set the states parent
+        DOMNode* parent = _states[i]->element->getParentNode();
+        if (parent && parent->getNodeType() == DOMNode::ELEMENT_NODE) {
+            _states[i]->parent = stateElements[(DOMElement*)parent];
+        }
+        
+        // set the states children
+        std::list<State*> childList;
+        for (auto childElem = _states[i]->element->getFirstElementChild(); childElem; childElem = childElem->getNextElementSibling()) {
+            if (isState(childElem, false)) {
+                childList.push_back(stateElements[childElem]);
+            }
+        }
+        _states[i]->children = { std::make_move_iterator(std::begin(childList)), std::make_move_iterator(std::end(childList))};
+    }
+    
+    /** -- All things transitions -- */
+
+    tmp = DOMUtils::inPostFixOrder({
+        XML_PREFIX(_scxml).str() + "scxml",
+        XML_PREFIX(_scxml).str() + "state",
+        XML_PREFIX(_scxml).str() + "final",
+        XML_PREFIX(_scxml).str() + "history",
+        XML_PREFIX(_scxml).str() + "initial",
+        XML_PREFIX(_scxml).str() + "parallel"
+    }, _scxml);
+    tmp = DOMUtils::filterChildElements(XML_PREFIX(_scxml).str() + "transition", tmp);
+    
+    _transitions.resize(tmp.size());
+    
+    for (i = 0; i < _transitions.size(); i++) {
+        _transitions[i] = new Transition(i);
+        _transitions[i]->element = tmp.front();
+        transElements[_transitions[i]->element] = _transitions[i];
+        tmp.pop_front();
+    }
+    assert(tmp.size() == 0);
+
+    
+    for (i = 0; i < _transitions.size(); i++) {
+        // establish the transitions' exit set
+        assert(_transitions[i]->element != NULL);
+        
+        {
+            std::list<DOMElement*> exitList = getExitSet(_transitions[i]->element, _scxml);
+
+            auto elemIter = exitList.begin();
+            for (size_t j = 0; j < exitList.size(); j++) {
+                _transitions[i]->exitSet.insert(stateElements[*elemIter++]);
+            }
+        }
+
+        // establish the transitions' conflict set
+        std::list<Transition*> conflictList;
+
+        for (j = 0; j < _transitions.size(); j++) {
+            DOMElement* t1 = _transitions[i]->element;
+            DOMElement* t2 = _transitions[j]->element;
+            if ((getSourceState(t1) == getSourceState(t2)) ||
+                (DOMUtils::isDescendant(getSourceState(t1), getSourceState(t2))) ||
+                (DOMUtils::isDescendant(getSourceState(t2), getSourceState(t1))) ||
+                (DOMUtils::hasIntersection(getExitSet(t1, _scxml), getExitSet(t2, _scxml)))) {
+            } else {
+                // compatible
+                conflictList.push_back(transElements[t2]);
+            }
+        }
+        _transitions[i]->compatible = {std::make_move_iterator(std::begin(conflictList)), std::make_move_iterator(std::end(conflictList))};
+        
+
+        // establish the transitions' target set
+        std::list<State*> targetList;
+
+        {
+            std::list<std::string> targets = tokenize(ATTR(_transitions[i]->element, kXMLCharTarget));
+            for (auto tIter = targets.begin(); tIter != targets.end(); tIter++) {
+                if (stateIds.find(*tIter) != stateIds.end()) {
+                    targetList.push_back(stateElements[getState(*tIter, _scxml)]);
+                }
+            }
+        }
+        _transitions[i]->target = {std::make_move_iterator(std::begin(targetList)), std::make_move_iterator(std::end(targetList))};
+        
+        // the transition's type
+        if (!HAS_ATTR(_transitions[i]->element, kXMLCharTarget)) {
+            _transitions[i]->type |= USCXML_TRANS_TARGETLESS;
+        }
+        
+        if (HAS_ATTR(_transitions[i]->element, kXMLCharType) && iequals(ATTR(_transitions[i]->element, kXMLCharType), "internal")) {
+            _transitions[i]->type |= USCXML_TRANS_INTERNAL;
+        }
+        
+        if (!HAS_ATTR(_transitions[i]->element, kXMLCharEvent)) {
+            _transitions[i]->type |= USCXML_TRANS_SPONTANEOUS;
+        }
+        
+        if (iequals(TAGNAME_CAST(_transitions[i]->element->getParentNode()), _xmlPrefix.str() + "history")) {
+            _transitions[i]->type |= USCXML_TRANS_HISTORY;
+        }
+        
+        if (iequals(TAGNAME_CAST(_transitions[i]->element->getParentNode()), _xmlPrefix.str() + "initial")) {
+            _transitions[i]->type |= USCXML_TRANS_INITIAL;
+        }
+        
+        // the transitions event and condition
+        _transitions[i]->event = (HAS_ATTR(_transitions[i]->element, kXMLCharEvent) ?
+                                  ATTR(_transitions[i]->element, kXMLCharEvent) : "");
+        _transitions[i]->cond = (HAS_ATTR(_transitions[i]->element, kXMLCharCond) ?
+                                 ATTR(_transitions[i]->element, kXMLCharCond) : "");
+        
+        // is there executable content?
+        if (_transitions[i]->element->getChildElementCount() > 0) {
+            _transitions[i]->onTrans = _transitions[i]->element;
+        }
+
+    }
+    
+    /* Connect states and transitions */
+    for (auto state : _states) {
+        std::list<XERCESC_NS::DOMElement*> transList = DOMUtils::filterChildElements(_xmlPrefix.str() + "transition", state->element);
+        state->transitions.resize(transList.size());
+
+        for (auto i = 0; transList.size() > 0; i++) {
+            auto trans = transList.front();
+            transList.pop_front();
+            transElements[trans]->source = state;
+            state->transitions[i] = transElements[trans];
+        }
+        assert(transList.size() == 0);
+    }
+    
+    _isInitialized = true;
+}
+
+InterpreterState LargeMicroStep::step(size_t blockMs) {
+    if (!_isInitialized) {
+        init(_scxml);
+        return USCXML_INITIALIZED;
+    }
+    
+    std::set<InterpreterMonitor*> monitors = _callbacks->getMonitors();
+    
+    _exitSet.clear();
+    _entrySet.clear();
+    _targetSet.clear();
+    _tmpStates.clear();
+    
+    _compatible.clear();
+    _transSet.clear();
+    boost::container::flat_set<State*> erase;
+    
+    if (_flags & USCXML_CTX_FINISHED)
+        return USCXML_FINISHED;
+    
+    if (_flags & USCXML_CTX_TOP_LEVEL_FINAL) {
+        USCXML_MONITOR_CALLBACK(monitors, beforeCompletion);
+        
+        /* exit all remaining states */
+        for (auto stateIter = _configuration.end() ; stateIter != _configuration.begin() ; /* Do nothing */ ) {
+            --stateIter;
+            /* call all on exit handlers */
+            for (auto onExit : (*stateIter)->onExit) {
+                try {
+                    _callbacks->process(onExit);
+                } catch (...) {
+                    // do nothing and continue with next block
+                }
+            }
+            if (_invocations.find(*stateIter) != _invocations.end()) {
+                /* cancel all invokers */
+                for (auto invoke : (*stateIter)->invoke) {
+                    _callbacks->uninvoke(invoke);
+                }
+                _invocations.clear();
+            }
+        }
+        
+        _flags |= USCXML_CTX_FINISHED;
+        
+        USCXML_MONITOR_CALLBACK(monitors, afterCompletion);
+        
+        return USCXML_FINISHED;
+    }
+    
+    
+    if (_flags == USCXML_CTX_PRISTINE) {
+        // TODO: Is this working?
+        _targetSet = _states.front()->completion;
+        _flags |= USCXML_CTX_SPONTANEOUS | USCXML_CTX_INITIALIZED;
+        USCXML_MONITOR_CALLBACK(monitors, beforeMicroStep);
+        
+        goto ESTABLISH_ENTRYSET;
+    }
+    
+    if (_flags & USCXML_CTX_SPONTANEOUS) {
+        _event = Event();
+        goto SELECT_TRANSITIONS;
+    }
+    
+    
+    if ((_event = _callbacks->dequeueInternal())) {
+        USCXML_MONITOR_CALLBACK1(monitors, beforeProcessingEvent, _event);
+        goto SELECT_TRANSITIONS;
+    }
+    
+    /* manage uninvocations */
+    for (auto invokeIter = _invocations.begin(); invokeIter != _invocations.end();) {
+        if (_configuration.find(*invokeIter) == _configuration.end()) {
+            /* uninvoke */
+            for (auto invoke : (*invokeIter)->invoke) {
+                _callbacks->uninvoke(invoke);
+            }
+            invokeIter = _invocations.erase(invokeIter);
+        } else {
+            invokeIter++;
+        }
+    }
+    
+    /* manage invocations */
+    for (auto config : _configuration) {
+        if (_invocations.find(config) == _invocations.end()) {
+            for (auto invoke : config->invoke) {
+                try {
+                    /* invoke */
+                    _callbacks->invoke(invoke);
+                } catch (ErrorEvent e) {
+                    LOG(_callbacks->getLogger(), USCXML_WARN) << e;
+                    // TODO: Shall we deliver the event into the interpreter runtime?
+                } catch (...) {
+                }
+            }
+        }
+        _invocations.insert(config);
+    }
+    
+    // we dequeued all internal events and ought to signal stable configuration
+    if (!(_flags & USCXML_CTX_STABLE)) {
+        USCXML_MONITOR_CALLBACK(monitors, onStableConfiguration);
+        _microstepConfigurations.clear();
+        _flags |= USCXML_CTX_STABLE;
+        return USCXML_MACROSTEPPED;
+    }
+    
+    if ((_event = _callbacks->dequeueExternal(blockMs))) {
+        USCXML_MONITOR_CALLBACK1(monitors, beforeProcessingEvent, _event);
+        goto SELECT_TRANSITIONS;
+    }
+    
+    if (_isCancelled) {
+        // finalize and exit
+        _flags |= USCXML_CTX_TOP_LEVEL_FINAL;
+        return USCXML_CANCELLED;
+    }
+    
+    //	if (blocking) // we received the empty event to unblock
+    //        return USCXML_IDLE; // we return IDLE nevertheless
+    
+    return USCXML_IDLE;
+    
+SELECT_TRANSITIONS:
+    
+    // we read an event - unset stable to signal onstable again later
+    _flags &= ~USCXML_CTX_STABLE;
+    
+    {
+        BENCHMARK("select transitions");
+        for (auto transition : _transitions) { // we need to iterate over all for ordering
+            
+            /* never select history or initial transitions automatically */
+            if unlikely(transition->type & (USCXML_TRANS_HISTORY | USCXML_TRANS_INITIAL))
+                continue;
+            
+            /* is it even active */
+            if (_configuration.find(transition->source) == _configuration.end())
+                continue;
+            
+            /* is it spontaneous with an event or vice versa? */
+            if ((transition->event.size() == 0 && _event) ||
+                (transition->event.size() != 0 && !_event))
+                continue;
+
+            /* is it non-conflicting? */
+            if ((_flags & USCXML_CTX_TRANSITION_FOUND) && _compatible.find(transition) == _compatible.end())
+                continue;
+            
+            /* is it matched? */
+            if (_event && !_callbacks->isMatched(_event, transition->event))
+                continue;
+            
+            /* is it enabled? */
+            if (transition->cond.size() > 0 && !_callbacks->isTrue(transition->cond))
+                continue;
+
+            /* transitions that are pre-empted */
+            if (_flags & USCXML_CTX_TRANSITION_FOUND) {
+                for (auto compIter = _compatible.begin(); compIter != _compatible.end();) {
+                    if (transition->compatible.find(*compIter) == transition->compatible.end()) {
+                        compIter = _compatible.erase(compIter);
+                    } else {
+                        compIter++;
+                    }
+                }
+            } else {
+                _compatible = transition->compatible;
+            }
+            
+            /* remember that we found a transition */
+            _flags |= USCXML_CTX_TRANSITION_FOUND;
+
+            /* states that are directly targeted (resolve as entry-set later) */
+            _targetSet.insert(transition->target.begin(), transition->target.end());
+            
+            /* states that will be left */
+            for (auto config : _configuration) {
+                if (transition->exitSet.find(config) != transition->exitSet.end()) {
+                    _exitSet.insert(config);
+                }
+            }
+            
+            _transSet.insert(transition);
+        }
+    }
+    if (_flags & USCXML_CTX_TRANSITION_FOUND) {
+        // trigger more sppontaneuous transitions
+        _flags |= USCXML_CTX_SPONTANEOUS;
+        _flags &= ~USCXML_CTX_TRANSITION_FOUND;
+    } else {
+        // spontaneuous transitions are exhausted and we will attempt to dequeue an internal event next round
+        _flags &= ~USCXML_CTX_SPONTANEOUS;
+        return USCXML_MICROSTEPPED;
+    }
+    
+    USCXML_MONITOR_CALLBACK(monitors, beforeMicroStep);
+    
+#ifdef USCXML_VERBOSE
+    std::cerr << "Targets: ";
+    printStateNames(_targetSet);
+#endif
+    
+#ifdef USCXML_VERBOSE
+    std::cerr << "ExitSet: ";
+    printStateNames(_exitSet);
+#endif
+    
+    
+    /* REMEMBER_HISTORY: */
+    {
+        BENCHMARK("remember history");
+
+        for (auto state : _states) {
+            if likely(USCXML_STATE_MASK(state->type) != USCXML_STATE_HISTORY_SHALLOW &&
+                      USCXML_STATE_MASK(state->type) != USCXML_STATE_HISTORY_DEEP)
+                continue;
+            
+            if likely(_exitSet.find(state->parent) == _exitSet.end())
+                continue;
+
+            /* a history state whose parent is about to be exited */
+            for (auto completion : state->completion) {
+                if (_configuration.find(completion) != _configuration.end()) {
+                    _history.insert(completion);
+                } else {
+                    _history.erase(completion);
+                }
+            }
+        }
+    }
+    
+#ifdef USCXML_VERBOSE
+    std::cerr << "History: ";
+    printStateNames(_history);
+#endif
+
+ESTABLISH_ENTRYSET:
+    /* calculate new entry set */
+    _entrySet = _targetSet;
+    
+#ifdef USCXML_VERBOSE
+    std::cerr << "Targets: ";
+    printStateNames(_targetSet);
+#endif
+
+    /* make sure iterators are not invalidated, TODO: we can know the actual maximum number by syntactic analysis */
+    _entrySet.reserve(_states.size());
+    
+    /* iterate for ancestors */
+    {
+        BENCHMARK("add ancestors");
+        // running from back to front allows us to add parents only due to document order
+        for (auto stateIter = _entrySet.end() ; stateIter != _entrySet.begin() ; /* Do nothing */ ) {
+            --stateIter;
+            if ((*stateIter)->parent) {
+                stateIter = ++(_entrySet.insert((*stateIter)->parent).first);
+            }
+        }
+    }
+    
+    /* iterate for descendants */
+    {
+        BENCHMARK("add descendants");
+        // we cannot use the simplified for loop as inserting will invalidate those iterators
+        for (auto stateIter = _entrySet.begin(); stateIter != _entrySet.end(); stateIter++ ) {
+            State* state = *stateIter;
+            
+            switch (USCXML_STATE_MASK(state->type)) {
+                case USCXML_STATE_FINAL:
+                case USCXML_STATE_ATOMIC:
+                    break;
+                    
+                case USCXML_STATE_PARALLEL: {
+                    BENCHMARK("add descendants parallel");
+                    _entrySet.insert(state->completion.begin(), state->completion.end());
+                    break;
+                }
+                    
+                case USCXML_STATE_HISTORY_SHALLOW:
+                case USCXML_STATE_HISTORY_DEEP: {
+                    BENCHMARK("add descendants history");
+                    if (_configuration.find(state->parent) == _configuration.end() &&
+                        !intersects(state->completion.begin(), state->completion.end(), _history.begin(), _history.end())) {
+                    
+                        /* nothing set for history, look for a default transition */
+                        for (auto transition : state->transitions) {
+                            _entrySet.insert(transition->target.begin(), transition->target.end());
+                            
+                            if(USCXML_STATE_MASK(state->type) == USCXML_STATE_HISTORY_DEEP &&
+                               !intersects(transition->target.begin(), transition->target.end(), state->children.begin(), state->children.end())) {
+
+                                // add all the target's ancestors
+                                for (auto target : transition->target) {
+                                    State* anc = target->parent;
+                                    while(anc != NULL && _entrySet.find(anc) == _entrySet.end()) {
+                                        _entrySet.insert(anc);
+                                        anc = anc->parent;
+                                    }
+                                }
+                            }
+                            _transSet.insert(transition);
+                            break;
+                        }
+                    } else {
+                        _tmpStates = state->completion;
+                        for (auto iter = _tmpStates.begin(); iter != _tmpStates.end();) {
+                            if (_history.find(*iter) == _history.end()) {
+                                iter = _tmpStates.erase(iter);
+                            } else {
+                                iter++;
+                            }
+                        }
+                        _entrySet.insert(_tmpStates.begin(), _tmpStates.end());
+                        
+                        if (state->type == (USCXML_STATE_HAS_HISTORY | USCXML_STATE_HISTORY_DEEP)) {
+                            /* a deep history state with nested histories -> more completion */
+                            for (auto histState : state->completion) {
+                                if (!(histState->type & USCXML_STATE_HAS_HISTORY))
+                                    continue;
+                                
+                                if (_entrySet.find(histState) == _entrySet.end())
+                                    continue;
+                                
+                                for (auto histChild : histState->children) {
+                                    if ((USCXML_STATE_MASK(histChild->type) == USCXML_STATE_HISTORY_DEEP ||
+                                         USCXML_STATE_MASK(histChild->type) == USCXML_STATE_HISTORY_SHALLOW)) {
+                                        // We can leverage that deep history assignments are already completed and skip a few states in outer loop
+                                        stateIter = _entrySet.insert(histChild).first;
+                                    }
+                                }
+                            }
+                        }
+                    }
+                    break;
+                }
+                    
+                case USCXML_STATE_INITIAL: {
+                    BENCHMARK("add descendants initial");
+                    for (auto transition : state->transitions) {
+                        _transSet.insert(transition); // remember transition for onentry later
+                        
+                        for (auto target : transition->target) {
+                            _entrySet.insert(target);
+                            // add all states between target and this state
+                            State* anc = target->parent;
+                            while(anc != NULL && anc != state) {
+                                _entrySet.insert(anc);
+                                anc = anc->parent;
+                            }
+                        }
+                    }
+                    break;
+                }
+                    
+                case USCXML_STATE_COMPOUND: {
+                    BENCHMARK("add descendants compound");
+
+                    /* Compound state may already be complete */
+                    {
+                        BENCHMARK("add descendants compound intersect entry/child");
+                        for (auto child : state->children) {
+                            /* one child is already in entry_set */
+                            if (_entrySet.find(child) != _entrySet.end())
+                                goto NEXT_DESCENDANT;
+                            /* one child is already active and not left */
+                            if (_exitSet.find(child) == _exitSet.end() && _configuration.find(child) != _configuration.end())
+                                goto NEXT_DESCENDANT;
+                        }
+                    }
+                    
+                    assert(state->completion.size() == 1);
+                    State* completion = *(state->completion.begin());
+
+                    _entrySet.insert(completion);
+
+                    /* deep completion */
+                    {
+                        BENCHMARK("add descendants compound deep completion");
+
+                        if (std::binary_search(state->children.begin(), state->children.end(), completion))
+                            goto NEXT_DESCENDANT;
+
+                        // add deep completions ancestors
+                        State* anc = completion->parent;
+                        while(anc != NULL && anc != state) {
+                            _entrySet.insert(anc);
+                            anc = anc->parent;
+                        }
+                    }
+                    break;
+                }
+        
+            }
+        NEXT_DESCENDANT:;
+        }
+    }
+    
+#ifdef USCXML_VERBOSE
+    std::cerr << "Entering: ";
+    printStateNames(_entrySet);
+#endif
+
+    /* EXIT_STATES: */
+    {
+        BENCHMARK("exit states");
+        for (auto stateIter = _exitSet.end() ; stateIter != _exitSet.begin() ; /* Do nothing */ ) {
+            State* state = *(--stateIter);
+            
+            USCXML_MONITOR_CALLBACK1(monitors, beforeExitingState, state->element);
+
+            /* call all on exit handlers */
+            for (auto exitIter = state->onExit.begin(); exitIter != state->onExit.end(); exitIter++) {
+                try {
+                    _callbacks->process(*exitIter);
+                } catch (...) {
+                    // do nothing and continue with next block
+                }
+            }
+            
+            _configuration.erase(state);
+            USCXML_MONITOR_CALLBACK1(monitors, afterExitingState, state->element);
+
+        }
+    }
+    
+    /* TAKE_TRANSITIONS: */
+    {
+        BENCHMARK("take transitions");
+        for (auto transition : _transSet) {
+            if ((transition->type & (USCXML_TRANS_HISTORY | USCXML_TRANS_INITIAL)) == 0) {
+                USCXML_MONITOR_CALLBACK1(monitors, beforeTakingTransition, transition->element);
+                
+                if (transition->onTrans != NULL) {
+                    
+                    /* call executable content in non-history, non-initial transition */
+                    try {
+                        _callbacks->process(transition->onTrans);
+                    } catch (...) {
+                        // do nothing and continue with next block
+                    }
+                }
+                
+                USCXML_MONITOR_CALLBACK1(monitors, afterTakingTransition, transition->element);
+            }
+        }
+    }
+    
+    // remove active state from enter states
+    for (auto config : _configuration) {
+        if (_entrySet.find(config) != _entrySet.end())
+            _entrySet.erase(config);
+    }
+    
+    /* ENTER_STATES: */
+    {
+        BENCHMARK("enter states");
+        for (auto state : _entrySet) {
+
+            /* these are no proper states */
+            if unlikely(USCXML_STATE_MASK(state->type) == USCXML_STATE_HISTORY_DEEP ||
+                        USCXML_STATE_MASK(state->type) == USCXML_STATE_HISTORY_SHALLOW ||
+                        USCXML_STATE_MASK(state->type) == USCXML_STATE_INITIAL) {
+                continue;
+            }
+
+            USCXML_MONITOR_CALLBACK1(monitors, beforeEnteringState, state->element);
+            
+            _configuration.insert(state);
+
+            /* initialize data */
+            if (state->data.size() > 0) {
+                if (_initializedData.find(state) == _initializedData.end()) {
+                    for (auto dataIter = state->data.begin(); dataIter != state->data.end(); dataIter++) {
+                        _callbacks->initData(*dataIter);
+                    }
+                    _initializedData.insert(state);
+                }
+            }
+            
+            /* call all on entry handlers */
+            for (auto onEntry : state->onEntry) {
+                try {
+                    _callbacks->process(onEntry);
+                } catch (...) {
+                    // do nothing and continue with next block
+                }
+            }
+            
+            USCXML_MONITOR_CALLBACK1(monitors, afterEnteringState, state->element);
+
+            /* take history and initial transitions */
+            for (auto child : state->children) {
+                if (child->type != USCXML_STATE_INITIAL &&
+                    child->type != USCXML_STATE_HISTORY_DEEP &&
+                    child->type != USCXML_STATE_HISTORY_SHALLOW)
+                    continue;
+                
+                for (auto transition : child->transitions) {
+                    if (!(transition->type & (USCXML_TRANS_HISTORY | USCXML_TRANS_INITIAL)) ||
+                        _transSet.find(transition) == _transSet.end())
+                        continue;
+                    
+                    USCXML_MONITOR_CALLBACK1(monitors, beforeTakingTransition, transition->element);
+                    
+                    /* call executable content in transition */
+                    if (transition->onTrans != NULL) {
+                        try {
+                            _callbacks->process(transition->onTrans);
+                        } catch (...) {
+                            // do nothing and continue with next block
+                        }
+                    }
+                    
+                    USCXML_MONITOR_CALLBACK1(monitors, afterTakingTransition, transition->element);
+                }
+
+            }
+            
+            /* handle final states */
+            if unlikely(USCXML_STATE_MASK(state->type) == USCXML_STATE_FINAL) {
+                BENCHMARK("enter states final")
+                if unlikely(state->parent == _states[0]) {
+                    // only the topmost scxml is an ancestor
+                    _flags |= USCXML_CTX_TOP_LEVEL_FINAL;
+                } else {
+                    /* raise done event */
+                    _callbacks->raiseDoneEvent(state->parent->element, state->doneData);
+                }
+                
+                /**
+                 * are we the last final state to leave a parallel state?:
+                 * 1. Gather all parallel states in our ancestor chain
+                 * 2. Find all states for which these parallels are ancestors
+                 * 3. Iterate all active final states and remove their ancestors
+                 * 4. If a state remains, not all children of a parallel are final
+                 */
+                {
+                    BENCHMARK("enter states final parallel")
+
+                    State* anc = state->parent;
+                    while(anc != NULL) {
+                        if (USCXML_STATE_MASK(anc->type) == USCXML_STATE_PARALLEL &&
+                            isInFinal(anc)) {
+                            _callbacks->raiseDoneEvent(anc->element, anc->doneData);
+                            break; // ancestors cannot be final either
+                        }
+                        anc = anc->parent;
+                    }
+                }
+            }
+        }
+    }
+    
+    USCXML_MONITOR_CALLBACK(monitors, afterMicroStep);
+    
+    // are we running in circles?
+    if (_microstepConfigurations.find(_configuration) != _microstepConfigurations.end()) {
+        InterpreterIssue issue("Reentering same configuration during microstep  - possible endless loop",
+                               NULL,
+                               InterpreterIssue::USCXML_ISSUE_WARNING);
+        
+        USCXML_MONITOR_CALLBACK1(monitors,
+                                 reportIssue,
+                                 issue);
+    }
+    _microstepConfigurations.insert(_configuration);
+    
+    return USCXML_MICROSTEPPED;
+}
+
+bool LargeMicroStep::isInFinal(const State* state) {
+    switch (USCXML_STATE_MASK(state->type)) {
+        case USCXML_STATE_FINAL:
+            /* a final state is final */
+            return true;
+
+        case USCXML_STATE_ATOMIC:
+            return false;
+
+        case USCXML_STATE_PARALLEL:
+            for (auto child : state->children) {
+                if (!isInFinal(child))
+                    return false;
+            }
+            return true;
+
+        case USCXML_STATE_INITIAL:
+            return false;
+
+        case USCXML_STATE_COMPOUND:
+            for (auto child : state->children) {
+                if (_configuration.find(child) != _configuration.end()) {
+                    return isInFinal(child);
+                    break;
+                }
+            }
+            return true;
+
+        default:
+            // history
+            return true;
+            break;
+    }
+    return false;
+}
+   
+void LargeMicroStep::resortStates(DOMElement* element, const X& xmlPrefix) {
+    
+    /**
+     initials
+     deep histories
+     shallow histories
+     everything else
+     */
+    
+    // TODO: We can do this in one iteration
+    
+    DOMElement* child = element->getFirstElementChild();
+    while(child) {
+        resortStates(child, xmlPrefix);
+        child = child->getNextElementSibling();
+    }
+    
+    // shallow history states to top
+    child = element->getFirstElementChild();
+    while(child) {
+        if (TAGNAME_CAST(child) == xmlPrefix.str() + "history" &&
+            (!HAS_ATTR(element, kXMLCharType) || iequals(ATTR(element, kXMLCharType), "shallow"))) {
+            
+            DOMElement* tmp = child->getNextElementSibling();
+            if (child != element->getFirstChild()) {
+                element->insertBefore(child, element->getFirstChild());
+            }
+            child = tmp;
+        } else {
+            child = child->getNextElementSibling();
+        }
+    }
+    
+    // deep history states to top
+    child = element->getFirstElementChild();
+    while(child) {
+        if (child->getNodeType() == DOMNode::ELEMENT_NODE &&
+            TAGNAME_CAST(child) == xmlPrefix.str() + "history" &&
+            HAS_ATTR(element, kXMLCharType) &&
+            iequals(ATTR(element, kXMLCharType), "deep")) {
+            
+            DOMElement* tmp = child->getNextElementSibling();
+            if (child != element->getFirstChild()) {
+                element->insertBefore(child, element->getFirstChild());
+            }
+            child = tmp;
+        } else {
+            child = child->getNextElementSibling();
+        }
+    }
+    
+    // initial states on top of histories even
+    child = element->getFirstElementChild();
+    while(child) {
+        if (child->getNodeType() == DOMNode::ELEMENT_NODE && LOCALNAME_CAST(child) == "initial") {
+            DOMElement* tmp = child->getNextElementSibling();
+            if (child != element->getFirstChild()) {
+                element->insertBefore(child, element->getFirstChild());
+            }
+            child = tmp;
+        } else {
+            child = child->getNextElementSibling();
+        }
+    }
+}
+
+}
diff --git a/src/uscxml/interpreter/LargeMicroStep.h b/src/uscxml/interpreter/LargeMicroStep.h
new file mode 100644
index 0000000..3443d80
--- /dev/null
+++ b/src/uscxml/interpreter/LargeMicroStep.h
@@ -0,0 +1,179 @@
+/**
+ *  @file
+ *  @author     2017 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
+ */
+
+//#define USCXML_VERBOSE
+
+#ifndef LARGEMICROSTEP_H_2573547
+#define LARGEMICROSTEP_H_2573547
+
+#include "uscxml/config.h"
+#include "uscxml/Common.h"
+#include "uscxml/util/DOM.h" // X
+
+#include "uscxml/util/Predicates.h"
+#include "uscxml/util/String.h"
+#include "uscxml/interpreter/InterpreterMonitor.h"
+
+/* flat_set is 10 times faster than std::set here */
+#include <boost/container/flat_set.hpp>
+
+#include <vector>
+#include <list>
+#include <map>
+#include "MicroStepImpl.h"
+
+namespace uscxml {
+
+/**
+ * @ingroup microstep
+ * @ingroup impl
+ */
+class LargeMicroStep : public MicroStepImpl {
+public:
+
+	LargeMicroStep(MicroStepCallbacks* callbacks);
+	virtual ~LargeMicroStep();
+	virtual std::shared_ptr<MicroStepImpl> create(MicroStepCallbacks* callbacks);
+
+	virtual InterpreterState step(size_t blockMs);
+	virtual void reset();
+	virtual bool isInState(const std::string& stateId);
+	virtual std::list<XERCESC_NS::DOMElement*> getConfiguration();
+	void markAsCancelled();
+
+    virtual void deserialize(const Data& encodedState) {}
+    virtual Data serialize() { return Data(); }
+
+protected:
+	class State;
+	class Transition;
+
+    struct StateOrder
+    {
+        bool operator()(const State* lhs, const State* rhs) const  { return lhs->documentOrder < rhs->documentOrder; }
+    };
+
+    struct TransitionOrder
+    {
+        bool operator()(const Transition* lhs, const Transition* rhs) const  { return lhs->postFixOrder < rhs->postFixOrder; }
+    };
+
+    std::vector<State*> _states; ///< States in document order
+    std::vector<Transition*> _transitions; ///< Transitions in reverse post-order
+
+    boost::container::flat_set<State*, StateOrder> _configuration;
+    boost::container::flat_set<State*, StateOrder> _invocations;
+    boost::container::flat_set<State*, StateOrder> _history;
+    boost::container::flat_set<State*, StateOrder> _initializedData;
+
+	class Transition {
+	public:
+        Transition(uint32_t postFixOrder) : postFixOrder(postFixOrder) {}
+        const uint32_t postFixOrder; // making these const increases performance somewhat
+
+		XERCESC_NS::DOMElement* element = NULL;
+		boost::container::flat_set<Transition*, TransitionOrder> compatible;
+		boost::container::flat_set<State*, StateOrder> exitSet;
+
+		State* source = NULL;
+		std::vector<State*> target;
+
+		XERCESC_NS::DOMElement* onTrans = NULL;
+
+		std::string event;
+		std::string cond;
+
+		unsigned char type = 0;
+
+	};
+
+	class State {
+	public:
+        State(uint32_t documentOrder) : documentOrder(documentOrder) {}
+        const uint32_t documentOrder;
+
+		XERCESC_NS::DOMElement* element;
+		boost::container::flat_set<State*, StateOrder> completion;
+		std::vector<State*> children;
+		State* parent = NULL;
+
+        std::vector<Transition*> transitions;
+		std::vector<XERCESC_NS::DOMElement*> data;
+		std::vector<XERCESC_NS::DOMElement*> invoke;
+		std::vector<XERCESC_NS::DOMElement*> onEntry;
+		std::vector<XERCESC_NS::DOMElement*> onExit;
+		XERCESC_NS::DOMElement* doneData = NULL;
+
+		unsigned char type;
+	};
+
+    void init(XERCESC_NS::DOMElement* scxml);
+
+    std::list<XERCESC_NS::DOMElement*> getCompletion(const XERCESC_NS::DOMElement* state);
+    std::list<XERCESC_NS::DOMElement*> getHistoryCompletion(const XERCESC_NS::DOMElement* history);
+
+    unsigned char _flags = 0;
+    boost::container::flat_set<boost::container::flat_set<State*, StateOrder> > _microstepConfigurations;
+
+    bool _isInitialized = false;
+    bool _isCancelled = false;
+    Event _event; // we do not care about the event's representation
+
+    std::list<XERCESC_NS::DOMElement*> _globalScripts;
+
+    Binding _binding;
+    XERCESC_NS::DOMElement* _scxml;
+    X _xmlPrefix;
+    X _xmlNS;
+    
+    /// Normalize order of elements per state
+    void resortStates(XERCESC_NS::DOMElement* node, const X& xmlPrefix);
+
+private:
+
+    boost::container::flat_set<State*, StateOrder> _exitSet;
+    boost::container::flat_set<State*, StateOrder> _entrySet;
+    boost::container::flat_set<State*, StateOrder> _targetSet;
+    boost::container::flat_set<State*, StateOrder> _tmpStates;
+    
+    boost::container::flat_set<Transition*, TransitionOrder> _compatible;
+    boost::container::flat_set<Transition*, TransitionOrder> _transSet;
+
+    // adapted from http://www.cplusplus.com/reference/algorithm/set_intersection/
+    template <class iter_t1, class iter_t2, class compare = StateOrder>
+    bool intersects(iter_t1 first1, iter_t1 last1, iter_t2 first2, iter_t2 last2) {
+        while (first1 != last1 && first2 != last2) {
+            if (compare()(*first1, *first2)) {
+                ++first1;
+            } else if (compare()(*first2, *first1)) {
+                ++first2;
+            } else {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    bool isInFinal(const State* state);
+    void printStateNames(const boost::container::flat_set<LargeMicroStep::State*, LargeMicroStep::StateOrder>& a);
+
+};
+
+}
+#endif /* end of include guard: LARGEMICROSTEP_H_2573547 */
diff --git a/src/uscxml/transform/ChartToC.cpp b/src/uscxml/transform/ChartToC.cpp
index 61d1b25..0f64ad6 100644
--- a/src/uscxml/transform/ChartToC.cpp
+++ b/src/uscxml/transform/ChartToC.cpp
@@ -53,8 +53,8 @@ ChartToC::ChartToC(const Interpreter& other) : TransformerImpl(other), _topMostM
 	_allMachines.push_back(this);
 	_hasNativeDataModel = HAS_ATTR(_scxml, kXMLCharDataModel) && ATTR(_scxml, kXMLCharDataModel) == "native";
 
-	prepare();
 	findNestedMachines();
+    prepare();
 
 	if (_extensions.find("prefix") != _extensions.end()) {
 		_prefixes = new std::list<std::string>();
@@ -382,8 +382,15 @@ void ChartToC::prepare() {
 	setStateCompletion();
 
 	// how many bits do we need to represent the state array?
+    size_t largestStateSpace = 0;
+    size_t largestTransSpace = 0;
+    for (auto machine : _allMachines) {
+        largestStateSpace = (machine->_states.size() > largestStateSpace ? machine->_states.size() : largestStateSpace);
+        largestTransSpace = (machine->_transitions.size() > largestTransSpace ? machine->_transitions.size() : largestTransSpace);
+    }
+    
 	std::string seperator;
-	_stateCharArraySize = ceil((float)_states.size() / (float)8);
+	_stateCharArraySize = ceil((float)largestStateSpace / (float)8);
 	_stateCharArrayInit = "{";
 	for (size_t i = 0; i < _stateCharArraySize; i++) {
 		_stateCharArrayInit += seperator + "0";
@@ -392,18 +399,18 @@ void ChartToC::prepare() {
 	_stateCharArrayInit += "}";
 
 	if (false) {
-	} else if (_states.size() < (1UL << 8)) {
+	} else if (largestStateSpace < (1UL << 8)) {
 		_stateDataType = "uint8_t";
-	} else if (_states.size() < (1UL << 16)) {
+	} else if (largestStateSpace < (1UL << 16)) {
 		_stateDataType = "uint16_t";
-	} else if (_states.size() < (1UL << 32)) {
+	} else if (largestStateSpace < (1UL << 32)) {
 		_stateDataType = "uint32_t";
 	} else {
 		_stateDataType = "uint64_t";
 	}
 
 	seperator = "";
-	_transCharArraySize = ceil((float)_transitions.size() / (float)8);
+	_transCharArraySize = ceil((float)largestTransSpace / (float)8);
 	_transCharArrayInit = "{";
 	for (size_t i = 0; i < _transCharArraySize; i++) {
 		_transCharArrayInit += seperator + "0";
@@ -412,11 +419,11 @@ void ChartToC::prepare() {
 	_transCharArrayInit += "}";
 
 	if (false) {
-	} else if (_transitions.size() < (1UL << 8)) {
+	} else if (largestTransSpace < (1UL << 8)) {
 		_transDataType = "uint8_t";
-	} else if (_transitions.size() < (1UL << 16)) {
+	} else if (largestTransSpace < (1UL << 16)) {
 		_transDataType = "uint16_t";
-	} else if (_transitions.size() < (1UL << 32)) {
+	} else if (largestTransSpace < (1UL << 32)) {
 		_transDataType = "uint32_t";
 	} else {
 		_transDataType = "uint64_t";
@@ -1663,11 +1670,13 @@ void ChartToC::writeElementInfo(std::ostream& stream) {
 		size_t i = 0;
 		for (auto iter = params.begin(); iter != params.end(); iter++, i++) {
 			DOMElement* param = *iter;
+            // TODO: Index is wrong for multiple params!
 			if (param->getParentNode() != parent) {
-				static_cast<DOMElement*>(param->getParentNode())->setAttribute(X("paramIndex"), X(toStr(i)));
 				if (i > 0) {
 					stream << "    { NULL, NULL, NULL }," << std::endl;
+                    i++;
 				}
+                static_cast<DOMElement*>(param->getParentNode())->setAttribute(X("paramIndex"), X(toStr(i)));
 				parent = param->getParentNode();
 			}
 			stream << "    { ";