October 15, 2017 Viswesh Subramanian 0Comment

If you are reading this, you acknowledge the need to understand Abstract syntax trees and you have already perused the primer here. If you have not read the primer, I suggest you start there.

Visualization is a great way to capture mental models; especially to establish an intimate relationship with the data. Given that AST’s are trees, it just makes sense to visualize the data in a hierarchical layout to substantiate our mental model.

The tool which you will be building has 2 components – a code editor and a tab with 3 sections: a tree layout, construct usage and the AST itself. If you would like to follow along, grab a copy from GitHub

Demo

AST Visualizer tool

Thanks to Open Source Software, we have all the tools at our disposal to put together a solution in no time. Our action plan:

  1. Create a page layout
  2. Insert a code editor in the left container
  3. Insert a tab in the right container
  4. Listen for code edits and generate AST
  5. Visualize AST

For the layout, let’s leverage materializecss – With this library, creating a responsive layout is a couple of divs away. 

<div class="row">
    <div class="col s12 m4 l3">
    
    </div>

    <div class="col s12 m8 l9">

    </div>
</div>

Now that we have our layout covered, let’s move on to creating our first component – the code editor. Code editors are great because it enables users to poke around your API’s and sample code snippets. CodeFlask is one such microcode editor which can be used on web pages. Its usage cannot be simpler –

var flask = new CodeFlask;
var defaultCode = "function init() { \n console.log('hello world'); \n} \ninit();";

flask.run('#my-code-wrapper', {
        language: 'js'
    });

flask.update(defaultCode);

Codeflask also provides ‘onUpdate’ hooks. As user types, the complete code block is passed as a String parameter to a callback function. 

flask.onUpdate(function (code) {
  var ast = generateAst(code);
  renderVisuals(ast);
});

Moving on, we need to transform the code into an AST. Enter Esprima – By invoking the parse method on esprima with the code string as a parameter, AST is generated.

var ast = esprima.parse(code);

Once the AST is generated, the world is for your taking. You can traverse it to make changes as desired. In our case, we use a traversal library ast-traverse to normalize the data for visualization. If you are a keen observer, you might have noticed that the AST does not necessarily have an array of elements in the ‘body’ property. Since our visualization library requires an array of children to be attached to a parent, we normalize the data by wrapping all body property with an object as an array. As we traversed, we are also at liberty to mutate values or any other constructs but for brevity, this is good enough.

We have finally arrived at the last step of our action plan – Visualizing the AST.  Since we will also be counting the constructs and displaying the AST, let’s wrap all of our content into tabs. Lucky for us, materializecss offers a tab widget. Great! statch ’em. Our first tab content will present the visual. Among the myriad javascript visualization libraries, let’s use the popular library – d3.js. It offers various layouts such as “bundle”, “chord”, “force”, “hierarchy”, “partition”, “pie”, “stack”, “histogram”, “pack”, “tree”, “cluster” and “treemap”. Our interest lies with the tree layout.

Creating a tree visual with d3.js involves declaring a tree layout, transforming the data and mapping the transformed data with the tree layout. The result is a d3 decorated object on steroids.

// declares a tree layout and assigns the size
var treemap = d3.tree()
   .size([width, height]);

// assigns the data to a hierarchy using parent-child relationships
var nodes = d3.hierarchy(treeData);

// maps the node data to the tree layout
nodes = treemap(nodes);

Once we have our data transformed and normalized, we are all set for launch. First thing first, create the base SVG element.

var svg = d3.select(container).append("svg");
..

Next, creating SVG ‘Path’ elements to connect nodes. The returned array from nodes.descendants() call is used to create paths with class ‘link’.

var link = svg.selectAll(".link")
    .data(nodes.descendants().slice(1))
    .enter().append("path")
    .attr("class", "link")
    .attr("d", function (d) {
          return "M" + d.x + "," + d.y
          + "C" + d.x + "," + (d.y + d.parent.y) / 2
          + " " + d.parent.x + "," + (d.y + d.parent.y) / 2
          + " " + d.parent.x + "," + d.parent.y;
});

The same nodes.descendants() call also feeds data to generate ‘circle’ SVG elements.

var node = g.selectAll(".node")
            .data(nodes.descendants())
            .enter().append("g")
            .attr("class", function (d) {
                return "node" +
                    (d.children ? " node--internal" : " node--leaf");
            })
            .attr("transform", function (d) {
                return "translate(" + d.x + "," + d.y + ")";
            });

node.append("circle")
    .attr("r", 10);

Once nodes are created, we append “text” element to the nodes.

node.append("text")
    .attr({
       "dy": ".35em",
       "y": function (d) {
                return d.children ? -20 : 20;
        }})
        .text(function (d) {
           return d.data.type;
        });

And that is it! There are 2 more tabs which supplement our visual – Usage & AST. To get a count of each construct type and its usage frequency, let’s reach back into our toolkit for ast-traverse.

var hash = {};
traverse(ast,{            
 post: function (node) {
  hash.hasOwnProperty(node.type) ? hash[node.type] = hash[node.type] + 1 : hash[node.type] = 1;
            }
        });

Once we have an object with type and count, create a table element, loop through every property and create a row.

Finally, to display the AST, create another instance of CodeFlask and update the editor with the AST. This could very well be a textarea but CodeFlask offers formatting and colors, so why not.

Bringing it all together, the code in the editor is transformed into an AST which is visualized and analyzed. In a future post, we can look into using AST’s to solve real software problems.