/**
 *  @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 "uscxml/util/Predicates.h"

#include <algorithm>
#include <iostream>

#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();
	_configurationPostFix.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) + ":";
	}

	{
		BENCHMARK("init resort states")
		resortStates(_scxml, _xmlPrefix);
	}

	std::set<std::string> stateIds;

	/** -- 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();
		if (HAS_ATTR(_states[i]->element, kXMLCharId)) {
			_states[i]->name = ATTR(_states[i]->element, kXMLCharId);
		}
		_states[i]->element->setUserData(X("uscxmlState"), _states[i], NULL);
		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.insert(ATTR(_states[i]->element, kXMLCharId));
		}

		// TODO: Reserve space for ancestors? => Measure performance!

		// check for executable content and datamodels
		if (_states[i]->element->getChildElementCount() > 0) {
			// not every child element will be a child state, but we can shrink later
			_states[i]->children.reserve(_states[i]->element->getChildElementCount());

			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 { // <scxml> and any other state
			_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((State*)completionList.front()->getUserData(X("uscxmlState")));
			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 and add us as a children
		DOMNode* parent = _states[i]->element->getParentNode();
		if (parent && parent->getNodeType() == DOMNode::ELEMENT_NODE) {
			_states[i]->parent = (State*)parent->getUserData(X("uscxmlState"));
			if (_states[i]->parent != NULL) {
				_states[i]->parent->children.push_back(_states[i]);
				_states[i]->ancestors.insert(_states[i]->parent);
				_states[i]->ancestors.insert(_states[i]->parent->ancestors.begin(), _states[i]->parent->ancestors.end());
			}
		}
	}

	/** -- 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());
	_conflicting.resize(tmp.size());
	_compatible.resize(tmp.size());

	for (i = 0; i < _transitions.size(); i++) {
		_transitions[i] = new Transition(i);
		_transitions[i]->element = tmp.front();
		_transitions[i]->element->setUserData(X("uscxmlTrans"), _transitions[i], NULL);
		tmp.pop_front();
	}
	assert(tmp.size() == 0);


	for (i = 0; i < _transitions.size(); i++) {
		// establish the transitions' target set
		{
			std::list<std::string> targets = tokenize(ATTR(_transitions[i]->element, kXMLCharTarget));
			_transitions[i]->target.reserve(targets.size());

			for (auto tIter = targets.begin(); tIter != targets.end(); tIter++) {
				if (stateIds.find(*tIter) != stateIds.end()) {
					_transitions[i]->target.push_back((State*)getState(*tIter, _scxml)->getUserData(X("uscxmlState")));
				}
			}
		}

		// 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);
		if (transList.size() > 0) {
			state->transitions.resize(transList.size());
			for (auto i = 0; transList.size() > 0; i++) {
				auto trans = transList.front();
				transList.pop_front();
				Transition* uscxmlTrans = ((Transition*)trans->getUserData(X("uscxmlTrans")));
				uscxmlTrans->source = state;
				// save some memory? => Measure performance!
//                uscxmlTrans->compatible.shrink_to_fit();
//                uscxmlTrans->exitSet.shrink_to_fit();

				state->transitions[i] = uscxmlTrans;
			}
			// we need the postfix order for iterating transitions of active states
			state->postFixOrder = (*(state->transitions.begin()))->postFixOrder;
		} else {
			state->postFixOrder = std::numeric_limits<uint32_t>::max();
		}

		// save some memory? => Measure performance!
//        state->ancestors.shrink_to_fit();
		state->children.shrink_to_fit();
//        state->completion.shrink_to_fit();

		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();
	_conflicting.clear();
	_transSet.clear();

	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");

		// iterate active states in postfix order and find transitions
		for (auto stateIter = _configurationPostFix.begin(); stateIter != _configurationPostFix.end();) {
			State* state = *stateIter++;
//            std::cout << (HAS_ATTR(state->element, kXMLCharId) ? ATTR(state->element, kXMLCharId) : "?");
//            std::cout << ": " << state->documentOrder << " - " << state->postFixOrder << std::endl;

			for (auto transIter = state->transitions.begin(); transIter != state->transitions.end();) {
				Transition* transition = *transIter++;

				/* never select history or initial transitions automatically */
				if unlikely(transition->type & (USCXML_TRANS_HISTORY | USCXML_TRANS_INITIAL))
					continue;

				/* is it spontaneous with an event or vice versa? */
				if ((transition->event.size() == 0 && _event) ||
				        (transition->event.size() != 0 && !_event))
					continue;

				/* check whether it is explicitly conflicting or compatible, calculate if neither */
				if (_flags & USCXML_CTX_TRANSITION_FOUND) {
					BENCHMARK("select transitions conflict & compatible calc");

					if (_conflicting[transition->postFixOrder]) {
						// this transition is explicitly conflicting
						continue;
					}
					if (!_compatible[transition->postFixOrder]) {
						// it is not explicitly compatible, we know nothing!
						BENCHMARK("select transitions conflict & compatible calc no entry");

						bool conflicts = false;
						for (auto enabledTrans : _transSet) {
							if (enabledTrans->compatible.find(transition->postFixOrder) != enabledTrans->compatible.end() ||
							        (enabledTrans->conflicting.find(transition->postFixOrder) != enabledTrans->conflicting.end())) {
								continue;
							}

							std::pair<uint32_t, uint32_t> exit1 = getExitSet(transition);
							std::pair<uint32_t, uint32_t> exit2 = getExitSet(enabledTrans);

							if (exit1.first != 0 && exit2.first != 0 && // empty domain
							        ((exit1.first <= exit2.first && exit1.second >= exit2.first) ||
							         (exit2.first <= exit1.first && exit2.second >= exit1.first))) {
								// it is conflicting!
//                                assert(uscxml::conflicts(t1, t2, _scxml));
								transition->conflicting.insert(enabledTrans->postFixOrder);
								enabledTrans->conflicting.insert(transition->postFixOrder);
								conflicts = true;
								break;
							} else {
//                                assert(!uscxml::conflicts(t1, t2, _scxml));
								transition->compatible.insert(enabledTrans->postFixOrder);
								enabledTrans->compatible.insert(transition->postFixOrder);
							}
						}
						if (conflicts)
							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;

				// This transition is fine and ought to be taken!

				/* update conflicting and compatible transitions */
				if (_flags & USCXML_CTX_TRANSITION_FOUND) {
					BENCHMARK("select transitions conflict & compatible update");

					/* remove all compatible transitions not listed in ours */
					size_t i = _compatible.find_first();
					while(i != boost::dynamic_bitset<BITSET_BLOCKTYPE>::npos) {
						if (transition->compatible.find(i) == transition->compatible.end()) {
							_compatible[i] = false;
						}
						i = _compatible.find_next(i);
					}

					/* add all conflicting transitions listed in ours */
					for (auto conflict : transition->conflicting) {
						_conflicting[conflict] = true;
					}

				} else {
					/* Very first transition added to optimally transition set */
					for (auto compatible : transition->compatible) {
						_compatible[compatible] = true;
					}
					for (auto conflict : transition->conflicting) {
						_conflicting[conflict] = true;
					}
				}

				/* remember that we found a transition */
				_flags |= USCXML_CTX_TRANSITION_FOUND;

				/* states that are directly targeted (complete as entry-set later) */
				_targetSet.insert(transition->target.begin(), transition->target.end());

				/* lazily initialize exit set */
				if (transition->exitSet.first == 0 && transition->exitSet.second == 0) {
//                    DOMElement* tmp = getTransitionDomain(transition->element, _scxml);
//                    State* domain1 = tmp == NULL ? NULL : (State*)tmp->getUserData(X("uscxmlState"));
//                    uint32_t domain2 = getTransitionDomain(transition);
//                    assert(domain1 == NULL ? domain2 == std::numeric_limits<uint32_t>::max() : domain1->documentOrder == domain2);

//                    std::pair<uint32_t, uint32_t> orig = getExitSetCached(transition->element, _scxml);
					transition->exitSet = getExitSet(transition);
//                    assert(transition->exitSet == orig);
				}

				/* states that will be left */
				for (auto config : _configuration) {
					if (config->documentOrder >= transition->exitSet.first && config->documentOrder <= transition->exitSet.second) {
						_exitSet.insert(config);
					}
				}
				_transSet.insert(transition);

				// break and exit loop if we are at the end
				if (stateIter == _configurationPostFix.end())
					break;

				/* move to next possible state that can have optimally enabled transitions */
				auto nextIter = stateIter;
				nextIter++; // advance by one
				while(nextIter != _configurationPostFix.end() && *nextIter == (*stateIter)->parent) {
					// advance until we found a non-ancestor
					nextIter++;
					stateIter++;
				}

				break; // next state
			}
		}
//        std::cout << "." << iters << std::flush;
	}

	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) {
#if 1
								_entrySet.insert(target->ancestors.begin(), target->ancestors.end());
#else
								State* anc = target->parent;
								while(anc != NULL && _entrySet.find(anc) == _entrySet.end()) {
									_entrySet.insert(anc);
									anc = anc->parent;
								}
#endif
							}
						}
						_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
#if 1
						_entrySet.insert(target->ancestors.begin(), target->ancestors.end());
#else
						State* anc = target->parent;
						while(anc != NULL && anc != state) {
							_entrySet.insert(anc);
							anc = anc->parent;
						}
#endif
					}
				}
				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;
					}
				}

				// completion of a compound maybe multiple states via initial attribute
				_entrySet.insert(state->completion.begin(), state->completion.end());

				/* deep completion */
				{
					BENCHMARK("add descendants compound deep completion");
					for (auto completion : state->completion) {

						if (std::binary_search(state->children.begin(), state->children.end(), completion))
							continue;

						// add deep completions ancestors
#if 1
						_entrySet.insert(completion->ancestors.begin(), completion->ancestors.end());
#else
						State* anc = completion->parent;
						while(anc != NULL && anc != state) {
							_entrySet.insert(anc);
							anc = anc->parent;
						}
#endif
					}
				}
				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_CALLBACK2(monitors, beforeExitingState, state->name, 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);
			_configurationPostFix.erase(state);
			USCXML_MONITOR_CALLBACK2(monitors, afterExitingState, state->name, 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_CALLBACK2(monitors, beforeEnteringState, state->name, state->element);

			_configuration.insert(state);
			_configurationPostFix.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_CALLBACK2(monitors, afterEnteringState, state->name, 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) {
							if (isInFinal(anc)) {
								_callbacks->raiseDoneEvent(anc->element, anc->doneData);
							} else {
								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();
		}
	}
}

std::pair<uint32_t, uint32_t> LargeMicroStep::getExitSet(const Transition* transition) {
	if (_exitSetCache.find(transition->postFixOrder) == _exitSetCache.end()) {
		std::pair<uint32_t, uint32_t> statesToExit;
		uint32_t domain = getTransitionDomain(transition);
		if (domain == std::numeric_limits<uint32_t>::max())
			return statesToExit;

		State* domainState = _states[domain];

		// start of exit set
		statesToExit.first = domainState->documentOrder + 1; // do not include domain itself

		// end of exit set
		XERCESC_NS::DOMElement* sibling = domainState->element->getNextElementSibling();
		while(sibling && !isState(sibling))
			sibling = sibling->getNextElementSibling();
		if (sibling) {
			State* siblingState = (State*)sibling->getUserData(X("uscxmlState"));
			statesToExit.second = siblingState->documentOrder - 1;
		} else {
			statesToExit.second = _states.size() - 1;
		}
		_exitSetCache[transition->postFixOrder] = statesToExit;
		return statesToExit;
	}
	return _exitSetCache[transition->postFixOrder];
}

uint32_t LargeMicroStep::getTransitionDomain(const Transition* transition) {
	if (transition->target.size() == 0)
		return std::numeric_limits<uint32_t>::max();

	bool internal = (HAS_ATTR(transition->element, kXMLCharType) ? ATTR(transition->element, kXMLCharType) == "internal" : false);
	if (internal && USCXML_STATE_MASK(transition->source->type) == USCXML_STATE_COMPOUND) {
		for (auto target : transition->target) {
			if (target->ancestors.find(transition->source) == target->ancestors.end()) {
				goto BREAK_LOOP;
			}
		}
		return transition->source->documentOrder;
	}
BREAK_LOOP:

	// find LCCA
	uint32_t ancestor = std::numeric_limits<uint32_t>::max();

	// reverse walk up!
	for(auto ancIter = transition->source->ancestors.rbegin(); ancIter != transition->source->ancestors.rend(); ancIter++) {
		State* anc = *ancIter;

		// LCCA has to be a compound
		if (!(USCXML_STATE_MASK(anc->type) == USCXML_STATE_COMPOUND))
			continue;

		// that contains all states
		for (auto target : transition->target) {
			if (target->ancestors.find(anc) == target->ancestors.end()) {
				goto NEXT_ANCESTOR;
			}
		}
		ancestor = anc->documentOrder;
		break;
NEXT_ANCESTOR:
		;
	}

	// none found - take uppermost root as ancestor
	if (ancestor == std::numeric_limits<uint32_t>::max())
		return 0;
	return ancestor;
}

}