Responsibility is only possible by granting ownership and setting expectations. If you don't turn over ownership, don't expect folks to take responsibility. When you grant ownership and set expectations, you'll be astounded what folks will accomplish without you.

I am astounded.

In addition to providing a static type system and compiler for a superset of JavaScript, TypeScript makes much of its functionality available programmatically. In this post we'll use the TypeScript compiler API to build an interpreter. We'll build off of a TypeScript wiki article and cover a few areas that were confusing to me as I built out a separate project.

The end result we're building will look like this:

$ cat test.ts # A program we can interpret
print(1 + 5);
$ tsc interpreter.ts # Build the source code for the interpreter
$ node interpreter.js test.ts # Run the interpreter against test program
6

All code is available on Github.

Setup

To begin with, we need Node.js and some dependencies:

$ yarn add typescript @types/node

Then we can begin the first stage of an interpreter: parsing the code.

Parsing

Parsing a fixed set of files is simple enough. We pass a list of files to createProgram along with compiler options. But, as a user, we don't want to keep track of all files used by a program (i.e. everything we import). The most ideal situation is to pass a single-file entrypoint (something like a main.js) and have our interpreter figure out all the imports and handle them recursively. More on this later, for now we'll just parse the single-file entrypoint.

import * as ts from 'typescript';

const TS_COMPILER_OPTIONS = {
  allowNonTsExtensions: true,
};

function parse(fileName: string): ts.Program {
  return ts.createProgram([fileName], TS_COMPILER_OPTIONS);
}

function interpret(program: ts.Program) { // TODO }

function main(entrypoint: string) {
  const program = parse(entrypoint);
  interpret(program);
}

main(process.argv[2]);

interpret and ts.Program

A program contains all source files as well as any implicitly needed TypeScript definition files (for us it will just be the TypeScript definitions for the Node.js standard library).

The program also gives us access to a type checker that we can use to query the type of any node in the program tree. We'll get into this in another post.

Our interpret program will iterate over all the source files, ignoring the TypeScript definition files, and call interpretNode on all the elements of the source file.

function interpretNode(node: ts.Node) { // TODO }

function interpret(program: ts.Program) {
  return program.getSourceFiles().map((source) => {
    const { fileName } = source;
    if (fileName.endsWith('.d.ts')) {
      return;
    }

    const results = [];
    ts.forEachChild(source, (node) => {
      results.push(interpretNode(node));
    });
    return results;
  });
}

interpretNode and ts.Node

A Node is a wrapper for most elements of what we consider a program to be, such as a binary expression (2 + 3), a literal expression (2), a function call expression (a(c)), and so forth. When exploring a parser, it takes time to become familiar with the particular way that a parser breaks out a program into a tree of nodes.

As a concrete example, the following program:

print(a);

Will be built into ts.Node tree along these lines:

Node: ExpressionStatement: print(a);
  Node: CallExpression: print, a
    Node: Identifier: print
    Node: Identifier: a
Node: EndOfFileToken

And another example:

1 + 3;

Will be built into a ts.Node tree along these lines:

Node: Expression: 1 + 3
  Node: BinaryExpression: 1, 3, +
    Node: NumericLiteral: 1
    Node: NumericLiteral: 3
    Node: PlusToken
Node: EndOfFileToken

But how would one come to know this?

Exploring the ts.Node tree

The easiest thing to do is throw an error on every Node type we don't yet know about and fill in support for each program we throw at the interpreter.

For example:

function interpretNode(node: ts.Node) {
  switch (node.kind) {
    default:
      throw new Error('Unsupported node type: ' + ts.SyntaxKind[node.kind]);
  }
}

Now let's run our interpreter against an input file, test.ts, that combines these two to make a semi-interesting program:

$ cat test.ts
print(1 + 2);
$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: ExpressionStatement
...

And we see an outer wrapper, an ExpressionStatement. To proceed we look up the definition of an ExpressionStatement in TypeScript source code, src/compiler/types.ts to be specific. This file will become our best friend. Hit ctrl-f and look for "interface ExpressionStatement ". We see that it has only one child, expression, so we call interpretNode on this recursively:

function interpretNode(node: ts.Node) {
  switch (node.kind) {
    case ts.SyntaxKind.ExpressionStatement: {
      const es = node as ts.ExpressionStatement;
      return interpretNode(es.expression);
    }
    default:
      throw new Error('Unsupported node type: ' + ts.SyntaxKind[node.kind]);
  }
}

Thankfully TypeScript will be very quick to call us out if we misunderstand this structure.

It's pretty weird to me that the ts.Node tree is organized such that I must cast at each ts.Node but that's what they do even in the TypeScript source so I don't think I'm misunderstanding.

Now we recompile and run the interpreter against the program to discover the next ts.Node type.

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: CallExpression
...

Cool! Back to src/compiler/types.ts. Call expressions are complex enough that we'll break out handling them into a separate function.

interpretCall and ts.CallExpression

From our reading of types.ts we need to handle the expression that evaluates to a function, and we need to handle its parameters. We'll just call interpretNode on each of these to get their real value. And finally we'll call the function with the arguments.

function interpretCall(ce: ts.CallExpression) {
  const fn = interpretNode(ce.expression);
  const args = ce.arguments.map(interpretNode);
  return fn(...args);
}

function interpretNode() {
  switch (node.kind) {
    ...
    case ts.SyntaxKind.CallExpression: {
      const ce = node as ts.CallExpression;
      return interpretCall(ce);
    }
    ...
  }
}

Please ignore the fact that we are not correctly setting this here.

Recompile and let's see what's next!

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: Identifier
...

And back to types.ts.

ts.Identifier

In order to support identifiers in general we'd need to have a context we could use to look up the value of an identifier. But we don't have a context like this right now so we'll add builtin support for a print function so we can get some output!

function interpretNode() {
  switch (node.kind) {
    ...
    case ts.SyntaxKind.Identifier: {
      const id = (node as ts.Identifier).escapedText as string;
      if (id === 'print') {
        return function (...args) { console.log(...args); };
      }

      throw new Error('Unsupported identifier: ' + id);
    }
    ...
  }
}

Recompile and let's see what's next!

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: BinaryExpression
...

And we're finally into the parameters.

interpretBinaryExpression and ts.BinaryExpression

Looking into types.ts for this Node type suggests we may want to break this out into its own function as well; there are a ton of operator types. Within the interpretBinaryExpression helper we'll interpret each operand and then switch on the operator type. We'll throw an error on operators we don't know about -- all of them at first:

function interpretBinaryExpression(be: ts.BinaryExpression) {
  const left = interpretNode(be.left);
  const right = interpretNode(be.right);
  switch (be.operatorToken.kind) {
    default:
      throw new Error('Unsupported operator: ' + ts.SyntaxKind[be.operatorToken.kind]);
  }
}

function interpretNode() {
  switch (node.kind) {
    ...
    case ts.SyntaxKind.BinaryExpression: {
      const be = node as ts.BinaryExpression;
      return interpretBinaryExpression(be);
    }
    ...
  }
}

We know the drill.

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: FirstLiteralToken
...

At this point we're actually failing first on an unknown node type rather than an operator. This is because we interpret the operands (which are numeric literals) before we look up the operator. Time to revisit types.ts!

ts.FirstLiteralToken, ts.NumericLiteral

Looking at types.ts shows us that FirstLiteralToken is a synonym for NumericLiteral. The latter name is more obvious, so let's add that to our supported Node list:

function interpretNode() {
  switch (node.kind) {
    ...
      case ts.SyntaxKind.NumericLiteral: {
      const nl = node as ts.NumericLiteral;
      return Number(nl.text);
    }
    ...
  }
}

And we keep going!

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported operator: PlusToken
...

And we're into unknown operator territory!

interpretBinaryExpression and ts.PlusToken

A simple extension to our existing interpretBinaryExpression, we return the sum of the left and right values:

function interpretBinaryExpression(be: ts.BinaryExpression) {
  const left = interpretNode(be.left);
  const right = interpretNode(be.right);
  switch (be.operatorToken.kind) {
    case ts.SyntaxKind.PlusToken:
      return left + right;
    default:
      throw new Error('Unsupported operator: ' + ts.SyntaxKind[be.operatorToken.kind]);
  }
}

And we give it another shot.

$ tsc interpreter.ts
$ node interpreter.js test.ts
...
Error: Unsupported node type: EndOfFileToken
...

ts.SyntaxKind.EndOfFileToken

Our final Node type before a working program, we simply do nothing:

function interpretNode() {
  switch (node.kind) {
    ...
    case ts.SyntaxKind.EndOfFileToken:
      break;
    ...
  }
}

One more time:

$ tsc interpreter.ts
$ node interpreter.js test.ts
3

A working program! And if we jiggle the test?

$ cat test.ts
print(1 + 5);
$ node interpreter.js test.ts
6

We're well on our way to interpreting TypeScript, and have gained some familiarity with the TypeScript Compiler API.

All code is available on Github.

Quick intro to the TypeScript Compiler API by writing an interpreter https://t.co/QKz3XtOuP9

— Phil Eaton (@phil_eaton) April 14, 2019

Say we have some HTML:

<html>
  <body>
    <h1>Hello world!</h1>
  </body>
</html>

And say we'd like to be able to render this page in a web browser. If the server is hosted locally we may want to enter localhost:9000/hello-world.html in the address bar, hit enter, make a request (done by the browser), receive a response (sent by some server), and render the result (done by the browser).

Here is a minimal, often incomplete, and unsafe Node.js program (about 100 LoC) that would serve this (code available on Github):

const fs = require('fs');
const net = require('net');

const CRLF = '\r\n';

const HELLO_WORLD = `<html>
  <body>
    <h1>Hello world!</h1>
  </body>
</html>`;
const NOT_FOUND = `<html>
  <body>
    <h1>Not found</h1>
  </body>
</html>`;

class HTTPRequestHandler {
  constructor(connection) {
    this.connection = connection;
    this.request = {
      statusLine: null,
      headers: {},
      body: null,
    };
  }

  parse(buffer) {
    const lines = buffer.toString().split(CRLF);

    // Parse/store status line if necessary
    if (!this.request.statusLine) {
      const [method, path, protocol] = lines.shift().split(' ');
      this.request.statusLine = { method, path, protocol };
    }

    // Parse/store headers if the body hasn't begun
    if (!this.request.body) {
      for (let line = lines.shift(); lines.length; line = lines.shift()) {
        // Reached the end of headers, double CRLF
        if (line === '') {
          this.request.body = '';
          break;
        }

        const [key, value] = line.split(':');

        const safeKey = key.toLowerCase();
        if (!this.request.headers[safeKey]) {
          this.request.headers[safeKey] = [];
        }

        this.request.headers[safeKey].push(value.trimStart());
      }
    }

    this.request.body += lines.join(CRLF);
  }

  requestComplete() {
    if (!this.request.statusLine || !Object.keys(this.request.headers).length || this.request.body === null) {
      return false;
    }

    const [contentLength] = this.request.headers['content-length'] || [];
    if (this.request.statusLine.method !== 'GET' && this.request.body.length !== contentLength) {
      return false;
    }

    return true;
  }

  sendResponse() {
    const response = { status: 200, statusMessage: 'OK', body: '' };

    if (this.request.statusLine.path === '/hello-world.html') {
      response.body = HELLO_WORLD;
    } else {
      response.status = 404;
      response.statusMessage = 'NOT FOUND';
      response.body = NOT_FOUND;
    }

    const serialized = 'HTTP/1.1 ${response.status} ${response.statusMessage}' + CRLF +
                       'Content-Length: ' + response.body.length + CRLF + CRLF +
                       response.body;
    this.connection.write(serialized);
  }

  handle(buffer) {
    this.parse(buffer);

    if (!this.requestComplete()) {
      return;
    }

    this.sendResponse();

    // Other-wise the connection may attempt to be re-used, we don't support this.
    this.connection.end();
  }
}

function handleConnection(connection) {
  const handler = new HTTPRequestHandler(connection);
  connection.on('data', (buffer) => handler.handle(buffer));
}

const server = net.createServer(handleConnection);

server.listen('9000');

So what's going on?

The protocol

HTTP (version 1.1, specifically) is a convention for connecting over TCP/IP and sending plain-text messages between two processes. HTTP messages are broken into two categories: requests (the sender of a request is called a "client") and responses (the sender of a response is called a "server").

HTTP is important because it is the default protocol of web browsers. When we type in localhost:9000/hello-world.html and hit enter, the browser will open an TCP/IP connection to the location localhost on the port 9000 and send an HTTP request. If/when it receives the HTTP response from the server it will try to render the response.

An HTTP request

A bare minimum HTTP/1.1 request (defined here) based on the request for localhost:9000/hello-world.html is the following:

GET /hello-world.html HTTP/1.1\r\nHost: localhost:9000\r\n\r\n

The spec explicitly requires the \r\n combo to represent a newline instead of simply \n.

If we printed out this request it would look like this:

GET /hello-world.html HTTP/1.1
Host: localhost:9000

Components of an HTTP request

An HTTP/1.1 request is made up of a few parts:

• [Mandatory]: The status line (the first line) followed by a CRLF (the \r\n combo)
• [Mandatory]: HTTP headers separated by a CRLF and followed by an additional CRLF
• [Optional]: The request body

The status line consists of the request method (e.g. GET, POST, PUT, etc.), the path for the request, and the protocol -- all separated by a space.

An HTTP header is a key-value pair separated by a colon. Spaces following the colon are ignored. The key is case insensitive. Only the Host header appears to be mandatory. Since these headers are sent by the client they are intended for the server's use.

The request body is text and is only relevant for requests of certain methods (e.g. POST but not GET).

An HTTP response

A bare minimum HTTP/1.1 response (defined here) based on the file we wanted to send back is the following:

HTTP/1.1 200 OK\r\n\r\n<html>\n  <body>\n    <h1>Hello world!</h1>\n  </body>\n</html>

If we printed out this response it would look like this:

HTTP/1.1 200 OK

<html>
  <body>
    <h1>Hello world!</h1>
  </body>
</html>

Components of an HTTP response

An HTTP/1.1 response is made up of a few parts:

• [Mandatory]: The status line (the first line) followed by a CRLF
• [Optional]: HTTP headers separated by a CRLF and followed by an additional CRLF
• [Optional]: The request body

The status line consists of the protocol, the status code, and the status message -- all separated by a space.

HTTP response headers are the same as HTTP request headers although in a response they are directives from the server to the client. There are many standard headers that are used for such things as setting cache rules, setting cookies, settings response type (e.g. HTML vs CSS vs PNG so the browser knows how to handle the response).

The response body is similar to the HTTP request body.

Sockets

Most operating systems have a built-in means of connecting over TCP/IP (and sending and receiving messages) called "sockets". Sockets allow us to treat TCP/IP connections like files in memory. Most programming languages have a built-in socket library. Node.js provides a high-level interface for listening on a port and handling new connections.

function handleConnection(connection) {
  connection.on('data', (buffer) => doSomething???);
}

const server = net.createServer(handleConnection);

server.listen('9000');

Once the program is listening, clients can open TCP/IP connections to the address (localhost) and port (9000) and our program takes over from there. Each connection is handled separately and receives "data" events. Each data event includes new bytes available for us to handle.

Let's encapsulate the state of each connection in HTTPRequestHandler class. Its function will be to parse data as it becomes available and respond to the request when the request is done.

class HTTPRequestHandler {
  constructor(connection) {
    this.connection = connection;
  }

  parse(buffer) {}

  requestComplete() {}

  sendResponse() {}

  handle(buffer) {
    this.parse(buffer);

    if (!this.requestComplete()) {
      return;
    }

    this.sendResponse();

    // Other-wise the connection may attempt to be re-used, we don't support this.
    this.connection.end();
  }
}

function handleConnection(connection) {
  const handler = new HTTPRequestHandler(connection);
  connection.on('data', (buffer) => handler.handle(buffer));
}

...

There are three functions we need to implement now: parse(buffer), requestComplete(), and sendResponse.

parse(buffer)

This function will be responsible for progressively pulling out data from the buffer. If the status line has not been received, it will try to grab the status line. If the body has not yet started, it will accumulate headers. Then it will continue accumulating the body until we close the connection (this will happen implicitly when requestComplete() returns true).

class HTTPRequestHandler {
  constructor(connection) {
    this.connection = connection;
    this.request = {
      statusLine: null,
      headers: {},
      body: null,
    };
  }

  parse(buffer) {
    const lines = buffer.toString().split(CRLF);

    // Parse/store status line if necessary
    if (!this.request.statusLine) {
      const [method, path, protocol] = lines.shift().split(' ');
      this.request.statusLine = { method, path, protocol };
    }

    // Parse/store headers if the body hasn't begun
    if (this.request.body === null) {
      for (let line = lines.shift(); lines.length; line = lines.shift()) {
        // Reached the end of headers, double CRLF
        if (line === '') {
          this.request.body = '';
          break;
        }

        const [key, value] = line.split(':');

        const safeKey = key.toLowerCase();
        if (!this.request.headers[safeKey]) {
          this.request.headers[safeKey] = [];
        }

        this.request.headers[safeKey].push(value.trimStart());
      }
    }

    this.request.body += lines.join(CRLF);
  }

...

}

requestComplete()

This function will look at the internal request state and return false if the status line has not been received, no headers have been received (although this is stricter than the HTTP/1.1 standard requires), or if the body length is not equal to the value of the Content-Length header.

class HTTPRequestHandler {

...

  requestComplete() {
    if (!this.request.statusLine || !Object.keys(this.request.headers).length || this.request.body === null) {
      return false;
    }

    const [contentLength] = this.request.headers['content-length'] || [];
    if (this.request.statusLine.method !== 'GET' && this.request.body.length !== contentLength) {
      return false;
    }

    return true;
  }

...

}

sendResponse()

Finally we'll hard-code two responses (one for the valid request for /hello-world.html and a catch-all 404 response for every other request). These responses need to be serialized according the HTTP response format described above and written to the connection.

class HTTPRequestHandler {

...

  sendResponse() {
    const response = { status: 200, statusMessage: 'OK', body: '' };

    if (this.request.statusLine.path === '/hello-world.html') {
      response.body = HELLO_WORLD;
    } else {
      response.status = 404;
      response.statusMessage = 'NOT FOUND';
      response.body = NOT_FOUND;
    }

    const serialized = 'HTTP/1.1 ${response.status} ${response.statusMessage}' + CRLF +
                       'Content-Length: ' + response.body.length + CRLF + CRLF +
                       response.body;
    this.connection.write(serialized);
  }  

...

}

Run it

Now that we've got all the pieces we can finally run the initial program:

$ node uweb.js &
$ open localhost:9000/hello-world.html

And we see the page! Try any other path and we receive a 404.

Review and next steps

We covered the basics of HTTP/1.1: a very simple, plain-text protocol oriented around requests and responses over a TCP/IP connection. We realize we need to know little about anything but parsing and formatting text on top of the TCP/IP blackbox called sockets. We created a simple application that returns different responses based on the request. But we're a far shot from a more general library, a web framework. Future posts will explore this transition as well as performance and more features.

Code is available on Github.

First post in a new series on web server basics starting with HTTP and sockets (using JavaScript/Node.js). https://t.co/uBiNfOBJeZ

— Phil Eaton (@phil_eaton) April 7, 2019