~bzr-pqm/bzr/bzr.dev

#! /usr/bin/python

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

# Author: Martin Pool <mbp@canonical.com>

"""Weave - storage of related text file versions"""

# XXX: If we do weaves this way, will a merge still behave the same

# way if it's done in a different order?  That's a pretty desirable

# property.

# TODO: Nothing here so far assumes the lines are really \n newlines,

# rather than being split up in some other way.  We could accommodate

# binaries, perhaps by naively splitting on \n or perhaps using

# something like a rolling checksum.

# TODO: End marker for each version so we can stop reading?

# TODO: Check that no insertion occurs inside a deletion that was

# active in the version of the insertion.

# TODO: In addition to the SHA-1 check, perhaps have some code that

# checks structural constraints of the weave: ie that insertions are

# properly nested, that there is no text outside of an insertion, that

# insertions or deletions are not repeated, etc.

# TODO: Parallel-extract that passes back each line along with a

# description of which revisions include it.  Nice for checking all

# shas or calculating stats in parallel.

# TODO: Using a single _extract routine and then processing the output

# is probably inefficient.  It's simple enough that we can afford to

# have slight specializations for different ways its used: annotate,

# basis for add, get, etc.

# TODO: Probably the API should work only in names to hide the integer

# indexes from the user.

# TODO: Is there any potential performance win by having an add()

# variant that is passed a pre-cooked version of the single basis

# version?

# TODO: Reweave can possibly be made faster by remembering diffs

# where the basis and destination are unchanged.

# FIXME: Sometimes we will be given a parents list for a revision

# that includes some redundant parents (i.e. already a parent of 

# something in the list.)  We should eliminate them.  This can 

# be done fairly efficiently because the sequence numbers constrain

# the possible relationships.

# FIXME: the conflict markers should be *7* characters

from copy import copy

from cStringIO import StringIO

import os

import sha

import time

import warnings

from bzrlib import (

    progress,

    )

from bzrlib.trace import mutter

from bzrlib.errors import (WeaveError, WeaveFormatError, WeaveParentMismatch,

        RevisionAlreadyPresent,

        RevisionNotPresent,

        WeaveRevisionAlreadyPresent,

        WeaveRevisionNotPresent,

        )

import bzrlib.errors as errors

from bzrlib.osutils import sha_strings

import bzrlib.patiencediff

from bzrlib.symbol_versioning import (deprecated_method,

        deprecated_function,

        zero_eight,

        )

from bzrlib.tsort import topo_sort

from bzrlib.versionedfile import VersionedFile, InterVersionedFile

from bzrlib.weavefile import _read_weave_v5, write_weave_v5

class Weave(VersionedFile):

    """weave - versioned text file storage.

    A Weave manages versions of line-based text files, keeping track

    of the originating version for each line.

    To clients the "lines" of the file are represented as a list of strings.

    These strings  will typically have terminal newline characters, but

    this is not required.  In particular files commonly do not have a newline

    at the end of the file.

    Texts can be identified in either of two ways:

    * a nonnegative index number.

    * a version-id string.

    Typically the index number will be valid only inside this weave and

    the version-id is used to reference it in the larger world.

    The weave is represented as a list mixing edit instructions and

    literal text.  Each entry in _weave can be either a string (or

    unicode), or a tuple.  If a string, it means that the given line

    should be output in the currently active revisions.

    If a tuple, it gives a processing instruction saying in which

    revisions the enclosed lines are active.  The tuple has the form

    (instruction, version).

    The instruction can be '{' or '}' for an insertion block, and '['

    and ']' for a deletion block respectively.  The version is the

    integer version index.  There is no replace operator, only deletes

    and inserts.  For '}', the end of an insertion, there is no

    version parameter because it always closes the most recently

    opened insertion.

    Constraints/notes:

    * A later version can delete lines that were introduced by any

      number of ancestor versions; this implies that deletion

      instructions can span insertion blocks without regard to the

      insertion block's nesting.

    * Similarly, deletions need not be properly nested with regard to

      each other, because they might have been generated by

      independent revisions.

    * Insertions are always made by inserting a new bracketed block

      into a single point in the previous weave.  This implies they

      can nest but not overlap, and the nesting must always have later

      insertions on the inside.

    * It doesn't seem very useful to have an active insertion

      inside an inactive insertion, but it might happen.

    * Therefore, all instructions are always"considered"; that

      is passed onto and off the stack.  An outer inactive block

      doesn't disable an inner block.

    * Lines are enabled if the most recent enclosing insertion is

      active and none of the enclosing deletions are active.

    * There is no point having a deletion directly inside its own

      insertion; you might as well just not write it.  And there

      should be no way to get an earlier version deleting a later

      version.

    _weave

        Text of the weave; list of control instruction tuples and strings.

    _parents

        List of parents, indexed by version number.

        It is only necessary to store the minimal set of parents for

        each version; the parent's parents are implied.

    _sha1s

        List of hex SHA-1 of each version.

    _names

        List of symbolic names for each version.  Each should be unique.

    _name_map

        For each name, the version number.

    _weave_name

        Descriptive name of this weave; typically the filename if known.

        Set by read_weave.

    """

    __slots__ = ['_weave', '_parents', '_sha1s', '_names', '_name_map',

                 '_weave_name', '_matcher']

    def __init__(self, weave_name=None, access_mode='w', matcher=None):

        super(Weave, self).__init__(access_mode)

        self._weave = []

        self._parents = []

        self._sha1s = []

        self._names = []

        self._name_map = {}

        self._weave_name = weave_name

        if matcher is None:

            self._matcher = bzrlib.patiencediff.PatienceSequenceMatcher

        else:

            self._matcher = matcher

    def __repr__(self):

        return "Weave(%r)" % self._weave_name

    def copy(self):

        """Return a deep copy of self.

        The copy can be modified without affecting the original weave."""

        other = Weave()

        other._weave = self._weave[:]

        other._parents = self._parents[:]

        other._sha1s = self._sha1s[:]

        other._names = self._names[:]

        other._name_map = self._name_map.copy()

        other._weave_name = self._weave_name

        return other

    def __eq__(self, other):

        if not isinstance(other, Weave):

            return False

        return self._parents == other._parents \

               and self._weave == other._weave \

               and self._sha1s == other._sha1s 

    def __ne__(self, other):

        return not self.__eq__(other)

    @deprecated_method(zero_eight)

    def idx_to_name(self, index):

        """Old public interface, the public interface is all names now."""

        return index

    def _idx_to_name(self, version):

        return self._names[version]

    @deprecated_method(zero_eight)

    def lookup(self, name):

        """Backwards compatibility thunk:

        Return name, as name is valid in the api now, and spew deprecation

        warnings everywhere.

        """

        return name

    def _lookup(self, name):

        """Convert symbolic version name to index."""

        try:

            return self._name_map[name]

        except KeyError:

            raise RevisionNotPresent(name, self._weave_name)

    @deprecated_method(zero_eight)

    def iter_names(self):

        """Deprecated convenience function, please see VersionedFile.names()."""

        return iter(self.names())

    @deprecated_method(zero_eight)

    def names(self):

        """See Weave.versions for the current api."""

        return self.versions()

    def versions(self):

        """See VersionedFile.versions."""

        return self._names[:]

    def has_version(self, version_id):

        """See VersionedFile.has_version."""

        return (version_id in self._name_map)

    __contains__ = has_version

    def get_delta(self, version_id):

        """See VersionedFile.get_delta."""

        return self.get_deltas([version_id])[version_id]

    def get_deltas(self, version_ids):

        """See VersionedFile.get_deltas."""

        version_ids = self.get_ancestry(version_ids)

        for version_id in version_ids:

            if not self.has_version(version_id):

                raise RevisionNotPresent(version_id, self)

        # try extracting all versions; parallel extraction is used

        nv = self.num_versions()

        sha1s = {}

        deltas = {}

        texts = {}

        inclusions = {}

        noeols = {}

        last_parent_lines = {}

        parents = {}

        parent_inclusions = {}

        parent_linenums = {}

        parent_noeols = {}

        current_hunks = {}

        diff_hunks = {}

        # its simplest to generate a full set of prepared variables.

        for i in range(nv):

            name = self._names[i]

            sha1s[name] = self.get_sha1(name)

            parents_list = self.get_parents(name)

            try:

                parent = parents_list[0]

                parents[name] = parent

                parent_inclusions[name] = inclusions[parent]

            except IndexError:

                parents[name] = None

                parent_inclusions[name] = set()

            # we want to emit start, finish, replacement_length, replacement_lines tuples.

            diff_hunks[name] = []

            current_hunks[name] = [0, 0, 0, []] # #start, finish, repl_length, repl_tuples

            parent_linenums[name] = 0

            noeols[name] = False

            parent_noeols[name] = False

            last_parent_lines[name] = None

            new_inc = set([name])

            for p in self._parents[i]:

                new_inc.update(inclusions[self._idx_to_name(p)])

            # debug only, known good so far.

            #assert set(new_inc) == set(self.get_ancestry(name)), \

            #    'failed %s != %s' % (set(new_inc), set(self.get_ancestry(name)))

            inclusions[name] = new_inc

        nlines = len(self._weave)

        for lineno, inserted, deletes, line in self._walk_internal():

            # a line is active in a version if:

            # insert is in the versions inclusions

            # and

            # deleteset & the versions inclusions is an empty set.

            # so - if we have a included by mapping - version is included by

            # children, we get a list of children to examine for deletes affect

            # ing them, which is less than the entire set of children.

            for version_id in version_ids:  

                # The active inclusion must be an ancestor,

                # and no ancestors must have deleted this line,

                # because we don't support resurrection.

                parent_inclusion = parent_inclusions[version_id]

                inclusion = inclusions[version_id]

                parent_active = inserted in parent_inclusion and not (deletes & parent_inclusion)

                version_active = inserted in inclusion and not (deletes & inclusion)

                if not parent_active and not version_active:

                    # unrelated line of ancestry

                    continue

                elif parent_active and version_active:

                    # shared line

                    parent_linenum = parent_linenums[version_id]

                    if current_hunks[version_id] != [parent_linenum, parent_linenum, 0, []]:

                        diff_hunks[version_id].append(tuple(current_hunks[version_id]))

                    parent_linenum += 1

                    current_hunks[version_id] = [parent_linenum, parent_linenum, 0, []]

                    parent_linenums[version_id] = parent_linenum

                    try:

                        if line[-1] != '\n':

                            noeols[version_id] = True

                    except IndexError:

                        pass

                elif parent_active and not version_active:

                    # deleted line

                    current_hunks[version_id][1] += 1

                    parent_linenums[version_id] += 1

                    last_parent_lines[version_id] = line

                elif not parent_active and version_active:

                    # replacement line

                    # noeol only occurs at the end of a file because we 

                    # diff linewise. We want to show noeol changes as a

                    # empty diff unless the actual eol-less content changed.

                    theline = line

                    try:

                        if last_parent_lines[version_id][-1] != '\n':

                            parent_noeols[version_id] = True

                    except (TypeError, IndexError):

                        pass

                    try:

                        if theline[-1] != '\n':

                            noeols[version_id] = True

                    except IndexError:

                        pass

                    new_line = False

                    parent_should_go = False

                    if parent_noeols[version_id] == noeols[version_id]:

                        # no noeol toggle, so trust the weaves statement

                        # that this line is changed.

                        new_line = True

                        if parent_noeols[version_id]:

                            theline = theline + '\n'

                    elif parent_noeols[version_id]:

                        # parent has no eol, we do:

                        # our line is new, report as such..

                        new_line = True

                    elif noeols[version_id]:

                        # append a eol so that it looks like

                        # a normalised delta

                        theline = theline + '\n'

                        if parents[version_id] is not None:

                        #if last_parent_lines[version_id] is not None:

                            parent_should_go = True

                        if last_parent_lines[version_id] != theline:

                            # but changed anyway

                            new_line = True

                            #parent_should_go = False

                    if new_line:

                        current_hunks[version_id][2] += 1

                        current_hunks[version_id][3].append((inserted, theline))

                    if parent_should_go:

                        # last hunk last parent line is not eaten

                        current_hunks[version_id][1] -= 1

                    if current_hunks[version_id][1] < 0:

                        current_hunks[version_id][1] = 0

                        # import pdb;pdb.set_trace()

                    # assert current_hunks[version_id][1] >= 0

        # flush last hunk

        for i in range(nv):

            version = self._idx_to_name(i)

            if current_hunks[version] != [0, 0, 0, []]:

                diff_hunks[version].append(tuple(current_hunks[version]))

        result = {}

        for version_id in version_ids:

            result[version_id] = (

                                  parents[version_id],

                                  sha1s[version_id],

                                  noeols[version_id],

                                  diff_hunks[version_id],

                                  )

        return result

    def get_parents(self, version_id):

        """See VersionedFile.get_parent."""

        return map(self._idx_to_name, self._parents[self._lookup(version_id)])

    def _check_repeated_add(self, name, parents, text, sha1):

        """Check that a duplicated add is OK.

        If it is, return the (old) index; otherwise raise an exception.

        """

        idx = self._lookup(name)

        if sorted(self._parents[idx]) != sorted(parents) \

            or sha1 != self._sha1s[idx]:

            raise RevisionAlreadyPresent(name, self._weave_name)

        return idx

    @deprecated_method(zero_eight)

    def add_identical(self, old_rev_id, new_rev_id, parents):

        """Please use Weave.clone_text now."""

        return self.clone_text(new_rev_id, old_rev_id, parents)

    def _add_lines(self, version_id, parents, lines, parent_texts):

        """See VersionedFile.add_lines."""

        return self._add(version_id, lines, map(self._lookup, parents))

    @deprecated_method(zero_eight)

    def add(self, name, parents, text, sha1=None):

        """See VersionedFile.add_lines for the non deprecated api."""

        return self._add(name, text, map(self._maybe_lookup, parents), sha1)

    def _add(self, version_id, lines, parents, sha1=None):

        """Add a single text on top of the weave.

        Returns the index number of the newly added version.

        version_id

            Symbolic name for this version.

            (Typically the revision-id of the revision that added it.)

        parents

            List or set of direct parent version numbers.

        lines

            Sequence of lines to be added in the new version.

        """

        assert isinstance(version_id, basestring)

        self._check_lines_not_unicode(lines)

        self._check_lines_are_lines(lines)

        if not sha1:

            sha1 = sha_strings(lines)

        if version_id in self._name_map:

            return self._check_repeated_add(version_id, parents, lines, sha1)

        self._check_versions(parents)

        ## self._check_lines(lines)

        new_version = len(self._parents)

        # if we abort after here the (in-memory) weave will be corrupt because only

        # some fields are updated

        # XXX: FIXME implement a succeed-or-fail of the rest of this routine.

        #      - Robert Collins 20060226

        self._parents.append(parents[:])

        self._sha1s.append(sha1)

        self._names.append(version_id)

        self._name_map[version_id] = new_version

        if not parents:

            # special case; adding with no parents revision; can do

            # this more quickly by just appending unconditionally.

            # even more specially, if we're adding an empty text we

            # need do nothing at all.

            if lines:

                self._weave.append(('{', new_version))

                self._weave.extend(lines)

                self._weave.append(('}', None))

            return new_version

        if len(parents) == 1:

            pv = list(parents)[0]

            if sha1 == self._sha1s[pv]:

                # special case: same as the single parent

                return new_version

        ancestors = self._inclusions(parents)

        l = self._weave

        # basis a list of (origin, lineno, line)

        basis_lineno = []

        basis_lines = []

        for origin, lineno, line in self._extract(ancestors):

            basis_lineno.append(lineno)

            basis_lines.append(line)

        # another small special case: a merge, producing the same text

        # as auto-merge

        if lines == basis_lines:

            return new_version            

        # add a sentinel, because we can also match against the final line

        basis_lineno.append(len(self._weave))

        # XXX: which line of the weave should we really consider

        # matches the end of the file?  the current code says it's the

        # last line of the weave?

        #print 'basis_lines:', basis_lines

        #print 'new_lines:  ', lines

        s = self._matcher(None, basis_lines, lines)

        # offset gives the number of lines that have been inserted

        # into the weave up to the current point; if the original edit instruction

        # says to change line A then we actually change (A+offset)

        offset = 0

        for tag, i1, i2, j1, j2 in s.get_opcodes():

            # i1,i2 are given in offsets within basis_lines; we need to map them

            # back to offsets within the entire weave

            #print 'raw match', tag, i1, i2, j1, j2

            if tag == 'equal':

                continue

            i1 = basis_lineno[i1]

            i2 = basis_lineno[i2]

            assert 0 <= j1 <= j2 <= len(lines)

            #print tag, i1, i2, j1, j2

            # the deletion and insertion are handled separately.

            # first delete the region.

            if i1 != i2:

                self._weave.insert(i1+offset, ('[', new_version))

                self._weave.insert(i2+offset+1, (']', new_version))

                offset += 2

            if j1 != j2:

                # there may have been a deletion spanning up to

                # i2; we want to insert after this region to make sure

                # we don't destroy ourselves

                i = i2 + offset

                self._weave[i:i] = ([('{', new_version)] 

                                    + lines[j1:j2] 

                                    + [('}', None)])

                offset += 2 + (j2 - j1)

        return new_version

    def _clone_text(self, new_version_id, old_version_id, parents):

        """See VersionedFile.clone_text."""

        old_lines = self.get_text(old_version_id)

        self.add_lines(new_version_id, parents, old_lines)

    def _inclusions(self, versions):

        """Return set of all ancestors of given version(s)."""

        if not len(versions):

            return []

        i = set(versions)

        for v in xrange(max(versions), 0, -1):

            if v in i:

                # include all its parents

                i.update(self._parents[v])

        return i

        ## except IndexError:

        ##     raise ValueError("version %d not present in weave" % v)

    @deprecated_method(zero_eight)

    def inclusions(self, version_ids):

        """Deprecated - see VersionedFile.get_ancestry for the replacement."""

        if not version_ids:

            return []

        if isinstance(version_ids[0], int):

            return [self._idx_to_name(v) for v in self._inclusions(version_ids)]

        else:

            return self.get_ancestry(version_ids)

    def get_ancestry(self, version_ids):

        """See VersionedFile.get_ancestry."""

        if isinstance(version_ids, basestring):

            version_ids = [version_ids]

        i = self._inclusions([self._lookup(v) for v in version_ids])

        return [self._idx_to_name(v) for v in i]

    def _check_lines(self, text):

        if not isinstance(text, list):

            raise ValueError("text should be a list, not %s" % type(text))

        for l in text:

            if not isinstance(l, basestring):

                raise ValueError("text line should be a string or unicode, not %s"

                                 % type(l))

    def _check_versions(self, indexes):

        """Check everything in the sequence of indexes is valid"""

        for i in indexes:

            try:

                self._parents[i]

            except IndexError:

                raise IndexError("invalid version number %r" % i)

    def _compatible_parents(self, my_parents, other_parents):

        """During join check that other_parents are joinable with my_parents.

        Joinable is defined as 'is a subset of' - supersets may require 

        regeneration of diffs, but subsets do not.

        """

        return len(other_parents.difference(my_parents)) == 0

    def annotate(self, version_id):

        if isinstance(version_id, int):

            warnings.warn('Weave.annotate(int) is deprecated. Please use version names'

                 ' in all circumstances as of 0.8',

                 DeprecationWarning,

                 stacklevel=2

                 )

            result = []

            for origin, lineno, text in self._extract([version_id]):

                result.append((origin, text))

            return result

        else:

            return super(Weave, self).annotate(version_id)

    def annotate_iter(self, version_id):

        """Yield list of (version-id, line) pairs for the specified version.

        The index indicates when the line originated in the weave."""

        incls = [self._lookup(version_id)]

        for origin, lineno, text in self._extract(incls):

            yield self._idx_to_name(origin), text

    @deprecated_method(zero_eight)

    def _walk(self):

        """_walk has become visit, a supported api."""

        return self._walk_internal()

    def iter_lines_added_or_present_in_versions(self, version_ids=None,

                                                pb=None):

        """See VersionedFile.iter_lines_added_or_present_in_versions()."""

        if version_ids is None:

            version_ids = self.versions()

        version_ids = set(version_ids)

        for lineno, inserted, deletes, line in self._walk_internal(version_ids):

            # if inserted not in version_ids then it was inserted before the

            # versions we care about, but because weaves cannot represent ghosts

            # properly, we do not filter down to that

            # if inserted not in version_ids: continue

            if line[-1] != '\n':

                yield line + '\n'

            else:

                yield line

    #@deprecated_method(zero_eight)

    def walk(self, version_ids=None):

        """See VersionedFile.walk."""

        return self._walk_internal(version_ids)

    def _walk_internal(self, version_ids=None):

        """Helper method for weave actions."""

        istack = []

        dset = set()

        lineno = 0         # line of weave, 0-based

        for l in self._weave:

            if l.__class__ == tuple:

                c, v = l

                isactive = None

                if c == '{':

                    istack.append(self._names[v])

                elif c == '}':

                    istack.pop()

                elif c == '[':

                    assert self._names[v] not in dset

                    dset.add(self._names[v])

                elif c == ']':

                    dset.remove(self._names[v])