~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2006-2010 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

import os

import errno

from stat import S_ISREG, S_IEXEC

import time

import bzrlib

from bzrlib import (

    errors,

    lazy_import,

    registry,

    tree,

    )

lazy_import.lazy_import(globals(), """

from bzrlib import (

    annotate,

    bencode,

    bzrdir,

    commit,

    delta,

    errors,

    inventory,

    multiparent,

    osutils,

    revision as _mod_revision,

    trace,

    ui,

    )

""")

from bzrlib.errors import (DuplicateKey, MalformedTransform, NoSuchFile,

                           ReusingTransform, CantMoveRoot,

                           ExistingLimbo, ImmortalLimbo, NoFinalPath,

                           UnableCreateSymlink)

from bzrlib.filters import filtered_output_bytes, ContentFilterContext

from bzrlib.inventory import InventoryEntry

from bzrlib.osutils import (

    delete_any,

    file_kind,

    has_symlinks,

    pathjoin,

    sha_file,

    splitpath,

    supports_executable,

    )

from bzrlib.progress import ProgressPhase

from bzrlib.symbol_versioning import (

    deprecated_function,

    deprecated_in,

    deprecated_method,

    )

from bzrlib.trace import warning

import bzrlib.ui

import bzrlib.urlutils as urlutils

ROOT_PARENT = "root-parent"

def unique_add(map, key, value):

    if key in map:

        raise DuplicateKey(key=key)

    map[key] = value

class _TransformResults(object):

    def __init__(self, modified_paths, rename_count):

        object.__init__(self)

        self.modified_paths = modified_paths

        self.rename_count = rename_count

class TreeTransformBase(object):

    """The base class for TreeTransform and its kin."""

    def __init__(self, tree, pb=None,

                 case_sensitive=True):

        """Constructor.

        :param tree: The tree that will be transformed, but not necessarily

            the output tree.

        :param pb: ignored

        :param case_sensitive: If True, the target of the transform is

            case sensitive, not just case preserving.

        """

        object.__init__(self)

        self._tree = tree

        self._id_number = 0

        # mapping of trans_id -> new basename

        self._new_name = {}

        # mapping of trans_id -> new parent trans_id

        self._new_parent = {}

        # mapping of trans_id with new contents -> new file_kind

        self._new_contents = {}

        # Set of trans_ids whose contents will be removed

        self._removed_contents = set()

        # Mapping of trans_id -> new execute-bit value

        self._new_executability = {}

        # Mapping of trans_id -> new tree-reference value

        self._new_reference_revision = {}

        # Mapping of trans_id -> new file_id

        self._new_id = {}

        # Mapping of old file-id -> trans_id

        self._non_present_ids = {}

        # Mapping of new file_id -> trans_id

        self._r_new_id = {}

        # Set of trans_ids that will be removed

        self._removed_id = set()

        # Mapping of path in old tree -> trans_id

        self._tree_path_ids = {}

        # Mapping trans_id -> path in old tree

        self._tree_id_paths = {}

        # The trans_id that will be used as the tree root

        root_id = tree.get_root_id()

        if root_id is not None:

            self._new_root = self.trans_id_tree_file_id(root_id)

        else:

            self._new_root = None

        # Indicator of whether the transform has been applied

        self._done = False

        # A progress bar

        self._pb = pb

        # Whether the target is case sensitive

        self._case_sensitive_target = case_sensitive

        # A counter of how many files have been renamed

        self.rename_count = 0

    def finalize(self):

        """Release the working tree lock, if held.

        This is required if apply has not been invoked, but can be invoked

        even after apply.

        """

        if self._tree is None:

            return

        self._tree.unlock()

        self._tree = None

    def __get_root(self):

        return self._new_root

    root = property(__get_root)

    def _assign_id(self):

        """Produce a new tranform id"""

        new_id = "new-%s" % self._id_number

        self._id_number +=1

        return new_id

    def create_path(self, name, parent):

        """Assign a transaction id to a new path"""

        trans_id = self._assign_id()

        unique_add(self._new_name, trans_id, name)

        unique_add(self._new_parent, trans_id, parent)

        return trans_id

    def adjust_path(self, name, parent, trans_id):

        """Change the path that is assigned to a transaction id."""

        if parent is None:

            raise ValueError("Parent trans-id may not be None")

        if trans_id == self._new_root:

            raise CantMoveRoot

        self._new_name[trans_id] = name

        self._new_parent[trans_id] = parent

    def adjust_root_path(self, name, parent):

        """Emulate moving the root by moving all children, instead.

        We do this by undoing the association of root's transaction id with the

        current tree.  This allows us to create a new directory with that

        transaction id.  We unversion the root directory and version the

        physically new directory, and hope someone versions the tree root

        later.

        """

        old_root = self._new_root

        old_root_file_id = self.final_file_id(old_root)

        # force moving all children of root

        for child_id in self.iter_tree_children(old_root):

            if child_id != parent:

                self.adjust_path(self.final_name(child_id),

                                 self.final_parent(child_id), child_id)

            file_id = self.final_file_id(child_id)

            if file_id is not None:

                self.unversion_file(child_id)

            self.version_file(file_id, child_id)

        # the physical root needs a new transaction id

        self._tree_path_ids.pop("")

        self._tree_id_paths.pop(old_root)

        self._new_root = self.trans_id_tree_file_id(self._tree.get_root_id())

        if parent == old_root:

            parent = self._new_root

        self.adjust_path(name, parent, old_root)

        self.create_directory(old_root)

        self.version_file(old_root_file_id, old_root)

        self.unversion_file(self._new_root)

    def fixup_new_roots(self):

        """Reinterpret requests to change the root directory

        Instead of creating a root directory, or moving an existing directory,

        all the attributes and children of the new root are applied to the

        existing root directory.

        This means that the old root trans-id becomes obsolete, so it is

        recommended only to invoke this after the root trans-id has become

        irrelevant.

        """

        new_roots = [k for k, v in self._new_parent.iteritems() if v is

                     ROOT_PARENT]

        if len(new_roots) < 1:

            return

        if len(new_roots) != 1:

            raise ValueError('A tree cannot have two roots!')

        if self._new_root is None:

            self._new_root = new_roots[0]

            return

        old_new_root = new_roots[0]

        # TODO: What to do if a old_new_root is present, but self._new_root is

        #       not listed as being removed? This code explicitly unversions

        #       the old root and versions it with the new file_id. Though that

        #       seems like an incomplete delta

        # unversion the new root's directory.

        file_id = self.final_file_id(old_new_root)

        if old_new_root in self._new_id:

            self.cancel_versioning(old_new_root)

        else:

            self.unversion_file(old_new_root)

        # if, at this stage, root still has an old file_id, zap it so we can

        # stick a new one in.

        if (self.tree_file_id(self._new_root) is not None and

            self._new_root not in self._removed_id):

            self.unversion_file(self._new_root)

        self.version_file(file_id, self._new_root)

        # Now move children of new root into old root directory.

        # Ensure all children are registered with the transaction, but don't

        # use directly-- some tree children have new parents

        list(self.iter_tree_children(old_new_root))

        # Move all children of new root into old root directory.

        for child in self.by_parent().get(old_new_root, []):

            self.adjust_path(self.final_name(child), self._new_root, child)

        # Ensure old_new_root has no directory.

        if old_new_root in self._new_contents:

            self.cancel_creation(old_new_root)

        else:

            self.delete_contents(old_new_root)

        # prevent deletion of root directory.

        if self._new_root in self._removed_contents:

            self.cancel_deletion(self._new_root)

        # destroy path info for old_new_root.

        del self._new_parent[old_new_root]

        del self._new_name[old_new_root]

    def trans_id_tree_file_id(self, inventory_id):

        """Determine the transaction id of a working tree file.

        This reflects only files that already exist, not ones that will be

        added by transactions.

        """

        if inventory_id is None:

            raise ValueError('None is not a valid file id')

        path = self._tree.id2path(inventory_id)

        return self.trans_id_tree_path(path)

    def trans_id_file_id(self, file_id):

        """Determine or set the transaction id associated with a file ID.

        A new id is only created for file_ids that were never present.  If

        a transaction has been unversioned, it is deliberately still returned.

        (this will likely lead to an unversioned parent conflict.)

        """

        if file_id is None:

            raise ValueError('None is not a valid file id')

        if file_id in self._r_new_id and self._r_new_id[file_id] is not None:

            return self._r_new_id[file_id]

        else:

            try:

                self._tree.iter_entries_by_dir([file_id]).next()

            except StopIteration:

                if file_id in self._non_present_ids:

                    return self._non_present_ids[file_id]

                else:

                    trans_id = self._assign_id()

                    self._non_present_ids[file_id] = trans_id

                    return trans_id

            else:

                return self.trans_id_tree_file_id(file_id)

    def trans_id_tree_path(self, path):

        """Determine (and maybe set) the transaction ID for a tree path."""

        path = self.canonical_path(path)

        if path not in self._tree_path_ids:

            self._tree_path_ids[path] = self._assign_id()

            self._tree_id_paths[self._tree_path_ids[path]] = path

        return self._tree_path_ids[path]

    def get_tree_parent(self, trans_id):

        """Determine id of the parent in the tree."""

        path = self._tree_id_paths[trans_id]

        if path == "":

            return ROOT_PARENT

        return self.trans_id_tree_path(os.path.dirname(path))

    def delete_contents(self, trans_id):

        """Schedule the contents of a path entry for deletion"""

        kind = self.tree_kind(trans_id)

        if kind is not None:

            self._removed_contents.add(trans_id)

    def cancel_deletion(self, trans_id):

        """Cancel a scheduled deletion"""

        self._removed_contents.remove(trans_id)

    def unversion_file(self, trans_id):

        """Schedule a path entry to become unversioned"""

        self._removed_id.add(trans_id)

    def delete_versioned(self, trans_id):

        """Delete and unversion a versioned file"""

        self.delete_contents(trans_id)

        self.unversion_file(trans_id)

    def set_executability(self, executability, trans_id):

        """Schedule setting of the 'execute' bit

        To unschedule, set to None

        """

        if executability is None:

            del self._new_executability[trans_id]

        else:

            unique_add(self._new_executability, trans_id, executability)

    def set_tree_reference(self, revision_id, trans_id):

        """Set the reference associated with a directory"""

        unique_add(self._new_reference_revision, trans_id, revision_id)

    def version_file(self, file_id, trans_id):

        """Schedule a file to become versioned."""

        if file_id is None:

            raise ValueError()

        unique_add(self._new_id, trans_id, file_id)

        unique_add(self._r_new_id, file_id, trans_id)

    def cancel_versioning(self, trans_id):

        """Undo a previous versioning of a file"""

        file_id = self._new_id[trans_id]

        del self._new_id[trans_id]

        del self._r_new_id[file_id]

    def new_paths(self, filesystem_only=False):

        """Determine the paths of all new and changed files.

        :param filesystem_only: if True, only calculate values for files

            that require renames or execute bit changes.

        """

        new_ids = set()

        if filesystem_only:

            stale_ids = self._needs_rename.difference(self._new_name)

            stale_ids.difference_update(self._new_parent)

            stale_ids.difference_update(self._new_contents)

            stale_ids.difference_update(self._new_id)

            needs_rename = self._needs_rename.difference(stale_ids)

            id_sets = (needs_rename, self._new_executability)

        else:

            id_sets = (self._new_name, self._new_parent, self._new_contents,

                       self._new_id, self._new_executability)

        for id_set in id_sets:

            new_ids.update(id_set)

        return sorted(FinalPaths(self).get_paths(new_ids))

    def _inventory_altered(self):

        """Get the trans_ids and paths of files needing new inv entries."""

        new_ids = set()

        for id_set in [self._new_name, self._new_parent, self._new_id,

                       self._new_executability]:

            new_ids.update(id_set)

        changed_kind = set(self._removed_contents)

        changed_kind.intersection_update(self._new_contents)

        changed_kind.difference_update(new_ids)

        changed_kind = (t for t in changed_kind

                        if self.tree_kind(t) != self.final_kind(t))

        new_ids.update(changed_kind)

        return sorted(FinalPaths(self).get_paths(new_ids))

    def final_kind(self, trans_id):

        """Determine the final file kind, after any changes applied.

        :return: None if the file does not exist/has no contents.  (It is

            conceivable that a path would be created without the corresponding

            contents insertion command)

        """

        if trans_id in self._new_contents:

            return self._new_contents[trans_id]

        elif trans_id in self._removed_contents:

            return None

        else:

            return self.tree_kind(trans_id)

    def tree_file_id(self, trans_id):

        """Determine the file id associated with the trans_id in the tree"""

        try:

            path = self._tree_id_paths[trans_id]

        except KeyError:

            # the file is a new, unversioned file, or invalid trans_id

            return None

        # the file is old; the old id is still valid

        if self._new_root == trans_id:

            return self._tree.get_root_id()

        return self._tree.path2id(path)

    def final_file_id(self, trans_id):

        """Determine the file id after any changes are applied, or None.

        None indicates that the file will not be versioned after changes are

        applied.

        """

        try:

            return self._new_id[trans_id]

        except KeyError:

            if trans_id in self._removed_id:

                return None

        return self.tree_file_id(trans_id)

    def inactive_file_id(self, trans_id):

        """Return the inactive file_id associated with a transaction id.

        That is, the one in the tree or in non_present_ids.

        The file_id may actually be active, too.

        """

        file_id = self.tree_file_id(trans_id)

        if file_id is not None:

            return file_id

        for key, value in self._non_present_ids.iteritems():

            if value == trans_id:

                return key

    def final_parent(self, trans_id):

        """Determine the parent file_id, after any changes are applied.

        ROOT_PARENT is returned for the tree root.

        """

        try:

            return self._new_parent[trans_id]

        except KeyError:

            return self.get_tree_parent(trans_id)

    def final_name(self, trans_id):

        """Determine the final filename, after all changes are applied."""

        try:

            return self._new_name[trans_id]

        except KeyError:

            try:

                return os.path.basename(self._tree_id_paths[trans_id])

            except KeyError:

                raise NoFinalPath(trans_id, self)

    def by_parent(self):

        """Return a map of parent: children for known parents.

        Only new paths and parents of tree files with assigned ids are used.

        """

        by_parent = {}

        items = list(self._new_parent.iteritems())

        items.extend((t, self.final_parent(t)) for t in

                      self._tree_id_paths.keys())

        for trans_id, parent_id in items:

            if parent_id not in by_parent:

                by_parent[parent_id] = set()

            by_parent[parent_id].add(trans_id)

        return by_parent

    def path_changed(self, trans_id):

        """Return True if a trans_id's path has changed."""

        return (trans_id in self._new_name) or (trans_id in self._new_parent)

    def new_contents(self, trans_id):

        return (trans_id in self._new_contents)

    def find_conflicts(self):

        """Find any violations of inventory or filesystem invariants"""

        if self._done is True:

            raise ReusingTransform()

        conflicts = []

        # ensure all children of all existent parents are known

        # all children of non-existent parents are known, by definition.

        self._add_tree_children()

        by_parent = self.by_parent()

        conflicts.extend(self._unversioned_parents(by_parent))

        conflicts.extend(self._parent_loops())

        conflicts.extend(self._duplicate_entries(by_parent))

        conflicts.extend(self._duplicate_ids())

        conflicts.extend(self._parent_type_conflicts(by_parent))

        conflicts.extend(self._improper_versioning())

        conflicts.extend(self._executability_conflicts())

        conflicts.extend(self._overwrite_conflicts())

        return conflicts

    def _check_malformed(self):

        conflicts = self.find_conflicts()

        if len(conflicts) != 0:

            raise MalformedTransform(conflicts=conflicts)

    def _add_tree_children(self):

        """Add all the children of all active parents to the known paths.

        Active parents are those which gain children, and those which are

        removed.  This is a necessary first step in detecting conflicts.

        """

        parents = self.by_parent().keys()

        parents.extend([t for t in self._removed_contents if

                        self.tree_kind(t) == 'directory'])

        for trans_id in self._removed_id:

            file_id = self.tree_file_id(trans_id)

            if file_id is not None:

                if self._tree.inventory[file_id].kind == 'directory':

                    parents.append(trans_id)

            elif self.tree_kind(trans_id) == 'directory':

                parents.append(trans_id)

        for parent_id in parents:

            # ensure that all children are registered with the transaction

            list(self.iter_tree_children(parent_id))

    @deprecated_method(deprecated_in((2, 3, 0)))

    def has_named_child(self, by_parent, parent_id, name):

        return self._has_named_child(

            name, parent_id, known_children=by_parent.get(parent_id, []))

    def _has_named_child(self, name, parent_id, known_children):

        """Does a parent already have a name child.

        :param name: The searched for name.

        :param parent_id: The parent for which the check is made.

        :param known_children: The already known children. This should have

            been recently obtained from `self.by_parent.get(parent_id)`

            (or will be if None is passed).

        """

        if known_children is None:

            known_children = self.by_parent().get(parent_id, [])

        for child in known_children:

            if self.final_name(child) == name:

                return True

        parent_path = self._tree_id_paths.get(parent_id, None)

        if parent_path is None:

            # No parent... no children

            return False

        child_path = joinpath(parent_path, name)

        child_id = self._tree_path_ids.get(child_path, None)

        if child_id is None:

            # Not known by the tree transform yet, check the filesystem

            return osutils.lexists(self._tree.abspath(child_path))

        else:

            raise AssertionError('child_id is missing: %s, %s, %s'

                                 % (name, parent_id, child_id))

    def _available_backup_name(self, name, target_id):

        """Find an available backup name.

        :param name: The basename of the file.

        :param target_id: The directory trans_id where the backup should 

            be placed.

        """

        known_children = self.by_parent().get(target_id, [])

        return osutils.available_backup_name(

            name,

            lambda base: self._has_named_child(

                base, target_id, known_children))

    def _parent_loops(self):

        """No entry should be its own ancestor"""

        conflicts = []

        for trans_id in self._new_parent:

            seen = set()

            parent_id = trans_id

            while parent_id is not ROOT_PARENT:

                seen.add(parent_id)

                try:

                    parent_id = self.final_parent(parent_id)

                except KeyError:

                    break

                if parent_id == trans_id:

                    conflicts.append(('parent loop', trans_id))

                if parent_id in seen:

                    break

        return conflicts

    def _unversioned_parents(self, by_parent):

        """If parent directories are versioned, children must be versioned."""

        conflicts = []

        for parent_id, children in by_parent.iteritems():

            if parent_id is ROOT_PARENT:

                continue

            if self.final_file_id(parent_id) is not None:

                continue

            for child_id in children:

                if self.final_file_id(child_id) is not None:

                    conflicts.append(('unversioned parent', parent_id))

                    break;

        return conflicts

    def _improper_versioning(self):

        """Cannot version a file with no contents, or a bad type.

        However, existing entries with no contents are okay.

        """

        conflicts = []

        for trans_id in self._new_id.iterkeys():

            kind = self.final_kind(trans_id)

            if kind is None:

                conflicts.append(('versioning no contents', trans_id))

                continue

            if not InventoryEntry.versionable_kind(kind):

                conflicts.append(('versioning bad kind', trans_id, kind))

        return conflicts

    def _executability_conflicts(self):

        """Check for bad executability changes.