~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

from tempfile import mkdtemp

import warnings

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

import bzrlib.osutils

from bzrlib.osutils import rename, pathjoin, rmtree

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)

from bzrlib.versionedfile import WeaveMerge

from bzrlib import ui

# TODO: Report back as changes are merged in

def _get_tree(treespec, local_branch=None):

    location, revno = treespec

    branch = Branch.open_containing(location)[0]

    if revno is None:

        revision = None

    elif 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_pending_merge(self.other_rev_id)

    def set_other(self, other_revision):

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

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

        if base_revision == [None, None]:

            try:

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

        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 == "root_directory":

                kind = "directory"

            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)

                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

                    create_by_entry(self.tt, 

                                    self.other_tree.inventory[file_id], 

                                    self.other_tree, trans_id)

                    if file_id not in self.this_tree.inventory:

                        self.tt.version_file(file_id, trans_id)

                    return "modified"

                elif file_id in self.this_tree.inventory:

                    # OTHER deleted the file

                    self.tt.unversion_file(trans_id)

                    return "deleted"

            #BOTH THIS and OTHER introduced changes; scalar conflict

            elif this_pair[0] == "file" and other_pair[0] == "file":

                # THIS and OTHER are both files, so text merge.  Either

                # BASE is a file, or both converted to files, so at least we

                # have agreement that output should be a file.

                try:

                    self.text_merge(file_id, trans_id)

                except BinaryFile:

                    return contents_conflict()

                if file_id not in self.this_tree.inventory:

                    self.tt.version_file(file_id, trans_id)

                try:

                    self.tt.tree_kind(trans_id)

                    self.tt.delete_contents(trans_id)

                except NoSuchFile:

                    pass

                return "modified"

            else:

                # Scalar conflict, can't text merge.  Dump conflicts

                return contents_conflict()

    def get_lines(self, tree, file_id):

        """Return the lines in a file, or an empty list."""

        if file_id in tree:

            return tree.get_file(file_id).readlines()

        else:

            return []

    def text_merge(self, file_id, trans_id):

        """Perform a three-way text merge on a file_id"""