Tangled tree DSL

README.md

An example of a simple Domain-Specific Language for editing tangled trees.

AppView.coffee

window.AppView = Backbone.D3View.extend
  initialize: () ->
    # retrieve the grammar from an external file
    d3.text 'tangled.peg.js', (grammar) =>
      editor = new Editor
        model: @model
        grammar: grammar

      @el.appendChild(editor.el)
      editor.render()


      node_link = new NodeLink
        model: @model

      @el.appendChild(node_link.el)
      node_link.render()
      

AppView.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.AppView = Backbone.D3View.extend({
    initialize: function() {
      return d3.text('tangled.peg.js', (function(_this) {
        return function(grammar) {
          var editor, node_link;
          editor = new Editor({
            model: _this.model,
            grammar: grammar
          });
          _this.el.appendChild(editor.el);
          editor.render();
          node_link = new NodeLink({
            model: _this.model
          });
          _this.el.appendChild(node_link.el);
          return node_link.render();
        };
      })(this));
    }
  });

}).call(this);

backbone.d3view.js

// Backbone.D3View.js 0.3.1
// ---------------

//     (c) 2015 Adam Krebs
//     Backbone.D3View may be freely distributed under the MIT license.
//     For all details and documentation:
//     https://github.com/akre54/Backbone.D3View

(function (factory) {
  if (typeof define === 'function' && define.amd) { define(['backbone', 'd3'], factory);
  } else if (typeof exports === 'object') { module.exports = factory(require('backbone'), require('d3'));
  } else { factory(Backbone, d3); }
}(function (Backbone, d3) {

  // Cached regex to match an opening '<' of an HTML tag, possibly left-padded
  // with whitespace.
  var paddedLt = /^\s*</;

  var ElementProto = (typeof Element !== 'undefined' && Element.prototype) || {};
  var matchesSelector = ElementProto.matches ||
    ElementProto.webkitMatchesSelector ||
    ElementProto.mozMatchesSelector ||
    ElementProto.msMatchesSelector ||
    ElementProto.oMatchesSelector;

  Backbone.D3ViewMixin = {

    // A reference to the d3 selection backing the view.
    d3el: null,

    namespace: d3.ns.prefix.svg,

    $: function(selector) {
      return this.el.querySelectorAll(selector);
    },

    $$: function(selector) {
      return this.d3el.selectAll(selector);
    },

    _removeElement: function() {
      this.undelegateEvents();
      this.d3el.remove();
    },

    _createElement: function(tagName) {
      var ns = typeof this.namespace === 'function' ? this.namespace() : this.namespace;
      return ns ?
         document.createElementNS(ns, tagName) :
         document.createElement(tagName);
    },

    _setElement: function(element) {
      if (typeof element == 'string') {
        if (paddedLt.test(element)) {
          var el = document.createElement('div');
          el.innerHTML = element;
          this.el = el.firstChild;
        } else {
          this.el = document.querySelector(element);
        }
      } else {
        this.el = element;
      }

      this.d3el = d3.select(this.el);
    },

    _setAttributes: function(attributes) {
      this.d3el.attr(attributes);
    },

    // `delegate` supports two- and three-arg forms. The `selector` is optional.
    delegate: function(eventName, selector, listener) {
      if (listener === undefined) {
        listener = selector;
        selector = null;
      }

      var view = this;
      var wrapped = function(event) {
        var node = event.target,
            idx = 0,
            o = d3.event;

        d3.event = event;

        // The `event` object is stored in `d3.event` but Backbone expects it as
        // the first argument to the listener.
        if (!selector) {
          listener.call(view, d3.event, node.__data__, idx++);
          d3.event = o;
          return;
        }

        while (node && node !== view.el) {
          if (matchesSelector.call(node, selector)) {
            listener.call(view, d3.event, node.__data__, idx++);
          }
          node = node.parentNode;
        }
        d3.event = o;
      };

      var map = this._domEvents || (this._domEvents = {});
      var handlers = map[eventName] || (map[eventName] = []);
      handlers.push({selector: selector, listener: listener, wrapped: wrapped});

      this.el.addEventListener(eventName, wrapped, false);
      return this;
    },

    undelegate: function(eventName, selector, listener) {
      if (!this._domEvents || !this._domEvents[eventName]) return;

      if (typeof selector !== 'string') {
        listener = selector;
        selector = null;
      }

      var handlers = this._domEvents[eventName].slice();
      var i = handlers.length;
      while (i--) {
        var handler = handlers[i];

        var match = (listener ? handler.listener === listener : true) &&
            (selector ? handler.selector === selector : true);

        if (!match) continue;

        this.el.removeEventListener(eventName, handler.wrapped, false);
        this._domEvents[eventName].splice(i, 1);
      }
    },

    undelegateEvents: function() {
      var map = this._domEvents, el = this.el;
      if (!el || !map) return;

      Object.keys(map).forEach(function(eventName) {
        map[eventName].forEach(function(handler) {
          el.removeEventListener(eventName, handler.wrapped, false);
        });
      });

      this._domEvents = {};
      return this;
    }
  };

  Backbone.D3View = Backbone.View.extend(Backbone.D3ViewMixin);

  return Backbone.D3View;
}));

Editor.coffee

window.Editor = Backbone.D3View.extend
  namespace: null
  tagName: 'div'
    
  initialize: (conf) ->
    @d3el.classed 'Editor', true
    
    # Chrome bug workaround (https://github.com/codemirror/CodeMirror/issues/3679)
    editor_div = @d3el.append 'div'
      .attr
        class: 'editor_div'
      .style
        position: 'relative'

    wrapper = editor_div.append 'div'
      .style
        position: 'absolute'
        height: '100%'
        width: '100%'
        
    @status_bar = @d3el.append 'div'
      .attr
        class: 'status_bar'
    
    @parser = PEG.buildParser conf.grammar
    
    @editor = CodeMirror wrapper.node(), {
      lineNumbers: true,
      lineWrapping: true,
      keyMap: 'sublime',
      value: '''
        # indentation is used to build the tree
        Figura
          Triangolo
            Equilatero
            Isoscele
            Scaleno
          Quadrilatero
            Trapezio
              Parallelogramma
                Rettangolo
                  Quadrato
                Rombo
                  # repeat an identifier to
                  # define more than a single
                  # parent node
                  Quadrato

        # it is also possible to define another
        # connected component...
        Animale
          Gatto
          Cane

        # ...or to merge another tree with an
        # existing one
        Gatto
          Siamese
          Persiano
      '''
      extraKeys: {
        Tab: (cm) ->
          # replace tab with spaces
          if cm.somethingSelected()
            cm.indentSelection('add')
          else
            cm.replaceSelection(Array(cm.getOption('indentUnit') + 1).join(' '), 'end', '+input')
      }
    }

    @editor.on 'change', () =>
      @compile()
  
    @compile()
    
  render: () ->
    @editor.refresh()
  
  compile: () ->
    @status_bar.text 'All ok.'
    @status_bar.classed 'error', false
    
    try
      graph = @parser.parse @editor.getValue()
      @highlight_code graph
      @model.update graph
    catch e
      @status_bar.text "Line #{e.location.start.line}: #{e.message}"
      @status_bar.classed 'error', true
      
  highlight_code: (graph) ->
    # clear highlighting
    @editor.getAllMarks().forEach (mark) ->
      mark.clear()
      
    graph.nodes.forEach (d) =>
      if not d.dummy
        @editor.markText {line: d.code_location.start.line-1, ch: d.code_location.start.column-1}, {line: d.code_location.end.line-1, ch: d.code_location.end.column-1}, {className: 'node_def'}

    graph.node_refs.forEach (d) =>
      @editor.markText {line: d.code_location.start.line-1, ch: d.code_location.start.column-1}, {line: d.code_location.end.line-1, ch: d.code_location.end.column-1}, {className: 'node_ref'}
      
    graph.comments.forEach (d) =>
      @editor.markText {line: d.code_location.start.line-1, ch: d.code_location.start.column-1}, {line: d.code_location.end.line-1, ch: d.code_location.end.column-1}, {className: 'comment'}
    

Editor.css

.Editor {
  display: flex;
  flex-direction: column;
}
.Editor .editor_div {
  flex-grow: 1;
  height: 0;
}

.Editor .CodeMirror {
  height: 100%;
  font-size: 12px;
  line-height: 1.3;
  color: #999;
  background: #FFF;
}

.Editor .status_bar {
  height: 22px;
  background: #DDD;
  border-top: 1px solid gray;
  font-family: sans-serif;
  font-size: 12px;
  padding: 4px;
  box-sizing: border-box;
}
.Editor .error {
  background: #F77;
}

.Editor .node_def {
  color: black;
}
.Editor .node_ref {
  color: black;
  font-style: italic;
}
.Editor .comment {
  color: #509050;
  font-style: italic;
}

Editor.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.Editor = Backbone.D3View.extend({
    namespace: null,
    tagName: 'div',
    initialize: function(conf) {
      var editor_div, wrapper;
      this.d3el.classed('Editor', true);
      editor_div = this.d3el.append('div').attr({
        "class": 'editor_div'
      }).style({
        position: 'relative'
      });
      wrapper = editor_div.append('div').style({
        position: 'absolute',
        height: '100%',
        width: '100%'
      });
      this.status_bar = this.d3el.append('div').attr({
        "class": 'status_bar'
      });
      this.parser = PEG.buildParser(conf.grammar);
      this.editor = CodeMirror(wrapper.node(), {
        lineNumbers: true,
        lineWrapping: true,
        keyMap: 'sublime',
        value: '# indentation is used to build the tree\nFigura\n  Triangolo\n    Equilatero\n    Isoscele\n    Scaleno\n  Quadrilatero\n    Trapezio\n      Parallelogramma\n        Rettangolo\n          Quadrato\n        Rombo\n          # repeat an identifier to\n          # define more than a single\n          # parent node\n          Quadrato\n\n# it is also possible to define another\n# connected component...\nAnimale\n  Gatto\n  Cane\n\n# ...or to merge another tree with an\n# existing one\nGatto\n  Siamese\n  Persiano',
        extraKeys: {
          Tab: function(cm) {
            if (cm.somethingSelected()) {
              return cm.indentSelection('add');
            } else {
              return cm.replaceSelection(Array(cm.getOption('indentUnit') + 1).join(' '), 'end', '+input');
            }
          }
        }
      });
      this.editor.on('change', (function(_this) {
        return function() {
          return _this.compile();
        };
      })(this));
      return this.compile();
    },
    render: function() {
      return this.editor.refresh();
    },
    compile: function() {
      var e, error, graph;
      this.status_bar.text('All ok.');
      this.status_bar.classed('error', false);
      try {
        graph = this.parser.parse(this.editor.getValue());
        this.highlight_code(graph);
        return this.model.update(graph);
      } catch (error) {
        e = error;
        this.status_bar.text("Line " + e.location.start.line + ": " + e.message);
        return this.status_bar.classed('error', true);
      }
    },
    highlight_code: function(graph) {
      this.editor.getAllMarks().forEach(function(mark) {
        return mark.clear();
      });
      graph.nodes.forEach((function(_this) {
        return function(d) {
          if (!d.dummy) {
            return _this.editor.markText({
              line: d.code_location.start.line - 1,
              ch: d.code_location.start.column - 1
            }, {
              line: d.code_location.end.line - 1,
              ch: d.code_location.end.column - 1
            }, {
              className: 'node_def'
            });
          }
        };
      })(this));
      graph.node_refs.forEach((function(_this) {
        return function(d) {
          return _this.editor.markText({
            line: d.code_location.start.line - 1,
            ch: d.code_location.start.column - 1
          }, {
            line: d.code_location.end.line - 1,
            ch: d.code_location.end.column - 1
          }, {
            className: 'node_ref'
          });
        };
      })(this));
      return graph.comments.forEach((function(_this) {
        return function(d) {
          return _this.editor.markText({
            line: d.code_location.start.line - 1,
            ch: d.code_location.start.column - 1
          }, {
            line: d.code_location.end.line - 1,
            ch: d.code_location.end.column - 1
          }, {
            className: 'comment'
          });
        };
      })(this));
    }
  });

}).call(this);

Graph.coffee

window.Graph = Backbone.Model.extend
  defaults:
    graph: {
      dummy_root: null
      nodes: []
      links: []
      node_refs: []
      comments: []
    }
    
  update: (graph) ->
    # compute link ids and mark links as directed
    graph.links.forEach (l) ->
      l.directed = true
      l.id = l.source.id + '->' + l.target.id
    
    @set 'graph', graph
    

Graph.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.Graph = Backbone.Model.extend({
    defaults: {
      graph: {
        dummy_root: null,
        nodes: [],
        links: [],
        node_refs: [],
        comments: []
      }
    },
    update: function(graph) {
      graph.links.forEach(function(l) {
        l.directed = true;
        return l.id = l.source.id + '->' + l.target.id;
      });
      return this.set('graph', graph);
    }
  });

}).call(this);

index.coffee

app = new AppView
  el: 'body'
  model: new Graph

index.css

html, body {
  margin: 0;
  padding: 0;
  width: 100%;
  height: 100%;
  overflow: hidden;
}

body {
  display: flex;
  flex-direction: row;
}

.editor {
  width: 0;
  flex-grow: 1;
  border-right: 2px solid gray;
}

.node_link {
  width: 0;
  flex-grow: 2;
}

index.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Tangled tree DSL</title>
    <link rel="stylesheet" href="index.css">
    <script src="http://d3js.org/d3.v3.min.js"></script>
    <script src="/webvis/tmp/peg-0.9.0.min.js"></script>
    <script src="http://underscorejs.org/underscore-min.js"></script>
    <script src="http://backbonejs.org/backbone-min.js"></script>
    <script src="backbone.d3view.js"></script>
    <script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
    <script src="tsort.js"></script>
    <script src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.0/lodash.min.js"></script>
    
    <link type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/codemirror.min.css" rel="stylesheet"/>
    <script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/codemirror.min.js"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/codemirror/4.6.0/keymap/sublime.js"></script>
    
    <!-- your views go here -->
    <script src="AppView.js"></script>
    <script src="Editor.js"></script>
    <link rel="stylesheet" href="Editor.css">
    <script src="NodeLink.js"></script>
    <link rel="stylesheet" href="NodeLink.css">
    
    <!-- your models go here -->
    <script src="Graph.js"></script>
  </head>
  <body>
    <script src="index.js"></script>
  </body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var app;

  app = new AppView({
    el: 'body',
    model: new Graph
  });

}).call(this);

NodeLink.coffee

R = 20

window.NodeLink = Backbone.D3View.extend
  tagName: 'svg'
  
  initialize: () ->
    @d3el.classed 'node_link', true

    defs = @d3el.append 'defs'

    # define arrow markers for graph links
    defs.append 'marker'
      .attr
        id: 'end-arrow'
        viewBox: '0 0 10 10'
        refX: 4+R
        refY: 5
        orient: 'auto'
    .append 'path'
      .attr
        d: 'M0,0 L0,10 L10,5 z'
        
    # append a group for zoomable content
    zoomable_layer = @d3el.append('g')

    zoom = d3.behavior.zoom()
      .scaleExtent([-Infinity,Infinity])
      .on 'zoom', () ->
        zoomable_layer
          .attr
            transform: "translate(#{zoom.translate()})scale(#{zoom.scale()})"

    @d3el.call(zoom)

    # compansate for dummy nodes translation
    graph_layer = zoomable_layer.append 'g'
      .attr
        transform: "translate(0,#{-2*R})"
        
    # create two layers for nodes and links
    @links_layer = graph_layer.append 'g'
    @nodes_layer = graph_layer.append 'g'
    
    throttled_render = _.debounce (() =>
      @render()
    ), 800, {trailing: true}
    
    @listenTo @model, 'change:graph', throttled_render
  
  render: () ->
    width = @el.getBoundingClientRect().width
    height = @el.getBoundingClientRect().height

    graph = @model.get 'graph'
    
    ### store the node index into the node itself ###
    for n, i in graph.nodes
      n.i = i

    ### store neighbor nodes into each node ###
    for n, i in graph.nodes
      n.in_neighbors = []
      n.out_neighbors = []

    for l in graph.links
      l.source.out_neighbors.push l.target
      l.target.in_neighbors.push l.source

    ### compute longest distances ###
    topological_order = tsort(graph.links.map (l) -> [l.source.i, l.target.i])
    # console.debug 'Topological order: ' + topological_order

    for n in graph.nodes
      n.longest_dist = -Infinity

    # initialize root nodes
    graph.dummy_root.longest_dist = 0

    for i in topological_order
      n = graph.nodes[i]
      for nn in n.out_neighbors
        if nn.longest_dist < n.longest_dist+1
          nn.longest_dist = n.longest_dist+1
          
    
    ### CONSTRAINTS ###
    
    graph.constraints = []

    ### create the alignment contraints ###
    levels = _.uniq graph.nodes.map (n) -> n.longest_dist
    levels.forEach (depth) ->
      graph.constraints.push {
        type: 'alignment',
        axis: 'y',
        offsets: graph.nodes.filter((n) -> n.longest_dist is depth).map (n) -> {
          node: n.i,
          offset: 0
        }
      }

    PAD_MULTIPLIER = 3.5

    ### create the position contraints ###
    levels.forEach (depth, i) ->
      if i < levels.length-1
        n1 = _.find graph.nodes, (n) -> n.longest_dist is depth
        n2 = _.find graph.nodes, (n) -> n.longest_dist is depth+1
        graph.constraints.push {
          axis: 'y',
          left: n1.i,
          right: n2.i,
          gap: 2*R
        }
    
    # draw nodes
    nodes = @nodes_layer.selectAll '.node'
      .data graph.nodes, (d) -> d.id

    enter_nodes = nodes.enter().append 'g'
      .attr
        class: 'node'
        display: (d) -> if d.dummy then 'none' else null

    enter_nodes.append 'circle'
      .attr
        r: R

    # draw the label
    enter_nodes.append 'text'
      .text (d) -> d.id
      .attr
        dy: '0.35em'
      
    nodes.exit()
      .remove()
      
    # draw links
    links = @links_layer.selectAll '.link'
      .data graph.links, (d) -> d.id

    links
      .enter().append 'line'
        .attr
          class: 'link'
          display: (d) -> if d.source.dummy or d.target.dummy then 'none' else null
    
    links
      .classed 'directed', (d) -> d.directed
        
    links.exit()
      .remove()

    ### cola layout ###
    graph.nodes.forEach (v) ->
      v.width = 3*R
      v.height = 3*R

    d3cola = cola.d3adaptor()
      .size([width, height])
      .linkDistance(60)
      .avoidOverlaps(true)
      .constraints(graph.constraints)
      .nodes(graph.nodes)
      .links(graph.links)
      .on 'tick', () ->
        # update nodes and links
        nodes
          .attr('transform', (d) -> "translate(#{d.x},#{d.y})")

        links
          .attr('x1', (d) -> d.source.x)
          .attr('y1', (d) -> d.source.y)
          .attr('x2', (d) -> d.target.x)
          .attr('y2', (d) -> d.target.y)
          
    drag = d3cola.drag()
    drag.on 'dragstart', () ->
      # silence other listener
      d3.event.sourceEvent.stopPropagation()
      
    nodes
      .call(drag)
      
    d3cola.start(100,30,30)
    

NodeLink.css

.node_link .node > circle {
  
  fill: #EDD;
  stroke: #A99;
  stroke-width: 2px;
}

.node_link .node > text {
  font-family: sans-serif;
  text-anchor: middle;
  pointer-events: none;
  font-weight: bold;
  font-size: 12px;
  text-shadow: -1px -1px white, -1px 1px white, 1px 1px white, 1px -1px white, -1px 0 white, 0 1px white, 1px 0 white, 0 -1px white;
  
  -webkit-touch-callout: none; /* iOS Safari */
  -webkit-user-select: none;   /* Chrome/Safari/Opera */
  -khtml-user-select: none;    /* Konqueror */
  -moz-user-select: none;      /* Firefox */
  -ms-user-select: none;       /* IE/Edge */
  user-select: none;           /* non-prefixed version, currently
                                  not supported by any browser */
}

.node_link .link {
  stroke: #CCD;
  stroke-width: 4px;
  opacity: 0.6;
}
.node_link .directed.link {
  marker-end: url(#end-arrow);
}
.node_link #end-arrow {
  fill: #CCD;
}

NodeLink.js

// Generated by CoffeeScript 1.10.0
(function() {
  var R;

  R = 20;

  window.NodeLink = Backbone.D3View.extend({
    tagName: 'svg',
    initialize: function() {
      var defs, graph_layer, throttled_render, zoom, zoomable_layer;
      this.d3el.classed('node_link', true);
      defs = this.d3el.append('defs');
      defs.append('marker').attr({
        id: 'end-arrow',
        viewBox: '0 0 10 10',
        refX: 4 + R,
        refY: 5,
        orient: 'auto'
      }).append('path').attr({
        d: 'M0,0 L0,10 L10,5 z'
      });
      zoomable_layer = this.d3el.append('g');
      zoom = d3.behavior.zoom().scaleExtent([-Infinity, Infinity]).on('zoom', function() {
        return zoomable_layer.attr({
          transform: "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")"
        });
      });
      this.d3el.call(zoom);
      graph_layer = zoomable_layer.append('g').attr({
        transform: "translate(0," + (-2 * R) + ")"
      });
      this.links_layer = graph_layer.append('g');
      this.nodes_layer = graph_layer.append('g');
      throttled_render = _.debounce(((function(_this) {
        return function() {
          return _this.render();
        };
      })(this)), 800, {
        trailing: true
      });
      return this.listenTo(this.model, 'change:graph', throttled_render);
    },
    render: function() {
      var PAD_MULTIPLIER, d3cola, drag, enter_nodes, graph, height, i, j, k, l, len, len1, len2, len3, len4, len5, levels, links, m, n, nn, nodes, o, p, q, ref, ref1, ref2, ref3, ref4, topological_order, width;
      width = this.el.getBoundingClientRect().width;
      height = this.el.getBoundingClientRect().height;
      graph = this.model.get('graph');

      /* store the node index into the node itself */
      ref = graph.nodes;
      for (i = j = 0, len = ref.length; j < len; i = ++j) {
        n = ref[i];
        n.i = i;
      }

      /* store neighbor nodes into each node */
      ref1 = graph.nodes;
      for (i = k = 0, len1 = ref1.length; k < len1; i = ++k) {
        n = ref1[i];
        n.in_neighbors = [];
        n.out_neighbors = [];
      }
      ref2 = graph.links;
      for (m = 0, len2 = ref2.length; m < len2; m++) {
        l = ref2[m];
        l.source.out_neighbors.push(l.target);
        l.target.in_neighbors.push(l.source);
      }

      /* compute longest distances */
      topological_order = tsort(graph.links.map(function(l) {
        return [l.source.i, l.target.i];
      }));
      ref3 = graph.nodes;
      for (o = 0, len3 = ref3.length; o < len3; o++) {
        n = ref3[o];
        n.longest_dist = -Infinity;
      }
      graph.dummy_root.longest_dist = 0;
      for (p = 0, len4 = topological_order.length; p < len4; p++) {
        i = topological_order[p];
        n = graph.nodes[i];
        ref4 = n.out_neighbors;
        for (q = 0, len5 = ref4.length; q < len5; q++) {
          nn = ref4[q];
          if (nn.longest_dist < n.longest_dist + 1) {
            nn.longest_dist = n.longest_dist + 1;
          }
        }
      }

      /* CONSTRAINTS */
      graph.constraints = [];

      /* create the alignment contraints */
      levels = _.uniq(graph.nodes.map(function(n) {
        return n.longest_dist;
      }));
      levels.forEach(function(depth) {
        return graph.constraints.push({
          type: 'alignment',
          axis: 'y',
          offsets: graph.nodes.filter(function(n) {
            return n.longest_dist === depth;
          }).map(function(n) {
            return {
              node: n.i,
              offset: 0
            };
          })
        });
      });
      PAD_MULTIPLIER = 3.5;

      /* create the position contraints */
      levels.forEach(function(depth, i) {
        var n1, n2;
        if (i < levels.length - 1) {
          n1 = _.find(graph.nodes, function(n) {
            return n.longest_dist === depth;
          });
          n2 = _.find(graph.nodes, function(n) {
            return n.longest_dist === depth + 1;
          });
          return graph.constraints.push({
            axis: 'y',
            left: n1.i,
            right: n2.i,
            gap: 2 * R
          });
        }
      });
      nodes = this.nodes_layer.selectAll('.node').data(graph.nodes, function(d) {
        return d.id;
      });
      enter_nodes = nodes.enter().append('g').attr({
        "class": 'node',
        display: function(d) {
          if (d.dummy) {
            return 'none';
          } else {
            return null;
          }
        }
      });
      enter_nodes.append('circle').attr({
        r: R
      });
      enter_nodes.append('text').text(function(d) {
        return d.id;
      }).attr({
        dy: '0.35em'
      });
      nodes.exit().remove();
      links = this.links_layer.selectAll('.link').data(graph.links, function(d) {
        return d.id;
      });
      links.enter().append('line').attr({
        "class": 'link',
        display: function(d) {
          if (d.source.dummy || d.target.dummy) {
            return 'none';
          } else {
            return null;
          }
        }
      });
      links.classed('directed', function(d) {
        return d.directed;
      });
      links.exit().remove();

      /* cola layout */
      graph.nodes.forEach(function(v) {
        v.width = 3 * R;
        return v.height = 3 * R;
      });
      d3cola = cola.d3adaptor().size([width, height]).linkDistance(60).avoidOverlaps(true).constraints(graph.constraints).nodes(graph.nodes).links(graph.links).on('tick', function() {
        nodes.attr('transform', function(d) {
          return "translate(" + d.x + "," + d.y + ")";
        });
        return links.attr('x1', function(d) {
          return d.source.x;
        }).attr('y1', function(d) {
          return d.source.y;
        }).attr('x2', function(d) {
          return d.target.x;
        }).attr('y2', function(d) {
          return d.target.y;
        });
      });
      drag = d3cola.drag();
      drag.on('dragstart', function() {
        return d3.event.sourceEvent.stopPropagation();
      });
      nodes.call(drag);
      return d3cola.start(100, 30, 30);
    }
  });

}).call(this);

tangled.peg.js

{
  var prev_indentation = -1;
  var node_index = {};
  var graph = {
    dummy_root: {
      id: '',
      dummy: true
    },
    nodes: [],
    links: [],
    node_refs: [],
    comments: []
  };
  graph.nodes.push(graph.dummy_root);
  var nodes_stack = [graph.dummy_root];
}

start
  = first:Line rest:('\n' Line)* {
    var line_list = [first].concat(rest.map(function(d){ return d[1]; }));
    var node_list = line_list.filter(function(d){ return d.id != null; });
    var comment_list = line_list.filter(function(d){ return d.comment; });

    node_list.forEach(function(d){
      // create node if not already found
      if(!node_index.hasOwnProperty(d.id)) {
        node_index[d.id] = d;
        graph.nodes.push(d);
      }
      else {
        // store this node as a reference node
        d.definition = node_index[d.id];
        graph.node_refs.push(d);
      }
      // retrieve the current node indentation
      var indentation = d.indentation;
      
      // always use the stored reference
      d = node_index[d.id];
      
      // use indentation to infer links
      var delta = indentation - prev_indentation;
      
      if(delta > 0) {
        // this is a child node
        graph.links.push({
          source: nodes_stack[nodes_stack.length-1],
          target: d
        });
        nodes_stack.push(d);
      } else if(delta == 0) {
        // this is a sibling node
        nodes_stack.pop();
        graph.links.push({
          source: nodes_stack[nodes_stack.length-1],
          target: d
        });
        nodes_stack.push(d);
      } else { // delta < 0
        // find a node with equal indentation
        var i;
        var found = false;
        for(i in nodes_stack) {
          if(nodes_stack[i].indentation == indentation) {
            found = true;
            break;
          }
        }
        if(!found) {
          throw {
            message: 'Inconsistent indentation',
            location: d.code_location
          };
        }
          
        nodes_stack = nodes_stack.slice(0,parseInt(i)+1);
        // this is a sibling node
        nodes_stack.pop();
        graph.links.push({
          source: nodes_stack[nodes_stack.length-1],
          target: d
        });
        nodes_stack.push(d);
      }
      prev_indentation = indentation;
    });

    node_list.forEach(function(d){
      delete d.indentation; // no longer meaningful
    });

    comment_list.forEach(function(d){
      graph.comments.push(d);
    });

    return graph;
  }

Line 'line'
  = CommentLine / NodeLine

NodeLine 'node line'
  = w:Whitespace* n:Node? { return {indentation: w.length, id: n, code_location: location()}; }
  
CommentLine 'comment line'
  = w:Whitespace* '#' [^\n]* { return {comment: true, code_location: location()}; }


Node 'identifier'
  = [_a-zA-Z0-9]+ { return text(); }

Whitespace 'whitespace'
  = ' '

thumbnail.png

tsort.js

/**
 * general topological sort
 * @author SHIN Suzuki (shinout310@gmail.com)
 * @param Array<Array> edges : list of edges. each edge forms Array<ID,ID> e.g. [12 , 3]
 *
 * @returns Array : topological sorted list of IDs
 **/

function tsort(edges) {
  var nodes   = {}, // hash: stringified id of the node => { id: id, afters: lisf of ids }
      sorted  = [], // sorted list of IDs ( returned value )
      visited = {}; // hash: id of already visited node => true

  var Node = function(id) {
    this.id = id;
    this.afters = [];
  };

  // 1. build data structures
  edges.forEach(function(v) {
    var from = v[0], to = v[1];
    if (!nodes[from]) nodes[from] = new Node(from);
    if (!nodes[to]) nodes[to]     = new Node(to);
    nodes[from].afters.push(to);
  });

  // 2. topological sort
  Object.keys(nodes).forEach(function visit(idstr, ancestors) {
    var node = nodes[idstr],
        id   = node.id;

    // if already exists, do nothing
    if (visited[idstr]) return;

    if (!Array.isArray(ancestors)) ancestors = [];

    ancestors.push(id);

    visited[idstr] = true;

    node.afters.forEach(function(afterID) {
      if (ancestors.indexOf(afterID) >= 0)  // if already in ancestors, a closed chain exists.
        throw new Error('closed chain : ' +  afterID + ' is in ' + id);

      visit(afterID.toString(), ancestors.map(function(v) { return v })); // recursive call
    });

    sorted.unshift(id);
  });

  return sorted;
}

/**
 * TEST
 **/
function tsortTest() {

  // example 1: success
  var edges = [
    [1, 2],
    [1, 3],
    [2, 4],
    [3, 4]
  ];

  var sorted = tsort(edges);
  console.log(sorted);

  // example 2: failure ( A > B > C > A )
  edges = [
    ['A', 'B'],
    ['B', 'C'],
    ['C', 'A']
  ];

  try {
    sorted = tsort(edges);
  }
  catch (e) {
    console.log(e.message);
  }

  // example 3: generate random edges
  var max = 100, iteration = 30;
  function randomInt(max) {
    return Math.floor(Math.random() * max) + 1;
  }

  edges = (function() {
    var ret = [], i = 0;
    while (i++ < iteration) ret.push( [randomInt(max), randomInt(max)] );
    return ret;
  })();

  try {
    sorted = tsort(edges);
    console.log("succeeded", sorted);
  }
  catch (e) {
    console.log("failed", e.message);
  }

}


// for node.js
if (typeof exports == 'object' && exports === this) {
  module.exports = tsort;
  if (process.argv[1] === __filename) tsortTest();
}