31 Jan 2021, 21:28

Measuring the World with JavaScript

If I asked you to measure two points on a table, you might get out a ruler or a tape measure to tell me the distance between the two. However, what if I asked you to measure the points between two capital cities? Suddenly it becomes more complicated, not only just logistically but also in terms of assumptions we have to make about that measurement.

One big change, apart from just scale, is that we now have to account for the roundness of the world. Thankfully mathematicians who were far smarter than me have come up with formulas that can account for this in various ways. One such formula is the haversine formula. This is credited as far back as 1801 to Spanish astronomer and mathematician José de Mendoza y Ríos.

The Haversine formula is useful in a lot of spherical trigonometry problems, as it allows a person to determine what is called a great-circle distance between two given points on a sphere. In particular relevance to what we are looking at today, it is useful for determining the approximate distance between two latitude and longitudes on the globe.

When it comes to translating this to code Chris Veness, a UK based programmer has written a healthy amount of code in the space - a lot of it is featured in the popular geospatial library Turf.js. Here’s a stand-alone adaptation of some of his code for the Haversine formula, written in TypeScript:

export function haversineDistance(
  pointOne: { lng: number; lat: number },
  pointTwo: { lng: number; lat: number }
) {
  const toRadians = (latOrLng: number) => (latOrLng * Math.PI) / 180;

  const phiOne = toRadians(pointOne.lat);
  const lambdaOne = toRadians(pointOne.lng);
  const phiTwo = toRadians(pointTwo.lat);
  const lambdaTwo = toRadians(pointTwo.lng);
  const deltaPhi = phiTwo - phiOne;
  const deltalambda = lambdaTwo - lambdaOne;

  const a =
    Math.sin(deltaPhi / 2) * Math.sin(deltaPhi / 2) +
    Math.cos(phiOne) *
      Math.cos(phiTwo) *
      Math.sin(deltalambda / 2) *
      Math.sin(deltalambda / 2);
  const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

  const radius = 6371e3;
  const distance = radius * c;

  return distance;
}

The Haversine formula suffers from one core problem, which is that it assumes that the world is round. Unfortunately for us, the world is not actually round, it’s closer to what we’d determine as an oblate spheroid; a sphere that is flattened at the poles. As the Haversine makes this assumption, it cannot be guaranteed correct to provide results with better than 0.5% accuracy.

This is where another formula comes in, Vincenty’s inverse formula. The formula comes from Thaddeus Vincenty, a Polish American geodesist who was with the U.S. Air Force. Vincenty’s inverse formula works with the idea that the Earth is an oblate-spheroid. This approach is more complex and is also iteration based, unlike the haversine formula.

Again, I’ve taken some of Chris’s code and made it standalone (you can just copy and paste this function). It works on the WGS84 ellipsoid, as this is probably the most common use case. Lets take a look at the code, again in TypeScript:

export function inverseVincentyDistance(
  pointOne: { lng: number; lat: number },
  pointTwo: { lng: number; lat: number }
): number {
  const toRadians = (latOrLng: number) => (latOrLng * Math.PI) / 180;

  const phiOne = toRadians(pointOne.lat);
  const lambda1 = toRadians(pointOne.lng);
  const phiTwo = toRadians(pointTwo.lat);
  const lambda2 = toRadians(pointTwo.lng);

  const wgs84ellipsoid = {
    a: 6378137,
    b: 6356752.314245,
    f: 1 / 298.257223563,
  };
  const { a, b, f } = wgs84ellipsoid;

  const L = lambda2 - lambda1; // L = difference in longitude, U = reduced latitude, defined by tan U = (1-f)·tanphi.
  const tanU1 = (1 - f) * Math.tan(phiOne),
    cosU1 = 1 / Math.sqrt(1 + tanU1 * tanU1),
    sinU1 = tanU1 * cosU1;
  const tanU2 = (1 - f) * Math.tan(phiTwo),
    cosU2 = 1 / Math.sqrt(1 + tanU2 * tanU2),
    sinU2 = tanU2 * cosU2;

  const antipodal =
    Math.abs(L) > Math.PI / 2 || Math.abs(phiTwo - phiOne) > Math.PI / 2;

  let lambda = L,
    sinLambda = null,
    cosLambda = null; // lambda = difference in longitude on an auxiliary sphere
  let sigma = antipodal ? Math.PI : 0,
    sinSigma = 0,
    cosSigma = antipodal ? -1 : 1,
    sinSqsigma = null; // sigma = angular distance P₁ P₂ on the sphere
  let cos2sigmaM = 1; // sigmaM = angular distance on the sphere from the equator to the midpoint of the line
  let sinalpha = null,
    cosSqAlpha = 1; // alpha = azimuth of the geodesic at the equator
  let C = null;

  let lambdaʹ = null,
    iterations = 0;
  do {
    sinLambda = Math.sin(lambda);
    cosLambda = Math.cos(lambda);
    sinSqsigma =
      cosU2 * sinLambda * (cosU2 * sinLambda) +
      (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda) *
        (cosU1 * sinU2 - sinU1 * cosU2 * cosLambda);

    if (Math.abs(sinSqsigma) < Number.EPSILON) {
      break; // co-incident/antipodal points (falls back on lambda/sigma = L)
    }

    sinSigma = Math.sqrt(sinSqsigma);
    cosSigma = sinU1 * sinU2 + cosU1 * cosU2 * cosLambda;
    sigma = Math.atan2(sinSigma, cosSigma);
    sinalpha = (cosU1 * cosU2 * sinLambda) / sinSigma;
    cosSqAlpha = 1 - sinalpha * sinalpha;
    cos2sigmaM =
      cosSqAlpha != 0 ? cosSigma - (2 * sinU1 * sinU2) / cosSqAlpha : 0; // on equatorial line cos²alpha = 0 (§6)
    C = (f / 16) * cosSqAlpha * (4 + f * (4 - 3 * cosSqAlpha));
    lambdaʹ = lambda;
    lambda =
      L +
      (1 - C) *
        f *
        sinalpha *
        (sigma +
          C *
            sinSigma *
            (cos2sigmaM + C * cosSigma * (-1 + 2 * cos2sigmaM * cos2sigmaM)));
    const iterationCheck = antipodal
      ? Math.abs(lambda) - Math.PI
      : Math.abs(lambda);
    if (iterationCheck > Math.PI) {
      throw new Error("lambda > Math.PI");
    }
  } while (Math.abs(lambda - lambdaʹ) > 1e-12 && ++iterations < 1000);
  if (iterations >= 1000) {
    throw new Error("Vincenty formula failed to converge");
  }

  const uSq = (cosSqAlpha * (a * a - b * b)) / (b * b);
  const A = 1 + (uSq / 16384) * (4096 + uSq * (-768 + uSq * (320 - 175 * uSq)));
  const B = (uSq / 1024) * (256 + uSq * (-128 + uSq * (74 - 47 * uSq)));
  const deltaSigma =
    B *
    sinSigma *
    (cos2sigmaM +
      (B / 4) *
        (cosSigma * (-1 + 2 * cos2sigmaM * cos2sigmaM) -
          (B / 6) *
            cos2sigmaM *
            (-3 + 4 * sinSigma * sinSigma) *
            (-3 + 4 * cos2sigmaM * cos2sigmaM)));

  const distance = b * A * (sigma - deltaSigma); // distance = length of the geodesic

  return distance;
}

I’ll be honest, Vincenty’s formula is a bit lost on me, but it promises to provide more accurate results! In fact, its use is very common in geodesy because the expected accuracy is to 0.5mm on the Earth ellipsoid. Pretty cool right? The one downside is that it is computationally slower due to the increased number of operations and the iterative approach.

Hopefully, you’ve enjoyed this short blog post about how to measure distances on the Earth with JavaScript (…okay TypeScript). Let me know if you would be interested in follow-ups on similar topics!

25 Dec 2020, 18:28

Experimenting Producing AVIF Images with Node.js

I’ve wanted to experiment with writing shorter and easier to digest blog posts on interesting web topics. So, this is my first exploring the AVIF Image format!

AV1 Image File Format or AVIF is an exciting new image format that can work with the web. It has been developed by the Alliance for Open Media aiming to be an open-source and royalty-free image format. It already has adopters some big-name adopters like Netflix, which is interesting to see.

I got excited about the possibilities for the new format and had a little gander at some of the analysis by some people much smarter than me to see what the deal was. The first post I looked at was AVIF vs WebP by Daniel Aleksandersen, which found against a baseline of JPEG there was a median file size reduction of 50.3% compared to WebP’s 31.5% reduction. Similarly, Jake Archibald did a nice comparison for a photo of an F1 car where WebP came in 57.7% of the size, and AVIF an impressive 18.2% of the size.

I was intrigued myself and saw that Sharp recently merged AVIF support in their Node.js library so I decided to have a little experiment with the new format.

It’s important to state here this specific blog post is not about comparing file sizes or perceived quality of output, as that is a fairly exact art and you can read all about the pitfalls of attempting that in this great post by Kornel Lesiński. Rather, this post is more about how you can create an AVIF image using Node.js today.

To start with I found this nice high-resolution image of Saturn on Wikipedia and thought I’d use it myself as a test image.

After this I went ahead and created a new Node.js project:

mkdir avif-sharp
cd avif-sharp
npm init
npm install sharp

I then wrote a little code snippet that exports a WebP image and another in the new AVIF format:

const sharp = require("sharp");
const fs = require("fs");

fs.readFile("saturn-original.jpeg", (err, inputBuffer) => {
  if (err) {
    console.error(err);
    return;
  }

  // JPEG
  console.time("jpeg");
  sharp(inputBuffer)
    .jpeg({ quality: 50, speed: 1 })
    .toFile("saturn.jpeg", (err, info) => {
      console.timeEnd("jpeg");
      console.log("jpeg", info);
    });

  // WebP
  console.time("webp");
  sharp(inputBuffer)
    .webp({ quality: 50, speed: 1 })
    .toFile("saturn.webp", (err, info) => {
      console.timeEnd("webp");
      console.log("avif", info);
    });

  // AVIF
  console.time("avif");
  sharp(inputBuffer)
    .avif({ quality: 50, speed: 1 })
    .toFile("saturn.avif", (err, info) => {
      console.timeEnd("avif");
      console.log("avif", info);
    });
});

The code uses console.time and console.timeEnd to get logs on how long these processes took. Running the code created three files, one saturn.jpeg, one saturn.webp and one saturn.avif as anticipated. You can find the full API docs for AVIF in Sharp here if you want to play with the configuration options.

Results

On my reasonably well-specced work machine, it took 287ms to output the compressed JPEG, 1288ms to output the WebP image and 22508ms to produce the AVIF image. Again it’s important to note here that quality: 50 and speed: 1 are not an absolute and comparable parameters here so try not to read into them.

With regards to size, at these settings for the AVIF image was 43.7kb compared to WebP which was 149kb, so approximately 29.32% of the size of the WebP image. Compared to the compressed JPEG the AVIF image was 13.35% of the size.

As I mentioned, take these results with a pinch of salt and I’d defer to Daniel Aleksandersen’s analysis of images at the same DSSIM and also take a look at BunnyCDNs take on the format for a more qualitative take.

I hope this shorter format still sits well, and that the blog post has shown you how you can create AVIF images using Sharp. Till next time!

16 Aug 2020, 18:28

Getting Started With Handling TypeScript ASTs

TypeScript provides a language which builds on top of JavaScript adding static types to help determine type mismatches at compile time (and even whilst you write!). This is useful from a developmental perspective as (without wanting to dive into the dynamic vs static typing) it makes it easier to reason about the data flowing through your programs, documenting the shape of data at each stage.

TypeScript is powerful in that it has a solid level of inference, which means you don’t need to strictly type every variable. For variable assignment it will take what’s called a best common type; this means if your provide an integer or float, it will infer a number type, but also if you have an array with multiple types it will type the variable as an array with those possible types (i.e. let arr = ["1", 2, null] would type to (string | number | null)[]). Along with side this, it also provides what you could call the ‘inverse’ of this; contextual typing. Contextual typing means that the type can be implied by the location and usage. For example, when you assign a function to environment callbacks like window.onmousemove in the browser, TypeScript can imply the parameter type of the function is of type MouseEvent because it knows onmousemove takes a function with this as its first parameter (the type is inferred from the hand side of the assignment).

When the TypeScript compiler compiles your code, it creates an Abstract Syntax Tree (AST) of it. Essentially, an AST can be thought of as a tree representation of the syntax of your source code, with each node being a data structure representing a construct in the relating source code. The tree is complete with nodes of all the elements of the source code.

For example, if we took the simple TypeScript program:

console.log("hello world");

We would end up with an AST structure that could be represented textually in this form:

SourceFile
  ExpressionStatement
    CallExpression
      PropertyAccessExpression
        Identifier
        Identifier
      StringLiteral
  EndOfFileToken

Here, SourceFile represents the file itself, we then have two child nodes; a parent ExpressionStatement (console.log("hello world");) and the EndOfFileToken, representing the end of the file. The ExpressionStatement comprises of one CallExpression, which has one PropertyAccessExpression composed of two Identifiers console and it’s property log. We also have the StringLiteral in the call expression which is, in this case, "hello world".

Each of these items in our tree is an AST node, which can be traversed and has a series of metadata attached to it. This data can be useful or interesting to us as developers. As an elementary example, we can determine the kind of the node; in TypeScript this is represented as an enum called SyntaxKind. To demonstrate, we can say that the value 243 is equal to FunctionDeclaration in the SyntaxKind enum. This scratches simple use scratches the surface what we can do, however, and as we go deeper into this blog post you’ll see the types of things we can do with the TypeScript AST.

To get more specific here are some ideas of things you could do by traversing and manipulating ASTs:

  • Write documentation in markdown or HTML for your TypeScript code
  • Edit code programmatically by using the manipulation features
  • Automatically update code between new versions of a library or framework
  • Write new code, leveraging something like code-block-writer
  • Write types for the return payloads of your APIs for your frontend code
  • Write a custom linter for your TypeScript code

Now, lets first dive into how we can explore ASTs using the TypeScript compiler API.

Making sense of TypeScript’s AST

The typescript package provides a compiler API, which allows you to access to the AST nodes. In theory, if we wanted to print the above AST we could do so using the typescript module itself like so:

import * as ts from 'typescript';

const code = "console.log('hello world')";

const sourceFile = ts.createSourceFile('temp.ts', code);
let indent = 0;

function printTree(node) {
    console.log(new Array(indent + 1).join(' ') + ts.SyntaxKind[node.kind]);
    indent++;
    ts.forEachChild(node, printTree);
    indent--;
}
printTree(sourceFile);

Here we can see us creating a temporary sourcefile in memory using the code string, then traversing down the tree to print out its children type. This will print out the tree depicted above. Let’s take this a small step further and use the node APIs to only log out the programs syntactic elements when it’s a string literal:

import * as ts from 'typescript';

const code = "console.log('hello world')";

const sourceFile = ts.createSourceFile('temp.ts', code);

function printTree(node) {
    if (ts.isStringLiteral(node)) {
        console.log("Text:", node.getFullText());
    }
    ts.forEachChild(node, printTree);
}
printTree(sourceFile);

This program would log out hello world, as it ignores any node that isn’t a string literal.

This is perhaps one of the most rudimentary things we could do with the compiler API, but there’s a whole host of use cases and more detailed dives into the TypeScript Compiler API in the TypeScript GitHub documentation.

Introducing ts-morph

Some might argue that the TypeScript compiler API can be slightly cumbersome to work with. ts-morph is a package that wraps around the compiler API to provide a smoother and easier way to deal with the TypeScript code.

Let’s rewrite the first program we took from using the TypeScript compiler API:

import { Project } from "ts-morph";

const project = new Project();
const code = "console.log('hello world')";
const sourceFile = project.createSourceFile("temp.ts", code);

let indent = 0;

function printTree(node) {
    console.log(new Array(indent + 1).join(' ') + node.getKindName());
    indent++;
    node.forEachChild(printTree);
    indent--;
}
printTree(sourceFile);

The main difference here is that instead of using methods on the ts module, ts-morph creates an object that has those methods attached to the nodes. As such we could turn the second program into:

import { Project } from "ts-morph";

const project = new Project();
const code = "console.log('hello world')";
const sourceFile = project.createSourceFile("temp.ts", code);

function printTree(node: SourceFile) {
    if (node.getKindName() === 'StringLiteral') {
        console.log("Text:", node.getFullText());
    }
    node.forEachChild(printTree);
}
printTree(sourceFile);

Putting ts-morph to work

Taking ts-morph a bit further we can relatively straightforwardly go about doing more interesting things. Say we wanted to get the names of all the classes that contained a certain property name in a file, we could write a function that does that like so that:

const findClassesWithPropertyName = (sourceFile: SourceFile, name: string) => {

    const classes = sourceFile.getClasses();
    const classesWithProperty: ClassDeclaration[] = [];

    for (let i = 0; i > classes.length; i++) {
        const tsClass = classes[i];
        const matches = tsClass.getProperties().map((p) => p.getName()).includes(name)
        if (matches) {
            classesWithProperty.push(tsClass);
        }
    }

    return classesWithProperty;

} 

Let’s think of another example program; in this case, we are interested in determining the depth of the deepest nested function within a source code file which contains top-level functions. We could achieve this using something like the following code:

const getDeepestFunction = (sourceFile: Node | SourceFile) => {
    let deepest = 0;

    const stack: Node[] = [sourceFile.getFirstChildByKind(ts.SyntaxKind.SyntaxList)];
    const parentNodes = [...stack[0].getChildren()]

    let depth = 0;

    while (stack.length) {
        const node = stack.pop();
        const kind = node.getKindName();

        if (parentNodes.indexOf(node) !== -1) {
            depth = 0;
        }
        
        if ((kind === 'FunctionDeclaration' || kind === 'ArrowFunction') ) {
            depth++
            if (depth > deepest) {
                deepest = depth;
            }
        }
        stack.push(...node.getChildren());
    }

    return deepest;
} 

Here you can see we create a stack and iterate through the child nodes, adding depth every time we encounter a function declaration or an ES6 arrow function. We reset if we are in one of the top-level parent nodes.

Replacing and updating AST nodes

Lastly, I want to demonstrate how you could rewrite your codes AST using ts-morph (although the behaviour is basically identical for the core typescript library). Let’s say we have a code snippet that converts 10000000000 bytes to kilobytes, megabytes and gigabytes. However we notice that the conversion is off by one!:

const totalSize = 10000000000;
const totalSizeKB = totalSize / Math.pow(1024,2);
const totalSizeMB = totalSize / Math.pow(1024,3);
const totalSizeGB = totalSize / Math.pow(1024,4);

This is of course slightly contrived and we could certainly fix this issue manually, but it’s useful to demonstrate how we can start doing code transforms and updating our code programmatically. We could write a function that changes the powers from 2, 3 and 4 to be 1, 2 and 3 respectively:

const rewriteMemoryPowers = (sourceFile: SourceFile) => {
    return sourceFile.transform(traversal => { 
        const node = traversal.visitChildren(); // Here travseral visits children in postorder
        if (ts.isNumericLiteral(node) && node.getText().length === 1) {
            return ts.createNumericLiteral(String(parseInt(node.getText()) - 1));
        }
        return node;
    });
};

Here we use the transform method which returns a TransformTraversalControl. This, in turn, allows us to traverse down the AST and replace and update node; we call visitChildren to make sure we traverse down the child nodes (here ‘traversal’ also has a currentNode property if you are not interested in the node’s children).

The program goes through each node and its children, determines if it is a numeric literal, and if it is and has a length of 1 (e.g. 2, 3, 4) then we decrement it by one and create a new numeric literal in its place. That should fix our issue! Arguably the way this is coded isn’t super robust, but the aim here is to demonstrate how you can use the transform method to recurse down the AST tree and update the behaviour of the program by changing its nodes.

Saving and emitting to disk

If you made transforms to your code, or you’re interested in converting them to JavaScript, saving and emitting will be useful features. Thankfully with ts-morph, this is reasonably straightforward. In our previous example, if we wanted to save the file to disk, we could do something like so:

const sourceFile = project.createSourceFile("conversion.ts", code);
rewriteMemoryPowers(sourceFile).saveSync();

Here we use saveSync, but you can use save if you would like that to be asynchronous. On a similar note, assuming we wanted to emit the compiled JavaScript file, we could do:

const sourceFile = project.createSourceFile("conversion.ts", code);
rewriteMemoryPowers(sourceFile).emitSync();

This will write a conversion.js file to disk. Here we have been using in-memory files up until the point we save them, but we can also read files from disk, and even whole directories if we so wish. See the ts-morph docs on navigation and directories.

Conclusion

Hopefully, this blog post has shown you how you can get started with exploring TypeScript ASTs and how you can manipulate their data structures in useful ways.

An aim here was that the ideas at the beginning of this post give some inspiration for what might be possible. If there is interest I can look into exploring one of these examples in a further blog post.