nitsaf: introduce Nit Static Analysis Framework

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

diff --git a/src/saf/saf.nit b/src/saf/saf.nit
new file mode 100644 (file)
index 0000000..f087f63
--- /dev/null
+++ b/src/saf/saf.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.
+
+# Nit Static Analysis Framework.
+module saf
+
+import saf_base

diff --git a/src/saf/saf_base.nit b/src/saf/saf_base.nit
new file mode 100644 (file)
index 0000000..806b711
--- /dev/null
+++ b/src/saf/saf_base.nit
@@ -0,0 +1,133 @@
+# 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.
+
+# Static Analysis Framework base
+#
+# A lot of TODOs still missing:
+# * flow breaks (AReturnExpr, AEscapeExpr, AAbortExpr)
+# * other conditionnals (AIfexprExpr, AAssertExpr, ABonBoolExpr)
+# * flow through AAttrPropDef
+module saf_base
+
+import modelbuilder
+
+# The base of all analysis performed statically.
+abstract class StaticAnalysis
+       super Visitor
+
+       # Type of FlowSet representation used by the StaticAnalysis.
+       type FLOW: FlowSet
+
+       # "in" set for the currently visited node.
+       var current_inset: FLOW is noinit, writable
+
+       # 'out' set for the currently visited node.
+       var current_outset: FLOW is noinit, writable
+
+       # Sets at the entry of each node.
+       #
+       # Each node is associated with the `current_inset` it got.
+       var insets = new HashMap[ANode, FLOW]
+
+       # Sets at the exit of each node.
+       #
+       # Each node is associated with the `current_outset` it got.
+       var outsets = new HashMap[ANode, FLOW]
+
+       init do
+               current_inset = new_initial_flow
+               current_outset = new_initial_flow
+       end
+
+       # Initial flow set to use.
+       #
+       # Because the initial flow set depends on the analysis performed, the
+       # implementation of this method is the responsability the subclass.
+       fun new_initial_flow: FLOW is abstract
+
+       # The merge operation on sets for confluence.
+       #
+       # Depends on the analysis performed.
+       fun merge(s1, s2: FLOW): FLOW is abstract
+
+       # ModelBuilder used to lookup AST nodes.
+       var modelbuilder: ModelBuilder
+
+       # Run `self` on an AST `node`.
+       fun start_analysis(node: ANode) do visit(node)
+
+       # Pretty print the outsets of this analysis.
+       #
+       # Mainly used for debug and testing.
+       fun pretty_print is abstract
+end
+
+# An analysis go forward from the entry point to the exit point.
+#
+# With a forward analysis, output properties are determined by the inputs.
+class ForwardAnalysis
+       super StaticAnalysis
+
+       redef fun visit(n) do n.accept_forward_analysis(self)
+end
+
+# FlowSet are used to represent data at the entry and exit of a statement.
+interface FlowSet
+       super Cloneable
+
+       # Merge `self` with another flow set.
+       fun flow_union(o: SELF): SELF is abstract
+end
+
+# A FlowSet based on a HashMap.
+class FlowHashMap[K, V]
+       super FlowSet
+       super HashMap[K, V]
+
+       # Init `self` with the content of `map`.
+       init from(map: Map[K, V]) do
+               init
+               for k, v in map do self[k] = v
+       end
+
+       # Not a deep copy.
+       redef fun clone do return new FlowHashMap[K, V].from(self)
+end
+
+# A FlowSet based on a HashSet.
+class FlowHashSet[E]
+       super FlowSet
+       super HashSet[E]
+
+       redef fun clone do return new FlowHashSet[E].from(self)
+
+       # Remove all items found in `other` from `self`.
+       fun remove_from(other: Collection[E]) do
+               for e in other do remove(e)
+       end
+
+       redef fun flow_union(o) do return new FlowHashSet[E].from(union(o))
+end
+
+redef class ANode
+
+       # Apply the forward analysis `v` to `self`.
+       fun accept_forward_analysis(v: ForwardAnalysis) do
+               v.current_inset = v.current_outset.clone
+               v.current_outset = v.current_inset.clone
+               v.insets[self] = v.current_inset
+               visit_all(v)
+               v.outsets[self] = v.current_outset
+       end
+end