-
Notifications
You must be signed in to change notification settings - Fork 1.1k
/
ControlFlowGraph.java
204 lines (188 loc) · 6.44 KB
/
ControlFlowGraph.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
/*
* Copyright 2008 The Closure Compiler Authors.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.javascript.jscomp;
import com.google.javascript.jscomp.NodeTraversal.Callback;
import com.google.javascript.jscomp.graph.LinkedDirectedGraph;
import com.google.javascript.rhino.Node;
import java.util.Comparator;
/**
* Control flow graph.
*
*
* @param <N> The instruction type of the control flow graph.
*/
public class ControlFlowGraph<N> extends
LinkedDirectedGraph<N, ControlFlowGraph.Branch> {
/**
* A special node marked by the node value key null to a singleton
* "return" when control is transferred outside of the current control flow
* graph.
*/
private final DiGraphNode<N, ControlFlowGraph.Branch> implicitReturn;
private final DiGraphNode<N, ControlFlowGraph.Branch> entry;
/**
* Constructor.
*/
ControlFlowGraph(
N entry, boolean nodeAnnotations, boolean edgeAnnotations) {
super(nodeAnnotations, edgeAnnotations);
implicitReturn = createDirectedGraphNode(null);
this.entry = createDirectedGraphNode(entry);
}
/**
* Gets the implicit return node.
*
* @return Return node.
*/
public DiGraphNode<N, ControlFlowGraph.Branch> getImplicitReturn() {
return implicitReturn;
}
/**
* Gets the entry point of the control flow graph. In general, this should be
* the beginning of the global script or beginning of a function.
*
* @return The entry point.
*/
public DiGraphNode<N, ControlFlowGraph.Branch> getEntry() {
return entry;
}
/**
* Checks whether node is the implicit return.
*
* @param node Node.
* @return True if the node is the implicit return.
*/
public boolean isImplicitReturn(
DiGraphNode<N, ControlFlowGraph.Branch> node) {
return node == implicitReturn;
}
/**
* Gets a comparator for the nodes. The default implementation returns
* {@code null}. See {@link ControlFlowGraph#getOptionalNodeComparator}.
* @param isForward Whether the comparator sorts the nodes in the direction of
* the flow.
* @return a comparator or null (in particular, if not overridden)
*/
public Comparator<DiGraphNode<N, Branch>> getOptionalNodeComparator(
boolean isForward) {
return null;
}
/**
* The edge object for the control flow graph.
*/
public static enum Branch {
/** Edge is taken if the condition is true. */
ON_TRUE,
/** Edge is taken if the condition is false. */
ON_FALSE,
/** Unconditional branch. */
UNCOND,
/**
* Exception-handling code paths.
* Conflates two kind of control flow passing:
* - An exception is thrown, and falls into a catch or finally block
* - During exception handling, a finally block finishes and control
* passes to the next finally block.
* In theory, we need 2 different edge types. In practice, we
* can just treat them as "the edges we can't really optimize".
*/
ON_EX,
/** Possible folded-away template */
SYN_BLOCK;
public boolean isConditional() {
return this == ON_TRUE || this == ON_FALSE;
}
}
/**
* Abstract callback to visit a control flow graph node without going into
* subtrees of the node that are also represented by other
* control flow graph nodes.
*
* <p>For example, traversing an IF node as root will visit the two subtrees
* pointed by the {@link ControlFlowGraph.Branch#ON_TRUE} and
* {@link ControlFlowGraph.Branch#ON_FALSE} edges.
*/
public abstract static class AbstractCfgNodeTraversalCallback implements
Callback {
@Override
public final boolean shouldTraverse(NodeTraversal nodeTraversal, Node n,
Node parent) {
if (parent == null) {
return true;
}
return !isEnteringNewCfgNode(n);
}
}
/**
* @return True if n should be represented by a new CFG node in the control
* flow graph.
*/
public static boolean isEnteringNewCfgNode(Node n) {
Node parent = n.getParent();
switch (parent.getToken()) {
case BLOCK:
case SCRIPT:
case TRY:
return true;
case FUNCTION:
// A function node represents the start of a function where the name
// bleeds into the local scope and parameters are assigned
// to the formal argument names. The node includes the name of the
// function and the LP list since we assume the whole set up process
// is atomic without change in control flow. The next change of
// control is going into the function's body, represented by the second
// child.
return n != parent.getSecondChild();
case WHILE:
case DO:
case IF:
// These control structures are represented by a node that holds the
// condition. Each of them is a branch node based on its condition.
return NodeUtil.getConditionExpression(parent) != n;
case FOR:
case FOR_IN:
// The FOR(;;) node differs from other control structures in that
// it has an initialization and an increment statement. Those
// two statements have corresponding CFG nodes to represent them.
// The FOR node only represents the condition check for each iteration.
// That way the following:
// for(var x = 0; x < 10; x++) { } has a graph that is isomorphic to
// var x = 0; while(x<10) { x++; }
if (NodeUtil.isForIn(parent)) {
// TODO(user): Investigate how we should handle the case where
// we have a very complex expression inside the FOR-IN header.
return n != parent.getFirstChild();
} else {
return NodeUtil.getConditionExpression(parent) != n;
}
case SWITCH:
case CASE:
case CATCH:
case WITH:
return n != parent.getFirstChild();
default:
return false;
}
}
@Override
public String toString() {
String s = "CFG:\n";
for (GraphvizEdge e : getGraphvizEdges()) {
s += e.toString() + '\n';
}
return s;
}
}