#ifndef SIMGRID_MC_UDPOR_GLOBAL_HPP
#define SIMGRID_MC_UDPOR_GLOBAL_HPP
+#include "src/mc/api/State.hpp"
+
#include <iostream>
+#include <optional>
#include <queue>
+#include <set>
#include <string_view>
/* TODO: many method declared in this module are not implemented */
-namespace simgrid::mc {
+namespace simgrid::mc::udpor {
class UnfoldingEvent;
-using EventSet = std::deque<UnfoldingEvent*>;
+class Configuration;
+using StateHandle = uint64_t;
+
+class EventSet {
+private:
+ std::set<UnfoldingEvent*> events_;
+ explicit EventSet(std::set<UnfoldingEvent*>&& raw_events) : events_(raw_events) {}
-class EvtSetTools {
public:
- static bool contains(const EventSet& events, const UnfoldingEvent* e);
- static UnfoldingEvent* find(const EventSet& events, const UnfoldingEvent* e);
- static void subtract(EventSet& events, EventSet const& otherSet);
- static bool depends(const EventSet& events, const EventSet& otherSet);
- static bool isEmptyIntersection(EventSet evtS1, EventSet evtS2);
- static EventSet makeUnion(const EventSet& s1, const EventSet& s2);
- static void pushBack(EventSet& events, UnfoldingEvent* e);
- static void remove(EventSet& events, UnfoldingEvent* e);
- static EventSet minus(EventSet events, UnfoldingEvent* e);
- static EventSet plus(EventSet events, UnfoldingEvent* e);
+ EventSet() = default;
+ EventSet(const EventSet&) = default;
+ EventSet& operator=(const EventSet&) = default;
+ EventSet& operator=(EventSet&&) = default;
+ EventSet(EventSet&&) = default;
+
+ inline auto begin() const { return this->events_.begin(); }
+ inline auto end() const { return this->events_.end(); }
+
+ void remove(UnfoldingEvent* e);
+ void subtract(const EventSet& other);
+ void subtract(const Configuration& other);
+ EventSet subtracting(UnfoldingEvent* e) const;
+ EventSet subtracting(const EventSet& e) const;
+ EventSet subtracting(const Configuration* e) const;
+
+ void insert(UnfoldingEvent* e);
+ void form_union(const EventSet&);
+ void form_union(const Configuration&);
+ EventSet make_union(UnfoldingEvent* e) const;
+ EventSet make_union(const EventSet&) const;
+ EventSet make_union(const Configuration& e) const;
+
+ size_t size() const;
+ bool empty() const;
+ bool contains(UnfoldingEvent* e) const;
+ bool is_subset_of(const EventSet& other) const;
};
struct s_evset_in_t {
class Configuration {
public:
- EventSet events_;
- EventSet maxEvent; // Events recently added to events_
- EventSet actorMaxEvent; // maximal events of the actors in current configuration
- UnfoldingEvent* lastEvent; // The last added event
+ Configuration() = default;
+ Configuration(const Configuration&) = default;
+ Configuration& operator=(Configuration const&) = default;
+ Configuration(Configuration&&) = default;
- Configuration plus_config(UnfoldingEvent*) const;
- void createEvts(Configuration C, EventSet& result, const std::string& trans_tag, s_evset_in_t ev_sets, bool chk,
- UnfoldingEvent* immPreEvt);
- void updateMaxEvent(UnfoldingEvent*); // update maximal events of the configuration and actors
- UnfoldingEvent* findActorMaxEvt(int actorId); // find maximal event of a Actor whose id = actorId
+ inline auto begin() const { return this->events_.begin(); }
+ inline auto end() const { return this->events_.end(); }
+ inline const EventSet& get_events() const { return this->events_; }
+ inline const EventSet& get_maximal_events() const { return this->max_events_; }
- UnfoldingEvent* findTestedComm(const UnfoldingEvent* testEvt); // find comm tested by action testTrans
+ void add_event(UnfoldingEvent*);
+ UnfoldingEvent* get_latest_event() const;
- Configuration() = default;
- Configuration(const Configuration&) = default;
- Configuration& operator=(Configuration const&) = default;
- Configuration(Configuration&&) = default;
+private:
+ /**
+ * @brief The most recent event added to the configuration
+ */
+ UnfoldingEvent* newest_event = nullptr;
+ EventSet events_;
+
+ /**
+ * The <-maxmimal events of the configuration. These are
+ * dynamically adjusted as events are added to the configuration
+ *
+ * @invariant: Each event that is part of this set is
+ *
+ * 1. a <-maxmimal event of the configuration, in the sense that
+ * there is no event in the configuration that is "greater" than it.
+ * In UDPOR terminology, each event does not "cause" another event
+ *
+ * 2. contained in the set of events `events_` which comprise
+ * the configuration
+ */
+ EventSet max_events_;
+
+private:
+ void recompute_maxmimal_events(UnfoldingEvent* new_event);
};
class UnfoldingEvent {
public:
- UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& causes, int sid = -1);
- UnfoldingEvent(const UnfoldingEvent&) = default;
+ UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes,
+ StateHandle sid);
+ UnfoldingEvent(unsigned int nb_events, std::string const& trans_tag, EventSet const& immediate_causes);
+ UnfoldingEvent(const UnfoldingEvent&) = default;
UnfoldingEvent& operator=(UnfoldingEvent const&) = default;
UnfoldingEvent(UnfoldingEvent&&) = default;
- EventSet getHistory() const;
-
- bool isConflict(UnfoldingEvent* event, UnfoldingEvent* otherEvent) const;
- bool concernSameComm(const UnfoldingEvent* event, const UnfoldingEvent* otherEvent) const;
-
- // check otherEvent is in my history ?
- bool inHistory(UnfoldingEvent* otherEvent) const;
+ EventSet get_history() const;
+ bool in_history(const UnfoldingEvent* otherEvent) const;
- bool isImmediateConflict1(UnfoldingEvent* evt, UnfoldingEvent* otherEvt) const;
+ bool conflicts_with(const UnfoldingEvent* otherEvent) const;
+ bool conflicts_with(const Configuration& config) const;
+ bool immediately_conflicts_with(const UnfoldingEvent* otherEvt) const;
- bool conflictWithConfig(UnfoldingEvent* event, Configuration const& config) const;
bool operator==(const UnfoldingEvent&) const { return false; };
- void print() const;
- inline int get_state_id() const { return state_id; }
- inline void set_state_id(int sid) { state_id = sid; }
-
- inline std::string get_transition_tag() const { return transition_tag; }
- inline void set_transition_tag(std::string_view tr_tag) { transition_tag = tr_tag; }
+ inline StateHandle get_state_id() const { return state_id; }
+ inline void set_state_id(StateHandle sid) { state_id = sid; }
private:
- EventSet causes; // used to store directed ancestors of event e
int id = -1;
- int state_id{-1};
- std::string transition_tag{""}; // The tag of the last transition that lead to creating the event
- bool transition_is_IReceive(const UnfoldingEvent* testedEvt, const UnfoldingEvent* SdRcEvt) const;
- bool transition_is_ISend(const UnfoldingEvent* testedEvt, const UnfoldingEvent* SdRcEvt) const;
- bool check_tr_concern_same_comm(bool& chk1, bool& chk2, UnfoldingEvent* evt1, UnfoldingEvent* evt2) const;
+
+ /**
+ * @brief The "immediate" causes of this event.
+ *
+ * An event `e` is an immediate cause of an event `e'` if
+ *
+ * 1. e < e'
+ * 2. There is no event `e''` in E such that
+ * `e < e''` and `e'' < e'`
+ *
+ * Intuitively, an immediate cause "happened right before"
+ * this event was executed. It is sufficient to store
+ * only the immediate causes of any event `e`, as any indirect
+ * causes of that event would either be an indirect cause
+ * or an immediate cause of the immediate causes of `e`, and
+ * so on.
+ */
+ EventSet immediate_causes;
+ StateHandle state_id = 0ul;
+};
+
+class StateManager {
+private:
+ using Handle = StateHandle;
+
+ Handle current_handle_ = 1ul;
+ std::unordered_map<Handle, std::unique_ptr<State>> state_map_;
+
+public:
+ Handle record_state(std::unique_ptr<State>);
+ std::optional<std::reference_wrapper<State>> get_state(Handle);
};
-} // namespace simgrid::mc
+
+} // namespace simgrid::mc::udpor
#endif
