~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 (

    osutils,

    )

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 common_ancestor, is_ancestor, NULL_REVISION

from bzrlib.textfile import check_text_lines

from bzrlib.trace import mutter, warning, note

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

                              FinalPaths, create_by_entry, unique_add,

                              ROOT_PARENT)

from bzrlib.versionedfile import WeaveMerge

from bzrlib import ui

# TODO: Report back as changes are merged in

def _get_tree(treespec, local_branch=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)[0]

    if revno == -1:

        revision = branch.last_revision()

    else:

        revision = branch.get_rev_id(revno)

        if revision is None:

            revision = NULL_REVISION

    return branch, _get_revid_tree(branch, revision, local_branch)

def _get_revid_tree(branch, revision, local_branch):

    if revision is None:

        base_tree = branch.bzrdir.open_workingtree()

    else:

        if local_branch is not None:

            if local_branch.base != branch.base:

                local_branch.fetch(branch, revision)

            base_tree = local_branch.repository.revision_tree(revision)

        else:

            base_tree = branch.repository.revision_tree(revision)

    return base_tree

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

        object.__init__(self)

        assert this_tree is not None, "this_tree is required"

        self.this_branch = this_branch

        self.this_basis = 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.base_tree = base_tree

        self.ignore_zero = False

        self.backup_files = False

        self.interesting_ids = None

        self.show_base = False

        self.reprocess = False

        self._pb = pb 

        self.pp = None

    def revision_tree(self, revision_id):

        return self.this_branch.repository.revision_tree(revision_id)

    def ensure_revision_trees(self):

        if self.this_revision_tree is None:

            self.this_basis_tree = self.this_branch.repository.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")

        if check_clean:

            self.compare_basis()

            if self.this_basis != self.this_rev_id:

                raise BzrCommandError("Working tree has uncommitted changes.")

    def compare_basis(self):

        changes = self.this_tree.changes_from(self.this_tree.basis_tree())

        if not changes.has_changed():

            self.this_rev_id = self.this_basis

    def set_interesting_files(self, file_list):

        try:

            self._set_interesting_files(file_list)

        except NotVersionedError, e:

            raise BzrCommandError("%s is not a source file in any"

                                      " tree." % e.path)

    def _set_interesting_files(self, file_list):

        """Set the list of interesting ids from a list of files."""

        if file_list is None:

            self.interesting_ids = None

            return

        interesting_ids = set()

        for path in file_list:

            found_id = False

            for tree in (self.this_tree, self.base_tree, self.other_tree):

                file_id = tree.inventory.path2id(path)

                if file_id is not None:

                    interesting_ids.add(file_id)

                    found_id = True

            if not found_id:

                raise NotVersionedError(path=path)

        self.interesting_ids = interesting_ids

    def set_pending(self):

        if not self.base_is_ancestor:

            return

        if self.other_rev_id is None:

            return

        ancestry = self.this_branch.repository.get_ancestry(self.this_basis)

        if self.other_rev_id in ancestry:

            return

        self.this_tree.add_parent_tree((self.other_rev_id, self.other_tree))

    def set_other(self, other_revision):

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

        """

        other_branch, self.other_tree = _get_tree(other_revision,

                                                  self.this_branch)

        if other_revision[1] == -1:

            self.other_rev_id = other_branch.last_revision()

            if self.other_rev_id is None:

                raise NoCommits(other_branch)

            self.other_basis = self.other_rev_id

        elif other_revision[1] is not None:

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

            self.other_basis = self.other_rev_id

        else:

            self.other_rev_id = None

            self.other_basis = other_branch.last_revision()

            if self.other_basis is None:

                raise NoCommits(other_branch)

        if other_branch.base != self.this_branch.base:

            self.this_branch.fetch(other_branch, last_revision=self.other_basis)

    def find_base(self):

        self.set_base([None, None])

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

            try:

                pb = ui.ui_factory.nested_progress_bar()

                try:

                    this_repo = self.this_branch.repository

                    self.base_rev_id = common_ancestor(self.this_basis, 

                                                       self.other_basis, 

                                                       this_repo, pb)

                finally:

                    pb.finished()

            except NoCommonAncestor:

                raise UnrelatedBranches()

            self.base_tree = _get_revid_tree(self.this_branch, self.base_rev_id,

                                            None)

            self.base_is_ancestor = True

        else:

            base_branch, self.base_tree = _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 = None

            else:

                self.base_rev_id = base_branch.get_rev_id(base_revision[1])

            if self.this_branch.base != base_branch.base:

                self.this_branch.fetch(base_branch)

            self.base_is_ancestor = is_ancestor(self.this_basis, 

                                                self.base_rev_id,

                                                self.this_branch)

    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,

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

        merge = self.merge_type(pb=self._pb, **kwargs)

        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)

    def regen_inventory(self, new_entries):

        old_entries = self.this_tree.read_working_inventory()

        new_inventory = {}

        by_path = {}

        new_entries_map = {} 

        for path, file_id in new_entries:

            if path is None:

                continue

            new_entries_map[file_id] = path

        def id2path(file_id):

            path = new_entries_map.get(file_id)

            if path is not None:

                return path

            entry = old_entries[file_id]

            if entry.parent_id is None:

                return entry.name

            return pathjoin(id2path(entry.parent_id), entry.name)

        for file_id in old_entries:

            entry = old_entries[file_id]

            path = id2path(file_id)

            if file_id in self.base_tree.inventory:

                executable = getattr(self.base_tree.inventory[file_id], 'executable', False)

            else:

                executable = getattr(entry, 'executable', False)

            new_inventory[file_id] = (path, file_id, entry.parent_id, 

                                      entry.kind, executable)

            by_path[path] = file_id

        deletions = 0

        insertions = 0

        new_path_list = []

        for path, file_id in new_entries:

            if path is None:

                del new_inventory[file_id]

                deletions += 1

            else:

                new_path_list.append((path, file_id))

                if file_id not in old_entries:

                    insertions += 1

        # Ensure no file is added before its parent

        new_path_list.sort()

        for path, file_id in new_path_list:

            if path == '':

                parent = None

            else:

                parent = by_path[os.path.dirname(path)]

            abspath = pathjoin(self.this_tree.basedir, path)

            kind = osutils.file_kind(abspath)

            if file_id in self.base_tree.inventory:

                executable = getattr(self.base_tree.inventory[file_id], 'executable', False)

            else:

                executable = False

            new_inventory[file_id] = (path, file_id, parent, kind, executable)

            by_path[path] = file_id 

        # Get a list in insertion order

        new_inventory_list = new_inventory.values()

        mutter ("""Inventory regeneration:

    old length: %i insertions: %i deletions: %i new_length: %i"""\

            % (len(old_entries), insertions, deletions, 

               len(new_inventory_list)))

        assert len(new_inventory_list) == len(old_entries) + insertions\

            - deletions

        new_inventory_list.sort()

        return new_inventory_list

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

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

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

                 pb=DummyProgress(), pp=None):

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

        object.__init__(self)

        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.pb = pb

        self.pp = pp

        if self.pp is None:

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

        if interesting_ids is not None:

            all_ids = interesting_ids

        else:

            all_ids = set(base_tree)

            all_ids.update(other_tree)

        working_tree.lock_tree_write()

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

        try:

            self.pp.next_phase()

            child_pb = ui.ui_factory.nested_progress_bar()

            try:

                for num, file_id in enumerate(all_ids):

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

                    self.merge_names(file_id)

                    file_status = self.merge_contents(file_id)

                    self.merge_executable(file_id, 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)

            finally:

                child_pb.finished()

            self.cook_conflicts(fs_conflicts)

            for conflict in self.cooked_conflicts:

                warning(conflict)

            self.pp.next_phase()

            results = self.tt.apply()

            self.write_modified(results)

            try:

                working_tree.add_conflicts(self.cooked_conflicts)

            except UnsupportedOperation:

                pass

        finally:

            self.tt.finalize()

            working_tree.unlock()

            self.pb.clear()

    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.inventory.root.file_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

    @staticmethod

    def contents_sha1(tree, file_id):

        """Determine the sha1 of the file contents (used as a key method)."""

        if file_id not in tree:

            return None

        return tree.get_file_sha1(file_id)

    @staticmethod

    def executable(tree, file_id):

        """Determine the executability of a file-id (used as a key method)."""

        if file_id not in tree:

            return None

        if tree.kind(file_id) != "file":

            return False

        return tree.is_executable(file_id)

    @staticmethod

    def kind(tree, file_id):

        """Determine the kind of a file-id (used as a key method)."""

        if file_id not in tree:

            return None

        return tree.kind(file_id)

    @staticmethod

    def scalar_three_way(this_tree, base_tree, other_tree, file_id, key):

        """Do a three-way test on a scalar.

        Return "this", "other" or "conflict", depending whether a value wins.

        """

        key_base = key(base_tree, file_id)

        key_other = key(other_tree, file_id)

        #if base == other, either they all agree, or only THIS has changed.

        if key_base == key_other:

            return "this"

        key_this = key(this_tree, file_id)

        if key_this not in (key_base, key_other):

            return "conflict"

        # "Ambiguous clean merge"

        elif key_this == key_other:

            return "this"

        else:

            assert key_this == key_base

            return "other"

    def merge_names(self, file_id):

        """Perform a merge on file_id names and parents"""

        def get_entry(tree):

            if file_id in tree.inventory:

                return tree.inventory[file_id]

            else:

                return None

        this_entry = get_entry(self.this_tree)

        other_entry = get_entry(self.other_tree)

        base_entry = get_entry(self.base_tree)

        name_winner = self.scalar_three_way(this_entry, base_entry, 

                                            other_entry, file_id, self.name)

        parent_id_winner = self.scalar_three_way(this_entry, base_entry, 

                                                 other_entry, file_id, 

                                                 self.parent)

        if this_entry is None:

            if name_winner == "this":

                name_winner = "other"

            if parent_id_winner == "this":

                parent_id_winner = "other"

        if name_winner == "this" and parent_id_winner == "this":

            return

        if name_winner == "conflict":

            trans_id = self.tt.trans_id_file_id(file_id)

            self._raw_conflicts.append(('name conflict', trans_id, 

                                        self.name(this_entry, file_id), 

                                        self.name(other_entry, file_id)))

        if parent_id_winner == "conflict":

            trans_id = self.tt.trans_id_file_id(file_id)

            self._raw_conflicts.append(('parent conflict', trans_id, 

                                        self.parent(this_entry, file_id), 

                                        self.parent(other_entry, file_id)))

        if other_entry is None:

            # it doesn't matter whether the result was 'other' or 

            # 'conflict'-- if there's no 'other', we leave it alone.

            return

        # if we get here, name_winner and parent_winner are set to safe values.

        winner_entry = {"this": this_entry, "other": other_entry, 

                        "conflict": other_entry}

        trans_id = self.tt.trans_id_file_id(file_id)

        parent_id = winner_entry[parent_id_winner].parent_id

        if parent_id is not None:

            parent_trans_id = self.tt.trans_id_file_id(parent_id)

            self.tt.adjust_path(winner_entry[name_winner].name, 

                                parent_trans_id, trans_id)

    def merge_contents(self, file_id):

        """Performa a merge on file_id contents."""

        def contents_pair(tree):

            if file_id not in tree:

                return (None, None)

            kind = tree.kind(file_id)

            if kind == "file":

                contents = tree.get_file_sha1(file_id)

            elif kind == "symlink":

                contents = tree.get_symlink_target(file_id)

            else:

                contents = None

            return kind, contents

        def contents_conflict():

            trans_id = self.tt.trans_id_file_id(file_id)

            name = self.tt.final_name(trans_id)

            parent_id = self.tt.final_parent(trans_id)

            if file_id in self.this_tree.inventory:

                self.tt.unversion_file(trans_id)

                if file_id in self.this_tree:

                    self.tt.delete_contents(trans_id)

            file_group = self._dump_conflicts(name, parent_id, file_id, 

                                              set_version=True)

            self._raw_conflicts.append(('contents conflict', file_group))

        # See SPOT run.  run, SPOT, run.

        # So we're not QUITE repeating ourselves; we do tricky things with

        # file kind...

        base_pair = contents_pair(self.base_tree)

        other_pair = contents_pair(self.other_tree)

        if base_pair == other_pair:

            # OTHER introduced no changes

            return "unmodified"

        this_pair = contents_pair(self.this_tree)

        if this_pair == other_pair:

            # THIS and OTHER introduced the same changes

            return "unmodified"

        else:

            trans_id = self.tt.trans_id_file_id(file_id)

            if this_pair == base_pair:

                # only OTHER introduced changes

                if file_id in self.this_tree:

                    # Remove any existing contents

                    self.tt.delete_contents(trans_id)

                if file_id in self.other_tree:

                    # OTHER changed the file