/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]: 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 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,

    inventory,

    lock,

    osutils,

    trace,

    )

from bzrlib.osutils import (

    pathjoin,

    sha_file,

    sha_string,

    walkdirs,

    )

class _Bisector(object):

    """This just keeps track of information as we are bisecting."""

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. 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

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

        """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.

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

        """

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

        self._filename = path

        self._lock_token = None

        self._id_index = None

        self._end_of_header = None

        self._split_path_cache = {}

        self._bisect_page_size = DirState.BISECT_PAGE_SIZE

    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 inventory.make_entry

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

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

        assert file_id.__class__ == str, \

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

        # Make sure the file_id does not exist in this tree

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

        if file_id_entry != (None, None):

            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)

        entry_key = (dirname, basename, file_id)

        self._read_dirblocks_if_needed()

        block_index, present = self._find_block_index_from_key(entry_key)

        if not present:

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

        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 kind == 'file':

            entry_data = entry_key, [

                (minikind, link_or_sha1, 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, 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

        if self._id_index:

            self._id_index.setdefault(entry_key[2], set()).add(entry_key)

    def _bisect(self, dir_name_list):

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

        :param dir_name_list: A list of (dir, name) pairs.

        :return: A dict mapping (dir, name) => entry for found entries. Missing

                 entries will not be in the map.

        """

        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.

        assert self._dirblock_state == DirState.NOT_IN_MEMORY

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

        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, dir_name_list)]

        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

                first_dir_name = (first_fields[1], first_fields[2])

                first_loc = bisect.bisect_left(cur_files, first_dir_name)

                # 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

                    after = mid + len(block) - len(entries[-1])

                    last_entry_num -= 1

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

                else:

                    after = mid + len(block)

                last_dir_name = (last_fields[1], last_fields[2])

                last_loc = bisect.bisect_right(post, last_dir_name)

                middle_files = post[:last_loc]

                post = post[last_loc:]

                if middle_files:

                    # We have files that should occur in this block

                    # (>= first, <= last)

                    # Either we will find them here, or we can mark them as

                    # missing.

                    if middle_files[0] == first_dir_name:

                        # We might need to go before this location

                        pre.append(first_dir_name)

                    if middle_files[-1] == last_dir_name:

                        post.insert(0, last_dir_name)

                    # Find out what paths we have

                    paths = {first_dir_name:[first_fields]}

                    # last_dir_name might == first_dir_name so we need to be

                    # careful if we should append rather than overwrite

                    if last_entry_num != first_entry_num:

                        paths.setdefault(last_dir_name, []).append(last_fields)

                    for num in xrange(first_entry_num+1, last_entry_num):

                        # TODO: jam 20070223 We are already splitting here, so

                        #       shouldn't we just split the whole thing rather

                        #       than doing the split again in add_one_record?

                        fields = entries[num].split('\0')

                        dir_name = (fields[1], fields[2])

                        paths.setdefault(dir_name, []).append(fields)

                    for dir_name in middle_files:

                        for fields in paths.get(dir_name, []):

                            # offset by 1 because of the opening '\0'

                            # consider changing fields_to_entry to avoid the

                            # extra list slice

                            entry = fields_to_entry(fields[1:])

                            found.setdefault(dir_name, []).append(entry)

            # Now we have split up everything into pre, middle, and post, and

            # we have handled everything that fell in 'middle'.

            # We add 'post' first, so that we prefer to seek towards the

            # beginning, so that we will tend to go as early as we need, and

            # then only seek forward after that.

            if post:

                pending.append((after, high, post))

            if pre:

                pending.append((low, start-1, pre))

        # Consider that we may want to return the directory entries in sorted

        # order. For now, we just return them in whatever order we found them,

        # and leave it up to the caller if they care if it is ordered or not.

        return found

    def _bisect_dirblocks(self, dir_list):

        """Bisect through the disk structure to find entries in given dirs.

        _bisect_dirblocks is meant to find the contents of directories, which

        differs from _bisect, which only finds individual entries.

        :param dir_list: An sorted list of directory names ['', 'dir', 'foo'].

        :return: A map from dir => entries_for_dir

        """

        # TODO: jam 20070223 A lot of the bisecting logic could be shared

        #       between this and _bisect. It would require parameterizing the

        #       inner loop with a function, though. We should evaluate the

        #       performance difference.

        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.

        assert self._dirblock_state == DirState.NOT_IN_MEMORY

        # 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 => entry

        found = {}

        # Avoid infinite seeking

        max_count = 30*len(dir_list)

        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)

        #   dirs -> The list of directories that should be found in

        #                the [low, high] range

        pending = [(low, high, dir_list)]

        page_size = self._bisect_page_size

        fields_to_entry = self._get_fields_to_entry()

        while pending:

            low, high, cur_dirs = pending.pop()

            if not cur_dirs 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_dirs))

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

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

                # Try a large page size and repeat this query

                page_size *= 2

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

                continue

            else:

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

                # after this first record.

                after = start

                first_dir = first_fields[1]

                first_loc = bisect.bisect_left(cur_dirs, first_dir)

                # These exist before the current location

                pre = cur_dirs[: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_dirs[first_loc:]

            if post and len(first_fields) >= entry_field_count:

                # We have records to look at 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

                    after = mid + len(block) - len(entries[-1])

                    last_entry_num -= 1

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

                else:

                    after = mid + len(block)

                last_dir = last_fields[1]

                last_loc = bisect.bisect_right(post, last_dir)

                middle_files = post[:last_loc]

                post = post[last_loc:]

                if middle_files:

                    # We have files that should occur in this block

                    # (>= first, <= last)

                    # Either we will find them here, or we can mark them as

                    # missing.

                    if middle_files[0] == first_dir:

                        # We might need to go before this location

                        pre.append(first_dir)

                    if middle_files[-1] == last_dir:

                        post.insert(0, last_dir)

                    # Find out what paths we have

                    paths = {first_dir:[first_fields]}

                    # last_dir might == first_dir so we need to be

                    # careful if we should append rather than overwrite

                    if last_entry_num != first_entry_num:

                        paths.setdefault(last_dir, []).append(last_fields)

                    for num in xrange(first_entry_num+1, last_entry_num):

                        # TODO: jam 20070223 We are already splitting here, so

                        #       shouldn't we just split the whole thing rather

                        #       than doing the split again in add_one_record?

                        fields = entries[num].split('\0')

                        paths.setdefault(fields[1], []).append(fields)

                    for cur_dir in middle_files:

                        for fields in paths.get(cur_dir, []):

                            # offset by 1 because of the opening '\0'

                            # consider changing fields_to_entry to avoid the

                            # extra list slice

                            entry = fields_to_entry(fields[1:])

                            found.setdefault(cur_dir, []).append(entry)

            # Now we have split up everything into pre, middle, and post, and

            # we have handled everything that fell in 'middle'.

            # We add 'post' first, so that we prefer to seek towards the

            # beginning, so that we will tend to go as early as we need, and

            # then only seek forward after that.

            if post:

                pending.append((after, high, post))

            if pre:

                pending.append((low, start-1, pre))

        return found

    def _bisect_recursive(self, dir_name_list):

        """Bisect for entries for all paths and their children.

        This will use bisect to find all records for the supplied paths. It

        will then continue to bisect for any records which are marked as

        directories. (and renames?)

        :param paths: A sorted list of (dir, name) pairs

             eg: [('', 'a'), ('', 'f'), ('a/b', 'c')]

        :return: A dictionary mapping (dir, name, file_id) => [tree_info]

        """

        # Map from (dir, name, file_id) => [tree_info]

        found = {}

        found_dir_names = set()

        # Directories that have been read

        processed_dirs = set()

        # Get the ball rolling with the first bisect for all entries.

        newly_found = self._bisect(dir_name_list)

        while newly_found:

            # Directories that need to be read

            pending_dirs = set()

            paths_to_search = set()

            for entry_list in newly_found.itervalues():

                for dir_name_id, trees_info in entry_list:

                    found[dir_name_id] = trees_info

                    found_dir_names.add(dir_name_id[:2])

                    is_dir = False

                    for tree_info in trees_info:

                        minikind = tree_info[0]

                        if minikind == 'd':

                            if is_dir:

                                # We already processed this one as a directory,

                                # we don't need to do the extra work again.

                                continue

                            subdir, name, file_id = dir_name_id

                            path = osutils.pathjoin(subdir, name)

                            is_dir = True

                            if path not in processed_dirs:

                                pending_dirs.add(path)

                        elif minikind == 'r':

                            # Rename, we need to directly search the target

                            # which is contained in the fingerprint column

                            dir_name = osutils.split(tree_info[1])