model: add variable arguments for bug messages
[model-checker.git] / cyclegraph.h
1 /**
2  * @file cyclegraph.h
3  * @brief Data structure to track ordering constraints on modification order
4  *
5  * Used to determine whether a total order exists that satisfies the ordering
6  * constraints.
7  */
8
9 #ifndef __CYCLEGRAPH_H__
10 #define __CYCLEGRAPH_H__
11
12 #include <inttypes.h>
13 #include <stdio.h>
14
15 #include "hashtable.h"
16 #include "config.h"
17 #include "mymemory.h"
18 #include "stl-model.h"
19
20 class Promise;
21 class CycleNode;
22 class ModelAction;
23
24 typedef ModelVector<const Promise *> promise_list_t;
25
26 /** @brief A graph of Model Actions for tracking cycles. */
27 class CycleGraph {
28  public:
29         CycleGraph();
30         ~CycleGraph();
31
32         template <typename T, typename U>
33         bool addEdge(const T *from, const U *to);
34
35         template <typename T>
36         void addRMWEdge(const T *from, const ModelAction *rmw);
37
38         bool checkForCycles() const;
39         bool checkPromise(const ModelAction *from, Promise *p) const;
40
41         template <typename T, typename U>
42         bool checkReachable(const T *from, const U *to) const;
43
44         void startChanges();
45         void commitChanges();
46         void rollbackChanges();
47 #if SUPPORT_MOD_ORDER_DUMP
48         void dumpNodes(FILE *file) const;
49         void dumpGraphToFile(const char *filename) const;
50
51         void dot_print_node(FILE *file, const ModelAction *act);
52         template <typename T, typename U>
53         void dot_print_edge(FILE *file, const T *from, const U *to, const char *prop);
54 #endif
55
56         bool resolvePromise(const Promise *promise, ModelAction *writer);
57
58         SNAPSHOTALLOC
59  private:
60         bool addNodeEdge(CycleNode *fromnode, CycleNode *tonode);
61         void putNode(const ModelAction *act, CycleNode *node);
62         void putNode(const Promise *promise, CycleNode *node);
63         void erasePromiseNode(const Promise *promise);
64         CycleNode * getNode(const ModelAction *act);
65         CycleNode * getNode(const Promise *promise);
66         CycleNode * getNode_noCreate(const ModelAction *act) const;
67         CycleNode * getNode_noCreate(const Promise *promise) const;
68         bool mergeNodes(CycleNode *node1, CycleNode *node2);
69
70         HashTable<const CycleNode *, const CycleNode *, uintptr_t, 4, model_malloc, model_calloc, model_free> *discovered;
71         ModelVector<const CycleNode *> * queue;
72
73
74         /** @brief A table for mapping ModelActions to CycleNodes */
75         HashTable<const ModelAction *, CycleNode *, uintptr_t, 4> actionToNode;
76         /** @brief A table for mapping Promises to CycleNodes */
77         HashTable<const Promise *, CycleNode *, uintptr_t, 4> promiseToNode;
78
79 #if SUPPORT_MOD_ORDER_DUMP
80         SnapVector<CycleNode *> nodeList;
81 #endif
82
83         bool checkReachable(const CycleNode *from, const CycleNode *to) const;
84
85         /** @brief A flag: true if this graph contains cycles */
86         bool hasCycles;
87         bool oldCycles;
88
89         SnapVector<CycleNode *> rollbackvector;
90         SnapVector<CycleNode *> rmwrollbackvector;
91 };
92
93 /**
94  * @brief A node within a CycleGraph; corresponds either to one ModelAction or
95  * to a promised future value
96  */
97 class CycleNode {
98  public:
99         CycleNode(const ModelAction *act);
100         CycleNode(const Promise *promise);
101         bool addEdge(CycleNode *node);
102         CycleNode * getEdge(unsigned int i) const;
103         unsigned int getNumEdges() const;
104         CycleNode * getBackEdge(unsigned int i) const;
105         unsigned int getNumBackEdges() const;
106         CycleNode * removeEdge();
107         CycleNode * removeBackEdge();
108
109         bool setRMW(CycleNode *);
110         CycleNode * getRMW() const;
111         void clearRMW() { hasRMW = NULL; }
112         const ModelAction * getAction() const { return action; }
113         const Promise * getPromise() const { return promise; }
114         bool is_promise() const { return !action; }
115         void resolvePromise(const ModelAction *writer);
116
117         SNAPSHOTALLOC
118  private:
119         /** @brief The ModelAction that this node represents */
120         const ModelAction *action;
121
122         /** @brief The promise represented by this node; only valid when action
123          * is NULL */
124         const Promise *promise;
125
126         /** @brief The edges leading out from this node */
127         SnapVector<CycleNode *> edges;
128
129         /** @brief The edges leading into this node */
130         SnapVector<CycleNode *> back_edges;
131
132         /** Pointer to a RMW node that reads from this node, or NULL, if none
133          * exists */
134         CycleNode *hasRMW;
135 };
136
137 #endif /* __CYCLEGRAPH_H__ */