ast-flow-graph

Constructs a CFG for JavaScript source code.

This module will read one or more JavaScript source files and produce CFGs of the code.

Install

npm i ast-flow-graph

Usage

const
    CFG = require( 'ast-flow-graph' ),
    fs = require( 'fs' ),
    src = fs.readFileSync( 'some-javascript.js', 'utf8' ),
    cfg = new CFG( src, {
        parser:    {
            loc:          true,
            range:        true,
            comment:      true,
            tokens:       true,
            ecmaVersion:  9,
            sourceType:   'module',
            ecmaFeatures: {
                impliedStrict: true,
                experimentalObjectRestSpread: true
            }
        }
    } );

cfg.generate();     // Generate a CFG for all functions (and main module)
// or for just one function
const graph = cfg.generate( 'my_function' );

// Create all graphs and then get one of them
cfg.generate(); // You only need to do this once.
const myFunc = cfg.by_name( 'my_function' );
// ...
console.log( cfg.toTable() );    // Display all functions as tables
// Create a graph-viz .dot file

console.log( cfg.create_dot( myFunc ) );

CLI Usage

  cfg version 1.0.0

Usage

  cfg [-d] [-g] [-s ...sources] [-t] [-n ...names] [-r] [-v] [-h] [...files]

Options

  -d, --debug             Turn on debugging mode. Warning: This will generate a lot of output.
  -g, --graph             Create a .dot file for graph-viz
  -o, --output string     If this option is present, save the .dot files to this directory.
  -s, --source string[]   Input source file. Can also be specified at the end of the command line.
  -t, --table             Output a table showing all CFG blocks
  -l, --lines             Output CFG blocks as text
  -n, --name string[]     Specify a function name to only display information for that function.
  -v, --verbose           Output additional information
  -h, --help              Display this help message

Description

  Creates a CFG from one or more source files.

The CFG it outputs can be in one of several formats. Two of them are for easy text displays in the console and can be displayed using the -t, --table or -l, --lines options for tabular or line oriented output, respectively. These displays are of limited use and are mostly used for quick reference or checks. The program will also output a .dot file for use with Graphviz or, optionally, graph-easy or similar programs that can read standard .dot files.

Since I like to include some explanatory graphs in source or README.md files, I like to create graphs in line ascii. For this, I use the perl module graph-easy.

Example usage:

ast-flow-graph -g -s test-data/cfg-test-04.js | graph-easy --as_boxart

Or in two steps.

ast-flow-graph -gs test-data/cfg-test-04.js > cfg-04.dot
graph-easy cfg-04.dot --as_boxart >flow-04.txt

which will produce something like this:

                                          blah:12-28

                        ╭─────────────╮
                        │   entry:0   │
                        ╰─────────────╯
                          │
                          │
                          ▼
                        ╭─────────────╮
                        │ NORMAL:1@14 │
                        ╰─────────────╯
                          │
                          │
                          ▼
                        ╭────────────────────────────────────────────╮  CONTINUE
                        │               NORMAL:2@16-20               │ ◀─────────────┐
                        ╰────────────────────────────────────────────╯               │
                          │              ▲         │                                 │
                          │              │         │                                 │
                          ▼              │         ▼                                 │
╭─────────────╮  TRUE   ╭─────────────╮  │       ╭───────────────────╮             ╭───────────╮
│ NORMAL:6@23 │ ◀╴╴╴╴╴╴ │  TEST:5@22  │  └────── │ TEST|LOOP:3@18-19 │ ──────────▶ │ LOOP:4@19 │
╰─────────────╯         ╰─────────────╯          ╰───────────────────╯             ╰───────────╯
  │                       ╵
  │                       ╵ FALSE
  │                       ▼
  │                     ╭─────────────╮
  │                     │  TEST:7@24  │ ╴┐
  │                     ╰─────────────╯  ╵
  │                       ╵              ╵
  │                       ╵ TRUE         ╵
  │                       ▼              ╵
  │                     ╭─────────────╮  ╵
  │                     │ NORMAL:8@25 │  ╵ FALSE
  │                     ╰─────────────╯  ╵
  │                       │              ╵
  │                       │              ╵
  │                       ▼              ╵
  │                     ╭─────────────╮  ╵
  └───────────────────▶ │ NORMAL:9@27 │ ◀┘
                        ╰─────────────╯
                          │
                          │
                          ▼
                        ╭─────────────╮
                        │ NORMAL:10@0 │
                        ╰─────────────╯
                          │
                          │
                          ▼
                        ╭─────────────╮
                        │   exit:11   │
                        ╰─────────────╯

The annotations, like 3@18-19, for example, means (CFG) block number 3, covering lines 18 through 19 in the source code. A TEST is a conditional branch, probably an if statement, and TEST|LOOP is a loop condition test, and so on.

You can also send the output Graphviz and use one of its myriad outputs. We can generate a .png of the graph above with a command like this:

ast-flow-graph -gs test-data/cfg-test-04.js > cfg-04.dot
dot -Tpng tmp-04.dot

which produces something the image below (I scaled it down for size reasons):

Finally, note that the .dot file is simple text, so you can edit the labels, colors, and whatnot if you care or need to do so.

Plugins

This section is a work in progress. The headers, rows, and json are not implemented, the others are but not tested.

General

• postLoad for general initialization
• preExit for general cleanup

CFG

• init before anything is done
• postInit after AST but before graph
• finish after graph as part of block finishing
• headers
• rows
• json

AST

• init before parsing
• postInit after parsing
• finish after parsing and traversal
• postFinish after all AST functions are done

CFGBlock

• init after the block is initialized
• finish after the block has been visited
• postFinish after the block has been added and the walker is moving on
• headers
• rows
• json

BlockManager

• init after the BlockManager has been initialized
• finish after the BlockManager has added all blocks
• postFinish after the clean() stage
• headers
• rows
• json

Other

• parse called to parse the source code

API

Members

Functions

Typedefs

succesors_as_indices ⇒ Array.<number>

Kind: global variable

successors ⇒ Array.<CFGBlock>

Kind: global variable

succs ⇒ Array.<CFGBlock>

Kind: global variable

preds ⇒ Array.<CFGBlock>

Kind: global variable

preds ⇒ Array.<number>

Get all predecessors for a given CFGBlock

Kind: global variable

defaultOutputOptions

The default display options for table and string output.

Kind: global variable

pluginManager : PluginManager

Kind: global variable

Block : enum

Kind: global enum

Edge : enum

Kind: global enum

node_to_scope(node) ⇒ *

Kind: global function

| Param | Type | | --- | --- | | node | AnnotatedNode |

forFunctions() : Iterable.<FunctionInfo>

Kind: global function

traverse(ast, [enter], [leave])

Kind: global function

| Param | Type | | --- | --- | | ast | Node | function | | [enter] | function | | [leave] | function |

walker(node, [enter], [leave])

Kind: global function

| Param | Type | | --- | --- | | node | AnnotatedNode | BaseNode | Node | | [enter] | function | | [leave] | function |

flat_walker(nodes, cb)

Iterate over all nodes in a block without recursing into sub-nodes.

Kind: global function

| Param | Type | | --- | --- | | nodes | Array.<AnnotatedNode> | AnnotatedNode | | cb | function |

call_visitors(node, cb)

Callback for each visitor key for a given node.

Kind: global function

| Param | Type | | --- | --- | | node | AnnotatedNode | | cb | function |

add_line(lineNumber, sourceLine)

Add a new line to the source code.

Kind: global function

| Param | Type | Description | | --- | --- | --- | | lineNumber | number | 0-based line number | | sourceLine | string | The source line to add |

rename(inode, newName)

Kind: global function

| Param | Type | Description | | --- | --- | --- | | inode | Identifier | AnnotatedNode | A node of type Syntax.Identifier | | newName | string | The new name of the identifier |

as_source() ⇒ string

Return the AST nodes as source code, including any modifications made.

Kind: global function Returns: string - - The lossy source code

get_from_function(node, [whatToGet]) ⇒ Array.<Node> | string | CFGInfo

Kind: global function Access: protected

| Param | Type | Default | | --- | --- | --- | | node | FunctionDeclaration | FunctionExpression | MethodDefinition | ArrowFunctionExpression | Property | Node | | | [whatToGet] | string | "'all'" |

isEmpty() ⇒ boolean

Kind: global function

classify(to, type) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | to | number | CFGBlock | | type | string |

follows(cb) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | cb | CFGBlock | Array.<CFGBlock> |

from(cb) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | cb | CFGBlock | Array.<CFGBlock> |

to(cb) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | cb | CFGBlock | Array.<CFGBlock> |

remove_succs() ⇒ CFGBlock

Kind: global function

remove_succ(kill) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | kill | number | CFGBlock |

as(nodeType) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | nodeType | number |

edge_as(edgeType, [to]) ⇒ CFGBlock

Sets the last edge to type.

Kind: global function

| Param | Type | | --- | --- | | edgeType | Edge | | [to] | number | CFGBlock |

not(nodeType) ⇒ CFGBlock

Removes a type from this block.

Kind: global function

| Param | Type | | --- | --- | | nodeType | Edge |

whenTrue(block) ⇒ CFGBlock

For test nodes, this adds the edge taken when the condition is true.

Kind: global function

| Param | Type | | --- | --- | | block | CFGBlock |

whenFalse(block) ⇒ CFGBlock

For test nodes, this adds the edge taken when the condition is false.

Kind: global function

| Param | Type | | --- | --- | | block | CFGBlock |

add(node) ⇒ CFGBlock

Add a current-level AST node to this block.

Kind: global function

| Param | Type | | --- | --- | | node | AnnotatedNode | BaseNode | Node |

first() ⇒ AnnotatedNode | BaseNode | Node

Returns the first AST node (if any) of this block.

Kind: global function

last() ⇒ AnnotatedNode | BaseNode | Node

Returns the last AST node (if any) of this block.

Kind: global function

by(txt) ⇒ CFGBlock

Free-text field indicating the manner of of creation of this node. For information in graphs and printouts only.

Kind: global function

| Param | Type | | --- | --- | | txt | string |

isa(typeName) ⇒ boolean

Check if this block has a particular type.

Kind: global function

| Param | Type | | --- | --- | | typeName | number |

eliminate() ⇒ boolean

Remove itself if it's an empty node and isn't the start or exit node.

Kind: global function Returns: boolean - - true if it was deleted

defer_edge_type(type)

Kind: global function

| Param | Type | | --- | --- | | type | Edge |

graph_label() ⇒ string

For the vertices.

Kind: global function

lines() ⇒ string

Stringified line numbers for this block.

Kind: global function

pred_edge_types() ⇒ Array.<string>

Kind: global function

succ_edge_types() ⇒ Array.<string>

Kind: global function

split_by(arr, chunkSize) ⇒ ArrayArray.<string>

Kind: global function

| Param | Type | | --- | --- | | arr | Array.<*> | | chunkSize | number |

toRow() ⇒ Array.<string>

Headers are TYPE / LINES / LEFT EDGES / NODE / RIGHT EDGES / CREATED BY / AST

Kind: global function

toString() ⇒ Array.<string>

Kind: global function

toString() ⇒ string

Kind: global function

toTable() ⇒ string

Kind: global function

generate([name]) ⇒ Array.<CFGInfo> | CFG

Kind: global function

| Param | Type | | --- | --- | | [name] | string |

by_name(name) ⇒ CFGInfo

Kind: global function

| Param | Type | | --- | --- | | name | string |

forEach(fn)

Kind: global function

| Param | Type | | --- | --- | | fn | function |

create_dot(cfg, [title]) ⇒ string

Kind: global function

| Param | Type | | --- | --- | | cfg | CFGInfo | | [title] | string |

_as_table(hdr, [headers], [rows])

Kind: global function

| Param | Type | | --- | --- | | hdr | string | Array.<string> | Array.<Array.<string>> | | [headers] | Array.<string> | Array.<Array.<string>> | | [rows] | Array.<Array.<string>> |

reindex(from) ⇒ Edges

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number |

add(from, to, type) ⇒ Edges

Add an edge between to CFGBlocks.

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number | | to | CFGBlock | number | | type | Edge |

classify(from, to, ctype) ⇒ Edges

Set a type on an arbitrary edge.

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number | | to | CFGBlock | number | | ctype | Edge |

not(from, to, type) ⇒ Edges

Remove a type from an arbitrary edge.

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number | | to | CFGBlock | number | | type | Edge |

retarget_multiple(node) ⇒ Edges

Point one or more edges to a new CFGBlock, used in block removal.

Kind: global function

| Param | Type | | --- | --- | | node | CFGBlock | number |

remove_succ(from, to) ⇒ Edges

Remove a successor CFGBlock from a CFGBlock

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number | | to | CFGBlock | number |

get_succs(from) ⇒ Array.<CFGBlock>

Get all successors for a given CFGBlock.

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number |

get_preds(from) ⇒ Array.<CFGBlock>

Get all predecessors for a given CFGBlock

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number |

renumber(newOffsets)

Renumber all indices (id field) because of removed CFGBlocks.

Kind: global function

| Param | Type | | --- | --- | | newOffsets | Array.<number> |

successors() : Iterable.<number>

Kind: global function

has(from, type) ⇒ boolean

Is there an edge of the gievn type?

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number | | type | Edge |

edges(from) ⇒ Array.<Connection>

Get edge information for a given CFGBlock, i.e. successors.

Kind: global function

| Param | Type | | --- | --- | | from | CFGBlock | number |

pred_edges(_from) ⇒ Array.<Connection>

Get all predecessor edge information for a given CFGBlock.

Kind: global function

| Param | Type | | --- | --- | | _from | CFGBlock | number |

forEach(fn)

Kind: global function

| Param | Type | | --- | --- | | fn | function |

map(fn)

Kind: global function

| Param | Type | | --- | --- | | fn | function |

get(index) ⇒ CFGBlock

Kind: global function

| Param | Type | | --- | --- | | index | number |

toString() ⇒ string

Kind: global function

toTable() ⇒ Array.<string>

Kind: global function

create_dot(title) ⇒ string

Kind: global function

| Param | Type | | --- | --- | | title | string |

callback(topKey, subKey, ...args) ⇒ *

Kind: global function

| Param | Type | | --- | --- | | topKey | string | | subKey | string | | ...args | * |

output(options)

Override display options.

Kind: global function

| Param | | --- | | options |

CFGInfo : object

Kind: global typedef Properties

| Name | Type | | --- | --- | | name | string | | params | Array.<AnnotatedNode> | | body | AnnotatedNode | Array.<AnnotatedNode> | | lines | Array.<Number> | | [bm] | BlockManager | | [trailing] | CFGBlock | | node, | AnnotatedNode | Node | BaseNode | | ast | AST | | topScope | Scope | | toString | function | | toTable | function |

VisitorHelper : object

Kind: global typedef Properties

| Name | Type | | --- | --- | | BlockManager | BlockManager | | bm | BlockManager | | ast | AST | | prev | CFGBlock | | block | CFGBlock | | newBlock | function | | toExit | Array.<CFGBlock> | | [flatWalk] | function | | [scanWalk] | function | | breakTargets | Array.<CFGBlock> | | addBreakTarget | function | | addLoopTarget | function | | popTarget | function | | getBreakTarget | function | | getLoopTarget | function |

AnnotatedNode : Statement | function | Expression | Pattern | Declaration | Node | BaseNode | Esprima.Node

It's damn near impossible to make WebStorm understand a class hierarchy.

Kind: global typedef Extends: BaseNode, Node, VariableDeclarator, Statement, Declaration, Pattern, Expression, Function, BlockStatement, espree.Node Properties

| Name | Type | | --- | --- | | [index] | number | | [parent] | AnnotatedNode | | [cfg] | CFGBlock | | [toString] | function | | scope | Scope | | level | number | | field | string | | fieldIndex | number |

CFGOptions : object

Kind: global typedef Properties

| Name | Type | | --- | --- | | ssaSource | boolean | | parser | object |

DotOptions : object

Kind: global typedef Properties

| Name | Type | Default | Description | | --- | --- | --- | --- | | title | string | | | | nodeLabels | Array.<string> | | | | edgeLabels | Array.<string> | | // was graph_label | | [start] | number | | | | [end] | number | | | | conditional | Array.<Array.<number>> | | Actually an array of a tuple length 2: [ number, number ] | | unconditional | Array.<Array.<number>> | | Actually an array of a tuple length 2: [ number, number ] | | [dotOptions] | object | {} | | | blocks | Array.<CFGBlock> | | |

FunctionInfo : object

Kind: global typedef Properties

| Name | Type | Description | | --- | --- | --- | | name | string | | | body | Array.<AnnotatedNode> | AnnotatedNode | | | [params] | Array.<AnnotatedNode> | | | node | AnnotatedNode | | | lines | Array.<number> | A tuple with length 2 |

Connection : object

Kind: global typedef Properties

| Name | Type | | --- | --- | | from | number | | to | number | | type | EdgeInfo |

License

MIT © Julian Jensen