ParseAPI docs updated for new simpler EdgePredicate abstraction.
[dyninst.git] / parseAPI / doc / API / EdgePredicate.tex
1 \subsection{Edge Predicates}
2 \label{sec:pred}
3
4 \definedin{CFG.h}
5
6 Edge predicates control iteration over edges. For example, the provided
7 \code{Intraproc} edge predicate can be used with filter iterators and standard
8 algorithms, ensuring that only intraprocedural edges are visited during
9 iteration. Two other examples of edge predicates are provided: 
10 \code{SingleContext} only visits edges that stay in a single
11 function context, and \code{NoSinkPredicate} does not visit edges to 
12 the \emph{sink} block.  The following code traverses 
13 all of the basic blocks within a
14 function:
15
16 \lstset{language=[GNU]C++,basicstyle=\fontfamily{fvm}\selectfont\small}
17 \lstset{numbers=left, numberstyle=\tiny, stepnumber=5, numbersep=5pt}
18 \begin{lstlisting}
19     #include <boost/filter_iterator.hpp>
20     using boost::make_filter_iterator;
21     struct target_block
22     {
23       Block* operator()(Edge* e) { return e->trg(); }
24     };
25
26
27     vector<Block*> work;
28     Intraproc epred; // ignore calls, returns
29    
30     work.push_back(func->entry()); // assuming `func' is a Function*
31
32     // do_stuff is a functor taking a Block* as its argument
33     while(!work.empty()) {
34         Block * b = work.back();
35         work.pop_back();
36
37         Block::edgelist & targets = block->targets();
38         // Do stuff for each out edge
39         std::for_each(make_filter_iterator(targets.begin(), epred), 
40                       make_filter_iterator(targets.end(), epred),
41                       do_stuff());
42         std::transform(make_filter_iterator(targets.begin(), epred),
43                        make_filter_iterator(targets.end(), epred), 
44                        std::back_inserter(work), 
45                        std::mem_fun(Edge::trg));
46         Block::edgelist::const_iterator found_interproc =
47                 std::find_if(targets.begin(), targets.end(), Interproc());
48         if(interproc != targets.end()) {
49                 // do something with the interprocedural edge you found
50         }
51     }
52
53 \end{lstlisting}
54
55 Anything that can be treated as a function from \code{Edge*} to a \code{bool} can be used in this manner. This replaces the beta interface where all
56 \code{EdgePredicate}s needed to descend from a common parent class. Code that previously constructed iterators from an edge predicate should be replaced
57 with equivalent code using filter iterators as follows:
58
59 \begin{lstlisting}
60   // OLD
61   for(Block::edgelist::iterator i = targets.begin(epred); i != targets.end(epred); i++)
62   {
63     // ...
64   }
65   // NEW
66   for_each(make_filter_iterator(targets.begin(), epred),
67            make_filter_iterator(targets.end(), epred),
68            loop_body_as_function);
69   // NEW (C++11)
70   for(auto  i = make_filter_iterator(targets.begin(), epred); i != make_filter_iterator(targets.end(), epred); i++)
71   {
72     // ...
73   }
74   
75
76 \end{lstlisting}