❤
npm
Sign UpSign In

ast-flow-graph

1.0.18 • Public • Published

ast-flow-graph

Greenkeeper badge codecov Coveralls Status Build Status npm version License Known Vulnerabilities david-dm

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):

cfg-04.dot

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

succesors_as_indices ⇒ Array.<number>
successors ⇒ Array.<CFGBlock>
succs ⇒ Array.<CFGBlock>
preds ⇒ Array.<CFGBlock>
preds ⇒ Array.<number>

Get all predecessors for a given CFGBlock

defaultOutputOptions

The default display options for table and string output.

pluginManager : PluginManager

Functions

node_to_scope(node) ⇒ *
forFunctions() : Iterable.<FunctionInfo>
traverse(ast, [enter], [leave])
walker(node, [enter], [leave])
flat_walker(nodes, cb)

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

call_visitors(node, cb)

Callback for each visitor key for a given node.

add_line(lineNumber, sourceLine)

Add a new line to the source code.

rename(inode, newName)
as_source() ⇒ string

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

get_from_function(node, [whatToGet]) ⇒ Array.<Node> | string | CFGInfo
isEmpty() ⇒ boolean
classify(to, type) ⇒ CFGBlock
follows(cb) ⇒ CFGBlock
from(cb) ⇒ CFGBlock
to(cb) ⇒ CFGBlock
remove_succs() ⇒ CFGBlock
remove_succ(kill) ⇒ CFGBlock
as(nodeType) ⇒ CFGBlock
edge_as(edgeType, [to]) ⇒ CFGBlock

Sets the last edge to type.

not(nodeType) ⇒ CFGBlock

Removes a type from this block.

whenTrue(block) ⇒ CFGBlock

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

whenFalse(block) ⇒ CFGBlock

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

add(node) ⇒ CFGBlock

Add a current-level AST node to this block.

first() ⇒ AnnotatedNode | BaseNode | Node

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

last() ⇒ AnnotatedNode | BaseNode | Node

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

by(txt) ⇒ CFGBlock

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

isa(typeName) ⇒ boolean

Check if this block has a particular type.

eliminate() ⇒ boolean

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

defer_edge_type(type)
graph_label() ⇒ string

For the vertices.

lines() ⇒ string

Stringified line numbers for this block.

pred_edge_types() ⇒ Array.<string>
succ_edge_types() ⇒ Array.<string>
split_by(arr, chunkSize) ⇒ ArrayArray.<string>
toRow() ⇒ Array.<string>

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

toString() ⇒ Array.<string>
toString() ⇒ string
toTable() ⇒ string
generate([name]) ⇒ Array.<CFGInfo> | CFG
by_name(name) ⇒ CFGInfo
forEach(fn)
create_dot(cfg, [title]) ⇒ string
_as_table(hdr, [headers], [rows])
reindex(from) ⇒ Edges
add(from, to, type) ⇒ Edges

Add an edge between to CFGBlocks.

classify(from, to, ctype) ⇒ Edges

Set a type on an arbitrary edge.

not(from, to, type) ⇒ Edges

Remove a type from an arbitrary edge.

retarget_multiple(node) ⇒ Edges

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

remove_succ(from, to) ⇒ Edges

Remove a successor CFGBlock from a CFGBlock

get_succs(from) ⇒ Array.<CFGBlock>

Get all successors for a given CFGBlock.

get_preds(from) ⇒ Array.<CFGBlock>

Get all predecessors for a given CFGBlock

renumber(newOffsets)

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

successors() : Iterable.<number>
has(from, type) ⇒ boolean

Is there an edge of the gievn type?

edges(from) ⇒ Array.<Connection>

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

pred_edges(_from) ⇒ Array.<Connection>

Get all predecessor edge information for a given CFGBlock.

forEach(fn)
map(fn)
get(index) ⇒ CFGBlock
toString() ⇒ string
toTable() ⇒ Array.<string>
create_dot(title) ⇒ string
callback(topKey, subKey, ...args) ⇒ *
output(options)

Override display options.

Typedefs

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

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

CFGOptions : object
DotOptions : object
FunctionInfo : object
Connection : object

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

Readme

Keywords

Package Sidebar

Install

npm i ast-flow-graph

Repository

github.com/julianjensen/ast-flow-graph

Homepage

github.com/julianjensen/ast-flow-graph#readme

Weekly Downloads

1

Version

1.0.18

License

MIT

Unpacked Size

317 kB

Total Files

35

Last publish

Collaborators

  • jjdanois
Try on RunKit
Report malware