Comment 2 for bug 535118

The current implementation now runs for 19minutes without returning. This implementation returns after 12 seconds cpu time with the same repository. I am not completely sure that the sorting will be correct (in the extreme case that an older commit has a newer timestamp).

def revision_history(self, head):
    """Returns a list of the commits reachable from head.

    Returns a list of commit objects. the first of which will be the commit
    of head, then following theat will be the parents.

    Raises NotCommitError if any no commits are referenced, including if the
    head parameter isn't the sha of a commit.

    XXX: work out how to handle merges.
    """
    # We build the list backwards, as parents are more likely to be older
    # than children
    try:
        pending_commits = [self.commit(head)]
    except KeyError:
        raise MissingCommitError(head)

    all_commits = set()
    sorted_commits = []
    while pending_commits != []:
        pending_commits.sort(key=lambda x:x.commit_time, reverse=True)
        commit = pending_commits.pop(0)

        if commit.id in all_commits:
            continue

        all_commits.add(commit.id)
        sorted_commits.append(commit)
        for parent in commit.parents:
            try:
                pending_commits.append(self.commit(parent))
            except KeyError:
                raise MissingCommitError(parent)
    sorted_commits.reverse()
    return sorted_commits