~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/dirstate.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-10-24 06:48:13 UTC
  • mfrom: (2592.3.241 mbp-packrepo-as-knits)
  • Revision ID: pqm@pqm.ubuntu.com-20071024064813-wjcmv8ofabf6kdrb
Pack repositories!

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2006-2010 Canonical Ltd
 
1
# Copyright (C) 2006, 2007 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
"""DirState objects record the state of a directory and its bzr metadata.
18
18
 
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 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.
 
85
'f' is a file entry: As for directory, but its a file. The fingerprint is a
 
86
    sha1 value.
88
87
'l' is a symlink entry: As for directory, but a symlink. The fingerprint is the
89
88
    link target.
90
89
't' is a reference to a nested subtree; the fingerprint is the referenced
100
99
 
101
100
--- Format 1 had the following different definition: ---
102
101
rows = dirname, NULL, basename, NULL, MINIKIND, NULL, fileid_utf8, NULL,
103
 
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target,
 
102
    WHOLE NUMBER (* size *), NULL, packed stat, NULL, sha1|symlink target, 
104
103
    {PARENT ROW}
105
104
PARENT ROW = NULL, revision_utf8, NULL, MINIKIND, NULL, dirname, NULL,
106
105
    basename, NULL, WHOLE NUMBER (* size *), NULL, "y" | "n", NULL,
131
130
operations for the less common but still occurs a lot status/diff/commit
132
131
on specific files). Operations on specific files involve a scan for all
133
132
the children of a path, *in every involved tree*, which the current
134
 
format did not accommodate.
 
133
format did not accommodate. 
135
134
----
136
135
 
137
136
Design priorities:
149
148
 
150
149
Memory representation:
151
150
 vector of all directories, and vector of the childen ?
152
 
   i.e.
153
 
     root_entrie = (direntry for root, [parent_direntries_for_root]),
 
151
   i.e. 
 
152
     root_entrie = (direntry for root, [parent_direntries_for_root]), 
154
153
     dirblocks = [
155
154
     ('', ['data for achild', 'data for bchild', 'data for cchild'])
156
155
     ('dir', ['achild', 'cchild', 'echild'])
159
158
    - in-order for serialisation - this is 'dirblock' grouping.
160
159
    - insertion of a file '/a' affects only the '/' child-vector, that is, to
161
160
      insert 10K elements from scratch does not generates O(N^2) memoves of 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
 
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 
164
163
      single directory. compare with Inventory.InventoryDirectory which has
165
164
      a dictionary for the children. No bisect capability, can only probe for
166
165
      exact matches, or grab all elements and sort.
167
166
    - 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
 
167
      we should have a net win regardless of optimality. So we are going to 
169
168
      go with what seems reasonable.
170
169
open questions:
171
170
 
187
186
the file on disk, and then immediately discard, the overhead of object creation
188
187
becomes a significant cost.
189
188
 
190
 
Figures: Creating a tuple from 3 elements was profiled at 0.0625
 
189
Figures: Creating a tuple from from 3 elements was profiled at 0.0625
191
190
microseconds, whereas creating a object which is subclassed from tuple was
192
191
0.500 microseconds, and creating an object with 3 elements and slots was 3
193
192
microseconds long. 0.1 milliseconds is 100 microseconds, and ideally we'll get
204
203
import bisect
205
204
import binascii
206
205
import errno
207
 
import operator
208
206
import os
209
207
from stat import S_IEXEC
210
208
import stat
214
212
import zlib
215
213
 
216
214
from bzrlib import (
217
 
    cache_utf8,
218
215
    debug,
219
216
    errors,
220
217
    inventory,
224
221
    )
225
222
 
226
223
 
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
 
224
def pack_stat(st, _encode=binascii.b2a_base64, _pack=struct.pack):
 
225
    """Convert stat values into a packed representation."""
 
226
    # jam 20060614 it isn't really worth removing more entries if we
 
227
    # are going to leave it in packed form.
 
228
    # With only st_mtime and st_mode filesize is 5.5M and read time is 275ms
 
229
    # With all entries, filesize is 5.9M and read time is maybe 280ms
 
230
    # well within the noise margin
 
231
 
 
232
    # base64 encoding always adds a final newline, so strip it off
 
233
    # The current version
 
234
    return _encode(_pack('>LLLLLL'
 
235
        , st.st_size, int(st.st_mtime), int(st.st_ctime)
 
236
        , st.st_dev, st.st_ino & 0xFFFFFFFF, st.st_mode))[:-1]
 
237
    # This is 0.060s / 1.520s faster by not encoding as much information
 
238
    # return _encode(_pack('>LL', int(st.st_mtime), st.st_mode))[:-1]
 
239
    # This is not strictly faster than _encode(_pack())[:-1]
 
240
    # return '%X.%X.%X.%X.%X.%X' % (
 
241
    #      st.st_size, int(st.st_mtime), int(st.st_ctime),
 
242
    #      st.st_dev, st.st_ino, st.st_mode)
 
243
    # Similar to the _encode(_pack('>LL'))
 
244
    # return '%X.%X' % (int(st.st_mtime), st.st_mode)
306
245
 
307
246
 
308
247
class DirState(object):
310
249
 
311
250
    A dirstate is a specialised data structure for managing local working
312
251
    tree state information. Its not yet well defined whether it is platform
313
 
    specific, and if it is how we detect/parameterize that.
 
252
    specific, and if it is how we detect/parameterise that.
314
253
 
315
254
    Dirstates use the usual lock_write, lock_read and unlock mechanisms.
316
255
    Unlike most bzr disk formats, DirStates must be locked for reading, using
363
302
    HEADER_FORMAT_2 = '#bazaar dirstate flat format 2\n'
364
303
    HEADER_FORMAT_3 = '#bazaar dirstate flat format 3\n'
365
304
 
366
 
    def __init__(self, path, sha1_provider):
 
305
    def __init__(self, path):
367
306
        """Create a  DirState object.
368
307
 
 
308
        Attributes of note:
 
309
 
 
310
        :attr _root_entrie: The root row of the directory/file information,
 
311
            - contains the path to / - '', ''
 
312
            - kind of 'directory',
 
313
            - the file id of the root in utf8
 
314
            - size of 0
 
315
            - a packed state
 
316
            - and no sha information.
369
317
        :param path: The path at which the dirstate file on disk should live.
370
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
371
318
        """
372
319
        # _header_state and _dirblock_state represent the current state
373
320
        # of the dirstate metadata and the per-row data respectiely.
375
322
        # IN_MEMORY_UNMODIFIED indicates that what we have in memory
376
323
        #   is the same as is on disk
377
324
        # IN_MEMORY_MODIFIED indicates that we have a modified version
378
 
        #   of what is on disk.
 
325
        #   of what is on disk. 
379
326
        # In future we will add more granularity, for instance _dirblock_state
380
327
        # will probably support partially-in-memory as a separate variable,
381
328
        # allowing for partially-in-memory unmodified and partially-in-memory
382
329
        # modified states.
383
330
        self._header_state = DirState.NOT_IN_MEMORY
384
331
        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
388
332
        self._dirblocks = []
389
333
        self._ghosts = []
390
334
        self._parents = []
393
337
        self._lock_token = None
394
338
        self._lock_state = None
395
339
        self._id_index = None
396
 
        # a map from packed_stat to sha's.
397
 
        self._packed_stat_index = None
398
340
        self._end_of_header = None
399
341
        self._cutoff_time = None
400
342
        self._split_path_cache = {}
401
343
        self._bisect_page_size = DirState.BISECT_PAGE_SIZE
402
 
        self._sha1_provider = sha1_provider
403
344
        if 'hashcache' in debug.debug_flags:
404
345
            self._sha1_file = self._sha1_file_and_mutter
405
346
        else:
406
 
            self._sha1_file = self._sha1_provider.sha1
 
347
            self._sha1_file = osutils.sha_file_by_name
407
348
        # These two attributes provide a simple cache for lookups into the
408
349
        # dirstate in-memory vectors. By probing respectively for the last
409
350
        # block, and for the next entry, we save nearly 2 bisections per path
419
360
        """Add a path to be tracked.
420
361
 
421
362
        :param path: The path within the dirstate - '' is the root, 'foo' is the
422
 
            path foo within the root, 'foo/bar' is the path bar within foo
 
363
            path foo within the root, 'foo/bar' is the path bar within foo 
423
364
            within the root.
424
365
        :param file_id: The file id of the path being added.
425
 
        :param kind: The kind of the path, as a string like 'file',
 
366
        :param kind: The kind of the path, as a string like 'file', 
426
367
            'directory', etc.
427
368
        :param stat: The output of os.lstat for the path.
428
 
        :param fingerprint: The sha value of the file's canonical form (i.e.
429
 
            after any read filters have been applied),
 
369
        :param fingerprint: The sha value of the file,
430
370
            or the target of a symlink,
431
371
            or the referenced revision id for tree-references,
432
372
            or '' for directories.
433
373
        """
434
374
        # adding a file:
435
 
        # find the block its in.
 
375
        # find the block its in. 
436
376
        # find the location in the block.
437
377
        # check its not there
438
378
        # add it.
451
391
        # in the parent, or according to the special treatment for the root
452
392
        if basename == '.' or basename == '..':
453
393
            raise errors.InvalidEntryName(path)
454
 
        # now that we've normalised, we need the correct utf8 path and
 
394
        # now that we've normalised, we need the correct utf8 path and 
455
395
        # dirname and basename elements. This single encode and split should be
456
396
        # faster than three separate encodes.
457
397
        utf8path = (dirname + '/' + basename).strip('/').encode('utf8')
458
398
        dirname, basename = osutils.split(utf8path)
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), ))
 
399
        assert file_id.__class__ == str, \
 
400
            "must be a utf8 file_id not %s" % (type(file_id))
463
401
        # Make sure the file_id does not exist in this tree
464
 
        rename_from = None
465
 
        file_id_entry = self._get_entry(0, fileid_utf8=file_id, include_deleted=True)
 
402
        file_id_entry = self._get_entry(0, fileid_utf8=file_id)
466
403
        if file_id_entry != (None, None):
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)
 
404
            path = osutils.pathjoin(file_id_entry[0][0], file_id_entry[0][1])
 
405
            kind = DirState._minikind_to_kind[file_id_entry[1][0][0]]
 
406
            info = '%s:%s' % (kind, path)
 
407
            raise errors.DuplicateFileId(file_id, info)
482
408
        first_key = (dirname, basename, '')
483
409
        block_index, present = self._find_block_index_from_key(first_key)
484
410
        if present:
485
411
            # check the path is not in the tree
486
412
            block = self._dirblocks[block_index][1]
487
413
            entry_index, _ = self._find_entry_index(first_key, block)
488
 
            while (entry_index < len(block) and
 
414
            while (entry_index < len(block) and 
489
415
                block[entry_index][0][0:2] == first_key[0:2]):
490
416
                if block[entry_index][1][0][0] not in 'ar':
491
417
                    # this path is in the dirstate in the current tree.
511
437
            packed_stat = pack_stat(stat)
512
438
        parent_info = self._empty_parent_info()
513
439
        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, '')
520
440
        if kind == 'file':
521
441
            entry_data = entry_key, [
522
442
                (minikind, fingerprint, size, False, packed_stat),
539
459
        if not present:
540
460
            block.insert(entry_index, entry_data)
541
461
        else:
542
 
            if block[entry_index][1][0][0] != 'a':
543
 
                raise AssertionError(" %r(%r) already added" % (basename, file_id))
 
462
            assert block[entry_index][1][0][0] == 'a', " %r(%r) already added" % (basename, file_id)
544
463
            block[entry_index][1][0] = entry_data[1][0]
545
464
 
546
465
        if kind == 'directory':
565
484
        # If _dirblock_state was in memory, we should just return info from
566
485
        # there, this function is only meant to handle when we want to read
567
486
        # part of the disk.
568
 
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
569
 
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
 
487
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
570
488
 
571
489
        # The disk representation is generally info + '\0\n\0' at the end. But
572
490
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
758
676
        # If _dirblock_state was in memory, we should just return info from
759
677
        # there, this function is only meant to handle when we want to read
760
678
        # part of the disk.
761
 
        if self._dirblock_state != DirState.NOT_IN_MEMORY:
762
 
            raise AssertionError("bad dirblock state %r" % self._dirblock_state)
 
679
        assert self._dirblock_state == DirState.NOT_IN_MEMORY
 
680
 
763
681
        # The disk representation is generally info + '\0\n\0' at the end. But
764
682
        # for bisecting, it is easier to treat this as '\0' + info + '\0\n'
765
683
        # Because it means we can sync on the '\n'
979
897
            processed_dirs.update(pending_dirs)
980
898
        return found
981
899
 
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
 
 
1024
900
    def _empty_parent_info(self):
1025
901
        return [DirState.NULL_PARENT_DETAILS] * (len(self._parents) -
1026
902
                                                    len(self._ghosts))
1052
928
        # the basename of the directory must be the end of its full name.
1053
929
        if not (parent_block_index == -1 and
1054
930
            parent_block_index == -1 and dirname == ''):
1055
 
            if not dirname.endswith(
1056
 
                    self._dirblocks[parent_block_index][1][parent_row_index][0][1]):
1057
 
                raise AssertionError("bad dirname %r" % dirname)
 
931
            assert dirname.endswith(
 
932
                self._dirblocks[parent_block_index][1][parent_row_index][0][1])
1058
933
        block_index, present = self._find_block_index_from_key((dirname, '', ''))
1059
934
        if not present:
1060
 
            ## In future, when doing partial parsing, this should load and
 
935
            ## In future, when doing partial parsing, this should load and 
1061
936
            # populate the entire block.
1062
937
            self._dirblocks.insert(block_index, (dirname, []))
1063
938
        return block_index
1072
947
            to prevent unneeded overhead when callers have a sorted list already.
1073
948
        :return: Nothing.
1074
949
        """
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
 
950
        assert new_entries[0][0][0:2] == ('', ''), \
 
951
            "Missing root row %r" % (new_entries[0][0],)
 
952
        # The two blocks here are deliberate: the root block and the 
1079
953
        # contents-of-root block.
1080
954
        self._dirblocks = [('', []), ('', [])]
1081
955
        current_block = self._dirblocks[0][1]
1102
976
        # The above loop leaves the "root block" entries mixed with the
1103
977
        # "contents-of-root block". But we don't want an if check on
1104
978
        # all entries, so instead we just fix it up here.
1105
 
        if self._dirblocks[1] != ('', []):
1106
 
            raise ValueError("bad dirblock start %r" % (self._dirblocks[1],))
 
979
        assert self._dirblocks[1] == ('', [])
1107
980
        root_block = []
1108
981
        contents_of_root_block = []
1109
982
        for entry in self._dirblocks[0][1]:
1114
987
        self._dirblocks[0] = ('', root_block)
1115
988
        self._dirblocks[1] = ('', contents_of_root_block)
1116
989
 
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
 
 
1135
990
    def _entry_to_line(self, entry):
1136
991
        """Serialize entry to a NULL delimited line ready for _get_output_lines.
1137
992
 
1205
1060
        # one to use it. we use _right here because there are two
1206
1061
        # '' blocks - the root, and the contents of root
1207
1062
        # we always have a minimum of 2 in self._dirblocks: root and
1208
 
        # root-contents, and for '', we get 2 back, so this is
 
1063
        # root-contents, and for '', we get 2 back, so this is 
1209
1064
        # simple and correct:
1210
1065
        present = (block_index < len(self._dirblocks) and
1211
1066
            self._dirblocks[block_index][0] == key[0])
1240
1095
        return entry_index, present
1241
1096
 
1242
1097
    @staticmethod
1243
 
    def from_tree(tree, dir_state_filename, sha1_provider=None):
 
1098
    def from_tree(tree, dir_state_filename):
1244
1099
        """Create a dirstate from a bzr Tree.
1245
1100
 
1246
1101
        :param tree: The tree which should provide parent information and
1247
1102
            inventory ids.
1248
 
        :param sha1_provider: an object meeting the SHA1Provider interface.
1249
 
            If None, a DefaultSHA1Provider is used.
1250
1103
        :return: a DirState object which is currently locked for writing.
1251
1104
            (it was locked by DirState.initialize)
1252
1105
        """
1253
 
        result = DirState.initialize(dir_state_filename,
1254
 
            sha1_provider=sha1_provider)
 
1106
        result = DirState.initialize(dir_state_filename)
1255
1107
        try:
1256
1108
            tree.lock_read()
1257
1109
            try:
1275
1127
            raise
1276
1128
        return result
1277
1129
 
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.
 
1130
    def update_entry(self, entry, abspath, stat_value,
 
1131
                     _stat_to_minikind=_stat_to_minikind,
 
1132
                     _pack_stat=pack_stat):
 
1133
        """Update the entry based on what is actually on disk.
 
1134
 
 
1135
        :param entry: This is the dirblock entry for the file in question.
 
1136
        :param abspath: The path on disk for this file.
 
1137
        :param stat_value: (optional) if we already have done a stat on the
 
1138
            file, re-use it.
 
1139
        :return: The sha1 hexdigest of the file (40 bytes) or link target of a
 
1140
                symlink.
1724
1141
        """
1725
1142
        try:
1726
1143
            minikind = _stat_to_minikind[stat_value.st_mode & 0170000]
1728
1145
            # Unhandled kind
1729
1146
            return None
1730
1147
        packed_stat = _pack_stat(stat_value)
 
1148
        (saved_minikind, saved_link_or_sha1, saved_file_size,
 
1149
         saved_executable, saved_packed_stat) = entry[1][0]
 
1150
 
 
1151
        if (minikind == saved_minikind
 
1152
            and packed_stat == saved_packed_stat):
 
1153
            # The stat hasn't changed since we saved, so we can re-use the
 
1154
            # saved sha hash.
 
1155
            if minikind == 'd':
 
1156
                return None
 
1157
 
 
1158
            # size should also be in packed_stat
 
1159
            if saved_file_size == stat_value.st_size:
 
1160
                return saved_link_or_sha1
 
1161
 
 
1162
        # If we have gotten this far, that means that we need to actually
 
1163
        # process this entry.
 
1164
        link_or_sha1 = None
1731
1165
        if minikind == 'f':
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
            link_or_sha1 = self._sha1_file(abspath)
 
1167
            executable = self._is_executable(stat_value.st_mode,
 
1168
                                             saved_executable)
 
1169
            if self._cutoff_time is None:
 
1170
                self._sha_cutoff_time()
 
1171
            if (stat_value.st_mtime < self._cutoff_time
 
1172
                and stat_value.st_ctime < self._cutoff_time):
 
1173
                entry[1][0] = ('f', link_or_sha1, stat_value.st_size,
 
1174
                               executable, packed_stat)
 
1175
            else:
 
1176
                entry[1][0] = ('f', '', stat_value.st_size,
 
1177
                               executable, DirState.NULLSTAT)
 
1178
        elif minikind == 'd':
 
1179
            link_or_sha1 = None
 
1180
            entry[1][0] = ('d', '', 0, False, packed_stat)
 
1181
            if saved_minikind != 'd':
 
1182
                # This changed from something into a directory. Make sure we
 
1183
                # have a directory block for it. This doesn't happen very
 
1184
                # often, so this doesn't have to be super fast.
 
1185
                block_index, entry_index, dir_present, file_present = \
 
1186
                    self._get_block_entry_index(entry[0][0], entry[0][1], 0)
 
1187
                self._ensure_block(block_index, entry_index,
 
1188
                                   osutils.pathjoin(entry[0][0], entry[0][1]))
 
1189
        elif minikind == 'l':
 
1190
            link_or_sha1 = self._read_link(abspath, saved_link_or_sha1)
 
1191
            if self._cutoff_time is None:
 
1192
                self._sha_cutoff_time()
 
1193
            if (stat_value.st_mtime < self._cutoff_time
 
1194
                and stat_value.st_ctime < self._cutoff_time):
 
1195
                entry[1][0] = ('l', link_or_sha1, stat_value.st_size,
 
1196
                               False, packed_stat)
 
1197
            else:
 
1198
                entry[1][0] = ('l', '', stat_value.st_size,
 
1199
                               False, DirState.NULLSTAT)
 
1200
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1201
        return link_or_sha1
1739
1202
 
1740
1203
    def _sha_cutoff_time(self):
1741
1204
        """Return cutoff time.
1758
1221
        # when -Dhashcache is turned on, this is monkey-patched in to log
1759
1222
        # file reads
1760
1223
        trace.mutter("dirstate sha1 " + abspath)
1761
 
        return self._sha1_provider.sha1(abspath)
 
1224
        return osutils.sha_file_by_name(abspath)
1762
1225
 
1763
1226
    def _is_executable(self, mode, old_executable):
1764
1227
        """Is this file executable?"""
1777
1240
        #       already in memory. However, this really needs to be done at a
1778
1241
        #       higher level, because there either won't be anything on disk,
1779
1242
        #       or the thing on disk will be a file.
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
 
1243
        return os.readlink(abspath)
1792
1244
 
1793
1245
    def get_ghosts(self):
1794
1246
        """Return a list of the parent tree revision ids that are ghosts."""
1934
1386
        # linear search through entries at this path to find the one
1935
1387
        # requested.
1936
1388
        while entry_index < len(block) and block[entry_index][0][1] == basename:
1937
 
            if block[entry_index][1][tree_index][0] not in 'ar':
1938
 
                # neither absent or relocated
 
1389
            if block[entry_index][1][tree_index][0] not in \
 
1390
                       ('a', 'r'): # absent, relocated
1939
1391
                return block_index, entry_index, True, True
1940
1392
            entry_index += 1
1941
1393
        return block_index, entry_index, True, False
1942
1394
 
1943
 
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None, include_deleted=False):
 
1395
    def _get_entry(self, tree_index, fileid_utf8=None, path_utf8=None):
1944
1396
        """Get the dirstate entry for path in tree tree_index.
1945
1397
 
1946
1398
        If either file_id or path is supplied, it is used as the key to lookup.
1954
1406
            trees.
1955
1407
        :param fileid_utf8: A utf8 file_id to look up.
1956
1408
        :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.
1960
1409
        :return: The dirstate entry tuple for path, or (None, None)
1961
1410
        """
1962
1411
        self._read_dirblocks_if_needed()
1963
1412
        if path_utf8 is not None:
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))
 
1413
            assert path_utf8.__class__ == str, ('path_utf8 is not a str: %s %s'
 
1414
                % (type(path_utf8), path_utf8))
1967
1415
            # path lookups are faster
1968
1416
            dirname, basename = osutils.split(path_utf8)
1969
1417
            block_index, entry_index, dir_present, file_present = \
1971
1419
            if not file_present:
1972
1420
                return None, None
1973
1421
            entry = self._dirblocks[block_index][1][entry_index]
1974
 
            if not (entry[0][2] and entry[1][tree_index][0] not in ('a', 'r')):
1975
 
                raise AssertionError('unversioned entry?')
 
1422
            assert entry[0][2] and entry[1][tree_index][0] not in ('a', 'r'), 'unversioned entry?!?!'
1976
1423
            if fileid_utf8:
1977
1424
                if entry[0][2] != fileid_utf8:
1978
 
                    self._changes_aborted = True
1979
1425
                    raise errors.BzrError('integrity error ? : mismatching'
1980
1426
                                          ' tree_index, file_id and path')
1981
1427
            return entry
1982
1428
        else:
 
1429
            assert fileid_utf8 is not None
1983
1430
            possible_keys = self._get_id_index().get(fileid_utf8, None)
1984
1431
            if not possible_keys:
1985
1432
                return None, None
1997
1444
                entry_index, present = self._find_entry_index(key, block)
1998
1445
                if present:
1999
1446
                    entry = self._dirblocks[block_index][1][entry_index]
2000
 
                    # TODO: We might want to assert that entry[0][2] ==
2001
 
                    #       fileid_utf8.
2002
1447
                    if entry[1][tree_index][0] in 'fdlt':
2003
 
                        # this is the result we are looking for: the
 
1448
                        # this is the result we are looking for: the  
2004
1449
                        # real home of this file_id in this tree.
2005
1450
                        return entry
2006
1451
                    if entry[1][tree_index][0] == 'a':
2007
1452
                        # there is no home for this entry in this tree
2008
 
                        if include_deleted:
2009
 
                            return entry
2010
1453
                        return None, None
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))
 
1454
                    assert entry[1][tree_index][0] == 'r', \
 
1455
                        "entry %r has invalid minikind %r for tree %r" \
 
1456
                        % (entry,
 
1457
                           entry[1][tree_index][0],
 
1458
                           tree_index)
2017
1459
                    real_path = entry[1][tree_index][1]
2018
1460
                    return self._get_entry(tree_index, fileid_utf8=fileid_utf8,
2019
1461
                        path_utf8=real_path)
2020
1462
            return None, None
2021
1463
 
2022
1464
    @classmethod
2023
 
    def initialize(cls, path, sha1_provider=None):
 
1465
    def initialize(cls, path):
2024
1466
        """Create a new dirstate on path.
2025
1467
 
2026
1468
        The new dirstate will be an empty tree - that is it has no parents,
2027
1469
        and only a root node - which has id ROOT_ID.
2028
1470
 
2029
1471
        :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.
2032
1472
        :return: A write-locked DirState object.
2033
1473
        """
2034
1474
        # This constructs a new DirState object on a path, sets the _state_file
2036
1476
        # stock empty dirstate information - a root with ROOT_ID, no children,
2037
1477
        # and no parents. Finally it calls save() to ensure that this data will
2038
1478
        # persist.
2039
 
        if sha1_provider is None:
2040
 
            sha1_provider = DefaultSHA1Provider()
2041
 
        result = cls(path, sha1_provider)
 
1479
        result = cls(path)
2042
1480
        # root dir and root dir contents with no children.
2043
1481
        empty_tree_dirblocks = [('', []), ('', [])]
2044
1482
        # a new root directory, with a NULLSTAT.
2055
1493
            raise
2056
1494
        return result
2057
1495
 
2058
 
    @staticmethod
2059
 
    def _inv_entry_to_details(inv_entry):
 
1496
    def _inv_entry_to_details(self, inv_entry):
2060
1497
        """Convert an inventory entry (from a revision tree) to state details.
2061
1498
 
2062
1499
        :param inv_entry: An inventory entry whose sha1 and link targets can be
2067
1504
        kind = inv_entry.kind
2068
1505
        minikind = DirState._kind_to_minikind[kind]
2069
1506
        tree_data = inv_entry.revision
 
1507
        assert tree_data, 'empty revision for the inv_entry %s.' % \
 
1508
            inv_entry.file_id
2070
1509
        if kind == 'directory':
2071
1510
            fingerprint = ''
2072
1511
            size = 0
2073
1512
            executable = False
2074
1513
        elif kind == 'symlink':
2075
 
            if inv_entry.symlink_target is None:
2076
 
                fingerprint = ''
2077
 
            else:
2078
 
                fingerprint = inv_entry.symlink_target.encode('utf8')
 
1514
            fingerprint = inv_entry.symlink_target or ''
2079
1515
            size = 0
2080
1516
            executable = False
2081
1517
        elif kind == 'file':
2090
1526
            raise Exception("can't pack %s" % inv_entry)
2091
1527
        return (minikind, fingerprint, size, executable, tree_data)
2092
1528
 
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
 
 
2134
1529
    def _iter_entries(self):
2135
1530
        """Iterate over all the entries in the dirstate.
2136
1531
 
2177
1572
        return len(self._parents) - len(self._ghosts)
2178
1573
 
2179
1574
    @staticmethod
2180
 
    def on_file(path, sha1_provider=None):
2181
 
        """Construct a DirState on the file at path "path".
 
1575
    def on_file(path):
 
1576
        """Construct a DirState on the file at path path.
2182
1577
 
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.
2186
1578
        :return: An unlocked DirState object, associated with the given path.
2187
1579
        """
2188
 
        if sha1_provider is None:
2189
 
            sha1_provider = DefaultSHA1Provider()
2190
 
        result = DirState(path, sha1_provider)
 
1580
        result = DirState(path)
2191
1581
        return result
2192
1582
 
2193
1583
    def _read_dirblocks_if_needed(self):
2194
1584
        """Read in all the dirblocks from the file if they are not in memory.
2195
 
 
 
1585
        
2196
1586
        This populates self._dirblocks, and sets self._dirblock_state to
2197
1587
        IN_MEMORY_UNMODIFIED. It is not currently ready for incremental block
2198
1588
        loading.
2213
1603
        parent_line = self._state_file.readline()
2214
1604
        info = parent_line.split('\0')
2215
1605
        num_parents = int(info[0])
 
1606
        assert num_parents == len(info)-2, 'incorrect parent info line'
2216
1607
        self._parents = info[1:-1]
 
1608
 
2217
1609
        ghost_line = self._state_file.readline()
2218
1610
        info = ghost_line.split('\0')
2219
1611
        num_ghosts = int(info[1])
 
1612
        assert num_ghosts == len(info)-3, 'incorrect ghost info line'
2220
1613
        self._ghosts = info[2:-1]
2221
1614
        self._header_state = DirState.IN_MEMORY_UNMODIFIED
2222
1615
        self._end_of_header = self._state_file.tell()
2239
1632
        and their ids. Followed by a newline.
2240
1633
        """
2241
1634
        header = self._state_file.readline()
2242
 
        if header != DirState.HEADER_FORMAT_3:
2243
 
            raise errors.BzrError(
2244
 
                'invalid header line: %r' % (header,))
 
1635
        assert header == DirState.HEADER_FORMAT_3, \
 
1636
            'invalid header line: %r' % (header,)
2245
1637
        crc_line = self._state_file.readline()
2246
 
        if not crc_line.startswith('crc32: '):
2247
 
            raise errors.BzrError('missing crc32 checksum: %r' % crc_line)
 
1638
        assert crc_line.startswith('crc32: '), 'missing crc32 checksum'
2248
1639
        self.crc_expected = int(crc_line[len('crc32: '):-1])
2249
1640
        num_entries_line = self._state_file.readline()
2250
 
        if not num_entries_line.startswith('num_entries: '):
2251
 
            raise errors.BzrError('missing num_entries line')
 
1641
        assert num_entries_line.startswith('num_entries: '), 'missing num_entries line'
2252
1642
        self._num_entries = int(num_entries_line[len('num_entries: '):-1])
2253
1643
 
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
 
 
2268
1644
    def save(self):
2269
1645
        """Save any pending changes created during this session.
2270
1646
 
2279
1655
        start over, to allow for fine grained read lock duration, so 'status'
2280
1656
        wont block 'commit' - for example.
2281
1657
        """
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
2288
1658
        if (self._header_state == DirState.IN_MEMORY_MODIFIED or
2289
1659
            self._dirblock_state == DirState.IN_MEMORY_MODIFIED):
2290
1660
 
2323
1693
 
2324
1694
        :param parent_ids: A list of parent tree revision ids.
2325
1695
        :param dirblocks: A list containing one tuple for each directory in the
2326
 
            tree. Each tuple contains the directory path and a list of entries
 
1696
            tree. Each tuple contains the directory path and a list of entries 
2327
1697
            found in that directory.
2328
1698
        """
2329
1699
        # our memory copy is now authoritative.
2332
1702
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2333
1703
        self._parents = list(parent_ids)
2334
1704
        self._id_index = None
2335
 
        self._packed_stat_index = None
2336
1705
 
2337
1706
    def set_path_id(self, path, new_id):
2338
1707
        """Change the id of path to new_id in the current working tree.
2342
1711
        :param new_id: The new id to assign to the path. This must be a utf8
2343
1712
            file id (not unicode, and not None).
2344
1713
        """
 
1714
        assert new_id.__class__ == str, \
 
1715
            "path_id %r is not a plain string" % (new_id,)
2345
1716
        self._read_dirblocks_if_needed()
2346
1717
        if len(path):
2347
1718
            # TODO: logic not written
2356
1727
        self.update_minimal(('', '', new_id), 'd',
2357
1728
            path_utf8='', packed_stat=entry[1][0][4])
2358
1729
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
 
1730
        if self._id_index is not None:
 
1731
            self._id_index.setdefault(new_id, set()).add(entry[0])
2359
1732
 
2360
1733
    def set_parent_trees(self, trees, ghosts):
2361
1734
        """Set the parent trees for the dirstate.
2362
1735
 
2363
1736
        :param trees: A list of revision_id, tree tuples. tree must be provided
2364
 
            even if the revision_id refers to a ghost: supply an empty tree in
 
1737
            even if the revision_id refers to a ghost: supply an empty tree in 
2365
1738
            this case.
2366
1739
        :param ghosts: A list of the revision_ids that are ghosts at the time
2367
1740
            of setting.
2368
 
        """
2369
 
        # TODO: generate a list of parent indexes to preserve to save
 
1741
        """ 
 
1742
        # TODO: generate a list of parent indexes to preserve to save 
2370
1743
        # processing specific parent trees. In the common case one tree will
2371
1744
        # be preserved - the left most parent.
2372
1745
        # TODO: if the parent tree is a dirstate, we might want to walk them
2377
1750
        # map and then walk the new parent trees only, mapping them into the
2378
1751
        # dirstate. Walk the dirstate at the same time to remove unreferenced
2379
1752
        # entries.
2380
 
        # for now:
2381
 
        # sketch: loop over all entries in the dirstate, cherry picking
 
1753
        # for now: 
 
1754
        # sketch: loop over all entries in the dirstate, cherry picking 
2382
1755
        # entries from the parent trees, if they are not ghost trees.
2383
1756
        # after we finish walking the dirstate, all entries not in the dirstate
2384
1757
        # are deletes, so we want to append them to the end as per the design
2389
1762
        #   links. We dont't trivially use the inventory from other trees
2390
1763
        #   because this leads to either double touching, or to accessing
2391
1764
        #   missing keys,
2392
 
        # - find other keys containing a path
2393
 
        # We accumulate each entry via this dictionary, including the root
 
1765
        # - find other keys containing a path 
 
1766
        # We accumulate each entry via this dictionary, including the root 
2394
1767
        by_path = {}
2395
1768
        id_index = {}
2396
1769
        # we could do parallel iterators, but because file id data may be
2400
1773
        # parent, but for now the common cases are adding a new parent (merge),
2401
1774
        # and replacing completely (commit), and commit is more common: so
2402
1775
        # optimise merge later.
2403
 
 
 
1776
        
2404
1777
        # ---- start generation of full tree mapping data
2405
1778
        # what trees should we use?
2406
1779
        parent_trees = [tree for rev_id, tree in trees if rev_id not in ghosts]
2407
 
        # how many trees do we end up with
 
1780
        # how many trees do we end up with 
2408
1781
        parent_count = len(parent_trees)
2409
1782
 
2410
1783
        # one: the current tree
2411
1784
        for entry in self._iter_entries():
2412
1785
            # skip entries not in the current tree
2413
 
            if entry[1][0][0] in 'ar': # absent, relocated
 
1786
            if entry[1][0][0] in ('a', 'r'): # absent, relocated
2414
1787
                continue
2415
1788
            by_path[entry[0]] = [entry[1][0]] + \
2416
1789
                [DirState.NULL_PARENT_DETAILS] * parent_count
2417
1790
            id_index[entry[0][2]] = set([entry[0]])
2418
 
 
 
1791
        
2419
1792
        # now the parent trees:
2420
1793
        for tree_index, tree in enumerate(parent_trees):
2421
1794
            # the index is off by one, adjust it.
2435
1808
                # avoid checking all known paths for the id when generating a
2436
1809
                # new entry at this path: by adding the id->path mapping last,
2437
1810
                # all the mappings are valid and have correct relocation
2438
 
                # records where needed.
 
1811
                # records where needed. 
2439
1812
                file_id = entry.file_id
2440
1813
                path_utf8 = path.encode('utf8')
2441
1814
                dirname, basename = osutils.split(path_utf8)
2452
1825
                        # This is the vertical axis in the matrix, all pointing
2453
1826
                        # to the real path.
2454
1827
                        by_path[entry_key][tree_index] = ('r', path_utf8, 0, False, '')
2455
 
                # by path consistency: Insert into an existing path record (trivial), or
 
1828
                # by path consistency: Insert into an existing path record (trivial), or 
2456
1829
                # add a new one with relocation pointers for the other tree indexes.
2457
1830
                if new_entry_key in id_index[file_id]:
2458
1831
                    # there is already an entry where this data belongs, just insert it.
2471
1844
                            new_details.append(DirState.NULL_PARENT_DETAILS)
2472
1845
                        else:
2473
1846
                            # grab any one entry, use it to find the right path.
2474
 
                            # TODO: optimise this to reduce memory use in highly
 
1847
                            # TODO: optimise this to reduce memory use in highly 
2475
1848
                            # fragmented situations by reusing the relocation
2476
1849
                            # records.
2477
1850
                            a_key = iter(id_index[file_id]).next()
2510
1883
        return sorted(entry_list, key=_key)
2511
1884
 
2512
1885
    def set_state_from_inventory(self, new_inv):
2513
 
        """Set new_inv as the current state.
 
1886
        """Set new_inv as the current state. 
2514
1887
 
2515
1888
        This API is called by tree transform, and will usually occur with
2516
1889
        existing parent trees.
2520
1893
        if 'evil' in debug.debug_flags:
2521
1894
            trace.mutter_callsite(1,
2522
1895
                "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:")
2526
1896
        self._read_dirblocks_if_needed()
2527
1897
        # sketch:
2528
 
        # Two iterators: current data and new data, both in dirblock order.
 
1898
        # Two iterators: current data and new data, both in dirblock order. 
2529
1899
        # We zip them together, which tells about entries that are new in the
2530
1900
        # inventory, or removed in the inventory, or present in both and
2531
 
        # possibly changed.
 
1901
        # possibly changed.  
2532
1902
        #
2533
1903
        # You might think we could just synthesize a new dirstate directly
2534
1904
        # since we're processing it in the right order.  However, we need to
2537
1907
        new_iterator = new_inv.iter_entries_by_dir()
2538
1908
        # we will be modifying the dirstate, so we need a stable iterator. In
2539
1909
        # future we might write one, for now we just clone the state into a
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.
 
1910
        # list - which is a shallow copy.
2543
1911
        old_iterator = iter(list(self._iter_entries()))
2544
1912
        # both must have roots so this is safe:
2545
1913
        current_new = new_iterator.next()
2551
1919
                return None
2552
1920
        while current_new or current_old:
2553
1921
            # skip entries in old that are not really there
2554
 
            if current_old and current_old[1][0][0] in 'ar':
 
1922
            if current_old and current_old[1][0][0] in ('r', 'a'):
2555
1923
                # relocated or absent
2556
1924
                current_old = advance(old_iterator)
2557
1925
                continue
2579
1947
            # we make both end conditions explicit
2580
1948
            if not current_old:
2581
1949
                # 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'))
2585
1950
                self.update_minimal(new_entry_key, current_new_minikind,
2586
1951
                    executable=current_new[1].executable,
2587
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
2588
 
                    fullscan=True)
 
1952
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
2589
1953
                current_new = advance(new_iterator)
2590
1954
            elif not current_new:
2591
1955
                # 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'))
2596
1956
                self._make_absent(current_old)
2597
1957
                current_old = advance(old_iterator)
2598
1958
            elif new_entry_key == current_old[0]:
2605
1965
                # kind has changed.
2606
1966
                if (current_old[1][0][3] != current_new[1].executable or
2607
1967
                    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'))
2611
1968
                    self.update_minimal(current_old[0], current_new_minikind,
2612
1969
                        executable=current_new[1].executable,
2613
 
                        path_utf8=new_path_utf8, fingerprint=fingerprint,
2614
 
                        fullscan=True)
 
1970
                        path_utf8=new_path_utf8, fingerprint=fingerprint)
2615
1971
                # both sides are dealt with, move on
2616
1972
                current_old = advance(old_iterator)
2617
1973
                current_new = advance(new_iterator)
2620
1976
                      and new_entry_key[1:] < current_old[0][1:])):
2621
1977
                # new comes before:
2622
1978
                # add a entry for this and advance new
2623
 
                if tracing:
2624
 
                    trace.mutter("Inserting from new '%s'.",
2625
 
                        new_path_utf8.decode('utf8'))
2626
1979
                self.update_minimal(new_entry_key, current_new_minikind,
2627
1980
                    executable=current_new[1].executable,
2628
 
                    path_utf8=new_path_utf8, fingerprint=fingerprint,
2629
 
                    fullscan=True)
 
1981
                    path_utf8=new_path_utf8, fingerprint=fingerprint)
2630
1982
                current_new = advance(new_iterator)
2631
1983
            else:
2632
1984
                # we've advanced past the place where the old key would be,
2633
1985
                # 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'))
2638
1986
                self._make_absent(current_old)
2639
1987
                current_old = advance(old_iterator)
2640
1988
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2641
1989
        self._id_index = None
2642
 
        self._packed_stat_index = None
2643
 
        if tracing:
2644
 
            trace.mutter("set_state_from_inventory complete.")
2645
1990
 
2646
1991
    def _make_absent(self, current_old):
2647
1992
        """Mark current_old - an entry - as absent for tree 0.
2655
2000
        all_remaining_keys = set()
2656
2001
        # Dont check the working tree, because it's going.
2657
2002
        for details in current_old[1][1:]:
2658
 
            if details[0] not in 'ar': # absent, relocated
 
2003
            if details[0] not in ('a', 'r'): # absent, relocated
2659
2004
                all_remaining_keys.add(current_old[0])
2660
2005
            elif details[0] == 'r': # relocated
2661
2006
                # record the key for the real path.
2668
2013
            # Remove it, its meaningless.
2669
2014
            block = self._find_block(current_old[0])
2670
2015
            entry_index, present = self._find_entry_index(current_old[0], block[1])
2671
 
            if not present:
2672
 
                raise AssertionError('could not find entry for %s' % (current_old,))
 
2016
            assert present, 'could not find entry for %s' % (current_old,)
2673
2017
            block[1].pop(entry_index)
2674
2018
            # if we have an id_index in use, remove this key from it for this id.
2675
2019
            if self._id_index is not None:
2681
2025
        for update_key in all_remaining_keys:
2682
2026
            update_block_index, present = \
2683
2027
                self._find_block_index_from_key(update_key)
2684
 
            if not present:
2685
 
                raise AssertionError('could not find block for %s' % (update_key,))
 
2028
            assert present, 'could not find block for %s' % (update_key,)
2686
2029
            update_entry_index, present = \
2687
2030
                self._find_entry_index(update_key, self._dirblocks[update_block_index][1])
2688
 
            if not present:
2689
 
                raise AssertionError('could not find entry for %s' % (update_key,))
 
2031
            assert present, 'could not find entry for %s' % (update_key,)
2690
2032
            update_tree_details = self._dirblocks[update_block_index][1][update_entry_index][1]
2691
2033
            # it must not be absent at the moment
2692
 
            if update_tree_details[0][0] == 'a': # absent
2693
 
                raise AssertionError('bad row %r' % (update_tree_details,))
 
2034
            assert update_tree_details[0][0] != 'a' # absent
2694
2035
            update_tree_details[0] = DirState.NULL_PARENT_DETAILS
2695
2036
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2696
2037
        return last_reference
2697
2038
 
2698
2039
    def update_minimal(self, key, minikind, executable=False, fingerprint='',
2699
 
        packed_stat=None, size=0, path_utf8=None, fullscan=False):
 
2040
                       packed_stat=None, size=0, path_utf8=None):
2700
2041
        """Update an entry to the state in tree 0.
2701
2042
 
2702
2043
        This will either create a new entry at 'key' or update an existing one.
2707
2048
        :param minikind: The type for the entry ('f' == 'file', 'd' ==
2708
2049
                'directory'), etc.
2709
2050
        :param executable: Should the executable bit be set?
2710
 
        :param fingerprint: Simple fingerprint for new entry: canonical-form
2711
 
            sha1 for files, referenced revision id for subtrees, etc.
 
2051
        :param fingerprint: Simple fingerprint for new entry: sha1 for files, 
 
2052
            referenced revision id for subtrees, etc.
2712
2053
        :param packed_stat: Packed stat value for new entry.
2713
2054
        :param size: Size information for new entry
2714
2055
        :param path_utf8: key[0] + '/' + key[1], just passed in to avoid doing
2715
2056
                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
2057
 
2720
2058
        If packed_stat and fingerprint are not given, they're invalidated in
2721
2059
        the entry.
2730
2068
        new_details = (minikind, fingerprint, size, executable, packed_stat)
2731
2069
        id_index = self._get_id_index()
2732
2070
        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
2750
2071
            # new entry, synthesis cross reference here,
2751
2072
            existing_keys = id_index.setdefault(key[2], set())
2752
2073
            if not existing_keys:
2757
2078
                # grab one of them and use it to generate parent
2758
2079
                # relocation/absent entries.
2759
2080
                new_entry = key, [new_details]
2760
 
                # existing_keys can be changed as we iterate.
2761
 
                for other_key in tuple(existing_keys):
 
2081
                for other_key in existing_keys:
2762
2082
                    # change the record at other to be a pointer to this new
2763
2083
                    # record. The loop looks similar to the change to
2764
2084
                    # relocations when updating an existing record but its not:
2765
2085
                    # the test for existing kinds is different: this can be
2766
2086
                    # factored out to a helper though.
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)
 
2087
                    other_block_index, present = self._find_block_index_from_key(other_key)
 
2088
                    assert present, 'could not find block for %s' % (other_key,)
 
2089
                    other_entry_index, present = self._find_entry_index(other_key,
 
2090
                                            self._dirblocks[other_block_index][1])
 
2091
                    assert present, 'could not find entry for %s' % (other_key,)
 
2092
                    assert path_utf8 is not None
 
2093
                    self._dirblocks[other_block_index][1][other_entry_index][1][0] = \
 
2094
                        ('r', path_utf8, 0, False, '')
2790
2095
 
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
2795
2096
                num_present_parents = self._num_present_parents()
2796
 
                if num_present_parents:
2797
 
                    other_key = list(existing_keys)[0]
2798
2097
                for lookup_index in xrange(1, num_present_parents + 1):
2799
2098
                    # grab any one entry, use it to find the right path.
2800
 
                    # TODO: optimise this to reduce memory use in highly
 
2099
                    # TODO: optimise this to reduce memory use in highly 
2801
2100
                    # fragmented situations by reusing the relocation
2802
2101
                    # records.
2803
2102
                    update_block_index, present = \
2804
2103
                        self._find_block_index_from_key(other_key)
2805
 
                    if not present:
2806
 
                        raise AssertionError('could not find block for %s' % (other_key,))
 
2104
                    assert present, 'could not find block for %s' % (other_key,)
2807
2105
                    update_entry_index, present = \
2808
2106
                        self._find_entry_index(other_key, self._dirblocks[update_block_index][1])
2809
 
                    if not present:
2810
 
                        raise AssertionError('update_minimal: could not find entry for %s' % (other_key,))
 
2107
                    assert present, 'could not find entry for %s' % (other_key,)
2811
2108
                    update_details = self._dirblocks[update_block_index][1][update_entry_index][1][lookup_index]
2812
 
                    if update_details[0] in 'ar': # relocated, absent
 
2109
                    if update_details[0] in ('r', 'a'): # relocated, absent
2813
2110
                        # its a pointer or absent in lookup_index's tree, use
2814
2111
                        # it as is.
2815
2112
                        new_entry[1].append(update_details)
2820
2117
            block.insert(entry_index, new_entry)
2821
2118
            existing_keys.add(key)
2822
2119
        else:
2823
 
            # Does the new state matter?
 
2120
            # Does the new state matter? 
2824
2121
            block[entry_index][1][0] = new_details
2825
2122
            # parents cannot be affected by what we do.
2826
 
            # other occurences of this id can be found
 
2123
            # other occurences of this id can be found 
2827
2124
            # from the id index.
2828
2125
            # ---
2829
2126
            # tree index consistency: All other paths for this id in this tree
2831
2128
            # we may have passed entries in the state with this file id already
2832
2129
            # that were absent - where parent entries are - and they need to be
2833
2130
            # converted to relocated.
2834
 
            if path_utf8 is None:
2835
 
                raise AssertionError('no path')
 
2131
            assert path_utf8 is not None
2836
2132
            for entry_key in id_index.setdefault(key[2], set()):
2837
2133
                # TODO:PROFILING: It might be faster to just update
2838
2134
                # rather than checking if we need to, and then overwrite
2843
2139
                    # This is the vertical axis in the matrix, all pointing
2844
2140
                    # to the real path.
2845
2141
                    block_index, present = self._find_block_index_from_key(entry_key)
2846
 
                    if not present:
2847
 
                        raise AssertionError('not present: %r', entry_key)
 
2142
                    assert present
2848
2143
                    entry_index, present = self._find_entry_index(entry_key, self._dirblocks[block_index][1])
2849
 
                    if not present:
2850
 
                        raise AssertionError('not present: %r', entry_key)
 
2144
                    assert present
2851
2145
                    self._dirblocks[block_index][1][entry_index][1][0] = \
2852
2146
                        ('r', path_utf8, 0, False, '')
2853
2147
        # add a containing dirblock if needed.
2859
2153
 
2860
2154
        self._dirblock_state = DirState.IN_MEMORY_MODIFIED
2861
2155
 
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
 
 
2877
2156
    def _validate(self):
2878
2157
        """Check that invariants on the dirblock are correct.
2879
2158
 
2880
 
        This can be useful in debugging; it shouldn't be necessary in
 
2159
        This can be useful in debugging; it shouldn't be necessary in 
2881
2160
        normal code.
2882
2161
 
2883
2162
        This must be called with a lock held.
2899
2178
            if not self._dirblocks[0][0] == '':
2900
2179
                raise AssertionError(
2901
2180
                    "dirblocks don't start with root block:\n" + \
2902
 
                    pformat(self._dirblocks))
 
2181
                    pformat(dirblocks))
2903
2182
        if len(self._dirblocks) > 1:
2904
2183
            if not self._dirblocks[1][0] == '':
2905
2184
                raise AssertionError(
2906
2185
                    "dirblocks missing root directory:\n" + \
2907
 
                    pformat(self._dirblocks))
 
2186
                    pformat(dirblocks))
2908
2187
        # the dirblocks are sorted by their path components, name, and dir id
2909
2188
        dir_names = [d[0].split('/')
2910
2189
                for d in self._dirblocks[1:]]
2928
2207
                    "dirblock for %r is not sorted:\n%s" % \
2929
2208
                    (dirblock[0], pformat(dirblock)))
2930
2209
 
 
2210
 
2931
2211
        def check_valid_parent():
2932
2212
            """Check that the current entry has a valid parent.
2933
2213
 
2952
2232
        # For each file id, for each tree: either
2953
2233
        # the file id is not present at all; all rows with that id in the
2954
2234
        # key have it marked as 'absent'
2955
 
        # OR the file id is present under exactly one name; any other entries
 
2235
        # OR the file id is present under exactly one name; any other entries 
2956
2236
        # that mention that id point to the correct name.
2957
2237
        #
2958
2238
        # We check this with a dict per tree pointing either to the present
2968
2248
                "wrong number of entry details for row\n%s" \
2969
2249
                ",\nexpected %d" % \
2970
2250
                (pformat(entry), tree_count))
2971
 
            absent_positions = 0
2972
2251
            for tree_index, tree_state in enumerate(entry[1]):
2973
2252
                this_tree_map = id_path_maps[tree_index]
2974
2253
                minikind = tree_state[0]
2975
 
                if minikind in 'ar':
2976
 
                    absent_positions += 1
2977
2254
                # have we seen this id before in this column?
2978
2255
                if file_id in this_tree_map:
2979
 
                    previous_path, previous_loc = this_tree_map[file_id]
 
2256
                    previous_path = this_tree_map[file_id]
2980
2257
                    # any later mention of this file must be consistent with
2981
2258
                    # what was said before
2982
2259
                    if minikind == 'a':
2996
2273
                        # pointed to by a relocation, which must point here
2997
2274
                        if previous_path != this_path:
2998
2275
                            raise AssertionError(
2999
 
                                "entry %r inconsistent with previous path %r "
3000
 
                                "seen at %r" %
3001
 
                                (entry, previous_path, previous_loc))
 
2276
                            "entry %r inconsistent with previous path %r" % \
 
2277
                            (entry, previous_path))
3002
2278
                        check_valid_parent()
3003
2279
                else:
3004
2280
                    if minikind == 'a':
3005
2281
                        # absent; should not occur anywhere else
3006
 
                        this_tree_map[file_id] = None, this_path
 
2282
                        this_tree_map[file_id] = None
3007
2283
                    elif minikind == 'r':
3008
 
                        # relocation, must occur at expected location
3009
 
                        this_tree_map[file_id] = tree_state[1], this_path
 
2284
                        # relocation, must occur at expected location 
 
2285
                        this_tree_map[file_id] = tree_state[1]
3010
2286
                    else:
3011
 
                        this_tree_map[file_id] = this_path, this_path
 
2287
                        this_tree_map[file_id] = this_path
3012
2288
                        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))
3023
2289
 
3024
2290
    def _wipe_state(self):
3025
2291
        """Forget all state information about the dirstate."""
3026
2292
        self._header_state = DirState.NOT_IN_MEMORY
3027
2293
        self._dirblock_state = DirState.NOT_IN_MEMORY
3028
 
        self._changes_aborted = False
3029
2294
        self._parents = []
3030
2295
        self._ghosts = []
3031
2296
        self._dirblocks = []
3032
2297
        self._id_index = None
3033
 
        self._packed_stat_index = None
3034
2298
        self._end_of_header = None
3035
2299
        self._cutoff_time = None
3036
2300
        self._split_path_cache = {}
3081
2345
            raise errors.ObjectNotLocked(self)
3082
2346
 
3083
2347
 
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
 
 
3970
2348
# Try to load the compiled form if possible
3971
2349
try:
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,
 
2350
    from bzrlib._dirstate_helpers_c import (
 
2351
        _read_dirblocks_c as _read_dirblocks,
 
2352
        bisect_dirblock_c as bisect_dirblock,
 
2353
        _bisect_path_left_c as _bisect_path_left,
 
2354
        _bisect_path_right_c as _bisect_path_right,
 
2355
        cmp_by_dirs_c as cmp_by_dirs,
3980
2356
        )
3981
 
except ImportError, e:
3982
 
    osutils.failed_to_load_extension(e)
 
2357
except ImportError:
3983
2358
    from bzrlib._dirstate_helpers_py import (
3984
 
        _read_dirblocks,
3985
 
        bisect_dirblock,
3986
 
        _bisect_path_left,
3987
 
        _bisect_path_right,
3988
 
        cmp_by_dirs,
 
2359
        _read_dirblocks_py as _read_dirblocks,
 
2360
        bisect_dirblock_py as bisect_dirblock,
 
2361
        _bisect_path_left_py as _bisect_path_left,
 
2362
        _bisect_path_right_py as _bisect_path_right,
 
2363
        cmp_by_dirs_py as cmp_by_dirs,
3989
2364
        )
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