feat(codegen): instantiate function templates by deduction

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

8 files changed, 452 insertions, 16 deletions

diff --git a/lib/CodeGen/CodeGen.cc b/lib/CodeGen/CodeGen.cc
index 641b424..3e5b890 100644
--- a/lib/CodeGen/CodeGen.cc
+++ b/lib/CodeGen/CodeGen.cc
@@ -147,7 +147,7 @@ const TypeInfo *CodeGen::resolveType(const std::string &TypeName) const {
 }
 
 bool CodeGen::isVisible(size_t Owner) const {
-    return !Units || (*Units)[CurrentUnit].Visible[Owner];
+    return !Units || (*Units)[VisibilityUnit.value_or(CurrentUnit)].Visible[Owner];
 }
 
 void CodeGen::selectUnit(size_t Unit) {
@@ -185,17 +185,18 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
     });
     FuncGen->setVisibility([this](size_t Owner) { return isVisible(Owner); });
 
-    struct Definition { size_t Unit; bool IsFunction; bool IsOverload; bool IsExtern; int Line; };
+    struct Definition { size_t Unit; bool IsFunction; bool IsOverload; bool IsExtern; bool IsTemplate; int Line; };
     IdentifierMap<Definition> Definitions;
     std::optional<size_t> CodeUnit;
     FunctionDefAST *Entry = nullptr;
     size_t EntryUnit = 0;
     auto Reserve = [&](const std::string &Name, bool IsFunction = false, bool IsOverload = false,
-                       bool IsExtern = false) {
-        auto [It, Added] = Definitions.emplace(Name, Definition{CurrentUnit, IsFunction, IsOverload, IsExtern, DiagnosticLine});
+                       bool IsExtern = false, bool IsTemplate = false) {
+        auto [It, Added] = Definitions.emplace(Name, Definition{CurrentUnit, IsFunction, IsOverload, IsExtern, IsTemplate, DiagnosticLine});
         bool Compatible = (IsFunction && IsOverload && It->second.IsFunction && It->second.IsOverload) ||
                           (IsExtern && It->second.IsExtern);
-        if (!Added && It->second.Unit != CurrentUnit && !Compatible) {
+        if (!Added && !Compatible && (It->second.Unit != CurrentUnit ||
+            ((IsTemplate || It->second.IsTemplate) && !(IsFunction && It->second.IsFunction)))) {
             // Default library units follow user inputs; point at the user's conflicting definition.
             bool UserConflict = Sources[CurrentUnit].IsLibrary && !Sources[It->second.Unit].IsLibrary;
             SaveAndRestore<int> Location(DiagnosticLine, UserConflict ? It->second.Line : DiagnosticLine);
@@ -212,7 +213,7 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
             std::string TypeName;
             if (auto *T = dynamic_cast<TemplateDeclAST*>(S.get())) {
                 auto *Function = T->getFunction();
-                Reserve(T->getName(), Function != nullptr, Function && Function->getProto()->isOverload());
+                Reserve(T->getName(), Function != nullptr, Function && Function->getProto()->isOverload(), false, true);
                 Templates[T->getName()].push_back({T, I});
             } else if (auto *F = dynamic_cast<FunctionDefAST*>(S.get())) {
                 Reserve(F->getProto()->getName(), true, F->getProto()->isOverload());
@@ -310,6 +311,8 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
         }
     }
 
+    validateTemplates();
+
     // Constants are literal exports. Own constants are still installed only
     // when their declaration is encountered during body emission.
     for (size_t I = 0; I < Sources.size(); ++I) {
@@ -330,11 +333,13 @@ void CodeGen::compile(const std::vector<SourceUnit> &Sources) {
             runGlobalPrePass(Sources[I], Phase);
         }
     }
+    captureTemplateSymbols();
     for (size_t I = 0; I < Sources.size(); ++I) {
         selectUnit(I);
         importSymbols();
         for (const auto &Stmt : Sources[I].Statements) emitStmt(Stmt.get());
     }
+    drainTemplateBodies();
     selectUnit(MainUnit);
     if (!CodeUnit && !Entry && !HadError) {
         SaveAndRestore<int> Location(DiagnosticLine, Sources.size() > 1 ? 1 : 0);
@@ -498,13 +503,14 @@ Value *CodeGen::emitVariadicArgument(ExprAST *Expr, const std::string &Callee, s
 const FuncSig *CodeGen::resolveCall(const std::string &Name,
                                   const std::vector<std::unique_ptr<ExprAST>> &Args) {
     auto Overloads = FuncGen->getOverloads(Name);
-    if (Overloads.empty()) {
+    bool HasTemplates = hasFunctionTemplate(Name);
+    if (Overloads.empty() && !HasTemplates) {
         reportError("Call to undefined function %s", Name.c_str());
         return nullptr;
     }
-    if (Overloads.size() == 1 && !Overloads.front()->IsOverload) return Overloads.front();
+    if (!HasTemplates && Overloads.size() == 1 && !Overloads.front()->IsOverload) return Overloads.front();
     // Visible EXTERN redeclarations are identical by construction.
-    if (Overloads.front()->IsExternal) return Overloads.front();
+    if (!HasTemplates && Overloads.front()->IsExternal) return Overloads.front();
     struct ArgumentType { const TypeInfo *Type; int Rank; };
     std::vector<ArgumentType> Actual;
     std::string Key;
@@ -521,6 +527,7 @@ const FuncSig *CodeGen::resolveCall(const std::string &Name,
         if (Rank) Key += "ARRAY" + std::to_string(Rank) + " OF ";
         Key += Type ? Type->Name : "?";
     }
+    const FuncSig *Ordinary = nullptr;
     for (const FuncSig *Sig : Overloads) {
         if (Sig->Params.size() != Actual.size()) continue;
         bool Match = true;
@@ -532,8 +539,48 @@ const FuncSig *CodeGen::resolveCall(const std::string &Name,
                 break;
             }
         }
-        if (Match) return Sig;
+        if (Match) {
+            if (Ordinary && HasTemplates) {
+                reportError("Ambiguous call to %s(%s)", Name.c_str(), Key.c_str());
+                return nullptr;
+            }
+            Ordinary = Sig;
+            if (!HasTemplates) return Sig;
+        }
+    }
+    if (Ordinary) return Ordinary;
+    const TemplateDefinition *Selected = nullptr;
+    IdentifierMap<std::vector<std::string>> SelectedBindings;
+    if (HasTemplates) {
+        for (const auto &Definition : Templates.at(Name)) {
+            auto *Function = Definition.Decl->getFunction();
+            if (!Function || Definition.Decl->isVariadic() || !isVisible(Definition.OwnerUnit)) continue;
+            const auto &Params = Function->getProto()->getParams();
+            if (Params.size() != Actual.size()) continue;
+            IdentifierMap<std::vector<std::string>> Bindings;
+            for (const auto &Param : Definition.Decl->getParams()) Bindings.emplace(Param.Name, std::vector<std::string>{});
+            bool Match = true;
+            for (size_t I = 0; I < Actual.size(); ++I) {
+                const auto &P = Params[I];
+                const TypeInfo *Type = Actual[I].Type;
+                if (!Type || Type->isVoid() || Actual[I].Rank != (P.IsArray ? P.Rank : 0)) { Match = false; break; }
+                auto Binding = Bindings.find(P.TypeName);
+                if (Binding != Bindings.end()) {
+                    if (Binding->second.empty()) Binding->second.push_back(Type->Name);
+                    else if (!Type->sameType(resolveType(Binding->second.front()))) { Match = false; break; }
+                } else if (!Type->sameType(resolveType(P.TypeName))) { Match = false; break; }
+            }
+            for (const auto &[Param, Types] : Bindings) if (Types.empty()) Match = false;
+            if (!Match) continue;
+            if (Selected) {
+                reportError("Ambiguous call to %s(%s)", Name.c_str(), Key.c_str());
+                return nullptr;
+            }
+            Selected = &Definition;
+            SelectedBindings = std::move(Bindings);
+        }
     }
+    if (Selected) return instantiateFunction(*Selected, SelectedBindings);
     reportError("No matching overload for %s(%s)", Name.c_str(), Key.c_str());
     return nullptr;
 }
diff --git a/lib/CodeGen/ConstantGen.cc b/lib/CodeGen/ConstantGen.cc
index 374b423..1ac2a28 100644
--- a/lib/CodeGen/ConstantGen.cc
+++ b/lib/CodeGen/ConstantGen.cc
@@ -60,7 +60,7 @@ void CodeGen::emitConstantStmt(ConstantStmtAST *Stmt) {
         return;
     }
     if (ConstantScopes.back().ID == 0 &&
-        (FuncGen->hasFunction(Name) || isBuiltinName(Name))) {
+        (hasCallable(Name) || isBuiltinName(Name))) {
         reportError("Constant %s conflicts with a function name", Name.c_str());
         return;
     }
diff --git a/lib/CodeGen/FunctionGen.cc b/lib/CodeGen/FunctionGen.cc
index 543bd14..c01b042 100644
--- a/lib/CodeGen/FunctionGen.cc
+++ b/lib/CodeGen/FunctionGen.cc
@@ -11,7 +11,7 @@ using namespace cps;
 
 // Symbols the compiler itself declares (libc + runtime); a user
 // FUNCTION/PROCEDURE with one of these names would hijack the runtime.
-static bool isReservedRuntimeName(const std::string &Name) {
+bool FunctionGen::isReservedRuntimeName(const std::string &Name) {
     static const char *Reserved[] = {
         "__cps_main", "__cps_user_line", "printf", "scanf", "malloc", "free", "strlen", "memcpy",
         "strcpy", "strcat", "toupper", "tolower", "sprintf", "snprintf", "strtol", "strtoll",
@@ -105,12 +105,12 @@ void FunctionGen::createArgumentAllocas(Function *F, const std::vector<ParamDecl
     }
 }
 
-std::vector<const FuncSig *> FunctionGen::getOverloads(const std::string &Name) const {
+std::vector<const FuncSig *> FunctionGen::getOverloads(const std::string &Name, bool AllUnits) const {
     std::vector<const FuncSig *> Result;
     auto It = Signatures.find(sameIdentifier(Name, "MAIN") ? "__cps_main" : Name);
     if (It != Signatures.end())
         for (const FuncSig &Sig : It->second)
-            if (!Visible || Visible(Sig.OwnerUnit)) Result.push_back(&Sig);
+            if (AllUnits || !Visible || Visible(Sig.OwnerUnit)) Result.push_back(&Sig);
     return Result;
 }
 
diff --git a/lib/CodeGen/GlobalGen.cc b/lib/CodeGen/GlobalGen.cc
index b5c39a8..89a61ac 100644
--- a/lib/CodeGen/GlobalGen.cc
+++ b/lib/CodeGen/GlobalGen.cc
@@ -34,7 +34,7 @@ void CodeGen::runGlobalPrePass(const SourceUnit &Unit, int Phase) {
                     continue;
                 }
                 if (Exports[CurrentUnit].count(Name) || Types->resolve(Name) ||
-                    Types->lookupEnumConstant(Name) || FuncGen->hasFunction(Name) ||
+                    Types->lookupEnumConstant(Name) || hasCallable(Name) ||
                     isBuiltinName(Name)) {
                     reportError("Global %s conflicts with an existing definition", Name.c_str());
                     continue;
diff --git a/lib/CodeGen/StatementGen.cc b/lib/CodeGen/StatementGen.cc
index 6bc4ec4..2186aa0 100644
--- a/lib/CodeGen/StatementGen.cc
+++ b/lib/CodeGen/StatementGen.cc
@@ -105,7 +105,7 @@ void CodeGen::emitStmtImpl(StmtAST *Stmt) {
 
     if (auto *Call = dynamic_cast<CallStmtAST*>(Stmt)) {
         Value *Result = emitCall(Call->getCallee(), Call->getArgs(), Call->getLine());
-        const FuncSig *Sig = FuncGen->hasFunction(Call->getCallee())
+        const FuncSig *Sig = hasCallable(Call->getCallee())
             ? resolveCall(Call->getCallee(), Call->getArgs()) : nullptr;
         const TypeInfo *Type = Sig ? resolveType(Sig->ReturnTypeName) : nullptr;
         if (Result && Type && (Type->IsClass || containsString(Type))) materializeOperatorReceiver(Result, Type);
diff --git a/lib/CodeGen/TemplateClone.cc b/lib/CodeGen/TemplateClone.cc
new file mode 100644
index 0000000..7374ee8
--- /dev/null
+++ b/lib/CodeGen/TemplateClone.cc
@@ -0,0 +1,238 @@
+#include "TemplateClone.h"
+#include "cps/FileAST.h"
+#include <cctype>
+
+using namespace cps;
+using namespace cps::detail;
+
+namespace {
+template<class T, class U> std::unique_ptr<T> located(std::unique_ptr<T> Copy, const U *Source) {
+    Copy->setLine(Source->getLine());
+    return Copy;
+}
+}
+
+void TemplateClone::fail(int Line, const std::string &Message) {
+    Failed = true;
+    Error(Line, Message);
+}
+
+std::string TemplateClone::type(const std::string &Name) {
+    size_t Position = 0;
+    auto Join = [](const std::vector<std::string> &Parts) {
+        std::string Result;
+        for (const auto &Part : Parts) {
+            if (!Result.empty()) Result += ',';
+            Result += Part;
+        }
+        return Result;
+    };
+    std::function<std::vector<std::string>()> Parse = [&]() -> std::vector<std::string> {
+        size_t Start = Position;
+        while (Position < Name.size() &&
+               (std::isalnum(static_cast<unsigned char>(Name[Position])) || Name[Position] == '_')) ++Position;
+        if (Position == Start) {
+            fail(0, "Invalid canonical template type " + Name);
+            Position = Name.size();
+            return {};
+        }
+        std::string Base = Name.substr(Start, Position - Start);
+        bool HasArguments = Position < Name.size() && Name[Position] == '<';
+        if (HasArguments) {
+            ++Position;
+            std::vector<std::string> Arguments;
+            while (Position < Name.size() && Name[Position] != '>') {
+                auto Expanded = Parse();
+                Arguments.insert(Arguments.end(), Expanded.begin(), Expanded.end());
+                if (Position == Name.size() || Name[Position] != ',') break;
+                ++Position;
+            }
+            if (Position == Name.size() || Name[Position] != '>') {
+                fail(0, "Invalid canonical template type " + Name);
+                return {};
+            }
+            ++Position;
+            Base += "<" + Join(Arguments) + ">";
+        }
+        bool Expand = Name.compare(Position, 3, "...") == 0;
+        if (Expand) Position += 3;
+        auto Binding = Bindings.find(Base);
+        if (Binding == Bindings.end()) return {Base};
+        if (Expand) return Binding->second;
+        if (Binding->second.size() != 1) {
+            fail(0, "A type pack requires an expansion");
+            return {};
+        }
+        return Binding->second;
+    };
+    auto Types = Parse();
+    if (Position != Name.size()) fail(0, "Invalid canonical template type " + Name);
+    return Join(Types);
+}
+
+std::vector<std::unique_ptr<ExprAST>> TemplateClone::arguments(
+    const std::vector<std::unique_ptr<ExprAST>> &Args) {
+    std::vector<std::unique_ptr<ExprAST>> Result;
+    for (const auto &Arg : Args) {
+        if (auto *Pack = dynamic_cast<PackExpansionExprAST *>(Arg.get())) {
+            auto Names = PackNames.find(Pack->getName());
+            if (Names == PackNames.end()) fail(Pack->getLine(), "Unknown parameter pack " + Pack->getName());
+            else for (const auto &Name : Names->second)
+                Result.push_back(located(std::make_unique<VariableExprAST>(Name), Pack));
+        } else Result.push_back(expression(Arg.get()));
+    }
+    return Result;
+}
+
+std::vector<std::unique_ptr<StmtAST>> TemplateClone::body(
+    const std::vector<std::unique_ptr<StmtAST>> &Body) {
+    std::vector<std::unique_ptr<StmtAST>> Result;
+    for (const auto &Stmt : Body) Result.push_back(statement(Stmt.get()));
+    return Result;
+}
+
+std::unique_ptr<ExprAST> TemplateClone::expression(ExprAST *Expr) {
+    if (!Expr) return nullptr;
+    std::unique_ptr<ExprAST> Copy;
+    if (auto *E = dynamic_cast<IntegerExprAST *>(Expr)) Copy = std::make_unique<IntegerExprAST>(E->getVal());
+    else if (auto *E = dynamic_cast<RealExprAST *>(Expr)) Copy = std::make_unique<RealExprAST>(E->getVal());
+    else if (auto *E = dynamic_cast<BooleanExprAST *>(Expr)) Copy = std::make_unique<BooleanExprAST>(E->getVal());
+    else if (auto *E = dynamic_cast<CharExprAST *>(Expr)) Copy = std::make_unique<CharExprAST>(E->getVal());
+    else if (auto *E = dynamic_cast<StringExprAST *>(Expr)) Copy = std::make_unique<StringExprAST>(E->getVal(), E->isCString());
+    else if (auto *E = dynamic_cast<VariableExprAST *>(Expr)) Copy = std::make_unique<VariableExprAST>(E->getName());
+    else if (auto *E = dynamic_cast<ArrayAccessExprAST *>(Expr)) {
+        std::vector<std::unique_ptr<ExprAST>> Indices;
+        for (const auto &Index : E->getIndices()) Indices.push_back(expression(Index.get()));
+        Copy = std::make_unique<ArrayAccessExprAST>(E->getName(), std::move(Indices), E->getLine());
+    } else if (auto *E = dynamic_cast<UnaryExprAST *>(Expr)) Copy = std::make_unique<UnaryExprAST>(E->getOp(), expression(E->getOperand()));
+    else if (auto *E = dynamic_cast<BinaryExprAST *>(Expr)) Copy = std::make_unique<BinaryExprAST>(E->getOp(), expression(E->getLHS()), expression(E->getRHS()), E->getLine());
+    else if (auto *E = dynamic_cast<CallExprAST *>(Expr)) {
+        std::vector<std::string> Types;
+        for (const auto &Arg : E->getTemplateArgs()) {
+            std::string Substituted = type(Arg);
+            // A template argument pack expands into separate argument slots.
+            size_t Start = 0, Depth = 0;
+            for (size_t I = 0; I <= Substituted.size(); ++I) {
+                if (I < Substituted.size() && Substituted[I] == '<') ++Depth;
+                if (I < Substituted.size() && Substituted[I] == '>') --Depth;
+                if (I == Substituted.size() || (!Depth && Substituted[I] == ',')) {
+                    if (I > Start) Types.push_back(Substituted.substr(Start, I - Start));
+                    Start = I + 1;
+                }
+            }
+        }
+        Copy = std::make_unique<CallExprAST>(E->getCallee(), arguments(E->getArgs()), E->getLine(), std::move(Types));
+    } else if (auto *E = dynamic_cast<MemberCallExprAST *>(Expr)) Copy = std::make_unique<MemberCallExprAST>(expression(E->getReceiver()), E->getMethod(), arguments(E->getArgs()), E->getLine());
+    else if (auto *E = dynamic_cast<NewExprAST *>(Expr)) Copy = std::make_unique<NewExprAST>(type(E->getClassName()), arguments(E->getArgs()), E->getLine());
+    else if (auto *E = dynamic_cast<CastExprAST *>(Expr)) Copy = std::make_unique<CastExprAST>(type(E->getTypeName()), expression(E->getOperand()));
+    else if (auto *E = dynamic_cast<DesignatorExprAST *>(Expr)) {
+        std::vector<DesignatorAccess> Accesses;
+        for (const auto &A : E->getAccesses()) {
+            DesignatorAccess CopyAccess{A.Kind, {}, A.FieldName};
+            for (const auto &Index : A.Indices) CopyAccess.Indices.push_back(expression(Index.get()));
+            Accesses.push_back(std::move(CopyAccess));
+        }
+        Copy = std::make_unique<DesignatorExprAST>(E->getBaseName(), std::move(Accesses), E->getLine());
+    } else if (auto *E = dynamic_cast<AddrOfExprAST *>(Expr)) {
+        auto Target = expression(E->getTarget());
+        Copy = std::make_unique<AddrOfExprAST>(std::unique_ptr<DesignatorExprAST>(static_cast<DesignatorExprAST *>(Target.release())));
+    } else if (dynamic_cast<PackExpansionExprAST *>(Expr)) fail(Expr->getLine(), "A parameter pack expansion is only allowed in an argument list");
+    else fail(Expr->getLine(), "Unsupported expression in template body");
+    if (Copy) Copy->setLine(Expr->getLine());
+    return Copy;
+}
+
+std::unique_ptr<StmtAST> TemplateClone::statement(StmtAST *Stmt) {
+    std::unique_ptr<StmtAST> Copy;
+    if (auto *S = dynamic_cast<DeclareStmtAST *>(Stmt)) Copy = std::make_unique<DeclareStmtAST>(S->getName(), type(S->getType()), arguments(S->getArgs()), S->hasParens());
+    else if (auto *S = dynamic_cast<ArrayDeclareStmtAST *>(Stmt)) {
+        std::vector<std::pair<std::unique_ptr<ExprAST>, std::unique_ptr<ExprAST>>> Bounds;
+        for (const auto &B : S->getBounds()) Bounds.emplace_back(expression(B.first.get()), expression(B.second.get()));
+        Copy = std::make_unique<ArrayDeclareStmtAST>(S->getName(), std::move(Bounds), type(S->getType()));
+    } else if (auto *S = dynamic_cast<ConstantStmtAST *>(Stmt)) Copy = std::make_unique<ConstantStmtAST>(S->getName(), expression(S->getValue()));
+    else if (auto *S = dynamic_cast<AssignStmtAST *>(Stmt)) Copy = std::make_unique<AssignStmtAST>(S->getName(), expression(S->getExpr()));
+    else if (auto *S = dynamic_cast<ArrayAssignStmtAST *>(Stmt)) {
+        std::vector<std::unique_ptr<ExprAST>> Indices;
+        for (const auto &Index : S->getIndices()) Indices.push_back(expression(Index.get()));
+        Copy = std::make_unique<ArrayAssignStmtAST>(S->getName(), std::move(Indices), expression(S->getExpr()), S->getLine());
+    } else if (auto *S = dynamic_cast<DesignatorAssignStmtAST *>(Stmt)) {
+        auto Target = expression(S->getTarget());
+        Copy = std::make_unique<DesignatorAssignStmtAST>(std::unique_ptr<DesignatorExprAST>(static_cast<DesignatorExprAST *>(Target.release())), expression(S->getExpr()));
+    } else if (auto *S = dynamic_cast<InputStmtAST *>(Stmt)) Copy = std::make_unique<InputStmtAST>(expression(S->getTarget()));
+    else if (auto *S = dynamic_cast<DeleteStmtAST *>(Stmt)) Copy = std::make_unique<DeleteStmtAST>(expression(S->getTarget()));
+    else if (auto *S = dynamic_cast<OutputStmtAST *>(Stmt)) {
+        std::vector<std::unique_ptr<ExprAST>> Exprs;
+        for (const auto &E : S->getExprs()) Exprs.push_back(expression(E.get()));
+        Copy = std::make_unique<OutputStmtAST>(std::move(Exprs));
+    } else if (auto *S = dynamic_cast<ReturnStmtAST *>(Stmt)) Copy = std::make_unique<ReturnStmtAST>(expression(S->getRetVal()));
+    else if (auto *S = dynamic_cast<CallStmtAST *>(Stmt)) {
+        CallExprAST Call(S->getCallee(), {}, S->getLine(), S->getTemplateArgs());
+        auto Expr = expression(&Call);
+        auto *Cloned = static_cast<CallExprAST *>(Expr.get());
+        Copy = std::make_unique<CallStmtAST>(S->getCallee(), arguments(S->getArgs()), S->getLine(), Cloned->getTemplateArgs());
+    } else if (auto *S = dynamic_cast<MemberCallStmtAST *>(Stmt)) {
+        auto Call = expression(S->getCall());
+        Copy = std::make_unique<MemberCallStmtAST>(std::unique_ptr<MemberCallExprAST>(static_cast<MemberCallExprAST *>(Call.release())));
+    } else if (auto *S = dynamic_cast<IfStmtAST *>(Stmt)) Copy = std::make_unique<IfStmtAST>(expression(S->getCond()), body(S->getThenStmts()), body(S->getElseStmts()));
+    else if (auto *S = dynamic_cast<WhileStmtAST *>(Stmt)) Copy = std::make_unique<WhileStmtAST>(expression(S->getCond()), body(S->getBody()));
+    else if (auto *S = dynamic_cast<RepeatStmtAST *>(Stmt)) Copy = std::make_unique<RepeatStmtAST>(body(S->getBody()), expression(S->getCond()));
+    else if (auto *S = dynamic_cast<ForStmtAST *>(Stmt)) Copy = std::make_unique<ForStmtAST>(S->getVarName(), expression(S->getStart()), expression(S->getEnd()), expression(S->getStep()), body(S->getBody()));
+    else if (auto *S = dynamic_cast<CaseStmtAST *>(Stmt)) {
+        std::vector<CaseBranch> Branches;
+        for (const auto &B : S->getBranches()) Branches.push_back({expression(B.Lower.get()), expression(B.Upper.get()), body(B.Body), B.Line});
+        Copy = std::make_unique<CaseStmtAST>(S->getSelector(), std::move(Branches));
+    } else if (auto *S = dynamic_cast<TryStmtAST *>(Stmt)) Copy = std::make_unique<TryStmtAST>(body(S->getBody()), body(S->getCatchBody()));
+    else if (dynamic_cast<ThrowStmtAST *>(Stmt)) Copy = std::make_unique<ThrowStmtAST>();
+    else if (auto *S = dynamic_cast<OpenFileStmtAST *>(Stmt)) Copy = std::make_unique<OpenFileStmtAST>(expression(S->getFileName()), S->getMode(), S->getLine());
+    else if (auto *S = dynamic_cast<ReadFileStmtAST *>(Stmt)) Copy = std::make_unique<ReadFileStmtAST>(expression(S->getFileName()), S->getVarName(), S->getLine());
+    else if (auto *S = dynamic_cast<WriteFileStmtAST *>(Stmt)) Copy = std::make_unique<WriteFileStmtAST>(expression(S->getFileName()), expression(S->getData()), S->getLine());
+    else if (auto *S = dynamic_cast<CloseFileStmtAST *>(Stmt)) Copy = std::make_unique<CloseFileStmtAST>(expression(S->getFileName()), S->getLine());
+    else if (dynamic_cast<FunctionDefAST *>(Stmt)) fail(Stmt->getLine(), "Nested FUNCTION or PROCEDURE definitions are not allowed in template bodies");
+    else fail(Stmt->getLine(), "Unsupported declaration in template body");
+    if (Copy) Copy->setLine(Stmt->getLine());
+    return Copy;
+}
+
+std::unique_ptr<FunctionDefAST> TemplateClone::function(const FunctionDefAST *Source,
+    const std::string &Name, const std::string &OwnerClass) {
+    auto SavedNames = PackNames;
+    const auto *Proto = Source->getProto();
+    std::vector<ParamDecl> Params;
+    for (const auto &P : Proto->getParams()) {
+        if (P.IsPack) {
+            auto Binding = Bindings.find(P.TypeName);
+            if (Binding == Bindings.end()) { fail(P.Line, "Unbound template parameter pack"); continue; }
+            auto &Names = PackNames[P.Name];
+            Names.clear();
+            for (size_t I = 0; I < Binding->second.size(); ++I) {
+                ParamDecl Copy = P;
+                Copy.Name += "#" + std::to_string(I + 1);
+                Copy.TypeName = Binding->second[I];
+                Copy.IsPack = false;
+                Names.push_back(Copy.Name);
+                Params.push_back(std::move(Copy));
+            }
+        } else {
+            Params.push_back(P);
+            Params.back().TypeName = type(P.TypeName);
+        }
+    }
+    auto CopyProto = std::make_unique<PrototypeAST>(Name, std::move(Params), type(Proto->getReturnType()),
+        Proto->isExternal(), OwnerClass, Proto->isPublic(), Proto->isOverload());
+    CopyProto->setOperator(Proto->getOperator());
+    CopyProto->setVariadic(Proto->isVariadic());
+    auto Copy = located(std::make_unique<FunctionDefAST>(std::move(CopyProto), body(Source->getBody())), Source);
+    PackNames = std::move(SavedNames);
+    return Failed ? nullptr : std::move(Copy);
+}
+
+std::unique_ptr<ClassTypeDeclAST> TemplateClone::klass(const ClassTypeDeclAST *Source,
+    const std::string &Name) {
+    std::vector<RecordFieldDecl> Fields = Source->getFields();
+    for (auto &Field : Fields) Field.TypeName = type(Field.TypeName);
+    std::vector<std::unique_ptr<FunctionDefAST>> Methods;
+    for (const auto &Method : Source->getMethods())
+        Methods.push_back(function(Method.get(), Method->getProto()->getName(), Name));
+    auto Copy = located(std::make_unique<ClassTypeDeclAST>(Name, std::move(Fields), std::move(Methods)), Source);
+    return Failed ? nullptr : std::move(Copy);
+}
diff --git a/lib/CodeGen/TemplateClone.h b/lib/CodeGen/TemplateClone.h
new file mode 100644
index 0000000..a0f196f
--- /dev/null
+++ b/lib/CodeGen/TemplateClone.h
@@ -0,0 +1,32 @@
+#pragma once
+#include "cps/TemplateAST.h"
+#include "cps/Identifier.h"
+#include <functional>
+
+namespace cps::detail {
+
+using TemplateBindings = IdentifierMap<std::vector<std::string>>;
+
+// Clones own all children; source ASTs remain reusable for later instances.
+class TemplateClone {
+    const TemplateBindings &Bindings;
+    IdentifierMap<std::vector<std::string>> PackNames;
+    std::function<void(int, const std::string &)> Error;
+    bool Failed = false;
+    void fail(int Line, const std::string &Message);
+    std::vector<std::unique_ptr<ExprAST>> arguments(const std::vector<std::unique_ptr<ExprAST>> &Args);
+    std::vector<std::unique_ptr<StmtAST>> body(const std::vector<std::unique_ptr<StmtAST>> &Body);
+    std::unique_ptr<ExprAST> expression(ExprAST *Expr);
+    std::unique_ptr<StmtAST> statement(StmtAST *Stmt);
+public:
+    TemplateClone(const TemplateBindings &Bindings,
+                  std::function<void(int, const std::string &)> Error)
+        : Bindings(Bindings), Error(std::move(Error)) {}
+    std::string type(const std::string &Name);
+    std::unique_ptr<FunctionDefAST> function(const FunctionDefAST *Source,
+        const std::string &Name, const std::string &OwnerClass = {});
+    std::unique_ptr<ClassTypeDeclAST> klass(const ClassTypeDeclAST *Source,
+                                           const std::string &Name);
+};
+
+} // namespace cps::detail
diff --git a/lib/CodeGen/TemplateGen.cc b/lib/CodeGen/TemplateGen.cc
new file mode 100644
index 0000000..a3fd4ec
--- /dev/null
+++ b/lib/CodeGen/TemplateGen.cc
@@ -0,0 +1,119 @@
+#include "cps/CodeGen.h"
+#include "cps/TemplateAST.h"
+#include "TemplateClone.h"
+#include "llvm/ADT/ScopeExit.h"
+
+using namespace cps;
+using namespace cps::detail;
+using namespace llvm;
+
+bool CodeGen::hasFunctionTemplate(const std::string &Name) const {
+    auto It = Templates.find(Name);
+    if (It == Templates.end()) return false;
+    for (const auto &Definition : It->second)
+        if (Definition.Decl->getFunction() && isVisible(Definition.OwnerUnit)) return true;
+    return false;
+}
+
+bool CodeGen::hasCallable(const std::string &Name) const {
+    return FuncGen->hasFunction(Name) || hasFunctionTemplate(Name);
+}
+
+void CodeGen::validateTemplates() {
+    for (const auto &[Name, Definitions] : Templates) {
+        auto Ordinary = FuncGen->getOverloads(Name, true);
+        size_t Count = Ordinary.size();
+        for (const auto &Definition : Definitions) Count += Definition.Decl->getFunction() != nullptr;
+        for (const auto &Definition : Definitions) {
+            selectUnit(Definition.OwnerUnit);
+            SaveAndRestore<int> Location(DiagnosticLine, Definition.Decl->getLine());
+            auto *Function = Definition.Decl->getFunction();
+            if (!Function) continue;
+            if (sameIdentifier(Name, "MAIN")) reportError("MAIN cannot be a template");
+            if (FunctionGen::isReservedRuntimeName(Name))
+                reportError("'%s' is a reserved runtime symbol and cannot be a FUNCTION/PROCEDURE name", Name.c_str());
+            if (isBuiltinName(Name)) reportError("'%s' is a built-in function and cannot be redefined", Name.c_str());
+            if (Types->lookupEnumConstant(Name) || Types->resolve(Name))
+                reportError("Template %s conflicts with an enum value or type name", Name.c_str());
+            bool Consistent = Function->getProto()->isOverload();
+            for (const auto &Other : Definitions)
+                if (Other.Decl->getFunction()) Consistent &= Other.Decl->getFunction()->getProto()->isOverload();
+            for (const auto *Other : Ordinary) Consistent &= Other->IsOverload;
+            if (Count > 1 && !Consistent)
+                reportError("Function %s has multiple definitions; every overload must be declared OVERLOAD", Name.c_str());
+        }
+    }
+}
+
+void CodeGen::captureTemplateSymbols() {
+    for (size_t I = 0; I < Units->size(); ++I) {
+        selectUnit(I);
+        importSymbols();
+        for (const auto &Stmt : (*Units)[I].Statements) {
+            if (auto *Constant = dynamic_cast<ConstantStmtAST *>(Stmt.get())) {
+                auto It = Exports[I].find(Constant->getName());
+                if (It != Exports[I].end()) Symbols[It->first] = It->second;
+            } else if (auto *Template = dynamic_cast<TemplateDeclAST *>(Stmt.get())) {
+                TemplateSymbols.emplace(Template, Symbols);
+            }
+        }
+    }
+}
+
+const FuncSig *CodeGen::instantiateFunction(const TemplateDefinition &Definition,
+    const TemplateBindings &Bindings) {
+    std::string Key;
+    for (const auto &Param : Definition.Decl->getParams()) {
+        auto It = Bindings.find(Param.Name);
+        if (It == Bindings.end()) return nullptr;
+        for (const auto &Type : It->second) {
+            if (!Key.empty()) Key += ',';
+            Key += Type;
+        }
+    }
+    for (const auto &Instance : TemplateInstances)
+        if (Instance.Decl == Definition.Decl && sameIdentifier(Instance.Arguments, Key)) return Instance.Signature;
+    if (TemplateDepth >= 64) {
+        reportError("Template instantiation depth exceeds 64");
+        return nullptr;
+    }
+    size_t Requester = VisibilityUnit.value_or(CurrentUnit);
+    size_t SavedUnit = CurrentUnit;
+    scope_exit RestoreUnit([&] { selectUnit(SavedUnit); });
+    SaveAndRestore<std::optional<size_t>> Visibility(VisibilityUnit, Requester);
+    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());
+    });
+    std::string Name = Definition.Decl->getName() + "<" + Key + ">";
+    auto Function = Clone.function(Definition.Decl->getFunction(), Name);
+    if (!Function || !FuncGen->emitPrototype(Function->getProto())) return nullptr;
+    auto Signatures = FuncGen->getOverloads(Name);
+    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,
+        Definition.OwnerUnit, Requester, TemplateDepth + 1});
+    return Signature;
+}
+
+void CodeGen::drainTemplateBodies() {
+    size_t SavedUnit = CurrentUnit;
+    scope_exit RestoreUnit([&] { selectUnit(SavedUnit); });
+    while (NextTemplateBody < TemplateInstances.size()) {
+        // Emission may append instances, so keep no vector element references.
+        const auto &Instance = TemplateInstances[NextTemplateBody++];
+        auto *Function = Instance.Function.get();
+        auto *Declaration = Instance.Decl;
+        size_t Owner = Instance.OwnerUnit;
+        size_t Requester = Instance.RequesterUnit;
+        unsigned Depth = Instance.Depth;
+        SaveAndRestore<std::optional<size_t>> Visibility(VisibilityUnit, Requester);
+        SaveAndRestore<unsigned> InstantiationDepth(TemplateDepth, Depth);
+        SaveAndRestore<IdentifierMap<SymbolInfo>> SymbolContext(Symbols, TemplateSymbols.at(Declaration));
+        selectUnit(Owner);
+        emitStmt(Function);
+    }
+}