rta: resolve the open-types in a depth-first order to reach limit faster

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

diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit
index c072314..2d621e8 100644 (file)
--- a/src/rapid_type_analysis.nit
+++ b/src/rapid_type_analysis.nit
@@ -314,7 +314,9 @@ class RapidTypeAnalysis
                                if not check_depth(rt) then continue
                                #print "{ot}/{t} -> {rt}"
                                live_types.add(rt)
-                               todo_types.add(rt)
+                               # unshift means a deep-first visit.
+                               # So that the `check_depth` limit is reached sooner.
+                               todo_types.unshift(rt)
                        end
                end
                #print "MType {live_types.length}: {live_types.join(", ")}"

diff --git a/tests/base_gen_infinite2.nit b/tests/base_gen_infinite2.nit
new file mode 100644 (file)
index 0000000..05c4fb6
--- /dev/null
+++ b/tests/base_gen_infinite2.nit
@@ -0,0 +1,32 @@
+# 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 end
+
+interface Object
+       type SELF: Object
+       fun output_class_name is intern
+end
+
+class A[E]
+       new do return new B[E]
+end
+
+class B[E]
+       super A[E]
+
+       fun foo: A[E] do return new A[SELF]
+end
+
+(new B[Object]).foo.output_class_name

diff --git a/tests/sav/base_gen_infinite2.res b/tests/sav/base_gen_infinite2.res
new file mode 100644 (file)
index 0000000..e38f38e
--- /dev/null
+++ b/tests/sav/base_gen_infinite2.res
@@ -0,0 +1 @@
+B[B[Object]]

diff --git a/tests/sav/nitce/base_gen_infinite2.res b/tests/sav/nitce/base_gen_infinite2.res
new file mode 100644 (file)
index 0000000..223b783
--- /dev/null
+++ b/tests/sav/nitce/base_gen_infinite2.res
@@ -0,0 +1 @@
+B

diff --git a/tests/sav/nitcg/fixme/base_gen_infinite2.res b/tests/sav/nitcg/fixme/base_gen_infinite2.res
new file mode 100644 (file)
index 0000000..2f63d29
--- /dev/null
+++ b/tests/sav/nitcg/fixme/base_gen_infinite2.res
@@ -0,0 +1 @@
+Fatal Error: limitation in the rapidtype analysis engine: a type depth of 256 is too important, the problematic type is `A[A[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[Sys]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]`.

diff --git a/tests/sav/nitcs/fixme/base_gen_infinite2.res b/tests/sav/nitcs/fixme/base_gen_infinite2.res
new file mode 100644 (file)
index 0000000..2f63d29
--- /dev/null
+++ b/tests/sav/nitcs/fixme/base_gen_infinite2.res
@@ -0,0 +1 @@
+Fatal Error: limitation in the rapidtype analysis engine: a type depth of 256 is too important, the problematic type is `A[A[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[Sys]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]`.

diff --git a/tests/sav/nitcsg/fixme/base_gen_infinite2.res b/tests/sav/nitcsg/fixme/base_gen_infinite2.res
new file mode 100644 (file)
index 0000000..2f63d29
--- /dev/null
+++ b/tests/sav/nitcsg/fixme/base_gen_infinite2.res
@@ -0,0 +1 @@
+Fatal Error: limitation in the rapidtype analysis engine: a type depth of 256 is too important, the problematic type is `A[A[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[B[Sys]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]`.