def _dagwalker(repo, revs):

    if not revs:

        return

    if repo.alias == 'hg':

        parentrev_func = repo._repo.changelog.parentrevs

    elif repo.alias == 'git':

        def parentrev_func(rev):

            return [x.revision for x in repo[rev].parents]

    minrev = revs[-1] # assuming sorted reverse

    knownrevs = set(revs)

    acache = {}

    for rev in revs:

        parents = set(parentrev_func(rev)) - set([nullrev])

        dagparents = parents & knownrevs

        # Calculate indirect parents

        for p in parents - dagparents:

            ancestors = acache.get(p)

            if ancestors is None:

                ancestors = acache[p] = _first_known_ancestors(parentrev_func, minrev, knownrevs, p)

            dagparents.update(ancestors)

        yield (rev, sorted(dagparents))

def _colored(repo, dag):

    """annotates a DAG with colored edge information

    For each DAG node this function emits tuples::

      ((col, color), [(col, nextcol, color)])

    with the following new elements:

      - Tuple (col, color) with column and color index for the current node

      - A list of tuples indicating the edges between the current node and its

        parents.

    """

    branch_cache = {}

    def branch(rev):

        if rev not in branch_cache:

            branch_cache[rev] = repo[rev].branch

        return branch_cache[rev]

    row = []

    colors = {}

    newcolor = 1

    for (rev, dagparents) in dag:

        # Compute row and nextrow

        if rev not in row:

            row.append(rev)  # new head

            colors[rev] = newcolor

            newcolor += 1

        col = row.index(rev)

        addparents = [p for p in dagparents if p not in row]

        # Add unknown parents to nextrow

        tmprow = row[:]

        tmprow[col:col + 1] = reversed(addparents) # highest revs first (to the right), dead ends last (to the left)

        # Stop looking for non-existing ancestors

        nextrow = []

        for r in tmprow:

            if r > nullrev or r in dagparents:

                nextrow.append(r)

            else:

                colors.pop(r)

        # Set colors for the parents

        color = colors.pop(rev)

        if addparents:

            b = branch(rev)

            for p in reversed(addparents):

                if b and branch(abs(p)) == b:

                    colors[p] = color

                    b = None

                else:

                    colors[p] = newcolor

                    newcolor += 1

        # Add edges to the graph

        edges = []

        for ecol, ep in enumerate(row):

            if ep in nextrow:

            elif ep == rev:

                for p in dagparents:

        # Yield and move on

        closing = int(repo[rev].closesbranch)

        obsolete = int(repo[rev].obsolete)

        yield ((col, color), edges, closing, obsolete)

        row = nextrow

		// HiDPI version needs to be scaled by 2x then halved via css

		// Note: Firefox on OS X fails scaling if the canvas height is more than 32k

		if (window.devicePixelRatio && content.clientHeight * window.devicePixelRatio < 32768) {

			this.canvas.setAttribute('width', canvasWidth * window.devicePixelRatio);

			this.canvas.setAttribute('height', content.clientHeight * window.devicePixelRatio);

			this.canvas.style.width = canvasWidth + "px";

			this.canvas.style.height = content.clientHeight + "px";

			this.ctx.scale(window.devicePixelRatio, window.devicePixelRatio);

		}

		var lineCount = 1;

		for (var i=0;i<data.length;i++) {

			var in_l = data[i][1];

			for (var j in in_l) {

				var m = in_l[j][0];

				if (m > lineCount)

					lineCount = m;

			}

		}

		var edge_pad = this.dot_radius + 2;

		var box_size = Math.min(18, (canvasWidth - edge_pad * 2) / lineCount);

		var base_x = canvasWidth - edge_pad;

		for (var i=0; i < data.length; ++i) {

			var row = document.getElementById(row_id_prefix+idx);

			if (row == null) {

				console.log("error: row "+row_id_prefix+idx+" not found");

				continue;

			}

			var next = document.getElementById(row_id_prefix+(idx+1));

			var extra = 0;

			cur = data[i];

			node = cur[0];

			in_l = cur[1];

			closing = cur[2];

			obsolete_node = cur[3];

			var rowY = row.offsetTop + row.offsetHeight/2;

			var nextY = (next == null) ? rowY + row.offsetHeight/2 : next.offsetTop + next.offsetHeight/2;

			for (var j in in_l) {

				line = in_l[j];

				start = line[0];

				end = line[1];

				color = line[2];

				x = Math.floor(base_x - box_size * start);

				// figure out if this is a dead-end;

				// we want to fade away this line

				var dead_end = true;

				if (next != null) {

					nextdata = data[i+1];

					next_l = nextdata[1];

					for (var k=0; k < next_l.length; ++k) {

						if (next_l[k][0] == end) {

							dead_end = false;

							break;

						}

					}

					if (nextdata[0][0] == end) // this is a root - not a dead end

						dead_end = false;

				}

				if (dead_end) {

					var gradient = this.ctx.createLinearGradient(x,rowY,x,nextY);

					gradient.addColorStop(0,this.calcColor(color, 0.0, 0.65));

					gradient.addColorStop(1,this.calcColor(color, 1.0, 0.0));

					this.ctx.strokeStyle = gradient;

					this.ctx.fillStyle = gradient;

				}

				// if this is a merge of differently

				// colored line, make it a gradient towards

				// the merged color

				else if (color != node[1] && start == node[0])

				{

					var gradient = this.ctx.createLinearGradient(x,rowY,x,nextY);

					gradient.addColorStop(0,this.calcColor(node[1], 0.0, 0.65));

					gradient.addColorStop(1,this.calcColor(color, 0.0, 0.65));

					this.ctx.strokeStyle = gradient;

					this.ctx.fillStyle = gradient;

				}

				else

				{

					this.setColor(color, 0.0, 0.65);

				}

				this.ctx.lineWidth=this.line_width;

				this.ctx.beginPath();

				this.ctx.moveTo(x, rowY);

				if (start == end)

				{

					this.ctx.lineTo(x,nextY+extra,3);

				}

				else

				{

					var x2 = Math.floor(base_x - box_size * end);

					var ymid = (rowY+nextY) / 2;

					this.ctx.bezierCurveTo (x,ymid,x2,ymid,x2,nextY);

				}

				this.ctx.stroke();

			}

			column = node[0];

			color = node[1];

			x = Math.floor(base_x - box_size * column);

			this.setColor(color, 0.25, 0.75);

			r = this.dot_radius

			if (obsolete_node)

			{

				this.ctx.beginPath();

				this.ctx.moveTo(x - this.close_x, rowY - this.close_y - 3);

				this.ctx.lineTo(x - this.close_x + 2*this.close_x, rowY - this.close_y + 4*this.close_y - 1);

				this.ctx.moveTo(x - this.close_x, rowY - this.close_y + 4*this.close_y - 1);

				this.ctx.lineTo(x - this.close_x + 2*this.close_x, rowY - this.close_y - 3);

				this.ctx.stroke();

				r -= 0.5

			}

			if (closing)

			{

				this.ctx.fillRect(x - this.close_x, rowY - this.close_y, 2*this.close_x, 2*this.close_y);

			}

			else

			{

				this.ctx.beginPath();

				this.ctx.arc(x, rowY, r, 0, Math.PI * 2, true);

				this.ctx.fill();

			}

			idx++;

		}

	}

}