~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Robert Collins
  • Date: 2010-04-08 04:34:03 UTC
  • mfrom: (5138 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5139.
  • Revision ID: robertc@robertcollins.net-20100408043403-56z0d07vdqrx7f3t
Update bugfix for 528114 to trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006, 2007 Canonical Ltd
 
1
# Copyright (C) 2006-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
"""DirState objects record the state of a directory and its bzr metadata.
18
18
 
29
29
 
30
30
dirstate format = header line, full checksum, row count, parent details,
31
31
 ghost_details, entries;
32
 
header line = "#bazaar dirstate flat format 2", NL;
 
32
header line = "#bazaar dirstate flat format 3", NL;
33
33
full checksum = "crc32: ", ["-"], WHOLE_NUMBER, NL;
34
 
row count = "num_entries: ", digit, NL;
 
34
row count = "num_entries: ", WHOLE_NUMBER, NL;
35
35
parent_details = WHOLE NUMBER, {REVISION_ID}* NL;
36
36
ghost_details = WHOLE NUMBER, {REVISION_ID}*, NL;
37
37
entries = {entry};
82
82
'a' is an absent entry: In that tree the id is not present at this path.
83
83
'd' is a directory entry: This path in this tree is a directory with the
84
84
    current file id. There is no fingerprint for directories.
85
 
'f' is a file entry: As for directory, but its a file. The fingerprint is a
86
 
    sha1 value.
 
85
'f' is a file entry: As for directory, but it's a file. The fingerprint is the
 
86
    sha1 value of the file's canonical form, i.e. after any read filters have
 
87
    been applied to the convenience form stored in the working tree.
87
88
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
88
89
    link target.
89
90
't' is a reference to a nested subtree; the fingerprint is the referenced
99
100
 
100
101
--- Format 1 had the following different definition: ---
101
102
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
102
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target, 
 
103
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
103
104
    {PARENT ROW}
104
105
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
105
106
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
118
119
where we need id->path mapping; we also usually read the whole file, so
119
120
I'm going to skip that for the moment, as we have the ability to locate
120
121
via bisect any path in any tree, and if we lookup things by path, we can
121
 
accumulate a id->path mapping as we go, which will tend to match what we
 
122
accumulate an id->path mapping as we go, which will tend to match what we
122
123
looked for.
123
124
 
124
125
I plan to implement this asap, so please speak up now to alter/tweak the
130
131
operations for the less common but still occurs a lot status/diff/commit
131
132
on specific files). Operations on specific files involve a scan for all
132
133
the children of a path, *in every involved tree*, which the current
133
 
format did not accommodate. 
 
134
format did not accommodate.
134
135
----
135
136
 
136
137
Design priorities:
143
144
Locking:
144
145
 Eventually reuse dirstate objects across locks IFF the dirstate file has not
145
146
 been modified, but will require that we flush/ignore cached stat-hit data
146
 
 because we wont want to restat all files on disk just because a lock was
 
147
 because we won't want to restat all files on disk just because a lock was
147
148
 acquired, yet we cannot trust the data after the previous lock was released.
148
149
 
149
150
Memory representation:
150
151
 vector of all directories, and vector of the childen ?
151
 
   i.e. 
152
 
     root_entrie = (direntry for root, [parent_direntries_for_root]), 
 
152
   i.e.
 
153
     root_entrie = (direntry for root, [parent_direntries_for_root]),
153
154
     dirblocks = [
154
155
     ('', ['data for achild', 'data for bchild', 'data for cchild'])
155
156
     ('dir', ['achild', 'cchild', 'echild'])
158
159
    - in-order for serialisation - this is 'dirblock' grouping.
159
160
    - insertion of a file '/a' affects only the '/' child-vector, that is, to
160
161
      insert 10K elements from scratch does not generates O(N^2) memoves of a
161
 
      single vector, rather each individual, which tends to be limited to a 
162
 
      manageable number. Will scale badly on trees with 10K entries in a 
 
162
      single vector, rather each individual, which tends to be limited to a
 
163
      manageable number. Will scale badly on trees with 10K entries in a
163
164
      single directory. compare with Inventory.InventoryDirectory which has
164
165
      a dictionary for the children. No bisect capability, can only probe for
165
 
      exact matches, or grab all elements and sorta.
166
 
    - Whats the risk of error here? Once we have the base format being processed
167
 
      we should have a net win regardless of optimality. So we are going to 
168
 
      go with what seems reasonably.
 
166
      exact matches, or grab all elements and sort.
 
167
    - What's the risk of error here? Once we have the base format being processed
 
168
      we should have a net win regardless of optimality. So we are going to
 
169
      go with what seems reasonable.
169
170
open questions:
170
171
 
171
 
maybe we should do a test profile of these core structure - 10K simulated searches/lookups/etc?
 
172
Maybe we should do a test profile of the core structure - 10K simulated
 
173
searches/lookups/etc?
172
174
 
173
175
Objects for each row?
174
176
The lifetime of Dirstate objects is current per lock, but see above for
185
187
the file on disk, and then immediately discard, the overhead of object creation
186
188
becomes a significant cost.
187
189
 
188
 
Figures: Creating a tuple from from 3 elements was profiled at 0.0625
 
190
Figures: Creating a tuple from 3 elements was profiled at 0.0625
189
191
microseconds, whereas creating a object which is subclassed from tuple was
190
192
0.500 microseconds, and creating an object with 3 elements and slots was 3
191
193
microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get
202
204
import bisect
203
205
import binascii
204
206
import errno
 
207
import operator
205
208
import os
206
209
from stat import S_IEXEC
207
210
import stat
211
214
import zlib
212
215
 
213
216
from bzrlib import (
 
217
    cache_utf8,
 
218
    debug,
214
219
    errors,
215
220
    inventory,
216
221
    lock,
219
224
    )
220
225
 
221
226
 
222
 
def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
223
 
    """Convert stat values into a packed representation."""
224
 
    # jam 20060614 it isn't really worth removing more entries if we
225
 
    # are going to leave it in packed form.
226
 
    # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
227
 
    # With all entries filesize is 5.9M and read time is mabye 280ms
228
 
    # well within the noise margin
229
 
 
230
 
    # base64 encoding always adds a final newline, so strip it off
231
 
    # The current version
232
 
    return _encode(_pack('>LLLLLL'
233
 
        , st.st_size, int(st.st_mtime), int(st.st_ctime)
234
 
        , st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
235
 
    # This is 0.060s / 1.520s faster by not encoding as much information
236
 
    # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
237
 
    # This is not strictly faster than _encode(_pack())[:-1]
238
 
    # return '%X.%X.%X.%X.%X.%X' % (
239
 
    #      st.st_size, int(st.st_mtime), int(st.st_ctime),
240
 
    #      st.st_dev, st.st_ino, st.st_mode)
241
 
    # Similar to the _encode(_pack('>LL'))
242
 
    # return '%X.%X' % (int(st.st_mtime), st.st_mode)
 
227
# This is the Windows equivalent of ENOTDIR
 
228
# It is defined in pywin32.winerror, but we don't want a strong dependency for
 
229
# just an error code.
 
230
ERROR_PATH_NOT_FOUND = 3
 
231
ERROR_DIRECTORY = 267
 
232
 
 
233
 
 
234
if not getattr(struct, '_compile', None):
 
235
    # Cannot pre-compile the dirstate pack_stat
 
236
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
 
237
        """Convert stat values into a packed representation."""
 
238
        return _encode(_pack('>LLLLLL', st.st_size, int(st.st_mtime),
 
239
            int(st.st_ctime), st.st_dev, st.st_ino & 0xFFFFFFFF,
 
240
            st.st_mode))[:-1]
 
241
else:
 
242
    # compile the struct compiler we need, so as to only do it once
 
243
    from _struct import Struct
 
244
    _compiled_pack = Struct('>LLLLLL').pack
 
245
    def pack_stat(st, _encode=binascii.b2a_base64, _pack=_compiled_pack):
 
246
        """Convert stat values into a packed representation."""
 
247
        # jam 20060614 it isn't really worth removing more entries if we
 
248
        # are going to leave it in packed form.
 
249
        # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
 
250
        # With all entries, filesize is 5.9M and read time is maybe 280ms
 
251
        # well within the noise margin
 
252
 
 
253
        # base64 encoding always adds a final newline, so strip it off
 
254
        # The current version
 
255
        return _encode(_pack(st.st_size, int(st.st_mtime), int(st.st_ctime),
 
256
            st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
257
        # This is 0.060s / 1.520s faster by not encoding as much information
 
258
        # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
 
259
        # This is not strictly faster than _encode(_pack())[:-1]
 
260
        # return '%X.%X.%X.%X.%X.%X' % (
 
261
        #      st.st_size, int(st.st_mtime), int(st.st_ctime),
 
262
        #      st.st_dev, st.st_ino, st.st_mode)
 
263
        # Similar to the _encode(_pack('>LL'))
 
264
        # return '%X.%X' % (int(st.st_mtime), st.st_mode)
 
265
 
 
266
 
 
267
class SHA1Provider(object):
 
268
    """An interface for getting sha1s of a file."""
 
269
 
 
270
    def sha1(self, abspath):
 
271
        """Return the sha1 of a file given its absolute path.
 
272
 
 
273
        :param abspath:  May be a filesystem encoded absolute path
 
274
             or a unicode path.
 
275
        """
 
276
        raise NotImplementedError(self.sha1)
 
277
 
 
278
    def stat_and_sha1(self, abspath):
 
279
        """Return the stat and sha1 of a file given its absolute path.
 
280
        
 
281
        :param abspath:  May be a filesystem encoded absolute path
 
282
             or a unicode path.
 
283
 
 
284
        Note: the stat should be the stat of the physical file
 
285
        while the sha may be the sha of its canonical content.
 
286
        """
 
287
        raise NotImplementedError(self.stat_and_sha1)
 
288
 
 
289
 
 
290
class DefaultSHA1Provider(SHA1Provider):
 
291
    """A SHA1Provider that reads directly from the filesystem."""
 
292
 
 
293
    def sha1(self, abspath):
 
294
        """Return the sha1 of a file given its absolute path."""
 
295
        return osutils.sha_file_by_name(abspath)
 
296
 
 
297
    def stat_and_sha1(self, abspath):
 
298
        """Return the stat and sha1 of a file given its absolute path."""
 
299
        file_obj = file(abspath, 'rb')
 
300
        try:
 
301
            statvalue = os.fstat(file_obj.fileno())
 
302
            sha1 = osutils.sha_file(file_obj)
 
303
        finally:
 
304
            file_obj.close()
 
305
        return statvalue, sha1
243
306
 
244
307
 
245
308
class DirState(object):
247
310
 
248
311
    A dirstate is a specialised data structure for managing local working
249
312
    tree state information. Its not yet well defined whether it is platform
250
 
    specific, and if it is how we detect/parameterise that.
 
313
    specific, and if it is how we detect/parameterize that.
251
314
 
252
315
    Dirstates use the usual lock_write, lock_read and unlock mechanisms.
253
316
    Unlike most bzr disk formats, DirStates must be locked for reading, using
300
363
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
301
364
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
302
365
 
303
 
    def __init__(self, path):
 
366
    def __init__(self, path, sha1_provider):
304
367
        """Create a  DirState object.
305
368
 
306
 
        Attributes of note:
307
 
 
308
 
        :attr _root_entrie: The root row of the directory/file information,
309
 
            - contains the path to / - '', ''
310
 
            - kind of 'directory',
311
 
            - the file id of the root in utf8
312
 
            - size of 0
313
 
            - a packed state
314
 
            - and no sha information.
315
369
        :param path: The path at which the dirstate file on disk should live.
 
370
        :param sha1_provider: an object meeting the SHA1Provider interface.
316
371
        """
317
372
        # _header_state and _dirblock_state represent the current state
318
373
        # of the dirstate metadata and the per-row data respectiely.
320
375
        # IN_MEMORY_UNMODIFIED indicates that what we have in memory
321
376
        #   is the same as is on disk
322
377
        # IN_MEMORY_MODIFIED indicates that we have a modified version
323
 
        #   of what is on disk. 
 
378
        #   of what is on disk.
324
379
        # In future we will add more granularity, for instance _dirblock_state
325
380
        # will probably support partially-in-memory as a separate variable,
326
381
        # allowing for partially-in-memory unmodified and partially-in-memory
327
382
        # modified states.
328
383
        self._header_state = DirState.NOT_IN_MEMORY
329
384
        self._dirblock_state = DirState.NOT_IN_MEMORY
 
385
        # If true, an error has been detected while updating the dirstate, and
 
386
        # for safety we're not going to commit to disk.
 
387
        self._changes_aborted = False
330
388
        self._dirblocks = []
331
389
        self._ghosts = []
332
390
        self._parents = []
335
393
        self._lock_token = None
336
394
        self._lock_state = None
337
395
        self._id_index = None
 
396
        # a map from packed_stat to sha's.
 
397
        self._packed_stat_index = None
338
398
        self._end_of_header = None
339
399
        self._cutoff_time = None
340
400
        self._split_path_cache = {}
341
401
        self._bisect_page_size = DirState.BISECT_PAGE_SIZE
 
402
        self._sha1_provider = sha1_provider
 
403
        if 'hashcache' in debug.debug_flags:
 
404
            self._sha1_file = self._sha1_file_and_mutter
 
405
        else:
 
406
            self._sha1_file = self._sha1_provider.sha1
 
407
        # These two attributes provide a simple cache for lookups into the
 
408
        # dirstate in-memory vectors. By probing respectively for the last
 
409
        # block, and for the next entry, we save nearly 2 bisections per path
 
410
        # during commit.
 
411
        self._last_block_index = None
 
412
        self._last_entry_index = None
342
413
 
343
414
    def __repr__(self):
344
415
        return "%s(%r)" % \
348
419
        """Add a path to be tracked.
349
420
 
350
421
        :param path: The path within the dirstate - '' is the root, 'foo' is the
351
 
            path foo within the root, 'foo/bar' is the path bar within foo 
 
422
            path foo within the root, 'foo/bar' is the path bar within foo
352
423
            within the root.
353
424
        :param file_id: The file id of the path being added.
354
 
        :param kind: The kind of the path, as a string like 'file', 
 
425
        :param kind: The kind of the path, as a string like 'file',
355
426
            'directory', etc.
356
427
        :param stat: The output of os.lstat for the path.
357
 
        :param fingerprint: The sha value of the file,
 
428
        :param fingerprint: The sha value of the file's canonical form (i.e.
 
429
            after any read filters have been applied),
358
430
            or the target of a symlink,
359
431
            or the referenced revision id for tree-references,
360
432
            or '' for directories.
361
433
        """
362
434
        # adding a file:
363
 
        # find the block its in. 
 
435
        # find the block its in.
364
436
        # find the location in the block.
365
437
        # check its not there
366
438
        # add it.
367
 
        #------- copied from inventory.make_entry
 
439
        #------- copied from inventory.ensure_normalized_name - keep synced.
368
440
        # --- normalized_filename wants a unicode basename only, so get one.
369
441
        dirname, basename = osutils.split(path)
370
442
        # we dont import normalized_filename directly because we want to be
379
451
        # in the parent, or according to the special treatment for the root
380
452
        if basename == '.' or basename == '..':
381
453
            raise errors.InvalidEntryName(path)
382
 
        # now that we've normalised, we need the correct utf8 path and 
 
454
        # now that we've normalised, we need the correct utf8 path and
383
455
        # dirname and basename elements. This single encode and split should be
384
456
        # faster than three separate encodes.
385
457
        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
386
458
        dirname, basename = osutils.split(utf8path)
387
 
        assert file_id.__class__ == str, \
388
 
            "must be a utf8 file_id not %s" % (type(file_id))
 
459
        # uses __class__ for speed; the check is needed for safety
 
460
        if file_id.__class__ is not str:
 
461
            raise AssertionError(
 
462
                "must be a utf8 file_id not %s" % (type(file_id), ))
389
463
        # Make sure the file_id does not exist in this tree
390
 
        file_id_entry = self._get_entry(0, fileid_utf8=file_id)
 
464
        rename_from = None
 
465
        file_id_entry = self._get_entry(0, fileid_utf8=file_id, include_deleted=True)
391
466
        if file_id_entry != (None, None):
392
 
            path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
393
 
            kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
394
 
            info = '%s:%s' % (kind, path)
395
 
            raise errors.DuplicateFileId(file_id, info)
 
467
            if file_id_entry[1][0][0] == 'a':
 
468
                if file_id_entry[0] != (dirname, basename, file_id):
 
469
                    # set the old name's current operation to rename
 
470
                    self.update_minimal(file_id_entry[0],
 
471
                        'r',
 
472
                        path_utf8='',
 
473
                        packed_stat='',
 
474
                        fingerprint=utf8path
 
475
                    )
 
476
                    rename_from = file_id_entry[0][0:2]
 
477
            else:
 
478
                path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
 
479
                kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
 
480
                info = '%s:%s' % (kind, path)
 
481
                raise errors.DuplicateFileId(file_id, info)
396
482
        first_key = (dirname, basename, '')
397
483
        block_index, present = self._find_block_index_from_key(first_key)
398
484
        if present:
399
485
            # check the path is not in the tree
400
486
            block = self._dirblocks[block_index][1]
401
487
            entry_index, _ = self._find_entry_index(first_key, block)
402
 
            while (entry_index < len(block) and 
 
488
            while (entry_index < len(block) and
403
489
                block[entry_index][0][0:2] == first_key[0:2]):
404
490
                if block[entry_index][1][0][0] not in 'ar':
405
491
                    # this path is in the dirstate in the current tree.
425
511
            packed_stat = pack_stat(stat)
426
512
        parent_info = self._empty_parent_info()
427
513
        minikind = DirState._kind_to_minikind[kind]
 
514
        if rename_from is not None:
 
515
            if rename_from[0]:
 
516
                old_path_utf8 = '%s/%s' % rename_from
 
517
            else:
 
518
                old_path_utf8 = rename_from[1]
 
519
            parent_info[0] = ('r', old_path_utf8, 0, False, '')
428
520
        if kind == 'file':
429
521
            entry_data = entry_key, [
430
522
                (minikind, fingerprint, size, False, packed_stat),
447
539
        if not present:
448
540
            block.insert(entry_index, entry_data)
449
541
        else:
450
 
            assert block[entry_index][1][0][0] == 'a', " %r(%r) already added" % (basename, file_id)
 
542
            if block[entry_index][1][0][0] != 'a':
 
543
                raise AssertionError(" %r(%r) already added" % (basename, file_id))
451
544
            block[entry_index][1][0] = entry_data[1][0]
452
545
 
453
546
        if kind == 'directory':
472
565
        # If _dirblock_state was in memory, we should just return info from
473
566
        # there, this function is only meant to handle when we want to read
474
567
        # part of the disk.
475
 
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
 
568
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
 
569
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
476
570
 
477
571
        # The disk representation is generally info + '\0\n\0' at the end. But
478
572
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
651
745
        _bisect_dirblocks is meant to find the contents of directories, which
652
746
        differs from _bisect, which only finds individual entries.
653
747
 
654
 
        :param dir_list: An sorted list of directory names ['', 'dir', 'foo'].
 
748
        :param dir_list: A sorted list of directory names ['', 'dir', 'foo'].
655
749
        :return: A map from dir => entries_for_dir
656
750
        """
657
751
        # TODO: jam 20070223 A lot of the bisecting logic could be shared
664
758
        # If _dirblock_state was in memory, we should just return info from
665
759
        # there, this function is only meant to handle when we want to read
666
760
        # part of the disk.
667
 
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
668
 
 
 
761
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
 
762
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
669
763
        # The disk representation is generally info + '\0\n\0' at the end. But
670
764
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
671
765
        # Because it means we can sync on the '\n'
885
979
            processed_dirs.update(pending_dirs)
886
980
        return found
887
981
 
 
982
    def _discard_merge_parents(self):
 
983
        """Discard any parents trees beyond the first.
 
984
 
 
985
        Note that if this fails the dirstate is corrupted.
 
986
 
 
987
        After this function returns the dirstate contains 2 trees, neither of
 
988
        which are ghosted.
 
989
        """
 
990
        self._read_header_if_needed()
 
991
        parents = self.get_parent_ids()
 
992
        if len(parents) < 1:
 
993
            return
 
994
        # only require all dirblocks if we are doing a full-pass removal.
 
995
        self._read_dirblocks_if_needed()
 
996
        dead_patterns = set([('a', 'r'), ('a', 'a'), ('r', 'r'), ('r', 'a')])
 
997
        def iter_entries_removable():
 
998
            for block in self._dirblocks:
 
999
                deleted_positions = []
 
1000
                for pos, entry in enumerate(block[1]):
 
1001
                    yield entry
 
1002
                    if (entry[1][0][0], entry[1][1][0]) in dead_patterns:
 
1003
                        deleted_positions.append(pos)
 
1004
                if deleted_positions:
 
1005
                    if len(deleted_positions) == len(block[1]):
 
1006
                        del block[1][:]
 
1007
                    else:
 
1008
                        for pos in reversed(deleted_positions):
 
1009
                            del block[1][pos]
 
1010
        # if the first parent is a ghost:
 
1011
        if parents[0] in self.get_ghosts():
 
1012
            empty_parent = [DirState.NULL_PARENT_DETAILS]
 
1013
            for entry in iter_entries_removable():
 
1014
                entry[1][1:] = empty_parent
 
1015
        else:
 
1016
            for entry in iter_entries_removable():
 
1017
                del entry[1][2:]
 
1018
 
 
1019
        self._ghosts = []
 
1020
        self._parents = [parents[0]]
 
1021
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1022
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1023
 
888
1024
    def _empty_parent_info(self):
889
1025
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
890
1026
                                                    len(self._ghosts))
916
1052
        # the basename of the directory must be the end of its full name.
917
1053
        if not (parent_block_index == -1 and
918
1054
            parent_block_index == -1 and dirname == ''):
919
 
            assert dirname.endswith(
920
 
                self._dirblocks[parent_block_index][1][parent_row_index][0][1])
 
1055
            if not dirname.endswith(
 
1056
                    self._dirblocks[parent_block_index][1][parent_row_index][0][1]):
 
1057
                raise AssertionError("bad dirname %r" % dirname)
921
1058
        block_index, present = self._find_block_index_from_key((dirname, '', ''))
922
1059
        if not present:
923
 
            ## In future, when doing partial parsing, this should load and 
 
1060
            ## In future, when doing partial parsing, this should load and
924
1061
            # populate the entire block.
925
1062
            self._dirblocks.insert(block_index, (dirname, []))
926
1063
        return block_index
935
1072
            to prevent unneeded overhead when callers have a sorted list already.
936
1073
        :return: Nothing.
937
1074
        """
938
 
        assert new_entries[0][0][0:2] == ('', ''), \
939
 
            "Missing root row %r" % (new_entries[0][0],)
940
 
        # The two blocks here are deliberate: the root block and the 
 
1075
        if new_entries[0][0][0:2] != ('', ''):
 
1076
            raise AssertionError(
 
1077
                "Missing root row %r" % (new_entries[0][0],))
 
1078
        # The two blocks here are deliberate: the root block and the
941
1079
        # contents-of-root block.
942
1080
        self._dirblocks = [('', []), ('', [])]
943
1081
        current_block = self._dirblocks[0][1]
964
1102
        # The above loop leaves the "root block" entries mixed with the
965
1103
        # "contents-of-root block". But we don't want an if check on
966
1104
        # all entries, so instead we just fix it up here.
967
 
        assert self._dirblocks[1] == ('', [])
 
1105
        if self._dirblocks[1] != ('', []):
 
1106
            raise ValueError("bad dirblock start %r" % (self._dirblocks[1],))
968
1107
        root_block = []
969
1108
        contents_of_root_block = []
970
1109
        for entry in self._dirblocks[0][1]:
975
1114
        self._dirblocks[0] = ('', root_block)
976
1115
        self._dirblocks[1] = ('', contents_of_root_block)
977
1116
 
 
1117
    def _entries_for_path(self, path):
 
1118
        """Return a list with all the entries that match path for all ids."""
 
1119
        dirname, basename = os.path.split(path)
 
1120
        key = (dirname, basename, '')
 
1121
        block_index, present = self._find_block_index_from_key(key)
 
1122
        if not present:
 
1123
            # the block which should contain path is absent.
 
1124
            return []
 
1125
        result = []
 
1126
        block = self._dirblocks[block_index][1]
 
1127
        entry_index, _ = self._find_entry_index(key, block)
 
1128
        # we may need to look at multiple entries at this path: walk while the specific_files match.
 
1129
        while (entry_index < len(block) and
 
1130
            block[entry_index][0][0:2] == key[0:2]):
 
1131
            result.append(block[entry_index])
 
1132
            entry_index += 1
 
1133
        return result
 
1134
 
978
1135
    def _entry_to_line(self, entry):
979
1136
        """Serialize entry to a NULL delimited line ready for _get_output_lines.
980
1137
 
1036
1193
        """
1037
1194
        if key[0:2] == ('', ''):
1038
1195
            return 0, True
 
1196
        try:
 
1197
            if (self._last_block_index is not None and
 
1198
                self._dirblocks[self._last_block_index][0] == key[0]):
 
1199
                return self._last_block_index, True
 
1200
        except IndexError:
 
1201
            pass
1039
1202
        block_index = bisect_dirblock(self._dirblocks, key[0], 1,
1040
1203
                                      cache=self._split_path_cache)
1041
1204
        # _right returns one-past-where-key is so we have to subtract
1042
1205
        # one to use it. we use _right here because there are two
1043
1206
        # '' blocks - the root, and the contents of root
1044
1207
        # we always have a minimum of 2 in self._dirblocks: root and
1045
 
        # root-contents, and for '', we get 2 back, so this is 
 
1208
        # root-contents, and for '', we get 2 back, so this is
1046
1209
        # simple and correct:
1047
1210
        present = (block_index < len(self._dirblocks) and
1048
1211
            self._dirblocks[block_index][0] == key[0])
 
1212
        self._last_block_index = block_index
 
1213
        # Reset the entry index cache to the beginning of the block.
 
1214
        self._last_entry_index = -1
1049
1215
        return block_index, present
1050
1216
 
1051
1217
    def _find_entry_index(self, key, block):
1053
1219
 
1054
1220
        :return: The entry index, True if the entry for the key is present.
1055
1221
        """
 
1222
        len_block = len(block)
 
1223
        try:
 
1224
            if self._last_entry_index is not None:
 
1225
                # mini-bisect here.
 
1226
                entry_index = self._last_entry_index + 1
 
1227
                # A hit is when the key is after the last slot, and before or
 
1228
                # equal to the next slot.
 
1229
                if ((entry_index > 0 and block[entry_index - 1][0] < key) and
 
1230
                    key <= block[entry_index][0]):
 
1231
                    self._last_entry_index = entry_index
 
1232
                    present = (block[entry_index][0] == key)
 
1233
                    return entry_index, present
 
1234
        except IndexError:
 
1235
            pass
1056
1236
        entry_index = bisect.bisect_left(block, (key, []))
1057
 
        present = (entry_index < len(block) and
 
1237
        present = (entry_index < len_block and
1058
1238
            block[entry_index][0] == key)
 
1239
        self._last_entry_index = entry_index
1059
1240
        return entry_index, present
1060
1241
 
1061
1242
    @staticmethod
1062
 
    def from_tree(tree, dir_state_filename):
 
1243
    def from_tree(tree, dir_state_filename, sha1_provider=None):
1063
1244
        """Create a dirstate from a bzr Tree.
1064
1245
 
1065
1246
        :param tree: The tree which should provide parent information and
1066
1247
            inventory ids.
 
1248
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
1249
            If None, a DefaultSHA1Provider is used.
1067
1250
        :return: a DirState object which is currently locked for writing.
1068
1251
            (it was locked by DirState.initialize)
1069
1252
        """
1070
 
        result = DirState.initialize(dir_state_filename)
 
1253
        result = DirState.initialize(dir_state_filename,
 
1254
            sha1_provider=sha1_provider)
1071
1255
        try:
1072
1256
            tree.lock_read()
1073
1257
            try:
1091
1275
            raise
1092
1276
        return result
1093
1277
 
1094
 
    def update_entry(self, entry, abspath, stat_value,
1095
 
                     _stat_to_minikind=_stat_to_minikind,
1096
 
                     _pack_stat=pack_stat):
1097
 
        """Update the entry based on what is actually on disk.
1098
 
 
1099
 
        :param entry: This is the dirblock entry for the file in question.
1100
 
        :param abspath: The path on disk for this file.
1101
 
        :param stat_value: (optional) if we already have done a stat on the
1102
 
            file, re-use it.
1103
 
        :return: The sha1 hexdigest of the file (40 bytes) or link target of a
1104
 
                symlink.
 
1278
    def update_by_delta(self, delta):
 
1279
        """Apply an inventory delta to the dirstate for tree 0
 
1280
 
 
1281
        This is the workhorse for apply_inventory_delta in dirstate based
 
1282
        trees.
 
1283
 
 
1284
        :param delta: An inventory delta.  See Inventory.apply_delta for
 
1285
            details.
 
1286
        """
 
1287
        self._read_dirblocks_if_needed()
 
1288
        encode = cache_utf8.encode
 
1289
        insertions = {}
 
1290
        removals = {}
 
1291
        # Accumulate parent references (path_utf8, id), to check for parentless
 
1292
        # items or items placed under files/links/tree-references. We get
 
1293
        # references from every item in the delta that is not a deletion and
 
1294
        # is not itself the root.
 
1295
        parents = set()
 
1296
        # Added ids must not be in the dirstate already. This set holds those
 
1297
        # ids.
 
1298
        new_ids = set()
 
1299
        # This loop transforms the delta to single atomic operations that can
 
1300
        # be executed and validated.
 
1301
        for old_path, new_path, file_id, inv_entry in sorted(
 
1302
            inventory._check_delta_unique_old_paths(
 
1303
            inventory._check_delta_unique_new_paths(
 
1304
            inventory._check_delta_ids_match_entry(
 
1305
            inventory._check_delta_ids_are_valid(
 
1306
            inventory._check_delta_new_path_entry_both_or_None(delta))))),
 
1307
            reverse=True):
 
1308
            if (file_id in insertions) or (file_id in removals):
 
1309
                raise errors.InconsistentDelta(old_path or new_path, file_id,
 
1310
                    "repeated file_id")
 
1311
            if old_path is not None:
 
1312
                old_path = old_path.encode('utf-8')
 
1313
                removals[file_id] = old_path
 
1314
            else:
 
1315
                new_ids.add(file_id)
 
1316
            if new_path is not None:
 
1317
                if inv_entry is None:
 
1318
                    raise errors.InconsistentDelta(new_path, file_id,
 
1319
                        "new_path with no entry")
 
1320
                new_path = new_path.encode('utf-8')
 
1321
                dirname_utf8, basename = osutils.split(new_path)
 
1322
                if basename:
 
1323
                    parents.add((dirname_utf8, inv_entry.parent_id))
 
1324
                key = (dirname_utf8, basename, file_id)
 
1325
                minikind = DirState._kind_to_minikind[inv_entry.kind]
 
1326
                if minikind == 't':
 
1327
                    fingerprint = inv_entry.reference_revision or ''
 
1328
                else:
 
1329
                    fingerprint = ''
 
1330
                insertions[file_id] = (key, minikind, inv_entry.executable,
 
1331
                                       fingerprint, new_path)
 
1332
            # Transform moves into delete+add pairs
 
1333
            if None not in (old_path, new_path):
 
1334
                for child in self._iter_child_entries(0, old_path):
 
1335
                    if child[0][2] in insertions or child[0][2] in removals:
 
1336
                        continue
 
1337
                    child_dirname = child[0][0]
 
1338
                    child_basename = child[0][1]
 
1339
                    minikind = child[1][0][0]
 
1340
                    fingerprint = child[1][0][4]
 
1341
                    executable = child[1][0][3]
 
1342
                    old_child_path = osutils.pathjoin(child_dirname,
 
1343
                                                      child_basename)
 
1344
                    removals[child[0][2]] = old_child_path
 
1345
                    child_suffix = child_dirname[len(old_path):]
 
1346
                    new_child_dirname = (new_path + child_suffix)
 
1347
                    key = (new_child_dirname, child_basename, child[0][2])
 
1348
                    new_child_path = osutils.pathjoin(new_child_dirname,
 
1349
                                                      child_basename)
 
1350
                    insertions[child[0][2]] = (key, minikind, executable,
 
1351
                                               fingerprint, new_child_path)
 
1352
        self._check_delta_ids_absent(new_ids, delta, 0)
 
1353
        try:
 
1354
            self._apply_removals(removals.iteritems())
 
1355
            self._apply_insertions(insertions.values())
 
1356
            # Validate parents
 
1357
            self._after_delta_check_parents(parents, 0)
 
1358
        except errors.BzrError, e:
 
1359
            self._changes_aborted = True
 
1360
            if 'integrity error' not in str(e):
 
1361
                raise
 
1362
            # _get_entry raises BzrError when a request is inconsistent; we
 
1363
            # want such errors to be shown as InconsistentDelta - and that 
 
1364
            # fits the behaviour we trigger.
 
1365
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1366
 
 
1367
    def _apply_removals(self, removals):
 
1368
        for file_id, path in sorted(removals, reverse=True,
 
1369
            key=operator.itemgetter(1)):
 
1370
            dirname, basename = osutils.split(path)
 
1371
            block_i, entry_i, d_present, f_present = \
 
1372
                self._get_block_entry_index(dirname, basename, 0)
 
1373
            try:
 
1374
                entry = self._dirblocks[block_i][1][entry_i]
 
1375
            except IndexError:
 
1376
                self._changes_aborted = True
 
1377
                raise errors.InconsistentDelta(path, file_id,
 
1378
                    "Wrong path for old path.")
 
1379
            if not f_present or entry[1][0][0] in 'ar':
 
1380
                self._changes_aborted = True
 
1381
                raise errors.InconsistentDelta(path, file_id,
 
1382
                    "Wrong path for old path.")
 
1383
            if file_id != entry[0][2]:
 
1384
                self._changes_aborted = True
 
1385
                raise errors.InconsistentDelta(path, file_id,
 
1386
                    "Attempt to remove path has wrong id - found %r."
 
1387
                    % entry[0][2])
 
1388
            self._make_absent(entry)
 
1389
            # See if we have a malformed delta: deleting a directory must not
 
1390
            # leave crud behind. This increases the number of bisects needed
 
1391
            # substantially, but deletion or renames of large numbers of paths
 
1392
            # is rare enough it shouldn't be an issue (famous last words?) RBC
 
1393
            # 20080730.
 
1394
            block_i, entry_i, d_present, f_present = \
 
1395
                self._get_block_entry_index(path, '', 0)
 
1396
            if d_present:
 
1397
                # The dir block is still present in the dirstate; this could
 
1398
                # be due to it being in a parent tree, or a corrupt delta.
 
1399
                for child_entry in self._dirblocks[block_i][1]:
 
1400
                    if child_entry[1][0][0] not in ('r', 'a'):
 
1401
                        self._changes_aborted = True
 
1402
                        raise errors.InconsistentDelta(path, entry[0][2],
 
1403
                            "The file id was deleted but its children were "
 
1404
                            "not deleted.")
 
1405
 
 
1406
    def _apply_insertions(self, adds):
 
1407
        try:
 
1408
            for key, minikind, executable, fingerprint, path_utf8 in sorted(adds):
 
1409
                self.update_minimal(key, minikind, executable, fingerprint,
 
1410
                                    path_utf8=path_utf8)
 
1411
        except errors.NotVersionedError:
 
1412
            self._changes_aborted = True
 
1413
            raise errors.InconsistentDelta(path_utf8.decode('utf8'), key[2],
 
1414
                "Missing parent")
 
1415
 
 
1416
    def update_basis_by_delta(self, delta, new_revid):
 
1417
        """Update the parents of this tree after a commit.
 
1418
 
 
1419
        This gives the tree one parent, with revision id new_revid. The
 
1420
        inventory delta is applied to the current basis tree to generate the
 
1421
        inventory for the parent new_revid, and all other parent trees are
 
1422
        discarded.
 
1423
 
 
1424
        Note that an exception during the operation of this method will leave
 
1425
        the dirstate in a corrupt state where it should not be saved.
 
1426
 
 
1427
        Finally, we expect all changes to be synchronising the basis tree with
 
1428
        the working tree.
 
1429
 
 
1430
        :param new_revid: The new revision id for the trees parent.
 
1431
        :param delta: An inventory delta (see apply_inventory_delta) describing
 
1432
            the changes from the current left most parent revision to new_revid.
 
1433
        """
 
1434
        self._read_dirblocks_if_needed()
 
1435
        self._discard_merge_parents()
 
1436
        if self._ghosts != []:
 
1437
            raise NotImplementedError(self.update_basis_by_delta)
 
1438
        if len(self._parents) == 0:
 
1439
            # setup a blank tree, the most simple way.
 
1440
            empty_parent = DirState.NULL_PARENT_DETAILS
 
1441
            for entry in self._iter_entries():
 
1442
                entry[1].append(empty_parent)
 
1443
            self._parents.append(new_revid)
 
1444
 
 
1445
        self._parents[0] = new_revid
 
1446
 
 
1447
        delta = sorted(delta, reverse=True)
 
1448
        adds = []
 
1449
        changes = []
 
1450
        deletes = []
 
1451
        # The paths this function accepts are unicode and must be encoded as we
 
1452
        # go.
 
1453
        encode = cache_utf8.encode
 
1454
        inv_to_entry = self._inv_entry_to_details
 
1455
        # delta is now (deletes, changes), (adds) in reverse lexographical
 
1456
        # order.
 
1457
        # deletes in reverse lexographic order are safe to process in situ.
 
1458
        # renames are not, as a rename from any path could go to a path
 
1459
        # lexographically lower, so we transform renames into delete, add pairs,
 
1460
        # expanding them recursively as needed.
 
1461
        # At the same time, to reduce interface friction we convert the input
 
1462
        # inventory entries to dirstate.
 
1463
        root_only = ('', '')
 
1464
        # Accumulate parent references (path_utf8, id), to check for parentless
 
1465
        # items or items placed under files/links/tree-references. We get
 
1466
        # references from every item in the delta that is not a deletion and
 
1467
        # is not itself the root.
 
1468
        parents = set()
 
1469
        # Added ids must not be in the dirstate already. This set holds those
 
1470
        # ids.
 
1471
        new_ids = set()
 
1472
        for old_path, new_path, file_id, inv_entry in delta:
 
1473
            if inv_entry is not None and file_id != inv_entry.file_id:
 
1474
                raise errors.InconsistentDelta(new_path, file_id,
 
1475
                    "mismatched entry file_id %r" % inv_entry)
 
1476
            if new_path is not None:
 
1477
                if inv_entry is None:
 
1478
                    raise errors.InconsistentDelta(new_path, file_id,
 
1479
                        "new_path with no entry")
 
1480
                new_path_utf8 = encode(new_path)
 
1481
                # note the parent for validation
 
1482
                dirname_utf8, basename_utf8 = osutils.split(new_path_utf8)
 
1483
                if basename_utf8:
 
1484
                    parents.add((dirname_utf8, inv_entry.parent_id))
 
1485
            if old_path is None:
 
1486
                adds.append((None, encode(new_path), file_id,
 
1487
                    inv_to_entry(inv_entry), True))
 
1488
                new_ids.add(file_id)
 
1489
            elif new_path is None:
 
1490
                deletes.append((encode(old_path), None, file_id, None, True))
 
1491
            elif (old_path, new_path) != root_only:
 
1492
                # Renames:
 
1493
                # Because renames must preserve their children we must have
 
1494
                # processed all relocations and removes before hand. The sort
 
1495
                # order ensures we've examined the child paths, but we also
 
1496
                # have to execute the removals, or the split to an add/delete
 
1497
                # pair will result in the deleted item being reinserted, or
 
1498
                # renamed items being reinserted twice - and possibly at the
 
1499
                # wrong place. Splitting into a delete/add pair also simplifies
 
1500
                # the handling of entries with ('f', ...), ('r' ...) because
 
1501
                # the target of the 'r' is old_path here, and we add that to
 
1502
                # deletes, meaning that the add handler does not need to check
 
1503
                # for 'r' items on every pass.
 
1504
                self._update_basis_apply_deletes(deletes)
 
1505
                deletes = []
 
1506
                # Split into an add/delete pair recursively.
 
1507
                adds.append((None, new_path_utf8, file_id,
 
1508
                    inv_to_entry(inv_entry), False))
 
1509
                # Expunge deletes that we've seen so that deleted/renamed
 
1510
                # children of a rename directory are handled correctly.
 
1511
                new_deletes = reversed(list(self._iter_child_entries(1,
 
1512
                    encode(old_path))))
 
1513
                # Remove the current contents of the tree at orig_path, and
 
1514
                # reinsert at the correct new path.
 
1515
                for entry in new_deletes:
 
1516
                    if entry[0][0]:
 
1517
                        source_path = entry[0][0] + '/' + entry[0][1]
 
1518
                    else:
 
1519
                        source_path = entry[0][1]
 
1520
                    if new_path_utf8:
 
1521
                        target_path = new_path_utf8 + source_path[len(old_path):]
 
1522
                    else:
 
1523
                        if old_path == '':
 
1524
                            raise AssertionError("cannot rename directory to"
 
1525
                                " itself")
 
1526
                        target_path = source_path[len(old_path) + 1:]
 
1527
                    adds.append((None, target_path, entry[0][2], entry[1][1], False))
 
1528
                    deletes.append(
 
1529
                        (source_path, target_path, entry[0][2], None, False))
 
1530
                deletes.append(
 
1531
                    (encode(old_path), new_path, file_id, None, False))
 
1532
            else:
 
1533
                # changes to just the root should not require remove/insertion
 
1534
                # of everything.
 
1535
                changes.append((encode(old_path), encode(new_path), file_id,
 
1536
                    inv_to_entry(inv_entry)))
 
1537
        self._check_delta_ids_absent(new_ids, delta, 1)
 
1538
        try:
 
1539
            # Finish expunging deletes/first half of renames.
 
1540
            self._update_basis_apply_deletes(deletes)
 
1541
            # Reinstate second half of renames and new paths.
 
1542
            self._update_basis_apply_adds(adds)
 
1543
            # Apply in-situ changes.
 
1544
            self._update_basis_apply_changes(changes)
 
1545
            # Validate parents
 
1546
            self._after_delta_check_parents(parents, 1)
 
1547
        except errors.BzrError, e:
 
1548
            self._changes_aborted = True
 
1549
            if 'integrity error' not in str(e):
 
1550
                raise
 
1551
            # _get_entry raises BzrError when a request is inconsistent; we
 
1552
            # want such errors to be shown as InconsistentDelta - and that 
 
1553
            # fits the behaviour we trigger. Partof this is driven by dirstate
 
1554
            # only supporting deltas that turn the basis into a closer fit to
 
1555
            # the active tree.
 
1556
            raise errors.InconsistentDeltaDelta(delta, "error from _get_entry.")
 
1557
 
 
1558
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1559
        self._header_state = DirState.IN_MEMORY_MODIFIED
 
1560
        self._id_index = None
 
1561
        return
 
1562
 
 
1563
    def _check_delta_ids_absent(self, new_ids, delta, tree_index):
 
1564
        """Check that none of the file_ids in new_ids are present in a tree."""
 
1565
        if not new_ids:
 
1566
            return
 
1567
        id_index = self._get_id_index()
 
1568
        for file_id in new_ids:
 
1569
            for key in id_index.get(file_id, []):
 
1570
                block_i, entry_i, d_present, f_present = \
 
1571
                    self._get_block_entry_index(key[0], key[1], tree_index)
 
1572
                if not f_present:
 
1573
                    # In a different tree
 
1574
                    continue
 
1575
                entry = self._dirblocks[block_i][1][entry_i]
 
1576
                if entry[0][2] != file_id:
 
1577
                    # Different file_id, so not what we want.
 
1578
                    continue
 
1579
                # NB: No changes made before this helper is called, so no need
 
1580
                # to set the _changes_aborted flag.
 
1581
                raise errors.InconsistentDelta(
 
1582
                    ("%s/%s" % key[0:2]).decode('utf8'), file_id,
 
1583
                    "This file_id is new in the delta but already present in "
 
1584
                    "the target")
 
1585
 
 
1586
    def _update_basis_apply_adds(self, adds):
 
1587
        """Apply a sequence of adds to tree 1 during update_basis_by_delta.
 
1588
 
 
1589
        They may be adds, or renames that have been split into add/delete
 
1590
        pairs.
 
1591
 
 
1592
        :param adds: A sequence of adds. Each add is a tuple:
 
1593
            (None, new_path_utf8, file_id, (entry_details), real_add). real_add
 
1594
            is False when the add is the second half of a remove-and-reinsert
 
1595
            pair created to handle renames and deletes.
 
1596
        """
 
1597
        # Adds are accumulated partly from renames, so can be in any input
 
1598
        # order - sort it.
 
1599
        adds.sort()
 
1600
        # adds is now in lexographic order, which places all parents before
 
1601
        # their children, so we can process it linearly.
 
1602
        absent = 'ar'
 
1603
        for old_path, new_path, file_id, new_details, real_add in adds:
 
1604
            # the entry for this file_id must be in tree 0.
 
1605
            entry = self._get_entry(0, file_id, new_path)
 
1606
            if entry[0] is None or entry[0][2] != file_id:
 
1607
                self._changes_aborted = True
 
1608
                raise errors.InconsistentDelta(new_path, file_id,
 
1609
                    'working tree does not contain new entry')
 
1610
            if real_add and entry[1][1][0] not in absent:
 
1611
                self._changes_aborted = True
 
1612
                raise errors.InconsistentDelta(new_path, file_id,
 
1613
                    'The entry was considered to be a genuinely new record,'
 
1614
                    ' but there was already an old record for it.')
 
1615
            # We don't need to update the target of an 'r' because the handling
 
1616
            # of renames turns all 'r' situations into a delete at the original
 
1617
            # location.
 
1618
            entry[1][1] = new_details
 
1619
 
 
1620
    def _update_basis_apply_changes(self, changes):
 
1621
        """Apply a sequence of changes to tree 1 during update_basis_by_delta.
 
1622
 
 
1623
        :param adds: A sequence of changes. Each change is a tuple:
 
1624
            (path_utf8, path_utf8, file_id, (entry_details))
 
1625
        """
 
1626
        absent = 'ar'
 
1627
        for old_path, new_path, file_id, new_details in changes:
 
1628
            # the entry for this file_id must be in tree 0.
 
1629
            entry = self._get_entry(0, file_id, new_path)
 
1630
            if entry[0] is None or entry[0][2] != file_id:
 
1631
                self._changes_aborted = True
 
1632
                raise errors.InconsistentDelta(new_path, file_id,
 
1633
                    'working tree does not contain new entry')
 
1634
            if (entry[1][0][0] in absent or
 
1635
                entry[1][1][0] in absent):
 
1636
                self._changes_aborted = True
 
1637
                raise errors.InconsistentDelta(new_path, file_id,
 
1638
                    'changed considered absent')
 
1639
            entry[1][1] = new_details
 
1640
 
 
1641
    def _update_basis_apply_deletes(self, deletes):
 
1642
        """Apply a sequence of deletes to tree 1 during update_basis_by_delta.
 
1643
 
 
1644
        They may be deletes, or renames that have been split into add/delete
 
1645
        pairs.
 
1646
 
 
1647
        :param deletes: A sequence of deletes. Each delete is a tuple:
 
1648
            (old_path_utf8, new_path_utf8, file_id, None, real_delete).
 
1649
            real_delete is True when the desired outcome is an actual deletion
 
1650
            rather than the rename handling logic temporarily deleting a path
 
1651
            during the replacement of a parent.
 
1652
        """
 
1653
        null = DirState.NULL_PARENT_DETAILS
 
1654
        for old_path, new_path, file_id, _, real_delete in deletes:
 
1655
            if real_delete != (new_path is None):
 
1656
                self._changes_aborted = True
 
1657
                raise AssertionError("bad delete delta")
 
1658
            # the entry for this file_id must be in tree 1.
 
1659
            dirname, basename = osutils.split(old_path)
 
1660
            block_index, entry_index, dir_present, file_present = \
 
1661
                self._get_block_entry_index(dirname, basename, 1)
 
1662
            if not file_present:
 
1663
                self._changes_aborted = True
 
1664
                raise errors.InconsistentDelta(old_path, file_id,
 
1665
                    'basis tree does not contain removed entry')
 
1666
            entry = self._dirblocks[block_index][1][entry_index]
 
1667
            if entry[0][2] != file_id:
 
1668
                self._changes_aborted = True
 
1669
                raise errors.InconsistentDelta(old_path, file_id,
 
1670
                    'mismatched file_id in tree 1')
 
1671
            if real_delete:
 
1672
                if entry[1][0][0] != 'a':
 
1673
                    self._changes_aborted = True
 
1674
                    raise errors.InconsistentDelta(old_path, file_id,
 
1675
                            'This was marked as a real delete, but the WT state'
 
1676
                            ' claims that it still exists and is versioned.')
 
1677
                del self._dirblocks[block_index][1][entry_index]
 
1678
            else:
 
1679
                if entry[1][0][0] == 'a':
 
1680
                    self._changes_aborted = True
 
1681
                    raise errors.InconsistentDelta(old_path, file_id,
 
1682
                        'The entry was considered a rename, but the source path'
 
1683
                        ' is marked as absent.')
 
1684
                    # For whatever reason, we were asked to rename an entry
 
1685
                    # that was originally marked as deleted. This could be
 
1686
                    # because we are renaming the parent directory, and the WT
 
1687
                    # current state has the file marked as deleted.
 
1688
                elif entry[1][0][0] == 'r':
 
1689
                    # implement the rename
 
1690
                    del self._dirblocks[block_index][1][entry_index]
 
1691
                else:
 
1692
                    # it is being resurrected here, so blank it out temporarily.
 
1693
                    self._dirblocks[block_index][1][entry_index][1][1] = null
 
1694
 
 
1695
    def _after_delta_check_parents(self, parents, index):
 
1696
        """Check that parents required by the delta are all intact.
 
1697
        
 
1698
        :param parents: An iterable of (path_utf8, file_id) tuples which are
 
1699
            required to be present in tree 'index' at path_utf8 with id file_id
 
1700
            and be a directory.
 
1701
        :param index: The column in the dirstate to check for parents in.
 
1702
        """
 
1703
        for dirname_utf8, file_id in parents:
 
1704
            # Get the entry - the ensures that file_id, dirname_utf8 exists and
 
1705
            # has the right file id.
 
1706
            entry = self._get_entry(index, file_id, dirname_utf8)
 
1707
            if entry[1] is None:
 
1708
                self._changes_aborted = True
 
1709
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1710
                    file_id, "This parent is not present.")
 
1711
            # Parents of things must be directories
 
1712
            if entry[1][index][0] != 'd':
 
1713
                self._changes_aborted = True
 
1714
                raise errors.InconsistentDelta(dirname_utf8.decode('utf8'),
 
1715
                    file_id, "This parent is not a directory.")
 
1716
 
 
1717
    def _observed_sha1(self, entry, sha1, stat_value,
 
1718
        _stat_to_minikind=_stat_to_minikind, _pack_stat=pack_stat):
 
1719
        """Note the sha1 of a file.
 
1720
 
 
1721
        :param entry: The entry the sha1 is for.
 
1722
        :param sha1: The observed sha1.
 
1723
        :param stat_value: The os.lstat for the file.
1105
1724
        """
1106
1725
        try:
1107
1726
            minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
1109
1728
            # Unhandled kind
1110
1729
            return None
1111
1730
        packed_stat = _pack_stat(stat_value)
1112
 
        (saved_minikind, saved_link_or_sha1, saved_file_size,
1113
 
         saved_executable, saved_packed_stat) = entry[1][0]
1114
 
 
1115
 
        if (minikind == saved_minikind
1116
 
            and packed_stat == saved_packed_stat):
1117
 
            # The stat hasn't changed since we saved, so we can re-use the
1118
 
            # saved sha hash.
1119
 
            if minikind == 'd':
1120
 
                return None
1121
 
 
1122
 
            # size should also be in packed_stat
1123
 
            if saved_file_size == stat_value.st_size:
1124
 
                return saved_link_or_sha1
1125
 
 
1126
 
        # If we have gotten this far, that means that we need to actually
1127
 
        # process this entry.
1128
 
        link_or_sha1 = None
1129
1731
        if minikind == 'f':
1130
 
            link_or_sha1 = self._sha1_file(abspath, entry)
1131
 
            executable = self._is_executable(stat_value.st_mode,
1132
 
                                             saved_executable)
1133
 
            if self._cutoff_time is None:
1134
 
                self._sha_cutoff_time()
1135
 
            if (stat_value.st_mtime < self._cutoff_time
1136
 
                and stat_value.st_ctime < self._cutoff_time):
1137
 
                entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
1138
 
                               executable, packed_stat)
1139
 
            else:
1140
 
                entry[1][0] = ('f', '', stat_value.st_size,
1141
 
                               executable, DirState.NULLSTAT)
1142
 
        elif minikind == 'd':
1143
 
            link_or_sha1 = None
1144
 
            entry[1][0] = ('d', '', 0, False, packed_stat)
1145
 
            if saved_minikind != 'd':
1146
 
                # This changed from something into a directory. Make sure we
1147
 
                # have a directory block for it. This doesn't happen very
1148
 
                # often, so this doesn't have to be super fast.
1149
 
                block_index, entry_index, dir_present, file_present = \
1150
 
                    self._get_block_entry_index(entry[0][0], entry[0][1], 0)
1151
 
                self._ensure_block(block_index, entry_index,
1152
 
                                   osutils.pathjoin(entry[0][0], entry[0][1]))
1153
 
        elif minikind == 'l':
1154
 
            link_or_sha1 = self._read_link(abspath, saved_link_or_sha1)
1155
 
            if self._cutoff_time is None:
1156
 
                self._sha_cutoff_time()
1157
 
            if (stat_value.st_mtime < self._cutoff_time
1158
 
                and stat_value.st_ctime < self._cutoff_time):
1159
 
                entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
1160
 
                               False, packed_stat)
1161
 
            else:
1162
 
                entry[1][0] = ('l', '', stat_value.st_size,
1163
 
                               False, DirState.NULLSTAT)
1164
 
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1165
 
        return link_or_sha1
 
1732
            if self._cutoff_time is None:
 
1733
                self._sha_cutoff_time()
 
1734
            if (stat_value.st_mtime < self._cutoff_time
 
1735
                and stat_value.st_ctime < self._cutoff_time):
 
1736
                entry[1][0] = ('f', sha1, entry[1][0][2], entry[1][0][3],
 
1737
                    packed_stat)
 
1738
                self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1166
1739
 
1167
1740
    def _sha_cutoff_time(self):
1168
1741
        """Return cutoff time.
1181
1754
        """Return the os.lstat value for this path."""
1182
1755
        return os.lstat(abspath)
1183
1756
 
1184
 
    def _sha1_file(self, abspath, entry):
1185
 
        """Calculate the SHA1 of a file by reading the full text"""
1186
 
        f = file(abspath, 'rb', buffering=65000)
1187
 
        try:
1188
 
            return osutils.sha_file(f)
1189
 
        finally:
1190
 
            f.close()
 
1757
    def _sha1_file_and_mutter(self, abspath):
 
1758
        # when -Dhashcache is turned on, this is monkey-patched in to log
 
1759
        # file reads
 
1760
        trace.mutter("dirstate sha1 " + abspath)
 
1761
        return self._sha1_provider.sha1(abspath)
1191
1762
 
1192
1763
    def _is_executable(self, mode, old_executable):
1193
1764
        """Is this file executable?"""
1206
1777
        #       already in memory. However, this really needs to be done at a
1207
1778
        #       higher level, because there either won't be anything on disk,
1208
1779
        #       or the thing on disk will be a file.
1209
 
        return os.readlink(abspath)
 
1780
        fs_encoding = osutils._fs_enc
 
1781
        if isinstance(abspath, unicode):
 
1782
            # abspath is defined as the path to pass to lstat. readlink is
 
1783
            # buggy in python < 2.6 (it doesn't encode unicode path into FS
 
1784
            # encoding), so we need to encode ourselves knowing that unicode
 
1785
            # paths are produced by UnicodeDirReader on purpose.
 
1786
            abspath = abspath.encode(fs_encoding)
 
1787
        target = os.readlink(abspath)
 
1788
        if fs_encoding not in ('UTF-8', 'US-ASCII', 'ANSI_X3.4-1968'):
 
1789
            # Change encoding if needed
 
1790
            target = target.decode(fs_encoding).encode('UTF-8')
 
1791
        return target
1210
1792
 
1211
1793
    def get_ghosts(self):
1212
1794
        """Return a list of the parent tree revision ids that are ghosts."""
1330
1912
            be attempted.
1331
1913
        :return: A tuple describing where the path is located, or should be
1332
1914
            inserted. The tuple contains four fields: the block index, the row
1333
 
            index, anda two booleans are True when the directory is present, and
1334
 
            when the entire path is present.  There is no guarantee that either
 
1915
            index, the directory is present (boolean), the entire path is
 
1916
            present (boolean).  There is no guarantee that either
1335
1917
            coordinate is currently reachable unless the found field for it is
1336
1918
            True. For instance, a directory not present in the searched tree
1337
1919
            may be returned with a value one greater than the current highest
1349
1931
            return block_index, 0, False, False
1350
1932
        block = self._dirblocks[block_index][1] # access the entries only
1351
1933
        entry_index, present = self._find_entry_index(key, block)
1352
 
        # linear search through present entries at this path to find the one
 
1934
        # linear search through entries at this path to find the one
1353
1935
        # requested.
1354
1936
        while entry_index < len(block) and block[entry_index][0][1] == basename:
1355
 
            if block[entry_index][1][tree_index][0] not in \
1356
 
                       ('a', 'r'): # absent, relocated
 
1937
            if block[entry_index][1][tree_index][0] not in 'ar':
 
1938
                # neither absent or relocated
1357
1939
                return block_index, entry_index, True, True
1358
1940
            entry_index += 1
1359
1941
        return block_index, entry_index, True, False
1360
1942
 
1361
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None):
1362
 
        """Get the dirstate entry for path in tree tree_index
 
1943
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
1944
        """Get the dirstate entry for path in tree tree_index.
1363
1945
 
1364
1946
        If either file_id or path is supplied, it is used as the key to lookup.
1365
1947
        If both are supplied, the fastest lookup is used, and an error is
1372
1954
            trees.
1373
1955
        :param fileid_utf8: A utf8 file_id to look up.
1374
1956
        :param path_utf8: An utf8 path to be looked up.
 
1957
        :param include_deleted: If True, and performing a lookup via
 
1958
            fileid_utf8 rather than path_utf8, return an entry for deleted
 
1959
            (absent) paths.
1375
1960
        :return: The dirstate entry tuple for path, or (None, None)
1376
1961
        """
1377
1962
        self._read_dirblocks_if_needed()
1378
1963
        if path_utf8 is not None:
1379
 
            assert path_utf8.__class__ == str, 'path_utf8 is not a str: %s %s' % (type(path_utf8), path_utf8)
 
1964
            if type(path_utf8) is not str:
 
1965
                raise errors.BzrError('path_utf8 is not a str: %s %r'
 
1966
                    % (type(path_utf8), path_utf8))
1380
1967
            # path lookups are faster
1381
1968
            dirname, basename = osutils.split(path_utf8)
1382
1969
            block_index, entry_index, dir_present, file_present = \
1384
1971
            if not file_present:
1385
1972
                return None, None
1386
1973
            entry = self._dirblocks[block_index][1][entry_index]
1387
 
            assert entry[0][2] and entry[1][tree_index][0] not in ('a', 'r'), 'unversioned entry?!?!'
 
1974
            if not (entry[0][2] and entry[1][tree_index][0] not in ('a', 'r')):
 
1975
                raise AssertionError('unversioned entry?')
1388
1976
            if fileid_utf8:
1389
1977
                if entry[0][2] != fileid_utf8:
 
1978
                    self._changes_aborted = True
1390
1979
                    raise errors.BzrError('integrity error ? : mismatching'
1391
1980
                                          ' tree_index, file_id and path')
1392
1981
            return entry
1393
1982
        else:
1394
 
            assert fileid_utf8 is not None
1395
1983
            possible_keys = self._get_id_index().get(fileid_utf8, None)
1396
1984
            if not possible_keys:
1397
1985
                return None, None
1404
1992
                    continue
1405
1993
                # WARNING: DO not change this code to use _get_block_entry_index
1406
1994
                # as that function is not suitable: it does not use the key
1407
 
                # to lookup, and thus the wront coordinates are returned.
 
1995
                # to lookup, and thus the wrong coordinates are returned.
1408
1996
                block = self._dirblocks[block_index][1]
1409
1997
                entry_index, present = self._find_entry_index(key, block)
1410
1998
                if present:
1411
1999
                    entry = self._dirblocks[block_index][1][entry_index]
 
2000
                    # TODO: We might want to assert that entry[0][2] ==
 
2001
                    #       fileid_utf8.
1412
2002
                    if entry[1][tree_index][0] in 'fdlt':
1413
 
                        # this is the result we are looking for: the  
 
2003
                        # this is the result we are looking for: the
1414
2004
                        # real home of this file_id in this tree.
1415
2005
                        return entry
1416
2006
                    if entry[1][tree_index][0] == 'a':
1417
2007
                        # there is no home for this entry in this tree
 
2008
                        if include_deleted:
 
2009
                            return entry
1418
2010
                        return None, None
1419
 
                    assert entry[1][tree_index][0] == 'r', \
1420
 
                        "entry %r has invalid minikind %r for tree %r" \
1421
 
                        % (entry,
1422
 
                           entry[1][tree_index][0],
1423
 
                           tree_index)
 
2011
                    if entry[1][tree_index][0] != 'r':
 
2012
                        raise AssertionError(
 
2013
                            "entry %r has invalid minikind %r for tree %r" \
 
2014
                            % (entry,
 
2015
                               entry[1][tree_index][0],
 
2016
                               tree_index))
1424
2017
                    real_path = entry[1][tree_index][1]
1425
2018
                    return self._get_entry(tree_index, fileid_utf8=fileid_utf8,
1426
2019
                        path_utf8=real_path)
1427
2020
            return None, None
1428
2021
 
1429
2022
    @classmethod
1430
 
    def initialize(cls, path):
 
2023
    def initialize(cls, path, sha1_provider=None):
1431
2024
        """Create a new dirstate on path.
1432
2025
 
1433
2026
        The new dirstate will be an empty tree - that is it has no parents,
1434
2027
        and only a root node - which has id ROOT_ID.
1435
2028
 
1436
2029
        :param path: The name of the file for the dirstate.
 
2030
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
2031
            If None, a DefaultSHA1Provider is used.
1437
2032
        :return: A write-locked DirState object.
1438
2033
        """
1439
2034
        # This constructs a new DirState object on a path, sets the _state_file
1441
2036
        # stock empty dirstate information - a root with ROOT_ID, no children,
1442
2037
        # and no parents. Finally it calls save() to ensure that this data will
1443
2038
        # persist.
1444
 
        result = cls(path)
 
2039
        if sha1_provider is None:
 
2040
            sha1_provider = DefaultSHA1Provider()
 
2041
        result = cls(path, sha1_provider)
1445
2042
        # root dir and root dir contents with no children.
1446
2043
        empty_tree_dirblocks = [('', []), ('', [])]
1447
2044
        # a new root directory, with a NULLSTAT.
1458
2055
            raise
1459
2056
        return result
1460
2057
 
1461
 
    def _inv_entry_to_details(self, inv_entry):
 
2058
    @staticmethod
 
2059
    def _inv_entry_to_details(inv_entry):
1462
2060
        """Convert an inventory entry (from a revision tree) to state details.
1463
2061
 
1464
2062
        :param inv_entry: An inventory entry whose sha1 and link targets can be
1469
2067
        kind = inv_entry.kind
1470
2068
        minikind = DirState._kind_to_minikind[kind]
1471
2069
        tree_data = inv_entry.revision
1472
 
        assert len(tree_data) > 0, 'empty revision for the inv_entry.'
1473
2070
        if kind == 'directory':
1474
2071
            fingerprint = ''
1475
2072
            size = 0
1476
2073
            executable = False
1477
2074
        elif kind == 'symlink':
1478
 
            fingerprint = inv_entry.symlink_target or ''
 
2075
            if inv_entry.symlink_target is None:
 
2076
                fingerprint = ''
 
2077
            else:
 
2078
                fingerprint = inv_entry.symlink_target.encode('utf8')
1479
2079
            size = 0
1480
2080
            executable = False
1481
2081
        elif kind == 'file':
1490
2090
            raise Exception("can't pack %s" % inv_entry)
1491
2091
        return (minikind, fingerprint, size, executable, tree_data)
1492
2092
 
 
2093
    def _iter_child_entries(self, tree_index, path_utf8):
 
2094
        """Iterate over all the entries that are children of path_utf.
 
2095
 
 
2096
        This only returns entries that are present (not in 'a', 'r') in
 
2097
        tree_index. tree_index data is not refreshed, so if tree 0 is used,
 
2098
        results may differ from that obtained if paths were statted to
 
2099
        determine what ones were directories.
 
2100
 
 
2101
        Asking for the children of a non-directory will return an empty
 
2102
        iterator.
 
2103
        """
 
2104
        pending_dirs = []
 
2105
        next_pending_dirs = [path_utf8]
 
2106
        absent = 'ar'
 
2107
        while next_pending_dirs:
 
2108
            pending_dirs = next_pending_dirs
 
2109
            next_pending_dirs = []
 
2110
            for path in pending_dirs:
 
2111
                block_index, present = self._find_block_index_from_key(
 
2112
                    (path, '', ''))
 
2113
                if block_index == 0:
 
2114
                    block_index = 1
 
2115
                    if len(self._dirblocks) == 1:
 
2116
                        # asked for the children of the root with no other
 
2117
                        # contents.
 
2118
                        return
 
2119
                if not present:
 
2120
                    # children of a non-directory asked for.
 
2121
                    continue
 
2122
                block = self._dirblocks[block_index]
 
2123
                for entry in block[1]:
 
2124
                    kind = entry[1][tree_index][0]
 
2125
                    if kind not in absent:
 
2126
                        yield entry
 
2127
                    if kind == 'd':
 
2128
                        if entry[0][0]:
 
2129
                            path = entry[0][0] + '/' + entry[0][1]
 
2130
                        else:
 
2131
                            path = entry[0][1]
 
2132
                        next_pending_dirs.append(path)
 
2133
 
1493
2134
    def _iter_entries(self):
1494
2135
        """Iterate over all the entries in the dirstate.
1495
2136
 
1511
2152
        return self._id_index
1512
2153
 
1513
2154
    def _get_output_lines(self, lines):
1514
 
        """format lines for final output.
 
2155
        """Format lines for final output.
1515
2156
 
1516
 
        :param lines: A sequece of lines containing the parents list and the
 
2157
        :param lines: A sequence of lines containing the parents list and the
1517
2158
            path lines.
1518
2159
        """
1519
2160
        output_lines = [DirState.HEADER_FORMAT_3]
1527
2168
        return output_lines
1528
2169
 
1529
2170
    def _make_deleted_row(self, fileid_utf8, parents):
1530
 
        """Return a deleted for for fileid_utf8."""
 
2171
        """Return a deleted row for fileid_utf8."""
1531
2172
        return ('/', 'RECYCLED.BIN', 'file', fileid_utf8, 0, DirState.NULLSTAT,
1532
2173
            ''), parents
1533
2174
 
1536
2177
        return len(self._parents) - len(self._ghosts)
1537
2178
 
1538
2179
    @staticmethod
1539
 
    def on_file(path):
1540
 
        """Construct a DirState on the file at path path.
 
2180
    def on_file(path, sha1_provider=None):
 
2181
        """Construct a DirState on the file at path "path".
1541
2182
 
 
2183
        :param path: The path at which the dirstate file on disk should live.
 
2184
        :param sha1_provider: an object meeting the SHA1Provider interface.
 
2185
            If None, a DefaultSHA1Provider is used.
1542
2186
        :return: An unlocked DirState object, associated with the given path.
1543
2187
        """
1544
 
        result = DirState(path)
 
2188
        if sha1_provider is None:
 
2189
            sha1_provider = DefaultSHA1Provider()
 
2190
        result = DirState(path, sha1_provider)
1545
2191
        return result
1546
2192
 
1547
2193
    def _read_dirblocks_if_needed(self):
1548
2194
        """Read in all the dirblocks from the file if they are not in memory.
1549
 
        
 
2195
 
1550
2196
        This populates self._dirblocks, and sets self._dirblock_state to
1551
2197
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
1552
2198
        loading.
1567
2213
        parent_line = self._state_file.readline()
1568
2214
        info = parent_line.split('\0')
1569
2215
        num_parents = int(info[0])
1570
 
        assert num_parents == len(info)-2, 'incorrect parent info line'
1571
2216
        self._parents = info[1:-1]
1572
 
 
1573
2217
        ghost_line = self._state_file.readline()
1574
2218
        info = ghost_line.split('\0')
1575
2219
        num_ghosts = int(info[1])
1576
 
        assert num_ghosts == len(info)-3, 'incorrect ghost info line'
1577
2220
        self._ghosts = info[2:-1]
1578
2221
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
1579
2222
        self._end_of_header = self._state_file.tell()
1587
2230
            self._read_header()
1588
2231
 
1589
2232
    def _read_prelude(self):
1590
 
        """Read in the prelude header of the dirstate file
 
2233
        """Read in the prelude header of the dirstate file.
1591
2234
 
1592
2235
        This only reads in the stuff that is not connected to the crc
1593
2236
        checksum. The position will be correct to read in the rest of
1596
2239
        and their ids. Followed by a newline.
1597
2240
        """
1598
2241
        header = self._state_file.readline()
1599
 
        assert header == DirState.HEADER_FORMAT_3, \
1600
 
            'invalid header line: %r' % (header,)
 
2242
        if header != DirState.HEADER_FORMAT_3:
 
2243
            raise errors.BzrError(
 
2244
                'invalid header line: %r' % (header,))
1601
2245
        crc_line = self._state_file.readline()
1602
 
        assert crc_line.startswith('crc32: '), 'missing crc32 checksum'
 
2246
        if not crc_line.startswith('crc32: '):
 
2247
            raise errors.BzrError('missing crc32 checksum: %r' % crc_line)
1603
2248
        self.crc_expected = int(crc_line[len('crc32: '):-1])
1604
2249
        num_entries_line = self._state_file.readline()
1605
 
        assert num_entries_line.startswith('num_entries: '), 'missing num_entries line'
 
2250
        if not num_entries_line.startswith('num_entries: '):
 
2251
            raise errors.BzrError('missing num_entries line')
1606
2252
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
1607
2253
 
 
2254
    def sha1_from_stat(self, path, stat_result, _pack_stat=pack_stat):
 
2255
        """Find a sha1 given a stat lookup."""
 
2256
        return self._get_packed_stat_index().get(_pack_stat(stat_result), None)
 
2257
 
 
2258
    def _get_packed_stat_index(self):
 
2259
        """Get a packed_stat index of self._dirblocks."""
 
2260
        if self._packed_stat_index is None:
 
2261
            index = {}
 
2262
            for key, tree_details in self._iter_entries():
 
2263
                if tree_details[0][0] == 'f':
 
2264
                    index[tree_details[0][4]] = tree_details[0][1]
 
2265
            self._packed_stat_index = index
 
2266
        return self._packed_stat_index
 
2267
 
1608
2268
    def save(self):
1609
2269
        """Save any pending changes created during this session.
1610
2270
 
1611
2271
        We reuse the existing file, because that prevents race conditions with
1612
2272
        file creation, and use oslocks on it to prevent concurrent modification
1613
 
        and reads - because dirstates incremental data aggretation is not
 
2273
        and reads - because dirstate's incremental data aggregation is not
1614
2274
        compatible with reading a modified file, and replacing a file in use by
1615
 
        another process is impossible on windows.
 
2275
        another process is impossible on Windows.
1616
2276
 
1617
2277
        A dirstate in read only mode should be smart enough though to validate
1618
2278
        that the file has not changed, and otherwise discard its cache and
1619
2279
        start over, to allow for fine grained read lock duration, so 'status'
1620
2280
        wont block 'commit' - for example.
1621
2281
        """
 
2282
        if self._changes_aborted:
 
2283
            # Should this be a warning? For now, I'm expecting that places that
 
2284
            # mark it inconsistent will warn, making a warning here redundant.
 
2285
            trace.mutter('Not saving DirState because '
 
2286
                    '_changes_aborted is set.')
 
2287
            return
1622
2288
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
1623
2289
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
1624
2290
 
1657
2323
 
1658
2324
        :param parent_ids: A list of parent tree revision ids.
1659
2325
        :param dirblocks: A list containing one tuple for each directory in the
1660
 
            tree. Each tuple contains the directory path and a list of entries 
 
2326
            tree. Each tuple contains the directory path and a list of entries
1661
2327
            found in that directory.
1662
2328
        """
1663
2329
        # our memory copy is now authoritative.
1666
2332
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1667
2333
        self._parents = list(parent_ids)
1668
2334
        self._id_index = None
 
2335
        self._packed_stat_index = None
1669
2336
 
1670
2337
    def set_path_id(self, path, new_id):
1671
2338
        """Change the id of path to new_id in the current working tree.
1675
2342
        :param new_id: The new id to assign to the path. This must be a utf8
1676
2343
            file id (not unicode, and not None).
1677
2344
        """
1678
 
        assert new_id.__class__ == str, \
1679
 
            "path_id %r is not a plain string" % (new_id,)
1680
2345
        self._read_dirblocks_if_needed()
1681
2346
        if len(path):
1682
 
            # logic not written
 
2347
            # TODO: logic not written
1683
2348
            raise NotImplementedError(self.set_path_id)
1684
2349
        # TODO: check new id is unique
1685
2350
        entry = self._get_entry(0, path_utf8=path)
1691
2356
        self.update_minimal(('', '', new_id), 'd',
1692
2357
            path_utf8='', packed_stat=entry[1][0][4])
1693
2358
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1694
 
        if self._id_index is not None:
1695
 
            self._id_index.setdefault(new_id, set()).add(entry[0])
1696
2359
 
1697
2360
    def set_parent_trees(self, trees, ghosts):
1698
2361
        """Set the parent trees for the dirstate.
1699
2362
 
1700
2363
        :param trees: A list of revision_id, tree tuples. tree must be provided
1701
 
            even if the revision_id refers to a ghost: supply an empty tree in 
 
2364
            even if the revision_id refers to a ghost: supply an empty tree in
1702
2365
            this case.
1703
2366
        :param ghosts: A list of the revision_ids that are ghosts at the time
1704
2367
            of setting.
1705
 
        """ 
1706
 
        # TODO: generate a list of parent indexes to preserve to save 
 
2368
        """
 
2369
        # TODO: generate a list of parent indexes to preserve to save
1707
2370
        # processing specific parent trees. In the common case one tree will
1708
2371
        # be preserved - the left most parent.
1709
2372
        # TODO: if the parent tree is a dirstate, we might want to walk them
1714
2377
        # map and then walk the new parent trees only, mapping them into the
1715
2378
        # dirstate. Walk the dirstate at the same time to remove unreferenced
1716
2379
        # entries.
1717
 
        # for now: 
1718
 
        # sketch: loop over all entries in the dirstate, cherry picking 
 
2380
        # for now:
 
2381
        # sketch: loop over all entries in the dirstate, cherry picking
1719
2382
        # entries from the parent trees, if they are not ghost trees.
1720
2383
        # after we finish walking the dirstate, all entries not in the dirstate
1721
2384
        # are deletes, so we want to append them to the end as per the design
1726
2389
        #   links. We dont't trivially use the inventory from other trees
1727
2390
        #   because this leads to either double touching, or to accessing
1728
2391
        #   missing keys,
1729
 
        # - find other keys containing a path 
1730
 
        # We accumulate each entry via this dictionary, including the root 
 
2392
        # - find other keys containing a path
 
2393
        # We accumulate each entry via this dictionary, including the root
1731
2394
        by_path = {}
1732
2395
        id_index = {}
1733
2396
        # we could do parallel iterators, but because file id data may be
1737
2400
        # parent, but for now the common cases are adding a new parent (merge),
1738
2401
        # and replacing completely (commit), and commit is more common: so
1739
2402
        # optimise merge later.
1740
 
        
 
2403
 
1741
2404
        # ---- start generation of full tree mapping data
1742
2405
        # what trees should we use?
1743
2406
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
1744
 
        # how many trees do we end up with 
 
2407
        # how many trees do we end up with
1745
2408
        parent_count = len(parent_trees)
1746
2409
 
1747
2410
        # one: the current tree
1748
2411
        for entry in self._iter_entries():
1749
2412
            # skip entries not in the current tree
1750
 
            if entry[1][0][0] in ('a', 'r'): # absent, relocated
 
2413
            if entry[1][0][0] in 'ar': # absent, relocated
1751
2414
                continue
1752
2415
            by_path[entry[0]] = [entry[1][0]] + \
1753
2416
                [DirState.NULL_PARENT_DETAILS] * parent_count
1754
2417
            id_index[entry[0][2]] = set([entry[0]])
1755
 
        
 
2418
 
1756
2419
        # now the parent trees:
1757
2420
        for tree_index, tree in enumerate(parent_trees):
1758
2421
            # the index is off by one, adjust it.
1772
2435
                # avoid checking all known paths for the id when generating a
1773
2436
                # new entry at this path: by adding the id->path mapping last,
1774
2437
                # all the mappings are valid and have correct relocation
1775
 
                # records where needed. 
 
2438
                # records where needed.
1776
2439
                file_id = entry.file_id
1777
2440
                path_utf8 = path.encode('utf8')
1778
2441
                dirname, basename = osutils.split(path_utf8)
1787
2450
                        # this file id is at a different path in one of the
1788
2451
                        # other trees, so put absent pointers there
1789
2452
                        # This is the vertical axis in the matrix, all pointing
1790
 
                        # tot he real path.
 
2453
                        # to the real path.
1791
2454
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
1792
 
                # by path consistency: Insert into an existing path record (trivial), or 
 
2455
                # by path consistency: Insert into an existing path record (trivial), or
1793
2456
                # add a new one with relocation pointers for the other tree indexes.
1794
2457
                if new_entry_key in id_index[file_id]:
1795
2458
                    # there is already an entry where this data belongs, just insert it.
1808
2471
                            new_details.append(DirState.NULL_PARENT_DETAILS)
1809
2472
                        else:
1810
2473
                            # grab any one entry, use it to find the right path.
1811
 
                            # TODO: optimise this to reduce memory use in highly 
 
2474
                            # TODO: optimise this to reduce memory use in highly
1812
2475
                            # fragmented situations by reusing the relocation
1813
2476
                            # records.
1814
2477
                            a_key = iter(id_index[file_id]).next()
1841
2504
        try to keep everything in sorted blocks all the time, but sometimes
1842
2505
        it's easier to sort after the fact.
1843
2506
        """
1844
 
        # TODO: Might be faster to do a schwartzian transform?
1845
2507
        def _key(entry):
1846
2508
            # sort by: directory parts, file name, file id
1847
2509
            return entry[0][0].split('/'), entry[0][1], entry[0][2]
1848
2510
        return sorted(entry_list, key=_key)
1849
2511
 
1850
2512
    def set_state_from_inventory(self, new_inv):
1851
 
        """Set new_inv as the current state. 
 
2513
        """Set new_inv as the current state.
1852
2514
 
1853
2515
        This API is called by tree transform, and will usually occur with
1854
2516
        existing parent trees.
1855
2517
 
1856
2518
        :param new_inv: The inventory object to set current state from.
1857
2519
        """
 
2520
        if 'evil' in debug.debug_flags:
 
2521
            trace.mutter_callsite(1,
 
2522
                "set_state_from_inventory called; please mutate the tree instead")
 
2523
        tracing = 'dirstate' in debug.debug_flags
 
2524
        if tracing:
 
2525
            trace.mutter("set_state_from_inventory trace:")
1858
2526
        self._read_dirblocks_if_needed()
1859
2527
        # sketch:
1860
 
        # incremental algorithm:
1861
 
        # two iterators: current data and new data, both in dirblock order. 
 
2528
        # Two iterators: current data and new data, both in dirblock order.
 
2529
        # We zip them together, which tells about entries that are new in the
 
2530
        # inventory, or removed in the inventory, or present in both and
 
2531
        # possibly changed.
 
2532
        #
 
2533
        # You might think we could just synthesize a new dirstate directly
 
2534
        # since we're processing it in the right order.  However, we need to
 
2535
        # also consider there may be any number of parent trees and relocation
 
2536
        # pointers, and we don't want to duplicate that here.
1862
2537
        new_iterator = new_inv.iter_entries_by_dir()
1863
2538
        # we will be modifying the dirstate, so we need a stable iterator. In
1864
2539
        # future we might write one, for now we just clone the state into a
1865
 
        # list - which is a shallow copy, so each 
 
2540
        # list using a copy so that we see every original item and don't have
 
2541
        # to adjust the position when items are inserted or deleted in the
 
2542
        # underlying dirstate.
1866
2543
        old_iterator = iter(list(self._iter_entries()))
1867
2544
        # both must have roots so this is safe:
1868
2545
        current_new = new_iterator.next()
1874
2551
                return None
1875
2552
        while current_new or current_old:
1876
2553
            # skip entries in old that are not really there
1877
 
            if current_old and current_old[1][0][0] in ('r', 'a'):
 
2554
            if current_old and current_old[1][0][0] in 'ar':
1878
2555
                # relocated or absent
1879
2556
                current_old = advance(old_iterator)
1880
2557
                continue
1887
2564
                current_new_minikind = \
1888
2565
                    DirState._kind_to_minikind[current_new[1].kind]
1889
2566
                if current_new_minikind == 't':
1890
 
                    fingerprint = current_new[1].reference_revision
 
2567
                    fingerprint = current_new[1].reference_revision or ''
1891
2568
                else:
 
2569
                    # We normally only insert or remove records, or update
 
2570
                    # them when it has significantly changed.  Then we want to
 
2571
                    # erase its fingerprint.  Unaffected records should
 
2572
                    # normally not be updated at all.
1892
2573
                    fingerprint = ''
1893
2574
            else:
1894
2575
                # for safety disable variables
1895
 
                new_path_utf8 = new_dirname = new_basename = new_id = new_entry_key = None
 
2576
                new_path_utf8 = new_dirname = new_basename = new_id = \
 
2577
                    new_entry_key = None
1896
2578
            # 5 cases, we dont have a value that is strictly greater than everything, so
1897
2579
            # we make both end conditions explicit
1898
2580
            if not current_old:
1899
2581
                # old is finished: insert current_new into the state.
 
2582
                if tracing:
 
2583
                    trace.mutter("Appending from new '%s'.",
 
2584
                        new_path_utf8.decode('utf8'))
1900
2585
                self.update_minimal(new_entry_key, current_new_minikind,
1901
2586
                    executable=current_new[1].executable,
1902
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2587
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2588
                    fullscan=True)
1903
2589
                current_new = advance(new_iterator)
1904
2590
            elif not current_new:
1905
2591
                # new is finished
 
2592
                if tracing:
 
2593
                    trace.mutter("Truncating from old '%s/%s'.",
 
2594
                        current_old[0][0].decode('utf8'),
 
2595
                        current_old[0][1].decode('utf8'))
1906
2596
                self._make_absent(current_old)
1907
2597
                current_old = advance(old_iterator)
1908
2598
            elif new_entry_key == current_old[0]:
1909
2599
                # same -  common case
 
2600
                # We're looking at the same path and id in both the dirstate
 
2601
                # and inventory, so just need to update the fields in the
 
2602
                # dirstate from the one in the inventory.
1910
2603
                # TODO: update the record if anything significant has changed.
1911
2604
                # the minimal required trigger is if the execute bit or cached
1912
2605
                # kind has changed.
1913
2606
                if (current_old[1][0][3] != current_new[1].executable or
1914
2607
                    current_old[1][0][0] != current_new_minikind):
 
2608
                    if tracing:
 
2609
                        trace.mutter("Updating in-place change '%s'.",
 
2610
                            new_path_utf8.decode('utf8'))
1915
2611
                    self.update_minimal(current_old[0], current_new_minikind,
1916
2612
                        executable=current_new[1].executable,
1917
 
                        path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2613
                        path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2614
                        fullscan=True)
1918
2615
                # both sides are dealt with, move on
1919
2616
                current_old = advance(old_iterator)
1920
2617
                current_new = advance(new_iterator)
1921
 
            elif (new_entry_key[0].split('/') < current_old[0][0].split('/')
1922
 
                  and new_entry_key[1:] < current_old[0][1:]):
 
2618
            elif (cmp_by_dirs(new_dirname, current_old[0][0]) < 0
 
2619
                  or (new_dirname == current_old[0][0]
 
2620
                      and new_entry_key[1:] < current_old[0][1:])):
1923
2621
                # new comes before:
1924
2622
                # add a entry for this and advance new
 
2623
                if tracing:
 
2624
                    trace.mutter("Inserting from new '%s'.",
 
2625
                        new_path_utf8.decode('utf8'))
1925
2626
                self.update_minimal(new_entry_key, current_new_minikind,
1926
2627
                    executable=current_new[1].executable,
1927
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
 
2628
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
 
2629
                    fullscan=True)
1928
2630
                current_new = advance(new_iterator)
1929
2631
            else:
1930
 
                # old comes before:
 
2632
                # we've advanced past the place where the old key would be,
 
2633
                # without seeing it in the new list.  so it must be gone.
 
2634
                if tracing:
 
2635
                    trace.mutter("Deleting from old '%s/%s'.",
 
2636
                        current_old[0][0].decode('utf8'),
 
2637
                        current_old[0][1].decode('utf8'))
1931
2638
                self._make_absent(current_old)
1932
2639
                current_old = advance(old_iterator)
1933
2640
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1934
2641
        self._id_index = None
 
2642
        self._packed_stat_index = None
 
2643
        if tracing:
 
2644
            trace.mutter("set_state_from_inventory complete.")
1935
2645
 
1936
2646
    def _make_absent(self, current_old):
1937
2647
        """Mark current_old - an entry - as absent for tree 0.
1938
2648
 
1939
 
        :return: True if this was the last details entry for they entry key:
 
2649
        :return: True if this was the last details entry for the entry key:
1940
2650
            that is, if the underlying block has had the entry removed, thus
1941
2651
            shrinking in length.
1942
2652
        """
1943
2653
        # build up paths that this id will be left at after the change is made,
1944
2654
        # so we can update their cross references in tree 0
1945
2655
        all_remaining_keys = set()
1946
 
        # Dont check the working tree, because its going.
 
2656
        # Dont check the working tree, because it's going.
1947
2657
        for details in current_old[1][1:]:
1948
 
            if details[0] not in ('a', 'r'): # absent, relocated
 
2658
            if details[0] not in 'ar': # absent, relocated
1949
2659
                all_remaining_keys.add(current_old[0])
1950
2660
            elif details[0] == 'r': # relocated
1951
2661
                # record the key for the real path.
1958
2668
            # Remove it, its meaningless.
1959
2669
            block = self._find_block(current_old[0])
1960
2670
            entry_index, present = self._find_entry_index(current_old[0], block[1])
1961
 
            assert present, 'could not find entry for %s' % (current_old,)
 
2671
            if not present:
 
2672
                raise AssertionError('could not find entry for %s' % (current_old,))
1962
2673
            block[1].pop(entry_index)
1963
2674
            # if we have an id_index in use, remove this key from it for this id.
1964
2675
            if self._id_index is not None:
1965
2676
                self._id_index[current_old[0][2]].remove(current_old[0])
1966
2677
        # update all remaining keys for this id to record it as absent. The
1967
 
        # existing details may either be the record we are making as deleted
 
2678
        # existing details may either be the record we are marking as deleted
1968
2679
        # (if there were other trees with the id present at this path), or may
1969
2680
        # be relocations.
1970
2681
        for update_key in all_remaining_keys:
1971
2682
            update_block_index, present = \
1972
2683
                self._find_block_index_from_key(update_key)
1973
 
            assert present, 'could not find block for %s' % (update_key,)
 
2684
            if not present:
 
2685
                raise AssertionError('could not find block for %s' % (update_key,))
1974
2686
            update_entry_index, present = \
1975
2687
                self._find_entry_index(update_key, self._dirblocks[update_block_index][1])
1976
 
            assert present, 'could not find entry for %s' % (update_key,)
 
2688
            if not present:
 
2689
                raise AssertionError('could not find entry for %s' % (update_key,))
1977
2690
            update_tree_details = self._dirblocks[update_block_index][1][update_entry_index][1]
1978
2691
            # it must not be absent at the moment
1979
 
            assert update_tree_details[0][0] != 'a' # absent
 
2692
            if update_tree_details[0][0] == 'a': # absent
 
2693
                raise AssertionError('bad row %r' % (update_tree_details,))
1980
2694
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
1981
2695
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
1982
2696
        return last_reference
1983
2697
 
1984
2698
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
1985
 
                       packed_stat=None, size=0, path_utf8=None):
 
2699
        packed_stat=None, size=0, path_utf8=None, fullscan=False):
1986
2700
        """Update an entry to the state in tree 0.
1987
2701
 
1988
2702
        This will either create a new entry at 'key' or update an existing one.
1993
2707
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
1994
2708
                'directory'), etc.
1995
2709
        :param executable: Should the executable bit be set?
1996
 
        :param fingerprint: Simple fingerprint for new entry.
1997
 
        :param packed_stat: packed stat value for new entry.
 
2710
        :param fingerprint: Simple fingerprint for new entry: canonical-form
 
2711
            sha1 for files, referenced revision id for subtrees, etc.
 
2712
        :param packed_stat: Packed stat value for new entry.
1998
2713
        :param size: Size information for new entry
1999
2714
        :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
2000
2715
                extra computation.
 
2716
        :param fullscan: If True then a complete scan of the dirstate is being
 
2717
            done and checking for duplicate rows should not be done. This
 
2718
            should only be set by set_state_from_inventory and similar methods.
 
2719
 
 
2720
        If packed_stat and fingerprint are not given, they're invalidated in
 
2721
        the entry.
2001
2722
        """
2002
2723
        block = self._find_block(key)[1]
2003
2724
        if packed_stat is None:
2004
2725
            packed_stat = DirState.NULLSTAT
 
2726
        # XXX: Some callers pass '' as the packed_stat, and it seems to be
 
2727
        # sometimes present in the dirstate - this seems oddly inconsistent.
 
2728
        # mbp 20071008
2005
2729
        entry_index, present = self._find_entry_index(key, block)
2006
2730
        new_details = (minikind, fingerprint, size, executable, packed_stat)
2007
2731
        id_index = self._get_id_index()
2008
2732
        if not present:
 
2733
            # New record. Check there isn't a entry at this path already.
 
2734
            if not fullscan:
 
2735
                low_index, _ = self._find_entry_index(key[0:2] + ('',), block)
 
2736
                while low_index < len(block):
 
2737
                    entry = block[low_index]
 
2738
                    if entry[0][0:2] == key[0:2]:
 
2739
                        if entry[1][0][0] not in 'ar':
 
2740
                            # This entry has the same path (but a different id) as
 
2741
                            # the new entry we're adding, and is present in ths
 
2742
                            # tree.
 
2743
                            raise errors.InconsistentDelta(
 
2744
                                ("%s/%s" % key[0:2]).decode('utf8'), key[2],
 
2745
                                "Attempt to add item at path already occupied by "
 
2746
                                "id %r" % entry[0][2])
 
2747
                        low_index += 1
 
2748
                    else:
 
2749
                        break
2009
2750
            # new entry, synthesis cross reference here,
2010
2751
            existing_keys = id_index.setdefault(key[2], set())
2011
2752
            if not existing_keys:
2016
2757
                # grab one of them and use it to generate parent
2017
2758
                # relocation/absent entries.
2018
2759
                new_entry = key, [new_details]
2019
 
                for other_key in existing_keys:
 
2760
                # existing_keys can be changed as we iterate.
 
2761
                for other_key in tuple(existing_keys):
2020
2762
                    # change the record at other to be a pointer to this new
2021
2763
                    # record. The loop looks similar to the change to
2022
2764
                    # relocations when updating an existing record but its not:
2023
2765
                    # the test for existing kinds is different: this can be
2024
2766
                    # factored out to a helper though.
2025
 
                    other_block_index, present = self._find_block_index_from_key(other_key)
2026
 
                    assert present, 'could not find block for %s' % (other_key,)
2027
 
                    other_entry_index, present = self._find_entry_index(other_key,
2028
 
                                            self._dirblocks[other_block_index][1])
2029
 
                    assert present, 'could not find entry for %s' % (other_key,)
2030
 
                    assert path_utf8 is not None
2031
 
                    self._dirblocks[other_block_index][1][other_entry_index][1][0] = \
2032
 
                        ('r', path_utf8, 0, False, '')
 
2767
                    other_block_index, present = self._find_block_index_from_key(
 
2768
                        other_key)
 
2769
                    if not present:
 
2770
                        raise AssertionError('could not find block for %s' % (
 
2771
                            other_key,))
 
2772
                    other_block = self._dirblocks[other_block_index][1]
 
2773
                    other_entry_index, present = self._find_entry_index(
 
2774
                        other_key, other_block)
 
2775
                    if not present:
 
2776
                        raise AssertionError(
 
2777
                            'update_minimal: could not find other entry for %s'
 
2778
                            % (other_key,))
 
2779
                    if path_utf8 is None:
 
2780
                        raise AssertionError('no path')
 
2781
                    # Turn this other location into a reference to the new
 
2782
                    # location. This also updates the aliased iterator
 
2783
                    # (current_old in set_state_from_inventory) so that the old
 
2784
                    # entry, if not already examined, is skipped over by that
 
2785
                    # loop.
 
2786
                    other_entry = other_block[other_entry_index]
 
2787
                    other_entry[1][0] = ('r', path_utf8, 0, False, '')
 
2788
                    self._maybe_remove_row(other_block, other_entry_index,
 
2789
                        id_index)
2033
2790
 
 
2791
                # This loop:
 
2792
                # adds a tuple to the new details for each column
 
2793
                #  - either by copying an existing relocation pointer inside that column
 
2794
                #  - or by creating a new pointer to the right row inside that column
2034
2795
                num_present_parents = self._num_present_parents()
 
2796
                if num_present_parents:
 
2797
                    other_key = list(existing_keys)[0]
2035
2798
                for lookup_index in xrange(1, num_present_parents + 1):
2036
2799
                    # grab any one entry, use it to find the right path.
2037
 
                    # TODO: optimise this to reduce memory use in highly 
 
2800
                    # TODO: optimise this to reduce memory use in highly
2038
2801
                    # fragmented situations by reusing the relocation
2039
2802
                    # records.
2040
2803
                    update_block_index, present = \
2041
2804
                        self._find_block_index_from_key(other_key)
2042
 
                    assert present, 'could not find block for %s' % (other_key,)
 
2805
                    if not present:
 
2806
                        raise AssertionError('could not find block for %s' % (other_key,))
2043
2807
                    update_entry_index, present = \
2044
2808
                        self._find_entry_index(other_key, self._dirblocks[update_block_index][1])
2045
 
                    assert present, 'could not find entry for %s' % (other_key,)
 
2809
                    if not present:
 
2810
                        raise AssertionError('update_minimal: could not find entry for %s' % (other_key,))
2046
2811
                    update_details = self._dirblocks[update_block_index][1][update_entry_index][1][lookup_index]
2047
 
                    if update_details[0] in ('r', 'a'): # relocated, absent
 
2812
                    if update_details[0] in 'ar': # relocated, absent
2048
2813
                        # its a pointer or absent in lookup_index's tree, use
2049
2814
                        # it as is.
2050
2815
                        new_entry[1].append(update_details)
2055
2820
            block.insert(entry_index, new_entry)
2056
2821
            existing_keys.add(key)
2057
2822
        else:
2058
 
            # Does the new state matter? 
 
2823
            # Does the new state matter?
2059
2824
            block[entry_index][1][0] = new_details
2060
2825
            # parents cannot be affected by what we do.
2061
 
            # other occurences of this id can be found 
 
2826
            # other occurences of this id can be found
2062
2827
            # from the id index.
2063
2828
            # ---
2064
2829
            # tree index consistency: All other paths for this id in this tree
2066
2831
            # we may have passed entries in the state with this file id already
2067
2832
            # that were absent - where parent entries are - and they need to be
2068
2833
            # converted to relocated.
2069
 
            assert path_utf8 is not None
 
2834
            if path_utf8 is None:
 
2835
                raise AssertionError('no path')
2070
2836
            for entry_key in id_index.setdefault(key[2], set()):
2071
2837
                # TODO:PROFILING: It might be faster to just update
2072
2838
                # rather than checking if we need to, and then overwrite
2077
2843
                    # This is the vertical axis in the matrix, all pointing
2078
2844
                    # to the real path.
2079
2845
                    block_index, present = self._find_block_index_from_key(entry_key)
2080
 
                    assert present
 
2846
                    if not present:
 
2847
                        raise AssertionError('not present: %r', entry_key)
2081
2848
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
2082
 
                    assert present
 
2849
                    if not present:
 
2850
                        raise AssertionError('not present: %r', entry_key)
2083
2851
                    self._dirblocks[block_index][1][entry_index][1][0] = \
2084
2852
                        ('r', path_utf8, 0, False, '')
2085
2853
        # add a containing dirblock if needed.
2091
2859
 
2092
2860
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2093
2861
 
 
2862
    def _maybe_remove_row(self, block, index, id_index):
 
2863
        """Remove index if it is absent or relocated across the row.
 
2864
        
 
2865
        id_index is updated accordingly.
 
2866
        """
 
2867
        present_in_row = False
 
2868
        entry = block[index]
 
2869
        for column in entry[1]:
 
2870
            if column[0] not in 'ar':
 
2871
                present_in_row = True
 
2872
                break
 
2873
        if not present_in_row:
 
2874
            block.pop(index)
 
2875
            id_index[entry[0][2]].remove(entry[0])
 
2876
 
2094
2877
    def _validate(self):
2095
2878
        """Check that invariants on the dirblock are correct.
2096
2879
 
2097
 
        This can be useful in debugging; it shouldn't be necessary in 
 
2880
        This can be useful in debugging; it shouldn't be necessary in
2098
2881
        normal code.
2099
2882
 
2100
2883
        This must be called with a lock held.
2116
2899
            if not self._dirblocks[0][0] == '':
2117
2900
                raise AssertionError(
2118
2901
                    "dirblocks don't start with root block:\n" + \
2119
 
                    pformat(dirblocks))
 
2902
                    pformat(self._dirblocks))
2120
2903
        if len(self._dirblocks) > 1:
2121
2904
            if not self._dirblocks[1][0] == '':
2122
2905
                raise AssertionError(
2123
2906
                    "dirblocks missing root directory:\n" + \
2124
 
                    pformat(dirblocks))
 
2907
                    pformat(self._dirblocks))
2125
2908
        # the dirblocks are sorted by their path components, name, and dir id
2126
2909
        dir_names = [d[0].split('/')
2127
2910
                for d in self._dirblocks[1:]]
2145
2928
                    "dirblock for %r is not sorted:\n%s" % \
2146
2929
                    (dirblock[0], pformat(dirblock)))
2147
2930
 
2148
 
 
2149
2931
        def check_valid_parent():
2150
2932
            """Check that the current entry has a valid parent.
2151
2933
 
2170
2952
        # For each file id, for each tree: either
2171
2953
        # the file id is not present at all; all rows with that id in the
2172
2954
        # key have it marked as 'absent'
2173
 
        # OR the file id is present under exactly one name; any other entries 
 
2955
        # OR the file id is present under exactly one name; any other entries
2174
2956
        # that mention that id point to the correct name.
2175
2957
        #
2176
2958
        # We check this with a dict per tree pointing either to the present
2186
2968
                "wrong number of entry details for row\n%s" \
2187
2969
                ",\nexpected %d" % \
2188
2970
                (pformat(entry), tree_count))
 
2971
            absent_positions = 0
2189
2972
            for tree_index, tree_state in enumerate(entry[1]):
2190
2973
                this_tree_map = id_path_maps[tree_index]
2191
2974
                minikind = tree_state[0]
 
2975
                if minikind in 'ar':
 
2976
                    absent_positions += 1
2192
2977
                # have we seen this id before in this column?
2193
2978
                if file_id in this_tree_map:
2194
 
                    previous_path = this_tree_map[file_id]
 
2979
                    previous_path, previous_loc = this_tree_map[file_id]
2195
2980
                    # any later mention of this file must be consistent with
2196
2981
                    # what was said before
2197
2982
                    if minikind == 'a':
2211
2996
                        # pointed to by a relocation, which must point here
2212
2997
                        if previous_path != this_path:
2213
2998
                            raise AssertionError(
2214
 
                            "entry %r inconsistent with previous path %r" % \
2215
 
                            (entry, previous_path))
 
2999
                                "entry %r inconsistent with previous path %r "
 
3000
                                "seen at %r" %
 
3001
                                (entry, previous_path, previous_loc))
2216
3002
                        check_valid_parent()
2217
3003
                else:
2218
3004
                    if minikind == 'a':
2219
3005
                        # absent; should not occur anywhere else
2220
 
                        this_tree_map[file_id] = None
 
3006
                        this_tree_map[file_id] = None, this_path
2221
3007
                    elif minikind == 'r':
2222
 
                        # relocation, must occur at expected location 
2223
 
                        this_tree_map[file_id] = tree_state[1]
 
3008
                        # relocation, must occur at expected location
 
3009
                        this_tree_map[file_id] = tree_state[1], this_path
2224
3010
                    else:
2225
 
                        this_tree_map[file_id] = this_path
 
3011
                        this_tree_map[file_id] = this_path, this_path
2226
3012
                        check_valid_parent()
 
3013
            if absent_positions == tree_count:
 
3014
                raise AssertionError(
 
3015
                    "entry %r has no data for any tree." % (entry,))
 
3016
        if self._id_index is not None:
 
3017
            for file_id, entry_keys in self._id_index.iteritems():
 
3018
                for entry_key in entry_keys:
 
3019
                    if entry_key[2] != file_id:
 
3020
                        raise AssertionError(
 
3021
                            'file_id %r did not match entry key %s'
 
3022
                            % (file_id, entry_key))
2227
3023
 
2228
3024
    def _wipe_state(self):
2229
3025
        """Forget all state information about the dirstate."""
2230
3026
        self._header_state = DirState.NOT_IN_MEMORY
2231
3027
        self._dirblock_state = DirState.NOT_IN_MEMORY
 
3028
        self._changes_aborted = False
2232
3029
        self._parents = []
2233
3030
        self._ghosts = []
2234
3031
        self._dirblocks = []
2235
3032
        self._id_index = None
 
3033
        self._packed_stat_index = None
2236
3034
        self._end_of_header = None
2237
3035
        self._cutoff_time = None
2238
3036
        self._split_path_cache = {}
2239
3037
 
2240
3038
    def lock_read(self):
2241
 
        """Acquire a read lock on the dirstate"""
 
3039
        """Acquire a read lock on the dirstate."""
2242
3040
        if self._lock_token is not None:
2243
3041
            raise errors.LockContention(self._lock_token)
2244
3042
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2251
3049
        self._wipe_state()
2252
3050
 
2253
3051
    def lock_write(self):
2254
 
        """Acquire a write lock on the dirstate"""
 
3052
        """Acquire a write lock on the dirstate."""
2255
3053
        if self._lock_token is not None:
2256
3054
            raise errors.LockContention(self._lock_token)
2257
3055
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2264
3062
        self._wipe_state()
2265
3063
 
2266
3064
    def unlock(self):
2267
 
        """Drop any locks held on the dirstate"""
 
3065
        """Drop any locks held on the dirstate."""
2268
3066
        if self._lock_token is None:
2269
3067
            raise errors.LockNotHeld(self)
2270
3068
        # TODO: jam 20070301 Rather than wiping completely, if the blocks are
2278
3076
        self._split_path_cache = {}
2279
3077
 
2280
3078
    def _requires_lock(self):
2281
 
        """Checks that a lock is currently held by someone on the dirstate"""
 
3079
        """Check that a lock is currently held by someone on the dirstate."""
2282
3080
        if not self._lock_token:
2283
3081
            raise errors.ObjectNotLocked(self)
2284
3082
 
2285
3083
 
 
3084
def py_update_entry(state, entry, abspath, stat_value,
 
3085
                 _stat_to_minikind=DirState._stat_to_minikind,
 
3086
                 _pack_stat=pack_stat):
 
3087
    """Update the entry based on what is actually on disk.
 
3088
 
 
3089
    This function only calculates the sha if it needs to - if the entry is
 
3090
    uncachable, or clearly different to the first parent's entry, no sha
 
3091
    is calculated, and None is returned.
 
3092
 
 
3093
    :param state: The dirstate this entry is in.
 
3094
    :param entry: This is the dirblock entry for the file in question.
 
3095
    :param abspath: The path on disk for this file.
 
3096
    :param stat_value: The stat value done on the path.
 
3097
    :return: None, or The sha1 hexdigest of the file (40 bytes) or link
 
3098
        target of a symlink.
 
3099
    """
 
3100
    try:
 
3101
        minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
 
3102
    except KeyError:
 
3103
        # Unhandled kind
 
3104
        return None
 
3105
    packed_stat = _pack_stat(stat_value)
 
3106
    (saved_minikind, saved_link_or_sha1, saved_file_size,
 
3107
     saved_executable, saved_packed_stat) = entry[1][0]
 
3108
 
 
3109
    if minikind == 'd' and saved_minikind == 't':
 
3110
        minikind = 't'
 
3111
    if (minikind == saved_minikind
 
3112
        and packed_stat == saved_packed_stat):
 
3113
        # The stat hasn't changed since we saved, so we can re-use the
 
3114
        # saved sha hash.
 
3115
        if minikind == 'd':
 
3116
            return None
 
3117
 
 
3118
        # size should also be in packed_stat
 
3119
        if saved_file_size == stat_value.st_size:
 
3120
            return saved_link_or_sha1
 
3121
 
 
3122
    # If we have gotten this far, that means that we need to actually
 
3123
    # process this entry.
 
3124
    link_or_sha1 = None
 
3125
    if minikind == 'f':
 
3126
        executable = state._is_executable(stat_value.st_mode,
 
3127
                                         saved_executable)
 
3128
        if state._cutoff_time is None:
 
3129
            state._sha_cutoff_time()
 
3130
        if (stat_value.st_mtime < state._cutoff_time
 
3131
            and stat_value.st_ctime < state._cutoff_time
 
3132
            and len(entry[1]) > 1
 
3133
            and entry[1][1][0] != 'a'):
 
3134
            # Could check for size changes for further optimised
 
3135
            # avoidance of sha1's. However the most prominent case of
 
3136
            # over-shaing is during initial add, which this catches.
 
3137
            # Besides, if content filtering happens, size and sha
 
3138
            # are calculated at the same time, so checking just the size
 
3139
            # gains nothing w.r.t. performance.
 
3140
            link_or_sha1 = state._sha1_file(abspath)
 
3141
            entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
 
3142
                           executable, packed_stat)
 
3143
        else:
 
3144
            entry[1][0] = ('f', '', stat_value.st_size,
 
3145
                           executable, DirState.NULLSTAT)
 
3146
    elif minikind == 'd':
 
3147
        link_or_sha1 = None
 
3148
        entry[1][0] = ('d', '', 0, False, packed_stat)
 
3149
        if saved_minikind != 'd':
 
3150
            # This changed from something into a directory. Make sure we
 
3151
            # have a directory block for it. This doesn't happen very
 
3152
            # often, so this doesn't have to be super fast.
 
3153
            block_index, entry_index, dir_present, file_present = \
 
3154
                state._get_block_entry_index(entry[0][0], entry[0][1], 0)
 
3155
            state._ensure_block(block_index, entry_index,
 
3156
                               osutils.pathjoin(entry[0][0], entry[0][1]))
 
3157
    elif minikind == 'l':
 
3158
        link_or_sha1 = state._read_link(abspath, saved_link_or_sha1)
 
3159
        if state._cutoff_time is None:
 
3160
            state._sha_cutoff_time()
 
3161
        if (stat_value.st_mtime < state._cutoff_time
 
3162
            and stat_value.st_ctime < state._cutoff_time):
 
3163
            entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
 
3164
                           False, packed_stat)
 
3165
        else:
 
3166
            entry[1][0] = ('l', '', stat_value.st_size,
 
3167
                           False, DirState.NULLSTAT)
 
3168
    state._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
3169
    return link_or_sha1
 
3170
 
 
3171
 
 
3172
class ProcessEntryPython(object):
 
3173
 
 
3174
    __slots__ = ["old_dirname_to_file_id", "new_dirname_to_file_id",
 
3175
        "last_source_parent", "last_target_parent", "include_unchanged",
 
3176
        "partial", "use_filesystem_for_exec", "utf8_decode",
 
3177
        "searched_specific_files", "search_specific_files",
 
3178
        "searched_exact_paths", "search_specific_file_parents", "seen_ids",
 
3179
        "state", "source_index", "target_index", "want_unversioned", "tree"]
 
3180
 
 
3181
    def __init__(self, include_unchanged, use_filesystem_for_exec,
 
3182
        search_specific_files, state, source_index, target_index,
 
3183
        want_unversioned, tree):
 
3184
        self.old_dirname_to_file_id = {}
 
3185
        self.new_dirname_to_file_id = {}
 
3186
        # Are we doing a partial iter_changes?
 
3187
        self.partial = search_specific_files != set([''])
 
3188
        # Using a list so that we can access the values and change them in
 
3189
        # nested scope. Each one is [path, file_id, entry]
 
3190
        self.last_source_parent = [None, None]
 
3191
        self.last_target_parent = [None, None]
 
3192
        self.include_unchanged = include_unchanged
 
3193
        self.use_filesystem_for_exec = use_filesystem_for_exec
 
3194
        self.utf8_decode = cache_utf8._utf8_decode
 
3195
        # for all search_indexs in each path at or under each element of
 
3196
        # search_specific_files, if the detail is relocated: add the id, and
 
3197
        # add the relocated path as one to search if its not searched already.
 
3198
        # If the detail is not relocated, add the id.
 
3199
        self.searched_specific_files = set()
 
3200
        # When we search exact paths without expanding downwards, we record
 
3201
        # that here.
 
3202
        self.searched_exact_paths = set()
 
3203
        self.search_specific_files = search_specific_files
 
3204
        # The parents up to the root of the paths we are searching.
 
3205
        # After all normal paths are returned, these specific items are returned.
 
3206
        self.search_specific_file_parents = set()
 
3207
        # The ids we've sent out in the delta.
 
3208
        self.seen_ids = set()
 
3209
        self.state = state
 
3210
        self.source_index = source_index
 
3211
        self.target_index = target_index
 
3212
        if target_index != 0:
 
3213
            # A lot of code in here depends on target_index == 0
 
3214
            raise errors.BzrError('unsupported target index')
 
3215
        self.want_unversioned = want_unversioned
 
3216
        self.tree = tree
 
3217
 
 
3218
    def _process_entry(self, entry, path_info, pathjoin=osutils.pathjoin):
 
3219
        """Compare an entry and real disk to generate delta information.
 
3220
 
 
3221
        :param path_info: top_relpath, basename, kind, lstat, abspath for
 
3222
            the path of entry. If None, then the path is considered absent in 
 
3223
            the target (Perhaps we should pass in a concrete entry for this ?)
 
3224
            Basename is returned as a utf8 string because we expect this
 
3225
            tuple will be ignored, and don't want to take the time to
 
3226
            decode.
 
3227
        :return: (iter_changes_result, changed). If the entry has not been
 
3228
            handled then changed is None. Otherwise it is False if no content
 
3229
            or metadata changes have occurred, and True if any content or
 
3230
            metadata change has occurred. If self.include_unchanged is True then
 
3231
            if changed is not None, iter_changes_result will always be a result
 
3232
            tuple. Otherwise, iter_changes_result is None unless changed is
 
3233
            True.
 
3234
        """
 
3235
        if self.source_index is None:
 
3236
            source_details = DirState.NULL_PARENT_DETAILS
 
3237
        else:
 
3238
            source_details = entry[1][self.source_index]
 
3239
        target_details = entry[1][self.target_index]
 
3240
        target_minikind = target_details[0]
 
3241
        if path_info is not None and target_minikind in 'fdlt':
 
3242
            if not (self.target_index == 0):
 
3243
                raise AssertionError()
 
3244
            link_or_sha1 = update_entry(self.state, entry,
 
3245
                abspath=path_info[4], stat_value=path_info[3])
 
3246
            # The entry may have been modified by update_entry
 
3247
            target_details = entry[1][self.target_index]
 
3248
            target_minikind = target_details[0]
 
3249
        else:
 
3250
            link_or_sha1 = None
 
3251
        file_id = entry[0][2]
 
3252
        source_minikind = source_details[0]
 
3253
        if source_minikind in 'fdltr' and target_minikind in 'fdlt':
 
3254
            # claimed content in both: diff
 
3255
            #   r    | fdlt   |      | add source to search, add id path move and perform
 
3256
            #        |        |      | diff check on source-target
 
3257
            #   r    | fdlt   |  a   | dangling file that was present in the basis.
 
3258
            #        |        |      | ???
 
3259
            if source_minikind in 'r':
 
3260
                # add the source to the search path to find any children it
 
3261
                # has.  TODO ? : only add if it is a container ?
 
3262
                if not osutils.is_inside_any(self.searched_specific_files,
 
3263
                                             source_details[1]):
 
3264
                    self.search_specific_files.add(source_details[1])
 
3265
                # generate the old path; this is needed for stating later
 
3266
                # as well.
 
3267
                old_path = source_details[1]
 
3268
                old_dirname, old_basename = os.path.split(old_path)
 
3269
                path = pathjoin(entry[0][0], entry[0][1])
 
3270
                old_entry = self.state._get_entry(self.source_index,
 
3271
                                             path_utf8=old_path)
 
3272
                # update the source details variable to be the real
 
3273
                # location.
 
3274
                if old_entry == (None, None):
 
3275
                    raise errors.CorruptDirstate(self.state._filename,
 
3276
                        "entry '%s/%s' is considered renamed from %r"
 
3277
                        " but source does not exist\n"
 
3278
                        "entry: %s" % (entry[0][0], entry[0][1], old_path, entry))
 
3279
                source_details = old_entry[1][self.source_index]
 
3280
                source_minikind = source_details[0]
 
3281
            else:
 
3282
                old_dirname = entry[0][0]
 
3283
                old_basename = entry[0][1]
 
3284
                old_path = path = None
 
3285
            if path_info is None:
 
3286
                # the file is missing on disk, show as removed.
 
3287
                content_change = True
 
3288
                target_kind = None
 
3289
                target_exec = False
 
3290
            else:
 
3291
                # source and target are both versioned and disk file is present.
 
3292
                target_kind = path_info[2]
 
3293
                if target_kind == 'directory':
 
3294
                    if path is None:
 
3295
                        old_path = path = pathjoin(old_dirname, old_basename)
 
3296
                    self.new_dirname_to_file_id[path] = file_id
 
3297
                    if source_minikind != 'd':
 
3298
                        content_change = True
 
3299
                    else:
 
3300
                        # directories have no fingerprint
 
3301
                        content_change = False
 
3302
                    target_exec = False
 
3303
                elif target_kind == 'file':
 
3304
                    if source_minikind != 'f':
 
3305
                        content_change = True
 
3306
                    else:
 
3307
                        # Check the sha. We can't just rely on the size as
 
3308
                        # content filtering may mean differ sizes actually
 
3309
                        # map to the same content
 
3310
                        if link_or_sha1 is None:
 
3311
                            # Stat cache miss:
 
3312
                            statvalue, link_or_sha1 = \
 
3313
                                self.state._sha1_provider.stat_and_sha1(
 
3314
                                path_info[4])
 
3315
                            self.state._observed_sha1(entry, link_or_sha1,
 
3316
                                statvalue)
 
3317
                        content_change = (link_or_sha1 != source_details[1])
 
3318
                    # Target details is updated at update_entry time
 
3319
                    if self.use_filesystem_for_exec:
 
3320
                        # We don't need S_ISREG here, because we are sure
 
3321
                        # we are dealing with a file.
 
3322
                        target_exec = bool(stat.S_IEXEC & path_info[3].st_mode)
 
3323
                    else:
 
3324
                        target_exec = target_details[3]
 
3325
                elif target_kind == 'symlink':
 
3326
                    if source_minikind != 'l':
 
3327
                        content_change = True
 
3328
                    else:
 
3329
                        content_change = (link_or_sha1 != source_details[1])
 
3330
                    target_exec = False
 
3331
                elif target_kind == 'tree-reference':
 
3332
                    if source_minikind != 't':
 
3333
                        content_change = True
 
3334
                    else:
 
3335
                        content_change = False
 
3336
                    target_exec = False
 
3337
                else:
 
3338
                    if path is None:
 
3339
                        path = pathjoin(old_dirname, old_basename)
 
3340
                    raise errors.BadFileKindError(path, path_info[2])
 
3341
            if source_minikind == 'd':
 
3342
                if path is None:
 
3343
                    old_path = path = pathjoin(old_dirname, old_basename)
 
3344
                self.old_dirname_to_file_id[old_path] = file_id
 
3345
            # parent id is the entry for the path in the target tree
 
3346
            if old_basename and old_dirname == self.last_source_parent[0]:
 
3347
                source_parent_id = self.last_source_parent[1]
 
3348
            else:
 
3349
                try:
 
3350
                    source_parent_id = self.old_dirname_to_file_id[old_dirname]
 
3351
                except KeyError:
 
3352
                    source_parent_entry = self.state._get_entry(self.source_index,
 
3353
                                                           path_utf8=old_dirname)
 
3354
                    source_parent_id = source_parent_entry[0][2]
 
3355
                if source_parent_id == entry[0][2]:
 
3356
                    # This is the root, so the parent is None
 
3357
                    source_parent_id = None
 
3358
                else:
 
3359
                    self.last_source_parent[0] = old_dirname
 
3360
                    self.last_source_parent[1] = source_parent_id
 
3361
            new_dirname = entry[0][0]
 
3362
            if entry[0][1] and new_dirname == self.last_target_parent[0]:
 
3363
                target_parent_id = self.last_target_parent[1]
 
3364
            else:
 
3365
                try:
 
3366
                    target_parent_id = self.new_dirname_to_file_id[new_dirname]
 
3367
                except KeyError:
 
3368
                    # TODO: We don't always need to do the lookup, because the
 
3369
                    #       parent entry will be the same as the source entry.
 
3370
                    target_parent_entry = self.state._get_entry(self.target_index,
 
3371
                                                           path_utf8=new_dirname)
 
3372
                    if target_parent_entry == (None, None):
 
3373
                        raise AssertionError(
 
3374
                            "Could not find target parent in wt: %s\nparent of: %s"
 
3375
                            % (new_dirname, entry))
 
3376
                    target_parent_id = target_parent_entry[0][2]
 
3377
                if target_parent_id == entry[0][2]:
 
3378
                    # This is the root, so the parent is None
 
3379
                    target_parent_id = None
 
3380
                else:
 
3381
                    self.last_target_parent[0] = new_dirname
 
3382
                    self.last_target_parent[1] = target_parent_id
 
3383
 
 
3384
            source_exec = source_details[3]
 
3385
            changed = (content_change
 
3386
                or source_parent_id != target_parent_id
 
3387
                or old_basename != entry[0][1]
 
3388
                or source_exec != target_exec
 
3389
                )
 
3390
            if not changed and not self.include_unchanged:
 
3391
                return None, False
 
3392
            else:
 
3393
                if old_path is None:
 
3394
                    old_path = path = pathjoin(old_dirname, old_basename)
 
3395
                    old_path_u = self.utf8_decode(old_path)[0]
 
3396
                    path_u = old_path_u
 
3397
                else:
 
3398
                    old_path_u = self.utf8_decode(old_path)[0]
 
3399
                    if old_path == path:
 
3400
                        path_u = old_path_u
 
3401
                    else:
 
3402
                        path_u = self.utf8_decode(path)[0]
 
3403
                source_kind = DirState._minikind_to_kind[source_minikind]
 
3404
                return (entry[0][2],
 
3405
                       (old_path_u, path_u),
 
3406
                       content_change,
 
3407
                       (True, True),
 
3408
                       (source_parent_id, target_parent_id),
 
3409
                       (self.utf8_decode(old_basename)[0], self.utf8_decode(entry[0][1])[0]),
 
3410
                       (source_kind, target_kind),
 
3411
                       (source_exec, target_exec)), changed
 
3412
        elif source_minikind in 'a' and target_minikind in 'fdlt':
 
3413
            # looks like a new file
 
3414
            path = pathjoin(entry[0][0], entry[0][1])
 
3415
            # parent id is the entry for the path in the target tree
 
3416
            # TODO: these are the same for an entire directory: cache em.
 
3417
            parent_id = self.state._get_entry(self.target_index,
 
3418
                                         path_utf8=entry[0][0])[0][2]
 
3419
            if parent_id == entry[0][2]:
 
3420
                parent_id = None
 
3421
            if path_info is not None:
 
3422
                # Present on disk:
 
3423
                if self.use_filesystem_for_exec:
 
3424
                    # We need S_ISREG here, because we aren't sure if this
 
3425
                    # is a file or not.
 
3426
                    target_exec = bool(
 
3427
                        stat.S_ISREG(path_info[3].st_mode)
 
3428
                        and stat.S_IEXEC & path_info[3].st_mode)
 
3429
                else:
 
3430
                    target_exec = target_details[3]
 
3431
                return (entry[0][2],
 
3432
                       (None, self.utf8_decode(path)[0]),
 
3433
                       True,
 
3434
                       (False, True),
 
3435
                       (None, parent_id),
 
3436
                       (None, self.utf8_decode(entry[0][1])[0]),
 
3437
                       (None, path_info[2]),
 
3438
                       (None, target_exec)), True
 
3439
            else:
 
3440
                # Its a missing file, report it as such.
 
3441
                return (entry[0][2],
 
3442
                       (None, self.utf8_decode(path)[0]),
 
3443
                       False,
 
3444
                       (False, True),
 
3445
                       (None, parent_id),
 
3446
                       (None, self.utf8_decode(entry[0][1])[0]),
 
3447
                       (None, None),
 
3448
                       (None, False)), True
 
3449
        elif source_minikind in 'fdlt' and target_minikind in 'a':
 
3450
            # unversioned, possibly, or possibly not deleted: we dont care.
 
3451
            # if its still on disk, *and* theres no other entry at this
 
3452
            # path [we dont know this in this routine at the moment -
 
3453
            # perhaps we should change this - then it would be an unknown.
 
3454
            old_path = pathjoin(entry[0][0], entry[0][1])
 
3455
            # parent id is the entry for the path in the target tree
 
3456
            parent_id = self.state._get_entry(self.source_index, path_utf8=entry[0][0])[0][2]
 
3457
            if parent_id == entry[0][2]:
 
3458
                parent_id = None
 
3459
            return (entry[0][2],
 
3460
                   (self.utf8_decode(old_path)[0], None),
 
3461
                   True,
 
3462
                   (True, False),
 
3463
                   (parent_id, None),
 
3464
                   (self.utf8_decode(entry[0][1])[0], None),
 
3465
                   (DirState._minikind_to_kind[source_minikind], None),
 
3466
                   (source_details[3], None)), True
 
3467
        elif source_minikind in 'fdlt' and target_minikind in 'r':
 
3468
            # a rename; could be a true rename, or a rename inherited from
 
3469
            # a renamed parent. TODO: handle this efficiently. Its not
 
3470
            # common case to rename dirs though, so a correct but slow
 
3471
            # implementation will do.
 
3472
            if not osutils.is_inside_any(self.searched_specific_files, target_details[1]):
 
3473
                self.search_specific_files.add(target_details[1])
 
3474
        elif source_minikind in 'ra' and target_minikind in 'ra':
 
3475
            # neither of the selected trees contain this file,
 
3476
            # so skip over it. This is not currently directly tested, but
 
3477
            # is indirectly via test_too_much.TestCommands.test_conflicts.
 
3478
            pass
 
3479
        else:
 
3480
            raise AssertionError("don't know how to compare "
 
3481
                "source_minikind=%r, target_minikind=%r"
 
3482
                % (source_minikind, target_minikind))
 
3483
            ## import pdb;pdb.set_trace()
 
3484
        return None, None
 
3485
 
 
3486
    def __iter__(self):
 
3487
        return self
 
3488
 
 
3489
    def _gather_result_for_consistency(self, result):
 
3490
        """Check a result we will yield to make sure we are consistent later.
 
3491
        
 
3492
        This gathers result's parents into a set to output later.
 
3493
 
 
3494
        :param result: A result tuple.
 
3495
        """
 
3496
        if not self.partial or not result[0]:
 
3497
            return
 
3498
        self.seen_ids.add(result[0])
 
3499
        new_path = result[1][1]
 
3500
        if new_path:
 
3501
            # Not the root and not a delete: queue up the parents of the path.
 
3502
            self.search_specific_file_parents.update(
 
3503
                osutils.parent_directories(new_path.encode('utf8')))
 
3504
            # Add the root directory which parent_directories does not
 
3505
            # provide.
 
3506
            self.search_specific_file_parents.add('')
 
3507
 
 
3508
    def iter_changes(self):
 
3509
        """Iterate over the changes."""
 
3510
        utf8_decode = cache_utf8._utf8_decode
 
3511
        _cmp_by_dirs = cmp_by_dirs
 
3512
        _process_entry = self._process_entry
 
3513
        search_specific_files = self.search_specific_files
 
3514
        searched_specific_files = self.searched_specific_files
 
3515
        splitpath = osutils.splitpath
 
3516
        # sketch:
 
3517
        # compare source_index and target_index at or under each element of search_specific_files.
 
3518
        # follow the following comparison table. Note that we only want to do diff operations when
 
3519
        # the target is fdl because thats when the walkdirs logic will have exposed the pathinfo
 
3520
        # for the target.
 
3521
        # cases:
 
3522
        #
 
3523
        # Source | Target | disk | action
 
3524
        #   r    | fdlt   |      | add source to search, add id path move and perform
 
3525
        #        |        |      | diff check on source-target
 
3526
        #   r    | fdlt   |  a   | dangling file that was present in the basis.
 
3527
        #        |        |      | ???
 
3528
        #   r    |  a     |      | add source to search
 
3529
        #   r    |  a     |  a   |
 
3530
        #   r    |  r     |      | this path is present in a non-examined tree, skip.
 
3531
        #   r    |  r     |  a   | this path is present in a non-examined tree, skip.
 
3532
        #   a    | fdlt   |      | add new id
 
3533
        #   a    | fdlt   |  a   | dangling locally added file, skip
 
3534
        #   a    |  a     |      | not present in either tree, skip
 
3535
        #   a    |  a     |  a   | not present in any tree, skip
 
3536
        #   a    |  r     |      | not present in either tree at this path, skip as it
 
3537
        #        |        |      | may not be selected by the users list of paths.
 
3538
        #   a    |  r     |  a   | not present in either tree at this path, skip as it
 
3539
        #        |        |      | may not be selected by the users list of paths.
 
3540
        #  fdlt  | fdlt   |      | content in both: diff them
 
3541
        #  fdlt  | fdlt   |  a   | deleted locally, but not unversioned - show as deleted ?
 
3542
        #  fdlt  |  a     |      | unversioned: output deleted id for now
 
3543
        #  fdlt  |  a     |  a   | unversioned and deleted: output deleted id
 
3544
        #  fdlt  |  r     |      | relocated in this tree, so add target to search.
 
3545
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
 
3546
        #        |        |      | this id at the other path.
 
3547
        #  fdlt  |  r     |  a   | relocated in this tree, so add target to search.
 
3548
        #        |        |      | Dont diff, we will see an r,fd; pair when we reach
 
3549
        #        |        |      | this id at the other path.
 
3550
 
 
3551
        # TODO: jam 20070516 - Avoid the _get_entry lookup overhead by
 
3552
        #       keeping a cache of directories that we have seen.
 
3553
 
 
3554
        while search_specific_files:
 
3555
            # TODO: the pending list should be lexically sorted?  the
 
3556
            # interface doesn't require it.
 
3557
            current_root = search_specific_files.pop()
 
3558
            current_root_unicode = current_root.decode('utf8')
 
3559
            searched_specific_files.add(current_root)
 
3560
            # process the entries for this containing directory: the rest will be
 
3561
            # found by their parents recursively.
 
3562
            root_entries = self.state._entries_for_path(current_root)
 
3563
            root_abspath = self.tree.abspath(current_root_unicode)
 
3564
            try:
 
3565
                root_stat = os.lstat(root_abspath)
 
3566
            except OSError, e:
 
3567
                if e.errno == errno.ENOENT:
 
3568
                    # the path does not exist: let _process_entry know that.
 
3569
                    root_dir_info = None
 
3570
                else:
 
3571
                    # some other random error: hand it up.
 
3572
                    raise
 
3573
            else:
 
3574
                root_dir_info = ('', current_root,
 
3575
                    osutils.file_kind_from_stat_mode(root_stat.st_mode), root_stat,
 
3576
                    root_abspath)
 
3577
                if root_dir_info[2] == 'directory':
 
3578
                    if self.tree._directory_is_tree_reference(
 
3579
                        current_root.decode('utf8')):
 
3580
                        root_dir_info = root_dir_info[:2] + \
 
3581
                            ('tree-reference',) + root_dir_info[3:]
 
3582
 
 
3583
            if not root_entries and not root_dir_info:
 
3584
                # this specified path is not present at all, skip it.
 
3585
                continue
 
3586
            path_handled = False
 
3587
            for entry in root_entries:
 
3588
                result, changed = _process_entry(entry, root_dir_info)
 
3589
                if changed is not None:
 
3590
                    path_handled = True
 
3591
                    if changed:
 
3592
                        self._gather_result_for_consistency(result)
 
3593
                    if changed or self.include_unchanged:
 
3594
                        yield result
 
3595
            if self.want_unversioned and not path_handled and root_dir_info:
 
3596
                new_executable = bool(
 
3597
                    stat.S_ISREG(root_dir_info[3].st_mode)
 
3598
                    and stat.S_IEXEC & root_dir_info[3].st_mode)
 
3599
                yield (None,
 
3600
                       (None, current_root_unicode),
 
3601
                       True,
 
3602
                       (False, False),
 
3603
                       (None, None),
 
3604
                       (None, splitpath(current_root_unicode)[-1]),
 
3605
                       (None, root_dir_info[2]),
 
3606
                       (None, new_executable)
 
3607
                      )
 
3608
            initial_key = (current_root, '', '')
 
3609
            block_index, _ = self.state._find_block_index_from_key(initial_key)
 
3610
            if block_index == 0:
 
3611
                # we have processed the total root already, but because the
 
3612
                # initial key matched it we should skip it here.
 
3613
                block_index +=1
 
3614
            if root_dir_info and root_dir_info[2] == 'tree-reference':
 
3615
                current_dir_info = None
 
3616
            else:
 
3617
                dir_iterator = osutils._walkdirs_utf8(root_abspath, prefix=current_root)
 
3618
                try:
 
3619
                    current_dir_info = dir_iterator.next()
 
3620
                except OSError, e:
 
3621
                    # on win32, python2.4 has e.errno == ERROR_DIRECTORY, but
 
3622
                    # python 2.5 has e.errno == EINVAL,
 
3623
                    #            and e.winerror == ERROR_DIRECTORY
 
3624
                    e_winerror = getattr(e, 'winerror', None)
 
3625
                    win_errors = (ERROR_DIRECTORY, ERROR_PATH_NOT_FOUND)
 
3626
                    # there may be directories in the inventory even though
 
3627
                    # this path is not a file on disk: so mark it as end of
 
3628
                    # iterator
 
3629
                    if e.errno in (errno.ENOENT, errno.ENOTDIR, errno.EINVAL):
 
3630
                        current_dir_info = None
 
3631
                    elif (sys.platform == 'win32'
 
3632
                          and (e.errno in win_errors
 
3633
                               or e_winerror in win_errors)):
 
3634
                        current_dir_info = None
 
3635
                    else:
 
3636
                        raise
 
3637
                else:
 
3638
                    if current_dir_info[0][0] == '':
 
3639
                        # remove .bzr from iteration
 
3640
                        bzr_index = bisect.bisect_left(current_dir_info[1], ('.bzr',))
 
3641
                        if current_dir_info[1][bzr_index][0] != '.bzr':
 
3642
                            raise AssertionError()
 
3643
                        del current_dir_info[1][bzr_index]
 
3644
            # walk until both the directory listing and the versioned metadata
 
3645
            # are exhausted.
 
3646
            if (block_index < len(self.state._dirblocks) and
 
3647
                osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
 
3648
                current_block = self.state._dirblocks[block_index]
 
3649
            else:
 
3650
                current_block = None
 
3651
            while (current_dir_info is not None or
 
3652
                   current_block is not None):
 
3653
                if (current_dir_info and current_block
 
3654
                    and current_dir_info[0][0] != current_block[0]):
 
3655
                    if _cmp_by_dirs(current_dir_info[0][0], current_block[0]) < 0:
 
3656
                        # filesystem data refers to paths not covered by the dirblock.
 
3657
                        # this has two possibilities:
 
3658
                        # A) it is versioned but empty, so there is no block for it
 
3659
                        # B) it is not versioned.
 
3660
 
 
3661
                        # if (A) then we need to recurse into it to check for
 
3662
                        # new unknown files or directories.
 
3663
                        # if (B) then we should ignore it, because we don't
 
3664
                        # recurse into unknown directories.
 
3665
                        path_index = 0
 
3666
                        while path_index < len(current_dir_info[1]):
 
3667
                                current_path_info = current_dir_info[1][path_index]
 
3668
                                if self.want_unversioned:
 
3669
                                    if current_path_info[2] == 'directory':
 
3670
                                        if self.tree._directory_is_tree_reference(
 
3671
                                            current_path_info[0].decode('utf8')):
 
3672
                                            current_path_info = current_path_info[:2] + \
 
3673
                                                ('tree-reference',) + current_path_info[3:]
 
3674
                                    new_executable = bool(
 
3675
                                        stat.S_ISREG(current_path_info[3].st_mode)
 
3676
                                        and stat.S_IEXEC & current_path_info[3].st_mode)
 
3677
                                    yield (None,
 
3678
                                        (None, utf8_decode(current_path_info[0])[0]),
 
3679
                                        True,
 
3680
                                        (False, False),
 
3681
                                        (None, None),
 
3682
                                        (None, utf8_decode(current_path_info[1])[0]),
 
3683
                                        (None, current_path_info[2]),
 
3684
                                        (None, new_executable))
 
3685
                                # dont descend into this unversioned path if it is
 
3686
                                # a dir
 
3687
                                if current_path_info[2] in ('directory',
 
3688
                                                            'tree-reference'):
 
3689
                                    del current_dir_info[1][path_index]
 
3690
                                    path_index -= 1
 
3691
                                path_index += 1
 
3692
 
 
3693
                        # This dir info has been handled, go to the next
 
3694
                        try:
 
3695
                            current_dir_info = dir_iterator.next()
 
3696
                        except StopIteration:
 
3697
                            current_dir_info = None
 
3698
                    else:
 
3699
                        # We have a dirblock entry for this location, but there
 
3700
                        # is no filesystem path for this. This is most likely
 
3701
                        # because a directory was removed from the disk.
 
3702
                        # We don't have to report the missing directory,
 
3703
                        # because that should have already been handled, but we
 
3704
                        # need to handle all of the files that are contained
 
3705
                        # within.
 
3706
                        for current_entry in current_block[1]:
 
3707
                            # entry referring to file not present on disk.
 
3708
                            # advance the entry only, after processing.
 
3709
                            result, changed = _process_entry(current_entry, None)
 
3710
                            if changed is not None:
 
3711
                                if changed:
 
3712
                                    self._gather_result_for_consistency(result)
 
3713
                                if changed or self.include_unchanged:
 
3714
                                    yield result
 
3715
                        block_index +=1
 
3716
                        if (block_index < len(self.state._dirblocks) and
 
3717
                            osutils.is_inside(current_root,
 
3718
                                              self.state._dirblocks[block_index][0])):
 
3719
                            current_block = self.state._dirblocks[block_index]
 
3720
                        else:
 
3721
                            current_block = None
 
3722
                    continue
 
3723
                entry_index = 0
 
3724
                if current_block and entry_index < len(current_block[1]):
 
3725
                    current_entry = current_block[1][entry_index]
 
3726
                else:
 
3727
                    current_entry = None
 
3728
                advance_entry = True
 
3729
                path_index = 0
 
3730
                if current_dir_info and path_index < len(current_dir_info[1]):
 
3731
                    current_path_info = current_dir_info[1][path_index]
 
3732
                    if current_path_info[2] == 'directory':
 
3733
                        if self.tree._directory_is_tree_reference(
 
3734
                            current_path_info[0].decode('utf8')):
 
3735
                            current_path_info = current_path_info[:2] + \
 
3736
                                ('tree-reference',) + current_path_info[3:]
 
3737
                else:
 
3738
                    current_path_info = None
 
3739
                advance_path = True
 
3740
                path_handled = False
 
3741
                while (current_entry is not None or
 
3742
                    current_path_info is not None):
 
3743
                    if current_entry is None:
 
3744
                        # the check for path_handled when the path is advanced
 
3745
                        # will yield this path if needed.
 
3746
                        pass
 
3747
                    elif current_path_info is None:
 
3748
                        # no path is fine: the per entry code will handle it.
 
3749
                        result, changed = _process_entry(current_entry, current_path_info)
 
3750
                        if changed is not None:
 
3751
                            if changed:
 
3752
                                self._gather_result_for_consistency(result)
 
3753
                            if changed or self.include_unchanged:
 
3754
                                yield result
 
3755
                    elif (current_entry[0][1] != current_path_info[1]
 
3756
                          or current_entry[1][self.target_index][0] in 'ar'):
 
3757
                        # The current path on disk doesn't match the dirblock
 
3758
                        # record. Either the dirblock is marked as absent, or
 
3759
                        # the file on disk is not present at all in the
 
3760
                        # dirblock. Either way, report about the dirblock
 
3761
                        # entry, and let other code handle the filesystem one.
 
3762
 
 
3763
                        # Compare the basename for these files to determine
 
3764
                        # which comes first
 
3765
                        if current_path_info[1] < current_entry[0][1]:
 
3766
                            # extra file on disk: pass for now, but only
 
3767
                            # increment the path, not the entry
 
3768
                            advance_entry = False
 
3769
                        else:
 
3770
                            # entry referring to file not present on disk.
 
3771
                            # advance the entry only, after processing.
 
3772
                            result, changed = _process_entry(current_entry, None)
 
3773
                            if changed is not None:
 
3774
                                if changed:
 
3775
                                    self._gather_result_for_consistency(result)
 
3776
                                if changed or self.include_unchanged:
 
3777
                                    yield result
 
3778
                            advance_path = False
 
3779
                    else:
 
3780
                        result, changed = _process_entry(current_entry, current_path_info)
 
3781
                        if changed is not None:
 
3782
                            path_handled = True
 
3783
                            if changed:
 
3784
                                self._gather_result_for_consistency(result)
 
3785
                            if changed or self.include_unchanged:
 
3786
                                yield result
 
3787
                    if advance_entry and current_entry is not None:
 
3788
                        entry_index += 1
 
3789
                        if entry_index < len(current_block[1]):
 
3790
                            current_entry = current_block[1][entry_index]
 
3791
                        else:
 
3792
                            current_entry = None
 
3793
                    else:
 
3794
                        advance_entry = True # reset the advance flaga
 
3795
                    if advance_path and current_path_info is not None:
 
3796
                        if not path_handled:
 
3797
                            # unversioned in all regards
 
3798
                            if self.want_unversioned:
 
3799
                                new_executable = bool(
 
3800
                                    stat.S_ISREG(current_path_info[3].st_mode)
 
3801
                                    and stat.S_IEXEC & current_path_info[3].st_mode)
 
3802
                                try:
 
3803
                                    relpath_unicode = utf8_decode(current_path_info[0])[0]
 
3804
                                except UnicodeDecodeError:
 
3805
                                    raise errors.BadFilenameEncoding(
 
3806
                                        current_path_info[0], osutils._fs_enc)
 
3807
                                yield (None,
 
3808
                                    (None, relpath_unicode),
 
3809
                                    True,
 
3810
                                    (False, False),
 
3811
                                    (None, None),
 
3812
                                    (None, utf8_decode(current_path_info[1])[0]),
 
3813
                                    (None, current_path_info[2]),
 
3814
                                    (None, new_executable))
 
3815
                            # dont descend into this unversioned path if it is
 
3816
                            # a dir
 
3817
                            if current_path_info[2] in ('directory'):
 
3818
                                del current_dir_info[1][path_index]
 
3819
                                path_index -= 1
 
3820
                        # dont descend the disk iterator into any tree
 
3821
                        # paths.
 
3822
                        if current_path_info[2] == 'tree-reference':
 
3823
                            del current_dir_info[1][path_index]
 
3824
                            path_index -= 1
 
3825
                        path_index += 1
 
3826
                        if path_index < len(current_dir_info[1]):
 
3827
                            current_path_info = current_dir_info[1][path_index]
 
3828
                            if current_path_info[2] == 'directory':
 
3829
                                if self.tree._directory_is_tree_reference(
 
3830
                                    current_path_info[0].decode('utf8')):
 
3831
                                    current_path_info = current_path_info[:2] + \
 
3832
                                        ('tree-reference',) + current_path_info[3:]
 
3833
                        else:
 
3834
                            current_path_info = None
 
3835
                        path_handled = False
 
3836
                    else:
 
3837
                        advance_path = True # reset the advance flagg.
 
3838
                if current_block is not None:
 
3839
                    block_index += 1
 
3840
                    if (block_index < len(self.state._dirblocks) and
 
3841
                        osutils.is_inside(current_root, self.state._dirblocks[block_index][0])):
 
3842
                        current_block = self.state._dirblocks[block_index]
 
3843
                    else:
 
3844
                        current_block = None
 
3845
                if current_dir_info is not None:
 
3846
                    try:
 
3847
                        current_dir_info = dir_iterator.next()
 
3848
                    except StopIteration:
 
3849
                        current_dir_info = None
 
3850
        for result in self._iter_specific_file_parents():
 
3851
            yield result
 
3852
 
 
3853
    def _iter_specific_file_parents(self):
 
3854
        """Iter over the specific file parents."""
 
3855
        while self.search_specific_file_parents:
 
3856
            # Process the parent directories for the paths we were iterating.
 
3857
            # Even in extremely large trees this should be modest, so currently
 
3858
            # no attempt is made to optimise.
 
3859
            path_utf8 = self.search_specific_file_parents.pop()
 
3860
            if osutils.is_inside_any(self.searched_specific_files, path_utf8):
 
3861
                # We've examined this path.
 
3862
                continue
 
3863
            if path_utf8 in self.searched_exact_paths:
 
3864
                # We've examined this path.
 
3865
                continue
 
3866
            path_entries = self.state._entries_for_path(path_utf8)
 
3867
            # We need either one or two entries. If the path in
 
3868
            # self.target_index has moved (so the entry in source_index is in
 
3869
            # 'ar') then we need to also look for the entry for this path in
 
3870
            # self.source_index, to output the appropriate delete-or-rename.
 
3871
            selected_entries = []
 
3872
            found_item = False
 
3873
            for candidate_entry in path_entries:
 
3874
                # Find entries present in target at this path:
 
3875
                if candidate_entry[1][self.target_index][0] not in 'ar':
 
3876
                    found_item = True
 
3877
                    selected_entries.append(candidate_entry)
 
3878
                # Find entries present in source at this path:
 
3879
                elif (self.source_index is not None and
 
3880
                    candidate_entry[1][self.source_index][0] not in 'ar'):
 
3881
                    found_item = True
 
3882
                    if candidate_entry[1][self.target_index][0] == 'a':
 
3883
                        # Deleted, emit it here.
 
3884
                        selected_entries.append(candidate_entry)
 
3885
                    else:
 
3886
                        # renamed, emit it when we process the directory it
 
3887
                        # ended up at.
 
3888
                        self.search_specific_file_parents.add(
 
3889
                            candidate_entry[1][self.target_index][1])
 
3890
            if not found_item:
 
3891
                raise AssertionError(
 
3892
                    "Missing entry for specific path parent %r, %r" % (
 
3893
                    path_utf8, path_entries))
 
3894
            path_info = self._path_info(path_utf8, path_utf8.decode('utf8'))
 
3895
            for entry in selected_entries:
 
3896
                if entry[0][2] in self.seen_ids:
 
3897
                    continue
 
3898
                result, changed = self._process_entry(entry, path_info)
 
3899
                if changed is None:
 
3900
                    raise AssertionError(
 
3901
                        "Got entry<->path mismatch for specific path "
 
3902
                        "%r entry %r path_info %r " % (
 
3903
                        path_utf8, entry, path_info))
 
3904
                # Only include changes - we're outside the users requested
 
3905
                # expansion.
 
3906
                if changed:
 
3907
                    self._gather_result_for_consistency(result)
 
3908
                    if (result[6][0] == 'directory' and
 
3909
                        result[6][1] != 'directory'):
 
3910
                        # This stopped being a directory, the old children have
 
3911
                        # to be included.
 
3912
                        if entry[1][self.source_index][0] == 'r':
 
3913
                            # renamed, take the source path
 
3914
                            entry_path_utf8 = entry[1][self.source_index][1]
 
3915
                        else:
 
3916
                            entry_path_utf8 = path_utf8
 
3917
                        initial_key = (entry_path_utf8, '', '')
 
3918
                        block_index, _ = self.state._find_block_index_from_key(
 
3919
                            initial_key)
 
3920
                        if block_index == 0:
 
3921
                            # The children of the root are in block index 1.
 
3922
                            block_index +=1
 
3923
                        current_block = None
 
3924
                        if block_index < len(self.state._dirblocks):
 
3925
                            current_block = self.state._dirblocks[block_index]
 
3926
                            if not osutils.is_inside(
 
3927
                                entry_path_utf8, current_block[0]):
 
3928
                                # No entries for this directory at all.
 
3929
                                current_block = None
 
3930
                        if current_block is not None:
 
3931
                            for entry in current_block[1]:
 
3932
                                if entry[1][self.source_index][0] in 'ar':
 
3933
                                    # Not in the source tree, so doesn't have to be
 
3934
                                    # included.
 
3935
                                    continue
 
3936
                                # Path of the entry itself.
 
3937
 
 
3938
                                self.search_specific_file_parents.add(
 
3939
                                    osutils.pathjoin(*entry[0][:2]))
 
3940
                if changed or self.include_unchanged:
 
3941
                    yield result
 
3942
            self.searched_exact_paths.add(path_utf8)
 
3943
 
 
3944
    def _path_info(self, utf8_path, unicode_path):
 
3945
        """Generate path_info for unicode_path.
 
3946
 
 
3947
        :return: None if unicode_path does not exist, or a path_info tuple.
 
3948
        """
 
3949
        abspath = self.tree.abspath(unicode_path)
 
3950
        try:
 
3951
            stat = os.lstat(abspath)
 
3952
        except OSError, e:
 
3953
            if e.errno == errno.ENOENT:
 
3954
                # the path does not exist.
 
3955
                return None
 
3956
            else:
 
3957
                raise
 
3958
        utf8_basename = utf8_path.rsplit('/', 1)[-1]
 
3959
        dir_info = (utf8_path, utf8_basename,
 
3960
            osutils.file_kind_from_stat_mode(stat.st_mode), stat,
 
3961
            abspath)
 
3962
        if dir_info[2] == 'directory':
 
3963
            if self.tree._directory_is_tree_reference(
 
3964
                unicode_path):
 
3965
                self.root_dir_info = self.root_dir_info[:2] + \
 
3966
                    ('tree-reference',) + self.root_dir_info[3:]
 
3967
        return dir_info
 
3968
 
 
3969
 
2286
3970
# Try to load the compiled form if possible
2287
3971
try:
2288
 
    from bzrlib._dirstate_helpers_c import (
2289
 
        _read_dirblocks_c as _read_dirblocks,
2290
 
        bisect_dirblock_c as bisect_dirblock,
2291
 
        _bisect_path_left_c as _bisect_path_left,
2292
 
        _bisect_path_right_c as _bisect_path_right,
2293
 
        cmp_by_dirs_c as cmp_by_dirs,
 
3972
    from bzrlib._dirstate_helpers_pyx import (
 
3973
        _read_dirblocks,
 
3974
        bisect_dirblock,
 
3975
        _bisect_path_left,
 
3976
        _bisect_path_right,
 
3977
        cmp_by_dirs,
 
3978
        ProcessEntryC as _process_entry,
 
3979
        update_entry as update_entry,
2294
3980
        )
2295
 
except ImportError:
 
3981
except ImportError, e:
 
3982
    osutils.failed_to_load_extension(e)
2296
3983
    from bzrlib._dirstate_helpers_py import (
2297
 
        _read_dirblocks_py as _read_dirblocks,
2298
 
        bisect_dirblock_py as bisect_dirblock,
2299
 
        _bisect_path_left_py as _bisect_path_left,
2300
 
        _bisect_path_right_py as _bisect_path_right,
2301
 
        cmp_by_dirs_py as cmp_by_dirs,
 
3984
        _read_dirblocks,
 
3985
        bisect_dirblock,
 
3986
        _bisect_path_left,
 
3987
        _bisect_path_right,
 
3988
        cmp_by_dirs,
2302
3989
        )
 
3990
    # FIXME: It would be nice to be able to track moved lines so that the
 
3991
    # corresponding python code can be moved to the _dirstate_helpers_py
 
3992
    # module. I don't want to break the history for this important piece of
 
3993
    # code so I left the code here -- vila 20090622
 
3994
    update_entry = py_update_entry
 
3995
    _process_entry = ProcessEntryPython