Static Value-Flow Analysis
Loading...
Searching...
No Matches
GenericGraph.h
Go to the documentation of this file.
1//===- CenericGraph.h -- Generic graph ---------------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2017> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===----------------------------------------------------------------------===//
22
23/*
24 * GenericGraph.h
25 *
26 * Created on: Mar 19, 2014
27 * Author: Yulei Sui
28 */
29
30#ifndef GENERICGRAPH_H_
31#define GENERICGRAPH_H_
32
33#include "SVFIR/SVFType.h"
34#include "Util/iterator.h"
35#include "Graphs/GraphTraits.h"
36#include "SVFIR/SVFValue.h"
37
38namespace SVF
39{
42template <typename, typename> class GenericGraphWriter;
43template <typename, typename> class GenericGraphReader;
45
49template<class NodeTy>
51{
52
53public:
62private:
66
67public:
72
74 virtual ~GenericEdge()
75 {
76 }
77
79
80 inline NodeID getSrcID() const
81 {
82 return src->getId();
83 }
84 inline NodeID getDstID() const
85 {
86 return dst->getId();
87 }
88 inline GEdgeKind getEdgeKind() const
89 {
90 return (EdgeKindMask & edgeFlag);
91 }
93 {
94 return edgeFlag;
95 }
97 {
98 return src;
99 }
101 {
102 return dst;
103 }
105
107 // and duplicated elements in the set are not inserted (binary tree comparison)
109 typedef struct equalGEdge
110 {
112 {
113 if (lhs->edgeFlag != rhs->edgeFlag)
114 return lhs->edgeFlag < rhs->edgeFlag;
115 else if (lhs->getSrcID() != rhs->getSrcID())
116 return lhs->getSrcID() < rhs->getSrcID();
117 else
118 return lhs->getDstID() < rhs->getDstID();
119 }
120 } equalGEdge;
121
122 virtual inline bool operator==(const GenericEdge<NodeType>* rhs) const
123 {
124 return (rhs->edgeFlag == this->edgeFlag &&
125 rhs->getSrcID() == this->getSrcID() &&
126 rhs->getDstID() == this->getDstID());
127 }
129
130protected:
131 static constexpr unsigned char EdgeKindMaskBits = 8;
132 static constexpr u64_t EdgeKindMask = (~0ULL) >> (64 - EdgeKindMaskBits);
133};
134
135
136
140template<class NodeTy,class EdgeTy>
142{
143
144public:
151 typedef typename GEdgeSetTy::iterator iterator;
152 typedef typename GEdgeSetTy::const_iterator const_iterator;
154
155private:
156
159
160public:
163 {
164
165 }
166
168 virtual ~GenericNode()
169 {
170 for (auto * edge : OutEdges)
171 delete edge;
172 }
173
176 inline const GEdgeSetTy& getOutEdges() const
177 {
178 return OutEdges;
179 }
180 inline const GEdgeSetTy& getInEdges() const
181 {
182 return InEdges;
183 }
185
187
188 inline bool hasIncomingEdge() const
189 {
190 return (InEdges.empty() == false);
191 }
192 inline bool hasOutgoingEdge() const
193 {
194 return (OutEdges.empty() == false);
195 }
197
199
201 {
202 return OutEdges.begin();
203 }
205 {
206 return OutEdges.end();
207 }
209 {
210 return InEdges.begin();
211 }
213 {
214 return InEdges.end();
215 }
217 {
218 return OutEdges.begin();
219 }
221 {
222 return OutEdges.end();
223 }
225 {
226 return InEdges.begin();
227 }
229 {
230 return InEdges.end();
231 }
233
235
237 {
238 return OutEdges.begin();
239 }
240 virtual inline iterator directOutEdgeEnd()
241 {
242 return OutEdges.end();
243 }
245 {
246 return InEdges.begin();
247 }
248 virtual inline iterator directInEdgeEnd()
249 {
250 return InEdges.end();
251 }
252
253 virtual inline const_iterator directOutEdgeBegin() const
254 {
255 return OutEdges.begin();
256 }
257 virtual inline const_iterator directOutEdgeEnd() const
258 {
259 return OutEdges.end();
260 }
261 virtual inline const_iterator directInEdgeBegin() const
262 {
263 return InEdges.begin();
264 }
265 virtual inline const_iterator directInEdgeEnd() const
266 {
267 return InEdges.end();
268 }
270
272
274 {
275 return InEdges.insert(inEdge).second;
276 }
278 {
279 return OutEdges.insert(outEdge).second;
280 }
282
286 {
287 iterator it = InEdges.find(edge);
288 assert(it != InEdges.end() && "can not find in edge in SVFG node");
289 InEdges.erase(it);
290 return 1;
291 }
293 {
294 iterator it = OutEdges.find(edge);
295 assert(it != OutEdges.end() && "can not find out edge in SVFG node");
296 OutEdges.erase(it);
297 return 1;
298 }
300
302
304 {
306 if (it != InEdges.end())
307 return *it;
308 else
309 return nullptr;
310 }
312 {
314 if (it != OutEdges.end())
315 return *it;
316 else
317 return nullptr;
318 }
320
321 static inline bool classof(const GenericNode<NodeTy, EdgeTy>*)
322 {
323 return true;
324 }
325
326 static inline bool classof(const SVFValue*)
327 {
328 return true;
329 }
330};
331
332/*
333 * Generic graph for program representation
334 * It is base class and needs to be instantiated
335 */
336template<class NodeTy, class EdgeTy>
338{
339 friend class GenericGraphWriter<NodeTy, EdgeTy>;
340 friend class GenericGraphReader<NodeTy, EdgeTy>;
341
342public:
347
349
350 typedef typename IDToNodeMapTy::iterator iterator;
351 typedef typename IDToNodeMapTy::const_iterator const_iterator;
353
356
359 {
360 destroy();
361 }
362
364 void destroy()
365 {
366 for (auto &entry : IDToNodeMap)
367 delete entry.second;
368 }
370
372 {
373 return IDToNodeMap.begin();
374 }
375 inline iterator end()
376 {
377 return IDToNodeMap.end();
378 }
379 inline const_iterator begin() const
380 {
381 return IDToNodeMap.begin();
382 }
383 inline const_iterator end() const
384 {
385 return IDToNodeMap.end();
386 }
387 //}@
388
390 inline void addGNode(NodeID id, NodeType* node)
391 {
392 IDToNodeMap[id] = node;
393 nodeNum++;
394 }
395
397 inline NodeType* getGNode(NodeID id) const
398 {
399 const_iterator it = IDToNodeMap.find(id);
400 assert(it != IDToNodeMap.end() && "Node not found!");
401 return it->second;
402 }
403
405 inline bool hasGNode(NodeID id) const
406 {
407 const_iterator it = IDToNodeMap.find(id);
408 return it != IDToNodeMap.end();
409 }
410
412 inline void removeGNode(NodeType* node)
413 {
414 assert(node->hasIncomingEdge() == false
415 && node->hasOutgoingEdge() == false
416 && "node which have edges can't be deleted");
417 iterator it = IDToNodeMap.find(node->getId());
418 assert(it != IDToNodeMap.end() && "can not find the node");
419 IDToNodeMap.erase(it);
420 delete node;
421 }
422
424 inline u32_t getTotalNodeNum() const
425 {
426 return nodeNum;
427 }
428 inline u32_t getTotalEdgeNum() const
429 {
430 return edgeNum;
431 }
433 inline void incNodeNum()
434 {
435 nodeNum++;
436 }
437 inline void incEdgeNum()
438 {
439 edgeNum++;
440 }
441
442protected:
444
445public:
448};
449
450} // End namespace SVF
451
452/* !
453 * GenericGraphTraits specializations for generic graph algorithms.
454 * Provide graph traits for traversing from a node using standard graph traversals.
455 */
456namespace SVF
457{
458
459// mapped_iter - This is a simple iterator adapter that causes a function to
460// be applied whenever operator* is invoked on the iterator.
461
462template <typename ItTy, typename FuncTy,
463 typename FuncReturnTy =
464 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
466 : public iter_adaptor_base<
467 mapped_iter<ItTy, FuncTy>, ItTy,
468 typename std::iterator_traits<ItTy>::iterator_category,
469 typename std::remove_reference<FuncReturnTy>::type>
470{
471public:
473 : mapped_iter::iter_adaptor_base(std::move(U)), F(std::move(F)) {}
474
476 {
477 return this->I;
478 }
479
480 FuncReturnTy operator*() const
481 {
482 return F(*this->I);
483 }
484
485private:
486 FuncTy F;
487};
488
489// map_iter - Provide a convenient way to create mapped_iters, just like
490// make_pair is useful for creating pairs...
491template <class ItTy, class FuncTy>
493{
494 return mapped_iter<ItTy, FuncTy>(std::move(I), std::move(F));
495}
496
500template<class NodeTy,class EdgeTy> struct GenericGraphTraits<SVF::GenericNode<NodeTy,EdgeTy>* >
501{
504
505 static inline NodeType* edge_dest(const EdgeType* E)
506 {
507 return E->getDstNode();
508 }
509
510 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
512
514 {
515 return pagN;
516 }
517
519 {
520 return map_iter(N->OutEdgeBegin(), &edge_dest);
521 }
522 static inline ChildIteratorType child_end(const NodeType* N)
523 {
524 return map_iter(N->OutEdgeEnd(), &edge_dest);
525 }
527 {
528 return map_iter(N->directOutEdgeBegin(), &edge_dest);
529 }
531 {
532 return map_iter(N->directOutEdgeEnd(), &edge_dest);
533 }
534};
535
539template<class NodeTy,class EdgeTy>
540struct GenericGraphTraits<Inverse<SVF::GenericNode<NodeTy,EdgeTy>* > >
541{
544
545 static inline NodeType* edge_dest(const EdgeType* E)
546 {
547 return E->getSrcNode();
548 }
549
550 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
552
554 {
555 return G.Graph;
556 }
557
559 {
560 return map_iter(N->InEdgeBegin(), &edge_dest);
561 }
562 static inline ChildIteratorType child_end(const NodeType* N)
563 {
564 return map_iter(N->InEdgeEnd(), &edge_dest);
565 }
566
567 static inline unsigned getNodeID(const NodeType* N)
568 {
569 return N->getId();
570 }
571};
572
576template<class NodeTy,class EdgeTy> struct GenericGraphTraits<SVF::GenericGraph<NodeTy,EdgeTy>* > : public GenericGraphTraits<SVF::GenericNode<NodeTy,EdgeTy>* >
577{
581
583 {
584 return nullptr; // return null here, maybe later we could create a dummy node
585 }
586
587 typedef std::pair<SVF::NodeID, NodeType*> PairTy;
588 static inline NodeType* deref_val(PairTy P)
589 {
590 return P.second;
591 }
592
593 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
594 typedef mapped_iter<typename GenericGraphTy::iterator, decltype(&deref_val)> nodes_iterator;
595
597 {
598 return map_iter(G->begin(), &deref_val);
599 }
601 {
602 return map_iter(G->end(), &deref_val);
603 }
604
605 static unsigned graphSize(GenericGraphTy* G)
606 {
607 return G->getTotalNodeNum();
608 }
609
610 static inline unsigned getNodeID(NodeType* N)
611 {
612 return N->getId();
613 }
615 {
616 return G->getGNode(id);
617 }
618};
619
620} // End namespace llvm
621
622#endif /* GENERICGRAPH_H_ */
virtual bool operator==(const GenericEdge< NodeType > *rhs) const
NodeTy * src
source node
GEdgeKind getEdgeKindWithoutMask() const
NodeType * getSrcNode() const
virtual ~GenericEdge()
Destructor.
GenericEdge(NodeTy *s, NodeTy *d, GEdgeFlag k)
Constructor.
NodeType * getDstNode() const
static constexpr u64_t EdgeKindMask
GEdgeFlag edgeFlag
edge kind
NodeTy * dst
destination node
GEdgeKind getEdgeKind() const
NodeID getDstID() const
NodeID getSrcID() const
get methods of the components
static constexpr unsigned char EdgeKindMaskBits
We use the lower 8 bits to denote edge kind.
NodeTy NodeType
Node type.
void addGNode(NodeID id, NodeType *node)
Add a Node.
iterator begin()
Iterators.
void removeGNode(NodeType *node)
Delete a node.
u32_t getTotalEdgeNum() const
u32_t edgeNum
total num of node
const_iterator end() const
const_iterator begin() const
u32_t nodeNum
total num of edge
virtual ~GenericGraph()
Destructor.
IDToNodeMapTy IDToNodeMap
node map
IDToNodeMapTy::const_iterator const_iterator
bool hasGNode(NodeID id) const
Has a node.
void incNodeNum()
Increase number of node/edge.
u32_t getTotalNodeNum() const
Get total number of node/edge.
GenericGraph()
Constructor.
IDToNodeMapTy::iterator iterator
Node Iterators.
NodeType * getGNode(NodeID id) const
Get a node.
void destroy()
Release memory.
OrderedMap< NodeID, NodeType * > IDToNodeMapTy
NodeID to GenericNode map.
const_iterator InEdgeEnd() const
OrderedSet< EdgeType *, typename EdgeType::equalGEdge > GEdgeSetTy
Edge kind.
GEdgeSetTy OutEdges
all outgoing edge of this node
bool hasIncomingEdge() const
Has incoming/outgoing edge set.
bool hasOutgoingEdge() const
u32_t removeOutgoingEdge(EdgeType *edge)
GenericNode(NodeID i, GNodeK k, const SVFType *svfType=nullptr)
Constructor.
virtual iterator directInEdgeEnd()
iterator OutEdgeEnd()
EdgeType * hasIncomingEdge(EdgeType *edge) const
Find incoming and outgoing edges.
GEdgeSetTy InEdges
all incoming edge of this node
GEdgeSetTy::iterator iterator
const GEdgeSetTy & getOutEdges() const
virtual ~GenericNode()
Destructor.
virtual iterator directInEdgeBegin()
const_iterator OutEdgeBegin() const
virtual iterator directOutEdgeEnd()
const GEdgeSetTy & getInEdges() const
static bool classof(const SVFValue *)
const_iterator InEdgeBegin() const
virtual const_iterator directOutEdgeEnd() const
bool addIncomingEdge(EdgeType *inEdge)
Add incoming and outgoing edges.
u32_t removeIncomingEdge(EdgeType *edge)
virtual iterator directOutEdgeBegin()
Iterators used for SCC detection, overwrite it in child class if necessary.
iterator OutEdgeBegin()
iterators
virtual const_iterator directInEdgeEnd() const
static bool classof(const GenericNode< NodeTy, EdgeTy > *)
virtual const_iterator directInEdgeBegin() const
GEdgeSetTy::const_iterator const_iterator
const_iterator OutEdgeEnd() const
virtual const_iterator directOutEdgeBegin() const
EdgeType * hasOutgoingEdge(EdgeType *edge) const
iterator InEdgeBegin()
bool addOutgoingEdge(EdgeType *outEdge)
iterator InEdgeEnd()
WrappedIteratorT I
Definition iterator.h:242
mapped_iter(ItTy U, FuncTy F)
FuncReturnTy operator*() const
for isBitcode
Definition BasicTypes.h:68
unsigned long long u64_t
Definition GeneralType.h:49
u32_t NodeID
Definition GeneralType.h:56
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
unsigned u32_t
Definition GeneralType.h:47
mapped_iter< ItTy, FuncTy > map_iter(ItTy I, FuncTy F)
signed long long s64_t
Definition GeneralType.h:50
Add the hash function for std::set (we also can overload operator< to implement this)
bool operator()(const GenericEdge< NodeType > *lhs, const GenericEdge< NodeType > *rhs) const
mapped_iter< typename SVF::GenericNode< NodeTy, EdgeTy >::iterator, decltype(&edge_dest)> ChildIteratorType
static NodeType * getNode(GenericGraphTy *G, SVF::NodeID id)
mapped_iter< typename GenericGraphTy::iterator, decltype(&deref_val)> nodes_iterator
static ChildIteratorType direct_child_begin(const NodeType *N)
static ChildIteratorType child_end(const NodeType *N)
static ChildIteratorType direct_child_end(const NodeType *N)
mapped_iter< typename SVF::GenericNode< NodeTy, EdgeTy >::iterator, decltype(&edge_dest)> ChildIteratorType
static ChildIteratorType child_begin(const NodeType *N)
const GraphType & Graph
Definition GraphTraits.h:99