view mercurial/node.py @ 20499:2efd608473fb

revset: optimize missing ancestor expressions

A missing ancestor expression is any expression of the form (::x - ::y) or
equivalent. Such expressions are remarkably common, and so far have involved
multiple walks down the DAG, followed by a set difference operation.

With this patch, such expressions will be transformed into uses of the fast
algorithm at ancestor.missingancestor.

For a repository with over 600,000 revisions, perfrevset for '::tip - ::-10000'
returns:

Before: ! wall 3.999575 comb 4.000000 user 3.910000 sys 0.090000 (best of 3)
After:  ! wall 0.132423 comb 0.130000 user 0.130000 sys 0.000000 (best of 75)

# node.py - basic nodeid manipulation for mercurial
#
# Copyright 2005, 2006 Matt Mackall <[e-mail]>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.

import binascii

nullrev = -1
nullid = "\0" * 20

# This ugly style has a noticeable effect in manifest parsing
hex = binascii.hexlify
bin = binascii.unhexlify

def short(node):
    return hex(node[:6])