refactor

11 files changed, 478 insertions, 0 deletions

diff --git a/src/lang/builtin/index.ts b/src/lang/builtin/index.ts
new file mode 100644
index 0000000..373f54a
--- /dev/null
+++ b/src/lang/builtin/index.ts
@@ -0,0 +1,34 @@
+import {
+  AddNumbers,
+  AddStrings,
+  Multiply,
+  ToString,
+  UnarrayIfOnlyHead,
+} from "../util";
+
+export type FnError<T extends string> = `Function execution error: ${T}`;
+
+export type BUILTIN_Arr<Args extends readonly any[]> = Args;
+
+export type BUILTIN_ToString<Args extends readonly any[]> = ToString<
+  UnarrayIfOnlyHead<{
+    [Idx in keyof Args]: ToString<Args[Idx]>;
+  }>
+>;
+
+export type BUILTIN_Add<Args extends readonly any[]> =
+  Args extends readonly string[]
+    ? AddStrings<Args>
+    : Args extends readonly number[]
+    ? AddNumbers<Args>
+    : FnError<`Cannot add operands ${ToString<Args>}`>;
+
+export type BUILTIN_Mul<Args extends readonly any[]> = Args extends [
+  infer A,
+  infer B,
+  infer C
+]
+  ? FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>
+  : Args extends [infer M extends number, infer N extends number]
+  ? Multiply<M, N>
+  : FnError<`Can only multiply [number, number], but got ${ToString<Args>}`>;
diff --git a/src/lang/core/common.ts b/src/lang/core/common.ts
new file mode 100644
index 0000000..c1a1dc3
--- /dev/null
+++ b/src/lang/core/common.ts
@@ -0,0 +1,57 @@
+export enum TokenType {
+  OPEN_PAREN = "(",
+  CLOSE_PAREN = ")",
+  SPACE = " ",
+  SEMICOLON = ";",
+  COMMA = ",",
+  NAME = "NAME",
+}
+
+export enum TokenSubType {
+  NA = "NA",
+  LITERAL = "LITERAL",
+  REFERENCE = "REFERENCE",
+}
+
+export type Token<
+  Type extends TokenType = TokenType,
+  Name extends string = string
+> = {
+  type: Type;
+  name: Name;
+};
+
+export type LexerCtx = {
+  next: string;
+  nameCollection: string;
+  tokens: readonly Token[];
+};
+
+export enum NodeType {
+  INT = "INT",
+  EXT = "EXT",
+  PARSER_ERROR = "PARSER_ERROR",
+}
+
+export type ASTNode<
+  Type extends NodeType = NodeType,
+  Name extends string = string,
+  Value extends any = any,
+  Children extends readonly ASTNode[] = readonly ASTNode<
+    NodeType,
+    string,
+    any,
+    any
+  >[]
+> = {
+  type: Type;
+  name: Name;
+  value: Value;
+  children: Children;
+};
+
+export type ParserCtx = {
+  remainingTokens: readonly Token[];
+  lastToken: Token | null;
+  stack: readonly ASTNode[];
+};
diff --git a/src/lang/core/eval.ts b/src/lang/core/eval.ts
new file mode 100644
index 0000000..6a25a6c
--- /dev/null
+++ b/src/lang/core/eval.ts
@@ -0,0 +1,42 @@
+import {
+  BUILTIN_Add,
+  BUILTIN_Arr,
+  BUILTIN_Mul,
+  BUILTIN_ToString,
+} from "../builtin";
+import { ASTNode, NodeType } from "./common";
+import { Lex } from "./lexer";
+import { Parse } from "./parser";
+
+export type SENTINEL_NO_BUILTIN = "__NO_BUILTIN__";
+export type MapBuiltins<Node extends ASTNode> =
+  Node["children"] extends infer Children extends readonly ASTNode[]
+    ? {
+        [Idx in keyof Children]: Children[Idx] extends ASTNode
+          ? Evaluate<Children[Idx]>
+          : never;
+      } extends infer Args extends readonly any[]
+      ? Node["name"] extends "tostring"
+        ? BUILTIN_ToString<Args>
+        : Node["name"] extends "arr"
+        ? BUILTIN_Arr<Args>
+        : Node["name"] extends "add"
+        ? BUILTIN_Add<Args>
+        : Node["name"] extends "mul"
+        ? BUILTIN_Mul<Args>
+        : SENTINEL_NO_BUILTIN
+      : never
+    : never;
+
+export type EvalError<T extends string> = `Eval error: ${T}`;
+
+export type Evaluate<Node extends ASTNode> = Node["type"] extends NodeType.INT
+  ? Node["value"]
+  : Node["type"] extends NodeType.EXT
+  ? MapBuiltins<Node>
+  : EvalError<`Unhandled node type ${Node["type"]}`>;
+
+const input = `` as const;
+const lex_result = null as unknown as Lex<typeof input>;
+const parse_result = null as unknown as Parse<typeof lex_result>;
+const eval_result = null as unknown as Evaluate<typeof parse_result>;
diff --git a/src/lang/core/index.ts b/src/lang/core/index.ts
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/lang/core/index.ts
diff --git a/src/lang/core/lexer.ts b/src/lang/core/lexer.ts
new file mode 100644
index 0000000..33a408a
--- /dev/null
+++ b/src/lang/core/lexer.ts
@@ -0,0 +1,62 @@
+import { LexerCtx, Token, TokenSubType, TokenType } from "./common";
+
+export type BreakingToken =
+  | TokenType.OPEN_PAREN
+  | TokenType.CLOSE_PAREN
+  | TokenType.COMMA
+  | TokenType.SEMICOLON
+  | TokenType.SPACE;
+
+export type IsWhitespace<T extends string> = T extends `${TokenType.SPACE}`
+  ? true
+  : T extends `${TokenType.COMMA}`
+  ? true
+  : T extends `${TokenType.SEMICOLON}`
+  ? true
+  : false;
+
+export type ProcessNameCollection<
+  Ctx extends LexerCtx,
+  Tail extends string,
+  _Token extends Token | null
+> = {
+  next: Tail;
+  nameCollection: "";
+  tokens: _Token extends null
+    ? [
+        ...Ctx["tokens"],
+        ...(Ctx["nameCollection"] extends ""
+          ? []
+          : [Token<TokenType.NAME, Ctx["nameCollection"]>])
+      ]
+    : [
+        ...Ctx["tokens"],
+        ...(Ctx["nameCollection"] extends ""
+          ? [_Token]
+          : [Token<TokenType.NAME, Ctx["nameCollection"]>, _Token])
+      ];
+};
+
+export type IsOpen<T> = T extends `${TokenType.OPEN_PAREN}` ? true : false;
+export type IsClose<T> = T extends `${TokenType.CLOSE_PAREN}` ? true : false;
+
+export type _Lex<Ctx extends LexerCtx> =
+  Ctx["next"] extends `${infer Head}${infer Tail}`
+    ? IsWhitespace<Head> extends true
+      ? _Lex<ProcessNameCollection<Ctx, Tail, null>>
+      : IsOpen<Head> extends true
+      ? _Lex<ProcessNameCollection<Ctx, Tail, Token<TokenType.OPEN_PAREN>>>
+      : IsClose<Head> extends true
+      ? _Lex<ProcessNameCollection<Ctx, Tail, Token<TokenType.CLOSE_PAREN>>>
+      : _Lex<{
+          next: Tail;
+          nameCollection: `${Ctx["nameCollection"]}${Head}`;
+          tokens: Ctx["tokens"];
+        }>
+    : Ctx["tokens"];
+
+export type Lex<Raw extends string> = _Lex<{
+  next: `${Raw};`;
+  tokens: [];
+  nameCollection: "";
+}>;
diff --git a/src/lang/core/parser.ts b/src/lang/core/parser.ts
new file mode 100644
index 0000000..79218e9
--- /dev/null
+++ b/src/lang/core/parser.ts
@@ -0,0 +1,220 @@
+import {
+  ASTNode,
+  NodeType,
+  ParserCtx,
+  Token,
+  TokenSubType,
+  TokenType,
+} from "./common";
+import { Lex } from "./lexer";
+
+/* 
+start
+if no 'lastName'
+then:
+    expect nextToken to be a name
+    lastName = nextToken
+    goto start
+    
+else:
+    if nextToken is name
+    then:
+        // we already have a lastName
+        mutate last element of stack to push lastName as child
+        lastName = nextToken
+        goto start
+
+    else:
+        //nextToken is openParen or close paren
+        if nextToken is closeParen
+        then:
+            set last element of stack as child of prev element on stack
+            pop stack
+            // [stack[last - 1].children.push(stack.pop)
+            goto start
+        else if nextToken is openParen:
+            push lastName onto stack
+            goto start
+
+
+finally:
+    // only one element remains on the stack
+    return stack[0]
+
+
+    CALL ( param, CALL2 ( param2 ) )
+
+    param2 ret call2 param ret call
+
+    | call
+    |-- param
+    |-- | call2
+        |-- param2
+
+ */
+
+export type Error<T extends string> = ASTNode<
+  NodeType.PARSER_ERROR,
+  "Error",
+  T,
+  []
+>;
+
+export type PushChild<Node extends ASTNode, Child extends ASTNode> = {
+  type: Node["type"];
+  value: Node["value"];
+  name: Node["name"];
+  children: [...Node["children"], Child];
+};
+
+export type PushChildToLastElementOfStack<
+  Stack extends ParserCtx["stack"],
+  Child extends ASTNode
+> = Stack extends [...infer Head, infer Tail extends ASTNode]
+  ? [...Head, PushChild<Tail, Child>]
+  : Stack extends [infer Only extends ASTNode]
+  ? [PushChild<Only, Child>]
+  : never;
+
+export type PushChildToSecondLastElementOfStack<
+  Stack extends ParserCtx["stack"],
+  Child extends ASTNode
+> = Stack extends [
+  ...infer Head,
+  infer Tail extends ASTNode,
+  infer Final extends ASTNode
+]
+  ? [...Head, PushChild<Tail, Child>, Final]
+  : Stack extends [infer Only extends ASTNode, infer Final extends ASTNode]
+  ? [PushChild<Only, Child>, Final]
+  : never;
+
+export type GetLastOnStack<Stack extends ParserCtx["stack"]> = Stack extends [
+  ...infer Head,
+  infer Tail extends ASTNode
+]
+  ? Tail
+  : Stack extends [infer Only extends ASTNode]
+  ? Only
+  : never;
+
+export type StackWithoutLast<Stack extends ParserCtx["stack"]> = Stack extends [
+  ...infer Head extends ASTNode[],
+  infer Tail
+]
+  ? [...Head]
+  : Stack extends [infer Only extends ASTNode]
+  ? []
+  : never;
+
+type NULL_SENTINEL = {
+  NULL: true;
+};
+
+export type ParseNumberLiteral<T extends string> =
+  T extends `${infer Inner extends number}` ? Inner : NULL_SENTINEL;
+
+export type ParseStringLiteral<T extends string> =
+  T extends `"${infer Inner extends string}"` ? Inner : NULL_SENTINEL;
+
+export type ResolveNodeFromToken<_Token extends Token> = ParseNumberLiteral<
+  _Token["name"]
+> extends number
+  ? ASTNode<NodeType.INT, "", ParseNumberLiteral<_Token["name"]>, []>
+  : ParseStringLiteral<_Token["name"]> extends string
+  ? ASTNode<NodeType.INT, "", ParseStringLiteral<_Token["name"]>, []>
+  : ASTNode<NodeType.EXT, _Token["name"], null, []>;
+
+export type _Parse<Ctx extends ParserCtx> = Ctx["remainingTokens"] extends [
+  infer Head extends Token,
+  ...infer Tail extends readonly Token[]
+]
+  ? Ctx["lastToken"] extends Token
+    ? Head["type"] extends TokenType.NAME
+      ? // we already have a lastName
+        // mutate last element of stack to push lastName as child
+        // lastName = nextToken
+        // goto start
+        _Parse<{
+          lastToken: Head;
+          remainingTokens: Tail;
+          stack: PushChildToLastElementOfStack<
+            Ctx["stack"],
+            ResolveNodeFromToken<Ctx["lastToken"]>
+          >;
+        }>
+      : //nextToken is openParen or close paren
+      Head["type"] extends TokenType.CLOSE_PAREN
+      ? // handle lastName
+        // set last element of stack as child of prev element on stack
+        // pop stack
+        // [stack[last - 1].children.push(stack.pop)
+        // goto start
+        _Parse<{
+          lastToken: null;
+          remainingTokens: Tail;
+          // first push the last name onto the children of the top
+          // then push the top onto the children of the next
+          // then remove the top
+          stack: StackWithoutLast<
+            PushChildToSecondLastElementOfStack<
+              Ctx["stack"],
+              PushChild<
+                GetLastOnStack<Ctx["stack"]>,
+                ResolveNodeFromToken<Ctx["lastToken"]>
+              >
+            >
+          >;
+        }>
+      : Head["type"] extends TokenType.OPEN_PAREN
+      ? // push lastName onto stack
+        // goto start
+        _Parse<{
+          lastToken: null;
+          remainingTokens: Tail;
+          stack: [...Ctx["stack"], ResolveNodeFromToken<Ctx["lastToken"]>];
+        }>
+      : Ctx & Error<`Was not expecting ${Head["type"]}`>
+    : // expect nextToken to be a name or close paren
+    Head["type"] extends TokenType.NAME
+    ? // lastName = nextToken
+      // goto start
+      _Parse<{
+        lastToken: Head;
+        remainingTokens: Tail;
+        stack: Ctx["stack"];
+      }>
+    : Head["type"] extends TokenType.CLOSE_PAREN
+    ? _Parse<{
+        lastToken: null;
+        remainingTokens: Tail;
+        // push the top onto the children of the next
+        // then remove the top
+        stack: StackWithoutLast<
+          PushChildToSecondLastElementOfStack<
+            Ctx["stack"],
+            GetLastOnStack<Ctx["stack"]>
+          >
+        >;
+      }>
+    : Ctx &
+        Error<`Expected nextToken to be a name or close paren at ${Head["type"]}`>
+  : Ctx["lastToken"] extends Token
+  ? // case where we ended with a name
+    _Parse<{
+      lastToken: null;
+      remainingTokens: [];
+      stack: PushChildToLastElementOfStack<
+        Ctx["stack"],
+        ResolveNodeFromToken<Ctx["lastToken"]>
+      >;
+    }>
+  : Ctx["stack"][0];
+
+export type Parse<Raw extends readonly Token[]> = _Parse<{
+  lastToken: null;
+  remainingTokens: Raw;
+  stack: [ASTNode<NodeType.EXT, "arr", null, []>];
+}>;
+
+const test_result = null as unknown as Parse<Lex<`test(135)`>>;
diff --git a/src/lang/index.ts b/src/lang/index.ts
new file mode 100644
index 0000000..8d119de
--- /dev/null
+++ b/src/lang/index.ts
@@ -0,0 +1 @@
+export * from "./core";
diff --git a/src/lang/util/index.ts b/src/lang/util/index.ts
new file mode 100644
index 0000000..00a3e54
--- /dev/null
+++ b/src/lang/util/index.ts
@@ -0,0 +1,3 @@
+export * from "./number";
+export * from "./utils";
+export * from "./string";
diff --git a/src/lang/util/number.ts b/src/lang/util/number.ts
new file mode 100644
index 0000000..132994b
--- /dev/null
+++ b/src/lang/util/number.ts
@@ -0,0 +1,34 @@
+export type NumberToArray<
+  Number extends number,
+  Carry extends readonly any[] = []
+> = Number extends Carry["length"]
+  ? Carry
+  : NumberToArray<Number, [...Carry, any]>;
+
+export type NumbersToArray<
+  Numbers extends readonly number[],
+  Carry extends readonly any[] = []
+> = Numbers extends [
+  infer Head extends number,
+  ...infer Tail extends readonly number[]
+]
+  ? NumbersToArray<Tail, [...Carry, ...NumberToArray<Head>]>
+  : Carry;
+
+export type AddNumbers<Numbers extends readonly number[]> =
+  NumbersToArray<Numbers> extends infer T extends readonly any[]
+    ? T["length"]
+    : never;
+
+export type MultiplyInner<
+  N extends number,
+  MS extends readonly any[],
+  Carry extends number = 0
+> = MS extends [infer Head extends number, ...infer Tail extends readonly any[]]
+  ? MultiplyInner<N, Tail, AddNumbers<[Carry, N]>>
+  : Carry;
+
+export type Multiply<M extends number, N extends number> = MultiplyInner<
+  M,
+  NumberToArray<N>
+>;
diff --git a/src/lang/util/string.ts b/src/lang/util/string.ts
new file mode 100644
index 0000000..5772f40
--- /dev/null
+++ b/src/lang/util/string.ts
@@ -0,0 +1,17 @@
+export type AddStrings<
+  Strings extends readonly string[],
+  Carry extends string = ""
+> = Strings extends [infer Head extends string, ...infer Tail extends string[]]
+  ? AddStrings<Tail, `${Carry}${Head}`>
+  : Carry;
+
+export type ToString<T, Carry extends string = ""> = T extends string | number
+  ? `${T}`
+  : T extends readonly any[]
+  ? T extends readonly [infer Head, ...infer Tail]
+    ? `${ToString<
+        Tail,
+        `${Carry extends "" ? "" : `${Carry}, `}${ToString<Head>}`
+      >}`
+    : `[${Carry}]`
+  : never;
diff --git a/src/lang/util/utils.ts b/src/lang/util/utils.ts
new file mode 100644
index 0000000..ac36ca1
--- /dev/null
+++ b/src/lang/util/utils.ts
@@ -0,0 +1,8 @@
+export type UnarrayIfOnlyHead<T extends readonly any[]> = T extends [
+  infer Head,
+  infer Next
+]
+  ? T
+  : T extends [infer Head]
+  ? Head
+  : T;