( )⚙ D4009 exchange: move _computeellipsis() from narrow

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4009

exchange: move _computeellipsis() from narrow
ClosedPublic

Authored by indygreg on Aug 1 2018, 1:03 PM.

Details

Reviewers
durin42
Group Reviewers
hg-reviewers
Commits
rHG7e66e7999bdd: exchange: move _computeellipsis() from narrow
rHG0f39d92b8a82: exchange: move _computeellipsis() from narrow
rHGea9834aa017a: exchange: move _computeellipsis() from narrow
Summary

This is also referenced as part of the narrow changegroup code and
therefore needs to move to core before we can integrate the narrow
changegroup code into core.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

indygreg created this revision.Aug 1 2018, 1:03 PM
durin42 accepted this revision.Aug 1 2018, 4:49 PM
This revision is now accepted and ready to land.Aug 1 2018, 4:49 PM
Closed by commit rHGea9834aa017a: exchange: move _computeellipsis() from narrow (authored by indygreg). · Explain WhyAug 1 2018, 5:25 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mhgext/narrow/narrowbundle2.py (132 lines)
Mmercurial/exchange.py (127 lines)

Diff 9701

hgext/narrow/narrowbundle2.py

# narrowbundle2.py - bundle2 extensions for narrow repository support # narrowbundle2.py - bundle2 extensions for narrow repository support
# #
# Copyright 2017 Google, Inc. # Copyright 2017 Google, Inc.
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
from __future__ import absolute_import from __future__ import absolute_import
import collections
import errno import errno
import struct import struct
from mercurial.i18n import _ from mercurial.i18n import _
from mercurial.node import ( from mercurial.node import (
bin, bin,
nullid, nullid,
nullrev,
) )
from mercurial import ( from mercurial import (
bundle2, bundle2,
changegroup, changegroup,
dagutil,
error, error,
exchange, exchange,
extensions, extensions,
narrowspec, narrowspec,
repair, repair,
util, util,
wireprototypes, wireprototypes,
) )
_MFHEADERSIZE = struct.calcsize(_ELIDEDMFHEADER) _MFHEADERSIZE = struct.calcsize(_ELIDEDMFHEADER)
# When advertising capabilities, always include narrow clone support. # When advertising capabilities, always include narrow clone support.
def getrepocaps_narrow(orig, repo, **kwargs): def getrepocaps_narrow(orig, repo, **kwargs):
caps = orig(repo, **kwargs) caps = orig(repo, **kwargs)
caps[NARROWCAP] = ['v0'] caps[NARROWCAP] = ['v0']
return caps return caps
def _computeellipsis(repo, common, heads, known, match, depth=None):
"""Compute the shape of a narrowed DAG.
Args:
repo: The repository we're transferring.
common: The roots of the DAG range we're transferring.
May be just [nullid], which means all ancestors of heads.
heads: The heads of the DAG range we're transferring.
match: The narrowmatcher that allows us to identify relevant changes.
depth: If not None, only consider nodes to be full nodes if they are at
most depth changesets away from one of heads.
Returns:
A tuple of (visitnodes, relevant_nodes, ellipsisroots) where:
visitnodes: The list of nodes (either full or ellipsis) which
need to be sent to the client.
relevant_nodes: The set of changelog nodes which change a file inside
the narrowspec. The client needs these as non-ellipsis nodes.
ellipsisroots: A dict of {rev: parents} that is used in
narrowchangegroup to produce ellipsis nodes with the
correct parents.
"""
cl = repo.changelog
mfl = repo.manifestlog
cldag = dagutil.revlogdag(cl)
# dagutil does not like nullid/nullrev
commonrevs = cldag.internalizeall(common - set([nullid])) | set([nullrev])
headsrevs = cldag.internalizeall(heads)
if depth:
revdepth = {h: 0 for h in headsrevs}
ellipsisheads = collections.defaultdict(set)
ellipsisroots = collections.defaultdict(set)
def addroot(head, curchange):
"""Add a root to an ellipsis head, splitting heads with 3 roots."""
ellipsisroots[head].add(curchange)
# Recursively split ellipsis heads with 3 roots by finding the
# roots' youngest common descendant which is an elided merge commit.
# That descendant takes 2 of the 3 roots as its own, and becomes a
# root of the head.
while len(ellipsisroots[head]) > 2:
child, roots = splithead(head)
splitroots(head, child, roots)
head = child # Recurse in case we just added a 3rd root
def splitroots(head, child, roots):
ellipsisroots[head].difference_update(roots)
ellipsisroots[head].add(child)
ellipsisroots[child].update(roots)
ellipsisroots[child].discard(child)
def splithead(head):
r1, r2, r3 = sorted(ellipsisroots[head])
for nr1, nr2 in ((r2, r3), (r1, r3), (r1, r2)):
mid = repo.revs('sort(merge() & %d::%d & %d::%d, -rev)',
nr1, head, nr2, head)
for j in mid:
if j == nr2:
return nr2, (nr1, nr2)
if j not in ellipsisroots or len(ellipsisroots[j]) < 2:
return j, (nr1, nr2)
raise error.Abort('Failed to split up ellipsis node! head: %d, '
'roots: %d %d %d' % (head, r1, r2, r3))
missing = list(cl.findmissingrevs(common=commonrevs, heads=headsrevs))
visit = reversed(missing)
relevant_nodes = set()
visitnodes = [cl.node(m) for m in missing]
required = set(headsrevs) | known
for rev in visit:
clrev = cl.changelogrevision(rev)
ps = cldag.parents(rev)
if depth is not None:
curdepth = revdepth[rev]
for p in ps:
revdepth[p] = min(curdepth + 1, revdepth.get(p, depth + 1))
needed = False
shallow_enough = depth is None or revdepth[rev] <= depth
if shallow_enough:
curmf = mfl[clrev.manifest].read()
if ps:
# We choose to not trust the changed files list in
# changesets because it's not always correct. TODO: could
# we trust it for the non-merge case?
p1mf = mfl[cl.changelogrevision(ps[0]).manifest].read()
needed = bool(curmf.diff(p1mf, match))
if not needed and len(ps) > 1:
# For merge changes, the list of changed files is not
# helpful, since we need to emit the merge if a file
# in the narrow spec has changed on either side of the
# merge. As a result, we do a manifest diff to check.
p2mf = mfl[cl.changelogrevision(ps[1]).manifest].read()
needed = bool(curmf.diff(p2mf, match))
else:
# For a root node, we need to include the node if any
# files in the node match the narrowspec.
needed = any(curmf.walk(match))
if needed:
for head in ellipsisheads[rev]:
addroot(head, rev)
for p in ps:
required.add(p)
relevant_nodes.add(cl.node(rev))
else:
if not ps:
ps = [nullrev]
if rev in required:
for head in ellipsisheads[rev]:
addroot(head, rev)
for p in ps:
ellipsisheads[p].add(rev)
else:
for p in ps:
ellipsisheads[p] |= ellipsisheads[rev]
# add common changesets as roots of their reachable ellipsis heads
for c in commonrevs:
for head in ellipsisheads[c]:
addroot(head, c)
return visitnodes, relevant_nodes, ellipsisroots
def _packellipsischangegroup(repo, common, match, relevant_nodes, def _packellipsischangegroup(repo, common, match, relevant_nodes,
ellipsisroots, visitnodes, depth, source, version): ellipsisroots, visitnodes, depth, source, version):
if version in ('01', '02'): if version in ('01', '02'):
raise error.Abort( raise error.Abort(
'ellipsis nodes require at least cg3 on client and server, ' 'ellipsis nodes require at least cg3 on client and server, '
'but negotiated version %s' % version) 'but negotiated version %s' % version)
# We wrap cg1packer.revchunk, using a side channel to pass # We wrap cg1packer.revchunk, using a side channel to pass
# relevant_nodes into that area. Then if linknode isn't in the # relevant_nodes into that area. Then if linknode isn't in the
# single node. # single node.
deadrevs = known deadrevs = known
def genkills(): def genkills():
for r in deadrevs: for r in deadrevs:
yield _KILLNODESIGNAL yield _KILLNODESIGNAL
yield repo.changelog.node(r) yield repo.changelog.node(r)
yield _DONESIGNAL yield _DONESIGNAL
bundler.newpart(_CHANGESPECPART, data=genkills()) bundler.newpart(_CHANGESPECPART, data=genkills())
newvisit, newfull, newellipsis = _computeellipsis( newvisit, newfull, newellipsis = exchange._computeellipsis(
repo, set(), common, known, newmatch) repo, set(), common, known, newmatch)
if newvisit: if newvisit:
cg = _packellipsischangegroup( cg = _packellipsischangegroup(
repo, common, newmatch, newfull, newellipsis, repo, common, newmatch, newfull, newellipsis,
newvisit, depth, source, version) newvisit, depth, source, version)
part = bundler.newpart('changegroup', data=cg) part = bundler.newpart('changegroup', data=cg)
part.addparam('version', version) part.addparam('version', version)
if 'treemanifest' in repo.requirements: if 'treemanifest' in repo.requirements:
part.addparam('treemanifest', '1') part.addparam('treemanifest', '1')
visitnodes, relevant_nodes, ellipsisroots = _computeellipsis( visitnodes, relevant_nodes, ellipsisroots = exchange._computeellipsis(
repo, common, heads, set(), newmatch, depth=depth) repo, common, heads, set(), newmatch, depth=depth)
repo.ui.debug('Found %d relevant revs\n' % len(relevant_nodes)) repo.ui.debug('Found %d relevant revs\n' % len(relevant_nodes))
if visitnodes: if visitnodes:
cg = _packellipsischangegroup( cg = _packellipsischangegroup(
repo, common, newmatch, relevant_nodes, ellipsisroots, repo, common, newmatch, relevant_nodes, ellipsisroots,
visitnodes, depth, source, version) visitnodes, depth, source, version)
part = bundler.newpart('changegroup', data=cg) part = bundler.newpart('changegroup', data=cg)

mercurial/exchange.py

import collections import collections
import hashlib import hashlib
from .i18n import _ from .i18n import _
from .node import ( from .node import (
bin, bin,
hex, hex,
nullid, nullid,
nullrev,
) )
from .thirdparty import ( from .thirdparty import (
attr, attr,
) )
from . import ( from . import (
bookmarks as bookmod, bookmarks as bookmod,
bundle2, bundle2,
changegroup, changegroup,
dagutil,
discovery, discovery,
error, error,
lock as lockmod, lock as lockmod,
logexchange, logexchange,
narrowspec, narrowspec,
obsolete, obsolete,
phases, phases,
pushkey, pushkey,
new_args = {} new_args = {}
new_args.update(kwargs) new_args.update(kwargs)
new_args['includepats'] = req_includes new_args['includepats'] = req_includes
if req_excludes: if req_excludes:
new_args['excludepats'] = req_excludes new_args['excludepats'] = req_excludes
return new_args return new_args
def _computeellipsis(repo, common, heads, known, match, depth=None):
"""Compute the shape of a narrowed DAG.
Args:
repo: The repository we're transferring.
common: The roots of the DAG range we're transferring.
May be just [nullid], which means all ancestors of heads.
heads: The heads of the DAG range we're transferring.
match: The narrowmatcher that allows us to identify relevant changes.
depth: If not None, only consider nodes to be full nodes if they are at
most depth changesets away from one of heads.
Returns:
A tuple of (visitnodes, relevant_nodes, ellipsisroots) where:
visitnodes: The list of nodes (either full or ellipsis) which
need to be sent to the client.
relevant_nodes: The set of changelog nodes which change a file inside
the narrowspec. The client needs these as non-ellipsis nodes.
ellipsisroots: A dict of {rev: parents} that is used in
narrowchangegroup to produce ellipsis nodes with the
correct parents.
"""
cl = repo.changelog
mfl = repo.manifestlog
cldag = dagutil.revlogdag(cl)
# dagutil does not like nullid/nullrev
commonrevs = cldag.internalizeall(common - set([nullid])) | set([nullrev])
headsrevs = cldag.internalizeall(heads)
if depth:
revdepth = {h: 0 for h in headsrevs}
ellipsisheads = collections.defaultdict(set)
ellipsisroots = collections.defaultdict(set)
def addroot(head, curchange):
"""Add a root to an ellipsis head, splitting heads with 3 roots."""
ellipsisroots[head].add(curchange)
# Recursively split ellipsis heads with 3 roots by finding the
# roots' youngest common descendant which is an elided merge commit.
# That descendant takes 2 of the 3 roots as its own, and becomes a
# root of the head.
while len(ellipsisroots[head]) > 2:
child, roots = splithead(head)
splitroots(head, child, roots)
head = child # Recurse in case we just added a 3rd root
def splitroots(head, child, roots):
ellipsisroots[head].difference_update(roots)
ellipsisroots[head].add(child)
ellipsisroots[child].update(roots)
ellipsisroots[child].discard(child)
def splithead(head):
r1, r2, r3 = sorted(ellipsisroots[head])
for nr1, nr2 in ((r2, r3), (r1, r3), (r1, r2)):
mid = repo.revs('sort(merge() & %d::%d & %d::%d, -rev)',
nr1, head, nr2, head)
for j in mid:
if j == nr2:
return nr2, (nr1, nr2)
if j not in ellipsisroots or len(ellipsisroots[j]) < 2:
return j, (nr1, nr2)
raise error.Abort(_('Failed to split up ellipsis node! head: %d, '
'roots: %d %d %d') % (head, r1, r2, r3))
missing = list(cl.findmissingrevs(common=commonrevs, heads=headsrevs))
visit = reversed(missing)
relevant_nodes = set()
visitnodes = [cl.node(m) for m in missing]
required = set(headsrevs) | known
for rev in visit:
clrev = cl.changelogrevision(rev)
ps = cldag.parents(rev)
if depth is not None:
curdepth = revdepth[rev]
for p in ps:
revdepth[p] = min(curdepth + 1, revdepth.get(p, depth + 1))
needed = False
shallow_enough = depth is None or revdepth[rev] <= depth
if shallow_enough:
curmf = mfl[clrev.manifest].read()
if ps:
# We choose to not trust the changed files list in
# changesets because it's not always correct. TODO: could
# we trust it for the non-merge case?
p1mf = mfl[cl.changelogrevision(ps[0]).manifest].read()
needed = bool(curmf.diff(p1mf, match))
if not needed and len(ps) > 1:
# For merge changes, the list of changed files is not
# helpful, since we need to emit the merge if a file
# in the narrow spec has changed on either side of the
# merge. As a result, we do a manifest diff to check.
p2mf = mfl[cl.changelogrevision(ps[1]).manifest].read()
needed = bool(curmf.diff(p2mf, match))
else:
# For a root node, we need to include the node if any
# files in the node match the narrowspec.
needed = any(curmf.walk(match))
if needed:
for head in ellipsisheads[rev]:
addroot(head, rev)
for p in ps:
required.add(p)
relevant_nodes.add(cl.node(rev))
else:
if not ps:
ps = [nullrev]
if rev in required:
for head in ellipsisheads[rev]:
addroot(head, rev)
for p in ps:
ellipsisheads[p].add(rev)
else:
for p in ps:
ellipsisheads[p] |= ellipsisheads[rev]
# add common changesets as roots of their reachable ellipsis heads
for c in commonrevs:
for head in ellipsisheads[c]:
addroot(head, c)
return visitnodes, relevant_nodes, ellipsisroots
def caps20to10(repo, role): def caps20to10(repo, role):
"""return a set with appropriate options to use bundle20 during getbundle""" """return a set with appropriate options to use bundle20 during getbundle"""
caps = {'HG20'} caps = {'HG20'}
capsblob = bundle2.encodecaps(bundle2.getrepocaps(repo, role=role)) capsblob = bundle2.encodecaps(bundle2.getrepocaps(repo, role=role))
caps.add('bundle2=' + urlreq.quote(capsblob)) caps.add('bundle2=' + urlreq.quote(capsblob))
return caps return caps
# List of names of steps to perform for a bundle2 for getbundle, order matters. # List of names of steps to perform for a bundle2 for getbundle, order matters.