An example of a simple Domain-Specific Language for editing tangled trees.
// Generated by CoffeeScript 1.10.0
(function() {
var app;
app = new AppView({
el: 'body',
model: new Graph
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Tangled tree DSL</title>
<link rel="stylesheet" href="index.css">
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="/webvis/tmp/peg-0.9.0.min.js"></script>
<script src="//underscorejs.org/underscore-min.js"></script>
<script src="//backbonejs.org/backbone-min.js"></script>
<script src="backbone.d3view.js"></script>
<script src="//marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
<script src="tsort.js"></script>
<script src="//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>
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()
// 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);
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 {
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;
}// 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);
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
// 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);
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)
.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;
}// 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);
// 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;
}));app = new AppView
el: 'body'
model: new Graph
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;
}
{
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'
= ' '/**
* 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();
}