ast-flow-graph

v1.0.18

Published

3 years ago

Constructs a CFG for JavaScript source code.

Downloads

0High
0Medium
0Low

jjdanois

cfg flowgraph flow graph control flow graph

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

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

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 |

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

ast-flow-graph

Install

Usage

CLI Usage

Plugins

General

CFG

AST

CFGBlock

BlockManager

Other

API

Members

Functions

Typedefs

succesors_as_indices ⇒ Array.<number>

successors ⇒ Array.<CFGBlock>

succs ⇒ Array.<CFGBlock>

preds ⇒ Array.<CFGBlock>

preds ⇒ Array.<number>

defaultOutputOptions

pluginManager : PluginManager

Block : enum

Edge : enum

node_to_scope(node) ⇒ *

forFunctions() : Iterable.<FunctionInfo>

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

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

flat_walker(nodes, cb)

call_visitors(node, cb)

add_line(lineNumber, sourceLine)

rename(inode, newName)

as_source() ⇒ string

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

not(nodeType) ⇒ CFGBlock

whenTrue(block) ⇒ CFGBlock

whenFalse(block) ⇒ CFGBlock

add(node) ⇒ CFGBlock

first() ⇒ AnnotatedNode | BaseNode | Node

last() ⇒ AnnotatedNode | BaseNode | Node

by(txt) ⇒ CFGBlock

isa(typeName) ⇒ boolean

eliminate() ⇒ boolean

defer_edge_type(type)

graph_label() ⇒ string

lines() ⇒ string

pred_edge_types() ⇒ Array.<string>

succ_edge_types() ⇒ Array.<string>

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

toRow() ⇒ Array.<string>

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

classify(from, to, ctype) ⇒ Edges

not(from, to, type) ⇒ Edges

retarget_multiple(node) ⇒ Edges

remove_succ(from, to) ⇒ Edges

get_succs(from) ⇒ Array.<CFGBlock>

`CFG`

`AST`

`CFGBlock`

`BlockManager`