status/res/imp/commits-canvas-sk.html - buildbot - Git at Google

 <!--
   The res/js/status.js file must be included before this file.

   This in an HTML Import-able file this contains the definition
   of the following elements:

     <commits-canvas-sk>

   To use this file import it:

     <link href="/res/imp/commits-canvas-sk.html" rel="import" />

   Usage:

     <commits-canvas-sk></commits-canvas-sk>

   Properties:
     //input
     branch_heads: Array<Object>, an array of Objects with the following attributes:
         head: String, the last commit revision in this branch.  If it is off the screen, it will
               not be drawn.
         name: String, the name of the branch.  Will be drawn next to the "head" commit.
     commits: Array<Object>, an array of commit objects, in chronological order with (at least), the
       following attributes:
         hash: String, the commit's revision
         parent: Array<String>, the hashes of any parents.
         timestamp: String, the commit's timestamp, formatted like: "2016-02-22T06:34:47-08:00"
     roll_statuses: Array of Objects, which is used to link to the recent rolls. Each object contains at least:
         currentRollRev: String, git hash of current roll
         lastRollRev: String, git hash of previous roll

     //output
     commits_to_load: Number, the number of commits to load.
     reload: Number, the number of seconds that the status page should be reloaded.

   Methods:
     None.

   Events:
     None.
 -->
 <link rel="import" href="/res/imp/bower_components/paper-input/paper-input.html">
 <link rel="import" href="/res/common/imp/styles-sk.html">

 <dom-module id="commits-canvas-sk">
   <template>
     <style include="styles-sk">
       .refresh {
         font-size: 12px;
         font-weight: normal;
         height: 108px;
         width: 160px;
         padding: 5px;
       }

       paper-input {
         display: inline-block;
       }
       :host{
         --paper-input-container-input: {
             font-size: 1.0em;
         };
       }
       div[prefix] {
         font-size: 1.0em;
       }

       #commitCanvas.pointer {
         cursor: pointer;
       }
     </style>

     <div id="container">

       <div id="reload" class="refresh">
         <paper-input type="number" value="{{reload}}" auto-validate no-label-float>
           <div prefix>Reload (s):&nbsp;</div>
         </paper-input>
         <paper-input type="number" value="{{commits_to_load}}" auto-validate no-label-float>
           <div prefix>Commits:&nbsp;</div>
         </paper-input>
         <div>Loaded {{_lastLoaded}}</div>
       </div>

       <!-- The tap event (which was originally used) does not always produce offsetY.
       on-click works for the Pixels (even when touching), so we use that.-->
       <canvas id="commitCanvas" on-click="handleclick" on-mousemove="handlemouseover"></canvas>

     </div>

   </template>
   <script>
   (function() {
     var MIN_CANVAS_WIDTH = 175;
     var commitY = 20;              // Vertical pixels used by each commit.
     var paddingX = 10;             // Left-side padding pixels.
     var paddingY = 20;             // Top padding pixels.
     var radius = 3;                // Radius of commit dots.
     var columnWidth = commitY;     // Pixel width of per-branch colums.
     // This is filled in later.
     var palette = [];
     var commitBg = "#FFFFFF";    // Background color of alternating commits.
     var commitBgAlt = "#EFEFEF"; // Background color of alternating commits.
     var font = "10px monospace"; // Font used for labels.

     var BRANCH_PREFIX = "origin/";

     // Draws a filled-in dot at the given center with the given radius and color.
     function drawDot(ctx, center, radius, color) {
       ctx.fillStyle = color;
       ctx.beginPath();
       ctx.arc(center.x, center.y, radius, 0, 2*Math.PI, false);
       ctx.fill();
       ctx.closePath();
     }

     // Object with an x and y-value.
     function Point(x, y) {
       this.x = x;
       this.y = y;
     }

     // Object representing a commit used for creating layout and drawing.
     function Commit(commitInfo, row) {
       this.hash = commitInfo.hash;
       this.timestamp = new Date(commitInfo.timestamp);
       this.row = row;
       this.column = -1;
       this.label = [];
       this.parents = commitInfo.parent || [];

       // The color for this commit.
       this.color = function() {
         return palette[this.column % palette.length];
       };

       // Where to draw this commit.
       this.getBounds = function() {
         return new Point(paddingX, paddingY - commitY/4 + commitY * this.row);
       };

       // The center of this commit's dot.
       this.dotCenter = function() {
         var start = this.getBounds();
         var centerX = start.x + columnWidth * this.column + radius;
         var centerY = start.y - radius - 2;
         return new Point(centerX, centerY);
       };

       // Coordinates for drawing this commit's label.
       this.labelCoords = function() {
         var bounds = this.getBounds();
         var center = this.dotCenter();
         return new Point(center.x + 3 * radius, bounds.y - 1);
       };

       // Return the text for this commit's label, truncated to 24 characters.
       this.labelText = function() {
         return sk.truncate(this.label.join(","), 24);
       };

       // Return the estimated width of this commit's label text.
       this.labelWidth = function(ctx) {
         return ctx.measureText(this.labelText()).width;
       };

       // Draw an an alternating background color for this commit.
       this.drawBackground = function(ctx) {
         var startY = commitY * this.row;
         var bgColor = this.row % 2 ? commitBg : commitBgAlt;
         ctx.fillStyle = bgColor;
         ctx.fillRect(0, startY, ctx.canvas.clientWidth, startY + commitY);
       };

       // Draw a line connecting this commit to one of its parents.
       this.drawConnection = function(ctx, parent, allCommits) {
         var center = this.dotCenter();
         var to = parent.dotCenter();
         ctx.beginPath();
         ctx.moveTo(center.x, center.y);
         if (this.column == parent.column) {
           // Draw a straight line.
           ctx.lineTo(to.x, to.y);
         } else {
           // Draw a connector composed of five segments: a vertical line, an
           // arc, a horizontal line, another arc, and another vertical line.
           // One or more of the lines may have zero length.
           var arcRadius = commitY / 2;
           // The direction in which to draw the arc.
           var d = center.x > to.x ? 1 : -1;

           // We'll reuse these values, so pre-compute them.
           var halfPI = 0.5 * Math.PI;
           var oneAndHalfPI = 1.5 * Math.PI;

           // If there is at least one commit in the current commit's column
           // between the current commit and this parent, the first arc must
           // begin at the current commit: the first vertical line has zero
           // length. Otherwise, the length of the first vertical line is
           // flexible.
           var v1_flex = true;
           for (var i = 0; i < this.parents.length; i++) {
             var c = allCommits[this.parents[i]];
             if (!c) {
               console.warn("Cannot find " + this.parents[i]);
               continue;
             }
             if (this.timestamp > c.timestamp && c.timestamp > parent.timestamp) {
               if (this.column == c.column) {
                 v1_flex = false;
                 break;
               }
             }
           }

           // If there is at least one commit in the parent's column between the
           // current commit and this parent, the secon arc must end at the
           // parent commit: the second vertical line has zero length.
           // Otherwise, the length of the second vertical line is flexible.
           var v2_flex = true;
           for (var i = 0; i < parent.children.length; i++) {
             var c = allCommits[parent.children[i]];
             if (this.timestamp > c.timestamp && c.timestamp > parent.timestamp) {
               if (parent.column == c.column) {
                 v2_flex = false;
                 break;
               }
             }
           }

           // Arc information..
           var a1 = new Point(center.x - d * arcRadius, to.y - commitY);
           var a2 = new Point(to.x + d * arcRadius, to.y);

           // If both vertical lines are flexible, arbitrarily choose where to
           // put the arcs and horizontal line (eg. next to the parent).
           if (v1_flex && v2_flex) {
             a1.y = to.y - commitY;
             a2.y = to.y;
           }
           // If exactly one vertical line is flexible, put the arcs and
           // horizontal line where they must go.
           else if (v1_flex && !v2_flex) {
             a1.y = to.y - commitY;
             a2.y = to.y;
           } else if (!v1_flex && v2_flex) {
             a1.y = center.y;
             a2.y = center.y + commitY;
           }
           // If neither vertical line is flexible, then we have to place arcs
           // at both commits and the "horizontal" line becomes diagonal.
           else {
             a1.y = center.y;
             a2.y = to.y;
           }

           // Distance between the two arc centers.
           var dist = Math.sqrt(Math.pow(a2.x - a1.x, 2) + Math.pow(a2.y - a1.y, 2));
           // Length of the arc to draw.
           var arcLength = Math.PI - Math.acos(2*arcRadius / dist) - Math.acos((Math.abs(to.x - center.x) - 2*arcRadius) / dist);
           var a1_start = halfPI - d * halfPI;
           var a2_start = oneAndHalfPI - d * (halfPI - arcLength);

           // Draw the connector: vertical line, arc, horizontal line, arc,
           // vertical line.
           ctx.lineTo(a1.x + d*arcRadius, a1.y);
           ctx.arc(a1.x, a1.y, arcRadius, a1_start, a1_start + d*arcLength, d < 0);
           // The middle line doesn't need to be explicitly drawn.
           ctx.arc(a2.x, a2.y, arcRadius, a2_start, a2_start - d*arcLength, d > 0);
           ctx.lineTo(to.x, to.y);
         }
         ctx.strokeStyle = this.color();
         ctx.stroke();
       };

       // Draw this commit's label.
       this.drawLabel = function(ctx) {
         if (this.label.length <= 0) {
           return;
         }
         labelCoords = this.labelCoords();
         var w = this.labelWidth(ctx);
         var h = parseInt(font);
         var paddingY = 3;
         var paddingX = 3;
         ctx.fillStyle = this.color();
         ctx.fillRect(labelCoords.x - paddingX, labelCoords.y - h, w + 2 * paddingX, h + paddingY);
         ctx.fillStyle = "#FFFFFF";
         ctx.fillText(this.labelText(), labelCoords.x, labelCoords.y);
       };

       this.draw = function(ctx, displayCommits) {
         var color = this.color();
         var center = this.dotCenter();

         // Connect the dots.
         for (var p = 0; p < this.parents.length; p++) {
           var parent = displayCommits[this.parents[p]];
           if (!displayCommits[this.parents[p]]) {
             console.warn("Cannot find " + this.parents[p]);
             continue;
           }
           this.drawConnection(ctx, parent, displayCommits);
         }

         // Draw a dot.
         drawDot(ctx, center, radius, color);

         // Draw a label, if applicable.
         this.drawLabel(ctx);
       };
     }

     // Follow commits by first parent, assigning the given column until we get
     // to a commit that we aren't going to draw.
     function traceCommits(displayCommits, commits, remaining, hash, column) {
       var usedColumn = false;
       while(remaining[hash]) {
         var c = displayCommits[hash];
         c.column = column;
         delete remaining[hash];
         hash = c.parents[0];
         usedColumn = true;
         // Special case for non-displayed parents.
         if (!displayCommits[hash]) {
           var parent = new Commit({
             hash: hash,
           }, commits.length);
           parent.column = c.column;
           displayCommits[hash] = parent;
         }
       }
       return usedColumn;
     }

     // Create Commit objects to be displayed. Assigns rows and columns for each
     // commit to assist in producing a nice layout.
     function prepareCommitsForDisplay(commits, branch_heads) {
       // Create a Commit object for each commit.
       var displayCommits = {}; // Commit objects by hash.
       var remaining = {};      // Not-yet-processed commits by hash.
       for (var i = 0; i < commits.length; i++) {
         var c = new Commit(commits[i], i)
         displayCommits[c.hash] = c;
         remaining[c.hash] = c;
       }

       // Pre-process the branches. We want master first, and no HEAD.
       var masterIdx = -1;
       var branches = [];
       for (var b = 0; b < branch_heads.length; b++) {
         if (branch_heads[b].name === "master") {
           masterIdx = b;
           branches.push(branch_heads[b]);
         }
       }
       for (var b = 0; b < branch_heads.length; b++) {
         var branch = branch_heads[b];
         if (b != masterIdx && branch.name != "HEAD") {
           branches.push(branch);
         }
       }

       // Trace each branch, placing commits on that branch in an associated column.
       var column = 0;
       for (var b = 0; b < branches.length; b++) {
         // Add a label to commits at branch heads.
         var hash = branches[b].head
         // The branch might have scrolled out of the time window. If so, just
         // skip it.
         if (!displayCommits[hash]) {
           continue
         }
         displayCommits[hash].label.push(branches[b].name);
         if (traceCommits(displayCommits, commits, remaining, hash, column)) {
           column++;
         }
       }

       // Add the remaining commits to their own columns.
       for (var hash in remaining) {
         if (traceCommits(displayCommits, commits, remaining, hash, column)) {
           column++;
         }
       }

       // Point all parents at their children, for convenience.
       for (var hash in displayCommits) {
         displayCommits[hash].children = [];
       }
       for (var hash in displayCommits) {
         var c = displayCommits[hash];
         if (c.parents) {
           for (var i = 0; i < c.parents.length; i++) {
             if (!displayCommits[c.parents[i]]) {
               console.warn("Cannot find " + c.parents[i]);
               continue;
             }
             displayCommits[c.parents[i]].children.push(c.hash);
           }
         }
       }

       return [displayCommits, column];
     }

     Polymer({
       is: "commits-canvas-sk",
       properties: {
         // input
         cr_roll: {
           type: Object,
         },
         android_roll: {
           type: Object,
         },
         branch_heads: {
           type: Array,
         },
         commits: {
           type: Array,
         },
         repo_base: {
           type: String,
         },

         // output
         commits_to_load: {
           type: Number,
           value: 35,
           notify: true,
         },
         reload: {
           type: Number,
           value: 60,
           notify: true,
         },

         // private
         _linkMap: {
           // Number: String, number is index of commit in display, String is URL to link to.
           type: Object,
           computed: "_computeLinkMap(commits.*,roll_statuses.*,branch_heads.*)",
         },
         _titleMap: {
           // Number: String, number is index of commit in display, String is the title of the label.
           type: Object,
           computed: "_computeTitleMap(commits.*,roll_statuses.*,branch_heads.*)",
         },
         _lastLoaded: {
           type: String,
           value: "(not yet loaded)",
         },
       },

       observers: [
         "draw(commits.*, branch_heads.*)"
       ],

       draw: function() {
         var commits = this.commits;
         var branch_heads = this.branch_heads;
         this._lastLoaded = new Date().toLocaleTimeString();
         console.time("draw");
         // Initialize all commits.
         var prep = prepareCommitsForDisplay(commits, branch_heads);
         this.displayCommits = prep[0];
         var numColumns = prep[1];

         // Calculate the required canvas width based on the commit columns and
         // labels.
         // TODO(borenet): Further minimize this width by reordering the columns
         // based on which has the longest label.
         var dummyCtx = document.createElement("canvas").getContext("2d");
         dummyCtx.font = font;
         var longestWidth = 0;
         for (var i = 0; i < commits.length; i++) {
           var c = this.displayCommits[commits[i].hash];
           var w = c.labelWidth(dummyCtx);
           w += commitY * (c.column + 1);
           if (w > longestWidth) {
             longestWidth = w;
           }
         }

         // Redraw the canvas.
         var scale = window.devicePixelRatio || 1.0;
         var canvas = this.$.commitCanvas;
         this.canvasWidth = Math.max(longestWidth + paddingX, MIN_CANVAS_WIDTH);
         this.canvasHeight = commitY * commits.length;
         canvas.style.width = Math.floor(this.canvasWidth) + "px";
         canvas.style.height = Math.floor(this.canvasHeight) + "px";
         canvas.width = this.canvasWidth * scale;
         canvas.height = this.canvasHeight * scale;
         var ctx = canvas.getContext("2d");
         ctx.clearRect(0, 0, canvas.width, canvas.height);
         ctx.setTransform(scale, 0, 0, scale, 0, 0);
         ctx.font = font;

         // Shade an alternating background.
         for (var i = 0; i < commits.length; i++) {
           this.displayCommits[commits[i].hash].drawBackground(ctx);
         }

         // Create the color palette for the commits.
         palette = [
           this.getComputedStyleValue("--color-bluegreen"),
           this.getComputedStyleValue("--color-redorange"),
           this.getComputedStyleValue("--color-purple"),
           this.getComputedStyleValue("--color-pink"),
           this.getComputedStyleValue("--color-lightgreen"),
           this.getComputedStyleValue("--color-lightorange"),
           this.getComputedStyleValue("--color-burntorange"),
           this.getComputedStyleValue("--color-gray"),
         ];

         // Draw the commits.
         for (var i = 0; i < commits.length; i++) {
           this.displayCommits[commits[i].hash].draw(ctx, this.displayCommits);
         }

         console.timeEnd("draw");
       },

       // _computeLinkMap looks through all the branch_heads, finds the index of each
       // commit belonging to a branch and makes a map of index -> URL.  Then, it handles
       // the special case of current autoroll and previous autoroll.
       // The last link added to the map will be the one used. So when there are multiple
       // links added we need prioritize which one should displayed.
       // Here is the current order: Chrome roll links have priority over Android roll links
       // which in turn have priority over branch links.
       _computeLinkMap: function() {
         var linkMap = {};

         // Link to generic branch heads.
         this.branch_heads.forEach(function(branch) {
           var name = branch.name;
           if (branch.name.startsWith(BRANCH_PREFIX)) {
             var name = branch.name.slice(BRANCH_PREFIX.length);
           }
           // If the commit is not found in the range of commits, we will just be
           // overwriting the value at key "-1", which won't actually get used.
           var idx = this._indexOfRevision(branch.head);
           linkMap[idx] = this.repo_base + name;
         }.bind(this));

         // Link to rolls.
         for (var i = 0; i < this.roll_statuses.length; i++) {
           var roller = this.roll_statuses[i];
           var idx = this._indexOfRevision(roller.currentRollRev);
           linkMap[idx] = roller.url;
           idx = this._indexOfRevision(roller.lastRollRev);
           linkMap[idx] = roller.url;
         }
         return linkMap;
       },

       // _computeTitleMap looks through all the branch heads, find the index of each
       // commit belonging to a branch and makes a map of index -> label title.
       _computeTitleMap: function() {
         var titleMap = {};

         this.branch_heads.forEach(function(branch) {
           var name = branch.name;
           var idx = this._indexOfRevision(branch.head);
           if (titleMap[idx]) {
             titleMap[idx] = titleMap[idx] + "," + name;
           } else {
             titleMap[idx] = name;
           }
         }.bind(this));
         return titleMap;
       },

       _indexOfRevision: function(revision) {
         var idx = -1;
         this.commits.forEach(function(c,i){
           if (c.hash === revision){
             idx = i;
           }
         });
         return idx;
       },

       // handleclick converts the click's offsetY (Y location relative to the tapped canvas) into index
       handleclick: function(e) {
         if (!this._linkMap) {
           return;
         }
         var y = (e && e.offsetY) || 1;
         var commitIdx = Math.floor(y / commitY);

         var link = this._linkMap[commitIdx];
         if (link){
           window.open(link);
         }
       },

       handlemouseover: function(e) {
         if (!this._linkMap) {
           return;
         }
         var commitIdx = Math.floor(e.offsetY / commitY);
         var link = this._linkMap[commitIdx];
         if (link){
           this.$.commitCanvas.classList.add("pointer");
         } else {
           this.$.commitCanvas.classList.remove("pointer");
         }
         var title = this._titleMap[commitIdx];
         if (title) {
           this.$.commitCanvas.title = title;
         }
       },

     });
   })();
   </script>
 </dom-module>
	<!--
	The res/js/status.js file must be included before this file.

	This in an HTML Import-able file this contains the definition
	of the following elements:

	<commits-canvas-sk>

	To use this file import it:

	<link href="/res/imp/commits-canvas-sk.html" rel="import" />

	Usage:

	<commits-canvas-sk></commits-canvas-sk>

	Properties:
	//input
	branch_heads: Array<Object>, an array of Objects with the following attributes:
	head: String, the last commit revision in this branch. If it is off the screen, it will
	not be drawn.
	name: String, the name of the branch. Will be drawn next to the "head" commit.
	commits: Array<Object>, an array of commit objects, in chronological order with (at least), the
	following attributes:
	hash: String, the commit's revision
	parent: Array<String>, the hashes of any parents.
	timestamp: String, the commit's timestamp, formatted like: "2016-02-22T06:34:47-08:00"
	roll_statuses: Array of Objects, which is used to link to the recent rolls. Each object contains at least:
	currentRollRev: String, git hash of current roll
	lastRollRev: String, git hash of previous roll

	//output
	commits_to_load: Number, the number of commits to load.
	reload: Number, the number of seconds that the status page should be reloaded.

	Methods:
	None.

	Events:
	None.
	-->
	<link rel="import" href="/res/imp/bower_components/paper-input/paper-input.html">
	<link rel="import" href="/res/common/imp/styles-sk.html">

	<dom-module id="commits-canvas-sk">
	<template>
	<style include="styles-sk">
	.refresh {
	font-size: 12px;
	font-weight: normal;
	height: 108px;
	width: 160px;
	padding: 5px;
	}

	paper-input {
	display: inline-block;
	}
	:host{
	--paper-input-container-input: {
	font-size: 1.0em;
	};
	}
	div[prefix] {
	font-size: 1.0em;
	}

	#commitCanvas.pointer {
	cursor: pointer;
	}
	</style>

	<div id="container">

	<div id="reload" class="refresh">
	<paper-input type="number" value="{{reload}}" auto-validate no-label-float>
	<div prefix>Reload (s): </div>
	</paper-input>
	<paper-input type="number" value="{{commits_to_load}}" auto-validate no-label-float>
	<div prefix>Commits: </div>
	</paper-input>
	<div>Loaded {{_lastLoaded}}</div>
	</div>

	<!-- The tap event (which was originally used) does not always produce offsetY.
	on-click works for the Pixels (even when touching), so we use that.-->
	<canvas id="commitCanvas" on-click="handleclick" on-mousemove="handlemouseover"></canvas>

	</div>

	</template>
	<script>
	(function() {
	var MIN_CANVAS_WIDTH = 175;
	var commitY = 20; // Vertical pixels used by each commit.
	var paddingX = 10; // Left-side padding pixels.
	var paddingY = 20; // Top padding pixels.
	var radius = 3; // Radius of commit dots.
	var columnWidth = commitY; // Pixel width of per-branch colums.
	// This is filled in later.
	var palette = [];
	var commitBg = "#FFFFFF"; // Background color of alternating commits.
	var commitBgAlt = "#EFEFEF"; // Background color of alternating commits.
	var font = "10px monospace"; // Font used for labels.

	var BRANCH_PREFIX = "origin/";

	// Draws a filled-in dot at the given center with the given radius and color.
	function drawDot(ctx, center, radius, color) {
	ctx.fillStyle = color;
	ctx.beginPath();
	ctx.arc(center.x, center.y, radius, 0, 2*Math.PI, false);
	ctx.fill();
	ctx.closePath();
	}

	// Object with an x and y-value.
	function Point(x, y) {
	this.x = x;
	this.y = y;
	}

	// Object representing a commit used for creating layout and drawing.
	function Commit(commitInfo, row) {
	this.hash = commitInfo.hash;
	this.timestamp = new Date(commitInfo.timestamp);
	this.row = row;
	this.column = -1;
	this.label = [];
	this.parents = commitInfo.parent \|\| [];

	// The color for this commit.
	this.color = function() {
	return palette[this.column % palette.length];
	};

	// Where to draw this commit.
	this.getBounds = function() {
	return new Point(paddingX, paddingY - commitY/4 + commitY * this.row);
	};

	// The center of this commit's dot.
	this.dotCenter = function() {
	var start = this.getBounds();
	var centerX = start.x + columnWidth * this.column + radius;
	var centerY = start.y - radius - 2;
	return new Point(centerX, centerY);
	};

	// Coordinates for drawing this commit's label.
	this.labelCoords = function() {
	var bounds = this.getBounds();
	var center = this.dotCenter();
	return new Point(center.x + 3 * radius, bounds.y - 1);
	};

	// Return the text for this commit's label, truncated to 24 characters.
	this.labelText = function() {
	return sk.truncate(this.label.join(","), 24);
	};

	// Return the estimated width of this commit's label text.
	this.labelWidth = function(ctx) {
	return ctx.measureText(this.labelText()).width;
	};

	// Draw an an alternating background color for this commit.
	this.drawBackground = function(ctx) {
	var startY = commitY * this.row;
	var bgColor = this.row % 2 ? commitBg : commitBgAlt;
	ctx.fillStyle = bgColor;
	ctx.fillRect(0, startY, ctx.canvas.clientWidth, startY + commitY);
	};

	// Draw a line connecting this commit to one of its parents.
	this.drawConnection = function(ctx, parent, allCommits) {
	var center = this.dotCenter();
	var to = parent.dotCenter();
	ctx.beginPath();
	ctx.moveTo(center.x, center.y);
	if (this.column == parent.column) {
	// Draw a straight line.
	ctx.lineTo(to.x, to.y);
	} else {
	// Draw a connector composed of five segments: a vertical line, an
	// arc, a horizontal line, another arc, and another vertical line.
	// One or more of the lines may have zero length.
	var arcRadius = commitY / 2;
	// The direction in which to draw the arc.
	var d = center.x > to.x ? 1 : -1;

	// We'll reuse these values, so pre-compute them.
	var halfPI = 0.5 * Math.PI;
	var oneAndHalfPI = 1.5 * Math.PI;

	// If there is at least one commit in the current commit's column
	// between the current commit and this parent, the first arc must
	// begin at the current commit: the first vertical line has zero
	// length. Otherwise, the length of the first vertical line is
	// flexible.
	var v1_flex = true;
	for (var i = 0; i < this.parents.length; i++) {
	var c = allCommits[this.parents[i]];
	if (!c) {
	console.warn("Cannot find " + this.parents[i]);
	continue;
	}
	if (this.timestamp > c.timestamp && c.timestamp > parent.timestamp) {
	if (this.column == c.column) {
	v1_flex = false;
	break;
	}
	}
	}

	// If there is at least one commit in the parent's column between the
	// current commit and this parent, the secon arc must end at the
	// parent commit: the second vertical line has zero length.
	// Otherwise, the length of the second vertical line is flexible.
	var v2_flex = true;
	for (var i = 0; i < parent.children.length; i++) {
	var c = allCommits[parent.children[i]];
	if (this.timestamp > c.timestamp && c.timestamp > parent.timestamp) {
	if (parent.column == c.column) {
	v2_flex = false;
	break;
	}
	}
	}

	// Arc information..
	var a1 = new Point(center.x - d * arcRadius, to.y - commitY);
	var a2 = new Point(to.x + d * arcRadius, to.y);

	// If both vertical lines are flexible, arbitrarily choose where to
	// put the arcs and horizontal line (eg. next to the parent).
	if (v1_flex && v2_flex) {
	a1.y = to.y - commitY;
	a2.y = to.y;
	}
	// If exactly one vertical line is flexible, put the arcs and
	// horizontal line where they must go.
	else if (v1_flex && !v2_flex) {
	a1.y = to.y - commitY;
	a2.y = to.y;
	} else if (!v1_flex && v2_flex) {
	a1.y = center.y;
	a2.y = center.y + commitY;
	}
	// If neither vertical line is flexible, then we have to place arcs
	// at both commits and the "horizontal" line becomes diagonal.
	else {
	a1.y = center.y;
	a2.y = to.y;
	}

	// Distance between the two arc centers.
	var dist = Math.sqrt(Math.pow(a2.x - a1.x, 2) + Math.pow(a2.y - a1.y, 2));
	// Length of the arc to draw.
	var arcLength = Math.PI - Math.acos(2arcRadius / dist) - Math.acos((Math.abs(to.x - center.x) - 2arcRadius) / dist);
	var a1_start = halfPI - d * halfPI;
	var a2_start = oneAndHalfPI - d * (halfPI - arcLength);

	// Draw the connector: vertical line, arc, horizontal line, arc,
	// vertical line.
	ctx.lineTo(a1.x + d*arcRadius, a1.y);
	ctx.arc(a1.x, a1.y, arcRadius, a1_start, a1_start + d*arcLength, d < 0);
	// The middle line doesn't need to be explicitly drawn.
	ctx.arc(a2.x, a2.y, arcRadius, a2_start, a2_start - d*arcLength, d > 0);
	ctx.lineTo(to.x, to.y);
	}
	ctx.strokeStyle = this.color();
	ctx.stroke();
	};

	// Draw this commit's label.
	this.drawLabel = function(ctx) {
	if (this.label.length <= 0) {
	return;
	}
	labelCoords = this.labelCoords();
	var w = this.labelWidth(ctx);
	var h = parseInt(font);
	var paddingY = 3;
	var paddingX = 3;
	ctx.fillStyle = this.color();
	ctx.fillRect(labelCoords.x - paddingX, labelCoords.y - h, w + 2 * paddingX, h + paddingY);
	ctx.fillStyle = "#FFFFFF";
	ctx.fillText(this.labelText(), labelCoords.x, labelCoords.y);
	};

	this.draw = function(ctx, displayCommits) {
	var color = this.color();
	var center = this.dotCenter();

	// Connect the dots.
	for (var p = 0; p < this.parents.length; p++) {
	var parent = displayCommits[this.parents[p]];
	if (!displayCommits[this.parents[p]]) {
	console.warn("Cannot find " + this.parents[p]);
	continue;
	}
	this.drawConnection(ctx, parent, displayCommits);
	}

	// Draw a dot.
	drawDot(ctx, center, radius, color);

	// Draw a label, if applicable.
	this.drawLabel(ctx);
	};
	}

	// Follow commits by first parent, assigning the given column until we get
	// to a commit that we aren't going to draw.
	function traceCommits(displayCommits, commits, remaining, hash, column) {
	var usedColumn = false;
	while(remaining[hash]) {
	var c = displayCommits[hash];
	c.column = column;
	delete remaining[hash];
	hash = c.parents[0];
	usedColumn = true;
	// Special case for non-displayed parents.
	if (!displayCommits[hash]) {
	var parent = new Commit({
	hash: hash,
	}, commits.length);
	parent.column = c.column;
	displayCommits[hash] = parent;
	}
	}
	return usedColumn;
	}

	// Create Commit objects to be displayed. Assigns rows and columns for each
	// commit to assist in producing a nice layout.
	function prepareCommitsForDisplay(commits, branch_heads) {
	// Create a Commit object for each commit.
	var displayCommits = {}; // Commit objects by hash.
	var remaining = {}; // Not-yet-processed commits by hash.
	for (var i = 0; i < commits.length; i++) {
	var c = new Commit(commits[i], i)
	displayCommits[c.hash] = c;
	remaining[c.hash] = c;
	}

	// Pre-process the branches. We want master first, and no HEAD.
	var masterIdx = -1;
	var branches = [];
	for (var b = 0; b < branch_heads.length; b++) {
	if (branch_heads[b].name === "master") {
	masterIdx = b;
	branches.push(branch_heads[b]);
	}
	}
	for (var b = 0; b < branch_heads.length; b++) {
	var branch = branch_heads[b];
	if (b != masterIdx && branch.name != "HEAD") {
	branches.push(branch);
	}
	}

	// Trace each branch, placing commits on that branch in an associated column.
	var column = 0;
	for (var b = 0; b < branches.length; b++) {
	// Add a label to commits at branch heads.
	var hash = branches[b].head
	// The branch might have scrolled out of the time window. If so, just
	// skip it.
	if (!displayCommits[hash]) {
	continue
	}
	displayCommits[hash].label.push(branches[b].name);
	if (traceCommits(displayCommits, commits, remaining, hash, column)) {
	column++;
	}
	}

	// Add the remaining commits to their own columns.
	for (var hash in remaining) {
	if (traceCommits(displayCommits, commits, remaining, hash, column)) {
	column++;
	}
	}

	// Point all parents at their children, for convenience.
	for (var hash in displayCommits) {
	displayCommits[hash].children = [];
	}
	for (var hash in displayCommits) {
	var c = displayCommits[hash];
	if (c.parents) {
	for (var i = 0; i < c.parents.length; i++) {
	if (!displayCommits[c.parents[i]]) {
	console.warn("Cannot find " + c.parents[i]);
	continue;
	}
	displayCommits[c.parents[i]].children.push(c.hash);
	}
	}
	}

	return [displayCommits, column];
	}

	Polymer({
	is: "commits-canvas-sk",
	properties: {
	// input
	cr_roll: {
	type: Object,
	},
	android_roll: {
	type: Object,
	},
	branch_heads: {
	type: Array,
	},
	commits: {
	type: Array,
	},
	repo_base: {
	type: String,
	},

	// output
	commits_to_load: {
	type: Number,
	value: 35,
	notify: true,
	},
	reload: {
	type: Number,
	value: 60,
	notify: true,
	},

	// private
	_linkMap: {
	// Number: String, number is index of commit in display, String is URL to link to.
	type: Object,
	computed: "_computeLinkMap(commits.,roll_statuses.,branch_heads.*)",
	},
	_titleMap: {
	// Number: String, number is index of commit in display, String is the title of the label.
	type: Object,
	computed: "_computeTitleMap(commits.,roll_statuses.,branch_heads.*)",
	},
	_lastLoaded: {
	type: String,
	value: "(not yet loaded)",
	},
	},

	observers: [
	"draw(commits., branch_heads.)"
	],

	draw: function() {
	var commits = this.commits;
	var branch_heads = this.branch_heads;
	this._lastLoaded = new Date().toLocaleTimeString();
	console.time("draw");
	// Initialize all commits.
	var prep = prepareCommitsForDisplay(commits, branch_heads);
	this.displayCommits = prep[0];
	var numColumns = prep[1];

	// Calculate the required canvas width based on the commit columns and
	// labels.
	// TODO(borenet): Further minimize this width by reordering the columns
	// based on which has the longest label.
	var dummyCtx = document.createElement("canvas").getContext("2d");
	dummyCtx.font = font;
	var longestWidth = 0;
	for (var i = 0; i < commits.length; i++) {
	var c = this.displayCommits[commits[i].hash];
	var w = c.labelWidth(dummyCtx);
	w += commitY * (c.column + 1);
	if (w > longestWidth) {
	longestWidth = w;
	}
	}

	// Redraw the canvas.
	var scale = window.devicePixelRatio \|\| 1.0;
	var canvas = this.$.commitCanvas;
	this.canvasWidth = Math.max(longestWidth + paddingX, MIN_CANVAS_WIDTH);
	this.canvasHeight = commitY * commits.length;
	canvas.style.width = Math.floor(this.canvasWidth) + "px";
	canvas.style.height = Math.floor(this.canvasHeight) + "px";
	canvas.width = this.canvasWidth * scale;
	canvas.height = this.canvasHeight * scale;
	var ctx = canvas.getContext("2d");
	ctx.clearRect(0, 0, canvas.width, canvas.height);
	ctx.setTransform(scale, 0, 0, scale, 0, 0);
	ctx.font = font;

	// Shade an alternating background.
	for (var i = 0; i < commits.length; i++) {
	this.displayCommits[commits[i].hash].drawBackground(ctx);
	}

	// Create the color palette for the commits.
	palette = [
	this.getComputedStyleValue("--color-bluegreen"),
	this.getComputedStyleValue("--color-redorange"),
	this.getComputedStyleValue("--color-purple"),
	this.getComputedStyleValue("--color-pink"),
	this.getComputedStyleValue("--color-lightgreen"),
	this.getComputedStyleValue("--color-lightorange"),
	this.getComputedStyleValue("--color-burntorange"),
	this.getComputedStyleValue("--color-gray"),
	];

	// Draw the commits.
	for (var i = 0; i < commits.length; i++) {
	this.displayCommits[commits[i].hash].draw(ctx, this.displayCommits);
	}

	console.timeEnd("draw");
	},

	// _computeLinkMap looks through all the branch_heads, finds the index of each
	// commit belonging to a branch and makes a map of index -> URL. Then, it handles
	// the special case of current autoroll and previous autoroll.
	// The last link added to the map will be the one used. So when there are multiple
	// links added we need prioritize which one should displayed.
	// Here is the current order: Chrome roll links have priority over Android roll links
	// which in turn have priority over branch links.
	_computeLinkMap: function() {
	var linkMap = {};

	// Link to generic branch heads.
	this.branch_heads.forEach(function(branch) {
	var name = branch.name;
	if (branch.name.startsWith(BRANCH_PREFIX)) {
	var name = branch.name.slice(BRANCH_PREFIX.length);
	}
	// If the commit is not found in the range of commits, we will just be
	// overwriting the value at key "-1", which won't actually get used.
	var idx = this._indexOfRevision(branch.head);
	linkMap[idx] = this.repo_base + name;
	}.bind(this));

	// Link to rolls.
	for (var i = 0; i < this.roll_statuses.length; i++) {
	var roller = this.roll_statuses[i];
	var idx = this._indexOfRevision(roller.currentRollRev);
	linkMap[idx] = roller.url;
	idx = this._indexOfRevision(roller.lastRollRev);
	linkMap[idx] = roller.url;
	}
	return linkMap;
	},

	// _computeTitleMap looks through all the branch heads, find the index of each
	// commit belonging to a branch and makes a map of index -> label title.
	_computeTitleMap: function() {
	var titleMap = {};

	this.branch_heads.forEach(function(branch) {
	var name = branch.name;
	var idx = this._indexOfRevision(branch.head);
	if (titleMap[idx]) {
	titleMap[idx] = titleMap[idx] + "," + name;
	} else {
	titleMap[idx] = name;
	}
	}.bind(this));
	return titleMap;
	},

	_indexOfRevision: function(revision) {
	var idx = -1;
	this.commits.forEach(function(c,i){
	if (c.hash === revision){
	idx = i;
	}
	});
	return idx;
	},

	// handleclick converts the click's offsetY (Y location relative to the tapped canvas) into index
	handleclick: function(e) {
	if (!this._linkMap) {
	return;
	}
	var y = (e && e.offsetY) \|\| 1;
	var commitIdx = Math.floor(y / commitY);

	var link = this._linkMap[commitIdx];
	if (link){
	window.open(link);
	}
	},

	handlemouseover: function(e) {
	if (!this._linkMap) {
	return;
	}
	var commitIdx = Math.floor(e.offsetY / commitY);
	var link = this._linkMap[commitIdx];
	if (link){
	this.$.commitCanvas.classList.add("pointer");
	} else {
	this.$.commitCanvas.classList.remove("pointer");
	}
	var title = this._titleMap[commitIdx];
	if (title) {
	this.$.commitCanvas.title = title;
	}
	},

	});
	})();
	</script>
	</dom-module>