10 import collections

    18     nullrev,

    23     dagutil,

    54 

    55 def _computeellipsis(repo, common, heads, known, match, depth=None):

    56     """Compute the shape of a narrowed DAG.

    57 

    58     Args:

    59       repo: The repository we're transferring.

    60       common: The roots of the DAG range we're transferring.

    61               May be just [nullid], which means all ancestors of heads.

    62       heads: The heads of the DAG range we're transferring.

    63       match: The narrowmatcher that allows us to identify relevant changes.

    64       depth: If not None, only consider nodes to be full nodes if they are at

    65              most depth changesets away from one of heads.

    66 

    67     Returns:

    68       A tuple of (visitnodes, relevant_nodes, ellipsisroots) where:

    69 

    70         visitnodes: The list of nodes (either full or ellipsis) which

    71                     need to be sent to the client.

    72         relevant_nodes: The set of changelog nodes which change a file inside

    73                  the narrowspec. The client needs these as non-ellipsis nodes.

    74         ellipsisroots: A dict of {rev: parents} that is used in

    75                        narrowchangegroup to produce ellipsis nodes with the

    76                        correct parents.

    77     """

    78     cl = repo.changelog

    79     mfl = repo.manifestlog

    80 

    81     cldag = dagutil.revlogdag(cl)

    82     # dagutil does not like nullid/nullrev

    83     commonrevs = cldag.internalizeall(common - set([nullid])) | set([nullrev])

    84     headsrevs = cldag.internalizeall(heads)

    85     if depth:

    86         revdepth = {h: 0 for h in headsrevs}

    87 

    88     ellipsisheads = collections.defaultdict(set)

    89     ellipsisroots = collections.defaultdict(set)

    90 

    91     def addroot(head, curchange):

    92         """Add a root to an ellipsis head, splitting heads with 3 roots."""

    93         ellipsisroots[head].add(curchange)

    94         # Recursively split ellipsis heads with 3 roots by finding the

    95         # roots' youngest common descendant which is an elided merge commit.

    96         # That descendant takes 2 of the 3 roots as its own, and becomes a

    97         # root of the head.

    98         while len(ellipsisroots[head]) > 2:

    99             child, roots = splithead(head)

   100             splitroots(head, child, roots)

   101             head = child  # Recurse in case we just added a 3rd root

   102 

   103     def splitroots(head, child, roots):

   104         ellipsisroots[head].difference_update(roots)

   105         ellipsisroots[head].add(child)

   106         ellipsisroots[child].update(roots)

   107         ellipsisroots[child].discard(child)

   108 

   109     def splithead(head):

   110         r1, r2, r3 = sorted(ellipsisroots[head])

   111         for nr1, nr2 in ((r2, r3), (r1, r3), (r1, r2)):

   112             mid = repo.revs('sort(merge() & %d::%d & %d::%d, -rev)',

   113                             nr1, head, nr2, head)

   114             for j in mid:

   115                 if j == nr2:

   116                     return nr2, (nr1, nr2)

   117                 if j not in ellipsisroots or len(ellipsisroots[j]) < 2:

   118                     return j, (nr1, nr2)

   119         raise error.Abort('Failed to split up ellipsis node! head: %d, '

   120                           'roots: %d %d %d' % (head, r1, r2, r3))

   121 

   122     missing = list(cl.findmissingrevs(common=commonrevs, heads=headsrevs))

   123     visit = reversed(missing)

   124     relevant_nodes = set()

   125     visitnodes = [cl.node(m) for m in missing]

   126     required = set(headsrevs) | known

   127     for rev in visit:

   128         clrev = cl.changelogrevision(rev)

   129         ps = cldag.parents(rev)

   130         if depth is not None:

   131             curdepth = revdepth[rev]

   132             for p in ps:

   133                 revdepth[p] = min(curdepth + 1, revdepth.get(p, depth + 1))

   134         needed = False

   135         shallow_enough = depth is None or revdepth[rev] <= depth

   136         if shallow_enough:

   137             curmf = mfl[clrev.manifest].read()

   138             if ps:

   139                 # We choose to not trust the changed files list in

   140                 # changesets because it's not always correct. TODO: could

   141                 # we trust it for the non-merge case?

   142                 p1mf = mfl[cl.changelogrevision(ps[0]).manifest].read()

   143                 needed = bool(curmf.diff(p1mf, match))

   144                 if not needed and len(ps) > 1:

   145                     # For merge changes, the list of changed files is not

   146                     # helpful, since we need to emit the merge if a file

   147                     # in the narrow spec has changed on either side of the

   148                     # merge. As a result, we do a manifest diff to check.

   149                     p2mf = mfl[cl.changelogrevision(ps[1]).manifest].read()

   150                     needed = bool(curmf.diff(p2mf, match))

   151             else:

   152                 # For a root node, we need to include the node if any

   153                 # files in the node match the narrowspec.

   154                 needed = any(curmf.walk(match))

   155 

   156         if needed:

   157             for head in ellipsisheads[rev]:

   158                 addroot(head, rev)

   159             for p in ps:

   160                 required.add(p)

   161             relevant_nodes.add(cl.node(rev))

   162         else:

   163             if not ps:

   164                 ps = [nullrev]

   165             if rev in required:

   166                 for head in ellipsisheads[rev]:

   167                     addroot(head, rev)

   168                 for p in ps:

   169                     ellipsisheads[p].add(rev)

   170             else:

   171                 for p in ps:

   172                     ellipsisheads[p] |= ellipsisheads[rev]

   173 

   174     # add common changesets as roots of their reachable ellipsis heads

   175     for c in commonrevs:

   176         for head in ellipsisheads[c]:

   177             addroot(head, c)

   178     return visitnodes, relevant_nodes, ellipsisroots