← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Jelmer Vernooij
  • Date: 2011-04-09 22:14:24 UTC
  • mfrom: (5777.4.2 mutableinventorytree)
  • mto: This revision was merged to the branch mainline in revision 5787.
  • Revision ID: jelmer@samba.org-20110409221424-a2air35exbz50hi8
Mergemutableinventorytree.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
23
23
    revision,
24
24
    trace,
25
25
    )
 
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
26
27
 
27
28
STEP_UNIQUE_SEARCHER_EVERY = 5
28
29
 
58
59
    def __repr__(self):
59
60
        return 'DictParentsProvider(%r)' % self.ancestry
60
61
 
61
 
    # Note: DictParentsProvider does not implement get_cached_parent_map
62
 
    #       Arguably, the data is clearly cached in memory. However, this class
63
 
    #       is mostly used for testing, and it keeps the tests clean to not
64
 
    #       change it.
65
 
 
66
62
    def get_parent_map(self, keys):
67
63
        """See StackedParentsProvider.get_parent_map"""
68
64
        ancestry = self.ancestry
69
 
        return dict([(k, ancestry[k]) for k in keys if k in ancestry])
 
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
70
66
 
71
67
 
72
68
class StackedParentsProvider(object):
73
69
    """A parents provider which stacks (or unions) multiple providers.
74
 
 
 
70
    
75
71
    The providers are queries in the order of the provided parent_providers.
76
72
    """
77
 
 
 
73
    
78
74
    def __init__(self, parent_providers):
79
75
        self._parent_providers = parent_providers
80
76
 
96
92
        """
97
93
        found = {}
98
94
        remaining = set(keys)
99
 
        # This adds getattr() overhead to each get_parent_map call. However,
100
 
        # this is StackedParentsProvider, which means we're dealing with I/O
101
 
        # (either local indexes, or remote RPCs), so CPU overhead should be
102
 
        # minimal.
103
 
        for parents_provider in self._parent_providers:
104
 
            get_cached = getattr(parents_provider, 'get_cached_parent_map',
105
 
                                 None)
106
 
            if get_cached is None:
107
 
                continue
108
 
            new_found = get_cached(remaining)
109
 
            found.update(new_found)
110
 
            remaining.difference_update(new_found)
111
 
            if not remaining:
112
 
                break
113
 
        if not remaining:
114
 
            return found
115
95
        for parents_provider in self._parent_providers:
116
96
            new_found = parents_provider.get_parent_map(remaining)
117
97
            found.update(new_found)
171
151
            return None
172
152
        return dict(self._cache)
173
153
 
174
 
    def get_cached_parent_map(self, keys):
175
 
        """Return items from the cache.
176
 
 
177
 
        This returns the same info as get_parent_map, but explicitly does not
178
 
        invoke the supplied ParentsProvider to search for uncached values.
179
 
        """
180
 
        cache = self._cache
181
 
        if cache is None:
182
 
            return {}
183
 
        return dict([(key, cache[key]) for key in keys if key in cache])
184
 
 
185
154
    def get_parent_map(self, keys):
186
155
        """See StackedParentsProvider.get_parent_map."""
187
156
        cache = self._cache
211
180
            self.missing_keys.add(key)
212
181
 
213
182
 
214
 
class CallableToParentsProviderAdapter(object):
215
 
    """A parents provider that adapts any callable to the parents provider API.
216
 
 
217
 
    i.e. it accepts calls to self.get_parent_map and relays them to the
218
 
    callable it was constructed with.
219
 
    """
220
 
 
221
 
    def __init__(self, a_callable):
222
 
        self.callable = a_callable
223
 
 
224
 
    def __repr__(self):
225
 
        return "%s(%r)" % (self.__class__.__name__, self.callable)
226
 
 
227
 
    def get_parent_map(self, keys):
228
 
        return self.callable(keys)
229
 
 
230
 
 
231
183
class Graph(object):
232
184
    """Provide incremental access to revision graphs.
233
185
 
282
234
        common ancestor of all border ancestors, because this shows that it
283
235
        cannot be a descendant of any border ancestor.
284
236
 
285
 
        The scaling of this operation should be proportional to:
286
 
 
 
237
        The scaling of this operation should be proportional to
287
238
        1. The number of uncommon ancestors
288
239
        2. The number of border ancestors
289
240
        3. The length of the shortest path between a border ancestor and an
421
372
 
422
373
        :param unique_revision: The revision_id whose ancestry we are
423
374
            interested in.
424
 
            (XXX: Would this API be better if we allowed multiple revisions on
425
 
            to be searched here?)
 
375
            XXX: Would this API be better if we allowed multiple revisions on
 
376
                 to be searched here?
426
377
        :param common_revisions: Revision_ids of ancestries to exclude.
427
378
        :return: A set of revisions in the ancestry of unique_revision
428
379
        """
1451
1402
        parents_of_found = set()
1452
1403
        # revisions may contain nodes that point to other nodes in revisions:
1453
1404
        # we want to filter them out.
1454
 
        seen = self.seen
1455
 
        seen.update(revisions)
 
1405
        self.seen.update(revisions)
1456
1406
        parent_map = self._parents_provider.get_parent_map(revisions)
1457
1407
        found_revisions.update(parent_map)
1458
1408
        for rev_id, parents in parent_map.iteritems():
1459
1409
            if parents is None:
1460
1410
                continue
1461
 
            new_found_parents = [p for p in parents if p not in seen]
 
1411
            new_found_parents = [p for p in parents if p not in self.seen]
1462
1412
            if new_found_parents:
1463
1413
                # Calling set.update() with an empty generator is actually
1464
1414
                # rather expensive.
1597
1547
 
1598
1548
        The recipe allows reconstruction of the same results at a later date.
1599
1549
 
1600
 
        :return: A tuple of `(search_kind_str, *details)`.  The details vary by
 
1550
        :return: A tuple of (search_kind_str, *details).  The details vary by
1601
1551
            kind of search result.
1602
1552
        """
1603
1553
        raise NotImplementedError(self.get_recipe)
1882
1832
    """Find all revisions missing in one repo for a some specific heads."""
1883
1833
 
1884
1834
    def __init__(self, to_repo, from_repo, required_ids, if_present_ids=None,
1885
 
            find_ghosts=False, limit=None):
 
1835
            find_ghosts=False):
1886
1836
        """Constructor.
1887
1837
 
1888
1838
        :param required_ids: revision IDs of heads that must be found, or else
1892
1842
        :param if_present_ids: revision IDs of heads that may be absent in the
1893
1843
            source repository.  If present, then their ancestry not already
1894
1844
            found in other will be included in the search result.
1895
 
        :param limit: maximum number of revisions to fetch
1896
1845
        """
1897
1846
        self.to_repo = to_repo
1898
1847
        self.from_repo = from_repo
1899
1848
        self.find_ghosts = find_ghosts
1900
1849
        self.required_ids = required_ids
1901
1850
        self.if_present_ids = if_present_ids
1902
 
        self.limit = limit
1903
1851
 
1904
1852
    def __repr__(self):
1905
1853
        if len(self.required_ids) > 5:
1911
1859
        else:
1912
1860
            ifp_revs_repr = repr(self.if_present_ids)
1913
1861
 
1914
 
        return ("<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r"
1915
 
                "limit:%r>") % (
1916
 
                self.__class__.__name__, self.from_repo, self.to_repo,
1917
 
                self.find_ghosts, reqd_revs_repr, ifp_revs_repr,
1918
 
                self.limit)
 
1862
        return "<%s from:%r to:%r find_ghosts:%r req'd:%r if-present:%r>" % (
 
1863
            self.__class__.__name__, self.from_repo, self.to_repo,
 
1864
            self.find_ghosts, reqd_revs_repr, ifp_revs_repr)
1919
1865
 
1920
1866
    def execute(self):
1921
1867
        return self.to_repo.search_missing_revision_ids(
1922
1868
            self.from_repo, revision_ids=self.required_ids,
1923
 
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts,
1924
 
            limit=self.limit)
1925
 
 
1926
 
 
1927
 
def invert_parent_map(parent_map):
1928
 
    """Given a map from child => parents, create a map of parent=>children"""
1929
 
    child_map = {}
1930
 
    for child, parents in parent_map.iteritems():
1931
 
        for p in parents:
1932
 
            # Any given parent is likely to have only a small handful
1933
 
            # of children, many will have only one. So we avoid mem overhead of
1934
 
            # a list, in exchange for extra copying of tuples
1935
 
            if p not in child_map:
1936
 
                child_map[p] = (child,)
1937
 
            else:
1938
 
                child_map[p] = child_map[p] + (child,)
1939
 
    return child_map
1940
 
 
1941
 
 
1942
 
def _find_possible_heads(parent_map, tip_keys, depth):
1943
 
    """Walk backwards (towards children) through the parent_map.
1944
 
 
1945
 
    This finds 'heads' that will hopefully succinctly describe our search
1946
 
    graph.
1947
 
    """
1948
 
    child_map = invert_parent_map(parent_map)
1949
 
    heads = set()
1950
 
    current_roots = tip_keys
1951
 
    walked = set(current_roots)
1952
 
    while current_roots and depth > 0:
1953
 
        depth -= 1
1954
 
        children = set()
1955
 
        children_update = children.update
1956
 
        for p in current_roots:
1957
 
            # Is it better to pre- or post- filter the children?
1958
 
            try:
1959
 
                children_update(child_map[p])
1960
 
            except KeyError:
1961
 
                heads.add(p)
1962
 
        # If we've seen a key before, we don't want to walk it again. Note that
1963
 
        # 'children' stays relatively small while 'walked' grows large. So
1964
 
        # don't use 'difference_update' here which has to walk all of 'walked'.
1965
 
        # '.difference' is smart enough to walk only children and compare it to
1966
 
        # walked.
1967
 
        children = children.difference(walked)
1968
 
        walked.update(children)
1969
 
        current_roots = children
1970
 
    if current_roots:
1971
 
        # We walked to the end of depth, so these are the new tips.
1972
 
        heads.update(current_roots)
1973
 
    return heads
1974
 
 
1975
 
 
1976
 
def _run_search(parent_map, heads, exclude_keys):
1977
 
    """Given a parent map, run a _BreadthFirstSearcher on it.
1978
 
 
1979
 
    Start at heads, walk until you hit exclude_keys. As a further improvement,
1980
 
    watch for any heads that you encounter while walking, which means they were
1981
 
    not heads of the search.
1982
 
 
1983
 
    This is mostly used to generate a succinct recipe for how to walk through
1984
 
    most of parent_map.
1985
 
 
1986
 
    :return: (_BreadthFirstSearcher, set(heads_encountered_by_walking))
1987
 
    """
1988
 
    g = Graph(DictParentsProvider(parent_map))
1989
 
    s = g._make_breadth_first_searcher(heads)
1990
 
    found_heads = set()
1991
 
    while True:
1992
 
        try:
1993
 
            next_revs = s.next()
1994
 
        except StopIteration:
1995
 
            break
1996
 
        for parents in s._current_parents.itervalues():
1997
 
            f_heads = heads.intersection(parents)
1998
 
            if f_heads:
1999
 
                found_heads.update(f_heads)
2000
 
        stop_keys = exclude_keys.intersection(next_revs)
2001
 
        if stop_keys:
2002
 
            s.stop_searching_any(stop_keys)
2003
 
    for parents in s._current_parents.itervalues():
2004
 
        f_heads = heads.intersection(parents)
2005
 
        if f_heads:
2006
 
            found_heads.update(f_heads)
2007
 
    return s, found_heads
2008
 
 
2009
 
 
2010
 
def limited_search_result_from_parent_map(parent_map, missing_keys, tip_keys,
2011
 
                                          depth):
2012
 
    """Transform a parent_map that is searching 'tip_keys' into an
2013
 
    approximate SearchResult.
2014
 
 
2015
 
    We should be able to generate a SearchResult from a given set of starting
2016
 
    keys, that covers a subset of parent_map that has the last step pointing at
2017
 
    tip_keys. This is to handle the case that really-long-searches shouldn't be
2018
 
    started from scratch on each get_parent_map request, but we *do* want to
2019
 
    filter out some of the keys that we've already seen, so we don't get
2020
 
    information that we already know about on every request.
2021
 
 
2022
 
    The server will validate the search (that starting at start_keys and
2023
 
    stopping at stop_keys yields the exact key_count), so we have to be careful
2024
 
    to give an exact recipe.
2025
 
 
2026
 
    Basic algorithm is:
2027
 
        1) Invert parent_map to get child_map (todo: have it cached and pass it
2028
 
           in)
2029
 
        2) Starting at tip_keys, walk towards children for 'depth' steps.
2030
 
        3) At that point, we have the 'start' keys.
2031
 
        4) Start walking parent_map from 'start' keys, counting how many keys
2032
 
           are seen, and generating stop_keys for anything that would walk
2033
 
           outside of the parent_map.
2034
 
 
2035
 
    :param parent_map: A map from {child_id: (parent_ids,)}
2036
 
    :param missing_keys: parent_ids that we know are unavailable
2037
 
    :param tip_keys: the revision_ids that we are searching
2038
 
    :param depth: How far back to walk.
2039
 
    """
2040
 
    if not parent_map:
2041
 
        # No search to send, because we haven't done any searching yet.
2042
 
        return [], [], 0
2043
 
    heads = _find_possible_heads(parent_map, tip_keys, depth)
2044
 
    s, found_heads = _run_search(parent_map, heads, set(tip_keys))
2045
 
    _, start_keys, exclude_keys, key_count = s.get_result().get_recipe()
2046
 
    if found_heads:
2047
 
        # Anything in found_heads are redundant start_keys, we hit them while
2048
 
        # walking, so we can exclude them from the start list.
2049
 
        start_keys = set(start_keys).difference(found_heads)
2050
 
    return start_keys, exclude_keys, key_count
2051
 
 
2052
 
 
2053
 
def search_result_from_parent_map(parent_map, missing_keys):
2054
 
    """Transform a parent_map into SearchResult information."""
2055
 
    if not parent_map:
2056
 
        # parent_map is empty or None, simple search result
2057
 
        return [], [], 0
2058
 
    # start_set is all the keys in the cache
2059
 
    start_set = set(parent_map)
2060
 
    # result set is all the references to keys in the cache
2061
 
    result_parents = set()
2062
 
    for parents in parent_map.itervalues():
2063
 
        result_parents.update(parents)
2064
 
    stop_keys = result_parents.difference(start_set)
2065
 
    # We don't need to send ghosts back to the server as a position to
2066
 
    # stop either.
2067
 
    stop_keys.difference_update(missing_keys)
2068
 
    key_count = len(parent_map)
2069
 
    if (revision.NULL_REVISION in result_parents
2070
 
        and revision.NULL_REVISION in missing_keys):
2071
 
        # If we pruned NULL_REVISION from the stop_keys because it's also
2072
 
        # in our cache of "missing" keys we need to increment our key count
2073
 
        # by 1, because the reconsitituted SearchResult on the server will
2074
 
        # still consider NULL_REVISION to be an included key.
2075
 
        key_count += 1
2076
 
    included_keys = start_set.intersection(result_parents)
2077
 
    start_set.difference_update(included_keys)
2078
 
    return start_set, stop_keys, key_count
 
1869
            if_present_ids=self.if_present_ids, find_ghosts=self.find_ghosts)
2079
1870
 
2080
1871
 
2081
1872
def collapse_linear_regions(parent_map):
2167
1958
        return set([h[0] for h in head_keys])
2168
1959
 
2169
1960
    def merge_sort(self, tip_revision):
2170
 
        nodes = self._graph.merge_sort((tip_revision,))
2171
 
        for node in nodes:
2172
 
            node.key = node.key[0]
2173
 
        return nodes
 
1961
        return self._graph.merge_sort((tip_revision,))
2174
1962
 
2175
1963
    def add_node(self, revision, parents):
2176
1964
        self._graph.add_node((revision,), [(p,) for p in parents])