GCC 4.8 build fixes: ensure all extern template declarations are in fact extern'ed...
[dyninst.git] / common / src / Node.C
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31
32 // Node class implementation
33
34 #include "Graph.h"
35 #include "Edge.h"
36 #include "Node.h"
37 #include <assert.h>
38
39 #include "common/src/NodeIterator.h"
40
41 // Nodes are quite simple; they have an Insn, an Absloc, and a set of Edges.
42
43 using namespace Dyninst;
44
45 const Address Node::INVALID_ADDR = (Address) -1;
46
47
48 void Node::addInEdge(const EdgePtr in) {
49    ins_.insert(in);
50 }
51  
52 void Node::addOutEdge(const EdgePtr out) {
53    outs_.insert(out);
54 }   
55
56 void Node::ins(NodeIterator &begin, NodeIterator &end) {
57     // Ins and outs are currently stored as sets of edges.
58     // We need an iterator that translates them...
59     begin = NodeIterator(new NodeFromEdgeSet(ins_.begin(), NodeFromEdgeSet::source));
60     end = NodeIterator(new NodeFromEdgeSet(ins_.end(), NodeFromEdgeSet::source));
61 }
62
63 void Node::outs(NodeIterator &begin, NodeIterator &end) {
64     begin = NodeIterator(new NodeFromEdgeSet(outs_.begin(), NodeFromEdgeSet::target));
65     end = NodeIterator(new NodeFromEdgeSet(outs_.end(), NodeFromEdgeSet::target));
66 }
67
68 void Node::ins(EdgeIterator &begin, EdgeIterator &end) {
69     // Iteration over a pre-existing set is easy...
70     begin = EdgeIterator(new EdgeIteratorSet(ins_.begin()));
71     end = EdgeIterator(new EdgeIteratorSet(ins_.end()));
72 }
73
74 void Node::outs(EdgeIterator &begin, EdgeIterator &end) {
75     // Iteration over a pre-existing set is easy...
76     begin = EdgeIterator(new EdgeIteratorSet(outs_.begin()));
77     end = EdgeIterator(new EdgeIteratorSet(outs_.end()));
78 }
79
80 bool Node::hasInEdges() {
81     return !ins_.empty();
82 }
83
84 bool Node::hasOutEdges() {
85     return !outs_.empty();
86 }
87
88 void Node::forwardClosure(NodeIterator &begin, NodeIterator &end) {
89     end = NodeIterator(new NodeSearchIterator());
90
91     if (!hasOutEdges()) {
92         begin = end;
93     }
94     else {
95         NodeIterator outBegin, outEnd;
96         outs(outBegin, outEnd);
97         begin = NodeIterator(new NodeSearchIterator(outBegin, outEnd, NodeSearchIterator::out, NodeSearchIterator::breadth));
98     }
99 }
100
101 void Node::backwardClosure(NodeIterator &begin, NodeIterator &end) {
102     end = NodeIterator(new NodeSearchIterator());
103
104     if (!hasInEdges()) {
105         begin = end;
106     }
107     else {
108         NodeIterator inBegin, inEnd;
109         ins(inBegin, inEnd);
110         begin = NodeIterator(new NodeSearchIterator(inBegin, inEnd, NodeSearchIterator::in, NodeSearchIterator::breadth));
111     }
112 }
113
114
115 Node::Ptr PhysicalNode::createNode(Address addr) {
116     return Node::Ptr(new PhysicalNode(addr));
117 }
118
119 Node::Ptr PhysicalNode::copy() {
120     return Node::Ptr(new PhysicalNode(addr()));
121 }
122
123 std::string PhysicalNode::format() const {
124     char buf[256];
125     sprintf(buf, "N_0x%lx", addr());
126     return std::string(buf);
127 }
128
129 std::string VirtualNode::defaultName("N_VIRTUAL");
130
131 Node::Ptr VirtualNode::createNode() {
132     return Node::Ptr(new VirtualNode());
133 }
134
135 Node::Ptr VirtualNode::createNode(std::string name) {
136     return Node::Ptr(new VirtualNode(name));
137 }
138
139 Node::Ptr VirtualNode::copy() {
140     return Node::Ptr(new VirtualNode(name_));
141 }
142
143 std::string VirtualNode::format() const {
144     return name_;
145 }
146
147 // Prefix...
148 NodeIterator &NodeIterator::operator++() {
149     if (!iter_) return *this;
150     
151     iter_->inc();
152     return *this;
153 }
154
155 // Postfix...
156 NodeIterator NodeIterator::operator++(int) {
157     NodeIterator ret = *this;
158     ++(*this);
159     return ret;    
160 }
161 /*
162 // Prefix...
163 NodeIterator &NodeIterator::operator--() {
164     if (!iter_) return *this;
165     
166     iter_->dec();
167     return *this;
168 }
169
170 // Postfix...
171 NodeIterator NodeIterator::operator--(int) {
172     NodeIterator ret = *this;
173     --(*this);
174     return ret;    
175 }
176 */
177
178 Node::Ptr NodeIterator::operator*() const {
179     if (!iter_) return Node::Ptr();
180
181     return iter_->get();
182 }
183
184 bool NodeIterator::operator!=(const NodeIterator &rhs) const {
185     if (!iter_) {
186         return (rhs.iter_ != NULL);
187     }
188     return !iter_->equals(rhs.iter_);
189 }
190
191 bool NodeIterator::operator==(const NodeIterator &rhs) const {
192     if (!iter_) {
193         return (rhs.iter_ == NULL);
194     }
195     return iter_->equals(rhs.iter_);
196 }
197
198 NodeIterator &NodeIterator::operator=(const NodeIterator &rhs) {
199     if (iter_) delete iter_;
200     iter_ = rhs.copy();
201     return *this;
202 }
203
204 NodeIterator::NodeIterator() : iter_(NULL) {
205 }
206
207 NodeIterator::NodeIterator(NodeIteratorImpl *iter) :
208     iter_(iter) {
209 }
210
211 NodeIterator::NodeIterator(const NodeIterator &rhs) :
212     iter_(rhs.copy()) {
213 }
214
215 NodeIterator::~NodeIterator() { 
216     if (iter_) delete iter_;
217 }
218
219 NodeIteratorImpl *NodeIterator::copy() const {
220     if (iter_ == NULL) return NULL;
221     return iter_->copy();
222 }
223
224 Graph::Ptr Node::forwardSubgraph() {
225     // We want to copy this node and every node reachable from
226     // it along a forward direction. This node will become the
227     // entry for a new subgraph. 
228
229     // TODO: this is a generic graph by definition, as nodes
230     // have no idea what type of graph they belong to. Is that
231     // the right thing? 
232
233     Graph::Ptr ret = Graph::createGraph();
234     
235     Node::Ptr newEntry = copy();
236     ret->insertEntryNode(newEntry);
237     
238     std::set<Node::Ptr> visited;
239     std::queue<std::pair<Node::Ptr, Node::Ptr> > worklist;
240
241     // We don't have a shared pointer to the current node. 
242     // However, we do have an edge, which has a weak pointer. 
243
244     if (outs_.empty()) return ret;
245     Node::Ptr thisPtr = (*outs_.begin())->source();
246
247     worklist.push(std::make_pair(thisPtr, newEntry));
248
249     while (!worklist.empty()) {
250         // First is the original node, second the copy
251         std::pair<Node::Ptr, Node::Ptr> src = worklist.front(); 
252         worklist.pop();
253
254         if (visited.find(src.first) != visited.end()) continue;
255         visited.insert(src.first);
256
257         NodeIterator b, e;
258         src.first->outs(b, e);
259
260         if (b == e) {
261             ret->insertExitNode(src.second);
262         }
263
264         for (; b != e; ++b) {
265             std::pair<Node::Ptr, Node::Ptr> targ = std::make_pair(*b, (*b)->copy());
266             ret->insertPair(src.second, targ.second);
267             worklist.push(targ);
268         } 
269     }
270     return ret;
271 }
272
273 Graph::Ptr Node::backwardSubgraph() {
274     // We want to copy this node and every node reachable from
275     // it along a forward direction. This node will become the
276     // entry for a new subgraph. 
277
278     // TODO: this is a generic graph by definition, as nodes
279     // have no idea what type of graph they belong to. Is that
280     // the right thing? 
281
282     Graph::Ptr ret = Graph::createGraph();
283     
284     Node::Ptr newExit = copy();
285     ret->insertExitNode(newExit);
286     
287     std::set<Node::Ptr> visited;
288     std::queue<std::pair<Node::Ptr, Node::Ptr> > worklist;
289     
290     // See comment in nearly-identical code above...
291     if (ins_.empty()) return ret;
292     Node::Ptr thisPtr = (*ins_.begin())->target();
293
294     worklist.push(std::make_pair(thisPtr, newExit));
295
296     while (!worklist.empty()) {
297         // First is the original node, second the copy
298         std::pair<Node::Ptr, Node::Ptr> targ = worklist.front(); 
299         worklist.pop();
300
301         if (visited.find(targ.first) != visited.end()) continue;
302         visited.insert(targ.first);
303
304         NodeIterator b, e;
305
306         targ.first->ins(b, e);
307
308         if (b == e) {
309             ret->insertEntryNode(targ.second);
310         }
311
312         for (; b != e; ++b) {
313             std::pair<Node::Ptr, Node::Ptr> src = std::make_pair(*b, (*b)->copy());
314             ret->insertPair(src.second, targ.second);
315             worklist.push(src);
316         } 
317     }
318     return ret;
319 }
320
321 void Node::deleteInEdge(EdgeIterator e) {
322   ins_.erase(*e);
323 }
324
325 void Node::deleteOutEdge(EdgeIterator e) {
326   outs_.erase(*e);
327 }
328