1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Analysis that determines which definitions may reach a given point in the code.
20 # Determines wich variables definitions reach each statement.
21 class ReachingDefsAnalysis
24 redef type FLOW: FlowHashSet[VarDef]
26 # New initial flows are empty (conservative analysis).
27 redef fun new_initial_flow
do return new FlowHashSet[VarDef]
29 # New initial flows for methods contains the parameters.
30 redef fun new_initial_method_flow
(n
) do
31 var flow
= new_initial_flow
32 var n_signature
= n
.n_signature
33 if n_signature
== null then return flow
34 for n_param
in n_signature
.n_params
do
35 var variable
= n_param
.variable
36 if variable
== null then continue
37 flow
.add
(new VarDef(variable
, n_param
.location
))
42 # Perform set union (used for **some path** analysis).
43 redef fun merge
(s1
, s2
) do return s1
.flow_union
(s2
)
45 redef fun visit
(n
) do n
.accept_reaching_defs
(self)
47 # Generate a new variable definition in the `current_outset`.
48 fun gen
(variable
: Variable, location
: Location) do
49 current_outset
.add
(new VarDef(variable
, location
))
52 # Kill a variable definition in the `current_outset`.
53 fun kill
(variable
: Variable) do
54 for vardef
in current_outset
.to_a
do
55 if vardef
.variable
== variable
then current_outset
.remove
(vardef
)
59 redef fun pretty_print
do
60 for node
, outset
in outsets
do
61 if outset
.is_empty
then continue
62 var values
= outset
.to_a
63 default_comparator
.sort
(values
)
64 print
"{node.location.line_end}: {values.join(", ")} out of {node.class_name}"
71 # Apply a ReachingDefsAnalysis to `self`.
72 fun accept_reaching_defs
(v
: ReachingDefsAnalysis) do accept_forward_analysis
(v
)
75 redef class AVardeclExpr
76 redef fun accept_reaching_defs
(v
) do
78 v
.kill
(variable
.as(not null))
79 v
.gen
(variable
.as(not null), location
)
83 redef class AVarAssignExpr
84 redef fun accept_reaching_defs
(v
) do
86 v
.kill
(variable
.as(not null))
87 v
.gen
(variable
.as(not null), location
)
91 redef class AVarReassignExpr
92 redef fun accept_reaching_defs
(v
) do
94 v
.kill
(variable
.as(not null))
95 v
.gen
(variable
.as(not null), location
)
100 redef fun accept_reaching_defs
(v
) do
101 # add variables from `for` declaration
102 for n_group
in n_groups
do
103 var variables
= n_group
.variables
104 if variables
== null then continue
105 for variable
in variables
do v
.gen
(variable
, n_group
.location
)
108 # remove variables from `for` declaration
109 for n_group
in n_groups
do
110 var variables
= n_group
.variables
111 if variables
== null then continue
112 for variable
in variables
do v
.kill
(variable
)
117 # A Variable definition.
119 # Associates a variable to the location of its definition.
123 redef type OTHER: VarDef
125 # Variable this definition is about.
126 var variable
: Variable
128 # Location of this definition in the source code.
129 var location
: Location
132 return o
isa OTHER and variable
== o
.variable
and location
== o
.location
136 if variable
.name
== o
.variable
.name
then
137 return location
.line_start
<=> o
.location
.line_start
139 return variable
.name
<=> o
.variable
.name
143 redef fun hash
do return variable
.hash
+ location
.hash
144 redef fun to_s
do return "\{{variable}: {location.line_start}\}"