Shift AST

... and the Shift family of tools

What is the Shift AST?

  • Represents the structure of an ECMAScript program as a tree
  • Easily transformed to create new programs or analysed to create reports or inform other computations

Why is it relevant to you?

  • ECMAScript ASTs are used in the vast majority of language tooling: linters, compilers, minifiers, refactoring tools, IDEs, etc.
  • Nearly eliminates the chance of accidentally creating an AST that does not represent an ECMAScript program

Use Cases

Transformation

Allowing for convenient, error-free transformation was the highest priority in the design of the Shift AST format. This has been achieved through a number of means, some of which are illustrated below. The following program is represented in both the Shift AST (left) and an alternative representation, ESTree, formerly known as the SpiderMonkey AST (right). 

var x; for(var y;;);
{"type":"Script","directives":[],"statements":[{"type":"VariableDeclarationStatement","declaration":{"type":"VariableDeclaration","kind":"var","declarators":[{"type":"VariableDeclarator","binding":{"type":"BindingIdentifier","name":"x"},"init":null}]}},{"type":"ForStatement","init":{"type":"VariableDeclaration","kind":"var","declarators":[{"type":"VariableDeclarator","binding":{"type":"BindingIdentifier","name":"y"},"init":null}]},"test":null,"update":null,"body":{"type":"EmptyStatement"}}]}
Shift
{"type":"Program","body":[{"type":"VariableDeclaration","declarations":[{"type":"VariableDeclarator","id":{"type":"Identifier","name":"x"},"init":null}],"kind":"var"},{"type":"ForStatement","init":{"type":"VariableDeclaration","declarations":[{"type":"VariableDeclarator","id":{"type":"Identifier","name":"y"},"init":null}],"kind":"var"},"test":null,"update":null,"body":{"type":"EmptyStatement"}}]}
ESTree

Using the ESTree format, a user that is only considering programs that contain variable declarations in statement position may write a naïve transformation that replaces all variable declarations with while statements. But the same user using the Shift AST format knows that all statement nodes may be replaced by other statement nodes, and would apply the transformation to the VariableDeclarationStatement node instead.

This is a single, simple example of the benefits reaped from using an AST format that was specifically designed with transformation in mind. For other examples, see the Shape Security blog post, A Technical Comparison of the Shift and SpiderMonkey AST Formats.

Analysis

Program analysis using the Shift AST is easy due to the large variety of node types that help reduce the necessary amount of context during analysis.

As a case study, consider the implementation of the id-length linting rule in eslint, which allows a user to enforce a minimum or maximum length for identifiers. Because eslint uses the ESTree representation internally, this rule has to do a surprising amount of work keeping track of context while linting to ensure that labels, object property names, and static member accesses do not get misinterpreted as identifiers. This difficulty originates from the use of a generic Identifier node in ESTree, which is used in all of these contexts and more. Using the Shift AST, a linting rule like this would be trivial: assert that the name of each VariableReference node is within the given bounds.

Support

ES2015 (ES6) ES2016 ES2017 ES2018 ES2019
AST Specification Legacy Legacy Legacy Legacy Complete
Parser JS + Java JS + Java JS + Java JS + Java JS
Code Generator JS + Java JS + Java JS + Java JS + Java JS
Scope Analyser JS + Java JS + Java JS + Java JS + Java JS
Reducer JS + Java JS + Java JS + Java JS + Java JS
Fuzzer Java JS + Java JS + Java JS + Java JS
Validator JS + Java JS + Java JS + Java JS + Java JS
ESTree Converter JS — — — —
Shift Template — JS + Java JS + Java Java —
Regexp Acceptor — JS — JS JS
AST Constructors JS + Java JS + Java JS + Java JS + Java JS
Spec Representation JS JS JS JS JS

Note that older versions of the Shift specification and many of the Shift tools (back to ES5) are available but not listed here.

© Shape Security, Inc.