nodestack: add print_may_read_from()
[model-checker.git] / nodestack.cc
1 #include "nodestack.h"
2 #include "action.h"
3 #include "common.h"
4 #include "model.h"
5
6 /**
7  * @brief Node constructor
8  *
9  * Constructs a single Node for use in a NodeStack. Each Node is associated
10  * with exactly one ModelAction (exception: the first Node should be created
11  * as an empty stub, to represent the first thread "choice") and up to one
12  * parent.
13  *
14  * @param act The ModelAction to associate with this Node. May be NULL.
15  * @param par The parent Node in the NodeStack. May be NULL if there is no
16  * parent.
17  * @param nthreads The number of threads which exist at this point in the
18  * execution trace.
19  */
20 Node::Node(ModelAction *act, Node *par, int nthreads)
21         : action(act),
22         parent(par),
23         num_threads(nthreads),
24         explored_children(num_threads),
25         backtrack(num_threads),
26         numBacktracks(0),
27         may_read_from()
28 {
29         if (act)
30                 act->set_node(this);
31 }
32
33 /** @brief Node desctructor */
34 Node::~Node()
35 {
36         if (action)
37                 delete action;
38 }
39
40 /** Prints debugging info for the ModelAction associated with this Node */
41 void Node::print()
42 {
43         if (action)
44                 action->print();
45         else
46                 printf("******** empty action ********\n");
47 }
48
49 /** @brief Prints info about may_read_from set */
50 void Node::print_may_read_from()
51 {
52         readfrom_set_t::iterator it;
53         for (it = may_read_from.begin(); it != may_read_from.end(); it++)
54                 (*it)->print();
55 }
56
57 /**
58  * Checks if the Thread associated with this thread ID has been explored from
59  * this Node already.
60  * @param tid is the thread ID to check
61  * @return true if this thread choice has been explored already, false
62  * otherwise
63  */
64 bool Node::has_been_explored(thread_id_t tid)
65 {
66         int id = id_to_int(tid);
67         return explored_children[id];
68 }
69
70 /**
71  * Checks if the backtracking set is empty.
72  * @return true if the backtracking set is empty
73  */
74 bool Node::backtrack_empty()
75 {
76         return numBacktracks == 0;
77 }
78
79 /**
80  * Mark the appropriate backtracking infromation for exploring a thread choice.
81  * @param act The ModelAction to explore
82  */
83 void Node::explore_child(ModelAction *act)
84 {
85         explore(act->get_tid());
86 }
87
88 /**
89  * Records a backtracking reference for a thread choice within this Node.
90  * Provides feedback as to whether this thread choice is already set for
91  * backtracking.
92  * @return false if the thread was already set to be backtracked, true
93  * otherwise
94  */
95 bool Node::set_backtrack(thread_id_t id)
96 {
97         int i = id_to_int(id);
98         if (backtrack[i])
99                 return false;
100         backtrack[i] = true;
101         numBacktracks++;
102         return true;
103 }
104
105 thread_id_t Node::get_next_backtrack()
106 {
107         /* TODO: find next backtrack */
108         unsigned int i;
109         for (i = 0; i < backtrack.size(); i++)
110                 if (backtrack[i] == true)
111                         break;
112         if (i >= backtrack.size())
113                 return THREAD_ID_T_NONE;
114         backtrack[i] = false;
115         numBacktracks--;
116         return int_to_id(i);
117 }
118
119 bool Node::is_enabled(Thread *t)
120 {
121         return id_to_int(t->get_id()) < num_threads;
122 }
123
124 /**
125  * Add an action to the may_read_from set.
126  * @param act is the action to add
127  */
128 void Node::add_read_from(const ModelAction *act)
129 {
130         may_read_from.push_back(act);
131 }
132
133 void Node::explore(thread_id_t tid)
134 {
135         int i = id_to_int(tid);
136         if (backtrack[i]) {
137                 backtrack[i] = false;
138                 numBacktracks--;
139         }
140         explored_children[i] = true;
141 }
142
143 static void clear_node_list(node_list_t *list, node_list_t::iterator start,
144                                                node_list_t::iterator end)
145 {
146         node_list_t::iterator it;
147
148         for (it = start; it != end; it++)
149                 delete (*it);
150         list->erase(start, end);
151 }
152
153 NodeStack::NodeStack()
154         : total_nodes(0)
155 {
156         node_list.push_back(new Node());
157         total_nodes++;
158         iter = node_list.begin();
159 }
160
161 NodeStack::~NodeStack()
162 {
163         clear_node_list(&node_list, node_list.begin(), node_list.end());
164 }
165
166 void NodeStack::print()
167 {
168         node_list_t::iterator it;
169         printf("............................................\n");
170         printf("NodeStack printing node_list:\n");
171         for (it = node_list.begin(); it != node_list.end(); it++) {
172                 if (it == this->iter)
173                         printf("vvv following action is the current iterator vvv\n");
174                 (*it)->print();
175         }
176         printf("............................................\n");
177 }
178
179 ModelAction * NodeStack::explore_action(ModelAction *act)
180 {
181         DBG();
182
183         ASSERT(!node_list.empty());
184
185         if (get_head()->has_been_explored(act->get_tid())) {
186                 iter++;
187                 return (*iter)->get_action();
188         }
189
190         /* Diverging from previous execution; clear out remainder of list */
191         node_list_t::iterator it = iter;
192         it++;
193         clear_node_list(&node_list, it, node_list.end());
194
195         /* Record action */
196         get_head()->explore_child(act);
197         node_list.push_back(new Node(act, get_head(), model->get_num_threads()));
198         total_nodes++;
199         iter++;
200         return NULL;
201 }
202
203 Node * NodeStack::get_head()
204 {
205         if (node_list.empty())
206                 return NULL;
207         return *iter;
208 }
209
210 Node * NodeStack::get_next()
211 {
212         node_list_t::iterator it = iter;
213         if (node_list.empty()) {
214                 DEBUG("Empty\n");
215                 return NULL;
216         }
217         it++;
218         if (it == node_list.end()) {
219                 DEBUG("At end\n");
220                 return NULL;
221         }
222         return *it;
223 }
224
225 void NodeStack::reset_execution()
226 {
227         iter = node_list.begin();
228 }