Declarative instrumentation

Brian Burg edited this page Oct 10, 2013 · 36 revisions

Instrumenting programs to gather runtime data

Developer tools increasingly use and analyze runtime data to support program understanding tasks. The iterative and context-dependent nature of program understanding tasks means that a tool might invoke several dynamic analyses together on-demand as questions arise, and each analyses is tailored to gather data and answer questions within a specific context (a file, function, callsite, or object) rather than for the entire execution. For example, a tool to link asynchronous callbacks to their origin may want to capture both control and data flow information, but there's no reason that these should be coupled together. Traditional instrumentation techniques do not support runtime-adjustable and context-tailored analyses needed by developer tools.

Why not Source Instrumentation?

Source-to-source instrumentation (as exemplified by esprima + escodegen) is a popular technique for instrumenting JavaScript in a cross-platform way. Examples include Istanbul, a code coverage tool; esprof, a profiling tool; tracegl, a code tracing tool; Theseus, a JS debugger (focusing on asynchronous control flow) and jsbench, a benchmark synthesis tool.

Source instrumentation is not composable, thus rendering it impractical for collecting runtime data on behalf of developer tools. Source transformations are not transparent to each other, so the same source code cannot be multiply-instrumented. Adding or removing source instrumentation can only be done by reloading the application or by patching function bodies at runtime. Source instrumentation also interferes with the use of debuggers and profilers, which cannot distinguish instrumentation code from program code.

Why not Bytecode Instrumentation?

Bytecode instrumentation is the dominant means of instrumenting code that runs on bytecode VMs such as Java (JVM), C# (CLR). Unfortunately for dynamic analysis writers, there is no client-facing or standardized JavaScript bytecode format. Unlike JVM bytecode, the bytecode IR used internally by JS engines (JSC; IonMonkey) is low-level, complex, and changes frequently. It is a large engineering and maintenance burden to make dynamic analyses aware of the semantics of internal bytecodes. Modern engines emit special bytecodes to implement tracing profilers and debugger hooks; implementing these traditional tools require extra bytecodes, code generator paths, and implementations for each of the engine tiers (interpreter, baseline JIT, optimizing JIT, etc). It would obviously not be sustainable for each dynamic analysis to add its own helper code throughout the engine.

Declaratively Specifying Instrumentation

An alternate approach to instrumentation is to split instrumentation locations from instrumentation actions. Sets of locations are specified declaratively, rather than implicitly via an imperative algorithm. A declarative instrumentation framework abstracts over the vagaries of actually inserting instrumentation code, letting the analysis writer add instrumentation without needing to know about the internals of language runtimes.

In the remainder of this document we explore prior approaches for declaratively specifying instrumentation, and sketch a new instrumentation approach based on CSS-like selectors.

Related Work

Several imperative and declarative instrumentation frameworks already exist, and are briefly described below. They differ along the following axes:

  • What a program location corresponds to (AST node, bytecode, symbolic location)
  • How to query/specify program locations (visitors, Matchers, CSS selectors, aspect pointcuts)
  • Arguments available to instrumentation actions/callbacks (uniform, per-location type)
  • When instrumentation is inserted; when actions fire

Actions are invoked by most frameworks using a call-based model. In this model, analysis routines are (conceptually) called by the runtime environment as the instrumented program executes.

Clang AST Matchers

  • Program locations: AST nodes
  • Specification mechanism: tree matchers
  • Action arguments: the matched AST node
  • Instrumentation inserted at: (n/a)
  • Actions "fire" at: compile-time

Clang uses AST matcher objects to query the AST for a set of nodes. In contrast to CSS selectors, matchers can perform arbitrary inspection of the AST. Compound matchers are built imperatively. Matchers are used to implement source-to-source translation passes and path-insensitive static analyses at compile-time. Clang matchers do not seem to be used to specify/insert runtime instrumentation.

Matchers are run by specifying a root node, and then matching from the root of a matcher to its tail. This is probably less efficient than if one were to exploit basic CSS selector matching optimizations (end-user optimization strategies; optimization implementation strategies). However, we have no data on whether these optimizations are necessary for this domain where neither the rules nor tree can change.

PIN

  • Program locations: instructions (abstracted over specific ISAs)
  • Specification mechanism: visitors
  • Action arguments: configurable, instruction-dependent
  • Instrumentation inserted at: run-time
  • Actions fire at: run-time

PIN is a tool for runtime instrumentation of linux programs. Instrumentation and analysis routines execute alongside an executing program. PIN uses a JIT to reduce the overhead of its call-based model. The JIT can inline analysis codes, save/restore registers, re-allocate registers, and do other tricks to minimize instrumentation overhead.

DiSL: A DSL for Bytecode Instrumentation

  • Program locations: methods, basic blocks, instructions
  • Specification mechanisms: pointcut-like static method annotations
  • Action arguments: local variables, call stack, operand stack
  • Instrumentation inserted at: load-time weaving
  • Actions fire at: run-time

DiSL is intended to replace AOP as a facility for implementing high-level runtime instrumentation. It has an open join point model, meaning that users can write custom joint points. Snippets (i.e., advice) can access dynamic (runtime) context, synthetic variables, and other things. Snippets for individual instructions have access to the operand stack. Markers (i.e., join points) can access static context. The authors show code to implement basic block CCT profiling, array access profiling, and re-implemented Senseo's aspect-based dynamic instrumentation.

Senseo

  • Program locations: join points
  • Specification mechanisms: pointcuts
  • action arguments: can inspect Dynamic and Static context objects
  • instrumentation inserted at: load-time weaving
  • actions fire at: run-time

JSPath

Peter van der Zee has proposed (but not implemented) something similar to XPath selectors for JS AST nodes. It seems targeted for the purpose of uniquely referencing specific AST nodes, rather than specifying sets of elements.


Declarative Instrumentation API

Clients can use the declarative instrumentation to gather runtime data as the program executes, without modifying the JavaScript engine. To use the API, clients create several instrumentation hooks, and then register the hooks with the instrumentation API provided by the Javascript VM. The instrumentation API interprets hook requests and adds the necessary instrumentation into the program's bytecode stream. When the 1) eligible program locations are instrumented at parse-time or 2) instrumented parts of the program are executed at runtime, the relevant client-supplied callback is invoked. Then, the client can collect data.

To support a wide variety of analyses, we support two types of hooks: barrier hooks and AST selector hooks.

Barrier hooks

Some dynamic analyses (such as those implemented by Jalangi or Whyline) require low-level, precise, complete instrumentation of events such as property reads, property writes, allocations, garbage collections, etc. It is imprecise or impossible to capture these events with source instrumentation. For example, features like Array.prototype.map, Array.prototype.filter, and for (var key in map) perform implicit read, write, and allocation. In order to account for these operations, we provide barrier hooks which use VM support to introspect these events.

Each barrier hook consists of the following:

  • barrier hook type
  • instrumentation location (before/after)
  • callbacks to process instrumentation events
  • static scope where the hook should be active

Barrier hook types

  • Property read
  • Property write
  • Object allocation (prior to constructor invocation)

Program element selectors

Some dynamic analyses require high-level, sparse instrumentation; for example, call trace profiling requires instrumentation before and after all function calls. Users may also want to add logging expressions at a systematic set of source locations (i.e, arguments passed to functions named "addEventListener"), but not want to perform automated analysis. For these use cases, low-level barrier hooks are overkill.

Program element selectors are a mini-language for declaratively selecting AST nodes in an AST parse tree. The selectors chosen here are inspired by CSS 2.1 Selectors and Clang AST Matchers. The basic rules and intended style are closest to CSS selectors.

CSS selectors over DOM elements use special selectors for element type, class name, and id. Similarly, AST selectors have special selectors for node class, type, and label.

Rather than adding a custom string parser, AST selector expressions are built manually by constructing selector objects, placing constraints on them, and linking them together.

Each AST selector hook consists of the following:

  • program element selector
  • instrumentation location (before/after)
  • callbacks to process instrumentation events
  • static scope where the hook should be active

Classes

Classes represent common AST node interfaces. An AST node can have more than one class; for example, a FunctionDeclaration is both a Function and Declaration, and a FunctionExpression is both a Function and Expression. Class selectors are written .ClassName, similar to a CSS class selector. Listed below are all classes (with subinterfaces denoted in parenthesis), which closely follows the JavaScript Parser API.

  • Node (base class; everything <: Node)
  • Program
  • Function
  • Expression
  • ExpressionList
  • SwitchCase
  • SwitchCaseList
  • Literal ( <: Expression)
  • Identifier ( <: Expression)
  • Statement
  • StatementList
  • Declaration ( <: Statement)
  • DeclarationList

(Note that we omit AST classes which are only used by SpiderMonkey extensions or are not implemented by JSC, such as destructuring assignments, comprehensions, generators, etc.)

Types and Labels

Types are leaf AST node types, as defined in the Parser API. Examples of types include IfStatement, ReturnStatement, ArrayExpression, Literal, and so on. Labels include @test, @consequent, @alternate, @id, @params. A full list of supported node types and labels for each type is in Appendix B.

Selectors

  • type selectors: E (ex: ObjectLiteral)
  • class selectors E.foo (ex: Statement.Declaration)
  • label selectors E@label (ex: StatementList@consequent)
  • descendant selectors E F (ex: WhileStatement ReturnStatement)
  • child selectors E > F (ex: IfStatement > @consequent)
  • attribute selectors E[foo="bar"] (ex: UnaryExpression[operator="*"])
  • pseudo-classes :first-child, :last-child (ex: @consequent > :first-child)
  • sibling selectors E + F (ex: TODO: is there a use case for this?)

Pseudoclasses listed above only apply to nodes containing classes ending in List (StatementList, ExpressionList, etc), and otherwise filter out nothing (the "all" selector).

Instrumentation Location

Each hook is inserted either before or after each program element is evaluated.

Instrumentation Callbacks

To store static context and receive runtime data, clients provide two callbacks with each hook set.

  • WillEmitHookCallback: called when the hook is about to be emitted at "compile-time". Clients can use this opportunity to save static context of the hook, since it is not available at runtime. Static context is provided through the ParserContext class and associated wrapper classes, defined in Appendix B.

  • WillTriggerHookCallback: called when the hook is executed at runtime. Clients can access dynamic context available through ExecState, such as the call stack. For "after" hooks of expressions, the evaluated result is also made available.

Instrumentation Scope

The applicability of instrumentation hooks can be limited to any combination of the following lexical scopes:

  • File
  • Text range (starting line+column, ending line+column)

Sample use cases

Tracing profiler

  • What: function being called, source location of callsite, timestamp, source location of current call frame.
  • Where: before and after each callsite

To gather the function being called:

  • Approach 1: force deoptimization to slow paths, implement custom instrumentation inside LLIntSlowPaths.cpp.

  • Approach 2 (used by LegacyProfiler): inside emitCall(), create a register for hook args (hookReg), move function reference to hookReg, then emit the register index of hookReg after op_instrument_hook. Then, the implementation of op_instrument_hook can load the function reference from the register index embedded into the bytecode stream.

  • Approach 3: client adds 3 hooks, which each

    • hook("expr.call > .callee", after) -- to capture expression value inside call node
    • hook("expr.call", before) -- to capture timestamp before op_call
    • hook("expr.call", after) -- to capture timestamp/return value after op_call.

Other values can be obtained through WTF or ExecState at the time of the hook callback.

Branch/basic-block profiler

  • Prerequisite: Tracing profiler implementation
  • What: source location of statement/expression, timestamp
  • Where: before top-level expressions of ternary expression arms; before first statement of if arms and while-for loop; continue, return, break

This could be implemented by treating basic blocks as nodes in the calling context tree. Instrumentation that would normally belong before/after a callsite must additionally be inserted before/after jump statements.

  • Hook 1-3: as above in "Tracing Profiler"
  • Hook 4:
    • hook("stmt.if, stmt.while, stmt.for, stmt.switch", before) - before jumps
    • hook("stmt.if > .consequent > stmt:first-child", before) - after jump to then-branch
    • hook("stmt.if > .alternate > stmt:first-child", before) - after jump to else-branch
    • TODO: how to handle loops?

Conditional expression highlighting

  • What (subexpressions): expression value, source location of expression
  • Where (subexpressions): any expression within an if-conditional or while/for loop header
  • What (branch): source location of branch
  • Where (branch): before first statement of each if branch, or at loop head

Statement-based debugger

  • What: source location of statement
  • Where: before every statement

Hooks:

  • hook("stmt", before) - call into the breakpoint server with current script and line number

Unique object numbering

  • What: store a unique id into objects after allocation
  • Where: object literals, new()

Hooks:

  • XXX: can't hook into this syntactically, since objects are created internally.

Track objects to allocation site

  • What: store allocation site id into object private property, or save object id into per-allocation site list
  • Where: object literals, new()

Hooks:

  • hook("expr.new > expr, literal.object", after) - tag created object with allocation site id

Offline interpretation (Richards et al, PLDI 2010)

  • Prerequisite: Unique object numbering
  • What: save operand values/object ids
  • Where: calls, returns, allocations, property load/stores, GC

Appendix A: Brainstorming, Design and Implementation Notes

Double-callback design

The double callback design (once at emission, many times at firing) is in contrast to the design of [DiSL][] where both static and dynamic context objects are available to callbacks that fire at runtime. I do not see a good way to support the single-callback model in JSC since runtime reflection of static structure is very limited and very slow. For example, functions can be stringified with .toString() and arguments/callstack can be introspected with arguments object from within a callee.

Q: Why not inline static information into the bytestream? The debugger does this with line and column information.

A: JSC does not support variable-length opcodes. Even if it is known hook-registration time which static information is necessary, it cannot be inlined into the bytecode stream in an extensible way.

Q: Why should the client have to save static information itself, instead of having that done by the server?

A: There may be many hooks, and eagerly saving all available static information for every hook implies persisting the AST indefinitely. This is probably not acceptable performance-wise. Storing a subset is not realistic either, because the hook server cannot anticipate what subset of information every analysis will need.

Q: Can instrumentation be declared and consumed by JavaScript (Inspector) instead of C++?

A: Hypothetically, yes, but performance may be an issue. The StaticContext C++ wrapper object could be bound to JS by using IDL or by creating JSON objects. The DynamicContext objects can be exposed to script in the same way that breakpoints and logging are able to evaluate arbitrary expressions in a specific CallFrame. Performance would suffer because many objects would need to be serialized to the frontend and stored, rather than being stored in C++ data structures.

Bytecode generator notes

Each Node subclass' implementation of emitBytecode() generates bytecodes for the AST node. Subclasses of ExpressionNode have a RegisterID return value to which the return value (if any) is stored. StatementNode subclasses do not have a return value. The RegisterID* dst parameter to both emitBytecode() versions specifies the most efficient destination for the production's value, and must be honored. (The latter is a crude form of copy propagation.)

Code generation for each node is kicked off through one of the BytecodeGenerator::emitNode calls (usually; there are some exceptions, which should be found and fixed).

It should be possible to reuse the legacy profiler's means of adding instrumentation. A new opcode called instrument_hook will be emitted before/after the targeted node, and the hook id will be emitted into the bytecode stream. When executed, the slow path implementation for instrument_hook will read the id as pc[1], and call the hook server with the hook id and runtime state (i.e., ExecState and destination register, if applicable).

To emit low-level barrier instrumentation of all reads, writes, or allocations, we need to use a different strategy to interpose on these operations. One possibility is to use the existing WriteBarrier machinery to selectively emit read, write, or alloc barriers as necessary. This requires other changes, for WriteBarriers only seem to be emitted for JIT & DFG tiers right now. Also, read and alloc barriers are not implemented.

Parser and Matching notes

The JS parser produces a parse tree that does not contain up-pointers (from children to parents). In order to match selectors efficiently (from last selector towards the first---up the tree) we need to keep the tree context around during bytecode generation. We could keep a node stack during bytecode generation that is maintained by RAII inside emitNode(). Then, we consult the stack when matching selectors against the parse tree.

There is not a 1-to-1 mapping of JSC's parser nodes to the Parser API nodes. We'll need to have some sort of adapter class to reconcile the different class hierarchies. I don't think this will be too bad, as most of the differences are cases of JSC specializing the node type based on lexical information (i.e., specializing unary operators, or specializing different ways of read/writing properties).

Appendix B: TODOs, Planning, Estimates

TODOs

  • Strategy for mapping between JSC's AST nodes and Parser API nodes
  • Static context available to callbacks
  • Where to add hooks during bytecode emission?
  • Flesh out hooks for example dynamic analysis
  • Hooks for basic block (counter) profiling
  • Hooks for context-sensitive basic block profiling
  • Reflection of object allocations and GC/object ID stamping

Tasks (out of date)

  • (5) define language and hooks, design document (this page)
  • (8) AST hook opcode emission and plumbing
  • (5) implement selector creation API
  • (13) StaticContext API
  • (3) DynamicContext API
  • (13) Tracing hooks API (low-level: read, write, allocation, call)
  • (8) selector matching
  • (3) support lexical scoping for selectors
  • (8) reimplement profiler hooks
  • (5) write protocol/integration tests

Appendix C: Instrumentation Hook API (C++)

typedef uint32 HookSetId;
typedef uint32 HookId;

typedef void (*EmitHookCallback)(HookId, StaticContext&);
typedef void (*FIreHookCallback)(HookId, DynamicContext&);

enum BarrierHookType {
  BarrierHookAllocations,
  BarrierHookPropertyReads,
  BarrierHookPropertyWrites,
};

class HookServer {
    HookSetId registerBarrierHook(BarrierHookType, Set<HookScope>&, FireHookCallback);
    HookSetId registerSelectorHook(ASTSelector&, HookPosition, Set<HookScope>&,
                                   EmitHookCallback, FireHookCallback);
    void unregisterHook(HookSetId);

    // other stuff...
}

class ParserContext {
  // TODO

}

Appendix D: Selector API

enum NodeType { ... };
enum NodeClass { ... };
enum NodeAttributeName { ... };
enum NodeAttributeValue { ... };
enum NodePseudoclass { ... };

class Selector {
  RefPtr<Selector> create();
  void setType(NodeType);
  void setLabel(NodeLabel);
  void addClassRequirement(NodeClass);
  void setChildSelector(RefPtr<Selector>);
  void setDescendantSelector(RefPtr<Selector>);
  void setExpectedAttributeValue(NodeAttributeName, NoteAttributeValue);
  void setPseudoClass(NodePseudoclass);
}

Types and Labels

These are largely borrowed from the Parser API.

Compared to that API, there is some normalization/flattening of statement lists, to avoid adding two cases for BlockStatement and singleton statements.


Type: EmptyStatement
Classes: Node, Statement
Labels: (none)

Type: ExpressionStatement
Classes: Node, Statement
Labels: @expression (.Expression)

Type: IfStatement
Classes: Node, Statement
Labels: @test (.Expression),
        @consequent (StatementList)
        @alternate (StatementList)

Type: LabelStatement
Classes: Node, Statement
Labels: @label (Identifier),
        @body (StatementList)

Type: BreakStatement
Classes: Node, Statement
Labels: @label (Identifier)

Type: ContinueStatement
Classes: Node, Statement
Labels: @label (Identifier)

Type: WithStatement
Classes: Node, Statement
Labels: @object (Expression),
        @body (StatementList)

Type: SwitchStatement
Classes: Node, Statement
Labels: @discriminant (Expression),
        @cases (SwitchCaseList)

Type: ReturnStatement
Classes: Node, Statement
Labels: @argument (Expression)

Type: ThrowStatement
Classes: Node, Statement
Labels: @argument (Expression)

Type: TryStatement
Classes: Node, Statement
Labels: @body (StatementList)
        @param (Identifier)
        @handler (StatementList)
        @finalizer (StatementList)

Type: WhileStatement
Classes: Node, Statement
Labels: @test (Expression),
        @body (StatementList)

Type: DoWhileStatement
Classes: Node, Statement
Labels: @test (Expression),
        @body (StatementList)

Type: ForStatement
Classes: Node, Statement
Labels: @init (VariableDeclaration or Expression),
        @test (Expression),
        @update (Expression),
        @body (StatementList)

Type: ForInStatement
Classes: Node, Statement
Labels: @left (VariableDeclaration or Expression),
        @right (Expression),
        @body (StatementList)

Type: FunctionDeclarationStatement
Classes: Node, Function, Declaration, Statement
Labels: @id (Identifier),
        @params (IdentifierList),
        @body (StatementList)

Type: VariableDeclarationStatement
Classes: Node, Statement, Declaration
Labels: @declarations (DeclarationList)
Attributes: kind (Atom=[var, let, const])

Type: VariableDeclaration
Classes: Node
Labels: @id (Identifier),
        @init (Expression)

Type: ThisExpression
Classes: Node, Expression

Type: Identifier
Classes: Node, Expression
Attributes: name (String)

Type: ArrayLiteral
Classes: Node, Expression
Labels: @elements (ExpressionList)

Type: ObjectLiteral
Classes: Node, Expression
Labels: @properties (ObjectPropertyList)

Type: StringLiteral
Classes: Node, Expression
Attributes: value (String)

Type: BooleanLiteral
Classes: Node, Expression
Attributes: value (Atom=[true, false])

Type: NullLiteral
Classes: Node, Expression

Type: NumberLiteral
Classes: Node, Expression
Attributes: value (String)

Type: RegexpLiteral
Classes: Node, Expression
Attributes: value (String)

Type: ObjectProperty
Classes: Node
Labels: @key (Literal or Identifier),
        @value (Expression),
Attributes: kind (Atom=[init, get, set])

Type: FunctionExpression
Classes: Node, Expression, Function
Labels: @id (Identifier),
        @params (IdentifierList),
        @body (StatementList)

Type: SequenceExpression
Classes: Node, Expression
Labels: @expressions (ExpressionList)

Type: UnaryExpression
Classes: Node, Expression
Labels: @operator (Atom=["-", "+", "!", "~", "typeof", "void", "delete"]),
        @argument (Expression)

Type: BinaryExpression
Classes: Node, Expression
Labels: @operator (Atom=["==", "!=", "===", "!==", "<", "<=", ">", ">=", "<<", ">>", ">>>", "+", "-", "*", "/", "%", "|", "^", "in", "instanceof"]),
        @left (Expression),
        @right (Expression)

Type: AssignmentExpression
Classes: Node, Expression
Labels: @operator (Atom=["=", "+=", "-=", "*=", "/=", "%=", "<<=", ">>=", ">>>=", "|=", "^=", "&="]),
        @left (Expression),
        @right (Expression)

Type: UpdateExpression
Classes: Node, Expression
Labels: @operator (Atom=["++", "--"]),
        @argument (Expression)

Type: LogicalExpression
Classes: Node, Expression
Labels: @operator (Atom=["||", "&&"]),
        @left (Expression),
        @right (Expression)

Type: ConditionalExpression
Classes: Node, Expression
Labels: @test (Expression),
        @alternate (Expression),
        @consequent (Expression)

Type: NewExpression
Classes: Node, Expression
Labels: @callee (Expression),
        @arguments (ExpressionList)

Type: CallExpression
Classes: Node, Expression
Labels: @callee (Expression),
        @arguments (ExpressionList)

Type: MemberExpression
Classes: Node, Expression
Labels: @object (Expression),
        @property (Identifier or Expression),
        @computed (bool)

Type: SwitchCase
Classes: Node
Labels: @test (Expression),
        @consequent (StatementList)

Appendix E: Sample program, AST, and Parser output

Sample program:

// Life, Universe, and Everything
var answer = 6 * 7;

function fact(n, pr) {
	if (n == 0) return 1;
	else return n*fact(n-1, pr);
}

fact(5);
var d = {};
d.answer = answer;

Sample pseudo-HTML

<program>
  <stmts label="body">
    <declarations class="variable" label="variable"> // var, let, const
      <declaration name="answer"> // decl type inferred from parent
	<expr class="binary" operator="*">
	  <literal class="left" value="6" />
	  <literal class="right" value="7" />
	</expr>
      </declaration>
    </declarations>
    <stmt class="function-declaration" name="fact">
      <patterns class="params">
	<identifier name="n" />
	<identifier name="pr" />
      </patterns>
      <stmt class="block">
	<stmts class="body">
	  <stmt class="if">
	    <expr class="test binary" operator="==">
	      <identifier class="left" name="n" />
	      <literal class="right" name="0" />
	    </expr>
	    <stmt class="consequent return">
	      <literal class="argument" value="1" />
	    </stmt>
	    <stmt class="alternate return">
	      <expr class="argument binary" operator="*">
		<identifier class="left" name="n" />
		<expr class="right call">
		  <identifier class="callee" name="fact" />
		  <exprs class="arguments">
		    <expr class="binary" operator="-">
		      <identifier class="left" name="n" />
		      <literal class="right" value="1" />
		    </expr>
		    <identifier name="pr" />
		  </exprs>
		</expr>
	      </expr>
	    </stmt>
	  </stmt>
	</stmts>
      </stmt>
    </stmt>
    <stmt class="expression">
      <expr class="call">
        <identifier class="callee" name="fact" />
        <exprs class="arguments">
          <literal value="5" />
        </exprs>
      </expr>
    </stmt>
    <stmt class="declaration" type="var">
      <declarations>
        <declaration class="variable">
          <identifier class="id" name="d" />
          <expr class="object">
            <properties />
          </expr>
        </declaration>
      </declarations>
    </stmt>
    <stmt class="expression">
      <expr class="assignment" operator="=">
        <expr class="member left" computed="false">
          <identifier class="object" name="d" />
          <identifier class="property" name="answer" />
        </expr>
        <identifier class="right" name="answer" />
      </expr>
    </stmt>
  </stmts>
</program>

AST for the program:

{
    "type": "Program",
    "body": [
        {
            "type": "VariableDeclaration",
            "declarations": [
                {
                    "type": "VariableDeclarator",
                    "id": {
                        "type": "Identifier",
                        "name": "answer"
                    },
                    "init": {
                        "type": "BinaryExpression",
                        "operator": "*",
                        "left": {
                            "type": "Literal",
                            "value": 6,
                            "raw": "6"
                        },
                        "right": {
                            "type": "Literal",
                            "value": 7,
                            "raw": "7"
                        }
                    }
                }
            ],
            "kind": "var"
        },
        {
            "type": "FunctionDeclaration",
            "id": {
                "type": "Identifier",
                "name": "fact"
            },
            "params": [
                {
                    "type": "Identifier",
                    "name": "n"
                },
                {
                    "type": "Identifier",
                    "name": "pr"
                }
            ],
            "defaults": [],
            "body": {
                "type": "BlockStatement",
                "body": [
                    {
                        "type": "IfStatement",
                        "test": {
                            "type": "BinaryExpression",
                            "operator": "==",
                            "left": {
                                "type": "Identifier",
                                "name": "n"
                            },
                            "right": {
                                "type": "Literal",
                                "value": 0,
                                "raw": "0"
                            }
                        },
                        "consequent": {
                            "type": "ReturnStatement",
                            "argument": {
                                "type": "Literal",
                                "value": 1,
                                "raw": "1"
                            }
                        },
                        "alternate": {
                            "type": "ReturnStatement",
                            "argument": {
                                "type": "BinaryExpression",
                                "operator": "*",
                                "left": {
                                    "type": "Identifier",
                                    "name": "n"
                                },
                                "right": {
                                    "type": "CallExpression",
                                    "callee": {
                                        "type": "Identifier",
                                        "name": "fact"
                                    },
                                    "arguments": [
                                        {
                                            "type": "BinaryExpression",
                                            "operator": "-",
                                            "left": {
                                                "type": "Identifier",
                                                "name": "n"
                                            },
                                            "right": {
                                                "type": "Literal",
                                                "value": 1,
                                                "raw": "1"
                                            }
                                        },
                                        {
                                            "type": "Identifier",
                                            "name": "pr"
                                        }
                                    ]
                                }
                            }
                        }
                    }
                ]
            },
            "rest": null,
            "generator": false,
            "expression": false
        },
        {
            "type": "ExpressionStatement",
            "expression": {
                "type": "CallExpression",
                "callee": {
                    "type": "Identifier",
                    "name": "fact"
                },
                "arguments": [
                    {
                        "type": "Literal",
                        "value": 5,
                        "raw": "5"
                    }
                ]
            }
        },
        {
            "type": "VariableDeclaration",
            "declarations": [
                {
                    "type": "VariableDeclarator",
                    "id": {
                        "type": "Identifier",
                        "name": "d"
                    },
                    "init": {
                        "type": "ObjectExpression",
                        "properties": []
                    }
                }
            ],
            "kind": "var"
        },
        {
            "type": "ExpressionStatement",
            "expression": {
                "type": "AssignmentExpression",
                "operator": "=",
                "left": {
                    "type": "MemberExpression",
                    "computed": false,
                    "object": {
                        "type": "Identifier",
                        "name": "d"
                    },
                    "property": {
                        "type": "Identifier",
                        "name": "answer"
                    }
                },
                "right": {
                    "type": "Identifier",
                    "name": "answer"
                }
            }
        }
    ]
}