← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/repofmt/pack_repo.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-03-15 21:00:35 UTC
  • mfrom: (3228.4.15 revision_graph)
  • Revision ID: pqm@pqm.ubuntu.com-20080315210035-5qwda8bre2nwsra3
(jam) Update PackRepo.get_revision_graph() to efficiently handle
        ghosts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/repofmt/pack_repo.py
1928
1928
            found_parents[key[0]] = parents
1929
1929
        return found_parents
1930
1930
 
 
1931
    @needs_read_lock
 
1932
    def get_revision_graph(self, revision_id=None):
 
1933
        """Return a dictionary containing the revision graph.
 
1934
 
 
1935
        :param revision_id: The revision_id to get a graph from. If None, then
 
1936
        the entire revision graph is returned. This is a deprecated mode of
 
1937
        operation and will be removed in the future.
 
1938
        :return: a dictionary of revision_id->revision_parents_list.
 
1939
        """
 
1940
        if 'evil' in debug.debug_flags:
 
1941
            mutter_callsite(3,
 
1942
                "get_revision_graph scales with size of history.")
 
1943
        # special case NULL_REVISION
 
1944
        if revision_id == _mod_revision.NULL_REVISION:
 
1945
            return {}
 
1946
        if revision_id is None:
 
1947
            revision_vf = self._get_revision_vf()
 
1948
            return revision_vf.get_graph()
 
1949
        g = self.get_graph()
 
1950
        first = g.get_parent_map([revision_id])
 
1951
        if revision_id not in first:
 
1952
            raise errors.NoSuchRevision(self, revision_id)
 
1953
        else:
 
1954
            ancestry = {}
 
1955
            children = {}
 
1956
            NULL_REVISION = _mod_revision.NULL_REVISION
 
1957
            ghosts = set([NULL_REVISION])
 
1958
            for rev_id, parent_ids in g.iter_ancestry([revision_id]):
 
1959
                if parent_ids is None: # This is a ghost
 
1960
                    ghosts.add(rev_id)
 
1961
                    continue
 
1962
                ancestry[rev_id] = parent_ids
 
1963
                for p in parent_ids:
 
1964
                    if p in children:
 
1965
                        children[p].append(rev_id)
 
1966
                    else:
 
1967
                        children[p] = [rev_id]
 
1968
 
 
1969
            if NULL_REVISION in ancestry:
 
1970
                del ancestry[NULL_REVISION]
 
1971
 
 
1972
            # Find all nodes that reference a ghost, and filter the ghosts out
 
1973
            # of their parent lists. To preserve the order of parents, and
 
1974
            # avoid double filtering nodes, we just find all children first,
 
1975
            # and then filter.
 
1976
            children_of_ghosts = set()
 
1977
            for ghost in ghosts:
 
1978
                children_of_ghosts.update(children[ghost])
 
1979
 
 
1980
            for child in children_of_ghosts:
 
1981
                ancestry[child] = tuple(p for p in ancestry[child]
 
1982
                                           if p not in ghosts)
 
1983
            return ancestry
 
1984
 
1931
1985
    def has_revisions(self, revision_ids):
1932
1986
        """See Repository.has_revisions()."""
1933
1987
        revision_ids = set(revision_ids)