comparison mercurial/revlogutils/deltas.py @ 49678:efbbc2f9121e

delta-find: use a smarter object for snapshot caching

This open the way for a longer lived cache.

49677:05db41701ece

                        break

    yield None


def _findsnapshots(revlog, cache, start_rev):
    """find snapshot from start_rev to tip"""
    if util.safehasattr(revlog.index, b'findsnapshots'):
        revlog.index.findsnapshots(cache, start_rev)
    else:
        deltaparent = revlog.deltaparent
        issnapshot = revlog.issnapshot
        for rev in revlog.revs(start_rev):
            if issnapshot(rev):
                cache[deltaparent(rev)].append(rev)


def _refinedgroups(revlog, p1, p2, cachedelta):
    good = None
    # First we try to reuse a the delta contained in the bundle.
    # (or from the source revlog)
    #

            if debug_info is not None:
                debug_info['cached-delta.accepted'] += 1
            yield None
            return
    # XXX cache me higher
    snapshots = collections.defaultdict(list)
    groups = _rawgroups(
        revlog,
        p1,
        p2,
        cachedelta,
        snapshots,
    )
    for candidates in groups:
        good = yield candidates
        if good is not None:
            break

            base = revlog.deltaparent(good)
            if base == nullrev:
                break
            good = yield (base,)
        # refine snapshot up
        if not snapshots:
            _findsnapshots(revlog, snapshots, good + 1)
        previous = None
        while good != previous:
            previous = good
            children = tuple(sorted(c for c in snapshots[good]))
            good = yield children

    if debug_info is not None:
        if good is None:
            debug_info['no-solution'] += 1

    yield None


def _rawgroups(revlog, p1, p2, cachedelta, snapshots=None):
    """Provides group of revision to be tested as delta base

    This lower level function focus on emitting delta theorically interresting
    without looking it any practical details.

        elif len(parents) > 0:
            # Test all parents (1 or 2), and keep the best candidate
            yield parents

    if sparse and parents:
        if snapshots is None:
            # map: base-rev: [snapshot-revs]
            snapshots = collections.defaultdict(list)
        # See if we can use an existing snapshot in the parent chains to use as
        # a base for a new intermediate-snapshot
        #
        # search for snapshot in parents delta chain
        # map: snapshot-level: snapshot-rev

            for idx, s in enumerate(chain):
                if not revlog.issnapshot(s):
                    break
                parents_snaps[idx].add(s)
        snapfloor = min(parents_snaps[0]) + 1
        _findsnapshots(revlog, snapshots, snapfloor)
        # search for the highest "unrelated" revision
        #
        # Adding snapshots used by "unrelated" revision increase the odd we
        # reuse an independant, yet better snapshot chain.
        #

        # likely to result in small delta
        floor = None
        for idx, snaps in sorted(parents_snaps.items(), reverse=True):
            siblings = set()
            for s in snaps:
                siblings.update(snapshots[s])
            # Before considering making a new intermediate snapshot, we check
            # if an existing snapshot, children of base we consider, would be
            # suitable.
            #
            # It give a change to reuse a delta chain "unrelated" to the

        #
        # It give a chance to reuse a delta chain unrelated to the current
        # revisions instead of starting our own. Without such re-use,
        # topological branches would keep reopening new full chains. Creating
        # more and more snapshot as the repository grow.
        yield tuple(snapshots[nullrev])

    if not sparse:
        # other approach failed try against prev to hopefully save us a
        # fulltext.
        yield (prev,)


class deltacomputer:
    def __init__(
        self,

49678:efbbc2f9121e

                        break

    yield None


def _refinedgroups(revlog, p1, p2, cachedelta):
    good = None
    # First we try to reuse a the delta contained in the bundle.
    # (or from the source revlog)
    #

            if debug_info is not None:
                debug_info['cached-delta.accepted'] += 1
            yield None
            return
    # XXX cache me higher
    snapshot_cache = SnapshotCache()
    groups = _rawgroups(
        revlog,
        p1,
        p2,
        cachedelta,
        snapshot_cache,
    )
    for candidates in groups:
        good = yield candidates
        if good is not None:
            break

            base = revlog.deltaparent(good)
            if base == nullrev:
                break
            good = yield (base,)
        # refine snapshot up
        if not snapshot_cache.snapshots:
            snapshot_cache.update(revlog, good + 1)
        previous = None
        while good != previous:
            previous = good
            children = tuple(sorted(c for c in snapshot_cache.snapshots[good]))
            good = yield children

    if debug_info is not None:
        if good is None:
            debug_info['no-solution'] += 1

    yield None


def _rawgroups(revlog, p1, p2, cachedelta, snapshot_cache=None):
    """Provides group of revision to be tested as delta base

    This lower level function focus on emitting delta theorically interresting
    without looking it any practical details.

        elif len(parents) > 0:
            # Test all parents (1 or 2), and keep the best candidate
            yield parents

    if sparse and parents:
        if snapshot_cache is None:
            # map: base-rev: [snapshot-revs]
            snapshot_cache = SnapshotCache()
        # See if we can use an existing snapshot in the parent chains to use as
        # a base for a new intermediate-snapshot
        #
        # search for snapshot in parents delta chain
        # map: snapshot-level: snapshot-rev

            for idx, s in enumerate(chain):
                if not revlog.issnapshot(s):
                    break
                parents_snaps[idx].add(s)
        snapfloor = min(parents_snaps[0]) + 1
        snapshot_cache.update(revlog, snapfloor)
        # search for the highest "unrelated" revision
        #
        # Adding snapshots used by "unrelated" revision increase the odd we
        # reuse an independant, yet better snapshot chain.
        #

        # likely to result in small delta
        floor = None
        for idx, snaps in sorted(parents_snaps.items(), reverse=True):
            siblings = set()
            for s in snaps:
                siblings.update(snapshot_cache.snapshots[s])
            # Before considering making a new intermediate snapshot, we check
            # if an existing snapshot, children of base we consider, would be
            # suitable.
            #
            # It give a change to reuse a delta chain "unrelated" to the

        #
        # It give a chance to reuse a delta chain unrelated to the current
        # revisions instead of starting our own. Without such re-use,
        # topological branches would keep reopening new full chains. Creating
        # more and more snapshot as the repository grow.
        yield tuple(snapshot_cache.snapshots[nullrev])

    if not sparse:
        # other approach failed try against prev to hopefully save us a
        # fulltext.
        yield (prev,)


class SnapshotCache:
    __slots__ = ('snapshots', '_start_rev', '_end_rev')

    def __init__(self):
        # XXX should probably be a set ?
        self.snapshots = collections.defaultdict(list)
        self._start_rev = None
        self._end_rev = None

    def update(self, revlog, start_rev=0):
        """find snapshots from start_rev to tip"""
        nb_revs = len(revlog)
        end_rev = nb_revs - 1
        if start_rev > end_rev:
            return  # range is empty

        if self._start_rev is None:
            assert self._end_rev is None
            self._update(revlog, start_rev, end_rev)
        elif not (self._start_rev <= start_rev and end_rev <= self._end_rev):
            if start_rev < self._start_rev:
                self._update(revlog, start_rev, self._start_rev - 1)
            if self._end_rev < end_rev:
                self._update(revlog, self._end_rev + 1, end_rev)

        if self._start_rev is None:
            assert self._end_rev is None
            self._end_rev = end_rev
            self._start_rev = start_rev
        else:
            self._start_rev = min(self._start_rev, start_rev)
            self._end_rev = max(self._end_rev, end_rev)
        assert self._start_rev <= self._end_rev, (
            self._start_rev,
            self._end_rev,
        )

    def _update(self, revlog, start_rev, end_rev):
        """internal method that actually do update content"""
        assert self._start_rev is None or (
            start_rev < self._start_rev or start_rev > self._end_rev
        ), (self._start_rev, self._end_rev, start_rev, end_rev)
        assert self._start_rev is None or (
            end_rev < self._start_rev or end_rev > self._end_rev
        ), (self._start_rev, self._end_rev, start_rev, end_rev)
        cache = self.snapshots
        if util.safehasattr(revlog.index, b'findsnapshots'):
            revlog.index.findsnapshots(cache, start_rev, end_rev)
        else:
            deltaparent = revlog.deltaparent
            issnapshot = revlog.issnapshot
            for rev in revlog.revs(start_rev, end_rev):
                if issnapshot(rev):
                    cache[deltaparent(rev)].append(rev)


class deltacomputer:
    def __init__(
        self,