1
2
3
4 package joeq.Compiler.Dataflow;
5
6 import jwutil.graphs.Graph;
7
8 /***
9 * Problem
10 *
11 * @author John Whaley
12 * @version $Id: Problem.java 1931 2004-09-22 22:17:47Z joewhaley $
13 */
14 public abstract class Problem {
15
16 /***
17 * Performs necessary initialization for this dataflow problem.
18 *
19 * @param g graph of locations that we will run over
20 */
21 public void initialize(Graph g) {}
22
23 /***
24 * Returns true if this is a forward dataflow problem, false if it is
25 * a backward dataflow problem.
26 *
27 * @return direction
28 */
29 public abstract boolean direction();
30
31 /***
32 * Returns the boundary value for this dataflow problem. For a forward
33 * problem, this is the value at the entrypoint, whereas for a backward problem,
34 * this is the value at the exitpoint.
35 *
36 * @return boundary value
37 */
38 public abstract Fact boundary();
39
40 /***
41 * Returns the value that the interior points should be initialized to.
42 *
43 * @return value for interior points
44 */
45 public abstract Fact interior();
46
47 /***
48 * Returns the transfer function for the given code element.
49 *
50 * @param e code element
51 * @return transfer function for the given code element
52 */
53 public abstract TransferFunction getTransferFunction(Object e);
54
55 /***
56 * Applies the transfer function to the given dataflow value, yielding
57 * another dataflow value.
58 *
59 * @param tf transfer function
60 * @param f dataflow value
61 * @return resulting dataflow value
62 */
63 public Fact apply(TransferFunction tf, Fact f) {
64 return tf.apply(f);
65 }
66
67 /***
68 * Compares two dataflow facts, returning true if they are equal and false
69 * otherwise.
70 *
71 * @param f1 first fact
72 * @param f2 second fact
73 * @return true if they match, false otherwise
74 */
75 public boolean compare(Fact f1, Fact f2) {
76 return f1.equals(f2);
77 }
78
79 /***
80 * Combines two dataflow values, returning a new value that is the confluence
81 * of the two.
82 *
83 * @param f1 first fact
84 * @param f2 second fact
85 * @return confluence of the two facts
86 */
87 public Fact merge(Fact f1, Fact f2) {
88 return f1.merge(f2);
89 }
90
91 /***
92 * Returns the composition of two transfer functions. The default implementation
93 * simply returns a transfer function that applies each of the transfer functions
94 * in turn.
95 *
96 * @param tf1 first transfer function
97 * @param tf2 second transfer function
98 * @return composed transfer function
99 */
100 public TransferFunction compose(TransferFunction tf1, TransferFunction tf2) {
101 final TransferFunction t1 = tf1;
102 final TransferFunction t2 = tf2;
103 return new TransferFunction() {
104 public Fact apply(Fact f) {
105 Fact f1 = Problem.this.apply(t1, f);
106 Fact f2 = Problem.this.apply(t2, f1);
107 return f2;
108 }
109 };
110 }
111
112 /***
113 * Returns the closure of the given transfer function. The closure is a
114 * transfer function that is equivalent to composing the given transfer function
115 * with itself repeatedly until the value stablizes. (A monotone lattice with
116 * finite descending chains guarantees this.)
117 *
118 * @param tf
119 * @return transfer function representing the closure
120 */
121 public TransferFunction closure(TransferFunction tf) {
122 final TransferFunction t = tf;
123 return new TransferFunction() {
124 public Fact apply(Fact f) {
125 for (;;) {
126 Fact f1 = Problem.this.apply(t, f);
127 if (Problem.this.compare(f, f1)) return f;
128 f = f1;
129 }
130 }
131 };
132 }
133
134 }