Notorious Penguin Magicians

    abstract-syntax-tree

    2.20.5 • Public • Published

    abstract-syntax-tree

    npm build

    A library for working with abstract syntax trees.

    Table of Contents

    Background

    An abstract syntax tree is a way to represent the source code. In case of this library it is represented in the estree format.

    For example, the following source code:

    const answer = 42

    Has the following representation:

    {
      "type": "Program",
      "body": [
        {
          "type": "VariableDeclaration",
          "declarations": [
            {
              "type": "VariableDeclarator",
              "id": {
                "type": "Identifier",
                "name": "answer"
              },
              "init": {
                "type": "Literal",
                "value": 42
              }
            }
          ],
          "kind": "const"
        }
      ]
    }

    The goal of this library is to consolidate common abstract syntax tree operations in one place. It uses a variety of libriaries under the hood based on their performance and flexibility, e.g. meriyah for parsing and astring for source code generation.

    The library exposes a set of utility methods that can be useful for analysis or transformation of abstract syntax trees. It supports functional and object-oriented programming style.

    Install

    npm install abstract-syntax-tree

    Usage

    const { parse, find } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(find(tree, 'Literal')) // [ { type: 'Literal', value: 42 } ]
    const AbstractSyntaxTree = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = new AbstractSyntaxTree(source)
    console.log(tree.find('Literal')) // [ { type: 'Literal', value: 42 } ]

    API

    Static Methods

    parse

    The library uses meriyah to create an estree compatible abstract syntax tree. All meriyah parsing options can be passed to the parse method.

    const { parse } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(tree) // { type: 'Program', body: [ ... ] }
    const { parse } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source, {
      loc: true,
      ranges: true
    })
    console.log(tree) // { type: 'Program', body: [ ... ], loc: {...} }

    generate

    The library uses astring to generate the source code. All astring generate options can be passed to the generate method.

    const { parse, generate } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(generate(tree)) // 'const answer = 42;'

    walk

    Walk method is a thin layer over estraverse.

    const { parse, walk } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    walk(tree, (node, parent) => {
      console.log(node)
      console.log(parent)
    })

    find

    Find supports two traversal methods. You can pass a string selector or pass an object that will be compared to every node in the tree. The method returns an array of nodes.

    The following selectors are supported:

    • node type (Identifier)
    • node attribute ([name="foo"])
    • node attribute existence ([name])
    • wildcard (*)
    const { parse, find } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(find(tree, 'VariableDeclaration')) // [ { type: 'VariableDeclaration', ... } ]
    console.log(find(tree, { type: 'VariableDeclaration' })) // [ { type: 'VariableDeclaration', ... } ]

    serialize

    Serialize can transform nodes into values. Works for: Array, Boolean, Error, Infinity, Map, NaN, Number, Object, RegExp, Set, String, Symbol, WeakMap, WeakSet, null and undefined.

    const { serialize } = require('abstract-syntax-tree')
    const node = {
      type: 'ArrayExpression',
      elements: [
        { type: 'Literal', value: 1 },
        { type: 'Literal', value: 2 },
        { type: 'Literal', value: 3 },
        { type: 'Literal', value: 4 },
        { type: 'Literal', value: 5 }
      ]
    }
    const array = serialize(node) // [1, 2, 3, 4, 5]

    traverse

    Traverse method accepts a configuration object with enter and leave callbacks. It allows multiple transformations in one traversal.

    const { parse, traverse } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    traverse(tree, {
      enter (node) {},
      leave (node) {}
    })

    replace

    Replace extends estraverse by handling replacement of give node with multiple nodes. It will also remove given node if null is returned.

    const { parse, replace } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    replace(tree, node => {
      if (node.type === 'VariableDeclaration') {
        node.kind = 'let'
      }
      return node
    })

    remove

    Remove uses estraverse and ensures that no useless nodes are left in the tree. It accepts a string, object or callback as the matching strategy.

    const { parse, remove, generate } = require('abstract-syntax-tree')
    const source = '"use strict"; const b = 4;'
    const tree = parse(source)
    remove(tree, 'Literal[value="use strict"]')
    
    // or
    // remove(tree, { type: 'Literal', value: 'use strict' })
    
    // or
    // remove(tree, (node) => {
    //   if (node.type === 'Literal' && node.value === 'use strict') return null
    //   return node
    // })
    
    console.log(generate(tree)) // 'const b = 4;'

    each

    const { parse, each } = require('abstract-syntax-tree')
    const source = 'const foo = 1; const bar = 2;'
    const tree = parse(source)
    each(tree, 'VariableDeclaration', node => {
      console.log(node)
    })

    first

    const { parse, first } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(first(tree, 'VariableDeclaration')) // { type: 'VariableDeclaration', ... }

    last

    const { parse, last } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(last(tree, 'VariableDeclaration')) // { type: 'VariableDeclaration', ... }

    reduce

    const { parse, reduce } = require('abstract-syntax-tree')
    const source = 'const a = 1, b = 2'
    const tree = parse(source)
    const value = reduce(tree, (sum, node) => {
      if (node.type === 'Literal') {
        sum += node.value
      }
      return sum
    }, 0)
    console.log(value) // 3

    has

    const { parse, has } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(has(tree, 'VariableDeclaration')) // true
    console.log(has(tree, { type: 'VariableDeclaration' })) // true

    count

    const { parse, count } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    console.log(count(tree, 'VariableDeclaration')) // 1
    console.log(count(tree, { type: 'VariableDeclaration' })) // 1

    append

    Append pushes nodes to the body of the abstract syntax tree. It accepts estree nodes as input.

    const { parse, append } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    append(tree, {
      type: 'ExpressionStatement',
      expression:  {
        type: "CallExpression",
        callee: {
          type: 'MemberExpression',
          object: {
            type: 'Identifier',
            name: 'console'
          },
          property: {
            type: 'Identifier',
            name: 'log'
          },
          computed: false
        },
        arguments: [
          {
            type: 'Identifier',
            name: 'answer'
          }
        ]
      }
    })

    Strings will be converted into abstract syntax tree under the hood. Please note that this approach might make the code run a bit slower due to an extra interpretation step.

    const { parse, append } = require('abstract-syntax-tree')
    const source = 'const answer = 42'
    const tree = parse(source)
    append(tree, 'console.log(answer)')

    prepend

    Prepend unshifts nodes to the body of the abstract syntax tree. Accepts estree nodes or strings as input, same as append.

    const { parse, prepend } = require('abstract-syntax-tree')
    const source = 'const a = 1;'
    const tree = parse(source)
    prepend(tree, {
      type: 'ExpressionStatement',
      expression: {
        type: 'Literal',
        value: 'use strict'
      }
    })

    equal

    const { equal } = require('abstract-syntax-tree')
    console.log(equal({ type: 'Literal', value: 42 }, { type: 'Literal', value: 42 })) // true
    console.log(equal({ type: 'Literal', value: 41 }, { type: 'Literal', value: 42 })) // false

    match

    const { match } = require('abstract-syntax-tree')
    console.log(match({ type: 'Literal', value: 42 }, 'Literal[value=42]')) // true
    console.log(match({ type: 'Literal', value: 41 }, 'Literal[value=42]')) // false

    template

    The function converts the input to an equivalent abstract syntax tree representation.

    const { template } = require('abstract-syntax-tree')
    const literal = template(42)
    const nodes = template('const foo = <%= bar %>;', { bar: { type: 'Literal', value: 1 } })
    const { template } = require('abstract-syntax-tree')
    const nodes = template('function foo(%= bar %) {}', {
      bar: [
        { type: 'Identifier', name: 'baz' },
        { type: 'Identifier', name: 'qux' }
      ]
    })

    program

    Creates an abstract syntax tree with a blank program.

    const { program } = require('abstract-syntax-tree')
    const tree = program() // { type: 'Program', sourceType: 'module', body: [] }

    iife

    Creates an abstract syntax tree for an immediately invoked function expression.

    const { iife } = require('abstract-syntax-tree')
    const node = iife() // { type: 'ExpressionStatement', expression: { ... } }

    Instance Methods

    Almost all of the static methods (excluding parse, generate, template and match) have their instance equivalents. There are few extra instance methods:

    mark

    const AbstractSyntaxTree = require('abstract-syntax-tree')
    const tree = new AbstractSyntaxTree('const a = 1')
    tree.mark()
    console.log(tree.first('Program').cid) // 1
    console.log(tree.first('VariableDeclaration').cid) // 2

    wrap

    const AbstractSyntaxTree = require('abstract-syntax-tree')
    const source = 'const a = 1'
    const tree = new AbstractSyntaxTree(source)
    tree.wrap(body => {
        return [
          {
            type: 'ExpressionStatement',
            expression: {
              type: 'CallExpression',
              callee: {
                type: 'FunctionExpression',
                params: [],
                body: {
                  type: 'BlockStatement',
                  body
                }
              },
              arguments: []
            }
          }
        ]
    })

    unwrap

    const AbstractSyntaxTree = require('abstract-syntax-tree')
    const source = '(function () { console.log(1); }())'
    const tree = new AbstractSyntaxTree(source)
    tree.unwrap()
    console.log(tree.source) // console.log(1);

    Getters

    body

    Gives the body of the root node.

    source

    Gives access to the source code representation of the abstract syntax tree.

    const AbstractSyntaxTree = require('abstract-syntax-tree')
    const source = 'const foo = "bar";'
    const tree = new AbstractSyntaxTree(source)
    console.log(tree.source) // const foo = "bar";

    map

    Gives the source map of the source code.

    Setters

    body

    Sets the body of the root node.

    Transformations

    toBinaryExpression

    const { toBinaryExpression } = require('abstract-syntax-tree')
    const expression = {
      type: 'ArrayExpression',
      elements: [
        { type: 'Literal', value: 'foo' },
        { type: 'Literal', value: 'bar' },
        { type: 'Literal', value: 'baz' }
      ]
    }
    console.log(toBinaryExpression(expression)) // { type: 'BinaryExpression', ... }

    Nodes

    You can also use classes to create nodes.

    const { ArrayExpression, Literal } = require('abstract-syntax-tree')
    const expression = new ArrayExpression([
      new Literal('foo'),
      new Literal('bar'),
      new Literal('baz')
    ])

    Here's a list of all available nodes, with examples.

    Type Example
    ArrayExpression const foo = []
    ArrayPattern const [foo, bar] = bar
    ArrowFunctionExpression (() => {})
    AssignmentExpression foo = bar
    AssignmentOperator
    AssignmentPattern function foo(bar = baz) {}
    AwaitExpression (async () => { await foo() })()
    BigIntLiteral const foo = 9007199254740991n
    BinaryExpression foo + bar
    BinaryOperator
    BlockStatement { console.log(foo) }
    BreakStatement for (foo in bar) break
    CallExpression foo()
    CatchClause try {} catch (error) {}
    ChainElement
    ChainExpression foo?.()
    Class
    ClassBody class Foo {}
    ClassDeclaration class Foo {}
    ClassExpression (class {})
    ConditionalExpression foo ? bar : baz
    ContinueStatement while(true) { continue }
    DebuggerStatement debugger
    Declaration
    Directive
    DoWhileStatement do {} while (true) {}
    EmptyStatement ;
    ExportAllDeclaration export * from "foo"
    ExportDefaultDeclaration export default foo
    ExportNamedDeclaration export { foo as bar }
    ExportSpecifier export { foo }
    Expression
    ExpressionStatement foo
    ForInStatement for (foo in bar) {}
    ForOfStatement for (foo of bar) {}
    ForStatement for (let i = 0; i < 10; i ++) {}
    Function
    FunctionBody
    FunctionDeclaration function foo () {}
    FunctionExpression (function () {})
    Identifier foo
    IfStatement if (foo) {}
    ImportDeclaration import "foo"
    ImportDefaultSpecifier import foo from "bar"
    ImportExpression import(foo).then(bar)
    ImportNamespaceSpecifier import * as foo from "bar"
    ImportSpecifier import { foo } from "bar"
    LabeledStatement label: foo
    Literal 42
    LogicalExpression true && false
    LogicalOperator
    MemberExpression foo.bar
    MetaProperty function foo () { new.target }
    MethodDefinition class Foo { bar() {} }
    ModuleDeclaration
    ModuleSpecifier
    NewExpression new Foo()
    Node
    ObjectExpression ({})
    ObjectPattern function foo ({}) {}
    Pattern
    Position
    Program 42
    Property
    RegExpLiteral
    RestElement function foo (...bar) {}
    ReturnStatement function foo () { return bar }
    SequenceExpression foo, bar
    SourceLocation
    SpreadElement
    Statement
    Super class Foo extends Bar { constructor() { super() } }
    SwitchCase switch (foo) { case 'bar': }
    SwitchStatement switch(foo) {}
    TaggedTemplateExpression css.foo { color: red; }
    TemplateLiteral css.foo { color: red; }
    ThisExpression this.foo = 'bar'
    ThrowStatement throw new Error("foo")
    TryStatement try { foo() } catch (exception) { bar() }
    UnaryExpression !foo
    UnaryOperator
    UpdateExpression foo++
    UpdateOperator
    VariableDeclaration const answer = 42
    VariableDeclarator const foo = 'bar'
    WhileStatement while (true) {}
    WithStatement with (foo) {}
    YieldExpression function* foo() { yield bar }

    Optimizations

    How can you optimize an abstract syntax tree?

    Abstract syntax tree is a tree-like structure that represents your program. The program is interpreted at some point, e.g. in your browser. Everything takes time, and the same applies to the interpretation. Some of the operations, e.g. adding numbers can be done at compile time, so that the interpreter has less work to do. Having less work to do means that your program will run faster.

    Usage

    const { binaryExpressionReduction } = require('abstract-syntax-tree')

    What optimization techniques are available?

    binaryExpressionReduction

    const number = 2 + 2

    In the example above we have added two numbers. We could optimize the code by:

    const number = 4

    The tree would be translated from:

    {
      "type": "BinaryExpression",
      "operator": "+",
      "left": { "type": "Literal", "value": 2 },
      "right": { "type": "Literal", "value": 2 }
    }

    to

    { "type": "Literal", "value": 4 }

    ifStatementRemoval

    if (true) {
      console.log('foo')
    } else {
      console.log('bar')
    }

    It seems that we'll only enter the true path. We can simplify the code to:

    console.log('foo')

    The tree would be translated from:

    {
          "type": "IfStatement",
          "test": {
            "type": "Literal",
            "value": true
          },
          "consequent": {
            "type": "BlockStatement",
            "body": [
              {
                "type": "ExpressionStatement",
                "expression": {
                  "type": "CallExpression",
                  "callee": {
                    "type": "MemberExpression",
                    "object": {
                      "type": "Identifier",
                      "name": "console"
                    },
                    "property": {
                      "type": "Identifier",
                      "name": "log"
                    },
                    "computed": false
                  },
                  "arguments": [
                    {
                      "type": "Literal",
                      "value": "foo"
                    }
                  ]
                }
              }
            ]
          },
          "alternate": {
            "type": "BlockStatement",
            "body": [
              {
                "type": "ExpressionStatement",
                "expression": {
                  "type": "CallExpression",
                  "callee": {
                    "type": "MemberExpression",
                    "object": {
                      "type": "Identifier",
                      "name": "console"
                    },
                    "property": {
                      "type": "Identifier",
                      "name": "log"
                    },
                    "computed": false
                  },
                  "arguments": [
                    {
                      "type": "Literal",
                      "value": "bar"
                    }
                  ]
                }
              }
            ]
          }
        }

    to:

    {
            "type": "CallExpression",
            "callee": {
              "type": "MemberExpression",
              "object": {
                "type": "Identifier",
                "name": "console"
              },
              "property": {
                "type": "Identifier",
                "name": "log"
              },
              "computed": false
            },
            "arguments": [
              {
                "type": "Literal",
                "value": "foo"
              }
            ]
          }

    negationOperatorRemoval

    if (!(foo === bar)) {
      console.log('foo')
    }

    It seems that our negation operator could be a part of the condition inside the brackets.

    if (foo !== bar)  {
      console.log('foo')
    }

    The tree would be translated from:

    {
      "type": "UnaryExpression",
      "operator": "!",
      "prefix": true,
      "argument": {
        "type": "BinaryExpression",
        "left": {
          "type": "Identifier",
          "name": "foo"
        },
        "operator": "===",
        "right": {
          "type": "Identifier",
          "name": "bar"
        }
      }
    }

    to

    {
      "type": "BinaryExpression",
      "left": {
        "type": "Identifier",
        "name": "foo"
      },
      "operator": "!==",
      "right": {
        "type": "Identifier",
        "name": "bar"
      }
    }

    logicalExpressionReduction

    const foo = "bar" || "baz"

    The first value is truthy so it's safe to simplify the code.

    const foo = "bar"

    The tree would be translated from:

    {
      "type": "LogicalExpression",
      "left": {
        "type": "Literal",
        "value": "bar"
      },
      "operator": "||",
      "right": {
        "type": "Literal",
        "value": "baz"
      }
    }

    To:

    {
      "type": "Literal",
      "value": "bar"
    }

    ternaryOperatorReduction

    const foo = true ? "bar": "baz"

    Given a known value of the conditional expression it's possible to get the right value immediately.

    const foo = "bar"

    The tree would be translated from:

    {
      "type": "ConditionalExpression",
      "test": {
        "type": "Literal",
        "value": true
      },
      "consequent": {
        "type": "Literal",
        "value": "bar"
      },
      "alternate": {
        "type": "Literal",
        "value": "baz"
      }
    }

    To:

    {
      "type": "Literal",
      "value": "bar"
    }

    typeofOperatorReduction

    const foo = typeof "bar"

    It's possible to determine the type of some variables during analysis.

    const foo = "string"

    The tree would be translated from:

    {
      "type": "UnaryExpression",
      "operator": "typeof",
      "prefix": true,
      "argument": {
        "type": "Literal",
        "value": "foo"
      }
    }

    To:

    {
      "type": "Literal",
      "value": "string"
    }

    memberExpressionReduction

    const foo = ({ bar: "baz" }).bar

    Given an inlined object expression it's possible to retrieve the value immediately.

    const foo = "baz"

    The tree would be translated from:

    {
      "type": "MemberExpression",
      "object": {
        "type": "ObjectExpression",
        "properties": [
          {
            "type": "Property",
            "method": false,
            "shorthand": false,
            "computed": false,
            "key": {
              "type": "Identifier",
              "name": "bar"
            },
            "value": {
              "type": "Literal",
              "value": "baz"
            },
            "kind": "init"
          }
        ]
      },
      "property": {
        "type": "Identifier",
        "name": "baz"
      },
      "computed": false
    }

    To:

    {
      "type": "Literal",
      "value": "baz"
    }

    Browser

    The library is not intended to work inside of a browser. This might change in the future, but it's a bigger lift, pretty time consuming. For now, consider exposing and using an API endpoint instead.

    Maintainers

    @emilos.

    Contributing

    All contributions are highly appreciated! Open an issue or a submit PR.

    The lib follows the tdd approach and is expected to have a high code coverage. Please follow the Contributor Covenant Code of Conduct.

    License

    MIT © buxlabs

    Install

    npm i abstract-syntax-tree

    DownloadsWeekly Downloads

    5,193

    Version

    2.20.5

    License

    MIT

    Unpacked Size

    86 kB

    Total Files

    127

    Last publish

    Collaborators

    • buxlabs-dev
    • emilos