From faf4b5e72a92e96b44f2020a81387bf8417c52cc Mon Sep 17 00:00:00 2001 From: Jean Privat Date: Wed, 21 Nov 2012 13:36:25 -0500 Subject: [PATCH] rta: limit the depth of types to avoid infinite loops Signed-off-by: Jean Privat --- src/model/model.nit | 42 ++++++++++++++++++++++++++++ src/rapid_type_analysis.nit | 10 +++++++ tests/base_gen_infinite.nit | 41 +++++++++++++++++++++++++++ tests/sav/base_gen_infinite.res | 4 +++ tests/sav/nitg/fixme/base_gen_infinite.res | 1 + 5 files changed, 98 insertions(+) create mode 100644 tests/base_gen_infinite.nit create mode 100644 tests/sav/base_gen_infinite.res create mode 100644 tests/sav/nitg/fixme/base_gen_infinite.res diff --git a/src/model/model.nit b/src/model/model.nit index 635d34a..dbaf282 100644 --- 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 --- 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 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 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 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]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]. -- 1.7.9.5