~wgrant/bzr-git/dulwich-0.9.6

# Copyright (C) 2009-2012 Jelmer Vernooij <jelmer@samba.org>

# Copyright (C) 2012 Canonical Ltd

#

# 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

"""Map from Git sha's to Bazaar objects."""

from __future__ import absolute_import

from dulwich.objects import (

    Blob,

    Commit,

    Tree,

    sha_to_hex,

    ZERO_SHA,

    )

from dulwich.object_store import (

    BaseObjectStore,

    )

from bzrlib import (

    errors,

    lru_cache,

    trace,

    ui,

    urlutils,

    )

from bzrlib.lock import LogicalLockResult

from bzrlib.revision import (

    NULL_REVISION,

    )

from bzrlib.testament import(

    StrictTestament3,

    )

from bzrlib.plugins.git.cache import (

    from_repository as cache_from_repository,

    )

from bzrlib.plugins.git.mapping import (

    default_mapping,

    directory_to_tree,

    extract_unusual_modes,

    mapping_registry,

    symlink_to_blob,

    )

from bzrlib.plugins.git.unpeel_map import (

    UnpeelMap,

    )

import posixpath

import stat

def get_object_store(repo, mapping=None):

    git = getattr(repo, "_git", None)

    if git is not None:

        git.object_store.unlock = lambda: None

        git.object_store.lock_read = lambda: LogicalLockResult(lambda: None)

        git.object_store.lock_write = lambda: LogicalLockResult(lambda: None)

        return git.object_store

    return BazaarObjectStore(repo, mapping)

MAX_TREE_CACHE_SIZE = 50 * 1024 * 1024

class LRUTreeCache(object):

    def __init__(self, repository):

        def approx_tree_size(tree):

            # Very rough estimate, 250 per inventory entry

            try:

                inv = tree.root_inventory

            except AttributeError:

                inv = tree.inventory

            return len(inv) * 250

        self.repository = repository

        self._cache = lru_cache.LRUSizeCache(max_size=MAX_TREE_CACHE_SIZE,

            after_cleanup_size=None, compute_size=approx_tree_size)

    def revision_tree(self, revid):

        try:

            tree = self._cache[revid]

        except KeyError:

            tree = self.repository.revision_tree(revid)

            self.add(tree)

        return tree

    def iter_revision_trees(self, revids):

        trees = {}

        todo = []

        for revid in revids:

            try:

                tree = self._cache[revid]

            except KeyError:

                todo.append(revid)

            else:

                assert tree.get_revision_id() == revid

                trees[revid] = tree

        for tree in self.repository.revision_trees(todo):

            trees[tree.get_revision_id()] = tree

            self.add(tree)

        return (trees[r] for r in revids)

    def revision_trees(self, revids):

        return list(self.iter_revision_trees(revids))

    def add(self, tree):

        self._cache[tree.get_revision_id()] = tree

def _find_missing_bzr_revids(graph, want, have):

    """Find the revisions that have to be pushed.

    :param get_parent_map: Function that returns the parents for a sequence

        of revisions.

    :param want: Revisions the target wants

    :param have: Revisions the target already has

    :return: Set of revisions to fetch

    """

    handled = set(have)

    todo = set()

    for rev in want:

        extra_todo = graph.find_unique_ancestors(rev, handled)

        todo.update(extra_todo)

        handled.update(extra_todo)

    if NULL_REVISION in todo:

        todo.remove(NULL_REVISION)

    return todo

def _check_expected_sha(expected_sha, object):

    """Check whether an object matches an expected SHA.

    :param expected_sha: None or expected SHA as either binary or as hex digest

    :param object: Object to verify

    """

    if expected_sha is None:

        return

    if len(expected_sha) == 40:

        if expected_sha != object.sha().hexdigest():

            raise AssertionError("Invalid sha for %r: %s" % (object,

                expected_sha))

    elif len(expected_sha) == 20:

        if expected_sha != object.sha().digest():

            raise AssertionError("Invalid sha for %r: %s" % (object,

                sha_to_hex(expected_sha)))

    else:

        raise AssertionError("Unknown length %d for %r" % (len(expected_sha),

            expected_sha))

def _tree_to_objects(tree, parent_trees, idmap, unusual_modes,

                     dummy_file_name=None):

    """Iterate over the objects that were introduced in a revision.

    :param idmap: id map

    :param parent_trees: Parent revision trees

    :param unusual_modes: Unusual file modes dictionary

    :param dummy_file_name: File name to use for dummy files

        in empty directories. None to skip empty directories

    :return: Yields (path, object, ie) entries

    """

    new_trees = {}

    new_blobs = []

    shamap = {}

    try:

        base_tree = parent_trees[0]

        other_parent_trees = parent_trees[1:]

    except IndexError:

        base_tree = tree._repository.revision_tree(NULL_REVISION)

        other_parent_trees = []

    def find_unchanged_parent_ie(file_id, kind, other, parent_trees):

        for ptree in parent_trees:

            try:

                pkind = ptree.kind(file_id)

            except errors.NoSuchId:

                pass

            else:

                if kind == "file":

                    if (pkind == "file" and 

                        ptree.get_file_sha1(file_id) == other):

                        return (file_id, ptree.get_file_revision(file_id))

                if kind == "symlink":

                    if (pkind == "symlink" and

                        ptree.get_symlink_target(file_id) == other):

                        return (file_id, ptree.get_file_revision(file_id))

        raise KeyError

    # Find all the changed blobs

    for (file_id, path, changed_content, versioned, parent, name, kind,

         executable) in tree.iter_changes(base_tree):

        if kind[1] == "file":

            if changed_content:

                try:

                    (pfile_id, prevision) = find_unchanged_parent_ie(file_id, kind[1], tree.get_file_sha1(file_id), other_parent_trees)

                except KeyError:

                    pass

                else:

                    try:

                        shamap[file_id] = idmap.lookup_blob_id(

                            pfile_id, prevision)

                    except KeyError:

                        # no-change merge ?

                        blob = Blob()

                        blob.data = tree.get_file_text(file_id)

                        shamap[file_id] = blob.id

            if not file_id in shamap:

                new_blobs.append((path[1], file_id))

            new_trees[posixpath.dirname(path[1])] = parent[1]

        elif kind[1] == "symlink":

            if changed_content:

                target = tree.get_symlink_target(file_id)

                blob = symlink_to_blob(target)

                shamap[file_id] = blob.id

                try:

                    find_unchanged_parent_ie(file_id, kind[1], target, other_parent_trees)

                except KeyError:

                    yield path[1], blob, (file_id, tree.get_file_revision(file_id, path[1]))

            new_trees[posixpath.dirname(path[1])] = parent[1]

        elif kind[1] not in (None, "directory"):

            raise AssertionError(kind[1])

        if (path[0] not in (None, "") and

            tree.has_id(parent[0]) and

            tree.kind(parent[0]) == "directory"):

            # Removal

            new_trees[posixpath.dirname(path[0])] = parent[0]

    # Fetch contents of the blobs that were changed

    for (path, file_id), chunks in tree.iter_files_bytes(

        [(file_id, (path, file_id)) for (path, file_id) in new_blobs]):

        obj = Blob()

        obj.chunked = chunks

        yield path, obj, (file_id, tree.get_file_revision(file_id, path))

        shamap[file_id] = obj.id

    for path in unusual_modes:

        parent_path = posixpath.dirname(path)

        file_id = tree.path2id(parent_path)

        assert file_id is not None, "Unable to find file id for %r" % parent_path

        new_trees[parent_path] = file_id

    trees = {}

    while new_trees:

        items = new_trees.items()

        new_trees = {}

        for path, file_id in items:

            if path != "":

                parent_path = urlutils.dirname(path)

                parent_id = tree.path2id(parent_path)

                new_trees[parent_path] = parent_id

            trees[path] = file_id

    def ie_to_hexsha(ie):

        try:

            return shamap[ie.file_id]

        except KeyError:

            # FIXME: Should be the same as in parent

            if ie.kind in ("file", "symlink"):

                try:

                    return idmap.lookup_blob_id(ie.file_id, ie.revision)

                except KeyError:

                    # no-change merge ?

                    blob = Blob()

                    blob.data = tree.get_file_text(ie.file_id)

                    return blob.id

            elif ie.kind == "directory":

                # Not all cache backends store the tree information, 

                # calculate again from scratch

                ret = directory_to_tree(ie.children, ie_to_hexsha,

                    unusual_modes, dummy_file_name, ie.parent_id is None)

                if ret is None:

                    return ret

                return ret.id

            else:

                raise AssertionError

    try:

        inv = tree.root_inventory

    except AttributeError:

        inv = tree.inventory

    for path in sorted(trees.keys(), reverse=True):

        file_id = trees[path]

        assert tree.kind(file_id) == 'directory'

        ie = inv[file_id]

        obj = directory_to_tree(ie.children, ie_to_hexsha, unusual_modes,

            dummy_file_name, path == "")

        if obj is not None:

            yield path, obj, (file_id, )

            shamap[file_id] = obj.id

class PackTupleIterable(object):

    def __init__(self, store):

        self.store = store

        self.store.lock_read()

        self.objects = {}

    def __del__(self):

        self.store.unlock()

    def add(self, sha, path):

        self.objects[sha] = path

    def __len__(self):

        return len(self.objects)

    def __iter__(self):

        return ((self.store[object_id], path) for (object_id, path) in

                self.objects.iteritems())

class BazaarObjectStore(BaseObjectStore):

    """A Git-style object store backed onto a Bazaar repository."""

    def __init__(self, repository, mapping=None):

        self.repository = repository

        self._map_updated = False

        self._locked = None

        if mapping is None:

            self.mapping = default_mapping

        else:

            self.mapping = mapping

        self._cache = cache_from_repository(repository)

        self._content_cache_types = ("tree",)

        self.start_write_group = self._cache.idmap.start_write_group

        self.abort_write_group = self._cache.idmap.abort_write_group

        self.commit_write_group = self._cache.idmap.commit_write_group

        self.tree_cache = LRUTreeCache(self.repository)

        self.unpeel_map = UnpeelMap.from_repository(self.repository)

    def _missing_revisions(self, revisions):

        return self._cache.idmap.missing_revisions(revisions)

    def _update_sha_map(self, stop_revision=None):

        if not self.is_locked():

            raise AssertionError()

        if self._map_updated:

            return

        if (stop_revision is not None and

            not self._missing_revisions([stop_revision])):

            return

        graph = self.repository.get_graph()

        if stop_revision is None:

            all_revids = self.repository.all_revision_ids()

            missing_revids = self._missing_revisions(all_revids)

        else:

            heads = set([stop_revision])

            missing_revids = self._missing_revisions(heads)

            while heads:

                parents = graph.get_parent_map(heads)

                todo = set()

                for p in parents.values():

                    todo.update([x for x in p if x not in missing_revids])

                heads = self._missing_revisions(todo)

                missing_revids.update(heads)

        if NULL_REVISION in missing_revids:

            missing_revids.remove(NULL_REVISION)

        missing_revids = self.repository.has_revisions(missing_revids)

        if not missing_revids:

            if stop_revision is None:

                self._map_updated = True

            return

        self.start_write_group()

        try:

            pb = ui.ui_factory.nested_progress_bar()

            try:

                for i, revid in enumerate(graph.iter_topo_order(missing_revids)):

                    trace.mutter('processing %r', revid)

                    pb.update("updating git map", i, len(missing_revids))

                    self._update_sha_map_revision(revid)

            finally:

                pb.finished()

            if stop_revision is None:

                self._map_updated = True

        except:

            self.abort_write_group()

            raise

        else:

            self.commit_write_group()

    def __iter__(self):

        self._update_sha_map()

        return iter(self._cache.idmap.sha1s())

    def _reconstruct_commit(self, rev, tree_sha, lossy, verifiers):

        """Reconstruct a Commit object.

        :param rev: Revision object

        :param tree_sha: SHA1 of the root tree object

        :param lossy: Whether or not to roundtrip bzr metadata

        :param verifiers: Verifiers for the commits

        :return: Commit object

        """

        def parent_lookup(revid):

            try:

                return self._lookup_revision_sha1(revid)

            except errors.NoSuchRevision:

                return None

        return self.mapping.export_commit(rev, tree_sha, parent_lookup,

            lossy, verifiers)

    def _create_fileid_map_blob(self, tree):

        # FIXME: This can probably be a lot more efficient, 

        # not all files necessarily have to be processed.

        file_ids = {}

        for (path, ie) in tree.inventory.iter_entries():

            if self.mapping.generate_file_id(path) != ie.file_id:

                file_ids[path] = ie.file_id

        return self.mapping.export_fileid_map(file_ids)

    def _revision_to_objects(self, rev, tree, lossy):

        """Convert a revision to a set of git objects.

        :param rev: Bazaar revision object

        :param tree: Bazaar revision tree

        :param lossy: Whether to not roundtrip all Bazaar revision data

        """

        unusual_modes = extract_unusual_modes(rev)

        present_parents = self.repository.has_revisions(rev.parent_ids)

        parent_trees = self.tree_cache.revision_trees(

            [p for p in rev.parent_ids if p in present_parents])

        root_tree = None

        for path, obj, bzr_key_data in _tree_to_objects(tree, parent_trees,

                self._cache.idmap, unusual_modes, self.mapping.BZR_DUMMY_FILE):

            if path == "":

                root_tree = obj

                root_key_data = bzr_key_data

                # Don't yield just yet

            else:

                yield path, obj, bzr_key_data

        if root_tree is None:

            # Pointless commit - get the tree sha elsewhere

            if not rev.parent_ids:

                root_tree = Tree()

            else:

                base_sha1 = self._lookup_revision_sha1(rev.parent_ids[0])

                root_tree = self[self[base_sha1].tree]

            root_key_data = (tree.get_root_id(), )

        if not lossy and self.mapping.BZR_FILE_IDS_FILE is not None:

            b = self._create_fileid_map_blob(tree)

            if b is not None:

                root_tree[self.mapping.BZR_FILE_IDS_FILE] = (

                    (stat.S_IFREG | 0644), b.id)

                yield self.mapping.BZR_FILE_IDS_FILE, b, None

        yield "", root_tree, root_key_data

        if not lossy:

            testament3 = StrictTestament3(rev, tree)

            verifiers = { "testament3-sha1": testament3.as_sha1() }

        else:

            verifiers = {}

        commit_obj = self._reconstruct_commit(rev, root_tree.id,

            lossy=lossy, verifiers=verifiers)

        try:

            foreign_revid, mapping = mapping_registry.parse_revision_id(

                rev.revision_id)

        except errors.InvalidRevisionId:

            pass

        else:

            _check_expected_sha(foreign_revid, commit_obj)

        yield None, commit_obj, None

    def _get_updater(self, rev):

        return self._cache.get_updater(rev)

    def _update_sha_map_revision(self, revid):

        rev = self.repository.get_revision(revid)

        tree = self.tree_cache.revision_tree(rev.revision_id)

        updater = self._get_updater(rev)

        # FIXME JRV 2011-12-15: Shouldn't we try both values for lossy ?

        for path, obj, ie in self._revision_to_objects(rev, tree, lossy=(not self.mapping.roundtripping)):

            if isinstance(obj, Commit):

                testament3 = StrictTestament3(rev, tree)

                ie = { "testament3-sha1": testament3.as_sha1() }

            updater.add_object(obj, ie, path)

        commit_obj = updater.finish()

        return commit_obj.id

    def _reconstruct_blobs(self, keys):

        """Return a Git Blob object from a fileid and revision stored in bzr.

        :param fileid: File id of the text

        :param revision: Revision of the text

        """

        stream = self.repository.iter_files_bytes(

            ((key[0], key[1], key) for key in keys))

        for (fileid, revision, expected_sha), chunks in stream:

            blob = Blob()

            blob.chunked = chunks

            if blob.id != expected_sha and blob.data == "":

                # Perhaps it's a symlink ?

                tree = self.tree_cache.revision_tree(revision)

                if tree.kind(fileid) == 'symlink':

                    blob = symlink_to_blob(tree.get_symlink_target(fileid))

            _check_expected_sha(expected_sha, blob)

            yield blob

    def _reconstruct_tree(self, fileid, revid, bzr_tree, unusual_modes,

        expected_sha=None):

        """Return a Git Tree object from a file id and a revision stored in bzr.

        :param fileid: fileid in the tree.

        :param revision: Revision of the tree.

        """

        def get_ie_sha1(entry):

            if entry.kind == "directory":

                try:

                    return self._cache.idmap.lookup_tree_id(entry.file_id,

                        revid)

                except (NotImplementedError, KeyError):

                    obj = self._reconstruct_tree(entry.file_id, revid, bzr_tree,

                        unusual_modes)

                    if obj is None:

                        return None

                    else:

                        return obj.id

            elif entry.kind in ("file", "symlink"):

                try:

                    return self._cache.idmap.lookup_blob_id(entry.file_id,

                        entry.revision)

                except KeyError:

                    # no-change merge?

                    return self._reconstruct_blobs(

                        [(entry.file_id, entry.revision, None)]).next().id

            elif entry.kind == 'tree-reference':

                # FIXME: Make sure the file id is the root id

                return self._lookup_revision_sha1(entry.reference_revision)

            else:

                raise AssertionError("unknown entry kind '%s'" % entry.kind)

        try:

            inv = bzr_tree.root_inventory

        except AttributeError:

            inv = bzr_tree.inventory

        tree = directory_to_tree(inv[fileid].children,

                get_ie_sha1, unusual_modes, self.mapping.BZR_DUMMY_FILE,

                bzr_tree.get_root_id() == fileid)

        if (bzr_tree.get_root_id() == fileid and

            self.mapping.BZR_FILE_IDS_FILE is not None):

            if tree is None:

                tree = Tree()

            b = self._create_fileid_map_blob(bzr_tree)

            # If this is the root tree, add the file ids

            tree[self.mapping.BZR_FILE_IDS_FILE] = (

                (stat.S_IFREG | 0644), b.id)

        if tree is not None:

            _check_expected_sha(expected_sha, tree)

        return tree

    def get_parents(self, sha):

        """Retrieve the parents of a Git commit by SHA1.

        :param sha: SHA1 of the commit

        :raises: KeyError, NotCommitError

        """

        return self[sha].parents

    def _lookup_revision_sha1(self, revid):

        """Return the SHA1 matching a Bazaar revision."""

        if revid == NULL_REVISION:

            return ZERO_SHA

        try:

            return self._cache.idmap.lookup_commit(revid)

        except KeyError:

            try:

                return mapping_registry.parse_revision_id(revid)[0]

            except errors.InvalidRevisionId: