From c56877035d6600b463a9cbf0e339f7548c0b46fd Mon Sep 17 00:00:00 2001 From: _ov4 Date: Wed, 21 Oct 2026 05:54:26 +0000 Subject: feat(codegen): instantiate function templates by deduction Co-Authored-By: Claude Opus 5.5 --- lib/CodeGen/CodeGen.cc | 67 ++++++++++-- lib/CodeGen/ConstantGen.cc | 2 +- lib/CodeGen/FunctionGen.cc | 6 +- lib/CodeGen/GlobalGen.cc | 2 +- lib/CodeGen/StatementGen.cc | 2 +- lib/CodeGen/TemplateClone.cc | 238 +++++++++++++++++++++++++++++++++++++++++++ lib/CodeGen/TemplateClone.h | 32 ++++++ lib/CodeGen/TemplateGen.cc | 119 ++++++++++++++++++++++ 8 files changed, 452 insertions(+), 16 deletions(-) create mode 100644 lib/CodeGen/TemplateClone.cc create mode 100644 lib/CodeGen/TemplateClone.h create mode 100644 lib/CodeGen/TemplateGen.cc (limited to 'lib/CodeGen') 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 &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 Definitions; std::optional 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 Location(DiagnosticLine, UserConflict ? It->second.Line : DiagnosticLine); @@ -212,7 +213,7 @@ void CodeGen::compile(const std::vector &Sources) { std::string TypeName; if (auto *T = dynamic_cast(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(S.get())) { Reserve(F->getProto()->getName(), true, F->getProto()->isOverload()); @@ -310,6 +311,8 @@ void CodeGen::compile(const std::vector &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 &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 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> &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 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> 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> Bindings; + for (const auto &Param : Definition.Decl->getParams()) Bindings.emplace(Param.Name, std::vector{}); + 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 FunctionGen::getOverloads(const std::string &Name) const { +std::vector FunctionGen::getOverloads(const std::string &Name, bool AllUnits) const { std::vector 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(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 + +using namespace cps; +using namespace cps::detail; + +namespace { +template std::unique_ptr located(std::unique_ptr 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 &Parts) { + std::string Result; + for (const auto &Part : Parts) { + if (!Result.empty()) Result += ','; + Result += Part; + } + return Result; + }; + std::function()> Parse = [&]() -> std::vector { + size_t Start = Position; + while (Position < Name.size() && + (std::isalnum(static_cast(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 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> TemplateClone::arguments( + const std::vector> &Args) { + std::vector> Result; + for (const auto &Arg : Args) { + if (auto *Pack = dynamic_cast(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(Name), Pack)); + } else Result.push_back(expression(Arg.get())); + } + return Result; +} + +std::vector> TemplateClone::body( + const std::vector> &Body) { + std::vector> Result; + for (const auto &Stmt : Body) Result.push_back(statement(Stmt.get())); + return Result; +} + +std::unique_ptr TemplateClone::expression(ExprAST *Expr) { + if (!Expr) return nullptr; + std::unique_ptr Copy; + if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getVal()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getVal()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getVal()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getVal()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getVal(), E->isCString()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getName()); + else if (auto *E = dynamic_cast(Expr)) { + std::vector> Indices; + for (const auto &Index : E->getIndices()) Indices.push_back(expression(Index.get())); + Copy = std::make_unique(E->getName(), std::move(Indices), E->getLine()); + } else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getOp(), expression(E->getOperand())); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(E->getOp(), expression(E->getLHS()), expression(E->getRHS()), E->getLine()); + else if (auto *E = dynamic_cast(Expr)) { + std::vector 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(E->getCallee(), arguments(E->getArgs()), E->getLine(), std::move(Types)); + } else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(expression(E->getReceiver()), E->getMethod(), arguments(E->getArgs()), E->getLine()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(type(E->getClassName()), arguments(E->getArgs()), E->getLine()); + else if (auto *E = dynamic_cast(Expr)) Copy = std::make_unique(type(E->getTypeName()), expression(E->getOperand())); + else if (auto *E = dynamic_cast(Expr)) { + std::vector 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(E->getBaseName(), std::move(Accesses), E->getLine()); + } else if (auto *E = dynamic_cast(Expr)) { + auto Target = expression(E->getTarget()); + Copy = std::make_unique(std::unique_ptr(static_cast(Target.release()))); + } else if (dynamic_cast(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 TemplateClone::statement(StmtAST *Stmt) { + std::unique_ptr Copy; + if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(S->getName(), type(S->getType()), arguments(S->getArgs()), S->hasParens()); + else if (auto *S = dynamic_cast(Stmt)) { + std::vector, std::unique_ptr>> Bounds; + for (const auto &B : S->getBounds()) Bounds.emplace_back(expression(B.first.get()), expression(B.second.get())); + Copy = std::make_unique(S->getName(), std::move(Bounds), type(S->getType())); + } else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(S->getName(), expression(S->getValue())); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(S->getName(), expression(S->getExpr())); + else if (auto *S = dynamic_cast(Stmt)) { + std::vector> Indices; + for (const auto &Index : S->getIndices()) Indices.push_back(expression(Index.get())); + Copy = std::make_unique(S->getName(), std::move(Indices), expression(S->getExpr()), S->getLine()); + } else if (auto *S = dynamic_cast(Stmt)) { + auto Target = expression(S->getTarget()); + Copy = std::make_unique(std::unique_ptr(static_cast(Target.release())), expression(S->getExpr())); + } else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getTarget())); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getTarget())); + else if (auto *S = dynamic_cast(Stmt)) { + std::vector> Exprs; + for (const auto &E : S->getExprs()) Exprs.push_back(expression(E.get())); + Copy = std::make_unique(std::move(Exprs)); + } else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getRetVal())); + else if (auto *S = dynamic_cast(Stmt)) { + CallExprAST Call(S->getCallee(), {}, S->getLine(), S->getTemplateArgs()); + auto Expr = expression(&Call); + auto *Cloned = static_cast(Expr.get()); + Copy = std::make_unique(S->getCallee(), arguments(S->getArgs()), S->getLine(), Cloned->getTemplateArgs()); + } else if (auto *S = dynamic_cast(Stmt)) { + auto Call = expression(S->getCall()); + Copy = std::make_unique(std::unique_ptr(static_cast(Call.release()))); + } else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getCond()), body(S->getThenStmts()), body(S->getElseStmts())); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getCond()), body(S->getBody())); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(body(S->getBody()), expression(S->getCond())); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(S->getVarName(), expression(S->getStart()), expression(S->getEnd()), expression(S->getStep()), body(S->getBody())); + else if (auto *S = dynamic_cast(Stmt)) { + std::vector 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(S->getSelector(), std::move(Branches)); + } else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(body(S->getBody()), body(S->getCatchBody())); + else if (dynamic_cast(Stmt)) Copy = std::make_unique(); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getFileName()), S->getMode(), S->getLine()); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getFileName()), S->getVarName(), S->getLine()); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getFileName()), expression(S->getData()), S->getLine()); + else if (auto *S = dynamic_cast(Stmt)) Copy = std::make_unique(expression(S->getFileName()), S->getLine()); + else if (dynamic_cast(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 TemplateClone::function(const FunctionDefAST *Source, + const std::string &Name, const std::string &OwnerClass) { + auto SavedNames = PackNames; + const auto *Proto = Source->getProto(); + std::vector 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(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(std::move(CopyProto), body(Source->getBody())), Source); + PackNames = std::move(SavedNames); + return Failed ? nullptr : std::move(Copy); +} + +std::unique_ptr TemplateClone::klass(const ClassTypeDeclAST *Source, + const std::string &Name) { + std::vector Fields = Source->getFields(); + for (auto &Field : Fields) Field.TypeName = type(Field.TypeName); + std::vector> Methods; + for (const auto &Method : Source->getMethods()) + Methods.push_back(function(Method.get(), Method->getProto()->getName(), Name)); + auto Copy = located(std::make_unique(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 + +namespace cps::detail { + +using TemplateBindings = IdentifierMap>; + +// Clones own all children; source ASTs remain reusable for later instances. +class TemplateClone { + const TemplateBindings &Bindings; + IdentifierMap> PackNames; + std::function Error; + bool Failed = false; + void fail(int Line, const std::string &Message); + std::vector> arguments(const std::vector> &Args); + std::vector> body(const std::vector> &Body); + std::unique_ptr expression(ExprAST *Expr); + std::unique_ptr statement(StmtAST *Stmt); +public: + TemplateClone(const TemplateBindings &Bindings, + std::function Error) + : Bindings(Bindings), Error(std::move(Error)) {} + std::string type(const std::string &Name); + std::unique_ptr function(const FunctionDefAST *Source, + const std::string &Name, const std::string &OwnerClass = {}); + std::unique_ptr 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 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(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(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> Visibility(VisibilityUnit, Requester); + selectUnit(Definition.OwnerUnit); + SaveAndRestore Location(DiagnosticLine, Definition.Decl->getLine()); + TemplateClone Clone(Bindings, [this](int Line, const std::string &Message) { + SaveAndRestore 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> Visibility(VisibilityUnit, Requester); + SaveAndRestore InstantiationDepth(TemplateDepth, Depth); + SaveAndRestore> SymbolContext(Symbols, TemplateSymbols.at(Declaration)); + selectUnit(Owner); + emitStmt(Function); + } +} -- cgit v1.3.1-4-g156e