Plan 01: Type System Polymorphic Hierarchy

Goal: Replace the flat, string-based TypeRef struct with a polymorphic Type interface, eliminating string-based type checking, introducing static singletons for primitives, and supporting first-class function signatures and structural types. Inspiration: Go's go/types/type.go, cmd/compile/internal/types2, and universe.go.

1. Problem Statement & Root Cause

Currently, Kyna defines all types in compiler/kyna_types/include/kyna/semantics/type_model.hpp via:

1struct TypeRef {
2  std::string name{"void"};
3  bool nullable{false};
4  std::vector<TypeRef> typeArgs;
5  std::vector<TypeRef> unionTypes;
6  std::string str() const;
7};

Critical Flaws

1. Dynamic Heap String Allocations: Every primitive type check (t("int"), t("str"), t("bool")) allocates a new std::string on the heap.
2. Loss of Function Signatures: Higher-order functions collapse to TypeRef{"func"}, making it impossible to check argument or return type compatibility of callbacks.
3. Encoding Metadata in String Names: Classes are prefixed with "class:Circle", modules with "module:math", and unions with "union".
4. Equality via Serialization: Type checks rely on left.type.str() == right.type.str(), which is slow and prone to formatting bugs (e.g. TypeRef::str() formatting "union | int | str").

2. Target Architecture: The Polymorphic Type Hierarchy

2.1 The Type Interface

1namespace kyna::types {
2 
3enum class TypeKind : uint8_t {
4  Basic,
5  Named,
6  Signature,
7  Interface,
8  Struct,
9  Array,
10  Map,
11  Union,
12  Nullable,
13  TypeParam
14};
15 
16class Type {
17public:
18  virtual ~Type() = default;
19  virtual TypeKind kind() const = 0;
20  virtual const Type* underlying() const = 0;
21  virtual std::string str() const = 0;
22  virtual bool isAssignableTo(const Type* target) const = 0;
23  virtual bool isIdenticalTo(const Type* other) const = 0;
24};
25 
26using TypePtr = const Type*; // Types are interned and immutable
27 
28} // namespace kyna::types

2.2 Concrete Type Implementations

1. BasicType: Singleton instances for int, float, bool, string, void, null, any.

   cpp

   cppCopy

   1class BasicType : public Type {
   2public:
   3  enum class BasicKind { Int, Float, Bool, String, Void, Null, Any };
   4  BasicKind basicKind() const;
   5  TypeKind kind() const override { return TypeKind::Basic; }
   6  const Type* underlying() const override { return this; }
   7  std::string str() const override;
   8  bool isAssignableTo(const Type* target) const override;
   9  bool isIdenticalTo(const Type* other) const override;
   10};

2. SignatureType: First-class function signatures.

   cpp

   cppCopy

   1class SignatureType : public Type {
   2private:
   3  std::vector<TypePtr> params_;
   4  TypePtr returnType_;
   5  TypePtr receiverType_{nullptr}; // for class methods
   6  bool isVariadic_{false};
   7public:
   8  TypeKind kind() const override { return TypeKind::Signature; }
   9  const std::vector<TypePtr>& params() const { return params_; }
   10  TypePtr returnType() const { return returnType_; }
   11  TypePtr receiverType() const { return receiverType_; }
   12  // ...
   13};

3. NamedType: Nominal classes and user-defined types.

   cpp

   cppCopy

   1class NamedType : public Type {
   2private:
   3  std::string name_;
   4  TypePtr underlying_{nullptr};
   5  std::vector<MethodSymbol> methods_;
   6public:
   7  TypeKind kind() const override { return TypeKind::Named; }
   8  const std::string& name() const { return name_; }
   9  const Type* underlying() const override { return underlying_; }
   10  // ...
   11};

4. Universe: Zero-allocation static registry.

   cpp

   cppCopy

   1class Universe {
   2public:
   3  static const BasicType* Int();
   4  static const BasicType* Float();
   5  static const BasicType* Bool();
   6  static const BasicType* String();
   7  static const BasicType* Void();
   8  static const BasicType* Null();
   9  static const BasicType* Any();
   10};

3. Implementation Steps

• Step 1: Create compiler/kyna_types/include/kyna/types/type.hpp
  • Define TypeKind, Type abstract interface, and Universe factory.
• Step 2: Implement Concrete Types
  • Implement BasicType, SignatureType, NamedType, UnionType, NullableType under compiler/kyna_types/src/types/.
• Step 3: Update CMakeLists.txt
  • Add newly created source files explicitly to compiler/kyna_types/CMakeLists.txt.
• Step 4: Provide Backward Compatibility Adapter
  • Maintain TypeRef as a thin wrapper or transition layer so existing code compiles incrementally.
• Step 5: Migrate Semantic Type Checker
  • Update type_checker.cpp and analyzer.cpp to use Universe::Int(), Universe::Bool(), and pointer comparisons instead of string matching.
• Step 6: Eliminate TypeRef::str() Serialization for Comparison
  • Replace sameParameters() in statement_checker.cpp with Type::isIdenticalTo().

4. Verification Plan

1. Unit Tests:
   • Create tests/types/test_type_hierarchy.cpp verifying pointer identity, assignability, and immutability.
2. Regression Verification:
   • Run ctest --test-dir build-debug --output-on-failure.
3. Repository Architecture Verifier:
   • Run python3 build_tools/verify_repository_architecture.py.