TypeScript Structural Subtyping Engine

This challenge asks you to implement a simplified structural subtyping engine in TypeScript. You will create a function that determines if one type is a subtype of another based on their structure, mimicking TypeScript's structural typing system. This is a fundamental concept in statically typed languages, enabling flexible and robust code design.

Problem Description

You need to build a function, isSubtype<T, U>(): boolean, that checks if type T is structurally a subtype of type U. In structural typing, a type T is considered a subtype of U if T has all the members (properties and methods) that U has, and the types of those members are also compatible (either T's member is a subtype of U's member, or they are the same type).

Key Requirements:

1. Property Checks: For every property p in U, T must also have a property p, and the type of T[p] must be a subtype of the type of U[p].
2. Method Checks: For every method m in U, T must also have a method m, and the signature of T[m] must be assignable to the signature of U[m]. This means:
   • The number of parameters must be the same or T's method can have more optional parameters at the end.
   • Each parameter in T's method must be a supertype of the corresponding parameter in U's method.
   • The return type of T's method must be a subtype of the return type of U's method.
3. Primitive Types: Handle basic primitive types (string, number, boolean, null, undefined, symbol, bigint) and their relationships (e.g., null is a subtype of object, undefined is a subtype of null).
4. Object Types: Recursively check for structural compatibility for object types.
5. Array Types: An array type T[] is a subtype of U[] if T is a subtype of U.
6. Union Types: A | B is a subtype of C if both A is a subtype of C and B is a subtype of C. C is a subtype of A | B if C is a subtype of A or C is a subtype of B.
7. Intersection Types: A & B is a subtype of C if A is a subtype of C and B is a subtype of C. C is a subtype of A & B if C is a subtype of A or C is a subtype of B. (For simplicity in this challenge, we'll primarily focus on the A & B is subtype of C case and C is subtype of A & B implies C is subtype of A and C is subtype of B).
8. Function Types: A function type T is a subtype of U if the parameter types of T are supertypes of U's parameter types (contravariance) and the return type of T is a subtype of U's return type (covariance).

Expected Behavior:

The isSubtype<T, U>() function should return true if T can be assigned to U structurally, and false otherwise.

Edge Cases:

• Handling of any and unknown types. any is a subtype of everything and everything is a subtype of any. unknown is only a subtype of any and only any is a subtype of unknown.
• Optional properties.
• Readonly properties.
• Methods with different numbers of parameters (considering optionality).
• Recursive type definitions.

Examples

Example 1: Basic Property Subtyping

Input:
type A = { name: string; age: number };
type B = { name: string };

Output: isSubtype<A, B>() // true

Explanation: Type B has a 'name' property of type 'string'. Type A also has a 'name' property of type 'string'. Since A has all members of B, A is a subtype of B.

Example 2: Method Signature Compatibility

Input:
type GreeterA = { greet: (name: string) => void };
type GreeterB = { greet: (name?: string) => void };

Output: isSubtype<GreeterA, GreeterB>() // true

Explanation: GreeterB's 'greet' method has an optional parameter 'name'. GreeterA's 'greet' method has a required parameter 'name'. For subtyping, the parameter in the subtype can be more general (a supertype) or optional. Here, 'string' is assignable to 'string | undefined', so GreeterA is a subtype of GreeterB.

Example 3: Union Type Subtyping

Input:
type UnionA = string | number;
type UnionB = string | number | boolean;

Output: isSubtype<UnionA, UnionB>() // true

Explanation: Every type within UnionA (string, number) is also present in UnionB. Therefore, UnionA is a subtype of UnionB.

Example 4: Complex Method Subtyping

Input:
type FuncA = (a: string | number, b?: boolean) => number;
type FuncB = (a: string, b: boolean) => number | string;

Output: isSubtype<FuncA, FuncB>() // false

Explanation:
- Parameter 'a': FuncA expects 'string | number', FuncB expects 'string'. 'string | number' is NOT a supertype of 'string' (it's the other way around for parameter assignment). This violates contravariance.
- Parameter 'b': FuncA expects 'boolean | undefined', FuncB expects 'boolean'. 'boolean | undefined' IS a supertype of 'boolean'.
- Return type: FuncA returns 'number', FuncB returns 'number | string'. 'number' IS a subtype of 'number | string' (covariance).
However, the failure on parameter 'a' makes FuncA NOT a subtype of FuncB.

Example 5: Nested Object Subtyping

Input:
type OuterA = {
  inner: {
    id: number;
    value: string;
  }
};
type OuterB = {
  inner: {
    id: number;
  }
};

Output: isSubtype<OuterA, OuterB>() // true

Explanation: The 'inner' property in OuterB requires an object with an 'id'. OuterA's 'inner' property has an object with both 'id' and 'value'. Since the structure of OuterA.inner satisfies the requirements of OuterB.inner, OuterA is a subtype of OuterB.

Constraints

• The isSubtype function should not rely on runtime type information like instanceof or typeof in a way that breaks the structural nature of the check. It should operate on type-level information conceptually.
• The implementation should aim for reasonable performance for moderately nested types. Avoid exponential complexity where possible.
• Assume valid TypeScript type syntax for input.
• You will need to use TypeScript's type system features (like conditional types, infer, mapped types, etc.) to represent and manipulate types within your engine.

Notes

This is a conceptual challenge. You are not literally compiling TypeScript code to check subtyping. Instead, you are building a representation of a subtyping system within TypeScript itself. Think about how you can use conditional types and recursive type definitions to express the rules of structural subtyping.

You'll likely need helper types to break down complex type structures (like unions, intersections, object types, function types) and apply the subtyping rules recursively.

Consider how to handle the basic primitive types and their predefined subtyping relationships.

This is an advanced TypeScript challenge that requires a deep understanding of its type system. Good luck!