nitsaf: add loop flow set merge

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

diff --git a/src/saf/reaching_defs.nit b/src/saf/reaching_defs.nit
index 9a5b953..bb4ee2a 100644 (file)
--- a/src/saf/reaching_defs.nit
+++ b/src/saf/reaching_defs.nit
@@ -83,6 +83,24 @@ redef class AVarReassignExpr
        end
 end
 
+redef class AForExpr
+       redef fun accept_reaching_defs(v) do
+               # add variables from `for` declaration
+               for n_group in n_groups do
+                       var variables = n_group.variables
+                       if variables == null then continue
+                       for variable in variables do v.gen(variable, n_group.location)
+               end
+               super
+               # remove variables from `for` declaration
+               for n_group in n_groups do
+                       var variables = n_group.variables
+                       if variables == null then continue
+                       for variable in variables do v.kill(variable)
+               end
+       end
+end
+
 # A Variable definition.
 #
 # Associates a variable to the location of its definition.

diff --git a/src/saf/saf_base.nit b/src/saf/saf_base.nit
index 48f5cbf..26d55ba 100644 (file)
--- a/src/saf/saf_base.nit
+++ b/src/saf/saf_base.nit
@@ -156,3 +156,74 @@ redef class AIfExpr
                v.current_outset = outset
        end
 end
+
+# Represent all kind of `do .. end` blocks.
+#
+# Used to factorize implementations across do blocks, whiles, fors and loops.
+#
+# This factorization makes sense since all these contructs can be flow managed
+# through contine and breack statements.
+#
+# TODO move this up in the module hierarchy
+interface ADoBlockHelper
+       # Lookup fix point for this loop.
+       fun loop_fix_point(v: StaticAnalysis, node: ANode) do
+               var inset = v.current_inset.clone
+               var last: nullable FlowSet = null
+               while v.current_outset != last do
+                       v.enter_visit(node)
+                       v.current_inset = v.merge(inset, v.current_outset)
+                       v.current_outset = v.current_inset.clone
+                       last = v.current_outset.clone
+               end
+               v.current_inset = inset
+               v.current_outset = v.merge(inset, v.current_outset)
+       end
+
+       # Factorize loop forward analysis.
+       fun accept_loop_forward_analysis(v: StaticAnalysis) do
+               var n_block = loop_block
+               if not n_block == null then loop_fix_point(v, n_block)
+       end
+
+       # The block contained by this loop.
+       fun loop_block: nullable ANode is abstract
+end
+
+redef class ADoExpr
+       super ADoBlockHelper
+
+       redef fun loop_block do return self.n_block
+       redef fun accept_forward_analysis(v) do accept_loop_forward_analysis(v)
+end
+
+redef class ALoopExpr
+       super ADoBlockHelper
+
+       redef fun loop_block do return self.n_block
+       redef fun accept_forward_analysis(v) do accept_loop_forward_analysis(v)
+end
+
+redef class AWhileExpr
+       super ADoBlockHelper
+
+       redef fun loop_block do return self.n_block
+
+       redef fun accept_forward_analysis(v) do
+               v.enter_visit(n_expr)
+               accept_loop_forward_analysis(v)
+       end
+end
+
+redef class AForExpr
+       super ADoBlockHelper
+
+       redef fun loop_block do return self.n_block
+
+       redef fun accept_forward_analysis(v) do
+               for n_group in n_groups do
+                       v.enter_visit(n_group.n_expr)
+               end
+               accept_loop_forward_analysis(v)
+       end
+end

diff --git a/tests/nitsaf.args b/tests/nitsaf.args
index 386bf16..03db9f4 100644 (file)
--- a/tests/nitsaf.args
+++ b/tests/nitsaf.args
@@ -3,3 +3,6 @@
 --analysis reaching-defs test_saf/flow_if1.nit
 --analysis reaching-defs test_saf/flow_if2.nit
 --analysis reaching-defs test_saf/flow_if3.nit
+--analysis reaching-defs test_saf/flow_loop1.nit
+--analysis reaching-defs test_saf/flow_loop2.nit
+--analysis reaching-defs test_saf/flow_loop3.nit

diff --git a/tests/sav/nitsaf_args6.res b/tests/sav/nitsaf_args6.res
new file mode 100644 (file)
index 0000000..d7e0096
--- /dev/null
+++ b/tests/sav/nitsaf_args6.res
@@ -0,0 +1,15 @@
+15: {x: 15} out of AListExprs
+15: {x: 15} out of ACallExpr
+15: {x: 15} out of AVardeclExpr
+17: {x: 15} out of TId
+17: {x: 15} out of TPluseq
+17: {x: 15} out of APlusAssignOp
+17: {x: 17} out of TInteger
+17: {x: 17} out of AIntegerExpr
+17: {x: 17} out of AVarReassignExpr
+18: {x: 17} out of TKwend
+18: {x: 17} out of ABlockExpr
+18: {x: 17} out of ABlockExpr
+18: {x: 17} out of AMainMethPropdef
+18: {x: 17} out of AMainClassdef
+18: {x: 17} out of AModule

diff --git a/tests/sav/nitsaf_args7.res b/tests/sav/nitsaf_args7.res
new file mode 100644 (file)
index 0000000..0395dc5
--- /dev/null
+++ b/tests/sav/nitsaf_args7.res
@@ -0,0 +1,60 @@
+15: {x: 15} out of AListExprs
+15: {x: 15} out of ACallExpr
+15: {x: 15} out of AVardeclExpr
+16: {x: 15} out of TId
+16: {x: 15} out of AVarExpr
+16: {x: 15} out of TLt
+16: {x: 15} out of TInteger
+16: {x: 15} out of AIntegerExpr
+16: {x: 15} out of ALtExpr
+17: {x: 15} out of TId
+17: {x: 15} out of TPluseq
+17: {x: 15} out of APlusAssignOp
+17: {x: 17} out of TId
+17: {x: 17} out of AVarExpr
+17: {x: 17} out of AVarReassignExpr
+18: {x: 17} out of TKwvar
+18: {x: 17} out of TId
+18: {x: 17} out of TAssign
+18: {x: 17} out of AImplicitSelfExpr
+18: {x: 17} out of TId
+18: {x: 17} out of AQid
+18: {x: 17} out of AListExprs
+18: {x: 17} out of ACallExpr
+18: {x: 17} out of TId
+18: {x: 17} out of AQid
+18: {x: 17}, {y: 18} out of AListExprs
+18: {x: 17}, {y: 18} out of ACallExpr
+18: {x: 17}, {y: 18} out of AVardeclExpr
+19: {x: 17}, {y: 18} out of AImplicitSelfExpr
+19: {x: 17}, {y: 18} out of TId
+19: {x: 17}, {y: 18} out of AQid
+19: {x: 17}, {y: 18} out of TId
+19: {x: 17}, {y: 18} out of AVarExpr
+19: {x: 17}, {y: 18} out of AListExprs
+19: {x: 17}, {y: 18} out of ACallExpr
+20: {x: 17}, {y: 18} out of TKwend
+20: {x: 17}, {y: 18} out of ABlockExpr
+21: {x: 15}, {x: 17}, {y: 18} out of AImplicitSelfExpr
+21: {x: 15}, {x: 17}, {y: 18} out of TId
+21: {x: 15}, {x: 17}, {y: 18} out of AQid
+21: {x: 15}, {x: 17}, {y: 18} out of TId
+21: {x: 15}, {x: 17}, {y: 18} out of AVarExpr
+21: {x: 15}, {x: 17}, {y: 18} out of AListExprs
+21: {x: 15}, {x: 17}, {y: 18} out of ACallExpr
+22: {x: 15}, {x: 17}, {y: 18} out of TId
+22: {x: 15}, {x: 17}, {y: 18} out of TAssign
+22: {x: 22}, {y: 18} out of TInteger
+22: {x: 22}, {y: 18} out of AIntegerExpr
+22: {x: 22}, {y: 18} out of AVarAssignExpr
+23: {x: 22}, {y: 18} out of AImplicitSelfExpr
+23: {x: 22}, {y: 18} out of TId
+23: {x: 22}, {y: 18} out of AQid
+23: {x: 22}, {y: 18} out of TId
+23: {x: 22}, {y: 18} out of AVarExpr
+23: {x: 22}, {y: 18} out of AListExprs
+23: {x: 22}, {y: 18} out of ACallExpr
+23: {x: 22}, {y: 18} out of ABlockExpr
+23: {x: 22}, {y: 18} out of AMainMethPropdef
+23: {x: 22}, {y: 18} out of AMainClassdef
+23: {x: 22}, {y: 18} out of AModule

diff --git a/tests/sav/nitsaf_args8.res b/tests/sav/nitsaf_args8.res
new file mode 100644 (file)
index 0000000..cac98bf
--- /dev/null
+++ b/tests/sav/nitsaf_args8.res
@@ -0,0 +1,74 @@
+15: {x: 15} out of AListExprs
+15: {x: 15} out of ACallExpr
+15: {x: 15} out of AVardeclExpr
+16: {x: 15} out of TKwvar
+16: {x: 15} out of TId
+16: {x: 15} out of TAssign
+16: {x: 15} out of AImplicitSelfExpr
+16: {x: 15} out of TId
+16: {x: 15} out of AQid
+16: {x: 15} out of AListExprs
+16: {x: 15} out of ACallExpr
+16: {x: 15} out of TId
+16: {x: 15} out of AQid
+16: {i: 17}, {x: 15}, {y: 16} out of AListExprs
+16: {i: 17}, {x: 15}, {y: 16} out of ACallExpr
+16: {i: 17}, {x: 15}, {y: 16} out of AVardeclExpr
+17: {i: 17}, {x: 15}, {y: 16} out of TObra
+17: {i: 17}, {x: 15}, {y: 16} out of TId
+17: {i: 17}, {x: 15}, {y: 16} out of AVarExpr
+17: {i: 17}, {x: 15}, {y: 16} out of TDotdot
+17: {i: 17}, {x: 15}, {y: 16} out of TId
+17: {i: 17}, {x: 15}, {y: 16} out of AVarExpr
+17: {i: 17}, {x: 15}, {y: 16} out of TCbra
+17: {i: 17}, {x: 15}, {y: 16} out of ACrangeExpr
+18: {i: 17}, {x: 15}, {y: 16} out of TId
+18: {i: 17}, {x: 15}, {y: 16} out of TPluseq
+18: {i: 17}, {x: 15}, {y: 16} out of APlusAssignOp
+18: {i: 17}, {x: 18}, {y: 16} out of TId
+18: {i: 17}, {x: 18}, {y: 16} out of AVarExpr
+18: {i: 17}, {x: 18}, {y: 16} out of AVarReassignExpr
+19: {i: 17}, {x: 18}, {y: 16} out of TId
+19: {i: 17}, {x: 18}, {y: 16} out of TAssign
+19: {i: 17}, {x: 18}, {y: 16} out of AImplicitSelfExpr
+19: {i: 17}, {x: 18}, {y: 16} out of TId
+19: {i: 17}, {x: 18}, {y: 16} out of AQid
+19: {i: 17}, {x: 18}, {y: 16} out of AListExprs
+19: {i: 17}, {x: 18}, {y: 16} out of ACallExpr
+19: {i: 17}, {x: 18}, {y: 16} out of TId
+19: {i: 17}, {x: 18}, {y: 16} out of AQid
+19: {i: 17}, {x: 18}, {y: 19} out of AListExprs
+19: {i: 17}, {x: 18}, {y: 19} out of ACallExpr
+19: {i: 17}, {x: 18}, {y: 19} out of AVarAssignExpr
+20: {i: 17}, {x: 18}, {y: 19} out of AImplicitSelfExpr
+20: {i: 17}, {x: 18}, {y: 19} out of TId
+20: {i: 17}, {x: 18}, {y: 19} out of AQid
+20: {i: 17}, {x: 18}, {y: 19} out of TId
+20: {i: 17}, {x: 18}, {y: 19} out of AVarExpr
+20: {i: 17}, {x: 18}, {y: 19} out of AListExprs
+20: {i: 17}, {x: 18}, {y: 19} out of ACallExpr
+21: {i: 17}, {x: 18}, {y: 19} out of TKwend
+21: {i: 17}, {x: 18}, {y: 19} out of ABlockExpr
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of AImplicitSelfExpr
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of TId
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of AQid
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of TId
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of AVarExpr
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of AListExprs
+22: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of ACallExpr
+23: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of TId
+23: {x: 15}, {x: 18}, {y: 16}, {y: 19} out of TAssign
+23: {x: 23}, {y: 16}, {y: 19} out of TInteger
+23: {x: 23}, {y: 16}, {y: 19} out of AIntegerExpr
+23: {x: 23}, {y: 16}, {y: 19} out of AVarAssignExpr
+24: {x: 23}, {y: 16}, {y: 19} out of AImplicitSelfExpr
+24: {x: 23}, {y: 16}, {y: 19} out of TId
+24: {x: 23}, {y: 16}, {y: 19} out of AQid
+24: {x: 23}, {y: 16}, {y: 19} out of TId
+24: {x: 23}, {y: 16}, {y: 19} out of AVarExpr
+24: {x: 23}, {y: 16}, {y: 19} out of AListExprs
+24: {x: 23}, {y: 16}, {y: 19} out of ACallExpr
+24: {x: 23}, {y: 16}, {y: 19} out of ABlockExpr
+24: {x: 23}, {y: 16}, {y: 19} out of AMainMethPropdef
+24: {x: 23}, {y: 16}, {y: 19} out of AMainClassdef
+24: {x: 23}, {y: 16}, {y: 19} out of AModule

diff --git a/tests/test_saf/flow_loop1.nit b/tests/test_saf/flow_loop1.nit
new file mode 100644 (file)
index 0000000..1b4e566
--- /dev/null
+++ b/tests/test_saf/flow_loop1.nit
@@ -0,0 +1,18 @@
+# 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.
+
+var x = gets.to_i
+loop
+       x += 1
+end

diff --git a/tests/test_saf/flow_loop2.nit b/tests/test_saf/flow_loop2.nit
new file mode 100644 (file)
index 0000000..6e2e4da
--- /dev/null
+++ b/tests/test_saf/flow_loop2.nit
@@ -0,0 +1,23 @@
+# 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.
+
+var x = gets.to_i
+while x < 1 do
+       x += x
+       var y = gets.to_i
+       print y
+end
+print x
+x = 0
+print x

diff --git a/tests/test_saf/flow_loop3.nit b/tests/test_saf/flow_loop3.nit
new file mode 100644 (file)
index 0000000..fd49d91
--- /dev/null
+++ b/tests/test_saf/flow_loop3.nit
@@ -0,0 +1,24 @@
+# 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.
+
+var x = gets.to_i
+var y = gets.to_i
+for i in [x..y] do
+       x += x
+       y = gets.to_i
+       print y
+end
+print x
+x = 0
+print x