view hgext/gpg.py @ 25647:46a96dd4d976

revset: improves time complexity of 'roots(xxx)'

The canonical way of doing 'roots(X)' is 'X - children(X)'. This is what the
implementation used to be. However, computing children is expensive because it
is unbounded. Any changesets in the repository may be a children of '0' so you
have to look at all changesets in the repository to compute children(0).
Moreover the current revsets implementation for children is not lazy, leading to
bad performance when fetching the first result.


There is a more restricted algorithm to compute roots:

    roots(X) = [r for r in X if not parents(r) & X]

This achieve the same result while only looking for parent/children relation in
the X set itself, making the algorithm 'O(len(X))' membership operation.
Another advantages is that it turns the check into a simple filter, preserving
all laziness property of the underlying revsets.

The speed is very significant and some laziness is restored.

-) revset without 'roots(...)' to compare to base line
0) before this change
1) after this change

revset #0: roots((tip~100::) - (tip~100::tip))
   plain         min           last
-) 0.001082      0.000993      0.000790
0) 0.001366      0.001385      0.001339
1) 0.001257  92% 0.001028  74% 0.000821  61%

revset #1: roots((0::) - (0::tip))
   plain         min           last
-) 0.134551      0.144682      0.068453
0) 0.161822      0.171786      0.157683
1) 0.137583  85% 0.146204  85% 0.070012  44%

revset #2: roots(tip~100:)
   plain         min           first         last
-) 0.000219      0.000225      0.000231      0.000229
0) 0.000513      0.000529      0.000507      0.000539
1) 0.000463  90% 0.000269  50% 0.000267  52% 0.000463  85%

revset #3: roots(:42)
   plain         min           first         last
-) 0.000119      0.000146      0.000146      0.000146
0) 0.000231      0.000254      0.000253      0.000260
1) 0.000216  93% 0.000186  73% 0.000184  72% 0.000244  93%

revset #4: roots(not public())
   plain         min           first
-) 0.000478      0.000502      0.000504
0) 0.000611      0.000639      0.000634
1) 0.000604      0.000560  87% 0.000558

revset #5: roots((0:tip)::)
   plain         min           max           first         last
-) 0.057795      0.004905      0.058260      0.004908      0.038812
0) 0.132845      0.118931      0.130306      0.114280      0.127742
1) 0.111659  84% 0.005023   4% 0.111658  85% 0.005022   4% 0.092490  72%

revset #6: roots(0::tip)
   plain         min           max           first         last
-) 0.032971      0.033947      0.033460      0.032350      0.033125
0) 0.083671      0.081953      0.084074      0.080364      0.086069
1) 0.074720  89% 0.035547  43% 0.077025  91% 0.033729  41% 0.083197

revset #7: 42:68 and roots(42:tip)
   plain         min           max           first         last
-) 0.006827      0.000251      0.006830      0.000254      0.006771
0) 0.000337      0.000353      0.000366      0.000350      0.000366
1) 0.000318  94% 0.000297  84% 0.000353      0.000293  83% 0.000351

revset #8: roots(0:tip)
   plain         min           max           first         last
-) 0.002119      0.000145      0.000147      0.000147      0.000147
0) 0.047441      0.040660      0.045662      0.040284      0.043435
1) 0.038057  80% 0.000187   0% 0.034919  76% 0.000186   0% 0.035097  80%

revset #0: roots(:42 + tip~42:)
   plain         min           max           first         last          sort
-) 0.000321      0.000317      0.000319      0.000308      0.000369      0.000343
0) 0.000772      0.000751      0.000811      0.000750      0.000802      0.000783
1) 0.000632  81% 0.000369  49% 0.000617  76% 0.000358  47% 0.000601  74% 0.000642  81%

# Copyright 2005, 2006 Benoit Boissinot <[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.

'''commands to sign and verify changesets'''

import os, tempfile, binascii
from mercurial import util, commands, match, cmdutil
from mercurial import node as hgnode
from mercurial.i18n import _

cmdtable = {}
command = cmdutil.command(cmdtable)
# Note for extension authors: ONLY specify testedwith = 'internal' for
# extensions which SHIP WITH MERCURIAL. Non-mainline extensions should
# be specifying the version(s) of Mercurial they are tested with, or
# leave the attribute unspecified.
testedwith = 'internal'

class gpg(object):
    def __init__(self, path, key=None):
        self.path = path
        self.key = (key and " --local-user \"%s\"" % key) or ""

    def sign(self, data):
        gpgcmd = "%s --sign --detach-sign%s" % (self.path, self.key)
        return util.filter(data, gpgcmd)

    def verify(self, data, sig):
        """ returns of the good and bad signatures"""
        sigfile = datafile = None
        try:
            # create temporary files
            fd, sigfile = tempfile.mkstemp(prefix="hg-gpg-", suffix=".sig")
            fp = os.fdopen(fd, 'wb')
            fp.write(sig)
            fp.close()
            fd, datafile = tempfile.mkstemp(prefix="hg-gpg-", suffix=".txt")
            fp = os.fdopen(fd, 'wb')
            fp.write(data)
            fp.close()
            gpgcmd = ("%s --logger-fd 1 --status-fd 1 --verify "
                      "\"%s\" \"%s\"" % (self.path, sigfile, datafile))
            ret = util.filter("", gpgcmd)
        finally:
            for f in (sigfile, datafile):
                try:
                    if f:
                        os.unlink(f)
                except OSError:
                    pass
        keys = []
        key, fingerprint = None, None
        for l in ret.splitlines():
            # see DETAILS in the gnupg documentation
            # filter the logger output
            if not l.startswith("[GNUPG:]"):
                continue
            l = l[9:]
            if l.startswith("VALIDSIG"):
                # fingerprint of the primary key
                fingerprint = l.split()[10]
            elif l.startswith("ERRSIG"):
                key = l.split(" ", 3)[:2]
                key.append("")
                fingerprint = None
            elif (l.startswith("GOODSIG") or
                  l.startswith("EXPSIG") or
                  l.startswith("EXPKEYSIG") or
                  l.startswith("BADSIG")):
                if key is not None:
                    keys.append(key + [fingerprint])
                key = l.split(" ", 2)
                fingerprint = None
        if key is not None:
            keys.append(key + [fingerprint])
        return keys

def newgpg(ui, **opts):
    """create a new gpg instance"""
    gpgpath = ui.config("gpg", "cmd", "gpg")
    gpgkey = opts.get('key')
    if not gpgkey:
        gpgkey = ui.config("gpg", "key", None)
    return gpg(gpgpath, gpgkey)

def sigwalk(repo):
    """
    walk over every sigs, yields a couple
    ((node, version, sig), (filename, linenumber))
    """
    def parsefile(fileiter, context):
        ln = 1
        for l in fileiter:
            if not l:
                continue
            yield (l.split(" ", 2), (context, ln))
            ln += 1

    # read the heads
    fl = repo.file(".hgsigs")
    for r in reversed(fl.heads()):
        fn = ".hgsigs|%s" % hgnode.short(r)
        for item in parsefile(fl.read(r).splitlines(), fn):
            yield item
    try:
        # read local signatures
        fn = "localsigs"
        for item in parsefile(repo.vfs(fn), fn):
            yield item
    except IOError:
        pass

def getkeys(ui, repo, mygpg, sigdata, context):
    """get the keys who signed a data"""
    fn, ln = context
    node, version, sig = sigdata
    prefix = "%s:%d" % (fn, ln)
    node = hgnode.bin(node)

    data = node2txt(repo, node, version)
    sig = binascii.a2b_base64(sig)
    keys = mygpg.verify(data, sig)

    validkeys = []
    # warn for expired key and/or sigs
    for key in keys:
        if key[0] == "ERRSIG":
            ui.write(_("%s Unknown key ID \"%s\"\n")
                     % (prefix, shortkey(ui, key[1][:15])))
            continue
        if key[0] == "BADSIG":
            ui.write(_("%s Bad signature from \"%s\"\n") % (prefix, key[2]))
            continue
        if key[0] == "EXPSIG":
            ui.write(_("%s Note: Signature has expired"
                       " (signed by: \"%s\")\n") % (prefix, key[2]))
        elif key[0] == "EXPKEYSIG":
            ui.write(_("%s Note: This key has expired"
                       " (signed by: \"%s\")\n") % (prefix, key[2]))
        validkeys.append((key[1], key[2], key[3]))
    return validkeys

@command("sigs", [], _('hg sigs'))
def sigs(ui, repo):
    """list signed changesets"""
    mygpg = newgpg(ui)
    revs = {}

    for data, context in sigwalk(repo):
        node, version, sig = data
        fn, ln = context
        try:
            n = repo.lookup(node)
        except KeyError:
            ui.warn(_("%s:%d node does not exist\n") % (fn, ln))
            continue
        r = repo.changelog.rev(n)
        keys = getkeys(ui, repo, mygpg, data, context)
        if not keys:
            continue
        revs.setdefault(r, [])
        revs[r].extend(keys)
    for rev in sorted(revs, reverse=True):
        for k in revs[rev]:
            r = "%5d:%s" % (rev, hgnode.hex(repo.changelog.node(rev)))
            ui.write("%-30s %s\n" % (keystr(ui, k), r))

@command("sigcheck", [], _('hg sigcheck REV'))
def check(ui, repo, rev):
    """verify all the signatures there may be for a particular revision"""
    mygpg = newgpg(ui)
    rev = repo.lookup(rev)
    hexrev = hgnode.hex(rev)
    keys = []

    for data, context in sigwalk(repo):
        node, version, sig = data
        if node == hexrev:
            k = getkeys(ui, repo, mygpg, data, context)
            if k:
                keys.extend(k)

    if not keys:
        ui.write(_("no valid signature for %s\n") % hgnode.short(rev))
        return

    # print summary
    ui.write("%s is signed by:\n" % hgnode.short(rev))
    for key in keys:
        ui.write(" %s\n" % keystr(ui, key))

def keystr(ui, key):
    """associate a string to a key (username, comment)"""
    keyid, user, fingerprint = key
    comment = ui.config("gpg", fingerprint, None)
    if comment:
        return "%s (%s)" % (user, comment)
    else:
        return user

@command("sign",
         [('l', 'local', None, _('make the signature local')),
          ('f', 'force', None, _('sign even if the sigfile is modified')),
          ('', 'no-commit', None, _('do not commit the sigfile after signing')),
          ('k', 'key', '',
           _('the key id to sign with'), _('ID')),
          ('m', 'message', '',
           _('use text as commit message'), _('TEXT')),
          ('e', 'edit', False, _('invoke editor on commit messages')),
         ] + commands.commitopts2,
         _('hg sign [OPTION]... [REV]...'))
def sign(ui, repo, *revs, **opts):
    """add a signature for the current or given revision

    If no revision is given, the parent of the working directory is used,
    or tip if no revision is checked out.

    See :hg:`help dates` for a list of formats valid for -d/--date.
    """

    mygpg = newgpg(ui, **opts)
    sigver = "0"
    sigmessage = ""

    date = opts.get('date')
    if date:
        opts['date'] = util.parsedate(date)

    if revs:
        nodes = [repo.lookup(n) for n in revs]
    else:
        nodes = [node for node in repo.dirstate.parents()
                 if node != hgnode.nullid]
        if len(nodes) > 1:
            raise util.Abort(_('uncommitted merge - please provide a '
                               'specific revision'))
        if not nodes:
            nodes = [repo.changelog.tip()]

    for n in nodes:
        hexnode = hgnode.hex(n)
        ui.write(_("signing %d:%s\n") % (repo.changelog.rev(n),
                                         hgnode.short(n)))
        # build data
        data = node2txt(repo, n, sigver)
        sig = mygpg.sign(data)
        if not sig:
            raise util.Abort(_("error while signing"))
        sig = binascii.b2a_base64(sig)
        sig = sig.replace("\n", "")
        sigmessage += "%s %s %s\n" % (hexnode, sigver, sig)

    # write it
    if opts['local']:
        repo.vfs.append("localsigs", sigmessage)
        return

    if not opts["force"]:
        msigs = match.exact(repo.root, '', ['.hgsigs'])
        if any(repo.status(match=msigs, unknown=True, ignored=True)):
            raise util.Abort(_("working copy of .hgsigs is changed "),
                             hint=_("please commit .hgsigs manually"))

    sigsfile = repo.wfile(".hgsigs", "ab")
    sigsfile.write(sigmessage)
    sigsfile.close()

    if '.hgsigs' not in repo.dirstate:
        repo[None].add([".hgsigs"])

    if opts["no_commit"]:
        return

    message = opts['message']
    if not message:
        # we don't translate commit messages
        message = "\n".join(["Added signature for changeset %s"
                             % hgnode.short(n)
                             for n in nodes])
    try:
        editor = cmdutil.getcommiteditor(editform='gpg.sign', **opts)
        repo.commit(message, opts['user'], opts['date'], match=msigs,
                    editor=editor)
    except ValueError, inst:
        raise util.Abort(str(inst))

def shortkey(ui, key):
    if len(key) != 16:
        ui.debug("key ID \"%s\" format error\n" % key)
        return key

    return key[-8:]

def node2txt(repo, node, ver):
    """map a manifest into some text"""
    if ver == "0":
        return "%s\n" % hgnode.hex(node)
    else:
        raise util.Abort(_("unknown signature version"))