Stack overflow when specializing generic type instances #851
Comments
|
The following standalone program reproduces this stack overflow: |
|
An alternative an even simpler way to reproduce the problem: |
|
Looking at the code, we seem to be running into a case where we're specializing some type The challenge here is that we can't generate these final instances ahead of time as doing so requires the specialization key to be present, but we can't generate the key because we get stuck in a recursive type. The first step here is figuring out what exactly the recursive type is, and if we should be running into such recursive types in the first place. |
|
The recursions seems to involve one type parameter being assigned to another, which then leads back to the former: diff --git a/types/src/specialize.rs b/types/src/specialize.rs
index ee9df306..f7cddee1 100644
--- a/types/src/specialize.rs
+++ b/types/src/specialize.rs
@@ -340,6 +340,16 @@ impl<'a, 'b, 'c> TypeSpecializer<'a, 'b, 'c> {
.into_iter()
.map(|p| {
let raw = args.get(p).unwrap();
+
+ // TODO: remove
+ println!(
+ "param {} ({:?}) = type {} ({:?})",
+ crate::format::format_type(self.db, p),
+ p,
+ crate::format::format_type(self.db, raw),
+ raw
+ );
+
let typ = self.specialize(raw);
args.assign(p, typ);Produces: |
|
I did some further digging using this patch: diff --git a/types/src/specialize.rs b/types/src/specialize.rs
index ee9df306..977439bb 100644
--- a/types/src/specialize.rs
+++ b/types/src/specialize.rs
@@ -335,11 +335,30 @@ impl<'a, 'b, 'c> TypeSpecializer<'a, 'b, 'c> {
}
let mut args = ins.type_arguments(self.db).unwrap().clone();
+
+ println!(
+ "\ntype = {} ({:?})\nshapes = {:?}\nargs = {:?}",
+ crate::format::format_type(self.db, ins),
+ ins,
+ self.shapes,
+ args,
+ );
+
let mut shapes: Vec<Shape> = typ
.type_parameters(self.db)
.into_iter()
.map(|p| {
let raw = args.get(p).unwrap();
8000
+
+ // TODO: remove
+ println!(
+ " {} ({:?}) = {} ({:?})",
+ crate::format::format_type(self.db, p),
+ p,
+ crate::format::format_type(self.db, raw),
+ raw,
+ );
+
let typ = self.specialize(raw);
args.assign(p, typ);This produces: Here it seems that |
|
If I apply this patch: diff --git a/std/src/std/tuple.inko b/std/src/std/tuple.inko
index 257a44db..77e16d1a 100644
--- a/std/src/std/tuple.inko
+++ b/std/src/std/tuple.inko
@@ -76,31 +76,31 @@ impl Format for Tuple1 if A: Format {
}
# A 2-ary tuple.
-type builtin Tuple2[A, B] {
- let pub @0: A
+type builtin Tuple2[FOO, B] {
+ let pub @0: FOO
let pub @1: B
}
-impl Equal for Tuple2 if A: Equal, B: Equal {
- fn pub ==(other: ref Tuple2[A, B]) -> Bool {
+impl Equal for Tuple2 if FOO: Equal, B: Equal {
+ fn pub ==(other: ref Tuple2[FOO, B]) -> Bool {
@0 == other.0 and @1 == other.1
}
}
-impl Hash for Tuple2 if A: Hash, B: Hash {
+impl Hash for Tuple2 if FOO: Hash, B: Hash {
fn pub hash[H: mut + Hasher](hasher: mut H) {
@0.hash(hasher)
@1.hash(hasher)
}
}
-impl Clone for Tuple2 if A: Clone, B: Clone {
- fn pub clone -> Tuple2[move A, move B] {
+impl Clone for Tuple2 if FOO: Clone, B: Clone {
+ fn pub clone -> Tuple2[move FOO, move B] {
(@0.clone, @1.clone)
}
}
-impl Format for Tuple2 if A: Format, B: Format {
+impl Format for Tuple2 if FOO: Format, B: Format {
fn pub fmt(formatter: mut Formatter) {
formatter.tuple('').field(@0).field(@1).finish
}
diff --git a/types/src/specialize.rs b/types/src/specialize.rs
index ee9df306..f8bef771 100644
--- a/types/src/specialize.rs
+++ b/types/src/specialize.rs
@@ -335,11 +335,46 @@ impl<'a, 'b, 'c> TypeSpecializer<'a, 'b, 'c> {
}
let mut args = ins.type_arguments(self.db).unwrap().clone();
+
+ println!("\n{} ({:?})", crate::format::format_type(self.db, ins), ins,);
+
+ println!("type arguments:");
+
+ for (k, v) in args.pairs() {
+ println!(
+ " {} = {} ({:?} = {:?})",
+ crate::format::format_type(self.db, k),
+ crate::format::format_type(self.db, v),
+ k,
+ v,
+ );
+ }
+
+ println!("shapes:");
+ for (k, v) in self.shapes {
+ println!(
+ " {} ({:?}) = {:?}",
+ crate::format::format_type(self.db, *k),
+ k,
+ v,
+ );
+ }
+
let mut shapes: Vec<Shape> = typ
.type_parameters(self.db)
.into_iter()
.map(|p| {
let raw = args.get(p).unwrap();
+
+ // TODO: remove
+ println!(
+ " {} ({:?}) = {} ({:?})",
+ crate::format::format_type(self.db, p),
+ p,
+ crate::format::format_type(self.db, raw),
+ raw,
+ );
+
let typ = self.specialize(raw);
args.assign(p, typ);The output is as follows: Here |
|
To add: the |
|
This problem isn't present in 0.17.1 but is in 0.18.1. I'm guessing this is due to the introduction of stack allocated types and how it changes the specialization logic. |
|
Standalone input file that reproduces the issue: |
|
I'm contemplating if we should just switch to specializing over all types instead of grouping them together. The idea of grouping was to reduce the amount of generated methods, but I'm not sure that was ever true to begin with. For example, if a method Due to inlining of generic methods, we're also already sort of specializing over types but in an ad-hoc manner, at least if the receiver type is a concrete type. This means that whatever duplication full specialization may cause is already there to some degree. The specialization setup is also quite complex and has been a source of quite a few bugs. In particular, reducing a set of types to a set of shapes and then expanding them (in case of inline types for example) to types is messy. If we specialize by all types, I think the code setup as a whole would be a lot easier. Instead of shapes, the specialization keys would just be the (normalized) type arguments. For symbol name generation we'd just use the mangled symbol names of each type, similar to what we do for the With all that said, this would be a pretty big change so I'll have to give it some additional thought first. |
|
Not directly related, but worth considering: I ran into a new instance of #666 when working on the upcoming Rather than spend hours trying to figure this out and fix it, I think this is yet another reason to move to just full on specialization instead of using shapes. |
|
Seeing how CI just keeps failing now with duplicate symbol errors, it's time to take a wrecking ball to our specialisation code and A) just specialise over all types instead of shapes B) hopefully fix these symbol errors. This will probably take a few days though. |
|
As a small update: I started work on this last week, and will continue this week. Progress is a bit slow though, as I'm re-evaluating past decisions related to specialization as I go along. |
Please describe the bug
While refactoring
std.optparseI ran into the following stack overflow:The input file is as follows:
The standard library state is as follows:
Operating system
Fedora
Inko version
main
The text was updated successfully, but these errors were encountered: