cde99bd | plum | pyrossh

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

cde99bd — Peter John 2026-09-03T14:06:30+05:30

fix(plum-checker): stop the self-nesting generic-method stack overflow

Files changed (2) hide show

libs/std/list.plum +24 -19
plum-checker/src/monomorphize.rs +148 -65

libs/std/list.plum CHANGED Viewed

@@ -369,29 +369,34 @@ type List[T: Stringable](Stringable) =
       i = i - 1
     return result
-  # `partition`/`chunk`/`groupBy` would each need to return `List[List[T]]`
+  # `chunk`/`partition` both return `List[List[T]]` — the SAME generic class
-  # (or `Map[K, List[T]]`) — the SAME generic class (`List`) nested inside
-  # itself as a method's own return type. `methods_generic_on`'s eager
+  # (`List`) nested inside itself as a method's own return type. This used to
-  # registration (`registerClassMethodSignatures` in
+  # be an unconditional stack-overflow landmine for the WHOLE COMPILER (see
-  # `plum-checker/src/monomorphize.rs`, which resolves and registers EVERY
+  # `plum-checker/src/monomorphize.rs`'s `isSelfNested`/`methodMentionsTemplate`
-  # method's signature immediately whenever its owning class is specialized
+  # doc comments for the full fix) — that danger is now FIXED (2026-09-02),
+  # verified: a program merely `import`ing `std/list` with these methods
+  # DEFINED no longer hangs/crashes regardless of whether anything calls
+  # them. `chunk`/`partition` THEMSELVES are still not implemented, though —
-  # at ANY concrete type, not lazily on first actual call) makes that an
+  # actually CALLING them still hits a second, more contained bug: the
-  # infinite regress: specializing `List[X]` resolves `chunk`'s return type
-  # `List[List[X]]`, which is a NEW, different specialization of `List` —
-  # eagerly specializing IT immediately re-triggers the exact same
-  # registration for ITS OWN `chunk`, needing `List[List[List[X]]]`, forever
+  # specialized `add` method on the resulting `List[List[T]]` (e.g.
-  # (confirmed: adding these methods made even unrelated programs that
+  # `List$List$Int`) gets registered with a WRONG/confused parameter type
-  # merely `import std/list` stack-overflow the compiler, since nothing
-  # needs to actually CALL `chunk` to trigger it — just having it exist on
+  # (`expected List$Int, found Int` and, inconsistently, `expected List$Int,
-  # `List[T]` is enough). Fixing this for real needs lazy (call-site-driven,
+  # found List$List$Int` for the very same key, across different reported
-  # not eager) method specialization, a substantially bigger change than
+  # call sites) — root cause not yet found; suspected signature-registration
-  # this method itself. Not implemented.
+  # aliasing between a self-nested specialization and its own inner
+  # specialization, possibly compounded by both keeping the SAME bare method
+  # name (`specializeFn` never mangles an ordinary method's own name).
-  fun partition(self) =
+  fun chunk(self) =
     todo
-  fun chunk(self) =
+  fun partition(self) =
     todo
+  # Grouping by an arbitrary key type would need its own generic param
+  # (`groupBy<K>(keyFn: fn(T) -> K) -> Map[K, List[T]]`) resolved from a
+  # closure's return type — the same method-level-generics gap documented on
+  # `List.map` above, PLUS `Map[K, List[T]]` would make `list.plum` depend on
+  # `map.plum`, which already depends on `list.plum`. Not implemented.
   fun groupBy(self) =
     todo

plum-checker/src/monomorphize.rs CHANGED Viewed

@@ -1222,7 +1222,7 @@ impl<'a> Monomorphizer<'a> {
     fn registerClassMethodSignatures(&mut self, class: &'a ast::Class, mangled: &str, bindings: &BTreeMap<String, PlumType>) {
         let Some(methods) = self.methods_generic_on.get(class.name.as_str()).cloned() else { return };
         let owner_params = classGenericParams(class);
-        self.registerMethodSignatures(methods, &owner_params, mangled, bindings);
+        self.registerMethodSignatures(&class.name, mangled, methods, &owner_params, bindings);
     }
     /// The enum counterpart to `registerClassMethodSignatures` — see its doc
@@ -1240,7 +1240,7 @@ impl<'a> Monomorphizer<'a> {
     fn registerEnumMethodSignatures(&mut self, e: &'a ast::Enum, mangled: &str, bindings: &BTreeMap<String, PlumType>) {
         let Some(methods) = self.methods_generic_on_enum.get(e.name.as_str()).cloned() else { return };
         let owner_params = enumGenericParams(e);
-        self.registerMethodSignatures(methods, &owner_params, mangled, bindings);
+        self.registerMethodSignatures(&e.name, mangled, methods, &owner_params, bindings);
     }
     /// Shared body of `registerClassMethodSignatures`/`registerEnumMethodSignatures`
@@ -1249,8 +1249,19 @@ impl<'a> Monomorphizer<'a> {
     /// of its own — see the skip below) method in `methods`, for the
     /// specialization named `mangled` under `bindings`, without producing the
     /// actual `ast::Fn` bodies (that still only happens once the worklist
-    /// entry for this specialization is popped).
+    /// entry for this specialization is popped). If this specialization is
+    /// itself already nested (`isSelfNested`), skips (only) a method whose
+    /// return type would construct yet another nested specialization
+    /// (`methodMentionsTemplate`) — the self-nesting landmine. Deliberately
+    /// NOT a blanket skip for every method whenever `mangled` is
+    /// self-nested: `List$List$Int`'s own `add`/`get`/etc are perfectly
+    /// finite regardless (their return types don't mention `List` at all)
+    /// and are needed for `chunk`'s own body (`result.add(piece)`) to even
+    /// compile — only `chunk`/`partition` THEMSELVES, called again on an
+    /// already-nested `List$List$Int`, would recurse into a third level and
+    /// must be skipped.
-    fn registerMethodSignatures(&mut self, methods: Vec<&'a ast::Fn>, owner_params: &[String], mangled: &str, bindings: &BTreeMap<String, PlumType>) {
+    fn registerMethodSignatures(&mut self, template_name: &str, mangled: &str, methods: Vec<&'a ast::Fn>, owner_params: &[String], bindings: &BTreeMap<String, PlumType>) {
+        let already_nested = self.isSelfNested(template_name, bindings);
         for method in methods {
             // See the matching comment in the `PendingSpecialization::Class`/
             // `PendingSpecialization::Enum` worklist arms — a method with its
@@ -1259,6 +1270,9 @@ impl<'a> Monomorphizer<'a> {
             if !methodOwnGenericParams(method, owner_params).is_empty() {
                 continue;
             }
+            if already_nested && Self::methodMentionsTemplate(method, template_name) {
+                continue;
+            }
             let key = (mangled.to_string(), method.name.clone());
             if self.methods.contains_key(&key) {
                 continue;
@@ -1304,6 +1318,50 @@ impl<'a> Monomorphizer<'a> {
         }
     }
+    /// True if the specialization about to be processed is ITSELF already a
+    /// nested instance of `template_name` — one of `bindings`'s VALUES is
+    /// either `template_name` itself or a recorded specialization OF it
+    /// (via `class_specialization_info`), e.g. `List$Int`'s `T` bound to
+    /// `Int` is NOT self-nested, but `List$List$Int`'s `T` bound to
+    /// `List$Int` IS. Guards the self-nesting landmine (a method returning
+    /// its OWN owning class/enum nested in itself, e.g. `List[T].chunk() ->
+    /// List[List[T]]`): resolving `chunk`'s return type for a specialization
+    /// that's ALREADY nested would create yet another, deeper nested
+    /// specialization, forever — and because this eager registration
+    /// happens once per WORKLIST entry (processed iteratively, not
+    /// recursively), a plain call-stack-scoped recursion guard tried first
+    /// was NOT enough to stop it (confirmed: hung 20+s with only that).
+    /// Combined with `methodMentionsTemplate` (only reachable, and only
+    /// meaningful, when this is true) — a specialization's OWN `add`/`get`/
+    /// etc are perfectly finite regardless of nesting and must NOT be
+    /// skipped, only a method whose return type would construct yet ANOTHER
+    /// nested specialization.
+    fn isSelfNested(&self, template_name: &str, bindings: &BTreeMap<String, PlumType>) -> bool {
+        bindings.values().any(|t| match t {
+            PlumType::TNamed(n) => {
+                n == template_name
+                    || self.class_specialization_info.get(n.as_str())
+                        .map(|(base, _)| base == template_name)
+                        .unwrap_or(false)
+            }
+            _ => false,
+        })
+    }
+    /// True if `method`'s OWN declared return type mentions `template_name`
+    /// anywhere (at any nesting depth, INCLUDING the top level — unlike a
+    /// naive structural check, depth doesn't matter here: this is only ever
+    /// consulted once `isSelfNested` has already confirmed the CURRENT
+    /// specialization is itself nested, at which point even a top-level
+    /// `List[...]` return needs a new, deeper nested specialization). See
+    /// `isSelfNested`'s doc comment for the full picture.
+    fn methodMentionsTemplate(method: &ast::Fn, template_name: &str) -> bool {
+        fn mentions(ty: &ast::Type, template_name: &str) -> bool {
+            ty.name == template_name || ty.generics.iter().any(|g| mentions(g, template_name))
+        }
+        method.returns.as_ref().map(|ret| mentions(ret, template_name)).unwrap_or(false)
+    }
     /// Fills `out` with a binding for every bare generic-letter type occurring
     /// in `declared` (possibly nested inside a container type, e.g. `T` inside
     /// `List[T]`), given `actual` — the ACTUAL concrete `PlumType` an argument
@@ -2179,44 +2237,61 @@ pub fn monomorphizeSource(source: &ast::Source) -> Result<ast::Source, String> {
                     spec_class.fields.iter().map(|f| (f.name.clone(), crate::plumTypeFromAst(&f.ty))).collect(),
                 );
                 m.produced.push(ast::Item::Class(spec_class));
+                // Same self-nesting landmine as `registerMethodSignatures` —
+                // if THIS specialization is itself already nested
+                // (`isSelfNested`), skips (only) a method whose return type
+                // would construct yet another nested specialization
+                // (`methodMentionsTemplate`; see `isSelfNested`'s doc
+                // comment). Without this, `List.chunk() -> List[List[T]]`
+                // would recurse into producing an unbounded chain of
+                // ever-more-nested `List` specializations via THIS SAME
+                // loop — and since this loop runs once per separate
+                // WORKLIST pop rather than recursively, a guard scoped to a
+                // single call stack isn't enough on its own.
+                {
+                    let already_nested = m.isSelfNested(&base.name, &subst.0);
-                if let Some(methods) = m.methods_generic_on.get(base.name.as_str()).cloned() {
+                    if let Some(methods) = m.methods_generic_on.get(base.name.as_str()).cloned() {
-                    let owner_params = classGenericParams(base);
+                        let owner_params = classGenericParams(base);
-                    for method in methods {
+                        for method in methods {
-                        // A method with generic param(s) of its OWN (e.g. `map`'s
+                            // A method with generic param(s) of its OWN (e.g. `map`'s
-                        // `U`, beyond `List[T]`'s own `T`) can't be produced HERE —
+                            // `U`, beyond `List[T]`'s own `T`) can't be produced HERE —
-                        // `U` is only known at a particular CALL SITE, not at class-
+                            // `U` is only known at a particular CALL SITE, not at class-
-                        // specialization time. `resolveMethodOwnGenerics` queues a
+                            // specialization time. `resolveMethodOwnGenerics` queues a
-                        // `PendingSpecialization::Fn` for each concrete `U` it
+                            // `PendingSpecialization::Fn` for each concrete `U` it
-                        // actually sees used, instead.
+                            // actually sees used, instead.
-                        if !methodOwnGenericParams(method, &owner_params).is_empty() {
+                            if !methodOwnGenericParams(method, &owner_params).is_empty() {
-                            continue;
+                                continue;
-                        }
+                            }
-                        let mut specialized_method = specializeFn(method, &subst, &method.name, Some(mangled.clone()));
-                        // Params (not returns — see `resolveFnParamTypes`'s doc
-                        // comment) must run before `rewriteFnBody`/registration
-                        // below: both read the signature's types directly off
-                        // this AST, and the real checker later rebuilds its own
-                        // tables from this exact (post-monomorphize) AST too.
-                        m.resolveFnParamTypes(&mut specialized_method);
-                        m.rewriteFnBody(&mut specialized_method, true)?;
-                        m.resolveFnReturnType(&mut specialized_method);
-                        // Register the specialized method's signature under its
-                        // (mangled receiver, method name) key so any later body that
-                        // dispatches to it can resolve its concrete return type.
-                        let param_types: Vec<PlumType> = specialized_method.params.iter().map(|p| match &p.ty {
+                            if already_nested && Monomorphizer::methodMentionsTemplate(method, &base.name) {
-                            ast::ParamType::Type(t) => crate::plumTypeFromAst(t),
-                            ast::ParamType::Variadic(t) => PlumType::TVariadic(Box::new(crate::plumTypeFromAst(t))),
-                            ast::ParamType::Fn(params, ret) => {
+                                continue;
-                                let param_types = params.iter().map(crate::plumTypeFromAst).collect();
-                                let ret_ty = ret.as_ref().map(|r| crate::plumTypeFromAst(r)).unwrap_or(PlumType::TUnit);
-                                PlumType::TFun(param_types, Box::new(ret_ty))
                             }
+                            let mut specialized_method = specializeFn(method, &subst, &method.name, Some(mangled.clone()));
+                            // Params (not returns — see `resolveFnParamTypes`'s doc
+                            // comment) must run before `rewriteFnBody`/registration
+                            // below: both read the signature's types directly off
+                            // this AST, and the real checker later rebuilds its own
+                            // tables from this exact (post-monomorphize) AST too.
+                            m.resolveFnParamTypes(&mut specialized_method);
+                            m.rewriteFnBody(&mut specialized_method, true)?;
+                            m.resolveFnReturnType(&mut specialized_method);
+                            // Register the specialized method's signature under its
+                            // (mangled receiver, method name) key so any later body that
+                            // dispatches to it can resolve its concrete return type.
+                            let param_types: Vec<PlumType> = specialized_method.params.iter().map(|p| match &p.ty {
+                                ast::ParamType::Type(t) => crate::plumTypeFromAst(t),
+                                ast::ParamType::Variadic(t) => PlumType::TVariadic(Box::new(crate::plumTypeFromAst(t))),
+                                ast::ParamType::Fn(params, ret) => {
+                                    let param_types = params.iter().map(crate::plumTypeFromAst).collect();
+                                    let ret_ty = ret.as_ref().map(|r| crate::plumTypeFromAst(r)).unwrap_or(PlumType::TUnit);
+                                    PlumType::TFun(param_types, Box::new(ret_ty))
+                                }
-                        }).collect();
+                            }).collect();
-                        let ret = specialized_method.returns.as_ref()
+                            let ret = specialized_method.returns.as_ref()
-                            .map(crate::plumTypeFromAst)
+                                .map(crate::plumTypeFromAst)
-                            .unwrap_or(PlumType::TUnit);
+                                .unwrap_or(PlumType::TUnit);
-                        m.methods.insert((mangled.clone(), specialized_method.name.clone()), PlumType::TFun(param_types, Box::new(ret)));
+                            m.methods.insert((mangled.clone(), specialized_method.name.clone()), PlumType::TFun(param_types, Box::new(ret)));
-                        m.produced.push(ast::Item::Fn(specialized_method));
+                            m.produced.push(ast::Item::Fn(specialized_method));
+                        }
                     }
                 }
             }
@@ -2256,31 +2331,39 @@ pub fn monomorphizeSource(source: &ast::Source) -> Result<ast::Source, String> {
                     }
                 }
                 m.produced.push(ast::Item::Enum(spec_enum));
+                // Guarded against the same self-nesting landmine as the
+                // `Class` arm above — see `isSelfNested`'s doc comment.
+                {
+                    let already_nested = m.isSelfNested(&base.name, &subst.0);
-                if let Some(methods) = m.methods_generic_on_enum.get(base.name.as_str()).cloned() {
+                    if let Some(methods) = m.methods_generic_on_enum.get(base.name.as_str()).cloned() {
-                    let owner_params = enumGenericParams(base);
+                        let owner_params = enumGenericParams(base);
-                    for method in methods {
+                        for method in methods {
-                        // See the matching comment in the `Class` arm above.
+                            // See the matching comment in the `Class` arm above.
-                        if !methodOwnGenericParams(method, &owner_params).is_empty() {
+                            if !methodOwnGenericParams(method, &owner_params).is_empty() {
-                            continue;
+                                continue;
-                        }
+                            }
-                        let mut specialized_method = specializeFn(method, &subst, &method.name, Some(mangled.clone()));
-                        m.resolveFnParamTypes(&mut specialized_method);
-                        m.rewriteFnBody(&mut specialized_method, true)?;
-                        m.resolveFnReturnType(&mut specialized_method);
-                        let param_types: Vec<PlumType> = specialized_method.params.iter().map(|p| match &p.ty {
+                            if already_nested && Monomorphizer::methodMentionsTemplate(method, &base.name) {
-                            ast::ParamType::Type(t) => crate::plumTypeFromAst(t),
-                            ast::ParamType::Variadic(t) => PlumType::TVariadic(Box::new(crate::plumTypeFromAst(t))),
-                            ast::ParamType::Fn(params, ret) => {
+                                continue;
-                                let param_types = params.iter().map(crate::plumTypeFromAst).collect();
-                                let ret_ty = ret.as_ref().map(|r| crate::plumTypeFromAst(r)).unwrap_or(PlumType::TUnit);
-                                PlumType::TFun(param_types, Box::new(ret_ty))
                             }
+                            let mut specialized_method = specializeFn(method, &subst, &method.name, Some(mangled.clone()));
+                            m.resolveFnParamTypes(&mut specialized_method);
+                            m.rewriteFnBody(&mut specialized_method, true)?;
+                            m.resolveFnReturnType(&mut specialized_method);
+                            let param_types: Vec<PlumType> = specialized_method.params.iter().map(|p| match &p.ty {
+                                ast::ParamType::Type(t) => crate::plumTypeFromAst(t),
+                                ast::ParamType::Variadic(t) => PlumType::TVariadic(Box::new(crate::plumTypeFromAst(t))),
+                                ast::ParamType::Fn(params, ret) => {
+                                    let param_types = params.iter().map(crate::plumTypeFromAst).collect();
+                                    let ret_ty = ret.as_ref().map(|r| crate::plumTypeFromAst(r)).unwrap_or(PlumType::TUnit);
+                                    PlumType::TFun(param_types, Box::new(ret_ty))
+                                }
-                        }).collect();
+                            }).collect();
-                        let ret = specialized_method.returns.as_ref()
+                            let ret = specialized_method.returns.as_ref()
-                            .map(crate::plumTypeFromAst)
+                                .map(crate::plumTypeFromAst)
-                            .unwrap_or(PlumType::TUnit);
+                                .unwrap_or(PlumType::TUnit);
-                        m.methods.insert((mangled.clone(), specialized_method.name.clone()), PlumType::TFun(param_types, Box::new(ret)));
+                            m.methods.insert((mangled.clone(), specialized_method.name.clone()), PlumType::TFun(param_types, Box::new(ret)));
-                        m.produced.push(ast::Item::Fn(specialized_method));
+                            m.produced.push(ast::Item::Fn(specialized_method));
+                        }
                     }
                 }
             }