Tuesday, January 3, 2017
The Shift Semantics library defines a structure for representing the behaviour of an ECMAScript program as well as a function for deriving one of these structures from a Shift AST.
While ECMAScript has many syntactic features, not every one of them maps to a
unique behaviour. For instance, all static member accesses (
a.b) can be
represented in terms of computed member accesses on strings (
a['b']), and all
for loops can be written in terms of
while loops. Shift Semantics defines a
data structure called an abstract semantic graph (ASG) which has a node for
each individual operation that an ECMAScript interpreter would need to be able
to interpret all ECMAScript programs. When an ASG is created, information about
the original syntactic representation is lost. Only the important bit about
what that program is supposed to do remains.
Why is this useful?
Many use cases for ECMAScript tooling do not involve knowledge of the original representation of the program. For instance, if one is compiling an ECMAScript program to another lower-level language, it is convenient to define a compilation once for all loops instead of repeating much of the same code for each looping construct in the language. This greatly reduces the number of structures you have to consider for your transformation/analysis and eliminates any need for code duplication.
What does it look like?
There are 52 ASG nodes. Many of them have an obvious meaning: Loop,
MemberAccess, GlobalReference, LiteralNumber, etc. Others are not as
obvious. Keys is an
Object.keys analogue, used to represent the for-in
behaviour of retrieiving enumerable keys of an object before looping over them.
RequireObjectCoercible represents the internal spec operation of the same name.
Halt explicitly indicates that the program has run to completion, though it’s
also allowed to be used in other places within the graph if one desires.
Update: If you’d like to see GraphViz visualisations, see the examples in Pull Request #8 or run the visualiser yourself on a program of your choosing.
How do I use it?
If you don’t already have a Shift AST for your program, you will need to use the parser to create one:
import com.shapesecurity.shift.parser.Parser; String js = "f(0);"; // if you have a script Script script = Parser.parseScript(js); // if you have a module Module module = Parser.parseModule(js);
Once you have your Shift AST, pass it to the Explicator:
import com.shapesecurity.shift.semantics.Explicator; Semantics semantics = Explicator.deriveSemantics(program);
Semantics object’s fields, including the ASG, can be accessed directly.
One can also define a reducer, in the same way a reducer is defined over a
Shift AST: subclassing the ReconstructingReducer. Note that our ASG reducers
have not yet been open-sourced, but will be soon.
Currently, WithStatements and direct calls to
eval are explicated into Halt
nodes. There’s no reason that these cannot be supported, but they were not part
of the initial effort. Similarly, not all of ECMAScript 2015 and beyond is
supported. We will be adding support for newer ECMAScript features piece by
piece as development continues.
Thanks to Shape engineer Kevin Gibbons for figuring out all the hard problems during the design of the ASG.