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 = fs = src = fs cfg = src parser: loc: true range: true comment: true tokens: true ecmaVersion: 9 sourceType: 'module' ecmaFeatures: impliedStrict: true experimentalObjectRestSpread: true ; cfg; // Generate a CFG for all functions (and main module)// or for just one functionconst graph = cfg; // Create all graphs and then get one of themcfg; // You only need to do this once.const myFunc = cfg;// ...console; // Display all functions as tables// Create a graph-viz .dot file console;
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-04js > cfg-04dotgraph-easy cfg-04dot --as_boxart >flow-04txt
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.dotdot -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 initializationpreExit
for general cleanup
CFG
init
before anything is donepostInit
afterAST
but before graphfinish
after graph as part of block finishingheaders
rows
json
AST
init
before parsingpostInit
after parsingfinish
after parsing and traversalpostFinish
after allAST
functions are done
CFGBlock
init
after the block is initializedfinish
after the block has been visitedpostFinish
after the block has been added and the walker is moving onheaders
rows
json
BlockManager
init
after theBlockManager
has been initializedfinish
after theBlockManager
has added all blockspostFinish
after theclean()
stageheaders
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
- 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
Array.<number>
succesors_as_indices ⇒
Array.<CFGBlock>
successors ⇒
Array.<CFGBlock>
succs ⇒
Array.<CFGBlock>
preds ⇒
Array.<number>
preds ⇒ Get all predecessors for a given CFGBlock
defaultOutputOptions
The default display options for table and string output.
PluginManager
pluginManager :
enum
Block :
enum
Edge :
*
node_to_scope(node) ⇒ Kind: global function
Param | Type |
---|---|
node | AnnotatedNode |
Iterable.<FunctionInfo>
forFunctions() :
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 |
string
as_source() ⇒ Return the AST nodes as source code, including any modifications made.
Kind: global function
Returns: string
- - The lossy source code
Array.<Node>
| string
| CFGInfo
get_from_function(node, [whatToGet]) ⇒ Kind: global function Access: protected
Param | Type | Default |
---|---|---|
node | FunctionDeclaration | FunctionExpression | MethodDefinition | ArrowFunctionExpression | Property | Node |
|
[whatToGet] | string |
"'all'" |
boolean
isEmpty() ⇒
CFGBlock
classify(to, type) ⇒ Kind: global function
Param | Type |
---|---|
to | number | CFGBlock |
type | string |
CFGBlock
follows(cb) ⇒ Kind: global function
Param | Type |
---|---|
cb | CFGBlock | Array.<CFGBlock> |
CFGBlock
from(cb) ⇒ Kind: global function
Param | Type |
---|---|
cb | CFGBlock | Array.<CFGBlock> |
CFGBlock
to(cb) ⇒ Kind: global function
Param | Type |
---|---|
cb | CFGBlock | Array.<CFGBlock> |
CFGBlock
remove_succs() ⇒
CFGBlock
remove_succ(kill) ⇒ Kind: global function
Param | Type |
---|---|
kill | number | CFGBlock |
CFGBlock
as(nodeType) ⇒ Kind: global function
Param | Type |
---|---|
nodeType | number |
CFGBlock
edge_as(edgeType, [to]) ⇒ Sets the last edge to type.
Kind: global function
Param | Type |
---|---|
edgeType | Edge |
[to] | number | CFGBlock |
CFGBlock
not(nodeType) ⇒ Removes a type from this block.
Kind: global function
Param | Type |
---|---|
nodeType | Edge |
CFGBlock
whenTrue(block) ⇒ For test nodes, this adds the edge taken when the condition is true.
Kind: global function
Param | Type |
---|---|
block | CFGBlock |
CFGBlock
whenFalse(block) ⇒ For test nodes, this adds the edge taken when the condition is false.
Kind: global function
Param | Type |
---|---|
block | CFGBlock |
CFGBlock
add(node) ⇒ Add a current-level AST node to this block.
Kind: global function
Param | Type |
---|---|
node | AnnotatedNode | BaseNode | Node |
AnnotatedNode
| BaseNode
| Node
first() ⇒ Returns the first AST node (if any) of this block.
AnnotatedNode
| BaseNode
| Node
last() ⇒ Returns the last AST node (if any) of this block.
CFGBlock
by(txt) ⇒ 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 |
boolean
isa(typeName) ⇒ Check if this block has a particular type.
Kind: global function
Param | Type |
---|---|
typeName | number |
boolean
eliminate() ⇒ 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 |
string
graph_label() ⇒ For the vertices.
string
lines() ⇒ Stringified line numbers for this block.
Array.<string>
pred_edge_types() ⇒
Array.<string>
succ_edge_types() ⇒
ArrayArray.<string>
split_by(arr, chunkSize) ⇒ Kind: global function
Param | Type |
---|---|
arr | Array.<*> |
chunkSize | number |
Array.<string>
toRow() ⇒ Headers are TYPE / LINES / LEFT EDGES / NODE / RIGHT EDGES / CREATED BY / AST
Array.<string>
toString() ⇒
string
toString() ⇒
string
toTable() ⇒
Array.<CFGInfo>
| CFG
generate([name]) ⇒ Kind: global function
Param | Type |
---|---|
[name] | string |
CFGInfo
by_name(name) ⇒ Kind: global function
Param | Type |
---|---|
name | string |
forEach(fn)
Kind: global function
Param | Type |
---|---|
fn | function |
string
create_dot(cfg, [title]) ⇒ 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>> |
Edges
reindex(from) ⇒ Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
Edges
add(from, to, type) ⇒ Add an edge between to CFGBlocks.
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
to | CFGBlock | number |
type | Edge |
Edges
classify(from, to, ctype) ⇒ Set a type on an arbitrary edge.
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
to | CFGBlock | number |
ctype | Edge |
Edges
not(from, to, type) ⇒ Remove a type from an arbitrary edge.
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
to | CFGBlock | number |
type | Edge |
Edges
retarget_multiple(node) ⇒ Point one or more edges to a new CFGBlock, used in block removal.
Kind: global function
Param | Type |
---|---|
node | CFGBlock | number |
Edges
remove_succ(from, to) ⇒ Remove a successor CFGBlock from a CFGBlock
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
to | CFGBlock | number |
Array.<CFGBlock>
get_succs(from) ⇒ Get all successors for a given CFGBlock.
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
Array.<CFGBlock>
get_preds(from) ⇒ 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> |
Iterable.<number>
successors() :
boolean
has(from, type) ⇒ Is there an edge of the gievn type?
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
type | Edge |
Array.<Connection>
edges(from) ⇒ Get edge information for a given CFGBlock, i.e. successors.
Kind: global function
Param | Type |
---|---|
from | CFGBlock | number |
Array.<Connection>
pred_edges(_from) ⇒ 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 |
CFGBlock
get(index) ⇒ Kind: global function
Param | Type |
---|---|
index | number |
string
toString() ⇒
Array.<string>
toTable() ⇒
string
create_dot(title) ⇒ 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 |
object
CFGInfo : 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 |
object
VisitorHelper : 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 |
Statement
| function
| Expression
| Pattern
| Declaration
| Node
| BaseNode
| Esprima.Node
AnnotatedNode : 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 |
object
CFGOptions : Kind: global typedef Properties
Name | Type |
---|---|
ssaSource | boolean |
parser | object |
object
DotOptions : 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> |
object
FunctionInfo : 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 |
object
Connection : Kind: global typedef Properties
Name | Type |
---|---|
from | number |
to | number |
type | EdgeInfo |
License
MIT © Julian Jensen