~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2006-2011 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 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" | "t";

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 3", NL;

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

row count = "num_entries: ", WHOLE_NUMBER, 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]: minikind

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 it's a file. The fingerprint is the

    sha1 value of the file's canonical form, i.e. after any read filters have

    been applied to the convenience form stored in the working tree.

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

    link target.

't' is a reference to a nested subtree; the fingerprint is the referenced

    revision.

Ordering:

The entries on disk and in memory are ordered according to the following keys:

    directory, as a list of components

    filename

    file-id

--- 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 an 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 won't 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 sort.

    - What's 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 reasonable.

open questions:

Maybe we should do a test profile of the 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 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 bisect

import binascii

import errno

import operator

import os

from stat import S_IEXEC

import stat

import struct

import sys

import time

import zlib

from bzrlib import (

    cache_utf8,

    debug,

    errors,

    inventory,

    lock,

    osutils,

    static_tuple,

    trace,

    )

# This is the Windows equivalent of ENOTDIR

# It is defined in pywin32.winerror, but we don't want a strong dependency for

# just an error code.

ERROR_PATH_NOT_FOUND = 3

ERROR_DIRECTORY = 267

if not getattr(struct, '_compile', None):

    # Cannot pre-compile the dirstate pack_stat

    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):

        """Convert stat values into a packed representation."""

        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),

            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,

            st.st_mode))[:-1]

else:

    # compile the struct compiler we need, so as to only do it once

    from _struct import Struct

    _compiled_pack = Struct('>LLLLLL').pack

    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):

        """Convert stat values into a packed representation."""

        # jam 20060614 it isn't really worth removing more entries if we

        # are going to leave it in packed form.

        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms

        # With all entries, filesize is 5.9M and read time is maybe 280ms

        # well within the noise margin

        # base64 encoding always adds a final newline, so strip it off

        # The current version

        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),

            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]

        # This is 0.060s / 1.520s faster by not encoding as much information

        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]

        # This is not strictly faster than _encode(_pack())[:-1]

        # return '%X.%X.%X.%X.%X.%X' % (

        #      st.st_size, int(st.st_mtime), int(st.st_ctime),

        #      st.st_dev, st.st_ino, st.st_mode)

        # Similar to the _encode(_pack('>LL'))

        # return '%X.%X' % (int(st.st_mtime), st.st_mode)

def _unpack_stat(packed_stat):

    """Turn a packed_stat back into the stat fields.

    This is meant as a debugging tool, should not be used in real code.

    """

    (st_size, st_mtime, st_ctime, st_dev, st_ino,

     st_mode) = struct.unpack('>LLLLLL', binascii.a2b_base64(packed_stat))

    return dict(st_size=st_size, st_mtime=st_mtime, st_ctime=st_ctime,

                st_dev=st_dev, st_ino=st_ino, st_mode=st_mode)

class SHA1Provider(object):

    """An interface for getting sha1s of a file."""

    def sha1(self, abspath):

        """Return the sha1 of a file given its absolute path.

        :param abspath:  May be a filesystem encoded absolute path

             or a unicode path.

        """

        raise NotImplementedError(self.sha1)

    def stat_and_sha1(self, abspath):

        """Return the stat and sha1 of a file given its absolute path.

        :param abspath:  May be a filesystem encoded absolute path

             or a unicode path.

        Note: the stat should be the stat of the physical file

        while the sha may be the sha of its canonical content.

        """

        raise NotImplementedError(self.stat_and_sha1)

class DefaultSHA1Provider(SHA1Provider):

    """A SHA1Provider that reads directly from the filesystem."""

    def sha1(self, abspath):

        """Return the sha1 of a file given its absolute path."""

        return osutils.sha_file_by_name(abspath)

    def stat_and_sha1(self, abspath):

        """Return the stat and sha1 of a file given its absolute path."""

        file_obj = file(abspath, 'rb')

        try:

            statvalue = os.fstat(file_obj.fileno())

            sha1 = osutils.sha_file(file_obj)

        finally:

            file_obj.close()

        return statvalue, sha1

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/parameterize that.

    Dirstates use the usual lock_write, lock_read and unlock mechanisms.

    Unlike most bzr disk formats, DirStates must be locked for reading, using

    lock_read.  (This is an os file lock internally.)  This is necessary

    because the file can be rewritten in place.

    DirStates must be explicitly written with save() to commit changes; just

    unlocking them does not write the changes to disk.

    """

    _kind_to_minikind = {

            'absent': 'a',

            'file': 'f',

            'directory': 'd',

            'relocated': 'r',

            'symlink': 'l',

            'tree-reference': 't',

        }

    _minikind_to_kind = {

            'a': 'absent',

            'f': 'file',

            'd': 'directory',

            'l':'symlink',

            'r': 'relocated',

            't': 'tree-reference',

        }

    _stat_to_minikind = {

        stat.S_IFDIR:'d',

        stat.S_IFREG:'f',

        stat.S_IFLNK:'l',

    }

    _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 Figure out what to do if we have a record that exceeds

    #       the BISECT_PAGE_SIZE. For now, we just have to make it large enough

    #       that we are sure a single record will always fit.

    BISECT_PAGE_SIZE = 4096

    NOT_IN_MEMORY = 0

    IN_MEMORY_UNMODIFIED = 1

    IN_MEMORY_MODIFIED = 2

    IN_MEMORY_HASH_MODIFIED = 3 # Only hash-cache updates

    # 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 = ('a', '', 0, False, '')

    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'

    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'

    def __init__(self, path, sha1_provider, worth_saving_limit=0):

        """Create a  DirState object.

        :param path: The path at which the dirstate file on disk should live.

        :param sha1_provider: an object meeting the SHA1Provider interface.

        :param worth_saving_limit: when the exact number of hash changed

            entries is known, only bother saving the dirstate if more than

            this count of entries have changed.

            -1 means never save hash changes, 0 means always save hash changes.

        """

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

        # If true, an error has been detected while updating the dirstate, and

        # for safety we're not going to commit to disk.

        self._changes_aborted = False

        self._dirblocks = []

        self._ghosts = []

        self._parents = []

        self._state_file = None

        self._filename = path

        self._lock_token = None

        self._lock_state = None

        self._id_index = None

        # a map from packed_stat to sha's.

        self._packed_stat_index = None

        self._end_of_header = None

        self._cutoff_time = None

        self._split_path_cache = {}

        self._bisect_page_size = DirState.BISECT_PAGE_SIZE

        self._sha1_provider = sha1_provider

        if 'hashcache' in debug.debug_flags:

            self._sha1_file = self._sha1_file_and_mutter

        else:

            self._sha1_file = self._sha1_provider.sha1

        # These two attributes provide a simple cache for lookups into the

        # dirstate in-memory vectors. By probing respectively for the last

        # block, and for the next entry, we save nearly 2 bisections per path

        # during commit.

        self._last_block_index = None

        self._last_entry_index = None

        # The set of known hash changes

        self._known_hash_changes = set()

        # How many hash changed entries can we have without saving

        self._worth_saving_limit = worth_saving_limit

    def __repr__(self):

        return "%s(%r)" % \

            (self.__class__.__name__, self._filename)

    def _mark_modified(self, hash_changed_entries=None, header_modified=False):

        """Mark this dirstate as modified.

        :param hash_changed_entries: if non-None, mark just these entries as

            having their hash modified.

        :param header_modified: mark the header modified as well, not just the

            dirblocks.

        """

        #trace.mutter_callsite(3, "modified hash entries: %s", hash_changed_entries)

        if hash_changed_entries:

            self._known_hash_changes.update([e[0] for e in hash_changed_entries])

            if self._dirblock_state in (DirState.NOT_IN_MEMORY,

                                        DirState.IN_MEMORY_UNMODIFIED):

                # If the dirstate is already marked a IN_MEMORY_MODIFIED, then

                # that takes precedence.

                self._dirblock_state = DirState.IN_MEMORY_HASH_MODIFIED

        else:

            # TODO: Since we now have a IN_MEMORY_HASH_MODIFIED state, we

            #       should fail noisily if someone tries to set

            #       IN_MEMORY_MODIFIED but we don't have a write-lock!

            # We don't know exactly what changed so disable smart saving

            self._dirblock_state = DirState.IN_MEMORY_MODIFIED

        if header_modified:

            self._header_state = DirState.IN_MEMORY_MODIFIED

    def _mark_unmodified(self):

        """Mark this dirstate as unmodified."""

        self._header_state = DirState.IN_MEMORY_UNMODIFIED

        self._dirblock_state = DirState.IN_MEMORY_UNMODIFIED

        self._known_hash_changes = set()

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

        """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, as a string like 'file',

            'directory', etc.

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

        :param fingerprint: The sha value of the file's canonical form (i.e.

            after any read filters have been applied),

            or the target of a symlink,

            or the referenced revision id for tree-references,

            or '' for directories.

        """

        # adding a file:

        # find the block its in.

        # find the location in the block.

        # check its not there

        # add it.

        #------- copied from inventory.ensure_normalized_name - keep synced.

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

        dirname, basename = osutils.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)

        # you should never have files called . or ..; just add the directory

        # in the parent, or according to the special treatment for the root

        if basename == '.' or basename == '..':

            raise errors.InvalidEntryName(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 = osutils.split(utf8path)

        # uses __class__ for speed; the check is needed for safety

        if file_id.__class__ is not str:

            raise AssertionError(

                "must be a utf8 file_id not %s" % (type(file_id), ))

        # Make sure the file_id does not exist in this tree

        rename_from = None

        file_id_entry = self._get_entry(0, fileid_utf8=file_id, include_deleted=True)

        if file_id_entry != (None, None):

            if file_id_entry[1][0][0] == 'a':

                if file_id_entry[0] != (dirname, basename, file_id):

                    # set the old name's current operation to rename

                    self.update_minimal(file_id_entry[0],

                        'r',

                        path_utf8='',

                        packed_stat='',

                        fingerprint=utf8path

                    )

                    rename_from = file_id_entry[0][0:2]

            else:

                path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])

                kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]

                info = '%s:%s' % (kind, path)

                raise errors.DuplicateFileId(file_id, info)

        first_key = (dirname, basename, '')

        block_index, present = self._find_block_index_from_key(first_key)

        if present:

            # check the path is not in the tree

            block = self._dirblocks[block_index][1]

            entry_index, _ = self._find_entry_index(first_key, block)

            while (entry_index < len(block) and

                block[entry_index][0][0:2] == first_key[0:2]):

                if block[entry_index][1][0][0] not in 'ar':

                    # this path is in the dirstate in the current tree.

                    raise Exception, "adding already added path!"

                entry_index += 1

        else:

            # The block where we want to put the file is not present. But it

            # might be because the directory was empty, or not loaded yet. Look

            # for a parent entry, if not found, raise NotVersionedError

            parent_dir, parent_base = osutils.split(dirname)

            parent_block_idx, parent_entry_idx, _, parent_present = \

                self._get_block_entry_index(parent_dir, parent_base, 0)

            if not parent_present:

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

            self._ensure_block(parent_block_idx, parent_entry_idx, dirname)

        block = self._dirblocks[block_index][1]

        entry_key = (dirname, basename, file_id)

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

        minikind = DirState._kind_to_minikind[kind]

        if rename_from is not None:

            if rename_from[0]:

                old_path_utf8 = '%s/%s' % rename_from

            else:

                old_path_utf8 = rename_from[1]

            parent_info[0] = ('r', old_path_utf8, 0, False, '')

        if kind == 'file':

            entry_data = entry_key, [

                (minikind, fingerprint, size, False, packed_stat),

                ] + parent_info

        elif kind == 'directory':

            entry_data = entry_key, [

                (minikind, '', 0, False, packed_stat),

                ] + parent_info

        elif kind == 'symlink':

            entry_data = entry_key, [

                (minikind, fingerprint, size, False, packed_stat),

                ] + parent_info

        elif kind == 'tree-reference':

            entry_data = entry_key, [

                (minikind, fingerprint, 0, False, packed_stat),

                ] + parent_info

        else:

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

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

        if not present:

            block.insert(entry_index, entry_data)

        else:

            if block[entry_index][1][0][0] != 'a':

                raise AssertionError(" %r(%r) already added" % (basename, file_id))

            block[entry_index][1][0] = entry_data[1][0]

        if kind == 'directory':

           # insert a new dirblock

           self._ensure_block(block_index, entry_index, utf8path)

        self._mark_modified()

        if self._id_index:

            self._add_to_id_index(self._id_index, entry_key)

    def _bisect(self, paths):

        """Bisect through the disk structure for specific rows.

        :param paths: A list of paths to find

        :return: A dict mapping path => entries for found entries. Missing

                 entries will not be in the map.

                 The list is not sorted, and entries will be populated

                 based on when they were read.

        """

        self._requires_lock()

        # We need the file pointer to be right after the initial header block

        self._read_header_if_needed()

        # If _dirblock_state was in memory, we should just return info from

        # there, this function is only meant to handle when we want to read

        # part of the disk.

        if self._dirblock_state != DirState.NOT_IN_MEMORY:

            raise AssertionError("bad dirblock state %r" % self._dirblock_state)

        # The disk representation is generally info + '\0\n\0' at the end. But

        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'

        # Because it means we can sync on the '\n'

        state_file = self._state_file

        file_size = os.fstat(state_file.fileno()).st_size

        # We end up with 2 extra fields, we should have a trailing '\n' to

        # ensure that we read the whole record, and we should have a precursur

        # '' which ensures that we start after the previous '\n'

        entry_field_count = self._fields_per_entry() + 1

        low = self._end_of_header

        high = file_size - 1 # Ignore the final '\0'

        # Map from (dir, name) => entry

        found = {}

        # Avoid infinite seeking

        max_count = 30*len(paths)

        count = 0

        # pending is a list of places to look.

        # each entry is a tuple of low, high, dir_names

        #   low -> the first byte offset to read (inclusive)

        #   high -> the last byte offset (inclusive)

        #   dir_names -> The list of (dir, name) pairs that should be found in

        #                the [low, high] range

        pending = [(low, high, paths)]

        page_size = self._bisect_page_size

        fields_to_entry = self._get_fields_to_entry()

        while pending:

            low, high, cur_files = pending.pop()

            if not cur_files or low >= high:

                # Nothing to find

                continue

            count += 1

            if count > max_count:

                raise errors.BzrError('Too many seeks, most likely a bug.')

            mid = max(low, (low+high-page_size)/2)

            state_file.seek(mid)

            # limit the read size, so we don't end up reading data that we have

            # already read.

            read_size = min(page_size, (high-mid)+1)

            block = state_file.read(read_size)

            start = mid

            entries = block.split('\n')

            if len(entries) < 2:

                # We didn't find a '\n', so we cannot have found any records.

                # So put this range back and try again. But we know we have to

                # increase the page size, because a single read did not contain

                # a record break (so records must be larger than page_size)

                page_size *= 2

                pending.append((low, high, cur_files))

                continue

            # Check the first and last entries, in case they are partial, or if

            # we don't care about the rest of this page

            first_entry_num = 0

            first_fields = entries[0].split('\0')

            if len(first_fields) < entry_field_count:

                # We didn't get the complete first entry

                # so move start, and grab the next, which

                # should be a full entry

                start += len(entries[0])+1

                first_fields = entries[1].split('\0')

                first_entry_num = 1

            if len(first_fields) <= 2:

                # We didn't even get a filename here... what do we do?

                # Try a large page size and repeat this query

                page_size *= 2

                pending.append((low, high, cur_files))

                continue

            else:

                # Find what entries we are looking for, which occur before and

                # after this first record.

                after = start

                if first_fields[1]:

                    first_path = first_fields[1] + '/' + first_fields[2]

                else:

                    first_path = first_fields[2]

                first_loc = _bisect_path_left(cur_files, first_path)

                # These exist before the current location

                pre = cur_files[:first_loc]

                # These occur after the current location, which may be in the

                # data we read, or might be after the last entry

                post = cur_files[first_loc:]

            if post and len(first_fields) >= entry_field_count:

                # We have files after the first entry

                # Parse the last entry

                last_entry_num = len(entries)-1

                last_fields = entries[last_entry_num].split('\0')

                if len(last_fields) < entry_field_count:

                    # The very last hunk was not complete,

                    # read the previous hunk