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

    minrev = revs[-1] # assuming sorted with highest revision numbers first

    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):

        """Return branch for rev, using cache for efficiency.

        For Mercurial, always return the named branch name (which may be 'default').

        For Git, return a branch name for branch heads, otherwise None."""

        if rev not in branch_cache:

            branch_cache[rev] = repo[rev].branch

        return branch_cache[rev]

    row = []  # the ancestor revision that each column is tracking

    colors = {}  # color number for revisions - set by descendants

    obs = {}  # obsolete flag for revisions - set by descendants

    newcolor = 1  # the next available color

    for (rev, dagparents) in dag:

        # Compute row and nextrow

        if rev not in row:

            row.append(rev)  # new head

            colors[rev] = newcolor

            obs[rev] = int(repo[rev].obsolete)

            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)

        # Filter old fake parents but keep new ones

        nextrow = []

        for r in tmprow:

            if r >= 0 or r in dagparents:

                nextrow.append(r)

            else:

                colors.pop(r)

                obs.pop(r)

        # Let color and obs for this rev be "inherited" by the first "parent"

        color = colors.pop(rev)

        if addparents:

            b = branch(rev)

            searching = True

            for p in reversed(addparents):

                obs[p] = int(repo[p].obsolete)

                if searching and branch(abs(p)) in [b, None]:

                    # This is the first parent on the same branch - inherit the color

                    colors[p] = color

                    searching = False # make sure we don't give the color away twice

                else:

                    colors[p] = newcolor

                    newcolor += 1

        # Add edges to the graph

        edges = []

        for ecol, ep in enumerate(row):

            if ep in nextrow:

                edges.append((ecol, nextrow.index(ep), colors[ep], obs[ep]))

            elif ep == rev:

                for p in dagparents:

                    edges.append((ecol, nextrow.index(p), colors[p], obs[p]))

        # Yield and move on

        closing = int(repo[rev].closesbranch)

        obsolete = int(repo[rev].obsolete)

        row = nextrow

                break

            yield data

    @LazyProperty

    def root(self):

        """

        Returns ``RootNode`` object for this changeset.

        """

        return self.get_node('')

    def next(self, branch=None):

        """

        Returns next changeset from current, if branch is gives it will return

        next changeset belonging to this branch

        :param branch: show changesets within the given named branch

        """

        raise NotImplementedError

    def prev(self, branch=None):

        """

        Returns previous changeset from current, if branch is gives it will

        return previous changeset belonging to this branch

        :param branch: show changesets within the given named branch

        """

        raise NotImplementedError

    @LazyProperty

    def added(self):

        """

        Returns list of added ``FileNode`` objects.

        """

        raise NotImplementedError

    @LazyProperty

    def changed(self):

        """

        Returns list of modified ``FileNode`` objects.

        """

        raise NotImplementedError

    @LazyProperty

    def removed(self):

        """

        Returns list of removed ``FileNode`` objects.

        """

        raise NotImplementedError

    @LazyProperty

    def size(self):

        """

        Returns total number of bytes from contents of all filenodes.

        """

        return sum((node.size for node in self.get_filenodes_generator()))

    def walk(self, topurl=''):

        """

        Similar to os.walk method. Instead of filesystem it walks through

        changeset starting at given ``topurl``.  Returns generator of tuples

        (topnode, dirnodes, filenodes).

        """

        topnode = self.get_node(topurl)

        yield (topnode, topnode.dirs, topnode.files)

        for dirnode in topnode.dirs:

            for tup in self.walk(dirnode.path):

                yield tup

    def get_filenodes_generator(self):

        """

        Returns generator that yields *all* file nodes.

        """

        for topnode, dirs, files in self.walk():

            for node in files:

                yield node

    def as_dict(self):

        """

        Returns dictionary with changeset's attributes and their values.

        """

        data = get_dict_for_attrs(self, ['id', 'raw_id', 'short_id',

            'revision', 'date', 'message'])

        data['author'] = {'name': self.author_name, 'email': self.author_email}

        data['added'] = [node.path for node in self.added]

        data['changed'] = [node.path for node in self.changed]

        data['removed'] = [node.path for node in self.removed]

        return data

    @LazyProperty

    def closesbranch(self):

        return False

    @LazyProperty

    def obsolete(self):

        return False

class BaseWorkdir(object):

    """

    Working directory representation of single repository.

    :attribute: repository: repository object of working directory

    """

    def __init__(self, repository):

        self.repository = repository

    def get_branch(self):

        """

        Returns name of current branch.

        """

        raise NotImplementedError

    def get_changeset(self):

        """

        Returns current changeset.

        """

        raise NotImplementedError

    def get_added(self):

        """

        Returns list of ``FileNode`` objects marked as *new* in working

        directory.

        """

        raise NotImplementedError

    def get_changed(self):

        """

        Returns list of ``FileNode`` objects *changed* in working directory.

        """

        raise NotImplementedError

    def get_removed(self):

        """

        Returns list of ``RemovedFileNode`` objects marked as *removed* in

        working directory.

        """

        raise NotImplementedError

    def get_untracked(self):

        """

        Returns list of ``FileNode`` objects which are present within working

        directory however are not tracked by repository.

        """

        raise NotImplementedError

    def get_status(self):

        """

        Returns dict with ``added``, ``changed``, ``removed`` and ``untracked``

        lists.

        """

        raise NotImplementedError

    def commit(self, message, **kwargs):

        """

        Commits local (from working directory) changes and returns newly

        created

        ``Changeset``. Updates repository's ``revisions`` list.

        :raises ``CommitError``: if any error occurs while committing

        """

        raise NotImplementedError

    def update(self, revision=None):

        """

        Fetches content of the given revision and populates it within working

        directory.

        """

        raise NotImplementedError

    def checkout_branch(self, branch=None):

        """

        Checks out ``branch`` or the backend's default branch.

        Raises ``BranchDoesNotExistError`` if the branch does not exist.

        """

        raise NotImplementedError

class BaseInMemoryChangeset(object):

    """

    Represents differences between repository's state (most recent head) and

    changes made *in place*.

    **Attributes**

        ``repository``

            repository object for this in-memory-changeset

        ``added``

            list of ``FileNode`` objects marked as *added*

        ``changed``

import os

import posixpath

from kallithea.lib.vcs.conf import settings

from kallithea.lib.vcs.backends.base import BaseChangeset

from kallithea.lib.vcs.exceptions import (

    ChangesetDoesNotExistError, ChangesetError, ImproperArchiveTypeError,

    NodeDoesNotExistError, VCSError

)

from kallithea.lib.vcs.nodes import (

    AddedFileNodesGenerator, ChangedFileNodesGenerator, DirNode, FileNode,

    NodeKind, RemovedFileNodesGenerator, RootNode, SubModuleNode

)

from kallithea.lib.vcs.utils import safe_str, safe_unicode, date_fromtimestamp

from kallithea.lib.vcs.utils.lazy import LazyProperty

from kallithea.lib.vcs.utils.paths import get_dirs_for_path

from kallithea.lib.vcs.utils.hgcompat import archival, hex

from mercurial import obsolete

class MercurialChangeset(BaseChangeset):

    """

    Represents state of the repository at the single revision.

    """

    def __init__(self, repository, revision):

        self.repository = repository

        assert isinstance(revision, basestring), repr(revision)

        self.raw_id = revision

        self._ctx = repository._repo[revision]

        self.revision = self._ctx._rev

        self.nodes = {}

    @LazyProperty

    def tags(self):

        return map(safe_unicode, self._ctx.tags())

    @LazyProperty

    def branch(self):

        return  safe_unicode(self._ctx.branch())

    @LazyProperty

    def closesbranch(self):

        return  self._ctx.closesbranch()

    @LazyProperty

    def obsolete(self):

        return  self._ctx.obsolete()

    @LazyProperty

    def successors(self):

        successors = obsolete.successorssets(self._ctx._repo, self._ctx.node())

        if successors:

            # flatten the list here handles both divergent (len > 1)

            # and the usual case (len = 1)

            successors = [hex(n)[:12] for sub in successors for n in sub if n != self._ctx.node()]

        return successors

    @LazyProperty

    def precursors(self):

        precursors = set()

        nm = self._ctx._repo.changelog.nodemap

        for p in self._ctx._repo.obsstore.precursors.get(self._ctx.node(), ()):

            pr = nm.get(p[0])

            if pr is not None:

                precursors.add(hex(p[0])[:12])

        return precursors

    @LazyProperty

    def bookmarks(self):

        return map(safe_unicode, self._ctx.bookmarks())

    @LazyProperty

    def message(self):

        return safe_unicode(self._ctx.description())

    @LazyProperty

    def committer(self):

        return safe_unicode(self.author)

    @LazyProperty

    def author(self):

        return safe_unicode(self._ctx.user())

    @LazyProperty

    def date(self):

        return date_fromtimestamp(*self._ctx.date())

    @LazyProperty

    def _timestamp(self):

        return self._ctx.date()[0]

    @LazyProperty

    def status(self):

        """

        Returns modified, added, removed, deleted files for current changeset

        """

        return self.repository._repo.status(self._ctx.p1().node(),

                                            self._ctx.node())

    @LazyProperty

    def _file_paths(self):

        return list(self._ctx)

    @LazyProperty

    def _dir_paths(self):

        p = list(set(get_dirs_for_path(*self._file_paths)))

        p.insert(0, '')

        return p

    @LazyProperty

    def _paths(self):

        return self._dir_paths + self._file_paths

    @LazyProperty

    def id(self):

        if self.last:

            return u'tip'

        return self.short_id

    @LazyProperty

    def short_id(self):

        return self.raw_id[:12]

    @LazyProperty

    def parents(self):

        """

        Returns list of parents changesets.

        """

        return [self.repository.get_changeset(parent.rev())

                for parent in self._ctx.parents() if parent.rev() >= 0]

    @LazyProperty

    def children(self):

        """

        Returns list of children changesets.

        """

        return [self.repository.get_changeset(child.rev())

                for child in self._ctx.children() if child.rev() >= 0]

    def next(self, branch=None):

        if branch and self.branch != branch:

            raise VCSError('Branch option used on changeset not belonging '

                           'to that branch')

var colors = [

	[ 1.0, 0.0, 0.0 ],

	[ 1.0, 1.0, 0.0 ],

	[ 0.0, 1.0, 0.0 ],

	[ 0.0, 1.0, 1.0 ],

	[ 0.0, 0.0, 1.0 ],

	[ 1.0, 0.0, 1.0 ],

	[ 1.0, 1.0, 0.0 ],

	[ 0.0, 0.0, 0.0 ]

];

function BranchRenderer(canvas_id, content_id, row_id_prefix) {

	// canvas_id is canvas to render into

	// content_id's height is applied to canvas

	// row_id_prefix is prefix that is applied to get row id's

	this.canvas = document.getElementById(canvas_id);

	var content = document.getElementById(content_id);

	if (!document.createElement("canvas").getContext)

		this.canvas = window.G_vmlCanvasManager.initElement(this.canvas);

	if (!this.canvas) { // canvas creation did for some reason fail - fail silently

		this.render = function(data,canvasWidth) {};

		return;

	}

	this.ctx = this.canvas.getContext('2d');

	this.ctx.strokeStyle = 'rgb(0, 0, 0)';

	this.ctx.fillStyle = 'rgb(0, 0, 0)';

	this.cur = [0, 0];

	this.line_width = 2.0;

	this.dot_radius = 3.5;

	this.close_x = 1.5 * this.dot_radius;

	this.close_y = 0.5 * this.dot_radius;

	this.calcColor = function(color, bg, fg) {

		color %= colors.length;

		var red = (colors[color][0] * fg) || bg;

		var green = (colors[color][1] * fg) || bg;

		var blue = (colors[color][2] * fg) || bg;

		red = Math.round(red * 255);

		green = Math.round(green * 255);

		blue = Math.round(blue * 255);

		var s = 'rgb(' + red + ', ' + green + ', ' + blue + ')';

		return s;

	}

	this.setColor = function(color, bg, fg) {

		var s = this.calcColor(color, bg, fg);

		this.ctx.strokeStyle = s;

		this.ctx.fillStyle = s;

	}

	this.render = function(data,canvasWidth) {

		var idx = 1;

		this.canvas.setAttribute('width',canvasWidth);

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

		// 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];

				obsolete_line = line[3];

				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();

				if (obsolete_line)

				{

					this.ctx.setLineDash([5]);

				}

				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;

					if (obsolete_node)

					{

						this.ctx.setLineDash([5]);

					}

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

				}

				this.ctx.stroke();

				this.ctx.setLineDash([]); // reset the dashed line, if any

			}

			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++;

		}

	}

}

from kallithea.tests import *

class TestChangelogController(TestController):

    def test_index_hg(self):

        self.log_user()

        response = self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO))

        response.mustcontain('''id="chg_20" class="container mergerow"''')

        response.mustcontain(

            """<input class="changeset_range" """

            """id="7b22a518347bb9bc19679f6af07cd0a61bfe16e7" """

            """name="7b22a518347bb9bc19679f6af07cd0a61bfe16e7" """

            """type="checkbox" value="1" />"""

        )

        #rev 640: code garden

        response.mustcontain(

            """<span class="changeset_hash">r640:0a4e54a44604</span>"""

        )

        response.mustcontain("""code garden""")

    def test_index_pagination_hg(self):

        self.log_user()

        #pagination

        self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 1})

        self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 2})

        self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 3})

        self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 4})

        self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 5})

        response = self.app.get(url(controller='changelog', action='index',

                                    repo_name=HG_REPO), {'page': 6, 'size': 20})

        # Test response after pagination...

        response.mustcontain(

            """<input class="changeset_range" """

            """id="22baf968d547386b9516965ce89d189665003a31" """

            """name="22baf968d547386b9516965ce89d189665003a31" """

            """type="checkbox" value="1" />"""

        )

        response.mustcontain(

            """<span class="changeset_hash">r539:22baf968d547</span>"""

        )

    def test_index_git(self):

        self.log_user()

        response = self.app.get(url(controller='changelog', action='index',

                                    repo_name=GIT_REPO))

        response.mustcontain('''id="chg_20" class="container "''') # why no mergerow for git?

        response.mustcontain(

            """<input class="changeset_range" """

            """id="95f9a91d775b0084b2368ae7779e44931c849c0e" """

            """name="95f9a91d775b0084b2368ae7779e44931c849c0e" """

            """type="checkbox" value="1" />"""

        )

        response.mustcontain(

            """<span class="changeset_hash">r613:95f9a91d775b</span>"""

        )

        response.mustcontain("""fixing stupid typo in context for mercurial""")