~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2005, 2006 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

import os

import errno

import warnings

from bzrlib import (

    debug,

    errors,

    osutils,

    patiencediff,

    registry,

    revision as _mod_revision,

    )

from bzrlib.branch import Branch

from bzrlib.conflicts import ConflictList, Conflict

from bzrlib.errors import (BzrCommandError,

                           BzrError,

                           NoCommonAncestor,

                           NoCommits,

                           NoSuchRevision,

                           NoSuchFile,

                           NotBranchError,

                           NotVersionedError,

                           UnrelatedBranches,

                           UnsupportedOperation,

                           WorkingTreeNotRevision,

                           BinaryFile,

                           )

from bzrlib.merge3 import Merge3

from bzrlib.osutils import rename, pathjoin

from progress import DummyProgress, ProgressPhase

from bzrlib.revision import (NULL_REVISION, ensure_null)

from bzrlib.textfile import check_text_lines

from bzrlib.trace import mutter, warning, note

from bzrlib.transform import (TreeTransform, resolve_conflicts, cook_conflicts,

                              conflict_pass, FinalPaths, create_by_entry,

                              unique_add, ROOT_PARENT)

from bzrlib.versionedfile import PlanWeaveMerge

from bzrlib import ui

# TODO: Report back as changes are merged in

def transform_tree(from_tree, to_tree, interesting_ids=None):

    merge_inner(from_tree.branch, to_tree, from_tree, ignore_zero=True,

                interesting_ids=interesting_ids, this_tree=from_tree)

class Merger(object):

    def __init__(self, this_branch, other_tree=None, base_tree=None,

                 this_tree=None, pb=DummyProgress(), change_reporter=None,

                 recurse='down'):

        object.__init__(self)

        assert this_tree is not None, "this_tree is required"

        self.this_branch = this_branch

        self.this_basis = _mod_revision.ensure_null(

            this_branch.last_revision())

        self.this_rev_id = None

        self.this_tree = this_tree

        self.this_revision_tree = None

        self.this_basis_tree = None

        self.other_tree = other_tree

        self.other_branch = None

        self.base_tree = base_tree

        self.ignore_zero = False

        self.backup_files = False

        self.interesting_ids = None

        self.interesting_files = None

        self.show_base = False

        self.reprocess = False

        self._pb = pb

        self.pp = None

        self.recurse = recurse

        self.change_reporter = change_reporter

        self._cached_trees = {}

    @staticmethod

    def from_uncommitted(tree, other_tree, pb):

        """Return a Merger for uncommitted changes in other_tree.

        :param tree: The tree to merge into

        :param other_tree: The tree to get uncommitted changes from

        :param pb: A progress indicator

        """

        merger = Merger(tree.branch, other_tree, other_tree.basis_tree(), tree,

                        pb)

        merger.base_rev_id = merger.base_tree.get_revision_id()

        merger.other_rev_id = None

        return merger

    @classmethod

    def from_mergeable(klass, tree, mergeable, pb):

        """Return a Merger for a bundle or merge directive.

        :param tree: The tree to merge changes into

        :param mergeable: A merge directive or bundle

        :param pb: A progress indicator

        """

        mergeable.install_revisions(tree.branch.repository)

        base_revision_id, other_revision_id, verified =\

            mergeable.get_merge_request(tree.branch.repository)

        if (base_revision_id != _mod_revision.NULL_REVISION and

            tree.branch.repository.get_graph().is_ancestor(

            base_revision_id, tree.branch.last_revision())):

            base_revision_id = None

        merger = klass.from_revision_ids(pb, tree, other_revision_id,

                                         base_revision_id)

        return merger, verified

    @staticmethod

    def from_revision_ids(pb, this, other, base=None, other_branch=None,

                          base_branch=None):

        """Return a Merger for revision-ids.

        :param tree: The tree to merge changes into

        :param other: The revision-id to use as OTHER

        :param base: The revision-id to use as BASE.  If not specified, will

            be auto-selected.

        :param other_branch: A branch containing the other revision-id.  If

            not supplied, this.branch is used.

        :param base_branch: A branch containing the base revision-id.  If

            not supplied, other_branch or this.branch will be used.

        :param pb: A progress indicator

        """

        merger = Merger(this.branch, this_tree=this, pb=pb)

        if other_branch is None:

            other_branch = this.branch

        merger.set_other_revision(other, other_branch)

        if base is None:

            merger.find_base()

        else:

            if base_branch is None:

                base_branch = other_branch

            merger.set_base_revision(base, base_branch)

        return merger

    def revision_tree(self, revision_id, branch=None):

        if revision_id not in self._cached_trees:

            if branch is None:

                branch = self.this_branch

            try:

                tree = self.this_tree.revision_tree(revision_id)

            except errors.NoSuchRevisionInTree:

                tree = branch.repository.revision_tree(revision_id)

            self._cached_trees[revision_id] = tree

        return self._cached_trees[revision_id]

    def _get_tree(self, treespec, possible_transports=None):

        from bzrlib import workingtree

        location, revno = treespec

        if revno is None:

            tree = workingtree.WorkingTree.open_containing(location)[0]

            return tree.branch, tree

        branch = Branch.open_containing(location, possible_transports)[0]

        if revno == -1:

            revision_id = branch.last_revision()

        else:

            revision_id = branch.get_rev_id(revno)

        revision_id = ensure_null(revision_id)

        return branch, self.revision_tree(revision_id, branch)

    def ensure_revision_trees(self):

        if self.this_revision_tree is None:

            self.this_basis_tree = self.revision_tree(self.this_basis)

            if self.this_basis == self.this_rev_id:

                self.this_revision_tree = self.this_basis_tree

        if self.other_rev_id is None:

            other_basis_tree = self.revision_tree(self.other_basis)

            changes = other_basis_tree.changes_from(self.other_tree)

            if changes.has_changed():

                raise WorkingTreeNotRevision(self.this_tree)

            other_rev_id = self.other_basis

            self.other_tree = other_basis_tree

    def file_revisions(self, file_id):

        self.ensure_revision_trees()

        def get_id(tree, file_id):

            revision_id = tree.inventory[file_id].revision

            assert revision_id is not None

            return revision_id

        if self.this_rev_id is None:

            if self.this_basis_tree.get_file_sha1(file_id) != \

                self.this_tree.get_file_sha1(file_id):

                raise WorkingTreeNotRevision(self.this_tree)

        trees = (self.this_basis_tree, self.other_tree)

        return [get_id(tree, file_id) for tree in trees]

    def check_basis(self, check_clean, require_commits=True):

        if self.this_basis is None and require_commits is True:

            raise BzrCommandError("This branch has no commits."

                                  " (perhaps you would prefer 'bzr pull')")

        if check_clean:

            self.compare_basis()

            if self.this_basis != self.this_rev_id:

                raise errors.UncommittedChanges(self.this_tree)

    def compare_basis(self):

        try:

            basis_tree = self.revision_tree(self.this_tree.last_revision())

        except errors.RevisionNotPresent:

            basis_tree = self.this_tree.basis_tree()

        changes = self.this_tree.changes_from(basis_tree)

        if not changes.has_changed():

            self.this_rev_id = self.this_basis

    def set_interesting_files(self, file_list):

        self.interesting_files = file_list

    def set_pending(self):

        if not self.base_is_ancestor or not self.base_is_other_ancestor or self.other_rev_id is None:

            return

        self._add_parent()

    def _add_parent(self):

        new_parents = self.this_tree.get_parent_ids() + [self.other_rev_id]

        new_parent_trees = []

        for revision_id in new_parents:

            try:

                tree = self.revision_tree(revision_id)

            except errors.RevisionNotPresent:

                tree = None

            else:

                tree.lock_read()

            new_parent_trees.append((revision_id, tree))

        try:

            self.this_tree.set_parent_trees(new_parent_trees,

                                            allow_leftmost_as_ghost=True)

        finally:

            for _revision_id, tree in new_parent_trees:

                if tree is not None:

                    tree.unlock()

    def set_other(self, other_revision, possible_transports=None):

        """Set the revision and tree to merge from.

        This sets the other_tree, other_rev_id, other_basis attributes.

        :param other_revision: The [path, revision] list to merge from.

        """

        self.other_branch, self.other_tree = self._get_tree(other_revision,

                                                            possible_transports)

        if other_revision[1] == -1:

            self.other_rev_id = _mod_revision.ensure_null(

                self.other_branch.last_revision())

            if _mod_revision.is_null(self.other_rev_id):

                raise NoCommits(self.other_branch)

            self.other_basis = self.other_rev_id

        elif other_revision[1] is not None:

            self.other_rev_id = self.other_branch.get_rev_id(other_revision[1])

            self.other_basis = self.other_rev_id

        else:

            self.other_rev_id = None

            self.other_basis = self.other_branch.last_revision()

            if self.other_basis is None:

                raise NoCommits(self.other_branch)

        if self.other_rev_id is not None:

            self._cached_trees[self.other_rev_id] = self.other_tree

        self._maybe_fetch(self.other_branch,self.this_branch, self.other_basis)

    def set_other_revision(self, revision_id, other_branch):

        """Set 'other' based on a branch and revision id

        :param revision_id: The revision to use for a tree

        :param other_branch: The branch containing this tree

        """

        self.other_rev_id = revision_id

        self.other_branch = other_branch

        self._maybe_fetch(other_branch, self.this_branch, self.other_rev_id)

        self.other_tree = self.revision_tree(revision_id)

        self.other_basis = revision_id

    def set_base_revision(self, revision_id, branch):

        """Set 'base' based on a branch and revision id

        :param revision_id: The revision to use for a tree

        :param branch: The branch containing this tree

        """

        self.base_rev_id = revision_id

        self.base_branch = branch

        self._maybe_fetch(branch, self.this_branch, revision_id)

        self.base_tree = self.revision_tree(revision_id)

        graph = self.this_branch.repository.get_graph()

        self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,

                                                  self.this_basis)

        self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,

                                                        self.other_basis)

    def _maybe_fetch(self, source, target, revision_id):

        if not source.repository.has_same_location(target.repository):

            target.fetch(source, revision_id)

    def find_base(self):

        this_repo = self.this_branch.repository

        graph = this_repo.get_graph()

        revisions = [ensure_null(self.this_basis),

                     ensure_null(self.other_basis)]

        if NULL_REVISION in revisions:

            self.base_rev_id = NULL_REVISION

        else:

            self.base_rev_id, steps = graph.find_unique_lca(revisions[0],

                revisions[1], count_steps=True)

            if self.base_rev_id == NULL_REVISION:

                raise UnrelatedBranches()

            if steps > 1:

                warning('Warning: criss-cross merge encountered.  See bzr'

                        ' help criss-cross.')

        self.base_tree = self.revision_tree(self.base_rev_id)

        self.base_is_ancestor = True

        self.base_is_other_ancestor = True

    def set_base(self, base_revision):

        """Set the base revision to use for the merge.

        :param base_revision: A 2-list containing a path and revision number.

        """

        mutter("doing merge() with no base_revision specified")

        if base_revision == [None, None]:

            self.find_base()

        else:

            base_branch, self.base_tree = self._get_tree(base_revision)

            if base_revision[1] == -1:

                self.base_rev_id = base_branch.last_revision()

            elif base_revision[1] is None:

                self.base_rev_id = _mod_revision.NULL_REVISION

            else:

                self.base_rev_id = _mod_revision.ensure_null(

                    base_branch.get_rev_id(base_revision[1]))

            self._maybe_fetch(base_branch, self.this_branch, self.base_rev_id)

            graph = self.this_branch.repository.get_graph()

            self.base_is_ancestor = graph.is_ancestor(self.base_rev_id,

                                                      self.this_basis)

            self.base_is_other_ancestor = graph.is_ancestor(self.base_rev_id,

                                                            self.other_basis)

    def do_merge(self):

        kwargs = {'working_tree':self.this_tree, 'this_tree': self.this_tree,

                  'other_tree': self.other_tree,

                  'interesting_ids': self.interesting_ids,

                  'interesting_files': self.interesting_files,

                  'pp': self.pp}

        if self.merge_type.requires_base:

            kwargs['base_tree'] = self.base_tree

        if self.merge_type.supports_reprocess:

            kwargs['reprocess'] = self.reprocess

        elif self.reprocess:

            raise BzrError("Conflict reduction is not supported for merge"

                                  " type %s." % self.merge_type)

        if self.merge_type.supports_show_base:

            kwargs['show_base'] = self.show_base

        elif self.show_base:

            raise BzrError("Showing base is not supported for this"

                                  " merge type. %s" % self.merge_type)

        self.this_tree.lock_tree_write()

        if self.base_tree is not None:

            self.base_tree.lock_read()

        if self.other_tree is not None:

            self.other_tree.lock_read()

        try:

            merge = self.merge_type(pb=self._pb,

                                    change_reporter=self.change_reporter,

                                    **kwargs)

            if self.recurse == 'down':

                for path, file_id in self.this_tree.iter_references():

                    sub_tree = self.this_tree.get_nested_tree(file_id, path)

                    other_revision = self.other_tree.get_reference_revision(

                        file_id, path)

                    if  other_revision == sub_tree.last_revision():

                        continue

                    sub_merge = Merger(sub_tree.branch, this_tree=sub_tree)

                    sub_merge.merge_type = self.merge_type

                    relpath = self.this_tree.relpath(path)

                    other_branch = self.other_branch.reference_parent(file_id, relpath)

                    sub_merge.set_other_revision(other_revision, other_branch)

                    base_revision = self.base_tree.get_reference_revision(file_id)

                    sub_merge.base_tree = \

                        sub_tree.branch.repository.revision_tree(base_revision)

                    sub_merge.do_merge()

        finally:

            if self.other_tree is not None:

                self.other_tree.unlock()

            if self.base_tree is not None:

                self.base_tree.unlock()

            self.this_tree.unlock()

        if len(merge.cooked_conflicts) == 0:

            if not self.ignore_zero:

                note("All changes applied successfully.")

        else:

            note("%d conflicts encountered." % len(merge.cooked_conflicts))

        return len(merge.cooked_conflicts)

class Merge3Merger(object):

    """Three-way merger that uses the merge3 text merger"""

    requires_base = True

    supports_reprocess = True

    supports_show_base = True

    history_based = False

    winner_idx = {"this": 2, "other": 1, "conflict": 1}

    def __init__(self, working_tree, this_tree, base_tree, other_tree, 

                 interesting_ids=None, reprocess=False, show_base=False,

                 pb=DummyProgress(), pp=None, change_reporter=None,

                 interesting_files=None):

        """Initialize the merger object and perform the merge.

        :param working_tree: The working tree to apply the merge to

        :param this_tree: The local tree in the merge operation

        :param base_tree: The common tree in the merge operation

        :param other_tree: The other other tree to merge changes from

        :param interesting_ids: The file_ids of files that should be

            participate in the merge.  May not be combined with

            interesting_files.

        :param: reprocess If True, perform conflict-reduction processing.

        :param show_base: If True, show the base revision in text conflicts.

            (incompatible with reprocess)

        :param pb: A Progress bar

        :param pp: A ProgressPhase object

        :param change_reporter: An object that should report changes made

        :param interesting_files: The tree-relative paths of files that should

            participate in the merge.  If these paths refer to directories,

            the contents of those directories will also be included.  May not

            be combined with interesting_ids.  If neither interesting_files nor

            interesting_ids is specified, all files may participate in the

            merge.

        """

        object.__init__(self)

        if interesting_files is not None:

            assert interesting_ids is None

        self.interesting_ids = interesting_ids

        self.interesting_files = interesting_files

        self.this_tree = working_tree

        self.this_tree.lock_tree_write()

        self.base_tree = base_tree

        self.base_tree.lock_read()

        self.other_tree = other_tree

        self.other_tree.lock_read()

        self._raw_conflicts = []

        self.cooked_conflicts = []

        self.reprocess = reprocess

        self.show_base = show_base

        self.pb = pb

        self.pp = pp

        self.change_reporter = change_reporter

        if self.pp is None:

            self.pp = ProgressPhase("Merge phase", 3, self.pb)

        self.tt = TreeTransform(working_tree, self.pb)

        try:

            self.pp.next_phase()

            entries = self._entries3()

            child_pb = ui.ui_factory.nested_progress_bar()

            try:

                for num, (file_id, changed, parents3, names3,

                          executable3) in enumerate(entries):

                    child_pb.update('Preparing file merge', num, len(entries))

                    self._merge_names(file_id, parents3, names3)

                    if changed:

                        file_status = self.merge_contents(file_id)

                    else:

                        file_status = 'unmodified'

                    self._merge_executable(file_id,

                        executable3, file_status)

            finally:

                child_pb.finished()

            self.fix_root()

            self.pp.next_phase()

            child_pb = ui.ui_factory.nested_progress_bar()

            try:

                fs_conflicts = resolve_conflicts(self.tt, child_pb,

                    lambda t, c: conflict_pass(t, c, self.other_tree))

            finally:

                child_pb.finished()

            if change_reporter is not None:

                from bzrlib import delta

                delta.report_changes(self.tt._iter_changes(), change_reporter)

            self.cook_conflicts(fs_conflicts)

            for conflict in self.cooked_conflicts:

                warning(conflict)

            self.pp.next_phase()

            results = self.tt.apply(no_conflicts=True)

            self.write_modified(results)

            try:

                working_tree.add_conflicts(self.cooked_conflicts)

            except UnsupportedOperation:

                pass

        finally:

            self.tt.finalize()

            self.other_tree.unlock()

            self.base_tree.unlock()

            self.this_tree.unlock()

            self.pb.clear()

    def _entries3(self):

        """Gather data about files modified between three trees.

        Return a list of tuples of file_id, changed, parents3, names3,

        executable3.  changed is a boolean indicating whether the file contents

        or kind were changed.  parents3 is a tuple of parent ids for base,

        other and this.  names3 is a tuple of names for base, other and this.

        executable3 is a tuple of execute-bit values for base, other and this.

        """

        result = []

        iterator = self.other_tree._iter_changes(self.base_tree,

                include_unchanged=True, specific_files=self.interesting_files,

                extra_trees=[self.this_tree])

        for (file_id, paths, changed, versioned, parents, names, kind,

             executable) in iterator:

            if (self.interesting_ids is not None and

                file_id not in self.interesting_ids):

                continue

            if file_id in self.this_tree.inventory:

                entry = self.this_tree.inventory[file_id]

                this_name = entry.name

                this_parent = entry.parent_id

                this_executable = entry.executable

            else:

                this_name = None

                this_parent = None

                this_executable = None

            parents3 = parents + (this_parent,)

            names3 = names + (this_name,)

            executable3 = executable + (this_executable,)

            result.append((file_id, changed, parents3, names3, executable3))

        return result

    def fix_root(self):

        try:

            self.tt.final_kind(self.tt.root)

        except NoSuchFile:

            self.tt.cancel_deletion(self.tt.root)

        if self.tt.final_file_id(self.tt.root) is None:

            self.tt.version_file(self.tt.tree_file_id(self.tt.root), 

                                 self.tt.root)

        if self.other_tree.inventory.root is None:

            return

        other_root_file_id = self.other_tree.get_root_id()

        other_root = self.tt.trans_id_file_id(other_root_file_id)

        if other_root == self.tt.root:

            return

        try:

            self.tt.final_kind(other_root)

        except NoSuchFile:

            return

        self.reparent_children(self.other_tree.inventory.root, self.tt.root)

        self.tt.cancel_creation(other_root)

        self.tt.cancel_versioning(other_root)

    def reparent_children(self, ie, target):

        for thing, child in ie.children.iteritems():

            trans_id = self.tt.trans_id_file_id(child.file_id)

            self.tt.adjust_path(self.tt.final_name(trans_id), target, trans_id)

    def write_modified(self, results):

        modified_hashes = {}

        for path in results.modified_paths:

            file_id = self.this_tree.path2id(self.this_tree.relpath(path))

            if file_id is None:

                continue

            hash = self.this_tree.get_file_sha1(file_id)

            if hash is None:

                continue

            modified_hashes[file_id] = hash

        self.this_tree.set_merge_modified(modified_hashes)

    @staticmethod

    def parent(entry, file_id):

        """Determine the parent for a file_id (used as a key method)"""

        if entry is None:

            return None

        return entry.parent_id

    @staticmethod

    def name(entry, file_id):

        """Determine the name for a file_id (used as a key method)"""

        if entry is None:

            return None

        return entry.name