feat(codegen): instantiate class templates

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

4 files changed, 204 insertions, 36 deletions

diff --git a/lib/CodeGen/CodeGen.cc b/lib/CodeGen/CodeGen.cc
index 9a678ca..fb86120 100644
--- a/lib/CodeGen/CodeGen.cc
+++ b/lib/CodeGen/CodeGen.cc
@@ -182,9 +182,11 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
     if (Sources.empty()) { reportError("no main program"); return; }
     Exports.resize(Sources.size());
     Types->setVisibility([this](const std::string &Name) {
+        if (FailedTemplateTypes.count(Name)) return false;
         auto It = TypeOwners.find(Name);
         return It == TypeOwners.end() || isVisible(It->second);
     });
+    Types->setResolveMiss([this](const std::string &Name) { return instantiateClass(Name); });
     FuncGen->setVisibility([this](size_t Owner) { return isVisible(Owner); });
 
     struct Definition { size_t Unit; bool IsFunction; bool IsOverload; bool IsExtern; bool IsTemplate; int Line; };
@@ -277,6 +279,7 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
     BasicBlock *UnhandledBB = BasicBlock::Create(*TheContext, "unhandled_exception", F);
     Exceptions->pushHandler(UnhandledBB);
 
+    TypePrePass = true;
     // Reserve names across every unit before resolving any type payload.
     for (size_t I = 0; I < Sources.size(); ++I) {
         selectUnit(I);
@@ -294,6 +297,8 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
         runTypePrePass(Sources[I].Statements, 2);
     };
     for (size_t I = 0; I < Sources.size(); ++I) DefineTypes(I);
+    TypePrePass = false;
+    emitDeferredClassPrototypes();
 
     for (size_t I = 0; I < Sources.size(); ++I) {
         selectUnit(I);
@@ -304,11 +309,7 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
             if (auto *Extern = dynamic_cast<ExternDeclAST*>(Stmt.get()))
                 FuncGen->emitExternPrototype(Extern->getProto());
             if (auto *Class = dynamic_cast<ClassTypeDeclAST*>(Stmt.get())) {
-                for (const auto &Method : Class->getMethods()) {
-                    SaveAndRestore<int> MethodLocation(DiagnosticLine, Method->getLine());
-                    if (isRegisteredMethod(Class->getName(), Method->getProto()))
-                        FuncGen->emitPrototype(Method->getProto());
-                }
+                emitClassPrototypes(Class);
             }
         }
     }
@@ -573,14 +574,15 @@ const FuncSig *CodeGen::resolveCall(const std::string &Name,
                 if (HasPackParam ? Actual.size() < FixedCount : Actual.size() != FixedCount) continue;
                 detail::TemplateBindings Bindings;
                 for (const auto &Param : TemplateParams) Bindings.emplace(Param.Name, std::vector<std::string>{});
+                SaveAndRestore<bool> Speculation(SpeculativeTemplateResolution, true);
                 bool Match = true;
                 if (HasExplicit) {
                     size_t FixedTypes = TemplateParams.size() - Variadic;
                     if (!Variadic && Explicit->size() > FixedTypes) continue;
                     for (size_t I = 0; I < Explicit->size(); ++I) {
-                        const TypeInfo *Type = resolveType((*Explicit)[I]);
-                        if (!Type || Type->isVoid()) { Match = false; break; }
-                        Bindings.at(TemplateParams[std::min(I, FixedTypes)].Name).push_back(Type->Name);
+                        auto Type = canonicalTemplateArgument((*Explicit)[I]);
+                        if (!Type) { Match = false; break; }
+                        Bindings.at(TemplateParams[std::min(I, FixedTypes)].Name).push_back(*Type);
                     }
                 }
                 if (!Match) continue;
diff --git a/lib/CodeGen/Designator.cc b/lib/CodeGen/Designator.cc
index 12d3b60..ed43cbe 100644
--- a/lib/CodeGen/Designator.cc
+++ b/lib/CodeGen/Designator.cc
@@ -42,35 +42,45 @@ void CodeGen::runTypePrePass(const std::vector<std::unique_ptr<StmtAST>> &Statem
         if (!Ok) reportError("%s", Err.c_str());
     }
 
-    if (Phase == 2) for (const auto &S : Statements) {
-        auto *Class = dynamic_cast<ClassTypeDeclAST*>(S.get());
-        if (!Class) continue;
-        auto &Methods = ClassMethods[Class->getName()];
-        IdentifierSet Names;
-        for (const auto &Field : Class->getFields()) {
-            Names.insert(Field.Name);
-            if (sameIdentifier(Field.Name, "this")) {
-                SaveAndRestore<int> Location(DiagnosticLine, Class->getLine());
-                reportError("A class field cannot be named this");
-            }
+    if (Phase == 2) for (const auto &S : Statements)
+        if (auto *Class = dynamic_cast<ClassTypeDeclAST*>(S.get())) registerClassMethods(Class);
+}
+
+void CodeGen::registerClassMethods(ClassTypeDeclAST *Class) {
+    auto &Methods = ClassMethods[Class->getName()];
+    IdentifierSet Names;
+    for (const auto &Field : Class->getFields()) {
+        Names.insert(Field.Name);
+        if (sameIdentifier(Field.Name, "this")) {
+            SaveAndRestore<int> Location(DiagnosticLine, Class->getLine());
+            reportError("A class field cannot be named this");
         }
-        for (const auto &Method : Class->getMethods()) {
-            SaveAndRestore<int> Location(DiagnosticLine, Method->getLine());
-            const std::string &Name = Method->getProto()->getName();
-            if (sameIdentifier(Name, "this")) {
-                reportError("A method cannot be named this");
-            } else if (Names.count(Name) ||
-                       (!Methods[Name].empty() && (!Method->getProto()->isOverload() ||
-                                                 !Methods[Name].front()->getProto()->isOverload()))) {
-                reportError("Duplicate member %s in class %s", Name.c_str(), Class->getName().c_str());
-            } else {
-                Methods[Name].push_back(Method.get());
-            }
+    }
+    for (const auto &Method : Class->getMethods()) {
+        SaveAndRestore<int> Location(DiagnosticLine, Method->getLine());
+        const std::string &Name = Method->getProto()->getName();
+        if (sameIdentifier(Name, "this")) {
+            reportError("A method cannot be named this");
+        } else if (Names.count(Name) ||
+                   (!Methods[Name].empty() && (!Method->getProto()->isOverload() ||
+                                             !Methods[Name].front()->getProto()->isOverload()))) {
+            reportError("Duplicate member %s in class %s", Name.c_str(), Class->getName().c_str());
+        } else {
+            Methods[Name].push_back(Method.get());
         }
     }
 }
 
+void CodeGen::emitClassPrototypes(ClassTypeDeclAST *Class) {
+    for (const auto &Method : Class->getMethods()) {
+        SaveAndRestore<int> Location(DiagnosticLine, Method->getLine());
+        if (isRegisteredMethod(Class->getName(), Method->getProto()))
+            FuncGen->emitPrototype(Method->getProto());
+    }
+}
+
 const std::vector<FunctionDefAST *> *CodeGen::findMethod(const std::string &Class, const std::string &Name) const {
+    if (Class.find('<') != std::string::npos && !resolveType(Class)) return nullptr;
     auto C = ClassMethods.find(Class);
     if (C == ClassMethods.end()) return nullptr;
     auto M = C->second.find(Name);
diff --git a/lib/CodeGen/TemplateGen.cc b/lib/CodeGen/TemplateGen.cc
index a3fd4ec..a094c17 100644
--- a/lib/CodeGen/TemplateGen.cc
+++ b/lib/CodeGen/TemplateGen.cc
@@ -7,6 +7,161 @@ using namespace cps;
 using namespace cps::detail;
 using namespace llvm;
 
+namespace {
+// Source template lists are nonempty; substitution may produce Empty<>.
+bool splitTemplateType(const std::string &Name, std::string &Base,
+                       std::vector<std::string> &Arguments) {
+    size_t Open = Name.find('<');
+    Base = Name.substr(0, Open);
+    if (Open == std::string::npos) return true;
+    if (Name.empty() || Name.back() != '>') return false;
+    size_t Start = Open + 1;
+    unsigned Depth = 0;
+    for (size_t I = Start; I + 1 < Name.size(); ++I) {
+        if (Name[I] == '<') ++Depth;
+        if (Name[I] == '>') {
+            if (!Depth) return false;
+            --Depth;
+        }
+        if (!Depth && Name[I] == ',') {
+            if (I == Start) return false;
+            Arguments.push_back(Name.substr(Start, I - Start));
+            Start = I + 1;
+        }
+    }
+    if (Depth) return false;
+    if (Start + 1 < Name.size()) Arguments.push_back(Name.substr(Start, Name.size() - Start - 1));
+    else if (Start != Open + 1) return false;
+    return true;
+}
+}
+
+std::optional<std::string> CodeGen::canonicalTemplateArgument(const std::string &Name) {
+    SaveAndRestore<bool> Speculation(SpeculativeTemplateResolution, true);
+    if (const TypeInfo *Type = resolveType(Name))
+        return Type->isVoid() ? std::nullopt : std::optional<std::string>(Type->Name);
+    if (FailedTemplateTypes.count(Name)) return std::nullopt;
+    std::string Base;
+    std::vector<std::string> Arguments;
+    if (!splitTemplateType(Name, Base, Arguments) || Name.find('<') == std::string::npos)
+        return std::nullopt;
+    auto Definitions = Templates.find(Base);
+    if (Definitions == Templates.end()) return std::nullopt;
+    for (const auto &Definition : Definitions->second) {
+        if (!Definition.Decl->getClass() || !isVisible(Definition.OwnerUnit)) continue;
+        size_t Fixed = Definition.Decl->getParams().size() - Definition.Decl->isVariadic();
+        if (Arguments.size() < Fixed || (!Definition.Decl->isVariadic() && Arguments.size() != Fixed))
+            return std::nullopt;
+        std::string Canonical = Definition.Decl->getName() + "<";
+        for (size_t I = 0; I < Arguments.size(); ++I) {
+            auto Argument = canonicalTemplateArgument(Arguments[I]);
+            if (!Argument) return std::nullopt;
+            if (I) Canonical += ',';
+            Canonical += *Argument;
+        }
+        return Canonical + ">";
+    }
+    return std::nullopt;
+}
+
+const TypeInfo *CodeGen::instantiateClass(const std::string &Name) {
+    std::string Base;
+    std::vector<std::string> Arguments;
+    bool Valid = splitTemplateType(Name, Base, Arguments);
+    auto Definitions = Templates.find(Base);
+    if (Definitions == Templates.end()) return nullptr;
+    const TemplateDefinition *Definition = nullptr;
+    for (const auto &Candidate : Definitions->second)
+        if (Candidate.Decl->getClass() && isVisible(Candidate.OwnerUnit)) {
+            Definition = &Candidate;
+            break;
+        }
+    if (!Definition || FailedTemplateTypes.count(Name)) return nullptr;
+    auto Fail = [&](const std::string &Message) -> const TypeInfo * {
+        if (!SpeculativeTemplateResolution && FailedTemplateTypes.insert(Name).second)
+            reportError("%s", Message.c_str());
+        return nullptr;
+    };
+    if (Name.find('<') == std::string::npos)
+        return Fail("Class template " + Base + " requires template arguments");
+    if (!Valid) return Fail("Invalid class template type " + Name);
+    const auto &Params = Definition->Decl->getParams();
+    size_t Fixed = Params.size() - Definition->Decl->isVariadic();
+    if (Arguments.size() < Fixed || (!Definition->Decl->isVariadic() && Arguments.size() != Fixed))
+        return Fail("Wrong number of template arguments for " + Base);
+    TemplateBindings Bindings;
+    for (const auto &Param : Params) Bindings.emplace(Param.Name, std::vector<std::string>{});
+    std::string Key;
+    for (size_t I = 0; I < Arguments.size(); ++I) {
+        const TypeInfo *Argument = resolveType(Arguments[I]);
+        if (!Argument || Argument->isVoid()) return Fail("Unknown or invalid template argument " + Arguments[I] + " for " + Base);
+        if (!Key.empty()) Key += ',';
+        Key += Argument->Name;
+        Bindings.at(Params[std::min(I, Fixed)].Name).push_back(Argument->Name);
+    }
+    std::string InstanceName = Definition->Decl->getName() + "<" + Key + ">";
+    if (FailedTemplateTypes.count(InstanceName)) return nullptr;
+    for (const auto &Instance : TemplateInstances)
+        if (Instance.Class && Instance.Decl == Definition->Decl && sameIdentifier(Instance.Arguments, Key))
+            return Types->resolve(InstanceName);
+    // Candidate matching must neither emit diagnostics nor reserve failed types.
+    // Its actual class type is already available, so an exact match reuses it above.
+    if (SpeculativeTemplateResolution) return nullptr;
+    if (TemplateDepth >= 64) return Fail("Template instantiation depth exceeds 64");
+
+    size_t Requester = VisibilityUnit.value_or(CurrentUnit);
+    size_t SavedUnit = CurrentUnit;
+    scope_exit RestoreUnit([&] { selectUnit(SavedUnit); });
+    SaveAndRestore<std::optional<size_t>> Visibility(VisibilityUnit, Requester);
+    SaveAndRestore<unsigned> Depth(TemplateDepth, TemplateDepth + 1);
+    selectUnit(Definition->OwnerUnit);
+    SaveAndRestore<int> Location(DiagnosticLine, Definition->Decl->getLine());
+    TemplateClone Clone(Bindings, [this](int Line, const std::string &Message) {
+        SaveAndRestore<int> Location(DiagnosticLine, Line ? Line : DiagnosticLine);
+        reportError("%s", Message.c_str());
+    });
+    auto Class = Clone.klass(Definition->Decl->getClass(), InstanceName);
+    if (!Class) {
+        FailedTemplateTypes.insert(Name);
+        return nullptr;
+    }
+    std::string Error;
+    if (!Types->declareUserType(InstanceName, TypeKind::Record, Error, true)) return Fail(Error);
+    TypeOwners[InstanceName] = Definition->OwnerUnit;
+    // Reserve and cache before fields resolve: recursion observes an opaque record
+    // and defineRecord diagnoses recursive by-value containment.
+    auto *ClonedClass = Class.get();
+    size_t Index = TemplateInstances.size();
+    TemplateInstances.push_back({Definition->Decl, Key, nullptr, std::move(Class), nullptr,
+        Definition->OwnerUnit, Requester, TemplateDepth});
+    if (!Types->defineRecord(InstanceName, ClonedClass->getFields(), Error)) {
+        Fail(Error);
+        FailedTemplateTypes.insert(InstanceName);
+        return nullptr;
+    }
+    registerClassMethods(ClonedClass);
+    if (TypePrePass) DeferredClassPrototypes.push_back(Index);
+    else emitClassPrototypes(ClonedClass);
+    return Types->resolve(InstanceName);
+}
+
+void CodeGen::emitDeferredClassPrototypes() {
+    size_t SavedUnit = CurrentUnit;
+    scope_exit RestoreUnit([&] { selectUnit(SavedUnit); });
+    for (size_t Index : DeferredClassPrototypes) {
+        const auto &Instance = TemplateInstances[Index];
+        auto *Class = Instance.Class.get();
+        size_t Requester = Instance.RequesterUnit;
+        size_t Owner = Instance.OwnerUnit;
+        unsigned Depth = Instance.Depth;
+        SaveAndRestore<std::optional<size_t>> Visibility(VisibilityUnit, Requester);
+        SaveAndRestore<unsigned> InstantiationDepth(TemplateDepth, Depth);
+        selectUnit(Owner);
+        emitClassPrototypes(Class);
+    }
+    DeferredClassPrototypes.clear();
+}
+
 bool CodeGen::hasFunctionTemplate(const std::string &Name) const {
     auto It = Templates.find(Name);
     if (It == Templates.end()) return false;
@@ -94,7 +249,7 @@ const FuncSig *CodeGen::instantiateFunction(const TemplateDefinition &Definition
     const FuncSig *Signature = nullptr;
     for (const auto *Sig : Signatures)
         if (Sig->Prototype == Function->getProto()) Signature = Sig;
-    TemplateInstances.push_back({Definition.Decl, Key, std::move(Function), Signature,
+    TemplateInstances.push_back({Definition.Decl, Key, std::move(Function), nullptr, Signature,
         Definition.OwnerUnit, Requester, TemplateDepth + 1});
     return Signature;
 }
@@ -106,6 +261,7 @@ void CodeGen::drainTemplateBodies() {
         // Emission may append instances, so keep no vector element references.
         const auto &Instance = TemplateInstances[NextTemplateBody++];
         auto *Function = Instance.Function.get();
+        auto *Class = Instance.Class.get();
         auto *Declaration = Instance.Decl;
         size_t Owner = Instance.OwnerUnit;
         size_t Requester = Instance.RequesterUnit;
@@ -114,6 +270,7 @@ void CodeGen::drainTemplateBodies() {
         SaveAndRestore<unsigned> InstantiationDepth(TemplateDepth, Depth);
         SaveAndRestore<IdentifierMap<SymbolInfo>> SymbolContext(Symbols, TemplateSymbols.at(Declaration));
         selectUnit(Owner);
-        emitStmt(Function);
+        if (Class && !FailedTemplateTypes.count(Class->getName())) emitStmt(Class);
+        if (Function) emitStmt(Function);
     }
 }
diff --git a/lib/CodeGen/TypeSystem.cc b/lib/CodeGen/TypeSystem.cc
index 6cf0f00..c5db1eb 100644
--- a/lib/CodeGen/TypeSystem.cc
+++ b/lib/CodeGen/TypeSystem.cc
@@ -111,9 +111,8 @@ bool TypeSystem::sameType(const std::string &Left, const std::string &Right) con
 
 const TypeInfo *TypeSystem::resolve(const std::string &TypeName) const {
     auto It = Types.find(TypeName);
-    if (It == Types.end() || (Visible && !Visible(TypeName))) {
-        return nullptr;
-    }
+    if (It == Types.end()) return ResolveMiss ? ResolveMiss(TypeName) : nullptr;
+    if (Visible && !Visible(TypeName)) return nullptr;
     return &It->second;
 }