~bzr-pqm/bzr/bzr.dev

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

from itertools import chain

import os

import warnings

from bzrlib import (

    debug,

    errors,

    graph as _mod_graph,

    osutils,

    patiencediff,

    registry,

    revision as _mod_revision,

    tree as _mod_tree,

    tsort,

    )

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.graph import Graph

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, is_quiet

from bzrlib.transform import (TransformPreview, TreeTransform,

                              resolve_conflicts, cook_conflicts,

                              conflict_pass, FinalPaths, create_from_tree,

                              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', revision_graph=None):

        object.__init__(self)

        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 = {}

        self._revision_graph = revision_graph

        self._base_is_ancestor = None

        self._base_is_other_ancestor = None

        self._is_criss_cross = None

        self._lca_trees = None

    @property

    def revision_graph(self):

        if self._revision_graph is None:

            self._revision_graph = self.this_branch.repository.get_graph()

        return self._revision_graph

    def _set_base_is_ancestor(self, value):

        self._base_is_ancestor = value

    def _get_base_is_ancestor(self):

        if self._base_is_ancestor is None:

            self._base_is_ancestor = self.revision_graph.is_ancestor(

                self.base_rev_id, self.this_basis)

        return self._base_is_ancestor

    base_is_ancestor = property(_get_base_is_ancestor, _set_base_is_ancestor)

    def _set_base_is_other_ancestor(self, value):

        self._base_is_other_ancestor = value

    def _get_base_is_other_ancestor(self):

        if self._base_is_other_ancestor is None:

            if self.other_basis is None:

                return True

            self._base_is_other_ancestor = self.revision_graph.is_ancestor(

                self.base_rev_id, self.other_basis)

        return self._base_is_other_ancestor

    base_is_other_ancestor = property(_get_base_is_other_ancestor,

                                      _set_base_is_other_ancestor)

    @staticmethod

    def from_uncommitted(tree, other_tree, pb, base_tree=None):

        """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

        :param base_tree: The basis to use for the merge.  If unspecified,

            other_tree.basis_tree() will be used.

        """

        if base_tree is None:

            base_tree = other_tree.basis_tree()

        merger = Merger(tree.branch, other_tree, base_tree, tree, pb)

        merger.base_rev_id = merger.base_tree.get_revision_id()

        merger.other_rev_id = None

        merger.other_basis = merger.base_rev_id

        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)

        revision_graph = tree.branch.repository.get_graph()

        if base_revision_id is not None:

            if (base_revision_id != _mod_revision.NULL_REVISION and

                revision_graph.is_ancestor(

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

                base_revision_id = None

            else:

                warning('Performing cherrypick')

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

                                         base_revision_id, revision_graph=

                                         revision_graph)

        return merger, verified

    @staticmethod

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

                          base_branch=None, revision_graph=None,

                          tree_branch=None):

        """Return a Merger for revision-ids.

        :param pb: A progress indicator

        :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, tree.branch is used.

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

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

        :param revision_graph: If you have a revision_graph precomputed, pass

            it in, otherwise it will be created for you.

        :param tree_branch: The branch associated with tree.  If not supplied,

            tree.branch will be used.

        """

        if tree_branch is None:

            tree_branch = tree.branch

        merger = Merger(tree_branch, this_tree=tree, pb=pb,

                        revision_graph=revision_graph)

        if other_branch is None:

            other_branch = tree.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

            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.NoSuchRevision:

            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.NoSuchRevision:

                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)

    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):

        revisions = [ensure_null(self.this_basis),

                     ensure_null(self.other_basis)]

        if NULL_REVISION in revisions:

            self.base_rev_id = NULL_REVISION

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

            self._is_criss_cross = False

        else:

            lcas = self.revision_graph.find_lca(revisions[0], revisions[1])

            self._is_criss_cross = False

            if len(lcas) == 0:

                self.base_rev_id = NULL_REVISION

            elif len(lcas) == 1:

                self.base_rev_id = list(lcas)[0]

            else: # len(lcas) > 1

                if len(lcas) > 2:

                    # find_unique_lca can only handle 2 nodes, so we have to

                    # start back at the beginning. It is a shame to traverse

                    # the graph again, but better than re-implementing

                    # find_unique_lca.

                    self.base_rev_id = self.revision_graph.find_unique_lca(

                                            revisions[0], revisions[1])

                else:

                    self.base_rev_id = self.revision_graph.find_unique_lca(

                                            *lcas)

                self._is_criss_cross = True

            if self.base_rev_id == NULL_REVISION:

                raise UnrelatedBranches()

            if self._is_criss_cross:

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

                        ' help criss-cross.')

                mutter('Criss-cross lcas: %r' % lcas)

                interesting_revision_ids = [self.base_rev_id]

                interesting_revision_ids.extend(lcas)

                interesting_trees = dict((t.get_revision_id(), t)

                    for t in self.this_branch.repository.revision_trees(

                        interesting_revision_ids))

                self._cached_trees.update(interesting_trees)

                self.base_tree = interesting_trees.pop(self.base_rev_id)

                sorted_lca_keys = self.revision_graph.find_merge_order(

                    revisions[0], lcas)

                self._lca_trees = [interesting_trees[key]

                                   for key in sorted_lca_keys]

            else:

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

        self.base_is_ancestor = True

        self.base_is_other_ancestor = True

        mutter('Base revid: %r' % self.base_rev_id)

    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)

    def make_merger(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,

                  'do_merge': False}

        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)

        if (not getattr(self.merge_type, 'supports_reverse_cherrypick', True)

            and not self.base_is_other_ancestor):

            raise errors.CannotReverseCherrypick()

        if self.merge_type.supports_cherrypick:

            kwargs['cherrypick'] = (not self.base_is_ancestor or

                                    not self.base_is_other_ancestor)

        if self._is_criss_cross and getattr(self.merge_type,

                                            'supports_lca_trees', False):

            kwargs['lca_trees'] = self._lca_trees

        return self.merge_type(pb=self._pb,

                               change_reporter=self.change_reporter,

                               **kwargs)

    def _do_merge_to(self, merge):

        merge.do_merge()

        if self.recurse == 'down':

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

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

                other_revision = self.other_tree.get_reference_revision(

                    file_id, relpath)

                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

                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.base_rev_id = base_revision

                sub_merge.do_merge()

    def do_merge(self):

        self.this_tree.lock_tree_write()

        try:

            if self.base_tree is not None:

                self.base_tree.lock_read()

            try:

                if self.other_tree is not None:

                    self.other_tree.lock_read()

                try:

                    merge = self.make_merger()

                    self._do_merge_to(merge)

                finally:

                    if self.other_tree is not None:

                        self.other_tree.unlock()

            finally:

                if self.base_tree is not None:

                    self.base_tree.unlock()

        finally:

            self.this_tree.unlock()

        if len(merge.cooked_conflicts) == 0:

            if not self.ignore_zero and not is_quiet():

                note("All changes applied successfully.")

        else:

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

        return len(merge.cooked_conflicts)

class _InventoryNoneEntry(object):

    """This represents an inventory entry which *isn't there*.

    It simplifies the merging logic if we always have an InventoryEntry, even

    if it isn't actually present

    """

    executable = None

    kind = None

    name = None

    parent_id = None

    revision = None

    symlink_target = None

    text_sha1 = None

_none_entry = _InventoryNoneEntry()

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

    supports_cherrypick = True

    supports_reverse_cherrypick = True

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

    supports_lca_trees = True

    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, do_merge=True,

                 cherrypick=False, lca_trees=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.

        :param lca_trees: Can be set to a dictionary of {revision_id:rev_tree}

            if the ancestry was found to include a criss-cross merge.

            Otherwise should be None.

        """

        object.__init__(self)

        if interesting_files is not None and interesting_ids is not None:

            raise ValueError(

                'specify either interesting_ids or interesting_files')

        self.interesting_ids = interesting_ids

        self.interesting_files = interesting_files

        self.this_tree = working_tree

        self.base_tree = base_tree

        self.other_tree = other_tree

        self._raw_conflicts = []

        self.cooked_conflicts = []

        self.reprocess = reprocess

        self.show_base = show_base

        self._lca_trees = lca_trees

        # Uncommenting this will change the default algorithm to always use

        # _entries_lca. This can be useful for running the test suite and

        # making sure we haven't missed any corner cases.

        # if lca_trees is None:

        #     self._lca_trees = [self.base_tree]

        self.pb = pb

        self.pp = pp

        self.change_reporter = change_reporter

        self.cherrypick = cherrypick

        if self.pp is None:

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

        if do_merge:

            self.do_merge()

    def do_merge(self):

        self.this_tree.lock_tree_write()

        self.base_tree.lock_read()

        self.other_tree.lock_read()

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

        try:

            self.pp.next_phase()

            self._compute_transform()

            self.pp.next_phase()