hgext3rd/evolve/utility.py
author Pierre-Yves David <pierre-yves.david@ens-lyon.org>
Sat, 11 Mar 2017 10:26:30 -0800
changeset 2087 0c2371542687
parent 2086 28241509ff6f
child 2088 9f7ce656bfdf
permissions -rw-r--r--
depth: update depth to code to reuse ancestors depth Computing the depth of all N revs is no longer 'O(N**2)'
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2047
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     1
# Various utility function for the evolve extension
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     2
#
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     3
# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org>
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     4
#
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
2086
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
     7
from mercurial import node
2047
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     8
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
     9
def obsexcmsg(ui, message, important=False):
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    10
    verbose = ui.configbool('experimental', 'verbose-obsolescence-exchange',
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    11
                            False)
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    12
    if verbose:
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    13
        message = 'OBSEXC: ' + message
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    14
    if important or verbose:
ce39d0f9976d serveronly: give the sub extension a way to access to the 'evolve' module
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents:
diff changeset
    15
        ui.status(message)
2054
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    16
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    17
def obsexcprg(ui, *args, **kwargs):
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    18
    topic = 'obsmarkers exchange'
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    19
    if ui.configbool('experimental', 'verbose-obsolescence-exchange', False):
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    20
        topic = 'OBSEXC'
f9d65d24b9f9 discovery: split discovery related code in 'obsdiscovery'
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2047
diff changeset
    21
    ui.progress(topic, *args, **kwargs)
2086
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    22
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    23
_depthcache = {}
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    24
def depth(repo, rev):
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    25
    cl = repo.changelog
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    26
    n = cl.node(rev)
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    27
    revdepth = _depthcache.get(n, None)
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    28
    if revdepth is None:
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    29
        p1, p2 = cl.parentrevs(rev)
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    30
        if p1 == node.nullrev:
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    31
            revdepth = 1
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    32
        elif p2 == node.nullrev:
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    33
            revdepth = depth(repo, p1) + 1
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    34
        else:
2087
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    35
            ancs = cl.commonancestorsheads(cl.node(p1), cl.node(p2))
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    36
            depth_p1 = depth(repo, p1)
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    37
            depth_p2 = depth(repo, p2)
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    38
            if not ancs:
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    39
                revdepth = depth_p1 + depth_p2 + 1
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    40
            elif len(ancs) == 1:
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    41
                anc = cl.rev(ancs[0])
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    42
                revdepth = depth_anc = depth(repo, anc)
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    43
                revdepth += depth_p1 - depth_anc
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    44
                revdepth += depth_p2 - depth_anc
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    45
                revdepth += 1
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    46
            else:
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    47
                # multiple ancestors, we pick the highest and search all missing bits
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    48
                anc = max(cl.rev(a) for a in ancs)
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    49
                revdepth = depth(repo, anc)
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    50
                revdepth += len(repo.revs('only(%d, %d)', rev, anc))
2086
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    51
        _depthcache[n] = revdepth
2087
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    52
    # actual_depth = len(list(cl.ancestors([rev], inclusive=True)))
0c2371542687 depth: update depth to code to reuse ancestors depth
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2086
diff changeset
    53
    # assert revdepth == actual_depth, (rev, revdepth, actual_depth)
2086
28241509ff6f obsdiscovery: extract a smarted depth in utility
Pierre-Yves David <pierre-yves.david@ens-lyon.org>
parents: 2054
diff changeset
    54
    return revdepth