XBT_DEBUG("Moving {%s} from U to G...", to_remove.to_string().c_str());
clean_up_set.form_union(to_remove);
}
- // TODO: We compute everything... but we don't actually
- // remove anything yet. This is a workaround until
- // we figure out how to deal with the fact that the previous
+
+ // TODO: We still perhaps need to
+ // figure out how to deal with the fact that the previous
// extension sets computed for past configurations
// contain events that may be removed from `U`. Perhaps
// it would be best to keep them around forever (they
// more efficient (we have to search all of `U` for such conflicts,
// and there would be no reason to search those events
// that UDPOR has marked as no longer being important)
- //
- // this->unfolding.remove(clean_up_set);
+ // For now, there appear to be no "obvious" issues (although
+ // UDPOR's behavior is often far from obvious...)
+ this->unfolding.remove(clean_up_set);
}
RecordTrace UdporChecker::get_record_trace()
if (e == nullptr) {
throw std::invalid_argument("Expected a non-null pointer to an event, but received NULL");
}
- this->global_events_.erase(e);
- this->event_handles.remove(e);
+ this->U.remove(e);
+ this->G.insert(e);
}
const UnfoldingEvent* Unfolding::insert(std::unique_ptr<UnfoldingEvent> e)
"This will result in a double free error and must be fixed.");
}
- if (auto loc = this->find_equivalent(handle); loc != this->end()) {
- // There's already an event in the unfolding that is semantically
- // equivalent. Return the handle to that event and ignore adding in
- // a duplicate event
+ // Attempt to search first for an event in `U`. If it exists, we use that event
+ // instead of `e` since it is semantically equivalent to `e` (i.e. `e` is
+ // effectively already contained in the unfolding)
+ if (auto loc = std::find_if(U.begin(), U.end(), [=](const auto e_i) { return *e_i == *handle; }); loc != U.end()) {
+ // Return the handle to that event and ignore adding in a duplicate event
return *loc;
}
+ // Then look for `e` in `G`. It's possible `e` was already constructed
+ // in the past, in which case we can simply re-use it.
+ //
+ // Note, though, that in this case we must move the event in `G` into
+ // `U`: we've inserted `e` into the unfolding, so we expect it to be in `U`
+ if (auto loc = std::find_if(G.begin(), G.end(), [=](const auto e_i) { return *e_i == *handle; }); loc != G.end()) {
+ const auto e_equiv = *loc;
+ G.remove(e_equiv);
+ U.insert(e_equiv);
+ return e_equiv;
+ }
+
+ // Otherwise `e` is truly a "new" event
+ this->U.insert(handle);
this->event_handles.insert(handle);
this->global_events_[handle] = std::move(e);
return handle;
EventSet Unfolding::get_immediate_conflicts_of(const UnfoldingEvent* e) const
{
EventSet immediate_conflicts;
- for (const auto event : *this) {
+ for (const auto event : U) {
if (event->immediately_conflicts_with(e)) {
immediate_conflicts.insert(event);
}
auto cend() const { return this->event_handles.cend(); }
size_t size() const { return this->event_handles.size(); }
bool empty() const { return this->event_handles.empty(); }
- bool contains(const UnfoldingEvent* e) const { return this->event_handles.contains(e); }
void remove(const UnfoldingEvent* e);
void remove(const EventSet& events);
*/
EventSet event_handles;
+ /**
+ * @brief: The collection of events in the unfolding that are "important"
+ */
+ EventSet U;
+
/**
* @brief The "irrelevant" portions of the unfolding that do not need to be kept
* around to ensure that UDPOR functions correctly
*
* The set `G` is another global variable maintained by the UDPOR algorithm which
* is used to keep track of all events which used to be important to UDPOR.
- *
- * @note: The current implementation does not touch the set `G`. Its use is perhaps
- * limited to debugging and/or model-checking acyclic state spaces
*/
EventSet G;
-
- auto find_equivalent(const UnfoldingEvent* e)
- {
- return std::find_if(begin(), end(), [=](const UnfoldingEvent* e_i) { return *e == *e_i; });
- }
};
} // namespace simgrid::mc::udpor
