/brz/remove-bazaar

# Copyright (C) 2006, 2007 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

"""DirState objects record the state of a directory and its bzr metadata.

Pseudo EBNF grammar for the state file. Fields are separated by NULLs, and

lines by NL. The field delimiters are ommitted in the grammar, line delimiters

are not - this is done for clarity of reading. All string data is in utf8.

MINIKIND = "f" | "d" | "l" | "a" | "r";

NL = "\n";

NULL = "\0";

WHOLE_NUMBER = {digit}, digit;

BOOLEAN = "y" | "n";

REVISION_ID = a non-empty utf8 string;

dirstate format = header line, full checksum, row count, parent details,

 ghost_details, entries;

header line = "#bazaar dirstate flat format 2", NL;

full checksum = "adler32: ", ["-"], WHOLE_NUMBER, NL;

row count = "num_entries: ", digit, NL;

parent_details = WHOLE NUMBER, {REVISION_ID}* NL;

ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;

entries = {entry};

entry = entry_key, current_entry_details, {parent_entry_details};

entry_key = dirname,  basename, fileid;

current_entry_details = common_entry_details, working_entry_details;

parent_entry_details = common_entry_details, history_entry_details;

common_entry_details = MINIKIND, fingerprint, size, executable

working_entry_details = packed_stat

history_entry_details = REVISION_ID;

executable = BOOLEAN;

size = WHOLE_NUMBER;

fingerprint = a nonempty utf8 sequence with meaning defined by minikind.

Given this definition, the following is useful to know:

entry (aka row) - all the data for a given key.

entry[0]: The key (dirname, basename, fileid)

entry[0][0]: dirname

entry[0][1]: basename

entry[0][2]: fileid

entry[1]: The tree(s) data for this path and id combination.

entry[1][0]: The current tree

entry[1][1]: The second tree

For an entry for a tree, we have (using tree 0 - current tree) to demonstrate:

entry[1][0][0]: kind

entry[1][0][1]: fingerprint

entry[1][0][2]: size

entry[1][0][3]: executable

entry[1][0][4]: packed_stat

OR (for non tree-0)

entry[1][1][4]: revision_id

There may be multiple rows at the root, one per id present in the root, so the

in memory root row is now:

self._dirblocks[0] -> ('', [entry ...]),

and the entries in there are

entries[0][0]: ''

entries[0][1]: ''

entries[0][2]: file_id

entries[1][0]: The tree data for the current tree for this fileid at /

etc.

Kinds:

'r' is a relocated entry: This path is not present in this tree with this id,

    but the id can be found at another location. The fingerprint is used to

    point to the target location.

'a' is an absent entry: In that tree the id is not present at this path.

'd' is a directory entry: This path in this tree is a directory with the

    current file id. There is no fingerprint for directories.

'f' is a file entry: As for directory, but its a file. The fingerprint is a

    sha1 value.

'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the

    link target.

--- Format 1 had the following different definition: ---

rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,

    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target, 

    {PARENT ROW}

PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,

    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,

    SHA1

PARENT ROW's are emitted for every parent that is not in the ghosts details

line. That is, if the parents are foo, bar, baz, and the ghosts are bar, then

each row will have a PARENT ROW for foo and baz, but not for bar.

In any tree, a kind of 'moved' indicates that the fingerprint field

(which we treat as opaque data specific to the 'kind' anyway) has the

details for the id of this row in that tree.

I'm strongly tempted to add a id->path index as well, but I think that

where we need id->path mapping; we also usually read the whole file, so

I'm going to skip that for the moment, as we have the ability to locate

via bisect any path in any tree, and if we lookup things by path, we can

accumulate a id->path mapping as we go, which will tend to match what we

looked for.

I plan to implement this asap, so please speak up now to alter/tweak the

design - and once we stabilise on this, I'll update the wiki page for

it.

The rationale for all this is that we want fast operations for the

common case (diff/status/commit/merge on all files) and extremely fast

operations for the less common but still occurs a lot status/diff/commit

on specific files). Operations on specific files involve a scan for all

the children of a path, *in every involved tree*, which the current

format did not accommodate. 

----

Design priorities:

 1) Fast end to end use for bzr's top 5 uses cases. (commmit/diff/status/merge/???)

 2) fall back current object model as needed.

 3) scale usably to the largest trees known today - say 50K entries. (mozilla

    is an example of this)

Locking:

 Eventually reuse dirstate objects across locks IFF the dirstate file has not

 been modified, but will require that we flush/ignore cached stat-hit data

 because we wont want to restat all files on disk just because a lock was

 acquired, yet we cannot trust the data after the previous lock was released.

Memory representation:

 vector of all directories, and vector of the childen ?

   i.e. 

     root_entrie = (direntry for root, [parent_direntries_for_root]), 

     dirblocks = [

     ('', ['data for achild', 'data for bchild', 'data for cchild'])

     ('dir', ['achild', 'cchild', 'echild'])

     ]

    - single bisect to find N subtrees from a path spec

    - in-order for serialisation - this is 'dirblock' grouping.

    - insertion of a file '/a' affects only the '/' child-vector, that is, to

      insert 10K elements from scratch does not generates O(N^2) memoves of a

      single vector, rather each individual, which tends to be limited to a 

      manageable number. Will scale badly on trees with 10K entries in a 

      single directory. compare with Inventory.InventoryDirectory which has

      a dictionary for the children. No bisect capability, can only probe for

      exact matches, or grab all elements and sorta.

    - Whats the risk of error here? Once we have the base format being processed

      we should have a net win regardless of optimality. So we are going to 

      go with what seems reasonably.

open questions:

maybe we should do a test profile of these core structure - 10K simulated searches/lookups/etc?

Objects for each row?

The lifetime of Dirstate objects is current per lock, but see above for

possible extensions. The lifetime of a row from a dirstate is expected to be

very short in the optimistic case: which we are optimising for. For instance,

subtree status will determine from analysis of the disk data what rows need to

be examined at all, and will be able to determine from a single row whether

that file has altered or not, so we are aiming to process tens of thousands of

entries each second within the dirstate context, before exposing anything to

the larger codebase. This suggests we want the time for a single file

comparison to be < 0.1 milliseconds. That would give us 10000 paths per second

processed, and to scale to 100 thousand we'll another order of magnitude to do

that. Now, as the lifetime for all unchanged entries is the time to parse, stat

the file on disk, and then immediately discard, the overhead of object creation

becomes a significant cost.

Figures: Creating a tuple from from 3 elements was profiled at 0.0625

microseconds, whereas creating a object which is subclassed from tuple was

0.500 microseconds, and creating an object with 3 elements and slots was 3

microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get

down to 10 microseconds for the total processing - having 33% of that be object

creation is a huge overhead. There is a potential cost in using tuples within

each row which is that the conditional code to do comparisons may be slower

than method invocation, but method invocation is known to be slow due to stack

frame creation, so avoiding methods in these tight inner loops in unfortunately

desirable. We can consider a pyrex version of this with objects in future if

desired.

"""

import base64

import bisect

import cStringIO

import os

import sha

import struct

import zlib

from bzrlib import (

    errors,

    trace,

    )

import bzrlib.inventory

from bzrlib import osutils

from bzrlib.osutils import (

    pathjoin,

    sha_file,

    sha_string,

    walkdirs,

    )

class DirState(object):

    """Record directory and metadata state for fast access.

    A dirstate is a specialised data structure for managing local working

    tree state information. Its not yet well defined whether it is platform

    specific, and if it is how we detect/parameterise that.

    """

    _kind_to_minikind = {'absent':'a', 'file':'f', 'directory':'d', 'relocated':'r', 'symlink':'l'}

    _minikind_to_kind = {'a':'absent', 'f':'file', 'd':'directory', 'l':'symlink', 'r':'relocated'}

    _to_yesno = {True:'y', False: 'n'} # TODO profile the performance gain

     # of using int conversion rather than a dict here. AND BLAME ANDREW IF

     # it is faster.

    # TODO: jam 20070221 Make sure we handle when there are duplicated records

    #       (like when we remove + add the same path, or we have a rename)

    # TODO: jam 20070221 Figure out what to do if we have a record that exceeds

    #       the BISECT_PAGE_SIZE.

    BISECT_PAGE_SIZE = 4096

    NOT_IN_MEMORY = 0

    IN_MEMORY_UNMODIFIED = 1

    IN_MEMORY_MODIFIED = 2

    # A pack_stat (the x's) that is just noise and will never match the output

    # of base64 encode.

    NULLSTAT = 'x' * 32

    NULL_PARENT_DETAILS = ('absent', '', 0, False, '')

    def __init__(self):

        """Create a  DirState object.

        Attributes of note:

        :attr _root_entrie: The root row of the directory/file information,

            - contains the path to / - '', ''

            - kind of 'directory',

            - the file id of the root in utf8

            - size of 0

            - a packed state

            - and no sha information.

        """

        # _header_state and _dirblock_state represent the current state

        # of the dirstate metadata and the per-row data respectiely.

        # NOT_IN_MEMORY indicates that no data is in memory

        # IN_MEMORY_UNMODIFIED indicates that what we have in memory

        #   is the same as is on disk

        # IN_MEMORY_MODIFIED indicates that we have a modified version

        #   of what is on disk. 

        # In future we will add more granularity, for instance _dirblock_state

        # will probably support partially-in-memory as a separate variable,

        # allowing for partially-in-memory unmodified and partially-in-memory

        # modified states.

        self._header_state = DirState.NOT_IN_MEMORY

        self._dirblock_state = DirState.NOT_IN_MEMORY

        self._dirblocks = []

        self._ghosts = []

        self._parents = []

        self._state_file=None

    def add(self, path, file_id, kind, stat, link_or_sha1):

        """Add a path to be tracked.

        :param path: The path within the dirstate - '' is the root, 'foo' is the

            path foo within the root, 'foo/bar' is the path bar within foo 

            within the root.

        :param file_id: The file id of the path being added.

        :param kind: The kind of the path.

        :param stat: The output of os.lstate for the path.

        :param link_or_sha1: The sha value of the file, or the target of a

            symlink. '' for directories.

        """

        # adding a file:

        # find the block its in. 

        # find the location in the block.

        # check its not there

        # add it.

        #------- copied from bzrlib.inventory.make_entry

        # --- normalized_filename wants a unicode basename only, so get one.

        dirname, basename = os.path.split(path)

        # we dont import normalized_filename directly because we want to be

        # able to change the implementation at runtime for tests.

        norm_name, can_access = osutils.normalized_filename(basename)

        if norm_name != basename:

            if can_access:

                basename = norm_name

            else:

                raise errors.InvalidNormalization(path)

        # now that we've normalised, we need the correct utf8 path and 

        # dirname and basename elements. This single encode and split should be

        # faster than three separate encodes.

        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')

        dirname, basename = os.path.split(utf8path)

        entry_key = (dirname, basename, file_id.encode('utf8'))

        self._read_dirblocks_if_needed()

        block_index, present = self._find_block_index_from_key(entry_key)

        if not present:

            # TODO: This test is not complete - an empty directory, or a

            # directory for a parent tree will fool it.

            # some parent path has not been added - its an error to add this

            # child

            raise errors.NotVersionedError(path, str(self))

        block = self._dirblocks[block_index][1]

        if stat is None:

            size = 0

            packed_stat = DirState.NULLSTAT

        else:

            size = stat.st_size

            packed_stat = pack_stat(stat)

        parent_info = self._empty_parent_info()

        if kind == 'file':

            entry_data = entry_key, [

                (kind, link_or_sha1, size, False, packed_stat),

                ] + parent_info

        elif kind == 'directory':

            entry_data = entry_key, [

                (kind, '', 0, False, packed_stat),

                ] + parent_info

        elif kind == 'symlink':

            entry_data = entry_key, [

                (kind, link_or_sha1, size, False, packed_stat),

                ] + parent_info

        else:

            raise errors.BzrError('unknown kind %r' % kind)

        entry_index, present = self._find_entry_index(entry_key, block)

        assert not present, "basename %r already added" % basename

        block.insert(entry_index, entry_data)

        if kind == 'directory':

           # insert a new dirblock

           self._ensure_block(block_index, entry_index, utf8path)

        self._dirblock_state = DirState.IN_MEMORY_MODIFIED

    def _empty_parent_info(self):

        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -

                                                    len(self._ghosts))

    def _ensure_block(self, parent_block_index, parent_row_index, dirname):

        """Enssure a block for dirname exists.

        This function exists to let callers which know that there is a

        directory dirname ensure that the block for it exists. This block can

        fail to exist because of demand loading, or because a directory had no

        children. In either case it is not an error. It is however an error to

        call this if there is no parent entry for the directory, and thus the

        function requires the coordinates of such an entry to be provided.

        The root row is special cased and can be indicated with a parent block

        and row index of -1

        :param parent_block_index: The index of the block in which dirname's row

            exists.

        :param parent_row_index: The index in the parent block where the row

            exists.

        :param dirname: The utf8 dirname to ensure there is a block for.

        :return: The index for the block.

        """

        assert dirname != ''

        # the basename of the directory must be the end of its full name.

        if not (parent_block_index == -1 and

            parent_block_index == -1 and dirname == ''):

            assert dirname.endswith(

                self._dirblocks[parent_block_index][1][parent_row_index][0][1])

        block_index, present = self._find_block_index_from_key((dirname, '', ''))

        if not present:

            ## In future, when doing partial parsing, this should load and 

            # populate the entire block.

            self._dirblocks.insert(block_index, (dirname, []))

        return block_index

    def _entries_to_current_state(self, new_entries):

        """Load new_entries into self.dirblocks.

        Process new_entries into the current state object, making them the active

        state.

        :param new_entries: A sorted list of entries. This function does not sort

            to prevent unneeded overhead when callers have a sorted list already.

        :return: Nothing.

        """

        assert new_entries[0][0][0:2] == ('', ''), \

            "Missing root row %r" % new_entries[0][0]

        # The two blocks here are deliberate: the root block and the 

        # contents-of-root block.

        self._dirblocks = [('', []), ('', [])]

        current_block = self._dirblocks[0][1]

        current_dirname = ''

        root_key = ('', '')

        for entry in new_entries:

            if entry[0][0] != current_dirname:

                # new block - different dirname

                current_block = []

                current_dirname = entry[0][0]

                self._dirblocks.append((current_dirname, current_block))

            elif entry[0][1]:

                # this is not a root entry for a tree (it has a basename)

                current_block = self._dirblocks[-1][1]

            # append the entry to the current block

            current_block.append(entry)

    def _entry_to_line(self, entry):

        """Serialize entry to a NULL delimited line ready for _get_output_lines.

        :param entry: An entry_tuple as defined in the module docstring.

        """

        entire_entry = list(entry[0])

        for tree_number, tree_data in enumerate(entry[1]):

            # (kind, fingerprint, size, executable, tree_specific_string)

            entire_entry.extend(tree_data)

            # 3 for the key, 5 for the fields per tree.

            tree_offset = 3 + tree_number * 5

            # kind

            entire_entry[tree_offset + 0] = DirState._kind_to_minikind[tree_data[0]]

            # size

            entire_entry[tree_offset + 2] = str(tree_data[2])

            # executable

            entire_entry[tree_offset + 3] = DirState._to_yesno[tree_data[3]]

        return '\0'.join(entire_entry)

    def _fields_per_row(self):

        """How many null separated fields should be in each entry row.

        Each line now has an extra '\n' field which is not used

        so we just skip over it

        entry size:

            3 fields for the key

            + number of fields per tree_data (5) * tree count

            + newline

         """

        tree_count = 1 + self._num_present_parents()

        return 3 + 5 * tree_count + 1

    def _find_block(self, key, add_if_missing=False):

        """Return the block that key should be present in.

        :param key: A dirstate entry key.

        :return: The block tuple.

        """

        block_index, present = self._find_block_index_from_key(key)

        if not present:

            if not add_if_missing:

                # check to see if key is versioned itself - we might want to

                # add it anyway, because dirs with no entries dont get a

                # dirblock at parse time.

                # This is an uncommon branch to take: most dirs have children,

                # and most code works with versioned paths.

                parent_base, parent_name = os.path.split(key[0])

                if not self._get_block_entry_index(parent_base, parent_name, 0)[3]:

                    # some parent path has not been added - its an error to add

                    # this child

                    raise errors.NotVersionedError(key[0:2], str(self))

            self._dirblocks.insert(block_index, (key[0], []))

        return self._dirblocks[block_index]

    def _find_block_index_from_key(self, key):

        """Find the dirblock index for a key.

        :return: The block index, True if the block for the key is present.

        """

        if key[0:2] == ('', ''):

            return 0, True

        block_index = bisect.bisect_left(self._dirblocks, (key[0], []), 1)

        # _right returns one-past-where-key is so we have to subtract

        # one to use it. we use _right here because there are two

        # '' blocks - the root, and the contents of root

        # we always have a minimum of 2 in self._dirblocks: root and

        # root-contents, and for '', we get 2 back, so this is 

        # simple and correct:

        present = (block_index < len(self._dirblocks) and

            self._dirblocks[block_index][0] == key[0])

        return block_index, present

    def _find_entry_index(self, key, block):

        """Find the entry index for a key in a block.

        :return: The entry index, True if the entry for the key is present.

        """

        entry_index = bisect.bisect_left(block, (key, []))

        present = (entry_index < len(block) and

            block[entry_index][0] == key)

        return entry_index, present

    @staticmethod

    def from_tree(tree, dir_state_filename):

        """Create a dirstate from a bzr Tree.

        :param tree: The tree which should provide parent information and

            inventory ids.

        """

        result = DirState.initialize(dir_state_filename)

        tree.lock_read()

        parent_ids = tree.get_parent_ids()

        num_parents = len(parent_ids)

        parent_trees = []

        for parent_id in parent_ids:

            parent_trees.append((parent_id, tree.branch.repository.revision_tree(parent_id)))

            parent_trees[-1][1].lock_read()

        result.set_parent_trees(parent_trees, [])

        result.set_state_from_inventory(tree.inventory)

        for revid, parent in parent_trees:

            parent.unlock()

        tree.unlock()

        return result

    def get_ghosts(self):

        """Return a list of the parent tree revision ids that are ghosts."""

        self._read_header_if_needed()

        return self._ghosts

    def get_lines(self):

        """Serialise the entire dirstate to a sequence of lines."""

        if (self._header_state == DirState.IN_MEMORY_UNMODIFIED and

            self._dirblock_state == DirState.IN_MEMORY_UNMODIFIED):

            # read whats on disk.

            self._state_file.seek(0)

            return self._state_file.readlines()

        lines = []

        lines.append(self._get_parents_line(self.get_parent_ids()))

        lines.append(self._get_ghosts_line(self._ghosts))

        # append the root line which is special cased

        lines.extend(map(self._entry_to_line, self._iter_entries()))

        return self._get_output_lines(lines)

    def _get_ghosts_line(self, ghost_ids):

        """Create a line for the state file for ghost information."""

        return '\0'.join([str(len(ghost_ids))] + ghost_ids)

    def _get_parents_line(self, parent_ids):

        """Create a line for the state file for parents information."""

        return '\0'.join([str(len(parent_ids))] + parent_ids)

    def _get_fields_to_entry(self):

        """Get a function which converts entry fields into a entry record.

        This handles kind, size, and executable, as well as parent records.

        :return: A function which takes a list of fields, and returns an

            appropriate record for storing in memory.

        """

        # This is intentionally unrolled for performance

        num_present_parents = self._num_present_parents()

        if num_present_parents == 0:

            def fields_to_entry_0_parents(fields, _int=int, _tuple=tuple,

                                          _mini_to_kind=self._minikind_to_kind):

                path_name_file_id_key = _tuple(fields[:3])

                return (path_name_file_id_key, [

                    ( # Current tree

                        _mini_to_kind[fields[3]], # kind

                        fields[4],                # fingerprint

                        _int(fields[5]),          # size

                        fields[6] == 'y',         # executable

                        fields[7],                # packed_stat or revision_id

                    )])

            return fields_to_entry_0_parents

        elif num_present_parents == 1:

            def fields_to_entry_1_parent(fields, _int=int, _tuple=tuple,

                                         _mini_to_kind=self._minikind_to_kind):

                path_name_file_id_key = _tuple(fields[:3])

                return (path_name_file_id_key, [

                    ( # Current tree

                        _mini_to_kind[fields[3]], # kind

                        fields[4],                # fingerprint

                        _int(fields[5]),          # size

                        fields[6] == 'y',         # executable

                        fields[7],                # packed_stat or revision_id

                    ),

                    ( # Parent 1

                        _mini_to_kind[fields[8]], # kind

                        fields[9],                # fingerprint

                        _int(fields[10]),         # size

                        fields[11] == 'y',        # executable

                        fields[12],               # packed_stat or revision_id

                    ),

                    ])

            return fields_to_entry_1_parent

        elif num_present_parents == 2:

            def fields_to_entry_2_parents(fields, _int=int, _tuple=tuple,

                                          _mini_to_kind=self._minikind_to_kind):

                path_name_file_id_key = _tuple(fields[:3])

                return (path_name_file_id_key, [

                    ( # Current tree

                        _mini_to_kind[fields[3]], # kind

                        fields[4],                # fingerprint

                        _int(fields[5]),          # size

                        fields[6] == 'y',         # executable

                        fields[7],                # packed_stat or revision_id

                    ),

                    ( # Parent 1

                        _mini_to_kind[fields[8]], # kind

                        fields[9],                # fingerprint

                        _int(fields[10]),         # size

                        fields[11] == 'y',        # executable

                        fields[12],               # packed_stat or revision_id

                    ),

                    ( # Parent 2

                        _mini_to_kind[fields[13]],# kind

                        fields[14],               # fingerprint

                        _int(fields[15]),         # size

                        fields[16] == 'y',        # executable

                        fields[17],               # packed_stat or revision_id

                    ),

                    ])

            return fields_to_entry_2_parents

        else:

            def fields_to_entry_n_parents(fields, _int=int, _tuple=tuple,

                                          _mini_to_kind=self._minikind_to_kind):

                path_name_file_id_key = _tuple(fields[:3])

                trees = [(_mini_to_kind[fields[cur]], # kind

                          fields[cur+1],              # fingerprint

                          _int(fields[cur+2]),        # size

                          fields[cur+3] == 'y',       # executable

                          fields[cur+4],              # stat or revision_id

                         ) for cur in xrange(3, len(fields)-1, 5)]

                return path_name_file_id_key, trees

            return fields_to_entry_n_parents

    def get_parent_ids(self):

        """Return a list of the parent tree ids for the directory state."""

        self._read_header_if_needed()

        return list(self._parents)

    def _get_block_entry_index(self, dirname, basename, tree_index):

        """Get the coordinates for a path in the state structure.

        :param dirname: The utf8 dirname to lookup.

        :param basename: The utf8 basename to lookup.

        :param tree_index: The index of the tree for which this lookup should

            be attempted.

        :return: A tuple describing where the path is located, or should be

            inserted. The tuple contains four fields: the block index, the row

            index, anda two booleans are True when the directory is present, and

            when the entire path is present.  There is no guarantee that either

            coordinate is currently reachable unless the found field for it is

            True. For instance, a directory not present in the searched tree

            may be returned with a value one greater than the current highest

            block offset. The directory present field will always be True when

            the path present field is True. The directory present field does

            NOT indicate that the directory is present in the searched tree,

            rather it indicates that there are at least some files in some

            tree present there.

        """

        self._read_dirblocks_if_needed()

        key = dirname, basename, ''

        block_index, present = self._find_block_index_from_key(key)

        if not present:

            # no such directory - return the dir index and 0 for the row.

            return block_index, 0, False, False

        block = self._dirblocks[block_index][1] # access the entries only

        entry_index, present = self._find_entry_index(key, block)

        # linear search through present entries at this path to find the one

        # requested.

        while entry_index < len(block) and block[entry_index][0][1] == basename:

            if block[entry_index][1][tree_index][0] not in \

                       ('absent', 'relocated'):

                return block_index, entry_index, True, True

            entry_index += 1

        return block_index, entry_index, True, False

    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None):

        """Get the dirstate entry for path in tree tree_index

        If either file_id or path is supplied, it is used as the key to lookup.

        If both are supplied, the fastest lookup is used, and an error is

        raised if they do not both point at the same row.

        :param tree_index: The index of the tree we wish to locate this path

            in. If the path is present in that tree, the entry containing its

            details is returned, otherwise (None, None) is returned

        :param fileid_utf8: A utf8 file_id to look up.

        :param path_utf8: An utf8 path to be looked up.

        :return: The dirstate entry tuple for path, or (None, None)

        """

        self._read_dirblocks_if_needed()

        if path_utf8 is not None:

            assert path_utf8.__class__ == str, 'path_utf8 is not a str: %s %s' % (type(path_utf8), path_utf8)

            # path lookups are faster

            dirname, basename = os.path.split(path_utf8)

            block_index, entry_index, dir_present, file_present = \

                self._get_block_entry_index(dirname, basename, tree_index)

            if not file_present:

                return None, None

            entry = self._dirblocks[block_index][1][entry_index]

            assert entry[0][2] and entry[1][tree_index][0] not in ('absent', 'relocated'), 'unversioned entry?!?!'

            if fileid_utf8:

                if entry[0][2] != fileid_utf8:

                    raise BzrError('integrity error ? : mismatching tree_index, file_id and path')

            return entry

        else:

            for entry in self._iter_entries():

                if entry[0][2] == fileid_utf8:

                    if entry[1][tree_index][0] == 'relocated':

                        # look up the real location directly by path

                        return self._get_entry(tree_index,

                            fileid_utf8=fileid_utf8,

                            path_utf8=entry[1][tree_index][1])

                    if entry[1][tree_index][0] == 'absent':

                        # not in the tree at all.

                        return None, None

                    return entry

            return None, None

    @staticmethod

    def initialize(path):

        """Create a new dirstate on path.

        The new dirstate will be an empty tree - that is it has no parents,

        and only a root node - which has id ROOT_ID.

        :param path: The name of the file for the dirstate.

        :return: A DirState object.

        """

        # This constructs a new DirState object on a path, sets the _state_file

        # to a new empty file for that path. It then calls _set_data() with our

        # stock empty dirstate information - a root with ROOT_ID, no children,

        # and no parents. Finally it calls save() to ensure that this data will

        # persist.

        result = DirState()

        result._state_file = open(path, 'wb+')

        # root dir and root dir contents with no children.

        empty_tree_dirblocks = [('', []), ('', [])]

        # a new root directory, with a NULLSTAT.

        empty_tree_dirblocks[0][1].append(

            (('', '', bzrlib.inventory.ROOT_ID), [

                ('directory', '', 0, False, DirState.NULLSTAT),

            ]))

        result._set_data([], empty_tree_dirblocks)

        try:

            result.save()

        except:

            result._state_file.close()

            raise

        return result