1 package Analysis.Pointer;
4 import Analysis.Pointer.AllocFactory.AllocNode;
6 import Analysis.Disjoint.TaintSet;
7 import Analysis.Disjoint.Taint;
9 public class GraphManip {
10 static MySet<Edge> genEdges(TempDescriptor tmp, HashSet<AllocNode> dstSet) {
11 MySet<Edge> edgeset=new MySet<Edge>();
12 for(AllocNode node:dstSet) {
13 edgeset.add(new Edge(tmp, node));
18 static MySet<Edge> genEdges(TempDescriptor tmp, MySet<Edge> dstSet) {
19 MySet<Edge> edgeset=new MySet<Edge>();
21 edgeset.add(e.changeSrcVar(tmp, null));
26 static MySet<Edge> genEdges(HashSet<AllocNode> srcSet, FieldDescriptor fd, HashSet<AllocNode> dstSet) {
27 MySet<Edge> edgeset=new MySet<Edge>();
28 for(AllocNode srcnode:srcSet) {
29 for(AllocNode dstnode:dstSet) {
30 edgeset.add(new Edge(srcnode, fd, dstnode, Edge.NEW));
36 static MySet<Edge> genEdges(HashSet<AllocNode> srcSet, FieldDescriptor fd, MySet<Edge> dstSet) {
37 MySet<Edge> edgeset=new MySet<Edge>();
38 for(AllocNode srcnode:srcSet) {
39 for(Edge dstedge:dstSet) {
40 edgeset.add(dstedge.changeSrc(fd, srcnode));
46 static MySet<Edge> getDiffEdges(Delta delta, TempDescriptor tmp) {
47 MySet<Edge> edges=new MySet<Edge>();
48 MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
50 MySet<Edge> baseedges=delta.basevaredge.get(tmp);
51 if (baseedges!=null) {
52 for(Edge e:baseedges) {
53 if (removeedges==null||!removeedges.contains(e))
57 if (delta.varedgeadd.containsKey(tmp))
58 for(Edge e:delta.varedgeadd.get(tmp)) {
64 static MySet<Edge> getEdges(Graph graph, Delta delta, TempDescriptor tmp) {
65 MySet<Edge> edges=new MySet<Edge>();
66 MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
68 for(Edge e:graph.getEdges(tmp)) {
69 if (removeedges==null||!removeedges.contains(e))
72 if (delta.varedgeadd.containsKey(tmp))
73 for(Edge e:delta.varedgeadd.get(tmp)) {
79 static MySet<Edge> getEdges(Graph graph, Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
80 MySet<Edge> nodes=new MySet<Edge>();
81 for(AllocNode node:srcNodes) {
82 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
83 for(Edge e:graph.getEdges(node)) {
84 if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
87 if (delta.heapedgeadd.containsKey(node))
88 for(Edge e:delta.heapedgeadd.get(node)) {
96 static MySet<Edge> getEdges(Graph graph, Delta delta, AllocNode node) {
97 MySet<Edge> nodes=new MySet<Edge>();
98 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
99 for(Edge e:graph.getEdges(node)) {
100 if ((removeedges==null||!removeedges.contains(e)))
103 if (delta.heapedgeadd.containsKey(node))
104 for(Edge e:delta.heapedgeadd.get(node)) {
111 static HashSet<AllocNode> getDiffNodes(Delta delta, TempDescriptor tmp) {
112 HashSet<AllocNode> nodes=new HashSet<AllocNode>();
113 MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
115 MySet<Edge> baseEdges=delta.basevaredge.get(tmp);
118 for(Edge e:baseEdges) {
119 if (removeedges==null||!removeedges.contains(e))
122 if (delta.varedgeadd.containsKey(tmp))
123 for(Edge e:delta.varedgeadd.get(tmp)) {
129 static HashSet<AllocNode> getNodes(Graph graph, Delta delta, TempDescriptor tmp) {
130 HashSet<AllocNode> nodes=new HashSet<AllocNode>();
131 MySet<Edge> removeedges=delta.varedgeremove.get(tmp);
133 for(Edge e:graph.getEdges(tmp)) {
134 if (removeedges==null||!removeedges.contains(e))
137 if (delta.varedgeadd.containsKey(tmp))
138 for(Edge e:delta.varedgeadd.get(tmp)) {
144 static HashSet<AllocNode> getDiffNodes(Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
145 HashSet<AllocNode> nodes=new HashSet<AllocNode>();
146 for(AllocNode node:srcNodes) {
147 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
148 MySet<Edge> baseEdges=delta.baseheapedge.get(node);
150 for(Edge e:baseEdges) {
151 if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
154 if (delta.heapedgeadd.containsKey(node))
155 for(Edge e:delta.heapedgeadd.get(node)) {
163 static MySet<Edge> getDiffEdges(Delta delta, HashSet<AllocNode> srcNodes) {
164 MySet<Edge> newedges=new MySet<Edge>();
165 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.baseheapedge.entrySet()) {
166 AllocNode node=entry.getKey();
167 if (srcNodes.contains(node)) {
168 MySet<Edge> edges=entry.getValue();
169 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
171 if (removeedges==null||!removeedges.contains(e)) {
177 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
178 AllocNode node=entry.getKey();
179 if (srcNodes.contains(node)) {
180 MySet<Edge> edges=entry.getValue();
181 newedges.addAll(edges);
188 static MySet<Edge> getDiffEdges(Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
189 MySet<Edge> newedges=new MySet<Edge>();
190 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.baseheapedge.entrySet()) {
191 AllocNode node=entry.getKey();
192 if (srcNodes.contains(node)) {
193 MySet<Edge> edges=entry.getValue();
194 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
196 if ((removeedges==null||!removeedges.contains(e))&&(e.fd==fd)) {
202 for(Map.Entry<AllocNode, MySet<Edge>> entry:delta.heapedgeadd.entrySet()) {
203 AllocNode node=entry.getKey();
204 if (srcNodes.contains(node)) {
205 MySet<Edge> edges=entry.getValue();
215 static MySet<Edge> makeOld(MySet<Edge> edgesin) {
216 MySet<Edge> edgeset=new MySet<Edge>();
217 for(Edge e:edgesin) {
218 edgeset.add(e.makeOld());
223 static MySet<Edge> dereference(Graph graph, Delta delta, TempDescriptor dst, MySet<Edge> srcEdges, FieldDescriptor fd, FlatNode fn, TaintSet taint) {
224 MySet<Edge> edgeset=new MySet<Edge>();
225 for(Edge edge:srcEdges) {
226 TaintSet ts=edge.getTaints();
234 MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
235 for(Edge e:graph.getEdges(edge.dst)) {
236 if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
237 e=e.changeSrcVar(dst, ts);
238 if (!edgeset.contains(e))
241 Edge preve=edgeset.get(e);
247 if (delta.heapedgeadd.containsKey(edge.dst))
248 for(Edge e:delta.heapedgeadd.get(edge.dst)) {
250 e=e.changeSrcVar(dst, ts);
251 if (!edgeset.contains(e))
254 Edge preve=edgeset.get(e);
264 static MySet<Edge> diffDereference(Delta delta, TempDescriptor dst, MySet<Edge> srcEdges, FieldDescriptor fd, FlatNode fn, TaintSet taint) {
265 MySet<Edge> edgeset=new MySet<Edge>();
266 for(Edge edge:srcEdges) {
267 TaintSet ts=edge.getTaints();
274 MySet<Edge> removeedges=delta.heapedgeremove.get(edge.dst);
275 if (delta.baseheapedge.containsKey(edge.dst)) {
276 for(Edge e:delta.baseheapedge.get(edge.dst)) {
277 if (e.fd==fd&&(removeedges==null||!removeedges.contains(e))) {
278 e=e.changeSrcVar(dst, ts);
279 if (!edgeset.contains(e))
282 Edge preve=edgeset.get(e);
289 if (delta.heapedgeadd.containsKey(edge.dst))
290 for(Edge e:delta.heapedgeadd.get(edge.dst)) {
292 e=e.changeSrcVar(dst, ts);
293 if (!edgeset.contains(e))
296 Edge preve=edgeset.get(e);
306 static HashSet<AllocNode> getNodes(Graph graph, Delta delta, HashSet<AllocNode> srcNodes, FieldDescriptor fd) {
307 HashSet<AllocNode> nodes=new HashSet<AllocNode>();
308 for(AllocNode node:srcNodes) {
309 MySet<Edge> removeedges=delta.heapedgeremove.get(node);
310 for(Edge e:graph.getEdges(node)) {
311 if (e.fd==fd&&(removeedges==null||!removeedges.contains(e)))
314 if (delta.heapedgeadd.containsKey(node))
315 for(Edge e:delta.heapedgeadd.get(node)) {