rjpower/index.html

## index.html
<!DOCTYPE html>
<!-- Some path computation code borrowed form http://bl.ocks.org/rkirsling/5001347 -->
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<title>Transaction Chain Viz</title>

<script type='text/javascript' src='http://d3js.org/d3.v3.min.js'></script>
<script type='text/javascript' src='http://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.2.1/lodash.min.js'></script>
<script type='text/javascript' src='http://cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js'></script>

<style type='text/css'>
svg {
  border: 1px solid black;
}

text {
  font-weight: 300;
  font-family: "Helvetica Neue", Helvetica, Arial, sans-serf;
  font-size: 14px;
}

rect {
  fill: #fff;
}

.node rect {
  stroke-width: 2px;
  stroke: #333;
  fill: none;
}

#node-CLOSED rect {
  fill: #f77;
}

#node-ESTAB rect {
  fill: #7f7;
}

.edge rect {
  fill: #fff;
}

.edge path {
  fill: none;
  stroke: #333;
  stroke-width: 1.5px;
}
</style>
</head>

<body>
  <textarea cols=60 rows=10 id="code">
MakeChain("Bid")
.add("Add", "bids", WRITE)
.add("UpdatePrice", "items", WRITE);

MakeChain("GetPrice")
.add("Read", "items", READ)

Commutes("Add", "Add");
Commutes("UpdatePrice", "UpdatePrice");
  </textarea>
  <textarea cols=60 rows=10 id="log" style="editable: false">
  </textarea>
  <br>
  <input type="submit" onClick="javascript:updateGraph()"></input>
  <br>
  <svg id="canvas" width="100%" height="50%"></svg>
</body>

<script type='text/javascript'>
  WRITE = 0;
  READ = 1;
  CYCLE = 2;

  S = "S";
  C = "C";
  COMMUTATIVE = "COMMUTATIVE";

  FORWARD = 0;
  BACKWARD = 1;

  idForType = {};
  idForType[S] = 1;
  idForType[C] = 2;
  idForType[COMMUTATIVE] = 3;

  // strongly connected components
  function SCC(hops, links) {
    var index = 0;
    var components = [];
    var C = [];
    for (i in hops) {
      hops[i].scc_index = -1;
      hops[i].low_link = -1;
    }

    function visit(h) {
      h.scc_index = h.low_link = index;
      index += 1;

      C.push(h);
      for (var j in links) {
        var l = links[j];
        if (l.source != h) { continue; }
        var t = l.target;
        if (t.scc_index == -1) {
          visit(t);
          h.low_link = _.min([h.low_link, t.low_link]);
        } else {
          h.low_link = _.min([h.low_link, t.scc_index]);
        }
      }

      if (h.low_link == h.scc_index) {
        var new_c = []
        do {
          var back = C.pop();
          new_c.push(back);
        } while (back != h);

        components.push(new_c);
      }
    }

    for (var i in hops) {
      var h = hops[i];
      if (h.scc_index != -1) { continue; }
      visit(h);
    }

    return components;
  }

  function Hop(name, table, type, pos) {
    this.name = name;
    this.table = table;
    this.type = type;
    this.pos = pos;
    this.visited = []
  }

  Hop.prototype.id = function() {
    return this.name + "-" + this.table;
  }

  function Chain(name) {
    this.name = name;
    this.hops = [];
  }

  Chain.prototype.add = function(name, table, type) {
    var h = new Hop(name, table, type, this.hops.length);
    this.hops.push(h);
    return this;
  }

  Chain.prototype.links = function() {
    var links = []
    for (var i in this.hops) {
      if (i > 0) {
        if (this.type == FORWARD) {
          links.push({"source" : this.hops[i - 1], "target" : this.hops[i], "type" : S});
        } else {
          links.push({"source" : this.hops[i], "target" : this.hops[i - 1], "type" : S});
        }
      }
    }
    return links;
  }

  Chain.prototype.copy = function(type) {
    var c = new Chain();
    c.name = this.name;
    c.type = type;
    c.hops = _.map(this.hops, function(h) {
      return new Hop(h.name + "." + type, h.table, h.type, h.pos)
    });
    return c;
  }

  function getHops(chains) {
    return _(chains)
             .map(function(c) { return c.hops; })
             .flatten()
             .value();
  }

  function commutes(a, b) {
    for (var i = 0; i < World.commutes.length; ++i) {
      var s = World.commutes[i][0];
      var e = World.commutes[i][1];
      if (a.name.substring(0, s.length) == s &&
          b.name.substring(0, e.length) == e) {
        return true;
      }
      if (b.name.substring(0, s.length) == s &&
          a.name.substring(0, e.length) == e) {
        return true;
      }
    }
    return false;
  }

  function getLinks(hops) {
    var sLinks = _(chains)
      .map(function(c) { return c.links(); })
      .flatten()
      .value();

    var cLinks = [];
    for(i in hops) {
      for (j in hops) {
        if (i == j) { continue; }
        var hi = hops[i];
        var hj = hops[j];

        if (hi.table == hj.table && (hi.type == WRITE || hj.type == WRITE)) {
          if (commutes(hi, hj)) {
            // drop edge
            // cLinks.push({ "source" : hi, "target" : hj, type : COMMUTATIVE });
          } else {
            cLinks.push({ "source" : hi, "target" : hj, type : C });
          }
        }
      }
    }

    return _.flatten([sLinks, cLinks]);
  }

  function MakeChain(name) {
    var c = new Chain(name);
    World.chains.push(c);
    return c;
  }

  function Commutes(a, b) {
    World.commutes.push([a, b]);
  }

  function updateGraph() {
    var log = document.getElementById("log");
    log.value = "";
    log.disabled = true;

    try {
      _update();
    } catch(err) {
      log.value += err;
    }
  }
  function _update() {
    var code = document.getElementById("code").value;
    var scale = d3.scale.category10();

    World = function() {};
    World.chains = [];
    World.commutes = [];

    eval(code);
    chains = _(World.chains).map(function(c) { return [c.copy(0), c.copy(1)] })
      .flatten()
      .value();

    hops = getHops(chains);
    links = getLinks(hops);
    components = SCC(hops, links);

    var log = document.getElementById("log");

    _.map(components, function(c) {
      link_types = {};
      link_types[S] = 0;
      link_types[C] = 0;
      link_types[COMMUTATIVE] = 0;

      for (var i = 0; i < c.length; ++i) {
        var h = c[i];
        for (var j = 0; j < links.length; ++j) {
          var l = links[j];
          if (l.source != h || !_.contains(c, l.target)) { continue; }
          link_types[l.type]++;
        }
      }

      if (link_types[S] > 0 && link_types[C] > 0) {
        _.map(c, function(h) { h.type = CYCLE; });
        log.value += "SC Cycle: " + _.map(c, function(h) { return h.name });
        log.value += "\n  ";
        log.value += _(link_types).pairs().join("\n  ");
      }
    });

    d3.select("#canvas").selectAll("*").remove();

    // make a graph for dagre
    g = new dagreD3.Digraph();

    hopDict = _.zipObject(_.range(hops.length), hops);
    rHopDict = _.zipObject(
        _.map(hops, function(h) { return h.id() }),
        _.range(hops.length)
    );
    linkDict = _.zipObject(_.range(links.length), links);

    _.map(hopDict, function(h, idx) {
      g.addNode("h." + idx, { label: h.id() }) });

    _.map(linkDict, function(l, idx) {
      var s = "h." + rHopDict[l.source.id()];
      var t = "h." + rHopDict[l.target.id()];
      g.addEdge(idx, s, t, { label: l.type });
    });

    renderer = new dagreD3.Renderer();
    var oldDrawNode = renderer.drawNode();
    var oldDrawEdge = renderer.drawEdge();

    renderer.drawNode(function(graph, u, svg) {
      oldDrawNode(graph, u, svg);
      var idx = Number(u.split(".")[1]);
      h = hopDict[idx];
      if (h.type == CYCLE) {
        svg.selectAll("rect").style("fill", "red");
      } else {
        svg.selectAll("rect").style("fill", scale(h.type));
      }
      svg.selectAll("text").style("stroke", "white");
    });

    renderer.drawEdge(function(graph, u, svg) {
      oldDrawEdge(graph, u, svg);
      e = graph.edge(u);
      var l = linkDict[Number(graph.edge(u).e)];
      console.log(l);
      svg.selectAll("path").style("stroke-fill", scale(idForType[l.type]));

      if (l.type == COMMUTATIVE) {
        svg.selectAll("path").style("stroke-dasharray", "5,5");
      }
    });

    renderer.run(g, d3.select("#canvas"));
  }

updateGraph();
</script>

</html>
	<!DOCTYPE html>
	<!-- Some path computation code borrowed form http://bl.ocks.org/rkirsling/5001347 -->
	<html>
	<head>
	<meta http-equiv="content-type" content="text/html; charset=UTF-8">
	<title>Transaction Chain Viz</title>

	<script type='text/javascript' src='http://d3js.org/d3.v3.min.js'></script>
	<script type='text/javascript' src='http://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.2.1/lodash.min.js'></script>
	<script type='text/javascript' src='http://cpettitt.github.io/project/dagre-d3/latest/dagre-d3.min.js'></script>

	<style type='text/css'>
	svg {
	border: 1px solid black;
	}

	text {
	font-weight: 300;
	font-family: "Helvetica Neue", Helvetica, Arial, sans-serf;
	font-size: 14px;
	}

	rect {
	fill: #fff;
	}

	.node rect {
	stroke-width: 2px;
	stroke: #333;
	fill: none;
	}

	#node-CLOSED rect {
	fill: #f77;
	}

	#node-ESTAB rect {
	fill: #7f7;
	}

	.edge rect {
	fill: #fff;
	}

	.edge path {
	fill: none;
	stroke: #333;
	stroke-width: 1.5px;
	}
	</style>
	</head>

	<body>
	<textarea cols=60 rows=10 id="code">
	MakeChain("Bid")
	.add("Add", "bids", WRITE)
	.add("UpdatePrice", "items", WRITE);

	MakeChain("GetPrice")
	.add("Read", "items", READ)

	Commutes("Add", "Add");
	Commutes("UpdatePrice", "UpdatePrice");
	</textarea>
	<textarea cols=60 rows=10 id="log" style="editable: false">
	</textarea>
	<br>
	<input type="submit" onClick="javascript:updateGraph()"></input>
	<br>
	<svg id="canvas" width="100%" height="50%"></svg>
	</body>

	<script type='text/javascript'>
	WRITE = 0;
	READ = 1;
	CYCLE = 2;

	S = "S";
	C = "C";
	COMMUTATIVE = "COMMUTATIVE";

	FORWARD = 0;
	BACKWARD = 1;

	idForType = {};
	idForType[S] = 1;
	idForType[C] = 2;
	idForType[COMMUTATIVE] = 3;

	// strongly connected components
	function SCC(hops, links) {
	var index = 0;
	var components = [];
	var C = [];
	for (i in hops) {
	hops[i].scc_index = -1;
	hops[i].low_link = -1;
	}

	function visit(h) {
	h.scc_index = h.low_link = index;
	index += 1;

	C.push(h);
	for (var j in links) {
	var l = links[j];
	if (l.source != h) { continue; }
	var t = l.target;
	if (t.scc_index == -1) {
	visit(t);
	h.low_link = _.min([h.low_link, t.low_link]);
	} else {
	h.low_link = _.min([h.low_link, t.scc_index]);
	}
	}

	if (h.low_link == h.scc_index) {
	var new_c = []
	do {
	var back = C.pop();
	new_c.push(back);
	} while (back != h);

	components.push(new_c);
	}
	}

	for (var i in hops) {
	var h = hops[i];
	if (h.scc_index != -1) { continue; }
	visit(h);
	}

	return components;
	}

	function Hop(name, table, type, pos) {
	this.name = name;
	this.table = table;
	this.type = type;
	this.pos = pos;
	this.visited = []
	}

	Hop.prototype.id = function() {
	return this.name + "-" + this.table;
	}

	function Chain(name) {
	this.name = name;
	this.hops = [];
	}

	Chain.prototype.add = function(name, table, type) {
	var h = new Hop(name, table, type, this.hops.length);
	this.hops.push(h);
	return this;
	}

	Chain.prototype.links = function() {
	var links = []
	for (var i in this.hops) {
	if (i > 0) {
	if (this.type == FORWARD) {
	links.push({"source" : this.hops[i - 1], "target" : this.hops[i], "type" : S});
	} else {
	links.push({"source" : this.hops[i], "target" : this.hops[i - 1], "type" : S});
	}
	}
	}
	return links;
	}

	Chain.prototype.copy = function(type) {
	var c = new Chain();
	c.name = this.name;
	c.type = type;
	c.hops = _.map(this.hops, function(h) {
	return new Hop(h.name + "." + type, h.table, h.type, h.pos)
	});
	return c;
	}

	function getHops(chains) {
	return _(chains)
	.map(function(c) { return c.hops; })
	.flatten()
	.value();
	}

	function commutes(a, b) {
	for (var i = 0; i < World.commutes.length; ++i) {
	var s = World.commutes[i][0];
	var e = World.commutes[i][1];
	if (a.name.substring(0, s.length) == s &&
	b.name.substring(0, e.length) == e) {
	return true;
	}
	if (b.name.substring(0, s.length) == s &&
	a.name.substring(0, e.length) == e) {
	return true;
	}
	}
	return false;
	}

	function getLinks(hops) {
	var sLinks = _(chains)
	.map(function(c) { return c.links(); })
	.flatten()
	.value();

	var cLinks = [];
	for(i in hops) {
	for (j in hops) {
	if (i == j) { continue; }
	var hi = hops[i];
	var hj = hops[j];

	if (hi.table == hj.table && (hi.type == WRITE \|\| hj.type == WRITE)) {
	if (commutes(hi, hj)) {
	// drop edge
	// cLinks.push({ "source" : hi, "target" : hj, type : COMMUTATIVE });
	} else {
	cLinks.push({ "source" : hi, "target" : hj, type : C });
	}
	}
	}
	}

	return _.flatten([sLinks, cLinks]);
	}

	function MakeChain(name) {
	var c = new Chain(name);
	World.chains.push(c);
	return c;
	}

	function Commutes(a, b) {
	World.commutes.push([a, b]);
	}

	function updateGraph() {
	var log = document.getElementById("log");
	log.value = "";
	log.disabled = true;

	try {
	_update();
	} catch(err) {
	log.value += err;
	}
	}
	function _update() {
	var code = document.getElementById("code").value;
	var scale = d3.scale.category10();

	World = function() {};
	World.chains = [];
	World.commutes = [];

	eval(code);
	chains = _(World.chains).map(function(c) { return [c.copy(0), c.copy(1)] })
	.flatten()
	.value();

	hops = getHops(chains);
	links = getLinks(hops);
	components = SCC(hops, links);

	var log = document.getElementById("log");

	_.map(components, function(c) {
	link_types = {};
	link_types[S] = 0;
	link_types[C] = 0;
	link_types[COMMUTATIVE] = 0;

	for (var i = 0; i < c.length; ++i) {
	var h = c[i];
	for (var j = 0; j < links.length; ++j) {
	var l = links[j];
	if (l.source != h \|\| !_.contains(c, l.target)) { continue; }
	link_types[l.type]++;
	}
	}

	if (link_types[S] > 0 && link_types[C] > 0) {
	_.map(c, function(h) { h.type = CYCLE; });
	log.value += "SC Cycle: " + _.map(c, function(h) { return h.name });
	log.value += "\n ";
	log.value += _(link_types).pairs().join("\n ");
	}
	});

	d3.select("#canvas").selectAll("*").remove();

	// make a graph for dagre
	g = new dagreD3.Digraph();

	hopDict = _.zipObject(_.range(hops.length), hops);
	rHopDict = _.zipObject(
	_.map(hops, function(h) { return h.id() }),
	_.range(hops.length)
	);
	linkDict = _.zipObject(_.range(links.length), links);

	_.map(hopDict, function(h, idx) {
	g.addNode("h." + idx, { label: h.id() }) });

	_.map(linkDict, function(l, idx) {
	var s = "h." + rHopDict[l.source.id()];
	var t = "h." + rHopDict[l.target.id()];
	g.addEdge(idx, s, t, { label: l.type });
	});

	renderer = new dagreD3.Renderer();
	var oldDrawNode = renderer.drawNode();
	var oldDrawEdge = renderer.drawEdge();

	renderer.drawNode(function(graph, u, svg) {
	oldDrawNode(graph, u, svg);
	var idx = Number(u.split(".")[1]);
	h = hopDict[idx];
	if (h.type == CYCLE) {
	svg.selectAll("rect").style("fill", "red");
	} else {
	svg.selectAll("rect").style("fill", scale(h.type));
	}
	svg.selectAll("text").style("stroke", "white");
	});

	renderer.drawEdge(function(graph, u, svg) {
	oldDrawEdge(graph, u, svg);
	e = graph.edge(u);
	var l = linkDict[Number(graph.edge(u).e)];
	console.log(l);
	svg.selectAll("path").style("stroke-fill", scale(idForType[l.type]));

	if (l.type == COMMUTATIVE) {
	svg.selectAll("path").style("stroke-dasharray", "5,5");
	}
	});

	renderer.run(g, d3.select("#canvas"));
	}

	updateGraph();
	</script>

	</html>