~bzr-pqm/bzr/bzr.dev

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

"""Inventories map files to their name in a revision."""

# TODO: Maybe store inventory_id in the file?  Not really needed.

__copyright__ = "Copyright (C) 2005 Canonical Ltd."
__author__ = "Martin Pool <mbp@canonical.com>"

import sys, os.path, types, re
from sets import Set

try:
    from cElementTree import Element, ElementTree, SubElement
except ImportError:
    from elementtree.ElementTree import Element, ElementTree, SubElement

from xml import XMLMixin
from errors import bailout

import bzrlib
from bzrlib.osutils import uuid, quotefn, splitpath, joinpath, appendpath
from bzrlib.trace import mutter

class InventoryEntry(XMLMixin):
    """Description of a versioned file.

    An InventoryEntry has the following fields, which are also
    present in the XML inventory-entry element:

    * *file_id*
    * *name*: (only the basename within the directory, must not
      contain slashes)
    * *kind*: "directory" or "file"
    * *directory_id*: (if absent/null means the branch root directory)
    * *text_sha1*: only for files
    * *text_size*: in bytes, only for files 
    * *text_id*: identifier for the text version, only for files

    InventoryEntries can also exist inside a WorkingTree
    inventory, in which case they are not yet bound to a
    particular revision of the file.  In that case the text_sha1,
    text_size and text_id are absent.


    >>> i = Inventory()
    >>> i.path2id('')
    >>> i.add(InventoryEntry('123', 'src', kind='directory'))
    >>> i.add(InventoryEntry('2323', 'hello.c', parent_id='123'))
    >>> for j in i.iter_entries():
    ...   print j
    ... 
    ('src', InventoryEntry('123', 'src', kind='directory', parent_id=None))
    ('src/hello.c', InventoryEntry('2323', 'hello.c', kind='file', parent_id='123'))
    >>> i.add(InventoryEntry('2323', 'bye.c', parent_id='123'))
    Traceback (most recent call last):
    ...
    BzrError: ('inventory already contains entry with id {2323}', [])
    >>> i.add(InventoryEntry('2324', 'bye.c', parent_id='123'))
    >>> i.add(InventoryEntry('2325', 'wibble', parent_id='123', kind='directory'))
    >>> i.path2id('src/wibble')
    '2325'
    >>> '2325' in i
    True
    >>> i.add(InventoryEntry('2326', 'wibble.c', parent_id='2325'))
    >>> i['2326']
    InventoryEntry('2326', 'wibble.c', kind='file', parent_id='2325')
    >>> for j in i.iter_entries():
    ...     print j[0]
    ...     assert i.path2id(j[0])
    ... 
    src
    src/bye.c
    src/hello.c
    src/wibble
    src/wibble/wibble.c
    >>> i.id2path('2326')
    'src/wibble/wibble.c'

    :todo: Maybe also keep the full path of the entry, and the children?
           But those depend on its position within a particular inventory, and
           it would be nice not to need to hold the backpointer here.
    """
    def __init__(self, file_id, name, kind='file', text_id=None,
                 parent_id=None):
        """Create an InventoryEntry
        
        The filename must be a single component, relative to the
        parent directory; it cannot be a whole path or relative name.

        >>> e = InventoryEntry('123', 'hello.c')
        >>> e.name
        'hello.c'
        >>> e.file_id
        '123'
        >>> e = InventoryEntry('123', 'src/hello.c')
        Traceback (most recent call last):
        BzrError: ("InventoryEntry name is not a simple filename: 'src/hello.c'", [])
        """
        
        if len(splitpath(name)) != 1:
            bailout('InventoryEntry name is not a simple filename: %r'
                    % name)
        
        self.file_id = file_id
        self.name = name
        assert kind in ['file', 'directory']
        self.kind = kind
        self.text_id = text_id
        self.parent_id = parent_id
        self.text_sha1 = None
        self.text_size = None
        if kind == 'directory':
            self.children = {}


    def sorted_children(self):
        l = self.children.items()
        l.sort()
        return l


    def copy(self):
        other = InventoryEntry(self.file_id, self.name, self.kind,
                               self.text_id, self.parent_id)
        other.text_sha1 = self.text_sha1
        other.text_size = self.text_size
        return other


    def __repr__(self):
        return ("%s(%r, %r, kind=%r, parent_id=%r)"
                % (self.__class__.__name__,
                   self.file_id,
                   self.name,
                   self.kind,
                   self.parent_id))

    
    def to_element(self):
        """Convert to XML element"""
        e = Element('entry')

        e.set('name', self.name)
        e.set('file_id', self.file_id)
        e.set('kind', self.kind)

        if self.text_size is not None:
            e.set('text_size', '%d' % self.text_size)
            
        for f in ['text_id', 'text_sha1', 'parent_id']:
            v = getattr(self, f)
            if v is not None:
                e.set(f, v)

        e.tail = '\n'
            
        return e


    def from_element(cls, elt):
        assert elt.tag == 'entry'
        self = cls(elt.get('file_id'), elt.get('name'), elt.get('kind'))
        self.text_id = elt.get('text_id')
        self.text_sha1 = elt.get('text_sha1')
        self.parent_id = elt.get('parent_id')
        
        ## mutter("read inventoryentry: %r" % (elt.attrib))

        v = elt.get('text_size')
        self.text_size = v and int(v)

        return self
            

    from_element = classmethod(from_element)

    def __cmp__(self, other):
        if self is other:
            return 0
        if not isinstance(other, InventoryEntry):
            return NotImplemented

        return cmp(self.file_id, other.file_id) \
               or cmp(self.name, other.name) \
               or cmp(self.text_sha1, other.text_sha1) \
               or cmp(self.text_size, other.text_size) \
               or cmp(self.text_id, other.text_id) \
               or cmp(self.parent_id, other.parent_id) \
               or cmp(self.kind, other.kind)



class RootEntry(InventoryEntry):
    def __init__(self, file_id):
        self.file_id = file_id
        self.children = {}
        self.kind = 'root_directory'
        self.parent_id = None
        self.name = ''

    def __cmp__(self, other):
        if self is other:
            return 0
        if not isinstance(other, RootEntry):
            return NotImplemented
        return cmp(self.file_id, other.file_id) \
               or cmp(self.children, other.children)



class Inventory(XMLMixin):
    """Inventory of versioned files in a tree.

    An Inventory acts like a set of InventoryEntry items.  You can
    also look files up by their file_id or name.
    
    May be read from and written to a metadata file in a tree.  To
    manipulate the inventory (for example to add a file), it is read
    in, modified, and then written back out.

    The inventory represents a typical unix file tree, with
    directories containing files and subdirectories.  We never store
    the full path to a file, because renaming a directory implicitly
    moves all of its contents.  This class internally maintains a
    lookup tree that allows the children under a directory to be
    returned quickly.

    InventoryEntry objects must not be modified after they are
    inserted, other than through the Inventory API.

    >>> inv = Inventory()
    >>> inv.write_xml(sys.stdout)
    <inventory>
    </inventory>
    >>> inv.add(InventoryEntry('123-123', 'hello.c'))
    >>> inv['123-123'].name
    'hello.c'

    May be treated as an iterator or set to look up file ids:
    
    >>> bool(inv.path2id('hello.c'))
    True
    >>> '123-123' in inv
    True

    May also look up by name:

    >>> [x[0] for x in inv.iter_entries()]
    ['hello.c']
    
    >>> inv.write_xml(sys.stdout)
    <inventory>
    <entry file_id="123-123" kind="file" name="hello.c" />
    </inventory>

    """

    ## TODO: Make sure only canonical filenames are stored.

    ## TODO: Do something sensible about the possible collisions on
    ## case-losing filesystems.  Perhaps we should just always forbid
    ## such collisions.

    ## TODO: No special cases for root, rather just give it a file id
    ## like everything else.

    ## TODO: Probably change XML serialization to use nesting

    def __init__(self):
        """Create or read an inventory.

        If a working directory is specified, the inventory is read
        from there.  If the file is specified, read from that. If not,
        the inventory is created empty.

        The inventory is created with a default root directory, with
        an id of None.
        """
        self.root = RootEntry(None)
        self._byid = {None: self.root}


    def __iter__(self):
        return iter(self._byid)


    def __len__(self):
        """Returns number of entries."""
        return len(self._byid)


    def iter_entries(self, from_dir=None):
        """Return (path, entry) pairs, in order by name."""
        if from_dir == None:
            assert self.root
            from_dir = self.root
        elif isinstance(from_dir, basestring):
            from_dir = self._byid[from_dir]
            
        kids = from_dir.children.items()
        kids.sort()
        for name, ie in kids:
            yield name, ie
            if ie.kind == 'directory':
                for cn, cie in self.iter_entries(from_dir=ie.file_id):
                    yield '/'.join((name, cn)), cie
                    


    def directories(self, from_dir=None):
        """Return (path, entry) pairs for all directories.
        """
        def descend(parent_ie):
            parent_name = parent_ie.name
            yield parent_name, parent_ie

            # directory children in sorted order
            dn = []
            for ie in parent_ie.children.itervalues():
                if ie.kind == 'directory':
                    dn.append((ie.name, ie))
            dn.sort()
            
            for name, child_ie in dn:
                for sub_name, sub_ie in descend(child_ie):
                    yield appendpath(parent_name, sub_name), sub_ie

        for name, ie in descend(self.root):
            yield name, ie
        


    def __contains__(self, file_id):
        """True if this entry contains a file with given id.

        >>> inv = Inventory()
        >>> inv.add(InventoryEntry('123', 'foo.c'))
        >>> '123' in inv
        True
        >>> '456' in inv
        False
        """
        return file_id in self._byid


    def __getitem__(self, file_id):
        """Return the entry for given file_id.

        >>> inv = Inventory()
        >>> inv.add(InventoryEntry('123123', 'hello.c'))
        >>> inv['123123'].name
        'hello.c'
        """
        return self._byid[file_id]


    def get_child(self, parent_id, filename):
        return self[parent_id].children.get(filename)


    def add(self, entry):
        """Add entry to inventory.

        To add  a file to a branch ready to be committed, use Branch.add,
        which calls this."""
        if entry.file_id in self._byid:
            bailout("inventory already contains entry with id {%s}" % entry.file_id)

        try:
            parent = self._byid[entry.parent_id]
        except KeyError:
            bailout("parent_id %r not in inventory" % entry.parent_id)

        if parent.children.has_key(entry.name):
            bailout("%s is already versioned" %
                    appendpath(self.id2path(parent.file_id), entry.name))

        self._byid[entry.file_id] = entry
        parent.children[entry.name] = entry


    def add_path(self, relpath, kind, file_id=None):
        """Add entry from a path.

        The immediate parent must already be versioned"""
        parts = bzrlib.osutils.splitpath(relpath)
        if len(parts) == 0:
            bailout("cannot re-add root of inventory")

        if file_id is None:
            file_id = bzrlib.branch.gen_file_id(relpath)

        parent_id = self.path2id(parts[:-1])
        ie = InventoryEntry(file_id, parts[-1],
                            kind=kind, parent_id=parent_id)
        return self.add(ie)


    def __delitem__(self, file_id):
        """Remove entry by id.

        >>> inv = Inventory()
        >>> inv.add(InventoryEntry('123', 'foo.c'))
        >>> '123' in inv
        True
        >>> del inv['123']
        >>> '123' in inv
        False
        """
        ie = self[file_id]

        assert self[ie.parent_id].children[ie.name] == ie
        
        # TODO: Test deleting all children; maybe hoist to a separate
        # deltree method?
        if ie.kind == 'directory':
            for cie in ie.children.values():
                del self[cie.file_id]
            del ie.children

        del self._byid[file_id]
        del self[ie.parent_id].children[ie.name]


    def id_set(self):
        return Set(self._byid)


    def to_element(self):
        """Convert to XML Element"""
        e = Element('inventory')
        e.text = '\n'
        for path, ie in self.iter_entries():
            e.append(ie.to_element())
        return e
    

    def from_element(cls, elt):
        """Construct from XML Element

        >>> inv = Inventory()
        >>> inv.add(InventoryEntry('foo.c-123981239', 'foo.c'))
        >>> elt = inv.to_element()
        >>> inv2 = Inventory.from_element(elt)
        >>> inv2 == inv
        True
        """
        assert elt.tag == 'inventory'
        o = cls()
        for e in elt:
            o.add(InventoryEntry.from_element(e))
        return o
        
    from_element = classmethod(from_element)


    def __cmp__(self, other):
        """Compare two sets by comparing their contents.

        >>> i1 = Inventory()
        >>> i2 = Inventory()
        >>> i1 == i2
        True
        >>> i1.add(InventoryEntry('123', 'foo'))
        >>> i1 == i2
        False
        >>> i2.add(InventoryEntry('123', 'foo'))
        >>> i1 == i2
        True
        """
        if self is other:
            return 0
        
        if not isinstance(other, Inventory):
            return NotImplemented

        if self.id_set() ^ other.id_set():
            return 1

        for file_id in self._byid:
            c = cmp(self[file_id], other[file_id])
            if c: return c

        return 0


    def id2path(self, file_id):
        """Return as a list the path to file_id."""
        p = []
        while file_id != None:
            ie = self._byid[file_id]
            p.insert(0, ie.name)
            file_id = ie.parent_id
        return '/'.join(p)
            


    def path2id(self, name):
        """Walk down through directories to return entry of last component.

        names may be either a list of path components, or a single
        string, in which case it is automatically split.

        This returns the entry of the last component in the path,
        which may be either a file or a directory.
        """
        if isinstance(name, types.StringTypes):
            name = splitpath(name)

        parent = self[None]
        for f in name:
            try:
                cie = parent.children[f]
                assert cie.name == f
                parent = cie
            except KeyError:
                # or raise an error?
                return None

        return parent.file_id


    def has_filename(self, names):
        return bool(self.path2id(names))


    def has_id(self, file_id):
        return self._byid.has_key(file_id)


    def rename(self, file_id, new_parent_id, new_name):
        """Move a file within the inventory.

        This can change either the name, or the parent, or both.

        This does not move the working file."""
        if not is_valid_name(new_name):
            bailout("not an acceptable filename: %r" % new_name)

        new_parent = self._byid[new_parent_id]
        if new_name in new_parent.children:
            bailout("%r already exists in %r" % (new_name, self.id2path(new_parent_id)))

        file_ie = self._byid[file_id]
        old_parent = self._byid[file_ie.parent_id]

        # TODO: Don't leave things messed up if this fails

        del old_parent.children[file_ie.name]
        new_parent.children[new_name] = file_ie
        
        file_ie.name = new_name
        file_ie.parent_id = new_parent_id




_NAME_RE = re.compile(r'^[^/\\]+$')

def is_valid_name(name):
    return bool(_NAME_RE.match(name))



if __name__ == '__main__':
    import doctest, inventory
    doctest.testmod(inventory)