Automata.cpp 11.1 KB
Newer Older
Anirudh Kaushik's avatar
Anirudh Kaushik committed
1
2
3
4
5
6
#include "Automata.h"

using namespace scpar;

/// Node class.

rmrf's avatar
rmrf committed
7
Node::Node() : _id(-1) {}
Anirudh Kaushik's avatar
Anirudh Kaushik committed
8

rmrf's avatar
rmrf committed
9
Node::Node(int i) : _id(i) {}
Anirudh Kaushik's avatar
Anirudh Kaushik committed
10

rmrf's avatar
rmrf committed
11
int Node::getId() { return _id; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
12

rmrf's avatar
rmrf committed
13
14
15
void Node::addSuccessor(Node *s) {
  _succs.insert(Node::connectPairType(s->getId(), s));
  s->addPredecessor(this);
Anirudh Kaushik's avatar
Anirudh Kaushik committed
16
17
}

rmrf's avatar
rmrf committed
18
19
void Node::addPredecessor(Node *p) {
  _preds.insert(Node::connectPairType(p->getId(), p));
Anirudh Kaushik's avatar
Anirudh Kaushik committed
20
21
}

rmrf's avatar
rmrf committed
22
vector<int> Node::getSuccessors(int fromId) {
Anirudh Kaushik's avatar
Anirudh Kaushik committed
23

rmrf's avatar
rmrf committed
24
  vector<int> tmpSuccs;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
25

rmrf's avatar
rmrf committed
26
27
28
29
30
31
32
  for (Node::connectMapType::iterator it = _succs.begin(), eit = _succs.end();
       it != eit; it++) {
    //  if(it->first == fromId) {
    tmpSuccs.push_back(it->first);
    //  }
  }
  return tmpSuccs;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
33
34
}

rmrf's avatar
rmrf committed
35
vector<int> Node::getPredecessors(int toId) {
Anirudh Kaushik's avatar
Anirudh Kaushik committed
36

rmrf's avatar
rmrf committed
37
  vector<int> tmpPreds;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
38

rmrf's avatar
rmrf committed
39
40
41
42
43
44
45
  for (Node::connectMapType::iterator it = _preds.begin(), eit = _preds.end();
       it != eit; it++) {
    //  if(it->first == fromId) {
    tmpPreds.push_back(it->first);
    //  }
  }
  return tmpPreds;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
46
47
}

rmrf's avatar
rmrf committed
48
49
50
51
52
53
54
55
56
57
58
59
60
void Node::dump(raw_ostream &os, int tabn) {
  os << "Node " << getId() << "\n";
  os << "  preds: ";
  for (Node::connectMapType::iterator it = _preds.begin(), eit = _preds.end();
       it != eit; it++) {
    os << it->first << " ";
  }
  os << "\n  succs: ";
  for (Node::connectMapType::iterator it = _succs.begin(), eit = _succs.end();
       it != eit; it++) {
    os << it->first << " ";
  }
  os << "\n";
Anirudh Kaushik's avatar
Anirudh Kaushik committed
61
62
63
64
}

////////////////////////////////////////////////////////////////////////////////////////
/// Edge class.
rmrf's avatar
rmrf committed
65
Edge::Edge(Node *f, Node *t) : _id(-1), _from(f), _to(t) {}
Anirudh Kaushik's avatar
Anirudh Kaushik committed
66

rmrf's avatar
rmrf committed
67
Edge::Edge(Node *f, Node *t, int i) : _id(i), _from(f), _to(t) {}
Anirudh Kaushik's avatar
Anirudh Kaushik committed
68

rmrf's avatar
rmrf committed
69
70
void Edge::updateSuspensionTime(timePairType timePair) {
  _timeAdvanceVector.push_back(timePair);
Anirudh Kaushik's avatar
Anirudh Kaushik committed
71
72
}

rmrf's avatar
rmrf committed
73
int Edge::getId() { return _id; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
74

rmrf's avatar
rmrf committed
75
76
void Edge::dump(raw_ostream &os, int tabn) {
  os << "Edge (" << _from->getId() << "," << _to->getId() << ")\n";
Anirudh Kaushik's avatar
Anirudh Kaushik committed
77
78
}

rmrf's avatar
rmrf committed
79
int Edge::getToId() { return _to->getId(); }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
80

rmrf's avatar
rmrf committed
81
int Edge::getFromId() { return _from->getId(); }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
82

rmrf's avatar
rmrf committed
83
84
Edge::timeAdvanceVectorType Edge::getTimeAdvanceVector() {
  return _timeAdvanceVector;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
85
86
87
88
89
}

////////////////////////////////////////////////////////////////////////////////////////
/// Graph class

rmrf's avatar
rmrf committed
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
135
136
137
138
139
140
141
142
143
144
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
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
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
Graph::Graph() : _nNodes(0), _nEdges(0) {}

Node *Graph::addNode() {
  Node *n = new Node(_nNodes);

  _nodeMap.insert(Graph::nodePairType(_nNodes, n));
  _nodeVector.push_back(n);
  _nodeIDVector.push_back(_nNodes);
  ++_nNodes;
  return n;
}

Node *Graph::addNode(int id) {
  Node *n = new Node(id);

  _nodeMap.insert(Graph::nodePairType(id, n));
  _nodeVector.push_back(n);
  _nodeIDVector.push_back(id);
  ++_nNodes;
  return n;
}

Edge *Graph::addEdge(Node *f, Node *t) {
  Edge *e = new Edge(f, t, _nEdges);

  _edgeMap.insert(Graph::edgePairType(_nEdges, e));

  // Update preds and succs in nodes.
  f->addSuccessor(t);
  ++_nEdges;

  // Insert in adjacency list.
  _adjList.insert(
      Graph::adjPairType(Graph::twoNodePairType(f->getId(), t->getId()), e));
  return e;
}

Edge *Graph::addEdge(int fID, int tID) {
  Node *f, *t;

  if (_nodeMap.find(fID) != _nodeMap.end()) {
    nodeMapType::iterator nodeFound = _nodeMap.find(fID);
    f = nodeFound->second;
  } else {
    f = new Node(fID);
    _nodeMap.insert(nodePairType(fID, f));
    _nodeVector.push_back(f);
    _nodeIDVector.push_back(fID);
    _nNodes++;
  }
  if (_nodeMap.find(tID) != _nodeMap.end()) {
    nodeMapType::iterator nodeFound = _nodeMap.find(tID);
    t = nodeFound->second;
  } else {
    t = new Node(tID);
    _nodeMap.insert(nodePairType(tID, t));
    _nodeVector.push_back(t);
    _nodeIDVector.push_back(tID);
    _nNodes++;
  }
  Edge *e = new Edge(f, t, _nEdges);

  _edgeMap.insert(Graph::edgePairType(_nEdges, e));

  // Update preds and succs in nodes.
  f->addSuccessor(t);
  ++_nEdges;

  // Insert in adjacency list.
  _adjList.insert(
      Graph::adjPairType(Graph::twoNodePairType(f->getId(), t->getId()), e));
  return e;
}

int Graph::getNodeID(Node *n) {
  for (nodeMapType::iterator it = _nodeMap.begin(), eit = _nodeMap.end();
       it != eit; it++) {
    if (n == it->second) {
      return it->first;
    }
  }
  return -1;
}

int Graph::getEdgeID(Edge *e) {
  for (edgeMapType::iterator it = _edgeMap.begin(), eit = _edgeMap.end();
       it != eit; it++) {
    if (it->second == e) {
      return it->first;
    }
  }
  return -1;
}

int Graph::getEdgeID(Node *f, Node *t) {
  if (_adjList.find(twoNodePairType(f->getId(), t->getId())) !=
      _adjList.end()) {
    adjMapType::iterator edgeFound =
        _adjList.find(twoNodePairType(f->getId(), t->getId()));
    return getEdgeID(edgeFound->second);
  }
  return -1;
}

int Graph::getEdgeID(int fID, int tID) {
  if (_adjList.find(twoNodePairType(fID, tID)) != _adjList.end()) {
    adjMapType::iterator edgeFound = _adjList.find(twoNodePairType(fID, tID));
    return getEdgeID(edgeFound->second);
  }
  return -1;
}

Edge *Graph::getEdge(int f, int t) {
  Graph::adjMapType::iterator fit = _adjList.find(Graph::twoNodePairType(f, t));
  if (fit == _adjList.end()) {
    return NULL;
  }
  return fit->second;
}

Edge *Graph::getEdge(Node *f, Node *t) {
  Graph::adjMapType::iterator fit =
      _adjList.find(Graph::twoNodePairType(f->getId(), t->getId()));
  if (fit == _adjList.end()) {
    return NULL;
  }

  return fit->second;
}

Node *Graph::getNode(int nodeID) {
  if (_nodeMap.find(nodeID) != _nodeMap.end()) {
    nodeMapType::iterator nodeFound = _nodeMap.find(nodeID);
    return nodeFound->second;
  }
  return NULL;
}

vector<Edge *> Graph::getEdgesFromSource(int sourceID) {
  vector<Edge *> edges;
  for (adjMapType::iterator it = _adjList.begin(), eit = _adjList.end();
       it != eit; it++) {
    twoNodePairType nodePair = it->first;

    if (nodePair.first == sourceID) {
      edges.push_back(it->second);
    }
  }
  return edges;
}

vector<Edge *> Graph::getEdgesFromDest(int destID) {
  vector<Edge *> edges;
  for (adjMapType::iterator it = _adjList.begin(), eit = _adjList.end();
       it != eit; it++) {
    twoNodePairType nodePair = it->first;

    if (nodePair.second == destID) {
      edges.push_back(it->second);
    }
  }
  return edges;
}

vector<Edge *> Graph::getEdgesFromSource(Node *sourceNode) {
  for (nodeMapType::iterator it = _nodeMap.begin(), eit = _nodeMap.end();
       it != eit; it++) {
    if (it->second == sourceNode) {
      getEdgesFromSource(it->first);
    }
  }
}

vector<Edge *> Graph::getEdgesFromDest(Node *destNode) {
  for (nodeMapType::iterator it = _nodeMap.begin(), eit = _nodeMap.end();
       it != eit; it++) {
    if (it->second == destNode) {
      getEdgesFromDest(it->first);
    }
  }
}

void Graph::dump(raw_ostream &os, int tabn) {

  // Print all nodes.
  os << "Node map: " << _nNodes << "\n";
  for (Graph::nodeMapType::iterator it = _nodeMap.begin(), eit = _nodeMap.end();
       it != eit; it++) {

    os << it->first << " " << it->second << " ";
    it->second->dump(os, tabn++);
  }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
282

rmrf's avatar
rmrf committed
283
284
285
286
287
288
289
290
  // Print all Edges.
  os << "Edge map: " << _nEdges << "\n";
  for (Graph::edgeMapType::iterator it = _edgeMap.begin(), eit = _edgeMap.end();
       it != eit; it++) {

    os << it->first << " " << it->second << " ";
    //    it->second->dump(os, tabn++);
  }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
291

rmrf's avatar
rmrf committed
292
293
294
295
296
  os << "Adjacency list: " << _adjList.size() << "\n";
  for (Graph::adjMapType::iterator it = _adjList.begin(), eit = _adjList.end();
       it != eit; it++) {
    Graph::twoNodePairType p = it->first;
    Edge *e = it->second;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
297

rmrf's avatar
rmrf committed
298
299
300
301
302
303
304
305
306
307
    os << "Edge (" << p.first << "," << p.second << ") \n";
    os << "TimeAdvance : \n";
    Edge::timeAdvanceVectorType timeAdvanceVector = e->getTimeAdvanceVector();
    os << "\n Size of timeAdvanceVector : " << timeAdvanceVector.size();
    for (unsigned int i = 0; i < timeAdvanceVector.size(); i++) {
      Edge::timePairType timePair = timeAdvanceVector.at(i);
      os << " " << timePair.first << " " << timePair.second << "\n";
    }
    //    e->dump(os,tabn++);
  }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
308
309
}

rmrf's avatar
rmrf committed
310
void Graph::dumpSauto(raw_ostream &os, int tabn) {
Anirudh Kaushik's avatar
Anirudh Kaushik committed
311

rmrf's avatar
rmrf committed
312
  LangOptions LO;
Anirudh Kaushik's avatar
Anirudh Kaushik committed
313

rmrf's avatar
rmrf committed
314
315
  LO.CPlusPlus = true;
  PrintingPolicy Policy(LO);
Anirudh Kaushik's avatar
Anirudh Kaushik committed
316

rmrf's avatar
rmrf committed
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
  for (Graph::adjMapType::iterator it = _adjList.begin(), eit = _adjList.end();
       it != eit; it++) {
    Graph::twoNodePairType p = it->first;
    Edge *e = it->second;

    os << " Edge (" << p.first << ", " << p.second << ")\n";

    /*
       os<<" Transition code \n";
       vector<CFGBlock*> codeBlocks = e->getPreStmtBlks();
       for (int i = 0; i<codeBlocks.size(); i++) {
       CFGBlock* currBlock = codeBlocks.at(i);
       for(CFGBlock::iterator it = currBlock->begin(), eit = currBlock->end();
       it != eit;
       it++) {
       if(Optional <CFGStmt> cfgStmt = it->getAs<CFGStmt>()) {
       const Stmt* stmt = cfgStmt->getStmt();
       stmt->printPretty(llvm::errs(), 0, Policy, 0);
       os<<"\n";
       }
       }
       }
     */
  }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
341
342
343
344
345
346
347
348
349
350
351
}

/*
void Graph::dumpSauto(raw_ostream& os, int tabn) {

  LangOptions LO;
  LO.CPlusPlus = true;
  PrintingPolicy Policy(LO);
  unsigned int state = 0;
  bool duplicateFound;
for (Graph::adjMapType::iterator it = _adjList.begin(), eit = _adjList.end();
rmrf's avatar
rmrf committed
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
        it != eit;
        it++) {
                Graph::twoNodePairType p = it->first;
                duplicateFound = false;
                //start and final states
                os <<"\n q_s : "<<p.first<< " "<<" q_f : "<<p.second;

                for (unsigned int i = 0; i<_nodeIds.size();i++) {
                        if(p.first == _nodeIds.at(i)){
                                duplicateFound = true;
                                break;
                        }
                }
                if(duplicateFound == false) {
                        _nodeIds.push_back(p.first);
                }
                Edge *e = it->second;
                vector<CFGBlock*> pre = e->getPreStmtBlks();

                os <<"\n B_pre :";
                for (unsigned int i = 0; i<pre.size();i++) {
                        os<<pre.at(i)->getBlockID()<<" ";
                }
                vector<CFGBlock*> guard = e->getGuardBlks();
                os <<"\n Guard :";
                for (unsigned int i = 0; i<guard.size();i++) {
                        os<<guard.at(i)->getBlockID()<<" ";
                        Stmt* condition = guard.at(i)->getTerminator();

                }
                vector<CFGBlock*> post = e->getPostStmtBlks();
                os <<"\n B_post :";
                for (unsigned   int i = 0; i<post.size();i++) {
                        os<<post.at(i)->getBlockID()<<" ";
                }

                os <<"\n **************************";
        }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
390
391
392
}
*/

rmrf's avatar
rmrf committed
393
Graph::adjMapType Graph::returnAdjList() { return _adjList; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
394

rmrf's avatar
rmrf committed
395
Graph::nodeIDVector Graph::returnNodeIDs() { return _nodeIDVector; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
396

rmrf's avatar
rmrf committed
397
Graph::edgeIDVector Graph::returnEdgeIDs() { return _edgeIDVector; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
398

rmrf's avatar
rmrf committed
399
Graph::nodeVector Graph::returnNodeVector() { return _nodeVector; }
Anirudh Kaushik's avatar
Anirudh Kaushik committed
400

rmrf's avatar
rmrf committed
401
402
403
404
405
406
407
408
409
410
411
412
413
Graph::edgeVector Graph::returnEdgeVector() { return _edgeVector; }

Graph::~Graph() {
  // Responsible for cleaning everything up.
  for (Graph::nodeMapType::iterator it = _nodeMap.begin(), eit = _nodeMap.end();
       it != eit; it++) {

    delete it->second;

    //    os <<  it->first << " " << it->second;
    //    it->second->dump(os, tabn++);
  }
  _nodeMap.clear();
Anirudh Kaushik's avatar
Anirudh Kaushik committed
414

rmrf's avatar
rmrf committed
415
416
417
418
419
420
421
  // Print all Edges.
  for (Graph::edgeMapType::iterator it = _edgeMap.begin(), eit = _edgeMap.end();
       it != eit; it++) {
    delete it->second;
  }
  _edgeMap.clear();
  _adjList.clear();
Anirudh Kaushik's avatar
Anirudh Kaushik committed
422
}