rta: limit the depth of types to avoid infinite loops

Signed-off-by: Jean Privat <jean@pryen.org>

diff --git a/src/model/model.nit b/src/model/model.nit
index 635d34a..dbaf282 100644 (file)
--- a/src/model/model.nit
+++ b/src/model/model.nit
@@ -683,6 +683,20 @@ abstract class MType
 
        private var as_nullable_cache: nullable MType = null
 
+
+       # The deph of the type seen as a tree.
+       #
+       # A -> 1
+       # G[A] -> 2
+       # H[A, B] -> 2
+       # H[G[A], B] -> 3
+       #
+       # Formal types have a depth of 1.
+       fun depth: Int
+       do
+               return 1
+       end
+
        # Compute all the classdefs inherited/imported.
        # The returned set contains:
        #  * the class definitions from `mmodule` and its imported modules
@@ -852,6 +866,16 @@ class MGenericType
                end
                return mclass.get_mtype(types)
        end
+
+       redef fun depth
+       do
+               var dmax = 0
+               for a in self.arguments do
+                       var d = a.depth
+                       if d > dmax then dmax = d
+               end
+               return dmax + 1
+       end
 end
 
 # A virtual formal type.
@@ -1047,6 +1071,8 @@ class MNullableType
                return res.as_nullable
        end
 
+       redef fun depth do return self.mtype.depth
+
        redef fun collect_mclassdefs(mmodule)
        do
                assert not self.need_anchor
@@ -1100,6 +1126,22 @@ class MSignature
        # The return type (null for a procedure)
        var return_mtype: nullable MType
 
+       redef fun depth
+       do
+               var dmax = 0
+               var t = self.return_mtype
+               if t != null then dmax = t.depth
+               for p in mparameters do
+                       var d = p.mtype.depth
+                       if d > dmax then dmax = d
+               end
+               for p in mclosures do
+                       var d = p.mtype.depth
+                       if d > dmax then dmax = d
+               end
+               return dmax + 1
+       end
+
        # REQUIRE: 1 <= mparameters.count p -> p.is_vararg
        init(mparameters: Array[MParameter], return_mtype: nullable MType)
        do

diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit
index cec5e78..1d41c34 100644 (file)
--- a/src/rapid_type_analysis.nit
+++ b/src/rapid_type_analysis.nit
@@ -113,6 +113,7 @@ class RapidTypeAnalysis
 
                assert not mtype.need_anchor
                self.live_types.add(mtype)
+               self.check_depth(mtype)
 
                # Collect default attributes
                for cd in mtype.collect_mclassdefs(self.mainmodule)
@@ -185,6 +186,15 @@ class RapidTypeAnalysis
 
                assert not mtype.need_anchor
                self.live_cast_types.add(mtype)
+               self.check_depth(mtype)
+       end
+
+       fun check_depth(mtype: MClassType)
+       do
+               var d = mtype.depth
+               if d > 255 then
+                       self.modelbuilder.toolcontext.fatal_error(null, "Fatal error: limitation in the rapidtype analysis engine: a type depth of {d} is too important, the problematic type is {mtype}.")
+               end
        end
 
        # Run the analysis until all visitable method definitions are visited.

diff --git a/tests/base_gen_infinite.nit b/tests/base_gen_infinite.nit
new file mode 100644 (file)
index 0000000..4bcce60
--- /dev/null
+++ b/tests/base_gen_infinite.nit
@@ -0,0 +1,41 @@
+# 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.
+
+import kernel
+
+class G[E: Object]
+       var sub: E
+
+       fun explode(i: Int): G[Object]
+       do
+               if i<=0 then return self
+               var gge = new G[G[E]](self)
+               return gge.explode(i-1)
+       end
+
+       fun count: Int
+       do
+               var e: Object = self.sub
+               if e isa G[Object] then return e.count + 1 else return 1
+       end
+end
+
+var g1 = new G[Int](1)
+g1.count.output
+var g2 = new G[G[Int]](g1)
+g2.count.output
+var g3 = g1.explode(2)
+g3.count.output
+var g30 = g1.explode(29)
+g30.count.output

diff --git a/tests/sav/base_gen_infinite.res b/tests/sav/base_gen_infinite.res
new file mode 100644 (file)
index 0000000..c2ab612
--- /dev/null
+++ b/tests/sav/base_gen_infinite.res
@@ -0,0 +1,4 @@
+1
+2
+3
+30

diff --git a/tests/sav/nitg/fixme/base_gen_infinite.res b/tests/sav/nitg/fixme/base_gen_infinite.res
new file mode 100644 (file)
index 0000000..4fff55f
--- /dev/null
+++ b/tests/sav/nitg/fixme/base_gen_infinite.res
@@ -0,0 +1 @@
+Fatal error: limitation in the rapidtype analysis engine: a type depth of 256 is too important, the problematic type is G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[G[Int]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]].