Hone logo
Hone
Problems

Advanced TypeScript Type Inference Engine

This challenge asks you to build a simplified, yet sophisticated, type inference engine within TypeScript. You'll be creating a system that can analyze a structured representation of code (akin to an Abstract Syntax Tree or AST) and deduce the types of variables, functions, and expressions. This is a fundamental concept in compilers and static analysis tools, enabling early detection of type errors and improving code maintainability.

Problem Description

Your task is to implement a type inference engine that can process a simplified, AST-like structure representing TypeScript code. The engine should be able to infer types for:

  • Variables: Based on their initial assignments.
  • Function Parameters: Based on their usage within the function body.
  • Function Return Types: Based on the types of values returned from the function.
  • Basic Expression Types: Such as arithmetic operations, string concatenations, and boolean comparisons.
  • Union and Intersection Types: Inferring when a variable can hold one of several types, or must hold all of a set of types.
  • Generic Types: Inferring type arguments for generic functions and classes.

The engine should maintain a "type environment" that maps identifiers (variable names) to their inferred types. When encountering a new declaration, it adds to this environment. When analyzing an expression, it consults the environment and applies type rules to determine the expression's type.

Key Requirements:

  1. Type Representation: Define a robust set of types that can be represented, including primitives (string, number, boolean), any, unknown, union types (|), intersection types (&), and generic types (e.g., Array<T>, Promise<T>).
  2. Type Environment: Implement a data structure to store and manage the type environment. This environment should support scoping (e.g., function scopes).
  3. Inference Rules: Implement the logic for inferring types based on various language constructs:
    • Assignments: let x: Type = value; or let x = value;
    • Function Declarations: function foo(param: Type1): ReturnType { ... } or function foo(param) { ... }
    • Function Calls: foo(arg)
    • Binary Operations: a + b, a > b, a && b
    • Conditional Expressions: condition ? expr1 : expr2
  4. Type Compatibility and Unification: Develop mechanisms to check if two types are compatible (e.g., can a string be assigned to a number | string?) and to unify types (e.g., inferring the common type of two expressions).
  5. Error Reporting: While not strictly required for output, the engine should ideally be able to identify and flag type mismatches. For this challenge, we'll focus on successful inference.

Expected Behavior:

The engine will take a structured representation of code and produce a mapping of variable/function names to their inferred types.

Edge Cases:

  • Recursive type definitions (though a full solution might be out of scope, consider how you might handle simple cases or detect cycles).
  • Inference with any and unknown types.
  • Handling of type parameters in generics when no explicit types are provided.

Examples

Let's define a simplified AST node structure for illustration:

// Placeholder for AST node types
type ASTNode =
  | VariableDeclaration
  | FunctionDeclaration
  | CallExpression
  | BinaryExpression
  | Literal
  | Identifier;

interface VariableDeclaration {
  type: "VariableDeclaration";
  name: string;
  initializer: ASTNode;
  // optional explicit type annotation
  typeAnnotation?: Type;
}

interface FunctionDeclaration {
  type: "FunctionDeclaration";
  name: string;
  parameters: Parameter[];
  body: ASTNode[];
  returnTypeAnnotation?: Type; // optional explicit return type
}

interface Parameter {
  name: string;
  typeAnnotation?: Type; // optional explicit parameter type
}

interface CallExpression {
  type: "CallExpression";
  callee: Identifier;
  arguments: ASTNode[];
}

interface BinaryExpression {
  type: "BinaryExpression";
  operator: "+" | "-" | "*" | "/" | ">" | "<" | "&&" | "||";
  left: ASTNode;
  right: ASTNode;
}

interface Literal {
  type: "Literal";
  value: string | number | boolean;
}

interface Identifier {
  type: "Identifier";
  name: string;
}

// Type System Representation
type Type =
  | PrimitiveType
  | UnionType
  | IntersectionType
  | GenericType
  | AnyType
  | UnknownType;

interface PrimitiveType {
  kind: "primitive";
  name: "string" | "number" | "boolean";
}

interface UnionType {
  kind: "union";
  types: Type[];
}

interface IntersectionType {
  kind: "intersection";
  types: Type[];
}

interface GenericType {
  kind: "generic";
  name: string; // e.g., "Array", "Promise"
  typeArguments: Type[];
}

interface AnyType {
  kind: "any";
}

interface UnknownType {
  kind: "unknown";
}

// Example structure for inferred types
type TypeEnvironment = Map<string, Type>;
type InferenceResult = {
  environment: TypeEnvironment;
  errors?: string[]; // Optional for error reporting
};

Example 1:

Input AST (simplified):
[
  {
    type: "VariableDeclaration",
    name: "age",
    initializer: { type: "Literal", value: 30 }
  },
  {
    type: "VariableDeclaration",
    name: "name",
    initializer: { type: "Literal", value: "Alice" }
  },
  {
    type: "VariableDeclaration",
    name: "isStudent",
    initializer: { type: "Literal", value: true }
  }
]

Output:
{
  environment: Map {
    'age' => { kind: 'primitive', name: 'number' },
    'name' => { kind: 'primitive', name: 'string' },
    'isStudent' => { kind: 'primitive', name: 'boolean' }
  },
  errors: []
}

Explanation: The engine processes each VariableDeclaration. For literals, it directly infers the corresponding primitive type. These are added to the type environment.

Example 2:

Input AST (simplified):
[
  {
    type: "VariableDeclaration",
    name: "message",
    initializer: {
      type: "BinaryExpression",
      operator: "+",
      left: { type: "Identifier", name: "name" },
      right: { type: "Literal", value: "'s age is '" } // Assuming string literal
    }
  },
  {
    type: "VariableDeclaration",
    name: "canVote",
    initializer: {
      type: "BinaryExpression",
      operator: ">",
      left: { type: "Identifier", name: "age" },
      right: { type: "Literal", value: 18 }
    }
  }
]
// Assume 'name' and 'age' are already in the environment from a previous step
// environment: Map { 'name' => { kind: 'primitive', name: 'string' }, 'age' => { kind: 'primitive', name: 'number' } }

Output:
{
  environment: Map {
    'name' => { kind: 'primitive', name: 'string' },
    'age' => { kind: 'primitive', name: 'number' },
    'message' => { kind: 'primitive', name: 'string' },
    'canVote' => { kind: 'primitive', name: 'boolean' }
  },
  errors: []
}

Explanation: For message, the binary expression + between a string (name) and a string literal results in a string. For canVote, the binary expression > between a number (age) and a number literal results in a boolean.

Example 3: Function Inference and Union Types

Input AST (simplified):
[
  {
    type: "VariableDeclaration",
    name: "processInput",
    initializer: {
      type: "FunctionDeclaration",
      name: "processInput",
      parameters: [
        { name: "input", typeAnnotation: { kind: "union", types: [{kind: "primitive", name: "string"}, {kind: "primitive", name: "number"}] } }
      ],
      body: [
        {
          type: "ReturnStatement", // Assume this exists, or inferred from last expression
          expression: {
            type: "ConditionalExpression",
            condition: { type: "BinaryExpression", operator: ">", left: { type: "Identifier", name: "input" }, right: { type: "Literal", value: 100 } },
            consequent: { type: "Literal", value: "Large Number" },
            alternate: { type: "Identifier", name: "input" }
          }
        }
      ]
    }
  }
]

Output:
{
  environment: Map {
    'processInput' => { // This would be a function type, simplified for this output
      kind: 'function',
      parameters: [ { name: 'input', type: { kind: 'union', types: [{ kind: 'primitive', name: 'string' }, { kind: 'primitive', name: 'number' }] } } ],
      returnType: { kind: 'union', types: [{ kind: 'primitive', name: 'string' }, { kind: 'primitive', name: 'number' }] }
    }
  },
  errors: []
}

Explanation: The processInput function is declared. Its parameter input is explicitly typed as string | number. Inside the function, a conditional expression is used. The consequent is a string literal, and the alternate is the input parameter itself. If input is a number and greater than 100, it returns "Large Number" (string). Otherwise, it returns input, which could be a string or a number. The union of these possible return types (string and number) becomes the inferred return type of the function.

Constraints

  • The input will be a valid, simplified AST structure representing TypeScript code.
  • You will only need to infer types for the constructs explicitly mentioned (variables, basic expressions, functions, unions, generics).
  • Focus on the core inference logic; intricate error handling and recovery are not primary concerns for this challenge.
  • Performance is not a critical bottleneck, but aim for a reasonably efficient algorithm.

Notes

  • Consider how you will represent function types and generic instantiations in your Type system.
  • You'll need to implement rules for type compatibility and potentially a unification algorithm.
  • Start with simpler cases (primitives, assignments) and gradually add complexity (functions, unions).
  • Think about the flow of information: how types are passed into functions, how they are inferred within function bodies, and how they are returned.
  • For function inference, you'll need to:
    • Infer parameter types if not provided.
    • Infer the return type by analyzing all possible return paths.
    • Create a function type in your type system.
  • For generic types, you'll need a way to represent type parameters and infer them based on usage.
Loading editor...
typescript