Newer
Older
//
// Created by ghofrane on 5/4/22.
//
#include "CndfsV2.h"
#include "ModelCheckBaseMT.h"
#include <iostream>
#include <spot/twa/twagraph.hh>
#include <thread>
#include <vector>
#include <utility>
#include <spot/twa/twa.hh>
#include <bddx.h>
#include <deque>
#include <atomic>
#include <condition_variable>
#include <algorithm>
#include "misc/stacksafe.h"
#include <spot/twa/formula2bdd.hh>
#include <spot/tl/formula.hh>
#include <spot/misc/minato.hh>
#include <spot/twaalgos/contains.hh>
#include <spot/tl/contain.hh>
#include <random>
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
CndfsV2::CndfsV2(ModelCheckBaseMT *mcl, const spot::twa_graph_ptr &af, const uint16_t &nbTh) : mMcl(mcl), mAa(af),
mNbTh(nbTh) {
getInitialState();
spawnThreads();
}
CndfsV2::~CndfsV2() {
for (int i = 0; i < mNbTh; ++i) {
mlThread[i]->join();
delete mlThread[i];
}
// Liberate dynamic allocated memory for synchropnized product
for (const auto & elt : mlBuiltStates)
delete elt;
}
// Create threads
void CndfsV2::spawnThreads() {
for (int i = 0; i < mNbTh; ++i) {
mlThread[i] = new thread(threadHandler, this);
if (mlThread[i] == nullptr) {
cout << "error: pthread creation failed. " << endl;
}
}
}
void CndfsV2::threadHandler(void *context) {
((CndfsV2 *) context)->threadRun();
}
void CndfsV2::threadRun() {
uint16_t idThread = mIdThread++;
vector<myState_t *> Rp;
vector<spot::formula> ap_sog;
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
}
/*
* Build initial state of the product automata
*/
void CndfsV2::getInitialState() {
mInitStatePtr = new myState_t;
mInitStatePtr->left = mMcl->getInitialMetaState();
mInitStatePtr->right = mAa->get_init_state();
mInitStatePtr->isAcceptance = mAa->state_is_accepting(mAa->get_init_state());
mInitStatePtr->isConstructed = true;
mlBuiltStates.push_back(mInitStatePtr);
}
//this function is to build a state with list of successor initially null
myState_t *CndfsV2::buildState(myState_t *state, spot::formula tr) {
myState_t *buildStatePtr = new myState_t;
// buildStatePtr->left = getSuccessorFromSOG(state->left,tr);
// buildStatePtr->right = getSuccessorFromBA(state->right,tr);
// buildStatePtr->isAcceptance = state->right;
// buildStatePtr->isConstructed = constructed;
return buildStatePtr;
}
//std::ostream &operator<<(std::ostream &Str, myState_t *state) {
// Str << "({ Sog state= " << state->left << ", BA state= " << state->right << ", acceptance= " << state->isAcceptance
// << ", constructed= " << state->isConstructed << ", red= " << state->red << ", blue= " << state->blue << " }"
// << endl;
// int i = 0;
// for (const auto &ii: state->new_successors) {
// Str << "succ num " << i << ii.first << " with transition " << ii.second << endl;
// i++;
// }
// return Str;
//}
void CndfsV2::dfsRed(myState_t *state, vector<myState_t *> &Rp, uint8_t idThread) {
// cout << "dfsRed" << endl;
Rp.push_back(state);
// computeSuccessors(state);
for (const auto &succ: state->new_successors) {
// cout << "dfs red 1 " << succ.first->cyan[idThread]<< endl;
if (succ.first->cyan[idThread]) {
cout << "cycle detected with the thread " << unsigned(idThread) << endl;
exit(0);
}
// unvisited and not red state
if ((find(Rp.begin(), Rp.end(), state) != Rp.end()) && !succ.first->red)
dfsRed(succ.first, Rp, idThread);
}
}
/*
* Check whether a product state exists or not
*/
myState_t *CndfsV2::isStateBuilt(LDDState *sogState, const spot::twa_graph_state *spotState) {
auto compare = [sogState, spotState](myState_t *state) {
return (state->left == sogState && state->right == spotState);
};
auto result = find_if(begin(mlBuiltStates), end(mlBuiltStates), compare);
return result == end(mlBuiltStates) ? nullptr : *result;
}
//compute new successors of a product state
void CndfsV2::fireable(myState_t *state, vector<spot::formula> ap_sog, uint8_t idThread) {
if (state->succState == SuccState::done) return;
std::unique_lock lk(mMutexStatus);
if (state->succState == SuccState::doing) {
mDataCondWait.wait(lk, [state] { return state->succState == SuccState::done; });
mMutexStatus.unlock();
return;
}
state->succState = SuccState::doing;
lk.unlock();
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
auto sog_current_state = state->left;
const spot::twa_graph_state *ba_current_state = state->right;
while (!sog_current_state->isCompletedSucc());
auto p = mAa->get_dict();//avoir le dictionnaire bdd,proposition atomique
//fetch the state's atomic proposition
for (const auto & vv: sog_current_state->getMarkedPlaces(mMcl->getPlaceProposition()))
{
auto name = string(mMcl->getPlace(vv));
auto ap_state = spot::formula::ap(name);
if (p->var_map.find(ap_state) != p->var_map.end()) {
ap_sog.push_back(ap_state);
for( auto n: p->var_map)
{
if (n.first != ap_state)
{
ap_sog.push_back(spot::formula::Not(n.first));
}
}
}
}
//iterate over the successors of a current aggregate
for (const auto &elt: sog_current_state->Successors) {
auto transition = elt.second; // je récupère le numéro du transition
auto name = string(mMcl->getTransition(transition)); // récuprer le nom de la transition
auto ap_edge = spot::formula::ap(name);// récuperer la proposition atomique qui correspond à la transition
if (p->var_map.find(ap_edge) != p->var_map.end()) {
ap_sog.push_back(ap_edge);
}
spot::formula pa_sog_result = spot::formula::And(ap_sog);
// cout << "formula sog: " << pa_sog_result << endl;
//iterate over the successors of a BA state
auto ii = mAa->succ_iter(ba_current_state);
if (ii->first())
do {
auto pa_ba_result = spot::bdd_to_formula(ii->cond(), p); // from bdd to formula
if (c.contained(pa_sog_result, pa_ba_result) || c.contained(pa_ba_result, pa_sog_result))
{
std::unique_lock lk(mMutex);
if (std::find(commonTr.begin(), commonTr.end(), pa_sog_result) == commonTr.end()) {
cout << "I'm here " << unsigned (idThread) << endl;
commonTr.push_back(pa_sog_result);
}
}
} while (ii->next());
mAa->release_iter(ii);
}
state->succState = SuccState::done;
mDataCondWait.notify_all();
int i = 0 ;
//Perform the dfsBlue
void CndfsV2::dfsBlue(myState_t *state, vector<myState_t *> &Rp, uint8_t idThread, vector<spot::formula> ap_sog) {
// std::shuffle(commonTr.begin(), commonTr.end(), g);
//
{
std::unique_lock lk(mMutex);
if (commonTr.size()>0)
{
spot::formula sel_elem = commonTr[commonTr.size()-1];
cout << "hello from thread " << unsigned(idThread) << " transition " << sel_elem << " size " << commonTr.size() << endl;
commonTr.pop_back();
}
}
// myState_t* st = buildState(state,sel_elem);
// myState_t* s = isStateBuilt(st->left,st->right);
// if(s)
// {
// free(st);
// state->new_successors.push_back(make_pair(s,0));
// mlBuiltStates.push_back(st);
// state->new_successors.push_back(make_pair(st,0));
// for (const auto &succ: state->new_successors) {
// if (!succ.first->blue && !succ.first->cyan[idThread]) {
// dfsBlue(succ.first, Rp, idThread, ap_sog, commonTr);
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
// }
// }
// state->blue = true;
// if (state->isAcceptance) {
//// cout << "Acceptance state detected " << endl;
// if (state->left->isDeadLock() || state->left->isDiv()) {
// cout << "cycle detected: an aggregate with deal_lock or live_lock" << endl;
// exit(0);
// } else {
// Rp.clear();
// dfsRed(state, Rp, idThread); //looking for an accepting cycle
// bool cond;
// do {
// cond = true;
// for (auto iter = Rp.begin(); iter != Rp.end() && cond; ++iter) {
// if ((*iter)->isAcceptance && (*iter != state)) {
// if (!(*iter)->red) cond = false;
// }
// }
// } while (!cond);
//
// for (const auto &qu: Rp) // prune other dfsRed
// {
// qu->red = true;
// }
// }
// cout << "no cycle detected" << endl;
// }
// state->cyan[idThread] = false;
}
spot::bdd_dict_ptr *CndfsV2::m_dict_ptr;