#!/usr/bin/python3
# -*- coding: utf-8 -*-
# Copyright (C) 2018 SUSE LLC
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
# USA.
import argparse
import bisect
import collections
import dbm
import functools
import operator
import os
import os.path
import pprint
import re
import shelve
import subprocess
import sys
import types
import pygit2_wrapper as pygit2
class GSException(BaseException):
pass
class GSError(GSException):
pass
class GSKeyError(GSException):
pass
class GSNotFound(GSException):
pass
class RepoURL(object):
k_org_canon_prefix = "git://git.kernel.org/pub/scm/linux/kernel/git/"
proto_match = re.compile("(git|https?)://")
ext = ".git"
def __init__(self, url):
if url is None or url == repr(None):
self.url = None
return
k_org_prefixes = [
"http://git.kernel.org/pub/scm/linux/kernel/git/",
"https://git.kernel.org/pub/scm/linux/kernel/git/",
"ssh://git@gitolite.kernel.org/pub/scm/linux/kernel/git/",
"https://kernel.googlesource.com/pub/scm/linux/kernel/git/",
]
for prefix in k_org_prefixes:
if url.startswith(prefix):
url = url.replace(prefix, self.k_org_canon_prefix)
break
if not self.proto_match.match(url):
url = self.k_org_canon_prefix + url
if not url.endswith(self.ext):
url = url + self.ext
# an undocumented alias
if url == "git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git":
url = "git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git"
self.url = url
def _is_valid_operand(self, other):
return hasattr(other, "url")
def __eq__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
return self.url == other.url
def __ne__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
return self.url != other.url
def __hash__(self):
return hash(self.url)
def __repr__(self):
return "%s" % (self.url,)
def __str__(self):
url = self.url
if url is None:
url = ""
elif url.startswith(self.k_org_canon_prefix) and url.endswith(self.ext):
url = url[len(self.k_org_canon_prefix):-1 * len(self.ext)]
return url
@functools.total_ordering
class Head(object):
def __init__(self, repo_url, rev="master"):
self.repo_url = repo_url
self.rev = rev
def _is_valid_operand(self, other):
return hasattr(other, "repo_url") and hasattr(other, "rev")
def _get_index(self):
"""
A head with no url is considered out of tree. Any other head with a
url is upstream of it.
"""
if self.repo_url == RepoURL(None):
return len(remotes)
else:
return remote_index[self]
def __eq__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
return (self.repo_url == other.repo_url and self.rev == other.rev)
def __lt__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
return self._get_index() < other._get_index()
def __hash__(self):
return hash((self.repo_url, self.rev,))
def __repr__(self):
return "%s %s" % (repr(self.repo_url), self.rev,)
def __str__(self):
url = str(self.repo_url)
if self.rev == "master":
return url
else:
result = "%s %s" % (url, self.rev,)
return result.strip()
# a list of each remote head which is indexed by this script
# If the working repository is a clone of linux.git (it fetches from mainline,
# the first remote) and a commit does not appear in one of these remotes, it is
# considered "not upstream" and cannot be sorted.
# Repositories that come first in the list should be pulling/merging from
# repositories lower down in the list. Said differently, commits should trickle
# up from repositories at the end of the list to repositories higher up. For
# example, network commits usually follow "net-next" -> "net" -> "linux.git".
#
# linux-next is not a good reference because it gets rebased. If a commit is in
# linux-next, it comes from some other tree. Please tag the patch accordingly.
#
# Head(RepoURL(remote url), remote branch name)[]
# Note that "remote url" can be abbreviated if it starts with one of the usual
# kernel.org prefixes and "remote branch name" can be omitted if it is "master".
remotes = (
Head(RepoURL("torvalds/linux.git")),
Head(RepoURL("netdev/net.git")),
Head(RepoURL("davem/net.git")),
Head(RepoURL("netdev/net-next.git")),
Head(RepoURL("davem/net-next.git")),
Head(RepoURL("rdma/rdma.git"), "for-rc"),
Head(RepoURL("rdma/rdma.git"), "for-next"),
Head(RepoURL("dledford/rdma.git"), "k.o/for-next"),
Head(RepoURL("jejb/scsi.git"), "for-next"),
Head(RepoURL("bp/bp.git"), "for-next"),
Head(RepoURL("tiwai/sound.git")),
Head(RepoURL("git://linuxtv.org/media_tree.git")),
Head(RepoURL("powerpc/linux.git"), "next"),
Head(RepoURL("powerpc/linux.git"), "fixes"),
Head(RepoURL("tip/tip.git")),
Head(RepoURL("shli/md.git"), "for-next"),
Head(RepoURL("dhowells/linux-fs.git"), "keys-uefi"),
Head(RepoURL("tytso/ext4.git"), "dev"),
Head(RepoURL("s390/linux.git"), "fixes"),
Head(RepoURL("https://github.com/kdave/btrfs-devel.git"), "misc-next"),
Head(RepoURL("git://people.freedesktop.org/~airlied/linux"), "drm-next"),
Head(RepoURL("git://anongit.freedesktop.org/drm/drm-misc"), "drm-misc-next"),
Head(RepoURL("gregkh/tty.git"), "tty-next"),
Head(RepoURL("jj/linux-apparmor.git"), "apparmor-next"),
Head(RepoURL("pablo/nf.git")),
Head(RepoURL("pablo/nf-next.git")),
Head(RepoURL("horms/ipvs.git")),
Head(RepoURL("horms/ipvs-next.git")),
Head(RepoURL("klassert/ipsec.git")),
Head(RepoURL("klassert/ipsec-next.git")),
Head(RepoURL("kvalo/wireless-drivers-next.git")),
Head(RepoURL("mkp/scsi.git"), "queue"),
Head(RepoURL("mkp/scsi.git"), "fixes"),
Head(RepoURL("git://git.kernel.dk/linux-block.git"), "for-next"),
Head(RepoURL("git://git.kernel.org/pub/scm/virt/kvm/kvm.git"), "queue"),
Head(RepoURL("git://git.infradead.org/nvme.git"), "nvme-5.15"),
Head(RepoURL("dhowells/linux-fs.git")),
Head(RepoURL("herbert/cryptodev-2.6.git")),
Head(RepoURL("helgaas/pci.git"), "next"),
Head(RepoURL("viro/vfs.git"), "for-linus"),
Head(RepoURL("viro/vfs.git"), "fixes"),
Head(RepoURL("jeyu/linux.git"), "modules-next"),
Head(RepoURL("joro/iommu.git"), "next"),
Head(RepoURL("nvdimm/nvdimm.git"), "libnvdimm-for-next"),
Head(RepoURL("nvdimm/nvdimm.git"), "libnvdimm-fixes"),
Head(RepoURL("djbw/nvdimm.git"), "libnvdimm-pending"),
Head(RepoURL("git://git.linux-nfs.org/projects/anna/linux-nfs.git"), "linux-next"),
Head(RepoURL("acme/linux.git"), "perf/core"),
Head(RepoURL("will/linux.git"), "for-joerg/arm-smmu/updates"),
Head(RepoURL("herbert/crypto-2.6.git"), "master"),
Head(RepoURL("rafael/linux-pm.git")),
Head(RepoURL("git://git.linux-nfs.org/~bfields/linux.git"), "nfsd-next"),
Head(RepoURL("vkoul/soundwire.git"),"fixes"),
Head(RepoURL("vkoul/soundwire.git"),"next"),
Head(RepoURL("arm64/linux.git"), "for-next/core"),
Head(RepoURL("robh/linux.git"), "for-next"),
Head(RepoURL("git://git.infradead.org/users/hch/dma-mapping.git"), "for-next"),
Head(RepoURL("thermal/linux.git"), "thermal/linux-next"),
Head(RepoURL("git://github.com/cminyard/linux-ipmi.git"), "for-next"),
Head(RepoURL("ras/ras.git"), "edac-for-next"),
Head(RepoURL("linusw/linux-pinctrl.git"), "for-next"),
Head(RepoURL("efi/efi.git"), "next"),
Head(RepoURL("ulfh/mmc.git"), "next"),
Head(RepoURL("masahiroy/linux-kbuild.git"), "for-next"),
Head(RepoURL("bluetooth/bluetooth-next.git")),
Head(RepoURL("clk/linux.git"), "clk-next"),
Head(RepoURL("git://github.com/ceph/ceph-client"), "testing"),
Head(RepoURL("bpf/bpf.git")),
)
remote_index = dict(zip(remotes, list(range(len(remotes)))))
oot = Head(RepoURL(None), "out-of-tree patches")
def get_heads(repo):
"""
Returns
repo_heads[Head]
sha1
"""
result = collections.OrderedDict()
repo_remotes = collections.OrderedDict(
((RepoURL(remote.url), remote,) for remote in repo.remotes))
for head in remotes:
if head in result:
raise GSException("head \"%s\" is not unique." % (head,))
try:
remote = repo_remotes[head.repo_url]
except KeyError:
continue
lhs = "refs/heads/%s" % (head.rev,)
rhs = None
nb = len(remote.fetch_refspecs)
if nb == 0:
# `git clone --bare` case
rhs = lhs
else:
for i in range(nb):
r = remote.get_refspec(i)
if r.src_matches(lhs):
rhs = r.transform(lhs)
break
if rhs is None:
raise GSError("No matching fetch refspec for head \"%s\"." %
(head,))
try:
commit = repo.revparse_single(rhs)
except KeyError:
raise GSError("Could not read revision \"%s\". Perhaps you need "
"to fetch from remote \"%s\"" % (rhs, remote.name,))
result[head] = str(commit.id)
if len(result) == 0 or list(result.keys())[0] != remotes[0]:
# According to the urls in remotes, this is not a clone of linux.git
# Sort according to commits reachable from the current head
result = collections.OrderedDict(
[(Head(RepoURL(None), "HEAD"),
str(repo.revparse_single("HEAD").id),)])
return result
def get_history(repo, repo_heads):
"""
Returns
history[Head][commit hash represented as string of 40 characters]
index, an ordinal number such that
commit a is an ancestor of commit b -> index(a) < index(b)
"""
processed = []
history = collections.OrderedDict()
args = ["git", "log", "--topo-order", "--pretty=tformat:%H"]
for head, rev in repo_heads.items():
sp = subprocess.Popen(args + processed + [rev],
cwd=repo.path,
env={},
stdout=subprocess.PIPE,
stderr=subprocess.STDOUT)
result = {}
for l in sp.stdout:
result[l.decode().strip()] = len(result)
# reverse indexes
history[head] = {commit : len(result) - val for commit, val in
result.items()}
sp.communicate()
if sp.returncode != 0:
raise GSError("git log exited with an error:\n" +
"\n".join(history[head]))
processed.append("^%s" % (rev,))
return history
class CException(BaseException):
pass
class CError(CException):
pass
class CNeedsRebuild(CException):
pass
class CAbsent(CNeedsRebuild):
pass
class CKeyError(CNeedsRebuild):
pass
class CUnsupported(CNeedsRebuild):
pass
class CInconsistent(CNeedsRebuild):
pass
class Cache(object):
"""
cache
version
history[]
(url, rev, sha1,
history[commit hash represented as string of 40 characters]
index (as described in get_history())
,)
The cache is stored using basic types.
"""
version = 3
def __init__(self, write_enable=False):
self.write_enable = write_enable
self.closed = True
try:
cache_dir = os.environ["XDG_CACHE_HOME"]
except KeyError:
cache_dir = os.path.expanduser("~/.cache")
cache_path = os.path.join(cache_dir, "git-sort")
try:
os.stat(cache_path)
except OSError as e:
if e.errno == 2:
if write_enable:
if not os.path.isdir(cache_dir):
try:
os.makedirs(cache_dir)
except OSError as err:
raise CError("Could not create cache directory:\n" +
str(err))
else:
raise CAbsent
else:
raise
if write_enable:
# In case there is already a database file of an unsupported format,
# one would hope that with flag="n" a new database would be created
# to overwrite the current one. Alas, that is not the case... :'(
try:
os.unlink(cache_path)
except OSError as e:
if e.errno != 2:
raise
flag_map = {False : "r", True : "n"}
try:
self.cache = shelve.open(cache_path, flag=flag_map[write_enable])
except dbm.error:
raise CUnsupported
self.closed = False
if write_enable:
self.cache["version"] = Cache.version
def __del__(self):
self.close()
def __enter__(self):
return self
def __exit__(self, *args):
self.close()
def close(self):
if not self.closed:
self.cache.close()
self.closed = True
def __getitem__(self, key):
"""
Supported keys:
"version"
int
"history"
OrderedDict((Head, sha1) : history)
"""
if self.closed:
raise ValueError
try:
version = self.cache["version"]
except KeyError:
key_error = True
except ValueError as err:
raise CUnsupported(str(err))
else:
key_error = False
if key == "version":
if key_error:
raise CKeyError
else:
return version
elif key == "history":
if key_error or version != Cache.version:
raise CUnsupported
try:
cache_history = self.cache["history"]
except KeyError:
raise CInconsistent
# This detailed check may be needed if an older git-sort (which
# didn't set a cache version) modified the cache.
if (not isinstance(cache_history, list) or
len(cache_history) < 1 or
len(cache_history[0]) != 4 or
not isinstance(cache_history[0][3], dict)):
raise CInconsistent
return collections.OrderedDict([
(
(Head(RepoURL(e[0]), e[1]), e[2],),
e[3],
) for e in cache_history])
else:
raise KeyError
def __setitem__(self, key, value):
"""
Supported keys:
"history"
OrderedDict((Head, sha1) : history)
"""
if self.closed or not self.write_enable:
raise ValueError
if key == "history":
self.cache["history"] = [(
repr(desc[0].repo_url), desc[0].rev, desc[1], log,
) for desc, log in value.items()]
else:
raise KeyError
@functools.total_ordering
class IndexedCommit(object):
def __init__(self, head, index):
self.head = head
self.index = index
def _is_valid_operand(self, other):
return hasattr(other, "head") and hasattr(other, "index")
def __eq__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
return (self.head == other.head and self.index == other.index)
def __lt__(self, other):
if not self._is_valid_operand(other):
return NotImplemented
if self.head == other.head:
return self.index < other.index
else:
return self.head < other.head
def __hash__(self):
return hash((self.head, self.index,))
def __repr__(self):
return "%s %d" % (repr(self.head), self.index,)
class SortIndex(object):
version_match = re.compile("refs/tags/v(2\.6\.\d+|\d\.\d+)(-rc\d+)?$")
def __init__(self, repo):
self.repo = repo
needs_rebuild = False
try:
with Cache() as cache:
try:
history = cache["history"]
except CNeedsRebuild:
needs_rebuild = True
except CNeedsRebuild:
needs_rebuild = True
except CError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
try:
repo_heads = get_heads(repo)
except GSError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
if needs_rebuild or list(history.keys()) != list(repo_heads.items()):
try:
history = get_history(repo, repo_heads)
except GSError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
try:
with Cache(write_enable=True) as cache:
cache["history"] = collections.OrderedDict(
[((head, repo_heads[head],), log,)
for head, log in history.items()])
except CError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
self.history = history
else:
# no more need for the head sha1
self.history = collections.OrderedDict(
[(key[0], log,) for key, log in history.items()])
self.version_indexes = None
self.repo_heads = repo_heads
def lookup(self, commit):
for head, log in self.history.items():
try:
index = log[commit]
except KeyError:
continue
else:
return IndexedCommit(head, index)
raise GSKeyError
def describe(self, index):
"""
index must come from the mainline head (remotes[0]).
"""
if self.version_indexes is None:
history = self.history[remotes[0]]
# Remove "refs/tags/"
# Mainline release tags are annotated tag objects attached to a
# commit object; do not consider other kinds of tags.
objects = [(obj_tag.get_object(), tag,)
for obj_tag, tag in [
(self.repo.revparse_single(tag), tag[10:],)
for tag in self.repo.listall_references()
if self.version_match.match(tag)
] if obj_tag.type == pygit2.GIT_OBJ_TAG]
revs = [(history[str(obj.id)], tag,)
for obj, tag in objects
if obj.type == pygit2.GIT_OBJ_COMMIT]
revs.sort(key=operator.itemgetter(0))
self.version_indexes = list(zip(*revs))
if not self.version_indexes:
raise GSError("Cannot describe commit, did not find any mainline "
"release tags in repository.")
indexes, tags = self.version_indexes
i = bisect.bisect_left(indexes, index)
if i == len(tags):
# not yet part of a tagged release
m = re.search("v([0-9]+)\.([0-9]+)(|-rc([0-9]+))$", tags[-1])
if m:
# Post-release commit with no rc, it'll be rc1
if m.group(3) == "":
nexttag = "v%s.%d-rc1" % (m.group(1), int(m.group(2)) + 1)
else:
nexttag = "v%s.%d or v%s.%s-rc%d (next release)" % \
(m.group(1), int(m.group(2)), m.group(1),
m.group(2), int(m.group(4)) + 1)
return nexttag
else:
return tags[i]
if __name__ == "__main__":
parser = argparse.ArgumentParser(
description="Sort input lines according to the upstream order of "
"commits that each line represents, with the first word on the line "
"taken to be a commit id.")
parser.add_argument("-d", "--dump-heads", action="store_true",
help="Print the branch heads used for sorting "
"(debugging).")
args = parser.parse_args()
try:
path = os.environ["GIT_DIR"]
except KeyError:
try:
# depending on the pygit2 version, discover_repository() will either
# raise KeyError or return None if a repository is not found.
path = pygit2.discover_repository(os.getcwd())
except KeyError:
path = None
if path is None:
print("Error: Not a git repository", file=sys.stderr)
sys.exit(1)
repo = pygit2.Repository(path)
if args.dump_heads:
needs_rebuild = False
try:
with Cache() as cache:
try:
print("Cached heads (version %d):" % cache["version"])
except CKeyError:
print("No usable cache")
needs_rebuild = True
else:
try:
history = cache["history"]
except CUnsupported:
print("Unsupported cache version")
needs_rebuild = True
except CInconsistent:
print("Inconsistent cache content")
needs_rebuild = True
else:
pprint.pprint(list(history.keys()))
except CAbsent:
print("No usable cache")
needs_rebuild = True
except CNeedsRebuild:
needs_rebuild = True
except CError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
try:
repo_heads = get_heads(repo)
except GSError as err:
print("Error: %s" % (err,), file=sys.stderr)
sys.exit(1)
if not needs_rebuild and list(history.keys()) != list(repo_heads.items()):
needs_rebuild = True
print("Current heads (version %d):" % Cache.version)
pprint.pprint(list(repo_heads.items()))
if needs_rebuild:
action = "Will"
else:
action = "Will not"
print("%s rebuild history" % (action,))
sys.exit(0)
index = SortIndex(repo)
dest = {}
oot = []
num = 0
for line in sys.stdin.readlines():
num = num + 1
tokens = line.strip().split(None, 1)
if not tokens:
continue
try:
commit = repo.revparse_single(tokens[0])
except ValueError:
print("Error: did not find a commit hash on line %d:\n%s" %
(num, line.strip(),), file=sys.stderr)
sys.exit(1)
except KeyError:
print("Error: commit hash on line %d not found in the repository:\n%s" %
(num, line.strip(),), file=sys.stderr)
sys.exit(1)
h = str(commit.id)
if h in dest:
dest[h][1].append(line)
else:
try:
ic = index.lookup(h)
except GSKeyError:
oot.append(line)
else:
dest[h] = (ic, [line],)
print("".join([line
for ic, lines in sorted(dest.values(),
key=operator.itemgetter(0))
for line in lines
]), end="")
if oot:
print("Error: the following entries were not found in the indexed heads:",
file=sys.stderr)
print("".join(oot), end="")
sys.exit(1)