DEV Community: Craig Taub

Under-the-hood of GraphQL DataLoader

Craig Taub — Fri, 11 Mar 2022 15:20:46 +0000

In recent years GraphQL has really taken off as a pattern/library/type system. It offers much which REST does not and its standardization and flexibility has really helped in its adoption. I have an article focused on digging deeper into GraphQL here, so today we will focus on another tool in the GraphQL ecosystem - one that is very important and interesting in how it assists applications - that tool is the DataLoader.

This is part of my "under-the-hood of" series:

The article today will be broken down into 2 parts:

Overview
- Batching
- Caching
Building our own GraphQL DataLoader

1: Overview

The NodeJS repository for GraphQL's DataLoader is found at https://github.com/graphql/dataloader, however it can be found in many different language implementations. It can be used as part of your applications data fetching layer, and its basic job is to reduce requests to backends by 2 means.

Batching
Caching

It utilizes different logic and functionality to perform the above efficiently.

The first question is what does GraphQL have to do with this?

It pairs nicely with GraphQL as GraphQL has fields which are designed to be stand-alone functions (resolvers) and it is very easy to share a class instance via the context. The class instance would be our instance of DataLoader.

The natural pairing of DataLoader and GraphQL has produced high success rates - some examples have seen 13 database queries reduced down to 3 or 4.

Batching

Batching is the primary feature of DataLoader, you must pass the library a "batch function" to detail how to process the batch.
Within a single tick of the event loop DataLoader gathers all individual loads, then calls the "batch loading function" with all requested keys.

VS your ORM

Its important to note DataLoader does not optimize the queries itself - you can look to an ORM for help there. For example Objection-JS has logic to avoid "N+1 selects" by utilizing "where in" queries.

Batch function

This is the function given to the library when you create a new instance

const ourInstance = new DataLoader(keys => myBatchFunction(keys))

The basic idea is that you check your cache first for a given key, if it exists return that value, else hit the data-source e.g database.

It passes in an array of keys, but there is a constraint that:
1) the returned array size must match the keys coming in
2) the returned array indexes must match the keys coming in

There is a sound reason for that limitation and it's related to the implementation - it is covered in part 2 below.

Its worth highlighting that keys are suited to table column ID's, so it stands to reason that having a database table for each entity in your data model would fit this mechanism well.

Caching

DataLoader uses a simple in-memory memoization cache. You can swap the memory store for something else e.g. SQL-lite.

Caching pairs really well with the Batching, because the batch can ensure the requested data has already been pulled from the database, the cache can be utilized to retrieve from there. We will go over this more in the next section

2. Building our own GraphQL Dataloader

In this section we will focus on the and save for another time. Hopefully it will provide enough context on how caching is utilized.

Within a single tick of the event loop DataLoader gathers all individual loads, then calls the "batch loading function" with all requested keys.

You might be wondering how it does this - so let's look at the most simple example.

const run = async () => {
  const keys = [];
  const batchFunction = (keys) => {
    // bad point 1 - called with [1,2], [1,2]
    console.log("keys: ", keys);
  };

  const load = async (id) => {
    keys.push(id);
    process.nextTick(() => {
      batchFunction(keys);
    });
    // bad point 2 - promise not connected to batch function
    return Promise.resolve(`id: ${id}`);
  };

  const a = await load(1);
  const b = await load(2);
  console.log("a", a); // id: 1
  console.log("b", b); // id: 2
};

run();

This calls our batch function twice - both times with both keys.
The order of events is this:

call load asynchronously with id 1
call load asynchronously with id 2
async load(1)
- store key 1 in the global keys array
- schedule a node process to, on the next tick, run our batchFunction with those keys
- Return a resolved promise with the id.
async load(2)
- store key 2 in the global keys array
- schedule a node process to, on the next tick, run our batchFunction with those keys
- Return a resolved promise with the id.
The first scheduled process runs, with both ids 1 and 2 in the keys array
The second scheduled process runs, with both ids 1 and 2 in the keys array.

So here you can see the basic mechanism of how batching works.

Good 👍🏻

Runs our batch function with both keys - this will mean we can cache the database response, and next time those keys are included only utilize cache

Bad 👎🏻

Unnecessarily calling the batch function with the same keys, unnecessarily running the code even if it is hitting the cache.
load does not return anything useful, its a completely isolated resolved promise.

The below example looks to improve on that.


let resolvedPromise;
let batchFunction;
let batch;

const dispatchBatch = () => {
  batch.hasDispatched = true;
  const batchPromise = batchFunction(batch.keys);

  batchPromise.then((values) => {
    for (var i = 0; i < batch.callbacks.length; i++) {
      var value = values[i];
      // resolve promise callback
      batch.callbacks[i].resolve(value);
    }
  });
};

const batchScheduleFn = (cb) => {
  // add more logic if scheduling
  process.nextTick(cb);
};

const getCurrentBatch = () => {
  // !hasDispatched only needed if using a 2nd tick - this example isnt
  if (batch && !batch.hasDispatched) {
    return batch;
  }
  const newBatch = { hasDispatched: false, keys: [], callbacks: [] };
  batch = newBatch;
  batchScheduleFn(() => {
    dispatchBatch();
  });
  return newBatch;
};

const load = async (id) => {
  const localBatch = getCurrentBatch();
  localBatch.keys.push(id);
  // add promise callback to batch
  const promise = new Promise((resolve, reject) => {
    localBatch.callbacks.push({ resolve, reject });
  });

  return promise;
};

async function threadTwo() {
  const user = await load(2);
  console.log("threadTwo user", user.id);
}

async function threadOne() {
  const user = await load(1);
  console.log("threadOne user", user.id);
}

const run = async () => {
  // make async
  batchFunction = async (keys) => {
    console.log("keys:", keys);
    // keys: [ 1, 2 ]
    return keys.map((key) => ({ id: key }));
  };

  threadOne();
  threadTwo();
};

run();

It introduces batches which can be sheduled - this is exactly how DataLoader manages it (here).

The order of events is this:

call threadOne - call load async with id 1
call threadTwo - call load async with id 2
async load(1)
- get the current batch
  - batch is currently undefined so a newBatch is created
  - we schedule a dispatch by calling dispatchBatch() inside our scheduler batchScheduleFn()
    - this adds dispatchBatch callback to the nextTick.
  - lastly we return the batch
- we add the id to the keys array on the current batch
- we create a new promise, add the reject and resolve to our current batch callbacks (so the list index is important)
- lastly we return the new promose
async load(2)
- get current batch
  - batch currently exists and has not been dispatched so we return that
- as above we add the id and reject/resolve to the current batch
- as well as return the promise
process.nextTick
- the tick runs dispatchBatch
- call our batchFunction with the current batches keys
  - batchFunction returns a promise
- when that promise resolves (.then), it returns an array of our keys
- we iterate over our batch callbacks - for each callback
  - we find the associated batchFunction key value this is why the batch function response indexes are so important
  - resolve the callback with that value
await load(1) resolves
- returning object {id}
await load(2) resolves
- returning object {id}

This calls the batch function once with both keys, it returns correct values from batch function - dealing with both "bad" points from the first example.

Thanks so much for reading, I learnt a huge amount about DataLoader and GraphQL from this research and I hope it was useful for you. You can find the repository for all this code here.

Thanks, Craig 😃

Under-the-hood of Docker

Craig Taub — Sun, 30 Jan 2022 09:49:36 +0000

Docker is defined as

A set of platform as a service products that use OS-level virtualization to delivery software in packages called containers

In essence Docker allows us to turn applications into binaries which can be stored externally and then be pulled to run or deployed anywhere. It was initially released in 2013 (8 years ago from now) and is predominantly written in Go. The two main public registries of docker images are Docker Hub and Docker Cloud. The former being the default registry Docker checks.

This is part of my "under-the-hood of" series:

The article today will be broken down into:

Overview
Building our own Docker

1: Overview

There are several components to Docker, lets start with:

Client
Registry
Host
- Daemon
- Images
- Containers
- Storage/volumes
- Networking

Client

The client is the means to interact with a Docker Host via the Daemon (see below). The client usually consists of a CLI (to run the commands directly e.g. docker pull x) or a piece of software which runs these connads for you (e.g. Docker Desktop).

The client can actually connect to more than 1 Docker daemon at a time.

Registry

This is the external database which stores the images. See my "under the hood of NPM" for more details on a registry Database.

Host

This is the environment to execute and run containers on, its not the same as the local machine. To get access you have to go into a container and then hit localhost:<port>.

The host includes several objects such as:

Daemon

The Daemon is a background process whose job is to listen for Docker API requests and respond to them. It manages objects like - images, containers, networks and volumes.

The binary can be run under

dockerd

Example - build command

CLI tells Deamon
Damon opens Dockerfile runnning 1 instruction at a time - It commits the result of each instruction to a new image
Finally outputs ID of image - Uses the build cache. Print message in CLI with each step

Build cache

For each instruction Daemon checks cache to see if exists already
Pairs "parent image" + "instruction" (key) to find a hit
Compares the instruction against all child images derived from base/parent images

Images

There is alot to images so I have tried to cover the main points.

Images are read-only templates, they are immutable snapshots.

Images come with a manifest.json file, which holds details of the image tags and signatures.
The image directory contains the image layer and manifest, only 1 layer per image. The base has no parent, the children have the ID of the parent. The bottom-most image is called the base image. The unique ID is a sha256 hash

Image layers

Layers are intermediate images, an image has 1 layer, each layer is an instruction. The instruction is stored inside the images JSON config, along with the folder details (i.e. lower, merged, upper, work). This system promotes smaller images as each is stacked on top of the previous.

Each layer is stored in its own directory, inside the Docker host local storage area. The directory contains (unique) image contents, but the directory name IS NOT the layer ID.

> ls /var/lib/docker/overlay2 # list image layers
> 16802227a96c24dcbeab5b37821e2
> ls 16802227a96c24dcbeab5b37821e2 # image layer contents
> diff link lower merged work

Directories

link - shortened layer id
diff - the layers contents from the root (the folders and files)
lower - Points to parent/previous layer (higher layers have this).
merged - Unified contents of higher layer and itself (higher layers have this)
work - used internally by OverlayFS storage driver

You can use the below commands to verify the cryptographic IDs

> docker image ls
> docker history

Use the below to view the layer ID and hte instruction which created it (note Size can be 0 if just adding to metadata)

> docker image history <image>

Containers

Containers are the virtualized runtime environment, they run the image.

Container layer

Each new container adds a new writeable layer on top of the underlying layers. All changes made to the running container (e.g. alter file) are written to this thin writeable layer.
When the container is deleted so is this writeable layer, the underlying image is untouched.
Multiple containers can share the same image but have their own data state.

If a volume is used the volume becomes this writeable layer.

Storage/volumes

I personally find this the trickiest one to understand from the Docker subject.

Storage driver

This controls how the "image layer (stack)" and "container (r/w) layer" are managed (the contents), unrelated to volumes.

Generally files are not persisted after a container is deleted, but the driver gives the ability to write data to the "containers (writeable) layer". The driver handles details of how the image layers interact with each other. They have different advantages and disadvantages based on the situation.

All drivers use the same stackable image layers and most use the CoW (copy-on-write) strategy (see below).

The overlay2 docker storage driver uses the OverlayFS Linux kernel driver (see below).

The storage driver uses the backing filesystem driver (in the kernel) to alter files (the filesystem of the host on which Docker is installed). Some storage drivers only work with specific backing file-systems e.g. extfs.

Copy-on-Write strategy

It is a very efficient storage technique. Essentially if the image is duplicated but not modified, don't create a new image. So you can share images until one is changed, but modifications create a new image.

OverlayFS

OverlayFS layers 2 directories on a single Linux host and presents them as a single directory. Is is a very modern union filesystem (i.e. container vs image layer) and it has efficient inode utilization.

Volumes

Volumes are used to persist data created in containers, for write-heavy applications. They are preferable to bind mounts, as volumes are managed by docker whereas bind mounts are via the OS.

To use a volume point local contents to the area used by the container and using the below format.

volume:directory

Volumes are bind-mounted into existing (or created) paths within the filesystem image, outside the image layer. They are preserved in their source location and become the "container layer". They can share data by sharing a single volume across multiple containers.

They are created initially and then re-used, managed via the Docker API. You can create and manage them outside the scope of a container. You can name the volume so it has a source from outside the container, or have it anonymous so when the container is removed the Daemon will remove it.

They live on the host filesystem (usually found under the docker data directory e.g. /var/lib/docker/volumes but depends on FS).

Some useful commands:

> docker volume create my-vol
> docker volume inspect my-vol
> docker volume rm my-vol
>  -v ./packages/website:/usr/src/app

Networking

The docker Deamon acts as a DHCP service for containers i.e. assigning IPS etc. The container uses DNS settings of the host (defined in /etc/resolv.conf).

The default network settings specify the container is part of the docker network stack and creates a bridge (a gateway and IP subnet). All containers that belong to this network can talk to each other via IP addressing.

My favourite Docker architecture image is this one - it shows an overview of the components but also the flow of operations (see the build, pull, run).

2: Building our own Docker

For this proof-of-concept we will be including the below aspects:

Host
- Daemon
- Existing images
CLI
- build
- run
Running the app

My plan was to use a copy-on-write mechanism and custom JS storage driver, but I ran out of time and decided it was more important to focus on the image creation and running aspect.

So our app is going to:

Read a local Dockerfile committing instructions into a new image layer, based off a parent layer, creating a new image.
Run the new image - use a tmp directory as a writeable container layer over the specified image. Then start our container in a virtualized runtime environment and execute a command.

Ignored aspects:

Daemon acting as DHCP for containers assigning ips
Host to run Daemon (will be on local machine)
Deleting container layer when stopped
Container layer using stackable "copy-on-write" strategy
Allow mounting volume
Container not using DNS settings of the host (no host)

A final thing which was omitted is that in real Docker each instruction creates a new image layer, in our PoC we have run all the instructions into a single image layer, hopefully this does simplify things.

THE CODE !!

Daemon

The Deamon is a simple express server executing commands in a child process.

import express from "express";
import path from "path";
import { promisify } from "util";
import run from "./commands/run.js";
import build from "./commands/build.js";

const app = express();
const port = 3000;

app.get("/:command/:args", async (req, res) => {
  console.log("Command: ", req.params.command);
  console.log("Args: ", req.params.args);

  switch (req.params.command) {
    case "run":
      await run(req.params.args);
      break;
    case "build":
      await build(req.params.args);
      break;
  }
  res.send("success");
});

app.listen(port, () => {
  console.log(`Example app listening at http://localhost:${port}`);
});

Existing images

Before we look at the commands, I have created a couple of fake image layers inside images.

To summarize what is found in the above link:

images/lowest-layer contains:

/diff
- contains folders /etc, /home, /lib, /mount, /opt, /user, /var
link
- contents LOWEST-ID
config.json
- JSON object with empty values
manifest.json

images/middle-layer contains:

/diff
- contains folders /media + /usr/src/app
- Note that /usr/src/app now has a small JS application with index.prod.js and index.dev.js
/merged
- contains folders /etc, /home, /lib, /mount, /opt, /user, /var, /media
- /media is new
link
- contents MIDDLE-ID
lower
- contents l/LOWEST-ID
config.json
- JSON object with values for Env, Cmd and WorkingDir
- Cmd runs index.dev.js
manifest.json

CLI

const daemon = 'http://localhost:3000';
const supported = ['build', 'run'];

async function run() {
  const command = process.argv[2];
  const details = process.argv[3];
  if (!supported.includes(command)) {
    console.log("Not supported");
    return;
  }
  const response = await fetch(`${daemon}/${command}/${details}`);
  if (response.status) {
    console.log("SUCCESS");
    return;
  }
  console.log("Failure :(");
}

run();

It is very simple. It takes an argument and some details and HTTP GET's the Daemon with those details. The HTTP GET mechanism is a simplification of the real CLI->Daemon communication, but it works easily for a PoC.

Our cli package script will just run node cli.js.

Example commands are:

  > npm run cli <command> <argument>

Commands

Build

We start with some utils, they return paths or update config values.

const utils = {
  getFullPath: () => path.resolve(path.dirname("")),
  grabConfig: async () => {
    await delay(1000);
    const fullPath = utils.getFullPath();
    const fullConfig = await import(`${fullPath}/tmp/config.json`);
    return fullConfig.default[0];
  },
  updateConfig: async (config) => {
    const fullPath = utils.getFullPath();
    return asyncWriteFile(
      `${fullPath}/tmp/config.json`,
      JSON.stringify([config])
    );
  },
};

The main build fuction.

export default async function (buildImage) {
  // 1
  if (buildImage === ".") {
    // Default local image
    // 2
    const dockerFilePath = path.resolve(path.dirname(""), "./OurDockerfile");
    const file = await asyncReadFile(dockerFilePath, {
      encoding: "utf-8",
    });
    // 3
    // good for small files, NOT big ones
    const linesArray = file.split(/\r?\n/);
    await linesArray.map(async (line) => await commitLine(line));
    // required for above OS ops to finish
    await delay(1000);
    // create new image
    const layerName = "highest-layer";

    const fullPath = utils.getFullPath();
    // 4
    // update link (HIGHEST-LAYER) + lower (MIDDLE-ID)
    const link = await asyncReadFile(`${fullPath}/tmp/link`, {
      encoding: "utf-8",
    });
    await asyncWriteFile(`${fullPath}/tmp/link`, layerName.toUpperCase());
    await asyncWriteFile(`${fullPath}/tmp/lower`, link);

    console.log(`SUCCESS - Created layer: ${layerName}`);
    await delay(1000);
    // 5
    // move tmp to new image
    await asyncNcp(`${fullPath}/tmp`, `images/${layerName}`);
    // remove tmp
    await asyncRimraf(`${fullPath}/tmp/`, {});
  }
}

It works like this:

Checks for build image, currently only supports local file i.e. .
Grab the OurDockerfile contents.
Split the file by its lines and run commitLine to process each line
Update the link and lower of the new image, the references to itself and parent image.
Move the new image layer from /tmp into /images and remove /tmp

The commit maps job is to action the comamnds inside the Dockerfile. In real Docker it would create a new layer for each instruction. There is also a commitLine which runs against the map. It currently supports some of the most popular commands in Docker:

from
env
workdir
copy
cmd

const commitMap = {
  from: async (layer) => {
    // move to tmp for processing
    const fullPath = utils.getFullPath();
    await asyncNcp(`${fullPath}/images/${layer}`, `tmp`);
    // remove diff as specific to layer
    await asyncRimraf(`${fullPath}/tmp/diff`, {});
  },
  env: async (values) => {
    const config = await utils.grabConfig();
    if (config.Config.Env) {
      config.Config.Env.push(...values); // merge incoming array into config one
    } else {
      config.Config.Env = values;
    }
    await utils.updateConfig(config);
  },
  workdir: async ([value]) => {
    const config = await utils.grabConfig();
    config.Config.WorkingDir = value; // a string
    await utils.updateConfig(config);
  },
  copy: async (values) => {
    const fullPath = utils.getFullPath();
    const cpyLoc = values.pop();
    // required for diff deletion to finish
    await delay(1000);
    values.map(async (file) => {
      // create folder recursively
      await asyncMkdir(`${fullPath}/tmp/diff${cpyLoc}/`, { recursive: true });
      // copy files
      await asyncCopyFile(file, `${fullPath}/tmp/diff${cpyLoc}/${file}`);
    });
  },
  cmd: async (values) => {
    const config = await utils.grabConfig();
    config.Config.Cmd = values;
    await utils.updateConfig(config);
  },
};

async function commitLine(line) {
  const args = line.split(" ");
  // 1
  const command = args[0];
  if (!command) return; // empty line or something
  args.shift();
  // 2
  // call command function
  if (!commitMap[command.toLowerCase()]) return; // invalid instruction
  await commitMap[command.toLowerCase()](args);
}

The break down the flow once commitLine(line) is called

Grab the command
Make sure it exists in the commitMap then execute it with arguments

If we take the following OurDockerfile

FROM middle-layer
ENV NODE_VERSION=13.0.0
WORKDIR /usr/src/app
COPY fileA.txt fileB.txt /usr/src/app
CMD npm run start.prod

Note that fileA.txt and fileB.txt both exist at the top level of the test repository and have simple content inside.

We can step through how each instruction gets processed:

FROM

gets the full path
moves the image (e.g. middle-layer) located in images into tmp
removes the tmp/diff folder as it is specific to the layer

I have 2 example images already build under images

middle-layer
lowest-layer

ENV

Grab the config
if there are values set under Env add to them, else create the section and add this value
Update the config

WORKDIR

Grab the config
Set the WorkingDir to be the new value
update the config

COPY

Grab the copy location
Map over each file to copy and move to /tmp/diff/<copy location>

CMD

Grab the config
Set the Cmd to be the new value, i.e. run index.prod.js
update the config

Notice the similarities between ENV, WORKDIR and CMD. They are mostly updating the image layers config.json file, so when it is run it has the correct values.

In real Docker each of the instructions would be committed into a new image layer and at the end the image would be created, however we have merged those 2 concepts for simplicity sake so that all the instructions create a single image layer.

Run

Now we will look at what it takes to build a new image.

export default async function (image) {
  // 1. copy image contents, exclude configs
  const fullImgPath = path.resolve(path.dirname(""), "./images");
  await asyncNcp(`${fullImgPath}/${image}/merged`, `tmp`);
  console.log("copied");

  // 2. process config
  const fullConfig = await import(`../../images/${image}/config.json`);
  const config = fullConfig.default[0].Config;
  const splitCommand = config.Cmd;
  // env is key:value pairs
  const environment = config.Env.reduce((acc, curr) => {
    const [key, value] = curr.split("=");
    acc[key] = value;
    return acc;
  }, {});
  const workingDir = config.WorkingDir;

  // 3. run command in child
  const startCmd = splitCommand[0];
  splitCommand.shift();
  const childProcess = spawn(startCmd, splitCommand, {
    cwd: `tmp/${workingDir}`,
    env: environment,
  });
  // 4. outputs
  childProcess.stdout.on("data", (data) => {
    console.log(`stdout: ${data}`);
  });
  childProcess.stderr.on("data", (data) => {
    console.error(`stderr: ${data}`);
  });
  childProcess.on("error", (error) => {
    console.log(`child process error ${error}`);
  });
  childProcess.on("close", (code) => {
    console.log(`child process exited with code ${code}`);
  });
  // remove ref might close open conn, but not sure it will considering above
  childProcess.unref();
}

Lets review

We move the images merged contents into tmp for processing
We process the config.json grabbing the values we need such as Cmd, WorkingDir and Env for the environment variables.
Spawn a child process and run the command using the working directory given and the environment variables
Create listeners on events such as stdout and error. Logging the output.

Running the app

To test we will perform the following

Run middle-layer -> runs tiny js app which prints run DEV app
Build a new highest-layer images -> creates images/highest-layer
Run highest-layer -> the same tiny js app except runs run PROD app

Lets go 💪

In terminal A we run below starting the Daemon

> npm run daemon

In terminal B we run our other commands.

Run middle-layer image

> npm run cli run middle-layer

Built with command npm run start.dev
Outputs run DEV app. Check

Build highest-layer image

> npm run cli build .

Run highest-layer image

> npm run cli run highest-layer

Built with command npm run start.prod
Outputs run PROD app

So thats it 🙌, our mini Docker works.

Thanks so much for reading, I learnt a huge amount about Docker from this research and I hope it was useful for you. You can find the repository for all this code here.

Thanks, Craig 😃

Under-the-hood of NPM

Craig Taub — Tue, 01 Jun 2021 11:53:53 +0000

NPM is the official package manager for the NodeJS ecosystem. Since the first release of NodeJS it has come with NPM built-in. The initial release date for NPM was 12 January 2010 and since then has grown into the Worlds largest software registry.

I would expect most engineers in the JavaScript ecosystem to know all about either NPM or Yarn, as they are critical to most local, CI and CD flows. However in the overview section I am going to cover the core functionality, as this is what we will focus on building later.

This is part of my "under-the-hood of" series:

The article today will be broken down into:

Overview
Module vs Package
Building our own NodeJS package manager

1: Overview

There are 3 parts to NPM

CLI tool

The CLI is open-source code available on Github. It is currently on version 7 and has had over 700 contributors. The CLI commands are NodeJS scripts and require the format npm <command>.

You can point the CLI to any registry e.g. npm adduser --registry http://localhost:4873

The most popular commands are:

`npm init`

Setup a new package
Creates a package.json (among other things)

`npm install`

Code located in install.js.
Uses npm-registry-fetch https://github.com/npm/npm-registry-fetch
Generates node_modules
Downloads dependencies defined in package.json (see "Module resolution" below)
Generates lockfile (see "Lockfile" below)
Utilises a cache (see "Cache" below)

Example output below:

Lockfile

Generates package-lock.json - describes dependency tree that was installed. For deterministic installs (subsequent installs). If it exists, the install is driven by that. The lockfile stores an 'integrity' hash for each dep. Ths hash (checksum) is of the package tarball uploaded to registry. Can be SHA-1 (older NPM) or SHA-512 (newer NPM). Its akin to a Subresource Integrity used in HTML/browsers.

Module resolution

NPM installs per package and sequentially i.e. moves on once package installed. This means it can be quite slow to finish.
Currently installs all of the nested dependencies as efficiently (or flat) as possible. If a version is the first for a dependency it is top-level, if it is not the first version then it is stored with the parent who requires it.
The old package resolution (pre npm v5) was done on disk by NodeJS (node_modules), this was much slower and is not used anymore.
Example resolution below

Cache

Stores http request/response data and other package-related data
Uses pacote. Library responsible for package fetching
All data passed through the cache is verified for integrity on insertion and extraction
Cache corruption will trigger a refetch, so clearing cache should only be necessary for reclaiming disk space

`npm version`

Bump local version, update package.json and package-lock.json
Create version commit and tag for git

`npm pack`

Create tarball (a zip) of the package (package.tar.gz)
Example screenshot below:

`npm publish`

Code located in publish.js
Runs npm pack as part of it
Sends tarball to registry
Publishing a package consists of at least 1 step (http PUT) with a metadata payload and tarball
See in the logs printed "npm http fetch PUT 200"

Registry

Large public database of JavaScript packages and the meta-information surrounding it. Versioned like git.

Uses Apache's NoSQL database Couch DB to manage publicly available data (it offers good storage performance and replication). It has database for "users" and one for "registry", the latter holds the packages.

Tarballs

It uses Couch DB's attachments for package tarballs. It is incredlby easy to upload or download an attachment from Couch, simpler than most other NoSQL.

API

Couch naturally exposes HTTP endpoints which means it has an API built into it by default. For auth there is a /_session endpoint (to create a new cookie-based session) or it accepts an Authentication header for basic auth, both natively. Using design document Rewrites (see below section) you can build redirects to different parts of the database

Querying

Couch DB is very dynamic in that it allows you to create a kind of schema called a "design document" for a given section. This can include javascript functions (yes it can store and run JS code internally) which execute at given events e.g. Updates is list of functions which run when a document is updated. It also allows Views which are function that take document data and produce searchable lists of information based on the document's contents. There are other types of dynamic mechanisms, more details here.

NPM links

The Couch DB tables and API for registry details are here (a repository for Registry documentation). Couch DB views used by the Registry are found in npm-registry-couchapp. An example Docker image for their DB setup is npm-docker-couchdb. It details how to update a local NPM client to use a local CouchDB registry (here), example below.

npm config set registry=http://localhost:5984/registry/_design/app/_rewrite

Some apps use the popular lightweight private proxy app verdaccio, for many reasons one of which is independent caching incase NPM is down.

Website

Found at https://www.npmjs.com/, a domain first registered on 19th March 2010.
It is built using Webpack, React and Lodash. Its assets are served via CDN CloudFlare. Any payments are processed via Stripe.

Connects and reads data from the registry Couch DB instance.

Packages are located at https://www.npmjs.com/package/<package name>.

The README markdown file is loaded as the landing page content with markdown rendered as HTML.

NPM also shows a load of other information such as the weekly download number, latest version, unpacked size and github location.

2. Module vs Package

A module is a file or directory that can be loaded by Nodejs, located inside node_modules.

CLI packages are not modules, they cannot be loaded by NodeJS until unzipped into a folder first.

2 versions of the same module can exist (module@1.0.0 and module@1.0.1) and they will not conflict. Generally npm packages are modules, loaded via require() or import

3: Building our own NodeJS package manager

We will be building an app which includes all 3 aspects of NPM.

Registry
CLI
Website

The aim is to get a basic PoC which will work for all 3.

Using an example-lib (a small package which returns some text) and example-app (a small express server using the previous package) we can test it works.

Wrapping all of the above in a single mono-repository with multiple packages.

Registry

For this we will use the default couchdb Docker image. It includes a basic unauthenticated CouchDB instance.

We will use docker-compose to set up our apps.

Our docker-compose.yml starts like this:

version: "3.0"

services:
  couchdb_container:
    image: couchdb:1.6.1
    ports:
      - 5984:5984

It does not need a volume mounted or anything else at this point.

We will use a Makefile to assist in running. We start by building and creating the registry database. Later I added a stop and reset so we could kill the docker application and reset the database quickly.

Makefile below:

up:
    docker-compose up --build

db:
    curl -XPUT http://localhost:5984/registry

stop:
    docker-compose stop

reset:
    curl -X DELETE \
        'http://localhost:5984/registry' \
        -H 'content-type: application/json'

Opening the browser confirms the database and couchDb instance exists

CLI

Located in our monorepo in packages/cli/. We will only be creating 2 commands for this PoC.

Install
Publish

The package.json will look like below

{
  "bin": {
    "our-npm-install": "./scripts/install.js",
    "our-npm-publish": "./scripts/publish.js"
  }
}

Using bin means inside the packages/cli folder we can run below:

npm install -g .

And from any directory in a terminal we can run the commands like this.

our-npm-publish

our-npm-install

I could have chosen to split these into a single script and use arguments, like the real NPM, but it did not seem worth it for this PoC. If I had gone that route I would have used yargs.

Install script

Located at packages/cli/scripts/install.js

It has 4 steps:

Grab the package name and ourDeps object, from the current working directory package.json
Iterate over each item in ourDeps, the version is ignored for our PoC.
1. make a fetch request to the couch-db tarball attachment (looks like http://localhost:5984/registry/{repo-name}/{repo-name}.tar.gz)
2. write the file to a local tmp.tar.gz file (for processing)
Extract the tmp.tar.gz contents using the tar library, into the current working directory node_modules/{repo-name}.
Finally delete the tmp.tar.gz file

The code is here.

#!/usr/bin/env node

const fetch = require("node-fetch")
const { writeFile } = require("fs")
const { promisify } = require("util")
const tar = require("tar")
const fs = require("fs")

const writeFilePromise = promisify(writeFile)
const apiUrl = "http://localhost:5984/registry"
const outputPath = `${process.cwd()}/tmp.tar.gz`

async function extractPackage(repoName) {
  const zipExtractFolder = `${process.cwd()}/node_modules/${repoName}`

  if (!fs.existsSync(zipExtractFolder)) {
    // create package in node_mods
    fs.mkdirSync(zipExtractFolder)
  }
  try {
    // Step 3
    await tar.extract({
      gzip: true,
      file: "tmp.tar.gz",
      cwd: zipExtractFolder, // current extract
    })
    console.log("Extract complete")
  } catch (e) {
    console.log("Extract error: ", e.message)
  }
}
async function downloadPackage(repoName) {
  // Step 2.1
  return (
    fetch(`${apiUrl}/${repoName}/${repoName}.tar.gz`)
      .then(x => x.arrayBuffer())
      // Step 2.2
      .then(x => writeFilePromise(outputPath, Buffer.from(x)))
      .catch(e => console.log("Download Error: ", e.message))
  )
}

async function run() {
  // Step 1
  const package = require(`${process.cwd()}/package.json`)
  // Step 2 - process each dep
  Object.keys(package.ourDeps).map(async repoName => {
    await downloadPackage(repoName)

    await extractPackage(repoName)

    // Step 4 - remove tar
    fs.unlinkSync(outputPath)
    console.log(`Downloaded: ${repoName}`)
  })
}

run()

Publish script

Located at packages/cli/scripts/publish.js

It has 4 steps:

From the current working directory grab
1. package.json file name field
2. The README.md contents
Create a tarball of the current working directory
Send the package tarball (as an attachment) and README contents (as plain text) to our couchdb instance, the document name is the package name.
Delete the local tarball file

#!/usr/bin/env node

const { unlinkSync, readFile } = require("fs")
const tar = require("tar")
const { promisify } = require("util")
const nano = require("nano")("http://localhost:5984")

const readFileAsync = promisify(readFile)

async function sendPackage(repoName, readmeContents) {
  const tarballName = `${repoName}.tar.gz`
  const filePath = `${process.cwd()}/${tarballName}`

  const tarballData = await readFileAsync(filePath)

  const registry = nano.db.use("registry")
  let response
  try {
    const docName = repoName

    // Step 3
    const response = await registry.insert({ readmeContents }, docName)
    await registry.attachment.insert(
      docName,
      tarballName,
      tarballData,
      "application/zip",
      { rev: response.rev }
    )
  } catch (e) {
    console.log("Error:", e)
  }
  console.log("Response success: ", response)
}

async function packageRepo(repoName) {
  try {
    // Step 2
    await tar.create(
      {
        gzip: true,
        file: `${repoName}.tar.gz`,
        cwd: process.cwd(),
      },
      ["./"]
    )
  } catch (e) {
    console.log("gzip ERROR: ", e.message)
  }
}

async function run() {
  // Step 1.1
  const repoName = require(`${process.cwd()}/package.json`).name
  // Step 1.2
  const readmeContents = await readFileAsync(`${process.cwd()}/README.md`, {
    encoding: "utf8",
  })

  await packageRepo(repoName)

  await sendPackage(repoName, readmeContents)

  // Step 4 - remove file
  unlinkSync(`${repoName}.tar.gz`)
}

run()

Website

Located under packages/website we will use Docker to create a basic NodeJS website.

Our packages/website/Dockerfile looks like.

FROM node:14-alpine

# Create app directory
RUN mkdir -p /usr/src/app
WORKDIR /usr/src/app

# Install dependencies
COPY package.json package-lock.json ./
RUN npm install

# Bundle app source
COPY . ./

# Exports
EXPOSE 3000
CMD [ "npm", "run", "start.dev" ]

The website details are located in packages/website/src/server.js

For a request to the /packages/:package-name url

Query the couchdb instance for the package name
Using showdown library, render the README markdown as HTML.

If no package is found a nice message is printed.

// deps...
const nano = require("nano")("http://couchdb_container:5984") // no auth for GET

// Constants
const PORT = 3000
const HOST = "0.0.0.0"

// couchdb
async function findOne(packageName) {
  try {
    const registry = nano.db.use("registry")
    // Step 1
    const doc = await registry.get(packageName)
    console.log("client result: ", doc)
    return doc
  } catch (err) {
    console.log("ERROR: ", err.message)
  }
}

// App
const app = express()
app.get("/packages/:packageName", async (req, res) => {
  const packageName = req.params["packageName"]

  const result = await findOne(packageName)
  if (result) {
    const converter = new showdown.Converter()
    // Step 2
    const html = converter.makeHtml(result.readmeContents)
    res.send(html)
  } else {
    res.send("No package found")
  }
})

app.listen(PORT, HOST)
console.log(`Running on http://${HOST}:${PORT}`)

Lastly we will add the website to our docker-compose.yml so we can run it with the registry database.

The docker-compose.yml now looks like this

version: "3.0"

services:
  web:
    build: packages/website
    ports:
      - "3000:3000"
    restart: always
    volumes:
      - ./packages/website:/usr/src/app

  couchdb_container:
    image: couchdb:1.6.1
    ports:
      - 5984:5984

Testing it works

We now have 3 of the core 3 jobs carried out by NPM, so we need to test it works using an example application and example library.

`example-lib`

The library will just return a string.

The packages/example-lib/package.json looks like below.

{
  "name": "example-lib",
  "main": "index.js"
}

The packages/example-lib/index.js is below, it just returns a string.

module.exports = () => "example-lib data"

`example-app`

It will print information from a real library (e.g. express) and our example library.

Our packages/example-app/package.json looks like this. As mentioned the version is ignored for our PoC.

{
  "ourDeps": {
    "example-lib": null
  }
}

The packages/example-app/src/index.js is below.

const express = require("express")
const exampleLib = require("example-lib")

console.log("express function", express.urlencoded)
console.log("example-lib function", exampleLib())

Lastly we update the reset in our Makefile to also remove the package installed and uninstall the global binary commands. The final file is below:

up:
    docker-compose up --build

db:
    curl -XPUT http://localhost:5984/registry

stop:
    docker-compose stop

reset:
    curl -X DELETE \
        'http://localhost:5984/registry' \
        -H 'content-type: application/json'
    rm -rf packages/example-app/node_modules/example-lib
    cd packages/cli && npm uninstall -g our-npm-cli

Running the example

Setup commands

make up

make reset

Check website for the package

GET http://localhost:3000/packages/example-lib -> Notice the package does not exist yet

Setup the database and CLI

make db
cd packages/cli
npm install -g . -> Install the 2 CLI scripts globally (see bin inside package.json)

Publish the package then check website

cd ../example-lib
our-npm-publish -> Publish the example-lib package to our registry
GET http://localhost:5984/registry/example-lib/example-lib.tar.gz -> Location of the registry package tarball
GET http://localhost:3000/packages/example-lib -> Package README on website (screenshot below)

Use package

cd ../example-app
npm start -> See the missing package error (screenshot below)
our-npm-install -> Install the packages from package.json -> ourDeps list (screenshot below)
npm start -> Package found, now it works (screenshot below)

So thats it 🙌, our mini NPM works.

I encourage anyone that is interested to check out the code and play with the mechanism yourself.

What have we missed?

As mentioned there is functionality to each of the 3 core elements to NPM which we have omitted from our app. Some of those are:

CLI

Various commands including init and pack
Ability to download a package via argument
Creating lockfile (including versions and dependency info)
Caching and request/response data
Flags e.g --devDeps
Dependency module resolution (NPM has a lot of logic for managing this, see overview section)

Registry

Better authentication on the CouchDB instance
sha512sum hash of package/tarball contents ("Subresource Integrity" check)
Install counter
Semvar package versions

Website

Show install increment
Show versions and intergrity hash
A decent UI

Thanks so much for reading, I learnt a huge amount about NPM from this research and I hope it was useful for you. You can find the repository for all this code here.

Thanks, Craig 😃

How we resolved a memory leak on our website

Craig Taub — Thu, 20 May 2021 09:40:58 +0000

The fiit website is used for creating subscriptions as well as helping users log into the app on TV platforms such as Sky and Amazon. As such it is an important asset to the business, but ultimately does not change very often.

For some time there has been a memory leak on the website. How can we be sure? I think the memory graphs below are pretty self explanatory. This is the memory usage over a normal week (shows min/max and average in green).
You can see every 1-2 days it would increase up to 100% before it eventually crashes and then starts the process all over again.

The stack is out of date, with some node modules being 3 years behind, and NodeJS being version 10 (which was released in October 2018). At time of writing LTS is 14.17.

So we know there is a leak, it could be our code or it could be an out of date version. Where to start?

Plan A - Local profiling

We thought we would start by analysing our code. We would run the application in production mode, and take memory snapshots with Chrome dev-tools at various times. Comparing the difference between the snapshots should hopefully highlight the cause.

However there were a couple of other problems to solve first...

Problem #1 - How to thrash the server locally?

We used Apache Benchmark to do this. It is pretty great, you can set the total number of requests and number in parallel. E.g

ab -c 50 -n 5000 -k http://localhost:8080/

Problem #2 - Which pages to thrash?

Now we have a tool which we can use to replicate high user volume, where should we target?

The website uses GA, so I grabbed the 2 most popular pages, one of which is the homepage, and planned to use both of those.

Problem #3 - How to capture the memory of a server run via docker containers?

This has 3 steps

On the docker image expose the NodeJS debugger port (this is 9229). e.g 9229:7001
On the docker image start the application with the debugger on. E.g. --inspect=0.0.0.0 and garbage collection exposed --expose-gc (the reason is so we can trigger GC before we collect a snapshot, therefore isolating the parts of memory which are not being collected properly)
Open Chrome inspector (chrome://inspect/#devices) and add a target to localhost:7001 (our remote debugging port)
Find the application you want to profile running in the list, click it and you will get an open Chrome dev-tools. From here we can use the "memory" tab to take heap snapshots.

Now we are running our server application on a docker container, and can connect to the box's memory.

Local profiling

We decided to start with 1000 requests, 30 at a time.
We would take a memory heap snapshot every 2 minutes for about 8 minutes, forcing a GC (global.gc()) each time, then at the end compare the different snapshots, looking for items with a large footprint i.e. 1% or greater.

What we immediately found was an issue with how we used Lodash, and more specifically the memoize() function.
We were handing unique keys each time and thus creating a new instance of the function every single time. So the internal Map would just keep growing. This counts as a leak.
The 2 culprits were found in the below snapshots, note the first internal array is the “node_modules”, and removed from code.

There was also a 3rd instance of this which was actually worse than the others, so this was also removed.

Removing the memoize function fixed these particular problems.

However the overall problem on production remained and the boxes continued to leak memory in the same way.

At this point we felt it might be useful to get more insights to the leak on production.

Plan B - More production visibility

We decided there were 2 ways to gather production box information.

1. Prometheus

Add Prometheus to the box - it is fantastic at capturing all kinds of low level metrics and might prove insightful at helping us locate the source of the leak.
The idea is we add a /metrics endpoint for the app which exposes certain stats, and we can gather and display them on our Grafana.

This is an example of the /metrics output.

With the Koa library, the change looks something like this, using the popular library prom-client.

Once this change was live we were able to analyse the results.
One of the most interesting metrics is called "NodeJS heap space size used". It lets you examine the performance of different memory spaces.

const metricsRouter = new Router();

metricsRouter.get('/metrics', async (ctx) => {
  ctx.set('Content-Type', register.contentType);
  ctx.body = await register.metrics();
  ctx.status = 200;
});

router.use(metricsRouter.routes());

What we found was that the "old space" is where the leak resides.

To demonstrate the difference in memory space here is the "new space" in a period of time.

And here is the same period of time with the "old space". A clear leak.

What this suggests is that we have objects surviving being garbage collected, the top 2 reasons for this is that we have pointers to other objects still in memory or we have raw data being continually written to. Both those reasons are typically caused by bad code.

2. Heapdump

Using the heapdump package we can capture and download snapshots from production, put them into the Chrome memory profiler locally and try to locate the source of the leak.
The idea is that the real box memory would contain the real leak, whereas local attempts to replicate had mostly failed to be consistent.

There were 3 problems with this, most come from the fact we use AWS ECS Fargate on production distributing requests across multiple containers.

Problem #1

We could not connect directly to a running box via terminal (ala a "docker exec" like command) as they are not exposed this way. Any "ECS" command is run in a new container and therefore would be useless at providing a memory snapshot we can use.

Problem #2

Given "Problem #1" we knew we had to go with exposing a URL to download the snapshot. However we could not reliably hit the URL of the same box. The load balancer would keep moving us around boxes (we have not enabled sticky sessions) so we would take memory dumps of the different boxes which would prove useless once compared.

Problem #3

Building a memory snapshot uses a heck of a lot of CPU and memory in itself. It is a very intensive task. So we had to make sure any URL that exposed this ability was behind some sort of authentication.

Solution

We added a url to the website and added authentication via time sensitive 1-way hash to ensure nobody could hit the page without our permission.

The process to download the memory heap snapshot file was to first generate a valid hash locally, tied to the start of the hour (I have omitted the real value)

node -e "const moment = require('moment'); console.log(crypto.createHmac('sha256', 'secret-key').update(JSON.stringify({ date: moment.utc().startOf('hour').toISOString(), value: '[obfuscated]' })).digest('hex'));"

And to then hit the website url with /heapdump?hash=<hash> to download the file.

The same hash code is run on the server and as long as they match the current memory snapshot is taken, this took care of Problem #1 and Problem #3.
The snapshot filename is the ECS task-id (more details on how to capture that in AWS docs here), so hitting it a couple of times should get around Problem #2 and generate profiles from the same box.

Analyse production snapshots

We followed the same process as with our local profiling i.e. hitting a box then waiting a couple of minutes to hit it again. Then comparing the memory allocated between them.
The 2 tasks profiled are shown in google dev-tools below.

The good news is that the snapshots highlight the clear signs of a leak. The memory always starts around 50mb, after 10-15 minutes has moved to 85mb then another 10-15 minutes later is 122mb. Generating the snapshot will incur a memory cost, but it should not be that much.
This is not something we were able to see locally.

By looking at the “objects allocated” between the snaps with the large gaps (see below) we found that an internal array was increasing by 4-5% (note: the top item is the snapshot itself, it requires memory to generate the snapshot).
This applies to the retained memory, which is important as it lets us know how much memory would be freed if this object was garbage collected.

As each entry was from a different library we decided it was possibly a NodeJS issue, perhaps maps/arrays were not as optimised in v10 as in v14?

Upgrading NodeJS

Upgrading the version of NodeJS that the website uses was fairly straightforward as we were not using any deprecated features from v10. We had to update the Docker image, CircleCI config and our local NVM config. All of which to the latest at the time, which was v14.16.

The results were immediate..instead of a continual steep incline up, the memory remained stable, see below.

The old space in the heap, which was previously the root cause, was looking much better after the upgrade too.

So that was it 🙌🏻 ! We profiled production, found the root cause, applied a fix and since that day the website's memory usage has been stable.

Lessons learned

We learnt a lot through this journey, here we detail a couple of points:

When dealing with a leak local profiling is a good place to start, but don’t pin all your hopes on finding the cause there
Use prometheus to locate the memory space of a memory leak
Compare memory heap dumps in google dev-tools to locate the source of the memory leak
If you are considering collecting production memory snapshot, be aware of what your infrastructure can or cannot do
Keep your dependencies up to date, if you don't eventually there will be a price to pay

We hope you enjoyed this post.
If you think you would be interested to work with the engineering department at Fiit check out our careers page here to see what's available.

Thanks

Under-the-hood of Git

Craig Taub — Mon, 22 Mar 2021 10:29:51 +0000

Originally posted on craigtaub.dev

For many years now Git has been the SCM (source control management aka version control) of choice. It offered many features which alternatives such as CVS did not, and combined with GitHub website created an entire CI pipeline which any teams Dev practices could be built around.

When I began reading about the mechanics of Git it was obvious that it's combination of many different techniques, all of which produce the "replicated versioned file system" know as Git, for example:

Linked lists,
File system objects database
Hashing (stat SHA-1 vs content SHA-1 vs content Deflate)
Differential encoding

So I decided to create a mini-working version with some of the core version control features. Thankfully there are many helpful books which break down how things work, so I have attempted to strip the internals down to its bare minimum.

This post will focus on:

repositories,
working directories,
staging,
committing
status checks.

I have omitted packfiles, deltas, branches, tags, merging and comparing staged chunks (diffing). I may do a follow up post/repository on those.

This is part of my "under-the-hood of" series:

A video for this talk can be found here. Part of my "under-the-hood of" series here.

The article today will be broken down into:

1) Overview

Workflow
Object model
Components
Additional reading

2) Building our own Git

Our git code
Testing it works

3) What have we missed?

1: Overview

Git is described as a distributed version-control system, which tracks changes in any set of files. It was initially released 15 years ago (in 2005) and has grown in functionality and popularity massively since then. As any developer who uses Github knows (or an alternative e.g. BitBucket/GitLab) it has become a staple in the world of software as a best practice.

Workflow

I am not going to review how it is used but the basic workflow can be summarised by:

initialise a new git repository
A file/s change is made locally and saved
The file/s is added to staging
The file/s in the staging area are comitted
The commit is pushed to a remote repository (pulling the latest before doing so).

We will break down each step, but before we do we need to review the mechanism at the core of Git, the "Object model".

Object model

The object model is essentially an incredibly efficient versioned file system (with replication).

Each file in the repository exists in the file system and the object database. The object database is a hash of the contents.
A hash is an object, there are 4 types in total but today we will look at (excluding "tags"):

Blob -> a sequence of bytes. A blob in Git will contain the same exact data as a file, it’s just that a blob is stored in the Git object database. Basically the file contents.
Tree -> corresponds to UNIX directory entries. Can contain blobs or sub trees (sub directory). The commit tree has the entire project in blob and trees at time of the commit. It can recreate the entire project from that tree. Always from root directory even if a sub directory file is being updated in the commit.
Commit -> single tree id and commits preceding it

Each tree node, commit and file have their own unique 40 character long SHA-1 representation. The filename is a hash of the contents. If the contents change, so does the hash. Each time it changes a new entry/hash is added but keeps the old ones.

Inside a git repository they are found under the .git/objects folder.

This is my favourite image to describe the structure.

Hash

Within the object model, the filename is a 2-way SHA-1 encoding of the contents.

Git prefixes any Blob objects with blob, followed by the length (as a human-readable integer), followed by a NUL character
Example:

> s='abc'
> printf "$s" | git hash-object --stdin

Equivalent to

> printf "blob $(printf "$s" | wc -c)\0$s" | sha1sum

Object file contents are compressed via DEFLATE zlib algorithm, it is less human readable or filename-friendly but a more efficient encoding.

Components

I will be covering the components we will be building in our mini-working version.

Working directory

The current system folder with git repository in, also known as the working tree.

HEAD

A file holding a ref to current working branch. Basically the last checked out workspace.
It holds a reference to the parent commit, usually last branch checked out.

Found in the file .git/HEAD.
Example

> ls  .git/HEAD

ref: refs/heads/master

> ls .git/refs/heads/master

2e1803ee08fa9aa36e4c5918220e283380a4c385

Branches

A branch is actually just a named pointer to specific snapshot.
When it is checked out

moves HEAD pointer to point to the feature ref (branch)
moves all content from the current branch repo into the index file, so it's easy to track changes.
Make working dir match content of commit pointing to (using tree and blob objects to update working dir contents)

Repository

A git project stored on disk i.e. not in-memory. Essentially a collection of objects.

Staging

Area between working directory and repository. All changes in staging will be in the next commit.

Index file

The index is a binary file, it does not hold objects (blobs/trees), it stores info about files in repository. It is a virtual working tree state.

The index file is located at .git/index. You can see the status of the Index file via > git ls-files --stage

Information stored

For each file it stores

time of last update, name of file,
file version in working dir,
file version in index,
file version in repository

File versions are marked with checksums, a SHA-1 hash of stat(), not a hash of the contents. This is more efficient.

Refresh

It is updated when you checkout a branch or the working directory is updated. Runs in the background automatically.

Hashing

It uses uses a filesystem stat() to get the files information, to check quickly if the working tree file content has changed from version recorder in index file. Checks the file modification time under st_mtime.

The refresh literally calls stat() for all files.

Additional reading

The main goal of this post is the mini-working version below so we have only just touched briefly on how git works. Here are websites which go into far more details

2: Building our own Git

our git code

The code consists of 4 files, one for each command, plus a util.

init.mjs
status.mjs
add.mjs
commit.mjs
util.mjs

init.mjs

// imports excluded, see linked repo for details
const init = () => {
  const workingDirectory = workingDir()
  const files = glob.sync("**/*.txt", { cwd: workingDirectory }) // (1)

  const indexData = files.reduce((acc, curr) => { // (2)
    const hash = hashFileStats(curr)
    acc[curr] = {
      cwd: hash,
      staging: "",
      repository: "",
    }
    return acc
  }, {})

  fs.mkdirSync(`${workingDirectory}/.repo`) // (3)
  updateIndex(indexData)
  fs.writeFileSync(`${workingDirectory}/.repo/HEAD`) // (4)
  fs.mkdirSync(`${workingDirectory}/.repo/objects`) // (4)
}

(1) Grab all the files from the current working directory
(2) Build the index file using files stat() SHA-1 hash for each file
(3) Write a repository folder under .repo
(4) Inside repository write a HEAD file and objects folder

status.mjs

// imports excluded, see linked repo for details
const status = () => {
  const indexData = getIndexData() // (1)

  const notStaged = []
  const notComitted = []
  const updatedIndexData = Object.keys(indexData).reduce((acc, curr) => { // (2)
    const hash = hashFileStats(curr) // (2a)
    if (hash !== indexData[curr].cwd) { // (2b)
      acc[curr] = {
        cwd: hash,
        staging: indexData[curr].staging,
        repository: indexData[curr].repository,
      }
      notStaged.push(curr)
    } else {
      if (indexData[curr].cwd !== indexData[curr].staging) {
        notStaged.push(curr) // (2c)
      } else if (indexData[curr].staging !== indexData[curr].repository) {
        notComitted.push(curr) // (2d)
      }
      acc[curr] = indexData[curr]
    }

    return acc
  }, {})

  updateIndex(updatedIndexData) // (3)

  console.log("\nChanged locally but not staged:")
  notStaged.map(message => console.log(`- ${message}`)) // (4)
  console.log("\nStaged but not comitted:")
  notComitted.map(message => console.log(`- ${message}`)) // (5)
}

(1) Grab the index data
(2) For each item in the index data
(2a) Grab files stat() SHA-1 hash
(2b) If doesnt match current working dir stored hash of file, flag as changed not staged
(2c) If does match above but doesnt match staged, flag as not staged
(2d) If does match staged but not repository, flag as not comitted
(3) Update index file
(4) Output local changes not staged
(5) Output staged changes not comitted

add.mjs

// imports excluded, see linked repo for details
const add = () => {
  const workingDirectory = workingDir()

  const files = process.argv.slice(2) // (1)

  const indexData = getIndexData()

  console.log("[add] - write blob objects")
  const updatedFiles = files.map(file => {
    const blobHash = hashBlobContentsInFile(file) // (2)
    const blobDir = blobHash.substring(0, 2)
    const blobObject = blobHash.substring(2)

    // TODO - check exists first - for re-adding file with earlier contents
    fs.mkdirSync(`${workingDirectory}/.repo/objects/${blobDir}`)

    const blobCompressed = compressBlobContentsInFile(file) // (3)
    fs.writeFileSync(
      `${workingDirectory}/.repo/objects/${blobDir}/${blobObject}`,
      blobCompressed
    )

    const hash = hashFileStats(file) // (4)

    return {
      file,
      hash,
    }
  })

  const updatedIndexData = Object.keys(indexData).reduce((acc, curr) => { // (5)
    if (!updatedFiles.find(item => item.file === curr)) { // (5a)
      acc[curr] = {
        cwd: indexData[curr].cwd,
        staging: indexData[curr].staging,
        repository: indexData[curr].repository,
      }
      return acc
    }
    acc[curr] = {
      cwd: indexData[curr].cwd,
      staging: updatedFiles.find(item => item.file === curr).hash, // (5b)
      repository: indexData[curr].repository,
    }
    return acc
  }, {})

  updateIndex(updatedIndexData) // (6)
}

(1) Explicitly give files e.g. one.txt and two/three.txt
(2) For each file, get contents in SHA-1 and use for directory name and filename
(3) Get DEFLATED value and use for content
(4) Get SHA-1 value for files stat()
(5) Update the index
(5a) If file was not touched, just proxy values
(5b) If file was touched, update staging for the file
(6) Override old index data with new index data

commit.mjs

// imports excluded, see linked repo for details

// array of dir (name) and files (children), ordered by bottom-up
const _buildTree = paths => {
  return paths.reduce(
    (parent, path, key) => {
      path.split("/").reduce((r, name, i, { length }) => {
        if (!r.children) {
          r.children = []
        }
        let temp = r.children.find(q => q.name === name)
        if (!temp) {
          temp = { name }
          if (i + 1 === length) {
            temp.type = "blob"
            temp.hash = hashBlobContentsInFile(path)
          } else {
            temp.type = "tree"
          }
          r.children.push(temp)
        }
        return temp
      }, parent)

      return parent
    },
    { children: [] }
  ).children
}

const commit = () => {
  const workingDirectory = workingDir()
  const indexData = getIndexData()
  // TODO - if comitted already then dont recreate tree?? PROB chek first
  const paths = Object.keys(indexData).filter( // (1)
    item => indexData[item].staging || indexData[item].repository
  )

  const rootTrees = _buildTree(paths) // (2)

  const flattenedTrees = rootTrees.reverse().reduce((acc, curr, key) => { // (3)
    if (curr.children) {
      const hash = createTreeObject(curr.children) // (3a)
      const clone = Object.assign({}, curr)
      delete clone.children
      clone.hash = hash
      acc.push(curr.children) // (3b)
      acc.push([clone])
    } else {
      acc[key].push(curr) // (3c)
    }
    return acc
  }, [])

  const rootTree = flattenedTrees.reverse()[0]
  const treeForCommit = createTreeObject(rootTree) // (4)

  const parent = getParentCommit()

  const commit = { // (5)
    tree: treeForCommit,
    parent: parent === "undefined" ? null : parent,
    author: "CRAIG", // hardcoded for now
    committor: "CRAIG",
    message: "Initial commit",
  }

  const commitHash = createCommitObject(commit) // (6)

  const updatedIndexData = Object.keys(indexData).reduce((acc, curr) => { // (7)
    const { cwd, staging, repository } = indexData[curr]
    let updatedRepo = repository
    if (staging !== repository) { // (7a)
      updatedRepo = staging
    }
    acc[curr] = {
      cwd: indexData[curr].cwd,
      staging: indexData[curr].staging,
      repository: updatedRepo,
    }
    return acc
  }, {})
  updateIndex(updatedIndexData)

  fs.writeFileSync(`${workingDirectory}/.repo/HEAD`, commitHash) // (8)
}

(1) Grab files of files to commit
(2) Build tree for files in staging or comitted, excluded working dir only
(3) Iterate items root "tree" into a flattened array of trees
(3a) If tree, create tree for children
(3b) Then add children to flattened tree
(3c) If not a tree, push with previous tree
(4) Create tree object for root
(5) Create commit object, using parent commit if exists and the tree hash
(6) From commit object get commit hash
(7) Update index file
(7a) If staging hash does not match repository hash then update. An existing file has been updated.
(8) Update HEAD with the latest commit

utils.mjs

I have included the helper file but hopefully the names are pretty self-explanatory.

The largest is createTreeObject and createCommitObject. Both of which:

Process given contents into a hash
Compress given contents
Writes compressed contents to the respective directory and file - The first 2 characters of a hash become the directory and the rest the filename.

import fs from "fs"
import crypto from "crypto"
import zlib from "zlib"

export const workingDir = () => {
  const cwd = process.cwd()
  return cwd + "/src"
}

export const sha1 = object => {
  const string = JSON.stringify(object)
  return crypto
    .createHash("sha1")
    .update(string)
    .digest("hex")
}

const getFilePath = file => {
  const workingDirectory = workingDir()
  return `${workingDirectory}/${file}`
}
const getContentsInFile = file => {
  const path = getFilePath(file)
  return fs.readFileSync(path, { encoding: "utf-8" })
}

export const compressBlobContentsInFile = file => {
  const contents = getContentsInFile(file)
  return zlib.deflateSync(contents)
}

// always same based on contents
export const hashBlobContentsInFile = file => {
  const contents = getContentsInFile(file)
  return sha1({ type: "blob", contents })
}

// different based on midified time
// remove atime + atimeMs which are different each stat() call
export const hashFileStats = file => {
  const path = getFilePath(file)
  const contents = fs.statSync(path)
  delete contents["atime"]
  delete contents["atimeMs"]
  return sha1(contents)
}

export const getIndexData = () => {
  const workingDirectory = workingDir()
  return JSON.parse(
    fs.readFileSync(`${workingDirectory}/.repo/index`, { encoding: "utf-8" })
  )
}

export const updateIndex = indexData => {
  const workingDirectory = workingDir()
  fs.writeFileSync(`${workingDirectory}/.repo/index`, JSON.stringify(indexData))
}

// hash contents, create tree, return hash
export const createTreeObject = contents => {
  const contentsClone = Object.assign([], contents)
  const flatContents = contentsClone.map(item => {
    delete item.children // dont need full children depth
    return item
  })
  const workingDirectory = workingDir()
  const stringContents = JSON.stringify(flatContents)
  const treeHash = sha1(stringContents)
  const treeDir = treeHash.substring(0, 2)
  const treeObject = treeHash.substring(2)
  const treeCompressed = zlib.deflateSync(stringContents)
  // create tree object
  fs.mkdirSync(`${workingDirectory}/.repo/objects/${treeDir}`)
  fs.writeFileSync(
    `${workingDirectory}/.repo/objects/${treeDir}/${treeObject}`,
    treeCompressed
  )
  return treeHash
}

export const createCommitObject = contents => {
  const workingDirectory = workingDir()
  const stringContents = JSON.stringify(contents)
  const commitHash = sha1(stringContents)
  const commitDir = commitHash.substring(0, 2)
  const commitObject = commitHash.substring(2)
  const commitCompressed = zlib.deflateSync(stringContents)
  // create commit object
  fs.mkdirSync(`${workingDirectory}/.repo/objects/${commitDir}`)
  fs.writeFileSync(
    `${workingDirectory}/.repo/objects/${commitDir}/${commitObject}`,
    commitCompressed
  )
  return commitHash
}

export const getParentCommit = () => {
  const workingDirectory = workingDir()
  return fs.readFileSync(`${workingDirectory}/.repo/HEAD`, {
    encoding: "utf-8",
  })
}

Testing it works

I wrote a small project to test the version control. 3 files each with a line of text, 2 of which inside a folder.

The above scripts are found inside bin/

A working directory / application is found in src/

one.txt
two/three.txt
two/four.txt

Then I wrote some inegration tests (test/index.integration.spec.js) to help track what happens to our repository for a given command, the steps (and results) are:

repo:init => created INDEX with current working directory files stat() hash
repo:status => flag 3 new local changes not staged (those above)
repo:add one.txt two/three.txt =>
- should create blob objects, inside 2 character-long directories, with content compressed
- should update INDEX, move items to staged
repo:status => flag 1 new local changes not staged and 2 changes not comitted
Manually update one.txt
repo:status => similar to previous except now flags one.txt as locally changed
repo:add one.txt => re-add updated file one.txt should update blob object
repo:status => re-added file should show with old added file
repo:add two/four.txt => add two/four.txt so 2 items in tree object
repo:commit => should create tree and commit object and update HEAD and INDEX

What have we missed?

As mentioned there are many additional parts to the real Git version control which we have omitted from our library. Some of those are:

Comparing change chunks (diffing)
Packfiles
Deltas
Branches
Tags
Merging

Thanks so much for reading, I learnt a huge amount about Git from this research and I hope it was useful for you. You can find the repository for all this code here.

Thanks, Craig 😃

Under-the-hood of type systems (e.g. TypeScript)

Craig Taub — Fri, 08 May 2020 12:00:09 +0000

I struggled to find an explanation from a low-level view of exactly how a "JavaScript type system compiler" is implemented. I understood many of the jobs of a type system but was unsure of the mechanisms involved and how they worked together.

This article looks to shine a light on some of the fundamentals at work under-the-hood. It is not possible to focus on everything in 1 article so here we will be looking at "type checks" specifically. Starting with an overview of type systems then building our own compiler which can run type checks and output sensible messages. For more help on transforms please see my article or talks on Web Bundlers or Source Maps.

A video for this talk can be found here. Part of my "under-the-hood of" series here.

NOTE: Apologies as there is some repetition in this article with my previous article on Source Maps. But it is important to include all of the necessary information to understand the mechanisms we will be looking at today.

This article will be broken down into (click links to navigate):

PART A: Overview of type system compilers (including TypeScript)
Syntax vs Semantics

What is AST?
Types of compilers
What does a language compiler do?
How does a language compiler work?
Type system compiler jobs
Advanced type checker features

PART B: Building our own type system compiler

The parser
The checker
Running our compiler
What have we missed?

Lets make a start 💪

PART A: Overview of type system compilers

Syntax vs Semantics

Something which is important to run over early is the difference between syntax and semantics.

Syntax

Is typically code which is native to JavaScript. Essentially asking if the given code is correct for the JavaScript runtime. For example the below is syntactically correct:

var foo: number = "not a number";

Semantics

This is code specific to the type system. Essentially asking if the given types attached to the code are correct. For example the above is syntactically correct BUT semantically wrong (defining the variable as a number but setting a string).

Next onto AST and compilers in the JavaScript ecosystem.

What is AST?

Before we go much further we need to take a quick look at one of the important mechanisms inside any JavaScript compiler, AST.

AST stands for "Abstract Syntax Tree", it is basically a tree of "Nodes" representing a Program of code. A "Node" is the smallest possible unit and is basically a POJO (i.e. plain old js object) with "type" and "location" properties. All Nodes have these 2 properties but based on the "type" they can have various other properties as well.

In AST form code is very easy to manipulate so operations like adding, removing or even replacing are do-able.

An example is the below code:

Would become the following AST:

There are websites such as https://astexplorer.net/ which are great at letting you write JavaScript code and immediately see its AST.

Types of compilers

There are 2 main types of compilers in the JavaScript ecosystem

1. Native compiler

A native compiler will convert code into a form that can be run by a server or computer (i.e. machine code). A compiler such as the one found in the Java ecosystem converts code into bytecode and then into native machine code.

2. Language compiler

A language compiler has a quite different role. The compilers for TypeScript and Flow both count in the category as language compilers as they output code into JavaScript. The main difference with native compilers is that they compile for tooling-sake (e.g. optimising code performance or adding additional features) not to produce machine code.

What does a language compiler do?

Let us start with the basics. A couple of the core jobs found in a type system compiler are:

1. Performing type checks

By this I mean the introduction of "types" (often via explicit annotations or implicit inference) and a way to check that 1 type matches another e.g. string vs number.

2. Running a language server

For a type system to work in a development environment it is best if it can run any type checks in an IDE and provide instant feedback for the user. Language servers connect a type system to an IDE, they can run the compiler in the background and re-run when a user saves a file. Popular languages such as TypeScript and Flow both contain a language server.

3. Transforming code

Many type systems contain code which is not supported in native Javascript (e.g. type annotations are not supported) so they must transform from unsupported JavaScript to supported JavaScript.

As mentioned at the very top we will be focusing on point (1) Performing type checks. If it seems valuable we could explore (2) language servers in the future. My articles on Web Bundlers and Source Maps go into more detail about (3) transforming code.

How does a language compiler work?

Next we will have a look at the steps required to perform all of the above jobs in an efficient and scalable way. There are 3 common stages to most compilers in some form or another.

1) Parse source code into AST

Lexical analysis -> Turn string of code into a stream (i.e. an array) of tokens.
Syntactic analysis -> Turn stream of tokens into its AST representation

Parsers check the "syntax" of given code. A type system will have to house its own parser, often containing thousands of lines of code.

The Babel parser contains 2,100 lines of code just to process code statements (see it here) which can understand the syntactical analysis of any compiler-specific code but also append additional information for types.

Hegel appends a typeAnnotation property to code which has a type annotation (you can see it doing it here).

TypeScript's parser is a whopping 8,600 lines of code (find where it begins traversing the tree here). It houses an entire superset of JavaScript which all requires the parser to understand.

2) Transform nodes on AST

Manipulate AST nodes

Here any transformations to apply to the AST are performed.

3) Generate source code

Turn AST into string of JavaScript source code

A type system has to map any non-JS compliant AST back to native JavaScript.

But how does a type system fit into that?

Type System compiler jobs

As well as the above steps, Type system compilers will usually include an additional step or 2 after "parsing" which will include the type-specific work.

On a side-note TypeScript actually has a total of 5 phases in its compiler, they are:

Language server pre-processor
Parser
Binder
Checker
Emitter

As you can see above the language server contains a pre-processor which triggers the type compiler to only run over the file/s which has changed. This will follow any "import" statements to determine what else could have changed and would need to be included in the next re-run. Additionally the compiler has the ability to only re-process the branch of the AST graph which has changed. More on "lazy compilation" below.

There are 2 common jobs to the type system compiler:

1. Inferring

Inferring is required for code which does not have an annotation. On that subject there is a really interesting blog post here on when to use type annotations and when to let the engine use Inference.

Using a pre-defined algorithm the engine will calculate what the type for a given variable/function is.

TypeScript uses the algorithm "best common type" inside of its Binding phase (the 1st of 2 semantic passes). It considers each candidate type and picks the type that is compatible with all the other candidates. Contextual typing comes into play here i.e. using the location in the inference. There is more help on this in the TypeScript spec here. TypeScript actually introduces the idea of "Symbols" (interface here) these are named declarations which connect declaration nodes in the AST to other declarations contributing to the same entity. They are the basic building block of the TypeScript Semantic system

2. Checking

Now that (1) is complete and types have been assigned the engine can run its type checks. They check the "semantics" of the given code. There are many flavours of these types of checks ranging from type mis-match to type non-existing.

For TypeScript this is the Checker (the 2nd semantic pass) and it is 20,000 lines of code long. I feel that gives a really strong idea of just how complicated and difficult it is to check so many different types across so many different scenarios.

The type checker is NOT dependent on calling code i.e. if the file executes any of its own code (i.e. at runtime) . The type checker will process each line in a given file itself and run the appropriate checks.

Advanced type checker features

A couple of additional concepts which we will not dig into any deeper today due to the complexity they entail:

Lazy compilation

A common feature for modern compilations is "lazy loading". They will not recalculate or re-compile a file or AST branch unless absolutely required.

TypeScripts pre-processor can use AST code which is stored in memory from a previous run. This has a massive performance boost as it can just focus on running over a small part of the program or node tree which has changed. TypeScript uses immutable read-only data-structures stored in what it terms "look-aside tables". This makes it easy to know what has/has not changed.

Soundness

There are certain operations which a compiler can not know is safe at compile-time and must wait for run-time. Each compiler must make difficult choices as to what will and will not be included. TypeScript has certain areas which are said to "not to be sound" (i.e. require run-time type checks).

We will not be addressing the above features in our compiler as they add additional complexity and not worth it for our small POC.

Onto more exciting stuff now, building one ourselves…

PART B: Building our own type system compiler

We are going to build a compiler which can run type checks for 3 different scenarios and throw a specific message for each. The reason we will limit it to 3 scenarios is so we can focus on the specific mechanisms in work around each one, and hopefully by the end have a really strong idea on how to introduce more complex type checks.

We will be working with a function declaration and an expression (calling that function) in our compiler.

The scenarios are:

(1) Issue with type matching a string vs a number

fn("craig-string"); // throw with string vs number
function fn(a: number) {}

(2) Issue with using an unknown type which is not defined

fn("craig-string"); // throw with string vs ?
function fn(a: made_up_type) {} // throw with bad type

(3) Issue with using a property name not found on the interface

interface Person {
  name: string;
}
fn({ nam: "craig" }); // throw with "nam" vs "name"
function fn(a: Person) {}

Onto our compiler, there are 2 parts to our compilers, the parser and the checker.

The Parser

As previously mentioned we won't be focusing on a parser today. We will be following the Hegel parsing approach of assuming a typeAnnotation object has been attached to all annotated AST nodes. I have hardcoded the AST objects.

Scenario 1 will use the below parser:

function parser(code) {
  // fn("craig-string");
  const expressionAst = {
    type: "ExpressionStatement",
    expression: {
      type: "CallExpression",
      callee: {
        type: "Identifier",
        name: "fn"
      },
      arguments: [
        {
          type: "StringLiteral", // Parser "Inference" for type.
          value: "craig-string"
        }
      ]
    }
  };

  // function fn(a: number) {}
  const declarationAst = {
    type: "FunctionDeclaration",
    id: {
      type: "Identifier",
      name: "fn"
    },
    params: [
      {
        type: "Identifier",
        name: "a",
        typeAnnotation: {
          // our only type annotation
          type: "TypeAnnotation",
          typeAnnotation: {
            type: "NumberTypeAnnotation"
          }
        }
      }
    ],
    body: {
      type: "BlockStatement",
      body: [] // "body" === block/line of code. Ours is empty
    }
  };

  const programAst = {
    type: "File",
    program: {
      type: "Program",
      body: [expressionAst, declarationAst]
    }
  };
  // normal AST except with typeAnnotations on
  return programAst;
}

You can see the expressionAstblock for our top-line expression statement, and the declarationAst for where we have declared our function on the second line. We return a programAst which is a program with both AST blocks in.

Inside the AST you can see the typeAnnotation the param identifier "a", matching where it sits in the code.

Scenario 2 will use the below parser:

function parser(code) {
  // fn("craig-string");
  const expressionAst = {
    type: "ExpressionStatement",
    expression: {
      type: "CallExpression",
      callee: {
        type: "Identifier",
        name: "fn"
      },
      arguments: [
        {
          type: "StringLiteral", // Parser "Inference" for type.
          value: "craig-string"
        }
      ]
    }
  };

  // function fn(a: made_up_type) {}
  const declarationAst = {
    type: "FunctionDeclaration",
    id: {
      type: "Identifier",
      name: "fn"
    },
    params: [
      {
        type: "Identifier",
        name: "a",
        typeAnnotation: {
          // our only type annotation
          type: "TypeAnnotation",
          typeAnnotation: {
            type: "made_up_type" // BREAKS
          }
        }
      }
    ],
    body: {
      type: "BlockStatement",
      body: [] // "body" === block/line of code. Ours is empty
    }
  };

  const programAst = {
    type: "File",
    program: {
      type: "Program",
      body: [expressionAst, declarationAst]
    }
  };
  // normal AST except with typeAnnotations on
  return programAst;
}

It is very similar to Scenario 1 with its expression, declaration and program AST blocks. However the difference is the typeAnnotation inside params is made_up_type instead of what scenario 1 has which is NumberTypeAnnotation.

Scenario 3 will use the below parser:

function parser(code) {
  // interface Person {
  //   name: string;
  // }
  const interfaceAst = {
    type: "InterfaceDeclaration",
    id: {
      type: "Identifier",
      name: "Person",
    },
    body: {
      type: "ObjectTypeAnnotation",
      properties: [
        {
          type: "ObjectTypeProperty",
          key: {
            type: "Identifier",
            name: "name",
          },
          kind: "init",
          method: false,
          value: {
            type: "StringTypeAnnotation",
          },
        },
      ],
    },
  };

  // fn({nam: "craig"});
  const expressionAst = {
    type: "ExpressionStatement",
    expression: {
      type: "CallExpression",
      callee: {
        type: "Identifier",
        name: "fn",
      },
      arguments: [
        {
          type: "ObjectExpression",
          properties: [
            {
              type: "ObjectProperty",
              method: false,
              key: {
                type: "Identifier",
                name: "nam",
              },
              value: {
                type: "StringLiteral",
                value: "craig",
              },
            },
          ],
        },
      ],
    },
  };

  // function fn(a: Person) {}
  const declarationAst = {
    type: "FunctionDeclaration",
    id: {
      type: "Identifier",
      name: "fn",
    },
    params: [
      {
        type: "Identifier",
        name: "a",
        typeAnnotation: {
          type: "TypeAnnotation",
          typeAnnotation: {
            type: "GenericTypeAnnotation",
            id: {
              type: "Identifier",
              name: "Person",
            },
          },
        },
      },
    ],
    body: {
      type: "BlockStatement",
      body: [], // Empty function
    },
  };

  const programAst = {
    type: "File",
    program: {
      type: "Program",
      body: [interfaceAst, expressionAst, declarationAst],
    },
  };
  // normal AST except with typeAnnotations on
  return programAst;
}

As well as the expression, declaration and program AST blocks there is also an interfaceAst block which holds the AST for our InterfaceDeclaration. The declarationAst now has a GenericType on its annotation as it takes an object identifier i.e. Person. The programAst will return an array of those 3 objects for this scenario.

Similarities in the parsers

As you can see from above, the main area which holds the type annotation for all 3 scenarios is the declaration param. All 3 have that in common.

The Checker

Now onto the part of the compiler which does our type checks. It needs to iterate through all the program body AST objects and depending on the node type do the appropriate type checks. We will add any errors onto an array to be returned to the caller for printing.

Before we go any further, the basic logic we will work with for each type is:

Function declaration: check the types for the argument are valid, then check each statement in the block body
Expression: find the function declaration for the caller, grab the type on the declarations argument, lastly grab the type of the expressions caller argument and compare them.

The code

This snippet contains the typeChecks object (and errors array) which will be used to check our expression and a basic annotation check.

const errors = [];

const ANNOTATED_TYPES = {
  NumberTypeAnnotation: "number",
  GenericTypeAnnotation: true
};

// Logic for type checks
const typeChecks = {
  expression: (declarationFullType, callerFullArg) => {
    switch (declarationFullType.typeAnnotation.type) {
      case "NumberTypeAnnotation":
        return callerFullArg.type === "NumericLiteral";
      case "GenericTypeAnnotation": // non-native
        // If called with Object, check properties
        if (callerFullArg.type === "ObjectExpression") {
          // Get Interface
          const interfaceNode = ast.program.body.find(
            node => node.type === "InterfaceDeclaration"
          );
          // Get properties
          const properties = interfaceNode.body.properties;

          // Check each property against caller
          properties.map((prop, index) => {
            const name = prop.key.name;
            const associatedName = callerFullArg.properties[index].key.name;
            if (name !== associatedName) {
              errors.push(
                `Property "${associatedName}" does not exist on interface "${interfaceNode.id.name}". Did you mean Property "${name}"?`
              );
            }
          });
        }
        return true; // as already logged
    }
  },
  annotationCheck: arg => {
    return !!ANNOTATED_TYPES[arg];
  }
};

Let us walk through the code. Our expression has 2 types of checks:

For NumberTypeAnnotation; the caller type should be a NumericLiteral (i.e. if annotated as a number, the caller type should be a number). Scenario 1 would fail here but nothing is logged yet.
For GenericTypeAnnotation; if it is an object we search the tree for an InterfaceDeclaration and then check each property of the caller on that interface. Any issues get pushed onto the errors array, with a helpful message about what property name does exist and therefore what it could actually be. Scenario 3 would fail here and get this error.

Our processing is limited to this file, however most type checkers have the notion of "scope" so they would be able to determine if a declaration was anywhere in the runtime. Ours has an easier job as it is just a POC.

This snippet contains the processing of each node type in the program body. This is where the type check logic above is called from.

// Process program
ast.program.body.map(stnmt => {
  switch (stnmt.type) {
    case "FunctionDeclaration":
      stnmt.params.map(arg => {
        // Does arg has a type annotation?
        if (arg.typeAnnotation) {
          const argType = arg.typeAnnotation.typeAnnotation.type;
          // Is type annotation valid
          const isValid = typeChecks.annotationCheck(argType);
          if (!isValid) {
            errors.push(
              `Type "${argType}" for argument "${arg.name}" does not exist`
            );
          }
        }
      });

      // Process function "block" code here
      stnmt.body.body.map(line => {
        // Ours has none
      });

      return;
    case "ExpressionStatement":
      const functionCalled = stnmt.expression.callee.name;
      const declationForName = ast.program.body.find(
        node =>
          node.type === "FunctionDeclaration" &&
          node.id.name === functionCalled
      );

      // Get declaration
      if (!declationForName) {
        errors.push(`Function "${functionCalled}" does not exist`);
        return;
      }

      // Array of arg-to-type. e.g. 0 = NumberTypeAnnotation
      const argTypeMap = declationForName.params.map(param => {
        if (param.typeAnnotation) {
          return param.typeAnnotation;
        }
      });

      // Check exp caller "arg type" with declaration "arg type"
      stnmt.expression.arguments.map((arg, index) => {
        const declarationType = argTypeMap[index].typeAnnotation.type;
        const callerType = arg.type;
        const callerValue = arg.value;

        // Declaration annotation more important here
        const isValid = typeChecks.expression(
          argTypeMap[index], // declaration details
          arg // caller details
        );

        if (!isValid) {
          const annotatedType = ANNOTATED_TYPES[declarationType];
          // Show values to user, more explanatory than types
          errors.push(
            `Type "${callerValue}" is incompatible with "${annotatedType}"`
          );
        }
      });

      return;
  }
});

Let us walk through the code again, breaking it down by type.

FunctionDeclaration (i.e. function hello() { })

Start by processing the arguments/params. If you find a type annotation check if the type exists for the argument given i.e. argType. If it does not add an error to errors. Scenario 2 would get an error here.

Lastly we process the function body, however as we know there is no function body to process I have left it blank.

ExpressionStatement (i.e. hello())

First check the program body for the declaration of the function. This is where scope would apply to a real type checker. If no declaration is found add an error to the errors array.

Next we check each defined argument type against the caller argument type. If there is a type mismatch found then add an error onto the errors array. Both Scenario 1 and Scenario 2 will get this error.

Running our compiler

I have introduced a basic repository with a simple index file which processes all 3 AST node objects in 1 go and logs the errors. When I run it I get the below:

So to summarise:

Scenario 1

We defined the argument type of number, yet called it with a string

Scenario 2

We defined a type on the function argument which does not exist and then we called our function, so we get 2 errors (1 for bad type defined, 1 for type mismatch)

Scenario 3

We defined an interface but used a property called nam which was not on the object, we are asked if we meant to use name instead.

It works !!! Good job 👍💪

What have we missed?

As mentioned there are many additional parts to a type compiler which we have omitted from our compiler. Some of those are:

The parser: we manually wrote the AST blocks these would be generated on a real type compiler
Pre-processing/language compiler: A real compiler has mechanisms to plug into the IDE and re-run at appropriate times
Lazy compilation: No intelligence around what has changed or using memory
Transform: we have skipped the final part of the compiler which is where the native JavaScript code is generated.
Scope: as our POC is a single file it did not need to understand the notion of "scope" however real compiler have to always be aware of context.

Thanks so much for reading or watching, I learnt a huge amount about type systems from this research and I hope it was useful for you. You can find the repository for all this code here. Please spare a heart if you enjoyed this.

Thanks, Craig 😃

Source Maps from top to bottom

Craig Taub — Sun, 26 Apr 2020 12:01:56 +0000

This article covers a basic overview and an in-depth explanation of the mechanics of JS code generators and source maps. Building our own from scratch, hence why it is quite long.

Source Maps are something of a mystery to most people. They are found in most web-based compilation scenarios; from type system to web bundlers. But often the details of how they are actually built is not 100% transparent as their usage alone can be complex enough. Today we will start with a brief overview of what they are and how to use them. Then move onto walking through the lower-level mechanics; by building our own compiler which will generate some code and produce its own Source Map for browser consumption.

A full video walkthrough for this post is here. Part of my “under-the-hood of” video series.

The plan for today:

Part A: Intro to source maps and compilers

What is a source map and why are they useful?
Using source maps with popular tools
What is AST?
Steps in transforming JavaScript
How compilers build source maps

Part B: Building our own compiler

Building a JavaScript code generator
What is Base64 VLQ?
Adding source map support
Testing our source map

Lets get started 💪

Part A: Intro to source maps and compilers

1. What is a source map and why are they useful?

First let us look at some reason why people write JavaScript which needs transpilation into native JavaScript:

Using a type system,
Using the latest ES 8–9–10 features,
Code optimising (e.g minification)
Bundle optimising (e.g. vendor vs app bundles)

The modern compiler architecture looks like this:

The problem is that in the process of turning your modules into assets, the code itself becomes un-readable for humans as its emphasis is put on the computer (usually a browser or server) to read.

Some example code which has been put through a compiler is below. It becomes near impossible to reason about and even harder to debug if there is an issue.

This is where Source Maps come in !!

A basic definition for a Source Map would be:

“A source map provides a way of mapping code within a compressed file back to it’s original position in a source file”

So fairly straight forward in its purpose. Modern browsers will parse the source map automatically and make it appear as though you’re running un-minified or uncombined files.

An example below shows debugging TypeScript in the browser, something which is only possible due to Source Maps.

With this you could now put a breakpoint in your code and inside the browser inspect the call stack, variables and any runtime state, all via the pre-compiled TypeScript code.

2. Using source maps with popular tools

Connecting the browser to the source map

There are 2 ways to notify the Browser there is a source map available.

At the footer of a JavaScript file add

//# sourceMappingURL=/path/to/file.js.map

In the “Header” of a JavaScript file add

X-SourceMap: /path/to/file.js.map

Couple of points to note

Chrome will only download a source map if DevTools is open (as they can be huge in size)
Source maps will not appear as a network request (inside the network tab)
Once you have your source map you can add breakpoints inside the “source” code (found under sources tab).

Source map spec

Current source maps must follow the latest version of the source map spec. That is version 3 and can be found in full here, it is written by mostly Mozilla and Google engineers. Version 3 comes with improvements to its overall size that will speed up its downloading and parsing.

The below shows an example source map, an important point is the “mappings”, these are Base64 VLQ strings which contain the actual mappings from source to generated code. More on this later as we will be producing our own.

Usage in popular tools:

Node.js

Via the flag — enable-source-maps

Source maps cached and used for stack traces when an exception occurs.

Babel

By default Babel will add a source map location to the bottom of every generated bundle e.g.

//# sourceMappingURL=file.map.js

But via the flag — source-maps — inline you can tell Babel to use an inline source map, which looks like below (i.e. base64 encode string of contents).

//# sourceMappingURL=data:application/json;charset=utf-8;base64,....

Webpack

Via the config property devtool: ‘source-map’

It is worth noting that because tools like Webpack often carry out multiple transformations using many processors at once (e.g. Babel and TypeScript) it can still produce a single source map. Each processor will produce its own source map but there are libraries available which can concatenate JavaScript files while consolidating corresponding source map files. An example is called mapcat.

3. What is AST?

Before we go much further we need to take a quick look at one of the important mechanisms inside any JavaScript compiler, AST.

AST stands for “Abstract Syntax Tree”, it is basically a tree of “Nodes” representing a Program of code. A “Node” is the smallest possible unit and is basically a POJO (i.e. plain old js object) with “type” and “location” properties. All Nodes have these 2 properties, but based on the “type” they can have various other properties as well.

In AST form code is very easy to manipulate, so operations like adding, removing or even replacing.

An example is the below code:

Would become the following AST:

There are websites such as https://astexplorer.net which are great at letting you write JavaScript code and immediately see its AST.

Tree traversal

The most important part of processing the AST is understanding that there are different approaches and each has pros and cons.

An example of a popular type (and the type we will use today) is called “Depth-first search” and it works by starting at the root and exploring as far left as possible along each branch before backtracking. So it would process a tree in the below order:

So if we had a block of code such as

2 + 3 * 1

It would produce the following tree:

4. Steps in transforming JavaScript

There are 3 steps in transforming JavaScript:

1) Parse source code into AST

Lexical analysis -> Turn string of code into a stream (i.e. an array) of tokens.
Syntactic analysis -> Turn stream of tokens into its AST representation

2) Transform nodes on AST

Manipulate AST nodes (any library plugins would operate here e.g. Babel)

3) Generate source code

Turn AST into string of JavaScript source code

TODAY we are going to focus on the jobs of a generator !!

Libraries differ between doing just step 1 to doing all 3 steps.

Examples of libraries which do all 3:

Examples of libraries which do just 1:

Esprima (does parsing)
ast-types (does AST node manipulation)
Escodegen (does generation)

5. How compilers build source maps

There are 3 parts to producing a source map, all of which a compiler has to do:

1) Transform code and note the new generated source location

2) Check for a difference in location between the original and generated code

3) Using these mapping build a source map

This is an over-simplification and we will get more into the nuts and bolts of it in Part B below.

Part B: Building our own compiler

1. Building a JavaScript code generator

We will be starting with the below architecture. With the aim to produce a transformed file (index.es5.js) and source map (index.es5.js.map) after compilation.

Our src/index.es6.js will look like this (a simple “add” function):

function add(number) {
    return number + 1;
}
globalThis.add = add;

So now we have our pre-compiled source code. We want to start looking at the compiler.

THE PROCESS

There are a couple of steps our compiler must perform:

1. Parse the code to AST

As this article is not focusing on parsing, we will use a basic 3rd party tool for this (esprima or escodegen)

2. Add a shallow clone of each node onto the AST

This idea was borrowed from recast. The idea is that each Node will hold itself as well as a clone of itself (i.e. the original). The clone is used to check if the Node has changed. More about this later.

3. Transformation

We will manually be doing this. We could have used a library such as ast-types or @babel/types as they have useful APIs.

4. Generate source code

Turn our AST into JavaScript.

5. Add source map support

4 and 5 are done at the same time as above. This will involve traversing the tree and detecting where the AST node has changed with its “original” property. For those instances store a mapping between the “original” and the “generated” code.

6. Write to build/

Finally write our generated source code and its source map to the appropriate file.

THE CODE

Let us look at these steps again, but this time in more detail.

1. Parse the code to AST

Using a basic 3rd party tool (I went for a simple one called ast), we grab our file contents and pass them into the libraries parser.

import fs from "fs";
import path from "path";
import ast from "abstract-syntax-tree";

const file = "./src/index.es6.js";
const fullPath = path.resolve(file);
const fileContents = fs.readFileSync(fullPath, "utf8");
const sourceAst = ast.parse(fileContents, { loc: true });

2. Add a shallow clone of each node onto the AST

First we define a function called “visit” with the job of traversing the tree and executing our callback function on every single Node.

export function visit(ast, callback) {
  callback(ast);

  const keys = Object.keys(ast);
  for (let i = 0; i < keys.length; i++) {
    const keyName = keys[i];
    const child = ast[keyName];
    if (keyName === "loc") return;
    if (Array.isArray(child)) {
      for (let j = 0; j < child.length; j++) {
        visit(child[j], callback);
      }
    } else if (isNode(child)) {
      visit(child, callback);
    }
  }
}
function isNode(node) {
  return typeof node === "object" && node.type;
}

Here we are doing a “depth-first search” as mentioned above. For a given Node it will:

Execute the callback
Check for the location property, if so return early
Check for any properties which are arrays, if so call itself with each child
Check For any properties which are AST Nodes, if so call itself with the node.

Next we move onto producing our clones.

export const cloneOriginalOnAst = ast => {
  visit(ast, node => {
    const clone = Object.assign({}, node);
    node.original = clone;
  });
};

Our cloneOriginalAst function produces a clone of the Node and appends that onto the original.

For our cloning we use Object.assign so it is a shallow clone and copies the top-level properties. The nested props are still connected by pass-by-reference i.e. changing them will change the clone. We could have also used the spread operator here as that does the same thing. We will do our comparison using the top-level which is enough to compare 2 AST nodes and determine if the node has changed or not.

Overall our code here will return the same tree except with “original” property on every single Node.

3. Transformation

Next we will do our node manipulation. We will keep it simple so are going to just swap 2 nodes from our program. So we will start with:

number + 1

And will end with:

1 + number

Simple in theory right !

Our code to do the swap is below:

// Swap: "number + 1"
// - clone left node
const leftClone = Object.assign(
  {},
  sourceAst.body[0].body.body[0].argument.left
);
// - replace left node with right node
sourceAst.body[0].body.body[0].argument.left =
  sourceAst.body[0].body.body[0].argument.right;
// - replace right node with left clone
sourceAst.body[0].body.body[0].argument.right = leftClone;
// Now: "1 + number". Note: loc is wrong

We have not used a clean API to do this (which many libraries provide) as we have manually swapped the 2 nodes.

An example of using a library with a helpful API could look something like below, provided by the documentation on ast-types.

This way is certainly safer, easier to follow and faster to develop with. So in general I would recommend using it for any complex AST manipulation, most big name compilers do.

4. Generate source code

Code generators are typically housed in a single file and are several thousand lines long. For example escodegen’s compiler is 2,619 lines (see here). That is on the smaller side compared to others (crazy right!)

I have used much of the same code for our compiler (as most generators need very similar logic to process AST into JavaScript) EXCEPT only what is absolutely necessary for us to process the code from our “index.es6.js” file.

Below I have defined the 3 types of code we have inside our compiler.

a) Node processors and character utilities

These are general utility functions used to process AST nodes (depending on the type e.g. a function declaration will have an identifier) and build source code. It also includes some common character constants (e.g. a “space”). They are called from our code “type statements” in the next section.

I would not worry too much about the details here unless you plan on writing a compiler. This was largely borrowed from the generator in escodegen here.

// Common characters
const space = " ";
const indent = space + space;
const newline = "\n";
const semicolon = ";"; // USUALLY flags on this

// Utility functions
function parenthesize(text, current, should) {
  if (current < should) {
    return ["(", text, ")"];
  }
  return text;
}
const generateAssignment = (left, right, operator, precedence) => {
  const expression = [
    generateExpression(left),
    space + operator + space,
    generateExpression(right)
  ];
  return parenthesize(expression, 1, precedence).flat(); // FLATTEN
};
const generateIdentifier = id => {
  return id.name;
};
const generateFunctionParams = node => {
  const result = [];
  result.push("(");
  result.push(node.params[0].name); // USUALLY lots of logic to grab param name
  result.push(")");
  return result;
};
const generateStatement = node => {
  const result = Statements[node.type](node);
  return result;
};
const generateFunctionBody = node => {
  const result = generateFunctionParams(node);
  return result.concat(generateStatement(node.body)); // if block generateStatement
};
const generateExpression = node => {
  const result = Statements[node.type](node);
  return result;
};

b) Type statements

This is an object holding functions which are tied to an AST node type. Each contains the logic necessary to process that AST node type and produce source code. For example for a function declaration it contains all possible variations of arguments, identifiers, logic and return types. There is a level of recursion that is common here i.e. for a type statement to trigger another type statement which might trigger another etc.

Here we ONLY have the necessary statement functions to process our “index.es6.js” file, so it is fairly limited. You can see how much code is required just to process our AST tree of 3–4 lines of code (in addition to that of the above section).

Again this has borrowed from escodegen here so please feel free to ignore the details, unless you plan to write your own compiler.

const Statements = {
  FunctionDeclaration: function(node) {
    let id;
    if (node.id) {
      id = generateIdentifier(node.id);
    } else {
      id = "";
    }
    const body = generateFunctionBody(node);
    return ["function", space, id].concat(body); // JOIN
  },
  BlockStatement: function(node) {
    let result = ["{", newline];
    // USUALLY withIndent OR for loop on body OR addIndent
    result = result.concat(generateStatement(node.body[0])).flat();
    result.push("}");
    result.push("\n");
    return result;
  },
  ReturnStatement: function(node) {
    // USUALLY check for argument else return
    return [
      indent,
      "return",
      space,
      generateExpression(node.argument),
      semicolon,
      newline
    ];
  },
  BinaryExpression: function(node) {
    const left = generateExpression(node.left);
    const right = generateExpression(node.right);
    return [left, space, node.operator, space, right];
  },
  Literal: function(node) {
    if (node.value === null) {
      return "null";
    }
    if (typeof node.value === "boolean") {
      return node.value ? "true" : "false";
    }
    return node.value;
  },
  Identifier: function(node) {
    return generateIdentifier(node);
  },
  ExpressionStatement: function(node) {
    const result = generateExpression(node.expression); // was []
    result.push(";");
    return result;
  },
  AssignmentExpression: function(node, precedence) {
    return generateAssignment(node.left, node.right, node.operator, precedence);
  },
  MemberExpression: function(node, precedence) {
    const result = [generateExpression(node.object)];
    result.push(".");
    result.push(generateIdentifier(node.property));
    return parenthesize(result, 19, precedence);
  }
};

c) Process code statements

Lastly we are going to iterate over the program body (i.e. each line of code) and start running our generator. This will now return an array called “code” which contains every line of our newly generated source code.

  const code = ast.body
    .map(astBody => Statements[astBody.type](astBody))
    .flat();

6. Write to build/

We are going to skip step 5 for now and complete the core elements of our compiler. So for this step we will

Add a source map location to our generated code (we will build this in the next section)
Produce a bundle for the generated code (joining our array of code together), and copy the original code so that the browser can see it (this is only 1 approach to this).

// Add sourcemap location
code.push("\n");
code.push("//# sourceMappingURL=/static/index.es5.js.map");

// Write our generated and original
fs.writeFileSync(`./build/index.es5.js`, code.join(""), "utf8");
fs.writeFileSync(`./build/index.es6.js`, fileContents, "utf8");

5. Add source map support

There are 4 requirements when it comes to building a source map:

Store record of source file
Store record of generated file
Store mappings of line/columns
Display in Source Map file using spec version3

For a quick win we can use the library which almost every JavaScript code generator uses called source-map. It is from Mozilla and handles storing of points 1–3 as well as the processing the mappings into Base64 VLQ (step 4).

Little reminder what a source map looks like with mappings highlighted (from way above):

The mappings are Base64 VLQ, but what is that?

2. What is Base64 VLQ?

A brief overview on Base64 and VLQ first.

Base64

Solves the ASCII problem of handling languages which don’t have the full ASCII character set. Base64 has only a subset of ASCII, which is easier for processing in different languages.

VLQ (variable-length quantity)

Breaks a binary representation of an integer into a group of small blocks of variable bits.

Base64 VLQ

Optimised to make it easy to have mapping between big numbers and corresponding information in source files.

A line of code is represented in a series of “segments”. The number “1” would be: AAAA => 0000
Here is an example of how the numbers correlate to build a “Segment”:

Building a basic mapping in JavaScript would look something like this:

// .. define "item"
const sourceArray = [];
sourceArray.push(item.generated.column);
sourceArray.push("file.es6.js");
sourceArray.push(item.source.line);
sourceArray.push(item.source.column);
const encoded = vlq.encode(sourceArray);

However this does not handle line and segment separation (which can be very tricky) so it is still more efficient to use Mozilla’s library.

3. Adding source map support

Back to our compiler !!

Using Mozillas SourceMapGenerator

To make full use of Mozillas library we will:

Create a sourceMap instance to hold and build our mappings
Initialise and store local mappings

So at times when a node has changed we will; build the location then add it to our local mappings and to the SourceMap instance. We keep a local instance so that we can keep a record of the current location start and end as that will be crucial to build out the next location.

// SourceMap instance
const mozillaMap = new SourceMapGenerator({
  file: "index.es5.js"
});

// Local mappings instance
const mappings = [
  {
    target: {
      start: { line: 1, column: 0 },
      end: { line: 1, column: 0 }
    },
    source: {
      start: { line: 1, column: 0 },
      end: { line: 1, column: 0 }
    },
    name: "START"
  }
];

We need a function which will actually handle updating these mapping instances. The below “buildLocation” function handles all the location generation logic. Most libraries have a similar function using offsets for column and line given by caller.

Its job is to work out the new start of line and column numbers as well as end of line and column numbers. It will only add a mapping if a node has changed, limiting what mappings we will store.

const buildLocation = ({
  colOffset = 0, lineOffset = 0, name, source, node
}) => {
  let endColumn, startColumn, startLine;
  const lastGenerated = mappings[mappings.length - 1].target;
  const endLine = lastGenerated.end.line + lineOffset;
  if (lineOffset) {
    endColumn = colOffset;
    startColumn = 0; // If new line reset column
    startLine = lastGenerated.end.line + lineOffset;
  } else {
    endColumn = lastGenerated.end.column + colOffset;
    startColumn = lastGenerated.end.column;
    startLine = lastGenerated.end.line;
  }

  const target = {
    start: {
      line: startLine,
      column: startColumn
    },
    end: {
      line: endLine,
      column: endColumn
    }
  };
  node.loc = target; // Update node with new location

  const clonedNode = Object.assign({}, node);
  delete clonedNode.original; // Only useful for check against original
  const original = node.original;
  if (JSON.stringify(clonedNode) !== JSON.stringify(original)) {
    // Push to real mapping. Just START. END is for me managing state
    mozillaMap.addMapping({
      generated: {
        line: target.start.line,
        column: target.start.column
      },
      source: sourceFile,
      original: source.start,
      name
    });
  }

  return { target };
};

So now we have our “buildLocation”, we have to go about introducing it across the code. A couple of examples are below. For the “generateIdentifier” processor utility and “Literal” AST type statements you can see how we incorporate “buildLocation”.

// Processor utility
const generateIdentifier = id => {
  mappings.push(
    buildLocation({
      name: `_identifier_ name ${id.name}`,
      colOffset: String(id.name).length,
      source: id.original.loc,
      node: id
    })
  );
  return id.name;
};

// AST type statement function (part of "Statements" object)
Literal: function(node) {
  mappings.push(
    buildLocation({
      name: `_literal_ value ${node.value}`,
      colOffset: String(node.value).length,
      source: node.original.loc,
      node
    })
  );

  if (node.value === null) {
    return "null";
  }
  if (typeof node.value === "boolean") {
    return node.value ? "true" : "false";
  }
  return node.value;
};

We need to apply this throughout our code generator (i.e. all node processors and AST type statement functions).

I found this tricky as the node-to-character mapping is not always 1–2–1. For example a function could have brackets either side of its argument which has to be accounted for when it comes to character line positions. So:

(one) =>

Has different character positions to:

one =>

What most libraries do is introduce logic and defensive checks using information on the AST nodes, so all scenarios can all be covered. I would have followed the same practice except I was only adding code for what was absolutely necessary for our “index.es6.js”.

For full usage please see the code for my generator in the repository here. It is missing large pieces but it does the job and is the building blocks for a real code generator.

The final part is writing our source map contents into the source map file. This is surprisingly easy with Mozillas library as they expose a “toString()” method which will handle the Base64 VLQ encoding and build all the mappings into a v3 spec compliant file. NICE !!

// From our Mozilla SourceMap instance
fs.writeFileSync(`./build/index.es5.js.map`, mozillaMap.toString(), "utf8");

Now our reference to “./build/index.es5.js” earlier will have a file that exists.

OUR COMPILER IS NOW DONE !!!! 🤩

Thats it for the compiler, the last part is now getting confirmation that is has worked.

If we compile the code it should produce our build folder with 3 files inside.

npm run compile

That is the original, the generated and the source map.

4. Testing our source map

There is a fantastic website at https://sokra.github.io/source-map-visualization/ which lets you visualise source map mappings.

The page starts like this:

By dropping our 3 files into it we can now see this:

Very colourful eh !

It contains the original code, the generated code and the mappings decoded (at the bottom).

A little reminder of our transformation from earlier:

// Swap: "number + 1"
// - clone left node
const leftClone = Object.assign(
  {},
  sourceAst.body[0].body.body[0].argument.left
);
// - replace left node with right node
sourceAst.body[0].body.body[0].argument.left =
  sourceAst.body[0].body.body[0].argument.right;
// - replace right node with left clone
sourceAst.body[0].body.body[0].argument.right = leftClone;
// Now: "1 + number". Note: loc is wrong

We have swapped:

number + 1

Into:

1 + number

Can we confirm the mapping has worked?

If we hover over the character or mapping, it will highlight the mapping and its corresponding locations in the generated and original locations.

This screenshot shows what happens when I hover over the literal number “1” character. It clearly shows there is a mapping.

This screenshot shows what happens when I hover over the variable identifier “number” word. It clearly shows there is a mapping.

SUCCESS !! 💪

What did we miss?

So what are the limitations of building a compiler like this?

Not all JavaScript statements are covered (only what our file needed)
Current it only works with 1 file. Web bundlers will follow the app building a dependency graph and applying transformations on those files (see my “under-the-hood of web bundlers” article for more on this).
Output file vs bundle. Web bundlers will produce bundles with code runnable in specific JavaScript environments, ours was very limited (again see my “under-the-hood of web bundlers” for more).
Basic transform. Performing additional optimisations would not really be easy to do without a lot of new code.

Thanks so much for reading. This topic was very far reaching and I learnt a huge amount in researching it. I really hope this serves as useful in shining a light on how JavaScript compilers and source maps work together including the mechanisms involved.

The source code for this can be found at craigtaub/our-own-babel-sourcemap.

Thanks, Craig 😃

Under-the-hood of React Hooks

Craig Taub — Mon, 20 Apr 2020 13:24:01 +0000

React is filled with interesting design patterns, when Hooks were introduced it cleaned up many of the issues people had with the more arguably frustrating features such as classes and lifecycle methods. Today we will have a look at building our own React engine with Hooks, so we can understand the mechanisms at work for useState and useEffect.

We will not be covering Fibre, reconciliation or the change detection mechanisms. Video for this post can be found here. Video for this post can be found here. A part of my "under-the-hood of" video series.

React overview

We should start with a basic bare-bones version of React. To do that we need to touch on some of the core design concepts which React follows, such as:

JSX

Elements are POJO’s (plain-old-javascript-objects)
Components are functions

Pure rendering

A instance of a render follows: Render = Component(Data)

State machine

One-directional data flow
Data change detection forces updates for all children who need it

We are going to build our own (super simple) version of React and then add Hooks, to do that we need a basic version of the React engine which should render (log) a component with some props and return the component (for interacting with later).

const React = {
  render: Component => {
    const exampleProps = {
      unit: "likes"
    };
    const compo = Component(exampleProps);
    console.log("Render: ", compo.inner);
    return compo;
  }
};

Now we have a basic engine we need an accompanying component which returns the React element (object) during the render:

const Component = props => {
  return {
    type: "div",
    inner: props.unit
  };
};

We can now use our React and Component together and see its output (below each line of code):

let App = React.render(Component); // render
// logs: render 'likes'
App = React.render(Component); // re-render
// logs: render 'likes'

So we now have a basic Component which is rendered by our React engine.

React Hooks

A brief reminder about Hooks.

"Hooks let you use state and other React features inside a pure component, without writing a class"

Classes would often confuse people and add bloat to your code, however there are other strengths to using Hooks some of which are:

Easier to build and re-use stateful logic
Easier to split components into relatable pieces -Removes confusion over the many lifecycle methods (i.e. what correlates to what event)
No fundamental changes to your React knowledge, just a more direct way to use features you already know
Easy to add types, as Hooks are just functions (unlike high-order components and most of the render props pattern)
Easy to test with "react-dom/test-utils"

So it is easy to see why Hooks are such a powerful mechanism. So let’s examine how they work and build our own.

The useState Hook

There are a couple of core concepts with useState:

Use state in pure component.
Use any primitive (string/array/object etc.)

According to the docs they always return:

a reducer state
an action dispatcher

However this can be simplified into a basic property value and a setter.
There is a simple rule which is very important to Hooks. That is that the Hooks are called at the top. That means outside of any conditionals or nesting blocks. This is crucial to the Hooks mechanism and we will examine why.

So let us expand out React engine to include the useState Hook. We will need a "state index" counter, as well as "state store" for values.

const React = {
  index: 0, // state index
  state: [], // state store
  useState: defaultProp => {
    const cachedIndex = React.index;
    if (!React.state[cachedIndex]) {
      React.state[cachedIndex] = defaultProp;
    }

    const currentState = React.state[cachedIndex];
    const currentSetter = newValue => {
      React.state[cachedIndex] = newValue;
    };
    React.index++;
    return [currentState, currentSetter];
  },
  render: Component => {
    const exampleProps = {
      unit: "likes"
    };
    const compo = Component(exampleProps);
    console.log("Render: ", compo.inner);
    React.index = 0; // reset index
    return compo;
  }
};

We have also added a useState method. It works by:

Checking if the current index has a value in the state, if not set the default
Then build the setter for the current state index value
Finally increment the index (for the next Hook) and return the setter and current value.

Now we will make use of our useState in our Component.

const Component = props => {
  const [count, setCount] = React.useState(0);
  const [name, setName] = React.useState("Steve");

  return {
    type: "div",
    inner: `${count} ${props.unit} for ${name}`,
    click: () => setCount(count + 1),
    personArrived: person => setName(person)
  };
};

See the "count" and "name" usage above. Also we have utilised both inside the "inner" property so that we can spy on it in the terminal. Additionally we have added some manual methods to update the state values. They are manual as we are not worrying about the change detection or reconciliation in this post. We will be manually triggering the returned functions as well as the render method (following how we used it in our React engine section earlier).

So on running the below, we log the rendered output. We can see with each "click() "we are updating the count, and with "personArrived()" we are updating person (terminal output below line of code).

let App = React.render(Component); // render
// render '0 likes for Steve'
App = React.render(Component); // re-render
// render '0 likes for Steve' 
App.click();
App = React.render(Component); // re-render
// render '1 likes for steve'
App.click();
App.personArrived("Peter");
App = React.render(Component); // re-render
// render '2 likes for Peter'

There is 1 main issue in our usage. That is that this would NOT work for many components at the same time. It is very tightly coupled to our single component. The state should be held in module scope or a single store namespaced to the component.

The useEffect Hook

A short quote from the docs:

"A function which runs after the initial render and after every update"

Similarly to useState, the rule about calling at the top-level applies. It is required for our implementation as well.

Couple of concepts for effects:

Created during render
Run in definition order (like useState)
Run after a given lifecycle event (first render and/or when a dependency has changed. i.e. mount and update)
Returns a function (some effects require cleaning e.g. unsubscribing)

Our useEffect Hook mechanism is below:

useEffect: (callback, dependencies) => {
  const cachedIndex = React.index;
  const hasChanged = dependencies !== React.state[cachedIndex];
  if (dependencies === undefined || hasChanged) {
    callback();
    React.state[cachedIndex] = dependencies;
  }
  React.index++;
  return () => console.log("unsubscribed effect");
},

A run-through of the code:

Cache the store index
Check if the dependency has changed in state (this is our variable tracking mechanism)
If there is no dependency given or its changed, run our effect and update store index value with our dependency value
Then increment the store index for future Hooks to use their own index
Finally return a function

You can see the way that our effect Hooks also depend on the "state index". Similarly to useState, it relies on the deterministic order of values in the state array.

All state and effect Hooks must be called in the same order, so their state index can always be found in the same location in the state array.

Now lets update our component to use the effect Hook

const Component = props => {
  const [count, setCount] = React.useState(0);
  const [name, setName]= React.useState("Steve");

  const exitThis = React.useEffect(() => {
    console.log("Effect ran");
  }, name);

  return {
    type: "div",
    inner: `${count} ${props.unit} for ${name}`,
    click: () => setCount(count + 1),
    personArrived: person => setName(person),
    unsubscribe: () => exitThis()
  };
};

The above Hook will look for changes on the "name" property, also we have exposed an "unsubscribe" function for our effect Hook.

So now onto the running order during rendering, I have logged the state array with each render to help us follow (see below screenshot for the detailed explanation).

let App = React.render(Component); // render
// state: [ 0, 'Steve' ]
// Effect ran
App = React.render(Component); // re-render
// state: [ 0, 'Steve', 'Steve' ]
// Effect does not run
App.click();
App = React.render(Component); // re-render
// state: [ 1, 'Steve', 'Steve' ]
// Effect does not run
App.click();
App.personArrived("Peter");
App = React.render(Component); // re-render
// state: [ 2, 'Peter', 'Steve' ]
// Effect ran

App.unsubscribe();
// "unsubscribed effect"

The below details what is happening above for our effect.

First render

After 2 state runs the "cachedIndex" is now 2 inside of useEffect. The state value is "undefined" as it does not exist for that index (yet). So we will run our callback and write a new entity into state (under index 2), which is our dependency value (i.e. currently "Steve").

SO: state now has local state values and effect values. It is in a deterministic order based on the “state index” (i.e. where it is called in the component). This means it is reliable as this order should not change. Remember Rule #1.

Re-renders

We will check the 3rd value in our state array and the effect will run only if it changes. See above our Hook runs again when we change the name to "Peter". Lastly we unsubscribe from our Hook.

There are 2 main issues with the above (among others):

1. Only works with 1 dependency, not an array.

It is easy to expand our code so we could use an array. By using the same store index and storing an array of dependencies on the state, not just single value. Then iterate over that dependency array to check for changes.

2. Ours is run before the render, not after

This is a more complex issue to fix and would require fundamental changes to our React engine. As this is a small POC example it is not worth fixing.

I hope this was useful or at the very least a little interesting. I very much enjoyed learning about Hooks and have a deeper appreciation for them as a feature which has helped move the front-end developer experience forward.
You can find a gist of the code here
Thanks, Craig 😃

Under-the-hood of web bundlers (e.g. Webpack)

Craig Taub — Sun, 19 Apr 2020 15:33:07 +0000

Webpack is somewhat of a black box for most developers. Tools like "create-react-app" abstract most of the bundler functionality away. I did some research into it and began building my own light-weight web bundler to understand more about what it entails.

There will be 3 parts to this article:

What is a "web bundler"
Building a compiler for a "web bundler"
Using the output with an application

A full video walkthrough for this post can be found here. A part of my "under-the-hood of" video series.

1. What is a "web bundler"

We should first ask the question "Its 2020, why bundle in the first place?". There are many answers to this question:

Performance: 3rd party code is expensive, we can use static code analysis to optimise it (things like cherry picking and tree shaking). We can also simplify what is shipped by turning 100 files into 1, limiting the data and resource expense on the user
Support: the web has so many different environments and you want your code to run in as many as possible, while only writing it once (e.g. adding Polyfills where necessary)
User experience: Utilise browser caching with separate bundles (e.g. vendor for all your libraries and app for your application itself)
Separate concerns: Manage how you serve fonts, css, images as well as JS.

The basic architecture of a web bundler is:

Basically we put modules through a compiler to produce assets.

There are many concepts involved in the compiler. It is one of the reasons why I feel it is such an interesting topic, as there is so much in such a small amount of space.

These concepts are:

IIFE
Pass by ref
Dependency graphs (as we traverse our application files)
Defining custom import/export system (which can run on any environment)
Recursive functions
AST parsing and generation (turning source code into its tokenized form)
Hashing
Native ESM (ESM manages cyclic dependencies well due to its compile-time checks)

We will be ignoring non-js assets in our compiler; so no fonts, css or images.

2. Building a compiler for a "web bundler"

This will be a massive oversimplification of how Webpack works, as there are many different ways to solve the problem, hopefully this way will offer some insight into the mechanisms involved.

The overview of a compiler is below, we will be breaking down each phase.

Our application:

Our application consists of 4 files. Its job is to get a datetime, then hand that to a logDate, whose job is to add text to the date and send it to a logger. It is very simple.

Our application tree is thus:

PHASE 1

Using a 3rd party tool for AST parsing we (see code below):

Determine files full path (very important so its clear if we are dealing with the same file again)
Grab files contents
Parse into AST
Store both contents and AST onto a "module" object.
Process the dependencies inside the contents (using the AST "ImportDeclaration" value), recursively calling this function with the value
Finally add that function to the depsArray, so we can build up our tree with the first file appearing last (this is important)

SO our tree now looks like the below right array:

PHASE 2

A compilers job is to "Execute code which will produce executable code". This means we will have 2 levels of code so we will review them 1 at a time. First we will review what the compiler builds, then review the built/outputted code (run by the browser).

First the built code

Templates:

Module template: Its job is to convert a given module into a module our compiler can use.

We hand it the module code and an index (Webpack also does this with the index).

We want the code to be as compatible in as many environments as possible. ES6 modules support strict mode natively, but ES5 modules do not so we explicitly define strict mode in our module templates.

In NodeJS all ES modules are internally wrapped in a function attaching runtime details (i.e. exports), here we are using the same. Again Webpack does this.

Runtime template: Its job is to load our modules and give a id of the starting module.

We will review this more later, once we have the modules code inside it.

Custom import/export:

With our import statement we will be replacing the instance of "importing" with our own. It will look like the middle comment.

Our export will do something similar to the import, except replace any "exports" with our own. See bottom comment.

It is worth noting Webpack stores dependency IDs on the module earlier. It has its own "dependency template" which replaces the imports and exports usage with custom variables. Mine swaps just the import itself (theirs swaps the entire line and all usages of it). One of MANY things which aren’t exactly the same as the real Webpack.

Transform

Our transform function iterates through the dependencies. Replaces each import and export it finds with our own. Then turns the AST back into source code and builds a module string. Finally we join all the module strings together and hand them into the runtime template, and give the index location of the last item in the dependency array as this is our "entry point".

Now the code outputted from the compiler:

The left hand side is our runtime, the right hand side shows all the "modules" which are loaded. You can see they are the modules we started with at the beginning.

What is going on?

The runtime template IIFE runs immediately handing the modules array as an argument. We define a cache (installedModules) and our import function (our_require). Its job is to execute the module runtime and return the exports for a given module id (the ID correlates to its location in the modules array). The exports are set on the parent module, utilising pass-by-ref, and the module is then stored in cache for easier re-use.. Finally we execute the import function for our entry point which will start the application as it does not require calling an export itself. All imports inside our modules will now utilise our custom method.

3. Using the output with an application

Now we have an updated "vendorString" we want to use it (the above code). So we:

Create a hash of the contents which is to be used in the bundle filename and stored in the manifest
Write the vendorString into our new bundle

Lastly we run a small express server application which pulls the bundle name from the manifest and exposes the built code (/build) under a /static route.

If we now run:
> npm run compile
> npm run start
Our application will run and we can see our bundle and its contents in the "network" tab.

Lastly we can confirm it worked by checking the "console". Good job 👍

Not covered

You might be wondering "so what else does Webpack do which ours does not?"

Handles non-js assets (css/images/fonts)
Dev and HMR: this is built into Webpack
Chunks: Webpack can put different modules into different chunks, and each can have a slightly different runtime and polyfills if necessary. i.e. vendor, dynamic imports
Multiple exports: Ours could do this but needs a defensive check on the module type so its not worth it for this mess.
Further optimisations (e.g. minification/code splitting/cherry picking/tree shaking/polyfills)
Source maps: Webpack uses a mix of preprocessor which all generate their own maps. Webpack manages merging them all together.
Making it extensible or configurable (e.g. loaders, plugins or lifecycle). Webpack is 80% plugins even internally i.e. the compiler fires hooks on lifecycle events (e.g. "pre-process file") and the loaders listen out for this event and run when appropriate. Additionally we could extend our compiler to support lifecycle events, perhaps using NodeJS event emitter, but again not worth it for this mess.

Thats it

I hope this was useful to you as I certainly learnt a lot from my time on it. There is a repository for anyone interested found at craigtaub/our-own-webpack
Thanks, Craig 😃