nitsaf: introduce reaching defs analysis

Signed-off-by: Alexandre Terrasa <alexandre@moz-code.org>

diff --git a/src/saf/reaching_defs.nit b/src/saf/reaching_defs.nit
new file mode 100644 (file)
index 0000000..9a5b953
--- /dev/null
+++ b/src/saf/reaching_defs.nit
@@ -0,0 +1,114 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# 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.
+
+# Analysis that determines which definitions may reach a given point in the code.
+import saf_base
+
+import scope
+
+# Determines wich variables definitions reach each statement.
+class ReachingDefsAnalysis
+       super ForwardAnalysis
+
+       redef type FLOW: FlowHashSet[VarDef]
+
+       # New initial flows are empty (conservative analysis).
+       redef fun new_initial_flow do return new FlowHashSet[VarDef]
+
+       # Perform set union (used for **some path** analysis).
+       redef fun merge(s1, s2) do return s1.flow_union(s2)
+
+       redef fun visit(n) do n.accept_reaching_defs(self)
+
+       # Generate a new variable definition in the `current_outset`.
+       fun gen(variable: Variable, location: Location) do
+               current_outset.add(new VarDef(variable, location))
+       end
+
+       # Kill a variable definition in the `current_outset`.
+       fun kill(variable: Variable) do
+               for vardef in current_outset.to_a do
+                       if vardef.variable == variable then current_outset.remove(vardef)
+               end
+       end
+
+       redef fun pretty_print do
+               for node, outset in outsets do
+                       if outset.is_empty then continue
+                       var values = outset.to_a
+                       default_comparator.sort(values)
+                       print "{node.location.line_end}: {values.join(", ")} out of {node.class_name}"
+               end
+       end
+end
+
+redef class ANode
+
+       # Apply a ReachingDefsAnalysis to `self`.
+       fun accept_reaching_defs(v: ReachingDefsAnalysis) do accept_forward_analysis(v)
+end
+
+redef class AVardeclExpr
+       redef fun accept_reaching_defs(v) do
+               super
+               v.kill(variable.as(not null))
+               v.gen(variable.as(not null), location)
+       end
+end
+
+redef class AVarAssignExpr
+       redef fun accept_reaching_defs(v) do
+               super
+               v.kill(variable.as(not null))
+               v.gen(variable.as(not null), location)
+       end
+end
+
+redef class AVarReassignExpr
+       redef fun accept_reaching_defs(v) do
+               super
+               v.kill(variable.as(not null))
+               v.gen(variable.as(not null), location)
+       end
+end
+
+# A Variable definition.
+#
+# Associates a variable to the location of its definition.
+class VarDef
+       super Comparable
+
+       redef type OTHER: VarDef
+
+       # Variable this definition is about.
+       var variable: Variable
+
+       # Location of this definition in the source code.
+       var location: Location
+
+       redef fun ==(o) do
+               return o isa OTHER and variable == o.variable and location == o.location
+       end
+
+       redef fun <=>(o) do
+               if variable.name == o.variable.name then
+                       return location.line_start <=> o.location.line_start
+               else
+                       return variable.name <=> o.variable.name
+               end
+       end
+
+       redef fun hash do return variable.hash + location.hash
+       redef fun to_s do return "\{{variable}: {location.line_start}\}"
+end

diff --git a/src/saf/saf.nit b/src/saf/saf.nit
index f087f63..dd8ba31 100644 (file)
--- a/src/saf/saf.nit
+++ b/src/saf/saf.nit
@@ -15,4 +15,4 @@
 # Nit Static Analysis Framework.
 module saf
 
-import saf_base
+import reaching_defs